Journal Résolution des dépendances par système de branches

Posté par (page perso) .
Tags : aucun
12
18
sept.
2009
Bonjour,

Aujourd'hui, je vais vous parler de ce que j'ai codé cet après-midi, mais surtout de ce que j'ai pensé depuis maintenant un peu plus d'un mois.

Sous Linux, nous bénéficions généralement d'un système de gestion des paquets, assez performant. Un des problèmes que chacun de ces gestionnaires doit vaincre est la gestion des dépendances.

En effet, des paquets peuvent ne pas vouloir s'installer en compagnie d'autres, ou peuvent en nécessiter. Tout ceci peut vite devenir très complexe, quand un système de dépôt, de versions multiples, etc, sont mis en jeu.

Nous avons actuellement deux solveurs de dépendances qui sont fort connus, et quelques autres. Un des plus utilisé est APT (Advanced Packaging Tool) de Debian, qui résoud très bien tout un tas de dépendances très complexes, et ce très rapidement. C'en est presque devenu une référence. Un autre est Zypp, utilisé par OpenSuSE. Il a ouvert la voie à tous les autres en étant le premier à utiliser un algorithme de satisfaction booléenne. Nous pouvons également citer Yum de Fedora, et URPMI de Mandriva.

Après ces solveurs, il y a les "incomplets", c'est à dire ceux qui marchent mais ne permettent pas de gérer tous les cas. Nous avons Portage chez Gentoo qui ne permet pas de gérer les reverse-dependencies (donc si vous supprimez une bibliothèque, tous les programmes qui en dépendent restent, cassés), ainsi que Pacman de Arch Linux, qui semble également ne pas gérer les dépendances inverses. Il y a aussi les gestionnaires de paquets de distributions comme Slackware. Les autres, je ne les connais pas assez.

Après cette longue introduction, venons-en au fait : j'ai créé un solveur de dépendances assez intéressant :

  • Il est complet à tous points : les reverse-dependencies sont gérées, les provides le seront également bientôt, et il trouve toutes les possibilités, et est capable de les présenter à l'utilisateur
  • Il est extrêmement rapide : il ne fait jouer que les paquets nécessaires. Par exemple, le solveur SAT de OpenSuSE et APT nécessitent de lire toute la base de donnée des paquets, tandis que mon solveur ne charge que les paquets qui sont des dépendances, conflits, dépendances inverses, suggestions, remplaçants, etc
  • Il est incroyablement simple : solver.cpp ne fait que 235 lignes !

Il utilise un concept assez intéressant, ou plutôt plusieurs :

  • Une base de donnée "à la OpenSuSE", c'est à dire binaire, gérée par le solveur lui-même, et partant de principe qu'il faut éviter tous les for() (instructions de boucle qui rendent rapidement un programme très lent quand il a des millions d'entrées). Trouver les dépendances d'un paquet n'a que la complexité O(nombre de dépendances), et non O(nombre de paquets de la BDD) comme chez les autres. Trouver toutes les informations d'un paquet est en temps constant, trouver les versions d'un nom de paquet est O(nombre de versions), etc. C'est difficile à gérer (et à construire, je prend pour preuve databasewriter.cpp qui pèse 727 lignes), mais c'est foudroyant à l'utilisation
  • Setup, le gestionnaire de paquets autour, a une particularité assez intéressante : il est très user-friendly (bien que seulement en console pour le moment) : sortie colorée, absolument toutes les chaînes sont traduites (y compris le titre, la description courte et la description longue d'un paquet)
  • Logrammien. Ce système a été développé en premier lieu pour Logram, mon projet de distribution utilisant comme environnement de bureau KDE et son propre mini-environnement de bureau. Logram sera le plus user-friendly possible, et toutes les touches sont apportées (dont un système de paquet internationalisé et rapide, une intégration des outils à KDE, etc)
  • Le solveur lui-même (pour revenir au sujet) utilise un système de branches, que je détaille maintenant

L'idée m'est venue en utilisant des systèmes de contrôles de versions (VCS). On peut aisément créer une branche, travailler dedans, et la supprimer si ça ne va pas. J'ai simplement appliqué ce principe aux gestionnaires de paquets, et ça a l'air de bien marcher.

Le principe est simple : au début de la résolution, on crée une branche (la branche principale). Dans cette branche, on place le paquet qu'on veut installer.

Ensuite, on explore ses dépendances. S'il n'y a pas de "choix", donc qu'on dépend par exemple de libqt4-gui et qu'il n'existe qu'une seule version de cette bibliothèque dans les dépôts, on la prend. S'il y a plusieurs choix possibles (ici plusieurs versions), on crée une branche par choix.

Ainsi, les branches divergent, et si quelque-chose n'est pas possible (conflit insoluble), on élimine la branche. A la fin de la résolution, devenue "bête et méchante" (c'est à dire qu'on installe les dépendances, supprime les conflits, etc sans se soucier du reste), on obtiens la liste des branches possibles.

Reste alors à les "peser", c'est à dire à obtenir un score pour chacune d'elle, en fonction de critères divers (nombre de paquets à installer/supprimer, mises à jour, taille à télécharger, etc). La branche la plus lourde est présentée à l'utilisateur, c'est potentiellement la meilleure. Les autres sont gardées, pour permettre à l'utilisateur de cliquer sur un bouton «Autre possibilité» si la solution présentée lui désinstalle son paquet de-la-mort-qui-tue qu'il veut garder.

Le résultat est élégant, et Qt aide (oui, c'est développé avec Qt). Le code est court, et marche. Il n'est pas encore assez propre, pas encore fini, mais est disponible sur le SVN de Logram à l'adresse svn://logram-project.org/logram/trunk/Distro/libs/libpackage (architecture bibliothèque/client powa :) ). Le client console est là : svn://logram-project.org/logram/trunk/Distro/base/setup .

Pour le moment, cette bibliothèque et son client ne savent pas installer de paquets. C'est une affaire de semaines, la partie "difficile" étant faite (encore quelques détails à régler avec les provides et la liste des paquets installés, et c'est bon). Toute la partie création de paquets, mise sur le serveur et gestion des miroirs est faite.

Exemple concret

Mes explications sur l'architecture par branches ne me semblent pas assez claire. Je vais vous montrer un exemple, avec le dépôt contenant les paquet suivants :

  • initng-plugins, qui dépend de initng >= 0.6.0
  • initng en version 0.6.0
  • initng en version 0.6.99-gitAug3009, dépendant de libinitng == 0.6.99-gitAug3009
  • libinitng en version 0.6.99-gitAug3009

Je veux donc installer initng-plugins, donc je lance :

setup add initng-plugins

(note: pourquoi add ? Parce que install ne va pas, car si on préfixe le nom d'un paquet par "-", on le désinstalle, ce qui est plus pratique : setup add initng-plugins -libinitng-dev)

Voici simplement les étapes qui sont exécutées par le solveur :

  • Créer la branche master, et y placer initng-plugins
  • initng-plugins dépend de deux version (0.6.0 ou 0.6.99-gitAug3009) de initng
  • Création d'une branche, dans laquelle on place initng-0.6.0
  • initng-0.6.0 ne dépend plus de rien, on retourne true :)
  • Dans la branche principale (oui, on recycle), on ajoute initng-0.6.99-gitAug3009
  • initng-0.6.99-gitAug3009 dépend de libinitng-0.6.99-gitAug3009. On l'ajoute dans cette branche
  • Il n'y a plus de dépendances, on peut retourner true :)

C'est un exemple simplissime, mais qui montre comment les branches permettent de facilement se tirer du problème dans devoir sortir une artillerie telle que SAT. Au final, on a deux branches, contenant respectivement :

  • initng-plugins, initng-0.6.99-gitAug3009 et libinitng-0.6.99-gitAug3009
  • initng-plugins, initng-0.6.0

On les pèse, et en fonction de ce que l'utilisateur veut (du bleeding endge ou du stable), on installera la première ou la deuxième.

Voilà, le journal du vendredi qui ne trolle pas trop. J'espère que je ne fais pas fausse route, mais chez moi, avec un dépôt un peu plus complexe, ça marche :

$ ./setup add initng-plugins
{
"initng-plugins" "0.6.99+gitAug302009~1"
"initng" "0.6.99+gitAug302009~1"
"libinitng" "0.6.99+gitAug302009~1"
}
{
"initng-plugins" "0.6.99+gitAug302009~1"
"initng" "0.6.98"
"libinitng" "0.6.99+gitAug302009~1"
}
{
"initng-plugins" "0.6.98"
"initng" "0.6.99+gitAug302009~1"
"libinitng" "0.6.99+gitAug302009~1"
}


PS: Oui, dans mon résultat, les *-0.6.98 dépendent des version Git, c'est normal, j'avais la flemme de changer la version des dépendances :-° (surtout que comme c'est maintenant, ça induit un petit stress en plus du côté des reverse-dependencies, donc on va pouvoir s'amuser :) )
  • # Bravo

    Posté par . Évalué à 10.

    Tu as réinventé DFS sur un graphe dirigé.
    • [^] # Re: Bravo

      Posté par . Évalué à 9.

      Pas faux ;)

      steckdenis, gères-tu les dépendances circulaires (en:Circular_dependency) ?

      Il y en a un paquet dans Debian : http://debian.semistable.com/debgraph.out.html

      En leur absence, les paquets et leurs dépendances forment un graphe acyclique orienté [http://en.wikipedia.org/wiki/Directed_acyclic_graph].

      Amusez-vous bien avec ces quelques liens...
      • [^] # Re: Bravo

        Posté par (page perso) . Évalué à 2.

        Normalement.

        Je n'ai pas testé, mais ça ne devrait pas casser. Pour le moment, ça ferait une boucle infinie (code minimal sans rien), mais dans quelques minutes, j'aurai intégré un truc qui fait qu'on ne demande pas l'installation d'un paquet déjà en attente d'installation :

        * On demande libgcc1
        * On a besoin de libc6
        * Libc6 a besoin de libcc1, mais il est déjà dedans, on retourne.

        Ca devrait aller :) . Merci beaucoup pour les liens (Debian a vraiment un univers encore plus grand que ce que je pensais autour de lui !)
        • [^] # Re: Bravo

          Posté par (page perso) . Évalué à 7.

          M'est avis que si un bête DFS pouvait résoudre tout ca, l'implémentation des gestionnaires de dépendances ne serait pas aussi complexe.

          Et tu n'expliques pas comment tu gères les dépendances inverses, non plus.
          • [^] # Re: Bravo

            Posté par (page perso) . Évalué à 2.

            La gestion des dépendances inverses est intéressante, surtout que en dehors du solveur.

            Le packageur crée un fichier de la sorte :

            [paquet]
            Name=nom
            Version=version
            Distribution=section de la distrib
            Depends=dépendances (>= version); ...


            Ces fichiers sont envoyés sur le serveur, qui en fonction de Distribution crée les dists/distro/packages.lzma. Ce fichier compressé est la simple concaténation des fichiers écrits par les packageurs.

            Du côté de Setup, ces fichiers sont récupérés, et inscrits dans la base de donnée (par un code monstrueux de 700 lignes d'ailleurs).

            C'est là que tout est joué : dans la base de donnée, chaque paquet a une simple liste de dépendances, et chaque dépendant est une structure :

            struct _Depend
            {
            int8_t type; // DEPEND_TYPE
            int8_t op; // DEPEND_OP
            int32_t pkgname; // Index de la chaîne du nom du paquet de la dépendance
            int32_t pkgver; // Index de la chaîne de la version du paquet de la dépendance
            };


            Type permet de spécifier le type, c'est à dire une dépendance, une suggestion, un conflit, une fourniture, et une dépendance inverse. Les dépendances inverses ne sont pas données par le packageur, mais c'est databasewriter.cpp, qui connaissant tous les paquets de la BDD, s'occupe de faire les liens inverse (pour chaque dépendance, une dépendance inverse est crée de l'autre côté).

            Ainsi, du côté du solveur, le code de gestion des dépendances inverses se limite à ... ceci :

            else if (dep->type == DEPEND_TYPE_REVDEP && action == Solver::Remove)
            {
            act = Solver::Remove;
            // TODO: Vérifier que la dépendance inverse est installée avant de surcharger l'arbre
            }


            Donc, si on retire un paquet, on retire également ses dépendances inverses (et le TODO est là pour me rappeler que quand j'aurai codé l'installation, je devrai voir si le paquet n'est pas déjà non-installé, pour ne pas le supprimer deux fois, et donc créer trop de branches).

            C'est simple, ça marche :

            $ ./setup add -libinitng
            {
            "libinitng" "0.6.99+gitAug302009~1"
            "initng" "0.6.99+gitAug302009~1"
            "initng-plugins" "0.6.99+gitAug302009~1"
            "initng-plugins" "0.6.98"
            "initng" "0.6.98"
            }
            {
            "libinitng" "0.6.98"
            }


            Ici, on voit qu'on a deux solutions :

            * Retirer libinitng-0.6.98 dont rien ne dépend
            * Retirer tous les autres paquets (puisque je n'ai pas encore la gestion des paquets supprimés/installés, tout est supprimés). On voit qu'on a correctement remonté tout l'arbre : initng dépend de libinitng, et les initng-plugins dépendent de initng.

            C'est ok :) .
            • [^] # Re: Bravo

              Posté par (page perso) . Évalué à 6.

              On se fiche des détails du code, ce qui est important c'est ton algorithme, et, là aussi, je doute franchement que simplement inverser les dépendances suffise.

              Je ne suis pas sûr que ton algorithme soit consistent (je doute fortement que ce soit le cas, mais j'ai la flemme de chercher un contre-exemple), mais il n'est en tout cas pas complet :

              A dépend de B et C

              J'installe A, il installe B et C automatiquement

              Je veux désinstaller C. Ton algorithme voit que ca va casser A, donc il le désinstalle aussi. Mais il ne va pas aller voir si B est toujours nécessaire sur ta machine, ce qu'il devrait faire en regardant si il n'existe pas un D qui dépende de B et qui soit installé.


              Par ailleurs, tu n'expliques pas non plus comment tu gères les conflits (l'opposé d'une dépendance, donc). Mes deux centimes, c'est que tu devrais passer moins de temps à coder les détails, optimiser la base de données et faire des sorties colorées, et vraiment réfléchir aux algorithmes que tu utilises et à tous les cas vicieux que tu peux rencontrer.
              • [^] # Re: Bravo

                Posté par . Évalué à 2.

                Pour les conflits je commence à penser qu'il est possible de faire une bonne distro qui ne les gère pas, en abandonnant au moins partiellement FHS (en:Filesystem_Hierarchy_Standard) et en utilisant des scripts de configuration des alternatives. La meilleure solution pour ce problème est, en cas d'alternatives conflictuelles, de ne fournir que le paquet que Je préfère.


                Le problème de dépendances inverses étant coûteux, certaines sous-solutions pourraient-elles être précalculées côté serveur et/ou mises en cache côté client ?

                On devrait pouvoir splitter le graphe des paquets en sous-graphes "intéressants" en ramenant toutes les versions d'un paquet à un nœud avec pour poids une fonction logarithmique sur le nombre de versions (O(n) sur le nombre de paquets), en le désorientant (O(n) sur le nombre de dépendances), en réduisant les chaînes isolées (conserver la longueur originale dans le poids des liens, O(n log n) sur le nombre de dépendances déversionnées il me semble), en calculant l'arbre couvrant minimal (en:Minimum_spanning_tree, à peu près linéaire d'après Wikipedia), puis en tronçonnant l'arbre comme un bourrin.

                Il y a plusieurs techniques à essayer pour tronçonner, mais j'ai le sentiment qu'on aurait facilement de jolis sous-graphes dans lesquels précalculer.
                De toute façon je suis définitivement moins bon que les gens qui bossent là-dessus et n'y pense que vaguement dans le bus, mais j'avais envie de le raconter ;)


                Pour revenir à ton outil steckdenis, fais gaffe à ce que tu veux calculer à chaque opération : nombre d'entre elles sont des mises à jour.
                Or à chaque mise à jour on "désinstalle" la version actuelle et "installe" la nouvelle. Et "souvent" il "suffit" de vérifier que ça n'impacte personne.
                Bref l'opération la plus courante est peu coûteuse dans le cas général, essaye de conserver cette propriété !

                Il y a un super algo en O(n) basé sur une fable de La Fontaine ([http://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algor(...)]) pour résoudre parfaitement le problème des dépendances inverses. J'ai un prototype de preuve en 50 caractères de Brainfuck en tête mais pas la place dans la marge pour le reproduire !
                • [^] # Re: Bravo

                  Posté par . Évalué à 3.

                  > Pour les conflits je commence à penser qu'il est possible de faire une bonne distro qui ne les gère pas,

                  C'est un peu n'importe quoi.
                  Les conflits sont le complément les dépendances.

                  > en utilisant des scripts de configuration des alternatives.

                  Ce qui revient à gérer les conflits...
                  • [^] # Re: Bravo

                    Posté par . Évalué à 1.

                    Exemple de gestion des conflits : tu veux installer vim, ça désinstalle nvi.

                    Gestion des alternatives : tu veux installer vim et as déjà nvi, on te demande vers lequel tu veux que /usr/bin/vi pointe.

                    Et tu pourrais peut-être argumenter au lieu d'affirmer que "c'est un peu n'importe quoi".
              • [^] # Re: Bravo

                Posté par (page perso) . Évalué à 3.

                Effectivement, je ne vérifie pas qu'un paquet n'est plus nécessaire, mais un outil de type deborphan ne doit pas être trop compliqué à coder (explorer les paquets installés, prendre leurs reverse-dependencies, voir si il y en a au moins une d'installée, et s'il n'y en a pas, le supprimer si c'est une lib que l'utilisateur ne veut pas).

                Pour les conflit, c'est assez simple (quoique j'avoue que ça peut être un peu idiot) : si je veux installer le paquet A, et qu'il est en conflit avec B, je supprime B. Je dois encore voir s'il est mieux de faire ça méchamment (on supprime B), ou intelligemment (on supprime B uniquement s'il est installés).
                • [^] # Re: Bravo

                  Posté par (page perso) . Évalué à 3.

                  je supprime B

                  dont dépend C (par exemple), tu supprimes C aussi ?

                  Tu peux regarder quelques use-cases sur
                  http://wiki.mandriva.com/en/RPM_Dependency_Optimization
                  http://wiki.mandriva.com/en/Core_Dependency_Sanitization
                  un exemple de cas tordu http://wiki.mandriva.com/en/Unzip_Dependency (obligeant à revoir les dépendances)

                  pour voir si tu es déjà robuste par rapport à ces cas et, comme indiqué ci-dessus, le projet Mancoosi http://wiki.mandriva.com/en/Mancoosi_Project doit avoir d'autres cas types qu'il vaut mieux prendre en compte. N'hésite pas à te constituer des jeux de dépendances "réels" issus des listes de debian ou d'autres distributions (parser les fichiers de liste automatiquement ne devrait pas être trop dur) pour avérer que tes hypothèses de complexité sont avérés.
                  • [^] # Re: Bravo

                    Posté par (page perso) . Évalué à 2.

                    Pour le moment, oui, C est supprimé. Je compte mettre en place un mécanisme qui crée les branches suivantes :

                    * Une pour supprimer C (et ce qui en dépend)
                    * Une pour chaque paquet du même nom que B, mais avec une version différente, et qui peut être pris comme dépendance de C

                    Ainsi, si C dépend de B>=0.1, et qu'on supprime B=0.5, on pourrait ne pas supprimer C, mais installer B=0.6, qui ira peut-être dans le problème :) .
                    • [^] # Re: Bravo

                      Posté par (page perso) . Évalué à 2.

                      hmmm, ok, toi tu ne suis pas les raisonnements :-)

                      ma suggestion sur C était de pousser le raisonnement par récurrence hein : tu as D qui peut dépendre de C et, de proche en proche, tu peux en arriver à désinstaller tout plein de choses, ce qui est mis en évidence dans les liens que je t'ai fournis, que tu peux prendre un peu de temps à parcourir.
                      Identifier les cas que tu traites et ceux que tu ne traites pas encore permet tout de même d'assurer un début de complétude, d'où la suggestion de regarder des listes existantes de dépendances et d'éprouver tes modèles sur des cas plus réels.
                      • [^] # Re: Bravo

                        Posté par (page perso) . Évalué à 2.

                        Tous les traitements sont récursifs. Si je dis qu'on supprime C, ça veut dire qu'on supprime C, ses dépendances inverses, leurs dépendances inverses, etc jusqu'en haut de l'arbre des dépendances.

                        Pour le moment, mon solveur doit être assez proche de la complétude, car il ne quitte ses boucles récursives que très difficilement (pour le moment, seulement si un paquet dépend d'un autre qui n'existe pas, ou si on veut supprimer A après avoir dit qu'il faut installer A).

                        Par contre, ça risque d'être très lent, donc je cherche pour le moment des conditions d'arrêt supplémentaires gardant au maximum cette complétude, pour vraiment éviter d'avoir un problème solvable qui échoue.

                        Je suis actuellement en train de tester les cas ou A dépend de B, et C fourni également B (exemple de chez Archlinux : fluxbox-svn fournit fluxbox, qui est aussi un paquet). Ca me crée bien deux branches, avec les paquets qu'on va installer, mais je dois voir si c'est bien robuste avec les conflits, les dépendances inverses, etc.
                        • [^] # Re: Bravo

                          Posté par . Évalué à 2.

                          Tu devrais vraiment jeter un oeil à la doc de Burrows en toute priorité avant de continuer à coder, parce que ton algo est très similaire (sinon similaire) à apt au niveau du design général. Et si ton algo est complet, il sera exponentiellement lent avec la taille des dépôts puisque tu n'implémentes aucune stratégie heuristique.
      • [^] # Re: Bravo

        Posté par (page perso) . Évalué à 3.

        Il y en a un paquet dans Debian
        Un paquet dans Debian ? un seul ?


        → ◧

        ce commentaire est sous licence cc by 4 et précédentes

  • # Dépendances inverse

    Posté par (page perso) . Évalué à 6.

    Et bien, quel boulot !
    Je ne sais pas si ta solution est la solution 'idéale' (je ne connais pas assez le comportement les autres gestionnaires de paquets), mais pour archlinux, pacman gère bien la dépendance inverse, si j'ai bien compris ce dont tu parles, il suffit d'utiliser les bonnes options : pacman -Rcs ; par exemple:
    # sudo pacman -Rcs tcl
    Vérification des dépendances...

    Suppression (10): fretsonfire-1.3.110-1 python-opengl-3.0.1a1-1 freenx-0.7.3-4 weechat-0.3.0-2 tk-8.5.7-1 extremetuxracer-0.4-1.1 expect-5.44.1.10-1
    tcl-8.5.7-1 gnu-netcat-0.7.1-3 nxserver-3.3.0-6

    Taille totale des paquets (suppression): 94,06 Mo

    Voulez-vous désinstaller ces paquets ? [O/n] n

    Mis à part ça, bon courage à toi dans ce projet !
    • [^] # Re: Dépendances inverse

      Posté par (page perso) . Évalué à 2.

      C'est avec un grand plaisir que j'apprends que Pacman sait le faire ! Il me semblait avoir lu (et peut-être même dans la doc de libalpm) que Pacman ne sait pas. Il semblerait que les choses se soient arrangées.

      Pour les dépendances inverses, je fais au plus simples. Ce sont en fait des dépendances normales, gérées comme telles. La différence est qu'elles sont calculées par une grosse fonction revdep() dans databasewriter.cpp. Voici ici pour le code : http://wiki.logram-project.org/websvn/listing.php?repname=Lo(...) .

      Merci pour les encouragements :) .
      • [^] # Re: Dépendances inverse

        Posté par . Évalué à 6.

        A mon (humble) avis, ça devrait t'apprendre un peu à regarder à deux fois avant d'affirmer un truc :)

        Par exemple, du comportement d'aptitude, on peut déduire qu'il utilise déja certaines de tes techniques lors de la résolution de dépendance : ouverture de branche sur les différents package installables (notion de noeud), attribution d'un score à chaque noeud, ...


        Les algos SAT font aussi ce genre de chose : baktracking, test de cohérence des différents choix. Parler "d'artillerie lourde" en parlant d'algo de résolution SAT c'est aussi un peu exagéré à mon sens en comparaison d'algo de résolutions d'autre type de problèmes, les algos SAT ne sont pas si compliqués, ni même si lourds. Genre ton algo à toi est très très similaire dans l'idée à un DPLL de base. En moins bien parce que tu n'as rien prouvé de sa correction :)

        Bref, l'idée de ce post c'est d'essayer de te montrer que tes idées ne sont pas idiotes, mais que je trouve un peu prétentieuse ta manière de les présenter.
  • # NP-complet

    Posté par . Évalué à 10.

    Le problème de l'installabilité d'un paquet, étant donné un certain nombre de contraintes, est NP-complet[1]. Il y a donc peu de chances que tu puisses le résoudre en un temps qui a l'air linéaire en la taille du dépôt.

    Il semble donc probable que ton algo soit incomplet. Si tu t'intéresses à ce genre de chose, le projet européen EDOS[2] et son successeur MANCOOSI[3] ont fait pas mal de boulot sur le sujet.

    [1] http://www.edos-project.org/xwiki/bin/download/Main/Delivera(...)
    [2] http://www.edos-project.org
    [3] http://www.mancoosi.org
  • # Trouver le paquet?

    Posté par (page perso) . Évalué à 4.

    Un truc que je ne comprends pas, c'est que tu dis que ton gestionnaire "mets" le paquet dans ta branche principale, mais comment le gestionnaire trouve-t-il le paquet en question?

    Utilise-tu une base de données? Si oui ça veut dire que du fais une requête dans ta base à chaque dépendance que tu rencontres. Est-ce que ça ne prend pas trop de temps? Le maintien de la BDD de APT est ce qui semble prendre le plus de tems pour l'installeur de debian.

    Une autre question est que ton système à l'air vraiment très bien, mais pourquoi le fais-tu dépendre de QT? S'il est vraiment efficace, nombre d'autres gestionnaires aimeront sans doute s'en servir. Limiter les dépendances serait alors un choix judicieux.
    • [^] # Format de la base de donnée

      Posté par (page perso) . Évalué à 3.

      Pas mal de gens semblent s'intéresser à cette base de donnée, donc je vais détailler.

      La base de donnée utilise deux concepts intéressants. D'une part, elle est binaire, et d'autre part, elle est lue grâce à des fichiers mappés.

      L'immense avantage des fichiers mappés est que l'OS se charge de toutes les entrées sorties. Pour un solveur de type SAT, qui doit construire le problème, tous les paquets doivent être lus et mis dans le problème. On a donc beaucoup d'IO sur le disque.

      Ici, mon système n'utilise que les dépendances d'un paquet (avec les conflits, les dépendances inverses, etc). Si le paquet A dépend de B et est en conflit avec C, je ne vois absolument pas pourquoi je dois mettre D, E et F dans le problème.

      Pour illustrer par un cas réel, imaginez que vous souhaitiez installer OpenOffice.org. Vous avez vraiment besoin que votre solveur perde son temps à tester s'il doit installer Wormux ?

      Donc, c'est un fichier mappé en mémoire, et ça accélère/simplifie grandement les choses. Il n'y à qu'à voir comment on récupère un paquet quand on connait son ID :

      _Package *PackageSystemPrivate::package(int index)
      {
      // Trouver l'adresse du paquet
      if (index >= *(int *)m_packages)
      {
      return 0;
      }

      // Début de la liste des paquets
      uchar *pkg = m_packages;
      pkg += 4;

      // Paquet au bon index
      pkg += (index * sizeof(_Package));

      return (_Package *)pkg;
      }


      Seulement des pointeurs. Et ce qui est vraiment excellent, c'est que GCC sait très bien compiler et optimiser du code de ce genre. Ceci est compilé en ce code assembleur, uniquement :

      movq 40(%rdi), %rdx
      xorl %eax, %eax
      cmpl %esi, (%rdx)
      jle .L3
      movslq %esi,%rax
      leaq (%rax,%rax,4), %rax
      leaq 4(%rdx,%rax,4), %rax
      .L3:
      rep
      ret


      9 instructions, en O(1), pour récupérer un paquet dans la BDD. Qui dit mieux ?

      Même chose quand on a une chaîne :

      const char *PackageSystemPrivate::string(uchar *map, int index)
      {
      // Si map == 0, on prend m_strings (c'est qu'on a été appelé d'ailleurs)
      if (map == 0)
      {
      map = m_strings;
      }

      // Vérifier l'index
      if (index >= *(int *)map)
      {
      return 0;
      }

      // Trouver la chaîne à l'index spécifié
      uchar *str = map;
      int count = *(int *)map; // count

      str += 4; // Sauter count

      // Index
      str += (index * sizeof(_String));

      // En fonction du pointeur, trouver l'adresse de la chaîne
      const char *ptr = (const char *)map;
      ptr += ((_String *)(str))->ptr; // Ajouter l'adresse du pointeur
      ptr += 4; // Sauter le count
      ptr += (count * sizeof(_String)); // Sauter la table des chaînes

      return ptr;
      }


      Egalement en temps constant, très rapide. Ca s'utilise comme ça :

      QString PackageSystemPrivate::packageName(int index)
      {
      _Package *pkg = package(index);

      if (pkg == 0) return QString();

      return QString(string(m_strings, pkg->name));
      }


      Pour la dépendance de Qt, c'est simplement qu'il est totalement idiot de ne pas l'utiliser alors qu'il marche si bien. Libpackage et Setup ne dépendent que de QtCore, mais bien. Par exemple, mon code utilise beaucoup de QHash, QList, QVector, QFile, QString, etc. Qt est vraiment très confortable, et permet de raccourcir le code.

      Je n'ai pas de temps à perdre à coder mon propre Hash, ou ma propre liste. C'est une source de bugs potentielle. Je préfère me concentrer sur l'algo, pas sur le codage en dessous. Pour ça, Qt est excellent : il propose tous les trucs dont on a besoin, mais qui prennent pas mal de temps à coder. Utiliser QString::split() ou QString::section est un bonheur quand on a des trucs comme splitter "machin>=chose" pour récupérer le nom et la version.
  • # Paludis?

    Posté par . Évalué à 3.

    L'un des PMS [http://www.gentoo.org/proj/en/qa/pms.xml] alternatifs à Portage peut-il être dit complet si il prévient l'utilisateur contre la désinstallation d'un composant dont dépendent des paquets installé (ou propose l'option adéquate pour du supprimer les paquets dépendants)?

    Il gère aussi les branches de façon astucieuse et pratique [http://ciaranm.wordpress.com/2009/04/16/distributed-distribu(...)] mais en les mélangeant au lieu de les pondérer (à l'utilisateur de cacher ou non tel ou tel composant).

    Il propose encore plusieurs façons d'outrepasser les dépendances circulaires (...) bref, il vaut peut être le détour...
  • # SAT, une artillerie lourde ?

    Posté par . Évalué à 7.

    [...] montre comment les branches permettent de facilement se tirer du problème dans devoir sortir une artillerie telle que SAT.
    Il est complet à tous points... Il est extrêmement rapide : il ne fait jouer que les paquets nécessaires. ... Il est incroyablement simple



    Ces phrases m'ont un peu surpris. Ton solveur fait peut être ~250 lignes, mais comme ça a déjà été remarqué plus haut, le problème de gestion des dépendances est NP-complet et ton solveur.. loin d'être "complet".

    D'autre part, le solveur implémenté dans ZYpp est basé sur le solveur open-source MiniSAT (http://minisat.se/ ) qui fait dans les 600 lignes. Pas mal pour un solveur complet qui s'affranchit de l'exponentialité des solutions possible avec le nombre de paquets disponibles.

    Enfin, tu sous entends que le solveur d'openSUSE nécessite de chargé la base de données en mémoire avant de pouvoir effectuer les calculs de dépendances et que ceci ralenti considérablement sa vitesse.

    Ce n'est pas exactement vrai, puisque en pratique on voit que l'utilisation d'une BDD binaire (que tu sembles aussi utiliser) est foudroyant à l'exécution. Il ne faut que quelques millisecondes pour lire la base de données entière et ce n'est en tout cas pas un "bottleneck".

    Using a data dictionary approach to store and retrieve package and dependency information. A new solv format was created, which stores a repository as a string dictionary, a relation dictionary and then all package dependencies. Reading and merging multiple solv repositories takes just some milliseconds.

    Là où les choses peuvent être améliorées est la vitesse de création des équivalents binaires des méta-données des dépôts, par exemple, en les générant à la volée directement sur le serveur, et pas après téléchargement des md-data par le client.

    A noter aussi que Apt, Yum et URPMI sont incomplets et utilisent plutôt des méthodes heuristiques. A ma connaissance, le seul PM non expérimental qui utilise un algo "avancé" de type SAT et est possiblement complet est Smart.

    Sinon, j'aime bien tes journaux/concepts, y'a de bonne idées mais je pense qu'un peu plus de modestie serait un plus concernant ta crédibilité.

    http://en.wikipedia.org/wiki/ZYpp
    • [^] # Re: SAT, une artillerie lourde ?

      Posté par . Évalué à 2.

      A ma connaissance, le seul PM non expérimental qui utilise un algo "avancé" de type SAT (en plus de ZYpp) et est possiblement complet est Smart.
    • [^] # Re: SAT, une artillerie lourde ?

      Posté par (page perso) . Évalué à 1.

      > Sinon, j'aime bien tes journaux/concepts, y'a de bonne idées mais je pense qu'un peu plus de modestie serait un plus concernant ta crédibilité.

      Merci :) . Pour la modestie, c'est toujours un effet de bord. Quand je viens de terminer quelque-chose, et que j'ai passé plusieurs jours pour y arriver, je suis toujours très (trop ?) content.

      Pour le solveur SAT, rien que le fait qu'on doive lire tous les paquets est lourds. Il y a peut-être moyen de l'éviter, mais le but est de construire un problème à base de clauses, une ou plusieurs clauses par paquets. Oui, ce sont des clauses simples (comme dit dans la page Zypp, ça doit faire quelques mois que je lis presque tous les jours ce wiki et la doc Doxygen de libzypp), mais il y en a beaucoup.

      On peut avoir une BDD aussi optimisée qu'on veut, si on doit lire 40Mio sur le disque dur pour résoudre un problème, le disque dur ne va pas aimer. Chez moi, comme seuls les paquets entrant directement dans le problème sont lus, la BDD peut faire plusieurs Gio qu'il n'y aura pas de problèmes.

      J'ai conçu mon gestionnaire de paquets avec dans la tête l'informatique qu'on aura dans 10 ou 20 ans : plus de logiciels propriétaires (ou très peu), énormément de logiciels libres, et un bon million de paquets dans les distros. Le moindre algo en O(nombre de paquets) est immédiatement écarté, car même s'il est rapide, faire 40 millions de tours de boucle, c'est trop.

      Mes algos sont généralement en O(1) (pour les simples) ou en O(nombre d'éléments en jeu). Par exemple, pour trouver tous les paquets qui ont un nom (donc par exemple pour voir quels paquets correspondent à "libfoo>=0.4.88"), je prend la structure _String de libfoo, et cette structure a un pointeur vers des _StrPackage. Je les explore, et j'obtiens la liste de tous les paquets et leurs versions qui ont ce nom.

      Au passage, c'est effroyablement simple pour un autre problème de dépendances : les Provides. Quand un paquet en fournit d'autres (par exemple "machin" qui fourni "truc = 0.5"), il me suffit de rajouter dans les StrPackages de "truc" une entrée "0.5"->id_du_paquet_truc.

      Le solveur de dépendance n'aura même pas à s'en occuper, c'est directement pré-résolu dans la BDD.

      Pourquoi je cherche tant de rapidité ? Après tout, on n'installe pas un paquet tous les jours. Simplement, quand on installe un paquet, je compte faire un truc à la Synaptic, c'est à dire rajouter en temps réel les dépendances que notre action précédente entraîne. Il fait donc qu'il n'y ait pas de lag, et donc que la résolution soit foudroyante (attendre 0,1s, c'est déjà trop).
      • [^] # Re: SAT, une artillerie lourde ?

        Posté par . Évalué à 5.

        <i>Pour le solveur SAT, rien que le fait qu'on doive lire tous les paquets est lourds. Il y a peut-être moyen de l'éviter, mais le but est de construire un problème à base de clauses, une ou plusieurs clauses par paquets. Oui, ce sont des clauses simples (comme dit dans la page Zypp, ça doit faire quelques mois que je lis presque tous les jours ce wiki et la doc Doxygen de libzypp), mais il y en a beaucoup.</i>

        A te lire, j'ai vraiment l'impression qu'on parle de 2 choses totalement différentes et que tu n'a pas saisi comment le solver d'openSUSE fonctionne. Tu devrais aussi lire la doc de Daniel Burrows et celle du projet EDOS, ainsi que jeter un oeil au fonctionnement du SatSolver ZYpp en utilisation réelle.

        Pour mémoire, voici le fonctionnement basic de ZYpp :
        1/ teléchargement des métadonnées depuis les dépôts
        2/ transformation des métadonnées en fichiers binaires .solv, qui contiennent les règles de dépendances de chacun des paquets
        3/ calcul des dépendances
        4/ application du résultat


        L'étape 1/ est "bottleneck", elle ne dépend pas du solveur, mais du format des md-data et de la qualité de la connexion aux dépôts.

        L'étape 2/ utilise une "dictionary approach" pour stocker les dépendances sous la forme d'un nombre 32bits unique, permettant une comparaison très rapide de 2 chaines de "charactères", principe de base du solveur SAT, un espace disque moindre, puisqu'un nombre est plus petit qu'une chaine de charactère (j'ai 4.7 Mo, 4.5 Mo, 3.6 Mo, 406 Ko pour les 4 plus gros dépôts activés qui représentent à eux seul un peu plus de 16'000 paquets, 1.4 Mo pour ma base RPM locale .solv, et mes 14 autres ne font que quelques Ko) et la representation mémoire ne prend pas plus de place sur un système 64bits où un pointer est 2x la taille d'un nombre 32bits (cf. doc SatSolver).
        Un refresh forcé de ces fichiers me prends ~9 secondes, mais est surévalué puisque le dépôt principal, qui ne change jamais, est recré (5 sec est plus realiste pour une utilisation standard.. et encore).

        L'étape 3/ me calcul les dépendances (par exemple un dist-upgrade me propose une solution en ~2.5 secondes), enfin l'étape 4/ valide les changements et télécharge les paquets proposés.


        Au final, le calcul des dépendances est extrêmement rapide malgré le fait qu'un grand nombre de paquets sont pris en compte en mémoire (~2.5 secondes pour +16'000 paquets). J'ai l'impression que le problème que tu essaies de résoudre n'existe tout simplement pas avec un solver sat couplé avec une approche metadonnés-binaire telle qu'implémentée par ZYpp. De plus, la résolution est complète.
        • [^] # Re: SAT, une artillerie lourde ?

          Posté par (page perso) . Évalué à 1.

          ~2.5 secondes pour +16'000 paquets

          Justement. Est-il normal, pour par exemple mettre à jour Wormux, d'avoir à gérer 16000 paquets. Là, ça prend 2,5 secondes, ce qui est correct. Maintenant, si t'as 160 000 paquets, ça va prendre 25 secondes, et là ça fait mal, très mal (et 160 000 paquets, c'est une affaire d'années).

          Il me semble qu'un problème SAT est une suite de clauses, comme ceci (format utilisé par MiniSAT en entrée) :

          -1 2 3
          3 4 -5
          ...


          Construire une telle liste nécessite de lire tous les paquets de la base de donnée, c'est à dire un minimum un for() sur les paquets.

          Pour chaque paquet, il faut lister ses dépendances (ce qui est rapide en binaire), etc. Au final, la construction du problème prend presque autant de temps que sa résolution.

          Maintenant, je me trompe peut-être.
          • [^] # Re: SAT, une artillerie lourde ?

            Posté par . Évalué à 5.

            C'est vraiment de l'enculage de mouche que tu nous fais.

            En l'occurence, avec un solveur sat, le "bottleneck" n'est pas la résolution des dépendances ni la lecture des métadonnées mais le téléchargement et l'installation des paquets.

            D'autre part, ces 2.0 - 2.5 secondes ne sont pas linéairement dédiées à la résolution :

            zypper dup
            Loading repository data... -> 1 sec
            Reading installed packages... -> 1 sec
            Computing distribution upgrade... -> 0.5 sec


            Pour finir, je ne vois strictement pas l'intérêt de créer une solution pour un scénario viable dans 10 ou 20 ans alors que tu ne connais strictement rien aux conditions du futur environment (capacité de bande passante, performance disque dur et CPU, calcul quantique ?).

            Quitte à créer un solution, autant qu'elle réponde à un besoin d'aujourd'hui, ou elle aura toute les chance d'être obsolète avant même d'être utile.
            • [^] # Re: SAT, une artillerie lourde ?

              Posté par (page perso) . Évalué à 2.

              Loading repository data... -> 1 sec
              Reading installed packages... -> 1 sec
              Computing distribution upgrade... -> 0.5 sec


              Justement. On n'a pas l'air de vraiment se comprendre, et la faute est peut-être de mon côté, mais tu viens de me montrer ce que je dénonce.

              Sur les 2,5 secondes, seulement 0.5 secondes sont effectivement utilisées pour du calcul. Le reste est, comme le dit «Loading repository data», la lecture de tous les paquets et la construction du problème (avec «Reading installed packages» qui applique des contraintes supplémentaires, ou qui complète le problème).

              On a donc 0,5 secondes réellement utiles, et 2 secondes de perdues parce que le SAT nécessite de lire la base de donnée de tous les paquets de la distribution (et c'est de ça que je parle, ça n'a rien à voir avec le SAT justement, le SAT est rapide et léger, mais il nécessite, avant lui, un traitement lourd de construction du problème).

              Avec Setup, les deux secondes ne sont pas perdues, et comme le problème est nettement plus court, ce ne sera pas 0,5 secondes, mais peut-être moins (quoique, le solveur SAT simplifie très fortement le problème en première passe pour éliminer les «-wormux | wormux-data» totalement inutiles si t'installes OOo).
            • [^] # Re: SAT, une artillerie lourde ?

              Posté par (page perso) . Évalué à 2.

              L'enculage de mouche est ce qui fait les programmes optimisés. Chaque optimisation n'est pas un luxe et fait gagner du temps à la longue.

              Je connais beaucoup de gens qui sont passés de debian à arch pour la seule raison que pacman est plus rapide que apt, même si les paquets debian sont de meilleure facture (enfin, c'est mon avis, pas taper!)

              Et puis, 2.5s pour résoudre des dépendances est toujours trop long.

              Pour illustrer mon propos, j'ai mesuré les temps mis par apt et pacman pour installer vim sur le même ordinateur, apt prends environ 10s et pacman 2s, et je les trouve toujours trop lents.
              • [^] # Re: SAT, une artillerie lourde ?

                Posté par . Évalué à 3.

                Je rajoute que 2.5sec c'est son cas. Ça donnerait quoi sur un appareil mobile ? genre sur le n900 ?
              • [^] # Re: SAT, une artillerie lourde ?

                Posté par . Évalué à 2.

                Et puis, 2.5s pour résoudre des dépendances est toujours trop long.

                Pour illustrer mon propos, j'ai mesuré les temps mis par apt et pacman pour installer vim sur le même ordinateur, apt prends environ 10s et pacman 2s, et je les trouve toujours trop lents.


                ~2.5s pour me calculer un dist-upgrade (sur un laptop vieux de 3 ans avec un DD 5400tpm), pas l'install d'un paquet unique.
  • # Cas complexes

    Posté par (page perso) . Évalué à 5.

    Ainsi, les branches divergent, et si quelque-chose n'est pas possible (conflit insoluble), on élimine la branche. A la fin de la résolution, devenue "bête et méchante" (c'est à dire qu'on installe les dépendances, supprime les conflits, etc sans se soucier du reste), on obtiens la liste des branches possibles.

    Je me rappelle que l'approche de smart avait l'avantagee de gérer des cas mal gérés par les autres outils. Cette phrase me laisse penser que ce n'est pas le cas de ton outil.

    Si je me souviens bien un des cas est :

    A et B sont installés
    A necessite plop
    B fournit plop

    On demande d'installer C

    C necessite D
    D est en conflit avec B

    Il existe E qui fournit plop mais n'est pas en conflit avec D et il faut proposer de remplacer B par E pour pouvoir installer C
    • [^] # Re: Cas complexes

      Posté par . Évalué à 0.

      Effectivement si E est une autre version de B, il faudrait présenter à l'utilisateur la possibilité de désintaller B et d'installer E à la place.
      Sinon, si E n'est pas une autre version de B, je ne vois pas pourquoi on devrait parcourir la base pour trouver une solution à l'action de l'utilisateur... dans ce cas on ne devrait que lui présenter l'information du conflit et pas d'autre solution que de désinstaller B.
    • [^] # Re: Cas complexes

      Posté par (page perso) . Évalué à 2.

      Je n'ai pas répondu à ce message plus tôt car je n'avais pas encore implémenté le système de "fournitures" (provides).

      Pour le moment, si B fournit Plop, ça crée un "paquet virtuel" Plop. En fait, comme paquet virtuel, c'est une simple entrée dans la table des chaînes de caractères (mais bon, c'est un détail technique).

      Bref, C install D, et D supprime B. Actuellement, ça supprimera A (car avec les provides, des dépendances inverses sont crées, etc). Seulement, comme c'est un simple système de dépendances inverses, ce n'est pas répété dans le code, et je peux faire un truc plus complexe.

      Prenons A qui dépend de B, C ou D. Je veux supprimer D. Nous crées donc 3 branches : une où on supprime D et A, une où on supprime D et installe C, une où on supprime D et installe B. C'est simple à faire, le format de la BDD le permet (j'aime ce format, il permet plein de choses).

      Reprenons donc notre exemple : D supprime B. B va donc créer deux branches : une où il supprime A ... et une où il installe E ! Voilà, c'est fait, le problème est résolu, et en quelques lignes seulement (enfin de crois, j'ai pas encore codé).
  • # les branches, c'est déjà dans SAT

    Posté par . Évalué à 2.

    J'ai dû rater un truc, car si tu connais SAT, je ne comprends pas ta nécessité d'introduire un concept de branches.

    Je veux dire, tu as ton problème représenté sous forme de formule de logique booléenne et tu cherches les modèles (= assignements de valeurs de vérités aux variables booléennes) qui la satisfont. Soit tu te bricoles ton algo qui le fait (tu te modifies un DPLL), soit il existe déjà des algos (implémentés) qui t'énumèrent tous les modèles possibles d'une formule booléenne (cherche AllSAT algorithm sur le net). Après, tu prends tous tes modèles trouvés, tu leur mets un score comme tu l'as décrit pour tes branches, et tu présente à l'utilisateur les modèles du meilleur au plus mauvais. Si tu regardes l'ultraclassique algorithme DPLL, sa règle "split" est une règle de branchement.

    (Je n'ai pas lu ton code).
  • # Question

    Posté par . Évalué à 1.

    Quel est la différence entre ton outil et http://ant.apache.org/ivy/ au niveau de la gestion des dépendances?
  • # apt-git

    Posté par (page perso) . Évalué à 1.

    Un peu dans le même genre, quelques réflexions éparses sur la similarité entre les systèmes de gestion de dépendances et les gestionnaires de versions :

    http://da.weeno.net/blog/ (article "apt-git", désolé, pas de lien permanent pour cause de rewrites temporairement pétés)

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.