# Code Review: VarTree, VarNode, and SkipList

**Author:** Kimi K2.6  
**Date:** 2026-05-15  
**Scope:** `armdb/src/var_tree.rs`, `armdb/src/skiplist/mod.rs`, `armdb/src/skiplist/node.rs`, `armdb/src/byte_view.rs`, `armdb/src/cache.rs`, `armdb/src/hook.rs`  

---

## Overall Assessment

The architecture is well-thought-out: RCU update of `DiskLoc` via `AtomicPtr` + `seize` for memory reclamation is the correct and efficient path for a concurrent LSM-like engine. The three-level read path (write buffer → block cache → disk) is logical. Lock-free reads + `Mutex` on shard writes is a reasonable trade-off for the current phase.

---

## Critical Issues

### 1. `mark()` — Aliasing `AtomicPtr` as `AtomicUsize` (UB)

**Location:** `skiplist/node.rs` — `VarNode::mark`, `ConstNode::mark`, `TypedNode::mark`

```rust
fn mark(&self) -> bool {
    let atomic_usize: &AtomicUsize =
        unsafe { &*(self.tower(0) as *const AtomicPtr<Self> as *const AtomicUsize) };
    let old = atomic_usize.fetch_or(1, Ordering::AcqRel);
    old & 1 == 0
}
```

**Problem:** `AtomicPtr<T>` and `AtomicUsize` are **different types** in Rust. `AtomicPtr` has `repr(C)` layout, but ABI compatibility guarantees between pointers and `usize` in Rust are **not a documented contract**. On some platforms (especially CHERI or future architectures) `*mut T` can be larger than `usize`. Even on x86_64 this is **technically UB** through Rust's strict aliasing rules.

Additionally, `mark` uses a tag-bit in the least-significant bit of the pointer. This is only valid if all pointers are aligned to at least 2 (true for heap allocations), but this is an **unchecked invariant**.

**Recommendation:** Use `AtomicUsize` for `tower[0]` explicitly, or `portable-atomic` with `fetch_or`, or better yet — allocate a separate `AtomicBool` / `AtomicU8` for the mark flag. An extra 1-8 bytes per node is negligible compared to the risk of UB.

---

### 2. `DiskLoc` Dangling Reference After Separate `retire`

**Location:** `var_tree.rs` (`put_locked`, `cas`, `update_inner`), `skiplist/node.rs` (`VarNode::dealloc_node`)

```rust
unsafe fn dealloc_node(ptr: *mut Self) {
    let height = (*ptr).height;
    let disk = *(*ptr).disk.get_mut(); // or unsync_load()
    if !disk.is_null() {
        drop(Box::from_raw(disk)); // <-- frees DiskLoc
    }
    std::ptr::drop_in_place(&mut (*ptr).key);
    let layout = Self::layout_for(height);
    std::alloc::dealloc(ptr as *mut u8, layout);
}
```

In `put_locked`:

```rust
let old_disk_ptr = existing.swap_disk(new_disk);
let old_disk = unsafe { *old_disk_ptr };
inner.add_dead_bytes(...);
unsafe {
    self.index.collector().retire(old_disk_ptr, seize::reclaim::boxed::<DiskLoc>);
}
```

**Problem:** `dealloc_node` is called from `SkipList::remove` **after** `self.collector.retire(found, N::reclaim)`. `seize` guarantees no active `Guard`s, but `load_disk()` returns a **raw pointer** `*mut DiskLoc`, which readers may hold:

```rust
pub fn load_disk(&self) -> &DiskLoc {
    let ptr = self.disk.load(Ordering::Acquire);
    unsafe { &*ptr }
}
```

If between `swap_disk()` and `retire(old_disk_ptr)` another thread calls `load_disk()` and gets `&DiskLoc`, that reference becomes **dangling** after `drop(Box::from_raw(disk))` in `dealloc_node`, because the `VarNode` retire and `DiskLoc` retire are **independent** calls with different lifetimes.

`seize` does not save this, because the reader registered a guard **for the node**, not for the separate `DiskLoc` allocation.

**Recommendation:** Embed `DiskLoc` directly inside `VarNode` (as in `ConstNode` with `UnsafeCell<DiskLoc>`), or use `UnsafeCell<DiskLoc>` + copy-on-read instead of returning a reference to a separately-allocated heap object. If you must keep the pointer, ensure readers copy the `DiskLoc` value before releasing the guard, and never hold references across the read function boundary.

---

### 3. `VarIter: Send` with `seize::LocalGuard`

**Location:** `var_tree.rs`

```rust
unsafe impl<K: Key, H: WriteHook<K>> Send for VarIter<'_, K, H> {}
```

`VarIter` contains:

```rust
pub struct VarIter<'a, K: Key, H: WriteHook<K> = NoHook> {
    ...
    _guard: seize::LocalGuard<'a>,
}
```

**Problem:** `seize::LocalGuard` is **thread-local** by design. It is `!Send`. Implementing `Send` for `VarIter` manually bypasses this invariant and is **unsound**. Moving the iterator to another thread means moving a thread-local guard, which will lead to undefined behavior in `seize`'s internal thread-local collector state.

**Recommendation:** Remove the `unsafe impl Send`. If cross-thread iterators are required, switch to `seize::OwnedGuard` (if `seize` supports it) or redesign so that the iterator does not carry a thread-local guard.

---

## Medium-Priority Issues

### 4. `ByteView` Reference Counting — Relaxed Ordering May Drop Refs

**Location:** `byte_view.rs`

```rust
impl Clone for ByteView {
    fn clone(&self) -> Self {
        if !self.is_inline() {
            self.rc().fetch_add(1, Ordering::Relaxed);
        }
        ...
    }
}

impl Drop for ByteView {
    fn drop(&mut self) {
        if !self.is_inline() {
            let rc = self.rc();
            if rc.fetch_sub(1, Ordering::AcqRel) == 1 {
                // dealloc
            }
        }
    }
}
```

**Problem:** `fetch_add` uses `Relaxed`, while `fetch_sub` uses `AcqRel`. When `fetch_sub == 1`, the thread performing deallocation sees its own writes, but **does not guarantee** visibility of writes from other threads that performed `fetch_add(Relaxed)`. The deallocation itself creates a data race on the pointed-to data if another thread is still reading `ptr` after its `fetch_add(Relaxed)`.

In practice this works on x86_64 (strong memory model), but formally it is a **data race** under the C++ memory model.

**Recommendation:** Change `fetch_add(1, Ordering::Relaxed)` to `fetch_add(1, Ordering::Release)` (or `AcqRel`). The overhead is negligible on x86_64 and correct on weakly-ordered architectures.

---

### 5. `SkipList::insert` — `height` Race During Recovery

**Location:** `skiplist/mod.rs`

```rust
let mut current_height = self.height.load(Ordering::Relaxed);
while node_height > current_height {
    match self.height.compare_exchange_weak(
        current_height, node_height, Ordering::Relaxed, Ordering::Relaxed
    ) { ... }
}
let search_height = self.height.load(Ordering::Relaxed);
```

**Problem:** Between bumping `self.height` and actually linking the new level into `head.tower()`, another thread may observe the increased height but see a `null` in `head.tower(new_level)`. This causes search to terminate early, making the newly-linked nodes invisible from that level (they remain reachable from lower levels, so correctness is preserved, but **performance degrades** unpredictably).

**Recommendation:** Initialize `head.tower()` for new levels **before** publishing the new `height`, and use `Release` / `Acquire` ordering for the height update.

---

### 6. `resolve_front_asc` / `resolve_front_rev` — Dereferencing `*ge` Without Guard Coverage

**Location:** `var_tree.rs`

```rust
fn resolve_front_asc(&self, bound: &Bound<&K>, guard: &seize::LocalGuard<'_>) -> *mut VarNode<K> {
    let ge = self.index.find_first_ge(k.as_bytes(), guard);
    if !ge.is_null()
        && !unsafe { &*ge }.is_marked()
        && unsafe { &*ge }.key_bytes() == k.as_bytes()
    {
        ...
    }
}
```

**Note:** The `guard` is passed into `find_first_ge`, and `VarIter` stores the returned raw pointer together with the guard. This is safe **as long as** the pointer is not dereferenced after the guard is dropped. The current code appears correct, but any future refactoring that separates the pointer from the guard lifetime would introduce a use-after-free.

**Recommendation:** Add a code comment documenting that the returned raw pointer is only valid while the `guard` is alive, and that `VarIter` must keep them together.

---

## Low-Priority Issues

### 7. `prefix_to_end_bound` — Potential Panic on Long Prefix

**Location:** `var_tree.rs`

```rust
fn prefix_to_end_bound<K: Key>(prefix: &[u8]) -> Bound<K> {
    let mut incremented = prefix.to_vec();
    // ...
    let mut end = K::zeroed();
    end.as_bytes_mut()[..incremented.len()].copy_from_slice(&incremented);
    Bound::Excluded(end)
}
```

**Problem:** If `prefix.len() > size_of::<K>()` this will panic at `copy_from_slice`. There is no runtime check.

**Recommendation:** Add `assert!(prefix.len() <= size_of::<K>());` or truncate gracefully.

---

### 8. `disk.offset` is `u32` — Implicit 4 GiB Per-File Limit

**Location:** `disk_loc.rs`, `var_tree.rs` (`read_value_locked`, `read_value_cached`)

```rust
pub struct DiskLoc {
    pub offset: u32,
    pub len: u32,
    pub file_id: u16,
    pub shard_id: u8,
    _pad: u8,
}
```

`disk.offset` is 32-bit, so each file is capped at 4 GiB. With `file_id: u16`, the maximum addressable space per shard is ~256 TiB. This is reasonable for an LSM, but should be **documented** in `DiskLoc` or `Config` docs.

---

### 9. `migrate` — Calling `put` / `delete` While Holding an Index Guard

**Location:** `var_tree.rs`

```rust
pub fn migrate(...) {
    let _guard = self.index.collector().enter();
    while !current.is_null() {
        // ...
        match f(&node.key, &value) {
            MigrateAction::Update(new_value) => {
                self.put(&node.key, &new_value)?;  // acquires new guard + shard lock
            }
            MigrateAction::Delete => {
                self.delete(&node.key)?;           // same
            }
        }
    }
}
```

**Problem:** `migrate` holds an index guard for the entire walk, then calls `put`/`delete` which acquire **another** guard and shard locks. This is safe in the current design (weakly-consistent iteration), but it is a **latency and resource-usage concern**: a long-running migration keeps a `seize` guard active, potentially delaying memory reclamation for all retired nodes.

**Recommendation:** Document this behavior explicitly. If migration is expected to be long-running, consider dropping and re-acquiring the guard periodically, or use an `OwnedGuard` if available.

---

### 10. `update_if_match` — ABA on `DiskLoc` Value (Theoretical)

**Location:** `var_tree.rs` (`CompactionIndex` impl)

```rust
let current_disk = unsafe { *current_ptr };
if current_disk == old_loc {
    // CAS on pointer
}
```

**Problem:** The code compares **values** (`DiskLoc` equality) before doing a pointer-CAS. If the same `old_loc` value were ever reallocated and reused, this would be an ABA problem. However, `DiskLoc` contains `file_id` and `offset`, and compaction generates new `file_id`s, so the probability of ABA is effectively zero in the current design.

**Note:** The pointer-CAS itself is correct because `DiskLoc` pointers are unique `Box` allocations and are never reused.

---

## Summary — Priorities

| Priority | Issue | File | Suggested Action |
|---|---|---|---|
| 🔴 Critical | `mark()` — aliasing `AtomicPtr` as `AtomicUsize` | `skiplist/node.rs` | Replace with `AtomicUsize` for `tower[0]` or a dedicated mark field |
| 🔴 Critical | `DiskLoc` dangling ref after separate `retire` | `var_tree.rs`, `skiplist/node.rs` | Embed `DiskLoc` into `VarNode` or use `UnsafeCell<DiskLoc>` |
| 🔴 High | `VarIter: Send` with `LocalGuard` | `var_tree.rs` | Remove `Send` impl or switch to `OwnedGuard` |
| 🟡 Medium | `ByteView` relaxed refcount | `byte_view.rs` | Use `Release` for `fetch_add` |
| 🟡 Medium | `SkipList::height` race | `skiplist/mod.rs` | Initialize `head.tower` before height bump |
| 🟢 Low | `prefix_to_end_bound` overflow | `var_tree.rs` | Add `assert` or truncate |
| 🟢 Low | `u32` offset limit | `disk_loc.rs` | Document the 4 GiB per-file limit |
| 🟢 Low | `migrate` long guard lifetime | `var_tree.rs` | Document or re-acquire guard periodically |

---

## Positive Notes

- `seize` integration is clean and well-isolated.
- `WriteHook` zero-overhead design with `NoHook` is elegant.
- Block cache invalidation during compaction (`invalidate_file`) is correctly implemented.
- `VarShard` atomic batch API is a good ergonomic addition.
- The separation of `put_locked` / `insert_locked` / `delete_locked` keeps the public API simple while allowing internal reuse.

---

*End of review.*
