Packages, dependency solving, and distributions

Before you start#

Review userspace and distributions, files and permissions, and build systems. This chapter follows specific APT and dpkg source paths, then surveys selected RPM and libalpm interfaces. A source version identifies a reading target; it is not a recommendation to install an old package manager or change your host.

Learning goals#

Separate repository trust, dependency planning, archive extraction and package configuration. Explain why a package plan can fail before installation, why unpacking does not mean configuration succeeded, and why a signed package can still execute privileged code. Analyze a small dependency graph and inspect a toy archive without performing a package transaction.

Source walkthrough#

A distribution selects versions, builds software, supplies repository metadata and defines policies for upgrades. A package manager is userspace software; Linux does not implement APT or dpkg policy. APT uses repository indexes and local package state to select versions and construct a plan. dpkg is a lower-level Debian package manager that tracks and changes package state when instructed. The boundary is conceptual as well as operational: downloading a file, extracting its archive, unpacking a package into a root filesystem, and running its configuration scripts are different actions with different authority and failure modes.

In APT 2.9.8 apt-pkg/algorithms.cc, pkgProblemResolver::Resolve chooses between a configured external solver and its internal resolution path. The project's pinned COPYING gives the general files GPL-2-or-later, with stated exceptions; this file is covered by that general entry. The following exact function body is quoted with its signature:

bool pkgProblemResolver::Resolve(bool BrokenFix, OpProgress * const Progress)
{
   std::string const solver = _config->Find("APT::Solver", "internal");
   auto const ret = EDSP::ResolveExternal(solver.c_str(), Cache, 0, Progress);
   if (solver != "internal")
      return ret;
   return ResolveInternal(BrokenFix);
}

The configuration lookup selects a solver name with internal as its default. EDSP::ResolveExternal receives that name, the resolver's package cache and progress reporting; the shown function returns its result when an external solver was selected. Otherwise it invokes ResolveInternal with the requested broken-state handling. The cache represents APT's view of package versions and dependency state; it is not the filesystem payload itself. This excerpt identifies a conditional dispatch, not a claim that every APT transaction uses one fixed algorithm or that the external call necessarily launches a particular process in all cases. The adjacent comments describe a scoring-based resolution pass, and the exact algorithm and policy may change across releases.

The dpkg 1.22.9 src/main/configure.c, deferred_configure, carries a GPL-2-or-later file notice. The following exact excerpt omits later dependency and configuration work:

	if (pkg->status == PKG_STAT_NOTINSTALLED)
		ohshit(_("no package named '%s' is installed, cannot configure"),
		       pkg_name(pkg, pnaw_nonambig));

The pkg object is dpkg's representation of a package and its state. This branch rejects configuring a package recorded as not installed and produces an error using its package name. Subsequent branches distinguish already configured and inappropriate states; later work checks dependencies and runs configuration operations under dpkg's rules. An error can leave a package unpacked or half-configured rather than atomically restoring the entire machine to its previous state. The caller must inspect the reported state and use the distribution's recovery procedure, not assume the archive was never extracted.

Repository metadata and authority#

A repository publishes indexes describing available package versions, dependencies and checksums. In the APT model, InRelease is a clearsigned Release file; alternatively, a detached Release.gpg signature authenticates Release. The Release metadata carries hashes of index files such as Packages; those indexes identify package files and their hashes. Verification therefore chains archive bytes to indexes to metadata accepted under configured keys and policy. Key management, expiration, repository configuration and transport errors can interrupt this chain. An authenticated archive can still contain malicious or defective code: signature verification answers a provenance and integrity question under a trust policy, not whether a package is safe. See APT secure repository documentation.

The arrows in that map follow the chain described above. The last target has no arrow on purpose: a valid signature on metadata and an index entry for a checksum say nothing about what a maintainer script will do when it runs.

Package metadata describes constraints using versioned dependencies, alternatives, conflicts and virtual provisions. A dependency such as editor-api (>= 2) | alternative-api can be satisfied by a suitable candidate or provider under the package manager's rules. A virtual name is not necessarily a file and its provider's version semantics must be checked rather than assumed. An installed version, a repository candidate and a requested version are distinct pieces of state. Pinning policy and repository priorities can select an older candidate, forbid an upgrade or change which alternative is considered. Metadata can also be inconsistent, stale or unavailable.

A Debian .deb is an ar archive whose required members include debian-binary, control.tar and data.tar (the tar members may use supported compression suffixes). The control archive carries package control data and may carry maintainer scripts; the data archive contains payload paths. Exact format and compression support depend on dpkg version. Merely listing members with ar t or extracting into a private directory does not update dpkg's database, execute scripts or install files. Installing a package into a system root is different: maintainer scripts can run with the transaction's authority and may alter services or configuration. This lesson never runs such scripts or modifies the host package database. See Debian binary package format.

APT planning operates over a cache of packages, versions and dependency relations; apt-pkg/depcache.cc contains MarkInstall and related dependency processing. The plan can include installing, upgrading, keeping or removing packages. A plan is not yet a completed transaction. Between obtaining metadata and executing a plan, files, repository state or local package state can change. Locks serialize relevant operations, but cannot make external repositories immutable or guarantee a later download still exists. Preserve the indexes and version choices used for a reproducibility claim.

Worked constraint graph#

Consider a synthetic repository containing app version 1, engine versions 1 and 2, and viewer version 1. The app requires engine >= 2; the viewer requires engine < 2; the system currently has engine 1 and viewer 1. If the user requests app while also requiring viewer to remain installed, there is no solution using only these versions: engine 1 violates app's constraint and engine 2 violates viewer's constraint. An implementation may report a conflict or propose removing viewer if policy allows. A tool's suggestion is not an authorization to remove it.

Now add viewer 2, which requires engine >= 2, and permit upgrading viewer. A candidate plan is app 1 plus engine 2 plus viewer 2. The solver must consider a coordinated upgrade, not simply install app beside the current engine. If a repository also provides an alternative engine implementation, its exact Provides metadata and version eligibility determine whether it can satisfy the dependency. Do not assume every provider satisfies every version relation. A backtracking solver could first try an invalid candidate and then find the coordinated upgrade; this graph is a teaching exercise and does not claim APT 2.9.8 necessarily explores candidates in that order.

Suppose the plan is valid but downloading engine 2 fails a hash check. The plan has not made the failed bytes trustworthy; reject them and diagnose metadata, mirror or transport. Suppose instead the package files are accepted and unpacking succeeds but a post-install configuration script fails. The filesystem and package database can then describe an intermediate state requiring recovery. Those are different failures at different stages. Saving only the final command's exit status loses the dependency choices, verification result and package state needed to explain what happened.

Unpack, configure and recovery#

In the pinned src/main/unpack.c, process_archive is an entry point for archive processing. The package's data members, control information and database state must be handled under dpkg's rules. A valid archive can still conflict with installed file ownership, have an unsupported format, fail due to disk space or encounter script failure. File replacement, backup and rollback behavior depends on the operation and failure point; it is unsafe to describe an entire multi-package upgrade as one universally atomic filesystem transaction.

Configuration can run maintainer scripts, update status and participate in trigger processing. Triggers defer or consolidate work that a package requests another component to perform. A configuration file, often called a conffile in Debian package terminology, has special upgrade handling intended to preserve or ask about local changes; it is not an ordinary guarantee that all application configuration is automatically merged. A package may be in unpacked, half-configured, installed or another recorded state. The deferred_configure guard above rejects inappropriate transitions, then the broader code performs more checks and work. Recovery requires identifying the actual state and consulting the system's own instructions. Do not run recovery commands against an unrelated host merely because a chapter mentions them.

APT and dpkg use locks to prevent conflicting operations on relevant state. A lock does not make a transaction safe to interrupt at every instruction, and deleting lock files or forcing concurrent package operations is not a recovery strategy. A package database, the actual filesystem and external services can diverge after an interrupted or failed operation. Preserve logs, the package version and state before deciding on a repair. In a disposable teaching environment, retain a snapshot or rebuildable image so a failed experiment can be discarded rather than repaired in place.

Reproducible package builds ask whether independently controlled builders can produce matching package artifacts from specified inputs. Reproducible installation asks a different question: whether a specified set of packages and configuration produces an equivalent installed state under stated conditions. Repository snapshots, dependency versions, architecture, triggers, scripts, time and prior configuration all matter. Matching source tags or package names alone do not fix all of those inputs. Installation scripts may read machine-specific state, so identical package files do not by themselves imply identical running systems.

Comparative survey#

RPM and DNF, and Pacman with libalpm, have related responsibilities but do not implement APT's pkgProblemResolver or dpkg's package states. In the pinned RPM 4.20.0 lib/transaction.c, rpmtsRun operates on an RPM transaction set and calls preparation logic; an RPM frontend's dependency planning and repository policy are separate concerns. This is a source entry point, not an exhaustive account of DNF or libsolv. Different RPM releases and frontends can use different dependency solvers and plugins.

In Pacman 6.1.0 lib/libalpm/trans.c, alpm_trans_prepare and alpm_trans_commit are distinct library transaction stages. The API uses an alpm_handle_t and transaction state; callers must respect that library's own error, locking and lifetime rules. These selected names support a comparison of staged operations, not an assertion that RPM, APT and libalpm share a solver or identical rollback semantics. The user-facing command, archive metadata, signature policy and database are project-specific.

In the pinned Pacman 6.1.0 source, lib/libalpm/trans.c, which carries a GNU General Public License notice (version 2 or later, GPL-2.0-or-later), alpm_trans_prepare finishes planning by sorting dependencies and then recording the prepared state. The following exact lines are 148-162 of that file; the earlier preparation branches are omitted:

	if(!(trans->flags & ALPM_TRANS_FLAG_NODEPS)) {
		_alpm_log(handle, ALPM_LOG_DEBUG, "sorting by dependencies\n");
		if(trans->add) {
			alpm_list_t *add_orig = trans->add;
			trans->add = _alpm_sortbydeps(handle, add_orig, trans->remove, 0);
			alpm_list_free(add_orig);
		}
		if(trans->remove) {
			alpm_list_t *rem_orig = trans->remove;
			trans->remove = _alpm_sortbydeps(handle, rem_orig, NULL, 1);
			alpm_list_free(rem_orig);
		}
	}

	trans->state = STATE_PREPARED;

That state change is the observable boundary: a prepared transaction is a plan that the commit stage may consume. Preparation does not show that packages were downloaded, that hooks ran or that files were installed. The sort runs only when the transaction does not request no-dependency handling, so the order is a property of this flag and call path rather than of every libalpm operation.

In the same file, lib/libalpm/trans.c, under the same GPL-2.0-or-later notice, alpm_trans_commit moves to a committing state before it calls the removal or sync-commit path. The branch below records a failed transaction, and it distinguishes an interrupted commit from a completed one. Lines 212-235 are quoted exactly; the post-transaction hook and the final return are omitted:

	if(trans->add == NULL) {
		if(_alpm_remove_packages(handle, 1) == -1) {
			/* pm_errno is set by _alpm_remove_packages() */
			alpm_errno_t save = handle->pm_errno;
			alpm_logaction(handle, ALPM_CALLER_PREFIX, "transaction failed\n");
			handle->pm_errno = save;
			return -1;
		}
	} else {
		if(_alpm_sync_commit(handle) == -1) {
			/* pm_errno is set by _alpm_sync_commit() */
			alpm_errno_t save = handle->pm_errno;
			alpm_logaction(handle, ALPM_CALLER_PREFIX, "transaction failed\n");
			handle->pm_errno = save;
			return -1;
		}
	}

	if(trans->state == STATE_INTERRUPTED) {
		alpm_logaction(handle, ALPM_CALLER_PREFIX, "transaction interrupted\n");
	} else {
		event.type = ALPM_EVENT_TRANSACTION_DONE;
		EVENT(handle, (void *)&event);
		alpm_logaction(handle, ALPM_CALLER_PREFIX, "transaction completed\n");

A failed call returns before the completion event, and an interrupted state skips the completed-event path. The excerpt shows which branch runs, not what has already been written. It does not show rollback of installed files and does not establish that a database or filesystem can be restored after an interruption. Read the libalpm states as the library's bookkeeping, not as an atomic guarantee.

The pinned DNF 4.21.1 dnf/base.py has separate Base.resolve and Base.do_transaction methods. Its resolution path prepares a goal, protected packages and solver decisions before transaction execution. The separately pinned libsolv 0.7.30 src/solver.c defines solver_solve with a solver and job queue. These are selected source entry points for a comparison, not a verified complete call chain from this DNF release to that particular independently pinned libsolv build, nor a claim that every RPM frontend uses it. They illustrate why a frontend's request, solver's job representation and transaction engine should be investigated at their own version boundaries.

When comparing any two systems, ask which component consumes repository metadata, which constructs a dependency plan, which verifies signatures, which writes files and runs scripts, and how each records an interrupted state. A shared word such as “transaction” does not automatically mean a fully atomic database transaction over every file and external side effect. Inspect the relevant version and avoid assuming that a frontend's output is the same as the lower-level package manager's internal state.

Practice#

This exercise creates an intentionally simplified ar archive with a marker and two harmless text files. It is not a valid installable Debian package and no package manager is invoked. It needs only ar, a shell and private temporary storage:

work=$(mktemp -d)
printf '2.0\n' > "$work/debian-binary"
printf 'toy control metadata; no maintainer scripts\n' > "$work/control.tar"
printf 'toy payload; not a tar archive\n' > "$work/data.tar"
(cd "$work" && ar r toy.deb debian-binary control.tar data.tar)
ar t "$work/toy.deb"
mkdir "$work/extracted"
(cd "$work/extracted" && ar x ../toy.deb)
printf 'marker: '; cat "$work/extracted/debian-binary"
rm -rf -- "$work"

Expected output lists the three member names and marker 2.0. The control and data members deliberately contain plain text, so attempting to treat them as real tar archives would fail; this is the counterexample showing that member names alone do not validate a package. If ar is unavailable or extraction fails, record the tool and error and use the worked dependency graph above. No package database, index, host configuration or service is touched. The temporary directory and its archive are removed at the end.

As a source-only alternative, draw the app/engine/viewer graph twice: first show the incompatible engine constraints with viewer 1 held, then add viewer 2 and explain the coordinated upgrade. Add a four-row evidence table for metadata verification, dependency planning, unpacking and configuration. Mark each stage as unexecuted in this alternative. Deliver the graph and table rather than a command that installs software.

Knowledge check#

1. Why can a trusted repository signature fail to establish that a maintainer script is safe?
2. In the first worked graph, which constraints conflict and what additional version permits a solution?
3. What happens in the quoted dpkg branch when a package is recorded as not installed, and why is unpacked not equivalent to configured?
4. Why can a valid dependency plan still fail during download or configuration?
5. What do the selected RPM and libalpm source entry points establish, and what do they not establish about APT's solver?

Answers#

1. The signature verifies metadata or package provenance and integrity under configured trust assumptions. It does not prove the authenticated code is harmless; maintainer scripts can run with the transaction's authority.
2. App requires engine at least 2 while viewer 1 requires less than 2. With viewer held, neither available engine satisfies both. Viewer 2 requiring engine at least 2 allows a plan with engine 2 if policy permits that upgrade.
3. deferred_configure reports an error for the not-installed state. Unpacking puts package payload and metadata into an intermediate state, while configuration includes additional checks and potentially scripts and triggers that can fail.
4. The plan depends on metadata and assumed local state. A download may be unavailable or fail verification; disk operations or a maintainer script may fail later, leaving a state different from both the initial plan and a fully configured system.
5. They identify RPM transaction execution and libalpm prepare/commit stages in particular releases. They do not show identical solver algorithms, rollback guarantees, package formats or trust policies across projects.

Checkpoint#

Submit the version-constraint graph, four-stage evidence table and either the toy archive listing or the source-only analysis. Ready means explaining the unsatisfiable case, naming the state rejected by the dpkg excerpt, and distinguishing authenticated metadata from safe script behavior. If unclear, retry with only app and engine, then add viewer and the failure stages. This is not authorization to modify a production package database.

Sources#

• APT 2.9.8 resolver
• APT 2.9.8 dependency cache
• dpkg 1.22.9 configuration
• dpkg 1.22.9 archive processing
• RPM 4.20.0 transaction source
• Pacman 6.1.0 libalpm transaction source