Skip to main content

unityrs_core/
once.rs

1//! Lazily computed values, published without holding anything while they
2//! are computed.
3//!
4//! A lazy value in the core (a parsed bundle entry, a compiled tree, a
5//! container, a registry slot) may take caller code to compute: a
6//! [`crate::codec::BlockCodec`], a [`crate::provider::TypeTreeProvider`], the
7//! [`crate::budget::MemoryBudget`] every charge books with. Computing it
8//! inside `OnceLock::get_or_init` would run that code while the cell is
9//! locked, so a callback that reaches the same cell deadlocks, and a binding
10//! thread holding Python's GIL while it waits on the cell deadlocks against
11//! a computing thread whose Python callback needs the GIL (plan section
12//! 3.16). [`get_or_publish`] computes with nothing held and then publishes:
13//! the first value published wins, and a value computed by a thread that
14//! lost the race is dropped (its charges with it).
15//!
16//! **Fallible values** go through [`get_or_publish_result`], which publishes
17//! a value and the errors the input decides, and never a *transient* one: a
18//! budget or meter refusal depends on what else is held at that moment (two
19//! threads computing the same value at once can cause it themselves), so
20//! publishing it would fail every later ask of a shared dependency for the
21//! handle's life, however empty the pool later is. A transient error is
22//! returned unpublished and the next ask computes again. A published error
23//! is charged to the input's meter for the heap it owns ([`CellError`]), so
24//! a table of failing cells is paid for like any other, and every later ask
25//! gets a clone that shares that heap (the core's errors hold their strings
26//! and nested errors in `Arc`s), so a caller that keeps many answers holds
27//! no more (`tests/files_memory.rs`).
28//!
29//! **Work.** A computation that ends in an error its cell does not keep runs
30//! again on the next ask, so an input could make its readers repeat it
31//! without end (one type whose compile alone needs more than the meter,
32//! asked by every object of the type). When the input's meter itself
33//! refused it ([`CellError::is_meter_refusal`]), every byte the meter
34//! granted to the computation on its own thread is therefore counted as the
35//! open's work ([`crate::limits::Limits::max_decode_work`], shared with
36//! block decodes), and once work has passed that allowance an ask that would
37//! compute keeps a [`crate::LimitKind::DecodeWork`] refusal instead, which
38//! is not transient. Nothing else counts (round 6): grants another thread
39//! made on the same meter meanwhile are that thread's work, and a refusal
40//! by the budget, an I/O failure or a provider's failure depends on what
41//! else is held or on caller code, so counting it would let contention use
42//! up a valid shared dependency's allowance for the handle's life. Those
43//! repeat as often as the caller asks, which the engine bounds (plan 4.1).
44//!
45//! A compute has no side effect but its charges: what follows from a value
46//! (registering a nested container's entries) is done from the published
47//! value, after publishing, so a value that lost the race leaves nothing.
48//!
49//! Owner: the scaffold (implemented). Every lazily computed value in the
50//! core goes through it; no `get_or_init` runs anything but a move.
51
52use std::fmt;
53use std::sync::{Arc, OnceLock};
54
55use crate::error::LimitError;
56use crate::limits::{Charge, GrantScope, Meter};
57
58/// The value in `cell`, computing it with `compute` first when there is
59/// none. `compute` runs with no lock held, so it may call caller code, and
60/// it may even re-enter this cell; when two threads compute at once, the
61/// first to publish wins and the other's value is dropped.
62pub fn get_or_publish<T>(cell: &OnceLock<T>, compute: impl FnOnce() -> T) -> &T {
63    if let Some(v) = cell.get() {
64        return v;
65    }
66    let v = compute();
67    // A move: the only thing that ever runs inside the cell's lock.
68    cell.get_or_init(move || v)
69}
70
71/// What a cell must know about an error before it keeps it.
72pub trait CellError: Send + Sync {
73    /// Whether the error depends on more than the input: a budget or meter
74    /// refusal ([`crate::LimitKind::InputMemory`]), an I/O failure, a
75    /// provider's failure. Such an error is returned, never published.
76    fn is_transient(&self) -> bool;
77    /// Whether the error is the input's own meter refusing a charge
78    /// ([`crate::LimitKind::InputMemory`]), and not the budget, I/O or a
79    /// provider: what a computation that ends in it was granted counts as
80    /// its open's work (module docs).
81    fn is_meter_refusal(&self) -> bool;
82    /// The heap the error owns ([`crate::limits::heap_cost`] of each `Arc`
83    /// and string it holds, counted whether or not a string shares a file's
84    /// buffer), charged to the input's meter while a cell keeps it. A clone
85    /// shares that heap and allocates nothing.
86    fn heap_bytes(&self) -> u64;
87    /// The error for an ask refused because its open's work has passed its
88    /// allowance (`limit` is a [`crate::LimitKind::DecodeWork`] refusal): not
89    /// transient, so the cell keeps it (module docs).
90    fn work_refused(limit: LimitError) -> Self
91    where
92        Self: Sized;
93}
94
95/// An error a cell keeps, with the charge for its heap.
96pub struct KeptError<E> {
97    error: E,
98    charge: Charge,
99}
100
101impl<E> KeptError<E> {
102    pub(crate) fn into_parts(self) -> (E, Charge) {
103        (self.error, self.charge)
104    }
105
106    /// The error.
107    pub fn error(&self) -> &E {
108        &self.error
109    }
110}
111
112impl<E: fmt::Debug> fmt::Debug for KeptError<E> {
113    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
114        self.error.fmt(f)
115    }
116}
117
118/// A cell of a fallible value: the value, or an input-determined error with
119/// its charge.
120pub type ResultCell<T, E> = OnceLock<Result<T, KeptError<E>>>;
121
122/// The value in `cell`, computing it with `compute` first when there is
123/// none (as [`get_or_publish`]). An error the input decides is published
124/// with a charge on `meter` for its heap, and returned (cloned) to every
125/// later ask; a transient error ([`CellError::is_transient`]), or one whose
126/// charge the meter refuses, is returned unpublished, so the next ask
127/// computes again. `meter` is the meter of the open the computation charges:
128/// what it granted the computation, on this thread, counts as that open's
129/// work when the computation ends in the meter's own refusal, and once the
130/// work has passed its allowance an ask keeps a refusal instead of computing
131/// (module docs).
132pub fn get_or_publish_result<'a, T, E: CellError + Clone>(
133    cell: &'a ResultCell<T, E>,
134    meter: &Arc<Meter>,
135    compute: impl FnOnce() -> Result<T, E>,
136) -> Result<&'a T, E> {
137    let published = |r: &'a Result<T, KeptError<E>>| r.as_ref().map_err(|k| k.error.clone());
138    if let Some(r) = cell.get() {
139        return published(r);
140    }
141    if let Some(used_up) = meter.work_refused() {
142        return keep(cell, meter, E::work_refused(used_up));
143    }
144    let scope = GrantScope::enter(meter);
145    let got = compute();
146    let own = scope.finish(meter);
147    match got {
148        Ok(v) => published(cell.get_or_init(move || Ok(v))),
149        Err(e) if e.is_transient() => {
150            if e.is_meter_refusal() {
151                meter.add_work(own);
152            }
153            Err(e)
154        }
155        Err(e) => keep(cell, meter, e),
156    }
157}
158
159/// Publishes `e` in `cell` with a charge on `meter` for its heap and returns
160/// what the cell holds; an error the meter has no room to keep is returned
161/// unpublished.
162fn keep<'a, T, E: CellError + Clone>(
163    cell: &'a ResultCell<T, E>,
164    meter: &Arc<Meter>,
165    e: E,
166) -> Result<&'a T, E> {
167    match meter.charge(e.heap_bytes()) {
168        Ok(charge) => {
169            let kept = KeptError { error: e, charge };
170            cell.get_or_init(move || Err(kept))
171                .as_ref()
172                .map_err(|k| k.error.clone())
173        }
174        Err(_) => Err(e),
175    }
176}
177
178#[cfg(test)]
179mod tests {
180    use std::sync::atomic::{AtomicUsize, Ordering};
181    use std::sync::{Arc, OnceLock};
182
183    use super::get_or_publish;
184
185    /// Runs `f` on a thread and fails, past the deadlock guard
186    /// (`unityrs_testkit::guard`), if it has not returned, rather than
187    /// hanging the test run.
188    fn finishes<T: Send + 'static>(f: impl FnOnce() -> T + Send + 'static) -> T {
189        unityrs_testkit::guard::finishes("the compute (running it inside the cell deadlocks it)", f)
190    }
191
192    #[test]
193    fn a_compute_that_re_enters_its_cell_does_not_deadlock() {
194        let got = finishes(|| {
195            let cell = OnceLock::new();
196            // The callback asks for the same lazy value (a codec or provider
197            // that reads the same entry): the inner call computes and
198            // publishes, and the outer call's value loses.
199            let v = *get_or_publish(&cell, || *get_or_publish(&cell, || 2) + 1);
200            (v, cell.get().copied())
201        });
202        assert_eq!(got, (2, Some(2)));
203    }
204
205    #[test]
206    fn a_thread_holding_a_lock_the_compute_needs_does_not_wait_on_the_cell() {
207        // Thread A computes and needs `gil` (a Python codec); thread B holds
208        // `gil` and asks for the same value. B must not wait on A's compute.
209        let got = finishes(|| {
210            let cell = Arc::new(OnceLock::new());
211            let gil = Arc::new(std::sync::Mutex::new(()));
212            let started = Arc::new(std::sync::Barrier::new(2));
213            let a = {
214                let (cell, gil, started) = (cell.clone(), gil.clone(), started.clone());
215                std::thread::spawn(move || {
216                    *get_or_publish(&cell, || {
217                        started.wait();
218                        let _held = gil.lock().unwrap();
219                        1
220                    })
221                })
222            };
223            let held = gil.lock().unwrap();
224            started.wait();
225            let b = *get_or_publish(&cell, || 2);
226            drop(held);
227            let a = a.join().unwrap();
228            (a, b)
229        });
230        assert_eq!(got.0, got.1, "both see the one published value");
231    }
232
233    /// A failure for the cell tests: transient or not, owning `heap` bytes.
234    #[derive(Clone, Debug, PartialEq, Eq)]
235    struct Failed {
236        transient: bool,
237        heap: u64,
238    }
239
240    impl super::CellError for Failed {
241        fn is_transient(&self) -> bool {
242            self.transient
243        }
244        fn is_meter_refusal(&self) -> bool {
245            false
246        }
247        fn heap_bytes(&self) -> u64 {
248            self.heap
249        }
250        fn work_refused(_: crate::error::LimitError) -> Self {
251            Self {
252                transient: false,
253                heap: 0,
254            }
255        }
256    }
257
258    #[test]
259    fn a_refusal_is_not_published_and_the_next_ask_computes_again() {
260        use crate::budget::{Counting, Reservation};
261        use crate::error::Error;
262        use crate::limits::Meter;
263        // Round 3's probe: a pool of 100 bytes with 90 held elsewhere
264        // refuses the compute's 20; once the other reader drops, the same
265        // cell must compute again, not answer the old refusal.
266        let pool = Arc::new(Counting::new(100));
267        let dep = Meter::new(u64::MAX, pool.clone(), Reservation::Dependency);
268        let other = dep.charge(90).unwrap();
269        let cell: super::ResultCell<(u32, crate::limits::Charge), Error> = OnceLock::new();
270        let compute = || dep.charge(20).map(|c| (7, c)).map_err(Error::from);
271        let first = super::get_or_publish_result(&cell, &dep, compute).map(|v| v.0);
272        assert!(matches!(first, Err(Error::Budget(_))), "{first:?}");
273        assert!(cell.get().is_none(), "a refusal is not published");
274        drop(other);
275        let second = super::get_or_publish_result(&cell, &dep, compute).map(|v| v.0);
276        assert_eq!(second.ok(), Some(7));
277        assert_eq!(pool.used(), 20, "the published value keeps its charge");
278    }
279
280    #[test]
281    fn a_compute_refused_on_its_own_stops_at_the_work_bound() {
282        use crate::budget::{Reservation, Unbounded};
283        use crate::error::{Error, LimitKind};
284        use crate::limits::{Limits, Meter};
285        // Round 5: a compute the meter refuses with nothing else held is not
286        // the pool's contention but the input's own need, and it ran again
287        // on every ask. Its grants count as work: 300 bytes per refused run
288        // against 1,000 of work, so the fourth run uses the allowance up and
289        // every later ask answers the kept refusal without computing.
290        let limits = Limits {
291            max_input_memory: 500,
292            max_decode_work: 1000,
293            ..Limits::default()
294        };
295        let m = Meter::for_input(&limits, Arc::new(Unbounded), Reservation::Input);
296        let cell: super::ResultCell<u32, Error> = OnceLock::new();
297        let runs = AtomicUsize::new(0);
298        let compute = || {
299            runs.fetch_add(1, Ordering::Relaxed);
300            let _a = m.charge(300)?;
301            let _b = m.charge(300)?;
302            Ok(7)
303        };
304        let got: Vec<_> = (0..50)
305            .map(|_| super::get_or_publish_result(&cell, &m, compute).copied())
306            .collect();
307        assert_eq!(runs.load(Ordering::Relaxed), 4);
308        assert!(
309            got[..4]
310                .iter()
311                .all(|r| matches!(r, Err(Error::Limit(l)) if l.kind() == LimitKind::InputMemory))
312        );
313        assert!(
314            got[4..]
315                .iter()
316                .all(|r| matches!(r, Err(Error::Limit(l)) if l.kind() == LimitKind::DecodeWork))
317        );
318        assert!(cell.get().is_some(), "the work refusal is kept");
319        assert_eq!((m.decoded(), m.used()), (1200, 0));
320    }
321
322    #[test]
323    fn budget_refusals_count_no_work_and_the_read_succeeds_once_the_pool_empties() {
324        use crate::budget::{Counting, Reservation};
325        use crate::error::Error;
326        use crate::limits::{Limits, Meter};
327        // Round 6 (claude6 M2, C1): every transient failure's grants counted
328        // as work, budget refusals included, so a shared dependency asked
329        // while other jobs held the pool kept `DecodeWork` for good. Here
330        // each refused run is granted 300 bytes against 1,000 of work: 50
331        // refusals are fifteen times the allowance, and none of it counts.
332        let limits = Limits {
333            max_decode_work: 1000,
334            ..Limits::default()
335        };
336        let pool = Arc::new(Counting::new(1000));
337        let dep = Meter::for_input(&limits, pool.clone(), Reservation::Dependency);
338        let other = Meter::new(u64::MAX, pool.clone(), Reservation::Input);
339        let held = other.charge(600).unwrap();
340        let cell: super::ResultCell<u32, Error> = OnceLock::new();
341        let compute = || {
342            let _a = dep.charge(300)?;
343            let _b = dep.charge(300)?;
344            Ok(7)
345        };
346        for _ in 0..50 {
347            let got = super::get_or_publish_result(&cell, &dep, compute).copied();
348            assert!(matches!(got, Err(Error::Budget(_))), "{got:?}");
349        }
350        assert_eq!(dep.decoded(), 0, "contention is not the input's work");
351        drop(held);
352        let got = super::get_or_publish_result(&cell, &dep, compute).copied();
353        assert_eq!(got.ok(), Some(7));
354    }
355
356    #[test]
357    fn another_threads_grants_are_not_a_failing_computations_work() {
358        use crate::budget::{Reservation, Unbounded};
359        use crate::error::{Error, LimitKind};
360        use crate::limits::{Limits, Meter};
361        // Round 6 (claude6 M2, C3): the work counted was the meter's total
362        // grants while the computation ran, so another thread's successful
363        // work on the same open used up a failing computation's allowance.
364        // Here each failing run grants nothing itself while another thread
365        // keeps 1,000 bytes on the same meter, against 4,000 of work.
366        let limits = Limits {
367            max_decode_work: 4000,
368            ..Limits::default()
369        };
370        let m = Meter::for_input(&limits, Arc::new(Unbounded), Reservation::Input);
371        let cell: super::ResultCell<u32, Error> = OnceLock::new();
372        let mut kept = Vec::new();
373        for _ in 0..10 {
374            let got = super::get_or_publish_result(&cell, &m, || {
375                let m = m.clone();
376                kept.push(
377                    std::thread::spawn(move || m.charge(1000).unwrap())
378                        .join()
379                        .unwrap(),
380                );
381                Err(Error::Limit(crate::error::LimitError::refused(
382                    LimitKind::InputMemory,
383                    1,
384                    0,
385                )))
386            });
387            assert!(
388                matches!(got, Err(Error::Limit(l)) if l.kind() == LimitKind::InputMemory),
389                "{got:?}"
390            );
391        }
392        assert_eq!(m.decoded(), 0, "the other thread's grants are its own");
393        assert!(cell.get().is_none(), "nothing kept");
394    }
395
396    #[test]
397    fn an_input_error_is_published_with_a_charge_for_its_heap() {
398        use crate::budget::{Reservation, Unbounded};
399        use crate::limits::Meter;
400        let m = Meter::new(1000, Arc::new(Unbounded), Reservation::Input);
401        let cell: super::ResultCell<u32, Failed> = OnceLock::new();
402        let bad = Failed {
403            transient: false,
404            heap: 48,
405        };
406        let runs = AtomicUsize::new(0);
407        for _ in 0..3 {
408            let got = super::get_or_publish_result(&cell, &m, || {
409                runs.fetch_add(1, Ordering::Relaxed);
410                Err(bad.clone())
411            });
412            assert_eq!(got, Err(bad.clone()));
413        }
414        assert_eq!(runs.load(Ordering::Relaxed), 1, "computed once");
415        assert_eq!(m.used(), 48, "the kept error is charged");
416        drop(cell);
417        assert_eq!(m.used(), 0);
418        // An error the meter has no room to keep is returned, not kept.
419        let full = Meter::new(10, Arc::new(Unbounded), Reservation::Input);
420        let cell: super::ResultCell<u32, Failed> = OnceLock::new();
421        assert!(super::get_or_publish_result(&cell, &full, || Err(bad.clone())).is_err());
422        assert!(cell.get().is_none());
423    }
424
425    #[test]
426    fn the_first_published_value_wins_and_later_computes_never_run() {
427        let runs = AtomicUsize::new(0);
428        let cell = OnceLock::new();
429        let a = *get_or_publish(&cell, || {
430            runs.fetch_add(1, Ordering::Relaxed);
431            7
432        });
433        let b = *get_or_publish(&cell, || {
434            runs.fetch_add(1, Ordering::Relaxed);
435            8
436        });
437        assert_eq!((a, b, runs.load(Ordering::Relaxed)), (7, 7, 1));
438    }
439}