Este post faz parte de uma série sobre como implementar as funções malloc()
e free()
. Anteriormente, fizemos uma implementação são simplória que praticamente não libera memória nenhuma: um ponteiro aponta para o último bloco alocado, o que permite que abfree()
o desaloque, mas somente ele.
Uma opção melhor é fazer o último bloco apontar para o penúltimo, o penúltimo para o antepenúltimo e assim por diante, formando uma lista ligada. Para isso, criamos uma struct que servirá como cabeçalho dos blocos, contendo um ponteiro para o bloco anterior:
typedef struct Header { struct Header *previous; } Header;
Além disso, o ponteiro para o último bloco, que era do tipo void*
, agora é do tipo Header*
:
Header *last = NULL;
Para usar esses cabeçalhos, abmalloc()
reserva memória suficiente para armazenar tanto o cabeçalho quanto o tamanho solicitado:
void *abmalloc(size_t size) {
Header *header = sbrk(sizeof(Header) + size);
Deste modo, utilizamos o início do bloco para armazenar informações necessárias, como um ponteiro para o último bloco alocado antes do novo:
header->previous = last;
Em seguida, atualizamos last
para apontar para o novo bloco:
last = header;
Por fim, retornamos um ponteiro para a memória que o usuário pode utilizar. Como header
aponta para os metadados, não podemos simplesmente retorná-lo. Caso contrário, toda informação do cabeçalho seria sobrescrita quando o usuário usasse o ponteiro! Ao invés disso, retornamos um ponteiro para logo depois do cabeçalho. Este ponteiro é fácil de calcular: é o endereço de memória do cabeçalho mais o tamanho do cabeçalho:
return header + 1;
}
Note como incrementamos o ponteiro header em 1. Como o tipo do ponteiro é Header*
, o incremento será, na verdade, o número de bytes da struct Header
, não um byte apenas. Por isso, o tipo do ponteiro incrementado é muito relevante na aritmética de ponteiros.
Agora que nossos blocos de memória possuem metadados no início, é preciso levar isso em conta na hora de desalocar. free()
recebe um ponteiro não para o começo do bloco, mas para a memória disponibilizada ao usuário. Logo, precisamos encontrar o começo do bloco a partir do ponteiro que o usuário passou. Nada que uma pequena aritmética de ponteiros não resolva:
void abfree(void *ptr) { Header *header = (Header*) ptr - 1;
Se header
aponta para o último bloco alocado, o bloco anterior passará a ser o último. Neste caso, podemos retornar memória do heap para o sistema operacional através de brk()
:
if (header == last) {
last = header->previous;
brk(header);
}
Eis a nova versão de nossas funções malloc()
e free()
:
typedef struct Header { struct Header *previous; } Header; Header *last = NULL; void *abmalloc(size_t size) { Header *header = sbrk(sizeof(Header) + size); header->previous = last; last = header; return header + 1; } void abfree(void *ptr) { Header *header = (Header*) ptr - 1; if (header == last) { last = header->previous; brk(header); } }
abmalloc()
e abfree()
podem ser ligeiramente mais econômicos em memória agora, mas não muito. Raramente a memória alocada dinamicamente se comporta com uma pilha, onde o bloco mais velho é sempre desalocado primeiro. No próximo post, veremos como utilizar a memória de blocos mais antigos que não estão mais em uso.
Post Revisions:
- January 24, 2024 @ 17:20:29 [Current Revision] by brandizzi
- January 24, 2024 @ 17:20:29 by brandizzi