Received-SPF: pass (google.com: domain of linux-kernel+bounces-87971-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) client-ip=2604:1380:4601:e00::3;
Date: Fri, 1 Mar 2024 14:46:46 +0800
From: Chen Yu <yu.c.chen@intel.com>
To: Xuewen Yan <xuewen.yan94@gmail.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>
Subject: Re: [RFC PATCH] sched/eevdf: Return leftmost entity in pick_eevdf()
 if no eligible entity is found
Message-ID: <ZeF51sKRWaHMJIZ2@chenyu5-mobl2>
References: <20240226082349.302363-1-yu.c.chen@intel.com>
 <CAB8ipk9N9verfQp6U9s8+TQgNbA5J0DWkOB1dShf20n0xbx94w@mail.gmail.com>
 <Zd9QRBaWVgmZ5Df8@chenyu5-mobl2>
 <CAB8ipk9NFXrPM3jMi7U9hWNy-gSiqSWuUu_tBXs0Xgb3R66S_Q@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CAB8ipk9NFXrPM3jMi7U9hWNy-gSiqSWuUu_tBXs0Xgb3R66S_Q@mail.gmail.com>
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?dXpXVy9EK0VUMlVGMm16Rkp4bkNkSU9MbEs4UldYSzk5aW9RUFlaTlpXcVVW?=
 =?utf-8?B?WnVTSUEzOFhCSVpGVHQ0eEs3RjlFa2tJMXFpWnpib0Ixb1p2U1RFUnRPM01Z?=
 =?utf-8?B?VWtFdTBLWVgybGJiTnZRV1V3WGhoYks5a0ZpMGQvWlYyQy9HblJ4RjVBUXVt?=
 =?utf-8?B?K1RTcEFFZVJxLzUxZnFCMVZjSDl3ajU3LzZWZnN5TklNM1FGUU82WTV2WjNN?=
 =?utf-8?B?TzF1R3FEM1RyMlRoN0U4MFpmUmhuTHVZVGErVGxLSDEwcC9EZDNiRWkyaEhG?=
 =?utf-8?B?T21SRlA1NzJnL0E3aTZwSGloTTZ2eFkxbWJURkxMVWxlM3d6TTNxb2h3bGJv?=
 =?utf-8?B?cms5ZGpNSVRKVjBuZGZJRWhIajkyN1REU1YzL01UaTRBOUZmV28vUXJ5V0Vr?=
 =?utf-8?B?TWF2TENVcitKa2ZXRzhORXovMW1JeG45bVB3Ky9SdTUvWkw1dTZJeGNzSWgz?=
 =?utf-8?B?WVJnTkx2YWVnRzhscEs1Y1hLRXhyMXdBeGZ3VS84L2dqaFRCQ2ZBbXVpQ3pm?=
 =?utf-8?B?aVhKN3NkQlRSdXRwWUt1dFJTSS9xeXI3cjVCd1dYcEp2YVNtWVQrcVZuYlAv?=
 =?utf-8?B?dWtldTJ5Ri9sTStab1R0VDRBOElKUndzajRYK0NaMm9BMmVqWk5WWkUybVRu?=
 =?utf-8?B?dVpxWHVYTzZpaUcvUFo2REhOWEhxYk9SWE1rdHY5Mm83S05LWVk3Q0JQM1ZC?=
 =?utf-8?B?dXRoK2RWanZQWGZYL1VjMk1XRnhzS1QrOHYvNjFGdGJkako1T1ZOWWpKczZG?=
 =?utf-8?B?dEdERjZmUVFHb2ZBR1hSa3pUNUZVY0FTbmhrQk56Z2tpaVF1QjB6bTFhcDRa?=
 =?utf-8?B?ck9tSEF6Z1VXRzRkMEhyQm40YmFvL2FFVFh3Mm5pRHlxaXNPcG5reHNUMTNu?=
 =?utf-8?B?VEZ3ZVFjVGdKVTMzRUVaVndHUnJ3TllBTXdrT2ZLSVBqdE9FRnRQNUg4a1E4?=
 =?utf-8?B?NXVjN2RZQ214ZTJhUFpaTW96bWRxbnZlYjZvR09NbEhtem5ZS3c5d2MxUk5B?=
 =?utf-8?B?WHFkQi9uaFIxRzJlNmpFZGNWN3hudHRjbEFVZnRYckJ3eE03VUp1YllZM3Bs?=
 =?utf-8?B?d3FmcGJZenRvNjBoaDgwSldWNDFQb1cwYk1ObkViejRUb0U3OUpzaHdFUlVH?=
 =?utf-8?B?aFBhVVZCcTAwdVFlaVp6eHRLRE1jdGVwWDBmeFUxeXNqQVIyQ01QNDVUTzVs?=
 =?utf-8?B?dlh2V3Z6MW5nNVJYMDVwTUUrbW5YVHdHVUNVQ1U2MnFZTGFEVExDZlRlaVcv?=
 =?utf-8?B?TWtueitjWDQrNWh0QW1MT0tiM284Ym8rd0xiZFg3NTcrdVp6UlpLamxXdnFM?=
 =?utf-8?B?Mmh1MkNqRGxrM2xvR0tlREswRHduZlVLMkl0Rmpid3Fkd1AvM0F2S3hCcmVZ?=
 =?utf-8?B?UmtEVU5HOC81cDRKR2RxMFJILzUwVGo1eVhzWVhvNExKTG5GTWc4THA1M1lq?=
 =?utf-8?B?dHN4NXNTWmdaRSs2dmpPWTlnN1dQaTAyZnBFeFNWYjVUWUZGeHZEUVFJODRV?=
 =?utf-8?B?TTFPcWNMUUNNSFlveVAxdStYTldIQVVPdi9tRVNuQ0dTTWtqeThEeHZpVVl6?=
 =?utf-8?B?UWtjTXZqZnl6cDR2d0FLakNoL3JEUzQ4KzgyM1BtUGRBTXg1ejQ0WFFDVHFD?=
 =?utf-8?B?NXloUm5lREFjMGkzTGpWOVV5OHRKQ1cyL2c4M1Q3ZDhjOHcrSTF4dkxuOW01?=
 =?utf-8?B?VW9sQ3lGR1l3Ty9sd1ZsNm1yTG9BcVE4akVZRE9LdGN0SGdxeEFnMUJ6eFJs?=
 =?utf-8?B?amg2Y05YcTBMc0ZORlVaYUxGV28vM2NjZWVscjU2ei9CaTJJcW03NXZkSlNC?=
 =?utf-8?B?cFE2OXZFeVZYK0hidEZFZi9DakoxYm13RWVjUTIzVEZjTWc5YnhKZzZ5NVBa?=
 =?utf-8?B?Z2w1RkZUV1l1U1JkN0JQMTZSK21sYlJPWThXU1BCVjh6c0ZrT3k4NTNZRXZ1?=
 =?utf-8?B?K21KV2JqWi9LSW5GcnJMcGxlUkVPUjJONERDbWhzbzVnY0d4NFJXZi9LcldW?=
 =?utf-8?B?TWNsZTFHWXRVSzBoNXE0bnJnd0VWaVBNTzgzNVFXNTd3OUcxdjNVNkNjemhm?=
 =?utf-8?B?dm5IaUNMRlRPNVNsVHRvVTJZRE5YK3pCeVBxSkZvK0svajNLRjB4U2I2enBv?=
 =?utf-8?Q?ZL/+dTqn0B7lBf4aRI5dS539y?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 574b8b59-8783-4d09-af38-08dc39bb6452
X-MS-Exchange-CrossTenant-AuthSource: DM4PR11MB6020.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 01 Mar 2024 06:46:58.5807
 (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: /Oiy8bbmcRihYg9wF4qA/kpnV3Kog+gvkcN+uluQ+iSWsAlG1X0enuElejBPgtR7MiUmxPLmhGuOyLpudWB0Pg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY5PR11MB6162
X-OriginatorOrg: intel.com

On 2024-02-29 at 20:10:32 +0800, Xuewen Yan wrote:
> Hi Yu
> 
> On Wed, Feb 28, 2024 at 11:25 PM Chen Yu <yu.c.chen@intel.com> wrote:
> >
> > Hi Xuewen,
> >
> > On 2024-02-28 at 17:04:49 +0800, Xuewen Yan wrote:
> > > Hi Yu
> > >
> > > On Mon, Feb 26, 2024 at 4:26 PM 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: 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.
> > > >
> > > > 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().
> > >
> > > 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 cause
> > > the vrunitme's error.
> > >
> >
> > Thanks for providing this fix. I took a quick look at your patch, and it looks
> > reasonable to me. I'm not quite sure if the vlag issue is the root cause of
> > this NULL candidate problem, say, if the abnormal vlag happens, it should satisfy:
> > curr->vlag == curr->deadline ?
> 
> Actually, this is just a situation, because in set_next_entity(), it
> would set the valg be equal to deadline, and if using the vlag to
> update the vruntime, the vruntime is most likely wrong.

Yes, the child with wrong vlag might bring potential risk after child been place_entity().

> However, even if vlag is normal, after the calc: ((W + w_i)*vl'_i / W)
> or (w/w'), it may also be an out-of-bounds value.
> For example: if change the nice from -20(weight:88761) to
> 19(weight:15), its vlag would be 88761/15=5917*vlag.
>

Yes, this might exceed the limit range of vlag, 

> >
> > According to the data,
> > curr->deadline =
> > cfs_rq->min_vruntime = 763383370431
> > cfs_rq->avg_vruntime = 386638640128
> > entity_key = -10892823530978643
> > avg = -6851585614346926319
> > load = 2677
> > so avg_vruntime() = 18444185410266494357
> > curr->vlag = 8333396704550953
> > which does not equal to curr->deadline = 18435852013562231446
> >
> > Anyway, if we want to root cause why vruntime is behind cfs_rq->min_vruntime so
> > much, we can add more debug code to further investigation. And we will also leverage
> > lkp to test your vlag fix patch set.
> 
> Yes, maybe you can see more information by adding log in place_entity().
>

Sure, let me think about that.

thanks,
Chenyu