linux-kernel - Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched

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]

Message-ID: <20170410104725.xc2nah4ech5utqb4@hirez.programming.kicks-ass.net>
Date:   Mon, 10 Apr 2017 12:47:25 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Paul Turner <pjt@...gle.com>
Cc:     Yuyang Du <yuyang.du@...el.com>, Ingo Molnar <mingo@...nel.org>,
        LKML <linux-kernel@...r.kernel.org>,
        Benjamin Segall <bsegall@...gle.com>,
        Morten Rasmussen <morten.rasmussen@....com>,
        Vincent Guittot <vincent.guittot@...aro.org>,
        Dietmar Eggemann <dietmar.eggemann@....com>,
        Matt Fleming <matt@...eblueprint.co.uk>,
        Mike Galbraith <umgwanakikbuti@...il.com>
Subject: Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg()

On Fri, Mar 31, 2017 at 01:38:55PM +0200, Peter Zijlstra wrote:
> So here, @periods == p+1, see also c1. Yes, this is confusing [*].

> [*] hysterically p used to be off by 1, which is where the p+1 came
> from, but now periods includes it. I was thinking of doing a patch
> correcting all the comments to fully eradicate the whole +1 business.


Something like so; which also makes it obvious p == 0 is not 'right'.


--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2777,18 +2777,18 @@ static u32 __accumulate_pelt_segments(u6
 	u32 c1, c2, c3 = d3; /* y^0 == 1 */
 
 	/*
-	 * c1 = d1 y^(p+1)
+	 * c1 = d1 y^p
 	 */
 	c1 = decay_load((u64)d1, periods);
 
 	/*
-	 *             p
+	 *            p-1
 	 * c2 = 1024 \Sum y^n
 	 *            n=1
 	 *
 	 *              inf        inf
 	 *    = 1024 ( \Sum y^n - \Sum y^n - y^0 )
-	 *              n=0        n=p+1
+	 *              n=0        n=p
 	 */
 	c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
 
@@ -2808,15 +2808,15 @@ static u32 __accumulate_pelt_segments(u6
  *         |<->|<----------------->|<--->|
  * ... |---x---|------| ... |------|-----x (now)
  *
- *                                p
- * u' = (u + d1) y^(p+1) + 1024 \Sum y^n + d3 y^0
- *                               n=1
+ *                           p-1
+ * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
+ *                           n=1
  *
- *    = u y^(p+1) +				(Step 1)
+ *    = u y^p +					(Step 1)
  *
- *                          p
- *      d1 y^(p+1) + 1024 \Sum y^n + d3 y^0	(Step 2)
- *                         n=1
+ *                     p-1
+ *      d1 y^p + 1024 \Sum y^n + d3 y^0		(Step 2)
+ *                     n=1
  */
 static __always_inline u32
 accumulate_sum(u64 delta, int cpu, struct sched_avg *sa,


> > I computed all the values vs true value that the old/new computations
> > result in, and it's very close.  Absolutely it's approximately 2x off
> > the previous computation, e.g. if the old value was -15 (relative to
> > true value) than the new computation is -30.
> > 
> > This is definitely more than good enough.  If we want more precision,
> > then the correction factor of:
> >   +clamp(periods, 0, 45)
> 
> Can you do a patch with coherent comment explaining where that
> correction term comes from?

ping?