{"id":246,"date":"2024-09-24T11:59:00","date_gmt":"2024-09-24T14:59:00","guid":{"rendered":"https:\/\/suspensao.blog.br\/disbelief\/?p=246"},"modified":"2024-10-01T01:17:16","modified_gmt":"2024-10-01T04:17:16","slug":"implementing-malloc-and-free-old-memory-reused-first","status":"publish","type":"post","link":"https:\/\/suspensao.blog.br\/disbelief\/implementing-malloc-and-free-old-memory-reused-first\/","title":{"rendered":"Implementing malloc() and free() \u2014 old memory reused first"},"content":{"rendered":"\n

In the previous post<\/em><\/a> in this series on implementing malloc()<\/code>and free()<\/code>, we showed how it is possible to reuse memory blocks and reduce the heap by freeing newer blocks. However, the current function introduces a subtle issue: it prioritizes reusing newer blocks, which can lead to increased memory consumption over time. Why does this happen? Let\u2019s break it down.<\/p>\n\n\n\n

Heap reduction by reusing recent blocks<\/h3>\n\n\n\n

Consider the following scenario. First, we allocate four memory blocks:<\/p>\n\n\n\n

void *ptr1 = abmalloc(8); 
void *ptr2 = abmalloc(8); 
void *ptr3 = abmalloc(8); 
void *ptr4 = abmalloc(8);<\/code><\/pre>\n\n\n\n
The memory structure can be visualized like this:<\/p>\n\n\n\n
\"Linked<\/figure>\n\n\n\n
Now, we release the first and third blocks\u2026<\/p>\n\n\n\n
abfree(ptr1); 
abfree(ptr3);<\/code><\/pre>\n\n\n\n
\u2026resulting in the following structure:<\/p>\n\n\n\n
\"Linked<\/figure>\n\n\n\n
Then we allocate another block of the same size:<\/p>\n\n\n\n
void *ptr5 = abmalloc(8);<\/code><\/pre>\n\n\n\n
As the function abmalloc()<\/code> starts searching for the most recent free block, it reuses the block at the top. If we now free the last block:<\/p>\n\n\n\n
\"Linked<\/figure>\n\n\n\n
If we now release the last block\u2026<\/p>\n\n\n\n
abfree(ptr4);<\/code><\/pre>\n\n\n\n
\u2026we can reduce the heap size by just one 8-byte block, since the previous block is no longer free:<\/p>\n\n\n\n
\"Linked<\/figure>\n\n\n\n
Reuse of old blocks<\/h3>\n\n\n\n
Now, imagine the same scenario, but with one modification: our function starts searching for free blocks from the oldest one. The initial structure will be the same\u2026<\/p>\n\n\n\n
\"Linked<\/figure>\n\n\n\n
\u2026and again we free the first and third memory blocks:<\/p>\n\n\n\n
\"Linked<\/figure>\n\n\n\n
This time, the first block will be reused:<\/p>\n\n\n\n
\"Linked<\/figure>\n\n\n\n
Now, when we free the last block, we will have two free blocks at the top, allowing us to reduce the heap by two 8-byte blocks:<\/p>\n\n\n\n
\"Linked<\/figure>\n\n\n\n
This example illustrates how, by giving preference to newer blocks, we end up accumulating old unused blocks, wasting memory and leading to unnecessary heap growth. The solution is to modify the search strategy, prioritizing the reuse of older blocks.<\/p>\n\n\n\n
Implementing preference for old blocks<\/h3>\n\n\n\n
To solve this problem, we will start by adding a pointer to the next block in the header. We will also create a global pointer to the first block, so we can start the search from it:<\/p>\n\n\n\n
typedef struct Header { 
  struct Header *previous, *next; 
  size_t size; 
  bool available; 
} Header; 

Header *first = NULL; 
Header *last = NULL;<\/code><\/pre>\n\n\n\n
We will create memory blocks with headers in two different situations, so let’s make a small refactoring: we will extract this logic to a helper function that allocates and initializes the header (including setting the field next<\/code>with 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; 
}<\/code><\/pre>\n\n\n\n
With this new function, we can simplify the logic within 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; 
}<\/code><\/pre>\n\n\n\n
Now we have access to the first and last blocks, and given a block, we can find out the previous and next ones. We also know that when the pointer to the first block is null, no blocks have been allocated yet. So in this case, we will allocate the block immediately, and initialize both first and 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; 
  }<\/code><\/pre>\n\n\n\n
If first<\/code> is no longer NULL<\/code>, there are already allocated blocks, so we will start searching for a reusable block. We will continue using the variable header<\/code> as an iterator, but instead of starting with the most recent block, the search will start from the oldest:<\/p>\n\n\n\n
  Header *header = first;<\/code><\/pre>\n\n\n\n
At each iteration, we will advance to the next block in the sequence, instead of going backwards to the previous block:<\/p>\n\n\n\n
  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header + 1; 
    } 
    header = header->next; 
  }<\/code><\/pre>\n\n\n\n
The logic remains the same: if we find an available block of sufficient size, it is returned. Otherwise, if no reusable block is found after we traverse the list, a new block is allocated:<\/p>\n\n\n\n
  last = header_new(last, size, false);<\/code><\/pre>\n\n\n\n
Now, we need to adjust the block that was the last one (after the allocation, the second to last). It pointed to NULL<\/code>, but now it should point to the new block. To do this, we set the previous block\u2019s next<\/code> field to the new last block:<\/p>\n\n\n\n
  last->previous->next = last; 
  return last + 1; 
}<\/code><\/pre>\n\n\n\n
Adjustments in the abfree()<\/code> function<\/h3>\n\n\n\n
The function abfree()<\/code> basically maintains the same structure, but now we must handle some edge cases. When we free blocks at the top of the heap, a new block becomes the last one, as we already do in this snippet:<\/p>\n\n\n\n
    last = header->previous; 
    brk(header)<\/code><\/pre>\n\n\n\n
Here, the pointer header<\/code> references the last non-null block available on the stack. We have two possible scenarios:<\/p>\n\n\n\n
    \n
  1. the current block has a previous block, which will become the new last block. In this case, we should set the pointer next<\/code>of this block to NULL<\/code>. <\/li>\n\n\n\n
  2. the current block does not have a previous block (i.e., it is the first and oldest block). When it is freed, the stack is empty. In this case, instead of trying to update a field of a non-existent block, we simply set the variable first<\/code> to NULL<\/code>, indicating that there are no more allocated blocks.<\/li>\n<\/ol>\n\n\n\n
    Here is how we implement it:<\/p>\n\n\n\n
      last = header->previous; 
      if (last != NULL) { 
        last->next = NULL; 
      } else { 
        first = NULL; 
      } 
      brk(header);<\/code><\/pre>\n\n\n\n
    Conclusion<\/h3>\n\n\n\n
    Our functions abmalloc()<\/code> and abfree()<\/code> now look like this:<\/p>\n\n\n\n
            typedef struct Header {\n  struct Header *previous, *next;\n  size_t size;\n  bool available;\n} Header;\n\nHeader *first = NULL;\nHeader *last = NULL;\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;\n  header->size = size;\n  header->available = false;\n  return header;\n}\n\nvoid *abmalloc(size_t size) {\n  if (size == 0) {\n    return NULL;\n  }\n  if (first == NULL) {\n    first = last = header_new(NULL, size, false);\n    return first + 1;\n  }\n  Header *header = first;\n  while (header != NULL) {\n    if (header->available && (header->size >= size)) {\n      header->available = false;\n      return header + 1;\n    }\n    header = header->next;\n  }\n  last = header_new(last, size, false);\n  last->previous->next = last;\n  return last + 1;\n}\n\nvoid abfree(void *ptr) {\n  if (ptr == NULL) {\n   return;\n  }\n  Header *header = (Header*) ptr - 1;\n  if (header == last) {\n    while ((header->previous != NULL) && header->previous->available) {\n      header = header->previous;\n    }\n    last = header->previous;\n    if (last != NULL) {\n      last->next = NULL;\n    } else {\n      first = NULL;\n    }\n    brk(header);\n  } else {\n   header->available = true;\n  }\n }<\/code>Code language:  PHP  ( php )<\/small><\/code><\/pre>\n\n\n\n
    This change allows us to save considerably more memory. There are, however, still problems to solve. For example, consider the following scenario: we request the allocation of a memory block of 8 bytes, and abmalloc()<\/code>reuse a block of, say, 1024 bytes. There is clearly a waste.<\/p>\n\n\n\n
    We will see how to solve this in the next post.<\/p>\n\n\n\n
    (This post is a translation of <\/em>Implementando malloc() e free() \u2014 mem\u00f3ria antiga tem prefer\u00eancia<\/a>, first published in Suspens\u00e3o de Descren\u00e7a<\/a>.)<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"
    Suppose you have a linked list of blocks of memory that can be reused. Should you look for one to reuse from the beginning or the end? In this post, we have the answer, explain why and show how to implement it.<\/p>\n","protected":false},"author":1,"featured_media":264,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_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":"Suppose you have a linked list of blocks of memory that can be reused. Should you look for one to reuse from the beginning or the end? In this post, we have the answer, explain why and show how to implement it.","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[75,76],"tags":[77,86,82,80,78,47],"class_list":["post-246","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c","category-linux","tag-c","tag-libc","tag-linux","tag-malloc","tag-memory-management","tag-software-development"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/suspensao.blog.br\/disbelief\/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-1.jpg?fit=1077%2C480&ssl=1","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9Ru6q-3Y","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/suspensao.blog.br\/disbelief\/wp-json\/wp\/v2\/posts\/246","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/suspensao.blog.br\/disbelief\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/suspensao.blog.br\/disbelief\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/suspensao.blog.br\/disbelief\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/suspensao.blog.br\/disbelief\/wp-json\/wp\/v2\/comments?post=246"}],"version-history":[{"count":12,"href":"https:\/\/suspensao.blog.br\/disbelief\/wp-json\/wp\/v2\/posts\/246\/revisions"}],"predecessor-version":[{"id":276,"href":"https:\/\/suspensao.blog.br\/disbelief\/wp-json\/wp\/v2\/posts\/246\/revisions\/276"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/suspensao.blog.br\/disbelief\/wp-json\/wp\/v2\/media\/264"}],"wp:attachment":[{"href":"https:\/\/suspensao.blog.br\/disbelief\/wp-json\/wp\/v2\/media?parent=246"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/suspensao.blog.br\/disbelief\/wp-json\/wp\/v2\/categories?post=246"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/suspensao.blog.br\/disbelief\/wp-json\/wp\/v2\/tags?post=246"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}