Skip to content

Lesson 24.5 — Memory management: reference counting, tracing collection, ownership, regions

Techniques: reference counting (Swift ARC) — every object carries a count of references; the compiler inserts retain/release and optimizes pairs away; tracing GC with stack maps and statepoints — the runtime finds live objects from roots, and the compiler tells it which stack slots and registers hold pointers at every safepoint (gc.statepoint, stack maps); ownership and borrowing (Rust) — every value has one owner, moves transfer it, borrows are checked at compile time, and drops are inserted where the owner's scope ends: no run-time bookkeeping at all; regions — allocate into an arena and free the whole arena at once, by construction (obstacks, pools) or by inference (Tofte–Talpin) · Pebble implements: none: Pebble has no heap. The lesson's drills and quiz trace each design on the same allocation sequence, and the boxes read LLVM's statepoint stack maps, rustc's diagnostics and glibc's obstacks · Drills: refcount-trace, gc-roots · Prerequisites: Lesson 14.3 (liveness), Lesson 24.2 (stack maps of deoptimization points: the same section), Lesson 9.4 (address spaces) · Time: 6 hours

Pebble's values live on the stack and are copied; the language spec's §11.2 says "nothing has undefined behavior" partly because nothing is freed. The moment a language adds new, an implementer must decide who frees, and when, and the four families of answers each put the cost in a different place: reference counting spends per copy of a reference; tracing spends per collection and needs the compiler's cooperation to know where the pointers are; ownership spends nothing at run time and rejects programs instead; regions spend nothing per object and hold memory until the region dies. This lesson is a survey with the depth contract's full treatment for each: the algorithm the compiler runs (retain/release insertion, root recording, borrow checking, region lowering), the invariant that makes it safe, and the real artifacts: a statepoint's stack map with a base and a derived pointer, rustc's two classic errors, and 100 000 objects freed by one obstack_free.

1. Problem and motivation

Reference counting (Swift ARC)

Collins [Col60] proposed counting references so that an object is freed when the last one disappears. The cost is a count update per reference copy, and the weakness is cycles. Objective-C made programmers write retain/release; Apple's Automatic Reference Counting (2011) moved the insertion into the compiler, and Swift kept it: the front end emits strong_retain/strong_release in SIL under a convention per function parameter (owned: the callee receives a +1 and releases it; guaranteed: the caller keeps the object alive, no counting), and the SIL optimizer removes redundant pairs (ARCSequenceOpts, CopyPropagation) [Swift-ARCOpt]. The result is deterministic destruction (destructors run at the last release, which Swift's deinit relies on) at the price of atomic increments on every copy.

Tracing GC with stack maps and statepoints

McCarthy's Lisp collector (1960) [McC60] finds live objects by tracing from roots and frees the rest. A precise collector must know every root: every pointer in a register or stack slot at the moment it runs. A compiler that keeps pointers in registers and interleaves them with integers must therefore emit, for every point where the collector can run (a safepoint: calls, allocation sites, loop back edges in some designs), a stack map listing where the pointers are. Diwan, Moss and Hudson [DMH92] built this for Modula-3 with derived pointers (an interior pointer p + 8 must be updated together with its base if the object moves). LLVM's gc.statepoint [LLVM-Statepoints] is the modern form: RewriteStatepointsForGC finds base pointers and live pointers at each call, makes the relocation explicit in the IR, and the back end records the locations in .llvm_stackmaps, the same section the deoptimization points of Lesson 24.2 use.

Ownership and borrowing (Rust)

Clarke, Potter and Noble's ownership types [CPN98] and Cyclone's unique pointers [JMG+02] showed that aliasing can be restricted by the type system so that deallocation is decided statically. Rust made it mainstream: each value has exactly one owner; assigning or passing a non-Copy value moves it (the old name is dead); &T and &mut T are borrows whose lifetimes must end before the owner's, with any number of shared borrows or one mutable borrow alive at a time. The compiler (rustc_borrowck, non-lexical lifetimes) checks these rules on MIR, and drop elaboration inserts the destructor calls at the end of each owner's scope, on every path. There is no run-time cost and no collector; the price is that some correct programs are rejected (the second rustc box), and that Rc/RefCell exist for the rest.

Regions

Tofte and Talpin [TT94] inferred, for ML, a region for every allocation: a stack-like arena whose lifetime is a syntactic scope, so that letregion ρ in e allocates into \(\rho\) and frees all of it at the end. Long before, systems programmers used the same idea by hand: glibc's obstacks, Apache's pools, the arena allocators in every compiler (LLVM's BumpPtrAllocator, Lesson 10.1). Allocation is a pointer bump, deallocation is free, and the price is that an object lives as long as its region, so a long region retains garbage; region inference and Cyclone's region types decide the regions statically, MLKit made it a whole ML implementation, and Rust's lifetimes are a descendant.

2. Definitions and algorithms

Definition 24.5.1 (Heap, reference, reachability)

A heap is a finite set of objects \(o\), each with fields; some fields hold references to objects. The roots are the references held by the running program outside the heap: in registers, in stack slots, in globals. An object is reachable if some root refers to it or a reachable object's field does. An unreachable object can never be used again; a memory manager is safe if it never frees a reachable object and complete if it eventually frees every unreachable one.

Reference counting (Swift ARC)

Definition 24.5.2 (Reference count, ownership conventions)

Each object \(o\) carries \(\mathrm{rc}(o) \in \mathbb{N}\). The naive discipline keeps \(\mathrm{rc}(o)\) = the number of references to \(o\) held by variables and fields: creating a reference retains (\(+1\)), destroying one releases (\(-1\)), and \(\mathrm{rc}(o) = 0\) frees \(o\) (releasing its fields first). A function parameter is owned if the caller transfers one count to the callee, which must release it, and guaranteed if the caller promises the object stays alive for the call and transfers nothing.

Algorithm 24.5.3 (Naive retain/release insertion; the drill's oracle)

  • Input: a straight-line sequence of statements over reference variables: x = new, x = y, x = nil, use(x) (guaranteed), consume(x) (owned); the scope end.
  • Output: the sequence with retain/release operations inserted, and the point where each object is freed.
  • Precondition: no cycles among the objects (the sequence creates none: variables only).
  • Postcondition: at every point, \(\mathrm{rc}(o)\) equals the number of variables (plus transferred counts in flight) referring to \(o\); every object is freed at its last release (Theorem 24.5.11).
  • Invariant: the postcondition, per statement.
function InsertRC(stmts):
    for s in stmts:
        match s:
            x = new:        o ← allocate(); rc(o) ← 1            # the allocation's +1 is x's
                            old ← env[x]; env[x] ← o; if old: release(old)
            x = y:          o ← env[y]; if o: retain(o)           # +1 for the new reference...
                            old ← env[x]; env[x] ← o; if old: release(old)   # ...then -1 for the lost one
            x = nil:        old ← env[x]; env[x] ← none; if old: release(old)
            use(x):         nothing                                # guaranteed: caller keeps it alive
            consume(x):     retain(env[x]); [callee] release(env[x])   # owned: +1 transferred, callee's -1
    for x in variables, in name order:  if env[x]: release(env[x])   # scope end
release(o): rc(o) ← rc(o) - 1; if rc(o) = 0: free(o)

Swift's ARC is documented in its optimizer's own terms (quoted; no swiftc in this container)

Reproduce (Swift 6.1 sources; the text is quoted from the file, not produced by running a tool here):

curl -sL https://raw.githubusercontent.com/swiftlang/swift/swift-6.1-RELEASE/docs/ARCOptimization.md | sed -n '/^## Reference Counting Instructions/,/^## Memory Behavior/p'
curl -sL https://raw.githubusercontent.com/swiftlang/swift/swift-6.1-RELEASE/include/swift/SIL/SILArgumentConvention.h | grep -n 'Direct_Owned\|Direct_Guaranteed\|Direct_Unowned' | head -3

Output (quoted from docs/ARCOptimization.md and include/swift/SIL/SILArgumentConvention.h at tag swift-6.1-RELEASE; abridged to the instruction list and the three conventions):

## Reference Counting Instructions

- `strong_retain`
- `strong_release`
- `strong_retain_unowned`
- `unowned_retain`
- `unowned_release`
- `load_weak`
- `store_weak`
- `fix_lifetime`
- `mark_dependence`
- `is_unique`
- `copy_block`
33:    Direct_Owned,
34:    Direct_Unowned,
35:    Direct_Guaranteed,

What to notice: the counting operations are SIL instructions the optimizer sees and moves, not runtime calls it must treat as opaque; Direct_Owned and Direct_Guaranteed are Definition 24.5.2's conventions as an enum on every argument, which is what lets ARCSequenceOpts prove a retain/release pair redundant across a call. is_unique is the copy-on-write test (a count of 1 means the array can be mutated in place), a use of the count that a tracing collector cannot offer.

Tracing GC with stack maps and statepoints

Definition 24.5.4 (Safepoint, stack map, base and derived pointers)

A safepoint is a program point where the collector may run. A stack map for safepoint \(p\) is the set of locations (registers, stack slots) that hold references at \(p\), each tagged as a base pointer (the address of an object) or a derived pointer with its base (an address inside the base's object). The map is exact if it lists every reference live across \(p\) and nothing that is not a reference.

Definition 24.5.5 (Roots at a safepoint)

\(\mathrm{roots}(p) \triangleq \{\, v \in \mathrm{live}(p) \mid v \text{ is a reference} \,\}\), where \(\mathrm{live}(p)\) is the set of values live across \(p\) (defined before \(p\), used after it; Definition 14.3.6). A moving collector, after running at \(p\), must relocate every \(v \in \mathrm{roots}(p)\): overwrite its location with the object's new address (for a derived pointer: the new base plus the same offset).

Algorithm 24.5.6 (Statepoint rewriting, after RewriteStatepointsForGC)

  • Input: a function whose GC references are pointers in address space 1; the set of call sites that are safepoints.
  • Output: every safepoint call replaced by a gc.statepoint with the live references as gc-live operands, followed by gc.relocates that redefine every live reference; uses after the safepoint read the relocated values.
  • Precondition: every reference is a base pointer or derived from one by getelementptr/bitcast/phi/select (no integer-to-pointer casts).
  • Postcondition: after the back end records the gc-live operands' locations, the stack map at each safepoint is exact (Theorem 24.5.12).
  • Invariant: after rewriting safepoint \(p\), no use after \(p\) refers to a pre-\(p\) reference except through its gc.relocate.
function RewriteStatepoints(F):
    live ← liveness of reference values (backward dataflow, Lesson 14.3)   # computeLiveInValues
    for each safepoint call p:
        L ← { v ∈ live-out(p) with reference type }                           # findLiveSetAtInst
        for v in L: base[v] ← FindBase(v)                                    # findBasePointers: through gep/phi/select
        token ← gc.statepoint(callee, args) [ "gc-live"(L ∪ bases) ]
        for v in L: v' ← gc.relocate(token, index of base[v], index of v)
        rewrite every use of v dominated by p to v'                          # relocationViaAlloca / SSA update
    return F

function FindBase(v):
    if v is an allocation or an argument: return v
    if v = gep(b, …): return FindBase(b)
    if v = phi(v1, …, vk): return phi(FindBase(v1), …)                    # a base phi is inserted
    if v = select(c, a, b): return select(c, FindBase(a), FindBase(b))

A statepoint with a base and a derived pointer, and its stack map

Reproduce (opt, llc, llvm-readobj 23.1.2, x86-64):

cat > sp.ll <<'EOF'
declare void @collect()
define i64 @sum(ptr addrspace(1) %p) gc "statepoint-example" {
entry:
  %v = load i64, ptr addrspace(1) %p
  %q = getelementptr i64, ptr addrspace(1) %p, i64 1
  call void @collect()
  %w = load i64, ptr addrspace(1) %q
  %s = add i64 %v, %w
  ret i64 %s
}
EOF
opt -passes=rewrite-statepoints-for-gc -S sp.ll -o sp-rs.ll && grep -E 'statepoint|relocate|remat' sp-rs.ll
llc -O2 -filetype=obj sp-rs.ll -o sp-rs.o && llvm-readobj --stackmap sp-rs.o | sed -n '/Num Records/,$p'
llc -O2 sp-rs.ll -o - | sed -n '/^sum:/,/retq/p' | grep -E 'mov|call|add'

Output (complete for the three commands):

define i64 @sum(ptr addrspace(1) %p) gc "statepoint-example" {
  %statepoint_token = call token (i64, i32, ptr, i32, i32, ...) @llvm.experimental.gc.statepoint.p0(i64 2882400000, i32 0, ptr elementtype(void ()) @collect, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(ptr addrspace(1) %p) ]
  %p.relocated = call coldcc ptr addrspace(1) @llvm.experimental.gc.relocate.p1(token %statepoint_token, i32 0, i32 0) ; (%p, %p)
  %q.remat = getelementptr i64, ptr addrspace(1) %p.relocated, i64 1
  %w = load i64, ptr addrspace(1) %q.remat, align 4
declare token @llvm.experimental.gc.statepoint.p0(i64 immarg, i32 immarg, ptr, i32 immarg, i32 immarg, ...)
declare ptr addrspace(1) @llvm.experimental.gc.relocate.p1(token, i32 immarg, i32 immarg) #0
Num Records: 1
  Record ID: 2882400000, instruction offset: 18
    5 locations:
      #1: Constant 0, size: 8
      #2: Constant 0, size: 8
      #3: Constant 0, size: 8
      #4: Indirect [R#7 + 8], size: 8
      #5: Indirect [R#7 + 8], size: 8
    0 live-outs: [ ]
    movq    (%rdi), %rbx
    movq    %rdi, 8(%rsp)
    callq   collect@PLT
    movq    8(%rsp), %rax
    addq    8(%rax), %rbx
    movq    %rbx, %rax
    addq    $16, %rsp

What to notice: %q (derived, %p + 8) is live across the call, so Algorithm 24.5.6 puts its base %p in gc-live, relocates %p, and rematerializes %q from the relocated base instead of relocating two pointers (%q.remat): a cheap derived pointer is recomputed rather than recorded. The stack map has one record at offset 18 (the call) with the three header constants and then two locations, both [rsp + 8]: the base pointer, listed twice because the relocate names it as its own base and as the pointer (pairs (base, derived) are the map's unit). The assembly shows the compiler doing what the map promises: %p is spilled to 8(%rsp) before the call and reloaded after it, so that the collector can overwrite the slot with the object's new address; the movq (%rdi), %rbx before the call keeps %v in a callee-saved register, which is an integer and needs no entry.

Ownership and borrowing (Rust)

Definition 24.5.7 (Ownership, move, borrow, lifetime)

Every value has one owner (a variable or a field). let y = x or passing x by value moves the value if its type is not Copy: y is the owner and x is uninitialized afterwards. A borrow &x (shared) or &mut x (exclusive) is a reference with a lifetime \('a\): the set of program points where the reference may still be used (non-lexical lifetimes: from the borrow to its last use). The borrow rules: at every point, a place has either any number of live shared borrows or exactly one live exclusive borrow; a place is not moved, assigned or dropped while a borrow of it is live; a borrow's lifetime is contained in its owner's.

Algorithm 24.5.8 (Borrow checking and drop elaboration on a MIR body, after rustc)

  • Input: a MIR body (a CFG of statements over places), with the moves and borrows made explicit.
  • Output: either a set of errors (E0382 use after move, E0502/E0499 conflicting borrows, E0505 move while borrowed, ...) or the body with a drop(place) inserted on every edge where an owner goes out of scope still initialized.
  • Precondition: the body is typed; each borrow carries a region variable \('r\).
  • Postcondition: an accepted body never reads a moved value, never aliases mutably, and frees every value exactly once (Theorem 24.5.13).
  • Invariant: the dataflow facts (MaybeInitialized, MaybeUninitialized, Borrows) are sound over-approximations at every point.
function BorrowCheck(body):
    init ← forward dataflow: places maybe-initialized (gen: assignment; kill: move, drop)
    live ← liveness of every borrow's region: 'r is live at p iff a reference with lifetime 'r is used at or after p
    borrows ← forward dataflow: borrows in scope at p (gen: &place; kill: 'r no longer live)
    for each statement s at point p:
        for each place read by s:            if not init[p](place): error E0382 (use of moved value)
        for each borrow &mut q created by s: if some live borrow of q or a prefix of q in borrows[p]: error E0502/E0499
        for each move/assign/drop of q by s:  if some live borrow of q in borrows[p]: error E0505/E0506
    return errors

function ElaborateDrops(body):                                    # rustc_mir_transform::elaborate_drops
    for each owner x and each CFG edge where x's scope ends:
        if init is "definitely" at that edge:   insert drop(x)
        else if "maybe":                        insert drop-flag test; drop(x) if the flag is set
        else:                                   nothing

The two errors the borrow checker exists for, and the drops it inserts

Reproduce (rustc 1.94.1):

cat > own.rs <<'EOF'
fn consume(v: Vec<i32>) -> usize { v.len() }
fn main() {
    let v = vec![1, 2, 3];
    let n = consume(v);
    println!("{} {}", n, v.len());
}
EOF
rustc --edition 2021 own.rs 2>&1 | head -9
cat > borrow.rs <<'EOF'
fn main() {
    let mut v = vec![1, 2, 3];
    let first = &v[0];
    v.push(4);
    println!("{}", first);
}
EOF
rustc --edition 2021 borrow.rs 2>&1 | head -9
cat > drop.rs <<'EOF'
pub struct Guard(pub i32);
impl Drop for Guard { fn drop(&mut self) { unsafe { hook(self.0) } } }
extern "C" { fn hook(x: i32); }
pub fn scope(flag: bool) -> i32 {
    let g = Guard(1);
    if flag { return 2; }
    let h = Guard(3);
    g.0 + h.0
}
EOF
rustc --edition 2021 --crate-type lib -O --emit=llvm-ir drop.rs -o drop.ll && sed -n '/define.*scope/,/^}/p' drop.ll | grep -E 'call|br |ret'

Output (the diagnostics' first lines; the IR lines complete):

error[E0382]: borrow of moved value: `v`
 --> own.rs:5:26
  |
3 |     let v = vec![1, 2, 3];
  |         - move occurs because `v` has type `Vec<i32>`, which does not implement the `Copy` trait
4 |     let n = consume(v);
  |                     - value moved here
5 |     println!("{} {}", n, v.len());
  |                          ^ value borrowed here after move
error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable
 --> borrow.rs:4:5
  |
3 |     let first = &v[0];
  |                  - immutable borrow occurs here
4 |     v.push(4);
  |     ^^^^^^^^^ mutable borrow occurs here
5 |     println!("{}", first);
  |                    ----- immutable borrow later used here
  br i1 %flag, label %bb6, label %bb3
  tail call void @hook(i32 noundef 3) #1, !noalias !3
  br label %bb6
  tail call void @hook(i32 noundef 1) #1, !noalias !6
  ret i32 %_0.sroa.0.0

What to notice: E0382 is the init check of Algorithm 24.5.8 (v was moved into consume; the diagnostic points at the move and the later use); E0502 is the borrow-conflict check, and its third note, "immutable borrow later used here", is non-lexical lifetimes: the borrow first is live until line 5, so the &mut at line 4 conflicts; delete line 5 and the program compiles. The IR of scope shows drop elaboration: on the early-return path only g is dropped (hook(1) after the branch), on the fall-through path h then g (hook(3), hook(1)), in reverse declaration order, with no drop flag because both initializations are definite. No counts, no maps: the destructor calls are ordinary code.

Regions

Definition 24.5.9 (Region)

A region \(\rho\) is a set of objects with a common lifetime: allocation new_ρ(o) puts \(o\) in \(\rho\); free(ρ) frees every object of \(\rho\) at once; individual objects are never freed. A region discipline is safe if no reference to an object of \(\rho\) is used after free(ρ): by construction (the region's lifetime is a syntactic scope and references cannot escape it, Tofte–Talpin's letregion), or by convention (obstacks: the programmer promises).

Algorithm 24.5.10 (Region allocation and lexical region lowering)

  • Input: an expression with region annotations letregion ρ in e and allocations new_ρ.
  • Output: code with a bump allocator per region: a chunk list, a current pointer; region entry allocates the first chunk, region exit frees all chunks.
  • Precondition: every reference to an object of \(\rho\) has a lifetime contained in the letregion (Tofte–Talpin's typing ensures it; a library user asserts it).
  • Postcondition: every allocation costs \(O(1)\) amortized, free(ρ) costs \(O(\text{chunks of } \rho)\), and no freed object is used (Proposition 24.5.14).
  • Invariant: at every point, the live regions form a stack, innermost letregion on top; an object's region is live whenever a reference to it is live.
function Lower(letregion ρ in e):
    ρ.chunks ← [alloc_chunk()]; ρ.cur ← start(ρ.chunks[0])
    result ← Lower(e)
    for c in ρ.chunks: release_chunk(c)                    # obstack_free(&ρ, NULL)
    return result

function new_ρ(size):
    if ρ.cur + size > end(current chunk of ρ): ρ.chunks.append(alloc_chunk(max(size, chunk_size))); ρ.cur ← its start
    o ← ρ.cur; ρ.cur ← ρ.cur + size; return o           # obstack_alloc

100 000 objects, one free: glibc obstacks

Reproduce (gcc 14.2 on Ubuntu 24.04, glibc 2.39):

cat > region.c <<'EOF'
#include <obstack.h>
#include <stdio.h>
#include <stdlib.h>
#define obstack_chunk_alloc malloc
#define obstack_chunk_free free
struct node { int v; struct node *next; };
int main(void) {
  struct obstack region;
  obstack_init(&region);
  struct node *list = NULL;
  for (int i = 0; i < 100000; i++) {          /* 100000 allocations, no frees */
    struct node *n = obstack_alloc(&region, sizeof *n);
    n->v = i; n->next = list; list = n;
  }
  long sum = 0;
  for (struct node *p = list; p; p = p->next) sum += p->v;
  printf("sum %ld, objects live in the region: 100000\n", sum);
  obstack_free(&region, NULL);                /* the whole region, at once */
  printf("region freed with one call\n");
  return 0;
}
EOF
gcc-14 -O2 region.c -o region && ./region

Output (complete):

sum 4999950000, objects live in the region: 100000
region freed with one call

What to notice: the list's 100 000 nodes are never freed individually; obstack_alloc is Algorithm 24.5.10's bump (a pointer increment inside a chunk, a malloc of a new chunk when one fills), and obstack_free(&region, NULL) walks the chunk list once. The safety condition is the programmer's promise that list is dead after the free; Tofte–Talpin's type system would infer the region and check the promise, which is what a Pebble successor with a heap could adopt.

3. Worked example

Running example (used for every technique in this lesson): the allocation sequence

1: a = new       (O1)
2: b = a
3: a = new       (O2)
4: b = nil
5: q = a + 8     (a derived pointer into O2)
6: call f()      (a safepoint)
7: use q
   scope ends

drawn as objects and references after statement 5:

flowchart LR
  a[a] --> O2((O2))
  q[q: derived] -.->|"+8"| O2
  b[b: nil]
  O1((O1: freed at 4))

Reference counting (Swift ARC)

Algorithm 24.5.3, statement by statement (the refcount-trace drill's format):

stmt code operations counts
1 a = new O1 allocated with rc 1 (owned by a) O1=1
2 b = a retain O1 (rc 2) O1=2
3 a = new O2 allocated with rc 1 (owned by a); release O1 (rc 1) O1=1, O2=1
4 b = nil release O1 (rc 0): O1 freed O1=0, O2=1
5–7 q = a + 8, call f(), use q an interior pointer is not a reference in ARC (it is unsafe); no operations O2=1
end scope ends: release a's O2 rc 0: O2 freed O2=0

Two retains-worth of operations (1 retain, 3 releases) for two objects; O1 dies exactly at statement 4, deterministically. What ARCSequenceOpts would remove: nothing here (every operation changes a count that is observed), but if statement 4 came directly after 2, the retain at 2 and the release at 4 form a pair with no intervening decrement and both go.

Tracing GC with stack maps and statepoints

Algorithm 24.5.6 at the safepoint of statement 6: \(\mathrm{live}(6) = \{q\}\) (used at 7); \(a\) is dead after 5 (no later use), \(b\) is nil. \(\mathrm{roots}(6) = \{q\}\), a derived pointer; \(\mathrm{FindBase}(q) = a\). The statepoint's gc-live is \(\{a, q\}\) (the base is added even though \(a\) itself is dead: the collector needs it to relocate \(q\)), and after the call q' = relocate(token, base = a, derived = q); statement 7 uses q'. The stack map records two locations. O1 is unreachable at 6 (no root, no field) and is freed whenever the collector runs, not at statement 4: the difference between "freed at 4" (ARC) and "unreachable from 4" (tracing) is what a deinit observes.

Ownership and borrowing (Rust)

The same sequence as Rust (Box for new, references for the borrow):

stmt Rust Algorithm 24.5.8
1 let a = Box::new(O1); a initialized
2 let b = a; move: a uninitialized, b owns O1
3 let a = Box::new(O2); a new binding a (shadowing), initialized
4 drop(b); b moved into drop: O1 freed here, by the call
5 let q = &a.field; a shared borrow of a, lifetime = until 7
6 f(); fine: f cannot touch a (no reference escaped)
7 use(q); last use: the borrow's lifetime ends
end drop elaboration inserts drop(a): O2 freed; b is not dropped (moved)

Had statement 2 been let b = &a; and 3 a = Box::new(O2);, the assignment at 3 would be E0506 ("cannot assign to a because it is borrowed") if b were used later: the rules reject the reassignment that ARC handles with a release and tracing handles with reachability.

Regions

With one region for the sequence (letregion ρ in ...): statements 1 and 3 bump ρ.cur; statements 2, 4, 5, 7 are pointer copies with no bookkeeping; O1 is not freed at 4 (regions never free individual objects); the scope end frees \(\rho\): O1 and O2 together, in one free(ρ). Total cost: two bumps and one chunk release, against ARC's four count updates and tracing's stack map plus a collection; the price: O1's memory is held from statement 4 to the end.

Try it

./course drill refcount-trace --seed 4 --difficulty hard --solution (Algorithm 24.5.3 with owned and guaranteed calls) and ./course drill gc-roots --seed 4 --difficulty medium --solution (Definition 24.5.5 with derived pointers).

4. Invariants and correctness

Reference counting (Swift ARC)

Theorem 24.5.11 (Naive reference counting is safe and, without cycles, complete)

Under Algorithm 24.5.3, at every point \(\mathrm{rc}(o)\) equals the number of references to \(o\) (variables, fields and counts in flight). Hence an object is freed only when no reference to it exists (safety), and an object that becomes unreachable is freed at the release that removes its last reference, provided no unreachable cycle contains it (completeness).

Proof

Invariant: by induction over the statements. Allocation creates one reference and sets the count to 1. x = y creates one reference (retain, \(+1\)) and destroys one (the old value of x: release, \(-1\)); x = nil destroys one; the owned call creates one (retain, transferred) that the callee destroys (release); the scope end destroys each variable's reference. Field references are handled by the same rule inside free (releasing the fields of a freed object). In every case the count changes by exactly the change in the number of references. Safety: free(o) runs only at \(\mathrm{rc}(o) = 0\), that is, when no reference exists, so no later access can reach \(o\). Completeness: if \(o\) becomes unreachable and lies on no cycle, consider the last reference to it that was destroyed: destroying it released \(o\) (the invariant), and since no reference remained, the count reached 0 and \(o\) was freed. Where it breaks: a cycle \(o_1 \to o_2 \to o_1\) with no outside reference keeps both counts at 1 forever: Swift's weak and unowned references (not counted) are the programmer's tool, and the reason ARC is not complete.

Tracing GC with stack maps and statepoints

Theorem 24.5.12 (Exact stack maps make a moving collector safe)

Let every safepoint \(p\) carry an exact stack map (Definition 24.5.4) and let the collector, when it runs at \(p\), relocate exactly the recorded locations. Then no live reference is dangling after the collection, and every object reachable from the recorded roots is retained.

Proof

No dangling reference: a reference used after \(p\) is live across \(p\) (Definition 14.3.6), hence in \(\mathrm{roots}(p)\), hence recorded (exactness), hence relocated to the object's new address; for a derived pointer, relocation adds the recorded offset to the relocated base, which is recorded with it (Algorithm 24.5.6 adds bases to gc-live). A reference not recorded is dead: no later instruction reads it, so its stale value is never observed. Retention: the collector traces from the recorded roots; an object reachable from a live reference is reachable from a root, and the tracing marks it. Where it breaks: an integer that holds a pointer's bits (ptrtoint), which the map cannot see; LLVM's precondition on address space 1 excludes it, and a conservative collector (Boehm) treats every word that looks like a pointer as a root instead, at the price of never moving objects.

Ownership and borrowing (Rust)

Theorem 24.5.13 (An accepted body is memory safe and frees every value once)

If Algorithm 24.5.8 reports no error, then in every execution of the body: no place is read while uninitialized (in particular after a move), no two live references to overlapping places allow a write, and every initialized owner is dropped exactly once, at the end of its scope on the path taken.

Proof sketch (full proof for a core calculus: [JJKD17, RustBelt])

Reads: the init dataflow is a sound over-approximation of "maybe initialized"; a read of a place not maybe-initialized would have been reported, so every executed read is of an initialized place (the dataflow is a must-analysis on the complement: "definitely uninitialized" reads are errors, and "maybe" reads of scalars are errors too, as in Pebble's definite assignment, spec §12.2). Aliasing: a write through &mut q or to q itself while a borrow of \(q\) (or a prefix) is live would have been reported by the conflict check; liveness of a borrow's region is computed exactly (NLL: a region is the set of points where the reference may be used), so no reported-free program has an executed conflict. Drops: drop elaboration inserts drop(x) on every scope-ending edge where x is definitely initialized, a flag-guarded drop where it is maybe initialized, and nothing where it is definitely moved; the three cases partition the executions, so each executed path drops each initialized owner once. RustBelt [JJKD17] proves memory and thread safety for a formal model of this discipline, including the unsafe code behind Rc and RefCell, in Iris/Coq.

Regions

Proposition 24.5.14 (Lexical regions are safe)

If every reference to an object of region \(\rho\) is dead at the end of letregion ρ in e (Tofte–Talpin's typing, or the programmer's promise), then freeing \(\rho\) there never frees a reachable object, and every object of \(\rho\) is freed exactly once.

Proof

An object of \(\rho\) is reachable only through references to it; by hypothesis none is live after the region's end, so at free(ρ) no reachable object is in \(\rho\). Every object was allocated into exactly one region (the annotation) and regions are freed once, at a unique point (the invariant of Algorithm 24.5.10: regions form a stack, so the letregion that allocated \(\rho\) is the one that frees it). Where it breaks: a reference that escapes the scope (returned, stored in an outer region's object); Tofte–Talpin's effect system rejects it by making the region a type variable that cannot appear in the result type. The known weakness is not safety but space: an object allocated early in a long-lived region is retained until the region dies even if it is dead, which is why MLKit added region resetting and why real systems combine regions with a garbage collector (Cyclone, or the "arena for the request, GC for the rest" pattern).

5. Complexity

\(c\) = reference copies, \(n\) = objects, \(h\) = heap size (bytes), \(\ell\) = live bytes, \(s\) = safepoints, \(r\) = roots per safepoint, \(k\) = chunks of a region.

Technique Per operation Per collection Compiler work Space Justification
Reference counting \(O(1)\) per copy or destroy (an atomic add in Swift); \(O(\text{fields})\) at a free none pair elimination: dataflow over blocks, \(O(n \cdot \text{ops})\) one word per object Algorithm 24.5.3: constant work per statement; frees cascade over the freed object's fields
Tracing GC (mark-sweep / copying) \(O(1)\) per copy (nothing); a barrier per pointer write for generational/concurrent designs \(O(\ell)\) to copy live data, or \(O(h)\) to sweep liveness + base finding per safepoint: \(O(s \cdot r)\) map entries maps: \(O(s \cdot r)\); the heap's headroom Definition 24.5.5: a map entry per live reference per safepoint
Ownership (Rust) \(O(1)\): a drop is a call none borrow checking: dataflow over MIR, \(O(\text{points} \cdot \text{borrows})\), region inference polynomial none at run time Algorithm 24.5.8
Regions \(O(1)\) per allocation; \(O(k)\) per region free none inference: polynomial in the program (Tofte–Talpin), or none for a library retained garbage up to the region's peak Algorithm 24.5.10

Pathological families. Reference counting: a linked list of \(n\) nodes freed by releasing its head cascades \(n\) releases at one point (a pause as long as a collection, on the thread that released); a cycle leaks forever. Tracing: a heap of \(h\) bytes with \(\ell \approx h\) live copies everything at every collection: \(O(h)\) per collection with nothing freed (the collector's headroom is the whole cost model; generational designs bet that \(\ell \ll h\) for the young generation). Ownership: none at run time; at compile time, the borrow checker's polynomial region inference is the cost. Regions: a loop that allocates in a region that outlives it retains every iteration's garbage: \(O(\text{iterations})\) live bytes for \(O(1)\) live objects.

At scale: Swift's ARC traffic is measured in the "ARC and Copying" section of its optimizer's document [Swift-ARCOpt]; the statepoint box's function of 3 instructions needs a 5-location map and a spill/reload pair around the call; the obstack box allocates 100 000 nodes in a few chunks and frees them in one call.

6. Variants and refinements

Reference counting (Swift ARC)

  • Deferred and coalesced counting [DB76]: do not count stack references, only heap ones, and reconcile periodically; trade-off: frees are delayed to the reconciliation, losing determinism.
  • ARC pair elimination and code motion (ARCSequenceOpts, ARCCodeMotion in Swift [Swift-ARCOpt]): move retains down and releases up to make pairs adjacent and delete them; trade-off: a dataflow with alias information (a release may free the object a load reads).
  • Ownership SSA (OSSA) in Swift 5.x+ (CopyPropagation, CanonicalizeOSSALifetime): values carry ownership in SIL so copies are inserted late and minimally; trade-off: a new IR invariant every pass must respect.
  • Non-atomic counting where the object is provably unshared (Swift -assume-single-threaded; Python's per-object counts under the GIL); trade-off: correctness depends on the threading model.
  • Cycle collection (Bacon–Rajan trial deletion, used by CPython's gc): periodically find cycles among candidate objects; trade-off: a tracing pass after all.

Tracing GC with stack maps and statepoints

  • Shadow stacks (llvm.gcroot, ShadowStackGCLowering.cpp) [LLVM-GC]: the compiler spills every root to a linked stack frame the collector walks; trade-off: no stack maps, but every root lives in memory (the box's map lets %v stay in a register).
  • Conservative scanning (Boehm–Demers–Weiser): treat every word as a potential pointer; trade-off: no moving, possible retention of dead objects that look like pointers.
  • Generational and concurrent collectors with write barriers (llvm.gcwrite, or explicit barrier calls emitted by the front end): the map is the same; the barrier is the compiler's other duty; trade-off: a check per pointer store.
  • Safepoint polling on back edges (HotSpot, Go): loops without calls still reach a safepoint quickly; trade-off: a load-and-test per iteration, plus a map per poll.
  • Base-pointer rematerialization (the box's %q.remat): recompute cheap derived pointers from relocated bases instead of recording them; trade-off: a cost model for "cheap".

Ownership and borrowing (Rust)

  • Non-lexical lifetimes (rustc 1.31, 2018): a borrow's lifetime ends at its last use, not at the closing brace; trade-off: liveness-based region inference (rustc_borrowck::region_infer) instead of scopes.
  • Two-phase borrows (v.push(v.len())): a mutable borrow that starts shared and becomes exclusive at activation; trade-off: a special case in the checker.
  • Interior mutability and runtime checks (RefCell, Rc, Arc): the borrow rules enforced at run time with a flag or a count; trade-off: exactly the costs this discipline was avoiding, opt-in.
  • Polonius (the next borrow checker, formulated in Datalog, Lesson 14.8): computes "origins" of loans by inference rules, accepting more programs; trade-off: a new engine.

Regions

  • Region inference [TT94, MLKit]: infer the letregion annotations by an effect type system; trade-off: the analysis and its well-known space leaks in some programs.
  • Cyclone's region types [JMG+02]: explicit region parameters with lexical, dynamic and heap regions, plus a garbage collector for the heap region; trade-off: annotations in the source.
  • Arena libraries (obstacks, BumpPtrAllocator, Rust's typed-arena, bumpalo): no inference, the programmer picks the region; trade-off: safety by convention (C) or by lifetimes (Rust: the arena's &'a references cannot outlive it).
  • Region resetting and dynamic regions: reset a region in a loop when nothing of it is live (MLKit's resetRegions); trade-off: the compiler must prove or the programmer assert deadness.

7. In real compilers

Reference counting (Swift ARC)

Swift

lib/SILOptimizer/ARC/ARCSequenceOpts.cpp — ARCSequenceOpts, processFunctionWithoutLoopSupport, processFunctionWithLoopSupport (Swift 6.1) [Swift-ARCSeqOpts]: the pair-elimination dataflow, run twice (once freezing post-dominating releases); lib/SILOptimizer/Transforms/ARCCodeMotion.cpp; include/swift/SIL/SILArgumentConvention.h — Direct_Owned, Direct_Guaranteed (Definition 24.5.2); lib/SILOptimizer/Transforms/CopyPropagation.cpp — CanonicalizeOSSALifetime (the OSSA variant). No swiftc in this container: the pointers were checked against the tagged sources, and the box quotes them.

  • Objective-C / Clang llvm/lib/Transforms/ObjCARC/ObjCARCOpts.cpp — ObjCARCOpt::OptimizeSequences (LLVM 23.1.2): LLVM's own ARC optimizer for objc_retain/objc_release calls, the same pairing over LLVM IR.
  • CPython Include/internal/pycore_object.h (Py_INCREF/Py_DECREF) and Modules/gcmodule.c: naive counting plus a cycle collector.

Find where LLVM does it. In llvm/lib/Transforms/ObjCARC/ObjCARCOpts.cpp, find ObjCARCOpt::OptimizeSequences. Question: which two directions of dataflow does it combine to pair a retain with a release, and what is the name of the state each pointer carries ("sequence")?

Tracing GC with stack maps and statepoints

LLVM

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp — computeLiveInValues, findLiveSetAtInst, findBasePointers, relocationViaAlloca (LLVM 23.1.2) [LLVM-RS4GC]: Algorithm 24.5.6; llvm/lib/CodeGen/SelectionDAG/StatepointLowering.cpp — SelectionDAGBuilder::LowerStatepoint, lowerStatepointMetaArgs (spills the gc-live operands, as the box's movq %rdi, 8(%rsp)); llvm/lib/CodeGen/StackMaps.cpp — StackMaps::recordStatepoint, serializeToStackMapSection (the .llvm_stackmaps format the box dumps) [LLVM-StackMaps]. The textbook records roots; LLVM records (base, derived) pairs, because a moving collector cannot update an interior pointer alone.

  • HotSpot src/hotspot/share/opto/output.cpp — PhaseOutput::Process_OopMap_Node (OpenJDK 21): oop maps at safepoints, with derived-pointer tables (DerivedPointerTable).
  • V8 src/compiler/backend/code-generator.cc — CodeGenerator::RecordSafepoint (V8 13.6): tagged-slot bitmaps per call.
  • Wasmtime / Cranelift cranelift/codegen/src/machinst/buffer.rs — user_stack_maps (Wasmtime 34): (offset, span, stack_map) triples per safepoint for the host's collector (crates/wasmtime/src/runtime/vm/gc.rs — GcStore).

Find where LLVM does it. In llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp, find findBasePointers (the overload taking a live set). Question: what does it record for a live value that is its own base, and how does the base of a phi of pointers get represented?

Ownership and borrowing (Rust)

rustc

compiler/rustc_borrowck/src/lib.rs — MirBorrowckCtxt (the checker's state: do_mir_borrowck drives it), compiler/rustc_borrowck/src/region_infer/mod.rs — RegionInferenceContext (NLL's region solving), compiler/rustc_mir_transform/src/elaborate_drops.rs — ElaborateDrops::run_pass (rustc 1.94) [Rust-Borrowck]. The textbook checks lexical scopes; rustc computes each borrow's region from liveness and reports the "later used here" note from it (the box).

  • Cyclone [JMG+02]: unique pointers and regions in a C dialect, the direct ancestor.
  • Swift's ownership manifesto and ~Copyable types (Swift 5.9+): move-only types with the same static discipline, on top of ARC [Swift-Ownership].

Find where LLVM does it. LLVM has no borrow checker; the question is about rustc: in compiler/rustc_mir_transform/src/elaborate_drops.rs, what does ElaborateDrops::run_pass compute before it decides whether a drop needs a flag? (Quiz find-elaborate-drops.)

Regions

glibc and LLVM

glibc malloc/obstack.c — _obstack_newchunk, obstack_free (glibc 2.39): the chunk list of Algorithm 24.5.10; LLVM llvm/include/llvm/Support/Allocator.h — BumpPtrAllocatorImpl::Allocate, Reset (LLVM 23.1.2) [LLVM-Allocator]: the region every LLVM Context, ASTContext and pebble::ASTContext (Lesson 10.1) is built on, freed when the context dies.

  • MLKit (src/Compiler/Regions/): Tofte–Talpin region inference in production, with the space-leak experience that motivated region resetting.
  • Apache APR apr_pools.c: per-request pools in httpd, the "region per request" pattern.

Find where LLVM does it. In llvm/include/llvm/Support/Allocator.h, find BumpPtrAllocatorImpl::Allocate. Question: what happens when the requested size does not fit in the current slab, and what does Reset do with the slabs?

8. Comparison

Technique Power / precision Speed Output / error quality Implementation effort Typical use
Reference counting (ARC) frees at the last release (Theorem 24.5.11); cycles leak a retain/release per reference copy; ARC removes pairs deterministic destruction; no pauses moderate (compiler) + low (runtime) Swift, Objective-C, Python's first line of defense
Tracing GC with stack maps frees everything unreachable; needs exact roots (Theorem 24.5.12) zero cost on copies; pauses or barriers moving collectors need relocation of every live pointer (the stack-map box) high: runtime + compiler support Java, Go, V8, OCaml, Wasm hosts
Ownership (Rust) no run-time work at all; rejects some correct programs compile-time only errors at compile time (the rustc box) high in the type system; drop elaboration in the compiler Rust, Cyclone's unique pointers
Regions frees a whole region in \(O(1)\) (Proposition 24.5.14) bump allocation; no per-object free long-lived regions retain garbage low (a library) to high (inference) glibc obstacks, Apache pools, arenas in compilers, Cyclone, MLKit

Choose reference counting when destruction must be deterministic and the language can forbid or manage cycles; choose tracing when the heap is large and cyclic and the runtime can afford a collector, and give the compiler the safepoint discipline; choose ownership when the language can afford to reject programs and wants zero runtime; choose regions when lifetimes follow scopes (a request, a compilation) and peak memory is acceptable. A Pebble with a heap would most naturally start with regions (its values already have scope lifetimes) and add reference counting for what escapes.

Measured: the running example's counts (1 retain, 3 releases, two frees at 4 and at the end) against 2 map locations at one safepoint, 2 drops, and 1 region free (§3).

9. Assessment

  • Quiz: rc-trace-freed (mapping), rc-cycle (single), gc-roots-at-call (set), stackmap-pairs (single), borrow-error-kind (single), nll-last-use (single), find-elaborate-drops (text), region-free-order (sequence), region-space-leak (single). Tags refcount, tracing-gc, ownership, regions.
  • Drills: ./course drill refcount-trace (Algorithm 24.5.3; hard adds owned/guaranteed calls), ./course drill gc-roots (Definition 24.5.5 and base pointers). Ownership and regions have no drill: a borrow-checking drill needs a MIR-level instance language that the course does not define, and the quiz's borrow-error-kind, nll-last-use and region-free-order ask the mechanical parts (which rule fires, where the drops go, which region frees first) on concrete snippets instead.
  • Flashcards: tags refcount, tracing-gc, ownership, regions.
  • Exercises: none: Pebble has no heap. The stack-map format is exercised through ★ E3's cousin, the deoptimization stack map of Lesson 24.2.

Pitfall

"A tracing collector needs no compiler support." A conservative one needs none and cannot move objects; a precise one needs the stack map at every safepoint, and a moving one needs the (base, derived) pairs and the guarantee that no pointer hides in an integer. The compiler's part of a precise moving collector (Algorithm 24.5.6 plus the back end's map) is as large as the collector's.

References

See the chapter references.