Block Metadata Design

Every memory block needs metadata to answer critical questions:

• How big is this block?
• Is it free or allocated?
• Where is the next block?

The Block Header

We store metadata in a header immediately before the user's data:

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

Header Structure

A minimal header:

typedef struct block_header {
    size_t size;              // Size of user data region
    int free;                 // 1 = free, 0 = allocated
    struct block_header *next; // Next block in list
} block_header_t;

Critical Operations

Finding the Payload

void *block_to_payload(block_header_t *block) {
    return (char*)block + sizeof(block_header_t);
}

Finding the Header from Payload

block_header_t *payload_to_block(void *ptr) {
    return (block_header_t*)ptr - 1;
    // Or equivalently:
    // return (block_header_t*)((char*)ptr - sizeof(block_header_t));
}

Pointer Arithmetic Pitfall

// WRONG!
block_header_t *block = ptr - sizeof(block_header_t);
// This subtracts sizeof() * sizeof() because ptr has a type!

// CORRECT
block_header_t *block = (block_header_t*)ptr - 1;

When you subtract from a typed pointer, C multiplies by the element size. Casting to block_header_t* first makes -1 subtract exactly one header size.

Beware the char data[1] Trick

Some older allocators put char data[1] at the end of the header and return block->data as the payload. This is brittle because structure padding means:

sizeof(block_header_t) != offsetof(block_header_t, data)

Always compute the payload address with sizeof(block_header_t) (or block + 1) so alignment stays correct.

Alignment Considerations

The header must not break alignment of user data:

• User expects 8-byte alignment minimum
• If header is 24 bytes (typical: 8 + 4 + 4 + 8), user data starts at offset 24
• 24 is divisible by 8, so we're fine

If your header is an odd size, add padding.

Magic Numbers for Validation

Detecting invalid pointers passed to free():

#define BLOCK_MAGIC 0xDEADBEEF

typedef struct block_header {
    size_t size;
    int free;
    int magic;  // Set when block is created
    struct block_header *next;
} block_header_t;

void my_free(void *ptr) {
    block_header_t *block = payload_to_block(ptr);
    if (block->magic != BLOCK_MAGIC) {
        // Invalid pointer!
        abort();
    }
    // ... proceed with free
}

This catches some (not all) invalid frees.