reveal.js

# The Edge of Safe Rust
(Misusing Rust features to provide provable memory safety and tracing garbage
collection for pointer soup)

— Catherine West

www.kyju.org/blog/tokioconf-2026

---

## What this talk is about
- I work on indie video games, also language interpreters.
- This talk is about what I actually work on.
- Sort of on topic!

notes:

Kong does networking, and I helped them make an isolated VM, so this is must be
on topic?

---

## Background

- I became obsessed with making GC work in Rust
- With Totally *Zero Cost* Gc pointers
- Usable from completely safe Rust
- Made gc-arena!
- Now used by...

notes:

Task sort of failed successfully

---

## I live in a strange place

What the hell is...

```rust
// What the hell is `ctx`?
let methods = Gc::new(&ctx, DsGridMethods);
// What the hell is `unsize!`? Why does it have custom syntax?
let methods_ptr = gc_arena::unsize!(methods => dyn vm::UserDataMethods<'gc>);
```

or this...

```rust
// What the hell is the `Rootable![_]` macro, it evaluates to a **type**? What
// the hell does '_ in a macro mean?
let methods = ctx.singleton::<Rootable![DsGridMethodsSingleton<'_>]>().0;
let ud = vm::UserData::new::<Rootable![DsGrid<'_>]>(&ctx, self);
ud.set_methods(&ctx, Some(methods));
```

or this...

```rust
// Okay downcasting I understand, `downcast_write` must be like...
// `downcast_mut`, returning a `&mut T`? No? It's something else entirely that
// is impenetrable GC jargon? `&'gc barrier::Write<T>`?
let ds_list = DsList::downcast_write(&ctx, ud).unwrap();
// Again, what the hell is a barrier? Why does this have to be a macro? What
// syntax is this? WHY??
let inner = barrier::field!(ds_list, DsList, inner);
// Okay this part I basically understand, but what the hell is *unlocking*?
let mut vec = inner.unlock().borrow_mut();
```

notes:

This is the kind of code that gets you *fired*... or invited to TokioConf.

---

## *Introducing people to my personal hell to make myself feel better*

(An introduction to safe cyclic pointers and garbage collection in Rust)

— Catherine West

---

### Pointers in Rust without clear ownership is Very Hard
- Rust is really bad at dealing with cyclic pointers
- We're gonna talk about how to deal with this fact
- You can divide programming languages into three camps:
  1) Ownership and Drop - Safe Rust, C++ in theory
  2) "Reachability" - Lua, Python, Javascript, Java, Scheme...
  3) "Just Trust Me Bro" - C, C++ in practice, Unsafe Rust

---

### ***Ownership and Drop are also a form of garbage collection.***

### <span class="blinking-text">controversial statement alert</span>

- Rust picked a GC based on ownership and predictable drop
- This is the right tool for 99% of Rust
- Cyclic pointers have no clear ownership
- So Rust can't garbage collect them

---

### Implementing "reachability" langauges

- Rust's meme is linked lists being hard
- Here's a linked list in Lua

```Lua
local a = {}
local b = {}
local c = {}

-- You can just like... set the `next` pointer? And that's it?
a.next = b
b.next = c
c.next = a

-- Now our nodes look like this. Easy!
-- 
-- [a] -> [b] -> [c]
--  ^             |
--  |             |
--  +-------------+
```

notes:

What is the representation for this in memory if Rust is being used to implement
Lua?

---

## Rust is *really* good at Vec

(The most common way to handle this)

---

If you have a graph and you need to encode it in Rust, you'll eventually end
up here.

```rust
// An allocator for slots in a vec.
struct SlotAlloc<T> {
    slots: Vec<T>,
}

impl<T> SlotAlloc<T> {
    // Allocate a new slot, push it onto our `slots` vec, return its index!
    // Picture of simplicity.
    fn alloc(&mut self, value: T) -> usize { ... }

// Get a value by an allocated index.
    fn get(&self, index: usize) -> &T { ... }
    fn get_mut(&mut self, index: usize) -> &mut T { ... }
}
```

Please think of this like a "pointer" (usize) with a "context" (SlotAlloc)

---

### The good parts

- Nothing beats usize for simplicity!
- Serialize it!
- Shrink the address space (u32, u16)
- usize: Copy + Send + Sync

---

### The Bad Parts

Most anything works great until you want to free something

```rust
// An allocator for slots in a vec.
struct SlotAlloc<T> {
    slots: Vec<Option<T>>,
    free_list: Vec<usize>,
}

impl<T> SlotAlloc<T> {
    // Allocate a new value. If we have any known free indexes in `free_list`,
    // use them. Otherwise, push a new value, either way, return the index of
    // the assigned slot.
    fn alloc(&mut self, value: T) -> usize { ... }

// Set this slot to `None` and push the slot onto `free_list`.
    fn free(&mut self, index: usize);

// Get a value by an allocated index. If we are given an `index` that has
    // been freed, these will panic!
    fn get(&self, index: usize) -> &T { ... }
    fn get_mut(&mut self, index: usize) -> &mut T { ... }
}
```

Now you have use after free!

---

### A worse kind of UAF: The ABA problem

Add Generational Indexing!

```rust
// An allocator for slots in a vec.
struct SlotAlloc<T> {
    slots: Vec<Slot<T>>,
    free_list: Vec<usize>,
}

// A slot within a `SlotAlloc`.
struct Slot<T> {
    // The `generation` is incremented every time a slot is freed.
    generation: u32,
    value: Option<T>,
}

// An abstract "index" into a `SlotAlloc`.
#[derive(Copy, Clone)]
struct Index {
    // The index into the `slots` vec.
    slot: u32,
    // The generation at the time of allocation.
    generation: u32,
}
```
---

```rust
impl<T> SlotAlloc<T> {
    // Allocate a new value. If we have a free slot, increment the generation.
    fn alloc(&mut self, value: T) -> Index { ... }

// Set the slot for this index to `None` and push the slot onto `free_list`.
    //
    // Panics if `index.generation` is not correct.
    fn free(&mut self, index: Index) { ... }

// Get a value by an allocated index.
    //
    // Panics if freed or `index.generation` is not correct.
    fn get(&self, index: Index) -> &T { ... }
    fn get_mut(&mut self, index: Index) -> &mut T { ... }
}
```

This basically works, no more ABA!

We've built a pointer that will panic on misuse (UAF and ABA)! Cool!

<pre><code data-trim style="text-align: center;">
[---------------------generation (32 bits)---------------------]
[------------------------slot (32 bits)------------------------]
</code></pre>

---

<img src="cheri-shitpost.png" title="Diagram of CHERI pointer bits" width="80%">
<div style="width=100%; text-align: center;">
    <em>Pointer problems require Pointer solutions</em>
</div>

---

## Rust is really bad at circular references

(A misadventure in linked lists)

---

Let's make the Lua linked list in Rust with regular lifetimes

```rust
// A simple example of a node in a linked list.
struct Node<'a> {
    value: String,
    next: Cell<Option<&'a Node<'a>>>,
}

impl<'a> Node<'a> {
    fn new(value: String) -> Node<'a> {
        Node {
            next: Cell::new(None),
            value,
        }
    }

fn next(&self) -> Option<&'a Node<'a>> {
        self.next.get()
    }

fn set_next(&self, node: Option<&'a Node<'a>>) {
        self.next.set(node)
    }
}
```

---

Use it with *bumpalo*!

```rust
// A bump allocator from the `bumpalo` crate.
let bump = bumpalo::Bump::new();

// Each returned node here is a reference, and that reference has the lifetime
// of the `bump` allocator itself.
let a = bump.alloc(Node::new("1".to_owned()));
let b = bump.alloc(Node::new("2".to_owned()));
let c = bump.alloc(Node::new("3".to_owned()));

// We can thus set the ``next` node pointers to make make the 'a lifetime
// in each of the nodes equal to the lifetime of the references returned by
// `Bump::alloc`.
//
// Since all of the lifetimes of references returned by `Bump::alloc` are the
// same, all of the 'a lifetimes in each `Node` instance become the same.
//
// This *has* to be true, because every node references every other one, so they
// *must* live for exactly the same time.
a.set_next(Some(b));
b.set_next(Some(c));
c.set_next(Some(a));
```

---

## What's the big deal then?

- You can't *move* bump along with a, b, c
- You can solve this with self-borrowing (self_cell crate)

Nothing can soundly be dropped!
```rust
impl<'a> Drop for Node<'a> {
    fn drop(&mut self) {
        if let Some(next) = self.next() {
            println!("next value {:?}", next.value);
        }
    }
}
```

Bumpalo doesn't drop! same limitation as Box::leak
```rust
let a = Box::leak(Node::new("1".to_owned()));
let b = Box::leak(Node::new("2".to_owned()));
let c = Box::leak(Node::new("3".to_owned()));
```

---

## A trickier problem

(Infectious !Send)

```rust
struct RefNode<'a> {
    value: String,
    // RefNode can't be `Sync` because of `Cell<T>`, but that makes `&'a
    // RefNode<'a>` `!Send`, so `RefNode` can't be `Send` either.
    next: Cell<Option<&'a Node<'a>>>,
}

struct IdxNode {
    value: String,
    // If instead of using raw references we use an index, this problem
    // completely goes away.
    next: Cell<Option<NodeIdx>>,
}
```

---

## Takeaways

- Partial success?
- Important lesson: Any set of circular references *must have the same lifetime*

notes:

Kind of promising that Rust can even express this at *all*

---

## Adding Branding and Tracing to our index system

(With some more linked lists)

---

Branding Lifetimes (AKA Generativity)

```rust
// "Branding" Id type -- invariant over 'id
type Id<'id> = PhantomData<Cell<&'id ()>>;

fn generate_an_id(f: for<'a> impl Fn(Id<'a>)) {
    // It doesn't actually *matter* what the "real" lifetime is here for the
    // `Id` we pass in.
    let id: Id<'static> = PhantomData;
    f(id);
}

generate_an_id(|mut a| {
    generate_an_id(|mut b| {
        // Lifetime for `a` and `b` are totally unique!
        // a = b;
        // b = a;
    });
});
```

---

Start with a branded index type (Gc) and a simple Arena

```rust
// Invariant branding ID.
type Id<'gc> = PhantomData<Cell<&'gc ()>>;

// An index into an `Arena` verified at compile time.
#[derive(Copy, Clone)]
struct Gc<'gc> {
    // No need for arena ID or generation!
    index: usize,
    _id: Id<'gc>,
}

// The "inner accessor" (will actually hold all our data)
struct ArenaCtx<'gc, T> {
    slots: Vec<Option<T>>,
    free_list: Vec<usize>,
    _id: Id<'gc>,
}

// Bare minimum arena of a single type.
struct Arena<T> {
    // Real 'gc lifetime doesn't matter!
    ctx: ArenaCtx<'static, T>,
}
```

---

Arena::enter "creates" the branding lifetime, but it is really just 'static

```rust
impl<T> Arena<T> {
    // "Enter" the arena, providing access.
    fn enter<F, R>(&mut self, f: F) -> R
        where F: for<'gc> FnOnce(&mut ArenaCtx<'gc, T>) -> R
    {
        f(&mut self.ctx)
    }
}

impl<'gc, T> ArenaCtx<'gc, T> {
    // Allocate a new value and return the `Gc` index.
    fn alloc(&mut self, value: T) -> Gc<'gc> { ... }

// Access a value by its index. Guaranteed at compile time to have come
    // from `Arena::alloc`!
    fn get(&self, gc: Gc<'gc>) -> &T { ... }
    fn get_mut(&mut self, gc: Gc<'gc>) -> &mut T { ... }
}
```

---

### This works! It is incomplete though

- Gc can't escape Arena::enter
- Can't store Gc inside T (lifetimes don't work out)

Let's solve both of these...

---

Make a new lifetimeless trait for the stored type

```rust
// We will need an implementation of this type for whatever we want our `Arena`
// to store.
trait ArenaType {
    // We can use GATs!
    type Value<'gc>;
}

// Rather than taking a `T` type parameter, take a `A: ArenaType` instead.
struct Arena<A: ArenaType> {
    ctx: ArenaCtx<'static, A>,
}

//Also will need to change our `ArenaCtx` type to use `A` instead.
struct ArenaCtx<'gc, A: ArenaType> {
    slots: Vec<Option<A::Value<'gc>>>,
    free_list: Vec<usize>,
}

impl<A: ArenaType> Arena<A> {
    fn enter<F, R>(&mut self, f: F) -> R
        where F: for<'gc> FnOnce(&mut ArenaCtx<'gc, A>) -> R
    {
        f(&mut self.ctx)
    }
}
```

---

Now we can set up an arena of linked list nodes.

```rust
// A linked list node containing a `Gc` index.
struct Node<'gc> {
    next: Cell<Option<Gc<'gc>>>,
    value: String,
}

impl<'gc> Node<'gc> {
    fn new(value: String) -> Self { ... }
    fn next(&self) -> Option<Gc<'gc>> { ... }
    fn set_next(&self, next: Option<Gc<'gc>>) { ... }
}

struct ArenaNode;

impl ArenaType for ArenaNode {
    // The magic! We can produce our real `Node<'gc> type.
    type Value<'gc> = Node<'gc>;
}

type ArenaOfNodes = Arena<ArenaNode>;
```

---

Still need to store *something* outside. Just use something dead simple for now.

```rust
impl<'gc, A: ArenaType> ArenaCtx<'gc, A> {
    fn alloc(&mut self, value: A::Value<'gc>) -> Gc<'gc> { ... }
    fn get(&self, gc: Gc<'gc>) -> &A::Value<'gc> { ... }
    fn get_mut(&mut self, gc: Gc<'gc>) -> &mut A::Value<'gc> { ... }

// Return the plain index out of a branded `Gc` index
    fn gc_to_index(self, gc: Gc<'gc>) -> usize { ... }

// Turn a plain index back into a branded `Gc` index. 
    fn index_to_gc(self, usize: index) -> Option<Gc<'gc>> { ... }
}
```

---

That's enough pices! Let's look at how this API could be used.

```rust
let arena = Arena::<ArenaNode>::new();

// We pick a "root" value of the `a` node.
let a_root: usize = arena.enter(|ctx| {
    let a = ctx.alloc(Node::new("1".to_owned()));
    let b = ctx.alloc(Node::new("2".to_owned()));
    let c = ctx.alloc(Node::new("3".to_owned()));

a.set_next(Some(b));
    b.set_next(Some(c));
    c.set_next(Some(a));

ctx.gc_to_index(a)
});

// Now, even after we exit the arena, we can re-enter it and get back our
// `root`!
arena.enter(|ctx| {
    let a = ctx.index_to_gc(a_root).unwrap();
    let b = a.next().unwrap();
    let c = b.next().unwrap();
});
```

---

We're only missing *collection*

```rust
impl<A: ArenaType> Arena<A> {
    // Magically, somehow, remove every unreachable value.
    fn collect(&mut self, roots: impl IntoIterator<Item = usize>);
}
```

We need a new trait method to know what is *reachable*.

```rust
// Helper trait for tracing held `Gc` pointers
trait Visitor<'gc> {
    fn visit(&mut self, gc: Gc<'gc>);
}

trait ArenaType {
    type Value<'gc>;

// Visit every held `Gc` pointer and call `visitor.visit(gc)` on it.
    fn trace<'gc, V: Visitor<'gc>>(this: Self::Value<'gc>, visitor: &mut V);
}
```

---

Let's sketch out the missing pieces...

```rust
impl ArenaType for ArenaNode {
    type Value<'gc> = Node<'gc>;

fn trace<'gc, V: Visitor<'gc>>(this: Node<'gc>, trace: &mut V) {
        // This is all our user code needs to do!
        if let Some(next) = self.next.get() {
            visitor.visit(next);
        }
    }
}

impl<A: ArenaType> Arena<A> {
    ...

fn collect(&mut self, roots: impl IntoIterator<Item = usize>) {
        // We have enough pieces to do mark and sweep!

let queue: Vec<usize> = roots.into_iter().collect();
        let visited: HashSet<usize> = HashSet::new();

// Draw the rest of the Owl...
        ...
    }
}
```

---

### Primitive, but contains all the pieces to understand branded pointer GC

- External "roots" are plain usize which is easy to mess up
- We have to pass roots explicitly
- Using any Gc should never panic *assuming ArenaType::trace is implemented
correctly*

---

## The Real Deal

(approximately how gc-arena works)

---

First, fix our root type — no more manually listing roots!

```rust
// Instead of `usize`, hand out something that wraps an `Arc`.
//
// Allows iterating over the roots in `Arena::collect` without having to list
// them, *and* we can pack some identifier in it to prevent arena mixup.
struct Root<A: ArenaType>(Arc<InnerRoot<'gc, A>>);

struct Arena<A: ArenaType> {
    ...
    roots: Vec<Weak<InnerRoot<A>>>,
}

impl<A: ArenaType> Arena<A> {
    ...

// We no longer need to list all of our roots explicitly!
    fn collect(&mut self) { ... }
}

impl<'gc, A: ArenaType> ArenaCtx<'gc, A> {
    ...

fn gc_to_root(self, gc: Gc<'gc>) -> Root<A> { ... }

// Panics if the given `root` was not produced from `gc_to_root` of
    // the same *Arena*.
    fn root_to_gc(self, root: &Root<A>) -> Option<Gc<'gc>> { ... }
}
```

---

Major change - multiple types, store *pointers*.

```rust
// Simple, transparent wrapper around a raw pointer.
#[derive(Copy, Clone)]
#[repr(transparent)]
struct Gc<'gc, T> {
    ptr: NonNull<T>,
    _id: Id<'gc>,    
}

// Helper trait for tracing.
trait Visitor<'gc> {
    fn visit<T: Trace>(&mut self, gc: Gc<'gc, T>);
}

// A new trait! Similar to the `trace` method from our `ArenaType` trait.
//
// If this method *misses* any held pointer, we could observe UAF, so unsafe!
unsafe trait Trace<'gc> {
    fn trace<'gc, V: Visitor<'gc>>(this: Self::Value<'gc>, visitor: &mut V);
}

// The way to produce a value for any given `'gc`
trait ArenaType {
    // The actual value our arena will store, whatever the 'gc lifetime.
    type Value<'gc>: Trace<'gc>;
}

// Rooted handle
struct Root<A: ArenaType> { ... }
```

---

```rust
// Our `Arena` type is now typeless! We can allocate any type within it.
struct Arena {
    ctx: ArenaCtx<'static>,
}

struct ArenaCtx<'gc> {
    ...
    _id: Id<'gc>,
}

impl Arena {
    fn enter<F, R>(&mut self, f: F) -> R
        where F: for<'gc> FnOnce(&mut ArenaCtx<'gc>) -> R
    { ... }
    fn collect(&mut self) { ... }
}

impl<'gc> ArenaCtx<'gc> {
    // Acts like an allocator, takes `&self`.
    fn alloc<T: Trace + Send>(&self, value: T) -> Gc<'gc, T> { ... }

// Gc is compile-time safe, can be implemented as *raw pointer deref*.
    //
    // Relies on `Trace` being implemented correctly!
    fn get(&self, gc: Gc<'gc, T>) -> &T { ... }
    ...

// Calling `gc_to_root` now requires manually naming some *projection* type.
    fn gc_to_root<A: ArenaType>(self, gc: Gc<'gc, A::Value<'gc>>)
        -> Root<A> { ... }
    ...
}
```

---

This design is slightly *better* than gc-arena!

Inert Gc, as harmelss as usize index

```rust
#[derive(Copy, Clone)]
#[repr(transparent)]
struct Gc<'gc, T> {
    ptr: NonNull<T>,
    _id: Id<'gc>,    
}

// Gc has no ops::Deref, so is inert! This is okay to do!
unsafe impl<T> Send for Gc<'gc, T> {}
unsafe impl<T> Sync for Gc<'gc, T> {}
```

---

Our final linked list example (I promise)

```rust
// Possible to make a proc-macro derive unsafe Trace automatically!
#[derive(Trace)]
struct Node<'gc> {
    next: Cell<Option<Gc<'gc, Node<'gc>>>>,
    value: String,
}

struct ArenaNode;
impl ArenaType for ArenaNode {
    type Value<'gc> = Node<'gc>;
}

impl<'gc> Node<'gc> {
    fn new(value: String) -> Self { ... }
    fn next(&self) -> Option<Gc<'gc, Node<'gc>>> { ... }
    fn set_next(&self, next: Option<Gc<'gc, Node<'gc>>>) { ... }
}

// We can place values into our arena, like before...
let a_root = arena.enter(|ctx| {
    let a = ctx.alloc(Node::new("1".to_owned()));
    let b = ctx.alloc(Node::new("2".to_owned()));
    let c = ctx.alloc(Node::new("3".to_owned()));

a.set_next(Some(b));
    b.set_next(Some(c));
    c.set_next(Some(a));

// Create a root to `a`, unfortunately we have to name the projection type.
    ctx.gc_to_root::<ArenaNode>(a)
});
```

notes:

Make sure to mention proc-macro Trace

---

### Why this is so cool

- Make a network of pointers, keep track of just the roots
- Collect anything not reachable from roots based on proc-macro
- Only roots have runtime fallibility!
- Arena and Root are 'static, can be moved freely
- Arena and Root can be Send!
- Network of Rc can't be Send, but a network of Gc is Send!

---

## Wrapping up — The Bigger Picture

- Very cool, but takes a lot to get here
- Sometimes safety, even if difficult, is worth the pain
- Safe GC, the missing data structure?
- A thousand GCs is better than one big GC
- This design space is under explored!

notes:

Used `gc-arena` for years without experiencing a `gc-arena` bug (outside of its
own development).

---

## Where you can find me
- ~~Twitter~~ ~~Bluesky~~ ~~LinkedIn~~
- ~~Tumblr~~ (*Don't ask*)
- Blog: www.kyju.org (Don't update it enough)
- Email (catherine@kyju.org) (Probably won't answer)
- Synchronous is best: I'm on Discord!
- Discord: @u______________________________u
- (30 underscores!)

---

## Thank you!