Cómo construir un memory allocator en C desde cero.

// allocator.h
// Custom memory allocator interface

#ifndef _ALLOCATOR_H
#define _ALLOCATOR_H

#include <unistd.h>
#include <stdbool.h>
#include <stdint.h>

#define PAGE_SIZE 4096

typedef uint8_t  u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;

typedef int8_t   i8;
typedef int16_t  i16;
typedef int32_t  i32;
typedef int64_t  i64;

// Each block in the linked list carries this header
typedef struct free_area {
    int                marker;     // BLOCK_MARKER sentinel
    struct free_area  *prev;
    bool               InUse;
    u32                length;     // payload size, header excluded
    struct free_area  *next;
} area;

// Heap-wide stats kept at the very start of the heap
typedef struct stast {
    int  magical_bytes;     // ensures the allocator was initialized
    bool my_simple_lock;    // spin-style guard around malloc / free
    u32  amount_of_blocks;
    u32  amount_of_pages;
} my_stats;

void *heap_start = NULL;
void *heap_end   = NULL;

#endif

// allocator.c
#include <stdio.h>
#include <stdbool.h>
#include <unistd.h>
#include <assert.h>
#include <string.h>
#include <sys/wait.h>
#include <stdlib.h>

#include "allocator.h"

// MAGICAL_BYTES: stamped at the start of the heap to detect re-init
// BLOCK_MARKER : stamped on every block header to detect corruption
const int MAGICAL_BYTES = 0x55;
const int BLOCK_MARKER  = 0xDD;

// get_malloc_header(): return the my_stats header that sits at heap_start
my_stats *get_malloc_headear() {
    return (my_stats *)heap_start;
}

// find_last_block(): walk to the tail of the linked list
area *find_last_block() {
    area *block = (area *)((char *)heap_start + sizeof(my_stats));
    while (block->next != NULL) {
        block = block->next;
    }
    return block;
}

// an_malloc(): public entry point
//   - on first call: grow heap by one page, lay down magical_bytes + my_stats
//   - on every call: delegate to add_used_block()
//
// heap layout:
//   [ my_stats | first_block payload ........... ]
//        ^         ^
//   heap_start    heap_start + sizeof(my_stats)
int *an_malloc(ssize_t size) {
    if (heap_start == NULL) {
        heap_start = sbrk(0);  // current top of the data segment
        sbrk(4096);            // grow heap by 1 page
    }
    heap_end = sbrk(0);
    long int length = heap_end - heap_start;

    // first execution? stamp the magical bytes and lay the first block
    if (*(char *)heap_start != MAGICAL_BYTES) {
        *(char *)heap_start = MAGICAL_BYTES;
        my_stats *malloc_header = (my_stats *)heap_start;
        malloc_header->amount_of_blocks = 1;
        malloc_header->amount_of_pages  = 1;

        // the first block fills the heap; later we split it
        area *fst_block = (area *)((char *)heap_start + sizeof(my_stats));
        fst_block->marker = BLOCK_MARKER;
        fst_block->prev   = NULL;
        fst_block->InUse  = false;
        fst_block->length = length - sizeof(my_stats) - sizeof(area);
        fst_block->next   = NULL;
    }
    return add_used_block(size);
}

// the magical_bytes check inside an_malloc() guarantees the heap was set up
// before any allocation happens. if my_malloc is called without initialising
// the allocator first, *(char *)heap_start will not equal MAGICAL_BYTES (0x55).
//
// my_simple_lock is a tiny mutex on the heap header; threads spin with sleep(1)
// until the holder releases it, which prevents two an_malloc / an_free calls
// from racing on the free list at the same time.

// example of how add_used_block() acquires the lock:
my_stats *malloc_header = get_malloc_headear();
while (malloc_header->my_simple_lock) {
    sleep(1);                  // wait for the other thread to finish
}
malloc_header->my_simple_lock = true;
// ... critical section ...
malloc_header->my_simple_lock = false;

// Every time we walk a block in the free list we assert its marker matches
// BLOCK_MARKER. If a write overflows the previous block's payload, the first
// thing it tramples is this byte on the next block's header — turning an
// invisible bug into a loud assertion failure.

while (block != NULL) {
    assert(block->marker == BLOCK_MARKER);
    // ... use block ...
    block = block->next;
}

// best-fit search inside add_used_block(): walk every block, remember
// the smallest free one that still fits the request
area *block          = (area *)((char *)heap_start + sizeof(my_stats));
area *smallest_block = NULL;
area *last_block     = block;

while (block != NULL) {
    assert(block->marker == BLOCK_MARKER);
    // does this block fit the request and is it actually free?
    if ((block->length + sizeof(area)) >= size && block->InUse == false) {
        if (smallest_block == NULL || smallest_block->length > block->length) {
            smallest_block = block;
        }
    }
    last_block = block;
    block      = block->next;
}

int *add_used_block(ssize_t size) {
    // format heap_start with the shape of my_stats
    my_stats *malloc_header = get_malloc_headear();
    while (malloc_header->my_simple_lock) {
        sleep(1);                        // wait for the other thread to finish
    }
    malloc_header->my_simple_lock = true;

    // find the smallest free block that fits  (best-fit)
    area *block          = (area *)((char *)heap_start + sizeof(my_stats));
    area *smallest_block = NULL;
    area *last_block     = block;

    while (block != NULL) {
        assert(block->marker == BLOCK_MARKER);
        if ((block->length + sizeof(area)) >= size && block->InUse == false) {
            if (smallest_block == NULL || smallest_block->length > block->length) {
                smallest_block = block;
            }
        }
        last_block = block;
        block      = block->next;
    }

    // no block big enough — ask the OS for more pages until the tail fits
    if (smallest_block == NULL) {
        area *last_block = find_last_block();
        while (last_block->length < size) {
            sbrk(4096);
            last_block->length          += 4096;
            malloc_header->amount_of_pages += 1;
        }
        smallest_block = last_block;
    }

    smallest_block->InUse = true;

    // size of the leftover after carving the request out
    // -1 guarantees the new leftover block holds at least 1 byte of payload
    int must_have_size = smallest_block->length - size - sizeof(area) - 1;
    if (must_have_size <= 0) {
        sbrk(4096);
        malloc_header->amount_of_pages += 1;
        smallest_block->length         += 4096;
        must_have_size = smallest_block->length - size - sizeof(area) - 1;
    }
    int remaining_sizes = must_have_size + 1;
    malloc_header->amount_of_blocks += 1;

    // create the leftover block right after the carved-out payload
    area *new_block = (area *)((char *)smallest_block + sizeof(area) + size);
    new_block->marker = BLOCK_MARKER;
    new_block->InUse  = false;
    new_block->length = remaining_sizes;
    new_block->prev   = smallest_block;
    new_block->next   = smallest_block->next;
    if (new_block->next != NULL) {
        (new_block->next)->prev = new_block;
    }
    smallest_block->next   = new_block;
    smallest_block->length = size;

    malloc_header->my_simple_lock = false;
    return (int *)((char *)smallest_block + sizeof(area));
}

// after picking smallest_block and marking it in-use, we carve a new
// header out of its tail and turn the leftover into a fresh free block
int must_have_size = smallest_block->length - size - sizeof(area) - 1;

if (must_have_size <= 0) {
    sbrk(4096);                           // not enough room — grow the heap
    malloc_header->amount_of_pages += 1;
    smallest_block->length         += 4096;
    must_have_size = smallest_block->length - size - sizeof(area) - 1;
}
int remaining_sizes = must_have_size + 1;
malloc_header->amount_of_blocks += 1;

// the new (free) block lives right after the now-used payload
area *new_block = (area *)((char *)smallest_block + sizeof(area) + size);
new_block->marker = BLOCK_MARKER;
new_block->InUse  = false;
new_block->length = remaining_sizes;
new_block->prev   = smallest_block;
new_block->next   = smallest_block->next;
if (new_block->next != NULL) {
    (new_block->next)->prev = new_block;
}
smallest_block->next   = new_block;
smallest_block->length = size;

bool an_free(void *ptr) {
    bool      marker_state;
    my_stats *malloc_header = get_malloc_headear();
    while (malloc_header->my_simple_lock) {
        sleep(1);
    }
    malloc_header->my_simple_lock = true;

    // each block has a header behind it; back up one header to reach it
    area *block = ptr - sizeof(area);

    if (block->marker != BLOCK_MARKER) {
        marker_state = false;              // header corrupted — refuse to free
    } else {
        block->InUse = false;
        memset(ptr, 0, block->length);     // wipe the payload (defensive)

        // coalesce with the next neighbour if it is free
        if (block->next != NULL && (block->next)->InUse == false) {
            area *not_used_next_block = block->next;
            block->next = not_used_next_block->next;
            if (not_used_next_block->next != NULL) {
                (not_used_next_block->next)->prev = block;
            } else {
                block->next = NULL;
            }
            block->length += not_used_next_block->length + sizeof(area);
            memset((void *)not_used_next_block, 0,
                   sizeof(area) + not_used_next_block->length);
            malloc_header->amount_of_blocks -= 1;

            // coalesce with the previous neighbour if it is free too
            if (block->prev != NULL && (block->prev)->InUse == false) {
                area *to_delete_block = block;
                block         = block->prev;
                block->length += to_delete_block->length + sizeof(area);
                block->next   = to_delete_block->next;
            }
            if (block->next != NULL) {
                block->next->prev = block;
            }
            malloc_header->amount_of_blocks -= 1;
        }
        reduce_heap_size_if_possible();
        marker_state = true;
    }
    malloc_header->my_simple_lock = false;
    return marker_state;
}

// merge with the next neighbour if it is free
if (block->next != NULL && (block->next)->InUse == false) {
    area *not_used_next_block = block->next;
    block->next = not_used_next_block->next;
    if (not_used_next_block->next != NULL) {
        (not_used_next_block->next)->prev = block;
    } else {
        block->next = NULL;
    }
    block->length += not_used_next_block->length + sizeof(area);
    memset((void *)not_used_next_block, 0,
           sizeof(area) + not_used_next_block->length);
    malloc_header->amount_of_blocks -= 1;

    // and merge with the previous neighbour if it is free too
    if (block->prev != NULL && (block->prev)->InUse == false) {
        area *to_delete_block = block;
        block         = block->prev;
        block->length += to_delete_block->length + sizeof(area);
        block->next   = to_delete_block->next;
    }
    if (block->next != NULL) {
        block->next->prev = block;
    }
}

void reduce_heap_size_if_possible() {
    area *last_block      = find_last_block();
    area *prev_used_block = find_previous_used_block(last_block);

    if (prev_used_block == NULL) {
        if (last_block->length > PAGE_SIZE) {
            last_block->length = PAGE_SIZE;
        }
        prev_used_block = last_block;
    }

    // new_end = where the last used block actually ends in memory
    void *new_end  = (void *)prev_used_block + sizeof(area) + prev_used_block->length;
    void *heap_end = sbrk(0);                  // current top of the heap

    // peel whole pages off the top while there is still room above new_end
    while (new_end < heap_end - PAGE_SIZE) {
        sbrk(-PAGE_SIZE);                      // return one page to the OS
        heap_end = sbrk(0);
        my_stats *malloc_header = get_malloc_headear();
        malloc_header->amount_of_pages -= 1;
    }

    // most of the time there is a small gap between the last used block and
    // the new heap top — fit a free block in there if it can hold at least 1 B
    //   [ last_block_used ][ leftover space ][ end of heap ]
    if (heap_end - new_end > sizeof(area) + 1) {
        area *new_not_used_block = (area *)new_end;
        new_not_used_block->marker = BLOCK_MARKER;
        new_not_used_block->InUse  = false;
        new_not_used_block->prev   = prev_used_block;
        new_not_used_block->next   = NULL;
        new_not_used_block->length = heap_end - new_end - sizeof(area);
        prev_used_block->next      = new_not_used_block;
    }
}

// helper used by reduce_heap_size_if_possible(): walk backwards from a block
// until we find one that is in use (returns NULL if none exist)
area *find_previous_used_block(area *ptr) {
    area *last_block = ptr->prev;
    while (last_block != NULL) {
        if (last_block->InUse == true) {
            return last_block;
        }
        last_block = last_block->prev;
    }
    return NULL;
}

// my_simple_lock lives inside my_stats (one bool at the start of the heap).
// Every public entry point grabs it before touching the free list and drops
// it on the way out. Threads that find it taken spin with sleep(1).

void critical_section_example() {
    my_stats *malloc_header = get_malloc_headear();
    while (malloc_header->my_simple_lock) {
        sleep(1);                       // wait until the other thread releases
    }
    malloc_header->my_simple_lock = true;

    // ... walk the free list, split, coalesce, etc. ...

    malloc_header->my_simple_lock = false;
}

// call_test(): run a single test in its own forked child so a crash in one
// test cannot corrupt the heap of the next one. The parent waits and prints
// whether the child died with a signal or exited cleanly.
void call_test(void (*test_func)(), const char *msg) {
    pid_t pid = fork();
    if (pid == 0) {
        test_func();
        exit(0);
    } else {
        int status;
        waitpid(pid, &status, 0);
        if (WIFSIGNALED(status)) {
            printf("%s crashed with signal %d\n", msg, WTERMSIG(status));
        } else {
            printf("%s passed\n", msg);
        }
    }
}

// the four tests
void test_basic_malloc() {
    int *ptr = (int *)an_malloc(sizeof(int));
    assert(ptr != NULL);
    *ptr = 42;
    assert(*ptr == 42);
    an_free(ptr);
}

void test_bigger_than_available_malloc() {
    uint16_t *ptr = (uint16_t *)an_malloc(5000);
    area     *first_block = (void *)ptr - sizeof(area);
    for (uint16_t i = 0; i <= 2499; i++) {
        *(ptr + i) = i;
    }
    assert(first_block->marker == BLOCK_MARKER);
    assert(*ptr == 0);
    assert(*(ptr + 2499) == 2499);
}

void test_free() {
    int *ptr = (int *)an_malloc(sizeof(int));
    *ptr = 99;
    bool result = an_free(ptr);
    assert(result == true);
    area *block = (area *)((char *)ptr - sizeof(area));
    assert(block->InUse == false);
}

void complex_set_of_malloc_and_free_calls() {
    int *a = (int *)an_malloc(sizeof(int));
    int *b = (int *)an_malloc(sizeof(int) * 10);
    int *c = (int *)an_malloc(sizeof(int) * 100);

    *a = 1;
    for (int i = 0; i < 10;  i++) *(b + i) = i;
    for (int i = 0; i < 100; i++) *(c + i) = i;
    assert(*a == 1 && *(b + 9) == 9 && *(c + 99) == 99);

    an_free(b); an_free(a); an_free(c);

    int *d = (int *)an_malloc(sizeof(int));
    *d = 77;
    assert(*d == 77);
    an_free(d);
}

int main() {
    call_test(test_basic_malloc,                "Basic Malloc");
    call_test(test_bigger_than_available_malloc,"Request more memory Malloc");
    call_test(test_free,                        "Basic Free");
    call_test(complex_set_of_malloc_and_free_calls, "Complex");
    printf("DONE\n");
    return 0;
}

allocator.c: implicit declaration of function 'sbrk' [-Wimplicit-function-declaration]
allocator.c: implicit declaration of function 'fork' [-Wimplicit-function-declaration]

# Two ways to compile this allocator

# Option A: no strict standard — sbrk() is declared by default
gcc -Wall -Wextra -g allocator.c -o test

# Option B: strict C99 + POSIX feature-test macro
gcc -Wall -Wextra -g -D_DEFAULT_SOURCE -std=c99 allocator.c -o test

# Why? sbrk() is a POSIX extension. With -std=c99 alone, glibc hides its
# declaration in <unistd.h>, so the compiler assumes sbrk() returns int
# (32 bits) instead of void * (64 bits). The truncated pointer segfaults
# at runtime. -D_DEFAULT_SOURCE re-exposes the BSD/POSIX corner of glibc.