Jutta Degener, November 1994 Zurück zu Unix1

Dynamische Speicherverwaltung in C und Unix

Bevor wir uns mit den Funktionen zur dynamischen Speicherverwaltung in C beschäftigen, sollten wir uns kurz über das Gegenteil klarwerden; das heißt über die Mechanismen, die bei der Deklaration von Variablen in C implizit ihre Lebensdauer bestimmen.

Lebensdauer

Jedes Objekt in der Sprache C hat eine Lebensdauer (englisch: duration). Diese Lebensdauer sagt, wann für das Objekt Speicherplatz reserviert ist; wann man also überhaupt darauf zugreifen darf. Pro Objekt - pro Stück Speicher - liegt diese Eigenschaft immer fest; sie kann sich nicht zur Laufzeit plötzlich ändern.

Objekte, die durch Variablendefinitionen oder Stringkonstanten entstanden sind, können zwei verschiedene Arten Lebensdauer haben: statisch und automatisch.

Statische Lebensdauer haben Stringkonstanten; Objekte in Variablen, die ausserhalb von Funktionsblöcken definiert werden; und Objekte in Variablen, die (außerhalb oder innerhalb einer Funktion) mit dem Schlüsselwort static definiert werden.
```
    static int a;
    float * b;

    main()
    {
        static char c[80];
        return 0;
    }
```
Die Bytes, die sich hinter a und b und c verbergen, sind während der gesamten Laufzeit des Programms vorhanden. Sie werden vor dem Aufruf von main() vom Laufzeitsystem mit jeweils zum Typ der Variable passenden Nullwerten initialisiert, und erst nach Beendigung des ganzen Programmes zusammen mit dem restlichen vom Programm eingenommenen Speicher dem Betriebssystem zurückgegeben.
Objekte in automatischen Variablen dagegen sind in ihrer Lebensdauer an die Ausführung des Blocks gebunden, der ihre Definition enthält.
```
    f() {
        int a;
    }

    g() {
        float * b;
        f();
    }

    main() {
        char * c; 
        g();
        f();
    }
```
In diesem Beispiel existiert c, solange main() läuft; b gibt es, solange die Funktion g() ausgeführt wird; und a, solange f() läuft.
Eigentlich gibt es sogar zwei verschiedene a's: Eines, das existiert, wenn f() von g() aus aufgerufen wird; und eines, das beim Aufruf direkt von main() aus angelegt wird. (Wenn zwei Aufrufe von f() in main() stünden, gäbe es drei a's.)
Das ist ein wichtiger Unterschied zwischen automatischen und statischen Variablen: Bei statischen Variablen gibt es immer nur genau ein Objekt pro Definition; bei automatischen Variablen wird bei jedem Aufruf der umgebenden Funktion eine neue Variable erzeugt. (Für jemanden, der mit Pascal oder Modula vertraut ist, ist dieser Automatismus nichts Neues.)
Automatische Variablen werden in C nicht vom Compiler initialisiert; sie enthalten irgendwelchen Müll. Natürlich kann man sie als Programmierer ausdrücklich initialisieren:
```
    f() {
        int a = 5;
        float * b = (float *)0;
        char c[80] = "Hello, World!";
    }
```

C hat also einen Mechanismus, um Objekte in Variablen lange leben zu lassen; und einen Mechanismus, um dynamisch zur Laufzeit beliebig viele ``Abzüge'' derselben Variablen herzustellen. Wenn man aber beides braucht - beliebig viele Abzüge desselben Typs, die trotzdem länger leben als die Funktion, in der sie hergestellt werden - dann braucht man die Funktionen der dynamischen Speicherverwaltung.

Speichersegmente

Ein Programm, egal in welcher Sprache es geschrieben ist, greift mit Hilfe von Adressen auf Stellen im virtuellen Speicher zu. Das Programm steht irgendwo in diesem virtuellen Adreßraum; globale Variablen stehen da, und lokale Variablen ebenfalls. Die Bereiche, oder Segmente, auf denen die verschiedenen Arten von Daten und Programmtext liegen, haben verschiedene Namen

auf dem Stack liegen automatische Variablen;
das Programm steht im Textsegment, üblicherweise readonly.
im DatenSegment stehen vom Programmierer initialisierte Objekte mit statischer Lebensdauer;
im BSSSegment schließlich stehen Objekte mit statischer Lebensdauer, die vom LaufzeitSystem mit binären Nullen initialisiert werden.

Betriebssystem und Memory Management Unit arbeiten zusammen, um Zugriffe auf Addressen in diesen virtuellen Segmenten auf physikalische Speicherzugriffe abzubilden. Nicht alle Addressen sind gültig; nur ein kleiner Teil des großen virtuellen Adreßraumes ist tatsächlich an physikalische Speicherseiten gebunden. Diese Bindung läßt sich aber zur Laufzeit ändern: ein Programm kann das Betriebssystem bitten, physikalische Seiten zu alloziieren und an neue, bisher unbelegte virtuelle Speicherseiten zu binden.

Break und Heap.

Das Programm kann aber nicht beliebige Seiten anfordern; es kann nur die Grenze zwischen seinem Datensegment und dem unbelegten Speicher nach ``unten'' verschieben. (Aus historischen Gründen wächst dieser Speicher von ``oben'' nach ``unten''.) Diese Grenze heißt der Break (deutsch: Bruch); der durch Verschieben des Breaks gewonnenene Speicherbereich ist die Heap (deutsch: Halde, Haufen). (Manche sagen auch der Heap; das Heap habe ich noch nicht gehört; klingt mir zu sehr nach Seefahrt.)

Mit dem brk() SystemCall setzt ein Programm den Break auf eine bestimmte Speicheradresse; der sbrk() SystemCall inkrementiert oder dekrementiert den Break um die angegebene Distanz.

   caddr_t sbrk(int incr);
   int brk(caddr_t addr);

Diese SystemCalls können natürlich auch scheitern. Physikalischer und virtueller Speicher sind begrenzt; zusätzlich gibt es seit ein paar Jahren auch von außen festlegbare Grenzen für den Speicherplatz, den ein einzelner UserProzeß verbrauchen kann. Wie Rechenzeit und Plattenplatz ist eben auch Hauptspeicher eine Ressource, die ein Multiusersystem verwalten und einteilen muß.

Die Funktionen sbrk() und brk() sind nicht Teil der StandardCBibliothek, sondern Unixspezifisch. Wenn man sie sieht, sollte man sie erkennen; aber ihr braucht sie nicht zu benutzen.

void * malloc(size_t size)

Auf der Grundlage von sbrk() und brk() hat man komfortablere Funktionen geschrieben, mit denen CCode Speicherstücke dynamisch anfordern und auch wieder freigeben kann. Man sagt, diese Funktionen ``verwalten die Heap'' (oder ``den Heap''). Sie lassen sich mit einem geschickten Händler vergleichen, der seine Ware in großen Stücken vom Großhändler (dem Betriebssystem) einkauft, und in kleine, mundgerechte Stücke zerteilt weitergibt.

Die Funktion malloc() liefert einen Zeiger auf ein Stück Speicher der vom Aufrufer gewünschten Größe.

   void * malloc(size_t size);

Sie und die anderen Speicherverwaltungsfunktionen, die ab jetzt vorgestellt werden, und der Typ ihres Arguments, werden alle im gleichen HeaderFile definiert, in <stdlib.h>.

   #include <stdlib.h>
   main()
   {
       char * buf = (char *)malloc(80);
               ...
       return 0;
   }

Der Speicher, den malloc() zurückliefert, ist uninitialisiert - enthält also Müll, ähnlich wie automatische Variablen.

Sizeof und size_t

Der Typ des Parameters von malloc(), size_t, ist der Resultattyp des Operators sizeof. sizeof ist fest in C mit eingebaut; aber der Typ size_t wird in erst in den HeaderFiles <stddef.h> und <stdlib.h> definiert. (Einer von beiden reicht; beide zusammen stören sich nicht.) Man kann sizeof() benutzen, ohne <stddef.h> #included zu haben, aber wenn man tatsächlich eine Variable vom Typ size_t deklarieren will, braucht man das HeaderFile.

Zeiger auf void

Der Resultattyp von malloc() hat einige Eigenschaften, die ihn von anderen Datentypen unterscheiden.

Jeder Zeiger auf ein CObjekt läßt sich einen void * umwandeln (``casten''), und wieder zurück.
Man darf einen Zeiger auf void einem anderen ObjektzeigerTyp zuweisen und umgekehrt, braucht die Umwandlung also nicht explizit hinzuschreiben. Mein Beispiel oben hätte also auch lauten können:
```
   #include <stdlib.h>
   main()
   {
       char * buf = malloc(80);
               ...
       return 0;
   }
```
void * und char * sehen gleich aus. Beide Datentypen brauchen dieselbe Anzahl von Bytes, und dieselben Bits in diesen Bytes bedeuten bei beiden dasselbe. Das ist wichtig, weil void * eine Neuerung von ANSI C ist; es gibt viele alte Funktionen, die früher mit char * aufgerufen wurden, und jetzt mit void * benutzt werden; malloc() ist nur eine von ihnen.

Alignment

Datentypen haben nicht nur eine Größe, sie brauchen auch ein bestimmtes Alignment (deutsch: Ausrichtung). Die Anfangsadresse eines Objektes mit einem Alignment muß immer auf einem Vielfachen dieser Zahl liegen; tut sie das nicht, gibt's beim Zugriff einen bus error. Das Alignment ist eine kleine Zahl, meist 2, 4, oder 8, und hängt von der Hardware des Rechners und den Entscheidungen des Compilerautors ab.

Der Speicher, den malloc() liefert, ist maximal aligned - in ihm kann man also ein beliebiges Objekt anlegen und dann darauf zugreifen. Würde man sich dieselbe Menge Speicher vom CCompiler besorgen (zum Beispiel als ein Array von char), gäbe es diese Garantie nicht.

   #include <stdlib.h>
   main()
   {
        double * p;
        char array[sizeof(double) + 1];

        p = malloc(sizeof(double) + 1);
        *p = 3.14;                      /* geht */ 

        p = (void *)((char *)p + 1);
        *p = 3.13;                      /* bus error */

        p = (void *)(array + 1);
        *p = 3.12;                      /* bus error */
   }

void free(void *)

Was ist die Lebensdauer von mit malloc() alloziiertem Speicher? Weder statisch noch automatisch, sondern dynamisch - er ist so lange reserviert, bis bis das Programm terminiert, oder bis er mit free() wieder freigegeben wird.

   #include <stdlib.h>
   main()
   {
       char * buf = malloc(80);
               ...
       free(buf);
       return 0;
   }

Dabei wird der Speicher meist nicht an das Betriebssystem zurückgegeben, sondern nur in den internen Strukturen der HeapVerwaltung als ``frei'' vermerkt.

Buchhaltung

Beim Aufruf von free() wird die Größe des Speicherblocks nicht mit übergeben. Woher weiß free(), auf wieviel Speicher der Zeiger zeigt? Die dynamische Speicherverwaltung merkt sich das in ihren eigenen Strukturen. Oft funktioniert das so, daß vor einem alloziierten Block im Speicher ein paar Verwaltungsinformationen der Speicherverwaltung stehen: die Größe des alloziierten Blocks in Bytes und vielleicht ein paar Zeiger für eine verkette Liste von belegten Blöcken mit ähnlicher Größe. Diese Informationen werden beim malloc() an die richtige Stelle geschrieben; free() liest sie wieder aus, und weiß so sofort, was es mit dem Block anfangen kann. Der CCode, der malloc() und free() benutzt, schreibt nur hinter den Zeiger - und so bleibt die Verwaltungsinformation erhalten.

Daraus folgen zwei wichtige Details:

Wenn ein Programm aus Versehen diese Zeiger und Größen überschreibt - weil es zum Beispiel über das Ende eines Arrays hinweg in die Verwaltungsinformationen vor dem Anfang des nächsten gemalloc()ten Arrays schreibt - dann kann das Programm das möglicherweise erst sehr viel später, an einer ganz anderen Stelle, zu spüren bekommen.
Es ist gar keine gute Idee, an free() Speicher zu übergeben, der nicht mit malloc() angelegt wurde. malloc() macht eben doch mehr, als nur ein paar Bytes zu holen - es bindet diese Bytes auch in Datenstrukturen ein. Der Compiler und das Betriebssystem, die die ``rohen'' Bytes auf dem Stack und im Datensegment reservieren, wissen von diesen Datenstrukturen nichts; für sie sind die Zeiter und Größen der Speicherverwaltung nur Applikationsdaten wie alle anderen auch.

void * realloc(void * old, size_t size)

Oft weiß man nicht von vorneherein, wie groß ein Array wird. Man kann dann eine Maximalgröße festsetzen und abbrechen, wenn die überschritten wird; man kann auf andere, ``lockerere'' Datenstrukturen wie zum Beispiel verkettete Listen ausweichen; oder man kann versuchen, das Array dynamisch zu realloziieren, den Speicherbereich also den Bedürfnissen anzupassen. Das macht realloc().

   #include <stdlib.h>
   main()
   {
       char * buf = malloc(80);
               ...
       buf = realloc(buf, 160);
               ...
       free(buf);
       return 0;
   }

Wenn es geht, versucht realloc(), am Ende des alten Blocks noch freien Speicher zu finden und den Block so zu verlängern; in diesem Fall liefert realloc() dieselbe Adresse zurück, mit der es aufgerufen wurde. Ist nicht genug Speicher frei - weil an der Stelle schon ein anderes, gemalloc()'tes Objekt steht - so alloziiert realloc() einen ganz neuen Block woanders, kopiert das alte Objekt dort hin, gibt den alten Speicher frei, und liefert einen Zeiger auf den neuen Speicher zurück. Es funktioniert also wie eine Mischung aus free(), malloc(), und einer Kopieranweisung.

Bei einem realloc() kann ein dynamisches Objekt also umziehen. Die Zeiger auf das Objekt machen diesen Umzug nicht automatisch mit; ihr müßt sie selbst auf den neuen Wert setzen.

Korrekturen bitte per Email an Jutta Degener, jutta@cs.tu-berlin.de.