Support for (unsafe) atomic numeric and bit operations

[eggyal]

Another fantastically useful concurrency crate—thank you, @taiki-e !

I'm using atomic-maybe-uninit to workaround rust-lang/unsafe-code-guidelines#517. In particular, I transmute between "tagged pointer" structs similar to the following and MaybeUninit<u128> in order to manipulate atomically in an AtomicMaybeUninit<u128> without loss of pointer provenance:

#[cfg(target_pointer_width = "64")]
#[repr(C)]
pub struct TaggedPtr<T> {
    _align: [u128; 0],

    #[cfg(target_endian = "little")]
    pub tag: usize,

    pub ptr: *mut T,

    #[cfg(target_endian = "big")]
    pub tag: usize,
}

There are times that I need to atomically add/subtract from the tag. Currently, I do this via fetch_update—however that is obviously suboptimal, as it produces a compare-exchange loop. I'd like instead to be able to do a fetch_add/fetch_sub (and, by extension, one can also imagine cases where the other atomic bit and numeric operations might also be desirable).¹

Clearly such operations must be unsafe as the caller must guarantee that the value has been fully initialised. Indeed, casting as a fully initialised atomic, eg AtomicU128, to perform the operation is a possibility; but any value returned from such functions would then have lost pointer provenance, necessitating a subsequent load from the (uncasted) AtomicMaybeUninit to regain provenance—and thereby opening the door for other threads to modify the value in the interim.

Would you be open to adding such unsafe operations to AtomicMaybeUninit?

---

_{1. Before transmuting back from such a manipulated MaybeUninit<integer>, one must obviously check that the data is valid for the destination type; in this case, I will have to check that the tag did not overflow.}

[RalfJung]

So what you are looking for are provenance-preserving fetch_add/sub? As in, atomic pointer arithmetic?

[eggyal]

These operations won't actually modify the pointer, but yes I suppose the compiler will have to assume that it's pointer arithmetic (unless user provides a mask to indicate which bits are to be modified such that provenance is dropped only on those, however the compiler would have to generate some runtime validation which will be some complex fn of operation and mask).

[taiki-e]

As for fetch_add/fetch_sub, since double-width atomic add/subtract instructions are not available in any architecture, I don't feel that this API is particularly efficient compared to the CAS loop¹ (aside from LL/SC. well LLVM uses CAS instructions when it is available instead of LL/SC instructions, although). For 128-bit atomic instructions see this table.

As for bit operations, I have previously written implementations for aarch64: https://github.com/taiki-e/atomic-maybe-uninit/tree/rmw
Also, in my understanding, perhaps there would be no need for safety requirements on initialization at the AtomicMaybeUninit API level (iiuu <bit-op> iuiu == iuuu (i=init,u=uninit) should be able to guarantee).
That said, there should be very few (perhaps none at all in practice) CPUs at this time that actually support double-width atomic bit operation instructions as well (see the table mentioned above).

Footnotes

1. Well, there is an optimization that can be done if the CAS loop is written entirely in assembly, so it is slightly more efficient, although. ↩

[RalfJung]

AtomicMaybeUninit API level (iiuu iuiu == iuuu (i=init,u=uninit) should be able to guarantee).

I'm not sure what you mean, but bit operations on uninit data are UB. Rust doesn't have "poison" semantics, it has "immediate UB" semantics for operations like this.

[taiki-e]

@RalfJung

I'm not sure what you mean, but bit operations on uninit data are UB. Rust doesn't have "poison" semantics, it has "immediate UB" semantics for operations like this.

It was over a year ago, so I don't remember exactly what happened, but I think I was thinking about what actually happens with bit operations on the assembly (hardware) side and how much of that could be reflected in the API.

[taiki-e]

In any case, for such a use case (all initialized), I think it would be better to add something like AtomicDoublePtr(or AtomicPtrPair?) to portable-atomic crate, where the necessary implementation is already almost there, than to add such an API to this crate.

(Btw, there are actually several such types built on (patched) portable-atomic in private projects I have created in the last year. Particularly odd was AtomicTaggedPtrPair, which packed two pointers and one tag (extracted and merged from the lower bits of each pointer) into a single DW atomic...)

[eggyal]

As for fetch_add/fetch_sub, since double-width atomic add/subtract instructions are not available in any architecture

Ah, this I hadn't realised. The paper I was reading relies on double-width atomic RMW (read-modify-write) ops, and in pseudocode details an algorithm applying FAA (fetch-and-add) to a double-width variable, which is why I was searching for such facility so that I could play with an implementation in Rust. Looking now at the reference C++ implementation, I see that it calls gcc libatomic's atomic_fetch_add which indeed compiles to a CAS loop if the architecture lacks native support (godbolt), which hadn't been clear to me from its documentation.

Therefore I personally no longer have a use for this and am quite happy for the issue to be closed.

Thank you all for indulging me with your time and consideration; apologies for my misunderstanding.