On year ago, we (the mancoosi team) published a comparison study regarding the state of the art of dependency solving in debian. As few noticed, the data presented had few glitches that I promised to fix. So we’ve repeated our tests using exactly the same data we used one year ago, but now using the latest available versions of all package managers as available in debian unstable.

During the last year, three out of four solver that we evaluated release a major upgrade so I expected many improvements in performances and accuracy.

• apt-get 0.8.10 -> 0.9.7
• aptitude 0.6.3 -> 0.6.7
• smart 1.3-1 -> 1.4
• cupt 1.5.14.1 -> 2.5.6

Mpm, our test-bench for new technologies, changed quite a bit under the wood as a consequence of the evolution of apt-cudf and the recent work done in apt-get to integrate external cudf dependency solvers.

Overall the results of our study are not changed. All solvers but mpm, that is based on aspcud, are not scalable as the number of packages (and alternatives) grows. It seems that Smart is the solver that does not give up, incurring in a timeout (fixed at 60 seconds) most of the time. Aptitude is the solver that tried to give you a solution, doesn’t matter what and as result providing solutions that do not satisfy the user request for one reason or the other. Apt-get does surprisingly well, but it gives up pretty often showing the incomplete nature of it’s internal solver. Cupt sometimes timeout, sometimes gives up, but when it is able to provide an answer it is usually optimal and it is very fast … Mpm consistently finds an optimal solution, but sometimes it takes really a long time to do it. Since mpm is written in python and not optimized for speed this is not a big problem for us. The technology used by mpm is now integrated in apt-get and I hope this will alleviate this problem.

All the details of our study can be found one the Mancoosi Website as usual with a lot of details. For example here you can find the results when mixing four major releases : sarge-etch-lenny-squeeze.

Comments are more then welcome.

Recently, all relevant packages needed to run mpm (the mancoosi package manager) landed in debian (thanks ralf and zack !). Now it should be a tad easier to run mpm and to play with it. The code of mpm is available on the mancoosi svn repository (user/pass : mancoosi/mancoosi) . To run it, you also need to install python-apt.

These are all cudf solvers you can use as mpm backends. They use different solving techniques and were implemented for the MISC competition : mccs packup * aspcud

In addition, you need the CUDF solver integration for APT / MPM , that is the component in charge of translating the apt/mpm installation problem to cudf and to provide a solution back to apt/mpm * apt-cudf

The last (optional) component is the dudf-save that allows you to report an installation problem back to us . mancoosi contest (dudfsave) is avalaible for download at http://mancoosi.debian.net/

the mpm command line is still not very user friendly, but since it is not meant to be used by final users or production systems, I think I’ll not spend too much time to add all bells and whistles.

enjoy.

One of our paper has been accepted to The 14th International ACM SIGSOFT Symposium on Component Based Software Engineering (CBSE-2011) happening in June in Boulder, Colorado, USA. This is a joint work with Roberto Di Cosmo, Ralf Treinen and Stefano Zacchiroli.

Abstract

Software distributions in the FOSS world rely on so-called package managers for the installation and removal of packages on target machines. State-of-the-art package managers are monolithic in architecture, and each of them is hard-wired to an ad-hoc dependency solver implementing a customized heuristics. In this paper we propose a modular architecture allowing for pluggable dependency solvers and backends. We argue that this is the path that leads to the next generation of package managers that will deliver better results, accept more expressive input languages, and can be easily adaptable to new platforms. We present a working prototype—-called MPM—-which has been implemented following the design advocated in this paper.

More details about the paper are available here

UPDATE

Ralf (that went all the way to the US to present the paper) has just informed us that the paper won the ‘ACM Sigsoft Distinguished Paper Award’ !!!!!!!!

After a bit of work, today I decided to start using mpm, the mancoosi package manager, to upgrade my laptop. My first use of it on a production system - until now I run all my experiments in throw-away virtual machines - and it works !

Not rocket science here. During the last month David Kalnischkies (of APT fame) visited our offices in Paris and together with zack worked out a communication protocol between apt-get and the mancoosi cudf solvers (EDSP). I guess somebody is going to announce all details about this endeavor soon. This cooperation enabled us to advance in the integration of apt-get and the mancoosi technology.

Reusing the same protocol, and backend I developed to translate the apt problem to cudf (and to call a suitable solver), I’ve re-wrote large part of mpm and added the possibility to generate the installation plan before calling dpkg and really installing the selected packages.

Below notice the intermediate calls as Inject Model , Simulate, Compare Models . These are at the moment stubs that are going to call the simulation framework developed at mancoosi.

The food :

abate@zed.fr:~/Projects/git-svn-repos/mpm$sudo ./mpm.py -c mpm.conf update
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Inject Model ...


abate@zed.fr:~/Projects/git-svn-repos/mpm$sudo ./mpm.py -c mpm.conf upgrade
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following new packages will be installed:
libtracker-client-0.8-0 libnet-ip-perl libio-socket-ssl-perl libasyncns0 libapr1 
5 to install
Simulate
Proceed ? yes/[no] 
yes
Reading package fields... Done
Reading package status... Done
Retrieving bug reports... Done
Parsing Found/Fixed information... Done
Reading changelogs... Done
apt-listchanges: Mailing root: apt-listchanges: changelogs for zed
Reading package fields... Done
Reading package status... Done
Retrieving bug reports... Done
Parsing Found/Fixed information... Done
Reading changelogs... Done
apt-listchanges: Mailing root: apt-listchanges: changelogs for zed
(Reading database ... 179534 files and directories currently installed.)
Preparing to replace libapr1 1.4.2-8 (using .../libapr1_1.4.4-1_amd64.deb) ...
Unpacking replacement libapr1 ...
Preparing to replace libasyncns0 0.8-1 (using .../libasyncns0_0.8-2_amd64.deb) ...
Unpacking replacement libasyncns0 ...
Preparing to replace libio-socket-ssl-perl 1.40-1 (using .../libio-socket-ssl-perl_1.43-1_all.deb) ...
Unpacking replacement libio-socket-ssl-perl ...
Preparing to replace libnet-ip-perl 1.25-2 (using .../libnet-ip-perl_1.25-3_all.deb) ...
Unpacking replacement libnet-ip-perl ...
Preparing to replace libtracker-client-0.8-0 0.8.17-2 (using .../libtracker-client-0.8-0_0.8.18-1_amd64.deb) ...
Unpacking replacement libtracker-client-0.8-0 ...
Processing triggers for man-db ...
Setting up libapr1 (1.4.4-1) ...
Setting up libasyncns0 (0.8-2) ...
Setting up libio-socket-ssl-perl (1.43-1) ...
Setting up libnet-ip-perl (1.25-3) ...
Setting up libtracker-client-0.8-0 (0.8.18-1) ...
localepurge: Disk space freed in /usr/share/locale: 0 KiB
localepurge: Disk space freed in /usr/share/man: 0 KiB
localepurge: Disk space freed in /usr/share/gnome/help: 0 KiB
localepurge: Disk space freed in /usr/share/omf: 0 KiB

Total disk space freed by localepurge: 0 KiB

localepurge: Disk space freed in /usr/share/locale: 0 KiB
localepurge: Disk space freed in /usr/share/man: 0 KiB
localepurge: Disk space freed in /usr/share/gnome/help: 0 KiB
localepurge: Disk space freed in /usr/share/omf: 0 KiB

Total disk space freed by localepurge: 0 KiB

Inject Model ...
Compare Models ...
abate@zed.fr:~/Projects/git-svn-repos/mpm$

Reg the installation plan, this is an xml file that will be passed to a simulator developed by the university of L’Aquila to make sure that the installation script (well, a model of them), will not cause any problem during the installation.

The format is a very simple xml file as follows :

<selectionStates>
 <selectionState type="Install"> 
  <param name="package" value="libapr1" />
  <param name="version" value="1.4.4-1" /> 
  <param name="architecture" value="amd64" />
 </selectionState>
 <selectionState type="Install">
  <param name="package" value="libasyncns0" />
  <param name="version" value="0.8-2" />
  <param name="architecture" value="amd64" />
 </selectionState>
 <selectionState type="Install">
  <param name="package" value="libio-socket-ssl-perl" />
  <param name="version" value="1.43-1" />
  <param name="architecture" value="all" />
 </selectionState>
[...]

Soon APT will ship a patch to use the very same infrastructure of mpm (yeii !!!). This will on one hand make mpm useless as package manager on its own. It is a simple hack in python and I never tough to compete with its big brothers. On the other hand I think it will stand as a nice workbench to experiment with new ideas, to prototype new features and to make it easier for poeple that are not c++ experts to play with the APT library (thanks to python-apt) in a semi structured environment. The code is in the mancoosi svn if you want to have a look.

Here at mancoosi we have been working for quite a while to promote and advance solver technology for FOSS distributions. We are almost at the end of the project and it is important to make the mancoosi technology relevant for the community. On goal of the project is to provide a prototype that uses part of the results of mancoosi that can based to install/remove/upgrade packages on a user machine. We certainly don’t want to create yet another meta installer. This would be very time consuming and certainly going beyond the scope of the project. The idea is to create a prototype, that can work as an apt-get drop in replacement that will allow everybody to play with different solvers and installation criteria.

A very first integration step is a small shell script apt-mancoosi that tries to put together different tools that we have implemented during the project. Roberto wrote extensively about his experience with apt-mancoosi a while ago showing that somehow the mancoosi tools are already usable, as proof of concept, to experiment with all solvers participating to the Misc competition.

On notable obstacle we encountered with apt-mancoosi is how to pipe the result of an external solver to apt-get to effectively install the packages proposed as solution. Apt-mancoosi fails to be a drop-in replacement for apt-get exactly for this reason.

The “problem” is quite simple : The idea at the beginning was to pass to apt-get, on the command line, a request that effectively represents a complete solution. We expected that, since this was already a locked-down solution, apt-get would have just installed all packages without any further modification to the proposed installation set. Of course, since apt-get is designed to satisfy a user request, and not just to install packages, we quickly realized that our evil plan was doomed to failure.

The only option left, was to use libapt directly, but the idea of programming in c++ quickly made me to desist. After a bit of research (not that much after all), I finally found a viable solution to our problems in python-apt that is a low level and wrapper around libapt. This definitely made my day.

Now the juicy details. the problem was to convince apt to completely bypass the solver part and just call the installer. First a small intro. python-apt has an extensive documentation with a couple of tutorials. Using python-apt is actually pretty easy (some snippet from the python-apt doco) :

import apt

# First of all, open the cache
cache = apt.Cache()
# Now, lets update the package list
cache.update()

here we open the cache (apt.Cache is a wrapper around the low level binding in the apt_pkg module), then we update the package list. This is equivalent to apt-get update . Installing a package is equally easy :

import apt
cache = apt.Cache()
pkg = cache['python-apt']

# Mark python-apt for install
pkg.mark_install()

# Now, really install it
cache.commit()

Now, the method mark_install of the module package will effectively run the solver to resolve and mark all the dependencies of the package python-apt. This is the default behavior when apt-get is used on the command line. This method has however three optional arguments that are just what I was looking for, that is autoFix, autoInst and fromUser . The explanation from the python-apt doco is quite clear.

mark_install(*args, **kwds)
    Mark a package for install.
    If autoFix is True, the resolver will be run, trying to fix broken packages. This is the default.
    If autoInst is True, the dependencies of the packages will be installed automatically. This is the default.
    If fromUser is True, this package will not be marked as automatically installed. This is the default. Set it to False if you want to be able to automatically remove the package at a later stage when no other package depends on it.

What we want is to set autoFix and autoInst to false to completely bypass the solver. So imagine that an external solver can give use a string of the form : bash+ dash=1.4 baobab- that basically asks to install bash to the newest version, dash at version 1.4 and remove baobab. Suppose also that this is a complete solution, that is, all dependencies are satisfied and there are no conflicts.

The work flow of mpm (mancoosi package manager) is as follows : init apt-get, convert all packages lists + status in a cudf description, pass this cudf to an external solver, get the result and set all packages to add/remove in the apt.cache of python-apt download the packages commit the changes (effectively, run dpkg)

We already have a first prototype on the mancoosi svn. It’s not released yet as we are waiting to do more testing, add more options and make it stable enough for testing. Maybe one day, this will be uploaded to debian.

This is the trace of a successful installation of a package in a lenny chroot. The solver used here is the p2 solver

dev:~/mpm# ./mpm.py -c apt.conf install baobab
Running p2cudf-paranoid-1.6 solver ...
Validate solution ...
loading CUDF ...
loading solution ...
Summary of proposed changes:
 new: 30
 removed: 0
 replaced: 0
 upgraded: 0
 downgraded: 0
 unsatisfied recommends:: 8
 changed: 30
 uptodate: 322
 notuptodate: 116

New packages: baobab (2.30.0-2) dbus-x11 (1.2.24-3) gconf2 (2.28.1-5)
 gconf2-common (2.28.1-5) gnome-utils-common (2.30.0-2)
 libatk1.0-0 (1.30.0-1) libcairo2 (1.8.10-6) libdatrie1 (0.2.4-1)
 libdbus-glib-1-2 (0.88-2) libgconf2-4 (2.28.1-5) libgtk2.0-0 (2.20.1-2)
 libgtk2.0-common (2.20.1-2) libgtop2-7 (2.28.1-1) libgtop2-common (2.28.1-1)
 libidl0 (0.8.14-0.1) libjasper1 (1.900.1-7+b1) liborbit2 (1:2.14.18-0.1)
 libpango1.0-0 (1.28.3-1) libpango1.0-common (1.28.3-1)
 libpixman-1-0 (0.16.4-1) libthai-data (0.1.14-2) libthai0 (0.1.14-2)
 libtiff4 (3.9.4-5) libxcb-render-util0 (0.3.6-1) libxcb-render0 (1.6-1)
 libxcomposite1 (1:0.4.2-1) libxcursor1 (1:1.1.10-2) libxrandr2 (2:1.3.0-3)
 psmisc (22.11-1) shared-mime-info (0.71-3) 
Removed packages: 
Replaced packages: 
Upgraded packages: 

Selecting previously deselected package libatk1.0-0.
(Reading database ... 28065 files and directories currently installed.)
Unpacking libatk1.0-0 (from .../libatk1.0-0_1.30.0-1_i386.deb) ...
Selecting previously deselected package libpixman-1-0.
Unpacking libpixman-1-0 (from .../libpixman-1-0_0.16.4-1_i386.deb) ...
Selecting previously deselected package libxcb-render0.
Unpacking libxcb-render0 (from .../libxcb-render0_1.6-1_i386.deb) ...
Selecting previously deselected package libxcb-render-util0.
Unpacking libxcb-render-util0 (from .../libxcb-render-util0_0.3.6-1_i386.deb) ...
Selecting previously deselected package libcairo2.
Unpacking libcairo2 (from .../libcairo2_1.8.10-6_i386.deb) ...
Selecting previously deselected package libdbus-glib-1-2.
Unpacking libdbus-glib-1-2 (from .../libdbus-glib-1-2_0.88-2_i386.deb) ...
Selecting previously deselected package libidl0.
Unpacking libidl0 (from .../libidl0_0.8.14-0.1_i386.deb) ...
Selecting previously deselected package liborbit2.
Unpacking liborbit2 (from .../liborbit2_1%3a2.14.18-0.1_i386.deb) ...
Selecting previously deselected package gconf2-common.
Unpacking gconf2-common (from .../gconf2-common_2.28.1-5_all.deb) ...
Selecting previously deselected package libgconf2-4.
Unpacking libgconf2-4 (from .../libgconf2-4_2.28.1-5_i386.deb) ...
Selecting previously deselected package libgtk2.0-common.
Unpacking libgtk2.0-common (from .../libgtk2.0-common_2.20.1-2_all.deb) ...
Selecting previously deselected package libjasper1.
Unpacking libjasper1 (from .../libjasper1_1.900.1-7+b1_i386.deb) ...
Selecting previously deselected package libpango1.0-common.
Unpacking libpango1.0-common (from .../libpango1.0-common_1.28.3-1_all.deb) ...
Selecting previously deselected package libdatrie1.
Unpacking libdatrie1 (from .../libdatrie1_0.2.4-1_i386.deb) ...
Selecting previously deselected package libthai-data.
Unpacking libthai-data (from .../libthai-data_0.1.14-2_all.deb) ...
Selecting previously deselected package libthai0.
Unpacking libthai0 (from .../libthai0_0.1.14-2_i386.deb) ...
Selecting previously deselected package libpango1.0-0.
Unpacking libpango1.0-0 (from .../libpango1.0-0_1.28.3-1_i386.deb) ...
Selecting previously deselected package libtiff4.
Unpacking libtiff4 (from .../libtiff4_3.9.4-5_i386.deb) ...
Selecting previously deselected package libxcomposite1.
Unpacking libxcomposite1 (from .../libxcomposite1_1%3a0.4.2-1_i386.deb) ...
Selecting previously deselected package libxcursor1.
Selecting previously deselected package libxrandr2.
Unpacking libxrandr2 (from .../libxrandr2_2%3a1.3.0-3_i386.deb) ...
Selecting previously deselected package shared-mime-info.
Unpacking shared-mime-info (from .../shared-mime-info_0.71-3_i386.deb) ...
Selecting previously deselected package libgtk2.0-0.
Unpacking libgtk2.0-0 (from .../libgtk2.0-0_2.20.1-2_i386.deb) ...
Selecting previously deselected package libgtop2-common.
Unpacking libgtop2-common (from .../libgtop2-common_2.28.1-1_all.deb) ...
Selecting previously deselected package libgtop2-7.
Unpacking libgtop2-7 (from .../libgtop2-7_2.28.1-1_i386.deb) ...
Selecting previously deselected package psmisc.
Unpacking psmisc (from .../psmisc_22.11-1_i386.deb) ...
Selecting previously deselected package dbus-x11.
Unpacking dbus-x11 (from .../dbus-x11_1.2.24-3_i386.deb) ...
Selecting previously deselected package gconf2.
Unpacking gconf2 (from .../gconf2_2.28.1-5_i386.deb) ...
Selecting previously deselected package gnome-utils-common.
Unpacking gnome-utils-common (from .../gnome-utils-common_2.30.0-2_all.deb) ...
Selecting previously deselected package baobab.
Unpacking baobab (from .../baobab_2.30.0-2_i386.deb) ...
Processing triggers for man-db ...
Setting up libatk1.0-0 (1.30.0-1) ...
Setting up libpixman-1-0 (0.16.4-1) ...
Setting up libxcb-render0 (1.6-1) ...
Setting up libxcb-render-util0 (0.3.6-1) ...
Setting up libcairo2 (1.8.10-6) ...
Setting up libdbus-glib-1-2 (0.88-2) ...
Setting up libidl0 (0.8.14-0.1) ...
Setting up liborbit2 (1:2.14.18-0.1) ...
Setting up gconf2-common (2.28.1-5) ...

Creating config file /etc/gconf/2/path with new version
Setting up libgconf2-4 (2.28.1-5) ...
Setting up libgtk2.0-common (2.20.1-2) ...
Setting up libjasper1 (1.900.1-7+b1) ...
Setting up libpango1.0-common (1.28.3-1) ...
Cleaning up font configuration of pango...
Updating font configuration of pango...
Cleaning up category xfont..
Updating category xfont..
Setting up libdatrie1 (0.2.4-1) ...
Setting up libthai-data (0.1.14-2) ...
Setting up libthai0 (0.1.14-2) ...
Setting up libpango1.0-0 (1.28.3-1) ...
Setting up libtiff4 (3.9.4-5) ...
Setting up libxcomposite1 (1:0.4.2-1) ...
Setting up libxcursor1 (1:1.1.10-2) ...
Setting up libxrandr2 (2:1.3.0-3) ...
Setting up shared-mime-info (0.71-3) ...
Setting up libgtk2.0-0 (2.20.1-2) ...
Setting up libgtop2-common (2.28.1-1) ...
Setting up libgtop2-7 (2.28.1-1) ...
Setting up psmisc (22.11-1) ...
Setting up dbus-x11 (1.2.24-3) ...
Setting up gconf2 (2.28.1-5) ...
update-alternatives: using /usr/bin/gconftool-2 to provide /usr/bin/gconftool (gconftool) in auto mode.
Setting up gnome-utils-common (2.30.0-2) ...
Setting up baobab (2.30.0-2) ...
Broken: 0 
InstCount: 30 
DelCount: 0 
dev:~/mpm# 

I think we’ll keep working on this python prototype for a while, but this is not certainly what we want to propose to the community. The mancoosi package manager is probably going to be written in Ocaml and integrated with dose3 and libcudf. This will allow us to gain speed and have a solid language to develop with (nothing against python, but we don’t feel that a scripting language is suitable for an essential component as a package manager). Time will tell. For the moment this is just vapor-ware …