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:

Then we release the larger block:

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

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

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.

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 .