Dependency Resolution and Partial Upgrades

A security advisory names one package. The obvious response is to upgrade that package and nothing else. On a system with a package manager this is sometimes impossible, and the reason is that packages are not independent artifacts. They are nodes in a graph whose edges are version constraints, and a change to one node can invalidate the constraints on every edge that touches it. The resolver’s job is to find an assignment of versions to packages that satisfies all edges at once; the administrator’s request is only one constraint among thousands.

Understanding why a single-package upgrade turns into a hundred-package transaction, or into a refusal, requires looking at what the edges actually say.

The unit of upgrade is the graph

Consider a package that depends on a shared library. The dependency is not “the library exists” but “a version of the library satisfying this range is installed and configured”. When the library’s package releases a new major version, the range expressed by the dependent may no longer admit it, and the dependent must be rebuilt against the new library and re-released with an updated range. Until that happens, the archive contains a dependent whose range excludes the new library.

Upgrading the library alone therefore creates an unsatisfiable state: the new library is installed, the old dependent’s constraint is violated, and the package manager must either keep the old library (defeating the upgrade) or remove the dependent. Neither is what “upgrade this one package” was supposed to mean.

Both major Linux package formats express this with versioned relations, but the vocabulary differs in ways that matter when reading a resolver’s output.

Debian relations include Depends, meaning the target must be configured before the dependent is configured; Pre-Depends, meaning the target must be configured before the dependent is even unpacked; Recommends and Suggests for weaker preferences; Breaks, meaning the target must not be configured at the same time; and Conflicts, meaning the target must not be installed at all. Alternatives are written with a pipe, so a dependency on a mail transport agent is a dependency on any one of several packages, each of which Provides the virtual name.

That Provides mechanism is how a virtual package can be satisfied by implementations that share no code. It is also how a resolver can appear to make an arbitrary choice: if three packages provide the same virtual name and none is installed, the resolver picks one, and the pick is stable only as long as the archive’s ordering and the installed set stay the same.

Version comparison is defined rather than incidental. A Debian version string is [epoch:]upstream[-revision], where the epoch is an integer that overrides everything to its right. The epoch exists to recover from an upstream versioning mistake: when a package must move backwards numerically while still being an upgrade, the epoch increments. An epoch mismatch is the usual explanation for a dependency that looks satisfiable by inspection but is rejected by the resolver.

Why a library rename forces removals

Shared libraries carry a soname, and the soname is embedded in the binary at link time. When a library’s ABI changes incompatibly, the soname changes, and on Debian-derived systems the package name changes with it: libfoo1 becomes libfoo2. The two packages do not conflict, because they install different files. They can coexist, and during a transition they usually do.

Coexistence is what makes the transition possible, and also what makes partial upgrades dangerous. A program built against libfoo1 keeps working as long as libfoo1 remains installed. Once the distribution’s transition completes, libfoo1 is removed from the archive, and any system still holding a binary that links against it has a package that cannot be reinstalled, only replaced. If the binary is locally built and not owned by any package, the dynamic linker fails at the next start with a missing libfoo.so.1.

This is the mechanism behind the standing advice against partial upgrades on rolling distributions. A rolling archive is a snapshot of a state that is internally consistent only as a whole. Installing a subset of the current state onto a system pinned at an older state produces a mixture that no one tested and that may contain, for example, a new libc with an old dynamic linker configuration. The mixture often works, which is worse than always failing, because the failures appear later and look unrelated.

The same logic explains why third-party repositories break upgrades. A vendor repository built against one distribution release declares dependencies on exact versions from that release. When the base system moves forward, the vendor package’s constraints pin components backwards, and the resolver must choose between violating the vendor’s constraint and holding back the base system. Most resolvers choose to hold back, which is why a single foreign package can silently freeze an entire machine’s patch level.

Two commands, two policies

The difference between the upgrade commands is not a matter of thoroughness. It is a difference in which constraints the resolver is allowed to relax.

A conservative upgrade refuses to remove an installed package and refuses to install a package that was not already installed. When satisfying the request would require either, it holds the affected packages back and reports them. This keeps the running system’s package set stable at the cost of leaving known vulnerabilities unpatched, and the held-back list is the only signal that it happened.

A full upgrade permits removals and new installations. It will complete the transition, and in doing so it may remove the very service the upgrade was meant to protect, because the service’s package has not yet been rebuilt for the new library. The transaction is correct with respect to the archive and catastrophic with respect to the machine.

Holds are the third policy, and they interact badly with the first. A package marked as held is pinned at its current version regardless of what the archive offers. Dependencies that require a newer version of the held package become unsatisfiable, so the resolver holds back their dependents as well, and the held set grows transitively. The result is a machine that appears to be receiving updates, since the operation succeeds, while a connected component of its package graph is frozen.

Phased updates produce a similar signature without any hold being set. The archive publishes a new version to a fraction of machines, chosen per machine by a value derived from the machine’s identity, and the rest see the previous version as current. From the resolver’s perspective the new version is simply not offered, so a dependency on it cannot be satisfied yet. The package looks held; nothing is held.

File conflicts and the limits of declaration

Version constraints are not the only way one package can invalidate another. Two packages that ship the same path cannot both own it. rpm checks this at transaction test time and refuses the whole transaction with a file conflict, which is a clean failure. dpkg will allow one package to overwrite a file owned by another only when the incoming package declares a Replaces relation for it; otherwise it aborts the unpack.

The declaration is a promise that the package manager cannot verify. A package that declares Replaces and then ships a file whose format the replaced package’s readers cannot parse will install cleanly and break at runtime. Nothing in the metadata expresses “this file is compatible”.

There is also a class of dependency that no metadata captures: runtime dependencies on services, on kernel features, on configuration. A package can be perfectly installable and still fail to start because the kernel module it needs was removed in the running kernel’s version, or because its configuration file kept an option that the new binary rejects. Those failures are outside the resolver’s model entirely, which is why the conffile problem described in conffile conflicts during package upgrades shows up after the transaction has already succeeded.

Where the resolver gives up

Resolution is a constraint satisfaction problem, and in the general case it is not tractable by any algorithm that scales to a real archive. Practical resolvers are fast because real archives are sparse: most packages have a handful of dependencies, version ranges are narrow, and the installed set is already close to a solution. The hard cases are not random, though. They cluster around transitions, where a large connected component of the graph changes at once, and around third-party repositories, where constraints were written against a state that no longer exists.

When the resolver fails, the useful output is not the error line but the constraint that could not be met. A message naming a version range that no available package satisfies points at a pin, a hold, or a foreign repository. A message naming a conflict points at two packages that both must be installed. A message naming a removal points at a transition the machine has not completed.

The decision the resolver cannot make is which of two working states is preferable: the one where the vulnerable package stays at its old version, or the one where the service that depends on it is removed. That is a judgement about the machine’s purpose, and no constraint solver has access to it. The mechanism can only make the choice explicit, and the difference between the upgrade commands is exactly which choice each one makes by default.

What happens after the new binaries are on disk, and why some of them do not take effect until a restart, is the subject of reboot-required and live kernel patching.