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;