Received-SPF: pass (google.com: domain of linux-kernel+bounces-135413-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: Mon, 8 Apr 2024 21:11:39 +0800
From: Chen Yu <yu.c.chen@intel.com>
To: Peter Zijlstra <peterz@infradead.org>
CC: Abel Wu <wuyun.abel@bytedance.com>, 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: <ZhPtCyRmPxa0DpMe@chenyu5-mobl2>
References: <20240226082349.302363-1-yu.c.chen@intel.com>
 <758ebf4e-ee84-414b-99ec-182537bcc168@bytedance.com>
 <20240408115833.GF21904@noisy.programming.kicks-ass.net>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <20240408115833.GF21904@noisy.programming.kicks-ass.net>
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?nJs/Vmmn6onbrF0u2WREIykgbnflyj/sPmGv60Ugd/xTtsQ8ypy/+ksAXHZJ?=
 =?us-ascii?Q?stBhdKrelIuBFziBX4kFYZSHil2Jh+GM9NpJW249yX+4+f/4nS341ZgoJ/a1?=
 =?us-ascii?Q?QvVhcqMeq/ohwzpgd1mJpxqeDbiuzkRwYYNbPkpQ3rMNAxcWyoQNDC8sahuy?=
 =?us-ascii?Q?YfeDujNZq/wC9/nWD3cJXscWGfrm7GC2q28Pbf52MYHmWJLblekMjvPjbFI8?=
 =?us-ascii?Q?cjkEZFzICSp0jWmoieonPmiKsYAtkfByNteJhb+InMOudmUGYiGIP+7b1xv5?=
 =?us-ascii?Q?GU0cKPSI9uB3IJHlA/o+LyC1H3dciGl4BHW2DTwp75gSK4MMgSOkYqeFytol?=
 =?us-ascii?Q?+NYZwGB6RqPo4EbNRO+jbMkmAbya2vd8VXD0qbu0SDl/4yiqGwB86zjLWvEG?=
 =?us-ascii?Q?XJSJA7MLqG6MK4ZKnIch0EVpiwmR3Ty06r87AsAH8D+jl5ohBSPm9l3qx3Vb?=
 =?us-ascii?Q?4CbZfC9feDqfbLzK+31X/BMXSV3j/uwz3wNiOSbWyBK7mCEeFugnu5IIyURt?=
 =?us-ascii?Q?yjYV8F9ShnNu1kp54X5Bn2nAGHcJKOlvTPqb3Tzj9dnOnGfBnnrHWNa5AOxn?=
 =?us-ascii?Q?UrUtsnFj3KgbWrEDbza9thMIKSL8h70ozTc58bZq2DRP8y5PCAx1jJ1MKkJo?=
 =?us-ascii?Q?jBRXi70dVqNyb2U8nrWwX8hrRGB76LVto5QJTbpXcT31uAq4Vt8X3KobsNbz?=
 =?us-ascii?Q?Chzfe7UCr8yCwe1EBBdG5GzD5p0GGkg9cwMtJPFkeAsWGDusS3Tqa8M7dvLk?=
 =?us-ascii?Q?FXc0+8/84F8cpgqta9wMkz+hBgLht3BKanNw9oChSYJWvPcKMhgTwxpkI8Yw?=
 =?us-ascii?Q?tGk4qn7Gtzs9ozrDAAo3aIKqJ2tzEJDyHUdi7m2U6iWvFc0d24vyRcUXNCfs?=
 =?us-ascii?Q?wd03kGv3cH6/HXyRl44ny2QzI5O7j89d6nOVsRyaHY938X0+1TNKUzC3D1T8?=
 =?us-ascii?Q?xHj1NIEcEnIuVCvrdLSJbmYwfvIHuisMTFSbYUQsPvBu0hQR7YYeMrkaBnvV?=
 =?us-ascii?Q?ix2NY8kefHTYOf+yQGcPC8g2b/yi1xiXoyzouFQCVh52IyIF+8d87UuJahSh?=
 =?us-ascii?Q?kpg6RaCigsEmqOsQLQUzfVdo0xiHu85BhCCxg2eJNeb1RtQC1boFyY8jMIVS?=
 =?us-ascii?Q?CBBO5iFZ4v3SKxnp7KNDSGknBXcJ4MrmMceT6FpQ1gDu0nbwEiDNWTbdrfmw?=
 =?us-ascii?Q?YESygU4tyyLr25jstQh++1H5F0I6QWKMbd7hY7ngmS2vAx6JDNa9DJsXBhgu?=
 =?us-ascii?Q?BzXjnLYtTOY1mOOVPT3wFSd0YFaLmtjHkiPsWyhIiPDpBBFlCcfEoAdUlQn2?=
 =?us-ascii?Q?upbFw+OeH+zBopHZyN2GLjBu7UawLGYJydKcGQyw4URvcz/soKv+c/y+AdUw?=
 =?us-ascii?Q?ALKs0nAPEKyO0gfAQLTOFgHadyI6MVhb+nO8ezAc1e4g2GzbD2frGfGkl5Xg?=
 =?us-ascii?Q?k7Y+4YsMeFjr/FEThIhgrJ1OlnoJ7/cbQ5lDFz8E8i796gsFooTasWK6o3Hd?=
 =?us-ascii?Q?u2Lu1T976dj876eq6KUUB4HzhkxnkSEYhOOii5gJersyI6UBIksjoUA2G0zy?=
 =?us-ascii?Q?luEu/upl5UhOeGwZ6EiBgNtR1i/PHdgRWe5oJviH?=
X-MS-Exchange-CrossTenant-Network-Message-Id: d2010802-571c-4724-1c8a-08dc57cd74b3
X-MS-Exchange-CrossTenant-AuthSource: DM4PR11MB6020.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 08 Apr 2024 13:11:51.9061
 (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: zDkRB312q5BYySTiK3qIQXHPNNuUUJUvMixfQJwjM9sKT+e4jJtzT2n5hyiuGIrLybR9GZj/OABTHkiPeFT7aQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SA1PR11MB6781
X-OriginatorOrg: intel.com

On 2024-04-08 at 13:58:33 +0200, Peter Zijlstra wrote:
> On Thu, Feb 29, 2024 at 05:00:18PM +0800, Abel Wu wrote:
> 
> > > 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.
> 
> From the data presented it looks like min_vruntime is wrong and needs
> update. If you can readily reproduce this, dump the vruntime of all
> tasks on the runqueue and see if min_vruntime is indeed correct.
>

This was the dump of all the entities on the tree, from left to right,
and also from top down in middle order traverse, when this issue happens:

[  514.461242][ T8390] cfs_rq avg_vruntime:386638640128 avg_load:2048 cfs_rq->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  <-- leftmost se
[  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   <-- root se
[  514.539605][ T8390]  middle se 0xec4fcf20 deadline:763762447228 min_vruntime:763760947228 vruntime:763760947228 non-eligible

The tree looks like:

          se (0xec1234e0)
                  |
                  |
                  ----> se (0xec4fcf20)


The root se 0xec1234e0 is also the leftmost se, its min_vruntime and vruntime are both 763383370431,
which is aligned with cfs_rq->min_vruntime. It seems that the cfs_rq's min_vruntime gets updated correctly,
because it is monotonic increasing.

My guess is that, for some reason, one newly forked se in a newly created task group, in the rb-tree has not
been picked for a long time(maybe not eligible). Its vruntime stopped at the negative value(near (unsigned long)(-(1LL << 20))
for a long time, its vruntime is long behind the cfs_rq->vruntime, thus the overflow happens.


thanks,
Chenyu

> > > 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.
> 
> The reason is to ensure the wrap-around logic works -- which it must,
> because with the weighting thing, the vruntime can wrap quite quickly,
> something like one day IIRC (20 bit for precision etc.)
> 
> Better to have the wrap around happen quickly after boot and have
> everybody suffer, rather than have it be special and hard to reproduce.