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:   Wed, 19 Jul 2023 13:18:26 +0800
From:   Aaron Lu <aaron.lu@intel.com>
To:     Vincent Guittot <vincent.guittot@linaro.org>
CC:     Peter Zijlstra <peterz@infradead.org>,
        Ingo Molnar <mingo@redhat.com>,
        Juri Lelli <juri.lelli@redhat.com>,
        Daniel Jordan <daniel.m.jordan@oracle.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>,
        Tim Chen <tim.c.chen@intel.com>,
        Nitin Tekchandani <nitin.tekchandani@intel.com>,
        Yu Chen <yu.c.chen@intel.com>,
        Waiman Long <longman@redhat.com>,
        <linux-kernel@vger.kernel.org>
Subject: Re: [RFC PATCH 3/4] sched/fair: delay update_tg_load_avg() for
 cfs_rq's removed load
Message-ID: <20230719051826.GB84059@ziqianlu-dell>
References: <20230718134120.81199-1-aaron.lu@intel.com>
 <20230718134120.81199-4-aaron.lu@intel.com>
 <CAKfTPtAu33AN6=X82T=yOgm40S8OXi+sPcF0QyD-bYRPV=xPEg@mail.gmail.com>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <CAKfTPtAu33AN6=X82T=yOgm40S8OXi+sPcF0QyD-bYRPV=xPEg@mail.gmail.com>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?mUvbDN2GhEQCjc+LCYB3suUstazgAiRj+I97zolSQeJMSxm7XHHKGyRA8/OJ?=
 =?us-ascii?Q?JiMmmwtVcHyytmK3aI4ghZbL/vA8DsS5zaLcn1wc0lNVIer+suRxTo0qR5cN?=
 =?us-ascii?Q?/mkROYlT3oFo1yS5I8YZtI5WDomNHOW/+pc3pkHUgslahvWybKzyOuBjLWlg?=
 =?us-ascii?Q?0FrfOPKhMM9vZrck3tjBMmoFB6g1QRG/7NedmLQ8vDdjs6A5eUNuYkaDFuM2?=
 =?us-ascii?Q?JX0y6HRjJ83Dh4nKpjyn+BVDX8U7Xx9V5pqiDwcbKnruNmFgIHB1HpENZEZX?=
 =?us-ascii?Q?BsS94MhLd+cxEbXA05vi3XA4ZWna1GprGq50IL3d2dIymOwUf5qKV0K/W1ve?=
 =?us-ascii?Q?KBUd5f4Y3IfdTQk0EesNoatyCczD4gXW+DFAXnDcPKVMZQm4pkTyN8HT73IA?=
 =?us-ascii?Q?g87rBO23hHxbUcRAHjeRc7iXiKFYv/i/wC9PRBbiODUUz600SyJ/iLVt5G4Y?=
 =?us-ascii?Q?s+yAVpskj9W0pucfm1wj7IWdBn24LXzJRREVwYCs8ev2ZL8bVW4ixlvGcbum?=
 =?us-ascii?Q?7WnOzKvJgvYBLPMoE5UpQs0+EOzdrGQaPyimUAZ00vGl74rBIgAfdWDrvkLO?=
 =?us-ascii?Q?YV0tHic8Dkx/lunl4VaXIVbGSIak6BVu0uNYx2+gm5p9t1HLw+Us93BfEynm?=
 =?us-ascii?Q?/ltJe67DS2T9ECMDJcH2vRdLcNPDRLJl/YarxZBAuGftyes4G8JL9gUHuBYI?=
 =?us-ascii?Q?6cuPyc7ReVc40rWJSiEXwV+oB1cds2EqvqzZBVIAI5zUUuyg4dh9oOaYwAlF?=
 =?us-ascii?Q?0s0ptOARFnSDp3DcHrB5BfpB6oc9Mb9B9LVLxi9mL2KgD2ke4AW/cr9GlfJs?=
 =?us-ascii?Q?XYteRQoW3PdwWFSAa9Hc1sfQeisjFJsbS+VeZOB4OTaQlesJs/F9l/QA1h/H?=
 =?us-ascii?Q?ohGM7ZNIHPsbgL2FOvotmjjKLJ/89sikegvuWfLAD1Rd/VFp91h9ezE3Zqlp?=
 =?us-ascii?Q?7TmNJMdAiAoKjxjaiPbVVH1RmiUMQ6phdj39Ye+IOeGiFkdOsLf9NBaKNWO8?=
 =?us-ascii?Q?+9Dn8T3zdW+MYUHSvrCXr0yD+uQ2RpBAOi03ZJ6/K/09ImtF5rVfNkc9GJOo?=
 =?us-ascii?Q?Hlw+OXaPxQirX3srqsHNKFS/qtBoj3ffz7myvYCYiZC6SM512DbeYNJ19hPv?=
 =?us-ascii?Q?cmvt1ogKecvn9/3vik32EenCw7BANNNouAQunbsI/itC+W5+Sqt+LIDmRIdp?=
 =?us-ascii?Q?vCAVqEWa+x9ZleKjYh7THG4X6IGlCMiyxXlsX+rsa9FAUwSLe3nZxzW9Fq7/?=
 =?us-ascii?Q?YnQXo0tu4Sehjl3F5YpjBSP7zS8MLrO49QgnYlLQzMILPTVAaFkCAntnm1kN?=
 =?us-ascii?Q?mlLid66ZatAdE5b+Oo12yH3MLZ6qcOfuHP1yqpdeR+O1o464qrk8XI1LrBVo?=
 =?us-ascii?Q?G3zPswgswjsL4o6tz8SxcgPNayq40/OcLqgAv/LKI4TrF5ZiFQpti7HXhsyH?=
 =?us-ascii?Q?/hqWiJAulxSLfzHX80CfaJnt4i3yMCReenJjFqhwmnEsZPBtFIEJEf06aZub?=
 =?us-ascii?Q?DGyNapYd69IqTOWlaOOv4MxR3/RpHIUKNJQ/l16/mTbqnZE9epF1QRveEXyF?=
 =?us-ascii?Q?57HBVvJh8D6yFhlZX/rr2frARxgYrwTTA+anxfCC?=
X-MS-Exchange-CrossTenant-Network-Message-Id: b08de587-1457-494b-399c-08db88179c61
X-MS-Exchange-CrossTenant-AuthSource: BYAPR11MB3062.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 19 Jul 2023 05:18:39.5868
 (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: x9wb+q+w/sv5QvpS05lkEJva5uVe1iCM1JKAlFDadPsZJJbPz0KW32wUHpuqnxeTyIvIk5Kl3Vzfru59SIqo8w==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CO1PR11MB5107
X-OriginatorOrg: intel.com
X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,
        DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,
        RCVD_IN_DNSWL_BLOCKED,SPF_HELO_NONE,SPF_NONE,T_SCC_BODY_TEXT_LINE,
        URIBL_BLOCKED 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

On Tue, Jul 18, 2023 at 06:01:51PM +0200, Vincent Guittot wrote:
> On Tue, 18 Jul 2023 at 15:41, Aaron Lu <aaron.lu@intel.com> wrote:
> >
> > When a workload involves many wake time task migrations, tg->load_avg
> > can be heavily contended among CPUs because every migration involves
> > removing the task's load from its src cfs_rq and attach that load to
> > its new cfs_rq. Both the remove and attach requires an update to
> > tg->load_avg as well as propagating the change up the hierarchy.
> >
> > E.g. when running postgres_sysbench on a 2sockets/112cores/224cpus Intel
> > Sappire Rapids, during a 5s window, the wakeup number is 14millions and
> > migration number is 11millions. Since the workload can trigger many
> > wakeups and migrations, the access(both read and write) to tg->load_avg
> > can be unbound. For the above said workload, the profile shows
> > update_cfs_group() costs ~13% and update_load_avg() costs ~10%. With
> > netperf/nr_client=nr_cpu/UDP_RR, the wakeup number is 21millions and
> > migration number is 14millions; update_cfs_group() costs ~25% and
> > update_load_avg() costs ~16%.
> >
> > This patch is an attempt to reduce the cost of accessing tg->load_avg.
> 
> here you mention tg->load_avg which is updated with update_tg_load_avg()
> 
> but your patch below modifies the local update of cfs's util_avg,
> runnable_avg  and load_avg which need to be maintained up to date

Yes, since it delayed propagating the removed load, the upper cfs_rqs'
*_avg could be updated later than current code.

> You should be better to delay or rate limit the call to
> update_tg_load_avg() or calc_group_shares()/update_cfs_group() which
> access tg->load_avg and are the culprit instead of modifying other
> place.

Thanks for the suggestion and I think it makes perfect sense.

I tried below to rate limit the update to tg->load_avg at most once per
ms in update_tg_load_avg():

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index a80a73909dc2..e48fd0e6982d 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3665,6 +3665,7 @@ static inline bool cfs_rq_is_decayed(struct cfs_rq *cfs_rq)
 static inline void update_tg_load_avg(struct cfs_rq *cfs_rq)
 {
 	long delta = cfs_rq->avg.load_avg - cfs_rq->tg_load_avg_contrib;
+	u64 now = cfs_rq_clock_pelt(cfs_rq);
 
 	/*
 	 * No need to update load_avg for root_task_group as it is not used.
@@ -3672,9 +3673,11 @@ static inline void update_tg_load_avg(struct cfs_rq *cfs_rq)
 	if (cfs_rq->tg == &root_task_group)
 		return;
 
-	if (abs(delta) > cfs_rq->tg_load_avg_contrib / 64) {
+	if ((now - cfs_rq->last_update_tg_load_avg > 1000000) &&
+	    abs(delta) > cfs_rq->tg_load_avg_contrib / 64) {
 		atomic_long_add(delta, &cfs_rq->tg->load_avg);
 		cfs_rq->tg_load_avg_contrib = cfs_rq->avg.load_avg;
+		cfs_rq->last_update_tg_load_avg = now;
 	}
 }
 
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 14dfaafb3a8f..b5201d44d820 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -594,6 +594,7 @@ struct cfs_rq {
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	unsigned long		tg_load_avg_contrib;
+	u64			last_update_tg_load_avg;
 	long			propagate;
 	long			prop_runnable_sum;
 
From some quick tests using postgres_sysbench and netperf/UDP_RR on SPR,
this alone already delivers good results. For postgres_sysbench, the two
functions cost dropped to 1%-2% each; and for netperf/UDP_RR, the two
functions cost dropped to ~2% and ~4%. Togerther with some more rate
limiting on the read side, I think the end result will be better. Does
the above look reasonable to you?

Alternatively, I can remove some callsites of update_tg_load_avg() like
you suggested below and only call update_tg_load_avg() when cfs_rq is
decayed(really just decayed, not when it detected it has removed load
pending or load propagated from its children). This way it would give us
similar result as above(roughly once per ms).

> 
> Have you tried to remove update_cfs_group() from enqueue/dequeue and
> only let the tick update the share periodically ?

patch4 kind of did that :-)

> 
> Have you tried to make update_tg_load_avg() return early ? the change
> of cfs' load_avg is written in the tg->load_avg only when the change
> is bigger than 1.5%. maybe increase it to 6% ?

Yes, increase the delta is also a good way to limit the update to
tg->load_avg. Will try that too.

> 
> Or like for update_cfs_group, remove it from attach/detach entity and
> let the periodic update to propagate the change
> 
> But please don't touch local update of *_avg

OK I see.

Thanks again for the comments, they are very helpful.