Re: [PATCH] module: Use the binary search for symbols resolution

[Rusty Russell <rusty@rustcorp.com.au>]

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.