Block Coalescing

hard · memory, fragmentation, optimization

Block Coalescing: Reducing External Fragmentation

When you free multiple adjacent blocks, they remain separate unless you coalesce (merge) them. This creates external fragmentation: many small free blocks that can't satisfy large allocations.

The Problem

Without coalescing:

void *p1 = my_malloc(100);  // Block A
void *p2 = my_malloc(100);  // Block B
void *p3 = my_malloc(100);  // Block C

my_free(p1);  // A is free
my_free(p2);  // B is free
my_free(p3);  // C is free

void *big = my_malloc(250);  // FAILS! 3 separate 100-byte blocks
                              // can't satisfy 250-byte request

With coalescing:

void *p1 = my_malloc(100);
void *p2 = my_malloc(100);
void *p3 = my_malloc(100);

my_free(p1);  // A is free
my_free(p2);  // B merges with A → 200+ bytes
my_free(p3);  // C merges with AB → 300+ bytes

void *big = my_malloc(250);  // SUCCESS! One large block

Memory Layout

Before coalescing (all blocks free):
┌────────┬──────────┐┌────────┬──────────┐┌────────┬──────────┐
│ hdr A  │ data A   ││ hdr B  │ data B   ││ hdr C  │ data C   │
│ free=1 │ 100B     ││ free=1 │ 100B     ││ free=1 │ 100B     │
└────────┴──────────┘└────────┴──────────┘└────────┴──────────┘
    ↓ coalesce during free(B) and free(C)

After coalescing:
┌────────┬─────────────────────────────────────────────────────┐
│ hdr A  │              data: ~300B + 2*header_size            │
│ free=1 │                    (merged A+B+C)                   │
└────────┴─────────────────────────────────────────────────────┘

Your Task

Implement block coalescing in your free:

#define BLOCK_MAGIC 0xDEADBEEF
#define MIN_BLOCK_SIZE (sizeof(block_header_t) + 16)

// Coalesce with the next block if it's free
// Returns 1 if coalescing occurred, 0 otherwise
int coalesce_next(block_header_t *block);

// Coalesce with the previous block if it's free
// Returns pointer to the merged block, or 'block' if no merge
block_header_t *coalesce_prev(block_header_t *block);

// Full coalescing (next then prev)
block_header_t *coalesce(block_header_t *block);

// Free with coalescing
void my_free(void *ptr);

Coalescing with Next Block

Finding the next block is straightforward:

block_header_t *next = (block_header_t*)(
    (char*)block + sizeof(block_header_t) + block->size
);

// Check bounds and if free
void *heap_end = sbrk(0);
if ((void*)next < heap_end && next->free && next->magic == BLOCK_MAGIC) {
    block->size += sizeof(block_header_t) + next->size;
    block->next = next->next;  // Skip 'next' in linked list
}

The Hard Problem: Previous Block

With a singly-linked list, you can't go backward easily:

// Option 1: Scan from head (O(n) but simple)
block_header_t *candidate = free_list_head;
while (candidate != NULL) {
    block_header_t *cand_next = next_in_memory(candidate);
    if (cand_next == block && candidate->free) {
        // candidate is immediately before block - merge!
        candidate->size += sizeof(block_header_t) + block->size;
        candidate->next = block->next;
        return candidate;
    }
    candidate = candidate->next;
}

Critical Test: Adjacent Frees Must Merge

void *p1 = my_malloc(100);
void *p2 = my_malloc(100);
my_free(p1);
my_free(p2);

// Count blocks - should be 1 (merged), not 2
int count = 0;
block_header_t *curr = free_list_head;
while (curr != NULL) { count++; curr = curr->next; }
assert(count == 1);

// Large allocation should now succeed
void *big = my_malloc(180);
assert(big != NULL);  // Uses the merged block!

The Magic Field

Always validate magic before trusting block data:

if ((void*)next < heap_end && next->magic == BLOCK_MAGIC && next->free) {
    // Safe to coalesce
}

This catches corruption before it causes crashes.

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

#define BLOCK_MAGIC 0xDEADBEEF
#define MIN_BLOCK_SIZE (sizeof(block_header_t) + 16)

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;

// ============================================
// Helper functions (provided)
// ============================================

static size_t align8(size_t size) {
    return (size + 7) & ~7;
}

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

static block_header_t *get_block(void *ptr) {
    return ((block_header_t*)ptr) - 1;
}

static int is_valid_block(void *ptr) {
    if (ptr == NULL) return 0;
    block_header_t *block = get_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;
}

static block_header_t *find_free_block(size_t size) {
    block_header_t *current = free_list_head;
    while (current != NULL) {
        if (current->free && current->size >= size) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

static block_header_t *request_space(size_t size) {
    size_t total = sizeof(block_header_t) + size;
    block_header_t *block = sbrk((intptr_t)total);
    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;
}

// Helper: Get next block in memory (not linked list)
static block_header_t *next_in_memory(block_header_t *block) {
    return (block_header_t*)((char*)block + sizeof(block_header_t) + block->size);
}

// ============================================
// YOUR TASK: Implement coalescing
// ============================================

// Coalesce with the next block if it's free
// Returns 1 if coalescing occurred, 0 otherwise
int coalesce_next(block_header_t *block) {
    // TODO:
    // 1. Find the next block in memory using next_in_memory()
    // 2. Check if it's within heap bounds (use sbrk(0))
    // 3. Check if it has valid magic
    // 4. Check if it's free
    // 5. If free:
    //    - Add its size + header size to current block
    //    - Update linked list: block->next = next->next
    //    - Return 1
    // 6. If not free or invalid: return 0

return 0;
}

// Coalesce with the previous block if it's free
// Returns pointer to the merged block, or 'block' if no merge
block_header_t *coalesce_prev(block_header_t *block) {
    // TODO:
    // This is harder because we have a singly-linked list.
    // We need to find if there's a block whose "next in memory"
    // is our current block, AND that block is free.
    //
    // Strategy: Scan from head of list
    // For each block in list:
    //   1. Calculate what next_in_memory(candidate) would be
    //   2. If it equals 'block' AND candidate is free:
    //      - Merge: candidate->size += sizeof(header) + block->size
    //      - Update list: candidate->next = block->next
    //      - Return candidate (it now contains 'block')
    //
    // If no previous block found or it's not free: return block unchanged

return block;
}

// Coalesce a block with all adjacent free blocks
block_header_t *coalesce(block_header_t *block) {
    // TODO:
    // 1. First coalesce with next (if possible)
    //    - This is simpler, do it first
    // 2. Then coalesce with previous (if possible)
    //    - This may change which block we return
    // 3. Return the final merged block

return block;
}

// malloc - finds free block or requests space
void *my_malloc(size_t size) {
    if (size == 0) return NULL;

size_t aligned = align8(size);
    block_header_t *block = find_free_block(aligned);

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

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

// Free with coalescing - THIS IS WHERE YOU CALL COALESCE
void my_free(void *ptr) {
    if (ptr == NULL) return;
    if (!is_valid_block(ptr)) return;

block_header_t *block = get_block(ptr);
    block->free = 1;

// TODO: Call coalesce(block) here to merge with adjacent free blocks
}