Bins & Memory Allocations

Apoya a HackTricks

Información Básica

Para mejorar la eficiencia en cómo se almacenan los fragmentos, cada fragmento no está solo en una lista enlazada, sino que hay varios tipos. Estos son los bins y hay 5 tipos de bins: 62 bins pequeños, 63 bins grandes, 1 bin desordenado, 10 bins rápidos y 64 bins tcache por hilo.

La dirección inicial de cada bin desordenado, pequeño y grande está dentro del mismo array. El índice 0 no se usa, el 1 es el bin desordenado, los bins 2-64 son bins pequeños y los bins 65-127 son bins grandes.

Bins Tcache (Memoria Caché por Hilo)

Aunque los hilos intentan tener su propio montón (ver Arenas y Submontones), existe la posibilidad de que un proceso con muchos hilos (como un servidor web) termine compartiendo el montón con otros hilos. En este caso, la solución principal es el uso de bloqueadores, que podrían ralentizar significativamente los hilos.

Por lo tanto, un tcache es similar a un bin rápido por hilo en el sentido de que es una lista enlazada simple que no fusiona fragmentos. Cada hilo tiene 64 bins tcache enlazados individualmente. Cada bin puede tener un máximo de 7 fragmentos del mismo tamaño que van desde 24 a 1032B en sistemas de 64 bits y de 12 a 516B en sistemas de 32 bits.

Cuando un hilo libera un fragmento, si no es demasiado grande para ser asignado en el tcache y el bin tcache respectivo no está lleno (ya tiene 7 fragmentos), se asignará allí. Si no puede ir al tcache, deberá esperar a que el bloqueo del montón esté disponible para poder realizar la operación de liberación globalmente.

Cuando se asigna un fragmento, si hay un fragmento libre del tamaño necesario en el tcache, se utilizará, de lo contrario, deberá esperar a que el bloqueo del montón esté disponible para encontrar uno en los bins globales o crear uno nuevo. También hay una optimización, en este caso, mientras tiene el bloqueo del montón, el hilo llenará su tcache con fragmentos del montón (7) del tamaño solicitado, por lo que en caso de necesitar más, los encontrará en el tcache.

Agregar un ejemplo de fragmento tcache

```c #include #include

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

Compílalo y depúralo con un punto de interrupción en el opcode ret de la función main. luego con gef puedes ver el bin tcache en uso:
```bash
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)

Estructuras y Funciones de Tcache

En el siguiente código es posible ver los bines máximos y trozos por índice, la estructura tcache_entry creada para evitar liberaciones dobles y tcache_perthread_struct, una estructura que cada hilo utiliza para almacenar las direcciones de cada índice del bin.

tcache_entry y 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>

La función `__tcache_init` es la función que crea y asigna el espacio para el objeto `tcache_perthread_struct`
```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));
}

}

Índices de Tcache

El tcache tiene varios bins dependiendo del tamaño y los punteros iniciales al primer chunk de cada índice y la cantidad de chunks por índice están ubicados dentro de un chunk. Esto significa que al localizar el chunk con esta información (generalmente el primero), es posible encontrar todos los puntos iniciales de tcache y la cantidad de chunks de Tcache.

Bins Rápidos

Los bins rápidos están diseñados para acelerar la asignación de memoria para pequeños chunks al mantener chunks liberados recientemente en una estructura de acceso rápido. Estos bins utilizan un enfoque de Último en Entrar, Primero en Salir (LIFO), lo que significa que el chunk liberado más recientemente es el primero en ser reutilizado cuando hay una nueva solicitud de asignación. Este comportamiento es ventajoso para la velocidad, ya que es más rápido insertar y eliminar desde la parte superior de una pila (LIFO) en comparación con una cola (FIFO).

Además, los bins rápidos utilizan listas enlazadas simples, no doblemente enlazadas, lo que mejora aún más la velocidad. Dado que los chunks en los bins rápidos no se fusionan con los vecinos, no es necesario una estructura compleja que permita la eliminación desde el medio. Una lista enlazada simple es más simple y rápida para estas operaciones.

Básicamente, lo que sucede aquí es que el encabezado (el puntero al primer chunk a verificar) siempre apunta al chunk liberado más recientemente de ese tamaño. Entonces:

  • Cuando se asigna un nuevo chunk de ese tamaño, el encabezado apunta a un chunk libre para usar. Como este chunk libre apunta al siguiente para usar, esta dirección se almacena en el encabezado para que la próxima asignación sepa dónde obtener un chunk disponible.

  • Cuando se libera un chunk, el chunk libre guardará la dirección al chunk disponible actual y la dirección a este chunk liberado recientemente se colocará en el encabezado.

El tamaño máximo de una lista enlazada es 0x80 y están organizadas de modo que un chunk de tamaño 0x20 estará en el índice 0, un chunk de tamaño 0x30 estaría en el índice 1...

Los chunks en los bins rápidos no se establecen como disponibles, por lo que se mantienen como chunks de bin rápido durante algún tiempo en lugar de poder fusionarse con otros chunks libres que los rodean.

// 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)

Agregar un ejemplo de fragmento fastbin

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

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;
}

Observa cómo asignamos y liberamos 8 fragmentos del mismo tamaño para que llenen el tcache y el octavo se almacene en el fragmento rápido.

Compílalo y depúralo con un punto de interrupción en el opcode ret de la función main. Luego, con gef, puedes ver que el contenedor tcache está lleno y un fragmento está en el contenedor rápido:

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

Bin sin ordenar

El bin sin ordenar es una caché utilizada por el administrador de montón para acelerar la asignación de memoria. Así es como funciona: Cuando un programa libera un fragmento, y si este fragmento no puede ser asignado en una tcache o fast bin y no está colisionando con el fragmento superior, el administrador de montón no lo coloca inmediatamente en un bin pequeño o grande específico. En su lugar, primero intenta fusionarlo con cualquier fragmento libre vecino para crear un bloque más grande de memoria libre. Luego, coloca este nuevo fragmento en un bin general llamado "bin sin ordenar".

Cuando un programa solicita memoria, el administrador de montón verifica el bin sin ordenar para ver si hay un fragmento de tamaño suficiente. Si encuentra uno, lo utiliza de inmediato. Si no encuentra un fragmento adecuado en el bin sin ordenar, mueve todos los fragmentos de esta lista a sus bins correspondientes, ya sea pequeños o grandes, según su tamaño.

Ten en cuenta que si un fragmento más grande se divide en 2 mitades y el resto es mayor que MINSIZE, se colocará nuevamente en el bin sin ordenar.

Por lo tanto, el bin sin ordenar es una forma de acelerar la asignación de memoria reutilizando rápidamente la memoria liberada recientemente y reduciendo la necesidad de búsquedas y fusiones que consumen tiempo.

Ten en cuenta que incluso si los fragmentos son de diferentes categorías, si un fragmento disponible está colisionando con otro fragmento disponible (incluso si pertenecen originalmente a diferentes bins), se fusionarán.

Agregar un ejemplo de fragmento sin ordenar

```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; }

Observa cómo asignamos y liberamos 9 fragmentos del mismo tamaño para que **llenen la tcache** y el octavo se almacene en el bin no ordenado porque es **demasiado grande para el fastbin** y el noveno no se libera, por lo que el noveno y el octavo **no se fusionan con el chunk superior**.

Compílalo y depúralo con un punto de interrupción en el opcode `ret` de la función `main`. Luego, con `gef`, puedes ver que el bin de la tcache está lleno y un fragmento está en el bin no ordenado:
```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.

Bins Pequeños

Los bins pequeños son más rápidos que los bins grandes pero más lentos que los bins rápidos.

Cada bin de los 62 tendrá trozos del mismo tamaño: 16, 24, ... (con un tamaño máximo de 504 bytes en 32 bits y 1024 en 64 bits). Esto ayuda en la velocidad para encontrar el bin donde se debe asignar un espacio e insertar y eliminar entradas en estas listas.

Así es como se calcula el tamaño del bin pequeño según el índice del bin:

  • Tamaño más pequeño: 2*4*índice (por ejemplo, índice 5 -> 40)

  • Tamaño más grande: 2*8*índice (por ejemplo, índice 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)

Función para elegir entre contenedores pequeños y grandes:

#define bin_index(sz) \
((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))

Agregar un ejemplo de pequeño fragmento

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

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;
}

Observa cómo asignamos y liberamos 9 fragmentos del mismo tamaño para que llenen la tcache y el octavo se almacene en el bin no ordenado porque es demasiado grande para el fastbin y el noveno no se libera, por lo que el noveno y el octavo no se fusionan con el fragmento superior. Luego asignamos un fragmento más grande de 0x110, lo que hace que el fragmento en el bin no ordenado pase al bin pequeño.

Compílalo y depúralo con un punto de interrupción en el opcode ret de la función main. Luego, con gef, puedes ver que el bin tcache está lleno y un fragmento está en el bin pequeño:

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.

Bins grandes

A diferencia de los bins pequeños, que manejan fragmentos de tamaños fijos, cada bin grande maneja un rango de tamaños de fragmentos. Esto es más flexible, permitiendo que el sistema pueda acomodar varios tamaños sin necesidad de un bin separado para cada tamaño.

En un asignador de memoria, los bins grandes comienzan donde terminan los bins pequeños. Los rangos para los bins grandes crecen progresivamente, lo que significa que el primer bin podría cubrir fragmentos de 512 a 576 bytes, mientras que el siguiente cubre de 576 a 640 bytes. Este patrón continúa, con el bin más grande que contiene todos los fragmentos por encima de 1MB.

Los bins grandes son más lentos de operar en comparación con los bins pequeños porque deben ordenar y buscar a través de una lista de tamaños de fragmentos variables para encontrar el mejor ajuste para una asignación. Cuando un fragmento se inserta en un bin grande, debe ser ordenado, y cuando se asigna memoria, el sistema debe encontrar el fragmento adecuado. Este trabajo adicional los hace más lentos, pero dado que las asignaciones grandes son menos comunes que las pequeñas, es un compromiso aceptable.

Hay:

  • 32 bins de rango de 64B (colisionan con los bins pequeños)

  • 16 bins de rango de 512B (colisionan con los bins pequeños)

  • 8 bins de rango de 4096B (parte colisiona con los bins pequeños)

  • 4 bins de rango de 32768B

  • 2 bins de rango de 262144B

  • 1 bin para tamaños restantes

Código de tamaños de bins grandes

```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>Agregar un ejemplo de un gran fragmento</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;
}

2 grandes asignaciones se realizan, luego una se libera (poniéndola en el bin no ordenado) y se realiza una asignación más grande (moviendo la liberada del bin no ordenado al bin grande).

Compílalo y depúralo con un punto de interrupción en el opcode ret de la función main. Luego, con gef, puedes ver que el bin tcache está lleno y un fragmento está en el bin grande:

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.

Trozo Superior

// 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))

Básicamente, este es un fragmento que contiene toda la memoria heap disponible actualmente. Cuando se realiza un malloc, si no hay ningún fragmento libre disponible para usar, este fragmento superior reducirá su tamaño proporcionando el espacio necesario. El puntero al Top Chunk se almacena en la estructura malloc_state.

Además, al principio, es posible utilizar el fragmento desordenado como el fragmento superior.

Observa el ejemplo del Top Chunk

```c #include #include

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

Después de compilar y depurarlo con un punto de interrupción en el opcode `ret` de `main`, vi que el malloc devolvió la dirección `0xaaaaaaac12a0` y estos son los 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

Donde se puede ver que el chunk superior está en la dirección 0xaaaaaaac1ae0. Esto no es sorprendente porque el último chunk asignado fue en 0xaaaaaaac12a0 con un tamaño de 0x410 y 0xaaaaaaac12a0 + 0x410 = 0xaaaaaaac1ae0. También es posible ver la longitud del chunk superior en su encabezado de chunk:

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

Último Resto

Cuando se utiliza malloc y se divide un fragmento (por ejemplo, del bin no ordenado o del fragmento superior), el fragmento creado a partir del resto del fragmento dividido se llama Último Resto y su puntero se almacena en la estructura malloc_state.

Flujo de Asignación

Consultar:

malloc & sysmalloc

Flujo de Liberación

Consultar:

free

Verificaciones de Seguridad de Funciones de Montón

Consultar las verificaciones de seguridad realizadas por funciones ampliamente utilizadas en el montón en:

Heap Functions Security Checks

Referencias

Apoya a HackTricks

Last updated