Bins & Memory Allocations

Unterstützen Sie HackTricks

Grundlegende Informationen

Um die Effizienz bei der Speicherung von Chunks zu verbessern, ist jeder Chunk nicht nur in einer verketteten Liste, sondern es gibt mehrere Typen. Diese werden als Bins bezeichnet und es gibt 5 Arten von Bins: 62 Small Bins, 63 Large Bins, 1 Unsorted Bin, 10 Fast Bins und 64 Tcache Bins pro Thread.

Die Anfangsadresse für jeden unsortierten, kleinen und großen Bin befindet sich im selben Array. Der Index 0 wird nicht verwendet, 1 ist der unsortierte Bin, Bins 2-64 sind kleine Bins und Bins 65-127 sind große Bins.

Tcache (Pro-Thread-Cache) Bins

Obwohl Threads versuchen, ihren eigenen Heap zu haben (siehe Arenas und Subheaps), besteht die Möglichkeit, dass ein Prozess mit vielen Threads (wie ein Webserver) den Heap mit anderen Threads teilen wird. In diesem Fall ist die Hauptlösung die Verwendung von Sperren, die die Threads erheblich verlangsamen können.

Daher ist ein Tcache ähnlich wie ein Fast Bin pro Thread in der Hinsicht, dass es sich um eine einfach verkettete Liste handelt, die Chunks nicht zusammenführt. Jeder Thread hat 64 einfach verkettete Tcache-Bins. Jeder Bin kann maximal 7 Chunks gleicher Größe haben, die von 24 bis 1032B auf 64-Bit-Systemen und 12 bis 516B auf 32-Bit-Systemen reichen.

Wenn ein Thread einen Chunk freigibt, wenn er nicht zu groß ist, um im Tcache allokiert zu werden, und der entsprechende Tcache-Bin nicht voll ist (bereits 7 Chunks), wird er dort allokiert. Wenn er nicht in den Tcache gehen kann, muss er auf das Sperren des Heaps warten, um die Freigabeoperation global durchführen zu können.

Wenn ein Chunk allokiert wird, und es im Tcache einen freien Chunk der benötigten Größe gibt, wird dieser verwendet, andernfalls muss auf das Sperren des Heaps gewartet werden, um einen im globalen Bin zu finden oder einen neuen zu erstellen. Es gibt auch eine Optimierung, in diesem Fall, während das Sperren des Heaps, wird der Thread seinen Tcache mit Heap-Chunks (7) der angeforderten Größe füllen, sodass er sie im Tcache finden kann, falls er mehr benötigt.

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

int main(void)
{
char *chunk;
chunk = malloc(24);
printf("Address of the chunk: %p\n", (void *)chunk);
gets(chunk);
free(chunk);
return 0;
}

Kompilieren Sie es und debuggen Sie es mit einem Breakpoint im ret-Opcode der Hauptfunktion. Dann können Sie mit gef den tcache-Bin in Benutzung sehen:

gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=0, size=0x20, count=1] ←  Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)

Tcache-Strukturen & Funktionen

Im folgenden Code ist es möglich, die max bins und chunks per index, die tcache_entry Struktur, die erstellt wurde, um doppelte Freigaben zu vermeiden, und tcache_perthread_struct, eine Struktur, die jeder Thread verwendet, um die Adressen zu jedem Index des Bins zu speichern, zu sehen.

tcache_entry und tcache_perthread_struct

```c // From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c

/* We want 64 entries. This is an arbitrary limit, which tunables can reduce. */

define TCACHE_MAX_BINS 64

define MAX_TCACHE_SIZE tidx2usize (TCACHE_MAX_BINS-1)

/* Only used to pre-fill the tunables. */

define tidx2usize(idx) (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)

/* When "x" is from chunksize(). */

define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)

/* When "x" is a user-provided size. */

define usize2tidx(x) csize2tidx (request2size (x))

/* With rounding and alignment, the bins are... idx 0 bytes 0..24 (64-bit) or 0..12 (32-bit) idx 1 bytes 25..40 or 13..20 idx 2 bytes 41..56 or 21..28 etc. */

/* This is another arbitrary limit, which tunables can change. Each tcache bin will hold at most this number of chunks. */

define TCACHE_FILL_COUNT 7

/* Maximum chunks in tcache bins for tunables. This value must fit the range of tcache->counts[] entries, else they may overflow. */

define MAX_TCACHE_COUNT UINT16_MAX

[...]

typedef struct tcache_entry { struct tcache_entry next; / This field exists to detect double frees. */ uintptr_t key; } tcache_entry;

/* There is one of these for each thread, which contains the per-thread cache (hence "tcache_perthread_struct"). Keeping overall size low is mildly important. Note that COUNTS and ENTRIES are redundant (we could have just counted the linked list each time), this is for performance reasons. */ typedef struct tcache_perthread_struct { uint16_t counts[TCACHE_MAX_BINS]; tcache_entry *entries[TCACHE_MAX_BINS]; } tcache_perthread_struct;

</details>

Die Funktion `__tcache_init` ist die Funktion, die den Speicher für das Objekt `tcache_perthread_struct` erstellt und zuweist.

<details>

<summary>tcache_init Code</summary>
```c
// From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L3241C1-L3274C2

static void
tcache_init(void)
{
mstate ar_ptr;
void *victim = 0;
const size_t bytes = sizeof (tcache_perthread_struct);

if (tcache_shutting_down)
return;

arena_get (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
if (!victim && ar_ptr != NULL)
{
ar_ptr = arena_get_retry (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
}


if (ar_ptr != NULL)
__libc_lock_unlock (ar_ptr->mutex);

/* In a low memory situation, we may not be able to allocate memory
- in which case, we just keep trying later.  However, we
typically do this very early, so either there is sufficient
memory, or there isn't enough memory to do non-trivial
allocations anyway.  */
if (victim)
{
tcache = (tcache_perthread_struct *) victim;
memset (tcache, 0, sizeof (tcache_perthread_struct));
}

}

Tcache-Indizes

Die Tcache verfügt über mehrere Bins, abhängig von der Größe und den initialen Zeigern auf den ersten Chunk jedes Index und die Anzahl der Chunks pro Index sind innerhalb eines Chunks gespeichert. Dies bedeutet, dass durch Lokalisierung des Chunks mit diesen Informationen (normalerweise der erste) alle Tcache-Startpunkte und die Anzahl der Tcache-Chunks gefunden werden können.

Fast Bins

Fast Bins sind darauf ausgelegt, die Speicherzuweisung für kleine Chunks zu beschleunigen, indem kürzlich freigegebene Chunks in einer schnell zugänglichen Struktur aufbewahrt werden. Diese Bins verwenden einen Last-In, First-Out (LIFO)-Ansatz, was bedeutet, dass der zuletzt freigegebene Chunk der erste ist, der wiederverwendet wird, wenn eine neue Zuweisungsanforderung vorliegt. Dieses Verhalten ist vorteilhaft für die Geschwindigkeit, da es schneller ist, am oberen Ende eines Stapels (LIFO) einzufügen und zu entfernen im Vergleich zu einer Warteschlange (FIFO).

Zusätzlich verwenden Fast Bins einfach verkettete Listen, nicht doppelt verkettete, was die Geschwindigkeit weiter verbessert. Da Chunks in Fast Bins nicht mit Nachbarchunks zusammengeführt werden, ist keine komplexe Struktur erforderlich, die das Entfernen aus der Mitte ermöglicht. Eine einfach verkettete Liste ist einfacher und schneller für diese Operationen.

Im Grunde genommen zeigt der Header (der Zeiger auf den ersten Chunk, der überprüft werden soll) immer auf den zuletzt freigegebenen Chunk dieser Größe. Also:

  • Wenn ein neuer Chunk dieser Größe zugewiesen wird, zeigt der Header auf einen freien Chunk, der verwendet werden kann. Da dieser freie Chunk auf den nächsten zu verwendenden zeigt, wird diese Adresse im Header gespeichert, damit die nächste Zuweisung weiß, wo sie einen verfügbaren Chunk erhalten kann.

  • Wenn ein Chunk freigegeben wird, speichert der freie Chunk die Adresse des aktuellen verfügbaren Chunks und die Adresse dieses neu freigegebenen Chunks wird im Header platziert.

Die maximale Größe einer verketteten Liste beträgt 0x80 und sie sind so organisiert, dass ein Chunk der Größe 0x20 im Index 0 liegt, ein Chunk der Größe 0x30 im Index 1...

Chunks in Fast Bins werden nicht als verfügbar festgelegt, sodass sie für einige Zeit als Fast Bin Chunks gehalten werden, anstatt sich mit anderen freien Chunks in ihrer Umgebung zusammenführen zu können.

// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711

/*
Fastbins

An array of lists holding recently freed small chunks.  Fastbins
are not doubly linked.  It is faster to single-link them, and
since chunks are never removed from the middles of these lists,
double linking is not necessary. Also, unlike regular bins, they
are not even processed in FIFO order (they use faster LIFO) since
ordering doesn't much matter in the transient contexts in which
fastbins are normally used.

Chunks in fastbins keep their inuse bit set, so they cannot
be consolidated with other free chunks. malloc_consolidate
releases all chunks in fastbins and consolidates them with
other free chunks.
*/

typedef struct malloc_chunk *mfastbinptr;
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])

/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz) \
((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)


/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)

#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
Fügen Sie ein Beispiel für einen Fastbin-Chunk hinzu

```c #include #include

int main(void) { char *chunks[8]; int i;

// Loop to allocate memory 8 times for (i = 0; i < 8; i++) { chunks[i] = malloc(24); if (chunks[i] == NULL) { // Check if malloc failed fprintf(stderr, "Memory allocation failed at iteration %d\n", i); return 1; } printf("Address of chunk %d: %p\n", i, (void *)chunks[i]); }

// Loop to free the allocated memory for (i = 0; i < 8; i++) { free(chunks[i]); }

return 0; }

Beachten Sie, wie wir 8 Chunks derselben Größe zuweisen und freigeben, sodass sie den tcache füllen und der achte im fast chunk gespeichert wird.

Kompilieren Sie es und debuggen Sie es mit einem Breakpoint im `ret` Opcode der `main` Funktion. Dann können Sie mit `gef` sehen, dass der tcache-Bin voll ist und ein Chunk im fast bin ist:
```bash
gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=0, size=0x20, count=7] ←  Chunk(addr=0xaaaaaaac1770, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1750, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1730, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1710, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac16f0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac16d0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20]  ←  Chunk(addr=0xaaaaaaac1790, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
Fastbins[idx=1, size=0x30] 0x00

Unsortierter Bin

Der unsortierte Bin ist ein Cache, den der Heap-Manager verwendet, um die Speicherzuweisung zu beschleunigen. So funktioniert es: Wenn ein Programm einen Chunk freigibt und dieser Chunk weder in einem tcache oder Fast Bin allokiert werden kann noch mit dem Top-Chunk kollidiert, legt der Heap-Manager ihn nicht sofort in einen spezifischen kleinen oder großen Bin. Stattdessen versucht er zuerst, ihn mit benachbarten freien Chunks zu verschmelzen, um einen größeren Block freien Speichers zu erstellen. Anschließend platziert er diesen neuen Chunk in einem allgemeinen Bin namens "unsortierter Bin".

Wenn ein Programm nach Speicher fragt, überprüft der Heap-Manager den unsortierten Bin, um zu sehen, ob es einen ausreichend großen Chunk gibt. Wenn er einen findet, verwendet er ihn sofort. Wenn er keinen geeigneten Chunk im unsortierten Bin findet, verschiebt er alle Chunks in dieser Liste in ihre entsprechenden Bins, entweder klein oder groß, basierend auf ihrer Größe.

Beachten Sie, dass wenn ein größerer Chunk in 2 Hälften aufgeteilt wird und der Rest größer als MINSIZE ist, wird er wieder in den unsortierten Bin gelegt.

Der unsortierte Bin ist also eine Möglichkeit, die Speicherzuweisung zu beschleunigen, indem kürzlich freigegebener Speicher schnell wiederverwendet wird und die Notwendigkeit für zeitaufwändige Suchen und Verschmelzungen reduziert wird.

Beachten Sie, dass selbst wenn Chunks unterschiedlichen Kategorien angehören, wenn ein verfügbarer Chunk mit einem anderen verfügbaren Chunk kollidiert (auch wenn sie ursprünglich zu verschiedenen Bins gehörten), werden sie zusammengeführt.

Fügen Sie ein Beispiel für einen unsortierten Chunk hinzu

```c #include #include

int main(void) { char *chunks[9]; int i;

// Loop to allocate memory 8 times for (i = 0; i < 9; i++) { chunks[i] = malloc(0x100); if (chunks[i] == NULL) { // Check if malloc failed fprintf(stderr, "Memory allocation failed at iteration %d\n", i); return 1; } printf("Address of chunk %d: %p\n", i, (void *)chunks[i]); }

// Loop to free the allocated memory for (i = 0; i < 8; i++) { free(chunks[i]); }

return 0; }

Beachten Sie, wie wir 9 Chunks derselben Größe zuweisen und freigeben, damit sie den **tcache füllen** und der achte im unsortierten Bin gespeichert wird, weil er **zu groß für den fastbin ist** und der neunte nicht freigegeben wird, sodass der neunte und der achte **nicht mit dem Top-Chunk zusammengeführt werden**.

Kompilieren Sie es und debuggen Sie es mit einem Breakpoint im `ret`-Opcode der `main`-Funktion. Dann können Sie mit `gef` sehen, dass der tcache-Bin voll ist und ein Chunk im unsortierten Bin liegt:
```bash
gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=15, size=0x110, count=7] ←  Chunk(addr=0xaaaaaaac1d10, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1c00, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1af0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac19e0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac18d0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac17c0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac12a0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20] 0x00
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
─────────────────────────────────────────────────────────────────────── Unsorted Bin for arena at 0xfffff7f90b00 ───────────────────────────────────────────────────────────────────────
[+] unsorted_bins[0]: fw=0xaaaaaaac1e10, bk=0xaaaaaaac1e10
→   Chunk(addr=0xaaaaaaac1e20, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[+] Found 1 chunks in unsorted bin.

Kleine Bins

Kleine Bins sind schneller als große Bins, aber langsamer als Fast Bins.

Jeder Bin der 62 wird Chunks der gleichen Größe haben: 16, 24, ... (mit einer maximalen Größe von 504 Bytes in 32-Bit und 1024 in 64-Bit). Dies hilft bei der Geschwindigkeit beim Auffinden des Bins, in dem ein Speicherplatz allokiert werden soll, sowie beim Einfügen und Entfernen von Einträgen in diesen Listen.

So wird die Größe des kleinen Bins gemäß dem Index des Bins berechnet:

  • Kleinste Größe: 2*4*Index (z.B. Index 5 -> 40)

  • Größte Größe: 2*8*Index (z.B. Index 5 -> 80)

// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711
#define NSMALLBINS         64
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > CHUNK_HDR_SZ)
#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

#define in_smallbin_range(sz)  \
((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

#define smallbin_index(sz) \
((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
+ SMALLBIN_CORRECTION)

Funktion zum Auswählen zwischen kleinen und großen Bins:

#define bin_index(sz) \
((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))
Fügen Sie ein kleines Chunk-Beispiel hinzu

```c #include #include

int main(void) { char *chunks[10]; int i;

// Loop to allocate memory 8 times for (i = 0; i < 9; i++) { chunks[i] = malloc(0x100); if (chunks[i] == NULL) { // Check if malloc failed fprintf(stderr, "Memory allocation failed at iteration %d\n", i); return 1; } printf("Address of chunk %d: %p\n", i, (void *)chunks[i]); }

// Loop to free the allocated memory for (i = 0; i < 8; i++) { free(chunks[i]); }

chunks[9] = malloc(0x110);

return 0; }

Beachten Sie, wie wir 9 Chunks derselben Größe zuweisen und freigeben, damit sie den **tcache füllen** und der achte im unsortierten Bin gespeichert wird, weil er **zu groß für den fastbin ist** und der neunte nicht freigegeben wird, sodass der neunte und der achte **nicht mit dem Top-Chunk zusammengeführt werden**. Dann weisen wir einen größeren Chunk von 0x110 zu, wodurch **der Chunk im unsortierten Bin in den kleinen Bin gelangt**.

Kompilieren Sie es und debuggen Sie es mit einem Breakpoint im `ret`-Opcode der `main`-Funktion. Dann können Sie mit `gef` sehen, dass der tcache-Bin voll ist und ein Chunk im kleinen Bin liegt:
```bash
gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=15, size=0x110, count=7] ←  Chunk(addr=0xaaaaaaac1d10, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1c00, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1af0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac19e0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac18d0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac17c0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac12a0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20] 0x00
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
─────────────────────────────────────────────────────────────────────── Unsorted Bin for arena at 0xfffff7f90b00 ───────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in unsorted bin.
──────────────────────────────────────────────────────────────────────── Small Bins for arena at 0xfffff7f90b00 ────────────────────────────────────────────────────────────────────────
[+] small_bins[16]: fw=0xaaaaaaac1e10, bk=0xaaaaaaac1e10
→   Chunk(addr=0xaaaaaaac1e20, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[+] Found 1 chunks in 1 small non-empty bins.

Große Bins

Im Gegensatz zu kleinen Bins, die Chunks fester Größen verwalten, handhabt jede große Bin eine Reihe von Chunk-Größen. Dies ist flexibler und ermöglicht es dem System, verschiedene Größen zu berücksichtigen, ohne für jede Größe eine separate Bin zu benötigen.

In einem Speicherzuweiser beginnen große Bins dort, wo kleine Bins enden. Die Bereiche für große Bins werden progressiv größer, was bedeutet, dass die erste Bin Chunks von 512 bis 576 Bytes abdecken könnte, während die nächste 576 bis 640 Bytes abdeckt. Dieses Muster setzt sich fort, wobei die größte Bin alle Chunks über 1 MB enthält.

Große Bins sind langsamer in der Bedienung im Vergleich zu kleinen Bins, da sie durch eine Liste von variierenden Chunk-Größen sortieren und suchen müssen, um die beste Passform für eine Zuweisung zu finden. Wenn ein Chunk in eine große Bin eingefügt wird, muss er sortiert werden, und wenn Speicher allokiert wird, muss das System den richtigen Chunk finden. Diese zusätzliche Arbeit macht sie langsamer, aber da große Zuweisungen seltener sind als kleine, ist dies ein akzeptabler Kompromiss.

Es gibt:

  • 32 Bins im Bereich von 64B (kollidieren mit kleinen Bins)

  • 16 Bins im Bereich von 512B (kollidieren mit kleinen Bins)

  • 8 Bins im Bereich von 4096B (teilweise kollidieren mit kleinen Bins)

  • 4 Bins im Bereich von 32768B

  • 2 Bins im Bereich von 262144B

  • 1 Bin für verbleibende Größen

Code für große Bin-Größen

```c // From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711

#define largebin_index_32(sz) (((((unsigned long) (sz)) >> 6) <= 38) ? 56 + (((unsigned long) (sz)) >> 6) : ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) : ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) : ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) : ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) : 126)

#define largebin_index_32_big(sz) (((((unsigned long) (sz)) >> 6) <= 45) ? 49 + (((unsigned long) (sz)) >> 6) : ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) : ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) : ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) : ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) : 126)

// XXX It remains to be seen whether it is good to keep the widths of // XXX the buckets the same or whether it should be scaled by a factor // XXX of two as well. #define largebin_index_64(sz) (((((unsigned long) (sz)) >> 6) <= 48) ? 48 + (((unsigned long) (sz)) >> 6) : ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) : ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) : ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) : ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) : 126)

#define largebin_index(sz) (SIZE_SZ == 8 ? largebin_index_64 (sz) : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz) : largebin_index_32 (sz))

</details>

<details>

<summary>Fügen Sie ein Beispiel für einen großen Chunk hinzu</summary>
```c
#include <stdlib.h>
#include <stdio.h>

int main(void)
{
char *chunks[2];

chunks[0] = malloc(0x1500);
chunks[1] = malloc(0x1500);
free(chunks[0]);
chunks[0] = malloc(0x2000);

return 0;
}

Zwei große Zuweisungen werden durchgeführt, dann wird eine freigegeben (wodurch sie in den unsortierten Bin gelangt) und eine größere Zuweisung erfolgt (wodurch die freigegebene in den großen Bin verschoben wird).

Kompilieren Sie es und debuggen Sie es mit einem Haltepunkt im ret Opcode der main Funktion. Dann können Sie mit gef sehen, dass der tcache Bin voll ist und ein Chunk im großen Bin liegt:

gef➤  heap bin
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
All tcachebins are empty
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20] 0x00
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
─────────────────────────────────────────────────────────────────────── Unsorted Bin for arena at 0xfffff7f90b00 ───────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in unsorted bin.
──────────────────────────────────────────────────────────────────────── Small Bins for arena at 0xfffff7f90b00 ────────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in 0 small non-empty bins.
──────────────────────────────────────────────────────────────────────── Large Bins for arena at 0xfffff7f90b00 ────────────────────────────────────────────────────────────────────────
[+] large_bins[100]: fw=0xaaaaaaac1290, bk=0xaaaaaaac1290
   Chunk(addr=0xaaaaaaac12a0, size=0x1510, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[+] Found 1 chunks in 1 large non-empty bins.

Oberster Chunk

// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711

/*
Top

The top-most available chunk (i.e., the one bordering the end of
available memory) is treated specially. It is never included in
any bin, is used only if no other chunk is available, and is
released back to the system if it is very large (see
M_TRIM_THRESHOLD).  Because top initially
points to its own bin with initial zero size, thus forcing
extension on the first malloc request, we avoid having any special
code in malloc to check whether it even exists yet. But we still
need to do so when getting memory from system, so we make
initial_top treat the bin as a legal but unusable chunk during the
interval between initialization and the first call to
sysmalloc. (This is somewhat delicate, since it relies on
the 2 preceding words to be zero during this interval as well.)
*/

/* Conveniently, the unsorted bin can be used as dummy top on first call */
#define initial_top(M)              (unsorted_chunks (M))

Grundsätzlich handelt es sich hier um einen Chunk, der den gesamten derzeit verfügbaren Heap enthält. Wenn ein malloc durchgeführt wird und kein verfügbarer freier Chunk vorhanden ist, wird dieser Top-Chunk seine Größe reduzieren und den benötigten Speicherplatz bereitstellen. Der Zeiger auf den Top-Chunk wird in der malloc_state Struktur gespeichert.

Darüber hinaus ist es am Anfang möglich, den unsortierten Chunk als Top-Chunk zu verwenden.

Beispiel für den Top-Chunk beobachten

```c #include #include

int main(void) { char *chunk; chunk = malloc(24); printf("Address of the chunk: %p\n", (void *)chunk); gets(chunk); return 0; }

Nach dem Kompilieren und Debuggen mit einem Breakpoint im `ret`-Opcode von `main` sah ich, dass das malloc die Adresse `0xaaaaaaac12a0` zurückgab und das sind die Chunks:
```bash
gef➤  heap chunks
Chunk(addr=0xaaaaaaac1010, size=0x290, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac1010     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac12a0     41 41 41 41 41 41 41 00 00 00 00 00 00 00 00 00    AAAAAAA.........]
Chunk(addr=0xaaaaaaac12c0, size=0x410, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac12c0     41 64 64 72 65 73 73 20 6f 66 20 74 68 65 20 63    Address of the c]
Chunk(addr=0xaaaaaaac16d0, size=0x410, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac16d0     41 41 41 41 41 41 41 0a 00 00 00 00 00 00 00 00    AAAAAAA.........]
Chunk(addr=0xaaaaaaac1ae0, size=0x20530, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  top chunk

Wo es gesehen werden kann, dass der Top Chunk unter der Adresse 0xaaaaaaac1ae0 liegt. Dies ist keine Überraschung, da der zuletzt allokierte Chunk unter 0xaaaaaaac12a0 mit einer Größe von 0x410 war und 0xaaaaaaac12a0 + 0x410 = 0xaaaaaaac1ae0. Es ist auch möglich, die Länge des Top Chunks an seinem Chunk-Header zu sehen:

gef➤  x/8wx 0xaaaaaaac1ae0 - 16
0xaaaaaaac1ad0:	0x00000000	0x00000000	0x00020531	0x00000000
0xaaaaaaac1ae0:	0x00000000	0x00000000	0x00000000	0x00000000

Letzter Rest

Wenn malloc verwendet wird und ein Chunk geteilt wird (zum Beispiel aus dem unsortierten Bin oder aus dem Top-Chunk), wird der aus dem Rest des geteilten Chunks erstellte Chunk als Letzter Rest bezeichnet und sein Zeiger wird im malloc_state-Struktur gespeichert.

Zuweisungsfluss

Schau dir an:

Freigabefluss

Schau dir an:

Sicherheitsüberprüfungen der Heap-Funktionen

Überprüfe die Sicherheitsüberprüfungen, die von stark genutzten Funktionen im Heap durchgeführt werden, in:

Referenzen

Unterstütze HackTricks

Last updated