Skip to main content

unityrs_core/limits/
vec.rs

1//! [`MeteredVec`], a `Vec` charged before it grows, and the growth every
2//! charged buffer shares: geometric, charged first, retried at the exact
3//! size ([`grow_charged`], [`grow_counted`]).
4
5use std::fmt;
6use std::mem::size_of;
7use std::sync::Arc;
8
9use super::{Charge, ChargeError, Meter, heap_cost};
10use crate::budget::BudgetExceeded;
11use crate::error::LimitKind;
12
13/// `vec.try_reserve_exact(additional)`, after `meter` granted the `charged`
14/// bytes it costs: an allocation the allocator refuses is a refusal of
15/// those bytes for `meter`'s reservation, counted as a budget's refusal is
16/// ([`super::refusal`]). Every allocation the core charges before it makes
17/// it reports a failure this way, and makes it here (or, for
18/// [`shrink_charged`]'s move, as here): under the test feature this thread
19/// is marked while `try_reserve_exact` runs, and the refusal is counted
20/// (`crate::counters`; `docs/plans/batch.md` section 6, CR8), so a test's
21/// allocator can refuse this allocation alone.
22pub(crate) fn reserve_exact<T>(
23    vec: &mut Vec<T>,
24    additional: usize,
25    charged: u64,
26    meter: &Meter,
27) -> Result<(), BudgetExceeded> {
28    let got = {
29        let _mark = crate::counters::Fallible::enter();
30        vec.try_reserve_exact(additional)
31    };
32    got.map_err(|_| {
33        crate::counters::allocator(meter.reservation());
34        super::refusal(charged, meter.reservation())
35    })
36}
37
38/// Gives back `vec`'s spare room, `charge` (which holds [`heap_cost`] of
39/// its capacity, and may hold more) following it to [`heap_cost`] of its
40/// length. Where glibc shrinks the block where it is (a heap chunk split in
41/// place by `realloc`, a mapped one cut by `mremap`), no second block ever
42/// exists, so nothing more is charged and the difference is returned after.
43/// Where [`super::shrink_moves`] says the bytes move to a new allocation of
44/// exactly their length (a block that may be mapped, given back below
45/// 128 KiB), both blocks exist while they move, so the smaller one is
46/// charged first, and a refusal, the meter's or the allocator's, leaves
47/// `vec` and `charge` as they were (perf stage 2: the smaller block was
48/// charged beside the old one either way, so a decoded run of 69.4 MB cut
49/// from room of 128 MiB was charged both at once).
50pub(crate) fn shrink_charged<T>(vec: &mut Vec<T>, charge: &mut Charge) -> Result<(), ChargeError> {
51    let (len, cap) = (bytes_of::<T>(vec.len()), bytes_of::<T>(vec.capacity()));
52    if len >= cap {
53        return Ok(());
54    }
55    let (old, exact) = (heap_cost(cap), heap_cost(len));
56    if super::shrink_moves(len, cap) {
57        let smaller = charge.meter().charge(exact)?;
58        let mut moved = Vec::new();
59        // Marked and counted as `reserve_exact` is; written out here, so a
60        // build without the test feature compiles this to what it was.
61        let got = {
62            let _mark = crate::counters::Fallible::enter();
63            moved.try_reserve_exact(vec.len())
64        };
65        if got.is_err() {
66            // `smaller` drops here: nothing stays charged for it.
67            let what = charge.meter().reservation();
68            crate::counters::allocator(what);
69            return Err(ChargeError::Budget(super::refusal(exact, what)));
70        }
71        moved.append(vec);
72        *vec = moved;
73        charge.release(old);
74        charge.absorb(smaller);
75    } else {
76        vec.shrink_to_fit();
77        charge.release(old - exact);
78    }
79    Ok(())
80}
81
82fn bytes_of<T>(n: usize) -> u64 {
83    u64::try_from(n)
84        .unwrap_or(u64::MAX)
85        .saturating_mul(u64::try_from(size_of::<T>()).unwrap_or(u64::MAX))
86}
87
88/// Grows `vec`'s capacity to at least `need`, geometrically up to `max`
89/// (never below `need`), charging the new allocation to `charge`'s meter
90/// first. While the allocator moves the buffer both blocks exist, so both are
91/// charged until it is done; then the old block's charge is returned. That
92/// is a bound: exact where glibc copies the bytes to a new block, and an
93/// over-count of the old block, for as long as the growth runs, wherever
94/// glibc grows the block without a second one (plan section 3.15): a mapped
95/// block, which it grows with `mremap`, its pages kept (every block of
96/// 32 MiB or more, its largest `mmap` threshold, and a block of 128 KiB or
97/// more while the threshold, which rises as mapped blocks are freed, is
98/// still below it), and a heap chunk it extends in place into free space. A
99/// refused doubling is asked for again with half the room past `need`, and
100/// so on down to exactly `need` before it fails, so a meter that fits the
101/// data is never refused by the growth policy, and a vector that meets its
102/// bound grows a few dozen more times at most, each time by at least half of
103/// what could still be granted ([`grow_counted`]).
104pub(crate) fn grow_charged<T>(
105    vec: &mut Vec<T>,
106    charge: &mut Charge,
107    need: usize,
108    max: usize,
109) -> Result<(), ChargeError> {
110    grow_counted(vec, charge, need, max, 0)
111}
112
113/// [`grow_charged`], counting `work` bytes of the meter's work
114/// ([`Meter::count_decode`]) whether or not `vec` grows: with no growth,
115/// at once; with one, once the growth's memory is granted and before it is
116/// allocated, so a growth the meter or the budget refuses counts nothing,
117/// and one the work bound refuses returns its charge and allocates nothing.
118/// The check and the count are one atomic step, so writes on several
119/// threads never pass the bound together.
120///
121/// The growth's ladder is `Text::reserve`'s (`unityrs-dump`, fix pass 15).
122/// Fix pass 17: a refused doubling was asked for exactly `need`, so a vector
123/// whose capacity lay between a third and a half of what was free grew by
124/// one push at a time, each push past its room a refused request (a failed
125/// `mmap` where the allocator is what refuses; review round 16, through the
126/// walk's lists and the writer's [`crate::budget::DecodeBuf`]).
127pub(crate) fn grow_counted<T>(
128    vec: &mut Vec<T>,
129    charge: &mut Charge,
130    need: usize,
131    max: usize,
132    work: u64,
133) -> Result<(), ChargeError> {
134    let _growth = crate::counters::Growing::enter();
135    let have = vec.capacity();
136    if need <= have {
137        // Round 6: the work of a write into room already there went
138        // uncounted (a pre-sized or reused buffer decoded without bound).
139        if work > 0 {
140            charge.meter().count_decode(work)?;
141        }
142        return Ok(());
143    }
144    let mut target = have.saturating_mul(2).min(max).max(need);
145    loop {
146        match grow_exact(vec, charge, target, work) {
147            Ok(()) => return Ok(()),
148            // The work bound refuses the exact size as well.
149            Err(ChargeError::Limit(l)) if l.kind() == LimitKind::DecodeWork => {
150                return Err(ChargeError::Limit(l));
151            }
152            Err(_) if target > need => target = need + (target - need) / 2,
153            Err(e) => return Err(e),
154        }
155    }
156}
157
158fn grow_exact<T>(
159    vec: &mut Vec<T>,
160    charge: &mut Charge,
161    cap: usize,
162    work: u64,
163) -> Result<(), ChargeError> {
164    let old = heap_cost(bytes_of::<T>(vec.capacity()));
165    let new = heap_cost(bytes_of::<T>(cap));
166    let mut extra = charge.meter().charge(new)?;
167    if work > 0 {
168        // `extra` drops on a refusal: the memory granted is returned.
169        charge.meter().count_decode(work)?;
170    }
171    let additional = cap.saturating_sub(vec.len());
172    if let Err(e) = reserve_exact(vec, additional, new, charge.meter()) {
173        // `extra` drops here: nothing stays charged or counted for a failed
174        // allocation.
175        if work > 0 {
176            charge.meter().uncount_decode(work);
177        }
178        return Err(ChargeError::Budget(e));
179    }
180    let got = heap_cost(bytes_of::<T>(vec.capacity()));
181    if got > new && extra.grow(got - new).is_err() {
182        vec.shrink_to(cap);
183    }
184    charge.release(old);
185    charge.absorb(extra);
186    Ok(())
187}
188
189/// A `Vec` whose every growth is charged to a [`Meter`] before it happens
190/// (its capacity, at [`heap_cost`]). Parsers build every table this way, so
191/// a table can never hold more than the meter granted, however many records
192/// the input declares; [`Self::into_parts`] hands the charge on to whatever
193/// keeps the table.
194pub struct MeteredVec<T> {
195    vec: Vec<T>,
196    charge: Charge,
197}
198
199const _: () = crate::send_sync::<MeteredVec<u8>>();
200
201impl<T: fmt::Debug> fmt::Debug for MeteredVec<T> {
202    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
203        f.debug_struct("MeteredVec")
204            .field("vec", &self.vec)
205            .field("charge", &self.charge)
206            .finish()
207    }
208}
209
210impl<T> MeteredVec<T> {
211    /// An empty vector charging `meter`.
212    pub fn new(meter: &Arc<Meter>) -> Self {
213        Self {
214            vec: Vec::new(),
215            charge: Charge::zero(meter),
216        }
217    }
218
219    /// An empty vector with room for exactly `n`, charged first.
220    pub fn with_capacity(meter: &Arc<Meter>, n: usize) -> Result<Self, ChargeError> {
221        let mut v = Self::new(meter);
222        v.reserve_exact(n)?;
223        Ok(v)
224    }
225
226    /// Wraps a vector the caller already allocated (a TPK's rows, a test's),
227    /// charging its capacity now. Parsers of input never use this: they grow
228    /// a `MeteredVec` from empty.
229    pub fn from_vec(vec: Vec<T>, meter: &Arc<Meter>) -> Result<Self, ChargeError> {
230        let charge = meter.charge(heap_cost(bytes_of::<T>(vec.capacity())))?;
231        Ok(Self { vec, charge })
232    }
233
234    /// Removes the last element, retaining the charged capacity for reuse.
235    pub fn pop(&mut self) -> Option<T> {
236        self.vec.pop()
237    }
238
239    /// Transfer a buffer and its existing charge without allocating or copying.
240    /// Used by charged encoders. Any capacity not covered by the supplied
241    /// charge is booked before accepting ownership, as with `from_vec`.
242    pub fn from_charged_parts(vec: Vec<T>, mut charge: Charge) -> Result<Self, ChargeError> {
243        let cost = heap_cost(bytes_of::<T>(vec.capacity()));
244        if cost > charge.bytes() {
245            charge.grow(cost - charge.bytes())?;
246        }
247        Ok(Self { vec, charge })
248    }
249
250    /// The elements.
251    #[must_use]
252    pub fn as_slice(&self) -> &[T] {
253        &self.vec
254    }
255
256    /// The elements, mutably (the length cannot grow through this).
257    pub fn as_mut_slice(&mut self) -> &mut [T] {
258        &mut self.vec
259    }
260
261    /// Number of elements.
262    #[must_use]
263    pub fn len(&self) -> usize {
264        self.vec.len()
265    }
266
267    /// Whether it is empty.
268    #[must_use]
269    pub fn is_empty(&self) -> bool {
270        self.vec.is_empty()
271    }
272
273    /// The allocation, in elements.
274    #[must_use]
275    pub fn capacity(&self) -> usize {
276        self.vec.capacity()
277    }
278
279    /// The charge for the allocation.
280    #[must_use]
281    pub fn charge(&self) -> &Charge {
282        &self.charge
283    }
284
285    /// Room for `additional` more, growing geometrically; charged first.
286    pub fn reserve(&mut self, additional: usize) -> Result<(), ChargeError> {
287        let need = self.vec.len().saturating_add(additional);
288        grow_charged(&mut self.vec, &mut self.charge, need, usize::MAX)
289    }
290
291    /// Room for `additional` more, growing geometrically but never past
292    /// `most` elements in all (unless `additional` needs more); charged
293    /// first.
294    pub(crate) fn reserve_within(
295        &mut self,
296        additional: usize,
297        most: usize,
298    ) -> Result<(), ChargeError> {
299        let need = self.vec.len().saturating_add(additional);
300        grow_charged(&mut self.vec, &mut self.charge, need, most.max(need))
301    }
302
303    /// Room for exactly `additional` more; charged first.
304    pub fn reserve_exact(&mut self, additional: usize) -> Result<(), ChargeError> {
305        let need = self.vec.len().saturating_add(additional);
306        grow_charged(&mut self.vec, &mut self.charge, need, need)
307    }
308
309    /// Appends `value`, charging any growth first.
310    pub fn push(&mut self, value: T) -> Result<(), ChargeError> {
311        self.reserve(1)?;
312        self.vec.push(value);
313        Ok(())
314    }
315
316    /// Appends `value` with `charge`, the charge for the heap it owns, which
317    /// this vector keeps from then on (a built value going into its parent,
318    /// [`crate::value::Built`]). A refused growth drops both together.
319    pub(crate) fn push_charged(&mut self, value: T, charge: Charge) -> Result<(), ChargeError> {
320        self.reserve(1)?;
321        self.vec.push(value);
322        self.charge.absorb(charge);
323        Ok(())
324    }
325
326    /// Keeps `charge` with this vector's own: it returns when they do.
327    pub(crate) fn keep_charge(&mut self, charge: Charge) {
328        self.charge.absorb(charge);
329    }
330
331    /// Cuts to `len` elements; the allocation and its charge stay.
332    pub fn truncate(&mut self, len: usize) {
333        self.vec.truncate(len);
334    }
335
336    /// The vector and its charge, which must live as long as the vector's
337    /// allocation does.
338    pub fn into_parts(self) -> (Vec<T>, Charge) {
339        (self.vec, self.charge)
340    }
341
342    /// Gives back any spare capacity, the charge following it: shrunk in
343    /// place, its charge cut after (no second block exists, so nothing more
344    /// is charged); or, for a block that may be mapped given back below
345    /// 128 KiB ([`super::shrink_moves`]; review round 13), moved into an
346    /// exact allocation charged before it is made (both blocks exist while
347    /// it moves), so a refusal leaves the vector as it was and nothing
348    /// allocated beyond what was charged.
349    pub fn shrink_to_fit(&mut self) -> Result<(), ChargeError> {
350        shrink_charged(&mut self.vec, &mut self.charge)
351    }
352
353    /// The elements as a boxed slice, and its charge, with no spare
354    /// capacity ([`Self::shrink_to_fit`]).
355    pub fn into_boxed_slice(mut self) -> Result<(Box<[T]>, Charge), ChargeError> {
356        self.shrink_to_fit()?;
357        Ok((self.vec.into_boxed_slice(), self.charge))
358    }
359}
360
361impl<T: Clone> MeteredVec<T> {
362    /// Appends a copy of `items`, charging any growth first.
363    pub fn extend_from_slice(&mut self, items: &[T]) -> Result<(), ChargeError> {
364        self.reserve(items.len())?;
365        self.vec.extend_from_slice(items);
366        Ok(())
367    }
368}