Free List Operations: Managing the Block Chain

An allocator maintains a free list - a linked list of all memory blocks (both free and allocated). This list is how we:

1. Find free blocks for new allocations
2. Track all blocks for potential reuse

free_list_head
      │
      ▼
   ┌──────────┐     ┌──────────┐     ┌──────────┐
   │  Block 1 │────▶│  Block 2 │────▶│  Block 3 │────▶ NULL
   │ size=64  │     │ size=128 │     │ size=32  │
   │ free=0   │     │ free=1   │     │ free=0   │
   └──────────┘     └──────────┘     └──────────┘
      used            FREE            used

Your Task

Implement these free list operations:

// Global head of the block list
extern block_header_t *free_list_head;

// Find the first free block that can hold 'size' bytes
// Returns NULL if no suitable block exists
block_header_t *find_free_block(size_t size);

// Find the last block in the list (for appending new blocks)
// Returns NULL if list is empty
block_header_t *get_last_block(void);

// Add a block to the end of the list
void append_block(block_header_t *block);

// Count total free blocks
int count_free_blocks(void);

// Count total bytes available in free blocks
size_t total_free_space(void);

First-Fit Search Strategy

find_free_block uses first-fit: scan the list and return the FIRST block where:

• block->free == 1 (block is free)
• block->size >= size (block is large enough)

This is simple but can cause fragmentation at the beginning of the heap.

Why a Linked List?

Blocks in memory are contiguous, but the NEXT pointer lets us skip over allocated blocks quickly. Without the list, we'd have to scan every block header in memory.

Constraints

• Never dereference NULL pointers
• Handle empty list (free_list_head == NULL)
• First-fit means return FIRST match, don't keep searching