{"id":613,"date":"2024-02-01T11:15:00","date_gmt":"2024-02-01T14:15:00","guid":{"rendered":"https:\/\/suspensao.blog.br\/descrenca\/?p=613"},"modified":"2024-04-09T10:26:24","modified_gmt":"2024-04-09T13:26:24","slug":"implementando-malloc-e-free-reutilizando-blocos-de-memoria","status":"publish","type":"post","link":"https:\/\/suspensao.blog.br\/descrenca\/implementando-malloc-e-free-reutilizando-blocos-de-memoria\/","title":{"rendered":"Implementando malloc() e free() \u2014 reutilizando blocos de mem\u00f3ria"},"content":{"rendered":"\n

Este post faz parte de uma s\u00e9rie sobre como implementar as fun\u00e7\u00f5es malloc()<\/code> e free()<\/code>. No artigo anterior<\/a>, alteramos nossas fun\u00e7\u00f5es para liberar alguns blocos de mem\u00f3ria. Contudo, isto apenas ocorria se os blocos liberados fossem desalocados do mais novo ao mais antigo.<\/p>\n\n\n\n

Isto n\u00e3o faria muita diferen\u00e7a. Raramente a mem\u00f3ria alocada dinamicamente se comporta com uma pilha, onde o bloco mais novo \u00e9 sempre desalocado primeiro. A grande vantagem da aloca\u00e7\u00e3o de mem\u00f3ria din\u00e2mica, afinal, \u00e9 que ela n\u00e3o<\/em> funciona como uma pilha.<\/p>\n\n\n\n

Para entender as limita\u00e7\u00f5es de nossa implementa\u00e7\u00e3o, considere o c\u00f3digo abaixo<\/p>\n\n\n\n

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
abfree(ptr1);
void *ptr3 = abmalloc(8);<\/pre>\n\n\n\n
Na primeira linha, alocamos oito bytes, e os liberamos na terceira linha. Na \u00faltima linha, alocamos oito bytes de novo. Contudo, n\u00e3o podemos reaproveitar a mem\u00f3ria liberada, pois novos blocos de mem\u00f3ria s\u00f3 s\u00e3o alocados no topo do heap<\/em>. Para economizar mem\u00f3ria de verdade, precisamos de uma solu\u00e7\u00e3o mais sofisticada.<\/p>\n\n\n\n
Uma op\u00e7\u00e3o \u00e9 reutilizar blocos livres. Quando desalocarmos um bloco de mem\u00f3ria, vamos marc\u00e1-lo como dispon\u00edvel para reuso. Quando uma solicita\u00e7\u00e3o de mem\u00f3ria de tamanho menor ou igual a algum bloco dispon\u00edvel ocorrer, podemos apenas retornar um ponteiro para o bloco dispon\u00edvel e marc\u00e1-lo como em uso.<\/p>\n\n\n\n
Para isto, acrescentamos ao cabe\u00e7alho dos blocos um campo booleano, chamado available<\/code>, que indicar\u00e1 se o bloco est\u00e1 livre. Como um bloco s\u00f3 pode ser reusado se a mem\u00f3ria solicitada por abmalloc()<\/code> for menor ou igual \u00e0 dispon\u00edvel no bloco, precisamos tamb\u00e9m de um campo no cabe\u00e7alho indicando o tamanho do bloco, que chamaremos de size<\/code>. <\/p>\n\n\n\n
typedef struct Header {\n  struct Header *previous;\n  size_t size;\n  bool available;\n} Header;<\/pre>\n\n\n\n
Quando o bloco \u00e9 alocado, o valor do campo available<\/code> deve ser false<\/code> (j\u00e1 que o bloco n\u00e3o est\u00e1 dispon\u00edvel). Tamb\u00e9m registramos o tamanho do bloco no campo size<\/code>:<\/p>\n\n\n\n
void *abmalloc(size_t size) {\n  Header *header = sbrk(sizeof(Header) + size);\n  header->previous = last;\n  header->size = size;\n  header->available = false;\n  last = header;\n  return last + 1;\n}<\/pre>\n\n\n\n
Temos as informa\u00e7\u00f5es no cabe\u00e7alho mas ainda n\u00e3o estamos reusando mem\u00f3ria desalocada. Para reaproveitar os blocos dispon\u00edveis, precisamos encontr\u00e1-los! O algoritmo para isto \u00e9 bem simples: logo no come\u00e7o abmalloc()<\/code> ir\u00e1 iterar sobre os blocos, a partir do \u00faltimo at\u00e9 chegar ao primeiro. Como o ponteiro previous<\/code> do primeiro bloco \u00e9 sempre NULL<\/code>, paramos quando o ponteiro for NULL<\/code>:<\/p>\n\n\n\n
void *abmalloc(size_t size) {
   Header *header = last;
   while (header != NULL) {
     header = header->previous;
   }<\/pre>\n\n\n\n
Em cada itera\u00e7\u00e3o, verificamos se o bloco est\u00e1 dispon\u00edvel e tem tamanho aceit\u00e1vel. Se no meio desse processo encontrarmos um bloco dispon\u00edvel maior ou igual ao que precisamos, estamos com sorte! Marcamos o bloco como indispon\u00edvel, e o retornamos.<\/p>\n\n\n\n
void *abmalloc(size_t size) {
   Header *header = last;
   while (header != NULL) {
     if (header->available && (header->size >= size)) {
       header->available = false;
       return header + 1;
     }
     header = header->previous;
   }<\/pre>\n\n\n\n
E se n\u00e3o encontrarmos um bloco que satisfa\u00e7a essas condi\u00e7\u00f5es? Neste caso a fun\u00e7\u00e3o abmalloc()<\/code> aumenta o heap<\/em>, como j\u00e1 fazia antes:<\/p>\n\n\n\n
void *abmalloc(size_t size) {\n  Header *header = last;\n  while (header != NULL) {\n    if (header->available && (header->size >= size)) {\n      header->available = false;\n      return header + 1;\n    }\n    header = header->previous;\n  }\n  header = sbrk(sizeof(Header) + size);\n  header->previous = last;\n  header->size = size;\n  header->available = false;\n  last = header;\n  return last + 1;\n}<\/pre>\n\n\n\n
Na hora de desalocar, temos duas situa\u00e7\u00f5es poss\u00edveis. Se o bloco desalocado por abfree()<\/code> for o \u00faltimo, nada muda: movemos o topo do heap<\/em> para o come\u00e7o do bloco, alteramos o ponteiro last<\/code>. Mas se o bloco n\u00e3o<\/em> estiver no topo do heap? Simplesmente marcamos ele como dispon\u00edvel, como pode ser visto na cl\u00e1usula else<\/code> da fun\u00e7\u00e3o abaixo:<\/p>\n\n\n\n
void abfree(void *ptr) {\n   Header *header = (Header*) ptr - 1;\n   if (header == last) {\n     last = header->previous;\n     brk(header);\n   } else {\n     header->available = true;\n   }\n }<\/pre>\n\n\n\n
Reutilizar blocos de mem\u00f3ria \u00e9 um enorme avan\u00e7o. Contudo, podemos ser ainda mais eficientes no uso de mem\u00f3ria. Por exemplo, s\u00f3 reduzimos o tamanho do heap<\/em> se desalocamos o \u00faltimo bloco. Se h\u00e1 mais blocos inutilizados logo antes dele, poder\u00edamos liber\u00e1-los tamb\u00e9m. Veremos como fazer isto no pr\u00f3ximo post<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Este post faz parte de uma s\u00e9rie sobre como implementar as fun\u00e7\u00f5es malloc() e free(). No artigo anterior, alteramos nossas fun\u00e7\u00f5es para liberar alguns blocos de mem\u00f3ria. Contudo, isto apenas ocorria se os blocos liberados fossem desalocados do mais novo ao mais antigo. Isto n\u00e3o faria muita diferen\u00e7a. Raramente a mem\u00f3ria alocada dinamicamente se comporta […]<\/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,179,10,12,1],"tags":[79,180,171,96,170],"class_list":["post-613","post","type-post","status-publish","format-standard","hentry","category-c","category-libc","category-linux","category-programacao","category-uncategorized","tag-c","tag-desenvolvimento-de-software","tag-gerenciamento-de-memoria","tag-linguagens-de-programacao","tag-malloc"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p23QLV-9T","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/613","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=613"}],"version-history":[{"count":4,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/613\/revisions"}],"predecessor-version":[{"id":645,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/613\/revisions\/645"}],"wp:attachment":[{"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/media?parent=613"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/categories?post=613"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/tags?post=613"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}