Implementing malloc() and free() — reusing memory blocks
Tags: c, linux, programming, cpp
Published: 2024-03-13 14:42:06

---
title: Implementing malloc() and free() — reusing memory blocks
published: true
date: 2024-02-06 14:45:00 UTC
tags: C,Linux,programming,cpp
cover_image: https://upload.wikimedia.org/wikipedia/commons/thumb/e/e3/Mastrangelo_-_Reuse_-_2013.jpg/1024px-Mastrangelo_-_Reuse_-_2013.jpg
canonical_url: https://suspensao.blog.br/disbelief/implementing-malloc-and-free-reusing-memory-blocks/
series: Implementing malloc() and free()
---

This post is part of a series on how to implement the `malloc()` and `free()` functions. In [a previous article](https://dev.to/adambrandizzi/implementing-malloc-and-free-first-steps-hkm), we changed our functions to free up some memory blocks. However, this only occurred if the freed blocks were deallocated from newest to oldest.

This wouldn’t make much difference. Dynamically allocated memory rarely behaves like a stack, where the newest block is always deallocated first. The big advantage of dynamic memory allocation, after all, is that it _doesn’t_ work like a stack.

To understand the limitations of our implementation, consider the code below:

```c
void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
abfree(ptr1);
void *ptr3 = abmalloc(8);
```

In the first line, we allocate eight bytes, and free them in the third line. In the last line, we allocate eight bytes again. However, we cannot reuse the freed memory. To truly save memory, we need a more sophisticated solution.

One option is to reuse free blocks. To do this, we add a Boolean field to the block header, called `available`, which will indicate whether the block is free. As a block can only be reused if the memory requested by `abmalloc()` is less than or equal to that available in the block, we also need a field in the header indicating the size of the block, which we will call `size`.

```c
typedef struct Header {
  struct Header *previous;
  size_t size;
  bool available;
} Header;
```

When the block is allocated, the value of the `available` field must be `false` (since the block is not available). We also record the block size in the `size` field:

```c
void *abmalloc(size_t size) {
  Header *header = sbrk(sizeof(Header) + size);
  header->previous = last;
  header->size = size;
  header->available = false;
  last = header;
  return last + 1;
}
```

We have the information in the header but we are not yet reusing deallocated memory. To reuse the available blocks, we need to find them! The algorithm for this is very simple: `abmalloc()` will start iterating over the blocks, starting from the last until reaching the first. Since the `previous` pointer of the first block is always `NULL`, we stop when the pointer is `NULL`:

```c
void *abmalloc(size_t size) {
   Header *header = last;
   while (header != NULL) {
     header = header->previous;
   }
```

In each iteration, we check whether the block is available and has an acceptable size. If in the middle of this process we find an available block greater than or equal to what we need, we got lucky! Just mark the block as unavailable, and return it.

```c
void *abmalloc(size_t size) {
  Header *header = last;
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false; return header + 1;
    }
    header = header->previous;
  }
```

What if we don’t find a block that satisfies these conditions? In this case, the `abmalloc()` function increases the heap, as it did before:

```c
void *abmalloc(size_t size) {
  Header *header = last;
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false;
      return header + 1;
    }
    header = header->previous;
  }
  header = sbrk(sizeof(Header) + size);
  header->previous = last;
  header->size = size;
  header->available = false;
  last = header;
  return last + 1;
}
```

When it comes to deallocating, we have two possible situations. If the block deallocated by `abfree()` is the last one, nothing changes: we move the top of the _heap_ to the beginning of the block, we change the `last` pointer. But what if the block is _not_ on top of the heap? We simply mark it as available, as can be seen in the `else` clause of the function below:

```c
void abfree(void *ptr) {
   Header *header = (Header*) ptr - 1;
   if (header == last) {
     last = header->previous;
     brk(header);
   } else {
     header->available = true;
   }
 }
```

Reusing blocks of memory is a huge advance. However, we can be even more efficient in memory usage. For example, we only reduce the heap size if we deallocate the last block. If there are more unused blocks right before it, we could free them too. We will see how to do this in the next post.

_(This post was originally published in [Implementing malloc() and free() — reusing memory blocks](https://suspensao.blog.br/disbelief/implementing-malloc-and-free-reusing-memory-blocks/) in [Suspension of Disbelief](https://suspensao.blog.br/disbelief).);_