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.

Keep your files stored safely and securely with the SanDisk 2TB Extreme Portable SSD. With over 69,505 ratings and an impressive 4.6 out of 5 stars, this product has been purchased over 8K+ times in the past month. At only $129.99, this Amazon’s Choice product is a must-have for secure file storage.

Help keep private content private with the included password protection featuring 256-bit AES hardware encryption. Order now for just $129.99 on Amazon!