C++ bietet standardmäßig keine automatische Speicherverwaltung. C++ ermöglicht die Verwaltung von dynamischem Speicher unter anderem mit den Operatoren new und delete. Objekte, die mit new angelegt werden, müssen mit delete explizit freigegeben werden.

Als kleine Übung in C++ habe ich eine einfache Garbage Collection implementiert. Sie hat nicht alle Fähigkeiten der Speicherverwaltung von Java oder von C#, dass würde den Rahmen einer Übung sprengen, dafür ist sie aber ziemlich einfach und erfüllt die für mich wichtigste Aufgabe einer Garbage Collection – die nicht erreichbaren Objekte zu löschen.

Bevor ich mit dem Basteln anfange, sollte ich paar Termine definieren und paar Designentscheidungen erklären.

1. Speicher und die Lebenszyklen von Objekten

In C++ gibt es verschiedene Speicherbereiche, in denen Objekte leben können. Zuerst gibt es den statischen Speicher. Hier leben die globalen Variablen, die statischen Member von Klassen und die statischen Variablen von Prozeduren. Die Lebensdauer dieser Objekte entspricht, vereinfacht gesagt, der Ausführungszeit der Anwendung.

Dann gibt es den automatischen Speicher – der Stack. Hier leben die lokalen Variablen und Parameter der Prozeduren. Die Lebensdauer dieser Objekte ist bestimmt durch die Ausführungsdauer der Prozedur.

Und schließlich gibt es da den dynamischen Speicher – den Heap, mit dem sich unsere Garbage Collection beschäftigen wird. Die Lebensdauer der Objekte auf dem Heap wird explizit von dem Programm gesteuert. Durch new werden Objekte auf dem Heap angelegt, durch delete werden sie gelöscht. Vergisst man die angelegten und nicht mehr gebrauchten Objekte zu löschen, entsteht ein Speicherleck. Löscht man Objekte, die noch gebraucht werden vorzeitig, entsteht ein dangling Pointer. (Ich würde hier gerne ein deutsches Wort benutzen, aber anscheinend gibt es keine Einigkeit, wie „dangling pointer“ ins Deutsche übersetzt wird – wilder Zeiger, hängender Zeiger, ... – keine der Varianten gilt als die Übersetzung)

Meine Zielsetzung ist, eine kleine Bibliothek bereitzustellen, die sich darum kümmert, dass auf dem Heap angelegten Objekte zur richteigen Zeit gelöscht werden.

2. Speicherblock oder Objekt?

Zusätzlich, zu der Frage, ob ein Objekt auf dem statischen, dem automatischen oder dem dynamischen Speicher „lebt“, ist eine weitere Frage sehr wichtig: Lebt das Objekt auf einem Speicherblock, der ganz dem Objekt „gehört“ oder ist das Objekt nur ein Teil einer größeren Struktur? Ist es ein Member eines anderen Objektes, oder ist es ein Element eines dynamisch angelegten Arrays?

Diese Frage ist deswegen wichtig, weil nur Objekte, die mit new angelegt wurden, auch mit delete gelöscht werden dürfen. Objekte, die z.B. Elemente eines Arrays sind, werden gelöscht, wenn das Array mit delete[] gelöscht wird, Objekte, die Teile eines anderes Objektes sind, werden zusammen mit dem größeren Objekt gelöscht.

Die hier gebastelte Garbage Collection kann ausschließlich Objekte löschen, die mit new angelegt werden – nicht Objekte, die Teile solcher Objekte sind, und sie kann auch keine dynamisch angelehten Arrays löschen.

An dieser Stelle muss ich die erste Designentscheidung treffen:

Q1: Wer soll sich darum kümmern, dass die Garbage Collection erkennt, ob ein Objekt mit new angelegt worden ist? Die Bibliothek selbst, oder der Entwickler, der sie benutzt?

Wie gerne würde ich sagen, dass diese Aufgabe die Bibliothek übernimmt. Das Problem ist, dass es keine elegante Methode gibt, die plattformunabhängig bestimmten kann, ob ein Objekt mit new angelegt worden ist. Es wäre zwar möglich, komplett eigene Speicherverwaltung zu implementieren, aber das ist nicht mein Ziel bei dieser Übung. Also lautet meine Entscheidung:

D1: Der Benutzer der Bibliothek ist dafür zuständig, dass die von der Garbage Collection verwalteten Objekte mit new angelegt worden sind.

Wie das implementiert wird, werde ich gleich erklären.

3. Erreichbarkeit

Ich will, dass die Garbage Collection die Objekte löscht, die von der Anwendung nicht mehr erreichbar sind.

Um auf ein Objekt zugreifen zu können, braucht ein C++ Programm die Adresse des Objektes. Das Programm kennt implizit die Adressen der statischen und automatischen Variablen, die Adressen der dynamisch angelegten Objekte muss das Programm in Zeigern (Pointer) speichern.

Ich nenne ein Objekt direkt erreichbar wenn eins statische oder automatische Pointer- oder Referenz-Variable auf das Objekt zeigt. Ein Objekt ist erreichbar wenn es entweder direkt erreichbar ist, oder ein Pointer bzw. eine Referenz von einem erreichbaren Objekt auf das Objekt zeigt.

Wenn ich also eine lokale Pointer-Variable pA habe, dann ist das Objekt A, auf das pA zeigt, direkt erreichbar, und ein Objekt B auf das pA->pB zeigt ist indirekt erreichbar.

Ein Objekt ist referenziert wenn überhaupt ein Pointer darauf zeigt. Objekte die nicht referenziert sind, sind natürlich nicht erreichbar. Es kann aber Objekte geben, die zwar referenziert sind, aber nicht erreichbar. Wenn z.B. ein Objekt mit einem Member auf sich selbst zeigt, ist es zwar referenziert, wenn aber kein anderer Pointer auf das Objekt zeigt, ist es trotz der Referenz nicht von dem Programm erreichbar.

4. Reference Counting

Fangen wir ganz einfach an. Ein Objekt das nicht referenziert wird, ist nicht erreichbar, und kann gelöscht werden. Es reicht also aus, die Pointer, die auf ein Objekt zeigen zu zählen, und wenn die Zahl 0 ist, wird das Objekt gelöscht.

Das ist natürlich nur Teillösung der Aufgabe. Mit dieser Strategie werden zwar nur Objekte gelöscht, die nicht erreichbar sind (also entstehen keine dangling Pointer), aber es werden nicht alle solche Objekte gelöscht. Wir können also immer noch Speicherlecks haben.

Nächste Designentscheidung:

Q2: Sollen alle Pointer gezählt werden? Und wie wird die Anzahl der Pointer, die auf ein Objekt zeigen, ermittelt?

D2: Es werden nicht alle Pointer gezählt; wir werden spezielle „Smartpointer“ implementieren. Die Anzahl der Referenzen wird in dem Zielobjekt gespeichert und von den Smartpointern manipuliert werden.

Es wäre ziemlich schwierig alle Pointer zu überwachen. Um so was zu implementieren, müssten wir eigentlich den ganzen zugreifbaren Speicher der Anwendung scannen, und jede Bytefolge, die auf unser Objekt „zeigt“ in Betracht ziehen. Das würde den Rahmen der Übung sprengen. Es gibt Gargabe Collections für C++, die genau das machen.

Der Entwickler, der mit unserer Bibliothek arbeiten möchte, wird also statt der gewöhnlichen C++ Pointern unsere Smartpointer benutzen müssen, wenn die Lebensdauer des Objektes durch diese Garbage Collection verwaltet werden soll.

Die verwalteten Zielobjekte werden eine zusätzliche Membervariable enthalten müssen, in der die Anzahl der Referenzen gespeichert wird.

Der Anwender ist selbst dafür verantwortlich, dass die Objekte mit new angelegt werden und mit delete gelöscht werden können.

Die Membervariable m_nRefCount in der die Anzahl der Referenzen zu dem Objekt gespeichert wird, gehört nicht zu dem Zustand des Objektes. Sie enthält nur die Information über Beziehungen anderer Objekte zu dem Zielobjekt. Das hat subtile aber wichtige Konsequenzen:

• Die Memebervariable m_nRefCount wird als mutable deklariert. Denn die Anzahl der Referenzen auf ein konstantes Objekt kann sich auch ändern.
• Die Memebervariable m_nRefCount darf weder mit dem Kopierkonstruktor noch mit dem Zuweisungsoperator in ein anderes Objekt kopiert warden.

Ein Quelltext sagt mehr als dieses Geschwafel? Na gut, hier ist die erste Version: Quelltext 1

Selbstschutz

Der Benutzer der Biblithen ist dafür verantwortlich, dass die Objekte, deren Lebensdauer von von der refernzzählenden Garbage Collection verwaltet werden soll, von RefCounted abgeleitet sind und dass für den Zugriff auf die Objekte statt der normalen C++ Pointern die Smartpointer verwendet werden.

Wir sollten aber einen wichtigen Pointer, der sich nicht so einfach durch einen anderen ersetzen lässt, nicht vergessen. Ich meine den this-Pointer, der auf das Objekt zeigt, dessen Methode gerade ausgeführt wird. Wenn während der Ausführung der Methode die Anzahl der Referenzen, die auf das this Objekt zeigen auf 0 sinkt, wird das Objekt gelöscht. Danach ist der Zugriff auf die Membervariablen oder die Tabelle der virtuellen Methoden des Objektes nicht mehr erlaubt. Das kann unangenehm sein. Um solche Situationen zu vermeiden, reicht es aber am Anfang der Methode einen referenzzählenden Pointer, der auf this zeigt zu deklarieren RefCountedBase protectThis(this);. Damit stellen wir sicher, dass während der Ausführung der Methode die Anzahl der Referenzen nie auf 0 sinkt. Das Objekt, wenn es nirgendwo sonst referenziert wird, wird also erst nach der Ausführung der Methode gelöscht.

Haben wir damit alle Probleme beseitigt? Fast. Es gibt zwei spezielle Methoden, in denen wir das aktuelle Objekt nicht so schützen können. Es sind der Konstruktor und der Destruktor. Während das Objekt konstruiert wird, ist seine Referenzzahl 0, würden wir eine lokale Variable RefCountedBase protectThis(this); anlegen, würden die Methoden addRef und am Ende release aufgerufen. Das würde dazu führen, dass das Objekt sofort nach dem Erstellen wieder gelöscht würde.

Bei einem Destruktor ist die Situation ähnlich. Der Destruktor wird aufgerufen, wenn das Objekt gelöscht wird, und dann ist die Anzahl der Referenzen gleich 0. Wenn wir im Destruktor addRef und dann release aufrufen würden, würde es zum doppelten delete this führen. Und das ist ein Fehler.

Wenn wir also auf das gerade konstruierte oder destruierte Objekt mit einem referenzzählenden Pointer zeigen wollen, müssen wir das Objekt anders schützen. Wir müssen am Anfang die Anzahl der Referenzen inkrementieren (addRef) am Ende müssen wir sie wieder dekrementieren, ohne aber delete this aufzurufen, wenn die Anzahl auf 0 sinkt.

Mit der aktuellen Implementierung ist das nicht möglich (m_nRefCount und addRef sind ja privat) deswegen ändern wir sie. Wir erzeugen eine geschützte friend Klasse, ProtectConstructor die im ihren Konstruktor m_nRefCount inkrementiert und im ihren Destruktor dekrementiert, ohne allerdings das Objekt zu löschen.

Um einen Konstruktor oder Destruktor zu schützen, müssen wir also auf dessen Anfang nur eine Variable ProtectConstructor protectThis(this); deklarieren.

Der angepasste Quelltext ist Quelltext 2.

(Der echte Quelltext in der Bibliothek unterscheidet sich ein wenig von dieser Version. Er ist in *.h und *.cpp Dateien verteilt, ist kommentiert und enthälht Unit-Tests)

Die zum Scheitern verurteilte Selbstrettung

In letzter Mikrosekunde des Lebens eines Objektes könnte das Objekt versuchen sich zu retten, indem es z.B. im Destruktor einem globalen Smartpointer seine eigene Adresse zuweisen würde. Das kann in C++ nicht funktionieren, das Objekt wird bereits gelöscht, und kann nicht mehr gerettet werden. Der globale Pointer würde so zu einem Dangling Pointer werden. Um solche Fehler zu erkennen, enthält der Destruktor der Klasse RefCounted eine Zusicherung ASSERT(0 == m_nRefCount).

In Java oder in C# kann sich ein Objekt auf diese Weise vor dem Löschen retten. Das liegt daran es in diesen Sprachen keine Destruktoren, sondern Finalizer gibt. In C++ wird der Destruktor während des Löschvorganges aufgerufen. In Java bzw. C# wird der Finalizer vor dem Löschen der aufgerufen (grob vereinfacht beschrieben)

Im Teil 2 beschreibe ich die hierarchische Referenzzählung.
Im Teil 3 schließlich die Erkennung von Zyklen.
Die Bibliothek ist aber bereits jetzt komplett.

Die C++-Quelltexte habe ich mit diesem netten Tool von C++ zu HTML konvertiert.

Interessante Links zum Thema GarbageCollection.