Weird behavior in unsafe rust

help
1

I've been writing code for stack allocation, but with a stack on the heap (actually multiple stacks, but that's not entirely relevant). I've implemented a few easy data structures for it, but now I want to implement b-tree maps. However, it's running into weird UB that I can't find the source of.
I've made a minimal example that uses normal heap allocation, lacks a bunch of lifetime stuff and PhantomDatas, and isn't fully functional, but results in the very strange errors and the compiler emitting a UD2 instruction. Other errors include add/subtract with overflow in random places and index out of bounds: the len is 11 but the index is 65530 in insert_kv_unchecked (which is only possible if it takes the wrong branch).

Note that I am currently on rust 1.89 on gentoo amd64.

2

Have you tried running it with miri? I get a provenance error (UB). Maybe you can use the error message for debugging.

   Compiling playground v0.0.1 (/playground)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.58s
     Running `/playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/cargo-miri runner target/miri/x86_64-unknown-linux-gnu/debug/playground`
error: Undefined Behavior: pointer not dereferenceable: pointer must be dereferenceable for 192 bytes, but got 0x21280[noalloc] which is a dangling pointer (it has no provenance)
   --> /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:481:18
    |
481 |         unsafe { &mut *self.as_ptr() }
    |                  ^^^^^^^^^^^^^^^^^^^ Undefined Behavior occurred here
    |
    = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
    = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
    = note: BACKTRACE:
    = note: inside `std::ptr::NonNull::<Lnode<usize, usize>>::as_mut::<'_>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:481:18: 481:37
note: inside `HsBTreeMap::<usize, usize>::insert`
   --> src/main.rs:47:33
    |
 47 |             let leaf = unsafe { node_ref.leaf().as_mut() };
    |                                 ^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `main`
   --> src/main.rs:14:9
    |
 14 |         map.insert(i, i);
    |         ^^^^^^^^^^^^^^^^

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

error: aborting due to 1 previous error
1 Like
3

I did not even know miri existed until now! I can't easily install it on gentoo right now because it requires nightly and nightly rust won't compile for me, but the provenance error traced back to me using NonNull::without_provenance, and reading the description of that tells me that I really shouldn't have been using it. Switching it to with_exposed_provenance fixed everything. Thanks!

4

I don’t think you should be using exposed provenance either. There’s got to be a way to do pointer arithmetic with the low address bits while preserving provenance. Let me go find how the standard library does it.

Looks like map_addr or wrapping_offset would be better. And look at the example in the documentation for mask (the example uses map_addr, among other methods).