spelunking through the apk-tools dependency solver
In our previous episode, I wrote a high level overview of apk’s differences verses traditional package managers, which many have cited as a helpful resource for understanding the behavior of apk when it does something different than a traditional package manager would. But that article didn’t go into depth in enough detail to explain how it all actually works. This one hopefully will.
A high level view of the moving parts
Our adventure begins at the
/etc/apk/world file. This file contains the basic set of constraints imposed on the system: every constraint listed here must be solvable in order for the system to be considered correct, and no transaction may be committed that is incorrect. In other words, the package management system can be proven to be in a correct state every time a constraint is added or removed with the apk add/del commands.
Note I used the word transaction there: at its core, apk is a transactional package manager, though we have not fully exploited the transactional capabilities yet. A transaction is created by copying the current constraint list (
db->world), manipulating it with
apk_deps_add and then committing it with
apk_solver_commit. The commitment phase does pre-flight checks directly and returns an error if the transaction fails to pass.
This means that removing packages works the same way: you copy the current constraint set, remove the desired constraint, and then commit the result, which either errors out or updates the installed constraint set after the transaction is committed.
A deeper look into the solver itself
As noted above, the primary entry point into the solver is to call the
apk_solver_commit function, which at the time that I am writing this, is located in the apk-tools source code at src/commit.c:679. This function does a few pre-flight checks and then calls into the solver itself, using
apk_solver_solve, which generates the actual transaction to be committed. If there are errors, the generated transaction is discarded and a report is printed instead, otherwise the generated transaction is committed using
In essence, the code in src/commit.c can be thought of as the middle layer between the applets and the core solver. The core solver itself lives in src/solver.c and as previously noted, the main entry point is
apk_solver_solve, which generates a proposed transaction to satisfy the requested constraints. This function lives at src/solver.c:1021, and is the only entry point into the solver itself.
The first thing the solver does is alphabetically sort the constraint set. If you’ve noticed that
/etc/apk/world is always in alphabetical order, this is a side effect of that sorting.
Once the world constraints (the ones in
/etc/apk/world) are alphabetically ordered, the next step is to figure out what package, if any, presently satisfies the constraint. This is handled by the
discover_name function, which is called recursively on every constraint applicable to the system, starting with the world constraint.
The next step is to generate a fuzzy solution. This is done by walking the dependency graph again, calling the
apply_constraint function. This step does basic dependency resolution, removing possible solutions which explicitly conflict. Reverse dependencies (
install_if) are partially evaluated in this phase, but complex constraints (such as those involving a version constraint or multiple solutions) are not evaluated yet.
Once basic constraints are applied to the proposed updated world, the next step is to walk the dependency graph again, reconsidering the fuzzy solution generated in the step above. This step is done by the
reconsider_name function, which walks over parts of the dependency graph that are still ambiguous. Finally, packages are selected to resolve these ambiguities using the
select_package function. Afterwards, the final changeset is emitted by the
A deep dive into
As should hopefully be obvious by now, the really complicated cases are handled by the
reconsider_name function. These cases include scenarios such as virtual providers, situations where more than one package satisfies the constraint set, and so on. For these scenarios, it is the responsibility of the
reconsider_name function to select the most optimal package. Similarly, it is the responsibility of the
select_package function to check the work done by
reconsider_name and finalize the package selection if appropriate by removing the constraint from the ambiguous list.
The primary purpose of the
reconsider_name function is to use
apply_constraint to move more specific constraints upwards and downwards through the dependency graph, narrowing the possible set of packages which can satisfy a given restraint, ideally to one package or less. These simplified dependency nodes are then fed into
select_package to deduce the best package selection to make.
select_package function checks each constraint, and the list of remaining candidate packages, and then picks the best package for each constraint. This is done by calling
compare_providers for each possible package and until the best one is found. The heuristics checked by
compare_providers are, in order:
- The packages are checked to see if they are
NULLor not. The one that isn’t
NULLwins. This is mostly as a safety check.
- We check to see if the user is using
--latestor not. If they are, then the behavior changes a little bit. The details aren’t so important, you can read the source if you really want to know. Basically, in this step, we determine how fresh a package is, in alignment with what the user’s likely opinion on freshness would be.
- The provider versions are compared, if applicable. Highest version wins.
- The package versions themselves are compared. Highest version wins.
- The already installed package is preferred if the version is the same (this is helpful in upgrade transactions to make them less noisy).
provider_priorityfield is compared. Highest priority wins. This means that
provider_priorityis only checked for unversioned providers.
- Finally, the earliest repository in
/etc/apk/repositoriesis preferred if all else is the same.
Hopefully, this demystifies some of the common misconceptions around how the solver works, especially how
provider_priority works. Personally, I think in retrospect, despite working on the spec and implementing it in apk-tools, that
provider_priority was a mistake, and the preferred solution should be to always use versioned providers (e.g.
provides="foo=100") instead. The fact that we have moved to versioning
cmd: providers in this way demonstrates that
provider_priority isn’t really a good design.
Next time: what is the maximum number of entries allowed in
/etc/apk/repositories and why is it so low?