linux-kernel - Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

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, 22 Sep 2010 09:12:29 -0700
From:	"H. Peter Anvin" <hpa@...or.com>
To:	Andi Kleen <andi@...stfloor.org>
CC:	jbaron@...hat.com, rostedt@...dmis.com,
	linux-kernel@...r.kernel.org, mingo@...e.hu,
	mathieu.desnoyers@...ymtl.ca, tglx@...utronix.de,
	roland@...hat.com, rth@...hat.com, mhiramat@...hat.com,
	fweisbec@...il.com, avi@...hat.com, davem@...emloft.net,
	vgoyal@...hat.com, sam@...nborg.org, tony@...eyournoodle.com,
	Andi Kleen <ak@...ux.intel.com>
Subject: Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

On 09/22/2010 03:08 AM, Andi Kleen wrote:
>
> I believe it's also much cleaner than before.
>
> I did some performance tests comparing the hash implementation
> with the binary search. This was with a moderate config x86-64
> kernel with 68 modules loaded and about 480 trace points active
> in several modules and 1340 dynamic debug statements.
>

Now, the ideal data structure for this stuff is something called a 
minimal perfect hash.  This is something that would have to be generated 
(for each module and for the monolithic kernel) at compile time -- 
presumably in modpost -- because the static generation of them is fairly 
complex.

That would provide extremely simple handling in the kernel (just do some 
shifts and a table lookup and you have your answer) and if combined with 
an AVL or red-black tree holding the module addresses it would give 
extremely fast address-to-metadata lookup, not just for this but also 
for things like exception handling.

I have used MPH's in other projects and pitched them to Linus at one 
point for exception handling.  What is clear, though, is that we should 
do the same thing for exceptions, trace points, and any other similar 
things that depend on exact PC.

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