Determine autoremovable kernels at run-time

Our kernel autoremoval helper script protects the currently booted
kernel, but it only runs whenever we install or remove a kernel,
causing it to protect the kernel that was booted at that point in time,
which is not necessarily the same kernel as the one that is running
right now.

Reimplement the logic in C++ such that we can calculate it at run-time:
Provide a function to produce a regular expression that matches all
kernels that need protecting, and by changing the default root set
function in the DepCache to make use of that expression.

Note that the code groups the kernels by versions as before, and then
marks all kernel packages with the same version.

This optimized version inserts a virtual package $kernel into the cache
when building it to avoid having to iterate over all packages in the
cache to find the installed ones, significantly improving performance at
a minor cost when building the cache.

LP: #1615381

7 files changed, 239 insertions, 83 deletions

diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc
index cd09a6944..702030943 100644
--- a/apt-pkg/algorithms.cc
+++ b/apt-pkg/algorithms.cc
@@ -16,20 +16,32 @@
 #include <config.h>
 
 #include <apt-pkg/algorithms.h>
+#include <apt-pkg/cachefilter.h>
 #include <apt-pkg/configuration.h>
 #include <apt-pkg/depcache.h>
 #include <apt-pkg/dpkgpm.h>
 #include <apt-pkg/edsp.h>
 #include <apt-pkg/error.h>
+#include <apt-pkg/macros.h>
 #include <apt-pkg/packagemanager.h>
 #include <apt-pkg/pkgcache.h>
+#include <apt-pkg/string_view.h>
+#include <apt-pkg/strutl.h>
+#include <apt-pkg/version.h>
+
 #include <apt-pkg/prettyprinters.h>
 
 #include <cstdlib>
 #include <iostream>
+#include <map>
+#include <regex>
+#include <set>
+#include <sstream>
 #include <string>
 #include <utility>
+#include <vector>
 #include <string.h>
+#include <sys/utsname.h>
 
 #include <apti18n.h>
 									/*}}}*/
@@ -1442,3 +1454,174 @@ void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
    std::sort(List,List+Count,PrioComp(Cache));
 }
 									/*}}}*/
+
+namespace APT
+{
+
+namespace KernelAutoRemoveHelper
+{
+
+// \brief Returns the uname from a kernel package name, or "" for non-kernel packages.
+std::string getUname(std::string const &packageName)
+{
+
+   static const constexpr char *const prefixes[] = {
+      "linux-image-",
+      "kfreebsd-image-",
+      "gnumach-image-",
+   };
+
+   for (auto prefix : prefixes)
+   {
+      if (likely(not APT::String::Startswith(packageName, prefix)))
+	 continue;
+      if (unlikely(APT::String::Endswith(packageName, "-dbgsym")))
+	 continue;
+      if (unlikely(APT::String::Endswith(packageName, "-dbg")))
+	 continue;
+
+      auto aUname = packageName.substr(strlen(prefix));
+
+      // aUname must start with [0-9]+\.
+      if (aUname.length() < 2)
+	 continue;
+      if (strchr("0123456789", aUname[0]) == nullptr)
+	 continue;
+      auto dot = aUname.find_first_not_of("0123456789");
+      if (dot == aUname.npos || aUname[dot] != '.')
+	 continue;
+
+      return aUname;
+   }
+
+   return "";
+}
+std::string GetProtectedKernelsRegex(pkgCache *cache, bool ReturnRemove)
+{
+   if (_config->FindB("APT::Protect-Kernels", true) == false)
+      return "";
+
+   struct CompareKernel
+   {
+      pkgCache *cache;
+      bool operator()(const std::string &a, const std::string &b) const
+      {
+	 return cache->VS->CmpVersion(a, b) < 0;
+      }
+   };
+   bool Debug = _config->FindB("Debug::pkgAutoRemove", false);
+   // kernel version -> list of unames
+   std::map<std::string, std::vector<std::string>, CompareKernel> version2unames(CompareKernel{cache});
+   // needs to be initialized to 0s, might not be set up.
+   utsname uts{};
+   std::string bootedVersion;
+   std::string lastInstalledVersion;
+
+   std::string lastInstalledUname = _config->Find("APT::LastInstalledKernel");
+
+   // Get currently booted version, but only when not on reproducible build.
+   if (getenv("SOURCE_DATE_EPOCH") == 0)
+   {
+      if (uname(&uts) != 0)
+	 abort();
+   }
+
+   auto VirtualKernelPkg = cache->FindPkg("$kernel", "any");
+   if (VirtualKernelPkg.end())
+      return "";
+
+   for (pkgCache::PrvIterator Prv = VirtualKernelPkg.ProvidesList(); Prv.end() == false; ++Prv)
+   {
+      auto Pkg = Prv.OwnerPkg();
+      if (likely(Pkg->CurrentVer == 0))
+	 continue;
+
+      auto pkgUname = APT::KernelAutoRemoveHelper::getUname(Pkg.Name());
+      auto pkgVersion = Pkg.CurrentVer().VerStr();
+
+      if (pkgUname.empty())
+	 continue;
+
+      if (Debug)
+	 std::clog << "Found kernel " << pkgUname << "(" << pkgVersion << ")" << std::endl;
+
+      version2unames[pkgVersion].push_back(pkgUname);
+
+      if (pkgUname == uts.release)
+	 bootedVersion = pkgVersion;
+      if (pkgUname == lastInstalledUname)
+	 lastInstalledVersion = pkgVersion;
+   }
+
+   if (version2unames.size() == 0)
+      return "";
+
+   auto latest = version2unames.rbegin();
+   auto previous = latest;
+   ++previous;
+
+   std::set<std::string> keep;
+
+   if (not bootedVersion.empty())
+   {
+      if (Debug || false)
+	 std::clog << "Keeping booted kernel " << bootedVersion << std::endl;
+      keep.insert(bootedVersion);
+   }
+   if (not lastInstalledVersion.empty())
+   {
+      if (Debug || false)
+	 std::clog << "Keeping installed kernel " << lastInstalledVersion << std::endl;
+      keep.insert(lastInstalledVersion);
+   }
+   if (latest != version2unames.rend())
+   {
+      if (Debug || false)
+	 std::clog << "Keeping latest kernel " << latest->first << std::endl;
+      keep.insert(latest->first);
+   }
+   if (previous != version2unames.rend())
+   {
+      if (Debug)
+	 std::clog << "Keeping previous kernel " << previous->first << std::endl;
+      keep.insert(previous->first);
+   }
+
+   std::regex special("([\\.\\+])");
+   std::ostringstream ss;
+   for (auto &pattern : _config->FindVector("APT::VersionedKernelPackages"))
+   {
+      // Legacy compatibility: Always protected the booted uname and last installed uname
+      if (not lastInstalledUname.empty())
+	 ss << "|^" << pattern << "-" << std::regex_replace(lastInstalledUname, special, "\\$1") << "$";
+      if (*uts.release)
+	 ss << "|^" << pattern << "-" << std::regex_replace(uts.release, special, "\\$1") << "$";
+      for (auto const &kernel : version2unames)
+      {
+	 if (ReturnRemove ? keep.find(kernel.first) == keep.end() : keep.find(kernel.first) != keep.end())
+	 {
+	    for (auto const &uname : kernel.second)
+	       ss << "|^" << pattern << "-" << std::regex_replace(uname, special, "\\$1") << "$";
+	 }
+      }
+   }
+
+   auto re = ss.str().substr(1);
+   if (Debug)
+      std::clog << "Kernel protection regex: " << re << "\n";
+
+   return re;
+}
+
+std::unique_ptr<APT::CacheFilter::Matcher> GetProtectedKernelsFilter(pkgCache *cache, bool returnRemove)
+{
+   auto regex = GetProtectedKernelsRegex(cache, returnRemove);
+
+   if (regex.empty())
+      return std::make_unique<APT::CacheFilter::FalseMatcher>();
+
+   return std::make_unique<APT::CacheFilter::PackageNameMatchesRegEx>(regex);
+}
+
+} // namespace KernelAutoRemoveHelper
+} // namespace APT
diff --git a/apt-pkg/algorithms.h b/apt-pkg/algorithms.h
index fc578a4ca..12a77d4b8 100644
--- a/apt-pkg/algorithms.h
+++ b/apt-pkg/algorithms.h
@@ -29,11 +29,13 @@
 #ifndef PKGLIB_ALGORITHMS_H
 #define PKGLIB_ALGORITHMS_H
 
+#include <apt-pkg/cachefilter.h>
 #include <apt-pkg/depcache.h>
 #include <apt-pkg/packagemanager.h>
 #include <apt-pkg/pkgcache.h>
 
 #include <iostream>
+#include <memory>
 #include <string>
 
 #include <apt-pkg/macros.h>
@@ -146,5 +148,17 @@ APT_PUBLIC bool pkgFixBroken(pkgDepCache &Cache);
 
 APT_PUBLIC void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List);
 
+namespace APT
+{
+namespace KernelAutoRemoveHelper
+{
+// Public for linking to apt-private, but no A{P,B}I guarantee.
+APT_PUBLIC std::unique_ptr<APT::CacheFilter::Matcher> GetProtectedKernelsFilter(pkgCache *cache, bool returnRemove = false);
+std::string GetProtectedKernelsRegex(pkgCache *cache, bool ReturnRemove = false);
+std::string getUname(std::string const &packageName);
+
+} // namespace KernelAutoRemoveHelper
+
+} // namespace APT
 
 #endif
diff --git a/apt-pkg/deb/deblistparser.cc b/apt-pkg/deb/deblistparser.cc
index 240946529..95f6f6fc8 100644
--- a/apt-pkg/deb/deblistparser.cc
+++ b/apt-pkg/deb/deblistparser.cc
@@ -11,6 +11,7 @@
 // Include Files							/*{{{*/
 #include <config.h>
 
+#include <apt-pkg/algorithms.h>
 #include <apt-pkg/aptconfiguration.h>
 #include <apt-pkg/cachefilter.h>
 #include <apt-pkg/configuration.h>
@@ -246,7 +247,12 @@ bool debListParser::NewVersion(pkgCache::VerIterator &Ver)
    
    if (ParseProvides(Ver) == false)
       return false;
-   
+   if (not APT::KernelAutoRemoveHelper::getUname(Ver.ParentPkg().Name()).empty())
+   {
+      if (not NewProvides(Ver, "$kernel", "any", Ver.VerStr(), pkgCache::Flag::MultiArchImplicit))
+	 return false;
+   }
+
    return true;
 }
 									/*}}}*/
diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index 3c9695d56..f2b3dbcdc 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -9,6 +9,7 @@
 // Include Files							/*{{{*/
 #include <config.h>
 
+#include <apt-pkg/algorithms.h>
 #include <apt-pkg/aptconfiguration.h>
 #include <apt-pkg/cachefile.h>
 #include <apt-pkg/cacheset.h>
@@ -43,6 +44,23 @@
 
 using std::string;
 
+// helper for kernel autoremoval				  	/*{{{*/
+
+/** \brief Returns \b true for packages matching a regular
+ *  expression in APT::NeverAutoRemove.
+ */
+class APT_PUBLIC DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc
+{
+   std::unique_ptr<APT::CacheFilter::Matcher> Kernels;
+
+   public:
+   DefaultRootSetFunc2(pkgCache *cache) : Kernels(APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(cache)){};
+   virtual ~DefaultRootSetFunc2(){};
+
+   bool InRootSet(const pkgCache::PkgIterator &pkg) APT_OVERRIDE { return pkg.end() == false && ((*Kernels)(pkg) || DefaultRootSetFunc::InRootSet(pkg)); };
+};
+
+									/*}}}*/
 // helper for Install-Recommends-Sections and Never-MarkAuto-Sections	/*{{{*/
 static bool 
 ConfigValueInSubTree(const char* SubTree, const char *needle)
@@ -2153,14 +2171,14 @@ APT_PURE signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgFileIterator
 									/*}}}*/
 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()		/*{{{*/
 {
-  DefaultRootSetFunc *f = new DefaultRootSetFunc;
-  if(f->wasConstructedSuccessfully())
-    return f;
-  else
-    {
+   DefaultRootSetFunc *f = new DefaultRootSetFunc2(&GetCache());
+   if (f->wasConstructedSuccessfully())
+      return f;
+   else
+   {
       delete f;
       return NULL;
-    }
+   }
 }
 
 pkgDepCache::InRootSetFunc *pkgDepCache::GetCachedRootSetFunc()
diff --git a/debian/apt.auto-removal.sh b/debian/apt.auto-removal.sh
index 2c32b0c9d..eef550a53 100644
--- a/debian/apt.auto-removal.sh
+++ b/debian/apt.auto-removal.sh
@@ -1,82 +1,15 @@
 #!/bin/sh
 set -e
-# Mark as not-for-autoremoval those kernel packages that are:
-#  - the currently booted version
-#  - the kernel version we've been called for
-#  - the latest kernel version (as determined by debian version number)
-#  - the second-latest kernel version
-#
-# In the common case this results in two kernels saved (booted into the
-# second-latest kernel, we install the latest kernel in an upgrade), but
-# can save up to four. Kernel refers here to a distinct release, which can
-# potentially be installed in multiple flavours counting as one kernel.
 
 eval $(apt-config shell APT_CONF_D Dir::Etc::parts/d)
 test -n "${APT_CONF_D}" || APT_CONF_D="/etc/apt/apt.conf.d"
 config_file="${APT_CONF_D}/01autoremove-kernels"
 
-eval $(apt-config shell DPKG Dir::bin::dpkg/f)
-test -n "$DPKG" || DPKG="/usr/bin/dpkg"
-
-list="$("${DPKG}" -l | awk '/^[ih][^nc][ ]+(linux|kfreebsd|gnumach)-image-[0-9]+\./ && $2 !~ /-dbg(:.*)?$/ && $2 !~ /-dbgsym(:.*)?$/ { print $2,$3; }' \
-   | sed -e 's#^\(linux\|kfreebsd\|gnumach\)-image-##' -e 's#:[^:]\+ # #')"
-debverlist="$(echo "$list" | cut -d' ' -f 2 | sort --unique --reverse --version-sort)"
-
-if [ -n "$1" ]; then
-	installed_version="$(echo "$list" | awk "\$1 == \"$1\" { print \$2;exit; }")"
-fi
-unamer="$(uname -r | tr '[A-Z]' '[a-z]')"
-if [ -n "$unamer" ]; then
-	running_version="$(echo "$list" | awk "\$1 == \"$unamer\" { print \$2;exit; }")"
-fi
-# ignore the currently running version if attempting a reproducible build
-if [ -n "${SOURCE_DATE_EPOCH}" ]; then
-	unamer=""
-	running_version=""
-fi
-latest_version="$(echo "$debverlist" | sed -n 1p)"
-previous_version="$(echo "$debverlist" | sed -n 2p)"
-
-debkernels="$(echo "$latest_version
-$installed_version
-$running_version
-$previous_version" | sort -u | sed -e '/^$/ d')"
-kernels="$( (echo "$1
-$unamer"; for deb in $debkernels; do echo "$list" | awk "\$2 == \"$deb\" { print \$1; }"; done; ) \
-   | sed -e 's#\([\.\+]\)#\\\1#g' -e '/^$/ d' | sort -u)"
-
 generateconfig() {
 	cat <<EOF
 // DO NOT EDIT! File autogenerated by $0
-APT::NeverAutoRemove
-{
-EOF
-	for package in $(apt-config dump --no-empty --format '%v%n' 'APT::VersionedKernelPackages'); do
-		for kernel in $kernels; do
-			echo "   \"^${package}-${kernel}$\";"
-		done
-	done
-	echo '};'
-	if [ "${APT_AUTO_REMOVAL_KERNELS_DEBUG:-true}" = 'true' ]; then
-		cat <<EOF
-/* Debug information:
-# dpkg list:
-$(dpkg -l | grep '\(linux\|kfreebsd\|gnumach\)-image-')
-# list of installed kernel packages:
-$list
-# list of different kernel versions:
-$debverlist
-# Installing kernel: $installed_version ($1)
-# Running kernel: ${running_version:-ignored} (${unamer:-ignored})
-# Last kernel: $latest_version
-# Previous kernel: $previous_version
-# Kernel versions list to keep:
-$debkernels
-# Kernel packages (version part) to protect:
-$kernels
-*/
+APT::LastInstalledKernel "$1";
 EOF
-	fi
 }
 generateconfig "$@" > "${config_file}.dpkg-new"
 mv -f "${config_file}.dpkg-new" "$config_file"
diff --git a/doc/examples/configure-index b/doc/examples/configure-index
index b73166082..571bf2369 100644
--- a/doc/examples/configure-index
+++ b/doc/examples/configure-index
@@ -54,6 +54,9 @@ APT
   Build-Profiles "<STRING_OR_LIST>";
 
   NeverAutoRemove "<LIST>";  // list of package name regexes
+  LastInstalledKernel "<STRING>"; // last installed kernel version
+  VersionedKernelPackages "<LIST>"; // regular expressions to be protected from autoremoval (kernel uname will be appended)
+  Protect-Kernels "<BOOL>"; // whether to protect installed kernels against autoremoval (default: true)
 
   // Options for apt-get
   Get
diff --git a/test/integration/test-kernel-helper-autoremove b/test/integration/test-kernel-helper-autoremove
index 9cc978645..8dac44b93 100755
--- a/test/integration/test-kernel-helper-autoremove
+++ b/test/integration/test-kernel-helper-autoremove
@@ -38,9 +38,8 @@ testprotected() {
 	testsuccess --nomsg test -e rootdir/etc/apt/apt.conf.d/01autoremove-kernels
 	testfilestats 'rootdir/etc/apt/apt.conf.d/01autoremove-kernels' '%U:%G:%a' '=' "${TEST_DEFAULT_USER}:${TEST_DEFAULT_GROUP}:444"
 
-	msgtest 'Check kernel autoremoval protection list' 'can be dumped'
-	testsuccess --nomsg aptconfig dump --no-empty --format '%v%n' 'APT::NeverAutoRemove'
-	cp rootdir/tmp/testsuccess.output protected.list
+    testsuccess --nomsg apt -o Debug::PkgAutoRemove=1 autoremove -s
+    grep "Kernel protection regex" rootdir/tmp/testsuccess.output | cut -f2- -d: | tr '|' '\n' | sed 's/\s*//g' | sort -u > protected.list
 
 	msgtest 'Check kernel autoremoval protection list' 'can be parsed'
 	testfailure --nomsg grep '^[A-Z]: ' protected.list
@@ -71,7 +70,7 @@ The following packages were automatically installed and are no longer required:
    ${CURRENTKERNEL}-686-pae:i386 (5-1)
    ${CURRENTKERNEL}-dbg (5-1)
 Use '$AUTOREMOVE' to remove them.
-0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -sV
+0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -sV -o APT::Protect-Kernels=0
 testsuccessequal "Reading package lists...
 Building dependency tree...
 Reading state information...
@@ -85,13 +84,13 @@ The following packages were automatically installed and are no longer required:
    ${CURRENTKERNEL}-dbg (5-1)
    ${CURRENTKERNEL}-rt (5-1)
 Use '$AUTOREMOVE' to remove them.
-0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -sV --ignore-hold
+0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -sV --ignore-hold -o APT::Protect-Kernels=0
 testequal "Reading package lists...
 Building dependency tree...
 Reading state information...
 7 packages were automatically installed and are no longer required.
 Use '$AUTOREMOVE' to remove them.
-0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -s -o APT::Get::HideAutoRemove=small
+0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -s -o APT::Get::HideAutoRemove=small -o APT::Protect-Kernels=0
 testequal "Reading package lists...
 Building dependency tree...
 Reading state information...
@@ -110,7 +109,7 @@ Remv linux-image-100.0.0-1-generic [100.0.0-1]
 Remv $CURRENTKERNEL [5-1]
 Remv ${CURRENTKERNEL}+variant [5-1]
 Remv ${CURRENTKERNEL}-686-pae:i386 [5-1]
-Remv ${CURRENTKERNEL}-dbg [5-1]" aptget autoremove -sV
+Remv ${CURRENTKERNEL}-dbg [5-1]" aptget autoremove -sV -o APT::Protect-Kernels=0
 
 msgmsg "run without parameter"
 testprotected
@@ -168,7 +167,7 @@ Remv ${CURRENTKERNEL}-dbg [5-1]" aptget autoremove -s
 unset COLUMNS
 
 # rt kernel was put on hold while the protected list was generated
-testsuccess aptmark unhold "${CURRENTKERNEL}-rt"
+testsuccess aptmark hold "${CURRENTKERNEL}-rt"
 export COLUMNS=99999
 testsuccessequal "Reading package lists...
 Building dependency tree...