Implementing malloc() and free() — first steps
Tags: c, linux, programming, malloc
Published: 2024-01-16 19:40:18

---
title: Implementing malloc() and free() — first steps
published: true
description: Have you ever wondered how the malloc() and free() functions work? In this series, we will see how they can be implemented, from the most basic and inefficient way possible until... some less basic and inefficient way.
tags: c, Linux, Programming, Malloc
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9y83ehesd9f1dp3tuk3l.png
series: Implementing malloc() and free()
# Use a ratio of 100:42 for best results.
# published_at: 2024-01-16 19:26 +0000
---
Following the [wonderful journey](https://dev.to/adambrandizzi/dont-interpret-me-wrong-improvising-tests-for-an-interpreter-15je) that is reading [*Crafting Interpreters,*](http://craftinginterpreters.com/) I reached the point where we implemented an interpreter in C! As always, [Bob Nystrom](http://stuffwithstuff.com/) mercilessly proposes very interesting challenges that keep us busy for long periods. For instance, [in this chapter](http://craftinginterpreters.com/chunks-of-bytecode.html#challenges), he suggests implementing our own memory allocator, without any real need! Inevitably, I was nerdsniped.

The challenge allows us to allocate a large memory region with an existing `malloc()` function and manage it, but I decided to implement the `malloc()` from scratch. Since I use [Ubuntu](https://www.ubuntu.com/), it was necessary to first understand the memory layout of a process on Linux better.

Consider the diagram below, which represents the memory layout of a process.

!["Layout of memory allocated to a process in Linux: first, we have a block with executable code, then blocks for global and static variables (initialized and uninitialized). This is followed by a large block of unused memory at the beginning of the program , then the arguments and environment variables, and a block reserved for the kernel. The unused block will, over time, be used for local variables (stack) and dynamically allocated blocks (heap)."](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fsnfnscko7grqr5r589t.png)

In the memory allocated for the process, there are various sections. When the program starts its execution, the shaded part is not yet in use. Throughout its execution, the program declares local variables, causing the stack to grow backward.

On the other hand, dynamically allocated memory is obtained from the heap, which grows in the opposite direction. The popular way to expand the heap is by increasing the size of the [data segment](https://en.wikipedia.org/wiki/Data_segment) (i.e., the section that contains global and static variables) with the `sbrk()` system call.

![Diagram representing how srbk() works, by increasing the data segment pointer but returning the old value.](https://cdn-images-1.medium.com/max/800/0*K22ApeEndp1aX-IK)

The above diagram illustrates how this functional system call works. `sbrk()` takes an integer parameter that will be added to the pointer indicating the end of the data segment. After that, `sbrk()` returns the value of the pointer before the increment.

In a way, the behavior of `sbrk()` is already sufficient for memory allocation. Our `malloc()` function can simply invoke `sbrk()` and return to the user the pointer to the beginning of the allocated memory block:

```c
void *abmalloc(size_t size) {
   return sbrk(size);
}
```

In principle, `free()` doesn't need to do anything: since in this implementation, we always use memory from the top of the heap, there is nothing we can do to reuse older memory blocks. In that sense, `free()` can perfectly be a [no-op](https://en.wiktionary.org/wiki/no-op):

```c
void abfree(void *ptr) {
}
```

A useful operation can be done, however, if the block to be freed is the last one allocated. This means it is at the top of the stack, so we just need to move the stack pointer back with the `brk()` system call. This syscall takes a pointer as a parameter and, if this pointer is a "reasonable" value (not null, does not point into the stack, does not point before the heap), it uses the pointer's value as the new top of the heap. The result would be something like this:

```c
void abfree(void *ptr) {
  if (ptr == last_block) {
      brk(last_block);
  }
}
```

This deallocation, however, is practically useless. Consider the example below:

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

With the current version of `abfree()`, we can free the memory pointed to by `ptr1`, but not the one pointed to by `ptr2`. To be able to free `ptr2`, it would be necessary to know that, once `ptr1` has been deallocated, the next last block is `ptr2`. Could we create a `second_last_block` variable? It wouldn't help: we would have the same problem with the penultimate block, and so on.

We need a more powerful data structure here, and that's what we'll see in our next post.

*(This post was originally published as* [*Implementing malloc() and free() --- first steps*](https://suspensao.blog.br/disbelief/implementing-malloc-and-free-1/) *in* [*Suspension of Disbelief*](https://suspensao.blog.br/disbelief/)*.)*