Skip to content

fix(storage): remove stale positions HashMap from LRU cache - #147

Merged
adityamukho merged 1 commit into
mainfrom
fix/lru-cache-positions-corruption
Apr 17, 2026
Merged

adityamukho merged 1 commit into
mainfrom
fix/lru-cache-positions-corruption

Conversation

@adityamukho

Copy link
Copy Markdown
Collaborator

Root cause

The positions HashMap introduced in #146 (perf/hashmap-lru-touch) became stale after every eviction. pop_front() shifts all remaining VecDeque indices by 1, but the stored positions were never updated. On the next touch() call from put_dirty(), the code read the stale (off-by-one) position, popped the real last element, then tried self.order[stale_pos] — which was now past the end of the deque.

This caused all file-backend benchmarks to panic immediately:

thread 'main' panicked at src/storage/cache.rs:45:23:
Out of bounds access

The in-memory benchmarks weren't affected because they don't exercise the put_dirty → touch path in the same way.

Fix

Remove the positions HashMap entirely. Replace with an O(N) iter().position() scan in touch(). For the default 256-page cache this is negligible — touch() is only called from put_dirty(), which already holds a write lock.

Regression test

Added test_put_dirty_after_eviction_does_not_panic which reproduces the exact failure sequence: fill cache to capacity, trigger an eviction, then call put_dirty on a still-cached page to exercise touch() with previously-stale indices.

Test plan

  • cargo test — 793 tests pass, 0 failures
  • Pre-push hooks (fmt, clippy, full test suite) — all green

🤖 Generated with Claude Code

The positions HashMap introduced in perf/hashmap-lru-touch was
fundamentally broken: every pop_front eviction shifts all remaining
VecDeque indices by 1, but stored positions were never updated.
This caused touch() to index beyond the end of the order deque,
panicking all file-backend benchmarks with 'Out of bounds access'
at cache.rs:45.

Replace with an O(N) iter().position() search in touch(). For the
default 256-page cache this is negligible — touch() is only called
from put_dirty(), which already holds a write lock.

Also add a regression test that reproduces the exact failure
sequence: fill cache, evict LRU, then call put_dirty on a still-
cached page to trigger touch() on stale indices.

Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
@codecov

codecov Bot commented Apr 17, 2026 •

Copy link
Copy Markdown

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 83.41%. Comparing base (c88e666) to head (41aa5f8).
⚠️ Report is 1 commits behind head on main.

Additional details and impacted files

Impacted file tree graph

@@           Coverage Diff           @@
##             main     #147   +/-   ##
=======================================
  Coverage   83.41%   83.41%           
=======================================
  Files          26       26           
  Lines        4823     4811   -12     
=======================================
- Hits         4023     4013   -10     
+ Misses        800      798    -2     
Files with missing lines Coverage Δ
src/storage/cache.rs 86.53% <100.00%> (+0.60%) ⬆️
🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

@adityamukho
adityamukho merged commit 07b3e9a into main Apr 17, 2026
22 checks passed
@adityamukho
adityamukho deleted the fix/lru-cache-positions-corruption branch April 17, 2026 12:13
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant