Problem statement Currently if you have an automatically installed package A (= 1) where A (= 1) Depends B (= 1) A (= 2) Depends B (= 2) and you upgrade B from 1 to 2; then you can: Remove A (= 1) Upgrade A to version 2 If A was installed by a chain initiated by Recommends (say X Rec Y, Y Depends A), the solver sometimes preferred removing A (and anything depending on it until it got). ... Read more 》

As I was shopping groceries I had a shocking realization: The active dependencies of packages in a solver actually form a trie (a dependency A|B - “A or B” - of a package X is considered active if we marked X for install). Consider the dependencies A|B|C, A|B, B|X. In most package managers these just express alternatives, that is, the “or” relationship, but in Debian packages, it also expresses a preference relationship between its operands, so in A|B|C, A is preferred over B and B over C (and A transitively over C). ... Read more 》

As you may recall from previous posts and elsewhere I have been busy writing a new solver for APT. Today I want to share some of the latest changes in how to approach solving. The idea for the solver was that manually installed packages are always protected from removals – in terms of SAT solving, they are facts. Automatically installed packages become optional unit clauses. Optional clauses are solved after manual ones, they don’t partake in normal unit propagation. ... Read more 》

In my previous blog, I explored The New APT 3.0 solver. Since then I have been at work in the test suite making tests pass and fixing some bugs. You see for all intents and purposes, the new solver is a very stupid naive DPLL SAT solver (it just so happens we don’t actually have any pure literals in there). We can control it in a bunch of ways: We can mark packages as “install” or “reject” We can order actions/clauses. When backtracking the action that came later will be the first we try to backtrack on We can order the choices of a dependency - we try them left to right. This is about all that we really want to do, we can’t go if we reach a conflict, say “oh but this conflict was introduced by that upgrade, and it seems more important, so let’s not backtrack on the upgrade request but on this dependency instead.”. ... Read more 》

APT 2.9.3 introduces the first iteration of the new solver codenamed solver3, and now available with the –solver 3.0 option. The new solver works fundamentally different from the old one. How does it work? Solver3 is a fully backtracking dependency solving algorithm that defers choices to as late as possible. It starts with an empty set of packages, then adds the manually installed packages, and then installs packages automatically as necessary to satisfy the dependencies. ... Read more 》

APT currently knows about three types of upgrades: upgrade without new packages (apt-get upgrade) upgrade with new packages (apt upgrade) upgrade with new packages and deletions (apt{,-get} {dist,full}-upgrade) All of these upgrade types are necessary to deal with upgrades within a distribution release. Yes, sometimes even removals may be needed because bug fixes require adding a Conflicts somewhere. In Ubuntu we have a third type of upgrades, handled by a separate tool: release upgrades. ubuntu-release-upgrader changes your sources.list, and applies various quirks to the upgrade. ... Read more 》

This is the story of the currently progressing changes to secure boot on Ubuntu and the history of how we got to where we are. taking a step back: how does secure boot on Ubuntu work? Booting on Ubuntu involves three components after the firmware: shim grub linux Each of these is a PE binary signed with a key. The shim is signed by Microsoft’s 3rd party key and embeds a self-signed Canonical CA certificate, and optionally a vendor dbx (a list of revoked certificates or binaries). grub and linux (and fwupd) are then signed by a certificate issued by that CA ... Read more 》

Z3 is a theorem prover developed at Microsoft research and available as a dynamically linked C++ library in Debian-based distributions. While the library is a whopping 16 MB, and the solver is a tad slow, it’s permissive licensing, and number of tactics offered give it a huge potential for use in solving dependencies in a wide variety of applications. Z3 does not need normalized formulas, but offers higher level abstractions like atmost and atleast and implies, that we will make use of together with boolean variables to translate the dependency problem to a form Z3 understands. ... Read more 》

This is an edited copy of an email I sent to provide guidance to users of apt-key as to how to handle things in a post apt-key world. The manual page already provides all you need to know for replacing apt-key add usage: Note: Instead of using this command a keyring should be placed directly in the /etc/apt/trusted.gpg.d/ directory with a descriptive name and either “gpg” or “asc” as file extension ... Read more 》

APT 2.2.0 marks the freeze of the 2.1 development series and the start of the 2.2 stable series. Let’s have a look at what changed compared to 2.2. Many of you who run Debian testing or unstable, or Ubuntu groovy or hirsute will already have seen most of those changes. New features Various patterns related to dependencies, such as ?depends are now available (2.1.16) The Protected field is now supported. It replaces the previous Important field and is like Essential, but only for installed packages (some minor more differences maybe in terms of ordering the installs). The update command has gained an --error-on=any option that makes it error out on any failure, not just what it considers persistent ons. The rred method can now be used as a standalone program to merge pdiff files APT now implements phased updates. Phasing is used in Ubuntu to slow down and control the roll out of updates in the -updates pocket, but has previously only been available to desktop users using update-manager. Other behavioral changes The kernel autoremoval helper code has been rewritten from shell in C++ and now runs at run-time, rather than at kernel install time, in order to correctly protect the kernel that is running now, rather than the kernel that was running when we were installing the newest one. ... Read more 》