Implementing malloc() e free() — reducing the heap even more
Tags: c, linux, softwareengineering, malloc
Published: 2024-05-21 19:51:18

---
title: Implementing malloc() e free() — reducing the heap even more
published: true
date: 2024-04-23 14:35:00 UTC
tags: C,Linux,SoftwareEngineering,malloc
cover_image: https://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Madera_Sugar_Pine_Company_fellers_undercut_1911.jpg/1024px-Madera_Sugar_Pine_Company_fellers_undercut_1911.jpg
canonical_url: https://suspensao.blog.br/disbelief/implementing-malloc-e-free-reducing-the-heap-even-more/
series: Implementing malloc() and free()
---

This post is part of a series on implementing the `malloc()` and `free()` functions. In the [previous article](https://dev.to/adambrandizzi/implementing-malloc-and-free-reusing-memory-blocks-2nf9), we learned how to reuse memory blocks. It was a significant advancement, but there’s much more room for improvement.

One example is reducing the size of the heap, as explained in [the first post](https://dev.to/adambrandizzi/implementing-malloc-and-free-first-steps-2e5e-temp-slug-704313). When we free the last memory block, we move the top of the heap to the end of the previous block. However, this previous block might also be free, as well as others. Consider the scenario below:

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

In this case, when we free the block pointed to by `ptr2`, we make `ptr1` the last block. However, `ptr1` is also free, so we could further reduce the heap size.

To achieve this, we’ll iterate over the pointers from the end of the list until there are no more free blocks. If the header of the received pointer points to the last block and the previous block is free, we move the header pointer to it. We repeat this process until we reach an available block whose previous block is in use (or `NULL` if it’s the first block). Then, we execute the heap reduction procedure:

```
if (header == last) {
  while ((header->previous != NULL) && header->previous->available) {
    header = header->previous;
  }
  last = header->previous;
  brk(header);
} else {
```

Now, though, we need to fix a bug in `abfree()`. According to the specification, [the `free()` function should accept a null pointer and do nothing](http://pubs.opengroup.org/onlinepubs/009695399/functions/free.html). However, if `abfree()` receives `NULL`, we will have a segmentation fault! Fortunately, it is easy to fix by adding a check at the beginning of the function:

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

So, here’s our `abfree()` function at the moment:

```
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;
     brk(header);
   } else {
     header->available = true;
   }
 }
```

Reducing the size of the heap is a simple optimization, but there are still challenges ahead. In the next post, we’ll discuss how to avoid reusing very large memory blocks for small requests.

_(This post is a translation of [Implementando malloc() e free() — reduzindo ainda mais o heap](https://suspensao.blog.br/descrenca/implementando-malloc-e-free-reduzindo-ainda-mais-o-heap/), first published in [Suspensão de Descrença](https://suspensao.blog.br/descrenca/).)_