linux-kernel - Re: [PATCH] sched/fair.c: Fix the calculation method of 'lag'

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

Message-ID: <20240424085533.GS40213@noisy.programming.kicks-ass.net>
Date: Thu, 25 Apr 2024 19:44:59 +0800
From: <hupu@...o.com>
To: <peterz@...radead.org>
CC: <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>,
	<linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] sched/fair.c: Fix the calculation method of 'lag'

> > From: hupu <hupu@...o.com>
> >
> > I think the 'lag' calculation here is inaccurate.
> >
> > Assume that delta needs to be subtracted from v_i to ensure that the
> > vlag of task i after placement is the same as before.
>
> Why ?!? v_i is the unkown, it makes no sense to complicate things by
> adding extra unknowns.
>
> > At this time, the
> > vlag of task i after placement should be:
> > vl'_i = V' - (v_i - delta)
>
> But but but, you can't have V' without knowing v_i.
>

Thank you for your patient guidance. I overlooked a important fact that
v_i is unknown in the process of proof. Below is the complete proof
process, and it turns out that you are correct.

(I put the formula in a comment block to prevent the email system from
removing the spaces in the formula. This preserves the formatting of the
formula and makes it look more readable.)

The following formula is valid BEFORE placing task i.

/*
 *      \Sum (w_j * v_j)
 * V = ------------------
 *          \Sum w_j
 *
 * 
 * W = \Sum w_j
 * 
 * 
 * vl_i = V - v_i
 */


The following formula is valid AFTER placing task i.
/* 
 *        \Sum (w_j * v_j) + (w_i * v_i')
 * V' =  --------------------------------
 *              \Sum w_j + w_i
 * 
 * 
 * W' = \Sum w_j + w_i
 * 
 * 
 * vl_i' = V' - v_i'
 */

We hope to preserve the vlag which was calculated during the last
dequeue operation. So the proof process should be as follows:

/*
 * vl_i = vl_i'
 * 
 * =>
 * vl_i = V' - v_i'
 * 
 * =>
 *          \Sum (w_j * v_j) + (w_i * v_i')
 * vl_i = -------------------------------- - v_i'
 *                \Sum w_j + w_i
 * 
 * 
 *      \Sum (w_j * v_j) + (w_i * v_i') - v_i' * (\Sum w_j + w_i)
 *  = -------------------------------------------------------------
 *                           \Sum w_j + w_i
 * 
 * 
 *      \Sum (w_j * v_j) + (w_i * v_i') - (v_i' * \Sum w_j) - (v_i' *
 *      w_i)
 *  =
 *  ---------------------------------------------------------------------
 *                            \Sum w_j + w_i
 * 
 * 
 *      \Sum (w_j * v_j) - v_i' * \Sum w_j
 *  = --------------------------------------
 *              \Sum w_j + w_i
 * 
 * 
 *       V * \Sum w_j - v_i' * \Sum w_j
 *  = ------------------------------------
 *              \Sum w_j + w_i
 * 
 * 
 * =>
 * vl_i * (\Sum w_j + w_i) = V * \Sum w_j - v_i' * \Sum w_j
 * 
 * =>
 *              vl_i * (\Sum w_j + w_i)
 * v_i' = V - ---------------------------
 *                   \Sum w_j
 * 
 * 
 *              W + w_i
 *      = V - ----------- * vl_i
 *                 W
 */
 
-- 
2.17.1