Received: by 2002:a05:6602:2086:0:0:0:0 with SMTP id a6csp4637335ioa; Wed, 27 Apr 2022 08:01:14 -0700 (PDT) X-Google-Smtp-Source: ABdhPJxPdgZeR4Ojjg7edtG5b4KsbNfxjSrNVDShwCZixOY9ms+wPaUeekUMbKPo2Vb91g74wfqu X-Received: by 2002:a63:5949:0:b0:3ab:77b8:24a5 with SMTP id j9-20020a635949000000b003ab77b824a5mr10069600pgm.545.1651071674672; Wed, 27 Apr 2022 08:01:14 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1651071674; cv=none; d=google.com; s=arc-20160816; b=QvhGIHHAZlnGYsjvrrgkbGZtxkdqHtBPTpRvgDahR9O3ZiMFkjhmkkCDYC8Xu2RVNN 4f2GMDi2BBHRqk+sUKAxuFCZsoReTpKWMQq2eLw63/Xru66xiQoWVkniceAYaqeYqT8Y ikAsE5O3kqhJtYV2MBjYa7u2BjM3/DjTjM/Xw9IT5CWjFL6mH+pc+DPY0eAG5ndKRvZD RsrNnGjQmXQIUfdoSDeadFvryETwD3KkBVZMtCUYW7jn1ugkb9bcbp36LA43qT+Z9ked DzAwph55NpAlyI3VspU1/LVxSlfUBWOV3QleeOhhv1ptzYTAefdWPvetnMoeIVgaoDYF DCFQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=skztW+5fTAJcU+WOEHXrbnrlPAlOKgRTRSuXA+De7EQ=; b=RDRLy61awB/x2SKw/Y4cgOh9ENlnmS562KQEkd//80zDYfxqOYLrQQUrSuNXslKmX1 7t/IyMQe5+v3kYFSATfGs6TUByJwUYIiUfkaFsBrPFSKm7jTg6fHfhOtIrc32FL3Oxho NztCZ2pHV8hRpNLLvRdJOasMxoUCZ5JdL1l/fC4pfB8ISiadliutrqsBuId52BxX/Kqe AKsautaGCVsDdrly73+AOgmhOWghIAECOBKCeoKKMH6c+3wPQeBCOehEce6sE9WclsWa TRMCeCpSOM9L6ykhn/sXe5MHUVUoY2cj6GOuIOP2r4R4q2bbNTpBLlPfFwJ1WUK87bI4 sVjw== ARC-Authentication-Results: i=1; mx.google.com; spf=softfail (google.com: domain of transitioning linux-kernel-owner@vger.kernel.org does not designate 23.128.96.19 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=arm.com Return-Path: Received: from lindbergh.monkeyblade.net (lindbergh.monkeyblade.net. [23.128.96.19]) by mx.google.com with ESMTPS id w1-20020a170902e88100b0015908285c86si1936530plg.447.2022.04.27.08.01.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 27 Apr 2022 08:01:14 -0700 (PDT) Received-SPF: softfail (google.com: domain of transitioning linux-kernel-owner@vger.kernel.org does not designate 23.128.96.19 as permitted sender) client-ip=23.128.96.19; Authentication-Results: mx.google.com; spf=softfail (google.com: domain of transitioning linux-kernel-owner@vger.kernel.org does not designate 23.128.96.19 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=arm.com Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by lindbergh.monkeyblade.net (Postfix) with ESMTP id 9194B25C4F; Wed, 27 Apr 2022 07:34:00 -0700 (PDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238132AbiD0Ogm (ORCPT + 99 others); Wed, 27 Apr 2022 10:36:42 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40714 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238075AbiD0Ogb (ORCPT ); Wed, 27 Apr 2022 10:36:31 -0400 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by lindbergh.monkeyblade.net (Postfix) with ESMTP id DA05A5FD1 for ; Wed, 27 Apr 2022 07:33:18 -0700 (PDT) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 6AF18ED1; Wed, 27 Apr 2022 07:33:18 -0700 (PDT) Received: from localhost.localdomain (unknown [10.57.44.232]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id B94663F5A1; Wed, 27 Apr 2022 07:33:16 -0700 (PDT) From: Vincent Donnefort To: peterz@infradead.org, mingo@redhat.com, vincent.guittot@linaro.org Cc: linux-kernel@vger.kernel.org, dietmar.eggemann@arm.com, morten.rasmussen@arm.com, chris.redpath@arm.com, qperret@google.com, Vincent Donnefort Subject: [PATCH v7 2/7] sched/fair: Decay task PELT values during wakeup migration Date: Wed, 27 Apr 2022 15:32:59 +0100 Message-Id: <20220427143304.3950488-3-vincent.donnefort@arm.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220427143304.3950488-1-vincent.donnefort@arm.com> References: <20220427143304.3950488-1-vincent.donnefort@arm.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RDNS_NONE, SPF_HELO_NONE autolearn=no 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: X-Mailing-List: linux-kernel@vger.kernel.org Before being migrated to a new CPU, a task sees its PELT values synchronized with rq last_update_time. Once done, that same task will also have its sched_avg last_update_time reset. This means the time between the migration and the last clock update (B) will not be accounted for in util_avg and a discontinuity will appear. This issue is amplified by the PELT clock scaling. If the clock hasn't been updated while the CPU is idle, clock_pelt will not be aligned with clock_task and that time (A) will be also lost. ---------|----- A -----|-----------|------- B -----|> clock_pelt clock_task clock now This is especially problematic for asymmetric CPU capacity systems which need stable util_avg signals for task placement and energy estimation. Ideally, this problem would be solved by updating the runqueue clocks before the migration. But that would require taking the runqueue lock which is quite expensive [1]. Instead estimate the missing time and update the task util_avg with that value: A + B = clock_task - clock_pelt + sched_clock_cpu() - clock sched_clock_cpu() is a costly function. Limit the usage to the case where the source CPU is idle as we know this is when the clock is having the biggest risk of being outdated. Neither clock_task, clock_pelt nor clock can be accessed without the runqueue lock. We then need to store those values in a timestamp variable which can be accessed during the migration. rq's enter_idle will give the wall-clock time when the rq went idle. We have then: B = sched_clock_cpu() - rq->enter_idle. Then, to catch-up the PELT clock scaling (A), two cases: * !CFS_BANDWIDTH: We can simply use clock_task(). This value is stored in rq's clock_pelt_idle, before the rq enters idle. The estimated time is then: rq->clock_pelt_idle + sched_clock_cpu() - rq->enter_idle. * CFS_BANDWIDTH: We can't catch-up with clock_task because of the throttled_clock_task_time offset. cfs_rq's clock_pelt_idle is then giving the PELT clock when the cfs_rq becomes idle. This gives: A = rq->clock_pelt_idle - cfs_rq->clock_pelt_idle And gives the following estimated time: cfs_rq->last_update_time + rq->clock_pelt_idle - cfs_rq->clock_pelt_idle + (A) sched_clock_cpu() - rq->enter_idle (B) The (B) part of the missing time is however an estimation that doesn't take into account IRQ and Paravirt time. [1] https://lore.kernel.org/all/20190709115759.10451-1-chris.redpath@arm.com/ Signed-off-by: Vincent Donnefort diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index abd1feeec0c2..9cd506dc682c 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -3694,6 +3694,57 @@ static inline void add_tg_cfs_propagate(struct cfs_rq *cfs_rq, long runnable_sum #endif /* CONFIG_FAIR_GROUP_SCHED */ +#ifdef CONFIG_NO_HZ_COMMON +static inline void migrate_se_pelt_lag(struct sched_entity *se) +{ + struct cfs_rq *cfs_rq; + struct rq *rq; + bool is_idle; + u64 now; + + cfs_rq = cfs_rq_of(se); + rq = rq_of(cfs_rq); + + rcu_read_lock(); + is_idle = is_idle_task(rcu_dereference(rq->curr)); + rcu_read_unlock(); + + /* + * The lag estimation comes with a cost we don't want to pay all the + * time. Hence, limiting to the case where the source CPU is idle and + * we know we are at the greatest risk to have an outdated clock. + */ + if (!is_idle) + return; + + /* + * estimated "now" is: + * last_update_time + + * PELT scaling (rq->clock_pelt_idle - cfs_rq->clock_pelt_idle) + + * rq clock lag (sched_clock_cpu() - rq->enter_idle) + * + * The PELT scaling contribution is always 0 when !CFS_BANDWIDTH. + * (see clock_pelt = clock_task in _update_idle_rq_clock_pelt()) + */ +#ifdef CONFIG_CFS_BANDWIDTH + now = u64_u32_load(cfs_rq->clock_pelt_idle); + /* The clock has been stopped for throttling */ + if (now == U64_MAX) + return; + + now = u64_u32_load(rq->clock_pelt_idle) - now; + now += cfs_rq_last_update_time(cfs_rq); +#else + now = u64_u32_load(rq->clock_pelt_idle); +#endif + now += sched_clock_cpu(cpu_of(rq)) - u64_u32_load(rq->enter_idle); + + __update_load_avg_blocked_se(now, se); +} +#else +static void migrate_se_pelt_lag(struct sched_entity *se) {} +#endif + /** * update_cfs_rq_load_avg - update the cfs_rq's load/util averages * @now: current time, as per cfs_rq_clock_pelt() @@ -4429,6 +4480,9 @@ dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) */ if ((flags & (DEQUEUE_SAVE | DEQUEUE_MOVE)) != DEQUEUE_SAVE) update_min_vruntime(cfs_rq); + + if (cfs_rq->nr_running == 0) + update_idle_cfs_rq_clock_pelt(cfs_rq); } /* @@ -6946,6 +7000,8 @@ static void detach_entity_cfs_rq(struct sched_entity *se); */ static void migrate_task_rq_fair(struct task_struct *p, int new_cpu) { + struct sched_entity *se = &p->se; + /* * As blocked tasks retain absolute vruntime the migration needs to * deal with this by subtracting the old and adding the new @@ -6953,7 +7009,6 @@ static void migrate_task_rq_fair(struct task_struct *p, int new_cpu) * the task on the new runqueue. */ if (READ_ONCE(p->__state) == TASK_WAKING) { - struct sched_entity *se = &p->se; struct cfs_rq *cfs_rq = cfs_rq_of(se); se->vruntime -= u64_u32_load(cfs_rq->min_vruntime); @@ -6965,25 +7020,29 @@ static void migrate_task_rq_fair(struct task_struct *p, int new_cpu) * rq->lock and can modify state directly. */ lockdep_assert_rq_held(task_rq(p)); - detach_entity_cfs_rq(&p->se); + detach_entity_cfs_rq(se); } else { + remove_entity_load_avg(se); + /* - * We are supposed to update the task to "current" time, then - * its up to date and ready to go to new CPU/cfs_rq. But we - * have difficulty in getting what current time is, so simply - * throw away the out-of-date time. This will result in the - * wakee task is less decayed, but giving the wakee more load - * sounds not bad. + * Here, the task's PELT values have been updated according to + * the current rq's clock. But if that clock hasn't been + * updated in a while, a substantial idle time will be missed, + * leading to an inflation after wake-up on the new rq. + * + * Estimate the missing time from the cfs_rq last_update_time + * and update sched_avg to improve the PELT continuity after + * migration. */ - remove_entity_load_avg(&p->se); + migrate_se_pelt_lag(se); } /* Tell new CPU we are migrated */ - p->se.avg.last_update_time = 0; + se->avg.last_update_time = 0; /* We have migrated, no longer consider this task hot */ - p->se.exec_start = 0; + se->exec_start = 0; update_scan_period(p, new_cpu); } @@ -8149,6 +8208,10 @@ static bool __update_blocked_fair(struct rq *rq, bool *done) if (update_cfs_rq_load_avg(cfs_rq_clock_pelt(cfs_rq), cfs_rq)) { update_tg_load_avg(cfs_rq); + /* sync clock_pelt_idle with last update */ + if (cfs_rq->nr_running == 0) + update_idle_cfs_rq_clock_pelt(cfs_rq); + if (cfs_rq == &rq->cfs) decayed = true; } diff --git a/kernel/sched/pelt.h b/kernel/sched/pelt.h index 4ff2ed4f8fa1..6b39e07b2919 100644 --- a/kernel/sched/pelt.h +++ b/kernel/sched/pelt.h @@ -61,6 +61,23 @@ static inline void cfs_se_util_change(struct sched_avg *avg) WRITE_ONCE(avg->util_est.enqueued, enqueued); } +static inline u64 rq_clock_pelt(struct rq *rq) +{ + lockdep_assert_rq_held(rq); + assert_clock_updated(rq); + + return rq->clock_pelt - rq->lost_idle_time; +} + +/* The rq is idle, we can sync to clock_task */ +static inline void _update_idle_rq_clock_pelt(struct rq *rq) +{ + rq->clock_pelt = rq_clock_task(rq); + + u64_u32_store(rq->enter_idle, rq_clock(rq)); + u64_u32_store(rq->clock_pelt_idle, rq_clock_pelt(rq)); +} + /* * The clock_pelt scales the time to reflect the effective amount of * computation done during the running delta time but then sync back to @@ -76,8 +93,7 @@ static inline void cfs_se_util_change(struct sched_avg *avg) static inline void update_rq_clock_pelt(struct rq *rq, s64 delta) { if (unlikely(is_idle_task(rq->curr))) { - /* The rq is idle, we can sync to clock_task */ - rq->clock_pelt = rq_clock_task(rq); + _update_idle_rq_clock_pelt(rq); return; } @@ -130,17 +146,20 @@ static inline void update_idle_rq_clock_pelt(struct rq *rq) */ if (util_sum >= divider) rq->lost_idle_time += rq_clock_task(rq) - rq->clock_pelt; + + _update_idle_rq_clock_pelt(rq); } -static inline u64 rq_clock_pelt(struct rq *rq) +#ifdef CONFIG_CFS_BANDWIDTH +static inline void update_idle_cfs_rq_clock_pelt(struct cfs_rq *cfs_rq) { - lockdep_assert_rq_held(rq); - assert_clock_updated(rq); - - return rq->clock_pelt - rq->lost_idle_time; + if (unlikely(cfs_rq->throttle_count)) + u64_u32_store(cfs_rq->clock_pelt_idle, U64_MAX); + else + u64_u32_store(cfs_rq->clock_pelt_idle, + rq_clock_pelt(rq_of(cfs_rq))); } -#ifdef CONFIG_CFS_BANDWIDTH /* rq->task_clock normalized against any time this cfs_rq has spent throttled */ static inline u64 cfs_rq_clock_pelt(struct cfs_rq *cfs_rq) { @@ -150,6 +169,7 @@ static inline u64 cfs_rq_clock_pelt(struct cfs_rq *cfs_rq) return rq_clock_pelt(rq_of(cfs_rq)) - cfs_rq->throttled_clock_pelt_time; } #else +static inline void update_idle_cfs_rq_clock_pelt(struct cfs_rq *cfs_rq) { } static inline u64 cfs_rq_clock_pelt(struct cfs_rq *cfs_rq) { return rq_clock_pelt(rq_of(cfs_rq)); @@ -204,6 +224,7 @@ update_rq_clock_pelt(struct rq *rq, s64 delta) { } static inline void update_idle_rq_clock_pelt(struct rq *rq) { } +static inline void update_idle_cfs_rq_clock_pelt(struct cfs_rq *cfs_rq) { } #endif diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index e2cf6e48b165..07014e8cbae2 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -641,6 +641,10 @@ struct cfs_rq { int runtime_enabled; s64 runtime_remaining; + u64 clock_pelt_idle; +#ifndef CONFIG_64BIT + u64 clock_pelt_idle_copy; +#endif u64 throttled_clock; u64 throttled_clock_pelt; u64 throttled_clock_pelt_time; @@ -1013,6 +1017,12 @@ struct rq { u64 clock_task ____cacheline_aligned; u64 clock_pelt; unsigned long lost_idle_time; + u64 clock_pelt_idle; + u64 enter_idle; +#ifndef CONFIG_64BIT + u64 clock_pelt_idle_copy; + u64 enter_idle_copy; +#endif atomic_t nr_iowait; -- 2.25.1