Heap

O que é a memória heap

A heap é uma estrutura especial usada pelos processos. O seu "brilho" é o fato dela ter tamanho variável, permitindo que o processo requisite ou libere dinamicamente a sua memória, diferentemente da stack. Em baixo nível, isso é feito usando syscalls do SO, que são as mesmas responsáveis por alocar páginas para as seções se necessário.

Nota: A heap é global, ou seja, ela não depende dos escopos de funções da mesma forma que a stack.

O espaço de memória que os processos normalmente usam para a heap é o segmento de dados, e no Linux a syscall brk é a responsável por aumentar ou diminuir esse espaço, mas normalmente nós não usamos as chamadas de sistema, e sim funções pré definidas que facilitam a nossa vida. Em C a principal função utilizada para alocar memória é a malloc(size_t n) e para liberar é a free(void *p), mas saiba que essas funções não manipulam a heap diretamente, pois quem realmente vai gerenciar é a libc.

A função malloc(size_t n), de acordo com o glibc, divide o segmento de dados em arenas (uma ou mais regiões de memória). A arena principal corresponde à heap original do processo, mas outras arenas podem ser alocadas. Normalmente cada thread possui uma arena própria (até atingir um certo limite, aí elas começam a dividir arenas), e dentro de cada arena há regiões de memória também denominados de heap, e é essa heap que a função malloc(size_t n) aloca memória para um usuário da libc. Os espaços de memória alocados pela função são conhecidos como chunks.

Importante: É responsabilidade do programador liberar as memórias alocadas manualmente. Mas tenha em mente que algumas linguagens contém algo conhecido como garbage collector, que monitora o processo identificando se existe algum espaço de memória alocado que não esteja mais desempenhando nenhuma função.

Destrinchando a malloc

Como visto anteriormente a malloc recebe um argumento size_t, e isso é a primeira coisa a se ficar esperto, pois size_t é não sinalizado, logo se você passar um valor negativo, você alocará um tamanho muito grande.

Sobre o funcionamente em si da malloc, ela chama duas syscalls (uma ou outra, a imagem representa isso), elas são a brk e mmap.

A brk obtém memória (não inicializada com 0) do kernel aumentando o program break. Inicialmente o start_brk e o program break (ou end of heap segment ou brk) apontam para o mesmo local. Curiosamente, se o ASLR estiver desabilitado o valor do start_brk e brk apontam para o final do segmento de dados bss, mas caso esteja ativado os dois valores passarão a ser o final do segmento de dados mais o offset aleatório do brk.

O seguinte código mostra o funcionamento da brk com o ASLR ativado.

brk.c

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>

int main()
{
        void *curr_brk, *tmp_brk = NULL;

        printf("Seja bem vindo ao exemplo de sbrk, seu PID:%d\n", getpid());

        /* sbrk(0) nos informa a localização atual do program break*/
        tmp_brk = curr_brk = sbrk(0);
        printf("Primeira localização do program break:%p\n", curr_brk);
        getchar();

        /* brk(addr) aumenta/decrementa a localização do program break*/
        brk(curr_brk+4096);

        curr_brk = sbrk(0);
        printf("Segunda localização do program break:%p\n", curr_brk);
        getchar();

        brk(tmp_brk);

        curr_brk = sbrk(0);
        printf("Terceira localização do program break:%p\n", curr_brk);
        getchar();

        return 0;
}

A saída será mostrada a seguir, mas entre um getchar() e outro será mostrado o valor de como está a memória do processo.

Seja bem vindo ao exemplo de sbrk, seu PID:10959
Primeira localização do program break:0x5648d279d000

---
cat /proc/10959/maps
5648d277c000-5648d279d000 rw-p 00000000 00:00 0                          [heap]
---

Segunda localização do program break:0x5648d279e000

---
cat /proc/10959/maps
5648d277c000-5648d279e000 rw-p 00000000 00:00 0                          [heap]
---

Terceira localização do program break:0x5648d279d000

---
cat /proc/10959/maps
5648d277c000-5648d279d000 rw-p 00000000 00:00 0 
---

Os resultados do cat representam respectivamente isso:

range do endereço virtual para esse segmento
flags
offset do arquivo (como não é mapeado de nenhum outro arquivo é 0)
maior/menor número de dispositivo (como não é mapeado de nenhum outro arquivo é 0)
inode number (como não é mapeado de nenhum outro arquivo é 0)
[HEAP] é o segmento

Agora o mmap é utilizado pela malloc para criar "private anonymous mapping segment". O propósito principal do "private anonymous mapping" é criar segmentos de memórias preenchidos com 0, que serão usados exclusivamente para chamadas de processos ("calling process"). É importante reparar que diferente da brk, a mmap aloca espaços não contíguos para o programa.

Da mesma forma como foi com o brk, iremos apresentar o código e a saída com o ASLR ativado.

mmap.c

#include <stdio.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdlib.h>

void static inline errExit(const char* msg)
{
        printf("%s falhou. Encerrando o processo.\n", msg);
        exit(-1);
}

int main()
{
        int ret = -1;
        char* addr = NULL;

        printf("Seja bem vindo ao exemplo do 'private anonymous mapping', seu PID::PID:%d\n", getpid());
        printf("Antes do mmap\n");
        getchar();

        addr = mmap(NULL, (size_t)132*1024, PROT_READ|PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
        if (addr == MAP_FAILED){
            errExit("mmap");
        }
        printf("Depois do mmap\n");
        getchar();

        /* Unmap mapped region. */
        ret = munmap(addr, (size_t)132*1024);
        if(ret == -1){
            errExit("munmap");
        }
        printf("Depois do munmap\n");
        getchar();
        return 0;
}

Seja bem vindo ao exemplo do 'private anonymous mapping', seu PID::PID:17861
Antes do mmap

---
cat /proc/17861/maps
55f3a78a9000-55f3a78ca000 rw-p 00000000 00:00 0                          [heap]
7f298f34f000-7f298f352000 rw-p 00000000 00:00 0
---

Depois do mmap

---
cat /proc/17861/maps
55f3a78a9000-55f3a78ca000 rw-p 00000000 00:00 0                          [heap]
7f298f32e000-7f298f352000 rw-p 00000000 00:00 0 
---

Depois do munmap

---
cat /proc/17861/maps
55f3a78a9000-55f3a78ca000 rw-p 00000000 00:00 0                          [heap]
7f298f34f000-7f298f352000 rw-p 00000000 00:00 0 
---

Note que os 132K criados (7f298f34f000 - 7f298f32e000 = 21000) foram unidos a um segmento já existente (que é esse endereço no range final).

Importante: Tente fazer o mesmo na sua máquina, se preferir desative o ASLR para facilitar a visualização dos segmentos.

Arena

A arena nada mais é do que uma região contígua de memória heap, e caso ela fique cheia, é possível expandir seu espaço incrementando o program break (após aumentar o tamanho, o campo size do top chunk é aumentado para conter o tamanho extra). É importante ressaltar que a main_arena ou arena principal é aquela criada para a thread principal (da função main em C).

No geral é inviável fazer com que toda thread tenha sua própria arena, por isso o número máximo de arena depende da arquitetura e do número de cores. Para arquiteturas de 32 bits o número máximo de arenas é 2 * número de cores, enquanto para 64 bits o número máximo é 8 * número de cores. Para exemplificar, imagine o seguinte cenário: temos uma arquitetura de 32 bits com 1 core rodando um processo com 4 threads (main + 3), nesse caso 4 > 2, então uma das threads terá que dividir uma arena (main aparentemente não conta para o número de arenas).

Quando a main chama a malloc pela primeira vez já cria uma arena principal.
Quando as threads 1 e 2 chamam a malloc pela primeira vez, as duas recebem uma arena própria.
Quando a thread 3 chama a malloc pela primeira vez, o número de máximo de arenas já bateu, então ele tenta reutilizar uma arena. Para isso é verificado as arenas existentes e se é possível se juntar a elas.

Além de existir mais de uma arena, também existe múltiplas heaps, mas neste caso são dentro das arenas, exceto da arena principal que é aquela que tem seu tamanho aumentado contiguamente pela brk. Para gerenciar isso existe 3 estruturas principais:

heap_info ou heap header: as arenas contém uma única heap, mas quando essa heap fica cheia, uma nova heap é criada não contiguamente pelo mmap, e por isso cada heap vai ter um heap_info só para ela.

heap_info.c

typedef struct _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 mprotected
                           PROT_READ|PROT_WRITE.  */
  /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

malloc_state ou arena header: existe apenas uma por arena, e ela contém informação sobre bins, top chunks, e mais.

malloc_state.c

struct malloc_state
{
  /* Serialize access.  */
  mutex_t 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.  */
  struct malloc_state *next_free;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

malloc_chunk ou chunk header: cada chunk contém seu próprio header.

malloc_chunk

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if 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 free. */
  struct malloc_chunk* bk_nextsize;
};

Nota: Ressaltando alguns pontos, o primeiro é que a arena principal aumenta de forma contígua (aumento do program break) e por isso não possui heap_info, e o segundo é que a malloc_state da arena principal não está localizada nela, e sim no segmento de dados da libc pois ela é uma variável global neste caso.

Abaixo há duas figuras, uma mostra uma comparação entre a heap da arena principal e as outras arenas, e a outra mostra uma arena com múltiplas heaps.

Chunks

Os chunks são os espaços alocados dentro da heap, e eles podem ser de 4 tipos: alocados, liberados, topo, last remainder.

Alocados

Um chunk alocado contém os seguintes campos:

prev_size: este é o primeiro campo do chunk, e ele armazena o tamanho do chunk anterior se ele estiver livre, e caso ele não esteja livre, armazena os dados do chunk anterior.
size: este campo armazena o tamanho do chunk atual, e seus últimos 3 bits são usados para identificar 3 flags.
NON_MAIN_ARENA(N ou A): este bit é setado para 1 caso o chunk não esteja na arena principal.
IS_MMAPPED(M): este bit é setado caso o chunk seja alocado por meio da mmap, ou seja, ele não está em uma heap contínua.
PREV_INUSE(P): este bit é setado caso o chunk anterior esteja alocado.
USER DATA: este campo contém os dados do usuário, é importante notar que a função malloc retorna um ponteiro para o início deste campo.

Importante: Quando requisitamos um tamanho para as funções que alocam um chunk, esse tamanho passa por uma conversão para garantir alinhamento, espaço para os metadados dos chunks, e para os últimos 3 bits do size serem 0 (para as flags).

O alinhamento para o espaço de um chunk, pela malloc, é feito usando double word (4 bytes) ou word, dessa forma se um tamanho desalinhado for passado como parâmetro, a malloc irá aumentar o tamanho para garantir alinhamento. Por exemplo, se o alinhamento está sendo feito em 8 bytes, e o tamanho passado for 9, a malloc irá alocar 16 bytes.

Além do alinhamento no tamanho, há um alinhamento no endereço de memória retornado pela malloc, este alinhamento é feito com base em uma word (2 bytes). Este alinhamento é feito para evitar exceções e garantir melhor performance.

Liberados

Um chunk liberado contém os seguintes campos:

prev_size: neste caso, este campo sempre será os dados do usuário de um chunk alocado, pois não existe dois chunks liberados em sequência (eles são unidos em um único chunk caso aconteça).
size: este campo armazena o tamanho do chunk liberado (os últimos 3 bits ainda são as flags).
Forward Pointer(fd): este campo é um ponteiro para o próximo chunk na mesma bin, e não o próximo chunk na memória.
Backward Pointer(bk): este campo é um ponteiro para o chunk anterior na mesma bin, e não o anterior na memória.

Exemplo

O seguinte código está sendo usado para verificar as flags e tamanho dos chunks, note que o valor no parâmetro da malloc é alterado para os testes.

flags.c

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

int main(){
    size_t *chunk;
    size_t flags, size;

    chunk = (size_t *)malloc(8);

    flags = chunk[-1]&(0b111); //Deixando apenas os bits das flags setados.
    size = chunk[-1]&(~0b111); //Zerando apenas os bits das flags.

    printf("\nTamanho do chunk: %zu\nFlags: %zu", size, flags);

    free(chunk);
}

Saída para valor 8: Tamanho do chunk: 32 Flags: 1 (apenas flag P setada)

Saída para valor 20: Tamanho do chunk: 32 Flags: 1

Saída para valor 35: Tamanho do chunk: 48 Flags: 1

Saída para valor 56: Tamanho do chunk: 64 Flags: 1

Nota: O tamanho do chunk sempre é um múltiplo de 16 ou 32.

Exemplo Thread

O código a seguir verifica as flags e o tamanho em um chunk de um thread.

thread.c

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

void *thread_function(){
    size_t *chunk;
    size_t flags, size;

    chunk = (size_t *)malloc(49);

    flags = chunk[-1]&(0b111);
    size = chunk[-1]&(~0b111);

    printf("\nTamanho do chunk: %zu\nFlags: %zu", size, flags);

    free(chunk);
}

int main(){
    pthread_t thread;

    pthread_create(&thread, NULL, thread_function, NULL);
    pthread_join(thread, NULL);

    getchar();
}

Saída: Tamanho do chunk: 64 Flags: 5

💡 Nota: O valor 5 equivale a 0b101, logo nós temos a flag A (NON_MAIN_ARENA) setada e P setada.

Topo

O chunk do topo não pertence a nenhuma bin, e ele serve para atender requisições do usuário quando não há nenhum chunk em nenhuma bin. Quando o tamanho do chunk do topo é maior do que o tamanho que o usuário pediu, ele é dividido em 2: o do usuário, e o remainder. Quando o tamanho do chunk do topo é menor, o tamanho é extendido usando as syscalls.

Last remainder

É o mais recente chunk resultante de uma divisão de um chunk maior.

Bins

Bins são estruturas de dados do tipo vetor, ou seja, nada mais são do que um vetor de chunks liberados. Note que cada chunk liberado contém os campos fd e bk, isso faz com que eles também sejam um estrutura de dados do tipo lista, podendo ser duplamente ou simplesmente encadeada.

Existe três bins principais, a Tcachebin, a fastbinsY que contém as fast bins, e a bins que contém o unsorted, os small, e os large bins (note que a bins é um único vetor, sendo que o index 0 não é usado, o 1 é para o unsorted, 2-64 é para o small, e 65-127 é para o large). Suas definições são as seguintes:

bins.c

typedef struct malloc_chunk *mfastbinptr;
mfastbinptr fastbinsY[]; // Array of pointers to chunks

typedef struct malloc_chunk* mchunkptr;
mchunkptr bins[]; // Array of pointers to chunks

Tcache bin

Cada thread, até mesmo a principal, contém seu próprio Tcachebin, que é uma bin parecida com a fast bin. Inicialmente todo chunk liberado (se estiver dentro do limite de tamanho) vem parar nessa bin.

Número de bins: 64, sendo que vai de 24 até 1032 bytes em 64 bits, em 32 é de 12 até 516B. -> Lista simplesmente encadeada, com comportamento LIFO.
Quantidade de chunks: máximo de 7 chunks do mesmo tamanho em cada bin.
Não há coalisão.

É interessante notar que normalmente o primeiro chunk da Tcache contém um ponteiro para o HEAD de cada bin e a quantidade de quantos chunks há por bin.

Fast bin

Chunks de tamanho entre 16 e 80 são considerados fast chunks, e as bins que contém os fast chunks são as fast bins. As fast bins são mais rápidas em quesitos de alocação e desalocação. Segue algumas das propriedades delas:

Número de bins: 10. -> Cada bin contém uma lista simplesmente encadeada de chunks liberados. Ela é simplesmente encadeada pois tem funcionamento parecido com uma pilha (LIFO).
Tamanho do chunk: 8 em 8. -> Cada elemento do vetor contém uma lista de chunks liberados de mesmo tamanho, dessa forma o index 0 contém os chunks de tamanho 16, e o index 9 os chunks de tamanho 80.
Durante a inicialização da malloc o tamanho do maior chunk é setado para 64.
Não há coalisão, ou seja, chunks não são unidos, podendo gerar fragmentação, mas é mais rápido.

Note que as fast bins contém apenas a cabeça (HEAD) de suas bins. Todas as outras bins contém a cabeça (HEAD) e a cauda (TAIL).

Unsorted bin

Small chunks e large chunks são, inicialmente, adicionados ao unsorted bin quando eles são liberados, uma vez que o unsorted permite a libc reutilizar os chunks liberados recentemente. Algumas das propriedades são:

Número de bins: 1 (2 porque o index par é a HEAD e o ímpar a TAIL). -> Por ter HEAD e TAIL, a lista é duplamente encadeada. Os chunks são adicionados pela HEAD e removidos pela TAIL.
Tamanho do chunk: não tem.

Note que os chunks no unsorted podem ser divididos em chunks menores para atender um requisição de usuário. Dessa forma, se o chunk no unsorted tem tamanho 300, e o usuário pede um chunk de 250, o chunk será dividido em 2.

Small bin

Chunks com tamanho menor do que 512 bytes são conhecidos como small chunks, e as bins que armazenam eles são as small bins. Segue as caracteristicas deles:

Número de bins: 62 (124 pela lógica do HEAD e TAIL). -> Os chunks são adicionados pela HEAD e removidos pela TAIL.
Tamanho do chunk: 8 em 8. -> Começa a partir de 16 bytes, e segue em diante.
Há coalisão, então dois chunks liberados adjacentes são unidos para evitar fragmentação.

Large bin

Chunks com tamanho maior ou igual a 512 bytes são conhecidos como large chunks, e as bins que armazenam são as large bins. Segue as caracteristicas:

Número de bins: 63 (126). -> Os chunks podem ser adicionados ou removidos de qualquer posição da lista. Dessas 63 bins, 32 são de 64 em 64 (começando em 512), 16 são de 512 em 512, 8 são de 4096 em 4096, 4 são de 32768 em 32768, 2 são de 262144 em 262144, e 1 é o restante.
Chunks no mesmo index não são do mesmo tamanho, eles são armazenados em ordem decrescente.
Há coalisão.

Sobre a bin no geral

Lembrando que a bin é o vetor que armazena os unsorted, small e large. O que diferencia esses 3, além dos tamanhos dos chunks, são a posição deles no vetor.

Comandos para PwnDbg

heap: mostra a heap.
vis_heap_chunks: mostra os chunks da heap.
heap bins: mostra uma visão sobre as bins.
info proc mappings: lista as diferentes regiões de memória.
vmmap: lista todas as regiões de memória, incluindo os segmentos.

Referencias

AnteriorRet2gets PróximoDouble-Free

Atualizado há 2 meses