Working smarter instead of harder... in C!

gargantua — Sat, 12 Aug 2023 10:54:54 +0000

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:

We want our C code to compile on as many compilers and run on as many platforms as possible.
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.

#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.

#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.

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.

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.

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.

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.

#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:

#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.

#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:

#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:

#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:

#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.

#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. 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.

Forem: gargantua