Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.36 as permitted sender) client-ip=23.128.96.36;
Date:   Wed, 25 Oct 2023 15:19:10 +0800
From:   Chen Yu <yu.c.chen@intel.com>
To:     Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
CC:     Dietmar Eggemann <dietmar.eggemann@arm.com>,
        Peter Zijlstra <peterz@infradead.org>,
        <linux-kernel@vger.kernel.org>, Ingo Molnar <mingo@redhat.com>,
        Valentin Schneider <vschneid@redhat.com>,
        Steven Rostedt <rostedt@goodmis.org>,
        Ben Segall <bsegall@google.com>, Mel Gorman <mgorman@suse.de>,
        Daniel Bristot de Oliveira <bristot@redhat.com>,
        "Vincent Guittot" <vincent.guittot@linaro.org>,
        Juri Lelli <juri.lelli@redhat.com>,
        Swapnil Sapkal <Swapnil.Sapkal@amd.com>,
        Aaron Lu <aaron.lu@intel.com>,
        "Tim Chen" <tim.c.chen@intel.com>,
        K Prateek Nayak <kprateek.nayak@amd.com>,
        "Gautham R . Shenoy" <gautham.shenoy@amd.com>, <x86@kernel.org>
Subject: Re: [RFC PATCH v2 1/2] sched/fair: Introduce UTIL_FITS_CAPACITY
 feature (v2)
Message-ID: <ZTjBbgiSXj6bWE2O@chenyu5-mobl2.ccr.corp.intel.com>
References: <20231019160523.1582101-1-mathieu.desnoyers@efficios.com>
 <20231019160523.1582101-2-mathieu.desnoyers@efficios.com>
 <f40522de-b71d-4848-8aa3-5b87d38bb847@arm.com>
 <c79ac631-61c7-4953-a657-74047a264029@efficios.com>
 <ZTdf0529DL51pj8m@chenyu5-mobl2.ccr.corp.intel.com>
 <ae8412cb-fd78-4e3e-b51a-ee290fd076bd@efficios.com>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <ae8412cb-fd78-4e3e-b51a-ee290fd076bd@efficios.com>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?fTFtaiggM1Igw4xF8opyNZamWnwa3639+v4FJ6zOaz9xgCZC6G+GCx43y3cC?=
 =?us-ascii?Q?EW/HEYTsNDCunPy/KpeM2Pq9m1Aqf9V63YF94gcKRa7IGNtLQyqzdBevOCrP?=
 =?us-ascii?Q?91c9cyXPmSO8cQTKJJg1OV6UDjabQ2E+ICpJdb5uAapVEt2Ofe/HT+tfXGaj?=
 =?us-ascii?Q?GqzABIHXgIdxfK8m4Ixdkr4kJ3z1SfypGmKo7cOiRdXWAPZI2sR3wn9lOq3d?=
 =?us-ascii?Q?75exMREVRhdYqi2erhZdDXbhx0G70H3t5LZ0wBE7zVwUGNUzruRFHaCW/wTT?=
 =?us-ascii?Q?14/pPfTGLEnqI/qw/kKibL2Bh5a3Dg4fhYu93ON++CHbgQeiYZXM1Df18XIl?=
 =?us-ascii?Q?+2OM6XZZxZQLpYjEIklJyrAYBNjgTLVuZuj6xFL1bpdxbboKm2XuWTBkrS9P?=
 =?us-ascii?Q?Bfb2Q2z4MA8Rf40GCaWrOsg4zVlQgenBCAHTRbgbaK519dZYAyT+5d6BQdKz?=
 =?us-ascii?Q?Cef/iV+RNumc1dkiFtYUtpl0gXnbOVwMkG/+1YcZjYN8xJxZiuf3zUrZD/6R?=
 =?us-ascii?Q?+qCA4Ckrlj/7FBDK0wQoWVrtzD92RNQ1rACsG5WI1mkezANBgUHNlG0pqfHa?=
 =?us-ascii?Q?eYmW4RofDN9Ho75Nu+qdoqwULbOIc5cQRyaqQsiuKzl/zkW+tPYAiVO6EFSh?=
 =?us-ascii?Q?qWe5jIAH+bZeGVkIx6sfNRsuHhKOdAGcb4I4ZEoIB5T3pxChLtGwAeJj0lQm?=
 =?us-ascii?Q?q1ZnhS4BSdhDT2c4dOA2cAe7g/0ANB38HLV9ch0rdsBBD0uKdQCcPPeYMe8z?=
 =?us-ascii?Q?/rH6VxysqS8vjil2w8LPxuyS9x0wqvQUUPmRF0CydzVQagZdlfYeZ1ihGysv?=
 =?us-ascii?Q?USv2PQbJoP1FJ87VZ1VGg1tL0fD3rigP1gANBVTLDW8ZaFPjd1oM5zXz9yYr?=
 =?us-ascii?Q?q2felvj1LhDwI3sJleFaFHaQYMkUdrgt48zeeL3YJqv8WmJXX70EaRqs2num?=
 =?us-ascii?Q?9UnSiCejZ9JPA+kaFCablbBWTVy89n+Cecv2Peq/LwBHlKK203B2EIgFMExw?=
 =?us-ascii?Q?sbP2IxGC54LJ91No+aD/mZRiyVfpzN6TL5Skdj/kThiS+fLxerWAm13BI2/n?=
 =?us-ascii?Q?SYh9W/QsQ/sXfu/yO/9Khh27xjiRp86JKMbEf7LGX4hD0s36cQl0rea+xMdU?=
 =?us-ascii?Q?CTVhqgd/FiHBBce9yuIlIdQ95DWg95/vLCTM5U303MJeX3pzkE2YoUbuC9GG?=
 =?us-ascii?Q?ASrMwPv+8g04itoSIZEMvt59GZKMR97knM+cNsu402R/vmZpz7z6S9qR3JnC?=
 =?us-ascii?Q?RPzdw0H4yVwwnyfdyNL1+TTSPVoTqjZpsI6fnQSMqwLAnqbxzpxmFfNnVGhb?=
 =?us-ascii?Q?SB3nnUXKPqtEdje7YrzORj6wjes+qHYKxUEA6vQfMBGONyFTIgoAUDjDa3y6?=
 =?us-ascii?Q?hMzj1MLcK84hBpvlmpXQiYv7QQAqAzxfmf11fzaIwzNopCH0NKFCT3TaWmGG?=
 =?us-ascii?Q?eWrqkYnLPUTFS/WYKKWeQRbCZguOuG52dMho3wEcBUpzIRvJ603j8f6XWvCN?=
 =?us-ascii?Q?oMMRw7clILh497X/+pF958TS+xR/zIXy1GPKv6G951gjJNcHV8KMtgd9dt2z?=
 =?us-ascii?Q?lGzpZO1Yghhf1orFiLylhu86inJd+KXoMp7CpdPF?=
X-MS-Exchange-CrossTenant-Network-Message-Id: a613e7b1-98b8-49c8-9a84-08dbd52ab91f
X-MS-Exchange-CrossTenant-AuthSource: MN0PR11MB6206.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 25 Oct 2023 07:19:27.6182
 (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: DmSskxZpTBwFkkqRxHtUB8ihEtKTRHP2ljGtFS5DvuxC1jge31AfPHGic3CBgAv1qJ5JbIzPKH3qevChDiFDXw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SA3PR11MB7626
X-OriginatorOrg: intel.com
X-Spam-Status: No, score=-0.9 required=5.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,
	MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=unavailable
	autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on pete.vger.email
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 (pete.vger.email [0.0.0.0]); Wed, 25 Oct 2023 00:20:53 -0700 (PDT)

On 2023-10-24 at 10:49:37 -0400, Mathieu Desnoyers wrote:
> On 2023-10-24 02:10, Chen Yu wrote:
> > On 2023-10-23 at 11:04:49 -0400, Mathieu Desnoyers wrote:
> > > On 2023-10-23 10:11, Dietmar Eggemann wrote:
> > > > On 19/10/2023 18:05, Mathieu Desnoyers wrote:
> > > 
> > > [...]
> > > > > +static unsigned long scale_rt_capacity(int cpu);
> > > > > +
> > > > > +/*
> > > > > + * Returns true if adding the task utilization to the estimated
> > > > > + * utilization of the runnable tasks on @cpu does not exceed the
> > > > > + * capacity of @cpu.
> > > > > + *
> > > > > + * This considers only the utilization of _runnable_ tasks on the @cpu
> > > > > + * runqueue, excluding blocked and sleeping tasks. This is achieved by
> > > > > + * using the runqueue util_est.enqueued.
> > > > > + */
> > > > > +static inline bool task_fits_remaining_cpu_capacity(unsigned long task_util,
> > > > > +						    int cpu)
> > > > 
> > > > Or like find_energy_efficient_cpu() (feec(), used in
> > > > Energy-Aware-Scheduling (EAS)) which uses cpu_util(cpu, p, cpu, 0) to get:
> > > > 
> > > >     max(util_avg(CPU + p), util_est(CPU + p))
> > > 
> > > I've tried using cpu_util(), but unfortunately anything that considers
> > > blocked/sleeping tasks in its utilization total does not work for my
> > > use-case.
> > > 
> > >  From cpu_util():
> > > 
> > >   * CPU utilization is the sum of running time of runnable tasks plus the
> > >   * recent utilization of currently non-runnable tasks on that CPU.
> > > 
> > 
> > I thought cpu_util() indicates the utilization decay sum of task that was once
> > "running" on this CPU, but will not sum up the "util/load" of the blocked/sleeping
> > task?
> > 
> > accumulate_sum()
> >      /* only the running task's util will be sum up */
> >      if (running)
> >         sa->util_sum += contrib << SCHED_CAPACITY_SHIFT;
> > 
> > WRITE_ONCE(sa->util_avg, sa->util_sum / divider);
> 
> The accumulation into the cfs_rq->avg.util_sum indeed only happens when the task
> is running, which means that the task does not actively contribute to increment
> the util_sum when it is blocked/sleeping.
> 
> However, when the task is blocked/sleeping, the task is still attached to the
> runqueue, and therefore its historic util_sum still contributes to the cfs_rq
> util_sum/util_avg. This completely differs from what happens when the task is
> migrated to a different runqueue, in which case its util_sum contribution is
> entirely removed from the cfs_rq util_sum:
> 
> static void
> enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
> {
> [...]
>         update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH)
> [...]
> 
> static void
> dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
> {
> [...]
>         if (entity_is_task(se) && task_on_rq_migrating(task_of(se)))
>                 action |= DO_DETACH;
> [...]
> 
> static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
> {
> [...]
>         if (!se->avg.last_update_time && (flags & DO_ATTACH)) {
> 
>                 /*
>                  * DO_ATTACH means we're here from enqueue_entity().
>                  * !last_update_time means we've passed through
>                  * migrate_task_rq_fair() indicating we migrated.
>                  *
>                  * IOW we're enqueueing a task on a new CPU.
>                  */
>                 attach_entity_load_avg(cfs_rq, se);
>                 update_tg_load_avg(cfs_rq);
> 
>         } else if (flags & DO_DETACH) {
>                 /*
>                  * DO_DETACH means we're here from dequeue_entity()
>                  * and we are migrating task out of the CPU.
>                  */
>                 detach_entity_load_avg(cfs_rq, se);
>                 update_tg_load_avg(cfs_rq);
> [...]
> 
> In comparison, util_est_enqueue()/util_est_dequeue() are called from enqueue_task_fair()
> and dequeue_task_fair(), which include blocked/sleeping tasks scenarios. Therefore, util_est
> only considers runnable tasks in its cfs_rq->avg.util_est.enqueued.
>
> The current rq utilization total used for rq selection should not include historic
> utilization of all blocked/sleeping tasks, because we are taking a decision to bring
> back a recently blocked/sleeping task onto a runqueue at that point. Considering
> the historic util_sum from the set of other blocked/sleeping tasks still attached to that
> runqueue in the current utilization mistakenly makes the rq selection think that the rq is
> busier than it really is.
> 

Thanks for the description in detail, it is very helpful! Now I understand that using cpu_util()
could overestimate the busyness of the CPU in UTIL_FITS_CAPACITY.

> I suspect that cpu_util_without() is an half-successful attempt at solving this by removing
> the task p from the considered utilization, but it does not take into account scenarios where many
> other tasks happen to be blocked/sleeping as well.

Agree, those non-migrated tasks could contribute to cfs_rq's util_avg.

thanks,
Chenyu