Tag: libc

Implementing malloc() and free() — merging small blocks

In the previous post, we learned how to split blocks to make better use of memory. However, this brings a new challenge: memory fragmentation. Smaller blocks can accumulate, forming chains of free blocks that, if unified, would serve larger requests. As blocks are split, they become smaller and smaller, making it difficult to reuse them.

How small blocks can increase memory consumption

Consider the snippet below:

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

In it, we allocated 128 bytes of memory, and then 8 bytes. The memory blocks would have a layout similar to the figure below:

Diagram showing the result of allocation operations - a large, in-use block of memory, followed by a small, in-use block

Then we release the larger block:

Diagram showing the result of the first call to abfree() - a large block of memory free to be reused, followed by a small one still occupied

…and we allocated 8 bytes. Due to the latest changes in the function abmalloc(), these 8 bytes will be extracted from the larger block:

Diagram showing the result of allocation operations after freeing 128 bytes - a large free block of memory, followed by two small blocks also in use

Now, by freeing the newly allocated 8 bytes, we got two free blocks:

Diagram showing a large free block of memory, followed by a small free block and a small block in use

When we allocate a new 128-byte block, we face a problem: neither of the two free blocks is large enough individually, although together they could satisfy the request. As a result, a new block is allocated at the end of the
stack , which continues to grow.

A large free block of memory, a small free block, a small occupied block, and a large occupied block. If the smaller block that is now free had not been extracted from the larger one, we could have taken advantage of the larger free block.

One solution to this problem is to merge adjacent free blocks.

Refactoring for reuse and readability

Before we move on, we will do one more round of refactoring, as there are small but complex pieces of code that will be reused.

First, let’s create a function that, when receiving a header, returns a pointer to the memory area to be returned to the user. So far, we have obtained this result by adding one unit to the header pointer . Let’s encapsulate this logic in a function to simplify and improve code reuse:

void *header_user_area(Header *header) {
  return header + 1;
}

Consequently, in all the places abmalloc()where we previously used the line below…

return header + 1;

…let’s use the new function:

return header_user_area(first);

We also often need the pointer to the memory location following the block. Currently, we calculate this with a somewhat complicated formula: we cast the header pointer to void*, add the size of the structure Headerthe size of the allocated block. This logic can be seen in the function header_split():

Header *new_header = ((void*)header) + sizeof(Header) + header->size;

Let’s create a function to perform this operation, called header_address_after_block():

void *header_address_after_block(Header *header) {
  return ((void*)header) + sizeof(Header) + header->size;
}

Since the function header_user_area() already performs basically the same operation as the first part of the formula, we can use it to simplify header_split():

void *header_address_after_block(Header *header) {
  return header_user_area(header) + header->size;
}

After that, we will replace the formula with our function in
header_split():

Header *new_header = header_address_after_block(header);

Finally, it will be necessary to check whether, given a header, there is a free block before or after it. The expression for this check is intuitive, but extensive. For example, the formula below is used to determine whether there is a free block before it:

(header->previous != NULL) && header->previous->available

To make reading a little easier, let’s put this expression in a function, just like the other one, corresponding to later blocks:

bool header_previous_available(Header *header) {
  return (header->previous != NULL) && header->previous->available;
}

bool header_next_available(Header *header) {
  return (header->next != NULL) && header->next->available;
}

Okay, now we have four new tools that will help us merge available blocks. Let’s get started!

Searching for adjacent free blocks

To join adjacent free memory blocks, we need to check whether the previous or the next block is available at deallocation time. We can do this by creating two variables: one to point to the first free block and the other to the last free block. Initially, both will point to the block that is being deallocated.

Header *header_merge(Header *header) {
  Header *first_available = header;
  Header *last_available = header;

If the block before the current one is free, first_available point to it.

   if (header_previous_available(header)) {
     first_available = header->previous;
   }

Similarly, if the next block is available, last_available it should point to it.

  if (header_next_available(header)) {
    last_available = header->next;
  }

When there are no free blocks

If there are no free blocks either in front of or before the newly deallocated block, there is nothing to merge. In this case, the variables first_available and
last_available will be equal to header, and our function will simply return the pointer to the block that was passed to it.

  if ((first_available == header) && (last_available == header)) {
    return header;
  }

We do not need to check the block before the previous one, or after the next one, and so on. If, in each call of abfree(), we merge the block with any free neighbor, it is impossible to have two consecutive free blocks. Therefore, it is sufficient to check only the immediate neighbors.

Updating size when there are free blocks

If any of the variables first_available or last_available is not equal to header, we will need to merge the blocks. To do this, we need to perform two actions.

First, we need to update the size of the first available block to include the last block. To do this, we get the pointer that points just past the last available block.

  void *end = header_address_after_block(last_available);

The size of the new block will be the difference between this pointer and the user block address:

  size_t size = end - header_user_area(first_available);E

Once we have the size, we just need to update the first available block:

  header_init(first_available, size, true);

Updating merged block pointers

With the block size updated, we need to adjust its pointers. For the backward pointer, it should now point to the block before the first available block:

  Header *previous = first_available->previous;

The next one should be the one after the last available block:

  Header *next = last_available->next;

Once we have these values, we just need to connect them properly using the function header_plug():

  header_plug(first_available, previous, next);

Edge case: the last block

One last thing to keep in mind is that the new block may become the last one. In this case, the block we created should now become the last block.

  if (last_available == last) {
    last = first_available;
  }
  return first_available;
}

Using header_merge() in abfree()

Now that we have a function that joins free blocks, we change it abfree()to call it in the header of the block to be deallocated. Once this is done, we proceed with freeing memory.

  Header *header = (Header*) ptr - 1;
  header = header_merge(header);

  if (header == last) {

Conclusion

Here is our complete abfree() function for now:

void abfree(void *ptr) {
  if (ptr == NULL) {
    return;
  }
  Header *header = (Header*) ptr - 1;

  header = header_merge(header);

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

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header) + size);
  header_init(header, size, available);
  header_plug(header, previous, NULL);
  return header;
}

void header_init( Header *header, size_t size, bool available) {
  header->size = size;
  header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
  header->previous = previous;
  if (previous != NULL) {
    previous->next = header;
  }
  header->next = next;
  if (next != NULL) {
    next->previous = header;
  }
}

void *header_user_area(Header *header) {
  return header + 1;
}

void *header_address_after_block(Header *header) {
  return header_user_area(header) + header->size;
}

bool header_previous_available(Header *header) {
  return (header->previous != NULL) && header->previous->available;
}

bool header_next_available(Header *header) {
  return (header->next != NULL) && header->next->available;
}

Header *header_merge(Header *header) {
  Header *first_available = header;
  Header *last_available = header;

  if (header_previous_available(header)) {
    first_available = header->previous;
  }
  if (header_next_available(header)) {
    last_available = header->next;
  }

  if ((first_available == header) && (last_available == header)) {
    return header;
  }

  void *end = header_address_after_block(last_available);
  size_t size = end - header_user_area(first_available);
  header_init(first_available, size, true);

  Header *previous = first_available->previous;
  Header *next = last_available->next;
  header_plug(first_available, previous, next);

  if (last_available == last) {
    last = first_available;
  }

  return first_available;
}

Header *header_split(Header *header, size_t size) {
  size_t original_size = header->size;
  if (original_size > size + sizeof(Header)) {
    header->size = original_size - size - sizeof(Header);
    Header *new_header = header_address_after_block(header);
    header_init(new_header, size, true);
    header_plug(new_header, header, header->next);
    if (header == last) {
      last = new_header;
    }
    return new_header;
  } else {
    return header;
  }
}

With the changes made in this and the last post, the size of free blocks is no longer an aggravating factor in memory consumption, and our function malloc() is getting closer to being ready. However, there is one last problem to be solved: the alignment of memory blocks. We will examine this in the next
post .

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.)