linux-kernel - Re: [PATCH v2] sched/eevdf: Prevent vlag from going out of bounds when reweight

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAB8ipk-WYVLsRi1_wnm2vF3M4RDnV1cSomb4MkJ83ef2GY0gzg@mail.gmail.com>
Date: Tue, 23 Apr 2024 11:05:20 +0800
From: Xuewen Yan <xuewen.yan94@...il.com>
To: Peter Zijlstra <peterz@...radead.org>
Cc: Xuewen Yan <xuewen.yan@...soc.com>, mingo@...hat.com, juri.lelli@...hat.com, 
	vincent.guittot@...aro.org, dietmar.eggemann@....com, rostedt@...dmis.org, 
	bsegall@...gle.com, mgorman@...e.de, bristot@...hat.com, vschneid@...hat.com, 
	yu.c.chen@...el.com, ke.wang@...soc.com, di.shen@...soc.com, 
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2] sched/eevdf: Prevent vlag from going out of bounds
 when reweight_eevdf

On Mon, Apr 22, 2024 at 11:59 PM Peter Zijlstra <peterz@...radead.org> wrote:
>
> On Mon, Apr 22, 2024 at 09:12:12PM +0800, Xuewen Yan wrote:
>
> > By adding a log to observe weight changes in reweight_entity, I found
> > that calc_group_shares() often causes new_weight to become very small:
>
> Yes, cgroups do that. But over-all that should not matter no?
>
> Specifically, the whole re-weight thing turns into a series like:
>
>             w_0   w_1         w_n-1   w_0
>         S = --- * --- * ... * ----- = ---
>             w_1   w_2          w_n    w_n
>
> Where S is our ultimate scale factor.
>
> So even if w_m (0 < m < n) is 2, it completely disappears. But yes, it
> will create a big term, which is why the initial vlag should be limited.

Okay, I understand what you mean. Even if the weight during dequeue is
very small, the weight will be eliminated during enqueue.
In this case, the necessity of the !on_rq case does not seem to be
very important.

On the other hand, the following case:
place_entity()
{
..
 5244                 load = cfs_rq->avg_load;
 5245                 if (curr && curr->on_rq)
 5246                         load += scale_load_down(curr->load.weight);
 5247
 5248                 lag *= load + scale_load_down(se->load.weight);
 5249                 if (WARN_ON_ONCE(!load))
 5250                         load = 1;
 5251                 lag = div_s64(lag, load);<<<<
..
}
reweight_eevdf()
{
..
                 if (avruntime != se->vruntime) {
 3770                 vlag = entity_lag(avruntime, se);
 3771                 vlag = div_s64(vlag * old_weight, weight); <<<<
 3772                 se->vruntime = avruntime - vlag;
 3773         }
....
}

There is no need to clamp the above two positions because these two
calculations will not theoretically cause s64 overflow?

Thanks!

>
> Notably, nice should not exceed 88761*1024 / 2, but I'm not sure I
> remember the limits (if there are any on the cgrou pmuck).
>
> But if roughly 27 bits go to weight, then vlag should not exceed 36,
> which should be well within the slice limit iirc.
>
> Also, as said before, due to integer division being truncating, the
> actual S should be smaller than the expected S due to error
> accumulation.
>
> Anyway, the things to verify are:
>
>  - the S series is complete -- missing terms will mess things up right
>    quick;
>
>  - the limits on both the weight and vlag part, their sum exceeding
>    63bit (plut 1 for sign) will also mess things up.