Skip to main content

unityrs_testkit/
counted.rs

1//! The counting `#[global_allocator]` of the memory tests (plan section
2//! 7.3), and the thread it counts: only the thread under test.
3//!
4//! libtest runs a test on a thread of its own while its main thread goes on
5//! allocating (just after the spawn, and for its "has been running for over
6//! 60 seconds" notice), so an allocator that counts every thread reads such
7//! an allocation inside a measured window as the test's own, and a check
8//! with no slack fails now and then. The core starts no thread of its own
9//! ([`crate::waits`]), so the test's thread sees every allocation the core
10//! makes for it. A test's first line is [`count_this_thread`], then
11//! [`others_are_not_counted`] with the allocator's count.
12//!
13//! [`Allocator`] is every such allocator: a test file installs one with a
14//! [`Tally`] of its own, which says what a block that became live or was
15//! freed does to the file's counts. Only the allocator decides what
16//! happened: a block counts once `System` has made it, so a failed
17//! allocation or `realloc` counts nothing and the block a failed `realloc`
18//! leaves stays counted (review round 4: seven test files' copies counted
19//! the new block before `realloc` and freed the old one whatever it
20//! returned). [`stray_allocators`] finds a global allocator of another
21//! kind.
22//!
23//! Owner: package B.
24
25use std::alloc::{GlobalAlloc, Layout, System};
26use std::cell::Cell;
27use std::path::Path;
28use std::ptr;
29use std::sync::atomic::{AtomicU8, Ordering};
30
31std::thread_local! {
32    /// Whether this thread's allocations are counted.
33    static COUNTED: Cell<bool> = const { Cell::new(false) };
34}
35
36/// Whether the calling thread's allocations are counted. It allocates
37/// nothing, so a global allocator may ask it.
38#[must_use]
39#[inline]
40pub fn counted() -> bool {
41    COUNTED.try_with(Cell::get).unwrap_or(false)
42}
43
44/// Counts the calling thread's allocations from now on.
45pub fn count_this_thread() {
46    COUNTED.with(|c| c.set(true));
47}
48
49/// Stops counting the calling thread's allocations. A registered thread
50/// calls it before it ends: its exit's frees (its thread-locals'
51/// destructors, its handle) come after `thread::scope` has joined it, and
52/// counted they would land in whatever window a later test has armed.
53pub fn stop_counting_this_thread() {
54    COUNTED.with(|c| c.set(false));
55}
56
57/// Checks that an allocation on another thread does not move `live`, the
58/// allocator's count: a second thread allocates 64 KiB and holds it while
59/// the calling thread, which allocates nothing meanwhile, reads `live`
60/// before and after. Run it before the test takes any baseline: the second
61/// thread's start and end may leave a constant in the count (a block the
62/// calling thread allocated for it and the other thread freed).
63///
64/// # Panics
65///
66/// When the other thread's allocation was counted.
67pub fn others_are_not_counted(live: impl Fn() -> usize) {
68    // Barrier's first wait can box a pthread mutex/condvar on Darwin, on
69    // the counted thread and inside the before/during window. Atomics keep
70    // the probe itself allocation-free on both Darwin and Linux.
71    let step = AtomicU8::new(0);
72    std::thread::scope(|s| {
73        s.spawn(|| {
74            while step.load(Ordering::Acquire) != 1 {
75                std::thread::yield_now();
76            }
77            let block = std::hint::black_box(vec![1_u8; 1 << 16]);
78            step.store(2, Ordering::Release);
79            while step.load(Ordering::Acquire) != 3 {
80                std::thread::yield_now();
81            }
82            drop(block);
83        });
84        let before = live();
85        step.store(1, Ordering::Release);
86        while step.load(Ordering::Acquire) != 2 {
87            std::thread::yield_now();
88        }
89        let during = live();
90        step.store(3, Ordering::Release);
91        assert_eq!(
92            during, before,
93            "another thread's allocation moved the count"
94        );
95    });
96}
97
98/// What a test file counts of the blocks its [`Allocator`] sees. It is
99/// called inside the allocator, so it must not allocate, and it must not
100/// panic: a global allocator that unwinds is undefined behaviour
101/// (`GlobalAlloc`'s safety contract), so [`Allocator`] ends any unwind out
102/// of a tally's method by aborting the process (review round 6: a tally
103/// that panicked unwound through the allocator). A failed `assert!` or
104/// `unwrap` in a tally is therefore a `SIGABRT`, after the panic's
105/// message, and never a test failure that unwinds.
106pub trait Tally: Sync {
107    /// Whether a request of `size` bytes fails without reaching `System`,
108    /// on any thread (a test that refuses huge requests rather than meet the
109    /// machine's limit). Never, by default.
110    fn refuses(&self, size: usize) -> bool {
111        let _ = size;
112        false
113    }
114
115    /// Whether a `realloc` to `new_size` bytes fails without reaching
116    /// `System`: [`Self::refuses`], by default. A test that refuses one
117    /// fresh allocation of a size, and never a growth or shrink the code
118    /// under test makes infallibly, answers `false` here.
119    fn refuses_realloc(&self, new_size: usize) -> bool {
120        self.refuses(new_size)
121    }
122
123    /// A block of `size` bytes is about to be asked of `System` on a
124    /// counted thread (a fresh block, or a `realloc`'s new one): told before
125    /// it can be live, so a tally that counts here never holds less than the
126    /// live heap. Nothing, by default.
127    fn growing(&self, size: usize) {
128        let _ = size;
129    }
130
131    /// The request [`Self::growing`] told of failed: no block was made.
132    /// Nothing, by default.
133    fn failed(&self, size: usize) {
134        let _ = size;
135    }
136
137    /// A block of `size` bytes became live on a counted thread; `zeroed`
138    /// when `alloc_zeroed` made it.
139    fn grew(&self, size: usize, zeroed: bool);
140
141    /// A block of `size` bytes was freed on a counted thread: told once
142    /// `System` has freed it.
143    fn shrank(&self, size: usize);
144    /// Replace an old block after a successful in-place shrink. There was
145    /// no provisional new block; coherent tallies update in one event.
146    fn shrunk(&self, old: usize, new: usize) {
147        self.shrank(old);
148        self.grew(new, false);
149    }
150}
151
152/// A global allocator that forwards to `System` and tells its [`Tally`] of
153/// each block made or freed on a [`counted`] thread: of a request before
154/// `System` sees it ([`Tally::growing`], undone by [`Tally::failed`]), and
155/// of its block once `System` has answered: a failure counts nothing, and a `realloc` that fails leaves its
156/// old block live and counted. A growing `realloc` that succeeds counts its
157/// new block before it frees the old one, the worst case of a moving
158/// `realloc`: both blocks live at once. A shrinking one frees the old block
159/// first, since glibc shrinks in place, unless `System` allocates, copies
160/// and frees instead (an alignment over `malloc`'s, or a new size below the
161/// alignment), which counts as a growth does: the engine's allocator's
162/// rule (`unityrs_batch::alloc`). A tally that panics aborts the process
163/// ([`Tally`]). A test file installs it with its own tally:
164/// `#[global_allocator] static ALLOC: Allocator<Mine> = Allocator(Mine);`.
165pub struct Allocator<T>(pub T);
166
167/// `malloc`'s alignment, below which std's `System` calls `realloc` itself
168/// (`library/std/src/sys/alloc`'s `MIN_ALIGN`).
169const MIN_ALIGN: usize = if cfg!(target_pointer_width = "64") {
170    16
171} else {
172    8
173};
174
175/// Aborts the process when dropped: armed around each call into a
176/// [`Tally`] and disarmed (forgotten) when the call returns, so it drops
177/// only while a tally's panic unwinds, and the unwind ends there instead of
178/// leaving the allocator. `abort` neither allocates nor unwinds.
179struct NoUnwind;
180
181impl Drop for NoUnwind {
182    fn drop(&mut self) {
183        std::process::abort();
184    }
185}
186
187/// Runs `f`, a call into a tally, with no unwind out of it ([`NoUnwind`]).
188#[inline]
189fn no_unwind<R>(f: impl FnOnce() -> R) -> R {
190    let armed = NoUnwind;
191    let r = f();
192    std::mem::forget(armed);
193    r
194}
195
196impl<T: Tally> Allocator<T> {
197    /// Tells the tally of a request on a counted thread, before `System`
198    /// sees it; whether it told.
199    fn before(&self, size: usize) -> bool {
200        let tell = counted();
201        if tell {
202            no_unwind(|| self.0.growing(size));
203        }
204        tell
205    }
206
207    /// Tells the tally what `System` answered a request [`Self::before`]
208    /// told of.
209    fn after(&self, tell: bool, p: *mut u8, size: usize, zeroed: bool) -> *mut u8 {
210        if tell {
211            if p.is_null() {
212                no_unwind(|| self.0.failed(size));
213            } else {
214                no_unwind(|| self.0.grew(size, zeroed));
215            }
216        }
217        p
218    }
219}
220
221// SAFETY: every method forwards to `System` under the caller's contract,
222// which is `System`'s, and only tells the tally sizes, through `no_unwind`,
223// so no panic of the tally's unwinds out of a method; a refusal returns
224// null, which `GlobalAlloc` allows any allocation to.
225unsafe impl<T: Tally> GlobalAlloc for Allocator<T> {
226    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
227        if no_unwind(|| self.0.refuses(layout.size())) {
228            return ptr::null_mut();
229        }
230        let tell = self.before(layout.size());
231        // SAFETY: the caller's contract is `System.alloc`'s.
232        let p = unsafe { System.alloc(layout) };
233        self.after(tell, p, layout.size(), false)
234    }
235
236    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
237        if no_unwind(|| self.0.refuses(layout.size())) {
238            return ptr::null_mut();
239        }
240        let tell = self.before(layout.size());
241        // SAFETY: the caller's contract is `System.alloc_zeroed`'s.
242        let p = unsafe { System.alloc_zeroed(layout) };
243        self.after(tell, p, layout.size(), true)
244    }
245
246    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
247        // SAFETY: the caller's contract is `System.dealloc`'s: `ptr` came
248        // from this allocator, which is `System`'s.
249        unsafe { System.dealloc(ptr, layout) }
250        // Told once the block is gone, never while it is still live.
251        if counted() {
252            no_unwind(|| self.0.shrank(layout.size()));
253        }
254    }
255
256    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
257        if no_unwind(|| self.0.refuses_realloc(new_size)) {
258            return ptr::null_mut();
259        }
260        let in_place = layout.align() <= MIN_ALIGN && layout.align() <= new_size;
261        let shrinking = new_size <= layout.size() && in_place;
262        let tell = if shrinking {
263            counted()
264        } else {
265            self.before(new_size)
266        };
267        // SAFETY: the caller's contract is `System.realloc`'s.
268        let p = unsafe { System.realloc(ptr, layout, new_size) };
269        if tell && p.is_null() && !shrinking {
270            no_unwind(|| self.0.failed(new_size));
271        }
272        if !p.is_null() && tell {
273            no_unwind(|| {
274                // `System` calls `realloc` itself only for an alignment of
275                // at most `malloc`'s and no greater than the new size;
276                // otherwise it allocates, copies and frees (std's
277                // `realloc_fallback`), both blocks live: as the engine's
278                // allocator counts it (`unityrs_batch::alloc`).
279                if shrinking {
280                    // glibc shrinks a block where it is (a heap chunk split
281                    // in place, a mapped one cut by `mremap`): no second
282                    // block ever exists (plan section 3.15, perf stage 2).
283                    self.0.shrunk(layout.size(), new_size);
284                } else {
285                    // A growth may move: both blocks exist until it is done.
286                    self.0.grew(new_size, false);
287                    self.0.shrank(layout.size());
288                }
289            });
290        }
291        p
292    }
293}
294
295/// Every `file:line` of a `.rs` file under `root` (`target` directories
296/// left out) that implements `GlobalAlloc` itself, outside this module:
297/// a counting allocator of its own, whose accounting no test here checks.
298/// The engine's (`unityrs_batch::alloc`, the binary's) is the one other,
299/// its accounting held by its own tests, and its file is left out for that
300/// one implementation only: a count there other than one is reported as
301/// `<file>: <n> implementations, the exemption is for one`.
302/// Comment lines are not scanned.
303///
304/// # Panics
305/// When `root` cannot be read (a test helper).
306#[must_use]
307pub fn stray_allocators(root: &Path) -> Vec<String> {
308    let mut files = Vec::new();
309    crate::guard::rust_files(root, &mut files);
310    files.sort();
311    let mut found = Vec::new();
312    for path in files {
313        let text =
314            std::fs::read_to_string(&path).unwrap_or_else(|e| panic!("{}: {e}", path.display()));
315        let hits: Vec<String> = text
316            .lines()
317            .enumerate()
318            .filter(|(_, line)| {
319                !line.trim_start().starts_with("//") && line.contains("GlobalAlloc for")
320            })
321            .map(|(i, _)| format!("{}:{}", path.display(), i + 1))
322            .collect();
323        // This module, whose scan names the pattern itself.
324        if path.ends_with("unityrs-testkit/src/counted.rs") {
325            continue;
326        }
327        // The engine's counting allocator, which its own tests check
328        // (`unityrs-batch`'s `tests/alloc.rs`): that one, and no other.
329        if path.ends_with("unityrs-batch/src/alloc.rs") {
330            if hits.len() != 1 {
331                found.push(crate::guard::exemption_broken(
332                    &path,
333                    hits.len(),
334                    "implementations",
335                ));
336            }
337            continue;
338        }
339        found.extend(hits);
340    }
341    found
342}
343
344#[cfg(test)]
345mod tests {
346    use std::alloc::{GlobalAlloc, Layout, System};
347    use std::hint::black_box;
348    use std::sync::Mutex;
349
350    use super::{Allocator, Tally, count_this_thread, stray_allocators};
351
352    /// Every call, in order: `(+size)` grew, `(-size)` shrank.
353    struct Log(Mutex<Vec<i64>>);
354
355    impl Tally for Log {
356        fn refuses(&self, size: usize) -> bool {
357            size == 12_345
358        }
359        fn grew(&self, size: usize, _zeroed: bool) {
360            self.0.lock().unwrap().push(i64::try_from(size).unwrap());
361        }
362        fn shrank(&self, size: usize) {
363            self.0.lock().unwrap().push(-i64::try_from(size).unwrap());
364        }
365    }
366
367    impl Log {
368        fn take(&self) -> Vec<i64> {
369            std::mem::take(&mut *self.0.lock().unwrap())
370        }
371    }
372
373    /// No request `System` can meet: a `realloc` to it fails and returns null.
374    const HUGE: usize = usize::MAX / 4;
375
376    #[test]
377    fn a_shrink_below_alignment_counts_both_live_blocks() {
378        count_this_thread();
379        let a = Allocator(Log(Mutex::new(Vec::new())));
380        // Alignment no greater than malloc's: only the new size forces
381        // System's allocate/copy/free fallback.
382        let layout = Layout::from_size_align(64, super::MIN_ALIGN).unwrap();
383        let small = Layout::from_size_align(1, layout.align()).unwrap();
384        // SAFETY: non-zero layouts; the live pointer is used with its
385        // current layout, retains its first byte, and is freed once.
386        unsafe {
387            let p = a.alloc(layout);
388            assert!(!p.is_null());
389            p.write(42);
390            let q = a.realloc(p, layout, small.size());
391            assert!(!q.is_null());
392            assert_eq!(q.read(), 42);
393            a.dealloc(q, small);
394        }
395        assert_eq!(a.0.take(), [64, 1, -64, -1]);
396    }
397
398    #[test]
399    fn an_exempt_allocator_with_two_implementations_is_reported() {
400        let dir = crate::scratch::Scratch::new("allocator-exemption");
401        let file = dir.join("unityrs-batch/src/alloc.rs");
402        std::fs::create_dir_all(file.parent().unwrap()).unwrap();
403        std::fs::write(
404            &file,
405            "impl GlobalAlloc for A {}\nimpl GlobalAlloc for B {}\n",
406        )
407        .unwrap();
408        assert_eq!(
409            stray_allocators(dir.path()),
410            [format!(
411                "{}: 2 implementations, the exemption is for one",
412                file.display()
413            )]
414        );
415    }
416
417    /// A `realloc` that fails counts nothing: its old block stays live and
418    /// counted (review round 4: the copies counted the new block, then freed
419    /// the old one whatever `realloc` returned). One that succeeds counts
420    /// the new block before freeing the old. Each huge request's result goes
421    /// through `black_box` before its null check: unused, an optimised build
422    /// removes the request and folds the check (review round 6: the test
423    /// failed every time under `cargo test --release`).
424    #[test]
425    fn a_failed_realloc_keeps_the_old_block_counted() {
426        count_this_thread();
427        // Not the global allocator: the test's own, with a log of its own.
428        let a = Allocator(Log(Mutex::new(Vec::new())));
429        let layout = Layout::from_size_align(64, 8).unwrap();
430        // SAFETY: a non-zero layout; each pointer is used under the layout
431        // it was made with, and freed once.
432        unsafe {
433            let p = a.alloc(layout);
434            assert!(!p.is_null());
435            assert_eq!(a.0.take(), [64]);
436            let q = black_box(a.realloc(p, layout, HUGE));
437            assert!(q.is_null(), "System met a request of {HUGE} bytes");
438            assert!(a.0.take().is_empty(), "a failed realloc moved the count");
439            let q = a.realloc(p, layout, 4096);
440            assert!(!q.is_null());
441            assert_eq!(
442                a.0.take(),
443                [4096, -64],
444                "the new block before the old is freed"
445            );
446            let big = Layout::from_size_align(4096, 8).unwrap();
447            assert!(a.realloc(q, big, 12_345).is_null(), "a refusal");
448            assert!(
449                a.alloc(Layout::from_size_align(12_345, 8).unwrap())
450                    .is_null()
451            );
452            assert!(a.0.take().is_empty(), "a refusal counted");
453            a.dealloc(q, big);
454            assert_eq!(a.0.take(), [-4096]);
455            let z = a.alloc_zeroed(layout);
456            assert!(!z.is_null() && *z == 0);
457            a.dealloc(z, layout);
458            assert_eq!(a.0.take(), [64, -64]);
459            // A thread that is not counted tells the tally nothing.
460            std::thread::scope(|s| {
461                s.spawn(|| {
462                    let p = a.alloc(layout);
463                    a.dealloc(p, layout);
464                });
465            });
466            assert!(a.0.take().is_empty(), "another thread counted");
467            // `System` itself, for contrast: the huge request fails there.
468            assert!(black_box(System.alloc(Layout::from_size_align(HUGE, 8).unwrap())).is_null());
469        }
470    }
471
472    /// Panics in every method, as a tally with a failing `assert!` would.
473    struct Panicking;
474
475    impl Tally for Panicking {
476        fn grew(&self, _: usize, _: bool) {
477            panic!("the tally's own panic");
478        }
479        fn shrank(&self, _: usize) {
480            panic!("the tally's own panic");
481        }
482    }
483
484    const UNWIND_VAR: &str = "UNITYRS_TESTKIT_TALLY_PANIC";
485
486    /// Run by [`a_tally_that_panics_aborts_and_never_unwinds`] in a child:
487    /// a counted allocation whose tally panics, under `catch_unwind`. Were
488    /// the panic to unwind out of the allocator, `catch_unwind` would catch
489    /// it and the probe would pass. `killed:N:DIR` is first killed by
490    /// `SIGKILL` from outside on each of its first `N` runs
491    /// (`crate::child::kill_self_while`).
492    #[test]
493    #[ignore = "run by a_tally_that_panics_aborts_and_never_unwinds"]
494    fn tally_panic_probe() {
495        let Ok(what) = std::env::var(UNWIND_VAR) else {
496            return;
497        };
498        if let Some(spec) = what.strip_prefix("killed:") {
499            crate::child::kill_self_while(spec);
500        }
501        count_this_thread();
502        let a = Allocator(Panicking);
503        let layout = Layout::from_size_align(64, 8).unwrap();
504        let unwound = std::panic::catch_unwind(|| {
505            // SAFETY: a non-zero layout. The block leaks if the call returns.
506            black_box(unsafe { a.alloc(layout) });
507        });
508        assert!(unwound.is_ok(), "the tally's panic unwound out of alloc");
509    }
510
511    /// A tally that panics ends the process with `SIGABRT` after its
512    /// panic's message: no unwind leaves the allocator, which `GlobalAlloc`
513    /// forbids (review round 6). The probe runs in a child process, since
514    /// it aborts; a `SIGKILL` from outside is run again
515    /// ([`crate::child::output`]), and the probe's own abort comes back at
516    /// once (review round 8: one kill failed the test).
517    #[cfg(unix)]
518    #[test]
519    fn a_tally_that_panics_aborts_and_never_unwinds() {
520        let marks = crate::child::Marks::new("tally-panic-once");
521        for (spec, killed) in [
522            ("1".to_owned(), 0),
523            (format!("killed:{}", marks.killed(1)), 1),
524        ] {
525            tally_panic_aborts(&spec);
526            assert_eq!(marks.runs(), killed, "{spec}");
527        }
528    }
529
530    /// The tally-panic probe, run with `spec`, aborts after its panic.
531    #[cfg(unix)]
532    fn tally_panic_aborts(spec: &str) {
533        use std::os::unix::process::ExitStatusExt;
534        let exe = std::env::current_exe().unwrap();
535        let out = crate::child::output(
536            std::process::Command::new(exe)
537                .args([
538                    "--exact",
539                    "counted::tests::tally_panic_probe",
540                    "--ignored",
541                    "--test-threads=1",
542                    "--nocapture",
543                ])
544                .env(UNWIND_VAR, spec),
545        )
546        .unwrap();
547        let err = String::from_utf8_lossy(&out.stderr);
548        assert_eq!(
549            out.status.signal(),
550            Some(6),
551            "{spec}: the probe did not abort: {:?}\n{err}",
552            out.status
553        );
554        assert!(err.contains("the tally's own panic"), "{spec}: {err}");
555        assert!(
556            !err.contains("panic in a function that cannot unwind"),
557            "{spec}: std's nounwind abort reached instead of our guard: {err}"
558        );
559    }
560
561    /// Refuses a fresh allocation of 12,345 bytes, never a `realloc`.
562    struct FreshOnly(Log);
563
564    impl Tally for FreshOnly {
565        fn refuses(&self, size: usize) -> bool {
566            self.0.refuses(size)
567        }
568        fn refuses_realloc(&self, _new_size: usize) -> bool {
569            false
570        }
571        fn grew(&self, size: usize, zeroed: bool) {
572            self.0.grew(size, zeroed);
573        }
574        fn shrank(&self, size: usize) {
575            self.0.shrank(size);
576        }
577    }
578
579    /// A tally that refuses a fresh allocation may let a `realloc` to the
580    /// same size by (the dump's staging test: the code under test shrinks
581    /// into exact allocations infallibly); by default it refuses both
582    /// (`a_failed_realloc_keeps_the_old_block_counted`).
583    #[test]
584    fn a_tally_may_refuse_fresh_allocations_and_no_realloc() {
585        count_this_thread();
586        let a = Allocator(FreshOnly(Log(Mutex::new(Vec::new()))));
587        let layout = Layout::from_size_align(64, 8).unwrap();
588        let refused = Layout::from_size_align(12_345, 8).unwrap();
589        // SAFETY: non-zero layouts; each pointer is used under the layout
590        // it was made with, and freed once.
591        unsafe {
592            assert!(a.alloc(refused).is_null());
593            assert!(a.alloc_zeroed(refused).is_null());
594            let p = a.alloc(layout);
595            assert!(!p.is_null());
596            let q = a.realloc(p, layout, 12_345);
597            assert!(!q.is_null(), "a realloc refused");
598            a.dealloc(q, refused);
599            assert_eq!(a.0.0.take(), [64, 12_345, -64, -12_345]);
600        }
601    }
602
603    /// Every global allocator in the workspace is an [`Allocator`] or the
604    /// engine's counting allocator (`unityrs_batch::alloc`).
605    #[test]
606    fn every_global_allocator_in_the_workspace_is_this_one() {
607        let crates = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("..");
608        let found = stray_allocators(&crates);
609        assert!(
610            found.is_empty(),
611            "global allocators of their own, whose counts no test checks:\n{}",
612            found.join("\n")
613        );
614    }
615}