linux-kernel - Re: [PATCH 06/17] sched/fair: Add lag based placement

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]

Date:   Mon, 3 Apr 2023 17:18:06 +0800
From:   Chen Yu <yu.c.chen@...el.com>
To:     Peter Zijlstra <peterz@...radead.org>
CC:     <mingo@...nel.org>, <vincent.guittot@...aro.org>,
        <linux-kernel@...r.kernel.org>, <juri.lelli@...hat.com>,
        <dietmar.eggemann@....com>, <rostedt@...dmis.org>,
        <bsegall@...gle.com>, <mgorman@...e.de>, <bristot@...hat.com>,
        <corbet@....net>, <qyousef@...alina.io>, <chris.hyser@...cle.com>,
        <patrick.bellasi@...bug.net>, <pjt@...gle.com>, <pavel@....cz>,
        <qperret@...gle.com>, <tim.c.chen@...ux.intel.com>,
        <joshdon@...gle.com>, <timj@....org>, <kprateek.nayak@....com>,
        <youssefesmat@...omium.org>, <joel@...lfernandes.org>,
        <efault@....de>
Subject: Re: [PATCH 06/17] sched/fair: Add lag based placement

On 2023-03-28 at 11:26:28 +0200, Peter Zijlstra wrote:
>  place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
[...]
>  		/*
> -		 * Halve their sleep time's effect, to allow
> -		 * for a gentler effect of sleepers:
> +		 * If we want to place a task and preserve lag, we have to
> +		 * consider the effect of the new entity on the weighted
> +		 * average and compensate for this, otherwise lag can quickly
> +		 * evaporate:
> +		 *
> +		 * l_i = V - v_i <=> v_i = V - l_i
> +		 *
> +		 * V = v_avg = W*v_avg / W
> +		 *
> +		 * V' = (W*v_avg + w_i*v_i) / (W + w_i)
If I understand correctly, V' means the avg_runtime if se_i is enqueued?
Then,

V  = (\Sum w_j*v_j) / W

V' = (\Sum w_j*v_j + w_i*v_i) / (W + w_i)

Not sure how W*v_avg equals to Sum w_j*v_j ?

> +		 *    = (W*v_avg + w_i(v_avg - l_i)) / (W + w_i)
> +		 *    = v_avg + w_i*l_i/(W + w_i)
v_avg - w_i*l_i/(W + w_i) ?
> +		 *
> +		 * l_i' = V' - v_i = v_avg + w_i*l_i/(W + w_i) - (v_avg - l)
> +		 *      = l_i - w_i*l_i/(W + w_i)
> +		 *
> +		 * l_i = (W + w_i) * l_i' / W
>  		 */
[...]
> -		if (sched_feat(GENTLE_FAIR_SLEEPERS))
> -			thresh >>= 1;
> +		load = cfs_rq->avg_load;
> +		if (curr && curr->on_rq)
> +			load += curr->load.weight;
> +
> +		lag *= load + se->load.weight;
> +		if (WARN_ON_ONCE(!load))
> +			load = 1;
> +		lag = div_s64(lag, load);
>  
Should we calculate
l_i' = l_i * w / (W + w_i) instead of calculating l_i above? I thought we want to adjust
the lag(before enqueue) based on the new weight(after enqueued)


[I will start to run some benchmarks today.]

thanks,
Chenyu