Block Header Design

A memory allocator needs metadata to track each allocation. This metadata is stored in a block header placed immediately before the user's data.

The Challenge

Design and implement a block header structure and associated operations. Your header must support:

1. Size tracking - Know how many bytes the block holds
2. Free/allocated status - Know if the block can be reused
3. Corruption detection - Detect when memory has been corrupted
4. Navigation - Move between blocks in the heap

Your Task

#define BLOCK_MAGIC 0xDEADBEEF  // Magic number for corruption detection

typedef struct block_header {
    size_t size;           // Size of data region (not including header)
    int free;              // 1 if free, 0 if allocated
    unsigned int magic;    // Set to BLOCK_MAGIC - detects corruption
    struct block_header *next;  // Next block in linked list
} block_header_t;

// Calculate total block size (header + data)
size_t block_total_size(block_header_t *block);

// Given a header pointer, return pointer to user data region
void *block_to_payload(block_header_t *block);

// Given a user data pointer, return pointer to its header
block_header_t *payload_to_block(void *payload);

// Given a block, find the next block in memory (not next in list)
block_header_t *block_next_in_memory(block_header_t *block, void *heap_end);

// Initialize a block at the given location
void block_init(block_header_t *block, size_t data_size, int is_free);

// Check if a block is valid (magic number check)
int block_is_valid(block_header_t *block);

Why the Magic Number?

Memory corruption is the #1 cause of allocator bugs:

char *p = malloc(10);
strcpy(p, "this string is way too long");  // Buffer overflow!
// The next block's header is now corrupted

// Later...
free(p);
free(next_block);  // CRASH - header is garbage

With magic validation:

int block_is_valid(block_header_t *block) {
    return block->magic == BLOCK_MAGIC;
}

void my_free(void *ptr) {
    block_header_t *block = payload_to_block(ptr);
    if (!block_is_valid(block)) {
        // Corruption detected! Don't trust any fields
        return;  // or abort()
    }
    block->free = 1;
}

Memory Layout

+------------------+------------------------+
|  block_header_t  |     user data          |
+------------------+------------------------+
^                  ^
block pointer      payload pointer
                   (returned by malloc)

Header fields:
+------+------+-------+------+
| size | free | magic | next |
+------+------+-------+------+

Pointer Arithmetic

This is where many students get confused:

void *block_to_payload(block_header_t *block) {
    // Move forward by one header size
    return (void*)(block + 1);
}

block_header_t *payload_to_block(void *payload) {
    // Move backward by one header size
    return ((block_header_t*)payload) - 1;
}

Why block + 1? In C, pointer arithmetic on block_header_t* moves by sizeof(block_header_t) bytes.

Constraints

• Header must be naturally aligned (typically 8 bytes on 64-bit)
• Magic MUST be set on every block initialization
• block_is_valid should be called before trusting any block data