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: <1209754539.6929.7.camel@lappy>
Date:	Fri, 02 May 2008 20:55:39 +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>,
	Anton Blanchard <anton@....ibm.com>,
	Benjamin Herrenschmidt <benh@...nel.crashing.org>
Subject: Re: questions on calc_delta_mine() in sched.c

On Fri, 2008-05-02 at 13:46 -0500, Joel Schopp wrote:
> > This one builds and... boots
> 
> I'll try to test in on my end.
> 
> > +	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) {
> 
> Yep, got to get rid of unlikely.
> 
> > +		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;
> 
> I bet just dividing by weight + 1 unconditionally would be cheaper than 
> doing the test and shouldn't skew results too badly.

Yeah... probably - getting rid of that one case where it can happen is
on my todo list somewhere.

> > +		rq->lw_cache[rq->lw_cache_idx] = *lw;
> > +		rq->lw_cache_idx++;
> > +		rq->lw_cache_idx %= ARRAY_SIZE(rq->lw_cache);
> > +	}
> > + got_inv:
> 
> Doctor, I think the cure is worse than the disease.   I'd expect that even 
> if all these extra loads hit cache they should together be more expensive 
> than the divide they save.   Not that I have any better solutions myself.

Probably, but since you seemed in benchmarking mood I thought you might
as well give it a go ;-)

> I think a patch to get rid of unlikely and to change these two div64_64 to 
> 0s should be pushed up.  Not sure what we do about the divide.

Ok, I'll stick such a patch in to to-mingo queue ;-)

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