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

claude-codeclaude-opus-4-8 · 51 steps · 12m 49s · 4 filessession 6da6e019-501@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 06 / 51
alloc.cchange 1/1
#include "alloc.h"
 
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* ------------------------------------------------------------------------- *
 *  Layout
 *
 *  Every block occupies a contiguous run of arena bytes:
 *
 *      [ block_t header ][ payload (size bytes) ][ footer_t ]
 *
 *  `header` and `footer` sizes are both multiples of 16, and `size` is always
 *  rounded up to a multiple of 16, so if a block starts 16-byte aligned then
 *  its payload and the following block also start 16-byte aligned.  The arena
 *  itself is declared with 16-byte alignment, so the invariant holds forever.
 *
 *  Blocks are threaded two ways:
 *    - a physical doubly linked list (prev_phys / next_phys) covering the whole
 *      arena in address order, used for coalescing and for my_heap_check();
 *    - an explicit free list (prev_free / next_free) of the free blocks only,
 *      searched first-fit by my_malloc().
 * ------------------------------------------------------------------------- */
 
typedef struct block {
    uint32_t      head_canary;  /* == head_canary_for(this)                    */
    uint32_t      free;         /* 1 == free, 0 == in use                      */
    size_t        size;         /* usable payload bytes (multiple of 16)       */
    struct block *prev_phys;    /* previous block in address order (or NULL)   */
    struct block *next_phys;    /* next block in address order (or NULL)       */
    struct block *prev_free;    /* free-list links, valid only while free      */
    struct block *next_free;
} block_t;
 
typedef struct footer {
    uint64_t canary;            /* == foot_canary_for(owning block)            */
    uint64_t back;             /* == (uintptr_t)owning block, a redundant check */
} footer_t;
 
#define ARENA_SIZE   ((size_t)(1u << 20))   /* 1 MiB */
#define ALIGNMENT    ((size_t)16)
#define HEADER_SIZE  (sizeof(block_t))
#define FOOTER_SIZE  (sizeof(footer_t))
 
_Static_assert(HEADER_SIZE % ALIGNMENT == 0, "header must be 16-byte sized");
_Static_assert(FOOTER_SIZE == 16, "footer must be 16 bytes");
_Static_assert(ARENA_SIZE % ALIGNMENT == 0, "arena must be 16-byte sized");
_Static_assert((ARENA_SIZE - HEADER_SIZE - FOOTER_SIZE) % ALIGNMENT == 0,
               "initial payload must be 16-byte aligned");
 
/* The arena and the allocator's mutable state. */
static _Alignas(16) unsigned char arena[ARENA_SIZE];
static block_t *free_list;   /* head of the explicit free list */
static int      initialized;
 
/* ------------------------------------------------------------------------- *
 *  Canaries
 *
 *  Both canaries are derived from the block's own address, so a stray write
 *  that clobbers a canary -- or a corrupted pointer that lands on the wrong
 *  block -- is caught by my_heap_check().
 * ------------------------------------------------------------------------- */
 
#define HEAD_MAGIC 0xA110C8EDu
#define FOOT_MAGIC 0xDEADBEEFCAFEF00Dull
 
static uint32_t head_canary_for(const block_t *b) {
    return HEAD_MAGIC ^ (uint32_t)(uintptr_t)b;
}
 
static uint64_t foot_canary_for(const block_t *b) {
    return FOOT_MAGIC ^ (uint64_t)(uintptr_t)b;
}
 
static footer_t *footer_of(block_t *b) {
    return (footer_t *)((unsigned char *)b + HEADER_SIZE + b->size);
}
 
static void write_canaries(block_t *b) {
    b->head_canary = head_canary_for(b);
    footer_t *f = footer_of(b);
    f->canary = foot_canary_for(b);
    f->back = (uint64_t)(uintptr_t)b;
}
 
static int canaries_ok(block_t *b) {
    if (b->head_canary != head_canary_for(b)) return 0;
    footer_t *f = footer_of(b);
    if (f->canary != foot_canary_for(b)) return 0;
    if (f->back != (uint64_t)(uintptr_t)b) return 0;
    return 1;
}
 
/* payload <-> header conversions */
static void *payload_of(block_t *b) {
    return (unsigned char *)b + HEADER_SIZE;
}
static block_t *block_of(void *ptr) {
    return (block_t *)((unsigned char *)ptr - HEADER_SIZE);
}
static block_t *first_block(void) {
    return (block_t *)arena;
}
 
#define ALIGN_UP(n, a) (((n) + ((a) - 1)) & ~((size_t)(a) - 1))
 
static void fatal(const char *msg) {
    fprintf(stderr, "my_alloc: fatal: %s\n", msg);
    abort();
}
 
/* ------------------------------------------------------------------------- *
 *  Free-list bookkeeping (LIFO insertion; O(1) unlink)
 * ------------------------------------------------------------------------- */
 
static void fl_insert(block_t *b) {
    b->prev_free = NULL;
    b->next_free = free_list;
    if (free_list) free_list->prev_free = b;
    free_list = b;
}
 
static void fl_remove(block_t *b) {
    if (b->prev_free) b->prev_free->next_free = b->next_free;
    else              free_list = b->next_free;
    if (b->next_free) b->next_free->prev_free = b->prev_free;
    b->prev_free = b->next_free = NULL;
}
 
static void ensure_init(void) {
    if (initialized) return;
    initialized = 1;
 
    block_t *b = first_block();
    b->size      = ARENA_SIZE - HEADER_SIZE - FOOTER_SIZE;
    b->free      = 1;
    b->prev_phys = NULL;
    b->next_phys = NULL;
    b->prev_free = NULL;
    b->next_free = NULL;
    write_canaries(b);
 
    free_list = NULL;
    fl_insert(b);
}
 
/* ------------------------------------------------------------------------- *
 *  Core block operations
 * ------------------------------------------------------------------------- */
 
/* Mark `b` free, coalesce with adjacent free neighbours, insert into the free
 * list, and return the resulting (possibly merged) block. `b` must not already
 * be on the free list. */
static block_t *free_block(block_t *b) {
    b->free = 1;
 
    /* Merge with the following block if it is free. */
    block_t *next = b->next_phys;
    if (next && next->free) {
        fl_remove(next);
        b->size += FOOTER_SIZE + HEADER_SIZE + next->size;
        b->next_phys = next->next_phys;
        if (b->next_phys) b->next_phys->prev_phys = b;
    }
 
    /* Merge with the preceding block if it is free. */
    block_t *prev = b->prev_phys;
    if (prev && prev->free) {
        fl_remove(prev);
        prev->size += FOOTER_SIZE + HEADER_SIZE + b->size;
        prev->next_phys = b->next_phys;
        if (prev->next_phys) prev->next_phys->prev_phys = prev;
        b = prev;
    }
 
    write_canaries(b);
    fl_insert(b);
    return b;
}
 
/* Given an in-use block `b` with capacity `b->size >= asize` and not on the
 * free list, split off the tail beyond `asize` into its own free block when the
 * remainder is large enough to stand alone. The remainder is coalesced with the
 * block that physically follows it (used by realloc's shrink path). */
static void carve(block_t *b, size_t asize) {
    if (b->size < asize + HEADER_SIZE + FOOTER_SIZE + ALIGNMENT)
        return; /* remainder would be too small to be its own block */
 
    block_t *after = b->next_phys;
    block_t *r = (block_t *)((unsigned char *)b + HEADER_SIZE + asize + FOOTER_SIZE);
 
    r->size      = b->size - asize - HEADER_SIZE - FOOTER_SIZE;
    r->free      = 0; /* free_block() sets this properly */
    r->prev_phys = b;
    r->next_phys = after;
    r->prev_free = NULL;
    r->next_free = NULL;
    if (after) after->prev_phys = r;
 
    b->next_phys = r;
    b->size      = asize;
 
    free_block(r); /* left neighbour (b) is in use, so only merges rightward */
}
 
/* ------------------------------------------------------------------------- *
 *  Public API
 * ------------------------------------------------------------------------- */
 
void *my_malloc(size_t size) {
    if (size == 0 || size > ARENA_SIZE) return NULL;
    ensure_init();
 
    size_t asize = ALIGN_UP(size, ALIGNMENT);
 
    /* First fit. */
    block_t *b = free_list;
    while (b && b->size < asize) b = b->next_free;
    if (!b) return NULL;
 
    fl_remove(b);
    b->free = 0;
    carve(b, asize);       /* release any excess as a free remainder */
    write_canaries(b);
    return payload_of(b);
}
 
void my_free(void *ptr) {
    if (!ptr) return;
    ensure_init();
 
    if ((unsigned char *)ptr < arena + HEADER_SIZE ||
        (unsigned char *)ptr >= arena + ARENA_SIZE)
        fatal("free of a pointer outside the arena");
 
    block_t *b = block_of(ptr);
    if (!canaries_ok(b)) fatal("free of a corrupted or invalid block");
    if (b->free)         fatal("double free");
 
    free_block(b);
}
 
void *my_calloc(size_t nmemb, size_t size) {
    if (nmemb != 0 && size > ARENA_SIZE / nmemb) return NULL; /* overflow guard */
    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; }
    if (size > ARENA_SIZE) return NULL;
    ensure_init();
 
    block_t *b = block_of(ptr);
    if (!canaries_ok(b)) fatal("realloc of a corrupted or invalid block");
    if (b->free)         fatal("realloc of a freed block");
 
    size_t asize = ALIGN_UP(size, ALIGNMENT);
 
    /* Already big enough: keep in place, giving back any excess. */
    if (asize <= b->size) {
        carve(b, asize);
        write_canaries(b);
        return ptr;
    }
 
    /* Grow in place by absorbing the following block if it is free and big
     * enough for the two together to cover the request. */
    block_t *next = b->next_phys;
    if (next && next->free &&
        b->size + FOOTER_SIZE + HEADER_SIZE + next->size >= asize) {
        fl_remove(next);
        b->size += FOOTER_SIZE + HEADER_SIZE + next->size;
        b->next_phys = next->next_phys;
        if (b->next_phys) b->next_phys->prev_phys = b;
        carve(b, asize);   /* trim back down if we overshot */
        write_canaries(b);
        return ptr;
    }
 
    /* Fall back to allocate-copy-free. Leave the original intact on failure. */
    void *np = my_malloc(size);
    if (!np) return NULL;
    size_t copy = b->size < size ? b->size : size;
    memcpy(np, ptr, copy);
    my_free(ptr);
    return np;
}
 
void my_stats(heap_stats_t *out) {
    ensure_init();
 
    out->bytes_in_use       = 0;
    out->used_blocks        = 0;
    out->free_blocks        = 0;
    out->free_bytes         = 0;
    out->largest_free_block = 0;
 
    for (block_t *b = first_block(); b; b = b->next_phys) {
        if (b->free) {
            out->free_blocks++;
            out->free_bytes += b->size;
            if (b->size > out->largest_free_block)
                out->largest_free_block = b->size;
        } else {
            out->used_blocks++;
            out->bytes_in_use += b->size;
        }
    }
}
 
size_t my_heap_capacity(void) {
    return ARENA_SIZE - HEADER_SIZE - FOOTER_SIZE;
}
 
int my_heap_check(void) {
    ensure_init();
 
    size_t total = 0;         /* bytes accounted for by every block            */
    size_t nblocks = 0;       /* total block count                             */
    size_t nfree_phys = 0;    /* free blocks seen in the physical walk         */
    block_t *prev = NULL;
 
    for (block_t *b = first_block(); b; b = b->next_phys) {
        unsigned char *bb = (unsigned char *)b;
 
        if (bb < arena || bb + HEADER_SIZE > arena + ARENA_SIZE)
            return HEAP_ERR_BOUNDS;
        if (b->size % ALIGNMENT != 0)
            return HEAP_ERR_ALIGN;
 
        unsigned char *end = bb + HEADER_SIZE + b->size + FOOTER_SIZE;
        if (end > arena + ARENA_SIZE)
            return HEAP_ERR_BOUNDS;
 
        if (b->head_canary != head_canary_for(b))
            return HEAP_ERR_HEAD_CANARY;
        {
            footer_t *f = footer_of(b);
            if (f->canary != foot_canary_for(b) ||
                f->back != (uint64_t)(uintptr_t)b)
                return HEAP_ERR_FOOT_CANARY;
        }
 
        if (b->prev_phys != prev)
            return HEAP_ERR_PHYS_LINK;
 
        block_t *computed_next = (block_t *)end;
        if (end == arena + ARENA_SIZE) {
            if (b->next_phys != NULL) return HEAP_ERR_PHYS_LINK;
        } else if (b->next_phys != computed_next) {
            return HEAP_ERR_PHYS_LINK;
        }
 
        if (b->free && prev && prev->free)
            return HEAP_ERR_ADJACENT_FREE;
 
        total += HEADER_SIZE + b->size + FOOTER_SIZE;
        nblocks++;
        if (b->free) nfree_phys++;
        prev = b;
    }
 
    if (total != ARENA_SIZE)
        return HEAP_ERR_TOTAL;
 
    /* Cross-check the explicit free list against the physical walk. */
    size_t nfree_list = 0;
    size_t guard = nblocks + 1;
    for (block_t *f = free_list; f; f = f->next_free) {
        if (guard-- == 0) return HEAP_ERR_FREELIST; /* cycle */
        unsigned char *fb = (unsigned char *)f;
        if (fb < arena || fb + HEADER_SIZE + f->size + FOOTER_SIZE > arena + ARENA_SIZE)
            return HEAP_ERR_FREELIST;
        if (!f->free)        return HEAP_ERR_FREELIST;
        if (!canaries_ok(f)) return HEAP_ERR_FREELIST;
        if (f->next_free && f->next_free->prev_free != f)
            return HEAP_ERR_FREELIST;
        nfree_list++;
    }
    if (nfree_list != nfree_phys)
        return HEAP_ERR_FREELIST;
 
    return HEAP_OK;
}
 
391 linesc
Writes …/alloc.c
Files at this step
drag the rail to scrub
Discussion

No comments yet. Start the discussion. Recorded by @patrick-toulme.
#c #claude #claude-code #claude-opus-4-8 #medium
w1-claude
← all sessions