Small testing notes

[jamesmunns]

Hey there, thanks for sharing talc! I'm looking at potentially using it for mnemos, which currently uses linked-list-allocator.

I wanted to see how it fared in miri, and first ran into the problem that the benchmarks use an x86_64 asm call, which didn't build on my aarch64 mac:

error[E0433]: failed to resolve: could not find `x86_64` in `arch`
  --> examples/simple_chunk_allocator_bench.rs:90:45
   |
90 |     let mut now_fn = || unsafe { std::arch::x86_64::__rdtscp(std::ptr::addr_of_mut!(x)) };
   |                                             ^^^^^^ could not find `x86_64` in `arch`

I removed that file, and ran cargo +nightly miri test, and hit some errors pretty quickly:

     Running unittests src/lib.rs (target/miri/aarch64-apple-darwin/debug/deps/talc-3f2d44bc7b7dff89)

running 3 tests
test llist::tests::dostuff ... warning: integer-to-pointer cast
   --> src/llist.rs:38:30
    |
38  |         debug_assert!(node > 0x1000 as _);
    |                              ^^^^^^^^^^^ integer-to-pointer cast
    |
    = help: This program is using integer-to-pointer casts or (equivalently) `ptr::from_exposed_addr`,
    = help: which means that Miri might miss pointer bugs in this program.
    = help: See https://doc.rust-lang.org/nightly/std/ptr/fn.from_exposed_addr.html for more details on that operation.
    = help: To ensure that Miri does not miss bugs in your program, use Strict Provenance APIs (https://doc.rust-lang.org/nightly/std/ptr/index.html#strict-provenance, https://crates.io/crates/sptr) instead.
    = help: You can then pass the `-Zmiri-strict-provenance` flag to Miri, to ensure you are not relying on `from_exposed_addr` semantics.
    = help: Alternatively, the `-Zmiri-permissive-provenance` flag disables this warning.
    = note: BACKTRACE:
    = note: inside `llist::LlistNode::insert` at src/llist.rs:38:30: 38:41
note: inside `llist::tests::dostuff`
   --> src/llist.rs:135:13
    |
135 |             LlistNode::insert(&mut y, LlistNode::next_ptr(&mut x), None);
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure
   --> src/llist.rs:129:18
    |
128 |     #[test]
    |     ------- in this procedural macro expansion
129 |     fn dostuff() {
    |                  ^
    = note: this warning originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: integer-to-pointer cast
   --> src/llist.rs:39:38
    |
39  |         debug_assert!(next_of_prev > 0x1000 as _);
    |                                      ^^^^^^^^^^^ integer-to-pointer cast
    |
    = note: inside `llist::LlistNode::insert` at src/llist.rs:39:38: 39:49
note: inside `llist::tests::dostuff`
   --> src/llist.rs:135:13
    |
135 |             LlistNode::insert(&mut y, LlistNode::next_ptr(&mut x), None);
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure
   --> src/llist.rs:129:18
    |
128 |     #[test]
    |     ------- in this procedural macro expansion
129 |     fn dostuff() {
    |                  ^
    = note: this warning originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: integer-to-pointer cast
   --> src/llist.rs:57:30
    |
57  |         debug_assert!(node > 0x1000 as _);
    |                              ^^^^^^^^^^^ integer-to-pointer cast
    |
    = note: inside `llist::LlistNode::remove` at src/llist.rs:57:30: 57:41
note: inside `llist::tests::dostuff`
   --> src/llist.rs:148:13
    |
148 |             LlistNode::remove(&mut z);
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure
   --> src/llist.rs:129:18
    |
128 |     #[test]
    |     ------- in this procedural macro expansion
129 |     fn dostuff() {
    |                  ^
    = note: this warning originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: integer-to-pointer cast
   --> src/llist.rs:60:38
    |
60  |         debug_assert!(next_of_prev > 0x1000 as _);
    |                                      ^^^^^^^^^^^ integer-to-pointer cast
    |
    = note: inside `llist::LlistNode::remove` at src/llist.rs:60:38: 60:49
note: inside `llist::tests::dostuff`
   --> src/llist.rs:148:13
    |
148 |             LlistNode::remove(&mut z);
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure
   --> src/llist.rs:129:18
    |
128 |     #[test]
    |     ------- in this procedural macro expansion
129 |     fn dostuff() {
    |                  ^
    = note: this warning originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

error: Undefined Behavior: attempting a write access using <95150> at alloc30170[0x0], but that tag does not exist in the borrow stack for this location
   --> src/llist.rs:61:9
    |
61  |         *next_of_prev = next;
    |         ^^^^^^^^^^^^^^^^^^^^
    |         |
    |         attempting a write access using <95150> at alloc30170[0x0], but that tag does not exist in the borrow stack for this location
    |         this error occurs as part of an access at alloc30170[0x0..0x8]
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
    = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <95150> was created by a SharedReadWrite retag at offsets [0x0..0x10]
   --> src/llist.rs:136:59
    |
136 |             LlistNode::insert(&mut z, LlistNode::next_ptr(&mut x), Some(NonNull::from(&mut y)));
    |                                                           ^^^^^^
help: <95150> was later invalidated at offsets [0x0..0x10] by a Unique retag
   --> src/llist.rs:138:67
    |
138 |             let mut iter = LlistNode::iter_mut(Some(NonNull::from(&mut x)));
    |                                                                   ^^^^^^
    = note: BACKTRACE (of the first span):
    = note: inside `llist::LlistNode::remove` at src/llist.rs:61:9: 61:29
note: inside `llist::tests::dostuff`
   --> src/llist.rs:148:13
    |
148 |             LlistNode::remove(&mut z);
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure
   --> src/llist.rs:129:18
    |
128 |     #[test]
    |     ------- in this procedural macro expansion
129 |     fn dostuff() {
    |                  ^
    = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

I'll take a look at this later this weekend, I also helped linked-list-allocator to build cleanly with miri tests (issue: rust-osdev/linked-list-allocator#61, pr: rust-osdev/linked-list-allocator#62) and would be interested in helping if you're open to it!

[SFBdragon]

Thanks for opening an issue, I'll see what I can do!

I'll add some conditional compilation stuff to the benchmark (ideally I'll implement a similar high-resolution timing mechanism for other architectures).

As for being stacked borrows compliant, this sounds great. I'm on the road today and will need to read up on the specifics of miri tests and stacked borrows though.

At a glance, these errors and warning should be resolvable quite easily. Although I imagine these are far from the only violations.

Appreciate for the offer to help, although I'll save any questions until I feel like I better understand the scope of what needs to be done.

[SFBdragon]

Could you try using this function and let me know if it's giving you sensible results on your machine?

    let now_fn = || unsafe {
        if cfg!(target_arch = "x86_64") {
            let mut x = 0u32;
            std::arch::x86_64::__rdtscp(&mut x)
        } else if cfg!(target_arch = "aarch64") {
            let cntvct_el0: u64;
            std::arch::asm!("mrs {0}, CNTVCT_EL0", out(reg) cntvct_el0, options(nomem, nostack));
            cntvct_el0
        } else {
            panic!("Hardware-based counter is not implemented for this architecture. Supported: x86_64, aarch64");
        }
    };

Call it on either side of some set of operations or drop it into the benchmark and check if the results make sense, roughly speaking, compared to the benchmarks on x86_64. Thanks!

In other news, I've got miri happy with the existing and new Talc tests.

Some caveats though:

• miri is thoroughly dismayed that Talc is violating stacked borrows when used as a global_allocator upon attempting to free memory. I'm not sure if this is an artifact of my setup or how global_allocator works. See below.
• If any references to the arena get touched in between allocation operations miri complains. The Span type makes this rather easy to do if you aren't being careful enough (such as Span::from(arena.as_mut_ptr_range()), as_mut_ptr_range takes an &mut arena so miri complains).

I'm assuming that anyone who wants to test their code using miri will have to be extra careful anyway, but I don't know what's up with the global_allocator thing yet which bugs me. All I know is that if I take away the #[global_allocator] proc macro it works fine, as follows:

This is fine:

#![feature(allocator_api)]

use talc::*;

static ALLOCATOR: Talck<spin::Mutex<()>> = Talc::with_oom_handler(oom_handler).lock();
static mut ARENA: [u8; 10000] = [0; 10000];

fn oom_handler(talc: &mut Talc, _: core::alloc::Layout) -> Result<(), ()> {
    let arena_span = Span::from(unsafe { core::ptr::addr_of_mut!(ARENA) });
    
    if talc.get_arena() == arena_span {
        Err(())
    } else {
        unsafe {
            talc.init(arena_span);
        }
        
        Ok(())
    }
}

fn main() {
    let mut vec = Vec::with_capacity_in(100, ALLOCATOR.allocator_api_ref());
    vec.extend(0..300usize);
    vec.truncate(100);
    vec.shrink_to_fit();
}

This is not:

use talc::*;

#[global_allocator]
static ALLOCATOR: Talck<spin::Mutex<()>> = Talc::with_oom_handler(oom_handler).lock();
static mut ARENA: [u8; 10000] = [0; 10000];

fn oom_handler(talc: &mut Talc, _: core::alloc::Layout) -> Result<(), ()> {
    let arena_span = Span::from(unsafe { core::ptr::addr_of_mut!(ARENA) });
    
    if talc.get_arena() == arena_span {
        Err(())
    } else {
        unsafe {
            talc.init(arena_span);
        }
        
        Ok(())
    }
}

fn main() {
    let mut vec = Vec::with_capacity(100);
    vec.extend(0..300usize);
    vec.truncate(100);
    vec.shrink_to_fit();
}

[SFBdragon]

v2 is out, which should fix the issues you have brought to my attention. Thank you!

Note that all the code above is outdated, although the issue with the global_allocator proc macro hasn't gone anywhere.

I'll close the issue for now though. If you encounter any more issues, let me know!