Page-Based-Solution (Free-List Allocator)

This is Part 2 of how memory is allocated by the OS. In the first part, I talked about the need for virtual pages and why I called it the "Page-Based Solution." Here, we will talk about how that approach creates its own set of new problems, and how the solutions keep popping up like the heads of a Hydra.

Aligning Memory

Let’s talk about memory alignment. On a modern 64-bit architecture, the CPU reads data from RAM in 8-byte chunks (called "words"). If our memory isn't aligned, say, a 4-byte variable sits right across the boundary of two 8-byte chunks, the CPU has to read from memory twice just to stitch that single variable together. That makes it slow. But if we request a page from the OS, we are already getting a proper chunk of memory that is perfectly aligned to a 4096-byte boundary right out of the gate, making it faster and smoother. Sometimes, if we only need a tiny variable like a char, the system adds "filler" bytes (padding) to keep the next variable perfectly aligned to those 8-byte boundaries. You see? Keeping things aligned makes the CPU much more efficient.

In-band metadata in the heap.

"Is it efficient for 32 bytes?"
You are 100% correct. It is horribly inefficient for tiny allocations.

If a user asks for 4 bytes, and your control panel (metadata struct) is 24 bytes, your overhead is 600%. You are wasting more space managing the memory than actually using it! In the real world, the Linux kernel solves this using "Slab Allocators." For tiny requests, the OS creates a massive grid of exactly 32-byte slots and uses just one control panel to manage hundreds of them.

This is why I am going to show three main ways of allocating memory: Slab Allocator, Buddy Allocator, and Free-List Allocator.

I wondered which one is the best, but apparently, each is situational. Right now, I don't fully know what that means, but let's see if by the end of this article, I will be able to pick the appropriate allocator style for different projects.

Firstly, here is a skeleton of a manual memory allocation. I created two structs, each in charge of tracking free memory and used memory in a Linked List setting so it's easy to keep track of them. A good amount of pointer arithmetic was used, lool. I am not gonna explain the whole code just yet. The main idea of this article is to discuss different ways that memory allocation is possible.

#include <stdio.h>
#include <stdbool.h>
#include <sys/mman.h>


struct  node_data {

    size_t memory_size;
    bool is_free;
    struct node_data * ptr;
};

int main(){

    void *raw_memory = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

    struct node_data *metadata = (struct node_data *)raw_memory;

    metadata->is_free = true;
    metadata->ptr = NULL;
    metadata->memory_size = 4096 - sizeof(struct node_data);

    printf("%zu\n", metadata->memory_size);

    //Now for my 2nd struct to keep track of free space
    struct node_data *metadata2 = (struct node_data*)((char*)(metadata + 1)+32);
    metadata->is_free = false;
    metadata->ptr = metadata2;
    metadata->memory_size = 32; //gave 32 bytes to use

    metadata2->is_free = true;
    metadata2->ptr = NULL;
    metadata2->memory_size = 4096 - (metadata->memory_size) - sizeof(struct node_data) - sizeof(struct node_data);


    printf("The free size now is %zu\n", metadata2->memory_size); 


}

Slab Allocator:
This is considered to be the fastest because it keeps assigning the exact same block size of memory for every object. It is highly optimized, and due to the perks of same-sized blocks, it is usually used by the OS for repetitive things like Process tables and network socket buffers, which are always of fixed sizes.

Buddy Allocator:
It uses powers of 2 to merge free memory spaces (like 2, 4, 8, 16... up to huge blocks). It prevents external fragmentation, and Linux uses it heavily. But it can have a lot of internal fragmentation. Since it relies on powers of 2, if you want 17 bytes, you get assigned 32 bytes. That's 15 bytes of wasted space sitting unused inside your block!

Free-List Allocator:
Here, there is a metadata linked list that keeps track of all the free space scattered across the page. It might be a bit slow because the allocator has to search through the list to find a block big enough for your request. Over time, it can suffer from fragmentation as chunks are split and freed in random orders, leaving tiny holes everywhere. But it is very flexible for general-purpose programming. However, like we saw above, if the linked list metadata is 24 bytes and we request 4 bytes... we used 24 bytes to keep track of 4 bytes. I don't think we can call that efficient for tiny allocations.

Code for Free-List Allocation

Here is the code for a custom Free-List Allocator. The real magic happens right here through pointer arithmetic and linked-list traversal. This series isn't about doing a line-by-line code explanation, so I will keep it brief.

You just have to remember the core mechanics: we need a "walker" pointer to traverse the linked list. A while loop is perfect for this, allowing us to conditionally step from one pointer to the next until we find a free block big enough for our request. Always maintain a global variable to keep track of the start of your list, and rely on pointer arithmetic to calculate your remaining free space.

NGL, this was amazing to learn. Building a linked list that actively tracks state changes and dynamically slices up free memory on the fly is incredibly satisfying.

It has been a pleasure writing and learning this alongside you. Have an awesome day, and stay linked with curiosity.

#include <stdio.h>
#include <stdbool.h>
#include <sys/mman.h>


struct  node_data {

    size_t memory_size;
    bool is_free;
    struct node_data * ptr;
};


struct node_data *global_start;

void *my_malloc(size_t request_size);

int main(){

    void *raw_memory = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

    struct node_data *metadata = (struct node_data *)raw_memory;
    metadata->is_free = true;
    metadata->memory_size = 4096 - sizeof(struct node_data);
    metadata->ptr = NULL;

    global_start = metadata;

    my_malloc(34);

    return 0;
}

void *my_malloc(size_t request_size) {
    struct node_data *metadata2 = global_start;

    while (metadata2 != NULL) {
        if (metadata2->is_free == true && metadata2->memory_size >= request_size) {

            void *user_memory = (void *)(metadata2 + 1);
            struct node_data *metadata3 = (struct node_data *)((char *)user_memory + request_size);

            size_t old_size = metadata2->memory_size;

            metadata2->memory_size = request_size;
            metadata2->is_free = false;

            metadata3->ptr = metadata2->ptr;
            metadata2->ptr = metadata3;

            metadata3->is_free = true;
            metadata3->memory_size = old_size - request_size - sizeof(struct node_data);

            return user_memory;
        }
        metadata2 = metadata2->ptr;
    }
    return NULL;
}