Rollup merge of #101774 - Riolku:atomic-update-aba, r=m-ou-se

Warn about safety of `fetch_update`

Specifically as it relates to the ABA problem.

`fetch_update` is a useful function, and one that isn't provided by, say, C++. However, this does not mean the function is magic. It is implemented in terms of `compare_exchange_weak`, and in particular, suffers from the ABA problem. See the following code, which is a naive implementation of `pop` in a lock-free queue:

```rust
fn pop(&self) -> Option<i32> {
    self.front.fetch_update(Ordering::Relaxed, Ordering::Acquire, |front| {
        if front == ptr::null_mut() {
            None
        }
        else {
            Some(unsafe { (*front).next })
        }
    }.ok()
}
```

This code is unsound if called from multiple threads because of the ABA problem. Specifically, suppose nodes are allocated with `Box`. Suppose the following sequence happens:

```
Initial: Queue is X -> Y.

Thread A: Starts popping, is pre-empted.
Thread B: Pops successfully, twice, leaving the queue empty.
Thread C: Pushes, and `Box` returns X (very common for allocators)
Thread A: Wakes up, sees the head is still X, and stores Y as the new head.
```

But `Y` is deallocated. This is undefined behaviour.

Adding a note about this problem to `fetch_update` should hopefully prevent users from being misled, and also, a link to this common problem is, in my opinion, an improvement to our docs on atomics.

1 files changed, 26 insertions, 0 deletions

diff --git a/library/core/src/sync/atomic.rs b/library/core/src/sync/atomic.rs
index 3c96290fc53..6c70517d965 100644
--- a/library/core/src/sync/atomic.rs
+++ b/library/core/src/sync/atomic.rs
@@ -955,6 +955,14 @@ impl AtomicBool {
     /// **Note:** This method is only available on platforms that support atomic
     /// operations on `u8`.
     ///
+    /// # Considerations
+    ///
+    /// This method is not magic;  it is not provided by the hardware.
+    /// It is implemented in terms of [`AtomicBool::compare_exchange_weak`], and suffers from the same drawbacks.
+    /// In particular, this method will not circumvent the [ABA Problem].
+    ///
+    /// [ABA Problem]: https://en.wikipedia.org/wiki/ABA_problem
+    ///
     /// # Examples
     ///
     /// ```rust
@@ -1422,6 +1430,14 @@ impl<T> AtomicPtr<T> {
     /// **Note:** This method is only available on platforms that support atomic
     /// operations on pointers.
     ///
+    /// # Considerations
+    ///
+    /// This method is not magic;  it is not provided by the hardware.
+    /// It is implemented in terms of [`AtomicPtr::compare_exchange_weak`], and suffers from the same drawbacks.
+    /// In particular, this method will not circumvent the [ABA Problem].
+    ///
+    /// [ABA Problem]: https://en.wikipedia.org/wiki/ABA_problem
+    ///
     /// # Examples
     ///
     /// ```rust
@@ -2510,6 +2526,16 @@ macro_rules! atomic_int {
             /// **Note**: This method is only available on platforms that support atomic operations on
             #[doc = concat!("[`", $s_int_type, "`].")]
             ///
+            /// # Considerations
+            ///
+            /// This method is not magic;  it is not provided by the hardware.
+            /// It is implemented in terms of
+            #[doc = concat!("[`", stringify!($atomic_type), "::compare_exchange_weak`],")]
+            /// and suffers from the same drawbacks.
+            /// In particular, this method will not circumvent the [ABA Problem].
+            ///
+            /// [ABA Problem]: https://en.wikipedia.org/wiki/ABA_problem
+            ///
             /// # Examples
             ///
             /// ```rust