Heap

Conceitos Básicos do Heap

O heap é basicamente o local onde um programa pode armazenar dados quando solicita dados chamando funções como malloc, calloc... Além disso, quando essa memória não é mais necessária, ela é liberada chamando a função free.

Como mostrado, o heap está logo após onde o binário está sendo carregado na memória (verifique a seção [heap]):

Alocação Básica de Chunks

Quando alguns dados são solicitados para serem armazenados no heap, um espaço do heap é alocado para eles. Este espaço pertencerá a um bin e apenas os dados solicitados + o espaço dos cabeçalhos do bin + o deslocamento mínimo do tamanho do bin serão reservados para o chunk. O objetivo é reservar a menor quantidade de memória possível sem tornar complicado encontrar onde cada chunk está. Para isso, as informações de metadados do chunk são usadas para saber onde cada chunk usado/livre está.

Existem diferentes maneiras de reservar o espaço, principalmente dependendo do bin usado, mas uma metodologia geral é a seguinte:

O programa começa solicitando uma certa quantidade de memória.
Se na lista de chunks houver alguém disponível grande o suficiente para atender à solicitação, ele será usado.
Isso pode até significar que parte do chunk disponível será usada para essa solicitação e o restante será adicionado à lista de chunks.
Se não houver nenhum chunk disponível na lista, mas ainda houver espaço na memória alocada do heap, o gerenciador de heap cria um novo chunk.
Se não houver espaço suficiente no heap para alocar o novo chunk, o gerenciador de heap pede ao kernel para expandir a memória alocada para o heap e depois usa essa memória para gerar o novo chunk.
Se tudo falhar, o malloc retorna nulo.

Observe que se a memória solicitada ultrapassar um limite, o mmap será usado para mapear a memória solicitada.

Arenas

Em aplicações multithread, o gerenciador de heap deve evitar condições de corrida que possam levar a falhas. Inicialmente, isso era feito usando um mutex global para garantir que apenas uma thread pudesse acessar o heap de cada vez, mas isso causava problemas de desempenho devido ao gargalo induzido pelo mutex.

Para resolver isso, o alocador de heap ptmalloc2 introduziu "arenas", onde cada arena age como um heap separado com suas próprias estruturas de dados e mutex, permitindo que várias threads realizem operações de heap sem interferir umas com as outras, desde que usem arenas diferentes.

A arena "principal" padrão lida com operações de heap para aplicativos de thread única. Quando novas threads são adicionadas, o gerenciador de heap as atribui a arenas secundárias para reduzir a contenção. Ele primeiro tenta anexar cada nova thread a uma arena não utilizada, criando novas se necessário, até um limite de 2 vezes os núcleos da CPU para sistemas de 32 bits e 8 vezes para sistemas de 64 bits. Uma vez que o limite é atingido, as threads devem compartilhar arenas, levando a uma possível contenção.

Ao contrário da arena principal, que se expande usando a chamada de sistema brk, as arenas secundárias criam "subheaps" usando mmap e mprotect para simular o comportamento do heap, permitindo flexibilidade na gestão de memória para operações multithread.

Subheaps

Os subheaps servem como reservas de memória para arenas secundárias em aplicações multithread, permitindo que cresçam e gerenciem suas próprias regiões de heap separadamente do heap principal. Veja como os subheaps diferem do heap inicial e como operam:

Heap Inicial vs. Subheaps:

O heap inicial está localizado diretamente após o binário do programa na memória, e se expande usando a chamada de sistema sbrk.
Os subheaps, usados pelas arenas secundárias, são criados por meio de mmap, uma chamada de sistema que mapeia uma região de memória especificada.

Reserva de Memória com mmap:

Quando o gerenciador de heap cria um subheap, ele reserva um grande bloco de memória por meio de mmap. Essa reserva não aloca memória imediatamente; simplesmente designa uma região que outros processos do sistema ou alocações não devem usar.
Por padrão, o tamanho reservado para um subheap é de 1 MB para processos de 32 bits e 64 MB para processos de 64 bits.

Expansão Gradual com mprotect:

A região de memória reservada é inicialmente marcada como PROT_NONE, indicando que o kernel não precisa alocar memória física para este espaço ainda.
Para "expandir" o subheap, o gerenciador de heap usa mprotect para alterar as permissões da página de PROT_NONE para PROT_READ | PROT_WRITE, fazendo com que o kernel aloque memória física para os endereços previamente reservados. Esse processo passo a passo permite que o subheap se expanda conforme necessário.
Uma vez que todo o subheap esteja esgotado, o gerenciador de heap cria um novo subheap para continuar a alocação.

malloc_state

Cada heap (arena principal ou arenas de outras threads) tem uma estrutura malloc_state. É importante notar que a estrutura malloc_state da arena principal é uma variável global na libc (portanto, localizada no espaço de memória da libc). No caso das estruturas malloc_state dos heaps de threads, elas estão localizadas dentro do "heap" da própria thread.

Há algumas coisas interessantes a observar nesta estrutura (veja o código C abaixo):

O mchunkptr bins[NBINS * 2 - 2]; contém ponteiros para o primeiro e último chunks dos bins pequenos, grandes e não ordenados (o -2 é porque o índice 0 não é usado).
Portanto, o primeiro chunk desses bins terá um ponteiro reverso para esta estrutura e o último chunk desses bins terá um ponteiro para frente para esta estrutura. O que basicamente significa que se você puder vazar esses endereços na arena principal, terá um ponteiro para a estrutura na libc.
As structs struct malloc_state *next; e struct malloc_state *next_free; são listas encadeadas de arenas.
O chunk top é o último "chunk", que é basicamente todo o espaço restante do heap. Uma vez que o chunk superior está "vazio", o heap está completamente usado e precisa solicitar mais espaço.
O chunk last reminder vem de casos em que um chunk de tamanho exato não está disponível e, portanto, um chunk maior é dividido, uma parte restante do ponteiro é colocada aqui.

// From https://heap-exploitation.dhavalkapil.com/diving_into_glibc_heap/malloc_state
struct malloc_state
{
/* Serialize access.  */
__libc_lock_define (, mutex);
/* Flags (formerly in max_fast).  */
int flags;

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

typedef struct malloc_state *mstate;

malloc_chunk

Esta estrutura representa um pedaço particular de memória. Os vários campos têm significados diferentes para pedaços alocados e não alocados.

// From https://heap-exploitation.dhavalkapil.com/diving_into_glibc_heap/malloc_chunk
struct 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;
};

typedef struct malloc_chunk* mchunkptr;

Como comentado anteriormente, esses pedaços também possuem metadados, muito bem representados nesta imagem:

Os metadados geralmente são 0x08B, indicando o tamanho atual do pedaço, usando os últimos 3 bits para indicar:

A: Se 1, vem de um subheap, se 0, está na arena principal
M: Se 1, este pedaço faz parte de um espaço alocado com mmap e não faz parte de um heap
P: Se 1, o pedaço anterior está em uso

Em seguida, o espaço para os dados do usuário e, finalmente, 0x08B para indicar o tamanho do pedaço anterior quando o pedaço está disponível (ou para armazenar os dados do usuário quando é alocado).

Além disso, quando disponível, os dados do usuário são usados para conter também algumas informações:

Ponteiro para o próximo pedaço
Ponteiro para o pedaço anterior
Tamanho do próximo pedaço na lista
Tamanho do pedaço anterior na lista

Observe como organizar a lista dessa maneira evita a necessidade de ter um array onde cada pedaço é registrado individualmente.

Exemplo Rápido de Heap

Exemplo rápido de heap de https://guyinatuxedo.github.io/25-heap/index.html mas em arm64:

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

void main(void)
{
char *ptr;
ptr = malloc(0x10);
strcpy(ptr, "panda");
}

Defina um ponto de interrupção no final da função principal e vamos descobrir onde as informações foram armazenadas:

É possível ver que a string panda foi armazenada em 0xaaaaaaac12a0 (que foi o endereço fornecido como resposta pelo malloc dentro de x0). Verificando 0x10 bytes antes, é possível ver que o 0x0 representa que o chunk anterior não está em uso (comprimento 0) e que o comprimento deste chunk é 0x21.

Os espaços extras reservados (0x21-0x10=0x11) vêm dos cabeçalhos adicionados (0x10) e 0x1 não significa que foi reservado 0x21B, mas os últimos 3 bits do comprimento do cabeçalho atual têm alguns significados especiais. Como o comprimento é sempre alinhado em múltiplos de 16 bytes (em máquinas de 64 bits), esses bits na verdade nunca serão usados pelo número de comprimento.

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

Bins e Alocações/Liberações de Memória

Verifique quais são os bins, como eles são organizados e como a memória é alocada e liberada em:

pageBins & Memory Allocations

Verificações de Segurança das Funções de Heap

As funções envolvidas no heap realizarão certas verificações antes de executar suas ações para tentar garantir que o heap não foi corrompido:

pageHeap Functions Security Checks

Referências

PreviousFormat Strings Template NextBins & Memory Allocations

Last updated 8 days ago