iddqd, or the hardest kind of unsafe Rust
Mirrored from the canonical version on the Oxide blog . I’m the main author of , a Rust library for maps (named after the Doom cheat code ) where keys are borrowed from values. At Oxide we use it extensively in Omicron , our control plane—the software that sits at the heart of every Oxide rack, provisions resources like compute and storage for our customers, and ensures the rack stays up and running over time. maintains in-memory indexes of the kinds of large records that show up everywhere in a system like that, such as disks or sled inventories . As a result, it must be correct: if it misbehaves, our control plane can malfunction in ways that are unpredictable and hard to diagnose. consists of a fair amount of unsafe code underneath. There’s been some recent concern over the amount of unsafe code in Rust rewrites, so I thought I’d write about some of the unsafe code in and how we try to tame it. With Rust’s standard library maps, keys are stored separately from values. Let’s say you want to store a map of records keyed by an email address. With , you might write something like: This approach has what I consider to be a pretty major downside: the key (email) is not stored in the same struct as the value (the rest of the record). How would you handle this? One way is to pass around both the email and the user, for example with : As an extension, you could maybe have a struct which combines both at fetch time: In practice, this gets quite unwieldy when you have lots of different types of records that need this kind of treatment. Alternatively, you could duplicate the email across the key and the value: But that has the risk that the emails stored in the key and the value fall out of sync. provides a better alternative. With , you can write something like: At Oxide, this has proven to be an invaluable pattern: many of the records in our control plane are quite large (think database lookups), and is a great fit for them. It also comes with several other features that directly address pain points we’ve dealt with at Oxide. A few worth calling out: Like many of our other crates, is built for Oxide’s needs but is generally useful to the Rust community. You’re welcome to use it in your own projects as well. Before I move on, I want to talk about what it means for to exist in a memory-safe language. The big concern is undefined behavior (UB): a program behaves in an unpredictable way because core assumptions made by the language or compiler have been violated. Rust calls an abstraction sound if no safe code can use it to cause UB, and unsound otherwise. The vast majority of Rust code is safe, which (assuming that any unsafe used by the safe code is sound) means that no UB can occur. However, due to the fundamental undecidability of static analysis (see Rice’s theorem ), it is impossible for the Rust compiler—or any kind of algorithm that terminates—to accept all programs without UB and reject all programs with it. Therefore, when writing such an algorithm, its authors have to make a decision: do they reject some programs without UB, accept some programs with UB, or both? The Rust compiler does the first: within the context of safe Rust, it rejects all programs with UB but also some without UB. (This is the correct choice!) What if your program is in the no-man’s-land where it gets rejected even though you know it doesn’t have UB? To express those kinds of programs, the Rust compiler provides an escape hatch: the keyword. By writing it, the author takes responsibility for soundness: they vouch that no safe code can use this to cause UB, and that the compiler should trust them. What does it mean for some unsafe code to not have UB? Informally, it must follow the rules of Rust —all the rules that the compiler proves for safe Rust. Some examples of these rules are: The rules of Rust are very hard to reason about! I consider them to be significantly harder than C, for example, particularly due to the rules around mutable aliasing 2 . So judicious use of unsafe Rust usually involves encapsulating it behind a safe abstraction. In all but the simplest of cases, it is not possible to be sure that such an abstraction is sound without also reasoning about the surrounding safe Rust. In this section, I’ll walk through three examples in increasing order of difficulty. The first example is the method on slices. This method splits a mutable slice into two separate parts. is a safe method, but safe Rust lacks the ability to express this kind of partitioning of a slice. Thus, requires unsafe Rust. The implementation is roughly: To be sure of the correctness of the unsafe block, you also have to consider several things about the surrounding safe code: If any of these invariants (all of which are safe Rust) are not upheld, the safe abstraction becomes unsound. The next level up is that in many cases you also have to analyze the entire module the unsafe code is present in. Consider this vector type: The soundness of relies on every other method in the module, safe and unsafe, ensuring that is correct and in bounds. Encapsulation and privacy ( cannot be mutated from outside the module) are load-bearing here. The hardest situations, though, are when unsafe code is generic and calls back into user-supplied code. In those cases, the fundamental principle is: Safe Rust code, no matter how pathological or adversarially written, must never cause unsafe code to exhibit undefined behavior. In other words, you no longer have the luxury of analyzing just the safe code you see; you must put yourself in the shoes of an attacker, considering every safe Rust program one could write, and be resilient to all of them. For example, it is possible for user code to misbehave in a way that leads to internal tables or data structures being corrupted. Safe but buggy Rust may cause unsafe Rust to be slower, produce incorrect results, or even panic, but it must not cause UB! (Why assume the worst? You might argue that well-meaning Rust developers are quite unlikely to write adversarial code. One reason for having a firm rule is that guarding against adversarial code means guarding against innocent mistakes as a corollary; a bright line makes it easier to assign responsibility for protection against UB.) An example is the trait, which has a method that returns the exact size of an iterator. A developer might be tempted to take advantage of this in unsafe Rust: This code does not cause UB if the iterator is well-behaved. But there’s no guarantee of such behavior! It is entirely possible to write a broken implementation that returns a bogus result, all in safe Rust: will write into unallocated memory in this case, so it is unsound in general 3 . Another example is the trait , where a safe but buggy implementation can return the wrong number of bytes read. See Rust RFC 2930 for more discussion about this. is in exactly this situation: it consists of generic data structures which call into user-supplied code, so it is working at this highest level of difficulty 4 . ’s architecture is pretty straightforward: it uses a combination of a list of items (internally called an ) and a table with indexes into the slots. For example, consists of: For example, an holding three items might look like the diagram below. The top row is the hash table over ; the middle row is the . Adding a new item consists of checking to see if any slots are available. If so, we read the index out of that slot, overwrite the slot with , then set to the value we read. Otherwise, we push a new slot to the end. Finally, the hash table is updated, fetching the key and computing the hash, then recording the new index in the hash table. Starting from the state above: Let’s say we want to insert a new item . Calling recycles slot from the free chain, advances to , and records the new hash entry: Removing an item given a key involves this process in reverse: first, consult the hash table using the hash computed from the key, and remove the found index from the hash table. With the index in hand, replace the with , setting the internal to the current value of . Finally, set to the index that was just replaced with . Continuing from the post-insert state above: Calling drops the hash entry for , marks slot as with its pointing at the old ( ), and updates to : This pattern generalizes to the other map types: has a few different kinds of unsafe Rust within it. Most uses of unsafe follow well-established patterns also used within Rust’s standard library —these are not dependent on user code, and a sufficiently smart borrow checker would make these uses of unsafe unnecessary. But there are a few that stand out. Perhaps the most challenging one to reason about is mutable iteration over items. For , iteration is ordered by the key. One might start off by writing something like: But this would immediately return an error: The reason this occurs is that Rust’s iterators require that the returned values do not borrow from the iterator itself 6 . Many uses of iterators do not need this capability—in particular, most for loops only operate on one item at a time: But Rust’s iterators also let you create values that outlive the iterator, via e.g. the combinator : cannot outlive itself, but can outlive the iterator returned by . Crucially, this relies on knowing that all of the returned by the iterator are disjoint—or, in other words, that the iterator never yields the same value twice. (Remember that one of the rules of Rust is that there must never be multiple references to the same memory.) But the Rust borrow checker just sees a succession of accesses into a list, and it has no way of knowing that the indexes are all different. If the human writing the code has knowledge that all of the indexes are different, though, they can use an unsafe pattern called lifetime extension to tell the borrow checker to let this code through: In the previous section, we saw how unsafe Rust acts as an escape hatch for facts that the Rust compiler cannot establish by itself—in this case, that the indexes returned by are all different. But are the indexes actually different ? Based on the storage scheme described above, it would seem like that is the case. But this is generic code which calls into user-provided functions, so there’s a chance that sufficiently pathological user code can trick the map into storing duplicate indexes. Let’s take one such example we recently found and fixed. Suppose you have an called storing five items with integer keys 0 through 4, inserted and stored in order. Here, the top row is the B-tree storing indexes in key order, while the bottom row is the : Now suppose you use the Entry API (a standard Rust data structure pattern) to fetch an item by index 0: This will successfully look up the item stored at index 0 and return an . The internally stores the fact that the item was found at index 0. Now, at this point, let’s deliberately switch the implementation for to always return , no matter the values inside. There are a few different ways to do this in safe Rust, most of which use some form of interior mutability . (This is unlikely in ordinary Rust, but that doesn’t matter : unsafe generic Rust must handle arbitrarily pathological Rust!) Now remove the entry from the map using : At this point, would attempt to remove index 0 from the B-tree, descending into the tree again but comparing only by key 7 . Because we made comparisons by key always return , the comparison would short-circuit at the first element it compares against. For example, if the first comparison lands on the B-tree entry , then that entry would be removed. But the was carrying , so it would also remove item 0 from the item set: The map is no longer in a consistent state. The index 0 is still in the B-tree index but the corresponding slot in the is vacant; meanwhile, item 2 in the does not have any pointers to it. At this point, though, the invariant that there aren’t duplicate indexes hasn’t been violated. Where it does get violated is with this next step: suppose the implementation now switches back to being honest 8 , and you insert a new entry with key 1000. Since points to item 0, will attempt to reuse that slot. It is this step that results in duplicate indexes: There are now duplicate indexes pointing to the same item, and becomes unsound. This was fixed through a combination of two things: When descending into the B-tree, also check equality against the index. In other words, if we’re looking for a key with a known index in the B-tree, compare against both and . As covered in the example above, previously, we would just check that the key is the same; the pathological implementation returned , tricking the map into believing that the entry at was the one to remove. We changed this to additionally use the index as a tie-breaker. The comparison against now resolves to (since ), so the search doesn’t spuriously match here. By construction, the only way the search can now succeed is if the stored index actually equals the one we’re looking for. If there are no matches, fall back to a linear scan. The tie-breaker eliminates spurious matches on the wrong entry, but it doesn’t guarantee that the search finds the right entry. (The B-tree is sorted by key , while the tie-breaker compares by index , and in general these two orderings are independent.) If the tree search yields no results, we must still keep the tree and the in sync. In that case, we remove the index from the B-tree by doing a linear scan without calling into user code. The remove operation then takes linear rather than logarithmic time, but that is an acceptable tradeoff, since buggy user code is the only way to encounter the fallback. This is the kind of long-range reasoning that is sometimes required to establish the soundness of a safe abstraction. The overall system relies on all of these moving parts working correctly across arbitrarily complex series of operations. Because is such a foundational data structure at Oxide, we go through great lengths to validate its correctness, including the soundness of its abstractions. There is a great deal of analytical reasoning performed by experienced Rust authors and reviewers, as described in the section above. But we also empirically validate along several different dimensions. None of the layers is sufficient by itself, but by rigorously doing all of them we can be more confident that is correct. The layers of validation we apply are: In this section, I’ll provide a brief overview of each layer. Click through the links to see more details and code samples. All blocks and patterns of unsafe Rust have been analyzed by at least one human reviewer, and up to three. Thanks to several of my Oxide colleagues for lending their time and expertise to these reviews—these discussions helped sharpen our reasoning considerably. The reasoning for each unsafe block is captured in a comment above the block. We use Clippy’s lint to verify that these comments are present. The simplest kind of empirical validation is with example-based tests : create a map, perform some operations, and ensure that the results of those operations are as expected. has unit tests for its internals and integration tests for the public API . These also live as doctests, where they double as documentation. also has a battery of pathological tests which supply buggy implementations of and other traits. In CI, both regular and pathological tests are run under the Miri interpreter , which can detect many classes of undefined behavior. (If you’re curious about the details, we run with Miri under both Stacked and Tree Borrows .) But note that some classes of UB can be detected in the regular test environment as well. For example, in the previous section we established that the tables not containing duplicate indexes is a necessary condition for soundness; this invariant can be verified outside the Miri context as well. uses two layers of randomized testing: model-based comparison against a known-correct oracle, and fault injection on top of it. For data structures, example-based tests alone are generally considered insufficient. A much stronger kind of testing is model-based testing , also known as stateful property-based testing (stateful PBT): random sequences of operations are applied to an instance of the type, and the results are compared against an oracle that is known to be correct. has extensive model-based tests against a oracle that is inefficient but clearly correct. (I’ve talked about this style of testing before on Oxide and Friends .) An extension of model-based testing is fault injection , where bugs are randomly inserted into user code. For , a fruitful avenue for fault injection has been panic safety (or unwind safety ): user code panicking in the middle of an operation must not cause the map’s invariants to be violated 9 . We systematically explore fault injection by generating random sequences of map operations, where each operation is associated with a (randomly selected) panic countdown. Each call into user code decrements the countdown by 1; if it reaches 0, the code panics. Randomized panic safety testing found several subtle bugs in ( example ), including some that escalated into unsoundness. The model-based tests also verify internal invariants after each operation, such as the no-duplicate-index condition described in the previous section. We’ve found in practice that model-based tests are too slow to run under Miri, so we verify the invariants on which soundness (and correctness) is known to be dependent instead. Another kind of validation that’s recently become available is LLM-driven adversarial review . Current-generation frontier models 10 found several ways to write pathological implementations of user code that would corrupt the map. In one notable case , an LLM constructed a way for the map’s invariants to break on a custom allocator panicking and unwinding. This is a panic safety issue (and a failure mode I hadn’t thought about before), but distinct from the existing panic safety tests that only covered panics in regular user code like an implementation. LLMs can sometimes produce plausible-but-wrong soundness claims. An effective way to guard against that is red-green TDD , using Miri as an oracle: For a soundness bug, first have the LLM write a test case demonstrating the bug, running it under Miri to show undefined behavior—the red phase. Then, after fixing the bug, rerun the test to show that it now passes—the green phase. To formally verify , one’s first thought would be to use a model checker like Kani to establish that the maps don’t violate internal invariants. But is unfortunately a bit too complicated for Kani to handle, and the required proofs blow up beyond what is feasible for the tool. The Creusot deductive verifier can help Rust developers prove their code is free of panics and other errors, but as of this writing it’s unable to prove invariants that must hold even if user code panics or otherwise misbehaves. The infeasibility of proofs is a common problem with applying formal methods to implementations, so they are often applied to a higher-level specification instead. For , the closest thing to a specification is , but it can be easily observed to be correct without needing a formal proof. How do we ensure that the implementation matches the specification? Model-based testing does a lot of heavy lifting here. While they aren’t a formal proof that matches , running model-based tests thousands of times in CI provides fairly high confidence that it does. We keep an eye on developments in this space; the in-development , which lets you embed Lean soundness proofs alongside unsafe Rust as doc comments, looks quite interesting. If you’re working on formal verification tooling, is a great candidate to benchmark against because of its crisp invariants and relatively constrained yet non-trivial scope. We’d be especially interested in proofs that hold over arbitrary trait implementations, and of refinement between and . Please reach out by filing an issue or emailing me ! Writing unsafe generic Rust is extremely difficult. Each invariant that the unsafe code relies upon has to be carefully upheld over arbitrary trait implementations, including adversarial ones. This post covers one such example: how an implementation could be carefully written to trick the map into creating mutable aliases to the same memory, and how we fixed it. No single technique can hope to catch all bugs, which is why uses several layers of validation. Humans carefully reasoning about every line of unsafe code goes a long way; example-based, pathological, and randomized tests provide empirical evidence; and frontier models can find new and surprising ways to break code that humans might not have thought of. This is a lot of machinery, but at Oxide we believe that for foundational infrastructure, this level of rigor is justified. And if you agree, we’re hiring ! Diagrams courtesy Ben Leonard. Discuss on Hacker News and Lobsters . also supports integer keys; it serializes and deserializes them as strings. ↩︎ In C, the aliasing rules are about accesses : multiple pointers to the same memory are fine, as long as you don’t have a data race on them or violate strict aliasing . In Rust, it is UB for multiple references to the same memory to ever exist , even if they’re not actively being mutated simultaneously. ↩︎ An exercise for the reader. There is a second, entirely different, kind of bug in : it can leak memory with some user-supplied iterators. This isn’t a soundness bug, but it is a bug nonetheless. Try working out how this can happen and why this isn’t a soundness bug. (Hint: think about user code panicking.) ↩︎ For this discussion we’re restricting ourselves to single-threaded Rust, since iddqd is not a concurrent data structure. Concurrency amplifies the difficulty of reasoning about Rust several-fold further. ↩︎ The index is built on top of the standard library . This required making work with an external comparator through some further unsafe trickery. ↩︎ For a proposed version of an iterator which does let you borrow values from the iterator, see . ↩︎ Is this second descent necessary? ’s own stores a cursor into the map to avoid a second descent, and could be restructured to hold one. But there are other ways to trigger the same issue without using , for example by using a chaotic implementation that randomly returns at times. I’m using here as the clearest way to demonstrate the bug. ↩︎ Restoring is necessary here because, with , the duplicate-detection step at the start of would short-circuit and reject the insert. The point is that user code is free to misbehave in arbitrary ways, including changing its mind from one call to the next. ↩︎ Rust binaries can be configured to either unwind (be recovered from ) or abort (tear down the process). Panic safety only matters with . At Oxide, we ship our system software with . However, libraries cannot assume and must work with . ↩︎ Claude Opus 4.7 and GPT-5.5. ↩︎ First-class support for complex keys that borrow from more than one field, without having to resort to workarounds like dynamic dispatch . Maps with two or three keys per item, each independently indexing the same record, without the usual pattern of maintaining multiple maps by hand. Serde implementations that serialize as sequences rather than maps, so that non-string keys can be serialized in JSON 1 . Importantly, these implementations reject duplicate keys. (For backwards compatibility, serialization as maps is also supported .) There are no data races. There must be no reads of uninitialized or freed memory. There must not ever be multiple aliases of references to the same region of memory. Immutable data must not be mutated. that the function was provided a , and not, for example, a the ensuring that is in bounds the fact that is , and not, for example, an , which (similar to the crate ) internally has: a , where is an enum with two variants: (where represents an integer index into the ) a , which points to either the most recently freed slot, or is a sentinel (marked as in the diagrams below) indicating that no free vacant slots are available. (The combination of and the slots forms a free chain .) a over ( is the fast hash table implementation used by the standard library) follows a similar structure, except the hash table is replaced with a B-tree index 5 . and store two and three hash tables respectively. When descending into the B-tree, also check equality against the index. In other words, if we’re looking for a key with a known index in the B-tree, compare against both and . As covered in the example above, previously, we would just check that the key is the same; the pathological implementation returned , tricking the map into believing that the entry at was the one to remove. We changed this to additionally use the index as a tie-breaker. The comparison against now resolves to (since ), so the search doesn’t spuriously match here. By construction, the only way the search can now succeed is if the stored index actually equals the one we’re looking for. If there are no matches, fall back to a linear scan. The tie-breaker eliminates spurious matches on the wrong entry, but it doesn’t guarantee that the search finds the right entry. (The B-tree is sorted by key , while the tie-breaker compares by index , and in general these two orderings are independent.) If the tree search yields no results, we must still keep the tree and the in sync. In that case, we remove the index from the B-tree by doing a linear scan without calling into user code. The remove operation then takes linear rather than logarithmic time, but that is an acceptable tradeoff, since buggy user code is the only way to encounter the fallback. also supports integer keys; it serializes and deserializes them as strings. ↩︎ In C, the aliasing rules are about accesses : multiple pointers to the same memory are fine, as long as you don’t have a data race on them or violate strict aliasing . In Rust, it is UB for multiple references to the same memory to ever exist , even if they’re not actively being mutated simultaneously. ↩︎ An exercise for the reader. There is a second, entirely different, kind of bug in : it can leak memory with some user-supplied iterators. This isn’t a soundness bug, but it is a bug nonetheless. Try working out how this can happen and why this isn’t a soundness bug. (Hint: think about user code panicking.) ↩︎ For this discussion we’re restricting ourselves to single-threaded Rust, since iddqd is not a concurrent data structure. Concurrency amplifies the difficulty of reasoning about Rust several-fold further. ↩︎ The index is built on top of the standard library . This required making work with an external comparator through some further unsafe trickery. ↩︎ For a proposed version of an iterator which does let you borrow values from the iterator, see . ↩︎ Is this second descent necessary? ’s own stores a cursor into the map to avoid a second descent, and could be restructured to hold one. But there are other ways to trigger the same issue without using , for example by using a chaotic implementation that randomly returns at times. I’m using here as the clearest way to demonstrate the bug. ↩︎ Restoring is necessary here because, with , the duplicate-detection step at the start of would short-circuit and reject the insert. The point is that user code is free to misbehave in arbitrary ways, including changing its mind from one call to the next. ↩︎ Rust binaries can be configured to either unwind (be recovered from ) or abort (tear down the process). Panic safety only matters with . At Oxide, we ship our system software with . However, libraries cannot assume and must work with . ↩︎ Claude Opus 4.7 and GPT-5.5. ↩︎
Performance
Database
Testing
Ruby
DevOps
Cloud
Programming
Python
Hardware
JSON
Data Analysis
Open Source
Data
HTML
Web Development
CSS
C
Data Visualization
Frontend
Rust
Tutorial