Allocator::deallocate causes Miri stacked borrows violation

[inahga]

Miri under defaults settings (e.g. cargo miri nextest run allocate::tests::unaligned_allocator_16) generates UB findings for any tests exercising deallocation:

--- STDERR:              zlib-rs allocate::tests::unaligned_allocator_16 ---

error: Undefined Behavior: attempting a read access using <338987> at alloc135660[0xd], but that tag does not exist in the borrow stack for this location
   --> zlib-rs/src/allocate.rs:254:28
    |
254 |             let free_ptr = core::ptr::read_unaligned(original_ptr as *mut *mut c_void);
    |                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |                            |
    |                            attempting a read access using <338987> at alloc135660[0xd], but that tag does not exist in the borrow stack for this location
    |                            this error occurs as part of an access at alloc135660[0xd..0x15]
    |
    = 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: <338987> was created by a SharedReadWrite retag at offsets [0x15..0x25]
   --> zlib-rs/src/allocate.rs:303:43
    |
303 |             unsafe { allocator.deallocate(ptr, 1) }
    |                                           ^^^
    = note: BACKTRACE (of the first span) on thread `allocate::tests`:
    = note: inside `allocate::Allocator::<'_>::deallocate::<std::mem::MaybeUninit<u128>>` at zlib-rs/src/allocate.rs:254:28: 254:87
note: inside `allocate::tests::unaligned_allocator_help::<u128>`
   --> zlib-rs/src/allocate.rs:303:22
    |
303 |             unsafe { allocator.deallocate(ptr, 1) }
    |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `allocate::tests::unaligned_allocator_16`
   --> zlib-rs/src/allocate.rs:335:9
    |
335 |         unaligned_allocator_help::<u128>()
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure
   --> zlib-rs/src/allocate.rs:334:32
    |
333 |     #[test]
    |     ------- in this procedural macro expansion
334 |     fn unaligned_allocator_16() {
    |                                ^
    = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

This may be real UB, not just a violation of an experimental model. We pass around the allocated memory as a reference. Rust annotates reference function arguments as dereferencable, meaning LLVM can infer the reference can always be dereferenced. When a function invokes deallocate(), this assumption is violated and is therefore UB (see crossbeam-rs/crossbeam#545 (comment) for a chain of further reading).

I believe Miri flags this since we turn the allocated pointer into a reference, then rederive the pointer from the reference. This discards the provenance information about the pointer. We can solve both problems by never decaying allocations to a reference, i.e. always passing around allocations as pointers.

I'd suggest creating a new smart pointer type, perhaps one that encapsulates a raw *mut u8 and PhantomData<T>. Here's a quick (bad) sketch of that main...inahga:zlib-rs:inahga/fix-miri.

Alternatively, it may be less invasive to return allocations as NonNull<MaybeUninit<T>>. I've sketched that as well main...inahga:zlib-rs:inahga/fix-miri-2, it may be tricky to adapt this for slice types though.

Relatedly: I see elsewhere in CI we eschew stacked borrow checking by using -Zmiri-tree-borrows. What flags should Miri be run under? (I'd prefer that Miri passes with default flags, since it has fairly sensible defaults, but I'm curious if there's any rationale I'm missing).

[folkertdev]

I'll have to look at the details of those proposed solutions, but can give some context here

Relatedly: I see elsewhere in CI we eschew stacked borrow checking by using -Zmiri-tree-borrows. What flags should Miri be run under? (I'd prefer that Miri passes with default flags, since it has fairly sensible defaults, but I'm curious if there's any rationale I'm missing).

Of course I initially tried to run miri without any extra flags, and it failed with basically this error. So I asked in the zullip

https://rust-lang.zulipchat.com/#narrow/stream/269128-miri/topic/custom.20allocators.20with.20alignment/near/441097041

which confirmed that stacked borrows just cannot deal with allocators (if you also want the ergonomics of references to your allocated values). I think we really do want the ergonomics of slices if we at all can (for bounds checking, stdlib support, etc). At that point I went with just passing -Zmiri-tree-borrows because

• it's the newer model
• based on that zullip converation, it was designed to handle cases like this

My (naive) assumption has been that miri + tree borrows being OK with the code means that the code is sound.

---

I believe the problem in your second comment is distinct, because I recently ran into something very similar on the main branch where the problem was that a pointer is derived from the same reference twice, and both are "active" at the same time. The solution there was to just turn the reference into a pointer once, and then perform the arithmetic on the pointer.

[inahga]

Thanks for the context about Miri.

if you also want the ergonomics of references to your allocated values

I think that may be true, indeed the suggestions I've granted either de-optimize a bit, or sacrifice ergonomics (indeed I'm not 100% sure if the NonNull approach can be adapted for slice types, will need to experiment more).

My (naive) assumption has been that miri + tree borrows being OK with the code means that the code is sound.

That's sort-of my reading as well, insofar as Miri claims that tree borrows will find aliasing violations that more tangibly affect Rust today. https://github.com/rust-lang/miri?tab=readme-ov-file#miri--z-flags-and-environment-variables.

Though, I still find the allocation pattern we're using somewhat questionable due to deallocating a reference during a function call (i.e. ReadBuf::drop_in()). I will do some more reading/testing to confirm this though, all I find are mentions to this being UB in ad-hoc issues.

I believe the problem in your second comment is distinct,

Ah, I think you're right. I made the comment too fast 😄. I'll look into it more and pull it out into another issue.

[inahga]

Though, I still find the allocation pattern we're using somewhat questionable due to deallocating a reference during a function call (i.e. ReadBuf::drop_in()). I will do some more reading/testing to confirm this though, all I find are mentions to this being UB in ad-hoc issues.

I do believe this is UB, but I will open a separate issue for it. The original topic of this issue is not pertinent, since I won't be using Miri under stacked borrows for this project.