Merge branch 'fix/recursivemark' into 'main'

Fix infinite recursions in MarkPackage and improve recursions in general

See merge request apt-team/apt!183

11 files changed, 281 insertions, 129 deletions

diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml
index de517c11e..93a577ad2 100644
--- a/.gitlab-ci.yml
+++ b/.gitlab-ci.yml
@@ -17,7 +17,7 @@ test as root:
     - chmod -R o+rwX $PWD
     - ./prepare-release travis-ci
     - sudo -u travis mkdir -p build .ccache
-    - sudo -u travis env -C build cmake -DCMAKE_BUILD_TYPE=Release  -DCMAKE_C_COMPILER_LAUNCHER=ccache -DCMAKE_CXX_COMPILER_LAUNCHER=ccache -G Ninja ..
+    - sudo -u travis env -C build cmake -DCMAKE_BUILD_TYPE=RelWithDebInfo  -DCMAKE_C_COMPILER_LAUNCHER=ccache -DCMAKE_CXX_COMPILER_LAUNCHER=ccache -G Ninja ..
     - sudo -u travis --preserve-env=CCACHE_DIR,CCACHE_BASEDIR ninja -C build
     - CTEST_OUTPUT_ON_FAILURE=1 ninja -C build test
     - unbuffer ./test/integration/run-tests -q -j 4
@@ -34,7 +34,7 @@ test as user:
     - chmod -R o+rwX $PWD
     - ./prepare-release travis-ci
     - sudo -u travis mkdir -p build .ccache
-    - sudo -u travis env -C build cmake -DCMAKE_BUILD_TYPE=Release -DCMAKE_C_COMPILER_LAUNCHER=ccache -DCMAKE_CXX_COMPILER_LAUNCHER=ccache -G Ninja ..
+    - sudo -u travis env -C build cmake -DCMAKE_BUILD_TYPE=RelWithDebInfo -DCMAKE_C_COMPILER_LAUNCHER=ccache -DCMAKE_CXX_COMPILER_LAUNCHER=ccache -G Ninja ..
     - sudo -u travis --preserve-env=CCACHE_DIR,CCACHE_BASEDIR ninja -C build
     - sudo -u travis CTEST_OUTPUT_ON_FAILURE=1 ninja -C build test
     - sudo -u travis unbuffer ./test/integration/run-tests -q -j 4
diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index 2c3c6d01d..460fb296e 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -125,7 +125,6 @@ int pkgDepCache::DecreaseActionGroupLevel()
 struct pkgDepCache::Private
 {
    std::unique_ptr<InRootSetFunc> inRootSetFunc;
-   std::vector<bool> fullyExplored;
    std::unique_ptr<APT::CacheFilter::Matcher> IsAVersionedKernelPackage, IsProtectedKernelPackage;
 };
 pkgDepCache::pkgDepCache(pkgCache *const pCache, Policy *const Plcy) : group_level(0), Cache(pCache), PkgState(0), DepState(0),
@@ -895,8 +894,8 @@ static char const* PrintMode(char const mode)
 static bool IsModeChangeOk(pkgDepCache &Cache, pkgDepCache::ModeList const mode, pkgCache::PkgIterator const &Pkg,
 			   unsigned long const Depth, bool const FromUser, bool const DebugMarker)
 {
-   // we are not trying to hard…
-   if (unlikely(Depth > 100))
+   // we are not trying too hard…
+   if (unlikely(Depth > 3000))
       return false;
 
    // general sanity
@@ -2201,18 +2200,17 @@ pkgDepCache::InRootSetFunc *pkgDepCache::GetCachedRootSetFunc()
    return d->inRootSetFunc.get();
 }
 									/*}}}*/
-bool pkgDepCache::MarkFollowsRecommends()
+bool pkgDepCache::MarkFollowsRecommends()				/*{{{*/
 {
   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
 }
-
-bool pkgDepCache::MarkFollowsSuggests()
+									/*}}}*/
+bool pkgDepCache::MarkFollowsSuggests()					/*{{{*/
 {
   return _config->FindB("APT::AutoRemove::SuggestsImportant", true);
 }
-
-// pkgDepCache::MarkRequired - the main mark algorithm			/*{{{*/
-static bool IsPkgInBoringState(pkgCache::PkgIterator const &Pkg, pkgDepCache::StateCache const * const PkgState)
+									/*}}}*/
+static bool IsPkgInBoringState(pkgCache::PkgIterator const &Pkg, pkgDepCache::StateCache const * const PkgState)/*{{{*/
 {
    if (Pkg->CurrentVer == 0)
    {
@@ -2226,81 +2224,36 @@ static bool IsPkgInBoringState(pkgCache::PkgIterator const &Pkg, pkgDepCache::St
    }
    return false;
 }
-bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
-{
-   if (_config->Find("APT::Solver", "internal") != "internal")
-      return true;
-
-   bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
-
-   // init the states
-   auto const PackagesCount = Head().PackageCount;
-   for(auto i = decltype(PackagesCount){0}; i < PackagesCount; ++i)
-   {
-      PkgState[i].Marked  = false;
-      PkgState[i].Garbage = false;
-   }
-   d->fullyExplored = std::vector<bool>(PackagesCount, false);
-   if (debug_autoremove)
-      for(PkgIterator p = PkgBegin(); !p.end(); ++p)
-	 if(PkgState[p->ID].Flags & Flag::Auto)
-	    std::clog << "AutoDep: " << p.FullName() << std::endl;
-
-   bool const follow_recommends = MarkFollowsRecommends();
-   bool const follow_suggests   = MarkFollowsSuggests();
-
-   // do the mark part, this is the core bit of the algorithm
-   for (PkgIterator P = PkgBegin(); !P.end(); ++P)
-   {
-      if (PkgState[P->ID].Marked || IsPkgInBoringState(P, PkgState))
-	 continue;
-
-      const char *reason = nullptr;
-
-      if ((PkgState[P->ID].Flags & Flag::Auto) == 0)
-	 reason = "Manual-Installed";
-      else if (P->Flags & Flag::Essential)
-	 reason = "Essential";
-      else if (P->Flags & Flag::Important)
-	 reason = "Important";
-      else if (P->CurrentVer != 0 && P.CurrentVer()->Priority == pkgCache::State::Required)
-	 reason = "Required";
-      else if (userFunc.InRootSet(P))
-	 reason = "Blacklisted [APT::NeverAutoRemove]";
-      else if (not IsModeChangeOk(*this, ModeGarbage, P, 0, false, DebugMarker))
-	 reason = "Hold";
-      else
-	 continue;
-
-      if (PkgState[P->ID].Install())
-	 MarkPackage(P, PkgState[P->ID].InstVerIter(*this),
-	       follow_recommends, follow_suggests, reason);
-      else
-	 MarkPackage(P, P.CurrentVer(),
-	       follow_recommends, follow_suggests, reason);
-   }
-   d->fullyExplored.clear();
-   return true;
-}
 									/*}}}*/
 // MarkPackage - mark a single package in Mark-and-Sweep		/*{{{*/
-void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &Pkg,
-			      const pkgCache::VerIterator &Ver,
-			      bool const &follow_recommends,
-			      bool const &follow_suggests,
-			      const char *reason)
+static bool MarkPackage(pkgCache::PkgIterator const &Pkg,
+			pkgCache::VerIterator const &Ver,
+			bool const follow_recommends,
+			bool const follow_suggests,
+			bool const debug_autoremove,
+			std::string_view const reason,
+			size_t const Depth,
+			pkgCache &Cache,
+			pkgDepCache &DepCache,
+			pkgDepCache::StateCache *const PkgState,
+			std::vector<bool> &fullyExplored,
+			std::unique_ptr<APT::CacheFilter::Matcher> &IsAVersionedKernelPackage,
+			std::unique_ptr<APT::CacheFilter::Matcher> &IsProtectedKernelPackage)
 {
-   if (Ver.end() || (d->fullyExplored[Pkg->ID] && PkgState[Pkg->ID].Marked))
-      return;
+   if (Ver.end() || PkgState[Pkg->ID].Marked)
+      return true;
 
    if (IsPkgInBoringState(Pkg, PkgState))
    {
-      d->fullyExplored[Pkg->ID] = true;
-      return;
+      fullyExplored[Pkg->ID] = true;
+      return true;
    }
 
+   // we are not trying too hard…
+   if (unlikely(Depth > 3000))
+      return false;
+
    PkgState[Pkg->ID].Marked = true;
-   bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
    if(debug_autoremove)
       std::clog << "Marking: " << Pkg.FullName() << " " << Ver.VerStr()
 		<< " (" << reason << ")" << std::endl;
@@ -2308,20 +2261,20 @@ void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &Pkg,
    auto const sort_by_source_version = [](pkgCache::VerIterator const &A, pkgCache::VerIterator const &B) {
       auto const verret = A.Cache()->VS->CmpVersion(A.SourceVerStr(), B.SourceVerStr());
       if (verret != 0)
-	 return verret > 0;
+	 return verret < 0;
       return A->ID < B->ID;
    };
 
    for (auto D = Ver.DependsList(); not D.end(); ++D)
    {
       auto const T = D.TargetPkg();
-      if (T.end() || d->fullyExplored[T->ID])
+      if (T.end() || fullyExplored[T->ID])
 	 continue;
 
-      if (D->Type != Dep::Depends &&
-	    D->Type != Dep::PreDepends &&
-	    (follow_recommends == false || D->Type != Dep::Recommends) &&
-	    (follow_suggests == false || D->Type != Dep::Suggests))
+      if (D->Type != pkgCache::Dep::Depends &&
+	    D->Type != pkgCache::Dep::PreDepends &&
+	    (not follow_recommends || D->Type != pkgCache::Dep::Recommends) &&
+	    (not follow_suggests || D->Type != pkgCache::Dep::Suggests))
 	 continue;
 
       bool unsatisfied_choice = false;
@@ -2329,7 +2282,7 @@ void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &Pkg,
       // collect real part
       if (not IsPkgInBoringState(T, PkgState))
       {
-	 auto const TV = (PkgState[T->ID].Install()) ? PkgState[T->ID].InstVerIter(*this) : T.CurrentVer();
+	 auto const TV = (PkgState[T->ID].Install()) ? PkgState[T->ID].InstVerIter(DepCache) : T.CurrentVer();
 	 if (likely(not TV.end()))
 	 {
 	    if (not D.IsSatisfied(TV))
@@ -2349,7 +2302,7 @@ void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &Pkg,
 
 	 // we want to ignore provides from uninteresting versions
 	 auto const PV = (PkgState[PP->ID].Install()) ?
-	    PkgState[PP->ID].InstVerIter(*this) : PP.CurrentVer();
+	    PkgState[PP->ID].InstVerIter(DepCache) : PP.CurrentVer();
 	 if (unlikely(PV.end()) || PV != Prv.OwnerVer())
 	    continue;
 
@@ -2361,16 +2314,13 @@ void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &Pkg,
       // only latest binary package of a source package is marked instead of all
       for (auto &providers : providers_by_source)
       {
-	 std::sort(providers.second.begin(), providers.second.end(), sort_by_source_version);
-	 auto const highestSrcVer = (*providers.second.begin()).SourceVerStr();
-	 auto notThisVer = std::find_if_not(providers.second.begin(), providers.second.end(), [&](auto const &V) { return strcmp(highestSrcVer, V.SourceVerStr()) == 0; });
-	 if (notThisVer != providers.second.end())
-	    providers.second.erase(notThisVer, providers.second.end());
+	 auto const highestSrcVer = (*std::max_element(providers.second.begin(), providers.second.end(), sort_by_source_version)).SourceVerStr();
+	 providers.second.erase(std::remove_if(providers.second.begin(), providers.second.end(), [&](auto const &V) { return strcmp(highestSrcVer, V.SourceVerStr()) != 0; }), providers.second.end());
 	 // if the provider is a versioned kernel package mark them only for protected kernels
 	 if (providers.second.size() == 1)
 	    continue;
-	 if (not d->IsAVersionedKernelPackage)
-	    d->IsAVersionedKernelPackage = [&]() -> std::unique_ptr<APT::CacheFilter::Matcher> {
+	 if (not IsAVersionedKernelPackage)
+	    IsAVersionedKernelPackage = [&]() -> std::unique_ptr<APT::CacheFilter::Matcher> {
 	       auto const patterns = _config->FindVector("APT::VersionedKernelPackages");
 	       if (patterns.empty())
 		  return std::make_unique<APT::CacheFilter::FalseMatcher>();
@@ -2380,33 +2330,92 @@ void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &Pkg,
 	       regex << patterns.back() << "-.*$";
 	       return std::make_unique<APT::CacheFilter::PackageNameMatchesRegEx>(regex.str());
 	    }();
-	 if (not std::all_of(providers.second.begin(), providers.second.end(), [&](auto const &Prv) { return (*d->IsAVersionedKernelPackage)(Prv.ParentPkg()); }))
+	 if (not std::all_of(providers.second.begin(), providers.second.end(), [&](auto const &Prv) { return (*IsAVersionedKernelPackage)(Prv.ParentPkg()); }))
 	    continue;
 	 // … if there is at least one for protected kernels installed
-	 if (not d->IsProtectedKernelPackage)
-	    d->IsProtectedKernelPackage = APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(Cache);
-	 if (not std::any_of(providers.second.begin(), providers.second.end(), [&](auto const &Prv) { return (*d->IsProtectedKernelPackage)(Prv.ParentPkg()); }))
+	 if (not IsProtectedKernelPackage)
+	    IsProtectedKernelPackage = APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(&Cache);
+	 if (not std::any_of(providers.second.begin(), providers.second.end(), [&](auto const &Prv) { return (*IsProtectedKernelPackage)(Prv.ParentPkg()); }))
 	    continue;
 	 providers.second.erase(std::remove_if(providers.second.begin(), providers.second.end(),
-					       [&](auto const &Prv) { return not((*d->IsProtectedKernelPackage)(Prv.ParentPkg())); }),
+					       [&](auto const &Prv) { return not((*IsProtectedKernelPackage)(Prv.ParentPkg())); }),
 				providers.second.end());
       }
 
       if (not unsatisfied_choice)
-	 d->fullyExplored[T->ID] = true;
+	 fullyExplored[T->ID] = true;
       for (auto const &providers : providers_by_source)
       {
 	 for (auto const &PV : providers.second)
 	 {
 	    auto const PP = PV.ParentPkg();
 	    if (debug_autoremove)
-	       std::clog << "Following dep: " << APT::PrettyDep(this, D)
+	       std::clog << "Following dep: " << APT::PrettyDep(&DepCache, D)
 			 << ", provided by " << PP.FullName() << " " << PV.VerStr()
 			 << " (" << providers_by_source.size() << "/" << providers.second.size() << ")\n";
-	    MarkPackage(PP, PV, follow_recommends, follow_suggests, "Dependency");
+	    if (not MarkPackage(PP, PV, follow_recommends, follow_suggests, debug_autoremove,
+				"Dependency", Depth + 1, Cache, DepCache, PkgState, fullyExplored,
+				IsAVersionedKernelPackage, IsProtectedKernelPackage))
+	       return false;
 	 }
       }
    }
+   return true;
+}
+									/*}}}*/
+// pkgDepCache::MarkRequired - the main mark algorithm			/*{{{*/
+bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
+{
+   if (_config->Find("APT::Solver", "internal") != "internal")
+      return true;
+
+   // init the states
+   auto const PackagesCount = Head().PackageCount;
+   for(auto i = decltype(PackagesCount){0}; i < PackagesCount; ++i)
+   {
+      PkgState[i].Marked  = false;
+      PkgState[i].Garbage = false;
+   }
+   std::vector<bool> fullyExplored(PackagesCount, false);
+
+   bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
+   if (debug_autoremove)
+      for(PkgIterator p = PkgBegin(); !p.end(); ++p)
+	 if(PkgState[p->ID].Flags & Flag::Auto)
+	    std::clog << "AutoDep: " << p.FullName() << std::endl;
+
+   bool const follow_recommends = MarkFollowsRecommends();
+   bool const follow_suggests   = MarkFollowsSuggests();
+
+   // do the mark part, this is the core bit of the algorithm
+   for (PkgIterator P = PkgBegin(); !P.end(); ++P)
+   {
+      if (PkgState[P->ID].Marked || IsPkgInBoringState(P, PkgState))
+	 continue;
+
+      std::string_view reason;
+      if ((PkgState[P->ID].Flags & Flag::Auto) == 0)
+	 reason = "Manual-Installed";
+      else if (P->Flags & Flag::Essential)
+	 reason = "Essential";
+      else if (P->Flags & Flag::Important)
+	 reason = "Important";
+      else if (P->CurrentVer != 0 && P.CurrentVer()->Priority == pkgCache::State::Required)
+	 reason = "Required";
+      else if (userFunc.InRootSet(P))
+	 reason = "Blacklisted [APT::NeverAutoRemove]";
+      else if (not IsModeChangeOk(*this, ModeGarbage, P, 0, false, DebugMarker))
+	 reason = "Hold";
+      else
+	 continue;
+
+      pkgCache::VerIterator const PV = (PkgState[P->ID].Install()) ? PkgState[P->ID].InstVerIter(*this) : P.CurrentVer();
+      if (not MarkPackage(P, PV, follow_recommends, follow_suggests, debug_autoremove,
+			  reason, 0, *Cache, *this, PkgState, fullyExplored,
+			  d->IsAVersionedKernelPackage, d->IsProtectedKernelPackage))
+	 return false;
+   }
+   return true;
 }
 									/*}}}*/
 bool pkgDepCache::Sweep()						/*{{{*/
diff --git a/apt-pkg/depcache.h b/apt-pkg/depcache.h
index e0c5c4069..be27b1d77 100644
--- a/apt-pkg/depcache.h
+++ b/apt-pkg/depcache.h
@@ -71,31 +71,6 @@ class APT_PUBLIC pkgDepCache : protected pkgCache::Namespace
    };
 
    private:
-   /** \brief Mark a single package and all its unmarked important
-    *  dependencies during mark-and-sweep.
-    *
-    *  Recursively invokes itself to mark all dependencies of the
-    *  package.
-    *
-    *  \param pkg The package to mark.
-    *
-    *  \param ver The version of the package that is to be marked.
-    *
-    *  \param follow_recommends If \b true, recommendations of the
-    *  package will be recursively marked.
-    *
-    *  \param follow_suggests If \b true, suggestions of the package
-    *  will be recursively marked.
-    *
-    *  \param reason The reason why the package is being marked.
-    *  (Used in logging when Debug::pkgAutoRemove is set.)
-    */
-   APT_HIDDEN void MarkPackage(const pkgCache::PkgIterator &pkg,
-		    const pkgCache::VerIterator &ver,
-		    bool const &follow_recommends,
-		    bool const &follow_suggests,
-		    const char *reason);
-
    /** \brief Update the Marked field of all packages.
     *
     *  Each package's StateCache::Marked field will be set to \b true
diff --git a/apt-private/private-show.cc b/apt-private/private-show.cc
index 30b99b013..07b5a3ae3 100644
--- a/apt-private/private-show.cc
+++ b/apt-private/private-show.cc
@@ -300,6 +300,7 @@ static bool DisplayRecordV2(pkgCacheFile &CacheFile, pkgRecords &Recs, /*{{{*/
 bool ShowPackage(CommandLine &CmdL)					/*{{{*/
 {
    pkgCacheFile CacheFile;
+   CacheFile.InhibitActionGroups(true);
    auto VolatileCmdL = GetAllPackagesAsPseudo(CacheFile.GetSourceList(), CmdL, AddVolatileBinaryFile, "");
 
    if (unlikely(CacheFile.GetPkgCache() == nullptr))
diff --git a/cmdline/apt-mark.cc b/cmdline/apt-mark.cc
index 92efa0c81..3dd5ce784 100644
--- a/cmdline/apt-mark.cc
+++ b/cmdline/apt-mark.cc
@@ -47,6 +47,7 @@ using namespace std;
 static bool DoAuto(CommandLine &CmdL)
 {
    pkgCacheFile CacheFile;
+   CacheFile.InhibitActionGroups(true);
    pkgDepCache * const DepCache = CacheFile.GetDepCache();
    if (unlikely(DepCache == nullptr))
       return false;
@@ -105,6 +106,7 @@ static bool DoAuto(CommandLine &CmdL)
 static bool DoMarkAuto(CommandLine &CmdL)
 {
    pkgCacheFile CacheFile;
+   CacheFile.InhibitActionGroups(true);
    pkgDepCache * const DepCache = CacheFile.GetDepCache();
    if (unlikely(DepCache == nullptr))
       return false;
@@ -262,6 +264,7 @@ static bool DoMinimize(CommandLine &CmdL)
 static bool ShowAuto(CommandLine &CmdL)
 {
    pkgCacheFile CacheFile;
+   CacheFile.InhibitActionGroups(true);
    pkgDepCache * const DepCache = CacheFile.GetDepCache();
    if (unlikely(DepCache == nullptr))
       return false;
@@ -301,6 +304,7 @@ static bool ShowAuto(CommandLine &CmdL)
 static bool DoSelection(CommandLine &CmdL)
 {
    pkgCacheFile CacheFile;
+   CacheFile.InhibitActionGroups(true);
    pkgCache * const Cache = CacheFile.GetPkgCache();
    if (unlikely(Cache == nullptr))
       return false;
diff --git a/debian/tests/control b/debian/tests/control
index a69965db4..446f0afcc 100644
--- a/debian/tests/control
+++ b/debian/tests/control
@@ -7,4 +7,4 @@ Depends: @, @builddeps@, dpkg (>= 1.20.8), fakeroot, wget, stunnel4, lsof, db-ut
          gpgv1 | gpgv (<< 2),
          libfile-fcntllock-perl, python3-apt, aptitude,
          pkg-config,
-         valgrind
+         valgrind, gdb-minimal | gdb
diff --git a/debian/tests/run-tests b/debian/tests/run-tests
index 495f7edff..ff3359fae 100644
--- a/debian/tests/run-tests
+++ b/debian/tests/run-tests
@@ -22,4 +22,5 @@ APT_INTEGRATION_TESTS_INTERNAL_PLANNER=/usr/lib/apt/planners/apt \
 APT_INTEGRATION_TESTS_BUILD_DIR=/usr/bin \
 APT_INTEGRATION_TESTS_FTPARCHIVE_BIN_DIR=/usr/bin \
 APT_INTEGRATION_TESTS_LIBRARY_PATH=/dev/null/does/not/exist \
+APT_INTEGRATION_TESTS_ARTIFACTS_DIR="${AUTOPKGTEST_ARTIFACTS}" \
 ./test/integration/run-tests -q
diff --git a/test/integration/framework b/test/integration/framework
index 8c9abfbe4..1f942d162 100644
--- a/test/integration/framework
+++ b/test/integration/framework
@@ -307,6 +307,13 @@ find_project_binary_dir() {
 		export PROJECT_BINARY_DIR
 	fi
 }
+_removetmpworkingdirectory() {
+	cd /
+	if [ -n "$TMPWORKINGDIRECTORY" -a -d "$TMPWORKINGDIRECTORY" ]; then
+		rm -rf "$TMPWORKINGDIRECTORY"
+	fi
+	TMPWORKINGDIRECTORY=''
+}
 setupenvironment() {
 	# Next check needs a gnu stat, let's figure that out early.
 	stat=stat
@@ -317,8 +324,10 @@ setupenvironment() {
 	if [ -n "$TMPDIR" ] && [ "$(id -u)" = '0' ] && [ "$($stat --format '%a' "$TMPDIR")" != '1777' ]; then
 		unset TMPDIR
 	fi
-	TMPWORKINGDIRECTORY="$(mktemp -d)"
-	addtrap "cd /; rm -rf '$(escape_shell "$TMPWORKINGDIRECTORY")';"
+	if [ -z "$TMPWORKINGDIRECTORY" ]; then
+		addtrap '_removetmpworkingdirectory;'
+		TMPWORKINGDIRECTORY="$(mktemp -d)"
+	fi
 	if [ -n "$TMPDIR_ADD" ]; then
 		TMPWORKINGDIRECTORY="${TMPWORKINGDIRECTORY}/${TMPDIR_ADD}"
 		mkdir -p "$TMPWORKINGDIRECTORY"
@@ -361,6 +370,7 @@ setupenvironment() {
         APTINTERNALSOLVER="${APT_INTEGRATION_TESTS_INTERNAL_SOLVER:-"${BUILDDIRECTORY}/solvers/apt"}"
 	APTDUMPSOLVER="${APT_INTEGRATION_TESTS_DUMP_SOLVER:-"${BUILDDIRECTORY}/solvers/dump"}"
 	APTINTERNALPLANNER="${APT_INTEGRATION_TESTS_INTERNAL_PLANNER:-"${BUILDDIRECTORY}/planners/apt"}"
+	ARTIFACTSDIR="${APT_INTEGRATION_TESTS_ARTIFACTS_DIR:-"${BUILDDIRECTORY}/artifacts"}"
 	test -x "${BUILDDIRECTORY}/apt-get" || msgdie "You need to build tree first"
         # -----
 
@@ -1778,6 +1788,52 @@ msgfailoutput() {
 		ls -l
 	fi
 	catfile "$OUTPUT"
+	if [ "$CMD" != 'echo' ] && tail -n 1 "$OUTPUT" | grep -q '(core dumped)$'; then
+		local COREDUMP="${TMPWORKINGDIRECTORY}/rootdir/tmp/core.dump"
+		local COREEXE=''
+		for CORENAME in 'core' 'core.pid'; do
+			if [ -s "$CORENAME" ]; then
+				cp -a ${CORENAME} "$COREDUMP"
+			elif [ -s "${TMPWORKINGDIRECTORY}/${CORENAME}" ]; then
+				cp -a "${TMPWORKINGDIRECTORY}/${CORENAME}" "$COREDUMP"
+			else
+				continue
+			fi
+			break
+		done
+		if [ -s "$COREDUMP" ]; then
+			true # found already as a file
+		elif dpkg-checkbuilddeps -d 'systemd-coredump' /dev/null >/dev/null 2>&1; then
+			COREEXE="$(coredumpctl -1 --no-legend list | sed -e 's#^.* \([^ ]\+\)$#\1#')"
+			coredumpctl -1 dump "$COREEXE" -o "$COREDUMP" 2>/dev/null >&2 || true
+		else
+			echo '### core dump not found ###'
+			cat /proc/sys/kernel/core_pattern
+		fi
+		if [ -s "$COREDUMP" ]; then
+			if [ -z "$COREEXE" ]; then
+				case "$CMD" in
+				apt) COREEXE="${BUILDDIRECTORY}/${CMD}";;
+				aptftparchive) COREEXE="${APTFTPARCHIVEBINDIR}/apt-ftparchive";;
+				apthelper) COREEXE="${APTHELPERBINDIR}/apt-helper";;
+				aptwebserver) COREEXE="${APTTESTHELPERSBINDIR}/aptwebserver";;
+				apt*) COREEXE="${BUILDDIRECTORY}/apt-${CMD##*apt}";;
+				*) COREEXE="${BUILDDIRECTORY}/${CMD}";;
+				esac
+			fi
+
+			if [ -d "${ARTIFACTSDIR}" ]; then
+				local ARTIFACT_COREDUMP="$(mktemp --suffix=.coredump -p "${ARTIFACTSDIR}" "${COREEXE##*/}-XXXXXX")"
+				cp -a "$COREDUMP" "$ARTIFACT_COREDUMP"
+				echo "#### coredump in $ARTIFACT_COREDUMP for $COREEXE ####"
+			fi
+			if [ -n "$COREEXE" -a -s "$COREEXE" ] && dpkg-checkbuilddeps -d 'gdb' /dev/null >/dev/null 2>&1; then
+				echo "#### gdb backtrace ####"
+				command gdb --batch -n -ex 'set pagination off' --ex 'thread apply all bt full' "$COREEXE" "$COREDUMP" || true
+			fi
+		fi
+		rm -f "$COREDUMP"
+	fi
 	msgfail "$MSG"
 }
 
@@ -1801,6 +1857,9 @@ testsuccesswithglobalerror() {
 					if echo 'E: Can not write log (Is /dev/pts mounted?) - posix_openpt (2: No such file or directory)' \
 						| cmp - "${TMPWORKINGDIRECTORY}/rootdir/tmp/checkforwarnings.output" >/dev/null 2>&1; then
 						msgpass
+					elif echo 'E: Can not write log (Is /dev/pts mounted?) - posix_openpt (13: Permission denied)' \
+						| cmp - "${TMPWORKINGDIRECTORY}/rootdir/tmp/checkforwarnings.output" >/dev/null 2>&1; then
+						msgpass
 					else
 						msgfailoutput 'successful run, but output contains warnings/errors' "$OUTPUT" "$@"
 					fi
diff --git a/test/integration/test-bug-992993-marked-cycles b/test/integration/test-bug-992993-marked-cycles
new file mode 100755
index 000000000..a569040cf
--- /dev/null
+++ b/test/integration/test-bug-992993-marked-cycles
@@ -0,0 +1,30 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertinstalledpackage 'librust-nom-4-dev' 'all' '4.2.3-3' 'Provides: librust-nom-dev (= 4.2.3-3)'
+insertinstalledpackage 'librust-nom-dev' 'all' '5.0.1-4' 'Depends: librust-nom+default-dev (= 5.0.1-4)'
+insertinstalledpackage 'librust-nom+default-dev ' 'all' '5.0.1-4' 'Depends: librust-nom-dev (= 5.0.1-4)'
+insertinstalledpackage 'librust-nom-4+std-dev' 'all' '4.2.3-3' 'Provides: librust-nom+default-dev (= 4.2.3-3)'
+
+insertinstalledpackage 'foo' 'all' '1' 'Depends: librust-nom-4-dev, librust-nom-dev, librust-nom-4+std-dev'
+
+for AUTO in '' 'librust-nom-4-dev' 'librust*' 'foo' '.*'; do
+	msgmsg 'Running test with these packages marked auto:' "$AUTO"
+	testsuccess aptmark manual '.*'
+	if [ -n "$AUTO" ]; then
+		testsuccess aptmark auto "$AUTO"
+	fi
+
+	testsuccess aptget check
+	testsuccess aptget autoremove -s
+
+	testsuccess aptget upgrade
+	testsuccess aptget full-upgrade
+
+	testsuccess apt show foo
+done
diff --git a/test/interactive-helper/CMakeLists.txt b/test/interactive-helper/CMakeLists.txt
index 565474afd..fff47300b 100644
--- a/test/interactive-helper/CMakeLists.txt
+++ b/test/interactive-helper/CMakeLists.txt
@@ -11,7 +11,8 @@ target_link_libraries(aptdropprivs apt-pkg)
 add_executable(test_fileutl test_fileutl.cc)
 target_link_libraries(test_fileutl apt-pkg)
 add_executable(createdeb-cve-2020-27350 createdeb-cve-2020-27350.cc)
-
+add_executable(longest-dependency-chain longest-dependency-chain.cc)
+target_link_libraries(longest-dependency-chain apt-pkg apt-private)
 
 add_library(noprofile SHARED libnoprofile.c)
 target_link_libraries(noprofile ${CMAKE_DL_LIBS})
diff --git a/test/interactive-helper/longest-dependency-chain.cc b/test/interactive-helper/longest-dependency-chain.cc
new file mode 100644
index 000000000..3da722a5b
--- /dev/null
+++ b/test/interactive-helper/longest-dependency-chain.cc
@@ -0,0 +1,72 @@
+#include <config.h>
+
+#include <apt-pkg/cachefile.h>
+#include <apt-pkg/pkgsystem.h>
+#include <apt-private/private-cmndline.h>
+
+#include <iostream>
+
+static bool ShowHelp(CommandLine &)					/*{{{*/
+{
+   std::cout <<
+    "Usage: longest-dependecy-chain [options]\n"
+      "\n"
+      "Tries to find the longest dependency chain available in the data\n"
+      "assuming an empty status file, no conflicts, all or-group members\n"
+      "are followed and discovery order matters. In other words:\n"
+      "The found length might very well be too short and not realistic.\n"
+      "It is also not implemented very intelligently, so it runs forever.\n";
+   return true;
+}
+									/*}}}*/
+static std::vector<aptDispatchWithHelp> GetCommands()			/*{{{*/
+{
+   return {
+      {nullptr, nullptr, nullptr}
+   };
+}
+									/*}}}*/
+static size_t findLongestInstallChain(pkgDepCache &Cache, pkgCache::PkgIterator const &Pkg, std::vector<bool> &installed)/*{{{*/
+{
+   if (installed[Pkg->ID])
+      return 0;
+   installed[Pkg->ID] = true;
+
+   auto const Ver = Cache.GetCandidateVersion(Pkg);
+   if (Ver.end())
+      return 0;
+
+   size_t maxdepth = 0;
+   for (auto D = Ver.DependsList(); not D.end(); ++D)
+      if (D->Type == pkgCache::Dep::Depends ||
+	    D->Type == pkgCache::Dep::PreDepends ||
+	    D->Type == pkgCache::Dep::Recommends ||
+	    D->Type == pkgCache::Dep::Suggests)
+	 maxdepth = std::max(maxdepth, findLongestInstallChain(Cache, D.TargetPkg(), installed));
+   return maxdepth + 1;
+}
+									/*}}}*/
+int main(int argc,const char *argv[])					/*{{{*/
+{
+   CommandLine CmdL;
+   auto const Cmds = ParseCommandLine(CmdL, APT_CMD::APT_SORTPKG, &_config, &_system, argc, argv, &ShowHelp, &GetCommands);
+   _config->Set("dir::state::status", "/dev/null");
+
+   pkgCacheFile CacheFile;
+   CacheFile.InhibitActionGroups(true);
+   pkgDepCache * const Cache = CacheFile.GetDepCache();
+   if (unlikely(Cache == nullptr))
+      return DispatchCommandLine(CmdL, Cmds);
+
+   size_t maxdepth = 0;
+   for (auto P = Cache->PkgBegin(); not P.end(); ++P)
+   {
+      std::vector<bool> installed(Cache->Head().PackageCount, false);
+      auto const depth = findLongestInstallChain(*Cache, P, installed);
+      std::cout << depth << ' ' << P.FullName() << '\n';
+      maxdepth = std::max(maxdepth, depth);
+   }
+
+   return 0;
+}
+									/*}}}*/