chadtmiller.com/hud
A remote MCP server that shows atproto records as interactive UI inside MCP Apps hosts
place.hud.hudkit 0.3.1 Latest 5 packages
0
0
//! 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()));
}
}