Memory-model changes

From: Alan Stern <[email protected]>

More than one kernel developer has expressed the opinion that the LKMM should enforce ordering of writes by locking. In other words, given the following code:

	WRITE_ONCE(x, 1);
	spin_unlock(&s):
	spin_lock(&s);
	WRITE_ONCE(y, 1);

the stores to x and y should be propagated in order to all other CPUs, even though those other CPUs might not access the lock s. In terms of the memory model, this means expanding the cumul-fence relation.

Locks should also provide read-read (and read-write) ordering in a similar way. Given:

	READ_ONCE(x);
	spin_unlock(&s);
	spin_lock(&s);
	READ_ONCE(y);		// or WRITE_ONCE(y, 1);

the load of x should be executed before the load of (or store to) y. The LKMM already provides this ordering, but it provides it even in the case where the two accesses are separated by a release/acquire pair of fences rather than unlock/lock. This would prevent architectures from using weakly ordered implementations of release and acquire, which seems like an unnecessary restriction. The patch therefore removes the ordering requirement from the LKMM for that case.

All the architectures supported by the Linux kernel (including RISC-V) do provide this ordering for locks, albeit for varying reasons. Therefore this patch changes the model in accordance with the developers' wishes.

Signed-off-by Alan Stern <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Will Deacon <[email protected]>

Acked-by Peter Zijlstra (Intel) <[email protected]>

---
 .../Documentation/explanation.txt             | 186 ++++++++++++++----
 tools/memory-model/linux-kernel.cat           |   8 +-
 ...ISA2+pooncelock+pooncelock+pombonce.litmus |   7 +-
 3 files changed, 150 insertions(+), 51 deletions(-)

tools/memory-model/Documentation/explanation.txt +143 -43

index 0cbd1ef8f86d..35bff92cc773 100644
@@ -28,7 +28,8 @@ Explanation of the Linux-Kernel Memory Consistency Model
   20. THE HAPPENS-BEFORE RELATION: hb
   21. THE PROPAGATES-BEFORE RELATION: pb
   22. RCU RELATIONS: rcu-link, gp, rscs, rcu-fence, and rb
-  23. ODDS AND ENDS
+  23. LOCKING
+  24. ODDS AND ENDS
 
 
 

@@ -1067,28 +1068,6 @@ allowing out-of-order writes like this to occur.  The model avoided
 violating the write-write coherence rule by requiring the CPU not to
 send the W write to the memory subsystem at all!)
 
-There is one last example of preserved program order in the LKMM: when
-a load-acquire reads from an earlier store-release.  For example:
-
-	smp_store_release(&x, 123);
-	r1 = smp_load_acquire(&x);
-
-If the smp_load_acquire() ends up obtaining the 123 value that was
-stored by the smp_store_release(), the LKMM says that the load must be
-executed after the store; the store cannot be forwarded to the load.
-This requirement does not arise from the operational model, but it
-yields correct predictions on all architectures supported by the Linux
-kernel, although for differing reasons.
-
-On some architectures, including x86 and ARMv8, it is true that the
-store cannot be forwarded to the load.  On others, including PowerPC
-and ARMv7, smp_store_release() generates object code that starts with
-a fence and smp_load_acquire() generates object code that ends with a
-fence.  The upshot is that even though the store may be forwarded to
-the load, it is still true that any instruction preceding the store
-will be executed before the load or any following instructions, and
-the store will be executed before any instruction following the load.
-
 
 AND THEN THERE WAS ALPHA
 ------------------------

@@ -1766,6 +1745,147 @@ before it does, and the critical section in P2 both starts after P1's
 grace period does and ends after it does.
 
 
+LOCKING
+-------
+
+The LKMM includes locking.  In fact, there is special code for locking
+in the formal model, added in order to make tools run faster.
+However, this special code is intended to be more or less equivalent
+to concepts we have already covered.  A spinlock_t variable is treated
+the same as an int, and spin_lock(&s) is treated almost the same as:
+
+	while (cmpxchg_acquire(&s, 0, 1) != 0)
+		cpu_relax();
+
+This waits until s is equal to 0 and then atomically sets it to 1,
+and the read part of the cmpxchg operation acts as an acquire fence.
+An alternate way to express the same thing would be:
+
+	r = xchg_acquire(&s, 1);
+
+along with a requirement that at the end, r = 0.  Similarly,
+spin_trylock(&s) is treated almost the same as:
+
+	return !cmpxchg_acquire(&s, 0, 1);
+
+which atomically sets s to 1 if it is currently equal to 0 and returns
+true if it succeeds (the read part of the cmpxchg operation acts as an
+acquire fence only if the operation is successful).  spin_unlock(&s)
+is treated almost the same as:
+
+	smp_store_release(&s, 0);
+
+The "almost" qualifiers above need some explanation.  In the LKMM, the
+store-release in a spin_unlock() and the load-acquire which forms the
+first half of the atomic rmw update in a spin_lock() or a successful
+spin_trylock() -- we can call these things lock-releases and
+lock-acquires -- have two properties beyond those of ordinary releases
+and acquires.
+
+First, when a lock-acquire reads from a lock-release, the LKMM
+requires that every instruction po-before the lock-release must
+execute before any instruction po-after the lock-acquire.  This would
+naturally hold if the release and acquire operations were on different
+CPUs, but the LKMM says it holds even when they are on the same CPU.
+For example:
+
+	int x, y;
+	spinlock_t s;
+
+	P0()
+	{
+		int r1, r2;
+
+		spin_lock(&s);
+		r1 = READ_ONCE(x);
+		spin_unlock(&s);
+		spin_lock(&s);
+		r2 = READ_ONCE(y);
+		spin_unlock(&s);
+	}
+
+	P1()
+	{
+		WRITE_ONCE(y, 1);
+		smp_wmb();
+		WRITE_ONCE(x, 1);
+	}
+
+Here the second spin_lock() reads from the first spin_unlock(), and
+therefore the load of x must execute before the load of y.  Thus we
+cannot have r1 = 1 and r2 = 0 at the end (this is an instance of the
+MP pattern).
+
+This requirement does not apply to ordinary release and acquire
+fences, only to lock-related operations.  For instance, suppose P0()
+in the example had been written as:
+
+	P0()
+	{
+		int r1, r2, r3;
+
+		r1 = READ_ONCE(x);
+		smp_store_release(&s, 1);
+		r3 = smp_load_acquire(&s);
+		r2 = READ_ONCE(y);
+	}
+
+Then the CPU would be allowed to forward the s = 1 value from the
+smp_store_release() to the smp_load_acquire(), executing the
+instructions in the following order:
+
+		r3 = smp_load_acquire(&s);	// Obtains r3 = 1
+		r2 = READ_ONCE(y);
+		r1 = READ_ONCE(x);
+		smp_store_release(&s, 1);	// Value is forwarded
+
+and thus it could load y before x, obtaining r2 = 0 and r1 = 1.
+
+Second, when a lock-acquire reads from a lock-release, and some other
+stores W and W' occur po-before the lock-release and po-after the
+lock-acquire respectively, the LKMM requires that W must propagate to
+each CPU before W' does.  For example, consider:
+
+	int x, y;
+	spinlock_t x;
+
+	P0()
+	{
+		spin_lock(&s);
+		WRITE_ONCE(x, 1);
+		spin_unlock(&s);
+	}
+
+	P1()
+	{
+		int r1;
+
+		spin_lock(&s);
+		r1 = READ_ONCE(x);
+		WRITE_ONCE(y, 1);
+		spin_unlock(&s);
+	}
+
+	P2()
+	{
+		int r2, r3;
+
+		r2 = READ_ONCE(y);
+		smp_rmb();
+		r3 = READ_ONCE(x);
+	}
+
+If r1 = 1 at the end then the spin_lock() in P1 must have read from
+the spin_unlock() in P0.  Hence the store to x must propagate to P2
+before the store to y does, so we cannot have r2 = 1 and r3 = 0.
+
+These two special requirements for lock-release and lock-acquire do
+not arise from the operational model.  Nevertheless, kernel developers
+have come to expect and rely on them because they do hold on all
+architectures supported by the Linux kernel, albeit for various
+differing reasons.
+
+
 ODDS AND ENDS
 -------------
 

@@ -1831,26 +1951,6 @@ they behave as follows:
 	events and the events preceding them against all po-later
 	events.
 
-The LKMM includes locking.  In fact, there is special code for locking
-in the formal model, added in order to make tools run faster.
-However, this special code is intended to be exactly equivalent to
-concepts we have already covered.  A spinlock_t variable is treated
-the same as an int, and spin_lock(&s) is treated the same as:
-
-	while (cmpxchg_acquire(&s, 0, 1) != 0)
-		cpu_relax();
-
-which waits until s is equal to 0 and then atomically sets it to 1,
-and where the read part of the atomic update is also an acquire fence.
-An alternate way to express the same thing would be:
-
-	r = xchg_acquire(&s, 1);
-
-along with a requirement that at the end, r = 0.  spin_unlock(&s) is
-treated the same as:
-
-	smp_store_release(&s, 0);
-
 Interestingly, RCU and locking each introduce the possibility of
 deadlock.  When faced with code sequences such as:
 

tools/memory-model/linux-kernel.cat +4 -4

index 59b5cbe6b624..882fc33274ac 100644
@@ -38,7 +38,7 @@ let strong-fence = mb | gp
 (* Release Acquire *)
 let acq-po = [Acquire] ; po ; [M]
 let po-rel = [M] ; po ; [Release]
-let rfi-rel-acq = [Release] ; rfi ; [Acquire]
+let po-unlock-rf-lock-po = po ; [UL] ; rf ; [LKR] ; po
 
 (**********************************)
 (* Fundamental coherence ordering *)

@@ -60,13 +60,13 @@ let dep = addr | data
 let rwdep = (dep | ctrl) ; [W]
 let overwrite = co | fr
 let to-w = rwdep | (overwrite & int)
-let to-r = addr | (dep ; rfi) | rfi-rel-acq
+let to-r = addr | (dep ; rfi)
 let fence = strong-fence | wmb | po-rel | rmb | acq-po
-let ppo = to-r | to-w | fence
+let ppo = to-r | to-w | fence | (po-unlock-rf-lock-po & int)
 
 (* Propagation: Ordering from release operations and strong fences. *)
 let A-cumul(r) = rfe? ; r
-let cumul-fence = A-cumul(strong-fence | po-rel) | wmb
+let cumul-fence = A-cumul(strong-fence | po-rel) | wmb | po-unlock-rf-lock-po
 let prop = (overwrite & ext)? ; cumul-fence* ; rfe?
 
 (*

tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus +3 -4

index 0f749e419b34..094d58df7789 100644
@@ -1,11 +1,10 @@
 C ISA2+pooncelock+pooncelock+pombonce
 
 (*
- * Result: Sometimes
+ * Result: Never
  *
- * This test shows that the ordering provided by a lock-protected S
- * litmus test (P0() and P1()) are not visible to external process P2().
- * This is likely to change soon.
+ * This test shows that write-write ordering provided by locks
+ * (in P0() and P1()) is visible to external process P2().
  *)
 
 {}

Signature · 1 line

2.17.1

Quoted 9 lines

All the architectures supported by the Linux kernel (including RISC-V) do provide this ordering for locks, albeit for varying reasons. Therefore this patch changes the model in accordance with the developers' wishes.

Signed-off-by Alan Stern <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Will Deacon <[email protected]>

Acked-by Peter Zijlstra (Intel) <[email protected]>

Round 2 ;-), I guess... Let me start from the uncontroversial points:

1) being able to use the LKMM to reason about generic locking code

     is useful and desirable (paraphrasing Peter in [1]);

2) strengthening the ordering requirements of such code isn't going to boost performance (that's "real maths").

This patch is taking (1) away from us and it is formalizing (2), with almost _no_ reason (no reason at all, if we stick to the commit msg.).

In [2], Will wrote:

"[...] having them [the RMWs] closer to RCsc[/to the semantics of
locks] would make it easier to implement and reason about generic locking implementations (i.e. reduce the number of special ordering cases and/or magic barrier macros)"

"magic barrier macros" as in "mmh, if we accept this patch, we _should_ be auditing the various implementations/code to decide where to place a

smp_barrier_promote_ordinary_release_acquire_to_unlock_lock()" ;-)

or the like, and "special ordering cases" as in "arrgh, (otherwise) we are forced to reason on a per-arch basis while looking at generic code".

(Remark: ordinary release/acquire are building blocks for code such as
qspinlock, (q)rwlock, mutex, rwsem, ... and what else??).

To avoid further repetition, I conclude by confirming all the concerns and my assessment of this patch as pointed out in [3]; the subsequent discussion, although not conclusive, presented several suggestions for improvement (IMO).

Quoted 12 lines · Andrea Parri

Quoted 9 lines

All the architectures supported by the Linux kernel (including RISC-V) do provide this ordering for locks, albeit for varying reasons. Therefore this patch changes the model in accordance with the developers' wishes.

Signed-off-by Alan Stern <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Will Deacon <[email protected]>

Acked-by Peter Zijlstra (Intel) <[email protected]>

Round 2 ;-), I guess... Let me start from the uncontroversial points:

Quoted 8 lines

1) being able to use the LKMM to reason about generic locking code

     is useful and desirable (paraphrasing Peter in [1]);

2) strengthening the ordering requirements of such code isn't going to boost performance (that's "real maths").

This patch is taking (1) away from us and it is formalizing (2), with almost _no_ reason (no reason at all, if we stick to the commit msg.).

That's not quite fair. Generic code isn't always universally applicable; some of it is opt-in -- meant only for the architectures that can support it. In general, the LKMM allows us to reason about higher abstractions (such as locking) at a higher level, without necessarily being able to verify the architecture-specific details of the implementations.

Quoted 11 lines

In [2], Will wrote:

"[...] having them [the RMWs] closer to RCsc[/to the semantics of
locks] would make it easier to implement and reason about generic locking implementations (i.e. reduce the number of special ordering cases and/or magic barrier macros)"

"magic barrier macros" as in "mmh, if we accept this patch, we _should_ be auditing the various implementations/code to decide where to place a

Quoted 4 lines

smp_barrier_promote_ordinary_release_acquire_to_unlock_lock()" ;-)

or the like, and "special ordering cases" as in "arrgh, (otherwise) we are forced to reason on a per-arch basis while looking at generic code".

Currently the LKMM does not permit architecture-specific reasoning. It would have to be extended (in a different way for each architecture) first.

For example, one could use herd's POWER model combined with the POWER compilation scheme and the POWER-specific implementation of spinlocks for such reasoning. The LKMM alone is not sufficient.

Sure, programming and reasoning about the kernel would be easier if all architectures were the same. Unfortunately, we (and the kernel) have to live in the real world.

Quoted 2 lines

(Remark: ordinary release/acquire are building blocks for code such as
qspinlock, (q)rwlock, mutex, rwsem, ... and what else??).

But are these building blocks used the same way for all architectures?

Quoted 5 lines

To avoid further repetition, I conclude by confirming all the concerns and my assessment of this patch as pointed out in [3]; the subsequent discussion, although not conclusive, presented several suggestions for improvement (IMO).

Alan

Quoted 23 lines · Alan Stern

Quoted 12 lines · Andrea Parri

Quoted 9 lines

All the architectures supported by the Linux kernel (including RISC-V) do provide this ordering for locks, albeit for varying reasons. Therefore this patch changes the model in accordance with the developers' wishes.

Signed-off-by Alan Stern <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Will Deacon <[email protected]>

Acked-by Peter Zijlstra (Intel) <[email protected]>

Round 2 ;-), I guess... Let me start from the uncontroversial points:

Quoted 8 lines

1) being able to use the LKMM to reason about generic locking code

     is useful and desirable (paraphrasing Peter in [1]);

2) strengthening the ordering requirements of such code isn't going to boost performance (that's "real maths").

This patch is taking (1) away from us and it is formalizing (2), with almost _no_ reason (no reason at all, if we stick to the commit msg.).

Quoted 6 lines

That's not quite fair. Generic code isn't always universally applicable; some of it is opt-in -- meant only for the architectures that can support it. In general, the LKMM allows us to reason about higher abstractions (such as locking) at a higher level, without necessarily being able to verify the architecture-specific details of the implementations.

No, generic code is "universally applicable" by definition; see below for more on this point.

Quoted 15 lines

Quoted 14 lines

In [2], Will wrote:

"[...] having them [the RMWs] closer to RCsc[/to the semantics of
locks] would make it easier to implement and reason about generic locking implementations (i.e. reduce the number of special ordering cases and/or magic barrier macros)"

"magic barrier macros" as in "mmh, if we accept this patch, we _should_ be auditing the various implementations/code to decide where to place a

smp_barrier_promote_ordinary_release_acquire_to_unlock_lock()" ;-)

or the like, and "special ordering cases" as in "arrgh, (otherwise) we are forced to reason on a per-arch basis while looking at generic code".

Quoted 3 lines

Currently the LKMM does not permit architecture-specific reasoning. It would have to be extended (in a different way for each architecture) first.

Completely agreed; that's why I said that this patch is detrimental to the applicability of the LKMM...

Quoted 4 lines

For example, one could use herd's POWER model combined with the POWER compilation scheme and the POWER-specific implementation of spinlocks for such reasoning. The LKMM alone is not sufficient.

Quoted 8 lines

Sure, programming and reasoning about the kernel would be easier if all architectures were the same. Unfortunately, we (and the kernel) have to live in the real world.

Quoted 2 lines

(Remark: ordinary release/acquire are building blocks for code such as
qspinlock, (q)rwlock, mutex, rwsem, ... and what else??).

But are these building blocks used the same way for all architectures?

The more, the better! (because then we have the LKMM tools)

We already discussed the "fast path" example: the fast paths of the above all resemble:

*_lock(s): atomic_cmpxchg_acquire(&s->val, UNLOCKED_VAL, LOCKED_VAL) ... *_unlock(s): ... atomic_set_release(&s->val, UNLOCKED_VAL)

When I read this code, I think "Of course." (unless some arch. has messed the implementation of cmpxchg_* up, which can happen...); but then I read the subject line of this patch and I think "Wait, what?".

You can argue that this is not generic code, sure; but why on Earth would you like to do so?!

Quoted 15 lines · Andrea Parri

Quoted 5 lines · Alan Stern

Quoted 2 lines · Andrea Parri

(Remark: ordinary release/acquire are building blocks for code such as
qspinlock, (q)rwlock, mutex, rwsem, ... and what else??).

But are these building blocks used the same way for all architectures?

The more, the better! (because then we have the LKMM tools)

We already discussed the "fast path" example: the fast paths of the above all resemble:

*_lock(s): atomic_cmpxchg_acquire(&s->val, UNLOCKED_VAL, LOCKED_VAL) ... *_unlock(s): ... atomic_set_release(&s->val, UNLOCKED_VAL)

Quoted 6 lines

When I read this code, I think "Of course." (unless some arch. has messed the implementation of cmpxchg_* up, which can happen...); but then I read the subject line of this patch and I think "Wait, what?".

You can argue that this is not generic code, sure; but why on Earth would you like to do so?!

Because the code might not work! On RISC-V, for example, the implementation of ordinary release/acquire is currently not as strong as atomic release/acquire.

Yes, it's true that implementing locks with atomic_cmpxchg_acquire should be correct on all existing architectures. And Paul has invited a patch to modify the LKMM accordingly. If you feel that such a change would be a useful enhancement to the LKMM's applicability, please write it.

Quoted 5 lines

Yes, it's true that implementing locks with atomic_cmpxchg_acquire should be correct on all existing architectures. And Paul has invited a patch to modify the LKMM accordingly. If you feel that such a change would be a useful enhancement to the LKMM's applicability, please write it.

Yes, please! That would be the "RmW" discussion which Andrea partially quoted earlier on, so getting that going independently from this patch sounds like a great idea to me.

Cheers,

Will

Quoted 9 lines

Quoted 5 lines

Yes, it's true that implementing locks with atomic_cmpxchg_acquire should be correct on all existing architectures. And Paul has invited a patch to modify the LKMM accordingly. If you feel that such a change would be a useful enhancement to the LKMM's applicability, please write it.

Yes, please! That would be the "RmW" discussion which Andrea partially quoted earlier on, so getting that going independently from this patch sounds like a great idea to me.

That was indeed one of the proposal we discussed. As you recalled, that proposal only covered RmWs load-acquire (and ordinary store-release); in particular, I realized that comments such as:

"The atomic_cond_read_acquire() call above has provided the
necessary acquire semantics required for locking."

[from kernel/locking/qspinlock.c]

(for example) would still _not have "generic validity" _if we added the above po-unlock-rf-lock-po term... (which, again, makes me somehow uncon- fortable); Would to have _all_ the acquire be admissible for you?

Quoted 14 lines · Andrea Parri

Quoted 9 lines

Quoted 5 lines

Yes, it's true that implementing locks with atomic_cmpxchg_acquire should be correct on all existing architectures. And Paul has invited a patch to modify the LKMM accordingly. If you feel that such a change would be a useful enhancement to the LKMM's applicability, please write it.

Yes, please! That would be the "RmW" discussion which Andrea partially quoted earlier on, so getting that going independently from this patch sounds like a great idea to me.

That was indeed one of the proposal we discussed. As you recalled, that proposal only covered RmWs load-acquire (and ordinary store-release); in particular, I realized that comments such as:

Quoted 8 lines

"The atomic_cond_read_acquire() call above has provided the
necessary acquire semantics required for locking."

[from kernel/locking/qspinlock.c]

(for example) would still _not have "generic validity" _if we added the above po-unlock-rf-lock-po term... (which, again, makes me somehow uncon- fortable); Would to have _all_ the acquire be admissible for you?

In Cat speak,

tools/memory-model/linux-kernel.cat +2 -2

index 59b5cbe6b6240..fd9c0831adf0a 100644
@@ -38,7 +38,7 @@ let strong-fence = mb | gp
 (* Release Acquire *)
 let acq-po = [Acquire] ; po ; [M]
 let po-rel = [M] ; po ; [Release]
-let rfi-rel-acq = [Release] ; rfi ; [Acquire]
+let po-rel-rf-acq-po = po ; [Release] ; rf ; [Acquire] ; po
 
 (**********************************)
 (* Fundamental coherence ordering *)

@@ -60,13 +60,13 @@ let dep = addr | data
 let rwdep = (dep | ctrl) ; [W]
 let overwrite = co | fr
 let to-w = rwdep | (overwrite & int)
-let to-r = addr | (dep ; rfi) | rfi-rel-acq
+let to-r = addr | (dep ; rfi)
 let fence = strong-fence | wmb | po-rel | rmb | acq-po

I take this opportunity to summarize my viewpoint on these matters:

Someone would have to write the commit message for the above diff ... that is, to describe -why- we should go RCtso (and update the documen- tation accordingly); by now, the only argument for this appears to be:
"(most) people expect strong ordering" _and they will be "lazy enough" to not check their expectations by using the LKMM tool (paraphrasing from [1]); IAC, Linux "might work" better if we add this ordering to the LKMM. Agreeing on such an approach would mean agreeing that this argument "wins" over:

"We want new architectures to implement acquire/release efficiently,
and it's not unlikely that they will have acquire loads that are similar in semantics to LDAPR." [2]

"RISC-V probably would have been RCpc [...] it takes extra fences
to go from RCpc to either "RCtso" or RCsc." [3]

(or similar instances) since, of course, there is no such thing as a "free strong ordering"; and I'm not only talking about "efficiency", I'm also thinking at the fact that someone will have to maintain that ordering across all the architectures and in the LKMM.

If, OTOH, we agree that the above "win"/assumption is valid only for locks or, in other/better words, if we agree that we should maintain _two_ distinct release-acquire orderings (a first one for unlock-lock sequences and a second one for ordinary/atomic release-acquire, say, as proposed in the patch under RFC), I ask that we audit and modify the generic code accordingly/as suggested in other posts _before_ we upstream the changes for the LKMM: we should identify those places where (the newly introduced) _gap_ between unlock-lock and the other release-acquire is not admissible and fix those places (notice that this entails, in part., agreeing on what/where the generic code is).

Finally, if we don't agree with the above assumption at all (that is, no matter if we are considering unlock-lock or other release-acquire sequences), then we should go RCpc [4].

I described three different approaches (which are NOT "independent", clearly; let us find an agreement...); even though some of them look insane to me, I'm currently open to all of them: thoughts?

Quoted 31 lines

In Cat speak,

tools/memory-model/linux-kernel.cat +4 -4

index 59b5cbe6b6240..fd9c0831adf0a 100644
@@ -38,7 +38,7 @@ let strong-fence = mb | gp
 (* Release Acquire *)
 let acq-po = [Acquire] ; po ; [M]
 let po-rel = [M] ; po ; [Release]
-let rfi-rel-acq = [Release] ; rfi ; [Acquire]
+let po-rel-rf-acq-po = po ; [Release] ; rf ; [Acquire] ; po
 
 (**********************************)
 (* Fundamental coherence ordering *)

@@ -60,13 +60,13 @@ let dep = addr | data
 let rwdep = (dep | ctrl) ; [W]
 let overwrite = co | fr
 let to-w = rwdep | (overwrite & int)
-let to-r = addr | (dep ; rfi) | rfi-rel-acq
+let to-r = addr | (dep ; rfi)
 let fence = strong-fence | wmb | po-rel | rmb | acq-po
-let ppo = to-r | to-w | fence
+let ppo = to-r | to-w | fence | (po-rel-rf-acq-po & int)
 
 (* Propagation: Ordering from release operations and strong fences. *)
 let A-cumul(r) = rfe? ; r
-let cumul-fence = A-cumul(strong-fence | po-rel) | wmb
+let cumul-fence = A-cumul(strong-fence | po-rel) | wmb | po-rel-rf-acq-po
 let prop = (overwrite & ext)? ; cumul-fence* ; rfe?
 

tools/memory-model/linux-kernel.cat let dep = addr | data · line 72

Quoted 1 line

tools/memory-model/linux-kernel.cat +0 -0

 (*

Isn't the job of the memory model to formalise the guarantees provided by the implementation? Your diff appears to do exactly the opposite.

Quoted 24 lines

I take this opportunity to summarize my viewpoint on these matters:

Someone would have to write the commit message for the above diff ... that is, to describe -why- we should go RCtso (and update the documen- tation accordingly); by now, the only argument for this appears to be:
"(most) people expect strong ordering" _and they will be "lazy enough" to not check their expectations by using the LKMM tool (paraphrasing from [1]); IAC, Linux "might work" better if we add this ordering to the LKMM. Agreeing on such an approach would mean agreeing that this argument "wins" over:

"We want new architectures to implement acquire/release efficiently,
and it's not unlikely that they will have acquire loads that are similar in semantics to LDAPR." [2]

"RISC-V probably would have been RCpc [...] it takes extra fences
to go from RCpc to either "RCtso" or RCsc." [3]

(or similar instances) since, of course, there is no such thing as a "free strong ordering"; and I'm not only talking about "efficiency", I'm also thinking at the fact that someone will have to maintain that ordering across all the architectures and in the LKMM.

Quoted 10 lines

If, OTOH, we agree that the above "win"/assumption is valid only for locks or, in other/better words, if we agree that we should maintain _two_ distinct release-acquire orderings (a first one for unlock-lock sequences and a second one for ordinary/atomic release-acquire, say, as proposed in the patch under RFC), I ask that we audit and modify the generic code accordingly/as suggested in other posts _before_ we upstream the changes for the LKMM: we should identify those places where (the newly introduced) _gap_ between unlock-lock and the other release-acquire is not admissible and fix those places (notice that this entails, in part., agreeing on what/where the generic code is).

This is completely unrealistic. Have we already audited the kernel for the current definition of the memory model? Should we revert it until we have?

Of course not.

Right now, LKMM offers stronger guarantees that can portably be relied upon in the codebase. Alan's patch fixes that, and holding back a fix for a known issue runs counter to kernel development best practices.

Quoted 8 lines

Finally, if we don't agree with the above assumption at all (that is, no matter if we are considering unlock-lock or other release-acquire sequences), then we should go RCpc [4].

I described three different approaches (which are NOT "independent", clearly; let us find an agreement...); even though some of them look insane to me, I'm currently open to all of them: thoughts?

I'm very confused by your statements hypothesising about where our opinions may lie. We've discussed this to death, and it's clear that everybody who's commented apart from you is happy to weaken acquire/release but leave locking alone. Alan's written a patch to that effect which, again, only you seem to have a problem with.

The problem isn't about "if we agree foo" or "if we don't agree bar", the problem is that you're the only person raising an objection, so please can you provide a constructive argument against Alan's patch, rather than a confusing monologue of "what-if"s and unreasonable demands of anonymous contributors? We don't have to solve all of our problems before we can make any progress.

Thanks,

Will

Heh, your confusion might be the reflection of mine... ;-) That was indeed a long and not conclusive discussion (meaning there're pending issues); and I cannot claim to find "arguments" such as:

"More than one kernel developer has expressed the opinion that
the LKMM should enforce ordering of writes by locking."

particularly helpful (I do tend to be convinced by arguments rather than by opinions). In fact, you can take the following as my only current "constructive argument" against the patch [1,2]:

THE COMMIT MESSAGE IS RIDICULOUS; PLEASE EXPAND ON IT, AND DO SO BY LEVERAGING BOTH PROS AND CONS OF THE APPLIED CHANGES

Quoted 7 lines · Andrea Parri

Heh, your confusion might be the reflection of mine... ;-) That was indeed a long and not conclusive discussion (meaning there're pending issues); and I cannot claim to find "arguments" such as:

"More than one kernel developer has expressed the opinion that
the LKMM should enforce ordering of writes by locking."

Quoted 6 lines

particularly helpful (I do tend to be convinced by arguments rather than by opinions). In fact, you can take the following as my only current "constructive argument" against the patch [1,2]:

THE COMMIT MESSAGE IS RIDICULOUS; PLEASE EXPAND ON IT, AND DO SO BY LEVERAGING BOTH PROS AND CONS OF THE APPLIED CHANGES

Do you have any concrete suggestions (i.e., some actual text) for improvements to the patch description? Earlier in your message you mentioned that Will's comment:

LKMM offers stronger guarantees that can portably be relied upon in the codebase.

would make a good addition. Suitably edited, it could be added to the description. I can think of a few other things myself, but I'd like to hear your thoughts. Anything else?

Alan

Quoted 22 lines · Alan Stern

Quoted 7 lines · Andrea Parri

Heh, your confusion might be the reflection of mine... ;-) That was indeed a long and not conclusive discussion (meaning there're pending issues); and I cannot claim to find "arguments" such as:

"More than one kernel developer has expressed the opinion that
the LKMM should enforce ordering of writes by locking."

Quoted 6 lines

particularly helpful (I do tend to be convinced by arguments rather than by opinions). In fact, you can take the following as my only current "constructive argument" against the patch [1,2]:

THE COMMIT MESSAGE IS RIDICULOUS; PLEASE EXPAND ON IT, AND DO SO BY LEVERAGING BOTH PROS AND CONS OF THE APPLIED CHANGES

Do you have any concrete suggestions (i.e., some actual text) for improvements to the patch description? Earlier in your message you mentioned that Will's comment:

LKMM offers stronger guarantees that can portably be relied upon in the codebase.

Quoted 3 lines

would make a good addition. Suitably edited, it could be added to the description. I can think of a few other things myself, but I'd like to hear your thoughts. Anything else?

Yes: I do sometimes have the impression that your "rules" for trimming text in emails/replies are too aggressive...

Andrea

Quoted 3 lines

Alan

Quoted 27 lines · Andrea Parri

Quoted 25 lines · Alan Stern

Quoted 7 lines · Andrea Parri

Heh, your confusion might be the reflection of mine... ;-) That was indeed a long and not conclusive discussion (meaning there're pending issues); and I cannot claim to find "arguments" such as:

"More than one kernel developer has expressed the opinion that
the LKMM should enforce ordering of writes by locking."

Quoted 6 lines

particularly helpful (I do tend to be convinced by arguments rather than by opinions). In fact, you can take the following as my only current "constructive argument" against the patch [1,2]:

THE COMMIT MESSAGE IS RIDICULOUS; PLEASE EXPAND ON IT, AND DO SO BY LEVERAGING BOTH PROS AND CONS OF THE APPLIED CHANGES

Do you have any concrete suggestions (i.e., some actual text) for improvements to the patch description? Earlier in your message you mentioned that Will's comment:

LKMM offers stronger guarantees that can portably be relied upon in the codebase.

would make a good addition. Suitably edited, it could be added to the description. I can think of a few other things myself, but I'd like to hear your thoughts. Anything else?

Quoted 2 lines

Yes: I do sometimes have the impression that your "rules" for trimming text in emails/replies are too aggressive...

Andrea, by saying "Yes:", do you mean you have something else to be added? I don't think you do, but want to make sure.

I'm a bit surprised to see all you wanted was the amendment of the commit log...

Quoted 23 lines · Andrea Parri

Quoted 22 lines · Alan Stern

Quoted 7 lines · Andrea Parri

Heh, your confusion might be the reflection of mine... ;-) That was indeed a long and not conclusive discussion (meaning there're pending issues); and I cannot claim to find "arguments" such as:

"More than one kernel developer has expressed the opinion that
the LKMM should enforce ordering of writes by locking."

Quoted 6 lines

particularly helpful (I do tend to be convinced by arguments rather than by opinions). In fact, you can take the following as my only current "constructive argument" against the patch [1,2]:

THE COMMIT MESSAGE IS RIDICULOUS; PLEASE EXPAND ON IT, AND DO SO BY LEVERAGING BOTH PROS AND CONS OF THE APPLIED CHANGES

Do you have any concrete suggestions (i.e., some actual text) for improvements to the patch description? Earlier in your message you mentioned that Will's comment:

LKMM offers stronger guarantees that can portably be relied upon in the codebase.

Quoted 6 lines

Quoted 3 lines

would make a good addition. Suitably edited, it could be added to the description. I can think of a few other things myself, but I'd like to hear your thoughts. Anything else?

Yes: I do sometimes have the impression that your "rules" for trimming text in emails/replies are too aggressive...

Andrea, by saying "Yes:", do you mean you have something else to be added?

I don't think you do, but want to make sure.

I'm a bit surprised to see all you wanted was the amendment of the commit log...

Akira

Quoted 7 lines

Andrea

Quoted 3 lines

Alan

Quoted 28 lines · Akira Yokosawa

Quoted 27 lines · Andrea Parri

Quoted 25 lines · Alan Stern

Quoted 7 lines · Andrea Parri

Heh, your confusion might be the reflection of mine... ;-) That was indeed a long and not conclusive discussion (meaning there're pending issues); and I cannot claim to find "arguments" such as:

"More than one kernel developer has expressed the opinion that
the LKMM should enforce ordering of writes by locking."

Quoted 6 lines

particularly helpful (I do tend to be convinced by arguments rather than by opinions). In fact, you can take the following as my only current "constructive argument" against the patch [1,2]:

THE COMMIT MESSAGE IS RIDICULOUS; PLEASE EXPAND ON IT, AND DO SO BY LEVERAGING BOTH PROS AND CONS OF THE APPLIED CHANGES

Do you have any concrete suggestions (i.e., some actual text) for improvements to the patch description? Earlier in your message you mentioned that Will's comment:

LKMM offers stronger guarantees that can portably be relied upon in the codebase.

would make a good addition. Suitably edited, it could be added to the description. I can think of a few other things myself, but I'd like to hear your thoughts. Anything else?

Quoted 4 lines

Quoted 2 lines

Yes: I do sometimes have the impression that your "rules" for trimming text in emails/replies are too aggressive...

Andrea, by saying "Yes:", do you mean you have something else to be added?

Indeed (examples in the trimmed text).

Quoted 6 lines

I don't think you do, but want to make sure.

I'm a bit surprised to see all you wanted was the amendment of the commit log...

Well, I said that it was my only current constructive argument...

Andrea

Quoted 11 lines

Akira

Quoted 7 lines

Andrea

Quoted 3 lines

Alan

Quoted 11 lines

Quoted 11 lines

Quoted 11 lines

Quoted 10 lines

Do you have any concrete suggestions (i.e., some actual text) for improvements to the patch description? Earlier in your message you mentioned that Will's comment:

LKMM offers stronger guarantees that can portably be relied upon in the codebase.

would make a good addition. Suitably edited, it could be added to the description. I can think of a few other things myself, but I'd like to hear your thoughts. Anything else?

Quoted 6 lines

Quoted 4 lines

Quoted 2 lines

Yes: I do sometimes have the impression that your "rules" for trimming text in emails/replies are too aggressive...

Andrea, by saying "Yes:", do you mean you have something else to be added?

Indeed (examples in the trimmed text).

So, you mean just amending commit log does not work for you?

Quoted 9 lines

Quoted 7 lines

I don't think you do, but want to make sure.

I'm a bit surprised to see all you wanted was the amendment of the commit log...

Well, I said that it was my only current constructive argument...

This thread is getting quite hard for me to follow...

Akira

Quoted 15 lines

Andrea

Quoted 11 lines

Akira

Quoted 7 lines

Andrea

Quoted 3 lines

Alan

In Cat speak,

tools/memory-model/linux-kernel.cat +2 -2

index 59b5cbe6b6240..fd9c0831adf0a 100644
@@ -38,7 +38,7 @@ let strong-fence = mb | gp
 (* Release Acquire *)
 let acq-po = [Acquire] ; po ; [M]
 let po-rel = [M] ; po ; [Release]
-let rfi-rel-acq = [Release] ; rfi ; [Acquire]
+let po-rel-rf-acq-po = po ; [Release] ; rf ; [Acquire] ; po
 
 (**********************************)
 (* Fundamental coherence ordering *)

@@ -60,13 +60,13 @@ let dep = addr | data
 let rwdep = (dep | ctrl) ; [W]
 let overwrite = co | fr
 let to-w = rwdep | (overwrite & int)
-let to-r = addr | (dep ; rfi) | rfi-rel-acq
+let to-r = addr | (dep ; rfi)
 let fence = strong-fence | wmb | po-rel | rmb | acq-po

Quoted 31 lines · Andrea Parri

In Cat speak,

tools/memory-model/linux-kernel.cat +4 -4

index 59b5cbe6b6240..fd9c0831adf0a 100644
@@ -38,7 +38,7 @@ let strong-fence = mb | gp
 (* Release Acquire *)
 let acq-po = [Acquire] ; po ; [M]
 let po-rel = [M] ; po ; [Release]
-let rfi-rel-acq = [Release] ; rfi ; [Acquire]
+let po-rel-rf-acq-po = po ; [Release] ; rf ; [Acquire] ; po
 
 (**********************************)
 (* Fundamental coherence ordering *)

@@ -60,13 +60,13 @@ let dep = addr | data
 let rwdep = (dep | ctrl) ; [W]
 let overwrite = co | fr
 let to-w = rwdep | (overwrite & int)
-let to-r = addr | (dep ; rfi) | rfi-rel-acq
+let to-r = addr | (dep ; rfi)
 let fence = strong-fence | wmb | po-rel | rmb | acq-po
-let ppo = to-r | to-w | fence
+let ppo = to-r | to-w | fence | (po-rel-rf-acq-po & int)
 
 (* Propagation: Ordering from release operations and strong fences. *)
 let A-cumul(r) = rfe? ; r
-let cumul-fence = A-cumul(strong-fence | po-rel) | wmb
+let cumul-fence = A-cumul(strong-fence | po-rel) | wmb | po-rel-rf-acq-po
 let prop = (overwrite & ext)? ; cumul-fence* ; rfe?
 

tools/memory-model/linux-kernel.cat let dep = addr | data · line 72

Quoted 1 line

tools/memory-model/linux-kernel.cat +0 -0

 (*

I thought the goal you were aiming for was a patch making atomic-acquire/ordinary-release be RCtso (along with lock/unlock), while leaving ordinary-acquire/ordinary-release to remain RCpc.

Clearly that is not what this patch does.

Alan

I take this opportunity to summarize my viewpoint on these matters:

Someone would have to write the commit message for the above diff ... that is, to describe -why- we should go RCtso (and update the documen- tation accordingly); by now, the only argument for this appears to be:
"(most) people expect strong ordering" _and they will be "lazy enough" to not check their expectations by using the LKMM tool (paraphrasing from [1]); IAC, Linux "might work" better if we add this ordering to the LKMM. Agreeing on such an approach would mean agreeing that this argument "wins" over:

"We want new architectures to implement acquire/release efficiently,
and it's not unlikely that they will have acquire loads that are similar in semantics to LDAPR." [2]

"RISC-V probably would have been RCpc [...] it takes extra fences
to go from RCpc to either "RCtso" or RCsc." [3]

(or similar instances) since, of course, there is no such thing as a "free strong ordering"; and I'm not only talking about "efficiency", I'm also thinking at the fact that someone will have to maintain that ordering across all the architectures and in the LKMM.

If, OTOH, we agree that the above "win"/assumption is valid only for locks or, in other/better words, if we agree that we should maintain _two_ distinct release-acquire orderings (a first one for unlock-lock sequences and a second one for ordinary/atomic release-acquire, say, as proposed in the patch under RFC),

I ask that we audit and modify
the generic code accordingly/as suggested in other posts _before_ we upstream the changes for the LKMM: we should identify those places where (the newly introduced) _gap_ between unlock-lock and the other release-acquire is not admissible and fix those places (notice that this entails, in part., agreeing on what/where the generic code is).

Finally, if we don't agree with the above assumption at all (that is, no matter if we are considering unlock-lock or other release-acquire sequences), then we should go RCpc [4].

I described three different approaches (which are NOT "independent", clearly; let us find an agreement...); even though some of them look insane to me, I'm currently open to all of them: thoughts?

Andrea

[1] http://lkml.kernel.org/r/[email protected]

    http://lkml.kernel.org/r/CA+55aFwKpkU5C23OYt1HCiD3X5bJHVh1jz5G2dSnF1+kVrOCTA@mail.gmail.com
[2] http://lkml.kernel.org/r/[email protected]
[3] http://lkml.kernel.org/r/[email protected]
[4] http://lkml.kernel.org/r/20180711123421.GA9673@andrea
    http://lkml.kernel.org/r/[email protected]

Quoted 2 lines · Andrea Parri

I take this opportunity to summarize my viewpoint on these matters:

Quoted 13 lines

Someone would have to write the commit message for the above diff ... that is, to describe -why- we should go RCtso (and update the documen- tation accordingly); by now, the only argument for this appears to be:
"(most) people expect strong ordering" _and they will be "lazy enough" to not check their expectations by using the LKMM tool (paraphrasing from [1]); IAC, Linux "might work" better if we add this ordering to the LKMM. Agreeing on such an approach would mean agreeing that this argument "wins" over:

"We want new architectures to implement acquire/release efficiently,
and it's not unlikely that they will have acquire loads that are similar in semantics to LDAPR." [2]

Quoted 8 lines

"RISC-V probably would have been RCpc [...] it takes extra fences
to go from RCpc to either "RCtso" or RCsc." [3]

(or similar instances) since, of course, there is no such thing as a "free strong ordering"; and I'm not only talking about "efficiency", I'm also thinking at the fact that someone will have to maintain that ordering across all the architectures and in the LKMM.

Quoted 5 lines

If, OTOH, we agree that the above "win"/assumption is valid only for locks or, in other/better words, if we agree that we should maintain _two_ distinct release-acquire orderings (a first one for unlock-lock sequences and a second one for ordinary/atomic release-acquire, say, as proposed in the patch under RFC),

In fact, there have have been _two_ proposals along this line. One as you describe here (which is what the 1/7 patch under discussion does), and another in which unlock-lock sequences and atomic acquire-release sequences both have "RCtso" semantics while ordinary acquire/release sequences have RCpc semantics. You should consider the second proposal. It could be put into the LKMM quite easily by building upon this 1/7 patch.

Quoted 7 lines

I ask that we audit and modify
the generic code accordingly/as suggested in other posts _before_ we upstream the changes for the LKMM: we should identify those places where (the newly introduced) _gap_ between unlock-lock and the other release-acquire is not admissible and fix those places (notice that this entails, in part., agreeing on what/where the generic code is).

Have you noticed any part of the generic code that relies on ordinary acquire-release (rather than atomic RMW acquire-release) in order to implement locking constructs?

Quoted 7 lines

Finally, if we don't agree with the above assumption at all (that is, no matter if we are considering unlock-lock or other release-acquire sequences), then we should go RCpc [4].

I described three different approaches (which are NOT "independent", clearly; let us find an agreement...); even though some of them look insane to me, I'm currently open to all of them: thoughts?

How about this fourth approach?

Alan

Quoted 8 lines

Andrea

[1] http://lkml.kernel.org/r/[email protected]

    http://lkml.kernel.org/r/CA+55aFwKpkU5C23OYt1HCiD3X5bJHVh1jz5G2dSnF1+kVrOCTA@mail.gmail.com
[2] http://lkml.kernel.org/r/[email protected]
[3] http://lkml.kernel.org/r/[email protected]
[4] http://lkml.kernel.org/r/20180711123421.GA9673@andrea
    http://lkml.kernel.org/r/[email protected]

Quoted 3 lines

Have you noticed any part of the generic code that relies on ordinary acquire-release (rather than atomic RMW acquire-release) in order to implement locking constructs?

There are several places in code where the "lock-acquire" seems to be provided by an atomic_cond_read_acquire/smp_cond_load_acquire: I have mentioned one in qspinlock in this thread; qrwlock and mcs_spinlock provide other examples (grep for the primitives...).

As long as we don't consider these primitive as RMW (which would seem odd...) or as acquire for which "most people expect strong ordering" (see above), these provides other examples for the _gap_ I mentioned.

Quoted 4 lines · Andrea Parri

Quoted 3 lines

Have you noticed any part of the generic code that relies on ordinary acquire-release (rather than atomic RMW acquire-release) in order to implement locking constructs?

Quoted 8 lines

There are several places in code where the "lock-acquire" seems to be provided by an atomic_cond_read_acquire/smp_cond_load_acquire: I have mentioned one in qspinlock in this thread; qrwlock and mcs_spinlock provide other examples (grep for the primitives...).

As long as we don't consider these primitive as RMW (which would seem odd...) or as acquire for which "most people expect strong ordering" (see above), these provides other examples for the _gap_ I mentioned.

Okay, now I understand your objection. It does appear that on RISC-V, if nowhere else, the current implementations of qspinlock, qrwlock, etc. will not provide "RCtso" ordering.

The discussions surrounding this topic have been so lengthy and confusing that I have lost track of any comments Palmer or Daniel may have made concerning this potential problem.

One possible resolution would be to define smp_cond_load_acquire() specially on RISC-V so that it provided the same ordering guarantees as RMW-acquire. (Plus adding a comment in the asm-generic/barrier.h pointing out the necessity for the stronger guarantee on all architectures.)

Another would be to replace the usages of atomic/smp_cond_load_acquire in the locking constructs with a new function that would otherwise be the same but would provide the ordering guarantee we want.

Do you think either of these would be an adequate fix?

Quoted 33 lines · Alan Stern

Quoted 4 lines · Andrea Parri

Quoted 3 lines

Have you noticed any part of the generic code that relies on ordinary acquire-release (rather than atomic RMW acquire-release) in order to implement locking constructs?

Quoted 8 lines

There are several places in code where the "lock-acquire" seems to be provided by an atomic_cond_read_acquire/smp_cond_load_acquire: I have mentioned one in qspinlock in this thread; qrwlock and mcs_spinlock provide other examples (grep for the primitives...).

As long as we don't consider these primitive as RMW (which would seem odd...) or as acquire for which "most people expect strong ordering" (see above), these provides other examples for the _gap_ I mentioned.

Okay, now I understand your objection. It does appear that on RISC-V, if nowhere else, the current implementations of qspinlock, qrwlock, etc. will not provide "RCtso" ordering.

The discussions surrounding this topic have been so lengthy and confusing that I have lost track of any comments Palmer or Daniel may have made concerning this potential problem.

One possible resolution would be to define smp_cond_load_acquire() specially on RISC-V so that it provided the same ordering guarantees as RMW-acquire. (Plus adding a comment in the asm-generic/barrier.h pointing out the necessity for the stronger guarantee on all architectures.)

Another would be to replace the usages of atomic/smp_cond_load_acquire in the locking constructs with a new function that would otherwise be the same but would provide the ordering guarantee we want.

Quoted 1 line

Do you think either of these would be an adequate fix?

I didn't think RISC-V used qspinlock or qrwlock, so I'm not sure there's actually anything to fix, is there?

Will

Quoted 39 lines · Will Deacon

Quoted 29 lines · Alan Stern

Quoted 4 lines · Andrea Parri

Quoted 3 lines

Have you noticed any part of the generic code that relies on ordinary acquire-release (rather than atomic RMW acquire-release) in order to implement locking constructs?

Quoted 8 lines

There are several places in code where the "lock-acquire" seems to be provided by an atomic_cond_read_acquire/smp_cond_load_acquire: I have mentioned one in qspinlock in this thread; qrwlock and mcs_spinlock provide other examples (grep for the primitives...).

As long as we don't consider these primitive as RMW (which would seem odd...) or as acquire for which "most people expect strong ordering" (see above), these provides other examples for the _gap_ I mentioned.

Okay, now I understand your objection. It does appear that on RISC-V, if nowhere else, the current implementations of qspinlock, qrwlock, etc. will not provide "RCtso" ordering.

The discussions surrounding this topic have been so lengthy and confusing that I have lost track of any comments Palmer or Daniel may have made concerning this potential problem.

One possible resolution would be to define smp_cond_load_acquire() specially on RISC-V so that it provided the same ordering guarantees as RMW-acquire. (Plus adding a comment in the asm-generic/barrier.h pointing out the necessity for the stronger guarantee on all architectures.)

Quoted 5 lines

Another would be to replace the usages of atomic/smp_cond_load_acquire in the locking constructs with a new function that would otherwise be the same but would provide the ordering guarantee we want.

Do you think either of these would be an adequate fix?

I didn't think RISC-V used qspinlock or qrwlock, so I'm not sure there's actually anything to fix, is there?

Quoted 1 line

Will

I've also lost track of whether the current preference is or is not for RCtso, or in which subset of cases RCtso is currently preferred. For whichever cases do in fact need to be RCtso, the RISC-V approach would still be the same as what I've written in the past, as far as I can tell [1].

In a nutshell, if a data structure uses only atomics with .aq/.rl, RISC-V provides RCtso already anyway. If a data structure uses fences, or mixes fences and atomics, we can replace a "fence r,rw" or a "fence rw,w" with a "fence.tso" (== fence r,rw + fence rw,w) as necessary, at the cost of some amount of performance.

I suppose the answer to the question of whether smp_cond_load_acquire() needs to change depends on where exactly RCtso is needed, and which data structures actually use that vs. some other macro.

Does that answer your question Alan? Does it make sense?

[1] https://lore.kernel.org/lkml/[email protected]/

Dan

Quoted 40 lines · Daniel Lustig

Quoted 39 lines · Will Deacon

Quoted 29 lines · Alan Stern

Quoted 4 lines · Andrea Parri

Quoted 3 lines

Have you noticed any part of the generic code that relies on ordinary acquire-release (rather than atomic RMW acquire-release) in order to implement locking constructs?

Quoted 8 lines

There are several places in code where the "lock-acquire" seems to be provided by an atomic_cond_read_acquire/smp_cond_load_acquire: I have mentioned one in qspinlock in this thread; qrwlock and mcs_spinlock provide other examples (grep for the primitives...).

As long as we don't consider these primitive as RMW (which would seem odd...) or as acquire for which "most people expect strong ordering" (see above), these provides other examples for the _gap_ I mentioned.

Okay, now I understand your objection. It does appear that on RISC-V, if nowhere else, the current implementations of qspinlock, qrwlock, etc. will not provide "RCtso" ordering.

The discussions surrounding this topic have been so lengthy and confusing that I have lost track of any comments Palmer or Daniel may have made concerning this potential problem.

One possible resolution would be to define smp_cond_load_acquire() specially on RISC-V so that it provided the same ordering guarantees as RMW-acquire. (Plus adding a comment in the asm-generic/barrier.h pointing out the necessity for the stronger guarantee on all architectures.)

Quoted 5 lines

Another would be to replace the usages of atomic/smp_cond_load_acquire in the locking constructs with a new function that would otherwise be the same but would provide the ordering guarantee we want.

Do you think either of these would be an adequate fix?

I didn't think RISC-V used qspinlock or qrwlock, so I'm not sure there's actually anything to fix, is there?

Quoted 7 lines

Quoted 1 line

Will

I've also lost track of whether the current preference is or is not for RCtso, or in which subset of cases RCtso is currently preferred. For whichever cases do in fact need to be RCtso, the RISC-V approach would still be the same as what I've written in the past, as far as I can tell [1].

The patch which Paul plans to send in for the next merge window makes the LKMM require RCtso ordering for spinlocks, and by extension, for all locking operations. As I understand it, the current RISC-V implementation of spinlocks does provide this ordering.

We have discussed creating another patch for the LKMM which would require RMW-acquire/ordinary-release also to have RCtso ordering. Nobody has written the patch yet, but it would be straightfoward. The rationale is that many types of locks are implemented in terms of RMW-acquire, so if the locks are required to be RCtso then so should the lower-level operations they are built from.

Will feels strongly (and Linus agrees) that the LKMM should not require ordinary acquire and release to be any stronger than RCpc.

The issue that Andrea raised has to do with qspinlock, qrwlock, and mcs_spinlock, which are implemented using smp_cond_load_acquire() instead of RMW-acquire. This provides only the ordering properties of smp_load_acquire(), namely RCpc, which means that qspinlocks etc. might not be RCtso.

Since we do want locks to be RCtso, the question is how to resolve this discrepancy.

Quoted 11 lines

In a nutshell, if a data structure uses only atomics with .aq/.rl, RISC-V provides RCtso already anyway. If a data structure uses fences, or mixes fences and atomics, we can replace a "fence r,rw" or a "fence rw,w" with a "fence.tso" (== fence r,rw + fence rw,w) as necessary, at the cost of some amount of performance.

I suppose the answer to the question of whether smp_cond_load_acquire() needs to change depends on where exactly RCtso is needed, and which data structures actually use that vs. some other macro.

Does that answer your question Alan? Does it make sense?

On all other architectures, as far as I know, smp_cond_load_acquire() is in fact RCtso. Any changes would only be needed on RISC-V.

A quick grep of the kernel source (not quite up-to-date, unfortunately) turns up only the following additional usages of smp_cond_load_acquire():

It is used in kernel/smp.c for csd_lock(); I don't know what that is meant for.

It is also used in the scheduler core (kernel/sched/core.c). I don't know what ordering requirements the scheduler has for it, but Peter does.

There's a usage in drivers/iommu/arm-smmu-v3.c, but no comment to explain why it is needed.

To tell the truth, I'm not aware of any code in the kernel that actually _needs_ RCtso ordering for locks, but Peter and Will are quite firm that it should be required. Linus would actually like locks to be RCsc, but he recognizes that this would incur a noticeable performance penalty on Power so he'll settle for RCtso.

I'm not in a position to say whether smp_cond_load_acquire() should be changed, but hopefully this information will help others to make that determination.

Alan

Quoted 3 lines

[1] https://lore.kernel.org/lkml/[email protected]/

Dan

Will feels strongly (and Linus agrees) that the LKMM should not require ordinary acquire and release to be any stronger than RCpc.

The issue that Andrea raised has to do with qspinlock, qrwlock, and mcs_spinlock, which are implemented using smp_cond_load_acquire() instead of RMW-acquire. This provides only the ordering properties of smp_load_acquire(), namely RCpc, which means that qspinlocks etc. might not be RCtso.

Since we do want locks to be RCtso, the question is how to resolve this discrepancy.

To tell the truth, I'm not aware of any code in the kernel that actually _needs_ RCtso ordering for locks, but Peter and Will are quite firm that it should be required. Linus would actually like locks to be RCsc, but he recognizes that this would incur a noticeable performance penalty on Power so he'll settle for RCtso.

Quoted 6 lines

Quoted 3 lines

Take for instance the pattern where RCU relies on RCsc locks, this is an entirely simple and straight forward use of locks, yet completely fails on this subtle point.

Do you happen to remember exactly where in the kernel source this occurs?

Look for the uses of raw_spin_lock_irq_rcu_node() and friends in kernel/rcu and include/linux/*rcu*, along with the explanation in Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html

Quoted 10 lines · Paul E. McKenney

Quoted 6 lines

Quoted 3 lines

Take for instance the pattern where RCU relies on RCsc locks, this is an entirely simple and straight forward use of locks, yet completely fails on this subtle point.

Do you happen to remember exactly where in the kernel source this occurs?

Look for the uses of raw_spin_lock_irq_rcu_node() and friends in kernel/rcu and include/linux/*rcu*, along with the explanation in Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html

I just now started looking at this for the first time, and I was struck by the sloppy thinking displayed in the very first paragraph of the HTML document! For example, consider the third sentence:

Similarly, any code that happens before the beginning of a given RCU grace period is guaranteed to see the effects of all accesses following the end of that grace period that are within RCU read-side critical sections.

Is RCU now a time machine? :-)

I think what you meant to write in the second and third sentences was something more like this:

Any code in an RCU critical section that extends beyond the end of a given RCU grace period is guaranteed to see the effects of all accesses which were visible to the grace period's CPU before the start of the grace period. Similarly, any code that follows an RCU grace period (on the grace period's CPU) is guaranteed to see the effects of all accesses which were visible to an RCU critical section that began before the start of the grace period.

Also, the document doesn't seem to explain how Tree RCU relies on the lock-ordering guarantees of raw_spin_lock_rcu_node() and friends. It _says_ that these guarantees are used, but not how or where. (Unless I missed something; I didn't read the document all that carefully.)

In any case, you should bear in mind that the lock ordering provided by Peter's raw_spin_lock_rcu_node() and friends is not the same as what we have been discussing for the LKMM:

Peter's routines are meant for the case where you release one lock and then acquire another (for example, locks in two different levels of the RCU tree).

The LKMM patch applies only to cases where one CPU releases a lock and then that CPU or another acquires the _same_ lock again.

As another difference, the litmus test given near the start of the "Tree RCU Grace Period Memory Ordering Building Blocks" section would not be forbidden by the LKMM, even with RCtso locks, if it didn't use raw_spin_lock_rcu_node(). This is because the litmus test is forbidden only when locks are RCsc, which is what raw_spin_lock_rcu_node() provides.

So I don't see how the RCU code can be held up as an example either for or against requiring locks to be RCtso.

Quoted 11 lines

I think what you meant to write in the second and third sentences was something more like this:

Any code in an RCU critical section that extends beyond the end of a given RCU grace period is guaranteed to see the effects of all accesses which were visible to the grace period's CPU before the start of the grace period. Similarly, any code that follows an RCU grace period (on the grace period's CPU) is guaranteed to see the effects of all accesses which were visible to an RCU critical section that began before the start of the grace period.

That looks to me to be an improvement, other than that the "(on the grace period's CPU)" seems a bit restrictive -- you could for example have a release-acquire chain starting after the grace period, right?

Quoted 4 lines

Also, the document doesn't seem to explain how Tree RCU relies on the lock-ordering guarantees of raw_spin_lock_rcu_node() and friends. It _says_ that these guarantees are used, but not how or where. (Unless I missed something; I didn't read the document all that carefully.)

The closest is this sentence: "But the only part of rcu_prepare_for_idle() that really matters for this discussion are lines 37–39", which refers to this code:

37     raw_spin_lock_rcu_node(rnp);
38     needwake = rcu_accelerate_cbs(rsp, rnp, rdp);
39     raw_spin_unlock_rcu_node(rnp);

I could add a sentence explaining the importance of the smp_mb__after_unlock_lock() -- is that what you are getting at?

Quoted 12 lines

In any case, you should bear in mind that the lock ordering provided by Peter's raw_spin_lock_rcu_node() and friends is not the same as what we have been discussing for the LKMM:

Peter's routines are meant for the case where you release one lock and then acquire another (for example, locks in two different levels of the RCU tree).

The LKMM patch applies only to cases where one CPU releases a lock and then that CPU or another acquires the _same_ lock again.

Quoted 6 lines

As another difference, the litmus test given near the start of the "Tree RCU Grace Period Memory Ordering Building Blocks" section would not be forbidden by the LKMM, even with RCtso locks, if it didn't use raw_spin_lock_rcu_node(). This is because the litmus test is forbidden only when locks are RCsc, which is what raw_spin_lock_rcu_node() provides.

Agreed.

Quoted 2 lines

So I don't see how the RCU code can be held up as an example either for or against requiring locks to be RCtso.

Agreed again. The use of smp_mb__after_unlock_lock() instead provides RCsc. But this use case is deemed sufficiently rare that smp_mb__after_unlock_lock() is defined within RCU.

Not having received any responses to the question about usages of RCtso locks, I have decided to post the newly updated version of the patch description for commit c8c5779c854f ("tools/memory-model: Add extra ordering for locks and remove it for ordinary release/acquire") in Paul's LKMM branch. There are no changes to the patch itself.

Hopefully this includes all the important issues that people have raised. (Admittedly, some parts of the discussion have seemed less consequential than others, and some parts I didn't understand at all.)

Alan

-----------------------------------------------------------------------------
More than one kernel developer has expressed the opinion that the LKMM should enforce ordering of writes by locking. In other words, given the following code:

	WRITE_ONCE(x, 1);
	spin_unlock(&s):
	spin_lock(&s);
	WRITE_ONCE(y, 1);

the stores to x and y should be propagated in order to all other CPUs, even though those other CPUs might not access the lock s. In terms of the memory model, this means expanding the cumul-fence relation.

Locks should also provide read-read (and read-write) ordering in a similar way. Given:

	READ_ONCE(x);
	spin_unlock(&s);
	spin_lock(&s);
	READ_ONCE(y);		// or WRITE_ONCE(y, 1);

the load of x should be executed before the load of (or store to) y. The LKMM already provides this ordering, but it provides it even in the case where the two accesses are separated by a release/acquire pair of fences rather than unlock/lock. This would prevent architectures from using weakly ordered implementations of release and acquire, which seems like an unnecessary restriction. The patch therefore removes the ordering requirement from the LKMM for that case.

There are several arguments both for and against this change. Let us refer to these enhanced ordering properties by saying that the LKMM would require locks to be RCtso (a bit of a misnomer, but analogous to RCpc and RCsc) and it would require ordinary acquire/release only to be RCpc. (Note: In the following, the phrase "all supported architectures" does not include RISC-V, which is still somewhat in a state of flux.)

Pros:

The kernel already provides RCtso ordering for locks on all supported architectures, even though this is not stated explicitly anywhere. Therefore the LKMM should formalize it.

In theory, guaranteeing RCtso ordering would reduce the need for additional barrier-like constructs meant to increase the ordering strength of locks.

Will Deacon and Peter Zijlstra are strongly in favor of formalizing the RCtso requirement. Linus Torvalds and Will would like to go even further, requiring locks to have RCsc behavior (ordering preceding writes against later reads), but they recognize that this would incur a noticeable performance degradation on the POWER architecture. Linus also points out that people have made the mistake, in the past, of assuming that locking has stronger ordering properties than is currently guaranteed, and this change would reduce the likelihood of such mistakes.

Cons:

Andrea Parri and Luc Maranget feel that locks should have the same ordering properties as ordinary acquire/release (indeed, Luc points out that the names "acquire" and "release" derive from the usage of locks) and that having different ordering properties for different forms of acquires and releases would be confusing and unmaintainable.

Will and Linus, on the other
hand, feel that architectures should be free to implement ordinary acquire/release using relatively weak RCpc machine instructions. Linus points out that locks should be easy for people to use without worrying about memory consistency issues, since they are so pervasive in the kernel, whereas acquire/release is much more of an "expertss only" tool.

Locks are constructed from lower-level primitives, typically RMW-acquire (for locking) and ordinary release (for unlock). It is illogical to require stronger ordering properties from

the high-level operations than from the low-level operations they comprise. Thus, this change would make

while (cmpxchg_acquire(&s, 0, 1) != 0)
cpu_relax();

an incorrect implementation of spin_lock(&s)

. In theory this
weakness can be ameliorated by changing the LKMM even further, requiring RMW-acquire/release also to be RCtso (which it already is on all supported architectures).

As far as I know, nobody has singled out any examples of code in the kernel that actually relies on locks being RCtso. (People mumble about RCU and the scheduler, but nobody has pointed to any actual code. If there are any real cases, their number is likely quite small.) If RCtso ordering is not needed, why require it?

A handful of locking constructs (qspinlocks, qrwlocks, and mcs_spinlocks) are built on top of smp_cond_load_acquire() instead of an RMW-acquire instruction. It currently provides only the ordinary acquire semantics, not the stronger ordering this patch would require of locks. In theory this could be ameliorated by requiring smp_cond_load_acquire() in combination with ordinary release also to be RCtso (which is currently true in all supported architectures).

On future weakly ordered architectures, people may be able to implement locks in a non-RCtso fashion with significant performance improvement. Meeting the RCtso requirement would necessarily add run-time overhead.

Overall, the technical aspects of these arguments seem relatively minor, and it appears mostly to boil down to a matter of opinion. Since the opinions of long-time kernel developers such as Linus, Peter, and Will carry more weight than those of Luc and Andrea, this patch changes the model in accordance with the developers' wishes.

Signed-off-by Alan Stern <[email protected]>

---

v.4: Added pros and cons discussion to the Changelog.

v.3: Rebased against the dev branch of Paul's linux-rcu tree. Changed unlock-rf-lock-po to po-unlock-rf-lock-po, making it more symmetrical and more in accordance with the use of fence.tso for the release on RISC-V.

v.2: Restrict the ordering to lock operations, not general release and acquire fences.

Quoted 7 lines

There are several arguments both for and against this change. Let us refer to these enhanced ordering properties by saying that the LKMM would require locks to be RCtso (a bit of a misnomer, but analogous to RCpc and RCsc) and it would require ordinary acquire/release only to be RCpc. (Note: In the following, the phrase "all supported architectures" does not include RISC-V, which is still somewhat in a state of flux.)

But "all supported architectures" does include RISC-V.

Quoted 10 lines

Pros:

The kernel already provides RCtso ordering for locks on all supported architectures, even though this is not stated explicitly anywhere. Therefore the LKMM should formalize it.

In theory, guaranteeing RCtso ordering would reduce the need for additional barrier-like constructs meant to increase the ordering strength of locks.

Quoted 10 lines

Will Deacon and Peter Zijlstra are strongly in favor of formalizing the RCtso requirement. Linus Torvalds and Will would like to go even further, requiring locks to have RCsc behavior (ordering preceding writes against later reads), but they recognize that this would incur a noticeable performance degradation on the POWER architecture. Linus also points out that people have made the mistake, in the past, of assuming that locking has stronger ordering properties than is currently guaranteed, and this change would reduce the likelihood of such mistakes.

Pros for "RCpc-only ordinary (and atomic) acquire/release" should go here.

Quoted 8 lines

Cons:

Andrea Parri and Luc Maranget feel that locks should have the same ordering properties as ordinary acquire/release (indeed, Luc points out that the names "acquire" and "release" derive from the usage of locks) and that having different ordering properties for different forms of acquires and releases would be confusing and unmaintainable.

s/unmaintainable/unneeded ("confusing" should already convey the
fragility of these changes).

Quoted 8 lines

Will and Linus, on the other
hand, feel that architectures should be free to implement ordinary acquire/release using relatively weak RCpc machine instructions. Linus points out that locks should be easy for people to use without worrying about memory consistency issues, since they are so pervasive in the kernel, whereas acquire/release is much more of an "expertss only" tool.

Quoted 3 lines

Locks are constructed from lower-level primitives, typically RMW-acquire (for locking) and ordinary release (for unlock). It is illogical to require stronger ordering properties from

s/It is illogical/It is detrimental to the LKMM's applicability

Quoted 7 lines

the high-level operations than from the low-level operations they comprise. Thus, this change would make

while (cmpxchg_acquire(&s, 0, 1) != 0)
cpu_relax();

an incorrect implementation of spin_lock(&s)

... w.r.t. the LKMM (same for smp_cond_load_acquire).

Quoted 5 lines

. In theory this
weakness can be ameliorated by changing the LKMM even further, requiring RMW-acquire/release also to be RCtso (which it already is on all supported architectures).

Quoted 6 lines

As far as I know, nobody has singled out any examples of code in the kernel that actually relies on locks being RCtso. (People mumble about RCU and the scheduler, but nobody has pointed to any actual code. If there are any real cases, their number is likely quite small.) If RCtso ordering is not needed, why require it?

Your patch and Paul said "opinions ranking".

Andrea

The updated Changelog draft is below.

Alan.

--------------------------------------------------------------------------
More than one kernel developer has expressed the opinion that the LKMM should enforce ordering of writes by locking. In other words, given the following code:

	WRITE_ONCE(x, 1);
	spin_unlock(&s):
	spin_lock(&s);
	WRITE_ONCE(y, 1);

the stores to x and y should be propagated in order to all other CPUs, even though those other CPUs might not access the lock s. In terms of the memory model, this means expanding the cumul-fence relation.

Locks should also provide read-read (and read-write) ordering in a similar way. Given:

	READ_ONCE(x);
	spin_unlock(&s);
	spin_lock(&s);
	READ_ONCE(y);		// or WRITE_ONCE(y, 1);

the load of x should be executed before the load of (or store to) y. The LKMM already provides this ordering, but it provides it even in the case where the two accesses are separated by a release/acquire pair of fences rather than unlock/lock. This would prevent architectures from using weakly ordered implementations of release and acquire, which seems like an unnecessary restriction. The patch therefore removes the ordering requirement from the LKMM for that case.

There are several arguments both for and against this change. Let us refer to these enhanced ordering properties by saying that the LKMM would require locks to be RCtso (a bit of a misnomer, but analogous to RCpc and RCsc) and it would require ordinary acquire/release only to be RCpc. (Note: In the following, the phrase "all supported architectures" is meant not to include RISC-V. Although RISC-V is indeed supported by the kernel, the implementation is still somewhat in a state of flux and therefore statements about it would be premature.)

Pros:

The kernel already provides RCtso ordering for locks on all supported architectures, even though this is not stated explicitly anywhere. Therefore the LKMM should formalize it.

In theory, guaranteeing RCtso ordering would reduce the need for additional barrier-like constructs meant to increase the ordering strength of locks.

Will Deacon and Peter Zijlstra are strongly in favor of formalizing the RCtso requirement. Linus Torvalds and Peter would like to go even further, requiring locks to have RCsc behavior (ordering preceding writes against later reads), but they recognize that this would incur a noticeable performance degradation on the POWER architecture. Linus also points out that people have made the mistake, in the past, of assuming that locking has stronger ordering properties than is currently guaranteed, and this change would reduce the likelihood of such mistakes.

Not requiring ordinary acquire/release to be any stronger than RCpc may prove advantageous for future architectures, allowing them to implement smp_load_acquire() and smp_store_release() with more efficient machine instructions than would be possible if the operations had to be RCtso. Will and Linus approve this rationale, hypothetical though it is at the moment (it may end up affecting the RISC-V implementation). The same argument may or may not apply to RMW-acquire/release; see also the second Con entry below.

Linus feels that locks should be easy for people to use without worrying about memory consistency issues, since they are so pervasive in the kernel, whereas acquire/release is much more of an "experts only" tool. Requiring locks to be RCtso is a step in this direction.

Cons:

Andrea Parri and Luc Maranget think that locks should have the same ordering properties as ordinary acquire/release (indeed, Luc points out that the names "acquire" and "release" derive from the usage of locks). Andrea points out that having different ordering properties for different forms of acquires and releases is not only unnecessary, it would also be confusing and unmaintainable.

Locks are constructed from lower-level primitives, typically RMW-acquire (for locking) and ordinary release (for unlock). It is illogical to require stronger ordering properties from the high-level operations than from the low-level operations they comprise. Thus, this change would make

while (cmpxchg_acquire(&s, 0, 1) != 0)
cpu_relax();

an incorrect implementation of spin_lock(&s) as far as the LKMM is concerned. In theory this weakness can be ameliorated by changing the LKMM even further, requiring RMW-acquire/release also to be RCtso (which it already is on all supported architectures).

As far as I know, nobody has singled out any examples of code in the kernel that actually relies on locks being RCtso. (People mumble about RCU and the scheduler, but nobody has pointed to any actual code. If there are any real cases, their number is likely quite small.) If RCtso ordering is not needed, why require it?

A handful of locking constructs (qspinlocks, qrwlocks, and mcs_spinlocks) are built on top of smp_cond_load_acquire() instead of an RMW-acquire instruction. It currently provides only the ordinary acquire semantics, not the stronger ordering this patch would require of locks. In theory this could be ameliorated by requiring smp_cond_load_acquire() in combination with ordinary release also to be RCtso (which is currently true on all supported architectures).

On future weakly ordered architectures, people may be able to implement locks in a non-RCtso fashion with significant performance improvement. Meeting the RCtso requirement would necessarily add run-time overhead.

Overall, the technical aspects of these arguments seem relatively minor, and it appears mostly to boil down to a matter of opinion. Since the opinions of senior kernel maintainers such as Linus, Peter, and Will carry more weight than those of Luc and Andrea, this patch changes the model in accordance with the maintainers' wishes.

Signed-off-by Alan Stern <[email protected]>

v.5: Incorporated feedback from Andrea regarding the updated Changelog.

v.4: Added pros and cons discussion to the Changelog.

v.3: Rebased against the dev branch of Paul's linux-rcu tree. Changed unlock-rf-lock-po to po-unlock-rf-lock-po, making it more symmetrical and more in accordance with the use of fence.tso for the release on RISC-V.

v.2: Restrict the ordering to lock operations, not general release and acquire fences.

More than one kernel developer has expressed the opinion that the LKMM should enforce ordering of writes by locking. In other words, given the following code:

	WRITE_ONCE(x, 1);
	spin_unlock(&s):
	spin_lock(&s);
	WRITE_ONCE(y, 1);

the stores to x and y should be propagated in order to all other CPUs, even though those other CPUs might not access the lock s. In terms of the memory model, this means expanding the cumul-fence relation.

Locks should also provide read-read (and read-write) ordering in a similar way. Given:

	READ_ONCE(x);
	spin_unlock(&s);
	spin_lock(&s);
	READ_ONCE(y);		// or WRITE_ONCE(y, 1);

the load of x should be executed before the load of (or store to) y. The LKMM already provides this ordering, but it provides it even in the case where the two accesses are separated by a release/acquire pair of fences rather than unlock/lock. This would prevent architectures from using weakly ordered implementations of release and acquire, which seems like an unnecessary restriction. The patch therefore removes the ordering requirement from the LKMM for that case.

There are several arguments both for and against this change. Let us refer to these enhanced ordering properties by saying that the LKMM would require locks to be RCtso (a bit of a misnomer, but analogous to RCpc and RCsc) and it would require ordinary acquire/release only to be RCpc. (Note: In the following, the phrase "all supported architectures" is meant not to include RISC-V. Although RISC-V is indeed supported by the kernel, the implementation is still somewhat in a state of flux and therefore statements about it would be premature.)

Pros:

The kernel already provides RCtso ordering for locks on all supported architectures, even though this is not stated explicitly anywhere. Therefore the LKMM should formalize it.

In theory, guaranteeing RCtso ordering would reduce the need for additional barrier-like constructs meant to increase the ordering strength of locks.

Will Deacon and Peter Zijlstra are strongly in favor of formalizing the RCtso requirement. Linus Torvalds and Will would like to go even further, requiring locks to have RCsc behavior (ordering preceding writes against later reads), but they recognize that this would incur a noticeable performance degradation on the POWER architecture. Linus also points out that people have made the mistake, in the past, of assuming that locking has stronger ordering properties than is currently guaranteed, and this change would reduce the likelihood of such mistakes.

Not requiring ordinary acquire/release to be any stronger than RCpc may prove advantageous for future architectures, allowing them to implement smp_load_acquire() and smp_store_release() with more efficient machine instructions than would be possible if the operations had to be RCtso. Will and Linus approve this rationale, hypothetical though it is at the moment (it may end up affecting the RISC-V implementation). The same argument may or may not apply to RMW-acquire/release; see also the second Con entry below.

Linus feels that locks should be easy for people to use without worrying about memory consistency issues, since they are so pervasive in the kernel, whereas acquire/release is much more of an "experts only" tool. Requiring locks to be RCtso is a step in this direction.

Cons:

Andrea Parri and Luc Maranget think that locks should have the same ordering properties as ordinary acquire/release (indeed, Luc points out that the names "acquire" and "release" derive from the usage of locks). Andrea points out that having different ordering properties for different forms of acquires and releases is not only unnecessary, it would also be confusing and unmaintainable.

Locks are constructed from lower-level primitives, typically RMW-acquire (for locking) and ordinary release (for unlock). It is illogical to require stronger ordering properties from the high-level operations than from the low-level operations they comprise. Thus, this change would make

while (cmpxchg_acquire(&s, 0, 1) != 0)
cpu_relax();

an incorrect implementation of spin_lock(&s) as far as the LKMM is concerned. In theory this weakness can be ameliorated by changing the LKMM even further, requiring RMW-acquire/release also to be RCtso (which it already is on all supported architectures).

As far as I know, nobody has singled out any examples of code in the kernel that actually relies on locks being RCtso. (People mumble about RCU and the scheduler, but nobody has pointed to any actual code. If there are any real cases, their number is likely quite small.) If RCtso ordering is not needed, why require it?

A handful of locking constructs (qspinlocks, qrwlocks, and mcs_spinlocks) are built on top of smp_cond_load_acquire() instead of an RMW-acquire instruction. It currently provides only the ordinary acquire semantics, not the stronger ordering this patch would require of locks. In theory this could be ameliorated by requiring smp_cond_load_acquire() in combination with ordinary release also to be RCtso (which is currently true on all supported architectures).

On future weakly ordered architectures, people may be able to implement locks in a non-RCtso fashion with significant performance improvement. Meeting the RCtso requirement would necessarily add run-time overhead.

Overall, the technical aspects of these arguments seem relatively minor, and it appears mostly to boil down to a matter of opinion. Since the opinions of senior kernel maintainers such as Linus, Peter, and Will carry more weight than those of Luc and Andrea, this patch changes the model in accordance with the maintainers' wishes.

Signed-off-by Alan Stern <[email protected]>

Reviewed-by Will Deacon <[email protected]>

Acked-by Peter Zijlstra (Intel) <[email protected]>

Reviewed-by Andrea Parri <[email protected]>

---

v.5: Incorporated feedback from Andrea regarding the updated Changelog.

v.4: Added pros and cons discussion to the Changelog.

v.3: Rebased against the dev branch of Paul's linux-rcu tree. Changed unlock-rf-lock-po to po-unlock-rf-lock-po, making it more symmetrical and more in accordance with the use of fence.tso for the release on RISC-V.

v.2: Restrict the ordering to lock operations, not general release and acquire fences.

[as1871e]

 tools/memory-model/Documentation/explanation.txt                           |  186 +++++++---
 tools/memory-model/linux-kernel.cat                                        |    8 
 tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus |    7 
 3 files changed, 150 insertions(+), 51 deletions(-)

Index: usb-4.x/tools/memory-model/linux-kernel.cat
===================================================================

tools/memory-model/linux-kernel.cat +4 -4

@@ -38,7 +38,7 @@ let strong-fence = mb | gp
 (* Release Acquire *)
 let acq-po = [Acquire] ; po ; [M]
 let po-rel = [M] ; po ; [Release]
-let rfi-rel-acq = [Release] ; rfi ; [Acquire]
+let po-unlock-rf-lock-po = po ; [UL] ; rf ; [LKR] ; po
 
 (**********************************)
 (* Fundamental coherence ordering *)

@@ -60,13 +60,13 @@ let dep = addr | data
 let rwdep = (dep | ctrl) ; [W]
 let overwrite = co | fr
 let to-w = rwdep | (overwrite & int)
-let to-r = addr | (dep ; rfi) | rfi-rel-acq
+let to-r = addr | (dep ; rfi)
 let fence = strong-fence | wmb | po-rel | rmb | acq-po
-let ppo = to-r | to-w | fence
+let ppo = to-r | to-w | fence | (po-unlock-rf-lock-po & int)
 
 (* Propagation: Ordering from release operations and strong fences. *)
 let A-cumul(r) = rfe? ; r
-let cumul-fence = A-cumul(strong-fence | po-rel) | wmb
+let cumul-fence = A-cumul(strong-fence | po-rel) | wmb | po-unlock-rf-lock-po
 let prop = (overwrite & ext)? ; cumul-fence* ; rfe?
 
 (*

Index: usb-4.x/tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus
===================================================================

tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus +3 -4

@@ -1,11 +1,10 @@
 C ISA2+pooncelock+pooncelock+pombonce
 
 (*
- * Result: Sometimes
+ * Result: Never
  *
- * This test shows that the ordering provided by a lock-protected S
- * litmus test (P0() and P1()) are not visible to external process P2().
- * This is likely to change soon.
+ * This test shows that write-write ordering provided by locks
+ * (in P0() and P1()) is visible to external process P2().
  *)
 
 {}

Index: usb-4.x/tools/memory-model/Documentation/explanation.txt
===================================================================

tools/memory-model/Documentation/explanation.txt +143 -43

@@ -28,7 +28,8 @@ Explanation of the Linux-Kernel Memory C
   20. THE HAPPENS-BEFORE RELATION: hb
   21. THE PROPAGATES-BEFORE RELATION: pb
   22. RCU RELATIONS: rcu-link, gp, rscs, rcu-fence, and rb
-  23. ODDS AND ENDS
+  23. LOCKING
+  24. ODDS AND ENDS
 
 
 

@@ -1067,28 +1068,6 @@ allowing out-of-order writes like this t
 violating the write-write coherence rule by requiring the CPU not to
 send the W write to the memory subsystem at all!)
 
-There is one last example of preserved program order in the LKMM: when
-a load-acquire reads from an earlier store-release.  For example:
-
-	smp_store_release(&x, 123);
-	r1 = smp_load_acquire(&x);
-
-If the smp_load_acquire() ends up obtaining the 123 value that was
-stored by the smp_store_release(), the LKMM says that the load must be
-executed after the store; the store cannot be forwarded to the load.
-This requirement does not arise from the operational model, but it
-yields correct predictions on all architectures supported by the Linux
-kernel, although for differing reasons.
-
-On some architectures, including x86 and ARMv8, it is true that the
-store cannot be forwarded to the load.  On others, including PowerPC
-and ARMv7, smp_store_release() generates object code that starts with
-a fence and smp_load_acquire() generates object code that ends with a
-fence.  The upshot is that even though the store may be forwarded to
-the load, it is still true that any instruction preceding the store
-will be executed before the load or any following instructions, and
-the store will be executed before any instruction following the load.
-
 
 AND THEN THERE WAS ALPHA
 ------------------------

@@ -1766,6 +1745,147 @@ before it does, and the critical section
 grace period does and ends after it does.
 
 
+LOCKING
+-------
+
+The LKMM includes locking.  In fact, there is special code for locking
+in the formal model, added in order to make tools run faster.
+However, this special code is intended to be more or less equivalent
+to concepts we have already covered.  A spinlock_t variable is treated
+the same as an int, and spin_lock(&s) is treated almost the same as:
+
+	while (cmpxchg_acquire(&s, 0, 1) != 0)
+		cpu_relax();
+
+This waits until s is equal to 0 and then atomically sets it to 1,
+and the read part of the cmpxchg operation acts as an acquire fence.
+An alternate way to express the same thing would be:
+
+	r = xchg_acquire(&s, 1);
+
+along with a requirement that at the end, r = 0.  Similarly,
+spin_trylock(&s) is treated almost the same as:
+
+	return !cmpxchg_acquire(&s, 0, 1);
+
+which atomically sets s to 1 if it is currently equal to 0 and returns
+true if it succeeds (the read part of the cmpxchg operation acts as an
+acquire fence only if the operation is successful).  spin_unlock(&s)
+is treated almost the same as:
+
+	smp_store_release(&s, 0);
+
+The "almost" qualifiers above need some explanation.  In the LKMM, the
+store-release in a spin_unlock() and the load-acquire which forms the
+first half of the atomic rmw update in a spin_lock() or a successful
+spin_trylock() -- we can call these things lock-releases and
+lock-acquires -- have two properties beyond those of ordinary releases
+and acquires.
+
+First, when a lock-acquire reads from a lock-release, the LKMM
+requires that every instruction po-before the lock-release must
+execute before any instruction po-after the lock-acquire.  This would
+naturally hold if the release and acquire operations were on different
+CPUs, but the LKMM says it holds even when they are on the same CPU.
+For example:
+
+	int x, y;
+	spinlock_t s;
+
+	P0()
+	{
+		int r1, r2;
+
+		spin_lock(&s);
+		r1 = READ_ONCE(x);
+		spin_unlock(&s);
+		spin_lock(&s);
+		r2 = READ_ONCE(y);
+		spin_unlock(&s);
+	}
+
+	P1()
+	{
+		WRITE_ONCE(y, 1);
+		smp_wmb();
+		WRITE_ONCE(x, 1);
+	}
+
+Here the second spin_lock() reads from the first spin_unlock(), and
+therefore the load of x must execute before the load of y.  Thus we
+cannot have r1 = 1 and r2 = 0 at the end (this is an instance of the
+MP pattern).
+
+This requirement does not apply to ordinary release and acquire
+fences, only to lock-related operations.  For instance, suppose P0()
+in the example had been written as:
+
+	P0()
+	{
+		int r1, r2, r3;
+
+		r1 = READ_ONCE(x);
+		smp_store_release(&s, 1);
+		r3 = smp_load_acquire(&s);
+		r2 = READ_ONCE(y);
+	}
+
+Then the CPU would be allowed to forward the s = 1 value from the
+smp_store_release() to the smp_load_acquire(), executing the
+instructions in the following order:
+
+		r3 = smp_load_acquire(&s);	// Obtains r3 = 1
+		r2 = READ_ONCE(y);
+		r1 = READ_ONCE(x);
+		smp_store_release(&s, 1);	// Value is forwarded
+
+and thus it could load y before x, obtaining r2 = 0 and r1 = 1.
+
+Second, when a lock-acquire reads from a lock-release, and some other
+stores W and W' occur po-before the lock-release and po-after the
+lock-acquire respectively, the LKMM requires that W must propagate to
+each CPU before W' does.  For example, consider:
+
+	int x, y;
+	spinlock_t x;
+
+	P0()
+	{
+		spin_lock(&s);
+		WRITE_ONCE(x, 1);
+		spin_unlock(&s);
+	}
+
+	P1()
+	{
+		int r1;
+
+		spin_lock(&s);
+		r1 = READ_ONCE(x);
+		WRITE_ONCE(y, 1);
+		spin_unlock(&s);
+	}
+
+	P2()
+	{
+		int r2, r3;
+
+		r2 = READ_ONCE(y);
+		smp_rmb();
+		r3 = READ_ONCE(x);
+	}
+
+If r1 = 1 at the end then the spin_lock() in P1 must have read from
+the spin_unlock() in P0.  Hence the store to x must propagate to P2
+before the store to y does, so we cannot have r2 = 1 and r3 = 0.
+
+These two special requirements for lock-release and lock-acquire do
+not arise from the operational model.  Nevertheless, kernel developers
+have come to expect and rely on them because they do hold on all
+architectures supported by the Linux kernel, albeit for various
+differing reasons.
+
+
 ODDS AND ENDS
 -------------
 

@@ -1831,26 +1951,6 @@ they behave as follows:
 	events and the events preceding them against all po-later
 	events.
 
-The LKMM includes locking.  In fact, there is special code for locking
-in the formal model, added in order to make tools run faster.
-However, this special code is intended to be exactly equivalent to
-concepts we have already covered.  A spinlock_t variable is treated
-the same as an int, and spin_lock(&s) is treated the same as:
-
-	while (cmpxchg_acquire(&s, 0, 1) != 0)
-		cpu_relax();
-
-which waits until s is equal to 0 and then atomically sets it to 1,
-and where the read part of the atomic update is also an acquire fence.
-An alternate way to express the same thing would be:
-
-	r = xchg_acquire(&s, 1);
-
-along with a requirement that at the end, r = 0.  spin_unlock(&s) is
-treated the same as:
-
-	smp_store_release(&s, 0);
-
 Interestingly, RCU and locking each introduce the possibility of
 deadlock.  When faced with code sequences such as:
 

Quoted 9 lines

Quoted 5 lines

Yes, it's true that implementing locks with atomic_cmpxchg_acquire should be correct on all existing architectures. And Paul has invited a patch to modify the LKMM accordingly. If you feel that such a change would be a useful enhancement to the LKMM's applicability, please write it.

Yes, please! That would be the "RmW" discussion which Andrea partially quoted earlier on, so getting that going independently from this patch sounds like a great idea to me.

That was indeed one of the proposal we discussed. As you recalled, that proposal only covered RmWs load-acquire (and ordinary store-release); in particular, I realized that comments such as:

"The atomic_cond_read_acquire() call above has provided the
necessary acquire semantics required for locking."

[from kernel/locking/qspinlock.c]

(for example) would still _not have "generic validity" _if we added the above po-unlock-rf-lock-po term... (which, again, makes me somehow uncon- fortable); Would to have _all_ the acquire be admissible for you?

Quoted 31 lines · Andrea Parri

Quoted 29 lines · Alan Stern

Quoted 12 lines · Andrea Parri

Quoted 9 lines

All the architectures supported by the Linux kernel (including RISC-V) do provide this ordering for locks, albeit for varying reasons. Therefore this patch changes the model in accordance with the developers' wishes.

Signed-off-by Alan Stern <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Will Deacon <[email protected]>

Acked-by Peter Zijlstra (Intel) <[email protected]>

Round 2 ;-), I guess... Let me start from the uncontroversial points:

Quoted 8 lines

1) being able to use the LKMM to reason about generic locking code

     is useful and desirable (paraphrasing Peter in [1]);

2) strengthening the ordering requirements of such code isn't going to boost performance (that's "real maths").

This patch is taking (1) away from us and it is formalizing (2), with almost _no_ reason (no reason at all, if we stick to the commit msg.).

That's not quite fair. Generic code isn't always universally applicable; some of it is opt-in -- meant only for the architectures that can support it. In general, the LKMM allows us to reason about higher abstractions (such as locking) at a higher level, without necessarily being able to verify the architecture-specific details of the implementations.

Quoted 2 lines

No, generic code is "universally applicable" by definition; see below for more on this point.

Then perhaps we should be talking about "partially generic" code; i.e., code that applies to many but not all architectures.

Quoted 20 lines

Quoted 19 lines

Quoted 8 lines

In [2], Will wrote:

"[...] having them [the RMWs] closer to RCsc[/to the semantics of
locks] would make it easier to implement and reason about generic locking implementations (i.e. reduce the number of special ordering cases and/or magic barrier macros)"

Quoted 7 lines

"magic barrier macros" as in "mmh, if we accept this patch, we _should_ be auditing the various implementations/code to decide where to place a

smp_barrier_promote_ordinary_release_acquire_to_unlock_lock()" ;-)

or the like, and "special ordering cases" as in "arrgh, (otherwise) we are forced to reason on a per-arch basis while looking at generic code".

Currently the LKMM does not permit architecture-specific reasoning. It would have to be extended (in a different way for each architecture) first.

Quoted 2 lines

Completely agreed; that's why I said that this patch is detrimental to the applicability of the LKMM...

This ignores the attitude of the kernel developers who want locking to have the stronger RCtso semantics. From their point of view, the patch enhances the LKMM's applicability.

Quoted 26 lines

Quoted 5 lines

For example, one could use herd's POWER model combined with the POWER compilation scheme and the POWER-specific implementation of spinlocks for such reasoning. The LKMM alone is not sufficient.

Quoted 8 lines

Sure, programming and reasoning about the kernel would be easier if all architectures were the same. Unfortunately, we (and the kernel) have to live in the real world.

Quoted 2 lines

(Remark: ordinary release/acquire are building blocks for code such as
qspinlock, (q)rwlock, mutex, rwsem, ... and what else??).

But are these building blocks used the same way for all architectures?

The more, the better! (because then we have the LKMM tools)

We already discussed the "fast path" example: the fast paths of the above all resemble:

*_lock(s): atomic_cmpxchg_acquire(&s->val, UNLOCKED_VAL, LOCKED_VAL) ... *_unlock(s): ... atomic_set_release(&s->val, UNLOCKED_VAL)

When I read this code, I think "Of course." (unless some arch. has messed the implementation of cmpxchg_* up, which can happen...); but then I read the subject line of this patch and I think "Wait, what?".

Quoted 2 lines

You can argue that this is not generic code, sure; but why on Earth would you like to do so?!

Because the code might not work! On RISC-V, for example, the implementation of ordinary release/acquire is currently not as strong as atomic release/acquire.

Yes, it's true that implementing locks with atomic_cmpxchg_acquire should be correct on all existing architectures. And Paul has invited a patch to modify the LKMM accordingly. If you feel that such a change would be a useful enhancement to the LKMM's applicability, please write it.

Alan

From: Andrea Parri <[email protected]>

Amend commit 1f03e8d2919270 ("locking/barriers: Replace smp_cond_acquire() with smp_cond_load_acquire()") by updating the documentation accordingly. Also remove some obsolete information related to the implementation.

Signed-off-by Andrea Parri <[email protected]>

Cc Alan Stern <[email protected]>

Cc Will Deacon <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Boqun Feng <[email protected]>

Cc Nicholas Piggin <[email protected]>

Cc David Howells <[email protected]>

Cc Jade Alglave <[email protected]>

Cc Luc Maranget <[email protected]>

Cc "Paul E. McKenney" <[email protected]>

Cc Akira Yokosawa <[email protected]>

Cc Daniel Lustig <[email protected]>

Cc Jonathan Corbet <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 Documentation/memory-barriers.txt | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

Documentation/memory-barriers.txt +0 -0

index 0d8d7ef131e9..c1d913944ad8 100644

Quoted 29 lines · Paul E. McKenney

From: Andrea Parri <[email protected]>

Amend commit 1f03e8d2919270 ("locking/barriers: Replace smp_cond_acquire() with smp_cond_load_acquire()") by updating the documentation accordingly. Also remove some obsolete information related to the implementation.

Signed-off-by Andrea Parri <[email protected]>

Cc Alan Stern <[email protected]>

Cc Will Deacon <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Boqun Feng <[email protected]>

Cc Nicholas Piggin <[email protected]>

Cc David Howells <[email protected]>

Cc Jade Alglave <[email protected]>

Cc Luc Maranget <[email protected]>

Cc "Paul E. McKenney" <[email protected]>

Cc Akira Yokosawa <[email protected]>

Cc Daniel Lustig <[email protected]>

Cc Jonathan Corbet <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 Documentation/memory-barriers.txt | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

Documentation/memory-barriers.txt +0 -0

index 0d8d7ef131e9..c1d913944ad8 100644

Documentation/memory-barriers.txt And a couple of implicit varieties: · line 474

Quoted 6 lines

Documentation/memory-barriers.txt +1 -2

@@ -471,8 +471,7 @@ And a couple of implicit varieties:
      operations after the ACQUIRE operation will appear to happen after the
      ACQUIRE operation with respect to the other components of the system.
      ACQUIRE operations include LOCK operations and both smp_load_acquire()
-     and smp_cond_acquire() operations. The later builds the necessary ACQUIRE
-     semantics from relying on a control dependency and smp_rmb().
+     and smp_cond_load_acquire() operations.

Thanks for fixing the doc:

Acked-by Will Deacon <[email protected]>

This commit adds more detail about compiler optimizations and not-yet-modeled Linux-kernel APIs.

Signed-off-by Paul E. McKenney <[email protected]>

---
 tools/memory-model/README | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

tools/memory-model/README +6 -0

index ee987ce20aae..acf9077cffaa 100644
@@ -171,6 +171,12 @@ The Linux-kernel memory model has the following limitations:
 	particular, the "THE PROGRAM ORDER RELATION: po AND po-loc"
 	and "A WARNING" sections).
 
+	Note that this limitation in turn limits LKMM's ability to
+	accurately model address, control, and data dependencies.
+	For example, if the compiler can deduce the value of some variable
+	carrying a dependency, then the compiler can break that dependency
+	by substituting a constant of that value.
+
 2.	Multiple access sizes for a single variable are not supported,
 	and neither are misaligned or partially overlapping accesses.
 

@@ -190,6 +196,36 @@ The Linux-kernel memory model has the following limitations:
 	However, a substantial amount of support is provided for these
 	operations, as shown in the linux-kernel.def file.

tools/memory-model/README +24 -0

+
+	c.	The call_rcu() function is not modeled.  It can be
+		emulated in litmus tests by adding another process that
+		invokes synchronize_rcu() and the body of the callback
+		function, with (for example) a release-acquire from
+		the site of the emulated call_rcu() to the beginning
+		of the additional process.
+
+	d.	The rcu_barrier() function is not modeled.  It can be
+		emulated in litmus tests emulating call_rcu() via
+		(for example) a release-acquire from the end of each
+		additional call_rcu() process to the site of the
+		emulated rcu-barrier().
+
+	e.	Sleepable RCU (SRCU) is not modeled.  It can be
+		emulated, but perhaps not simply.
+
+	f.	Reader-writer locking is not modeled.  It can be
+		emulated in litmus tests using atomic read-modify-write
+		operations.
+
 The "herd7" tool has some additional limitations of its own, apart from
 the memory model:
 

@@ -204,3 +240,6 @@ the memory model:
 Some of these limitations may be overcome in the future, but others are
 more likely to be addressed by incorporating the Linux-kernel memory model
 into other tools.
+
+Finally, please note that LKMM is subject to change as hardware, use cases,
+and compilers evolve.

Signature · 1 line

2.17.1

Quoted 28 lines · Paul E. McKenney

This commit adds more detail about compiler optimizations and not-yet-modeled Linux-kernel APIs.

Signed-off-by Paul E. McKenney <[email protected]>

---
 tools/memory-model/README | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

tools/memory-model/README +6 -0

index ee987ce20aae..acf9077cffaa 100644
@@ -171,6 +171,12 @@ The Linux-kernel memory model has the following limitations:
 	particular, the "THE PROGRAM ORDER RELATION: po AND po-loc"
 	and "A WARNING" sections).
 
+	Note that this limitation in turn limits LKMM's ability to
+	accurately model address, control, and data dependencies.
+	For example, if the compiler can deduce the value of some variable
+	carrying a dependency, then the compiler can break that dependency
+	by substituting a constant of that value.
+
 2.	Multiple access sizes for a single variable are not supported,
 	and neither are misaligned or partially overlapping accesses.
 

@@ -190,6 +196,36 @@ The Linux-kernel memory model has the following limitations:
 	However, a substantial amount of support is provided for these
 	operations, as shown in the linux-kernel.def file.

tools/memory-model/README The Linux-kernel memory model has the following limitations: · line 207

Quoted 10 lines

tools/memory-model/README +9 -0

 
+	a.	When rcu_assign_pointer() is passed NULL, the Linux
+		kernel provides no ordering, but LKMM models this
+		case as a store release.
+
+	b.	The "unless" RMW operations are not currently modeled:
+		atomic_long_add_unless(), atomic_add_unless(),
+		atomic_inc_unless_negative(), and
+		atomic_dec_unless_positive().  These can be emulated
+		in litmus tests, for example, by using atomic_cmpxchg().

There is a prototype atomic_add_unless(): with current herd7,

$ cat atomic_add_unless.litmus
C atomic_add_unless

{}

P0(atomic_t *u, atomic_t *v)

{
	int r0;
	int r1;

	r0 = atomic_add_unless(u, 1, 2);
	r1 = atomic_read(v);
}

P1(atomic_t *u, atomic_t *v)

{
	int r0;
	int r1;

	r0 = atomic_add_unless(v, 1, 2);
	r1 = atomic_read(u);
}

exists (0:r1=0 /\ 1:r1=0)

$ herd7 -conf linux-kernel.cfg atomic_add_unless.litmus
Test atomic_add_unless Allowed
States 3
0:r1=0; 1:r1=1;
0:r1=1; 1:r1=0;
0:r1=1; 1:r1=1;
No
Witnesses
Positive: 0 Negative: 3
Condition exists (0:r1=0 /\ 1:r1=0)
Observation atomic_add_unless Never 0 3
Time atomic_add_unless 0.00
Hash=fa37a2359831690299e4cc394e45d966

The last commit in the herdtools7 repo. related to this implementation (AFAICT) is:

9523c340917b6a ("herd/linux: make atomic_add_unless a primitive, so as to yield more precise dependencies for the returned boolean.")

but I can only vaguely remember those dependencies issues now :/ ...; maybe we can now solve these issues? or should we change herd7 to re- turn a warning? (Notice that this primitive is currently not exported to the linux-kernel.def file.)

Andrea

Quoted 34 lines

tools/memory-model/README +24 -0

+
+	c.	The call_rcu() function is not modeled.  It can be
+		emulated in litmus tests by adding another process that
+		invokes synchronize_rcu() and the body of the callback
+		function, with (for example) a release-acquire from
+		the site of the emulated call_rcu() to the beginning
+		of the additional process.
+
+	d.	The rcu_barrier() function is not modeled.  It can be
+		emulated in litmus tests emulating call_rcu() via
+		(for example) a release-acquire from the end of each
+		additional call_rcu() process to the site of the
+		emulated rcu-barrier().
+
+	e.	Sleepable RCU (SRCU) is not modeled.  It can be
+		emulated, but perhaps not simply.
+
+	f.	Reader-writer locking is not modeled.  It can be
+		emulated in litmus tests using atomic read-modify-write
+		operations.
+
 The "herd7" tool has some additional limitations of its own, apart from
 the memory model:
 

@@ -204,3 +240,6 @@ the memory model:
 Some of these limitations may be overcome in the future, but others are
 more likely to be addressed by incorporating the Linux-kernel memory model
 into other tools.
+
+Finally, please note that LKMM is subject to change as hardware, use cases,
+and compilers evolve.

Signature · 1 line

2.17.1

Quoted 50 lines

tools/memory-model/README The Linux-kernel memory model has the following limitations: · line 207

Quoted 5 lines

tools/memory-model/README +5 -0

+	b.	The "unless" RMW operations are not currently modeled:
+		atomic_long_add_unless(), atomic_add_unless(),
+		atomic_inc_unless_negative(), and
+		atomic_dec_unless_positive().  These can be emulated
+		in litmus tests, for example, by using atomic_cmpxchg().

There is a prototype atomic_add_unless(): with current herd7,

$ cat atomic_add_unless.litmus
C atomic_add_unless

{}

P0(atomic_t *u, atomic_t *v)

{
	int r0;
	int r1;

	r0 = atomic_add_unless(u, 1, 2);
	r1 = atomic_read(v);
}

P1(atomic_t *u, atomic_t *v)

{
	int r0;
	int r1;

	r0 = atomic_add_unless(v, 1, 2);
	r1 = atomic_read(u);
}

exists (0:r1=0 /\ 1:r1=0)

$ herd7 -conf linux-kernel.cfg atomic_add_unless.litmus
Test atomic_add_unless Allowed
States 3
0:r1=0; 1:r1=1;
0:r1=1; 1:r1=0;
0:r1=1; 1:r1=1;
No
Witnesses
Positive: 0 Negative: 3
Condition exists (0:r1=0 /\ 1:r1=0)
Observation atomic_add_unless Never 0 3
Time atomic_add_unless 0.00
Hash=fa37a2359831690299e4cc394e45d966

The last commit in the herdtools7 repo. related to this implementation (AFAICT) is:

Quoted 6 lines

9523c340917b6a ("herd/linux: make atomic_add_unless a primitive, so as to yield more precise dependencies for the returned boolean.")

but I can only vaguely remember those dependencies issues now :/ ...; maybe we can now solve these issues? or should we change herd7 to re- turn a warning? (Notice that this primitive is currently not exported to the linux-kernel.def file.)

Cool! It would be good to add this to the .def file once the underlying herd7 machinery is ready. And then I would update the documentation accordingly. Or happily accept a patch updating the documentation, as the case might be. ;-)

Quoted 57 lines

Quoted 56 lines

tools/memory-model/README The Linux-kernel memory model has the following limitations: · line 207

Quoted 5 lines

tools/memory-model/README +5 -0

+	b.	The "unless" RMW operations are not currently modeled:
+		atomic_long_add_unless(), atomic_add_unless(),
+		atomic_inc_unless_negative(), and
+		atomic_dec_unless_positive().  These can be emulated
+		in litmus tests, for example, by using atomic_cmpxchg().

There is a prototype atomic_add_unless(): with current herd7,

$ cat atomic_add_unless.litmus
C atomic_add_unless

{}

P0(atomic_t *u, atomic_t *v)

{
	int r0;
	int r1;

	r0 = atomic_add_unless(u, 1, 2);
	r1 = atomic_read(v);
}

P1(atomic_t *u, atomic_t *v)

{
	int r0;
	int r1;

	r0 = atomic_add_unless(v, 1, 2);
	r1 = atomic_read(u);
}

exists (0:r1=0 /\ 1:r1=0)

$ herd7 -conf linux-kernel.cfg atomic_add_unless.litmus
Test atomic_add_unless Allowed
States 3
0:r1=0; 1:r1=1;
0:r1=1; 1:r1=0;
0:r1=1; 1:r1=1;
No
Witnesses
Positive: 0 Negative: 3
Condition exists (0:r1=0 /\ 1:r1=0)
Observation atomic_add_unless Never 0 3
Time atomic_add_unless 0.00
Hash=fa37a2359831690299e4cc394e45d966

The last commit in the herdtools7 repo. related to this implementation (AFAICT) is:

9523c340917b6a ("herd/linux: make atomic_add_unless a primitive, so as to yield more precise dependencies for the returned boolean.")

but I can only vaguely remember those dependencies issues now :/ ...; maybe we can now solve these issues? or should we change herd7 to re- turn a warning? (Notice that this primitive is currently not exported to the linux-kernel.def file.)

Quoted 4 lines

Cool! It would be good to add this to the .def file once the underlying herd7 machinery is ready. And then I would update the documentation accordingly. Or happily accept a patch updating the documentation, as the case might be. ;-)

Fair enough, ;-) Please feel free to add:

Reviewed-by Andrea Parri <[email protected]>

This commit adds s390.cat and s390.cfg files to allow users to check litmus tests for s390-specific code. Note that this change only enables herd7 checking of C-language litmus tests. Larger changes are required to enable the litmus7 and klitmus7 tools to check litmus tests on real hardare.

Suggested-by Martin Schwidefsky <[email protected]>

Suggested-by Christian Borntraeger <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

[ paulmck: Add fixes suggested by Alan Stern. ]

---
 tools/memory-model/s390.cat | 18 ++++++++++++++++++
 tools/memory-model/s390.cfg | 21 +++++++++++++++++++++
 2 files changed, 39 insertions(+)
 create mode 100644 tools/memory-model/s390.cat
 create mode 100644 tools/memory-model/s390.cfg

Hi Paul,

Quoted 10 lines · Paul E. McKenney

This commit adds s390.cat and s390.cfg files to allow users to check litmus tests for s390-specific code. Note that this change only enables herd7 checking of C-language litmus tests. Larger changes are required to enable the litmus7 and klitmus7 tools to check litmus tests on real hardare.

Suggested-by Martin Schwidefsky <[email protected]>

Suggested-by Christian Borntraeger <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

[ paulmck: Add fixes suggested by Alan Stern. ]

Quoted 6 lines

---
 tools/memory-model/s390.cat | 18 ++++++++++++++++++
 tools/memory-model/s390.cfg | 21 +++++++++++++++++++++
 2 files changed, 39 insertions(+)
 create mode 100644 tools/memory-model/s390.cat
 create mode 100644 tools/memory-model/s390.cfg

As I said before, I'd *much* prefer this to be part of the upstream herdtools7 repository. It's not really anything to do with the Linux kernel, so I don't think it belongs in the source tree.

Hello!

This series contains memory-model updates, not yet ready for inclusion:

bf36a3124d04 doc: Replace smp_cond_acquire() with smp_cond_load_acquire()

Small change, needs an ack. Looks to me like is is just aligning the documentation with the code, so should not be controversial (famous last words).

Please take a look and consider giving feedback and/or a review/ack.

Quoted 6 lines · Paul E. McKenney

bf36a3124d04 doc: Replace smp_cond_acquire() with smp_cond_load_acquire()

Small change, needs an ack. Looks to me like is is just aligning the documentation with the code, so should not be controversial (famous last words).

Quoted 2 lines

Please take a look and consider giving feedback and/or a review/ack.

What branch is this commit in? It doesn't seem to be in the lkmm branch.

In any case, the change is trivial and obviously correct.

Acked-by Alan Stern <[email protected]>