Erklärung zur ausgerichteten Malloc-Implementierung

Dies ist keine Hausaufgabe, sondern dient ausschließlich meiner persönlichen Weiterbildung.

Ich konnte nicht herausfinden, wie man einen ausgerichteten Malloc implementiert, also habe ich online gesucht und gefunden Diese Internetseite. Zur besseren Lesbarkeit poste ich folgenden Code:

#include <stdlib.h>
#include <stdio.h>

void* aligned_malloc(size_t required_bytes, size_t alignment)
{
    void* p1; // original block
    void** p2; // aligned block
    int offset = alignment - 1 + sizeof(void*);
    if ((p1 = (void*)malloc(required_bytes + offset)) == NULL)
    {
       return NULL;
    }
    p2 = (void**)(((size_t)(p1) + offset) & ~(alignment - 1));
    p2[-1] = p1;
    return p2;
}

void aligned_free(void *p)
{
    free(((void**)p)[-1]);
}

void main (int argc, char *argv[])
{
    char **endptr;
    int *p = aligned_malloc (100, strtol(argv[1], endptr, 10));

    printf ("%s: %p\n", argv[1], p);
    aligned_free (p);
}

Die Implementierung funktioniert, aber ich kann ehrlich gesagt nicht herausfinden, wie es funktioniert.

Folgendes kann ich nicht verstehen:

1. Warum brauchen wir einen Offset?
2. Was bedeutet anding with ~(alignment - 1) erreichen
3. p2 ist ein Doppelzeiger. Wie kommt es, dass wir es von einer Funktion zurückgeben können, die nur einen einzigen Zeiger zurückgeben soll?
4. Was ist der allgemeine Ansatz, um dieses Problem zu lösen?

Jede Hilfe ist sehr willkommen.

BEARBEITEN

Dies ist kein Duplikat von How to allocate aligned memory only using the standard library? weil ich auch wissen muss, wie man ausgerichteten Speicher freigibt.

1. Sie benötigen einen Offset, wenn Sie Ausrichtungen unterstützen möchten, die über die Ihres Systems hinausgehen malloc() tut. Zum Beispiel, wenn Ihr System malloc() an 8-Byte-Grenzen ausrichten, und Sie an 16 Bytes ausrichten möchten, fragen Sie nach 15 Bytes extra, damit Sie sicher wissen, dass Sie das Ergebnis verschieben können, um es wie gewünscht auszurichten. Du fügst auch hinzu sizeof(void*) auf die Größe, auf die Sie übergehen malloc() Raum für die Buchhaltung zu lassen.

2. ~(alignment - 1) garantiert die Ausrichtung. Wenn beispielsweise die Ausrichtung 16 ist, dann subtrahieren Sie 1, um 15 zu erhalten, auch bekannt als 0xF, und die Negation ergibt 0xFF..FF0, was die Maske ist, die Sie benötigen, um die Ausrichtung für jeden zurückgegebenen Zeiger zu erfüllen malloc(). Beachten Sie, dass dieser Trick davon ausgeht, dass die Ausrichtung eine Potenz von 2 ist (was normalerweise praktisch der Fall wäre, aber es sollte wirklich eine Überprüfung geben).

3. Es ist ein void**. Die Funktion kehrt zurück void*. Das ist in Ordnung, weil ein Zeiger auf void »ein Zeiger auf einen beliebigen Typ« ist, und in diesem Fall ist das der Typ void*. Mit anderen Worten, umwandeln void* zu und von anderen Zeigertypen ist erlaubt, und ein Doppelzeiger ist immer noch ein Zeiger.

4. Das allgemeine Schema besteht hier darin, den ursprünglichen Zeiger vor demjenigen zu speichern, der an den Aufrufer zurückgegeben wird. Einige Implementierungen von Standard malloc() machen Sie dasselbe: Verstauen Sie Buchhaltungsinformationen vor dem zurückgegebenen Block. So lässt sich leicht erkennen, wann wie viel Speicherplatz zurückgewonnen werden muss free() wird genannt.

Alles in allem ist so etwas normalerweise nicht sinnvoll, da der Standard malloc() gibt die größte Ausrichtung auf dem System zurück. Wenn Sie darüber hinaus eine Ausrichtung benötigen, gibt es möglicherweise andere Lösungen, einschließlich compilerspezifischer Attribute.

Umsetzung funktioniert

Vielleicht, aber ich wäre mir nicht sicher. Meiner Meinung nach wäre es besser, von Grund auf zu arbeiten. Sofort,

p1 = (void*)malloc

ist eine rote Fahne. malloc kehrt zurück void. In C kann jeder Zeiger von zugewiesen werden void *. Gießen aus malloc wird normalerweise als schlechte Form angesehen, weil jede Wirkung, die es hat, nur schlecht sein kann.

Warum wir einen Offset brauchen

Der Offset bietet Platz zum Verstauen des von zurückgegebenen Zeigers mallocspäter verwendet von free.

p1 abgerufen wird malloc. Später muss dafür gesorgt werden free freigegeben werden. aligned_malloc Reserven sizeof(void*) Byte bei p1Verstecke p1 dort und kehrt zurück p2 (die erste “ausgerichtete” Adresse im Block that p1 verweist auf). Später, wenn der Anrufer vorbeigeht p2 zu aligned_freees konvertiert p2 in der Tat zu void *p2[]und holt das Original p1 Verwenden von -1 als Index.

Was bewirkt anding mit ~(alignment – 1)?

Es ist was bringt p2 an der Grenze. Angenommen, die Ausrichtung ist 16; alignment -1 ist 15, 0xF. ~OxF sind alle Bits außer den letzten 4 eingeschaltet. Für jeden Zeiger P, P & ~0xF wird ein Vielfaches von 16 sein.

p2 ist ein Doppelzeiger.

Zeiger schmetter. malloc kehrt zurück void*. Es ist ein Speicherblock; Sie sprechen es an, wie Sie wollen. Du würdest nicht blinzeln

char **args = calloc(7, sizeof(char*));

um ein Array von 7 zuzuweisen char * Hinweise, würden Sie? Der Code wählt zumindest einen “ausgerichteten” Ort aus sizeof(void*) Bytes ab p1 und für die Zwecke von freebehandelt es als void **.

Wie ist die allgemeine Vorgehensweise

Es gibt keine Antwort. Am besten ist es wahrscheinlich, eine Standard- (oder beliebte) Bibliothek zu verwenden. Wenn man darauf baut malloc, genug zuzuweisen, um den “echten” Zeiger zu behalten und einen ausgerichteten zurückzugeben, ist ziemlich Standard, obwohl ich es anders codieren würde. Der Syscall mmap gibt einen seitenausgerichteten Zeiger zurück, der die meisten Kriterien für “ausgerichtet” erfüllt. Je nach Bedarf kann das besser oder schlechter sein als Huckepack malloc.

Angenommen, wir brauchen SZ Bytes ausgerichteten Speichers, lassen Sie:

A is the alignment.
W is the CPU word size.
P is the memory returned by malloc.
SZ is the requested number of bytes to be allocated.

wir werden zurück kommen (P + Y) in welchem (P + Y) mod A = 0

Also sollten wir den ursprünglichen Zeiger speichern P um den Speicher später freigeben zu können. In diesem Fall sollten wir zuweisen (SZ+W) Bytes, aber um den Speicher ausgerichtet zu lassen, werden wir substruieren Z Byte in welchem (P % A = Z) => (Z ∈ [0, A-1])

So the total memory to be allocated is:  SZ + W + MAX(Z) = SZ + W + A - 1

Der zurückzugebende Zeiger ist P + Y = P + W + MAX(Z) – (P + W + MAX(Z)) mod A

WIR HABEN: X – X mod A = INT(X / A) * A = X & ~(A – 1)

SO können wir ersetzen P + W + MAX(Z) – (P + W + MAX(Z)) mod A durch (P + W + MAX(Z)) & ~(A – 1)

The memory to be returned is: (P + W + MAX(Z)) & ~(A - 1) = (P + W + A - 1) & ~(A - 1)

Ich habe ein paar Probleme mit diesem Code. Ich habe sie in der folgenden Liste zusammengestellt:

1. p1 = (void*)malloc Sie wandeln den Rückgabewert von malloc nicht um.
2. free(((void**)p)[-1]); Sie werfen nicht frei.
3. if ((p1 = (void*)malloc(required_bytes + offset)) == NULL) Fügen Sie keine Zuweisung in den Vergleich einer if-Anweisung ein. Ich weiß, dass viele Leute das tun, aber meiner Meinung nach ist das einfach schlechter Stil und macht den Code schwieriger zu lesen.

Was sie hier tun, ist das Speichern des ursprünglichen Zeigers innerhalb des zugewiesenen Blocks. Das bedeutet, dass nur der ausgerichtete Zeiger an den Benutzer zurückgegeben wird. Den eigentlichen Zeiger, der von malloc zurückgegeben wird, sieht der Benutzer nie. Sie müssen diesen Zeiger jedoch beibehalten, da free ihn benötigt, um den Block von der zugewiesenen Liste zu trennen und ihn auf die freie Liste zu setzen. An den Kopf jedes Speicherblocks stellt malloc dort einige Verwaltungsinformationen. Dinge wie Next/Prev-Zeiger, Größe, Zuordnungsstatus usw. Einige Debug-Versionen von malloc verwenden Schutzwörter, um zu prüfen, ob etwas den Puffer übergelaufen hat. Die Ausrichtung, die an die Routine übergeben wird MUSS eine Potenz von 2 sein.

Als ich meine eigene Version von malloc für die Verwendung in einem gepoolten Speicherzuordner schrieb, betrug die minimale Blockgröße, die ich verwendete, 8 Byte. Einschließlich des Headers für ein 32-Bit-System betrug die Gesamtzahl also 28 Bytes (20 Bytes für den Header). Auf einem 64-Bit-System waren es 40 Bytes (32 Bytes für den Header). Die meisten Systeme haben eine erhöhte Leistung, wenn Daten auf einen Adresswert ausgerichtet sind (entweder 4 oder 8 Bytes auf modernen Computersystemen). Der Grund dafür liegt darin, dass die Maschine das gesamte Wort in einem Buszyklus erfassen kann, wenn es ausgerichtet ist. Wenn nicht, dann benötigt es zwei Buszyklen, um das gesamte Wort zu erhalten, dann muss es es aufbauen. Aus diesem Grund richten Compiler Variablen entweder auf 4 oder 8 Bytes aus. Das bedeutet, dass die letzten 2 oder 3 Bits des Adressbusses Null sind.

Ich weiß, dass es einige Hardwarebeschränkungen gibt, die mehr Ausrichtung erfordern als die Standardeinstellung 4 oder 8. Wenn ich mich richtig erinnere, erfordert das CUDA-System von Nvidia eine Ausrichtung auf 256 Bytes … und das ist eine Hardwareanforderung.

Das wurde aber schon mal gefragt. Siehe: So weisen Sie ausgerichteten Speicher nur mit der Standardbibliothek zu?

Hoffe das hilft.