Messages in this thread | | | Date | Thu, 29 Feb 2024 17:00:18 +0800 | Subject | Re: [RFC PATCH] sched/eevdf: Return leftmost entity in pick_eevdf() if no eligible entity is found | From | Abel Wu <> |
| |
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. Besides, choosing the leftmost entity which could be non-eligible can be sub-optimal, anyway this is only a workaround..
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.
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.
> > 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?
Thanks & BR, Abel
> > 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@intel.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 = cfs_rq->tasks_timeline.rb_root.rb_node; > struct sched_entity *se = __pick_first_entity(cfs_rq); > struct sched_entity *curr = cfs_rq->curr; > - struct sched_entity *best = NULL; > + struct sched_entity *best = NULL, *leftmost; > > /* > * We can safely skip eligibility check if there is only one entity > @@ -905,6 +905,8 @@ static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) > goto found; > } > > + leftmost = se; > + > /* Heap search for the EEVD entity */ > while (node) { > struct rb_node *left = 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 = 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 = leftmost; > + > return best; > } >
| |