CatCompiler.dev

The cat compiler.

Hi! I like cats, computers and compilers and I sometimes write blog posts.

I made a real allocator and it was hard

I finally did it! It took blood sweat and tears but it’s here now and I’m chuffed to bits! Please have a look, I’ve got loads of comments and it looks quite clean.

https://github.com/largenumberhere/libc2/blob/main/lib2/malloc.c

It’s not my first allocator but it is my first real one. I have made a bump allocator before which is an allocator in name but a glorified memory leak in practice. They are dump devices that do allow allocation but only ever free if every single allocation is freed. I don’t regret making it but I did find the complexity jump nauseating. Anyhow, I’m getting ahead of myself let’s talk about what I made today.

The libc2 allocator

The libc2 allocator is a part of the libc2 project I’m currently working on. The project goal is to make a simple implementation of libc from scratch. It is progressing well. My most daunting and difficult part of the project so far has been the allocator. The libc2 allocator is a linked-list allocator. This means it uses the data structure linked lists to store its data. In order to understand this allocator, you will need to have a broad understanding of linked lists and memory allocation. Reading up on malloc and free, the heap and linked lists should get you up to speed. This allocator implements malloc, calloc and free in the C programming language.

The linked list used in this allocator differs from conventional linked lists in one major way – the nodes are not allocated in a conventional way (obviously they couldn’t be because it’s the inside of an allocator!). The nodes are more like headers and serve purely to maintain metadata about all the allocations made. The backbone of this allocator is these chubby structures I call ‘AlocMeta’ which consists of a node length, start pointer, pointer to next and a flag to indicate if the node should be ignored. Some of the data is unnecessary or redundant in order to make it more ergonomic to implement.

typedef struct AlocMeta
{
    size_t len;                 
    void* start;                
    bool freed;                 
    struct AlocMeta* next_meta;
} AlocMeta;

Here are some very classy and professional diagrams to shed light on the structure.

Artist’s rendition of the allocator’s heap:

[AlocMeta, region]  (unused) [AlocMeta, region]

The basic linked list shape:

head -> AlocMeta -> AlocMeta -> NULL

So, in order to make the first allocation, the allocator first grabs a page or two of memory from the OS, that is to say a multiple for 4096 bytes. At the start of this region, a node is written and the allocator length is updated. When such memory is freed, the pointer to that node is removed. Any further allocations will reuse the space of any freed nodes when possible. If enough items are freed, pages are given back to the OS. It sounds fairly routine when I explain it like that but it took me hours to write and debug, the biggest difficulty I had was slipping up in some calculations… an off by one error in an allocator will destroy memory and an accidental < instead of a > will screw up all your metadata and by extension will cause an unrelated crash later. Since this is raw memory, there is no type safety, a pointer and an offset are important not to mix up but it’s hard when there’s a arithmetic to do on a dozen variables of type void* and `size_t`, the line between an address and a pointer blurs to a smudge. Another issue I ran into was failing to use the linked list correctly – linked lists are hard to implement because they have some edge cases to consider when traversing like the head node and I often found myself needing to traverse multiple nodes at once leading to several edge cases. An allocator also has the edge case of being possibly un-initialized… my first attempts at such an allocator ended up with walls of guard clauses obscuring all the actual logic…

Previous attempts

My early attempts often went out of bounds triggering an unforgiving segmentation fault in unclear places. Because of the nature of my project as libc implementation, I often could not rely on standard library features like printf because they are incomplete or buggy. “Is it the allocator this time or is it a bug in an unrelated assembly syscall” I’d often find the horror of asking myself. It’s quite a confusing situation where I have to play who dropped their guts in a room of stoics. Eventually I got through with some core dump abuse in my debugger, lots of reworks and hours of free time.

If I would do it again, I would do it very differently. I’d start off with the help of a known good libc, I’d practice dealing with normal linked lists in preparation, I’d pay extreme care to the arithmetic I’m performing and religiously log it. I’d break the code down into several helper functions as I go and I’d ask for help way earlier. With all that said, I’m very pleased with the result it was worth the struggle. I don’t plan to rewrite it again because the result is satisfactory. I am tempted to make plenty of tweaks for performance but I’ll hold myself back because it goes against the ethos of libc2.

Thank you for reading. Feedback is encouraged!

rose

,
, , , , , , , , , , , , , , ,

123 responses to “I made a real allocator and it was hard”

Leave a Reply to Khloe3487 Cancel reply

Your email address will not be published. Required fields are marked *