A Simplified Model of Fil-C

Peter Cawley's walkthrough of Fil-C, a memory-safe implementation of C/C++. The real Fil-C rewrites LLVM IR; Cawley's simplified model is presented as a source-to-source C rewrite, which is easier to reason about first and a small mental step from the production version.

The core mechanism: shadow capabilities

Every local variable of pointer type gets a companion variable of type AllocationRecord*:

T1* p1;               T1* p1; AllocationRecord* p1ar = NULL;

Where AllocationRecord holds the bounds:

struct AllocationRecord {
  char* visible_bytes;
  char* invisible_bytes;
  size_t length;
};

Trivial pointer ops move the companion along with the pointer: p1 = p2 becomes p1 = p2, p1ar = p2ar. Pointer arithmetic keeps the same companion (p1 = p2 + 10 keeps p1ar = p2ar). Casts from integer null out the companion.

Function calls pass the companion alongside each pointer argument, and specific standard library functions are replaced by Fil-C versions: malloc becomes filc_malloc, free becomes filc_free, and so on.

filc_malloc allocates three things

void* filc_malloc(size_t length) {
  AllocationRecord* ar = malloc(sizeof(AllocationRecord));
  ar->visible_bytes  = malloc(length);
  ar->invisible_bytes = calloc(length, 1);
  ar->length = length;
  return {ar->visible_bytes, ar};
}

Three allocations per malloc call: the record, the user-visible bytes, and a parallel "invisible" array the same size as the user allocation.

Bounds checks on deref

Every dereference expands to the obvious checks:

assert(p1ar != NULL);
uint64_t i = (char*)p1 - p1ar->visible_bytes;
assert(i < p1ar->length);
assert((p1ar->length - i) >= sizeof(*p1));
x = *p1;

Shadow memory for heap pointers

The clever part: when pointers live in heap memory, the compiler can't just add a companion local. Instead, invisible_bytes acts as a parallel array indexed identically to visible_bytes, but with element type AllocationRecord*. If a pointer sits at visible_bytes + i, its capability sits at invisible_bytes + i. i must be aligned to sizeof(AllocationRecord*) for sane access.

Loading or storing a pointer through another pointer therefore performs two loads/stores: one of the value, one of the companion. This is the reason memmove of eight aligned bytes behaves differently from eight separate 1-byte memmoves — the aligned version also moves shadow memory; the unaligned one doesn't.

The GC

filc_free frees visible_bytes and invisible_bytes but not the AllocationRecord itself. That gets handled by a garbage collector that traces through AllocationRecords and frees unreachable ones. Production Fil-C uses FUGC, a parallel concurrent incremental collector; the simplified model can use stop-the-world.

The GC does two extra things:

1. On freeing an unreachable AllocationRecord, call filc_free on it. So forgetting free is no longer a leak — the GC cleans it up. Explicit free just makes the release happen sooner.
2. If an AllocationRecord has length 0, pointers to it get rewritten to point at a single canonical length-0 record. This lets use-after-free resolve safely.

Once you have a GC, it becomes tempting to use more of it. Fil-C does: if a local variable has its address taken and the compiler can't prove the address doesn't escape, the local is promoted to heap allocation. No matching free needed — the GC picks it up.

Production complications

The simplified model skips four pieces of complexity in real Fil-C:

• Threads. filc_free can't free immediately — another thread might still be reading. Atomic pointer operations need extra magic since the default lowering splits one load into two (value + companion), breaking atomicity.
• Function pointers. An extra AllocationRecord field marks executable-code targets. Calls check p1 == p1ar->visible_bytes and the flag. To prevent type-confusion attacks, the calling ABI is uniform: every function takes a single AllocationRecord for a packed-struct argument frame.
• Memory optimization. Tempting to allocate invisible_bytes lazily, colocate record and visible bytes into one allocation, reuse the underlying allocator's metadata slot.
• Performance optimization. Bounds-check elimination and similar tricks to reduce the overhead.

When to use it

Cawley's four use cases:

1. Large pre-existing C/C++ code that's probably memory-safe but unproven, where you'll eat the GC + perf cost in exchange for safety, perhaps as a bridge to a Rust/Go/Java rewrite.
2. A sanitizer — like ASan, but with stronger guarantees, for bug finding.
3. Safe compile-time evaluation in languages where compile-time and runtime share the same language (Zig is the cited example) even if runtime stays unsafe.
4. A concrete, tractable instance of pointer-provenance. The companion AllocationRecord* is the provenance — so Fil-C demonstrates why compilers can't generally rewrite if (p1 == p2) { f(p1); } to if (p1 == p2) { f(p2); }: equal bit patterns can carry different provenances, and Fil-C would propagate different capabilities to f.

Related

• fil-c — the project itself
• pointer-provenance — the memory-model concept Fil-C makes concrete
• abi-stability — Fil-C's function-pointer defense requires a uniform ABI, which is a different angle on ABI design
• meta-tracing — another "rewrite the program to gain a property" technique, for perf rather than safety
• raii / stroustrup-memory-leaks — the social-contract version of the same goal: Stroustrup says "write code without leaks"; Fil-C enforces it mechanically when you can't trust the discipline