linux-kernel - [PATCH] sched: fair: Improve PELT decay

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: <20170310202341.11449-1-joelaf@google.com>
Date:   Fri, 10 Mar 2017 12:23:41 -0800
From:   Joel Fernandes <joelaf@...gle.com>
To:     linux-kernel@...r.kernel.org
Cc:     Joel Fernandes <joelaf@...gle.com>, Paul Turner <pjt@...gle.com>,
        Dietmar Eggemann <dietmar.eggemann@....com>,
        Juri Lelli <Juri.Lelli@....com>,
        Patrick Bellasi <patrick.bellasi@....com>,
        Peter Zijlstra <peterz@...radead.org>,
        Ingo Molnar <mingo@...hat.com>
Subject: [PATCH] sched: fair: Improve PELT decay_load calculation comments

The PELT decay_load comments are a bit confusing, first of all
the 1/2^N should be (1/2)^N so that the reader doesn't get confused.
Secondly, the y^N splitting into a 2-part decay factor deserves
a better explanation. This patch improves the comments.

Cc: Paul Turner <pjt@...gle.com>
Cc: Dietmar Eggemann <dietmar.eggemann@....com>
Cc: Juri Lelli <Juri.Lelli@....com>
Cc: Patrick Bellasi <patrick.bellasi@....com>
Cc: Peter Zijlstra <peterz@...radead.org>
Signed-off-by: Joel Fernandes <joelaf@...gle.com>
---
 kernel/sched/fair.c | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 6559d197e08a..1e1f2d77751e 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2761,11 +2761,15 @@ static __always_inline u64 decay_load(u64 val, u64 n)
 	local_n = n;
 
 	/*
-	 * As y^PERIOD = 1/2, we can combine
-	 *    y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
-	 * With a look-up table which covers y^n (n<PERIOD)
-	 *
-	 * To achieve constant time decay_load.
+	 * As y^PERIOD = 1/2, we can decay the load by 1/2
+	 * for n/PERIOD number of PERIOD sized instances. Then
+	 * we decay by the remaining windows in the final PERIOD,
+	 * that is n%PERIOD. In other words, the decay factor
+	 * y^N in terms of PERIOD becomes:
+	 *    y^n = (1/2)^(n/PERIOD) * y^(n%PERIOD).
+	 * Since now we only need to compute powers of y where
+	 * n < PERIOD, we use a look-up table for y^N (N<PERIOD).
+	 * This helps achieve constant time decay_load.
 	 */
 	if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
 		val >>= local_n / LOAD_AVG_PERIOD;
-- 
2.12.0.246.ga2ecc84866-goog