Skip to contentSkip to conversation

Fix a race between rwsem and the scheduler

RFC PATCH In review Balbir Singh 7 participants 27 messages Aug 30, 2016 – Sep 1, 2016 Scheduler

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 Fix a race between rwsem and the scheduler

The origin of the issue I've seen seems to be related to rwsem spin lock stealing. Basically I see the system deadlock'd in the following state

I have a system with multiple threads and

Most of the threads are stuck doing

[67272.593915] --- interrupt: e81 at _raw_spin_lock_irqsave+0xa4/0x130
[67272.593915]     LR = _raw_spin_lock_irqsave+0x9c/0x130
[67272.700996] [c000000012857ae0] [c00000000012453c] rwsem_wake+0xcc/0x110
[67272.749283] [c000000012857b20] [c0000000001215d8] up_write+0x78/0x90
[67272.788965] [c000000012857b50] [c00000000028153c] unlink_anon_vmas+0x15c/0x2c0
[67272.798782] [c000000012857bc0] [c00000000026f5c0] free_pgtables+0xf0/0x1c0
[67272.842528] [c000000012857c10] [c00000000027c9a0] exit_mmap+0x100/0x1a0
[67272.872947] [c000000012857cd0] [c0000000000b4a98] mmput+0xa8/0x1b0
[67272.898432] [c000000012857d00] [c0000000000bc50c] do_exit+0x33c/0xc30
[67272.944721] [c000000012857dc0] [c0000000000bcee4] do_group_exit+0x64/0x100
[67272.969014] [c000000012857e00] [c0000000000bcfac] SyS_exit_group+0x2c/0x30
[67272.978971] [c000000012857e30] [c000000000009204] system_call+0x38/0xb4
[67272.999016] Instruction dump:

They are spinning on the sem->wait_lock, the holder of sem->wait_lock has irq's disabled and is doing

[c00000037930fb30] c0000000000f724c try_to_wake_up+0x6c/0x570 [c00000037930fbb0] c000000000124328 __rwsem_do_wake+0x1f8/0x260 [c00000037930fc00] c0000000001244b4 rwsem_wake+0x84/0x110 [c00000037930fc40] c000000000121598 up_write+0x78/0x90 [c00000037930fc70] c000000000281a54 anon_vma_fork+0x184/0x1d0 [c00000037930fcc0] c0000000000b68e0 copy_process.isra.5+0x14c0/0x1870 [c00000037930fda0] c0000000000b6e68 _do_fork+0xa8/0x4b0 [c00000037930fe30] c000000000009460 ppc_clone+0x8/0xc

The offset of try_to_wake_up is actually misleading, it is actually stuck doing the following in try_to_wake_up

while (p->on_cpu)

	cpu_relax();

Analysis

The issue is triggered, due to the following race

CPU1 CPU2

while () {
if (cond)

    break;
  do {
    schedule();
    set_current_state(TASK_UN..)

} while (!cond);
rwsem_wake()
spin_lock_irqsave(wait_lock)
raw_spin_lock_irqsave(wait_lock) wake_up_process()
} try_to_wake_up()
set_current_state(TASK_RUNNING); ..
list_del(&waiter.list);

CPU2 wakes up CPU1, but before it can get the wait_lock and set current state to TASK_RUNNING the following occurs

CPU3
(stole the rwsem before waiter can be woken up from queue) up_write()
rwsem_wake()
raw_spin_lock_irqsave(wait_lock)
if (!list_empty)
wake_up_process()
try_to_wake_up() raw_spin_lock_irqsave(p->pi_lock)
..
if (p->on_rq && ttwu_wakeup())
..
while (p->on_cpu)

    cpu_relax()

..

CPU3 tries to wake up the task on CPU1 again since it finds it on the wait_queue, CPU1 is spinning on wait_lock, but immediately after CPU2, CPU3 got it.

CPU3 checks the state of p on CPU1, it is TASK_UNINTERRUPTIBLE and the task is spinning on the wait_lock. Interestingly since p->on_rq is checked under pi_lock, I've noticed that try_to_wake_up() finds p->on_rq to be 0. This was the most confusing bit of the analysis, but p->on_rq is changed under runqueue lock, rq_lock, the p->on_rq check is not reliable without this fix IMHO. The race is visible (based on the analysis) only when ttwu_queue() does a remote wakeup via ttwu_queue_remote. In which case the p->on_rq change is not done uder the pi_lock.

The result is that after a while the entire system locks up on the raw_spin_irqlock_save(wait_lock) and the holder spins infintely

Reproduction of the issue

The issue can be reproduced after a long run on my system with 80 threads and having to tweak available memory to very low and running memory stress-ng mmapfork test. It usually takes a long time to reproduce. I am trying to work on a test case that can reproduce the issue faster, but thats work in progress. I am still testing the changes on my still in a loop and the tests seem OK thus far.

Big thanks to Benjamin and Nick for helping debug this as well. Ben helped catch the missing barrier, Nick caught every missing bit in my theory

Cc Peter Zijlstra <[email protected]>
Cc Nicholas Piggin <[email protected]>
Cc Benjamin Herrenschmidt <[email protected]>
---
 kernel/sched/core.c | 11 +++++++++++
 1 file changed, 11 insertions(+)
kernel/sched/core.c +11 -0
index 2a906f2..582c684 100644
@@ -2016,6 +2016,17 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
 	success = 1; /* we're going to change ->state */
 	cpu = task_cpu(p);
 
+	/*
+	 * Ensure we see on_rq and p_state consistently
+	 *
+	 * For example in __rwsem_down_write_failed(), we have
+	 *    [S] ->on_rq = 1				[L] ->state
+	 *    MB					 RMB
+	 *    [S] ->state = TASK_UNINTERRUPTIBLE	[L] ->on_rq
+	 * In the absence of the RMB p->on_rq can be observed to be 0
+	 * and we end up spinning indefinitely in while (p->on_cpu)
+	 */
+	smp_rmb();
 	if (p->on_rq && ttwu_remote(p, wake_flags))
 		goto stat;
 
Signature · 1 line
2.5.5
#1 lore raw
Quoted 3 lines · On Tue, 30 Aug 2016 18:49:37 +1000 Balbir Singh <[email protected]> wrote:

The origin of the issue I've seen seems to be related to rwsem spin lock stealing. Basically I see the system deadlock'd in the following state

BTW. this is not really to do with rwsems, but purely a scheduler bug. It was seen in other callers too that follow similar pattern, but even when those don't follow this pattern that leads to deadlock, it could lead to a long busywait in the waker until the wakee next sleeps or gets preempted.

Quoted 137 lines

I have a system with multiple threads and

Most of the threads are stuck doing

[67272.593915] --- interrupt: e81 at _raw_spin_lock_irqsave+0xa4/0x130
[67272.593915]     LR = _raw_spin_lock_irqsave+0x9c/0x130
[67272.700996] [c000000012857ae0] [c00000000012453c] rwsem_wake+0xcc/0x110
[67272.749283] [c000000012857b20] [c0000000001215d8] up_write+0x78/0x90
[67272.788965] [c000000012857b50] [c00000000028153c] unlink_anon_vmas+0x15c/0x2c0
[67272.798782] [c000000012857bc0] [c00000000026f5c0] free_pgtables+0xf0/0x1c0
[67272.842528] [c000000012857c10] [c00000000027c9a0] exit_mmap+0x100/0x1a0
[67272.872947] [c000000012857cd0] [c0000000000b4a98] mmput+0xa8/0x1b0
[67272.898432] [c000000012857d00] [c0000000000bc50c] do_exit+0x33c/0xc30
[67272.944721] [c000000012857dc0] [c0000000000bcee4] do_group_exit+0x64/0x100
[67272.969014] [c000000012857e00] [c0000000000bcfac] SyS_exit_group+0x2c/0x30
[67272.978971] [c000000012857e30] [c000000000009204] system_call+0x38/0xb4
[67272.999016] Instruction dump:

They are spinning on the sem->wait_lock, the holder of sem->wait_lock has irq's disabled and is doing

[c00000037930fb30] c0000000000f724c try_to_wake_up+0x6c/0x570 [c00000037930fbb0] c000000000124328 __rwsem_do_wake+0x1f8/0x260 [c00000037930fc00] c0000000001244b4 rwsem_wake+0x84/0x110 [c00000037930fc40] c000000000121598 up_write+0x78/0x90 [c00000037930fc70] c000000000281a54 anon_vma_fork+0x184/0x1d0 [c00000037930fcc0] c0000000000b68e0 copy_process.isra.5+0x14c0/0x1870 [c00000037930fda0] c0000000000b6e68 _do_fork+0xa8/0x4b0 [c00000037930fe30] c000000000009460 ppc_clone+0x8/0xc

The offset of try_to_wake_up is actually misleading, it is actually stuck doing the following in try_to_wake_up

while (p->on_cpu)

	cpu_relax();

Analysis

The issue is triggered, due to the following race

CPU1 CPU2

while () {
if (cond)

    break;
  do {
    schedule();
    set_current_state(TASK_UN..)

} while (!cond);
rwsem_wake()
spin_lock_irqsave(wait_lock)
raw_spin_lock_irqsave(wait_lock) wake_up_process()
} try_to_wake_up()
set_current_state(TASK_RUNNING); ..
list_del(&waiter.list);

CPU2 wakes up CPU1, but before it can get the wait_lock and set current state to TASK_RUNNING the following occurs

CPU3
(stole the rwsem before waiter can be woken up from queue) up_write()
rwsem_wake()
raw_spin_lock_irqsave(wait_lock)
if (!list_empty)
wake_up_process()
try_to_wake_up() raw_spin_lock_irqsave(p->pi_lock)
..
if (p->on_rq && ttwu_wakeup())
..
while (p->on_cpu)

    cpu_relax()

..

CPU3 tries to wake up the task on CPU1 again since it finds it on the wait_queue, CPU1 is spinning on wait_lock, but immediately after CPU2, CPU3 got it.

CPU3 checks the state of p on CPU1, it is TASK_UNINTERRUPTIBLE and the task is spinning on the wait_lock. Interestingly since p->on_rq is checked under pi_lock, I've noticed that try_to_wake_up() finds p->on_rq to be 0. This was the most confusing bit of the analysis, but p->on_rq is changed under runqueue lock, rq_lock, the p->on_rq check is not reliable without this fix IMHO. The race is visible (based on the analysis) only when ttwu_queue() does a remote wakeup via ttwu_queue_remote. In which case the p->on_rq change is not done uder the pi_lock.

The result is that after a while the entire system locks up on the raw_spin_irqlock_save(wait_lock) and the holder spins infintely

Reproduction of the issue

The issue can be reproduced after a long run on my system with 80 threads and having to tweak available memory to very low and running memory stress-ng mmapfork test. It usually takes a long time to reproduce. I am trying to work on a test case that can reproduce the issue faster, but thats work in progress. I am still testing the changes on my still in a loop and the tests seem OK thus far.

Big thanks to Benjamin and Nick for helping debug this as well. Ben helped catch the missing barrier, Nick caught every missing bit in my theory

Cc Peter Zijlstra <[email protected]>
Cc Nicholas Piggin <[email protected]>
Cc Benjamin Herrenschmidt <[email protected]>
---
 kernel/sched/core.c | 11 +++++++++++
 1 file changed, 11 insertions(+)
kernel/sched/core.c +11 -0
index 2a906f2..582c684 100644
@@ -2016,6 +2016,17 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
 	success = 1; /* we're going to change ->state */
 	cpu = task_cpu(p);
 
+	/*
+	 * Ensure we see on_rq and p_state consistently
+	 *
+	 * For example in __rwsem_down_write_failed(), we have
+	 *    [S] ->on_rq = 1				[L] ->state
+	 *    MB					 RMB
+	 *    [S] ->state = TASK_UNINTERRUPTIBLE	[L] ->on_rq
+	 * In the absence of the RMB p->on_rq can be observed to be 0
+	 * and we end up spinning indefinitely in while (p->on_cpu)
+	 */
+	smp_rmb();
 	if (p->on_rq && ttwu_remote(p, wake_flags))
 		goto stat;
 
maintainer
#2 lore raw
In reply to Balbir Singh
Quoted 5 lines · Balbir Singh

The origin of the issue I've seen seems to be related to rwsem spin lock stealing. Basically I see the system deadlock'd in the following state

As Nick says (good to see you're back Nick!), this is unrelated to rwsems.

This is true for pretty much every blocking wait loop out there, they all do:

	for (;;) {
		current->state = UNINTERRUPTIBLE;
		smp_mb();
		if (cond)
			break;
		schedule();
	}
	current->state = RUNNING;

Which, if the wakeup is spurious, is just the pattern you need.

kernel/sched/core.c try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) · line 2024

Quoted 11 lines

+++ b/kernel/sched/core.c

kernel/sched/core.c +6 -0
@@ -2016,6 +2016,17 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
 	success = 1; /* we're going to change ->state */
 	cpu = task_cpu(p);
 
+	/*
+	 * Ensure we see on_rq and p_state consistently
+	 *
+	 * For example in __rwsem_down_write_failed(), we have
+	 *    [S] ->on_rq = 1				[L] ->state
+	 *    MB					 RMB

There isn't an MB there. The best I can do is UNLOCK+LOCK, which, thanks to PPC, is _not_ MB. It is however sufficient for this case.

kernel/sched/core.c try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) · line 2028

Quoted 4 lines
kernel/sched/core.c +4 -0
+	 *    [S] ->state = TASK_UNINTERRUPTIBLE	[L] ->on_rq
+	 * In the absence of the RMB p->on_rq can be observed to be 0
+	 * and we end up spinning indefinitely in while (p->on_cpu)
+	 */

/*
* Ensure we load p->on_rq _after_ p->state, otherwise it would
* be possible to, falsely, observe p->on_rq == 0 and get stuck
* in smp_cond_load_acquire() below.
*
* sched_ttwu_pending() try_to_wake_up()
* [S] p->on_rq = 1; [L] P->state
* UNLOCK rq->lock
*
* schedule() RMB
* LOCK rq->lock
* UNLOCK rq->lock
*
* [task p]
* [S] p->state = UNINTERRUPTIBLE [L] p->on_rq
*
* Pairs with the UNLOCK+LOCK on rq->lock from the
* last wakeup of our task and the schedule that got our task
* current.
*/

kernel/sched/core.c try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) · line 2032

Quoted 4 lines
kernel/sched/core.c +1 -0
+	smp_rmb();
 	if (p->on_rq && ttwu_remote(p, wake_flags))
 		goto stat;
 

Now, this has been present for a fair while, I suspect ever since we reworked the wakeup path to not use rq->lock twice. Curious you only now hit it.

#3 lore raw
Quoted 13 lines · Peter Zijlstra

/*
* Ensure we load p->on_rq _after_ p->state, otherwise it would
* be possible to, falsely, observe p->on_rq == 0 and get stuck
* in smp_cond_load_acquire() below.
*
* sched_ttwu_pending() try_to_wake_up()
* [S] p->on_rq = 1; [L] P->state
* UNLOCK rq->lock
*
* schedule() RMB
* LOCK rq->lock
* UNLOCK rq->lock

Quoted 8 lines

*
* [task p]
* [S] p->state = UNINTERRUPTIBLE [L] p->on_rq
*
* Pairs with the UNLOCK+LOCK on rq->lock from the
* last wakeup of our task and the schedule that got our task
* current.
*/

Confused... how this connects to UNLOCK+LOCK on rq->lock? A LOAD can leak into the critical section.

But context switch should imply mb() we can rely on?

Oleg.

maintainer
#4 lore raw
Quoted 23 lines · Oleg Nesterov
Quoted 13 lines · Peter Zijlstra

/*
* Ensure we load p->on_rq _after_ p->state, otherwise it would
* be possible to, falsely, observe p->on_rq == 0 and get stuck
* in smp_cond_load_acquire() below.
*
* sched_ttwu_pending() try_to_wake_up()
* [S] p->on_rq = 1; [L] P->state
* UNLOCK rq->lock
*
* schedule() RMB
* LOCK rq->lock
* UNLOCK rq->lock

Quoted 8 lines

*
* [task p]
* [S] p->state = UNINTERRUPTIBLE [L] p->on_rq
*
* Pairs with the UNLOCK+LOCK on rq->lock from the
* last wakeup of our task and the schedule that got our task
* current.
*/

Quoted 2 lines

Confused... how this connects to UNLOCK+LOCK on rq->lock? A LOAD can leak into the critical section.

How so? That LOCK+UNLOCK which is leaky, UNLOCK+LOCK is a read/write barrier (just not an MB because it lacks full transitivity).

Quoted 1 line

But context switch should imply mb() we can rely on?

Not sure it should, on x86 switch_mm does a CR3 write and that is serializing, but switch_to() doesn't need to do anything iirc.

#5 lore raw
Quoted 24 lines · Peter Zijlstra
Quoted 23 lines · Oleg Nesterov
Quoted 21 lines · Peter Zijlstra

/*
* Ensure we load p->on_rq _after_ p->state, otherwise it would
* be possible to, falsely, observe p->on_rq == 0 and get stuck
* in smp_cond_load_acquire() below.
*
* sched_ttwu_pending() try_to_wake_up()
* [S] p->on_rq = 1; [L] P->state
* UNLOCK rq->lock
*
* schedule() RMB
* LOCK rq->lock
* UNLOCK rq->lock
*
* [task p]
* [S] p->state = UNINTERRUPTIBLE [L] p->on_rq
*
* Pairs with the UNLOCK+LOCK on rq->lock from the
* last wakeup of our task and the schedule that got our task
* current.
*/

Quoted 5 lines
Quoted 2 lines

Confused... how this connects to UNLOCK+LOCK on rq->lock? A LOAD can leak into the critical section.

How so? That LOCK+UNLOCK which is leaky, UNLOCK+LOCK is a read/write barrier (just not an MB because it lacks full transitivity).

Ah, I have wrongly read the "Pairs with the UNLOCK+LOCK" as "Pairs with the LOCK+UNLOCK". And didn't notice this even after I copy-and-pasted this part.

Quoted 4 lines
Quoted 1 line

But context switch should imply mb() we can rely on?

Not sure it should, on x86 switch_mm does a CR3 write and that is serializing, but switch_to() doesn't need to do anything iirc.

Documentation/memory-barriers.txt says

schedule() and similar imply full memory barriers.

and I (wrongly?) interpreted this as if this is also true for 2 different threadds.

I mean, I thought that the LOAD/STORE's done by some task can't be re-ordered with LOAD/STORE's done by another task which was running on the same CPU. Wrong?

Oleg.

maintainer
#6 lore raw
Quoted 8 lines · Oleg Nesterov
Quoted 6 lines · Peter Zijlstra
Quoted 1 line · Oleg Nesterov

But context switch should imply mb() we can rely on?

Not sure it should, on x86 switch_mm does a CR3 write and that is serializing, but switch_to() doesn't need to do anything iirc.

Quoted 6 lines

Documentation/memory-barriers.txt says

schedule() and similar imply full memory barriers.

and I (wrongly?) interpreted this as if this is also true for 2 different threadds.

I'm not actually sure it does. There is the comment from 8643cda549ca4 which explain the program order guarantees.

But I'm not sure who or what would simply a full smp_mb() when you call schedule() -- I mean, its true on x86, but that's 'trivial'.

Quoted 3 lines

I mean, I thought that the LOAD/STORE's done by some task can't be re-ordered with LOAD/STORE's done by another task which was running on the same CPU. Wrong?

If so, I'm not sure how :/

So smp_mb__before_spinlock() stops stores from @prev, and the ACQUIRE from spin_lock(&rq->lock) stops both loads/stores from @next, but afaict nothing stops the loads from @prev seeing stores from @next.

Also not sure this matters though, if they're threads in the same process its a data race already and nobody cares. If they're not threads in the same process, they're separated by address space and can't 'see' each other anyway.

#7 lore raw
Quoted 6 lines · Peter Zijlstra

I'm not actually sure it does. There is the comment from 8643cda549ca4 which explain the program order guarantees.

But I'm not sure who or what would simply a full smp_mb() when you call schedule() -- I mean, its true on x86, but that's 'trivial'.

It's always been a requirement that if you actually context switch a full mb() is implied (though that isn't the case if you don't actually switch, ie, you are back to RUNNING before you even hit schedule).

On powerpc we have a sync deep in _switch to achieve that.

This is necessary so that a process who wakes up on a different CPU sees all of its own load/stores.

Quoted 6 lines
Quoted 3 lines

I mean, I thought that the LOAD/STORE's done by some task can't be re-ordered with LOAD/STORE's done by another task which was running on the same CPU. Wrong?

If so, I'm not sure how :/

Quoted 8 lines

So smp_mb__before_spinlock() stops stores from @prev, and the ACQUIRE from spin_lock(&rq->lock) stops both loads/stores from @next, but afaict nothing stops the loads from @prev seeing stores from @next.

Also not sure this matters though, if they're threads in the same process its a data race already and nobody cares. If they're not threads in the same process, they're separated by address space and can't 'see' each other anyway.

The architecture switch_to() has to do the right thing.

Cheers,
Ben.

maintainer
#8 lore raw
Quoted 4 lines · Benjamin Herrenschmidt

It's always been a requirement that if you actually context switch a full mb() is implied ...

On powerpc we have a sync deep in _switch to achieve that.

OK, fair enough. I must've missed it in the x86 switch_to, must be one of those implied serializing instructions I'm not too familiar with.

Quoted 2 lines

(though that isn't the case if you don't actually switch, ie, you are back to RUNNING before you even hit schedule).

Right, which invalidates the claim that schedule() implies a full mb,

Quoted 2 lines

This is necessary so that a process who wakes up on a different CPU sees all of its own load/stores.

Don't actually think its needed for that, see the comment from 8643cda549ca4, the scheduler has enough barriers to guarantee Program-Order for tasks without that.

#9 lore raw
Quoted 15 lines · Peter Zijlstra
Quoted 7 lines · Benjamin Herrenschmidt

It's always been a requirement that if you actually context switch a
full mb() is implied ...

On powerpc we have a sync deep in _switch to achieve that.

OK, fair enough. I must've missed it in the x86 switch_to, must be one
of those implied serializing instructions I'm not too familiar with.

Quoted 1 line
Quoted 4 lines
Quoted 2 lines

(though that isn't the case if you don't actually switch, ie, you are back to RUNNING before you even hit schedule).

Right, which invalidates the claim that schedule() implies a full mb,

Right, it's only full mb if you actually schedule to another process :- )

Quoted 9 lines
Quoted 4 lines

This is necessary so that a process who wakes up on a different CPU sees
all of its own load/stores.

Don't actually think its needed for that, see the comment from 8643cda549ca4, the scheduler has enough barriers to guarantee Program-Order for tasks without that.

maintainer
#10 lore raw
In reply to Benjamin Herrenschmidt
Quoted 1 line · Benjamin Herrenschmidt

On powerpc we have a sync deep in _switch to achieve that.

OK, for giggles, could you (or Balbir) check what happens if you take that sync out?

There should be enough serialization in the generic code to cover the case that code mentions.

ARM64 has a stronger barrier in its context switch code, but that's because they need to sync against external agents (like their TLB and cache) and no amount of generic locking is going to cover that.

#11 lore raw
Quoted 9 lines · Peter Zijlstra
Quoted 2 lines · Benjamin Herrenschmidt

On powerpc we have a sync deep in _switch to achieve that.

OK, for giggles, could you (or Balbir) check what happens if you take that sync out?

Quoted 6 lines

There should be enough serialization in the generic code to cover the case that code mentions.

ARM64 has a stronger barrier in its context switch code, but that's because they need to sync against external agents (like their TLB and cache) and no amount of generic locking is going to cover that.

The problem is no amount of testing can tell you it works for sure :-)

I would be nervous not having a real full sync in _switch. All we have along the scheduler path is lwsync's and our isync based load construct for spin_lock, I'm not sure what other assumptions we have around that sync in there...

Cheers,
Ben.

#12 lore raw
Quoted 17 lines · Benjamin Herrenschmidt
Quoted 9 lines · Peter Zijlstra
Quoted 2 lines · Benjamin Herrenschmidt

On powerpc we have a sync deep in _switch to achieve that.

OK, for giggles, could you (or Balbir) check what happens if you take that sync out?

Quoted 6 lines

There should be enough serialization in the generic code to cover the case that code mentions.

ARM64 has a stronger barrier in its context switch code, but that's because they need to sync against external agents (like their TLB and cache) and no amount of generic locking is going to cover that.

Quoted 7 lines

The problem is no amount of testing can tell you it works for sure :-)

I would be nervous not having a real full sync in _switch. All we have along the scheduler path is lwsync's and our isync based load construct for spin_lock, I'm not sure what other assumptions we have around that sync in there...

I would agree, I am not sure of the assumptions either.

Balbir Singh.

maintainer
#13 lore raw
In reply to Benjamin Herrenschmidt
Quoted 4 lines · Benjamin Herrenschmidt
Quoted 2 lines

OK, for giggles, could you (or Balbir) check what happens if you take that sync out?

The problem is no amount of testing can tell you it works for sure :-)

It breaking does prove the negative though, so still interesting.

Quoted 4 lines

I would be nervous not having a real full sync in _switch. All we have along the scheduler path is lwsync's and our isync based load construct for spin_lock, I'm not sure what other assumptions we have around that sync in there...

Only one way to find out ;-)

I'm not saying you should commit that change, just curious if (and how fast) it would come apart.

At the very least we could update the comment that goes with that sync.

#14 lore raw
Quoted 14 lines · Peter Zijlstra
Quoted 4 lines · Benjamin Herrenschmidt
Quoted 2 lines

OK, for giggles, could you (or Balbir) check what happens if you take that sync out?

The problem is no amount of testing can tell you it works for sure :-)

It breaking does prove the negative though, so still interesting.

Quoted 4 lines

I would be nervous not having a real full sync in _switch. All we have along the scheduler path is lwsync's and our isync based load construct for spin_lock, I'm not sure what other assumptions we have around that sync in there...

Quoted 6 lines

Only one way to find out ;-)

I'm not saying you should commit that change, just curious if (and how fast) it would come apart.

At the very least we could update the comment that goes with that sync.

Could there be some code that relies on the full barrier semantics of schedule() to provide transitivity?

IIUC, the Program Order Guarantee you stated before try_to_wake_up() only has ordering effect on wakers and wakees.

Regards,
Boqun

maintainer
#15 lore raw
Quoted 3 lines · Boqun Feng

On Thu, Sep 01, 2016 at 08:57:38AM +0200, Peter Zijlstra wrote:
Could there be some code that relies on the full barrier semantics of schedule() to provide transitivity?

Could, sure, who knows. RCU might, although Paul typically sticks in smp_mb just to be safe.

The kernel coming apart when you remove that sync would prove this fairly quick though.

Like Ben said, it not coming apart doesn't prove anything. It coming apart does however prove something, namely that it is required :-)

Quoted 2 lines

IIUC, the Program Order Guarantee you stated before try_to_wake_up() only has ordering effect on wakers and wakees.

Right, the scheduler only does RCpc guarantees.

#16 lore raw
In reply to Oleg Nesterov
Quoted 5 lines · Oleg Nesterov

Confused... how this connects to UNLOCK+LOCK on rq->lock? A LOAD can leak into the critical section.

But context switch should imply mb() we can rely on?

Between setting of ->on_rq and returning to the task so it can change its state back to [UN]INTERRUPTIBLE, there will be at least one write barrier (spin unlock of the rq), possibly even a full barrier (context switch). The write barrier is enough so I didn't dig to make sure we always context switch in the scenario we're looking at but I think we do.

Cheers,
Ben.

maintainer
#17 lore raw
Quoted 10 lines · Benjamin Herrenschmidt
Quoted 5 lines · Oleg Nesterov

Confused... how this connects to UNLOCK+LOCK on rq->lock? A LOAD can leak into the critical section.

But context switch should imply mb() we can rely on?

Between setting of ->on_rq and returning to the task so it can change its state back to [UN]INTERRUPTIBLE, there will be at least one write barrier (spin unlock of the rq),

spin-unlock is _not_ a write barrier, its a RELEASE barrier, and is not sufficient for this.

Quoted 4 lines

possibly even a full barrier
(context switch). The write barrier is enough so I didn't dig to make sure we always context switch in the scenario we're looking at but I think we do.

There is enough, you just need to pair the RELEASE with an ACQUIRE to get a full load-store barrier.

#18 lore raw
Quoted 8 lines · Peter Zijlstra
Quoted 7 lines · Benjamin Herrenschmidt
Quoted 5 lines · Oleg Nesterov

Confused... how this connects to UNLOCK+LOCK on rq->lock? A LOAD can leak into the critical section.

Quoted 8 lines
Quoted 5 lines
Quoted 1 line

But context switch should imply mb() we can rely on?

Between setting of ->on_rq and returning to the task so it can change its state back to [UN]INTERRUPTIBLE, there will be at least one write barrier (spin unlock of the rq),

spin-unlock is _not_ a write barrier, its a RELEASE barrier, and is not sufficient for this.

Ah yes well it's an lwsync so it's a wmb for us :-) .

Quoted 7 lines
Quoted 4 lines

possibly even a full barrier
(context switch). The write barrier is enough so I didn't dig to make sure we always context switch in the scenario we're looking at but I think we do.

There is enough, you just need to pair the RELEASE with an ACQUIRE to get a full load-store barrier.

Right so I *think* there will be at least the release of the rq_lock by the IPI followed by schedule itself taking and releasing it again, but I can't vouch for it. As I said, I didn't dig deeper on that side of things as for us a spin_unlock is a write barrier and for the write side that concerns me here it's sufficient ;-) It's the read side that has a problem.

That said you may want to investigate more to make sure there is no way out of schedule where that spin_unlock is the only thing between setting on_rq and coming out (which leads to setting the task state).

I suspect there will be at least one more re-aquisition & release of the rq lock but I may be wrong.

Cheers,
Ben.

#19 lore raw
In reply to Peter Zijlstra
Quoted 22 lines · Peter Zijlstra
Quoted 5 lines · Balbir Singh

The origin of the issue I've seen seems to be related to rwsem spin lock stealing. Basically I see the system deadlock'd in the following state

As Nick says (good to see you're back Nick!), this is unrelated to rwsems.

This is true for pretty much every blocking wait loop out there, they all do:

	for (;;) {
		current->state = UNINTERRUPTIBLE;
		smp_mb();
		if (cond)
			break;
		schedule();
	}
	current->state = RUNNING;
Quoted 1 line

Which, if the wakeup is spurious, is just the pattern you need.

Yes True! My bad Alexey had seen the same basic pattern, I should have been clearer in my commit log. Should I resend the patch?

Quoted 6 lines
Quoted 6 lines

+++ b/kernel/sched/core.c

kernel/sched/core.c +0 -0
@@ -2016,6 +2016,17 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
 	success = 1; /* we're going to change ->state */
 	cpu = task_cpu(p);
 
Quoted 10 lines

kernel/sched/core.c try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) · line 2024

Quoted 6 lines
kernel/sched/core.c +6 -0
+	/*
+	 * Ensure we see on_rq and p_state consistently
+	 *
+	 * For example in __rwsem_down_write_failed(), we have
+	 *    [S] ->on_rq = 1				[L] ->state
+	 *    MB					 RMB

There isn't an MB there. The best I can do is UNLOCK+LOCK, which, thanks to PPC, is _not_ MB. It is however sufficient for this case.

The MB comes from the __switch_to() in schedule(). Ben mentioned it in a different thread.

Quoted 27 lines

kernel/sched/core.c try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) · line 2028

Quoted 4 lines
kernel/sched/core.c +4 -0
+	 *    [S] ->state = TASK_UNINTERRUPTIBLE	[L] ->on_rq
+	 * In the absence of the RMB p->on_rq can be observed to be 0
+	 * and we end up spinning indefinitely in while (p->on_cpu)
+	 */

/*
* Ensure we load p->on_rq _after_ p->state, otherwise it would
* be possible to, falsely, observe p->on_rq == 0 and get stuck
* in smp_cond_load_acquire() below.
*
* sched_ttwu_pending() try_to_wake_up()
* [S] p->on_rq = 1; [L] P->state
* UNLOCK rq->lock
*
* schedule() RMB
* LOCK rq->lock
* UNLOCK rq->lock
*
* [task p]
* [S] p->state = UNINTERRUPTIBLE [L] p->on_rq
*
* Pairs with the UNLOCK+LOCK on rq->lock from the
* last wakeup of our task and the schedule that got our task
* current.
*/

Quoted 10 lines

kernel/sched/core.c try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) · line 2032

Quoted 4 lines
kernel/sched/core.c +1 -0
+	smp_rmb();
 	if (p->on_rq && ttwu_remote(p, wake_flags))
 		goto stat;
 

Now, this has been present for a fair while, I suspect ever since we reworked the wakeup path to not use rq->lock twice. Curious you only now hit it.

Yes, I just hit it a a week or two back and I needed to collect data to explain why p->on_rq got to 0. Hitting it requires extreme stress -- for me I needed a system with large threads and less memory running stress-ng. Reproducing the problem takes an unpredictable amount of time.

Balbir Singh.

maintainer
#20 lore raw
Quoted 23 lines · Balbir Singh
Quoted 22 lines · Peter Zijlstra
Quoted 5 lines · Balbir Singh

The origin of the issue I've seen seems to be related to rwsem spin lock stealing. Basically I see the system deadlock'd in the following state

As Nick says (good to see you're back Nick!), this is unrelated to rwsems.

This is true for pretty much every blocking wait loop out there, they all do:

	for (;;) {
		current->state = UNINTERRUPTIBLE;
		smp_mb();
		if (cond)
			break;
		schedule();
	}
	current->state = RUNNING;
Quoted 4 lines
Quoted 1 line

Which, if the wakeup is spurious, is just the pattern you need.

Yes True! My bad Alexey had seen the same basic pattern, I should have been clearer in my commit log. Should I resend the patch?

Yes please.

Quoted 6 lines
Quoted 3 lines

There isn't an MB there. The best I can do is UNLOCK+LOCK, which, thanks to PPC, is _not_ MB. It is however sufficient for this case.

The MB comes from the __switch_to() in schedule(). Ben mentioned it in a different thread.

Right, although even without that, there is sufficient ordering, as the rq unlock from the wakeup, coupled with the rq lock from the schedule already form a load-store barrier.

Quoted 9 lines
Quoted 4 lines

Now, this has been present for a fair while, I suspect ever since we reworked the wakeup path to not use rq->lock twice. Curious you only now hit it.

Yes, I just hit it a a week or two back and I needed to collect data to explain why p->on_rq got to 0. Hitting it requires extreme stress -- for me I needed a system with large threads and less memory running stress-ng. Reproducing the problem takes an unpredictable amount of time.

What hardware do you see this on, is it shiny new Power8 chips which have never before seen deep queues or something. Or is it 'regular' old Power7 like stuff?

#21 lore raw
Quoted 24 lines · Peter Zijlstra
Quoted 23 lines · Balbir Singh
Quoted 22 lines · Peter Zijlstra
Quoted 5 lines · Balbir Singh

The origin of the issue I've seen seems to be related to rwsem spin lock stealing. Basically I see the system deadlock'd in the following state

As Nick says (good to see you're back Nick!), this is unrelated to rwsems.

This is true for pretty much every blocking wait loop out there, they all do:

	for (;;) {
		current->state = UNINTERRUPTIBLE;
		smp_mb();
		if (cond)
			break;
		schedule();
	}
	current->state = RUNNING;
Quoted 7 lines
Quoted 4 lines
Quoted 1 line

Which, if the wakeup is spurious, is just the pattern you need.

Yes True! My bad Alexey had seen the same basic pattern, I should have been clearer in my commit log. Should I resend the patch?

Yes please.

Done, just now. I've tried to generalize the issue, but I've kept the example

Quoted 16 lines
Quoted 6 lines
Quoted 3 lines

There isn't an MB there. The best I can do is UNLOCK+LOCK, which, thanks to PPC, is _not_ MB. It is however sufficient for this case.

The MB comes from the __switch_to() in schedule(). Ben mentioned it in a different thread.

Right, although even without that, there is sufficient ordering, as the rq unlock from the wakeup, coupled with the rq lock from the schedule already form a load-store barrier.

Quoted 5 lines
Quoted 4 lines

Now, this has been present for a fair while, I suspect ever since we reworked the wakeup path to not use rq->lock twice. Curious you only now hit it.

Quoted 9 lines
Quoted 4 lines

Yes, I just hit it a a week or two back and I needed to collect data to explain why p->on_rq got to 0. Hitting it requires extreme stress -- for me I needed a system with large threads and less memory running stress-ng. Reproducing the problem takes an unpredictable amount of time.

What hardware do you see this on, is it shiny new Power8 chips which have never before seen deep queues or something. Or is it 'regular' old Power7 like stuff?

I don't think the issue is processor specific, it is probabilistic, but I've not tested on Power7. I am seeing it on a Power8 system

Balbir Singh

#22 lore raw
In reply to Peter Zijlstra
Quoted 4 lines · Peter Zijlstra

What hardware do you see this on, is it shiny new Power8 chips which have never before seen deep queues or something. Or is it 'regular' old Power7 like stuff?

Power8 which isn't *that* new these days...

Cheers,
Ben.

#23 lore raw
In reply to Peter Zijlstra
Quoted 47 lines · Peter Zijlstra
Quoted 23 lines · Balbir Singh
Quoted 22 lines · Peter Zijlstra
Quoted 5 lines · Balbir Singh

The origin of the issue I've seen seems to be related to rwsem spin lock stealing. Basically I see the system deadlock'd in the following state

As Nick says (good to see you're back Nick!), this is unrelated to rwsems.

This is true for pretty much every blocking wait loop out there, they all do:

	for (;;) {
		current->state = UNINTERRUPTIBLE;
		smp_mb();
		if (cond)
			break;
		schedule();
	}
	current->state = RUNNING;
Quoted 4 lines
Quoted 1 line

Which, if the wakeup is spurious, is just the pattern you need.

Yes True! My bad Alexey had seen the same basic pattern, I should have been clearer in my commit log. Should I resend the patch?

Yes please.

Quoted 6 lines
Quoted 3 lines

There isn't an MB there. The best I can do is UNLOCK+LOCK, which, thanks to PPC, is _not_ MB. It is however sufficient for this case.

The MB comes from the __switch_to() in schedule(). Ben mentioned it in a different thread.

Right, although even without that, there is sufficient ordering, as the rq unlock from the wakeup, coupled with the rq lock from the schedule already form a load-store barrier.

Quoted 5 lines
Quoted 4 lines

Now, this has been present for a fair while, I suspect ever since we reworked the wakeup path to not use rq->lock twice. Curious you only now hit it.

Quoted 8 lines
Quoted 4 lines

Yes, I just hit it a a week or two back and I needed to collect data to explain why p->on_rq got to 0. Hitting it requires extreme stress -- for me I needed a system with large threads and less memory running stress-ng. Reproducing the problem takes an unpredictable amount of time.

What hardware do you see this on, is it shiny new Power8 chips which have never before seen deep queues or something. Or is it 'regular' old Power7 like stuff?

I am seeing it on POWER8 with KVM and 2 guests, each having 3 virtio-net devices with vhost enabled, all virtio-net devices are connected to the same virtual bridge on the host (via /dev/tap*) and are doing lots of trafic, just between these 2 guests.

I remember doing the same test on POWER7 more than 2 years ago and finding missing barriers in virtio but nothing like this one. But POWER7 is seriously slower than POWER8 so it seems that nobody bothered with loading it that much.

I wonder how to reproduce the bug quicker as sometime it works days with no fault but sometime it fails within first 30 minutes (backtraces from 2 stuck CPUs are the same though), anyone has an idea (kernel hacks, taskset, type of traficб уес)? As Nick suggested, I changed cpus_share_cache() to return "false" so ttwu_queue() would always go via ttwu_queue_remote() path but this did not make any difference.

Signature · 1 line
Alexey
#24 lore raw
Quoted 67 lines · Alexey Kardashevskiy
Quoted 47 lines · Peter Zijlstra
Quoted 23 lines · Balbir Singh
Quoted 22 lines · Peter Zijlstra
Quoted 5 lines · Balbir Singh

The origin of the issue I've seen seems to be related to rwsem spin lock stealing. Basically I see the system deadlock'd in the following state

As Nick says (good to see you're back Nick!), this is unrelated to rwsems.

This is true for pretty much every blocking wait loop out there, they all do:

	for (;;) {
		current->state = UNINTERRUPTIBLE;
		smp_mb();
		if (cond)
			break;
		schedule();
	}
	current->state = RUNNING;
Quoted 4 lines
Quoted 1 line

Which, if the wakeup is spurious, is just the pattern you need.

Yes True! My bad Alexey had seen the same basic pattern, I should have been clearer in my commit log. Should I resend the patch?

Yes please.

Quoted 6 lines
Quoted 3 lines

There isn't an MB there. The best I can do is UNLOCK+LOCK, which, thanks to PPC, is _not_ MB. It is however sufficient for this case.

The MB comes from the __switch_to() in schedule(). Ben mentioned it in a different thread.

Right, although even without that, there is sufficient ordering, as the rq unlock from the wakeup, coupled with the rq lock from the schedule already form a load-store barrier.

Quoted 5 lines
Quoted 4 lines

Now, this has been present for a fair while, I suspect ever since we reworked the wakeup path to not use rq->lock twice. Curious you only now hit it.

Quoted 8 lines
Quoted 4 lines

Yes, I just hit it a a week or two back and I needed to collect data to explain why p->on_rq got to 0. Hitting it requires extreme stress -- for me I needed a system with large threads and less memory running stress-ng. Reproducing the problem takes an unpredictable amount of time.

What hardware do you see this on, is it shiny new Power8 chips which have never before seen deep queues or something. Or is it 'regular' old Power7 like stuff?

I am seeing it on POWER8 with KVM and 2 guests, each having 3 virtio-net devices with vhost enabled, all virtio-net devices are connected to the same virtual bridge on the host (via /dev/tap*) and are doing lots of trafic, just between these 2 guests.

I remember doing the same test on POWER7 more than 2 years ago and finding missing barriers in virtio but nothing like this one. But POWER7 is seriously slower than POWER8 so it seems that nobody bothered with loading it that much.

Quoted 6 lines

I wonder how to reproduce the bug quicker as sometime it works days with no fault but sometime it fails within first 30 minutes (backtraces from 2 stuck CPUs are the same though), anyone has an idea (kernel hacks, taskset, type of traficб уес)? As Nick suggested, I changed cpus_share_cache() to return "false" so ttwu_queue() would always go via ttwu_queue_remote() path but this did not make any difference.

Below are the backtraces of 2 stuck cpus (they could not be stopped in xmon as others, got these via bmc). I am also adding Michael in cc:, just in case...

0:mon> t 0xc000000fd4ab79b0
[c000000fd4ab79b0] c0000000001330c4 do_raw_spin_lock+0x1f4/0x260 [c000000fd4ab79f0] c000000000a368e8 _raw_spin_lock_irqsave+0x98/0xd0 [c000000fd4ab7a30] c00000000011ecbc remove_wait_queue+0x2c/0x70 [c000000fd4ab7a70] d0000000166e0364 vhost_poll_stop+0x34/0x60 [vhost] [c000000fd4ab7aa0] d0000000167a08c8 handle_rx+0x168/0x8d0 [vhost_net] [c000000fd4ab7c80] d0000000166e04e0 vhost_worker+0x120/0x1d0 [vhost] [c000000fd4ab7d00] c0000000000ebad8 kthread+0x118/0x140 [c000000fd4ab7e30] c0000000000098e8 ret_from_kernel_thread+0x5c/0x74

0:mon> t 0xc000001fff41b5a0
[c000001fff41b5a0] c0000000000fc3ac try_to_wake_up+0x5c/0x6c0 [c000001fff41b630] d0000000166e0fcc vhost_work_queue+0x6c/0x90 [vhost] [c000001fff41b660] d0000000166e205c vhost_poll_wakeup+0x3c/0x50 [vhost] [c000001fff41b680] c00000000011e6d4 __wake_up_common+0x84/0xf0 [c000001fff41b6e0] c00000000011ee98 __wake_up_sync_key+0x68/0xa0 [c000001fff41b730] c0000000008defd0 sock_def_readable+0x80/0x180 [c000001fff41b760] d0000000167438ac tun_net_xmit+0x52c/0x5d0 [tun] [c000001fff41b7b0] c000000000906dd8 dev_hard_start_xmit+0x178/0x450 [c000001fff41b870] c000000000938d6c sch_direct_xmit+0x11c/0x250 [c000001fff41b910] c000000000907840 __dev_queue_xmit+0x560/0x8c0 [c000001fff41b9c0] d000000016553c80 br_dev_queue_push_xmit+0xb0/0x250 [bridge] [c000001fff41ba00] d000000016553e54 br_forward_finish+0x34/0xe0 [bridge] [c000001fff41ba80] d000000016554044 __br_forward.isra.0+0x144/0x220 [bridge] [c000001fff41baf0] d000000016555e78 br_handle_frame_finish+0x148/0x570 [bridge] [c000001fff41bb80] d00000001655654c br_handle_frame+0x24c/0x400 [bridge] [c000001fff41bc10] c0000000008fed28 __netif_receive_skb_core+0x498/0xc60 [c000001fff41bcf0] c000000000904314 process_backlog+0x114/0x220 [c000001fff41bd60] c00000000090343c net_rx_action+0x36c/0x520 [c000001fff41be70] c0000000000c5068 __do_softirq+0x258/0x5b0 [c000001fff41bf90] c000000000028bd0 call_do_softirq+0x14/0x24 [c000000fc675b950] c0000000000155f8 do_softirq_own_stack+0x58/0xa0 [c000000fc675b990] c0000000000c4cb4 do_softirq.part.3+0x74/0xa0 [c000000fc675b9c0] c0000000008fe674 netif_rx_ni+0x1d4/0x230 [c000000fc675ba00] d0000000167415f8 tun_get_user+0x408/0xbc0 [tun] [c000000fc675baf0] d000000016741e04 tun_sendmsg+0x54/0x90 [tun] [c000000fc675bb30] d0000000167a1f68 handle_tx+0x298/0x5f0 [vhost_net] [c000000fc675bc80] d0000000166e04e0 vhost_worker+0x120/0x1d0 [vhost] [c000000fc675bd00] c0000000000ebad8 kthread+0x118/0x140 [c000000fc675be30] c0000000000098e8 ret_from_kernel_thread+0x5c/0x74 0:mon>

Signature · 1 line
Alexey
#25 lore raw
In reply to Balbir Singh
Quoted 128 lines · Balbir Singh

The origin of the issue I've seen seems to be related to rwsem spin lock stealing. Basically I see the system deadlock'd in the following state

I have a system with multiple threads and

Most of the threads are stuck doing

[67272.593915] --- interrupt: e81 at _raw_spin_lock_irqsave+0xa4/0x130
[67272.593915]     LR = _raw_spin_lock_irqsave+0x9c/0x130
[67272.700996] [c000000012857ae0] [c00000000012453c] rwsem_wake+0xcc/0x110
[67272.749283] [c000000012857b20] [c0000000001215d8] up_write+0x78/0x90
[67272.788965] [c000000012857b50] [c00000000028153c] unlink_anon_vmas+0x15c/0x2c0
[67272.798782] [c000000012857bc0] [c00000000026f5c0] free_pgtables+0xf0/0x1c0
[67272.842528] [c000000012857c10] [c00000000027c9a0] exit_mmap+0x100/0x1a0
[67272.872947] [c000000012857cd0] [c0000000000b4a98] mmput+0xa8/0x1b0
[67272.898432] [c000000012857d00] [c0000000000bc50c] do_exit+0x33c/0xc30
[67272.944721] [c000000012857dc0] [c0000000000bcee4] do_group_exit+0x64/0x100
[67272.969014] [c000000012857e00] [c0000000000bcfac] SyS_exit_group+0x2c/0x30
[67272.978971] [c000000012857e30] [c000000000009204] system_call+0x38/0xb4
[67272.999016] Instruction dump:

They are spinning on the sem->wait_lock, the holder of sem->wait_lock has irq's disabled and is doing

[c00000037930fb30] c0000000000f724c try_to_wake_up+0x6c/0x570 [c00000037930fbb0] c000000000124328 __rwsem_do_wake+0x1f8/0x260 [c00000037930fc00] c0000000001244b4 rwsem_wake+0x84/0x110 [c00000037930fc40] c000000000121598 up_write+0x78/0x90 [c00000037930fc70] c000000000281a54 anon_vma_fork+0x184/0x1d0 [c00000037930fcc0] c0000000000b68e0 copy_process.isra.5+0x14c0/0x1870 [c00000037930fda0] c0000000000b6e68 _do_fork+0xa8/0x4b0 [c00000037930fe30] c000000000009460 ppc_clone+0x8/0xc

The offset of try_to_wake_up is actually misleading, it is actually stuck doing the following in try_to_wake_up

while (p->on_cpu)

	cpu_relax();

Analysis

The issue is triggered, due to the following race

CPU1 CPU2

while () {
if (cond)

    break;
  do {
    schedule();
    set_current_state(TASK_UN..)

} while (!cond);
rwsem_wake()
spin_lock_irqsave(wait_lock)
raw_spin_lock_irqsave(wait_lock) wake_up_process()
} try_to_wake_up()
set_current_state(TASK_RUNNING); ..
list_del(&waiter.list);

CPU2 wakes up CPU1, but before it can get the wait_lock and set current state to TASK_RUNNING the following occurs

CPU3
(stole the rwsem before waiter can be woken up from queue) up_write()
rwsem_wake()
raw_spin_lock_irqsave(wait_lock)
if (!list_empty)
wake_up_process()
try_to_wake_up() raw_spin_lock_irqsave(p->pi_lock)
..
if (p->on_rq && ttwu_wakeup())
..
while (p->on_cpu)

    cpu_relax()

..

CPU3 tries to wake up the task on CPU1 again since it finds it on the wait_queue, CPU1 is spinning on wait_lock, but immediately after CPU2, CPU3 got it.

CPU3 checks the state of p on CPU1, it is TASK_UNINTERRUPTIBLE and the task is spinning on the wait_lock. Interestingly since p->on_rq is checked under pi_lock, I've noticed that try_to_wake_up() finds p->on_rq to be 0. This was the most confusing bit of the analysis, but p->on_rq is changed under runqueue lock, rq_lock, the p->on_rq check is not reliable without this fix IMHO. The race is visible (based on the analysis) only when ttwu_queue() does a remote wakeup via ttwu_queue_remote. In which case the p->on_rq change is not done uder the pi_lock.

The result is that after a while the entire system locks up on the raw_spin_irqlock_save(wait_lock) and the holder spins infintely

Reproduction of the issue

The issue can be reproduced after a long run on my system with 80 threads and having to tweak available memory to very low and running memory stress-ng mmapfork test. It usually takes a long time to reproduce. I am trying to work on a test case that can reproduce the issue faster, but thats work in progress. I am still testing the changes on my still in a loop and the tests seem OK thus far.

Big thanks to Benjamin and Nick for helping debug this as well. Ben helped catch the missing barrier, Nick caught every missing bit in my theory

Cc Peter Zijlstra <[email protected]>
Cc Nicholas Piggin <[email protected]>
Cc Benjamin Herrenschmidt <[email protected]>
---
 kernel/sched/core.c | 11 +++++++++++
 1 file changed, 11 insertions(+)
kernel/sched/core.c +1 -0
index 2a906f2..582c684 100644
@@ -2016,6 +2016,17 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
 	success = 1; /* we're going to change ->state */
 	cpu = task_cpu(p);
 
+	/*

kernel/sched/core.c try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) · line 2029

Quoted 10 lines
kernel/sched/core.c +10 -0
+	 * Ensure we see on_rq and p_state consistently
+	 *
+	 * For example in __rwsem_down_write_failed(), we have
+	 *    [S] ->on_rq = 1				[L] ->state
+	 *    MB					 RMB
+	 *    [S] ->state = TASK_UNINTERRUPTIBLE	[L] ->on_rq
+	 * In the absence of the RMB p->on_rq can be observed to be 0
+	 * and we end up spinning indefinitely in while (p->on_cpu)
+	 */
+	smp_rmb();

I think the patch is fine... but unless I am totally confused this is not specific to __rwsem_down_write_failed(). ttwu() can hang the same way if the target simply does

	schedule_timeout();
	current->state = TASK_INTERRUPTIBLE;
	current->state = TASK_RUNNING;

And. I am not sure I understand where this MB above comes from.

Oleg.

#26 lore raw
Quoted 144 lines · Oleg Nesterov
Quoted 128 lines · Balbir Singh

The origin of the issue I've seen seems to be related to rwsem spin lock stealing. Basically I see the system deadlock'd in the following state

I have a system with multiple threads and

Most of the threads are stuck doing

[67272.593915] --- interrupt: e81 at _raw_spin_lock_irqsave+0xa4/0x130
[67272.593915]     LR = _raw_spin_lock_irqsave+0x9c/0x130
[67272.700996] [c000000012857ae0] [c00000000012453c] rwsem_wake+0xcc/0x110
[67272.749283] [c000000012857b20] [c0000000001215d8] up_write+0x78/0x90
[67272.788965] [c000000012857b50] [c00000000028153c] unlink_anon_vmas+0x15c/0x2c0
[67272.798782] [c000000012857bc0] [c00000000026f5c0] free_pgtables+0xf0/0x1c0
[67272.842528] [c000000012857c10] [c00000000027c9a0] exit_mmap+0x100/0x1a0
[67272.872947] [c000000012857cd0] [c0000000000b4a98] mmput+0xa8/0x1b0
[67272.898432] [c000000012857d00] [c0000000000bc50c] do_exit+0x33c/0xc30
[67272.944721] [c000000012857dc0] [c0000000000bcee4] do_group_exit+0x64/0x100
[67272.969014] [c000000012857e00] [c0000000000bcfac] SyS_exit_group+0x2c/0x30
[67272.978971] [c000000012857e30] [c000000000009204] system_call+0x38/0xb4
[67272.999016] Instruction dump:

They are spinning on the sem->wait_lock, the holder of sem->wait_lock has irq's disabled and is doing

[c00000037930fb30] c0000000000f724c try_to_wake_up+0x6c/0x570 [c00000037930fbb0] c000000000124328 __rwsem_do_wake+0x1f8/0x260 [c00000037930fc00] c0000000001244b4 rwsem_wake+0x84/0x110 [c00000037930fc40] c000000000121598 up_write+0x78/0x90 [c00000037930fc70] c000000000281a54 anon_vma_fork+0x184/0x1d0 [c00000037930fcc0] c0000000000b68e0 copy_process.isra.5+0x14c0/0x1870 [c00000037930fda0] c0000000000b6e68 _do_fork+0xa8/0x4b0 [c00000037930fe30] c000000000009460 ppc_clone+0x8/0xc

The offset of try_to_wake_up is actually misleading, it is actually stuck doing the following in try_to_wake_up

while (p->on_cpu)

	cpu_relax();

Analysis

The issue is triggered, due to the following race

CPU1 CPU2

while () {
if (cond)

    break;
  do {
    schedule();
    set_current_state(TASK_UN..)

} while (!cond);
rwsem_wake()
spin_lock_irqsave(wait_lock)
raw_spin_lock_irqsave(wait_lock) wake_up_process()
} try_to_wake_up()
set_current_state(TASK_RUNNING); ..
list_del(&waiter.list);

CPU2 wakes up CPU1, but before it can get the wait_lock and set current state to TASK_RUNNING the following occurs

CPU3
(stole the rwsem before waiter can be woken up from queue) up_write()
rwsem_wake()
raw_spin_lock_irqsave(wait_lock)
if (!list_empty)
wake_up_process()
try_to_wake_up() raw_spin_lock_irqsave(p->pi_lock)
..
if (p->on_rq && ttwu_wakeup())
..
while (p->on_cpu)

    cpu_relax()

..

CPU3 tries to wake up the task on CPU1 again since it finds it on the wait_queue, CPU1 is spinning on wait_lock, but immediately after CPU2, CPU3 got it.

CPU3 checks the state of p on CPU1, it is TASK_UNINTERRUPTIBLE and the task is spinning on the wait_lock. Interestingly since p->on_rq is checked under pi_lock, I've noticed that try_to_wake_up() finds p->on_rq to be 0. This was the most confusing bit of the analysis, but p->on_rq is changed under runqueue lock, rq_lock, the p->on_rq check is not reliable without this fix IMHO. The race is visible (based on the analysis) only when ttwu_queue() does a remote wakeup via ttwu_queue_remote. In which case the p->on_rq change is not done uder the pi_lock.

The result is that after a while the entire system locks up on the raw_spin_irqlock_save(wait_lock) and the holder spins infintely

Reproduction of the issue

The issue can be reproduced after a long run on my system with 80 threads and having to tweak available memory to very low and running memory stress-ng mmapfork test. It usually takes a long time to reproduce. I am trying to work on a test case that can reproduce the issue faster, but thats work in progress. I am still testing the changes on my still in a loop and the tests seem OK thus far.

Big thanks to Benjamin and Nick for helping debug this as well. Ben helped catch the missing barrier, Nick caught every missing bit in my theory

Cc Peter Zijlstra <[email protected]>
Cc Nicholas Piggin <[email protected]>
Cc Benjamin Herrenschmidt <[email protected]>
---
 kernel/sched/core.c | 11 +++++++++++
 1 file changed, 11 insertions(+)
kernel/sched/core.c +1 -0
index 2a906f2..582c684 100644
@@ -2016,6 +2016,17 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
 	success = 1; /* we're going to change ->state */
 	cpu = task_cpu(p);
 
+	/*

kernel/sched/core.c try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) · line 2029

Quoted 10 lines
kernel/sched/core.c +10 -0
+	 * Ensure we see on_rq and p_state consistently
+	 *
+	 * For example in __rwsem_down_write_failed(), we have
+	 *    [S] ->on_rq = 1				[L] ->state
+	 *    MB					 RMB
+	 *    [S] ->state = TASK_UNINTERRUPTIBLE	[L] ->on_rq
+	 * In the absence of the RMB p->on_rq can be observed to be 0
+	 * and we end up spinning indefinitely in while (p->on_cpu)
+	 */
+	smp_rmb();

I think the patch is fine... but unless I am totally confused this is not specific to __rwsem_down_write_failed(). ttwu() can hang the same way if the target simply does

Quoted 2 lines
	schedule_timeout();
	current->state = TASK_INTERRUPTIBLE;

Yes

Quoted 3 lines
	current->state = TASK_RUNNING;

And. I am not sure I understand where this MB above comes from.

I think Ben pointed that out earlier and you found it in the documentation as well at the end of __switch

Balbir Singh