Miri can't track pointer through atomic bit-flip, which happens as usize

[jonhoo]

In haphazard, I maintain a concurrent linked list of things that can be "locked" through a bit flip in the next pointer. The relevant code is here:

https://github.com/jonhoo/haphazard/blob/ba8ffcceba6f0a0b117c0e35d2ab05a6c1bb5233/src/domain.rs#L259-L281

It basically looks like this:

let head_available = AtomicUsize::new(0);

// ...

let avail = hazptrs.head_available.load(Ordering::Acquire);
if avail == core::ptr::null::<HazPtrRecord>() as usize {
    return core::ptr::null_mut();
}
if (avail & LOCK_BIT) == 0 {
    let avail: *const HazPtrRecord = avail as _;

    // The available list is not currently locked.
    // Take the lock by flipping the bit.
    if head_available.compare_exchange_weak(
        avail as usize,
        avail as usize | LOCK_BIT,
        Ordering::AcqRel,
        Ordering::Relaxed,
    ).is_ok() {
        // ...

I would love to run this code through Miri with -Zmiri-tag-raw-pointers (it runs fine without), but then I (as expected) run into "parent tag " due to the int-to-ptr conversion, which matches the README's note saying " You can recognize false positives by <untagged> occurring in the message -- this indicates a pointer that was cast from an integer, so Miri was unable to track this pointer." You can replicate the issue using:

$ env "MIRIFLAGS=-Zmiri-tag-raw-pointers" cargo +nightly miri test --test lib feels_good

    Finished test [unoptimized + debuginfo] target(s) in 0.03s
     Running tests/lib.rs (/home/jon/.cargo-target/miri/x86_64-unknown-linux-gnu/debug/deps/lib-c166183ccbed9275)

running 1 test
test feels_good ... error: Undefined Behavior: trying to reborrow for SharedReadWrite at alloc65366, but parent tag <untagged> does not have an appropriate item in the borrow stack
   --> /home/jon/dev/streams/haphazard/src/domain.rs:310:33
    |
310 |         let mut next = unsafe { &*tail }.available_next.load(Ordering::Relaxed);
    |                                 ^^^^^^ trying to reborrow for SharedReadWrite at alloc65366, but parent tag <untagged> does not have an appropriate item in the borrow stack
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the 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

    = note: inside `haphazard::Domain::<haphazard::Global>::try_acquire_available_locked::<1_usize>` at /home/jon/dev/streams/haphazard/src/domain.rs:310:33
    = note: inside `haphazard::Domain::<haphazard::Global>::try_acquire_available::<1_usize>` at /home/jon/dev/streams/haphazard/src/domain.rs:284:45
    = note: inside `haphazard::Domain::<haphazard::Global>::acquire_many::<1_usize>` at /home/jon/dev/streams/haphazard/src/domain.rs:217:29
    = note: inside `haphazard::Domain::<haphazard::Global>::acquire` at /home/jon/dev/streams/haphazard/src/domain.rs:211:9
    = note: inside `haphazard::HazardPointer::new_in_domain` at /home/jon/dev/streams/haphazard/src/hazard.rs:54:21
    = note: inside `haphazard::HazardPointer::<'static>::new` at /home/jon/dev/streams/haphazard/src/hazard.rs:41:9
note: inside `feels_good` at tests/lib.rs:106:17
   --> tests/lib.rs:106:17
    |
106 |     let mut h = HazardPointer::new();
    |                 ^^^^^^^^^^^^^^^^^^^^
note: inside closure at tests/lib.rs:77:1
   --> tests/lib.rs:77:1
    |
76  |   #[test]
    |   ------- in this procedural macro expansion
77  | / fn feels_good() {
78  | |     let drops_42 = Arc::new(AtomicUsize::new(0));
79  | |
80  | |     let x = AtomicPtr::new(Box::into_raw(Box::new((
...   |
160 | |     assert_eq!(drops_9001.load(Ordering::SeqCst), 1);
161 | | }
    | |_^
    = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

Is there any way for me to "help" Miri realize what's going on here? For reference, the pointer stores happen here:

https://github.com/jonhoo/haphazard/blob/ba8ffcceba6f0a0b117c0e35d2ab05a6c1bb5233/src/domain.rs#L320-L322

and here

https://github.com/jonhoo/haphazard/blob/ba8ffcceba6f0a0b117c0e35d2ab05a6c1bb5233/src/domain.rs#L337-L350

[oli-obk]

Related issue for the same situation only in LLVM:

• Expose llvm.ptrmask intrinsic rust#63656

Basically we need a way to modify bits of a pointer as long as they only affect things that are not part of the base address. We used to have some of that in miri, but never exposed it to users. In addition to the existing offset method on pointers we need a way to read/write only the bits that the alignment of the pointee says must be zero if we had a reference instead of a pointer.

[RalfJung]

For non-atomic pointer manipulation, a solution exists, see this discussion and also here. At least as far as Miri provenance tracking is concerned, that basically handles the cases Oli mentioned:

/// Converts 'addr' to a pointer using the provenance of 'prov'.
fn int_to_ptr_with_provenance<T>(addr: usize, prov: *const T) -> *const T {
  // Nowhere in this function do we cast an integer to a pointer!
  let ptr = prov.cast::<u8>();
  ptr.wrapping_add(addr.wrapping_sub(ptr as usize)).cast()
}

let addr = ptr as usize;
// do bit-level stuff with addr to compute new_addr
let new_ptr = int_to_ptr_with_provenance(new_addr, ptr);

This code never casts an integer to a pointer and thus avoids all the problems associated with that operation.

However, that is likely not enough for atomic pointer manipulation. I'll take a look at this example later to understand what is needed.

[jonhoo]

Hmm, I think I could probably apply that to the code that's there today, since it does non atomic manipulation and then compare_exchanges it back. Will do that once I get a chance! However the next optimization I had planned for that piece of code was to swap the compare exchange for a fetch_or to do the bit flip atomically, which would then run afoul of the limitation.

[RalfJung]

Yes, fetch_or is exactly the concern (as @thomcc keeps mentioning whenever I propose int_to_ptr_with_provenance ;).

Basically we'd need fetch_or on AtomicPtr to even make this expressible.

[RalfJung]

Maybe at least for now an option is to "polyfill" such a fetch_or on Miri by doing a compare_exchange loop instead? Clearly that's not a proper solution though.

[jonhoo]

Yeah, it's a good idea — I'll take a look at making that change in haphazard for the time being with a link back to this :)

[thomcc]

Yes, fetch_or is exactly the concern (as @thomcc keeps mentioning whenever I propose int_to_ptr_with_provenance ;).

I will never log off

So, at one point I considered trying to mock up what the API would look like for a small family of AtomicB32/AtomicB64/AtomicB128, where the B represents bytes, since at the time it was being discussed by LLVM. My hope was if it was relatively clean in the end, I could run it by Ralf and mock up a pre-RFC, or something.

Unfortunately, largely I came to the conclusion it wasn't really viable. That it would just be a lot easier to find a way to either allow pointer->integer conversions, to make the atomic types generic, or to just make the existing atomic types behave this way, even if it means that they have provenance now.

That said, the main motivation for this exploration was "how can I CAS a #[repr(C)] struct { aba_counter: usize, ptr: *mut T }?", rather than this issue. And in fact, making them generic makes the problem in this issue slightly harder to design the API, since IMO it becomes a bit less reasonable to add bitwise operations, given that pointers don't support them¹?

I also have some... reasonably strong feelings about turning the current pointer->integer->pointer casts² into UB being a stability break too (and personally I think stability is more important³ than allowing aggressive optimizations around pointers, but I know many others disagree with me here, or disagree that it is actually a violation of our stability rules).

---

All that said, I suppose it wouldn't be hard to mock up what adding atomic ops directly to AtomicPtr would look like, as an unstable API. This might require new intrinsics for them, although perhaps the functions are enough, and miri could detect that e.g. the atomic_or intrinsic is being used on a pointer type. It may require additional changes to the other backends, I don't know.

That said, something here is probably needed to keep miri working when we integrate parking_lot into libstd, or more broadly improve our lock impls. For example, https://github.com/Amanieu/parking_lot/blob/78f09f45d6b8b34ec23afdf7a696cbe54d0a469b/core/src/word_lock.rs ⁴ does bitor on an AtomicUsize that holds a pointer.

Footnotes

1. Recently, It's been discussed that perhaps they should. I think this would be... interesting. ↩

2. Hell, I almost feel that way about pointer->integer transmutes, and much of the discussion about transmutes was around "what if we just made them be the same as casts", which I guess seems like it's no longer on the table. ↩

3. A lot of my perception here is colored by the fact that I don't think the optimizations this disallows tend to be that profitable in practice, but... well, perhaps I'm mistaken, and this is super getting off track at this point. ↩

4. It's possible we would just use a system lock instead in the libstd integration, since this lock isn't exposed. Even so, this kind of MCS-style construction is not uncommon in synchronization primitives. ↩

[RalfJung]

I also have some... reasonably strong feelings about turning the current pointer->integer->pointer casts2 into UB being a stability break too (and personally I think stability is more important3 than allowing aggressive optimizations around pointers, but I know many others disagree with me here, or disagree that it is actually a violation of our stability rules).

I absolutely hear you. I view this as exploring possibilities.
However, this isn't just about "aggressive optimizations around pointers". If we want to do any optimizations at all based on our reference types (anything that needs alias restrictions), including whatever LLVM already does with the noalias that we emit, I am now almost convinced we have to either

• drop ptr2int2ptr roundtrips, or
• make the aliasing model horrendously complicated (and Miri horrendously inefficient) by having some kind of "speculative provenance" that tracks all possible "provenance guesses" on an int2ptr cast and how they would play out in terms of which pointers get invalidated when, or
• accept counter-intuitive behavior such as Stacked Borrows: using the topmost "untagged" item is not "monotonic" unsafe-code-guidelines#273

And that already is assuming that a ptr2int cast performs a sort of "broadcast" of the provenance, meaning transmutes are entirely out.

I admit we lack data on how useful these optimizations are in practice. And there always is a slight chance that some clever trick could avoid this conundrum. :D

[jonhoo]

I implemented the suggested workaround, and documented what we'd need to do for fetch_or, in jonhoo/haphazard@0042528. Thanks!

[RalfJung]

FWIW here's a convenient wrapper around that cast function that has been proposed several times on Zulip:

fn int_to_ptr_with_provenance<T>(addr: usize, prov: *const T) -> *const T {
    // Nowhere in this function do we cast an integer to a pointer!
    let ptr = prov.cast::<u8>();
    ptr.wrapping_add(addr.wrapping_sub(ptr as usize)).cast()
}

fn ptr_map_addr<T>(ptr: *const T, f: impl FnOnce(usize) -> usize) -> *const T {
    int_to_ptr_with_provenance(f(ptr as usize), ptr)
}

let x = 12u16;
let tagged_x = ptr_map_addr(&x, |addr| addr | 0x1);

[JakobDegen]

Basically we need a way to modify bits of a pointer as long as they only affect things that are not part of the base address. We used to have some of that in miri, but never exposed it to users. In addition to the existing offset method on pointers we need a way to read/write only the bits that the alignment of the pointee says must be zero if we had a reference instead of a pointer.

I actually don't think that we necessarily need the "are not part of the base address" restriction. This restriction is important in C because in C people expect that if they figure out the pointer's address - no matter how - it's ok to use it for an int->ptr cast. But in Rust I don't think that will necessarily be a huge concern, because the rules are sort of more complicated already. People have even talked about having an explicit "pointer to int without broadcasting" (if we do choose semantics that involve broadcasting) operation.

[RalfJung]

I hope this will be resolved by #2133.

[jonhoo]

@RalfJung I'm not sure I completely see how #2133 fixes this? Specifically, if I use AtomicPtr::fetch_or, for example, I think that'll still lose provenance, and there won't be anywhere to recover the provenance from since the AtomicPtr is the only places that actually holds the pointer over time.

[RalfJung]

There is no AtomicPtr::fetch_or?

[RalfJung]

rust-lang/rust#96935 is suggesting to add some more operations to AtomicPtr, and they are all provenance-preserving.

[jonhoo]

Ah, sorry, yes, I was thinking of AtomicUsize::fetch_or with a pointer being stored in there, but that obviously won't work anyway. Thanks for the pointer (heh) to that PR — I'll keep an eye on it!

[RalfJung]

If you use proper casts to go from a ptr to usize and back, this will actually work now in Miri. But it might miss some bugs since the alias tracking has to get somewhat approximate.