unityrs_core/env/registry/register.rs
1// Ported from UnityPy 1.25.2 (MIT): UnityPy/environment.py. See THIRD_PARTY_LICENSES.
2//! Registering a key (module docs, "Ranks", "Nested containers under
3//! `LoadMode::Lazy`" and "Memory"): `register_cab`'s dict by rank, the lazy
4//! slot a registration drops listed in the same step, or stood in for
5//! (plan section 9, Q14), and what it dropped released after the lock.
6//!
7//! A registration is charged first ([`Registry::prepare`]: every charge it
8//! makes) and published after ([`Registry::apply`]: nothing in it can fail
9//! the registration; the `settle` a load's runs reaches the slots it
10//! listed, and a refusal there leaves them listed for a later call, as
11//! every `settle` does). A load registers each key in turn, each charged
12//! and then published; a dependency's load under `LoadMode::Lazy` charges
13//! every one of its registrations before it publishes the first
14//! ([`Stage`], module docs, "A failed dependency load").
15
16use std::sync::Arc;
17use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
18
19#[cfg(test)]
20use super::Hook;
21use super::{
22 Cab, DepSlot, Dependency, Entry, LOAD_KEYS_HERE, ORDER_LEAF, PENDING_SHARE, Rank, Registry,
23 RegistryInner, SHARE, SLOT_ARC, Slot, SlotKind, pending, reach, slot,
24};
25use crate::error::Error;
26use crate::files::BundleFile;
27use crate::limits::{Charge, Meter, MeteredVec};
28use crate::pystr::simplify_name;
29use crate::raw::RawStr;
30
31/// A registration charged and not yet published ([`Registry::prepare`]):
32/// its key, its position, its slot (its rank the value's), the share of
33/// the tables a key new when it was charged paid for, and the charge for
34/// its position's path.
35pub(crate) struct Staged {
36 /// The simplified name: for a key the registry did not hold when the
37 /// registration was charged, its own charged copy, which the key keeps
38 /// if it is still new at the lock (the name `simplify_name` built is
39 /// dropped once copied, so a staged registration holds one copy of its
40 /// new key, not two); for a known key, the name `simplify_name` built.
41 key: RawStr,
42 position: Rank,
43 slot: Arc<Slot>,
44 /// A new key's share of the tables (`key` is then its copy).
45 share: Option<Charge>,
46 first_charge: Charge,
47}
48
49/// A dependency load's registrations, each charged and none published
50/// (module docs, "A failed dependency load"): [`Registry::stage`] adds one,
51/// [`Registry::commit`] publishes them all in order. Dropped unpublished,
52/// it returns every charge and holds no key, so a load that fails before
53/// its commit leaves the registry as it was. The list is charged to the
54/// dependency's meter.
55pub(crate) struct Stage {
56 staged: MeteredVec<Staged>,
57 /// Whether a staged registration paid for the `order` B-tree's root.
58 root: bool,
59}
60
61impl Stage {
62 /// An empty stage, its list charged to `meter`, the dependency's.
63 pub(crate) fn new(meter: &Arc<Meter>) -> Self {
64 Self {
65 staged: MeteredVec::new(meter),
66 root: false,
67 }
68 }
69
70 /// Room for `n` more registrations, charged first.
71 pub(crate) fn reserve(&mut self, n: usize) -> Result<(), Error> {
72 Ok(self.staged.reserve_exact(n)?)
73 }
74}
75
76/// What a registration dropped (module docs): the slot and its charges,
77/// and whether it was listed, with the steps the listing took.
78struct Dropped {
79 slot: Arc<Slot>,
80 _charge: Charge,
81 listed: Option<u64>,
82}
83
84/// The loads of a registration's rank: the value's (`value`) and the
85/// position's (`position`, at most the value's). They differ only for the
86/// entries of a container a slot stands in for (plan section 9, Q14),
87/// which take their positions at the dropped slot's load, as its eager
88/// load registered them, and their values at the standing slot's.
89#[derive(Clone, Copy, Debug)]
90pub(super) struct Loads {
91 pub(super) value: u64,
92 pub(super) position: u64,
93}
94
95impl Loads {
96 /// A registration at `load` alone.
97 pub(super) fn at(load: u64) -> Self {
98 Self {
99 value: load,
100 position: load,
101 }
102 }
103}
104
105/// Which of two slots of one key stands in for the other (plan section 9,
106/// Q14), told before the registration's write lock, with no lock held
107/// (`reach::stands_in` may read a dependency's open handle), and applied
108/// in the lock's step only when the key's value is still `standing`.
109struct Stand {
110 standing: Arc<Slot>,
111 dropped: Arc<Slot>,
112}
113
114impl Stand {
115 /// What `new` and the key's value `value` tell: the one of greater
116 /// rank stands in for the other when that other is a lazy slot not yet
117 /// reached and `reach::stands_in` says so.
118 fn of(new: &Arc<Slot>, value: &Arc<Slot>) -> Option<Self> {
119 let (standing, dropped) = match new.rank.cmp(&value.rank) {
120 std::cmp::Ordering::Greater => (new, value),
121 std::cmp::Ordering::Less => (value, new),
122 std::cmp::Ordering::Equal => return None,
123 };
124 (dropped.unreached() && reach::stands_in(standing, dropped)).then(|| Self {
125 standing: standing.clone(),
126 dropped: dropped.clone(),
127 })
128 }
129}
130
131/// Who makes a registration: a load (a new key counts for the container
132/// pass's `RuntimeError`), or the reach of a nested container.
133#[derive(Clone, Copy, PartialEq, Eq)]
134pub(super) enum By {
135 Load,
136 Reach,
137}
138
139impl Registry {
140 /// A new load's sequence number: its registrations come after every
141 /// earlier load's (module docs).
142 pub(crate) fn next_load(&self) -> u64 {
143 self.loads.fetch_add(1, Ordering::Relaxed)
144 }
145
146 /// `register_cab(name, cab)` for a file the caller loaded, as a load of
147 /// its own, charged to `meter` (module docs). The slot holds `cab`, so it
148 /// is never evicted: `cab` is a file on a caller's input meter
149 /// ([`crate::budget::Reservation::Input`]), not one the Environment
150 /// loaded as a dependency, which its load registered already, and
151 /// whose reads through such a slot would charge the dependency pool
152 /// outside the Environment's retry (plan section 3.13).
153 pub fn register(&self, name: &RawStr, cab: Cab, meter: &Arc<Meter>) -> Result<(), Error> {
154 let load = self.next_load();
155 self.register_ready(name, cab, load, &[], meter)
156 }
157
158 /// Registers entry `dir_index` of a bundle the caller loaded `Lazy`, as a
159 /// load of its own, to parse on first use; charged to `meter`. As for
160 /// [`Self::register`], `bundle` is on a caller's input meter, not a
161 /// dependency's.
162 pub fn register_lazy(
163 &self,
164 name: &RawStr,
165 bundle: Arc<BundleFile>,
166 dir_index: usize,
167 meter: &Arc<Meter>,
168 ) -> Result<(), Error> {
169 let load = self.next_load();
170 self.register_entry(name, bundle, dir_index, load, &[dir_index], meter)
171 }
172
173 /// Registers a caller's CAB of load `load` at `path`.
174 pub(crate) fn register_ready(
175 &self,
176 name: &RawStr,
177 cab: Cab,
178 load: u64,
179 path: &[usize],
180 meter: &Arc<Meter>,
181 ) -> Result<(), Error> {
182 self.insert(
183 name,
184 SlotKind::Ready(cab),
185 Loads::at(load),
186 path,
187 meter,
188 By::Load,
189 false,
190 )
191 }
192
193 /// Registers entry `dir_index` of a caller's `Lazy` bundle, of load
194 /// `load` at `path`, unread (a lazy slot, module docs).
195 pub(crate) fn register_entry(
196 &self,
197 name: &RawStr,
198 bundle: Arc<BundleFile>,
199 dir_index: usize,
200 load: u64,
201 path: &[usize],
202 meter: &Arc<Meter>,
203 ) -> Result<(), Error> {
204 let kind = SlotKind::Entry { bundle, dir_index };
205 self.insert(name, kind, Loads::at(load), path, meter, By::Load, true)
206 }
207
208 /// Registers a dependency's CAB of load `load` at `path` (module docs),
209 /// charged to `meter`, the dependency's.
210 pub(crate) fn register_dependency(
211 &self,
212 name: &RawStr,
213 dep: &Arc<Dependency>,
214 load: u64,
215 path: &[usize],
216 meter: &Arc<Meter>,
217 ) -> Result<(), Error> {
218 let kind = SlotKind::Dependency {
219 dep: DepSlot::new(dep),
220 };
221 self.insert(name, kind, Loads::at(load), path, meter, By::Load, false)
222 }
223
224 /// Registers entry `path` of a dependency's `Lazy` bundle, of load
225 /// `load`, unread (a lazy slot, module docs), charged to `meter`, the
226 /// dependency's, one key at a time. The tests' only: a dependency's load
227 /// under `Lazy` stages every such registration ([`Self::stage`]), so
228 /// that it publishes nothing when it fails (module docs, "A failed
229 /// dependency load"); `pass_tests.rs` registers its slots this way.
230 #[cfg(test)]
231 pub(crate) fn register_lazy_dependency(
232 &self,
233 name: &RawStr,
234 dep: &Arc<Dependency>,
235 load: u64,
236 path: &[usize],
237 meter: &Arc<Meter>,
238 ) -> Result<(), Error> {
239 let kind = SlotKind::Dependency {
240 dep: DepSlot::new(dep),
241 };
242 self.insert(name, kind, Loads::at(load), path, meter, By::Load, true)
243 }
244
245 /// Stages a dependency's CAB of load `load` at `path`, charged to
246 /// `meter`, the dependency's: [`Self::register_dependency`]'s
247 /// registration, or with `lazy` the tests' `register_lazy_dependency`'s,
248 /// every charge made and nothing published until [`Self::commit`].
249 // The registration's parts, as `register_lazy_dependency`'s, and its stage.
250 #[allow(clippy::too_many_arguments)]
251 pub(crate) fn stage(
252 &self,
253 stage: &mut Stage,
254 name: &RawStr,
255 dep: &Arc<Dependency>,
256 load: u64,
257 path: &[usize],
258 meter: &Arc<Meter>,
259 lazy: bool,
260 ) -> Result<(), Error> {
261 let kind = SlotKind::Dependency {
262 dep: DepSlot::new(dep),
263 };
264 let loads = Loads::at(load);
265 let staged = self.prepare(name, kind, loads, path, meter, lazy, &mut stage.root)?;
266 // Within the room the caller reserved, no growth; past it, a
267 // charged one, whose refusal drops the registration with the rest.
268 Ok(stage.staged.push(staged)?)
269 }
270
271 /// Publishes a load's staged registrations, in the order they were
272 /// staged, each as [`Self::insert`] publishes one (and a load's
273 /// `settle` after each). Nothing in it can fail the load: every charge
274 /// a registration makes was made when it was staged, and the `settle`
275 /// after each, which reaches the lazy slots a registration dropped and
276 /// charges what it reads, keeps a refusal to itself and leaves the slot
277 /// listed for a later call, as every `settle` does. Its one error is
278 /// [`Self::apply`]'s for a key that went away after it was found,
279 /// which nothing does: no registry call removes a key.
280 pub(crate) fn commit(&self, stage: Stage) -> Result<(), Error> {
281 let (staged, _list) = stage.staged.into_parts();
282 for one in staged {
283 self.apply(one, By::Load)?;
284 }
285 Ok(())
286 }
287
288 /// Registers `kind` at rank `(loads.value, path)` under
289 /// `simplify_name(name)` with dict semantics by rank (module docs), as
290 /// a registration at `(loads.position, path)` followed by one at its
291 /// own rank would: a new key takes its place in the order at the
292 /// position and pays its share of the tables and a copy of itself; a
293 /// known key takes the slot only if its rank is greater than its
294 /// slot's, moves to the position if that is less than its own, and pays
295 /// only for the slot (and its new position's path when it moves).
296 /// Charged before anything is allocated; a refusal registers nothing. A
297 /// lazy slot the registration drops unreached (the value it replaces,
298 /// or its own slot when that ranks below the value) is listed in the
299 /// same step, unless the slot that stays stands in for it (plan section
300 /// 9, Q14: told before the lock, [`Stand`]), which then takes its
301 /// position; a load's registration reaches every listed slot before it
302 /// returns ([`Self::settle`], module docs), and a change sets the
303 /// running container preload walks' flags under the key and, for a
304 /// load's, starts a new container index generation, in the step that
305 /// publishes it, under the write lock ([`super::watch`], W1;
306 /// `RegistryInner::publish`); a load's registration that changes no key
307 /// but lists the slot it dropped starts one in the step that lists it.
308 // The registration's parts, each one of the module docs' terms.
309 #[allow(clippy::too_many_arguments)]
310 pub(super) fn insert(
311 &self,
312 name: &RawStr,
313 kind: SlotKind,
314 loads: Loads,
315 path: &[usize],
316 meter: &Arc<Meter>,
317 by: By,
318 lazy: bool,
319 ) -> Result<(), Error> {
320 // UnityPy environment.py:252-264
321 let staged = self.prepare(name, kind, loads, path, meter, lazy, &mut false)?;
322 self.apply(staged, by)
323 }
324
325 /// The charged half of [`Self::insert`]: the key, the slot and, for a
326 /// key the registry does not hold now, its copy and its share of the
327 /// tables (the first key's with the B-tree's root, unless a registration
328 /// staged before it paid for that, `root`, which this one sets when it
329 /// pays), and the position's path. Every charge a registration makes is
330 /// made here, before anything is published: a refusal registers
331 /// nothing.
332 // The registration's parts, as `insert`'s, and the stage's root.
333 #[allow(clippy::too_many_arguments)]
334 fn prepare(
335 &self,
336 name: &RawStr,
337 kind: SlotKind,
338 loads: Loads,
339 path: &[usize],
340 meter: &Arc<Meter>,
341 lazy: bool,
342 root: &mut bool,
343 ) -> Result<Staged, Error> {
344 let lowered = simplify_name(name, meter)?;
345 let slot = Self::new_slot(kind, loads.value, path, lazy, meter)?;
346 // The position shares the value's path, which `first_charge` pays
347 // for while the key keeps it.
348 let position = Rank {
349 load: loads.position.min(loads.value),
350 path: slot.rank.path.clone(),
351 };
352 // This read and `apply`'s are two: the one before the charges asks
353 // whether the key is new, the one after them reads its value for
354 // the stand-in, with no lock held between (the price of charging a
355 // staged registration before any is published; `insert` pays it
356 // too, one more read lock per registration).
357 let (known, first) = {
358 let inner = self.read();
359 let known = inner.slots.contains_key(lowered.as_bytes());
360 (known, inner.order.is_empty() && !*root)
361 };
362 // A new key's own copy and its share of the tables, made before the
363 // lock: the key holds no input's buffer (module docs); the first key
364 // also pays for the B-tree's root. The share is charged before the
365 // copy. A key found here is found at the lock too, since no call
366 // removes one; a key not found here may be by then (another load's,
367 // or one this load staged before it), and its copy and share are
368 // then returned. A known key may move to this rank: its path is
369 // charged now and returned if it does not.
370 let (key, share) = if known {
371 (lowered, None)
372 } else {
373 let share = meter.charge(if first { SHARE + ORDER_LEAF } else { SHARE })?;
374 *root |= first;
375 (RawStr::charged(lowered.as_bytes(), meter)?, Some(share))
376 };
377 let first_charge = meter.charge(Rank::heap(path.len()))?;
378 Ok(Staged {
379 key,
380 position,
381 slot,
382 share,
383 first_charge,
384 })
385 }
386
387 /// The published half of [`Self::insert`], in which nothing can fail
388 /// the registration: whether the slot that stays stands in for the
389 /// one dropped, told with no lock held ([`Stand`]), then the change,
390 /// in one step under the write lock, then what it dropped released
391 /// and, for a load's, the listed slots reached ([`Self::settle`],
392 /// whose refusal leaves them listed for a later call and does not fail
393 /// the registration). Its one error is for a key found when the
394 /// registration was charged and gone at the lock, which nothing does:
395 /// no call removes a key.
396 fn apply(&self, staged: Staged, by: By) -> Result<(), Error> {
397 let Staged {
398 key,
399 position,
400 slot,
401 share,
402 first_charge,
403 } = staged;
404 let rank = slot.rank.clone();
405 let value = self
406 .read()
407 .slots
408 .get(key.as_bytes())
409 .map(|e| e.slot.clone());
410 let stand = value.as_ref().and_then(|v| Stand::of(&slot, v));
411 drop(value);
412 let hash = self.watches.hash(key.as_bytes());
413 let (dropped, changed, new_key) = {
414 let mut inner = self.write();
415 let RegistryInner {
416 order,
417 slots,
418 pending,
419 ..
420 } = &mut *inner;
421 let out = if let Some(e) = slots.get_mut(key.as_bytes()) {
422 let moves = position < e.first;
423 let charge = if moves {
424 if let Some(key) = order.remove(&e.first) {
425 order.insert(position.clone(), key);
426 }
427 e.first = position;
428 std::mem::replace(&mut e.first_charge, first_charge)
429 } else {
430 first_charge
431 };
432 let replaces = rank > e.slot.rank;
433 // Equal ranks are one entry registered again: nothing of it
434 // is dropped.
435 let distinct = rank != e.slot.rank;
436 let slot = if replaces {
437 std::mem::replace(&mut e.slot, slot)
438 } else {
439 slot
440 };
441 let listed = (distinct
442 && slot.unreached()
443 && !Self::stood_in(stand.as_ref(), &e.slot, &slot))
444 .then(|| {
445 let (_, steps) = pending.push(slot.clone());
446 self.store_lens(pending);
447 steps
448 });
449 let dropped = Dropped {
450 slot,
451 _charge: charge,
452 listed,
453 };
454 (Some(dropped), moves || replaces, false)
455 } else if let Some(share) = share {
456 order.insert(position.clone(), key.clone());
457 slots.reserve(1);
458 slots.insert(
459 key,
460 Entry {
461 slot,
462 first: position,
463 _share: share,
464 first_charge,
465 },
466 );
467 (None, true, true)
468 } else {
469 // The key went away between the charge and the lock: never,
470 // since nothing removes one; register it on the next call.
471 return Err(Error::Malformed {
472 what: "registry",
473 detail: "a key vanished".into(),
474 });
475 };
476 // The change, the setting of the walks' flags under its key and
477 // a load's new generation are one step (`super::watch`, W1).
478 // So are a load's listing of the slot it dropped, which changes
479 // no key, and a new generation: the reach that settles the slot
480 // registers its container's entries, which no pass marked built
481 // before this step has walked (plan section 3.16, P1; review
482 // round 16: a load ranked between the key's position and its
483 // value listed its slot with no new generation, so its
484 // container's tables were never walked).
485 if out.1 {
486 inner.publish(hash, by == By::Load);
487 } else if by == By::Load && out.0.as_ref().is_some_and(|d| d.listed.is_some()) {
488 inner.start_generation();
489 }
490 out
491 };
492 self.count_change(changed, new_key, by);
493 drop(stand);
494 self.release(dropped);
495 if by == By::Load {
496 // A refusal leaves it for the next call (`settle`).
497 self.settle().ok();
498 }
499 Ok(())
500 }
501
502 /// What a registration counts once its change is published: a load's
503 /// new key counts on this thread (`LOAD_KEYS_HERE`); a reach registers
504 /// what an eager load registered at load, before any container pass.
505 // `changed` is the test's hook's.
506 #[cfg_attr(not(test), allow(unused_variables, clippy::unused_self))]
507 fn count_change(&self, changed: bool, new_key: bool, by: By) {
508 #[cfg(test)]
509 if changed {
510 self.hook(Hook::Published);
511 }
512 if new_key && by == By::Load {
513 LOAD_KEYS_HERE.with(|c| c.set(c.get().saturating_add(1)));
514 }
515 }
516
517 /// Whether `standing`, the key's value after a registration, stands in
518 /// for `dropped`, the slot it dropped, as `stand` told before the lock
519 /// (plan section 9, Q14); under the write lock. When it does, the
520 /// standing slot takes the dropped one's position
521 /// ([`Slot::position`]), and the dropped slot is not listed. A standing
522 /// slot that is the new registration's own is not yet published, so no
523 /// reach can have closed its position; one that was already the key's
524 /// value may be reaching now, and stands in only while its position is
525 /// not closed ([`Slot::stand_for`]): a reach closes it only at the
526 /// position it registered at, so a lowering it meets first is
527 /// registered before the slot is marked reached, and a registration
528 /// that meets the close lists the dropped slot, reached as any other
529 /// drop (`reach.rs`'s module docs).
530 fn stood_in(stand: Option<&Stand>, standing: &Arc<Slot>, dropped: &Arc<Slot>) -> bool {
531 let Some(stand) = stand else {
532 return false;
533 };
534 if !(Arc::ptr_eq(&stand.standing, standing) && Arc::ptr_eq(&stand.dropped, dropped)) {
535 return false;
536 }
537 standing.stand_for(dropped.position())
538 }
539
540 /// Publishes the lists' lengths (under the write lock).
541 pub(super) fn store_lens(&self, pending: &pending::Pending) {
542 self.pending_len
543 .store(pending.len(pending::List::Listed), Ordering::Release);
544 self.evicted_len
545 .store(pending.len(pending::List::Evicted), Ordering::Release);
546 }
547
548 /// A slot of `kind` at rank `(load, path)`, charged to `meter` (its
549 /// `Arc`, its rank's path, and a lazy slot's share of the list of
550 /// dropped slots) before either is allocated.
551 fn new_slot(
552 kind: SlotKind,
553 load: u64,
554 path: &[usize],
555 lazy: bool,
556 meter: &Arc<Meter>,
557 ) -> Result<Arc<Slot>, Error> {
558 let mut charge = Charge::zero(meter);
559 charge.grow(SLOT_ARC)?;
560 charge.grow(Rank::heap(path.len()))?;
561 if lazy {
562 charge.grow(PENDING_SHARE)?;
563 }
564 // The path's `Arc` after its charge (CR1's review, round 1: it was
565 // allocated before it).
566 let rank = Rank {
567 load,
568 path: Arc::from(path),
569 };
570 Ok(Arc::new(Slot {
571 kind,
572 rank,
573 lazy,
574 reached: AtomicBool::new(false),
575 stands_for: AtomicU64::new(slot::NONE),
576 counted: AtomicBool::new(false),
577 walked: AtomicBool::new(false),
578 charge,
579 }))
580 }
581
582 /// Drops what a registration replaced or did not use (and its charges),
583 /// after the lock, and counts the steps a listing took as the dropped
584 /// slot's input's work (`pending.rs`). A lazy slot not yet reached was
585 /// listed with the change unless the key's value stands in for it; a
586 /// load's registration then reaches every listed slot before it
587 /// returns, and a reach's registrations leave theirs to the `settle`
588 /// that runs the reach (`reach.rs`).
589 // `self` runs the test's hook.
590 #[cfg_attr(not(test), allow(clippy::unused_self))]
591 fn release(&self, dropped: Option<Dropped>) {
592 if let Some(d) = &dropped
593 && let Some(steps) = d.listed
594 {
595 d.slot
596 .input_meter()
597 .add_work(steps.saturating_mul(pending::STEP));
598 #[cfg(test)]
599 self.hook(Hook::Deferred);
600 }
601 drop(dropped);
602 }
603}