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 10 / 20
alloc.cchange 1/1
#include "alloc.h"
#include <string.h>
 
#define ALIGNMENT 16
#define CANARY_HEAD 0xCAFEBABE
#define CANARY_FOOT 0xDEADBEEF
 
typedef struct block_header {
    uint32_t magic_head;
    uint32_t is_free;
    size_t   size;               // Total block size (header + payload + footer), aligned to 16
    size_t   req_size;           // User-requested payload size
    struct block_header *next_free;
    struct block_header *prev_free;
    uint64_t pad;                // Keeps sizeof(block_header_t) == 48 (multiple of 16)
} block_header_t;
 
typedef struct block_footer {
    uint32_t magic_foot;
    uint32_t pad;
    size_t   size;               // Must match block_header_t->size
} block_footer_t;                // sizeof(block_footer_t) == 16
 
#define HEADER_SIZE (sizeof(block_header_t)) // 48
#define FOOTER_SIZE (sizeof(block_footer_t)) // 16
#define MIN_PAYLOAD 16
#define MIN_BLOCK_SIZE (HEADER_SIZE + MIN_PAYLOAD + FOOTER_SIZE) // 80
 
static uint8_t g_arena[ARENA_SIZE] __attribute__((aligned(16)));
static block_header_t *g_free_list = NULL;
static bool g_initialized = false;
 
static inline size_t align_up(size_t size, size_t align) {
    return (size + (align - 1)) & ~(align - 1);
}
 
static void free_list_add(block_header_t *block) {
    block->next_free = g_free_list;
    block->prev_free = NULL;
    if (g_free_list != NULL) {
        g_free_list->prev_free = block;
    }
    g_free_list = block;
}
 
static void free_list_remove(block_header_t *block) {
    if (block->prev_free != NULL) {
        block->prev_free->next_free = block->next_free;
    } else {
        g_free_list = block->next_free;
    }
    if (block->next_free != NULL) {
        block->next_free->prev_free = block->prev_free;
    }
    block->next_free = NULL;
    block->prev_free = NULL;
}
 
void my_init(void) {
    block_header_t *initial_block = (block_header_t *)g_arena;
    initial_block->magic_head = CANARY_HEAD;
    initial_block->is_free = 1;
    initial_block->size = ARENA_SIZE;
    initial_block->req_size = 0;
    initial_block->next_free = NULL;
    initial_block->prev_free = NULL;
    initial_block->pad = 0;
 
    block_footer_t *initial_footer = (block_footer_t *)(g_arena + ARENA_SIZE - FOOTER_SIZE);
    initial_footer->magic_foot = CANARY_FOOT;
    initial_footer->pad = 0;
    initial_footer->size = ARENA_SIZE;
 
    g_free_list = initial_block;
    g_initialized = true;
}
 
void *my_malloc(size_t size) {
    if (size == 0) return NULL;
    if (!g_initialized) my_init();
 
    size_t payload_size = align_up(size, ALIGNMENT);
    if (payload_size < MIN_PAYLOAD) {
        payload_size = MIN_PAYLOAD;
    }
 
    size_t needed_block_size = HEADER_SIZE + payload_size + FOOTER_SIZE;
    if (needed_block_size < size) return NULL; // Overflow guard
 
    // First-fit search on free list
    block_header_t *curr = g_free_list;
    while (curr != NULL) {
        if (curr->size >= needed_block_size) {
            break;
        }
        curr = curr->next_free;
    }
 
    if (curr == NULL) {
        return NULL; // Out of memory
    }
 
    size_t rem_size = curr->size - needed_block_size;
    if (rem_size >= MIN_BLOCK_SIZE) {
        // Split block
        block_header_t *split_free = (block_header_t *)((char *)curr + needed_block_size);
        split_free->magic_head = CANARY_HEAD;
        split_free->is_free = 1;
        split_free->size = rem_size;
        split_free->req_size = 0;
        split_free->next_free = NULL;
        split_free->prev_free = NULL;
        split_free->pad = 0;
 
        block_footer_t *split_ftr = (block_footer_t *)((char *)split_free + rem_size - FOOTER_SIZE);
        split_ftr->magic_foot = CANARY_FOOT;
        split_ftr->pad = 0;
        split_ftr->size = rem_size;
 
        // Replace curr with split_free in free list
        free_list_remove(curr);
        free_list_add(split_free);
 
        curr->size = needed_block_size;
    } else {
        // Use whole block without splitting
        free_list_remove(curr);
    }
 
    curr->magic_head = CANARY_HEAD;
    curr->is_free = 0;
    curr->req_size = size;
 
    block_footer_t *curr_ftr = (block_footer_t *)((char *)curr + curr->size - FOOTER_SIZE);
    curr_ftr->magic_foot = CANARY_FOOT;
    curr_ftr->pad = 0;
    curr_ftr->size = curr->size;
 
    return (void *)((char *)curr + HEADER_SIZE);
}
 
void my_free(void *ptr) {
    if (ptr == NULL) return;
    if (!g_initialized) return;
 
    char *p = (char *)ptr;
    if (p < (char *)g_arena + HEADER_SIZE || p >= (char *)g_arena + ARENA_SIZE - FOOTER_SIZE) {
        return;
    }
 
    if (((uintptr_t)p % ALIGNMENT) != 0) {
        return;
    }
 
    block_header_t *hdr = (block_header_t *)(p - HEADER_SIZE);
    if (hdr->magic_head != CANARY_HEAD || hdr->is_free != 0) {
        return;
    }
 
    block_footer_t *ftr = (block_footer_t *)((char *)hdr + hdr->size - FOOTER_SIZE);
    if (ftr->magic_foot != CANARY_FOOT || ftr->size != hdr->size) {
        return;
    }
 
    hdr->is_free = 1;
    hdr->req_size = 0;
 
    block_header_t *merged = hdr;
 
    // Coalesce Right neighbor
    char *right_addr = (char *)hdr + hdr->size;
    if (right_addr < (char *)g_arena + ARENA_SIZE) {
        block_header_t *right_hdr = (block_header_t *)right_addr;
        if (right_hdr->magic_head == CANARY_HEAD && right_hdr->is_free == 1) {
            free_list_remove(right_hdr);
            merged->size += right_hdr->size;
        }
    }
 
    // Coalesce Left neighbor
    char *left_ftr_addr = (char *)hdr - FOOTER_SIZE;
    if (left_ftr_addr >= (char *)g_arena) {
        block_footer_t *left_ftr = (block_footer_t *)left_ftr_addr;
        if (left_ftr->magic_foot == CANARY_FOOT) {
            block_header_t *left_hdr = (block_header_t *)((char *)hdr - left_ftr->size);
            if ((char *)left_hdr >= (char *)g_arena &&
                left_hdr->magic_head == CANARY_HEAD &&
                left_hdr->is_free == 1) {
                free_list_remove(left_hdr);
                left_hdr->size += merged->size;
                merged = left_hdr;
            }
        }
    }
 
    merged->magic_head = CANARY_HEAD;
    merged->is_free = 1;
    merged->req_size = 0;
 
    block_footer_t *merged_ftr = (block_footer_t *)((char *)merged + merged->size - FOOTER_SIZE);
    merged_ftr->magic_foot = CANARY_FOOT;
    merged_ftr->pad = 0;
    merged_ftr->size = merged->size;
 
    free_list_add(merged);
}
 
void *my_calloc(size_t nmemb, size_t size) {
    if (nmemb != 0 && size > SIZE_MAX / nmemb) {
        return NULL;
    }
    size_t total = nmemb * size;
    void *ptr = my_malloc(total);
    if (ptr != NULL && total > 0) {
        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;
    }
 
    char *p = (char *)ptr;
    if (p < (char *)g_arena + HEADER_SIZE || p >= (char *)g_arena + ARENA_SIZE - FOOTER_SIZE) {
        return NULL;
    }
    if (((uintptr_t)p % ALIGNMENT) != 0) {
        return NULL;
    }
 
    block_header_t *hdr = (block_header_t *)(p - HEADER_SIZE);
    if (hdr->magic_head != CANARY_HEAD || hdr->is_free != 0) {
        return NULL;
    }
 
    block_footer_t *ftr = (block_footer_t *)((char *)hdr + hdr->size - FOOTER_SIZE);
    if (ftr->magic_foot != CANARY_FOOT || ftr->size != hdr->size) {
        return NULL;
    }
 
    size_t curr_cap = hdr->size - HEADER_SIZE - FOOTER_SIZE;
    if (size <= curr_cap) {
        hdr->req_size = size;
        return ptr;
    }
 
    // Try in-place expansion into right neighbor if free
    size_t payload_size = align_up(size, ALIGNMENT);
    if (payload_size < MIN_PAYLOAD) payload_size = MIN_PAYLOAD;
    size_t needed_block_size = HEADER_SIZE + payload_size + FOOTER_SIZE;
 
    char *right_addr = (char *)hdr + hdr->size;
    if (right_addr < (char *)g_arena + ARENA_SIZE) {
        block_header_t *right_hdr = (block_header_t *)right_addr;
        if (right_hdr->magic_head == CANARY_HEAD && right_hdr->is_free == 1) {
            size_t combined_size = hdr->size + right_hdr->size;
            if (combined_size >= needed_block_size) {
                free_list_remove(right_hdr);
                size_t rem_size = combined_size - needed_block_size;
                if (rem_size >= MIN_BLOCK_SIZE) {
                    block_header_t *split_free = (block_header_t *)((char *)hdr + needed_block_size);
                    split_free->magic_head = CANARY_HEAD;
                    split_free->is_free = 1;
                    split_free->size = rem_size;
                    split_free->req_size = 0;
                    split_free->next_free = NULL;
                    split_free->prev_free = NULL;
                    split_free->pad = 0;
 
                    block_footer_t *split_ftr = (block_footer_t *)((char *)split_free + rem_size - FOOTER_SIZE);
                    split_ftr->magic_foot = CANARY_FOOT;
                    split_ftr->pad = 0;
                    split_ftr->size = rem_size;
 
                    free_list_add(split_free);
                    hdr->size = needed_block_size;
                } else {
                    hdr->size = combined_size;
                }
 
                hdr->req_size = size;
                block_footer_t *hdr_ftr = (block_footer_t *)((char *)hdr + hdr->size - FOOTER_SIZE);
                hdr_ftr->magic_foot = CANARY_FOOT;
                hdr_ftr->pad = 0;
                hdr_ftr->size = hdr->size;
 
                return ptr;
            }
        }
    }
 
    // Allocate new block & copy
    void *new_ptr = my_malloc(size);
    if (new_ptr == NULL) {
        return NULL;
    }
 
    size_t copy_size = hdr->req_size < size ? hdr->req_size : size;
    memcpy(new_ptr, ptr, copy_size);
    my_free(ptr);
 
    return new_ptr;
}
 
bool my_heap_check(void) {
    if (!g_initialized) {
        return true;
    }
 
    char *curr_addr = (char *)g_arena;
    size_t total_size_seen = 0;
    size_t free_blocks_physical = 0;
    block_header_t *prev_phys_hdr = NULL;
 
    while (curr_addr < (char *)g_arena + ARENA_SIZE) {
        if (((uintptr_t)curr_addr % ALIGNMENT) != 0) {
            return false;
        }
 
        block_header_t *hdr = (block_header_t *)curr_addr;
        if (hdr->magic_head != CANARY_HEAD) {
            return false;
        }
 
        if (hdr->is_free != 0 && hdr->is_free != 1) {
            return false;
        }
 
        if (hdr->size < MIN_BLOCK_SIZE || (hdr->size % ALIGNMENT) != 0) {
            return false;
        }
 
        if (curr_addr + hdr->size > (char *)g_arena + ARENA_SIZE) {
            return false;
        }
 
        block_footer_t *ftr = (block_footer_t *)(curr_addr + hdr->size - FOOTER_SIZE);
        if (ftr->magic_foot != CANARY_FOOT || ftr->size != hdr->size) {
            return false;
        }
 
        if (hdr->is_free == 1) {
            if (hdr->req_size != 0) {
                return false;
            }
            // Coalescing check: two consecutive physical free blocks are forbidden
            if (prev_phys_hdr != NULL && prev_phys_hdr->is_free == 1) {
                return false;
            }
            free_blocks_physical++;
        } else {
            size_t max_payload = hdr->size - HEADER_SIZE - FOOTER_SIZE;
            if (hdr->req_size > max_payload) {
                return false;
            }
        }
 
        prev_phys_hdr = hdr;
        total_size_seen += hdr->size;
        curr_addr += hdr->size;
    }
 
    if (total_size_seen != ARENA_SIZE) {
        return false;
    }
 
    // Validate free list integrity
    size_t free_list_count = 0;
    block_header_t *f = g_free_list;
    while (f != NULL) {
        char *f_addr = (char *)f;
        if (f_addr < (char *)g_arena || f_addr >= (char *)g_arena + ARENA_SIZE) {
            return false;
        }
 
        if (f->magic_head != CANARY_HEAD || f->is_free != 1) {
            return false;
        }
 
        if (f->next_free != NULL) {
            if (f->next_free->prev_free != f) {
                return false;
            }
        }
 
        free_list_count++;
        if (free_list_count > ARENA_SIZE / MIN_BLOCK_SIZE) {
            return false; // Cycle detection guard
        }
 
        f = f->next_free;
    }
 
    if (free_list_count != free_blocks_physical) {
        return false;
    }
 
    return true;
}
 
void my_stats(stats_t *out_stats) {
    if (out_stats == NULL) return;
    if (!g_initialized) my_init();
 
    size_t bytes_in_use = 0;
    size_t free_block_count = 0;
    size_t largest_free_block = 0;
 
    char *curr_addr = (char *)g_arena;
    while (curr_addr < (char *)g_arena + ARENA_SIZE) {
        block_header_t *hdr = (block_header_t *)curr_addr;
        if (hdr->magic_head == CANARY_HEAD) {
            if (hdr->is_free == 0) {
                bytes_in_use += hdr->req_size;
            } else {
                free_block_count++;
                size_t payload_cap = hdr->size - HEADER_SIZE - FOOTER_SIZE;
                if (payload_cap > largest_free_block) {
                    largest_free_block = payload_cap;
                }
            }
            curr_addr += hdr->size;
        } else {
            break;
        }
    }
 
    out_stats->bytes_in_use = bytes_in_use;
    out_stats->free_block_count = free_block_count;
    out_stats->largest_free_block = largest_free_block;
}
 
438 linesc
Writes …/tests.c
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