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

Groups > linux.kernel > #1220436 > unrolled thread

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

Back to article view | Back to linux.kernel

Contents

  [PATCH] Documentation: Remove misleading examples of the barriers in wake_*() Boqun Feng <boqun.feng@gmail.com> - 2015-09-08 03:20 +0200
    Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-09-09 21:30 +0200
      Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Boqun Feng <boqun.feng@gmail.com> - 2015-09-10 04:20 +0200
        Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Oleg Nesterov <oleg@redhat.com> - 2015-09-10 20:00 +0200
          Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Boqun Feng <boqun.feng@gmail.com> - 2015-09-11 19:10 +0200
          Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Peter Zijlstra <peterz@infradead.org> - 2015-09-17 15:10 +0200
            Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Oleg Nesterov <oleg@redhat.com> - 2015-09-17 19:10 +0200
              Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Peter Zijlstra <peterz@infradead.org> - 2015-09-18 09:00 +0200
                Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Oleg Nesterov <oleg@redhat.com> - 2015-09-21 19:50 +0200
            Re: [PATCH] Documentation: Remove misleading examples of the  barriers in wake_*() Boqun Feng <boqun.feng@gmail.com> - 2015-09-24 15:30 +0200

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

Two examples for barriers in wake_up() and co. in memory-barriers.txt
are misleading, along with their explanations:

1.	The example which wanted to explain the write barrier in
	wake_up() and co. [spotted by Oleg Nesterov <oleg@redhat.com>]

2.	The example which wanted to explain that the write barriers in
	wake_up() and co. only exist iff a wakeup actually occurs.

For example #1, according to Oleg Nesterov:

>
>       The barrier occurs before the task state is cleared
>
> is not actually right. This is misleading. What is really important is that
> we have a barrier before we _read_ the task state. And again, again, the
> fact that we actually have the write barrier is just the implementation
> detail.
>

And the example #2 is actually an example which could explain that the
barriers in wait_event() and co. only exist iff a sleep actually occurs.

Further more, these barriers are only used for the correctness of
sleeping and waking up, i.e. they exist only to guarantee the ordering
of memory accesses to the task states and the global variables
indicating an event. Users can't rely on them for other things, so
memory-barriers.txt had better to call this out and remove the
misleading examples.

This patch removes the misleading examples along with their
explanations, calls it out that those implied barriers are only for
sleep and wakeup related variables and adds a new example to explain the
implied barrier in wake_up() and co.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 Documentation/memory-barriers.txt | 42 +++++++++++++++++----------------------
 1 file changed, 18 insertions(+), 24 deletions(-)

diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index eafa6a5..07de72f 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -1948,6 +1948,10 @@ these appear to happen in the right order, the primitives to begin the process
 of going to sleep, and the primitives to initiate a wake up imply certain
 barriers.
 
+[!] Note that these implied barriers are only for the correctness of sleep and
+wake-up. So don't rely on these barriers for things that are neither the task
+states nor the global variables indicating the events.
+
 Firstly, the sleeper normally follows something like this sequence of events:
 
 	for (;;) {
@@ -1997,32 +2001,22 @@ or:
 	event_indicated = 1;
 	wake_up_process(event_daemon);
 
-A write memory barrier is implied by wake_up() and co. if and only if they wake
-something up.  The barrier occurs before the task state is cleared, and so sits
-between the STORE to indicate the event and the STORE to set TASK_RUNNING:
-
-	CPU 1				CPU 2
-	===============================	===============================
-	set_current_state();		STORE event_indicated
-	  smp_store_mb();		wake_up();
-	    STORE current->state	  <write barrier>
-	    <general barrier>		  STORE current->state
-	LOAD event_indicated
+A memory barrier is implied by wake_up() and co. if and only if they wake
+something up. The memory barrier here is not necessary to be a general barrier,
+it only needs to guarantee a STORE preceding this barrier can never be
+reordered after a LOAD following this barrier(i.e. a STORE-LOAD barrier). This
+barrier guarantees that the event has been indicated before the waker read the
+wakee's task state:
 
-To repeat, this write memory barrier is present if and only if something
-is actually awakened.  To see this, consider the following sequence of
-events, where X and Y are both initially zero:
+	CPU 1
+	===============================
+	STORE event_indicated;
+	wake_up_process(wakee);
+	  <STORE-LOAD barrier>
+	  LOAD wakee->state;
 
-	CPU 1				CPU 2
-	===============================	===============================
-	X = 1;				STORE event_indicated
-	smp_mb();			wake_up();
-	Y = 1;				wait_event(wq, Y == 1);
-	wake_up();			  load from Y sees 1, no memory barrier
-					load from X might see 0
-
-In contrast, if a wakeup does occur, CPU 2's load from X would be guaranteed
-to see 1.
+This barrier pairs with the general barrier implied by set_current_state() on
+the sleeper side.
 
 The available waker functions include:
 
-- 
2.5.1

--
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]

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

On Tue, Sep 08, 2015 at 09:14:01AM +0800, Boqun Feng wrote:
> Two examples for barriers in wake_up() and co. in memory-barriers.txt
> are misleading, along with their explanations:
> 
> 1.	The example which wanted to explain the write barrier in
> 	wake_up() and co. [spotted by Oleg Nesterov <oleg@redhat.com>]
> 
> 2.	The example which wanted to explain that the write barriers in
> 	wake_up() and co. only exist iff a wakeup actually occurs.
> 
> For example #1, according to Oleg Nesterov:
> 
> >
> >       The barrier occurs before the task state is cleared
> >
> > is not actually right. This is misleading. What is really important is that
> > we have a barrier before we _read_ the task state. And again, again, the
> > fact that we actually have the write barrier is just the implementation
> > detail.
> >
> 
> And the example #2 is actually an example which could explain that the
> barriers in wait_event() and co. only exist iff a sleep actually occurs.
> 
> Further more, these barriers are only used for the correctness of
> sleeping and waking up, i.e. they exist only to guarantee the ordering
> of memory accesses to the task states and the global variables
> indicating an event. Users can't rely on them for other things, so
> memory-barriers.txt had better to call this out and remove the
> misleading examples.
> 
> This patch removes the misleading examples along with their
> explanations, calls it out that those implied barriers are only for
> sleep and wakeup related variables and adds a new example to explain the
> implied barrier in wake_up() and co.
> 
> Signed-off-by: Boqun Feng <boqun.feng@gmail.com>

At this point, I would favor replacing that entire section with a short
paragraph describing what guarantees are provided, perhaps with an example
showing what added barriers/locks/whatever are required.  My feeling is
that we should avoid saying too much about the internals of wait_event()
and wake_up().

Or am I missing something?

							Thanx, Paul

> ---
>  Documentation/memory-barriers.txt | 42 +++++++++++++++++----------------------
>  1 file changed, 18 insertions(+), 24 deletions(-)
> 
> diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
> index eafa6a5..07de72f 100644
> --- a/Documentation/memory-barriers.txt
> +++ b/Documentation/memory-barriers.txt
> @@ -1948,6 +1948,10 @@ these appear to happen in the right order, the primitives to begin the process
>  of going to sleep, and the primitives to initiate a wake up imply certain
>  barriers.
> 
> +[!] Note that these implied barriers are only for the correctness of sleep and
> +wake-up. So don't rely on these barriers for things that are neither the task
> +states nor the global variables indicating the events.
> +
>  Firstly, the sleeper normally follows something like this sequence of events:
> 
>  	for (;;) {
> @@ -1997,32 +2001,22 @@ or:
>  	event_indicated = 1;
>  	wake_up_process(event_daemon);
> 
> -A write memory barrier is implied by wake_up() and co. if and only if they wake
> -something up.  The barrier occurs before the task state is cleared, and so sits
> -between the STORE to indicate the event and the STORE to set TASK_RUNNING:
> -
> -	CPU 1				CPU 2
> -	===============================	===============================
> -	set_current_state();		STORE event_indicated
> -	  smp_store_mb();		wake_up();
> -	    STORE current->state	  <write barrier>
> -	    <general barrier>		  STORE current->state
> -	LOAD event_indicated
> +A memory barrier is implied by wake_up() and co. if and only if they wake
> +something up. The memory barrier here is not necessary to be a general barrier,
> +it only needs to guarantee a STORE preceding this barrier can never be
> +reordered after a LOAD following this barrier(i.e. a STORE-LOAD barrier). This
> +barrier guarantees that the event has been indicated before the waker read the
> +wakee's task state:
> 
> -To repeat, this write memory barrier is present if and only if something
> -is actually awakened.  To see this, consider the following sequence of
> -events, where X and Y are both initially zero:
> +	CPU 1
> +	===============================
> +	STORE event_indicated;
> +	wake_up_process(wakee);
> +	  <STORE-LOAD barrier>
> +	  LOAD wakee->state;
> 
> -	CPU 1				CPU 2
> -	===============================	===============================
> -	X = 1;				STORE event_indicated
> -	smp_mb();			wake_up();
> -	Y = 1;				wait_event(wq, Y == 1);
> -	wake_up();			  load from Y sees 1, no memory barrier
> -					load from X might see 0
> -
> -In contrast, if a wakeup does occur, CPU 2's load from X would be guaranteed
> -to see 1.
> +This barrier pairs with the general barrier implied by set_current_state() on
> +the sleeper side.
> 
>  The available waker functions include:
> 
> -- 
> 2.5.1
> 

--
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]

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

[Multipart message — attachments visible in raw view] — view raw

On Wed, Sep 09, 2015 at 12:28:22PM -0700, Paul E. McKenney wrote:
> On Tue, Sep 08, 2015 at 09:14:01AM +0800, Boqun Feng wrote:
> > Two examples for barriers in wake_up() and co. in memory-barriers.txt
> > are misleading, along with their explanations:
> > 
> > 1.	The example which wanted to explain the write barrier in
> > 	wake_up() and co. [spotted by Oleg Nesterov <oleg@redhat.com>]
> > 
> > 2.	The example which wanted to explain that the write barriers in
> > 	wake_up() and co. only exist iff a wakeup actually occurs.
> > 
> > For example #1, according to Oleg Nesterov:
> > 
> > >
> > >       The barrier occurs before the task state is cleared
> > >
> > > is not actually right. This is misleading. What is really important is that
> > > we have a barrier before we _read_ the task state. And again, again, the
> > > fact that we actually have the write barrier is just the implementation
> > > detail.
> > >
> > 
> > And the example #2 is actually an example which could explain that the
> > barriers in wait_event() and co. only exist iff a sleep actually occurs.
> > 
> > Further more, these barriers are only used for the correctness of
> > sleeping and waking up, i.e. they exist only to guarantee the ordering
> > of memory accesses to the task states and the global variables
> > indicating an event. Users can't rely on them for other things, so
> > memory-barriers.txt had better to call this out and remove the
> > misleading examples.
> > 
> > This patch removes the misleading examples along with their
> > explanations, calls it out that those implied barriers are only for
> > sleep and wakeup related variables and adds a new example to explain the
> > implied barrier in wake_up() and co.
> > 
> > Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
> 
> At this point, I would favor replacing that entire section with a short
> paragraph describing what guarantees are provided, perhaps with an example
> showing what added barriers/locks/whatever are required.  My feeling is
> that we should avoid saying too much about the internals of wait_event()
> and wake_up().

Good idea!

However, I think a little more words help understand. So I keep the
original first paragraph and also add a paragraph for NOTE which, I
think, may be a little redundant although ;-)

How about the following new whole section?


SLEEP AND WAKE-UP FUNCTIONS
---------------------------

Sleeping and waking on an event flagged in global data can be viewed as an
interaction between two pieces of data: the task state of the task waiting for
the event and the global data used to indicate the event.  To make sure that
these appear to happen in the right order, the primitives to begin the process
of going to sleep, and the primitives to initiate a wake up imply certain
barriers.

The memory ordering requirement here can be expressed by two STORE-LOAD
barriers(barriers which can guarantee a STORE perceding it can never be
reordered after a LOAD following it). One STORE-LOAD barrier is needed on the
sleeper/wakee side, before reading a variable used to indicate the event and
after setting the state of the current task. Another STORE-LOAD barrier is
needed on the waker side, before reading the state of the wakee task and after
setting a variable used to indicate the event. These two barriers can pair with
each other to avoid race conditions between sleepers/wakees and wakers:

	sleepr/wakee on CPU 1		waker on CPU 2
	========================	========================
	{ wakee->state = TASK_RUNNING, event_indicated = 0 }
	STORE current->state=TASK_INTERRUPTIBLE
	<STORE-LOAD barrier>
	c = LOAD event_indicated	
					STORE event_indicated=1
					<STORE-LOAD barrier>
					s = LOAD wakee->state	

	assert(!(c==0 && s == TASK_RUNNING));

A STORE-LOAD barrier is implied after setting task state by wait-related functions:

	prepare_to_wait();
	prepare_to_wait_exclusive();
	prepare_to_wait_event();

A STORE-LOAD barrier is implied before reading task state by wake-related functions:

	complete();
	wake_up();
	wake_up_all();
	wake_up_bit();
	wake_up_interruptible();
	wake_up_interruptible_all();
	wake_up_interruptible_nr();
	wake_up_interruptible_poll();
	wake_up_interruptible_sync();
	wake_up_interruptible_sync_poll();
	wake_up_locked();
	wake_up_locked_poll();
	wake_up_nr();
	wake_up_poll();
	wake_up_process();

Make sure an appropriate wake-related function is called after setting a global
data used to indicate a event.

[!] Note that these implied barriers are only for the correctness of sleep and
wake-up. So don't rely on these barriers for things that are neither the task
states nor the global variables indicating the events.


git log --stat for this is:

 1 file changed, 29 insertions(+), 108 deletions(-)

, which I think it's better, thanks to your advice ;-)


I will rewrite the commit message and send a new patch if this looks to
you.

Regards,
Boqun

> 
> Or am I missing something?
> 
> 							Thanx, Paul

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

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

On 09/10, Boqun Feng wrote:
>
> On Wed, Sep 09, 2015 at 12:28:22PM -0700, Paul E. McKenney wrote:
> > My feeling is
> > that we should avoid saying too much about the internals of wait_event()
> > and wake_up().

I feel the same. I simply can't understand what we are trying to
document ;)

For example,

> A STORE-LOAD barrier is implied after setting task state by wait-related functions:
>
> 	prepare_to_wait();
> 	prepare_to_wait_exclusive();
> 	prepare_to_wait_event();

I won't argue, but to me this looks misleading too.

Yes, prepare_to_wait()->set_current_state() implies mb() and thus
a STORE-LOAD barrier.

But this has nothing to do with the explanation above. We do not
need this barrier to avoid the race with wake_up(). Again, again,
we can safely rely on wq->lock and acquire/release semantics.

This barrier is only needed if you do, say,

	CONDITION = 1;

	if (waitqueue_active(wq))
		wake_up(wq);

And note that the code above is wrong without another mb() after
CONDITION = 1.

Oleg.

--
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]

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

[Multipart message — attachments visible in raw view] — view raw

Hi Oleg,

On Thu, Sep 10, 2015 at 07:55:57PM +0200, Oleg Nesterov wrote:
> On 09/10, Boqun Feng wrote:
> >
> > On Wed, Sep 09, 2015 at 12:28:22PM -0700, Paul E. McKenney wrote:
> > > My feeling is
> > > that we should avoid saying too much about the internals of wait_event()
> > > and wake_up().
> 
> I feel the same. I simply can't understand what we are trying to
> document ;)
> 

What I think we should document here is what memory ordering guarantee
we can rely on with these sleep/wakeup primitives, or what kind of
barriers these primitives imply. Because the structure of the
memory-barriers.txt here is:

 (*) Implicit kernel memory barriers.

     - Locking functions.
     - Interrupt disabling functions.
   ->- Sleep and wake-up functions.<-
     - Miscellaneous functions.

> For example,
> 
> > A STORE-LOAD barrier is implied after setting task state by wait-related functions:
> >
> > 	prepare_to_wait();
> > 	prepare_to_wait_exclusive();
> > 	prepare_to_wait_event();
> 
> I won't argue, but to me this looks misleading too.
> 
> Yes, prepare_to_wait()->set_current_state() implies mb() and thus
> a STORE-LOAD barrier.
> 
> But this has nothing to do with the explanation above. We do not
> need this barrier to avoid the race with wake_up(). Again, again,
> we can safely rely on wq->lock and acquire/release semantics.
> 

Yes, you are right. prepare_to_wait*() should be put here. What should
be put here is set_current_state(), whose STORE-LOAD barrier pairs with
the STORE-LOAD barrier of wake_up_process().

> This barrier is only needed if you do, say,
> 
> 	CONDITION = 1;
> 
> 	if (waitqueue_active(wq))
> 		wake_up(wq);
> 
> And note that the code above is wrong without another mb() after
> CONDITION = 1.
> 

Understood, I admit I didn't realize this before.

To summarize, we have three kinds of data related to sleep/wakeup:

*	CONDITIONs: global data used to indicate events

*	task states

*	wait queues(may not be used, if users use set_current_state() +
	schedule() to sleep and wake_up_process() to wake up)

IIUC, the race on wait queues are almost avoided because of wq->locks,
and if a wait queue is used, race on task states are avoided because
states are readed and written with a wq->lock held in sleep/wakeup
functions. So only in two cases we need STORE-LOAD barriers to avoid the
race:

1.	no wait queue used(e.g. rcu_boost_kthread), we need STORE-LOAD
	to order accesses to task states and CONDITIONs, so we have
	barriers in wake_up_process() and set_current_state().

2.	wait queue accessed without a wq->lock held(e.g. your example),
	we need STORE-LOAD to order accesses to wait queues and CONDITIONs

Since case #1 still exists in kernel, we'd better keep this section in
memory-barriers.txt, however, I'm not sure whether we should mention
case #2 in this section.

Here is a modified version, without mentioning case #2:


SLEEP AND WAKE-UP FUNCTIONS
---------------------------

Sleeping and waking on an event flagged in global data can be viewed as an
interaction between two pieces of data: the task state of the task waiting for
the event and the global data used to indicate the event.  To make sure that
these appear to happen in the right order, the primitives to begin the process
of going to sleep, and the primitives to initiate a wake up imply certain
barriers.

If a wait queue is used, all accesses to task states are protected by the lock
of the wait queue, so the race on task states are avoided. However, if no wait
queue used, we need some memory ordering guantanee to avoid the race between
sleepers/wakees and wakers.

The memory ordering requirement here can be expressed by two STORE-LOAD
barriers(barriers which can guarantee a STORE perceding it can never be
reordered after a LOAD following it). One STORE-LOAD barrier is needed on the
sleeper/wakee side, before reading a variable used to indicate the event and
after setting the state of the current task. Another STORE-LOAD barrier is
needed on the waker side, before reading the state of the wakee task and after
setting a variable used to indicate the event. These two barriers can pair with
each other to avoid race conditions between sleepers/wakees and wakers:

	sleepr/wakee on CPU 1		waker on CPU 2
	========================	========================
	{ wakee->state = TASK_RUNNING, event_indicated = 0 }
	STORE current->state=TASK_INTERRUPTIBLE
	<STORE-LOAD barrier>
	c = LOAD event_indicated	
					STORE event_indicated=1
					<STORE-LOAD barrier>
					s = LOAD wakee->state	

	assert(!(c==0 && s == TASK_RUNNING));

A STORE-LOAD barrier is implied after setting task state in set_current_state()
and before reading task state in wake_up_process()

Make sure call set_current_state() before read the global data used to indicate
event and sleep, and call wake_up_process() after set the global data used to
indicate a event.


Regards,
Boqun

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

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

On Thu, Sep 10, 2015 at 07:55:57PM +0200, Oleg Nesterov wrote:
> On 09/10, Boqun Feng wrote:
> >
> > On Wed, Sep 09, 2015 at 12:28:22PM -0700, Paul E. McKenney wrote:
> > > My feeling is
> > > that we should avoid saying too much about the internals of wait_event()
> > > and wake_up().
> 
> I feel the same. I simply can't understand what we are trying to
> document ;)

So I've been sitting on this for a while and figured I'd finish it now.

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

Included in it are some of the details on this subject, because a wakeup
has two prior states that are of importance, the tasks own prior state
and the wakeup state, both should be considered in the 'program order'
flow.

So maybe we can reduce the description in memory-barriers to this
'split' program order guarantee, where a woken task must observe both
its own prior state and its wakee state.


---
 kernel/sched/core.c | 137 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 137 insertions(+)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 6ab415aa15c4..4fffde6f7c08 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -1897,6 +1897,143 @@ static void ttwu_queue(struct task_struct *p, int cpu)
 	raw_spin_unlock(&rq->lock);
 }
 
+/*
+ * Notes on process 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
+ *
+ *   WMB              WMB (aka smp_mb__before_spinlock)
+ *   LOCK rq(0)->lock LOCK X->pi_lock
+ *
+ *   dequeue X
+ *                    while (X->on_cpu)
+ *                      cpu_relax()
+ *   sched-out X
+ *   WMB
+ *   X->on_cpu = 0
+ *                    RMB
+ *                    X->state = WAKING
+ *                    set_task_cpu(X,1)
+ *                      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
+ * stores on CPU0 cannot get delayed past the MB, the llist primitives order
+ * between CPU1 and CPU2 and X's loads on CPU2 cannot get before the last LOCK.
+ *
+ * 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, purely by the llist primitives ordering
+ * CPU1 to CPU2.
+ *
+ * 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              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 the CPU, 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 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]

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

On 09/17, Peter Zijlstra wrote:
>
> Included in it are some of the details on this subject, because a wakeup
> has two prior states that are of importance, the tasks own prior state
> and the wakeup state, both should be considered in the 'program order'
> flow.

Great. Just one question,

> + *   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
> + *
> + *   WMB              WMB (aka smp_mb__before_spinlock)

Yes, both CPU's do WMB-aka-smp_mb__before_spinlock...

But afaics in this particular case we do not really need them?
So perhaps we should not even mention them?

Because (if I am right) this can confuse the reader who will try
to understand how/where do we rely on these barriers.

Oleg.

--
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]

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

On Thu, Sep 17, 2015 at 07:01:11PM +0200, Oleg Nesterov wrote:
> On 09/17, Peter Zijlstra wrote:
> >
> > Included in it are some of the details on this subject, because a wakeup
> > has two prior states that are of importance, the tasks own prior state
> > and the wakeup state, both should be considered in the 'program order'
> > flow.
> 
> Great. Just one question,
> 
> > + *   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
> > + *
> > + *   WMB              WMB (aka smp_mb__before_spinlock)
> 
> Yes, both CPU's do WMB-aka-smp_mb__before_spinlock...
> 
> But afaics in this particular case we do not really need them?
> So perhaps we should not even mention them?
> 
> Because (if I am right) this can confuse the reader who will try
> to understand how/where do we rely on these barriers.

Good point. Initially I put all barriers in, but now that we've figured
out which are important (the text is correct, right? please double
check) we can remove the rest.
--
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]

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

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.

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.

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(). Although cpu_relax()
should imply barrier(), but afaik this is not documented.

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?

Oleg.

--
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]

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

[Multipart message — attachments visible in raw view] — view raw

Hi Peter,

On Thu, Sep 17, 2015 at 03:01:26PM +0200, Peter Zijlstra wrote:
> On Thu, Sep 10, 2015 at 07:55:57PM +0200, Oleg Nesterov wrote:
> > On 09/10, Boqun Feng wrote:
> > >
> > > On Wed, Sep 09, 2015 at 12:28:22PM -0700, Paul E. McKenney wrote:
> > > > My feeling is
> > > > that we should avoid saying too much about the internals of wait_event()
> > > > and wake_up().
> > 
> > I feel the same. I simply can't understand what we are trying to
> > document ;)
> 
> So I've been sitting on this for a while and figured I'd finish it now.
> 
> It are some notes on the scheduler locking and how it provides program
> order guarantees on SMP systems.
> 
> Included in it are some of the details on this subject, because a wakeup
> has two prior states that are of importance, the tasks own prior state
> and the wakeup state, both should be considered in the 'program order'
> flow.
> 

Great and very helpful ;-)

> So maybe we can reduce the description in memory-barriers to this
> 'split' program order guarantee, where a woken task must observe both
> its own prior state and its wakee state.
                              ^^^^^
I think you mean "waker" here, right?

And the waker is not necessarily the same task who set the @cond to
true, right? If so, I feel like it's really hard to *use* this 'split'
program order guarantee in other places than sleep/wakeup itself. Could
you give an example? Thank you.

Regards,
Boqun

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web