Wie wird malloc() intern implementiert? [duplicate]

Kann jemand erklären, wie malloc() funktioniert intern?

habe ich manchmal gemacht strace program und ich sehe viel sbrk Systemaufrufe, tun man sbrk spricht davon, dass es in verwendet wird malloc() aber nicht viel mehr.

Das sbrkSystemaufruf verschiebt die “Grenze” des Datensegments. Dies bedeutet, dass es eine Grenze eines Bereichs verschiebt, in dem ein Programm Daten lesen/schreiben kann (wodurch es wächst oder schrumpft, obwohl AFAIK Nr malloc gibt mit dieser Methode wirklich Speichersegmente an den Kernel zurück). Abgesehen davon gibt es auch mmap das verwendet wird, um Dateien in den Speicher abzubilden, aber auch zum Zuweisen von Speicher verwendet wird (wenn Sie gemeinsam genutzten Speicher zuweisen müssen, mmap so machst du das).

Sie haben also zwei Methoden, um mehr Speicher aus dem Kernel zu bekommen: sbrk und mmap. Es gibt verschiedene Strategien, wie Sie den Speicher, den Sie vom Kernel haben, organisieren können.

Ein naiver Weg besteht darin, es in Zonen zu unterteilen, die oft als “Eimer” bezeichnet werden und bestimmten Strukturgrößen zugeordnet sind. Zum Beispiel ein malloc Die Implementierung könnte Buckets für 16-, 64-, 256- und 1024-Byte-Strukturen erstellen. Wenn du fragst malloc Um Ihnen eine Erinnerung an eine bestimmte Größe zu geben, rundet es diese Zahl auf die nächste Bucket-Größe auf und gibt Ihnen dann ein Element aus diesem Bucket. Wenn Sie eine größere Fläche benötigen malloc könnte benutzen mmap direkt mit dem Kernel zuzuweisen. Wenn der Eimer einer bestimmten Größe leer ist malloc könnte benutzen sbrk um mehr Platz für einen neuen Eimer zu bekommen.

Es gibt verschiedene malloc Designs und es gibt wahrscheinlich keinen wahren Weg zur Implementierung malloc da Sie einen Kompromiss zwischen Geschwindigkeit, Overhead und Vermeidung von Fragmentierung/Platzeffektivität eingehen müssen. Wenn beispielsweise einem Bucket die Elemente ausgehen, könnte eine Implementierung ein Element aus einem größeren Bucket erhalten, es aufteilen und es dem Bucket hinzufügen, dem die Elemente ausgegangen sind. Dies wäre recht platzsparend, wäre aber nicht bei jedem Design möglich. Wenn Sie nur einen anderen Eimer per bekommen sbrk/mmap das ist vielleicht schneller und noch einfacher, aber nicht so platzsparend. Außerdem muss bei der Gestaltung natürlich berücksichtigt werden, dass „freier“ Platz zur Verfügung gestellt werden muss malloc wieder irgendwie. Sie geben Speicher nicht einfach weiter, ohne ihn wiederzuverwenden.

Falls Sie interessiert sind, der OpenSER/Kamailio-SIP-Proxy hat zwei malloc Implementierungen (sie brauchen ihre eigenen, weil sie Shared Memory und das System stark nutzen malloc unterstützt keinen Shared Memory). Sehen: https://github.com/OpenSIPS/opensips/tree/master/mem

Dann könntest du dir das auch mal anschauen GNU-libc malloc Implementierungaber das ist sehr kompliziert, IIRC.

Vereinfacht malloc und free so arbeiten:

malloc bietet Zugriff auf den Heap eines Prozesses. Der Heap ist ein Konstrukt in der C-Core-Bibliothek (allgemein libc), die es Objekten ermöglicht, exklusiven Zugriff auf einen bestimmten Speicherplatz auf dem Heap des Prozesses zu erhalten.

Jede Zuordnung auf dem Heap wird als Heap-Zelle bezeichnet. Diese besteht typischerweise aus einem Header, der Informationen über die Größe der Zelle sowie einen Zeiger auf die nächste Heap-Zelle enthält. Dies macht einen Heap effektiv zu einer verketteten Liste.

Wenn man einen Prozess startet, enthält der Heap eine einzelne Zelle, die den gesamten beim Start zugewiesenen Heap-Speicherplatz enthält. Diese Zelle existiert auf der freien Liste des Heaps.

Wenn einer anruft mallocSpeicher wird der großen Heap-Zelle entnommen, die von zurückgegeben wird malloc. Der Rest wird zu einer neuen Heap-Zelle geformt, die aus dem gesamten Rest des Speichers besteht.

Wenn man Speicher freigibt, wird die Heap-Zelle an das Ende der freien Liste des Heaps hinzugefügt. Anschließend mallocGehen Sie die freie Liste durch und suchen Sie nach einer Zelle geeigneter Größe.

Wie zu erwarten ist, kann der Heap fragmentiert werden und der Heap-Manager kann von Zeit zu Zeit versuchen, benachbarte Heap-Zellen zusammenzuführen.

Wenn für eine gewünschte Zuordnung kein Speicherplatz mehr auf der freien Liste vorhanden ist, malloc Anrufe brk oder sbrk Das sind die Systemaufrufe, die mehr Speicherseiten vom Betriebssystem anfordern.

Jetzt gibt es ein paar Modifikationen, um Heap-Operationen zu optimieren.

• Bei großen Speicherzuweisungen (normalerweise > 512 Byte) kann der Heap-Manager direkt zum Betriebssystem gehen und eine vollständige Speicherseite zuweisen.
• Der Heap kann eine Mindestgröße der Zuordnung spezifizieren, um große Mengen an Fragmentierung zu verhindern.
• Der Heap kann sich auch selbst in Behälter aufteilen, einen für kleine Zuordnungen und einen für größere Zuordnungen, um größere Zuordnungen schneller zu machen.
• Es gibt auch clevere Mechanismen zur Optimierung der Multithread-Heap-Zuweisung.

Es ist auch wichtig zu wissen, dass das einfache Verschieben des Programm-Unterbrechungszeigers mit brk und sbrk eigentlich nicht zuordnen der Speicher, es richtet nur den Adressraum ein. Unter Linux beispielsweise wird der Speicher beim Zugriff auf diesen Adressbereich durch tatsächliche physische Seiten “unterstützt”, was zu einem Seitenfehler führt und schließlich dazu führt, dass der Kernel den Seitenzuordner aufruft, um eine Sicherungsseite zu erhalten.