Upgrading from jammy to noble results in a linux-headers package being in a broken state

[Ankush Pathak]

(For APT SRU versioning, see https://wiki.ubuntu.com/AptUpdates)

[Impact]
Obsolete packages can be removed despite still having reverse dependencies installed, for example:

Now that 24.04.1 has been released, 22.04 users are encouraged to upgrade to 24.04 via the `do-release-upgrade` command. This issue was seen whilst testing this upgrade path.
Upgrading and later rebooting a jammy GCP instance results in `linux-headers-6.5.0-1025-gcp` being a broken state.

```
$ sudo apt install
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
You might want to run 'apt --fix-broken install' to correct these.
The following packages have unmet dependencies:
 linux-headers-6.5.0-1025-gcp : Depends: linux-gcp-6.5-headers-6.5.0-1025 but it is not installable
E: Unmet dependencies. Try 'apt --fix-broken install' with no packages (or specify a solution).
```
`linux-gcp-6.5-headers-6.5.0-1025` is a dependency of `linux-image-6.5.0-1025-gcp` which is also not removed during the upgrade.

```
$ apt-cache rdepends linux-headers-6.5.0-1025-gcp
linux-headers-6.5.0-1025-gcp
Reverse Depends:
  linux-image-6.5.0-1025-gcp
$ apt-cache rdepends linux-image-6.5.0-1025-gcp
linux-image-6.5.0-1025-gcp
Reverse Depends:
```

Running `apt --fix-broken install` resolves the error.
```
$ sudo apt --fix-broken install
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
Correcting dependencies... Done
The following packages will be REMOVED:
  linux-headers-6.5.0-1025-gcp
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
After this operation, 27.9 MB disk space will be freed.
Do you want to continue? [Y/n] y
(Reading database ... 83770 files and directories currently installed.)
Removing linux-headers-6.5.0-1025-gcp (6.5.0-1025.27~22.04.1) ...
$ sudo apt install
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
```

This issue was also observed after upgrading a jammy AWS instance to noble.

```
$ sudo apt install
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
You might want to run 'apt --fix-broken install' to correct these.
The following packages have unmet dependencies:
 linux-headers-6.5.0-1024-aws : Depends: linux-aws-6.5-headers-6.5.0-1024 but it is not installable
E: Unmet dependencies. Try 'apt --fix-broken install' with no packages (or specify a solution).
```

[Test plan]

## Jammy APT verification

To prepare the VMs, follow the following scheme:

$ lxc launch ubuntu:jammy jammy-to-noble --vm

If using lxc shell or exec to connect to it, also perform the step below:

$ lxc exec jammy-to-noble apt-mark lxd-agent-launcher # otherwise it resets

On this jammy VM, edit /etc/update-manager/release-upgrades and set Prompt to "normal" (since release upgrades to noble via the lts prompt are temporarily blocked due to this bug)

If this test run is meant to test the fix, then at this point you should install apt from jammy proposed. Otherwise, continue directly with the release upgrade.

Then to continue with the test, proceed to the release upgrade:

$ sudo do-release-upgrade

Check that currently booted linux-headers- are *not* removed as obsolete.

After the reboot at the end, in the rebooted system, issue:

$ sudo apt upgrade

With the bug present, you will get an error like this:
$ sudo apt upgrade
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
You might want to run 'apt --fix-broken install' to correct these.
The following packages have unmet dependencies:
 linux-headers-5.15.0-1065-kvm : Depends: linux-kvm-headers-5.15.0-1065 but it is not installable
E: Unmet dependencies. Try 'apt --fix-broken install' with no packages (or specify a solution).

## Noble APT verification

To validate the APT change on noble, we must rely on the test suite as we won't have a noble->oracular upgrade bug causing it, most likely.

To validate an ubuntu-release-upgrader change, instead run:

ubuntu@jammy-to-noble$ do-release-upgrade -p
ubuntu@mantic-to-noble$ do-release-upgrade -p

[Where problems could occur: APT SRU]

For the APT change, the function in question is used in a small number of places:

In APT library:
- In the `upgrade` command and library function. Removals are already undone there before calling it so we never reach the new code path.
- In the phased update implementation, during dist-upgrade. I expect a failure is lurking there that is fixed by this, but I haven't been able to write a reproducer to trigger it just yet.

In aptitude:
- The function is wrapped, but the wrapper never called

In QApt:
- QApt seems to rely on it for upgrading and doesn't seem to have any error checking of the return value. I expect it will read the error

[Where problems could occur: u-r-u SRU]
Upgrades will now result in a consistent state, but may spend hours searching for obsolete software again.

[Julian Andres Klode (juliank)]

This is missing the /var/log/dist-upgrade information, commonly collected by ubuntu-bug ubuntu-release-upgrader

[Launchpad Janitor (janitor)]

Status changed to 'Confirmed' because the bug affects multiple users.

[Moshe Caspi (mcaspi12)]

Had the same issue with linux-headers-5.15.0-119-generic:amd64.

[Gauthier Jolly (gjolly)]

I was also able to reproduce on Azure. After upgrading from jammy to noble using do-release-upgrade and rebooting:

$ sudo apt install
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
You might want to run 'apt --fix-broken install' to correct these.
The following packages have unmet dependencies:
 linux-cloud-tools-6.5.0-1025-azure : Depends: linux-azure-6.5-cloud-tools-6.5.0-1025 but it is not installable
 linux-headers-6.5.0-1025-azure : Depends: linux-azure-6.5-headers-6.5.0-1025 but it is not installable
 linux-tools-6.5.0-1025-azure : Depends: linux-azure-6.5-tools-6.5.0-1025 but it is not installable
E: Unmet dependencies. Try 'apt --fix-broken install' with no packages (or specify a solution).

[Ankush Pathak (ankushpathak)]

Issue was reproducible on jammy generic[0] and kvm[1] download images too.

Generic download image
```
$ sudo apt install
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
You might want to run 'apt --fix-broken install' to correct these.
The following packages have unmet dependencies:
 linux-headers-5.15.0-119-generic : Depends: linux-headers-5.15.0-119 but it is not installable
E: Unmet dependencies. Try 'apt --fix-broken install' with no packages (or specify a solution).
```

KVM download image
```
$ sudo apt install
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
You might want to run 'apt --fix-broken install' to correct these.
The following packages have unmet dependencies:
 linux-headers-5.15.0-1065-kvm : Depends: linux-kvm-headers-5.15.0-1065 but it is not installable
E: Unmet dependencies. Try 'apt --fix-broken install' with no packages (or specify a solution).
```

[0]: https://cloud-images.ubuntu.com/jammy/20240823/jammy-server-cloudimg-amd64.img
[1]: https://cloud-images.ubuntu.com/jammy/20240823/jammy-server-cloudimg-amd64-disk-kvm.img

[Stefan Bader (smb)]

As a disclaimer, this is not meant as a final solution. It is still unclear what goes wrong and how to address this. Just from the versions reported broken it sounds like those were kernels running before the upgrade and after reboot people should be running 6.8 kernels. If that is true, then it *might* help for individual systems to identify the offending 5.15 or 6.5 kernel packages and remove them with dpkg (NOT if that is still the running kernel, of course). That evicts an older fallback kernel but might get the system back into a state where it receives updates.

[Julian Andres Klode (juliank)]

Thanks this seems to be a bug in the APT solver not undoing the purge requests here, a regression from when we switched to the new obsoletes handling. This is odd, I am investigating

[Julian Andres Klode (juliank)]

Turns out that yes this is a bug in the APT solver:

https://salsa.debian.org/apt-team/apt/-/merge_requests/373/diffs

It was not restoring/keeping obsolete (in its parlance, no longer downloadable) packages that are marked for removal due to a false optimization.

[Dylan Uhryniuk (uhryniuk)]

This was reproduced on Oracle images when running Jammy -> Noble then reboot.

```
$ sudo apt install
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
You might want to run 'apt --fix-broken install' to correct these.
The following packages have unmet dependencies:
 linux-headers-6.5.0-1027-oracle : Depends: linux-oracle-6.5-headers-6.5.0-1027 but it is not installable
E: Unmet dependencies. Try 'apt --fix-broken install' with no packages (or specify a solution).
```

[Julian Andres Klode (juliank)]

apt/jammy SRU uploaded. The ones for noble and devel need a bit more massaging due to test suite failures but are not relevant before oracular is released (noble's apt is used for noble->oracular updates)

[Julian Andres Klode (juliank)]

ubuntu-release-upgrader SRU uploaded to noble and also uploaded to oracular.

These reintroduce the slow path as a fallback, specifically for APT versions prior to this SRU (and hence mantic); they also fix that code to correctly consider running kernels (and KeepInstalledSection) in the removal of reverse dependencies of obsolete packages.

[Andreas Hasenack (ahasenack)]

I was able to reproduce this in jammy lxd VM, and tweaked the test plan a bit.

I'm going to accept this into jammy-proposed in order to allow for testing to begin quickly, but we still need the noble and oracular uploads as well.

The APT noble test plan could also use some refinement, there are still too many unknowns there, and not clear steps as to what should happen and what shouldn't.

[Andreas Hasenack (ahasenack)]

Hello Ankush, or anyone else affected,

Accepted apt into jammy-proposed. The package will build now and be available at https://launchpad.net/ubuntu/+source/apt/2.4.13 in a few hours, and then in the -proposed repository.

Please help us by testing this new package. See https://wiki.ubuntu.com/Testing/EnableProposed for documentation on how to enable and use -proposed. Your feedback will aid us getting this update out to other Ubuntu users.

If this package fixes the bug for you, please add a comment to this bug, mentioning the version of the package you tested, what testing has been performed on the package and change the tag from verification-needed-jammy to verification-done-jammy. If it does not fix the bug for you, please add a comment stating that, and change the tag to verification-failed-jammy. In either case, without details of your testing we will not be able to proceed.

Further information regarding the verification process can be found at https://wiki.ubuntu.com/QATeam/PerformingSRUVerification . Thank you in advance for helping!

N.B. The updated package will be released to -updates after the bug(s) fixed by this package have been verified and the package has been in -proposed for a minimum of 7 days.

[Launchpad Janitor (janitor)]

This bug was fixed in the package ubuntu-release-upgrader - 1:24.10.9

---------------
ubuntu-release-upgrader (1:24.10.9) oracular; urgency=medium

  * Ensure that we remove only the right obsolete packages, specifically
    not kernel packages (LP: #2078720):
    - Revert back to old obsolete logic if new one fails
    - Force obsolete removals on non-foreign packages
    - Consistently check that we do not remove protected obsolete packages
  * Run pre-build.sh: updating mirrors, demotions, and translations.

 -- Julian Andres Klode <email address hidden> Thu, 05 Sep 2024 21:11:05 +0200

[Ubuntu SRU Bot (ubuntu-sru-bot)]

All autopkgtests for the newly accepted apt (2.4.13) for jammy have finished running.
The following regressions have been reported in tests triggered by the package:

apport/2.20.11-0ubuntu82.6 (s390x)
apt/2.4.13 (s390x)
auto-apt-proxy/14 (s390x)
debspawn/0.5.2-1 (arm64)
dgit/9.15 (armhf)
gcc-11/11.4.0-1ubuntu1~22.04 (arm64)
libqapt/3.0.5-1ubuntu1 (armhf)
ruby-debian/unknown (armhf)
sbuild/0.81.2ubuntu6 (arm64)

Please visit the excuses page listed below and investigate the failures, proceeding afterwards as per the StableReleaseUpdates policy regarding autopkgtest regressions [1].

https://people.canonical.com/~ubuntu-archive/proposed-migration/jammy/update_excuses.html#apt

[1] https://wiki.ubuntu.com/StableReleaseUpdates#Autopkgtest_Regressions

Thank you!

[Łukasz Zemczak (sil2100)]

Hello Ankush, or anyone else affected,

Accepted ubuntu-release-upgrader into noble-proposed. The package will build now and be available at https://launchpad.net/ubuntu/+source/ubuntu-release-upgrader/1:24.04.23 in a few hours, and then in the -proposed repository.

Please help us by testing this new package. See https://wiki.ubuntu.com/Testing/EnableProposed for documentation on how to enable and use -proposed. Your feedback will aid us getting this update out to other Ubuntu users.

If this package fixes the bug for you, please add a comment to this bug, mentioning the version of the package you tested, what testing has been performed on the package and change the tag from verification-needed-noble to verification-done-noble. If it does not fix the bug for you, please add a comment stating that, and change the tag to verification-failed-noble. In either case, without details of your testing we will not be able to proceed.

Further information regarding the verification process can be found at https://wiki.ubuntu.com/QATeam/PerformingSRUVerification . Thank you in advance for helping!

N.B. The updated package will be released to -updates after the bug(s) fixed by this package have been verified and the package has been in -proposed for a minimum of 7 days.

[Łukasz Zemczak (sil2100)]

I have accepted the ubuntu-release-upgrader SRU, but I would like to understand better the mentioned regression potential. It mentions the risk of spending hours searching for obsolete packages. How bad is it? Was it how it was previously? What can trigger such a long wait time?

[Julian Andres Klode (juliank)]

Verifying the apt/jammy SRU:

I installed libapt-pkg6.0=2.4.13 from proposed, then run `do-release-upgrade -p` (`-d` should work now too, but was broken before):

The headers for the running kernel are not being removed:

Remove (was auto installed) binutils binutils-common
  binutils-x86-64-linux-gnu gcc-12-base irqbalance isc-dhcp-client
  isc-dhcp-common libaio1 libappstream4 libbinutils libbpf0
  libcbor0.8 libctf-nobfd0 libctf0 libdns-export1110 libgprofng0
  libicu70 libisc-export1105 libldap-2.5-0 libmpdec3 libnetplan0
  libnsl2 libpcre3 libperl5.34 libprocps8 libpython3.10
  libpython3.10-minimal libpython3.10-stdlib libsframe1 libunistring2
  linux-headers-kvm perl-modules-5.34 pkexec policykit-1
  python3-jaraco.classes python3-jeepney python3-keyring
  python3-secretstorage python3.10 python3.10-minimal
  ubuntu-advantage-tools

(linux-headers-kvm is, it got replaced by linux-headers-virtual).

And apt upgrade is happy:

root@jammy-to-noble:~# apt upgrade
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
Calculating upgrade... Done
The following packages have been kept back:
  lxd-agent-loader
0 upgraded, 0 newly installed, 0 to remove and 1 not upgraded.

[Julian Andres Klode (juliank)]

@sil2100 The regression in time is back to the old behavior prior to 24.04.20; actually it's a bit faster as there is just a single action group now. But the reason for it was that we iterated over all packages in the cache and recorded their selected state in case we needed to undo a change (verifying the change is allowed was equally expensive).

What triggers this? The run time is linear to the number of obsolete Ubuntu packages (packages no longer in noble) you have installed. In a small lxd VM, it is sub-second vs 20 seconds or so, on a desktop with many obsolete packages installed it will be a lot longer.

Updates from jammy to noble won't see the regression, the apt 2.4.13 SRU I just verified fixes the APT algorithm so it should never fallback.

[Julian Andres Klode (juliank)]

Upgrading with ubuntu-release-upgrader from proposed also worked correctly:

$ lxc list -c nft
+--------------------------+--------------+-----------------+
| NAME | BASE IMAGE | TYPE |
+--------------------------+--------------+-----------------+
| jammy-to-noble-proposed | d45dfeba51e0 | VIRTUAL-MACHINE |
+--------------------------+--------------+-----------------+
| mantic-to-noble-proposed | 554642c1987e | VIRTUAL-MACHINE |
+--------------------------+--------------+-----------------+
$ lxc exec mantic-to-noble-proposed grep "INFO.*version" /var/log/dist-upgrade/main.log
2024-09-06 13:58:31,556 INFO apt version: '2.7.3ubuntu0.1'
2024-09-06 13:58:31,556 INFO python version: '3.11.6 (main, Apr 10 2024, 17:26:07) [GCC 13.2.0]'
2024-09-06 13:58:31,558 INFO release-upgrader version '24.04.23' started
$ lxc exec jammy-to-noble-proposed grep "INFO.*version" /var/log/dist-upgrade/main.log
2024-09-06 13:58:30,075 INFO apt version: '2.4.12'
2024-09-06 13:58:30,076 INFO python version: '3.10.12 (main, Jul 29 2024, 16:56:48) [GCC 11.4.0]'
2024-09-06 13:58:30,078 INFO release-upgrader version '24.04.23' started

^ looks good :)

Now as for the verification itself:

***jammy***

Remove: libblockdev-crypto2 libblockdev-fs2 libblockdev-loop2
  libblockdev-part-err2 libblockdev-part2 libblockdev-swap2
  libblockdev-utils2 libblockdev2 libtss2-mu0

Remove (was auto installed) binutils binutils-common
  binutils-x86-64-linux-gnu gcc-12-base irqbalance isc-dhcp-client
  isc-dhcp-common libaio1 libappstream4 libbinutils libbpf0
  libcbor0.8 libctf-nobfd0 libctf0 libdns-export1110 libgprofng0
  libicu70 libisc-export1105 libldap-2.5-0 libmpdec3 libnetplan0
  libnsl2 libpcre3 libperl5.34 libprocps8 libpython3.10
  libpython3.10-minimal libpython3.10-stdlib libsframe1 libunistring2
  linux-headers-kvm perl-modules-5.34 pkexec policykit-1
  python3-jaraco.classes python3-jeepney python3-keyring
  python3-secretstorage python3.10 python3.10-minimal
  ubuntu-advantage-tools

Finally:

root@jammy-to-noble-proposed:~# apt-get upgrade
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
Calculating upgrade... Done
The following packages have been kept back:
  lxd-agent-loader
0 upgraded, 0 newly installed, 0 to remove and 1 not upgraded.

***mantic***
Remove (was auto installed) bolt fwupd-signed gcc-13-base irqbalance
  jq libaio1 libappstream4 libarchive13t64 libatasmart4
  libblockdev-crypto3 libblockdev-fs3 libblockdev-loop3
  libblockdev-mdraid3 libblockdev-nvme3 libblockdev-part3
  libblockdev-swap3 libblockdev-utils3 libblockdev3
  libbytesize-common libbytesize1 libcbor0.8 libflashrom1 libftdi1-2
  libfwupd2 libgcab-1.0-0 libgpgme11t64 libgusb2 libicu72 libjcat1
  libjq1 libjson-glib-1.0-0 libjson-glib-1.0-common libmbim-glib4
  libmbim-proxy libmbim-utils libmm-glib0 libnetplan0 libnsl2
  libnspr4 libnss-nis libnss-nisplus libnss3 libnvme1t64 libonig5
  libperl5.36 libprotobuf-c1 libpython3.11 libpython3.11-minimal
  libpython3.11-stdlib libqmi-glib5 libqmi-proxy ...

[Łukasz Zemczak (sil2100)]

The verification of the Stable Release Update for apt has completed successfully and the package is now being released to -updates. Subsequently, the Ubuntu Stable Release Updates Team is being unsubscribed and will not receive messages about this bug report. In the event that you encounter a regression using the package from -updates please report a new bug using ubuntu-bug and tag the bug report regression-update so we can easily find any regressions.

[Launchpad Janitor (janitor)]

This bug was fixed in the package ubuntu-release-upgrader - 1:24.04.23

---------------
ubuntu-release-upgrader (1:24.04.23) noble; urgency=medium

  * Ensure that we remove only the right obsolete packages, specifically
    not kernel packages (LP: #2078720):
    - Revert back to old obsolete logic if new one fails
    - Force obsolete removals on non-foreign packages
    - Consistently check that we do not remove protected obsolete packages
  * Run pre-build.sh: updating mirrors, demotions, and translations.

 -- Julian Andres Klode <email address hidden> Thu, 05 Sep 2024 21:11:05 +0200

[Launchpad Janitor (janitor)]

This bug was fixed in the package apt - 2.4.13

---------------
apt (2.4.13) jammy; urgency=medium

  * Fix keeping back removals of obsolete packages (LP: #2078720)
  * Return an error if ResolveByKeep() is unsuccessful (LP: #2078720)

 -- Julian Andres Klode <email address hidden> Thu, 05 Sep 2024 16:43:03 +0200

[A Feldman (aaronmfeld)]

Not fixed. Its Sept. 11 and I reinstalled and reupgraded no dice.

[Julian Andres Klode (juliank)]

@aaronmfeld If you have an upgrade issue, please file a separate issue, this particular one has been verified as fixed.

[Julian Andres Klode (juliank)]

Tagging this for the apt/noble and apt/oracular uploads.