Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Lift unnecessary restriction on CAS failure ordering #68464

Closed
tmiasko opened this issue Jan 22, 2020 · 8 comments · Fixed by #98383
Closed

Lift unnecessary restriction on CAS failure ordering #68464

tmiasko opened this issue Jan 22, 2020 · 8 comments · Fixed by #98383
Assignees
@m-ou-se
Labels
A-concurrency Area: Concurrency C-enhancement Category: An issue proposing an enhancement or a PR with one. T-lang Relevant to the language team, which will review and decide on the PR/issue. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@tmiasko
Copy link
Contributor

tmiasko commented Jan 22, 2020 •
edited
Loading

Currently compare_exchange requires the failure ordering to "be equivalent to
or weaker than a success ordering". On the other hand C11/C++11 requires only
that "failure shall be no stronger than the success", which arguably means that
one can write e.g. compare_exchange(..., Release, Acquire) in C/C++ but not in Rust.

Arguably, because neither C11 standard nor C++11 standard defines what it means
for an ordering to be stronger from another. When the issue was raised in
LWG2445, the proposed and accepted resolution was to lift those restrictions
altogether, leaving only requirement that "the failure argument shall not be
memory_order_release nor memory_order_acq_rel".

It would be beneficial to remove success/failure ordering restrictions for
reasons described in C++ proposal P0418r2.

EDIT: Restrictions were lifted in clang & LLVM:
@tmiasko tmiasko mentioned this issue Jan 22, 2020
Merged
@Amanieu Amanieu added the T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. label Jan 22, 2020
@jonas-schievink jonas-schievink added A-concurrency Area: Concurrency C-enhancement Category: An issue proposing an enhancement or a PR with one. labels Jan 22, 2020
@Centril Centril added the T-lang Relevant to the language team, which will review and decide on the PR/issue. label Jan 22, 2020
@tmiasko
Copy link
Contributor Author

tmiasko commented Jul 17, 2020

Blocked on https://bugs.llvm.org/show_bug.cgi?id=33332. The cmpxchg release acquire is accepted by LLVM but miscompiled on AArch64.

@tmiasko tmiasko mentioned this issue Jul 21, 2020
Closed
@tmiasko tmiasko self-assigned this May 26, 2022
@tmiasko tmiasko mentioned this issue May 26, 2022
Closed
@m-ou-se
Copy link
Member

m-ou-se commented May 26, 2022

@tmiasko I'm about to send a PR that implements this.

@m-ou-se m-ou-se mentioned this issue May 26, 2022
Merged
@tmiasko
Copy link
Contributor Author

tmiasko commented May 26, 2022

@m-ou-se I do have implementation ready as well, but that's fine, I can review instead :-).

@m-ou-se
Copy link
Member

m-ou-se commented May 26, 2022

I split it in a PR that renames the intrinsics first, and a separate PR for exposing the new ordering combinations afterwards.

@tmiasko tmiasko assigned m-ou-se and unassigned tmiasko May 29, 2022
@m-ou-se m-ou-se mentioned this issue Jun 22, 2022
Merged
@m-ou-se
Copy link
Member

m-ou-se commented Jun 22, 2022

Looks like llvm 12 doesn't support this: #98383 (comment)

Can we make things conditionally fall back to a stronger ordering depending on the llvm version? I don't think we do anything like that in the library right now, but maybe the compiler already does things differently for different llvm versions?

@m-ou-se
Copy link
Member

m-ou-se commented Jun 22, 2022 •
edited
Loading

Ah yes, some code checks llvm_util::get_version() < (13, 0, 0). I suppose Builder::atomic_cmpxchg could check the same, and upgrade the ordering if necessary in that case.

@m-ou-se m-ou-se mentioned this issue Jun 22, 2022
Merged
@m-ou-se
Copy link
Member

m-ou-se commented Jun 22, 2022 •
edited
Loading

Did exactly that in #98385

@m-ou-se
Copy link
Member

m-ou-se commented Jun 22, 2022 •
edited by tmiasko
Loading

To do:

JohnTitor added a commit to JohnTitor/rust that referenced this issue Jun 26, 2022
@JohnTitor
Rollup merge of rust-lang#98385 - m-ou-se:llvm-12-memory-order, r=pet…
7c39776 
…rochenkov

Work around llvm 12's memory ordering restrictions.

Older llvm has the pre-C++17 restriction on success and failure memory ordering, requiring the former to be at least as strong as the latter. So, for llvm 12, this upgrades the success ordering to a stronger one if necessary.

See rust-lang#68464
Dylan-DPC added a commit to Dylan-DPC/rust that referenced this issue Jun 26, 2022
@Dylan-DPC
Rollup merge of rust-lang#97423 - m-ou-se:memory-ordering-intrinsics,…
683631a 
… r=tmiasko

Simplify memory ordering intrinsics

This changes the names of the atomic intrinsics to always fully include their memory ordering arguments.

```diff
- atomic_cxchg
+ atomic_cxchg_seqcst_seqcst

- atomic_cxchg_acqrel
+ atomic_cxchg_acqrel_release

- atomic_cxchg_acqrel_failrelaxed
+ atomic_cxchg_acqrel_relaxed

// And so on.
```

- `seqcst` is no longer implied
- The failure ordering on chxchg is no longer implied in some cases, but now always explicitly part of the name.
- `release` is no longer shortened to just `rel`. That was especially confusing, since `relaxed` also starts with `rel`.
- `acquire` is no longer shortened to just `acq`, such that the names now all match the `std::sync::atomic::Ordering` variants exactly.
- This now allows for more combinations on the compare exchange operations, such as `atomic_cxchg_acquire_release`, which is necessary for rust-lang#68464.
- This PR only exposes the new possibilities through unstable intrinsics, but not yet through the stable API. That's for [a separate PR](rust-lang#98383) that requires an FCP.

Suffixes for operations with a single memory order:

| Order   | Before       | After      |
|---------|--------------|------------|
| Relaxed | `_relaxed`   | `_relaxed` |
| Acquire | `_acq`       | `_acquire` |
| Release | `_rel`       | `_release` |
| AcqRel  | `_acqrel`    | `_acqrel`  |
| SeqCst  | (none)       | `_seqcst`  |

Suffixes for compare-and-exchange operations with two memory orderings:

| Success | Failure | Before                   | After              |
|---------|---------|--------------------------|--------------------|
| Relaxed | Relaxed | `_relaxed`               | `_relaxed_relaxed` |
| Relaxed | Acquire | ❌                      | `_relaxed_acquire` |
| Relaxed | SeqCst  | ❌                      | `_relaxed_seqcst`  |
| Acquire | Relaxed | `_acq_failrelaxed`       | `_acquire_relaxed` |
| Acquire | Acquire | `_acq`                   | `_acquire_acquire` |
| Acquire | SeqCst  | ❌                      | `_acquire_seqcst`  |
| Release | Relaxed | `_rel`                   | `_release_relaxed` |
| Release | Acquire | ❌                      | `_release_acquire` |
| Release | SeqCst  | ❌                      | `_release_seqcst`  |
| AcqRel  | Relaxed | `_acqrel_failrelaxed`    | `_acqrel_relaxed`  |
| AcqRel  | Acquire | `_acqrel`                | `_acqrel_acquire`  |
| AcqRel  | SeqCst  | ❌                      | `_acqrel_seqcst`   |
| SeqCst  | Relaxed | `_failrelaxed`           | `_seqcst_relaxed`  |
| SeqCst  | Acquire | `_failacq`               | `_seqcst_acquire`  |
| SeqCst  | SeqCst  | (none)                   | `_seqcst_seqcst`   |
Dylan-DPC added a commit to Dylan-DPC/rust that referenced this issue Jun 26, 2022
@Dylan-DPC
Rollup merge of rust-lang#97423 - m-ou-se:memory-ordering-intrinsics,…
04ef53f 
… r=tmiasko

Simplify memory ordering intrinsics

This changes the names of the atomic intrinsics to always fully include their memory ordering arguments.

```diff
- atomic_cxchg
+ atomic_cxchg_seqcst_seqcst

- atomic_cxchg_acqrel
+ atomic_cxchg_acqrel_release

- atomic_cxchg_acqrel_failrelaxed
+ atomic_cxchg_acqrel_relaxed

// And so on.
```

- `seqcst` is no longer implied
- The failure ordering on chxchg is no longer implied in some cases, but now always explicitly part of the name.
- `release` is no longer shortened to just `rel`. That was especially confusing, since `relaxed` also starts with `rel`.
- `acquire` is no longer shortened to just `acq`, such that the names now all match the `std::sync::atomic::Ordering` variants exactly.
- This now allows for more combinations on the compare exchange operations, such as `atomic_cxchg_acquire_release`, which is necessary for rust-lang#68464.
- This PR only exposes the new possibilities through unstable intrinsics, but not yet through the stable API. That's for [a separate PR](rust-lang#98383) that requires an FCP.

Suffixes for operations with a single memory order:

| Order   | Before       | After      |
|---------|--------------|------------|
| Relaxed | `_relaxed`   | `_relaxed` |
| Acquire | `_acq`       | `_acquire` |
| Release | `_rel`       | `_release` |
| AcqRel  | `_acqrel`    | `_acqrel`  |
| SeqCst  | (none)       | `_seqcst`  |

Suffixes for compare-and-exchange operations with two memory orderings:

| Success | Failure | Before                   | After              |
|---------|---------|--------------------------|--------------------|
| Relaxed | Relaxed | `_relaxed`               | `_relaxed_relaxed` |
| Relaxed | Acquire | ❌                      | `_relaxed_acquire` |
| Relaxed | SeqCst  | ❌                      | `_relaxed_seqcst`  |
| Acquire | Relaxed | `_acq_failrelaxed`       | `_acquire_relaxed` |
| Acquire | Acquire | `_acq`                   | `_acquire_acquire` |
| Acquire | SeqCst  | ❌                      | `_acquire_seqcst`  |
| Release | Relaxed | `_rel`                   | `_release_relaxed` |
| Release | Acquire | ❌                      | `_release_acquire` |
| Release | SeqCst  | ❌                      | `_release_seqcst`  |
| AcqRel  | Relaxed | `_acqrel_failrelaxed`    | `_acqrel_relaxed`  |
| AcqRel  | Acquire | `_acqrel`                | `_acqrel_acquire`  |
| AcqRel  | SeqCst  | ❌                      | `_acqrel_seqcst`   |
| SeqCst  | Relaxed | `_failrelaxed`           | `_seqcst_relaxed`  |
| SeqCst  | Acquire | `_failacq`               | `_seqcst_acquire`  |
| SeqCst  | SeqCst  | (none)                   | `_seqcst_seqcst`   |
Dylan-DPC added a commit to Dylan-DPC/rust that referenced this issue Jun 28, 2022
@Dylan-DPC
Rollup merge of rust-lang#97423 - m-ou-se:memory-ordering-intrinsics,…
0bd783c 
… r=tmiasko

Simplify memory ordering intrinsics

This changes the names of the atomic intrinsics to always fully include their memory ordering arguments.

```diff
- atomic_cxchg
+ atomic_cxchg_seqcst_seqcst

- atomic_cxchg_acqrel
+ atomic_cxchg_acqrel_release

- atomic_cxchg_acqrel_failrelaxed
+ atomic_cxchg_acqrel_relaxed

// And so on.
```

- `seqcst` is no longer implied
- The failure ordering on chxchg is no longer implied in some cases, but now always explicitly part of the name.
- `release` is no longer shortened to just `rel`. That was especially confusing, since `relaxed` also starts with `rel`.
- `acquire` is no longer shortened to just `acq`, such that the names now all match the `std::sync::atomic::Ordering` variants exactly.
- This now allows for more combinations on the compare exchange operations, such as `atomic_cxchg_acquire_release`, which is necessary for rust-lang#68464.
- This PR only exposes the new possibilities through unstable intrinsics, but not yet through the stable API. That's for [a separate PR](rust-lang#98383) that requires an FCP.

Suffixes for operations with a single memory order:

| Order   | Before       | After      |
|---------|--------------|------------|
| Relaxed | `_relaxed`   | `_relaxed` |
| Acquire | `_acq`       | `_acquire` |
| Release | `_rel`       | `_release` |
| AcqRel  | `_acqrel`    | `_acqrel`  |
| SeqCst  | (none)       | `_seqcst`  |

Suffixes for compare-and-exchange operations with two memory orderings:

| Success | Failure | Before                   | After              |
|---------|---------|--------------------------|--------------------|
| Relaxed | Relaxed | `_relaxed`               | `_relaxed_relaxed` |
| Relaxed | Acquire | ❌                      | `_relaxed_acquire` |
| Relaxed | SeqCst  | ❌                      | `_relaxed_seqcst`  |
| Acquire | Relaxed | `_acq_failrelaxed`       | `_acquire_relaxed` |
| Acquire | Acquire | `_acq`                   | `_acquire_acquire` |
| Acquire | SeqCst  | ❌                      | `_acquire_seqcst`  |
| Release | Relaxed | `_rel`                   | `_release_relaxed` |
| Release | Acquire | ❌                      | `_release_acquire` |
| Release | SeqCst  | ❌                      | `_release_seqcst`  |
| AcqRel  | Relaxed | `_acqrel_failrelaxed`    | `_acqrel_relaxed`  |
| AcqRel  | Acquire | `_acqrel`                | `_acqrel_acquire`  |
| AcqRel  | SeqCst  | ❌                      | `_acqrel_seqcst`   |
| SeqCst  | Relaxed | `_failrelaxed`           | `_seqcst_relaxed`  |
| SeqCst  | Acquire | `_failacq`               | `_seqcst_acquire`  |
| SeqCst  | SeqCst  | (none)                   | `_seqcst_seqcst`   |
Dylan-DPC added a commit to Dylan-DPC/rust that referenced this issue Jun 29, 2022
@Dylan-DPC
Rollup merge of rust-lang#97423 - m-ou-se:memory-ordering-intrinsics,…
45740ac 
… r=tmiasko

Simplify memory ordering intrinsics

This changes the names of the atomic intrinsics to always fully include their memory ordering arguments.

```diff
- atomic_cxchg
+ atomic_cxchg_seqcst_seqcst

- atomic_cxchg_acqrel
+ atomic_cxchg_acqrel_release

- atomic_cxchg_acqrel_failrelaxed
+ atomic_cxchg_acqrel_relaxed

// And so on.
```

- `seqcst` is no longer implied
- The failure ordering on chxchg is no longer implied in some cases, but now always explicitly part of the name.
- `release` is no longer shortened to just `rel`. That was especially confusing, since `relaxed` also starts with `rel`.
- `acquire` is no longer shortened to just `acq`, such that the names now all match the `std::sync::atomic::Ordering` variants exactly.
- This now allows for more combinations on the compare exchange operations, such as `atomic_cxchg_acquire_release`, which is necessary for rust-lang#68464.
- This PR only exposes the new possibilities through unstable intrinsics, but not yet through the stable API. That's for [a separate PR](rust-lang#98383) that requires an FCP.

Suffixes for operations with a single memory order:

| Order   | Before       | After      |
|---------|--------------|------------|
| Relaxed | `_relaxed`   | `_relaxed` |
| Acquire | `_acq`       | `_acquire` |
| Release | `_rel`       | `_release` |
| AcqRel  | `_acqrel`    | `_acqrel`  |
| SeqCst  | (none)       | `_seqcst`  |

Suffixes for compare-and-exchange operations with two memory orderings:

| Success | Failure | Before                   | After              |
|---------|---------|--------------------------|--------------------|
| Relaxed | Relaxed | `_relaxed`               | `_relaxed_relaxed` |
| Relaxed | Acquire | ❌                      | `_relaxed_acquire` |
| Relaxed | SeqCst  | ❌                      | `_relaxed_seqcst`  |
| Acquire | Relaxed | `_acq_failrelaxed`       | `_acquire_relaxed` |
| Acquire | Acquire | `_acq`                   | `_acquire_acquire` |
| Acquire | SeqCst  | ❌                      | `_acquire_seqcst`  |
| Release | Relaxed | `_rel`                   | `_release_relaxed` |
| Release | Acquire | ❌                      | `_release_acquire` |
| Release | SeqCst  | ❌                      | `_release_seqcst`  |
| AcqRel  | Relaxed | `_acqrel_failrelaxed`    | `_acqrel_relaxed`  |
| AcqRel  | Acquire | `_acqrel`                | `_acqrel_acquire`  |
| AcqRel  | SeqCst  | ❌                      | `_acqrel_seqcst`   |
| SeqCst  | Relaxed | `_failrelaxed`           | `_seqcst_relaxed`  |
| SeqCst  | Acquire | `_failacq`               | `_seqcst_acquire`  |
| SeqCst  | SeqCst  | (none)                   | `_seqcst_seqcst`   |
JohnTitor added a commit to JohnTitor/rust that referenced this issue Jul 17, 2022
@JohnTitor
Rollup merge of rust-lang#98383 - m-ou-se:remove-memory-order-restric…
4a3d780 
…tions, r=joshtriplett

Remove restrictions on compare-exchange memory ordering.

We currently don't allow the failure memory ordering of compare-exchange operations to be stronger than the success ordering, as was the case in C++11 when its memory model was copied to Rust. However, this restriction was lifted in C++17 as part of [p0418r2](https://wg21.link/p0418r2). It's time  we lift the restriction too.

| Success | Failure | Before | After |
|---------|---------|--------|-------|
| Relaxed | Relaxed | ✔️ | ✔️ |
| Relaxed | Acquire | ❌                | ✔️ |
| Relaxed | SeqCst  | ❌                | ✔️ |
| Acquire | Relaxed | ✔️ | ✔️ |
| Acquire | Acquire | ✔️ | ✔️ |
| Acquire | SeqCst  | ❌                | ✔️ |
| Release | Relaxed | ✔️ | ✔️ |
| Release | Acquire | ❌                | ✔️ |
| Release | SeqCst  | ❌                | ✔️ |
| AcqRel  | Relaxed | ✔️ | ✔️ |
| AcqRel  | Acquire | ✔️ | ✔️ |
| AcqRel  | SeqCst  | ❌                | ✔️ |
| SeqCst  | Relaxed | ✔️ | ✔️ |
| SeqCst  | Acquire | ✔️ | ✔️ |
| SeqCst  | SeqCst  | ✔️ | ✔️ |
| \*      | Release | ❌                | ❌                |
| \*      | AcqRel  | ❌                | ❌                |

Fixes rust-lang#68464
@bors bors closed this as completed in 796bc7c Jul 18, 2022
@m-ou-se m-ou-se reopened this Jul 18, 2022
workingjubilee pushed a commit to tcdi/postgrestd that referenced this issue Sep 15, 2022
@JohnTitor
Rollup merge of #98383 - m-ou-se:remove-memory-order-restrictions, r=…
0d333ea 
…joshtriplett

Remove restrictions on compare-exchange memory ordering.

We currently don't allow the failure memory ordering of compare-exchange operations to be stronger than the success ordering, as was the case in C++11 when its memory model was copied to Rust. However, this restriction was lifted in C++17 as part of [p0418r2](https://wg21.link/p0418r2). It's time  we lift the restriction too.

| Success | Failure | Before | After |
|---------|---------|--------|-------|
| Relaxed | Relaxed | ✔️ | ✔️ |
| Relaxed | Acquire | ❌                | ✔️ |
| Relaxed | SeqCst  | ❌                | ✔️ |
| Acquire | Relaxed | ✔️ | ✔️ |
| Acquire | Acquire | ✔️ | ✔️ |
| Acquire | SeqCst  | ❌                | ✔️ |
| Release | Relaxed | ✔️ | ✔️ |
| Release | Acquire | ❌                | ✔️ |
| Release | SeqCst  | ❌                | ✔️ |
| AcqRel  | Relaxed | ✔️ | ✔️ |
| AcqRel  | Acquire | ✔️ | ✔️ |
| AcqRel  | SeqCst  | ❌                | ✔️ |
| SeqCst  | Relaxed | ✔️ | ✔️ |
| SeqCst  | Acquire | ✔️ | ✔️ |
| SeqCst  | SeqCst  | ✔️ | ✔️ |
| \*      | Release | ❌                | ❌                |
| \*      | AcqRel  | ❌                | ❌                |

Fixes rust-lang/rust#68464
@tmiasko tmiasko closed this as completed Sep 23, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@m-ou-se m-ou-se

Labels
A-concurrency Area: Concurrency C-enhancement Category: An issue proposing an enhancement or a PR with one. T-lang Relevant to the language team, which will review and decide on the PR/issue. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Remove restrictions on compare-exchange memory ordering. m-ou-se/rust
5 participants
@Amanieu @m-ou-se @Centril @jonas-schievink @tmiasko