heap_allocator
1.0.0
Este é um alocador de heap simples que escrevi para um sistema operacional de hobby no qual estou trabalhando. Escrevi este alocador com muito pouca pesquisa e ele foi feito para ser o mais fácil de entender possível. Acho que este repositório pode ser útil para aqueles que são novos no desenvolvimento de sistemas operacionais (como eu) ou estão interessados em ver uma versão simplificada de funções como malloc e free.
Existem dois arquivos de cabeçalho que definem o heap e a lista vinculada. para compilar este repositório:
$ gcc main.c llist.c heap.c -o heap_test
$ ./heap_test
isso executará uma demonstração do alocador e imprimirá algumas informações.
Para inicializar esse heap, uma seção de memória deve ser fornecida. Neste repositório, essa memória é fornecida pelo malloc (sim, alocando um heap via heap). Em uma configuração de sistema operacional, algumas páginas precisariam ser mapeadas e fornecidas ao heap (um cenário). Observe que os compartimentos na estrutura heap_t também precisam de memória alocada para eles.
Quando a função init_heap é chamada, o endereço da estrutura de heap vazia (com ponteiros de bin alocados) deve ser fornecido. A função init_heap criará então um grande pedaço com cabeçalho ( node_t struct) e um rodapé ( footer_t struct). Para determinar o tamanho deste pedaço, a função usa a constante HEAP_INIT_SIZE . Ele adicionará isso ao argumento start para determinar onde o heap termina.
Cada pedaço de memória possui uma estrutura de nó no início e uma estrutura de rodapé no final. O nó contém o tamanho, independentemente de o pedaço ser livre ou não, e dois ponteiros usados na lista duplamente vinculada (próximo e anterior). A estrutura do rodapé simplesmente mantém um ponteiro para o cabeçalho (usado ao liberar pedaços adjacentes). O pedaço no final do heap é chamado de pedaço "selvagem". É o maior pedaço e seus tamanhos mínimo e máximo são definidos em heap.h. contrair e expandir a pilha é tão fácil quanto redimensionar esse pedaço selvagem. Pedaços livres de memória são armazenados em "caixas". Cada caixa é, na verdade, apenas uma lista duplamente vinculada de nós com tamanhos semelhantes. A estrutura heap contém um número definido de compartimentos ( BIN_COUNT em heap.h). Para determinar em qual compartimento colocar um pedaço, o tamanho do pedaço é mapeado para um índice de compartimento pela função get_bin_index . Esta função de binning consistente garantirá que os pedaços possam ser acessados e armazenados de maneira definida. Os pedaços são classificados à medida que são inseridos nas caixas, de modo que a inserção dos pedaços não é O(1), mas isso torna muito mais fácil encontrar os pedaços que melhor se ajustam. Observe que a função binning pode ser definida da maneira que o usuário deste heap achar adequado. pode ser benéfico determinar uma função de binning mais sofisticada para ajudar na recuperação rápida de pedaços.
A função heap_alloc pega o endereço da estrutura de heap para alocar e um tamanho. A função simplesmente usa get_bin_index para determinar onde DEVE estar um pedaço desse tamanho, é claro que pode não haver um pedaço desse tamanho. Se nenhum pedaço for encontrado no compartimento correspondente, o próximo compartimento será verificado. Isso continuará até que um pedaço seja encontrado ou até que o último compartimento seja alcançado; nesse caso, um pedaço de memória será apenas retirado do pedaço selvagem. Se o pedaço encontrado for grande o suficiente, ele será dividido. Para determinar se um pedaço deve ser dividido, a quantidade de metadados (overhead) é subtraída do que nossa alocação atual não usa. Se o que sobrar for maior ou igual a MIN_ALLOC_SZ então significa que devemos dividir esse pedaço e colocar as sobras na lixeira correta. Quando estivermos prontos para retornar o pedaço que encontramos, pegamos o endereço do next campo e o retornamos. Isso é feito porque os campos next e prev não são usados enquanto um pedaço é alocado, portanto, o usuário do pedaço pode gravar dados nesses campos sem afetar o funcionamento interno do heap.
A função heap_free recebe um ponteiro retornado por heap_alloc . Ele subtrai o deslocamento correto para obter o endereço da estrutura do nó. Em vez de simplesmente colocar o pedaço no compartimento correto, os pedaços ao redor do pedaço fornecido são verificados. Se algum desses pedaços estiver livre, podemos uni-los para criar um pedaço maior. Para colar os pedaços, o rodapé é usado para obter a estrutura do nó do pedaço anterior e a estrutura do nó do próximo pedaço. Por exemplo, digamos que temos um pedaço chamado to_free . Para obter o pedaço antes deste pedaço, subtraímos sizeof(footer_t) para obter o rodapé do pedaço anterior. O rodapé contém um ponteiro para o início do bloco anterior. Para obter o próximo pedaço, simplesmente pegamos o rodapé de to_free e depois adicionamos sizeof(footer_t) para obter o próximo pedaço. Depois que tudo isso for feito e os tamanhos recalculados, o pedaço é colocado de volta em uma lixeira.
NOTA: Este código foi originalmente compilado para máquinas de 32 bits, isso significa que quando este código foi usado era aceitável converter um int em um ponteiro devido ao fato de ambos serem do mesmo tamanho. Em um sistema de 64 bits, o compilador avisará sobre a diferença de tamanho. Para silenciar esses avisos, usei uintptr_t ao converter de um unsigned int para um ponteiro. Isso atrapalha um pouco a legibilidade e algumas das conversões e aritmética dos ponteiros são detalhadas, portanto, tenha isso em mente ao ler o código.
