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:   Thu, 6 Apr 2023 11:03:41 +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-04-05 at 11:47:20 +0200, Peter Zijlstra wrote:
> On Mon, Apr 03, 2023 at 05:18:06PM +0800, Chen Yu wrote:
> > 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
> 
> multiply by W on both sides to get:
> 
>   V*W = \Sum w_j*v_j
> 
> > 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 ?
> 
>  V := v_avg
>
I see, thanks for the explanation. 
> (yeah, I should clean up this stuff, already said to Josh I would)
> 
> > > +		 *    = (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) ?
> 
> Yup -- seems typing is hard :-)
> 
> > > +		 *
> > > +		 * 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)
> 
> We want to ensure the lag after placement is the lag we got before
> dequeue.
> 
> I've updated the comment to read like so:
> 
> 		/*
> 		 * 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.
> 		 *
> 		 * Lag is defined as:
> 		 *
> 		 *   l_i = V - v_i <=> v_i = V - l_i
> 		 *
> 		 * And we take V to be the weighted average of all v:
> 		 *
> 		 *   V = (\Sum w_j*v_j) / W
> 		 *
> 		 * Where W is: \Sum w_j
> 		 *
> 		 * Then, the weighted average after adding an entity with lag
> 		 * l_i is given by:
> 		 *
> 		 *   V' = (\Sum w_j*v_j + w_i*v_i) / (W + w_i)
> 		 *      = (W*V + w_i*(V - l_i)) / (W + w_i)
> 		 *      = (W*V + w_i*V - w_i*l_i) / (W + w_i)
> 		 *      = (V*(W + w_i) - w_i*l) / (W + w_i)
small typo  w_i*l -> w_i*l_i
> 		 *      = V - w_i*l_i / (W + w_i)
> 		 *
> 		 * And the actual lag after adding an entity with l_i is:
> 		 *
> 		 *   l'_i = V' - v_i
> 		 *        = V - w_i*l_i / (W + w_i) - (V - l_i)
> 		 *        = l_i - w_i*l_i / (W + w_i)
> 		 *
> 		 * Which is strictly less than l_i. So in order to preserve lag
> 		 * we should inflate the lag before placement such that the
> 		 * effective lag after placement comes out right.
> 		 *
> 		 * As such, invert the above relation for l'_i to get the l_i
> 		 * we need to use such that the lag after placement is the lag
> 		 * we computed before dequeue.
> 		 *
> 		 *   l'_i = l_i - w_i*l_i / (W + w_i)
> 		 *        = ((W + w_i)*l_i - w_i*l_i) / (W + w_i)
> 		 *
> 		 *   (W + w_i)*l'_i = (W + w_i)*l_i - w_i*l_i
> 		 *                  = W*l_i
> 		 *
> 		 *   l_i = (W + w_i)*l'_i / W
> 		 */
Got it, thanks! This is very clear.

thanks,
Chenyu