]> git.lizzy.rs Git - rust.git/commit - library/std/src/os/fd/raw.rs
Rollup merge of #101774 - Riolku:atomic-update-aba, r=m-ou-se
authorMatthias Krüger <matthias.krueger@famsik.de>
Tue, 11 Oct 2022 16:59:46 +0000 (18:59 +0200)
committerGitHub <noreply@github.com>
Tue, 11 Oct 2022 16:59:46 +0000 (18:59 +0200)
commitd13f7aef7042dbb37be17b30a2f048dc0ed56f82
tree60455cf48725932b51eec6deec6a6b1835ab31d2
parentcadb37a8c7811773d2831b95f7554a36a52f53b0
parent3d28a1ad761f4106e62e90ceebb209af533a1f24
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.