Skip to contentSkip to conversation

scheduler ordering bits

PATCH In review Peter Zijlstra 9 participants 78 messages Nov 2, 2015 – Dec 4, 2015

Subsystems (9)
lore
Share & tools
lore

Peter Zijlstra

author maintainer
#0 lore raw

cover scheduler ordering bits

Hai,

These patches are the result of recent discussions in a thread on barrier documentation.

Please have a careful look, as always, this stuff is tricky.

author maintainer
#1 lore raw

PATCH 1/4 sched: Better document the try_to_wake_up() barriers

Explain how the control dependency and smp_rmb() end up providing ACQUIRE semantics and pair with smp_store_release() in finish_lock_switch().

Cc Paul E. McKenney <[email protected]>
Cc Oleg Nesterov <[email protected]>
---
 kernel/sched/core.c  |    8 +++++++-
 kernel/sched/sched.h |    3 +++
 2 files changed, 10 insertions(+), 1 deletion(-)
kernel/sched/core.c +7 -1
@@ -1947,7 +1947,13 @@ try_to_wake_up(struct task_struct *p, un
 	while (p->on_cpu)
 		cpu_relax();
 	/*
-	 * Pairs with the smp_wmb() in finish_lock_switch().
+	 * Combined with the control dependency above, we have an effective
+	 * smp_load_acquire() without the need for full barriers.
+	 *
+	 * Pairs with the smp_store_release() in finish_lock_switch().
+	 *
+	 * This ensures that tasks getting woken will be fully ordered against
+	 * their previous state and preserve Program Order.
 	 */
 	smp_rmb();
 
kernel/sched/sched.h +3 -0
@@ -1073,6 +1073,9 @@ static inline void finish_lock_switch(st
 	 * We must ensure this doesn't happen until the switch is completely
 	 * finished.
 	 *
+	 * In particular, the load of prev->state in finish_task_switch() must
+	 * happen before this.
+	 *
 	 * Pairs with the control dependency and rmb in try_to_wake_up().
 	 */
 	smp_store_release(&prev->on_cpu, 0);
#2 lore raw

Re: [PATCH 1/4] sched: Better document the try_to_wake_up() barriers

Quoted 18 lines · Peter Zijlstra

Explain how the control dependency and smp_rmb() end up providing ACQUIRE semantics and pair with smp_store_release() in finish_lock_switch().

Cc Paul E. McKenney <[email protected]>
Cc Oleg Nesterov <[email protected]>
---
 kernel/sched/core.c  |    8 +++++++-
 kernel/sched/sched.h |    3 +++
 2 files changed, 10 insertions(+), 1 deletion(-)
kernel/sched/core.c +0 -0
@@ -1947,7 +1947,13 @@ try_to_wake_up(struct task_struct *p, un
 	while (p->on_cpu)
 		cpu_relax();
 	/*

kernel/sched/core.c try_to_wake_up(struct task_struct *p, un · line 1958

Quoted 10 lines
kernel/sched/core.c +7 -1
-	 * Pairs with the smp_wmb() in finish_lock_switch().
+	 * Combined with the control dependency above, we have an effective
+	 * smp_load_acquire() without the need for full barriers.
+	 *
+	 * Pairs with the smp_store_release() in finish_lock_switch().
+	 *
+	 * This ensures that tasks getting woken will be fully ordered against
+	 * their previous state and preserve Program Order.
 	 */
 	smp_rmb();

Hello,

I am not sure, but just curious..

I thought it's good enough to use a kind of dependancy barrier such as smp_read_barrier_depends() instead of smp_rmb() here unless something e.g. compiler breaks the control dependacy. Right?

Quoted 20 lines
kernel/sched/sched.h +3 -1
@@ -1073,6 +1073,9 @@ static inline void finish_lock_switch(st
 	 * We must ensure this doesn't happen until the switch is completely
 	 * finished.
 	 *
+	 * In particular, the load of prev->state in finish_task_switch() must
+	 * happen before this.
+	 *
 	 * Pairs with the control dependency and rmb in try_to_wake_up().
 	 */
 	smp_store_release(&prev->on_cpu, 0);
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

#3 lore raw

Re: [PATCH 1/4] sched: Better document the try_to_wake_up() barriers

In reply to Peter Zijlstra
Quoted 18 lines · Peter Zijlstra

Explain how the control dependency and smp_rmb() end up providing ACQUIRE semantics and pair with smp_store_release() in finish_lock_switch().

Cc Paul E. McKenney <[email protected]>
Cc Oleg Nesterov <[email protected]>
---
 kernel/sched/core.c  |    8 +++++++-
 kernel/sched/sched.h |    3 +++
 2 files changed, 10 insertions(+), 1 deletion(-)
kernel/sched/core.c +0 -0
@@ -1947,7 +1947,13 @@ try_to_wake_up(struct task_struct *p, un
 	while (p->on_cpu)
 		cpu_relax();
 	/*

kernel/sched/core.c try_to_wake_up(struct task_struct *p, un · line 1958

Quoted 10 lines
kernel/sched/core.c +7 -1
-	 * Pairs with the smp_wmb() in finish_lock_switch().
+	 * Combined with the control dependency above, we have an effective
+	 * smp_load_acquire() without the need for full barriers.
+	 *
+	 * Pairs with the smp_store_release() in finish_lock_switch().
+	 *
+	 * This ensures that tasks getting woken will be fully ordered against
+	 * their previous state and preserve Program Order.
 	 */
 	smp_rmb();

I am very sorry.

Please ignore my previous question :-(

Quoted 20 lines
kernel/sched/sched.h +3 -1
@@ -1073,6 +1073,9 @@ static inline void finish_lock_switch(st
 	 * We must ensure this doesn't happen until the switch is completely
 	 * finished.
 	 *
+	 * In particular, the load of prev->state in finish_task_switch() must
+	 * happen before this.
+	 *
 	 * Pairs with the control dependency and rmb in try_to_wake_up().
 	 */
 	smp_store_release(&prev->on_cpu, 0);
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

author maintainer
#4 lore raw

PATCH 2/4 sched: Document Program-Order guarantees

In reply to Peter Zijlstra

These are some notes on the scheduler locking and how it provides program order guarantees on SMP systems.

Cc Linus Torvalds <[email protected]>
Cc Will Deacon <[email protected]>
Cc Oleg Nesterov <[email protected]>
Cc Boqun Feng <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc Jonathan Corbet <[email protected]>
Cc Michal Hocko <[email protected]>
Cc David Howells <[email protected]>
---
 kernel/sched/core.c |  142 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 142 insertions(+)
kernel/sched/core.c +142 -0
@@ -1905,6 +1905,148 @@ static void ttwu_queue(struct task_struc
 	raw_spin_unlock(&rq->lock);
 }
 
+/*
+ * Notes on Program-Order guarantees on SMP systems.
+ *
+ *
+ *   PREEMPTION/MIGRATION
+ *
+ * Regular preemption/migration is safe because as long as the task is runnable
+ * migrations involve both rq locks, albeit not (necessarily) at the same time.
+ *
+ * So we get (we allow 3 CPU migrations):
+ *
+ *   CPU0            CPU1            CPU2
+ *
+ *   LOCK rq(0)->lock
+ *   sched-out X
+ *   sched-in Y
+ *   UNLOCK rq(0)->lock
+ *
+ *                                   LOCK rq(0)->lock // MB against CPU0
+ *                                   dequeue X
+ *                                   UNLOCK rq(0)->lock
+ *
+ *                                   LOCK rq(1)->lock
+ *                                   enqueue X
+ *                                   UNLOCK rq(1)->lock
+ *
+ *                   LOCK rq(1)->lock // MB against CPU2
+ *                   sched-out Z
+ *                   sched-in X
+ *                   UNLOCK rq(1)->lock
+ *
+ * and the first LOCK rq(0) on CPU2 gives a full order against the UNLOCK rq(0)
+ * on CPU0. Similarly the LOCK rq(1) on CPU1 provides full order against the
+ * UNLOCK rq(1) on CPU2, therefore by the time task X runs on CPU1 it must
+ * observe the state it left behind on CPU0.
+ *
+ *
+ *   BLOCKING -- aka. SLEEP + WAKEUP
+ *
+ * For blocking things are a little more interesting, because when we dequeue
+ * the task, we don't need to acquire the old rq lock in order to migrate it.
+ *
+ * Say CPU0 does a wait_event() and CPU1 does the wake() and migrates the task
+ * to CPU2 (the most complex example):
+ *
+ *   CPU0 (schedule)  CPU1 (try_to_wake_up) CPU2 (sched_ttwu_pending)
+ *
+ *   X->state = UNINTERRUPTIBLE
+ *   MB
+ *   if (cond)
+ *     break
+ *                    cond = true
+ *
+ *   LOCK rq(0)->lock LOCK X->pi_lock
+ *
+ *   dequeue X
+ *                    while (X->on_cpu)
+ *                      cpu_relax()
+ *   sched-out X
+ *   RELEASE
+ *   X->on_cpu = 0
+ *                    RMB
+ *                    X->state = WAKING
+ *                    set_task_cpu(X,2)
+ *                      WMB
+ *                      ti(X)->cpu = 2
+ *
+ *                    llist_add(X, rq(2)) // MB
+ *                                          llist_del_all() // MB
+ *
+ *                                          LOCK rq(2)->lock
+ *                                          enqueue X
+ *                                          X->state = RUNNING
+ *                                          UNLOCK rq(2)->lock
+ *
+ *                                          LOCK rq(2)->lock
+ *                                          sched-out Z
+ *                                          sched-in X
+ *                                          UNLOCK rq(1)->lock
+ *
+ *                                          if (cond) // _TRUE_
+ *                    UNLOCK X->pi_lock
+ *   UNLOCK rq(0)->lock
+ *
+ * So in this case the scheduler does not provide an obvious full barrier; but
+ * the smp_store_release() in finish_lock_switch(), paired with the control-dep
+ * and smp_rmb() in try_to_wake_up() form a release-acquire pair and fully
+ * order things between CPU0 and CPU1.
+ *
+ * The llist primitives order things between CPU1 and CPU2 -- the alternative
+ * is CPU1 doing the remote enqueue (the alternative path in ttwu_queue()) in
+ * which case the rq(2)->lock release/acquire will order things between them.
+ *
+ * Which again leads to the guarantee that by the time X gets to run on CPU2
+ * it must observe the state it left behind on CPU0.
+ *
+ * However; for blocking there is a second guarantee we must provide, namely we
+ * must observe the state that lead to our wakeup. That is, not only must X
+ * observe its own prior state, it must also observe the @cond store.
+ *
+ * This too is achieved in the above, since CPU1 does the waking, we only need
+ * the ordering between CPU1 and CPU2, which is the same as the above.
+ *
+ *
+ * There is however a much more interesting case for this guarantee, where X
+ * never makes it off CPU0:
+ *
+ *   CPU0 (schedule)  CPU1 (try_to_wake_up)
+ *
+ *   X->state = UNINTERRUPTIBLE
+ *   MB
+ *   if (cond)
+ *     break
+ *                    cond = true
+ *
+ *                    WMB (aka smp_mb__before_spinlock)
+ *                    LOCK X->pi_lock
+ *
+ *                    if (X->on_rq)
+ *                      LOCK rq(0)->lock
+ *                      X->state = RUNNING
+ *                      UNLOCK rq(0)->lock
+ *
+ *   LOCK rq(0)->lock // MB against CPU1
+ *   UNLOCK rq(0)->lock
+ *
+ *   if (cond) // _TRUE_
+ *
+ *                    UNLOCK X->pi_lock
+ *
+ * Here our task X never quite leaves CPU0, the wakeup happens before we can
+ * dequeue and schedule someone else. In this case we must still observe cond
+ * after our call to schedule() completes.
+ *
+ * This is achieved by the smp_mb__before_spinlock() WMB which ensures the store
+ * cannot leak inside the LOCK, and LOCK rq(0)->lock on CPU0 provides full order
+ * against the UNLOCK rq(0)->lock from CPU1. Furthermore our load of cond cannot
+ * happen before this same LOCK.
+ *
+ * Therefore, again, we're good.
+ */
+
 /**
  * try_to_wake_up - wake up a thread
  * @p: the thread to be awakened
#5 lore raw

Re: [PATCH 2/4] sched: Document Program-Order guarantees

Quoted 48 lines · Peter Zijlstra

These are some notes on the scheduler locking and how it provides program order guarantees on SMP systems.

Cc Linus Torvalds <[email protected]>
Cc Will Deacon <[email protected]>
Cc Oleg Nesterov <[email protected]>
Cc Boqun Feng <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc Jonathan Corbet <[email protected]>
Cc Michal Hocko <[email protected]>
Cc David Howells <[email protected]>
---
 kernel/sched/core.c |  142 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 142 insertions(+)
kernel/sched/core.c +26 -0
@@ -1905,6 +1905,148 @@ static void ttwu_queue(struct task_struc
        raw_spin_unlock(&rq->lock);
 }
 
+/*
+ * Notes on Program-Order guarantees on SMP systems.
+ *
+ *
+ *   PREEMPTION/MIGRATION
+ *
+ * Regular preemption/migration is safe because as long as the task is runnable
+ * migrations involve both rq locks, albeit not (necessarily) at the same time.
+ *
+ * So we get (we allow 3 CPU migrations):
+ *
+ *   CPU0            CPU1            CPU2
+ *
+ *   LOCK rq(0)->lock
+ *   sched-out X
+ *   sched-in Y
+ *   UNLOCK rq(0)->lock
+ *
+ *                                   LOCK rq(0)->lock // MB against CPU0
+ *                                   dequeue X
+ *                                   UNLOCK rq(0)->lock
+ *
+ *                                   LOCK rq(1)->lock
+ *                                   enqueue X
+ *                                   UNLOCK rq(1)->lock
+ *

kernel/sched/core.c static void ttwu_queue(struct task_struc · line 1943

Quoted 10 lines
kernel/sched/core.c +10 -0
+ *                   LOCK rq(1)->lock // MB against CPU2
+ *                   sched-out Z
+ *                   sched-in X
+ *                   UNLOCK rq(1)->lock
+ *
+ * and the first LOCK rq(0) on CPU2 gives a full order against the UNLOCK rq(0)
+ * on CPU0. Similarly the LOCK rq(1) on CPU1 provides full order against the
+ * UNLOCK rq(1) on CPU2, therefore by the time task X runs on CPU1 it must
+ * observe the state it left behind on CPU0.
+ *

I suspect this part might be more explicitly expressed by specifying the requirements that migration satisfies; then providing an example. This makes it easier for others to reason about the locks and saves worrying about whether the examples hit our 3 million sub-cases.

I'd also propose just dropping preemption from this part, we only need memory order to be correct on migration, whether it's scheduled or not [it also invites confusion with the wake-up case].

Something like:
When any task 't' migrates, all activity on its prior cpu [c1] is guaranteed to be happens-before any subsequent execution on its new cpu [c2]. There are 3 components to enforcing this.

[c1] 1) Sched-out of t requires rq(c1)->lock
[any cpu] 2) Any migration of t, by any cpu is required to synchronize on *both* rq(c1)->lock and rq(c2)->lock
[c2] 3) Sched-in of t requires cq(c2)->lock

Transitivity guarantees that (2) orders after (1) and (3) after (2). Note that in some cases (e.g. active, or idle cpu) the balancing cpu in (2) may be c1 or c2.

[Follow example]

Quoted 46 lines
kernel/sched/core.c +46 -0
+ *
+ *   BLOCKING -- aka. SLEEP + WAKEUP
+ *
+ * For blocking things are a little more interesting, because when we dequeue
+ * the task, we don't need to acquire the old rq lock in order to migrate it.
+ *
+ * Say CPU0 does a wait_event() and CPU1 does the wake() and migrates the task
+ * to CPU2 (the most complex example):
+ *
+ *   CPU0 (schedule)  CPU1 (try_to_wake_up) CPU2 (sched_ttwu_pending)
+ *
+ *   X->state = UNINTERRUPTIBLE
+ *   MB
+ *   if (cond)
+ *     break
+ *                    cond = true
+ *
+ *   LOCK rq(0)->lock LOCK X->pi_lock
+ *
+ *   dequeue X
+ *                    while (X->on_cpu)
+ *                      cpu_relax()
+ *   sched-out X
+ *   RELEASE
+ *   X->on_cpu = 0
+ *                    RMB
+ *                    X->state = WAKING
+ *                    set_task_cpu(X,2)
+ *                      WMB
+ *                      ti(X)->cpu = 2
+ *
+ *                    llist_add(X, rq(2)) // MB
+ *                                          llist_del_all() // MB
+ *
+ *                                          LOCK rq(2)->lock
+ *                                          enqueue X
+ *                                          X->state = RUNNING
+ *                                          UNLOCK rq(2)->lock
+ *
+ *                                          LOCK rq(2)->lock
+ *                                          sched-out Z
+ *                                          sched-in X
+ *                                          UNLOCK rq(1)->lock
+ *
+ *                                          if (cond) // _TRUE_
+ *                    UNLOCK X->pi_lock

kernel/sched/core.c static void ttwu_queue(struct task_struc · line 1999

Quoted 10 lines
kernel/sched/core.c +10 -0
+ *   UNLOCK rq(0)->lock
+ *
+ * So in this case the scheduler does not provide an obvious full barrier; but
+ * the smp_store_release() in finish_lock_switch(), paired with the control-dep
+ * and smp_rmb() in try_to_wake_up() form a release-acquire pair and fully
+ * order things between CPU0 and CPU1.
+ *
+ * The llist primitives order things between CPU1 and CPU2 -- the alternative
+ * is CPU1 doing the remote enqueue (the alternative path in ttwu_queue()) in
+ * which case the rq(2)->lock release/acquire will order things between them.

I'd vote for similar treatment here. We can make the dependency on on_cpu much more obvious, something that is a reasonably subtle detail today.

Quoted 60 lines
kernel/sched/core.c +50 -1
+ *
+ * Which again leads to the guarantee that by the time X gets to run on CPU2
+ * it must observe the state it left behind on CPU0.
+ *
+ * However; for blocking there is a second guarantee we must provide, namely we
+ * must observe the state that lead to our wakeup. That is, not only must X
+ * observe its own prior state, it must also observe the @cond store.
+ *
+ * This too is achieved in the above, since CPU1 does the waking, we only need
+ * the ordering between CPU1 and CPU2, which is the same as the above.
+ *
+ *
+ * There is however a much more interesting case for this guarantee, where X
+ * never makes it off CPU0:
+ *
+ *   CPU0 (schedule)  CPU1 (try_to_wake_up)
+ *
+ *   X->state = UNINTERRUPTIBLE
+ *   MB
+ *   if (cond)
+ *     break
+ *                    cond = true
+ *
+ *                    WMB (aka smp_mb__before_spinlock)
+ *                    LOCK X->pi_lock
+ *
+ *                    if (X->on_rq)
+ *                      LOCK rq(0)->lock
+ *                      X->state = RUNNING
+ *                      UNLOCK rq(0)->lock
+ *
+ *   LOCK rq(0)->lock // MB against CPU1
+ *   UNLOCK rq(0)->lock
+ *
+ *   if (cond) // _TRUE_
+ *
+ *                    UNLOCK X->pi_lock
+ *
+ * Here our task X never quite leaves CPU0, the wakeup happens before we can
+ * dequeue and schedule someone else. In this case we must still observe cond
+ * after our call to schedule() completes.
+ *
+ * This is achieved by the smp_mb__before_spinlock() WMB which ensures the store
+ * cannot leak inside the LOCK, and LOCK rq(0)->lock on CPU0 provides full order
+ * against the UNLOCK rq(0)->lock from CPU1. Furthermore our load of cond cannot
+ * happen before this same LOCK.
+ *
+ * Therefore, again, we're good.
+ */
+
 /**
  * try_to_wake_up - wake up a thread
  * @p: the thread to be awakened
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

author maintainer
#6 lore raw

Re: [PATCH 2/4] sched: Document Program-Order guarantees

Quoted 19 lines · Paul Turner

I suspect this part might be more explicitly expressed by specifying the requirements that migration satisfies; then providing an example. This makes it easier for others to reason about the locks and saves worrying about whether the examples hit our 3 million sub-cases.

I'd also propose just dropping preemption from this part, we only need memory order to be correct on migration, whether it's scheduled or not [it also invites confusion with the wake-up case].

Something like:
When any task 't' migrates, all activity on its prior cpu [c1] is guaranteed to be happens-before any subsequent execution on its new cpu [c2]. There are 3 components to enforcing this.

[c1] 1) Sched-out of t requires rq(c1)->lock
[any cpu] 2) Any migration of t, by any cpu is required to synchronize on *both* rq(c1)->lock and rq(c2)->lock
[c2] 3) Sched-in of t requires cq(c2)->lock

Quoted 5 lines

Transitivity guarantees that (2) orders after (1) and (3) after (2). Note that in some cases (e.g. active, or idle cpu) the balancing cpu in (2) may be c1 or c2.

[Follow example]

Make sense, I'll try and reword things like that.

Note that in don't actually need the strong transitivity here (RCsc), weak transitivity (RCpc) is in fact sufficient.

#7 lore raw

Re: [PATCH 2/4] sched: Document Program-Order guarantees

Quoted 24 lines · Peter Zijlstra
Quoted 23 lines · Paul Turner

I suspect this part might be more explicitly expressed by specifying the requirements that migration satisfies; then providing an example. This makes it easier for others to reason about the locks and saves worrying about whether the examples hit our 3 million sub-cases.

I'd also propose just dropping preemption from this part, we only need memory order to be correct on migration, whether it's scheduled or not [it also invites confusion with the wake-up case].

Something like:
When any task 't' migrates, all activity on its prior cpu [c1] is guaranteed to be happens-before any subsequent execution on its new cpu [c2]. There are 3 components to enforcing this.

[c1] 1) Sched-out of t requires rq(c1)->lock
[any cpu] 2) Any migration of t, by any cpu is required to synchronize on *both* rq(c1)->lock and rq(c2)->lock
[c2] 3) Sched-in of t requires cq(c2)->lock

Transitivity guarantees that (2) orders after (1) and (3) after (2). Note that in some cases (e.g. active, or idle cpu) the balancing cpu in (2) may be c1 or c2.

Quoted 6 lines
Quoted 1 line

[Follow example]

Make sense, I'll try and reword things like that.

Note that in don't actually need the strong transitivity here (RCsc), weak transitivity (RCpc) is in fact sufficient.

Yeah, I thought about just using acquire/release to talk about the interplay, in particular with the release in (1) in release and acquire from (3) which would make some of this much more explicit and highlight that we only need RCpc. We have not been very consistent at using this terminology, although this could be a good starting point.

If we went this route, we could do something like:

+ * So in this case the scheduler does not provide an obvious full barrier; but
+ * the smp_store_release() in finish_lock_switch(), paired with the control-dep
+ * and smp_rmb() in try_to_wake_up() form a release-acquire pair and fully
+ * order things between CPU0 and CPU1.

Instead of having this, which is complete, but hard to synchronize with the points at which it actually matters. Just use acquire and release above, then at the actual site, e.g. in try_to_wake_up() document how we deliver the acquire required by the higher level documentation/requirements.

This makes it easier to maintain the stupidly racy documentation consistency property in the future.

author maintainer
#8 lore raw

Re: [PATCH 2/4] sched: Document Program-Order guarantees

Quoted 7 lines · Paul Turner

If we went this route, we could do something like:

+ * So in this case the scheduler does not provide an obvious full barrier; but
+ * the smp_store_release() in finish_lock_switch(), paired with the control-dep
+ * and smp_rmb() in try_to_wake_up() form a release-acquire pair and fully
+ * order things between CPU0 and CPU1.

Quoted 5 lines

Instead of having this, which is complete, but hard to synchronize with the points at which it actually matters. Just use acquire and release above, then at the actual site, e.g. in try_to_wake_up() document how we deliver the acquire required by the higher level documentation/requirements.

Right, which was most of the point of trying to introduce smp_cond_acquire(), abstract out the tricky cond-dep and rmb trickery so we can indeed talk about release+acquire like normal people ;-)

author maintainer
#9 lore raw

Re: [PATCH 2/4] sched: Document Program-Order guarantees

In reply to Paul Turner
Quoted 4 lines · Paul Turner

I suspect this part might be more explicitly expressed by specifying the requirements that migration satisfies; then providing an example. This makes it easier for others to reason about the locks and saves worrying about whether the examples hit our 3 million sub-cases.

Something like so then? Note that this patch (obviously) comes after introducing smp_cond_acquire(), simplifying the RELEASE/ACQUIRE on p->on_cpu.

---
Subject: sched: Document Program-Order guarantees
From: Peter Zijlstra <[email protected]>
Date: Tue Nov 17 19:01:11 CET 2015

These are some notes on the scheduler locking and how it provides program order guarantees on SMP systems.

Cc "Paul E. McKenney" <[email protected]>
Cc Jonathan Corbet <[email protected]>
Cc Michal Hocko <[email protected]>
Cc David Howells <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Will Deacon <[email protected]>
Cc Oleg Nesterov <[email protected]>
Cc Boqun Feng <[email protected]>
---
 kernel/sched/core.c |   91 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 91 insertions(+)
kernel/sched/core.c +91 -0
@@ -1916,6 +1916,97 @@ static void ttwu_queue(struct task_struc
 	raw_spin_unlock(&rq->lock);
 }
 
+/*
+ * Notes on Program-Order guarantees on SMP systems.
+ *
+ *  MIGRATION
+ *
+ * The basic program-order guarantee on SMP systems is that when a task [t]
+ * migrates, all its activity on its old cpu [c0] happens-before any subsequent
+ * execution on its new cpu [c1].
+ *
+ * For migration (of runnable tasks) this is provided by the following means:
+ *
+ *  A) UNLOCK of the rq(c0)->lock scheduling out task t
+ *  B) migration for t is required to synchronize *both* rq(c0)->lock and
+ *     rq(c1)->lock (if not at the same time, then in that order).
+ *  C) LOCK of the rq(c1)->lock scheduling in task
+ *
+ * Transitivity guarantees that B happens after A and C after B.
+ * Note: we only require RCpc transitivity.
+ * Note: the cpu doing B need not be c0 or c1
+ *
+ * Example:
+ *
+ *   CPU0            CPU1            CPU2
+ *
+ *   LOCK rq(0)->lock
+ *   sched-out X
+ *   sched-in Y
+ *   UNLOCK rq(0)->lock
+ *
+ *                                   LOCK rq(0)->lock // orders against CPU0
+ *                                   dequeue X
+ *                                   UNLOCK rq(0)->lock
+ *
+ *                                   LOCK rq(1)->lock
+ *                                   enqueue X
+ *                                   UNLOCK rq(1)->lock
+ *
+ *                   LOCK rq(1)->lock // orders against CPU2
+ *                   sched-out Z
+ *                   sched-in X
+ *                   UNLOCK rq(1)->lock
+ *
+ *
+ *  BLOCKING -- aka. SLEEP + WAKEUP
+ *
+ * For blocking we (obviously) need to provide the same guarantee as for
+ * migration. However the means are completely different as there is no lock
+ * chain to provide order. Instead we do:
+ *
+ *   1) smp_store_release(X->on_cpu, 0)
+ *   2) smp_cond_acquire(!X->on_cpu)
+ *
+ * Example:
+ *
+ *   CPU0 (schedule)  CPU1 (try_to_wake_up) CPU2 (schedule)
+ *
+ *   LOCK rq(0)->lock LOCK X->pi_lock
+ *   dequeue X
+ *   sched-out X
+ *   smp_store_release(X->on_cpu, 0);
+ *
+ *                    smp_cond_acquire(!X->on_cpu);
+ *                    X->state = WAKING
+ *                    set_task_cpu(X,2)
+ *
+ *                    LOCK rq(2)->lock
+ *                    enqueue X
+ *                    X->state = RUNNING
+ *                    UNLOCK rq(2)->lock
+ *
+ *                                          LOCK rq(2)->lock // orders against CPU1
+ *                                          sched-out Z
+ *                                          sched-in X
+ *                                          UNLOCK rq(1)->lock
+ *
+ *                    UNLOCK X->pi_lock
+ *   UNLOCK rq(0)->lock
+ *
+ *
+ * However; for wakeups there is a second guarantee we must provide, namely we
+ * must observe the state that lead to our wakeup. That is, not only must our
+ * task observe its own prior state, it must also observe the stores prior to
+ * its wakeup.
+ *
+ * This means that any means of doing remote wakeups must order the CPU doing
+ * the wakeup against the CPU the task is going to end up running on. This,
+ * however, is already required for the regular Program-Order guarantee above,
+ * since the waking CPU is the one issueing the ACQUIRE (2).
+ *
+ */
+
 /**
  * try_to_wake_up - wake up a thread
  * @p: the thread to be awakened
#10 lore raw

Re: [PATCH 2/4] sched: Document Program-Order guarantees

Hi Peter,

On Fri, Nov 20, 2015 at 11:02:30AM +0100, Peter Zijlstra wrote:
[snip]

Quoted 31 lines

+ * BLOCKING -- aka. SLEEP + WAKEUP
+ *
+ * For blocking we (obviously) need to provide the same guarantee as for
+ * migration. However the means are completely different as there is no lock
+ * chain to provide order. Instead we do:
+ *
+ * 1) smp_store_release(X->on_cpu, 0)
+ * 2) smp_cond_acquire(!X->on_cpu)
+ *
+ * Example:
+ *
+ * CPU0 (schedule) CPU1 (try_to_wake_up) CPU2 (schedule)
+ *

+ *   LOCK rq(0)->lock LOCK X->pi_lock
+ *   dequeue X
+ *   sched-out X
+ *   smp_store_release(X->on_cpu, 0);
+ *
+ *                    smp_cond_acquire(!X->on_cpu);
+ *                    X->state = WAKING
+ *                    set_task_cpu(X,2)
+ *
+ *                    LOCK rq(2)->lock
+ *                    enqueue X
+ *                    X->state = RUNNING
+ *                    UNLOCK rq(2)->lock
+ *
+ *                                          LOCK rq(2)->lock // orders against CPU1
+ *                                          sched-out Z
+ *                                          sched-in X
+ *                                          UNLOCK rq(1)->lock
Quoted 15 lines

+ *
+ * UNLOCK X->pi_lock
+ * UNLOCK rq(0)->lock
+ *
+ *
+ * However; for wakeups there is a second guarantee we must provide, namely we
+ * must observe the state that lead to our wakeup. That is, not only must our
+ * task observe its own prior state, it must also observe the stores prior to
+ * its wakeup.
+ *
+ * This means that any means of doing remote wakeups must order the CPU doing
+ * the wakeup against the CPU the task is going to end up running on. This,
+ * however, is already required for the regular Program-Order guarantee above,
+ * since the waking CPU is the one issueing the ACQUIRE (2).
+ *

Hope I'm the only one who got confused about the "2" in "ACQUIRE (2)", what does that refer? "2) smp_cond_acquire(!X->on_cpu)"?

The comments are great, just try to understand your meaning here ;-)

Regards,
Boqun

Quoted 5 lines

+ */
+
/**
* try_to_wake_up - wake up a thread
* @p: the thread to be awakened

author maintainer
#11 lore raw

Re: [PATCH 2/4] sched: Document Program-Order guarantees

Quoted 51 lines · Boqun Feng

Hi Peter,

On Fri, Nov 20, 2015 at 11:02:30AM +0100, Peter Zijlstra wrote:
[snip]

Quoted 31 lines

+ * BLOCKING -- aka. SLEEP + WAKEUP
+ *
+ * For blocking we (obviously) need to provide the same guarantee as for
+ * migration. However the means are completely different as there is no lock
+ * chain to provide order. Instead we do:
+ *
+ * 1) smp_store_release(X->on_cpu, 0)
+ * 2) smp_cond_acquire(!X->on_cpu)
+ *
+ * Example:
+ *
+ * CPU0 (schedule) CPU1 (try_to_wake_up) CPU2 (schedule)
+ *

+ *   LOCK rq(0)->lock LOCK X->pi_lock
+ *   dequeue X
+ *   sched-out X
+ *   smp_store_release(X->on_cpu, 0);
+ *
+ *                    smp_cond_acquire(!X->on_cpu);
+ *                    X->state = WAKING
+ *                    set_task_cpu(X,2)
+ *
+ *                    LOCK rq(2)->lock
+ *                    enqueue X
+ *                    X->state = RUNNING
+ *                    UNLOCK rq(2)->lock
+ *
+ *                                          LOCK rq(2)->lock // orders against CPU1
+ *                                          sched-out Z
+ *                                          sched-in X
+ *                                          UNLOCK rq(1)->lock
Quoted 15 lines

+ *
+ * UNLOCK X->pi_lock
+ * UNLOCK rq(0)->lock
+ *
+ *
+ * However; for wakeups there is a second guarantee we must provide, namely we
+ * must observe the state that lead to our wakeup. That is, not only must our
+ * task observe its own prior state, it must also observe the stores prior to
+ * its wakeup.
+ *
+ * This means that any means of doing remote wakeups must order the CPU doing
+ * the wakeup against the CPU the task is going to end up running on. This,
+ * however, is already required for the regular Program-Order guarantee above,
+ * since the waking CPU is the one issueing the ACQUIRE (2).
+ *

Quoted 2 lines

Hope I'm the only one who got confused about the "2" in "ACQUIRE (2)", what does that refer? "2) smp_cond_acquire(!X->on_cpu)"?

Yes, exactly that. Would an unadorned 2 be clearer?

#12 lore raw

Re: [PATCH 2/4] sched: Document Program-Order guarantees

Quoted 52 lines · Peter Zijlstra
Quoted 51 lines · Boqun Feng

Hi Peter,

On Fri, Nov 20, 2015 at 11:02:30AM +0100, Peter Zijlstra wrote:
[snip]

Quoted 46 lines

+ * BLOCKING -- aka. SLEEP + WAKEUP
+ *
+ * For blocking we (obviously) need to provide the same guarantee as for
+ * migration. However the means are completely different as there is no lock
+ * chain to provide order. Instead we do:
+ *
+ * 1) smp_store_release(X->on_cpu, 0)
+ * 2) smp_cond_acquire(!X->on_cpu)
+ *
+ * Example:
+ *
+ * CPU0 (schedule) CPU1 (try_to_wake_up) CPU2 (schedule)
+ *

+ *   LOCK rq(0)->lock LOCK X->pi_lock
+ *   dequeue X
+ *   sched-out X
+ *   smp_store_release(X->on_cpu, 0);
+ *
+ *                    smp_cond_acquire(!X->on_cpu);
+ *                    X->state = WAKING
+ *                    set_task_cpu(X,2)
+ *
+ *                    LOCK rq(2)->lock
+ *                    enqueue X
+ *                    X->state = RUNNING
+ *                    UNLOCK rq(2)->lock
+ *
+ *                                          LOCK rq(2)->lock // orders against CPU1
+ *                                          sched-out Z
+ *                                          sched-in X
+ *                                          UNLOCK rq(1)->lock

+ *
+ * UNLOCK X->pi_lock
+ * UNLOCK rq(0)->lock
+ *
+ *
+ * However; for wakeups there is a second guarantee we must provide, namely we
+ * must observe the state that lead to our wakeup. That is, not only must our
+ * task observe its own prior state, it must also observe the stores prior to
+ * its wakeup.
+ *
+ * This means that any means of doing remote wakeups must order the CPU doing
+ * the wakeup against the CPU the task is going to end up running on. This,
+ * however, is already required for the regular Program-Order guarantee above,
+ * since the waking CPU is the one issueing the ACQUIRE (2).
+ *

Quoted 4 lines
Quoted 2 lines

Hope I'm the only one who got confused about the "2" in "ACQUIRE (2)", what does that refer? "2) smp_cond_acquire(!X->on_cpu)"?

Yes, exactly that. Would an unadorned 2 be clearer?

How about "the one issueing the ACQUIRE (smp_cond_acquire)"?

author maintainer
#13 lore raw

Re: [PATCH 2/4] sched: Document Program-Order guarantees

Quoted 3 lines · Boqun Feng
Quoted 1 line

Yes, exactly that. Would an unadorned 2 be clearer?

How about "the one issueing the ACQUIRE (smp_cond_acquire)"?

Sure, that works. Thanks

author maintainer
#14 lore raw

PATCH 3/4 sched: Fix a race in try_to_wake_up() vs schedule()

In reply to Peter Zijlstra

Oleg noticed that its possible to falsely observe p->on_cpu == 0 such that we'll prematurely continue with the wakeup and effectively run p on two CPUs at the same time.

Even though the overlap is very limited; the task is in the middle of being scheduled out; it could still result in corruption of the scheduler data structures.

        CPU0                            CPU1

        set_current_state(...)

        <preempt_schedule>
          context_switch(X, Y)
            prepare_lock_switch(Y)
              Y->on_cpu = 1;
            finish_lock_switch(X)
              store_release(X->on_cpu, 0);

                                        try_to_wake_up(X)
                                          LOCK(p->pi_lock);

                                          t = X->on_cpu; // 0

          context_switch(Y, X)
            prepare_lock_switch(X)
              X->on_cpu = 1;
            finish_lock_switch(Y)
              store_release(Y->on_cpu, 0);
        </preempt_schedule>

        schedule();
          deactivate_task(X);
          X->on_rq = 0;

                                          if (X->on_rq) // false

                                          if (t) while (X->on_cpu)
                                            cpu_relax();

          context_switch(X, ..)
            finish_lock_switch(X)
              store_release(X->on_cpu, 0);

Avoid the load of X->on_cpu being hoisted over the X->on_rq load.

---
 kernel/sched/core.c |   19 +++++++++++++++++++
 1 file changed, 19 insertions(+)
kernel/sched/core.c +19 -0
@@ -2084,6 +2084,25 @@ try_to_wake_up(struct task_struct *p, un
 
 #ifdef CONFIG_SMP
 	/*
+	 * Ensure we load p->on_cpu _after_ p->on_rq, otherwise it would be
+	 * possible to, falsely, observe p->on_cpu == 0.
+	 *
+	 * One must be running (->on_cpu == 1) in order to remove oneself
+	 * from the runqueue.
+	 *
+	 *  [S] ->on_cpu = 1;	[L] ->on_rq
+	 *      UNLOCK rq->lock
+	 *			RMB
+	 *      LOCK   rq->lock
+	 *  [S] ->on_rq = 0;    [L] ->on_cpu
+	 *
+	 * Pairs with the full barrier implied in the UNLOCK+LOCK on rq->lock
+	 * from the consecutive calls to schedule(); the first switching to our
+	 * task, the second putting it to sleep.
+	 */
+	smp_rmb();
+
+	/*
 	 * If the owning (remote) cpu is still in the middle of schedule() with
 	 * this task as prev, wait until its done referencing the task.
 	 */
author maintainer
#15 lore raw

PATCH 4/4 locking: Introduce smp_cond_acquire()

In reply to Peter Zijlstra

Introduce smp_cond_acquire() which combines a control dependency and a read barrier to form acquire semantics.

This primitive has two benefits:
- it documents control dependencies,
- its typically cheaper than using smp_load_acquire() in a loop.

Note that while smp_cond_acquire() has an explicit smp_read_barrier_depends() for Alpha, neither sites it gets used in were actually buggy on Alpha for their lack of it. The first uses smp_rmb(), which on Alpha is a full barrier too and therefore serves its purpose. The second had an explicit full barrier.

---
 include/linux/compiler.h |   18 ++++++++++++++++++
 kernel/sched/core.c      |    8 +-------
 kernel/task_work.c       |    4 ++--
 3 files changed, 21 insertions(+), 9 deletions(-)
include/linux/compiler.h +18 -0
@@ -275,6 +275,24 @@ static __always_inline void __write_once
 	__val; \
 })
 
+/**
+ * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering
+ * @cond: boolean expression to wait for
+ *
+ * Equivalent to using smp_load_acquire() on the condition variable but employs
+ * the control dependency of the wait to reduce the barrier on many platforms.
+ *
+ * The control dependency provides a LOAD->STORE order, the additional RMB
+ * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
+ * aka. ACQUIRE.
+ */
+#define smp_cond_acquire(cond)	do {		\
+	while (!(cond))				\
+		cpu_relax();			\
+	smp_read_barrier_depends(); /* ctrl */	\
+	smp_rmb(); /* ctrl + rmb := acquire */	\
+} while (0)
+
 #endif /* __KERNEL__ */
 
 #endif /* __ASSEMBLY__ */
kernel/sched/core.c +1 -7
@@ -2111,19 +2111,13 @@ try_to_wake_up(struct task_struct *p, un
 	/*
 	 * If the owning (remote) cpu is still in the middle of schedule() with
 	 * this task as prev, wait until its done referencing the task.
-	 */
-	while (p->on_cpu)
-		cpu_relax();
-	/*
-	 * Combined with the control dependency above, we have an effective
-	 * smp_load_acquire() without the need for full barriers.
 	 *
 	 * Pairs with the smp_store_release() in finish_lock_switch().
 	 *
 	 * This ensures that tasks getting woken will be fully ordered against
 	 * their previous state and preserve Program Order.
 	 */
-	smp_rmb();
+	smp_cond_acquire(!p->on_cpu);
 
 	p->sched_contributes_to_load = !!task_contributes_to_load(p);
 	p->state = TASK_WAKING;
kernel/task_work.c +2 -2
@@ -102,13 +102,13 @@ void task_work_run(void)
 
 		if (!work)
 			break;
+
 		/*
 		 * Synchronize with task_work_cancel(). It can't remove
 		 * the first entry == work, cmpxchg(task_works) should
 		 * fail, but it can play with *work and other entries.
 		 */
-		raw_spin_unlock_wait(&task->pi_lock);
-		smp_mb();
+		smp_cond_acquire(!raw_spin_is_locked(&task->pi_lock));
 
 		do {
 			next = work->next;
author maintainer
#16 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 13 lines · Peter Zijlstra

Note that while smp_cond_acquire() has an explicit smp_read_barrier_depends() for Alpha, neither sites it gets used in were actually buggy on Alpha for their lack of it. The first uses smp_rmb(), which on Alpha is a full barrier too and therefore serves its purpose. The second had an explicit full barrier.

include/linux/compiler.h +7 -0
+/**
+ * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering
+ * @cond: boolean expression to wait for
+ *
+ * Equivalent to using smp_load_acquire() on the condition variable but employs
+ * the control dependency of the wait to reduce the barrier on many platforms.
+ *

include/linux/compiler.h static __always_inline void __write_once · line 294

Quoted 10 lines
include/linux/compiler.h +10 -0
+ * The control dependency provides a LOAD->STORE order, the additional RMB
+ * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
+ * aka. ACQUIRE.
+ */
+#define smp_cond_acquire(cond)	do {		\
+	while (!(cond))				\
+		cpu_relax();			\
+	smp_read_barrier_depends(); /* ctrl */	\
+	smp_rmb(); /* ctrl + rmb := acquire */	\
+} while (0)

So per the above argument we could leave out the smp_read_barrier_depends() for Alpha, although that would break consistency with all the other control dependency primitives we have. It would avoid issuing a double barrier.

Thoughts?

#17 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 31 lines · Peter Zijlstra
Quoted 13 lines · Peter Zijlstra

Note that while smp_cond_acquire() has an explicit smp_read_barrier_depends() for Alpha, neither sites it gets used in were actually buggy on Alpha for their lack of it. The first uses smp_rmb(), which on Alpha is a full barrier too and therefore serves its purpose. The second had an explicit full barrier.

include/linux/compiler.h +7 -0
+/**
+ * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering
+ * @cond: boolean expression to wait for
+ *
+ * Equivalent to using smp_load_acquire() on the condition variable but employs
+ * the control dependency of the wait to reduce the barrier on many platforms.
+ *

include/linux/compiler.h static __always_inline void __write_once · line 294

Quoted 10 lines
include/linux/compiler.h +10 -0
+ * The control dependency provides a LOAD->STORE order, the additional RMB
+ * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
+ * aka. ACQUIRE.
+ */
+#define smp_cond_acquire(cond)	do {		\
+	while (!(cond))				\
+		cpu_relax();			\
+	smp_read_barrier_depends(); /* ctrl */	\
+	smp_rmb(); /* ctrl + rmb := acquire */	\
+} while (0)

So per the above argument we could leave out the smp_read_barrier_depends() for Alpha, although that would break consistency with all the other control dependency primitives we have. It would avoid issuing a double barrier.

Quoted 1 line

Thoughts?

Do we even know that Alpha needs a barrier for control-dependencies in the first place?

Will

#18 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 32 lines · Will Deacon
Quoted 31 lines · Peter Zijlstra
Quoted 13 lines · Peter Zijlstra

Note that while smp_cond_acquire() has an explicit smp_read_barrier_depends() for Alpha, neither sites it gets used in were actually buggy on Alpha for their lack of it. The first uses smp_rmb(), which on Alpha is a full barrier too and therefore serves its purpose. The second had an explicit full barrier.

include/linux/compiler.h +7 -0
+/**
+ * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering
+ * @cond: boolean expression to wait for
+ *
+ * Equivalent to using smp_load_acquire() on the condition variable but employs
+ * the control dependency of the wait to reduce the barrier on many platforms.
+ *

include/linux/compiler.h static __always_inline void __write_once · line 294

Quoted 10 lines
include/linux/compiler.h +10 -0
+ * The control dependency provides a LOAD->STORE order, the additional RMB
+ * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
+ * aka. ACQUIRE.
+ */
+#define smp_cond_acquire(cond)	do {		\
+	while (!(cond))				\
+		cpu_relax();			\
+	smp_read_barrier_depends(); /* ctrl */	\
+	smp_rmb(); /* ctrl + rmb := acquire */	\
+} while (0)

So per the above argument we could leave out the smp_read_barrier_depends() for Alpha, although that would break consistency with all the other control dependency primitives we have. It would avoid issuing a double barrier.

Quoted 4 lines
Quoted 1 line

Thoughts?

Do we even know that Alpha needs a barrier for control-dependencies in the first place?

You would ask that question when I am many thousands of miles from my copy of the Alpha reference manual! ;-)

There is explicit wording in that manual that says that no multi-variable ordering is implied without explicit memory-barrier instructions.

Thanx, Paul

#19 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 3 lines · Paul E. McKenney

You would ask that question when I am many thousands of miles from my copy of the Alpha reference manual! ;-)

I don't think I've touched a paper manual in years. Too m uch effort to index and search. Look here

http://download.majix.org/dec/alpha_arch_ref.pdf

Quoted 2 lines

There is explicit wording in that manual that says that no multi-variable ordering is implied without explicit memory-barrier instructions.

Right. But the whole "read -> conditional -> write" ends up being a dependency chain to *every* single write that happens after the conditional.

So there may be no "multi-variable ordering" implied in any individual access, but despite that a simple "read + conditional" orders every single store that comes after it. Even if it orders them "individually".

Linus

#20 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Peter Zijlstra

Hi Peter,

Quoted 6 lines · Peter Zijlstra

Introduce smp_cond_acquire() which combines a control dependency and a read barrier to form acquire semantics.

This primitive has two benefits:
- it documents control dependencies,
- its typically cheaper than using smp_load_acquire() in a loop.

I'm not sure that's necessarily true on arm64, where we have a native load-acquire instruction, but not a READ -> READ barrier (smp_rmb() orders prior loads against subsequent loads and stores for us).

Perhaps we could allow architectures to provide their own definition of smp_cond_acquire in case they can implement it more efficiently?

Quoted 21 lines

Note that while smp_cond_acquire() has an explicit smp_read_barrier_depends() for Alpha, neither sites it gets used in were actually buggy on Alpha for their lack of it. The first uses smp_rmb(), which on Alpha is a full barrier too and therefore serves its purpose. The second had an explicit full barrier.

---
 include/linux/compiler.h |   18 ++++++++++++++++++
 kernel/sched/core.c      |    8 +-------
 kernel/task_work.c       |    4 ++--
 3 files changed, 21 insertions(+), 9 deletions(-)
include/linux/compiler.h +2 -0
@@ -275,6 +275,24 @@ static __always_inline void __write_once
 	__val; \
 })
 
+/**
+ * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering

include/linux/compiler.h static __always_inline void __write_once · line 289

Quoted 10 lines
include/linux/compiler.h +10 -0
+ * @cond: boolean expression to wait for
+ *
+ * Equivalent to using smp_load_acquire() on the condition variable but employs
+ * the control dependency of the wait to reduce the barrier on many platforms.
+ *
+ * The control dependency provides a LOAD->STORE order, the additional RMB
+ * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
+ * aka. ACQUIRE.
+ */
+#define smp_cond_acquire(cond)	do {		\

I think the previous version that you posted/discussed had the actual address of the variable being loaded passed in here too? That would be useful for arm64, where we can wait-until-memory-location-has-changed to save us re-evaluating cond prematurely.

include/linux/compiler.h static __always_inline void __write_once · line 293

Quoted 4 lines
include/linux/compiler.h +4 -0
+	while (!(cond))				\
+		cpu_relax();			\
+	smp_read_barrier_depends(); /* ctrl */	\
+	smp_rmb(); /* ctrl + rmb := acquire */	\

It's actually stronger than acquire, I think, because accesses before the smp_cond_acquire cannot be moved across it.

Quoted 33 lines
include/linux/compiler.h +2 -0
+} while (0)
+
 #endif /* __KERNEL__ */
 
 #endif /* __ASSEMBLY__ */
kernel/sched/core.c +1 -7
@@ -2111,19 +2111,13 @@ try_to_wake_up(struct task_struct *p, un
 	/*
 	 * If the owning (remote) cpu is still in the middle of schedule() with
 	 * this task as prev, wait until its done referencing the task.
-	 */
-	while (p->on_cpu)
-		cpu_relax();
-	/*
-	 * Combined with the control dependency above, we have an effective
-	 * smp_load_acquire() without the need for full barriers.
 	 *
 	 * Pairs with the smp_store_release() in finish_lock_switch().
 	 *
 	 * This ensures that tasks getting woken will be fully ordered against
 	 * their previous state and preserve Program Order.
 	 */
-	smp_rmb();
+	smp_cond_acquire(!p->on_cpu);
 
 	p->sched_contributes_to_load = !!task_contributes_to_load(p);
 	p->state = TASK_WAKING;
kernel/task_work.c +0 -0
@@ -102,13 +102,13 @@ void task_work_run(void)
 
 		if (!work)

kernel/task_work.c void task_work_run(void) · line 111

Quoted 10 lines
kernel/task_work.c +2 -2
 			break;
+
 		/*
 		 * Synchronize with task_work_cancel(). It can't remove
 		 * the first entry == work, cmpxchg(task_works) should
 		 * fail, but it can play with *work and other entries.
 		 */
-		raw_spin_unlock_wait(&task->pi_lock);
-		smp_mb();
+		smp_cond_acquire(!raw_spin_is_locked(&task->pi_lock));

Hmm, there's some sort of release equivalent in kernel/exit.c, but I couldn't easily figure out whether we could do anything there. If we could, we could kill raw_spin_unlock_wait :)

Will

#21 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Peter Zijlstra

include/linux/compiler.h static __always_inline void __write_once · line 294

Quoted 6 lines · Peter Zijlstra
include/linux/compiler.h +6 -0
+#define smp_cond_acquire(cond) do {            \
+       while (!(cond))                         \
+               cpu_relax();                    \
+       smp_read_barrier_depends(); /* ctrl */  \
+       smp_rmb(); /* ctrl + rmb := acquire */  \
+} while (0)

This code makes absolutely no sense.

smp_read_barrier_depends() is about a memory barrier where there is a data dependency between two accesses. The "depends" is very much about the data dependency, and very much about *nothing* else.

Your comment talks about control dependencies, but smp_read_barrier_depends() has absolutely nothing to do with a control dependency. In fact, it is explicitly a no-op on architectures like ARM and PowerPC that violate control dependencies.

So the code may end up *working*, but the comments in it are misleading, insane, and nonsensical. And I think the code is actively wrong (although in the sense that it has a barrier too *many*, not lacking one).

Because smp_read_barrier_depends() definitely has *nothing* to do with control barriers in any way, shape or form. The comment is actively and entirely wrong.

As far as I know, even on alpha that 'smp_read_barrier_depends()' is unnecessary. Not because of any barrier semantics (whether smp_read_barrier depends or any other barrier), but simply because a store cannot finalize before the conditional has been resolved, which means that the read must have been done.

So for alpha, you end up depending on the exact same logic that you depend on for every other architecture, since there is no "architectural" memory ordering guarantee of it anywhere else either (ok, so x86 has the explicit "memory ordering is causal" guarantee, so x86 does kind of make that conditional ordering explicit).

Adding that "smp_read_barrier_depends()" doesn't add anything to the whole ctrl argument.

So the code looks insane to me. On everything but alpha, "smp_read_barrier_depends()" is a no-op. And on alpha, a combination of "smp_read_barrier_depends()" and "smp_rmb()" is nonsensical. So in no case can that code make sense, as far as I can tell.

Linus

#22 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 10 lines · Linus Torvalds

include/linux/compiler.h static __always_inline void __write_once · line 294

Quoted 6 lines · Peter Zijlstra
include/linux/compiler.h +6 -0
+#define smp_cond_acquire(cond) do {            \
+       while (!(cond))                         \
+               cpu_relax();                    \
+       smp_read_barrier_depends(); /* ctrl */  \
+       smp_rmb(); /* ctrl + rmb := acquire */  \
+} while (0)

This code makes absolutely no sense.

Quoted 3 lines

smp_read_barrier_depends() is about a memory barrier where there is a data dependency between two accesses. The "depends" is very much about the data dependency, and very much about *nothing* else.

Paul wasn't so sure, which I think is why smp_read_barrier_depends() is already used in, for example, READ_ONCE_CTRL:

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

although I agree that this would pave the way for speculative stores on Alpha and that seems like a heavy accusation to make.

Quoted 4 lines

Your comment talks about control dependencies, but smp_read_barrier_depends() has absolutely nothing to do with a control dependency. In fact, it is explicitly a no-op on architectures like ARM and PowerPC that violate control dependencies.

In this case, control dependencies are only referring to READ -> WRITE ordering, so they are honoured by ARM and PowerPC.

Will

#23 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 11 lines · Will Deacon
Quoted 10 lines · Linus Torvalds

include/linux/compiler.h static __always_inline void __write_once · line 294

Quoted 6 lines · Peter Zijlstra
include/linux/compiler.h +6 -0
+#define smp_cond_acquire(cond) do {            \
+       while (!(cond))                         \
+               cpu_relax();                    \
+       smp_read_barrier_depends(); /* ctrl */  \
+       smp_rmb(); /* ctrl + rmb := acquire */  \
+} while (0)

This code makes absolutely no sense.

Quoted 8 lines
Quoted 3 lines

smp_read_barrier_depends() is about a memory barrier where there is a data dependency between two accesses. The "depends" is very much about the data dependency, and very much about *nothing* else.

Paul wasn't so sure, which I think is why smp_read_barrier_depends() is already used in, for example, READ_ONCE_CTRL:

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

Quoting the alpha architecture manual is kind of pointless, when NO OTHER ARCHITECTURE OUT THERE guararantees that whole "read + conditional orders wrt subsequent writes" _either_.

(Again, with the exception of x86, which has the sane "we honor causality")

Alpha isn't special. And smp_read_barrier_depends() hasn't magically become something new.

If people think that control dependency needs a memory barrier on alpha, then it damn well needs on on all other weakly ordered architectuers too, afaik.

Either that "you cannot finalize a write unless all conditionals it depends on are finalized" is true or it is not. That argument has *never* been about some architecture-specific memory ordering model, as far as I know.

As to READ_ONCE_CTRL - two wrongs don't make a right.

That smp_read_barrier_depends() there doesn't make any sense either.

And finally, the alpha architecture manual actually does have the notion of "Dependence Constraint" (5.6.1.7) that talks about writes that depend on previous reads (where "depends" is explicitly spelled out to be about conditionals, write data _or_ write address). They are actually constrained on alpha too.

Note that a "Dependence Constraint" is not a memory barrier, because it only affects that particular chain of dependencies. So it doesn't order other things in *general*, but it does order a particular read with a particular sef of subsequent write. Which is all we guarantee on anything else too wrt the whole control dependencies.

The smp_read_barrier_depends() is a *READ BARRIER*. It's about a *read* that depends on a previous read. Now, it so happens that alpha doesn't have a "read-to-read" barrier, and it's implemented as a full barrier, but it really should be read as a "smp_rmb().

Yes, yes, alpha has the worst memory ordering ever, and the worst barriers for that insane memory ordering, but that still does not make alpha "magically able to reorder more than physically or logically possible". We don't add barriers that don't make sense just because the alpha memory orderings are insane.

Paul? I really disagree with how you have totally tried to re-purpose smp_read_barrier_depends() in ways that are insane and make no sense. That is not a control dependency. If it was, then PPC and ARM would need to make it a real barrier too. I really don't see why you have singled out alpha as the victim of your "let's just randomly change the rules".

Quoted 2 lines

In this case, control dependencies are only referring to READ -> WRITE ordering, so they are honoured by ARM and PowerPC.

Do ARM and PPC actually guarantee the generic "previous reads always order before subsequent writes"?

Because if that's the issue, then we should perhaps add a new ordering primitive that says that (ie "smp_read_to_write_barrier()"). That could be a useful thing in general, where we currently use "smp_mb()" to order an earlier read with a later write.

Linus

#24 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 30 lines · Linus Torvalds
Quoted 11 lines · Will Deacon
Quoted 10 lines · Linus Torvalds

include/linux/compiler.h static __always_inline void __write_once · line 294

Quoted 6 lines · Peter Zijlstra
include/linux/compiler.h +6 -0
+#define smp_cond_acquire(cond) do {            \
+       while (!(cond))                         \
+               cpu_relax();                    \
+       smp_read_barrier_depends(); /* ctrl */  \
+       smp_rmb(); /* ctrl + rmb := acquire */  \
+} while (0)

This code makes absolutely no sense.

Quoted 8 lines
Quoted 3 lines

smp_read_barrier_depends() is about a memory barrier where there is a data dependency between two accesses. The "depends" is very much about the data dependency, and very much about *nothing* else.

Paul wasn't so sure, which I think is why smp_read_barrier_depends() is already used in, for example, READ_ONCE_CTRL:

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

Quoting the alpha architecture manual is kind of pointless, when NO OTHER ARCHITECTURE OUT THERE guararantees that whole "read + conditional orders wrt subsequent writes" _either_.

(Again, with the exception of x86, which has the sane "we honor causality")

Alpha isn't special. And smp_read_barrier_depends() hasn't magically become something new.

Quoted 8 lines

If people think that control dependency needs a memory barrier on alpha, then it damn well needs on on all other weakly ordered architectuers too, afaik.

Either that "you cannot finalize a write unless all conditionals it depends on are finalized" is true or it is not. That argument has *never* been about some architecture-specific memory ordering model, as far as I know.

You can imagine a (horribly broken) value-speculating architecture that would permit this re-ordering, but then you'd have speculative stores and thin-air values, which Alpha doesn't have.

Quoted 1 line

As to READ_ONCE_CTRL - two wrongs don't make a right.

Sure, I just wanted to point out the precedence and related discussion.

Quoted 7 lines

That smp_read_barrier_depends() there doesn't make any sense either.

And finally, the alpha architecture manual actually does have the notion of "Dependence Constraint" (5.6.1.7) that talks about writes that depend on previous reads (where "depends" is explicitly spelled out to be about conditionals, write data _or_ write address). They are actually constrained on alpha too.

In which case, it looks like we can remove the smp_read_barrier_depends instances from all of the control-dependency macros, but I'll defer to Paul in case he has some further insight. I assume you're ok with this patch if the smp_read_barrier_depends() is removed?

Quoted 5 lines
Quoted 2 lines

In this case, control dependencies are only referring to READ -> WRITE ordering, so they are honoured by ARM and PowerPC.

Do ARM and PPC actually guarantee the generic "previous reads always order before subsequent writes"?

Only to *dependent* subsequent writes, but Peter's patch makes all subsequent writes dependent on cond, so I think that's the right way to achieve the ordering we want.

Will

author maintainer
#25 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 22 lines · Will Deacon
Quoted 22 lines
Quoted 8 lines
Quoted 3 lines

smp_read_barrier_depends() is about a memory barrier where there is a data dependency between two accesses. The "depends" is very much about the data dependency, and very much about *nothing* else.

Paul wasn't so sure, which I think is why smp_read_barrier_depends() is already used in, for example, READ_ONCE_CTRL:

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

Quoting the alpha architecture manual is kind of pointless, when NO OTHER ARCHITECTURE OUT THERE guararantees that whole "read + conditional orders wrt subsequent writes" _either_.

(Again, with the exception of x86, which has the sane "we honor causality")

Alpha isn't special. And smp_read_barrier_depends() hasn't magically become something new.

If people think that control dependency needs a memory barrier on alpha, then it damn well needs on on all other weakly ordered architectuers too, afaik.

Quoted 8 lines
Quoted 4 lines

Either that "you cannot finalize a write unless all conditionals it depends on are finalized" is true or it is not. That argument has *never* been about some architecture-specific memory ordering model, as far as I know.

You can imagine a (horribly broken) value-speculating architecture that would permit this re-ordering, but then you'd have speculative stores and thin-air values, which Alpha doesn't have.

I've tried arguing this point with Paul on a number of occasions, and I think he at one point constructed some elaborate scheme that depended on the split cache where this might require the full barrier.

Quoted 3 lines
Quoted 1 line

As to READ_ONCE_CTRL - two wrongs don't make a right.

Sure, I just wanted to point out the precedence and related discussion.

I purely followed 'convention' here.

Quoted 8 lines
Quoted 7 lines

That smp_read_barrier_depends() there doesn't make any sense either.

And finally, the alpha architecture manual actually does have the notion of "Dependence Constraint" (5.6.1.7) that talks about writes that depend on previous reads (where "depends" is explicitly spelled out to be about conditionals, write data _or_ write address). They are actually constrained on alpha too.

Quoted 4 lines

In which case, it looks like we can remove the smp_read_barrier_depends instances from all of the control-dependency macros, but I'll defer to Paul in case he has some further insight. I assume you're ok with this patch if the smp_read_barrier_depends() is removed?

That would be good indeed.

author maintainer
#26 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Linus Torvalds
Quoted 10 lines · Linus Torvalds

As to READ_ONCE_CTRL - two wrongs don't make a right.

That smp_read_barrier_depends() there doesn't make any sense either.

And finally, the alpha architecture manual actually does have the notion of "Dependence Constraint" (5.6.1.7) that talks about writes that depend on previous reads (where "depends" is explicitly spelled out to be about conditionals, write data _or_ write address). They are actually constrained on alpha too.

Quoted 5 lines

Note that a "Dependence Constraint" is not a memory barrier, because it only affects that particular chain of dependencies. So it doesn't order other things in *general*, but it does order a particular read with a particular sef of subsequent write. Which is all we guarantee on anything else too wrt the whole control dependencies.

Something like so then, Paul?

---
Subject: locking: Alpha honours control dependencies too

The alpha architecture manual actually does have the notion of "Dependence Constraint" (5.6.1.7) that talks about writes that depend on previous reads (where "depends" is explicitly spelled out to be about conditionals, write data _or_ write address). They are actually constrained on alpha too.

Which means we can remove the smp_read_barrier_depends() abuse from the various control dependency primitives.

Retain the primitives, as they are a useful documentation aid.

---
 include/linux/atomic.h   | 2 --
 include/linux/compiler.h | 1 -
 2 files changed, 3 deletions(-)
include/linux/atomic.h +0 -2
index 27e580d232ca..f16b1dedd909 100644
@@ -8,7 +8,6 @@
 static inline int atomic_read_ctrl(const atomic_t *v)
 {
 	int val = atomic_read(v);
-	smp_read_barrier_depends(); /* Enforce control dependency. */
 	return val;
 }
 #endif
@@ -565,7 +564,6 @@ static inline int atomic_dec_if_positive(atomic_t *v)
 static inline long long atomic64_read_ctrl(const atomic64_t *v)
 {
 	long long val = atomic64_read(v);
-	smp_read_barrier_depends(); /* Enforce control dependency. */
 	return val;
 }
 #endif
include/linux/compiler.h +0 -1
index 3d7810341b57..1d1f5902189d 100644
@@ -311,7 +311,6 @@ static __always_inline void __write_once_size(volatile void *p, void *res, int s
 #define READ_ONCE_CTRL(x) \
 ({ \
 	typeof(x) __val = READ_ONCE(x); \
-	smp_read_barrier_depends(); /* Enforce control dependency. */ \
 	__val; \
 })
 
#27 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Linus Torvalds
Quoted 21 lines · Linus Torvalds
Quoted 11 lines · Will Deacon
Quoted 10 lines · Linus Torvalds

include/linux/compiler.h static __always_inline void __write_once · line 294

Quoted 6 lines · Peter Zijlstra
include/linux/compiler.h +6 -0
+#define smp_cond_acquire(cond) do {            \
+       while (!(cond))                         \
+               cpu_relax();                    \
+       smp_read_barrier_depends(); /* ctrl */  \
+       smp_rmb(); /* ctrl + rmb := acquire */  \
+} while (0)

This code makes absolutely no sense.

Quoted 8 lines
Quoted 3 lines

smp_read_barrier_depends() is about a memory barrier where there is a data dependency between two accesses. The "depends" is very much about the data dependency, and very much about *nothing* else.

Paul wasn't so sure, which I think is why smp_read_barrier_depends() is already used in, for example, READ_ONCE_CTRL:

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

Quoted 8 lines

Quoting the alpha architecture manual is kind of pointless, when NO OTHER ARCHITECTURE OUT THERE guararantees that whole "read + conditional orders wrt subsequent writes" _either_.

(Again, with the exception of x86, which has the sane "we honor causality")

Alpha isn't special. And smp_read_barrier_depends() hasn't magically become something new.

The existing control dependencies (READ_ONCE_CTRL() and friends) only guarantee ordering against later stores, and not against later loads. Of the weakly ordered architectures, only Alpha fails to respect load-to-store control dependencies.

Quoted 3 lines

If people think that control dependency needs a memory barrier on alpha, then it damn well needs on on all other weakly ordered architectuers too, afaik.

For load-to-load control dependencies, agreed, from what I can see, all the weakly ordered architectures do need an explicit barrier.

Quoted 7 lines

Either that "you cannot finalize a write unless all conditionals it depends on are finalized" is true or it is not. That argument has *never* been about some architecture-specific memory ordering model, as far as I know.

As to READ_ONCE_CTRL - two wrongs don't make a right.

Quoted 7 lines

That smp_read_barrier_depends() there doesn't make any sense either.

And finally, the alpha architecture manual actually does have the notion of "Dependence Constraint" (5.6.1.7) that talks about writes that depend on previous reads (where "depends" is explicitly spelled out to be about conditionals, write data _or_ write address). They are actually constrained on alpha too.

I am in India and my Alpha Architecture Manual is in the USA. Google Books has a PDF, but it conveniently omits that particular section. I do remember quoting that section at the Alpha architects back in the late 1990s and being told that it didn't mean what I thought it meant.

And they did post a clarification on the web:

http://h71000.www7.hp.com/wizard/wiz_2637.html

For instance, your producer must issue a "memory barrier" instruction after writing the data to shared memory and before inserting it on the queue; likewise, your consumer must issue a memory barrier instruction after removing an item from the queue and before reading from its memory. Otherwise, you risk seeing stale data, since, while the Alpha processor does provide coherent memory, it does not provide implicit ordering of reads and writes. (That is, the write of the producer's data might reach memory after the write of the queue, such that the consumer might read the new item from the queue but get the previous values from the item's memory.

So 5.6.1.7 apparently does not sanction data dependency ordering.

Quoted 11 lines

Note that a "Dependence Constraint" is not a memory barrier, because it only affects that particular chain of dependencies. So it doesn't order other things in *general*, but it does order a particular read with a particular sef of subsequent write. Which is all we guarantee on anything else too wrt the whole control dependencies.

The smp_read_barrier_depends() is a *READ BARRIER*. It's about a *read* that depends on a previous read. Now, it so happens that alpha doesn't have a "read-to-read" barrier, and it's implemented as a full barrier, but it really should be read as a "smp_rmb().

Quoted 8 lines

Yes, yes, alpha has the worst memory ordering ever, and the worst barriers for that insane memory ordering, but that still does not make alpha "magically able to reorder more than physically or logically possible". We don't add barriers that don't make sense just because the alpha memory orderings are insane.

Paul? I really disagree with how you have totally tried to re-purpose smp_read_barrier_depends() in ways that are insane and make no sense.

I did consider adding a new name, but apparently was lazy that day. I would of course be happy to add a separate name.

Quoted 4 lines

That is not a control dependency. If it was, then PPC and ARM would need to make it a real barrier too. I really don't see why you have singled out alpha as the victim of your "let's just randomly change the rules".

Just trying to make this all work on Alpha as well as the other architectures... But if the actual Alpha hardware that is currently running recent Linux kernels is more strict than the architecture, I of course agree that we could code to the actual hardware rather than to the architecture. They aren't making new Alphas, so we could argue thta the usual forward-compatibility issues do not apply.

And I have not been able to come up with an actual scenario that allows real Alpha hardware to reorder a store with a prior load that it control-depends on. Then again, I wasn't able to come up with the split-cache scenario that breaks data dependencies before my lengthy argument^Wdiscussion with the Alpha architects.

Quoted 5 lines
Quoted 2 lines

In this case, control dependencies are only referring to READ -> WRITE ordering, so they are honoured by ARM and PowerPC.

Do ARM and PPC actually guarantee the generic "previous reads always order before subsequent writes"?

Almost. PPC instead guarantees ordering between a previous read and a later store, but only if they are separated (at runtime) by a conditional branch that depends on the read.

Quoted 4 lines

Because if that's the issue, then we should perhaps add a new ordering primitive that says that (ie "smp_read_to_write_barrier()"). That could be a useful thing in general, where we currently use "smp_mb()" to order an earlier read with a later write.

I agree that smp_read_to_write_barrier() would be useful, and on PPC it could use the lighter-weight lwsync instruction. But that is a different case than the load-to-store control dependencies, which PPC (and I believe also ARM) enforce without a memory-barrier instruction.

Thanx, Paul

#28 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 6 lines · Paul E. McKenney
Quoted 3 lines

Alpha isn't special. And smp_read_barrier_depends() hasn't magically become something new.

The existing control dependencies (READ_ONCE_CTRL() and friends) only guarantee ordering against later stores, and not against later loads.

Right. And using "smp_read_barrier_depends()" for them is WRONG.

That's my argument.

Your arguments make no sense.

Quoted 2 lines

Of the weakly ordered architectures, only Alpha fails to respect load-to-store control dependencies.

NO IT DOES NOT.

Christ, Paul. I even sent you the alpha architecture manual information where it explicitly says that there's a dependency ordering for that case.

There's a reason that "smp_read_barrier_depends()" is called smp_READ_barrier_depends().

It's a rmb. Really

You have turned it into something else in your mind. But your mind is WRONG.

Quoted 1 line

I am in India and my Alpha Architecture Manual is in the USA.

I sent you a link to something that should work, and that has the section.

Quoted 1 line

And they did post a clarification on the web:

So for alpha, you trust a random web posting by a unknown person that talks about some random problem in an application that we don't even know what it is.

But you don't trust the architecture manual, and you don't trust the fact that it si *physically impossible* to not have the load-to-control-to-store ordering without some kind of magical nullifying stores that we know that alpha didn't have?

But then magically, you trust the architecture manuals for other architectures, or just take the "you cannot have smp-visible speculative stores" on faith.

But alpha is different, and lives in a universe where causality suddenly doesn't exist.

I really don't understand your logic.

Quoted 1 line

So 5.6.1.7 apparently does not sanction data dependency ordering.

Exactly why are you arguing against he architecture manual?

Quoted 5 lines
Quoted 2 lines

Paul? I really disagree with how you have totally tried to re-purpose smp_read_barrier_depends() in ways that are insane and make no sense.

I did consider adding a new name, but apparently was lazy that day. I would of course be happy to add a separate name.

That is NOT WHAT I WANT AT ALL.

Get rid of the smp_read_barrier_depends(). It doesn't do control barriers against stores, it has never done that, and they aren't needed in the first place.

There is no need for a new name. The only thing that there is a need for is to just realize that alpha isn't magical.

Alpha does have a stupid segmented cache which means that even when the core is constrained by load-to-load data address dependencies (because no alpha actually did value predication), the cachelines that core loads may not be ordered without the memory barrier.

But that "second load may get a stale value from the past" is purely about loads. You cannot have the same issue happen for stores, because there's no way a store buffer somehow magically goes backwards in time and exposes the store before the load that it depended on.

And the architecture manual even *EXPLICITLY* says so. Alpha does actually have a dependency chain from loads to dependent stores - through addresses, through data, _and_ through control. It's documented, but equally importantly, it's just basically impossible to not have an architecture that does that.

Even if you do some really fancy things like actual value prediction (which the alpha architecture _allows_, although no alpha ever did, afaik), that cannot break the load->store dependency. Because even if the load value was predicted (or any control flow after the load was predicted), the store cannot be committed and made visible to other CPU's until after that prediction has been verified.

So there may be bogus values in a store buffer, but those values will have to be killed with the store instructions that caused them, if any prediction failed. They won't be visible to other CPU's.

And I say that not because the architecture manual says so (although it does), but because because such a CPU wouldn't *work*. It wouldn't be a CPU, it would at most be a fuzzy neural network that generates cool results that may be interesting, but they won't be dependable or reliable in the sense that the Linux kernel depends on.

Quoted 8 lines
Quoted 4 lines

That is not a control dependency. If it was, then PPC and ARM would need to make it a real barrier too. I really don't see why you have singled out alpha as the victim of your "let's just randomly change the rules".

Just trying to make this all work on Alpha as well as the other architectures... But if the actual Alpha hardware that is currently running recent Linux kernels is more strict than the architecture

.. really. This is specified in the architecture manual. The fact that you have found some random posting by some random person that says "you need barriers everywhere" is immaterial. That support blog may well have been simply a "I don't know what I am talking about, and I don't know what problem you have, but I do know that the memory model is really nasty, and adding random barriers will make otherwise correct code work".

But we don't add random read barriers to make a control-to-store barrier. Not when the architecture manual explicitly says there is a dependency chain there, and not when I don't see how you could possibly even make a valid CPU that doesn't have that dependency.

Linus

#29 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 2 lines · Linus Torvalds

On Mon, Nov 2, 2015 at 5:57 PM, Paul E. McKenney
<[email protected]> wrote:

[ . . . ]

Quoted 3 lines
Quoted 1 line

I am in India and my Alpha Architecture Manual is in the USA.

I sent you a link to something that should work, and that has the section.

Thank you, and yes, it clearly states that read-to-write dependencies are ordered. Color me slow and stupid.

Quoted 5 lines
Quoted 1 line

And they did post a clarification on the web:

So for alpha, you trust a random web posting by a unknown person that talks about some random problem in an application that we don't even know what it is.

In my defense, the Alpha architects pointed me at that web posting, but yes, it appears to be pushing for overly conservative safety rather than accuracy. Please accept my apologies for my confusion.

Thanx, Paul

#30 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 3 lines · Paul E. McKenney

Thank you, and yes, it clearly states that read-to-write dependencies are ordered.

Well, I wouldn't say that it's exactly "clear".

The fact that they explicitly say "Note that the DP relation does not directly impose a BEFORE (⇐) ordering between accesses u and v" makes it all clear as mud.

They *then* go on to talk about how the DP relationship *together* with the odd "is source of" ordering (which in turn is defined in terms of BEFORE ordering) cannot have cycles.

I have no idea why they do it that way, but the reason seems to be that they wanted to make "BEFORE" be purely about barriers and accesses, and make the other orderings be described separately. So the "BEFORE" ordering is used to define how memory must act, which is then used as a basis for that storage definition and the "is source of" thing.

But none of that seems to make much sense to a *user*.

The fact that they seem to equate "BEFORE" with "Processor Issue Constraints" also makes me think that the whole logic was written by a CPU designer, and part of why they document it that way is that the CPU designer literally thought of "can I issue this access" as being very different from "is there some inherent ordering that just results from issues outside of my design".

I really don't know. That whole series of memory ordering rules makes my head hurt.

But I do think the only thing that matters in the end is that they do have that DP relationship between reads and subsequently dependent writes, but basically not for *any* other relationship.

So on alpha read-vs-read, write-vs-later-read, and write-vs-write all have to have memory barriers, unless the accesses physically overlap.

Linus

#31 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 32 lines · Linus Torvalds
Quoted 3 lines · Paul E. McKenney

Thank you, and yes, it clearly states that read-to-write dependencies are ordered.

Well, I wouldn't say that it's exactly "clear".

The fact that they explicitly say "Note that the DP relation does not directly impose a BEFORE (⇐) ordering between accesses u and v" makes it all clear as mud.

They *then* go on to talk about how the DP relationship *together* with the odd "is source of" ordering (which in turn is defined in terms of BEFORE ordering) cannot have cycles.

I have no idea why they do it that way, but the reason seems to be that they wanted to make "BEFORE" be purely about barriers and accesses, and make the other orderings be described separately. So the "BEFORE" ordering is used to define how memory must act, which is then used as a basis for that storage definition and the "is source of" thing.

But none of that seems to make much sense to a *user*.

The fact that they seem to equate "BEFORE" with "Processor Issue Constraints" also makes me think that the whole logic was written by a CPU designer, and part of why they document it that way is that the CPU designer literally thought of "can I issue this access" as being very different from "is there some inherent ordering that just results from issues outside of my design".

Quoted 2 lines

I really don't know. That whole series of memory ordering rules makes my head hurt.

The honest answer is that for Alpha, I don't know either. But if your head isn't hurting enough yet, feel free to read on...

My guess, based loosely on ARM and PowerPC, is that memory barriers provide global ordering but that the load-to-store dependency ordering is strictly local. Which as you say does not necessarily make much sense to a user. One guess is that the following would never trigger the BUG_ON() given x, y, and z initially zero (and ignoring the possibility of compiler mischief):

	CPU 0		CPU 1		CPU 2
	r1 = x;		r2 = y;		r3 = z;
	if (r1)		if (r2)		if (r3)
		y = 1;		z = 1;		x = 1;
	BUG_ON(r1 == 1 && r2 == 1 && r3 == 1); /* after the dust settles */

The write-to-read relationships prevent misordering. The copy of the Alpha manual I downloaded hints that this BUG_ON() could not fire.

However, the following might well trigger:

	CPU 0		CPU 1		CPU 2
	x = 1;		r1 = x;		r2 = y;
			if (r1)		if (r2)
				y = 1;		x = 2;
	BUG_ON(r1 == 1 && r2 == 1 && x == 1); /* after the dust settles */

The dependency ordering orders each CPU individually, but might not force CPU 0's write to reach CPU 1 and CPU 2 at the same time. So the BUG_ON() case would happen if CPU 0's write to x reach CPU 1 before it reached CPU 2, in which case the x==2 value might not be seen outside of CPU 2, so that everyone agrees on the order of values taken on by x.

And this could be prevented by enforcing global (rather than local) ordering by placing a memory barrier in CPU 1:

	CPU 0		CPU 1		CPU 2
	x = 1;		r1 = x;		r2 = y;
			smp_mb();	if (r2)
			if (r1)			x = 2;
				y = 1;
	BUG_ON(r1 == 1 && r2 == 1 && x == 1); /* after the dust settles */

But the reference manual doesn't have this sort of litmus test, so who knows? CCing the Alpha maintainers in case they know.

Quoted 6 lines

But I do think the only thing that matters in the end is that they do have that DP relationship between reads and subsequently dependent writes, but basically not for *any* other relationship.

So on alpha read-vs-read, write-vs-later-read, and write-vs-write all have to have memory barriers, unless the accesses physically overlap.

Agreed.

Thanx, Paul

maintainer
#32 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Linus Torvalds
Quoted 2 lines · Linus Torvalds

include/linux/compiler.h static __always_inline void __write_once · line 293

Quoted 2 lines
include/linux/compiler.h +2 -0
+       smp_read_barrier_depends(); /* ctrl */  \
+       smp_rmb(); /* ctrl + rmb := acquire */  \

Doesn't smp_rmb() imply an smp_read_barrier_depends() anyway? In memory-barriers.txt, it says:

Read memory barriers imply data dependency barriers, and so can substitute for them.

David

author maintainer
#33 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 10 lines · David Howells
Quoted 2 lines · Linus Torvalds

include/linux/compiler.h static __always_inline void __write_once · line 293

Quoted 2 lines
include/linux/compiler.h +2 -0
+       smp_read_barrier_depends(); /* ctrl */  \
+       smp_rmb(); /* ctrl + rmb := acquire */  \

Doesn't smp_rmb() imply an smp_read_barrier_depends() anyway? In memory-barriers.txt, it says:

Read memory barriers imply data dependency barriers, and so can substitute for them.

Yes, I noted that in a follow up email, Alpha implements both as MB. So just the smp_rmb() is sufficient.

#34 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to David Howells
Quoted 6 lines · David Howells
Quoted 2 lines · Linus Torvalds

include/linux/compiler.h static __always_inline void __write_once · line 293

Quoted 2 lines
include/linux/compiler.h +2 -0
+       smp_read_barrier_depends(); /* ctrl */  \
+       smp_rmb(); /* ctrl + rmb := acquire */  \

Doesn't smp_rmb() imply an smp_read_barrier_depends() anyway?

Yes, it does. But that "smp_read_barrier_depends()" is actually mis-used as a "barrier against subsequent dependent writes, thanks to the control flow". It's not protecting against subsequent reads - which is what the smp_rmb() is about.

Which is completely bogus, but that's what the comment implies.

Of course, on alpha (which is where smp_read_barrier_depends() makes a difference), both that and smp_rmb() are just full memory barriers, because alpha is some crazy sh*t. So yes, a "smp_rmb()" is sufficient everywhere, but that is actually not where the confusion comes from in the first place.

Linus

#35 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Peter Zijlstra
Quoted 7 lines · Peter Zijlstra
include/linux/compiler.h +6 -0
+#define smp_cond_acquire(cond)	do {		\
+	while (!(cond))				\
+		cpu_relax();			\
+	smp_read_barrier_depends(); /* ctrl */	\
+	smp_rmb(); /* ctrl + rmb := acquire */	\
+} while (0)

...

Quoted 5 lines
kernel/task_work.c +0 -0
@@ -102,13 +102,13 @@ void task_work_run(void)
 
 		if (!work)

kernel/task_work.c void task_work_run(void) · line 111

Quoted 10 lines
kernel/task_work.c +2 -2
 			break;
+
 		/*
 		 * Synchronize with task_work_cancel(). It can't remove
 		 * the first entry == work, cmpxchg(task_works) should
 		 * fail, but it can play with *work and other entries.
 		 */
-		raw_spin_unlock_wait(&task->pi_lock);
-		smp_mb();
+		smp_cond_acquire(!raw_spin_is_locked(&task->pi_lock));

Unfortunately this doesn't look exactly right...

spin_unlock_wait() is not equal to "while (locked) relax", the latter is live-lockable or at least sub-optimal: we do not really need to spin until we observe !spin_is_locked(), we only need to synchronize with the current owner of this lock. Once it drops the lock we can proceed, we do not care if another thread takes the same lock right after that.

Oleg.

author maintainer
#36 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 11 lines · Oleg Nesterov

kernel/task_work.c void task_work_run(void) · line 111

Quoted 3 lines
kernel/task_work.c +1 -2
-		raw_spin_unlock_wait(&task->pi_lock);
-		smp_mb();
+		smp_cond_acquire(!raw_spin_is_locked(&task->pi_lock));

Unfortunately this doesn't look exactly right...

spin_unlock_wait() is not equal to "while (locked) relax", the latter is live-lockable or at least sub-optimal: we do not really need to spin until we observe !spin_is_locked(), we only need to synchronize with the current owner of this lock. Once it drops the lock we can proceed, we do not care if another thread takes the same lock right after that.

Ah indeed. And while every use of spin_unlock_wait() has 'interesting' barriers associated, they all seem different.

#37 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Oleg Nesterov

Hi Oleg,

On Tue, Nov 03, 2015 at 06:59:58PM +0100, Oleg Nesterov wrote:
[snip]

Quoted 5 lines

Unfortunately this doesn't look exactly right...

spin_unlock_wait() is not equal to "while (locked) relax", the latter is live-lockable or at least sub-optimal: we do not really need to spin

Just be curious, should spin_unlock_wait() semantically be an ACQUIRE? Because spin_unlock_wait() is used for us to wait for a certain lock to RELEASE so that we can do something *after* we observe the RELEASE. Considering the follow example:

	CPU 0 				CPU 1
	============================	===========================
	{ X = 0 }
					WRITE_ONCE(X, 1);
					spin_unlock(&lock);
	spin_unlock_wait(&lock)
	r1 = READ_ONCE(X);

If spin_unlock_wait() is not an ACQUIRE, r1 can be 0 in this case, right? Am I missing something subtle here? Or spin_unlock_wait() itself doesn't have the ACQUIRE semantics, but it should always come with a smp_mb() *following* it to achieve the ACQUIRE semantics? However in do_exit(), an smp_mb() is preceding raw_spin_unlock_wait() rather than following, which makes me confused... could you explain that? Thank you ;-)

Regards,
Boqun

Quoted 6 lines

until we observe !spin_is_locked(), we only need to synchronize with the current owner of this lock. Once it drops the lock we can proceed, we do not care if another thread takes the same lock right after that.

Oleg.

#38 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 11 lines · Boqun Feng

Hi Oleg,

On Tue, Nov 03, 2015 at 06:59:58PM +0100, Oleg Nesterov wrote:
[snip]

Quoted 5 lines

Unfortunately this doesn't look exactly right...

spin_unlock_wait() is not equal to "while (locked) relax", the latter is live-lockable or at least sub-optimal: we do not really need to spin

Just be curious, should spin_unlock_wait() semantically be an ACQUIRE?

Hmm.. I guess I was wrong, it doesn't need to be an ACQUIRE, it needs only to use the control dependency to order the load of lock state and stores following it.

Quoted 12 lines

Because spin_unlock_wait() is used for us to wait for a certain lock to RELEASE so that we can do something *after* we observe the RELEASE. Considering the follow example:

	CPU 0 				CPU 1
	============================	===========================
	{ X = 0 }
					WRITE_ONCE(X, 1);
					spin_unlock(&lock);
	spin_unlock_wait(&lock)
	r1 = READ_ONCE(X);
Quoted 8 lines

If spin_unlock_wait() is not an ACQUIRE, r1 can be 0 in this case, right? Am I missing something subtle here? Or spin_unlock_wait() itself doesn't have the ACQUIRE semantics, but it should always come with a smp_mb() *following* it to achieve the ACQUIRE semantics? However in do_exit(), an smp_mb() is preceding raw_spin_unlock_wait() rather than following, which makes me confused... could you explain that? Thank you ;-)

But still, there is one suspicious use of smp_mb() in do_exit():

	/*
	 * The setting of TASK_RUNNING by try_to_wake_up() may be delayed
	 * when the following two conditions become true.
	 *   - There is race condition of mmap_sem (It is acquired by
	 *     exit_mm()), and
	 *   - SMI occurs before setting TASK_RUNINNG.
	 *     (or hypervisor of virtual machine switches to other guest)
	 *  As a result, we may become TASK_RUNNING after becoming TASK_DEAD
	 *
	 * To avoid it, we have to wait for releasing tsk->pi_lock which
	 * is held by try_to_wake_up()
	 */
	smp_mb();
	raw_spin_unlock_wait(&tsk->pi_lock);

	/* causes final put_task_struct in finish_task_switch(). */
	tsk->state = TASK_DEAD;
	tsk->flags |= PF_NOFREEZE;	/* tell freezer to ignore us */
	schedule();

Seems like smp_mb() doesn't need here? Because the control dependency already orders load of tsk->pi_lock and store of tsk->state, and this control dependency order guarantee pairs with the spin_unlock(->pi_lock) in try_to_wake_up() to avoid data race on ->state.

Regards,
Boqun

Quoted 9 lines

Regards,
Boqun

Quoted 6 lines

until we observe !spin_is_locked(), we only need to synchronize with the current owner of this lock. Once it drops the lock we can proceed, we do not care if another thread takes the same lock right after that.

Oleg.

#39 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

He Boqun,

Let me first state that I can't answer authoritatively when it comes to barriers. That said,

Quoted 23 lines · Boqun Feng

But still, there is one suspicious use of smp_mb() in do_exit():

	/*
	 * The setting of TASK_RUNNING by try_to_wake_up() may be delayed
	 * when the following two conditions become true.
	 *   - There is race condition of mmap_sem (It is acquired by
	 *     exit_mm()), and
	 *   - SMI occurs before setting TASK_RUNINNG.
	 *     (or hypervisor of virtual machine switches to other guest)
	 *  As a result, we may become TASK_RUNNING after becoming TASK_DEAD
	 *
	 * To avoid it, we have to wait for releasing tsk->pi_lock which
	 * is held by try_to_wake_up()
	 */
	smp_mb();
	raw_spin_unlock_wait(&tsk->pi_lock);

	/* causes final put_task_struct in finish_task_switch(). */
	tsk->state = TASK_DEAD;
	tsk->flags |= PF_NOFREEZE;	/* tell freezer to ignore us */
	schedule();
Quoted 1 line

Seems like smp_mb() doesn't need here?

Please see my reply to peterz's email.

AFAICS, we need the barries on both sides. But, since we only need to STORE into tsk->state after unlock_wait(), we can rely on the control dependency and avoid the 2nd mb().

Oleg.

#40 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Boqun Feng
Quoted 8 lines · Boqun Feng
Quoted 7 lines · Boqun Feng

Hi Oleg,

On Tue, Nov 03, 2015 at 06:59:58PM +0100, Oleg Nesterov wrote:
[snip]

Quoted 3 lines

Unfortunately this doesn't look exactly right...

Quoted 8 lines
Quoted 4 lines
Quoted 2 lines

spin_unlock_wait() is not equal to "while (locked) relax", the latter is live-lockable or at least sub-optimal: we do not really need to spin

Just be curious, should spin_unlock_wait() semantically be an ACQUIRE?

Hmm.. I guess I was wrong, it doesn't need to be an ACQUIRE, it needs only to use the control dependency to order the load of lock state and stores following it.

I must say that spin_unlock_wait() and friends are a bit tricky. There are only a few uses in drivers/ata/libata-eh.c, ipc/sem.c, kernel/exit.c, kernel/sched/completion.c, and kernel/task_work.c. Almost all of these seem to assume that spin_unlock_wait() provides no ordering. We might have just barely enough uses to produce useful abstractions, but my guess is that it would not hurt to wait.

Quoted 43 lines
Quoted 12 lines

Because spin_unlock_wait() is used for us to wait for a certain lock to RELEASE so that we can do something *after* we observe the RELEASE. Considering the follow example:

	CPU 0 				CPU 1
	============================	===========================
	{ X = 0 }
					WRITE_ONCE(X, 1);
					spin_unlock(&lock);
	spin_unlock_wait(&lock)
	r1 = READ_ONCE(X);
Quoted 8 lines

If spin_unlock_wait() is not an ACQUIRE, r1 can be 0 in this case, right? Am I missing something subtle here? Or spin_unlock_wait() itself doesn't have the ACQUIRE semantics, but it should always come with a smp_mb() *following* it to achieve the ACQUIRE semantics? However in do_exit(), an smp_mb() is preceding raw_spin_unlock_wait() rather than following, which makes me confused... could you explain that? Thank you ;-)

But still, there is one suspicious use of smp_mb() in do_exit():

	/*
	 * The setting of TASK_RUNNING by try_to_wake_up() may be delayed
	 * when the following two conditions become true.
	 *   - There is race condition of mmap_sem (It is acquired by
	 *     exit_mm()), and
	 *   - SMI occurs before setting TASK_RUNINNG.
	 *     (or hypervisor of virtual machine switches to other guest)
	 *  As a result, we may become TASK_RUNNING after becoming TASK_DEAD
	 *
	 * To avoid it, we have to wait for releasing tsk->pi_lock which
	 * is held by try_to_wake_up()
	 */
	smp_mb();
	raw_spin_unlock_wait(&tsk->pi_lock);

	/* causes final put_task_struct in finish_task_switch(). */
	tsk->state = TASK_DEAD;
	tsk->flags |= PF_NOFREEZE;	/* tell freezer to ignore us */
	schedule();
Quoted 4 lines

Seems like smp_mb() doesn't need here? Because the control dependency already orders load of tsk->pi_lock and store of tsk->state, and this control dependency order guarantee pairs with the spin_unlock(->pi_lock) in try_to_wake_up() to avoid data race on ->state.

The exit() path is pretty heavyweight, so I suspect that an extra smp_mb() is down in the noise. Or are you saying that this is somehow unsafe?

Thanx, Paul

Quoted 14 lines

Regards,
Boqun

Quoted 9 lines

Regards,
Boqun

Quoted 6 lines

until we observe !spin_is_locked(), we only need to synchronize with the current owner of this lock. Once it drops the lock we can proceed, we do not care if another thread takes the same lock right after that.

Oleg.

author maintainer
#41 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Boqun Feng
Quoted 1 line · Boqun Feng

Just be curious, should spin_unlock_wait() semantically be an ACQUIRE?

I did wonder the same thing, it would simplify a number of things if this were so.

#42 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 7 lines · Peter Zijlstra
Quoted 1 line · Boqun Feng

Just be curious, should spin_unlock_wait() semantically be an ACQUIRE?

I did wonder the same thing, it would simplify a number of things if this were so.

Yes, me too.

Sometimes I even think it should have both ACQUIRE + RELEASE semantics. IOW, it should be "equivalent" to spin_lock() + spin_unlock().

Consider this code:

	object_t *object;
	spinlock_t lock;

	void update(void)
	{
		object_t *o;

		spin_lock(&lock);
		o = READ_ONCE(object);
		if (o) {
			BUG_ON(o->dead);
			do_something(o);
		}
		spin_unlock(&lock);
	}

	void destroy(void) // can be called only once, can't race with itself
	{
		object_t *o;

		o = object;
		object = NULL;

		/*
		 * pairs with lock/ACQUIRE. The next update() must see
		 * object == NULL after spin_lock();
		 */
		smp_mb();

		spin_unlock_wait(&lock);

		/*
		 * pairs with unlock/RELEASE. The previous update() has
		 * already passed BUG_ON(o->dead).
		 *
		 * (Yes, yes, in this particular case it is not needed,
		 *  we can rely on the control dependency).
		 */
		smp_mb();

		o->dead = true;
	}

I believe the code above is correct and it needs the barriers on both sides.

If it is wrong, then task_work_run() is buggy: it relies on mb() implied by cmpxchg() before spin_unlock_wait() the same way: the next task_work_cancel() should see the result of our cmpxchg(), it must not try to read work->next or work->func.

Hmm. Not sure I really understand what I am trying to say... Perhaps in fact I mean that unlock_wait() should be removed because it is too subtle for me ;)

Oleg.

#43 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 4 lines · Oleg Nesterov

On 11/11, Peter Zijlstra wrote:

Sometimes I even think it should have both ACQUIRE + RELEASE semantics. IOW, it should be "equivalent" to spin_lock() + spin_unlock().

That's insane.

"Release" semantics are - by definition - about stuff that *predeces* it.

It is simply not sensible to have a "wait_for_unlock()" that then synchronizes loads or stores that happened *before* the wait. That's some crazy voodoo programming.

And if you do need to have model where you do "store something, then make sure that the unlock we wait for happens after the store", then you need to just add a "smp_mb()" in between that store and the waiting for unlock.

Or just take the damn lock, and don't play any games at all.

Linus

#44 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Oleg Nesterov
Quoted 59 lines · Oleg Nesterov
Quoted 7 lines · Peter Zijlstra
Quoted 1 line · Boqun Feng

Just be curious, should spin_unlock_wait() semantically be an ACQUIRE?

I did wonder the same thing, it would simplify a number of things if this were so.

Yes, me too.

Sometimes I even think it should have both ACQUIRE + RELEASE semantics. IOW, it should be "equivalent" to spin_lock() + spin_unlock().

Consider this code:

	object_t *object;
	spinlock_t lock;

	void update(void)
	{
		object_t *o;

		spin_lock(&lock);
		o = READ_ONCE(object);
		if (o) {
			BUG_ON(o->dead);
			do_something(o);
		}
		spin_unlock(&lock);
	}

	void destroy(void) // can be called only once, can't race with itself
	{
		object_t *o;

		o = object;
		object = NULL;

		/*
		 * pairs with lock/ACQUIRE. The next update() must see
		 * object == NULL after spin_lock();
		 */
		smp_mb();

		spin_unlock_wait(&lock);

		/*
		 * pairs with unlock/RELEASE. The previous update() has
		 * already passed BUG_ON(o->dead).
		 *
		 * (Yes, yes, in this particular case it is not needed,
		 *  we can rely on the control dependency).
		 */
		smp_mb();

		o->dead = true;
	}
Quoted 2 lines

I believe the code above is correct and it needs the barriers on both sides.

Hmm.. probably incorrect.. because the ACQUIRE semantics of spin_lock() only guarantees that the memory operations following spin_lock() can't be reorder before the *LOAD* part of spin_lock() not the *STORE* part, i.e. the case below can happen(assuming the spin_lock() is implemented as ll/sc loop)

	spin_lock(&lock):
	  r1 = *lock; // LL, r1 == 0
	o = READ_ONCE(object); // could be reordered here.
	  *lock = 1; // SC

This could happen because of the ACQUIRE semantics of spin_lock(), and the current implementation of spin_lock() on PPC allows this happen.

(Cc PPC maintainers for their opinions on this one)

Therefore the case below can happen:

	CPU 1			CPU 2			CPU 3
	==================	====================	==============
							spin_unlock(&lock);
				spin_lock(&lock):
				  r1 = *lock; // r1 == 0;
				o = READ_ONCE(object); // reordered here
	object = NULL;
	smp_mb();
	spin_unlock_wait(&lock);
				  *lock = 1;
	smp_mb();		
	o->dead = true;
				if (o) // true
				  BUG_ON(o->dead); // true!!

To show this, I also translate this situation into a PPC litmus for herd[1]:

	PPC spin-lock-wait
	"
	r1: local variable of lock
	r2: constant 1
	r3: constant 0 or NULL
	r4: local variable of object, i.e. o
	r5: local variable of *o (simulate ->dead as I didn't know 
	    how to write fields of structure in herd ;-()
	r13: the address of lock, i.e. &lock
	r14: the address of object, i.e. &object
	"
	{
	0:r1=0;0:r2=1;0:r3=0;0:r13=lock;0:r14=object;
	1:r1=0;1:r2=1;1:r3=0;1:r4=0;1:r5=0;1:r13=lock;1:r14=object;
	2:r1=0;2:r13=lock;
	lock=1; object=old; old=0;
	}

	P0              | P1                 | P2 ;
	ld r4,0(r14)    | Lock:              | stw r1,0(r13);
	std r3,0(r14)   | lwarx r1,r3,r13    | ;
	                | cmpwi r1,0         | ;
	sync            | bne Lock           | ;
	                | stwcx. r2,r3,r13   | ;
	Wait:           | bne Lock           | ;
	lwz r1,0(r13)   | lwsync             | ;
	cmpwi r1,0      | ld r4,0(r14)       | ;
	bne Wait        | cmpwi r4,0         | ;
	                | beq Fail           | ;
	sync            | lwz r5, 0(r4)      | ;
	stw r2,0(r4)    | Fail:              | ;
	                | lwsync             | ;
	                | stw r3, 0(r13)     | ;

	exists
	(1:r4=old /\ 1:r5=1)

,whose result says that (1:r4=old /\ 1:r5=1) can happen:

	Test spin-lock-wait Allowed
	States 3
	1:r4=0; 1:r5=0;
	1:r4=old; 1:r5=0;
	1:r4=old; 1:r5=1;
	Loop Ok
	Witnesses
	Positive: 18 Negative: 108
	Condition exists (1:r4=old /\ 1:r5=1)
	Observation spin-lock-wait Sometimes 18 108
	Hash=244f8c0f91df5a5ed985500ed7230272

Please note that I use backwards jump in this litmus, which is only supported by herd(not by ppcmem[2]), and it will take a while to get the result. And I'm not that confident that I'm familiar with this tool, maybe Paul and Will can help check my translate and usage here ;-)

IIUC, the problem here is that spin_lock_wait() can be implemented with only LOAD operations, and to have a RELEASE semantics, one primivite must have a *STORE* part, therefore spin_lock_wait() can not be a RELEASE.

So.. we probably need to take the lock here.

Quoted 8 lines

If it is wrong, then task_work_run() is buggy: it relies on mb() implied by cmpxchg() before spin_unlock_wait() the same way: the next task_work_cancel() should see the result of our cmpxchg(), it must not try to read work->next or work->func.

Hmm. Not sure I really understand what I am trying to say... Perhaps in fact I mean that unlock_wait() should be removed because it is too subtle for me ;)

;-)

I think it's OK for it as an ACQUIRE(with a proper barrier) or even just a control dependency to pair with spin_unlock(), for example, the following snippet in do_exit() is OK, except the smp_mb() is redundant, unless I'm missing something subtle:

/*
* The setting of TASK_RUNNING by try_to_wake_up() may be delayed
* when the following two conditions become true.
* - There is race condition of mmap_sem (It is acquired by
* exit_mm()), and
* - SMI occurs before setting TASK_RUNINNG.
* (or hypervisor of virtual machine switches to other guest)
* As a result, we may become TASK_RUNNING after becoming TASK_DEAD *
* To avoid it, we have to wait for releasing tsk->pi_lock which
* is held by try_to_wake_up()
*/
smp_mb();
raw_spin_unlock_wait(&tsk->pi_lock);

/* causes final put_task_struct in finish_task_switch(). */ tsk->state = TASK_DEAD;

Ref:
[1]: https://github.com/herd/herdtools
[2]: http://www.cl.cam.ac.uk/~pes20/ppcmem/index.html

Regards,
Boqun

author maintainer
#45 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 6 lines · Boqun Feng

Hmm.. probably incorrect.. because the ACQUIRE semantics of spin_lock() only guarantees that the memory operations following spin_lock() can't be reorder before the *LOAD* part of spin_lock() not the *STORE* part, i.e. the case below can happen(assuming the spin_lock() is implemented as ll/sc loop)

Quoted 7 lines
	spin_lock(&lock):
	  r1 = *lock; // LL, r1 == 0
	o = READ_ONCE(object); // could be reordered here.
	  *lock = 1; // SC

This could happen because of the ACQUIRE semantics of spin_lock(), and the current implementation of spin_lock() on PPC allows this happen.

Urgh, you just _had_ to send an email like this, didn't you ;-)

I think AARGH64 does the same thing. They either use LDAXR/STXR, which also places the ACQUIRE on the load, or use LDADDA (v8.1) which I suspect does the same, but I'm not entirely sure how to decode these 8.1 atomics yet.

Let me think a little more on this..

#46 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Boqun Feng
Quoted 60 lines · Boqun Feng
Quoted 44 lines · Oleg Nesterov
	object_t *object;
	spinlock_t lock;

	void update(void)
	{
		object_t *o;

		spin_lock(&lock);
		o = READ_ONCE(object);
		if (o) {
			BUG_ON(o->dead);
			do_something(o);
		}
		spin_unlock(&lock);
	}

	void destroy(void) // can be called only once, can't race with itself
	{
		object_t *o;

		o = object;
		object = NULL;

		/*
		 * pairs with lock/ACQUIRE. The next update() must see
		 * object == NULL after spin_lock();
		 */
		smp_mb();

		spin_unlock_wait(&lock);

		/*
		 * pairs with unlock/RELEASE. The previous update() has
		 * already passed BUG_ON(o->dead).
		 *
		 * (Yes, yes, in this particular case it is not needed,
		 *  we can rely on the control dependency).
		 */
		smp_mb();

		o->dead = true;
	}
Quoted 2 lines

I believe the code above is correct and it needs the barriers on both sides.

Hmm.. probably incorrect.. because the ACQUIRE semantics of spin_lock() only guarantees that the memory operations following spin_lock() can't be reorder before the *LOAD* part of spin_lock() not the *STORE* part, i.e. the case below can happen(assuming the spin_lock() is implemented as ll/sc loop)

	spin_lock(&lock):
	  r1 = *lock; // LL, r1 == 0
	o = READ_ONCE(object); // could be reordered here.
	  *lock = 1; // SC
Quoted 4 lines

This could happen because of the ACQUIRE semantics of spin_lock(), and the current implementation of spin_lock() on PPC allows this happen.

(Cc PPC maintainers for their opinions on this one)

In this case the code above is obviously wrong. And I do not understand how we can rely on spin_unlock_wait() then.

And afaics do_exit() is buggy too then, see below.

Quoted 5 lines

I think it's OK for it as an ACQUIRE(with a proper barrier) or even just a control dependency to pair with spin_unlock(), for example, the following snippet in do_exit() is OK, except the smp_mb() is redundant, unless I'm missing something subtle:

Quoted 14 lines

/*
* The setting of TASK_RUNNING by try_to_wake_up() may be delayed
* when the following two conditions become true.
* - There is race condition of mmap_sem (It is acquired by
* exit_mm()), and
* - SMI occurs before setting TASK_RUNINNG.
* (or hypervisor of virtual machine switches to other guest)
* As a result, we may become TASK_RUNNING after becoming TASK_DEAD *
* To avoid it, we have to wait for releasing tsk->pi_lock which
* is held by try_to_wake_up()
*/
smp_mb();
raw_spin_unlock_wait(&tsk->pi_lock);

Perhaps it is me who missed something. But I don't think we can remove this mb(). And at the same time it can't help on PPC if I understand your explanation above correctly.

To simplify, lets ignore exit_mm/down_read/etc. The exiting task does

	current->state = TASK_UNINTERRUPTIBLE;
	// without schedule() in between
	current->state = TASK_RUNNING;

	smp_mb();
	spin_unlock_wait(pi_lock);

	current->state = TASK_DEAD;
	schedule();

and we need to ensure that if we race with try_to_wake_up(TASK_UNINTERRUPTIBLE) it can't change TASK_DEAD back to RUNNING.

Without smp_mb() this can be reordered, spin_unlock_wait(pi_locked) can read the old "unlocked" state of pi_lock before we set UNINTERRUPTIBLE, so in fact we could have

	current->state = TASK_UNINTERRUPTIBLE;
	
	spin_unlock_wait(pi_lock);

	current->state = TASK_RUNNING;

	current->state = TASK_DEAD;

and this can obviously race with ttwu() which can take pi_lock and see state == TASK_UNINTERRUPTIBLE after spin_unlock_wait().

And, if I understand you correctly, this smp_mb() can't help on PPC. try_to_wake_up() can read task->state before it writes to *pi_lock. To me this doesn't really differ from the code above,

	CPU 1 (do_exit)				CPU_2 (ttwu)

						spin_lock(pi_lock):
						  r1 = *pi_lock; // r1 == 0;
	p->state = TASK_UNINTERRUPTIBLE;
						state = p->state;
	p->state = TASK_RUNNING;
	mb();
	spin_unlock_wait();
						*pi_lock = 1;

	p->state = TASK_DEAD;
						if (state & TASK_UNINTERRUPTIBLE) // true
							p->state = RUNNING;

No?

And smp_mb__before_spinlock() looks wrong too then.

Oleg.

#47 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 91 lines · Oleg Nesterov
Quoted 60 lines · Boqun Feng
Quoted 44 lines · Oleg Nesterov
	object_t *object;
	spinlock_t lock;

	void update(void)
	{
		object_t *o;

		spin_lock(&lock);
		o = READ_ONCE(object);
		if (o) {
			BUG_ON(o->dead);
			do_something(o);
		}
		spin_unlock(&lock);
	}

	void destroy(void) // can be called only once, can't race with itself
	{
		object_t *o;

		o = object;
		object = NULL;

		/*
		 * pairs with lock/ACQUIRE. The next update() must see
		 * object == NULL after spin_lock();
		 */
		smp_mb();

		spin_unlock_wait(&lock);

		/*
		 * pairs with unlock/RELEASE. The previous update() has
		 * already passed BUG_ON(o->dead).
		 *
		 * (Yes, yes, in this particular case it is not needed,
		 *  we can rely on the control dependency).
		 */
		smp_mb();

		o->dead = true;
	}
Quoted 2 lines

I believe the code above is correct and it needs the barriers on both sides.

Hmm.. probably incorrect.. because the ACQUIRE semantics of spin_lock() only guarantees that the memory operations following spin_lock() can't be reorder before the *LOAD* part of spin_lock() not the *STORE* part, i.e. the case below can happen(assuming the spin_lock() is implemented as ll/sc loop)

	spin_lock(&lock):
	  r1 = *lock; // LL, r1 == 0
	o = READ_ONCE(object); // could be reordered here.
	  *lock = 1; // SC
Quoted 4 lines

This could happen because of the ACQUIRE semantics of spin_lock(), and the current implementation of spin_lock() on PPC allows this happen.

(Cc PPC maintainers for their opinions on this one)

In this case the code above is obviously wrong. And I do not understand how we can rely on spin_unlock_wait() then.

And afaics do_exit() is buggy too then, see below.

Quoted 5 lines

I think it's OK for it as an ACQUIRE(with a proper barrier) or even just a control dependency to pair with spin_unlock(), for example, the following snippet in do_exit() is OK, except the smp_mb() is redundant, unless I'm missing something subtle:

Quoted 14 lines

/*
* The setting of TASK_RUNNING by try_to_wake_up() may be delayed
* when the following two conditions become true.
* - There is race condition of mmap_sem (It is acquired by
* exit_mm()), and
* - SMI occurs before setting TASK_RUNINNG.
* (or hypervisor of virtual machine switches to other guest)
* As a result, we may become TASK_RUNNING after becoming TASK_DEAD *
* To avoid it, we have to wait for releasing tsk->pi_lock which
* is held by try_to_wake_up()
*/
smp_mb();
raw_spin_unlock_wait(&tsk->pi_lock);

Quoted 3 lines

Perhaps it is me who missed something. But I don't think we can remove this mb(). And at the same time it can't help on PPC if I understand your explanation above correctly.

I cannot resist suggesting that any lock that interacts with spin_unlock_wait() must have all relevant acquisitions followed by smp_mb__after_unlock_lock().

Thanx, Paul

#48 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

On Thu, Nov 12, 2015 at 06:40:04AM -0800, Paul E. McKenney wrote:
[snip]

Quoted 5 lines

I cannot resist suggesting that any lock that interacts with spin_unlock_wait() must have all relevant acquisitions followed by smp_mb__after_unlock_lock().

But

1. This would expand the purpose of smp_mb__after_unlock_lock(),
right? smp_mb__after_unlock_lock() is for making UNLOCK-LOCK pair global transitive rather than guaranteeing no operations can be reorder before the STORE part of LOCK/ACQUIRE.

2. If ARM64 has the same problem as PPC now,

	smp_mb__after_unlock_lock() can't help, as it's a no-op on
	ARM64.

Regards,
Boqun

#49 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 8 lines · Boqun Feng

On Thu, Nov 12, 2015 at 06:40:04AM -0800, Paul E. McKenney wrote:
[snip]

Quoted 5 lines

I cannot resist suggesting that any lock that interacts with spin_unlock_wait() must have all relevant acquisitions followed by smp_mb__after_unlock_lock().

Quoted 6 lines

But

1. This would expand the purpose of smp_mb__after_unlock_lock(),
right? smp_mb__after_unlock_lock() is for making UNLOCK-LOCK pair global transitive rather than guaranteeing no operations can be reorder before the STORE part of LOCK/ACQUIRE.

Indeed it would. Which might be OK.

Quoted 3 lines

2. If ARM64 has the same problem as PPC now,

	smp_mb__after_unlock_lock() can't help, as it's a no-op on
	ARM64.

Agreed, and that is why we need Will to weigh in.

Thanx, Paul

#50 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 16 lines · Paul E. McKenney
Quoted 8 lines · Boqun Feng

On Thu, Nov 12, 2015 at 06:40:04AM -0800, Paul E. McKenney wrote:
[snip]

Quoted 5 lines

I cannot resist suggesting that any lock that interacts with spin_unlock_wait() must have all relevant acquisitions followed by smp_mb__after_unlock_lock().

Quoted 6 lines

But

1. This would expand the purpose of smp_mb__after_unlock_lock(),
right? smp_mb__after_unlock_lock() is for making UNLOCK-LOCK pair global transitive rather than guaranteeing no operations can be reorder before the STORE part of LOCK/ACQUIRE.

Quoted 7 lines

Indeed it would. Which might be OK.

Quoted 3 lines

2. If ARM64 has the same problem as PPC now,

	smp_mb__after_unlock_lock() can't help, as it's a no-op on
	ARM64.

Agreed, and that is why we need Will to weigh in.

I really don't want to implement smp_mb__after_unlock_lock, because we don't need it based on its current definition and I think there's a better way to fix spin_unlock_wait (see my other post).

Will

author maintainer
#51 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Paul E. McKenney
Quoted 3 lines · Paul E. McKenney

I cannot resist suggesting that any lock that interacts with spin_unlock_wait() must have all relevant acquisitions followed by smp_mb__after_unlock_lock().

Ha! that would certainly help here. But it would mean that argh64v8 also needs to define that, even though that is already RCsc.

#52 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Paul E. McKenney

I cannot resist suggesting that any lock that interacts with spin_unlock_wait() must have all relevant acquisitions followed by smp_mb__after_unlock_lock().

Ha! that would certainly help here. But it would mean that argh64v8 also needs to define that, even though that is already RCsc.

Maybe. It could also be that arm64 avoids the need somehow, for example via their RCsc behavior. Their memory model is similar to PPC, but not exactly the same.

Will?

Thanx, Paul

author maintainer
#53 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 6 lines · Paul E. McKenney
Quoted 5 lines · Peter Zijlstra
Quoted 3 lines · Paul E. McKenney

I cannot resist suggesting that any lock that interacts with spin_unlock_wait() must have all relevant acquisitions followed by smp_mb__after_unlock_lock().

Quoted 8 lines
Quoted 2 lines

Ha! that would certainly help here. But it would mean that argh64v8 also needs to define that, even though that is already RCsc.

Maybe. It could also be that arm64 avoids the need somehow, for example via their RCsc behavior. Their memory model is similar to PPC, but not exactly the same.

Will?

So when I spoke to Will earlier today, we agreed that LDAXR+STXR is susceptible to the same problem. The STXR will allow loads to pass up over that store.

On v8.1, which is using LDADDA, this is not an issue, for as the ACQUIRE is part of the LOAD, the Read-Modify-Write is indivisible as a whole, and therefore a subsequent load has nothing to pass over.

#54 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 16 lines · Peter Zijlstra
Quoted 6 lines · Paul E. McKenney
Quoted 5 lines · Peter Zijlstra
Quoted 3 lines · Paul E. McKenney

I cannot resist suggesting that any lock that interacts with spin_unlock_wait() must have all relevant acquisitions followed by smp_mb__after_unlock_lock().

Quoted 8 lines
Quoted 2 lines

Ha! that would certainly help here. But it would mean that argh64v8 also needs to define that, even though that is already RCsc.

Maybe. It could also be that arm64 avoids the need somehow, for example via their RCsc behavior. Their memory model is similar to PPC, but not exactly the same.

Will?

Quoted 7 lines

So when I spoke to Will earlier today, we agreed that LDAXR+STXR is susceptible to the same problem. The STXR will allow loads to pass up over that store.

On v8.1, which is using LDADDA, this is not an issue, for as the ACQUIRE is part of the LOAD, the Read-Modify-Write is indivisible as a whole, and therefore a subsequent load has nothing to pass over.

So one approach required for one level of hardware and another for the next level. I can relate to that all too well... :-/

Thanx, Paul

#55 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

[sorry for the late reply, I'm away from my desk until Monday since I'm
busy with family issues]

Quoted 21 lines · Paul E. McKenney
Quoted 20 lines · Peter Zijlstra
Quoted 6 lines · Paul E. McKenney
Quoted 5 lines · Peter Zijlstra
Quoted 3 lines · Paul E. McKenney

I cannot resist suggesting that any lock that interacts with spin_unlock_wait() must have all relevant acquisitions followed by smp_mb__after_unlock_lock().

Quoted 8 lines
Quoted 2 lines

Ha! that would certainly help here. But it would mean that argh64v8 also needs to define that, even though that is already RCsc.

Maybe. It could also be that arm64 avoids the need somehow, for example via their RCsc behavior. Their memory model is similar to PPC, but not exactly the same.

Will?

So when I spoke to Will earlier today, we agreed that LDAXR+STXR is susceptible to the same problem. The STXR will allow loads to pass up over that store.

Quoted 6 lines
Quoted 3 lines

On v8.1, which is using LDADDA, this is not an issue, for as the ACQUIRE is part of the LOAD, the Read-Modify-Write is indivisible as a whole, and therefore a subsequent load has nothing to pass over.

So one approach required for one level of hardware and another for the next level. I can relate to that all too well... :-/

Just to confirm, Peter's correct in that Boqun's litmus test is permitted by the arm64 architecture when the ll/sc spinlock definitions are in use.

However, I don't think that strengthening smp_mb__after_unlock_lock is the right way to solve this. I'll reply to the other part of the thread...

Will

#56 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Oleg Nesterov
Quoted 1 line · Oleg Nesterov

On 11/12, Boqun Feng wrote:

[snip]

Quoted 42 lines
Quoted 12 lines

Hmm.. probably incorrect.. because the ACQUIRE semantics of spin_lock() only guarantees that the memory operations following spin_lock() can't be reorder before the *LOAD* part of spin_lock() not the *STORE* part, i.e. the case below can happen(assuming the spin_lock() is implemented as ll/sc loop)

	spin_lock(&lock):
	  r1 = *lock; // LL, r1 == 0
	o = READ_ONCE(object); // could be reordered here.
	  *lock = 1; // SC
Quoted 4 lines

This could happen because of the ACQUIRE semantics of spin_lock(), and the current implementation of spin_lock() on PPC allows this happen.

(Cc PPC maintainers for their opinions on this one)

In this case the code above is obviously wrong. And I do not understand how we can rely on spin_unlock_wait() then.

And afaics do_exit() is buggy too then, see below.

Quoted 5 lines

I think it's OK for it as an ACQUIRE(with a proper barrier) or even just a control dependency to pair with spin_unlock(), for example, the following snippet in do_exit() is OK, except the smp_mb() is redundant, unless I'm missing something subtle:

Quoted 14 lines

/*
* The setting of TASK_RUNNING by try_to_wake_up() may be delayed
* when the following two conditions become true.
* - There is race condition of mmap_sem (It is acquired by
* exit_mm()), and
* - SMI occurs before setting TASK_RUNINNG.
* (or hypervisor of virtual machine switches to other guest)
* As a result, we may become TASK_RUNNING after becoming TASK_DEAD *
* To avoid it, we have to wait for releasing tsk->pi_lock which
* is held by try_to_wake_up()
*/
smp_mb();
raw_spin_unlock_wait(&tsk->pi_lock);

Quoted 2 lines

Perhaps it is me who missed something. But I don't think we can remove this mb(). And at the same time it can't help on PPC if I understand

You are right, we need this smp_mb() to order the previous STORE of ->state with the LOAD of ->pi_lock. I missed that part because I saw all the explicit STOREs of ->state in do_exit() are set_current_state() which has a smp_mb() following the STOREs.

Quoted 30 lines

your explanation above correctly.

To simplify, lets ignore exit_mm/down_read/etc. The exiting task does

	current->state = TASK_UNINTERRUPTIBLE;
	// without schedule() in between
	current->state = TASK_RUNNING;

	smp_mb();
	spin_unlock_wait(pi_lock);

	current->state = TASK_DEAD;
	schedule();

and we need to ensure that if we race with try_to_wake_up(TASK_UNINTERRUPTIBLE) it can't change TASK_DEAD back to RUNNING.

Without smp_mb() this can be reordered, spin_unlock_wait(pi_locked) can read the old "unlocked" state of pi_lock before we set UNINTERRUPTIBLE, so in fact we could have

	current->state = TASK_UNINTERRUPTIBLE;
	
	spin_unlock_wait(pi_lock);

	current->state = TASK_RUNNING;

	current->state = TASK_DEAD;
Quoted 3 lines

and this can obviously race with ttwu() which can take pi_lock and see state == TASK_UNINTERRUPTIBLE after spin_unlock_wait().

Yep, my mistake ;-)

Quoted 19 lines

And, if I understand you correctly, this smp_mb() can't help on PPC. try_to_wake_up() can read task->state before it writes to *pi_lock. To me this doesn't really differ from the code above,

	CPU 1 (do_exit)				CPU_2 (ttwu)

						spin_lock(pi_lock):
						  r1 = *pi_lock; // r1 == 0;
	p->state = TASK_UNINTERRUPTIBLE;
						state = p->state;
	p->state = TASK_RUNNING;
	mb();
	spin_unlock_wait();
						*pi_lock = 1;

	p->state = TASK_DEAD;
						if (state & TASK_UNINTERRUPTIBLE) // true
							p->state = RUNNING;
Quoted 2 lines

No?

do_exit() is surely buggy if spin_lock() could work in this way.

Quoted 2 lines

And smp_mb__before_spinlock() looks wrong too then.

Maybe not? As smp_mb__before_spinlock() is used before a LOCK operation, which has both LOAD part and STORE part unlike spin_unlock_wait()?

Quoted 2 lines

Oleg.

#57 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 7 lines · Boqun Feng
Quoted 3 lines · Oleg Nesterov

No?

do_exit() is surely buggy if spin_lock() could work in this way.

OK, good ;) so we need to fix spin_lock() on PPC ? Or add mb__after_unlock_lock() but this leads to other questions... Or change do_exit() to do lock() + unlock().

Quoted 6 lines
Quoted 3 lines

And smp_mb__before_spinlock() looks wrong too then.

Maybe not? As smp_mb__before_spinlock() is used before a LOCK operation, which has both LOAD part and STORE part unlike spin_unlock_wait()?

Maybe not.

But let me remind that the original purpose of this mb__before_spinlock() was to ensure that "CONDITION = true" before ttwu() can not be reordered with

	if (!(p->state & state))
		goto out;		// do not wakeup

inside try_to_wake_up(). Otherwise

	CONDITION = true;
	try_to_wake_up(p);

can race with "p" doing

	set_current_state(...);	// implies mb();
	if (CONDITION)
		return;
	schedule();

because try_to_wake_up() can read p->state before it sets CONDITION = 1 and then it won't wakeup "p" which has already checked this CONDITION.

Now. If try_to_wake_up() can read p->state before it writes to *pi_lock, then how smp_mb__before_spinlock() == wmb() can help to serialize STORE and LOAD?

It seems that PPC needs to define smp_mb__before_spinlock() as full mb(), no?

Oleg.

author maintainer
#58 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 2 lines · Oleg Nesterov

It seems that PPC needs to define smp_mb__before_spinlock() as full mb(), no?

It does:

arch/powerpc/include/asm/barrier.h:#define smp_mb__before_spinlock() smp_mb()

#59 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 8 lines · Peter Zijlstra
Quoted 2 lines · Oleg Nesterov

It seems that PPC needs to define smp_mb__before_spinlock() as full mb(), no?

It does:

arch/powerpc/include/asm/barrier.h:#define smp_mb__before_spinlock() smp_mb()

Ah, indeed, thanks.

And given that it also defines smp_mb__after_unlock_lock() as smp_mb(), I am starting to understand how it can help to avoid the races with spin_unlock_wait() in (for example) do_exit().

But as Boqun has already mentioned, this means that mb__after_unlock_lock() has the new meaning which should be documented.

Hmm. And 12d560f4 "Privatize smp_mb__after_unlock_lock()" should be reverted then ;)

Oleg.

#60 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 16 lines · Oleg Nesterov
Quoted 8 lines · Peter Zijlstra
Quoted 2 lines · Oleg Nesterov

It seems that PPC needs to define smp_mb__before_spinlock() as full mb(), no?

It does:

arch/powerpc/include/asm/barrier.h:#define smp_mb__before_spinlock() smp_mb()

Ah, indeed, thanks.

And given that it also defines smp_mb__after_unlock_lock() as smp_mb(), I am starting to understand how it can help to avoid the races with spin_unlock_wait() in (for example) do_exit().

Quoted 5 lines

But as Boqun has already mentioned, this means that mb__after_unlock_lock() has the new meaning which should be documented.

Hmm. And 12d560f4 "Privatize smp_mb__after_unlock_lock()" should be reverted then ;)

Surprisingly, this reverts cleanly against today's mainline, please see the patch below. Against my -rcu stack, not so much, but so it goes. ;-)

Thanx, Paul

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

commit eff0632b4181f91f2596d56f7c73194e1a869aff

Author: Paul E. McKenney <[email protected]>
Date:   Thu Nov 12 10:54:23 2015 -0800

Revert "rcu,locking: Privatize smp_mb__after_unlock_lock()"

This reverts commit 12d560f4ea87030667438a169912380be00cea4b.

The reason for this revert is that smp_mb__after_unlock_lock() might prove useful outside of RCU after all for interactions between the locking primitives and spin_unlock_wait().

Documentation/memory-barriers.txt +67 -4
index aef9487303d0..d4501664d49f 100644
@@ -1855,10 +1855,16 @@ RELEASE are to the same lock variable, but only from the perspective of
 another CPU not holding that lock.  In short, a ACQUIRE followed by an
 RELEASE may -not- be assumed to be a full memory barrier.
 
-Similarly, the reverse case of a RELEASE followed by an ACQUIRE does
-not imply a full memory barrier.  Therefore, the CPU's execution of the
-critical sections corresponding to the RELEASE and the ACQUIRE can cross,
-so that:
+Similarly, the reverse case of a RELEASE followed by an ACQUIRE does not
+imply a full memory barrier.  If it is necessary for a RELEASE-ACQUIRE
+pair to produce a full barrier, the ACQUIRE can be followed by an
+smp_mb__after_unlock_lock() invocation.  This will produce a full barrier
+(including transitivity) if either (a) the RELEASE and the ACQUIRE are
+executed by the same CPU or task, or (b) the RELEASE and ACQUIRE act on
+the same variable.  The smp_mb__after_unlock_lock() primitive is free
+on many architectures.  Without smp_mb__after_unlock_lock(), the CPU's
+execution of the critical sections corresponding to the RELEASE and the
+ACQUIRE can cross, so that:
 
 	*A = a;
 	RELEASE M
@@ -1896,6 +1902,29 @@ the RELEASE would simply complete, thereby avoiding the deadlock.
 	a sleep-unlock race, but the locking primitive needs to resolve
 	such races properly in any case.
 
+With smp_mb__after_unlock_lock(), the two critical sections cannot overlap.
+For example, with the following code, the store to *A will always be
+seen by other CPUs before the store to *B:
+
+	*A = a;
+	RELEASE M
+	ACQUIRE N
+	smp_mb__after_unlock_lock();
+	*B = b;
+
+The operations will always occur in one of the following orders:
+
+	STORE *A, RELEASE, ACQUIRE, smp_mb__after_unlock_lock(), STORE *B
+	STORE *A, ACQUIRE, RELEASE, smp_mb__after_unlock_lock(), STORE *B
+	ACQUIRE, STORE *A, RELEASE, smp_mb__after_unlock_lock(), STORE *B
+
+If the RELEASE and ACQUIRE were instead both operating on the same lock
+variable, only the first of these alternatives can occur.  In addition,
+the more strongly ordered systems may rule out some of the above orders.
+But in any case, as noted earlier, the smp_mb__after_unlock_lock()
+ensures that the store to *A will always be seen as happening before
+the store to *B.
+
 Locks and semaphores may not provide any guarantee of ordering on UP compiled
 systems, and so cannot be counted on in such a situation to actually achieve
 anything at all - especially with respect to I/O accesses - unless combined
@@ -2126,6 +2155,40 @@ But it won't see any of:
 	*E, *F or *G following RELEASE Q
 
 
+However, if the following occurs:
+
+	CPU 1				CPU 2
+	===============================	===============================
+	WRITE_ONCE(*A, a);
+	ACQUIRE M		     [1]
+	WRITE_ONCE(*B, b);
+	WRITE_ONCE(*C, c);
+	RELEASE M	     [1]
+	WRITE_ONCE(*D, d);		WRITE_ONCE(*E, e);
+					ACQUIRE M		     [2]
+					smp_mb__after_unlock_lock();
+					WRITE_ONCE(*F, f);
+					WRITE_ONCE(*G, g);
+					RELEASE M	     [2]
+					WRITE_ONCE(*H, h);
+
+CPU 3 might see:
+
+	*E, ACQUIRE M [1], *C, *B, *A, RELEASE M [1],
+		ACQUIRE M [2], *H, *F, *G, RELEASE M [2], *D
+
+But assuming CPU 1 gets the lock first, CPU 3 won't see any of:
+
+	*B, *C, *D, *F, *G or *H preceding ACQUIRE M [1]
+	*A, *B or *C following RELEASE M [1]
+	*F, *G or *H preceding ACQUIRE M [2]
+	*A, *B, *C, *E, *F or *G following RELEASE M [2]
+
+Note that the smp_mb__after_unlock_lock() is critically important
+here: Without it CPU 3 might see some of the above orderings.
+Without smp_mb__after_unlock_lock(), the accesses are not guaranteed
+to be seen in order unless CPU 3 holds lock M.
+
 
 ACQUIRES VS I/O ACCESSES
 ------------------------
arch/powerpc/include/asm/spinlock.h +2 -0
index 523673d7583c..4dbe072eecbe 100644
@@ -28,6 +28,8 @@
 #include <asm/synch.h>
 #include <asm/ppc-opcode.h>
 
+#define smp_mb__after_unlock_lock()	smp_mb()  /* Full ordering for lock. */
+
 #ifdef CONFIG_PPC64
 /* use 0x800000yy when locked, where yy == CPU number */
 #ifdef __BIG_ENDIAN__
include/linux/spinlock.h +10 -0
index 47dd0cebd204..ffcd053ca89a 100644
@@ -130,6 +130,16 @@ do {								\
 #define smp_mb__before_spinlock()	smp_wmb()
 #endif
 
+/*
+ * Place this after a lock-acquisition primitive to guarantee that
+ * an UNLOCK+LOCK pair act as a full barrier.  This guarantee applies
+ * if the UNLOCK and LOCK are executed by the same CPU or if the
+ * UNLOCK and LOCK operate on the same lock variable.
+ */
+#ifndef smp_mb__after_unlock_lock
+#define smp_mb__after_unlock_lock()	do { } while (0)
+#endif
+
 /**
  * raw_spin_unlock_wait - wait until the spinlock gets unlocked
  * @lock: the spinlock in question.
kernel/rcu/tree.h +0 -12
index 9fb4e238d4dc..8c6753d903ec 100644
@@ -652,15 +652,3 @@ static inline void rcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)
 #endif /* #else #ifdef CONFIG_RCU_NOCB_CPU */
 }
 #endif /* #ifdef CONFIG_RCU_TRACE */
-
-/*
- * Place this after a lock-acquisition primitive to guarantee that
- * an UNLOCK+LOCK pair act as a full barrier.  This guarantee applies
- * if the UNLOCK and LOCK are executed by the same CPU or if the
- * UNLOCK and LOCK operate on the same lock variable.
- */
-#ifdef CONFIG_PPC
-#define smp_mb__after_unlock_lock()	smp_mb()  /* Full ordering for lock. */
-#else /* #ifdef CONFIG_PPC */
-#define smp_mb__after_unlock_lock()	do { } while (0)
-#endif /* #else #ifdef CONFIG_PPC */
#61 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 17 lines · Paul E. McKenney
Quoted 16 lines · Oleg Nesterov
Quoted 8 lines · Peter Zijlstra
Quoted 2 lines · Oleg Nesterov

It seems that PPC needs to define smp_mb__before_spinlock() as full mb(), no?

It does:

arch/powerpc/include/asm/barrier.h:#define smp_mb__before_spinlock() smp_mb()

Ah, indeed, thanks.

And given that it also defines smp_mb__after_unlock_lock() as smp_mb(), I am starting to understand how it can help to avoid the races with spin_unlock_wait() in (for example) do_exit().

Quoted 8 lines
Quoted 5 lines

But as Boqun has already mentioned, this means that mb__after_unlock_lock() has the new meaning which should be documented.

Hmm. And 12d560f4 "Privatize smp_mb__after_unlock_lock()" should be reverted then ;)

Surprisingly, this reverts cleanly against today's mainline, please see the patch below. Against my -rcu stack, not so much, but so it goes. ;-)

I think we ended up concluding that smp_mb__after_unlock_lock is indeed required, but I don't think we should just resurrect the old definition, which doesn't keep UNLOCK -> LOCK distinct from RELEASE -> ACQUIRE. I'm still working on documenting the different types of transitivity that we identified in that thread, but it's slow going.

Also, as far as spin_unlock_wait is concerned, it is neither a LOCK or an UNLOCK and this barrier doesn't offer us anything. Sure, it might work because PPC defines it as smp_mb(), but it doesn't help on arm64 and defining the macro is overkill for us in most places (i.e. RCU).

If we decide that the current usage of spin_unlock_wait is valid, then I would much rather implement a version of it in the arm64 backend that does something like:

1: ldrex r1, [&lock]
if r1 indicates that lock is taken, branch back to 1b strex r1, [&lock]
if store failed, branch back to 1b

i.e. we don't just test the lock, but we also write it back atomically if we discover that it's free. That would then clear the exclusive monitor on any cores in the process of taking the lock and restore the ordering that we need.

Will

#62 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 47 lines · Will Deacon
Quoted 17 lines · Paul E. McKenney
Quoted 16 lines · Oleg Nesterov
Quoted 8 lines · Peter Zijlstra
Quoted 2 lines · Oleg Nesterov

It seems that PPC needs to define smp_mb__before_spinlock() as full mb(), no?

It does:

arch/powerpc/include/asm/barrier.h:#define smp_mb__before_spinlock() smp_mb()

Ah, indeed, thanks.

And given that it also defines smp_mb__after_unlock_lock() as smp_mb(), I am starting to understand how it can help to avoid the races with spin_unlock_wait() in (for example) do_exit().

Quoted 8 lines
Quoted 5 lines

But as Boqun has already mentioned, this means that mb__after_unlock_lock() has the new meaning which should be documented.

Hmm. And 12d560f4 "Privatize smp_mb__after_unlock_lock()" should be reverted then ;)

Surprisingly, this reverts cleanly against today's mainline, please see the patch below. Against my -rcu stack, not so much, but so it goes. ;-)

I think we ended up concluding that smp_mb__after_unlock_lock is indeed required, but I don't think we should just resurrect the old definition, which doesn't keep UNLOCK -> LOCK distinct from RELEASE -> ACQUIRE. I'm still working on documenting the different types of transitivity that we identified in that thread, but it's slow going.

Also, as far as spin_unlock_wait is concerned, it is neither a LOCK or an UNLOCK and this barrier doesn't offer us anything. Sure, it might work because PPC defines it as smp_mb(), but it doesn't help on arm64 and defining the macro is overkill for us in most places (i.e. RCU).

If we decide that the current usage of spin_unlock_wait is valid, then I would much rather implement a version of it in the arm64 backend that does something like:

1: ldrex r1, [&lock]
if r1 indicates that lock is taken, branch back to 1b strex r1, [&lock]
if store failed, branch back to 1b

Quoted 4 lines

i.e. we don't just test the lock, but we also write it back atomically if we discover that it's free. That would then clear the exclusive monitor on any cores in the process of taking the lock and restore the ordering that we need.

We could clearly do something similar in PowerPC, but I suspect that this would hurt really badly on large systems, given that there are PowerPC systems with more than a thousand hardware threads. So one approach is ARM makes spin_unlock_wait() do the write, similar to spin_lock(); spin_lock(), but PowerPC relies on smp_mb__after_unlock_lock().

Or does someone have a better proposal?

Thanx, Paul

#63 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Hi Paul,

Quoted 26 lines · Paul E. McKenney
Quoted 20 lines · Will Deacon

I think we ended up concluding that smp_mb__after_unlock_lock is indeed required, but I don't think we should just resurrect the old definition, which doesn't keep UNLOCK -> LOCK distinct from RELEASE -> ACQUIRE. I'm still working on documenting the different types of transitivity that we identified in that thread, but it's slow going.

Also, as far as spin_unlock_wait is concerned, it is neither a LOCK or an UNLOCK and this barrier doesn't offer us anything. Sure, it might work because PPC defines it as smp_mb(), but it doesn't help on arm64 and defining the macro is overkill for us in most places (i.e. RCU).

If we decide that the current usage of spin_unlock_wait is valid, then I would much rather implement a version of it in the arm64 backend that does something like:

1: ldrex r1, [&lock]
if r1 indicates that lock is taken, branch back to 1b strex r1, [&lock]
if store failed, branch back to 1b

Quoted 4 lines

i.e. we don't just test the lock, but we also write it back atomically if we discover that it's free. That would then clear the exclusive monitor on any cores in the process of taking the lock and restore the ordering that we need.

Quoted 5 lines

We could clearly do something similar in PowerPC, but I suspect that this would hurt really badly on large systems, given that there are PowerPC systems with more than a thousand hardware threads. So one approach is ARM makes spin_unlock_wait() do the write, similar to spin_lock(); spin_lock(), but PowerPC relies on smp_mb__after_unlock_lock().

Sure, I'm certainly not trying to tell you how to do this for PPC, but the above would be better for arm64 (any huge system should be using the 8.1 atomics anyway).

Quoted 1 line

Or does someone have a better proposal?

I don't think I'm completely clear on the current proposal wrt smp_mb__after_unlock_lock. To summarise my understanding (in the context of Boqun's original example, which I've duplicated at the end of this mail):

* Putting smp_mb__after_unlock_lock() after the LOCK on CPU2 creates global order, by upgrading the UNLOCK -> LOCK to a full barrier. If we extend this to include the accesses made by the UNLOCK and LOCK as happening *before* the notional full barrier, then a from-read edge from CPU2 to CPU1 on `object' implies that the LOCK operation is observed by CPU1 before it writes object = NULL. So we can add this barrier and fix the test for PPC.

* Upgrading spin_unlock_wait to a LOCK operation (which is basically what I'm proposing for arm64) means that we now rely on LOCK -> LOCK being part of a single, total order (i.e. all CPUs agree on the order in which a lock was taken).

Assuming PPC has this global LOCK -> LOCK ordering, then we end up in a sticky situation defining the kernel's memory model because we don't have an architecture-agnostic semantic. The only way I can see to fix this is by adding something like smp_mb__between_lock_unlock_wait, but that's grim.

Do you see a way forward?

Will

--->8

	CPU 1			CPU 2			CPU 3
	==================	====================	==============
							spin_unlock(&lock);
				spin_lock(&lock):
				  r1 = *lock; // r1 == 0;
				o = READ_ONCE(object); // reordered here
	object = NULL;
	smp_mb();
	spin_unlock_wait(&lock);
				  *lock = 1;
	smp_mb();
	o->dead = true;
				if (o) // true
				  BUG_ON(o->dead); // true!!
#64 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Boqun Feng
Quoted 11 lines · Boqun Feng

Hmm.. probably incorrect.. because the ACQUIRE semantics of spin_lock() only guarantees that the memory operations following spin_lock() can't be reorder before the *LOAD* part of spin_lock() not the *STORE* part, i.e. the case below can happen(assuming the spin_lock() is implemented as ll/sc loop)

        spin_lock(&lock):
          r1 = *lock; // LL, r1 == 0
        o = READ_ONCE(object); // could be reordered here.
          *lock = 1; // SC

It may be worth noting that at least in theory, not only reads may pass the store. If the spin-lock is done as

        r1 = *lock   // read-acquire, r1 == 0
        *lock = 1    // SC

then even *writes* inside the locked region might pass up through the "*lock = 1".

So other CPU's - that haven't taken the spinlock - could see the modifications inside the critical region before they actually see the lock itself change.

Now, the point of spin_unlock_wait() (and "spin_is_locked()") should generally be that you have some external ordering guarantee that guarantees that the lock has been taken. For example, for the IPC semaphores, we do either one of:

(a) get large lock, then - once you hold that lock - wait for each small lock

or

(b) get small lock, then - once you hold that lock - check that the
largo lock is unlocked

and that's the case we should really worry about. The other uses of spin_unlock_wait() should have similar "I have other reasons to know I've seen that the lock was taken, or will never be taken after this because XYZ".

This is why powerpc has a memory barrier in "arch_spin_is_locked()". Exactly so that the "check that the other lock is unlocked" is guaranteed to be ordered wrt the store that gets the first lock.

It looks like ARM64 gets this wrong and is fundamentally buggy wrt "spin_is_locked()" (and, as a result, "spin_unlock_wait()").

BUT! And this is a bug BUT:

It should be noted that that is purely an ARM64 bug. Not a bug in our users. If you have a spinlock where the "get lock write" part of the lock can be delayed, then you have to have a "arch_spin_is_locked()" that has the proper memory barriers.

Of course, ARM still hides their architecture manuals in odd places, so I can't double-check. But afaik, ARM64 store-conditional is "store exclusive with release", and it has only release semantics, and ARM64 really does have the above bug.

On that note: can anybody point me to the latest ARM64 8.1 architecture manual in pdf form, without the "you have to register" crap? I thought ARM released it, but all my googling just points to the idiotic ARM service center that wants me to sign away something just to see the docs. Which I don't do.

Linus

#65 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 13 lines · Linus Torvalds
Quoted 11 lines · Boqun Feng

Hmm.. probably incorrect.. because the ACQUIRE semantics of spin_lock() only guarantees that the memory operations following spin_lock() can't be reorder before the *LOAD* part of spin_lock() not the *STORE* part, i.e. the case below can happen(assuming the spin_lock() is implemented as ll/sc loop)

        spin_lock(&lock):
          r1 = *lock; // LL, r1 == 0
        o = READ_ONCE(object); // could be reordered here.
          *lock = 1; // SC
Quoted 8 lines

It may be worth noting that at least in theory, not only reads may pass the store. If the spin-lock is done as

        r1 = *lock   // read-acquire, r1 == 0
        *lock = 1    // SC

then even *writes* inside the locked region might pass up through the "*lock = 1".

Right, but only if we didn't have the control dependency to branch back in the case that the SC failed. In that case, the lock would be broken because you'd dive into the critical section even if you failed to take the lock.

Quoted 21 lines

So other CPU's - that haven't taken the spinlock - could see the modifications inside the critical region before they actually see the lock itself change.

Now, the point of spin_unlock_wait() (and "spin_is_locked()") should generally be that you have some external ordering guarantee that guarantees that the lock has been taken. For example, for the IPC semaphores, we do either one of:

(a) get large lock, then - once you hold that lock - wait for each small lock

or

(b) get small lock, then - once you hold that lock - check that the
largo lock is unlocked

and that's the case we should really worry about. The other uses of spin_unlock_wait() should have similar "I have other reasons to know I've seen that the lock was taken, or will never be taken after this because XYZ".

Quoted 6 lines

This is why powerpc has a memory barrier in "arch_spin_is_locked()". Exactly so that the "check that the other lock is unlocked" is guaranteed to be ordered wrt the store that gets the first lock.

It looks like ARM64 gets this wrong and is fundamentally buggy wrt "spin_is_locked()" (and, as a result, "spin_unlock_wait()").

I don't see how a memory barrier would help us here, and Boqun's example had smp_mb() either sides of the spin_unlock_wait(). What we actually need is to make spin_unlock_wait more like a LOCK operation, so that it forces parallel lockers to replay their LL/SC sequences.

I'll write a patch once I've heard more back from Paul about smp_mb__after_unlock_lock().

Quoted 11 lines

BUT! And this is a bug BUT:

It should be noted that that is purely an ARM64 bug. Not a bug in our users. If you have a spinlock where the "get lock write" part of the lock can be delayed, then you have to have a "arch_spin_is_locked()" that has the proper memory barriers.

Of course, ARM still hides their architecture manuals in odd places, so I can't double-check. But afaik, ARM64 store-conditional is "store exclusive with release", and it has only release semantics, and ARM64 really does have the above bug.

The store-conditional in our spin_lock routine has no barrier semantics; they are enforced by the load-exclusive-acquire that pairs with it.

Quoted 5 lines

On that note: can anybody point me to the latest ARM64 8.1 architecture manual in pdf form, without the "you have to register" crap? I thought ARM released it, but all my googling just points to the idiotic ARM service center that wants me to sign away something just to see the docs. Which I don't do.

We haven't yet released a document for the 8.1 instructions, but I can certainly send you a copy when it's made available.

Will

author maintainer
#66 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Linus Torvalds
Quoted 9 lines · Linus Torvalds

Now, the point of spin_unlock_wait() (and "spin_is_locked()") should generally be that you have some external ordering guarantee that guarantees that the lock has been taken. For example, for the IPC semaphores, we do either one of:

(a) get large lock, then - once you hold that lock - wait for each small lock

or

Quoted 7 lines

(b) get small lock, then - once you hold that lock - check that the
largo lock is unlocked

and that's the case we should really worry about. The other uses of spin_unlock_wait() should have similar "I have other reasons to know I've seen that the lock was taken, or will never be taken after this because XYZ".

I don't think this is true for the usage in do_exit(), we have no knowledge on if pi_lock is taken or not. We just want to make sure that _if_ it were taken, we wait until it is released.

But I'm not sure where task_work_run() sits, at first reading it appears to also not be true -- there doesn't appear to be a reason we know a lock to be held.

It does however appear true for the usage in completion_done(), where by having tested x->done, we know a pi_lock _was_ held.

author maintainer
#67 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · Linus Torvalds

Now, the point of spin_unlock_wait() (and "spin_is_locked()") should generally be that you have some external ordering guarantee that guarantees that the lock has been taken. For example, for the IPC semaphores, we do either one of:

(a) get large lock, then - once you hold that lock - wait for each small lock

or

(b) get small lock, then - once you hold that lock - check that the
largo lock is unlocked

Quoted 8 lines
Quoted 4 lines

and that's the case we should really worry about. The other uses of spin_unlock_wait() should have similar "I have other reasons to know I've seen that the lock was taken, or will never be taken after this because XYZ".

I don't think this is true for the usage in do_exit(), we have no knowledge on if pi_lock is taken or not. We just want to make sure that _if_ it were taken, we wait until it is released.

And unless PPC would move to using RCsc locks with a SYNC in spin_lock(), I don't think it makes sense to add smp_mb__after_unlock_lock() to all tsk->pi_lock instances to fix this. As that is far more expensive than flipping the exit path to do spin_lock()+spin_unlock().

#68 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 23 lines · Peter Zijlstra
Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · Linus Torvalds

Now, the point of spin_unlock_wait() (and "spin_is_locked()") should generally be that you have some external ordering guarantee that guarantees that the lock has been taken. For example, for the IPC semaphores, we do either one of:

(a) get large lock, then - once you hold that lock - wait for each small lock

or

(b) get small lock, then - once you hold that lock - check that the
largo lock is unlocked

Quoted 8 lines
Quoted 4 lines

and that's the case we should really worry about. The other uses of spin_unlock_wait() should have similar "I have other reasons to know I've seen that the lock was taken, or will never be taken after this because XYZ".

I don't think this is true for the usage in do_exit(), we have no knowledge on if pi_lock is taken or not. We just want to make sure that _if_ it were taken, we wait until it is released.

Quoted 5 lines

And unless PPC would move to using RCsc locks with a SYNC in spin_lock(), I don't think it makes sense to add smp_mb__after_unlock_lock() to all tsk->pi_lock instances to fix this. As that is far more expensive than flipping the exit path to do spin_lock()+spin_unlock().

... or we upgrade spin_unlock_wait to a LOCK operation, which might be slightly cheaper than spin_lock()+spin_unlock().

Will

#69 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 24 lines · Will Deacon
Quoted 23 lines · Peter Zijlstra
Quoted 21 lines · Peter Zijlstra
Quoted 9 lines · Linus Torvalds

Now, the point of spin_unlock_wait() (and "spin_is_locked()") should generally be that you have some external ordering guarantee that guarantees that the lock has been taken. For example, for the IPC semaphores, we do either one of:

(a) get large lock, then - once you hold that lock - wait for each small lock

or

Quoted 7 lines

(b) get small lock, then - once you hold that lock - check that the
largo lock is unlocked

and that's the case we should really worry about. The other uses of spin_unlock_wait() should have similar "I have other reasons to know I've seen that the lock was taken, or will never be taken after this because XYZ".

I don't think this is true for the usage in do_exit(), we have no knowledge on if pi_lock is taken or not. We just want to make sure that _if_ it were taken, we wait until it is released.

Quoted 8 lines
Quoted 5 lines

And unless PPC would move to using RCsc locks with a SYNC in spin_lock(), I don't think it makes sense to add smp_mb__after_unlock_lock() to all tsk->pi_lock instances to fix this. As that is far more expensive than flipping the exit path to do spin_lock()+spin_unlock().

... or we upgrade spin_unlock_wait to a LOCK operation, which might be slightly cheaper than spin_lock()+spin_unlock().

Or we supply a heavyweight version of spin_unlock_wait() that forces the cache miss. But I bet that the difference in overhead between spin_lock()+spin_unlock() and the heavyweight version would be down in the noise.

Thanx, Paul

#70 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 31 lines · Paul E. McKenney
Quoted 30 lines · Will Deacon
Quoted 28 lines · Peter Zijlstra
Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · Linus Torvalds

Now, the point of spin_unlock_wait() (and "spin_is_locked()") should generally be that you have some external ordering guarantee that guarantees that the lock has been taken. For example, for the IPC semaphores, we do either one of:

(a) get large lock, then - once you hold that lock - wait for each small lock

or

(b) get small lock, then - once you hold that lock - check that the
largo lock is unlocked

Quoted 8 lines
Quoted 4 lines

and that's the case we should really worry about. The other uses of spin_unlock_wait() should have similar "I have other reasons to know I've seen that the lock was taken, or will never be taken after this because XYZ".

I don't think this is true for the usage in do_exit(), we have no knowledge on if pi_lock is taken or not. We just want to make sure that _if_ it were taken, we wait until it is released.

And unless PPC would move to using RCsc locks with a SYNC in spin_lock(), I don't think it makes sense to add smp_mb__after_unlock_lock() to all tsk->pi_lock instances to fix this. As that is far more expensive than flipping the exit path to do spin_lock()+spin_unlock().

Quoted 7 lines
Quoted 2 lines

... or we upgrade spin_unlock_wait to a LOCK operation, which might be slightly cheaper than spin_lock()+spin_unlock().

Or we supply a heavyweight version of spin_unlock_wait() that forces the cache miss. But I bet that the difference in overhead between spin_lock()+spin_unlock() and the heavyweight version would be down in the noise.

I'm not so sure. If the lock is ticket-based, then spin_lock() has to queue for its turn, whereas spin_unlock_wait could just wait for the next unlock.

Will

#71 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 35 lines · Will Deacon
Quoted 34 lines · Paul E. McKenney
Quoted 32 lines · Will Deacon
Quoted 23 lines · Peter Zijlstra
Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · Linus Torvalds

Now, the point of spin_unlock_wait() (and "spin_is_locked()") should generally be that you have some external ordering guarantee that guarantees that the lock has been taken. For example, for the IPC semaphores, we do either one of:

(a) get large lock, then - once you hold that lock - wait for each small lock

or

(b) get small lock, then - once you hold that lock - check that the
largo lock is unlocked

Quoted 8 lines
Quoted 4 lines

and that's the case we should really worry about. The other uses of spin_unlock_wait() should have similar "I have other reasons to know I've seen that the lock was taken, or will never be taken after this because XYZ".

I don't think this is true for the usage in do_exit(), we have no knowledge on if pi_lock is taken or not. We just want to make sure that _if_ it were taken, we wait until it is released.

Quoted 5 lines

And unless PPC would move to using RCsc locks with a SYNC in spin_lock(), I don't think it makes sense to add smp_mb__after_unlock_lock() to all tsk->pi_lock instances to fix this. As that is far more expensive than flipping the exit path to do spin_lock()+spin_unlock().

... or we upgrade spin_unlock_wait to a LOCK operation, which might be slightly cheaper than spin_lock()+spin_unlock().

Quoted 8 lines
Quoted 4 lines

Or we supply a heavyweight version of spin_unlock_wait() that forces the cache miss. But I bet that the difference in overhead between spin_lock()+spin_unlock() and the heavyweight version would be down in the noise.

I'm not so sure. If the lock is ticket-based, then spin_lock() has to queue for its turn, whereas spin_unlock_wait could just wait for the next unlock.

Fair point, and it actually applies to high-contention spinlocks as well, just a bit less deterministically. OK, given that I believe that we do see high contention on the lock in question, I withdraw any objections to a heavy-weight form of spin_unlock_wait().

Thanx, Paul

#72 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

In reply to Will Deacon
Quoted 3 lines · Will Deacon

... or we upgrade spin_unlock_wait to a LOCK operation, which might be slightly cheaper than spin_lock()+spin_unlock().

So traditionally the real concern has been the cacheline ping-pong part of spin_unlock_wait(). I think adding a memory barrier (that doesn't force any exclusive states, just ordering) to it is fine, but I don't think we want to necessarily have it have to get the cacheline into exclusive state.

Because if spin_unlock_wait() ends up having to get the spinlock cacheline (for example, by writing the same value back with a SC), I don't think spin_unlock_wait() will really be all that much cheaper than just getting the spinlock, and in that case we shouldn't play complicated ordering games.

On another issue:

I'm also looking at the ARM documentation for strx, and the _documentation_ says that it has no stronger ordering than a "store release", but I'm starting to wonder if that is actually true.

Because I do end up thinking that it does have the same "control dependency" to all subsequent writes (but not reads). So reads after the SC can percolate up, but I think writes are restricted.

Why? In order for the SC to be able to return success, the write itself may not have been actually done yet, but the cacheline for the write must have successfully be turned into exclusive ownership. Agreed?

That means that by the time a SC returns success, no other CPU can see the old value of the spinlock any more. So by the time any subsequent stores in the locked region can be visible to any other CPU's, the locked value of the lock itself has to be visible too.

Agreed?

So I think that in effect, when a spinlock is implemnted with LL/SC, the loads inside the locked region are only ordered wrt the acquire on the LL, but the stores can be considered ordered wrt the SC.

No?

So I think a _successful_ SC - is still more ordered than just any random store with release consistency.

Of course, I'm not sure that actually *helps* us, because I think the problem tends to be loads in the locked region moving up earlier than the actual store that sets the lock, but maybe it makes some difference.

Linus

#73 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Hi Linus,

Quoted 10 lines · Linus Torvalds
Quoted 3 lines · Will Deacon

... or we upgrade spin_unlock_wait to a LOCK operation, which might be slightly cheaper than spin_lock()+spin_unlock().

So traditionally the real concern has been the cacheline ping-pong part of spin_unlock_wait(). I think adding a memory barrier (that doesn't force any exclusive states, just ordering) to it is fine, but I don't think we want to necessarily have it have to get the cacheline into exclusive state.

The problem is, I don't think the memory-barrier buys you anything in the context of Boqun's example. In fact, he already had smp_mb() either side of the spin_unlock_wait() and its still broken on arm64 and ppc.

Paul is proposing adding a memory barrier after spin_lock() in the racing thread, but I personally think people will forget to add that.

Quoted 5 lines

Because if spin_unlock_wait() ends up having to get the spinlock cacheline (for example, by writing the same value back with a SC), I don't think spin_unlock_wait() will really be all that much cheaper than just getting the spinlock, and in that case we shouldn't play complicated ordering games.

It was the lock-fairness guarantees that I was concerned about. A spin_lock could place you into a queue, so you're no longer waiting for a single spin_unlock(), you're now waiting for *all* the spin_unlocks by the CPUs preceding you in the queue.

Quoted 6 lines

On another issue:

I'm also looking at the ARM documentation for strx, and the _documentation_ says that it has no stronger ordering than a "store release", but I'm starting to wonder if that is actually true.

Quoted 8 lines

Because I do end up thinking that it does have the same "control dependency" to all subsequent writes (but not reads). So reads after the SC can percolate up, but I think writes are restricted.

Why? In order for the SC to be able to return success, the write itself may not have been actually done yet, but the cacheline for the write must have successfully be turned into exclusive ownership. Agreed?

If the LL/SC logic hangs off the coherency logic, then yes, but there are other ways to build this (using a seperate "exclusive monitor" block) and the architecture caters for this, too. See below.

Quoted 6 lines

That means that by the time a SC returns success, no other CPU can see the old value of the spinlock any more. So by the time any subsequent stores in the locked region can be visible to any other CPU's, the locked value of the lock itself has to be visible too.

Agreed?

No. A successful SC is *not* multi-copy atomic, but you're right to point out that it provides more guarantees than a plain store. In particular, a successful SC cannot return its success value until its corresponding write has fixed its place in the coherence order for the location that it is updating.

To be more concrete (simplified AArch64 asm, X1 and X2 hold addresses of zero-initialised locations):

P0
LDXR X0, [X1]
ADD X0, X0, #1
STXR X0, [X1] // Succeeds

P1
LDR X0, [X1] // Reads 1
<dependency>
STR #1, [X2]

P2
LDR X0, [X2] // Reads 1
<dependency>
LDR X0, [X1] // **Not required to read 1**

However:

P0
LDXR X0, [X1]
ADD X0, X0, #1
STXR X0, [X1] // Succeeds

P1
LDR X0, [X1] // Reads 1
<dependency>
STR #1, [X2]

P2
LDR X0, [X2] // Reads 1
<dependency>
STR #2, [X1] // Location at [X1] must be ordered {0->1->2}

We can also extend this example so that P2 instead does:

P2
LDR X0, [X2] // Reads 1
<dependency>
LDXR X0, [X1]
ADD X0, X0, #1
STXR X0, [X1] // Succeeds; location at [x1] must be ordered {0->1->2}

i.e. the STXR cannot succeed until the coherence order has been resolved, which also requires the LDXR to return the up-to-date value.

Quoted 5 lines

So I think that in effect, when a spinlock is implemnted with LL/SC, the loads inside the locked region are only ordered wrt the acquire on the LL, but the stores can be considered ordered wrt the SC.

No?

I initially fell into the same trap because a control dependency between a load and a store is sufficient to create order (i.e. we don't speculate writes). An SC is different, though, because the control dependency can be resolved without the write being multi-copy atomic, whereas a read is required to return its data (i.e. complete) before the control hazard can be resolved.

I think that all of this means I should either:

(1) Update the arm64 spin_unlock_wait to use LDXR/STXR (perhaps with acquire semantics?)

- or -

(2) Replace spin_unlock_wait with spin_lock; spin_unlock, my worries about queuing notwithstanding.

The cacheline ping-pong in (1) can be mitigated somewhat by the use of wfe, so it won't be any worse than a spin_lock().

Will

#74 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 14 lines · Will Deacon

Hi Linus,

Quoted 10 lines · Linus Torvalds
Quoted 3 lines · Will Deacon

... or we upgrade spin_unlock_wait to a LOCK operation, which might be slightly cheaper than spin_lock()+spin_unlock().

So traditionally the real concern has been the cacheline ping-pong part of spin_unlock_wait(). I think adding a memory barrier (that doesn't force any exclusive states, just ordering) to it is fine, but I don't think we want to necessarily have it have to get the cacheline into exclusive state.

Quoted 6 lines

The problem is, I don't think the memory-barrier buys you anything in the context of Boqun's example. In fact, he already had smp_mb() either side of the spin_unlock_wait() and its still broken on arm64 and ppc.

Paul is proposing adding a memory barrier after spin_lock() in the racing thread, but I personally think people will forget to add that.

A mechanical check would certainly make me feel better about it, so that any lock that was passed to spin_unlock_wait() was required to have all acquisitions followed by smp_mb__after_unlock_lock() or some such. But I haven't yet given up on finding a better solution.

Thanx, Paul

#75 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 17 lines · Paul E. McKenney
Quoted 16 lines · Will Deacon
Quoted 10 lines · Linus Torvalds
Quoted 3 lines · Will Deacon

... or we upgrade spin_unlock_wait to a LOCK operation, which might be slightly cheaper than spin_lock()+spin_unlock().

So traditionally the real concern has been the cacheline ping-pong part of spin_unlock_wait(). I think adding a memory barrier (that doesn't force any exclusive states, just ordering) to it is fine, but I don't think we want to necessarily have it have to get the cacheline into exclusive state.

The problem is, I don't think the memory-barrier buys you anything in the context of Boqun's example. In fact, he already had smp_mb() either side of the spin_unlock_wait() and its still broken on arm64 and ppc.

Quoted 7 lines
Quoted 2 lines

Paul is proposing adding a memory barrier after spin_lock() in the racing thread, but I personally think people will forget to add that.

A mechanical check would certainly make me feel better about it, so that any lock that was passed to spin_unlock_wait() was required to have all acquisitions followed by smp_mb__after_unlock_lock() or some such. But I haven't yet given up on finding a better solution.

Right-o. I'll hack together the arm64 spin_unlock_wait fix, but hold off merging it for a few weeks in case we get struck by a sudden flash of inspiration.

Will

#76 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

Quoted 21 lines · Will Deacon
Quoted 20 lines · Paul E. McKenney
Quoted 18 lines · Will Deacon
Quoted 10 lines · Linus Torvalds
Quoted 3 lines · Will Deacon

... or we upgrade spin_unlock_wait to a LOCK operation, which might be slightly cheaper than spin_lock()+spin_unlock().

So traditionally the real concern has been the cacheline ping-pong part of spin_unlock_wait(). I think adding a memory barrier (that doesn't force any exclusive states, just ordering) to it is fine, but I don't think we want to necessarily have it have to get the cacheline into exclusive state.

The problem is, I don't think the memory-barrier buys you anything in the context of Boqun's example. In fact, he already had smp_mb() either side of the spin_unlock_wait() and its still broken on arm64 and ppc.

Paul is proposing adding a memory barrier after spin_lock() in the racing thread, but I personally think people will forget to add that.

Quoted 8 lines
Quoted 4 lines

A mechanical check would certainly make me feel better about it, so that any lock that was passed to spin_unlock_wait() was required to have all acquisitions followed by smp_mb__after_unlock_lock() or some such. But I haven't yet given up on finding a better solution.

Right-o. I'll hack together the arm64 spin_unlock_wait fix, but hold off merging it for a few weeks in case we get struck by a sudden flash of inspiration.

For completeness, here's what I've currently got. I've failed to measure any performance impact on my 8-core systems, but that's not surprising.

Will

--->8

Quoted 1 line

From da14adc1aef2f12b7a7def4d6b7dde254a91ebf1 Mon Sep 17 00:00:00 2001

From: Will Deacon <[email protected]>
Date: Thu, 19 Nov 2015 17:48:31 +0000
Subject: [PATCH] arm64: spinlock: serialise spin_unlock_wait against
concurrent lockers

Boqun Feng reported a rather nasty ordering issue with spin_unlock_wait on architectures implementing spin_lock with LL/SC sequences and acquire semantics:

 | CPU 1                   CPU 2                     CPU 3
 | ==================      ====================      ==============
 |                                                   spin_unlock(&lock);
 |                         spin_lock(&lock):
 |                           r1 = *lock; // r1 == 0;
 |                         o = READ_ONCE(object); // reordered here
 | object = NULL;
 | smp_mb();
 | spin_unlock_wait(&lock);
 |                           *lock = 1;
 | smp_mb();
 | o->dead = true;
 |                         if (o) // true
 |                           BUG_ON(o->dead); // true!!

The crux of the problem is that spin_unlock_wait(&lock) can return on CPU 1 whilst CPU 2 is in the process of taking the lock. This can be resolved by upgrading spin_unlock_wait to a LOCK operation, forcing it to serialise against a concurrent locker and giving it acquire semantics in the process (although it is not at all clear whether this is needed - different callers seem to assume different things about the barrier semantics and architectures are similarly disjoint in their implementations of the macro).

This patch implements spin_unlock_wait using an LL/SC sequence with acquire semantics on arm64. For v8.1 systems with the LSE atomics, the exclusive writeback is omitted, since the spin_lock operation is indivisible and no intermediate state can be observed.

---
 arch/arm64/include/asm/spinlock.h | 24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)
arch/arm64/include/asm/spinlock.h +22 -2
index c85e96d174a5..b531791a75ff 100644
@@ -26,9 +26,29 @@
  * The memory barriers are implicit with the load-acquire and store-release
  * instructions.
  */
+static inline void arch_spin_unlock_wait(arch_spinlock_t *lock)
+{
+	unsigned int tmp;
+	arch_spinlock_t lockval;
 
-#define arch_spin_unlock_wait(lock) \
-	do { while (arch_spin_is_locked(lock)) cpu_relax(); } while (0)
+	asm volatile(
+"	sevl\n"
+"1:	wfe\n"
+"2:	ldaxr	%w0, %2\n"
+"	eor	%w1, %w0, %w0, ror #16\n"
+"	cbnz	%w1, 1b\n"
+	ARM64_LSE_ATOMIC_INSN(
+	/* LL/SC */
+"	stxr	%w1, %w0, %2\n"
+	/* Serialise against any concurrent lockers */
+"	cbnz	%w1, 2b\n",
+	/* LSE atomics */
+"	nop\n"
+"	nop\n")
+	: "=&r" (lockval), "=&r" (tmp), "+Q" (*lock)
+	:
+	: "memory");
+}
 
 #define arch_spin_lock_flags(lock, flags) arch_spin_lock(lock)
 
Signature · 1 line
2.1.4
author maintainer
#77 lore raw

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

arch/arm64/include/asm/spinlock.h line 36

Quoted 11 lines · Will Deacon

For completeness, here's what I've currently got. I've failed to measure any performance impact on my 8-core systems, but that's not surprising.

arch/arm64/include/asm/spinlock.h +7 -0
+static inline void arch_spin_unlock_wait(arch_spinlock_t *lock)
+{
+	unsigned int tmp;
+	arch_spinlock_t lockval;
 
+	asm volatile(
+"	sevl\n"
+"1:	wfe\n"

Using WFE here would lower the cacheline bouncing pressure a bit I imagine. Sure we still pull it over into S(hared) after every store but we don't keep banging on it making the initial e(X)clusive grab hard.

arch/arm64/include/asm/spinlock.h line 47

Quoted 11 lines

+"2: ldaxr %w0, %2\n"
+" eor %w1, %w0, %w0, ror #16\n"
+" cbnz %w1, 1b\n"

arch/arm64/include/asm/spinlock.h +8 -0
+	ARM64_LSE_ATOMIC_INSN(
+	/* LL/SC */
+"	stxr	%w1, %w0, %2\n"
+	/* Serialise against any concurrent lockers */
+"	cbnz	%w1, 2b\n",
+	/* LSE atomics */
+"	nop\n"
+"	nop\n")

I find these ARM64_LSE macro thingies aren't always easy to read, its fairly easy to overlook the ',' separating the v8 and v8.1 parts, esp. if you have further interleaving comments like in the above.

Quoted 4 lines
arch/arm64/include/asm/spinlock.h +4 -0
+	: "=&r" (lockval), "=&r" (tmp), "+Q" (*lock)
+	:
+	: "memory");
+}