Working smarter instead of harder... in C!
Tags: c, programming, opensource, learning
Published: 2023-08-12 10:54:54

Programmers and laziness go hand-in-hand, which is why C scares a lot of people away. I'm here to show you how to defeat manual memory management instead of the other way around, and hopefully teach you some of the cool things I've learned along the way!

## Why C?

C is that language that everyone knows about, many claim to know, and few *actually know*. Most people "learn" it as part of a course or two in university, and remember it as that language with pointers and manual memory management.

I'm not here to tell you why manual memory management is actually a good thing. I'm not here to tell you why C is great, your language sucks, and you're stupid for not using C for **everything**. Too many people in the C community already do that, and most of them don't even know the language outside of the syntax.

C is a hard language and I would be lying if I said it wasn't. But just like any language, you can learn clever ways to make your life easier while writing C code. If you can get good at being lazy in C (the language that fights laziness at every turn), you will get a lot better at doing the same in other languages.

So let's do exactly that! Let's get rid of most of the overhead of manual memory management and make our code faster with an easy-to-implement and easy-to-use tool.

## The Arena Allocator

To get the C gears turning, recall that we allocate memory with `malloc()` and free/deallocate memory with `free()`, which are provided by the C Standard Library. You specify the amount of bytes you want to use to `malloc()` and assign the result to a pointer variable. You then pass that variable to `free()` and the memory is released.

In other languages this is usually done for you, but in C you need to use these tools each time you need space that you don't know the size of at the time of writing the code. It sounds easy at first, but as projects get larger, these things get hard to keep track of.

As a result, it's easy to get lost and mess up, leading to `segfault`'s and memory leaks that are difficult to track down. The Arena Allocator solves this issue by allocating large chunks of memory all at once, then distributing that memory as needed throughout the program. Finally, the large chunk of memory is `free()`'d all at once. We have effectively turned multiple `malloc`'s and `free()`'s into just a few.

Not only does this make writing C easier for us, it also makes our code faster. `malloc` and `free` are slow, *especially* `free`. And as C programmers, we know that fast is good and slow is bad, right? Right?

## Planning our code style

When it comes to writing code, it is always good to come up with a single style and stick to it. Consistency is key, maintainability is the treasure.

For this project I wanted to create something that was easy for someone else to use, but still powerful. That means we need to accomplish two things:

1. We want our C code to compile on as many compilers and run on as many platforms as possible.

2. We want our tool to be easy to integrate into any project that someone might need it for, regardless of the complexity of the project or expertise of the user.

To accomplish `1`, we will be using ANSI-C, the oldest C standard that is still used in a lot of places. C standards are backwards compatible so our code will work in any codebase using ANSI-C or newer. We will also minimize our dependencies just in case.

To accomplish `2`, we will make our project single-header, meaning all of the code and functionality is contained within a single header file and can be used by just including it. We will make use of the preprocessor to allow for some configuration as well.

## Now for the code

### Foundation

Let's get started on our Arena Allocator and create a header file called `arena.h`. Let's start by setting up our header guards.
```c
#ifndef ARENA_H
#define ARENA_H

/* CODE HERE */

#endif /* !ARENA_H */
```
Now we can lay some foundations by creating our `Arena` data structure and some forward declarations for our functions.
```c
#include <stddef.h> /* For NULL and size_t */
#include <stdlib.h> /* For malloc() and free() */

typedef struct
{
    char *region; /* The memory chunk */
    size_t index; /* How we will divide up memory */
    size_t size;  /* The size of our memory chunk */
} Arena;

/* Creating the arena, all malloc()'s happen here */
Arena* arena_create(size_t size);

/* Allocating memory from the arena */
void* arena_alloc(Arena *arena, size_t size);

/* Reset the arena to "free" without calling free() */
void arena_clear(Arena* arena);

/* Destroy the arena. Actually calls free() */
void arena_destroy(Arena *arena);
```

Disregard the functions; we will go into each of them in depth later. For now, let's focus on the Arena `struct`. It has a `char *region`, which is the pointer we will allocate the large chunks of memory to. I use a `char` pointer because the C standard guarantees a `char` to be one byte in size.

It also has an `index` and a `size`. The `index` will keep track of how much of our `region` we have allocated so far, and `size` will be the capacity of the `region`. Both are `size_t` which is best for representing amounts of memory and locations within memory.

### `arena_create()`

Now let's write the function for creating the arena.

```c
Arena* arena_create(size_t size)
{
    Arena *arena = malloc(sizeof(Arena));
    if(arena == NULL)
    {
        return NULL;
    }
    
    arena->region = malloc(size);
    if(arena->region == NULL)
    {
        return NULL;
    }

    arena->index = 0;
    arena->size = size;
    return arena;
}
```

Our function will allocate memory for an `Arena` (which will be returned to the caller) and its region. If either ends up `NULL` afterward, that means the `malloc()` failed, so we best return `NULL` ourselves to further mimic the behavior of `malloc()`.

The caller will provide a size in bytes for the `region`. The `index` will then be preset to `0` and the `size` will be set accordingly.

### `arena_alloc()`

Now we will implement the allocation part of our allocator.

```c
void* arena_alloc(Arena *arena, size_t size)
{
    if(arena == NULL)
    {
        return NULL;
    }

    if(arena->region == NULL)
    {
        return NULL;
    }

    if(arena->size - arena->index < size)
    {
        return NULL;    
    }

    arena->index += size;
    return arena->region + (arena->index - size);
}
```

Just like before, we check to make sure our `arena` and its `region` are not `NULL`. Then we check if we have enough room in the arena for the allocation. If we don't, it fails, and we return `NULL` again. If we do, we change the `index` in preparation for the next allocation, then return the `region` pointer but with the offset of the original `index`.

Notice how we are returning a `void` pointer. This again copies the behavior of `malloc()` which allows for the returned pointer to be interpreted as any other kind of pointer.

### `arena_clear()`

Clearing the memory is the easiest part.

```c
void arena_clear(Arena* arena)
{
    if(arena == NULL)
    {
        return;
    }
    arena->index = 0;
}
```

We perform a `NULL` check on the passed `arena`, but since we don't use the `region` we don't need to check it. We set the `index` back to `0` which will let us overwrite anything that was already in the arena. This allows us to easily reuse memory without any `free()`'s.

### `arena_destroy()`

Destroying the arena is the second-easiest part. We perform the `NULL` checks on `arena` and `region`, and `free()` them if we can. This will free everything we have allocated within the memory, effectively `free()`ing as many allocations as we want with only two calls.

```c
void arena_destroy(Arena *arena)
{
    if(arena == NULL)
    {
        return;
    }
    
    if(arena->region != NULL)
    {
        free(arena->region);            
    }
    free(arena);
}
```

### Being fancy with the preprocessor

Our arena allocator is pretty much done, now we just need to get it into a working state under our guidelines that we set for ourselves earlier.

The first thing that comes to mind is the `stdlib.h` dependency. We only use it for `malloc()` and `free()`, which many C code bases have their own versions of. We don't want to force them to use `stdlib.h` implementations, especially since those might not always exist.

Let's wrap `malloc` and `free` with some macros and give the programmer the ability to replace them with their own.

```c
#if !defined(ARENA_MALLOC) || !defined(ARENA_FREE)

#include <stdlib.h>
#define ARENA_MALLOC malloc
#define ARENA_FREE free

#endif /* !defined ARENA_MALLOC, ARENA_FREE */
```

We then need to remove the first `#include <stdlib.h>` that we added at the top, as well as replace all `malloc`'s with `ARENA_MALLOC` and all `free`'s with `ARENA_FREE` in our `arena.h` file.

Now by default our implementation will use `stdlib`'s `malloc` and `free`, but someone could specify their own `malloc` and `free` by defining the macros before the include, like this:

```c
#define ARENA_MALLOC my_custom_malloc
#define ARENA_FREE my_custom_free
#include "arena.h"
```

This might be a little unclear to someone rushing to use our library, so we can add a warning if replacements aren't specified as well as a macro that the user can define to suppress said warning.

```c
#if !defined(ARENA_MALLOC) || !defined(ARENA_FREE)

#ifndef ARENA_SUPPRESS_MALLOC_WARN
#warning \
"Using <stdlib.h> malloc and free, because a replacement for one or both \
was not specified before including 'arena.h'."
#endif /* !ARENA_SUPPRESS_MALLOC_WARN */

#include <stdlib.h>
#define ARENA_MALLOC malloc
#define ARENA_FREE free

#endif /* !defined ARENA_MALLOC, ARENA_FREE */
```

Now someone *without* their own custom allocator and deallocator can use our arena allocator by doing the following:

```c
#define ARENA_SUPPRESS_MALLOC_WARN
#include "arena.h"
```

### Finishing touches and final product

Our single-header allocator is almost in a working state. For single-file projects or projects that only use the arena in one file, this would work perfectly. If we wanted to use our arena allocator in multiple files in the project, we would run into linker errors for duplicated functions.

We can resolve this issue with a little more preprocessor finesse. We will introduce one final macro that will wrap around our `ARENA_ALLOC` and `ARENA_FREE` macros, as well as all of our function **definitions** called `ARENA_IMPLEMENTATION`. Our final code should look like this:

```c
#ifndef ARENA_H
#define ARENA_H

#include <stddef.h>

typedef struct
{
    char *region;
    size_t index;
    size_t size;
} Arena;

Arena* arena_create(size_t size);
void* arena_alloc(Arena *arena, size_t size);
void* arena_alloc_aligned(Arena *arena, size_t size, unsigned int alignment);
void arena_clear(Arena* arena);
void arena_destroy(Arena *arena);

#ifdef ARENA_IMPLEMENTATION

#if !defined(ARENA_MALLOC) || !defined(ARENA_FREE)

#ifndef ARENA_SUPPRESS_MALLOC_WARN
#warning \
"Using <stdlib.h> malloc and free, because a replacement for one or both \
was not specified before including 'arena.h'."
#endif /* !ARENA_SUPPRESS_MALLOC_WARN */

#include <stdlib.h>
#define ARENA_MALLOC malloc
#define ARENA_FREE free

#endif /* !defined ARENA_MALLOC, ARENA_FREE */

Arena* arena_create(size_t size)
{
    Arena *arena = ARENA_MALLOC(sizeof(Arena));
    if(arena == NULL)
    {
        return NULL;
    }
    
    arena->region = ARENA_MALLOC(size);
    if(arena->region == NULL)
    {
        return NULL;
    }

    arena->index = 0;
    arena->size = size;
    return arena;
}

void* arena_alloc(Arena *arena, size_t size)
{
    if(arena == NULL)
    {
        return NULL;
    }

    if(arena->region == NULL)
    {
        return NULL;
    }

    if(arena->size - arena->index < size)
    {
        return NULL;    
    }

    arena->index += size;
    return arena->region + (arena->index - size);
}

void arena_clear(Arena* arena)
{
    if(arena == NULL)
    {
        return;
    }
    arena->index = 0;
}

void arena_destroy(Arena *arena)
{
    if(arena == NULL)
    {
        return;
    }
    
    if(arena->region != NULL)
    {
        ARENA_FREE(arena->region);            
    }
    ARENA_FREE(arena);
}

#endif /* ARENA_IMPLEMENTATION */

#endif /* ARENA_H */
```

Now, one file in one translation unit needs to at least have the following macros defined before an include:

```c
#define ARENA_IMPLEMENTATION
#define ARENA_SUPPRESS_MALLOC_WARN
#include "arena.h"
```

And any other files that use our arena allocator in the project only need to include it normally.

```c
#include "arena.h"
```

## Conclusion

Congratulations! You have written an Arena Allocator in C!

That was a bit of a long journey. Don't feel bad if there was a lot you didn't understand, it's really easy to get lost in the terminology. I encourage you to look further into Arena Allocators and the C programming language in general. You could potentially use terms and phrases you didn't understand from this article in your searches or ChatGPT prompts.

The code for this project (with one additional functionality and documentation) can be found [here](https://www.github.com/ccgargantua/arena-allocator). I hope you are inspired to continue learning how to be lazy in C. If not, I hope, at the very least, you learned something.

Thank you for reading.