ABA-problem with pointer provenance in lockless queues #121950

joboet · 2024-03-03T20:21:35Z

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.

The text was updated successfully, but these errors were encountered:

the8472 · 2024-03-03T20:28:20Z

Since this is mac-specific why not use a DWCAS? Afaik they don't have any hardware that doesn't have those.

joboet · 2024-03-03T20:33:49Z

It's not mac-specific, though. Once gets used on all platforms except the futex ones, I believe even Windows. RwLock gets used on NetBSD and other UNIXes as well, and I'd like to use it to get rid of the unsound SGX lock implementations. So we need to find something portable here.

Also, this is a provenance-only problem, so I'd like to avoid anything that makes the machine code less efficient, because in terms of what is actually generated, the current implementation is perfectly bug-free. It "just" violates the memory model.

the8472 · 2024-03-03T20:57:55Z

And using the return value from the CAS (the Ok(_)) and working on that instead of state doesn't work either?

joboet · 2024-03-03T20:59:45Z

No, because the old pointer is stored inside the node, and we can't retroactively update the pointer, because a traversal operation could access the old one immediately after the compare_exchange.

saethlin · 2024-03-03T21:06:33Z

to make miri/LLVM guess the right provenance.

I don't think LLVM implements expose semantics in any sense, so I suspect doing the expose dance here wouldn't change LLVM's view of the code. (Happy to be corrected on this)

joboet · 2024-03-03T21:12:38Z

LLVM's pointer aliasing rules mention that the pointer resulting from inttoptr is based on "all pointer values that contribute (directly or indirectly) to the computation of the pointer’s value". IIUC, that means that because the traversing thread reads the current pointer from state and uses it to load the integer that is then passed to inttoptr, the resulting pointer will also be based on the current pointer, making the code sound.

RalfJung · 2024-03-03T21:48:00Z

Also, this is a provenance-only problem, so I'd like to avoid anything that makes the machine code less efficient, because in terms of what is actually generated, the current implementation is perfectly bug-free. It "just" violates the memory model.

That is assuming that we don't have optimizations that make full use of the provenance model. Or have you inspected the generated assembly to be sure?

This looks extremely related to rust-lang/unsafe-code-guidelines#480 to me. I wonder if the CAS semantics I proposed here would help.

joboet · 2024-03-03T21:53:07Z

I inspected the assembly of a simplified version (I removed the Thread handle and park operations). Also, the Once implementation has existed for ~9 years, with no issue encountered.

saethlin · 2024-03-03T21:56:24Z

The age of an implementation is not an indicator of its soundness with respect to provenance rules. If anything, perhaps the correlation runs the other direction.

I'm willing to review codegen tests for suspicious things like this, if someone can find a way to write them that's both effective and doesn't make them break often. I don't think we usually check in codegen tests for structures as complex as this.

apiraino · 2024-03-05T11:41:01Z

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize P-medium

RalfJung · 2024-03-05T11:44:26Z

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.

Just recording here that another possible solution has been sketched, also spelled out here.

rwlock: disable 'frob' test in Miri on macOS Due to rust-lang#121950, Miri will sometimes complain about this test on macOS. Better disable the test, as otherwise it can fail for unrelated PRs. r? `@joboet`

rwlock: disable 'frob' test in Miri on macOS Due to rust-lang#121950, Miri will sometimes complain about this test on macOS. Better disable the test, as otherwise it can fail for unrelated PRs. r? ``@joboet``

Rollup merge of rust-lang#128640 - RalfJung:rwlock-macos-miri, r=joboet rwlock: disable 'frob' test in Miri on macOS Due to rust-lang#121950, Miri will sometimes complain about this test on macOS. Better disable the test, as otherwise it can fail for unrelated PRs. r? ``@joboet``

Noratrieb removed the needs-triage This issue may need triage. Remove it if it has been sufficiently triaged. label Mar 3, 2024

joboet added the A-atomic Area: atomics, barriers, and sync primitives label Mar 3, 2024

RalfJung mentioned this issue Mar 3, 2024

Stacked Borrows violation in macOS RwLock #121626

Closed

rustbot added P-medium Medium priority and removed I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels Mar 5, 2024

RalfJung mentioned this issue Mar 5, 2024

Expressivity Gap: concurrent ABA-safe stack (atomics provenance = pain) rust-lang/unsafe-code-guidelines#480

Open

joboet mentioned this issue Mar 15, 2024

Fix provenance-ABA in lockless queues using fuzzy provenance #122541

Closed

joboet mentioned this issue Jul 22, 2024

Rollup of 7 pull requests #128039

Closed

workingjubilee mentioned this issue Jul 22, 2024

Did miri spot a concurrency bug taking RwLockWriteGuard? #128052

Closed

RalfJung mentioned this issue Aug 4, 2024

rwlock: disable 'frob' test in Miri on macOS #128640

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ABA-problem with pointer provenance in lockless queues #121950

ABA-problem with pointer provenance in lockless queues #121950

joboet commented Mar 3, 2024 •

edited

Loading

the8472 commented Mar 3, 2024

joboet commented Mar 3, 2024 •

edited

Loading

the8472 commented Mar 3, 2024 •

edited

Loading

joboet commented Mar 3, 2024

saethlin commented Mar 3, 2024 •

edited

Loading

joboet commented Mar 3, 2024

RalfJung commented Mar 3, 2024

joboet commented Mar 3, 2024

saethlin commented Mar 3, 2024 •

edited

Loading

apiraino commented Mar 5, 2024

RalfJung commented Mar 5, 2024 •

edited

Loading

ABA-problem with pointer provenance in lockless queues #121950

ABA-problem with pointer provenance in lockless queues #121950

Comments

joboet commented Mar 3, 2024 • edited Loading

Possible solutions

the8472 commented Mar 3, 2024

joboet commented Mar 3, 2024 • edited Loading

the8472 commented Mar 3, 2024 • edited Loading

joboet commented Mar 3, 2024

saethlin commented Mar 3, 2024 • edited Loading

joboet commented Mar 3, 2024

RalfJung commented Mar 3, 2024

joboet commented Mar 3, 2024

saethlin commented Mar 3, 2024 • edited Loading

apiraino commented Mar 5, 2024

RalfJung commented Mar 5, 2024 • edited Loading

joboet commented Mar 3, 2024 •

edited

Loading

joboet commented Mar 3, 2024 •

edited

Loading

the8472 commented Mar 3, 2024 •

edited

Loading

saethlin commented Mar 3, 2024 •

edited

Loading

saethlin commented Mar 3, 2024 •

edited

Loading

RalfJung commented Mar 5, 2024 •

edited

Loading