Skip to main content

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}