Debug the Allocator

hard · memory, debugging, gdb

Debug the Allocator

Your colleague wrote a memory allocator, but it's crashing in production. Your task: find and fix all the bugs.

The Situation

The allocator has several bugs. Some cause immediate crashes, others cause subtle corruption. You have access to:

The buggy source code
Test cases that reproduce the crashes
GDB for debugging

Bugs to Find

There are 4 bugs in the code:

Off-by-one error - A size calculation is wrong
Missing initialization - A critical field isn't set
Wrong pointer arithmetic - Pointer math is incorrect
Logic error - A condition is wrong

Debugging Strategy

Step 1: Compile with Debug Symbols

gcc -g -O0 solution.c test.c -o test

Step 2: Run Under GDB

gdb ./test
(gdb) run
# Wait for crash
(gdb) bt         # Backtrace - see where it crashed
(gdb) print *block  # Inspect variables

Step 3: Set Breakpoints

(gdb) break my_malloc
(gdb) break my_free
(gdb) run
(gdb) print block->magic    # Check for corruption

Step 4: Watch for Corruption

(gdb) watch block->magic
(gdb) continue
# Stops when magic changes

Your Task

Fix all 4 bugs in the provided code. The tests will tell you when you've fixed them all.

Hints

Bug 1: Look at request_space - is the size calculation correct?
Bug 2: Look at block_init - are all fields initialized?
Bug 3: Look at payload_to_block - is the pointer arithmetic right?
Bug 4: Look at find_free_block - is the condition correct?

Learning Outcome

Real allocator bugs are subtle and dangerous. This exercise teaches you:

How to use GDB effectively
Common allocator bug patterns
The value of magic numbers for corruption detection

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

#define BLOCK_MAGIC 0xDEADBEEF

typedef struct block_header {
    size_t size;
    int free;
    unsigned int magic;
    struct block_header *next;
} block_header_t;

block_header_t *free_list_head = NULL;

// ============================================
// BUGGY CODE - Find and fix the 4 bugs!
// ============================================

static void *get_payload(block_header_t *block) {
    return (void*)(block + 1);
}

// BUG 3: Wrong pointer arithmetic (hint: should be -1, not +1)
static block_header_t *payload_to_block(void *payload) {
    return ((block_header_t*)payload) + 1;  // BUG: Wrong direction!
}

static int is_valid_block(void *ptr) {
    if (ptr == NULL) return 0;
    block_header_t *block = payload_to_block(ptr);
    return block->magic == BLOCK_MAGIC;
}

static block_header_t *get_last_block(void) {
    if (free_list_head == NULL) return NULL;
    block_header_t *curr = free_list_head;
    while (curr->next != NULL) curr = curr->next;
    return curr;
}

// BUG 4: Wrong condition (hint: should check free AND size)
block_header_t *find_free_block(size_t size) {
    block_header_t *current = free_list_head;
    while (current != NULL) {
        // BUG: Only checks size, not if block is free!
        if (current->size >= size) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

// BUG 1: Off-by-one in size calculation
static block_header_t *request_space(size_t size) {
    // BUG: Should be sizeof(block_header_t) + size, not size - 1
    size_t total_size = sizeof(block_header_t) + size - 1;
    block_header_t *block = sbrk((intptr_t)total_size);
    if (block == (void*)-1) return NULL;

block->size = size;
    block->free = 0;
    block->magic = BLOCK_MAGIC;
    block->next = NULL;

if (free_list_head == NULL) {
        free_list_head = block;
    } else {
        get_last_block()->next = block;
    }
    return block;
}

// BUG 2: Missing initialization in block_init
void block_init(block_header_t *block, size_t data_size, int is_free) {
    block->size = data_size;
    block->free = is_free;
    // BUG: Forgot to set magic!
    block->next = NULL;
}

void *my_malloc(size_t size) {
    if (size == 0) return NULL;

block_header_t *block = find_free_block(size);
    if (block != NULL) {
        block->free = 0;
        return get_payload(block);
    }

block = request_space(size);
    if (block == NULL) return NULL;
    return get_payload(block);
}

void my_free(void *ptr) {
    if (ptr == NULL) return;
    if (!is_valid_block(ptr)) return;
    block_header_t *block = payload_to_block(ptr);
    block->free = 1;
}