Month: September 2024

Implementing malloc() and free() — old memory reused first

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.

In the previous post in this series on implementing malloc()and free(), 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’s break it down.

Heap reduction by reusing recent blocks

Consider the following scenario. First, we allocate four memory blocks:

void *ptr1 = abmalloc(8); 
void *ptr2 = abmalloc(8); 
void *ptr3 = abmalloc(8); 
void *ptr4 = abmalloc(8);

The memory structure can be visualized like this:

Linked list with four nodes. Newer nodes point to older ones. All nodes are in use, so they are all labeled In use.

Now, we release the first and third blocks…

abfree(ptr1); 
abfree(ptr3);

…resulting in the following structure:

Linked list with four nodes. The newest nodes point to the oldest ones. The second and fourth nodes in the list (i.e. the second newest and oldest of all) have been freed with free(), so they are labeled with the word Available.

Then we allocate another block of the same size:

void *ptr5 = abmalloc(8);

As the function abmalloc() starts searching for the most recent free block, it reuses the block at the top. If we now free the last block:

Linked list with four nodes. Newer nodes point to older ones. Now only the last node is free and labeled with the word Free

If we now release the last block…

abfree(ptr4);

…we can reduce the heap size by just one 8-byte block, since the previous block is no longer free:

Linked list with three nodes. Newer nodes point to older ones. The last node is free and labeled with the word Free.

Reuse of old blocks

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…

Linked list with four nodes. Older nodes point to newer ones. All nodes are in use and labeled with the word In use.

…and again we free the first and third memory blocks:

Linked list with four nodes. Older nodes point to newer ones. The first and third nodes (i.e., the oldest and the third oldest/second newest) have been deallocated and are labeled with the In use

This time, the first block will be reused:

Linked list with four nodes. Older nodes point to newer ones. The third node (i.e., the oldest and third oldest/second newest) has been deallocated. Hence, it is labeled with the word Free

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:

Linked list with two nodes. We have freed two newer nodes, and since we reused the oldest, we have less nodes than the original case now.

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.

Implementing preference for old blocks

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:

typedef struct Header { 
  struct Header *previous, *next; 
  size_t size; 
  bool available; 
} Header; 

Header *first = NULL; 
Header *last = NULL;

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 nextwith NULL):

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; 
}

With this new function, we can simplify the logic within abmalloc():

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; 
}

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:

void *abmalloc(size_t size) { 
  if (size == 0) { 
    return NULL; 
  } 
  if (first == NULL) { 
    first = last = header_new(NULL, size, false); 
    return first + 1; 
  }

If first is no longer NULL, there are already allocated blocks, so we will start searching for a reusable block. We will continue using the variable header as an iterator, but instead of starting with the most recent block, the search will start from the oldest:

  Header *header = first;

At each iteration, we will advance to the next block in the sequence, instead of going backwards to the previous block:

  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header + 1; 
    } 
    header = header->next; 
  }

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:

  last = header_new(last, size, false);

Now, we need to adjust the block that was the last one (after the allocation, the second to last). It pointed to NULL, but now it should point to the new block. To do this, we set the previous block’s next field to the new last block:

  last->previous->next = last; 
  return last + 1; 
}

Adjustments in the abfree() function

The function abfree() 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:

    last = header->previous; 
    brk(header)

Here, the pointer header references the last non-null block available on the stack. We have two possible scenarios:

  1. the current block has a previous block, which will become the new last block. In this case, we should set the pointer nextof this block to NULL.
  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 to NULL, indicating that there are no more allocated blocks.

Here is how we implement it:

  last = header->previous; 
  if (last != NULL) { 
    last->next = NULL; 
  } else { 
    first = NULL; 
  } 
  brk(header);

Conclusion

Our functions abmalloc() and abfree() now look like this:

        typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;

Header *first = NULL;
Header *last = NULL;

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;
}

void *abmalloc(size_t size) {
  if (size == 0) {
    return NULL;
  }
  if (first == NULL) {
    first = last = header_new(NULL, size, false);
    return first + 1;
  }
  Header *header = first;
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false;
      return header + 1;
    }
    header = header->next;
  }
  last = header_new(last, size, false);
  last->previous->next = last;
  return last + 1;
}

void abfree(void *ptr) {
  if (ptr == NULL) {
   return;
  }
  Header *header = (Header*) ptr - 1;
  if (header == last) {
    while ((header->previous != NULL) && header->previous->available) {
      header = header->previous;
    }
    last = header->previous;
    if (last != NULL) {
      last->next = NULL;
    } else {
      first = NULL;
    }
    brk(header);
  } else {
   header->available = true;
  }
 }Code language:  PHP  ( php )

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()reuse a block of, say, 1024 bytes. There is clearly a waste.

We will see how to solve this in the next post.

(This post is a translation of Implementando malloc() e free() — memória antiga tem preferência, first published in Suspensão de Descrença.)