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

[Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>]

* H. Peter Anvin (hpa@zytor.com) wrote:
> On 09/22/2010 12:43 PM, Mathieu Desnoyers wrote:
> > * H. Peter Anvin (hpa@zytor.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