target

integration into IS ISO/IEC 9899:202y

document history

This document is based on Defang and deprecate memory_order::consume by Hans Boehm, which has been accepted into C++26.

1 Introduction

It is widely accepted that the current definition of the concept of consume operations and of the corresponding memory order memory_order_consume (memory_order::consume for C++) in the C standard is not useful: all current compilers essentially map it to memory_order_acquire. We propose to completely remove the notion from the C standard and to phase out the associated features.

2 Problem description

Memory order “consume” is a concept that is meant to be less restrictive than “acquire” by relaxing the requirement on the receiving side of an atomic operation. The relaxation is basically that instead of locally relying on the sequenced before relation for the ordering (which is a temporal relationship) it is based on a concept of “dependency”, the term referring in that case to a data-flow dependency.

Difficulties with the concept appear to be multiple:

• There is a high implementation complexity necessary to be able to profit from the operation.
• The current definition uses a fairly general definition of “dependency”, thus requiring frequent and inconvenient use of invocations of the kill_dependency macro (and additionally the [[carries_dependency]] attribute in C++).
• The current definition of “happens before” is not transitive.

It is also widely accepted that memory_order_consume could have frequent and important use cases in many large code bases. For example, the Linux kernel makes extensive use of RCU. To avoid over-constraining memory order for something like RCU on architectures like ARM and Power something like memory_order_consume is required. Some core Android code similarly relies on dependency-based ordering.

On the other hand, there are strong arguments that we are not likely to introduce a new facility that can benefit significantly from the existing wording, and that we therefor should remove it:

1. This problem has been recognized for around a decade. In particular in the C++ community there have been much discussion around it and possible replacements, but there was no agreement on such a replacement. Even serious issues with its current specification have not been fixed.
2. It complicates the memory model appreciably. More mathematical academic work tends to ignore its existence, since it is known to be broken. This makes it harder to translate such work into the standard. The memory models of C and C++ are in some need of tricky repair. It would be nice to avoid this unused complication.
3. The most widely-used CPU architectures no longer really require memory_order_consume.
   • It was never very beneficial on X86.
   • ARM provides hardware support for memory_order_acquire (and memory_order_seq_cst) loads that, for common micro-architectures and use-cases, perform similarly to memory_order_relaxed. The accepted C++ paper has a comparison of microbenchmark between memory_order_relaxed vs. memory_order_seq_cst load times on some ARM implementations.
   • RISC-V currently lacks this support, but appears to be moving in the same direction with the proposed Zalasr extension.
   • The main architectures that could still benefit are Power and GPUs.
4. In practice, non-portable, very careful, abuse of memory_order_relaxed seems to have carried the day for the remaining use cases.

3 Problems not handled by this paper

There are other problems concerning memory consistency that arise from the use of memory_order_relaxed and memory_order_seq_cst that are not handled by this paper here. The whole has been described in

• Revising the C++ memory model

It identifies several problems: non-conformance of some specific implementations, seq_cst fences, release sequences, out-of-thin-air, consume.

C++ has already integrated changes that deal with two of these problems:

• Defang and deprecate memory_order::consume
• Weaken Release Sequences

These provide satisfactory solutions, namely for the problem of consume operations (as proposed in this paper) and for a problem with release sequences. Since the second problem is orthogonal to what is proposed here, we will deal with this in a seperate paper. For convenience, the suggested wording below already marks the text that would be suppressed by this second change.

Some solutions for the other problems are already integrated into C++ (which version?), but are unfortunately not yet satisfactory and will need more discussion in the community, including implementers. So we don’t think that it would be wise to follow C++, yet.

4 Approach

When not using consume operations, a whole bunch of definitions in the C standard become unused, namely:

• carries a dependency,
• dependency-ordered before,
• inter-thread happens before,
• the enumeration constant memory_order_consume, and
• the macro kill_dependency.

The first three can be safely removed. The latter two should be kept for backwards compatibility.

• The enumeration constant memory_order_consume becomes a synonym for memory_order_acquire, because that is what implementations currently do and because this is conforming to C23.
• The macro kill_dependency simply returns its argument. Again, this is what implementations do and what is conforming to C23.

Both identifiers are marked to be obsolescent.

5 Suggested wording changes

New text is underlined green, removed text is stroke-out red. For information, other changes that have already brought to C++ are underlined.

5.1 Environment

5.2.2.5 Multi-threaded executions and data races

…

5 The library defines atomic operations (7.17) and operations on mutexes (7.30.4) that are specially identified as synchronization operations. These operations play a special role in making assignments in one thread visible to another. A synchronization operation on one or more memory locations is one of an acquire operation, a release operation, or both an acquire and release operation, or a consume operation. A synchronization operation without an associated memory location is a fence and can be either an acquire fence, a release fence, or both an acquire and release fence. In addition, there are relaxed atomic operations, which are not synchronization operations, and atomic read-modify-write operations, which have special characteristics.

6 NOTE 2 For example, a call that acquires a mutex will perform an acquire operation on the locations composing the mutex. Correspondingly, a call that releases the same mutex will perform a release operation on those same locations. Informally, performing a release operation on A forces prior side effects on other memory locations to become visible to other threads that later perform an acquire or consume operation on A. Relaxed atomic operations are not included as synchronization operations although, like synchronization operations, they cannot contribute to data races.

…

10 A release sequence headed by a release operation A on an atomic object M is a maximal contiguous sub-sequence of side effects in the modification order of M , where the first operation is A and every subsequent operation either is performed by the same thread that performed the release or is an atomic read-modify-write operation.

11 Certain library calls synchronize with other library calls performed by another thread. In particular, an atomic operation A that performs a release operation on an object M synchronizes with an atomic operation B that performs an acquire operation on M and reads a value written by any side effect in the release sequence headed by A.

…

14 An evaluation A carries a dependency¹¹⁾ to an evaluation B if:

• the value of A is used as an operand of B, unless:

• B is an invocation of the kill_dependency macro,
• A is the left operand of a && or || operator,
• A is the left operand of a ?: operator, or
• A is the left operand of a , operator;

or

• A writes a scalar object or bit-field M , B reads from M the value written by A, and A is sequenced before B, or
• for some evaluation X, A carries a dependency to X and X carries a dependency to B.

¹¹⁾ The “carries a dependency” relation is a subset of the “sequenced before” relation, and is similarly strictly intra-thread.

15 An evaluation A is dependency-ordered before¹²⁾ an evaluation B if:

• A performs a release operation on an atomic object M , and, in another thread, B performs a consume operation on M and reads a value written by any side effect in the release sequence headed by A, or
• for some evaluation X, A is dependency-ordered before X and X carries a dependency to B.

¹²⁾ The “dependency-ordered before” relation is analogous to the “synchronizes with” relation, but uses release/consume in place of release/acquire.

16 An evaluation A inter-thread happens before an evaluation B if A synchronizes with B, A is dependency-ordered before B, or, for some evaluation X:

• A synchronizes with X and X is sequenced before B,
• A is sequenced before X and X inter-thread happens before B, or
• A inter-thread happens before X and X inter-thread happens before B.

17 NOTE 7 The “inter-thread happens before” relation describes arbitrary concatenations of “sequenced before”, “synchronizes with”, and “dependency-ordered before” relationships, with two exceptions. The first exception is that a concatenation is not permitted to end with “dependency-ordered before” followed by “sequenced before”. The reason for this limitation is that a consume operation participating in a “dependency-ordered before” relationship provides ordering only with respect to operations to which this consume operation carries a dependency. The reason that this limitation applies only to the end of such a concatenation is that any subsequent release operation will provide the required ordering for a prior consume operation. The second exception is that a concatenation is not permitted to consist entirely of “sequenced before”. The reasons for this limitation are (1) to permit “inter-thread happens> before” to be transitively closed and (2) the “happens before” relation, defined subsequently in this subclause, provides for relationships consisting entirely of “sequenced before”.

18 An evaluation A happens before an evaluation B if A is sequenced before B or A inter-thread happens before B. The implementation shall ensure that no program execution demonstrates a cycle in the “happens> before” relation.

14′ An evaluation A happens before an evaluation B (or, equivalently, B happens after A) if either

• A is sequenced before B, or
• A synchronizes with B, or
• A happens before X and X happens before B.

19 NOTE 8 This cycle would otherwise be possible only through the use of consume operations.

15′ NOTE 7′ An evaluation cannot happen before itself.

5.2 Library

7.17 Atomics <stdatomic.h>

…

7.17.3 Order and consistency

7.17.3.1 General

1 The enumerated type memory_order specifies the detailed regular (non-atomic) memory synchronization operations as defined in 5.2.2.5 and may provide for operation ordering. Its enumeration constants are as follows:^XXX)

^XXX) The use of the enumeration constant memory_order_consume is obsolescent. See “future library directions” (7.35.11).

2 For memory_order_relaxed, no operation orders memory.

3 For memory_order_release, memory_order_acq_rel, and memory_order_seq_cst, a store operation performs a release operation on the affected memory location.

4 For memory_order_acquire, memory_order_consume, memory_order_acq_rel, and memory_order_seq_cst, a load operation performs an acquire operation on the affected memory location.

5 For memory_order_consume, a load operation performs a consume operation on the affected memory location.

…

7.17.3.2 The kill_dependency macro

…

Description

2 The kill_dependency macro terminates a dependency chain; the argument does not carry a dependency to the return value has no other effect than its result.

Returns

3 The kill_dependency macro returns the value of y.

4 NOTE The kill_dependency macro is an obsolescent feature (7.35.11).

…

7.35 Future library directions

…

7.35.11 Atomics <stdatomic.h>

1 Macros that begin with ATOMIC_ and an uppercase letter are potentially reserved identifiers and may be added to the macros defined in the <stdatomic.h> header. Typedef names that begin with either atomic_ or memory_, and a lowercase letter are potentially reserved identifiers and may be added to the declarations in the <stdatomic.h> header. Enumeration constants that begin with memory_order_ and a lowercase letter are potentially reserved identifiers and may be added to the definition of the memory_order type in the <stdatomic.h> header; the enumeration constant memory_order_consume is an obsolescent feature. Function names that begin with atomic_ and a lowercase letter are potentially reserved identifiers and may be added to the declarations in the <stdatomic.h> header. The kill_dependency macro is an obsolescent feature.

5.3 Note to the editors

The changes proposed have some modified paragraphs in common with n3606. In particular, we would have to watch to remove memory_order_consume in 7.17.3.1, p12′, NOTE 2′ of that paper.

The wording changes have been integrated into the standard source in the following branch:

https://gitlab.gwdg.de/iso-c/draft/-/tree/consume