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

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:

Now, we release the first and third blocks…

abfree(ptr1);
abfree(ptr3);

…resulting in the following structure:

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:

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:

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…

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

This time, the first block will be reused:

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:

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 firstit is no longer NULL, there are already allocated blocks, so we will start searching for a reusable block. We will continue using the variable headeras 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 abfree()

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

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.