Block Splitting

hard · memory, fragmentation, optimization

Block Splitting: Reducing Internal Fragmentation

When you allocate 50 bytes but find a 1000-byte free block, the naive approach wastes 950 bytes. Block splitting divides large blocks to reduce this waste.

The Problem

Without splitting:

void *p1 = my_malloc(1000);  // Get a 1000-byte block
my_free(p1);                  // Free it
void *p2 = my_malloc(50);     // Reuse the 1000-byte block!
                              // 950 bytes wasted (internal fragmentation)

With splitting:

void *p1 = my_malloc(1000);  // Get a 1000-byte block
my_free(p1);                  // Free it
void *p2 = my_malloc(50);     // Split: use 50, remainder is new free block
void *p3 = my_malloc(100);    // Use the remainder!

Memory Layout

Before split (1000-byte free block, requesting 50):
┌────────────────┬─────────────────────────────────────────┐
│ header (32B)   │        data region (1000B)              │
│ size=1000      │                                         │
│ free=1         │                                         │
└────────────────┴─────────────────────────────────────────┘

After split:
┌────────────────┬──────────┬────────────────┬─────────────┐
│ header (32B)   │ data(56B)│ new header(32B)│ data(~900B) │
│ size=56        │ (USED)   │ size=~900      │  (FREE)     │
│ free=0         │          │ free=1         │             │
└────────────────┴──────────┴────────────────┴─────────────┘
                             ↑
                             New block can satisfy future allocations!

Your Task

Implement block splitting in your malloc:

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

// Check if block can be split for given size
int can_split(block_header_t *block, size_t size);

// Split block, returns new free block (or NULL if not split)
block_header_t *split_block(block_header_t *block, size_t size);

// malloc with splitting support
void *my_malloc(size_t size);

// free with magic validation
void my_free(void *ptr);

Critical Test: Remainder Must Be Usable

void *p1 = my_malloc(1000);
my_free(p1);

void *p2 = my_malloc(50);   // Should split the 1000-byte block
void *p3 = my_malloc(100);  // Should use the remainder!

// p2 and p3 should be DIFFERENT and VALID
// If p3 == NULL or p3 == p2, splitting failed

Alignment Matters

Always align sizes to 8 bytes before splitting:

size_t aligned = (size + 7) & ~7;

If you split without aligning, the new block's header might be misaligned, causing crashes on some architectures.

The Magic Field

Add a magic number to detect corruption:

typedef struct block_header {
    size_t size;
    int free;
    unsigned int magic;  // Set to BLOCK_MAGIC
    struct block_header *next;
} block_header_t;

Validate magic before trusting any block data.

#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
// ============================================

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;
}

// ============================================
// YOUR TASK: Implement splitting
// ============================================

// Check if block can be split for given allocation size
// A block can be split if the remaining space after allocation
// is large enough for a new block (header + MIN_BLOCK_SIZE)
int can_split(block_header_t *block, size_t size) {
    // TODO:
    // 1. Align the size
    // 2. Calculate remaining = block->size - aligned_size
    // 3. Return 1 if remaining >= sizeof(block_header_t) + MIN_DATA_SIZE
    return 0;
}

// Split the block, returning the new free block
// Returns NULL if split not possible
block_header_t *split_block(block_header_t *block, size_t size) {
    // TODO:
    // 1. Check if split is possible (use can_split)
    // 2. Calculate new block location:
    //    new_block = (char*)block + sizeof(header) + aligned_size
    // 3. Initialize new block (size, free=1, magic, next)
    // 4. Update original block's size and next pointer
    // 5. Return new block
    return NULL;
}

// malloc with splitting - finds free block, splits if beneficial
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) {
        // TODO: Try to split the block before using it
        // split_block(block, aligned);

block->free = 0;
        return get_payload(block);
    }

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

// free with magic validation
void my_free(void *ptr) {
    if (ptr == NULL) return;
    if (!is_valid_block(ptr)) return;  // Corrupted or invalid!

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