Skip to main content

unityrs_core/walk/
work.rs

1//! The work of one read or one write, counted on its open's meter as it is
2//! done ([`OpenWork`]), and one read's bounds of its own ([`Work`]): the
3//! module docs of [`super`], "Work"; plan 3.10, "Bounds" and "Work per
4//! open".
5
6use super::{ReadDetail, ReadError, ReadErrorKind, first_reserve, limit_error};
7use crate::error::{LimitError, LimitKind};
8use crate::limits::{Limits, Meter};
9use crate::value::Value;
10
11/// The open's work one value costs a read or a write, in bytes
12/// ([`crate::limits::Limits::max_decode_work`]): the size of the [`Value`]
13/// that holds it, whether the value is kept or not, as a decode counts every
14/// byte it writes whether its output is kept or not. A child a read or a
15/// write skips costs as much. An element of a primitive run that a read
16/// holds as a run costs its width instead (`Work::run`, `Work::elements`),
17/// and so does a primitive a write writes.
18pub const VALUE_WORK: u64 = size_of::<Value>() as u64;
19
20/// The open's work one step costs a read or a write that builds no value,
21/// in bytes: a slot a dict's table of positions grows by, an entry a lookup
22/// by name passes, and an entry a name table indexes. 8, as a step of a
23/// bundle read (plan 3.6, "What a read costs"). A name a step compares or
24/// hashes counts its bytes besides.
25pub const STEP_WORK: u64 = 8;
26
27/// The most work a read or a write counts on its own before it adds it to
28/// its open's meter, in bytes (`OpenWork`): so the most it can be past
29/// its open's allowance before it learns of it, and the most each read or
30/// write in progress on other threads can add past it.
31pub const WORK_CHUNK: u64 = 64 << 10;
32
33/// The open's work refusal once its work has passed its allowance, `Ok`
34/// while it is within it: what a read or a write meets before it starts and
35/// when it ends (module docs of [`super`], "Work").
36pub(crate) fn work_left(meter: &Meter) -> Result<(), LimitError> {
37    meter.work_refused().map_or(Ok(()), Err)
38}
39
40/// The open's work of one read or one write, counted on the open's meter
41/// as it is done (module docs, "Work"). A step is counted before it is
42/// done; the steps add up here, and every [`WORK_CHUNK`] of them goes to the
43/// meter in one atomic check-and-add, so reads and writes on several
44/// threads that share one meter learn of each other's work as it is done,
45/// and stop once the open's work has passed its allowance (review round 6:
46/// each read added its work only when it ended, so two that started
47/// together within the allowance both ran to their end past it). A chunk
48/// the allowance cannot hold is refused: the steps before the one that
49/// filled it are done, and counted; that one is not done, nor counted. The
50/// read or write then fails with [`LimitKind::DecodeWork`]. When it ends
51/// ([`Self::finish`]), what is left is counted and checked: a read or a
52/// write whose own work took its open past its allowance fails too, so the
53/// work of those that succeed is never past it, however they interleave.
54/// Each one in progress can count at most a chunk and one step past it.
55pub(crate) struct OpenWork<'m> {
56    meter: &'m Meter,
57    /// Counted here and not yet on the meter: less than [`WORK_CHUNK`].
58    pending: u64,
59}
60
61impl<'m> OpenWork<'m> {
62    /// The work of a read or a write on `meter`: refused before it starts
63    /// once the open's work has passed its allowance.
64    pub(crate) fn start(meter: &'m Meter) -> Result<Self, LimitError> {
65        work_left(meter)?;
66        Ok(Self { meter, pending: 0 })
67    }
68
69    /// Counts `n` bytes of work, about to be done.
70    #[inline]
71    pub(crate) fn add(&mut self, n: u64) -> Result<(), LimitError> {
72        let done = self.pending;
73        let pending = done.saturating_add(n);
74        if pending < WORK_CHUNK {
75            self.pending = pending;
76            return Ok(());
77        }
78        self.pending = 0;
79        self.meter.count_work(pending).inspect_err(|_| {
80            // The steps before this one are done, whatever the bound says.
81            self.meter.add_work(done);
82        })
83    }
84
85    /// Counts `n` steps of [`STEP_WORK`], about to be taken.
86    #[inline]
87    pub(crate) fn steps(&mut self, n: usize) -> Result<(), LimitError> {
88        self.add(
89            u64::try_from(n)
90                .unwrap_or(u64::MAX)
91                .saturating_mul(STEP_WORK),
92        )
93    }
94
95    /// Counts what is left, all of it done, and refuses once the open's work
96    /// has passed its allowance.
97    pub(crate) fn finish(&mut self) -> Result<(), LimitError> {
98        self.meter.add_work(std::mem::take(&mut self.pending));
99        work_left(self.meter)
100    }
101}
102
103impl Drop for OpenWork<'_> {
104    /// Work left uncounted by a read or a write that never reached
105    /// [`OpenWork::finish`] is done all the same.
106    fn drop(&mut self) {
107        self.meter.add_work(std::mem::take(&mut self.pending));
108    }
109}
110
111/// A [`Limits`] bound's refusal, or the open's work's, while reading: kind
112/// `other` (R16).
113pub(crate) fn limit_refused(at: u64, limit: LimitError) -> ReadError {
114    ReadError {
115        kind: ReadErrorKind::Other,
116        at,
117        detail: ReadDetail::Limit(limit),
118    }
119}
120
121/// The reader's limits on work, shared by both readers (plan 3.10, "Bounds").
122///
123/// **What counts against `max_values_per_object`.** The bound is for the
124/// work of one read that neither its bytes nor its memory bounds. Every
125/// value a read keeps sits in a slot charged to the input's meter (a list's
126/// item, a dict's entry, a tuple's item: at least a [`Value`] each), and a
127/// primitive run is one value whose elements are bytes of the input
128/// (UnityPyBoost's `vector<UInt8>`, a slice) or of a charged run. So
129/// UnityPyBoost's reader, whose position never goes back, counts against it
130/// only what it does and keeps nothing of: each child it skips
131/// ([`Self::skipped`]), and each value it builds under a child whose name a
132/// sibling repeats ([`Self::enter_repeated`]), one of which replaces the
133/// other's value ([`Self::kept`]). Everything else it builds is bounded by
134/// `max_input_memory` and by the object's bytes, as UnityPy's own values are
135/// by the memory they take (review round 9: a `Mesh` of a 2^26 + 1 byte
136/// `vector<UInt8>`, and any struct array of more than 2^26 values, was
137/// refused where UnityPy reads it). The pure-Python reader counts every
138/// value it builds and every element of a primitive run
139/// ([`Self::elements`]): a negative `TypelessData` length takes it back, so
140/// it can read the same bytes again any number of times, and a
141/// `vector<UInt8>`'s elements are a slice that holds none of them.
142pub(crate) struct Work<'m> {
143    pub(crate) values: u64,
144    pub(crate) zero_size: u64,
145    /// How many times the read has done work it keeps nothing of
146    /// ([`Self::discard`]); an element's [`Self::zero_size`] compares it
147    /// with its value before the element.
148    discards: u64,
149    pub(crate) depth: u32,
150    /// How many children whose name a sibling repeats are being read
151    /// ([`crate::typetree::NodeInfo::repeated`]): while any is, every value
152    /// built counts against `max_values_per_object`.
153    repeated: u32,
154    /// Elements the read's open lists reserved before their bytes were read
155    /// and have not filled yet ([`Self::first_room`]).
156    unfilled: usize,
157    /// The open's work, counted as the read goes.
158    pub(crate) open: OpenWork<'m>,
159    pub(crate) limits: Limits,
160}
161
162impl<'m> Work<'m> {
163    /// The work of a read on `meter`: refused before it starts once the
164    /// open's work has passed its allowance (module docs, "Work").
165    pub(crate) fn start(limits: Limits, meter: &'m Meter) -> Result<Self, ReadError> {
166        let open = OpenWork::start(meter).map_err(|l| limit_refused(0, l))?;
167        Ok(Self {
168            values: 0,
169            zero_size: 0,
170            discards: 0,
171            depth: 0,
172            repeated: 0,
173            unfilled: 0,
174            open,
175            limits,
176        })
177    }
178
179    /// The first reservation of a list of `len` elements of at least
180    /// `min_size` bytes each, `remaining` bytes left ([`first_reserve`]): at
181    /// most what the read's open lists leave of `max_prealloc`, so every
182    /// list a read holds open at once (vectors nested in vectors, a ref type
183    /// re-entered level after level) reserves no more together than one may
184    /// (review round 7's sweep: each reserved `max_prealloc` of its own, so
185    /// a read nested `d` deep held `d` times it before the bytes were read).
186    /// It is unfilled until [`Self::filled`] counts its elements.
187    pub(crate) fn first_room(&mut self, len: usize, remaining: usize, min_size: u32) -> usize {
188        let room = self.limits.max_prealloc.saturating_sub(self.unfilled);
189        let first = first_reserve(len, remaining, min_size, room);
190        self.unfilled = self.unfilled.saturating_add(first);
191        first
192    }
193
194    /// Element `i` of a list whose first reservation was `first` is read.
195    pub(crate) fn filled(&mut self, i: usize, first: usize) {
196        if i < first {
197            self.unfilled = self.unfilled.saturating_sub(1);
198        }
199    }
200
201    /// Counts what is left of the read's work on its open's meter, whatever
202    /// the read's outcome, and refuses once the open's work has passed its
203    /// allowance ([`OpenWork::finish`]).
204    pub(crate) fn finish(&mut self, at: u64) -> Result<(), ReadError> {
205        self.open.finish().map_err(|l| limit_refused(at, l))
206    }
207
208    /// Counts `n` steps that build no value ([`STEP_WORK`]), about to be
209    /// taken: the open's work, and not against `max_values_per_object`,
210    /// which counts what UnityPy's reader counts.
211    pub(crate) fn steps(&mut self, n: usize, at: u64) -> Result<(), ReadError> {
212        self.open.steps(n).map_err(|l| limit_refused(at, l))
213    }
214
215    /// Counts `n` values against `max_values_per_object`, each
216    /// [`VALUE_WORK`] of the open's work: every value the pure-Python reader
217    /// builds.
218    pub(crate) fn values(&mut self, n: u64, at: u64) -> Result<(), ReadError> {
219        self.count(n, n.saturating_mul(VALUE_WORK), at)
220    }
221
222    /// Counts one child the read skips (a `ReferencedObject`'s data that
223    /// resolves to no tree, a `ManagedReferencesRegistry` once one is in
224    /// scope) as a value ([`Self::values`]): the class's loop visits it
225    /// whether or not a value comes out, and keeps nothing of it
226    /// ([`Self::discard`]).
227    pub(crate) fn skipped(&mut self, at: u64) -> Result<(), ReadError> {
228        self.discard();
229        self.values(1, at)
230    }
231
232    /// Marks work the read keeps nothing of: a child it skips
233    /// ([`Self::skipped`]), a value a later sibling of the same name
234    /// replaces (`walk::dict::Dict::set`), and, in the pure-Python reader, a
235    /// read that takes the position back, so later reads read the same
236    /// bytes again. An element that does any of these and reads no byte is
237    /// what [`Self::zero_size`] counts.
238    pub(crate) fn discard(&mut self) {
239        self.discards = self.discards.wrapping_add(1);
240    }
241
242    /// The mark an element's [`Self::zero_size`] is given: how many times
243    /// the read had done work it keeps nothing of before the element.
244    pub(crate) fn discards(&self) -> u64 {
245        self.discards
246    }
247
248    /// Counts one value UnityPyBoost's reader builds: [`VALUE_WORK`] of the
249    /// open's work, and against `max_values_per_object` only under a child
250    /// whose name a sibling repeats (the type's docs).
251    pub(crate) fn kept(&mut self, at: u64) -> Result<(), ReadError> {
252        let n = u64::from(self.repeated > 0);
253        self.count(n, VALUE_WORK, at)
254    }
255
256    /// Counts a primitive run of `bytes` bytes that UnityPyBoost's reader
257    /// holds as one value (a [`crate::value::PrimRun`] or a slice of the
258    /// object), its vector's: its bytes as the open's work, as a decode
259    /// counts the bytes it writes, and no value of its own. Its elements
260    /// are the object's bytes, which its position passes once.
261    pub(crate) fn run(&mut self, bytes: u64, at: u64) -> Result<(), ReadError> {
262        self.open.add(bytes).map_err(|l| limit_refused(at, l))
263    }
264
265    /// Counts `n` elements of `width` bytes each of a primitive run the
266    /// pure-Python reader reads one by one: `n` values against
267    /// `max_values_per_object`, and their bytes as the open's work.
268    pub(crate) fn elements(&mut self, n: u64, width: u64, at: u64) -> Result<(), ReadError> {
269        self.count(n, n.saturating_mul(width), at)
270    }
271
272    /// Starts reading a child whose name a sibling repeats: until the
273    /// matching [`Self::leave_repeated`], [`Self::kept`] counts every value
274    /// against `max_values_per_object`.
275    pub(crate) fn enter_repeated(&mut self) {
276        self.repeated = self.repeated.saturating_add(1);
277    }
278
279    pub(crate) fn leave_repeated(&mut self) {
280        self.repeated = self.repeated.saturating_sub(1);
281    }
282
283    fn count(&mut self, n: u64, work: u64, at: u64) -> Result<(), ReadError> {
284        self.values = self.values.saturating_add(n);
285        if self.values > self.limits.max_values_per_object {
286            return Err(limit_error(
287                at,
288                LimitKind::ValuesPerObject,
289                self.values,
290                self.limits.max_values_per_object,
291            ));
292        }
293        self.open.add(work).map_err(|l| limit_refused(at, l))
294    }
295
296    /// Counts one array element whose read ended no further on than it
297    /// began (plan section 9, Q15 (c)), when the read did work it keeps
298    /// nothing of since `before` (the [`Self::discards`] mark taken before
299    /// the element): it skipped a child, a sibling of the same name replaced
300    /// a value, or, in the pure-Python reader, a negative `TypelessData`
301    /// length took the position back ([`Self::discard`]). Such elements do
302    /// work that neither the object's bytes nor the meter bound, so a count
303    /// in a few bytes could ask any number of them. Every other element
304    /// keeps what it builds, each value in a slot charged to the meter (a
305    /// list's item, a dict's entry), and [`VALUE_WORK`] of the open's work a
306    /// value: an array of a class with no fields reads no byte per element,
307    /// and is read at any count the meter holds, as UnityPy reads it (review
308    /// round 9's sweep found it refused past 2^20). What an element really
309    /// read is the test, not its tree's
310    /// [`crate::typetree::NodeInfo::min_size`]: which children a read skips
311    /// depends on the registry in scope, and the pure-Python reader reads a
312    /// malformed `pair` or `Array` UnityPyBoost refuses (review round 4:
313    /// both were refused past the bound where UnityPy read them).
314    pub(crate) fn zero_size(&mut self, before: u64, at: u64) -> Result<(), ReadError> {
315        if self.discards == before {
316            return Ok(());
317        }
318        self.zero_size = self.zero_size.saturating_add(1);
319        if self.zero_size > self.limits.max_zero_size_elements {
320            return Err(limit_error(
321                at,
322                LimitKind::ZeroSizeElements,
323                self.zero_size,
324                self.limits.max_zero_size_elements,
325            ));
326        }
327        Ok(())
328    }
329
330    /// Enters one level of value nesting.
331    pub(crate) fn enter(&mut self, at: u64) -> Result<(), ReadError> {
332        self.depth = self.depth.saturating_add(1);
333        if self.depth > self.limits.max_value_depth {
334            return Err(limit_error(
335                at,
336                LimitKind::ValueDepth,
337                u64::from(self.depth),
338                u64::from(self.limits.max_value_depth),
339            ));
340        }
341        Ok(())
342    }
343
344    pub(crate) fn leave(&mut self) {
345        self.depth = self.depth.saturating_sub(1);
346    }
347}