Implementing malloc() and free() — old memory reused first

Im vorherigen Beitrag dieser Serie zur Implementierung von malloc() und free() haben wir gezeigt, wie es möglich ist, Speicherblöcke wiederzuverwenden und den Heap zu reduzieren, indem neuere Blöcke freigegeben werden. Allerdings bringt die aktuelle Funktion ein subtiles Problem mit sich: Sie priorisiert die Wiederverwendung neuerer Blöcke, was mit der Zeit zu einem erhöhten Speicherverbrauch führen kann. Warum passiert das? Lass es uns aufschlüsseln.

Heap-Reduktion durch Wiederverwendung aktueller Blöcke

Stellen Sie sich das folgende Szenario vor. Zuerst weisen wir vier Speicherblöcke zu:

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

Die Speicherstruktur kann folgendermaßen visualisiert werden:

Jetzt geben wir den ersten und dritten Block frei...

abfree(ptr1);
abfree(ptr3);

…was zu folgender Struktur führt:

Dann weisen wir einen weiteren Block derselben Größe zu:

void *ptr5 = abmalloc(8);

Wenn die Funktion abmalloc() mit der Suche nach dem neuesten freien Block beginnt, verwendet sie den Block oben wieder. Wenn wir jetzt den letzten Block freigeben:

Wenn wir jetzt den letzten Block freigeben…

abfree(ptr4);

…wir können die Heap-Größe um nur einen 8-Byte-Block reduzieren, da der vorherige Block nicht mehr frei ist:

Wiederverwendung alter Blöcke

Stellen Sie sich nun das gleiche Szenario vor, jedoch mit einer Änderung: Unsere Funktion beginnt mit der Suche nach freien Blöcken ab dem ältesten Block. Die anfängliche Struktur wird dieselbe sein…

…und wieder geben wir den ersten und dritten Speicherblock frei:

Dieses Mal wird der erste Block wiederverwendet:

Wenn wir nun den letzten Block freigeben, haben wir oben zwei freie Blöcke, sodass wir den Heap um zwei 8-Byte-Blöcke reduzieren können:

Dieses Beispiel zeigt, wie wir durch die Bevorzugung neuerer Blöcke letztendlich alte ungenutzte Blöcke ansammeln, Speicher verschwenden und zu unnötigem Heap-Wachstum führen. Die Lösung besteht darin, die Suchstrategie zu ändern und der Wiederverwendung älterer Blöcke Vorrang einzuräumen.

Präferenz für alte Blöcke implementieren

Um dieses Problem zu lösen, fügen wir zunächst einen Zeiger auf den nächsten Block im Header hinzu. Wir werden auch einen globalen Zeiger auf den ersten Block erstellen, damit wir die Suche von dort aus starten können:

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;
Header *first = NULL;
Header *last = NULL;

Wir werden Speicherblöcke mit Headern in zwei verschiedenen Situationen erstellen, also nehmen wir eine kleine Umgestaltung vor: Wir werden diese Logik in eine Hilfsfunktion extrahieren, die den Header zuweist und initialisiert (einschließlich der Festlegung des Felds next mit NULL):

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header) + size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

Mit dieser neuen Funktion können wir die Logik in abmalloc():
vereinfachen

void *abmalloc(size_t size) {
  if (size == 0) {
    return NULL;
  }
  Header *header = last;
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false;
      return header + 1;
    }
    header = header->previous;
  }
  last = header_new(last, size, false);
  return last + 1;
}

Jetzt haben wir Zugriff auf den ersten und letzten Block und können bei einem gegebenen Block den vorherigen und nächsten herausfinden. Wir wissen auch, dass noch keine Blöcke zugewiesen wurden, wenn der Zeiger auf den ersten Block null ist. In diesem Fall weisen wir den Block also sofort zu und initialisieren sowohl den ersten als auch den letzten Block:

void *abmalloc(size_t size) {
  if (size == 0) {
    return NULL;
  }
  if (first == NULL) {
    first = last = header_new(NULL, size, false);
    return first + 1;
  }

Wenn firstit nicht mehr NULL ist, sind bereits Blöcke zugewiesen, sodass wir mit der Suche nach einem wiederverwendbaren Block beginnen. Wir werden die Variablenheader weiterhin als Iterator verwenden, aber anstatt mit dem neuesten Block zu beginnen, beginnt die Suche beim ältesten:

Header *header = first;

Bei jeder Iteration gehen wir zum nächsten Block in der Sequenz über, anstatt zum vorherigen Block rückwärts zu gehen:

while (header != NULL) {
  if (header->available && (header->size >= size)) {
    header->available = false;
    return header + 1;
  }
  header = header->next;
}

Die Logik bleibt dieselbe: Wenn wir einen verfügbaren Block ausreichender Größe finden, wird er zurückgegeben. Andernfalls, wenn nach dem Durchlaufen der Liste kein wiederverwendbarer Block gefunden wird, wird ein neuer Block zugewiesen:

last = header_new(last, size, false);

Jetzt müssen wir den Block anpassen, der der letzte war (nach der Zuweisung der vorletzte). Es zeigte auf NULL, aber jetzt sollte es auf den neuen Block zeigen. Dazu setzen wir das nächste Feld des vorherigen Blocks auf den neuen letzten Block:

  last->previous->next = last;
  return last + 1;
}

Adjustments in abfree()

The function abfree() basically maintains the same structure, but now we must handle some edge cases. When we free blocks at the top of the heap, a new block becomes the last one, as we already do in this snippet:

last = header->previous;
brk(header)

Here, the pointer header references the last non-null block available on the stack. We have two possible scenarios:

1. the current block has a previous block, which will become the new last block. In this case, we should set the pointer nextof this block to NULL.
2. the current block does not have a previous block (i.e., it is the first and oldest block). When it is freed, the stack is empty. In this case, instead of trying to update a field of a non-existent block, we simply set it first to NULL, indicating that there are no more allocated blocks.

Here is how we implement it:

last = header->previous;
if (last != NULL) {
  last->next = NULL;
} else {
  first = NULL;
}
brk(header);

Conclusion

Our functions abmalloc() and abfree() now look like this:

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;

Header *first = NULL;
Header *last = NULL;

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header) + size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

void *abmalloc(size_t size) {
  if (size == 0) {
    return NULL;
  }
  if (first == NULL) {
    first = last = header_new(NULL, size, false);
    return first + 1;
  }
  Header *header = first;
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false;
      return header + 1;
    }
    header = header->next;
  }
  last = header_new(last, size, false);
  last->previous->next = last;
  return last + 1;
}

void abfree(void *ptr) {
  if (ptr == NULL) {
   return;
  }
  Header *header = (Header*) ptr - 1;
  if (header == last) {
    while ((header->previous != NULL) && header->previous->available) {
      header = header->previous;
    }
    last = header->previous;
    if (last != NULL) {
      last->next = NULL;
    } else {
      first = NULL;
    }
    brk(header);
  } else {
   header->available = true;
  }
 }

This change allows us to save considerably more memory. There are, however, still problems to solve. For example, consider the following scenario: we request the allocation of a memory block of 8 bytes, and abmalloc() reuse a block of, say, 1024 bytes. There is clearly a waste.

We will see how to solve this in the next post.

The above is the detailed content of Implementing malloc() and free() — old memory reused first. For more information, please follow other related articles on the PHP Chinese website!