Tracking Issue for arithmetic and certain bitwise ops on AtomicPtr

[WaffleLapkin]

Feature gate: #![feature(strict_provenance_atomic_ptr)]

This is a tracking issue for arithmetic and certain bitwise operations on AtomicPtr.
As part of the strict provenance experiment #95228.

This feature adds arithmetic (add, sub) and bitwise (or, end, xor) atomic operations for AtomicPtr in order to replace uses of AtomicUsize-but-actually-a-pointer to preserve provenance information for the compiler and remove usize->ptr casts from existing code.

Arithmetic ops behave as the their non-atomic wrapping versions. Bitwise ops behave as .map_addr(|x| x op val).

Public API

// core::sync::atomic

impl<T> AtomicPtr<T> {
    pub fn fetch_ptr_add(&self, val: usize, order: Ordering) -> *mut T;
    pub fn fetch_ptr_sub(&self, val: usize, order: Ordering) -> *mut T;

    pub fn fetch_byte_add(&self, val: usize, order: Ordering) -> *mut T;
    pub fn fetch_byte_sub(&self, val: usize, order: Ordering) -> *mut T;

    pub fn fetch_or(&self, val: usize, order: Ordering) -> *mut T;
    pub fn fetch_and(&self, val: usize, order: Ordering) -> *mut T;
    pub fn fetch_xor(&self, val: usize, order: Ordering) -> *mut T;
}

Steps / History

• Implementation: Allow arithmetic and certain bitwise ops on AtomicPtr #96935
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• Naming (some discussion at Rename AtomicPtr::fetch_ptr_{add,sub} to AtomicPtr::fetch_{add,sub} libs-team#126)

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[RalfJung]

In terms of implementation details, I think we should also improve the types at which we call the atomic_add and other core atomic intrinsics. Right now we pass them two pointers and then the backend has to know that the left one is actually a pointer and we care about its provenance, and the right one isn't. Ideally we'd give a pointer as first argument and an integer as second argument.

[WaffleLapkin]

"The problem" with making rhs usize is that all atomic intrinsics are currently defined as *mut T -> T -> T, for example:

rust/library/core/src/intrinsics.rs

Line 111 in 8a392a5

pub fn atomic_xadd_relaxed<T: Copy>(dst: *mut T, src: T) -> T;

Making the second argument of a different type will probably require compiler changes.

[RalfJung]

Indeed, and I think those compiler changes should be made. :)

[WaffleLapkin]

I think ptr in method names (fetch_ptr_add and fetch_ptr_sub) is confusing, we are not adding/subtracting a pointer but instead just add/sub in units of T. IMO it's too similar to sub_ptr.

[ibraheemdev]

I think the only open question about this API is whether there is a better name for fetch_byte_{add,sub}/fetch_ptr_{add,sub} (rust-lang/libs-team#126 (comment))? Can we move forward towards stabilization? If those methods are still up for debate, fetch_{or,and,xor} are pretty straightforward additions (and probably the more common operations) so can probably be stabilized.

[tgross35]

Why not just fetch_wrapping_{add, sub} rather than fetch_ptr_sub? ptr in the name seems redundant, and I would expect fetch_add to be the equivalent of <*const T>::add (not <*const T>::wrapping_add)

[WaffleLapkin]

@tgross35 note that all atomic operations are wrapping, so wrapping is probably even more redundant than ptr 😅

I don't really like _ptr_ either, but it does disambiguate that it's in units of T, as opposed to fetch_byte_add.

[tgross35]

@RalfJung are there any implementation blockers to stabilizing these API, now that strict_provenance merged?

It sounds like nobody is super thrilled with the ptr_add / ptr_sub names so there is probably more bikeshedding there, but it seems like maybe we are okay on the technical side of things now.

[RalfJung]

I don't know how these are implemented, but from an opsem perspective this all seems fine.

Arithmetic ops behave as the their non-atomic wrapping versions. Bitwise ops behave as .map_addr(|x| x op val).

Note that the wrapping ptr arithmetic operations are equivalent to ptr.map_addr(|x| x.wrapping_add(offset)), so indeed all these ops here can be explained as atomic variants of map_addr.

[RalfJung]

The implementation is a bit odd, since it goes via atomic_add which ends up adding two pointers together. Miri then explicitly says we always return a value with the provenance of the left input.

Worse, for LLVM we are casting everything to integers and emit an atomic integer add. That may work since LLVM never analyzes the flow of pointers through atomics too carefully, but it is strictly speaking not a correct implementation. I don't know if LLVM has any way to do e.g. an atomic wrapping increment on a pointer in a way that preserves provenance (i.e., does not go through integers), but that is what we would need -- Cc @nikic.

[nikic]

Why isn't it a correct implementation? Isn't going through a pointer to integer to pointer cast conservatively correct, just sub-optimal from an optimization perspective?

We can add an atomicrmw ptradd flavor, but I don't think it would really make any difference in terms of LLVM behavior. Things like fetch_or would have to go via integers anyway.

[RalfJung]

The problem is that in memory, there is a pointer (i.e. data with provenance). We then do an atomicrmw at type i64 on that, which means it loads the pointer as an integer, adds something, and then stores it back. This sounds like a sequence of operations that could be considered as discarding provenance -- at last if you did this in Rust, it would discard provenance, and in general LLVM is unsound if an i64 value can hold provenance.

I don't know if LLVM ever replaces atomicrmw by a sequence of read-arithmetic-write when it has proven that the location is local and there can't be any racy accesses; that might be one way that this turns into trouble.

[marc0246]

The ptr in the names sounds like stutter to me, and I really dislike the inconsistency with the raw pointer method names. The argument for changing between AtomicUsize and AtomicPtr sounds weak to me because how could this not be the first thing that's caught by unit testing, or really, any testing?

But really, I just want this to be stabilized. I'd rather seethe writing those method names because the type is arguably unusable without these methods.

[ibraheemdev]

Does anyone have a use case for fetch_ptr_add? I've never come across any code that would need it, I only have examples of fetch_byte_add(1). I'm not sure why you would be atomically adding in terms of T (typically the allocation is finite and so you would need to preserve the original pointer).

Though I would prefer fetch_byte_add be made the default fetch_add, it seems people have strongly differing opinions so disambiguating explicitly seems reasonable.

I also think fetch_or/xor/and are uncontroversial and the most important to stabilize.

[marc0246]

Indeed the methods I'm really looking for personally are the bitwise ones. Arithmetic is useful to me for e.g. concurrent allocation but you need compare_exchange for that like you mention. Even then, it's most likely adding in terms of bytes. So I like the idea of stabilizing everything except the arithmetic 👍

[tgross35]

Does anyone have a use case for fetch_ptr_add? I've never come across any code that would need it, I only have examples of fetch_byte_add(1). I'm not sure why you would be atomically adding in terms of T (typically the allocation is finite and so you would need to preserve the original pointer).

Though I would prefer fetch_byte_add be made the default fetch_add, it seems people have strongly differing opinions so disambiguating explicitly seems reasonable.

It does look like there are some uses of it floating around, probably using the version from portable_atomic https://github.com/search?q=lang%3Arust+%2Ffetch_ptr_%28add%7Csub%29.*%3B%2F+%28NOT+path%3Atests%29+%28NOT+path%3Alibrary%2Fcore%2Fsrc%2Fsync%29&type=code.

It looks like fetch_add defaulting to bytes came up at #96935 (comment) (I agree that if fetch_add, if it exists with that name, should be doing the same thing as <*mut T>::add to avoid confusion).

I also think fetch_or/xor/and are uncontroversial and the most important to stabilize.

Agreed that this is probably the most useful bit of the API. I think it is still blocked on some resolution to the above LLVM behavior / provenance question though.

[ibraheemdev]

It does look like there are some uses of it floating around, probably using the version from portable_atomic

Ah kernel-level usage makes sense. I would still disagree that this should be default behavior so the current API seems fine.

Agreed that this is probably the most useful bit of the API. I think it is still blocked on some resolution to the above LLVM behavior / provenance question though

Is there discussion about that anywhere? Even if the current implementation is problematic, stabilizing would be useful for Miri compatibility.

[tgross35]

Agreed that this is probably the most useful bit of the API. I think it is still blocked on some resolution to the above LLVM behavior / provenance question though

Is there discussion about that anywhere? Even if the current implementation is problematic, stabilizing would be useful for Miri compatibility.

AIUI there isn't anything problematic with our API, just possibly some LLVM semantics that our intrinsics invoke. But I'll bring this up on opsem llvm Zulip to double check. (edit: https://rust-lang.zulipchat.com/#narrow/channel/187780-t-compiler.2Fwg-llvm/topic/AtomicPtr.20provenance.20APIs)

In any case the docs should probably gain a note about provenance since this is indeed tricky.

[tgross35]

For naming, I can't come up with anything better than fetch_wrapping_add and fetch_wrapping_sub for T-sized offsets here.

• It is consistent with <*const T>::wrapping_add which has the same semantics as this operation
• It breaks the footgun of switching between AtomicUsize and AtomicPtr and getting different results with fetch_add (this concern from here)
• I don't think we ever expect to add an atomic API that parallels <*const T>::add

That being said, add_ptr and (oops that never existed) sub_ptr is being renamed so the current names here won't conflict anymore.

[RalfJung]

add_ptr and sub_ptr #95892

There is no add_ptr, but yes sub_ptr is being renamed.