From 0a57c0f0e4d0bc3474ce4d2101f36a997891d30d Mon Sep 17 00:00:00 2001 From: Michael Vogt Date: Wed, 29 Jun 2005 06:11:36 +0000 Subject: * use mark-and-sweep from aptitude now as GC algorithm --- apt-pkg/algorithms.cc | 245 +++++++++++++++++++++++++++++++++----------------- apt-pkg/depcache.cc | 43 ++++----- apt-pkg/depcache.h | 16 ++-- apt-pkg/pkgcache.h | 1 - cmdline/apt-get.cc | 5 +- debian/changelog | 7 +- 6 files changed, 197 insertions(+), 120 deletions(-) diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc index 5167d11eb..bed90f5d0 100644 --- a/apt-pkg/algorithms.cc +++ b/apt-pkg/algorithms.cc @@ -20,7 +20,10 @@ #include #include #include +#include +#include #include + #include @@ -1248,106 +1251,186 @@ void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List) /*}}}*/ -// pkgMarkPkgUsed - Mark used packages as dirty /*{{{*/ -// --------------------------------------------------------------------- -/* Mark all reachable packages as dirty. */ -void pkgMarkPkgUsed(pkgDepCache &Cache, pkgCache::PkgIterator Pkg, - pkgCache::State::PkgRemoveState DirtLevel) +// mark a single package in Mark-and-Sweep +void pkgMarkPackage(pkgDepCache &Cache, + const pkgCache::PkgIterator &pkg, + const pkgCache::VerIterator &ver, + bool follow_recommends, + bool follow_suggests) { - // If it is not installed, and we are in manual mode, ignore it - if ((Pkg->CurrentVer == 0 && Cache[Pkg].Install() == false || Cache[Pkg].Delete() == true) && - DirtLevel == pkgCache::State::RemoveManual) + pkgDepCache::StateCache &state=Cache[pkg]; + pkgCache::VerIterator candver=state.CandidateVerIter(Cache); + pkgCache::VerIterator instver=state.InstVerIter(Cache); + +#if 0 + // If a package was garbage-collected but is now being marked, we + // should re-select it + // For cases when a pkg is set to upgrade and this trigger the + // removal of a no-longer used dependency. if the pkg is set to + // keep again later it will result in broken deps + if(state.Delete() && state.RemoveReason=pkgDepCache::Unused) { -// fprintf(stdout,"This one is not installed/virtual %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel); - return; + if(ver==candver) + mark_install(pkg, false, false, NULL); + else if(ver==pkg.CurrentVer()) + MarkKeep(pkg); + + instver=state.InstVerIter(*this); } +#endif - // If it is not installed, and it is not virtual, ignore it - if ((Pkg->CurrentVer == 0 && Cache[Pkg].Install() == false || Cache[Pkg].Delete() == true) && - Pkg->VersionList != 0) - { -// fprintf(stdout,"This one is not installed %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel); + // Ignore versions other than the InstVer, and ignore packages + // that are already going to be removed or just left uninstalled. + if(!(ver==instver && !instver.end())) return; - } - // If it is similar or more dirty than we are ;-), because we've been here already, don't mark it - // This is necessary because virtual packages just relay the current level, - // so it may be possible e.g. that this was already seen with ::RemoveSuggested, but - // we are ::RemoveRequired - if (Cache[Pkg].Dirty() >= DirtLevel) - { - //fprintf(stdout,"Seen already %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel); + // if we are marked already we are done + if(state.Marked) return; - } - - // If it is less important than the current DirtLevel, don't mark it - if (Cache[Pkg].AutomaticRemove != pkgCache::State::RemoveManual && - Cache[Pkg].AutomaticRemove > DirtLevel) + + //std::cout << "Setting Marked for: " << pkg.Name() << std::endl; + state.Marked=true; + + if(!ver.end()) { -// fprintf(stdout,"We don't need %s %d %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel, Cache[Pkg].Dirty()); - return; + for(pkgCache::DepIterator d=ver.DependsList(); !d.end(); ++d) + { + if(d->Type==pkgCache::Dep::Depends || + d->Type==pkgCache::Dep::PreDepends || + (follow_recommends && + d->Type==pkgCache::Dep::Recommends) || + (follow_suggests && + d->Type==pkgCache::Dep::Suggests)) + { + // Try all versions of this package. + for(pkgCache::VerIterator V=d.TargetPkg().VersionList(); + !V.end(); ++V) + { + if(_system->VS->CheckDep(V.VerStr(),d->CompareOp, d.TargetVer())) + { + pkgMarkPackage(Cache, V.ParentPkg(), V, + follow_recommends, follow_suggests); + } + } + // Now try virtual packages + for(pkgCache::PrvIterator prv=d.TargetPkg().ProvidesList(); + !prv.end(); ++prv) + { + if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp, + d.TargetVer())) + { + pkgMarkPackage(Cache, prv.OwnerPkg(), prv.OwnerVer(), + follow_recommends, follow_suggests); + } + } + } + } } +} - // Mark it as used - Cache.SetDirty(Pkg, DirtLevel); - - //fprintf(stdout,"We keep %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel); - // We are a virtual package - if (Pkg->VersionList == 0) +bool pkgMarkUsed(pkgDepCache &Cache) +{ + bool follow_recommends; + bool follow_suggests; + + // init the states + for(pkgCache::PkgIterator p=Cache.PkgBegin(); !p.end(); ++p) { -// fprintf(stdout,"We are virtual %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel); - for (pkgCache::PrvIterator Prv = Pkg.ProvidesList(); ! Prv.end(); ++Prv) - pkgMarkPkgUsed (Cache, Prv.OwnerPkg(), DirtLevel); - return; + Cache[p].Marked=false; + Cache[p].Garbage=false; } - // Depending on the type of dependency, follow it - for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); ! D.end(); ++D) - { -// fprintf(stdout,"We depend on %s %s\n", D.TargetPkg().Name(), D.DepType()); + // init vars + follow_recommends=_config->FindB("APT::AutoRemove::RecommendsImportant",false); + follow_suggests=_config->FindB("APT::AutoRemove::SuggestsImportend", false); - switch(D->Type) + + // do the mark part + for(pkgCache::PkgIterator p=Cache.PkgBegin(); !p.end(); ++p) + { + if(Cache[p].InstallReason==pkgDepCache::Manual || + (p->Flags & pkgCache::Flag::Essential)) { - case pkgCache::Dep::Depends: - case pkgCache::Dep::PreDepends: - pkgMarkPkgUsed (Cache, D.TargetPkg(), pkgCache::State::RemoveRequired); - break; - case pkgCache::Dep::Recommends: - pkgMarkPkgUsed (Cache, D.TargetPkg(), pkgCache::State::RemoveRecommended); - break; - case pkgCache::Dep::Suggests: - pkgMarkPkgUsed (Cache, D.TargetPkg(), pkgCache::State::RemoveSuggested); - break; - case pkgCache::Dep::Conflicts: - case pkgCache::Dep::Replaces: - case pkgCache::Dep::Obsoletes: - // We don't handle these here - break; + if(Cache[p].Keep() && !p.CurrentVer().end()) + pkgMarkPackage(Cache, p, p.CurrentVer(), + follow_recommends, follow_suggests); + else if(Cache[p].Install()) + pkgMarkPackage(Cache, p, Cache[p].InstVerIter(Cache), + follow_recommends, follow_suggests); } } -// fprintf(stdout,"We keep %s %d %d \n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel); -} - /*}}}*/ -bool pkgMarkUsed(pkgDepCache &Cache) -{ - // debug only - if(_config->FindI("Debug::pkgAutoRemove",false) == true) - for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); ! Pkg.end(); ++Pkg) - if(!Cache[Pkg].Dirty() && Cache[Pkg].AutomaticRemove > 0) - std::clog << "has auto-remove information: " << Pkg.Name() - << " " << (int)Cache[Pkg].AutomaticRemove - << std::endl; - - // init with defaults - for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); ! Pkg.end(); ++Pkg) - Cache.SetDirty(Pkg, pkgCache::State::RemoveUnknown); - - // go recursive over the cache - for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); ! Pkg.end(); ++Pkg) - pkgMarkPkgUsed (Cache, Pkg, pkgCache::State::RemoveManual); - + // do the sweep + for(pkgCache::PkgIterator p=Cache.PkgBegin(); !p.end(); ++p) + { + pkgDepCache::StateCache &state=Cache[p]; + + if(!state.Marked) + { + // mark installed but not yet marked stuff as garbage + if(p->CurrentVer != 0) { + state.Garbage=true; + std::cout << "Garbage: " << p.Name() << std::endl; + } + +#if 0 // mvo: the below bits still needs to be ported + + // Be sure not to re-delete already deleted packages. + if(delete_unused && (!p.CurrentVer().end() || state.Install()) && + !state.Delete()) + { + bool do_delete=true; + + // If the package is being upgraded, check if we're + // losing a versioned dep. If the dependency matches + // the previous version and not the new version, keep + // the package back instead of removing it. + if(!p.CurrentVer().end() && state.Install()) + { + const char *vs=p.CurrentVer().VerStr(); + + // Check direct revdeps only. THIS ASSUMES NO + // VERSIONED PROVIDES, but Debian probably won't + // have them for ages if ever. + for(pkgCache::DepIterator revdep=p.RevDependsList(); + !revdep.end(); ++revdep) + { + pkgCache::PkgIterator depender=revdep.ParentPkg(); + // Find which version of the depending package + // will be installed. + pkgCache::VerIterator instver=(*this)[depender].InstVerIter(*this); + + // Only pay attention to strong positive + // dependencies whose parents will be installed. + if(revdep.ParentVer()==instver && + (revdep->Type==pkgCache::Dep::Depends || + revdep->Type==pkgCache::Dep::PreDepends || + (revdep->Type==pkgCache::Dep::Recommends && + follow_recommends))) + { + // If the previous version matched, cancel the + // deletion. (note that I assume that the new + // version does NOT match; otherwise it would + // not be unused!) + if(_system->VS->CheckDep(vs, + revdep->CompareOp, + revdep.TargetVer())) + { + mark_keep(p, false, false, undo); + do_delete=false; + break; + } + } + } + } + + if(do_delete) + mark_delete(p, false, true, undo); + } +#endif + } + } return true; } diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc index e30baa4b2..52b43d83d 100644 --- a/apt-pkg/depcache.cc +++ b/apt-pkg/depcache.cc @@ -78,9 +78,7 @@ bool pkgDepCache::Init(OpProgress *Prog) // Find the proper cache slot StateCache &State = PkgState[I->ID]; State.iFlags = 0; - State.DirtyState = pkgCache::State::RemoveUnknown; - //State.AutomaticRemove = I->AutomaticRemove; - State.AutomaticRemove = pkgCache::State::RemoveUnknown; + State.InstallReason = Manual; // Figure out the install version State.CandidateVer = GetCandidateVer(I); @@ -116,7 +114,7 @@ bool pkgDepCache::readStateFile(OpProgress *Prog) state_file.Open(state, FileFd::ReadOnly); int file_size = state_file.Size(); Prog->OverallProgress(0, file_size, 1, - _("Reading extended state information")); + _("Reading state information")); pkgTagFile tagfile(&state_file); pkgTagSection section; @@ -127,16 +125,17 @@ bool pkgDepCache::readStateFile(OpProgress *Prog) // Silently ignore unknown packages and packages with no actual // version. if(!pkg.end() && !pkg.VersionList().end()) { - short reason = section.FindI("Remove-Reason", - pkgCache::State::RemoveManual); - PkgState[pkg->ID].AutomaticRemove = reason; - //std::cout << "Set: " << pkgname << " to " << reason << std::endl; + short reason = section.FindI("Install-Reason",pkgDepCache::Manual); + PkgState[pkg->ID].InstallReason = (ChangedReason)reason; + if(_config->FindB("Debug::pkgAutoRemove",false)) + std::cout << "Install-Reason for: " << pkgname + << " is " << reason << std::endl; amt+=section.size(); Prog->OverallProgress(amt, file_size, 1, - _("Reading extended state information")); + _("Reading state information")); } Prog->OverallProgress(file_size, file_size, 1, - _("Reading extended state information")); + _("Reading state information")); } } @@ -145,9 +144,6 @@ bool pkgDepCache::readStateFile(OpProgress *Prog) bool pkgDepCache::writeStateFile(OpProgress *prog) { - // FIXME: this function needs to be called inside the commit() - // of the package manager. so after - FileFd StateFile; string state = _config->FindDir("Dir::State") + "pkgstates"; @@ -160,20 +156,20 @@ bool pkgDepCache::writeStateFile(OpProgress *prog) // clear out no longer installed pkg if(PkgState[pkg->ID].Delete() || pkg.CurrentVer() == NULL) - PkgState[pkg->ID].AutomaticRemove = pkgCache::State::RemoveUnknown; + PkgState[pkg->ID].InstallReason = Manual; // check if we have new information if(PkgState[pkg->ID].Flags & pkgCache::Flag::Auto) { if(_config->FindI("Debug::pkgAutoRemove",false)) std::clog << "pkg: " << pkg.Name() << " is auto-dep" << std::endl; - PkgState[pkg->ID].AutomaticRemove = pkgCache::State::RemoveRequired; + PkgState[pkg->ID].InstallReason = Libapt; } - if(PkgState[pkg->ID].AutomaticRemove != pkgCache::State::RemoveUnknown) { + if(PkgState[pkg->ID].InstallReason != Manual) { ostr.str(string("")); - ostr << "Package: " << pkg.Name() - << "\nRemove-Reason: " - << (int)(PkgState[pkg->ID].AutomaticRemove) << "\n\n"; + ostr << "Package: " << pkg.Name() + << "\nInstall-Reason: " + << (int)(PkgState[pkg->ID].InstallReason) << "\n\n"; StateFile.Write(ostr.str().c_str(), ostr.str().size()); } } @@ -841,15 +837,6 @@ void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To) AddSizes(Pkg); } /*}}}*/ -// DepCache::SetDirty - Switch the package between dirty states /*{{{*/ -// --------------------------------------------------------------------- -/* */ -void pkgDepCache::SetDirty(PkgIterator const &Pkg, pkgCache::State::PkgRemoveState To) -{ - StateCache &P = PkgState[Pkg->ID]; - P.DirtyState = To; -} - /*}}}*/ // DepCache::SetCandidateVersion - Change the candidate version /*{{{*/ // --------------------------------------------------------------------- /* */ diff --git a/apt-pkg/depcache.h b/apt-pkg/depcache.h index e02ed72f0..c91e09ab3 100644 --- a/apt-pkg/depcache.h +++ b/apt-pkg/depcache.h @@ -63,6 +63,10 @@ class pkgDepCache : protected pkgCache::Namespace enum VersionTypes {NowVersion, InstallVersion, CandidateVersion}; enum ModeList {ModeDelete = 0, ModeKeep = 1, ModeInstall = 2}; + + // Flags for the GC + enum ChangedReason {Manual, UserAuto, Libapt, FromResolver, PkgIsUnused}; + struct StateCache { // Epoch stripped text versions of the two version fields @@ -79,9 +83,13 @@ class pkgDepCache : protected pkgCache::Namespace unsigned short Flags; unsigned short iFlags; // Internal flags - // Traversal status and state for automatic removal - unsigned char DirtyState; - unsigned char AutomaticRemove; + // mark and sweep flags + ChangedReason InstallReason; +#if 0 + ChangedReason RemoveReason; +#endif + bool Marked; + bool Garbage; // Various tree indicators signed char Status; // -1,0,1,2 @@ -103,7 +111,6 @@ class pkgDepCache : protected pkgCache::Namespace inline bool NowBroken() const {return (DepState & DepNowMin) != DepNowMin;}; inline bool InstBroken() const {return (DepState & DepInstMin) != DepInstMin;}; inline bool Install() const {return Mode == ModeInstall;}; - inline unsigned char Dirty() const {return DirtyState;}; inline VerIterator InstVerIter(pkgCache &Cache) {return VerIterator(Cache,InstallVer);}; inline VerIterator CandidateVerIter(pkgCache &Cache) @@ -194,7 +201,6 @@ class pkgDepCache : protected pkgCache::Namespace unsigned long Depth = 0); void SetReInstall(PkgIterator const &Pkg,bool To); void SetCandidateVersion(VerIterator TargetVer); - void SetDirty(PkgIterator const &Pkg, pkgCache::State::PkgRemoveState To); // This is for debuging void Update(OpProgress *Prog = 0); diff --git a/apt-pkg/pkgcache.h b/apt-pkg/pkgcache.h index 083f20ac2..b07951dfb 100644 --- a/apt-pkg/pkgcache.h +++ b/apt-pkg/pkgcache.h @@ -75,7 +75,6 @@ class pkgCache enum PkgInstState {Ok=0,ReInstReq=1,HoldInst=2,HoldReInstReq=3}; enum PkgCurrentState {NotInstalled=0,UnPacked=1,HalfConfigured=2, HalfInstalled=4,ConfigFiles=5,Installed=6}; - enum PkgRemoveState {RemoveUnknown=0, RemoveManual=1,RemoveSuggested=2,RemoveRecommended=3,RemoveRequired=4}; }; struct Flag diff --git a/cmdline/apt-get.cc b/cmdline/apt-get.cc index 0236d7e77..9d97f8756 100644 --- a/cmdline/apt-get.cc +++ b/cmdline/apt-get.cc @@ -1374,12 +1374,11 @@ bool DoAutomaticRemove(CacheFile &Cache) // look over the cache to see what can be removed for (pkgCache::PkgIterator Pkg = Cache->PkgBegin(); ! Pkg.end(); ++Pkg) { - if (! Cache[Pkg].Dirty() && + if (Cache[Pkg].Garbage && (Pkg->CurrentVer != 0 && Cache[Pkg].Install() == false && Cache[Pkg].Delete() == false)) { - fprintf(stdout,"We could delete %s %d\n", - Pkg.Name(), Cache[Pkg].AutomaticRemove); + fprintf(stdout,"We could delete %s\n", Pkg.Name()); Cache->MarkDelete(Pkg,_config->FindB("APT::Get::Purge",false)); } } diff --git a/debian/changelog b/debian/changelog index 78559fd56..11e1a6282 100644 --- a/debian/changelog +++ b/debian/changelog @@ -14,8 +14,11 @@ apt (0.6.38ubuntu1mvo1) unstable; urgency=low the patch, thanks to Colin Watson for testing it. - better report network timeouts from the methods to the acuire code, only timeout once per sources.list line - - -- Michael Vogt Tue, 28 Jun 2005 11:18:24 +0200 + - started to port the great automatic dependency mangement code from + aptitude over to apt (thanks dburrows for answering my silly + questions and your great help!) + + -- apt (0.6.38ubuntu1) breezy; urgency=low -- cgit v1.2.3