~ knotless Search/
↑↓ move↵ open⇧↵ all results

chadtmiller.com/hud

A remote MCP server that shows atproto records as interactive UI inside MCP Apps hosts

0
0
616 lines · 20.4 KB Raw History
//! A map whose entries expire: the server's memory of what it looked up,
//! each kept as long as its kind says. It holds at most `cap` entries and
//! about `bytes` bytes, each entry weighed as it is put (`Weigh`); past
//! either, the expired go, then those nearest their end, until it is three
//! quarters full, which costs only lookups made again. A value weighing
//! more than a quarter of `bytes` is not kept at all. Each lookup is
//! counted, a hit or a miss, for `/metrics` and the summary each minute.
//!
//! A `Shared` is a `Ttl` filled once for all who ask for a key at once:
//! the first to ask fills it, and the rest wait for that answer.

use serde_json::Value;
use std::collections::{BTreeMap, HashMap};
use std::hash::Hash;
use std::mem::size_of;
use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
use std::sync::{Arc, Mutex, MutexGuard, PoisonError};
use std::time::{Duration, Instant};
use tokio::sync::watch;

/// About how many bytes a value holds, on the heap and inline.
pub trait Weigh {
    fn weigh(&self) -> usize;
}

impl Weigh for String {
    fn weigh(&self) -> usize {
        size_of::<String>() + self.len()
    }
}

impl Weigh for Value {
    fn weigh(&self) -> usize {
        size_of::<Value>()
            + match self {
                Value::String(s) => s.len(),
                Value::Array(a) => a.iter().map(Weigh::weigh).sum(),
                // A map entry: its key and value, and the map's own links.
                Value::Object(o) => o.iter().map(|(k, v)| k.weigh() + v.weigh() + 16).sum(),
                _ => 0,
            }
    }
}

impl<T: Weigh> Weigh for Arc<T> {
    fn weigh(&self) -> usize {
        size_of::<Self>() + T::weigh(self)
    }
}

impl<T: Weigh> Weigh for Option<T> {
    fn weigh(&self) -> usize {
        self.as_ref().map_or(size_of::<Self>(), Weigh::weigh)
    }
}

impl<T: Weigh, E: Weigh> Weigh for Result<T, E> {
    fn weigh(&self) -> usize {
        match self {
            Ok(v) => v.weigh(),
            Err(e) => e.weigh(),
        }
    }
}

impl<T: Weigh> Weigh for Vec<T> {
    fn weigh(&self) -> usize {
        size_of::<Self>() + self.iter().map(Weigh::weigh).sum::<usize>()
    }
}

impl<K: Weigh, V: Weigh> Weigh for BTreeMap<K, V> {
    fn weigh(&self) -> usize {
        size_of::<Self>()
            + self
                .iter()
                .map(|(k, v)| k.weigh() + v.weigh() + 16)
                .sum::<usize>()
    }
}

impl<A: Weigh, B: Weigh> Weigh for (A, B) {
    fn weigh(&self) -> usize {
        self.0.weigh() + self.1.weigh()
    }
}

impl Weigh for crate::pds::Record {
    fn weigh(&self) -> usize {
        self.uri.weigh() + self.cid.weigh() + self.value.weigh()
    }
}

impl Weigh for crate::backlinks::Count {
    fn weigh(&self) -> usize {
        size_of::<Self>()
    }
}

impl Weigh for crate::interactions::Generator {
    fn weigh(&self) -> usize {
        self.did.weigh() + size_of::<bool>()
    }
}

impl Weigh for crate::feeds::SavedFeed {
    fn weigh(&self) -> usize {
        self.name.weigh() + self.uri.weigh() + size_of::<bool>()
    }
}

impl Weigh for crate::xrpc::Asking {
    fn weigh(&self) -> usize {
        self.viewer.weigh() + self.service.weigh() + self.method.weigh() + self.pairs.weigh()
    }
}

/// What a cache holds now: its entries and their weight.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Held {
    pub entries: usize,
    pub bytes: usize,
}

/// The map's own cost of an entry, beside its key and value.
const ENTRY: usize = 48;

struct Inner<K, V> {
    entries: HashMap<K, (Instant, usize, V)>,
    bytes: usize,
}

pub struct Ttl<K, V> {
    inner: Mutex<Inner<K, V>>,
    cap: usize,
    bytes: usize,
    hits: AtomicU64,
    misses: AtomicU64,
}

impl<K: Eq + Hash + Clone + Weigh, V: Clone + Weigh> Ttl<K, V> {
    /// A cache of at most `cap` entries and about `bytes` bytes.
    pub fn new(cap: usize, bytes: usize) -> Ttl<K, V> {
        Ttl {
            inner: Mutex::new(Inner {
                entries: HashMap::new(),
                bytes: 0,
            }),
            cap,
            bytes,
            hits: AtomicU64::new(0),
            misses: AtomicU64::new(0),
        }
    }

    fn lock(&self) -> MutexGuard<'_, Inner<K, V>> {
        self.inner.lock().unwrap_or_else(PoisonError::into_inner)
    }

    /// The value kept for `key`, if it has not expired.
    pub fn get(&self, key: &K) -> Option<V> {
        let found = self.found(key);
        let counted = match found {
            Some(_) => &self.hits,
            None => &self.misses,
        };
        counted.fetch_add(1, Ordering::Relaxed);
        found
    }

    fn found(&self, key: &K) -> Option<V> {
        let mut inner = self.lock();
        match inner.entries.get(key) {
            Some((until, _, v)) if *until > Instant::now() => Some(v.clone()),
            Some(_) => {
                inner.bytes -= inner.entries.remove(key).map_or(0, |(_, w, _)| w);
                None
            }
            None => None,
        }
    }

    /// Its hits and misses since it was made.
    pub fn lookups(&self) -> (u64, u64) {
        let hits = self.hits.load(Ordering::Relaxed);
        (hits, self.misses.load(Ordering::Relaxed))
    }

    /// Keep `value` for `key` for `ttl`, unless it weighs too much to.
    pub fn put(&self, key: K, value: V, ttl: Duration) {
        let weight = ENTRY + key.weigh() + value.weigh();
        let mut inner = self.lock();
        if let Some((_, w, _)) = inner.entries.remove(&key) {
            inner.bytes -= w;
        }
        if weight > self.bytes / 4 {
            return;
        }
        if inner.entries.len() >= self.cap || inner.bytes + weight > self.bytes {
            self.evict(&mut inner);
        }
        inner.bytes += weight;
        inner
            .entries
            .insert(key, (Instant::now() + ttl, weight, value));
    }

    /// The expired out, then those nearest their end, to three quarters full.
    fn evict(&self, inner: &mut Inner<K, V>) {
        let now = Instant::now();
        let mut freed = 0;
        inner.entries.retain(|_, (until, w, _)| {
            let keep = *until > now;
            if !keep {
                freed += *w;
            }
            keep
        });
        inner.bytes -= freed;
        let (cap, bytes) = (self.cap * 3 / 4, self.bytes * 3 / 4);
        if inner.entries.len() <= cap && inner.bytes <= bytes {
            return;
        }
        let mut by_end: Vec<(Instant, K)> = inner
            .entries
            .iter()
            .map(|(k, (until, _, _))| (*until, k.clone()))
            .collect();
        by_end.sort_unstable_by_key(|(until, _)| *until);
        for (_, k) in by_end {
            if inner.entries.len() <= cap && inner.bytes <= bytes {
                break;
            }
            inner.bytes -= inner.entries.remove(&k).map_or(0, |(_, w, _)| w);
        }
    }

    /// Forget every entry whose key `gone` picks.
    pub fn forget(&self, gone: impl Fn(&K) -> bool) {
        let mut inner = self.lock();
        let mut freed = 0;
        inner.entries.retain(|k, (_, w, _)| {
            let keep = !gone(k);
            if !keep {
                freed += *w;
            }
            keep
        });
        inner.bytes -= freed;
    }

    /// What it holds now.
    pub fn held(&self) -> Held {
        let inner = self.lock();
        Held {
            entries: inner.entries.len(),
            bytes: inner.bytes,
        }
    }
}

/// A `Ttl` filled once for all who ask for a key at once: the first to ask
/// fills it, and the rest wait for that answer. An error is shared with
/// those waiting but never kept. A filler dropped before it answers (what
/// asked stopped waiting) leaves those waiting to ask again, one of them
/// filling. What is forgotten while it is filled is not kept.
pub struct Shared<K, V, E> {
    kept: Ttl<K, V>,
    flying: Mutex<HashMap<K, Flight<V, E>>>,
}

/// A fill under way: its answer once it comes, and whether what it fills
/// was forgotten since it began.
struct Flight<V, E> {
    answer: watch::Receiver<Option<Result<V, E>>>,
    stale: Arc<AtomicBool>,
}

impl<K: Eq + Hash + Clone + Weigh, V: Clone + Weigh, E: Clone> Shared<K, V, E> {
    /// A cache of at most `cap` entries and about `bytes` bytes.
    pub fn new(cap: usize, bytes: usize) -> Shared<K, V, E> {
        Shared {
            kept: Ttl::new(cap, bytes),
            flying: Mutex::new(HashMap::new()),
        }
    }

    fn flying(&self) -> MutexGuard<'_, HashMap<K, Flight<V, E>>> {
        self.flying.lock().unwrap_or_else(PoisonError::into_inner)
    }

    /// The value kept for `key`; else the answer of the fill under way for
    /// it; else `fill`'s, a value kept for `ttl`.
    pub async fn get_or(
        &self,
        key: K,
        ttl: Duration,
        fill: impl Future<Output = Result<V, E>>,
    ) -> Result<V, E> {
        let lead = loop {
            let mut answer = {
                let mut flying = self.flying();
                if let Some(v) = self.kept.get(&key) {
                    return Ok(v);
                }
                match flying.get(&key) {
                    Some(f) => f.answer.clone(),
                    None => {
                        let (tx, answer) = watch::channel(None);
                        let stale = Arc::new(AtomicBool::new(false));
                        let flight = Flight {
                            answer,
                            stale: stale.clone(),
                        };
                        flying.insert(key.clone(), flight);
                        break Landing {
                            shared: self,
                            key: &key,
                            tx,
                            stale,
                        };
                    }
                }
            };
            // None where the filler was dropped: ask again.
            let got = answer.wait_for(Option::is_some).await.ok();
            if let Some(got) = got.and_then(|a| a.clone()) {
                return got;
            }
        };
        let got = fill.await;
        lead.land(&got, ttl);
        got
    }

    /// Forget every value whose key `gone` picks, and keep none that a fill
    /// under way for one answers.
    pub fn forget(&self, gone: &dyn Fn(&K) -> bool) {
        let mut flying = self.flying();
        flying.retain(|k, f| {
            let keep = !gone(k);
            if !keep {
                f.stale.store(true, Ordering::Relaxed);
            }
            keep
        });
        self.kept.forget(gone);
    }

    /// What it holds now.
    pub fn held(&self) -> Held {
        self.kept.held()
    }

    /// Its hits and misses since it was made.
    pub fn lookups(&self) -> (u64, u64) {
        self.kept.lookups()
    }
}

/// The fill a caller leads: it lands the answer, and dropped, answered or
/// not, takes its flight off the board, so those asking next fill anew.
struct Landing<'a, K: Eq + Hash, V, E> {
    shared: &'a Shared<K, V, E>,
    key: &'a K,
    tx: watch::Sender<Option<Result<V, E>>>,
    stale: Arc<AtomicBool>,
}

impl<K: Eq + Hash + Clone + Weigh, V: Clone + Weigh, E: Clone> Landing<'_, K, V, E> {
    /// Keep a value unless it was forgotten as it flew (under the board's
    /// lock, as `forget` forgets), then give those waiting the answer.
    fn land(&self, got: &Result<V, E>, ttl: Duration) {
        let flying = self.shared.flying();
        if let Ok(v) = got
            && !self.stale.load(Ordering::Relaxed)
        {
            self.shared.kept.put(self.key.clone(), v.clone(), ttl);
        }
        drop(flying);
        self.tx.send_replace(Some(got.clone()));
    }
}

impl<K: Eq + Hash, V, E> Drop for Landing<'_, K, V, E> {
    fn drop(&mut self) {
        let mut flying = self
            .shared
            .flying
            .lock()
            .unwrap_or_else(PoisonError::into_inner);
        // Its own flight, unless it was forgotten and another took its place.
        if flying
            .get(self.key)
            .is_some_and(|f| Arc::ptr_eq(&f.stale, &self.stale))
        {
            flying.remove(self.key);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use serde_json::json;

    #[test]
    fn expires_and_caps() {
        let c = Ttl::new(2, 1 << 20);
        let s = |v: &str| v.to_string();
        c.put(s("a"), s("1"), Duration::from_secs(60));
        c.put(s("gone"), s("2"), Duration::ZERO);
        assert_eq!(c.get(&s("a")), Some(s("1")));
        assert_eq!(c.get(&s("gone")), None);
        assert_eq!(c.get(&s("never")), None);
        c.put(s("b"), s("3"), Duration::from_secs(60));
        c.put(s("c"), s("4"), Duration::from_secs(60));
        assert_eq!(c.get(&s("c")), Some(s("4")));
        assert!(c.held().entries <= 2);
    }

    #[test]
    fn the_expired_go_first_and_alone_when_that_is_room_enough() {
        let c = Ttl::new(4, 1 << 20);
        let s = |v: &str| v.to_string();
        for k in ["a", "b", "c"] {
            c.put(s(k), s("live"), Duration::from_secs(60));
        }
        c.put(s("stale"), s("old"), Duration::ZERO);
        // Full: the expired one makes room, and nothing live goes.
        c.put(s("d"), s("new"), Duration::from_secs(60));
        for k in ["a", "b", "c", "d"] {
            assert_eq!(
                c.get(&s(k)).as_deref(),
                Some(if k == "d" { "new" } else { "live" })
            );
        }
        let held = c.held();
        assert_eq!(held.entries, 4);
        assert_eq!(
            held.bytes,
            c.lock().entries.values().map(|(_, w, _)| w).sum::<usize>()
        );
    }

    #[test]
    fn records_weigh_their_text() {
        let record = |text: &str| crate::pds::Record {
            uri: "at://did:plc:x/a.b.c/1".into(),
            cid: "bafy".into(),
            value: json!({ "text": text }),
        };
        let small = Arc::new(vec![record("")]).weigh();
        let large = Arc::new(vec![record(&"x".repeat(10_000)), record("")]).weigh();
        assert!(
            large >= small + record("").weigh() + 10_000,
            "{small} {large}"
        );
        // A repository's records too heavy for a members cache are not kept.
        let c: Ttl<String, Arc<Vec<crate::pds::Record>>> = Ttl::new(10, 16 * 1024);
        c.put(
            "light".into(),
            Arc::new(vec![record("")]),
            Duration::from_secs(60),
        );
        c.put(
            "heavy".into(),
            Arc::new(vec![record(&"x".repeat(10_000))]),
            Duration::from_secs(60),
        );
        assert!(c.get(&"light".to_string()).is_some());
        assert!(c.get(&"heavy".to_string()).is_none());
    }

    #[test]
    fn bounded_by_bytes() {
        let c: Ttl<String, Value> = Ttl::new(1_000, 64 * 1024);
        let big = json!({ "text": "x".repeat(1_000) });
        for i in 0..200 {
            c.put(format!("k{i}"), big.clone(), Duration::from_secs(60 + i));
            assert!(c.held().bytes <= 64 * 1024, "{:?}", c.held());
        }
        // Those nearest their end went first: the latest are kept.
        assert!(c.get(&"k199".to_string()).is_some());
        assert!(c.get(&"k0".to_string()).is_none());
        // One too heavy for it is not kept, and leaves nothing behind.
        c.put(
            "k199".into(),
            json!("x".repeat(17 * 1024)),
            Duration::from_secs(60),
        );
        assert!(c.get(&"k199".to_string()).is_none());
        let held = c.held();
        assert_eq!(
            held.bytes,
            c.lock().entries.values().map(|(_, w, _)| w).sum::<usize>()
        );
    }

    #[test]
    fn weighs_json() {
        let small = json!({ "a": 1 }).weigh();
        let large = json!({ "a": "x".repeat(10_000) }).weigh();
        assert!(large > small + 10_000 - 1);
    }

    type Strings = Shared<(String, String), String, String>;

    /// A key: who asked, and what.
    fn key(who: &str, what: &str) -> (String, String) {
        (who.to_string(), what.to_string())
    }

    /// A fill answering `answer` after a moment, counted in `calls` as it
    /// starts.
    async fn counted(calls: &AtomicU64, answer: Result<&str, &str>) -> Result<String, String> {
        calls.fetch_add(1, Ordering::SeqCst);
        tokio::time::sleep(Duration::from_millis(20)).await;
        answer.map(str::to_string).map_err(str::to_string)
    }

    #[tokio::test]
    async fn shared_keeps_a_value_its_time_and_never_an_error() {
        let c = Strings::new(10, 1 << 20);
        let calls = AtomicU64::new(0);
        let ttl = Duration::from_millis(200);
        let ask = |what: &str, answer| c.get_or(key("a", what), ttl, counted(&calls, answer));
        // Filled, then within its time kept: the second fill is never run.
        assert_eq!(ask("q", Ok("1")).await, Ok("1".into()));
        assert_eq!(ask("q", Ok("2")).await, Ok("1".into()));
        assert_eq!(calls.load(Ordering::SeqCst), 1);
        // Past it, filled again.
        tokio::time::sleep(ttl).await;
        assert_eq!(ask("q", Ok("2")).await, Ok("2".into()));
        // An error is not kept: the next ask fills.
        assert_eq!(ask("e", Err("down")).await, Err("down".into()));
        assert_eq!(ask("e", Ok("up")).await, Ok("up".into()));
        assert_eq!(calls.load(Ordering::SeqCst), 4);
        assert_eq!(c.lookups(), (1, 4));
        assert_eq!(c.held().entries, 2);
    }

    #[tokio::test]
    async fn shared_fills_once_for_all_asking_at_once() {
        let c = Strings::new(10, 1 << 20);
        let calls = AtomicU64::new(0);
        let ttl = Duration::from_secs(60);
        let answers = ["1", "2", "3", "4", "5"];
        let asks = answers.map(|a| c.get_or(key("a", "q"), ttl, counted(&calls, Ok(a))));
        let got = futures::future::join_all(asks).await;
        assert_eq!(got, vec![Ok("1".to_string()); 5]);
        assert_eq!(calls.load(Ordering::SeqCst), 1);
        // An error too is had by all asking at once, and not kept.
        let asks = (0..3).map(|_| c.get_or(key("a", "e"), ttl, counted(&calls, Err("down"))));
        let got = futures::future::join_all(asks).await;
        assert_eq!(got, vec![Err("down".to_string()); 3]);
        assert_eq!(calls.load(Ordering::SeqCst), 2);
        let again = c.get_or(key("a", "e"), ttl, counted(&calls, Ok("up")));
        assert_eq!(again.await, Ok("up".into()));
        assert_eq!(calls.load(Ordering::SeqCst), 3);
    }

    #[tokio::test]
    async fn shared_asks_again_where_its_filler_stopped_waiting() {
        let c = Strings::new(10, 1 << 20);
        let calls = AtomicU64::new(0);
        let ttl = Duration::from_secs(60);
        // The first to ask stops waiting before its fill answers; the one
        // waiting on it fills.
        let first = tokio::time::timeout(
            Duration::from_millis(5),
            c.get_or(key("a", "q"), ttl, counted(&calls, Ok("1"))),
        );
        let second = c.get_or(key("a", "q"), ttl, counted(&calls, Ok("2")));
        let (first, second) = tokio::join!(first, second);
        assert!(first.is_err());
        assert_eq!(second, Ok("2".into()));
        assert_eq!(calls.load(Ordering::SeqCst), 2);
        let kept = c.get_or(key("a", "q"), ttl, counted(&calls, Ok("3")));
        assert_eq!(kept.await, Ok("2".into()));
    }

    #[tokio::test]
    async fn shared_forgets_what_it_is_told_to_and_what_flew_meanwhile() {
        let c = Strings::new(10, 1 << 20);
        let calls = AtomicU64::new(0);
        let ttl = Duration::from_secs(60);
        let ask = |who: &str, answer| c.get_or(key(who, "q"), ttl, counted(&calls, answer));
        ask("alice", Ok("a1")).await.unwrap();
        ask("bob", Ok("b1")).await.unwrap();
        // Alice's alone forgotten.
        c.forget(&|(who, _)| who == "alice");
        assert_eq!(ask("alice", Ok("a2")).await, Ok("a2".into()));
        assert_eq!(ask("bob", Ok("b2")).await, Ok("b1".into()));
        // Forgotten as it flies: who asked has its answer, but it is not
        // kept, and who asks after asks anew.
        let (sent, landed) = tokio::sync::oneshot::channel::<()>();
        let slow = async {
            landed.await.unwrap();
            Ok("old".to_string())
        };
        let flying = c.get_or(key("carol", "q"), ttl, slow);
        let after = async {
            tokio::task::yield_now().await;
            // Another's forgotten, Carol's flies on; then hers.
            c.forget(&|(who, _)| who == "dave");
            c.forget(&|(who, _)| who == "carol");
            let anew = ask("carol", Ok("new")).await;
            sent.send(()).unwrap();
            anew
        };
        let (flown, anew) = tokio::join!(flying, after);
        assert_eq!((flown, anew), (Ok("old".into()), Ok("new".into())));
        assert_eq!(ask("carol", Ok("x")).await, Ok("new".into()));
    }
}