7  Package management meta-tools: survey and state of the art

This section is taken from [EDO06].

In this section, we will consider existing package management tools. These tools perform functions such as storage management, distribution and dependency management.

  • Storage management includes packing and unpacking packages, checking their integrity, setting up configuration files.
  • Distribution is the network transfer of package files.
  • Dependency management orchestrates the previous two tasks in order to install, remove or upgrade software packages while maintaining the health of the system.

Major Linux distributions tend to use different tools for different tasks. Often a low-level storage management tool such as dpkg for Debian-based systems or rpm for RPM-based systems is controlled by a higher-level “meta” tool such as APT or urpmi. Ports-based systems such as Gentoo may use a single tool (emerge).

We are mostly interested in the formal aspects of dependency modeling and in the algorithmic aspects of dependency solving. Thus, low-level tools are out of our scope, but it is generally difficult to distinguish these two different kinds of tools without a close examination. We therefore begin by doing a quick survey of known tools, open-source and commercial, that deal with package management – some of which are programming language-specific.

Most of the many open-source and commercial package management projects deal only with storage management or distribution. Most of the rest do not handle complex requirements (namely, disjunctive dependencies with conflicts). Of the handful of package management tools that have non-trivial dependency handling logic we have the well-known and mainstream apt, urpmi and smart tools, on which we will focus in the remaining sections, providing for each of these a description of their algorithms, particularities and limitations we found during our investigations. In particular, we report, for each dependency solver, our findings concerning completeness, good formal properties (commutativity, declarativity), and efficiency. We also tested whether, given a full solution, each depsolver is able to simply verify that it is indeed a solution, and apply it directly. We also describe some properties of the code (programming language used, number of lines of code, overall structure, code quality).

Finally, we argue that neither of these tools can be used to correctly and efficiently check the abundance and peace conditions (see Definition 3) for a repository.

7.1  Quick survey of known tools and formalizations

7.1.1  Software providing NP-complete dependency management logic

These are package management tools that handle a dependency system whose expressive power is at least equivalent to boolean logic and that have solvers which should, bugs notwithstanding, be able to solve generic satisfiability problems.

The three major pieces of such a software (namely APT, URPMI and Smart), that are often used by well-established Linux distributions, are studied extensively in the following section. For completeness, we mention the following minor managers that also have a comparable level of logic complexity:

  • ipkg, also known as The Itsy package management system. Although it is proclaimed as a lightweight dpkg-replacement for iPaq PDAs, it has a complete dependency resolution engine. It is written in C.
  • swup A high-level package management tool, written in Python and used in Trustix Linux, that is able to handle conflicts, disjunctive dependencies and to install multiple versions (in fact, Gentoo-like slots) of a given unit. This tool may have been taking a non-OSS path as its CVS repository and source code seem to be no longer available.
  • Mongoose Package Manager, also known as mpak, was aiming to be “a kernel and architecture-independent package manager with support for dependency tracking...”. Written in C++, it is largely unfinished and was last updated in August 2004.
  • slapt-get An APT-like system for Slackware package management written in C which handles disjunctive dependencies, conflicts and suggestions, but does not seem to do complete resolution.

Derivatives of the major package management tools:

  • fink is a port of the Debian APT system to Darwin and Mac OS X.

7.1.2  Entities handling less-than-NP-complete dependency logic

Installation-on-demand

These tools attempt to provide automatic, on-demand and transparent installation of software.

  • klik Klik provides an easy way to download and use software for most major distributions. The approach is to create a self-contained package that is able to run on almost any Linux distribution. Klik is an application that is integrated within the web browser. When a user follows a “klik” link, the software client contacts the server and requests a “klik recipe”. The recipe is a file that tells the client what packages to download, the location of these packages and how to install them in a self contained package.

    The self contained package is a compressed image file that contains the basic system necessary for the application to run. After it is generated, it is mounted on the loop device and a wrapper script is called that enables the execution of the application.

  • ZeroInstall http://0install.net/ It is composed of two systems, Filesystem and Injector allowing users to run software without needing neither installation nor superuser privileges.
Storage managers

The tools in this category do not compile packages. Their main task is to add and remove packages. To add a package, the user obtains a package file (a binary archive containing some metadata) manually and then invokes the tool. The tool then checks the integrity of the package, unpacks it, calls contained installation scripts, and registers the package in the system package database. To remove a package, the user simply invokes the tool with the name of the package to remove. The associated files, whose paths are stored in the package database, are removed, unless they are configuration files modified by the user.

Classical storage-only managers

The following storage-only managers do not know anything about dependencies or conflicts.

  • FreeBSD, NetBSD and OpenBSD pkg_add, pkg_remove tools that complement the ports system.
  • Slackware’s pkgtool similar to the above BSD tools.
  • UniPKG A modular package manager that natively handles various package formats.
  • gnupdate A universal package management system comprising gpkg and libpackman.
  • libpackage (Open Package Library)
  • Splack A port of Slackware to SPARC.
  • UPMS is a simple package management system written in shell script with simple dependency management, for Filesystem Hierarchy Standard (FHS)-compliant Linux distributions.
  • pkgutils are package management utilities for Linux, used by the CRUX distribution. They are written in C++ and have no dependency management, only storage management with file-based conflict detection.
  • tinypackage A lightweight package manager for UNIX systems.

Some storage managers know of dependencies and conflicts because they are actually the backend of a suite of higher-level package management tools

  • dpkg as used by Debian APT
  • rpm as used either directly or as librpm by RPM-based distributions such as Red Hat or Madriva.
  • xpkg is the package manager of the OpenDarwin project handles complex dependencies.
Symbolic link managers

A particular and most primitive class of storage managers is the class of symbolic link managers. Assume software packages come as simple tar archives that can be extracted anywhere. Extending all search paths (for executables, libraries, manual pages...) for each piece of new software is cumbersome (one would get very long path variables) and usually requires users to restart their session to take fully effect. As for extracting an archive directly into the root filesystem, not only is it very dangerous (as vital system files, such as /etc/passwd may get, erroneously or maliciously, overwritten), it is also impossible to undo. Indeed, even if no file is overwritten, one still needs the original archive to know which files to delete. The idea of symbolic link managers is to have each piece of software in its own directory, at a known place, for instance under /opt or /usr/depot, to confine software to their own directories, thus allowing easy removal and preventing modification of important system files. Links are then established from standard points in the filesystem to that directory. For instance, vim would be unpacked in /opt/vim/, and a symbolic link would be created by the manager from /usr/bin/vim to /opt/vim/bin/vim. Removing packages is as easy as removing the /opt/vim directory and its contents while removing associated symbolic links. This scheme has the advantage of extreme simplicity. On modern systems, the overhead of symbolic links should be negligible. The depot tool is the most well-known symbolic link manager which has inspired a number of others.

  • depot
  • GNU stow and derivatives like stowES, XStow, reflect
  • graft
  • swpkg
  • encap, epkg, sencap
  • slashpackage
  • spill
  • It package manager
Classical storage and download managers

Augmenting storage managers with simple (non-disjunctive, non-conflictual) dependency information and automatic retrieval capabilities gives a class of tools for which the linear-time topological sorting algorithm is adequate for solving dependency problems. Unfortunately, disjunctions and conflicts can only be disposed of in an ideal world.

  • aduva
  • uludag
  • spkg A package management utility for Slackware that can do upgrades.
  • openbechede An OpenBSD packages tool
Package managers for programming languages

Modern programming languages have built-in modularity and therefore are ideally suited for software component management techniques. However this also means that conflicts and disjunctions are not common, and component managers seldom handle them.

  • Godi for Ocaml features dependency and conflict resolution, compilation options and automated downloading and compiling.
  • Ruby gems
  • libneedle for Ruby
  • CPAN, the Comprehensive Perl Archive Network, contains package installation tools that try to automate the download and installation of Perl modules
  • OSGi bundles are Java archive files that contain some installation and configuration classes and some static dependency information.
Recompilation frameworks

In their basic implementation, these systems can be described as a structured version control repository. Units exist as subdirectories of the repository. Each subdirectory contains a Makefile and associated scripts. Users of the system will first checkout the latest version of the repository. They will then place themselves in the directory of a unit they wish to install. An invocation of make will then automatically download the sources, configure and compile them, and install the unit. If the unit depends on other units, a recursive invocation of make on the associated directory will download and build it. The typical representative of this class of systems the BSD ports system, as used by FreeBSD, NetBSD and OpenBSD. These use standard tools (CVS, make, fetch) and shell scripts. While simple and elegant, the repositories being very large, performance issues arise when doing updates with CVS or Subversion (SVN). Also, the lack of logical expressiveness of make prohibits circular or disjunctive dependencies and conflicts.

Gentoo Linux significantly improves the ports system by replacing make with a more intelligent tool called emerge. This tool has finer-grained control over compilation options and can handle disjunctive dependencies. The general architecture and the “slotting” system reduce the number of conflicts. However, conflicts can arise due to incompatible requested version ranges, especially if subdistributions of different stability are mixed in the same system. Conflicts and circular dependencies, although rare, are not well-handled by emerge.

Version control system-based:

  • BSD ports, the classical CVS and make-based ports system
  • Gentoo portage is basically BSD ports with enhanced logic
  • mpkg A FreeBSD-like ports collection for DEC OSF/1, Linux, Solaris.
  • Darwin pkg is a port of the FreeBSD software package system to the Darwin OS.
  • The Scrudgeware tools are a combination of Encap and of the BSD ports system.
  • Emerde is a port of Gentoo’s Portage system for other distributions.
  • Conary is an interesting package management system that is based on an enhanced source version control system including local changesets (describing local modifications to configuration files) and shadows (which allows creation of a branch in the source control system that follows the evolutions of its parents). It is used in rPath linux.

Recompilation-only:

  • toast is a simple source-and-symlinks, recompiling package manager for both root and non-root users.
Metadata formats or ontologies

Modular programming is not something new and formalization of interdependencies between software components is as old as dependency graphs and the make tool. Of course such crude modeling is grossly insufficient for today’s highly complex relationships between packages. Heterogeneous software environments mandate, because of binary compatibility and linking issues, the use of version numbers, dependencies with upper- and lower-bounded ranges, disjunctive dependencies and therefore conflicts. There is a limit on what can be done with dynamic linking, hence many important aspects of a software product, such as the graphical toolkit it uses or the optimized numerical algorithm library it relies on must be known as a compile time. As a result, the number of units a software product can give grows as the product of the number of variants of components that must be statically linked. Assume we have a video player with GTK, KDE or command-line interfaces whose codecs must for some reason be statically linked (perhaps due to the language used), with available unoptimized codecs, optimized for AMD and Intel, 32- and 64-bit versions. This gives a total of 3 × 2 × 2 = 12 units. Add two units for common architecture-independent files such as documentation and GUI skin files. This gives 14 units. On the other hand, if we make the product into a library with its own documentation and development version, then we have 4 library units, 2 development units, 2 architecture-independant units and 3 main units with different interfaces, which saves us one unit.

  • Trove is a somewhat old proposal by Eric S. Raymond focused on software archive maintenance issues. It proposes to use the same dependency fields as in Debian, but does not delve deeper into the associated combinatorial problems.
  • The Dublin Core Metadata Initiative is a large and ambitious initiative that aims to create interoperable metadata standards for describing all kinds of information resources. Its overly broad scope and fuzzy semantics are not suitable for package management.
  • RPM metadata is an XML format proposal by Duke University for describing package metadata. From a dependency viewpoint, their DTD is based on the RPM format and provides sufficiently expressive fields.
  • The Installable Unit Package Format Specification is a W3C proposal developed by the OASIS consortium for standardizing packaging formats, notably for commercial software to be distributed on removable media, in order to create interoperable installers, notably for operating systems that lack packaging functions, such as Microsoft Windows, as can be deduced from the participation of InstallShield Softwarea Corp.
  • Not to be confused with Fink, Flink aims for formalize various knowledge about the Linux system. This includes formalizing package interrelationships. They provide an Owl ontology modeled on the Debian policy manual.

7.2  Analysis of some package management tools

In the following sections we perform an in-depth analysis and description of four mainstream package management meta-tools: Apt, Portage, Smart and Urpmi.

We are particularly interested in determining their fitness for being used as installability verifiers, i.e. tools to check server-side repository consistency, which is one of the main goals of our workpackage.

General analysis on a given testbench

For each of these tools, we performed the very same tests on a specially built package base, shown in figure 16, designed in order to verify completeness of the dependency solving algorithm (crucial for our goals), but also the quality of the solution found, which is crucial for the stated goals of these tools, which is maintaining an up-to-date installation on a user machine.


Figure 16: Graph of car dependencies and conflicts.

This fake repository contains a deeply nested conflict among glass version 2 and tyre version 2, and has one “optimum” solution (figure 17), in terms of number of freshest installed packages, which is given by taking tyre=1, and the most recent version for all other packages.


Figure 17: Car/Glass: optimum solution (maximum number of latest versions).

For information, the WP2 toolchain statistics on this fake repository are available online at http://www.edos-project.org/xwiki/stats/car.html. See also Figure 18.


Figure 18: Car/Glass: graphical representation of the dependency generated with the EDOS toolchain

The analysis show that no system is able to find the best solution but urpmi under certain conditions, and all but Smart do fail in being complete. For the Apt and Smart tool, we also investigate much more in depth the inner working of the system, finding a very surprising behavior for Apt, and exposing the potentially explosive computational behavior of Smart.

For all these reasons, we conclude that not a single one of these tools can be used to perform installability checking, and that we need to develop our own.

7.3  APT

The APT tool has been for a long time a key element of the success of the Debian distribution. It was indeed one of the first meta-package management tools incorporating dependency solving and package retrieving algorithms that gave the user the feel of a system able to automatically fetch and install the best set of packages suited for her needs.

The problem that APT tries to solve is quite tricky: maintain a distribution consistent, while upgrading to the most recent version of the packages that a user may require, which, as we have said before, is a more complex problem than mere installability, known now to be NP-complete (see Section 4.2).

As a result, in order to get answers in acceptable time, APT is forced to incorporate heuristics and stategies that turn out, when properly analysed, to be incomplete, inconsistent and to exhibit a surprising behavior (for a user).

For these reasons, APT is not an acceptable tool if one only needs to check for installability of a package (and it should not be used in the Debian production process to check whether a package may or not be migrated from one release to another, like from unstable to testing).

We report here our findings which seem not to be widely known. Let us start by testing APT’s dependency solver on the Car/Glass example.

7.3.1  Apt on the Car/Glass testbench

If apt-get was optimal it should install the marked packages in Figure 17. An acceptable alternative would be the packages marked in Figure 19.


Figure 19: Car/Glass: suboptimal solution

However, apt-get doesn’t find any of these solutions. The tests reported here were performed on CaixaMagica premises using apt for rpm, which uses the very same dependency solver as apt, so the results are transferable to apt in general, but w.r.t. rpm repositories:

sclara:/etc/apt/sources.list.d # apt-get install car
Reading Package Lists... Done
Building Dependency Tree... Done
[...]

The following packages have unmet dependencies: car: Depends: wheel (>= 2) but it is not going to be installed E: Broken packages

This comes from Apt’s choice of always installing the greatest version of a package, that lead it to the following steps

  1. Installed “engine = 2”
  2. Installed “wheel = 3” and for that installed its dependency “tyre = 2”
  3. Tried to install “door”, but before tried to install its dependency “window = 2” but even before tried to install window dependency’s “glass = 2”. Since this last one failed, they all failed.

Quite evidently, Apt does not backtrack to look for one of the two possible solutions.

Scenario 1 - fix “wheel = 3”

Let’s investigate more why apt does not backtrack: we manually install wheel and then door, in this order:

  1. Installed wheel (and apt-get installed well version 3 and tyre = 2)
  2. Tried to install door but apt-get suggest to remove wheel and tyre, before install door + windows + glass (see next output)

The install operation of “door.rpm” asks permission for removing the previous installed packages:

  sclara:/etc/apt/sources.list.d # apt-get install door 
 [...]
The following packages will be REMOVED:
  tyre wheel
The following NEW packages will be installed:
  door glass window

Why apt-get had not tried to install window = 1 and glass = 1?

7.3.2  Scenario 2 - fix “window = 1”

Notice that the installation of the package “window = 1” alone succeds (and it installs also its dependency “glass = 1”), and then we can install door without problems:

  sclara:/etc/apt/sources.list.d # apt-get install door
[..,]
Committing changes...
Preparing...                ############################ [100%]
   1:door                   ############################ [100%]
Done.

7.3.3  Scenario 3 - fix “wheel = 2”

Let’s explore the other possibility: fix “wheel = 2” by directly installing wheel = 2. This operation succeeds and then we can install “car.rpm” and its dependencies:

  Reading Package Lists... Done
Building Dependency Tree... Done
[...]
Do you want to continue? [Y/n] Y
Committing changes...
Preparing...                ############################ [100%]
   1:engine                 ############################ [ 20%]
   2:glass                  ############################ [ 40%]
   3:window                 ############################ [ 60%]
   4:door                   ############################ [ 80%]
   5:car                    ############################ [100%]
Done.

7.3.4  Algorithm specification

The previous tests highlight the following behavior of the Apt:

  1. Check the dependencies of a package.
  2. Try to install dependencies one-by-one in the order they are presented in the RPM.
  3. For each dependency, try to install its sub-dependencies by the greater version presented.
  4. If one subdependency fails by conflict with a package that will be installed (tyre=2 conflicted with glass=2), then the install operation aborts. It does not try to backtrack and check smaller versions (tyre = 1, for instance, or even window = 1).
  5. If one subdependency fails by conflict with a package that is already installed (case where wheel and tyre were installed), then the install prompts for removal of the installed package. It does not try to see if there is alternatives for the conflict package.

This heuristic tends to work well with well-behaviored repositories such as the ones centralized by a commercial distribution. It sacrifies the quality of the solution for the speed of the analysis.

7.3.5  Apt’s surprising behavior.

We have also tested Apt’s behavior on a snapshot of the Debian pool taken in the middle of 2005, and available in the EDOS subversion repository as
Data/Sources/Packages-pool.gz. Of the many tests performed, we retain the following three, which clearly exhibit some of Apt’s limitations.

  • apt-get install abiword-gnome=2.2.7-3 fails
  • apt-get install abiword-gnome=2.2.7-3 abiword-common=2.2.7-3 succeeds
  • apt-get install abiword-common=2.2.7-3 abiword-gnome=2.2.7-3 succeeds, but installs one more package!
First test, failure for abiword-gnome=2.2.7-3
Running apt using fake directory structure /extended/tmp/apt
Populating ...done.
Creating fake configuration file
Creating fake source list file
Updating debian-pool cache
Atteint http://www.pps.jussieu.fr unstable/main Packages
Ign http://www.pps.jussieu.fr unstable/main Release
Lecture des listes de paquets...
Trying to install abiword-gnome=2.2.7-3
Lecture des listes de paquets...
Construction de l’arbre des dépendances...
Certains paquets ne peuvent être installés. Ceci peut signifier
que vous avez demandé l’impossible, ou bien, si vous utilisez
la distribution unstable, que certains paquets n’ont pas encore
été créés ou ne sont pas sortis d’Incoming.

Puisque vous n’avez demandé qu’une seule opération, le paquet n’est probablement pas installable et vous devriez envoyer un rapport de bogue. L’information suivante devrait vous aider à résoudre la situation :

Les paquets suivants contiennent des dépendances non satisfaites : abiword-gnome: Dépend: abiword-common (= 2.2.7-3) mais 2.2.9-1 devra être installé

Second test, success for abiword-gnome=2.2.7-3 abiword-common=2.2.7-3
Running apt using fake directory structure /extended/tmp/apt
Populating ...done.
Creating fake configuration file
Creating fake source list file
Updating debian-pool cache
Atteint http://www.pps.jussieu.fr unstable/main Packages
Ign http://www.pps.jussieu.fr unstable/main Release
Reading Package Lists... Done
Trying to install abiword-gnome=2.2.7-3 abiword-common=2.2.7-3
Reading Package Lists... Done
Building Dependency Tree... Done
The following extra packages will be installed:
  abiword-common abiword-gnome adduser coreutils cpp cpp-4.0 dbus-1 
  dbus-glib-1 debconf debconf-i18n debianutils defoma esound-common file 
  fontconfig gcc-3.3-base gcc-4.0-base gconf2 gnome-keyring gnome-mime-data 
  gsfonts libacl1 libart-2.0-2 libaspell15 libatk1.0-0 libattr1 libaudiofile0
  libbonobo2-0 libbonobo2-common libbonoboui2-0 libbonoboui2-common libbz2-1.0
  libc6 libcap1 libcdparanoia0 libcomerr2 libcupsys2-gnutls10 libdb3
  libdb4.2 libenchant1 libesd0 libexpat1 libfam0c102 libfontconfig1 
  libfreetype6 libfribidi0 libgcc1 libgconf2-4 libgcrypt11 libgdbm3 
  libglade2-0 libglib2.0-0 libgnome-keyring0 libgnome2-0 
  libgnome2-common libgnomecanvas2-0 libgnomecanvas2-common 
  libgnomecups1.0-1 libgnomeprint2.2-0 libgnomeprint2.2-data 
  libgnomeprintui2.2-0 libgnomeprintui2.2-common libgtk2.0-common 
  libgnomeui-0 libgnomeui-common libgnomevfs2-0 libgnomevfs2-common 
  libgnutls11 libgpg-error0 libgtk2.0-0 libgtk2.0-bin libmyspell3
  libgucharmap4 libhal-storage0 libhal0 libice6 libidl0 libjpeg62 
  libkrb53 libldap2 liblocale-gettext-perl liblzo1 libmagic1 
libncurses5 libnewt0.51 libopencdk8 liborbit2 libpam-modules libpam-runtime libpam0g libpango1.0-0 libpango1.0-common libperl5.8 libpng12-0 libpopt0 libsasl2 libslang2 libsm6 libsmbclient libstdc++5 libstdc++6 libtasn1-2 libtext-charwidth-perl libtext-iconv-perl libtext-wrapi18n-perl libtiff4 libx11-6 libxcursor1 libxext6 libxft2 libxi6 libxinerama1 libxml2 libxrandr2 libxrender1 login lsb-base ncurses-bin passwd perl perl-base perl-modules sed shared-mime-info ttf-bitstream-vera ucf whiptail x11-common xlibs-data zlib1g

Suggested packages: abiword-plugins abiword-plugins-gnome abiword-doc xfs cpp-doc cpp-2.95-doc gcc-4.0-locales debconf-doc debconf-utils libterm-readline-gnu-perl libgnome2-perl libqt-perl libnet-ldap-perl libgnome-perl defoma-doc psfontmgr dfontmgr aspell aspell-bin libbz2-dev bzip2 glibc-doc esound libfreetype6-dev rng-tools gnome-icon-theme gnutls-bin krb5-doc krb5-user libpam-doc ttf-kochi-gothic ttf-kochi-mincho ttf-thryomanes ttf-baekmuk ttf-arphic-gbsn00lp ttf-arphic-bsmi00lp ttf-arphic-gkai00mp ttf-arphic-bkai00mp libterm-readline-perl-perl x-window-system-core x-window-system

Recommended packages: abiword-help aspell-en aspell6-dictionary abiword-gtk xfonts-abi x-ttcidfont-conf apt-utils libft-perl libatk1.0-data esound-clients python-xmlbase libglib2.0-data gamin hicolor-icon-theme myspell-en-us myspell-dictionary libgpmg1 libsasl2-modules xml-core perl-doc fam

The following NEW packages will be installed: abiword-common abiword-gnome adduser coreutils cpp cpp-4.0 dbus-1 dbus-glib-1 debconf debconf-i18n debianutils defoma esound-common file fontconfig gcc-3.3-base gcc-4.0-base gconf2 gnome-keyring gnome-mime-data gsfonts libacl1 libart-2.0-2 libaspell15 libatk1.0-0 libattr1 libaudiofile0 libbonobo2-0 libbonobo2-common libbonoboui2-0 libbonoboui2-common libbz2-1.0 libc6 libcap1 libcdparanoia0
libcupsys2-gnutls10 libdb3 libdb4.2 libenchant1 libesd0 libexpat1 libfam0c102 libfontconfig1 libfreetype6 libfribidi0 libgcc1 libgconf2-4 libgcrypt11 libgdbm3 libglade2-0 libglib2.0-0 libcomerr2 libgnome-keyring0 libgnome2-0 libgnome2-common libgnomecanvas2-0 libgnomecanvas2-common libgnomecups1.0-1 libgnomeprint2.2-0 libgnomeprint2.2-data libgnomeprintui2.2-0 libgnomeprintui2.2-common libgnomeui-0 libgnomeui-common libgnomevfs2-0 libgnomevfs2-common libgnutls11 libgpg-error0 libgtk2.0-0 libgtk2.0-bin libgtk2.0-common libgucharmap4 libhal-storage0 libhal0 libice6 libidl0 libjpeg62 libkrb53 libldap2 liblocale-gettext-perl liblzo1 libmagic1 libmyspell3 libncurses5 libnewt0.51 libopencdk8 liborbit2 libpam-modules libpam-runtime libpam0g libpango1.0-0 libpango1.0-common libperl5.8 libpng12-0 libpopt0 libsasl2 libslang2 libsm6 libsmbclient libstdc++5 libstdc++6 libtasn1-2 libtext-charwidth-perl libtext-iconv-perl libtext-wrapi18n-perl libtiff4 libx11-6 libxcursor1 libxext6 libxft2 libxi6 libxinerama1 libxml2 libxrandr2 libxrender1 login lsb-base ncurses-bin passwd perl perl-base perl-modules sed shared-mime-info ttf-bitstream-vera ucf whiptail x11-common xlibs-data zlib1g 0 packages upgraded, 130 newly installed, 0 to remove and 0 not upgraded.

Third test, different success for abiword-common=2.2.7-3 abiword-gnome=2.2.7-3

In this case, Apt will install also libaspell15c2, which is not proposed in the previous example, despite the fact that the commands given by the users differ in the ordering of the arguments.

Running apt using fake directory structure /extended/tmp/apt
Populating ...done.
Creating fake configuration file
Creating fake source list file
Updating debian-pool cache
Atteint http://www.pps.jussieu.fr unstable/main Packages
Ign http://www.pps.jussieu.fr unstable/main Release
Reading Package Lists... Done
Trying to install abiword-common=2.2.7-3 abiword-gnome=2.2.7-3
Reading Package Lists... Done
Building Dependency Tree... Done
The following extra packages will be installed:
  abiword-common abiword-gnome adduser coreutils cpp cpp-4.0 dbus-1 dbus-glib-1
  debconf debconf-i18n debianutils defoma esound-common file fontconfig
  gcc-3.3-base gcc-4.0-base gconf2 gnome-keyring gnome-mime-data gsfonts
  libacl1 libart-2.0-2 libaspell15 libaspell15c2 libatk1.0-0 libattr1
  libaudiofile0 libbonobo2-0 libbonobo2-common libbonoboui2-0
  libbonoboui2-common libbz2-1.0 libc6 libcap1 libcdparanoia0 libcomerr2
  libcupsys2-gnutls10 libdb3 libdb4.2 libenchant1 libesd0 libexpat1 libfam0c102
  libfontconfig1 libfreetype6 libfribidi0 libgcc1 libgconf2-4 libgcrypt11
  libgdbm3 libglade2-0 libglib2.0-0 libgnome-keyring0 libgnome2-0
  libgnome2-common libgnomecanvas2-0 libgnomecanvas2-common libgnomecups1.0-1
  libgnomeprint2.2-0 libgnomeprint2.2-data libgnomeprintui2.2-0
  libgnomeprintui2.2-common libgnomeui-0 libgnomeui-common libgnomevfs2-0
  libgnomevfs2-common libgnutls11 libgpg-error0 libgtk2.0-0 
  libgtk2.0-bin libgtk2.0-common libgucharmap4 libhal-storage0 libhal0 
  libice6 libidl0 libjpeg62 libkrb53 libldap2 liblocale-gettext-perl 
  liblzo1 libmagic1 libmyspell3 libncurses5 libnewt0.51 libopencdk8 
  liborbit2 libpam-modules libpam-runtime libpam0g libpango1.0-0 
  libpango1.0-common libperl5.8 libpng12-0 libpopt0 libsasl2 libslang2 
  libsm6 libsmbclient libstdc++5 libstdc++6 libtasn1-2 
  libtext-charwidth-perl libtext-iconv-perl libtext-wrapi18n-perl 
  libtiff4 libx11-6 libxcursor1 libxext6 libxft2 libxi6
  libxinerama1 libxml2 libxrandr2 libxrender1 login lsb-base 
  ncurses-bin passwd perl perl-base perl-modules sed shared-mime-info 
  ttf-bitstream-vera ucf whiptail x11-common xlibs-data zlib1g

Suggested packages: abiword-plugins abiword-plugins-gnome abiword-doc xfs cpp-doc cpp-2.95-doc gcc-4.0-locales debconf-doc debconf-utils libterm-readline-gnu-perl libgnome2-perl libqt-perl libnet-ldap-perl libgnome-perl defoma-doc psfontmgr dfontmgr aspell aspell-bin libbz2-dev bzip2 glibc-doc esound libfreetype6-dev rng-tools gnome-icon-theme gnutls-bin krb5-doc krb5-user libpam-doc ttf-kochi-gothic ttf-kochi-mincho ttf-thryomanes ttf-baekmuk ttf-arphic-gbsn00lp ttf-arphic-bsmi00lp ttf-arphic-gkai00mp ttf-arphic-bkai00mp libterm-readline-perl-perl x-window-system-core x-window-system

Recommended packages: abiword-help aspell-en aspell6-dictionary abiword-gtk xfonts-abi fam x-ttcidfont-conf apt-utils libft-perl libatk1.0-data esound-clients python-xmlbase libglib2.0-data gamin hicolor-icon-theme myspell-en-us myspell-dictionary libgpmg1 libsasl2-modules xml-core perl-doc

The following NEW packages will be installed: abiword-common abiword-gnome adduser coreutils cpp cpp-4.0 dbus-1 debconf debconf-i18n debianutils defoma esound-common file fontconfig gcc-3.3-base gcc-4.0-base gconf2 gnome-keyring gnome-mime-data gsfonts libacl1 libart-2.0-2 libaspell15 libaspell15c2 libatk1.0-0 libattr1 libaudiofile0 libbonobo2-0 libbonobo2-common libbonoboui2-0 dbus-glib-1 libbonoboui2-common libbz2-1.0 libc6 libcap1 libcdparanoia0 libcomerr2 libcupsys2-gnutls10 libdb3 libdb4.2 libenchant1 libesd0 libexpat1 libfontconfig1 libfreetype6 libfribidi0 libgcc1 libgconf2-4 libgcrypt11 libgdbm3 libglade2-0 libglib2.0-0 libgnome-keyring0 libgnome2-0 libgnome2-common libgnomecanvas2-0 libgnomecanvas2-common libgnomecups1.0-1 libgnomeprint2.2-0 libgnomeprint2.2-data libgnomeprintui2.2-0 libfam0c102 libgnomeprintui2.2-common libgnomeui-0 libgnomeui-common libgnomevfs2-0 libgnomevfs2-common libgnutls11 libgpg-error0 libgtk2.0-0 libgtk2.0-bin libgtk2.0-common libgucharmap4 libhal-storage0 libhal0 libice6 libidl0 libjpeg62 libkrb53 libldap2 liblocale-gettext-perl liblzo1 libmagic1 libmyspell3 libncurses5 libnewt0.51 libopencdk8 liborbit2 libpam-modules libpam-runtime libpam0g libpango1.0-0 libpango1.0-common libperl5.8 libpng12-0 libpopt0 libsasl2 libslang2 libsm6 libsmbclient libstdc++5 libstdc++6 libtasn1-2 libtext-charwidth-perl libtext-iconv-perl libtext-wrapi18n-perl libtiff4 libx11-6 libxcursor1 libxext6 libxft2 libxi6 libxinerama1 libxml2 libxrandr2 libxrender1 login lsb-base ncurses-bin passwd perl perl-base perl-modules sed shared-mime-info ttf-bitstream-vera ucf whiptail x11-common xlibs-data zlib1g 0 packages upgraded, 131 newly installed, 0 to remove and 0 not upgraded.

7.3.6  Conclusions on APT

It is quite clear now that

Apt is not complete:
The first test shows that it does not find a solution for installing abiword-gnome=2.2.7-3, while there are many such solutions.

This is enough to rule it out as a candidate tool for checking installability.

Apt solutions are order-dependent:
The second and third test only differ in the order of the parameters, not their value, yet the solutions found are different. This show that the solution set is order dependent, which is not stated in the documentaiton, and is quite surprising for a user. Nevertheless, this is perfectly consistent with the fact that the depsolver in APT examines dependencies in a left-to-right order. This is actually used on purpose by many packagers to specify dependencies in a preferred order, like in cases where one finds
apache|tomcat5|httpd

which is totally silly in a declarative world, as apache and tomcat5 both provide httpd, but makes perfect sense if order matters, as the maintainer is saying that she prefers apache over tomcat5 and tomcat5 over all other httpd servers.

7.3.7  A sidenote: upgradeability in practice, and a suggestion for the future

Another point we want to stress is the extreme user-unfriendliness of the APT tool in the rare occasions when upgrading or installing one package ends up into a major overhaul of the user installation… Here follows a real-world example recorded by one of the authors of this report during his daily running of his beloved Debian-based machine.

sudo apt-get install  debhelper
Reading Package Lists... Done
Building Dependency Tree... Done
The following extra packages will be installed:
  armagetron armagetron-common autoconf bonobo-activation codebreaker 
  debconf debconf-i18n debconf-utils dialog esound-common fb-music-high 
  fontconfig frozen-bubble-data grepmail gv intltool-debian 
  libaiksaurus-data libaiksaurus0c102 libatk1.0-0 libatk1.0-dev 
  libbonobo-activation4 libbonobo2-0 libbonobo2-common libdb3 
  libdbd-mysql-perl libdbi-perl libeel2-data libesd0 
  libfilehandle-unget-perl libfontconfig1 libforms1 libfreetype6
  libfreetype6-dev libgcc1 libgcrypt1 libgdbm3 libgladexml-perl 
  libglib2.0-0 libglib2.0-dev libgnome-perl libgnutls7 libgsf-1 
  libgtk-imlib-perl libgtk-perl libgtk1.2 libgtk1.2-common libgtk1.2-dbg 
  libhtml-parser-perl libice-dev libice6 libidl0 liblinc1 
  liblocale-gettext-perl liblzo1 libmagick5.5.7 
  libmail-mbox-messageparser-perl libmysqlclient12 libncurses5 
  libncurses5-dev libncursesw5 libnet-daemon-perl libnet-perl libnewt0.51
  libogg-dev libogg0 liborbit2 libpaper1 libplrpc-perl libpng12-0 
  libpopt-dev libpopt0 libsdl-console libsdl-gfx1.2 libsdl-image1.2 
  libsdl-ttf1.2 libsdl-ttf2.0-0 libsdl1.2debian libsdl1.2debian-oss 
  libsm-dev libsm6 libsmpeg0 libssl0.9.7 libstartup-notification0 
  libstdc++5 libt1-5 libtext-charwidth-perl libtext-iconv-perl 
  libtext-wrapi18n-perl libtiff-tools libwmf0.2-7 libwww-perl libx11-6 
  libx11-dev libxaw7 libxaw7-dev libxcursor1 libxext-dev libxext6
  libxft1 libxft2 libxi-dev libxi6 libxml-parser-perl libxml2 libxmu-dev 
  libxmu6 libxmuu-dev libxmuu1 libxp-dev libxp6 libxpm-dev libxpm4 
  libxrandr-dev libxrandr2 libxrender-dev libxrender1 libxt-dev libxt6 
  libxtrap-dev libxtrap6 libxtst-dev libxtst6 libxv-dev libxv1 lyx 
  lyx-common lyx-xforms perl perl-base perl-modules perlmagick pkg-config 
  pm-dev po-debconf render-dev tcl8.4 tcl8.4-dev tktable transfig ucf 
  whiptail x-dev xaw3dg xbase-clients xfig xfree86-common xlibmesa-dri 
  xlibmesa-gl xlibmesa-gl-dev xlibosmesa-dev xlibosmesa4 xlibs xlibs-data 
  xpdf-common

The following packages will be REMOVED: autoconf2.13 frozen-bubble frozen-bubble-lib gconf2 gnomemeeting itk3.1-dev libbonoboui2-0 libbonoboui2-common libdigest-md5-perl libforms0.89 libgconf2-4 libgnome2-0 libgnome2-common libgnomeui-0 libgnomevfs2-0 libgnomevfs2-common libgtk1.2-dev libgtk2.0-0png3 libgtk2.0-dev libmime-base64-perl libpango1.0-dev libsdl-mixer1.2-dev libsdl-perl libsdl-ttf1.2-dev libsdl1.2-dev libsmpeg-dev libstorable-perl nautilus tk8.3-dev tktable-dev x-window-system x-window-system-core xaw3dg-dev xlib6g xlib6g-dev xlibmesa-dev xlibmesa3 xlibosmesa3 xlibs-dev xlibs-pic xpdf xpdf-reader

The following NEW packages will be installed: armagetron-common debconf-i18n fb-music-high fontconfig intltool-debian libaiksaurus-data libaiksaurus0c102 libeel2-data libfilehandle-unget-perl libfontconfig1 libforms1 libgdbm3 libgnutls7 libgsf-1 libice-dev libice6 libidl0 liblzo1 libmagick5.5.7 libmail-mbox-messageparser-perl libmysqlclient12 libncursesw5 libnet-daemon-perl libnewt0.51 libpaper1 libplrpc-perl libsdl-console libsdl-gfx1.2 libsdl-ttf2.0-0 libsm-dev libsm6 libssl0.9.7 libstartup-notification0 libt1-5 libtext-charwidth-perl libtext-wrapi18n-perl libtiff-tools libwmf0.2-7 libx11-6 libx11-dev libxcursor1 libxext-dev libxext6 libxft1 libxft2 libxi-dev libxi6 libxmu-dev libxmu6 libxmuu-dev libxmuu1 libxp-dev libxp6 libxpm-dev libxpm4 libxrandr-dev libxrandr2 libxrender-dev libxrender1 libxt-dev libxt6 libxtrap-dev libxtrap6 libxtst-dev libxtst6 libxv-dev libxv1 lyx-common lyx-xforms pm-dev po-debconf render-dev tcl8.4 tcl8.4-dev ucf x-dev xlibmesa-dri xlibmesa-gl xlibmesa-gl-dev xlibs-data 75 packages upgraded, 80 newly installed, 42 to remove and 858 not upgraded. Need to get 67.1MB of archives. After unpacking 26.9MB will be used. Do you want to continue? [Y/n] n Abort.

It is quite clear that a careful user is not going to let such an upgade go through unless some hint is given by the system that core functionalities like those suggested by x-window-system and x-window-system-core, which the tool wants to remove, will not disappear, but will be properly replaced by some of the 80 new packages whose installation is suggested.

In other terms, next generation depsolvers will need to explain in a reasonable human-readable form the solution they found to the installation or upgrade problem, in order for the user to take an informed action about what they propose to do. This comment is clearly not limited to the APT tool, but extends to all tools we have tested insofar.

7.4  Portage

This tool is different from other Linux distributions since it is inspired from BSD ports system. In this last case, we download the source code, unpack in a directory (e.g. /usr/port) and compile it. Portage allows you to update your package tree over the internet with emerge -u world command. Or you can download only the packages with emerge –sync.

But Portage is also a package building and installation system. We can compile and install and application with the command emerge package.

When tested on the Car/Glass package tree (Package build and tests for Portage had been done by Mário Morgado from Caixa Mágica team), Portage fails to install the packages and blocks on the following conflicts:

z10n cm-test # emerge -pv --tree  cm-test/car

These are the packages that I would merge, in reverse order:

Calculating dependencies ...done! [blocks B ] =cm-test/tyre-2 (is blocking cm-test/glass-2) [ebuild N ] cm-test/car-1 0 kB [1] [ebuild N ] cm-test/door-2 0 kB [1] [ebuild N ] cm-test/window-2 0 kB [1] [ebuild N ] cm-test/glass-2 0 kB [1] [ebuild N ] cm-test/wheel-3 0 kB [1] [ebuild N ] cm-test/tyre-2 0 kB [1] [ebuild N ] cm-test/engine-2 0 kB [1]

Total size of downloads: 0 kB

Scenario 1 - fix “wheel = 3”

We can then try to help Protage by installing wheel-3 before installing the door package.

 
z10n ~ # emerge -pv cm-test/wheel

These are the packages that I would merge, in order:

Calculating dependencies ...done! [ebuild N ] cm-test/tyre-2 0 kB [1] [ebuild N ] cm-test/wheel-3 0 kB [1]

The marked packages are now installed (Figure 20).


Figure 20: Graph of wheel-3 installed

If we try to install the door package:

  z10n ~ # emerge -pv  cm-test/door

These are the packages that I would merge, in order:

Calculating dependencies ...done! [blocks B ] =cm-test/tyre-2 (is blocking cm-test/glass-2) [ebuild N ] cm-test/glass-2 0 kB [1] [ebuild N ] cm-test/window-2 0 kB [1] [ebuild N ] cm-test/door-2 0 kB [1]

Total size of downloads: 0 k

Portage fails again to find a solution because it does not solve the glass-2 vs tyre-2 conflict.

Scenario 1 - fix “window = 1”

Let’s install window-1 before the other packages:

  z10n ~ # emerge -pv =cm-test/window-1 

These are the packages that I would merge, in order: Calculating dependencies ...done! [ebuild N ] cm-test/glass-1 0 kB [1] [ebuild N ] cm-test/window-1 0 kB [1] Total size of downloads: 0 kB

Glass-1 and window-1 are installed (Figure 21).


Figure 21: Graph of glass-1 and window-1 installed

We can then install door:

 
z10n ~ # emerge -pv cm-test/door These are the packages that I would merge, in order:

Calculating dependencies ...done! [ebuild U ] cm-test/glass-2 [1] 0 kB [1] [ebuild U ] cm-test/window-2 [1] 0 kB [1] [ebuild N ] cm-test/door-2 0 kB [1]

Total size of downloads: 0 kB

The installation occurs without problems, and an upgrade of the dependencies (glass and window) is performed. This is different from the Apt algorithm behavior.

Installation of car would fail as in the first step since it would conflict with tyre-2.

Scenario 1 - fix “wheel = 2”

This scenario is not worth testing since in last section we discover that all the dependencies are updated as well. The installation of car will always lead to an update to wheel-3 and the conflict would remain.

7.4.1  Conclusions on Portage

Even without looking at the source code, it is quite clear that the Portage algorithm for finding a solution of an installation problem goes along the following lines:

  1. List the dependencies of a package.
  2. Try to install dependencies one-by-one in the order they are presented in the ebuild package . If the dependency has an update, update it.
  3. For each dependency, try to install its sub-dependencies by the greater version presented.
  4. If one subdependency fails by conflict with a package that will be installed (tyre=2 conflicted with glass=2), then the install operation aborts. It does not try to backtrack and check smaller versions (tyre = 1, for instance, or even window = 1).
  5. If one subdependency fails by conflict with a package that is already installed (case where wheel and tyre were installed), then the install exit with a failure message.

It is clear that Portage’s solver is not complete.

7.5  SMART

Smart is a package management system meta tool that offers some advanced features with respect to package dependency management and installation.

Smart does not depend on any particular package management system but it uses a plugin system for defining backends that will take care of using a particular package storage management system in order to perform package-related operations. Every backend can use one or several channels in order to retrieve the needed packages. Channels can be of different types (e.g., HTTP, FTP or local repositories) and abstract the differences among the packages retrieval mechanisms.

Smart uses the notion of transaction in order to compute a particular set of operations necessary to perform an operation (e.g., installation or upgrade) on a given set of packages. Differently to many other package management meta system that do not make any effort to explore, even partially, the space of the possible solutions with respect to a given target operation, Smart tries to do so and tries to pick the “best” possible solution in that space.

The notion of “best” solution is given by a policy that weights the found solutions and allows Smart to choose the most suitable one with respect to the chosen policy. There are several predefined policies such as “remove the least number of packages” or “upgrade the most number of packages with the less impact”, etc. Other policies can be plugged in Smart by extending the relevant classes.

Smart has been proven to been an effective tools that is able to gracefully handle package operations on client installed distributions.

By trying to obtain an optimal solution, Smart explores the solution space which is potentially huge, using some heuristics to avoid getting lost in such exploration.

7.5.1  Smart on the Car/Glass testbench

We use again the RPM repository with the Car/Glass packages, and create a Smart in order to perform the tests.

Updating cache...               #### [100%]

Fetching information for 'Repositorio Local'... -> http://localhost/testRPMs/base/release release #### [ 33%] -> http://localhost/testRPMs/base/release.car -> http://localhost/testRPMs/base/pkglist.car.bz2 pkglist.car.bz2 #### [ 66%] release.car #### [100%] Updating cache... #### [100%]

Channels have 9 new packages: door-1-0@i586 engine-1-0@i586 glass-1-0@i586 turbo-1-0@i586 tyre-1-0@i586 tyre-2-0@i586 wheel-3-0@i586 window-0-0@i586 window-1-0@i586

Saving cache...

The result of the command smart install car is:

  Computing transaction...
Installed packages (4):
  car-2-0@i586      door-1-0@i586     engine-2-0@i586   wheel-2-0@i586 
7.8kB of package files are needed.

Smart has solved the conflicts and installed car package in the first attempt. The chosen packages for installation are a interesting set as we can see in Figure 22. Every “branch” that had a conflict with another branch was excluded and an older version of the package was used.

The wheel-3 package was not installed and wheel-2 was prefered. The same for door-1.


Figure 22: Graph of packages installed by Smart for car.

The solution was not optimal because a newer version of wheel (version 3) could be installed without conflict. As in alternative, “door-2” could be installed.

Let’s check some other scenarii.

Scenario 1 - fix “wheel = 3”

In this scenario we will install first the wheel-3. This will freeze that branch.

Smart installed the newer versions since no conflict was present:

  Computing transaction...
Installed packages (2):
  tyre-2-0@i586     wheel-3-0@i586 

We then tryed to install the car package:

Computing transaction...
Installed packages (3):
  car-2-0@i586      door-1-0@i586     engine-2-0@i586 
5.8kB of package files are needed.

Smart installed the package by guessing well that the only version possible was door-2.

Scenario 2 - fix “window = 1”

Now we forced the installation of window-1 and Smart installed it and its dependency, glass-1.

Now we try to install car. The expected behaviour was the installation of wheel-3 since no conflict was expected. Smart had a strange behaviour here and installed wheel-2. It was not necessary.

Scenario 3 - fix “wheel = 2”

Starting by installing wheel-2 Smart could install door-2 but in fact it had not. It just installed door-1 like it had detected that door-2 had a “possible” conflict.

7.5.2  Smart Algorithm

These tests already highlight part of the behevior of Smart’s algorithm:

  1. Check the dependencies of a package.
  2. Try to install dependencies one-by-one.
  3. For each dependency, try to install its sub-dependencies by the greater version presented. If the greater version has a conflict with a known package (even if the version with the conflict will not be installed) than try to install an older version of the dependency.

Unlike the previous tools, Smart does try to backtrack and choose older versions of a package when a conflict is found during the state-space exploration. Nevertheless, the backtracking system is not guaranteed to find an optimal solution, as we have seem in the previous examples.

7.5.3  Combinatorial explosion

Unfortunately, when performing server-side operations, such as checking the consistency of package bases at the distribution source, the solution space is much bigger than in the average use-case on a client installation, and Smart is unable to find a solution in an acceptable (or even practically finite) time for a significant number of packages.

We verified this limitation by setting up a package base that comprises the whole Debian Pool, and asking Smart to install a given package starting on an empty system. Here are two examples

23576s = 6h30 to check installability of php3
 /usr/bin/time smart –data-dir=/ext/tmp/smart install 
                     –urls php3
 Loading cache...
 Updating cache...               ##################### [100%]
 Computing transaction...
 /pool/main/libg/libgcrypt11/libgcrypt11_1.2.1-4_i386.deb
 /pool/main/a/apache/apache-common_1.3.33-7_i386.deb
 /pool/main/o/openssl/libssl0.9.7_0.9.7g-1_i386.deb
 …
  23576.80user 6h30 8.71system 13:09:13elapsed 49%CPU 
 
Two months are not enough to check installability of achims-guestbook
 /usr/bin/time smart –data-dir=/ext/tmp/smart install 
                     –urls achims-guestbook
 Loading cache...
 Updating cache...               ##################### [100%]
 Computing transaction...
 ^C
 

This computation has been stopped two months after being started, without ever returning a solution.

7.5.4  Conclusions on Smart

Smart is up to now the best tool in terms of completeness among the ones we have analysed, even if we have shown that the solutions provided by this tool are not necessarily optimal from a user’s point of view.

We cannot say anything conclusive about completeness or soundness either: on one side, the depsolver algorithm, using the predefined policies, is only available as Python source code, and not formally described, so we could not really check its correctness; on the other side its explosive behavior has prevented us from being able to collect experimental evidence of its completeness (or incompleteness).

Nevertheless, the combinatorial explosion exposed by the two tests above is of course reason enough to rule out Smart as a possible candidate tool for checking installability: our tool must handle dozens of thousands of packages, and cannot spend an unbounded amount of time on checking installability for just one of them.

7.6  URPMI

Urpmi is the depsolver used in the Mandriva distribution; this section contains a description of its inner working as presented by the maintainer of Urpmi himself.

7.6.1  Algorithms used

Basically urpmi constructs a dependency tree from a set of demanded modules. It begins to load the dependency tree for the known set of packages available in its repositories; then a simple tree-walk algorithm is used to gather all required packages. urpmi being an interactive tool, it is able to propose different sets of packages than can solve the set of requirements for the demanded modules. For example, to solve a dependency on "webfetch" urpmi can use the "curl" or the "wget" package, so it will ask the user for it.

The dependencies can be versioned, so urpmi maintains a range of acceptable versions for each dependency, narrowing them down when the tree walk progresses.

When urpmi encounters a conflict (either because it is a conflict explicitly marked in the package, or because two packages A and B require another package C with non-overlapping version requirements), it backtracks in the dependency tree and tries another path.

7.6.2  Upgradeability in practice

Given a list of arguments (packages to be installed or upgraded), urpmi produces deterministic results. urpmi will never downgrade a package. So, if asked to install a package A that requires an older package B than the B currently installed on the system, it will abort. Some rare situations can make urpmi hang in an infinite loop. urpme, a counterpart to urpmi, is used to remove packages, and all packages that depend on them recursively.

7.6.3  Notes on implementation

urpmi is written mostly in Perl 5 (about 10,000 lines of code), with a small part in C, used to bind it to the API of the RPM library.

7.6.4  Examples

Here’s a simple example of urpmi installing a new package, taking care of conflicts and broken dependencies:

sudo urpmi libdb4.2-static-devel
The following packages have to be removed for others
      to be upgraded:
libdb4.1-devel-4.1.25-9mdk.i586
 (due to conflicts with libdb4.2-devel)
libdb4.1-static-devel-4.1.25-9mdk.i586
 (due to unsatisfied db4.1-devel == 4.1.25-9mdk) (y/N) y
To satisfy dependencies, the following packages are going
      to be installed:
libdb4.2-devel-4.2.52-9mdk.i586
libdb4.2-static-devel-4.2.52-9mdk.i586
Proceed with the installation of the 2 packages? 
      (43 MB) (Y/n) y
installing libdb4.2-static-devel-4.2.52-9mdk.i586.rpm
           libdb4.2-devel-4.2.52-9mdk.i586.rpm
           from /var/cache/urpmi/rpms
removing libdb4.1-static-devel-4.1.25-9mdk.i586
         libdb4.1-devel-4.1.25-9mdk.i586
Preparing...                     ####################
      1/2: libdb4.2-devel        ####################
      2/2: libdb4.2-static-devel ####################

7.6.5  urpmi on the Car/Glass testbench

We use the same RPM repository as before to perform the tests. A naive approach is to tell urpmi to install all the packages in this repository.

Passing all the rpm as arguments

urpmi *.rpm

Some package requested cannot be installed: door-2-0.i586 (due to missing window-2-0.i586) engine-1-0.i586 glass-2-0.i586 tyre-1-0.i586 wheel-3-0.i586 window-0-0.i586 window-2-0.i586 (due to unsatisfied glass[== 2]) Continue? (Y/n) installing glass-1-0.i586.rpm window-1-0.i586.rpm wheel-2-0.i586.rpm engine-2-0.i586.rpm tyre-2-0.i586.rpm car-2-0.i586.rpm door-1-0.i586.rpm turbo-1-0.i586.rpm Preparing... 1/8: door warning: user prrt does not exist - using root 2/8: engine warning: user prrt does not exist - using root 3/8: wheel warning: user prrt does not exist - using root 4/8: glass warning: user prrt does not exist - using root 5/8: window warning: user prrt does not exist - using root 6/8: tyre warning: user prrt does not exist - using root 7/8: car warning: user prrt does not exist - using root 8/8: turbo warning: user prrt does not exist - using root

The result is basically the same as the one we obtained previously with smart when installing the car from the repository. urpmi solves the conflicts and installs car at the first attempt. However, it does not find the optimum solution. It discarded wheel-3 and also door-2 which are the only 2 branches leading with a potential conflict (Figure 23).


Figure 23: Car/Glass: Graph of the packages installed when passed as arguments to urpmi.

However, this test is far from being representative of a package installation in the real world. To be fair, a RPM repository must be created with a hdlist for urpmi. This is what we are doing in the next section.

Using a repository

First we need to create the repository before we can use it. Then we will try to install car without giving any more clue to urpmi to see what it can find by itself.

genhdlist

urpmi.addmedia wp2d2-car_test . with hdlist.cz

added medium wp2d2-car_test wrote config file [/etc/urpmi/urpmi.cfg] examining synthesis file [/var/lib/urpmi/synthesis.hdlist.The Ultimate Linux Desktop DVD (Mandriva 2006 Powerpack (local) 1).cz] copying source hdlist (or synthesis) of "wp2d2-car_test"? ...copying done /bin/cp: cannot stat ‘/home/EDOS/RPMS.car/pubkey’: No such file or directory ...copying failed examining hdlist file [/var/cache/urpmi/partial/hdlist.wp2d2-car_test.cz] writing list file for medium "wp2d2-car_test" (...) built hdlist synthesis file for medium "wp2d2-car_test" found 0 headers in cache removing 0 obsolete headers in cache wrote config file [/etc/urpmi/urpmi.cfg]

The repository is built and registered with the client (eg. the user laptop) with no particular problem except that urpmi.addmedia complains about a file we did not provide but which is not relevant for this experiment (a pgp key for security checking).

Now, let’s try to install the car package.

urpmi car

To satisfy dependencies, the following 7 packages are going to be installed (0 MB): car-2-0.i586 door-2-0.i586 engine-2-0.i586 glass-2-0.i586 tyre-2-0.i586 wheel-3-0.i586 window-2-0.i586 Is this OK? (Y/n) installing tyre-2-0.i586.rpm wheel-3-0.i586.rpm door-2-0.i586.rpm glass-2-0.i586.rpm window-2-0.i586.rpm engine-2-0.i586.rpm car-2-0.i586.rpm from /home/EDOS/RPMS.car/. Installation failed: tyre = 2 conflicts with glass-2-0.i586

Now urpmi is selecting correctly wheel-3 and door-2 but it is failling to install them altogether with the car because it detected the conflict between tyre-2 and glass-2. It appears that urpmi selects always all the freshest versions and it does not backtrack for example to choose tyre-1 instead of tyre-2.

urpmi fails in installing the car directly. Let’s try to find alternative scenarios to remedy this situation. That will also let us see how urpmi behaves with different pre-existing installations.

Scenario 1 - Trying to install tyre-1 first

Knowing the best solution in advance, let’s start by installing tyre-1 and see if it helps urpmi to find this optimum installation.

urpmi tyre-1

installing tyre-1-0.i586.rpm from /home/EDOS/RPMS.car/. Preparing... 1/1: tyre warning: user prrt does not exist - using root

urpmi car

To satisfy dependencies, the following 7 packages are going to be installed (0 MB): car-2-0.i586 door-2-0.i586 engine-2-0.i586 glass-2-0.i586 tyre-2-0.i586 wheel-3-0.i586 window-2-0.i586 Is this OK? (Y/n) installing tyre-2-0.i586.rpm wheel-3-0.i586.rpm door-2-0.i586.rpm glass-2-0.i586.rpm window-2-0.i586.rpm engine-2-0.i586.rpm car-2-0.i586.rpm from /home/EDOS/RPMS.car/. Installation failed: tyre = 2 conflicts with glass-2-0.i586

It does not solve the problem at all, because urpmi tries to be too smart by upgrading tyre to the latest version, and this is just what we intended to avoid. Unfortunately, it does try to upgrade tyre here and it fails to install again, for the same reason as before.

Scenario 2 - Trying to install window-1 first

urpmi did not use our clue when we installed tyre-1 first, let’s see what it does when we try to install window-1 first, and then the car.

urpmi window-1

To satisfy dependencies, the following 2 packages are going to be installed (0 MB): glass-1-0.i586 window-1-0.i586 Is this OK? (Y/n) installing glass-1-0.i586.rpm window-1-0.i586.rpm from /home/EDOS/RPMS.car/. Preparing... 1/2: glass warning: user prrt does not exist - using root 2/2: window warning: user prrt does not exist - using root

urpmi car

To satisfy dependencies, the following 5 packages are going to be installed (0 MB): car-2-0.i586 door-2-0.i586 engine-2-0.i586 tyre-2-0.i586 wheel-3-0.i586 Is this OK? (Y/n) installing tyre-2-0.i586.rpm wheel-3-0.i586.rpm door-2-0.i586.rpm engine-2-0.i586.rpm car-2-0.i586.rpm from /home/EDOS/RPMS.car/. Preparing... 1/5: engine warning: user prrt does not exist - using root 2/5: door warning: user prrt does not exist - using root 3/5: tyre warning: user prrt does not exist - using root 4/5: wheel warning: user prrt does not exist - using root 5/5: car warning: user prrt does not exist - using root

Success! This time urpmi installs everything and it reaches the optimum installation (Figure 17). With reason it did not try to upgrade the window.

Scenario 3 - Trying to install wheel-2 first

Let’s repeat the experiment, this time by installing wheel-2 first.

urpmi wheel-2

installing wheel-2-0.i586.rpm from /home/EDOS/RPMS.car/. Preparing... 1/1: wheel warning: user prrt does not exist - using root

urpmi car

To satisfy dependencies, the following 5 packages are going to be installed (0 MB): car-2-0.i586 door-2-0.i586 engine-2-0.i586 glass-2-0.i586 window-2-0.i586 Is this OK? (Y/n) installing door-2-0.i586.rpm glass-2-0.i586.rpm window-2-0.i586.rpm engine-2-0.i586.rpm car-2-0.i586.rpm from /home/EDOS/RPMS.car/. Preparing... 1/5: engine warning: user prrt does not exist - using root 2/5: glass warning: user prrt does not exist - using root 3/5: window warning: user prrt does not exist - using root 4/5: door warning: user prrt does not exist - using root 5/5: car warning: user prrt does not exist - using root

Another success, but this time urpmi did not reach the optimum installation as shown in Figure 24. It detected a conflict with the wheel-3 and tyre-2 and it did not backtrack to find a better solution with tyre-1 instead.


Figure 24: Car/Glass: Graph of the installation obtained by urpmi with Scenario 3.

7.6.6  Conclusions on Urpmi

urpmi finds the same solutions as smart in the first attempt when it is given the complete list of RPM packages as command line parameters. However, it fails when relying on the repository hdlist only. When starting with a partially installed environment in Scenarii 2 and 3, it has a good solution comparable to smart.

For the overall problem, urpmi seems to have the same performance of apt. It cannot backtrack and solve the conflict problem.

Interestingly, in the alternative scenarios explored with different pre-existing installations, urpmi out-performs smart, however it does only find the optimum solution once out of 3, and it fails in one situation.

As it is evident in this presentation, urpmi does not try to be complete, as a depsolver, and for this reason it cannot be used for maintaining distributions on the server side, where we need to check installability of every single package.

7.7  Conclusions

The problem of finding an optimal installation candidate, w.r.t. some criteria, is computationally hard and is treated differently by different tools.

Some rely on special heuristics, like Apt, Portage and Urpmi, that perform reasonably well on well-behaved repositories, and ensure that an answer will be reported in a limited time, but at the price of giving up completeness, which means failing to find an installation candidate when it is located too far from the solution suggested by the heuristics.

Others, like Smart, strive to be complete, and really try to explore the solution space, using some special heuristic to try and limit the effect of the combinatorial explosion of the solution space, but at the price of having unacceptably high computation times on some cases; as we have seen, the solution found is not necessarily always optimal either.

We conclude that none of these tool is adapted to checking installability on the server-side, to guarantee quality of a distribution, either because of incompleteness (Apt, Portage, Urpmi), or because of complexity (Smart), and we have hence built our own tools, which are soundly based on formal methods, are complete and perform extremely well on the real-world cases.

The content of this chapter should in no way be construed as a criticism of the tools we analysed: they do try to solve a much harder problem than ours, and they really try their best at it, handling all the added complexity of the extra bits of metadata associated to package management: we know of no satisfactory solution for this problem up to now, and our tools are not a replacement for Apt, Protage, Urpmi, Smart and the like.

Nevertheless, we do hope that the detailed analysis presented here will help the designers of future generation client-side package management meta-tools in their quest of the best tradeoff between efficiency and completeness.