Skip to main content

nitr_std/
cache.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2// This file is part of Nitr.
3// See https://nitrweb.com/ for more information
4// Copyright (C) 2024-present Jose Quintana <joseluisq.net>
5
6//! `nitr.cache`: a bounded, Rust-owned cache shared by every pooled state.
7//!
8//! This is deliberately *not* a hole in the isolation model. Values are
9//! serialized on the way in and rebuilt on the way out, so no Lua value,
10//! function, or userdata ever crosses between states, and one state can
11//! never reach another's heap through it. Rust owns the memory and the
12//! bound, so the cache cannot grow without limit. It is shared **data**,
13//! not shared **state** — the same relationship Lua already has with
14//! SQLite.
15//!
16//! Two properties applications must know, because building on the opposite
17//! assumption fails quietly:
18//!
19//! - It lives in the process. A restart empties it, and two Nitr processes
20//!   behind a load balancer have two independent caches. Do not put
21//!   sessions, locks, or counters that must be exact in here.
22//! - It survives a reload. A cache that empties every time the handler
23//!   script changes is a cache that never warms, which is worse than not
24//!   having one in development.
25
26use std::collections::{BTreeMap, HashMap};
27use std::sync::atomic::{AtomicU64, Ordering};
28use std::sync::{Arc, Mutex};
29use std::time::{Duration, Instant};
30
31use mlua::{ExternalResult as _, Lua, LuaSerdeExt as _, Table, UserData, UserDataMethods, Value};
32
33/// Limits and defaults for the shared cache.
34#[derive(Debug, Clone)]
35pub struct CacheOptions {
36    /// Maximum live entries before the least recently used is evicted.
37    pub max_entries: usize,
38    /// Maximum total size of stored values, in bytes.
39    pub max_bytes: u64,
40    /// Seconds an entry lives when `set` does not say; `0` means no expiry.
41    pub default_ttl: u64,
42}
43
44impl Default for CacheOptions {
45    fn default() -> Self {
46        Self {
47            max_entries: 10_000,
48            max_bytes: 32 * 1024 * 1024,
49            default_ttl: 300,
50        }
51    }
52}
53
54struct Entry {
55    /// The value as JSON bytes: plain data, never a Lua handle.
56    value: Vec<u8>,
57    /// `None` for an entry that never expires.
58    expires_at: Option<Instant>,
59    /// Monotonic tick of the last read or write, for LRU eviction.
60    touched: u64,
61    /// Tick of the write that created the entry: the tiebreaker that
62    /// keeps two entries expiring at the same instant apart in the
63    /// expiry index.
64    inserted: u64,
65}
66
67/// Longest key accepted, so a request-derived key cannot dominate an
68/// entry's cost.
69const MAX_KEY_BYTES: usize = 1024;
70
71/// The longest TTL honored, in seconds (~10 years): anything past it is
72/// indistinguishable from "never expires" and is clamped rather than let
73/// near `Instant`'s arithmetic limit.
74const MAX_TTL_SECS: u64 = 10 * 365 * 24 * 60 * 60;
75
76impl Entry {
77    /// What one entry costs against the byte bound: key and value both.
78    fn cost(key: &str, value: &[u8]) -> u64 {
79        (key.len() + value.len()) as u64
80    }
81}
82
83impl Entry {
84    fn is_live(&self, now: Instant) -> bool {
85        self.expires_at.is_none_or(|at| at > now)
86    }
87}
88
89/// The storage behind the lock.
90///
91/// Two ordered indexes ride beside the map so that eviction is a lookup,
92/// not a scan: every `set` used to `retain` over the whole map to drop
93/// expired entries and then scan it again per victim, all under the lock
94/// every state shares — O(n) per write at 10 000 entries. Now a write
95/// costs a few `BTreeMap` operations and a victim is the first key of an
96/// index. Keys are shared (`Arc<str>`) between the map and the indexes.
97#[derive(Default)]
98struct Inner {
99    entries: HashMap<Arc<str>, Entry>,
100    /// Least recently used first; `touched` ticks are unique, so this is
101    /// a total order over the live entries.
102    lru: BTreeMap<u64, Arc<str>>,
103    /// Soonest expiry first, over the entries that have a TTL.
104    expiry: BTreeMap<(Instant, u64), Arc<str>>,
105    bytes: u64,
106    hits: u64,
107    misses: u64,
108    evictions: u64,
109}
110
111impl Inner {
112    /// Removes an entry from the map and both indexes, debiting its cost.
113    fn remove(&mut self, key: &str) -> Option<Entry> {
114        let (key, entry) = self.entries.remove_entry(key)?;
115        self.lru.remove(&entry.touched);
116        if let Some(at) = entry.expires_at {
117            self.expiry.remove(&(at, entry.inserted));
118        }
119        // Saturating (here and at every debit): if the hand-kept counter
120        // ever drifts, a wrap near `u64::MAX` would make eviction expel
121        // everything forever; flooring at zero merely over-admits until
122        // entries cycle out.
123        self.bytes = self.bytes.saturating_sub(Entry::cost(&key, &entry.value));
124        Some(entry)
125    }
126}
127
128/// The shared cache. Cloning shares the same storage; the server builds one
129/// and hands it to every state.
130#[derive(Clone)]
131pub struct Cache {
132    inner: Arc<Mutex<Inner>>,
133    opts: Arc<CacheOptions>,
134    /// Supplies the LRU ordering. A counter rather than a timestamp: it is
135    /// cheaper and cannot go backwards when the wall clock does.
136    clock: Arc<AtomicU64>,
137}
138
139impl std::fmt::Debug for Cache {
140    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
141        f.debug_struct("Cache")
142            .field("max_entries", &self.opts.max_entries)
143            .field("max_bytes", &self.opts.max_bytes)
144            .finish_non_exhaustive()
145    }
146}
147
148impl Cache {
149    /// Creates an empty cache bounded by the given limits.
150    pub fn new(opts: CacheOptions) -> Self {
151        Self {
152            inner: Arc::new(Mutex::new(Inner::default())),
153            opts: Arc::new(opts),
154            clock: Arc::new(AtomicU64::new(0)),
155        }
156    }
157
158    /// Drops every entry (the counters stay). `nitr test` calls it
159    /// between test files, so no file sees what the previous one cached.
160    ///
161    /// # Errors
162    ///
163    /// Only when a panic poisoned the lock.
164    pub fn clear(&self) -> mlua::Result<()> {
165        let mut inner = self.lock()?;
166        inner.entries.clear();
167        inner.lru.clear();
168        inner.expiry.clear();
169        inner.bytes = 0;
170        Ok(())
171    }
172
173    fn lock(&self) -> mlua::Result<std::sync::MutexGuard<'_, Inner>> {
174        self.inner
175            .lock()
176            .map_err(|_| mlua::Error::RuntimeError("the cache lock is poisoned".into()))
177    }
178
179    fn tick(&self) -> u64 {
180        self.clock.fetch_add(1, Ordering::Relaxed)
181    }
182
183    fn get_raw(&self, key: &str) -> mlua::Result<Option<Vec<u8>>> {
184        // Expiry reads the standard library's clock, so a test can age an
185        // entry with `nitr.test.clock.advance` instead of sleeping.
186        let now = crate::clock::now_instant();
187        let touched = self.tick();
188        let mut inner = self.lock()?;
189        let inner = &mut *inner;
190
191        match inner.entries.get_mut(key) {
192            Some(entry) if entry.is_live(now) => {
193                // Re-ranked in the LRU index under its new tick.
194                let previous = std::mem::replace(&mut entry.touched, touched);
195                let value = entry.value.clone();
196                if let Some(shared) = inner.lru.remove(&previous) {
197                    inner.lru.insert(touched, shared);
198                }
199                inner.hits += 1;
200                Ok(Some(value))
201            }
202            // An expired entry is dropped on the way past rather than left
203            // to be evicted later: it is dead weight against both bounds.
204            Some(_) => {
205                inner.remove(key);
206                inner.misses += 1;
207                Ok(None)
208            }
209            None => {
210                inner.misses += 1;
211                Ok(None)
212            }
213        }
214    }
215
216    fn set_raw(&self, key: String, value: Vec<u8>, ttl: Option<u64>) -> mlua::Result<()> {
217        if key.len() > MAX_KEY_BYTES {
218            return Err(mlua::Error::RuntimeError(format!(
219                "cache key is {} bytes; keys are bounded to {MAX_KEY_BYTES} (hash a long \
220                 key first)",
221                key.len()
222            )));
223        }
224        // The key is part of what the entry costs: a script keying on a
225        // request-derived string would otherwise fill memory with keys
226        // the byte bound never saw.
227        let size = Entry::cost(&key, &value);
228        if size > self.opts.max_bytes {
229            return Err(mlua::Error::RuntimeError(format!(
230                "cache value for `{key}` is {size} bytes, larger than the whole \
231                 {} byte cache",
232                self.opts.max_bytes
233            )));
234        }
235        let ttl = ttl.unwrap_or(self.opts.default_ttl);
236        // `Instant + Duration` panics on overflow; a `ttl` a script computed
237        // from request data must not be able to reach that. Anything past
238        // the clamp is "effectively forever" and behaves like it.
239        let expires_at = (ttl > 0)
240            .then(|| {
241                crate::clock::now_instant().checked_add(Duration::from_secs(ttl.min(MAX_TTL_SECS)))
242            })
243            .flatten();
244        let touched = self.tick();
245        let mut inner = self.lock()?;
246        let inner = &mut *inner;
247
248        inner.remove(&key);
249        let key: Arc<str> = key.into();
250        inner.bytes += size;
251        inner.lru.insert(touched, key.clone());
252        if let Some(at) = expires_at {
253            inner.expiry.insert((at, touched), key.clone());
254        }
255        inner.entries.insert(
256            key,
257            Entry {
258                value,
259                expires_at,
260                touched,
261                inserted: touched,
262            },
263        );
264        self.evict(inner);
265        Ok(())
266    }
267
268    /// Brings the cache back inside both bounds, dropping expired entries
269    /// first (soonest expired first) and then the least recently used.
270    ///
271    /// Only runs while a bound is exceeded: an expired entry that still
272    /// fits is reaped when it is next read, or when room is needed, rather
273    /// than by a sweep on every write. Dropping expired entries does not
274    /// count as an eviction — they were dead already.
275    fn evict(&self, inner: &mut Inner) {
276        let now = crate::clock::now_instant();
277        while inner.entries.len() > self.opts.max_entries || inner.bytes > self.opts.max_bytes {
278            let expired = inner
279                .expiry
280                .first_key_value()
281                .filter(|((at, _), _)| *at <= now)
282                .map(|(_, key)| key.clone());
283            match expired {
284                Some(key) => {
285                    inner.remove(&key);
286                }
287                None => {
288                    let Some(victim) = inner.lru.first_key_value().map(|(_, key)| key.clone())
289                    else {
290                        break;
291                    };
292                    inner.remove(&victim);
293                    inner.evictions += 1;
294                }
295            }
296        }
297    }
298}
299
300impl UserData for Cache {
301    fn add_methods<M: UserDataMethods<Self>>(methods: &mut M) {
302        // cache:get(key) -> value | nil
303        methods.add_method("get", |lua, cache, key: String| {
304            match cache.get_raw(&key)? {
305                Some(bytes) => {
306                    let json: serde_json::Value = serde_json::from_slice(&bytes).into_lua_err()?;
307                    lua.to_value(&json)
308                }
309                None => Ok(Value::Nil),
310            }
311        });
312
313        // cache:set(key, value, opts?) — opts is { ttl = seconds }.
314        // The value is serialized here, which is what keeps states isolated
315        // and is also why a function or userdata cannot be cached. Setting
316        // nil removes the key: a stored `null` would read back as a truthy
317        // light userdata, not as the nil that was set.
318        methods.add_method(
319            "set",
320            |_, cache, (key, value, opts): (String, Value, Option<Table>)| {
321                if value.is_nil() || value.is_null() {
322                    cache.lock()?.remove(&key);
323                    return Ok(());
324                }
325                let ttl = match &opts {
326                    Some(opts) => opts.get::<Option<u64>>("ttl")?,
327                    None => None,
328                };
329                let bytes = crate::bounded::to_json_vec(&value).map_err(|err| {
330                    mlua::Error::RuntimeError(format!(
331                        "cache values must be plain data (a table, string, number or \
332                         boolean); `{key}` is not serializable: {err}"
333                    ))
334                })?;
335                cache.set_raw(key, bytes, ttl)?;
336                Ok(())
337            },
338        );
339
340        // cache:delete(key) -> whether it was there
341        methods.add_method("delete", |_, cache, key: String| {
342            let mut inner = cache.lock()?;
343            Ok(inner.remove(&key).is_some())
344        });
345
346        methods.add_method("clear", |_, cache, ()| cache.clear());
347
348        // cache:remember(key, opts?, fn) — get, or compute and store.
349        //
350        // The common shape, worth having as one call: written by hand it is
351        // three lines that are easy to get subtly wrong (caching a nil,
352        // forgetting the TTL).
353        methods.add_async_method(
354            "remember",
355            |lua, cache, (key, arg, f): (String, Value, Option<mlua::Function>)| async move {
356                // remember(key, fn) and remember(key, opts, fn) both work.
357                let (opts, f) = match (arg, f) {
358                    (Value::Function(f), None) => (None, f),
359                    (Value::Table(opts), Some(f)) => (Some(opts), f),
360                    _ => {
361                        return Err(mlua::Error::RuntimeError(
362                            "cache:remember expects (key, fn) or (key, opts, fn)".into(),
363                        ));
364                    }
365                };
366                if let Some(bytes) = cache.get_raw(&key)? {
367                    let json: serde_json::Value = serde_json::from_slice(&bytes).into_lua_err()?;
368                    return lua.to_value(&json);
369                }
370                let ttl = match &opts {
371                    Some(opts) => opts.get::<Option<u64>>("ttl")?,
372                    None => None,
373                };
374                let value: Value = f.call_async(()).await?;
375                // A nil result is not cached: it would be indistinguishable
376                // from a miss on the way out, so every later call would run
377                // the function anyway while occupying an entry.
378                if value.is_nil() {
379                    return Ok(Value::Nil);
380                }
381                let bytes = crate::bounded::to_json_vec(&value).map_err(|err| {
382                    mlua::Error::RuntimeError(format!(
383                        "cache:remember value for `{key}` is not serializable: {err}"
384                    ))
385                })?;
386                cache.set_raw(key, bytes, ttl)?;
387                Ok(value)
388            },
389        );
390
391        // cache:stats() — entries, bytes, hits, misses, evictions.
392        methods.add_method("stats", |lua, cache, ()| {
393            let inner = cache.lock()?;
394            let table = lua.create_table()?;
395            table.set("entries", inner.entries.len())?;
396            table.set("bytes", inner.bytes)?;
397            table.set("hits", inner.hits)?;
398            table.set("misses", inner.misses)?;
399            table.set("evictions", inner.evictions)?;
400            table.set("max_entries", cache.opts.max_entries)?;
401            table.set("max_bytes", cache.opts.max_bytes)?;
402            Ok(table)
403        });
404    }
405}
406
407/// Builds the `nitr.cache` handle for one state over the shared storage.
408pub(crate) fn create_cache(lua: &Lua, cache: Cache) -> mlua::Result<mlua::AnyUserData> {
409    lua.create_userdata(cache)
410}
411
412#[cfg(test)]
413mod tests {
414    use super::*;
415
416    fn cache(opts: CacheOptions) -> Cache {
417        Cache::new(opts)
418    }
419
420    /// A chain of `depth` nested Lua tables (the root included).
421    fn deep_table(lua: &Lua, depth: usize) -> Value {
422        let root = lua.create_table().expect("table");
423        let mut cur = root.clone();
424        for _ in 1..depth {
425            let next = lua.create_table().expect("table");
426            cur.set("x", next.clone()).expect("set");
427            cur = next;
428        }
429        Value::Table(root)
430    }
431
432    /// `cache:set` serializes script values: without the depth guard a
433    /// deep chain recursed to a stack-overflow abort here too.
434    #[test]
435    fn set_rejects_values_nested_beyond_the_json_depth_bound() {
436        let lua = Lua::new();
437        let ud = lua
438            .create_userdata(cache(CacheOptions::default()))
439            .expect("ud");
440        lua.globals().set("cache", ud).expect("global");
441        lua.globals()
442            .set("deep", deep_table(&lua, 129))
443            .expect("global");
444        let err: String = lua
445            .load(
446                r#"local ok, err = pcall(function() cache:set("k", deep) end)
447                   assert(not ok)
448                   return tostring(err)"#,
449            )
450            .eval()
451            .expect("eval");
452        assert!(err.contains("nested deeper than 128 levels"), "got: {err}");
453    }
454
455    /// Storing nil is removing: a stored JSON `null` read back as a
456    /// truthy light userdata, so `if cache:get(k)` took the wrong branch.
457    #[test]
458    fn setting_nil_removes_the_key() {
459        let lua = Lua::new();
460        let ud = lua
461            .create_userdata(cache(CacheOptions::default()))
462            .expect("ud");
463        lua.globals().set("cache", ud).expect("global");
464        let (gone, entries): (bool, i64) = lua
465            .load(
466                r#"cache:set("k", 1)
467                   cache:set("k", nil)
468                   return cache:get("k") == nil, cache:stats().entries"#,
469            )
470            .eval()
471            .expect("eval");
472        assert!(gone);
473        assert_eq!(entries, 0);
474    }
475
476    #[test]
477    fn values_round_trip_and_count_against_the_bounds() {
478        let c = cache(CacheOptions::default());
479        c.set_raw("a".into(), b"{\"n\":1}".to_vec(), None)
480            .expect("set");
481        assert_eq!(
482            c.get_raw("a").expect("get").as_deref(),
483            Some(&b"{\"n\":1}"[..])
484        );
485        assert_eq!(c.get_raw("missing").expect("get"), None);
486
487        let inner = c.inner.lock().expect("lock");
488        assert_eq!(inner.entries.len(), 1);
489        // Key and value both count.
490        assert_eq!(inner.bytes, Entry::cost("a", b"{\"n\":1}"));
491        assert_eq!((inner.hits, inner.misses), (1, 1));
492    }
493
494    /// `Cache::clear` (the runner's between-files reset) empties the
495    /// entries and the byte count together, and a clone — the handle
496    /// every state holds — sees the same empty cache.
497    #[test]
498    fn clear_empties_every_handle_to_the_cache() {
499        let c = cache(CacheOptions::default());
500        let shared = c.clone();
501        c.set_raw("a".into(), b"1".to_vec(), Some(60)).expect("set");
502        c.set_raw("b".into(), b"2".to_vec(), None).expect("set");
503        shared.clear().expect("clear");
504        assert_eq!(c.get_raw("a").expect("get"), None);
505        assert_eq!(c.get_raw("b").expect("get"), None);
506        let inner = c.inner.lock().expect("lock");
507        assert!(inner.entries.is_empty() && inner.lru.is_empty() && inner.expiry.is_empty());
508        assert_eq!(inner.bytes, 0);
509    }
510
511    #[test]
512    fn overwriting_a_key_does_not_double_count_its_bytes() {
513        let c = cache(CacheOptions::default());
514        c.set_raw("k".into(), vec![b'x'; 100], None).expect("set");
515        c.set_raw("k".into(), vec![b'y'; 10], None)
516            .expect("overwrite");
517        let inner = c.inner.lock().expect("lock");
518        assert_eq!(inner.entries.len(), 1);
519        assert_eq!(inner.bytes, Entry::cost("k", &[b'y'; 10]));
520    }
521
522    #[test]
523    fn the_least_recently_used_entry_is_evicted_first() {
524        let c = cache(CacheOptions {
525            max_entries: 2,
526            ..Default::default()
527        });
528        c.set_raw("a".into(), b"1".to_vec(), None).expect("set a");
529        c.set_raw("b".into(), b"2".to_vec(), None).expect("set b");
530        // Touch `a`, so `b` becomes the least recently used.
531        c.get_raw("a").expect("get a");
532        c.set_raw("c".into(), b"3".to_vec(), None).expect("set c");
533
534        assert!(c.get_raw("a").expect("a").is_some());
535        assert!(c.get_raw("b").expect("b").is_none(), "b must be evicted");
536        assert!(c.get_raw("c").expect("c").is_some());
537    }
538
539    #[test]
540    fn the_byte_bound_evicts_too() {
541        let c = cache(CacheOptions {
542            max_bytes: 100,
543            ..Default::default()
544        });
545        c.set_raw("a".into(), vec![b'x'; 60], None).expect("set a");
546        c.set_raw("b".into(), vec![b'x'; 60], None).expect("set b");
547
548        let inner = c.inner.lock().expect("lock");
549        assert!(inner.bytes <= 100, "bytes must stay within the bound");
550        assert_eq!(inner.entries.len(), 1);
551        assert_eq!(inner.evictions, 1);
552    }
553
554    #[test]
555    fn a_value_larger_than_the_whole_cache_is_refused() {
556        let c = cache(CacheOptions {
557            max_bytes: 10,
558            ..Default::default()
559        });
560        let err = c
561            .set_raw("big".into(), vec![b'x'; 11], None)
562            .expect_err("must be refused");
563        assert!(err.to_string().contains("larger than"), "{err}");
564    }
565
566    #[test]
567    fn an_expired_entry_reads_as_a_miss_and_frees_its_bytes() {
568        let c = cache(CacheOptions::default());
569        // A zero TTL means "no expiry", so expiry is set directly here.
570        c.set_raw("k".into(), vec![b'x'; 50], Some(1)).expect("set");
571        {
572            let mut inner = c.inner.lock().expect("lock");
573            let entry = inner.entries.get_mut("k").expect("entry");
574            entry.expires_at = Some(Instant::now() - Duration::from_secs(1));
575        }
576        assert!(c.get_raw("k").expect("get").is_none());
577        assert_eq!(c.inner.lock().expect("lock").bytes, 0);
578    }
579
580    #[test]
581    fn a_zero_ttl_never_expires() {
582        let c = cache(CacheOptions {
583            default_ttl: 0,
584            ..Default::default()
585        });
586        c.set_raw("k".into(), b"v".to_vec(), None).expect("set");
587        assert!(
588            c.inner.lock().expect("lock").entries["k"]
589                .expires_at
590                .is_none()
591        );
592    }
593}