Re: [RFC PATCH] sched/eevdf: Return leftmost entity in pick_eevdf() if no eligible entity is found

[Abel Wu]

On 3/1/24 3:07 PM, Chen Yu Wrote:
> On 2024-02-29 at 17:00:18 +0800, Abel Wu wrote:
> > Hi Chen, thanks for detailed analysis.
> >
> > The title of this patch sounds a little weird to me, since any
> > non-empty cfs_rq should have at least one eligible entity.
>
> My understanding is that, current + cfs_rq's tree has at least one
> eligible entity, as the current running entity is not on the tree.
> In vruntime_eligible() check, we consider all the entities on the
> tree, plus the current running one. So, it could be possible that
> all the entities on the tree are not eligible, while the current is
> eligible, no?

Yes, and I didn't mean only rb-tree when I said "non-empty cfs_rq" :)

> > Besides, choosing the leftmost entity which could be non-eligible can be
> > sub-optimal, anyway this is only a workaround..
>
> Yes, it is a workaround to show the possible scenario to bring NULL exception,
> and it was not root caused yet.
>   
> > On 2/26/24 4:23 PM, Chen Yu Wrote:
> > > There is occasional report from lkp that the kernel hits the NULL pointer
> > > exception:
> > >
> > > [  512.079810][ T8305] BUG: kernel NULL pointer dereference, address: 0000002c
> > > [  512.080897][ T8305] #PF: supervisor read access in kernel mode
> > > [  512.081636][ T8305] #PF: error_code(0x0000) - not-present page
> > > [  512.082337][ T8305] *pde = 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 analyzed.
> > > 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:18435852013562231446
> > > 			min_vruntime:18437121115753667698 vruntime:18435852013561943404, 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_vruntime:763383370431 vruntime:763383370431 non-eligible
> > > [  514.539605][ T8390]  middle se 0xec4fcf20 deadline:763762447228 min_vruntime:763760947228 vruntime:763760947228 non-eligible
> > > [  514.540340][ T8390] Found best:0x0
> > > [  514.540613][ T8390] BUG: kernel NULL pointer dereference, address: 00000074
> > >
> > > 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 = NULL;
> > >
> > > and the best is set to NULL, which caused the problem:
> > > if (!best || (curr && entity_before(curr, best)))
> > > 	best = 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 >= (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 = 2677,
> > > thus:
> > > s64 delta = (s64)(18435852013561943404 - 763383370431) = -10892823530978643
> > >       delta * 2677 = 7733399554989275921
> > > that is to say, the multiply result overflow the s64, which turns the
> > > negative value into a positive value, thus eligible check fails.
> >
> > Indeed.
> >
> > > 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 case)
> > > seldom scheduled in, its vruntime might not move forward too much and
> > > remain its original value by previous place_entity().
> >
> > So why not just initialize to 0? The (unsigned long)(-(1LL << 20))
> > thing is dangerous as it can easily blow up lots of calculations in
> > lag, key, avg_vruntime and so on.
>
> Usually the min variable is initialized to a very large value, so later
> the real min can overwrite it easily. The 1LL << 20 was introduced decade ago
> in 67e9fb2a39a1, and I don't know why it is this value.

Yes, as the min_vruntime keeps moving forward given the way
update_min_vruntime() does, I don't think it would be a problem.

> > Say during this pre-life, which is about 1ms for 1024-weight entity,
> > there is only one entity running in this cfs_rq. Now another entity
> > with funny lag joins in, being placed somewhere at 0+ vruntime, so
> > cfs_rq->min_vruntime needs to be adjusted accordingly which leads to
> > the breakage of cfs_rq->curr's key as you showed above.
>
> Yes, this is possible.
>
> > > 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.
> >
> > Inspired by Xuewen's proposal, will it work if limit the key?

After a second thought, this doesn't solve the insane huge vruntime
itself. Since the immediate problem is that 'huge' number actually is
a small one, is it possible to make vruntime s64 at definition?