Skip to main content

unityrs_core/budget/
mod.rs

1//! Memory budgets: the mechanism in the core, the policy in the batch engine.
2//!
3//! A budget is shared by many inputs (a batch's admission pool, its
4//! dependency pool). The core never asks it directly: every charge an
5//! input's [`crate::limits::Meter`] grants is also booked here, as a
6//! [`Permit`] that rides inside the charge, so the budget sees everything
7//! every input holds, and gets it back when the last owner drops it. The
8//! request never blocks: blocking inside a rayon pool can deadlock, so a
9//! batch engine does any waiting of its own *before* it hands work to the
10//! pool (plan section 4.1 lists what the core guarantees it).
11//!
12//! A decoder writes through a [`DecodeBuf`], which charges the input's meter
13//! before every growth, so no decoded byte exists unpaid, a refused growth
14//! allocates nothing, and a dropped buffer (a failed decode) returns its
15//! charge.
16//!
17//! Owner: the scaffold (implemented); package C maintains it.
18
19use std::fmt;
20use std::sync::Arc;
21use std::sync::atomic::{AtomicU64, Ordering};
22
23use bytes::Bytes;
24
25use crate::error::{LimitError, LimitKind};
26use crate::limits::{
27    Charge, ChargeError, Meter, grow_charged, grow_counted, heap_cost, shrink_charged,
28};
29
30/// Which kind of load a charge belongs to, so a refusal says which pool
31/// refused (plan section 4.1).
32#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
33pub enum Reservation {
34    /// An input the caller loaded: everything its meter charges.
35    Input,
36    /// A file the environment loaded as a dependency (its LRU), and
37    /// everything that file's meter charges.
38    Dependency,
39    /// A typetree provider's own data (a TPK's trees), which no input owns:
40    /// a refusal of it is the allocator's, on whichever input's read asked.
41    Provider,
42}
43
44/// A host allocator refusal, kept by value without a heap-owned source.
45///
46/// `requested` is the failed request or a documented reservation estimate.
47/// The tag attributes the request; it does not claim that a meter owns it.
48/// Before a meter exists, fixed Environment storage is attributed to Input.
49#[derive(Clone, Copy, Debug, PartialEq, Eq, thiserror::Error)]
50#[error("allocator refused {requested} bytes for {what:?}")]
51pub struct AllocError {
52    /// Failed request size or reservation estimate, in bytes.
53    pub requested: u64,
54    /// The load or provider that requested the storage.
55    pub what: Reservation,
56}
57
58const _: () = crate::send_sync::<AllocError>();
59
60/// A refused reservation.
61#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
62#[error("memory budget refused {requested} bytes for {what:?}")]
63pub struct BudgetExceeded {
64    /// Bytes asked for.
65    pub requested: u64,
66    /// What they were for.
67    pub what: Reservation,
68}
69
70/// A source of permits.
71///
72/// **Contract** (plan section 3.16). The core calls a budget, and a permit's
73/// home, wherever it charges or returns memory, *including while it holds
74/// one of its own locks* (publishing a decoded run grows the bundle's run
75/// table under its mutex; a value replaced in a cell or a registry slot
76/// returns its charge as it drops). So an implementation must not block (it
77/// refuses instead: blocking inside a pool can deadlock it), must not call
78/// into the core, and must not take a lock that a thread may hold while it
79/// calls the core (Python's GIL among them): a budget that does any of these
80/// can deadlock against a core lock. [`Unbounded`] and [`Counting`] are
81/// atomic counters. The permits of one pool share one home (one
82/// `Arc<dyn PermitHome>`): the core merges permits by home, and keeps one
83/// record per distinct home a charge absorbs, so a budget that made a home
84/// per reservation would grow every owner's bookkeeping.
85pub trait MemoryBudget: Send + Sync + fmt::Debug {
86    /// Reserves `bytes`, or refuses at once. A successful permit holds exactly
87    /// `bytes`, including when detached from any home.
88    fn try_reserve(&self, bytes: u64, what: Reservation) -> Result<Permit, BudgetExceeded>;
89
90    /// Observes a detected allocator refusal exactly once at its source.
91    /// Wrapping or cloning the error must not notify again. Optional work may
92    /// absorb it, including settle after a successful registry commit; a batch
93    /// caller must audit observations before continuing or publishing.
94    ///
95    /// The same nonblocking, non-reentrant contract as budget operations applies.
96    /// Implementations must also allocate nothing while reporting a refusal.
97    fn allocator_refused(&self, _error: AllocError) {}
98}
99
100/// Where a permit returns its bytes. The same contract as [`MemoryBudget`]:
101/// called under core locks, so it must not block or call the core.
102pub trait PermitHome: Send + Sync {
103    /// Takes `bytes` back.
104    fn release(&self, bytes: u64);
105}
106
107/// Bytes reserved from a budget, returned when the permit drops.
108///
109/// A permit can take in another ([`Permit::absorb`]), so a buffer that grew
110/// past its first reservation carries every top-up in one owner, and can give
111/// back what its buffer no longer holds ([`Permit::shrink_to`]). Permits
112/// merge by home: an empty permit takes the home of the first one it
113/// absorbs, a permit of the same home adds its bytes, and one of another
114/// home merges into the record kept for that home, so a permit holds one
115/// record per distinct home whatever it absorbed ([`Self::records`]).
116/// Up to two distinct homes are stored inline, without heap allocation.
117#[must_use = "a permit returns its bytes when dropped"]
118pub struct Permit {
119    primary: PermitRecord,
120    // Two phase homes can meet in a retained charge. Keep the first additional
121    // home inline so that crossing that boundary never allocates bookkeeping.
122    more: PermitRecords,
123}
124
125enum PermitRecords {
126    Empty,
127    Inline(PermitRecord),
128    Heap(Vec<PermitRecord>),
129}
130
131impl PermitRecords {
132    fn as_slice(&self) -> &[PermitRecord] {
133        match self {
134            Self::Empty => &[],
135            Self::Inline(record) => std::slice::from_ref(record),
136            Self::Heap(records) => records,
137        }
138    }
139
140    fn as_mut_slice(&mut self) -> &mut [PermitRecord] {
141        match self {
142            Self::Empty => &mut [],
143            Self::Inline(record) => std::slice::from_mut(record),
144            Self::Heap(records) => records,
145        }
146    }
147}
148
149struct PermitRecord {
150    bytes: u64,
151    home: Option<Arc<dyn PermitHome>>,
152}
153
154impl PermitRecord {
155    fn release(&mut self, n: u64) {
156        let n = n.min(self.bytes);
157        if let Some(home) = &self.home {
158            home.release(n);
159        }
160        self.bytes -= n;
161    }
162}
163
164impl Drop for PermitRecord {
165    fn drop(&mut self) {
166        self.release(self.bytes);
167    }
168}
169
170fn same_home(a: Option<&Arc<dyn PermitHome>>, b: Option<&Arc<dyn PermitHome>>) -> bool {
171    match (a, b) {
172        (None, None) => true,
173        // Compare the data addresses only: two vtables for one type may differ.
174        (Some(a), Some(b)) => std::ptr::addr_eq(Arc::as_ptr(a), Arc::as_ptr(b)),
175        _ => false,
176    }
177}
178
179impl Permit {
180    /// A permit that belongs to no budget.
181    pub fn detached(bytes: u64) -> Self {
182        Self {
183            primary: PermitRecord { bytes, home: None },
184            more: PermitRecords::Empty,
185        }
186    }
187
188    /// A permit that returns its bytes to `home`.
189    pub fn new(bytes: u64, home: Arc<dyn PermitHome>) -> Self {
190        Self {
191            primary: PermitRecord {
192                bytes,
193                home: Some(home),
194            },
195            more: PermitRecords::Empty,
196        }
197    }
198
199    /// The bytes this permit holds, absorbed permits included.
200    #[must_use]
201    pub fn bytes(&self) -> u64 {
202        self.more
203            .as_slice()
204            .iter()
205            .fold(self.primary.bytes, |n, p| n.saturating_add(p.bytes))
206    }
207
208    /// Takes `other` in: its bytes are returned when this permit drops
209    /// (merged by home, type docs). The first additional home stays inline.
210    pub fn absorb(&mut self, other: Permit) {
211        match other.more {
212            PermitRecords::Empty => (),
213            PermitRecords::Inline(record) => self.absorb_record(record),
214            PermitRecords::Heap(records) => {
215                for record in records {
216                    self.absorb_record(record);
217                }
218            }
219        }
220        self.absorb_record(other.primary);
221    }
222
223    fn absorb_record(&mut self, mut other: PermitRecord) {
224        if other.bytes == 0 {
225            other.home = None;
226            return;
227        }
228        if let Some(kept) = std::iter::once(&mut self.primary)
229            .chain(self.more.as_mut_slice())
230            .find(|p| same_home(p.home.as_ref(), other.home.as_ref()))
231        {
232            kept.bytes = kept.bytes.saturating_add(other.bytes);
233            other.bytes = 0;
234            other.home = None;
235        } else if self.primary.bytes == 0 {
236            self.primary = other;
237        } else {
238            match &mut self.more {
239                PermitRecords::Empty => self.more = PermitRecords::Inline(other),
240                PermitRecords::Heap(records) => records.push(other),
241                PermitRecords::Inline(_) => {
242                    let previous = std::mem::replace(&mut self.more, PermitRecords::Empty);
243                    if let PermitRecords::Inline(record) = previous {
244                        self.more = PermitRecords::Heap(vec![record, other]);
245                    }
246                }
247            }
248        }
249    }
250
251    /// How many records this permit keeps besides its own: one per other
252    /// home it absorbed. The first is inline and requires no allocation.
253    #[must_use]
254    pub fn records(&self) -> usize {
255        self.more.as_slice().len()
256    }
257
258    /// Returns every byte above `keep` to its budget now.
259    pub fn shrink_to(&mut self, keep: u64) {
260        let mut excess = self.bytes().saturating_sub(keep);
261        match &mut self.more {
262            PermitRecords::Empty => (),
263            PermitRecords::Inline(record) => {
264                let n = excess.min(record.bytes);
265                record.release(n);
266                excess -= n;
267                if record.bytes == 0 {
268                    self.more = PermitRecords::Empty;
269                }
270            }
271            PermitRecords::Heap(records) => {
272                while excess > 0 {
273                    let Some(last) = records.last_mut() else {
274                        break;
275                    };
276                    let n = excess.min(last.bytes);
277                    last.release(n);
278                    excess -= n;
279                    if last.bytes == 0 {
280                        records.pop();
281                    }
282                }
283            }
284        }
285        self.primary.release(excess);
286    }
287}
288
289impl fmt::Debug for Permit {
290    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
291        f.debug_struct("Permit")
292            .field("bytes", &self.bytes())
293            .field("attached", &self.primary.home.is_some())
294            .field("more", &self.records())
295            .finish_non_exhaustive()
296    }
297}
298
299/// A budget that never refuses: UnityPy's behaviour, and the default.
300#[derive(Clone, Copy, Debug, Default)]
301pub struct Unbounded;
302
303impl MemoryBudget for Unbounded {
304    fn try_reserve(&self, bytes: u64, _what: Reservation) -> Result<Permit, BudgetExceeded> {
305        Ok(Permit::detached(bytes))
306    }
307}
308
309/// A non-blocking budget with a fixed limit, counting what is alive.
310#[derive(Debug)]
311pub struct Counting {
312    limit: u64,
313    used: Arc<CountingHome>,
314}
315
316#[derive(Debug, Default)]
317struct CountingHome {
318    used: AtomicU64,
319}
320
321impl PermitHome for CountingHome {
322    fn release(&self, bytes: u64) {
323        self.used.fetch_sub(bytes, Ordering::AcqRel);
324    }
325}
326
327impl Counting {
328    /// A budget of `limit` bytes.
329    #[must_use]
330    pub fn new(limit: u64) -> Self {
331        Self {
332            limit,
333            used: Arc::new(CountingHome::default()),
334        }
335    }
336
337    /// Bytes reserved and not yet returned.
338    #[must_use]
339    pub fn used(&self) -> u64 {
340        self.used.used.load(Ordering::Acquire)
341    }
342}
343
344impl MemoryBudget for Counting {
345    fn try_reserve(&self, bytes: u64, what: Reservation) -> Result<Permit, BudgetExceeded> {
346        let refused = BudgetExceeded {
347            requested: bytes,
348            what,
349        };
350        self.used
351            .used
352            .try_update(Ordering::AcqRel, Ordering::Acquire, |used| {
353                used.checked_add(bytes).filter(|n| *n <= self.limit)
354            })
355            .map_err(|_| refused)?;
356        Ok(Permit::new(bytes, self.used.clone()))
357    }
358}
359
360/// The owner of a decoded buffer inside its `Bytes`: the buffer and the
361/// charge that paid for it, returned when the last slice drops.
362struct Charged {
363    buf: Vec<u8>,
364    _charge: Charge,
365}
366
367impl AsRef<[u8]> for Charged {
368    fn as_ref(&self) -> &[u8] {
369        &self.buf
370    }
371}
372
373/// What wrapping a buffer in `Bytes` allocates besides the buffer: the
374/// shared owner record `Bytes::from_owner` boxes (the buffer, its charge and
375/// a reference count), with room to spare.
376pub const OWNER_COST: u64 = heap_cost(256);
377
378/// `buf` as `Bytes` that carry `charge`, which must already cover `buf`'s
379/// allocation: the owner record is charged first ([`OWNER_COST`]), and the
380/// whole charge returns when the last slice drops, whoever holds it.
381pub fn charged_bytes(buf: Vec<u8>, mut charge: Charge) -> Result<Bytes, ChargeError> {
382    charge.grow(OWNER_COST)?;
383    Ok(Bytes::from_owner(Charged {
384        buf,
385        _charge: charge,
386    }))
387}
388
389/// A decoder's output buffer that pays before it grows.
390///
391/// A codec writes a block's output here and nowhere else
392/// ([`crate::codec::BlockCodec::decode`]); the core's other byte buffers
393/// (a path read, the writer's output) use it too. Every growth first checks
394/// the current segment's cap, then charges the new allocation to the input's
395/// meter (which books it with the budget), and only then grows; a refused
396/// growth allocates nothing. Capacity grows geometrically, never past the
397/// current segment's end (its start and its cap: room no write may use is
398/// never allocated, review round 13), nor, while what is needed fits it,
399/// past the run's declared end: the block's start, the size
400/// [`Self::begin_block`] was given, and what the run's next blocks declare
401/// as far as its reader has read ahead (`set_ahead`, which the crate's
402/// bundle reader calls). Room a well-formed run never writes is never
403/// allocated, so a block decoded in windows ends at its declared size, and
404/// a run of blocks doubles, ending at its last block's end. A refused
405/// doubling is asked again with half the room past the size needed, down
406/// to exactly that size ([`crate::limits::MeteredVec`]'s growth). A block
407/// that writes past that declared end (an LZMA stream that ignores its
408/// size) grows geometrically from there, to the segment's end.
409///
410/// **Segments.** A run of several blocks is one buffer, but each block has
411/// its own cap ([`crate::limits::Limits::max_block_output`]): the caller
412/// starts each block with [`Self::begin_block`], and a block that writes past
413/// its own cap fails there, whatever the run's size. Every decode is charged
414/// (a first decode, a re-decode, a measuring decode): the meter counts what is
415/// held, not what was first seen. A block's segment (capped by
416/// [`LimitKind::BlockOutput`]) also counts every byte written into it
417/// ([`Self::extend_from_slice`], [`Self::grow_zeroed`]) as the decode work
418/// of its meter's open ([`crate::limits::Limits::max_decode_work`]), which
419/// is never returned, so a block decoded again and again (a failing block
420/// read for every entry, a span re-decoded for every range) stops there even
421/// though each attempt returns its memory. The count is of writes, not of
422/// growths: a buffer sized up front, a scratch buffer reused across decodes
423/// and output written in small pieces count every byte (round 6: growths
424/// alone were counted, so all three decoded without bound). Room made ahead
425/// ([`Self::new`]'s `initial`, [`Self::reserve`]) is memory, charged, and
426/// counts as work only when it is written. Work counted ahead for what a
427/// decode reads (`prepay`, the bundle reader's) is credit its writes use
428/// first.
429///
430/// **Drop.** A buffer dropped unfinished (a decode that failed) returns its
431/// charge with its allocation.
432pub struct DecodeBuf {
433    buf: Vec<u8>,
434    charge: Charge,
435    seg_start: usize,
436    seg_cap: u64,
437    seg_kind: LimitKind,
438    /// The segment's declared size ([`Self::begin_block`]'s `declared`;
439    /// the cap for a buffer's first segment): room grows past it, and past
440    /// `ahead`, only for a write that needs it.
441    seg_declared: u64,
442    /// What the run's blocks after this one declare ([`Self::set_ahead`]).
443    ahead: u64,
444    /// Bumped by every [`Self::begin_block`] and every [`Self::truncate`]
445    /// below the segment's start, so [`crate::codec::decode_block`] can see
446    /// that a codec left its own segment (round 6).
447    seg_epoch: u64,
448    /// Work counted ahead ([`Self::prepay`]) that no write has used yet.
449    prepaid: u64,
450    count_writes: bool,
451}
452
453impl fmt::Debug for DecodeBuf {
454    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
455        f.debug_struct("DecodeBuf")
456            .field("len", &self.buf.len())
457            .field("capacity", &self.buf.capacity())
458            .field("charged", &self.charge.bytes())
459            .field("seg_start", &self.seg_start)
460            .field("seg_cap", &self.seg_cap)
461            .finish_non_exhaustive()
462    }
463}
464
465impl DecodeBuf {
466    /// An empty buffer charging `meter`, with room for `initial` bytes (cut
467    /// to `cap`), charged before it is allocated. Its first segment may hold
468    /// `cap` bytes; passing that is a `cap_kind` limit error.
469    pub fn new(
470        meter: &Arc<Meter>,
471        initial: u64,
472        cap: u64,
473        cap_kind: LimitKind,
474    ) -> Result<Self, ChargeError> {
475        let mut out = Self {
476            buf: Vec::new(),
477            charge: Charge::zero(meter),
478            seg_start: 0,
479            seg_cap: cap,
480            seg_kind: cap_kind,
481            seg_declared: cap,
482            ahead: 0,
483            seg_epoch: 0,
484            prepaid: 0,
485            count_writes: cap_kind == LimitKind::BlockOutput,
486        };
487        let initial = usize::try_from(initial.min(cap)).unwrap_or(usize::MAX);
488        grow_charged(&mut out.buf, &mut out.charge, initial, initial)?;
489        Ok(out)
490    }
491
492    /// An inflation buffer whose writes also count as decode work.
493    pub(crate) fn inflated(meter: &Arc<Meter>, cap: u64) -> Result<Self, ChargeError> {
494        Self::counted(meter, cap, LimitKind::Inflate)
495    }
496
497    /// An empty buffer whose writes count as work only after growth succeeds.
498    pub(crate) fn counted(
499        meter: &Arc<Meter>,
500        cap: u64,
501        cap_kind: LimitKind,
502    ) -> Result<Self, ChargeError> {
503        let mut out = Self::new(meter, 0, cap, cap_kind)?;
504        out.count_writes = true;
505        Ok(out)
506    }
507
508    /// Starts a new segment at the current length (the next block of a run):
509    /// from here the buffer may grow by at most `cap` bytes, and its room
510    /// grows past `declared` bytes (the block's declared size, a growth
511    /// hint) only for a write that needs it (type docs).
512    pub fn begin_block(&mut self, cap: u64, cap_kind: LimitKind, declared: u64) {
513        self.seg_start = self.buf.len();
514        self.seg_cap = cap;
515        self.seg_kind = cap_kind;
516        self.count_writes = cap_kind == LimitKind::BlockOutput;
517        self.seg_declared = declared;
518        self.seg_epoch = self.seg_epoch.wrapping_add(1);
519    }
520
521    /// What the run's blocks after the next one declare, `bytes` in all, as
522    /// far as its reader reads ahead: room may grow that far past the next
523    /// block's declared end (type docs), so a run of many blocks doubles its
524    /// room rather than growing it to each block's end in turn (perf stage
525    /// 2's review: 64 MiB in 4,096 blocks reallocated 4,096 times). It holds
526    /// until it is set again; a buffer never given it reads no further than
527    /// each block's own end.
528    pub(crate) fn set_ahead(&mut self, bytes: u64) {
529        self.ahead = bytes;
530    }
531
532    /// Counts `n` bytes as its meter's open's work now, in one checked add
533    /// ([`crate::limits::Meter::count_decode`]), before what they pay for
534    /// runs, and keeps them as credit for the next `n` bytes written into a
535    /// block's segment, which then count nothing more. The bundle reader
536    /// prepays a block's stored bytes before a codec reads them, so a decode
537    /// counts the larger of what it reads and what it writes, and one that
538    /// reads its whole block and fails before it writes still counts its
539    /// read (review round 6: an LZ4 scan that failed counted nothing). A
540    /// refusal ([`LimitKind::DecodeWork`]) counts nothing and leaves no
541    /// credit.
542    pub(crate) fn prepay(&mut self, n: u64) -> Result<(), ChargeError> {
543        self.charge.meter().count_decode(n)?;
544        self.prepaid = self.prepaid.saturating_add(n);
545        Ok(())
546    }
547
548    /// Ends [`Self::prepay`]'s credit: what no write used, which stays
549    /// counted unless the caller gives it back.
550    pub(crate) fn end_prepaid(&mut self) -> u64 {
551        std::mem::take(&mut self.prepaid)
552    }
553
554    /// The meter this buffer charges: a codec charges what it holds beside
555    /// its output (an LZMA dictionary) to the same input.
556    #[must_use]
557    pub fn meter(&self) -> &Arc<Meter> {
558        self.charge.meter()
559    }
560
561    /// The cap of the current segment ([`Self::begin_block`]'s `cap`).
562    #[must_use]
563    pub fn segment_cap(&self) -> u64 {
564        self.seg_cap
565    }
566
567    /// Changes whenever a segment begins or the bytes are cut below the
568    /// current segment's start.
569    pub(crate) fn segment_epoch(&self) -> u64 {
570        self.seg_epoch
571    }
572
573    /// The bytes written.
574    #[must_use]
575    pub fn len(&self) -> usize {
576        self.buf.len()
577    }
578
579    /// The bytes written in the current segment (since the last
580    /// [`Self::begin_block`]).
581    #[must_use]
582    pub fn segment_len(&self) -> usize {
583        self.buf.len().saturating_sub(self.seg_start)
584    }
585
586    /// Whether nothing was written.
587    #[must_use]
588    pub fn is_empty(&self) -> bool {
589        self.buf.is_empty()
590    }
591
592    /// The allocation.
593    #[must_use]
594    pub fn capacity(&self) -> usize {
595        self.buf.capacity()
596    }
597
598    /// The bytes charged for this buffer: [`heap_cost`] of its capacity.
599    #[must_use]
600    pub fn charged(&self) -> u64 {
601        self.charge.bytes()
602    }
603
604    /// The bytes written.
605    #[must_use]
606    pub fn as_slice(&self) -> &[u8] {
607        &self.buf
608    }
609
610    fn seg_end(&self) -> usize {
611        let cap = usize::try_from(self.seg_cap).unwrap_or(usize::MAX);
612        self.seg_start.saturating_add(cap)
613    }
614
615    /// Makes room for `additional` more bytes: the segment's cap is checked
616    /// and the meter charged before the buffer grows. The capacity doubles,
617    /// up to the segment's end (and to the run's declared end while what is
618    /// needed fits it), while the meter can pay for the old and the new
619    /// block at once, and grows to exactly what is needed when it cannot.
620    /// Room is memory, not work: what is written into it counts
621    /// ([`Self::extend_from_slice`]).
622    pub fn reserve(&mut self, additional: usize) -> Result<(), ChargeError> {
623        self.make_room(additional, 0)
624    }
625
626    /// Room for `n` bytes about to be written. In a block's segment (one
627    /// capped by [`LimitKind::BlockOutput`]) the `n` bytes are also the
628    /// open's decode work, counted in one atomic check-and-add
629    /// ([`crate::limits::Meter::count_decode`]) whether or not the buffer
630    /// grows: when it grows, once the meter and the budget granted the
631    /// growth and before it allocates. Decodes on several threads never pass
632    /// the bound together, a write the bound refuses
633    /// ([`LimitKind::DecodeWork`]) writes and allocates nothing, and a growth
634    /// the meter or the budget refuses counts no work, so a refusal leaves
635    /// the input as it was and the same read succeeds once there is room.
636    /// Work already counted ahead ([`Self::prepay`]) pays for the bytes
637    /// first, and is used only by a write that is made.
638    fn room_to_write(&mut self, n: usize) -> Result<(), ChargeError> {
639        let work = if self.count_writes {
640            u64::try_from(n).unwrap_or(u64::MAX)
641        } else {
642            0
643        };
644        let credit = work.min(self.prepaid);
645        self.make_room(n, work - credit)?;
646        self.prepaid -= credit;
647        Ok(())
648    }
649
650    fn make_room(&mut self, additional: usize, work: u64) -> Result<(), ChargeError> {
651        let need = self.buf.len().saturating_add(additional);
652        let end = self.seg_end();
653        if need > end {
654            return Err(ChargeError::Limit(LimitError::refused(
655                self.seg_kind,
656                u64::try_from(need - self.seg_start).unwrap_or(u64::MAX),
657                self.seg_cap,
658            )));
659        }
660        // Review round 13: the doubling was not capped, so a block whose
661        // output ended just past a power of two of its first window held
662        // room up to twice its cap (a TPK's LZMA payload of 16 MiB, 32 MiB),
663        // which a later charge (an LZMA retry's dictionary) then had to fit
664        // beside. Perf stage 2 (plan section 3.15): it still passed the
665        // block's declared size, so an LZMA block of 69.4 MB decoded in
666        // 1 MiB windows held 128 MiB of room, charged, and a run of LZ4
667        // blocks doubled past its last block.
668        let declared = self.seg_declared.saturating_add(self.ahead);
669        let declared = usize::try_from(declared).unwrap_or(usize::MAX);
670        let hint = self.seg_start.saturating_add(declared).min(end);
671        let most = if need <= hint { hint } else { end };
672        grow_counted(&mut self.buf, &mut self.charge, need, most, work)
673    }
674
675    /// Appends `data`.
676    pub fn extend_from_slice(&mut self, data: &[u8]) -> Result<(), ChargeError> {
677        self.room_to_write(data.len())?;
678        self.buf.extend_from_slice(data);
679        Ok(())
680    }
681
682    /// Patch existing bytes, extending with a zero-filled gap when needed.
683    /// Every fallible check precedes the first byte mutation.
684    pub(crate) fn write_at(&mut self, offset: usize, data: &[u8]) -> Result<(), ChargeError> {
685        if data.is_empty() {
686            return Ok(());
687        }
688        let refused =
689            || ChargeError::Limit(LimitError::refused(self.seg_kind, u64::MAX, self.seg_cap));
690        let end = offset.checked_add(data.len()).ok_or_else(refused)?;
691        let old = self.buf.len();
692        let overlap = old.saturating_sub(offset).min(data.len());
693        let (prefix, suffix) = data.split_at_checked(overlap).ok_or_else(refused)?;
694        let gap = offset.saturating_sub(old);
695        let work = if self.count_writes {
696            u64::try_from(gap.saturating_add(data.len())).unwrap_or(u64::MAX)
697        } else {
698            0
699        };
700        let credit = work.min(self.prepaid);
701        self.make_room(end.saturating_sub(old), work - credit)?;
702        self.prepaid -= credit;
703        if gap > 0 {
704            self.buf.resize(offset, 0);
705        }
706        if let Some(target) = self.buf.get_mut(offset..offset.saturating_add(overlap)) {
707            target.copy_from_slice(prefix);
708        }
709        self.buf.extend_from_slice(suffix);
710        Ok(())
711    }
712
713    /// Appends `n` zero bytes and returns them for a decoder to fill; cut the
714    /// unused tail with [`Self::truncate`]. All `n` count as written.
715    pub fn grow_zeroed(&mut self, n: usize) -> Result<&mut [u8], ChargeError> {
716        self.room_to_write(n)?;
717        let start = self.buf.len();
718        self.buf.resize(start + n, 0);
719        Ok(self.buf.get_mut(start..).unwrap_or_default())
720    }
721
722    /// Zero a cursor-selected span, charging its growth and work atomically.
723    pub(crate) fn write_zeroes_at(
724        &mut self,
725        offset: usize,
726        count: usize,
727    ) -> Result<(), ChargeError> {
728        if count == 0 {
729            return Ok(());
730        }
731        let end = offset.checked_add(count).ok_or_else(|| {
732            ChargeError::Limit(LimitError::refused(self.seg_kind, u64::MAX, self.seg_cap))
733        })?;
734        let old = self.buf.len();
735        let work = if self.count_writes {
736            u64::try_from(offset.saturating_sub(old).saturating_add(count)).unwrap_or(u64::MAX)
737        } else {
738            0
739        };
740        let credit = work.min(self.prepaid);
741        self.make_room(end.saturating_sub(old), work - credit)?;
742        self.prepaid -= credit;
743        self.buf.resize(old.max(end), 0);
744        if let Some(target) = self.buf.get_mut(offset..end) {
745            target.fill(0);
746        }
747        Ok(())
748    }
749
750    /// Cuts the written bytes to `len`. The allocation and its charge stay
751    /// until [`Self::into_bytes`] or drop.
752    pub fn truncate(&mut self, len: usize) {
753        self.buf.truncate(len);
754        if self.buf.len() < self.seg_start {
755            self.seg_start = self.buf.len();
756            self.seg_epoch = self.seg_epoch.wrapping_add(1);
757        }
758    }
759
760    /// The output as `Bytes` that carry their charge ([`charged_bytes`]).
761    /// A buffer with spare capacity is shrunk to its length, its charge cut
762    /// to the smaller block's ([`crate::limits::MeteredVec::shrink_to_fit`]'s
763    /// rule): in place, charging nothing more (perf stage 2: the smaller
764    /// block was charged beside the old one, which an in-place shrink never
765    /// holds); or, for a block that may be mapped given back below 128 KiB
766    /// ([`crate::limits::shrink_moves`]; review round 13: 10 bytes cut from
767    /// room of 1 MiB, as an LZMA block's first window leaves a short block,
768    /// held a page against a charge of 32 bytes), moved to a new block when
769    /// the meter can also pay for it while the bytes move, and kept (charged
770    /// as it is) when the meter or the allocator refuses that block.
771    pub fn into_bytes(mut self) -> Result<Bytes, ChargeError> {
772        // A refused move keeps the buffer as it is.
773        let _ = shrink_charged(&mut self.buf, &mut self.charge);
774        charged_bytes(self.buf, self.charge)
775    }
776}
777
778#[cfg(test)]
779mod tests;