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 11 / 51

tests.cchange 1/1

#include "alloc.h"
 
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* Fail loudly and abort regardless of NDEBUG. */
#define CHECK(cond, msg)                                                     \
    do {                                                                     \
        if (!(cond)) {                                                       \
            fprintf(stderr, "FAILED: %s\n  at %s:%d\n", (msg),               \
                    __FILE__, __LINE__);                                     \
            exit(1);                                                         \
        }                                                                    \
    } while (0)
 
/* ------------------------------------------------------------------------- *
 *  Deterministic PRNG (xorshift64). Same seed => same sequence everywhere.
 * ------------------------------------------------------------------------- */
 
static uint64_t rng_state;
 
static void rng_seed(uint64_t s) { rng_state = s ? s : 0x9e3779b97f4a7c15ull; }
 
static uint64_t rng_next(void) {
    uint64_t x = rng_state;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    rng_state = x;
    return x;
}
 
static uint32_t rng_range(uint32_t n) { return (uint32_t)(rng_next() % n); }
 
/* ------------------------------------------------------------------------- *
 *  Position-dependent fill so overlapping allocations are caught: byte i is
 *  (seed + i). A different seed per allocation gives a fresh pattern.
 * ------------------------------------------------------------------------- */
 
static void fill_pattern(unsigned char *p, size_t n, uint8_t seed) {
    for (size_t i = 0; i < n; i++) p[i] = (uint8_t)(seed + (uint8_t)i);
}
 
static int verify_pattern(const unsigned char *p, size_t n, uint8_t seed) {
    for (size_t i = 0; i < n; i++)
        if (p[i] != (uint8_t)(seed + (uint8_t)i)) return 0;
    return 1;
}
 
/* ------------------------------------------------------------------------- *
 *  Test: basic API semantics
 * ------------------------------------------------------------------------- */
 
static void test_basics(void) {
    CHECK(my_malloc(0) == NULL, "malloc(0) must return NULL");
    CHECK(my_realloc(NULL, 0) == NULL, "realloc(NULL,0) must return NULL");
 
    /* realloc(NULL, n) == malloc(n) */
    unsigned char *a = my_realloc(NULL, 100);
    CHECK(a != NULL, "realloc(NULL,100) should allocate");
    fill_pattern(a, 100, 0x11);
 
    /* grow: prefix preserved */
    unsigned char *b = my_realloc(a, 5000);
    CHECK(b != NULL, "grow realloc should succeed");
    CHECK(verify_pattern(b, 100, 0x11), "grow must preserve bytes");
 
    /* shrink: prefix preserved, realloc(p,0) frees */
    unsigned char *c = my_realloc(b, 40);
    CHECK(c != NULL, "shrink realloc should succeed");
    CHECK(verify_pattern(c, 40, 0x11), "shrink must preserve bytes");
    CHECK(my_realloc(c, 0) == NULL, "realloc(p,0) frees and returns NULL");
 
    /* calloc zeroes and rejects overflow */
    size_t n = 64;
    unsigned char *z = my_calloc(n, 4);
    CHECK(z != NULL, "calloc should succeed");
    for (size_t i = 0; i < n * 4; i++) CHECK(z[i] == 0, "calloc must zero memory");
    my_free(z);
    CHECK(my_calloc((size_t)-1, 2) == NULL, "calloc overflow must return NULL");
 
    my_free(NULL); /* no-op */
 
    CHECK(my_heap_check() == HEAP_OK, "heap consistent after basics");
    heap_stats_t s;
    my_stats(&s);
    CHECK(s.bytes_in_use == 0, "everything freed after basics");
    CHECK(s.free_blocks == 1, "fully coalesced after basics");
    CHECK(s.largest_free_block == my_heap_capacity(), "full capacity recovered");
 
    printf("  [ok] basics: malloc/free/calloc/realloc semantics\n");
}
 
/* ------------------------------------------------------------------------- *
 *  Test: fragmentation, then coalescing recovers the largest block
 * ------------------------------------------------------------------------- */
 
static void test_fragmentation(void) {
    heap_stats_t s;
    my_stats(&s);
    const size_t initial_largest = s.largest_free_block;
    CHECK(initial_largest == my_heap_capacity(), "start from an empty heap");
 
    /* Fill the arena with same-sized blocks so there is no big free tail. */
    enum { CAP = 512 };
    void *blk[CAP];
    int n = 0;
    while (n < CAP) {
        void *p = my_malloc(4096);
        if (!p) break;
        blk[n++] = p;
    }
    CHECK(n > 8, "should place many blocks before the arena fills");
    CHECK(my_heap_check() == HEAP_OK, "heap consistent when full");
 
    my_stats(&s);
    CHECK(s.largest_free_block < 4096 + 4096, "arena is essentially full");
 
    /* Punch holes: free every other block. Each hole is walled off by its
     * still-allocated neighbours, so no coalescing can happen yet. */
    for (int i = 0; i < n; i += 2) {
        my_free(blk[i]);
        blk[i] = NULL;
    }
    CHECK(my_heap_check() == HEAP_OK, "heap consistent while fragmented");
 
    my_stats(&s);
    const size_t fragmented_largest = s.largest_free_block;
    CHECK(fragmented_largest < initial_largest / 4,
          "fragmented heap has no large contiguous block");
    CHECK(s.free_blocks > 4, "fragmentation produced many free blocks");
 
    /* Now free the rest. Adjacent frees must coalesce back into one block. */
    for (int i = 1; i < n; i += 2) {
        if (blk[i]) my_free(blk[i]);
        blk[i] = NULL;
    }
    CHECK(my_heap_check() == HEAP_OK, "heap consistent after full free");
 
    my_stats(&s);
    CHECK(s.free_blocks == 1, "coalescing must collapse to a single free block");
    CHECK(s.largest_free_block == initial_largest,
          "coalescing must recover the full-size largest block");
 
    printf("  [ok] fragmentation: fragmented to %zu bytes, coalesced back to %zu\n",
           fragmented_largest, s.largest_free_block);
}
 
/* ------------------------------------------------------------------------- *
 *  Test: a buffer overflow that smashes a canary is detected
 * ------------------------------------------------------------------------- */
 
static void test_canary(void) {
    CHECK(my_heap_check() == HEAP_OK, "heap clean before canary test");
 
    /* Request a multiple of 16 so the payload exactly abuts the footer canary:
     * writing one byte past the request lands on the canary. */
    const size_t n = 64;
    unsigned char *p = my_malloc(n);
    CHECK(p != NULL, "canary test allocation");
    fill_pattern(p, n, 0x5a);
    CHECK(my_heap_check() == HEAP_OK, "heap clean with a valid canary");
 
    /* Simulate a one-past-the-end overflow into the footer canary. The write
     * stays inside the static arena object, so it is invisible to ASan -- which
     * is exactly why we need our own canary to catch it. */
    unsigned char *overflow = p + n;
    unsigned char saved[8];
    memcpy(saved, overflow, sizeof saved);
    overflow[0] ^= 0xFF;
 
    int rc = my_heap_check();
    CHECK(rc == HEAP_ERR_FOOT_CANARY, "overflow must be reported as a footer-canary violation");
 
    /* Repair the canary and confirm the validator agrees the heap is clean. */
    memcpy(overflow, saved, sizeof saved);
    CHECK(my_heap_check() == HEAP_OK, "heap clean after repairing the canary");
    CHECK(verify_pattern(p, n, 0x5a), "user bytes intact after repair");
 
    my_free(p);
    CHECK(my_heap_check() == HEAP_OK, "heap clean after freeing canary block");
 
    printf("  [ok] canary: footer overflow detected (code %d) and validated clean after repair\n", rc);
}
 
/* ------------------------------------------------------------------------- *
 *  Test: seeded stress test mirrored against a shadow table
 * ------------------------------------------------------------------------- */
 
static void test_stress(void) {
    enum { NSLOTS = 256, MAXSZ = 4096, NOPS = 100000, CHECK_EVERY = 1000 };
 
    typedef struct {
        unsigned char *ptr;
        size_t         size;
        uint8_t        seed;
    } slot_t;
 
    static slot_t slot[NSLOTS]; /* static: 256 * 24 bytes, keep off the C stack */
    memset(slot, 0, sizeof slot);
 
    rng_seed(0xC0FFEEull);
 
    unsigned long n_malloc = 0, n_calloc = 0, n_free = 0;
    unsigned long n_realloc = 0, n_oom = 0, n_verify = 0;
 
    for (int op = 0; op < NOPS; op++) {
        uint32_t i = rng_range(NSLOTS);
        slot_t *sp = &slot[i];
 
        if (sp->ptr == NULL) {
            /* Empty slot: allocate via malloc or calloc. */
            size_t sz = 1 + rng_range(MAXSZ);
            unsigned char *p;
            if (rng_range(2) == 0) {
                p = my_malloc(sz);
                n_malloc++;
            } else {
                p = my_calloc(sz, 1);
                n_calloc++;
                if (p)
                    for (size_t k = 0; k < sz; k++)
                        CHECK(p[k] == 0, "calloc memory must be zeroed");
            }
            if (!p) { n_oom++; continue; } /* arena full/fragmented: fine */
 
            uint8_t seed = (uint8_t)rng_next();
            fill_pattern(p, sz, seed);
            sp->ptr = p;
            sp->size = sz;
            sp->seed = seed;
        } else {
            /* Occupied slot: verify, then free / realloc / just re-verify. */
            CHECK(verify_pattern(sp->ptr, sp->size, sp->seed),
                  "shadow pattern must match before touching a block");
            n_verify++;
 
            uint32_t what = rng_range(3);
            if (what == 0) {
                my_free(sp->ptr);
                n_free++;
                sp->ptr = NULL;
                sp->size = 0;
            } else if (what == 1) {
                size_t nsz = 1 + rng_range(MAXSZ);
                unsigned char *q = my_realloc(sp->ptr, nsz);
                n_realloc++;
                if (q) {
                    size_t keep = sp->size < nsz ? sp->size : nsz;
                    CHECK(verify_pattern(q, keep, sp->seed),
                          "realloc must preserve the overlapping prefix");
                    uint8_t ns = (uint8_t)rng_next();
                    fill_pattern(q, nsz, ns);
                    sp->ptr = q;
                    sp->size = nsz;
                    sp->seed = ns;
                } else {
                    /* Failed grow: the original must be untouched. */
                    n_oom++;
                    CHECK(verify_pattern(sp->ptr, sp->size, sp->seed),
                          "failed realloc must leave the original intact");
                }
            }
            /* what == 2: leave it allocated; the verify above already ran. */
        }
 
        if (op % CHECK_EVERY == 0)
            CHECK(my_heap_check() == HEAP_OK, "heap must stay consistent under stress");
    }
 
    /* Drain: verify and free everything still outstanding. */
    for (int i = 0; i < NSLOTS; i++) {
        if (slot[i].ptr) {
            CHECK(verify_pattern(slot[i].ptr, slot[i].size, slot[i].seed),
                  "final shadow pattern must match");
            my_free(slot[i].ptr);
            slot[i].ptr = NULL;
        }
    }
 
    CHECK(my_heap_check() == HEAP_OK, "heap consistent after draining");
    heap_stats_t s;
    my_stats(&s);
    CHECK(s.bytes_in_use == 0, "nothing should remain in use");
    CHECK(s.free_blocks == 1, "heap must coalesce to a single free block");
    CHECK(s.largest_free_block == my_heap_capacity(), "full capacity recovered");
 
    printf("  [ok] stress: %d ops (malloc %lu, calloc %lu, realloc %lu, free %lu, "
           "verify %lu, oom %lu)\n",
           NOPS, n_malloc, n_calloc, n_realloc, n_free, n_verify, n_oom);
}
 
int main(void) {
    printf("running my_alloc tests...\n");
    test_basics();
    test_fragmentation();
    test_canary();
    test_stress();
    printf("ALL TESTS PASSED\n");
    return 0;
}
 

304 linesc

Now the Makefile:

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