artmap 0.8.0

A concurrent in-memory Adaptive Radix Tree (ART) featuring optimistic lock coupling.
Documentation
# artmap safety model

This document is normative for artmap's `unsafe` code. Every `// SAFETY:`
comment cites the invariants below (`Inv N`), the latch rules (`W1`–`W5`,
`R1`–`R6`), or a section (`§N`). Section numbers follow the safety and
soundness plan this model was derived from, so references in the code and in
the plan agree.

## §3 What "sound" means

No undefined behaviour, data race or use-after-free is reachable from safe
code under any concurrency; under adversarial but safe user code (`AsBytes`,
`Clone`, `Drop`, `Debug` and closures may panic, be non-deterministic, or
re-enter the map); under subtyping and variance; with guards from any source;
under misuse of public helper types; and with hostile sizes (very long keys,
full or tiny arenas).

Liveness: a panic in user code never leaves a latch locked or a half-mutated
node published; the map stays usable. No operation recurses in proportion to
key length or tree depth. Dropping a map releases every key and value.

Consistency: point operations are linearizable; iterators yield every key
present for the whole scan exactly once, in order; `clear()` is linearizable
at its root swap; `len()` is exact at quiescence and never underflows. While
writers on several threads are in flight, `len()` may be transiently low or
high (Inv 12).

## §4 Invariants

**Inv 1 — Immutable publication; retire exactly once.** Once a leaf or a
version node is reachable, its key, value, version and tombstone state are
never mutated, moved out, or dropped in place. Replacing means allocating a
new object, installing it with a `Release` store under the owning latch,
flagging the old object (`removed`/`superseded`) before unlocking, and
retiring it exactly once after it is unreachable. Inner nodes are different:
their header fields and child slots are mutated in place under the node latch,
following Inv 5.

**Inv 2 — Map-bound, guard-bound borrows.** Every reference into an EBR map
is bounded by both a borrow of the map and a live epoch guard (owned, shared
or borrowed). Arena references are bounded by the map borrow alone, because
arena memory is never reused while the map is borrowed. Tree drop is
synchronous and runs only when no borrow exists.

**Inv 3 — No `&mut` to published memory.** Published nodes and leaves are
accessed only through `&T` with atomics and `UnsafeCell`, or through raw
pointers. `&mut` is permitted only on allocations no other thread can reach
(unpublished nodes being built, or exclusively owned ones). Arena
initialisation writes go through raw places.

**Inv 4 — Strict provenance.** No integer-to-pointer casts in artmap code.
Tag bits are manipulated with `map_addr`; retirement goes through
`Retired<T>`; arena offsets are integers re-based on a provenance-carrying
base pointer.

**Inv 5 — Latch protocol.** See §5.

**Inv 6 — Unwind and re-entrancy safety.** Every latch-held region has a
*prepare* phase, which may unwind and writes nothing another thread can see,
and a *commit* phase, which contains only stores to published memory followed
by unlock or mark-obsolete, inside an `AbortOnUnwind` scope. User code
(`AsBytes`, `Clone`, `Drop`, closures) never runs while a latch is held.
Fallible calls (arena allocation, `expect`, indexing) never run in a commit
phase. Every operation pins once, before its first latch, and never pins,
flushes or repins while holding a latch. Discarded keys and values are dropped
after unlocking. Latch guards are RAII.

**Inv 7 — Structural moves, obsolescence and lock order.** An operation that
detaches a node (growth, unlinking, `shrink_to_fit`, `clear`) or changes its
depth or absolute key path (prefix split) holds that node's latch and bumps or
obsoletes its version before the parent's latch is released. `OBSOLETE` is set only on
nodes already unlinked.
The lock order is `root_latch` → parent → child → `chain_latch`. Parents and
`root_latch` are taken with a blocking `lock()` while holding nothing,
followed by a pointer re-check; nodes below a held latch are taken only by a
version-checked `try_upgrade`. `chain_latch` is terminal: while holding it,
code never takes another latch, allocates from an arena, pins, or runs user
code.

**Inv 8 — Latched writes only; no rollback.** Every write to a published
node's child slot, bitmap, key byte, count, prefix or `exact_leaf`, to `root`,
or to a version chain's `head`/`next`, happens while holding the owning latch.
A published pointer is never rolled back. There is no lock-free insert path.
Every load of `root` is `Acquire`.

**Inv 9 — Invariance and auto traits.** All maps, trees and inserters are
invariant in `K` and `V` (`PhantomData<(L, fn(L) -> L)>`). Handles, iterators,
guards and inserters are `!Send` and `!Sync`. Maps are `Sync` iff
`K, V: Send + Sync`.

**Inv 10 — User traits are untrusted.** Unsafe code never relies on `AsBytes`
being deterministic, having stable lengths, or agreeing with `Borrow`. Every
index derived from key bytes is bounds-checked. The bytes used for an install
are derived once, from the key's final location in the leaf; probes on a
caller's key are hints.

**Inv 11 — One reclamation domain.** All pins and retirements use the default
crossbeam collector, through artmap's own per-thread participant. Public APIs
accept only `artmap::Guard<'m>`, which always wraps a real pin.

**Inv 12 — Accounting inside the critical section.** `len` is incremented
before the `Release` store that makes a new live entry reachable, and
decremented after the store that unlinks one, inside the same critical
section. `len` is a signed counter striped by thread: each thread adds to its
own stripe, and `len()` is the sum, clamped at zero. The sum is exact at
quiescence. A read that overlaps updates on several threads can pair one
thread's decrement with another's not-yet-seen increment, so it is only
approximate while those are in flight; a single writer thread never makes it
undercount.

**Inv 13 — Bounded stack.** No algorithm recurses in proportion to key length
or tree depth.

## §5 Latch protocol

Writers:

- **W1** Acquire with an `Acquire` CAS, then immediately `fence(Release)`.
- **W2** After the fence, scalar stores (key bytes, prefix words, counts) may
  be `Relaxed`.
- **W3** Pointer stores are always `Release`; readers load pointers with
  `Acquire`.
- **W4** `unlock` stores `v + STEP` with `Release`; `mark_obsolete` stores
  `v | OBSOLETE`, only for unlinked nodes.
- **W5** Every field an optimistic reader reads is atomic and written at the
  width it is read.

Readers:

- **R1** `v = read_version()` (`Acquire`); locked or obsolete means retry.
- **R2** Load each field at most once per optimistic section, clamp what is
  derived from it, and use `>=`/`<` checks.
- **R3** Never conclude anything (return, lock, compare as final) from
  unvalidated reads. Following a non-null child before validation is fine.
- **R4** After reading a child's version, validate the parent; at the root,
  re-check that `root` still points at the node.
- **R5** `validate(v)` is `fence(Acquire)` then a `Relaxed` load equal to `v`.
- **R6** A null child slot is absent; it is never dereferenced.

## §8.2 Guards and handles

Every artmap pin goes through an artmap-owned per-thread participant, tagged
with an ID. A handle is duplicated with a nested pin only after checking that
the current participant has the same ID; during thread-local destruction, when
that cannot be proven, duplication panics. Owned iterators share one
`Rc<Guard>` with their items; `*_with_guard` APIs borrow the caller's guard.

## §9 Writers

Every write: pin; optimistic descent with coupling, comparing existing keys
before any latch; prepare unpublished nodes; acquire the parent (blocking,
then re-check) and the node (`try_upgrade`); commit inside `AbortOnUnwind`
with `len` accounting before the publishing store; unlock; then retire
displaced objects. Retries reuse prepared nodes.

§9.3: a new leaf is owned by an `Unpublished` guard until the commit phase
disarms it, so a discarded leaf is freed after the install returns, outside
any latch, and after the last use of the key bytes derived from it.

§9.4 `remove`: as above, locking only the leaf's node `N` when it keeps an
entry; when it takes `N`'s last one, it unlinks `N` in the same critical
section (§13).

§9.8 `clear()`: swap the root under `root_latch`, then walk the detached tree
holding one node latch at a time, marking each node obsolete, retiring nodes
and leaves individually, and subtracting the number of leaves found.

## §10 Readers and the cursor

Point lookups follow §5 with coupling. The cursor keeps `(node, version,
next byte)` frames, validates each step, and on failure re-seeks from an
owned copy of the last key it yielded. Unbounded back ends are rightmost
descents; the two ends of a double-ended scan stop when they meet.

## §11 Version chains

Every chain mutation holds the leaf's `chain_latch`, a four-byte lock
(`ChainLock`). Chain readers never validate it: they load `head` and `next`
with `Acquire`, paired with the writers' `Release` stores, so it needs no
version. It can die: the thread that unlinks the leaf kills it while holding
it (§13), after which every `lock` fails, and a writer that found the leaf
before the unlink looks the key up again rather than writing into an
unlinked chain. A dead lock is the leaf's removed state, and in the arena it
holds the leaf's retired-list link. A version node's flags (superseded,
tombstone, inline) live in the low bits of its 8-aligned `next` link; only
the latch holder writes the link and the superseded bit, and the tombstone
and inline bits never change. Positions are found under the latch. Same-version replacement is out of place. Inline slots are owned by
the leaf and never retired independently. `len` changes by the liveness of
the head before and after, decided under the latch. `prune_key` evaluates the
user's `is_tombstone` without any latch, re-checks under the latch, and
retires every detached heap node exactly once. `remove_version` unlinks one
node under the latch, or the whole leaf (§13) when it is the only one.

## §12 Arena

The arena buffer is aligned to 64 bytes; allocation is a check-then-bump CAS
that honours each type's alignment and never advances on failure. Arena maps
drop every key and value exactly once when dropped: the live tree, the
version chains, and retired lists of every leaf or version node unlinked
while the map was alive. An unlinked versioned leaf keeps its whole chain,
and is linked into the storage's retired list through its dead chain lock, so
it needs no field of its own. Allocation happens only in prepare phases; a failed
allocation releases every latch and returns the caller's key and value.

## §13 Delete-side unlinking and `shrink_to_fit`

**Removes.** A remove that takes the last entry of its leaf's node `N` unlinks
`N` from its parent `P` in the same critical section. A remove that leaves `N`
an entry locks only `N`, and a node left with a single entry stays: collapsing
it would make every remove and re-insert of a key beside one other key free a
node and allocate another.

- **Order.** `P` (or `root_latch`) by blocking `lock()` while holding nothing,
  then a re-check that it still points at `N`; `N` by `try_upgrade(v_N)`,
  restarting on failure. This is the grow and split order.
- **Commit.** Remove `N` from `P`; account `len` (Inv 12); mark `N` obsolete;
  then release `P`. `N`'s slots are not cleared: whoever is still inside `N`
  fails its next validation or upgrade. `N` is retired after `P` is released.
- **Follow-up.** If that leaves `P` empty, the remover releases every latch and
  unlinks `P` as a new top-down operation: it descends from the root along the
  removed key, then works upwards, taking each parent by `lock()` and a
  pointer re-check and each node by `try_upgrade` of the version its previous
  step unlocked it at. Any failure restarts the descent. At most two latches
  are held at a time.
- **No allocation.** Unlinking never allocates, so a remove never fails. The
  arena maps unlink too; an unlinked node's bytes stay in the arena, like a
  replaced leaf's.
- **Correctness does not depend on it.** An empty node is a state that
  readers, writers and the cursor handle. At quiescence, `validate` asserts
  that no inner node is empty, and that no `prefix_len` exceeds
  `MAX_PREFIX_LEN`.

**`shrink_to_fit`** (heap maps) walks the tree once, children before parents,
and fits each node `N`: an empty one is unlinked; one holding a single leaf is
replaced by that leaf; one holding a single inner child `C` is replaced by a
copy of `C` whose prefix is `N.prefix + byte + C.prefix`, when that fits in
`MAX_PREFIX_LEN`; any other is replaced by a copy in the smallest layout that
holds its children.

- **Out of place.** A replacement is allocated before any latch, as for
  growth, and filled while `N` (and `C`) are latched, so the copy is exact.
  Nothing published is rewritten.
- **Order.** `P` (or `root_latch`) by `lock()` while holding nothing and a
  re-check; `N` by `try_upgrade`; for a merge, `C` by `try_upgrade` of a
  version read while holding `N`. A failed upgrade retries a few times, then
  leaves the node as it is: the walk is best effort under concurrent writes.
- **Commit.** Publish the replacement (or unlink) in `P`; mark `C` and `N`
  obsolete; release `P`; retire them.
- It runs under one pin and holds at most three latches at a time. The arena
  maps do not offer it: their replaced nodes would only add to the arena.

**Versioned leaves.** A versioned leaf is unlinked by a prune (when its
newest version at or below the watermark is its newest version and a
tombstone), by `remove_key`, by `remove_version` of its only version, and by
`clear`. A delete is still a tombstone.

- The unlinker never takes an ART latch while holding a `chain_latch`: it
  evaluates any user code (`is_tombstone`, `AsBytes`) first, holding nothing,
  then descends and takes the ART latches as above, then the terminal
  `chain_latch`. Under it, it re-checks its condition, counts the head's
  liveness for `len`, and kills the lock, all before the unlinking store.
- A writer that found the leaf before the unlink therefore either linked its
  version first (and it goes with the leaf) or fails to lock and retries
  from the tree, where it finds no leaf or a new one. No version is written
  into an unlinked leaf.
- `clear` kills each detached leaf's lock under that leaf's node latch before
  counting its head, so `len` stays exact.
- The heap retires the leaf through EBR, and its drop frees the chain that is
  still linked to it; the arena puts it on the storage's retired list.
- A write at or below a watermark that already unlinked its key starts the
  key afresh; the watermark contract leaves such writes unsupported.