Arithmetic and bitwise ops on AtomicPtr

[thomcc]

Problem statement

We'd like to allow code that wants to atomically manipulate some of the bits of a pointer's address to do so while following the strict provenance rules.

Motivation, use-cases

Currently it's not uncommon to store pointers inside an AtomicUsize in order to allow manipulating their bits. This occurs in parking_lot, usync, crossbeam (I can't find the link, and may be wrong), and several others. These sorts of tricks are also fairly common in C and C++ concurrent data structure implementations, and other similarly tricky code.

Essentially: Libraries and users are already performing atomic operations on pointers that are stored inside AtomicUsize. As part of the strict provenance work, we're adding APIs that allow avoiding roundtrips of pointers through integers. AtomicPtr is a major unsolved piece of that which currently is hard to work around (or at least annoying), and is even called out (or at least name-dropped) as a problem in the core::ptr module docs¹.

Solution sketches

In rust-lang/rust#96935, the following API is implemented. I've included a rough description of semantics, but see the PR for more in-depth documentation comments including an attempted description of the provenance semantics, which I'd summarize as: these ops don't change the provenance of the pointer inside the AtomicPtr, and they (conceptually) operate on the address.

#[cfg(target_has_atomic = "ptr")]
impl<T> AtomicPtr<T> {
    // Add/sub the `AtomicPtr` in units of bytes (e.g. `val` is directly used as
    // an offset, possibly misaligning the pointer).
    //
    // Note that these use the semantics of `ptr::{wrapping_add, wrapping_sub}`,
    // and not `ptr::{add, sub}` (see the "Alternatives" section for some rationale).
    pub fn fetch_byte_add(&self, val: usize, order: Ordering) -> *mut T;
    pub fn fetch_byte_sub(&self, val: usize, order: Ordering) -> *mut T;

    // Same as `fetch_byte_add`/`fetch_byte_sub` but in units of `size_of::<T>()`.
    // Equivalent to `self.fetch_byte_add(val.wrapping_mul(size_of::<T>()))` (or sub).
    pub fn fetch_ptr_add(&self, val: usize, order: Ordering) -> *mut T;
    pub fn fetch_ptr_sub(&self, val: usize, order: Ordering) -> *mut T;

    // Allow atomically setting some bits of a pointer.
    pub fn fetch_or(&self, bits: usize, order: Ordering) -> *mut T;
    // Allow atomically clearing some bits of a pointer.
    pub fn fetch_and(&self, bits: usize, order: Ordering) -> *mut T;
    // Allow atomically toggling some bits of a pointer.
    pub fn fetch_xor(&self, bits: usize, order: Ordering) -> *mut T;
}

I think this is blocked from stabilization by the strict_provenance work, and it may need further refinement as a couple details on targets like CHERI remains an open question², which may impact the shape of these APIs.

Anyway, landing this unstably lets code that wants to work with miri under strict provenance do so (without resorting to something like a CAS/fetch_update loop containing a call to ptr::map_addr, as discussed below).

It also allows us to potentially use these inside the stdlib, so that we can perform these operations while maintaining strict provenance (that is, without breaking or special casing Miri), although I don't know if we actually have any cases where we want this currently.

Alternatives

This API is has some definite wonkiness in it, in a few ways. Here are some alternatives, along with discussion (and if relevant, rationale on why they weren't used):

1. Do nothing. In principal, we could instead opt to document patterns that concurrent code can use to avoid violating strict provenance.

   For example, these may currently be emulated with a CAS loop over oldptr.map_addr(|a| a <op> b) (or a similar fetch_update call). Unfortunately, this has the downsides of poor ergonomics, discoverability, and (probably) performance.

2. Add only a subset of the proposed APIs:

   • fetch_ptr_add/fetch_ptr_sub could be removed, as users can just do ap.fetch_byte_add(n * size_of::<T>(), ord). Now that more time has passed since I filed the PR, I actually kind of am in favor of this, but it might be a surprising absence.

   • You could imagine removing fetch_xor as well, probably, since it's unlikely to be as widely used as the rest.

3. We may want to rename the fetch_ptr_add/fetch_ptr_sub functions.

   While I initially liked this name, if you contrast fetch_ptr_add with fetch_byte_add, it seems like the former would operate in units of size_of::<*const T>(), rather than units of size_of::<T>() (which is how it does work). An alternate name might be fetch_elem_add (but again, perhaps it is better to go with only fetch_byte_*, and force the user to multiply by size_of::<T>() if they need).

   (For background: initially the names for these were fetch_add and fetch_sub, as it mirrored how default arithmetic functions behave for raw pointers. This was changed since it seemed pretty error-prone, since it's likely that frequently, units of size_of::<T>() would not be desired)

4. Rather than using wrapping_add/wrapping_sub semantics for the fetch_{ptr,byte}_{add,sub} functions, we could instead mimic the raw pointer APIs and offer two versions: a set of safe ones with wrapping semantics, and a set of unsafe ones with the in-bounds requirement that ptr::add and friends have.

   This has the benefit of being similar to core::ptr APIs, but I don't think it'd be the right call for the following reasons:

   • It seems error-prone to have the default fetch_*_add functions to behave this way without a bigger warning flag in the name -- AtomicPtr code will frequently already be in an unsafe block, and may be being ported from AtomicUsize, in which case they might not realize a new invariant needs to be upheld (and upholding this kind of invariant can often be harder in concurrent code).

   • In the case that you can easily uphold the safety requirement, I suspect (with no evidence) that unsafe { atomptr.fetch_ptr_add(n, ord).add(n) } is a more useful way to convey this to the compiler anyway, at least if the result is going to be used right away.

   • This would push us to 8 of these add/sub functions on AtomicPtr, and 4 already felt like it was approaching "too many".

   (Note that at least given our current lowering, LLVM would not be able to optimize this any better)

Possible further work

1. This doesn't offer all of the AtomicUsize fetch_* APIs, and maybe we should. Concretely, fetch_nand, fetch_min, and fetch_max are absent:

   • I'm not sure what the use case for fetch_nand would be (wheras or/and/xor map cleanly to set/clear/toggle), as it seems like it would destroy all of the pointer bits. (Maybe I'm just missing something though, it would not be hard to add).

   • While I can imagine some (fully hypothetical) use cases for AtomicPtr::{fetch_min, fetch_max}, I think it would need to take another pointer as the other param, which brings more complex concerns about provenance and possibly signedness.

2. It's possible that fetch_byte_offset/fetch_ptr_offset operations, analogous to ptr::offset, should also be provided.

I believe all of these can be added in the future without any issues if we decide they're important.

Links and related work

• Tracking Issue for strict_provenance rust#95228: The strict provenance tracking issue, as complying with strict provenance is the motivation for this work. It contains a lot of links to other things, discussion around why we might want to add APIs which allow avoiding round-tripping pointers through integers, and is probably required reading to understand this proposal.

• [strict provenance] Close The Gap Between AtomicUsize and AtomicPtr rust#95492: the issue this fixes, which contains some rough and outdated versions what ended up getting PRed.

• Allow arithmetic and certain bitwise ops on AtomicPtr rust#96935: a PR implementing the proposed API, which contains some discussion about the shape of the API, such as what to name these.

• https://rust-lang.zulipchat.com/#narrow/stream/136281-t-lang.2Fwg-unsafe-code-guidelines/topic/Questions.20about.20extending.20strict.20prov.2E.20to.20AtomicPtr: A zulip discussion where the basic current shape of the API was hashed out.

• Support index size != pointer width rust#65473: One of the many discussions about relaxing the "size_of::<usize>() == size_of::<*const T>() (for T: Sized) rule, in order to be more CHERI-compatible. This is discussed a bit above, but I don't think it matters to these APIs in the short term.

• Tracking Issue for pointer_bytes_offsets rust#96283: The tracking issue which includes ptr::byte_add/ptr::byte_sub, from which the fetch_byte_add/fetch_byte_sub APIs take their name.

Footnotes

1. Specifically, the bit where "Yes, if you’ve been using AtomicUsize for pointers in concurrent data-structures, you should be using AtomicPtr instead. If that messes up the way you atomically manipulate pointers, we would like to know why, and what needs to be done to fix it" -- this proposal is hoping to be an answer to "what needs to be done", or at least start us moving towards one. ↩

2. That is, it's been suggested that maybe we'll want to make usize be smaller than a pointer on CHERI. Ignoring whether or not that's good/bad/allowed/breaking/etc, if we do go that route, then the usize passed to these functions would still need to be the same size as a pointer. This is required to prevent mixed-size atomic access (which is cursed, and almost certainly UB). This does mean that while conceptually these do not change the provenance of the pointer in the AtomicPtr, it may be messier in practice, since they could trash the capability bits on CHERI.

   I'm going to optimistically handwave this away for now, since (I'd like to avoid starting another instance of this debate here, but also) probably we'd just change the integers here from usize to whatever fills the shoes of uintptr_t. (I believe there's some precedent for this in how CHERI-C implements atomics on u?intptr_t, FWIW). ↩

[thomcc]

Actually, regarding the CHERI addr stuff in the footnote, we could also just turn the usize into a uptr when lowering. If we arrange it so that when performing fetch_or/fetch_xor/fetch_*_add/fetch_*_sub we ensure the bits/val argument has all-zeros over the capability part, and for fetch_and the bits argument all-ones over the capability part, then this would maintain the semantics of "only operates on the address part" that we'd desire, while avoiding any mixed size atomic access.

So that's probably not going to be a problem, and won't end up impacting the API surface (or semantics). At least, it doesn't have to.

[cuviper]

We should get some CHERI folks to confirm that a no-op on those capability bits will let the hidden validity bit remain.

[arichardson]

Regarding footnote 2: For CHERI uintptr_t atomics in C, while the LLVM instructions currently take a 128-bit uintptr_t as the fetch_add argument (i8 addrspace(200)*), the semantics are as if the argument was a size_t (64-bit). This means provenance is inherited from the LHS. However, most of the time we only see (cmp)xchg being used on pointer atomics, fetch_add is quite rare.

[thomcc]

most of the time we only see (cmp)xchg being used on pointer atomics, fetch_add is quite rare.

The linked parking_lot and usync code both have examples of using fetch_sub/fetch_add on a AtomicUsizes which may or do hold pointers. It's mostly to manipulate tags stored in unused bits, or to manipulate them when the value isn't a pointer at all, and is just a bitpattern that in other code paths could hold a pointer (a la https://doc.rust-lang.org/nightly/std/ptr/fn.invalid.html).

I do think manipulating pointer tag bits fetch_and and fetch_or are somewhat more common though, but these use cases seem pretty reasonable to me, and have precedent since at least parking_lot is quite popular.

---

Anyway, I think this means we can ignore CHERI as a concern here, and however things pan out with usize on CHERI, these APIs will not be impacted.

[yaahc]

Seconded (by @dtolnay)

@rustbot label +initial-comment-period

[rustbot]

Error: The feature relabel is not enabled in this repository.
To enable it add its section in the triagebot.toml in the root of the repository.

Please file an issue on GitHub at triagebot if there's a problem with this bot, or reach out on #t-infra on Zulip.

[yaahc]

this time i believe (that #64 will fix the issue)

@rustbot label +initial-comment-period

edit: 😡

[rustbot]

Error: The feature relabel is not enabled in this repository.
To enable it add its section in the triagebot.toml in the root of the repository.

Please file an issue on GitHub at triagebot if there's a problem with this bot, or reach out on #t-infra on Zulip.

[WaffleLapkin]

This was implemented a while ago, should we close this?