# Var Collections Critical Correctness

**Date:** 2026-05-15  
**Status:** Approved design  
**Scope:** `VarTree`, `VarMap`, shared SkipList node safety, and narrowly related tests  
**Review:** updated after `armdb/docs/superpowers/reviews/26-05-15-var-collections-critical-correctness.md`

## Context

The review in `armdb/docs/reviews/codex-vartree-varmap.md` validated several AI-generated reviews against the current code. The first implementation slice will address only critical correctness problems that can be fixed without changing the on-disk file format or redesigning the storage engine.

Breaking API changes are acceptable in this repository. However, any change that affects the on-disk format, storage architecture, or meaningful performance characteristics must be explicitly agreed before implementation.

## Goals

1. Remove unsound `Send` implementations from iterators that carry `seize::LocalGuard`.
2. Replace deletion marking that reinterprets `AtomicPtr<T>` as `AtomicUsize`.
3. Make `VarTree::insert_locked` handle `InsertResult::Exists`.
4. Turn oversized variable-value entries from panic into an explicit error.
5. Make encrypted locked-read paths return plaintext for `VarTree` and `VarMap`.
6. Add targeted regression tests for the behavior above where runtime tests are useful.

## Non-Goals

This slice will not change:

- `DiskLoc` layout or `file_id` width.
- Entry header, key/value serialization, padding, or file naming.
- Existing cache policy for supported value sizes.
- Direct-write support for values larger than `write_buffer_size`.
- `migrate` / hook semantics.
- Compaction stale-`DiskLoc` read semantics.
- Arbitrary-size multi-block value support beyond the existing write-buffer-sized value envelope.
- Replication `VarTree::apply_entry` semantics. That path already uses put-like behavior on `InsertResult::Exists` and is not changed by the insert-if-absent fix.

## Design

### Iterator Send Safety

`VarIter` contains `seize::LocalGuard`, which is intentionally local to the thread that entered the collector. It must not be moved to another thread. The unsafe `Send` implementation on `VarIter` will be removed.

The same pattern exists on `ConstIter` and `TypedIter`. Because they carry the same guard type, their unsafe `Send` implementations will be removed as part of the same safety fix. This is a breaking trait-bound change for downstream code that expected these iterators to be `Send`, but it does not change runtime behavior or stored data.

Other unsafe `Send` implementations are not removed in this slice unless they also carry `seize::LocalGuard`. In particular, `SkipList`, `*Node`, `VarTypedShard`, `ByteView`, and `AlignedBuf` have different safety arguments and remain out of scope for this fix.

No runtime regression test is planned for this. The compiler becomes the enforcement mechanism once the unsafe impls are gone.

### Explicit SkipList Mark State

Current node deletion marking stores the logical-delete bit in the low bit of `tower[0]` and implements `mark()` by casting `&AtomicPtr<Self>` to `&AtomicUsize`.

The fix will add an explicit atomic mark field to SkipList node structs and make:

- `is_marked()` read that atomic field.
- `mark()` set that atomic field with compare/exchange or swap semantics.
- tower pointers remain plain `AtomicPtr<Self>` values with no tag bits.
- `strip_mark()` remains as a compatibility helper for the existing call sites, but becomes an identity function. It must not cast pointers through integers once tower pointers no longer carry mark bits.

This changes only in-memory node layout. It does not affect any persisted data.

Performance impact: every mark check becomes an explicit atomic load instead of a tagged pointer load. This is accepted for this slice because the current implementation relies on a fragile unsafe aliasing assumption. The implementation should keep ordering conservative (`Acquire` for reads, `AcqRel` for marking) and avoid unrelated SkipList algorithm changes.

Correctness after splitting `(mark, next)` into separate atomics relies on the existing traversal shape: readers follow a tower pointer to a node, then check that node's mark flag before using its value. A reader may see a node that was marked and unlinked concurrently, but the active `seize` guard protects the allocation and the reader skips marked nodes. The next pointer is read separately and may itself lead to a marked neighbor, which will be skipped on the next loop iteration. This design does not require `SeqCst` or an atomic pair containing both mark and next pointer.

### `VarTree::insert_locked`

`VarTree::insert_locked` currently checks the index, writes an entry, allocates a `VarNode`, then ignores the result of `index.insert()`. It will be changed to match on `InsertResult`:

- `Inserted`: return `Ok(())`.
- `Exists`: free the rejected node, record the just-written entry as dead bytes for compaction accounting, and return `DbError::KeyExists`.

Normal public inserts for the same key already route to the same shard lock, so this is primarily a robustness and internal-edge fix. It keeps existing public semantics: insert-if-absent returns `KeyExists` if the key already exists.

`VarMap::insert_locked` does not need the same fix because it holds the per-shard `HashMap` lock across the existence check and insert.

The rejected `node_ptr` in `insert_locked` is different from the unused node in `put_locked`'s `Exists` slow path. In `insert_locked`, the new node has never been published and uniquely owns its freshly allocated `DiskLoc` box, so `VarNode::dealloc_node(node_ptr)` should free it normally. The `disk.store(null)` trick used in `put_locked` should not be copied here unless the implementation first transfers that `DiskLoc` pointer elsewhere.

### Oversized Variable Entries

Variable-value writes currently serialize a full entry into a `Vec` and copy it into `WriteBuffer`. If the serialized entry is larger than `write_buffer_size`, the copy can panic.

This slice will make the current implicit limit explicit:

- if `entry_size(key_len, value_len) > write_buffer_size`, `append_entry` returns `DbError::Client("entry exceeds write_buffer_size")` before consuming a GSN or modifying the write buffer;
- no direct-write path is added;
- no multi-buffer write path is added;
- the effective max value remains `write_buffer_size - EntryHeader - key_len - padding`.

### Encrypted Locked Reads

`VarTree::read_value_locked` and `VarMap::read_value_locked` are used by CAS, update/fetch_update, delete/put old-value hooks, and shard-handle reads. They currently read flushed data through `direct::pread_value`, which is not encryption-aware.

The fix will route the disk-read part of locked reads through an encryption-aware helper:

- first check the active write buffer as today;
- for flushed active or immutable files, read plaintext using the same encryption rules as shard value/block reads;
- in non-encrypted builds, keep the current plain read behavior;
- do not change the public API.

The helper should be a `pub(crate)` method or helper in `shard.rs` that accepts `&ShardInner` and `&DiskLoc`, chooses the active or immutable file from that already-locked state, and performs the correct plain/encrypted read. It must not take the shard mutex again. `VarTree::read_value_locked` and `VarMap::read_value_locked` already run with the shard lock held, so a helper that calls `Shard::lock()` or reuses `Shard::read_value()` directly would deadlock. The implementation should preserve the current behavior that locked reads may perform disk I/O while holding the shard lock.

## Error Handling

Oversized entries must return `DbError::Client("entry exceeds write_buffer_size")` and leave in-memory and on-disk state unchanged for that attempted entry.

Encrypted locked reads should preserve existing error surfaces where possible. Public methods that currently map read failures to `KeyNotFound` or `None` may keep that behavior in this slice, but the read must return plaintext when data exists and decryption succeeds.

`VarTree::insert_locked` must free any rejected node allocation on `Exists` and must not return `Ok(())` for a duplicate insert.

## Tests

Targeted tests are allowed for this task.

Planned coverage:

1. `VarTree` duplicate insert edge: verify duplicate insert returns `DbError::KeyExists` and does not corrupt the existing value.
2. Oversized variable value:
   - `VarTree` returns an error for a value whose serialized entry exceeds `write_buffer_size`.
   - `VarMap` returns an error for the same case.
   - the tests must not rely on panic catching as the expected behavior.
3. Encrypted locked read:
   - with `feature = "encryption"` and `var-collections`, write a value, flush it, then `cas` or `update` must compare plaintext and succeed for `VarTree`;
   - mirror the same for `VarMap` if the existing test structure makes it straightforward;
   - the test must avoid public `get()` before the locked operation, because `get()` can populate block cache with plaintext;
   - the value should cross a 4096-byte block boundary, for example a value larger than `4096 - (EntryHeader + key_len)`, so the single-block cache branch in `read_value_locked` is skipped and the test exercises the encrypted disk-read path.
4. Existing SkipList Miri/Loom/basic tests should continue to cover node lifecycle after explicit mark-state changes.

No test is required for removing iterator `Send` unless the repository already has a compile-fail test framework. The absence of the unsafe impl is the fix.

## Verification

After implementation:

1. Run `cargo fmt`.
2. Run targeted tests for changed behavior.
3. Run encryption-targeted tests when the encryption fix is implemented.
4. Run shared SkipList lifecycle tests if node marking changes touch shared SkipList code.

Full workspace `cargo test` is useful after this slice because shared SkipList code affects many collections, but it can be decided during implementation based on targeted test results and runtime cost.

## Follow-Up Work

Separate specs should handle:

- `migrate` / hook semantics for `VarTree` and `VarMap`.
- `DiskLoc.file_id` overflow and any related file-format decision.
- compaction behavior for readers holding stale copied `DiskLoc` values.
- direct-write or arbitrary multi-block cache support for values larger than the write buffer.
