Memória Física

Antes que um kernel possa mapear qualquer coisa, ele precisa saber quais endereços físicos correspondem de fato a RAM utilizável, e quais desses endereços estão atualmente livres versus já reivindicados pela imagem do kernel, estruturas de firmware, ou outra alocação. Gerenciamento de memória física é a camada responsável por rastrear isso, um frame de página de cada vez (convencionalmente 4 KB, correspondendo ao menor tamanho de página que a paginação suporta), e fica abaixo tanto da paginação quanto de qualquer heap allocator construído sobre ela, nenhum dos quais consegue funcionar sem uma fonte de frames físicos para trabalhar.

Descobrindo a memória disponível

Um kernel não precisa determinar sozinho quais endereços físicos são RAM utilizável; o firmware já sabe, já que inicializou o controlador de memória, e relata essa informação através de um mapa de memória que o kernel recupera durante o boot inicial. Em sistemas baseados em BIOS, isso vem da chamada de firmware int 0x15, EAX=0xE820, executada ainda em real mode antes de entrar em protected mode, retornando uma série de entradas cada uma descrevendo o endereço-base, comprimento e tipo (utilizável, reservado, ACPI recuperável, ACPI NVS, ou defeituoso) de uma faixa contígua. Sistemas UEFI, em vez disso, chamam GetMemoryMap, que retorna uma lista conceitualmente semelhante através de uma estrutura e convenção de chamada diferentes, sem a mesma restrição de timing de real mode. Um bootloader seguindo a especificação Multiboot recupera essa informação em nome do kernel e a repassa na estrutura de informação de boot, poupando o kernel de implementar detecção de memória específica de firmware por conta própria.

Independentemente da fonte, um mapa de memória bruto não é imediatamente seguro para tratar como “tudo marcado utilizável está livre”: a própria imagem do kernel ocupa parte do que o firmware relata como memória utilizável, já que o firmware não tem como saber de antemão onde um kernel será carregado, e o mapa de memória é gerado antes mesmo de o kernel existir como uma entidade carregada e em execução. Um kernel precisa reservar adicionalmente a faixa física que seu próprio código, dados, e quaisquer estruturas iniciais de boot (tabelas de página, uma estrutura de informação Multiboot, um ramdisk inicial) ocupam, antes de considerar o resto de uma região “utilizável” de fato livre.

Rastreando o estado de alocação

Uma vez conhecido o conjunto de frames utilizáveis, algo precisa rastrear quais deles estão atualmente alocados. Várias estruturas são comuns, trocando overhead de memória por velocidade de alocação e a granularidade das operações que suportam eficientemente.

Um bitmap dedica um bit por frame, definido ou limpo de acordo com se aquele frame está em uso; compacto (aproximadamente 32 KB de bitmap por gigabyte de memória física gerenciada) e simples de raciocinar sobre, mas uma busca por um frame livre é uma varredura linear a menos que combinada com estruturas auxiliares como uma dica em cache de “primeiro índice conhecido como livre” para evitar revarrer repetidamente regiões já cheias.

uint8_t frame_bitmap[MAX_FRAMES / 8];

void mark_used(size_t frame) {
    frame_bitmap[frame / 8] |= (1 << (frame % 8));
}

int find_free_frame(void) {
    for (size_t i = 0; i < MAX_FRAMES; i++) {
        if (!(frame_bitmap[i / 8] & (1 << (i % 8))))
            return i;
    }
    return -1; // sem memória
}

Uma free list, em vez disso, encadeia frames livres diretamente, armazenando um ponteiro para o próximo frame livre dentro do próprio frame livre, já que um frame que está livre não tem outro conteúdo que precise ser preservado, usar seu próprio espaço para contabilidade não custa nada extra. Alocação e liberação são ambas de tempo constante, retirando ou inserindo no início da lista, ao custo de precisar de um mecanismo separado (tipicamente um bitmap ou uma verificação de faixa) para determinar se um endereço arbitrário está atualmente alocado, já que percorrer a própria free list só revela o que não está alocado.

Um buddy allocator, coberto com mais profundidade como técnica geral em Heap Allocators, também é comumente usado especificamente no nível de frame físico, já que alocações de página frequentemente precisam de mais de um frame contíguo de uma vez (para um buffer de DMA, ou para um bloco grande o suficiente para sustentar uma huge page), e os blocos de potência de dois e o coalescing rápido baseado em endereço de um buddy allocator se ajustam bem a esse padrão.

Regiões reservadas

Além da própria imagem do kernel, várias outras regiões de memória física são convencionalmente proibidas independentemente do que o mapa de memória do firmware relata. O primeiro megabyte de memória física contém uma mistura de vetores de interrupção de real mode, áreas de dados de BIOS, e memória de vídeo legada que código mais antigo ou dependente de firmware ainda pode esperar encontrar ali, e é frequentemente deixado permanentemente reservado mesmo em sistemas que não dependem mais diretamente de nada disso. Tabelas ACPI, onde quer que o firmware as tenha colocado, precisam permanecer intactas pelo tempo que o kernel pretenda consultá-las, o que para tabelas como a MADT (usada para configurar o APIC) costuma ser apenas durante o boot inicial, mas para outras pode ser indefinidamente. Regiões de I/O mapeado em memória, como os alvos de um Base Address Register de um dispositivo PCI, não são RAM alguma, apesar de ocuparem endereços no mesmo espaço físico, e nunca devem ser alocadas como se fossem memória de propósito geral.

Notas de implementação

O frame 0, endereço físico zero, merece cautela específica: alocá-lo e mapeá-lo no espaço de endereçamento de um processo significa que uma desreferência de ponteiro nulo naquele processo lê ou escreve silenciosamente memória real e válida em vez de falhar, anulando uma das proteções acidentais mais úteis que um kernel ganha de graça. A maioria das implementações simplesmente marca o frame 0 como permanentemente reservado, em vez de arriscar isso.

Fragmentação no nível de frame físico se comporta de forma diferente da fragmentação em um heap allocator de propósito geral: como toda unidade tem exatamente o tamanho de um frame, não há fragmentação interna por tamanhos de alocação incompatíveis da forma que um heap allocator de tamanho variável experimenta, mas fragmentação externa (existir frames livres totais suficientes, sem nenhuma das sequências contíguas multi-frame necessárias disponível) continua sendo uma preocupação real para qualquer coisa que requisite mais de um frame por vez, exatamente o problema que a estrutura de um buddy allocator busca resolver.

Referências

^ Especificação ACPI: define o formato de entrada do mapa de memória E820 e os valores de seu campo de tipo.
^ Especificação UEFI, EFI_BOOT_SERVICES.GetMemoryMap(): a interface nativa correspondente de descoberta de memória em UEFI.

Ver também

Paging & Virtual Memory: como os frames rastreados aqui acabam mapeados em um espaço de endereçamento virtual.
Heap Allocators: a camada construída sobre a alocação de frames físicos para requisições com granularidade menor que uma página.
initrd: uma estrutura de tempo de boot cuja faixa física precisa do mesmo tipo de reserva descrito acima.