Iddqd, or the hardest kind of unsafe Rust
7 hours ago
- #rust
- #data-structures
- #unsafe-code
- iddqd is a Rust library for maps where keys are borrowed from values, used extensively at Oxide in Omicron for in-memory indexing.
- It solves the problem of storing keys separately from values in standard maps by allowing keys to be extracted from values via a trait, avoiding duplication or synchronization issues.
- The library features complex key borrowing, multiple indexes per record, and safe Serde serialization with duplicate key rejection.
- Unsafe Rust in iddqd is justified as an escape hatch for correct programs rejected by the compiler, but requires sound abstractions to prevent undefined behavior.
- Key challenges include reasoning about safe Rust invariants, module-wide correctness, and adversarial user code in generic contexts.
- Internally, iddqd uses an ItemSet (a Vec of slots) and indexes (hash or B-tree) to manage items, with efficient insertion and removal via free lists.
- Unsafe patterns like lifetime extension are used for mutable iteration, ensuring disjoint mutable references without borrow checker limitations.
- A bug involving pathological Ord implementations causing duplicate indexes was fixed by adding index tie-breaking and fallback linear scans.
- Validation includes analytical reasoning, example-based tests, Miri pathological tests, model-based testing with fault injection, and LLM adversarial review.
- Formal methods are currently infeasible, but model-based testing provides high confidence, and the library is open for use and collaboration.