It occurs to me that I have yet to understand how to implement a memory allocator. Four years ago I attempted at a simple garbage collector. That approach was flawed; one of the reason why is the fact that I used malloc and free - they don't come from thin air, they still need something else to back them up, and as someone that tries to rely on less things as possible, this is unacceptable. While I did say I'm planning to quit computer science, I pretty much don't enjoy not knowing things, so we are here.

One day after a shower I've come up with the simplest technique I could think of. Immediately I noticed a few difference:

• Unlike allocating an object (which could made to come with a metadata header), you need to directly return the block of memory that's free for your caller to write on.
• For the same reason, you can't easily move allocated memory blocks around: the caller only knows the address you've given to them, if you move the block somewhere else the caller would have no way to tell unless they somehow rely on the behaviour of the memory allocator, which is a thing that shouldn't have happened.

The latter point means that there is no easy way to stop fragmentation.

The idea is very simple - for any continuous span of memory one turns it into a linked list. In the beginning there would be one single node with all the memory. Each allocation request splits what is originally one node into two. Freeing a block of memory is done by simply marking the node as free. Freed nodes are coalesced into one single node during allocation whenever possible.

The code of the idea is very simple. I didn't try to do a very good job, but it's still a merely 50-something lines of C. (df stands for "dumbfvck" by the way, because I thought this method is ridiculously naïve.)

void* dfalloc_backing_mem;
size_t dfalloc_mem_size;
enum {
    DFALLOC_FREE,
    DFALLOC_USED,
};
typedef struct dfalloc_st {
    uint_fast64_t type;
    size_t size;
    struct dfalloc_st* next;
} dfalloc_st;
void df_init(void* backing_mem, size_t size) {
    dfalloc_backing_mem = backing_mem;
    dfalloc_mem_size = size;
    ((dfalloc_st*)backing_mem)->type = DFALLOC_FREE;
    ((dfalloc_st*)backing_mem)->size = dfalloc_mem_size-(sizeof(dfalloc_st));
    ((dfalloc_st*)backing_mem)->next = NULL;
}
void* df_malloc(size_t size) {
    dfalloc_st* subj = ((dfalloc_st*)dfalloc_backing_mem);
    for (;;) {
        if (subj == NULL) {
            return NULL;
        }
        // compress multiple empty node if there is any
        if (subj->type == DFALLOC_FREE) {
            dfalloc_st* nxt;
            for (;;) {
                nxt = subj->next;
                if (nxt == NULL) { break; }
                if (nxt->type == DFALLOC_USED) { break; }
                subj->size += nxt->size + sizeof(dfalloc_st);
                subj->next = nxt->next;
            }
        }
        if (subj->type == DFALLOC_FREE && subj->size >= size) {
            if (subj->size - size <= sizeof(dfalloc_st)) {
                subj->type = DFALLOC_USED;
            } else {
                dfalloc_st* new_node = (dfalloc_st*)(((void*)subj)+sizeof(dfalloc_st)+size);
                new_node->type = DFALLOC_FREE;
                new_node->size = subj->size - size - sizeof(dfalloc_st);
                new_node->next = subj->next;
                subj->type = DFALLOC_USED;
                subj->size = size;
                subj->next = new_node;
            }
            return ((void*)subj)+sizeof(dfalloc_st);
        }
        subj = subj->next;
    }
}
void df_free(void* p) {
    dfalloc_st* subj = (dfalloc_st*)(p-sizeof(dfalloc_st));
    subj->type = DFALLOC_FREE;
}

One would suspect that the use of uint_fast64_t seems a bit wasteful when there are only two possible times and a simple _Bool would be more than plenty; this concern is valid but (1) it's easy to change it to something else and (2) due to memory alignment you'd still be using more than one byte for that _Bool field if you don't specify anything.

(We'll come back to other kind of allocators later…)

Back

Last update: 2025.8.22