Skip to main content

unityrs_testkit/
ledger.rs

1//! One coherent, allocation-free observation of a counted engine's heap
2//! and its held charges (`docs/plans/extract.md` X12, X13). The engine's
3//! counting allocator and official thread-registration/account hooks feed
4//! this test-only ledger (`docs/plans/batch.md` 2.11's `tally` row).
5//!
6//! - **Registration** is [`crate::counted::count_this_thread`]: a test
7//!   registers each engine thread before its measured work (Tokio's
8//!   `on_thread_start` takes it as is); a thread never registered, the test
9//!   runner's or a peer's, is never counted.
10//! - **The heap** is the aggregate of every registered thread, one sum, so
11//!   a block made on one thread and freed on another balances; no thread's
12//!   signed count is read as what it owns.
13//! - **Conservative**: a block counts from before `System` is asked for it
14//!   until after `System` has freed it ([`crate::counted::Tally::growing`],
15//!   [`crate::counted::Tally::shrank`]), so between two events the ledger
16//!   never holds less than the registered threads' live heap, however
17//!   their allocations interleave: what the lock orders is the count, and
18//!   the count brackets each real transition.
19//! - **Charges** are told to the same ledger ([`Ledger::charge`],
20//!   [`Ledger::release`]): what a budget holds, never a reservation's
21//!   unused part or a cap.
22//!
23//! Every event, a block or a charge, goes through one short critical
24//! section, so each event sees the heap and the charges as one state, in
25//! one total order: the residual it records, the heap's rise since
26//! [`Ledger::arm`] less the charges' rise, is of one instant, never two
27//! peaks read at different times. The critical section
28//! is a spin on an atomic flag, which allocates nothing and cannot fail;
29//! no event formats, allocates or panics, so a global allocator may call
30//! it ([`crate::counted::Tally`]). Each event is an observation: a
31//! residual past [`Ledger::arm`]'s uncharged allowance is a violation, the
32//! first one kept with its event number.
33
34use std::hint::spin_loop;
35use std::sync::atomic::{AtomicBool, AtomicI64, AtomicU64, Ordering};
36
37use crate::counted::Tally;
38
39/// No violation yet.
40const NONE: u64 = u64::MAX;
41
42/// The aggregate heap and charges of the registered threads, observed at
43/// each event. `cost` is the charge unit of a block's size (the core's
44/// `heap_cost`, which the testkit does not link): a test passes it.
45pub struct Ledger {
46    cost: fn(u64) -> u64,
47    busy: AtomicBool,
48    heap: AtomicI64,
49    charged: AtomicI64,
50    allowance: AtomicU64,
51    events: AtomicU64,
52    base: AtomicI64,
53    base_charged: AtomicI64,
54    peak: AtomicI64,
55    max_residual: AtomicI64,
56    max_at: AtomicU64,
57    first_at: AtomicU64,
58    first_heap: AtomicI64,
59    first_charged: AtomicI64,
60}
61
62/// One event's view of the ledger, or a reading of it: one state.
63#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
64pub struct Observation {
65    /// Events since the last [`Ledger::arm`].
66    pub events: u64,
67    /// The registered threads' live heap, in the charge unit.
68    pub heap: i64,
69    /// The charges held.
70    pub charged: i64,
71    /// The most `heap` has been since the arm, above its value there.
72    pub peak_above_arm: i64,
73    /// The most any event since the arm saw of the residual: the heap's
74    /// rise since the arm less the charges' rise (0 at the arm).
75    pub max_residual: i64,
76    /// The event that saw [`Self::max_residual`] (0: the arm itself).
77    pub max_at: u64,
78    /// The first event whose residual passed the allowance.
79    pub first_violation: Option<Violation>,
80}
81
82/// An event whose heap passed its charges plus the allowance.
83#[derive(Clone, Copy, Debug, PartialEq, Eq)]
84pub struct Violation {
85    /// The event's number since the arm.
86    pub event: u64,
87    /// The heap it saw.
88    pub heap: i64,
89    /// The charges it saw.
90    pub charged: i64,
91}
92
93/// Holds the ledger's critical section; dropped, it lets the next event in.
94struct Held<'a>(&'a AtomicBool);
95
96impl Drop for Held<'_> {
97    fn drop(&mut self) {
98        self.0.store(false, Ordering::Release);
99    }
100}
101
102fn signed(n: u64) -> i64 {
103    i64::try_from(n).unwrap_or(i64::MAX)
104}
105
106impl Ledger {
107    /// An empty ledger whose blocks cost `cost(size)`.
108    #[must_use]
109    pub const fn new(cost: fn(u64) -> u64) -> Self {
110        Self {
111            cost,
112            busy: AtomicBool::new(false),
113            heap: AtomicI64::new(0),
114            charged: AtomicI64::new(0),
115            allowance: AtomicU64::new(0),
116            events: AtomicU64::new(0),
117            base: AtomicI64::new(0),
118            base_charged: AtomicI64::new(0),
119            peak: AtomicI64::new(0),
120            max_residual: AtomicI64::new(0),
121            max_at: AtomicU64::new(0),
122            first_at: AtomicU64::new(NONE),
123            first_heap: AtomicI64::new(0),
124            first_charged: AtomicI64::new(0),
125        }
126    }
127
128    /// Takes the critical section: a short spin, then the CPU given up
129    /// between tries (`sched_yield`, which allocates nothing), so a holder
130    /// preempted on a host with fewer cores than registered threads runs
131    /// again at once instead of after every spinner's time slice.
132    fn hold(&self) -> Held<'_> {
133        let mut tries = 0_u32;
134        while self
135            .busy
136            .compare_exchange_weak(false, true, Ordering::Acquire, Ordering::Relaxed)
137            .is_err()
138        {
139            tries = tries.saturating_add(1);
140            if tries < 64 {
141                spin_loop();
142            } else {
143                std::thread::yield_now();
144            }
145        }
146        Held(&self.busy)
147    }
148
149    /// Starts a measured window: from now each event's residual, the heap's
150    /// rise since now less the charges', is held against `allowance`, the
151    /// uncharged bytes the window may hold, and the peaks and the first
152    /// violation start again. The live heap and charges are not reset.
153    /// Returns the coherent `(heap, charged)` at the arm for phase-local
154    /// absolute residual comparisons.
155    pub fn arm(&self, allowance: u64) -> (i64, i64) {
156        let _held = self.hold();
157        let heap = self.heap.load(Ordering::Relaxed);
158        let charged = self.charged.load(Ordering::Relaxed);
159        self.allowance.store(allowance, Ordering::Relaxed);
160        self.events.store(0, Ordering::Relaxed);
161        self.base.store(heap, Ordering::Relaxed);
162        self.base_charged.store(charged, Ordering::Relaxed);
163        self.peak.store(heap, Ordering::Relaxed);
164        self.max_residual.store(0, Ordering::Relaxed);
165        self.max_at.store(0, Ordering::Relaxed);
166        self.first_at.store(NONE, Ordering::Relaxed);
167        (heap, charged)
168    }
169
170    /// One event: `heap` and `charged` move by the deltas, and the state
171    /// after them is observed.
172    fn event(&self, heap: i64, charged: i64) {
173        let _held = self.hold();
174        let h = self.heap.load(Ordering::Relaxed).saturating_add(heap);
175        let c = self.charged.load(Ordering::Relaxed).saturating_add(charged);
176        self.heap.store(h, Ordering::Relaxed);
177        self.charged.store(c, Ordering::Relaxed);
178        let n = self.events.load(Ordering::Relaxed).saturating_add(1);
179        self.events.store(n, Ordering::Relaxed);
180        if h > self.peak.load(Ordering::Relaxed) {
181            self.peak.store(h, Ordering::Relaxed);
182        }
183        let residual = h
184            .saturating_sub(self.base.load(Ordering::Relaxed))
185            .saturating_sub(c.saturating_sub(self.base_charged.load(Ordering::Relaxed)));
186        if residual > self.max_residual.load(Ordering::Relaxed) {
187            self.max_residual.store(residual, Ordering::Relaxed);
188            self.max_at.store(n, Ordering::Relaxed);
189        }
190        let allowance = signed(self.allowance.load(Ordering::Relaxed));
191        if residual > allowance && self.first_at.load(Ordering::Relaxed) == NONE {
192            self.first_at.store(n, Ordering::Relaxed);
193            self.first_heap.store(h, Ordering::Relaxed);
194            self.first_charged.store(c, Ordering::Relaxed);
195        }
196    }
197
198    /// A budget granted `bytes`: held from this event on.
199    pub fn charge(&self, bytes: u64) {
200        self.event(0, signed(bytes));
201    }
202
203    /// A held charge of `bytes` was returned.
204    pub fn release(&self, bytes: u64) {
205        self.event(0, signed(bytes).saturating_neg());
206    }
207
208    /// The state now, read inside the critical section: one instant.
209    #[must_use]
210    pub fn observe(&self) -> Observation {
211        let _held = self.hold();
212        let first_at = self.first_at.load(Ordering::Relaxed);
213        Observation {
214            events: self.events.load(Ordering::Relaxed),
215            heap: self.heap.load(Ordering::Relaxed),
216            charged: self.charged.load(Ordering::Relaxed),
217            peak_above_arm: self
218                .peak
219                .load(Ordering::Relaxed)
220                .saturating_sub(self.base.load(Ordering::Relaxed)),
221            max_residual: self.max_residual.load(Ordering::Relaxed),
222            max_at: self.max_at.load(Ordering::Relaxed),
223            first_violation: (first_at != NONE).then(|| Violation {
224                event: first_at,
225                heap: self.first_heap.load(Ordering::Relaxed),
226                charged: self.first_charged.load(Ordering::Relaxed),
227            }),
228        }
229    }
230}
231
232/// Counted conservatively: a block is counted before `System` is asked for
233/// it and uncounted once `System` has freed it, so the ledger's heap is
234/// never below the live heap, whatever the threads' interleaving; a
235/// moving `realloc` counts its new block before the call and drops its old
236/// one after success; a failed request is rolled back. A nonmoving shrink
237/// holds the old cost through the call, then replaces it in one event.
238impl Tally for Ledger {
239    fn shrunk(&self, old: usize, new: usize) {
240        self.event(
241            signed((self.cost)(new as u64)).saturating_sub(signed((self.cost)(old as u64))),
242            0,
243        );
244    }
245    fn growing(&self, size: usize) {
246        self.event(signed((self.cost)(size as u64)), 0);
247    }
248
249    fn failed(&self, size: usize) {
250        self.event(signed((self.cost)(size as u64)).saturating_neg(), 0);
251    }
252
253    /// Counted already, by [`Self::growing`].
254    fn grew(&self, _size: usize, _zeroed: bool) {}
255
256    fn shrank(&self, size: usize) {
257        self.event(signed((self.cost)(size as u64)).saturating_neg(), 0);
258    }
259}
260
261#[cfg(test)]
262mod tests {
263    use super::{Ledger, Violation};
264    use crate::counted::Tally;
265
266    fn bytes(n: u64) -> u64 {
267        n
268    }
269
270    #[test]
271    fn a_charge_before_its_block_and_a_release_after_its_free_never_pass() {
272        let l = Ledger::new(bytes);
273        l.arm(0);
274        l.charge(64);
275        l.growing(64);
276        l.shrank(64);
277        l.release(64);
278        let o = l.observe();
279        assert_eq!(o.events, 4);
280        assert_eq!((o.heap, o.charged), (0, 0));
281        assert_eq!(o.peak_above_arm, 64);
282        assert_eq!(o.max_residual, 0);
283        assert_eq!(o.first_violation, None);
284    }
285
286    /// A block made before its charge is an uncharged instant: the first
287    /// violation is kept, a later one does not replace it.
288    #[test]
289    fn an_allocation_before_its_reservation_is_the_first_violation() {
290        let l = Ledger::new(bytes);
291        l.arm(16);
292        l.growing(64);
293        l.charge(64);
294        l.growing(32);
295        let o = l.observe();
296        assert_eq!(
297            o.first_violation,
298            Some(Violation {
299                event: 1,
300                heap: 64,
301                charged: 0
302            })
303        );
304        assert_eq!((o.max_residual, o.max_at), (64, 1));
305        l.arm(64);
306        assert_eq!(l.observe().first_violation, None, "the arm starts again");
307        assert_eq!(l.observe().heap, 96, "the live heap is not reset");
308    }
309
310    #[test]
311    fn the_cost_is_the_given_unit() {
312        let l = Ledger::new(|n| n.div_ceil(16) * 16 + 16);
313        l.growing(1);
314        assert_eq!(l.observe().heap, 32);
315        l.shrank(1);
316        assert_eq!(l.observe().heap, 0);
317    }
318}