linux-kernel - Re: [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 18:14:04 +0100
From:	Dietmar Eggemann <dietmar.eggemann@....com>
To:	Yuyang Du <yuyang.du@...el.com>, 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, juri.lelli@....com
Subject: Re: [PATCH 3/4] sched/fair: Modify accumulated sums for load/util
 averages

On 10/04/16 23:36, Yuyang Du wrote:
> 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))
>

So since with this patch series, we always operate on period boundaries
you want to add 1024 instead of 1024*y (1024 * 0.5^(1/32) = 1002) for
the most recent period in the past?

Paul Turner's pelt program could be adapted like this:

diff --git a/pelt.c b/pelt.c
index b36194e8bb9c..3c6b42e88c2d 100644
--- a/pelt.c
+++ b/pelt.c
@@ -39,8 +39,8 @@ void calc_yn_sum(int n)
        printf("sum y^n\n");
        printf("   %8s  %8s %8s\n", "exact", "floor", "error");
        for (i = 1; i <= n; i++) {
-               sum = (y * sum + y * 1024);
-               sum_fl = floor(y * sum_fl+ y * 1024);
+               sum = (y * sum + 1024);
+               sum_fl = floor(y * sum_fl + 1024);
                printf("%2d: %8.0f  %8.0f %8.0f\n", i, sum, sum_fl,
                        sum_fl - sum);
        }

to achieve this.

$ ./pelt

sum y^n
      exact     *floor*    error
 1:     1024      1024        0
 2:     2026      2026       -0
...
31:    23371     23360      -11
32:    23894     23883      -11

> 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,
>  };
>  
>  /*
>