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.

0 files changed, 0 insertions, 0 deletions