Skip to main content

rf_cache/
mem.rs

1//! The in-memory half of the scan cache: a byte-weighted LRU with a TTL.
2//!
3//! MCP-05/ROB-07. The MCP server's memory cache was
4//! `Mutex<HashMap<String, Arc<CachedScan>>>` with exactly two operations,
5//! `get` and `put`. No capacity, no eviction, no TTL. Measured on the live
6//! server: twelve depth-varying scans of one 900 KB binary walked RSS from
7//! 5 MB to 84 MB *monotonically* while every request carried
8//! `max_results: 1` — which is the point, because the *response* cap bounds
9//! what is sent, never what is retained. One depth-40 scan pinned 2.57 GB
10//! for the life of the process.
11//!
12//! Three properties make this a bound rather than a hint:
13//!
14//!   * **Weighted by bytes, not entries.** A cap of "1000 entries" means
15//!     nothing when one entry is 2.57 GB. The weight is
16//!     [`CachedScan::heap_bytes`], the retained size of the record, and
17//!     eviction runs until the total is under budget.
18//!   * **Evicted on insert, not on a timer.** There is no background task
19//!     to fail to start; the budget is restored by the operation that
20//!     breached it.
21//!   * **An entry larger than the whole budget is never stored.** Storing
22//!     it would evict everything else and still be over, so it is counted
23//!     (`too_large`) and dropped.
24//!
25//! Recency is a monotonic sequence number in a `BTreeMap`, so the least
26//! recently used entry is the first key in O(log n) and no intrusive
27//! linked list (and no `unsafe`) is needed.
28
29use std::collections::{BTreeMap, HashMap};
30use std::sync::{Arc, Mutex, MutexGuard, PoisonError};
31use std::time::{Duration, SystemTime, UNIX_EPOCH};
32
33use crate::record::CachedScan;
34
35/// Default `--cache-mem-mb`, in bytes (512 MiB).
36pub const DEFAULT_MEM_MAX_BYTES: u64 = 512 * 1024 * 1024;
37/// Default `--cache-ttl-secs` (24 h).
38pub const DEFAULT_MEM_TTL: Duration = Duration::from_secs(86_400);
39
40/// Budget for [`MemCache`].
41#[derive(Debug, Clone, Copy, PartialEq, Eq)]
42pub struct MemLimits {
43    /// Total retained bytes across all entries.
44    pub max_bytes: u64,
45    /// An entry older than this is a miss and is dropped on sight.
46    pub ttl: Duration,
47}
48
49impl Default for MemLimits {
50    fn default() -> Self {
51        MemLimits {
52            max_bytes: DEFAULT_MEM_MAX_BYTES,
53            ttl: DEFAULT_MEM_TTL,
54        }
55    }
56}
57
58/// Counters for `get_server_stats` (MCP-09).
59#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
60pub struct MemStats {
61    /// Lookups served from the cache.
62    pub hits: u64,
63    /// Lookups that found nothing.
64    pub misses: u64,
65    /// Entries dropped because they were older than the TTL.
66    pub expired: u64,
67    /// Entries added.
68    pub inserted: u64,
69    /// Entries dropped to stay under `max_bytes`.
70    pub evicted: u64,
71    /// Bytes reclaimed by those evictions.
72    pub evicted_bytes: u64,
73    /// Entries never stored because one of them exceeds the whole budget.
74    pub too_large: u64,
75    /// Live values, filled in by [`MemCache::stats`].
76    pub entries: u64,
77    /// Live retained bytes, filled in by [`MemCache::stats`].
78    pub bytes: u64,
79}
80
81#[derive(Debug)]
82struct Entry {
83    scan: Arc<CachedScan>,
84    bytes: u64,
85    created_unix: u64,
86    /// Recency key into [`Inner::order`].
87    seq: u64,
88}
89
90#[derive(Debug, Default)]
91struct Inner {
92    map: HashMap<String, Entry>,
93    /// `seq -> key`, ascending: the first entry is the least recently used.
94    order: BTreeMap<u64, String>,
95    next_seq: u64,
96    bytes: u64,
97    stats: MemStats,
98}
99
100/// Byte-weighted, TTL'd LRU over [`CachedScan`] values.
101///
102/// Shared by the MCP server and the CLI so the bound is written once —
103/// the duplication of this cache is what MCP-05 and CLI-08 have in common.
104#[derive(Debug)]
105pub struct MemCache {
106    limits: MemLimits,
107    inner: Mutex<Inner>,
108}
109
110impl Default for MemCache {
111    fn default() -> Self {
112        MemCache::new(MemLimits::default())
113    }
114}
115
116/// Seconds since the epoch, saturating rather than panicking on a clock
117/// that predates it.
118#[must_use]
119pub fn now_unix() -> u64 {
120    SystemTime::now()
121        .duration_since(UNIX_EPOCH)
122        .map(|d| d.as_secs())
123        .unwrap_or(0)
124}
125
126impl MemCache {
127    /// An empty cache bounded by `limits`.
128    #[must_use]
129    pub fn new(limits: MemLimits) -> Self {
130        MemCache {
131            limits,
132            inner: Mutex::new(Inner::default()),
133        }
134    }
135
136    /// The budget this cache was built with.
137    #[must_use]
138    pub fn limits(&self) -> MemLimits {
139        self.limits
140    }
141
142    /// A panic anywhere else must not disable the cache for the rest of the
143    /// session: every operation below is a single consistent update, so
144    /// recovering a poisoned guard cannot expose a half-applied insert.
145    fn inner(&self) -> MutexGuard<'_, Inner> {
146        self.inner.lock().unwrap_or_else(PoisonError::into_inner)
147    }
148
149    /// Look up `key`, refreshing its recency. An entry older than the TTL
150    /// is removed and reported as a miss.
151    pub fn get(&self, key: &str) -> Option<Arc<CachedScan>> {
152        let now = now_unix();
153        let ttl = self.limits.ttl.as_secs();
154        let mut g = self.inner();
155        let found = g.map.get(key).map(|e| {
156            (
157                e.seq,
158                e.scan.clone(),
159                now.saturating_sub(e.created_unix) > ttl,
160            )
161        });
162        match found {
163            None => {
164                g.stats.misses += 1;
165                None
166            }
167            Some((_, _, true)) => {
168                g.remove(key);
169                g.stats.expired += 1;
170                g.stats.misses += 1;
171                None
172            }
173            Some((seq, scan, false)) => {
174                let next = g.bump();
175                g.order.remove(&seq);
176                g.order.insert(next, key.to_string());
177                if let Some(e) = g.map.get_mut(key) {
178                    e.seq = next;
179                }
180                g.stats.hits += 1;
181                Some(scan)
182            }
183        }
184    }
185
186    /// Insert (or replace) `key`, then evict least-recently-used entries
187    /// until the total is within budget.
188    ///
189    /// Returns the stored value so the caller can use it whether or not it
190    /// was retained: an entry bigger than the whole budget is *served* but
191    /// not *kept*.
192    pub fn put(&self, key: &str, scan: CachedScan) -> Arc<CachedScan> {
193        self.put_arc(key, Arc::new(scan))
194    }
195
196    /// [`MemCache::put`] for a value the caller already shares.
197    pub fn put_arc(&self, key: &str, scan: Arc<CachedScan>) -> Arc<CachedScan> {
198        let cost = scan.heap_bytes() as u64;
199        let mut g = self.inner();
200        g.remove(key);
201        if cost > self.limits.max_bytes {
202            // Keeping it would evict every other entry and still breach the
203            // budget. Serve it; do not retain it.
204            g.stats.too_large += 1;
205            return scan;
206        }
207        let seq = g.bump();
208        g.order.insert(seq, key.to_string());
209        g.bytes += cost;
210        g.map.insert(
211            key.to_string(),
212            Entry {
213                scan: scan.clone(),
214                bytes: cost,
215                created_unix: now_unix(),
216                seq,
217            },
218        );
219        g.stats.inserted += 1;
220        while g.bytes > self.limits.max_bytes {
221            let Some(victim) = g.order.values().next().cloned() else {
222                break;
223            };
224            let freed = g.remove(&victim);
225            if freed == 0 {
226                break;
227            }
228            g.stats.evicted += 1;
229            g.stats.evicted_bytes += freed;
230        }
231        scan
232    }
233
234    /// Drop every entry older than the TTL. `get` does this lazily; this is
235    /// for a caller that wants the bytes back without a lookup.
236    pub fn sweep_expired(&self) -> u64 {
237        let now = now_unix();
238        let ttl = self.limits.ttl.as_secs();
239        let mut g = self.inner();
240        let stale: Vec<String> = g
241            .map
242            .iter()
243            .filter(|(_, e)| now.saturating_sub(e.created_unix) > ttl)
244            .map(|(k, _)| k.clone())
245            .collect();
246        let mut n = 0;
247        for k in stale {
248            if g.remove(&k) > 0 {
249                g.stats.expired += 1;
250                n += 1;
251            }
252        }
253        n
254    }
255
256    /// Counters plus the live `entries`/`bytes`.
257    #[must_use]
258    pub fn stats(&self) -> MemStats {
259        let g = self.inner();
260        MemStats {
261            entries: g.map.len() as u64,
262            bytes: g.bytes,
263            ..g.stats
264        }
265    }
266
267    /// Retained bytes right now.
268    #[must_use]
269    pub fn bytes(&self) -> u64 {
270        self.inner().bytes
271    }
272
273    /// Entries retained right now.
274    #[must_use]
275    pub fn len(&self) -> usize {
276        self.inner().map.len()
277    }
278
279    /// True when the cache holds nothing.
280    #[must_use]
281    pub fn is_empty(&self) -> bool {
282        self.len() == 0
283    }
284
285    /// Drop every entry.
286    pub fn clear(&self) {
287        let mut g = self.inner();
288        g.map.clear();
289        g.order.clear();
290        g.bytes = 0;
291    }
292}
293
294impl Inner {
295    fn bump(&mut self) -> u64 {
296        self.next_seq += 1;
297        self.next_seq
298    }
299
300    /// Remove `key`, returning the bytes it was costing (0 if absent).
301    fn remove(&mut self, key: &str) -> u64 {
302        match self.map.remove(key) {
303            None => 0,
304            Some(e) => {
305                self.order.remove(&e.seq);
306                self.bytes = self.bytes.saturating_sub(e.bytes);
307                e.bytes
308            }
309        }
310    }
311}
312
313#[cfg(test)]
314mod tests {
315    use super::*;
316    use crate::record::CachedGadget;
317
318    /// A scan whose retained size grows linearly in `n`.
319    fn scan_of(n: usize) -> CachedScan {
320        CachedScan {
321            gadgets: (0..n)
322                .map(|i| CachedGadget {
323                    vaddr: format!("0x{i:08x}"),
324                    bytes: "5fc3".to_string(),
325                    text: "pop rdi ; ret".to_string(),
326                    ..CachedGadget::default()
327                })
328                .collect(),
329            ..CachedScan::default()
330        }
331    }
332
333    #[test]
334    fn heap_bytes_grows_with_the_gadget_count() {
335        let fixed = crate::SCAN_OVERHEAD_BYTES;
336        let one = scan_of(1).heap_bytes() - fixed;
337        // Strictly linear in the gadget count, which is the axis MCP-05's
338        // 2.57 GB grew along.
339        assert_eq!(scan_of(1000).heap_bytes() - fixed, 1000 * one);
340        assert_eq!(scan_of(0).heap_bytes(), fixed);
341        // Every gadget costs at least the fixed per-record overhead, so a
342        // million tiny gadgets cannot look free.
343        assert!(one >= crate::GADGET_OVERHEAD_BYTES, "{one}");
344    }
345
346    /// MCP-05: the sequence that walked 5 MB -> 84 MB monotonically now
347    /// stops at the budget.
348    #[test]
349    fn insert_evicts_until_under_budget() {
350        let one = scan_of(200).heap_bytes() as u64;
351        let cache = MemCache::new(MemLimits {
352            max_bytes: one * 3,
353            ttl: DEFAULT_MEM_TTL,
354        });
355        for i in 0..40 {
356            cache.put(&format!("k{i}"), scan_of(200));
357            assert!(
358                cache.bytes() <= one * 3,
359                "over budget at {i}: {} > {}",
360                cache.bytes(),
361                one * 3
362            );
363        }
364        assert_eq!(cache.len(), 3);
365        let s = cache.stats();
366        assert_eq!(s.inserted, 40);
367        assert_eq!(s.evicted, 37);
368        assert!(s.evicted_bytes >= 37 * one);
369        // ...and it is the LEAST RECENTLY USED that went.
370        assert!(cache.get("k39").is_some());
371        assert!(cache.get("k0").is_none());
372    }
373
374    #[test]
375    fn a_hit_refreshes_recency() {
376        let one = scan_of(50).heap_bytes() as u64;
377        let cache = MemCache::new(MemLimits {
378            max_bytes: one * 2,
379            ttl: DEFAULT_MEM_TTL,
380        });
381        cache.put("a", scan_of(50));
382        cache.put("b", scan_of(50));
383        // Touch `a`, so `b` becomes the eviction victim.
384        assert!(cache.get("a").is_some());
385        cache.put("c", scan_of(50));
386        assert!(cache.get("a").is_some(), "a was refreshed");
387        assert!(cache.get("b").is_none(), "b was the LRU");
388        assert!(cache.get("c").is_some());
389    }
390
391    /// ROB-07: one depth-40 scan pinned 2.57 GB. An entry that cannot fit
392    /// the budget is served and dropped, never retained.
393    #[test]
394    fn an_oversized_entry_is_served_but_never_retained() {
395        let cache = MemCache::new(MemLimits {
396            max_bytes: 1024,
397            ttl: DEFAULT_MEM_TTL,
398        });
399        let out = cache.put("huge", scan_of(1000));
400        assert_eq!(out.gadgets.len(), 1000, "still usable by this caller");
401        assert_eq!(cache.len(), 0);
402        assert_eq!(cache.bytes(), 0);
403        assert_eq!(cache.stats().too_large, 1);
404        assert!(cache.get("huge").is_none());
405    }
406
407    #[test]
408    fn an_expired_entry_is_a_miss_and_its_bytes_come_back() {
409        let cache = MemCache::new(MemLimits {
410            max_bytes: 1 << 30,
411            ttl: Duration::from_secs(60),
412        });
413        cache.put("k", scan_of(20));
414        assert!(cache.bytes() > 0);
415        // Backdate the entry past the TTL.
416        {
417            let mut g = cache.inner();
418            if let Some(e) = g.map.get_mut("k") {
419                e.created_unix = now_unix().saturating_sub(3600);
420            }
421        }
422        assert!(cache.get("k").is_none());
423        assert_eq!(cache.bytes(), 0);
424        assert_eq!(cache.len(), 0);
425        let s = cache.stats();
426        assert_eq!(s.expired, 1);
427        assert_eq!(s.misses, 1);
428    }
429
430    #[test]
431    fn replacing_a_key_does_not_double_count_its_bytes() {
432        let cache = MemCache::new(MemLimits::default());
433        cache.put("k", scan_of(100));
434        let first = cache.bytes();
435        cache.put("k", scan_of(100));
436        assert_eq!(cache.bytes(), first);
437        assert_eq!(cache.len(), 1);
438    }
439
440    #[test]
441    fn sweep_expired_reclaims_without_a_lookup() {
442        let cache = MemCache::new(MemLimits {
443            max_bytes: 1 << 30,
444            ttl: Duration::from_secs(60),
445        });
446        for i in 0..5 {
447            cache.put(&format!("k{i}"), scan_of(10));
448        }
449        {
450            let mut g = cache.inner();
451            for e in g.map.values_mut() {
452                e.created_unix = now_unix().saturating_sub(3600);
453            }
454        }
455        assert_eq!(cache.sweep_expired(), 5);
456        assert_eq!(cache.bytes(), 0);
457        assert!(cache.is_empty());
458    }
459
460    #[test]
461    fn stats_report_live_entries_and_bytes() {
462        let cache = MemCache::new(MemLimits::default());
463        assert_eq!(cache.stats(), MemStats::default());
464        cache.put("a", scan_of(3));
465        let s = cache.stats();
466        assert_eq!(s.entries, 1);
467        assert_eq!(s.bytes, cache.bytes());
468        assert_eq!(s.inserted, 1);
469        assert!(cache.get("a").is_some());
470        assert_eq!(cache.stats().hits, 1);
471        assert!(cache.get("nope").is_none());
472        assert_eq!(cache.stats().misses, 1);
473    }
474}