storage/
resident.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at https://mozilla.org/MPL/2.0/.
4// Copyright (c) 2026 2youg1 and the sprawling contributors
5
6//! The working set read back from disk: a cache with a byte budget,
7//! trimmed from its oldest entry, that holds nothing for a frozen run
8//! (`crates/storage/Spec.lean` §8-40).
9//!
10//! The properties it keeps are proved in
11//! `crates/sprawling/spec/Serving/Memory.lean` §8-173: the resident bytes
12//! never exceed the budget, a frozen run holds nothing, and every read
13//! answers the bytes on disk, an evicted entry's included. The budget
14//! counts bytes rather than entries because entries differ in size by
15//! orders of magnitude (sprawling D42).
16
17use std::collections::{BTreeMap, BTreeSet, VecDeque};
18use std::sync::Arc;
19
20/// The whole read-back budget: 12 MiB for the views and the side index
21/// and 12 MiB of read-back, the figure Memory.lean's budget table
22/// proposes until a reading replaces it.
23pub const RESIDENT_TOTAL_BYTES: usize = 24 * 1024 * 1024;
24
25/// Entries in the order they were placed, each owned by one run and named
26/// by its address on disk.
27///
28/// A hit does not reorder: the model trims first in, first out, and only
29/// placing an address again moves it to the newest end.
30pub struct Resident<R, K> {
31    budget: usize,
32    held: usize,
33    order: VecDeque<(R, K)>,
34    bytes: BTreeMap<(R, K), Arc<[u8]>>,
35    frozen: BTreeSet<R>,
36}
37
38impl<R: Ord + Clone, K: Ord + Clone> Resident<R, K> {
39    /// An empty cache that never holds more than `budget_bytes`.
40    pub fn new(budget_bytes: usize) -> Self {
41        Self {
42            budget: budget_bytes,
43            held: 0,
44            order: VecDeque::new(),
45            bytes: BTreeMap::new(),
46            frozen: BTreeSet::new(),
47        }
48    }
49
50    /// Reads `key` from disk through `load` and places it, then drops the
51    /// oldest entries until the cache is within its budget. A frozen run
52    /// is not placed; an entry larger than the budget is not kept. A
53    /// failed `load` changes nothing and its error is returned.
54    pub fn insert<E>(
55        &mut self,
56        owner: &R,
57        key: &K,
58        load: impl FnOnce(&K) -> Result<Vec<u8>, E>,
59    ) -> Result<(), E> {
60        let bytes = Arc::<[u8]>::from(load(key)?);
61        self.place(owner, key, bytes);
62        Ok(())
63    }
64
65    /// Answers the cached bytes on a hit; on a miss reads them through
66    /// `load`, places them as [`Self::insert`] does, and answers them.
67    pub fn read<E>(
68        &mut self,
69        owner: &R,
70        key: &K,
71        load: impl FnOnce(&K) -> Result<Vec<u8>, E>,
72    ) -> Result<Arc<[u8]>, E> {
73        let name = (owner.clone(), key.clone());
74        if let Some(bytes) = self.bytes.get(&name) {
75            return Ok(Arc::clone(bytes));
76        }
77        let bytes = Arc::<[u8]>::from(load(key)?);
78        self.place(owner, key, Arc::clone(&bytes));
79        Ok(bytes)
80    }
81
82    /// Drops the oldest entry, when the system asks for memory back or a
83    /// beat evicts.
84    pub fn evict_oldest(&mut self) {
85        if let Some(name) = self.order.pop_front() {
86            self.forget(&name);
87        }
88    }
89
90    /// Drops every entry of `owner` and places nothing for it afterwards.
91    pub fn freeze(&mut self, owner: &R) {
92        let (gone, kept): (VecDeque<_>, VecDeque<_>) =
93            self.order.drain(..).partition(|(run, _)| run == owner);
94        self.order = kept;
95        gone.iter().for_each(|name| self.forget(name));
96        self.frozen.insert(owner.clone());
97    }
98
99    /// The bytes the cache holds now.
100    pub fn resident_bytes(&self) -> usize {
101        self.held
102    }
103
104    fn place(&mut self, owner: &R, key: &K, bytes: Arc<[u8]>) {
105        if self.frozen.contains(owner) {
106            return;
107        }
108        let name = (owner.clone(), key.clone());
109        if self.bytes.contains_key(&name) {
110            self.order.retain(|placed| placed != &name);
111            self.forget(&name);
112        }
113        self.held = self.held.saturating_add(bytes.len());
114        self.bytes.insert(name.clone(), bytes);
115        self.order.push_back(name);
116        self.trim();
117    }
118
119    /// Drops from the oldest end while the cache is over its budget, the
120    /// newest entry included when it alone is larger than the budget.
121    fn trim(&mut self) {
122        while self.held > self.budget && !self.order.is_empty() {
123            self.evict_oldest();
124        }
125    }
126
127    fn forget(&mut self, name: &(R, K)) {
128        if let Some(bytes) = self.bytes.remove(name) {
129            self.held = self.held.saturating_sub(bytes.len());
130        }
131    }
132}
133
134#[cfg(test)]
135#[path = "resident/tests.rs"]
136mod tests;
storage/resident.rs

storage/
resident.rs
