Project 6: Dynamic Memory Allocator

A custom malloc/free implementation with block metadata, coalescing, and performance instrumentation.

Quick Reference

Attribute Value
Difficulty Level 4 - Expert
Time Estimate 2-3 weeks
Main Programming Language C
Alternative Programming Languages Rust (for comparison)
Coolness Level Level 5 - Pure Magic
Business Potential Level 1 - Resume Gold
Prerequisites Pointers, alignment, UB awareness, basic data structures
Key Topics Heap layout, free lists, fragmentation, coalescing

1. Learning Objectives

By completing this project, you will:

  1. Design a heap block layout with headers, footers, and alignment guarantees.
  2. Implement allocation, deallocation, splitting, and coalescing.
  3. Compare allocation strategies (first-fit, best-fit, segregated lists).
  4. Measure fragmentation and throughput under synthetic workloads.
  5. Build a test harness that validates allocator correctness and robustness.

2. All Theory Needed (Per-Concept Breakdown)

Concept 1: Heap Block Layout, Alignment, and Coalescing

Fundamentals

A heap allocator manages a contiguous region of memory by carving it into blocks. Each block contains metadata (header/footer) and a payload. The allocator must guarantee alignment so that the payload can hold any type safely. When a block is freed, adjacent free blocks should be coalesced to reduce fragmentation. If you get the layout wrong, you corrupt the heap; if you get alignment wrong, you can trigger undefined behavior or hardware faults. This concept is the core mechanical foundation of a custom allocator.

Deep Dive into the concept

A typical block layout includes a header with size and allocation status, optionally a footer for boundary-tag coalescing, and a payload. The header is placed immediately before the payload so the allocator can compute the block’s base address from a user pointer. The size is usually stored with the allocation bit in the low-order bits because sizes are aligned to at least 8 or 16 bytes, leaving low bits free. The footer mirrors the header at the end of the block, allowing backward coalescing without scanning from the heap base.

Alignment is non-negotiable. The allocator must return pointers aligned to the maximum alignment of any type (often 16 bytes on 64-bit). This means block sizes are rounded up to the alignment boundary and the header size itself must preserve alignment for the payload. If you fail this, you may cause crashes or silent data corruption when the user stores types with stricter alignment requirements (e.g., long double or SIMD types). Proper alignment is also required for performance: misaligned accesses can be slower or trap on strict architectures.

Coalescing is the process of merging adjacent free blocks. Without it, the heap becomes fragmented: you may have enough total free memory but no block large enough to satisfy a request. There are two strategies: immediate coalescing (merge on free) and deferred coalescing (merge during allocation). Immediate coalescing simplifies reasoning and reduces fragmentation at the cost of free time. Deferred coalescing can improve throughput but increases fragmentation risk. A professional allocator often combines both via periodic coalescing or size-class segregation.

The invariants are strict: block headers and footers must be consistent, the heap must be aligned, and the free list must accurately reflect free blocks. One subtlety is that coalescing may change the size of blocks already in free lists, so you must remove and reinsert them correctly. Another subtlety is that the user pointer must never be exposed to allocator metadata. If user code overwrites the header (via buffer overflow), the allocator can crash or be exploited. This is why robust allocators include guard checks, canaries, or optional debug modes.

In this project, you will design and implement these mechanisms, then test them with synthetic workloads that allocate and free blocks in patterns that stress fragmentation. The goal is to build a mental model of heap structure and ensure you can reason about it under pressure.

A practical extension is to treat the heap as a verified data structure with explicit invariants. For example, you can enforce that every block’s size is a multiple of the alignment, that headers and footers agree, and that the heap begins and ends with sentinel blocks to simplify boundary conditions. Many allocators also store a previous block allocated bit in the header so they can avoid reading the previous footer in common cases, which can improve performance. Another detail is minimum block size: if you split a block and the remainder is too small to hold metadata and alignment, you should avoid splitting and instead allocate the entire block. This reduces unusable fragments. Finally, consider adding a debug mode with canaries or red zones around blocks to detect overruns. This mirrors how real allocators provide debug features and will deepen your understanding of allocator safety.

To operationalize this concept in a real codebase, create a short checklist of invariants and a set of micro-experiments. Start with a minimal, deterministic test that isolates one rule or behavior, then vary a single parameter at a time (inputs, flags, platform, or data layout) and record the outcome. Keep a table of assumptions and validate them with assertions or static checks so violations are caught early. Whenever the concept touches the compiler or OS, capture tool output such as assembly, warnings, or system call traces and attach it to your lab notes. Finally, define explicit failure modes: what does a violation look like at runtime, and how would you detect it in logs or tests? This turns abstract theory into repeatable engineering practice and makes results comparable across machines and compiler versions.

How this fits on projects

Definitions & key terms

  • Block header/footer: Metadata storing size and allocation state.
  • Alignment: Required byte boundary for payload pointers.
  • Coalescing: Merging adjacent free blocks.
  • Fragmentation: Wasted memory due to small unusable blocks.
  • Boundary tags: Header+footer scheme to enable backward coalescing.

Mental model diagram (ASCII)

[Header|payload.............|Footer]
 size/alloc bits               size/alloc bits

How it works (step-by-step, with invariants and failure modes)

  1. Round request size to alignment and add header/footer overhead.
  2. Find a free block of sufficient size.
  3. Split if the remainder is large enough for a new block.
  4. On free, mark the block free and coalesce with neighbors.

Invariant: All blocks are aligned and headers/footers match. Failure mode: Incorrect coalescing corrupts the free list or heap.

Minimal concrete example

// Header stores size and allocation bit
#define ALLOC 0x1
size_t header = size | ALLOC;

Common misconceptions

  • “Only the payload matters.” → Metadata is critical for correctness.
  • “Coalescing can wait forever.” → Fragmentation will break allocations.
  • “Alignment is optional.” → It is required by the C standard.

Check-your-understanding questions

  1. Why do allocators round sizes up to alignment?
  2. What problem does coalescing solve?
  3. Why might you store alloc bits in size fields?
  4. What happens if you split a block too small?
  5. Why are footers useful?

Check-your-understanding answers

  1. To ensure returned pointers are properly aligned.
  2. It reduces fragmentation by merging adjacent free blocks.
  3. Alignment leaves low bits unused, so they can store flags.
  4. It creates unusable fragments and metadata corruption risk.
  5. They allow backward coalescing without scanning from the heap base.

Real-world applications

  • Memory allocators in operating systems and language runtimes.
  • High-performance servers with custom allocators.
  • Embedded systems that need deterministic allocation.

Where you’ll apply it

References

  • “Computer Systems: A Programmer’s Perspective” — malloc lab chapters
  • “Memory Management” — Wilson et al. (allocator survey)

Key insights

Heap allocation is just data structure management with strict invariants.

Summary

Block layout and alignment are the foundation of any allocator. Coalescing preserves usable memory and prevents fragmentation. These mechanisms define correctness and performance.

Homework/Exercises to practice the concept

  1. Design a block header format that supports coalescing.
  2. Calculate the minimum block size given header/footer and alignment.
  3. Simulate coalescing by hand on a sequence of frees.

Solutions to the homework/exercises

  1. Include size and alloc flag; optionally store prev-alloc bit.
  2. Minimum size is header+footer+alignment padding.
  3. Merge adjacent free blocks and update sizes accordingly.

Concept 2: Free Lists and Allocation Strategies

Fundamentals

The allocator needs a way to find a suitable free block. A free list is a data structure containing all free blocks. The simplest approach is an implicit list that scans the entire heap; more advanced allocators use explicit free lists, segregated size classes, or balanced trees. The allocation strategy (first-fit, best-fit, next-fit) determines which free block is chosen. This choice affects performance and fragmentation.

Deep Dive into the concept

An implicit free list walks all blocks in the heap and finds the first block large enough. This is simple but slow: allocation becomes O(n) in the number of blocks. Explicit free lists store free blocks in a linked list, which reduces scanning but adds pointer overhead in each free block. Segregated lists maintain multiple lists by size class, reducing search time and improving locality. Some allocators use balanced trees keyed by block size for best-fit selection. Each strategy trades speed, memory overhead, and fragmentation.

First-fit chooses the first block that fits, which is fast but can leave small unusable fragments near the front of the heap. Best-fit chooses the smallest block that fits, which reduces wasted space but can be slower and can create many tiny fragments. Next-fit continues searching from the last allocation position, which spreads fragmentation. A professional allocator often uses segregated lists with size classes (e.g., 16, 32, 64, 128 bytes, etc.) to get near-constant allocation time for small blocks.

Free list maintenance is tricky. When you split a block, the remainder must be inserted into the appropriate list. When you coalesce, you must remove the old blocks from the list and insert the new merged block. If you use an explicit list, you must store prev/next pointers in the payload of free blocks. This means the layout of a free block differs from an allocated block, which complicates debugging. Many allocators use a “debug mode” where they verify free list integrity after each operation.

In this project, you will implement at least two strategies (first-fit implicit list and segregated explicit list) and compare their performance. You will measure throughput and fragmentation by running synthetic traces (e.g., many small allocations, mixed size patterns, random frees). You will also build a heap checker that verifies list consistency and block invariants. This is the difference between a toy allocator and a professional one.

To operationalize this concept in a real codebase, create a short checklist of invariants and a set of micro-experiments. Start with a minimal, deterministic test that isolates one rule or behavior, then vary a single parameter at a time (inputs, flags, platform, or data layout) and record the outcome. Keep a table of assumptions and validate them with assertions or static checks so violations are caught early. Whenever the concept touches the compiler or OS, capture tool output such as assembly, warnings, or system call traces and attach it to your lab notes. Finally, define explicit failure modes: what does a violation look like at runtime, and how would you detect it in logs or tests? This turns abstract theory into repeatable engineering practice and makes results comparable across machines and compiler versions.

Another way to deepen understanding is to map the concept to a small decision table: list inputs, expected outcomes, and the assumptions that must hold. Create at least one negative test that violates an assumption and observe the failure mode, then document how you would detect it in production. Add a short trade-off note: what you gain by following the rule and what you pay in complexity or performance. Where possible, instrument the implementation with debug-only checks so violations are caught early without affecting release builds. If the concept admits multiple approaches, implement two and compare them; the act of measuring and documenting the difference is part of professional practice. This habit turns theoretical understanding into an engineering decision framework you can reuse across projects.

How this fits on projects

Definitions & key terms

  • Implicit free list: Scan all blocks to find a free block.
  • Explicit free list: Maintain a list of free blocks only.
  • Segregated lists: Multiple free lists by size class.
  • First-fit / best-fit / next-fit: Allocation strategies.
  • Fragmentation: External and internal wasted memory.

Mental model diagram (ASCII)

Free list (size class 64): [block]->[block]->[block]
Free list (size class 128): [block]->[block]

How it works (step-by-step, with invariants and failure modes)

  1. Choose a size class for the request.
  2. Search the corresponding free list for a block.
  3. If none, search larger classes or extend the heap.
  4. Split and insert remainder if needed.

Invariant: Every free block appears exactly once in a free list. Failure mode: Double insertion leads to cycles or corruption.

Minimal concrete example

struct free_block { struct free_block *next; };

Common misconceptions

  • “Best-fit always reduces fragmentation.” → It can create many tiny blocks.
  • “Explicit lists are always faster.” → Maintenance overhead can outweigh gains.
  • “A single free list is enough.” → Performance suffers with mixed sizes.

Check-your-understanding questions

  1. What is the time complexity of an implicit free list?
  2. Why use segregated lists?
  3. How does splitting affect free list integrity?
  4. What is external vs internal fragmentation?
  5. Why must free blocks be removed before coalescing?

Check-your-understanding answers

  1. O(n) in number of blocks.
  2. To reduce search time and improve locality.
  3. The remainder must be inserted in the correct list.
  4. External is unusable gaps; internal is wasted space inside blocks.
  5. Because their sizes change and list pointers become invalid.

Real-world applications

  • Custom allocators in databases and game engines.
  • Memory pools for networking stacks.
  • High-frequency trading systems with deterministic allocation.

Where you’ll apply it

References

  • “The Memory Management Reference” — Wilson et al.
  • “Designing Data-Intensive Applications” — sections on memory pools

Key insights

Allocator performance is largely determined by free list strategy and fragmentation control.

Summary

Free lists are the allocator’s search structure. The choice of strategy determines speed and fragmentation. A robust allocator must maintain free list invariants under all operations.

Homework/Exercises to practice the concept

  1. Implement a simple implicit free list search.
  2. Add a segregated list and compare allocation time.
  3. Write a heap checker that validates list integrity.

Solutions to the homework/exercises

  1. Walk blocks and choose first that fits.
  2. Measure throughput for small allocations.
  3. Ensure each free block appears exactly once and is marked free.

3. Project Specification

3.1 What You Will Build

A reusable memory allocator library that provides mm_malloc, mm_free, and mm_realloc with configurable strategies, plus a CLI test harness to run traces and generate a fragmentation report.

3.2 Functional Requirements

  1. Allocation: Provide mm_malloc(size_t) with alignment guarantees.
  2. Free/Realloc: Support mm_free and mm_realloc.
  3. Coalescing: Merge adjacent free blocks.
  4. Splitting: Split large free blocks when possible.
  5. Heap Checker: Validate invariants and free list correctness.

3.3 Non-Functional Requirements

  • Performance: Handle 10,000 allocations per second in the test harness.
  • Reliability: Heap checker passes after every operation in debug mode.
  • Usability: API mirrors malloc/free semantics.

3.4 Example Usage / Output

void *p = mm_malloc(64);
mm_free(p);

3.5 Data Formats / Schemas / Protocols

Trace format (text):

alloc 64
free 0
realloc 1 128

3.6 Edge Cases

  • Allocating 0 bytes.
  • Freeing NULL.
  • Realloc shrinking and growing.

3.7 Real World Outcome

What you will see:

  1. A working allocator library with a test harness.
  2. A fragmentation and throughput report.
  3. A heap checker that validates invariants.

3.7.1 How to Run (Copy/Paste)

make
./allocator_test traces/trace1.txt

3.7.2 Golden Path Demo (Deterministic)

Run a fixed trace and verify the fragmentation metrics.

3.7.3 If CLI: exact terminal transcript

$ ./allocator_test traces/simple.txt
Allocations: 100
Frees: 100
Peak heap: 4096 bytes
Fragmentation: 8.5%
Exit: 0

Failure demo (deterministic):

$ ./allocator_test traces/missing.txt
ERROR: trace file not found
Exit: 2

4. Solution Architecture

4.1 High-Level Design

+-------------------+
| allocator API      |
+---------+---------+
          |
          v
+-------------------+     +-------------------+
| block manager      | -->| free lists        |
+-------------------+     +-------------------+
          |
          v
+-------------------+
| heap checker       |
+-------------------+

4.2 Key Components

| Component | Responsibility | Key Decisions | |———–|—————-|—————-| | Block manager | Manage headers/footers | Boundary tags | | Free lists | Track free blocks | Segregated lists | | Heap checker | Validate invariants | Debug-only option |

4.3 Data Structures (No Full Code)

typedef struct block_header {
    size_t size_and_flags;
} block_header_t;

4.4 Algorithm Overview

  1. Adjust request size for alignment.
  2. Search free list for block.
  3. Split if needed and update lists.
  4. On free, coalesce and update lists.

Complexity Analysis:

  • Time: O(1) average with segregated lists
  • Space: O(n) for metadata

5. Implementation Guide

5.1 Development Environment Setup

clang -std=c23 -Wall -Wextra -Werror -fsanitize=address,undefined -g

5.2 Project Structure

allocator/
├── src/
│   ├── mm.c
│   ├── free_list.c
│   └── heap_checker.c
├── include/
│   └── mm.h
├── tests/
├── traces/
└── Makefile

5.3 The Core Question You’re Answering

“How do real allocators manage memory safely and fast without corrupting the heap?”

5.4 Concepts You Must Understand First

  1. Block layout and alignment.
  2. Coalescing and fragmentation.
  3. Free list strategies.

5.5 Questions to Guide Your Design

  1. What minimum block size prevents unusable fragments?
  2. How will you validate free list integrity?
  3. How will you measure fragmentation? (internal vs external)

5.6 Thinking Exercise

Simulate allocations/free operations on paper and draw the heap.

5.7 The Interview Questions They’ll Ask

  1. Why do allocators store size in headers?
  2. What is external fragmentation?
  3. How would you design a segregated free list?

5.8 Hints in Layers

  • Hint 1: Start with an implicit free list and first-fit.
  • Hint 2: Add coalescing and block splitting.
  • Hint 3: Introduce segregated lists for performance.

5.9 Books That Will Help

| Topic | Book | Chapter | |——-|——|———| | Allocator internals | “CS:APP” — malloc lab | Ch. 9 | | Memory management | Wilson et al. | Survey |

5.10 Implementation Phases

Phase 1: Foundation (1 week)

  • Implement implicit list with headers/footers.
  • Checkpoint: Basic allocate/free works.

Phase 2: Core Functionality (1 week)

  • Add coalescing and splitting.
  • Checkpoint: Heap checker passes tests.

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

  • Add segregated lists and benchmarks.
  • Checkpoint: Throughput improves on traces.

5.11 Key Implementation Decisions

| Decision | Options | Recommendation | Rationale | |———-|———|—————-|———–| | Coalescing | immediate, deferred | immediate | Simpler correctness | | Free list | implicit, explicit | explicit | Better performance |

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |———|———|———-| | Unit tests | Validate block operations | Split/merge | | Integration tests | Trace replay | traces/*.txt | | Edge case tests | Zero alloc, double free | Error cases |

6.2 Critical Test Cases

  1. Double-free detection in debug mode.
  2. Coalescing adjacent blocks correctly.
  3. Realloc growing while preserving data.

6.3 Test Data

trace: alloc 64, alloc 128, free 0, free 1

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |——–|———|———-| | Incorrect header size | Heap corruption | Use macros for header size | | Free list cycles | Infinite loop | Validate list integrity | | Misaligned payload | Crash or slow access | Align all block sizes |

7.2 Debugging Strategies

  • Use a heap checker after every operation in debug builds.
  • Visualize heap state after each trace step.

7.3 Performance Traps

Over-coalescing can slow free-heavy workloads; measure with traces.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add a heap visualization tool.

8.2 Intermediate Extensions

  • Add a tiny object cache for small sizes.

8.3 Advanced Extensions

  • Implement per-thread arenas.
  • Add support for mmap-backed large allocations.

9. Real-World Connections

9.1 Industry Applications

  • Custom allocators in databases, game engines, and browsers.
  • Embedded systems with deterministic memory usage.
  • jemalloc, tcmalloc, mimalloc.

9.3 Interview Relevance

  • Allocator design is a classic systems interview topic.

10. Resources

10.1 Essential Reading

  • “CS:APP” malloc lab chapters
  • “Memory Allocation” — Wilson et al.

10.2 Video Resources

  • Talks on malloc internals (Facebook/Google allocators)

10.3 Tools & Documentation

  • Valgrind, AddressSanitizer, heap checkers

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain block headers/footers and coalescing.
  • I can describe why alignment matters.
  • I can compare free list strategies.

11.2 Implementation

  • Allocator passes all traces.
  • Heap checker reports no errors.
  • Throughput metrics are recorded.

11.3 Growth

  • I can explain allocator design trade-offs in an interview.
  • I can extend the allocator with new policies.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • mm_malloc, mm_free, mm_realloc working.
  • Coalescing and splitting implemented.
  • Trace-driven tests pass.

Full Completion:

  • All minimum criteria plus:
  • Segregated free lists and fragmentation report.

Excellence (Going Above & Beyond):

  • Per-thread arenas and large-object mmap support.