Atomic[IU]size: Supply a generic CAS loop

[llogiq]

Rationale: Writing an optimal CAS loop is time-consuming and risks errors (e.g.
mis-setting Orderings). On the other hand, there are two general operations:
fetch_and_update which is useful for things like random number generators,
and update_and_fetch which is the usual operation when you want to e.g. keep
a maximum stat over a series of concurrently produced values.

Adding those two operations as methods has little cost. Conversely, requiring
an extra crate means that the methods would have to either be implemented as
functions instead of methods, or that an extension trait would have to be
imported to use them. Both of those options are suboptimal.

Prior art: Java has an getAndUpdate / updateAndGet method on its
AtomicInteger class since version 1.8. Due to the fact that Java lambdas are
more restricted w.r.t. mutability of their arguments than Rust's, there's also
accumulateAndGet / getAndAccumulate.

[ghost]

This method would definitely be useful. However, I wonder if it's a better fit for something like crossbeam_atomic::AtomicCell rather than std::sync::atomic::AtomicUsize?

Note that Java's AtomicInteger would be more similar to AtomicCell (they're both high-level atomic primitives), while AtomicUsize is more low-level (it's essentially just a thin wrapper around LLVM atomics).

[stbuehler]

I think the current doc could be read as "on success returns Ok(new_value)"; afaict the implementation always returns the "previous" value passed to the last invocation of f; as Ok(_) on success and as Err(_) if f returned None. Perhaps the wording could be improved?

[llogiq]

Agreed, the wording can certainly be improved. I had a lot of back-and-forth and frankly at one point almost closed the PR, I'm just happy it's landed.

If you like, you may submit a doc improvement PR. Otherwise I can do it, citing you as the source.

[nagisa]

Documentation for the functions should specify which orderings are valid or not (e.g. fetch_order for fetch_update does not permit AcqRel or Release).

[RalfJung]

The ordering argument names are also not entirely correct -- set_order is also used for the the successful load. The two modes should probably be called success and failure, with failure also used for the load.

EDIT: Oh, the argument order is the wrong way around compared to compare_exchange. Dang :/

EDIT2: Also see #53106.

[RalfJung]

Is it worth mentioning that for the case where f always returns Some and never panics, there really is no reason not to use Relaxed as load ordering? A final successful CAS is going to happen, which is sufficient for synchronization. No need to use anything stronger for all the loads and failed CASes.

[nikolads]

Is Result the correct return type? Unlike the compare_exchange functions here an Err result doesn't indicate that the function failed to do something, it indicates that f returned None.

My concern is that Result is marked as #[must_use] and here a common use case will be that you are not interested in the result value. So you will write code like let _ = x.fetch_update(...);.

Maybe a custom enum with Updated and NotUpdated variants can be used. But then you will have to import an additional type if you are interested in the result and want to pattern match it.

[mystor]

Stumbled across this method today, and figured I'd prod this issue & drop in my bikeshed 2¢.

I pulled the Weak::upgrade method as an example from the stdlib, and translated it roughly to the new API, formatted with rustfmt, as an example:

// We use a CAS loop to increment the strong count instead of a
// fetch_add because once the count hits 0 it must never be above 0.
let inner = self.inner()?;

// Relaxed load because any write of 0 that we can observe leaves the
// field in a permanently zero state (so a "stale" read of 0 is fine),
// and any other value is confirmed via the CAS.
inner
    .strong
    .fetch_update(
        |n| {
            if n == 0 {
                return None;
            }

            // See comments in `Arc::clone` for why we do this (for `mem::forget`).
            if n > MAX_REFCOUNT {
                unsafe {
                    abort();
                }
            }

            Some(n + 1)
        },
        Relaxed,
        Relaxed,
    )
    .ok()
    .map(|_| Arc {
        // null checked above
        ptr: self.ptr,
        phantom: PhantomData,
    })

A few things I've noticed:

1. This particular usecase has a fairly textually long update parameter, which forces the method into the multi-line format used by rustfmt. If we moved the ordering parameters before the lambda parameter, it would end up looking a bit cleaner:

inner
    .strong
    .fetch_update(Relaxed, Relaxed, |n| {
        if n == 0 {
            return None;
        }

        // See comments in `Arc::clone` for why we do this (for `mem::forget`).
        if n > MAX_REFCOUNT {
            unsafe {
                abort();
            }
        }

        Some(n + 1)
    })

2. The ordering parameters are in the opposite order to compare_exchange (although this doesn't come up in this particular case). It might be more straightforward for code to move over if the order was consistent.

3. The return value being a Result doesn't bother me, as I don't have any use cases currently which wouldn't want to match on it in some way. If we'd like to make it non-essential to match on, a tuple return type could potentially be used, like (usize, Option<usize>), where the first is the previous value, and the second is the new value returned by the last call to the passed-in lambda.

4. I also noticed that this method doesn't appear to exist for AtomicBool or AtomicPtr. It may be nice to add this method to those types too before stabilization.

In summary, I think I'd move the lambda parameter after the two ordering parameters, and make them match the parameter order used by the compare_exchange method.

Other than that, this seems like a handy API which makes writing CAS loops much cleaner, and I'd be happy to see it stabilized.

[sfackler]

I've opened a PR to stabilize fetch_update with @mystor's suggested tweaks: #71843.

[jplatte]

fetch_update has been stabilized in #71843, fetch_min and fetch_max in #72324. This tracking issue can be closed, right?