Project 3: Memory Allocator (malloc from Scratch)

Implement malloc/free/realloc with a free list, splitting, and coalescing, and validate it with real programs.

Quick Reference

Attribute Value
Difficulty Intermediate
Time Estimate 12-20 hours
Main Programming Language C
Alternative Programming Languages C++ or Rust (unsafe)
Coolness Level High
Business Potential Medium (perf/debug tooling)
Prerequisites C pointers, alignment, basic OS memory model
Key Topics heap layout, free lists, fragmentation, sbrk/mmap

1. Learning Objectives

By completing this project, you will:

  1. Design a heap layout with headers, footers, and alignment.
  2. Implement malloc, free, and realloc with coalescing.
  3. Measure internal/external fragmentation and reuse.
  4. Explain trade-offs between first-fit, best-fit, and segregated lists.

2. All Theory Needed (Per-Concept Breakdown)

Heap Allocation, Free Lists, and Fragmentation

Fundamentals

Dynamic memory allocation turns large, OS-provided chunks of memory into variable-sized allocations for programs. A malloc implementation must track which regions are free, which are in use, and how to quickly find a region that fits a request. It also must satisfy alignment constraints so that allocated addresses are safe for any type. This is why allocators store metadata in headers and sometimes footers, allowing the allocator to navigate between blocks. Two kinds of fragmentation emerge: internal fragmentation (wasted space inside blocks due to alignment or minimum sizes) and external fragmentation (free space split into small, non-contiguous pieces). The allocator’s policy determines how it trades speed for fragmentation.

Deep Dive into the concept

At the OS level, the heap is a continuous virtual memory region that grows upward. Historically, allocators used sbrk to extend the heap, but modern allocators often use mmap for large allocations to reduce fragmentation and allow independent release. Your allocator can model either approach. The simplest allocator is a bump allocator: it returns the next free address and never reuses memory. That is fast but leaks. To support free, you need a free list that records blocks available for reuse.

A typical block layout uses a header containing the block size and allocation status. Some designs include a footer (boundary tag) with a copy of the size, which makes coalescing with the previous block efficient. When a block is freed, the allocator checks neighboring blocks. If adjacent blocks are free, it merges them to reduce external fragmentation. This is called coalescing. The allocator must also decide when to split a larger free block to satisfy a smaller request. Splitting reduces wasted space but can increase fragmentation if the remainder is too small to be useful.

Policies matter. First-fit scans from the start of the free list and picks the first block that fits, which is fast but can create small holes near the beginning. Best-fit searches for the smallest block that fits, which reduces immediate waste but can be slow and can create many tiny unusable fragments. A compromise is next-fit (continue from where you left off), which improves speed and distributes fragmentation. More advanced allocators use segregated free lists: multiple lists for different size classes, which improves speed and reduces fragmentation by grouping similar sizes.

Alignment is a practical invariant. If you align all blocks to 16 bytes, you can safely return any pointer for any type. That requires that header size and block sizes are multiples of the alignment. A common technique is to round the requested size up to the nearest alignment and then add header overhead. If the leftover fragment after splitting is smaller than a minimum block size (e.g., header + alignment), you should avoid splitting and allocate the entire block.

Realloc introduces another dimension. If you can grow a block in place by checking the next block and coalescing, you avoid copying. Otherwise, you allocate a new block, copy data, and free the old block. Keeping realloc efficient requires careful block metadata and coalescing logic.

Testing allocators requires adversarial patterns. Alternating small and large allocations can create fragmentation. Randomized stress tests can reveal metadata corruption. You can also preload your allocator into real programs with LD_PRELOAD to verify it behaves under real workloads. That is a powerful validation that your implementation respects the libc ABI and alignment rules.

How this fit on projects

This concept powers Section 3.2 (functional requirements), Section 4 (architecture), and Section 6 (testing). It connects to VM concepts in Project 4 and process memory in Project 6.

Definitions & key terms

  • Header: Metadata stored before a block (size, allocated bit).
  • Footer: Metadata stored at end of block for backward traversal.
  • Coalescing: Merging adjacent free blocks.
  • Internal fragmentation: Wasted space inside an allocated block.
  • External fragmentation: Free space split into unusable pieces.

Mental model diagram (ASCII)

Heap:
[ H | payload | F ][ H | payload | F ][ H | payload | F ]
  ^ size+flags           ^ free block

How it works (step-by-step)

  1. Round requested size to alignment and add header size.
  2. Search free list for a fitting block.
  3. If found, split if remainder is large enough.
  4. Mark block allocated and return payload pointer.
  5. On free, mark block free and coalesce neighbors.

Minimal concrete example

struct header {
    size_t size;  // includes header
    int free;
    struct header *next;
};

void *mymalloc(size_t n) {
    size_t size = align(n + sizeof(struct header));
    struct header *b = find_fit(size);
    if (!b) b = request_more(size);
    split_if_needed(b, size);
    b->free = 0;
    return (void*)(b + 1);
}

Common misconceptions

  • “free knows the size”: it does, because you stored it in the header.
  • “alignment is optional”: misalignment can crash on some platforms.
  • “coalescing is always safe”: only if neighbors are truly free.

Check-your-understanding questions

  1. Why do allocators store block size in a header?
  2. What is the difference between internal and external fragmentation?
  3. When should a block be split versus allocated whole?
  4. Why is boundary tagging useful for coalescing?

Check-your-understanding answers

  1. So free can find block boundaries and sizes without extra input.
  2. Internal is wasted space within a block; external is scattered free blocks.
  3. Split only if the remainder can form a valid block.
  4. It allows constant-time access to previous block size.

Real-world applications

  • General-purpose allocators (glibc malloc, jemalloc).
  • Debug allocators for memory leak detection.

Where you’ll apply it

  • This project: Section 3.2, Section 4.4, Section 5.10 Phase 2, Section 6.
  • Also used in: Project 4, Project 6.

References

  • “OSTEP” Ch. 17
  • “CS:APP” Ch. 9
  • “The Linux Programming Interface” Ch. 7

Key insights

Allocators are policy engines: their decisions trade speed for fragmentation and reuse.

Summary

By tracking block metadata and coalescing neighbors, you convert raw heap pages into safe, reusable allocations.

Homework/Exercises to practice the concept

  1. Implement first-fit and best-fit and compare fragmentation.
  2. Add a segregated free list for sizes <= 128 bytes.
  3. Add statistics: total heap, in-use, free, fragmentation.

Solutions to the homework/exercises

  1. Collect stats after a fixed workload and compare.
  2. Use an array of free list heads by size class.
  3. Walk the heap and sum sizes by free/used flags.

3. Project Specification

3.1 What You Will Build

A drop-in memory allocator with malloc/free/realloc that uses a free list and coalescing. It will be usable via LD_PRELOAD and will log allocations for debugging.

3.2 Functional Requirements

  1. Implement malloc, free, and realloc with correct alignment.
  2. Support splitting and coalescing of free blocks.
  3. Provide allocation statistics and debug logging.
  4. Work correctly when preloaded into a small real program.

3.3 Non-Functional Requirements

  • Performance: handle 10k allocations/sec in a simple benchmark.
  • Reliability: no memory corruption under randomized tests.
  • Usability: clear log output with block sizes.

3.4 Example Usage / Output

$ gcc -fPIC -shared -o libmymalloc.so mymalloc.c
$ LD_PRELOAD=./libmymalloc.so ./alloc_test
[mymalloc] malloc(128) -> 0x7f1234000010
[mymalloc] free(0x7f1234000010)

3.5 Data Formats / Schemas / Protocols

  • Block header: size + free flag + next pointer.
  • Alignment: 16-byte alignment for payload.

3.6 Edge Cases

  • Freeing NULL (no-op).
  • Realloc to size 0 (free).
  • Coalescing two or three adjacent free blocks.

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

gcc -fPIC -shared -o libmymalloc.so mymalloc.c
LD_PRELOAD=./libmymalloc.so ./alloc_test --seed 42

3.7.2 Golden Path Demo (Deterministic)

  • Use --seed 42 in the test harness to fix allocation patterns.

3.7.3 If CLI: exact terminal transcript

$ LD_PRELOAD=./libmymalloc.so ./alloc_test --seed 42
[mymalloc] malloc(64)  -> 0x7f1234000010
[mymalloc] malloc(128) -> 0x7f1234000060
[mymalloc] free(0x7f1234000010)
[mymalloc] malloc(32)  -> 0x7f1234000010 (reused)
stats: total=65536 used=160 free=65376 frag=2%

Failure demo (deterministic):

$ LD_PRELOAD=./libmymalloc.so ./alloc_test --seed 42 --corrupt-header
allocator error: invalid block header

Exit codes:

  • 0 success
  • 2 allocator detected corruption
  • 3 invalid arguments

4. Solution Architecture

4.1 High-Level Design

request_more() -> free list -> split/coalesce -> return payload

4.2 Key Components

| Component | Responsibility | Key Decisions | |———–|—————-|—————| | Heap manager | Extend heap | sbrk for small, mmap for large | | Free list | Track free blocks | singly linked list | | Coalescer | Merge neighbors | boundary tags |

4.3 Data Structures (No Full Code)

struct block {
    size_t size;
    int free;
    struct block *next;
};

4.4 Algorithm Overview

Key Algorithm: Coalescing

  1. Mark block free.
  2. If next block free, merge.
  3. If previous block free, merge (via footer).

Complexity Analysis:

  • Time: O(n) search, O(1) coalesce
  • Space: O(1) overhead per block

5. Implementation Guide

5.1 Development Environment Setup

sudo apt-get install build-essential

5.2 Project Structure

project-root/
|-- mymalloc.c
|-- alloc_test.c
|-- Makefile
`-- README.md

5.3 The Core Question You’re Answering

“How does the runtime turn raw pages into safe, reusable allocations with predictable overhead?”

5.4 Concepts You Must Understand First

  1. Alignment and padding.
  2. Heap growth via sbrk/mmap.
  3. Fragmentation metrics.

5.5 Questions to Guide Your Design

  1. Which fit policy will you use first?
  2. What is the minimum block size?
  3. When will you use mmap instead of sbrk?

5.6 Thinking Exercise

Manually simulate malloc/free for sizes 32, 64, 16, free 64, malloc 48.

5.7 The Interview Questions They’ll Ask

  1. Why does free not take a size parameter?
  2. How do allocators prevent fragmentation?
  3. How would you make it thread-safe?

5.8 Hints in Layers

Hint 1: Start with a bump allocator.

Hint 2: Add a free list and reuse blocks.

Hint 3: Add splitting and coalescing.

5.9 Books That Will Help

| Topic | Book | Chapter | |——-|——|———| | Allocation | OSTEP | 17 | | Heap internals | CS:APP | 9 | | sbrk/mmap | TLPI | 7 |

5.10 Implementation Phases

Phase 1: Bump allocator (2-3 hours)

Goals: allocate memory, ignore free. Checkpoint: allocations return unique aligned pointers.

Phase 2: Free list (4-6 hours)

Goals: support free and reuse. Checkpoint: simple reuse works.

Phase 3: Coalescing and stats (4-6 hours)

Goals: reduce fragmentation, report stats. Checkpoint: fragmentation decreases on sample workload.

5.11 Key Implementation Decisions

| Decision | Options | Recommendation | Rationale | |———-|———|—————-|———–| | Fit policy | first-fit vs best-fit | first-fit | simpler and fast | | Large allocs | sbrk only vs mmap | mmap for large | reduce fragmentation |

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |———-|———|———-| | Unit | Validate split/coalesce | synthetic block list tests | | Integration | Preload into program | alloc_test | | Stress | Random workloads | seed-based random alloc/free |

6.2 Critical Test Cases

  1. Coalesce two adjacent free blocks.
  2. Realloc grows in place when possible.
  3. Alignment is correct for double.

6.3 Test Data

seed=42
alloc sizes: [64,128,32,256,...]

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |——–|———|———-| | Misaligned block | crashes on SIMD | align sizes to 16 | | Corrupt free list | random crashes | add sanity checks | | Bad coalesce | double-free or loop | verify neighbor headers |

7.2 Debugging Strategies

  • Add canaries in headers.
  • Use AddressSanitizer to detect invalid writes.

7.3 Performance Traps

  • O(n) search on every alloc without size classes.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add allocation statistics output.

8.2 Intermediate Extensions

  • Implement segregated free lists.

8.3 Advanced Extensions

  • Thread-safe allocator with locks or per-thread arenas.

9. Real-World Connections

9.1 Industry Applications

  • Production allocators (jemalloc, tcmalloc).
  • jemalloc: advanced allocator with arenas.
  • dlmalloc: classic allocator design.

9.3 Interview Relevance

  • Common systems interview topic on memory management.

10. Resources

10.1 Essential Reading

  • OSTEP Ch. 17
  • CS:APP Ch. 9

10.2 Video Resources

  • University allocator lectures

10.3 Tools & Documentation

  • man sbrk, man mmap

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain headers/footers and alignment.
  • I can define internal vs external fragmentation.

11.2 Implementation

  • malloc/free/realloc pass tests.
  • coalescing works on randomized workloads.

11.3 Growth

  • I can explain allocator trade-offs in an interview.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • malloc/free work and pass a randomized test.

Full Completion:

  • realloc and stats implemented.

Excellence (Going Above & Beyond):

  • Segregated lists and thread safety.