[RT PATCH 0/3] hrtimer: RT fixes for hrtimer_grab_expiry_lock()

[RT PATCH 0/3] hrtimer: RT fixes for hrtimer_grab_expiry_lock()

[Julien Grall]

Hi all,

This small series contains a few fixes for the hrtimer code in RT linux
(v5.2.9-rt3-rebase).

The patch #2 contains a error I managed to reproduce. The other two are
were found while looking at the code.

Cheers,

Julien Grall (3):
  hrtimer: Use READ_ONCE to access timer->base in
    hrimer_grab_expiry_lock()
  hrtimer: Don't grab the expiry lock for non-soft hrtimer
  hrtimer: Prevent using uninitialized spin_lock in
    hrtimer_grab_expiry_lock()

 kernel/time/hrtimer.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

-- 
2.11.0

[RT PATCH 1/3] hrtimer: Use READ_ONCE to access timer->base in hrimer_grab_expiry_lock()

[Julien Grall]

The update to timer->base is protected by the base->cpu_base->lock().
However, hrtimer_grab_expirty_lock() does not access it with the lock.

So it would theorically be possible to have timer->base changed under
our feet. We need to prevent the compiler to refetch timer->base so the
check and the access is performed on the same base.

Other access of timer->base are either done with a lock or protected
with READ_ONCE(). So use READ_ONCE() in hrtimer_grab_expirty_lock().

Signed-off-by: Julien Grall <julien.grall@arm.com>

---

This is rather theoritical so far as I don't have a reproducer for this.
---
 kernel/time/hrtimer.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
index 7d7db8802131..b869e816e96a 100644
--- a/kernel/time/hrtimer.c
+++ b/kernel/time/hrtimer.c
@@ -932,7 +932,7 @@ EXPORT_SYMBOL_GPL(hrtimer_forward);
 
 void hrtimer_grab_expiry_lock(const struct hrtimer *timer)
 {
-	struct hrtimer_clock_base *base = timer->base;
+	struct hrtimer_clock_base *base = READ_ONCE(timer->base);
 
 	if (base && base->cpu_base) {
 		spin_lock(&base->cpu_base->softirq_expiry_lock);
-- 
2.11.0

Re: [RT PATCH 1/3] hrtimer: Use READ_ONCE to access timer->base in hrimer_grab_expiry_lock()

[Sebastian Andrzej Siewior]

On 2019-08-21 10:24:07 [+0100], Julien Grall wrote:
> The update to timer->base is protected by the base->cpu_base->lock().
> However, hrtimer_grab_expirty_lock() does not access it with the lock.
> 
> So it would theorically be possible to have timer->base changed under
> our feet. We need to prevent the compiler to refetch timer->base so the
> check and the access is performed on the same base.

It is not a problem if the timer's bases changes. We get here because we
want to help the timer to complete its callback.
The base can only change if the timer gets re-armed on another CPU which
means is completed callback. In every case we can cancel the timer on
the next iteration.

Sebastian

Re: [RT PATCH 1/3] hrtimer: Use READ_ONCE to access timer->base in hrimer_grab_expiry_lock()

[Thomas Gleixner]

On Wed, 21 Aug 2019, Sebastian Andrzej Siewior wrote:

> On 2019-08-21 10:24:07 [+0100], Julien Grall wrote:
> > The update to timer->base is protected by the base->cpu_base->lock().
> > However, hrtimer_grab_expirty_lock() does not access it with the lock.
> > 
> > So it would theorically be possible to have timer->base changed under
> > our feet. We need to prevent the compiler to refetch timer->base so the
> > check and the access is performed on the same base.
> 
> It is not a problem if the timer's bases changes. We get here because we
> want to help the timer to complete its callback.
> The base can only change if the timer gets re-armed on another CPU which
> means is completed callback. In every case we can cancel the timer on
> the next iteration.

It _IS_ a problem when the base changes and the compiler reloads

   CPU0	  	       	   	CPU1
   base = timer->base;

   lock(base->....);
				switch base

   reload
	base = timer->base;

   unlock(base->....);

See?

   

Re: [RT PATCH 1/3] hrtimer: Use READ_ONCE to access timer->base in hrimer_grab_expiry_lock()

[Sebastian Andrzej Siewior]

On 2019-08-21 15:50:33 [+0200], Thomas Gleixner wrote:
> On Wed, 21 Aug 2019, Sebastian Andrzej Siewior wrote:
> 
> > On 2019-08-21 10:24:07 [+0100], Julien Grall wrote:
> > > The update to timer->base is protected by the base->cpu_base->lock().
> > > However, hrtimer_grab_expirty_lock() does not access it with the lock.
> > > 
> > > So it would theorically be possible to have timer->base changed under
> > > our feet. We need to prevent the compiler to refetch timer->base so the
> > > check and the access is performed on the same base.
> > 
> > It is not a problem if the timer's bases changes. We get here because we
> > want to help the timer to complete its callback.
> > The base can only change if the timer gets re-armed on another CPU which
> > means is completed callback. In every case we can cancel the timer on
> > the next iteration.
> 
> It _IS_ a problem when the base changes and the compiler reloads
> 
>    CPU0	  	       	   	CPU1
>    base = timer->base;
> 
>    lock(base->....);
> 				switch base
> 
>    reload
> 	base = timer->base;
> 
>    unlock(base->....);
> 
> See?
so read_once() it is then.

Sebastian

Re: [RT PATCH 1/3] hrtimer: Use READ_ONCE to access timer->base in hrimer_grab_expiry_lock()

[Eric Dumazet]

On 8/21/19 6:50 AM, Thomas Gleixner wrote:
> On Wed, 21 Aug 2019, Sebastian Andrzej Siewior wrote:
> 
>> On 2019-08-21 10:24:07 [+0100], Julien Grall wrote:
>>> The update to timer->base is protected by the base->cpu_base->lock().
>>> However, hrtimer_grab_expirty_lock() does not access it with the lock.
>>>
>>> So it would theorically be possible to have timer->base changed under
>>> our feet. We need to prevent the compiler to refetch timer->base so the
>>> check and the access is performed on the same base.
>>
>> It is not a problem if the timer's bases changes. We get here because we
>> want to help the timer to complete its callback.
>> The base can only change if the timer gets re-armed on another CPU which
>> means is completed callback. In every case we can cancel the timer on
>> the next iteration.
> 
> It _IS_ a problem when the base changes and the compiler reloads
> 
>    CPU0	  	       	   	CPU1
>    base = timer->base;
> 
>    lock(base->....);
> 				switch base
> 
>    reload
> 	base = timer->base;
> 
>    unlock(base->....);
> 

It seems we could hit a similar problem in lock_hrtimer_base()

 base = timer->base;

 if (likely(base != &migration_base)) {

     <reload base : could point to &migration_base>

     raw_spin_lock_irqsave(&base->cpu_base->lock, *flags);

Probably not a big deal, since migration_base-cpu_base->lock can be locked just fine,
(without lockdep complaining that the lock has not been initialized since we use raw_ variant),
but this could cause unnecessary false sharing.


diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
index 0d4dc241c0fb498036c91a571e65cb00f5d19ba6..fa881c03e0a1a351186a8d8f798dd7471067a951 100644
--- a/kernel/time/hrtimer.c
+++ b/kernel/time/hrtimer.c
@@ -164,7 +164,7 @@ struct hrtimer_clock_base *lock_hrtimer_base(const struct hrtimer *timer,
 	struct hrtimer_clock_base *base;
 
 	for (;;) {
-		base = timer->base;
+		base = READ_ONCE(timer->base);
 		if (likely(base != &migration_base)) {
 			raw_spin_lock_irqsave(&base->cpu_base->lock, *flags);
 			if (likely(base == timer->base))

[RT PATCH 2/3] hrtimer: Don't grab the expiry lock for non-soft hrtimer

[Julien Grall]

There are no guarantee the hrtimer_cancel() will be called on the same
CPU as the non-soft hrtimer is running on so the following scenario
can happen.

CPU0                                         |  CPU1
                                             |
                                             | hrtimer_interrupt()
                                             |   raw_spin_lock_irqsave(&cpu_save->lock)
hrtimer_cancel()                             |      __run_hrtimer_run_queues()
  hrtimer_try_to_cancel()                    |      __run_hrtimer()
    lock_hrtimer_base()                      |        base->running = timer;
                                             |        raw_spin_unlock_irqrestore(&cpu_save->lock)
      raw_spin_lock_irqsave(cpu_base->lock)  |        fn(timer);
    hrtimer_callback_running()               |

hrtimer_callback_running() will be returning true as the callback is
running somewhere else. This means hrtimer_try_to_cancel() would return -1.
Therefore hrtimer_grab_expiry_lock() would be called.

non-soft hrtimer may be used when the timer needs to be manipulated from
a non-preemptible context. This is for instance the case of KVM Arm
timers. The following splat can be seen in the log:

[  157.449545] 000: BUG: sleeping function called from invalid context at kernel/locking/rtmutex.c:968
[  157.449569] 000: in_atomic(): 1, irqs_disabled(): 0, pid: 990, name: kvm-vcpu-1
[  157.449579] 000: 2 locks held by kvm-vcpu-1/990:
[  157.449592] 000:  #0: 00000000c2fc8217 (&vcpu->mutex){+.+.}, at: kvm_vcpu_ioctl+0x70/0xae0
[  157.449638] 000:  #1: 0000000096863801 (&cpu_base->softirq_expiry_lock){+.+.}, at: hrtimer_grab_expiry_lock+0x24/0x40
[  157.449677] 000: Preemption disabled at:
[  157.449679] 000: [<ffff0000111a4538>] schedule+0x30/0xd8
[  157.449702] 000: CPU: 0 PID: 990 Comm: kvm-vcpu-1 Tainted: G        W 5.2.0-rt1-00001-gd368139e892f #104
[  157.449712] 000: Hardware name: ARM LTD ARM Juno Development Platform/ARM Juno Development Platform, BIOS EDK II Jan 23 2017
[  157.449718] 000: Call trace:
[  157.449722] 000:  dump_backtrace+0x0/0x130
[  157.449730] 000:  show_stack+0x14/0x20
[  157.449738] 000:  dump_stack+0xbc/0x104
[  157.449747] 000:  ___might_sleep+0x198/0x238
[  157.449756] 000:  rt_spin_lock+0x5c/0x70
[  157.449765] 000:  hrtimer_grab_expiry_lock+0x24/0x40
[  157.449773] 000:  hrtimer_cancel+0x1c/0x38
[  157.449780] 000:  kvm_timer_vcpu_load+0x78/0x3e0

An hrtimer is always either running in softirq or not. This cannot be
changed after it is instantiated. So we can rely on timer->is_soft
for checking whether the lock can be grabbed.

Signed-off-by: Julien Grall <julien.grall@arm.com>
---
 kernel/time/hrtimer.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
index b869e816e96a..119414a2f59c 100644
--- a/kernel/time/hrtimer.c
+++ b/kernel/time/hrtimer.c
@@ -934,7 +934,7 @@ void hrtimer_grab_expiry_lock(const struct hrtimer *timer)
 {
 	struct hrtimer_clock_base *base = READ_ONCE(timer->base);
 
-	if (base && base->cpu_base) {
+	if (timer->is_soft && base && base->cpu_base) {
 		spin_lock(&base->cpu_base->softirq_expiry_lock);
 		spin_unlock(&base->cpu_base->softirq_expiry_lock);
 	}
-- 
2.11.0

Re: [RT PATCH 2/3] hrtimer: Don't grab the expiry lock for non-soft hrtimer

[Sebastian Andrzej Siewior]

On 2019-08-21 10:24:08 [+0100], Julien Grall wrote:
> diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
> index b869e816e96a..119414a2f59c 100644
> --- a/kernel/time/hrtimer.c
> +++ b/kernel/time/hrtimer.c
> @@ -934,7 +934,7 @@ void hrtimer_grab_expiry_lock(const struct hrtimer *timer)
>  {
>  	struct hrtimer_clock_base *base = READ_ONCE(timer->base);
>  
> -	if (base && base->cpu_base) {
> +	if (timer->is_soft && base && base->cpu_base) {
>  		spin_lock(&base->cpu_base->softirq_expiry_lock);
>  		spin_unlock(&base->cpu_base->softirq_expiry_lock);
>  	}

right, much simpler.

Sebastian

[RT PATCH 3/3] hrtimer: Prevent using uninitialized spin_lock in hrtimer_grab_expiry_lock()

[Julien Grall]

migration_base is used as a placeholder when an hrtimer is switching
between base (see switch_hrtimer_timer_base). It is possible
theoritically possible to have timer->base equal to migration_base.

Even if it is a placeholder, it would pass all the current check in
hrtimer_grab_expiry_lock() leading to use softirq_expiry_lock
uninitialized.

This is can be prevented by checking whether the base is equal to
the placeholder (i.e. migration_base).

Furthermore, all the path leading to hrtimer_grab_expiry_lock() assumes
timer->base and timer->base->cpu_base are always non-NULL. So it is safe
to remove the NULL checks here.

Signed-off-by: Julien Grall <julien.grall@arm.com>

---

I don't have a reproducer so far, but I can't see why it would not be
possible to happen.
---
 kernel/time/hrtimer.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
index 119414a2f59c..5eb45a868de9 100644
--- a/kernel/time/hrtimer.c
+++ b/kernel/time/hrtimer.c
@@ -934,7 +934,7 @@ void hrtimer_grab_expiry_lock(const struct hrtimer *timer)
 {
 	struct hrtimer_clock_base *base = READ_ONCE(timer->base);
 
-	if (timer->is_soft && base && base->cpu_base) {
+	if (timer->is_soft && base != &migration_base) {
 		spin_lock(&base->cpu_base->softirq_expiry_lock);
 		spin_unlock(&base->cpu_base->softirq_expiry_lock);
 	}
-- 
2.11.0

Re: [RT PATCH 3/3] hrtimer: Prevent using uninitialized spin_lock in hrtimer_grab_expiry_lock()

[Thomas Gleixner]

On Wed, 21 Aug 2019, Julien Grall wrote:

> migration_base is used as a placeholder when an hrtimer is switching
> between base (see switch_hrtimer_timer_base). It is possible
> theoritically possible to have timer->base equal to migration_base.
> 
> Even if it is a placeholder, it would pass all the current check in
> hrtimer_grab_expiry_lock() leading to use softirq_expiry_lock
> uninitialized.
>
> This is can be prevented by checking whether the base is equal to
> the placeholder (i.e. migration_base).

That's a lame argument. The point is that it does not make sense to do that
on migration base, but not for the reason you are giving (uninitialized
lock).

If base == migration_base then there is no point to lock soft_expiry_lock
simply because the timer is not executing the callback in soft irq context
and the whole lock/unlock dance can be avoided.

But, yes. Good catch.

Thanks,

	tglx

Re: [RT PATCH 3/3] hrtimer: Prevent using uninitialized spin_lock in hrtimer_grab_expiry_lock()

[Julien Grall]

Hi Thomas,

Thank you for the review.

On 21/08/2019 15:02, Thomas Gleixner wrote:
> On Wed, 21 Aug 2019, Julien Grall wrote:
> 
>> migration_base is used as a placeholder when an hrtimer is switching
>> between base (see switch_hrtimer_timer_base). It is possible
>> theoritically possible to have timer->base equal to migration_base.
>>
>> Even if it is a placeholder, it would pass all the current check in
>> hrtimer_grab_expiry_lock() leading to use softirq_expiry_lock
>> uninitialized.
>>
>> This is can be prevented by checking whether the base is equal to
>> the placeholder (i.e. migration_base).
> 
> That's a lame argument. The point is that it does not make sense to do that
> on migration base, but not for the reason you are giving (uninitialized
> lock).

Fair point, I will update the commit message.

> 
> If base == migration_base then there is no point to lock soft_expiry_lock
> simply because the timer is not executing the callback in soft irq context
> and the whole lock/unlock dance can be avoided.
> 
> But, yes. Good catch.

Do you want me to resend the series or can I just provide an update to the 
commit message here?

Cheers,

-- 
Julien Grall