My 100-line garbage collector in C had a use-after-free

Before v0.1.0, a Sprout loop could leak gigabytes. About a hundred lines of C fixed that.

Until then my interpreter freed nothing, which was fine for short scripts and a blocker for a REPL session or a long loop. Now a mark-and-sweep collector reclaims memory, and in CI it runs before every statement under AddressSanitizer. It also had a use-after-free in three places that CI never touched, which matters because I’d rather leak than crash a beginner’s program.

Mark-and-sweep, before any C

When a script runs make xs = [1, 2, 3] and later sets xs to something else, how does the C program underneath know that list’s memory is free to reuse? A program can only reach a value through pointers that start at something it already holds: a global, a local, an argument. Those are the roots. Mark follows every pointer from every root and flags what it reaches, then sweep walks every allocated object and frees the unflagged ones.

roots ──► A ──► B          C ◄──► D

A and B survive. C and D point at each other, but no root reaches them, so both go. Reference counting would leak that pair, and Sprout builds such cycles easily: a lambda’s TaskDef points at the environment it captured, which can hold the same lambda.

One allocator, one list of every object

Every collectible object comes from gc_alloc, which prepends a small header and pushes it onto one intrusive linked list. The next pointer lives in the header itself, so tracking costs no extra allocation.

typedef enum { GC_LIST, GC_MAP, GC_ENV, GC_TASK, GC_STR } GCKind;
typedef struct GCObj { struct GCObj *next; GCKind kind; int mark; } GCObj;
static GCObj *gc_all = NULL;                        /* every live collectible allocation */
static size_t gc_bytes = 0, gc_threshold = 4u << 20;   /* collect once ~4 MB has been allocated since the last GC */
...
static void *gc_alloc(GCKind kind, size_t size) {   /* a zeroed object + header, tracked for sweeping */
  GCObj *h = (GCObj *)calloc(1, sizeof(GCObj) + size);
  if (!h) fail(0, "ran out of memory.");
  h->kind = kind; h->next = gc_all; gc_all = h;
  gc_bytes += size;
  return (void *)(h + 1);
}
#define GC_HDR(p) ((GCObj *)(p) - 1)

The caller gets h + 1 and never sees the header. Lists, maps, environments, lambdas and strings all come through here, including the list behind xs. The arrays hanging off them needed an owner on paper:

Finding roots on the C stack

Some roots can be listed exactly: the global, file and module environments, the environments named tasks captured, the pending return value and the active fail value. The rest sit in C locals mid-evaluation, such as a builtin’s Value a[16] or a match subject, each a struct carrying raw pointers.

A precise shadow stack would push every temporary onto a side stack. Miss one push and you get a use-after-free, and longjmp error unwinding skips the pops. A conservative scan treats every aligned word on the C stack and in registers that equals a known object’s address as a root. No evaluator changes, and longjmp can’t break it, so I chose the scan:

static void gc_collect(void) {
  jmp_buf regs; setjmp(regs);               /* spill all callee-saved registers so we can scan them (never longjmp'd) */
  char marker; char *sp = ▮          /* current stack top (lowest live address) */
  ...
  gc_push(global_env); gc_push(cur_file_env);
  for (int i = 0; i < g_nmods; i++) gc_push(g_mods[i].env);
  for (int i = 0; i < ntasks; i++) { gc_push(tasks[i].home); gc_push(tasks[i].file_env); }
  gc_push_value(return_value);
  if (g_have_fail_override) gc_push_value(g_fail_override);
  gc_scan_range((char *)&regs, (char *)&regs + sizeof regs);   /* the spilled registers */
  char *lo = sp, *hi = gc_stack_bottom;
  if (lo > hi) { char *t = lo; lo = hi; hi = t; }
  while ((size_t)lo % sizeof(void *)) lo++;
  gc_scan_range(lo, hi);                                       /* the whole live C stack */

main records the bottom in its first line, the local marker is the top, and the swap makes stack direction irrelevant. A compiler can keep the only copy of a pointer in a callee-saved register, one a function must restore before returning, and setjmp into a local jmp_buf copies those registers out where the scan can read them. It’s the classic portable trick, not a guarantee.

Every object’s address also goes into a hash set, and gc_lookup accepts a stack word only if it equals one exactly. A stray integer can still pin one object and everything reachable from it, a whole scope chain if it hits an environment.

Marking with a worklist, sweeping by unlinking

A recursive mark can overflow the C stack on a deeply nested list. So gc_push skips unknown or already-marked pointers, and otherwise sets the mark bit and queues the object. The same bit stops cycles:

static void gc_push(void *p) {                 /* discover an object: mark it + queue it to scan */
  GCObj *h = gc_lookup(p);
  if (!h || h->mark) return;
  h->mark = 1;
  ...
  gc_work[gc_workn++] = h;
}

gc_drain pops the queue and pushes each object’s children, and strings are leaves. The sweep walks gc_all with a pointer-to-pointer, GCObj **pp = &gc_all, so unlinking the head needs no special case. Survivors get their mark cleared, and the dead free their owned arrays, then header and object in one free.

Collecting only between statements

A safe point is a place where a collection is allowed to run. Sprout has exactly one. It’s the top of exec, before every statement:

static void exec(Stmt *s, Env *env) {
  ...
#ifndef __EMSCRIPTEN__   /* the conservative stack scan can't see roots held in WASM locals; leak instead (playground programs are short, each run is a fresh instance) */
  if (gc_stack_bottom && (gc_bytes > gc_threshold || gc_stress)) gc_collect();
#endif

It fires after about 4 MB of tracked allocation, or before every statement in stress mode. Loop bodies run through exec, so long loops get collected. The browser build skips this and leaks.

In my v0.1.0 benchmark notes (Windows, wall-clock, including startup), the collector moved fib from about 1.3 s to 2.0 s and loop from 0.44 s to 0.8 s. The trigger also undercounts: gc_bytes sees sizeof(SList) and misses the items array that list_push grows with realloc.

How CI hunts for a missing root

If sort_by lost a key, the crash wouldn’t come in sort_by. It would come later, in whichever statement next read that memory. Setting SPROUT_GC_STRESS makes exec collect before every statement, its only collection site. The CI asan job builds with -fsanitize=address and runs the suite and examples twice, the second time like this:

      - name: Run the suite under GC stress + ASan
        env:
          ASAN_OPTIONS: detect_leaks=0:detect_stack_use_after_return=0:halt_on_error=1:abort_on_error=1
          SPROUT_GC_STRESS: "1"
        run: bash src/tests/run.sh

On every path the suite exercises, a missing root becomes a use-after-free that ASan halts on. No sort_by test sorted by freshly built strings, though. ASan can move locals onto a fake stack to catch stack-use-after-return, out of the scan’s reach, so CI turns that off and keeps heap use-after-free detection.

src/tests/gc.sprout tries to break the collector with a 200,000-turn allocation loop, a list nested 5,000 deep and a map that contains itself:

make m = {n: 42}
set m["self"] = m
repeat 20000 times:
    make spam = {a: 1, b: 2, c: 3}
check("cycle is collected-safe + still valid", m["self"]["self"]["n"], 42)

Each turn’s spam map becomes garbage while m has to stay intact. gc_strings.sprout does the same for strings.

Three places the scan can’t see

My README says the collector “can never free a live value”, and as written that’s wrong. The scan protects objects whose address sits on the C stack, in a register or in an explicit root, plus everything reachable from those. A pointer held only in untraced memory, like a plain malloc’d array, is invisible.

Sprout has three places that store a fresh result in such an array and then run more Sprout code. Method calls and super calls do it with their argument arrays. sort_by does it with one key per item:

      Value *keys = (Value *)malloc((size_t)l->n * sizeof(Value));   /* each item's sort key, computed once */
      for (int i = 0; i < l->n; i++) keys[i] = call_task_v(a[1].task, &l->items[i], 1, call->line);

Each call runs the task’s body through exec, so every turn of that loop passes a safe point, and neither the keys array nor the caller’s return_value covers the earlier keys.

So the code doesn’t guarantee these temporaries survive, and they don’t. I built Sprout in Docker with CI’s ASan line, set SPROUT_GC_STRESS=1, and ran show sort_by(["b","a","c"], task(w): upper(w)):

ERROR: AddressSanitizer: heap-use-after-free
    #1 0x000000431e22 in call_builtin /w/src/sprout.c:2335
freed by thread T0 here:
    #1 0x000000408a36 in gc_collect /w/src/sprout.c:1499

A collection ran while the next key was being computed, freed a key string, and strcmp read it afterwards. Seven-argument method and super calls failed the same way; three-argument ones survived on stale stack copies, by luck. Without stress mode the failure is quieter and worse. On the normal -O2 build, sorting 60,000 strings by upper(w) + "-padding-padding" printed 60000 no instead of 60000 yes, with no error. The existing sort_by tests sort by numbers, which aren’t heap objects in Sprout, or by strings a rooted list already holds, so CI stayed green the whole time.

The fix pattern was already in the same file. A named-task call binds each argument into the new frame’s environment as soon as it’s evaluated, and the frame is a local, so the scan reaches the arguments through it. The fix (6ff6426, merged into main in 7b763cb) gives method and super calls the same binding and keeps sort_by’s keys in a GC list instead of a malloc’d array. It also closed a heap-buffer-overflow in the same lines, where a key task that grew the list being sorted wrote past the end of the keys array.

The tests went in first (beca805) and failed on the old main. Now the one-liner prints [a, b, c] under ASan and stress mode, the 60,000-string sort prints 60000 yes, and the full suite passes in all three CI modes. A green CI run proves only the paths it runs, and this one stayed green with a broken path next to it.