1use std::collections::{BTreeMap, HashMap};
30use std::sync::{Arc, Mutex, MutexGuard, PoisonError};
31use std::time::{Duration, SystemTime, UNIX_EPOCH};
32
33use crate::record::CachedScan;
34
35pub const DEFAULT_MEM_MAX_BYTES: u64 = 512 * 1024 * 1024;
37pub const DEFAULT_MEM_TTL: Duration = Duration::from_secs(86_400);
39
40#[derive(Debug, Clone, Copy, PartialEq, Eq)]
42pub struct MemLimits {
43 pub max_bytes: u64,
45 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#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
60pub struct MemStats {
61 pub hits: u64,
63 pub misses: u64,
65 pub expired: u64,
67 pub inserted: u64,
69 pub evicted: u64,
71 pub evicted_bytes: u64,
73 pub too_large: u64,
75 pub entries: u64,
77 pub bytes: u64,
79}
80
81#[derive(Debug)]
82struct Entry {
83 scan: Arc<CachedScan>,
84 bytes: u64,
85 created_unix: u64,
86 seq: u64,
88}
89
90#[derive(Debug, Default)]
91struct Inner {
92 map: HashMap<String, Entry>,
93 order: BTreeMap<u64, String>,
95 next_seq: u64,
96 bytes: u64,
97 stats: MemStats,
98}
99
100#[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#[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 #[must_use]
129 pub fn new(limits: MemLimits) -> Self {
130 MemCache {
131 limits,
132 inner: Mutex::new(Inner::default()),
133 }
134 }
135
136 #[must_use]
138 pub fn limits(&self) -> MemLimits {
139 self.limits
140 }
141
142 fn inner(&self) -> MutexGuard<'_, Inner> {
146 self.inner.lock().unwrap_or_else(PoisonError::into_inner)
147 }
148
149 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 pub fn put(&self, key: &str, scan: CachedScan) -> Arc<CachedScan> {
193 self.put_arc(key, Arc::new(scan))
194 }
195
196 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 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 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 #[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 #[must_use]
269 pub fn bytes(&self) -> u64 {
270 self.inner().bytes
271 }
272
273 #[must_use]
275 pub fn len(&self) -> usize {
276 self.inner().map.len()
277 }
278
279 #[must_use]
281 pub fn is_empty(&self) -> bool {
282 self.len() == 0
283 }
284
285 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 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 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 assert_eq!(scan_of(1000).heap_bytes() - fixed, 1000 * one);
340 assert_eq!(scan_of(0).heap_bytes(), fixed);
341 assert!(one >= crate::GADGET_OVERHEAD_BYTES, "{one}");
344 }
345
346 #[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 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 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 #[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 {
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}