Heap Allocators

Um heap allocator gerencia requisições de memória de tamanho variável e momento arbitrário dentro de uma região do espaço de endereçamento já sustentada por memória real, expondo uma interface como malloc e free. Ele fica acima do gerenciamento de memória física e da paginação, em vez de substituir qualquer um dos dois: um alocador de páginas distribui memória em unidades fixas do tamanho de uma página, o que é muito mais grosseiro do que a maioria das alocações que um kernel ou programa realmente precisa, e um heap allocator existe especificamente para subdividir essa memória de granularidade grossa nos pedaços pequenos e de tamanhos variados que o código real solicita.

Propósito e escopo

Um alocador de páginas sozinho é insuficiente para uso de propósito geral porque a maioria das alocações é muito menor que uma página e chega em tamanhos e ordem imprevisíveis. Uma estrutura de dados do kernel pode precisar de 64 bytes; um programa em espaço de usuário pode solicitar uma string de tamanho arbitrário. Arredondar toda requisição desse tipo para uma página inteira desperdiçaria quantidades enormes de memória e não forneceria, por si só, nenhum mecanismo para reutilizar o espaço depois que uma alocação é liberada. Um heap allocator resolve isso solicitando memória do alocador de páginas em grandes blocos e então gerenciando o layout interno desses blocos por conta própria, rastreando quais partes estão em uso e quais estão livres, e atendendo requisições futuras a partir das partes livres antes de pedir mais ao alocador de páginas.

O alocador interno de um kernel opera sob restrições que um alocador em espaço de usuário não tem. Código rodando com interrupções desabilitadas, ou dentro de um próprio handler de interrupção, geralmente não pode bloquear esperando memória ficar disponível, o que descarta qualquer caminho de alocação que possa precisar esperar por um lock mantido por código que foi ele mesmo interrompido, ou que possa disparar uma operação de reclamação de páginas com duração potencialmente ilimitada. Kernels de produção costumam expressar essa distinção através de flags passadas em toda chamada interna de alocação, indicando, por exemplo, se quem chamou está em um contexto que permite dormir caso memória precise ser liberada em outro lugar primeiro, ou se exige uma resposta imediata independentemente de essa resposta ser uma alocação bem-sucedida ou uma falha total. Um heap allocator destinado apenas a um uso simples e de contexto único dentro do kernel geralmente pode ignorar essa distinção, mas ela se torna inevitável assim que handlers de interrupção e código de kernel preemptível compartilham o mesmo alocador.

Essa divisão de responsabilidade não é exclusiva de um kernel: implementações de malloc em espaço de usuário resolvem o mesmo problema, solicitando memória do kernel através de uma chamada de sistema (historicamente brk/sbrk, mais comumente mmap em sistemas modernos) e então gerenciando essa memória por conta própria, em vez de fazer uma chamada de sistema para cada alocação. O heap allocator interno de um kernel, usado para suas próprias estruturas de dados, e o alocador por trás do malloc de um programa em espaço de usuário são, conceitualmente, o mesmo tipo de software resolvendo o mesmo problema, diferindo principalmente no que pedem à camada abaixo deles.

O modelo de free list

O design de alocador mais comum mantém uma lista encadeada de blocos livres. Cada bloco, livre ou em uso, é precedido por um pequeno header registrando, no mínimo, seu tamanho, o que permite que free determine quanta memória recuperar tendo apenas o ponteiro originalmente retornado por malloc: o header fica logo antes desse ponteiro, em um offset negativo fixo, e nunca é exposto a quem chamou.

struct block_header {
    size_t size;       // tamanho da região utilizável, sem contar este header
    int    free;
    struct block_header *next; // próximo bloco na free list
};

const BlockHeader = struct {
    size: usize,          // tamanho da região utilizável, sem contar este header
    free: bool,
    next: ?*BlockHeader,  // próximo bloco na free list
};

#[repr(C)]
struct BlockHeader {
    size: usize,             // tamanho da região utilizável, sem contar este header
    free: bool,
    next: *mut BlockHeader,  // próximo bloco na free list
}

Alocação percorre a free list procurando um bloco grande o suficiente para satisfazer a requisição. Várias estratégias de busca trocam velocidade de alocação pela qualidade com que preservam grandes regiões livres contíguas: first-fit retorna o primeiro bloco encontrado que seja grande o suficiente, o que é rápido mas tende a deixar muitos fragmentos pequenos e inutilizáveis perto do início da lista com o tempo; best-fit varre a lista inteira e retorna o menor bloco que ainda satisfaça a requisição, minimizando o espaço desperdiçado por alocação ao custo de uma varredura completa; next-fit se comporta como first-fit mas retoma a busca de onde a busca anterior parou, em vez de recomeçar do início, distribuindo as alocações de forma mais uniforme pelo heap.

A lista descrita acima é uma free list explícita: os ponteiros ligando um bloco livre ao próximo são armazenados dentro dos próprios blocos, mas apenas dentro dos livres, já que um bloco alocado não tem necessidade alguma de aparecer na lista e seu conteúdo pertence inteiramente a quem chamou. Um design alternativo, mais simples, usa uma free list implícita, onde todo bloco, livre ou alocado, está ligado em ordem de endereço independentemente do status, e uma busca passa por blocos alocados lendo seu campo de tamanho e pulando adiante, em vez de seguir um ponteiro next explícito. Uma lista implícita exige menos contabilidade por bloco no caso livre, mas precisa inspecionar todo bloco, alocado ou não, durante uma busca, enquanto uma lista explícita pode pular blocos alocados por completo já que eles nunca foram ligados a ela, uma troca entre simplicidade e eficiência de busca que espelha a escolha entre um array e uma lista encadeada em outros contextos.

Split e coalescing

Um bloco livre maior que o tamanho requisitado não é necessariamente usado por inteiro: alocadores tipicamente fazem split, separando apenas a quantidade necessária e deixando o restante como um bloco livre menor de volta na lista, desde que o restante seja grande o suficiente para conter um header e ser útil por conta própria. Fazer split indefinidamente acabaria produzindo blocos pequenos demais para valer a pena rastrear separadamente, então implementações geralmente definem um tamanho mínimo de bloco abaixo do qual um restante é deixado maior que o necessário em vez de dividido.

A operação inversa, coalescing, mescla um bloco recém-liberado com quaisquer blocos livres fisicamente adjacentes de volta em um bloco maior, o que é o que impede o heap de se fragmentar em um número sempre crescente de regiões livres pequenas e individualmente inúteis ao longo da vida de um programa de longa duração. Fazer coalescing com o bloco seguinte é simples se blocos livres estão ligados em ordem de endereço: o header do bloco sendo liberado pode inspecionar seu vizinho imediato diretamente. Fazer coalescing com o bloco anterior exige saber o tamanho daquele bloco sem percorrer a lista inteira desde o início, o que uma boundary tag (também chamada de footer) fornece: uma cópia do campo de tamanho duplicada no final de todo bloco, livre ou alocado, permitindo que código imediatamente atrás de um determinado bloco encontre o header desse bloco diretamente, em tempo constante, independentemente do comprimento da lista.

Uma única free list buscada linearmente não escala bem quando o heap contém muitos blocos de tamanhos muito variados, já que satisfazer uma pequena requisição pode exigir passar por um grande número de blocos livres não relacionados antes de encontrar um adequado. Free lists segregadas resolvem isso mantendo várias free lists em vez de uma só, cada uma dedicada a uma faixa de tamanhos de bloco (uma lista para blocos abaixo de 32 bytes, outra para 32 a 64 bytes, e assim por diante) de modo que uma busca só examine blocos já conhecidos por estarem aproximadamente no tamanho certo. Fazer coalescing sob esse esquema exige adicionalmente mover um bloco recém-mesclado da lista de sua antiga classe de tamanho para qualquer lista que corresponda ao seu novo tamanho maior, mas a redução no tempo de busca por alocação é substancial o suficiente para que a maioria dos alocadores de propósito geral usados em produção, em vez de uma única free list plana, adote alguma forma de segregação por classe de tamanho.

Crescendo o heap

Quando nenhum bloco livre é grande o suficiente para satisfazer uma requisição, o alocador estende a região que gerencia solicitando memória adicional de o que quer que esteja abaixo dele: o alocador de páginas físicas e o código de paginação, dentro de um kernel, ou uma chamada de sistema como brk ou mmap em espaço de usuário. A memória recém-obtida é formatada como um único bloco livre grande, mesclada com qualquer bloco livre existente que por acaso estivesse no final da região anterior, e a alocação então prossegue como aconteceria contra qualquer outro bloco livre suficientemente grande. Como solicitar mais memória à camada abaixo é tipicamente muito mais caro do que satisfazer uma alocação a partir de um bloco livre existente, alocadores geralmente solicitam mais memória do que a alocação imediata estritamente exige, antecipando requisições futuras e amortizando o custo da requisição subjacente ao longo de muitas alocações subsequentes.

Encolher o heap de volta é consideravelmente mais raro na prática do que crescê-lo, e muitos alocadores nunca tentam isso, retendo todo byte já solicitado da camada abaixo pelo resto da vida do processo ou kernel. Onde é tentado, só é simples quando uma grande região livre está bem no final da área gerenciada: memória pode então ser liberada com brk (movendo o endereço de break para trás) ou munmap, espelhando exatamente como foi obtida, porque uma região livre em qualquer outro lugar no meio do heap não pode ser liberada de forma independente sem realocar alocações ainda vivas ao seu redor ou deixar um buraco que a camada subjacente não tem como recuperar.

Fragmentação

Fragmentação interna é memória desperdiçada dentro de um bloco alocado que é maior do que o realmente requisitado, resultado de requisitos de alinhamento, tamanhos mínimos de bloco, ou a decisão de um alocador de não dividir um bloco cujo restante seria pequeno demais para ser útil. Fragmentação externa é memória desperdiçada entre alocações: pode existir memória livre total suficiente para satisfazer uma requisição, mas nenhum bloco livre único é grande o suficiente porque a memória livre está espalhada em pedaços pequenos demais individualmente, mesmo depois que o coalescing mesclou o que pôde de regiões livres adjacentes. Fragmentação externa é o problema mais difícil na prática, já que depende de todo o histórico de ordem de alocação e desalocação em vez de qualquer alocação isolada, e diferentes designs de alocador fazem trocas diferentes para controlá-la: classes de alocação menores, coalescing mais agressivo e free lists ordenadas por endereço reduzem-na a algum custo em velocidade ou complexidade de código.

Fragmentação é comumente quantificada como uma taxa de utilização: a quantidade de pico de memória realmente requisitada por alocações vivas em qualquer momento, dividida pela quantidade total de memória que o alocador solicitou da camada abaixo dele para satisfazer essas requisições. Uma taxa próxima de um indica um alocador que desperdiça pouco espaço com overhead ou lacunas inutilizáveis; pesquisas e benchmarks de alocadores historicamente comparam implementações contra traces de alocação sintéticos e do mundo real especificamente para medir essa taxa sob padrões de uso realistas, em vez de adversariais ou de melhor caso, já que o comportamento de fragmentação de um alocador depende fortemente da mistura e ordem específicas de tamanhos que uma determinada carga de trabalho requisita.

Designs alternativos de alocador

O modelo de free list é de propósito geral mas não a única abordagem, e kernels frequentemente usam mais de um alocador internamente para propósitos diferentes.

Um buddy allocator gerencia memória em blocos de tamanho potência de dois. Uma requisição é arredondada para a potência de dois mais próxima, e um bloco desse tamanho é obtido dividindo recursivamente um bloco livre maior ao meio, em dois “buddies”, até resultar um bloco do tamanho requerido. Liberar um bloco verifica se seu buddy (encontrado através de um simples XOR de endereço com o tamanho do bloco) também está livre, e se estiver, mescla os dois no próximo bloco de potência de dois maior, repetindo a verificação em cada tamanho maior. Isso torna o coalescing extremamente rápido e a contabilidade simples, ao custo de fragmentação interna potencialmente significativa, já que uma requisição de 65 KB é arredondada para 128 KB. Buddy allocators são comuns como o alocador que gerencia os próprios frames de página física, um nível abaixo do heap allocator descrito no resto deste artigo.

Um slab allocator adota uma abordagem diferente, adequada a um padrão comum dentro de kernels: alocar e liberar repetidamente muitos objetos exatamente do mesmo tamanho e tipo fixo: process control blocks, inodes de sistema de arquivos, buffers de pacotes de rede. Em vez de uma free list geral, um slab allocator mantém pools separados (“caches”), cada um pré-formatado para conter objetos de um tamanho específico, com objetos livres em um cache rastreados por uma simples free list embutida, sem exigir header separado algum. Isso evita tanto o overhead de busca de um alocador de propósito geral quanto sua fragmentação interna por completo, já que todo objeto em um determinado cache é exatamente do tamanho que precisa ser, e é por isso que kernels de produção tipicamente colocam um slab allocator sobre seu alocador de páginas para suas próprias estruturas internas de tamanho fixo, reservando um heap allocator de propósito geral para alocações de tamanho variável ou voltadas ao espaço de usuário.

Alocadores de propósito geral de produção destinados a grandes programas multithreaded em espaço de usuário frequentemente combinam várias das ideias acima em um único design, em vez de escolher exclusivamente uma. Classes de tamanho estreitas o suficiente para limitar rigorosamente a fragmentação interna, caches por thread para evitar contenção, e estruturas de suporte com granularidade de página compartilhadas entre classes de tamanho são elementos estruturais comuns entre alocadores desenvolvidos independentemente e usados em software amplamente implantado, alcançados separadamente por implementações diferentes convergindo para soluções amplamente semelhantes para as mesmas restrições subjacentes, e não por um design ter sido copiado entre elas.

Concorrência

Um alocador compartilhado entre múltiplas CPUs precisa proteger sua free list, ou listas, contra modificação concorrente, e um único lock global em volta de toda alocação se torna um gargalo significativo à medida que o número de CPUs cresce, já que todo núcleo disputa o mesmo lock em toda chamada de malloc e free. Alocadores destinados a uso multiprocessado costumam dar a cada CPU (ou cada thread) seu próprio cache local pequeno de blocos livres, satisfazendo a maioria das alocações sem tomar lock compartilhado algum, e recorrendo a uma estrutura compartilhada e travada apenas quando um cache local está vazio ou precisa devolver memória excedente. Esse padrão aparece tanto em slab allocators internos de kernel quanto em alocadores de espaço de usuário projetados para programas multithreaded, pelo mesmo motivo subjacente: contenção em uma única estrutura de dados compartilhada escala mal, enquanto estado por CPU que é apenas ocasionalmente reconciliado com um pool compartilhado escala muito melhor.

Um risco de concorrência mais sutil, específico da reutilização de memória, é o false sharing: mesmo sem qualquer contenção de lock, se duas alocações não relacionadas feitas por threads diferentes acabam caindo na mesma linha de cache da CPU, porque um alocador as empacotou juntas sem considerar qual thread requisitou qual, escritas de uma thread em seus próprios dados, logicamente independentes, ainda vão forçar a linha de cache para fora do cache da outra thread, degradando o desempenho de uma forma que não tem nada a ver com qualquer dependência real de dados entre as duas threads. Alocadores cientes disso às vezes preenchem ou alinham alocações por thread a limites de linha de cache especificamente para evitar isso, trocando uma pequena quantidade de fragmentação interna adicional pela eliminação de um problema de desempenho que, de outra forma, seria difícil de diagnosticar.

Uma implementação mínima

Um alocador first-fit sobre uma única arena de tamanho fixo pode ser implementado de forma compacta. O header definido anteriormente é colocado imediatamente antes de todo bloco, e a free list é ligada simplesmente:

static struct block_header *free_list = NULL;

void heap_init(void *start, size_t size) {
    free_list = start;
    free_list->size = size - sizeof(struct block_header);
    free_list->free = 1;
    free_list->next = NULL;
}

void *heap_alloc(size_t size) {
    struct block_header *curr = free_list;
    while (curr) {
        if (curr->free && curr->size >= size) {
            if (curr->size >= size + sizeof(struct block_header) + MIN_BLOCK_SIZE) {
                struct block_header *remainder =
                    (void *)((char *)curr + sizeof(struct block_header) + size);
                remainder->size = curr->size - size - sizeof(struct block_header);
                remainder->free = 1;
                remainder->next = curr->next;
                curr->size = size;
                curr->next = remainder;
            }
            curr->free = 0;
            return (char *)curr + sizeof(struct block_header);
        }
        curr = curr->next;
    }
    return NULL; // sem memória; uma implementação real cresceria o heap aqui
}

void heap_free(void *ptr) {
    struct block_header *block =
        (struct block_header *)((char *)ptr - sizeof(struct block_header));
    block->free = 1;
    // uma implementação real faria coalescing com blocos livres adjacentes aqui
}

Um alocador de produção adiciona coalescing, crescimento do heap, e tipicamente preenchimento de alinhamento para que todo ponteiro retornado satisfaça o requisito de alinhamento de pior caso da plataforma (comumente 16 bytes em x86-64), nada disso mudando a estrutura fundamental de free-list-e-header mostrada acima.

A mesma lógica, expressa em Zig, é estruturalmente idêntica (um header com tag, uma free list ligada simplesmente, e o mesmo comportamento de split ao alocar), diferindo principalmente em como a linguagem expressa aritmética de ponteiros e valores opcionais explicitamente:

const BlockHeader = struct {
    size: usize,
    free: bool,
    next: ?*BlockHeader,
};

const min_block_size: usize = 16;
var free_list: ?*BlockHeader = null;

fn heapInit(start: [*]u8, size: usize) void {
    const block: *BlockHeader = @ptrCast(@alignCast(start));
    block.size = size - @sizeOf(BlockHeader);
    block.free = true;
    block.next = null;
    free_list = block;
}

fn heapAlloc(size: usize) ?[*]u8 {
    var curr = free_list;
    while (curr) |block| {
        if (block.free and block.size >= size) {
            if (block.size >= size + @sizeOf(BlockHeader) + min_block_size) {
                const remainder_addr = @intFromPtr(block) + @sizeOf(BlockHeader) + size;
                const remainder: *BlockHeader = @ptrFromInt(remainder_addr);
                remainder.size = block.size - size - @sizeOf(BlockHeader);
                remainder.free = true;
                remainder.next = block.next;
                block.size = size;
                block.next = remainder;
            }
            block.free = false;
            const data_addr = @intFromPtr(block) + @sizeOf(BlockHeader);
            return @ptrFromInt(data_addr);
        }
        curr = block.next;
    }
    return null;
}

fn heapFree(ptr: [*]u8) void {
    const block_addr = @intFromPtr(ptr) - @sizeOf(BlockHeader);
    const block: *BlockHeader = @ptrFromInt(block_addr);
    block.free = true;
}

O tipo de ponteiro opcional do Zig (?*BlockHeader) faz com que o caso de “fim da lista” (o equivalente do Zig a um next pointer nulo) seja verificado pelo compilador em todo ponto em que o valor é usado, em vez de depender de um programador lembrar de testá-lo, embora o algoritmo e o layout de memória subjacentes permaneçam inalterados em relação à versão em C.

Um kernel escrito em Rust geralmente implementa a mesma estrutura por trás da trait GlobalAlloc, ainda dependendo de ponteiros brutos e blocos unsafe internamente, já que manipular uma free list fundamentalmente exige o tipo de aritmética de ponteiros não verificada que o modelo de posse do Rust não permite de outra forma:

#[repr(C)]
struct BlockHeader {
    size: usize,
    free: bool,
    next: *mut BlockHeader,
}

const MIN_BLOCK_SIZE: usize = 16;
static mut FREE_LIST: *mut BlockHeader = core::ptr::null_mut();

unsafe fn heap_init(start: *mut u8, size: usize) {
    let block = start as *mut BlockHeader;
    (*block).size = size - core::mem::size_of::<BlockHeader>();
    (*block).free = true;
    (*block).next = core::ptr::null_mut();
    FREE_LIST = block;
}

unsafe fn heap_alloc(size: usize) -> *mut u8 {
    let header_size = core::mem::size_of::<BlockHeader>();
    let mut curr = FREE_LIST;
    while !curr.is_null() {
        if (*curr).free && (*curr).size >= size {
            if (*curr).size >= size + header_size + MIN_BLOCK_SIZE {
                let remainder = (curr as *mut u8).add(header_size + size) as *mut BlockHeader;
                (*remainder).size = (*curr).size - size - header_size;
                (*remainder).free = true;
                (*remainder).next = (*curr).next;
                (*curr).size = size;
                (*curr).next = remainder;
            }
            (*curr).free = false;
            return (curr as *mut u8).add(header_size);
        }
        curr = (*curr).next;
    }
    core::ptr::null_mut()
}

unsafe fn heap_free(ptr: *mut u8) {
    let header_size = core::mem::size_of::<BlockHeader>();
    let block = ptr.sub(header_size) as *mut BlockHeader;
    (*block).free = true;
}

O atributo #[repr(C)] na struct do header é necessário aqui pelo mesmo motivo que um kernel escrito em Rust geralmente precisa dele em qualquer estrutura cujo layout de memória precise ser previsível: o layout padrão de struct do Rust é deliberadamente não especificado e pode reordenar campos para otimização, enquanto size, free e next precisam ocupar exatamente os offsets que a aritmética de ponteiros deste código pressupõe.

Notas de implementação

Escrever além do fim de uma alocação corrompe o que estiver logo depois na memória, comumente o header do próximo bloco, já que blocos são tipicamente empacotados de forma contígua, o que pode fazer uma alocação ou liberação posterior e não relacionada falhar de uma forma que parece inteiramente desconectada do bug real. Liberar o mesmo ponteiro duas vezes corrompe a free list ao ligar um bloco a ela mais de uma vez, de modo que uma alocação subsequente pode retornar a mesma memória para dois chamadores diferentes simultaneamente. Ambas as classes de bug são consideravelmente mais difíceis de diagnosticar em um heap allocator do que na maior parte do resto do código, precisamente porque seus sintomas aparecem longe de sua causa; builds de depuração de um alocador costumam adicionar valores de guarda ao redor de cada bloco e verificá-los em toda operação especificamente para capturar esse tipo de corrupção mais perto de onde ela de fato ocorre.

Alinhamento merece atenção separada do dimensionamento: a maioria das arquiteturas exige que certos tipos de dados comecem em endereços que sejam múltiplos de seu tamanho, e um alocador que não garante um alinhamento mínimo para todo ponteiro retornado eventualmente vai entregar memória que causa uma falha de acesso desalinhado, ou degradação silenciosa de desempenho em arquiteturas que toleram desalinhamento mas o penalizam.

Valores de guarda colocados imediatamente antes e depois da região utilizável de um bloco, comumente chamados de redzones, estendem essa defesa especificamente contra escritas que ultrapassam o limite de uma alocação, em vez de corrompê-la internamente: um padrão de byte fixo e reconhecível é escrito nos bytes de redzone quando um bloco é alocado, e verificado novamente quando é liberado, de modo que uma escrita que se estenda mesmo um pouco além do fim do tamanho requisitado pelo chamador é capturada no momento em que o bloco é liberado, em vez de aparecer muito mais tarde como uma corrupção não relacionada e inexplicada em algum outro lugar do heap. Ferramentas construídas em torno dessa técnica, mais notavelmente o AddressSanitizer, estendem a mesma ideia ainda mais, envenenando adicionalmente a redzone de uma forma que uma verificação de hardware ou software pode detectar imediatamente no momento de um acesso fora dos limites, em vez de apenas retroativamente quando o bloco é eventualmente liberado.

Referências

^ D. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms: descreve a técnica de boundary tag e estratégias clássicas de alocação por free list.
^ J. L. Peterson e T. A. Norman, “Buddy Systems,” Communications of the ACM, 1977: a descrição original da alocação de memória por buddy system.
^ J. Bonwick, “The Slab Allocator: An Object-Caching Kernel Memory Allocator,” USENIX Summer 1994: introduz o modelo de alocação slab usado pela maioria dos kernels de produção.

Ver também

Physical Memory: o alocador de frames de página do qual um heap allocator solicita sua memória subjacente.
Paging & Virtual Memory: como as páginas que um heap allocator gerencia acabam mapeadas em um espaço de endereçamento.
O Slab Allocator: um tratamento completo do design de tamanho fixo tocado brevemente acima.