1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
// Ported from UnityPy 1.25.2 (MIT): UnityPy/helpers/CompressionHelper.py. See THIRD_PARTY_LICENSES.
//! Hard bounds on what untrusted input can make the library allocate or do,
//! and the one meter that enforces the memory bound.
//!
//! UnityPy has none of these: where it would exhaust memory or the C stack,
//! unityrs stops with [`crate::Error::Limit`] (or the walker's `other` kind) and
//! `PARITY.md` lists the case as a safety divergence (plan section 3.15).
//!
//! **One meter per input.** Everything the core allocates in proportion to a
//! size or count the input chose is charged to the input's [`Meter`] *before*
//! it is allocated: the input's own bytes when the core reads a path, every
//! block decode (a first decode, a lazy re-decode, a measuring decode, a
//! decode after eviction), every metadata table and typetree row of every
//! entry parse (an entry parsed twice, or two directory rows over the same
//! bytes, pay twice), every compiled tree, every parsed value and every
//! writer output. A charge the meter refuses allocates nothing. The charge is
//! a [`Charge`] that lives inside what it paid for, so the bytes return when
//! that drops: a [`crate::Parsed`] carries the charge for its values, a
//! decoded buffer's [`bytes::Bytes`] the charge for the buffer. So what one
//! input holds at any moment, retained values included, is at most
//! [`Limits::max_input_memory`] in the unit the meter charges ([`heap_cost`],
//! a request in glibc's chunks), plus the constant overhead plan section 3.15
//! states; in glibc's own chunks a live allocation below 128 KiB may hold up
//! to [`CHUNK_SLACK`] bytes more than its charge, at most half again of it
//! ([`heap_cost`]'s docs), so the heap such an input holds is at most half
//! again of that limit, plus the constant. A top-level load makes the meter;
//! every file inside it (a bundle's entries, nested bundles) charges the same
//! one.
//!
//! **A meter is one open of its input.** Its memory is the input's: an
//! account every open of the input shares, so the bound holds across opens.
//! Its *work* ([`Limits::max_decode_work`]) is the open's own: the
//! Environment opens an evicted dependency again on [`Meter::reopen`], a new
//! meter on the same account with a fresh allowance, while a handle of the
//! old open that someone still holds (a nested bundle a resource read kept)
//! goes on counting against the old meter's, which nothing resets.
//!
//! **One accounting path.** The meter books every charge it grants with the
//! load's [`MemoryBudget`] as well ([`crate::FileContext::budget`]), so a
//! batch engine's budget sees exactly what every input holds, and a refusal
//! says which side refused: [`ChargeError::Limit`] (this input's bound) or
//! [`ChargeError::Budget`] (the shared budget, tagged with the meter's
//! [`Reservation`]).
//!
//! The other bounds are on work and nesting, per object read or per input.
//!
//! Owner: the scaffold (implemented). Packages read these fields and charge
//! through these types; a new limit is added only through the integration
//! package.
//!
//! [`MemoryBudget`]: crate::budget::MemoryBudget
//! [`Reservation`]: crate::budget::Reservation
use crate;
use crateLimitError;
pub use ;
pub use ;
pub use TreeTraversal;
pub use MeteredVec;
pub use ;
/// Bounds on allocation, recursion and work per input.
/// Buckets a hash table is charged (or counted) per key: a doubling table
/// (hashbrown's, behind `std`'s `HashMap`) is at least 7/16 full once it has
/// grown, so it holds up to 16/7 buckets per key, and while it grows the old
/// table and the doubled one are both live, up to 24/7 buckets per key; four
/// cover both. A bucket is a key, a value and one control byte; the table's
/// fixed part (its control bytes' tail of one SIMD group, 16 bytes, and the
/// allocator's rounding of its one allocation) is a constant per table.
pub const HASH_TABLE_SHARES: u64 = 4;
/// The charge for a hash table of `len` keys (at least two keys' worth)
/// whose key and value take `entry` bytes together: [`HASH_TABLE_SHARES`]
/// buckets a key, each the entry and one control byte, plus the table's
/// fixed part, as one [`heap_cost`]. A table that grows one key at a time
/// charges `hash_table_cost(n + 1, _) - hash_table_cost(n, _)` before each
/// insert; the 4/7 of a bucket a key between the four charged and the 24/7
/// a doubling holds covers the rounding of the second allocation while
/// both are live.
pub
/// glibc's default `M_MMAP_THRESHOLD`: a chunk of at least this many bytes
/// may be `mmap`ped (the threshold starts here and can only rise, which
/// serves more chunks from the heap, never fewer).
const MMAP_THRESHOLD: u64 = 128 << 10;
/// glibc's chunk for a request of `bytes` from its heap on x86-64: the
/// request and its 8-byte header rounded up to 16, at least 32
/// (`request2size`).
const
/// What one heap allocation of `bytes` costs, which is what a charge for it
/// is: glibc's chunk on x86-64. The request gets its 8-byte header and is
/// rounded to 16, with a 32-byte minimum (`request2size`); a chunk of
/// 128 KiB (glibc's default `M_MMAP_THRESHOLD`) or more may be `mmap`ped
/// instead, which adds another 8 bytes and rounds to a 4 KiB page
/// (`sysmalloc`'s `ALIGN_UP(nb + SIZE_SZ, pagesize)`), and that is the
/// larger of the two. 0 for no allocation.
///
/// So a charge covers the rounding of a fresh chunk, carved from the top of
/// a heap or mapped. What it does not cover (review round 13): glibc hands
/// over a free chunk whole when what would be left of it could not be a
/// chunk of its own (under its 32-byte minimum: `_int_malloc`'s best fit,
/// and `_int_realloc` when it grows or shrinks a chunk in place), so a live
/// allocation whose chunk is below 128 KiB can hold [`CHUNK_SLACK`] bytes
/// past its charge, depending on what the heap freed before it: at most
/// half again of the smallest charge, 48 bytes against 32, and less as the
/// charge grows. A mapped chunk's page covers the 16 bytes. A buffer whose
/// spare room is given back below 128 KiB from a block that may be mapped is
/// moved to a new allocation ([`shrink_moves`]): glibc's `realloc` would keep
/// it mapped, a page or more against a charge of tens of bytes.
/// `tests/heap_rounding.rs` measures both on glibc.
pub const
/// The most a live allocation whose chunk is below 128 KiB holds past its
/// [`heap_cost`]: glibc hands over a free chunk whole when what would be left
/// is under its 32-byte minimum chunk, and chunks are multiples of 16, so
/// what is left is 0 or 16 bytes ([`heap_cost`]'s docs). That is for an
/// alignment of 16 bytes or less (`malloc`'s), which every allocation the
/// core charges has.
pub const CHUNK_SLACK: u64 = 16;
/// Whether a buffer whose block holds `cap` bytes gives back its spare room,
/// down to `len` bytes, by moving them to a new allocation rather than by
/// asking the allocator to shrink the block: when the block may be `mmap`ped
/// (its chunk is 128 KiB or more) and the bytes left would be a heap chunk
/// (below it). glibc's `realloc` keeps a shrunk mapped block mapped
/// (`mremap_chunk`), rounded up to a page, so 10 bytes cut from a 1 MiB
/// buffer held a page against a [`heap_cost`] of 32 (review round 13;
/// `tests/heap_rounding.rs` with the move undone: "10 bytes hold 4088", its
/// usable bytes and an 8-byte header).
/// A new allocation below 128 KiB is a heap chunk, which [`heap_cost`]
/// covers ([`CHUNK_SLACK`] aside). Both blocks exist while the bytes move,
/// as they may while `realloc` moves them, so a caller charges both first.
pub const
/// A charge the meter or the budget refused. Nothing was allocated.
///
/// Callers must leave room for future refusal kinds.
/// ```compile_fail,E0004
/// use unityrs_core::limits::ChargeError;
/// fn classify(error: ChargeError) {
/// match error {
/// ChargeError::Limit(_) => {},
/// ChargeError::Budget(_) => {},
/// ChargeError::Allocator(_) => {},
/// }
/// }
/// ```