Implementing malloc() and free() — adding metadata to the memory blocks
Tags: c, linux, programming, cpp
Published: 2024-02-14 10:37:30

---
title: Implementing malloc() and free() — adding metadata to the memory blocks
published: true
date: 2024-01-30 17:15:00 UTC
tags: C,Linux,Programming,cpp
cover_image: https://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Metal_chain_%28Unsplash%29.jpg/1024px-Metal_chain_%28Unsplash%29.jpg
canonical_url: https://suspensao.blog.br/disbelief/implementing-malloc-and-free-adding-metadata-to-the-memory-blocks/
series: Implementing malloc() and free()
---

This post is part of a series on implementing the `malloc()` and `free()` functions. Previously, [we implemented a rather simplistic approach](https://dev.to/adambrandizzi/implementing-malloc-and-free-first-steps-hkm) that almost doesn’t free any memory: a pointer points to the last allocated block, enabling `free()` to deallocate it, but only it.

A better option is to make the last block point to the second-to-last, the second-to-last block to the third-to-last, and so on, forming a [linked list](https://en.wikipedia.org/wiki/Linked_list). To achieve this, we create a struct that will serve as the header of the blocks, containing a pointer to the previous block:

```c
typedef struct Header {
  struct Header *previous;
} Header;
```

Additionally, the pointer to the last block, which used to be `void*`, is now of type `Header*`:

```c
Header *last = NULL;
```

To use these headers, `abmalloc()` reserves enough memory to store both the header and the requested size:

```c
void *abmalloc(size_t size) {
  Header *header = sbrk(sizeof(Header) + size);
```

In this way, we use the beginning of the block to store necessary information, such as a pointer to the last allocated block before the new one:

```c
  header->previous = last;
```

Then, we update `last` to point to the new block:

```c
  last = header;
```

Finally, we return a pointer to the memory that the user can use. Since `header` points to the metadata, we cannot simply return it. Otherwise, all header information would be overwritten when the user used the pointer! Instead, we return a pointer to just after the header. This pointer is easy to calculate: it is the memory address of the header _plus_ the size of the header:

```c
  return header + 1;
}
```

Note how we increment the `header` pointer by 1. Since the pointer type is `Header*`, the increment is actually the number of bytes of the `Header` struct, not just one byte. The type of the pointer is very relevant in [pointer arithmetic](https://www-ime-usp-br.translate.goog/~pf/algoritmos/aulas/pont.html?_x_tr_sl=pt&_x_tr_tl=en&_x_tr_hl=pt-BR&_x_tr_pto=wapp#array).

Now that our memory blocks have metadata at the beginning, we need to take this into account when deallocating. `free()` receives a pointer not to the start of the block but to the memory made available to the user. Therefore, we need to find the start of the block from the pointer the user passed. Nothing that a little pointer arithmetic can’t solve:

```c
void abfree(void *ptr) {
  Header *header = (Header*) ptr - 1;
```

If `header` points to the last allocated block, the previous block will become the last. In this case, we can return memory from the heap to the operating system through `brk()`:

```c
  if (header == last) {
    last = header->previous;
    brk(header);
  }
}
```

Here are our new `malloc()` and `free()` functions:

```c
typedef struct Header {
   struct Header *previous;
 } Header;

 Header *last = NULL;

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

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

`abmalloc()` and `abfree()` may be slightly more memory-efficient now, but not by much. Dynamically allocated memory rarely behaves like a stack, where the oldest block is always deallocated first. In the next post, we will see how to use the memory of older blocks that are no longer in use.


_(This post was originally published as  [Implementing malloc() and free() — adding metadata to the memory blocks](https://suspensao.blog.br/disbelief/implementing-malloc-and-free-adding-metadata-to-the-memory-blocks/) in [*Suspension of Disbelief*](https://suspensao.blog.br/disbelief/).)_