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

Groups > linux.kernel > #1697148 > unrolled thread

Re: [Question]: try to fix contention between expire_timers and try_to_del_timer_sync

Back to article view | Back to linux.kernel

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

Contents

  Re: [Question]: try to fix contention between expire_timers and  try_to_del_timer_sync Thomas Gleixner <tglx@linutronix.de> - 2017-07-26 16:20 +0200
    Re: [Question]: try to fix contention between expire_timers and  try_to_del_timer_sync qiaozhou <qiaozhou@asrmicro.com> - 2017-07-27 03:40 +0200
      Re: [Question]: try to fix contention between expire_timers and  try_to_del_timer_sync Thomas Gleixner <tglx@linutronix.de> - 2017-07-27 17:20 +0200
      Re: [Question]: try to fix contention between expire_timers and  try_to_del_timer_sync Will Deacon <will.deacon@arm.com> - 2017-07-27 17:20 +0200
      Re: [Question]: try to fix contention between expire_timers and  try_to_del_timer_sync Vikram Mulukutla <markivx@codeaurora.org> - 2017-07-28 03:20 +0200
        Re: [Question]: try to fix contention between expire_timers and  try_to_del_timer_sync Will Deacon <will.deacon@arm.com> - 2017-07-28 11:30 +0200
          Re: [Question]: try to fix contention between expire_timers and  try_to_del_timer_sync Vikram Mulukutla <markivx@codeaurora.org> - 2017-07-28 21:10 +0200
            Re: [Question]: try to fix contention between expire_timers and  try_to_del_timer_sync qiaozhou <qiaozhou@asrmicro.com> - 2017-07-31 13:30 +0200
        Re: [Question]: try to fix contention between expire_timers and  try_to_del_timer_sync Peter Zijlstra <peterz@infradead.org> - 2017-07-28 11:30 +0200
          Re: [Question]: try to fix contention between expire_timers and  try_to_del_timer_sync Vikram Mulukutla <markivx@codeaurora.org> - 2017-07-28 21:20 +0200

#1697148 — Re: [Question]: try to fix contention between expire_timers and try_to_del_timer_sync

On Wed, 26 Jul 2017, qiaozhou wrote:

Cc'ed ARM folks.

> I want to ask you for suggestions about how to fix one contention between
> expire_timers and try_to_del_timer_sync. Thanks in advance.
> The issue is a hard-lockup issue detected on our platform(arm64, one cluster
> with 4 a53, and the other with 4 a73). The sequence is as below:
> 1. core0 checks expired timers, and wakes up a process on a73, in step 1.3.
> 2. core4 starts to run the process and try to delete the timer in sync method,
> in step 2.1.
> 3. Before core0 can run to 1.4 and get the lock, core4 has already run from
> 2.1 to 2.6 in while loop. And in step 2.4, it fails since the timer is still
> the running timer.
> 
> core0(a53): core4(a73):
> run_timer_softirq
> __run_timers
>     spin_lock_irq(&base->lock)
>         expire_timers()
>             1.1: base->running_timer = timer;
>             1.2: spin_unlock_irq(&base->lock);
>             1.3: call_timer_fn(timer, fn, data);
> schedule()
>             1.4: spin_lock_irq(&base->lock);     del_timer_sync(&timer)
>             1.5: back to 1.1 in while loop
> 2.1: try_to_del_timer_sync()
>         2.2: get_timer_base()
>         2.3: spin_lock_irqsave(&base->lock, flags);
>           2.4: check "base->running_timer != timer"
>         2.5: spin_unlock_irqrestore(&base->lock, flags);
>    2.6:cpu_relax(); (back to 2.1 in while loop)

This is horribly formatted.

> Core0 runs @832MHz, and core4 runs @1.8GHz. A73 is also much more powerful in
> design than a53. So the actual running is that a73 keeps looping in spin_lock
> -> check running_timer -> spin_unlock -> spin_lock ->...., while a53 can't
> even succeed to complete one store exclusive instruction, before it can enter
> WFE to wait for lock release. It just keeps looping in +30 and+3c in below
> asm, due to stxr fails.
> 
> So it deadloop, a53 can't jump out ldaxr/stxr loop, while a73 can't pass the
> running_timer check. Finally the hard-lockup is triggered.(BTW, the issue
> needs a long time to occur.)
> 
> <_raw_spin_lock_irq+0x2c>:   prfm    pstl1strm, [x19]
> /<_raw_spin_lock_irq+0x30>:   ldaxr   w0, [x19]//
> //<_raw_spin_lock_irq+0x34>:   add     w1, w0, #0x10, lsl #12//
> //<_raw_spin_lock_irq+0x38>:   stxr    w2, w1, [x19]//
> //<_raw_spin_lock_irq+0x3c>:   cbnz    w2, 0xffffff80089f52e0
> <_raw_spin_lock_irq+0x30>/
> <_raw_spin_lock_irq+0x40>:   eor     w1, w0, w0, ror #16
> <_raw_spin_lock_irq+0x44>:   cbz     w1, 0xffffff80089f530c
> <_raw_spin_lock_irq+0x5c>
> <_raw_spin_lock_irq+0x48>:   sevl
> <_raw_spin_lock_irq+0x4c>:   wfe
> <_raw_spin_lock_irq+0x50>:   ldaxrh  w2, [x19]
> <_raw_spin_lock_irq+0x54>:   eor     w1, w2, w0, lsr #16
> <_raw_spin_lock_irq+0x58>:   cbnz    w1, 0xffffff80089f52fc
> <_raw_spin_lock_irq+0x4c>
> 
> The loop on a53 only has 4 instructions, and loop on a73 has ~100
> instructions. Still a53 has no chance to store exclusive successfully. It may
> be related with ldaxr/stxr cost, core frequency, core number etc.
> 
> I have no idea of fixing it in spinlock/unlock implement, so I try to fix it
> in timer driver. I prepared a raw patch, not sure it's the correct direction
> to solve this issue. Could you help to give some suggestions? Thanks.
> 
> From fb8fbfeb8f9f92fdadd9920ce234fd433bc883e1 Mon Sep 17 00:00:00 2001
> From: Qiao Zhou <qiaozhou@asrmicro.com>
> Date: Wed, 26 Jul 2017 20:30:33 +0800
> Subject: [PATCH] RFC: timers: try to fix contention between expire_timers and
>  del_timer_sync
> 
> try to fix contention between expire_timers and del_timer_sync by
> adding TIMER_WOKEN status, which means that the timer has already
> woken up corresponding process.

Timers do a lot more things than waking up a process.

Just because this happens in a particular case for you where a wakeup is
involved this does not mean, that this is generally true.

And that whole flag business is completely broken. There is a comment in
call_timer_fn() which says:

        /*
         * It is permissible to free the timer from inside the
         * function that is called from it ....

So you _CANNOT_ touch timer after the function returned. It might be gone
already.

For that particular timer case we can clear base->running_timer w/o the
lock held (see patch below), but this kind of

     lock -> test -> unlock -> retry

loops are all over the place in the kernel, so this is going to hurt you
sooner than later in some other place.

Thanks,

	tglx

8<------------

--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1301,10 +1301,12 @@ static void expire_timers(struct timer_b
 		if (timer->flags & TIMER_IRQSAFE) {
 			raw_spin_unlock(&base->lock);
 			call_timer_fn(timer, fn, data);
+			base->running_timer = NULL;
 			raw_spin_lock(&base->lock);
 		} else {
 			raw_spin_unlock_irq(&base->lock);
 			call_timer_fn(timer, fn, data);
+			base->running_timer = NULL;
 			raw_spin_lock_irq(&base->lock);
 		}
 	}

[toc] | [next] | [standalone]

#1697651

On 2017年07月26日 22:16, Thomas Gleixner wrote:
> On Wed, 26 Jul 2017, qiaozhou wrote:
>
> Cc'ed ARM folks.
>
>> I want to ask you for suggestions about how to fix one contention between
>> expire_timers and try_to_del_timer_sync. Thanks in advance.
>> The issue is a hard-lockup issue detected on our platform(arm64, one cluster
>> with 4 a53, and the other with 4 a73). The sequence is as below:
>> 1. core0 checks expired timers, and wakes up a process on a73, in step 1.3.
>> 2. core4 starts to run the process and try to delete the timer in sync method,
>> in step 2.1.
>> 3. Before core0 can run to 1.4 and get the lock, core4 has already run from
>> 2.1 to 2.6 in while loop. And in step 2.4, it fails since the timer is still
>> the running timer.
>>
>> core0(a53): core4(a73):
>> run_timer_softirq
>> __run_timers
>>      spin_lock_irq(&base->lock)
>>          expire_timers()
>>              1.1: base->running_timer = timer;
>>              1.2: spin_unlock_irq(&base->lock);
>>              1.3: call_timer_fn(timer, fn, data);
>> schedule()
>>              1.4: spin_lock_irq(&base->lock);     del_timer_sync(&timer)
>>              1.5: back to 1.1 in while loop
>> 2.1: try_to_del_timer_sync()
>>          2.2: get_timer_base()
>>          2.3: spin_lock_irqsave(&base->lock, flags);
>>            2.4: check "base->running_timer != timer"
>>          2.5: spin_unlock_irqrestore(&base->lock, flags);
>>     2.6:cpu_relax(); (back to 2.1 in while loop)
> This is horribly formatted.
Sorry for the format. Updated the calling sequence on two cores.

core0(a53): core4(a73):
run_timer_softirq
__run_timers
     spin_lock_irq(&base->lock)
         expire_timers()
             1.1: base->running_timer = timer;
             1.2: spin_unlock_irq(&base->lock);
             1.3: call_timer_fn(timer, fn, data);
             1.4: spin_lock_irq(&base->lock);
             1.5: back to 1.1 in while loop

core4(a73):
schedule()
   del_timer_sync(&timer)
      2.1: try_to_del_timer_sync()
         2.2: get_timer_base()
         2.3: spin_lock_irqsave(&base->lock, flags);
         2.4: check "base->running_timer != timer"
         2.5: spin_unlock_irqrestore(&base->lock, flags);
      2.6:cpu_relax(); (back to 2.1 in while loop)

>
>> Core0 runs @832MHz, and core4 runs @1.8GHz. A73 is also much more powerful in
>> design than a53. So the actual running is that a73 keeps looping in spin_lock
>> -> check running_timer -> spin_unlock -> spin_lock ->...., while a53 can't
>> even succeed to complete one store exclusive instruction, before it can enter
>> WFE to wait for lock release. It just keeps looping in +30 and+3c in below
>> asm, due to stxr fails.
>>
>> So it deadloop, a53 can't jump out ldaxr/stxr loop, while a73 can't pass the
>> running_timer check. Finally the hard-lockup is triggered.(BTW, the issue
>> needs a long time to occur.)
>>
>> <_raw_spin_lock_irq+0x2c>:   prfm    pstl1strm, [x19]
>> /<_raw_spin_lock_irq+0x30>:   ldaxr   w0, [x19]//
>> //<_raw_spin_lock_irq+0x34>:   add     w1, w0, #0x10, lsl #12//
>> //<_raw_spin_lock_irq+0x38>:   stxr    w2, w1, [x19]//
>> //<_raw_spin_lock_irq+0x3c>:   cbnz    w2, 0xffffff80089f52e0
>> <_raw_spin_lock_irq+0x30>/
>> <_raw_spin_lock_irq+0x40>:   eor     w1, w0, w0, ror #16
>> <_raw_spin_lock_irq+0x44>:   cbz     w1, 0xffffff80089f530c
>> <_raw_spin_lock_irq+0x5c>
>> <_raw_spin_lock_irq+0x48>:   sevl
>> <_raw_spin_lock_irq+0x4c>:   wfe
>> <_raw_spin_lock_irq+0x50>:   ldaxrh  w2, [x19]
>> <_raw_spin_lock_irq+0x54>:   eor     w1, w2, w0, lsr #16
>> <_raw_spin_lock_irq+0x58>:   cbnz    w1, 0xffffff80089f52fc
>> <_raw_spin_lock_irq+0x4c>
>>
>> The loop on a53 only has 4 instructions, and loop on a73 has ~100
>> instructions. Still a53 has no chance to store exclusive successfully. It may
>> be related with ldaxr/stxr cost, core frequency, core number etc.
>>
>> I have no idea of fixing it in spinlock/unlock implement, so I try to fix it
>> in timer driver. I prepared a raw patch, not sure it's the correct direction
>> to solve this issue. Could you help to give some suggestions? Thanks.
>>
>>  From fb8fbfeb8f9f92fdadd9920ce234fd433bc883e1 Mon Sep 17 00:00:00 2001
>> From: Qiao Zhou <qiaozhou@asrmicro.com>
>> Date: Wed, 26 Jul 2017 20:30:33 +0800
>> Subject: [PATCH] RFC: timers: try to fix contention between expire_timers and
>>   del_timer_sync
>>
>> try to fix contention between expire_timers and del_timer_sync by
>> adding TIMER_WOKEN status, which means that the timer has already
>> woken up corresponding process.
> Timers do a lot more things than waking up a process.
>
> Just because this happens in a particular case for you where a wakeup is
> involved this does not mean, that this is generally true.
Yes, you're right. My intention is that as the timer function is 
executed, maybe we can do something.
>
> And that whole flag business is completely broken. There is a comment in
> call_timer_fn() which says:
>
>          /*
>           * It is permissible to free the timer from inside the
>           * function that is called from it ....
>
> So you _CANNOT_ touch timer after the function returned. It might be gone
> already.
You're right. Touching timer here has risk.
>
> For that particular timer case we can clear base->running_timer w/o the
> lock held (see patch below), but this kind of
>
>       lock -> test -> unlock -> retry
>
> loops are all over the place in the kernel, so this is going to hurt you
> sooner than later in some other place.
It's true. This is the way spinlock is used normally and widely in 
kernel. I'll also ask ARM experts whether we can do something to avoid 
or reduce the chance of such issue. ARMv8.1 has one single 
instruction(ldadda) to replace the ldaxr/stxr loop. Hope it can improve 
and reduce the chance.
>
> Thanks,
>
> 	tglx
>
> 8<------------
>
> --- a/kernel/time/timer.c
> +++ b/kernel/time/timer.c
> @@ -1301,10 +1301,12 @@ static void expire_timers(struct timer_b
>   		if (timer->flags & TIMER_IRQSAFE) {
>   			raw_spin_unlock(&base->lock);
>   			call_timer_fn(timer, fn, data);
> +			base->running_timer = NULL;
>   			raw_spin_lock(&base->lock);
>   		} else {
>   			raw_spin_unlock_irq(&base->lock);
>   			call_timer_fn(timer, fn, data);
> +			base->running_timer = NULL;
>   			raw_spin_lock_irq(&base->lock);
>   		}
>   	}
It should work for this particular issue and I'll test it. Previously I 
thought it was unsafe to touch base->running_timer without holding lock.

Thanks a lot for all the suggestions.

Best Regards
Qiao

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

#1698088

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

On Thu, 27 Jul 2017, Will Deacon wrote:
> On Thu, Jul 27, 2017 at 09:29:20AM +0800, qiaozhou wrote:
> > On 2017年07月26日 22:16, Thomas Gleixner wrote:
> > >--- a/kernel/time/timer.c
> > >+++ b/kernel/time/timer.c
> > >@@ -1301,10 +1301,12 @@ static void expire_timers(struct timer_b
> > >  		if (timer->flags & TIMER_IRQSAFE) {
> > >  			raw_spin_unlock(&base->lock);
> > >  			call_timer_fn(timer, fn, data);
> > >+			base->running_timer = NULL;
> > >  			raw_spin_lock(&base->lock);
> > >  		} else {
> > >  			raw_spin_unlock_irq(&base->lock);
> > >  			call_timer_fn(timer, fn, data);
> > >+			base->running_timer = NULL;
> > >  			raw_spin_lock_irq(&base->lock);
> > >  		}
> > >  	}
> > It should work for this particular issue and I'll test it. Previously I
> > thought it was unsafe to touch base->running_timer without holding lock.
> 
> I think it works out in practice because base->lock and base->running_timer
> share a cacheline, so end up being ordered correctly. We should probably be
> using READ_ONCE/WRITE_ONCE for accessing the running_time field though.
> 
> One thing I don't get though, is why try_to_del_timer_sync needs to check
> base->running_timer at all. Given that it holds the base->lock, can't it
> be the person that sets it to NULL?

No. The timer callback code does:

    base->running_timer = timer;
    spin_unlock(base->lock);
    fn(timer);
    spin_lock(base->lock);
    base->running_timer = NULL;

So for del_timer_sync() the only way to figure out whether the timer
callback is running is to check base->running_timer. We cannot store state
in the timer itself because we cannot clear that state when the callback
return as the timer might have been freed in the callback. Yes, that's
nasty, but reality.

Thanks,

	tglx

    

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

#1698091

On Thu, Jul 27, 2017 at 09:29:20AM +0800, qiaozhou wrote:
> On 2017年07月26日 22:16, Thomas Gleixner wrote:
> >--- a/kernel/time/timer.c
> >+++ b/kernel/time/timer.c
> >@@ -1301,10 +1301,12 @@ static void expire_timers(struct timer_b
> >  		if (timer->flags & TIMER_IRQSAFE) {
> >  			raw_spin_unlock(&base->lock);
> >  			call_timer_fn(timer, fn, data);
> >+			base->running_timer = NULL;
> >  			raw_spin_lock(&base->lock);
> >  		} else {
> >  			raw_spin_unlock_irq(&base->lock);
> >  			call_timer_fn(timer, fn, data);
> >+			base->running_timer = NULL;
> >  			raw_spin_lock_irq(&base->lock);
> >  		}
> >  	}
> It should work for this particular issue and I'll test it. Previously I
> thought it was unsafe to touch base->running_timer without holding lock.

I think it works out in practice because base->lock and base->running_timer
share a cacheline, so end up being ordered correctly. We should probably be
using READ_ONCE/WRITE_ONCE for accessing the running_time field though.

One thing I don't get though, is why try_to_del_timer_sync needs to check
base->running_timer at all. Given that it holds the base->lock, can't it
be the person that sets it to NULL?

Will

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

#1698401

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

cc: Sudeep Holla

On 2017-07-26 18:29, qiaozhou wrote:
> On 2017年07月26日 22:16, Thomas Gleixner wrote:
>> On Wed, 26 Jul 2017, qiaozhou wrote:
>> 
>> Cc'ed ARM folks.
>> 

<snip>

>> 
>> For that particular timer case we can clear base->running_timer w/o 
>> the
>> lock held (see patch below), but this kind of
>> 
>>       lock -> test -> unlock -> retry
>> 
>> loops are all over the place in the kernel, so this is going to hurt 
>> you
>> sooner than later in some other place.
> It's true. This is the way spinlock is used normally and widely in
> kernel. I'll also ask ARM experts whether we can do something to avoid
> or reduce the chance of such issue. ARMv8.1 has one single
> instruction(ldadda) to replace the ldaxr/stxr loop. Hope it can
> improve and reduce the chance.

I think we should have this discussion now - I brought this up earlier 
[1]
and I promised a test case that I completely forgot about - but here it
is (attached). Essentially a Big CPU in an acquire-check-release loop
will have an unfair advantage over a little CPU concurrently attempting
to acquire the same lock, in spite of the ticket implementation. If the 
Big
CPU needs the little CPU to make forward progress : livelock.

We've run into the same loop construct in other spots in the kernel and
the reason that a real  symptom is so rare is that the retry-loop on the 
'Big'
CPU needs to be interrupted just once by say an IRQ/FIQ and the 
live-lock
is broken. If the entire retry loop is within an interrupt-disabled 
critical
section then the odds of live-locking are much higher.

An example of the problem on a previous kernel is here [2]. Changes to 
the
workqueue code since may have fixed this particular instance.

One solution was to use udelay(1) in such loops instead of cpu_relax(), 
but
that's not very 'relaxing'. I'm not sure if there's something we could 
do
within the ticket spin-lock implementation to deal with this.

Note that I ran my test on a 4.9 kernel so that didn't include any 
spinlock
implementation changes since then. The test schedules two threads, one 
on
a big CPU and one on a little CPU. The big CPU thread does the 
lock/unlock/retry
loop for a full 1 second with interrupts disabled, while the little CPU 
attempts
to acquire the same loop but enabling interrupts after every successful 
lock+unlock.
With unfairness, the little CPU may take upto 1 second (or several 
milliseconds at
the least) just to acquire the lock once. This varies depending on the 
IPC difference
and frequencies of the big and little ARM64 CPUs:

Big cpu frequency | Little cpu frequency | Max time taken by little to 
acquire lock
2GHz              | 1.5GHz               | 133 microseconds
2GHz              | 300MHz               | 734 milliseconds

Thanks,
Vikram

[1] - https://lkml.org/lkml/2016/11/17/934
[2] - https://goo.gl/uneFjt

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
a Linux Foundation Collaborative Project

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

#1698618

On Thu, Jul 27, 2017 at 06:10:34PM -0700, Vikram Mulukutla wrote:
> On 2017-07-26 18:29, qiaozhou wrote:
> >On 2017年07月26日 22:16, Thomas Gleixner wrote:
> >>On Wed, 26 Jul 2017, qiaozhou wrote:
> >>For that particular timer case we can clear base->running_timer w/o the
> >>lock held (see patch below), but this kind of
> >>
> >>      lock -> test -> unlock -> retry
> >>
> >>loops are all over the place in the kernel, so this is going to hurt you
> >>sooner than later in some other place.
> >It's true. This is the way spinlock is used normally and widely in
> >kernel. I'll also ask ARM experts whether we can do something to avoid
> >or reduce the chance of such issue. ARMv8.1 has one single
> >instruction(ldadda) to replace the ldaxr/stxr loop. Hope it can
> >improve and reduce the chance.
> 
> I think we should have this discussion now - I brought this up earlier [1]
> and I promised a test case that I completely forgot about - but here it
> is (attached). Essentially a Big CPU in an acquire-check-release loop
> will have an unfair advantage over a little CPU concurrently attempting
> to acquire the same lock, in spite of the ticket implementation. If the Big
> CPU needs the little CPU to make forward progress : livelock.
> 
> We've run into the same loop construct in other spots in the kernel and
> the reason that a real  symptom is so rare is that the retry-loop on the
> 'Big'
> CPU needs to be interrupted just once by say an IRQ/FIQ and the live-lock
> is broken. If the entire retry loop is within an interrupt-disabled critical
> section then the odds of live-locking are much higher.
> 
> An example of the problem on a previous kernel is here [2]. Changes to the
> workqueue code since may have fixed this particular instance.
> 
> One solution was to use udelay(1) in such loops instead of cpu_relax(), but
> that's not very 'relaxing'. I'm not sure if there's something we could do
> within the ticket spin-lock implementation to deal with this.

Does bodging cpu_relax to back-off to wfe after a while help? The event
stream will wake it up if nothing else does. Nasty patch below, but I'd be
interested to know whether or not it helps.

Will

--->8

diff --git a/arch/arm64/include/asm/processor.h b/arch/arm64/include/asm/processor.h
index 64c9e78f9882..1f5a29c8612e 100644
--- a/arch/arm64/include/asm/processor.h
+++ b/arch/arm64/include/asm/processor.h
@@ -149,9 +149,11 @@ extern void release_thread(struct task_struct *);
 
 unsigned long get_wchan(struct task_struct *p);
 
+void __cpu_relax(unsigned long pc);
+
 static inline void cpu_relax(void)
 {
-	asm volatile("yield" ::: "memory");
+	__cpu_relax(_THIS_IP_);
 }
 
 /* Thread switching */
diff --git a/arch/arm64/kernel/arm64ksyms.c b/arch/arm64/kernel/arm64ksyms.c
index 67368c7329c0..be8a698ea680 100644
--- a/arch/arm64/kernel/arm64ksyms.c
+++ b/arch/arm64/kernel/arm64ksyms.c
@@ -72,6 +72,8 @@ EXPORT_SYMBOL(_mcount);
 NOKPROBE_SYMBOL(_mcount);
 #endif
 
+EXPORT_SYMBOL(__cpu_relax);
+
 	/* arm-smccc */
 EXPORT_SYMBOL(__arm_smccc_smc);
 EXPORT_SYMBOL(__arm_smccc_hvc);
diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
index 659ae8094ed5..c394c3704b7f 100644
--- a/arch/arm64/kernel/process.c
+++ b/arch/arm64/kernel/process.c
@@ -403,6 +403,31 @@ unsigned long get_wchan(struct task_struct *p)
 	return ret;
 }
 
+static DEFINE_PER_CPU(u64, __cpu_relax_data);
+
+#define CPU_RELAX_WFE_THRESHOLD	10000
+void __cpu_relax(unsigned long pc)
+{
+	u64 new, old = raw_cpu_read(__cpu_relax_data);
+	u32 old_pc, new_pc;
+	bool wfe = false;
+
+	old_pc = (u32)old;
+	new = new_pc = (u32)pc;
+
+	if (old_pc == new_pc) {
+		if ((old >> 32) > CPU_RELAX_WFE_THRESHOLD) {
+			asm volatile("sevl; wfe; wfe\n" ::: "memory");
+			wfe = true;
+		} else {
+			new = old + (1UL << 32);
+		}
+	}
+
+	if (this_cpu_cmpxchg(__cpu_relax_data, old, new) == old && !wfe)
+		asm volatile("yield" ::: "memory");
+}
+
 unsigned long arch_align_stack(unsigned long sp)
 {
 	if (!(current->personality & ADDR_NO_RANDOMIZE) && randomize_va_space)

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

#1699034

On 2017-07-28 02:28, Will Deacon wrote:
> On Thu, Jul 27, 2017 at 06:10:34PM -0700, Vikram Mulukutla wrote:

<snip>

>> 
>> I think we should have this discussion now - I brought this up earlier 
>> [1]
>> and I promised a test case that I completely forgot about - but here 
>> it
>> is (attached). Essentially a Big CPU in an acquire-check-release loop
>> will have an unfair advantage over a little CPU concurrently 
>> attempting
>> to acquire the same lock, in spite of the ticket implementation. If 
>> the Big
>> CPU needs the little CPU to make forward progress : livelock.
>> 

<snip>

>> 
>> One solution was to use udelay(1) in such loops instead of 
>> cpu_relax(), but
>> that's not very 'relaxing'. I'm not sure if there's something we could 
>> do
>> within the ticket spin-lock implementation to deal with this.
> 
> Does bodging cpu_relax to back-off to wfe after a while help? The event
> stream will wake it up if nothing else does. Nasty patch below, but I'd 
> be
> interested to know whether or not it helps.
> 
> Will
> 
This does seem to help. Here's some data after 5 runs with and without 
the patch.

time = max time taken to acquire lock
counter = number of times lock acquired

cpu0: little cpu @ 300MHz, cpu4: Big cpu @2.0GHz
Without the cpu_relax() bodging patch:
=====================================================
cpu0 time | cpu0 counter | cpu4 time | cpu4 counter |
==========|==============|===========|==============|
   117893us|       2349144|        2us|       6748236|
   571260us|       2125651|        2us|       7643264|
    19780us|       2392770|        2us|       5987203|
    19948us|       2395413|        2us|       5977286|
    19822us|       2429619|        2us|       5768252|
    19888us|       2444940|        2us|       5675657|
=====================================================

cpu0: little cpu @ 300MHz, cpu4: Big cpu @2.0GHz
With the cpu_relax() bodging patch:
=====================================================
cpu0 time | cpu0 counter | cpu4 time | cpu4 counter |
==========|==============|===========|==============|
        3us|       2737438|        2us|       6907147|
        2us|       2742478|        2us|       6902241|
      132us|       2745636|        2us|       6876485|
        3us|       2744554|        2us|       6898048|
        3us|       2741391|        2us|       6882901|
=====================================================

The patch also seems to have helped with fairness in general
allowing more work to be done if the CPU frequencies are more
closely matched (I don't know if this translates to real world
performance - probably not). The counter values are higher
with the patch.

time = max time taken to acquire lock
counter = number of times lock acquired

cpu0: little cpu @ 1.5GHz, cpu4: Big cpu @2.0GHz
Without the cpu_relax() bodging patch:
=====================================================
cpu0 time | cpu0 counter | cpu4 time | cpu4 counter |
==========|==============|===========|==============|
        2us|       5240654|        1us|       5339009|
        2us|       5287797|       97us|       5327073|
        2us|       5237634|        1us|       5334694|
        2us|       5236676|       88us|       5333582|
       84us|       5285880|       84us|       5329489|
=====================================================

cpu0: little cpu @ 1.5GHz, cpu4: Big cpu @2.0GHz
With the cpu_relax() bodging patch:
=====================================================
cpu0 time | cpu0 counter | cpu4 time | cpu4 counter |
==========|==============|===========|==============|
      140us|      10449121|        1us|      11154596|
        1us|      10757081|        1us|      11479395|
       83us|      10237109|        1us|      10902557|
        2us|       9871101|        1us|      10514313|
        2us|       9758763|        1us|      10391849|
=====================================================


Thanks,
Vikram

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
a Linux Foundation Collaborative Project

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

#1699946

On 2017年07月29日 03:09, Vikram Mulukutla wrote:
> On 2017-07-28 02:28, Will Deacon wrote:
>> On Thu, Jul 27, 2017 at 06:10:34PM -0700, Vikram Mulukutla wrote:
> 
> <snip>
> 
>>>
>>> I think we should have this discussion now - I brought this up 
>>> earlier [1]
>>> and I promised a test case that I completely forgot about - but here it
>>> is (attached). Essentially a Big CPU in an acquire-check-release loop
>>> will have an unfair advantage over a little CPU concurrently attempting
>>> to acquire the same lock, in spite of the ticket implementation. If 
>>> the Big
>>> CPU needs the little CPU to make forward progress : livelock.
>>>
> 
> <snip>
> 
>>>
>>> One solution was to use udelay(1) in such loops instead of 
>>> cpu_relax(), but
>>> that's not very 'relaxing'. I'm not sure if there's something we 
>>> could do
>>> within the ticket spin-lock implementation to deal with this.
>>
>> Does bodging cpu_relax to back-off to wfe after a while help? The event
>> stream will wake it up if nothing else does. Nasty patch below, but 
>> I'd be
>> interested to know whether or not it helps.
>>
>> Will
>>
The patch also helps a lot on my platform. (Though it does cause 
deadlock(related with udelay) in uart driver in early boot, and not sure 
it's uart driver issue. Just workaround it firstly)

Platform: 4 a53(832MHz) + 4 a73(1.8GHz)
Test condition #1:
     a. core2: a53, while loop (spinlock, spin_unlock)
     b. core7: a73, while loop (spinlock, spin_unlock, cpu_relax)

Test result: recording the lock acquire times(a53, a73), max lock 
acquired time(a53), in 20 seconds

Without cpu_relax bodging patch:
===============================================================
|a53 locked times | a73 locked times | a53 max locked time(us)|
==================|==================|========================|
                182|          38371616|               1,951,954|
                202|          38427652|               2,261,319|
                210|          38477427|              15,309,597|
                207|          38494479|               6,656,453|
                220|          38422283|               2,064,155|
===============================================================

With cpu_relax bodging patch:
===============================================================
|a53 locked times | a73 locked times | a53 max locked time(us)|
==================|==================|========================|
            1849898|          37799379|                 131,255|
            1574172|          38557653|                  38,410|
            1924777|          37831725|                  42,999|
            1477665|          38723741|                  52,087|
            1865793|          38007741|                 783,965|
===============================================================

Also add some workload to the whole system to check the result.
Test condition #2: based on #1
     c. core6: a73, 1.8GHz, run "while(1);" loop

With cpu_relax bodging patch:
===============================================================
|a53 locked times | a73 locked times | a53 max locked time(us)|
==================|==================|========================|
                 20|          42563981|               2,317,070|
                 10|          42652793|               4,210,944|
                  9|          42651075|               5,691,834|
                 28|          42652591|               4,539,555|
                 10|          42652801|               5,850,639|
===============================================================

Also hotplug out other cores.
Test condition #2: based on #1
     d. hotplug out core1/3/4/5/6, keep core0 for scheduling

With cpu_relax bodging patch:
===============================================================
|a53 locked times | a73 locked times | a53 max locked time(us)|
==================|==================|========================|
                447|          42652450|                 309,549|
                515|          42650382|                 337,661|
                415|          42646669|                 628,525|
                431|          42651137|                 365,862|
                464|          42648916|                 379,934|
===============================================================

The last two tests are the actual cases where the hard-lockup is 
triggered on my platform. So I gathered some data, and it shows that a53 
needs much longer time to acquire the lock.

All tests are done in android, black screen with USB cable attached. The 
data is not so pretty as Vikram's. It might be related with cpu 
topology, core numbers, CCI frequency etc. (I'll do another test with 
both a53 and a73 running at 1.2GHz, to check whether it's the core 
frequency which leads to the major difference.)

> This does seem to help. Here's some data after 5 runs with and without 
> the patch.
> 
> time = max time taken to acquire lock
> counter = number of times lock acquired
> 
> cpu0: little cpu @ 300MHz, cpu4: Big cpu @2.0GHz
> Without the cpu_relax() bodging patch:
> =====================================================
> cpu0 time | cpu0 counter | cpu4 time | cpu4 counter |
> ==========|==============|===========|==============|
>    117893us|       2349144|        2us|       6748236|
>    571260us|       2125651|        2us|       7643264|
>     19780us|       2392770|        2us|       5987203|
>     19948us|       2395413|        2us|       5977286|
>     19822us|       2429619|        2us|       5768252|
>     19888us|       2444940|        2us|       5675657|
> =====================================================
> 
> cpu0: little cpu @ 300MHz, cpu4: Big cpu @2.0GHz
> With the cpu_relax() bodging patch:
> =====================================================
> cpu0 time | cpu0 counter | cpu4 time | cpu4 counter |
> ==========|==============|===========|==============|
>         3us|       2737438|        2us|       6907147|
>         2us|       2742478|        2us|       6902241|
>       132us|       2745636|        2us|       6876485|
>         3us|       2744554|        2us|       6898048|
>         3us|       2741391|        2us|       6882901|
> ==================================================== >
> The patch also seems to have helped with fairness in general
> allowing more work to be done if the CPU frequencies are more
> closely matched (I don't know if this translates to real world
> performance - probably not). The counter values are higher
> with the patch.
> 
> time = max time taken to acquire lock
> counter = number of times lock acquired
> 
> cpu0: little cpu @ 1.5GHz, cpu4: Big cpu @2.0GHz
> Without the cpu_relax() bodging patch:
> =====================================================
> cpu0 time | cpu0 counter | cpu4 time | cpu4 counter |
> ==========|==============|===========|==============|
>         2us|       5240654|        1us|       5339009|
>         2us|       5287797|       97us|       5327073|
>         2us|       5237634|        1us|       5334694|
>         2us|       5236676|       88us|       5333582|
>        84us|       5285880|       84us|       5329489|
> =====================================================
> 
> cpu0: little cpu @ 1.5GHz, cpu4: Big cpu @2.0GHz
> With the cpu_relax() bodging patch:
> =====================================================
> cpu0 time | cpu0 counter | cpu4 time | cpu4 counter |
> ==========|==============|===========|==============|
>       140us|      10449121|        1us|      11154596|
>         1us|      10757081|        1us|      11479395|
>        83us|      10237109|        1us|      10902557|
>         2us|       9871101|        1us|      10514313|
>         2us|       9758763|        1us|      10391849|
> =====================================================
> 
> 
> Thanks,
> Vikram
> 

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

#1698621

On Thu, Jul 27, 2017 at 06:10:34PM -0700, Vikram Mulukutla wrote:

> I think we should have this discussion now - I brought this up earlier [1]
> and I promised a test case that I completely forgot about - but here it
> is (attached). Essentially a Big CPU in an acquire-check-release loop
> will have an unfair advantage over a little CPU concurrently attempting
> to acquire the same lock, in spite of the ticket implementation. If the Big
> CPU needs the little CPU to make forward progress : livelock.

This needs to be fixed in hardware. There really isn't anything the
software can sanely do about it.

It also doesn't have anything to do with the spinlock implementation.
Ticket or not, its a fundamental problem of LL/SC. Any situation where
we use atomics for fwd progress guarantees this can happen.

The little core (or really any core) should hold on to the locked
cacheline for a while and not insta relinquish it. Giving it a chance to
reach the SC.

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

#1699035

On 2017-07-28 02:28, Peter Zijlstra wrote:
> On Thu, Jul 27, 2017 at 06:10:34PM -0700, Vikram Mulukutla wrote:
> 
>> I think we should have this discussion now - I brought this up earlier 
>> [1]
>> and I promised a test case that I completely forgot about - but here 
>> it
>> is (attached). Essentially a Big CPU in an acquire-check-release loop
>> will have an unfair advantage over a little CPU concurrently 
>> attempting
>> to acquire the same lock, in spite of the ticket implementation. If 
>> the Big
>> CPU needs the little CPU to make forward progress : livelock.
> 
> This needs to be fixed in hardware. There really isn't anything the
> software can sanely do about it.
> 
> It also doesn't have anything to do with the spinlock implementation.
> Ticket or not, its a fundamental problem of LL/SC. Any situation where
> we use atomics for fwd progress guarantees this can happen.
> 

Agreed, it seems like trying to build a fair SW protocol over unfair HW.
But if we can minimally change such loop constructs to address this (all
instances I've seen so far use cpu_relax) it would save a lot of hours
spent debugging these problems. Lot of b.L devices out there :-)

It's also possible that such a workaround may help contention 
performance
since the big CPU may have to wait for say a tick before breaking out of
that loop (the non-livelock scenario where the entire loop isn't in a
critical section).

> The little core (or really any core) should hold on to the locked
> cacheline for a while and not insta relinquish it. Giving it a chance 
> to
> reach the SC.

Thanks,
Vikram

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
a Linux Foundation Collaborative Project

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web