Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.37 as permitted sender) client-ip=23.128.96.37;
Date:   Thu, 14 Sep 2023 12:36:33 +0530
From:   "Gautham R. Shenoy" <gautham.shenoy@amd.com>
To:     Chen Yu <yu.c.chen@intel.com>
Cc:     Aaron Lu <aaron.lu@intel.com>,
        Peter Zijlstra <peterz@infradead.org>,
        Mathieu Desnoyers <mathieu.desnoyers@efficios.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>,
        Dietmar Eggemann <dietmar.eggemann@arm.com>,
        Steven Rostedt <rostedt@goodmis.org>,
        Ben Segall <bsegall@google.com>, Mel Gorman <mgorman@suse.de>,
        Daniel Bristot de Oliveira <bristot@redhat.com>,
        Valentin Schneider <vschneid@redhat.com>,
        K Prateek Nayak <kprateek.nayak@amd.com>,
        linux-kernel@vger.kernel.org
Subject: Re: [RFC PATCH 2/2] sched/fair: skip the cache hot CPU in
 select_idle_cpu()
Message-ID: <ZQKw+W7k+XNweKBu@BLR-5CG11610CF.amd.com>
References: <cover.1694397335.git.yu.c.chen@intel.com>
 <d49cf5748aa7c6d69580315d2373a9eafa21c21f.1694397335.git.yu.c.chen@intel.com>
 <20230911072629.GA298322@ziqianlu-dell>
 <ZP7SYu+gxlc/YjHu@chenyu5-mobl2>
 <ZQFVFv4GcPOU+X7N@BLR-5CG11610CF.amd.com>
 <ZQFj2hk4i1QAWEQp@chenyu5-mobl2.ccr.corp.intel.com>
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <ZQFj2hk4i1QAWEQp@chenyu5-mobl2.ccr.corp.intel.com>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?fMmnkhQmlCvxosgxwi82Lsub7jWgK/5iMCWmSFljRcYTBKIYS3I5zGQCZZc4?=
 =?us-ascii?Q?Gfgq59XjqsLQ0mTKNB00rKD2J4sGUrM/YYt09uV5XSbdclKOqLgjqbiZT4hL?=
 =?us-ascii?Q?bGowpMafldyuYK9traNCg23RfQP6dcqu79W5Cm4UWf0DjvbYsm/CqPuOePlt?=
 =?us-ascii?Q?aX5PTXCF1vRGFQgezzO4S9RquohGoH1uMSz9psXPhDBrfOcZoANkSgHIpWU0?=
 =?us-ascii?Q?5hXR6K0SZsYdxlro3cIrJbhxC3vmulmDtW9ggPXn+XC5Aln/GYrdIcM/qoI1?=
 =?us-ascii?Q?5THXbxoxub/aljAsvfwsneJ/byv7C2c85JxfRUI71c0/I9hi5ilGvt0TgWWa?=
 =?us-ascii?Q?/q1Kz7O1I/t+d/duZzx19erVjHGfym7kjhwqMZIdb9E1ETpkXoQiufrUxqQv?=
 =?us-ascii?Q?M//5HtSRRpnLAUdJtlEnqVVZWY50HPtWFVL6lSIP8ftrxHitGf1IShxFKQYR?=
 =?us-ascii?Q?fJlezmXzcPfvZnju/f6+S/z6Q+Tawzx9jBaKVdhS4Jxg5DCiZgr3QiVGzQEQ?=
 =?us-ascii?Q?Kq+VL46fhAJReLHXKssjt59g6Ig15BqecfDxi7SAzJS7A9dATvdcSLpJLgf4?=
 =?us-ascii?Q?kxoBExVudMxHfMl8Fmuk05+T6jKijs1czqCIXvt0L7HWYijOkPKNJ2ml/mmd?=
 =?us-ascii?Q?O+9UP8GVR3dTSH+n2+3jQo4XHrP9GlbiAJ3SIflWT1tlF1K6L6YHfQcmLfoO?=
 =?us-ascii?Q?IRD+JAuKfDhzkRl5rIZ+QGUOtGgNofzAx0K7nPRoDy15Obaykcd0IMZzFmge?=
 =?us-ascii?Q?LTZfryKqy9DT3uuk7SPdndwNBkw84WKIg5tjeIW7Fje08BL/hMvru5d51O/L?=
 =?us-ascii?Q?xW3layYiEGhBxrJIdNKvEH4EqbvRYUyiDSuNR8MTWf1rt+Snnd1GBCrdNfCT?=
 =?us-ascii?Q?z14JVpDP52CPi99SRhMCP19dhGr8mxDLyDK8rAaezo6p1LtWN3NyLGarUebt?=
 =?us-ascii?Q?5VZ9puL5lRdqdO/NRAxYpqDmekK8Sor0nYHwQZ2plgO0ix8ad4P8yjGe+Qmq?=
 =?us-ascii?Q?E4gKeQbHUicpTo2aXC2eh9nTmtyH7hcvd41T8B+aSHtD2bdRwqIxyZteKAhN?=
 =?us-ascii?Q?e2e21RS5uG2S90wYGJUEmUq9r9/4901ihL3BD8oKDG1F66y1Lcek7vdKoQA6?=
 =?us-ascii?Q?PAeHgDPBP4v44h0VQxUZXA6zT5ziOBAh3F4YdYiBf9V2NUti67tgG4/Rzzlx?=
 =?us-ascii?Q?J8n3CqsZAXF1hY0uz8L7TlJ16MZ2xKQDDswrp43Jwsz3rRW2OE1u6+FiNzU9?=
 =?us-ascii?Q?UDQvUeCb5DkXQa9WZtkGjxy/BqYr2uExX3nTFbCQlo8nUX3eoMljh6C4L/1L?=
 =?us-ascii?Q?EOmwgtSqZJ4IzUVd+3cxBRAdgcDoIRCSNRSZePGRtW+i2mvlZ7vxQCu7Ip16?=
 =?us-ascii?Q?AAxM718TjIN22G/HpvZo4SODIfvqIid8bCJwBxFtbiiQTx6eHa0ZMxt12e4Z?=
 =?us-ascii?Q?YKIjOR/uuF3kiBs5vWTwekQwPrbpifqNUTzWquHimBggjkdx2sf6C3ccRQ9r?=
 =?us-ascii?Q?PbPNQbD5MhDtqSo2XoV3iKfijCbj1zCzX9xxHKZB85yRgolktqRMcxkWY4vX?=
 =?us-ascii?Q?YoV7c8jdMMqkjBS/b8vcbo//dqBWMlLu47nD+clf?=
X-OriginatorOrg: amd.com
X-MS-Exchange-CrossTenant-Network-Message-Id: dd1c7c31-f902-4463-78c9-08dbb4f12c3f
X-MS-Exchange-CrossTenant-AuthSource: DS7PR12MB8252.namprd12.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 14 Sep 2023 07:06:52.9004
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 3dd8961f-e488-4e60-8e11-a82d994e183d
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: Yf6V9QgdKlbF1e/iHWppFyLL40pvf0p4ZFcLmvfPVRfXt+V9XLAxEQ3Z0sViY/QqBwkGjtcxG/lwHHIcKiEPHw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR12MB4221
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (snail.vger.email [0.0.0.0]); Thu, 14 Sep 2023 00:07:08 -0700 (PDT)

Hello Chen Yu,

On Wed, Sep 13, 2023 at 03:25:14PM +0800, Chen Yu wrote:
> Hi Gautham,
> 
> thanks for the review,
> 
> On 2023-09-13 at 11:52:14 +0530, Gautham R. Shenoy wrote:
> > On Mon, Sep 11, 2023 at 04:40:02PM +0800, Chen Yu wrote:
> > > Hi Aaron,
> > > 
> > > thanks for the review,
> > > 
> > > On 2023-09-11 at 15:26:29 +0800, Aaron Lu wrote:
> > 
> > [..snip..]
> > 
> > > > > @@ -6982,8 +6997,13 @@ static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *p
> > > > >  static inline int __select_idle_cpu(int cpu, struct task_struct *p)
> > > > >  {
> > > > >  	if ((available_idle_cpu(cpu) || sched_idle_cpu(cpu)) &&
> > > > > -	    sched_cpu_cookie_match(cpu_rq(cpu), p))
> > > > > +	    sched_cpu_cookie_match(cpu_rq(cpu), p)) {
> > > > > +		if (sched_feat(SIS_CACHE) &&
> > > > > +		    sched_clock_cpu(cpu) < cpu_rq(cpu)->cache_hot_timeout)
> > > > > +			return -1;
> > > > > +
> > > > 
> > > > Maybe introduce a new function that also considers rq->cache_hot_timeout,
> > > > like available_idle_cpu_migrate() so that above and below logic can be
> > > > simplified a bit?
> > > > 
> > > 
> > > Yes, that would be simpler, I'll do in next version.
> > > 
> > > > I was thinking to simply add that rq->cache_hot_timeout check to
> > > > available_idle_cpu() but then a long sleeping task could be forced to
> > > > migrate if its prev_cpu happens to just deschedule a task that sets rq's
> > > > cache_hot_timeout. I guess that's why you chose to only change the idle
> > > > semantic in select_idle_cpu() but not in select_idle_sibling()?
> > > >
> > > 
> > > Yes, sort of. And the reason I did not put this cache hot check in available_idle_cpu()
> > > or idle_cpu() was mainly because these APIs are generic and could be invoked by select_idle_sibling().
> > > If the task fall asleep and woken up quickly, its previous idle CPU will also be skipped,
> > > thus no one could use this CPU within the cache hot period, including the cache-hot task
> > > itself.
> > 
> > This happens even with this patch right? It is possible for a task p1
> > whose avg sleep time is "t" to go to sleep which causes its CPU to go
> > idle. When it wakes up after a time t' < t, the logic above skips the
> > idle CPU because it is still cache-hot, despite the fact that it is
> > cache hot for p1!
> > 
> Not sure if I understand correctly, in select_idle_sibling() p1's previous
> CPU will be checked first, and that check does not involve cache-hot. So if
> p1's previous CPU is idle, it will be picked, no?
> 
>         if (prev != target && cpus_share_cache(prev, target) &&
>             (available_idle_cpu(prev) || sched_idle_cpu(prev)) &&
>             asym_fits_cpu(task_util, util_min, util_max, prev))
>                 return prev;


You are right, but the "if" condition is the one prior to "if (prev !=
target ...)" which causes p1 can pick the previous CPU here. However,
note that it is not just p1 which can pick the previous CPU as
intended by your patch.

Consider the following case:

* p1' ran on CPUX, and went to sleep. We now update the
  cache_hot_timeout for CPUX based on the sleep-avg of p1'

* When the CPU goes idle, during CPU_NEWLY_IDLE load balancing, (or
  due to shared_runq search), the CPU could pull p1 from another CPU
  Y.

* p1 now runs on CPUX, and goes to sleep.

* We update the cache_hot_timeout for CPUX based on the sleep-avg of p1.

* p1' wakesup and picks prev as the target after doing wake_affine()
  check in select_task_rq_fair().

* In select_idle_sibling() it encounters the following, which checks
  out and thus returns from target.

	if ((available_idle_cpu(target) || sched_idle_cpu(target)) &&
	    asym_fits_cpu(task_util, util_min, util_max, target))
		return target;

* p1 now wakes up, picks the previous cpu as the target. However,
  available_idle_cpu() is no longer true.

So despite "reserving" the CPU for p1, which is likely to have its
data still hot in the case, we would have scheduled p1', thus
defeating the whole purpose of reservation.

To be honest, this isn't so bad, because we have been able to avoid a
migration in this case.

> 
> Or do you mean, in select_idle_cpu(), we will re-check p1's previous
> CPU but it is skipped due to cache-hot?

I had originally thought about this, but then as you pointed out we
have an opportunity to pick the previous cpu in the early checks
inside select_idle_sibling().

> 
> > Have you considered recording p1's identity in the
> > rq->cache_hot_sleeper so that in select_task_rq_fair(), we can simply
> > return the previous CPU if it is cache hot and the wakee is
> > rq->cache_hot_sleeper, thus avoiding the whole select_idle_sibling
> > scan.
> > 
> 
> Yes this seems to be donable, and one problem would be, if there are
> more than 2 dequeued tasks prefer the same (previous) CPU, which task
> should be the rq->cache_hot_sleeper. And per Mathieu's feedback[1], we
> want to deal with multiple dequeued tasks. If we record all of them,
> it might be costly.

If there are multiple dequeued tasks, then it doesn't make sense to
record the identity of the tasks. However, we need the bail out to be
much earlier, in select_task_rq_fair(), perhaps even before the
want_affine() checks.

After all, if the previous CPU is idle, and its cache_hot_timeout
hasn't expired, and if the wakee's sleep duration is less than the
cache_hot_timeout, why don't we just pick it here and be done with it?

> 
> [1] https://lore.kernel.org/lkml/2a47ae82-b8cd-95db-9f48-82b3df0730f3@efficios.com/
> 
> thanks,
> Chenyu

--
Thanks and Regards
gautham.