A C status code returned as i32 (zlib’s Z_OK, Z_STREAM_END, Z_NEED_DICT, Z_BUF_ERROR, …) and compared by every caller; a mode passed as an i32 constant (Z_FINISH) |
Result<Status, Error>: the Ok carries the non-error statuses (Result<(), Error> when success is only Z_OK), the Err a typed error enum; each type has code() for the C value, and the Z_* constants stay as those values; the mode is an enum (Flush) with its own code() (sys/lib/libz/zlib.rs) |
? and match replace the comparisons; an error cannot be mistaken for progress, and an out-of-range mode cannot be built. Callers that keep a status integer of their own (libsa’s cread) take .code() |
A hash or MAC context struct and C-named free functions over it: X_Init(&mut ctx), X_Update(&mut ctx, data), X_Final(&mut out, &mut ctx) (MD5Init, SHA256Final, SipHash24_End, blake2s_final) |
A type with methods: XCtx::new() (or new(key) for a keyed one) is Init, update(&mut self, &[u8]) is Update, finalize(&mut self) -> [u8; N] is Final and returns the digest; finalize wipes the context in place where the C does explicit_bzero(ctx), so it takes &mut self, not self (a by-value self would wipe a copy). Default is the wiped state, not a started hash (sys/crypto/md5.rs). Every hash or keyed context is not Copy (it stays Clone for a caller that forks a prefixed hash) and its impl Drop runs the zeroize that finalize runs too, field by field through crate::crypto::wipe and explicit_bzero (a Drop cannot wipe(self): the assignment drops the old value and would recurse); its tests assert the missing Copy at compile time with assert_not_copy! (sys/crypto/testutil.rs, an ambiguous impl, since stable Rust has no negative bound). A parameter the C passes on every call but fixes per use becomes a const parameter of the type (SipHash’s round counts: SiphashCtx<C, D>, sys/crypto/siphash.rs; BLAKE2s’s digest length: Blake2sState<N>, whose range check is a const assertion) |
The context cannot be updated before it is started or used across two algorithms, the digest is a value instead of an out parameter whose length must match, and a context cannot change its fixed parameters midway; no by-value pass or early drop leaves an unwiped copy of the state, which for SipHash, a keyed BLAKE2s and Idgen32 is key-derived (a move still can, as the row below says) |
A run-time key kept in Cell<Key> (Cell<SiphashKey>: pf’s SYN-cookie secrets, WireGuard’s peer-table and rate-limit secrets, the inpcb hash keys, udf’s node hash key) and copied out with get() onto the stack for every hash, never wiped; the key type Copy |
the key type is not Copy and wipes itself in Drop (SiphashKey); a key that several CPUs read while one replaces it is its stored words in atomics behind a type of the crypto module (AtomicSiphashKey, sys/crypto/siphash.rs) that starts the hash from the words (siphash24(), hash24(src), through SiphashCtx::with_key_words) and is replaced in place (store, store_bytes); a key behind a lock or written once at boot stays a SiphashKey used by reference |
No key value is gathered on the stack per use, a replaced key is overwritten in its only storage, and the race the C has between a key being rewritten and a reader on another CPU (a wrong hash) stays a defined race instead of a data race on a Cell; no unsafe, and the owner’s struct loses an unsafe impl Sync when the key was its last non-Sync part |
A key schedule in a Copy struct ([u32; 32], AesCtx, …), wiped only when the framework explicit_bzeros the session |
the schedule’s own type, built by its constructor and impl Drop zeroing its words through crate::crypto::wipe (so it is not Copy); scratch secrets are still wiped where the C wipes them |
The key cannot outlive its owner on any path (an early return, a replaced Kschedule, a freed session), without new unsafe; the stores go through black_box, so the optimizer keeps them. A move can leave a copy on the stack, as the C’s by-value copies do |
Cell<*const T> (struct type *) and Cell<*const Cell<*const T>> (struct type **) in a queue.h/tree.h entry or head, each read through its own unsafe { p.as_ref() } with “a linked element is valid” as its comment, NULL checked by hand or not at all |
a typed intrusive link: a private type, Link<P> = Cell<Option<NonNull<P>>> (None is NULL), whose fields only the module’s mutators write, from references, so a link carries the element’s provenance; its invariant (a link of a head or of a linked element is None or names a live object) is stated once on the type and the dereference lives in one function (Link::target, sys/sys/queue.rs; splay_follow, sys/sys/tree.rs), whose SAFETY: is that invariant, kept by the unsafe mutators’ contract (linked elements stay valid and in place); the algorithms are safe code on &Elem. The _FOREACH_SAFE walks share one cursor that holds the pending position as NonNull; tree.rs leaves a removed element holding no links, so readers stay safe on it. What the C turns into a NULL dereference is a None arm that panics (the panic row below). The drain while ((e = TAILQ_FIRST(h))) TAILQ_REMOVE(h, e, f) is one safe call, TailqHead::pop_head (N3.2), whose single unsafe removal is of the element the head names, so its precondition is the link invariant itself and no drain writes unsafe at its call site (sys/uvm/uvm_km.rs’s page lists) |
One soundness argument instead of one per read (queue.rs: 49 unsafe blocks to 6), and the null case cannot be forgotten: an absent link is None, matched instead of compared; same size and auto traits as the raw pointer, so the structures that embed the entries do not change |
container_of from a pointer taken from a field reference (&elem.entry.next as *const _, stored as the C’s tqh_last/tqe_prev), stepping back with unsafe pointer arithmetic |
the stored back pointer is made with the whole element’s provenance (NonNull::from(elem).with_addr(field.addr()), link_of), the step back is safe wrapping_byte_sub by the adapter’s offset plus the field’s (container_of), and only the dereference of the result is unsafe (sys/sys/queue.rs) |
A pointer derived from a field reference may not reach the rest of the element; with the element’s provenance it may, and the arithmetic needs no unsafe |
An unsafe trait Adapter whose contract (OFFSET is the offset of the field entry returns) each implementer vouches for with an unsafe impl, written by queue_adapter! at every invoking site |
A safe trait (sys/sys/queue.rs) whose contract is kept by construction and checked by tools: only queue_adapter! (and tree_adapter!, through it) implements it, computing OFFSET with offset_of! of the very field entry projects; the macro checks at compile time that the field’s type is exactly the entry type (let _: *const $entry = addr_of!(elem.$field);: a raw pointer never deref-coerces, so a Box or reference field is refused, a compile_fail doctest proves it); cargo xtask lz check refuses a hand-written impl, a rename of the trait and an impl whose trait is a macro variable. The core’s SAFETY: arguments that rely on it cite this “adapter premise” |
Under #[forbid(unsafe_code)] an unsafe impl expanded from a macro is refused in the invoking module (docs/ZERO_UNSAFE.md, section 3), so every module that declares a list or a tree could not be forbid. The one place where a CI check over the source, a tripwire rather than a proof, upholds a premise of the core’s soundness; a reviewer still refuses any other way around it (decision 7) |
A pointer stored as an integer and turned back (p as usize, (cookie ^ v) as *const T: XSIMPLEQ_XOR) |
p.expose_provenance() to encode and ptr::with_exposed_provenance(_mut) to decode (sys/sys/queue.rs) |
Rust’s explicit API for the round trip: the decoded pointer is one the compiler allows to be dereferenced, and the intent shows |
A C algorithm over raw links (struct rb_entry *) ported as *const Entry locals, an unsafe fn e(p) -> &Entry and an unsafe block per step; a generic root that any rb_type may walk; the mirrored left/right halves written twice |
A typed handle, RbNode<'a, T> (sys/kern/subr_tree.rs): a Copy wrapper of the link, typed by the tree’s RbType, made only from the element’s own entry (address arithmetic by map_addr, which keeps the element’s provenance) or from a link read out of a tree of the same type; its accessors (left, parent, set_child, color, …) are safe, and the module’s two dereferences (RbNode::entry, rb_e2n) carry the soundness argument. The root is RbTree<T>, typed by its RbType; the mirrored halves are one path over a Side |
The algorithm becomes safe code with the C’s control flow; a link of one tree cannot be read with another type’s offset; a missing node the C would dereference as null is a None the code must handle (here, a panic naming the broken structure) |
A broken precondition that the C turns into a fault or silent corruption (a NULL dereference in TAILQ_REMOVE, SIMPLEQ_REMOVE_HEAD of an empty queue; a null child in a rotation, a poison value followed, a tree element removed twice or never inserted, which empties the tree), mirrored in LZ by dereferencing the raw pointer |
an Option match or a checked link whose failure calls a #[cold] module function that is panic(9) in the kernel and std::panic! under cfg(test) (queue_panic, sys/sys/queue.rs; rb_panic, sys/kern/subr_tree.rs), in every configuration, with a message naming the operation or the broken structure; #[should_panic(expected = ...)] tests cover each case |
The fault stays a fault, with a message instead of a trap, deterministic, and never becomes a silent no-op; the host’s panic(9) ends the test process (boot exits), so the test build unwinds and #[should_panic] can test each case |
A global written once at boot and read afterwards (a function table, a console, an attachment), spelled StaticCell<T> whose every access is unsafe and names the boot phase that excludes a writer |
hal::once::OnceStatic<T>: set(v) -> Result<(), T> succeeds once and hands a later value back, get() -> Option<&T> is None before the set; one atomic state byte (EMPTY, BUSY, READY) orders the one write before every read; each reader decides, as a type, what “before set” means (sys/hal/once.rs) |
The phase the StaticCell caller promised is checked instead, and no caller writes unsafe; StaticCell stays in libkern for the legacy tree (hal depends on libkern) and its uses move with their subsystems |
A direct call from new code into a subsystem that has not moved yet (splraise, curcpu(), tsleep, km_alloc, malloc, pool_get, copyin), which would make hal or kernel depend on bsd |
a bridge: a trait declared beside its caller (hal::intr::IntrLevel, hal::cpu::CpuId, …), one private OnceStatic<&'static dyn Trait> slot in sys/hal/bridges.rs with a register_* function bsd’s main() calls once, a crate-private reader that answers None before registration, and a row of bridges.toml (trait, for, paid_by); each primitive documents its behaviour without the bridge (no interrupts yet, one boot CPU, …), never a panic in a hot path |
The dependency arrows go down only (docs/ZERO_UNSAFE.md 0.1); what goes up is a registration, audited in one file and counted in one table that must be empty at N9; a bridge has no logic, so it moves without a behaviour change |
s = splraise(ipl); ...; splx(s) (and splnet(), splbio(), …), the restore written by hand on every path out |
hal::intr::splraise(ipl) -> SplGuard, whose drop is splx of the level it replaced; not Send (sys/hal/intr.rs); the raw pair stays crate-private for the locks that keep the old level in the lock (mtx_oldipl) |
No path can leave the level raised, and the guard cannot be dropped on another CPU |
struct mutex and free functions (mtx_enter(&m) … mtx_leave(&m)), the protected fields Cells beside the lock, every access trusting the caller to hold it |
hal::mutex::Mutexed<T>: the lock owns its data; lock() is mtx_enter (level raised, owner word swapped, spins counted) and returns a MutexedGuard through which alone the data is reached (Deref/DerefMut), its drop is mtx_leave; not Send; try_lock() is mtx_enter_try; guard.sleep_nsec(ident, prio, wmesg, nsecs) is msleep_nsec on &mut self, the mutex entered again on return (N3.4a); the owner word is never 0, so exclusion rests on the compare-and-swap alone (sys/hal/mutex.rs) |
The guard is the proof of the lock: an access without it does not compile, a path out cannot forget the leave, and the protected data needs no Cell; the legacy Mutex stays for its 129 files (decision 8) |
struct cpumem handles to ncpusfound pool or malloc allocations reached by raw pointer (cpumem_enter -> NonNull<u8>, cast by each user); counters_* over *mut u64 |
hal::percpu::PerCpu<T>: MAXCPUS cache-line aligned slots of T by value, get() the running CPU’s (&T), iter() the ncpusfound copies; a const fn new() for T: PerCpuInit (atomics), so a static needs no boot allocation; Counters<N> keeps the C’s generation protocol under MULTIPROCESSOR and read() returns the sums (sys/hal/percpu.rs) |
No allocation and no cast: the per-CPU discipline is T’s own interior mutability, and the type is Sync exactly when T is; the price is MAXCPUS slots, so an instance never lives on a kernel stack |
struct rwlock with free functions (rw_enter_write(&l) … rw_exit_write(&l)), the protected fields Cells or raw pointers beside it, rw_assert_wrlock where the C asserts, and rwsleep_nsec(ident, &l, ...) re-entering the lock behind the caller’s back |
hal::rwlock::Rwlocked<T>: write()/read() (and write_flags/read_flags with RW_NOSLEEP/RW_INTR, try_*) return a WriteGuard (&mut T) or ReadGuard (&T) whose drop is the exit; guard.sleep_nsec(ident, prio, wmesg, nsecs) is rwsleep on &mut self, the lock held again on return whatever the sleep said; guard.unlocked(f) runs a copy that may fault with the lock released; downgrade/try_upgrade consume the guard; the C’s waits, priorities, writer preference and wakeups are kept (sys/hal/rwlock.rs) |
No reference into the data lives across a sleep or an unlock (the borrow checker sees the &mut self), the assertions are types, and a writer’s exit compares the word it stored, so exclusion never rests on the Sleep bridge; the legacy Rwlock stays for its 72 files (decision 8) |
pool_get(pp, flags) cast to the type and initialised by hand, handed out as &'static T (pipe_pair_create), pool_put wherever the owner decides |
hal::pool::TypedPool<T>: one pool(9) per type (so vmstat -m lists it), init(ipl, flags, wchan); get_shared(flags, init) -> Option<PoolArc<T>> writes the value before any handle exists; PoolArc<T> is an owned counted handle (Clone +1, Deref<Target = T>, the last drop drops the T and puts the item back); no &'static T of an item that can be freed and no raw form; PoolArc::get_mut while the handle is the only one, PoolArc::leak to give a handle up for good (an item never freed, N3.4a); a pool whose values records reach by address (init_recorded, the pmaps) never gives one mutably (sys/hal/pool.rs) |
Decision 10: a reference borrows a handle, so a use after free or a double put cannot be written; the pool behind it is still the C’s, through the PoolBackend bridge |
km_alloc(len, &kv_any, &kp_pageable, &kd_waitok) kept as a void * and a size beside it, km_free with the same modes on every path, slices over it in unsafe blocks (pipe_buffer) |
hal::kmbuf::KmBuf: owns the pages, Deref/DerefMut<Target = [u8]>, moves like a value (out of a lock while a copy that may fault runs, then back, decision 11), its drop is the km_free with the modes it was made with (alloc_pageable(mem, len), alloc_wired(mem, len, wait), the page provider passed as a value and kept in the buffer) (sys/hal/kmbuf.rs) |
The pointer, the size and the modes cannot disagree or leak, and the bytes are a slice; the pages are the provider’s, the kernel’s vm::km since N3.2 (no registered slot) |
New code trusting the kernel’s allocators silently (km_alloc, pool_get, malloc used as raw pointers at every caller) |
a safe memory bridge (PoolBackend/RawPool, Malloc; PageMemory until N3.2, now a provider passed as a value under the same contract) returning a block and the size granted; the trust is the boot registration contract (registered once by the kernel’s boot path with its own allocator, before any user; sys/hal/bridges.rs), named in the // SAFETY: of every hal site that makes a reference of a block, and every answer goes through trust::check_block (aligned, size covers the request, a write-and-read-back probe under diagnostic; a failure is panic(9) naming the bridge) (sys/hal/trust.rs) |
Decision 30 (the user rejected unsafe impls in bsd): bsd registers with no unsafe, hal’s API stays safe, and the trust is one documented boundary with runtime checks, not a compile-time proof, that goes with the bridges (N3, N9) |
p = malloc(sizeof(*p), M_KEVENT, M_WAITOK) … free(p, M_KEVENT, sizeof(*p)), the type and the size repeated at both ends, or a Rust Box (the global allocator’s M_TEMP, M_NOWAIT) |
hal::malloc::MBox<T>: MBox::new(ty, flags, value) -> Option<MBox<T>> with the C’s malloc type and M_WAITOK/M_NOWAIT/M_CANFAIL (None only where the C’s malloc returns NULL), Deref/DerefMut, the drop drops the T and frees with the same type and size; a type malloc cannot align, or a zero-sized one, refused at compile time (sys/hal/malloc.rs) |
Decision 19: vmstat -m counts the block in the C’s row and M_WAITOK sleeps where the C sleeps; the two ends cannot disagree |
copyin(uaddr, &obj, sizeof(obj)) with a usize address, over an unsafe trait AbiPod vouched for by an unsafe impl per type (about 200, sys/machine/copy.rs) |
hal::user::UserPtr<T>: a user address typed by what it points at; copyin() -> Result<T, Errno>, copyout(&T), the _slice forms for arrays, copyinstr/copyoutstr on UserPtr<u8>; AbiPod is a safe trait written only by abi_pod!(Type { field: Type, ... }), which checks at compile time each field’s exact type, that each is AbiPod, and that the fields in order tile the type with no padding and none left out (sys/hal/user.rs) |
Decision 17: the byte view’s one unsafe lives in hal and rests on a compiler-checked premise (and lz check refusing other impls, as for Adapter), so the kernel and the ABI module copy structures with no unsafe; the size is the type’s |
An LZ module reached at its old crate:: path (crate::arch::amd64::include::frame, crate::machine::param) |
Moved into hal (sys/hal/arch/, sys/hal/machine/, sys/hal/sys/) as an inherited module, code untouched; the old parent mod.rs keeps the name with pub use hal::...; |
The hardware lives in the one crate with unsafe, and the generic modules and the remaining arch files keep their paths; a re-export is a rename-free move. An inherent impl on a moved type can no longer be written in bsd (orphan rule): none existed. |
A lower layer that calls an upper one by name: each arch trap picks sysent[code] and calls mi_syscall itself (sys/arch/amd64/amd64/trap.rs syscall, sys/arch/arm64/arm64/syscall.rs svc_handler) |
A two-way registration through hal: the call goes down to one hal dispatch point (hal::syscall::dispatch), and whoever answers it registered there at boot, going up only as a registration: bsd’s main registers the Legacy fallback (set_legacy), the module registers its handler through KernelApi (set_handler); each is an init-once cell, a second registration is refused and handed back, and the dispatch is a pure choice (route: the handler, else the fallback, else ENOSYS) with host tests (sys/hal/syscall.rs) |
The dependencies stay one way (bsd -> kernel -> hal, abi -> kernel): nothing below names what is above it, yet the trap reaches the module and the module reaches bsd’s table; a handler can never change under a running system call |
The kernel’s entry points reached by name from anywhere in the one binary (sys_* through sysent[], copyin from sys/machine/copy.rs), every caller linked against every callee |
A vtable handed at load: KernelApi (sys/hal/api.rs, below both sides, so the module names it with no dependency on the kernel crate; kernel::api::table fills it), #[repr(C)], its version and size first (ApiPrefix), Rust-ABI fn pointers over slices and Results (both sides are built by the one pinned toolchain from the one tree); bsd fills it today with the functions that answer (KernelApi::new), an entry moves to a kernel function when its subsystem moves; the module receives it as the argument of abi_init and of every call, so it keeps no state; the module’s header (AbiModuleHeader, magic, version, size, entry) is checked by the loader before the first call |
The module links no kernel code and no hal state, so it is a separate ELF file (decision 22); everything the kernel offers it is one reviewed table, and a module built against another table is refused at boot instead of misbehaving |
A file format read by casting the buffer to the header’s struct ((Elf_Ehdr *)buf, libsa’s loadfile_elf reading Elf64_Phdr arrays in place) |
The format’s structures declared #[repr(C)] as the specification lays them out, their sizes pinned by a compile-time check, and each read from the bytes field by field (from_le_bytes at a checked offset, the whole structure’s range checked first) into an owned value (Elf64Ehdr::read, sys/hal/module/elf.rs); what the loader accepts is then checked as a whole (Module::parse: machine, page-aligned W^X loads, no interpreter or TLS, no import, RELATIVE relocations only) and a refusal is a typed error naming what was wrong |
No unsafe, no alignment assumption, no out-of-bounds read on a short or lying file (a test parses every truncation of a fixture); the #[repr(C)] declaration still documents the layout the specification fixes |
A kernel object that embeds a structure of a subsystem still in bsd (struct pipe’s struct klist and struct sigio_ref) and calls its functions by name (knote_locked, pgsigio) |
The kernel type is generic over a glue trait the kernel declares (PipePair<G: PipeGlue>, sys/kernel/pipe.rs): G is one value per object inside it, made by PipeGlue::new() -> Result<Self, Errno> as the C sets it up (ENOMEM when the glue’s part cannot be had), and its methods are the calls the C makes (one call into bsd each, a bridge of bridges.toml); bsd instantiates the type once over its own glue (Pipes<BsdPipeGlue>) |
The kernel names nothing of bsd, the embedded structure stays where the C has it (no cast, no registry slot, no indirection: the compiler emits the concrete code), and the glue goes when its subsystem moves |
Fields the C guards with the object’s lock but that are also read where no guard can be passed (a filter called back by kqueue under the lock its caller holds, kern_sysctl’s unlocked read of pipe_state) |
Those words only are atomics beside the lock-owning state (Pipe::state, peer_alive, cnt, size, sys/kernel/pipe.rs), stored only through setters that take the write guard as their witness (fn set(&self, _w: &mut WriteGuard<'_, PairState>, ..)); everything else stays inside Rwlocked<T> |
The writers are still serialised by the lock, and a reader that the lock covers but cannot hold a guard sees the same values as the C, without unsafe and without a second copy of the state (decision 12) |
A pool item shared by two owners that each destroy their half (pipe_destroy twice, the second also pipe_pair_destroy), reached by raw pointers, the destroy an unsafe fn taking NonNull |
One owned, non-Clone handle per half (PipeEnd<G>: a PoolArc of the pair and which half), whose drop is that half’s destroy; the item goes back to the pool with the last handle (PoolArc), the C’s final destroy is the item’s Drop (sys/kernel/pipe.rs) |
Each half is destroyed exactly once and the item freed exactly once, on every path (the error paths of pipe_pair_create and dopipe included), and a use after free cannot be written |
A file’s object behind the type-erased f_data (Cell<*mut c_void>), cast back to &Pipe by fp_pipe in an unsafe block |
A typed slot beside it for the one type that moved into the kernel crate (File::f_pipe: Mutexed<Option<PipeFile>>, sys/sys/file.rs): set once by dopipe, read by cloning the pair’s PoolArc and its Dir under the mutex (never sleeping or calling into the pair there), taken by fo_close, which drops it after releasing the mutex; f_data stays null for it (sys/kern/pipe_glue.rs) |
No cast and no unsafe; the other DTYPEs keep f_data untouched; the cost (one uncontended mutex and one atomic per operation) goes at N4 with FileData (decision 14) |
kn_hook set to the object a knote is hooked on (kn->kn_hook = wpipe) and cast back in f_detach (kn_pipe) |
kn_hook holds a small index (the Dir of the pipe whose klist holds the knote) as an address without provenance (ptr::without_provenance_mut(dir.index())), read back with .addr(); the object comes from the knote’s file (sys/kern/pipe_glue.rs) |
Nothing is ever dereferenced from the hook, so it needs no unsafe and cannot dangle |
A legacy structure embedded in a kernel object (struct klist, struct sigio_ref in struct pipe) when the legacy type is Sync but not Send and the object is a PoolArc (whose value must be Send) |
The glue allocates the legacy part itself (Vec::try_reserve_exact + leak, never the allocator’s panic), holds it as a &'static (which is Send because the target is Sync), and recycles it through a Mutexed<Vec<&'static T>> free list instead of freeing it (PipeKlists, sys/kern/pipe_glue.rs) |
No unsafe impl Send in bsd (decision 30’s pattern, refused); the cost, stated in the module’s deviations, is memory kept at the peak and counted under M_TEMP; it goes when the legacy type is the kernel’s (N4) |
A page-table page reached by a raw pointer (the recursive mapping’s kvtopte, pde_at/pde_set through the direct map), each entry written in its own unsafe block |
A table the kernel owns is a typed static of atomics, #[repr(C, align(4096))] struct Ptp([AtomicU64; NPDPG]) in .bss, written with safe atomic stores and compare-exchanges, the MMU reading it by the physical address pmap_extract gives; only the view of a table the boot loader built stays unsafe, one block (the module window, sys/hal/arch/amd64/pmap/window.rs) |
Ownership first: memory that is ours is a Rust object, so its entries need no pointer and no unsafe; the .bss is mapped, zeroed and outside uvm on both boot paths before pmap_bootstrap can take pages from anywhere |
A pool item with exactly one owner, reached by raw links (struct pv_entry’s pv_next, pte_desc in a vp3 slot), pool_get cast and filled by hand and pool_put wherever the owner decides (Cell<*const PvEntry>) |
hal::pool::BoxPool<T> (its own pool type: an item is exactly a T, so vmstat -m shows the C’s size; the pool rides in the handle) and PoolBox<T> from BoxPool::get(flags, init): the one owner, Deref/DerefMut, not Clone, whose drop drops the T and puts the item back. A chain the C links by next pointers is Option<PoolBox<T>> with each entry owning the next; an entry leaves by a &mut Option<PoolBox<T>> cursor (take the entry, put its next in its place), never by a raw unlink; a long chain is emptied entry by entry, never dropped whole (each drop recurses into the next, and the kernel stack is small) (sys/hal/pool.rs, D18). An item that raw links also reach (arm64’s pte_desc: owned by its table slot, linked on its page’s pv list) is a SharedBox<T> (BoxPool::get_linked): the same owner and the same drop, Deref only, its fields changed after linking atomics or Cells under their lock, the links made from SharedBox::link and read under the lock that guards their removal, every link removed before the owner drops it; PoolBox (with DerefMut) only where the owner is the one way in. An owner that is one word of a page (arm64’s vp3 slot, 512 of them beside the table the MMU reads) keeps SharedBox::into_raw’s pointer and frees with SharedBox::from_raw (pub(crate) unsafe, its one call in the slot’s take) |
A double put, a put into another pool, a use after the put and a lost entry cannot be written; the item stays the C’s size. Not TypedPool with a mode: its Inner<T> carries a count and a pool pointer an owned item does not need |
A kernel-wide operation any caller may make whose soundness needs a fact no check can see (pmap_kenter_pa/pmap_kremove, pmap_enter on pmap_kernel(): the caller owns the kernel virtual addresses), kept an unsafe fn whose # Safety names the fact |
A capability token: a zero-sized type with a private field, not Clone, which one function returns once (hal::pmap::KernelMapper from bootstrap, a second call panics); the operations are its methods and are safe; the token goes to the owner of the fact (the kernel map, uvm_km, N3.2) and nowhere else (sys/hal/pmap.rs) |
Possession is the proof: safe code without the token cannot remap a kernel stack, and the trust boundary is one hand-over at boot instead of every call site’s unsafe block (decision 30’s pattern, per object instead of per registration). The same pattern guards the switch of a CPU’s address space (hal::pmap::Switcher, Pmap::load): only the context switch, which records the switch for the shootdowns and keeps the pmap referenced, holds it. The guarantee is for kernel crate code; bsd’s adapter keeps the token in a static whose reader is private to sys/machine/pmap.rs behind LZ’s unsafe fns, LZ’s level, until their callers move |
An object handed out as &'static T from a pool, freed by a safe destroy(&'static T) while one static instance exists beside the pooled ones (pmap_create/pmap_destroy/pmap_reference and pmap_kernel()) |
A counted handle with a static arm: enum PmapRef { Kernel, User(PoolArc<Pmap>) }, Deref<Target = Pmap>; Clone is the reference, the last drop of a User is the destroy, the Kernel arm counts nothing; identity is as_ptr() for the records that keep a raw pointer (pcb_pmap, ci_proc_pmap); the value’s Drop refuses to free while something still points at it (a pmap with a leaf mapping panics); a record that keeps the object’s address (a pv entry) gets a counted handle back from it with PoolArc::from_value under the lock that keeps the record, and drops it outside every lock (sys/hal/pmap.rs, sys/hal/pool.rs) |
A use after free cannot be written and the static is never “freed”; the one &'static left is the static itself |
A page-table page reached by a raw pointer per access (pde_at/pde_set, pmap_pte_set and friends, the recursive mapping’s kvtopte), each an unsafe block on the caller’s word |
One view function per machine for every frame the pmap touches: frame(pa) -> &'static [AtomicU64; 512] over the direct map, behind trust::check_frame (page-aligned, the whole page inside the direct map the boot glue described); every entry an &AtomicU64 (atomic_swap_64/setbits/clearbits are swap/fetch_or/fetch_and), the walks safe code; a frame is viewed only while it is held (a user pmap’s tables under its pm_mtx or the pv_mtx of a page they map, the kernel’s always) (sys/hal/arch/amd64/pmap/tables.rs). arm64’s (sys/hal/arch/arm64/pmap/vp.rs) views each vp table’s two frames the same way (view over three page-of-atomics types) and keeps the descriptors’ pointers as typed links, Link<SlotKind> in a level-3 slot and Link<PvKind> on a pv list, dereferenced in one function that takes the witness of the link’s kind (Holds<K>: the slot’s pmap’s Locked, built only by Locked::of and checked against the level-3 position’s pmap, or the page’s pv_mtx guard) |
One unsafe for the whole pmap instead of one per access, every access atomic beside the MMU’s own A/D updates, and the frame checked before any reference to it exists |
A page-table page found through a per-pmap object and a hint (pm_obj[lvl] with ptp_va2o, pm_ptphint, pmap_find_ptp, the PTP’s wire_count in its vm_page) |
The page-table walk is its own index: the directory entry is the lookup, the PTP’s count of valid entries plus one lives in its PageMd::ptp_refs reached through the page provider, pmap_destroy frees by walking the user half top-down (sys/hal/arch/amd64/pmap/backend.rs) |
No second structure to keep consistent with the tables, no uvm_object inside a hal type, and the pmap needs only PhysPages from the page system |
A subsystem calling up into the allocator that owns its memory (the pmap calling uvm_pagealloc, uvm_pagefree, PHYS_TO_VM_PAGE, uvm_page_physsteal), which hal cannot name |
A provider trait passed down as a value: hal::pmap::PhysPages, given once to bootstrap(params, &'static dyn PhysPages), kept by the kernel pmap and copied into every pmap create() makes; no registry slot (sys/hal/pmap.rs, D16) |
Arrows stay down, host tests pass a fake, and only the provider the boot path handed in is ever trusted (steal_memory reads the kernel pmap’s); a bridges.toml row while bsd implements it, plain API once kernel does |
Boot facts written by machdep into the subsystem’s statics before its bootstrap reads them (PMAP_DIRECT_BASE/END, PMAP_KERNEL_IMAGE_*, EFER.NXE read inside the pmap), and two machines’ bootstraps returning different things |
A parameters struct and a results struct: BootstrapParams { direct_base, direct_end, nx, first_avail, image: Option<KernelImage> } in, Bootstrapped { first_avail, virtual_avail, mapper } out (sys/hal/pmap.rs) |
No static is written before its reader runs, every fact is named at the call, and each machine reads what it needs from the same shape; the boot glue’s facts stay trusted, documented once |
One hal API implemented by each machine (the C’s MD half behind an MI header) |
The MI module holds the types, the handles and the checks and calls a crate-private contract trait (PmapBackend) implemented by crate::arch::current::<api>::Backend, selected by cfg as hal::arch::current (amd64, arm64, or the host double, sys/hal/arch/host/); the backend’s constructors are const fns and its statics are built by the MI type’s pub(crate) const fn (Pmap::kernel_with), never associated consts of interior-mutable types; what only one machine’s own code uses stays pub in its backend module, reached by path (sys/hal/pmap.rs) |
The contract is checked by the compiler on every machine, the checks are written once, and generic code never names an architecture |
A resource hal needs from code above it registered in a slot (PageMemory in hal::bridges, ModulePlatform::alloc/release), implemented by bsd over km_alloc |
The kernel implements hal’s safe trait itself and hands it down as a value: kernel::vm::km::page_memory() and module_memory(), const fns returning &'static dyn of a unit struct; the user keeps it (KmBuf stores mem, Pipes::new(mem), hal::module::load(api, mem)); tests pass their doubles the same way (sys/kernel/vm/km.rs) |
No slot and no bridges.toml row for what is API between our own crates (0.3.2); the arrow stays down, and a test needs no process-wide registration |
A capability token that legacy code still needs while its owner has moved (KernelMapper: 54 lines in 22 bsd files call pmap_kenter_pa/pmap_kremove) |
The owner adopts the token (kernel::vm::km::adopt_mapper, once, from machine::pmap::pmap_bootstrap), which returns the one lend handle, LegacyLend (private field, not Clone, not Copy); the borrower keeps it in a private static and shows it to legacy_mapper(&LegacyLend) -> &'static KernelMapper, so only that module (sys/machine/pmap.rs) reaches the token: its unsafe fn wrappers, whose callers keep their unsafe blocks as the proof, and its safe pmap_enter/pmap_remove/pmap_protect on the kernel pmap for the kernel map’s own paths; the handle and the function go with the last caller (N3.3 to N7) (sys/kernel/vm/km.rs) |
One hand-over instead of two (the token moves once, to its owner), the audience is the one holder of the handle, which the compiler checks, and deleting the handle proves no one else borrows |
A subsystem calling across into another that has not moved, through the other’s object types (km_alloc draining a struct pglist of vm_pages, PHYS_TO_VM_PAGE) |
A bridge whose boundary is the C’s own value type, the physical frame: KmPages::alloc(sz, constraint, align, boundary, maxseg, flags, each: &mut dyn FnMut(Paddr)) hands each frame over as it is taken off the list (TailqHead::pop_head), free_list(&[Paddr]) -> Result<(), Paddr> gives a chunk back the C’s km_free way (uvm_pglistfree: the free list, uvmexp.free, its wakeups; the kernel collects at most FREE_CHUNK frames on its stack, unmapping them first) and free(pa) -> bool one the uvm_pagefree way (uvm_km_pgremove_intrsafe’s); a frame no page describes is the error, and the caller panics with the C’s message; work the C does between steps runs inside the callback (the first frame takes the virtual space, so pages-then-space keeps the C’s order) (sys/kernel/vm/km.rs, sys/uvm/uvm_km.rs) |
The kernel needs no list, no heap and no view of VmPage while the page system is still bsd’s. KmPages itself was retired at N3.3 (the bridge and BsdKmPages are gone): once the page system is the kernel’s (kernel::vm::page), km_alloc/km_free call it directly and the C’s order (the page list first, then the space) is back; the shape stays the pattern for a bridge into a subsystem that has not moved |
A switch of the translation table the running code is fetched through, which changes the kernel’s live entries (locore.S’s switch_mmu_kernel, which pmap_bootstrap calls at its physical address through locore’s identity map) |
A position-independent global_asm! routine in a section of its own, its address taken from a safe static of its instruction words in an unsafe extern block, called from one asm! block at its physical address through a one-page identity table the pmap builds in TTBR0_EL1, which the block puts back with TCR_EL1 (sys/hal/arch/arm64/pmap/cpufunc.rs, backend.rs’s switch_mmu_kernel_table) |
Break-before-make for the kernel’s own entries: no instruction is fetched through TTBR1_EL1 while it changes, and the routine’s address needs no unsafe beyond its declaration |
An intrusive TAILQ/RBT whose mutators are pub unsafe fn (“the element is valid and in place while linked”), its links Cell<Option<NonNull<T>>> and tqe_prev pointing into the head, over elements that are in fact never freed (the vm_page array, the pmemranges) |
hal::link::Link<T> (an atomic &'static T, one deref in get), and over it hal::list::List<A> (TAILQ: prev names the previous element, the head holds first/last) and hal::tree::Tree<A> (RBT), elements &'static, adapters by list_adapter!/tree_adapter!, every mutator safe and a broken precondition a panic (sys/hal/{link,list,tree}.rs, N3.3) |
When every element outlives every list, “valid while linked” is the type’s (set takes &'static T) and nothing is left for a caller to promise; no pointer into a head, so a head is an ordinary value. Only for 'static elements: pool items and stack markers keep sys/sys/queue.rs until their owners move |
(struct T *)uvm_pageboot_alloc(n * sizeof(T)) (pmap_steal_memory’s bytes cast, each entry written through the pointer: the vm_page array, uvm_pmr_allocpmr) |
hal::bootmem::steal_slice(n, \|i\| T) -> &'static [T] and steal_one(\|\| T) -> &'static T over hal::pmap::steal_memory: the cast and the in-place writes are hal’s, the kernel gets a typed slice (sys/hal/bootmem.rs, N3.3) |
Boot-stolen memory is never given back, so 'static is true; the provider’s contract (the frames leave the page system for good, mapped and zeroed) is the one premise, checked where it can be (alignment, size) |
A structure the C reads without its lock because it changes only during boot (uvm_pmemrange_find in uvm_pmr_cache_put: the range tree, outside uvm.fpageqlock) |
The structure stays owned by its lock; the fields the hot path reads are copied, once the boot step that builds them is done, into a static of atomics published by a count stored Release (the slots are written before it, a reader loads it Acquire first), and whatever would change the structure withdraws the count first, so the readers take the lock while it is unpublished (kernel::vm::pmemrange’s PmrIndex, N3.3) |
The hot path takes no lock, as in the C, with no lock-free way into a Mutexed; a change after boot, which the C would race, sends the readers to the locked lookup instead of a stale copy; a host test resets it by withdrawing (no OnceStatic to forget) |
A back pointer to an owner that is not 'static (vm_page.uobject, vm_page.uanon: Cell<*const T> followed by every caller, its validity “the owner outlives its pages”) |
An identity tag in the element (kernel::vm::page::OwnerTag: the owner’s address as a number, its kind in the low bit), compared and never dereferenced, and the owner as an argument the caller already holds (Owner<'_> = None \| Object(&dyn PageObject) \| Anon(&dyn PageAnon)), checked against the tag (sys/kernel/vm/page.rs, N3.3) |
The C’s [o] rule says every caller holds the owner’s lock, so it has the owner in hand; the element can name it without keeping a reference that could dangle, and a wrong owner is a panic instead of a write into someone else’s object |
pg + n / pg - n in an array of structures reached through a pointer (VmPage::add, sub, ptr_add, the pmemrange’s pg[1] and “the array broke” pointer test) |
each element knows its position (VmPage::index), and pg + n is pages()[pg.index + n], a bounds-checked slice index (page::nth, nth_back); “contiguous in the array” is prev.index + prev.fpgsz == pg.index; a &VmPage becomes the array’s &'static by its index (page::static_of) (sys/kernel/vm/page.rs, pmemrange.rs, N3.3) |
Safe and checked, the same cost as the pointer step plus a compare, and it keeps the C’s semantics: one array laid out by uvm_page_init, its order not the physical order |
A lock taken by one function and released by another it calls (uvn_flush holds uvm.pageqlock across uvm_pager_put, which unlocks it once the cluster is built), spelled uvm_lock_pageq() / uvm_unlock_pageq() free functions around a lock beside its data |
The callee takes the guard by value and drops it where the C unlocks (uvm_pager_put(.., pageq: MutexedGuard<'static, PageQueues>)); the caller re-takes the lock with uvm_lock_pageq() after the call, and every temporary unlock is a drop(q) / q = uvm_lock_pageq() pair the compiler checks for definite initialisation (sys/uvm/uvm_vnode.rs, uvm_pager.rs, N3.3) |
A lock that owns its data (Mutexed<PageQueues>) cannot be unlocked by a function that does not hold its guard; passing the guard keeps the C’s lock protocol exactly and makes “the callee unlocks” part of the signature |
Locks of objects the fault does not own taken in one function and released in others along many paths (amap_lock in uvm_fault_check, uvmfault_unlockall(ufi, amap, uobj) on fifteen paths, rw_enter(anon->an_lock, lock_type) again in uvmfault_anonget, pgo_get(PGO_SYNCIO) entered locked and returning unlocked), with KASSERT(rw_status(lock) == flt->upper_lock_type) where each function starts |
The witnesses travel as values: the function that takes a lock returns its RwWitness, the one that releases it takes it by value (uvmfault_unlockall(ufi, upper: Option<RwWitness>, lower: Option<RwWitness>), ObjRef::get_sync(&self, w: WriteWitness, ..)), and one that may release or keep it answers which (enum AnonGet { Resident(w), NeedWrite(w), Unlocked(errno) }); the handles the witnesses borrow live in a per-round slot of the loop (uvm_fault_check(.., slot: &'v mut Option<EntryView>) -> (&'v EntryView, Option<RwWitness<'v>>)), so no witness outlives its round (sys/kernel/vm/fault.rs, N3.4d) |
What is held at each point is the set of live witnesses, checked by the compiler on every path: no lock is kept past its round or released twice (a witness is moved, and borrows the round’s snapshot), a lock is released on every path that drops its witness, and a Guarded cell opens only through the witness in hand; the order of acquisition stays the code’s (MAPS => AMAP => UOBJ), commented where each lock is taken |
A map still owned by legacy code reached by raw *const VmMap/*const VmMapEntry pointers turned into &'static (ufi.entry()), and the C’s “relock and compare ufi->mapv with map->timestamp, read ufi->entry again if equal” |
The kernel code is generic over a bridge trait the legacy map implements (FaultMap, like PipeGlue, no registered slot), whose lock is a GAT guard (type Guard<'a>: FaultMapGuard where Self: 'a) that hands out entries borrowing it (lookup(&self, va) -> Option<&Entry>); the version check is relock(&self, version) -> Option<Guard>, None with nothing held; what the code needs of an entry is copied once under the lock into a value holding counted handles (EntryView) (sys/kernel/vm/fault.rs, N3.4d) |
An entry reference cannot outlive the map lock (it borrows the guard), and “the map changed while unlocked” has no entry to misuse: the relock either gives a guard or nothing. The snapshot is what the C reads, since the entry cannot change while the map is locked or after a relock at the same version |
A lock object several objects share and none owns (rw_obj_alloc(&amap->am_lock, ..), rw_obj_hold when an anon or an amap copy takes the same lock, rw_obj_free by each), a &'static Rwlock cast back to its struct rwlock_obj by offset_of and a magic number; rwsleep_nsec(.., PNORELOCK) returning with the lock released behind the caller’s back (uvm_pagewait) |
hal::rwlock::SharedRwlock: a counted handle, enum { Static(&'static RawRwlock), Pooled(PoolArc<RawRwlock>) } (pool "rwobjpl", init_shared(); new(name) the alloc, Clone the hold, the last drop the free, from_static for a lock that is never freed); write()/read() return a WriteWitness/ReadWitness, guards with no data whose existence proves the lock; their sleep_nsec retakes the lock, their into_sleep(ident, prio, wmesg) is PNORELOCK and consumes the witness; downgrade/try_upgrade as Rwlocked’s (sys/hal/rwlock.rs, N3.4a) |
The lock lives exactly as long as its last holder, with no cast and no magic; a witness borrows a handle, so it cannot outlive the lock, and a consumed witness cannot be used after the release, which is what makes PNORELOCK safe to express |
Fields of one object “locked by” a lock another object owns (the C’s [a]: anon->an_ref under the amap’s lock, the amap’s chunk tables, the aobj’s swap slots), every access trusting the caller and at best a KASSERT(anon->an_lock == amap->am_lock) |
hal::rwlock::Guarded<T>: a cell keyed to one lock’s identity (Guarded::new(&lock, v), new_static(&RAW, v) in a const), get(&w) -> &T with any witness, get_mut(&mut WriteWitness) -> &mut T, each panic(9) on a witness of another lock; rekey(&mut self, &lock) and get_mut_owned(&mut self) for a value still its maker’s; Witness is sealed (the two witnesses only); scalars read without the lock stay atomics written by setters that take the witness (sys/hal/rwlock.rs, N3.4a) |
The identity check is the soundness proof, not a diagnostic: a cell opens only for a holder of its lock, the reference borrows the witness (so it ends before a sleep or a release), and the C’s assertion becomes the check that every access makes |
A lock mode decided at run time and kept in an int (flt->upper_lock_type = RW_READ, raised to RW_WRITE), the lock taken in it (rw_enter(lock, flt->upper_lock_type)), taken again in the mode found (lock_type = rw_status(lock); ... rw_enter(lock, lock_type)), and KASSERT(rw_status(lock) == flt->upper_lock_type) at every step |
hal::rwlock::RwMode { Read, Write } (from_flags, flags) and SharedRwlock::enter(mode) -> RwWitness, enum RwWitness { Read(ReadWitness), Write(WriteWitness) }: mode() is the status, try_upgrade() is RW_UPGRADE \| RW_NOSLEEP with the writer’s fast path (Err gives the reader back), as_write() opens a Guarded mutably, the sleeps are the witnesses’; the enum is a sealed Witness itself (sys/hal/rwlock.rs, N3.4d) |
The mode stays a value the code decides, but what is held is a witness whose arm says the mode, so “re-enter in the mode I had” is lock.enter(w.mode()) and the status assertions are facts of the type; no witness is minted from a lock word, so a reader never claims a count it does not hold |
p = mallocarray(n, sizeof(*p), M_UVMAMAP, flags), a loop that fills it, free(p, M_UVMAMAP, n * sizeof(*p)) with the count repeated at the other end (am_ppref, am_buckets, u_swslots, the hashinit tables) |
hal::malloc::MArray<T>: MArray::new(ty, flags, n, \|i\| init) -> Option<MArray<T>>, Deref/DerefMut<Target = [T]>, the drop drops each element and frees with the same type and size; the C’s overflow test kept (None under M_CANFAIL, panic(9) otherwise; past isize::MAX too, a slice’s bound) (sys/hal/malloc.rs, N3.4a) |
vmstat -m counts the block in the C’s row, the length cannot disagree with the free, and the elements are a bounds-checked slice |
vaddr_t kva = uvm_pagermapin(pps, npages, flags) cast into an iovec and memset past what the read returned, uvm_pagermapout(kva, npages) on every path |
hal::mapped::MappedBytes, made only by the kernel map’s token: KernelMapper::map_frames(va, &[Paddr], prot) -> Result<MappedBytes, Errno> (each frame checked to be a busy managed page through PhysPages::is_busy, the window checked unmapped, prot with PROT_READ, entered PMAP_WIRED \| PMAP_CANFAIL \| prot, the entered ones removed on a failure) or KernelMapper::map_direct(pa) for one page; each frame claimed for the one view by a bit of its PageMd that only hal sets: a second view, pmap_zero_page/pmap_copy_page, a pmap_page_protect that would write-protect a writable view, the page’s unbusy (VmPage::clear_bits), its free and its next allocation all panic on a held frame, and pmap_page_protect(PROT_NONE) spares the view’s own mapping (a window’s kernel entry, recorded in PageMd; the direct map is on no pv chain) while it removes the others, as the C deactivating a busy page; as_slice/as_slice_mut (the latter refused on a read-only window); the drop gives the claims up and is the pmap_remove, unmap(self) -> Vaddr gives the window back for its segment (sys/hal/mapped.rs, N3.4a) |
The window cannot be used after it is unmapped nor written when mapped read-only, two views of one frame cannot exist, and nothing without the token writes, unmaps, frees or reallocates a viewed frame. Pages of uvm_pglistalloc (km_alloc, pools, malloc, KmBuf) and page tables are never busy, so they cannot be viewed; the gap until N3.5 (the token holder’s contract): no live window is overlaid, removed or write-protected through the kernel map’s token but by its drop, and no frame is a busy page that backs kernel memory (the buffer cache’s, busy for the buffer’s life); the frames stay busy until the drop (unbusying, freeing or reallocating a viewed page panics) |
A pool item handed out as &'static T and freed by whoever drops a C reference count of one kind of holder to 0 (uvm_analloc/uvm_anfree with an_ref, the amap slots that hold the anon; amap_alloc/amap_free with am_ref, the map entries), while holders the count does not count (a fault sleeping on the anon’s busy page, kept alive by PG_RELEASED and an rw_obj_hold) still name it |
The item is a hal::pool::PoolArc<T> (AnonRef, AmapRef) whose handle count owns the memory, and the C’s counter stays beside it with the C’s meaning, a relaxed atomic written under the C’s lock: every place the C increments the counter also clones a handle into the new holder (an amap slot’s copy, a map entry’s reference), a holder the C does not count (a thread across a sleep) clones a handle and leaves the counter alone, and the C’s free at count 0 does what it did to the page and the swap slot, the memory going with the last handle; the counters’ setters assert the lock (KASSERT, as the C’s rule) instead of taking the witness, because a walk holds the same lock’s Guarded tables open mutably through the write witness while it drops the counts (sys/kernel/vm/anon.rs, amap.rs, N3.4b) |
The decisions the C makes on the counter (copy the anon when an_ref > 1, take the amap over when am_ref == 1) read exactly what the C reads, while no holder, counted or not, can see the memory go before it lets go; a PG_RELEASED page needs no extra lock reference, since the anon holding the lock’s clone lives as long as the busy page’s holder |
A table of function pointers per object kind (struct uvm_pagerops reached through uobj->pgops, nine Option<fn>, NULL where a pager has none) whose functions get the common header (&UvmObject) and cast it back to the structure it is the #[repr(C)] first member of ((struct uvm_aobj *)uobj, (struct uvm_vnode *)uobj) |
An enum of the handles to the objects that have a pager (kernel::vm::object::ObjRef: Aobj(PoolArc<Aobj>), Kernel(&'static Aobj), Vnode(&'static Uvn)), Deref to the common header (Object), whose methods are the operations, each a match on the arm calling the pager’s function with its own type; the kind tests (UVM_OBJ_IS_AOBJ) are an ObjKind fixed at creation; an operation a pager lacks is what the C’s NULL would do (mk_pcluster answers None, put on an aobj panics as the call through NULL faults). Where the C’s operation changes its lock protocol by a flag (pgo_get with PGO_LOCKED keeps the lock, without it returns unlocked) it is two methods, one borrowing a witness of the object’s lock and one consuming it (get, get_sync); an operation that drops and retakes the lock inside (put, flush) borrows the write witness mutably; each checks the witness is its object’s lock’s (N3.4c) |
No cast and no #[repr(C)] layout to keep for nothing userland sees; a new pager is an arm the compiler makes every operation handle; the lock state each operation needs and leaves is in its signature, so a caller cannot use the object’s state after a call that released the lock |
A sentinel pointer value in an array of pointers (PGO_DONTCARE, (struct vm_page *)-1: “a page we are not interested in getting”, compared and never followed, beside NULL for “none yet”), carried in LZ as *const VmPage slots read through unsafe derefs |
An enum slot (kernel::vm::pager::PageSlot: Empty, DontCare, Page(&'static VmPage)), Copy, the array &mut [PageSlot]; page() answers the page, is_empty()/is_dontcare() the tests (N3.4c) |
The three cases the C encodes in one pointer are three variants: the sentinel cannot be followed, and a page in a slot is a reference to the page array, which lives for ever |
A pool item that is never freed because another structure keeps it across its own recycling (struct uvm_vnode, pool_get once per vnode and kept in vp->v_uvm; LZ: a pool item written by hand and handed out as &'static UvmVnode) |
TypedPool::get_shared then hal::pool::PoolArc::leak(handle) -> &'static T: the handle is forgotten with its count, so the item is never put back and the reference is true for ever; the vnode and the map’s handle (ObjRef::Vnode) keep it (sys/kernel/vm/vnode.rs, N3.4c) |
The C’s lifetime (never freed) as a type, with the pool’s accounting (vmstat -m’s uvmvnodes) kept; only for items the C never frees, since a leaked item is gone for the pool |
A pointer to a counted object copied between records without counting (dst->aref = src->aref in uvm_mapent_copy, the clips, uvm_mapent_clone; entry->object.uvm_obj the same), the count (am_ref, uo_refs) changed by named calls elsewhere, the pointer just forgotten when the record is freed; LZ: Cell<*const VmAmap> made &'static by an accessor |
The record holds the object’s counted handle in a Cell of the pointer’s size (Cell<Option<AmapRef>>, Cell<VmMapEntryObject> over the kernel’s ObjRef), read by take/clone/set (VmAref::amap, VmMapEntry::uvm_obj: a clone, never a reference into the cell) inside a one-byte busy flag beside the cell (AtomicBool, spun on for that window only: a clone or a swap), each C copy a handle clone (VmAref::copy_from), the C’s count left to the C’s calls (amap_ref, amap_unref, amap_splitref, pgo_reference, pgo_detach), and the record’s free clearing the cell (uvm_mapent_free), since a pool item is overwritten without a drop |
The handle count is the memory’s lifetime and the C’s count stays the C’s meaning (the N3.4 G2 row); a Cell of a non-Copy handle has no safe by-reference read, so the clone is the read; the record’s lock does not cover the take/set window, since a read lock admits several readers (two faults on one entry, uvm_map_clean on a busy map: N3.4e’s first smoke-mp saw a fault find the entry’s object gone and return EFAULT), hence the flag; flag and cell fit the pointer’s place and the record’s padding, so the entry pools’ item sizes (vmstat -m) stay (bsd’s map until N3.5 S2; superseded in kernel::vm::map by the handles’ Guarded cell keyed to the map’s lock, part 1, read shared under any witness: no flag) |
A lock the caller holds C-style around a call whose callee asserts it (vm_map_lock(map) … uvm_fault_unwire_locked(map, ..) … vm_map_unlock(map) in uvm_map.c and uvm_glue.c, the callee’s vm_map_assert_anylock(map)) while the redesigned callee takes the lock’s guard as the proof (kernel::vm::fault::uvm_fault_unwire_locked(&G: FaultMapGuard, ..)) |
MapGuard::held(map) (sys/uvm/uvm_fault.rs): after the assertion, a guard of the lock the caller holds, in the mode rw_status answers, that does not unlock on drop (owned: false); the guards the callee’s own FaultMap::lock makes unlock |
The legacy callers keep their shape until their module moves (N3.5) and the callee keeps its typed proof; the guard is made only where the C asserts the lock held, so it claims nothing the C does not check |
An intrusive red-black tree or tail queue of pool items freed explicitly (uvm’s map entries: the address tree, RBT_GENERATE_AUGMENT with fspace_augment, and the dead queue over the same dfree union), LZ’s RbtHead/TailqHead taking &'static elements in unsafe inserts whose comment says the entry stays alive while linked, and uvm_mapent_free(&'static VmMapEntry) freeing what a caller still holds |
hal::owned::OwnedTree<A> and OwnedList<A>, which own their elements: insert(&mut self, PoolBox<T>)/push consume the box, take_by(&mut self, key_vs) -> Option<PoolBox<T>>/pop give it back, drain_into(&mut self, &mut OwnedList<A>) moves a whole tree in linear time, the drop frees what is left; elements are reached only as &T borrowing the container (root/min/next(&self, e)/find_by/nfind_by/iter), RBT_AUGMENT is augment(&self, e); one OwnedEntry per element (tree or list, the C’s union) records the owner’s identity and the element’s pool; the adapter (owned_adapter!(.., augment = f), f(e, left, right) -> bool one node’s step, walked up while it changes) is checked at every access (the entry lies within the element and carries the container’s identity), and a panic in a change poisons the container (sys/hal/owned.rs, N3.5 S0) |
Ownership is the soundness argument instead of 'static: no element can be freed or given out mutably while a reference into the container lives, so a use after free cannot be written; take_by finds and removes in one call because a reference that borrows the tree cannot be passed to a method that changes it. Rejected: elements not intrusive (no alloc in the kernel; a node pool would be a second vmstat -m row and a pointer per node) |
A static array of objects handed out from a free list under a mutex, extended by pages carved into more objects and never freed (kernel_map_entry[MAX_KMAPENT], uvm.kentry_free under uvm_kmapent_mtx, uvm_mapent_alloc’s km_alloc(PAGE_SIZE, &kv_page, &kp_dirty, &kd_nowait) when the list is empty), beside two pool(9)s of the same objects; LZ: a static [VmMapEntry; 1024], a legacy SlistHead and p.write into a carved page, each entry a &'static |
hal::pool::StaticArena<T, N> (const fn new(), extend(&self, KmBuf) over KmBuf::leak_slice, nout, has_free), a RawPool that is not a pool(9) (no vmstat -m row, as the C’s), behind an ordinary BoxPool (BoxPool::init_arena(&'static ARENA)), so the static entries are the same PoolBox<T> as the pooled ones and go back to the arena by the box’s drop (sys/hal/pool.rs, N3.5 S0) |
One handle type for every source of an object, so the containers and the code that frees need not know which: the C’s flags & UVM_MAP_STATIC/KMEM dispatch at free time is the box’s pool. The arena’s RawPool is a private type, so no caller can put a pointer it did not get; decision 10 holds (no &'static from an item that can be freed: the arena’s slots are never freed, and still only borrowed) |
A lock embedded in the object whose fields it guards and taken by name around them (vm_map_lock(map): rw_enter_write(&map->lock), then map->addr, entry->object, entry->aref read and written), the fields Cells under a Sync claim (LZ’s unsafe impl Sync for VmMap, the N3.4e busy flags on the entry’s two handles) |
The lock a hal::rwlock::RawRwlock field, taken through its own witnesses (RawRwlock::write/read/enter, their _flags/try_ forms; SharedRwlock’s are its lock’s), the fields Guarded cells keyed to it once the object sits where it stays (Guarded::new_keyed(&lock, v), rekey_raw/rekey_id after placement: a key to the address the lock had before a move opens with no witness) (sys/hal/rwlock.rs, N3.5 S0) |
The cells’ soundness is the lock’s own word, as for a shared lock object, with no pool item per object (no rwobjpl row the C does not have); a witness borrows the object, so the object cannot be freed or moved while the lock is held through it |
A map whose lock is a mutex instead of an rwlock when it is used from interrupt context (VM_MAP_INTRSAFE: mtx_enter(&map->mtx) in vm_map_lock, kmem_map), the same fields under either |
A MutexedGuard is a witness (Witness, Exclusive, Divisible: the one holder of the mutex, as a writer is of an rwlock), the cells keyed to the mutex (Guarded::new_mutexed(&mtx, v), Mutexed::id, rekey_mutexed); a LockId tags a mutex’s identity (the address of its owner word with the low bit set) so a mutex and an rwlock never open each other’s cells (sys/hal/mutex.rs, rwlock.rs, N3.5 S0) |
One map type whose lock is either kind, the cells opening through whichever guard the map’s lock gave; no second map type and no generic over the lock |
Two fields under one lock touched in one stretch while one is borrowed from the other (uvm_map_splitentry, uvm_unmap_remove: the map’s tree walked while an entry’s object/aref change), which one &mut from one witness cannot express (get_mut(&mut w) borrows the witness for as long as the reference lives) |
Divisible::split(&mut w) -> [WitnessPart<'_>; N] (N <= WITNESS_PARTS, 4): parts that each open only the cells made in their part (Guarded::keyed(id, part, v)), mutably and at once; the whole witness opens every part when it is not split; a part is Exclusive but not Divisible, not Clone, not Send (sys/hal/rwlock.rs, N3.5 S0) |
Disjointness is declared where the cells are made (a map’s state in part 0, its entries’ handles in part 1) and checked at each access, so the state’s &mut and an entry’s &mut coexist while two &mut of one part never do (the borrow checker keeps a part’s reference unique) |
A lock composed by hand from a rwlock, a busy owner that keeps writers out while the map is unlocked, nbusy waiters and a timestamp every write lock bumps, or a mutex instead for an INTRSAFE map (vm_map_lock_ln’s loop, vm_map_busy/unbusy, vm_map_upgrade, vm_map_lock_read; LZ: Cell<*const Proc> and the C’s calls one by one) |
Values: VmMap::lock/lock_try/lock_read/relock(version) give a MapWriteGuard/MapGuard holding the rwlock’s RwWitness or the mutex’s guard (AnyWitness), whose drop unlocks; upgrade(self) -> Result<MapWriteGuard, MapGuard>, downgrade(self); MapWriteGuard::into_busy(self) -> MapBusy is vm_map_busy + unlock, MapBusy::lock() the busy holder’s lock (no wait, no version), its drop vm_map_unbusy; busy/nbusy a Mutexed<Busy> whose address is the waiters’ channel, the owner hal::sleep::curproc_word() (0 is none) (sys/kernel/vm/map.rs, N3.5) |
The C’s protocol (who waits, who passes, what bumps the version) is unchanged, but the states are types: a write lock’s operations take the guard, a busy window holds a value whose drop unbusies, and an unlock cannot be forgotten or doubled |
C pointers to tree elements kept across changes of the tree (uvm_map_clip_start(map, entry, addr) keeps entry naming the upper part; uvm_map_mkentry(map, first, last, ..); walks that clip as they go) |
The element’s unique key (an entry’s start) instead of a reference, the element found again after every insert, removal or clip (ent(&st.addr, key, who)); a clipper returns the key the C’s pointer names afterwards (uvm_map_clip_start_at the clip address, uvm_map_clip_end_at the same key) (sys/kernel/vm/map.rs, N3.5) |
A reference borrows the tree, so it cannot live across a &mut change of it; the address tree’s keys are unique (an insert collision panics, as the C), so a key names exactly what the C’s pointer did, at O(log n) a step |
A walk of a busy, unlocked map’s entries (uvm_map_pageable_wire’s second pass, uvm_map_clean), reading entries no lock protects while busy keeps writers out |
Each step takes the read lock briefly (MapBusy::lock_read: readers pass busy), copies the entry’s scalars, clones its handles and the next key, releases, then does the work (a fault, a flush) with nothing held (sys/kernel/vm/map.rs, N3.5) |
Entries are reachable only through a witness; busy still excludes every writer for the whole walk, so what each step reads is what the C reads without a lock |
A write-locked object whose state and whose elements’ fields change in one stretch (uvm_map_splitentry: the tree and an entry’s object/aref) |
MapWriteGuard::split(&mut self) -> MapSplit, and MapSplit::parts(&mut self) -> (&mut MapState, &mut EntryWrite<'_>): the state through witness part 0, the entries’ scalar setters (&EntryWrite) and handles (handles_mut(&mut EntryWrite)) through part 1 (sys/kernel/vm/map.rs, N3.5) |
The parts borrow the witness, so they must live in a value the caller holds (a function cannot return references into its own locals); the setters’ parameter is the proof the C’s comments state (“map write-locked”) |
A function the C calls with a lock held “by the caller” (uvm_fault_unwire_locked(map, ..) from inside uvm_unmap_kill_entry, uvm_map_pageable_pgon), generic over a guard trait (FaultMapGuard) |
A view of the held lock as that trait (HeldView { map, st, part } over the split write guard’s state and entries’ part), reads only; the trait’s lock-changing methods (downgrade, copy_amap) panic on it (sys/kernel/vm/map.rs, N3.5) |
The caller’s guard is already split (its parts borrowed), so the guard itself cannot be lent; the view lends exactly what the callee reads |
(struct vmspace *)map: the map is the first field of the vmspace and code holding the map casts back to reach the vmspace’s statistics (vm_dused, vm_daddr, the stack bounds; LZ: #[repr(C)] and an unsafe cast) |
The statistics live in the map (VmMap.vs: VmspaceVars, atomics) and the outer type derefs to them (impl Deref<Target = VmspaceVars> for Vmspace), so vm.vm_dused reads as before and map code reads map.vmspace_vars() (sys/kernel/vm/map.rs, N3.5) |
No back link from an inner field to its container exists in safe Rust without a &'static to a pool item; the fields sit where the code that changes them already holds a reference |
Another address space’s pages extracted into the kernel map and copied through as kernel memory (uvm_io: uvm_map_extract then uiomove((caddr_t)(kva + pageoffset), sz, uio); sys_kbind: kcopy(param, (void *)(kva + pageoffset), s)), a fault on a page the other process unmapped caught by pcb_onfault; LZ: a &[u8] over the window (uvm_io.rs) and an unsafe fn kcopy over two raw pointers (uvm_mmap.rs) |
hal::user::ForeignWindow<'m>, minted only by the kernel map’s token (KernelMapper::foreign_window(va, len)), never dereferenced: read_at(off, &mut [u8]) and write_at(off, &[u8]) copy a range checked inside the window through the UserCopy bridge’s kcopy_in/kcopy_out (in bsd, uiomove over a UIO_SYSSPACE iovec: the machine’s kcopy, a fault an EFAULT); bridges::user_copy() is crate-private, so the kernel reaches kcopy only through a window (sys/hal/user.rs, N3.5 S0) |
The pages are aliased by their own process, so no Rust reference to them may exist (a &mut [u8] over them is a lie, a &[u8] a data race); the C’s own shape, a fault-recovering copy, is the honest one. The window’s premise is the token’s contract, as for every address the kernel map maps: its holder mints a window only over a range its own uvm_map_extract returned (foreign pages, no Rust object among them) and unmaps it only after the window is gone; nothing checks the range, so a window is the strongest primitive the token gives (a write to any address its maker names), to be made a type in N3.5 S1 (windows minted only from the extract’s result). bsd’s kcopy stays an unsafe fn; the safe path S0 rides on is bsd’s legacy uiomove with a UIO_SYSSPACE uio (sys/kern/kern_subr.rs), already a safe signature over kcopy before S0 (its iovecs’ builder vouches for them) |
A second tree or a back pointer to elements another structure owns and frees (the selectors’ free trees uaddr_free_rbtree over dfree.rbtree, the pivot’s up_pivot.entry), kept valid by the C’s rule “remove from the free tree before the address tree” (uvm_mapent_free_remove before uvm_mapent_addr_remove) and by nulling the pointer (uaddr_pivot_remove); LZ: Cell<*const VmMapEntry> turned into &'static |
hal::owned::SecondaryTree<S> (insert(&mut self, &T), remove(&mut self, &T), clear, the walks) through a SecondaryEntry of its own, and hal::owned::SecondaryRef<A> (set(&mut self, Option<&T>), get(&self) -> Option<&T>): each link counted in the element’s OwnedEntry (indexed), only for an element some owning container owns, and the owner’s take_by/pop/drop panic while the count is not 0 (sys/hal/owned.rs, N3.5 S0) |
The C’s ordering rule becomes a checked precondition: a secondary link keeps its element alive because the owner refuses to free a counted one, so the secondary’s derefs need no promise from its callers, and a dangling pivot or free-tree link cannot exist |
A window’s range trusted as whatever number its maker passes (uvm_io, sys_kbind: kva from uvm_map_extract kept in a local beside the copy and the later uvm_unmap_remove(kernel_map, kva, kva + len, ...); S0’s KernelMapper::foreign_window(va, len) takes any range) |
kernel::vm::km::Extracted, a range of kernel_map with no public constructor, made only by km::uvm_map_extract_window from the address uvm_map_extract returned, and consumed by km::foreign_window(Extracted) -> KernelWindow, the only way to a ForeignWindow over it; KernelWindow drops its window before its range, and the range’s drop is the C’s uvm_unmap_remove + uvm_unmap_detach(AMAP_REFALL); the token itself stays private to km: the rest of kernel::vm gets a VmMapper newtype (enter, map_direct, map_frames), which has no foreign_window (sys/kernel/vm/km.rs, N3.5 S1) |
The token’s contract (“a window only over a range your own extract returned, unmapped only after the window is gone”) becomes a type: no caller can name another range, forget the unmap, or unmap while a window copies through it |
A C callback with a void *cookie the caller threads through (uvm_coredump_walkmap(p, setup, walk, cookie), uvm_coredump_walk_cb(start, realend, end, prot, isvnode, nsegment, cookie)); LZ: fn pointers and *mut c_void |
&mut dyn FnMut(..) -> Result<(), Errno> closures, the arguments a struct when they are many (vm::types::CoredumpSeg); the cookie is what the closure captures (sys/kernel/vm/unix.rs, N3.5 S1) |
The state stays typed and borrowed: no cast back from *mut c_void, and the walk cannot outlive what it writes to |
A system call’s or a fault’s reads of curproc scattered through the VM code (p->p_p->ps_wxcounter++, lim_cur(RLIMIT_DATA), fd_getfile(p->p_fd, fd), p->p_ru.ru_minflt++, pr->ps_kbind_addr under ps_mtx, PROC_PC(p)), LZ passing &Proc everywhere |
One registered bridge, kernel::vm::proc::VmProc, whose every method acts on the calling thread and is one call into bsd; the kernel’s functions take the address space (&Vmspace) and their typed arguments, bsd’s sysent[] adapters pass p->p_vmspace. A read-check-update the C does under a lock is one method running the kernel’s closure inside it (with_kbind(&mut dyn FnMut(&mut KbindSlot)) under ps_mtx; with_fd_vnode from fd_getfile to FRELE) (sys/kernel/vm/proc.rs, N3.5 S1) |
struct proc stays bsd’s until N4; one slot keeps the crossing countable (one bridges.toml row) and every check in the kernel, and a closure keeps a critical section whole where a get/set pair would open a race |
Machine constants the generic code reads through the machine’s traits (<Machine as VmParam>::DFLSSIZ, MachineParam::USPACE, MachineExec::LDPGSZ, <Machine as Pmap>::DMA_CONSTRAINT), implemented by bsd’s arch |
Those hal carries are read from hal::arch::current::vmparam; the rest are one kernel::vm::init::VmMachine value (ldpgsz, uspace, uspace_align, have_uspace_guard, dma_constraint) bsd’s uvm_init hands down once (uvm_machine_init), read through vm::init::machine() (sys/kernel/vm/init.rs, N3.5 S1) |
The kernel cannot name bsd’s Machine, and a value handed down is data, not a bridge: no call crosses back into bsd |
A bounce buffer built by hand: km_alloc(kp_none) for the space, uvm_pglistalloc(dma_constraint) for the pages, pmap_kenter_pa per page, slices over it in unsafe blocks, and the reverse on every exit path (uvm_vslock_device, uvm_vsunlock_device) |
A hal::kmbuf::KmBuf from a constrained provider (kernel::vm::km::dma_memory(), km_alloc with kp_dma_zero): owned, mapped, sliced safely, freed by its drop; it travels inside the value that holds the map’s read guard (vm::glue::DeviceLock) to the unlock (sys/kernel/vm/glue.rs, N3.5 S1) |
The same pages from the same physical range, with one owner; no exit path can leak or double-free them |
A process’s address space as a raw pointer to a counted object (pr->ps_vmspace, p->p_vmspace), counted by hand (uvmspace_addref before a read that may sleep, uvmspace_free after; uvm_exit nulls then frees); LZ: Cell<*const Vmspace> and an unsafe deref in every reader (fill_kproc, the ^T status line) |
The counted handle itself in the pointer’s slot: Process::ps_vmspace: Cell<Option<VmspaceRef>> (one word, as the pointer), dereferenced by reference in one accessor only (vmspace(), vmspace_opt(), vmspace_share(), vmspace_ptr() copy out before they return; nothing lends the handle itself to a caller, which could empty the slot under the borrow) and written only where the process is alone (fork1 before it is reachable, exec single-threaded, the reaper’s uvm_exit); a reader that keeps it holds a handle of its own (vmspace_share, the C’s uvmspace_addref) given back by uvmspace_free; the threads’ copy p_vmspace stays the raw address until Proc moves (N4.2) |
The pool item goes back only with the last handle, so no reader dereferences a freed vmspace; the readers’ unsafe derefs go (one stays, the slot’s own), and the processpl item does not grow (vmstat -m unchanged) |
A table the kernel builds and checks in safe code (sys_pinsyscalls’ MArray<u32>) but whose owner is still C-shaped state that frees it with free(9) (ps_libcpin.pn_pins, read by pin_check, freed by pin_free at exit/exec); LZ: malloc of npins * sizeof(u_int) and a slice::from_raw_parts_mut over it |
hal::malloc::MArray::into_raw(this) -> (NonNull<T>, usize), safe as Box::into_raw: the block is handed over initialised and counted, and the receiver frees it with the same malloc type and size (Pinsyscall::install) |
The checks stay the kernel’s and the construction needs no unsafe; the legacy reader and freer change nothing until N4’s proc owns the table |
A #[repr(C)] structure of ints copied out as raw bytes (sysctl_rdstruct(.., &uexp, sizeof(uexp))); LZ: unsafe impl SysctlPlain for UvmexpCopy (a byte view) |
UvmexpCopy::to_ne_bytes(), written by the member-list macro that declares the structure: each member’s native-endian bytes in declaration order, the layout pinned by a test against offset_of! |
The bytes userland reads are the C’s without viewing a structure as bytes: no unsafe impl, and a member added to the list is copied out with no second list to keep |
A pointer to an element kept across the calls of one walk while a sibling structure changes (uvm_map_fix_space, uvm_map_mkentry, uvm_mapent_mkfree: the entry of the address tree in hand while uvm_mapent_free_insert/_remove change a selector’s free tree; uvmspace_fork’s RBT_FOREACH over the parent while the child’s map changes); N3’s first shape: the entry named by its key and found again by every callee (ent(&st.addr, key), next_key: 12-15 tree searches per entry forked) |
The state split for the free-list functions, MapState::free_parts(&mut self, owners) -> FreeParts { tree: &OwnedTree, owners, exe, any, brk_stack: &mut } (sys/kernel/vm/map.rs): an entry found through fp.tree stays borrowed while the selectors change through fp, so a walk finds its entry once per step and again (by key) only after a removal changed the tree, while an insert lends the tree, shared, and the element it linked (OwnedTree::insert_get(&mut self, box) -> Result<(&Self, &Elem), (box, &equal)>, uvm_mapent_addr_insert_parts: the state split around the new entry, as uvm_map_fix_space goes on from it); a walk over another map’s tree (fork’s parent) holds &VmMapEntry and steps with next(e); a function that makes an entry and gives it back borrows the state for the result’s life (uvm_map_mkentry<'s>(st: &'s mut MapState, ..) -> Option<&'s VmMapEntry>), and one whose caller must change the state after it gives back a Copy summary instead (Forked) |
Decision 43’s hot-path rule (whoever holds a reference to an element does not look it up again by key): the borrow checker, not a key, says when the tree may have changed; the C’s pointers are what this follows (uvm_map.c keeps entry across these calls), and a &'s result of a &'s mut borrow keeps the whole state borrowed for 's, so a caller that changes the map after the call (the fork’s amap_copy) takes the values it needs, not the reference |
Hot path (decision 43): the C’s page fault, fork, exec and mmap/munmap follow pointers, read derived values in place and take one reference per pointer copied; N3’s first native shape, safe but heavier: an entry found again by key in every callee (ent(&st.addr, key), next_key), MapState::owners() rebuilt by every free-list call, the owned tree’s view and identity check computed twice per node, handles cloned on the way (OldEntry::of, uvm_mapent_clone), Guarded::check through &dyn Witness |
Four rules, N3’s pattern (decision 42’s phase 2, sys/kernel/vm/map.rs, sys/hal/owned.rs, sys/hal/rwlock.rs): (1) whoever already holds a reference to an element (&VmMapEntry) does not look it up again by key in a loop: it walks with next(e) or a cursor (the row above, ac8b9ebf, f5caa6de); (2) derived state (MapState::owners()) is kept and recomputed only when what it derives from changes; an operation computes it once and lends it (&Owners) to its callees, recomputing only after a step that moved a selector or the brk/stack areas (uvm_map_vmspace_update says so; dd9dc059); (3) a soundness check runs once per operation or per node, never repeated in the same walk, and is never removed (hal::owned views each node once and checks its identity on every node visited, 9986eaac; Guarded::check inlined over the concrete witness, the same two compares, 9dab32dd); (4) a handle is lent (&T) instead of cloned when the lock already guarantees it lives (OldEntry<'w>, amap_copy_from(&Amap); the clones that cross a sleep with the map unlocked stay, 6eb820e2) |
The safe shape costs no more than the C’s: host fork and exec 36-49 % faster at the same checks (decision 42); a slice on a hot path proves it with sys/kernel/benches/vm.rs, debug and release, and a rise above 10 % without a reason stops it (testing.md); the reviewer asks whether the path makes more lookups, clones or recomputations than the C |
A struct timeout (or struct task) its owner embeds anywhere (a softc, a pool item, a stack frame: timeout_barrier’s), linked into a global queue through raw links (LZ: kern_timeout.rs’s circq_* unsafe fns over Cell<*const Circq> and timeout_from_circq’s cast; TailqHead inserts of &'static Task) and freed when the owner pleases, “timeout_del before free” a convention |
hal::pinlist: the element is linked through Pin<&T> (core::pin::pin! on a stack, hal::pin::pin_static for a static or a legacy &'static, PoolArc::as_pin/MBox::as_pin for an item), its PinEntry’s drop panics while linked, and a type that unlinks itself does it in its own Drop under the lock (kernel::timeout::Timeout); PinRing is the C’s circular queue with a sentinel head (removal names no queue, timeout_del), PinList a tail queue whose head moves (a task queue in a pool item); every operation takes the lock’s witness and the lists of one lock share their elements’ identity, so CIRCQ_CONCAT/MOVEBUCKET is a splice (sys/hal/pinlist.rs, N4.1) |
A use after free of a queued element cannot be written in safe code: the C’s convention becomes a checked precondition that stops the kernel instead of corrupting it; nothing is allocated per element (the C’s embedding), and the splice keeps the wheel’s per-tick cost the C’s (addendum C.1) |
Fields of many objects guarded by one global mutex (timeout_mutex’s [T] to_func, to_kclock, to_abstime of every timeout; SCHED_LOCK’s [S] fields of every proc), LZ’s Cells under an unsafe impl Sync whose comment names the lock, made by a const initializer (TIMEOUT_INITIALIZER) |
The global lock is a static Mutexed (its data the C’s other [T] globals) or a data-less SharedMutex; each object’s fields are one Guarded cell made by Guarded::new_static_mutexed(&STATIC, v) in a const fn, opened by that mutex’s guard (sys/hal/rwlock.rs, mutex.rs, N4.1); fields read where no guard can be passed (timeout_pending’s to_flags) or changed during a walk that holds a reference from the guard (to_time in timeout_adjust_ticks) are atomics written under it |
The guard is the proof, checked per access (two compares), and the object stays const-constructible, so a timeout in a static or on a stack needs no run-time keying; the C’s unlocked timeout_set becomes a locked write (the cost measured, timeout.set) |
A kernel thread handed a function and a void * it casts back (kthread_create(softclock_thread, NULL, ..), kthread_create(taskq_thread, tq, ..), kthread_create_deferred(taskq_create_thread, tq)) |
The start ticket: the kernel files what the thread is to run as a value of its own types (enum Start, a queue’s counted handle) in a table and hands the bridge only the slot’s number; bsd’s thread function gives the number back to kernel::thread::run (run_deferred), which takes the value out in safe code; a table that cannot grow is the C’s allocation failure (sys/kernel/thread.rs, N4.1) |
No address is re-typed across the bridge, so the kernel’s thread entry points stay safe while the threads are bsd’s (until N4.5); the argument is owned by the ticket until the thread takes it, so a queue destroyed before its creator runs is still alive for it (taskq_destroy in TQ_S_CREATED) |
A legacy structure that embeds a struct timeout (a softc zeroed by autoconf, a pool item, a struct proc) and is freed without being dropped (pool_put, free: LZ’s frees run no Drop), so a kernel object it held by value would have to be valid all zero and outlive a free nobody announces |
The legacy wrapper keeps only what is valid all zero (the initializer’s values, a hal::link::Link to its node) and is served by a node from a pool, found by the wrapper’s address in a registry (hal::tree::Tree under a Mutexed) and never given back: an address made again takes its node back, taken off its queue uncounted and set fresh (kernel::timeout::Timeout::set_fresh), claimed under the registry’s lock; a served wrapper’s path is one load and one compare (the link names a node of this address), a fresh wrapper’s (a fork’s three timeouts, a tcpcb’s) the registry’s lock, a tree search and the wheel’s lock nested (about 6x the served set on the host), a new address’s a pool item more (about 80x) (sys/sys/timeout.rs, N4.1; sys/benches/legacy_timeout.rs) |
No unsafe and no change at the legacy call sites (the unsafe impl Softc proofs that cite the timeouts’ all-zero validity stay true); the nodes are bounded by the distinct addresses that ever held one, a stated deviation that goes with the callers when they own a kernel::timeout::Timeout |
A caller’s own descriptor linked into a container so the container need not allocate under the caller’s lock (extent_alloc_with_descr: the SMMU’s struct extent_region embedded in its map state, ER_DISCARD; LZ: unsafe fns whose caller promised the descriptor stays put while linked) |
The descriptor is a box of the container’s pool made in advance (kernel::extent::descr, a Descr = PoolBox<ExtentRegion>), with the caller’s sleep or failure, before its lock; the container takes it by value and owns it from then on, giving it back to the pool when its region goes (sys/kernel/extent.rs, N4.1) |
The allocation still happens where the C’s did (with the caller’s structure) and never under the lock, and no promise is left to the caller: a descriptor cannot be freed or moved while linked |
One operation that works a lock’s queue several times under one hold (softclock’s look at the first timeout then its CIRCQ_REMOVE/move, timeout_hardclock_update’s MOVEBUCKETs and expired-bucket dumps onto timeout_todo), each queue macro a bare pointer operation in the C |
PinRing::bound(w) gives a hal::pinlist::BoundRing, the ring with the witness held mutably, its binding to the lock checked once: first, remove_first, move_first(dst) and concat(other) check only the other ring they name, and the lock’s data is read through witness() and changed through data_mut() (the data, never the guard: a &mut guard could be replaced by another lock’s while the view works the ring) while the view lives (sys/kernel/timeout.rs, N4.1 review fix N2) |
The hot path’s checks once per operation, as the C does no check at all (decision 43’s hot-path row): the one-shot methods re-checked the same ring’s binding at every call, twice per timeout in softclock and once per bucket in the hardclock; an element first lends borrows the view, so no change runs while it lives |