wake-up-neo.com

Wie funktionieren malloc () und free ()?

Ich möchte wissen, wie malloc und free funktionieren.

int main() {
    unsigned char *p = (unsigned char*)malloc(4*sizeof(unsigned char));
    memset(p,0,4);
    strcpy((char*)p,"abcdabcd"); // **deliberately storing 8bytes**
    cout << p;
    free(p); // Obvious Crash, but I need how it works and why crash.
    cout << p;
    return 0;
}

Ich wäre wirklich dankbar, wenn die Antwort auf Speicherebene ausführlich ist, wenn es möglich ist.

261
mahesh

OK, einige Antworten zu malloc wurden bereits gepostet.

Der interessantere Teil ist wie frei funktioniert (und in dieser Richtung kann Malloc auch besser verstanden werden).

In vielen malloc/free-Implementierungen gibt free den Speicher normalerweise nicht an das Betriebssystem zurück (oder zumindest nur in seltenen Fällen). Der Grund ist, dass Sie Lücken in Ihrem Heap bekommen und es daher passieren kann, dass Sie Ihre 2 oder 4 GB virtuellen Speicher nur mit Lücken abschließen. Dies sollte vermieden werden, da Sie große Probleme haben werden, sobald der virtuelle Speicher voll ist. Der andere Grund ist, dass das Betriebssystem nur Speicherbereiche verarbeiten kann, die eine bestimmte Größe und Ausrichtung haben. Um genau zu sein: Normalerweise kann das Betriebssystem nur Blöcke verarbeiten, die der virtuelle Speichermanager verarbeiten kann (meistens ein Vielfaches von 512 Bytes, z. B. 4 KB).

Die Rückgabe von 40 Bytes an das Betriebssystem funktioniert also nicht. Also, was macht Free?

Free fügt den Speicherblock in eine eigene Liste der freien Blöcke ein. Normalerweise wird auch versucht, benachbarte Blöcke im Adressraum zu verschmelzen. Die Liste der freien Blöcke ist nur eine zirkuläre Liste von Speicherblöcken, die am Anfang einige Verwaltungsdaten enthalten. Dies ist auch der Grund, warum die Verwaltung sehr kleiner Speicherelemente mit dem Standard malloc/free nicht effizient ist. Jeder Speicherblock benötigt zusätzliche Daten, und bei kleineren Größen tritt eine stärkere Fragmentierung auf.

Die freie Liste ist auch der erste Ort, an dem sich malloc umschaut, wenn ein neuer Speicherblock benötigt wird. Es wird gescannt, bevor neuer Speicher vom Betriebssystem angefordert wird. Wenn ein Block gefunden wird, der größer als der benötigte Speicher ist, wird er in zwei Teile geteilt. Einer wird an den Anrufer zurückgegeben, der andere wird wieder in die freie Liste aufgenommen.

Es gibt viele verschiedene Optimierungen für dieses Standardverhalten (z. B. für kleine Speicherbereiche). Aber da malloc und free so universell sein müssen, ist das Standardverhalten immer der Fallback, wenn Alternativen nicht verwendbar sind. Es gibt auch Optimierungen im Umgang mit der freien Liste - zum Beispiel das Speichern der Blöcke in Listen, die nach Größen sortiert sind. Alle Optimierungen haben aber auch ihre eigenen Grenzen.

Warum stürzt Ihr Code ab:

Der Grund dafür ist, dass Sie durch das Schreiben von 9 Zeichen (das nachfolgende Null-Byte nicht vergessen) in einen Bereich mit einer Größe von 4 Zeichen wahrscheinlich die Verwaltungsdaten überschreiben, die für einen anderen Speicherblock gespeichert sind, der sich "hinter" Ihrem Datenblock befindet ( da diese Daten am häufigsten "vor" den Speicherblöcken gespeichert werden). Wenn free dann versucht, Ihren Chunk in die freie Liste zu setzen, kann er diese Verwaltungsdaten berühren und somit über einen überschriebenen Zeiger stolpern. Dies wird das System zum Absturz bringen.

Dies ist ein ziemlich anmutiges Verhalten. Ich habe auch Situationen gesehen, in denen ein außer Kontrolle geratener Zeiger irgendwo Daten in der speicherfreien Liste überschrieben hat und das System nicht sofort abstürzte, sondern einige Unterprogramme später. Selbst in einem System mittlerer Komplexität können solche Probleme sehr, sehr schwer zu beheben sein! In dem einen Fall, in dem ich involviert war, haben wir (eine größere Gruppe von Entwicklern) mehrere Tage gebraucht, um den Grund des Absturzes zu finden - da er sich an einem völlig anderen Ort befand als der, der durch den Speicherauszug angegeben wurde. Es ist wie eine Zeitbombe. Sie wissen, Ihr nächstes "freies" oder "Malloc" wird abstürzen, aber Sie wissen nicht warum!

Dies sind einige der schlimmsten C/C++ - Probleme und ein Grund, warum Zeiger so problematisch sein können.

368
Juergen

Wie Aluser in diesem Forenthread sagt:

Ihr Prozess verfügt über einen Speicherbereich von der Adresse x bis zur Adresse y, der als Heap bezeichnet wird. Alle Ihre malloc'd Daten leben in diesem Bereich. malloc () enthält eine Datenstruktur, zum Beispiel eine Liste aller freien Speicherbereiche auf dem Heap. Wenn Sie malloc aufrufen, durchsucht es die Liste nach einem Block, der groß genug für Sie ist, gibt einen Zeiger darauf zurück und zeichnet die Tatsache auf, dass er nicht mehr kostenlos ist und wie groß er ist. Wenn Sie free () mit demselben Zeiger aufrufen, ermittelt free (), wie groß dieser Block ist, und fügt ihn wieder der Liste der freien Blöcke () hinzu. Wenn Sie malloc () aufrufen und im Heap kein ausreichend großes Stück gefunden wird, wird der Heap mithilfe von brk () syscall vergrößert, dh es wird die Adresse y erhöht und alle Adressen zwischen dem alten y und dem neuen y werden zu gültige Erinnerung sein. brk () muss ein Syscall sein; Es gibt keine Möglichkeit, dasselbe vollständig vom Benutzerraum aus zu tun.

malloc () ist system-/compilerabhängig, daher ist es schwierig, eine bestimmte Antwort zu geben. Grundsätzlich wird jedoch nachverfolgt, welcher Speicher zugewiesen ist, und je nachdem, wie dies geschieht, können Ihre Anrufe zum Freigeben fehlschlagen oder erfolgreich sein.

malloc() and free() don't work the same way on every O/S.

54
joe

Eine Implementierung von malloc/free führt Folgendes aus:

  1. Holen Sie sich einen Speicherblock vom Betriebssystem über sbrk () (Unix-Aufruf).
  2. Erstellen Sie eine Kopfzeile und eine Fußzeile um diesen Speicherblock mit einigen Informationen wie Größe, Berechtigungen und der Position des nächsten und vorherigen Blocks.
  3. Wenn ein Aufruf von malloc eingeht, wird auf eine Liste verwiesen, die auf Blöcke der entsprechenden Größe verweist.
  4. Dieser Block wird dann zurückgegeben und Kopf- und Fußzeilen werden entsprechend aktualisiert.
34
samoz

Der Speicherschutz ist seitengranular und erfordert eine Interaktion mit dem Kernel

Ihr Beispielcode fragt im Wesentlichen, warum das Beispielprogramm keine Überfüllung durchführt, und die Antwort lautet, dass der Speicherschutz eine Kernelfunktion ist und nur für ganze Seiten gilt, wohingegen der Speicherzuweiser eine Bibliotheksfunktion ist und .. ohne Durchsetzung .. willkürlich verwaltet Blöcke, die oft viel kleiner als Seiten sind.

Der Speicher kann nur in Einheiten von Seiten aus Ihrem Programm entfernt werden, und selbst das ist unwahrscheinlich.

calloc (3) und malloc (3) interagieren bei Bedarf mit dem Kernel, um Speicher zu erhalten. Die meisten Implementierungen von free (3) geben jedoch keinen Speicher an den Kernel zurück1Sie fügen es einfach einer freien Liste hinzu, die calloc () und malloc () später konsultieren, um die freigegebenen Blöcke wiederzuverwenden.

Selbst wenn ein free () Speicher an das System zurückgeben wollte, würde es mindestens eine zusammenhängende Speicherseite benötigen, damit der Kernel die Region tatsächlich schützt. Das Freigeben eines kleinen Blocks würde also nur dann zu einer Änderung des Schutzes führen, wenn dies der Fall ist der letzte kleine Block auf einer Seite.

Also ist dein Block da und sitzt auf der freien Liste. Sie können fast immer darauf und auf den Speicher in der Nähe zugreifen, als wäre er noch reserviert. C kompiliert direkt zu Maschinencode und ohne spezielle Debugging-Vorkehrungen gibt es keine Sicherheitsüberprüfungen für Lasten und Geschäfte. Wenn Sie nun versuchen, auf einen freien Block zuzugreifen, ist das Verhalten vom Standard nicht definiert, um keine unangemessenen Anforderungen an Bibliotheksimplementatoren zu stellen. Wenn Sie versuchen, auf den freigegebenen Speicher oder Speicherbereich außerhalb eines zugewiesenen Blocks zuzugreifen, können verschiedene Probleme auftreten:

  • Manchmal verwalten Zuweiser separate Speicherblöcke, manchmal verwenden sie einen Header, den sie kurz vor oder nach Ihrem Block zuweisen (eine "Fußzeile", denke ich), aber sie möchten möglicherweise nur Speicher innerhalb des Blocks verwenden, um die freie Liste zu behalten miteinander verbunden. Wenn dies der Fall ist, ist das Lesen des Blocks in Ordnung, der Inhalt kann sich jedoch ändern, und das Schreiben in den Block kann wahrscheinlich zu einem Fehlverhalten oder Absturz des Zuweisers führen.
  • Natürlich kann Ihr Block in Zukunft zugewiesen werden, und dann wird er wahrscheinlich von Ihrem Code oder einer Bibliotheksroutine oder von calloc () mit Nullen überschrieben.
  • Wenn der Block neu zugewiesen wird, kann sich auch seine Größe ändern. In diesem Fall werden an verschiedenen Stellen weitere Links oder Initialisierungen geschrieben.
  • Offensichtlich können Sie so weit außerhalb des Bereichs verweisen, dass Sie eine Grenze eines der vom Kernel bekannten Segmente Ihres Programms überschreiten, und in diesem einen Fall werden Sie einen Trap ausführen.

Theorie der Arbeitsweise

Wenn Sie also von Ihrem Beispiel auf die allgemeine Theorie zurückgehen, ruft malloc (3) den Speicher aus dem Kernel ab, wenn er benötigt wird, und zwar normalerweise in Einheiten von Seiten. Diese Seiten werden je nach Programm aufgeteilt oder konsolidiert. Malloc und free arbeiten zusammen, um ein Verzeichnis zu führen. Sie vereinigen nach Möglichkeit benachbarte freie Blöcke, um große Blöcke bereitstellen zu können. Das Verzeichnis kann die Verwendung des Speichers in freigegebenen Blöcken zum Bilden einer verknüpften Liste beinhalten oder nicht. (Die Alternative ist etwas speicherfreier und paging-freundlicher und beinhaltet die Zuweisung von Speicher speziell für das Verzeichnis.) Malloc und Free können den Zugriff auf einzelne Blöcke kaum erzwingen, selbst wenn spezieller und optionaler Debugging-Code kompiliert wird das Programm.


1. Die Tatsache, dass nur sehr wenige Implementierungen von free () versuchen, Speicher an das System zurückzugeben, ist nicht unbedingt darauf zurückzuführen, dass die Implementierer nachlassen. Die Interaktion mit dem Kernel ist viel langsamer als die Ausführung von Bibliothekscode, und der Nutzen wäre gering. Die meisten Programme sind im eingeschwungenen Zustand oder nehmen an Speicherbedarf zu, sodass die Zeit, die für die Analyse des Heapspeichers auf der Suche nach wiederverwendbarem Speicher aufgewendet wird, vollständig verschwendet wird. Zu den weiteren Gründen gehört die Tatsache, dass durch die interne Fragmentierung die Existenz von seitenausgerichteten Blöcken unwahrscheinlich wird und das Zurückgeben eines Blocks wahrscheinlich dazu führt, dass Blöcke zu beiden Seiten fragmentiert werden. Schließlich umgehen die wenigen Programme, die große Mengen an Speicher zurückgeben, wahrscheinlich malloc () und weisen einfach Seiten zu und geben sie trotzdem frei.

26
DigitalRoss

Theoretisch bezieht malloc für diese Anwendung Speicher vom Betriebssystem. Da Sie jedoch möglicherweise nur 4 Bytes benötigen und das Betriebssystem in Seiten (häufig 4 KB) arbeiten muss, kann malloc etwas mehr. Es nimmt eine Seite ein und fügt dort seine eigenen Informationen ein, damit es verfolgen kann, was Sie zugewiesen und von dieser Seite befreit haben.

Wenn Sie beispielsweise 4 Bytes zuweisen, gibt malloc Ihnen einen Zeiger auf 4 Bytes. Was Sie vielleicht nicht bemerken, ist, dass der Speicher 8-12 Bytes vorher Ihre 4 Bytes von malloc verwendet werden, um eine Kette des gesamten von Ihnen zugewiesenen Speichers zu erstellen. Wenn Sie kostenlos anrufen, nimmt es Ihren Zeiger auf, sichert seine Daten und verarbeitet diese.

Wenn Sie Speicher freigeben, entfernt malloc diesen Speicherblock aus der Kette ... und gibt diesen Speicher möglicherweise an das Betriebssystem zurück. Wenn dies der Fall ist, schlägt der Zugriff auf diesen Speicher wahrscheinlich fehl, da das Betriebssystem Ihnen die Berechtigungen für den Zugriff auf diesen Speicherort entzieht. Wenn malloc den Speicher behält (weil andere Dinge auf dieser Seite zugewiesen sind oder für eine Optimierung), funktioniert der Zugriff. Es ist immer noch falsch, aber es könnte funktionieren.

HAFTUNGSAUSSCHLUSS: Was ich beschrieben habe, ist eine übliche Implementierung von malloc, aber keineswegs die einzig mögliche.

24
Chris Arguin

Ihre strcpy-Zeile versucht aufgrund des NUL-Abschlusszeichens, 9 Byte und nicht 8 Byte zu speichern. Es ruft undefiniertes Verhalten auf.

Der Anruf zum Freiwerden kann abstürzen oder nicht. Der Speicher "nach" den 4 Bytes Ihrer Zuordnung wird möglicherweise von Ihrer C- oder C++ - Implementierung für etwas anderes verwendet. Wenn es für etwas anderes verwendet wird, dann führt das Kritzeln dazu, dass "etwas anderes" schief geht, aber wenn es für nichts anderes verwendet wird, kann es passieren, dass Sie damit durchkommen. "Damit durchkommen" klingt vielleicht gut, ist aber tatsächlich schlecht, da Ihr Code anscheinend in Ordnung ist, aber bei einem zukünftigen Durchgang könnten Sie möglicherweise nicht damit durchkommen.

Bei einem Speicher-Allokator im Debugging-Stil stellen Sie möglicherweise fest, dass dort ein spezieller Guard-Wert geschrieben wurde, und dass dieser Wert kostenlos überprüft wird.

Andernfalls stellen Sie möglicherweise fest, dass die nächsten 5 Bytes einen Teil eines Verbindungsknotens enthalten, der zu einem anderen Speicherblock gehört, der noch nicht zugewiesen wurde. Wenn Sie Ihren Block freigeben, müssen Sie ihn möglicherweise zu einer Liste der verfügbaren Blöcke hinzufügen. Da Sie in den Listenknoten gekritzelt haben, kann durch diese Operation ein Zeiger mit einem ungültigen Wert dereferenziert werden, was zu einem Absturz führt.

Es hängt alles vom Speicherzuweiser ab - verschiedene Implementierungen verwenden unterschiedliche Mechanismen.

12
Steve Jessop

Wie malloc () und free () funktionieren, hängt von der verwendeten Laufzeitbibliothek ab. Im Allgemeinen weist malloc () einen Heap (einen Speicherblock) vom Betriebssystem zu. Jede Anforderung an malloc () weist dann einen kleinen Teil dieses Speichers zu, indem ein Zeiger auf den Aufrufer zurückgegeben wird. Die Speicherzuweisungsroutinen müssen einige zusätzliche Informationen über den zugewiesenen Speicherblock speichern, um den belegten und freien Speicher auf dem Heap verfolgen zu können. Diese Informationen werden häufig in wenigen Bytes unmittelbar vor dem von malloc () zurückgegebenen Zeiger gespeichert und können eine verknüpfte Liste von Speicherblöcken sein.

Wenn Sie an dem von malloc () zugewiesenen Speicherblock vorbeischreiben, werden Sie höchstwahrscheinlich einige der Buchhaltungsinformationen des nächsten Blocks zerstören, bei dem es sich möglicherweise um den verbleibenden nicht verwendeten Speicherblock handelt.

Ein Ort, an dem Sie möglicherweise auch abstürzen, ist das Kopieren zu vieler Zeichen in den Puffer. Befinden sich die zusätzlichen Zeichen außerhalb des Heapspeichers, kann es zu einer Zugriffsverletzung kommen, wenn Sie versuchen, in den nicht vorhandenen Speicher zu schreiben.

12

Dies hat nichts spezielles mit Malloc und Free zu tun. Ihr Programm zeigt ein undefiniertes Verhalten, nachdem Sie die Zeichenfolge kopiert haben. Es kann zu diesem Zeitpunkt oder zu einem späteren Zeitpunkt abstürzen. Dies wäre auch dann der Fall, wenn Sie malloc und free niemals verwendet und das char-Array auf dem Stack oder statisch zugewiesen hätten.

6
anon

malloc und free sind implementierungsabhängig. Eine typische Implementierung beinhaltet das Partitionieren des verfügbaren Speichers in eine "freie Liste" - eine verknüpfte Liste der verfügbaren Speicherblöcke. Viele Implementierungen unterteilen es künstlich in kleine und große Objekte. Freie Blöcke beginnen mit Informationen darüber, wie groß der Speicherblock ist und wo sich der nächste befindet usw.

Wenn Sie malloc, wird ein Block aus der freien Liste gezogen. Wenn Sie freigeben, wird der Block wieder in die freie Liste aufgenommen. Wenn Sie das Ende Ihres Zeigers überschreiben, schreiben Sie wahrscheinlich in die Kopfzeile eines Blocks in der freien Liste. Wenn Sie Ihren Speicher freigeben, versucht free (), auf den nächsten Block zu schauen, und trifft wahrscheinlich auf einen Zeiger, der einen Busfehler verursacht.

5
plinth

Nun, es hängt von der Speicherzuweiser-Implementierung und dem Betriebssystem ab.

Unter Windows kann ein Prozess beispielsweise eine Seite oder mehr RAM anfordern. Das Betriebssystem weist diese Seiten dann dem Prozess zu. Dies ist jedoch nicht der Ihrer Anwendung zugewiesene Speicher. Die CRT-Speicherzuordnung markiert den Speicher als zusammenhängenden "verfügbaren" Block. Der CRT-Speicherzuordner durchläuft dann die Liste der freien Blöcke und sucht den kleinstmöglichen Block, den er verwenden kann. Es nimmt dann so viel von diesem Block, wie es benötigt, und fügt ihn einer "zugewiesenen" Liste hinzu. An den Kopf der tatsächlichen Speicherzuordnung wird ein Kopf angehängt. Dieser Header enthält verschiedene Informationen (er kann beispielsweise den nächsten und den vorherigen zugewiesenen Block enthalten, um eine verknüpfte Liste zu bilden. Höchstwahrscheinlich enthält er die Größe der Zuordnung).

Free entfernt dann den Header und fügt ihn wieder zur Liste der freien Speicherplätze hinzu. Wenn es mit den umgebenden freien Blöcken einen größeren Block bildet, werden diese zu einem größeren Block addiert. Wenn jetzt eine ganze Seite frei ist, gibt der Allokator die Seite höchstwahrscheinlich an das Betriebssystem zurück.

Es ist kein einfaches Problem. Der OS-Zuweisungsbereich liegt vollständig außerhalb Ihrer Kontrolle. Ich empfehle Ihnen, etwas wie Doug Lea's Malloc (DLMalloc) durchzulesen, um zu verstehen, wie ein relativ schneller Allokator funktionieren wird.

Bearbeiten: Ihr Absturz wird durch die Tatsache verursacht, dass Sie durch Schreiben, das größer als die Zuweisung ist, den nächsten Speicherheader überschrieben haben. Auf diese Weise wird es sehr verwirrt, was genau es befreit und wie es in den folgenden Block verschmilzt. Dies kann nicht immer sofort zu einem Absturz führen. Dies kann später zu einem Absturz führen. Vermeiden Sie generell das Überschreiben des Speichers!

4
Goz

Ihr Programm stürzt ab, weil es Speicher verwendet, der Ihnen nicht gehört. Es kann von jemand anderem verwendet werden oder nicht - wenn Sie Glück haben, stürzen Sie ab, wenn nicht, bleibt das Problem möglicherweise für eine lange Zeit verborgen und kommt zurück und beißt Sie später.

Bei der Implementierung von malloc/free sind ganze Bücher dem Thema gewidmet. Grundsätzlich würde der Allokator größere Speicherbereiche vom Betriebssystem abrufen und diese für Sie verwalten. Einige der Probleme, die ein Allokator angehen muss, sind:

  • Wie bekomme ich neues Gedächtnis?
  • So speichern Sie es - (Liste oder andere Struktur, mehrere Listen für Speicherblöcke unterschiedlicher Größe usw.)
  • Was ist zu tun, wenn der Benutzer mehr Speicher als derzeit verfügbar anfordert? (Fordern Sie mehr Speicher vom Betriebssystem an, fügen Sie einige der vorhandenen Blöcke hinzu, wie man sie genau zusammenfügt, ...)
  • Was tun, wenn der Benutzer Speicher freigibt?
  • Debug-Zuweiser geben Ihnen möglicherweise einen größeren Teil, den Sie angefordert haben, und füllen ihn mit einem Byte-Muster. Wenn Sie den Speicher freigeben, kann der Zuweiser überprüfen, ob außerhalb des Blocks geschrieben wurde (was in Ihrem Fall wahrscheinlich der Fall ist).
3
devdimi

Es ist schwer zu sagen, da das tatsächliche Verhalten zwischen verschiedenen Compilern/Laufzeiten unterschiedlich ist. Selbst Debug-/Release-Builds verhalten sich unterschiedlich. In Debugbuilds von VS2005 werden Markierungen zwischen Zuordnungen eingefügt, um eine Speicherbeschädigung zu erkennen. Anstelle eines Absturzes wird also free () aktiviert.

2
Sebastiaan M

Es ist auch wichtig zu wissen, dass das einfache Bewegen des Programmunterbrechungszeigers mit brk und sbrk nicht wirklich zuordnet Im Speicher wird lediglich der Adressraum eingerichtet. Unter Linux beispielsweise wird der Speicher beim Zugriff auf diesen Adressbereich durch tatsächliche physische Seiten "gesichert", was zu einem Seitenfehler führt und schließlich dazu, dass der Kernel den Seitenzuweiser aufruft, um eine Hintergrundseite abzurufen.

1
mgalgs