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;