# DualCache-FF Specification (v0.3.0)

---

### 1. Core Facade and Global Configuration (`lib.rs`)

```rust
pub struct Config {
    pub capacity: usize,
    pub t1_slots: usize,
    pub t2_slots: usize,
    pub duration: u32,
    pub threads: usize,
    pub poll_us: u64,             // Daemon polling interval (µs)
    pub flush_tick_threshold: u64, // TLS forced flush threshold (ticks)
}

pub trait DaemonSpawner: Send + Sync {
    fn spawn(&self, f: Box<dyn FnOnce() + Send + 'static>);
}

pub trait TlsProvider: Send + Sync {
    fn get_worker_id(&self) -> Option<usize>;
    fn with_hit_buf(&self, f: &mut dyn FnMut(&mut ([usize; 64], usize)));
    fn with_l1_filter(&self, f: &mut dyn FnMut(&mut ([u8; 4096], usize)));
    fn with_last_flush_tick(&self, f: &mut dyn FnMut(&mut u64));
}

pub struct DualCacheFF<K, V, S = RandomState, Tls: TlsProvider = DefaultTls> {
    pub hasher: S,
    pub t1: Arc<T1<K, V>>,
    pub t2: Arc<T2<K, V>>,
    pub cache: Arc<Cache<K, V>>,
    pub cmd_tx: Arc<LossyQueue<Command<K, V>>>, // Custom Wait-Free queue
    pub hit_tx: Arc<LossyQueue<[usize; 64]>>,
    pub epoch: Arc<AtomicU32>,
    pub worker_states: Arc<[WorkerState]>,
    pub miss_buffers: Arc<[WorkerSlot<K, V>]>,
    pub daemon_tick: Arc<AtomicU64>,             // Background counter
    pub tls: Tls, // Zero-cost TLS provider generic parameter
}
```

### 2. Memory Access Path (`storage.rs`, `arena.rs`, `cache_padded.rs`)

**Physical Constraints:**
- **Alignment**: Uses `cache_padded::CachePadded` to prevent False Sharing on `WorkerState`. ARM/Apple Silicon uses 128-byte alignment.
- **Wait-Free Read**: The read path is 100% lock-free, based on `AtomicPtr` and **QSBR (Quiet State Based Reclamation)**.
- **no_std**: The core engine code is fully compatible with `no_std` + `alloc`.

```rust
// ─── Node: Physical Data Node ───
pub struct Node<K, V> {
    pub key: K,
    pub value: V,
    pub expire_at: u32,
    pub g_idx: u32,
}

// ─── LossyQueue: State Turnstile Queue ───
// Status Codes: EMPTY(0) -> WRITING(1) -> READY(2)
pub struct LossyQueue<T> {
    tail: AtomicUsize, // Producer FAA
    head: AtomicUsize, // Consumer
    buffer: Box<[Slot<T>]>,
}
```

### 3. Lifecycle Management (`daemon.rs`)

```rust
pub struct Daemon<K, V, S> {
    pub arena: Arena,
    pub cmd_rx: Arc<LossyQueue<Command<K, V>>>,
    pub hit_rx: Arc<LossyQueue<[usize; 64]>>,
    pub daemon_tick: Arc<AtomicU64>,
    // ...
}
```

---

# Execution Flow

## Physical Constraints and Concurrency Model
*   **Worker (Frontend)**: 100% Wait-Free. Employs `L1_FILTER` for local admission control.
*   **Time-based Flush**: The worker compares its local `LAST_FLUSH_TICK` with the global `daemon_tick`. If the interval exceeds the threshold, it forces a flush of the TLS buffer to resolve visibility delays under low-frequency write scenarios.
*   **Daemon (Background)**: The single writer. Executes maintenance tasks at intervals defined by `poll_us`. In `no_std` mode, this can be driven externally by an RTOS scheduler.

---

## Phase 1: Frontend Read Pipeline (Worker Read Path)
1.  **[QSBR Check-in]**: Marks the `local_epoch` with the current global epoch.
2.  **[Hierarchical Lookup]**: Searches T1 (L1) -> T2 (L2) -> Cache (L3).
3.  **[QSBR Check-out]**: Clears the `local_epoch` marker (resets to 0).
4.  **[Hit Telemetry]**: Buffers the hit index in TLS. Flushes to `hit_tx` when the buffer reaches 64 elements or the flush threshold expires.

---

## Phase 2: Background Maintenance Pipeline (Daemon Maintenance)
1.  **[Hit Resolution]**: Consumes hit indices in batches from `hit_rx`, updates the `Arena` ranks, and populates T1/T2.
2.  **[QSBR Reclamation]**: Checks all registered worker epochs and safely deallocates expired nodes in the `garbage_queue`.
3.  **[Tick Advancement]**: Increments `daemon_tick` to trigger frontend TLS forced flushes.

---

## Phase 3: Background Eviction Pipeline (Daemon Eviction)
1.  **[Averaged Scan]**: Scans the `Arena` using a circular Clock algorithm.
2.  **[Revolution Shield]**: High-frequency items gain rank protection. Nodes with ranks below the global average are evicted into the `garbage_queue`.

---

## Phase 4: Background Insertion Pipeline (Daemon Insertion)
1.  **[Admission Control]**: Checks the `Ghost Set` (Resurrection filter).
2.  **[Lossy Enqueue]**: Pushes insertion requests through the MPSC `LossyQueue`. If `compare_exchange` fails due to queue saturation, the request is immediately dropped to protect frontend latency.

---

## Phase 5: Lifecycle Destruction & CPU Yielding
1. **[Lock-Free Safe Destruction]**: The `Drop` implementation of `DualCacheFF` monitors `Arc` strong counts. When the last controller instance is dropped, it automatically dispatches `Command::Shutdown` to `cmd_tx` to safely terminate the background Daemon's polling loop.
2. **[Zero-Leak Memory Safety]**:
   - The `Drop` implementation of `Cache` iterates through all internal pointers and safely deallocates (`Box::from_raw`) any remaining physical `Node` elements.
   - The `Drop` implementation of `Daemon` safely deallocates all pending `Node` memory held in the `garbage_queue` awaiting QSBR reclamation.
3. **[Progressive CPU Yielding (Spin-then-Yield)]**: In `std` mode, `OneshotAck::wait()` and `LossyQueue::send_blocking()` utilize progressive spinning. The first 100 iterations use `core::hint::spin_loop()`, after which they transition to yielding via `std::thread::yield_now()` to prevent high CPU utilization (busy waiting) under extreme contention. In `no_std` mode, they maintain pure wait-free spin behavior.

---

## Phase 6: Concurrency Safety, Loom Checking & Timeout Watchdogs

1. **[Loom Coroutine Stack Overflow Prevention]**:
   - In `loom` model checking, the constrained virtual coroutine stack (2 KB - 4 KB) is highly susceptible to stack overflows when copying large structures like `BatchBuf` (`[MaybeUninit; 32]`, ~768+ bytes) in `new_headless`.
   - The framework has been updated under the `loom` feature flag to heap-allocate `BatchBuf` inside `WorkerSlot` via `UnsafeCell<Box<BatchBuf<K, V>>>`. By accessing the buffer via `**ptr` under Loom, the hot read path's API remains perfectly compatible while completely resolving virtual stack overflows.
2. **[Active Timeout Watchdogs]**:
   - **Integration Tests**: All 6 integration test suites (`concurrent`, `pressure`, `robust`, `stability`, `test_hash`, `unsafe_spec`) are wrapped in a custom watchdog executor (`run_with_timeout`) with limits ranging from 5 to 30 seconds. Exceeding these limits triggers an immediate panic to prevent indefinite hangs in case of deadlocks or livelocks.
   - **Benchmarks**: All 5 benchmark suites (`capex`, `latency`, `memory`, `throughput`, `rw_ratio`) spawn a background asynchronous watchdog (`start_timeout_watchdog`) upon startup (120s limit for `rw_ratio`, 60s for others). If a benchmark hangs, the watchdog terminates the process via `std::process::exit(101)` to prevent zombie processes.

---

## Phase 7: Dynamic Thread ID Recycling, Cold Start & Hit Rate Restoration

1. **[Dynamic Thread ID Recycling]**:
   - **Context**: Previously, thread-local `WORKER_ID` allocations relied on a simple monotonic atomic increment (`fetch_add(1)`). In test and benchmark runs where threads are repeatedly spawned and destroyed, IDs exceeded `config.threads`, causing those threads to degrade to "overflow threads" that bypass L1 admission control and hit rate tracking.
   - **Optimization**: We introduced a global `IdAllocator` and a thread-local `ThreadIdGuard` implementing `Drop`. When a worker thread terminates, its ID is automatically pushed back to a global thread-safe `free_list` for reuse. This keeps active concurrent IDs strictly bounded by the physical concurrent thread peak, eliminating overflow degradation.
2. **[Cold Start & Update Lookup Bypass]**:
   - Under heavy write ratios, the L1 probation filter (designed to drop one-hit wonders) would incorrectly drop high-frequency update elements before they reached the Daemon, hurting hit rates.
   - We introduced a global `is_cold_start` flag. When the cache is in a cold-start phase, or if the key already exists in `t1`, `t2`, or `cache` (L3), the frontend `insert` bypasses the L1 filter entirely, permitting direct insertion/updates. This restored hit rates to their peak of **84.5% - 84.7%** under all workloads (Zipf and varied read/write ratios).
3. **[Graceful Overflow Safety]**:
   - Lookups and insertions on T1, T2, and Cache are strictly guarded under `if id_opt.is_some() { ... }`.
   - If an unexpected thread burst exceeds the registered `config.threads` capacity, the thread gracefully degrades to a safe cache miss with lossy background updates, fully preserving memory safety and eliminating Use-After-Free (UAF) risks.

---

## Phase 8: Static and Stub Cache Interfaces (v0.2.3)

To fully support resource-constrained IoT/bare-metal environments (e.g., ESP32-C6, TinyNode) where dynamic memory allocator (`alloc`) is disabled or highly discouraged due to fragmentation or OOM risks, two additional interfaces are introduced in `v0.2.3` under the `static_cache` module:

### 1. Zero-Overhead Compile-Time Stub (`DualCacheStub<K, V>`)
- **Aesthetic / Intent**: Complete physical compile-time erasure. All API methods (`new`, `new_headless`, `get`, `insert`, `remove`, `clear`, `sync`) are annotated with `#[inline(always)]` and evaluate to direct no-ops.
- **Physical Footprint**: 0 bytes RAM, 0 CPU cycles in release mode. Useful to compile-out caching mechanisms cleanly when building for target nodes with extreme memory constraints.

### 2. Zero-Allocation Static Cache (`StaticDualCache<K, V, const N: usize, S = RandomState>`)
- **Aesthetic / Intent**: 100% `alloc`-free active caching with direct-mapped layout.
- **Concurrency Guarantee**: Thread safety is achieved at the slot level. Each of the `N` cache slots (`CacheSlot<K, V>`) possesses its own atomic spinlock (`AtomicBool`) guarding an `UnsafeCell<Option<(K, V)>>`.
- **Memory Overhead**: Statically allocated in memory (typically in BSS or data segments when declared in global `static`), eliminating dynamic fragmentation risks entirely.
- **API Parity**: Matches the frontend pipeline of `DualCacheFF` (`get`, `insert`, `remove`, `clear`, `sync`, and `new_headless` returning `(Self, ())`).

---

## Phase 9: Unsafe Encapsulation and Pure Portability (v0.2.4)

### 1. 100% Safe Hot-Path Abstractions
- **Architectural Shift**: In v0.2.4, the hot-path logic inside `cache.rs` and `daemon.rs` has been thoroughly cleansed of all `unsafe` blocks. Pointer dereferencing and lock-free slot manipulations have been confined behind zero-cost strict safe wrappers (e.g., `get_mut_safe` in `WorkerSlot` and `get_node` in `Cache`).
- **Defensive Radius**: This strictly limits memory safety blast radius to `unsafe_core.rs` and `arena.rs`, drastically improving auditability.
- **Strict Configuration Guard**: Initialization cold paths (e.g., `Config::new_expert`) no longer use `unsafe` to bypass parameter boundaries. Instead, strict `assert!` mechanisms apply compile-time eliminated boundary validation (BCE).

### 2. Embedded & RTOS `AtomicU32` Fallbacks
- **Architecture Validation**: Many resource-constrained processors (e.g., specific RISC-V or older ARM cores) natively lack 64-bit hardware atomic instructions. 
- **Type Aliasing**: Introduced conditional target feature compilation inside `sync.rs` (`target_has_atomic = "64"`). `AtomicIndex` and `AtomicTick` are now dynamically bound to `AtomicU64` or `AtomicU32` at compile time, retaining wait-free operations on smaller target constraints while adjusting bit masks for tags automatically.

