{"id":571,"date":"2023-10-31T10:45:00","date_gmt":"2023-10-31T13:45:00","guid":{"rendered":"https:\/\/suspensao.blog.br\/descrenca\/?p=571"},"modified":"2025-03-17T18:23:17","modified_gmt":"2025-03-17T21:23:17","slug":"malloc-free-1","status":"publish","type":"post","link":"https:\/\/suspensao.blog.br\/descrenca\/malloc-free-1\/","title":{"rendered":"Implementando malloc() e free() \u2014 primeiros passos"},"content":{"rendered":"

Seguindo a maravilhosa jornada<\/a> que \u00e9 ler\u00a0 Crafting Interpreters,<\/em><\/a> cheguei no ponto onde implementamos um interpretador em C! Como sempre, Bob Nystrom<\/a> impiedosamente nos prop\u00f5e desafios interessant\u00edssimos que nos mant\u00e9m ocupados por longos per\u00edodos. Por exemplo, neste cap\u00edtulo<\/a> ele nos sugere implementar nosso pr\u00f3prio alocador de mem\u00f3ria, sem a menor necessidade! Inevitavelmente, ca\u00ed na armadilha.<\/p>\n

O desafio nos permite alocar uma grande regi\u00e3o de mem\u00f3ria e gerenci\u00e1-la, mas decidi implementar a fun\u00e7\u00e3o malloc()<\/code> do zero. Como uso Ubuntu<\/a>, foi necess\u00e1rio primeiramente entender melhor o layout da mem\u00f3ria de um processo no Linux.<\/p>\n

Considere o diagrama abaixo, que representa o layout da mem\u00f3ria de um processo.<\/p>\n\n\n

\"Layout<\/figure>\n\n\n\n

Na mem\u00f3ria alocada para o processo, h\u00e1 v\u00e1rias se\u00e7\u00f5es. Quando o programa inicia sua execu\u00e7\u00e3o, a parte acinzentada n\u00e3o est\u00e1 em uso ainda. Ao longo de sua execu\u00e7\u00e3o, o programa declara vari\u00e1veis locais, fazendo a stack<\/em> (pilha) crescer para tr\u00e1s.<\/p>\n\n\n\n

J\u00e1 a mem\u00f3ria dinamicamente alocada \u00e9 obtida do heap<\/em>, que cresce na dire\u00e7\u00e3o oposta. A maneira bem popular de expandir o heap<\/em> \u00e9 aumentando o tamanho do segmento de data<\/a> (i.e. a se\u00e7\u00e3o que cont\u00e9m vari\u00e1veis globais e est\u00e1ticas) com a chamada de sistema sbrk()<\/code><\/a>.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

O diagrama acima ilustra como esta chamada de sistema funcional funciona. sbrk()<\/code> recebe como par\u00e2metro um n\u00famero inteiro que ir\u00e1 ser somado ao ponteiro que indica o fim do segmento de data. Depois disso, sbrk()<\/code> retorna o valor do ponteiro antes do incremento. <\/p>\n\n\n\n

De certo modo, o comportamento de sbrk()<\/code> j\u00e1 \u00e9 suficiente para alocar mem\u00f3ria. Nossa fun\u00e7a\u00f5 malloc()<\/code> pode simplesmente invocar sbrk()<\/code> e retornar para o usu\u00e1rio o ponteiro para o in\u00edcio do bloco de mem\u00f3ria alocada:<\/p>\n\n\n\n

void *abmalloc(size_t size) {
   return sbrk(size);
 }<\/pre>\n\n\n\n
Em princ\u00edpio, free()<\/code> n\u00e3o precisa fazer nada: como nesta implementa\u00e7\u00e3o sempre usamos a mem\u00f3ria do topo do heap<\/em>, n\u00e3o h\u00e1 nada que possamos fazer para reutilizar blocos de mem\u00f3ria mais antigos. Nesse sentido, free()<\/code> pode perfeitamente ser um no-op<\/a><\/em>:<\/p>\n\n\n\n
void abfree(void *ptr) {
}<\/pre>\n\n\n\n
Uma opera\u00e7\u00e3o \u00fatil pode ser feita, por\u00e9m, se o bloco a ser liberado tiver sido o \u00faltimo a ser alocado. Isto significa que ele est\u00e1 no topo da pilha, ent\u00e3o basta mover o ponteiro do topo da pilha para o in\u00edcio do bloco desalocado. Para isto, primeiramente devemos saber onde come\u00e7a o \u00faltimo bloco de mem\u00f3ria alocado, o que \u00e9 f\u00e1cil com uma vari\u00e1vel global:<\/p>\n\n\n\n
void *last_block = NULL;

void *abmalloc(size_t size) {
   last_block = sbrk(size);
   return last_block;
} <\/pre>\n\n\n\n
Depois, na fun\u00e7\u00e3o free()<\/code>, verificamos se o ponteiro passado aponta para o \u00faltimo bloco. Neste caso, movemos o topo da pilha para tr\u00e1s com a chamada de sistema brk()<\/code>. Esta syscall<\/em> recebe como par\u00e2metro um ponteiro e, se este ponteiro \u00e9 um valor “razo\u00e1vel” (n\u00e3o \u00e9 nulo, n\u00e3o aponta para dentro da stack, n\u00e3o aponta para antes do heap), usa o valor do ponteiro como novo topo do heap. O resultado seria algo assim.<\/p>\n\n\n\n
void abfree(void *ptr) {\n  if (ptr == last_block) {\n      brk(last_block);\n  }\n}<\/pre>\n\n\n\n
Esta desaloca\u00e7\u00e3o, por\u00e9m, \u00e9 in\u00fatil na pr\u00e1tica. Considere o exemplo abaixo:<\/p>\n\n\n\n
void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
abfree(ptr2);
abfree(ptr1);<\/pre>\n\n\n\n
Com a vers\u00e3o atual de abfree()<\/code>, conseguimos liberar a mem\u00f3ria apontada por ptr1<\/code>, mas n\u00e3o a apontada por ptr2<\/code>. Para poder liberar ptr2<\/code>, seria preciso saber que, uma vez que ptr1<\/code> foi desalocada, o pr\u00f3ximo \u00faltimo bloco \u00e9 ptr2<\/code>. Poder\u00edamos criar uma vari\u00e1vel second_last_block<\/code>? N\u00e3o adiantaria: ter\u00edamos o mesmo problema com o antepen\u00faltimo bloco, e assim por diante.<\/p>\n\n\n\n
Precisamos de uma estrutura de dados mais poderosa aqui, e \u00e9 isto que veremos no nosso pr\u00f3ximo post<\/em><\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
J\u00e1 imaginou como as fun\u00e7\u00f5es malloc() e free() s\u00e3o implementadas? Tive a oportunidade de aprender um pouco sobre isso, \u00e9 fascinante! Neste post, apresento os conceitos (e implementa\u00e7\u00f5es) mais b\u00e1sicos.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[29,24],"tags":[172,79,173,171,96,170],"class_list":["post-571","post","type-post","status-publish","format-standard","hentry","category-c","category-linguagens-de-programacao","tag-alocacao-de-memoria","tag-c","tag-crafting-interpreters","tag-gerenciamento-de-memoria","tag-linguagens-de-programacao","tag-malloc"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p23QLV-9d","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/571","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/comments?post=571"}],"version-history":[{"count":4,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/571\/revisions"}],"predecessor-version":[{"id":703,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/571\/revisions\/703"}],"wp:attachment":[{"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/media?parent=571"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/categories?post=571"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/tags?post=571"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}