Inside the Flow-Wing garbage collector

void  fw_gc_init(void);
void *fw_gc_alloc(size_t size, const FWTypeDescriptor *desc);
void *fw_gc_alloc_array(const FWTypeDescriptor *array_desc, size_t n);
void  fw_gc_collect(void);
void  fw_gc_add_root(void **slot);      /* globals */
void  fw_gc_remove_root(void **slot);
void  fw_gc_register_finalizer(void *obj, void (*fn)(void *));
void  fw_gc_set_stress(int on);         /* FW_GC_STRESS=1 */
FWGCStats fw_gc_stats(void);

You never call these from Flow-Wing. The compiler emits them for you — every string concatenation, object literal and array is an fw_gc_alloc.

typedef struct FWObjHeader {
  struct FWObjHeader *next;            /* threads ALL live objects, for sweep */
  uintptr_t           desc_and_flags;  /* descriptor pointer | pin | mark */
  size_t              size;            /* payload bytes, header excluded */
} FWObjHeader;

fw_payload(h) = (char*)h + 24      /* what your program receives */
fw_header(p)  = (char*)p - 24      /* how the GC gets back */

A FWTypeDescriptor is 8-byte aligned, so the low three bits of any pointer to one are always zero. Free real estate — the mark bit lives there instead of in its own word.

Masking with ~0x7 recovers the descriptor; the bits never corrupt it. That is the whole trick — no extra byte per object.

Some objects keep their GC pointers where no static layout can describe them — a vec or map holds elements in a C++ container on the malloc heap. Those types provide a callback:

typedef void (*fw_trace_fn)(void *obj, void (*mark)(void *ptr));

The collector calls trace(obj, mark) while marking and the hook calls mark(p) once per contained pointer. mark skips non-heap and already-marked pointers for you, so a native container can hold any Flow-Wing value with zero copies.

typedef struct FWFrame {
  struct FWFrame *prev;   /* caller's frame  */
  uint32_t        n;      /* how many roots  */
  void          **roots;  /* n slot ADDRESSES, each a void**  */
} FWFrame;

extern FWFrame *fw_gc_shadow_top;   /* the code running right now */

Note the double indirection. roots[i] is a void** — the address of a local variable. The collector reads *roots[i] at collection time, so it always sees the variable's current value, even if the function reassigned it after pushing the frame.

push(frame with s = "a")
s = "b"          ← GC still sees "a";
                    "b" is collected

push(frame with &s)
s = "b"          ← GC reads *&s = "b"
                    always current

fw_gc_mark_from_roots()
   │
   ├─ 1. globals            g_global_roots[]        (fw_gc_add_root)
   ├─ 2. running code       fw_gc_shadow_top chain
   ├─ 3. aux scanner         s_aux_scanner()        ← the scheduler
   │        ├─ every PARKED task's own shadow chain
   │        └─ every QUEUED task's argument block
   └─ 4. drain the work-list until empty

Step 3 is the bridge to spawn. A suspended task's locals live on its stack, which nothing else points at; a queued task's arguments are referenced by nobody at all. Without that hook both get swept. See the concurrency page.

• Candidate pointers are resolved, not trusted. A str field may point at a static literal that the GC never allocated. fw_gc_resolve_object(p) returns the heap object containing p, or NULL — so junk and non-heap pointers are skipped instead of having a garbage header read.
• An index makes that cheap. A linear search of the object list would make marking O(objects²). Since nothing is allocated during a collection, the collector snapshots every live payload range into a sorted array, binary-searches it, and frees it before the sweep — O(log N) per lookup.

fw_gc_build_object_index();   /* live set is stable -> snapshot + sort */
fw_gc_mark_from_roots();      /* binary search per candidate pointer   */
fw_gc_free_object_index();    /* drop it before anything is freed      */
fw_gc_sweep();

Recursion in scan_fields is bounded by descriptor nesting depth (an array of tagged values), never by the object graph — so a million-node linked list cannot overflow the C stack.

fw_gc_run_finalizer_if_any(payload);   /* e.g. close a file handle    */
g_stats.live_objects--;
g_stats.live_bytes -= h->size;
g_stats.total_frees++;
memset(h, 0xDD, 24 + h->size);         /* poison */
free(h);

0xDD poisoning is deliberate. A use-after-free then reads an obvious pattern rather than plausible-looking stale data, so the bug surfaces immediately instead of three functions later. A survivor simply has its mark bit cleared, ready for the next cycle.

void *fw_gc_alloc(size_t size, const FWTypeDescriptor *desc) {
  if (g_stress || g_stats.live_bytes + size > g_threshold) {
    fw_gc_collect();
  }
  ...
}

Two conditions: stress mode, or the heap crossing a threshold.

size_t grown = g_stats.live_bytes * 2;
size_t floor = 1 MiB;
g_threshold  = grown > floor ? grown : floor;

FW_GC_STRESS=1 ./your_program

Collects on every single allocation. Any object you failed to root dies immediately rather than one run in a hundred. It turns a heisenbug into a deterministic failure.

Every fixture under tests/fixtures/LatestTests/GcTests/ runs under it automatically — no flag needed. Elsewhere, a fixture opts in with a /; FW_GC_STRESS header line.

Switching tasks saves and restores fw_gc_shadow_top around the stack swap, so the "currently running" chain always belongs to whoever is actually on the CPU.

var items: int[3] = [1, 2, 3]
var name: str = "Flow" + "-Wing"     /; allocates
var p: Point = { x: 1, y: 2 }        /; allocates

No free, no ownership, no lifetimes. When nothing can reach a value, it goes.

FW_GC_STRESS=1 ./myprogram

If the output is identical, every value your program holds is properly rooted. If it changes, something was reachable only by luck. This is the single most useful thing on this page.

typedef struct {
  size_t live_objects;   /* on the heap right now        */
  size_t live_bytes;     /* payload bytes right now      */
  size_t total_allocs;   /* cumulative since init        */
  size_t total_frees;    /* cumulative since init        */
} FWGCStats;

total_allocs - total_frees == live_objects always holds. If it ever does not, something freed an object without going through the sweep.