Received-SPF: pass (google.com: domain of linux-kernel+bounces-87991-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) client-ip=147.75.80.249;
Date: Fri, 1 Mar 2024 15:07:37 +0800
From: Chen Yu <yu.c.chen@intel.com>
To: Abel Wu <wuyun.abel@bytedance.com>
CC: Peter Zijlstra <peterz@infradead.org>, Ingo Molnar <mingo@redhat.com>,
	Vincent Guittot <vincent.guittot@linaro.org>, Juri Lelli
	<juri.lelli@redhat.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>
Subject: Re: [RFC PATCH] sched/eevdf: Return leftmost entity in pick_eevdf()
 if no eligible entity is found
Message-ID: <ZeF+uc/jMohokNRb@chenyu5-mobl2>
References: <20240226082349.302363-1-yu.c.chen@intel.com>
 <758ebf4e-ee84-414b-99ec-182537bcc168@bytedance.com>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <758ebf4e-ee84-414b-99ec-182537bcc168@bytedance.com>
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?jojD7NY0feEtMDY7iPsokPMSqIuKANgSS5FPL4UoJBG85q0F4xSCS0uJW+1x?=
 =?us-ascii?Q?LSMeAsTgwvBvTMdLB5wZwJ86yVEJa5NYvzutEoCtNwtgdDVMAvkbZ16BvFmN?=
 =?us-ascii?Q?ipUKRUI8reXwceO/LOHD/kYJaNeRGGYrgYpqHTD0Z2h0Nvw7G/DfH66/H73u?=
 =?us-ascii?Q?MNCWA9n5rFftmRjh9KKBLa98rcVddYdePdjDYhX82+Uldj70xBlLXysHmyY/?=
 =?us-ascii?Q?Z6oGCgZvwqKd0NaUCe5BfKGBkIoNPCMhqF/CJb9a/e0sh/ViXnIsaMbUnkqu?=
 =?us-ascii?Q?KdGfFFtcQrrBofRFlFM5paFKuL6i9GC+1iSTlJiGAvXB/0YIMYLI0PBoEKiV?=
 =?us-ascii?Q?mH97QIcGx3nIkc4OGF1Cx0TZD9TwrAQAWM+nOez/mP8HZSb3z33AzsA758KE?=
 =?us-ascii?Q?8lb4EIeR58kl9mchkKjmnc0EUMyVVvHDwly07Tw01JCLrl+qvKq+b+bXTa2E?=
 =?us-ascii?Q?4q9RiQSOazq9aT3sMuttWGeDAaIq7qpmm12oQT2L5lL+4UrJUwxIr4XC7IXQ?=
 =?us-ascii?Q?7Vql1d33KTeZAGcULxJjbUYwT0J/NCE37F4YAQ5D+u4rC9yYJ45xqYGUOsyO?=
 =?us-ascii?Q?OW7ltoJulSV7BCQIxCQz2Y+/xAdTQeGJp95RvPu4Km5mRu2vqghenIomGnjD?=
 =?us-ascii?Q?5rdZjax8oyWvF0Disd51BJo4TTra2VdOkyMEoKd38H300Tz5k2ghxkaIpaBK?=
 =?us-ascii?Q?c+wULVsBQJmpH8ULWLjInJemuMUe5mqGaMX0e7exE6Rcr6Y2KAMKo1bhyBnh?=
 =?us-ascii?Q?s8/wRT6WrMVr8YDSHPB1c9oqhKlxNca1/1KFCbVvxhIOG/ceoTtkbnnXIUUs?=
 =?us-ascii?Q?wQR3pQDxz1lYxRRDnetuwKINAsPrcZ/RA1aNcfrptLzBR2vnd1hc1zbZUl3u?=
 =?us-ascii?Q?STmGjmjeuudq72ezReBUeTIOYKd+gp341KgI3vre5cHgfE0+5pO4o/YVxUKB?=
 =?us-ascii?Q?JzpZtkssEzHdKUFQlx6p917k4QEs/ChScen2oWDU0LnrXLYWS7KZxqy3w88t?=
 =?us-ascii?Q?g+dGw4ZDSpLfhhw487iJYxv+08qRx4oxMekOKQ2/6naPPWKYQOts3VDXqHK4?=
 =?us-ascii?Q?4l+HPahG+4qnLGxuAymVcHMseeL1Ui03iM880Gk+Vw3i1MQpS7Gp3M/SNvZR?=
 =?us-ascii?Q?FMAd1tPj+JpoaonVC1BHFsvNSDy0/jI5RSx63KLT43ckbSF7b+SrENUk7agf?=
 =?us-ascii?Q?y9opPEYZdfB3O/a2e7IynuDQgfQrzqrgqiAn85A5MNsEtXXOEdNCDXfRr/7b?=
 =?us-ascii?Q?wwfzEzO0hF3irFeVrlb5RSjkKYOG8PKn3Rdhxgz6edP1/Pkaa0pDu6ihzz8b?=
 =?us-ascii?Q?TclE3z+UhqzLuagQnnm6izBNBAUsZdHJa8ihyIcaUsgAk0taUDSAke+jlP5I?=
 =?us-ascii?Q?kQjorkD6Qglj3vpQddKkM8AuASEtQIKkbCXI2UzZL0vN9dIqxFJTvbrHKfUV?=
 =?us-ascii?Q?ugOh3uG/Ktw2q+EbaSebjajpBsD15L/sOsl6Nkg2Xi7jiLfABWobQo9TU7PO?=
 =?us-ascii?Q?uzHOOzduyL4oeL7Vz1jJ8GgPxutwrCLGxTXBSHWo9BftzXmo1Psv4BQDNthD?=
 =?us-ascii?Q?yVN65MnAp7+fODAVKuNOpAWPtcROQ/xAL/tYdKlL?=
X-MS-Exchange-CrossTenant-Network-Message-Id: bd52ada4-6722-4b2d-f7fc-08dc39be4f52
X-MS-Exchange-CrossTenant-AuthSource: DM4PR11MB6020.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 01 Mar 2024 07:07:51.8063
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: PJ9glBhtZsrrh/otrtk3Uwk8Imf/r/Xv7mQ691xYZ2tC9AWspWa/7Eco62itABe5f4G5mTngdEXH6aVZiH/MAw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SJ0PR11MB5022
X-OriginatorOrg: intel.com

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?

> 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.


> 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?
>

Yes we can, let me think about some debug code to demonstrate the scenario
you described above.

thanks,
Chenyu