C11 memory allocator implementation

opencodegpt-5.5 · 45 steps · 2m 20s · 4 filessession a5c0bade-919@patrick-toulme

"Implement a memory allocator in C11 in this directory. Files: alloc.c, alloc.h (my_malloc, my_free, my_calloc, my_realloc managing a 1 MiB static byte arena — first-fit free list with block splitting and coalescing of adjacent free blocks on free, 16-byte alignment, per-block canaries with a my_heap_check() validator that walks the heap, and my_stats() reporting bytes in use, free block count, and largest free block), tests.c (a deterministic seeded stress test: 100k mixed malloc/free/realloc ops mirrored against a shadow table, filling each allocation with a pattern and verifying it before free; fragmentation scenario tests proving coalescing recovers the largest block; a canary-violation detection test), Makefile (clang -std=c11 -Wall -Wextra -fsanitize=address,undefined). Build with make, run the tests, and fix failures until everything passes clean."

same matchclaude-code · 51 steps opencode · 45 steps pi · 44 steps antigravity · 20 steps

compare in arena

step 45 / 45

alloc.cchange 2/2

#include "alloc.h"
 
#include <stdint.h>
#include <string.h>
 
#define CANARY_VALUE UINT64_C(0xc0ffee1234fedcba)
#define MIN_SPLIT_PAYLOAD MY_ALIGNMENT
 
typedef struct block_header {
    size_t size;
    int free;
    struct block_header *prev;
    struct block_header *next;
    uint64_t canary;
} block_header;
 
typedef union arena_storage {
    unsigned char bytes[MY_ARENA_SIZE];
    max_align_t align;
} arena_storage;
 
static arena_storage arena;
static block_header *head;
static int initialized;
 
static size_t align_up(size_t size) {
    return (size + (MY_ALIGNMENT - 1u)) & ~(size_t)(MY_ALIGNMENT - 1u);
}
 
static size_t header_size(void) {
    return align_up(sizeof(block_header));
}
 
static size_t footer_size(void) {
    return align_up(sizeof(uint64_t));
}
 
static uint64_t *tail_canary(block_header *block) {
    return (uint64_t *)((unsigned char *)block + header_size() + block->size);
}
 
static void set_canaries(block_header *block) {
    block->canary = CANARY_VALUE;
    *tail_canary(block) = CANARY_VALUE;
}
 
static void init_heap(void) {
    if (initialized) {
        return;
    }
 
    head = (block_header *)arena.bytes;
    head->size = MY_ARENA_SIZE - header_size() - footer_size();
    head->free = 1;
    head->prev = NULL;
    head->next = NULL;
    set_canaries(head);
    initialized = 1;
}
 
static void split_block(block_header *block, size_t size) {
    const size_t overhead = header_size() + footer_size();
 
    if (block->size < size + overhead + MIN_SPLIT_PAYLOAD) {
        return;
    }
 
    block_header *new_block = (block_header *)((unsigned char *)block + overhead + size);
    new_block->size = block->size - size - overhead;
    new_block->free = 1;
    new_block->prev = block;
    new_block->next = block->next;
    if (new_block->next != NULL) {
        new_block->next->prev = new_block;
    }
 
    block->size = size;
    block->next = new_block;
    set_canaries(block);
    set_canaries(new_block);
}
 
static void coalesce(block_header *block) {
    const size_t overhead = header_size() + footer_size();
 
    if (block->next != NULL && block->next->free) {
        block_header *next = block->next;
        block->size += overhead + next->size;
        block->next = next->next;
        if (block->next != NULL) {
            block->next->prev = block;
        }
        set_canaries(block);
    }
 
    if (block->prev != NULL && block->prev->free) {
        block_header *prev = block->prev;
        prev->size += overhead + block->size;
        prev->next = block->next;
        if (prev->next != NULL) {
            prev->next->prev = prev;
        }
        set_canaries(prev);
    }
}
 
static block_header *ptr_to_block(void *ptr) {
    if (ptr == NULL) {
        return NULL;
    }
    return (block_header *)((unsigned char *)ptr - header_size());
}
 
void *my_malloc(size_t size) {
    if (size == 0) {
        return NULL;
    }
 
    init_heap();
    size = align_up(size);
 
    for (block_header *block = head; block != NULL; block = block->next) {
        if (block->free && block->size >= size) {
            split_block(block, size);
            block->free = 0;
            set_canaries(block);
            return (unsigned char *)block + header_size();
        }
    }
 
    return NULL;
}
 
void my_free(void *ptr) {
    if (ptr == NULL) {
        return;
    }
 
    block_header *block = ptr_to_block(ptr);
    if (block->canary != CANARY_VALUE || *tail_canary(block) != CANARY_VALUE) {
        return;
    }
 
    block->free = 1;
    coalesce(block);
}
 
void *my_calloc(size_t count, size_t size) {
    if (count != 0 && size > (SIZE_MAX / count)) {
        return NULL;
    }
 
    size_t total = count * size;
    void *ptr = my_malloc(total);
    if (ptr != NULL) {
        memset(ptr, 0, total);
    }
    return ptr;
}
 
void *my_realloc(void *ptr, size_t size) {
    if (ptr == NULL) {
        return my_malloc(size);
    }
    if (size == 0) {
        my_free(ptr);
        return NULL;
    }
 
    block_header *block = ptr_to_block(ptr);
    if (block->canary != CANARY_VALUE || *tail_canary(block) != CANARY_VALUE) {
        return NULL;
    }
 
    size_t new_size = align_up(size);
    if (new_size <= block->size) {
        split_block(block, new_size);
        return ptr;
    }
 
    if (block->next != NULL && block->next->free) {
        size_t combined = block->size + header_size() + footer_size() + block->next->size;
        if (combined >= new_size) {
            block_header *next = block->next;
            block->size = combined;
            block->next = next->next;
            if (block->next != NULL) {
                block->next->prev = block;
            }
            split_block(block, new_size);
            block->free = 0;
            set_canaries(block);
            return ptr;
        }
    }
 
    void *new_ptr = my_malloc(size);
    if (new_ptr == NULL) {
        return NULL;
    }
 
    memcpy(new_ptr, ptr, block->size < size ? block->size : size);
    my_free(ptr);
    return new_ptr;
}
 
int my_heap_check(void) {
    init_heap();
 
    unsigned char *arena_start = arena.bytes;
    unsigned char *arena_end = arena.bytes + MY_ARENA_SIZE;
    unsigned char *expected = arena_start;
 
    for (block_header *block = head; block != NULL; block = block->next) {
        unsigned char *block_start = (unsigned char *)block;
        unsigned char *payload = block_start + header_size();
        unsigned char *tail = payload + block->size;
        unsigned char *block_end = tail + footer_size();
 
        if (block_start != expected || block_start < arena_start || block_end > arena_end) {
            return 0;
        }
        if (((uintptr_t)payload % MY_ALIGNMENT) != 0 || (block->size % MY_ALIGNMENT) != 0) {
            return 0;
        }
        if (block->canary != CANARY_VALUE || *(uint64_t *)tail != CANARY_VALUE) {
            return 0;
        }
        if (block->next != NULL && block->next->prev != block) {
            return 0;
        }
        if (block->free && block->next != NULL && block->next->free) {
            return 0;
        }
 
        expected = block_end;
    }
 
    return expected == arena_end;
}
 
my_stats_result my_stats(void) {
    init_heap();
 
    my_stats_result stats = {0, 0, 0};
    for (block_header *block = head; block != NULL; block = block->next) {
        if (block->free) {
            stats.free_block_count++;
            if (block->size > stats.largest_free_block) {
                stats.largest_free_block = block->size;
            }
        } else {
            stats.bytes_in_use += block->size;
        }
    }
    return stats;
}
 
void my_heap_reset(void) {
    initialized = 0;
    head = NULL;
    init_heap();
}
 

264 linesc

Implemented the C11 allocator and tests. Files added: - `alloc.h` - `alloc.c` - `tests.c` -…

Files at this step

drag the rail to scrub

Discussion

No comments yet. Start the discussion. Recorded by @patrick-toulme.

#c #gpt #gpt-5.5 #opencode #quick #testing

w3-opencode

← all sessions