Writing a simple pool allocator in C

In our simple implementation, we will declare a Chunk type with a fixed size. In a more general implementation, we would use a chunk size specified by the programmer at runtime, but that method adds a lot of casts, and I think it would make this article more confusing.

First, let’s have a look at the definition of Chunk.

#define CHUNK_SZ 64

typedef union Chunk Chunk;
union Chunk {
    Chunk* next;
    char arr[CHUNK_SZ];
};

Notice how we are typedef’ing a union, not a struct.

If you are not familiar with C union’s, they are syntactically similar to struct’s, but they can be used to define variables that may hold (at different times) objects of different types and sizes; as opposed to structures, which let the programmer group different data types as a single record. Unions essentially let the programmer access the data in a single area of storage as if it were storing one of many data types at a given time. When you access a member of a union variable (e.g. my_chunk.next or my_chunk.arr), the compiler is responsible for accessing the union variable as if it were the specified member type (in that example, either a pointer or an array of CHUNK_SZ characters, never both).

In this case, using a union is convenient because it lets us “interpret” the Chunk as a pointer to another Chunk depending on the context, while also specifying the real size of the Chunk (i.e. CHUNK_SZ). Also note that the size of a union is the size of the biggest possible member (in a 64-bit computer, sizeof(Chunk*) is 8 bytes, and since the arr member is 64 bytes, that will be the size of the Chunk union).

However, it’s still not clear why we would need to interpret the Chunk as a pointer depending on the context. First, we need to understand that there will be two (implicit) types of chunks:

1. Free chunks: They are not in use by the program. They will use the next pointer.
2. Non-free chunks: They have been allocated, so we assume they contain arbitrary user data. Specifically, in this implementation, each chunk can contain (at most) CHUNK_SZ bytes of data.

As mentioned, these types are “implicit”. This means that there isn’t any flags variable that lets us know whether a specified chunk is free; instead, we know that a chunk is free because it will be inside a linked list of free chunks. When we initialize the pool, since all chunks are free, we will use the Chunk.next pointer to link each chunk to its adjacent one, like this:

The gray area represents the rest of the union that is not used when accessing Chunk.next, and the incomplete red arrow represents a NULL pointer. The creation of this linked list, along with its advantages, will be explained when creating the pool below.

We will also declare a Pool structure, which simply contains:

1. A pointer to the first element of the linked list of free chunks, which will be used when the user allocates a chunk.
2. A pointer to the first element of the chunk array, which will be used when closing the whole pool.

typedef struct Pool Pool;
struct Pool {
    Chunk* free_chunk;
    Chunk* chunk_arr;
};

Again, other members such as the chunks size might be necessary depending on the implementation; in this case it’s known at compile time.

We will define a function for creating a Pool with an arbitrary number of chunks.

Pool* pool_new(size_t pool_sz) {
    Pool* pool = malloc(sizeof(Pool));
    if (pool == NULL)
        return NULL;

    pool->chunk_arr = pool->free_chunk = malloc(pool_sz * sizeof(Chunk));
    if (pool->chunk_arr == NULL) {
        free(pool);
        return NULL;
    }

    for (size_t i = 0; i < pool_sz - 1; i++)
        pool->chunk_arr[i].next = &pool->chunk_arr[i + 1];
    pool->chunk_arr[pool_sz - 1].next = NULL;

    return pool;
}

Here’s a brief explanation of each step:

1. We allocate the Pool structure that will be returned, using malloc².
2. We allocate the pool itself, that is, the array of Chunk unions. We initialize both chunk_arr and free_chunk pointers to the same address, since all chunks will be free by default.
3. We build the linked list of free chunks. We set the .next member of the Chunk union to the address of the adjacent chunk³, except for the last free chunk, which will point to NULL.

This is how the pool looks after being returned from pool_new:

And this is how the pool looks after the user has allocated two chunks. This process will be explained below, but perhaps you are starting to realize the advantages of this method:

Since this implementation doesn’t support pool resizing, the only O(n) algorithm occurs when creating the pool itself, since we need to iterate each chunk to build the linked list described above. The chunk allocation process, on the other hand, has O(1) complexity, since we always have a free chunk waiting for us at Pool.free_chunk. Freeing a chunk is also done in constant time, since we just have to prepend an element to this linked list.

Now that the pool has a pointer to a linked list of free chunks, when the user requests an allocation for a chunk, we just have to:

1. Ensure that we haven’t reached the end of the list, that is, ensure the Pool.free_chunk pointer is not NULL.
2. The first element of this “free chunks” list will be returned. Before that, remove it from the list by setting the start of the list (i.e. Pool.free_chunk) to what used to be the second element (i.e. Pool.free_chunk.next).

void* pool_alloc(Pool* pool) {
    if (pool == NULL || pool->free_chunk == NULL)
        return NULL;

    Chunk* result    = pool->free_chunk;
    pool->free_chunk = pool->free_chunk->next;
    return result;
}

Now the user can safely overwrite the contents of the pointer returned by pool_alloc, and it will be essentially setting the arr member of the Chunk union. This is fine, since that chunk is no longer part of our “free chunks” list.

Just to emphasize once again, we are not iterating anything, so this process is constant. Allocating chunks of arbitrary size on constant time obviously has great advantages, specially when we have to allocate and free many times per second (e.g. many entities in each tick of a simulation).

Freeing chunks is pretty straight-forward, and if you understood the previous sections, I recommend you try to write your own function.

The freeing process simply consists of adding (prepending) a chunk back into the linked list of free chunks. As you can probably tell, this is also a constant process.

void pool_free(Pool* pool, void* ptr) {
    if (pool == NULL || ptr == NULL)
        return;

    Chunk* freed     = ptr;
    freed->next      = pool->free_chunk;
    pool->free_chunk = freed;
}

For example, following the previous figure, this would be the layout after the user frees the first block of memory.

Notice how, unlike with arena allocators, we don’t have to free in the same order that we allocated.

Finally, once the user is done with the pool itself, it should be able to free it to the system. This is also pretty intuitive in this implementation, but it will get a bit trickier below.

void pool_close(Pool* pool) {
    if (pool == NULL)
        return;

    free(pool->chunk_arr);
    free(pool);
}

For keeping track of these pointers, we will create another linked list of “array starts”. We declare an ArrayStart structure which will contain the address of the next element in the linked list (or NULL), along with the pointer to the start of each array.

typedef struct ArrayStart ArrayStart;
struct ArrayStart {
    Chunk* arr;
    ArrayStart* next;
};

Now, instead of storing a single Chunk* in the Pool structure, we store a pointer to the linked list of array starts.

struct Pool {
    Chunk* free_chunk;
    ArrayStart* array_starts; /* Updated */
};

This takes a bit more space in memory, but it’s worth it. Even if we don’t expand the pool, only the size 2 more pointers would be needed: one that points to the ArrayStart structure itself, and the (unused) .next member.

The pool_new and pool_free functions need to be modified according to our new ArrayStart structure.

When creating the pool, instead of storing the base address of the chunk array in pool->chunk_arr, we will have to allocate an ArrayStart structure and write it there.

Pool* pool_new(size_t pool_sz) {
    Pool* pool = malloc(sizeof(Pool));
    if (pool == NULL)
        return NULL;

    Chunk* arr = pool->free_chunk = malloc(pool_sz * sizeof(Chunk));
    if (arr == NULL) {
        free(pool);
        return NULL;
    }

    for (size_t i = 0; i < pool_sz - 1; i++)
        arr[i].next = &arr[i + 1];
    arr[pool_sz - 1].next = NULL;

    /* Added */
    pool->array_starts = malloc(sizeof(ArrayStart));
    if (pool->array_starts == NULL) {
        free(arr);
        free(pool);
        return NULL;
    }

    pool->array_starts->next = NULL;
    pool->array_starts->arr  = arr;

    return pool;
}

When closing the pool, we will also need to traverse this array_starts linked list, freeing each chunk array and each ArrayStart structure in the list.

void pool_close(Pool* pool) {
    if (pool == NULL)
        return;

    ArrayStart* array_start = pool->array_starts;
    while (array_start != NULL) {
        ArrayStart* next = array_start->next;
        free(array_start->arr);
        free(array_start);
        array_start = next;
    }

    free(pool);
}

Now that we have a way of storing the start addresses of an indefinite number of chunk arrays, we can implement the expansion method shown in the previous figure. The expansion process is the following:

1. Allocate the array of extra chunks that we are trying to add to the pool.
2. Link the new chunks together, just like we did when creating the pool.
3. Prepend the array of extra chunks to the “free chunks” list, just like we did when freeing chunks.
4. Allocate a new ArrayStart structure, and store the start of the new chunk array in it.
5. Prepend this new ArrayStart structure to the linked list of “array starts”, stored inside the Pool structure.

And this is the code corresponding to the previous steps.

bool pool_expand(Pool* pool, size_t extra_sz) {
    if (pool == NULL || extra_sz == 0)
        return false;

    /* Step 1 */
    Chunk* extra_arr = malloc(extra_sz * sizeof(Chunk));
    if (extra_arr == NULL)
        return false;

    /* Step 2 */
    for (size_t i = 0; i < extra_sz - 1; i++)
        extra_arr[i].next = &extra_arr[i + 1];

    /* Step 3 */
    extra_arr[extra_sz - 1].next = pool->free_chunk;
    pool->free_chunk             = extra_arr;

    /* Step 4 */
    ArrayStart* array_start = malloc(sizeof(ArrayStart));
    if (array_start == NULL) {
        free(extra_arr);
        return false;
    }

    /* Step 5 */
    array_start->arr   = extra_arr;
    array_start->next  = pool->array_starts;
    pool->array_starts = array_start;

    return true;
}

Just like in the previous figure, the green and blue regions represent arrays allocated independently, but their respective ArrayStart structures are also included in the diagram.

Naturally, this second implementation is able to allocate and free chunks with the same O(1) efficiency. The memory impact is slightly bigger, but it’s probably worth it if you ever want to resize a pool.