Benutzerdefiniertes malloc() Implementierung Header-Design

Question

Ich versuche, einen benutzerdefinierten Zuordner für Debugging-Zwecke (als Übung) in C zu schreiben, wo ich eine einzelne verknüpfte Liste verwenden werde, um die freie Liste des Speichers mit der ersten Anpassung zusammenzuhalten Algorithmus. Ich habe unten die Struktur gezeigt, die ich in einem "leeren Speicherknoten" erstellen möchte.

Wie schreibe ich den Header-Block (eine Union um genau zu sein) auf die ersten paar Bytes des Speichers, ich bekomme (ich benutze malloc(), um zunächst ein Stück Speicher), so dass die restlichen Bytes sind frei?

Dies ist die Vereinigung ich verwende:

/*Define Header Structure for proper alignment*/ 
union header { 
struct{ 
    union header* next; 
    unsigned size ; /*Make it size_t*/ 
}s; 
double dummy_align_var; 
}; 

------------------------------------------------------------------------------- 
|Next  |Size of |16Byte| User is concerned only about |16Byte|   | 
|Free Memory |Allocated|Header| this portion of memory  |Footer|Checksum | 
|Address  |Block |Picket| and has no knowledge of rest |Picket|   | 
------------------------------------------------------------------------------- 
|-------Header---------|  ^Address Returned to user 
           ^------User Requested Size-----^ 
^-------------Memory Obtained From The Operating System-----------------------^ 
*/ 

[EDIT] geändert Blockstruktur nach Anregungen zur Verfügung gestellt.

Answer 1

Warum verwenden Sie eine Union? Verwenden Sie einfach einen struct und geben Sie &dummy_align_var als den Anfang des freien Blocks an den Benutzer zurück.

Oh, und da dies zum Debuggen ist, schlage ich vor, dass Sie eine Mungwall hinzufügen: Setzen Sie 16 Bytes auf beiden Seiten des Benutzerbereichs und füllen Sie sie mit einem Muster (zum Beispiel 0xdeadbeef, viermal wiederholt). Überprüfen Sie unter free(), ob sich diese Bytes nicht geändert haben.

[EDIT] Hier einige Pseudo-Code:

struct header { 
    struct header * next; 
    unsigned size; 
    // put mungwall here 
    double user_data; 
}; 

init() 
    int blockSize = 1024; 
    char * bigMem = original_malloc(blockSize); 
    struct header * first = (struct header *)bigMem; 
    first->next = NULL; 
    first->size = blockSize - (sizeof(struct header) - sizeof(double)); 

Answer 2

Sie können auch die dummy_align_var als union header* prev so erklären wollen, dass Sie die freien Speicherblöcke in einer doppelt verknüpften Liste setzen können.

Dies hilft sehr bei der Leistung, wenn Sie einen freigegebenen Block mit den vorherigen und nächsten Schwarzen zusammenführen wollen, falls diese ebenfalls frei sind.

Schließlich erwähnen Sie es nicht, halten Sie die Liste sortiert nach Größe macht es schneller zu finden den besten Block für eine bestimmte Anfrage zuzuordnen, während nach Adresse sortiert erleichtert es, freigegebene Blöcke zusammenzuführen. Wenn Sie beides tun wollen, machen Sie den Benutzerbereich mindestens 3 header* groß, es wird die Zeiger passen, die benötigt werden, wenn der Block freigegeben wird.

Zusätzlich zu den Grenzen, die Aaron erwähnt, überschreiben freigegebene Puffer mit dem gleichen Muster. Dies erleichtert die Erkennung von Code, der bereits freigegebene Puffer verwendet.

Answer 3

Wenn Sie nicht malloc verwenden möchten(), sollten Sie einen Blick auf sbrk

Answer 4

ich vorschlagen würde nützlich sein: Vor einigen Jahren wurde ich ein Backup malloc benötigt() Einrichtung für Zwecke Debuggen (allocation Tracer und so weiter) ... Und es war ziemlich einfach, die FreeBSD-Implementierung von ihrer libstdc zu nehmen. Es war so, wie ich mich an FreeBSD 5.0 ​​oder sogar 4.x späte Veröffentlichungen erinnere, aber das Lustige war, dass ihre Einrichtung in der einfachen Bibliothek malloc.o-Modul isoliert war, so dass das Überladen dieser Ebene sehr einfach war und die Implementierung wirklich gut war.

Müssen Sie wirklich all diese Arbeit machen? Ja, es ist nur ein Punkt zu überprüfen, ich behaupte nicht, dass diese Lösung die beste ist.

Answer 5

würde ich so etwas wie

#define MEM_ALIGN 4 // 8 on 64b eventually 

struct header { 
    union aligned_header { 
     struct _s { 
      union aligned_header* next; 
      size_t size; 
     } data; 
     char dummy_align_var[sizeof(struct _s) + sizeof(struct _s)%MEM_ALIGN]; 
    } header_data; 
    char user_address; 
}; 

tun und &user_address zurückzukehren.

Answer 6

Sie können Ihre ursprüngliche Vereinigung verwenden, wenn Sie möchten, etwa so:

union header *hdr = malloc(total_size); 
void *user_ptr = hdr + 1; 
char *trailer_ptr = (char *)user_ptr + user_size; 

Die user_ptr, wo die nächsten union header beginnen würde eingestellt werden, wenn der malloc ed Block wurde als ein Array von diesen Gewerkschaften behandelt. Das ist der Wert, den Sie an den Benutzer zurückgeben.

Es setzt auch trailer_ptr, um auf das erste Byte nach der Benutzerzuweisung zu zeigen, wo Sie Ihre Prüfsumme setzen können.

Answer 7

Verwenden Sie zum Debuggen von malloc möglicherweise Padding-Platz zwischen Ihrer Kontrollstruktur und dem Start der Benutzerdaten sowie zwischen dem Ende der Benutzerdaten und der Prüfsumme. Ein Byte des Auffüllens sollte ein Nullbyte 0x00 sein - so stoppen Zeichenkettenoperationen; überlege, einen anderen als 0xFF zu setzen. Wenn Sie ein festes Muster haben und feststellen, dass es sich geändert hat, wissen Sie, dass etwas in den Grenzbereich gerutscht ist - aber es besteht eine größere Chance, dass Ihre sensiblen Kontrolldaten nicht mit Füßen getreten wurden. Wenn Sie auf beiden Seiten des dem Benutzer zugewiesenen Speicherplatzes 16 Byte Padding verwenden, können Sie so weit gehen, 4 Bytes von Nullen passend ausgerichtet (also eine ganze Zahl von 4 Byte) und vielleicht 0xFFFFFFFF für -1 zu setzen. Da Sie die angeforderte Größe wahrscheinlich auf ein Vielfaches Ihrer Basisblockgröße aufgerundet haben, legen Sie die Bytes, die der Benutzer nicht verwenden soll, auf einen bekannten Wert fest - und bestätigen Sie, dass sie unverändert bleiben. Dadurch werden Änderungen von "Eins über die zugewiesene Länge" oder nur wenige Byte über die zugewiesene Länge erkannt, die ansonsten unerkannt bleiben könnten.

Der einzige Nachteil des Null-Byte in Padding ist, dass Sie Leseoperationen nicht erkennen, die nicht am Ende des reservierten Speichers anhalten, wenn Sie nach einem Nullbyte suchen. Sie könnten Einblick in diese erhalten, indem Sie eine alternative Option verwenden, die Padding ohne Nullbytes verwendet.

Eine andere Option, die in Betracht gezogen werden sollte, besteht darin, die Steuerdaten vollständig vom Speicher zu trennen, der an den Benutzer zurückgegeben wird. Natürlich ist eine vollständige Trennung unmöglich, aber zumindest eine Liste von Zuordnungen (mit Größen und Zeigern) getrennt von den zugewiesenen Blöcken. Auch dies schützt Sie, indem Sie Ihre wertvollen Kontrolldaten vor unkontrollierten Speichertrampeln schützen. Sie sind nicht vollständig vor fehlerhaften Zeigern geschützt, aber Sie sind besser geschützt. (Und Sie können weiterhin Pufferzonen um den zugewiesenen Speicherplatz herum bereitstellen, um außer Kontrolle geratenes Schreiben zu erkennen.) Dieses Design unterscheidet sich jedoch deutlich von der Frage.

---

Vorausgesetzt, dass Sie Ihren Speicherblock Suche von 'malloc()', dann würden Sie tun - etwa:

void *my_malloc(size_t nbytes) 
{ 
    size_t reqblocks = (nbytes + sizeof(header) - 1)/sizeof(header); 
    size_t reqspace = (reqblocks + 2) * sizeof(header) + 2 * sizeof(padding); 
    void *space = malloc(reqspace); 
    if (space == 0) 
     return space; 
    void *retval = (char *)space + sizeof(header) + sizeof(padding); 
    header *head = space; 
    head->next = ...next...; 
    head->size = nbytes; 
    ...set head padding to chosen value... 
    ...set tail padding to chosen value... 
    ...set gap between nbytes and block boundary to chosen value... 
    return retval; 
} 

Es gibt einige Interpretation noch zu tun ...