linux-kernel - [PATCH 3/4] sched/fair: Modify accumulated sums for load/util averages

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, 11 Apr 2016 06:36:04 +0800
From:	Yuyang Du <yuyang.du@...el.com>
To:	peterz@...radead.org, mingo@...nel.org,
	linux-kernel@...r.kernel.org
Cc:	bsegall@...gle.com, pjt@...gle.com, morten.rasmussen@....com,
	vincent.guittot@...aro.org, dietmar.eggemann@....com,
	juri.lelli@....com, Yuyang Du <yuyang.du@...el.com>
Subject: [PATCH 3/4] sched/fair: Modify accumulated sums for load/util averages

After we dropped the incomplete period, the current period should be
a complete "past" period, since all period boundaries, in the past
or in the future, are predetermined.

With incomplete current period:

         |    |    |    |    |
       -------------------*
                        ^ ^
                        | |
                      current

With this patch:

         |    |    |    |    |
       -------------------*
                   ^    ^
                   |    |
                   current

So, the precomputed sums in __accumulated_sum_N[] and
__accumulated_sum_N32[] should be updated accordingly.

Update the script to generate the constants:

print " #:      inv_N    sum_N"
print "-----------------------"
y = (0.5)**(1/32.0)
x = 2**32
xx = 1024
for i in range(0, 32):
	if i == 0:
		x = x-1
	else:
		x = x*y
		xx = int(xx*y + 1024)
	print "%2d: %#x %8d" % (i, int(x), int(xx))

print " #:  sum_N32"
print "------------"
xxx = xx
for i in range(0, 11):
	if i == 0:
		xxx = xx
	else:
		xxx = xxx/2 + xx
	print "%2d: %8d" % (i, xxx)

Signed-off-by: Yuyang Du <yuyang.du@...el.com>
---
 kernel/sched/fair.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 68273e8..49e9f1a 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -666,7 +666,7 @@ static unsigned long task_h_load(struct task_struct *p);
  */
 #define LOAD_AVG_PERIOD 32
 #define LOAD_AVG_MAX 47742 /* maximum possible load avg */
-#define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_AVG_MAX */
+#define LOAD_AVG_MAX_N 347 /* number of full periods to produce LOAD_AVG_MAX */
 
 /* Give new sched_entity start runnable values to heavy its load in infant time */
 void init_entity_runnable_average(struct sched_entity *se)
@@ -2591,9 +2591,9 @@ static const u32 __decay_inv_multiply_N[] = {
  * over-estimates when re-combining.
  */
 static const u32 __accumulated_sum_N[] = {
-	    0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103,
-	 9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082,
-	17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
+	    0, 1024, 2026, 3006, 3965, 4904, 5822, 6721, 7600, 8461, 9303,
+	10127,10933,11722,12494,13250,13990,14714,15422,16115,16793,17457,
+	18106,18742,19364,19973,20569,21152,21722,22280,22826,23360,23883,
 };
 
 /*
@@ -2601,8 +2601,8 @@ static const u32 __accumulated_sum_N[] = {
  * lower integers.
  */
 static const u32 __accumulated_sum_N32[] = {
-	    0, 23371, 35056, 40899, 43820, 45281,
-	46011, 46376, 46559, 46650, 46696, 46719,
+	    0, 23883, 35824, 41795, 44780, 46273,
+	47019, 47392, 47579, 47672, 47719, 47742,
 };
 
 /*
-- 
2.1.4