ABA-problem with pointer provenance in lockless queues #121950
Description
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:
- Thread 1: Append node 1 to the queue.
- Thread 2: Load the state (a pointer to node 1) and store it as the
next
pointer of node 2. - Thread 1: Remove node 1 from the queue and deallocate it/modify it.
- Thread 1: Create node 3 at the same address as node 1 and append it to the queue.
- 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.