Messages in this thread | | | Date | Wed, 22 Sep 2010 16:41:01 -0400 | From | Mathieu Desnoyers <> | Subject | Re: [PATCH 2/2] Rewrite jump_label.c to use binary search |
| |
* 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
| |