linux-kernel - [PATCH] sched/eevdf: Improve the clarity of the lag-based placement comments

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

Message-Id: <4c99af2c8d9b35ccdab66163c3ac256e3e95d5c0.1723802710.git.rocking@linux.alibaba.com>
Date: Fri, 16 Aug 2024 18:17:30 +0800
From: Peng Wang <rocking@...ux.alibaba.com>
To: mingo@...hat.com,
	peterz@...radead.org,
	juri.lelli@...hat.com,
	vincent.guittot@...aro.org,
	dietmar.eggemann@....com,
	rostedt@...dmis.org,
	bsegall@...gle.com,
	mgorman@...e.de,
	vschneid@...hat.com
Cc: linux-kernel@...r.kernel.org
Subject: [PATCH] sched/eevdf: Improve the clarity of the lag-based placement comments

In the original comments, the derivation starts with preserving v_i to
calculate V' and uses the equation v_i = V - vl_i. However, tasks might
have migrated from other queues, which means that the relationship with
this queue's V does not necessarily hold.

The new derivation is based on keeping vl_i unchanged and derives from the
post-enqueue perspective, thereby avoiding the previous assumption.

Signed-off-by: Peng Wang <rocking@...ux.alibaba.com>
---
 kernel/sched/fair.c | 56 +++++++++++++++------------------------------
 1 file changed, 19 insertions(+), 37 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 9057584ec06d..2bfae2ca2bb6 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5196,56 +5196,38 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 		lag = se->vlag;
 
 		/*
-		 * If we want to place a task and preserve lag, we have to
+		 * If we want to place a task i 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:
+		 *		Avg-Load    VRuntime    Avg-VRuntime	Vlag
+		 *	before	  W	    v_i		  V		vl_i
+		 *	after	  W+w_i	    v_i'	  V'		vl_i
 		 *
-		 *   lag_i = S - s_i = w_i * (V - v_i)
+		 * We want to preserve lag, so vl_i wil not change:
 		 *
-		 * To avoid the 'w_i' term all over the place, we only track
-		 * the virtual lag:
+		 *   vl_i = V' - v_i'
+		 *   ==> v_i' = V' - vl_i			(1)
 		 *
-		 *   vl_i = V - v_i <=> v_i = V - vl_i
+		 * We take V' to be the weighted average of all v'
 		 *
-		 * And we take V to be the weighted average of all v:
+		 *   V' = (W*V + w_i*v_i') / (W + w_i)
+		 *   ==> (W + w_i)*V' = W*V + w_i*v_i'		(2)
 		 *
-		 *   V = (\Sum w_j*v_j) / W
+		 * by using (1) & (2) we obtain:
 		 *
-		 * Where W is: \Sum w_j
+		 *   (W + w_i)*V' = W*V + w_i*(V' - vl_i)
+		 *   ==>     W*V' = W*V -w_i*vl_i
+		 *   ==>       V' = V - w_i*vl_i/W		(3)
 		 *
-		 * Then, the weighted average after adding an entity with lag
-		 * vl_i is given by:
+		 * by using (1) & (3) we obtain:
 		 *
-		 *   V' = (\Sum w_j*v_j + w_i*v_i) / (W + w_i)
-		 *      = (W*V + w_i*(V - vl_i)) / (W + w_i)
-		 *      = (W*V + w_i*V - w_i*vl_i) / (W + w_i)
-		 *      = (V*(W + w_i) - w_i*l) / (W + w_i)
-		 *      = V - w_i*vl_i / (W + w_i)
+		 *   v_i' = V - w_i*vl_i/W - vl_i
+		 *        = V - (w_i*vl_i/W + vl_i)
+		 *        = V - (w_i*vl_i + W*vl_i)/W
+		 *        = V - vl_i*(w_i + W)/W
 		 *
-		 * And the actual lag after adding an entity with vl_i is:
-		 *
-		 *   vl'_i = V' - v_i
-		 *         = V - w_i*vl_i / (W + w_i) - (V - vl_i)
-		 *         = vl_i - w_i*vl_i / (W + w_i)
-		 *
-		 * Which is strictly less than vl_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 vl'_i to get the vl_i
-		 * we need to use such that the lag after placement is the lag
-		 * we computed before dequeue.
-		 *
-		 *   vl'_i = vl_i - w_i*vl_i / (W + w_i)
-		 *         = ((W + w_i)*vl_i - w_i*vl_i) / (W + w_i)
-		 *
-		 *   (W + w_i)*vl'_i = (W + w_i)*vl_i - w_i*vl_i
-		 *                   = W*vl_i
-		 *
-		 *   vl_i = (W + w_i)*vl'_i / W
 		 */
 		load = cfs_rq->avg_load;
 		if (curr && curr->on_rq)
-- 
2.27.0