Skip to content

ABA-problem with pointer provenance in lockless queues #121950

Open
@joboet

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:

  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.

Metadata

Assignees

No one assigned

    Labels

    A-atomicArea: Atomics, barriers, and sync primitivesI-unsoundIssue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/SoundnessP-mediumMedium priorityT-libsRelevant to the library team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions