Received-SPF: pass (google.com: domain of linux-kernel+bounces-205256-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) client-ip=147.75.80.249;
Date: Fri, 7 Jun 2024 10:38:14 +0800
From: Chen Yu <yu.c.chen@intel.com>
To: Chunxin Zang <spring.cxz@gmail.com>
CC: K Prateek Nayak <kprateek.nayak@amd.com>, <mingo@redhat.com>, "Peter
 Zijlstra" <peterz@infradead.org>, <juri.lelli@redhat.com>,
	<vincent.guittot@linaro.org>, <dietmar.eggemann@arm.com>,
	<rostedt@goodmis.org>, <bsegall@google.com>, <mgorman@suse.de>,
	<bristot@redhat.com>, <vschneid@redhat.com>, <linux-kernel@vger.kernel.org>,
	<yangchen11@lixiang.com>, Jerry Zhou <zhouchunhua@lixiang.com>, Chunxin Zang
	<zangchunxin@lixiang.com>, Balakumaran Kannan <kumaran.4353@gmail.com>, "Mike
 Galbraith" <efault@gmx.de>
Subject: Re: [PATCH] sched/fair: Reschedule the cfs_rq when current is
 ineligible
Message-ID: <ZmJylkNFg7EFgPmZ@chenyu5-mobl2>
References: <20240524134011.270861-1-spring.cxz@gmail.com>
 <ZlCyhDspcZQhxlNk@chenyu5-mobl2>
 <06649B84-DA1D-4360-B0C4-79C81A34BC08@gmail.com>
 <cf8fdb86-194b-34c4-f5e8-dd7ddc56d8d9@amd.com>
 <ZmCeBwNO2t2ikrcm@chenyu5-mobl2>
 <CF70ED2D-2566-4CA7-A9BB-E8536F353797@gmail.com>
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CF70ED2D-2566-4CA7-A9BB-E8536F353797@gmail.com>
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?M0d6MmhUT0N1UURGMWhqazg2MGdCMmtSVDlBRmpIQTV5ZkE5cGdHcENwN0Fs?=
 =?utf-8?B?bXRiYmY0aG92Nmk5N2M0VjdXOEY2aTdaalJyMDZFdjdSUFdZR1hhV0xvdXhp?=
 =?utf-8?B?VkNkT0YvNVplMStoc05QelpxbTlna0NLQlRScC9iNlRFK0lwSGtYMUtQL3dG?=
 =?utf-8?B?VXE5MStqUE84WFJtZzlOdlIyS2IvTHdJZlhwOWRRMjVwTURBSWl5aUMyOHhM?=
 =?utf-8?B?V0dXWGhGTXZHZEFxU0E4MnQvUmNRU1VTUUpnUHJFaityUE5mUXE3OTZ3Qis2?=
 =?utf-8?B?ZzRJNDNaanNzMmVnN1lRYXFrQXZZMVF5S2FIWXhoM0djMGovdGw1bnFHSVVG?=
 =?utf-8?B?YWllWlhVSWFCeEVXKzVVL0FvYjlCbk92SjNmeldRd0RJdjJoVDQwVzduVXlH?=
 =?utf-8?B?aTJ4OC8xVEZZM3JtWGZtZkFVd2dDSG04WW4zcmtWVzcwVGZFMDJkcmVvQXY1?=
 =?utf-8?B?N3ZhUi9qc1MwQis1eWJ2Q2x1TEJMZnpKbmhGekprSXlRQ1dZUGl0bkV2L291?=
 =?utf-8?B?Zmd4NmFiOWt5UHdrRy9aY0hrWXczM3p3bTlEOStvR0J2OTZCTkd3bVV0L2Iw?=
 =?utf-8?B?M0xEcW9QNWEzU2Y1dk9DQWNCSWZ0dVJGbWU5VXJoKzV4MTlIdlhiQVJlY0xq?=
 =?utf-8?B?SUl6amRCemdWV1NrbVNYdE1nSHhCMWVNK1NEc3lVN0RKbnFxa0pwQ3I0dkdq?=
 =?utf-8?B?em9iZVRmYXlIYWVZZmhSYzZOcEx4V0c1Y2pjdHR3ZHN6a2V3d0U3Mk1WNWQ3?=
 =?utf-8?B?N0phOXpFN0I4UWowTkE5Tk9yRXNIQkVpTG4wQmpITDdXQkVrSXVQTjlEVXkx?=
 =?utf-8?B?R3JxT1lEb2pldUdxb1AyUUR5R3FQSzh6UEZGeDlzUWg4TWNSTU51b3lYMVpN?=
 =?utf-8?B?ZWZaSUVtSmZsY3BxRjFmbWo4RXI2UUVjZS83MUF4NVdzcUJFOHpDZ3RWd3hY?=
 =?utf-8?B?ZTZwbFgzNTJwMWpkekN3a2pySG5URUFlRW1FbXR0dUlKZmR4a1U4SVdoa2tR?=
 =?utf-8?B?b0VmWjY4Yk9uK2xVR2hUcVFzM0dTQzNaZkFaYnNtdGJMNEMrdFE2ZmtIcE1Y?=
 =?utf-8?B?TTU4VFByNmtDZTFXdC8zb3hNN0RLYWYwZWtBYmVkYzZ4UUVjZlFoRUhIQ3Nm?=
 =?utf-8?B?ektIS3hpMmpVSTcrc0kzTXV2OHZpYWVuWE1odmNpWHUvQlRPcUlRVTRMZERY?=
 =?utf-8?B?YWxQL0ExaUFZVXJJY1lPTjZFRE5PN1c2U1gwNFlKaEVBNFVTamhrblBXYkhm?=
 =?utf-8?B?YU90MmF0NFFBTk5VUUl1OXpsV2IyT2tLcDJnSTdjbUVqaDVWNTZLZC82eVov?=
 =?utf-8?B?bW82SkdDQk9XZGJ2RWsrTGZXdWlBSlQyMXIwWmVnNG05eHdaZ0ZZVS9kR2FI?=
 =?utf-8?B?Z1BTUG9xSXhibVR5aHRTSnlVRGNVSkcyekJEcGhrdmNLMjFkVzdkbTMvRFBX?=
 =?utf-8?B?NkZ5dTcrTkhUV3RwTW9tYmM3RHFqdzZZQysyMktZMU0vNXFWUXViKzUwaWFZ?=
 =?utf-8?B?dHc0UmZrZmVpVTNqZnFCQ1lFdXBJcFdzTGVFVlVIZFJGK1E0bFFoYUJsYjJO?=
 =?utf-8?B?VmNJcHZTSDdEUkIvSEdWS2xxQTBPOWp4L1Rkb0JOaEo3aW5PUFdDMjNhNXpU?=
 =?utf-8?B?YmtDdGRxRGc3M2hocHh4akpmalI4MjFPL0Z6L014QmpRK0JEOXJudUxUTlJx?=
 =?utf-8?B?V2RhSmFhYkJ2b1NiOTUranQ1L0JiQnI5bEVuVnRyRHNVVkxUWE5NQ2hTdnd6?=
 =?utf-8?B?ZFpscjYzai9FM25CTzNkU3FkbWpOaDRkVjRPK24vQXJjcDhTZTIvTUY0eDRG?=
 =?utf-8?B?clZHcWFJVG0wanY4WEZVSmRIeCt4VVltZTBzM3gxZ2twOGFDbWJsZnZ5cFlp?=
 =?utf-8?B?MzZobFdMb1BoejJQSVZ3Zk5MaEZ2cXRZcEVDb0RkNW1HcFo5L21kMUJYMk1V?=
 =?utf-8?B?ZFBwWWJSYlQ0VDRaU05ldk1tV2ZCWlNtbzRLZEp2WlBxdkFjSkc2UFg0alNW?=
 =?utf-8?B?L092QndOREJpbVF5Mlk4Vm01ajNYN3pFVStJb1IzVUpVTm0zK1hFaFNHaG5z?=
 =?utf-8?B?d3dFVWpTc0dqdFBRZ3lmeUxmQTNkWXRuOWl6WUlJR2g5VmVmOTlOOGRYVm9l?=
 =?utf-8?Q?k+/a8I2l7l83uRXRNPJiXCqMm?=
X-MS-Exchange-CrossTenant-Network-Message-Id: b21a7952-3aba-4d63-0e56-08dc869aea31
X-MS-Exchange-CrossTenant-AuthSource: DM4PR11MB6020.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 07 Jun 2024 02:38:29.4425
 (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: 2wp6xhFDT01SUmsFBHBomOnuzhBkxHOiRoh+0X+QfTVCQyNoMCXCh/2nzP3CiUldHWuAFEXPQz3xgcDOy6WxhA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN7PR11MB6993
X-OriginatorOrg: intel.com

On 2024-06-06 at 09:46:53 +0800, Chunxin Zang wrote:
> 
> 
> > On Jun 6, 2024, at 01:19, Chen Yu <yu.c.chen@intel.com> wrote:
> > 
> > 
> > Sorry for the late reply and thanks for help clarify this. Yes, this is
> > what my previous concern was:
> > 1. It does not consider the cgroup and does not check preemption in the same
> >   level which is covered by find_matching_se().
> > 2. The if (!entity_eligible(cfs_rq, se)) for current is redundant because
> >   later pick_eevdf() will check the eligible of current anyway. But
> >   as pointed out by Chunxi, his concern is the double-traverse of the rb-tree,
> >   I just wonder if we could leverage the cfs_rq->next to store the next
> >   candidate, so it can be picked directly in the 2nd pick as a fast path?
> >   Something like below untested:
> > 
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 8a5b1ae0aa55..f716646d595e 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -8349,7 +8349,7 @@ static void set_next_buddy(struct sched_entity *se)
> > static void check_preempt_wakeup_fair(struct rq *rq, struct task_struct *p, int wake_flags)
> > {
> >        struct task_struct *curr = rq->curr;
> > -       struct sched_entity *se = &curr->se, *pse = &p->se;
> > +       struct sched_entity *se = &curr->se, *pse = &p->se, *next;
> >        struct cfs_rq *cfs_rq = task_cfs_rq(curr);
> >        int cse_is_idle, pse_is_idle;
> > 
> > @@ -8415,7 +8415,11 @@ static void check_preempt_wakeup_fair(struct rq *rq, struct task_struct *p, int
> >        /*
> >         * XXX pick_eevdf(cfs_rq) != se ?
> >         */
> > -       if (pick_eevdf(cfs_rq) == pse)
> > +       next = pick_eevdf(cfs_rq);
> > +       if (sched_feat(NEXT_BUDDY) && !(wake_flags & WF_FORK) && next)
> > +               set_next_buddy(next);
> > +
> > +       if (next == pse)
> >                goto preempt;
> > 
> >        return;
> > 
> > 
> > thanks,
> > Chenyu
> 
> Hi Chen
> 
> First of all, thank you for your patient response. Regarding the issue of avoiding traversing
> the RB-tree twice, I initially had two methods in mind. 
> 1. Cache the optimal result so that it can be used directly during the second pick_eevdf operation.
>   This idea is similar to the one you proposed this time. 
> 2. Avoid the pick_eevdf operation as much as possible within 'check_preempt_wakeup_fair.' 
>   Because I believe that 'checking whether preemption is necessary' and 'finding the optimal
>   process to schedule' are two different things.

I agree, and it seems that in current eevdf implementation the former relies on the latter.

> 'check_preempt_wakeup_fair' is not just to
>   check if the newly awakened process should preempt the current process; it can also serve
>   as an opportunity to check whether any other processes should preempt the current one,
>   thereby improving the real-time performance of the scheduler. Although now in pick_eevdf,
>   the legitimacy of 'curr' is also evaluated, if the result returned is not the awakened process,
>   then the current process will still not be preempted.

I thought Mike has proposed a patch to deal with this scenario you mentioned above:
https://lore.kernel.org/lkml/e17d3d90440997b970067fe9eaf088903c65f41d.camel@gmx.de/

And I suppose you are refering to increase the preemption chance on current rather than reducing
the invoke of pick_eevdf() in check_preempt_wakeup_fair().

> Therefore, I posted the v2 PATCH. 
>   The implementation of v2 PATCH might express this point more clearly. 
> https://lore.kernel.org/lkml/20240529141806.16029-1-spring.cxz@gmail.com/T/
>

Let me take a look at it and do some tests.
 
> I previously implemented and tested both of these methods, and the test results showed that
> method 2 had somewhat more obvious benefits. Therefore, I submitted method 2. Now that I
> think about it, perhaps method 1 could also be viable at the same time. :)
>

Actually I found that, even without any changes, if we enabled sched feature NEXT_BUDDY, the
wakeup latency/request latency are both reduced. The following is the schbench result on a
240 CPUs system:

NO_NEXT_BUDDY
Wakeup Latencies percentiles (usec) runtime 100 (s) (1698990 total samples)
        50.0th: 6          (429125 samples)
        90.0th: 14         (682355 samples)
      * 99.0th: 29         (126695 samples)
        99.9th: 529        (14603 samples)
        min=1, max=4741
Request Latencies percentiles (usec) runtime 100 (s) (1702523 total samples)
        50.0th: 14992      (550939 samples)
        90.0th: 15376      (668687 samples)
      * 99.0th: 15600      (128111 samples)
        99.9th: 15888      (11238 samples)
        min=3528, max=31677
RPS percentiles (requests) runtime 100 (s) (101 total samples)
        20.0th: 16864      (31 samples)
      * 50.0th: 16928      (26 samples)
        90.0th: 17248      (36 samples)
        min=16615, max=20041
average rps: 17025.23

NEXT_BUDDY
Wakeup Latencies percentiles (usec) runtime 100 (s) (1653564 total samples)
        50.0th: 5          (376845 samples)
        90.0th: 12         (632075 samples)
      * 99.0th: 24         (114398 samples)
        99.9th: 105        (13737 samples)
        min=1, max=7428
Request Latencies percentiles (usec) runtime 100 (s) (1657268 total samples)
        50.0th: 14480      (524763 samples)
        90.0th: 15216      (647982 samples)
      * 99.0th: 15472      (130730 samples)
        99.9th: 15728      (13980 samples)
        min=3542, max=34805
RPS percentiles (requests) runtime 100 (s) (101 total samples)
        20.0th: 16544      (62 samples)
      * 50.0th: 16544      (0 samples)
        90.0th: 16608      (37 samples)
        min=16470, max=16648
average rps: 16572.68

So I think NEXT_BUDDY has more or less reduced the rb-tree scan.

thanks,
Chenyu