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}