Skip to main content

unityrs_core/limits/
mod.rs

1// Ported from UnityPy 1.25.2 (MIT): UnityPy/helpers/CompressionHelper.py. See THIRD_PARTY_LICENSES.
2//! Hard bounds on what untrusted input can make the library allocate or do,
3//! and the one meter that enforces the memory bound.
4//!
5//! UnityPy has none of these: where it would exhaust memory or the C stack,
6//! unityrs stops with [`crate::Error::Limit`] (or the walker's `other` kind) and
7//! `PARITY.md` lists the case as a safety divergence (plan section 3.15).
8//!
9//! **One meter per input.** Everything the core allocates in proportion to a
10//! size or count the input chose is charged to the input's [`Meter`] *before*
11//! it is allocated: the input's own bytes when the core reads a path, every
12//! block decode (a first decode, a lazy re-decode, a measuring decode, a
13//! decode after eviction), every metadata table and typetree row of every
14//! entry parse (an entry parsed twice, or two directory rows over the same
15//! bytes, pay twice), every compiled tree, every parsed value and every
16//! writer output. A charge the meter refuses allocates nothing. The charge is
17//! a [`Charge`] that lives inside what it paid for, so the bytes return when
18//! that drops: a [`crate::Parsed`] carries the charge for its values, a
19//! decoded buffer's [`bytes::Bytes`] the charge for the buffer. So what one
20//! input holds at any moment, retained values included, is at most
21//! [`Limits::max_input_memory`] in the unit the meter charges ([`heap_cost`],
22//! a request in glibc's chunks), plus the constant overhead plan section 3.15
23//! states; in glibc's own chunks a live allocation below 128 KiB may hold up
24//! to [`CHUNK_SLACK`] bytes more than its charge, at most half again of it
25//! ([`heap_cost`]'s docs), so the heap such an input holds is at most half
26//! again of that limit, plus the constant. A top-level load makes the meter;
27//! every file inside it (a bundle's entries, nested bundles) charges the same
28//! one.
29//!
30//! **A meter is one open of its input.** Its memory is the input's: an
31//! account every open of the input shares, so the bound holds across opens.
32//! Its *work* ([`Limits::max_decode_work`]) is the open's own: the
33//! Environment opens an evicted dependency again on [`Meter::reopen`], a new
34//! meter on the same account with a fresh allowance, while a handle of the
35//! old open that someone still holds (a nested bundle a resource read kept)
36//! goes on counting against the old meter's, which nothing resets.
37//!
38//! **One accounting path.** The meter books every charge it grants with the
39//! load's [`MemoryBudget`] as well ([`crate::FileContext::budget`]), so a
40//! batch engine's budget sees exactly what every input holds, and a refusal
41//! says which side refused: [`ChargeError::Limit`] (this input's bound) or
42//! [`ChargeError::Budget`] (the shared budget, tagged with the meter's
43//! [`Reservation`]).
44//!
45//! The other bounds are on work and nesting, per object read or per input.
46//!
47//! Owner: the scaffold (implemented). Packages read these fields and charge
48//! through these types; a new limit is added only through the integration
49//! package.
50//!
51//! [`MemoryBudget`]: crate::budget::MemoryBudget
52//! [`Reservation`]: crate::budget::Reservation
53
54use crate::budget::{AllocError, BudgetExceeded};
55use crate::error::LimitError;
56
57mod meter;
58mod traversal;
59mod vec;
60
61pub use meter::{Charge, Meter, WorkPast};
62pub(crate) use meter::{GrantScope, pool_refusals, refusal};
63pub use traversal::TreeTraversal;
64pub use vec::MeteredVec;
65pub(crate) use vec::{grow_charged, grow_counted, reserve_exact, shrink_charged};
66
67/// Bounds on allocation, recursion and work per input.
68#[derive(Clone, Copy, Debug, PartialEq, Eq)]
69#[non_exhaustive]
70pub struct Limits {
71    /// What the core may hold for one input at once, in bytes, charged to
72    /// the input's [`Meter`] before every allocation whose size the input
73    /// chooses (module docs). Default 8 GiB.
74    pub max_input_memory: u64,
75    /// The longest input the Environment loads, from any
76    /// [`crate::env::Source`]: a path's file is checked from its length
77    /// before anything is read, and again as it is read
78    /// ([`crate::env::read_path`]); a fetch from the size its fetcher states
79    /// ([`crate::env::Fetch::size_hint`]) before it is fetched, and from the
80    /// length of what it returns; given bytes from their length. Default
81    /// 4 GiB.
82    pub max_input_bytes: u64,
83    /// One block's actual decoded output (blocks-info's included). LZMA
84    /// decodes to the end of its input whatever blocks-info says
85    /// (`helpers/CompressionHelper.py:17-44`), so a bomb is stopped here
86    /// before the meter. Default 4 GiB: a bundle states each block's size,
87    /// and its blocks-info's, in 32 bits (`files/BundleFile.py`, each
88    /// `read_u_int`), so no well-formed block's output reaches it (review
89    /// round 9's sweep; it was 1 GiB, which refused an LZMA bundle, one
90    /// block, that decodes to more).
91    pub max_block_output: u64,
92    /// The *work* one open of an input may cost, in bytes: every byte a
93    /// block decode writes, kept or not (a first decode, a measuring decode
94    /// whose output is dropped, a re-decode of a shared block, a decode that
95    /// fails after it wrote), whether or not its buffer had to grow for it,
96    /// and every byte the meter granted to a lazy computation, on the
97    /// computation's own thread, that the meter itself then refused
98    /// ([`LimitKind::InputMemory`]: a parse or compile that alone needs more
99    /// than the meter, which the next ask runs again:
100    /// [`crate::once::get_or_publish_result`]); and the bytes a parse
101    /// searches or indexes (a string's search, a typetree blob's one pass
102    /// over its string buffer, an old-format file's type index:
103    /// `typetree::parse` and `files::serialized`), every byte of a block a
104    /// codec reads beyond what it writes, counted before it reads it
105    /// (`files::bundle`: an LZ4 scan that fails writes nothing), the bytes a
106    /// bundle entry's gzip detection reads and inflates (`detect`), and every byte
107    /// the meter granted an entry parse that ended in an error its cell
108    /// keeps (`files::bundle`), all of which K directory rows over one span
109    /// repeat K times (round 4); and the work of every read and write of an
110    /// object's value, whatever its outcome ([`crate::walk::VALUE_WORK`] a
111    /// value built, written or skipped, a primitive run's bytes, a string's
112    /// bytes a write copies, a ref type a lookup reads,
113    /// [`crate::walk::STEP_WORK`] a step that builds no value: `walk`'s
114    /// "Work"), which K objects over one span repeat K times, a read refused
115    /// by its own bound keeping nothing (fix pass 4's sweep), as K objects
116    /// search one list of ref types; a read or a write counts as it goes and
117    /// is refused once its work takes the open past the allowance, and past
118    /// the allowance one is refused before it starts. The meter
119    /// bounds what is
120    /// held; this bounds what is done, so an input cannot make its readers
121    /// decode or recompute without end while the meter stays empty
122    /// (thousands of blocks that each decode to the block cap, measured and
123    /// dropped by a lazy read of the last entry; one type whose compile alone
124    /// needs more than the meter, asked by every object of the type). A
125    /// write the meter or the budget refuses decodes nothing and counts
126    /// nothing, and a lazy computation the budget, an I/O failure or a
127    /// provider refused counts nothing either (those depend on what else is
128    /// held or on caller code, and the engine bounds its retries), so
129    /// contention never uses the allowance up; a write is counted atomically
130    /// (between a growth's charge and its allocation when it grows), so
131    /// decodes running at once never pass the bound
132    /// ([`Meter::count_decode`]). It is counted
133    /// per open: every file of one open shares its meter's count, and the
134    /// Environment reopens an evicted dependency on [`Meter::reopen`], so
135    /// eviction churn costs work in proportion to the reads that cause it
136    /// and never exhausts a valid dependency. UnityPy decodes every block
137    /// once; a lazy read of a bundle whose entries do not overlap decodes a
138    /// block at most four times: measured, decoded for the entries wholly
139    /// inside it, and decoded again for each of the two entries that
140    /// straddle its edges (plan section 3.6, "Runs"). Default 32 GiB, four
141    /// times [`Self::max_input_memory`].
142    ///
143    /// [`LimitKind::InputMemory`]: crate::error::LimitKind::InputMemory
144    pub max_decode_work: u64,
145    /// One gzip stream inflated by detection (rule 7, streamed into a fixed
146    /// scratch buffer and never held). Default 4 GiB.
147    pub max_inflate: u64,
148    /// Containers nested in one input (a bundle entry that is itself a
149    /// bundle, and so on): parsing one recurses. Default 16.
150    pub max_container_depth: u32,
151    /// Depth of a compiled typetree. Default 256.
152    pub max_tree_depth: u32,
153    /// Runtime nesting while reading or writing a value, `ReferencedObject`
154    /// data included: the frames each reader and the writer recurse through
155    /// (plan section 3.10, "Bounds"). UnityPyBoost's are its C recursion,
156    /// which has no bound of its own; the pure-Python reader's and the
157    /// writer's are the Python frames UnityPy's own pushes (`read_value`,
158    /// `read_value_array`, each comprehension and `lambda`), so every value
159    /// UnityPy refuses with `RecursionError` (Python's 1,000 frames) passes
160    /// this first. What it costs in stack: [`Self::stack_needed`]. Default 512.
161    pub max_value_depth: u32,
162    /// The *work* of one object read or write that neither its bytes nor
163    /// its memory bound: each child it skips (a `ReferencedObject`'s data
164    /// that does not resolve to a tree, a `ManagedReferencesRegistry` once
165    /// one is in scope), since a class can skip many children for each
166    /// element of an array; each value built or written under a child whose
167    /// name a sibling repeats, since such a tree hands one value to each
168    /// child of the name, which writes it whole, and a read keeps only the
169    /// last; each child of a class a write writes from a value that is not
170    /// a dict whose write writes no byte (the child's value is an attribute
171    /// of the class's, which neither the value's memory nor the output
172    /// bounds); and every value and every element of a primitive run the
173    /// pure-Python reader reads, since a negative length lets it read the
174    /// same bytes again. A value UnityPyBoost's reader keeps, a primitive
175    /// run being one, is charged to the meter, and a write writes it from
176    /// there, so neither counts (review round 9: a `vector<UInt8>` of 2^26 +
177    /// 1 bytes was refused at this default; `tests/walk_runs.rs`). A write
178    /// through the tree its value was read with counts no more than its
179    /// read did unless the tree repeats a name, or a node whose type name
180    /// holds a NUL (read by UnityPyBoost as a primitive, a string or bytes,
181    /// written as a class) has a child that writes no byte
182    /// (`tests/walk_bounds.rs`). The work of every read and write together
183    /// is the open's ([`Self::max_decode_work`]). Default 2^26.
184    pub max_values_per_object: u64,
185    /// Array elements, per object, whose read ended no further on than it
186    /// began and did work it keeps nothing of: skipped a child (a registry
187    /// while one is in scope, a `ReferencedObject`'s data that resolves to
188    /// no tree), built a value a sibling of the same name replaces, or, in
189    /// the pure-Python reader, took the position back (a negative
190    /// `TypelessData` length), so every element reads the same bytes. An
191    /// element that reads a byte is never counted, whatever its tree, nor is
192    /// one that keeps all it builds: an array of a class with no fields is
193    /// read at any count, each element a value charged to the meter (plan
194    /// section 9, Q15 (c); `tests/walk_elements.rs`). Default 2^20.
195    pub max_zero_size_elements: u64,
196    /// Elements a read reserves before the bytes prove they exist, in all
197    /// the lists it holds open at once (a list nested in another, or in a
198    /// `ReferencedObject` re-entering its ref type, has what its outer
199    /// lists left); each list grows past its first reservation as it is
200    /// filled. Default 2^16.
201    pub max_prealloc: usize,
202}
203
204impl Limits {
205    /// The stack a thread needs to read or write one object under these
206    /// limits, from the frame that calls the reader or the writer: they
207    /// recurse once per level they count against
208    /// [`Self::max_value_depth`], and nothing else an object's bytes drive
209    /// recurses deeper (a typetree compiles without recursion; a value is
210    /// dropped one level per reader level). It grows with `max_value_depth`,
211    /// and a debug build's frames are several times a release build's.
212    ///
213    /// At the defaults: 1.75 MiB in a release build, 9 MiB in a debug one.
214    /// `tests/walk_stack.rs` reads, writes and drops the deepest object of
215    /// every shape on a thread this size, and its `stack_measured` prints
216    /// the least each needs: at most 1,261,568 bytes (1.2 MiB) in release
217    /// and 7,979,008 (7.6 MiB) in debug, with toolchain 1.99.1 (`cargo test
218    /// -p unityrs-core --test walk_stack [--release] -- --ignored
219    /// --nocapture`; review round 11: this said 0.90 MiB, measured before
220    /// fix pass 10; `docs/plans/core.md` section 6 records each integrated
221    /// head's). Rust's spawned threads get 2 MiB unless told
222    /// otherwise, and a main thread usually 8 MiB, so a debug build reads
223    /// untrusted input on a thread built with
224    /// `std::thread::Builder::stack_size(limits.stack_needed())`.
225    #[must_use]
226    pub fn stack_needed(&self) -> usize {
227        let (per_level, base): (usize, usize) = if cfg!(debug_assertions) {
228            (16 << 10, 1 << 20)
229        } else {
230            (3 << 10, 256 << 10)
231        };
232        usize::try_from(self.max_value_depth)
233            .unwrap_or(usize::MAX)
234            .saturating_mul(per_level)
235            .saturating_add(base)
236    }
237}
238
239impl Default for Limits {
240    fn default() -> Self {
241        Self {
242            max_input_memory: 8 << 30,
243            max_input_bytes: 4 << 30,
244            max_block_output: 4 << 30,
245            max_decode_work: 32 << 30,
246            max_inflate: 4 << 30,
247            max_container_depth: 16,
248            max_tree_depth: 256,
249            max_value_depth: 512,
250            max_values_per_object: 1 << 26,
251            max_zero_size_elements: 1 << 20,
252            max_prealloc: 1 << 16,
253        }
254    }
255}
256
257/// Buckets a hash table is charged (or counted) per key: a doubling table
258/// (hashbrown's, behind `std`'s `HashMap`) is at least 7/16 full once it has
259/// grown, so it holds up to 16/7 buckets per key, and while it grows the old
260/// table and the doubled one are both live, up to 24/7 buckets per key; four
261/// cover both. A bucket is a key, a value and one control byte; the table's
262/// fixed part (its control bytes' tail of one SIMD group, 16 bytes, and the
263/// allocator's rounding of its one allocation) is a constant per table.
264pub(crate) const HASH_TABLE_SHARES: u64 = 4;
265
266/// The charge for a hash table of `len` keys (at least two keys' worth)
267/// whose key and value take `entry` bytes together: [`HASH_TABLE_SHARES`]
268/// buckets a key, each the entry and one control byte, plus the table's
269/// fixed part, as one [`heap_cost`]. A table that grows one key at a time
270/// charges `hash_table_cost(n + 1, _) - hash_table_cost(n, _)` before each
271/// insert; the 4/7 of a bucket a key between the four charged and the 24/7
272/// a doubling holds covers the rounding of the second allocation while
273/// both are live.
274pub(crate) fn hash_table_cost(len: usize, entry: usize) -> u64 {
275    let bucket = (entry as u64).saturating_add(1);
276    heap_cost(
277        (len.max(2) as u64)
278            .saturating_mul(HASH_TABLE_SHARES.saturating_mul(bucket))
279            .saturating_add(16),
280    )
281}
282
283/// glibc's default `M_MMAP_THRESHOLD`: a chunk of at least this many bytes
284/// may be `mmap`ped (the threshold starts here and can only rise, which
285/// serves more chunks from the heap, never fewer).
286const MMAP_THRESHOLD: u64 = 128 << 10;
287
288/// glibc's chunk for a request of `bytes` from its heap on x86-64: the
289/// request and its 8-byte header rounded up to 16, at least 32
290/// (`request2size`).
291const fn heap_chunk(bytes: u64) -> u64 {
292    let chunk = bytes.saturating_add(8 + 15) & !15;
293    if chunk < 32 { 32 } else { chunk }
294}
295
296/// What one heap allocation of `bytes` costs, which is what a charge for it
297/// is: glibc's chunk on x86-64. The request gets its 8-byte header and is
298/// rounded to 16, with a 32-byte minimum (`request2size`); a chunk of
299/// 128 KiB (glibc's default `M_MMAP_THRESHOLD`) or more may be `mmap`ped
300/// instead, which adds another 8 bytes and rounds to a 4 KiB page
301/// (`sysmalloc`'s `ALIGN_UP(nb + SIZE_SZ, pagesize)`), and that is the
302/// larger of the two. 0 for no allocation.
303///
304/// So a charge covers the rounding of a fresh chunk, carved from the top of
305/// a heap or mapped. What it does not cover (review round 13): glibc hands
306/// over a free chunk whole when what would be left of it could not be a
307/// chunk of its own (under its 32-byte minimum: `_int_malloc`'s best fit,
308/// and `_int_realloc` when it grows or shrinks a chunk in place), so a live
309/// allocation whose chunk is below 128 KiB can hold [`CHUNK_SLACK`] bytes
310/// past its charge, depending on what the heap freed before it: at most
311/// half again of the smallest charge, 48 bytes against 32, and less as the
312/// charge grows. A mapped chunk's page covers the 16 bytes. A buffer whose
313/// spare room is given back below 128 KiB from a block that may be mapped is
314/// moved to a new allocation ([`shrink_moves`]): glibc's `realloc` would keep
315/// it mapped, a page or more against a charge of tens of bytes.
316/// `tests/heap_rounding.rs` measures both on glibc.
317#[must_use]
318pub const fn heap_cost(bytes: u64) -> u64 {
319    if bytes == 0 {
320        return 0;
321    }
322    let chunk = heap_chunk(bytes);
323    if chunk < MMAP_THRESHOLD {
324        chunk
325    } else {
326        chunk.saturating_add(8 + 4095) & !4095
327    }
328}
329
330/// The most a live allocation whose chunk is below 128 KiB holds past its
331/// [`heap_cost`]: glibc hands over a free chunk whole when what would be left
332/// is under its 32-byte minimum chunk, and chunks are multiples of 16, so
333/// what is left is 0 or 16 bytes ([`heap_cost`]'s docs). That is for an
334/// alignment of 16 bytes or less (`malloc`'s), which every allocation the
335/// core charges has.
336pub const CHUNK_SLACK: u64 = 16;
337
338/// Whether a buffer whose block holds `cap` bytes gives back its spare room,
339/// down to `len` bytes, by moving them to a new allocation rather than by
340/// asking the allocator to shrink the block: when the block may be `mmap`ped
341/// (its chunk is 128 KiB or more) and the bytes left would be a heap chunk
342/// (below it). glibc's `realloc` keeps a shrunk mapped block mapped
343/// (`mremap_chunk`), rounded up to a page, so 10 bytes cut from a 1 MiB
344/// buffer held a page against a [`heap_cost`] of 32 (review round 13;
345/// `tests/heap_rounding.rs` with the move undone: "10 bytes hold 4088", its
346/// usable bytes and an 8-byte header).
347/// A new allocation below 128 KiB is a heap chunk, which [`heap_cost`]
348/// covers ([`CHUNK_SLACK`] aside). Both blocks exist while the bytes move,
349/// as they may while `realloc` moves them, so a caller charges both first.
350#[must_use]
351pub const fn shrink_moves(len: u64, cap: u64) -> bool {
352    len < cap && heap_chunk(cap) >= MMAP_THRESHOLD && heap_chunk(len) < MMAP_THRESHOLD
353}
354
355/// A charge the meter or the budget refused. Nothing was allocated.
356///
357/// Callers must leave room for future refusal kinds.
358/// ```compile_fail,E0004
359/// use unityrs_core::limits::ChargeError;
360/// fn classify(error: ChargeError) {
361///     match error {
362///         ChargeError::Limit(_) => {},
363///         ChargeError::Budget(_) => {},
364///         ChargeError::Allocator(_) => {},
365///     }
366/// }
367/// ```
368#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
369#[non_exhaustive]
370pub enum ChargeError {
371    /// The input's own bound ([`Limits::max_input_memory`], or a buffer's
372    /// cap such as [`Limits::max_block_output`]).
373    #[error(transparent)]
374    Limit(#[from] LimitError),
375    /// The shared budget refused, or the allocator failed.
376    #[error(transparent)]
377    Budget(#[from] BudgetExceeded),
378    /// The host allocator refused storage after any charge was granted.
379    #[error(transparent)]
380    Allocator(#[from] AllocError),
381}
382
383#[cfg(test)]
384mod tests;