Re: [PATCH v2] timers/migration: Fix ignored event due to missing CPU update
From: Anna-Maria Behnsen
Date: Thu Apr 04 2024 - 12:53:02 EST
Frederic Weisbecker <frederic@xxxxxxxxxx> writes:
> Le Tue, Apr 02, 2024 at 11:52:23AM +0200, Anna-Maria Behnsen a écrit :
>> Frederic Weisbecker <frederic@xxxxxxxxxx> writes:
>>
>> > When a group event is updated with its expiry unchanged but a different
>> > CPU, that target change may go unnoticed and the event may be propagated
>> > up with a stale CPU value. The following depicts a scenario that has
>> > been actually observed:
>>
>> urgh...
>>
>> >
>> > Signed-off-by: Frederic Weisbecker <frederic@xxxxxxxxxx>
>> > ---
>> > kernel/time/timer_migration.c | 5 ++++-
>> > 1 file changed, 4 insertions(+), 1 deletion(-)
>> >
>> > diff --git a/kernel/time/timer_migration.c b/kernel/time/timer_migration.c
>> > index c63a0afdcebe..90786bb9a607 100644
>> > --- a/kernel/time/timer_migration.c
>> > +++ b/kernel/time/timer_migration.c
>> > @@ -762,8 +762,11 @@ bool tmigr_update_events(struct tmigr_group *group, struct tmigr_group *child,
>> > * queue when the expiry time changed only or when it could be ignored.
>> > */
>> > if (timerqueue_node_queued(&evt->nextevt)) {
>> > - if ((evt->nextevt.expires == nextexp) && !evt->ignore)
>> > + if ((evt->nextevt.expires == nextexp) && !evt->ignore) {
>> > + if (evt->cpu != first_childevt->cpu)
>> > + evt->cpu = first_childevt->cpu;
>>
>> Why not just unconditionally overwriting the evt->cpu value here?
>
> Right! See below:
>
> ---
> From d038dad7345398a2f6671a3cda98a48805f9eba3 Mon Sep 17 00:00:00 2001
> From: Frederic Weisbecker <frederic@xxxxxxxxxx>
> Date: Mon, 1 Apr 2024 23:48:59 +0200
> Subject: [PATCH v2] timers/migration: Fix ignored event due to missing CPU update
>
> When a group event is updated with its expiry unchanged but a different
> CPU, that target change may go unnoticed and the event may be propagated
> up with a stale CPU value. The following depicts a scenario that has
> been actually observed:
>
> [GRP2:0]
> migrator = GRP1:1
> active = GRP1:1
> nextevt = TGRP1:0 (T0)
> / \
> [GRP1:0] [GRP1:1]
> migrator = NONE [...]
> active = NONE
> nextevt = TGRP0:0 (T0)
> / \
> [GRP0:0] [...]
> migrator = NONE
> active = NONE
> nextevt = T0
> / \
> 0 (T0) 1 (T1)
> idle idle
>
> 0) The hierarchy has 3 levels. The left part (GRP1:0) is all idle,
> including CPU 0 and CPU 1 which have a timer each: T0 and T1. They have
> the same expiry value.
>
> [GRP2:0]
> migrator = GRP1:1
> active = GRP1:1
> nextevt = KTIME_MAX
> / \
> [GRP1:0] [GRP1:1]
> migrator = NONE [...]
> active = NONE
> nextevt = TGRP0:0 (T0)
> / \
> [GRP0:0] [...]
> migrator = NONE
> active = NONE
> nextevt = T0
> / \
> 0 (T0) 1 (T1)
> idle idle
>
> 1) The migrator in GRP1:1 handles remotely T0. The event is dequeued
> from the top and T0 executed.
>
> [GRP2:0]
> migrator = GRP1:1
> active = GRP1:1
> nextevt = KTIME_MAX
> / \
> [GRP1:0] [GRP1:1]
> migrator = NONE [...]
> active = NONE
> nextevt = TGRP0:0 (T0)
> / \
> [GRP0:0] [...]
> migrator = NONE
> active = NONE
> nextevt = T1
> / \
> 0 1 (T1)
> idle idle
>
> 2) The migrator in GRP1:1 fetches the next timer for CPU 0 and finds
> none. But it updates the events from its groups, starting with GRP0:0
> which now has T1 as its next event. So far so good.
>
> [GRP2:0]
> migrator = GRP1:1
> active = GRP1:1
> nextevt = KTIME_MAX
> / \
> [GRP1:0] [GRP1:1]
> migrator = NONE [...]
> active = NONE
> nextevt = TGRP0:0 (T0)
> / \
> [GRP0:0] [...]
> migrator = NONE
> active = NONE
> nextevt = T1
> / \
> 0 1 (T1)
> idle idle
>
> 3) The migrator in GRP1:1 proceeds upward and updates the events in
> GRP1:0. The child event TGRP0:0 is found queued with the same expiry
> as before. And therefore it is left unchanged. However the target CPU
> is not the same but that fact is ignored so TGRP0:0 still points to
> CPU 0 when it should point to CPU 1.
>
> [GRP2:0]
> migrator = GRP1:1
> active = GRP1:1
> nextevt = TGRP1:0 (T0)
> / \
> [GRP1:0] [GRP1:1]
> migrator = NONE [...]
> active = NONE
> nextevt = TGRP0:0 (T0)
> / \
> [GRP0:0] [...]
> migrator = NONE
> active = NONE
> nextevt = T1
> / \
> 0 1 (T1)
> idle idle
>
> 4) The propagation has reached the top level and TGRP1:0, having TGRP0:0
> as its first event, also wrongly points to CPU 0. TGRP1:0 is added to
> the top level group.
>
> [GRP2:0]
> migrator = GRP1:1
> active = GRP1:1
> nextevt = KTIME_MAX
> / \
> [GRP1:0] [GRP1:1]
> migrator = NONE [...]
> active = NONE
> nextevt = TGRP0:0 (T0)
> / \
> [GRP0:0] [...]
> migrator = NONE
> active = NONE
> nextevt = T1
> / \
> 0 1 (T1)
> idle idle
>
> 5) The migrator in GRP1:1 dequeues the next event in top level pointing
> to CPU 0. But since it actually doesn't see any real event in CPU 0, it
> early returns.
>
> 6) T1 is left unhandled until either CPU 0 or CPU 1 wake up.
>
> Some other bad scenario may involve trees with just two levels.
>
> Fix this with unconditionally updating the CPU of the child event before
> considering to early return while updating a queued event with an
> unchanged expiry value.
>
> Fixes: 7ee988770326 ("timers: Implement the hierarchical pull model")
> Signed-off-by: Frederic Weisbecker <frederic@xxxxxxxxxx>
Reviewed-by: Anna-Maria Behnsen <anna-maria@xxxxxxxxxxxxx>
Thanks,
Anna-Maria