linux-kernel - Re: Discrepancy between comments for sched_find_first

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:	Mon, 29 Mar 2010 12:25:02 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Matt Turner <mattst88@...il.com>
Cc:	LKML <linux-kernel@...r.kernel.org>, linux-alpha@...r.kernel.org,
	Ingo Molnar <mingo@...e.hu>
Subject: Re: Discrepancy between comments for sched_find_first_bit

On Sun, 2010-03-28 at 23:37 -0400, Matt Turner wrote:
> include/asm-generic/bitops/sched.h says
> /*
>  * Every architecture must define this function. It's the fastest
>  * way of searching a 100-bit bitmap.  It's guaranteed that at least
>  * one of the 100 bits is cleared.
>  */
> 
> arch/alpha/include/asm/bitops.h says
> /*
>  * Every architecture must define this function. It's the fastest
>  * way of searching a 140-bit bitmap where the first 100 bits are
>  * unlikely to be set. It's guaranteed that at least one of the 140
>  * bits is set.
>  */
> 
> Is the guarantee that one of the first 100-bits set (and that the last
> 40 are useless?), or 140-bits? If it's just the first 100 bits we care
> about, then the alpha version needs to be fixed.
> 
> I'm just checking this out, because gcc produces horrendous code for
> sched_find_first_bit on alpha. I rewrote it in assembly and it's
> better than 4 times faster.
> 
> Also, is it even worth optimizing that function? It looks like it's
> only used in kernel/sched_rt.c.

(might help if you CC the scheduler people on scheduler functions :-)

Right, so it used to be 140 bits with the old O(1) scheduler, currently
(as you noted) sched_rt is the only user left and will therefore only
care about the first 100 bits.

As it stands I think it might still make sense to optimize this as for
rt loads it still on a hot path.

As to the 100 vs 140 length, would it really make much of difference to
shorten the implementation to 100? If not I'd leave it at 140.

Ingo, any comments?

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