Cannot apt upgrade due to kernel package problems

an Ubuntu 14.04 LTS user here.

Basically I had a problem when running

sudo apt-get update
sudo apt-get upgrade

An error code was returned by dpkg because the Linux kernel package 3.13.0.57 was being marked as "not fully installed":

Errors were encountered while processing:
 linux-image-3.13.0.57-generic
 linux-image-extra-3.13.0-57-generic
E: Sub-process /usr/bin/dpkg returned an error code (1)

I typed uname -r in order to see what the current version of my system kernel is and surprisingly it was 3.13.0.57. Afterwards I rebooted the system and entered grub to list all of the installed linux kernels and saw that I have 3.8.0-35-generic so I booted in with it to try to reinstall the 3.13.0.57 version. I do not have any clue why by default Ubuntu 14.04 boots with 3.13.0.57 when 3.8.0-35 is available.

After I had successfully booted with 3.8.0 I listed once again all of the kernels I have with dpkg in order to be sure that 3.13.0-57 exists.

sudo dpkg --list | grep linux-image
sudo apt-get purge linux-image-3.13.0.57-generic
sudo apt-get purge linux-image-extra-3.13.0-57-generic

But the extra image package cannot be removed, while the pure linux image can:

Errors were encountered while processing:
 linux-image-extra-3.13.0-57-generic
E: Sub-process /usr/bin/dpkg returned an error code (1)

Any ideas how to fix this? I searched and saw that a possible lack of space on the boot partition can cause this type of problem but I think my case is different. I managed to clear 4-5 old kernels manually in order to be sure that I have freed enough space on the boot partition.

Edit 1: I saw that Ubuntu 14.04.2 ships with Linux Kernel 3.16.x but I do not have it. The newest one I have is 3.8.0-35 and then comes 3.13.0-57.

Edit 2: Running sudo apt-get autoremove or sudo apt-get dist-upgrade does not help. It seems that I cannot run any upgrades. Here is the log of sudo apt-get autoremove:

    $ sudo apt-get autoremove
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages will be REMOVED:
  linux-image-extra-3.13.0-57-generic
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
2 not fully installed or removed.
After this operation, 152 MB disk space will be freed.
Do you want to continue? [Y/n] y
(Reading database ... 747752 files and directories currently installed.)
Removing linux-image-extra-3.13.0-57-generic (3.13.0-57.95) ...
depmod: FATAL: could not load /boot/System.map-3.13.0-57-generic: No such file or directory
run-parts: executing /etc/kernel/postinst.d/apt-auto-removal 3.13.0-57-generic /boot/vmlinuz-3.13.0-57-generic
run-parts: executing /etc/kernel/postinst.d/dkms 3.13.0-57-generic /boot/vmlinuz-3.13.0-57-generic
run-parts: executing /etc/kernel/postinst.d/initramfs-tools 3.13.0-57-generic /boot/vmlinuz-3.13.0-57-generic
update-initramfs: Generating /boot/initrd.img-3.13.0-57-generic
grep: /boot/config-3.13.0-57-generic: No such file or directory
run-parts: executing /etc/kernel/postinst.d/pm-utils 3.13.0-57-generic /boot/vmlinuz-3.13.0-57-generic
run-parts: executing /etc/kernel/postinst.d/update-notifier 3.13.0-57-generic /boot/vmlinuz-3.13.0-57-generic
run-parts: executing /etc/kernel/postinst.d/zz-runlilo 3.13.0-57-generic /boot/vmlinuz-3.13.0-57-generic
Fatal: open /boot/vmlinuz-3.13.0-46-generic.efi.signed: No such file or directory
run-parts: /etc/kernel/postinst.d/zz-runlilo exited with return code 1
dpkg: error processing package linux-image-extra-3.13.0-57-generic (--remove):
 subprocess installed post-removal script returned error exit status 1
Errors were encountered while processing:
 linux-image-extra-3.13.0-57-generic
E: Sub-process /usr/bin/dpkg returned an error code (1)

I don't know what this - Fatal: open /boot/vmlinuz-3.13.0-46-generic.efi.signed: No such file or directory has to do with removing 3.13.0-57.

Solution 1:

I managed to find a solution to the problem. Nevertheless I decided to post it as an answer if someone with the same problem struggles.

The cause of the problem:

I checked the dpkg status of the packages:

dpkg --status linux-image-3.13.0.57-generic
dpkg --status linux-image-extra-3.13.0-57-generic

The output clearly stated that the packages were in bad state. They were "not fully installed" as I have written in the question above.

The solution:

The entries of these packages must be deleted from the status file of dpkg in order apt-get to function normally. The steps are as follows:

1. Make sure to make a back up of the status file if something goes wrong.

   sudo cp /var/lib/dpkg/status /var/lib/dpkg/status.backup

2. Open /var/lib/dpkg/status with your preferred text editor and search and delete ONLY the references of the broken packages. You must not delete anything else!

3. Run sudo apt-get upgrade to make sure that everything is fixed.

Solution 2:

wajig remove linux-headers-3.13.0-57-generic worked for me.

I rebooted and was on 3.13.0-57-generic kernel.

Be careful though! Backup your data.

Solution 3:

If you wanna upgrade to a New kernel Version you can install it manually through the "linux-image-lts..." packages vor through "apt-get dist-upgrade"

These failures offen happen in full luks encrypted Volumens cause /boot is much too small in these Setups.

Perhaps a "apt-get autoremove" helps too...