Received-SPF: pass (google.com: domain of linux-kernel+bounces-213115-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.199.223 as permitted sender) client-ip=147.75.199.223;
Date: Thu, 13 Jun 2024 19:45:57 +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: <Zmrb9YlcUAo10TsP@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>
 <ZmJylkNFg7EFgPmZ@chenyu5-mobl2>
 <9F5C4D69-4238-44DA-9247-5CE8E7B3ECB6@gmail.com>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <9F5C4D69-4238-44DA-9247-5CE8E7B3ECB6@gmail.com>
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?gwiEPkbM4yOBg1Obuw9s2hSDiIf8/d9CdO1/iFBxFctgxt217ckF/abB9D6P?=
 =?us-ascii?Q?PkbkBnDPPnNlQ0XYpHIaxC7D/5jOoNZ/NeBiVzfVU2QuTbPOwYWatiLVqQx1?=
 =?us-ascii?Q?8987lYYaXBHkYICuDSSF4/wVaDcz79pTvT+Pztn5/GZNXIN8erFdsAV4eUp0?=
 =?us-ascii?Q?1u3GelOhWsTSI5i7wpVPYI4ULHMDf4V44PkJDMKLYQf/mr2Fy0ydsaY1AXEl?=
 =?us-ascii?Q?BbYRhCLoYLBsyB8tNU6uFuAGmSN4Vn5ePcvaTFbliMYK9egAXC2IPLDb8wjz?=
 =?us-ascii?Q?HaeeJhMZC7laSJQYT14PN1CfiNBDZEQeYxVJkT8ftWjX+5zbXV1LdUpX/MRF?=
 =?us-ascii?Q?cmoP3omFkRn5ATKpUfVftevla+RA4M7V8O2f0meduy8tL+7LiOn8EDibKnt4?=
 =?us-ascii?Q?Qv+k75kJ8SclvNt8zrIo8j+f0l7MCugQHqj5pwIyoVfBOnvZxmdNc1OjcaHO?=
 =?us-ascii?Q?bg5+rZ152J96XmthVcL9yuRSygO1CUbyu+y83khIfZmE7JLZNBkK7H1WbgQ0?=
 =?us-ascii?Q?Y28x7ucPvASDu07zoZxVyiZRUfSAXxyN4J6MRkyGD/lX5gJYWYY4FCzQ+fqs?=
 =?us-ascii?Q?dzT3hVXMa+Ok38iFxS1Q+Fnaq26hwu0wxMr09yZfbifEbgnzyVAbBrNaO1x4?=
 =?us-ascii?Q?j1FUvrruB9bBjHTu3I4eO3tKoIrNLomq79ak/wE3HzSQ5lzKFErtBopUBgKv?=
 =?us-ascii?Q?oLmw/vPMEHy6SUuqoz40SeAALNY8BnhJ6Yob3Eiwn0zr0DO7TgwmSVKuqZBJ?=
 =?us-ascii?Q?w603HOsiFWAbUq2lXaBZygPgWJVsO1UoN++CVzHavbXv4H18asOEKEo9edWW?=
 =?us-ascii?Q?8t4aW5jLDo183G0Bc0tN2DlgMHsgMsb/UJph4z+J24crvK7lIaDOeLfpajkA?=
 =?us-ascii?Q?qKvm2rXsUj1+QD70LCz8WulBmB7X/pnmYZ8cxtWlfdSGT/dVF1kZ82OPv6+v?=
 =?us-ascii?Q?z0FOnRQirFmp0zUT4pA86X7RARK2Lzeu31SfeFrPk9awx+Wl0bnw73qo6ray?=
 =?us-ascii?Q?DVNjCSzzYcYomNgSg4VmNj1WTCRm3uiE6mHQ0A3NAaWlEUWoFVGDclgSyB2S?=
 =?us-ascii?Q?KBeA0gn1yb3el1bGRV/izd2kTqW5NxGa98VcyBxo5idhGvxsso9L7qh6Lexm?=
 =?us-ascii?Q?wvK4TQVL/qJ70IsTCEUPC7CqsijKKT0feH3NBTbbZtBIbkSCimTLtKSgAFSg?=
 =?us-ascii?Q?Pxx8vf7UfnO5jcVadboYCnrnYqrm1beDmXIPiOxZmnRTlf8/Nv6cXD1ZnuJ6?=
 =?us-ascii?Q?oX8hjGwF0DWZQhpTXILMiaSwRct7OiddJTBwPv/kfYLSinmetGd3FbUrG3fp?=
 =?us-ascii?Q?KCD8xtnEozBWqi52XsqnOxVwc8OuIUt+anD+MSYNLz0Zm+HYiMxQMKWiEImE?=
 =?us-ascii?Q?SPPbrjEZTOTAB9HFfW25CppOFwIWMyfgSXy3mAWFJInv4WpPjLmIAWoyZS+O?=
 =?us-ascii?Q?85EtYeBLC/UkCKkS13NVYEG2bYP37rHIzcMZjol9zd3wMLh8lYsw2O/l1gcD?=
 =?us-ascii?Q?TVZWHksfNAf4qn56ORzxndQdofy2hyg1o/3XmJpxdM9nkFRhcoZ808KWw/ti?=
 =?us-ascii?Q?ClryjyVVSADViOv+G16PmGSofbLnM1bimvacBFFD?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 8be80587-303c-4b48-4e89-08dc8b9e6d1d
X-MS-Exchange-CrossTenant-AuthSource: DM4PR11MB6020.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 13 Jun 2024 11:46:13.2651
 (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: NXIWPLhBsq4UYvltUjLqdTaEkaXSMzK03tp94az3mSiMrhP+Aune4RiXpTbdWxFWju1xJKXpUdGy5BfL5dJpeA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN7PR11MB8041
X-OriginatorOrg: intel.com

On 2024-06-11 at 21:10:50 +0800, Chunxin Zang wrote:
> 
> 
> > On Jun 7, 2024, at 10:38, Chen Yu <yu.c.chen@intel.com> wrote:
> > 
> > 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().
> 
> Hi chen
> 
> Happy holidays. I believe the modifications here will indeed provide more opportunities for preemption,
> thereby leading to lower scheduling latencies, while also truly reducing calls to pick_eevdf.  It's a win-win situation. :)
> 
> I conducted a test. It involved applying my modifications on top of MIKE PATCH, along with
> adding some statistical counts following your previous method, in order to assess the potential
> benefits of my changes.
>

[snip]
 
> Looking at the results, adding an ineligible check for the se within check_preempt_wakeup_fair
> can prevent 3% of pick_eevdf calls under the RUN_TO_PARITY feature, and in the case of
> NO_RUN_TO_PARITY, it can prevent 30% of pick_eevdf calls. It was also discovered that the
> patch_preempt_only_count is at 0, indicating that all invalid checks for the se are correct.
> 
> It's worth mentioning that under the RUN_TO_PARITY feature, the number of preemptions
> triggered by 'pick_eevdf != se' would be 2.25 times that of the original version, which could
> lead to a series of other performance issues. However, logically speaking, this is indeed reasonable. :(
> 
>

I wonder if we can only do this for NO_RUN_TO_PARITY? That is to say, if RUN_TO_PARITY is enabled,
we do not preempt the current task based on its eligibility in check_preempt_wakeup_fair()
or entity_tick(). Personally I don't have objection to increase the preemption a little bit, however
it seems that we have encountered over-scheduling and that is why RUN_TO_PARITY was introduced,
and RUN_TO_PARITY means "respect the slice" per my understanding.

> > So I think NEXT_BUDDY has more or less reduced the rb-tree scan.
> > 
> > thanks,
> > Chenyu
> 
> I'm not completely sure if my understanding is correct, but NEXT_BUDDY can only cache the process
> that has been woken up; it doesn't necessarily correspond to the result returned by pick_eevdf.  Furthermore,
> even if it does cache the result returned by pick_eevdf, by the time the next scheduling occurs, due to
> other processes enqueing or dequeuing, it might not be the result picked by pick_eevdf at that moment.
> Hence, it's a 'best effort' approach, and therefore, its impact on scheduling latency may vary depending
> on the use case.
>

That is true, currently the NEXT_BUDDY is set to the wakee if it is eligible, not mean it is the best
candidate in the tree. I think it is 'best effort' to reduce the wakeup latency rather than fairness.

thanks,
Chenyu