{"id":617,"date":"2024-09-16T11:47:00","date_gmt":"2024-09-16T14:47:00","guid":{"rendered":"https:\/\/suspensao.blog.br\/descrenca\/?p=617"},"modified":"2025-03-17T18:21:13","modified_gmt":"2025-03-17T21:21:13","slug":"implementando-malloc-e-free-memoria-antiga-tem-preferencia","status":"publish","type":"post","link":"https:\/\/suspensao.blog.br\/descrenca\/implementando-malloc-e-free-memoria-antiga-tem-preferencia\/","title":{"rendered":"Implementando malloc() e free() \u2014 mem\u00f3ria antiga tem prefer\u00eancia"},"content":{"rendered":"\n

No post<\/em> anterior<\/a> desta s\u00e9rie sobre a implementa\u00e7\u00e3o das fun\u00e7\u00f5es malloc()<\/code> e free()<\/code>, mostramos como \u00e9 poss\u00edvel reutilizar blocos de mem\u00f3ria e reduzir o heap<\/em> ao liberar os blocos mais novos. No entanto, a fun\u00e7\u00e3o atual reutiliza o bloco de mem\u00f3ria livre mais recente, levando a um consumo de mem\u00f3ria maior. Vamos analisar como isso ocorre.<\/p>\n\n\n\n

Redu\u00e7\u00e3o do heap<\/em> com reaproveitamento de blocos recentes<\/h3>\n\n\n\n

Considere o cen\u00e1rio a seguir. Primeiro, alocamos quatro blocos de mem\u00f3ria:<\/p>\n\n\n\n

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8); <\/pre>\n\n\n\n
A estrutura em mem\u00f3ria pode ser visualizada assim:<\/p>\n\n\n
\n
\"Lista<\/a><\/figure>\n<\/div>\n\n\n
Agora, liberamos o primeiro e o terceiro bloco…<\/p>\n\n\n\n
abfree(ptr1);
abfree(ptr3); <\/pre>\n\n\n\n
…resultando na seguinte estrutura:<\/p>\n\n\n
\n
\"Lista<\/a><\/figure>\n<\/div>\n\n\n
Em seguida, alocamos outro bloco do mesmo tamanho:<\/p>\n\n\n\n
void *ptr5 = abmalloc(8); <\/pre>\n\n\n\n
Como fun\u00e7\u00e3o abmalloc()<\/code> come\u00e7a a busca pelo bloco livre mais recente, ela reutiliza o bloco que est\u00e1 no topo. Se agora liberarmos o \u00faltimo bloco:<\/p>\n\n\n
\n
\"Lista<\/a><\/figure>\n<\/div>\n\n\n
Se, agora, liberamos o \u00faltimo bloco…<\/p>\n\n\n\n
abfree(ptr4);<\/pre>\n\n\n\n
…poderemos reduzir o tamanho do heap<\/em> em apenas um bloco de 8 bytes, j\u00e1 que o pen\u00faltimo bloco n\u00e3o est\u00e1 mais livre:<\/p>\n\n\n
\n
\"Lista<\/a><\/figure>\n<\/div>\n\n\n
Reaproveitamento de blocos antigos<\/h3>\n\n\n\n
Agora, imagine o mesmo cen\u00e1rio, mas com uma modifica\u00e7\u00e3o: nossa fun\u00e7\u00e3o busca blocos livres come\u00e7ando pelo mais antigo.<\/p>\n\n\n\n
A estrutura inicial ser\u00e1 a mesma…<\/p>\n\n\n
\n
\"Lista<\/a><\/figure>\n<\/div>\n\n\n
…e novamente liberamos o primeiro e o terceiro bloco de mem\u00f3ria:<\/p>\n\n\n
\n
\"Lista<\/a><\/figure>\n<\/div>\n\n\n
Dessa vez, o primeiro bloco ser\u00e1 reutilizado:<\/p>\n\n\n
\n
\"Lista<\/a><\/figure>\n<\/div>\n\n\n
Agora, ao liberarmos o \u00faltimo bloco, teremos dois blocos livres no topo, permitindo reduzir o heap<\/em> em dois blocos de 8 bytes:<\/p>\n\n\n
\n
\"Lista<\/a><\/figure>\n<\/div>\n\n\n
Esse exemplo ilustra como, ao dar prefer\u00eancia a blocos mais novos, acabamos acumulando blocos livres antigos, desperdi\u00e7ando mem\u00f3ria e levando a um crescimento desnecess\u00e1rio do heap<\/em>. A solu\u00e7\u00e3o \u00e9 modificar a estrat\u00e9gia de busca, priorizando a reutiliza\u00e7\u00e3o de blocos mais antigos.<\/p>\n\n\n\n
Implementando prefer\u00eancia por blocos antigos<\/h3>\n\n\n\n
Para resolver esse problema, vamos implementar uma nova abordagem no c\u00f3digo. Primeiramente, vamos adicionar ao cabe\u00e7alho dos blocos um ponteiro para o pr\u00f3ximo bloco, permitindo percorrermos a mem\u00f3ria de maneira eficiente. Tamb\u00e9m adicionaremos um ponteiro para o primeiro bloco, o que facilitar\u00e1 a busca:<\/p>\n\n\n\n
typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;

Header *first = NULL;
Header *last = NULL;<\/pre>\n\n\n\n
Agora, faremos uma pequena refatora\u00e7\u00e3o. Como criamos blocos de mem\u00f3ria com headers em duas situa\u00e7\u00f5es diferentes, extrairemos essa l\u00f3gica para uma fun\u00e7\u00e3o auxiliar que aloca e inicializa o cabe\u00e7alho (inclusive setando o campo next<\/code> com NULL<\/code>):<\/p>\n\n\n\n
Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header) + size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}<\/pre>\n\n\n\n
Com essa nova fun\u00e7\u00e3o, podemos simplificar a l\u00f3gica dentro de abmalloc()<\/code>:<\/p>\n\n\n\n
void *abmalloc(size_t size) {
  if (size == 0) {
    return NULL;
  }
  Header *header = last;
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false;
      return header + 1;
    }
    header = header->previous;
  }
  last = header_new(last, size, false);
  return last + 1;
}<\/pre>\n\n\n\n
Agora temos acesso ao primeiro e \u00faltimo blocos e, dado um bloco, podemos descobrir o anterior e o posterior. Sabemos, tamb\u00e9m, que quando o ponteiro para o primeiro bloco for nulo, nenhum bloco ter\u00e1 sido alocado ainda. Ent\u00e3o, neste caso, alocaremos o bloco imediatamente, e inicializaremos tanto first quanto last:<\/p>\n\n\n\n
void *abmalloc(size_t size) {
  if (size == 0) {
    return NULL;
  }
  if (first == NULL) {
    first = last = header_new(NULL, size, false);
    return first + 1;
  }<\/pre>\n\n\n\n
Se first<\/code> n\u00e3o \u00e9 mais NULL<\/code>, j\u00e1 existem blocos alocados, ent\u00e3o come\u00e7aremos a busca por um bloco reutiliz\u00e1vel. Continuaremos utilizando a vari\u00e1vel header<\/code> como iterador, mas, em vez de come\u00e7ar pelo bloco mais recente, a pesquisa ser\u00e1 iniciada a partir do mais antigo:<\/p>\n\n\n\n
  Header *header = first;<\/pre>\n\n\n\n
A cada itera\u00e7\u00e3o, avan\u00e7aremos para o pr\u00f3ximo bloco na sequ\u00eancia, em vez de retroceder para o bloco anterior:<\/p>\n\n\n\n
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false;
      return header + 1;
    }
    header = header->next;
  }<\/pre>\n\n\n\n
A l\u00f3gica permanece a mesma: se encontramos um bloco dispon\u00edvel e de tamanho suficiente, ele \u00e9 retornado. Caso contr\u00e1rio, se nenhum bloco reutiliz\u00e1vel for encontrado ap\u00f3s percorrermos a lista, um novo bloco ser\u00e1 alocado:<\/p>\n\n\n\n
  last = header_new(last, size, false);
<\/pre>\n\n\n\n
Agora, precisamos ajustar o bloco que era o \u00faltimo (e que, ap\u00f3s a aloca\u00e7\u00e3o, passa a ser o pen\u00faltimo). Ele apontava para NULL<\/code>, mas agora deve apontar para o novo bloco. Para isso, setamos o campo field<\/code> do block anterior com o novo bloco:<\/p>\n\n\n\n
  last->previous->next = last;
  return last + 1;
}<\/pre>\n\n\n\n
Ajustes na Fun\u00e7\u00e3o abfree()<\/code><\/h3>\n\n\n\n
A fun\u00e7\u00e3o abfree()<\/code> mant\u00e9m basicamente a mesma estrutura, mas agora devemos tratar alguns casos de borda. Quando liberamos blocos no topo do heap<\/em>, um novo bloco passa a ser o \u00faltimo, conforme j\u00e1 fazemos neste trecho:<\/p>\n\n\n\n
    last = header->previous;
    brk(header)<\/pre>\n\n\n\n
Aqui, o ponteiro header<\/code> referencia o \u00faltimo bloco n\u00e3o nulo e dispon\u00edvel na pilha. Temos dois cen\u00e1rios poss\u00edveis: <\/p>\n\n\n\n
    \n
  1. no primeiro, o bloco atual possui um bloco anterior, que se tornar\u00e1 o novo \u00faltimo bloco. Nesse caso, devemos ajustar o ponteiro next<\/code> desse bloco para NULL<\/code>.<\/li>\n\n\n\n
  2. No segundo cen\u00e1rio, o bloco atual n\u00e3o possui um bloco anterior (ou seja, ele \u00e9 o primeiro e mais antigo bloco). Quando ele \u00e9 liberado, a pilha fica vazia. Nesse caso, em vez de tentar atualizar um campo de um bloco inexistente, basta definirmos first<\/code> como NULL<\/code>, indicando que n\u00e3o h\u00e1 mais blocos alocados:<\/li>\n<\/ol>\n\n\n\n
      last = header->previous;
      if (last != NULL) {
        last->next = NULL;
      } else {
        first = NULL;
      }
      brk(header);<\/pre>\n\n\n\n
    Conclus\u00e3o<\/h3>\n\n\n\n
    Nossas fun\u00e7\u00f5es abmalloc()<\/code> e abfree()<\/code>  agora est\u00e3o assim:<\/p>\n\n\n
    typedef struct Header {\n  struct Header *previous, *next;\n  size_t size;\n  bool available;\n} Header;\n\nHeader *first = NULL<\/span>;\nHeader *last = NULL<\/span>;\n\nHeader *header_new(Header *previous, size_t size, bool available) {\n  Header *header = sbrk(sizeof(Header) + size);\n  header->previous = previous;\n  header->next = NULL<\/span>;\n  header->size = size;\n  header->available = false<\/span>;\n  return<\/span> header;\n}\n\nvoid *abmalloc(size_t size) {\n  if<\/span> (size == 0<\/span>) {\n    return<\/span> NULL<\/span>;\n  }\n  if<\/span> (first == NULL<\/span>) {\n    first = last = header_new(NULL<\/span>, size, false<\/span>);\n    return<\/span> first + 1<\/span>;\n  }\n  Header *header = first;\n  while<\/span> (header != NULL<\/span>) {\n    if<\/span> (header->available && (header->size >= size)) {\n      header->available = false<\/span>;\n      return<\/span> header + 1<\/span>;\n    }\n    header = header->next;\n  }\n  last = header_new(last, size, false<\/span>);\n  last->previous->next = last;\n  return<\/span> last + 1<\/span>;\n}\n\nvoid abfree(void *ptr) {\n  if<\/span> (ptr == NULL<\/span>) {\n   return<\/span>;\n  }\n  Header *header = (Header*) ptr - 1<\/span>;\n  if<\/span> (header == last) {\n    while<\/span> ((header->previous != NULL<\/span>) && header->previous->available) {\n      header = header->previous;\n    }\n    last = header->previous;\n    if<\/span> (last != NULL<\/span>) {\n      last->next = NULL<\/span>;\n    } else<\/span> {\n      first = NULL<\/span>;\n    }\n    brk(header);\n  } else<\/span> {\n   header->available = true<\/span>;\n  }\n }<\/code><\/span>Code language:<\/span> PHP<\/span> (<\/span>php<\/span>)<\/span><\/small><\/pre>\n\n\n
    Esta mudan\u00e7a nos permite economizar consideravelmente mais mem\u00f3ria. Existem, contudo, problemas a resolver ainda. Por exemplo, considere o seguinte cen\u00e1rio: solicitamos a aloca\u00e7\u00e3o de um bloco de mem\u00f3ria de 8 bytes, e abmalloc()<\/code> reaproveita um boco de, digamos, 1024 bytes. H\u00e1 claramente um desperd\u00edcio.<\/p>\n\n\n\n
    Veremos como resolver isso no pr\u00f3ximo post<\/em><\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
    No post anterior desta s\u00e9rie sobre a implementa\u00e7\u00e3o das fun\u00e7\u00f5es malloc() e free(), mostramos como \u00e9 poss\u00edvel reutilizar blocos de mem\u00f3ria e reduzir o heap ao liberar os blocos mais novos. No entanto, a fun\u00e7\u00e3o atual reutiliza o bloco de mem\u00f3ria livre mais recente, levando a um consumo de mem\u00f3ria maior. Vamos analisar como isso […]<\/p>\n","protected":false},"author":2,"featured_media":663,"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":[1],"tags":[],"class_list":["post-617","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/suspensao.blog.br\/descrenca\/wp-content\/uploads\/2024\/09\/The-lower-part-of-the-Sanaa-manuscript-which-was-scrapped-and-written-over-an-original-text.-An-old-and-reused-parchment.jpg?fit=1077%2C480&ssl=1","jetpack_shortlink":"https:\/\/wp.me\/p23QLV-9X","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/617","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=617"}],"version-history":[{"count":14,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/617\/revisions"}],"predecessor-version":[{"id":701,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/617\/revisions\/701"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/media\/663"}],"wp:attachment":[{"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/media?parent=617"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/categories?post=617"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/tags?post=617"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}