linux-kernel - Re: questions on calc_delta

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: <1209733807.6929.0.camel@lappy>
Date:	Fri, 02 May 2008 15:10:07 +0200
From:	Peter Zijlstra <a.p.zijlstra@...llo.nl>
To:	Joel Schopp <jschopp@...tin.ibm.com>
Cc:	Ingo Molnar <mingo@...e.hu>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: questions on calc_delta_mine() in sched.c

On Fri, 2008-05-02 at 14:30 +0200, Peter Zijlstra wrote: 
> On Fri, 2008-05-02 at 14:14 +0200, Peter Zijlstra wrote:
> 
> > And, no sadly I have no ideas on how to get rid of it ;-/
> 
> Well, not quite true - I've once thought about a small cache of recently
> computed inverse values. Esp for say a ping-pong scenario you end up
> re-computing basically the same values over and over again.
> 
> Maybe something like this (fully untested):

This one builds and... boots


Signed-off-by: Peter Zijlstra <a.p.zijlstra@...llo.nl>
---
 kernel/sched.c |   27 +++++++++++++++++++++++----
 1 file changed, 23 insertions(+), 4 deletions(-)

Index: linux-2.6-2/kernel/sched.c
===================================================================
--- linux-2.6-2.orig/kernel/sched.c
+++ linux-2.6-2/kernel/sched.c
@@ -537,6 +537,9 @@ struct rq {
 	unsigned long nr_load_updates;
 	u64 nr_switches;
 
+	struct load_weight lw_cache[4];
+	int lw_cache_idx;
+
 	struct cfs_rq cfs;
 	struct rt_rq rt;
 
@@ -1438,8 +1441,24 @@ calc_delta_mine(unsigned long delta_exec
 {
 	u64 tmp;
 
-	if (unlikely(!lw->inv_weight))
-		lw->inv_weight = (WMULT_CONST-lw->weight/2) / (lw->weight+1);
+	if (!lw->inv_weight) {
+		struct rq *rq = cpu_rq(smp_processor_id());
+		unsigned long weight = lw->weight;
+		int i;
+
+		for (i = 0; i < ARRAY_SIZE(rq->lw_cache); i++) {
+			if (rq->lw_cache[i].weight == weight)
+				lw->inv_weight = rq->lw_cache[i].inv_weight;
+			goto got_inv;
+		}
+		if (unlikely(!weight))
+			weight++;
+		lw->inv_weight = 1 + (WMULT_CONST - weight/2) / weight;
+		rq->lw_cache[rq->lw_cache_idx] = *lw;
+		rq->lw_cache_idx++;
+		rq->lw_cache_idx %= ARRAY_SIZE(rq->lw_cache);
+	}
+ got_inv:
 
 	tmp = (u64)delta_exec * weight;
 	/*
@@ -8025,7 +8044,7 @@ static void init_tg_cfs_entry(struct tas
 
 	se->my_q = cfs_rq;
 	se->load.weight = tg->shares;
-	se->load.inv_weight = div64_64(1ULL<<32, se->load.weight);
+	se->load.inv_weight = 0;
 	se->parent = parent;
 }
 #endif
@@ -8692,7 +8711,7 @@ static void __set_se_shares(struct sched
 		dequeue_entity(cfs_rq, se, 0);
 
 	se->load.weight = shares;
-	se->load.inv_weight = div64_64((1ULL<<32), shares);
+	se->load.inv_weight = 0;
 
 	if (on_rq)
 		enqueue_entity(cfs_rq, se, 0);


--
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/