lkml.org 
[lkml]   [2011]   [Apr]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: [PATCH] module: Use the binary search for symbols resolution
Date
On Tue,  5 Apr 2011 19:22:26 +0200, Alessio Igor Bogani <abogani@kernel.org> wrote:
> Let the linker sort the exported symbols and use the binary search for
> locate them.

OK, but why is this optional?

Also note that each_symbol() has an out-of-tree user in ksplice, so
changing the semantics to always search for a particular name might
break them.

Assuming they need it, we could rename it (so they can easily detect the
change) to search_symbol() and make it take a comparitor fn and a
"found" function.

So we want this as three patches, I think:
1) Change each_symbol() to search_symbol() as detailed above.
2) Change symbol tables to be sorted.
3) Change module code to do binary search.

That means we can tell exactly *what* breaks things in linux-next :)

Also:
> for (j = 0; j < arrsize; j++) {
> - for (i = 0; i < arr[j].stop - arr[j].start; i++)
> - if (fn(&arr[j], owner, i, data))
> +#ifdef CONFIG_SYMBOLS_BSEARCH
> + num = arr[j].stop - arr[j].start;
> + start = 0, end = num - 1, mid, result;
> + while (start <= end) {
> + mid = (start + end) / 2;
> + result = strcmp(fsa->name, arr[j].start[mid].name);
> + if (result < 0)
> + end = mid - 1;
> + else if (result > 0)
> + start = mid + 1;
> + else
> + if (fn(&arr[j], owner, mid, data))
> + return true;
> + }
> +#else

This will loop forever if rn() returns false! You want

return fn(&arr[j], owner, mid, data)

I think.

But very neat work!
Rusty.


\
 
 \ /
  Last update: 2011-04-12 05:53    [W:0.796 / U:0.036 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site