Complete malloc Capstone

hard · memory, systems, capstone

Complete malloc: The Capstone

This is the final challenge. Build a complete memory allocator from scratch.

Your allocator must implement:

my_malloc(size) - allocate memory with free block reuse
my_free(ptr) - mark blocks as free
my_realloc(ptr, size) - resize with data preservation
my_calloc(count, size) - allocate zeroed memory

Requirements

Core Functionality

Block metadata: Store size, free flag, and next pointer
Free list: Track all blocks in a linked list
First-fit search: Find first free block that fits
Block reuse: malloc → free → malloc must reuse blocks

Edge Cases

malloc(0) returns NULL
free(NULL) does nothing
realloc(NULL, n) acts like malloc(n)
realloc(p, 0) acts like free(p), returns NULL
calloc detects multiplication overflow

Data Integrity

Freed blocks can be reused
realloc preserves existing data
calloc zero-initializes memory

Testing Strategy

Your implementation will be tested with:

Basic operations: Simple alloc/free/realloc/calloc
Reuse verification: Ensure freed blocks are reused
Stress tests: Many allocations in patterns
Data integrity: Verify data survives operations
Edge cases: NULL pointers, zero sizes, overflow

Memory Layout

┌─────────────────────────────────────────────────────────┐
│                       Heap                              │
├───────────┬───────────┬───────────┬───────────┬─────────┤
│  Block 1  │  Block 2  │  Block 3  │  Block 4  │  ...    │
│ [hdr|data]│ [hdr|data]│ [hdr|data]│ [hdr|data]│         │
│  used     │   FREE    │   used    │   FREE    │         │
└───────────┴───────────┴───────────┴───────────┴─────────┘
             ↑                       ↑
        Reusable!              Reusable!

Implementation Skeleton

typedef struct block_header {
    size_t size;              // User data size
    int free;                 // 1 = free, 0 = used
    struct block_header *next;
} block_header_t;

block_header_t *free_list_head = NULL;

void *my_malloc(size_t size);
void my_free(void *ptr);
void *my_realloc(void *ptr, size_t size);
void *my_calloc(size_t count, size_t size);

This Is Your Moment

You've built each piece. Now put it all together.

The tests are comprehensive. Pass them all and you've built malloc.

#include <stddef.h>
#include <stdint.h>
#include <unistd.h>

// ============================================
// Block header structure
// ============================================

typedef struct block_header {
    size_t size;              // Size of user data (not including header)
    int free;                 // 1 if free, 0 if allocated
    struct block_header *next; // Next block in list
} block_header_t;

// Global head of block list
block_header_t *free_list_head = NULL;

// ============================================
// Helper functions (implement these)
// ============================================

// Get payload pointer from block header
static void *get_payload(block_header_t *block) {
    // TODO
    return NULL;
}

// Get block header from payload pointer
static block_header_t *get_block(void *ptr) {
    // TODO
    return NULL;
}

// Find last block in list
static block_header_t *get_last_block(void) {
    // TODO
    return NULL;
}

// Find first free block that can hold 'size' bytes
static block_header_t *find_free_block(size_t size) {
    // TODO: First-fit search
    return NULL;
}

// Request new space from OS using sbrk
static block_header_t *request_space(size_t size) {
    // TODO: sbrk, initialize header, add to list
    return NULL;
}

// Copy n bytes from src to dst
static void my_memcpy(void *dst, const void *src, size_t n) {
    // TODO
}

// Set n bytes to value
static void my_memset(void *ptr, int value, size_t n) {
    // TODO
}

// ============================================
// Main API (implement these)
// ============================================

void *my_malloc(size_t size) {
    // TODO:
    // 1. Return NULL if size == 0
    // 2. Search for free block
    // 3. If found, mark as used and return payload
    // 4. If not found, request new space
    return NULL;
}

void my_free(void *ptr) {
    // TODO:
    // 1. Handle NULL
    // 2. Get block header
    // 3. Mark as free
}

void *my_realloc(void *ptr, size_t size) {
    // TODO:
    // 1. If ptr is NULL, return malloc(size)
    // 2. If size is 0, free(ptr) and return NULL
    // 3. If size <= current, return same ptr
    // 4. Otherwise: malloc new, copy data, free old
    return NULL;
}

void *my_calloc(size_t count, size_t size) {
    // TODO:
    // 1. Handle zero count/size
    // 2. Check for overflow
    // 3. malloc(count * size)
    // 4. memset to zero
    return NULL;
}