I get a set of upgrades, about once a day these days (the Ubuntu and other Open Source developers are keeping way too busy!)

Because of that, I run the software updater. That takes time, generally. But why is that?

After various upgrades from one OS version to another, possibly from the start, I dunno exactly when it broke, but the autoremove feature stopped uninstalling the old kernels.

In itself, it is not so bad, you just get additional kernels under /boot. It can be come a problem if you have a small /boot partition, but otherwise, it is not a big problem in itself.

Until you upgrade!

Yes. At that point, the system detects that the kernel needs to be regenerated, and it will regenerate each single version with "the correct modules". Only if you have lingering old kernels, it will fail so each time you upgrade anything (whether the upgrade includes kernels) it slows down to a crawl since each time it tries to recompile the nVidia module and a few other things and then fails, it marks down that it failed, and next time it gives it a try again and again...

So, what you want to do is removing these old kernel.

1) Make sure you know which kernel you are running:

prompt $ uname -a
Linux halk 4.4.0-28-generic #47-Ubuntu SMP Fri Jun 24 10:09:13 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux

The version of the kernel appears, as here it is 4.4.0-28-generic

2) List all the installed kernels

ls /boot

Here you see the list of all your kernels. If you changed something and are not using /boot, your kernels could be somewhere else, but they are likely there under Debian and Ubuntu.

3) Find the corresponding package names

dpkg -l | grep <version>

The /boot output shows lists of kernels with their version. For example, you will see a file such as:

initrd.img-4.4.0-28-generic

Here the version is 4.4.0-28-generic so the grep as shown before would use:

dpkg -l | grep 4.4.0-28-generic

This will list several files and I suggest you purge them, otherwise you will get many "rc" entries with files that linger on your computer, files you are not likely to ever re-use since it was for a version of a kernel you do not even want to run.

ii  linux-headers-4.4.0-28-generic      4.4.0-28.47  amd64  Linux kernel headers for version 4.4.0 on 64 bit x86 SMP
ii  linux-image-4.4.0-28-generic        4.4.0-28.47  amd64  Linux kernel image for version 4.4.0 on 64 bit x86 SMP
ii  linux-image-extra-4.4.0-28-generic  4.4.0-28.47  amd64  Linux kernel extra modules for version 4.4.0 on 64 bit x86 SMP

WARNING: a kernel version COULD VERY WELL MATCH another software version. So please double check that it says "Linux kernel" in the description area.

4) Remove those packages

WARNING: The following command is DANGEROUS. Make double sure that the version being purged is NOT the one you are running on. It should not work, but it will depend in which state apt-get/dpkg are to prevent you from removing your running kernel.

apt-get purge linux-headers-4.4.0-28-generic linux-image-4.4.0-28-generic linux-image-extra-4.4.0-28-generic

Now we can remove all of these kernel files at once.

Note that you may run an apt-get purge with any number of packages (although the command line is limited to 32Kb under Linux) so you can remove several kernels at the same time. This will generally go faster since you will skip the step where it recomputes grub's files...