Skip to contentSkip to conversation

sched: Add smp_rmb() in task rq locking cycles

PATCH Applied Kirill Tkhai 7 participants 46 messages Feb 17, 2015 – Apr 30, 2015 1 message not in the archive

Subsystems (6)
lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): 20150217104516.12144.85911.stgit@tkhai

#1 lore raw

PATCH 2/2 sched: Add smp_rmb() in task rq locking cycles

We migrate a task using TASK_ON_RQ_MIGRATING state of on_rq:

	raw_spin_lock(&old_rq->lock);
	deactivate_task(old_rq, p, 0);
	p->on_rq = TASK_ON_RQ_MIGRATING;
	set_task_cpu(p, new_cpu);
	raw_spin_unlock(&rq->lock);

I.e.:

	write TASK_ON_RQ_MIGRATING
	smp_wmb() (in __set_task_cpu)
	write new_cpu

But {,__}task_rq_lock() don't use smp_rmb(), and they may see the cpu and TASK_ON_RQ_MIGRATING in opposite order. In this case {,__}task_rq_lock() lock new_rq before the task is actually queued on it.

Fix that using ordered reading.

Fixes cca26e8009d1 "sched: Teach scheduler to understand TASK_ON_RQ_MIGRATING state"
---
 kernel/sched/core.c  |    8 ++++++--
 kernel/sched/sched.h |    8 ++++++--
 2 files changed, 12 insertions(+), 4 deletions(-)
kernel/sched/core.c +6 -2
index fc12a1d..a42fb88 100644
@@ -319,8 +319,12 @@ static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags)
 		raw_spin_lock_irqsave(&p->pi_lock, *flags);
 		rq = task_rq(p);
 		raw_spin_lock(&rq->lock);
-		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
-			return rq;
+		if (likely(rq == task_rq(p))) {
+			/* Pairs with smp_wmb() in __set_task_cpu() */
+			smp_rmb();
+			if (likely(!task_on_rq_migrating(p)))
+				return rq;
+		}
 		raw_spin_unlock(&rq->lock);
 		raw_spin_unlock_irqrestore(&p->pi_lock, *flags);
 
kernel/sched/sched.h +6 -2
index f65f57c..4d7b03c 100644
@@ -1031,8 +1031,12 @@ static inline struct rq *__task_rq_lock(struct task_struct *p)
 	for (;;) {
 		rq = task_rq(p);
 		raw_spin_lock(&rq->lock);
-		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
-			return rq;
+		if (likely(rq == task_rq(p))) {
+			/* Pairs with smp_wmb() in __set_task_cpu() */
+			smp_rmb();
+			if (likely(!task_on_rq_migrating(p)))
+				return rq;
+		}
 		raw_spin_unlock(&rq->lock);
 
 		while (unlikely(task_on_rq_migrating(p)))
maintainer
#2 lore raw
Quoted 25 lines · Kirill Tkhai

We migrate a task using TASK_ON_RQ_MIGRATING state of on_rq:

	raw_spin_lock(&old_rq->lock);
	deactivate_task(old_rq, p, 0);
	p->on_rq = TASK_ON_RQ_MIGRATING;
	set_task_cpu(p, new_cpu);
	raw_spin_unlock(&rq->lock);

I.e.:

	write TASK_ON_RQ_MIGRATING
	smp_wmb() (in __set_task_cpu)
	write new_cpu

But {,__}task_rq_lock() don't use smp_rmb(), and they may see the cpu and TASK_ON_RQ_MIGRATING in opposite order. In this case {,__}task_rq_lock() lock new_rq before the task is actually queued on it.

kernel/sched/core.c +0 -0
index fc12a1d..a42fb88 100644

kernel/sched/core.c static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags) · line 323

Quoted 7 lines
kernel/sched/core.c +2 -2
@@ -319,8 +319,12 @@ static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags)
 		raw_spin_lock_irqsave(&p->pi_lock, *flags);
 		rq = task_rq(p);
 		raw_spin_lock(&rq->lock);
-		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
-			return rq;
+		if (likely(rq == task_rq(p))) {
+			/* Pairs with smp_wmb() in __set_task_cpu() */

That comment really is insufficient; but aside from that:

If we observe the old cpu value we've just acquired the old rq->lock and therefore we must observe the new cpu value and retry -- we don't care about the migrate value in this case.

If we observe the new cpu value, we've acquired the new rq->lock and its ACQUIRE will pair with the WMB to ensure we see the migrate value.

So I think the current code is correct; albeit it could use a comment.

kernel/sched/core.c static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags) · line 327

Quoted 4 lines
kernel/sched/core.c +4 -0
+			smp_rmb();
+			if (likely(!task_on_rq_migrating(p)))
+				return rq;
+		}

---
Subject: sched: Clarify ordering between task_rq_lock() and move_queued_task()
From: Peter Zijlstra <[email protected]>
Date: Tue Feb 17 13:07:38 CET 2015

There was a wee bit of confusion around the exact ordering here; clarify things.

---
 kernel/sched/core.c |   16 ++++++++++++++++
 1 file changed, 16 insertions(+)
kernel/sched/core.c +16 -0
@@ -341,6 +341,22 @@ static struct rq *task_rq_lock(struct ta
 		raw_spin_lock_irqsave(&p->pi_lock, *flags);
 		rq = task_rq(p);
 		raw_spin_lock(&rq->lock);
+		/*
+		 *	move_queued_task()		task_rq_lock()
+		 *
+		 *	ACQUIRE (rq->lock)
+		 *	[S] ->on_rq = MIGRATING		[L] rq = task_rq()
+		 *	WMB (__set_task_cpu())		ACQUIRE (rq->lock);
+		 *	[S] ->cpu = new_cpu		[L] task_rq()
+		 *					[L] ->on_rq
+		 *	RELEASE (rq->lock)
+		 *
+		 * If we observe the old cpu in task_rq_lock, the acquire of
+		 * the old rq->lock will fully serialize against the stores.
+		 *
+		 * If we observe the new cpu in task_rq_lock, the acquire will
+		 * pair with the WMB to ensure we must then also see migrating.
+		 */
 		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
 			return rq;
 		raw_spin_unlock(&rq->lock);
#3 lore raw

В Вт, 17/02/2015 в 13:12 +0100, Peter Zijlstra пишет:

Quoted 36 lines · Kirill Tkhai
Quoted 25 lines

We migrate a task using TASK_ON_RQ_MIGRATING state of on_rq:

	raw_spin_lock(&old_rq->lock);
	deactivate_task(old_rq, p, 0);
	p->on_rq = TASK_ON_RQ_MIGRATING;
	set_task_cpu(p, new_cpu);
	raw_spin_unlock(&rq->lock);

I.e.:

	write TASK_ON_RQ_MIGRATING
	smp_wmb() (in __set_task_cpu)
	write new_cpu

But {,__}task_rq_lock() don't use smp_rmb(), and they may see the cpu and TASK_ON_RQ_MIGRATING in opposite order. In this case {,__}task_rq_lock() lock new_rq before the task is actually queued on it.

kernel/sched/core.c +0 -0
index fc12a1d..a42fb88 100644

kernel/sched/core.c static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags) · line 323

Quoted 7 lines
kernel/sched/core.c +2 -2
@@ -319,8 +319,12 @@ static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags)
 		raw_spin_lock_irqsave(&p->pi_lock, *flags);
 		rq = task_rq(p);
 		raw_spin_lock(&rq->lock);
-		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
-			return rq;
+		if (likely(rq == task_rq(p))) {
+			/* Pairs with smp_wmb() in __set_task_cpu() */

That comment really is insufficient; but aside from that:

Quoted 6 lines

If we observe the old cpu value we've just acquired the old rq->lock and therefore we must observe the new cpu value and retry -- we don't care about the migrate value in this case.

If we observe the new cpu value, we've acquired the new rq->lock and its ACQUIRE will pair with the WMB to ensure we see the migrate value.

Yes, I warried about new_cpu case.

So, spin_lock() implies smp_rmb(). I used to think it does not do (I was confused by smp_mb__before_spin_lock(), but it's for STORE).

Thanks for the explanation :)

Quoted 49 lines

So I think the current code is correct; albeit it could use a comment.

kernel/sched/core.c static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags) · line 327

Quoted 4 lines
kernel/sched/core.c +4 -0
+			smp_rmb();
+			if (likely(!task_on_rq_migrating(p)))
+				return rq;
+		}

---
Subject: sched: Clarify ordering between task_rq_lock() and move_queued_task()
From: Peter Zijlstra <[email protected]>
Date: Tue Feb 17 13:07:38 CET 2015

There was a wee bit of confusion around the exact ordering here; clarify things.

---
 kernel/sched/core.c |   16 ++++++++++++++++
 1 file changed, 16 insertions(+)
kernel/sched/core.c +16 -0
@@ -341,6 +341,22 @@ static struct rq *task_rq_lock(struct ta
 		raw_spin_lock_irqsave(&p->pi_lock, *flags);
 		rq = task_rq(p);
 		raw_spin_lock(&rq->lock);
+		/*
+		 *	move_queued_task()		task_rq_lock()
+		 *
+		 *	ACQUIRE (rq->lock)
+		 *	[S] ->on_rq = MIGRATING		[L] rq = task_rq()
+		 *	WMB (__set_task_cpu())		ACQUIRE (rq->lock);
+		 *	[S] ->cpu = new_cpu		[L] task_rq()
+		 *					[L] ->on_rq
+		 *	RELEASE (rq->lock)
+		 *
+		 * If we observe the old cpu in task_rq_lock, the acquire of
+		 * the old rq->lock will fully serialize against the stores.
+		 *
+		 * If we observe the new cpu in task_rq_lock, the acquire will
+		 * pair with the WMB to ensure we must then also see migrating.
+		 */
 		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
 			return rq;
 		raw_spin_unlock(&rq->lock);
maintainer
#4 lore raw
Quoted 9 lines · Kirill Tkhai
Quoted 2 lines

If we observe the new cpu value, we've acquired the new rq->lock and its ACQUIRE will pair with the WMB to ensure we see the migrate value.

Yes, I warried about new_cpu case.

So, spin_lock() implies smp_rmb(). I used to think it does not do (I was confused by smp_mb__before_spin_lock(), but it's for STORE).

Thanks for the explanation :)

No, it does not imply RMB, its an ACQUIRE barrier.

Quoted 1 line

From Documentation/memory-barriers.txt:

(5) ACQUIRE operations.

This acts as a one-way permeable barrier. It guarantees that all memory 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 smp_load_acquire() operations.

Memory operations that occur before an ACQUIRE operation may appear to happen after it completes.

An ACQUIRE operation should almost always be paired with a RELEASE operation.

And note that the [L] rq = task_rq() cannot happen _after_ the acquire because the acquire has an address dependency on it, we must complete the load in order to actually take the lock.

(of course, taking the lock implies further stores and atomic ops, but those need not actually imply more than the ACQUIRE barrier -- even though they will on x86).

maintainer
#5 lore raw
In reply to Peter Zijlstra
Quoted 15 lines · Peter Zijlstra
kernel/sched/core.c +9 -0
@@ -341,6 +341,22 @@ static struct rq *task_rq_lock(struct ta
 		raw_spin_lock_irqsave(&p->pi_lock, *flags);
 		rq = task_rq(p);
 		raw_spin_lock(&rq->lock);
+		/*
+		 *	move_queued_task()		task_rq_lock()
+		 *
+		 *	ACQUIRE (rq->lock)
+		 *	[S] ->on_rq = MIGRATING		[L] rq = task_rq()
+		 *	WMB (__set_task_cpu())		ACQUIRE (rq->lock);
+		 *	[S] ->cpu = new_cpu		[L] task_rq()
+		 *					[L] ->on_rq
+		 *	RELEASE (rq->lock)

kernel/sched/core.c static struct rq *task_rq_lock(struct ta · line 362

Quoted 10 lines
kernel/sched/core.c +7 -0
+		 *
+		 * If we observe the old cpu in task_rq_lock, the acquire of
+		 * the old rq->lock will fully serialize against the stores.
+		 *
+		 * If we observe the new cpu in task_rq_lock, the acquire will
+		 * pair with the WMB to ensure we must then also see migrating.
+		 */
 		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
 			return rq;
 		raw_spin_unlock(&rq->lock);

Hey Paul, remember this: https://lkml.org/lkml/2014/7/16/310

I just used a creative one :-)

BTW, should we attempt to include that table in memory-barriers.txt like Mathieu said? As a cheat sheet with references to longer explanations for the 'interesting' ones?

FWIW, we should probably update that table to include control dependencies too; we didn't (formally) have those back then I think.

The blob under SMP BARRIER PAIRING does not mention pairing with control dependencies; and I'm rather sure I've done so.

#6 lore raw
Quoted 20 lines · Peter Zijlstra
Quoted 19 lines · Peter Zijlstra
kernel/sched/core.c +13 -0
@@ -341,6 +341,22 @@ static struct rq *task_rq_lock(struct ta
 		raw_spin_lock_irqsave(&p->pi_lock, *flags);
 		rq = task_rq(p);
 		raw_spin_lock(&rq->lock);
+		/*
+		 *	move_queued_task()		task_rq_lock()
+		 *
+		 *	ACQUIRE (rq->lock)
+		 *	[S] ->on_rq = MIGRATING		[L] rq = task_rq()
+		 *	WMB (__set_task_cpu())		ACQUIRE (rq->lock);
+		 *	[S] ->cpu = new_cpu		[L] task_rq()
+		 *					[L] ->on_rq
+		 *	RELEASE (rq->lock)
+		 *
+		 * If we observe the old cpu in task_rq_lock, the acquire of
+		 * the old rq->lock will fully serialize against the stores.
+		 *
Quoted 8 lines

kernel/sched/core.c static struct rq *task_rq_lock(struct ta · line 362

Quoted 6 lines
kernel/sched/core.c +3 -0
+		 * If we observe the new cpu in task_rq_lock, the acquire will
+		 * pair with the WMB to ensure we must then also see migrating.
+		 */
 		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
 			return rq;
 		raw_spin_unlock(&rq->lock);

Hey Paul, remember this: https://lkml.org/lkml/2014/7/16/310

I do now. ;-)

Quoted 1 line

I just used a creative one :-)

The scenario above?

Quoted 9 lines

BTW, should we attempt to include that table in memory-barriers.txt like Mathieu said? As a cheat sheet with references to longer explanations for the 'interesting' ones?

FWIW, we should probably update that table to include control dependencies too; we didn't (formally) have those back then I think.

The blob under SMP BARRIER PAIRING does not mention pairing with control dependencies; and I'm rather sure I've done so.

Yep, they should pair as well, though the pairing is limited. No transitivity, of course.

So the straightforward approach requires eighteen bits per cell, though some of them are a bit, ummm, "unusual". Sixteen of these are given by Scenarios 0-15 in http://lwn.net/Articles/573436/, with the barrier on the side corresponding to the first column and the barrier on the top corresponding to the second column. The seventeenth bit says whether you get transitivity chaining after the top access, assuming that it happens later. The eighteenth bit says whether you get transitivity chaining before the side access, assuming that it happens earlier.

The following is a rough first guess, filling in only the diagonal. Some of the entries are no doubt wrong, and getting them right requires something like 7*7*18 test cases, which will take some time. So, is something like this really helpful?

| mb | wmb | rmb | rbd | acq | rel | ctl |
-----+-------+-------+-------+-------+-------+-------+-------+
mb | 3ffff | X | X | X | X | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
wmb | X | 01000 | X | X | X | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
rmb | X | X | 00000 | X | X | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
rbd | X | X | X | 00000 | X | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
acq | X | X | X | X | 00020 | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
rel | X | X | X | X | X | 0cc00 | X +
-----+-------+-------+-------+-------+-------+-------+-------+

  ctl |   X   |   X   |   X   |   X   |   X   |   X   | 00020 +

-----+-------+-------+-------+-------+-------+-------+-------+

Thanx, Paul

#7 lore raw
Quoted 30 lines · Paul E. McKenney
Quoted 20 lines · Peter Zijlstra
Quoted 19 lines · Peter Zijlstra
kernel/sched/core.c +13 -0
@@ -341,6 +341,22 @@ static struct rq *task_rq_lock(struct ta
 		raw_spin_lock_irqsave(&p->pi_lock, *flags);
 		rq = task_rq(p);
 		raw_spin_lock(&rq->lock);
+		/*
+		 *	move_queued_task()		task_rq_lock()
+		 *
+		 *	ACQUIRE (rq->lock)
+		 *	[S] ->on_rq = MIGRATING		[L] rq = task_rq()
+		 *	WMB (__set_task_cpu())		ACQUIRE (rq->lock);
+		 *	[S] ->cpu = new_cpu		[L] task_rq()
+		 *					[L] ->on_rq
+		 *	RELEASE (rq->lock)
+		 *
+		 * If we observe the old cpu in task_rq_lock, the acquire of
+		 * the old rq->lock will fully serialize against the stores.
+		 *
Quoted 8 lines

kernel/sched/core.c static struct rq *task_rq_lock(struct ta · line 362

Quoted 6 lines
kernel/sched/core.c +3 -0
+		 * If we observe the new cpu in task_rq_lock, the acquire will
+		 * pair with the WMB to ensure we must then also see migrating.
+		 */
 		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
 			return rq;
 		raw_spin_unlock(&rq->lock);

Hey Paul, remember this: https://lkml.org/lkml/2014/7/16/310

Quoted 15 lines

I do now. ;-)

Quoted 1 line

I just used a creative one :-)

The scenario above?

Quoted 9 lines

BTW, should we attempt to include that table in memory-barriers.txt like Mathieu said? As a cheat sheet with references to longer explanations for the 'interesting' ones?

FWIW, we should probably update that table to include control dependencies too; we didn't (formally) have those back then I think.

The blob under SMP BARRIER PAIRING does not mention pairing with control dependencies; and I'm rather sure I've done so.

And here is a patch for the control-dependency pairing. Thoughts?

Thanx, Paul

------------------------------------------------------------------------

documentation: Clarify control-dependency pairing

This commit explicitly states that control dependencies pair normally with other barriers, and gives an example of such pairing.

Documentation/memory-barriers.txt +21 -5
index ca2387ef27ab..b09880086d96 100644
@@ -592,9 +592,9 @@ See also the subsection on "Cache Coherency" for a more thorough example.
 CONTROL DEPENDENCIES
 --------------------
 
-A control dependency requires a full read memory barrier, not simply a data
-dependency barrier to make it work correctly.  Consider the following bit of
-code:
+A load-load control dependency requires a full read memory barrier, not
+simply a data dependency barrier to make it work correctly.  Consider the
+following bit of code:
 
 	q = ACCESS_ONCE(a);
 	if (q) {
@@ -615,14 +615,15 @@ case what's actually required is:
 	}
 
 However, stores are not speculated.  This means that ordering -is- provided
-in the following example:
+for load-store control dependencies, as in the following example:
 
 	q = ACCESS_ONCE(a);
 	if (q) {
 		ACCESS_ONCE(b) = p;
 	}
 
-Please note that ACCESS_ONCE() is not optional!  Without the
+Control dependencies pair normally with other types of barriers.
+That said, please note that ACCESS_ONCE() is not optional!  Without the
 ACCESS_ONCE(), might combine the load from 'a' with other loads from
 'a', and the store to 'b' with other stores to 'b', with possible highly
 counterintuitive effects on ordering.
@@ -813,6 +814,8 @@ In summary:
       barrier() can help to preserve your control dependency.  Please
       see the Compiler Barrier section for more information.
 
+  (*) Control dependencies pair normally with other types of barriers.
+
   (*) Control dependencies do -not- provide transitivity.  If you
       need transitivity, use smp_mb().
 
@@ -850,6 +853,19 @@ Or:
 			      <data dependency barrier>
 			      y = *x;
 
+Or even:
+
+	CPU 1		      CPU 2
+	===============	      ===============================
+	r1 = ACCESS_ONCE(y);
+	<write barrier>
+	ACCESS_ONCE(y) = 1;   if (r2 = ACCESS_ONCE(x)) {
+			         <implicit control dependency>
+			         ACCESS_ONCE(y) = 1;
+			      }
+
+	assert(r1 == 0 || r2 == 0);
+
 Basically, the read barrier always has to be there, even though it can be of
 the "weaker" type.
 
maintainer
#8 lore raw
Quoted 4 lines · Paul E. McKenney
Quoted 2 lines
Quoted 2 lines

The blob under SMP BARRIER PAIRING does not mention pairing with control dependencies; and I'm rather sure I've done so.

And here is a patch for the control-dependency pairing. Thoughts?

The proposed patch does not change the blub under SMP BARRIER PAIRING, which would be the first place I would look for this.

Quoted 9 lines
Documentation/memory-barriers.txt +5 -0
@@ -850,6 +853,19 @@ Or:
 			      <data dependency barrier>
 			      y = *x;
 
+Or even:
+
+	CPU 1		      CPU 2
+	===============	      ===============================
+	r1 = ACCESS_ONCE(y);

Documentation/memory-barriers.txt Or: · line 870

Quoted 10 lines
Documentation/memory-barriers.txt +8 -0
+	<write barrier>
+	ACCESS_ONCE(y) = 1;   if (r2 = ACCESS_ONCE(x)) {
+			         <implicit control dependency>
+			         ACCESS_ONCE(y) = 1;
+			      }
+
+	assert(r1 == 0 || r2 == 0);
+
 Basically, the read barrier always has to be there, even though it can be of
 the "weaker" type.

Does that want to be a <general barrier>; CPU1 looks to do a LOAD followed by a STORE, separated by a WMB, which is of course odd.

To me the pairing with a general barrier is also the most intuitive, since the control dependency is a LOAD -> STORE order.

Then again, I'm rather tired and maybe I'm missing the obvious :-)

#9 lore raw
Quoted 8 lines · Peter Zijlstra
Quoted 4 lines · Paul E. McKenney
Quoted 2 lines
Quoted 2 lines

The blob under SMP BARRIER PAIRING does not mention pairing with control dependencies; and I'm rather sure I've done so.

And here is a patch for the control-dependency pairing. Thoughts?

The proposed patch does not change the blub under SMP BARRIER PAIRING, which would be the first place I would look for this.

OK, updated below.

Quoted 23 lines
Quoted 9 lines
(quoted diff) +5 -0
@@ -850,6 +853,19 @@ Or:
 			      <data dependency barrier>
 			      y = *x;
 
+Or even:
+
+	CPU 1		      CPU 2
+	===============	      ===============================
+	r1 = ACCESS_ONCE(y);

Review Or: · line 870

Quoted 10 lines
(quoted diff) +8 -0
+	<write barrier>
+	ACCESS_ONCE(y) = 1;   if (r2 = ACCESS_ONCE(x)) {
+			         <implicit control dependency>
+			         ACCESS_ONCE(y) = 1;
+			      }
+
+	assert(r1 == 0 || r2 == 0);
+
 Basically, the read barrier always has to be there, even though it can be of
 the "weaker" type.

Does that want to be a <general barrier>; CPU1 looks to do a LOAD followed by a STORE, separated by a WMB, which is of course odd.

Quoted 4 lines

To me the pairing with a general barrier is also the most intuitive, since the control dependency is a LOAD -> STORE order.

Then again, I'm rather tired and maybe I'm missing the obvious :-)

Nope, you are correct. There either must be a general barrier or CPU 1's write must be an smp_store_release(). I went with the general barrier. Please see below for an update.

Thanx, Paul

------------------------------------------------------------------------

documentation: Clarify control-dependency pairing

This commit explicitly states that control dependencies pair normally with other barriers, and gives an example of such pairing.

Documentation/memory-barriers.txt +29 -13
index ca2387ef27ab..6974f1c2b4e1 100644
@@ -592,9 +592,9 @@ See also the subsection on "Cache Coherency" for a more thorough example.
 CONTROL DEPENDENCIES
 --------------------
 
-A control dependency requires a full read memory barrier, not simply a data
-dependency barrier to make it work correctly.  Consider the following bit of
-code:
+A load-load control dependency requires a full read memory barrier, not
+simply a data dependency barrier to make it work correctly.  Consider the
+following bit of code:
 
 	q = ACCESS_ONCE(a);
 	if (q) {
@@ -615,14 +615,15 @@ case what's actually required is:
 	}
 
 However, stores are not speculated.  This means that ordering -is- provided
-in the following example:
+for load-store control dependencies, as in the following example:
 
 	q = ACCESS_ONCE(a);
 	if (q) {
 		ACCESS_ONCE(b) = p;
 	}
 
-Please note that ACCESS_ONCE() is not optional!  Without the
+Control dependencies pair normally with other types of barriers.
+That said, please note that ACCESS_ONCE() is not optional!  Without the
 ACCESS_ONCE(), might combine the load from 'a' with other loads from
 'a', and the store to 'b' with other stores to 'b', with possible highly
 counterintuitive effects on ordering.
@@ -813,6 +814,8 @@ In summary:
       barrier() can help to preserve your control dependency.  Please
       see the Compiler Barrier section for more information.
 
+  (*) Control dependencies pair normally with other types of barriers.
+
   (*) Control dependencies do -not- provide transitivity.  If you
       need transitivity, use smp_mb().
 
@@ -823,14 +826,14 @@ SMP BARRIER PAIRING
 When dealing with CPU-CPU interactions, certain types of memory barrier should
 always be paired.  A lack of appropriate pairing is almost certainly an error.
 
-General barriers pair with each other, though they also pair with
-most other types of barriers, albeit without transitivity.  An acquire
-barrier pairs with a release barrier, but both may also pair with other
-barriers, including of course general barriers.  A write barrier pairs
-with a data dependency barrier, an acquire barrier, a release barrier,
-a read barrier, or a general barrier.  Similarly a read barrier or a
-data dependency barrier pairs with a write barrier, an acquire barrier,
-a release barrier, or a general barrier:
+General barriers pair with each other, though they also pair with most
+other types of barriers, albeit without transitivity.  An acquire barrier
+pairs with a release barrier, but both may also pair with other barriers,
+including of course general barriers.  A write barrier pairs with a data
+dependency barrier, a control dependency, an acquire barrier, a release
+barrier, a read barrier, or a general barrier.  Similarly a read barrier,
+control dependency, or a data dependency barrier pairs with a write
+barrier, an acquire barrier, a release barrier, or a general barrier:
 
 	CPU 1		      CPU 2
 	===============	      ===============
@@ -850,6 +853,19 @@ Or:
 			      <data dependency barrier>
 			      y = *x;
 
+Or even:
+
+	CPU 1		      CPU 2
+	===============	      ===============================
+	r1 = ACCESS_ONCE(y);
+	<general barrier>
+	ACCESS_ONCE(y) = 1;   if (r2 = ACCESS_ONCE(x)) {
+			         <implicit control dependency>
+			         ACCESS_ONCE(y) = 1;
+			      }
+
+	assert(r1 == 0 || r2 == 0);
+
 Basically, the read barrier always has to be there, even though it can be of
 the "weaker" type.
 
maintainer
#11 lore raw
In reply to Paul E. McKenney
Quoted 11 lines · Paul E. McKenney
Quoted 5 lines

FWIW, we should probably update that table to include control dependencies too; we didn't (formally) have those back then I think.

The blob under SMP BARRIER PAIRING does not mention pairing with control dependencies; and I'm rather sure I've done so.

Yep, they should pair as well, though the pairing is limited. No transitivity, of course.

So the straightforward approach requires eighteen bits per cell, though some of them are a bit, ummm, "unusual".

Right, I think the idea was to not mark with 'X' when very unusual, otherwise you do indeed obtain the below 'trivial' matrix.

Quoted 28 lines

Sixteen of these are given by
Scenarios 0-15 in http://lwn.net/Articles/573436/, with the barrier on the side corresponding to the first column and the barrier on the top corresponding to the second column. The seventeenth bit says whether you get transitivity chaining after the top access, assuming that it happens later. The eighteenth bit says whether you get transitivity chaining before the side access, assuming that it happens earlier.

The following is a rough first guess, filling in only the diagonal. Some of the entries are no doubt wrong, and getting them right requires something like 7*7*18 test cases, which will take some time. So, is something like this really helpful?

| mb | wmb | rmb | rbd | acq | rel | ctl |
-----+-------+-------+-------+-------+-------+-------+-------+
mb | 3ffff | X | X | X | X | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
wmb | X | 01000 | X | X | X | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
rmb | X | X | 00000 | X | X | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
rbd | X | X | X | 00000 | X | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
acq | X | X | X | X | 00020 | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
rel | X | X | X | X | X | 0cc00 | X +
-----+-------+-------+-------+-------+-------+-------+-------+

Quoted 2 lines
  ctl |   X   |   X   |   X   |   X   |   X   |   X   | 00020 +

-----+-------+-------+-------+-------+-------+-------+-------+

So maybe make two tables; one with 'obvious' pairings, which would include things like mb - {mb,rmb,wmb}; rmb-wmb; acq-rel; ctl-mb; etc.

That table is for people to quickly check 'easy'; like yes wmb-rbd makes sense and rmb-rbd doesn't appear to make sense, I need more reading up.

After that do the 'funny' table, which will explain further possible pairings in more detail, like the rmb-rbd pairing.

I'm not entirely sure we want to do the 7*7*18 state table, that's a lot of work to exhaustively generate. We should be lazy and demand fill when people come to us.

#12 lore raw
Quoted 53 lines · Peter Zijlstra
Quoted 11 lines · Paul E. McKenney
Quoted 5 lines

FWIW, we should probably update that table to include control dependencies too; we didn't (formally) have those back then I think.

The blob under SMP BARRIER PAIRING does not mention pairing with control dependencies; and I'm rather sure I've done so.

Yep, they should pair as well, though the pairing is limited. No transitivity, of course.

So the straightforward approach requires eighteen bits per cell, though some of them are a bit, ummm, "unusual".

Right, I think the idea was to not mark with 'X' when very unusual, otherwise you do indeed obtain the below 'trivial' matrix.

Quoted 28 lines

Sixteen of these are given by
Scenarios 0-15 in http://lwn.net/Articles/573436/, with the barrier on the side corresponding to the first column and the barrier on the top corresponding to the second column. The seventeenth bit says whether you get transitivity chaining after the top access, assuming that it happens later. The eighteenth bit says whether you get transitivity chaining before the side access, assuming that it happens earlier.

The following is a rough first guess, filling in only the diagonal. Some of the entries are no doubt wrong, and getting them right requires something like 7*7*18 test cases, which will take some time. So, is something like this really helpful?

| mb | wmb | rmb | rbd | acq | rel | ctl |
-----+-------+-------+-------+-------+-------+-------+-------+
mb | 3ffff | X | X | X | X | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
wmb | X | 01000 | X | X | X | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
rmb | X | X | 00000 | X | X | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
rbd | X | X | X | 00000 | X | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
acq | X | X | X | X | 00020 | X | X +
-----+-------+-------+-------+-------+-------+-------+-------+
rel | X | X | X | X | X | 0cc00 | X +
-----+-------+-------+-------+-------+-------+-------+-------+

Quoted 2 lines
  ctl |   X   |   X   |   X   |   X   |   X   |   X   | 00020 +

-----+-------+-------+-------+-------+-------+-------+-------+

So maybe make two tables; one with 'obvious' pairings, which would include things like mb - {mb,rmb,wmb}; rmb-wmb; acq-rel; ctl-mb; etc.

That table is for people to quickly check 'easy'; like yes wmb-rbd makes sense and rmb-rbd doesn't appear to make sense, I need more reading up.

Quoted 6 lines

After that do the 'funny' table, which will explain further possible pairings in more detail, like the rmb-rbd pairing.

I'm not entirely sure we want to do the 7*7*18 state table, that's a lot of work to exhaustively generate. We should be lazy and demand fill when people come to us.

I could do a table per communication style. For example, message passing looks like this (give or take likely errors in the table):

	Side CPU	Top CPU
	--------	-------
	X = 1;		r1 = Y;
	<some barrier>	<some barrier>
	Y = 1;		r2 = X;

	assert(r1 == 0 || r2 == 1);


      |   mb  |  wmb  |  rmb  |  rbd  |  acq  |  rel  |  ctl  |

-----+-------+-------+-------+-------+-------+-------+-------+
mb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
wmb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
rmb | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rbd | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
acq | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rel | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
ctl | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+

Here "Y" says that the barrier pair works, "y" says that it can work but requires an artificial dependency, and " " says that it does not work.

Thanx, Paul

maintainer
#13 lore raw
Quoted 29 lines · Paul E. McKenney

I could do a table per communication style. For example, message passing looks like this (give or take likely errors in the table):

	Side CPU	Top CPU
	--------	-------
	X = 1;		r1 = Y;
	<some barrier>	<some barrier>
	Y = 1;		r2 = X;

	assert(r1 == 0 || r2 == 1);


      |   mb  |  wmb  |  rmb  |  rbd  |  acq  |  rel  |  ctl  |

-----+-------+-------+-------+-------+-------+-------+-------+
mb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
wmb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
rmb | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rbd | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
acq | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rel | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
ctl | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+

Quoted 3 lines

Here "Y" says that the barrier pair works, "y" says that it can work but requires an artificial dependency, and " " says that it does not work.

I would maybe do s/artificial/additional/, the pointer deref in RCU is not really artificial, is it?

Also, how many communication styles do you envision to enumerate?

#14 lore raw
Quoted 30 lines · Peter Zijlstra
Quoted 29 lines · Paul E. McKenney

I could do a table per communication style. For example, message passing looks like this (give or take likely errors in the table):

	Side CPU	Top CPU
	--------	-------
	X = 1;		r1 = Y;
	<some barrier>	<some barrier>
	Y = 1;		r2 = X;

	assert(r1 == 0 || r2 == 1);


      |   mb  |  wmb  |  rmb  |  rbd  |  acq  |  rel  |  ctl  |

-----+-------+-------+-------+-------+-------+-------+-------+
mb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
wmb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
rmb | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rbd | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
acq | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rel | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
ctl | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+

Quoted 6 lines
Quoted 3 lines

Here "Y" says that the barrier pair works, "y" says that it can work but requires an artificial dependency, and " " says that it does not work.

I would maybe do s/artificial/additional/, the pointer deref in RCU is not really artificial, is it?

Ah, but RCU is a slightly different pattern because you do have to have a dependency, so you need a different litmus test:

	Initial state: X = 0, Y = &Z, Z = 2

	Side CPU		Top CPU
	--------		-------
	X = 1;			r1 = READ_ONCE(Y);
	<some barrier>		<some_barrier>
	WRITE_ONCE(Y, &X);	r2 = *r1;

	assert(r1 == &Z || r2 == 1);

      |   mb  |  wmb  |  rmb  |  rbd  |  acq  |  rel  |  ctl  |

-----+-------+-------+-------+-------+-------+-------+-------+
mb | Y | | Y | Y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
wmb | Y | | Y | Y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
rmb | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rbd | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
acq | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rel | Y | | Y | Y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
ctl | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+

But of course you should instead use rcu_assign_pointer() and rcu_dereference(). And I should also have used READ_ONCE() and WRITE_ONCE() in my earlier example.

Quoted 1 line

Also, how many communication styles do you envision to enumerate?

As few as possible, but yes, that is likely to be a bit of a problem. To get an idea of how big it could get if not contained somehow, take a look at http://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf.
20 of them on the first page alone! ;-)

We most definitely need to stick to the lowest common denominator if we are taking this approach.

Thanx, Paul

#15 lore raw
In reply to Paul E. McKenney

Thanks Paul and Peter, this was the interesting reading ;)

This is almost off-topic (but see below), but perhaps memory-barriers.txt could also mention spin_unlock_wait() to explain that _most probably_ it is pointless without the memory barrier(s), and the barrer before-or-after unlock_wait() pairs with release-or-acquire.

At the same time, the code like

	spin_unlock_wait();
	STORE;

_can_ be correct because this implies the load-store control dependency.

Quoted 17 lines · Paul E. McKenney

| mb | wmb | rmb | rbd | acq | rel | ctl |
-----+-------+-------+-------+-------+-------+-------+-------+
mb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
wmb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
rmb | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rbd | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
acq | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rel | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
ctl | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+

OK, so "acq" can't pair with "acq", and I am not sure I understand.

First of all, it is not clear to me how you can even try to pair them unless you do something like spin_unlock_wait(). I would like to see an example which is not "obviously wrong".

At the same time, if you play with spin_unlock_wait() or spin_is_locked() then acq can pair with acq?

Let's look at sem_lock(). I never looked at this code before, I can be easily wrong. Manfred will correct me. But at first glance we can write the oversimplified pseudo-code:

	spinlock_t local, global;

	bool my_lock(bool try_local)
	{
		if (try_local) {
			spin_lock(&local);
			if (!spin_is_locked(&global))
				return true;
			spin_unlock(&local);
		}

		spin_lock(&global);
		spin_unlock_wait(&local);
		return false;
	}

	void my_unlock(bool drop_local)
	{
		if (drop_local)
			spin_unlock(&local);
		else
			spin_unlock(&global);
	}

it assumes that the "local" lock is cheaper than "global", the usage is

	bool xxx = my_lock(condition);
	/* CRITICAL SECTION */
	my_unlock(xxx);

Now. Unless I missed something, my_lock() does NOT need a barrier BEFORE spin_unlock_wait() (or spin_is_locked()). Either my_lock(true) should see spin_is_locked(global) == T, or my_lock(false)->spin_unlock_wait() should see that "local" is locked and wait.

Doesn't this mean that acq can pair with acq or I am totally confused?

Another question is do we need a barrier AFTER spin_unlock_wait(). I do not know what ipc/sem.c actually needs, but in general (I think) this does need mb(). Otherwise my_lock / my_unlock itself does not have the proper acq/rel semantics. For example, my_lock(false) can miss the changes which were done under my_lock(true).

So I think that (in theory) sem_wait_array() need smp_mb() at the end. But, given that we have the control dependency, perhaps smp_rmb() is enough?

Oleg.

maintainer
#16 lore raw
Quoted 19 lines · Oleg Nesterov
Quoted 17 lines · Paul E. McKenney

| mb | wmb | rmb | rbd | acq | rel | ctl |
-----+-------+-------+-------+-------+-------+-------+-------+
mb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
wmb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
rmb | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rbd | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
acq | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rel | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
ctl | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+

Quoted 1 line

OK, so "acq" can't pair with "acq", and I am not sure I understand.

Please consider the table in the context of message passing; that is what Paul proposed. Your example from sysvsems, while interesting, would not fit the general scenario of message passing.

This too illustrates a problem with that approach, people can't read, so they'll pick the wrong table to look at.

I really think having just the _one_ table with obvious pairings marked, and everything not marked in the table needs careful reading.

And acq-acq pairing would be a careful one in my book.

#17 lore raw
Quoted 21 lines · Peter Zijlstra
Quoted 19 lines · Oleg Nesterov
Quoted 17 lines · Paul E. McKenney

| mb | wmb | rmb | rbd | acq | rel | ctl |
-----+-------+-------+-------+-------+-------+-------+-------+
mb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
wmb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
rmb | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rbd | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
acq | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rel | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
ctl | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+

Quoted 5 lines
Quoted 1 line

OK, so "acq" can't pair with "acq", and I am not sure I understand.

Please consider the table in the context of message passing; that is what Paul proposed. Your example from sysvsems, while interesting, would not fit the general scenario of message passing.

Ah, yeeees, sorry. Somehow I completely missed that part of Paul's email.

Quoted 2 lines

This too illustrates a problem with that approach, people can't read, so they'll pick the wrong table to look at.

At least we know that I certainly can't ;)

Thanks,

Oleg.

#18 lore raw
Quoted 28 lines · Oleg Nesterov
Quoted 21 lines · Peter Zijlstra
Quoted 19 lines · Oleg Nesterov
Quoted 17 lines · Paul E. McKenney

| mb | wmb | rmb | rbd | acq | rel | ctl |
-----+-------+-------+-------+-------+-------+-------+-------+
mb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
wmb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
rmb | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rbd | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
acq | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rel | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
ctl | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+

Quoted 5 lines
Quoted 1 line

OK, so "acq" can't pair with "acq", and I am not sure I understand.

Please consider the table in the context of message passing; that is what Paul proposed. Your example from sysvsems, while interesting, would not fit the general scenario of message passing.

Quoted 6 lines

Ah, yeeees, sorry. Somehow I completely missed that part of Paul's email.

Quoted 2 lines

This too illustrates a problem with that approach, people can't read, so they'll pick the wrong table to look at.

At least we know that I certainly can't ;)

Nobody can! ;-)

Thanx, Paul

#19 lore raw
In reply to Paul E. McKenney

(Forgot to add Manfred, resending)

Thanks Paul and Peter, this was the interesting reading ;)

This is almost off-topic (but see below), but perhaps memory-barriers.txt could also mention spin_unlock_wait() to explain that _most probably_ it is pointless without the memory barrier(s), and the barrer before-or-after unlock_wait() pairs with release-or-acquire.

At the same time, the code like

	spin_unlock_wait();
	STORE;

_can_ be correct because this implies the load-store control dependency.

Quoted 17 lines · Paul E. McKenney

| mb | wmb | rmb | rbd | acq | rel | ctl |
-----+-------+-------+-------+-------+-------+-------+-------+
mb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
wmb | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
rmb | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rbd | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
acq | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+
rel | Y | | Y | y | Y | | Y +
-----+-------+-------+-------+-------+-------+-------+-------+
ctl | | | | | | | +
-----+-------+-------+-------+-------+-------+-------+-------+

OK, so "acq" can't pair with "acq", and I am not sure I understand.

First of all, it is not clear to me how you can even try to pair them unless you do something like spin_unlock_wait(). I would like to see an example which is not "obviously wrong".

At the same time, if you play with spin_unlock_wait() or spin_is_locked() then acq can pair with acq?

Let's look at sem_lock(). I never looked at this code before, I can be easily wrong. Manfred will correct me. But at first glance we can write the oversimplified pseudo-code:

	spinlock_t local, global;

	bool my_lock(bool try_local)
	{
		if (try_local) {
			spin_lock(&local);
			if (!spin_is_locked(&global))
				return true;
			spin_unlock(&local);
		}

		spin_lock(&global);
		spin_unlock_wait(&local);
		return false;
	}

	void my_unlock(bool drop_local)
	{
		if (drop_local)
			spin_unlock(&local);
		else
			spin_unlock(&global);
	}

it assumes that the "local" lock is cheaper than "global", the usage is

	bool xxx = my_lock(condition);
	/* CRITICAL SECTION */
	my_unlock(xxx);

Now. Unless I missed something, my_lock() does NOT need a barrier BEFORE spin_unlock_wait() (or spin_is_locked()). Either my_lock(true) should see spin_is_locked(global) == T, or my_lock(false)->spin_unlock_wait() should see that "local" is locked and wait.

Doesn't this mean that acq can pair with acq or I am totally confused?

Another question is do we need a barrier AFTER spin_unlock_wait(). I do not know what ipc/sem.c actually needs, but in general (I think) this does need mb(). Otherwise my_lock / my_unlock itself does not have the proper acq/rel semantics. For example, my_lock(false) can miss the changes which were done under my_lock(true).

So I think that (in theory) sem_wait_array() need smp_mb() at the end. But, given that we have the control dependency, perhaps smp_rmb() is enough?

Oleg.

#20 lore raw

Hi Oleg,

Quoted 30 lines · Oleg Nesterov

Let's look at sem_lock(). I never looked at this code before, I can be easily wrong. Manfred will correct me. But at first glance we can write the oversimplified pseudo-code:

	spinlock_t local, global;

	bool my_lock(bool try_local)
	{
		if (try_local) {
			spin_lock(&local);
			if (!spin_is_locked(&global))
				return true;
			spin_unlock(&local);
		}

		spin_lock(&global);
		spin_unlock_wait(&local);
		return false;
	}

	void my_unlock(bool drop_local)
	{
		if (drop_local)
			spin_unlock(&local);
		else
			spin_unlock(&global);
	}

it assumes that the "local" lock is cheaper than "global", the usage is

Quoted 8 lines
	bool xxx = my_lock(condition);
	/* CRITICAL SECTION */
	my_unlock(xxx);

Now. Unless I missed something, my_lock() does NOT need a barrier BEFORE spin_unlock_wait() (or spin_is_locked()). Either my_lock(true) should see spin_is_locked(global) == T, or my_lock(false)->spin_unlock_wait() should see that "local" is locked and wait.

I would agree:
There is no need for a barrier. spin_unlock_read() is just a read, the barriers are from spin_lock() and spin_unlock().

The barrier exist to protect something like a "force_global" flag (complex_count)

Quoted 19 lines

spinlock_t local, global;
bool force_global;
bool my_lock(bool try_local)

{
	if (try_local) {
		spin_lock(&local);
		if (!spin_is_locked(&global)) {
			if (!force_global) {
				return true;
			}
		}
		spin_unlock(&local);


		spin_lock(&global);
		spin_unlock_wait(&local);
		return false;
	}
Quoted 8 lines
	void my_unlock(bool drop_local)
	{
		if (drop_local)
			spin_unlock(&local);
		else
			spin_unlock(&global);
	}
}

force_global can only be set by the owner of &global.

Quoted 5 lines

Another question is do we need a barrier AFTER spin_unlock_wait(). I do not know what ipc/sem.c actually needs, but in general (I think) this does need mb(). Otherwise my_lock / my_unlock itself does not have the proper acq/rel semantics. For example, my_lock(false) can miss the changes which were done under my_lock(true).

How could that happen?
I thought that
thread A:

	protected_var = 1234;
	spin_unlock(&lock_a)

thread B:

	spin_lock(&lock_b)
	if (protected_var)

is safe. i.e, there is no need that acquire and releases is done on the same pointer.

--
Manfred

maintainer
#21 lore raw
Quoted 37 lines · Manfred Spraul
Quoted 28 lines

spinlock_t local, global;
bool force_global;
bool my_lock(bool try_local)

{
	if (try_local) {
		spin_lock(&local);
		if (!spin_is_locked(&global)) {
			if (!force_global) {
				return true;
			}
		}
		spin_unlock(&local);


		spin_lock(&global);
		spin_unlock_wait(&local);
		return false;
	}

	void my_unlock(bool drop_local)
	{
		if (drop_local)
			spin_unlock(&local);
		else
			spin_unlock(&global);
	}
}
Quoted 5 lines

Another question is do we need a barrier AFTER spin_unlock_wait(). I do not know what ipc/sem.c actually needs, but in general (I think) this does need mb(). Otherwise my_lock / my_unlock itself does not have the proper acq/rel semantics. For example, my_lock(false) can miss the changes which were done under my_lock(true).

How could that happen?
I thought that
thread A:

Quoted 8 lines
	protected_var = 1234;
	spin_unlock(&lock_a)

thread B:

	spin_lock(&lock_b)
	if (protected_var)

is safe. i.e, there is no need that acquire and releases is done on the same pointer.

Well, just those four statements can of course be executed like:

	CPU0		CPU1

			spin_lock(&b)
			if (prot_var)

	prot_var = 1;
	spin_unlock(&a);

And you would see the old var. Lock a and b are completely independent here.

Now of course the local/global thing in sysvsem is more complex.

As to what Oleg meant:

X := 0

	CPU0				CPU1

	spin_lock(&global);
					spin_lock(&local);
					X = 1;
					spin_unlock(&local);
	spin_unlock_wait(&local);

	assert(X == 1); /* BOOM */

that assert can trigger, because spin_unlock_wait() are reads, the read of X can be lifted over and above, before the assignment of X on CPU1.

Again, the sysvsem code is slightly more complex, but I think Oleg is right, there is no guarantee you'll observe the full critical section of sem->lock if sem_lock() takes the slow path and does sem_wait_array(), because of the above.

#22 lore raw
Quoted 5 lines · Peter Zijlstra
Quoted 2 lines · Manfred Spraul
Quoted 2 lines

spinlock_t local, global;
bool force_global;

Yes, force_global (sma->complex_count) adds more complications, but I think we can ignoire it in this discussion.

Quoted 73 lines
Quoted 35 lines
Quoted 26 lines

bool my_lock(bool try_local)

{
	if (try_local) {
		spin_lock(&local);
		if (!spin_is_locked(&global)) {
			if (!force_global) {
				return true;
			}
		}
		spin_unlock(&local);


		spin_lock(&global);
		spin_unlock_wait(&local);
		return false;
	}

	void my_unlock(bool drop_local)
	{
		if (drop_local)
			spin_unlock(&local);
		else
			spin_unlock(&global);
	}
}
Quoted 5 lines

Another question is do we need a barrier AFTER spin_unlock_wait(). I do not know what ipc/sem.c actually needs, but in general (I think) this does need mb(). Otherwise my_lock / my_unlock itself does not have the proper acq/rel semantics. For example, my_lock(false) can miss the changes which were done under my_lock(true).

How could that happen?
I thought that
thread A:

Quoted 8 lines
	protected_var = 1234;
	spin_unlock(&lock_a)

thread B:

	spin_lock(&lock_b)
	if (protected_var)

is safe. i.e, there is no need that acquire and releases is done on the same pointer.

Well, just those four statements can of course be executed like:

	CPU0		CPU1

			spin_lock(&b)
			if (prot_var)

	prot_var = 1;
	spin_unlock(&a);

And you would see the old var. Lock a and b are completely independent here.

Now of course the local/global thing in sysvsem is more complex.

As to what Oleg meant:

X := 0

	CPU0				CPU1

	spin_lock(&global);
					spin_lock(&local);
					X = 1;
					spin_unlock(&local);
	spin_unlock_wait(&local);

	assert(X == 1); /* BOOM */
Quoted 7 lines

that assert can trigger, because spin_unlock_wait() are reads, the read of X can be lifted over and above, before the assignment of X on CPU1.

Again, the sysvsem code is slightly more complex, but I think Oleg is right, there is no guarantee you'll observe the full critical section of sem->lock if sem_lock() takes the slow path and does sem_wait_array(), because of the above.

Yes, thanks Peter.

Or another artificial example,

	int X = 0, Y = 0;

	void func(void)
	{
		bool xxx = my_lock(rand());

		BUG_ON(X != Y);

		++X; ++Y;

		my_unlock(xxx);
	}

If func() can race with itself it can hit BUG_ON() above unless my_lock() has the barriers after spin_unlock_wait() and spin_is_locked().

We need the full barrier to serialize STORE's as well, but probably we can rely on control dependancy and thus we only need rmb().

And note that sem_lock() already has rmb() after spin_is_locked() to ensure that we can't miss ->complex_count != 0 which can be changed under sem_perm.lock ("global" lock in the pseudo code above). This is correct, but this equally applies to any other change under "global" lock, we can't miss it only because we have rmb().

Amd the same is true for spin_unlock_wait() in the "slow" path.

Again, again, I do not know, perhaps sem.c is fine. For example, perhaps sem_perm.lock doesn't need to fully serialize with sem_base[sem_num].lock. But this is not obvious, and spin_unlock_wait() without a barrier looks suspicious, at least this needs a comment imo.

Especially because it looks as if sem_base[sem_num].lock can't even fully serialize with itself, sem_lock(nsops => -1) on the 3rd CPU can force one of the lockers to switch to the "global" lock.

Oleg.

#23 lore raw

Hi Oleg,

my example was bad, let's continue with your example.

And: If sem_lock() needs another smp_xmb(), then we must add it:
Some apps do not have a user space hot path, i.e. it seems that on some setups, we have millions of calls per second. If there is a race, then it will happen.

I've tried to merge your example:

Quoted 20 lines

int X = 0, Y = 0;

void func(void)

{
    bool ll = rand();

    if (ll) {
        spin_lock(&local);
        if (!spin_is_locked(&global))
            goto done;
        spin_unlock(&local);
    }
    ll = false;
    spin_lock(&global);
    spin_unlock_wait(&local);
done:
    smp_rmb(); <<<<<<<<<<<<<<<
    BUG_ON(X != Y);
Quoted 7 lines
    ++X; ++Y;

    if (ll)
        spin_unlock(&local);
    else
        spin_unlock(&global);
}

I agree, we need the smp_rmb().
I'll write a patch.

Quoted 2 lines

We need the full barrier to serialize STORE's as well, but probably we can rely on control dependancy and thus we only need rmb().

Do we need a full barrier or not?

I don't manage to create a proper line of reasoning. --
Manfred

maintainer
#24 lore raw
Quoted 5 lines · Manfred Spraul
Quoted 2 lines

We need the full barrier to serialize STORE's as well, but probably we can rely on control dependancy and thus we only need rmb().

Do we need a full barrier or not?

I don't manage to create a proper line of reasoning.

I think I agree with Oleg in that we only need the smp_rmb(); of course that wants a somewhat elaborate comment to go along with it. How about something like so:

spin_unlock_wait(&local);
/*
* The above spin_unlock_wait() forms a control dependency with
* any following stores; because we must first observe the lock
* unlocked and we cannot speculate stores.
*
* Subsequent loads however can easily pass through the loads
* represented by spin_unlock_wait() and therefore we need the
* read barrier.
*
* This together is stronger than ACQUIRE for @local and
* therefore we will observe the complete prior critical section
* of @local.
*/
smp_rmb();

The obvious alternative is using spin_unlock_wait() with an smp_load_acquire(), but that might be more expensive on some archs due to repeated issuing of memory barriers.

#25 lore raw
Quoted 21 lines · Peter Zijlstra

I think I agree with Oleg in that we only need the smp_rmb(); of course that wants a somewhat elaborate comment to go along with it. How about something like so:

spin_unlock_wait(&local);
/*
* The above spin_unlock_wait() forms a control dependency with
* any following stores; because we must first observe the lock
* unlocked and we cannot speculate stores.
*
* Subsequent loads however can easily pass through the loads
* represented by spin_unlock_wait() and therefore we need the
* read barrier.
*
* This together is stronger than ACQUIRE for @local and
* therefore we will observe the complete prior critical section
* of @local.
*/
smp_rmb();

Quoted 3 lines

The obvious alternative is using spin_unlock_wait() with an smp_load_acquire(), but that might be more expensive on some archs due to repeated issuing of memory barriers.

Yes, yes, thanks!

But note that we need the same comment after sem_lock()->spin_is_locked().

So perhaps we can add this comment into include/linux/spinlock.h ? In this case perhaps it makes sense to add, say,

	#define smp_mb__after_unlock_wait()	smp_rmb()

with this comment above? Another potential user task_work_run(). It could use rmb() too, but this again needs the same fat comment.

Ehat do you think?

Oleg.

maintainer
#26 lore raw
Quoted 33 lines · Oleg Nesterov
Quoted 21 lines · Peter Zijlstra

I think I agree with Oleg in that we only need the smp_rmb(); of course that wants a somewhat elaborate comment to go along with it. How about something like so:

spin_unlock_wait(&local);
/*
* The above spin_unlock_wait() forms a control dependency with
* any following stores; because we must first observe the lock
* unlocked and we cannot speculate stores.
*
* Subsequent loads however can easily pass through the loads
* represented by spin_unlock_wait() and therefore we need the
* read barrier.
*
* This together is stronger than ACQUIRE for @local and
* therefore we will observe the complete prior critical section
* of @local.
*/
smp_rmb();

Quoted 3 lines

The obvious alternative is using spin_unlock_wait() with an smp_load_acquire(), but that might be more expensive on some archs due to repeated issuing of memory barriers.

Yes, yes, thanks!

But note that we need the same comment after sem_lock()->spin_is_locked().

So perhaps we can add this comment into include/linux/spinlock.h ? In this case perhaps it makes sense to add, say,

Quoted 6 lines
	#define smp_mb__after_unlock_wait()	smp_rmb()

with this comment above? Another potential user task_work_run(). It could use rmb() too, but this again needs the same fat comment.

Ehat do you think?

Sure, that works.

#27 lore raw
In reply to Peter Zijlstra
Quoted 28 lines · Peter Zijlstra
Quoted 5 lines · Manfred Spraul
Quoted 2 lines

We need the full barrier to serialize STORE's as well, but probably we can rely on control dependancy and thus we only need rmb().

Do we need a full barrier or not?

I don't manage to create a proper line of reasoning.

I think I agree with Oleg in that we only need the smp_rmb(); of course that wants a somewhat elaborate comment to go along with it. How about something like so:

spin_unlock_wait(&local);
/*
* The above spin_unlock_wait() forms a control dependency with
* any following stores; because we must first observe the lock
* unlocked and we cannot speculate stores.
*
* Subsequent loads however can easily pass through the loads
* represented by spin_unlock_wait() and therefore we need the
* read barrier.
*
* This together is stronger than ACQUIRE for @local and
* therefore we will observe the complete prior critical section
* of @local.
*/
smp_rmb();

Quoted 3 lines

The obvious alternative is using spin_unlock_wait() with an smp_load_acquire(), but that might be more expensive on some archs due to repeated issuing of memory barriers.

Please accept my apologies for the late reply. And thank you to Peter for prodding me (again!) to think more carefully about this. Because we have a bit of a comedy of errors at the moment. I will start with mine, namely that we need to support DEC Alpha, which means we cannot use ACCESS_ONCE() or READ_ONCE() to head a control-dependency chain. Alpha needs an mb instruction for control dependencies, just as it does for data dependencies.

I have the following (untested, probably does not even build) patch queued to introduce READ_ONCE_CTRL() to head control depedencies, making them safe for DEC Alpha. And, just as important, also making them more self-documenting.

But the fun doesn't end there! Some architectures have "interesting" implementations of spin_unlock_wait() and arch_spin_is_locked(). I will deal with these in a follow-up email.

In the meantime, thoughts on the patch below?

Thanx, Paul

------------------------------------------------------------------------

smp: Make control dependencies work on Alpha, improve documentation

The current formulation of control dependencies fails on DEC Alpha, which does not respect dependencies of any kind unless an explicit memory is provided. This means that the current fomulation of control dependencies fails on Alpha. This commit therefore creates a READ_ONCE_CTRL() that has the same overhead on non-Alpha systems, but causes Alpha to produce the needed ordering. This commit also applies READ_ONCE_CTRL() to the one known use of control dependencies.

Use of READ_ONCE_CTRL() also has the beneficial effect of adding a bit of self-documentation to control dependencies.

Documentation/memory-barriers.txt +33 -22
index 52c320e3f107..16897552dc1c 100644
@@ -617,16 +617,16 @@ case what's actually required is:
 However, stores are not speculated.  This means that ordering -is- provided
 for load-store control dependencies, as in the following example:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	if (q) {
 		ACCESS_ONCE(b) = p;
 	}
 
-Control dependencies pair normally with other types of barriers.
-That said, please note that ACCESS_ONCE() is not optional!  Without the
-ACCESS_ONCE(), might combine the load from 'a' with other loads from
-'a', and the store to 'b' with other stores to 'b', with possible highly
-counterintuitive effects on ordering.
+Control dependencies pair normally with other types of barriers.  That
+said, please note that READ_ONCE_CTRL() is not optional!  Without the
+READ_ONCE_CTRL(), the compiler might combine the load from 'a' with
+other loads from 'a', and the store to 'b' with other stores to 'b',
+with possible highly counterintuitive effects on ordering.
 
 Worse yet, if the compiler is able to prove (say) that the value of
 variable 'a' is always non-zero, it would be well within its rights
@@ -636,12 +636,15 @@ as follows:
 	q = a;
 	b = p;  /* BUG: Compiler and CPU can both reorder!!! */
 
-So don't leave out the ACCESS_ONCE().
+Finally, the READ_ONCE_CTRL() includes an smp_read_barrier_depends()
+that DEC Alpha needs in order to respect control depedencies.
+
+So don't leave out the READ_ONCE_CTRL().
 
 It is tempting to try to enforce ordering on identical stores on both
 branches of the "if" statement as follows:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	if (q) {
 		barrier();
 		ACCESS_ONCE(b) = p;
@@ -655,7 +658,7 @@ branches of the "if" statement as follows:
 Unfortunately, current compilers will transform this as follows at high
 optimization levels:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	barrier();
 	ACCESS_ONCE(b) = p;  /* BUG: No ordering vs. load from a!!! */
 	if (q) {
@@ -685,7 +688,7 @@ memory barriers, for example, smp_store_release():
 In contrast, without explicit memory barriers, two-legged-if control
 ordering is guaranteed only when the stores differ, for example:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	if (q) {
 		ACCESS_ONCE(b) = p;
 		do_something();
@@ -694,14 +697,14 @@ ordering is guaranteed only when the stores differ, for example:
 		do_something_else();
 	}
 
-The initial ACCESS_ONCE() is still required to prevent the compiler from
-proving the value of 'a'.
+The initial READ_ONCE_CTRL() is still required to prevent the compiler
+from proving the value of 'a'.
 
 In addition, you need to be careful what you do with the local variable 'q',
 otherwise the compiler might be able to guess the value and again remove
 the needed conditional.  For example:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	if (q % MAX) {
 		ACCESS_ONCE(b) = p;
 		do_something();
@@ -714,7 +717,7 @@ If MAX is defined to be 1, then the compiler knows that (q % MAX) is
 equal to zero, in which case the compiler is within its rights to
 transform the above code into the following:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	ACCESS_ONCE(b) = p;
 	do_something_else();
 
@@ -725,7 +728,7 @@ is gone, and the barrier won't bring it back.  Therefore, if you are
 relying on this ordering, you should make sure that MAX is greater than
 one, perhaps as follows:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	BUILD_BUG_ON(MAX <= 1); /* Order load from a with store to b. */
 	if (q % MAX) {
 		ACCESS_ONCE(b) = p;
@@ -742,14 +745,15 @@ of the 'if' statement.
 You must also be careful not to rely too much on boolean short-circuit
 evaluation.  Consider this example:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	if (a || 1 > 0)
 		ACCESS_ONCE(b) = 1;
 
-Because the second condition is always true, the compiler can transform
-this example as following, defeating control dependency:
+Because the first condition cannot fault and the second condition is
+always true, the compiler can transform this example as following,
+defeating control dependency:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	ACCESS_ONCE(b) = 1;
 
 This example underscores the need to ensure that the compiler cannot
@@ -762,8 +766,8 @@ demonstrated by two related examples, with the initial values of
 x and y both being zero:
 
 	CPU 0                     CPU 1
-	=====================     =====================
-	r1 = ACCESS_ONCE(x);      r2 = ACCESS_ONCE(y);
+	=======================   =======================
+	r1 = READ_ONCE_CTRL(x);   r2 = READ_ONCE_CTRL(y);
 	if (r1 > 0)               if (r2 > 0)
 	  ACCESS_ONCE(y) = 1;       ACCESS_ONCE(x) = 1;
 
@@ -783,7 +787,8 @@ But because control dependencies do -not- provide transitivity, the above
 assertion can fail after the combined three-CPU example completes.  If you
 need the three-CPU example to provide ordering, you will need smp_mb()
 between the loads and stores in the CPU 0 and CPU 1 code fragments,
-that is, just before or just after the "if" statements.
+that is, just before or just after the "if" statements.  Furthermore,
+the original two-CPU example is very fragile and should be avoided.
 
 These two examples are the LB and WWC litmus tests from this paper:
 http://www.cl.cam.ac.uk/users/pes20/ppc-supplemental/test6.pdf and this
@@ -791,6 +796,12 @@ site: https://www.cl.cam.ac.uk/~pes20/ppcmem/index.html.
 
 In summary:
 
+  (*) Control dependencies must be headed by READ_ONCE_CTRL().
+      Or, as a much less preferable alternative, interpose
+      be headed by READ_ONCE() or an ACCESS_ONCE() read and must
+      have smp_read_barrier_depends() between this read and the
+      control-dependent write.
+
   (*) Control dependencies can order prior loads against later stores.
       However, they do -not- guarantee any other sort of ordering:
       Not prior loads against later loads, nor prior stores against
include/linux/compiler.h +16 -0
index 1b45e4a0519b..a57eacde2b84 100644
@@ -264,6 +264,22 @@ static __always_inline void __write_once_size(volatile void *p, void *res, int s
 #define WRITE_ONCE(x, val) \
 	({ typeof(x) __val = (val); __write_once_size(&(x), &__val, sizeof(__val)); __val; })
 
+/**
+ * READ_ONCE_CTRL - Read a value heading a control dependency
+ * @x: The value to be read, heading the control dependency
+ *
+ * Control dependencies are tricky.  See Documentation/memory-barriers.txt
+ * for important information on how to use them.  Note that in many cases,
+ * use of smp_load_acquire() will be much simpler.  Control dependencies
+ * should be avoided except on the hottest of hotpaths.
+ */
+#define READ_ONCE_CTRL(x) \
+({ \
+	typeof(x) __val = READ_ONCE(x); \
+	smp_read_barrier_depends(); /* Enforce control dependency. */ \
+	__val; \
+})
+
 #endif /* __KERNEL__ */
 
 #endif /* __ASSEMBLY__ */
kernel/events/ring_buffer.c +1 -1
index eadb95ce7aac..67548d5de4cb 100644
@@ -141,7 +141,7 @@ int perf_output_begin(struct perf_output_handle *handle,
 	perf_output_get_handle(handle);
 
 	do {
-		tail = ACCESS_ONCE(rb->user_page->data_tail);
+		tail = READ_ONCE_CTRL(rb->user_page->data_tail);
 		offset = head = local_read(&rb->head);
 		if (!rb->overwrite &&
 		    unlikely(CIRC_SPACE(head, tail, perf_data_size(rb)) < size))
#28 lore raw
Quoted 7 lines · Paul E. McKenney
Quoted 6 lines · Peter Zijlstra
Quoted 4 lines · Manfred Spraul
Quoted 2 lines

We need the full barrier to serialize STORE's as well, but probably we can rely on control dependancy and thus we only need rmb().

Do we need a full barrier or not?

Quoted 7 lines
Quoted 7 lines
Quoted 1 line

I don't manage to create a proper line of reasoning.

I think I agree with Oleg in that we only need the smp_rmb(); of course that wants a somewhat elaborate comment to go along with it. How about something like so:

	spin_unlock_wait(&local);

And then an smp_read_barrier_depends() would be needed either here or embedded in apin_unlock_wait(). But we also need to check the spin_unlock_wait() implementations to see if any are potentially vulnerable to compiler misbehavior due to lack of ACCESS_ONCE(), READ_ONCE(), or other sources of the required volatility:

o alpha lacks ACCESS_ONCE() or READ_ONCE(), though admittedly the
potential for damage is at least somewhat limited by the fact that smp_read_barrier_depends() is a full memory barrier on Alpha.

o arc: lacks ACCESS_ONCE() or READ_ONCE(), but field is volatile,

	so OK..

o arm: looks good, the READ_ONCE() in arch_spin_is_locked()
should do it.

o arm64: ditto.

o blackfin: Drops into assembly, which should keep the compiler
suitably constrained.

o cris: lacks ACCESS_ONCE() or READ_ONCE(). Not sure where SMP
cris is getting its arch_spinlock_t from, though. Except for UP, which gets volatile fields.

o hexagon: lacks ACCESS_ONCE() or READ_ONCE(), but field is volatile,
so OK.

o ia64: Uses ACCESS_ONCE(), so OK.

o m32r: Volatile cast, so OK. READ_ONCE() might be nicer.

o metag: Drops into assembly, so OK.

o metag #2: volatile declaration on field, so OK.

o mips: ACCESS_ONCE(), so OK.

o mn10300: Volatile cast, so OK. READ_ONCE() might be nicer.

o parisc: Obscure but very real volatile cast, so OK.
Or, in another branch of #ifdef, volatile field, so also OK.

o powerpc: Volatile field, so OK.

o s390: ACCESS_ONCE(), so OK.

o sh: Volatile field, so OK.

o sparc: Volatile cast, so OK. READ_ONCE() might be nicer.
Or, in another path, volatile field, so also OK.

o tile: For 32-bit, looks like a bug. Compares ->current_ticket and
->next_ticket with no obvious protection. The compiler is free to load them in either order, so it is possible that the two fields could compare equal despite never having actually been equal at any given time. Needs something like arm, arm64, mips, or x86 to do single fetch, then compare fields in quantity fetched.

Except that this appears to be using int on a 32-bit system, thus might not have a 64-bit load. If that is the case, the trick would be to load them in order. Except that this can be defeated by overflow. Are there really 32-bit tile systems with enough CPUs to overflow an unsigned short?

For 64-bit, a READ_ONCE() appears to be in order -- no obvious volatility present.

o x86: Uses READ_ONCE(), so OK.

o xtensa: Uses volatile field, so OK.

o UP: Uses volatile fields, so OK.

So tile needs help in addition to the need for smp_read_barrier_depeneds().

One could argue that only Alpha really needs smp_read_barrier_depends(), so the others can avoid it. No opinion myself, at least not at the moment.

Thanx, Paul

Quoted 250 lines
Quoted 15 lines

/*
* The above spin_unlock_wait() forms a control dependency with
* any following stores; because we must first observe the lock
* unlocked and we cannot speculate stores.
*
* Subsequent loads however can easily pass through the loads
* represented by spin_unlock_wait() and therefore we need the
* read barrier.
*
* This together is stronger than ACQUIRE for @local and
* therefore we will observe the complete prior critical section
* of @local.
*/
smp_rmb();

Quoted 3 lines

The obvious alternative is using spin_unlock_wait() with an smp_load_acquire(), but that might be more expensive on some archs due to repeated issuing of memory barriers.

Please accept my apologies for the late reply. And thank you to Peter for prodding me (again!) to think more carefully about this. Because we have a bit of a comedy of errors at the moment. I will start with mine, namely that we need to support DEC Alpha, which means we cannot use ACCESS_ONCE() or READ_ONCE() to head a control-dependency chain. Alpha needs an mb instruction for control dependencies, just as it does for data dependencies.

I have the following (untested, probably does not even build) patch queued to introduce READ_ONCE_CTRL() to head control depedencies, making them safe for DEC Alpha. And, just as important, also making them more self-documenting.

But the fun doesn't end there! Some architectures have "interesting" implementations of spin_unlock_wait() and arch_spin_is_locked(). I will deal with these in a follow-up email.

In the meantime, thoughts on the patch below?

Thanx, Paul

------------------------------------------------------------------------

smp: Make control dependencies work on Alpha, improve documentation

The current formulation of control dependencies fails on DEC Alpha, which does not respect dependencies of any kind unless an explicit memory is provided. This means that the current fomulation of control dependencies fails on Alpha. This commit therefore creates a READ_ONCE_CTRL() that has the same overhead on non-Alpha systems, but causes Alpha to produce the needed ordering. This commit also applies READ_ONCE_CTRL() to the one known use of control dependencies.

Use of READ_ONCE_CTRL() also has the beneficial effect of adding a bit of self-documentation to control dependencies.

Documentation/memory-barriers.txt +33 -22
index 52c320e3f107..16897552dc1c 100644
@@ -617,16 +617,16 @@ case what's actually required is:
 However, stores are not speculated.  This means that ordering -is- provided
 for load-store control dependencies, as in the following example:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	if (q) {
 		ACCESS_ONCE(b) = p;
 	}
 
-Control dependencies pair normally with other types of barriers.
-That said, please note that ACCESS_ONCE() is not optional!  Without the
-ACCESS_ONCE(), might combine the load from 'a' with other loads from
-'a', and the store to 'b' with other stores to 'b', with possible highly
-counterintuitive effects on ordering.
+Control dependencies pair normally with other types of barriers.  That
+said, please note that READ_ONCE_CTRL() is not optional!  Without the
+READ_ONCE_CTRL(), the compiler might combine the load from 'a' with
+other loads from 'a', and the store to 'b' with other stores to 'b',
+with possible highly counterintuitive effects on ordering.
 
 Worse yet, if the compiler is able to prove (say) that the value of
 variable 'a' is always non-zero, it would be well within its rights
@@ -636,12 +636,15 @@ as follows:
 	q = a;
 	b = p;  /* BUG: Compiler and CPU can both reorder!!! */
 
-So don't leave out the ACCESS_ONCE().
+Finally, the READ_ONCE_CTRL() includes an smp_read_barrier_depends()
+that DEC Alpha needs in order to respect control depedencies.
+
+So don't leave out the READ_ONCE_CTRL().
 
 It is tempting to try to enforce ordering on identical stores on both
 branches of the "if" statement as follows:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	if (q) {
 		barrier();
 		ACCESS_ONCE(b) = p;
@@ -655,7 +658,7 @@ branches of the "if" statement as follows:
 Unfortunately, current compilers will transform this as follows at high
 optimization levels:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	barrier();
 	ACCESS_ONCE(b) = p;  /* BUG: No ordering vs. load from a!!! */
 	if (q) {
@@ -685,7 +688,7 @@ memory barriers, for example, smp_store_release():
 In contrast, without explicit memory barriers, two-legged-if control
 ordering is guaranteed only when the stores differ, for example:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	if (q) {
 		ACCESS_ONCE(b) = p;
 		do_something();
@@ -694,14 +697,14 @@ ordering is guaranteed only when the stores differ, for example:
 		do_something_else();
 	}
 
-The initial ACCESS_ONCE() is still required to prevent the compiler from
-proving the value of 'a'.
+The initial READ_ONCE_CTRL() is still required to prevent the compiler
+from proving the value of 'a'.
 
 In addition, you need to be careful what you do with the local variable 'q',
 otherwise the compiler might be able to guess the value and again remove
 the needed conditional.  For example:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	if (q % MAX) {
 		ACCESS_ONCE(b) = p;
 		do_something();
@@ -714,7 +717,7 @@ If MAX is defined to be 1, then the compiler knows that (q % MAX) is
 equal to zero, in which case the compiler is within its rights to
 transform the above code into the following:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	ACCESS_ONCE(b) = p;
 	do_something_else();
 
@@ -725,7 +728,7 @@ is gone, and the barrier won't bring it back.  Therefore, if you are
 relying on this ordering, you should make sure that MAX is greater than
 one, perhaps as follows:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	BUILD_BUG_ON(MAX <= 1); /* Order load from a with store to b. */
 	if (q % MAX) {
 		ACCESS_ONCE(b) = p;
@@ -742,14 +745,15 @@ of the 'if' statement.
 You must also be careful not to rely too much on boolean short-circuit
 evaluation.  Consider this example:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	if (a || 1 > 0)
 		ACCESS_ONCE(b) = 1;
 
-Because the second condition is always true, the compiler can transform
-this example as following, defeating control dependency:
+Because the first condition cannot fault and the second condition is
+always true, the compiler can transform this example as following,
+defeating control dependency:
 
-	q = ACCESS_ONCE(a);
+	q = READ_ONCE_CTRL(a);
 	ACCESS_ONCE(b) = 1;
 
 This example underscores the need to ensure that the compiler cannot
@@ -762,8 +766,8 @@ demonstrated by two related examples, with the initial values of
 x and y both being zero:
 
 	CPU 0                     CPU 1
-	=====================     =====================
-	r1 = ACCESS_ONCE(x);      r2 = ACCESS_ONCE(y);
+	=======================   =======================
+	r1 = READ_ONCE_CTRL(x);   r2 = READ_ONCE_CTRL(y);
 	if (r1 > 0)               if (r2 > 0)
 	  ACCESS_ONCE(y) = 1;       ACCESS_ONCE(x) = 1;
 
@@ -783,7 +787,8 @@ But because control dependencies do -not- provide transitivity, the above
 assertion can fail after the combined three-CPU example completes.  If you
 need the three-CPU example to provide ordering, you will need smp_mb()
 between the loads and stores in the CPU 0 and CPU 1 code fragments,
-that is, just before or just after the "if" statements.
+that is, just before or just after the "if" statements.  Furthermore,
+the original two-CPU example is very fragile and should be avoided.
 
 These two examples are the LB and WWC litmus tests from this paper:
 http://www.cl.cam.ac.uk/users/pes20/ppc-supplemental/test6.pdf and this
@@ -791,6 +796,12 @@ site: https://www.cl.cam.ac.uk/~pes20/ppcmem/index.html.
 
 In summary:
 
+  (*) Control dependencies must be headed by READ_ONCE_CTRL().
+      Or, as a much less preferable alternative, interpose
+      be headed by READ_ONCE() or an ACCESS_ONCE() read and must
+      have smp_read_barrier_depends() between this read and the
+      control-dependent write.
+
   (*) Control dependencies can order prior loads against later stores.
       However, they do -not- guarantee any other sort of ordering:
       Not prior loads against later loads, nor prior stores against
include/linux/compiler.h +16 -0
index 1b45e4a0519b..a57eacde2b84 100644
@@ -264,6 +264,22 @@ static __always_inline void __write_once_size(volatile void *p, void *res, int s
 #define WRITE_ONCE(x, val) \
 	({ typeof(x) __val = (val); __write_once_size(&(x), &__val, sizeof(__val)); __val; })
 
+/**
+ * READ_ONCE_CTRL - Read a value heading a control dependency
+ * @x: The value to be read, heading the control dependency
+ *
+ * Control dependencies are tricky.  See Documentation/memory-barriers.txt
+ * for important information on how to use them.  Note that in many cases,
+ * use of smp_load_acquire() will be much simpler.  Control dependencies
+ * should be avoided except on the hottest of hotpaths.
+ */
+#define READ_ONCE_CTRL(x) \
+({ \
+	typeof(x) __val = READ_ONCE(x); \
+	smp_read_barrier_depends(); /* Enforce control dependency. */ \
+	__val; \
+})
+
 #endif /* __KERNEL__ */
 
 #endif /* __ASSEMBLY__ */
kernel/events/ring_buffer.c +1 -1
index eadb95ce7aac..67548d5de4cb 100644
@@ -141,7 +141,7 @@ int perf_output_begin(struct perf_output_handle *handle,
 	perf_output_get_handle(handle);
 
 	do {
-		tail = ACCESS_ONCE(rb->user_page->data_tail);
+		tail = READ_ONCE_CTRL(rb->user_page->data_tail);
 		offset = head = local_read(&rb->head);
 		if (!rb->overwrite &&
 		    unlikely(CIRC_SPACE(head, tail, perf_data_size(rb)) < size))
maintainer
#29 lore raw
Quoted 14 lines · Paul E. McKenney

And then an smp_read_barrier_depends() would be needed either here or embedded in apin_unlock_wait(). But we also need to check the spin_unlock_wait() implementations to see if any are potentially vulnerable to compiler misbehavior due to lack of ACCESS_ONCE(), READ_ONCE(), or other sources of the required volatility:

o tile: For 32-bit, looks like a bug. Compares ->current_ticket and
->next_ticket with no obvious protection. The compiler is free to load them in either order, so it is possible that the two fields could compare equal despite never having actually been equal at any given time. Needs something like arm, arm64, mips, or x86 to do single fetch, then compare fields in quantity fetched.

Quoted 9 lines

Except that this appears to be using int on a 32-bit system, thus might not have a 64-bit load. If that is the case, the trick would be to load them in order. Except that this can be defeated by overflow. Are there really 32-bit tile systems with enough CPUs to overflow an unsigned short?

For 64-bit, a READ_ONCE() appears to be in order -- no obvious volatility present.

Chris?

#30 lore raw
Quoted 15 lines · Peter Zijlstra
Quoted 13 lines · Paul E. McKenney

And then an smp_read_barrier_depends() would be needed either here or embedded in apin_unlock_wait(). But we also need to check the spin_unlock_wait() implementations to see if any are potentially vulnerable to compiler misbehavior due to lack of ACCESS_ONCE(), READ_ONCE(), or other sources of the required volatility:

o tile: For 32-bit, looks like a bug. Compares ->current_ticket and
->next_ticket with no obvious protection. The compiler is free to load them in either order, so it is possible that the two fields could compare equal despite never having actually been equal at any given time. Needs something like arm, arm64, mips, or x86 to do single fetch, then compare fields in quantity fetched.

Quoted 5 lines
Quoted 5 lines

Except that this appears to be using int on a 32-bit system, thus might not have a 64-bit load. If that is the case, the trick would be to load them in order. Except that this can be defeated by overflow. Are there really 32-bit tile systems with enough CPUs to overflow an unsigned short?

As you surmise, tilepro doesn't have 64-bit loads. So we are stuck with 32-bit loads on these two fields. It's true that spin_unlock_wait() can therefore falsely claim that the lock is unlocked, but it should be only a hint anyway, since by the time the caller tries to act on that information the lock may have been retaken anyway, right? If spin_unlock_wait() is really trying to guarantee that the lock was available at some point in the interval between when it was called and when it returned, we could use READ_ONCE() to read the current ticket value first; is that a necessary part of the semantics?

(Even with READ_ONCE we'd still be exposed to a technical risk that others cores had taken and released the lock 2 billion times in between the two loads of the core running spin_unlock_wait, without ever having the lock actually be free, so technically the only solution is for that core to actually acquire and release the lock, but that seems a bit extreme in practice.)

The reason we use two 32-bit fields on tilepro is that the only available atomic instruction is tns (test and set), which sets a 32-bit "1" value into the target memory and returns the old 32-bit value. So we need to be able to safely "corrupt" the next_ticket value with a "1", load the current_ticket value, and if they don't match, rewrite next_ticket with its old value. We can't safely do this if next_ticket and current_ticket are 16-bit fields in one 32-bit word, since the "tns" operation would corrupt the current_ticket value in that case, making someone waiting on ticket 0 think they owned the lock.

On tilegx we made the atomic instruction situation much, much better :-)

Quoted 3 lines
Quoted 3 lines

For 64-bit, a READ_ONCE() appears to be in order -- no obvious
volatility present.

It depends, I guess. If you are spinning on arch_spin_is_locked(), yes, you need to make sure to do something to ensure the value is re-read. But arch_spin_unlock_wait() already calls delay_backoff(), which calls relax(), which includes a barrier(), so we're OK there. But if stylistically the consensus calls for a READ_ONCE() in arch_spin_is_locked(), I can certainly add that. What do folks think?

Assuming the answers to both questions is "change the code", how does this look?

arch/tile/include/asm/spinlock_32.h +16 -1
index c0a77b38d39a..7c7b80bd83db 100644
@@ -41,8 +41,23 @@ static inline int arch_spin_is_locked(arch_spinlock_t *lock)
         * to claim the lock is held, since it will be momentarily
         * if not already.  There's no need to wait for a "valid"
         * lock->next_ticket to become available.
+        *
+        * We order the reads here so that if we claim the lock is
+        * unlocked, we know it actually was for at least a moment.
+        * Since current_ticket is never incremented above
+        * next_ticket, by reading current first, then next, and
+        * finding them equal, we know that during that window between
+        * the reads the lock was unlocked.
+        *
+        * There is a technical risk in this that between reading
+        * current and reading next, other cores locked and unlocked
+        * two billion times without the lock ever being unlocked, and
+        * therefore it looks like the lock was at some point unlocked
+        * but it never was.  But this seems highly improbable.
         */
-       return lock->next_ticket != lock->current_ticket;
+       int current = READ_ONCE(lock->current_ticket);
+       int next = READ_ONCE(lock->next_ticket);
+       return next != current;
 }
 
 void arch_spin_lock(arch_spinlock_t *lock);
arch/tile/include/asm/spinlock_64.h +4 -1
index 9a12b9c7e5d3..b9718fb4e74a 100644
@@ -18,6 +18,8 @@
 #ifndef _ASM_TILE_SPINLOCK_64_H
 #define _ASM_TILE_SPINLOCK_64_H
 
+#include <linux/compiler.h>
+
 /* Shifts and masks for the various fields in "lock". */
 #define __ARCH_SPIN_CURRENT_SHIFT      17
 #define __ARCH_SPIN_NEXT_MASK          0x7fff
@@ -44,7 +46,8 @@ static inline u32 arch_spin_next(u32 val)
 /* The lock is locked if a task would have to wait to get it. */
 static inline int arch_spin_is_locked(arch_spinlock_t *lock)
 {
-       u32 val = lock->lock;
+       /* Use READ_ONCE() to ensure that calling this in a loop is OK. */
+       u32 val = READ_ONCE(lock->lock);
        return arch_spin_current(val) != arch_spin_next(val);
 }
 
Signature · 2 lines
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com
maintainer
#31 lore raw
Quoted 9 lines · Chris Metcalf

As you surmise, tilepro doesn't have 64-bit loads. So we are stuck with 32-bit loads on these two fields. It's true that spin_unlock_wait() can therefore falsely claim that the lock is unlocked, but it should be only a hint anyway, since by the time the caller tries to act on that information the lock may have been retaken anyway, right? If spin_unlock_wait() is really trying to guarantee that the lock was available at some point in the interval between when it was called and when it returned, we could use READ_ONCE() to read the current ticket value first; is that a necessary part of the semantics?

I think it must not return before the lock holder that is current at the time of calling releases. Anything thereafter is indeed fair game as per your logic above.

#32 lore raw

PATCH 1/1 spinlock: clarify doc for raw_spin_unlock_wait()

The intent of the function is to wait for the current locker. Thus, we don't have to worry about potential later lockers, but we also have to ensure that the arch implementation doesn't return a false positive for the current locker.

---

Quoted 3 lines · Peter Zijlstra

I think it must not return before the lock holder that is current at the time of calling releases. Anything thereafter is indeed fair game as per your logic above.

Great, that seems like a workable definition. How does this modified language seem? With this definition I can actually modify the implementation of tile's arch_raw_spin_unlock_wait() to just read current_ticket once and just wait until it changes (assuming the lock is, in fact, locked).

Not sure whose tree this should go through; any takers?

 include/linux/spinlock.h | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
include/linux/spinlock.h +2 -1
index 3e18379dfa6f..36de5fc86647 100644
@@ -141,7 +141,8 @@ do {								\
 #endif
 
 /**
- * raw_spin_unlock_wait - wait until the spinlock gets unlocked
+ * raw_spin_unlock_wait - wait until the lock holder that is current at the
+ * time of calling releases the lock (or return immediately if unlocked).
  * @lock: the spinlock in question.
  */
 #define raw_spin_unlock_wait(lock)	arch_spin_unlock_wait(&(lock)->raw_lock)
Signature · 1 line
2.1.2
Acked-by on v1 1/1
#33 lore raw

Re: [PATCH] spinlock: clarify doc for raw_spin_unlock_wait()

Quoted 6 lines · Chris Metcalf

The intent of the function is to wait for the current locker. Thus, we don't have to worry about potential later lockers, but we also have to ensure that the arch implementation doesn't return a false positive for the current locker.

sysvsem depends on this definition, i.e. a false early return can cause a corrupted semaphore state.

Quoted 30 lines

---

Quoted 3 lines · Peter Zijlstra

I think it must not return before the lock holder that is current at the time of calling releases. Anything thereafter is indeed fair game as per your logic above.

Great, that seems like a workable definition. How does this modified language seem? With this definition I can actually modify the implementation of tile's arch_raw_spin_unlock_wait() to just read current_ticket once and just wait until it changes (assuming the lock is, in fact, locked).

Not sure whose tree this should go through; any takers?

  include/linux/spinlock.h | 3 ++-
  1 file changed, 2 insertions(+), 1 deletion(-)
include/linux/spinlock.h +2 -1
index 3e18379dfa6f..36de5fc86647 100644
@@ -141,7 +141,8 @@ do {								\
  #endif
 
  /**
- * raw_spin_unlock_wait - wait until the spinlock gets unlocked
+ * raw_spin_unlock_wait - wait until the lock holder that is current at the
+ * time of calling releases the lock (or return immediately if unlocked).
   * @lock: the spinlock in question.
   */
  #define raw_spin_unlock_wait(lock)	arch_spin_unlock_wait(&(lock)->raw_lock)
#34 lore raw

PATCH 1/2 tile: modify arch_spin_unlock_wait() semantics

In reply to Peter Zijlstra

Rather than trying to wait until all possible lockers have unlocked the lock, we now only wait until the current locker (if any) has released the lock.

The old code was correct, but the new code works more like the x86 code and thus hopefully is more appropriate under contention. See commit 78bff1c8684f ("x86/ticketlock: Fix spin_unlock_wait() livelock") for x86.

---
 arch/tile/lib/spinlock_32.c | 11 ++++++++++-
 arch/tile/lib/spinlock_64.c | 11 ++++++++++-
 2 files changed, 20 insertions(+), 2 deletions(-)
arch/tile/lib/spinlock_32.c +10 -1
index b34f79aada48..c3df3c237496 100644
@@ -65,8 +65,17 @@ EXPORT_SYMBOL(arch_spin_trylock);
 void arch_spin_unlock_wait(arch_spinlock_t *lock)
 {
 	u32 iterations = 0;
-	while (arch_spin_is_locked(lock))
+	int current = READ_ONCE(lock->current_ticket);
+	int next = READ_ONCE(lock->next_ticket);
+
+	/* Return immediately if unlocked. */
+	if (next == current)
+		return;
+
+	/* Wait until the current locker has released the lock. */
+	do {
 		delay_backoff(iterations++);
+	} while (READ_ONCE(lock->current_ticket) == current)
 }
 EXPORT_SYMBOL(arch_spin_unlock_wait);
 
arch/tile/lib/spinlock_64.c +10 -1
index d6fb9581e980..aaf12813d4db 100644
@@ -65,8 +65,17 @@ EXPORT_SYMBOL(arch_spin_trylock);
 void arch_spin_unlock_wait(arch_spinlock_t *lock)
 {
 	u32 iterations = 0;
-	while (arch_spin_is_locked(lock))
+	u32 val = READ_ONCE(lock->lock);
+	u32 current = arch_spin_current(val);
+
+	/* Return immediately if unlocked. */
+	if (arch_spin_next(val) == current)
+		return;
+
+	/* Wait until the current locker has released the lock. */
+	do {
 		delay_backoff(iterations++);
+	} while (arch_spin_current(READ_ONCE(lock->lock)) == current);
 }
 EXPORT_SYMBOL(arch_spin_unlock_wait);
 
Signature · 1 line
2.1.2
#35 lore raw

PATCH 2/2 tile: use READ_ONCE() in arch_spin_is_locked()

This avoid potential issues if callers were to loop on these routines without some kind of memory barrier. Currently there are no such users in-tree, but it seems better safe than sorry.

Also, in the tilepro case we read "current" before "next", which gives us a slightly better guarantee that the lock was actually unlocked at least momentarily if we return claiming that it is not locked. None of the callers actually rely on this behavior, as far as I know, however.

---
 arch/tile/include/asm/spinlock_32.h | 5 ++++-
 arch/tile/include/asm/spinlock_64.h | 5 ++++-
 2 files changed, 8 insertions(+), 2 deletions(-)
arch/tile/include/asm/spinlock_32.h +5 -1
index c0a77b38d39a..f7c1c0ebcf1d 100644
@@ -41,8 +41,12 @@ static inline int arch_spin_is_locked(arch_spinlock_t *lock)
 	 * to claim the lock is held, since it will be momentarily
 	 * if not already.  There's no need to wait for a "valid"
 	 * lock->next_ticket to become available.
+	 * Use READ_ONCE() to ensure that calling this in a loop is OK.
 	 */
-	return lock->next_ticket != lock->current_ticket;
+	int current = READ_ONCE(lock->current_ticket);
+	int next = READ_ONCE(lock->next_ticket);
+
+	return next != current;
 }
 
 void arch_spin_lock(arch_spinlock_t *lock);
arch/tile/include/asm/spinlock_64.h +4 -1
index 9a12b9c7e5d3..b9718fb4e74a 100644
@@ -18,6 +18,8 @@
 #ifndef _ASM_TILE_SPINLOCK_64_H
 #define _ASM_TILE_SPINLOCK_64_H
 
+#include <linux/compiler.h>
+
 /* Shifts and masks for the various fields in "lock". */
 #define __ARCH_SPIN_CURRENT_SHIFT	17
 #define __ARCH_SPIN_NEXT_MASK		0x7fff
@@ -44,7 +46,8 @@ static inline u32 arch_spin_next(u32 val)
 /* The lock is locked if a task would have to wait to get it. */
 static inline int arch_spin_is_locked(arch_spinlock_t *lock)
 {
-	u32 val = lock->lock;
+	/* Use READ_ONCE() to ensure that calling this in a loop is OK. */
+	u32 val = READ_ONCE(lock->lock);
 	return arch_spin_current(val) != arch_spin_next(val);
 }
 
Signature · 1 line
2.1.2
maintainer
#36 lore raw
In reply to Chris Metcalf
Quoted 3 lines · Chris Metcalf

The reason we use two 32-bit fields on tilepro is that the only available atomic instruction is tns (test and set), which sets a 32-bit "1" value into the target memory and returns the old 32-bit value.

And you want a ticket lock as opposed to the test-and-set lock because with 64 tiles starvation under contention is a real worry?

Where sparc32 (which only has the load-store-unsigned-byte instruction, which is similar to your tns except it writes 0xff) has the benefit of not actually having many CPUs you get to do 64 cpus!

#37 lore raw
Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Chris Metcalf

The reason we use two 32-bit fields on tilepro is that the only available atomic instruction is tns (test and set), which sets a 32-bit "1" value into the target memory and returns the old 32-bit value.

And you want a ticket lock as opposed to the test-and-set lock because with 64 tiles starvation under contention is a real worry?

We see substantial unfairness under load with a plain spinlock, basically because nearer cores on the mesh network can exponentially crowd out further cores. The ticket lock avoids that, though we have to be careful to do backoff when checking the lock to avoid DDoS in the mesh network.

Quoted 3 lines

Where sparc32 (which only has the load-store-unsigned-byte instruction, which is similar to your tns except it writes 0xff) has the benefit of not actually having many CPUs you get to do 64 cpus!

Yes, the 64-core thing is awesome, but the atomic instructions we built into the first generation chip weren't really adequate to the task.

Signature · 2 lines
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com
maintainer
#38 lore raw
Quoted 6 lines · Chris Metcalf
Quoted 5 lines · Peter Zijlstra
Quoted 3 lines · Chris Metcalf

The reason we use two 32-bit fields on tilepro is that the only available atomic instruction is tns (test and set), which sets a 32-bit "1" value into the target memory and returns the old 32-bit value.

Quoted 8 lines
Quoted 2 lines

And you want a ticket lock as opposed to the test-and-set lock because with 64 tiles starvation under contention is a real worry?

We see substantial unfairness under load with a plain spinlock, basically because nearer cores on the mesh network can exponentially crowd out further cores. The ticket lock avoids that, though we have to be careful to do backoff when checking the lock to avoid DDoS in the mesh network.

Does your arch have 16bit atomic load/stores ? If so, would something like the below not make sense?

typedef struct {
	union {
		struct {
			unsigned short head;
			unsigned short tail;
		};
		unsigned int tickets;
	};
	unsigned int lock;
} arch_spinlock_t;

static inline void ___tns_lock(unsigned int *lock)

{
	while (tns(lock))
		cpu_relax();
}

static inline void ___tns_unlock(unsigned int *lock)

{
	WRITE_ONCE(*lock, 0);
}

static inline void arch_spin_lock(arch_spinlock_t *lock)

{
	unsigned short head, tail;

	___tns_lock(&lock->lock); /* XXX does the TNS imply a ___sync?  */
	head = lock->head;
	lock->head++;
	___tns_unlock(&lock->lock);

	while (READ_ONCE(lock->tail) != head)
		cpu_relax();
}

static inline void arch_spin_unlock(arch_spinlock_t *lock)

{
	/*
	 * can do with regular load/store because the lock owner
	 * is the only one going to do stores to the tail
	 */
	unsigned short tail = READ_ONCE(lock->tail);
	smp_mb(); /* MB is stronger than RELEASE */
	WRITE_ONCE(lock->tail, tail + 1);
}

static inline void arch_spin_unlock_wait(arch_spinlock_t *lock)

{
	union {
		struct {
			unsigned short head;
			unsigned short tail;
		};
		unsigned int tickets;
	} x;

	for (;;) {
		x.tickets = READ_ONCE(lock->tickets);
		if (x.head == x.tail)
			break;
		cpu_relax();
	}
}
#39 lore raw
Quoted 9 lines · Peter Zijlstra
Quoted 8 lines · Chris Metcalf
Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Chris Metcalf

The reason we use two 32-bit fields on tilepro is that the only available atomic instruction is tns (test and set), which sets a 32-bit "1" value into the target memory and returns the old 32-bit value.

And you want a ticket lock as opposed to the test-and-set lock because with 64 tiles starvation under contention is a real worry?

Quoted 7 lines
Quoted 5 lines

We see substantial unfairness under load with a plain spinlock, basically because nearer cores on the mesh network can exponentially crowd out further cores. The ticket lock avoids that, though we have to be careful to do backoff when checking the lock to avoid DDoS in the mesh network.

Does your arch have 16bit atomic load/stores ? If so, would something like the below not make sense?

Yes, tilepro can do 16-bit atomic load/stores. The reason we didn't use your approach (basically having tns provide locking for the head/tail) is just a perceived efficiency gain from rolling the tns lock into the head.

The current tilepro arch_spin_lock() is just three mesh network transactions (tns, store, load). Your proposed spin lock is five (tns, load, store, store, load). Or, looking it from a core-centric perspective, the current arch_spin_lock() only has to wait on requests from the mesh network twice (tns, load), basically once for each member of the lock structure; your proposed version is three (tns, load, load).

I don't honestly know how critical this difference is, but that's why I designed it the way I did.

I think your goal with your proposed redesign is being able to atomically read head and tail together for arch_spin_unlock_wait(), but I don't see why that's better than just reading head, checking it's not equal to tail with a separate read, then spinning waiting for head to change.

Quoted 64 lines
typedef struct {
	union {
		struct {
			unsigned short head;
			unsigned short tail;
		};
		unsigned int tickets;
	};
	unsigned int lock;
} arch_spinlock_t;

static inline void ___tns_lock(unsigned int *lock)

{
	while (tns(lock))
		cpu_relax();
}

static inline void ___tns_unlock(unsigned int *lock)

{
	WRITE_ONCE(*lock, 0);
}

static inline void arch_spin_lock(arch_spinlock_t *lock)

{
	unsigned short head, tail;

	___tns_lock(&lock->lock); /* XXX does the TNS imply a ___sync?  */
	head = lock->head;
	lock->head++;
	___tns_unlock(&lock->lock);

	while (READ_ONCE(lock->tail) != head)
		cpu_relax();
}

static inline void arch_spin_unlock(arch_spinlock_t *lock)

{
	/*
	 * can do with regular load/store because the lock owner
	 * is the only one going to do stores to the tail
	 */
	unsigned short tail = READ_ONCE(lock->tail);
	smp_mb(); /* MB is stronger than RELEASE */
	WRITE_ONCE(lock->tail, tail + 1);
}

static inline void arch_spin_unlock_wait(arch_spinlock_t *lock)

{
	union {
		struct {
			unsigned short head;
			unsigned short tail;
		};
		unsigned int tickets;
	} x;

	for (;;) {
		x.tickets = READ_ONCE(lock->tickets);
		if (x.head == x.tail)
			break;
		cpu_relax();
	}
}
Signature · 2 lines
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com
maintainer
#40 lore raw
Quoted 13 lines · Chris Metcalf

Yes, tilepro can do 16-bit atomic load/stores. The reason we didn't use your approach (basically having tns provide locking for the head/tail) is just a perceived efficiency gain from rolling the tns lock into the head.

The current tilepro arch_spin_lock() is just three mesh network transactions (tns, store, load). Your proposed spin lock is five (tns, load, store, store, load).
Or, looking it from a core-centric perspective, the current arch_spin_lock() only has to wait on requests from the mesh network twice (tns, load), basically
once for each member of the lock structure; your proposed version is three (tns, load, load).

Quoted 2 lines

I don't honestly know how critical this difference is, but that's why I designed it the way I did.

Makes sense. Good reason ;-)

Quoted 4 lines

I think your goal with your proposed redesign is being able to atomically read head and tail together for arch_spin_unlock_wait(), but I don't see why that's better than just reading head, checking it's not equal to tail with a separate read, then spinning waiting for head to change.

Right, that should be perfectly fine indeed.

A few questions:

Quoted 5 lines
Quoted 5 lines

static inline void arch_spin_lock(arch_spinlock_t *lock)

{
	unsigned short head, tail;

	___tns_lock(&lock->lock); /* XXX does the TNS imply a ___sync?  */

Does it? Something needs to provide the ACQUIRE semantics.

Quoted 8 lines
Quoted 8 lines
	head = lock->head;
	lock->head++;
	___tns_unlock(&lock->lock);

	while (READ_ONCE(lock->tail) != head)
		cpu_relax();
}
Quoted 8 lines
Quoted 8 lines

static inline void arch_spin_unlock(arch_spinlock_t *lock)

{
	/*
	 * can do with regular load/store because the lock owner
	 * is the only one going to do stores to the tail
	 */
	unsigned short tail = READ_ONCE(lock->tail);
	smp_mb(); /* MB is stronger than RELEASE */

Note that your code uses wmb(), wmb is strictly speaking not correct, as its weaker than RELEASE.

_However_ it doesn't make any practical difference since all three barriers end up emitting __sync() so its not a bug per se.

Quoted 2 lines
Quoted 2 lines
	WRITE_ONCE(lock->tail, tail + 1);
}
#41 lore raw
Quoted 9 lines · Peter Zijlstra

A few questions:

Quoted 5 lines · Chris Metcalf
Quoted 5 lines

static inline void arch_spin_lock(arch_spinlock_t *lock)

{
	unsigned short head, tail;

	___tns_lock(&lock->lock); /* XXX does the TNS imply a ___sync?  */

Does it? Something needs to provide the ACQUIRE semantics.

Yes, __insn_xxx() is a compiler barrier on tile.

Tile architectures do not need any hardware-level "acquire" semantics since normally control dependency is sufficient for lock acquisition. Loads and stores are issued in-order into the mesh network, but issued loads don't block further instruction issue until a register read dependency requires it. There is no speculative execution.

Quoted 16 lines
Quoted 8 lines
Quoted 8 lines
	head = lock->head;
	lock->head++;
	___tns_unlock(&lock->lock);

	while (READ_ONCE(lock->tail) != head)
		cpu_relax();
}
Quoted 8 lines
Quoted 8 lines

static inline void arch_spin_unlock(arch_spinlock_t *lock)

{
	/*
	 * can do with regular load/store because the lock owner
	 * is the only one going to do stores to the tail
	 */
	unsigned short tail = READ_ONCE(lock->tail);
	smp_mb(); /* MB is stronger than RELEASE */
Quoted 5 lines

Note that your code uses wmb(), wmb is strictly speaking not correct, as its weaker than RELEASE.

_However_ it doesn't make any practical difference since all three barriers end up emitting __sync() so its not a bug per se.

Yes, this code dates back to 2.6.18 or so; today I would use smp_store_release(). I like the trend in the kernel to move more towards the C11 memory order model; I think it will help a lot.

Signature · 2 lines
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com
maintainer Acked-by
#42 lore raw
In reply to Paul E. McKenney
Quoted 4 lines · Paul E. McKenney

smp: Make control dependencies work on Alpha, improve documentation

The current formulation of control dependencies fails on DEC Alpha, which does not respect dependencies of any kind unless an explicit memory is

+ barrier ?

Quoted 10 lines

provided. This means that the current fomulation of control dependencies fails on Alpha. This commit therefore creates a READ_ONCE_CTRL() that has the same overhead on non-Alpha systems, but causes Alpha to produce the needed ordering. This commit also applies READ_ONCE_CTRL() to the one known use of control dependencies.

Use of READ_ONCE_CTRL() also has the beneficial effect of adding a bit of self-documentation to control dependencies.

Quoted 17 lines
include/linux/compiler.h +9 -0
index 1b45e4a0519b..a57eacde2b84 100644
@@ -264,6 +264,22 @@ static __always_inline void __write_once_size(volatile void *p, void *res, int s
 #define WRITE_ONCE(x, val) \
 	({ typeof(x) __val = (val); __write_once_size(&(x), &__val, sizeof(__val)); __val; })
 
+/**
+ * READ_ONCE_CTRL - Read a value heading a control dependency
+ * @x: The value to be read, heading the control dependency
+ *
+ * Control dependencies are tricky.  See Documentation/memory-barriers.txt
+ * for important information on how to use them.  Note that in many cases,
+ * use of smp_load_acquire() will be much simpler.  Control dependencies
+ * should be avoided except on the hottest of hotpaths.
+ */

include/linux/compiler.h static __always_inline void __write_once_size(volatile void *p, void *res, int s · line 285

Quoted 10 lines
include/linux/compiler.h +7 -0
+#define READ_ONCE_CTRL(x) \
+({ \
+	typeof(x) __val = READ_ONCE(x); \
+	smp_read_barrier_depends(); /* Enforce control dependency. */ \
+	__val; \
+})
+
 #endif /* __KERNEL__ */
 
 #endif /* __ASSEMBLY__ */

We mostly try and align the \ for multi-line macros.

kernel/events/ring_buffer.c int perf_output_begin(struct perf_output_handle *handle, · line 147

Quoted 13 lines
kernel/events/ring_buffer.c +1 -1
index eadb95ce7aac..67548d5de4cb 100644
@@ -141,7 +141,7 @@ int perf_output_begin(struct perf_output_handle *handle,
 	perf_output_get_handle(handle);
 
 	do {
-		tail = ACCESS_ONCE(rb->user_page->data_tail);
+		tail = READ_ONCE_CTRL(rb->user_page->data_tail);
 		offset = head = local_read(&rb->head);
 		if (!rb->overwrite &&
 		    unlikely(CIRC_SPACE(head, tail, perf_data_size(rb)) < size))

Right. I could not remember any other current usage.

#43 lore raw
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · Paul E. McKenney

smp: Make control dependencies work on Alpha, improve documentation

The current formulation of control dependencies fails on DEC Alpha, which does not respect dependencies of any kind unless an explicit memory is

+ barrier ?

Good catch, fixed!

Quoted 6 lines
Quoted 6 lines

provided. This means that the current fomulation of control dependencies fails on Alpha. This commit therefore creates a READ_ONCE_CTRL() that has the same overhead on non-Alpha systems, but causes Alpha to produce the needed ordering. This commit also applies READ_ONCE_CTRL() to the one known use of control dependencies.

Quoted 6 lines
Quoted 4 lines

Use of READ_ONCE_CTRL() also has the beneficial effect of adding a bit of self-documentation to control dependencies.

Applied, thank you!

Thanx, Paul

Quoted 46 lines
Quoted 17 lines
include/linux/compiler.h +9 -0
index 1b45e4a0519b..a57eacde2b84 100644
@@ -264,6 +264,22 @@ static __always_inline void __write_once_size(volatile void *p, void *res, int s
 #define WRITE_ONCE(x, val) \
 	({ typeof(x) __val = (val); __write_once_size(&(x), &__val, sizeof(__val)); __val; })
 
+/**
+ * READ_ONCE_CTRL - Read a value heading a control dependency
+ * @x: The value to be read, heading the control dependency
+ *
+ * Control dependencies are tricky.  See Documentation/memory-barriers.txt
+ * for important information on how to use them.  Note that in many cases,
+ * use of smp_load_acquire() will be much simpler.  Control dependencies
+ * should be avoided except on the hottest of hotpaths.
+ */

include/linux/compiler.h static __always_inline void __write_once_size(volatile void *p, void *res, int s · line 285

Quoted 10 lines
include/linux/compiler.h +7 -0
+#define READ_ONCE_CTRL(x) \
+({ \
+	typeof(x) __val = READ_ONCE(x); \
+	smp_read_barrier_depends(); /* Enforce control dependency. */ \
+	__val; \
+})
+
 #endif /* __KERNEL__ */
 
 #endif /* __ASSEMBLY__ */

We mostly try and align the \ for multi-line macros.

kernel/events/ring_buffer.c int perf_output_begin(struct perf_output_handle *handle, · line 147

Quoted 13 lines
kernel/events/ring_buffer.c +1 -1
index eadb95ce7aac..67548d5de4cb 100644
@@ -141,7 +141,7 @@ int perf_output_begin(struct perf_output_handle *handle,
 	perf_output_get_handle(handle);
 
 	do {
-		tail = ACCESS_ONCE(rb->user_page->data_tail);
+		tail = READ_ONCE_CTRL(rb->user_page->data_tail);
 		offset = head = local_read(&rb->head);
 		if (!rb->overwrite &&
 		    unlikely(CIRC_SPACE(head, tail, perf_data_size(rb)) < size))

Right. I could not remember any other current usage.

#44 lore raw
In reply to Manfred Spraul
Quoted 37 lines · Manfred Spraul

Hi Oleg,

my example was bad, let's continue with your example.

And: If sem_lock() needs another smp_xmb(), then we must add it:
Some apps do not have a user space hot path, i.e. it seems that on some setups, we have millions of calls per second.
If there is a race, then it will happen.

I've tried to merge your example:

Quoted 20 lines

int X = 0, Y = 0;

void func(void)

{
    bool ll = rand();

    if (ll) {
        spin_lock(&local);
        if (!spin_is_locked(&global))
            goto done;
        spin_unlock(&local);
    }
    ll = false;
    spin_lock(&global);
    spin_unlock_wait(&local);
done:
    smp_rmb(); <<<<<<<<<<<<<<<
    BUG_ON(X != Y);
Quoted 7 lines
    ++X; ++Y;

    if (ll)
        spin_unlock(&local);
    else
        spin_unlock(&global);
}
Quoted 8 lines

I agree, we need the smp_rmb().
I'll write a patch.

Quoted 2 lines

We need the full barrier to serialize STORE's as well, but probably we can rely on control dependancy and thus we only need rmb().

Do we need a full barrier or not?

I don't manage to create a proper line of reasoning.

This has to be one of the more bizarre forms of Dekker's algorithm that I have seen. ;-)

I am going to have to put this through one of the tools...

Thanx, Paul

#45 lore raw
Quoted 43 lines · Paul E. McKenney
Quoted 42 lines · Manfred Spraul

Hi Oleg,

my example was bad, let's continue with your example.

And: If sem_lock() needs another smp_xmb(), then we must add it:
Some apps do not have a user space hot path, i.e. it seems that on some setups, we have millions of calls per second.
If there is a race, then it will happen.

I've tried to merge your example:

Quoted 20 lines

int X = 0, Y = 0;

void func(void)

{
    bool ll = rand();

    if (ll) {
        spin_lock(&local);
        if (!spin_is_locked(&global))
            goto done;
        spin_unlock(&local);
    }
    ll = false;
    spin_lock(&global);
    spin_unlock_wait(&local);
done:
    smp_rmb(); <<<<<<<<<<<<<<<
    BUG_ON(X != Y);
Quoted 7 lines
    ++X; ++Y;

    if (ll)
        spin_unlock(&local);
    else
        spin_unlock(&global);
}

I agree, we need the smp_rmb().
I'll write a patch.

Quoted 2 lines

We need the full barrier to serialize STORE's as well, but probably we can rely on control dependancy and thus we only need rmb().

Quoted 8 lines
Quoted 3 lines

Do we need a full barrier or not?

I don't manage to create a proper line of reasoning.

This has to be one of the more bizarre forms of Dekker's algorithm that I have seen. ;-)

I am going to have to put this through one of the tools...

And this was just me getting confused by memories of old versions of the code. This will work given current mainline code. Please accept my apologies for the noise.

And yes, you do need the smp_rmb() to ensure that the BUG_ON() happens after the other guy releases his spinlock.

Thanx, Paul

#46 lore raw

[tip:sched/core] sched: Clarify ordering between task_rq_lock() and move_queued_task()

In reply to Peter Zijlstra
sched: Clarify ordering between task_rq_lock() and move_queued_task()
Commit-ID:  74b8a4cb6ce3685049ee124243a52238c5cabe55
Gitweb:     http://git.kernel.org/tip/74b8a4cb6ce3685049ee124243a52238c5cabe55
Author:     Peter Zijlstra <[email protected]>
AuthorDate: Tue, 17 Feb 2015 13:07:38 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 18 Feb 2015 14:27:28 +0100

sched: Clarify ordering between task_rq_lock() and move_queued_task()

There was a wee bit of confusion around the exact ordering here; clarify things.

---
 kernel/sched/core.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
kernel/sched/core.c +16 -0
index 1f37fe7..fd0a6ed 100644
@@ -341,6 +341,22 @@ static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags)
 		raw_spin_lock_irqsave(&p->pi_lock, *flags);
 		rq = task_rq(p);
 		raw_spin_lock(&rq->lock);
+		/*
+		 *	move_queued_task()		task_rq_lock()
+		 *
+		 *	ACQUIRE (rq->lock)
+		 *	[S] ->on_rq = MIGRATING		[L] rq = task_rq()
+		 *	WMB (__set_task_cpu())		ACQUIRE (rq->lock);
+		 *	[S] ->cpu = new_cpu		[L] task_rq()
+		 *					[L] ->on_rq
+		 *	RELEASE (rq->lock)
+		 *
+		 * If we observe the old cpu in task_rq_lock, the acquire of
+		 * the old rq->lock will fully serialize against the stores.
+		 *
+		 * If we observe the new cpu in task_rq_lock, the acquire will
+		 * pair with the WMB to ensure we must then also see migrating.
+		 */
 		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
 			return rq;
 		raw_spin_unlock(&rq->lock);