Project 4: Simple Memory Allocator with Debugging

Implement a malloc/free allocator with free lists, leak detection, and fragmentation stats.

Quick Reference

Attribute Value
Difficulty Expert
Time Estimate 2 weeks
Language C
Prerequisites Pointers, memory layout, C structs
Key Topics free lists, coalescing, fragmentation

1. Learning Objectives

By completing this project, you will:

  1. Implement a basic allocator with a free list.
  2. Track allocations and detect double-free/leaks.
  3. Implement coalescing of adjacent free blocks.
  4. Report fragmentation metrics.

2. Theoretical Foundation

2.1 Core Concepts

  • Free lists: Track free blocks using linked lists.
  • Coalescing: Merge adjacent free blocks to reduce fragmentation.
  • Size classes: Use multiple lists to speed up allocations.

2.2 Why This Matters

Allocator choices directly affect performance and reliability in systems code.

2.3 Historical Context / Background

Modern allocators like jemalloc and tcmalloc are built on these same concepts.

2.4 Common Misconceptions

  • “malloc is a black box”: It is a simple data structure at its core.
  • “Fragmentation is rare”: It appears quickly with mixed sizes.

3. Project Specification

3.1 What You Will Build

A custom allocator that replaces malloc/free, tracks active allocations, and prints heap stats.

3.2 Functional Requirements

  1. Implement mm_malloc, mm_free, and mm_realloc.
  2. Maintain a free list (or multiple size classes).
  3. Detect double-free and leaks at shutdown.
  4. Provide a heap visualization report.

3.3 Non-Functional Requirements

  • Performance: O(1) or O(log n) allocation for common sizes.
  • Reliability: No metadata corruption.
  • Usability: Debug output for heap layout.

3.4 Example Usage / Output

$ ./alloc_demo
Allocated 3 blocks
Freed 1 block
Heap: 2 allocated, 1 free, fragmentation 23%

3.5 Real World Outcome

You will run a test program and see leak and fragmentation diagnostics:

$ ./alloc_demo
Allocated 3 blocks
Freed 1 block
Heap: 2 allocated, 1 free, fragmentation 23%

4. Solution Architecture

4.1 High-Level Design

request -> find free block -> split -> return pointer
free -> mark block -> coalesce -> add to free list

4.2 Key Components

Component Responsibility Key Decisions
Heap header Track size/status Store size + flags
Free list Track free blocks Intrusive list
Coalescer Merge adjacent blocks Boundary tags
Tracker Detect leaks Hash table of allocs

4.3 Data Structures

typedef struct block_hdr {
    size_t size;
    int free;
    struct block_hdr *prev;
    struct block_hdr *next;
} block_hdr_t;

4.4 Algorithm Overview

Key Algorithm: First Fit

  1. Scan free list for first block with size >= request.
  2. Split if large enough.
  3. Return payload.

Complexity Analysis:

  • Time: O(n) for first-fit
  • Space: O(n) blocks

5. Implementation Guide

5.1 Development Environment Setup

gcc --version

5.2 Project Structure

project-root/
├── allocator.c
├── allocator.h
├── demo.c
└── README.md

5.3 The Core Question You’re Answering

“How does malloc actually manage memory, and why does fragmentation happen?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Heap layout and headers
  2. Coalescing with boundary tags
  3. Metadata overhead

5.5 Questions to Guide Your Design

Before implementing, think through these:

  1. Will you use first-fit or best-fit allocation?
  2. How will you detect adjacent free blocks?
  3. How do you track allocations for leak detection?

5.6 Thinking Exercise

Fragmentation

Allocate blocks of sizes 16, 64, 16, free the 64, then allocate 48. Can you reuse the free block without split? What if you need 80?

5.7 The Interview Questions They’ll Ask

Prepare to answer these:

  1. “What is internal vs external fragmentation?”
  2. “How do free lists work?”
  3. “Why do allocators use size classes?”

5.8 Hints in Layers

Hint 1: Start simple Implement a single free list before adding size classes.

Hint 2: Boundary tags Store size in both header and footer to coalesce quickly.

Hint 3: Track allocations Use a hash table or list of active blocks to detect leaks.

5.9 Books That Will Help

Topic Book Chapter
Allocator design “CS:APP” Ch. 9.9
Free lists “OSTEP” Ch. 17
Fragmentation “TLPI” Ch. 7

5.10 Implementation Phases

Phase 1: Foundation (4-5 days)

Goals:

  • Basic malloc/free using a free list.

Tasks:

  1. Implement header and free list.
  2. Support allocate and free.

Checkpoint: Simple test allocates and frees correctly.

Phase 2: Core Functionality (1 week)

Goals:

  • Coalescing and leak tracking.

Tasks:

  1. Add boundary tags.
  2. Implement coalescing on free.

Checkpoint: Fragmentation decreases after coalescing.

Phase 3: Polish & Edge Cases (3-4 days)

Goals:

  • Debug stats and size classes.

Tasks:

  1. Add allocation tracking and reports.
  2. Add size class buckets.

Checkpoint: Debug report shows accurate stats.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Allocation policy first-fit vs best-fit first-fit Simpler and fast
Coalescing on free vs on alloc on free Keeps list tidy

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Allocation Basic correctness allocate/free cycles
Coalescing Merge correctness free adjacent blocks
Leak detection Track active blocks exit without free

6.2 Critical Test Cases

  1. Double-free triggers error.
  2. Adjacent free blocks coalesce.
  3. Leak report shows unfreed blocks.

6.3 Test Data

Block sizes: 16, 64, 128

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Corrupt headers Crashes on free Add canaries
No coalescing High fragmentation Implement boundary tags
Incorrect split Overlap blocks Verify pointer math

7.2 Debugging Strategies

  • Add a heap dump function to print block list.
  • Use AddressSanitizer on the allocator tests.

7.3 Performance Traps

Best-fit can scan many blocks; keep the policy simple at first.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add a heap dump command.
  • Add stats for internal/external fragmentation.

8.2 Intermediate Extensions

  • Add segregated free lists by size.
  • Add a quarantine list to catch use-after-free.

8.3 Advanced Extensions

  • Implement thread-local caches.
  • Add guard pages for large allocations.

9. Real-World Connections

9.1 Industry Applications

  • Custom allocators in databases, game engines, and runtimes.
  • jemalloc: https://jemalloc.net
  • tcmalloc: https://github.com/google/tcmalloc

9.3 Interview Relevance

  • Allocator internals are a common advanced systems topic.

10. Resources

10.1 Essential Reading

  • malloc(3) - man 3 malloc
  • brk(2) and mmap(2)

10.2 Video Resources

  • Memory allocator lectures (search “malloc implementation”)

10.3 Tools & Documentation

  • valgrind and massif for allocator testing

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain free lists and coalescing.
  • I can describe fragmentation types.
  • I can explain allocator metadata overhead.

11.2 Implementation

  • Allocation and free are correct.
  • Coalescing works.
  • Leak detection reports accurately.

11.3 Growth

  • I can compare with jemalloc design choices.
  • I can extend to size classes.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Basic malloc/free with a free list.

Full Completion:

  • Coalescing and leak detection.

Excellence (Going Above & Beyond):

  • Segregated size classes and guard pages.

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