EDOS WP2 Meeting of January 14th 2005

EDOS WP2 Meeting of January 14th 2005

Next scheduled meeting: february 28th, at PPS' location.

Participants

• Roberto Di Cosmo? - PPS
• Ralph Treinen? - LSV, Debian
• Marc Zeitoun? - LIAFA - http://www.liafa.jussieu.fr/~mz/
• Jérôme Vouillon? - PPS - http://www.pps.jussieu.fr/~vouillon/
• Xavier Leroy? - INRIA Cristal -
• Francesco Zappa Nardelli? - INRIA Moscova
• Radu Pop - Mandrakesoft - Thèse CIFRE INRIA Mandrakesoft
• Stéphane Laurière - Mandrakesoft - Mandrakeclub platform Architect.
• Warly - Mandrakesoft - Mandrakelinux Engineering
• Juliusz Chroboczeck? - PPS
• Vincent Balat - PPS

Overview of the Mandrakesoft distribution building process

External sources -> packaging -> integration -> QA -> distribution in the Cooker mirrors -> user feedback.

Distribution:

• Machine de référence
• Miroirs primaires
• Miroirs secondaires
• Utilisateurs

Orders of magnitude

Mandrakelinux: ~9000 binary rpms for each architecture. 50% to 60% packaged by external contributors that are coopted and considered trustworthy (no crypto signature, though).

Cooker: ~200 Mb/day modified and pushed to the mirrors (no metrics available on the propagation speed).

Debian: ~15000 packages, every contributor MUST obtain a key signed by a Debian member.

Static analysis of dependencies: overview and issues

One needs to ensure the coherence of a set of packages, w.r.t. a set of "dependencies".

At least 3 kinds of dependencies are used:

• compilation
• installation
• use

One needs to detect statically at least the following incoherences:

• A depends on B, which is missing
• A depends on a set of packages that, due to hereditary conflicts, end up not allowing A to be installed

(see more on this on the WpTwoSection)

Too often these checks are only empirically performed at installation time on the user machine by the tool used to install them (apt-get/urpmi etc.)

Dependencies idiosynchrasies

Mandrakelinux: packages can depend on a single file instead of a package (not in Debian).

Deian/Mandrakelinux: virtual package (a set of packages) try to provide a notion of "feature" (or functionality, like MailTransportAgent, WebBrowser, etc.) independently of the actual package providing the functionality.

Topology of the dependency graph:

some studies (see again WpTwoSection) indicate that this graph is similar to the Internet graph (heavy central kernel, with a wealth of mostly isolated vertices outside the core).

Sometimes one get cycles (provide examples here!!!!)

Goals:

• check dependency consistency:
• no blatant inconsistencies (the 2 cases above)
• "feature preservation" : if a collection of packages was installable at time t,

the same collection must still be installable at time t+1 (or a collection that replaces (in a formal sense, see Replaces: attribute in Debian format) the original)

• others?

All this, should be done EFFICIENTLY, possibly with on-line algorithms.

N.B.: Avoir un historique de tous les packages dans une base: packages de la 10.1, 10.0. Questions: quel chaînon pour passer de la 10.1 à la 11 sans briser trop de choses dans les paquets installés. Passage de devfs à udev de la 10.0 à la 10.1: problème de mise à jour: il y a des dépendances pratiques qui ne sont pas exprimables à l'avance. La notion de feature, qui dépasse la notion de package, est importante. Etat A n'est pas seulement un ensemble de packages mais un ensemble de packages + leurs configurations. Comment passer de A à B en conservant la configuration.

Ideas:

To perform the static analysis, we identified at least two approaches:

• conversion into a CLP problem: every dependency (package A version x depends on B vers. y and C vers. z, but conflicts with D <= w) can be turned into a Horn clause A(vx) :- B(vy), C(vz), not D(vw), vx==x, vy==y, vz==z, vw<=w in CLP.

Then one can check the "satisfiability" of some goals in the resulting HUGE CSP that model the above goals.

• building a dependency graph: this seems easier to handle when we need to compute a building order of the components, or

handle cycles, and then verifying the properties may turn out to be a model checking problem on the graph.

In any case, we need to attach COSTS to the dependencies, and optimize costs when choosing among many possible upgrade paths… among these paths we NEED to integrate the "virtual" paths that produce non-existing binary packages by properly recompiling some given sources… (see example about Roberto's compiler course).

Another interesting phase is the splitting phase of the distribution among several CDs (bin packing problem under some constraints, like minimizing dependencies between CDS, and keeping all prefix of the 1...n CDs consistent). Right now, Warly uses a greedy algorithm.

Tasks

collect the dependency scenarios

bis organize a couple of talks to explain the details of the .deb and .rpm metadata

(we want an up-to-date picture w.r.t. the paper by Alien's author, which seems outdated) task assigned to Ralf and Warly?

ter Get a semi-formal description of the algorithms at work in urpmi Warly and apt Ralf??

2 study the expressive power of the dependency metadata
Answer from Roberto and Jerome: using conflicts, and and-or normal forms, we can easily encode any possible propositiona logic satisfiability problem into a collection of packages. Just put the formula in conjunctiv normal form, then replace all negate atom A with a new package nA and define nA as conflicting with A. We sill need to get the expressive power for the CLP, but it seems we get all CLP(v) where v is the set of version numbers with the >,<, =, <> comparisons...
In this encoding, a package A present in the base with no dependencies is _satisfiable_ = installable, while an absent package is unsatisfiable (or false = not installable).
One needs to handle mutually recursive dependencies in a special way (like the Cretan paradox in the discussion with Antonio and Vincent).
What is the consequence for the complexity of the algorithms?
Notice that we need to verify a property on ALL the 20000 clauses at once… 3 build a fast, Oz based implementation of the CLP problem out of a given Debian pool or Cooker state and perform a first analysis of the first 2 properties, to see how real and widespread is the problem. this task is assigned to Ralf and Roberto? 4 need to build "plugins" able to read .deb, .rpm etc. and convert them in a common representation for analysis purposes. Samuel Hym suggested to look at ara, an OCaml tool by Berke Durak to perform complex searches in the Debian detabase? 5 we might imagine to refine dependencies (depend on symbols in binaries instead of files or full packages)

Unfinished part … these notes come from Stephane Lauriere and need to be digested yet; you are very welcome to do it

Quelle terminologie génie logiciel pour parler de features, d'éléments composables? Cf peut-être la terminologie OSGI de bundles etc. Format dkms pour modules du noyau. Capacité pour un élément p de s'auto-upgrader (les contraintes étant que: gcc soit installé etc.): recompilation pour que le module soit créé pour une nouvelle version du noyau: modules NVidia etc.

Concept de "trigger" liant les applications: Possibilité en rpm de dire: quand on installe Java, Mozilla va s'auto-configurer pour plugin Java. Mais ce n'est pas vraiment des dépendances. Ecarté dans un premier temps du projet.

Debian: il y a des dépendances plus ou moins strictes: recommends, suggests.

Worflow de la distribution Debian: Distribution "unstable", qui n'est pas forcément cohérente entre paquets. Extraction pseudo-automatique d'un ensemblde paquets pour constituer une distribution "testing" qui est cohérente. Propager les paquets d'une distribution vers une autre en garantissant que les packages restant cohérents. Testing est un état permettant en permanence de faire une distribution stable. Mais ne marche pas aussi bien car énormément de paquets. Numéros de version.

Répercussion sur le modèle: les noeuds sont ils des packages? ou faut-il exprimer les versions sous forme de noeuds.

Remarque: dépendances exprimées sur les sources versus exprimées sur les binaires. Cf l'approche Gentoo qui permet de compiler un ensemble de sources récursivement. Dans Mandrakelinux: rpmrebuilder sait plus ou moins faire ça. Graphe de dépendances annoté par des coûts. Pourrait permettre d'avoir un programme "intelligent" qui choisit de compiler des sources ou d'utiliser des binaires, qui saurait déterminer le chemin optimal. Pour l'utilisateur: avoir le minimum de packages à télécharger pour installer tel nouvel outil.

Les packages sources et les packages binaires sont des entités devant pouvoir être décrites et traitées par le même formalisme.

Dans la description du système, il y a aussi l'ensemble des patches appliqués au sources d'origine, et la façon dont a été construit le RPM source à partir du tar.gz d'origine. La transformation opéré sur le .tar.gz pour aboutir au RPM source doit être elle modélisée également? Les sources d'origine font-elles partie du système décrit? "upstream" dans le monde Debian. Signatures md5. Le fait qu'un binaire soit construit à partir de telle source est une dépendance. Dépendance du paquet source sur le source upstream.

NB sur les architectures: elles ne sont pas forcément mutuellement exclusives. Cf le cas de libs i586 et de libs x64. Il y a '64' dans le nom des librairies 64 bits. --> possibilité d'avoir une libc-64. Où est le README? Peut-être dans les 2.

Remarque: il faudrait avoir plus de flexibilité dans l'écriture des dépendances du binaire. Elles devraient pouvoir dépendre d'une part des dépendances spécifiées dans les sources et d'autre part par exemple du compilateur utilisé pour produire les binaires.

Actuellement l'ingénierie Mandrakelinux dispose d'un outil écrit en Python qui fait un calcul d'ordonnancement et permet d'avoir une idée empirique de la gestion. il faudrait modéliser et consolider les outils de gestion de dépendance existants: urpmi, apt etc.

Les algorithmes utilisés pour le calcul de dépendance sont actuellement répliqués dans plusieurs outils (rpm, urpmi etc.).

Obtenir graphe plus complet

Autres

Partie diffusion, Warly: peut-être utiliser MLDonkey écrit en CAML.

{metadata}

Type Meeting

Topics Wp2

{metadata}