unityrs_core/limits/meter.rs
1//! The [`Meter`] of one open of an input, the memory account every open of
2//! the input shares, what each lazy computation was granted on its own thread
3//! ([`GrantScope`]), the [`Charge`] each grant is, and how many refusals of
4//! the dependency pool each thread met ([`pool_refusals`]).
5
6use std::cell::Cell;
7use std::fmt;
8use std::mem::size_of;
9use std::sync::Arc;
10use std::sync::atomic::{AtomicU64, Ordering};
11
12use super::{ChargeError, Limits, heap_cost};
13use crate::budget::{AllocError, BudgetExceeded, MemoryBudget, Permit, Reservation, Unbounded};
14use crate::error::{LimitError, LimitKind};
15
16/// The bytes an `Arc` of a `T` of `size` bytes asks for: the value and the
17/// two reference counts.
18const fn arc_bytes(size: usize) -> u64 {
19 size as u64 + 2 * size_of::<usize>() as u64
20}
21
22/// What every open of one input holds: the memory account its meters share.
23struct Account {
24 used: AtomicU64,
25 limit: u64,
26 budget: Arc<dyn MemoryBudget>,
27 what: Reservation,
28}
29
30/// An open's work past its allowance, as [`Meter::work_used_up`] reports
31/// it: a status, not an error, so no refusal is made, or counted, until the
32/// core refuses new work for it.
33#[derive(Clone, Copy, Debug, PartialEq, Eq)]
34pub struct WorkPast {
35 done: u64,
36 allowance: u64,
37}
38
39const _: () = crate::send_sync::<WorkPast>();
40
41impl WorkPast {
42 /// The work counted.
43 #[must_use]
44 pub const fn done(&self) -> u64 {
45 self.done
46 }
47
48 /// The allowance it passed.
49 #[must_use]
50 pub const fn allowance(&self) -> u64 {
51 self.allowance
52 }
53}
54
55/// One open of an input: what the input holds, against
56/// [`Limits::max_input_memory`], and what this open has done, against
57/// [`Limits::max_decode_work`] (module docs). Thread-safe: a lazily read
58/// bundle's entries charge one meter from any thread. Shared as
59/// `Arc<Meter>`; every [`Charge`] keeps it alive.
60pub struct Meter {
61 /// The input's memory, shared by every open of it ([`Self::reopen`]).
62 account: Arc<Account>,
63 /// Work done by this open ([`Limits::max_decode_work`]).
64 work: AtomicU64,
65 work_limit: u64,
66 work_refusal: AtomicU64,
67 /// Every byte this meter ever granted, never returned: what a lazy
68 /// computation is measured by ([`crate::once::get_or_publish_result`]).
69 granted: AtomicU64,
70}
71
72const _: () = crate::send_sync::<Meter>();
73
74impl fmt::Debug for Meter {
75 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
76 f.debug_struct("Meter")
77 .field("used", &self.used())
78 .field("limit", &self.limit())
79 .field("decoded", &self.decoded())
80 .field("what", &self.reservation())
81 .finish_non_exhaustive()
82 }
83}
84
85impl Meter {
86 /// Records one detected allocator refusal on this meter's budget and
87 /// returns its provenance. Call only at detection, never in conversions.
88 /// Arithmetic/count overflow must use the corresponding limit error.
89 #[must_use]
90 pub fn allocator_refused(&self, requested: u64) -> AllocError {
91 let error = AllocError {
92 requested,
93 what: self.reservation(),
94 };
95 self.account.budget.allocator_refused(error);
96 error
97 }
98
99 /// The heap an input's first meter takes itself, outside every charge,
100 /// in glibc chunks ([`heap_cost`]): the meter and the memory account, each
101 /// in its `Arc` (plan section 3.15's constant per input). Each
102 /// [`Self::reopen`] adds [`Self::REOPEN_HEAP`].
103 pub const OWN_HEAP: u64 = Self::REOPEN_HEAP + heap_cost(arc_bytes(size_of::<Account>()));
104
105 /// The heap one more open's meter takes, in glibc chunks.
106 pub const REOPEN_HEAP: u64 = heap_cost(arc_bytes(size_of::<Self>()));
107
108 /// A meter of `limit` bytes whose charges are booked with `budget` as
109 /// `what`, with no bound on decode work.
110 #[must_use]
111 pub fn new(limit: u64, budget: Arc<dyn MemoryBudget>, what: Reservation) -> Arc<Self> {
112 Self::with_decode_work(limit, u64::MAX, budget, what)
113 }
114
115 /// A meter of `limit` bytes that also counts decode work up to
116 /// `max_decode_work` bytes ([`Self::count_decode`]).
117 #[must_use]
118 pub fn with_decode_work(
119 limit: u64,
120 max_decode_work: u64,
121 budget: Arc<dyn MemoryBudget>,
122 what: Reservation,
123 ) -> Arc<Self> {
124 Arc::new(Self {
125 account: Arc::new(Account {
126 used: AtomicU64::new(0),
127 limit,
128 budget,
129 what,
130 }),
131 work: AtomicU64::new(0),
132 work_limit: max_decode_work,
133 work_refusal: AtomicU64::new(0),
134 granted: AtomicU64::new(0),
135 })
136 }
137
138 /// The meter of one input loaded with `limits` and `budget`: its memory
139 /// bound is [`Limits::max_input_memory`] and its decode-work bound
140 /// [`Limits::max_decode_work`].
141 #[must_use]
142 pub fn for_input(
143 limits: &Limits,
144 budget: Arc<dyn MemoryBudget>,
145 what: Reservation,
146 ) -> Arc<Self> {
147 Self::with_decode_work(
148 limits.max_input_memory,
149 limits.max_decode_work,
150 budget,
151 what,
152 )
153 }
154
155 /// A meter for opening the same input again: it charges the same memory
156 /// account, so everything every open holds counts against one
157 /// [`Limits::max_input_memory`], and its work starts from zero with the
158 /// same bound. The Environment opens an evicted dependency again on it
159 /// (plan section 3.13). The old meter keeps its own count, so a handle
160 /// of the old open that something still holds (a nested bundle a
161 /// resource read kept) goes on counting against the old allowance, which
162 /// nothing resets, and every open's work stays bounded.
163 #[must_use]
164 pub fn reopen(&self) -> Arc<Self> {
165 Arc::new(Self {
166 account: self.account.clone(),
167 work: AtomicU64::new(0),
168 work_limit: self.work_limit,
169 work_refusal: AtomicU64::new(0),
170 granted: AtomicU64::new(0),
171 })
172 }
173
174 /// Separate work allowance on the same memory account, for caller-side export.
175 #[must_use]
176 pub fn work_scope(&self, limit: u64) -> Arc<Self> {
177 Arc::new(Self {
178 account: self.account.clone(),
179 work: AtomicU64::new(0),
180 work_limit: limit,
181 work_refusal: AtomicU64::new(0),
182 granted: AtomicU64::new(0),
183 })
184 }
185
186 /// Work attempted by this scope, including its largest refused increment.
187 #[must_use]
188 pub fn attempted_work(&self) -> u64 {
189 self.decoded()
190 .max(self.work_refusal.load(Ordering::Acquire))
191 }
192
193 /// Whether `other` charges the same input's memory (one of them is a
194 /// [`Self::reopen`] of the other, or they are the same meter).
195 #[must_use]
196 pub fn same_input(&self, other: &Self) -> bool {
197 Arc::ptr_eq(&self.account, &other.account)
198 }
199
200 pub(crate) fn input_address(&self) -> usize {
201 Arc::as_ptr(&self.account).addr()
202 }
203
204 /// Counts `bytes` of this open's work, refused when it would pass the
205 /// bound ([`LimitKind::DecodeWork`]): one atomic check-and-add, so work
206 /// counted at once from several threads never passes the bound. Work is
207 /// never returned while the open lives, whatever its charges do. A
208 /// refused decode counts nothing, so a smaller one may still fit; once
209 /// work has passed the bound (`add_work`, unchecked), every later decode on
210 /// this meter is refused. A
211 /// [`crate::budget::DecodeBuf`] counts every write of a block's segment:
212 /// one that needs a growth after the meter and the budget granted its
213 /// memory and before it allocates, so a refused growth counts nothing,
214 /// and a growth the count refuses returns its charge and allocates
215 /// nothing.
216 pub fn count_decode(&self, bytes: u64) -> Result<(), ChargeError> {
217 self.count_work(bytes).map_err(ChargeError::Limit)
218 }
219
220 /// [`Self::count_decode`]'s check-and-add, its refusal the bound's
221 /// [`LimitKind::DecodeWork`] error itself: what a walk's read or write
222 /// counts its work with as it goes (`walk::OpenWork`).
223 pub(crate) fn count_work(&self, bytes: u64) -> Result<(), LimitError> {
224 let limit = self.work_limit;
225 self.work
226 .try_update(Ordering::AcqRel, Ordering::Acquire, |done| {
227 done.checked_add(bytes).filter(|t| *t <= limit)
228 })
229 .map(|_| ())
230 .map_err(|done| self.decode_refused(done, bytes))
231 }
232
233 /// Counts `bytes` of work done if the bound holds them, in one atomic
234 /// check-and-add as [`Self::count_decode`], and whether it did. A `false`
235 /// counts nothing and records no refusal: a direct read
236 /// ([`crate::ObjectRef::emit_typetree`]) then leaves the object to the
237 /// full reader, which meets the refusal itself.
238 #[must_use]
239 pub fn try_count_work(&self, bytes: u64) -> bool {
240 let limit = self.work_limit;
241 self.work
242 .try_update(Ordering::AcqRel, Ordering::Acquire, |done| {
243 done.checked_add(bytes).filter(|t| *t <= limit)
244 })
245 .is_ok()
246 }
247
248 /// Takes back `bytes` counted by [`Self::count_decode`] for a growth
249 /// the allocator then failed (nothing was allocated).
250 pub(crate) fn uncount_decode(&self, bytes: u64) {
251 let _ = self
252 .work
253 .try_update(Ordering::AcqRel, Ordering::Acquire, |done| {
254 Some(done.saturating_sub(bytes))
255 });
256 }
257
258 /// Counts `bytes` of work already done, unchecked: what a lazy
259 /// computation that ended unkept was granted
260 /// ([`crate::once::get_or_publish_result`]), or a bundle entry's parse
261 /// that ended in a kept error (`files::bundle`). The work is done whatever
262 /// the bound says; what follows is refused ([`Self::work_used_up`]).
263 pub(crate) fn add_work(&self, bytes: u64) {
264 let _ = self
265 .work
266 .try_update(Ordering::AcqRel, Ordering::Acquire, |done| {
267 Some(done.saturating_add(bytes))
268 });
269 }
270
271 /// Whether this open's work has passed its allowance: the work done and
272 /// the allowance when it has, `None` while it has not. A status, not an
273 /// error: the core turns it into its refusal of new work
274 /// ([`LimitKind::DecodeWork`]) where it refuses that work, through
275 /// [`LimitError::refused`], which counts under CR8's test feature (round
276 /// 4: this query returned the `LimitError` itself, uncounted, so a
277 /// caller's code could hand the core a refusal no counter saw). The
278 /// allowance is inclusive, as [`Self::count_decode`] admits work: work
279 /// that lands exactly on it is within it, and what follows is refused by
280 /// `count_decode` itself. Only work counted past the bound (`add_work`,
281 /// unchecked: a detection's refused chunk, what a refused computation was
282 /// granted) passes it, so the refusal's work is always past the bound
283 /// (`limit DecodeWork: <work> > <bound>`).
284 #[must_use]
285 pub fn work_used_up(&self) -> Option<WorkPast> {
286 let done = self.decoded();
287 (done > self.work_limit).then_some(WorkPast {
288 done,
289 allowance: self.work_limit,
290 })
291 }
292
293 /// The refusal the core makes of new work once the open's work has
294 /// passed its allowance ([`Self::work_used_up`]), built by
295 /// [`LimitError::refused`], which counts: what a read, a parse or a lazy
296 /// computation meets then.
297 #[inline]
298 pub(crate) fn work_refused(&self) -> Option<LimitError> {
299 let done = self.decoded();
300 if done > self.work_limit {
301 Some(LimitError::refused(
302 LimitKind::DecodeWork,
303 done,
304 self.work_limit,
305 ))
306 } else {
307 None
308 }
309 }
310
311 fn decode_refused(&self, done: u64, bytes: u64) -> LimitError {
312 let attempted = done.saturating_add(bytes);
313 self.work_refusal.fetch_max(attempted, Ordering::AcqRel);
314 LimitError::refused(LimitKind::DecodeWork, attempted, self.work_limit)
315 }
316
317 /// The work this open's allowance still holds.
318 #[must_use]
319 pub fn work_left(&self) -> u64 {
320 self.work_limit.saturating_sub(self.decoded())
321 }
322
323 /// Work counted so far by this open.
324 #[must_use]
325 pub fn decoded(&self) -> u64 {
326 self.work.load(Ordering::Acquire)
327 }
328
329 /// Every byte this meter has granted since it was made, returned or not.
330 #[must_use]
331 pub fn granted(&self) -> u64 {
332 self.granted.load(Ordering::Acquire)
333 }
334
335 /// A meter with no bound and no budget, for data that is not an input's:
336 /// a TPK's trees, a caller's `nodes=` rows, tests.
337 #[must_use]
338 pub fn unlimited() -> Arc<Self> {
339 Self::new(u64::MAX, Arc::new(Unbounded), Reservation::Input)
340 }
341
342 /// Bytes charged to the input and not yet returned, by every open of it.
343 #[must_use]
344 pub fn used(&self) -> u64 {
345 self.account.used.load(Ordering::Acquire)
346 }
347
348 /// The bound.
349 #[must_use]
350 pub fn limit(&self) -> u64 {
351 self.account.limit
352 }
353
354 /// How the budget books this meter's charges.
355 #[must_use]
356 pub fn reservation(&self) -> Reservation {
357 self.account.what
358 }
359
360 /// Charges `bytes`: against the bound, then with the budget. A refusal
361 /// charges nothing.
362 pub fn charge(self: &Arc<Self>, bytes: u64) -> Result<Charge, ChargeError> {
363 let permit = self.reserve(bytes)?;
364 Ok(Charge {
365 meter: self.clone(),
366 permit,
367 more: Vec::new(),
368 })
369 }
370
371 fn reserve(&self, bytes: u64) -> Result<Permit, ChargeError> {
372 let account = &self.account;
373 let limit = account.limit;
374 account
375 .used
376 .try_update(Ordering::AcqRel, Ordering::Acquire, |used| {
377 used.checked_add(bytes).filter(|t| *t <= limit)
378 })
379 .map_err(|used| {
380 LimitError::refused(LimitKind::InputMemory, used.saturating_add(bytes), limit)
381 })?;
382 let permit = account
383 .budget
384 .try_reserve(bytes, account.what)
385 .map_err(|e| {
386 self.refund(bytes);
387 crate::counters::budget(e.what);
388 ChargeError::Budget(counted(e))
389 })?;
390 let _ = self
391 .granted
392 .try_update(Ordering::AcqRel, Ordering::Acquire, |g| {
393 Some(g.saturating_add(bytes))
394 });
395 GrantScope::credit(self, bytes);
396 Ok(permit)
397 }
398
399 fn refund(&self, bytes: u64) {
400 // Saturating: a refund never takes the count below zero.
401 let _ = self
402 .account
403 .used
404 .try_update(Ordering::AcqRel, Ordering::Acquire, |used| {
405 Some(used.saturating_sub(bytes))
406 });
407 }
408}
409
410thread_local! {
411 /// How many refusals of [`Reservation::Dependency`] this thread met
412 /// ([`pool_refusals`]).
413 static POOL_REFUSALS: Cell<u64> = const { Cell::new(0) };
414}
415
416/// How many refusals of the dependency pool ([`Reservation::Dependency`])
417/// this thread has met: the budget's, and an allocation refused on a
418/// dependency's meter ([`refusal`]). The Environment's one retry of a pool
419/// refusal tells by it whether the refusal it holds is one a retry already
420/// met, or a later one (`env::registry::with_room`).
421pub(crate) fn pool_refusals() -> u64 {
422 POOL_REFUSALS.with(Cell::get)
423}
424
425/// `e`, counted in [`pool_refusals`] when it refuses the dependency pool.
426fn counted(e: BudgetExceeded) -> BudgetExceeded {
427 if e.what == Reservation::Dependency {
428 POOL_REFUSALS.with(|n| n.set(n.get().wrapping_add(1)));
429 }
430 e
431}
432
433/// The refusal of `requested` bytes for `what` that the core makes itself
434/// (an allocation the allocator refused after the budget granted it),
435/// counted as a budget's is ([`pool_refusals`]).
436pub(crate) fn refusal(requested: u64, what: Reservation) -> BudgetExceeded {
437 counted(BudgetExceeded { requested, what })
438}
439
440/// How many lazy computations one thread tracks at once ([`GrantScope`]):
441/// more than any nesting the core reaches (an entry parse inside a nested
442/// bundle's, a compile inside a read, bounded by
443/// [`Limits::max_container_depth`] and the walker's limits). A deeper scope
444/// falls back to its meter's total grants, which errs towards stopping
445/// early.
446const GRANT_SCOPES: usize = 64;
447
448/// The lazy computations running on this thread, innermost last: the
449/// address of the meter each measures and what that meter granted on this
450/// thread since the computation started. A fixed array, so tracking
451/// allocates nothing (a counting-allocator test sees every heap byte).
452struct GrantFrames {
453 frames: [(usize, u64); GRANT_SCOPES],
454 len: usize,
455}
456
457thread_local! {
458 static GRANTS: std::cell::RefCell<GrantFrames> = const {
459 std::cell::RefCell::new(GrantFrames {
460 frames: [(0, 0); GRANT_SCOPES],
461 len: 0,
462 })
463 };
464}
465
466/// What one lazy computation was granted by its meter on its own thread
467/// while it ran ([`crate::once::get_or_publish_result`]): grants that other
468/// threads made on the same meter meanwhile are theirs, not its (round 6:
469/// the meter's total since the computation started was counted, so other
470/// threads' successful work used up a failing computation's allowance).
471/// Scopes nest; a grant counts for every open scope of its meter on the
472/// thread, a nested computation's grants included.
473pub(crate) struct GrantScope {
474 /// The scope's frame index, or `None` past [`GRANT_SCOPES`] (then
475 /// `fallback` holds the meter's total grants at the start).
476 depth: Option<usize>,
477 fallback: u64,
478}
479
480impl GrantScope {
481 /// Opens a scope measuring `meter`'s grants on this thread.
482 pub(crate) fn enter(meter: &Meter) -> Self {
483 let addr = std::ptr::from_ref(meter).addr();
484 let depth = GRANTS
485 .try_with(|g| {
486 let mut g = g.borrow_mut();
487 let at = g.len;
488 let frame = g.frames.get_mut(at)?;
489 *frame = (addr, 0);
490 g.len = at + 1;
491 Some(at)
492 })
493 .ok()
494 .flatten();
495 Self {
496 depth,
497 fallback: meter.granted(),
498 }
499 }
500
501 /// Closes the scope: what `meter` (the one it was opened on) granted on
502 /// this thread while it was open.
503 pub(crate) fn finish(self, meter: &Meter) -> u64 {
504 match self.depth {
505 Some(at) => GRANTS
506 .try_with(|g| g.borrow().frames.get(at).map_or(0, |f| f.1))
507 .unwrap_or(0),
508 None => meter.granted().saturating_sub(self.fallback),
509 }
510 // `self` drops here and pops its frame.
511 }
512
513 /// Adds `bytes` granted by `meter` to every open scope of it on this
514 /// thread.
515 fn credit(meter: &Meter, bytes: u64) {
516 let addr = std::ptr::from_ref(meter).addr();
517 let _ = GRANTS.try_with(|g| {
518 let mut g = g.borrow_mut();
519 let len = g.len;
520 for frame in g.frames.iter_mut().take(len) {
521 if frame.0 == addr {
522 frame.1 = frame.1.saturating_add(bytes);
523 }
524 }
525 });
526 }
527}
528
529impl Drop for GrantScope {
530 fn drop(&mut self) {
531 if let Some(at) = self.depth {
532 // Scopes close in reverse order of opening (a stack frame each),
533 // so this is the innermost one.
534 let _ = GRANTS.try_with(|g| g.borrow_mut().len = at);
535 }
536 }
537}
538
539/// Bytes charged to a [`Meter`] (and booked with its budget), returned when
540/// the charge drops. It rides inside whatever it paid for.
541///
542/// **Bookkeeping.** A charge holds one [`Permit`] for its own meter, and
543/// every charge it absorbs from that meter merges into it (bytes added,
544/// permits merged by home), so a value built from any number of charged
545/// tables keeps one record, however its budget books it. A charge absorbed
546/// from *another* meter is kept as one record per distinct meter. Neither
547/// grows with the input: one meter and one budget home (every budget of the
548/// core: [`Unbounded`], [`crate::budget::Counting`]) allocate no record at
549/// all (`tests/memory_model.rs` checks this under `Counting`).
550#[must_use = "a charge returns its bytes when dropped"]
551pub struct Charge {
552 meter: Arc<Meter>,
553 // The permit holds this meter's byte count as well as its homes. Keeping
554 // one count leaves room for the inline phase home without growing Charge.
555 permit: Permit,
556 /// Absorbed charges of other meters, one per meter.
557 more: Vec<Charge>,
558}
559
560const _: () = crate::send_sync::<Charge>();
561
562impl fmt::Debug for Charge {
563 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
564 f.debug_struct("Charge")
565 .field("bytes", &self.bytes())
566 .field("more", &self.more.len())
567 .finish_non_exhaustive()
568 }
569}
570
571impl Charge {
572 /// A charge of nothing on `meter`, to grow.
573 pub fn zero(meter: &Arc<Meter>) -> Self {
574 Self {
575 meter: meter.clone(),
576 permit: Permit::detached(0),
577 more: Vec::new(),
578 }
579 }
580
581 /// The bytes held, absorbed charges included.
582 #[must_use]
583 pub fn bytes(&self) -> u64 {
584 self.more
585 .iter()
586 .fold(self.permit.bytes(), |n, c| n.saturating_add(c.bytes()))
587 }
588
589 /// The meter this charge is on.
590 #[must_use]
591 pub fn meter(&self) -> &Arc<Meter> {
592 &self.meter
593 }
594
595 /// Charges `bytes` more to the same meter. A refusal changes nothing.
596 pub fn grow(&mut self, bytes: u64) -> Result<(), ChargeError> {
597 let permit = self.meter.reserve(bytes)?;
598 self.permit.absorb(permit);
599 Ok(())
600 }
601
602 /// Returns up to `bytes` of this meter's part now (what a buffer no
603 /// longer holds).
604 pub fn release(&mut self, bytes: u64) {
605 let held = self.permit.bytes();
606 let n = bytes.min(held);
607 self.meter.refund(n);
608 self.permit.shrink_to(held - n);
609 }
610
611 /// Takes `other` in: its bytes are returned when this charge drops. A
612 /// charge of this meter merges into this one; a charge of another meter
613 /// merges into the record this charge keeps for that meter (type docs).
614 pub fn absorb(&mut self, mut other: Charge) {
615 for c in std::mem::take(&mut other.more) {
616 self.absorb(c);
617 }
618 if Arc::ptr_eq(&self.meter, &other.meter) {
619 self.permit
620 .absorb(std::mem::replace(&mut other.permit, Permit::detached(0)));
621 } else if other.permit.bytes() > 0 {
622 match self
623 .more
624 .iter_mut()
625 .find(|c| Arc::ptr_eq(&c.meter, &other.meter))
626 {
627 Some(kept) => kept.absorb(other),
628 None => self.more.push(other),
629 }
630 }
631 }
632
633 /// How many records this charge keeps besides its own: one per other
634 /// meter it absorbed, plus its permit's ([`Permit::records`]).
635 #[must_use]
636 pub fn records(&self) -> usize {
637 self.more
638 .iter()
639 .fold(self.permit.records(), |n, c| n + 1 + c.records())
640 }
641}
642
643impl Drop for Charge {
644 fn drop(&mut self) {
645 // The permit drops after this, returning the budget's side.
646 self.meter.refund(self.permit.bytes());
647 }
648}