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

antigravitygemini · 20 steps · 49s · 4 filessession b2e47f91-007@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 12 / 20

tests.cchange 1/2

#include "alloc.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>
#include <stdbool.h>
 
static uint32_t g_rng = 0x12345678;
 
static uint32_t my_rand(void) {
    g_rng ^= g_rng << 13;
    g_rng ^= g_rng >> 17;
    g_rng ^= g_rng << 5;
    return g_rng;
}
 
static void fill_pattern(uint8_t *ptr, size_t size, uint32_t seed) {
    for (size_t i = 0; i < size; i++) {
        ptr[i] = (uint8_t)((seed + i) & 0xFF);
    }
}
 
static bool verify_pattern(const uint8_t *ptr, size_t size, uint32_t seed) {
    for (size_t i = 0; i < size; i++) {
        if (ptr[i] != (uint8_t)((seed + i) & 0xFF)) {
            return false;
        }
    }
    return true;
}
 
static void test_basic_and_alignment(void) {
    printf("[TEST] Running basic and alignment tests...\n");
    my_init();
    assert(my_heap_check());
 
    // my_malloc(0) should return NULL
    assert(my_malloc(0) == NULL);
 
    // my_free(NULL) should be safe
    my_free(NULL);
 
    // Alignment test
    size_t test_sizes[] = {1, 3, 7, 15, 16, 17, 31, 32, 64, 100, 255, 512, 1024, 4096};
    void *ptrs[14];
    for (size_t i = 0; i < 14; i++) {
        ptrs[i] = my_malloc(test_sizes[i]);
        assert(ptrs[i] != NULL);
        assert(((uintptr_t)ptrs[i] % 16) == 0);
        fill_pattern((uint8_t *)ptrs[i], test_sizes[i], (uint32_t)i);
    }
 
    assert(my_heap_check());
 
    for (size_t i = 0; i < 14; i++) {
        assert(verify_pattern((const uint8_t *)ptrs[i], test_sizes[i], (uint32_t)i));
        my_free(ptrs[i]);
    }
 
    assert(my_heap_check());
    stats_t st;
    my_stats(&st);
    assert(st.bytes_in_use == 0);
    assert(st.free_block_count == 1);
    printf("       -> Basic & Alignment tests PASSED.\n");
}
 
static void test_calloc(void) {
    printf("[TEST] Running my_calloc tests...\n");
    my_init();
 
    size_t count = 128;
    size_t elem_size = sizeof(int);
    int *arr = (int *)my_calloc(count, elem_size);
    assert(arr != NULL);
    assert(((uintptr_t)arr % 16) == 0);
 
    for (size_t i = 0; i < count; i++) {
        assert(arr[i] == 0);
    }
 
    assert(my_heap_check());
    my_free(arr);
    assert(my_heap_check());
    printf("       -> my_calloc tests PASSED.\n");
}
 
static void test_fragmentation_and_coalescing(void) {
    printf("[TEST] Running fragmentation & coalescing scenario tests...\n");
    my_init();
 
    stats_t init_st;
    my_stats(&init_st);
    size_t max_payload = init_st.largest_free_block;
    assert(init_st.free_block_count == 1);
 
    #define NUM_BLOCKS 50
    void *blocks[NUM_BLOCKS];
    size_t blk_size = 2048;
 
    for (int i = 0; i < NUM_BLOCKS; i++) {
        blocks[i] = my_malloc(blk_size);
        assert(blocks[i] != NULL);
        fill_pattern((uint8_t *)blocks[i], blk_size, (uint32_t)i);
    }
 
    assert(my_heap_check());
 
    // Free alternating blocks (even indices)
    for (int i = 0; i < NUM_BLOCKS; i += 2) {
        assert(verify_pattern((const uint8_t *)blocks[i], blk_size, (uint32_t)i));
        my_free(blocks[i]);
        blocks[i] = NULL;
    }
 
    assert(my_heap_check());
    stats_t frag_st;
    my_stats(&frag_st);
    assert(frag_st.free_block_count > 1);
 
    // Free remaining odd blocks
    for (int i = 1; i < NUM_BLOCKS; i += 2) {
        assert(verify_pattern((const uint8_t *)blocks[i], blk_size, (uint32_t)i));
        my_free(blocks[i]);
        blocks[i] = NULL;
    }
 
    // Verify full coalescing
    assert(my_heap_check());
    stats_t end_st;
    my_stats(&end_st);
    assert(end_st.bytes_in_use == 0);
    assert(end_st.free_block_count == 1);
    assert(end_st.largest_free_block == max_payload);
 
    // Out-of-order freeing (middle, left, right)
    void *a = my_malloc(1024);
    void *b = my_malloc(1024);
    void *c = my_malloc(1024);
    assert(a && b && c);
 
    my_free(b); // Free middle
    assert(my_heap_check());
    my_free(a); // Free left (should coalesce with b)
    assert(my_heap_check());
    my_free(c); // Free right (should coalesce with a+b)
    assert(my_heap_check());
 
    my_stats(&end_st);
    assert(end_st.bytes_in_use == 0);
    assert(end_st.free_block_count == 1);
    assert(end_st.largest_free_block == max_payload);
 
    printf("       -> Fragmentation & coalescing tests PASSED.\n");
    #undef NUM_BLOCKS
}
 
static void test_canary_violation(void) {
    printf("[TEST] Running canary-violation detection tests...\n");
    my_init();
 
    void *p = my_malloc(64);
    assert(p != NULL);
    assert(my_heap_check() == true);
 
    // Corrupt header canary
    uint32_t *hdr_canary = (uint32_t *)((char *)p - 48); // magic_head is at offset 0 of header (48 bytes before payload)
    uint32_t orig_val = *hdr_canary;
    *hdr_canary = 0xBADBAD00;
 
    // my_heap_check() MUST detect corruption!
    assert(my_heap_check() == false);
 
    // Restore header canary
    *hdr_canary = orig_val;
    assert(my_heap_check() == true);
 
    // Corrupt footer canary
    // Footer canary is 4 bytes at offset (hdr->size - 16) from header
    // Header size for 64-byte payload: 48 (hdr) + 64 (payload) + 16 (ftr) = 128 bytes total
    uint32_t *ftr_canary = (uint32_t *)((char *)p + 64); // payload is 64 bytes, footer starts immediately at p + 64
    uint32_t orig_ftr_val = *ftr_canary;
    *ftr_canary = 0xDEAD0000;
 
    assert(my_heap_check() == false);
 
    // Clean up / reset
    my_init();
    assert(my_heap_check() == true);
    printf("       -> Canary-violation tests PASSED.\n");
}
 
#define SHADOW_CAP 2000
#define STRESS_OPS 100000
 
typedef struct {
    void *ptr;
    size_t size;
    uint32_t seed;
    bool active;
} shadow_slot_t;
 
static shadow_slot_t g_slots[SHADOW_CAP];
static int g_active_indices[SHADOW_CAP];
static int g_active_count = 0;
 
static void test_seeded_stress(void) {
    printf("[TEST] Running 100k seeded stress test...\n");
    my_init();
    g_rng = 0xA5A5A5A5; // Fixed seed for reproducibility
 
    memset(g_slots, 0, sizeof(g_slots));
    g_active_count = 0;
 
    for (int op = 0; op < STRESS_OPS; op++) {
        uint32_t roll = my_rand() % 100;
 
        if (roll < 45) {
            // MALLOC (45%)
            if (g_active_count < SHADOW_CAP) {
                size_t sz = 1 + (my_rand() % 2048);
                void *ptr = my_malloc(sz);
                if (ptr != NULL) {
                    assert(((uintptr_t)ptr % 16) == 0);
                    uint32_t sd = my_rand();
 
                    // Find empty slot
                    int slot_idx = -1;
                    for (int i = 0; i < SHADOW_CAP; i++) {
                        if (!g_slots[i].active) {
                            slot_idx = i;
                            break;
                        }
                    }
                    assert(slot_idx != -1);
 
                    g_slots[slot_idx].ptr = ptr;
                    g_slots[slot_idx].size = sz;
                    g_slots[slot_idx].seed = sd;
                    g_slots[slot_idx].active = true;
 
                    fill_pattern((uint8_t *)ptr, sz, sd);
 
                    g_active_indices[g_active_count++] = slot_idx;
                }
            }
        } else if (roll < 85) {
            // FREE (40%)
            if (g_active_count > 0) {
                int pick = my_rand() % g_active_count;
                int slot_idx = g_active_indices[pick];
 
                assert(g_slots[slot_idx].active);
                assert(verify_pattern((const uint8_t *)g_slots[slot_idx].ptr, g_slots[slot_idx].size, g_slots[slot_idx].seed));
 
                my_free(g_slots[slot_idx].ptr);
                g_slots[slot_idx].active = false;
 
                g_active_indices[pick] = g_active_indices[g_active_count - 1];
                g_active_count--;
            }
        } else {
            // REALLOC (15%)
            if (g_active_count > 0) {
                int pick = my_rand() % g_active_count;
                int slot_idx = g_active_indices[pick];
 
                assert(g_slots[slot_idx].active);
                assert(verify_pattern((const uint8_t *)g_slots[slot_idx].ptr, g_slots[slot_idx].size, g_slots[slot_idx].seed));
 
                size_t new_sz = 1 + (my_rand() % 2048);
                uint32_t new_sd = my_rand();
 
                void *new_ptr = my_realloc(g_slots[slot_idx].ptr, new_sz);
                if (new_ptr != NULL) {
                    assert(((uintptr_t)new_ptr % 16) == 0);
                    g_slots[slot_idx].ptr = new_ptr;
                    g_slots[slot_idx].size = new_sz;
                    g_slots[slot_idx].seed = new_sd;
 
                    fill_pattern((uint8_t *)new_ptr, new_sz, new_sd);
                }
            }
        }
 
        if ((op + 1) % 25000 == 0) {
            assert(my_heap_check() == true);
            printf("       -> Progress: %d / %d operations complete...\n", op + 1, STRESS_OPS);
        }
    }
 
    assert(my_heap_check() == true);
 
    // Free all remaining active allocations
    for (int i = 0; i < g_active_count; i++) {
        int slot_idx = g_active_indices[i];
        assert(g_slots[slot_idx].active);
        assert(verify_pattern((const uint8_t *)g_slots[slot_idx].ptr, g_slots[slot_idx].size, g_slots[slot_idx].seed));
        my_free(g_slots[slot_idx].ptr);
        g_slots[slot_idx].active = false;
    }
    g_active_count = 0;
 
    assert(my_heap_check() == true);
    stats_t final_st;
    my_stats(&final_st);
    assert(final_st.bytes_in_use == 0);
    assert(final_st.free_block_count == 1);
 
    printf("       -> 100k Seeded Stress test PASSED.\n");
}
 
int main(void) {
    printf("=== RUNNING MEMORY ALLOCATOR TEST SUITE ===\n\n");
    test_basic_and_alignment();
    test_calloc();
    test_fragmentation_and_coalescing();
    test_canary_violation();
    test_seeded_stress();
    printf("\n=== ALL TESTS PASSED CLEANLY! ===\n");
    return 0;
}
 

324 linesc

Writes …/Makefile

Files at this step

drag the rail to scrub

Discussion

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

#antigravity #c #gemini #quick

w5-agy

← all sessions