Skip to main content

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}