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 16:41:01 -0400
From:	Mathieu Desnoyers <mathieu.desnoyers@...ymtl.ca>
To:	"H. Peter Anvin" <hpa@...or.com>
Cc:	Andi Kleen <andi@...stfloor.org>, jbaron@...hat.com,
	rostedt@...dmis.com, linux-kernel@...r.kernel.org, mingo@...e.hu,
	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

* H. Peter Anvin (hpa@...or.com) wrote:
> On 09/22/2010 12:43 PM, Mathieu Desnoyers wrote:
> > * H. Peter Anvin (hpa@...or.com) wrote:
> >> On 09/22/2010 03:08 AM, Andi Kleen wrote:
> > 
> > That's a very interesting idea, which applies very well to exception
> > handlers, but tracepoints and static jumps suffer from the problem that
> > there are many possible instances of the same key.
> > 
> > Tracepoints use a lookup by tracepoint name. Static jumps use a lookup
> > by associated variable address (but this variable can be associated with
> > many instances, e.g. in the case of static inline functions, or just
> > when the same variable is used to control many instances of static
> > jumps).
> > 
> > But maybe we could find a way to do an initial sort phase, so the
> > perfect hash could point to the first entry corresponding to the looked
> > up key ?
> > 
> 
> In the case of multiple instances of the same key you want the perfect
> hash to point to the cluster of solutions -- a list.  Since this is by
> simply be an array.

Yep, and sorting the section seems like a very natural way to create
these arrays. So to summarize:

- We add a post-linking step to core image and module build in
  modpost.c.
- This step accesses exception tables, tracepoint and static jump
  sections.
  - Both tracepoint and static jump need to be sorted.
  - For each of the 3 sections, a perfect hash is computed (creation
    must have the property to always succeed). The perfect hash creation
    should only take into account the first entry of duplicate keys.
  - Each of these perfect hash would translate into C code that would
    need to be compiled in a post-link phase.
  - Then we can link the perfect hash objects with the rest of the code,
    filling in one symbol per considered section (function pointer to
    the perfect hash function) and setting function pointers in struct
    module for modules.

I'm mostly writing this down as food for thoughts, since my own
implementation time is currently focused on other things.

Thanks,

Mathieu

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
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/