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

Groups > linux.kernel > #1472327 > unrolled thread

[RFC][PATCH] Fix a race between rwsem and the scheduler

Back to article view | Back to linux.kernel

Contents

  [RFC][PATCH] Fix a race between rwsem and the scheduler Balbir Singh <bsingharora@gmail.com> - 2016-08-30 10:50 +0200
    Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Nicholas Piggin <npiggin@gmail.com> - 2016-08-30 11:20 +0200
    Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Peter Zijlstra <peterz@infradead.org> - 2016-08-30 14:20 +0200
      Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Oleg Nesterov <oleg@redhat.com> - 2016-08-30 15:10 +0200
        Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Peter Zijlstra <peterz@infradead.org> - 2016-08-30 16:20 +0200
          Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Oleg Nesterov <oleg@redhat.com> - 2016-08-30 19:00 +0200
            Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Peter Zijlstra <peterz@infradead.org> - 2016-08-30 20:40 +0200
              Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Benjamin Herrenschmidt <benh@kernel.crashing.org> - 2016-08-30 23:30 +0200
                Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Peter Zijlstra <peterz@infradead.org> - 2016-08-31 09:20 +0200
                  Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Benjamin Herrenschmidt <benh@kernel.crashing.org> - 2016-08-31 13:40 +0200
                Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Peter Zijlstra <peterz@infradead.org> - 2016-08-31 15:40 +0200
                  Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Benjamin Herrenschmidt <benh@kernel.crashing.org> - 2016-08-31 23:50 +0200
                    Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Balbir Singh <bsingharora@gmail.com> - 2016-09-01 08:50 +0200
                    Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Peter Zijlstra <peterz@infradead.org> - 2016-09-01 09:00 +0200
                      Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Boqun Feng <boqun.feng@gmail.com> - 2016-09-01 16:20 +0200
                        Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Peter Zijlstra <peterz@infradead.org> - 2016-09-01 17:40 +0200
        Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Benjamin Herrenschmidt <benh@kernel.crashing.org> - 2016-08-30 23:30 +0200
          Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Peter Zijlstra <peterz@infradead.org> - 2016-08-31 09:30 +0200
            Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Benjamin Herrenschmidt <benh@kernel.crashing.org> - 2016-08-31 13:40 +0200
      Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Balbir Singh <bsingharora@gmail.com> - 2016-08-31 05:50 +0200
        Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Peter Zijlstra <peterz@infradead.org> - 2016-08-31 09:30 +0200
          Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Balbir Singh <bsingharora@gmail.com> - 2016-08-31 12:20 +0200
          Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Benjamin Herrenschmidt <benh@kernel.crashing.org> - 2016-08-31 13:00 +0200
          Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Alexey Kardashevskiy <aik@ozlabs.ru> - 2016-09-01 03:50 +0200
            Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Alexey Kardashevskiy <aik@ozlabs.ru> - 2016-09-01 14:20 +0200
    Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Oleg Nesterov <oleg@redhat.com> - 2016-08-30 15:00 +0200
      Re: [RFC][PATCH] Fix a race between rwsem and the scheduler Balbir Singh <bsingharora@gmail.com> - 2016-08-31 05:50 +0200

Page 1 of 2  [1] 2  Next page →

#1472327 — [RFC][PATCH] 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 <peterz@infradead.org>
Cc: Nicholas Piggin <npiggin@gmail.com>
Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>

Signed-off-by: Balbir Singh <bsingharora@gmail.com>
---
 kernel/sched/core.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 2a906f2..582c684 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -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;
 
-- 
2.5.5

[toc] | [next] | [standalone]

#1472343

On Tue, 30 Aug 2016 18:49:37 +1000
Balbir Singh <bsingharora@gmail.com> 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.

> 
> 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 <peterz@infradead.org>
> Cc: Nicholas Piggin <npiggin@gmail.com>
> Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
> 
> Signed-off-by: Balbir Singh <bsingharora@gmail.com>
> ---
>  kernel/sched/core.c | 11 +++++++++++
>  1 file changed, 11 insertions(+)
> 
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 2a906f2..582c684 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -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;
>  

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

#1472447

On Tue, Aug 30, 2016 at 06:49:37PM +1000, Balbir Singh 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

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.

> +++ b/kernel/sched/core.c
> @@ -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.

> +	 *    [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.
	 */

> +	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.

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

#1472471

On 08/30, Peter Zijlstra wrote:
>
> 	/*
> 	 * 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.
> 	 */

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.

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

#1472505

On Tue, Aug 30, 2016 at 03:04:27PM +0200, Oleg Nesterov wrote:
> On 08/30, Peter Zijlstra wrote:
> >
> > 	/*
> > 	 * 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.
> > 	 */
> 
> 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).

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

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

#1472641

On 08/30, Peter Zijlstra wrote:
> On Tue, Aug 30, 2016 at 03:04:27PM +0200, Oleg Nesterov wrote:
> > On 08/30, Peter Zijlstra wrote:
> > >
> > > 	/*
> > > 	 * 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.
> > > 	 */
> >
> > 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.

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

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

#1472756

On Tue, Aug 30, 2016 at 06:57:47PM +0200, Oleg Nesterov wrote:
> On 08/30, Peter Zijlstra wrote:
> > On Tue, Aug 30, 2016 at 03:04:27PM +0200, Oleg Nesterov wrote:

> > > 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'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'.

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

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

#1472888

On Tue, 2016-08-30 at 20:34 +0200, Peter Zijlstra wrote:
> 
> 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.

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

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

Cheers,
Ben.

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

#1473077

On Wed, Aug 31, 2016 at 07:28:18AM +1000, Benjamin Herrenschmidt wrote:
> 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.

> (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,

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

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

#1473354

On Wed, 2016-08-31 at 09:18 +0200, Peter Zijlstra wrote:
> On Wed, Aug 31, 2016 at 07:28:18AM +1000, Benjamin Herrenschmidt
> wrote:
> > 
> > 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.
> 
> > 
> > (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 :-
)

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

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

#1473472

On Wed, Aug 31, 2016 at 07:28:18AM +1000, Benjamin Herrenschmidt wrote:

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

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

#1473904

On Wed, 2016-08-31 at 15:31 +0200, Peter Zijlstra wrote:
> On Wed, Aug 31, 2016 at 07:28:18AM +1000, Benjamin Herrenschmidt
> wrote:
> 
> > 
> > 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.

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.

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

#1474088

On 01/09/16 07:47, Benjamin Herrenschmidt wrote:
> On Wed, 2016-08-31 at 15:31 +0200, Peter Zijlstra wrote:
>> On Wed, Aug 31, 2016 at 07:28:18AM +1000, Benjamin Herrenschmidt
>> wrote:
>>
>>>
>>> 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.
> 
> 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.

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

#1474103

On Thu, Sep 01, 2016 at 07:47:10AM +1000, Benjamin Herrenschmidt wrote:

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

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

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

#1474428

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

On Thu, Sep 01, 2016 at 08:57:38AM +0200, Peter Zijlstra wrote:
> On Thu, Sep 01, 2016 at 07:47:10AM +1000, Benjamin Herrenschmidt wrote:
> 
> > > 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.
> 
> > 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.

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

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

#1474502

On Thu, Sep 01, 2016 at 10:17:57PM +0800, Boqun Feng wrote:
> 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 :-)

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

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

#1472886

On Tue, 2016-08-30 at 15:04 +0200, Oleg Nesterov wrote:
> 
> 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.

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

#1473086

On Wed, Aug 31, 2016 at 07:25:01AM +1000, Benjamin Herrenschmidt wrote:
> On Tue, 2016-08-30 at 15:04 +0200, Oleg Nesterov wrote:
> > 
> > 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.

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

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

#1473344

On Wed, 2016-08-31 at 09:20 +0200, Peter Zijlstra wrote:
> On Wed, Aug 31, 2016 at 07:25:01AM +1000, Benjamin Herrenschmidt wrote:
> > 
> > On Tue, 2016-08-30 at 15:04 +0200, Oleg Nesterov wrote:
> > > 
> > > 
> > > 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.

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

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

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

#1473019

On 30/08/16 22:19, Peter Zijlstra wrote:
> On Tue, Aug 30, 2016 at 06:49:37PM +1000, Balbir Singh 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
> 
> 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.

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?

> 
>> +++ b/kernel/sched/core.c
>> @@ -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.
> 

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

>> +	 *    [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.
> 	 */
> 
>> +	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.

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

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web