From nobody Wed Apr 29 00:33:16 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 83E5CC433F5 for ; Thu, 26 May 2022 10:40:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1345048AbiEZKkE (ORCPT ); Thu, 26 May 2022 06:40:04 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:42330 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S241731AbiEZKj5 (ORCPT ); Thu, 26 May 2022 06:39:57 -0400 Received: from mail-pl1-x636.google.com (mail-pl1-x636.google.com [IPv6:2607:f8b0:4864:20::636]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 619D1CEB85 for ; Thu, 26 May 2022 03:39:56 -0700 (PDT) Received: by mail-pl1-x636.google.com with SMTP id c2so1123415plh.2 for ; Thu, 26 May 2022 03:39:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance-com.20210112.gappssmtp.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=1qF1kRC9LwiJlnC5OgZ6TWXKv8JNcRSCPefpgmCPVd0=; b=3prUM9x8qMxEGp9TN9u5j+Pn+QPRZ6vtKEOOTjfSve4w4ERlYmn9ZrUQHsNqu8f8Ys +BbC1CCUJCQyfky8idKRSKHXDe3b4jwQ4DFLjqVqnrY3Gh74XkTcQaBtmMMsJ+38b4if SAq6SEjqZYA/PkuEpM+RqqrWotZevQ1MMLXCPh0y6o/snlhbqUMfaByKL+2BLBE6delk DHAEYKLanbnXSXyOouIFC2/YQxPc4KEvgAYuulny8sv0JCXxu0nVg5FUqhHERU+MPspA SsXTlCuYc8sKKlTg/gdhOGzAJG5pKX01pv5fZIiH/1EMGcConD8j2sm1RyNgCZi3qlp1 6cNg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=1qF1kRC9LwiJlnC5OgZ6TWXKv8JNcRSCPefpgmCPVd0=; b=FLqapcr7I97iioHKrsvTOm49IhkdnvwdnV5BiW1DhVKM6OgKllc+UTHl5onZ+KYl/C WGAoJpq1edj8d9EWoODks02aEYWPINa1UyGQekuecI9GOiP3MNhnKx6gpYluhLzk6PYl 2tRlg6UUjb+iIUx11M0yhsvAgPfKhKlpM5+DXjG3wTtbSJRI/QtPNnptbyHb/rGLcP7K EuWr+4jvdWOP03a4E2Z1MOwT82VMPogFceq43WhOwSCmhaR9zZNypjxXzghBYvQMaj+0 7QZQJ5E/kNleWBw+gFPxYHzCrv+t/+A4vszql8JbH4zH3gxUCx57FWzETJJQ9+FNCHT3 eCBA== X-Gm-Message-State: AOAM530VHuZT7Cm5mluJvOsRmxivz4PHi4vz6rBXSjQ2gs/2WRcEjdCr Z/cVu9U6efAC44EvEF9/5i5X7E9ntXMApw== X-Google-Smtp-Source: ABdhPJxgjNHGHZhbqF3mCgZL1AIuiMiG/+kd4oHT3n+gConpQz+Ltl/AIjmdVxqrUx1rFXHmV1v20g== X-Received: by 2002:a17:90b:3a89:b0:1de:bad4:b614 with SMTP id om9-20020a17090b3a8900b001debad4b614mr1919898pjb.139.1653561595952; Thu, 26 May 2022 03:39:55 -0700 (PDT) Received: from C02CV1DAMD6P.bytedance.net ([139.177.225.225]) by smtp.gmail.com with ESMTPSA id u17-20020a17090341d100b0015e8d4eb23dsm1257311ple.135.2022.05.26.03.39.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 26 May 2022 03:39:55 -0700 (PDT) From: Chengming Zhou To: mingo@redhat.com, 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, odin@uged.al Cc: linux-kernel@vger.kernel.org, duanxiongchun@bytedance.com, songmuchun@bytedance.com, Chengming Zhou Subject: [PATCH v3 1/2] sched/fair: fix propagate during synchronous attach/detach Date: Thu, 26 May 2022 18:39:28 +0800 Message-Id: <20220526103929.14976-2-zhouchengming@bytedance.com> X-Mailer: git-send-email 2.35.1 In-Reply-To: <20220526103929.14976-1-zhouchengming@bytedance.com> References: <20220526103929.14976-1-zhouchengming@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" When a task moves from/to a cfs_rq, we first detach/attach the load_avg of se from/to that cfs_rq, then propagate the changes across the tg tree to make it visible to the root, which did in update_load_avg(). But the current code will break when encountering a on_list cfs_rq, can't propagate up to the root cfs_rq, that also mismatch with the comment of propagate_entity_cfs_rq(), which says "Propagate the changes of the sched_entity across the tg tree to make it visible to the root". The second problem is that it won't update_load_avg() for throttled cfs_rq, cause the load changes can't be propagated upwards. A | B --> throttled cfs_rq / C The prop_runnable_sum of C won't be propagated to B, so won't be propagated to A. Fixes: 0258bdfaff5b ("sched/fair: Fix unfairness caused by missing load dec= ay") Signed-off-by: Chengming Zhou --- kernel/sched/fair.c | 10 ++-------- 1 file changed, 2 insertions(+), 8 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 906b2c7c48d1..c6da204f3068 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -11267,14 +11267,8 @@ static void propagate_entity_cfs_rq(struct sched_e= ntity *se) for_each_sched_entity(se) { cfs_rq =3D cfs_rq_of(se); =20 - if (!cfs_rq_throttled(cfs_rq)){ - update_load_avg(cfs_rq, se, UPDATE_TG); - list_add_leaf_cfs_rq(cfs_rq); - continue; - } - - if (list_add_leaf_cfs_rq(cfs_rq)) - break; + update_load_avg(cfs_rq, se, UPDATE_TG); + list_add_leaf_cfs_rq(cfs_rq); } } #else --=20 2.36.1 From nobody Wed Apr 29 00:33:16 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id EAE17C433F5 for ; Thu, 26 May 2022 10:40:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S236472AbiEZKkO (ORCPT ); Thu, 26 May 2022 06:40:14 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:42434 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1347044AbiEZKkD (ORCPT ); Thu, 26 May 2022 06:40:03 -0400 Received: from mail-pf1-x430.google.com (mail-pf1-x430.google.com [IPv6:2607:f8b0:4864:20::430]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 07D56CC17C for ; Thu, 26 May 2022 03:40:02 -0700 (PDT) Received: by mail-pf1-x430.google.com with SMTP id f21so1382626pfa.3 for ; Thu, 26 May 2022 03:40:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance-com.20210112.gappssmtp.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=vrF2vcR0/pW4wvFrzoxssnv5OJSuZjV2lnZF1HbBxGE=; b=T4sjHlQ039UKiokC45ZvXjV+o5SwlzUKvmCsUyso6IjbdRJbzPUw3MIFd3ZYb3efFW JKAmaB0YtnRsvmP+eN/NpPEBtrFhfwWX5ar4zvSyR+werw47xydHsiu5o2/HbEdZIKGx hu1oNQcupimY/0DLqYhTo1hrzD1zlqi3hV8kUiLErv1NuPXvAvRinJvT6iyjJQF8EPQl tCYE3n+drJlU6HlqFCzZUNusXOZNe9hH7O71wYLFGAg0bLMbp8iwQXTVEZEQYbWgaOXx CkN/yO7toObMkNCsxbk2ebu0znNG9aZqFZSUMuCuNSD9PeQ+9FmmPnolfNiD4jCT1w+M oHSQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=vrF2vcR0/pW4wvFrzoxssnv5OJSuZjV2lnZF1HbBxGE=; b=RMst+zSdideOZi9Mf1DLRZGwAGX4DlVZQgkzxQsDl+LGKk1ktbn7SZj3wkVkrj2baG BYcSrRupsgKBvyUfmSezkq4zz6zSWe+pfg+vrtDj982fDsG8CWy6aPTwsJh8QmxJq5Dg J7FUPIRrlRJCHmPiz8AHwaBnQ4IhSlHl8wy0I5qUa5EifmpRn5HBSSt+CNNIY3cBEZex Ux+tbcwEDsx3HHVMzgIxJx7CuqhwQz1BSTGdi4l8D74fFitXd1Sz6vt2xu/mYsccaRxA xQ1MdPn0rcMJjpcShk0Uid3VeFCsFktMWwLNy+4cpgm+pupCa2SO8ivPWYC1T6vZ+hIQ 4OKA== X-Gm-Message-State: AOAM5327ZAJvAhZ8w5re1DASMrLEnTqNtQiCa7GdssSh4eRAwx64BaF1 Q1/3kWbRido/6I4wLHOmf1BsNg== X-Google-Smtp-Source: ABdhPJz4wHFBx2vm4NrKDY9rqMBv7XryWll7+4lR9FYuLFAqIXaogBH5CTBvml+9g1qZBJFo9/fYiA== X-Received: by 2002:a63:2365:0:b0:3db:8691:4fb9 with SMTP id u37-20020a632365000000b003db86914fb9mr32010393pgm.261.1653561601519; Thu, 26 May 2022 03:40:01 -0700 (PDT) Received: from C02CV1DAMD6P.bytedance.net ([139.177.225.225]) by smtp.gmail.com with ESMTPSA id u17-20020a17090341d100b0015e8d4eb23dsm1257311ple.135.2022.05.26.03.39.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 26 May 2022 03:40:01 -0700 (PDT) From: Chengming Zhou To: mingo@redhat.com, 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, odin@uged.al Cc: linux-kernel@vger.kernel.org, duanxiongchun@bytedance.com, songmuchun@bytedance.com, Chengming Zhou Subject: [PATCH v3 2/2] sched/fair: optimize and simplify rq leaf_cfs_rq_list Date: Thu, 26 May 2022 18:39:29 +0800 Message-Id: <20220526103929.14976-3-zhouchengming@bytedance.com> X-Mailer: git-send-email 2.35.1 In-Reply-To: <20220526103929.14976-1-zhouchengming@bytedance.com> References: <20220526103929.14976-1-zhouchengming@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" We notice the rq leaf_cfs_rq_list has two problems when do bugfix backports and some test profiling. 1. cfs_rqs under throttled subtree could be added to the list, and make their fully decayed ancestors on the list, even though not needed. 2. #1 also make the leaf_cfs_rq_list management complex and error prone, this is the list of related bugfix so far: commit 31bc6aeaab1d ("sched/fair: Optimize update_blocked_averages()") commit fe61468b2cbc ("sched/fair: Fix enqueue_task_fair warning") commit b34cb07dde7c ("sched/fair: Fix enqueue_task_fair() warning some m= ore") commit 39f23ce07b93 ("sched/fair: Fix unthrottle_cfs_rq() for leaf_cfs_r= q list") commit 0258bdfaff5b ("sched/fair: Fix unfairness caused by missing load = decay") commit a7b359fc6a37 ("sched/fair: Correctly insert cfs_rq's to list on u= nthrottle") commit fdaba61ef8a2 ("sched/fair: Ensure that the CFS parent is added af= ter unthrottling") commit 2630cde26711 ("sched/fair: Add ancestors of unthrottled undecayed= cfs_rq") commit 31bc6aeaab1d ("sched/fair: Optimize update_blocked_averages()") delete every cfs_rq under throttled subtree from rq->leaf_cfs_rq_list, and delete the throttled_hierarchy() test in update_blocked_averages(), which optimized update_blocked_averages(). But those later bugfix add cfs_rqs under throttled subtree back to rq->leaf_cfs_rq_list again, with their fully decayed ancestors, for the integrity of rq->leaf_cfs_rq_list. This patch takes another method, skip all cfs_rqs under throttled hierarchy when list_add_leaf_cfs_rq(), to completely make cfs_rqs under throttled subtree off the leaf_cfs_rq_list. So we don't need to consider throttled related things in enqueue_entity(), unthrottle_cfs_rq() and enqueue_task_fair(), which simplify the code a lot. Also optimize update_blocked_averages() since cfs_rqs under throttled hierarchy and their ancestors won't be on the leaf_cfs_rq_list. Signed-off-by: Chengming Zhou --- v3: - fix !CONFIG_FAIR_GROUP_SCHED build error, reported by kernel test robot v2: - move throttled_hierarchy() outside list_add_leaf_cfs_rq(), suggested by Vincent. --- kernel/sched/fair.c | 81 ++++++++++++--------------------------------- 1 file changed, 22 insertions(+), 59 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index c6da204f3068..48ff4330d68a 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -3114,6 +3114,8 @@ void reweight_task(struct task_struct *p, int prio) load->inv_weight =3D sched_prio_to_wmult[prio]; } =20 +static inline int throttled_hierarchy(struct cfs_rq *cfs_rq); + #ifdef CONFIG_FAIR_GROUP_SCHED #ifdef CONFIG_SMP /* @@ -3224,8 +3226,6 @@ static long calc_group_shares(struct cfs_rq *cfs_rq) } #endif /* CONFIG_SMP */ =20 -static inline int throttled_hierarchy(struct cfs_rq *cfs_rq); - /* * Recomputes the group entity based on the current state of its group * runqueue. @@ -4338,16 +4338,11 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_= entity *se, int flags) __enqueue_entity(cfs_rq, se); se->on_rq =3D 1; =20 - /* - * When bandwidth control is enabled, cfs might have been removed - * because of a parent been throttled but cfs->nr_running > 1. Try to - * add it unconditionally. - */ - if (cfs_rq->nr_running =3D=3D 1 || cfs_bandwidth_used()) - list_add_leaf_cfs_rq(cfs_rq); - - if (cfs_rq->nr_running =3D=3D 1) + if (cfs_rq->nr_running =3D=3D 1) { check_enqueue_throttle(cfs_rq); + if (!throttled_hierarchy(cfs_rq)) + list_add_leaf_cfs_rq(cfs_rq); + } } =20 static void __clear_buddies_last(struct sched_entity *se) @@ -4962,11 +4957,18 @@ void unthrottle_cfs_rq(struct cfs_rq *cfs_rq) /* update hierarchical throttle state */ walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq); =20 - /* Nothing to run but something to decay (on_list)? Complete the branch */ if (!cfs_rq->load.weight) { - if (cfs_rq->on_list) - goto unthrottle_throttle; - return; + if (!cfs_rq->on_list) + return; + /* + * Nothing to run but something to decay (on_list)? + * Complete the branch. + */ + for_each_sched_entity(se) { + if (list_add_leaf_cfs_rq(cfs_rq_of(se))) + break; + } + goto unthrottle_throttle; } =20 task_delta =3D cfs_rq->h_nr_running; @@ -5004,31 +5006,12 @@ void unthrottle_cfs_rq(struct cfs_rq *cfs_rq) /* end evaluation on encountering a throttled cfs_rq */ if (cfs_rq_throttled(qcfs_rq)) goto unthrottle_throttle; - - /* - * One parent has been throttled and cfs_rq removed from the - * list. Add it back to not break the leaf list. - */ - if (throttled_hierarchy(qcfs_rq)) - list_add_leaf_cfs_rq(qcfs_rq); } =20 /* At this point se is NULL and we are at root level*/ add_nr_running(rq, task_delta); =20 unthrottle_throttle: - /* - * The cfs_rq_throttled() breaks in the above iteration can result in - * incomplete leaf list maintenance, resulting in triggering the - * assertion below. - */ - for_each_sched_entity(se) { - struct cfs_rq *qcfs_rq =3D cfs_rq_of(se); - - if (list_add_leaf_cfs_rq(qcfs_rq)) - break; - } - assert_list_leaf_cfs_rq(rq); =20 /* Determine whether we need to wake up potentially idle CPU: */ @@ -5683,13 +5666,6 @@ enqueue_task_fair(struct rq *rq, struct task_struct = *p, int flags) /* end evaluation on encountering a throttled cfs_rq */ if (cfs_rq_throttled(cfs_rq)) goto enqueue_throttle; - - /* - * One parent has been throttled and cfs_rq removed from the - * list. Add it back to not break the leaf list. - */ - if (throttled_hierarchy(cfs_rq)) - list_add_leaf_cfs_rq(cfs_rq); } =20 /* At this point se is NULL and we are at root level*/ @@ -5713,21 +5689,6 @@ enqueue_task_fair(struct rq *rq, struct task_struct = *p, int flags) update_overutilized_status(rq); =20 enqueue_throttle: - if (cfs_bandwidth_used()) { - /* - * When bandwidth control is enabled; the cfs_rq_throttled() - * breaks in the above iteration can result in incomplete - * leaf list maintenance, resulting in triggering the assertion - * below. - */ - for_each_sched_entity(se) { - cfs_rq =3D cfs_rq_of(se); - - if (list_add_leaf_cfs_rq(cfs_rq)) - break; - } - } - assert_list_leaf_cfs_rq(rq); =20 hrtick_update(rq); @@ -11257,9 +11218,10 @@ static inline bool vruntime_normalized(struct task= _struct *p) */ static void propagate_entity_cfs_rq(struct sched_entity *se) { - struct cfs_rq *cfs_rq; + struct cfs_rq *cfs_rq =3D cfs_rq_of(se); =20 - list_add_leaf_cfs_rq(cfs_rq_of(se)); + if (!throttled_hierarchy(cfs_rq)) + list_add_leaf_cfs_rq(cfs_rq); =20 /* Start to propagate at parent */ se =3D se->parent; @@ -11268,7 +11230,8 @@ static void propagate_entity_cfs_rq(struct sched_en= tity *se) cfs_rq =3D cfs_rq_of(se); =20 update_load_avg(cfs_rq, se, UPDATE_TG); - list_add_leaf_cfs_rq(cfs_rq); + if (!throttled_hierarchy(cfs_rq)) + list_add_leaf_cfs_rq(cfs_rq); } } #else --=20 2.36.1