Skip to contentSkip to conversation

wake_up_process implied memory barrier clarification

DISCUSSION Michal Hocko 5 participants 20 messages Aug 27, 2015 – Sep 8, 2015

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

Hi,
I have just stumbled over the comment above wake_up_process which claims:
"
* It may be assumed that this function implies a write memory barrier before
* changing the task state if and only if any tasks are woken up.
"

but try_to_wake_up does smp_mb__before_spinlock and did smp_wmb since 04e2f1741d235 unconditionally. The comment was added when the smp_wmb was in place already so I am wondering whether the comment is wrong/misleading.

Could somebody clarify please?

Signature · 2 lines
Michal Hocko
SUSE Labs
maintainer
#1 lore raw
Quoted 8 lines · Michal Hocko

Hi,
I have just stumbled over the comment above wake_up_process which claims:
"
* It may be assumed that this function implies a write memory barrier before
* changing the task state if and only if any tasks are woken up.
"

Quoted 6 lines

but try_to_wake_up does smp_mb__before_spinlock and did smp_wmb since 04e2f1741d235 unconditionally. The comment was added when the smp_wmb was in place already so I am wondering whether the comment is wrong/misleading.

Could somebody clarify please?

Its true for wake_up(), since that bails early if the waitqueue list is empty.

I suspect there was no exception made for wake_up_process() to simplify the rules.

#2 lore raw
Quoted 14 lines · Peter Zijlstra
Quoted 13 lines · Michal Hocko

Hi,
I have just stumbled over the comment above wake_up_process which claims:
"
* It may be assumed that this function implies a write memory barrier before
* changing the task state if and only if any tasks are woken up.
"

but try_to_wake_up does smp_mb__before_spinlock and did smp_wmb since 04e2f1741d235 unconditionally. The comment was added when the smp_wmb was in place already so I am wondering whether the comment is wrong/misleading.

Quoted 7 lines
Quoted 1 line

Could somebody clarify please?

Its true for wake_up(), since that bails early if the waitqueue list is empty.

I suspect there was no exception made for wake_up_process() to simplify the rules.

Thanks for the confirmation. Shouldn't we rather change the documentation because this is clearly misleading and confusing.
---

Quoted 1 line

From b70d9a384cfd018e686c0aca06e830f564a34dd9 Mon Sep 17 00:00:00 2001

From: Michal Hocko <[email protected]>
Date: Thu, 27 Aug 2015 15:10:55 +0200
Subject: [PATCH] sched: Clarigy wake_up_process memory barrier semantic

wake_up_process unlike other wake up primitives based on __wake_up implies the write memory barrier unconditionally because it relies on try_to_wake_up directly.

Clarify this in the function comment and memory-barriers.txt because the current doc is quite misleading.

---
 Documentation/memory-barriers.txt | 3 +++
 kernel/sched/core.c               | 3 +--
 2 files changed, 4 insertions(+), 2 deletions(-)
Documentation/memory-barriers.txt +3 -0
index 13feb697271f..c4f180caf0ff 100644
@@ -2031,6 +2031,9 @@ something up.  The barrier occurs before the task state is cleared, and so sits
 	    <general barrier>		  STORE current->state
 	LOAD event_indicated
 
+Please note that wake_up_process is an exception here because it implies
+the write memory barrier unconditionally.
+
 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:
kernel/sched/core.c +1 -2
index 78b4bad10081..39583b76ad2c 100644
@@ -1967,8 +1967,7 @@ static void try_to_wake_up_local(struct task_struct *p)
  *
  * Return: 1 if the process was woken up, 0 if it was already running.
  *
- * It may be assumed that this function implies a write memory barrier before
- * changing the task state if and only if any tasks are woken up.
+ * It may be assumed that this function implies a write memory barrier.
  */
 int wake_up_process(struct task_struct *p)
 {
Signature · 6 lines
2.5.0


-- 
Michal Hocko
SUSE Labs
#3 lore raw

Documentation/memory-barriers.txt something up. The barrier occurs before the task state is cleared, and so sits · line 2036

Quoted 10 lines · Michal Hocko
Documentation/memory-barriers.txt +3 -0
@@ -2031,6 +2031,9 @@ something up.  The barrier occurs before the task state is cleared, and so sits
 	    <general barrier>		  STORE current->state
 	LOAD event_indicated
 
+Please note that wake_up_process is an exception here because it implies
+the write memory barrier unconditionally.
+

I simply can't understand (can't even parse) this part of memory-barriers.txt.

kernel/sched/core.c static void try_to_wake_up_local(struct task_struct *p) · line 1971

Quoted 10 lines
kernel/sched/core.c +1 -2
@@ -1967,8 +1967,7 @@ static void try_to_wake_up_local(struct task_struct *p)
  *
  * Return: 1 if the process was woken up, 0 if it was already running.
  *
- * It may be assumed that this function implies a write memory barrier before
- * changing the task state if and only if any tasks are woken up.
+ * It may be assumed that this function implies a write memory barrier.
  */

I won't argue, technically this is correct of course. And I agree that the old comment is misleading.

But the new comment looks as if it is fine to avoid wmb() if you do wake_up_process(). Say,

	void w(void)
	{
		A = 1;
		wake_up_process(something_unrelated);
		// we know that it implies wmb().
		B = 1;
	}

	void r(void)
	{
		int a, b;

		b = B;
		rmb();
		a = A;

		BUG_ON(b && !a);
	}

Perhaps this part of the comment should be simply removed, the unconditional wmb() in ttwu() is just implementation detail. And note that initially the documented behaviour of smp_mb__before_spinlock() was only the STORE - LOAD serialization. Then people noticed that it actually does wmb() and started to rely on this fact.

To me, this comment should just explain that this function implies a barrier but only in a sense that you do not need another one after CONDITION = T and before wake_up_process().

Oleg.

#4 lore raw
Quoted 8 lines · Oleg Nesterov
Quoted 7 lines · Michal Hocko
Documentation/memory-barriers.txt +0 -0
@@ -2031,6 +2031,9 @@ something up.  The barrier occurs before the task state is cleared, and so sits
 	    <general barrier>		  STORE current->state
 	LOAD event_indicated
 
Quoted 5 lines

Documentation/memory-barriers.txt something up. The barrier occurs before the task state is cleared, and so sits · line 2036

Quoted 3 lines
Documentation/memory-barriers.txt +3 -0
+Please note that wake_up_process is an exception here because it implies
+the write memory barrier unconditionally.
+

I simply can't understand (can't even parse) this part of memory-barriers.txt.

Do you mean the added text or the example above it?

Quoted 5 lines
Quoted 5 lines
kernel/sched/core.c +0 -0
@@ -1967,8 +1967,7 @@ static void try_to_wake_up_local(struct task_struct *p)
  *
  * Return: 1 if the process was woken up, 0 if it was already running.
Quoted 8 lines

kernel/sched/core.c static void try_to_wake_up_local(struct task_struct *p) · line 1971

Quoted 5 lines
kernel/sched/core.c +1 -2
  *
- * It may be assumed that this function implies a write memory barrier before
- * changing the task state if and only if any tasks are woken up.
+ * It may be assumed that this function implies a write memory barrier.
  */

I won't argue, technically this is correct of course. And I agree that the old comment is misleading.

Well the reason I've noticed is the following race in the scsi code
CPU0 CPU1
scsi_error_handler scsi_host_dev_release
kthread_stop()

  while (!kthread_should_stop()) {
                                            set_bit(KTHREAD_SHOULD_STOP)
                                            wake_up_process()
                                            wait_for_completion()

    set_current_state(TASK_INTERRUPTIBLE)
    schedule()
    [...]

}

I have read the comment for wake_up_process and was wondering that moving set_current_state before kthread_should_stop wouldn't be enough because the the task at CPU0 might be TASK_RUNNIG and so wake_up_process wouldn't wake up it and the missing write barrier could lead to a missed KTHREAD_SHOULD_STOP. A look into ttwu made my worry void.

Quoted 28 lines

But the new comment looks as if it is fine to avoid wmb() if you do wake_up_process(). Say,

	void w(void)
	{
		A = 1;
		wake_up_process(something_unrelated);
		// we know that it implies wmb().
		B = 1;
	}

	void r(void)
	{
		int a, b;

		b = B;
		rmb();
		a = A;

		BUG_ON(b && !a);
	}

Perhaps this part of the comment should be simply removed, the unconditional wmb() in ttwu() is just implementation detail. And note that initially the documented behaviour of smp_mb__before_spinlock() was only the STORE - LOAD serialization. Then people noticed that it actually does wmb() and started to rely on this fact.

Quoted 3 lines

To me, this comment should just explain that this function implies a barrier but only in a sense that you do not need another one after CONDITION = T and before wake_up_process().

I have no objection against more precise wording here but what we have is just misleading.

Signature · 2 lines
Michal Hocko
SUSE Labs
#5 lore raw
Quoted 10 lines · Michal Hocko
Quoted 8 lines · Oleg Nesterov
Quoted 7 lines · Michal Hocko
Documentation/memory-barriers.txt +0 -0
@@ -2031,6 +2031,9 @@ something up.  The barrier occurs before the task state is cleared, and so sits
 	    <general barrier>		  STORE current->state
 	LOAD event_indicated
 
Quoted 7 lines
Quoted 5 lines

Documentation/memory-barriers.txt something up. The barrier occurs before the task state is cleared, and so sits · line 2036

Quoted 3 lines
Documentation/memory-barriers.txt +3 -0
+Please note that wake_up_process is an exception here because it implies
+the write memory barrier unconditionally.
+

I simply can't understand (can't even parse) this part of memory-barriers.txt.

Do you mean the added text or the example above it?

Both ;)

but note that "load from X might see 0" is true of course, and in this sense wake_up_process() is not exception:

	X = 1;
	wmb();	// unless I am totally confused this just adds more confusion
	Y = 1;
	wake_up_process(TASK);

vs TASK doing

	for (;;) {
		set_current_state(...);
		if (Y)
			break;
		schedule();
	}

	BUG_ON(X == 0)

is not correct, it can actually can hit the BUG_ON() above. However, if wake_up_process() actually wakes a sleeping TASK up, then it should also see X = 1. Even without wmb(), even if we do

	Y = 1;
	X = 1;
	wake_up_process(TASK);
Quoted 23 lines
Quoted 5 lines
Quoted 5 lines
kernel/sched/core.c +0 -0
@@ -1967,8 +1967,7 @@ static void try_to_wake_up_local(struct task_struct *p)
  *
  * Return: 1 if the process was woken up, 0 if it was already running.
Quoted 8 lines

kernel/sched/core.c static void try_to_wake_up_local(struct task_struct *p) · line 1971

Quoted 5 lines
kernel/sched/core.c +1 -2
  *
- * It may be assumed that this function implies a write memory barrier before
- * changing the task state if and only if any tasks are woken up.
+ * It may be assumed that this function implies a write memory barrier.
  */

I won't argue, technically this is correct of course. And I agree that the old comment is misleading.

Well the reason I've noticed is the following race in the scsi code
CPU0 CPU1
scsi_error_handler scsi_host_dev_release
kthread_stop()
while (!kthread_should_stop()) {
set_bit(KTHREAD_SHOULD_STOP) wake_up_process() wait_for_completion()

Quoted 2 lines

set_current_state(TASK_INTERRUPTIBLE)
schedule()

Heh. This looks like a common mistake. See fecdf8be2d91e04b0a9a4f79ff06499 ;)

But I believe this is another thing.

Quoted 5 lines

I have read the comment for wake_up_process and was wondering that moving set_current_state before kthread_should_stop wouldn't be enough because the the task at CPU0 might be TASK_RUNNIG and so wake_up_process wouldn't wake up it and the missing write barrier could lead to a missed KTHREAD_SHOULD_STOP.

And that is why try_to_wake_up()->smp_mb__before_spinlock() needs to serialize STORE(CONDITION) and the subsequent LOAD(p->state). The fact that it actually does wmb() is just implementation detail, that is what I tried to say.

Quoted 6 lines
Quoted 3 lines

To me, this comment should just explain that this function implies a barrier but only in a sense that you do not need another one after CONDITION = T and before wake_up_process().

I have no objection against more precise wording here but what we have is just misleading.

Yes, yes, I agree. Just I do not know what exactly it should document.

Oleg.

#6 lore raw

Hi Oleg

Quoted 17 lines · Oleg Nesterov
Quoted 16 lines · Michal Hocko
Quoted 13 lines · Oleg Nesterov

Documentation/memory-barriers.txt something up. The barrier occurs before the task state is cleared, and so sits · line 2036

Quoted 10 lines · Michal Hocko
Documentation/memory-barriers.txt +3 -0
@@ -2031,6 +2031,9 @@ something up.  The barrier occurs before the task state is cleared, and so sits
 	    <general barrier>		  STORE current->state
 	LOAD event_indicated
 
+Please note that wake_up_process is an exception here because it implies
+the write memory barrier unconditionally.
+

I simply can't understand (can't even parse) this part of memory-barriers.txt.

Quoted 5 lines
Quoted 1 line

Do you mean the added text or the example above it?

Both ;)

but note that "load from X might see 0" is true of course, and in this

By this, I think you actually means the example below the added text, i.e. the example for "to repeat..", right?

I think that's not a good example, and actually that example explains that the barriers in -wait_event()- rather than in -wake_up()- are conditional.

I wrote a patch to make things more clear, hope that helps.

(Add Paul and Jonathan to CCed)

Regards,
Boqun

Quoted 18 lines

sense wake_up_process() is not exception:

	X = 1;
	wmb();	// unless I am totally confused this just adds more confusion
	Y = 1;
	wake_up_process(TASK);

vs TASK doing

	for (;;) {
		set_current_state(...);
		if (Y)
			break;
		schedule();
	}

	BUG_ON(X == 0)
Quoted 8 lines

is not correct, it can actually can hit the BUG_ON() above. However, if wake_up_process() actually wakes a sleeping TASK up, then it should also see X = 1. Even without wmb(), even if we do

	Y = 1;
	X = 1;
	wake_up_process(TASK);

----------->8
Subject: Documentation: call out conditional barriers of wait_*() and wake_up*()

The memory barriers in some sleep and wakeup functions are conditional, there are several situations that there is no barriers:

1. If wait_event() and co. actually don't prepare to sleep, there
may be no barrier in them.

2. No matter whether a sleep occurs or not, there may be no barrier
between a successful wait-condition checking(the result of which is true) in wait_event() and the following instructions.

3. If wake_up() and co. actually wake up no one, there may be no
write barrier in them.

However, the current version of memory-barriers.txt doesn't call these out. Further more, the example which wanted to explain that write barriers in wake_up*() are conditional fails its job. To see that, consider a similar example:

	CPU 1				CPU 2
	===============================	===============================
	X = 1;
	smp_mb();
	Y = 1;				wait_event(wq, Y == 1);
					  load from Y sees 1, no memory barrier
	smp_wmb();
	wake_up();
					load from X might see 0

CPU 2's load from X might still be 0 even if we add a write barrier explicitly, which means that even if wake_up() guarantees a write barrier, the original example still doesn't have the desired order guarantee. In fact, the original example can explains the conditionality of barriers in wait_*() rather than wake_up*().

This patch makes things clear, by calling out that the barriers in wait_*() and wake_up*() are conditional and giving exact examples to explain that.

---

 Documentation/memory-barriers.txt | 81 +++++++++++++++++++++++++++++++--------
 1 file changed, 65 insertions(+), 16 deletions(-)
Documentation/memory-barriers.txt +65 -16
index eafa6a5..df69841 100644
@@ -1975,7 +1975,8 @@ set_current_state() may be wrapped by:
 
 which therefore also imply a general memory barrier after setting the state.
 The whole sequence above is available in various canned forms, all of which
-interpolate the memory barrier in the right place:
+imply a general barrier if and only if a sleep is at least about to happen,
+i.e. prepare_to_wait*() is called.
 
 	wait_event();
 	wait_event_interruptible();
@@ -1986,6 +1987,9 @@ interpolate the memory barrier in the right place:
 	wait_on_bit();
 	wait_on_bit_lock();
 
+Further more, no barrier is guaranteed after the successful wait condition
+checkings, whose results are true, in wait_*() and before the instructions
+following wait_*().
 
 Secondly, code that performs a wake up normally follows something like this:
 
@@ -2009,21 +2013,6 @@ between the STORE to indicate the event and the STORE to set TASK_RUNNING:
 	    <general barrier>		  STORE current->state
 	LOAD event_indicated
 
-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				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.
-
 The available waker functions include:
 
 	complete();
@@ -2042,6 +2031,66 @@ The available waker functions include:
 	wake_up_poll();
 	wake_up_process();
 
+To repeat, barriers in wait_event(), wake_up() and co. are conditional, meaning
+they are present if and only if a sleep or a wakeup actually occurs. To see
+this, consider the following three examples.
+
+The first example is for the conditional barriers in wait_*(), say X and Y
+are both initially zero:
+
+	CPU 1				CPU 2
+	===============================	===============================
+					X = 1;
+					smp_mb();
+	wait_event(wq, Y == 1);		Y = 1;
+	  load from Y sees 1		wake_up();
+	  <no memory barrier>
+	load from X might see 0
+
+And even if a sleep and a wakeup really occurs, there might be no barrier
+between the last load from Y(which the makes wait condition checking succeed)
+and load from X, so that load from X might still see 0. The second example shows
+that, the code running on CPU 1 & 2 is the same with the first example, however
+the sequence of events are different, say X, Y and Z are all initially zero,
+and another task may be waiting in wait_event(wq, Z == 1) on CPU 4:
+
+	CPU 1				CPU 2				CPU 3
+	===============================	=============================== ===============================
+	wait_event(wq, Y == 1);						Z = 1;
+	  load from Y sees 0
+	  prepare_to_wait_event();
+	    <general barrier>
+	  schedule();
+	    <general barrier>
+									wake_up();
+	  prepare_to_wait_event();
+	    <general barrier>
+					X = 1;
+					smp_mb();
+	  load from Y sees 1		Y = 1;
+	  <no memory barrier>		wake_up();
+	load from X might see 0
+
+So that, to guarantee that CPU 1's load from X is 1 in the two examples above,
+a read barrier must be added after wait_event() in the code running on CPU 1.
+
+The third example is for the conditional write barriers in wake_up*(), say
+X, Y and Z are all initially zero:
+
+	CPU 1				CPU 2
+	===============================	===============================
+					X = 1;
+	wait_event(wq, Y == 1);		Y = 1;
+	  load from Y sees 1		wake_up();
+					  <no memory barrier>
+					Z = 1;
+	load from Z sees 1
+	smp_rmb();
+	load from X might see 0
+
+In contrast, if a wakeup does occur, CPU 1's load from X would be guaranteed
+to see 1. To guarantee that CPU 1's load from X is 1, a write barrier must be
+added between store to X and store to Z in the code running on CPU 2.
 
 [!] Note that the memory barriers implied by the sleeper and the waker do _not_
 order multiple stores before the wake-up with respect to loads of those stored
#7 lore raw

Hello Boqun,

Quoted 20 lines · Boqun Feng

Hi Oleg

Quoted 17 lines · Oleg Nesterov
Quoted 16 lines · Michal Hocko
Quoted 13 lines · Oleg Nesterov

Documentation/memory-barriers.txt something up. The barrier occurs before the task state is cleared, and so sits · line 2036

Quoted 10 lines · Michal Hocko
Documentation/memory-barriers.txt +3 -0
@@ -2031,6 +2031,9 @@ something up.  The barrier occurs before the task state is cleared, and so sits
 	    <general barrier>		  STORE current->state
 	LOAD event_indicated
 
+Please note that wake_up_process is an exception here because it implies
+the write memory barrier unconditionally.
+

I simply can't understand (can't even parse) this part of memory-barriers.txt.

Quoted 8 lines
Quoted 5 lines
Quoted 1 line

Do you mean the added text or the example above it?

Both ;)

but note that "load from X might see 0" is true of course, and in this

By this, I think you actually means the example below the added text, i.e. the example for "to repeat..", right?

And above. Even

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.

Quoted 7 lines

Subject: Documentation: call out conditional barriers of wait_*() and wake_up*()

The memory barriers in some sleep and wakeup functions are conditional, there are several situations that there is no barriers:

1. If wait_event() and co. actually don't prepare to sleep, there
may be no barrier in them.

And thus (imo) we should not even try to document this. I mean, a user should not make any assumptions about the barriers inside wait_event().

Quoted 3 lines

2. No matter whether a sleep occurs or not, there may be no barrier
between a successful wait-condition checking(the result of which is true) in wait_event() and the following instructions.

Yes, this is true in any case. Not sure this deserves addtionional documentation, but see below.

Quoted 2 lines

3. If wake_up() and co. actually wake up no one, there may be no
write barrier in them.

See above.

Quoted 13 lines
Documentation/memory-barriers.txt +2 -1
@@ -1975,7 +1975,8 @@ set_current_state() may be wrapped by:
 
 which therefore also imply a general memory barrier after setting the state.
 The whole sequence above is available in various canned forms, all of which
-interpolate the memory barrier in the right place:
+imply a general barrier if and only if a sleep is at least about to happen,
+i.e. prepare_to_wait*() is called.
 
 	wait_event();
 	wait_event_interruptible();

Documentation/memory-barriers.txt interpolate the memory barrier in the right place: · line 1992

Quoted 6 lines
Documentation/memory-barriers.txt +3 -0
@@ -1986,6 +1987,9 @@ interpolate the memory barrier in the right place:
 	wait_on_bit();
 	wait_on_bit_lock();
 
+Further more, no barrier is guaranteed after the successful wait condition
+checkings, whose results are true, in wait_*() and before the instructions
+following wait_*().

Yes, perhaps this makes sense, but (to me) only because the explanation above looks a bit confusing to me. I simply can't understand why memory-barriers.txt mentions that barrier implied by set_current_state(). You need to know this if you want to understand how wait_event() works. You do not need to know about this barrier if you want to use wait_event(). If nothing else, because you can never rely on this barrier. Anf your examples below shows this.

Quoted 19 lines
Documentation/memory-barriers.txt +19 -0
+To repeat, barriers in wait_event(), wake_up() and co. are conditional, meaning
+they are present if and only if a sleep or a wakeup actually occurs. To see
+this, consider the following three examples.
+
+The first example is for the conditional barriers in wait_*(), say X and Y
+are both initially zero:
+
+	CPU 1				CPU 2
+	===============================	===============================
+					X = 1;
+					smp_mb();
+	wait_event(wq, Y == 1);		Y = 1;
+	  load from Y sees 1		wake_up();
+	  <no memory barrier>
+	load from X might see 0
+
+And even if a sleep and a wakeup really occurs, there might be no barrier
+between the last load from Y(which the makes wait condition checking succeed)
+and load from X, so that load from X might still see 0.

...

Documentation/memory-barriers.txt The available waker functions include: · line 2075

Quoted 2 lines
Documentation/memory-barriers.txt +2 -0
+So that, to guarantee that CPU 1's load from X is 1 in the two examples above,
+a read barrier must be added after wait_event() in the code running on CPU 1.

Yes. So why should we try to document that barrier in wait_event() ?

Quoted 7 lines
Documentation/memory-barriers.txt +7 -0
+The third example is for the conditional write barriers in wake_up*(), say
+X, Y and Z are all initially zero:
+
+	CPU 1				CPU 2
+	===============================	===============================
+					X = 1;
+	wait_event(wq, Y == 1);		Y = 1;

Documentation/memory-barriers.txt The available waker functions include: · line 2093

Quoted 10 lines
Documentation/memory-barriers.txt +10 -0
+	  load from Y sees 1		wake_up();
+					  <no memory barrier>
+					Z = 1;
+	load from Z sees 1
+	smp_rmb();
+	load from X might see 0
+
+In contrast, if a wakeup does occur, CPU 1's load from X would be guaranteed
+to see 1. To guarantee that CPU 1's load from X is 1, a write barrier must be
+added between store to X and store to Z in the code running on CPU 2.

The same. Why should we mention that barrier in wake_up() if we can't rely on it and CPU 2 needs a write barrier anyway?

Oleg.

#8 lore raw

Hi Oleg,

Quoted 2 lines · Oleg Nesterov

Hello Boqun,

...

Quoted 12 lines
Quoted 2 lines

By this, I think you actually means the example below the added text, i.e. the example for "to repeat..", right?

And above. Even

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.

Yes, agree with you. However, I didn't realize this problem before, I will see what I can do ;-)

Quoted 11 lines
Quoted 7 lines

Subject: Documentation: call out conditional barriers of wait_*() and wake_up*()

The memory barriers in some sleep and wakeup functions are conditional, there are several situations that there is no barriers:

1. If wait_event() and co. actually don't prepare to sleep, there
may be no barrier in them.

And thus (imo) we should not even try to document this. I mean, a user should not make any assumptions about the barriers inside wait_event().

Yep.

Quoted 28 lines
Quoted 3 lines

2. No matter whether a sleep occurs or not, there may be no barrier
between a successful wait-condition checking(the result of which is true) in wait_event() and the following instructions.

Yes, this is true in any case. Not sure this deserves addtionional documentation, but see below.

Quoted 2 lines

3. If wake_up() and co. actually wake up no one, there may be no
write barrier in them.

See above.

Quoted 16 lines
Documentation/memory-barriers.txt +2 -1
@@ -1975,7 +1975,8 @@ set_current_state() may be wrapped by:
 
 which therefore also imply a general memory barrier after setting the state.
 The whole sequence above is available in various canned forms, all of which
-interpolate the memory barrier in the right place:
+imply a general barrier if and only if a sleep is at least about to happen,
+i.e. prepare_to_wait*() is called.
 
 	wait_event();
 	wait_event_interruptible();
@@ -1986,6 +1987,9 @@ interpolate the memory barrier in the right place:
 	wait_on_bit();
 	wait_on_bit_lock();
 
Quoted 11 lines

Documentation/memory-barriers.txt interpolate the memory barrier in the right place: · line 1992

Quoted 3 lines
Documentation/memory-barriers.txt +3 -0
+Further more, no barrier is guaranteed after the successful wait condition
+checkings, whose results are true, in wait_*() and before the instructions
+following wait_*().

Yes, perhaps this makes sense, but (to me) only because the explanation above looks a bit confusing to me. I simply can't understand why memory-barriers.txt mentions that barrier implied by set_current_state(). You need to know this if you want to understand how wait_event() works. You do not need to know about this barrier if you want to use wait_event(). If nothing else, because you can never rely on this barrier. Anf your examples below shows this.

Fair enough, I went too far. How about just a single paragraph saying that:

The wake_up(), wait_event() and their friends have proper barriers in them, but these implicity barriers are only for the correctness for sleep and wakeup. So don't rely on these barriers for things that are neither wait-conditons nor task states.

Is that OK to you?

Thank you for your comments ;-)

Regards,
Boqun

#9 lore raw
Quoted 10 lines · Boqun Feng

Fair enough, I went too far. How about just a single paragraph saying that:

The wake_up(), wait_event() and their friends have proper barriers in them, but these implicity barriers are only for the correctness for sleep and wakeup. So don't rely on these barriers for things that are neither wait-conditons nor task states.

Is that OK to you?

Ask Paul ;) but personally I agree.

To me, the only thing a user should know about wake_up/try_to_wake_up and barriers is that you do not need another barrier between setting condition and waking up.

Oleg.

#10 lore raw
Quoted 10 lines · Oleg Nesterov
Quoted 9 lines · Boqun Feng

Fair enough, I went too far. How about just a single paragraph saying that:

The wake_up(), wait_event() and their friends have proper barriers in them, but these implicity barriers are only for the correctness for sleep and wakeup. So don't rely on these barriers for things that are neither wait-conditons nor task states.

Quoted 7 lines
Quoted 1 line

Is that OK to you?

Ask Paul ;) but personally I agree.

To me, the only thing a user should know about wake_up/try_to_wake_up and barriers is that you do not need another barrier between setting condition and waking up.

Sounds like an excellent idea in general. But could you please show me a short code snippet illustrating where you don't need the additional barrier, even if the fastpaths are taken so that there is no sleep and no wakeup?

Thanx, Paul

#11 lore raw

Hi Paul,

Quoted 15 lines · Paul E. McKenney
Quoted 14 lines · Oleg Nesterov
Quoted 10 lines · Boqun Feng

Fair enough, I went too far. How about just a single paragraph saying that:

The wake_up(), wait_event() and their friends have proper barriers in them, but these implicity barriers are only for the correctness for sleep and wakeup. So don't rely on these barriers for things that are neither wait-conditons nor task states.

Is that OK to you?

Ask Paul ;) but personally I agree.

Quoted 9 lines
Quoted 3 lines

To me, the only thing a user should know about wake_up/try_to_wake_up and barriers is that you do not need another barrier between setting condition and waking up.

Sounds like an excellent idea in general. But could you please show me a short code snippet illustrating where you don't need the additional barrier, even if the fastpaths are taken so that there is no sleep and no wakeup?

If there is no sleep and no wakeup, it means only CONDITION changed. Either CONDITION is a single variable or it should maintains internal ordering guarantee itself. And there is no need for barriers, because there is only one shared resource we are talking about, right?

But I'm still a little confused at Oleg's words:

"What is really important is that we have a barrier before we _read_ the task state."

I read is as "What is really important is that we have a barrier before we _read_ the task state and _after_ we write the CONDITION", if I don't misunderstand Oleg, this means a STORE-barrier-LOAD sequence, which IIUC can't pair with anything.

So, there might be some tricky barrier usage here?

Regards,
Boqun

#12 lore raw
Quoted 27 lines · Boqun Feng

Hi Paul,

Quoted 15 lines · Paul E. McKenney
Quoted 14 lines · Oleg Nesterov
Quoted 10 lines · Boqun Feng

Fair enough, I went too far. How about just a single paragraph saying that:

The wake_up(), wait_event() and their friends have proper barriers in them, but these implicity barriers are only for the correctness for sleep and wakeup. So don't rely on these barriers for things that are neither wait-conditons nor task states.

Is that OK to you?

Ask Paul ;) but personally I agree.

Quoted 8 lines
Quoted 3 lines

To me, the only thing a user should know about wake_up/try_to_wake_up and barriers is that you do not need another barrier between setting condition and waking up.

Sounds like an excellent idea in general. But could you please show me a short code snippet illustrating where you don't need the additional barrier, even if the fastpaths are taken so that there is no sleep and no wakeup?

Quoted 4 lines

If there is no sleep and no wakeup, it means only CONDITION changed. Either CONDITION is a single variable or it should maintains internal ordering guarantee itself. And there is no need for barriers, because there is only one shared resource we are talking about, right?

I could imagine all sorts of combinations, which is why I would like to see a code snippet showing exactly what Oleg is talking about. ;-)

Thanx, Paul

Quoted 14 lines

But I'm still a little confused at Oleg's words:

"What is really important is that we have a barrier before we _read_ the task state."

I read is as "What is really important is that we have a barrier before we _read_ the task state and _after_ we write the CONDITION", if I don't misunderstand Oleg, this means a STORE-barrier-LOAD sequence, which IIUC can't pair with anything.

So, there might be some tricky barrier usage here?

Regards,
Boqun

#13 lore raw
In reply to Boqun Feng
Quoted 9 lines · Boqun Feng

But I'm still a little confused at Oleg's words:

"What is really important is that we have a barrier before we _read_ the task state."

I read is as "What is really important is that we have a barrier before we _read_ the task state and _after_ we write the CONDITION", if I don't misunderstand Oleg, this means a STORE-barrier-LOAD sequence,

Yes, exactly.

Let's look at this trivial code again,

	CONDITION = 1;
	wake_up_process();

note that try_to_wake_up() does

	if (!(p->state & state))
		goto out;

If this LOAD could be reordered with STORE(CONDITION) above we can obviously race with

	set_current_state(...);
	if (!CONDITION)
		schedule();

See the comment at the start of try_to_wake_up(). And again, again, please note that initially the only documented behaviour of smp_mb__before_spinlock() was the STORE - LOAD serialization. This is what try_to_wake_up() needs, it doesn't actually need the write barrier after STORE(CONDITION).

And just in case, wake_up() differs in a sense that it doesn't even need that STORE-LOAD barrier in try_to_wake_up(), we can rely on wait_queue_head_t->lock. Assuming that wake_up() pairs with the "normal" wait_event()-like code.

Quoted 2 lines

which IIUC
can't pair with anything.

It pairs with the barrier implied by set_current_state().

Oleg.

#14 lore raw
Quoted 23 lines · Oleg Nesterov
Quoted 9 lines · Boqun Feng

But I'm still a little confused at Oleg's words:

"What is really important is that we have a barrier before we _read_ the task state."

I read is as "What is really important is that we have a barrier before we _read_ the task state and _after_ we write the CONDITION", if I don't misunderstand Oleg, this means a STORE-barrier-LOAD sequence,

Yes, exactly.

Let's look at this trivial code again,

	CONDITION = 1;
	wake_up_process();

note that try_to_wake_up() does

	if (!(p->state & state))
		goto out;
Quoted 8 lines

If this LOAD could be reordered with STORE(CONDITION) above we can obviously race with

	set_current_state(...);
	if (!CONDITION)
		schedule();

See the comment at the start of try_to_wake_up(). And again, again, please

Thank you for your detailed explanation!

I read the comment, but just couldn't understand how the pairing happens, I think I have a misunderstanding of pairing, please see below.

Quoted 9 lines

note that initially the only documented behaviour of smp_mb__before_spinlock() was the STORE - LOAD serialization. This is what try_to_wake_up() needs, it doesn't actually need the write barrier after STORE(CONDITION).

And just in case, wake_up() differs in a sense that it doesn't even need that STORE-LOAD barrier in try_to_wake_up(), we can rely on wait_queue_head_t->lock. Assuming that wake_up() pairs with the "normal" wait_event()-like code.

Quoted 4 lines
Quoted 2 lines

which IIUC
can't pair with anything.

It pairs with the barrier implied by set_current_state().

I think maybe I have a misunderstanding of barrier pairing. I used to think that a barrier pairing can only happen:

1. between a "MEM-barrier-STORE" and "LOAD-barrier-MEM", when the
LOAD reads the value which the STORE writes

where MEM is a memory operation(STORE or LOAD).

However, wait and wakeup don't fit in the #1 barrier pairing, so I guess I was wrong, there is a kind of barrier pairings which also happen:

2. between a "MEM-barrier-LOAD" and "STORE-barrier-MEM", when the
LOAD _fails_ to read the value which the STORE writes,

#1 pairing is easy to understand and memory-barriers.txt already has some examples. I admit that I haven't seen any usage of #2 pairing other than wait_event() and wake_up(). Of course, this may be because I'm not an expert of parallel programming and don't know too much..

Have to ask Paul, when we are talking about barrier pairing, we are actually talking about the combination of #1 and #2, right?

And Oleg, the barrier pairing we are talking here is the kind of #2, right?

Add two examples, in case that I fail to make clear the difference of two barrier pairings.

One example of #1 pairing is the following sequence of events:

Initially X = 0, Y = 0

CPU 1 CPU 2
=========================== ================================
WRITE_ONCE(Y, 1);
smp_mb();

WRITE_ONCE(X, 1);
				r1 = READ_ONCE(X); // r1 == 1
				smp_mb();
				r2 = READ_ONCE(Y);

----------------------------------------------------------------
{ assert(!(r1 == 1 && r2 == 0)); // means if r1 == 1 then r2 == 1}

If CPU 2 reads the value of X written by CPU 1, r2 is guaranteed to be 1, which means assert(!(r1 == 1 && r2 == 0)) afterwards wouldn't be triggered in any case.

One example of #2 pairing is the following sequence of events:

Initially X = 0, Y = 0

CPU 1 CPU 2
=========================== ================================
WRITE_ONCE(Y, 1);
smp_mb();
r1 = READ_ONCE(X); // r1 == 0

				WRITE_ONCE(X, 1);
				smp_mb();
				r2 = READ_ONCE(Y);

----------------------------------------------------------------
{ assert(!(r1 == 0 && r2 == 0)); // means if r1 == 0 then r2 == 1}

If CPU 1 _fails_ to read the value of X written by CPU 1, r2 is guaranteed to 1, which means assert(!(r1 == 0 && r2 == 0)) afterwards wouldn't be triggered in any case.

And this is actually the case of wake_up/wait, assuming that prepare_to_wait() is called on CPU 1 and wake_up() is called on CPU 2, X is the condition and Y is the task state, and replace smp_mb() with really necessary barriers, right?

Regards,
Boqun

#15 lore raw
Quoted 7 lines · Boqun Feng
Quoted 5 lines · Oleg Nesterov

And just in case, wake_up() differs in a sense that it doesn't even need that STORE-LOAD barrier in try_to_wake_up(), we can rely on wait_queue_head_t->lock. Assuming that wake_up() pairs with the "normal" wait_event()-like code.

Looks like, you have missed this part of my previous email. See below.

Quoted 1 line

I think maybe I have a misunderstanding of barrier pairing.

Or me. I can only say how it is supposed to work.

Quoted 1 line

think that a barrier pairing can only happen:

Well, no. See for example https://lkml.org/lkml/2014/7/16/310
Or, say, the comment in completion_done().

And please do not assume I can answer authoritatively the questions in this area. Fortunately we have paulmck/peterz in CC, they can correct me.

Plus I didn't sleep today, not sure I can understand you correctly and/or answer your question ;)

Quoted 16 lines

One example of #2 pairing is the following sequence of events:

Initially X = 0, Y = 0

CPU 1 CPU 2
=========================== ================================
WRITE_ONCE(Y, 1);
smp_mb();
r1 = READ_ONCE(X); // r1 == 0

				WRITE_ONCE(X, 1);
				smp_mb();
				r2 = READ_ONCE(Y);

----------------------------------------------------------------
{ assert(!(r1 == 0 && r2 == 0)); // means if r1 == 0 then r2 == 1}

Quoted 6 lines

If CPU 1 _fails_ to read the value of X written by CPU 1, r2 is guaranteed to 1, which means assert(!(r1 == 0 && r2 == 0)) afterwards wouldn't be triggered in any case.

And this is actually the case of wake_up/wait, assuming that prepare_to_wait() is called on CPU 1 and wake_up() is called on CPU 2,

See above, wake_up/wait_event are fine in any case because they use the same lock.

But as for try_to_wake_up() you are right, we rely on STORE-MB-LOAD. Now let me quote another previous email,

	So in fact try_to_wake_up() needs mb() before it does

		if (!(p->state & state))
			goto out;

	But mb() is heavy, we can use wmb() instead, but only in this particular
	case: before spin_lock(), which guarantees that LOAD(p->state) can't leak
	out of the critical section. And since spin_lock() itself is the STORE,
	this guarantees that STORE(CONDITION) can't leak _into_ the critical section
	and thus it can't be reordered with LOAD(p->state).

And I think that smp_mb__before_spinlock() + spin_lock() should pair correctly with mb(). If not - we should redefine it.

Quoted 1 line

X is the condition and Y is the task state,

Yes,

Quoted 1 line

and replace smp_mb() with really necessary barriers, right?

Sorry, can't understand this part...

Oleg.

#16 lore raw
Quoted 10 lines · Oleg Nesterov
Quoted 7 lines · Boqun Feng
Quoted 5 lines · Oleg Nesterov

And just in case, wake_up() differs in a sense that it doesn't even need that STORE-LOAD barrier in try_to_wake_up(), we can rely on wait_queue_head_t->lock. Assuming that wake_up() pairs with the "normal" wait_event()-like code.

Looks like, you have missed this part of my previous email. See below.

I guess I need to think through this, though I haven't found any problem in wake_up() if we remove the STORE-LOAD barrier in try_to_wake_up(). And I know that in wake_up(), try_to_wake_up() will be called with holding wait_queue_head_t->lock, however, only part of wait_event() holds the same lock, I can't figure out why the barrier is not needed because of the lock.. I will read the code carefully to see whether I miss something.

Quoted 8 lines
Quoted 2 lines

I think maybe I have a misunderstanding of barrier pairing.

Or me. I can only say how it is supposed to work.

Quoted 1 line

think that a barrier pairing can only happen:

Well, no. See for example https://lkml.org/lkml/2014/7/16/310

This helps a lot, so does the LWN article it references:

https://lwn.net/Articles/573436/

The barrier pairing here is scenario 10 in that article. I'm sure that is my misunderstanding of barrier pairing now, thank you!

Quoted 6 lines

Or, say, the comment in completion_done().

And please do not assume I can answer authoritatively the questions in this area. Fortunately we have paulmck/peterz in CC, they can correct me.

Your explanation and references help a lot, now I understand how the barrier works in try_to_wake_up() ;-)

Quoted 23 lines

Plus I didn't sleep today, not sure I can understand you correctly and/or answer your question ;)

Quoted 20 lines

One example of #2 pairing is the following sequence of events:

Initially X = 0, Y = 0

CPU 1 CPU 2
=========================== ================================
WRITE_ONCE(Y, 1);
smp_mb();
r1 = READ_ONCE(X); // r1 == 0

				WRITE_ONCE(X, 1);
				smp_mb();
				r2 = READ_ONCE(Y);

----------------------------------------------------------------
{ assert(!(r1 == 0 && r2 == 0)); // means if r1 == 0 then r2 == 1}

If CPU 1 _fails_ to read the value of X written by CPU 1, r2 is guaranteed to 1, which means assert(!(r1 == 0 && r2 == 0)) afterwards wouldn't be triggered in any case.

Quoted 6 lines
Quoted 2 lines

And this is actually the case of wake_up/wait, assuming that prepare_to_wait() is called on CPU 1 and wake_up() is called on CPU 2,

See above, wake_up/wait_event are fine in any case because they use the same lock.

I think I wanted to say wake_up_proccess() here, which calls try_to_wake_up() directly, sorry about that mistake..

Quoted 14 lines

But as for try_to_wake_up() you are right, we rely on STORE-MB-LOAD. Now let me quote another previous email,

	So in fact try_to_wake_up() needs mb() before it does

		if (!(p->state & state))
			goto out;

	But mb() is heavy, we can use wmb() instead, but only in this particular
	case: before spin_lock(), which guarantees that LOAD(p->state) can't leak
	out of the critical section. And since spin_lock() itself is the STORE,
	this guarantees that STORE(CONDITION) can't leak _into_ the critical section
	and thus it can't be reordered with LOAD(p->state).

This also helps a lot, thank you ;-)

Quoted 11 lines

And I think that smp_mb__before_spinlock() + spin_lock() should pair correctly with mb(). If not - we should redefine it.

Quoted 1 line

X is the condition and Y is the task state,

Yes,

Quoted 1 line

and replace smp_mb() with really necessary barriers, right?

Sorry, can't understand this part...

I just want to be accurate by saying that, because the barrier in try_to_wake_up() is not a smp_mb(), is a smp_mb__before_spinlock() + spin_lock().

Regards,
Boqun

#17 lore raw

Sorry for delay,

Quoted 11 lines · Boqun Feng
Quoted 9 lines · Oleg Nesterov
Quoted 7 lines · Boqun Feng
Quoted 5 lines · Oleg Nesterov

And just in case, wake_up() differs in a sense that it doesn't even need that STORE-LOAD barrier in try_to_wake_up(), we can rely on wait_queue_head_t->lock. Assuming that wake_up() pairs with the "normal" wait_event()-like code.

Quoted 8 lines
Quoted 1 line

Looks like, you have missed this part of my previous email. See below.

I guess I need to think through this, though I haven't found any problem in wake_up() if we remove the STORE-LOAD barrier in try_to_wake_up(). And I know that in wake_up(), try_to_wake_up() will be called with holding wait_queue_head_t->lock, however, only part of wait_event() holds the same lock, I can't figure out why the barrier is not needed because of the lock..

This is very simple. __wait_event() does

	for (;;) {
		prepare_to_wait_event(WQ, ...);	// takes WQ->lock

		if (CONDITION)
			break;

		schedule();
	}

and we have

	CONDITION = 1;
	wake_up(WQ);				// takes WQ->lock

on another side.

Suppose that __wait_event() wins and takes WQ->lock first. It can block then. In this case wake_up() must see the result of set_current_state() and list_add() when it takes the same lock, otherwise spin_lock() would be simply buggy. So it will wake the waiter up.

At the same time, if __wait_event() takes this lock after wake_up(), it can not miss CONDITION = 1. It must see it after it takes the lock, and of course after it drops the lock too.

So I am not sure I understand your concerns in this case...

Oleg.

#18 lore raw

Hi Oleg,

Quoted 41 lines · Oleg Nesterov

Sorry for delay,

Quoted 11 lines · Boqun Feng
Quoted 9 lines · Oleg Nesterov
Quoted 7 lines · Boqun Feng
Quoted 5 lines · Oleg Nesterov

And just in case, wake_up() differs in a sense that it doesn't even need that STORE-LOAD barrier in try_to_wake_up(), we can rely on wait_queue_head_t->lock. Assuming that wake_up() pairs with the "normal" wait_event()-like code.

Quoted 8 lines
Quoted 1 line

Looks like, you have missed this part of my previous email. See below.

I guess I need to think through this, though I haven't found any problem in wake_up() if we remove the STORE-LOAD barrier in try_to_wake_up(). And I know that in wake_up(), try_to_wake_up() will be called with holding wait_queue_head_t->lock, however, only part of wait_event() holds the same lock, I can't figure out why the barrier is not needed because of the lock..

This is very simple. __wait_event() does

	for (;;) {
		prepare_to_wait_event(WQ, ...);	// takes WQ->lock

		if (CONDITION)
			break;

		schedule();
	}

and we have

	CONDITION = 1;
	wake_up(WQ);				// takes WQ->lock

on another side.

Quoted 9 lines

Suppose that __wait_event() wins and takes WQ->lock first. It can block then. In this case wake_up() must see the result of set_current_state() and list_add() when it takes the same lock, otherwise spin_lock() would be simply buggy. So it will wake the waiter up.

At the same time, if __wait_event() takes this lock after wake_up(), it can not miss CONDITION = 1. It must see it after it takes the lock, and of course after it drops the lock too.

Yes, you're right! I wasn't aware that in prepare_to_wait_event(), set_current_state() is called with the WQ->lock.

Quoted 2 lines

So I am not sure I understand your concerns in this case...

It's my mistake. Thank you for your explanation ;-)

Regards,
Boqun

#19 lore raw
In reply to Paul E. McKenney
Quoted 16 lines · Paul E. McKenney
Quoted 14 lines · Oleg Nesterov
Quoted 10 lines · Boqun Feng

Fair enough, I went too far. How about just a single paragraph saying that:

The wake_up(), wait_event() and their friends have proper barriers in them, but these implicity barriers are only for the correctness for sleep and wakeup. So don't rely on these barriers for things that are neither wait-conditons nor task states.

Is that OK to you?

Ask Paul ;) but personally I agree.

Quoted 8 lines
Quoted 3 lines

To me, the only thing a user should know about wake_up/try_to_wake_up and barriers is that you do not need another barrier between setting condition and waking up.

Sounds like an excellent idea in general. But could you please show me a short code snippet illustrating where you don't need the additional barrier, even if the fastpaths are taken so that there is no sleep and no wakeup?

I guess I wasn't clear... All I tried to say is that

	CONDITION = 1;
	wake_up_process();

does not need any _additional_ barrier in between.

I mentioned this because afaics people are often unsure if this is true or not, and to some degree this question initiated this discussion.

Oleg.