Implement a memory allocator in C11 in this directory. Files: alloc.c, alloc.h (my_malloc, my_free, my_calloc, my_reallo

codexgpt-5.6-sol · 147 steps · 19m 51s · 5 filessession 169b7124-82e@agentsage-runs
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.
step 147 / 147
alloc.cchange 2/2
#include "alloc.h"
 
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
 
enum {
    BLOCK_FREE = 0x46524545u,
    BLOCK_USED = 0x55534544u,
    HEADER_VERSION = 0x00010001u
};
 
#define OFFSET_NONE UINT32_MAX
#define CANARY_SIZE ((size_t)sizeof(uint64_t))
 
typedef struct {
    uint64_t magic;
    uint64_t span;
    uint64_t requested;
    uint32_t prev_free;
    uint32_t next_free;
    uint32_t state;
    uint32_t version;
    uint64_t header_canary;
} BlockHeader;
 
#define HEADER_SIZE ((size_t)sizeof(BlockHeader))
#define MIN_BLOCK_SIZE \
    ((HEADER_SIZE + CANARY_SIZE + MY_ALIGNMENT - 1) & ~(MY_ALIGNMENT - 1))
#define MAX_BLOCKS (MY_ARENA_SIZE / MIN_BLOCK_SIZE)
 
_Static_assert(sizeof(BlockHeader) == 48, "block header must be 48 bytes");
_Static_assert(sizeof(BlockHeader) % MY_ALIGNMENT == 0,
               "block header must preserve payload alignment");
_Static_assert(MY_ARENA_SIZE % MY_ALIGNMENT == 0,
               "arena size must be alignment-sized");
_Static_assert(MY_ARENA_SIZE < UINT32_MAX,
               "free-list offsets must fit in uint32_t");
 
_Alignas(16) static unsigned char arena[MY_ARENA_SIZE];
static bool initialized;
static uint32_t free_head;
 
static const uint64_t [REDACTED];
static const uint64_t [REDACTED];
static const uint64_t [REDACTED];
 
static uint64_t mix64(uint64_t value)
{
    value ^= value >> 30;
    value *= UINT64_C(0xbf58476d1ce4e5b9);
    value ^= value >> 27;
    value *= UINT64_C(0x94d049bb133111eb);
    value ^= value >> 31;
    return value;
}
 
static uint64_t expected_magic(uint32_t offset)
{
    return mix64(MAGIC_SECRET ^ (uint64_t)offset);
}
 
static uint64_t expected_header_canary(uint32_t offset,
                                       const BlockHeader *header)
{
    uint64_t value = HEADER_SECRET ^ (uint64_t)offset;
 
    value = mix64(value ^ header->magic);
    value = mix64(value ^ header->span);
    value = mix64(value ^ header->requested);
    value = mix64(value ^ ((uint64_t)header->prev_free << 32) ^
                  (uint64_t)header->next_free);
    value = mix64(value ^ ((uint64_t)header->state << 32) ^
                  (uint64_t)header->version);
    return value;
}
 
static uint64_t expected_trailer_canary(uint32_t offset,
                                        const BlockHeader *header)
{
    uint64_t value = TRAILER_SECRET ^ (uint64_t)offset;
 
    value = mix64(value ^ header->span);
    value = mix64(value ^ header->requested);
    value = mix64(value ^ (uint64_t)header->state);
    return value;
}
 
static BlockHeader load_header(uint32_t offset)
{
    BlockHeader header;
 
    memcpy(&header, arena + offset, sizeof(header));
    return header;
}
 
static void seal_header(uint32_t offset, BlockHeader *header)
{
    header->magic = expected_magic(offset);
    header->version = HEADER_VERSION;
    header->header_canary = expected_header_canary(offset, header);
}
 
static void store_header(uint32_t offset, BlockHeader header)
{
    seal_header(offset, &header);
    memcpy(arena + offset, &header, sizeof(header));
}
 
static size_t trailer_offset(uint32_t offset, const BlockHeader *header)
{
    if (header->state == BLOCK_USED) {
        return (size_t)offset + HEADER_SIZE + (size_t)header->requested;
    }
    return (size_t)offset + (size_t)header->span - CANARY_SIZE;
}
 
static void store_block(uint32_t offset, BlockHeader header)
{
    uint64_t trailer;
    size_t tail;
 
    seal_header(offset, &header);
    memcpy(arena + offset, &header, sizeof(header));
 
    trailer = expected_trailer_canary(offset, &header);
    tail = trailer_offset(offset, &header);
    memcpy(arena + tail, &trailer, sizeof(trailer));
}
 
static void initialize_heap(void)
{
    BlockHeader initial;
 
    if (initialized) {
        return;
    }
 
    initial.magic = 0;
    initial.span = MY_ARENA_SIZE;
    initial.requested = 0;
    initial.prev_free = OFFSET_NONE;
    initial.next_free = OFFSET_NONE;
    initial.state = BLOCK_FREE;
    initial.version = 0;
    initial.header_canary = 0;
 
    free_head = 0;
    store_block(0, initial);
    initialized = true;
}
 
static bool valid_header(uint32_t offset, const BlockHeader *header)
{
    size_t remaining;
 
    if ((size_t)offset > MY_ARENA_SIZE - HEADER_SIZE ||
        (offset % MY_ALIGNMENT) != 0) {
        return false;
    }
    if (header->magic != expected_magic(offset) ||
        header->version != HEADER_VERSION) {
        return false;
    }
    if (header->state != BLOCK_FREE && header->state != BLOCK_USED) {
        return false;
    }
    if (header->span < MIN_BLOCK_SIZE ||
        (header->span % MY_ALIGNMENT) != 0) {
        return false;
    }
 
    remaining = MY_ARENA_SIZE - (size_t)offset;
    if (header->span > remaining) {
        return false;
    }
    if (header->requested >
        header->span - (uint64_t)HEADER_SIZE - (uint64_t)CANARY_SIZE) {
        return false;
    }
    if (header->state == BLOCK_FREE && header->requested != 0) {
        return false;
    }
    if (header->state == BLOCK_USED &&
        (header->requested == 0 || header->prev_free != OFFSET_NONE ||
         header->next_free != OFFSET_NONE)) {
        return false;
    }
    if (header->header_canary !=
        expected_header_canary(offset, header)) {
        return false;
    }
    return true;
}
 
static bool valid_block(uint32_t offset, const BlockHeader *header)
{
    uint64_t stored_trailer;
    size_t tail;
 
    if (!valid_header(offset, header)) {
        return false;
    }
 
    tail = trailer_offset(offset, header);
    memcpy(&stored_trailer, arena + tail, sizeof(stored_trailer));
    return stored_trailer == expected_trailer_canary(offset, header);
}
 
static bool required_span(size_t requested, size_t *result)
{
    size_t raw;
 
    if (requested == 0 ||
        requested > MY_ARENA_SIZE - HEADER_SIZE - CANARY_SIZE) {
        return false;
    }
    raw = HEADER_SIZE + requested + CANARY_SIZE;
    *result = (raw + MY_ALIGNMENT - 1) & ~(MY_ALIGNMENT - 1);
    return true;
}
 
static bool find_first_fit(size_t needed, uint32_t *offset_out,
                           BlockHeader *header_out)
{
    uint32_t offset = free_head;
    size_t visited = 0;
 
    while (offset != OFFSET_NONE && visited++ < MAX_BLOCKS) {
        BlockHeader header;
 
        if ((size_t)offset > MY_ARENA_SIZE - HEADER_SIZE ||
            (offset % MY_ALIGNMENT) != 0) {
            return false;
        }
        header = load_header(offset);
        if (!valid_block(offset, &header) || header.state != BLOCK_FREE) {
            return false;
        }
        if (header.span >= needed) {
            *offset_out = offset;
            *header_out = header;
            return true;
        }
        offset = header.next_free;
    }
    return false;
}
 
static void unlink_free(uint32_t offset, const BlockHeader *header)
{
    if (header->prev_free == OFFSET_NONE) {
        free_head = header->next_free;
    } else {
        BlockHeader previous = load_header(header->prev_free);
 
        previous.next_free = header->next_free;
        store_header(header->prev_free, previous);
    }
 
    if (header->next_free != OFFSET_NONE) {
        BlockHeader next = load_header(header->next_free);
 
        next.prev_free = header->prev_free;
        store_header(header->next_free, next);
    }
 
    (void)offset;
}
 
static void replace_free(uint32_t old_offset, const BlockHeader *old_header,
                         uint32_t new_offset, BlockHeader new_header)
{
    new_header.prev_free = old_header->prev_free;
    new_header.next_free = old_header->next_free;
 
    if (old_header->prev_free == OFFSET_NONE) {
        free_head = new_offset;
    } else {
        BlockHeader previous = load_header(old_header->prev_free);
 
        previous.next_free = new_offset;
        store_header(old_header->prev_free, previous);
    }
 
    if (old_header->next_free != OFFSET_NONE) {
        BlockHeader next = load_header(old_header->next_free);
 
        next.prev_free = new_offset;
        store_header(old_header->next_free, next);
    }
 
    store_block(new_offset, new_header);
    (void)old_offset;
}
 
static uint32_t insert_and_coalesce(uint32_t offset, BlockHeader header)
{
    uint32_t previous_offset = OFFSET_NONE;
    uint32_t next_offset = free_head;
    size_t visited = 0;
 
    while (next_offset != OFFSET_NONE && next_offset < offset &&
           visited++ < MAX_BLOCKS) {
        BlockHeader next = load_header(next_offset);
 
        previous_offset = next_offset;
        next_offset = next.next_free;
    }
 
    header.prev_free = previous_offset;
    header.next_free = next_offset;
    store_block(offset, header);
 
    if (previous_offset == OFFSET_NONE) {
        free_head = offset;
    } else {
        BlockHeader previous = load_header(previous_offset);
 
        previous.next_free = offset;
        store_header(previous_offset, previous);
    }
    if (next_offset != OFFSET_NONE) {
        BlockHeader next = load_header(next_offset);
 
        next.prev_free = offset;
        store_header(next_offset, next);
    }
 
    if (previous_offset != OFFSET_NONE) {
        BlockHeader previous = load_header(previous_offset);
 
        if ((uint64_t)previous_offset + previous.span == offset) {
            previous.span += header.span;
            previous.requested = 0;
            previous.next_free = next_offset;
            if (next_offset != OFFSET_NONE) {
                BlockHeader next = load_header(next_offset);
 
                next.prev_free = previous_offset;
                store_header(next_offset, next);
            }
            store_block(previous_offset, previous);
            offset = previous_offset;
            header = previous;
        }
    }
 
    next_offset = header.next_free;
    if (next_offset != OFFSET_NONE &&
        (uint64_t)offset + header.span == next_offset) {
        BlockHeader next = load_header(next_offset);
 
        header.span += next.span;
        header.requested = 0;
        header.next_free = next.next_free;
        if (next.next_free != OFFSET_NONE) {
            BlockHeader after = load_header(next.next_free);
 
            after.prev_free = offset;
            store_header(next.next_free, after);
        }
        store_block(offset, header);
    }
 
    return offset;
}
 
static bool find_used_pointer(const void *ptr, uint32_t *offset_out,
                              BlockHeader *header_out)
{
    size_t offset = 0;
    size_t visited = 0;
 
    while (offset < MY_ARENA_SIZE && visited++ < MAX_BLOCKS) {
        BlockHeader header;
 
        if (offset > MY_ARENA_SIZE - HEADER_SIZE ||
            (offset % MY_ALIGNMENT) != 0) {
            return false;
        }
        header = load_header((uint32_t)offset);
        if (!valid_block((uint32_t)offset, &header)) {
            return false;
        }
        if (ptr == (const void *)(arena + offset + HEADER_SIZE)) {
            if (header.state != BLOCK_USED) {
                return false;
            }
            *offset_out = (uint32_t)offset;
            *header_out = header;
            return true;
        }
        offset += (size_t)header.span;
    }
    return false;
}
 
void *my_malloc(size_t size)
{
    BlockHeader free_block;
    BlockHeader allocated;
    uint32_t offset;
    size_t needed;
    size_t remainder;
 
    initialize_heap();
    if (!my_heap_check() || !required_span(size, &needed) ||
        !find_first_fit(needed, &offset, &free_block)) {
        return NULL;
    }
 
    allocated.magic = 0;
    allocated.span = needed;
    allocated.requested = size;
    allocated.prev_free = OFFSET_NONE;
    allocated.next_free = OFFSET_NONE;
    allocated.state = BLOCK_USED;
    allocated.version = 0;
    allocated.header_canary = 0;
 
    remainder = (size_t)free_block.span - needed;
    if (remainder >= MIN_BLOCK_SIZE) {
        BlockHeader split;
        uint32_t split_offset = offset + (uint32_t)needed;
 
        split.magic = 0;
        split.span = remainder;
        split.requested = 0;
        split.prev_free = OFFSET_NONE;
        split.next_free = OFFSET_NONE;
        split.state = BLOCK_FREE;
        split.version = 0;
        split.header_canary = 0;
 
        replace_free(offset, &free_block, split_offset, split);
    } else {
        allocated.span = free_block.span;
        unlink_free(offset, &free_block);
    }
 
    store_block(offset, allocated);
    return arena + offset + HEADER_SIZE;
}
 
void my_free(void *ptr)
{
    BlockHeader header;
    uint32_t offset;
 
    if (ptr == NULL) {
        return;
    }
    initialize_heap();
    if (!my_heap_check() || !find_used_pointer(ptr, &offset, &header)) {
        return;
    }
 
    header.requested = 0;
    header.prev_free = OFFSET_NONE;
    header.next_free = OFFSET_NONE;
    header.state = BLOCK_FREE;
    store_block(offset, header);
    (void)insert_and_coalesce(offset, header);
}
 
void *my_calloc(size_t count, size_t size)
{
    size_t total;
    void *result;
 
    if (count == 0 || size == 0 || size > SIZE_MAX / count) {
        return NULL;
    }
    total = count * size;
    result = my_malloc(total);
    if (result != NULL) {
        memset(result, 0, total);
    }
    return result;
}
 
void *my_realloc(void *ptr, size_t size)
{
    BlockHeader header;
    uint32_t offset;
    size_t needed;
    size_t old_requested;
 
    if (ptr == NULL) {
        return my_malloc(size);
    }
    if (size == 0) {
        my_free(ptr);
        return NULL;
    }
 
    initialize_heap();
    if (!my_heap_check() || !find_used_pointer(ptr, &offset, &header) ||
        !required_span(size, &needed)) {
        return NULL;
    }
    old_requested = (size_t)header.requested;
 
    if (needed <= header.span) {
        size_t remainder = (size_t)header.span - needed;
 
        header.requested = size;
        if (remainder >= MIN_BLOCK_SIZE) {
            BlockHeader split;
            uint32_t split_offset = offset + (uint32_t)needed;
 
            header.span = needed;
            store_block(offset, header);
 
            split.magic = 0;
            split.span = remainder;
            split.requested = 0;
            split.prev_free = OFFSET_NONE;
            split.next_free = OFFSET_NONE;
            split.state = BLOCK_FREE;
            split.version = 0;
            split.header_canary = 0;
            store_block(split_offset, split);
            (void)insert_and_coalesce(split_offset, split);
        } else {
            store_block(offset, header);
        }
        return ptr;
    }
 
    if ((uint64_t)offset + header.span < MY_ARENA_SIZE) {
        uint32_t next_offset = offset + (uint32_t)header.span;
        BlockHeader next = load_header(next_offset);
 
        if (valid_block(next_offset, &next) && next.state == BLOCK_FREE &&
            header.span + next.span >= needed) {
            size_t combined = (size_t)(header.span + next.span);
            size_t remainder = combined - needed;
 
            header.requested = size;
            if (remainder >= MIN_BLOCK_SIZE) {
                BlockHeader split;
                uint32_t split_offset = offset + (uint32_t)needed;
 
                split.magic = 0;
                split.span = remainder;
                split.requested = 0;
                split.prev_free = OFFSET_NONE;
                split.next_free = OFFSET_NONE;
                split.state = BLOCK_FREE;
                split.version = 0;
                split.header_canary = 0;
 
                replace_free(next_offset, &next, split_offset, split);
                header.span = needed;
            } else {
                unlink_free(next_offset, &next);
                header.span = combined;
            }
            store_block(offset, header);
            return ptr;
        }
    }
 
    {
        void *replacement = my_malloc(size);
 
        if (replacement == NULL) {
            return NULL;
        }
        memcpy(replacement, ptr, old_requested < size ? old_requested : size);
        my_free(ptr);
        return replacement;
    }
}
 
int my_heap_check(void)
{
    size_t offset = 0;
    size_t visited = 0;
    size_t physical_free_count = 0;
    uint32_t previous_free = OFFSET_NONE;
    uint32_t previous_free_next = OFFSET_NONE;
    bool previous_block_was_free = false;
 
    initialize_heap();
 
    while (offset < MY_ARENA_SIZE && visited++ < MAX_BLOCKS) {
        BlockHeader header;
 
        if (offset > MY_ARENA_SIZE - HEADER_SIZE ||
            (offset % MY_ALIGNMENT) != 0) {
            return 0;
        }
        header = load_header((uint32_t)offset);
        if (!valid_block((uint32_t)offset, &header)) {
            return 0;
        }
 
        if (header.state == BLOCK_FREE) {
            if (previous_block_was_free) {
                return 0;
            }
            if (header.prev_free != previous_free) {
                return 0;
            }
            if (previous_free == OFFSET_NONE) {
                if (free_head != offset) {
                    return 0;
                }
            } else if (previous_free_next != offset) {
                return 0;
            }
            previous_free = (uint32_t)offset;
            previous_free_next = header.next_free;
            ++physical_free_count;
            previous_block_was_free = true;
        } else {
            previous_block_was_free = false;
        }
 
        offset += (size_t)header.span;
    }
 
    if (offset != MY_ARENA_SIZE || visited > MAX_BLOCKS) {
        return 0;
    }
    if (physical_free_count == 0) {
        if (free_head != OFFSET_NONE) {
            return 0;
        }
    } else if (previous_free_next != OFFSET_NONE) {
        return 0;
    }
    return 1;
}
 
my_stats_t my_stats(void)
{
    my_stats_t stats = {0, 0, 0};
    size_t offset = 0;
 
    initialize_heap();
    if (!my_heap_check()) {
        return stats;
    }
 
    while (offset < MY_ARENA_SIZE) {
        BlockHeader header = load_header((uint32_t)offset);
 
        if (header.state == BLOCK_USED) {
            stats.bytes_in_use += (size_t)header.requested;
        } else {
            size_t capacity = (size_t)header.span - HEADER_SIZE - CANARY_SIZE;
 
            ++stats.free_block_count;
            if (capacity > stats.largest_free_block) {
                stats.largest_free_block = capacity;
            }
        }
        offset += (size_t)header.span;
    }
    return stats;
}
 
666 linesc
Implemented the C11 allocator: - [alloc.c](…/alloc.c) - [alloc.h](…/alloc.h) - [tests.c](…/…
Files at this step
drag the rail to scrub
Discussion

No comments yet. Start the discussion. Recorded by @agentsage-runs.
#c #codex #gpt #gpt-5.6-sol #medium #subagents #testing
redo-alloc
← all sessions