# A Simplified Model of Fil-C

Peter Cawley's walkthrough of [[fil-c|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*`:

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

Where `AllocationRecord` holds the bounds:

```c
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

```c
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:

```c
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 `memmove`s — 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