This post is a nearly verbatim adaptation of my RustConf 2024 talk. I've kept everything in the present tense as it was in September 2024. Towards the end, I've also included a bit of content that I had planned on presenting but had to skip during the presentation for time.

Watch the talk · See the slides · See the full references

Netstack3

So what is this talk about? Well, I'm going to bury the lede a bit.

First, let's talk about Netstack3. Netstack3 is Fuchsia's next-generation, pure-Rust networking stack. It aims to replace Netstack2, which is written in Go.

I started Netstack3 about six years ago, and led its development for four years, and then for the past two years it's been led by a different team. I haven't been on the project for two years, so obviously this is beyond me now – it's a huge team effort – I'm going to be bragging a lot about those folks. There are some really good engineers who work on that now.

Writing a networking stack is a serious undertaking. It's responsible for almost all network traffic in the entire operating system. It implements dozens of protocols, each of which is specified in documents that can run into the hundreds of pages. And it's the first line of defense against any attacker who isn't physically sitting in front of a device.

It's also just big. As I said a second ago, it's taken us six years to get to this point, there have been plus or minus ten developers that whole time, and it's split across 63 crates totaling 192,000 lines of code. That's more code than the top ten crates on crates.io combined.

Over the past year, the team has been preparing to launch Netstack3. Those of you with networking backgrounds will know that you don't just deploy networking code into production.

Networking code is famously difficult to test, and so you have to assume that, despite your best efforts, your code is riddled with bugs.

For a project of this scale — deploying an entirely new, ground-up rewrite of a netstack — you would expect to dogfood in the field for months or maybe even years before shipping to real users. In that time, you would expect to uncover tens to hundreds of bugs that you hadn't seen during development. And only once you had burned down most of those bugs and seen relatively stable behavior for a while, only then would you finally deploy to real users.

So let's talk about what the process has looked like for Netstack3. For 11 months, the team has been ramping up a dogfooding program. At peak, that program has seen about 60 devices running nearly 24/7 in developers' homes.

Again, if this were any other netstack, we would have expected to uncover a giant mountain of bugs in that time. So, over the past year, how many bugs did the team uncover in the field?

Three.

Note from the future: As of posting, Netstack3 is now in production, running on millions of devices. Immediately after its first deployment, the team observed a ~20x lower rate of crashes per million devices per day and a 50% reduction in memory usage compared to its predecessor, Netstack2.

So this talk is going to be something of a flashback.

Netstack3 was designed around a particular methodology for how to architect robust systems. Hopefully I've convinced you that we did at least something right on the robustness front.

In a sentence, that methodology says:

Buggy programs don't compile.

Obviously, I am far from the first person to suggest this methodology. Here is just a small sample of crates that use this methodology somewhere in their APIs:

ghost-cell, session_types, nalgebra, mundane, indexing, zerocopy, and bytemuck.

And here is a small sample of what has been written on the topic, both about Rust and about other languages:

So my goal for this talk is not to introduce a new idea.

Instead, my goals are:

First, I'm going to propose a concrete but general framework that attempts to unify all of the different ways this methodology shows up in practice, and explain them in terms of the same basic concepts.

Second, I'm going to walk through two examples — one from the standard library and one from Netstack3 — and show how we can explain them in terms of this framework.

Unfortunately 25 minutes isn't enough time to present more than two examples in the depth I'd like. I had to leave a lot on the cutting-room floor when I was writing this talk. But I promise that these two examples only scratch the surface of what's possible. The full list of references contains a surprising diversity of problems which this methodology has already been applied to.

What do we mean by “buggy programs don't compile”?

On its website, Rust advertises three properties: performance, reliability, and productivity. Let's zoom in on reliability.

The website says:

Rust's rich type system and ownership model guarantee memory-safety and thread-safety.

In other words, out of the box, Rust guarantees that "buggy programs don't compile," but only if we restrict our definition of "bug" to memory bugs or threading bugs.

Don't get me wrong: memory safety and thread safety are huge on their own. For example, Netstack3 is able to pull all sorts of crazy buffer-sharing tricks in the name of performance that would be wildly dangerous in C or C++. I gave a talk on those techniques at Rust Belt Rust in 2018 if you're curious about the details.

But that's only half the story.

Many critical bugs that we'd like to prevent are neither memory bugs nor threading bugs.

Take TCP, for example. If you want to implement what RFC 4614 refers to as "basic functionality" for TCP, you need to implement six different standards that run a combined 270 pages.

Add in the "recommended enhancements" and you're up to a total of 18 standards spanning 476 pages.

And that's just one protocol. Add Ethernet, ARP, NDP, IPv4, IPv6, ICMP, IGMP, MLD, UDP, and a host of others, and all the subtle interactions between them, and you start to realize that memory and threading bugs are just the tip of the iceberg of all the fun and exciting ways that you could fuck it up.

That's why uncovering only three bugs in almost a year of dogfooding is so surprising. There's just no way that memory safety or thread safety alone would get you that level of robustness.

So the points I'm trying to make are:

  1. Out of the box, Rust guarantees that "buggy programs don't compile" only with respect to a small subset of the bugs we actually care about.
  2. Netstack3 would not have been able to achieve the level of robustness that it has by relying only on what the language provides out of the box.

However, what Netstack3 has done — and what I believe any project can do — is to extend the Rust language to guarantee freedom from almost any class of bugs, not just memory or threading bugs.

This is what I mean by "X-safety" in the talk's abstract.

As it stands today, Rust provides a core set of abstractions — lifetimes, references, RAII, traits, etc — and guarantees various safety properties related to those abstractions.

But the majority of abstractions in the ecosystem are provided by libraries: JSON, random-number generators, cryptography, regular expressions, logging, time, TCP, PNG, SQL, command-line interfaces, linear algebra, browser APIs, and so on. Those libraries generally don't provide the same degree of safety with respect to their abstractions that we might expect from the language.

But it doesn't have to be that way.

As we'll see in the following examples, Rust's core abstractions alone are sufficient to express almost any safety property that we might care about. I claim that every library can and should provide the same level of safety with respect to its abstractions that we already expect of the language itself.

A general framework for safety

To explain the framework, we're going to turn to the humble binary tree:

struct Node<T> {
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
    value: T,
}

For our binary tree to be correct, we of course need memory safety, but we need another safety property as well. We have to ensure that the tree is ordered: every value in the left subtree is less than our node's value, and our node's value is less than every value in the right subtree.

Rust can guarantee memory safety, but it has no visibility into this ordering requirement, and so it can't enforce it for us. So how do we make sure that we never produce an invalidly-ordered tree?

We use the concept of an invariant.

First, we document an ordering invariant that we expect to always hold for any Node:

struct Node<T> {
    // INVARIANT: All values in `left` are less than `value`.
    left: Option<Box<Node<T>>>,

    // INVARIANT: All values in `right` are greater than `value`.
    right: Option<Box<Node<T>>>,

    value: T,
}

Next, we ensure that every time we create a new Node, the ordering invariant holds:

impl<T> Node<T> {
    // Post-condition: `Node`'s internal field invariants hold.
    pub fn new(value: T) -> Node<T> {
        Node {
            left: None,
            right: None,
            value,
        }
    }
}

And finally, we ensure that every time we modify an existing Node, we preserve the ordering invariant, assuming it held to begin with:

impl<T> Node<T> {
    // Pre-condition: `Node`'s internal field invariants hold.
    // Post-condition: `Node`'s internal field invariants hold.
    pub fn insert(&mut self, value: T) -> Option<T> {
        // ...
    }
}

Now imagine that you are code outside of this module. (We'll restrict ourselves here to safe code; obviously unsafe code can do whatever it wants.)

I claim that, from the perspective of safe code outside of this module, there is no difference whatsoever between the safety invariants provided by the language and the ordering invariant provided by this module.

If you write code which, if run, would violate Rust's memory-safety guarantees, Rust guarantees that the code will not compile. By a similar token, if you write code outside this module which, if run, would violate the ordering invariant, then similarly Rust guarantees that the code will not compile.

In other words, by structuring our code in this way, we have in some sense "taught" Rust about a new safety property that it didn't know about before.

We can use this Node example to explain the framework. It has three components.

Definition

First, definition.

We define an object that the Rust type system can reason about. In this case, we define the Node struct. We attach to this object a safety property that Rust cannot reason about. In this case, that is the ordering property.

Because Rust can't reason about this safety property, it's up to us, as the authors of the abstraction, to make sure never to violate it. This brings us to the second component.

Enforcement

Second, enforcement. Here, we enforce that our safety property is upheld – that responsibility is on us as the programmers.

In this case, we use field privacy – we make sure that our struct fields are private. If they were public, external code could modify them and violate our safety property.

Next, we make sure that all the code we write preserves the safety property. In this case, the methods that modify the tree are responsible for maintaining its order.

Consumption

Finally, consumption. This is where we get the bang for our buck.

We write code that consumes the safety property as a precondition, and is only correct in virtue of that safety property being upheld. In this case, our methods can find the correct location in the tree for a particular value in O(log N) time, without having to traverse the entire tree.

That optimization is only valid because we are guaranteed that the tree is ordered. And the tree is only guaranteed to be ordered because we structured our code to define and enforce this ordering property so that we could later consume it as a precondition.

With that framework in mind, Let's get to our first example.

Example 1: Thread safety

Our first example is from the standard library and concerns thread safety.

What I'm going to demonstrate is that not only can libraries use the language's core features to build new safety guarantees, but the standard library itself already uses this technique.

In fact, the thread safety that Rust advertises as one of its core features is not actually a language feature at all. It is implemented in the standard library and, in principle, could have been implemented in a third-party crate. It's just convenient to have it in the standard library.

Imagine that you're writing spawn. spawn is a real function from the thread module in the standard library (although I've stripped down its signature for simplicity):

pub fn spawn<F: FnOnce()>(f: F) { ... }

It takes a function and spawns a new thread that will run that function.

If we think about how we might implement spawn, we immediately run into a limitation in the language: the Rust language itself doesn't provide any mechanism to interact with threads. Threads are an operating system concept, and so creating a new thread requires going outside the language and making use of an API provided by the operating system itself.

For example, on a POSIX system, this might require calling libc's pthread_create function:

pub fn spawn<F: FnOnce()>(f: F) {
    unsafe { libc::pthread_create(/* ... */) };
}

This is where we run into the first core abstraction that we'll need to use as a building block.

Since libc functions like pthread_create are implemented outside the language, Rust has no visibility into their behavior, and so it has no way of guaranteeing that calling such a function won't violate memory safety.

This is why Rust introduces the notion of unsafe code. unsafe code is code that Rust can't guarantee won't violate memory safety. That doesn't mean it definitely will violate memory safety. It just means that, on its own, Rust isn't smart enough to prove that it won't. Instead, Rust has to rely on the programmer to do the heavy lifting and confirm that the unsafe code is correct — or sound.

This is the purpose of an unsafe block like the one above. Inside an unsafe block, Rust gives the programmer free rein to perform operations that Rust can't reason about. In exchange, the programmer takes responsibility for upholding memory safety. If they mess it up, all bets are off.

This is our first example of using a core abstraction to extend the power of the language. Rust itself provides unsafe functions and unsafe blocks, but it doesn't provide any mechanism for interacting with threads. However, by using unsafe in combination with external APIs like pthread_create, we can "teach" the language about threads.

As written, though, this implementation of spawn is unsound.

Not all values are thread-safe, meaning that not all values are sound to send between threads. Think of the difference between Arc and Rc. As written, there's nothing to stop you from passing a closure that captures some value that is not thread-safe.

So the standard library encodes the notion of thread safety in the type system.

First, we introduce a new trait called Send:

/// # Safety
///
/// `Self` is thread-safe.
pub unsafe trait Send {}

This is the standard-library Send that you all know and love.

Note that Send is an unsafe trait. Just like unsafe functions, unsafe traits tell the type system: "This trait has safety implications that you can't reason about." Just as calling an unsafe function can only happen inside an unsafe block, implementing an unsafe trait requires an unsafe impl block. The programmer must opt into taking responsibility for upholding memory safety.

Since the language can't reason about the meaning of Send – it's just an opaque trait with some name – we have to document its meaning in prose like we've done here. In this case, we say that a type can only be Send if it's thread-safe.

Now that we've introduced this trait, we can use it as a bound elsewhere in our program:

pub fn spawn<F: FnOnce() + Send>(f: F) {
    unsafe { libc::pthread_create(/* ... */) };
}

By requiring that F implement Send, we can make spawn sound. There's no longer a risk that a programmer could accidentally call spawn with a non-thread-safe value, because that wouldn't type-check.

So we've introduced this Send trait that encodes the notion of thread safety, but we haven't actually implemented it for anything. Let's do that.

First, we can implement Send for any built-in type that we know is always thread-safe:

unsafe impl Send for u8 {}
unsafe impl Send for u16 {}
unsafe impl Send for u32 {}

From Rust's perspective, this is axiomatic. Using these unsafe impl blocks, we've declared by fiat that the Send property holds of these types.

Again, Rust has no way of knowing what Send means, and so it has no way of knowing whether these implementations are correct. It's just taking our word for it.

We can also implement Send for more complex types. For example, a mutex is thread-safe by design, and so it's okay to send mutex references between threads:

unsafe impl<'a, T: Send> Send for &'a Mutex<T> {}

Finally, we can permit arbitrary composite types to implement Send by writing a custom derive:

#[derive(Send)]
struct Foo<T, U>(T, U);

Of course, in reality, Send uses a special mechanism known as an auto trait to accomplish the same thing for ergonomics reasons. My point here is that there is no reason in principle that Send couldn't have been developed as a library maintained by somebody other than the Rust project. Again, the core abstractions provided by the language are enough on their own to permit somebody to build an abstraction as powerful as Send outside the Rust language project itself

Sticking with the hypothetical, our custom derive would automatically emit an unsafe impl block with the appropriate bounds. In particular, a type can be Send if all its fields are Send:

#[derive(Send)]
struct Foo<T, U>(T, U);

// Derive-generated code:
unsafe impl<T, U> Send for Foo<T, U>
where
    T: Send,
    U: Send,
{}

Since Send is just a normal trait, once we've written our implementations, it works like any other trait:

let foo: Foo<&Mutex<u8>, u16> = /* ... */;
spawn(move || {
    // use `foo`
});

We know that this Foo type is Send because:

  1. We derived Send for Foo.
  2. We manually implemented Send for Mutex references.
  3. We manually implemented Send for primitive types.

How does this example fit into our framework?

Definition

We define Send, teaching Rust about a new trait. We use prose to document that Send carries a special safety property that Rust can't reason about: thread safety.

Enforcement

We define Send as an unsafe trait so users can't violate the safety property without writing the unsafe keyword.

We manually implement Send for types that we know satisfy the safety property.

And, in our hypothetical version, we write a custom derive that generates an implementation that guarantees thread safety by requiring every field to be Send.

Consumption

In spawn, we use a Send bound to justify that our internal call to pthread_create is sound.

And that's how Rust guarantees thread safety without any support from the language itself.

Example 2: Deadlock prevention

Our second example is about preventing deadlocks. This is work by Alex Konradi, who was on the Netstack3 team at the time – I'm basically just bragging for him.

Imagine you're writing a netstack and you want to make your stack multithreaded. You care about performance, so instead of putting one mutex around all your state, you do fine-grained locking, using small mutexes around different pieces of state:

struct Stack {
    ip: Mutex<IpState>,
    device: Mutex<DeviceState>,
}

As we saw in the previous example, Rust will guarantee that anything you do with these mutexes is thread-safe, but it won't prevent you from deadlocking.

For example, imagine two different threads acquire these mutexes in different orders:

// Thread A
stack.ip.lock();
stack.device.lock();

// Thread B
stack.device.lock();
stack.ip.lock();

This is a classic deadlock scenario. If we're unlucky, Thread A will successfully acquire the IP mutex and Thread B will successfully acquire the device mutex. Now, to make progress, they're each blocked on the other.

You can conceptualize this as a graph of the locks we might want to acquire. All threads start in an Unlocked state, and can take different paths through the graph in order to acquire different locks:

%%{init: {"theme":"base","securityLevel":"loose","flowchart":{"htmlLabels":true,"padding":1,"diagramPadding":0,"wrappingWidth":520},"themeCSS":".diagram-box{stroke:none!important}.box-unlocked{fill:#e0e0e0!important}.box-ip{fill:#f2d4d3!important}.box-device{fill:#d3d2f5!important}.diagram-black{fill:none!important;stroke:#000!important;stroke-linecap:butt!important;stroke-linejoin:miter!important}.black-left{stroke-width:1.4px!important}.black-right{stroke-width:1.4px!important}.diagram-red{fill:none!important;stroke:#db3b26!important;stroke-width:2.8px!important;stroke-linecap:butt!important;stroke-linejoin:miter!important}.diagram-arrow{fill:#db3b26!important;stroke:none!important}.diagram-label{fill:#000!important;font-family:Liberation Mono,Menlo,Monaco,Consolas,Courier New,monospace!important;font-weight:400!important}.diagram-node-label{font-size:38px!important;letter-spacing:0.375px!important;stroke:#000!important;stroke-width:0.8px!important;paint-order:stroke fill!important}.diagram-thread-label{font-size:26.75px!important;letter-spacing:0.125px!important;stroke:#000!important;stroke-width:0.5px!important;paint-order:stroke fill!important}"}}%%
flowchart TB
  canvas["<svg xmlns='http://www.w3.org/2000/svg' width='520' height='399' viewBox='0 0 586 450' style='display:block'><g transform='translate(-2,-1)'><rect class='diagram-box box-unlocked' x='197' y='23' width='198' height='128'/><rect class='diagram-box box-ip' x='21' y='240' width='198' height='198'/><rect class='diagram-box box-device' x='373' y='240' width='198' height='198'/><line class='diagram-red' x1='127' y1='307.6' x2='365' y2='307.6'/><polygon class='diagram-arrow' points='361.5,301.5 373,307.5 361.5,313.5'/><line class='diagram-red' x1='230' y1='375' x2='465' y2='375'/><polygon class='diagram-arrow' points='231,369 219,375 231,381'/><path class='diagram-black black-left' d='M197 86.75 H127.25 V307.75'/><path class='diagram-black black-right' d='M395 86.75 H465 V376'/><text class='diagram-label diagram-node-label' x='295.75' y='101' text-anchor='middle'>Unlocked</text><text class='diagram-label diagram-node-label' x='120.5' y='352' text-anchor='middle'>IP</text><text class='diagram-label diagram-node-label' x='471.75' y='353' text-anchor='middle'>Device</text><text class='diagram-label diagram-thread-label' x='295.5' y='298' text-anchor='middle'>Thread A</text><text class='diagram-label diagram-thread-label' x='296.25' y='401' text-anchor='middle'>Thread B</text></g></svg>"]
  style canvas fill:transparent,stroke:transparent,stroke-width:0px

To avoid the risk of deadlocking, we need to make sure that this graph is acyclic. The two acquisition orders above form a cycle, so we need to remove at least one of those red edges.

This might seem like a fairly trivial problem in this tiny example. It's pretty obvious from looking at the code that it might deadlock.

But Netstack3 has 77 different mutexes protecting all manner of different state spread across 192,000 lines of code. You can imagine that keeping track of the order in which you're supposed to acquire mutexes in that environment would get pretty difficult pretty fast.

And indeed, Netstack2, its predecessor which is written in Go, has historically been plagued by deadlocks.

So the Netstack3 team decided to try to prevent deadlocks statically, at compile time. To do this, they needed a way to encode a lock-order graph in the type system and a way to ensure that code could only acquire locks consistent with that graph.

Let's see how they did it.

Name every mutex

The first step is to name each mutex:

struct Mutex<Id, T> {
    mtx: std::sync::Mutex<T>,
    _marker: PhantomData<Id>,
}

This new Mutex type is identical to the standard-library mutex, except that it carries an extra type parameter used to identify the mutex.

Returning to our example, we define one type per mutex and use those types as names:

struct Stack {
    ip: Mutex<IpLock, IpState>,
    device: Mutex<DeviceLock, DeviceState>,
}

enum IpLock {}
enum DeviceLock {}

These types are never constructed at runtime. We only need them for type-system purposes.

Encode the lock-order graph

Next, we define the LockAfter and LockBefore traits:

/// # Safety
///
/// No cycles!
pub unsafe trait LockAfter<M> {}

pub unsafe trait LockBefore<M> {}

unsafe impl<B: LockAfter<A>, A> LockBefore<B> for A {}

These traits encode the lock-order graph. They're unsafe to implement because the user has to promise not to introduce a lock-order graph with cycles. If they do, they violate our safety property.

Next, we define a macro that implements these traits on behalf of a user:

macro_rules! impl_lock_after {
    ($A:ty => $B:ty) => {
        // SAFETY: The blanket impl will cause any cycles
        // to result in a blanket impl conflict, and thus
        // won't compile.
        unsafe impl LockAfter<$A> for $B {}

        unsafe impl<X: LockBefore<$A>> LockAfter<X> for $B {}
    };
}

impl_lock_after!(TransportLock => IpLock);
impl_lock_after!(IpLock => DeviceLock);

Note that the macro expansion adds a blanket implementation. Don't worry about following the full logic here, but the consequence of that blanket implementation is important: if a user invokes the macro in a way that introduces cycles into the lock graph, those blanket implementations will conflict with one another.

Cyclic graphs therefore fail to compile.

Track the current position in the graph

Next, we define the notion of a lock context:

struct LockCtx<Id>(PhantomData<Id>);

A LockCtx allows the type system to keep track of where in the lock graph you are at any given point in the source code. It is a zero-sized type, so it has no cost at runtime.

Using these building blocks, we can build a deadlock-proof locking API:

impl<Id, T> Mutex<Id, T> {
    pub fn lock<L>(
        &self,
        ctx: &mut LockCtx<L>,
    ) -> (MutexGuard<'_, T>, LockCtx<Id>)
    where
        L: LockBefore<Id>,
    {
        (
            self.mtx.lock().unwrap(),
            LockCtx(PhantomData),
        )
    }
}

Let's walk through the components of this signature one by one.

First, we require an existing LockCtx. Note that we borrow it mutably, which disables the LockCtx for further use until we've unlocked the mutex by dropping the MutexGuard. So long as we're holding the mutex, that context is effectively unusable.

Second, we require that the existing LockCtx has a lock ID upstream of our lock ID in the graph. This prevents us from locking a mutex which we've already locked.

L: LockBefore<Id>

Finally, we return a new LockCtx that the caller can use to continue locking mutexes (recall that the original LockCtx is now unusable so long as the current mutex is held). This new LockCtx has our lock ID. So long as the returned MutexGuard exists — in other words, so long as this lock is held — this new LockCtx is the only usable lock context, and it only permits locking mutexes downstream of this one in the lock graph.

One last bit of boilerplate: to represent the root of any lock graph, we introduce the Unlocked type and permit anyone to construct a lock context that starts off unlocked:

pub enum Unlocked {}

impl LockCtx<Unlocked> {
    pub const UNLOCKED: LockCtx<Unlocked> = LockCtx(PhantomData);
}

Use the graph

Let's go back to our example and see how we can use this machinery to prevent deadlocks.

As we showed before, we introduce one type for each mutex and use the macro to encode our graph in the type system as implementations of LockAfter and LockBefore:

struct Stack {
    ip: Mutex<IpLock, IpState>,
    device: Mutex<DeviceLock, DeviceState>,
}

enum IpLock {}
enum DeviceLock {}

impl_lock_after!(Unlocked => IpLock);
impl_lock_after!(IpLock => DeviceLock);

Remember that this code will only compile so long as the graph is free of cycles.

Now let's walk through how we use this graph at runtime. First, we construct a new context that starts in the unlocked state:

let mut ctx = LockCtx::UNLOCKED;

Next, we lock our first mutex — the IP mutex. This generates a MutexGuard and a new LockCtx that shadows the old one:

let (ip, mut ctx) = stack.ip.lock(&mut ctx);

Finally, we repeat the same process to lock the device mutex:

let (device, mut ctx) = stack.device.lock(&mut ctx);

Putting it together:

let mut ctx = LockCtx::UNLOCKED;
let (ip, mut ctx) = stack.ip.lock(&mut ctx);
let (device, mut ctx) = stack.device.lock(&mut ctx);

Now take a look at what happens if we try to violate the lock order. As before, we start in an unlocked state and directly lock the device mutex:

let mut ctx = LockCtx::UNLOCKED;
let (device, mut ctx) = stack.device.lock(&mut ctx);

On its own, that is fine. We haven't introduced a cycle yet, so it compiles.

But if, having acquired the device mutex, we now try to acquire the IP mutex, that won't compile, because there's no path in the graph from the device mutex to the IP mutex:

let (ip, mut ctx) = stack.ip.lock(&mut ctx);
//                                ^^^^^^^^ ERROR

How does this fit into our framework?

Definition

First, we define the LockAfter and LockBefore traits. We document in prose that they carry a safety property: they always encode an acyclic graph.

Second, we define the Mutex type. We document in prose that it carries a safety property: it is only locked consistent with a predefined lock-order graph.

Enforcement

We make the LockAfter and LockBefore traits unsafe so that a user can only violate our safety property by writing the unsafe keyword.

We design impl_lock_after! so that it guarantees that only acyclic graphs can compile.

And we use a LockBefore bound to ensure that the lock method can only be called consistently with the lock-order graph.

Consumption

The lock method uses its LockBefore bound to justify that locking the inner mutex won't deadlock.

What I have presented here is a simplified version of what exists in practice. There are actually two subtle ways that I'm aware of that you can violate deadlock safety using this simplified version. And there's an interesting conversation to be had about whether safety properties like these should be literally impossible to circumvent, or whether they only need to be hard enough to circumvent that you could't shoot yourself in the foot by accident.

In reality, the lock-ordering library takes the latter approach. I'm not going to get into that discussion here, and it doesn't really affect the point I'm trying to make.

The results

How has this played out for Netstack3?

In the beginning, Netstack3 was entirely single-threaded for simplicity. But over the past few years, the team has been working to thread mutexes and mutex guards through the entire stack. Finally, just a few weeks ago, they had finished that process and were ready to flip the switch — to go from running on one thread to running on multiple threads.

So they changed the default number of threads from one to four:

- Self(NonZeroU8::new(1).unwrap())
+ Self(NonZeroU8::new(4).unwrap())

That's it. That was the whole change. It was bug-free on the first try.

Conclusions

Those are my two examples.

I'd like to encourage you to try this methodology for yourself, and especially to bring it to new domains and new classes of bugs that nobody in the Rust community has tackled yet.

Let me give you a few pieces of concrete advice to help get you started.

Treat partial functions as a code smell

On a practical note, think of partial functions in your API as a code smell.

Your public functions should never panic, and they usually shouldn't return Option or Result unless that is inherent to the behavior you're modeling.

Returning an error because an I/O operation failed is unavoidable and totally fine. Returning an error because the caller passed an illegal value? That code shouldn't have compiled in the first place.

For great primers on this way of thinking, I recommend Parse, don't validate and Type Safety Back and Forth.

Make your APIs exactly match the problem

Make your APIs exactly match the structure of the problem you're modeling.

Here is the error type that Netstack3 returns when it fails to parse an IP packet:

pub enum IpParseError<I: IcmpIpExt> {
    Parse {
        error: ParseError,
    },
    ParameterProblem {
        src_ip: I::Addr,
        dst_ip: I::Addr,
        code: I::ParameterProblemCode,
        pointer: I::ParameterProblemPointer,
        must_send_icmp: bool,
        header_len: I::HeaderLen,
        action: IpParseErrorAction,
    },
}

pub enum IpParseErrorAction {
    DiscardPacket,
    DiscardPacketSendIcmp,
    DiscardPacketSendIcmpNoMulticast,
}

pub enum ParseError {
    NotSupported,
    NotExpected,
    Checksum,
    Format,
}

This may seem surprisingly convoluted, but it is a faithful representation of the complexity of both the IPv4 and IPv6 protocols. To do anything simpler would cause us problems down the line.

For example, let's zoom in on the parameter problem pointer field.

If you receive a malformed packet, you have to respond with your own packet containing an error message. That error message identifies the byte offset of the malformed field that caused parsing to fail. That byte offset is known as the "parameter problem pointer".

Note the generic type here. In IPv4, the field in the error message that stores this pointer is one byte long. In IPv6, it's four bytes long. Using generics ensures that we always store the byte offset using the right size of integer.

If instead we uniformly stored the pointer as, for example, a u32, we would have to perform a fallible conversion elsewhere in the codebase. If we had a bug, that conversion would either silently produce incorrect error packets or panic and crash the stack.

By ensuring that our error type faithfully models the behavior of IPv4 and IPv6, we can make that sort of bug impossible.

Expect diverse solutions

Don't expect the solution to always be the same.

Just because the catchphrase is always that "buggy programs don't compile" doesn't mean that there's a recipe. In my experience, different problems call for wildly different solutions that leverage a hodgepodge of language features.

Simplicity is the art of hiding complexity

Don't expect it to always fall out naturally.

One of my favorite quotes is from Rob Pike, talking about Go's design:

Simplicity is the art of hiding complexity.

Your responsibility is to do the hard work so that your users have a simple mental model of your API and they don't have to understand how awful the internals of your library are.

Rust wasn't explicitly designed to support this methodology, at least not in its full generality, and you may have to really bend the language to your will.

For example, if you haven't seen the trick, it is not at all obvious that it would be possible to prevent graph cycles using the trait system. The internals of the lock-ordering library are kind of ugly as a result, but the mental model that a user needs in order to reason about the API is very simple:

Cyclic graphs don't compile.

That's it.

Turtles all the way down

When it comes to your internal APIs, use the same level of discipline and rigor that you would use with a public API.

If a function has safety requirements, make it an unsafe function. If a function can panic, document it clearly.

It may seem obvious in the moment how to call an internal API correctly, but it won't be so obvious to the new developer on the team four years and six refactors from now. If you keep up this discipline, then no matter how much time passes, your internal APIs will be just as easy to use correctly as the day you wrote them.

We adhered to this discipline strictly in Netstack3, and the larger the project grew, the more it paid off.

A bit of speculation

We're late in the podcast now, so we can let our hair down a bit and speculate.

– Sean Carroll

Finally, if you'll permit me a bit of speculation, I think this methodology has the potential to fundamentally reshape how we engage in the process of software engineering, and I think that so far we've only scratched the surface of how far we can push it.

One reason is that there are domains where correctness is a much bigger deal than it is for most of us in this room. Rust is only just starting to make inroads into high-assurance domains like automotive, aerospace, medical devices, and so on. Those are domains where bugs are so unacceptable that the pace of development is absolutely glacial.

I'm not suggesting that we're going to be able to stop doing code reviews or anything crazy like that. But imagine how much faster we could move if we eliminated entire classes of bugs that we normally have to catch through reviews or testing.

Another reason I think this methodology could be a big deal is that it allows software to scale more effectively.

Software complexity often scales superlinearly as a function of the size of the codebase, and much of that complexity is incidental rather than inherent. Humans only have so much mental capacity. As incidental complexity increases, it crowds out our ability to reason about the inherent complexity that we're actually interested in. That puts a natural upper limit on the inherent complexity of the problems we can tackle.

My guess is that this methodology stands to make the biggest difference in large, complex codebases, where small savings in complexity across every module compound on one another.

That has certainly been our experience in Netstack3.

As I mentioned at the beginning, I wasn't able to provide nearly as many examples as I would have liked. I strongly encourage you to check out the references and do more reading on your own.

I really believe that, thanks to Rust, we have the opportunity to fundamentally improve the state of software engineering, and I intend to spend the next phase of my career proving it.

I hope you'll join me. Thank you.