ABA-problem with pointer provenance in lockless queues

Both lockless queue implementations inside std for Once and RwLock suffer from the ABA problem, resulting in unsoundness.

In both cases, the enqueue operation roughly looks like the following:

struct Node {
    next: *mut Node,
}

struct Queue {
    state: AtomicPtr<Node>,
}

let mut state = queue.state.load();
loop {
    node.next = to_node(state); // Some pointer masking
    let next = to_state(node); // Some bittagging
    match state.compare_exchange(state, next) {
        Ok(_) => break,
        Err(new) => state = next,
    }
}

This code is problematic, because it allows the following to occur:

1. Thread 1: Append node 1 to the queue.
2. Thread 2: Load the state (a pointer to node 1) and store it as the next pointer of node 2.
3. Thread 1: Remove node 1 from the queue and deallocate it/modify it.
4. Thread 1: Create node 3 at the same address as node 1 and append it to the queue.
5. Thread 2: Perform the CAS. Because the state has the same bits, this succeeds.

Now, any traversal operation on the queue that attempts to dereference the next pointer of node 2 exhibits UB, as the pointer, while having the right address, only has provenance to node 1, which is no longer valid, but may not access node 3.

This is of little practical concern, as it is extremely unlikely that LLVM will perform a problematic optimization; but nevertheless the code is unsound, both under stacked-borrows and LLVM's semantics.

This is the cause of #121626, where this exact situation led to a (correct) UB report from miri.

@rustbot label +T-libs +I-unsound

Possible solutions

The only solution I see at the moment is to use fuzzy provenance and use from_exposed_provenance inside the traversal operation to make miri/LLVM guess the right provenance.

Start with the lockless queue implementations used by std's Once and RwLock, then read issue #121626 and its Miri UB report. Determine how the enqueue and traversal operations handle pointer provenance and ABA reuse; done means removing the reported unsoundness and verifying the affected behavior against the described scenario.