Received-SPF: pass (google.com: domain of linux-kernel+bounces-84734-linux.lists.archive=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) client-ip=139.178.88.99;
Precedence: bulk
MIME-Version: 1.0
References: <20240226082349.302363-1-yu.c.chen@intel.com>
In-Reply-To: <20240226082349.302363-1-yu.c.chen@intel.com>
From: Xuewen Yan <xuewen.yan94@gmail.com>
Date: Wed, 28 Feb 2024 17:04:49 +0800
Message-ID: <CAB8ipk9N9verfQp6U9s8+TQgNbA5J0DWkOB1dShf20n0xbx94w@mail.gmail.com>
Subject: Re: [RFC PATCH] sched/eevdf: Return leftmost entity in pick_eevdf()
 if no eligible entity is found
To: Chen Yu <yu.c.chen@intel.com>
Cc: Peter Zijlstra <peterz@infradead.org>, Ingo Molnar <mingo@redhat.com>, 
	Vincent Guittot <vincent.guittot@linaro.org>, Juri Lelli <juri.lelli@redhat.com>, 
	Abel Wu <wuyun.abel@bytedance.com>, Tim Chen <tim.c.chen@intel.com>, 
	Tiwei Bie <tiwei.btw@antgroup.com>, Honglei Wang <wanghonglei@didichuxing.com>, 
	Aaron Lu <aaron.lu@intel.com>, Chen Yu <yu.chen.surf@gmail.com>, 
	linux-kernel@vger.kernel.org, kernel test robot <oliver.sang@intel.com>, 
	Xuewen Yan <xuewen.yan@unisoc.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Yu

On Mon, Feb 26, 2024 at 4:26=E2=80=AFPM Chen Yu <yu.c.chen@intel.com> wrote=
:
>
> There is occasional report from lkp that the kernel hits the NULL pointer
> exception:
>
> [  512.079810][ T8305] BUG: kernel NULL pointer dereference, address: 000=
0002c
> [  512.080897][ T8305] #PF: supervisor read access in kernel mode
> [  512.081636][ T8305] #PF: error_code(0x0000) - not-present page
> [  512.082337][ T8305] *pde =3D 00000000
> [  512.082829][ T8305] Oops: 0000 [#1] PREEMPT SMP
> [  512.083407][ T8305] CPU: 1 PID: 8305 Comm: watchdog Tainted: G        =
W
> [  512.086203][ T8305] EIP: set_next_entity (fair.c:?)
>
> This is caused by NULL candidate returned by pick_eevdf() as Abel analyze=
d.
> After
> commit 2227a957e1d5 ("sched/eevdf: Sort the rbtree by virtual deadline")
> the NULL candidate would trigger the NULL pointer exception. While before
> this commit, there would be warning.
>
> This NULL entity issue was always there before above commit. With debug
> patch to print the cfs_rq and all the entities in the tree, we have the
> information when the issue was reproduced:
>
> [  514.461242][ T8390] cfs_rq avg_vruntime:386638640128 avg_load:2048 min=
_vruntime:763383370431
> [  514.535935][ T8390] current on_rq se 0xc5851400, deadline:184358520135=
62231446
>                         min_vruntime:18437121115753667698 vruntime:184358=
52013561943404, load:629
> [  514.536772][ T8390] Traverse rb-tree from left to right
> [  514.537138][ T8390]  se 0xec1234e0 deadline:763384870431 min_vruntime:=
763383370431 vruntime:763383370431 non-eligible
> [  514.537835][ T8390]  se 0xec4fcf20 deadline:763762447228 min_vruntime:=
763760947228 vruntime:763760947228 non-eligible
> [  514.538539][ T8390] Traverse rb-tree from topdown
> [  514.538877][ T8390]  middle se 0xec1234e0 deadline:763384870431 min_vr=
untime:763383370431 vruntime:763383370431 non-eligible
> [  514.539605][ T8390]  middle se 0xec4fcf20 deadline:763762447228 min_vr=
untime:763760947228 vruntime:763760947228 non-eligible
> [  514.540340][ T8390] Found best:0x0
> [  514.540613][ T8390] BUG: kernel NULL pointer dereference, address: 000=
00074
>
> We can see that non of the entities in the tree are eligible, neither is
> the current entity on this cfs_rq. As a result, curr is set to NULL:
> if (curr && (!curr->on_rq || !entity_eligible(cfs_rq, curr)))
>         curr =3D NULL;
>
> and the best is set to NULL, which caused the problem:
> if (!best || (curr && entity_before(curr, best)))
>         best =3D curr;
>
> The cause is that, the curr is eligible, but vruntime_eligible()
> returns false. And the false negative is due to the following
> code in vruntime_eligible():
>
> return avg >=3D (s64)(vruntime - cfs_rq->min_vruntime) * load;
>
> According to the log, vruntime is 18435852013561943404, the
> cfs_rq->min_vruntime is 763383370431, the load is 629 + 2048 =3D 2677,
> thus:
> s64 delta =3D (s64)(18435852013561943404 - 763383370431) =3D -10892823530=
978643
>     delta * 2677 =3D 7733399554989275921
> that is to say, the multiply result overflow the s64, which turns the
> negative value into a positive value, thus eligible check fails.
>
> So where is this insane huge vruntime 18435852013561943404 coming from?
> My guess is that, it is because the initial value of cfs_rq->min_vruntime
> is set to (unsigned long)(-(1LL << 20)). If the task(watchdog in this cas=
e)
> seldom scheduled in, its vruntime might not move forward too much and
> remain its original value by previous place_entity().

Could you please test the follow patch:

https://lore.kernel.org/all/20240130080643.1828-1-xuewen.yan@unisoc.com/

Because the se->vruntime would be changed in place_entity() and
reweight_eevdf(),
however, now the vlag may exceed eevdf's limit in some scenarios, it may ca=
use
the vrunitme's error.

>
> The proper fix should deal with the overflow of entity_key() * load, but
> I don't have much clue on that, so propose this conservative method to
> restore the previous behavior before the mentioned commit.
>
> Fixes: 2227a957e1d5 ("sched/eevdf: Sort the rbtree by virtual deadline")
> Reported-by: kernel test robot <oliver.sang@intel.com>
> Closes: https://lore.kernel.org/lkml/202401301012.2ed95df0-oliver.sang@in=
tel.com/
> Signed-off-by: Chen Yu <yu.c.chen@intel.com>
> ---
>  kernel/sched/fair.c | 13 ++++++++++++-
>  1 file changed, 12 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 533547e3c90a..fb9202f464e2 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -880,7 +880,7 @@ static struct sched_entity *pick_eevdf(struct cfs_rq =
*cfs_rq)
>         struct rb_node *node =3D cfs_rq->tasks_timeline.rb_root.rb_node;
>         struct sched_entity *se =3D __pick_first_entity(cfs_rq);
>         struct sched_entity *curr =3D cfs_rq->curr;
> -       struct sched_entity *best =3D NULL;
> +       struct sched_entity *best =3D NULL, *leftmost;
>
>         /*
>          * We can safely skip eligibility check if there is only one enti=
ty
> @@ -905,6 +905,8 @@ static struct sched_entity *pick_eevdf(struct cfs_rq =
*cfs_rq)
>                 goto found;
>         }
>
> +       leftmost =3D se;
> +

Maybe judging which of the deadlines of curr and se is smaller is better?

>         /* Heap search for the EEVD entity */
>         while (node) {
>                 struct rb_node *left =3D node->rb_left;
> @@ -937,6 +939,15 @@ static struct sched_entity *pick_eevdf(struct cfs_rq=
 *cfs_rq)
>         if (!best || (curr && entity_before(curr, best)))
>                 best =3D curr;
>
> +       /*
> +        * entity_eligible() could bring false negative due to
> +        * multiply overflow, which reports no eligible entity.
> +        * Return leftmost entity as a backup(it is guaranteed
> +        * the tree is not NULL.
> +        */
> +       if (!best)
> +               best =3D leftmost;
> +
>         return best;
>  }
>
> --
> 2.25.1
>
>

BR
--
xuewen