# VarTree / VarNode — Deep Review (DeepSeek)

Date: 2026-05-15

## 🔴 Critical Bug 1: `insert_locked` ignores `InsertResult::Exists`

**File:** `src/var_tree.rs`, lines 360–377

```rust
fn insert_locked(&self, shard_id, inner, guard, key, value) -> DbResult<()> {
    if self.index.get(key.as_bytes(), guard).is_some() {
        return Err(DbError::KeyExists);
    }
    let (disk_loc, _gsn) = inner.append_entry(...)?;   // already wrote to disk!
    let height = random_height();
    let node_ptr = VarNode::alloc(*key, disk_loc, height);
    self.index.insert(node_ptr, guard);                 // result IGNORED
    Ok(())
}
```

**Problem:** Between the `index.get()` check and `index.insert()`, another shard can insert the
same key via `put_locked`. `insert()` returns `InsertResult::Exists`, but:

- `append_entry()` already committed a disk write — **wasted space** (until compaction)
- `VarNode::alloc()` allocated a node — **memory leak**, nobody frees it
- The new `DiskLoc` is orphaned — data is lost permanently

**Comparison:** `ConstTree::insert_locked` (L494–503) correctly handles this case:

```rust
InsertResult::Exists(_) => {
    inner.write_discard(loc)?;
    unsafe { ConstNode::<K, V, D::Loc>::dealloc_node(node_ptr); }
    Err(DbError::KeyExists)
}
```

The same bug exists in `TypedTree::insert_locked` (`typed_tree.rs`, L460).

**How to reproduce:** Two threads concurrently `insert` the same key routed to different shards
(rare but possible when `shard_for(key)` collides).

**Fix:** Match on `self.index.insert()` result. On `Exists`, null out `disk`, deallocate the node,
and return `Err(DbError::KeyExists)`. The disk write cannot be undone for Bitcask/VarTree (unlike
`write_discard` for FixedStore), but it will be cleaned by compaction.

---

## 🟡 Potential Bug 2: `read_value_cached` — spanning value + cache hit skips write buffer

**File:** `src/var_tree.rs`, lines 726–761

```rust
fn read_value_cached(&self, disk: &DiskLoc) -> Option<ByteView> {
    // 1. Block Cache
    if let Some(block) = self.cache.get(&cache_key) {
        return Self::extract_from_block(&block, start, len, || {
            self.get_or_read_block(..., block_offset + 4096)  // no write buffer check!
        });
    }
    // 2. Write Buffer — only reached if step 1 missed
    { ... }
    // 3. Disk read + cache
    ...
}
```

**Problem:** When a value spans two blocks (> ~4KB) and the first block hits in cache, step 2
(write buffer check) is **skipped entirely**. The second block is fetched via `get_or_read_block`
→ `shard.read_block()`, which does **not** check the write buffer — it reads directly from disk.

If the data hasn't been flushed yet (still in write buffer), the second block read from disk will
return stale data or zeros.

**Realism:** Low. Requires:
- Value > (4096 − offset_in_block) bytes (rare)
- First block already cached (from a prior read)
- Data still unflushed in write buffer

**Fix:** In `extract_from_block` for the spanning case, check the write buffer first, similar to
step 2 logic in `read_value_cached`. Or unify: for spanning values, always fall through to
`read_value_locked` (which uses `pread_value`, correct for any size).

---

## 🟡 Concern 3: `SkipList::insert` returns `Exists` without re-checking `is_marked()`

**File:** `src/skiplist/mod.rs`, line 177

```rust
match self.key_cmp(next_ref.key_bytes(), key) {
    std::cmp::Ordering::Equal => {
        return InsertResult::Exists(next_ref);  // no is_marked() guard here
    }
}
```

**Analysis:** The `is_marked()` check happens earlier in the loop, before `key_cmp`. Between that
check and the `return`, a concurrent `remove` could mark the node. However, `insert` holds
`write_lock`, which serializes all modifications — so no concurrent `remove` can happen.

**Verdict:** NOT a bug under the current `write_lock` model.

**Future risk:** The design document plans to replace `write_lock` with CAS-based linking for
fully lock-free inserts. At that point, this TOCTOU race becomes real. Consider adding a
`debug_assert!(!next_ref.is_marked())` or an explicit re-check before returning.

---

## 🟢 Observation 4: `read_value_locked` does not cache spanning values

**File:** `src/var_tree.rs`, lines 934–970

```rust
fn read_value_locked(&self, disk: &DiskLoc, inner: &ShardInner) -> Option<ByteView> {
    // 2. Block cache (lock-free)
    if start + len <= 4096 {  // only for non-spanning!
        // check cache...
    }
    // 3. Disk read — pread_value handles any size
    let bytes = direct::pread_value(file, disk.offset as u64, len).ok()?;
    Some(ByteView::new(&bytes))
}
```

For spanning values (`start + len > 4096`), the block cache is neither checked nor populated.
Not a bug — `pread_value` does a direct read in any case. This is just slightly inconsistent with
`read_value_cached`. Low-priority micro-optimization.

---

## 🟢 Observation 5: `resolve_front_asc` and `resolve_front_rev` are duplicates

**File:** `src/var_tree.rs`, lines 444–498

The two functions have **identical implementations**. They are used as:
- `reversed=false` → `resolve_front_asc(&start, &guard)`
- `reversed=true` → `resolve_front_rev(&end, &guard)`

The only difference is which bound argument is passed. Duplication risks bugs when one function
is modified and the other is forgotten. Consider consolidating into a single `resolve_front`.

---

## 🟢 Observation 6: `migrate` — hook called with `old_value = None` for `Keep`

**File:** `src/var_tree.rs`, lines 679–722

```rust
MigrateAction::Keep => {
    self.hook.on_write(&node.key, None, Some(&value));
}
```

For `Keep`, the value does not change, but `old_value` is passed as `None` even though the actual
old value is available (it equals the new value). For a `WriteHook` implementation, this makes
`Keep` indistinguishable from `Insert`. If the distinction matters to the hook, this is a
semantic bug. If not, it's an API inconsistency.

---

## 🟢 Observation 7: `put` — `old_value` for `NEEDS_OLD_VALUE` may read from a deleted node

**File:** `src/var_tree.rs`, lines 220–240

```rust
let old_value = if H::NEEDS_OLD_VALUE {
    if let Some(node) = self.index.get(key.as_bytes(), &guard) {
        let disk = *node.load_disk();
        self.read_value_locked(&disk, &inner)
    } else { None }
} else { None };
self.put_locked(...)?;
```

Between reading `old_value` and `put_locked`, the node could be marked (deleted) by another
thread. Since both threads go through the same shard lock, there's no race. However, if `put`
is called **after** the key was deleted in another thread (serialized by shard lock), `old_value`
comes from an already-marked node. Semantically debatable: the hook receives `old_value` from a
deleted entry. Acceptable in practice, but worth noting.

---

## 🟢 Observation 8: `recover_var_hint` does `drop(Box::from_raw)` instead of `retire`

**File:** `src/recovery.rs`, lines 501–511

```rust
InsertResult::Exists(existing) => {
    let new_disk = Box::into_raw(Box::new(disk));
    let old_disk = existing.swap_disk(new_disk);
    unsafe { drop(Box::from_raw(old_disk)) }  // direct drop, not retire!
    ...
}
```

During recovery there are no concurrent readers, so direct `drop` is safe (no need for
`seize::retire`). However, if recovery ever becomes concurrent (parallel recovery of
multiple files), this would become a use-after-free. Consider adding a comment explaining
why direct drop is safe in this context.

---

## ✅ What's Done Well

1. **Convergence logic in `VarIter`** — the complex `next()`/`next_back()` interaction with
   `done`, `converged`, `check_end`/`check_start` is correct across multiple interleaving
   scenarios (manually traced).

2. **`reversed` ordering** — clean design with inverted `key_cmp` in `SkipList`. No code
   duplication for different directions in the core data structure.

3. **`put_locked` fast-path / slow-path** — avoids `write_lock` and node allocation for
   existing keys, only holds the shard lock.

4. **GSN-based conflict resolution in VarTree recovery** — unlike ConstTree, VarTree recovery
   uses `key_gsn: HashMap` to pick the winner by GSN, which is correct when recovery files
   are processed in arbitrary order.

5. **`VarNode::dealloc_node` with disk null-out** — in `put_locked` on `Exists`, the code
   stores `null` in `disk` before `dealloc_node`. This prevents double-free of the `DiskLoc`.

6. **Weak consistency model** — well-documented. Readers may see stale data, but never
   undefined behavior. Memory safety is guaranteed via `seize` guards.

---

## Summary

| # | Severity | Description | File:Line |
|---|----------|-------------|-----------|
| 1 | 🔴 Critical | `insert_locked` ignores `InsertResult::Exists` → memory leak + wasted disk | `var_tree.rs:360-377` |
| 2 | 🟡 Potential | `read_value_cached` spanning value skips write buffer | `var_tree.rs:726-761` |
| 3 | 🟢 Future | `SkipList::insert` TOCTOU on `is_marked()` if `write_lock` removed | `skiplist/mod.rs:177` |
| 4 | 🟢 Style | Duplicate `resolve_front_asc` / `resolve_front_rev` | `var_tree.rs:444-498` |
| 5 | 🟢 API | `migrate` Keep passes `old_value=None` | `var_tree.rs:679-722` |
