stopsoftwarepatents.eu petition banner

Die Interna von deborphan

Vorwort

Bei der Vorbereitung auf meine Prüfung zur Compilerbau‐Vorlesung hat es mir stark in den Fingern gejuckt und ich wollte mal wieder richtig programmieren. Das Opfer sollte dabei deborphan werden, da ich mit dem Hintergrund des Compilerbaus den Parser für die Datenbank neuschreiben bzw. verbessern wollte. Ich habe dem Drang dann auch nachgegeben, aber so sehr viel vom Compilerbaukonzept (ein Automat oder Rekursive-decent-Parser) habe ich nicht umgesetzt.

Da aber deborphan bei mir schon länger auf der Aufgabenliste stand, war dies auch ein guter Einstieg, das Problem mit den Zyklen im Abhängigkeitsgraphen in Angriff zu nehmen. Die Ideen dazu schwirrten mir schon mehrere Jahre im Kopf herum, aber es fehlte immer die Zeit sie mal umzusetzen.

Das Anliegen des Vortrags am 25. Oktober 2007 war es dann, die Ergebnisse und Erkenntnisse aus meiner (bisherigen) Arbeit zu präsentieren und darüber zu diskutieren. Es ging dabei nicht nur um deborphan, sondern auch um Programmierstil und ‐konzepte.

Das böse malloc

Spätestens seit Fefe wissen wir, dass malloc böse ist oder, korrekt gesagt, dass es missbraucht wird. Die Speicherstruktur für Pakete bei deborphan hat weniger als 100 Byte, aber wird zu Hauf gebraucht – bei mir z. B. über 1500 Stück. Die alte Version von deborphan hat den Speicher für jeden Container einzeln angefordert und freigegeben. Das führte zu mehreren tausend malloc‐Aufrufen. … und laut Fefe ist das schlecht.

Da deborphan eine ideale Welt bietet, in der

ließ sich sehr leicht eine eigene Speicherverwaltung schreiben, die sich mit malloc sehr größe Blöcke holt und diese dann intern in kleinere Einheiten zerlegt. So werden über die Grenze zwischen Userspace und Kernelspace nur große Blöcke transportiert, um den „teuren“ Contextswitch auszugleichen. (Der Ansatz ist falsch. siehe unten)

Der Code dazu ist recht einfach: 

#include <errno.h>
#include <stdlib.h>

#include "dbparser.h"
#include "mem.h"

static const unsigned pool_size[] = { 50, 100, 300, 600, 1200, 2400,
    4800, 9200, 18400, 36800, 73600 };

static pkg_t *pkg_pool[ sizeof(pool_size) ];

static signed char pkg_pool_level = -1;
static unsigned next_free_pkg;

pkg_t* mem_new_pkg(void)
{
    if (pkg_pool_level == -1 || next_free_pkg >= pool_size[pkg_pool_level])
    {
        ++pkg_pool_level;
        if (pkg_pool_level >= (signed char) sizeof(pool_size))
        {
            --pkg_pool_level;
            errno = ENOMEM;
            return NULL;
        }
        pkg_pool[pkg_pool_level] = malloc(pool_size[pkg_pool_level] * sizeof(pkg_t));
        if (pkg_pool[pkg_pool_level] == NULL)
        {
            --pkg_pool_level;
            return NULL;
        }
        next_free_pkg = 0;
    }

    pkg_t *pkg = &pkg;_pool[pkg_pool_level][next_free_pkg];
    ++next_free_pkg;

    return pkg;
}

void mem_free_pkg(pkg_t* ptr)
{
    if (ptr == &pkg;_pool[pkg_pool_level][next_free_pkg - 1])
      --next_free_pkg;

    /* I'm to lazy to handle the other cases */
}

void mem_finalize(void)
{
    signed char i;
    for (i = 0; i <= pkg_pool_level; ++i)
    {
        free(pkg_pool[i]);
        pkg_pool[i] = NULL;
    }
    pkg_pool_level = -1;
}
und einfache Tests sind auch recht vielversprechend: Ein Faktor 60. 
% ltrace -c ./test_mem
% time     seconds  usecs/call     calls      function
------ ----------- ----------- --------- --------------------
 68.82    0.000691         138         5 malloc
 31.18    0.000313         104         3 free
------ ----------- ----------- --------- --------------------
100.00    0.001004                     8 total

% ltrace -c ./test_mem-single_malloc
% time     seconds  usecs/call     calls      function
------ ----------- ----------- --------- --------------------
 52.04    0.034589          34      1001 malloc
 47.96    0.031882          31       999 free
------ ----------- ----------- --------- --------------------
100.00    0.066471                  2000 total

Aber spätere Tests haben gezeigt – was Thomas auch beim Vortrag eingeworfen hat –: es lohnt sich nicht darüber nachzudenken. Gemessen an der Gesamtzeit rangieren die malloc‐Aufrufe im unteren einstelligen Prozentbereich und es gibt wirklich schlimmere Stellen.

Hannes hat mich später noch darauf hingewiesen, dass malloc keine Systemfunktion ist, d. h. malloc ist nicht im Kernel implementiert! Vielmehr ist malloc ein Teil der libc, die entsprechende Aufrufe (brk, sbrk oder mmap) an den Kernel tätigt. Aus dem Grund kann man die malloc‐Aufrufe auch nicht mit strace sehen, sondern nur mit ltrace. Und auch aus diesem Grund schlagen hier weniger die Context‐Wechsel zwischen Kernel‐Space und User‐Space (diese werden durch die libc verringert) oder die Speicherimplementation im Kernel zu buche als vielmehr die Implementation in der libc. Das angesetzte Ziel der obigen Überlegungen ist also falsch.

Da sich deborphan bei der Speichernutzung wirklich sehr friedlich verhält, ist es überhaupt nicht sinnvoll, eine neue Problemquelle zu schaffen. Die Speicherverwaltung der libc reicht vollkommen aus. Außerdem sollte man bei der Implementation einer eigenen Speicherverwaltung sehr darauf achten, dass die Implementation von malloc nicht dagegen arbeitet, oder man verzichtet gänzlich auf malloc und benutzt die Systemfunktionen.

Vergleich von Zeichenketten

In der alten Version von deborphan wurde im Parser für die Datenbank der Type der Zeile (Package, Version, Depends, Maintainer, …) anhand von einzelnen Buchstaben erst grob bestimmt und dann wurde darauf mit strcmp geprüft. (Hier der Code aus der neuen Version)

switch ( toupper(line[0]) )
{
  case '\0':
    /* The empty line after the package block */
    return 1;

  case 'D':
    switch ( toupper(line[2]) )
    {
      case 'P':   /* DePends */
        match = match_lcase_skip_white(line, "depends:");
        if (match != NULL)
[…]
  case 'S':   /* DeScription */
    match = match_lcase_skip_white(line, "description:");
[…]
    }
  case 'E': 			/* Essential */
    match = match_lcase_skip_white(line, "essential:");

Von Thomas kam der Vorschlag, dass man doch auch mit strcmp hätte arbeiten können:

if (strncmp(line, "Depends:", 8) == 0)
  […]
else if (strncmp(line, "Description:", 12) == 0)
  […]
else if (strncmp(line, "Essential:", 10) == 0)
  […]

Ich habe solche Strukturen auch schon in anderen Programmen gesehen und uns sind in der Diskussion auch keine wirklichen Vor‐ oder Nachteile der einen oder der anderen Variante eingefallen.

Minensuchparadigma

Ich habe bei dieser Programmieraktion das erste Mal massiv assert eingesetzt. Zum Teil war ich zu faul ordentliche if (…) printf("Meldung"); zu schreiben und habe es auf später verschoben und teilweise waren es auch viele intere Prüfungen, die nur für die Entwicklung sinnvoll sind. Dabei habe ich unbewusst das umgesetzt, was Prof. Küspert in der Vorlesung über „Fehlertoleranzen in Datenbanksystemen“ als Minensuchparadigma bezeichnet hat: Wärend man sich auf dem Weg durch eine Datenstruktur (hier ein Graph) befindet, führt man lokale Konsistenzprüfungen (Anzahl der gelesenen Elemente == erwartete Anzahl oder der Typ des Knoten ist auch der erwartete Typ) durch. Man prüft nicht ständig die ganze Datenstruktur, sondern nur den Teil, in dem man gerade unterwegs ist. Der Name Minensuchparadigma kommt von der Arbeit eines Minensuchers, der mit seinem Metalldetektor immer lokal vor sich her bzw. um sich herum sucht und nicht planlos über das ganze Feld springt – immer nur dort, wo er sich gerade bewegt und wo es gebraucht wird.

Aus Erfahrung kann ich jetzt wirklich sagen, dass dies eine gute Methode ist. Ich habe auf diese Weise viele Merkwürdigkeiten (Pakete hängen von sich selbst ab, Pakete haben real existierende Pakete als Provides gesetzt, …) gefunden und viele Programmierfehler sind mir entgegengesprungen, die ich sonst hätte suchen müssen. Aus den vielen asserts kann ich jetzt notwendige Prüfungen auswählen und diese mit einer sinnvollen Ausgabe und einer ordentlichen Fehlerbehandlung versehen.

Modularisierung

Bei diesem Projekt habe ich wieder einmal gemerkt, dass eine saubere Trennung der Teile von sehr großem Vorteil ist. Ich habe versucht – an einigen Stellen musste ich es aber aufweichen –, konsequent die Phasen zu trennen: Datenbank einlesen, Graph aufbauen, Graph bearbeiten, Graph auswerten und gefundene Pakete ausgeben. Damit schlagen einerseits Änderungen in einem Bereich nicht unbedingt in den anderen durch (Änderung der Auswertereihenfolge ändert nicht das Ausgabeformat) und alles ist etwas robuster und andererseits wird der Code auch sauberer und besser verständlich.

Die eigentlichen Interna

Beim alten deborphan krankte alles an der Art, wie die Auswertung gemacht wurde. Die Pakete waren in einer linearen Liste gespeichert und diese wurde für jedes Paket nach entsprechenden Abhängigkeiten abgesucht. Der eigentlich Abhängigkeitsgraph wurde nie aufgebaut. Dies führte zu den Problemen,

Es wurden also nicht alle Möglichkeiten ausgeschöpft.

In der neuen Version erstelle ich wirklich den Graphen, indem ich von jedem Knoten a eine gerichtete Kante u (einen Zeiger) zu dem Knoten b ziehe, von dem der Knoten a abhängt, und eine weitere Kante v von b nach a für die Verbindung, dass b von a gebraucht wird. Damit kann ich zum Schluss einfach alle Knoten ablaufen und prüfen, ob es eine Kante für gebraucht‐werden gibt, und falls nicht, den Knoten als frei ausgeben.

Oder‐Verknüpfungen und Provides

Eine Oder‐Verknüpfung tritt auf, wenn ein Paket a das Paket b oder das Paket c benötigt. Um dies im meiner Datenstruktur nachzubilden habe ich Pseudoknoten mit dem Typ OR eingeführt, die ich später gesondert behandeln kann. Das Paket a hängt dann von dem OR‐Knoten ab und dieser hängt von den Paketen b und c ab.

Für Dienste wie mailer-daemon oder zum Ersetzen von anderen Paketen, kann ein Paket sagen, dass es dieses bereitstellt (Provides). Für die Auflösung von Abhängigkeiten ist dies wichtig, weil z. B. ein Programm von editor abhängen kann, aber es gibt kein echtes Paket editor. Stattdessen stellen die Pakete vim, emacs, … editor bereit. Diese Beziehung habe ich dadurch umgesetzt, dass ich einen Pseudoknoten vom Typ PROVIDES eingeführt habe. Der PROVIDES‐Knoten hängt dann vom eigentlichen Knoten ab und kann gleichzeitig von anderen genutzt werden.

Dabei ist mir dann aufgefallen, dass ich bei der Behandlung der beiden Typen keinen Unterschied machen brauche, was wiederum die Sache vereinfacht hat. Die Phase des Graphaufbaus habe ich also nochmal in erstellen der PROVIDES‐Knoten und setzen der Zeiger zerlegt.

Zyklen im Graphen

Wenn zwei oder mehr Pakete einen Zyklus bilden, d. h. a hängt von b ab und b hängt von a ab, kann man mit der einfachen Prüfung „Paket wird von keinem anderen benötigt“ nie diese Knoten finden. Sie sind immer als benötigt markiert, obwohl sie vielleicht ganz allein sind und als Paar gelöscht werden können; ein prominentes Beispiel: g++-3.3 und libstdc++5-3.3-dev. Der g++-3.3 wird vom alten deborphan nie als frei erkannt, obwohl er längst nicht mehr (im nichtstrengen Sinne) gebraucht wird.

Diese Zyklen bereiten selbst dem System Probleme und es gibt immer wieder den Vorstoß, diese zu verbannen. Für die Abhängigkeiten über Depends ist dies möglich. Doch sehr viele Zyklen finden sich auch auf der Recommends‐ und der Suggests‐Ebene und dafür benötigt deborphan Algorithmen zur Erkennung, denn diese werden immer existieren.

Auf die Idee für die Behandlung von Zyklen hat mich irgendwann mal Anke gebracht: Ich fasse einfach die an einem Zyklus beteiligten Pakete zusammen – kollabiere sie sozusagen. Das lässt sich zwar nicht direkt umsetzen, aber ich habe die Idee dadurch verwirklicht, dass ich einen weiteren Pseudoknotentyp JOIN eingeführt habe. Wenn zwei (oder mehr) Pakete a und b und an einem Zyklus beteiligt sind, dann erzeuge ich einen JOIN‐Knoten, der von den beiden Knoten abhängt. Die Knoten, die von a oder b abhängen, hängen dann von den neuen Knoten ab und die Abhängigkeiten der Knoten untereinander werden gelöscht.

Der Algorithmus zum Auffinden solcher Zyklen ist recht primitiv: In jedem Knoten prüfe ich, ob in der Liste der Abhängigkeiten ein Knoten steht, der auch in der Liste der Benutzer (die, die den Knoten brauchen) steht. Wenn dann ein JOIN‐Knoten nicht mehr benötigt wird, sprich kein weiteres, außer die am Zyklus beteiligten Pakete, verwendet eines der Pakete, dann können alle gemeinsam gelöscht werden. Der Standardalgorithmus wird zwar nicht die einzelnen Pakete erkennen, aber er wird den JOIN‐Knoten finden und kann entsprechend reagieren.

Probleme mit den Pseudoknoten

Beim Zusammenfassen der Abhängigkeiten für JOIN‐Knoten werden Informationen vernichtet – die genaue Zuordnung der Abhängigkeiten wird zusammengemischt/verwässert. Jedoch sind diese Informationen für das Auflösen der OR‐ und PROVIDES‐Konten notwendig. Ich habe einige Zeit lang gerätselt, wie man dies am Besten bewerkstelligen kann, denn beim Auflösen der OR‐ und PROVIDES‐Knoten bevorzuge ich u. a. Knoten mit höherem Benutzungsgrad. Ein Paket, das an einem Zyklus beteiligt ist, wird dann bevorzugt, obwohl es eigentlich benachteiligt seien sollte, weil mehr als ein Paket gelöscht werden könnte.

Eine derartige Situation findet sich um pdf-viewer. Die Pakete gv, evince und xpdf-utils stellen alle das Paket pdf-viewer bereit. Bei der Entscheidung, welches dieser Paket als Repräsentant für pdf-viewer verwendet wird, wird xpdf-utils bevorzugt, weil es von xpdf-common benötigt wird. Aber die Kombination xpdf-common und xpdf-utils kann gelöscht werden und es sollte gv oder evince gewählt werden.

Damit tut sich aber eine Zwickmühle auf: Einerseits sollte man erst die Zyklen zusammenfassen, um für die PROVIDES‐Knoten bessere Entscheidungen treffen zu können, und andererseits kann man nach dem Zusammenfassen eines PROVIDES‐Knoten nicht mehr sagen, wer dessen Benutzer ist – diese wurden mit den Benutzern der anderen Knoten im JOIN zusammengefasst.

Ich habe das Problem so gelöst, dass das Zusammenfassen von Zyklen in zwei Schritten geschieht: Zuerst werden alle Zyklen zusammengefasst, an denen kein OR‐ oder PROVIDES‐Knoten beteiligt ist. Danach werden die OR‐ und PROVIDES‐Knoten aufgelöst und dann ein weiteres Mal nach Zyklen gesucht.

Die gs‐Familie bildet z. B. eine Zyklus über den PROVIDES‐Knoten: gs-gpl bietet gs an und hängt von gs-common ab, gs-common hängt von gs ab. Das ist ein Zyklus über drei Knoten. Noch verzwickter ist die Situation, wenn gs-esp und gs-afpl beteiligt sind, denn diese bieten ebenfalls gs an und hängen von gs-common ab. Selbst auf dem Papier kann ich nicht sagen, was man hier sinnvoll zusammenfassen sollte.