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}