{"id":619,"date":"2025-01-14T11:31:00","date_gmt":"2025-01-14T14:31:00","guid":{"rendered":"https:\/\/suspensao.blog.br\/descrenca\/?p=619"},"modified":"2025-03-17T18:19:43","modified_gmt":"2025-03-17T21:19:43","slug":"implementando-malloc-e-free-juntando-blocos-pequenos","status":"publish","type":"post","link":"https:\/\/suspensao.blog.br\/descrenca\/implementando-malloc-e-free-juntando-blocos-pequenos\/","title":{"rendered":"Implementando malloc() e free() \u2014 juntando blocos pequenos"},"content":{"rendered":"\n

No post<\/em> anterior<\/a>, aprendemos como dividir blocos para aproveitar melhor os espa\u00e7os grandes. Contudo, isso traz um novo desafio: a fragmenta\u00e7\u00e3o da mem\u00f3ria. Blocos ores podem se acumular, formando cadeias de blocos livres que, se unificados, atenderiam a requisi\u00e7\u00f5es maiores. \u00c0 medida que os blocos s\u00e3o divididos, tornam-se cada vez menores, dificultando seu reaproveitamento.<\/p>\n\n\n\n

Como blocos pequenos podem aumentar o consumo de mem\u00f3ria<\/h2>\n\n\n\n

Considere, por exemplo, o snippet<\/em> de c\u00f3digo abaixo:<\/p>\n\n\n

void<\/span> *ptr1 = abmalloc(128<\/span>);\nvoid<\/span> *ptr2 = abmalloc(8<\/span>);\nabfree(ptr1);\nvoid<\/span> *ptr3 = abmalloc(8<\/span>);\nabfree(ptr3);\nvoid<\/span> *ptr4 = abmalloc(128<\/span>);<\/code><\/span>Code language:<\/span> JavaScript<\/span> (<\/span>javascript<\/span>)<\/span><\/small><\/pre>\n\n\n
Nele, alocamos 128 bytes de mem\u00f3ria e, posteriormente, 8 bytes. Os blocos de mem\u00f3ria teriam um layout<\/em> similar \u00e0 figura abaixo:<\/p>\n\n\n\n
\"Diagrama<\/a><\/figure>\n\n\n\n
Depois, liberamos o bloco maior:<\/p>\n\n\n\n
\"Diagrama<\/a><\/figure>\n\n\n\n
…e alocamos 8 bytes. Devido \u00e0s \u00faltimas mudan\u00e7as na fun\u00e7\u00e3o abmalloc()<\/code><\/a>, esses 8 bytes ser\u00e3o extra\u00eddos do bloco maior:<\/p>\n\n\n\n
\"Diagrama<\/a><\/figure>\n\n\n\n
Agora, ao liberar os 8 bytes rec\u00e9m-alocados, obtivemos dois blocos livres:<\/p>\n\n\n\n
\"Diagrama<\/a><\/figure>\n\n\n\n
Quando alocamos um novo bloco de 128 bytes, enfrentamos um problema: nenhum dos dois blocos livres possui tamanho suficiente individualmente, embora, juntos, eles pudessem atender \u00e0 requisi\u00e7\u00e3o. Como resultado, um novo bloco \u00e9 alocado no final da stack<\/em>, que continua a crescer.<\/p>\n\n\n\n
\"Um<\/a><\/figure>\n\n\n\n
Uma solu\u00e7\u00e3o para esse problema \u00e9 unir blocos livres adjacentes.<\/p>\n\n\n\n
Refatorando para reuso e legibilidade<\/h2>\n\n\n\n
Antes de prosseguirmos, faremos mais uma rodada de refatora\u00e7\u00f5es, pois h\u00e1 trechos de c\u00f3digo pequenos, mas complexos, que ser\u00e3o reutilizados.<\/p>\n\n\n\n
Primeiramente, vamos criar uma fun\u00e7\u00e3o que, ao receber um header<\/em>, retorne um ponteiro para a \u00e1rea de mem\u00f3ria a ser devolvida ao usu\u00e1rio. At\u00e9 agora, temos obtido esse resultado somando uma unidade ao ponteiro do header<\/em>. Vamos encapsular essa l\u00f3gica em uma fun\u00e7\u00e3o para simplificar e melhorar a reutiliza\u00e7\u00e3o do c\u00f3digo:<\/p>\n\n\n
void<\/span> *header_user_area(Header *header) {\n  return<\/span> header + 1<\/span>;\n}<\/code><\/span>Code language:<\/span> JavaScript<\/span> (<\/span>javascript<\/span>)<\/span><\/small><\/pre>\n\n\n
Consequentemente, em todos os lugares de abmalloc()<\/code> onde anteriormente utiliz\u00e1vamos:<\/p>\n\n\n
return<\/span> header + 1<\/span>;<\/code><\/span>Code language:<\/span> JavaScript<\/span> (<\/span>javascript<\/span>)<\/span><\/small><\/pre>\n\n\n
…vamos utilizar a nova fun\u00e7\u00e3o:<\/p>\n\n\n\n
return header_user_area(first);<\/pre>\n\n\n\n
Tamb\u00e9m precisamos frequentemente do ponteiro para a posi\u00e7\u00e3o de mem\u00f3ria ap\u00f3s o bloco. Atualmente, calculamos isso com uma f\u00f3rmula um tanto complicada: fazemos o casting do ponteiro do header para void*<\/code>, somamos o tamanho da estrutura Header<\/code> e adicionamos o tamanho do bloco alocado. Essa l\u00f3gica pode ser observada na fun\u00e7\u00e3o header_split()<\/code>:<\/p>\n\n\n
    Header *new_header = ((void<\/span>*)header) + sizeof(Header) + header->size;<\/code><\/span>Code language:<\/span> JavaScript<\/span> (<\/span>javascript<\/span>)<\/span><\/small><\/pre>\n\n\n
Vamos criar uma fun\u00e7\u00e3o para executar esta opera\u00e7\u00e3o, chamada header_address_after_block()<\/code>:<\/p>\n\n\n
void<\/span> *header_address_after_block(Header *header) {\n  return<\/span> ((void<\/span>*)header) + sizeof(Header) + header->size;\n}<\/code><\/span>Code language:<\/span> JavaScript<\/span> (<\/span>javascript<\/span>)<\/span><\/small><\/pre>\n\n\n
Como a fun\u00e7\u00e3o header_user_area()<\/code> j\u00e1 realiza basicamente a mesma opera\u00e7\u00e3o que a primeira parte da f\u00f3rmula, podemos utiliz\u00e1-la para simplificar header_split()<\/code>:<\/p>\n\n\n
void<\/span> *header_address_after_block(Header *header) {\n  return<\/span> header_user_area(header) + header->size;\n}<\/code><\/span>Code language:<\/span> JavaScript<\/span> (<\/span>javascript<\/span>)<\/span><\/small><\/pre>\n\n\n
Depois disso, substituiremos a f\u00f3rmula pela nossa fun\u00e7\u00e3o em header_split()<\/code>:<\/p>\n\n\n
    Header *new_header = header_address_after_block(header);<\/code><\/span><\/pre>\n\n\n
Por fim, ser\u00e1 necess\u00e1rio verificar se, dado um header<\/code>, existe um bloco livre antes ou depois dele. A express\u00e3o para essa verifica\u00e7\u00e3o \u00e9 intuitiva, mas extensa. Por exemplo, a f\u00f3rmula abaixo \u00e9 usada para determinar se h\u00e1 um bloco livre antes:<\/p>\n\n\n
(header->previous != NULL<\/span>) && header->previous->available<\/code><\/span>Code language:<\/span> PHP<\/span> (<\/span>php<\/span>)<\/span><\/small><\/pre>\n\n\n
Para facilitar um pouco a leitura, vamos colocar essa express\u00e3o em uma fun\u00e7\u00e3o, assim como a outra, correspondente a blocos posteriores:<\/p>\n\n\n
bool header_previous_available(Header *header) {\n  return<\/span> (header->previous != NULL<\/span>) && header->previous->available;\n}\n\nbool header_next_available(Header *header) {\n  return<\/span> (header->next != NULL<\/span>) && header->next->available;\n}<\/code><\/span>Code language:<\/span> PHP<\/span> (<\/span>php<\/span>)<\/span><\/small><\/pre>\n\n\n
Pronto, agora temos quatro novas ferramentas que ir\u00e3o nos ajudar a fundir blocos dispon\u00edveis. Vamos em frente!<\/p>\n\n\n\n
Procurando blocos livres adjacentes<\/h2>\n\n\n\n
Para juntar blocos de mem\u00f3ria livres e adjacentes, precisamos, no momento da desaloca\u00e7\u00e3o, verificar se o bloco anterior ou o bloco posterior est\u00e3o dispon\u00edveis. Podemos fazer isso criando duas vari\u00e1veis: uma para apontar para o primeiro bloco livre e outra para o \u00faltimo bloco livre. Inicialmente, ambas apontar\u00e3o para o bloco que est\u00e1 sendo desalocado.<\/p>\n\n\n
Header *header_merge(Header *header) {\n  Header *first_available = header;\n  Header *last_available = header;<\/code><\/span><\/pre>\n\n\n
Se o bloco anterior ao atual estiver livre,  first_available<\/code> aponta para ele.<\/p>\n\n\n
   if<\/span> (header_previous_available(header)) {\n     first_available = header->previous;\n   }<\/code><\/span>Code language:<\/span> PHP<\/span> (<\/span>php<\/span>)<\/span><\/small><\/pre>\n\n\n
De modo an\u00e1logo, se o pr\u00f3ximo bloco estiver dispon\u00edvel, last_available<\/code> deve apontar para ele<\/p>\n\n\n
  if<\/span> (header_next_available(header)) {\n    last_available = header->next;\n  }<\/code><\/span>Code language:<\/span> PHP<\/span> (<\/span>php<\/span>)<\/span><\/small><\/pre>\n\n\n
Quando n\u00e3o h\u00e1 blocos livres<\/h3>\n\n\n\n
Caso n\u00e3o haja blocos livres nem \u00e0 frente nem antes do bloco rec\u00e9m-desalocado, n\u00e3o h\u00e1 nada a ser fundido. Neste caso, as vari\u00e1veis first_available<\/code> e last_available<\/code> ser\u00e3o iguais a header<\/code>, e nossa fun\u00e7\u00e3o simplesmente retornar\u00e1 o ponteiro para o bloco que foi passado a ela.<\/p>\n\n\n
  if<\/span> ((first_available == header) && (last_available == header)) {\n    return<\/span> header;\n  }<\/code><\/span>Code language:<\/span> JavaScript<\/span> (<\/span>javascript<\/span>)<\/span><\/small><\/pre>\n\n\n
Nota:<\/strong> N\u00e3o precisamos verificar o bloco anterior ao anterior, ou o posterior ao posterior, e assim por diante. Se, em cada chamada de abfree()<\/code>, fundimos o bloco com qualquer vizinho livre, \u00e9 imposs\u00edvel ter dois blocos livres consecutivos. Portanto, basta verificar apenas os vizinhos imediatos.<\/p>\n\n\n\n
Atualizando o tamanho quando h\u00e1 blocos livres<\/h3>\n\n\n\n
Caso alguma das vari\u00e1veis first_available<\/code> ou last_available<\/code> n\u00e3o seja igual a header<\/code>, precisaremos fundir os blocos. Para isso, precisamos realizar duas a\u00e7\u00f5es.<\/p>\n\n\n\n
Primeiro, devemos atualizar o tamanho do primeiro bloco dispon\u00edvel para incluir o \u00faltimo bloco. Para isso, obtemos o ponteiro que aponta logo ap\u00f3s o \u00faltimo bloco dispon\u00edvel.<\/p>\n\n\n
  void<\/span> *end = header_address_after_block(last_available);<\/code><\/span>Code language:<\/span> JavaScript<\/span> (<\/span>javascript<\/span>)<\/span><\/small><\/pre>\n\n\n
O tamanho do novo bloco ser\u00e1 a diferen\u00e7a entre este ponteiro e o endere\u00e7o do bloco de usu\u00e1rio:<\/p>\n\n\n
  size_t size = end - header_user_area(first_available);E<\/code><\/span><\/pre>\n\n\n
Uma vez que tenhamos o tamanho, s\u00f3 precisamos atualizar o primeiro bloco dispon\u00edvel:<\/p>\n\n\n
  header_init(first_available, size, true<\/span>);<\/code><\/span>Code language:<\/span> JavaScript<\/span> (<\/span>javascript<\/span>)<\/span><\/small><\/pre>\n\n\n
Atualizando ponteiros do bloco fundido<\/h3>\n\n\n\n
Com o tamanho do bloco atualizado, precisamos ajustar seus ponteiros. Para o ponteiro para tr\u00e1s, ele deve passar a apontar para o bloco anterior ao primeiro bloco dispon\u00edvel:<\/p>\n\n\n
  Header *previous = first_available->previous;<\/code><\/span>Code language:<\/span> PHP<\/span> (<\/span>php<\/span>)<\/span><\/small><\/pre>\n\n\n
J\u00e1 o pr\u00f3ximo deve ser o que se seguia ao \u00faltimo bloco dispon\u00edvel:<\/p>\n\n\n
  Header *next = last_available->next;<\/code><\/span>Code language:<\/span> PHP<\/span> (<\/span>php<\/span>)<\/span><\/small><\/pre>\n\n\n
Uma vez que tenhamos esses valores, basta conect\u00e1-los adequadamente utilizando a fun\u00e7\u00e3o header_plug()<\/code>:<\/p>\n\n\n
  header_plug(first_available, previous, next);<\/code><\/span><\/pre>\n\n\n
Caso de borda: o \u00faltimo bloco<\/h3>\n\n\n\n
Um \u00faltimo cuidado que devemos ter \u00e9 considerar que o novo bloco pode vir a ser o \u00faltimo. Neste caso, o bloco que criamos deve se tornar o \u00faltimo bloco agora.<\/p>\n\n\n
  if<\/span> (last_available == last) {\n    last = first_available;\n  }\n  return<\/span> first_available;\n}<\/code><\/span>Code language:<\/span> JavaScript<\/span> (<\/span>javascript<\/span>)<\/span><\/small><\/pre>\n\n\n
Com isso, nossa fun\u00e7\u00e3o de fus\u00e3o est\u00e1 implementada.<\/p>\n\n\n\n
Utilizando header_merge()<\/code> em abfree()<\/code><\/h2>\n\n\n\n
Agora que temos uma fun\u00e7\u00e3o que une blocos livres, alteramos abfree()<\/code> para invoc\u00e1-la no header<\/em> do bloco a ser desalocado. Feito isso, prosseguimos com a libera\u00e7\u00e3o de mem\u00f3ria<\/p>\n\n\n
  Header *header = (Header*) ptr - 1;\n  header = header_merge(header);\n\n  if (header == last) {<\/code><\/span><\/pre>\n\n\n
Conclus\u00e3o<\/h2>\n\n\n\n
Aqui est\u00e1 a fun\u00e7\u00e3o abfree()<\/code> completa:<\/p>\n\n\n
void abfree(void *ptr) {\n  if<\/span> (ptr == NULL<\/span>) {\n    return<\/span>;\n  }\n  Header *header = (Header*) ptr - 1<\/span>;\n\n  header = header_merge(header);\n\n  if<\/span> (header == last) {\n    while<\/span> (header_previous_available(header)) {\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}\n\nHeader *header_new(Header *previous, size_t size, bool available) {\n  Header *header = sbrk(sizeof(Header) + size);\n  header_init(header, size, available);\n  header_plug(header, previous, NULL<\/span>);\n  return<\/span> header;\n}\n\nvoid header_init( Header *header, size_t size, bool available) {\n  header->size = size;\n  header->available = available;\n}\n\nvoid header_plug(Header *header, Header *previous, Header *next) {\n  header->previous = previous;\n  if<\/span> (previous != NULL<\/span>) {\n    previous->next = header;\n  }\n  header->next = next;\n  if<\/span> (next != NULL<\/span>) {\n    next->previous = header;\n  }\n}\n\nvoid *header_user_area(Header *header) {\n  return<\/span> header + 1<\/span>;\n}\n\nvoid *header_address_after_block(Header *header) {\n  return<\/span> header_user_area(header) + header->size;\n}\n\nbool header_previous_available(Header *header) {\n  return<\/span> (header->previous != NULL<\/span>) && header->previous->available;\n}\n\nbool header_next_available(Header *header) {\n  return<\/span> (header->next != NULL<\/span>) && header->next->available;\n}\n\nHeader *header_merge(Header *header) {\n  Header *first_available = header;\n  Header *last_available = header;\n\n  if<\/span> (header_previous_available(header)) {\n    first_available = header->previous;\n  }\n  if<\/span> (header_next_available(header)) {\n    last_available = header->next;\n  }\n\n  if<\/span> ((first_available == header) && (last_available == header)) {\n    return<\/span> header;\n  }\n\n  void *end = header_address_after_block(last_available);\n  size_t size = end - header_user_area(first_available);\n  header_init(first_available, size, true<\/span>);\n\n  Header *previous = first_available->previous;\n  Header *next = last_available->next;\n  header_plug(first_available, previous, next);\n\n  if<\/span> (last_available == last) {\n    last = first_available;\n  }\n\n  return<\/span> first_available;\n}\n\nHeader *header_split(Header *header, size_t size) {\n  size_t original_size = header->size;\n  if<\/span> (original_size > size + sizeof(Header)) {\n    header->size = original_size - size - sizeof(Header);\n    Header *new_header = header_address_after_block(header);\n    header_init(new_header, size, true<\/span>);\n    header_plug(new_header, header, header->next);\n    if<\/span> (header == last) {\n      last = new_header;\n    }\n    return<\/span> new_header;\n  } else<\/span> {\n    return<\/span> header;\n  }\n}<\/code><\/span>Code language:<\/span> PHP<\/span> (<\/span>php<\/span>)<\/span><\/small><\/pre>\n\n\n
Com as altera\u00e7\u00f5es deste e do \u00faltimo post<\/em>, o tamanho dos blocos livres deixam de ser um agravante no consumo de mem\u00f3ria, e nossa fun\u00e7\u00e3o malloc()<\/code> aproxima-se de ficar pronta. H\u00e1 por\u00e9m, um \u00faltimo problema a ser resolvido: o alinhamento de blocos de mem\u00f3ria. Examinaremos isto no pr\u00f3ximo post<\/em><\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
No post anterior, aprendemos como dividir blocos para aproveitar melhor os espa\u00e7os grandes. Contudo, isso traz um novo desafio: a fragmenta\u00e7\u00e3o da mem\u00f3ria. Blocos ores podem se acumular, formando cadeias de blocos livres que, se unificados, atenderiam a requisi\u00e7\u00f5es maiores. \u00c0 medida que os blocos s\u00e3o divididos, tornam-se cada vez menores, dificultando seu reaproveitamento. Como […]<\/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,1],"tags":[],"class_list":["post-619","post","type-post","status-publish","format-standard","hentry","category-c","category-libc","category-linux","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p23QLV-9Z","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/619","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=619"}],"version-history":[{"count":7,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/619\/revisions"}],"predecessor-version":[{"id":699,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/619\/revisions\/699"}],"wp:attachment":[{"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/media?parent=619"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/categories?post=619"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/tags?post=619"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}