linux-kernel - [RFC PATCH 2/9 v4] sched: Precise accumulated time and acount runnable number in update_entity_runnable

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:	Wed, 25 Jun 2014 08:36:01 +0800
From:	Yuyang Du <yuyang.du@...el.com>
To:	mingo@...hat.com, peterz@...radead.org, rafael.j.wysocki@...el.com,
	linux-kernel@...r.kernel.org, linux-pm@...r.kernel.org
Cc:	arjan.van.de.ven@...el.com, len.brown@...el.com,
	alan.cox@...el.com, mark.gross@...el.com, morten.rasmussen@....com,
	vincent.guittot@...aro.org, dietmar.eggemann@....com,
	rajeev.d.muralidhar@...el.com, vishwesh.m.rudramuni@...el.com,
	nicole.chalhoub@...el.com, ajaya.durg@...el.com,
	harinarayanan.seshadri@...el.com, jacob.jun.pan@...ux.intel.com,
	Yuyang Du <yuyang.du@...el.com>
Subject: [RFC PATCH 2/9 v4] sched: Precise accumulated time and acount runnable number in update_entity_runnable_avg

The current amount of time already accumulated against next period is
determined by:

	delta_w = sa->runnable_avg_period % 1024

Considering the runnable_avg_period is the sum of an infinite series, this
method looks gross, even the error would be no more than 1024 (~1ms).
But precisely accounting this is not hard, just use a variable period_contrib
to record it.

The current runnable argument is either 1 or 0, indicating whether this entity
is runnable or not. In order to account the number of runnables as well, change
how runnable_avg_sum is accumulated.

Signed-off-by: Yuyang Du <yuyang.du@...el.com>
---
 include/linux/sched.h |    1 +
 kernel/sched/fair.c   |   12 ++++++++----
 2 files changed, 9 insertions(+), 4 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 306f4f0..1b1997d 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1074,6 +1074,7 @@ struct sched_avg {
 	 * choices of y < 1-2^(-32)*1024.
 	 */
 	u32 runnable_avg_sum, runnable_avg_period;
+	u32 period_contrib;
 	u64 last_runnable_update;
 	s64 decay_count;
 	unsigned long load_avg_contrib;
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 1a2d04f..e914e32 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2294,10 +2294,12 @@ static __always_inline int __update_entity_runnable_avg(u64 now,
 	sa->last_runnable_update = now;
 
 	/* delta_w is the amount already accumulated against our next period */
-	delta_w = sa->runnable_avg_period % 1024;
+	delta_w = sa->period_contrib;
 	if (delta + delta_w >= 1024) {
 		/* period roll-over */
 		decayed = 1;
+		/* how much left for next period will start over, we don't know yet */
+		sa->period_contrib = 0;
 
 		/*
 		 * Now that we know we're crossing a period boundary, figure
@@ -2306,7 +2308,7 @@ static __always_inline int __update_entity_runnable_avg(u64 now,
 		 */
 		delta_w = 1024 - delta_w;
 		if (runnable)
-			sa->runnable_avg_sum += delta_w;
+			sa->runnable_avg_sum += runnable * delta_w;
 		sa->runnable_avg_period += delta_w;
 
 		delta -= delta_w;
@@ -2323,15 +2325,17 @@ static __always_inline int __update_entity_runnable_avg(u64 now,
 		/* Efficiently calculate \sum (1..n_period) 1024*y^i */
 		runnable_contrib = __compute_runnable_contrib(periods);
 		if (runnable)
-			sa->runnable_avg_sum += runnable_contrib;
+			sa->runnable_avg_sum += runnable * runnable_contrib;
 		sa->runnable_avg_period += runnable_contrib;
 	}
 
 	/* Remainder of delta accrued against u_0` */
 	if (runnable)
-		sa->runnable_avg_sum += delta;
+		sa->runnable_avg_sum += runnable * delta;
 	sa->runnable_avg_period += delta;
 
+	sa->period_contrib += delta;
+
 	return decayed;
 }
 
-- 
1.7.9.5

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/