linux-kernel - Re: [PATCH] sched/fair: set the se->vlag strictly following the paper

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CAKfTPtBUJa4A2V3XR8EwYVPxiY=ENZr1=Jg5R3E75r5XnrnRPg@mail.gmail.com>
Date: Thu, 19 Jun 2025 15:53:10 +0200
From: Vincent Guittot <vincent.guittot@...aro.org>
To: Huang Shijie <shijie@...amperecomputing.com>
Cc: mingo@...hat.com, peterz@...radead.org, patches@...erecomputing.com, 
	cl@...ux.com, yang@...amperecomputing.com, juri.lelli@...hat.com, 
	dietmar.eggemann@....com, rostedt@...dmis.org, bsegall@...gle.com, 
	mgorman@...e.de, vschneid@...hat.com, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] sched/fair: set the se->vlag strictly following the paper

On Thu, 19 Jun 2025 at 05:20, Huang Shijie
<shijie@...amperecomputing.com> wrote:
>
> From the paper, the lag should follow the limit:
>      -r_max < lag < max(r_max, q)
>
> But current code makes the lag follow the limit:
>      -max(r_max, q) < lag < max(r_max, q)
>
> This patch introduces limit_hi/limit_lo/r_max, and
> make the lag follow the paper strictly.

We don't strictly follow the paper. Typically, paper assumes that a
task will not run more than its slice r before deciding which task is
the next to run. But this is not our case as we must wait for a sched
event like the tick before picking next  task which can be longer than
the slice r

Side note, we don't have a fix definition of the quantum q which is
something between 0 and a tick (and even more currently with run to
parity) as we wait for the next the tick to pick another task

This means that a task can run a full tick period even if its slice is
shorter than the tick period

>
> Signed-off-by: Huang Shijie <shijie@...amperecomputing.com>
> ---
>  kernel/sched/fair.c | 9 ++++++---
>  1 file changed, 6 insertions(+), 3 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 83157de5b808..102d263df330 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -694,14 +694,17 @@ u64 avg_vruntime(struct cfs_rq *cfs_rq)
>   */
>  static void update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
>  {
> -       s64 vlag, limit;
> +       s64 vlag, limit_hi, limit_lo, r_max;
>
>         WARN_ON_ONCE(!se->on_rq);
>
>         vlag = avg_vruntime(cfs_rq) - se->vruntime;
> -       limit = calc_delta_fair(max_t(u64, 2*se->slice, TICK_NSEC), se);
> +       r_max = 2 * se->slice;
>
> -       se->vlag = clamp(vlag, -limit, limit);
> +       limit_hi = calc_delta_fair(max_t(u64, r_max, TICK_NSEC), se);
> +       limit_lo = calc_delta_fair(r_max, se);
> +
> +       se->vlag = clamp(vlag, -limit_lo, limit_hi);
>  }
>
>  /*
> --
> 2.40.1
>