Received-SPF: pass (google.com: domain of linux-kernel+bounces-131856-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) client-ip=147.75.80.249;
From: Anna-Maria Behnsen <anna-maria@linutronix.de>
To: Frederic Weisbecker <frederic@kernel.org>
Cc: Thomas Gleixner <tglx@linutronix.de>, Ingo Molnar <mingo@kernel.org>,
 LKML <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH v2] timers/migration: Fix ignored event due to missing
 CPU update
In-Reply-To: <Zg2Ct6M2RJAYHgCB@localhost.localdomain>
References: <20240401214859.11533-1-frederic@kernel.org>
 <87r0fo9jmw.fsf@somnus> <Zg2Ct6M2RJAYHgCB@localhost.localdomain>
Date: Thu, 04 Apr 2024 18:52:52 +0200
Message-ID: <878r1tvzmj.fsf@somnus>
Precedence: bulk
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Frederic Weisbecker <frederic@kernel.org> writes:

> Le Tue, Apr 02, 2024 at 11:52:23AM +0200, Anna-Maria Behnsen a =C3=A9crit=
 :
>> Frederic Weisbecker <frederic@kernel.org> writes:
>>=20
>> > 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 propagat=
ed
>> > up with a stale CPU value. The following depicts a scenario that has
>> > been actually observed:
>>=20
>> urgh...
>>=20
>> >
>> > Signed-off-by: Frederic Weisbecker <frederic@kernel.org>
>> > ---
>> >  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_migrati=
on.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 *grou=
p, struct tmigr_group *child,
>> >  	 * queue when the expiry time changed only or when it could be ignor=
ed.
>> >  	 */
>> >  	if (timerqueue_node_queued(&evt->nextevt)) {
>> > -		if ((evt->nextevt.expires =3D=3D nextexp) && !evt->ignore)
>> > +		if ((evt->nextevt.expires =3D=3D nextexp) && !evt->ignore) {
>> > +			if (evt->cpu !=3D first_childevt->cpu)
>> > +				evt->cpu =3D first_childevt->cpu;
>>=20
>> 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@kernel.org>
> Date: Mon, 1 Apr 2024 23:48:59 +0200
> Subject: [PATCH v2] timers/migration: Fix ignored event due to missing CP=
U 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 =3D GRP1:1
>                    active   =3D GRP1:1
>                    nextevt  =3D TGRP1:0 (T0)
>                     /              \
>                [GRP1:0]           [GRP1:1]
>             migrator =3D NONE       [...]
>             active   =3D NONE
>             nextevt  =3D TGRP0:0 (T0)
>             /           \
>         [GRP0:0]       [...]
>       migrator =3D NONE
>       active   =3D NONE
>       nextevt  =3D 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 =3D GRP1:1
>                    active   =3D GRP1:1
>                    nextevt  =3D KTIME_MAX
>                     /              \
>                [GRP1:0]           [GRP1:1]
>             migrator =3D NONE       [...]
>             active   =3D NONE
>             nextevt  =3D TGRP0:0 (T0)
>             /           \
>         [GRP0:0]       [...]
>       migrator =3D NONE
>       active   =3D NONE
>       nextevt  =3D 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 =3D GRP1:1
>                    active   =3D GRP1:1
>                    nextevt  =3D KTIME_MAX
>                     /              \
>                [GRP1:0]           [GRP1:1]
>             migrator =3D NONE       [...]
>             active   =3D NONE
>             nextevt  =3D TGRP0:0 (T0)
>             /           \
>         [GRP0:0]       [...]
>       migrator =3D NONE
>       active   =3D NONE
>       nextevt  =3D 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 =3D GRP1:1
>                    active   =3D GRP1:1
>                    nextevt  =3D KTIME_MAX
>                     /              \
>                [GRP1:0]           [GRP1:1]
>             migrator =3D NONE       [...]
>             active   =3D NONE
>             nextevt  =3D TGRP0:0 (T0)
>             /           \
>         [GRP0:0]       [...]
>       migrator =3D NONE
>       active   =3D NONE
>       nextevt  =3D 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 =3D GRP1:1
>                    active   =3D GRP1:1
>                    nextevt  =3D TGRP1:0 (T0)
>                     /              \
>                [GRP1:0]           [GRP1:1]
>             migrator =3D NONE       [...]
>             active   =3D NONE
>             nextevt  =3D TGRP0:0 (T0)
>             /           \
>         [GRP0:0]       [...]
>       migrator =3D NONE
>       active   =3D NONE
>       nextevt  =3D 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 =3D GRP1:1
>                    active   =3D GRP1:1
>                    nextevt  =3D KTIME_MAX
>                     /              \
>                [GRP1:0]           [GRP1:1]
>             migrator =3D NONE       [...]
>             active   =3D NONE
>             nextevt  =3D TGRP0:0 (T0)
>             /           \
>         [GRP0:0]       [...]
>       migrator =3D NONE
>       active   =3D NONE
>       nextevt  =3D 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@kernel.org>

Reviewed-by: Anna-Maria Behnsen <anna-maria@linutronix.de>

Thanks,

	Anna-Maria