Wie implementiert man einen plattformunabhängigen Garbage Collector?

Question

Im Grunde bin ich daran interessiert, ein plattformunabhängig Garbage Collector in C wahrscheinlich unter Verwendung des Mark-and-Sweep-Algorithmus oder einer seiner gängigen Varianten. Im Idealfall würde die Schnittstelle nach folgendem Muster funktionieren:

(1) gc_alloc() weist Speicher zu

(2) gc_realloc() ordnet Speicher neu zu

(3) gc_run() führt den Garbage Collector aus.

Ich habe bereits einen Blick auf die libgc Garbage-Collection-Bibliothek, die von Boehm et. al. entwickelt wurde, aber sie ist nicht plattformunabhängig; sie wurde lediglich auf viele verschiedene Systeme portiert. Ich würde gerne einen Garbage Collector implementieren, der keinen systemabhängigen Code enthält. Geschwindigkeit ist kein riesig Problem.

Irgendwelche Vorschläge?

Answer 1

Leider ist es nicht wirklich möglich, eine wirklich plattformunabhängigen Garbage Collector in C. Bei strenger Auslegung des C-Standards kann jeder Typ (außer unsigned char ), um Trap-Bits zu haben - Bits, die, wenn sie den falschen Wert haben, dazu führen, dass das System eine Ausnahme (d.h. ein undefiniertes Verhalten) meldet. Wenn Sie zugewiesene Blöcke nach Zeigern durchsuchen, haben Sie keine Möglichkeit festzustellen, ob ein bestimmter Speicherblock einen legalen Zeigerwert enthält oder ob er einen Trap auslöst, sobald Sie versuchen, den Wert in ihm zu betrachten.

Die Betrachtung von Zeigern als ints hilft auch nicht weiter - kein int-Typ muss eine Darstellung haben, die mit einem Zeiger kompatibel ist. intptr_t ist nur auf sehr aktuellen Compilern verfügbar, und ich glaube nicht, dass seine Vertretung muss ebenfalls kompatibel sein. Und ints können auch Trap-Bits haben.

Sie kennen auch nicht die Anforderungen an die Ausrichtung von Zeigern. Auf einer Plattform, auf der Zeiger keine Ausrichtungsanforderungen haben (d.h., sie können an jedem Byte beginnen), bedeutet dies, dass Sie an jedem Byte anhalten müssen, memcpy in einen geeigneten Zeigertyp umwandeln und das Ergebnis untersuchen. Oh, und verschiedene Zeigertypen können auch unterschiedliche Darstellungen haben, was ebenfalls unvermeidlich ist.

Aber das größere Problem ist die Suche nach dem Root-Set. Bohem GC und die anderen neigen dazu, den Stack und die statischen Daten nach Zeigern zu durchsuchen, die in das Root-Set gehören. Dies ist ohne Kenntnis des Speicherlayouts des Betriebssystems nicht möglich. . Der Benutzer muss also die Mitglieder des Root-Sets explizit markieren, was den Sinn eines Garbage Collectors in gewisser Weise zunichte macht.

Kurz gesagt, Sie können einen GC nicht in wirklich tragbare C. Im Prinzip können Sie das, wenn Sie einige Annahmen treffen:

• Gehen Sie davon aus, dass der Root-Satz Ihnen ausdrücklich vom Benutzer übergeben wird.
• Angenommen, es gibt keine Trap-Bits in Zeiger- oder int-Darstellungen.
• Angenommen, intptr_t ist verfügbar oder alle annehmen void * s streng geordnet sind (d.h., < y > vernünftig mit Zeigern aus verschiedenen malloc ationen)
• Angenommen, alle Datenzeigertypen haben eine Darstellung, die mit void * .
• Optional, aber ein großer Geschwindigkeitszuwachs: Hardcode für die Ausrichtung von Zeigern (dies ist bei weitem nicht universell und muss compiler- und plattformspezifisch sein) Diese Annahme ermöglicht es Ihnen, die memcpy Zeiger auf einen bekannten Speicherort und reduziert die Anzahl der zu prüfenden Zeiger.

Wenn Sie diese Annahmen treffen, sollten Sie in der Lage sein, einen konservativen Mark-Sweep-Allokator zu erstellen. Verwenden Sie einen binären Baum, um Informationen darüber zu erhalten, wo sich die Zuweisungen befinden, und durchsuchen Sie jede mögliche ausgerichtete Zeigerposition in zugewiesenen Blöcken nach Zeigern. Die Notwendigkeit, den Root-Satz explizit anzugeben, macht das Ganze jedoch sinnlos - es wird malloc y free wiederholen, mit der Ausnahme, dass Sie es für eine bestimmte, nicht näher definierte Gruppe von Objekten überspringen können. Das ist nicht genau das, was GC bieten soll, aber ich nehme an, dass es z.B. als Teil einer virtuellen Maschine seinen Platz haben könnte (in diesem Fall würde der Root-Satz aus Informationen abgeleitet, die der virtuellen Maschine zur Verfügung stehen).

Beachten Sie, dass dies alles nur gilt für konservativ GCs - d.h. solche, die blind arbeiten und nach Zeigern in Daten suchen, ohne zu wissen, wo diese sein könnten. Wenn Sie an einer VM arbeiten, ist es viel einfacher - Sie können einen einheitlichen Datentyp für alle Zuweisungen durch die VM erstellen, der explizit auflistet, wo Zeiger gefunden werden können. Damit und mit einem expliziten Root-Set können Sie eine nicht-konservative GC aufbauen; dies sollte für den Aufbau einer VM oder eines Interpreters ausreichen.

Answer 2

Für einen Mark-and-Sweep-Algorithmus muss man eigentlich nur berechnen, welche Objekte von der Wurzelmenge aus erreichbar sind, oder? (Es ist schon eine Weile her, seit ich mich damit beschäftigt habe...)

Dies könnte durch einen separaten Objektgraphen für GC-verwaltete Objekte verwaltet werden, und Sie müssten "nur" Funktionen hinzufügen, um diesen Graphen ordnungsgemäß zu verwalten, wenn Sie verwaltete Objekte zuweisen oder ändern. Wenn Sie außerdem eine Referenzzählung für verwaltete Objekte hinzufügen, wäre es einfacher zu berechnen, welche Objekte direkt über Stack-Referenzen erreichbar sind.

Dies sollte wahrscheinlich möglich sein, ziemlich plattformunabhängig zu schreiben, obwohl es fraglich sein könnte, ob dies ein echter Garbage Collector wäre.

Einfacher Pseudocode, um zu zeigen, was ich mit Referenzzählung und Graphmanagement meine:

some_object * pObject = gc_alloc(sizeof(some_object));
some_container * pContainer = gc_alloc(sizeof(some_container));

pContainer->pObject = pObject;
/* let the GC know that pContainer has a reference to pObject */
gc_object_reference(pContainer, pObject);

/* a new block of some kind */
{
    /* let the GC know we have a new reference for pObject */
    some_object * pReference = gc_reference(pObject); 

    /* do stuff */
    ...

    /* let the GC know that this reference is no longer used */
    gc_left_scope(pReference);
}

gc_left_scope(pObject);
gc_run(); /* should not be able to recycle anything, since there still is a live
           * reference to pContainer, and that has a reference to pObject
           */