El heap es básicamente el lugar donde un programa podrá almacenar datos cuando solicita datos llamando a funciones como malloc, calloc... Además, cuando esta memoria ya no es necesaria, se hace disponible llamando a la función free.
Como se muestra, está justo después de donde el binario se está cargando en memoria (ver la sección [heap]):
Basic Chunk Allocation
Cuando se solicita almacenar algunos datos en el heap, se asigna un espacio del heap para ello. Este espacio pertenecerá a un bin y solo se reservarán los datos solicitados + el espacio de los encabezados del bin + el desplazamiento del tamaño mínimo del bin para el chunk. El objetivo es reservar la menor cantidad de memoria posible sin complicar la búsqueda de dónde se encuentra cada chunk. Para esto, se utiliza la información de metadatos del chunk para saber dónde se encuentra cada chunk usado/libre.
Hay diferentes formas de reservar el espacio, principalmente dependiendo del bin utilizado, pero una metodología general es la siguiente:
El programa comienza solicitando cierta cantidad de memoria.
Si en la lista de chunks hay uno disponible lo suficientemente grande para cumplir con la solicitud, se utilizará.
Esto puede incluso significar que parte del chunk disponible se utilizará para esta solicitud y el resto se añadirá a la lista de chunks.
Si no hay ningún chunk disponible en la lista pero aún hay espacio en la memoria del heap asignada, el administrador del heap crea un nuevo chunk.
Si no hay suficiente espacio en el heap para asignar el nuevo chunk, el administrador del heap solicita al kernel que expanda la memoria asignada al heap y luego utiliza esta memoria para generar el nuevo chunk.
Si todo falla, malloc devuelve null.
Tenga en cuenta que si la memoria solicitada supera un umbral, se utilizará mmap para mapear la memoria solicitada.
Arenas
En aplicaciones multihilo, el administrador del heap debe prevenir condiciones de carrera que podrían llevar a fallos. Inicialmente, esto se hacía utilizando un mutex global para asegurar que solo un hilo pudiera acceder al heap a la vez, pero esto causaba problemas de rendimiento debido al cuello de botella inducido por el mutex.
Para abordar esto, el asignador de heap ptmalloc2 introdujo "arenas", donde cada arena actúa como un heap separado con sus propias estructuras de datos y mutex, permitiendo que múltiples hilos realicen operaciones en el heap sin interferir entre sí, siempre que utilicen diferentes arenas.
La arena "principal" por defecto maneja operaciones de heap para aplicaciones de un solo hilo. Cuando se añaden nuevos hilos, el administrador del heap les asigna arenas secundarias para reducir la contención. Primero intenta adjuntar cada nuevo hilo a una arena no utilizada, creando nuevas si es necesario, hasta un límite de 2 veces el número de núcleos de CPU para sistemas de 32 bits y 8 veces para sistemas de 64 bits. Una vez alcanzado el límite, los hilos deben compartir arenas, lo que lleva a una posible contención.
A diferencia de la arena principal, que se expande utilizando la llamada al sistema brk, las arenas secundarias crean "subheaps" utilizando mmap y mprotect para simular el comportamiento del heap, permitiendo flexibilidad en la gestión de memoria para operaciones multihilo.
Subheaps
Los subheaps sirven como reservas de memoria para arenas secundarias en aplicaciones multihilo, permitiéndoles crecer y gestionar sus propias regiones de heap por separado del heap principal. Aquí se explica cómo los subheaps difieren del heap inicial y cómo operan:
Heap Inicial vs. Subheaps:
El heap inicial se encuentra directamente después del binario del programa en memoria, y se expande utilizando la llamada al sistema sbrk.
Los subheaps, utilizados por arenas secundarias, se crean a través de mmap, una llamada al sistema que mapea una región de memoria especificada.
Reserva de Memoria con mmap:
Cuando el administrador del heap crea un subheap, reserva un gran bloque de memoria a través de mmap. Esta reserva no asigna memoria de inmediato; simplemente designa una región que otros procesos del sistema o asignaciones no deberían usar.
Por defecto, el tamaño reservado para un subheap es de 1 MB para procesos de 32 bits y 64 MB para procesos de 64 bits.
Expansión Gradual con mprotect:
La región de memoria reservada se marca inicialmente como PROT_NONE, indicando que el kernel no necesita asignar memoria física a este espacio aún.
Para "hacer crecer" el subheap, el administrador del heap utiliza mprotect para cambiar los permisos de página de PROT_NONE a PROT_READ | PROT_WRITE, lo que lleva al kernel a asignar memoria física a las direcciones previamente reservadas. Este enfoque paso a paso permite que el subheap se expanda según sea necesario.
Una vez que se agota todo el subheap, el administrador del heap crea un nuevo subheap para continuar la asignación.
heap_info
Esta estructura asigna información relevante del heap. Además, la memoria del heap puede no ser continua después de más asignaciones, esta estructura también almacenará esa información.
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/arena.c#L837typedefstruct _heap_info{mstate ar_ptr; /* Arena for this heap. */struct _heap_info *prev; /* Previous heap. */size_t size; /* Current size in bytes. */size_t mprotect_size; /* Size in bytes that has been mprotectedPROT_READ|PROT_WRITE. */size_t pagesize; /* Page size used when allocating the arena. *//* Make sure the following data is properly aligned, particularlythat sizeof (heap_info) + 2 * SIZE_SZ is a multiple ofMALLOC_ALIGNMENT. */char pad[-3* SIZE_SZ & MALLOC_ALIGN_MASK];} heap_info;
malloc_state
Cada heap (arena principal u otras arenas de hilos) tiene una estructura malloc_state.
Es importante notar que la estructura malloc_state de la arena principal es una variable global en la libc (por lo tanto, ubicada en el espacio de memoria de la libc).
En el caso de las estructuras malloc_state de los heaps de hilos, están ubicadas dentro del "heap" propio del hilo.
Hay algunas cosas interesantes a notar de esta estructura (ver el código C a continuación):
__libc_lock_define (, mutex); Está ahí para asegurar que esta estructura del heap sea accedida por 1 hilo a la vez
* El `mchunkptr bins[NBINS * 2 - 2];` contiene **punteros** a los **primeros y últimos chunks** de los **bins** pequeños, grandes y no ordenados (el -2 es porque el índice 0 no se usa)
* Por lo tanto, el **primer chunk** de estos bins tendrá un **puntero hacia atrás a esta estructura** y el **último chunk** de estos bins tendrá un **puntero hacia adelante** a esta estructura. Lo que básicamente significa que si puedes l**eak estas direcciones en la arena principal** tendrás un puntero a la estructura en la **libc**.
* Las estructuras `struct malloc_state *next;` y `struct malloc_state *next_free;` son listas enlazadas de arenas
* El chunk `top` es el último "chunk", que es básicamente **todo el espacio restante del heap**. Una vez que el chunk superior está "vacío", el heap está completamente utilizado y necesita solicitar más espacio.
* El chunk de `último recordatorio` proviene de casos donde un chunk de tamaño exacto no está disponible y, por lo tanto, un chunk más grande se divide, un puntero de la parte restante se coloca aquí.
```c
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1812
struct malloc_state
{
/* Serialize access. */
__libc_lock_define (, mutex);
/* Flags (formerly in max_fast). */
int flags;
/* Set if the fastbin chunks contain recently inserted free blocks. */
/* Note this is a bool but not all targets support atomics on booleans. */
int have_fastchunks;
/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;
/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];
/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];
/* Linked list */
struct malloc_state *next;
/* Linked list for free arenas. Access to this field is serialized
by free_list_lock in arena.c. */
struct malloc_state *next_free;
/* Number of threads attached to this arena. 0 if the arena is on
the free list. Access to this field is serialized by
free_list_lock in arena.c. */
INTERNAL_SIZE_T attached_threads;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};
malloc_chunk
Esta estructura representa un fragmento particular de memoria. Los diversos campos tienen diferentes significados para fragmentos asignados y no asignados.
// https://github.com/bminor/glibc/blob/master/malloc/malloc.cstruct malloc_chunk {INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk, if it is free. */INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */struct malloc_chunk* fd; /* double links -- used only if this chunk is free. */struct malloc_chunk* bk;/* Only used for large blocks: pointer to next larger size. */struct malloc_chunk* fd_nextsize; /* double links -- used only if this chunk is free. */struct malloc_chunk* bk_nextsize;};typedefstruct malloc_chunk* mchunkptr;
Como se comentó anteriormente, estos bloques también tienen algunos metadatos, muy bien representados en esta imagen:
Los metadatos suelen ser 0x08B, indicando el tamaño actual del bloque utilizando los últimos 3 bits para indicar:
A: Si es 1 proviene de un subheap, si es 0 está en la arena principal
M: Si es 1, este bloque es parte de un espacio asignado con mmap y no parte de un heap
P: Si es 1, el bloque anterior está en uso
Luego, el espacio para los datos del usuario, y finalmente 0x08B para indicar el tamaño del bloque anterior cuando el bloque está disponible (o para almacenar datos del usuario cuando está asignado).
Además, cuando está disponible, los datos del usuario también se utilizan para contener algunos datos:
fd: Puntero al siguiente bloque
bk: Puntero al bloque anterior
fd_nextsize: Puntero al primer bloque en la lista que es más pequeño que él mismo
bk_nextsize: Puntero al primer bloque en la lista que es más grande que él mismo
Nota cómo enlazar la lista de esta manera evita la necesidad de tener un array donde se registre cada bloque individualmente.
Punteros de Bloque
Cuando se usa malloc, se devuelve un puntero al contenido que se puede escribir (justo después de los encabezados), sin embargo, al gestionar bloques, se necesita un puntero al comienzo de los encabezados (metadatos).
Para estas conversiones se utilizan estas funciones:
// https://github.com/bminor/glibc/blob/master/malloc/malloc.c/* Convert a chunk address to a user mem pointer without correcting the tag. */#definechunk2mem(p) ((void*)((char*)(p) + CHUNK_HDR_SZ))/* Convert a user mem pointer to a chunk address and extract the right tag. */#definemem2chunk(mem) ((mchunkptr)tag_at (((char*)(mem) - CHUNK_HDR_SZ)))/* The smallest possible chunk */#defineMIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))/* The smallest size we can malloc is an aligned minimal chunk */#defineMINSIZE \(unsignedlong)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) &~MALLOC_ALIGN_MASK))
Alineación y tamaño mínimo
El puntero al chunk y 0x0f deben ser 0.
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/sysdeps/generic/malloc-size.h#L61#defineMALLOC_ALIGN_MASK (MALLOC_ALIGNMENT -1)// https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/sysdeps/i386/malloc-alignment.h#defineMALLOC_ALIGNMENT16// https://github.com/bminor/glibc/blob/master/malloc/malloc.c/* Check if m has acceptable alignment */#definealigned_OK(m) (((unsignedlong)(m) & MALLOC_ALIGN_MASK) ==0)#definemisaligned_chunk(p) \((uintptr_t)(MALLOC_ALIGNMENT == CHUNK_HDR_SZ ? (p) :chunk2mem (p)) \& MALLOC_ALIGN_MASK)/* pad request bytes into a usable size -- internal version *//* Note: This must be a macro that evaluates to a compile time constantif passed a literal constant. */#definerequest2size(req) \(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \MINSIZE : \((req) + SIZE_SZ + MALLOC_ALIGN_MASK) &~MALLOC_ALIGN_MASK)/* Check if REQ overflows when padded and aligned and if the resultingvalue is less than PTRDIFF_T. Returns the requested size orMINSIZE in case the value is less than MINSIZE, or 0 if any of theprevious checks fail. */staticinlinesize_tchecked_request2size (size_t req) __nonnull (1){if (__glibc_unlikely (req > PTRDIFF_MAX))return0;/* When using tagged memory, we cannot share the end of the userblock with the header for the next chunk, so ensure that weallocate blocks that are rounded up to the granule size. Takecare not to overflow from close to MAX_SIZE_T to a smallnumber. Ideally, this would be part of request2size(), but thatmust be a macro that produces a compile time constant if passeda constant literal. */if (__glibc_unlikely (mtag_enabled)){/* Ensure this is not evaluated if !mtag_enabled, see gcc PR 99551. */asm ("");req = (req + (__MTAG_GRANULE_SIZE -1)) &~(size_t)(__MTAG_GRANULE_SIZE -1);}returnrequest2size (req);}
Nota que para calcular el espacio total necesario, solo se añade SIZE_SZ 1 vez porque el campo prev_size puede ser utilizado para almacenar datos, por lo tanto, solo se necesita el encabezado inicial.
Obtener datos del Chunk y alterar metadatos
Estas funciones funcionan recibiendo un puntero a un chunk y son útiles para verificar/establecer metadatos:
Verificar las banderas del chunk
// From https://github.com/bminor/glibc/blob/master/malloc/malloc.c/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */#definePREV_INUSE0x1/* extract inuse bit of previous chunk */#defineprev_inuse(p) ((p)->mchunk_size & PREV_INUSE)/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */#defineIS_MMAPPED0x2/* check for mmap()'ed chunk */#definechunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtainedfrom a non-main arena. This is only set immediately before handingthe chunk to the user, if necessary. */#defineNON_MAIN_ARENA0x4/* Check for chunk from main arena. */#definechunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) ==0)/* Mark a chunk as not being on the main arena. */#defineset_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)
Tamaños y punteros a otros trozos
/*Bits to mask off when extracting sizeNote: IS_MMAPPED is intentionally not masked off from size field inmacros for which mmapped chunks should never be seen. This shouldcause helpful core dumps to occur if it is tried by accident bypeople extending or adapting this malloc.*/#defineSIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)/* Get size, ignoring use bits */#definechunksize(p) (chunksize_nomask (p) &~(SIZE_BITS))/* Like chunksize, but do not mask SIZE_BITS. */#definechunksize_nomask(p) ((p)->mchunk_size)/* Ptr to next physical malloc_chunk. */#definenext_chunk(p) ((mchunkptr) (((char*) (p)) +chunksize (p)))/* Size of the chunk below P. Only valid if !prev_inuse (P). */#defineprev_size(p) ((p)->mchunk_prev_size)/* Set the size of the chunk below P. Only valid if !prev_inuse (P). */#defineset_prev_size(p, sz) ((p)->mchunk_prev_size = (sz))/* Ptr to previous physical malloc_chunk. Only valid if !prev_inuse (P). */#defineprev_chunk(p) ((mchunkptr) (((char*) (p)) -prev_size (p)))/* Treat space at ptr + offset as a chunk */#definechunk_at_offset(p, s) ((mchunkptr) (((char*) (p)) + (s)))
Establecer encabezado y pie de página (cuando se utilizan números de fragmento)
/* Set size at head, without disturbing its use bit */#defineset_head_size(p, s) ((p)->mchunk_size = (((p)->mchunk_size & SIZE_BITS) | (s)))/* Set size/use field */#defineset_head(p, s) ((p)->mchunk_size = (s))/* Set size at footer (only when chunk is not in use) */#defineset_foot(p, s) (((mchunkptr) ((char*) (p) + (s)))->mchunk_prev_size = (s))
Obtén el tamaño de los datos utilizables reales dentro del chunk
#pragmaGCCpoisonmchunk_size#pragmaGCCpoisonmchunk_prev_size/* This is the size of the real usable data in the chunk. Not valid fordumped heap chunks. */#definememsize(p) \(__MTAG_GRANULE_SIZE > SIZE_SZ &&__glibc_unlikely (mtag_enabled) ? \chunksize (p) - CHUNK_HDR_SZ : \chunksize (p) - CHUNK_HDR_SZ + (chunk_is_mmapped (p) ?0: SIZE_SZ))/* If memory tagging is enabled the layout changes to accommodate the granulesize, this is wasteful for small allocations so not done by default.Both the chunk header and user data has to be granule aligned. */_Static_assert (__MTAG_GRANULE_SIZE <= CHUNK_HDR_SZ,"memory tagging is not supported with large granule.");static __always_inline void*tag_new_usable (void*ptr){if (__glibc_unlikely (mtag_enabled)&& ptr){mchunkptr cp =mem2chunk(ptr);ptr =__libc_mtag_tag_region (__libc_mtag_new_tag (ptr), memsize (cp));}return ptr;}
Establezca un punto de interrupción al final de la función principal y descubramos dónde se almacenó la información:
Es posible ver que la cadena panda se almacenó en 0xaaaaaaac12a0 (que fue la dirección dada como respuesta por malloc dentro de x0). Al verificar 0x10 bytes antes, es posible ver que el 0x0 representa que el chunk anterior no está utilizado (longitud 0) y que la longitud de este chunk es 0x21.
Los espacios adicionales reservados (0x21-0x10=0x11) provienen de los encabezados añadidos (0x10) y 0x1 no significa que se reservó 0x21B, sino que los últimos 3 bits de la longitud del encabezado actual tienen algunos significados especiales. Como la longitud siempre está alineada a 16 bytes (en máquinas de 64 bits), estos bits en realidad nunca se utilizarán por el número de longitud.
0x1: Previous in Use - Specifies that the chunk before it in memory is in use
0x2: Is MMAPPED - Specifies that the chunk was obtained with mmap()
0x4: Non Main Arena - Specifies that the chunk was obtained from outside of the main arena
Ejemplo de Multihilo
Multihilo
```c #include #include #include #include #include
void* threadFuncMalloc(void* arg) { printf("Hello from thread 1\n"); char* addr = (char*) malloc(1000); printf("After malloc and before free in thread 1\n"); free(addr); printf("After free in thread 1\n"); }
void* threadFuncNoMalloc(void* arg) { printf("Hello from thread 2\n"); }
int main() { pthread_t t1; void* s; int ret; char* addr;