Analysis of some package management tools

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

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

scn1sol1.png
Figure 7.1: Graph of car dependencies and con?icts.

scn1sol2.png
Figure 7.2: Car/Glass: optimum solution (maximum number of latest versions).

For each of these tools, we performed the very same tests on a specially built package base, shown in ?gure 7.1, 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.

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

For information, the WP2 toolchain statistics are available online at the following URL: http://www.edos-project.org/xwiki/stats/car.html . The graphic representation is inserted below.

car-graph.png
Graphic representation of the car repository generated with the EDOS Visualizer

The analysis shows that no system is able to ?nd the best solution, 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, ?nding 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.

apt

smart

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.

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 accept- able versions for each dependency, narrowing them down when the tree walk pro- gresses.

When urpmi encounters a con?ict (either because it is a con?ict 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.

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 in?nite loop.

urpme, a counterpart to urpmi, is used to remove packages, and all packages that depend on them recursively.

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.

Examples

Here?s a simple example of urpmi installing a new package, taking care of con?icts 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 ####################

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
##############warning: user prrt does not exist - using root
###############################
      2/8: engine                warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################
      3/8: wheel                 warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################
      4/8: glass                 warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################
      5/8: window                warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################
      6/8: tyre                  warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################
      7/8: car                   warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################
      8/8: turbo                 warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################

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.

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
##############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 not try not to upgrade tyre. Finally it fails to install again, and 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
##############warning: user prrt does not exist - using root
###############################
      2/2: window                warning: user prrt does not exist - using root
##############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
##############warning: user prrt does not exist - using root
###############################
      2/5: door                  warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################
      3/5: tyre                  warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################
      4/5: wheel                 warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################
      5/5: car                   warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################

Success! This time urpmi installs everything and it reaches the optimum installation. With reason it did not try to upgrade 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
##############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
##############warning: user prrt does not exist - using root
###############################
      2/5: glass                 warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################
      3/5: window                warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################
      4/5: door                  warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################
      5/5: car                   warning: user prrt does not exist - using root
##############warning: user prrt does not exist - using root
###############################

Another success, but this time urpmi did not reach the optimum installation. 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.

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.

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 dep-solver, 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.

Version 1.17 last modified by MarcLijour on 02/04/2006 at 20:11

Comments 0

No comments for this document

Attachments 11

BIN
hdlist.cz 1.1
PostedBy: MarcLijour on 02/04/2006 (3kb )
BIN
synthesis.hdlist.cz 1.1
PostedBy: MarcLijour on 02/04/2006 (339 bytes )
XML
statistics.xml 1.1
PostedBy: MarcLijour on 02/04/2006 (7kb )
BIN
statistics 1.2
PostedBy: MarcLijour on 02/04/2006 (628 bytes )
BIN
car.gml 1.1
PostedBy: MarcLijour on 02/04/2006 (5kb )
BIN
names 1.1
PostedBy: MarcLijour on 02/04/2006 (196 bytes )
BIN
result.info 1.1
PostedBy: MarcLijour on 02/04/2006 (114 bytes )
HTML
car.html 1.1
PostedBy: MarcLijour on 02/04/2006 (16kb )
Image
scn1sol1.png 1.1
PostedBy: MarcLijour on 02/04/2006 (15kb )
Image
scn1sol2.png 1.1
PostedBy: MarcLijour on 02/04/2006 (15kb )
Image
car-graph.png 1.1
PostedBy: MarcLijour on 02/04/2006 (110kb )
Creator: on 2006/04/02 02:37
Copyright EDOS Consortium
1.1.1