Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1240626 > unrolled thread

Re: [PATCH] Documentation: Remove misleading examples of the barriers in wake_*()

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Peter Zijlstra <peterz@infradead.org> - 2015-10-06 18:10 +0200
    Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Peter Zijlstra <peterz@infradead.org> - 2015-10-06 18:30 +0200
      Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Will Deacon <will.deacon@arm.com> - 2015-10-06 18:40 +0200
    Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Peter Zijlstra <peterz@infradead.org> - 2015-10-06 22:10 +0200
    Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Peter Zijlstra <peterz@infradead.org> - 2015-10-07 13:20 +0200
      Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-10-07 17:50 +0200

#1240626 — Re: [PATCH] Documentation: Remove misleading examples of the barriers in wake_*()

On Mon, Sep 21, 2015 at 07:46:11PM +0200, Oleg Nesterov wrote:
> On 09/18, Peter Zijlstra wrote:
> >
> > the text is correct, right?
> 
> Yes, it looks good to me and helpful.
> 
> But damn. I forgot why exactly try_to_wake_up() needs rmb() after
> ->on_cpu check... It looks reasonable in any case, but I do not
> see any strong reason immediately.

I read it like the smp_rmb() we have for
acquire__after_spin_is_unlocked. Except, as you note below, we need to
need an smp_read_barrier_depends for control barriers as well....

(I'm starting to think we're having more control deps what we were
thinking...)

--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -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();
 
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -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);


Updates the comments to clarify the release/acquire pair on p->on_cpu.

> Say,
> 
> 	p->sched_contributes_to_load = !!task_contributes_to_load(p);
> 	p->state = TASK_WAKING;
> 
> we can actually do this before "while (p->on_cpu)", afaics. However
> we must not do this before the previous p->on_rq check.

No, we must not touch the task before p->on_cpu is cleared, up until
that point the task is owned by the 'previous' CPU.

> So perhaps this rmb() helps to ensure task_contributes_to_load() can't
> happen before p->on_rq check...
> 
> As for "p->state = TASK_WAKING" we have the control dependency in both
> cases. But the modern fashion suggests to use _CTRL().

Yes, but I'm not sure we should go write:

	while (READ_ONCE_CTRL(p->on_cpu))
		cpu_relax();

Or:

	while (p->on_cpu)
		cpu_relax();

	smp_read_barrier_depends();

It seems to me that doing the smp_mb() (for Alpha) inside the loop might
be sub-optimal.

That said, it would be good if Paul (or anyone really) can explain to me
the reason for: 5af4692a75da ("smp: Make control dependencies work on
Alpha, improve documentation"). The Changelog simply states that Alpha
needs the mb, but not how/why etc.

> Although cpu_relax()
> should imply barrier(), but afaik this is not documented.

I think we're relying on that in many places..

> In short, I got lost ;) Now I don't even understand why we do not need
> another rmb() between p->on_rq and p->on_cpu. Suppose a thread T does
> 
> 	set_current_state(...);
> 	schedule();
> 
> it can be preempted in between, after that we have "on_rq && !on_cpu".
> Then it gets CPU again and calls schedule() which clears on_rq.
> 
> What guarantees that if ttwu() sees on_rq == 0 cleared by schedule()
> then it can _not_ still see the old value of on_cpu == 0?

Right, let me go have a think about that ;-)
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1240677

On Tue, Oct 06, 2015 at 06:04:50PM +0200, Peter Zijlstra wrote:
> On Mon, Sep 21, 2015 at 07:46:11PM +0200, Oleg Nesterov wrote:
> > On 09/18, Peter Zijlstra wrote:
> > >
> > > the text is correct, right?
> > 
> > Yes, it looks good to me and helpful.
> > 
> > But damn. I forgot why exactly try_to_wake_up() needs rmb() after
> > ->on_cpu check... It looks reasonable in any case, but I do not
> > see any strong reason immediately.
> 
> I read it like the smp_rmb() we have for
> acquire__after_spin_is_unlocked. Except, as you note below, we need to
> need an smp_read_barrier_depends for control barriers as well....

> Yes, but I'm not sure we should go write:
> 
> 	while (READ_ONCE_CTRL(p->on_cpu))
> 		cpu_relax();
> 
> Or:
> 
> 	while (p->on_cpu)
> 		cpu_relax();
> 
> 	smp_read_barrier_depends();
> 
> It seems to me that doing the smp_mb() (for Alpha) inside the loop might
> be sub-optimal.

And also referring to:

  lkml.kernel.org/r/20150812133109.GA8266@redhat.com

Do we want something like this?

#define smp_spin_acquire(cond) do {		\
	while (cond)				\
		cpu_relax();			\
	smp_read_barrier_depends(); /* ctrl */	\
	smp_rmb(); /* ctrl + rmb := acquire */	\
} while (0)

And use it like:

	smp_spin_acquire(raw_spin_is_locked(&task->pi_lock));

That might work for your task_work_run() and the scheduler case,
although it might be somewhat awkward for sem_wait_array().
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1240703

On Tue, Oct 06, 2015 at 06:24:23PM +0200, Peter Zijlstra wrote:
> On Tue, Oct 06, 2015 at 06:04:50PM +0200, Peter Zijlstra wrote:
> > On Mon, Sep 21, 2015 at 07:46:11PM +0200, Oleg Nesterov wrote:
> > > On 09/18, Peter Zijlstra wrote:
> > > >
> > > > the text is correct, right?
> > > 
> > > Yes, it looks good to me and helpful.
> > > 
> > > But damn. I forgot why exactly try_to_wake_up() needs rmb() after
> > > ->on_cpu check... It looks reasonable in any case, but I do not
> > > see any strong reason immediately.
> > 
> > I read it like the smp_rmb() we have for
> > acquire__after_spin_is_unlocked. Except, as you note below, we need to
> > need an smp_read_barrier_depends for control barriers as well....
> 
> > Yes, but I'm not sure we should go write:
> > 
> > 	while (READ_ONCE_CTRL(p->on_cpu))
> > 		cpu_relax();
> > 
> > Or:
> > 
> > 	while (p->on_cpu)
> > 		cpu_relax();
> > 
> > 	smp_read_barrier_depends();
> > 
> > It seems to me that doing the smp_mb() (for Alpha) inside the loop might
> > be sub-optimal.
> 
> And also referring to:
> 
>   lkml.kernel.org/r/20150812133109.GA8266@redhat.com
> 
> Do we want something like this?
> 
> #define smp_spin_acquire(cond) do {		\
> 	while (cond)				\
> 		cpu_relax();			\
> 	smp_read_barrier_depends(); /* ctrl */	\
> 	smp_rmb(); /* ctrl + rmb := acquire */	\
> } while (0)
> 
> And use it like:
> 
> 	smp_spin_acquire(raw_spin_is_locked(&task->pi_lock));
> 
> That might work for your task_work_run() and the scheduler case,
> although it might be somewhat awkward for sem_wait_array().

I could *really* use something like this for implementing power-saving
busy loops for arch/arm64 (i.e. in the qrwlock code). We have a WFE
instruction (wait for event) that can stop the processor clock and resume
it when the exclusive monitor is cleared (i.e. a cacheline migrates to
another CPU). That means we can implement a targetted wake-up when an
unlocker writes to a node in a queued lock, which isn't something
expressible with cpu_relax alone.

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

[toc] | [prev] | [next] | [standalone]

#1240953

> On Mon, Sep 21, 2015 at 07:46:11PM +0200, Oleg Nesterov wrote:

> > In short, I got lost ;) Now I don't even understand why we do not need
> > another rmb() between p->on_rq and p->on_cpu. Suppose a thread T does
> > 
> > 	set_current_state(...);
> > 	schedule();
> > 
> > it can be preempted in between, after that we have "on_rq && !on_cpu".
> > Then it gets CPU again and calls schedule() which clears on_rq.
> > 
> > What guarantees that if ttwu() sees on_rq == 0 cleared by schedule()
> > then it can _not_ still see the old value of on_cpu == 0?

I think you're right. Does the below adequately explain things?

I'll have another look tomorrow to see if I still agree with myself, but
for now I think I've convinced myself you're right.

---
Subject: sched: Fix race in try_to_wake_up() vs schedule()

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.

Reported-by: Oleg Nesterov <oleg@redhat.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/sched/core.c |   19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -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.
 	 */
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1241381

On Tue, Oct 06, 2015 at 06:04:50PM +0200, Peter Zijlstra wrote:
> That said, it would be good if Paul (or anyone really) can explain to me
> the reason for: 5af4692a75da ("smp: Make control dependencies work on
> Alpha, improve documentation"). The Changelog simply states that Alpha
> needs the mb, but not how/why etc.

Also, I suppose Documentation/circular-buffer.txt needs help.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1241607

On Wed, Oct 07, 2015 at 01:10:24PM +0200, Peter Zijlstra wrote:
> On Tue, Oct 06, 2015 at 06:04:50PM +0200, Peter Zijlstra wrote:
> > That said, it would be good if Paul (or anyone really) can explain to me
> > the reason for: 5af4692a75da ("smp: Make control dependencies work on
> > Alpha, improve documentation"). The Changelog simply states that Alpha
> > needs the mb, but not how/why etc.

"Alpha AXP Architecture Reference Manual, Second Edition", Sites & Witek,
page 5-20, Section 5.6.3, "Implied Barriers":

	In Alpha AXP, there are no implied barriers.  If an implied
	barrier is needed for functionally correct access to shared
	data, it must be written as an explicit instruction.  (Software
	must explicitly include any needed MB, WMB, or CALL_PAL IMB
	instructions.)

On exactly how the hardware might choose not to respect control
dependencies, I must defer to someone who knows about the Alpha hardware.
On my last opportunity to discuss this with Alpha architects, I was
concerned only about data dependencies, and didn't think to ask about
control dependencies.

> Also, I suppose Documentation/circular-buffer.txt needs help.

Who wrote that???  ;-)

How about the following?

							Thanx, Paul

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

diff --git a/Documentation/circular-buffers.txt b/Documentation/circular-buffers.txt
index 88951b179262..c71c0cab7bbb 100644
--- a/Documentation/circular-buffers.txt
+++ b/Documentation/circular-buffers.txt
@@ -161,7 +161,7 @@ The producer will look something like this:
 
 	unsigned long head = buffer->head;
 	/* The spin_unlock() and next spin_lock() provide needed ordering. */
-	unsigned long tail = ACCESS_ONCE(buffer->tail);
+	unsigned long tail = READ_ONCE_CTRL(buffer->tail);
 
 	if (CIRC_SPACE(head, tail, buffer->size) >= 1) {
 		/* insert one item into the buffer */
@@ -222,7 +222,7 @@ This will instruct the CPU to make sure the index is up to date before reading
 the new item, and then it shall make sure the CPU has finished reading the item
 before it writes the new tail pointer, which will erase the item.
 
-Note the use of ACCESS_ONCE() and smp_load_acquire() to read the
+Note the use of READ_ONCE_CTRL() and smp_load_acquire() to read the
 opposition index.  This prevents the compiler from discarding and
 reloading its cached value - which some compilers will do across
 smp_read_barrier_depends().  This isn't strictly needed if you can

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

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web