Speicherzuordnung bei verlinkter Liste

[Dario Linsky]

Hallo,

ich habe hier folgendes Struct, mit dem ich eine einfach verlinkte Liste aufbauen soll:

struct item {
  char data[9];
  struct item *next;
};

struct item *root;

Neue Listenelemente werden über die Funktion append_item angehängt:

void append_item(char data[]) {
  struct item *ptr;
  
  if (root == NULL) {
    root = malloc(sizeof(*root));
    strcpy(root->data, data);
    root->next = NULL;
  } else {
    ptr = root;
    while (ptr->next != NULL)
      ptr = ptr->next;
    
    ptr->next = malloc(sizeof(*ptr));
    ptr = ptr->next;
    strcpy(ptr->data, data);
    ptr->next = NULL;
  }
}

Wenn ich das ganze mit gcc (unter Linux) kompiliere und mit gdb laufen lasse, dann ist laut sizeof das Struct 16 Byte groß. Wenn ich mir aber die Speicherstellen der Listenelemente ansehe, dann ist der Versatz zwischen den einzelnen Elementen 24 Byte groß. Ändere ich die Länge von data auf 20 Byte, ist das Struct insgesamt 24 Byte groß, der Versatz wächst aber auf 32 Byte an.

Obwohl das Struct also immer ein Vielfaches von 8 Byte im Speicher belegen würde, hängt das Betriebssystem immer noch 8 Byte an. Diese sind übrigens auch nicht vollständig leer (in Form von Null-Bytes), sondern enthalten zum Teil irgendwelche Steuerzeichen. Wenn ich den Code ohne Debugging-Informationen kompiliere, bleibt der Effekt trotzdem bestehen.

Ausgabe im Debugger:

(gdb) p sizeof(struct item)
$2 = 16
(gdb) p ptr
$3 = (struct item *) 0x804a008
(gdb) p *ptr
$4 = {name = "Element 1", next = 0x804a020}
(gdb) p (char[24]) *root
$5 = "Element 1\000\000\000 ?\004\b\000\000\000\000\031\000\000"

Ich kann nicht nachvollziehen, ob sich das auf anderen Betriebssystemen ähnlich verhält, aber zumindest auf Windows Vista mit VS 9.0 soll das ebenfalls auftreten.

Jetzt meine Frage: Warum ist das Struct immer um 8 Byte größer, als sizeof anzeigt, selbst wenn die Speicherausrichtung für das Struct schon ein Vielfaches von 8 Byte alloziert? Und was für Daten liegen da in den zusätzlichen 8 Byte, die "zwischen" den einzelnen Listenelementen alloziert werden?

Danke im Voraus.

Grüße, D.

 

[Beichtpfarrer]

Wenn du mit malloc allozierst, kannst du dir nicht sicher sein, an welcher Stelle die reservierten Speicherstellen liegen.
Die müssen nicht aufeinanderfolgend sein. Es kann auch ein später reserviertes Objekt eine geringere Speicheradresse haben.
Das hängt nicht mit der Größe deines structs zusammen.
Es ist schlicht und einfach nicht definiert.

Wofür malloc den extra-Platz vebraucht?
Da kann ich nur raten. Vielleicht interne Daten, die Informationen über den reservierten Speicherbereich enthalten (zB Größe). Oder auch extra-Platz, damit Speicher nicht in jedem Fall neu beansprucht werden muss, falls du dich später entschließt, deinen Speicherbereich per realloc() zu vergrößern..
Das wird sich sowieso von Plattform zu Plattform unterscheiden, also programmiere lieber, ohne darüber nachzudenken.