Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Thu, 24 Feb 2022 12:40:09 +0530
From:   "Gautham R. Shenoy" <gautham.shenoy@amd.com>
To:     Abel Wu <wuyun.abel@bytedance.com>
Cc:     Ingo Molnar <mingo@redhat.com>,
        Peter Zijlstra <peterz@infradead.org>,
        Juri Lelli <juri.lelli@redhat.com>,
        Vincent Guittot <vincent.guittot@linaro.org>,
        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>,
        linux-kernel@vger.kernel.org, srikar@linux.vnet.ibm.com,
        aubrey.li@intel.com
Subject: Re: [RFC PATCH 1/5] sched/fair: record overloaded cpus
Message-ID: <YhcvUV/jW7yr0Sn+@BLR-5CG11610CF.amd.com>
References: <20220217154403.6497-1-wuyun.abel@bytedance.com>
 <20220217154403.6497-2-wuyun.abel@bytedance.com>
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20220217154403.6497-2-wuyun.abel@bytedance.com>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?jBvdgJyqfobwag7GJ+W8gduJLh3elE+kl9I1bakSaukyf8V/ZvmNtmCwM5DL?=
 =?us-ascii?Q?A8juAivDmPzZ1Vqvn/oJLztVnvIHSMK5vZs385Tz/s7dvW4JPolutr95kXk5?=
 =?us-ascii?Q?wg66o4zxHu1/lLZDj/ZBThpkLGTPzRJilHpolSHWYi8IeIB+ZqBWZ3WZZUAz?=
 =?us-ascii?Q?uv6UirNvQkM+QF2SY8/Gce4xzKQmgATBDZDuRov8s7TdHHP8qnZ+JSPEaxnk?=
 =?us-ascii?Q?aYpsHVWnnoSfvFOhdIwpPYcJWVY35/VeiZpx2trS3CU+I+oh8P5P2RA+b17f?=
 =?us-ascii?Q?Gtr/CIaHMu3a4l1SXETpMYj9KrGEpa6vM5Kt0gh8V7ogO8OSmFzj3JGlmI6/?=
 =?us-ascii?Q?iGLZ+B21fVB+fSSeiOeUQdXX56CDX+WgajpwxIYrybGa0e8Mgy2q7ZMpBhzy?=
 =?us-ascii?Q?8v+tzLMtFIYrNfp7s9pSKxT9emIwwiBJSrQjENKaqgmIWFQlXqUPpHzubmyg?=
 =?us-ascii?Q?MVyfePNd61gH2o/CIDp0zMuLSnM/kXlEdMy0ZbzLnv4E6jpPlS9bItg3RWDT?=
 =?us-ascii?Q?I+saMzb+oV0TpWqvHrvOX9xMQ6DYXJIqjHMedZ1ibpkNdKAp4cqRK61xIuWH?=
 =?us-ascii?Q?ZXZTI3nNydIgx6gvGzE1RI+cBl29eAYi0HP8odiNsr6HK6OGTxhWIp6XMkS6?=
 =?us-ascii?Q?8tdTKXFKK3xxlDTgvvC2V7WE0d/Kztmq1PIBPOd6HIfUqQtFia4/4MrkfDkI?=
 =?us-ascii?Q?hrLZsWBOdv19Yi/0CMS2g7NCy4DvIG0pEzug+mfH7sfEnR/763jga6ypTjx9?=
 =?us-ascii?Q?etYVkqGu5nbTwZb+aCjio7TtJ53se9MsPS0z4XQY/Af0WfQ1l1Wb1SBm9diE?=
 =?us-ascii?Q?ynb2MKurnqOq+osSIDg5ZSxjEyGtZCxAat2k3rBESKtEq/cIkjLS7QcCFyfp?=
 =?us-ascii?Q?KcfdKArU6jNnEi19kTE993evnLCmUyLOX1IDd7fMI3E94G0Rl7BUWXny1XbS?=
 =?us-ascii?Q?GzcX0ukg11L67kIL9R28cFDqI+NLIvmcJy0o+PufxHpRjDxEDBz0VayAbD+i?=
 =?us-ascii?Q?w80u+x65Y5OgPM6HkScR6DUB4H5tx34mCdg51tXMDbCW+3abJKeoCGsAK++e?=
 =?us-ascii?Q?csoEFV0ziCnjijlyaAA61BIymS5A7uZgxAz8gUpF+O7qqWTJwPah9shyPVUP?=
 =?us-ascii?Q?Uk+9uQQ19VLbS8N5YzGFOaBBAWdM7sNth3XRzmGLEzn9OSjsvBGJ5O0/+rrM?=
 =?us-ascii?Q?i9vWYNsXc9T5eR2hmnPnHvGDqaiedKztDyGm9mofAa/j/c4QBIPgdkxDpV27?=
 =?us-ascii?Q?55UvSd/LwDtQ1lmoyOA09ATcXWwb4Sm5CpLd34pntBCElDwlVomqaA7nKGfd?=
 =?us-ascii?Q?ot3Dxax9QSLU3KuOW7ErnPLaXbTknkKCVTtbEGKYZxNvJV3oNwL/aRpXxUU3?=
 =?us-ascii?Q?3up5A0y6B8oBWrR/CEEnvZutG0sNFVN0K/GbYvgZx5cylFzCUFOR0rg7yGl2?=
 =?us-ascii?Q?bRybf4GCADsN7ISvAgFyy13mtVmCh8Z9zZukHysgkfkmeDEmuvhtSBrcsC07?=
 =?us-ascii?Q?aNbjIaSfmxEE841FInR5ZRoX9ZgBNR9aMou+za3EsknNXILCKPgdx417camc?=
 =?us-ascii?Q?3FdJhdpqL0tGFDIw4cH4aLrRAknxAf7RY1mXrEpZJQ4+JMbAVJ3rOZkBj9Og?=
 =?us-ascii?Q?XN9Bv3IxD9TyBVHgm9Fe5n8=3D?=
X-OriginatorOrg: amd.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 502f5b24-b0f6-433e-cb33-08d9f764bd94
X-MS-Exchange-CrossTenant-AuthSource: BYAPR12MB3286.namprd12.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 24 Feb 2022 07:10:30.3289
 (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: oOz6CPDS60f0MupCQImv48UHS0JXkdv10rue5XjBBhcObxuPYAvZpObf3nXqBHYaeK/grzK/k+3jzUbahQ/1Dw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM6PR12MB4580
X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,
        RCVD_IN_MSPIKE_H2,SPF_HELO_PASS,SPF_PASS,T_SCC_BODY_TEXT_LINE
        autolearn=ham autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

Hello Abel,

(+ Aubrey Li, Srikar)

On Thu, Feb 17, 2022 at 11:43:57PM +0800, Abel Wu wrote:
> An CFS runqueue is considered overloaded when there are
> more than one pullable non-idle tasks on it (since sched-
> idle cpus are treated as idle cpus). And idle tasks are
> counted towards rq->cfs.idle_h_nr_running, that is either
> assigned SCHED_IDLE policy or placed under idle cgroups.
> 
> The overloaded cfs rqs can cause performance issues to
> both task types:
> 
>   - for latency critical tasks like SCHED_NORMAL,
>     time of waiting in the rq will increase and
>     result in higher pct99 latency, and
> 
>   - batch tasks may not be able to make full use
>     of cpu capacity if sched-idle rq exists, thus
>     presents poorer throughput.
> 
> The mask of overloaded cpus is updated in periodic tick
> and the idle path at the LLC domain basis. This cpumask
> will also be used in SIS as a filter, improving idle cpu
> searching.

This is an interesting approach to minimise the tail latencies by
keeping track of the overloaded cpus in the LLC so that
idle/sched-idle CPUs can pull from them. This approach contrasts with the
following approaches that were previously tried :

1. Maintain the idle cpumask at the LLC level by Aubrey Li
   https://lore.kernel.org/all/1615872606-56087-1-git-send-email-aubrey.li@intel.com/
   
2. Maintain the identity of the idle core itself at the LLC level, by Srikar :
   https://lore.kernel.org/lkml/20210513074027.543926-3-srikar@linux.vnet.ibm.com/

There have been concerns in the past about having to update the shared
mask/counter at regular intervals. Srikar, Aubrey any thoughts on this
?


> 
> Signed-off-by: Abel Wu <wuyun.abel@bytedance.com>
> ---
>  include/linux/sched/topology.h | 10 ++++++++++
>  kernel/sched/core.c            |  1 +
>  kernel/sched/fair.c            | 43 ++++++++++++++++++++++++++++++++++++++++++
>  kernel/sched/sched.h           |  6 ++++++
>  kernel/sched/topology.c        |  4 +++-
>  5 files changed, 63 insertions(+), 1 deletion(-)
> 
> diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
> index 56cffe42abbc..03c9c81dc886 100644
> --- a/include/linux/sched/topology.h
> +++ b/include/linux/sched/topology.h
> @@ -81,6 +81,16 @@ struct sched_domain_shared {
>  	atomic_t	ref;
>  	atomic_t	nr_busy_cpus;
>  	int		has_idle_cores;
> +
> +	/*
> +	 * The above varibles are used in idle path and
> +	 * select_task_rq, and the following two are
> +	 * mainly updated in tick. They are all hot but
> +	 * for different usage, so start a new cacheline
> +	 * to avoid false sharing.
> +	 */
> +	atomic_t	nr_overloaded	____cacheline_aligned;
> +	unsigned long	overloaded[];	/* Must be last */
>  };
>  
>  struct sched_domain {
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 1d863d7f6ad7..a6da2998ec49 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -9423,6 +9423,7 @@ void __init sched_init(void)
>  		rq->wake_stamp = jiffies;
>  		rq->wake_avg_idle = rq->avg_idle;
>  		rq->max_idle_balance_cost = sysctl_sched_migration_cost;
> +		rq->overloaded = 0;
>  
>  		INIT_LIST_HEAD(&rq->cfs_tasks);
>  
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 5c4bfffe8c2c..0a0438c3319b 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -6968,6 +6968,46 @@ balance_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>  
>  	return newidle_balance(rq, rf) != 0;
>  }
> +
> +static inline int cfs_rq_overloaded(struct rq *rq)
> +{
> +	return rq->cfs.h_nr_running - rq->cfs.idle_h_nr_running > 1;
> +}
> +
> +/* Must be called with rq locked */
> +static void update_overload_status(struct rq *rq)
> +{
> +	struct sched_domain_shared *sds;
> +	int overloaded = cfs_rq_overloaded(rq);
> +	int cpu = cpu_of(rq);
> +
> +	lockdep_assert_rq_held(rq);
> +
> +	if (rq->overloaded == overloaded)
> +		return;
> +
> +	rcu_read_lock();
> +	sds = rcu_dereference(per_cpu(sd_llc_shared, cpu));
> +	if (unlikely(!sds))
> +		goto unlock;
> +
> +	if (overloaded) {
> +		cpumask_set_cpu(cpu, sdo_mask(sds));
> +		atomic_inc(&sds->nr_overloaded);
> +	} else {
> +		cpumask_clear_cpu(cpu, sdo_mask(sds));
> +		atomic_dec(&sds->nr_overloaded);
> +	}
> +
> +	rq->overloaded = overloaded;
> +unlock:
> +	rcu_read_unlock();
> +}
> +
> +#else
> +
> +static inline void update_overload_status(struct rq *rq) { }
> +
>  #endif /* CONFIG_SMP */
>  
>  static unsigned long wakeup_gran(struct sched_entity *se)
> @@ -7315,6 +7355,8 @@ done: __maybe_unused;
>  	if (new_tasks > 0)
>  		goto again;
>  
> +	update_overload_status(rq);
> +

So here, we are calling update_overload_status() after
newidle_balance(). If we had pulled a single task as a part of
newidle_balance(), in your current code, we do not update the overload
status. While this should get remedied in the next tick, should we
move update_overload_status(rq) prior to the new_tasks > 0 check ?


--
Thanks and Regards
gautham.