Project 6: Memory Allocator

Build a simplified malloc/free allocator with headers, free lists, and coalescing.

Quick Reference

Attribute Value
Difficulty Expert
Time Estimate 2-4 weeks
Language C
Prerequisites Projects 1-5, memory model
Key Topics Heap management, fragmentation, headers

1. Learning Objectives

By completing this project, you will:

  1. Implement malloc, free, and realloc-style behavior.
  2. Manage free lists and block headers.
  3. Understand fragmentation and coalescing.
  4. Debug heap corruption using sanity checks.

2. Theoretical Foundation

2.1 Core Concepts

  • Heap blocks: Each allocation has metadata (size, flags).
  • Free lists: Track available blocks for reuse.
  • Fragmentation: Small unused blocks reduce usable memory.

2.2 Why This Matters

Every C program depends on an allocator. Implementing one teaches how memory is carved, reused, and corrupted when bugs appear.

2.3 Historical Context / Background

Classic allocators evolved from simple free lists to sophisticated segregated lists. This project starts with a minimal, teachable model.

2.4 Common Misconceptions

  • “free returns memory to the OS”: Often it just marks blocks reusable.
  • “realloc is always copy”: It can extend in place.

3. Project Specification

3.1 What You Will Build

A minimal heap allocator with:

  • mm_malloc, mm_free, mm_realloc
  • Free list management
  • Coalescing of adjacent free blocks
  • Optional heap checker for debugging

3.2 Functional Requirements

  1. Allocate aligned blocks with headers.
  2. Free blocks and insert into free list.
  3. Coalesce adjacent free blocks.
  4. realloc grows/shrinks blocks when possible.

3.3 Non-Functional Requirements

  • Correctness: Never return overlapping blocks.
  • Reliability: Detect obvious heap corruption.
  • Performance: Reasonable throughput for small tests.

3.4 Example Usage / Output

void *p = mm_malloc(64);
void *q = mm_malloc(128);
mm_free(p);
q = mm_realloc(q, 256);

3.5 Real World Outcome

You can trace how malloc requests map to heap blocks and explain fragmentation. You understand how a single overflow can corrupt allocator metadata.

4. Solution Architecture

4.1 High-Level Design

heap region -> block headers -> free list -> allocator API

4.2 Key Components

Component Responsibility Key Decisions
Block header Store size, flags Use size + alloc bit
Free list Track free blocks Singly linked list
Coalescer Merge adjacent frees Boundary tags

4.3 Data Structures

typedef struct Block {
    size_t size;
    struct Block *next;
} Block;

4.4 Algorithm Overview

Key Algorithm: First-fit allocation

  1. Traverse free list to find a block >= requested size.
  2. Split block if large enough.
  3. Mark allocated and return payload pointer.

Complexity Analysis:

  • Allocation: O(n) with simple list
  • Free: O(1) insert + O(1) coalesce if using boundary tags

5. Implementation Guide

5.1 Development Environment Setup

cc -Wall -Wextra -O2 -g -o test_mm test_mm.c mm.c

5.2 Project Structure

mm/
├── src/
│   ├── mm.c
│   └── mm.h
├── tests/
│   └── test_mm.c
└── README.md

5.3 The Core Question You’re Answering

“How does malloc carve memory into reusable blocks without losing track of it?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Alignment
    • Why align to 8 or 16 bytes?
  2. Fragmentation
    • Difference between internal and external fragmentation.
  3. Boundary tags
    • How do you find the previous block quickly?

5.5 Questions to Guide Your Design

Before implementing, think through these:

  1. Will you use sbrk or a fixed heap buffer?
  2. How will you store block size and allocation flag?
  3. What is your strategy for splitting blocks?

5.6 Thinking Exercise

Coalescing

Given two adjacent free blocks of 32 and 64 bytes, what does the combined block header look like after coalescing?

5.7 The Interview Questions They’ll Ask

Prepare to answer these:

  1. “What is internal vs external fragmentation?”
  2. “How does realloc work?”
  3. “Why do allocators align blocks?”

5.8 Hints in Layers

Hint 1: Start with a fixed heap Use a static buffer to avoid OS syscalls.

Hint 2: Implement first-fit Simple and correct before optimizing.

Hint 3: Add coalescing Merge adjacent free blocks to reduce fragmentation.

5.9 Books That Will Help

Topic Book Chapter
Memory allocation “Computer Systems: A Programmer’s Perspective” Ch. 9
Systems memory “The Linux Programming Interface” Ch. 7

5.10 Implementation Phases

Phase 1: Foundation (4-6 days)

Goals:

  • Fixed heap allocator

Tasks:

  1. Implement block headers and free list.
  2. Implement mm_malloc and mm_free.

Checkpoint: Basic allocations and frees work.

Phase 2: Core Functionality (5-7 days)

Goals:

  • Splitting and coalescing

Tasks:

  1. Split large blocks on allocation.
  2. Coalesce adjacent frees.

Checkpoint: Fragmentation reduced in tests.

Phase 3: Realloc + Debugging (4-6 days)

Goals:

  • Add mm_realloc and heap checker

Tasks:

  1. Implement grow/shrink behavior.
  2. Add sanity checks for headers.

Checkpoint: realloc passes tests and checker reports clean.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Fit strategy First-fit vs best-fit First-fit Simpler, good baseline
Heap source sbrk vs static buffer Static buffer first Easier to debug

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Block metadata Size/flags
Stress Tests Random alloc/free Fragmentation behavior
Corruption Tests Overwrites Checker detects

6.2 Critical Test Cases

  1. Allocate/free same size: Free list correct.
  2. Split block: Remainder becomes free block.
  3. Coalesce: Adjacent frees merge.

6.3 Test Data

Sizes: 8, 16, 24, 128, 1024

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Misaligned payloads Crash on SIMD Align to 8/16 bytes
Forgetting to update free list Leaks Update links carefully
Coalesce errors Overlapping blocks Use boundary tags

7.2 Debugging Strategies

  • Add a heap walk that prints every block.
  • Fill allocations with known patterns to detect overwrites.

7.3 Performance Traps

Linear free list scans get slow at scale. This is expected for a teaching allocator.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add mm_calloc.
  • Add stats reporting (free bytes, largest block).

8.2 Intermediate Extensions

  • Add segregated free lists by size.
  • Add next-fit strategy.

8.3 Advanced Extensions

  • Implement mmap-based large allocations.
  • Add thread-safe allocator with locks.

9. Real-World Connections

9.1 Industry Applications

  • Runtime libraries: glibc malloc internals.
  • Game engines: custom allocators for performance.
  • dlmalloc: Classic allocator implementation.

9.3 Interview Relevance

Allocator internals are common for systems roles and performance engineering.

10. Resources

10.1 Essential Reading

  • “Computer Systems: A Programmer’s Perspective” - Ch. 9
  • “The Linux Programming Interface” - Ch. 7

10.2 Video Resources

  • Memory allocator lectures and labs

10.3 Tools & Documentation

  • man 3 malloc: Standard allocator behavior
  • Memory Visualizer: Understands heap layout.
  • Thread Pool: Uses allocator extensively.

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain fragmentation types.
  • I can diagram block headers.
  • I can describe realloc behavior.

11.2 Implementation

  • Allocator passes tests.
  • Free list integrity holds.
  • Checker detects corruption.

11.3 Growth

  • I can add segregated lists.
  • I can explain this project in an interview.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • mm_malloc and mm_free with a free list.

Full Completion:

  • Coalescing and splitting working.

Excellence (Going Above & Beyond):

  • Segregated lists and mmap support.

This guide was generated from C_PROGRAMMING_COMPLETE_MASTERY.md. For the complete learning path, see the parent directory.