linux-kernel - [PATCH v2] sched/fair: Make PELT signal more accurate

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: <20170818235026.618-1-joelaf@google.com>
Date:   Fri, 18 Aug 2017 16:50:26 -0700
From:   Joel Fernandes <joelaf@...gle.com>
To:     linux-kernel@...r.kernel.org
Cc:     Joel Fernandes <joelaf@...gle.com>,
        Vincent Guittot <vincent.guittot@...aro.org>,
        Peter Zijlstra <peterz@...radead.org>,
        Juri Lelli <juri.lelli@....com>,
        Brendan Jackman <brendan.jackman@....com>,
        Dietmar Eggeman <dietmar.eggemann@....com>,
        kernel-team@...roid.com, Ingo Molnar <mingo@...hat.com>
Subject: [PATCH v2] sched/fair: Make PELT signal more accurate

The PELT signal (sa->load_avg and sa->util_avg) are not updated if the amount
accumulated during a single update doesn't cross a period boundary. This is
fine in cases where the amount accrued is much smaller than the size of a
single PELT window (1ms) however if the amount accrued is high then the
relative error (calculated against what the actual signal would be had we
updated the averages) can be high - as much 2% in my testing. On plotting
signals, I found that there are errors especially high when we update just
before the period boundary is hit. These errors can be significantly reduced if
we update the averages more often.

Inorder to fix this, this patch does the average update by also checking how
much time has elapsed since the last update and update the averages if it has
been long enough (as a threshold I chose 512us).

In order to compare the signals with/without the patch I created a synthetic
test (20ms runtime, 100ms period) and analyzed the signals and created a report
on the analysis data/plots and histograms both with and without the fix:
http://www.linuxinternals.org/misc/pelt-error-v4.pdf

With the patch, the error in the signal is significantly reduced, during
testing I found that 512us was a good choice. With this we ensure there are
atmost 2 updates per-window to the averages. Previous revisions chose 128 and
caused around 4% regression with unixbench. This version doesn't have such
regression. The tradeoff is slight overhead for the reduction in error.

Here's the unixbench shell8 test result for 2 runs:

Without: 9157.9, 9134.6
With: 9103.2, 9082

I also ran the hackbench-perf LKP test, total time:
With: 183.03 , Without: 183.12

Cc: Vincent Guittot <vincent.guittot@...aro.org>
Cc: Peter Zijlstra <peterz@...radead.org>
Cc: Juri Lelli <juri.lelli@....com>
Cc: Brendan Jackman <brendan.jackman@....com>
Cc: Dietmar Eggeman <dietmar.eggemann@....com>
Cc: kernel-team@...roid.com
Signed-off-by: Joel Fernandes <joelaf@...gle.com>
---
 kernel/sched/fair.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 40a89f415db0..4f61e8f1d63a 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3163,6 +3163,7 @@ ___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
 		  unsigned long load, unsigned long runnable, int running)
 {
 	u64 delta;
+	int periods;

 	delta = now - sa->last_update_time;
 	/*
@@ -3201,9 +3202,12 @@ ___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
 	 * accrues by two steps:
 	 *
 	 * Step 1: accumulate *_sum since last_update_time. If we haven't
-	 * crossed period boundaries, finish.
+	 * crossed period boundaries and the time since last update is small
+	 * enough, we're done.
 	 */
-	if (!accumulate_sum(delta, cpu, sa, load, runnable, running))
+	periods = accumulate_sum(delta, cpu, sa, load, runnable, running);
+
+	if (!periods && delta < 512)
 		return 0;

 	return 1;
-- 
2.14.1.480.gb18f417b89-goog