Garbage Collection: C, Mark-Sweep & Copying

Learning Goal: To implement both a Mark-and-Sweep and a Semispace Copying Garbage Collector from scratch in C. By building these systems alongside a minimal stack-based virtual machine, you will master low-level memory layout, pointer manipulation, manual allocation limits, dynamic reachability tracing, and strategies to resolve heap fragmentation.

Prerequisites

• C Programming Proficiency: Comfort with structs, unions, raw pointers, dynamic memory allocation (malloc, free), and bitwise manipulation.
• Basic Data Structures: Familiarity with stacks, queues, linked lists, and directed graphs.
• Development Environment: A Unix-like terminal environment with gcc or clang and make.

Estimated Total Study Time: 26 Hours

---

Module 1: Pointer Foundations & Manual Memory in C

This module establishes the core hardware-level foundations of system memory. You will study how compiler-managed stack frames contrast with runtime-managed heap allocations. Crucially, this module features a heavy bridging topic on implementing a custom memory allocator, ensuring you understand how to manage, slice, and keep metadata headers on raw memory pools before attempting to automate their cleanup.

Recommended Videos

Why this video

This course is a comprehensive deep-dive into how pointers represent raw physical addresses in hardware. It walks systematically through pointer arithmetic, indirection, the difference between value and reference passes, and provides the baseline fluency required to safely cast and manipulate headers within a manual heap structure.

---

Why this video

Although presented in C++, the hardware principles detailed here apply directly to C. The video visually demonstrates the physical structure of stack frames (local allocations, LIFO execution, fast CPU pointer increments) versus the global heap. This conceptual model is vital because your future garbage collector will treat stack-allocated variables as the "root set" to scan the heap.

---

Why this video

This video explains how memory allocators manage the heap under the hood. It discusses how libraries track block sizes and addresses, and how to write a custom tracking wrapper to monitor alloc/free cycles. This serves as an excellent conceptual bridge to managing raw memory.

---

Why this video

To automate memory, you must first understand how to structure raw chunks of memory manually. This full-length development video guides you in reserving a contiguous raw memory block and splitting it into functional blocks using custom metadata headers. It teaches you how allocators divide raw bytes, manage sizes, and execute internal bookkeeping without relying directly on default glibc malloc/free abstractions.

Knowledge Checkpoint

• Diagram a thread stack frame pointing to a heap-allocated memory block, listing which addresses are managed automatically by the CPU and which must be freed by software.
• Explain the layout of a typical dynamic allocation memory header (e.g., size field, allocation flag) and how a manual allocator navigates raw memory blocks using pointer offsets.
• Demonstrate pointer arithmetic in C by casting a raw byte buffer pointer to a custom metadata structure pointer and extracting its fields.

---

Module 2: Introduction to Automatic Memory Management

This module shifts the paradigm from manual memory freeing to automated cleanup. You will explore the theoretical boundaries of garbage collection, dissect the runtime relationship between the application (the mutator) and the memory manager (the collector), and contrast reference counting with tracing collectors.

Recommended Videos

Why this video

This summary of Bacon, Attanasio, Lee, Rajan, and Smith’s landmark paper covers the duality of garbage collection. It explains how tracing (identifying live objects to sweep dead ones) and reference counting (tracking incoming edges to immediately free dead objects) are duals of each other, laying a robust conceptual foundation for modern automatic memory management.

---

Why this video

This video explains the technical challenges of introducing garbage collection to systems languages like C and C++. It discusses how the lack of a managed runtime and the presence of raw pointer casts complicate automatic reachability tracing, highlighting why your custom VM will need strict tracking of root pointers.

---

Why this video

This video isolates the three core responsibilities of any tracing garbage collector: identifying live objects starting from roots, reclaiming memory from dead objects, and optionally relocating structures. It defines these concepts clearly, helping you plan your upcoming implementation.

Knowledge Checkpoint

• Define the terms mutator and collector and describe how they interact during a program's execution.
• Explain why standard reference counting fails to reclaim cyclic data structures (e.g., node A points to B, B points to A, but both are unreachable from roots), and how tracing collectors solve this.
• Describe the performance and memory footprint trade-offs between reference counting (immediate cleanup, constant overhead) and tracing (deferred batch cleanup, pause times).

---

Module 3: Mark-and-Sweep: Theory & Design

This module delves into the mechanics of the oldest and most fundamental tracing algorithm: Mark-Sweep. You will study how runtime graphs are traversed, how Dijkstra's Tri-Color Marking abstractly describes collection progress, and how this process results in memory fragmentation.

Recommended Videos

Why this video

This lecture provides an in-depth walkthrough of the Mark-and-Sweep algorithm. It illustrates how the collector traverses the application's object graph starting from stack/global roots, traces live references using depth-first search (DFS) or breadth-first search (BFS), and sweeps unreachable blocks back to the free list.

---

Why this video

This academic segment offers a precise look at the two distinct phases of Mark-Sweep. It breaks down the state mutations of objects during tracing, detailing the exact logic gate that separates marked (live) entities from unmarked (dead) entities, and showing how the sweep step reclaims dead blocks without moving live ones.

---

Why this video

Tri-color marking is an essential mental model for tracing collectors. This video explains how objects are classified during a collection cycle: White (unvisited/dead), Gray (visited but children unexamined), and Black (visited alongside all reachable children). This abstraction is crucial for structuring your C code's queue and traversal loops.

Knowledge Checkpoint

• Draw a directed graph of objects and trace a mark phase, coloring nodes White, Gray, or Black as a BFS traversal proceeds.
• Explain how a sweep phase navigates the heap sequentially and reconstructs a "free list" of unallocated memory chunks.
• Define memory fragmentation and explain why a naive Mark-and-Sweep collector exacerbates it when allocating objects of varying sizes over time.

---

Module 4: Building a Mark-and-Sweep GC in C

With the theory established, you will now write a fully functional Mark-and-Sweep garbage collector integrated into a minimal stack-based virtual machine. Because video tutorials specifically implementing GC in C are rare, this module provides comprehensive technical specifications to guide your implementation alongside the resources.

Technical Scaffolding: Structuring Your VM & GC

Your implementation should feature a VM with a call stack of objects, enabling you to clearly identify the "root set."

#define STACK_MAX 256 #define INITIAL_GC_THRESHOLD 8

typedef enum { OBJ_INT, OBJ_PAIR } ObjectType;

typedef struct sObject { ObjectType type; unsigned char marked; struct sObject* next; // Singly-linked list of all allocated objects

union { int value; struct { struct sObject* head; struct sObject* tail; } pair; };

} Object;

typedef struct { Object* stack[STACK_MAX]; int stackSize; Object* firstObject; // Head of VM-allocated objects list int numObjects; // Track current allocations int maxObjects; // Threshold to trigger GC } VM;

Writing the Collector

1. Mark Phase: Iterate through the VM's active stack. For every object found, call a recursive mark(Object* obj) function that flips obj->marked = 1. If the object is a pair, recursively mark its head and tail children.
2. Sweep Phase: Iterate through the global firstObject linked list. If marked is 0, unchain the object from the list, call free(), and decrement the allocation counter. If marked is 1, reset it to 0 for the next cycle.

Recommended Videos

Why this video

Though brief, this video demonstrates the literal loop mechanics of iterating through a tracked list of pointer allocations in C and executing ordered deallocations. It provides a visual guide to the physical clean-up phase of a custom collector.

---

Why this video

This video analyzes Cello, a library that brings high-level runtime behavior (including garbage collection) to C. It offers practical context on managing pointer structures, custom object types, and memory wrappers, serving as an architectural reference for your custom VM.

Module 4 Guided Lab Instruction

1. Initialize the VM: Set stackSize = 0, firstObject = NULL, numObjects = 0, and maxObjects = INITIAL_GC_THRESHOLD.
2. Allocate Safely: Create a function Object* newObject(VM* vm, ObjectType type). When vm->numObjects == vm->maxObjects, trigger a gc(vm) collection cycle before allocating. Update maxObjects dynamic thresholds dynamically based on post-collection occupancy.
3. Handle Edge Cases: Prevent stack overflows during deep recursive markings of linked data structures by using a flat array as an explicit mark queue (implementing tri-color marking).

Knowledge Checkpoint

• Implement a working mark function in C that correctly traverses nested parent-child references without infinite looping on cyclic object graphs.
• Implement a working sweep function in C that updates VM linked lists, frees unreferenced memory, and preserves live objects.
• Write a test suite simulating heavy VM stack push/pop actions, proving that unreferenced allocations are dynamically reclaimed when thresholds are breached.

---

Module 5: Copying GC & Cheney's Algorithm Theory

This module addresses memory fragmentation by studying Copying Garbage Collection. You will explore the theory of Cheney’s Semispace Collector, which splits dynamic memory into equal From-Space and To-Space blocks, resolving fragmentation by compacting live objects during collection.

Semispace Heap Layout: +-----------------------------------+-----------------------------------+ | FROM-SPACE | TO-SPACE | | [Obj A] [Obj B] [Free...] | (Empty space reserved for copy) | +-----------------------------------+-----------------------------------+

Recommended Videos

Why this video

This video explains Cheney's non-recursive copying collection algorithm. It uses a "two-finger" pointer system (scan and free) traversing the destination space to execute a breadth-first copying traversal of live objects, eliminating recursion stack overhead.

---

Why this video

This academic lecture provides a detailed walkthrough of the "Stop and Copy" garbage collection phase. It demonstrates how pointer configurations shift as a program transitions from runtime allocations to a collection freeze, compacting active elements into contiguous memory.

---

Why this video

This animated clip provides a clear visual demonstration of semispace collectors in action. It illustrates how the "bump-pointer" allocator sequentially places allocations in the active space and how objects are compacted into the target space when a collection is triggered.

Knowledge Checkpoint

• Explain the dual-space layout of a semispace allocator and why it requires twice the memory footprint of an in-place Mark-and-Sweep collector.
• Detail the functions of the scan and free pointers in Cheney’s algorithm during a collection phase.
• Describe the purpose of "forwarding pointers" and how they prevent copying the same shared object multiple times when processing the object graph.

---

Module 6: Building a Copying GC in C

In this final module, you will implement a Semispace Copying Garbage Collector in C using Cheney's algorithm. Because video tutorials on writing a Cheney collector in C are virtually non-existent, the technical blueprint below provides the necessary guidance to complete your implementation.

Technical Blueprint: Cheney's Semispace Collector in C

You will allocate a single large block of memory and divide it into two equal semispaces: from_space and to_space.

typedef struct { void* from_space; void* to_space; size_t space_size; void* alloc_ptr; // Current allocation position in from_space void* scan_ptr; // Cheney scanning finger in to_space void* free_ptr; // Cheney copying finger in to_space } SemispaceHeap;

// Forwarding pointer layout inside allocated objects typedef struct sCopyObject { ObjectType type; struct sCopyObject* forwarding; // Points to copy in to_space once migrated union { int value; struct { struct sCopyObject* head; struct sCopyObject* tail; } pair; }; } CopyObject;

The Cheney Tracing Implementation Loop

To trigger collection, initialize scan_ptr and free_ptr at the beginning of to_space.

1. Evacuate Roots: Copy all objects directly referenced by the VM stack from from_space into to_space. For each copied object:
   • Write its new address to its original forwarding field in from_space.
   • Advance the free_ptr in to_space.
2. Scan Phase: Loop while scan_ptr < free_ptr:
   • Examine the object at scan_ptr.
   • For any pointer field (e.g., head, tail) within that object, check if the referenced object has already been copied (i.e., has a forwarding pointer).
   • If copied, update the field to point to the forwarded address.
   • If not copied, copy it to free_ptr, set its forwarding address, and advance free_ptr.
   • Advance scan_ptr by the current object's size.
3. Swap Spaces: Once scan_ptr == free_ptr, swap the roles of from_space and to_space by exchanging their pointers. Set the allocation pointer (alloc_ptr) to free_ptr inside the new active space.

Recommended Videos

Why this video

This video reviews a JVM implementation written in a systems-level language (Rust) featuring a Cheney-based semispace copying collector. The architectural discussion translates directly to C design patterns.

---

Why this video

This presentation explains the mechanics of region allocators and bump pointer allocation layouts. Understanding how to manage sequential allocation pointers and boundary conditions is essential for constructing a reliable semispace heap.

Module 6 Guided Lab Instruction

1. Allocate Memory Pools: Use malloc() to allocate a single large memory block (e.g., 64KB) and split it into two 32KB pools representing from_space and to_space.
2. Build the Bump Allocator: Implement void* allocate(SemispaceHeap* heap, size_t size). If alloc_ptr + size exceeds the bounds of from_space, initiate collection.
3. Simulate Heap Fragmentation & Compare: Write a test runner that allocates and discards millions of small transient nodes. Compare the memory utilization, execution speed, and cache coherence of your Copying GC against your Mark-and-Sweep GC from Module 4.

Knowledge Checkpoint

• Implement a working copy helper function in C that relocates an object, sets its forwarding pointer, and returns its new address.
• Implement Cheney's scanning loop using scan_ptr and free_ptr to process all reachable child objects.
• Write a benchmark showing that a Semispace Copying GC maintains a contiguous free memory space after frequent allocations, avoiding the fragmentation seen in Mark-and-Sweep.

---

Course Map

---

Key People Index

• Dr. Jonas Birch (@dr-Jonas-Birch): Systems programmer and educator specializing in low-level allocations. His custom allocator and garbage collector video guides serve as the practical baseline for raw pointer management throughout this curriculum.
• C. J. Cheney: Computer scientist who invented the Cheney non-recursive copying garbage collection algorithm in 1970, introducing the elegant "two-finger" queue implementation.
• Richard Jones: Leading authority on garbage collection and author of The Garbage Collection Handbook, whose theoretical classifications on tracing and concurrent collection inform the modules' structural designs.
• Michael Bernstein: Tech researcher whose presentations on "A Unified Theory of Garbage Collection" clarify the underlying relationship between tracing and reference counting algorithms.

---

Final Self-Assessment

Complete this comprehensive self-assessment to verify your mastery of garbage collection in C:

• Pointer Safety: I can compile my custom memory allocator code using GCC flags (-Wall -Wextra -Werror) without experiencing warnings or undefined behaviors.
• Stack vs Heap Distinction: I can identify where every variable in my program is allocated and can trace stack references to heap memory.
• Tri-Color Tracking: I can explain tri-color marking and trace how an object graph is traversed and colored during collection.
• Cyclic Graph Resolution: My Mark-and-Sweep GC can identify and reclaim cyclic data structures that have lost their connection to roots.
• Header Structure Configuration: My C structs feature compact metadata headers, using minimum bit allocations to store markers without wasting space.
• No Leak Verification: I have tested my VM and GC under Valgrind, verifying that all allocated memory blocks are successfully freed by the collector upon exit.
• Cheney Pointer Synchronization: My copying collector correctly synchronizes scan_ptr and free_ptr, halting precisely when they meet in to_space.
• Forwarding Pointer Integrity: My Cheney implementation successfully writes forwarding addresses to old objects, preventing duplicate copies of shared references.
• Bump Pointer Allocation: My semispace allocator uses a sequential bump pointer within the active space, eliminating free list traversal times.
• Dynamic GC Tracing: I can trigger collection dynamically when memory limits are reached, run the GC cycle, adjust heap thresholds, and resume normal program execution.
• Benchmarking Evaluation: I have profiled both collectors under heavy load, documenting the execution speed, cache locality, and fragmentation trade-offs of Mark-and-Sweep versus Semispace Copying.