Implement a memory allocator in C11 in this directory. Files: alloc.c, alloc.h (my_mall…

pigpt-5.5 · 44 steps · 2m 36s · 4 filessession 8a65b7eb-a82@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 11 / 44

alloc.cchange 1/4

#include "alloc.h"
 
#include <stdint.h>
#include <string.h>
 
#define ARENA_SIZE (1024u * 1024u)
#define ALIGNMENT 16u
#define MIN_PAYLOAD 16u
#define FOOTER_SIZE 16u
#define CANARY_MAGIC UINT64_C(0x9e3779b97f4a7c15)
 
#define ALIGN_UP(x) (((x) + (ALIGNMENT - 1u)) & ~(size_t)(ALIGNMENT - 1u))
 
typedef struct block block_t;
struct block {
    size_t size;          /* aligned payload bytes */
    int free;
    uint64_t canary;
    block_t *prev;
    block_t *next;
    block_t *free_prev;
    block_t *free_next;
};
 
#define HEADER_SIZE ALIGN_UP(sizeof(block_t))
#define OVERHEAD (HEADER_SIZE + FOOTER_SIZE)
 
static _Alignas(16) unsigned char arena[ARENA_SIZE];
static block_t *heap_head;
static block_t *free_head;
static int initialized;
 
static uint64_t block_canary(const block_t *b) {
    uintptr_t p = (uintptr_t)b;
    return (uint64_t)(p >> 4) ^ (uint64_t)b->size ^ CANARY_MAGIC;
}
 
static uint64_t *footer_ptr(const block_t *b) {
    return (uint64_t *)((unsigned char *)b + HEADER_SIZE + b->size);
}
 
static void write_canaries(block_t *b) {
    b->canary = block_canary(b);
    *footer_ptr(b) = b->canary;
}
 
static int block_canaries_ok(const block_t *b) {
    if (b->canary != block_canary(b)) return 0;
    return *footer_ptr(b) == b->canary;
}
 
static void free_list_remove(block_t *b) {
    if (b->free_prev) b->free_prev->free_next = b->free_next;
    else if (free_head == b) free_head = b->free_next;
    if (b->free_next) b->free_next->free_prev = b->free_prev;
    b->free_prev = NULL;
    b->free_next = NULL;
}
 
static void free_list_push(block_t *b) {
    b->free = 1;
    b->free_prev = NULL;
    b->free_next = free_head;
    if (free_head) free_head->free_prev = b;
    free_head = b;
}
 
static void init_heap(void) {
    if (initialized) return;
    heap_head = (block_t *)arena;
    heap_head->size = ALIGN_UP(ARENA_SIZE - OVERHEAD);
    heap_head->free = 1;
    heap_head->prev = NULL;
    heap_head->next = NULL;
    heap_head->free_prev = NULL;
    heap_head->free_next = NULL;
    write_canaries(heap_head);
    free_head = heap_head;
    initialized = 1;
}
 
static void split_block(block_t *b, size_t need) {
    size_t remaining = b->size - need;
    if (remaining < OVERHEAD + MIN_PAYLOAD) return;
 
    block_t *n = (block_t *)((unsigned char *)b + HEADER_SIZE + need + FOOTER_SIZE);
    n->size = remaining - OVERHEAD;
    n->free = 1;
    n->prev = b;
    n->next = b->next;
    if (n->next) n->next->prev = n;
    n->free_prev = NULL;
    n->free_next = NULL;
 
    b->size = need;
    b->next = n;
    write_canaries(b);
    write_canaries(n);
    free_list_push(n);
}
 
static block_t *coalesce(block_t *b) {
    if (b->next && b->next->free) {
        block_t *n = b->next;
        free_list_remove(n);
        b->size += OVERHEAD + n->size;
        b->next = n->next;
        if (b->next) b->next->prev = b;
        write_canaries(b);
    }
    if (b->prev && b->prev->free) {
        block_t *p = b->prev;
        free_list_remove(b);
        p->size += OVERHEAD + b->size;
        p->next = b->next;
        if (p->next) p->next->prev = p;
        write_canaries(p);
        b = p;
    }
    return b;
}
 
void *my_malloc(size_t size) {
    init_heap();
    if (size == 0) return NULL;
    size_t need = ALIGN_UP(size);
    if (need < size) return NULL;
 
    for (block_t *b = free_head; b; b = b->free_next) {
        if (b->size >= need) {
            if (!block_canaries_ok(b)) return NULL;
            free_list_remove(b);
            b->free = 0;
            split_block(b, need);
            write_canaries(b);
            return (unsigned char *)b + HEADER_SIZE;
        }
    }
    return NULL;
}
 
void my_free(void *ptr) {
    if (!ptr) return;
    init_heap();
    block_t *b = (block_t *)((unsigned char *)ptr - HEADER_SIZE);
    if ((unsigned char *)b < arena || (unsigned char *)b >= arena + ARENA_SIZE) return;
    if (!block_canaries_ok(b) || b->free) return;
    b->free = 1;
    write_canaries(b);
    free_list_push(b);
    (void)coalesce(b);
}
 
void *my_calloc(size_t nmemb, size_t size) {
    if (size != 0 && nmemb > (size_t)-1 / size) return NULL;
    size_t total = nmemb * size;
    void *p = my_malloc(total);
    if (p) memset(p, 0, total);
    return p;
}
 
void *my_realloc(void *ptr, size_t size) {
    if (!ptr) return my_malloc(size);
    if (size == 0) {
        my_free(ptr);
        return NULL;
    }
 
    init_heap();
    block_t *b = (block_t *)((unsigned char *)ptr - HEADER_SIZE);
    if (!block_canaries_ok(b) || b->free) return NULL;
    size_t need = ALIGN_UP(size);
    if (need < size) return NULL;
 
    if (need <= b->size) {
        split_block(b, need);
        write_canaries(b);
        return ptr;
    }
 
    if (b->next && b->next->free && b->size + OVERHEAD + b->next->size >= need) {
        block_t *n = b->next;
        free_list_remove(n);
        b->size += OVERHEAD + n->size;
        b->next = n->next;
        if (b->next) b->next->prev = b;
        write_canaries(b);
        split_block(b, need);
        write_canaries(b);
        return (unsigned char *)b + HEADER_SIZE;
    }
 
    void *np = my_malloc(size);
    if (!np) return NULL;
    memcpy(np, ptr, b->size < size ? b->size : size);
    my_free(ptr);
    return np;
}
 
int my_heap_check(void) {
    init_heap();
    unsigned char *expected = arena;
    block_t *prev = NULL;
    for (block_t *b = heap_head; b; b = b->next) {
        if ((unsigned char *)b != expected) return 0;
        if (((uintptr_t)b & (ALIGNMENT - 1u)) != 0) return 0;
        if (b->prev != prev) return 0;
        if ((b->size & (ALIGNMENT - 1u)) != 0) return 0;
        if ((unsigned char *)b + OVERHEAD + b->size > arena + ARENA_SIZE) return 0;
        if (!block_canaries_ok(b)) return 0;
        expected = (unsigned char *)b + OVERHEAD + b->size;
        prev = b;
    }
    if (expected != arena + ARENA_SIZE) return 0;
 
    for (block_t *f = free_head; f; f = f->free_next) {
        if (!f->free) return 0;
        if (f->free_next && f->free_next->free_prev != f) return 0;
    }
    return 1;
}
 
my_stats_t my_stats(void) {
    init_heap();
    my_stats_t s = {0, 0, 0};
    for (block_t *b = heap_head; b; b = b->next) {
        if (b->free) {
            s.free_block_count++;
            if (b->size > s.largest_free_block) s.largest_free_block = b->size;
        } else {
            s.bytes_in_use += b->size;
        }
    }
    return s;
}
 

236 linesc

Writes 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 #pi #quick #testing

w4-pi

← all sessions