{"id":618,"date":"2024-10-14T11:02:00","date_gmt":"2024-10-14T14:02:00","guid":{"rendered":"https:\/\/suspensao.blog.br\/descrenca\/?p=618"},"modified":"2025-03-17T18:20:26","modified_gmt":"2025-03-17T21:20:26","slug":"implementando-malloc-e-free-dividindo-blocos-grandes","status":"publish","type":"post","link":"https:\/\/suspensao.blog.br\/descrenca\/implementando-malloc-e-free-dividindo-blocos-grandes\/","title":{"rendered":"Implementando malloc() e free() \u2014 dividindo blocos grandes"},"content":{"rendered":"\n<p>No <a href=\"https:\/\/suspensao.blog.br\/descrenca\/implementando-malloc-e-free-memoria-antiga-tem-preferencia\/\">artigo anterior da s\u00e9rie<\/a>, vimos como a ordem em que escolhemos que blocos de mem\u00f3ria reutilizar pode levar a maior ou menor consumo de mem\u00f3ria, e mudamos nossas fun\u00e7\u00f5es para evitar esse desperd\u00edcio. Mas precisamos resolver outro problema, at\u00e9 mais grave: \u00e0s vezes, um bloco de mem\u00f3ria muito grande pode ocupar o espa\u00e7o que v\u00e1rios blocos menores poderiam usar. Considere o caso abaixo, em que alocamos um grande peda\u00e7o de mem\u00f3ria, desalocamos e depois alocamos dois blocos bem menores:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-1\" data-shcb-language-name=\"JavaScript\" data-shcb-language-slug=\"javascript\"><span><code class=\"hljs language-javascript\"><span class=\"hljs-keyword\">void<\/span> *ptr1 = abmalloc(<span class=\"hljs-number\">128<\/span>);\n<span class=\"hljs-keyword\">void<\/span> *ptr2 = abmalloc(<span class=\"hljs-number\">8<\/span>);\nabfree(ptr1);\n<span class=\"hljs-keyword\">void<\/span> *ptr3 = abmalloc(<span class=\"hljs-number\">8<\/span>);\n<span class=\"hljs-keyword\">void<\/span> *ptr4 = abmalloc(<span class=\"hljs-number\">8<\/span>);<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-1\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">JavaScript<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">javascript<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Aqui, temos um bloco de mem\u00f3ria de 128 bytes livre, e, ao alocarmos um bloco de apenas 8 bytes, todos os 128 bytes ficam indispon\u00edveis. Quando alocamos outro bloco de 8 bytes, o <em>heap<\/em> precisa crescer novamente. Isso n\u00e3o \u00e9 um uso eficiente de mem\u00f3ria.<\/p>\n\n\n\n<p>Existem pelo menos duas solu\u00e7\u00f5es populares para esse caso. Uma, mais eficiente, \u00e9 usar <em><a href=\"https:\/\/sourceware.org\/glibc\/wiki\/MallocInternals#Arenas_and_Heaps\">bins<\/a><\/em>: listas que agrupam blocos por tamanho. Essa \u00e9 uma abordagem mais sofisticada, por\u00e9m mais complexa. Outra op\u00e7\u00e3o, mais simples, \u00e9 encontrar um bloco grande e dividi-lo em blocos menores. Vamos seguir por essa abordagem.<\/p>\n\n\n\n<p>Mas lembre-se: mais simples n\u00e3o significa exatamente simples \ud83d\ude09<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Refatora\u00e7\u00e3o Inicial<\/h3>\n\n\n\n<p>Antes de come\u00e7armos, faremos uma pequena refatora\u00e7\u00e3o. Atualmente, a fun\u00e7\u00e3o <code>header_new()<\/code> faz duas coisas: aloca mais mem\u00f3ria para um novo bloco e j\u00e1 inicializa seu cabe\u00e7alho, definindo os metadados e os ponteiros para o bloco anterior. A parte de inicializar o cabe\u00e7alho pode ser \u00fatil, ent\u00e3o vamos extra\u00ed-la. Criamos duas novas fun\u00e7\u00f5es para melhorar a legibilidade:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A fun\u00e7\u00e3o <code>header_plug()<\/code>, que &#8220;conecta&#8221; o bloco inicializado ao anterior e ao pr\u00f3ximo.<\/li>\n\n\n\n<li>A fun\u00e7\u00e3o <code>header_init()<\/code>, que define os valores iniciais dos metadados do bloco (tamanho e disponibilidade).<\/li>\n<\/ul>\n\n\n\n<p>Aqui est\u00e1 como elas ficam:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"PHP\" data-shcb-language-slug=\"php\"><span><code class=\"hljs language-php\">void header_init(Header *header, size_t size, bool available) {\n    header-&gt;size = size;\n    header-&gt;available = available;\n}\n\nvoid header_plug(Header *header, Header *previous, Header *next) {\n    header-&gt;previous = previous;\n    <span class=\"hljs-keyword\">if<\/span> (previous != <span class=\"hljs-keyword\">NULL<\/span>) {\n        previous-&gt;next = header;\n    }\n    header-&gt;next = next;\n    <span class=\"hljs-keyword\">if<\/span> (next != <span class=\"hljs-keyword\">NULL<\/span>) {\n        next-&gt;previous = header;\n    }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">PHP<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">php<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Agora, basta alterar <code>header_new()<\/code> para usar essas novas fun\u00e7\u00f5es:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"PHP\" data-shcb-language-slug=\"php\"><span><code class=\"hljs language-php\">Header *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, <span class=\"hljs-keyword\">NULL<\/span>);\n    <span class=\"hljs-keyword\">return<\/span> header;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">PHP<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">php<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>(Al\u00e9m disso, podemos remover a linha <code>last-&gt;previous-&gt;next = last;<\/code> da fun\u00e7\u00e3o <code>abmalloc()<\/code>, j\u00e1 que <code>header_plug()<\/code> agora cuida disso.)<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Dividindo Blocos<\/h3>\n\n\n\n<p>Com essas ferramentas em m\u00e3os, vamos criar a fun\u00e7\u00e3o <code>header_split()<\/code>. Dado um cabe\u00e7alho e um tamanho m\u00ednimo requerido, esta fun\u00e7\u00e3o divide o bloco de mem\u00f3ria em dois, se o bloco original for grande o suficiente para conter<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>o tamanho requerido,<\/li>\n\n\n\n<li>um novo cabe\u00e7alho do novo bloco e<\/li>\n\n\n\n<li>um pouco de mem\u00f3ria extra.<\/li>\n<\/ul>\n\n\n\n<p>Primeiro, verificamos se o bloco \u00e9 grande o bastante:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"PHP\" data-shcb-language-slug=\"php\"><span><code class=\"hljs language-php\">Header *header_split(Header *header, size_t size) {\n    size_t original_size = header-&gt;size;\n    <span class=\"hljs-keyword\">if<\/span> (original_size &gt;= size + sizeof(Header)) {<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">PHP<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">php<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Se essa condi\u00e7\u00e3o for satisfeita, dividimos o bloco. Primeiro, reduzimos o tamanho do bloco atual, subtraindo o tamanho de um cabe\u00e7alho e o espa\u00e7o solicitado por <code>abmalloc<\/code>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-5\" data-shcb-language-name=\"PHP\" data-shcb-language-slug=\"php\"><span><code class=\"hljs language-php\">    header-&gt;size = original_size - size - sizeof(Header);<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-5\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">PHP<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">php<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Isso deixa um espa\u00e7o de mem\u00f3ria ap\u00f3s o bloco atual, que usaremos para criar o novo bloco. Calculamos o ponteiro para esse novo bloco:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-6\" data-shcb-language-name=\"PHP\" data-shcb-language-slug=\"php\"><span><code class=\"hljs language-php\">    Header *new_header = header + sizeof(Header) + header-&gt;size;<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-6\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">PHP<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">php<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Agora que temos o ponteiro para o novo bloco, inicializamos o cabe\u00e7alho com <code>header_init()<\/code>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-7\" data-shcb-language-name=\"JavaScript\" data-shcb-language-slug=\"javascript\"><span><code class=\"hljs language-javascript\">    header_init(new_header, size, <span class=\"hljs-literal\">true<\/span>);<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-7\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">JavaScript<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">javascript<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>E conectamos o novo bloco ao anterior e ao pr\u00f3ximo usando <code>header_plug()<\/code>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-8\" data-shcb-language-name=\"PHP\" data-shcb-language-slug=\"php\"><span><code class=\"hljs language-php\">    header_plug(new_header, header, header-&gt;next);<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-8\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">PHP<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">php<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Se o bloco original for o \u00faltimo, o novo bloco agora ser\u00e1 o \u00faltimo, ent\u00e3o atualizamos o ponteiro <code>last<\/code>:<\/p>\n\n\n<pre class=\"wp-block-code\"><span><code class=\"hljs\">    if (header == last) {\n        last = new_header;\n    }<\/code><\/span><\/pre>\n\n\n<p>Por fim, retornamos o novo bloco:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-9\" data-shcb-language-name=\"JavaScript\" data-shcb-language-slug=\"javascript\"><span><code class=\"hljs language-javascript\">    <span class=\"hljs-keyword\">return<\/span> new_header;<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-9\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">JavaScript<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">javascript<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Se o bloco original n\u00e3o for grande o suficiente, simplesmente retornamos o bloco original:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-10\" data-shcb-language-name=\"JavaScript\" data-shcb-language-slug=\"javascript\"><span><code class=\"hljs language-javascript\">  } <span class=\"hljs-keyword\">else<\/span> {\n    <span class=\"hljs-keyword\">return<\/span> header;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-10\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">JavaScript<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">javascript<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\">Atualizando <code>abmalloc()<\/code><\/h3>\n\n\n\n<p>Agora, basta voltar \u00e0 fun\u00e7\u00e3o <code>abmalloc()<\/code> e, no lugar onde encontramos um bloco utiliz\u00e1vel, invocamos <code>header_split()<\/code> para tentar dividi-lo:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-11\" data-shcb-language-name=\"PHP\" data-shcb-language-slug=\"php\"><span><code class=\"hljs language-php\"><span class=\"hljs-keyword\">if<\/span> (header-&gt;available &amp;&amp; (header-&gt;size &gt;= size)) {\n    header = header_split(header, size);\n    header-&gt;available = <span class=\"hljs-keyword\">false<\/span>;\n    <span class=\"hljs-keyword\">return<\/span> header + <span class=\"hljs-number\">1<\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-11\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">PHP<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">php<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Se o bloco puder ser dividido, o novo bloco ser\u00e1 retornado. Caso contr\u00e1rio, o bloco original ser\u00e1 mantido e retornado, como antes.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Nota sobre a Divis\u00e3o de Blocos<\/h3>\n\n\n\n<p>Observe que criamos o novo bloco ao final do bloco original. Poder\u00edamos cri\u00e1-lo no in\u00edcio, mas criar o novo bloco utilizado ao final, o novo bloco livre fica mais pr\u00f3ximo dos blocos mais antigos. Com isso, ele ser\u00e1 encontrado primeiro na pr\u00f3xima vez que <code>abmalloc()<\/code> for invocado.<\/p>\n\n\n\n<p>Dividir blocos de mem\u00f3ria grandes \u00e9 um avan\u00e7o, mas h\u00e1 um problema contr\u00e1rio: blocos de mem\u00f3ria pequenos podem causar fragmenta\u00e7\u00e3o, fazendo com que requisi\u00e7\u00f5es maiores fa\u00e7am o <em>heap<\/em> crescer. Veremos como resolver isso no <a href=\"https:\/\/suspensao.blog.br\/descrenca\/implementando-malloc-e-free-juntando-blocos-pequenos\/\">pr\u00f3ximo <em>post<\/em><\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>When implementing malloc(), it is important to consider the size of the allocated blocks. For example, reusing blocks too big for smaller requests  cause memory waste. How to solve that? Let&#8217;s see on this post of our series on malloc() and free().<\/p>\n","protected":false},"author":2,"featured_media":675,"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":"When implementing malloc(), it is important to consider the size of the allocated blocks. For example, reusing blocks too big for smaller requests  cause memory waste. How to solve that? Let's see on this post of our series on malloc() and free().","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false},"version":2}},"categories":[29,179,10,1],"tags":[79,171,170],"class_list":["post-618","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c","category-libc","category-linux","category-uncategorized","tag-c","tag-gerenciamento-de-memoria","tag-malloc"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/suspensao.blog.br\/descrenca\/wp-content\/uploads\/2024\/10\/Owner_of_general_store_slicing_baloney_Jarreau_Louisiana_October_1938_crop.jpg?fit=1019%2C768&ssl=1","jetpack_shortlink":"https:\/\/wp.me\/p23QLV-9Y","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/618","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=618"}],"version-history":[{"count":5,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/618\/revisions"}],"predecessor-version":[{"id":700,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/posts\/618\/revisions\/700"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/media\/675"}],"wp:attachment":[{"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/media?parent=618"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/categories?post=618"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/suspensao.blog.br\/descrenca\/wp-json\/wp\/v2\/tags?post=618"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}