Skip to content

catalog.md

Latest commit

 

History

History
208 lines (152 loc) · 14.9 KB

catalog.md

File metadata and controls

208 lines (152 loc) · 14.9 KB
Raw

Testing Catalog

Reference for testing types used in CacheKit, types we do not use yet, and coverage gaps worth closing. For how to run tests and contributor workflows, see Testing strategy. For the policy semantic harness, see Policy semantic testing and the policy spec matrix.

Overview

CacheKit combines several layers: unit tests close to implementation, property tests and semantic oracles for eviction correctness, fuzz targets for data-structure robustness, Miri for undefined-behavior smoke checks, integration tests for concurrency and composition, and Criterion benchmarks for performance analysis.

Not every testing type applies to every component. Exact eviction policies benefit most from model-based dual-run tests; adaptive policies need weaker legal-set oracles; concurrent wrappers need stress tests and thread-safety tooling; product-facing performance claims belong in benchmarks with optional regression gates.

         fast / cheap                          slow / expensive
              │                                        │
  unit ───────┼── property ─── integration ─── fuzz ─── formal
              │         │              │          │
              │    policy_semantics    │     Miri / Loom
              │    (model dual-run)    │
              └──────── benchmarks / workload sim ────────┘

What CacheKit uses today

Type Purpose Location / entrypoint CI
Unit tests Specific behaviors and edge cases #[cfg(test)] mod tests in src/ Partial — filtered Miri on --lib ds:: / policy::; not full mod tests in main test job
Property tests (in-module) DS invariants over random inputs #[cfg(test)] mod property_tests in src/ds/, some policies PROPTEST_CASES=1000 cargo test --lib property_tests (property-tests job)
Policy semantic tests Eviction/residency oracles vs implementations tests/abstract_models/, tests/policy_semantics/ cargo test --test policy_semantics --all-features; higher case count in property-tests job
Dual-impl equivalence Two implementations, same trace tests/policy_semantics/dual_impl_tests.rs Via cargo test --test policy_semantics --all-features
Integration tests Multi-module wiring tests/lru_integration_test.rs, tests/ttl_integration_test.rs, other tests/*.rs cargo test --tests --all-features (main test job)
Cross-policy invariants Library-wide consistency tests/policy_invariants.rs cargo test --tests --all-features
Concurrency / stress Races and atomicity under load tests/*_concurrency.rs, tests/slab_concurrency.rs cargo test --tests --all-features; lru_concurrency / slab_concurrency need concurrency feature
O(1) regression Algorithmic complexity guards tests/performance_regression.rs cargo test --tests --all-features
Fuzz tests Crashes and invariant violations on mutated input fuzz/fuzz_targets/ (27 targets, DS layer) PR smoke (60s/target), nightly continuous
Miri Undefined-behavior smoke checks Lib ds:: / policy:: (filtered) + policy_semantics smoke_* Dedicated Miri job
Doc tests Rustdoc examples compile and run /// examples in src/ cargo test --doc --all-features
Example tests examples/ compile and pass examples/ cargo test --examples --all-features
Benchmarks Throughput, hit rate, cross-policy comparison benches/, bench-support/ cargo bench on main only
Static analysis Style, lints, deps, security clippy, rustfmt, cargo audit, cargo deny Dedicated CI jobs
Formal verification (manual) Reachable-state invariants on finite instances docs/testing/specs/formal/ (FIFO, LRU TLA+) Not in CI; run ./scripts/run-tlc.sh locally
MSRV check Minimum supported Rust Cargo.toml MSRV Dedicated CI job

Policy semantic coverage by tier

Canonical per-policy status: matrix.md.

Tier Harness mode Policies Oracle strength
Exact DualRun + CrossModel FIFO, LRU, Fast-LRU, LIFO, MRU, LFU, Heap-LFU, MFU, LRU-K Strong — independent reference/ models for all exact-tier policies
Mirror DualRun Clock, 2Q, SLRU, NRU Medium — exact/ models mirror implementation shape; specs still stub
Bounded InvariantOnly ARC, CAR, Clock-PRO, S3-FIFO Weak — structural invariants only; victim legal sets deferred
Composed DualRun + deadlines TTL Medium — LruOccupancyModel + TTL integration tests; spec still stub
Deferred — Random None — no semantic harness

Concurrency test coverage

Three policies ship native Concurrent* wrappers today (LRU, FIFO, S3-FIFO). See Concurrency.

Integration concurrency tests in tests/ cover FIFO, LFU, LRU, LRU-K, NRU, and ConcurrentSlabStore. Only lru_concurrency.rs and slab_concurrency.rs require the concurrency feature; the other *_concurrency.rs files run unconditionally. lru_concurrency.rs exercises ConcurrentLruCache; FIFO, LFU, and NRU use ad-hoc Arc<Mutex<…>> wrappers around sequential cores rather than native Concurrent* types. ConcurrentS3FifoCache has in-module tests in src/policy/s3_fifo.rs but no dedicated tests/*_concurrency.rs file.

Performance regression coverage

performance_regression.rs verifies O(1) scaling for LRU, LRU-K, LFU, Clock, and S3-FIFO only. Other policies rely on unit tests and semantic harnesses for correctness, not complexity guards.

Fuzz coverage

All 27 fuzz targets exercise internal data structures (ClockRing, SlotArena, GhostList, etc.), not end-to-end cache policy APIs. See Fuzzing in CI/CD and fuzz/README.md.

Testing types not used (or barely used)

The tables below list other testing types common in systems and Rust libraries. Relevance indicates how well each type fits CacheKit.

Correctness and semantics

Type What it checks CacheKit today Relevance
Golden / snapshot tests Output matches a saved baseline Not used Low — semantic oracles are more stable for caches
Model-based testing Random traces vs a reference model Core of policy_semantics High — already central
Equivalence testing Two implementations, same behavior dual_impl_tests.rs (LRU/Fast-LRU, Clock/ClockRing) High — extend to more pairs
Differential testing Output matches an external library on same traces Cross-library benches only Medium — good for hit-rate sanity, not CI today
Formal verification All reachable states satisfy invariants TLA+ for FIFO/LRU (manual) Medium — complementary to proptest
Symbolic / concolic execution Systematic path exploration Not used Low for this codebase size
Mutation testing Tests catch injected bugs Not used Medium — validates harness strength

Input exploration

Type What it checks CacheKit today Relevance
Property-based testing Invariants over random inputs proptest throughout High — already central
Fuzz testing Panics and invariant breaks on arbitrary bytes DS layer only High — policy-level fuzz is a gap
Regression corpora Saved minimal failing inputs tests/proptest-regressions/ Medium — expand as failures shrink
Adversarial testing Hash-collision DoS, untrusted keys Documented (KeysAreTrusted) Medium — no dedicated suite

Concurrency and runtime

Type What it checks CacheKit today Relevance
Concurrency / stress tests Races under threaded load Partial (*_concurrency.rs) High
Miri UB detection under interpreted execution Curated subset High — extend to TTL smoke
Loom / Shuttle Exhaustive interleavings on small models Not used High for Concurrent* wrappers
Sanitizer CI (TSan/ASan) Runtime memory and thread bugs Not in CI Medium — pairs well with concurrency tests

Performance and capacity

Type What it checks CacheKit today Relevance
Micro-benchmarks Op latency and throughput Criterion in benches/ High — already central
Workload simulation Zipfian, scan, mixed R/W benches/workloads.rs High — benchmarks only
Complexity / scaling tests O(1) vs O(n) as size grows 5 policies in performance_regression.rs High — expand coverage
Performance regression gates CI fails on perf drop vs baseline Benches on main only Medium — optional nightly/PR gate
Memory / allocation profiling Allocs in hot paths Not automated Medium — aligns with design goals
Soak / endurance tests Long-run leaks and drift Not used Low–medium — nightly fuzz partially covers

Build, platform, and delivery

Type What it checks CacheKit today Relevance
Feature-matrix testing All Cargo feature combinations --all-features in CI High — in place
Cross-compilation Multiple OS/arch targets ubuntu, macos, windows High — in place
Compatibility / semver tests Public API stable across releases Not automated Medium — as API stabilizes
Serialization round-trip Persist and restore cache state Design docs; limited tests Low until serde ships

Security and robustness

Type What it checks CacheKit today Relevance
Panic safety tests Invariants restored after panic Partial in ConcurrentLruCache tests Medium
Boundary tests capacity=0, capacity=1, empty cache Partial in policy_invariants.rs Medium — extend cross-policy
DoS-resistance tests Untrusted keys and hasher choice Documented, not a dedicated suite Medium

Known coverage gaps

Prioritized gaps between current practice and the testing goals in Testing strategy and Policy semantic testing.

1. Semantic oracle depth (highest impact)

  • Bounded policies (ARC, CAR, Clock-PRO, S3-FIFO): InvariantOnly checks do not assert victim correctness. Future work: OracleExpectation::Legal legal-victim sets (static-analysis.md).
  • Mirror policies (Clock, 2Q, SLRU, NRU): oracles mirror implementation; independent reference/ models and reference spec maturity are pending.
  • Random: no PolicyModel or policy_semantics harness (matrix.md).
  • TTL: integration tests exist; Miri smoke and composed-tier spec maturity are incomplete.
  • Path-sensitive traces: documented as future harness work, not implemented.

2. Concurrency

  • Only LRU, FIFO, and S3-FIFO ship Concurrent* wrappers; 15 policies rely on external locking (Concurrency).
  • No tests/*_concurrency.rs integration suite for ConcurrentS3FifoCache (in-module tests exist in src/policy/s3_fifo.rs).
  • No concurrency tests for Clock, ARC, CAR, 2Q, SLRU, MFU, and others.
  • FIFO/LFU/NRU integration concurrency tests use Mutex wrappers, not native Concurrent* APIs.

3. Performance regression breadth

  • O(1) guards cover 5 of ~18 policies.
  • Workload hit-rate and throughput regressions are not gated on PRs (benchmarks run on main only).

4. Fuzz scope

  • All targets hit DS primitives, not full Cache API sequences per policy.
  • Likely missing DS fuzz: expiration_index (TTL path).

5. Formal verification automation

  • TLA+ exists for FIFO and LRU only; TLC is manual, not CI.
  • No trace-export bridge between TLC reachable states and Rust oracle traces (formal/fifo/tlc.md).

6. Cross-cutting integration

  • Weighted eviction: unit tests in store/weight.rs; no integration tests (Weighted eviction).
  • Builder / DynCache: TTL builder path tested; CAR builder gap documented but not covered (Builder and runtime dispatch).
  • Cross-policy invariants: policy_invariants.rs is thin (mostly capacity-0 edge cases).
  • Dual-impl equivalence: only two pairs today (LRU/Fast-LRU, Clock/ClockRing).

7. Process and documentation maturity

  • Several policies have harness tests but operational specs remain stub (mirror, bounded, composed tiers).
  • Testing strategy describes in-module property_tests per module; most policies delegate to policy_semantics instead.
  • Main CI test job runs cargo test --tests --all-features only; lib mod tests outside property_tests are not executed there (partial lib coverage via Miri and the property-tests job).

Recommended additions (priority order)

  1. Legal-victim oracles for bounded policies — upgrade invariant-only tests to semantic checks where victims are not unique.
  2. Independent reference models for mirror policies — cross-model drift guards like exact-tier LRU.
  3. End-to-end policy fuzz targets — full Cache op sequences, complementing DS fuzz.
  4. Expand O(1) regression — FIFO, Fast-LRU, Heap-LFU, MFU, and other hot policies.
  5. tests/*_concurrency.rs for ConcurrentS3FifoCache (beyond in-module tests) and Miri smoke for TTL.
  6. Random policy harness — even a statistical residency/uniformity oracle helps benchmarking baselines.
  7. Optional nightly TLC job — FIFO/LRU formal specs as a non-blocking check.
  8. Loom or TSan on concurrency tests — small-model or sanitizer coverage for Concurrent* wrappers.

When adding a new test type, update this catalog if coverage or CI integration changes materially (including .github/workflows/ci.yml).

Related documentation