Add support for Phased-Update-Percentage

This adds support for Phased-Update-Percentage by pinning
upgrades that are not to be installed down to 1.

The output of policy has been changed to add the level of
phasing, and documentation has been improved to document
how phased updates work.

The patch detects if it is running in a chroot, and if so, always
includes phased updates, restoring classic apt behavior to avoid
behavioral changes on buildd chroots.

Various options are added to control this all:

* APT::Get::{Always,Never}-Include-Phased-Updates and their legacy
  update-manager equivalents to always or never include phased updates
* APT::Machine-ID can be set to a UUID string to have all machines in a
  fleet phase the same
* Dir::Etc::Machine-ID is weird in that it's default is sort of like
  ../machine-id, but not really, as ../machine-id would look up
  $PWD/../machine-id and not relative to Dir::Etc; but it allows you to
  override the path to machine-id (as opposed to the value)
* Dir::Bin::ischroot is the path to the ischroot(1) binary which is used
  to detect whether we are running in a chroot.

9 files changed, 152 insertions, 5 deletions

diff --git a/apt-pkg/aptconfiguration.cc b/apt-pkg/aptconfiguration.cc
index 61e53ec3a..b3b423fdc 100644
--- a/apt-pkg/aptconfiguration.cc
+++ b/apt-pkg/aptconfiguration.cc
@@ -480,4 +480,65 @@ std::string const Configuration::getBuildProfilesString() {
 	return list;
 }
 									/*}}}*/
+
+// getMachineID - supported data.tar extensions		/*{{{*/
+// ---------------------------------------------------------------------
+/* */
+std::string const Configuration::getMachineID()
+{
+   std::string id = _config->Find("APT::Machine-ID");
+
+   if (id.empty())
+   {
+      std::string file = _config->FindFile("Dir::Etc::machine-id");
+
+      if (file.empty())
+      {
+	 file = flCombine(_config->FindDir("Dir::Etc"), "../machine-id");
+      }
+      FileFd fd;
+      _error->PushToStack();
+
+      if (not OpenConfigurationFileFd(file, fd) || not fd.ReadLine(id))
+      {
+	 if (_config->FindB("Debug::Phasing", false))
+	 {
+	    _error->DumpErrors(std::clog);
+	 }
+      }
+
+      _error->RevertToStack();
+   }
+
+   return id;
+}
+									/*}}}*/
+// isChroot - whether we are inside a chroot			     	/*{{{*/
+// ---------------------------------------------------------------------
+/* */
+bool Configuration::isChroot()
+{
+   static struct once
+   {
+      bool res = false;
+      once()
+      {
+	 pid_t child = ExecFork();
+	 if (child == 0)
+	 {
+	    auto binary = _config->FindFile("Dir::Bin::ischroot", "/usr/bin/ischroot");
+	    const char *const Args[] = {
+	       binary.c_str(),
+	       nullptr};
+	    execvp(Args[0], const_cast<char **>(Args));
+	    _exit(127);
+	 }
+
+	 res = ExecWait(child, "ischroot", true);
+      }
+   } once;
+
+   return once.res;
+}
+									/*}}}*/
 }
diff --git a/apt-pkg/aptconfiguration.h b/apt-pkg/aptconfiguration.h
index 2cb2d823a..bbeb156b9 100644
--- a/apt-pkg/aptconfiguration.h
+++ b/apt-pkg/aptconfiguration.h
@@ -122,7 +122,12 @@ namespace Configuration {							/*{{{*/
 	APT_PUBLIC std::vector<std::string> const getBuildProfiles();
 	/** \return Return a comma-separated list of enabled build profile specifications */
 	APT_PUBLIC std::string const getBuildProfilesString();
-									/*}}}*/
+
+	std::string const getMachineID();
+
+	/** \return Whether we are running in a chroot */
+	bool isChroot();
+	/*}}}*/
 }
 									/*}}}*/
 }
diff --git a/apt-pkg/cacheiterators.h b/apt-pkg/cacheiterators.h
index 1b049b6e5..6261b5089 100644
--- a/apt-pkg/cacheiterators.h
+++ b/apt-pkg/cacheiterators.h
@@ -242,6 +242,20 @@ class APT_PUBLIC pkgCache::VerIterator : public Iterator<Version, VerIterator> {
 	bool Automatic() const;
 	VerFileIterator NewestFile() const;
 
+#ifdef APT_COMPILING_APT
+	inline unsigned int PhasedUpdatePercentage() const
+	{
+	   return (static_cast<Version::Extra *>(Owner->Map.Data()) + S->d)->PhasedUpdatePercentage;
+	}
+	inline bool PhasedUpdatePercentage(unsigned int percentage)
+	{
+	   if (percentage > 100)
+	      return false;
+	   (static_cast<Version::Extra *>(Owner->Map.Data()) + S->d)->PhasedUpdatePercentage = static_cast<uint8_t>(percentage);
+	   return true;
+	}
+#endif
+
 	inline VerIterator(pkgCache &Owner,Version *Trg = 0) : Iterator<Version, VerIterator>(Owner, Trg) {
 		if (S == 0)
 			S = OwnerPointer();
diff --git a/apt-pkg/deb/deblistparser.cc b/apt-pkg/deb/deblistparser.cc
index 95f6f6fc8..b5c9c066e 100644
--- a/apt-pkg/deb/deblistparser.cc
+++ b/apt-pkg/deb/deblistparser.cc
@@ -338,6 +338,13 @@ bool debListParser::UsePackage(pkgCache::PkgIterator &Pkg,
    else if (std::find(forceImportant.begin(), forceImportant.end(), Pkg.Name()) != forceImportant.end())
       Pkg->Flags |= pkgCache::Flag::Important;
 
+   auto phased = Section.FindULL(pkgTagSection::Key::Phased_Update_Percentage, 100);
+   if (phased != 100)
+   {
+      if (not Ver.PhasedUpdatePercentage(phased))
+	 _error->Warning("Ignoring invalid Phased-Update-Percentage value");
+   }
+
    if (ParseStatus(Pkg,Ver) == false)
       return false;
    return true;
diff --git a/apt-pkg/pkgcache.h b/apt-pkg/pkgcache.h
index 6c6a4664e..55baa3cef 100644
--- a/apt-pkg/pkgcache.h
+++ b/apt-pkg/pkgcache.h
@@ -623,6 +623,8 @@ struct pkgCache::DescFile
     or handled as separate versions based on the Hash value. */
 struct pkgCache::Version
 {
+   struct Extra;
+
    /** \brief complete version string */
    map_stringitem_t VerStr;
    /** \brief section this version is filled in */
@@ -688,8 +690,16 @@ struct pkgCache::Version
    map_pointer<Version> NextInSource;
 
    /** \brief Private pointer */
-   map_pointer<void> d;
+   map_pointer<Extra> d;
 };
+
+#ifdef APT_COMPILING_APT
+/// \brief Extra information for packages. APT-internal use only.
+struct pkgCache::Version::Extra
+{
+   uint8_t PhasedUpdatePercentage;
+};
+#endif
 									/*}}}*/
 // Description structure						/*{{{*/
 /** \brief datamember of a linked list of available description for a version */
diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc
index d02c49f03..bd81ca0f5 100644
--- a/apt-pkg/pkgcachegen.cc
+++ b/apt-pkg/pkgcachegen.cc
@@ -873,6 +873,10 @@ map_pointer<pkgCache::Version> pkgCacheGenerator::NewVersion(pkgCache::VerIterat
    
    // Fill it in
    Ver = pkgCache::VerIterator(Cache,Cache.VerP + Version);
+   Ver->d = AllocateInMap<pkgCache::Version::Extra>();
+   if (not Ver.PhasedUpdatePercentage(100))
+      abort();
+
    //Dynamic<pkgCache::VerIterator> DynV(Ver); // caller MergeListVersion already takes care of it
    Ver->NextVer = Next;
    Ver->ParentPkg = ParentPkg;
diff --git a/apt-pkg/policy.cc b/apt-pkg/policy.cc
index 761a6ede1..bdb049ead 100644
--- a/apt-pkg/policy.cc
+++ b/apt-pkg/policy.cc
@@ -14,6 +14,7 @@
 // Include Files							/*{{{*/
 #include <config.h>
 
+#include <apt-pkg/aptconfiguration.h>
 #include <apt-pkg/cachefilter.h>
 #include <apt-pkg/configuration.h>
 #include <apt-pkg/error.h>
@@ -26,6 +27,7 @@
 #include <apt-pkg/versionmatch.h>
 
 #include <iostream>
+#include <random>
 #include <sstream>
 #include <string>
 #include <vector>
@@ -40,12 +42,17 @@ using namespace std;
 
 constexpr short NEVER_PIN = std::numeric_limits<short>::min();
 
+struct pkgPolicy::Private
+{
+   std::string machineID;
+};
+
 // Policy::Init - Startup and bind to a cache				/*{{{*/
 // ---------------------------------------------------------------------
 /* Set the defaults for operation. The default mode with no loaded policy
    file matches the V0 policy engine. */
 pkgPolicy::pkgPolicy(pkgCache *Owner) : VerPins(nullptr),
-   PFPriority(nullptr), Cache(Owner), d(NULL)
+					PFPriority(nullptr), Cache(Owner), d(new Private)
 {
    if (Owner == 0)
       return;
@@ -77,6 +84,8 @@ pkgPolicy::pkgPolicy(pkgCache *Owner) : VerPins(nullptr),
 	 CreatePin(pkgVersionMatch::Release,"",DefRel,990);
    }
    InitDefaults();
+
+   d->machineID = APT::Configuration::getMachineID();
 }
 									/*}}}*/
 // Policy::InitDefaults - Compute the default selections		/*{{{*/
@@ -274,8 +283,38 @@ void pkgPolicy::CreatePin(pkgVersionMatch::MatchType Type,string Name,
 // Policy::GetPriority - Get the priority of the package pin		/*{{{*/
 // ---------------------------------------------------------------------
 /* */
+// Returns true if this update is excluded by phasing.
+static inline bool ExcludePhased(std::string machineID, pkgCache::VerIterator const &Ver)
+{
+   // The order and fallbacks for the always/never checks come from update-manager and exist
+   // to preserve compatibility.
+   if (_config->FindB("APT::Get::Always-Include-Phased-Updates",
+		      _config->FindB("Update-Manager::Always-Include-Phased-Updates", false)))
+      return false;
+
+   if (_config->FindB("APT::Get::Never-Include-Phased-Updates",
+		      _config->FindB("Update-Manager::Never-Include-Phased-Updates", false)))
+      return true;
+
+   if (machineID.empty()			 // no machine-id
+       || getenv("SOURCE_DATE_EPOCH") != nullptr // reproducible build - always include
+       || APT::Configuration::isChroot())
+      return false;
+
+   std::string seedStr = std::string(Ver.SourcePkgName()) + "-" + Ver.VerStr() + "-" + machineID;
+   std::seed_seq seed(seedStr.begin(), seedStr.end());
+   std::minstd_rand rand(seed);
+   std::uniform_int_distribution<unsigned int> dist(0, 100);
+
+   return dist(rand) > Ver.PhasedUpdatePercentage();
+}
 APT_PURE signed short pkgPolicy::GetPriority(pkgCache::VerIterator const &Ver, bool ConsiderFiles)
 {
+   if (Ver.ParentPkg()->CurrentVer && Ver.PhasedUpdatePercentage() != 100)
+   {
+      if (ExcludePhased(d->machineID, Ver))
+	 return 1;
+   }
    if (VerPins[Ver->ID].Type != pkgVersionMatch::None)
    {
       // If all sources are never pins, the never pin wins.
@@ -454,4 +493,9 @@ bool ReadPinFile(pkgPolicy &Plcy,string File)
 }
 									/*}}}*/
 
-pkgPolicy::~pkgPolicy() {delete [] PFPriority; delete [] VerPins; }
+pkgPolicy::~pkgPolicy()
+{
+   delete[] PFPriority;
+   delete[] VerPins;
+   delete d;
+}
diff --git a/apt-pkg/policy.h b/apt-pkg/policy.h
index 7f30d40ed..589cebcde 100644
--- a/apt-pkg/policy.h
+++ b/apt-pkg/policy.h
@@ -83,7 +83,8 @@ class APT_PUBLIC pkgPolicy : public pkgDepCache::Policy
    explicit pkgPolicy(pkgCache *Owner);
    virtual ~pkgPolicy();
    private:
-   void * const d;
+   struct Private;
+   Private *const d;
 };
 
 APT_PUBLIC bool ReadPinFile(pkgPolicy &Plcy, std::string File = "");
diff --git a/apt-pkg/tagfile-keys.list b/apt-pkg/tagfile-keys.list
index a16bc686a..b5cc2f1a4 100644
--- a/apt-pkg/tagfile-keys.list
+++ b/apt-pkg/tagfile-keys.list
@@ -46,6 +46,7 @@ Package-List
 Package_Revision
 Package-Revision
 Package-Type
+Phased-Update-Percentage
 Pre-Depends
 Priority
 Protected