Memory Management & Garbage Collection

A running program uses several distinct memory regions. The stack is a LIFO region managed automatically by the CPU as functions are called and return — local variables live and die with their stack frame. The heap is a large, general-purpose pool of memory that persists across function calls and lives until explicitly reclaimed. Understanding why the heap exists is the first step.

When you don't know at compile time how large a data structure will be (a list that grows, a string the user types), or when data must outlive the function that created it, you need the heap. The operating system gives your process a contiguous range of virtual address space; a heap allocator (e.g. ptmalloc, jemalloc, mimalloc) manages sub-division of that space into individual allocations.

A heap allocator must solve a non-trivial problem: given a pool of raw bytes and a sequence of malloc(n) and free(ptr) requests in arbitrary order, maintain a data structure (typically a combination of free-lists, bins, and boundary tags) that allows:

• Fast allocation of a block of at least n bytes
• Fast deallocation when given a pointer
• Low fragmentation — both internal (wasted bytes inside a block) and external (free space that can't be used because it's split into too-small pieces)

This is already a rich algorithmic problem, and it's the foundation on top of which all higher-level memory management is built.

/* C: explicit heap use */
#include <stdlib.h>
#include <string.h>

char* make_greeting(const char* name) {
    // Stack cannot hold this — it must outlive this frame
    size_t len = strlen(name) + 8;
    char* buf = malloc(len);   // allocate on heap
    snprintf(buf, len, "Hello, %s", name);
    return buf;  // caller is now responsible for free()
}

int main() {
    char* g = make_greeting("Alice");
    puts(g);
    free(g);  // must free — or leak
    return 0;
}

In C (and to a lesser extent C++), the programmer calls malloc/free (or new/delete) directly. The discipline required is simple to state but notoriously difficult to maintain at scale:

1. Every allocation has exactly one owner.
2. The owner frees the memory exactly once, after the last use.

Violations produce a taxonomy of bugs:

Memory leak: allocated memory is never freed. The program's heap grows without bound. In a long-running server this eventually causes OOM kills.

Use-after-free (UAF): a pointer is dereferenced after the memory it points to has been freed. The allocator may have reused that memory for something else, so you are reading or writing arbitrary other data. This is one of the most exploited vulnerability classes.

Double-free: free is called twice on the same pointer. The allocator's internal metadata gets corrupted, leading to heap corruption and exploitable conditions.

Buffer overflow: writing past the end of an allocated region corrupts adjacent allocator metadata or other objects.

These bugs are so endemic that entire mitigations (ASLR, stack canaries, safe unlinking in ptmalloc, memory-safe languages) exist primarily to combat them. Understanding their root cause — aliasing without lifetime tracking — is the key insight that motivates both garbage collection and ownership systems.

/* Classic use-after-free — undefined behavior */
int* p = malloc(sizeof(int));
*p = 42;
free(p);
// allocator may reuse this memory
printf("%d\n", *p);  // UAF: reads garbage or another object

/* Classic double-free — heap corruption */
int* q = malloc(sizeof(int));
free(q);
free(q);  // undefined behavior: corrupts allocator state

/* Memory leak in a loop */
for (int i = 0; i < 1000000; i++) {
    char* s = malloc(1024);
    sprintf(s, "item %d", i);
    // forgot to free(s) — 1 GB leaked
}

The simplest automatic memory management strategy: attach a counter to each heap object. The counter tracks how many references (pointers) currently point to that object. When a new reference is created, increment; when a reference is dropped, decrement. When the count hits zero, the object is immediately freed.

Advantages:

• Immediate reclamation: memory is freed the instant it becomes unreachable, not at some future GC pause.
• Incremental cost: no stop-the-world pauses; overhead is spread across each reference operation.
• Simple to implement and reason about.

Disadvantages:

• Cycle problem: if object A holds a reference to B and B holds a reference to A, neither count ever reaches zero even when no external references exist. This is a fundamental flaw — reference counting alone cannot collect cycles.
• Throughput overhead: every pointer copy and drop requires atomic counter updates. In multithreaded code, these must be atomic operations (e.g., std::atomic<int>), which are expensive.
• Cache pressure: counter updates write to the object's header, polluting cache lines.

Real-world use: CPython uses reference counting as its primary strategy, augmented by a cycle-detecting backup collector for the cycle problem. Swift and Objective-C use ARC (Automatic Reference Counting), which is reference counting inserted by the compiler at compile time. C++'s std::shared_ptr is a library-level reference-counted smart pointer.

The cycle problem is solved in practice by introducing weak references — references that do not increment the count and do not keep objects alive. A doubly-linked list where each node has a strong next and a weak prev avoids the cycle. In Python, the weakref module provides this.

# Python's refcount is visible via sys.getrefcount
import sys

a = [1, 2, 3]         # refcount = 1 (plus 1 for getrefcount arg)
print(sys.getrefcount(a))  # prints 2
b = a                  # refcount = 2 (a and b both point here)
print(sys.getrefcount(a))  # prints 3
del b                  # refcount drops back to 2

# Cycle: a and b keep each other alive — refcounts never reach 0
a = {}
b = {}
a['other'] = b
b['other'] = a
del a
del b
# Both objects still alive! Python's cycle GC will collect them later.

Tracing garbage collectors work differently: instead of tracking counts, they periodically trace all live objects from a set of roots (global variables, stack frames, registers) and mark everything reachable. Anything not marked is garbage and can be reclaimed.

Mark phase: starting from roots, do a graph traversal (DFS or BFS) over the object graph. Mark each visited object as live. The key invariant: any object not reachable from roots is unreachable by the program and is safe to collect.

Sweep phase: scan the entire heap linearly. Any object not marked is dead; reclaim it by returning it to the free list. Clear the marks from live objects for the next cycle.

Strengths:

• Correctly handles cycles — if a cycle is unreachable from roots, none of its nodes are marked, so all are collected.
• Conceptually clean: the invariant "reachable ≡ live" is precise and provable.

Weaknesses:

• Stop-the-world: in the naive form, the entire program must be paused during collection, because the object graph must not change while we traverse it. This causes latency spikes.
• Fragmentation: reclaimed memory is scattered across the heap as a free list. Over time, external fragmentation can make it impossible to satisfy large allocations even when enough total free bytes exist.
• Heap scan: the sweep phase touches every object, even short-lived ones that were already dead.

Tri-color invariant (for incremental/concurrent GC): objects are colored white (not yet seen), gray (seen but children not yet traced), or black (fully traced). The invariant that no black object points to a white object ensures correctness during concurrent marking. This is the foundation of modern concurrent GCs like Go's and Java's G1.

# Mark-and-sweep in pseudocode

def mark_and_sweep(roots, heap):
    # Mark phase: BFS/DFS from all roots
    worklist = list(roots)
    while worklist:
        obj = worklist.pop()
        if not obj.marked:
            obj.marked = True
            for child in obj.references():   # all pointers inside obj
                worklist.append(child)

    # Sweep phase: reclaim unmarked, clear marks on survivors
    for obj in heap.all_objects():
        if obj.marked:
            obj.marked = False   # reset for next GC cycle
        else:
            heap.free(obj)       # reclaim garbage

Mark-and-sweep leaves free memory scattered as a free list — a fragmentation problem. Copying collectors solve this by moving live objects.

The heap is divided into two equal semi-spaces: from-space and to-space. Allocation is bump-pointer allocation into from-space — just increment a pointer, which is O(1) and cache-friendly. When from-space is full, the GC copies all live objects (traversed from roots) into to-space, placing them compactly at the start. From-space becomes entirely free. The roles of the spaces swap and the program resumes.

Cheney's algorithm does this with a simple BFS using to-space itself as the queue: the scan pointer chases the free pointer through to-space, processing each copied object and copying its children. The key operation is forwarding: when an object is first copied, a forwarding pointer is stored in its old location so that any other reference to the same object will find the new address rather than creating a duplicate.

Benefits:

• Allocation is O(1) bump pointer — faster than malloc's free-list search.
• Compaction eliminates external fragmentation.
• Only live objects are touched — dead objects have zero cost.

Cost: requires 2x memory (two semi-spaces). Copying is expensive if the live set is large (most objects survive). This is why copying collectors shine in the young generation (few survivors) but are rarely used for the full heap.

Forwarding pointer mechanism: after copying object A from address 0x100 to 0x200, write forward → 0x200 at 0x100. Any other pointer to 0x100 checks: is there a forwarding pointer? Yes → update to 0x200.

# Cheney's copying GC (pseudocode)

class CopyingGC:
    def collect(self):
        self.free = start_of(to_space)
        scan = self.free

        # Copy all roots
        for root in roots:
            root.ref = self.copy(root.ref)

        # Process grey objects (BFS via scan pointer)
        while scan < self.free:
            obj = object_at(scan)
            for field in obj.pointer_fields():
                field.value = self.copy(field.value)
            scan += sizeof(obj)

        swap(from_space, to_space)

    def copy(self, obj):
        if has_forwarding_ptr(obj):
            return forwarding_ptr(obj)    # already copied
        new_addr = self.free
        memcpy(new_addr, obj, sizeof(obj))
        self.free += sizeof(obj)
        set_forwarding_ptr(obj, new_addr) # leave breadcrumb
        return new_addr

The generational hypothesis is an empirical observation found consistently across almost all workloads: most objects die young. In a typical Java program, over 90% of objects become garbage within milliseconds of allocation. They are temporary buffers, iterator objects, message wrappers — created and discarded in tight loops.

Generational GCs exploit this by dividing the heap into generations (typically two or three: young/nursery/eden, and old/tenured). The young generation is small and collected frequently using a fast copying collector. The old generation is larger and collected infrequently.

The key insight: by only collecting the young generation (a minor GC), you pay a very small cost (only scan young-gen roots + old→young pointers) to reclaim most garbage. Full GCs (major/old-gen collection) are rare.

Write barrier: how do we find old→young pointers without scanning the entire old generation? A write barrier — a small piece of code executed on every pointer write — records any write of a young-gen pointer into an old-gen object into a remembered set or card table. The minor GC treats the remembered set as additional roots.

Promotion: objects that survive enough minor GCs are promoted to the old generation. The threshold (tenuring threshold) is a tuning parameter.

Real-world GC architectures:

• JVM HotSpot (G1, ZGC, Shenandoah): generational + concurrent + region-based
• V8 (Chrome/Node.js): Scavenger (young) + Mark-Compact (old)
• Go: non-generational tri-color concurrent mark-sweep (GC team has been adding generational support)
• .NET CLR: three generations (gen0, gen1, gen2) + large object heap

# Illustrating the generational hypothesis with a simple simulation
import random

def simulate_object_lifetimes(n=100_000):
    lifetimes = []
    for _ in range(n):
        # Exponential-ish distribution: most die immediately
        if random.random() < 0.90:
            lifetimes.append(random.randint(1, 5))   # young: die in <5 minor GCs
        else:
            lifetimes.append(random.randint(100, 10_000))  # old: long-lived
    died_young = sum(1 for l in lifetimes if l < 10)
    print(f"{died_young/n*100:.1f}% of objects died before 10 minor GCs")
    # Typical output: ~90.0% of objects died before 10 minor GCs

simulate_object_lifetimes()

Stop-the-world GC pauses are unacceptable for latency-sensitive applications: a 500ms pause in a web server causes request timeouts; a 100ms pause in a game causes a visible hitch. Modern GCs address this by running concurrently with the application or incrementally.

Incremental GC: instead of doing all marking in one pause, interleave small increments of GC work with program execution. The mutator (the program) and the collector take turns. Pauses are short (bounded by the time per increment). The challenge: the program may modify the object graph between increments, potentially invalidating work already done.

Concurrent GC: the GC mark phase runs in a background thread while the mutator runs in parallel. This reduces pause time to nearly zero for the mark phase. The challenge is much harder: the mutator can create new pointers, delete pointers, or modify the graph at any moment.

Both require a write barrier (or sometimes a read barrier) to maintain invariants. The tri-color invariant ensures that no black object points directly to a white object — if a mutator creates such a reference, the write barrier must re-gray the black object or shade the white object gray.

SATB (Snapshot-At-The-Beginning): used by G1 and Shenandoah. Take a logical snapshot of the object graph at the start of the GC cycle; any object that was live at that point is treated as live for this cycle even if the mutator deletes references. The pre-write barrier saves the old value of any pointer before it is overwritten.

Pause times in practice:

• JVM ZGC: sub-millisecond pauses regardless of heap size, even for 1TB heaps
• JVM Shenandoah: concurrent compaction for sub-millisecond pause
• Go GC: typically under 1ms for sub-GB heaps

The price: higher CPU overhead (GC threads compete with app threads), higher memory overhead (SATB needs to retain more objects), and more engineering complexity.

# Tri-color invariant and write barrier (pseudocode)

# Colors: WHITE = not seen, GRAY = seen but children not scanned,
#          BLACK = fully scanned

# SATB write barrier (pre-write)
def write_barrier_satb(obj, field_index, new_value):
    old_value = obj.fields[field_index]
    # Snapshot: push old reference onto mark stack
    # so it won't be missed even if mutator deletes it
    if old_value is not None and color(old_value) == WHITE:
        mark_stack.push(old_value)  # shade gray
        set_color(old_value, GRAY)
    obj.fields[field_index] = new_value   # do the actual write

# Incremental-update write barrier (post-write)
def write_barrier_incremental(obj, field_index, new_value):
    obj.fields[field_index] = new_value
    # If black object now points to white, re-gray it
    if color(obj) == BLACK and color(new_value) == WHITE:
        set_color(new_value, GRAY)
        mark_stack.push(new_value)

Rust takes a radically different approach: memory management is handled at compile time by a type system that tracks ownership and lifetimes. There is no garbage collector and no runtime overhead beyond what C would have.

Ownership rules (the three fundamental rules):

1. Every value has exactly one owner (a binding/variable).
2. When the owner goes out of scope, the value is dropped (freed).
3. Ownership can be moved (transferred) to a new owner, after which the old owner is invalid.

Move semantics: when you assign let b = a;, ownership of the value is moved from a to b. a is no longer valid. The compiler statically verifies this — you cannot accidentally use a moved-from variable.

Borrowing: often you want to use a value without taking ownership. Rust allows references, which borrow access:

• &T — shared (immutable) reference: many readers, no writers simultaneously
• &mut T — exclusive (mutable) reference: exactly one writer, no other references

The borrow checker ensures these rules at compile time:

• You can have any number of &T references OR exactly one &mut T, never both.
• References must not outlive the owned value (the lifetime system).

This is essentially the readers-writer lock invariant enforced statically. The result: no data races, no use-after-free, no dangling pointers — all guaranteed at compile time, with zero runtime cost.

Why this works: the ownership model makes aliasing and mutation mutually exclusive. Use-after-free requires aliasing (one pointer frees, another uses). The borrow checker's single-writer / multiple-reader rule prevents the aliasing pattern that causes these bugs.

// Rust: ownership, move, and borrowing

fn main() {
    // OWNERSHIP
    let s1 = String::from("hello");  // s1 owns the heap string
    let s2 = s1;                      // MOVED: s1 no longer valid
    // println!("{}", s1);           // compile error: use of moved value
    println!("{}", s2);              // fine

    // BORROWING (shared reference)
    let s3 = String::from("world");
    let len = calculate_length(&s3);  // borrow, not move
    println!("{} has length {}", s3, len);  // s3 still valid

    // MUTABLE BORROWING
    let mut s4 = String::from("hello");
    change(&mut s4);  // exclusive mutable borrow
    println!("{}", s4);

    // LIFETIME ERROR: cannot return reference to local
    // fn dangle() -> &String {
    //     let s = String::from("hi");
    //     &s  // compile error: s dropped at end of fn, reference dangling
    // }
}

fn calculate_length(s: &String) -> usize {
    s.len()  // borrow: we can read but not move
}  // borrow ends here; s3 not dropped

fn change(s: &mut String) {
    s.push_str(", world");
}

C++ introduced RAII (Resource Acquisition Is Initialization) as a way to use the deterministic destructor mechanism of stack objects to manage heap allocations automatically. Rust formalized and generalized this into its ownership system.

RAII principle: tie the lifetime of a resource (heap allocation, file handle, mutex lock) to the lifetime of a stack object. When the stack object's destructor runs (always, even on exceptions), it releases the resource.

C++ smart pointers:

• std::unique_ptr<T>: single-owner, no reference counting, zero overhead over raw pointer. When unique_ptr goes out of scope, it calls delete. Ownership is transferable via move but not copyable. This is the C++ analog of Rust's owned values.
• std::shared_ptr<T>: reference-counted shared ownership. Multiple shared_ptrs can point to the same object; the last one to die deletes it. Thread-safe reference counting via atomic increment/decrement.
• std::weak_ptr<T>: non-owning reference to a shared_ptr-managed object. Does not increment the reference count. Must be upgraded to shared_ptr to use (and may fail if the object is gone). Solves the cycle problem: break cycles by making one direction a weak_ptr.

The rule of three / five / zero in modern C++ codifies RAII: if your class manages a resource, define (or explicitly default/delete) the destructor, copy constructor, move constructor, copy assignment, and move assignment.

In Rust, every type that owns a resource implements the Drop trait, which is called automatically when the value's scope ends — a formalized, type-system-enforced RAII.

// C++: smart pointers demonstrate RAII
#include <memory>
#include <iostream>

struct Node {
    int val;
    std::shared_ptr<Node> next;
    std::weak_ptr<Node> prev;   // weak to avoid cycle!
    ~Node() { std::cout << "Node " << val << " freed\n"; }
};

int main() {
    // unique_ptr: sole owner, freed when scope ends
    {
        auto p = std::make_unique<int>(42);
        std::cout << *p << "\n";
    } // p destroyed here, int freed automatically

    // shared_ptr: reference counted
    auto a = std::make_shared<Node>();  a->val = 1;
    auto b = std::make_shared<Node>();  b->val = 2;
    a->next = b;   // strong: a holds b alive
    b->prev = a;   // weak: does NOT prevent a from being freed
    // When main exits, both a and b are freed (no cycle in strong refs)
    return 0;
}

When objects are collected, should the collector run user-defined cleanup code? This is the finalization problem, and it is significantly more subtle than it appears.

Destructors (C++/Rust): run deterministically when a stack object goes out of scope (RAII). This is reliable and composable. You know exactly when cleanup runs.

Finalizers (Java/Python): the GC calls a finalizer method (Object.finalize() in Java, __del__ in Python) before an object's memory is reclaimed. This is non-deterministic — you don't know when the GC will run, so you don't know when the finalizer runs. This causes serious problems:

1. No guaranteed execution order: if A and B are both unreachable and A's finalizer references B, B might already be finalized. The JVM solves this partially by resurrecting finalized objects for one more GC cycle.
2. Resurrection: a finalizer can store this in a static field, making the object reachable again and preventing collection. This complicates GC design.
3. Latency: finalizable objects require an extra GC cycle to collect (first GC: mark unreachable, put on finalizer queue; run finalizer; second GC: actually reclaim).
4. No guarantee in many implementations: if the program exits, finalizers may not run at all.

Java deprecated Object.finalize() in Java 9 and removed it in Java 18 in favor of java.lang.ref.Cleaner (a phantom reference–based mechanism that avoids resurrection). Python's __del__ is similarly problematic with cycles.

The lesson: use RAII/deterministic destructors for resource cleanup (file handles, locks, network connections). Never rely on GC finalizers for timely cleanup of critical resources.

// Java: why you cannot rely on finalizers for resource cleanup
public class BadResource implements AutoCloseable {
    private boolean closed = false;

    @Override
    protected void finalize() throws Throwable {
        // WRONG: called non-deterministically, maybe never
        if (!closed) close();
    }

    @Override
    public void close() {
        closed = true;
        System.out.println("resource released");
    }

    // CORRECT PATTERN: try-with-resources (deterministic)
    public static void demo() {
        try (BadResource r = new BadResource()) {
            // use r
        } // r.close() called HERE, deterministically
    }
}

A language is memory safe if it is impossible for a well-typed program to trigger undefined behavior due to memory errors (use-after-free, buffer overflow, use of uninitialized memory, data races on memory). This is a precise, formal property, not a vague aspiration.

Unsafe languages (C, C++): the type system provides no guarantee of memory safety. Any pointer can be cast to any other type. Pointer arithmetic is unrestricted. The compiler assumes the programmer never writes undefined behavior — and if you do, the compiler is allowed to assume it does not happen, which can lead to security vulnerabilities from miscompilation (not just crashes).

Managed languages (Java, Python, Go, JavaScript): memory safety is guaranteed by the runtime. Array bounds are checked, null pointer dereferences throw exceptions rather than corrupting memory, no pointer arithmetic. The cost: performance overhead (bounds checks, GC) and reduced control.

Rust: memory safety is guaranteed by the type system and borrow checker, without runtime overhead. Well-typed safe Rust cannot produce use-after-free, double-free, buffer overflow (in safe code), or data races. The unsafe keyword is an escape hatch that allows raw pointer operations but must be audited manually — it is documented unsafety, not implicit.

Formal grounding: memory safety can be proven via operational semantics. Rust's ownership model has been given a formal model ("Stacked Borrows" by Ralf Jung, used by the Miri interpreter). The Rust team's RustBelt project gave the first machine-checked safety proof of a subset of Rust's type system.

Practical implication: the choice of language is a choice about the guarantees you get and the costs you pay. C gives you control at the cost of safety. Java gives you safety at the cost of a GC. Rust gives you both — safety and control — at the cost of learning a more demanding type system.

// Rust's unsafe escape hatch — documented, auditable unsafety
unsafe fn dangerous_raw_pointer() {
    let mut x = 5;
    let r = &mut x as *mut i32;  // raw pointer — no borrow check
    *r = 42;  // unsafe dereference
    // This is correct here, but the compiler cannot verify it
}

fn safe_caller() {
    // Must explicitly opt in to unsafety
    unsafe { dangerous_raw_pointer(); }
    // If you call this without 'unsafe', compile error
}

// By contrast, a buffer overflow is impossible in safe Rust:
fn no_overflow() {
    let v = vec![1, 2, 3];
    // v[10]; // panics with bounds-check error — no UB
    // v.get(10) returns None safely
}