Re: [PATCH 0/2] Use generic binary search function

[Alan Jenkins <alan-jenkins@tuffmail.co.uk>]

Tim Abbott wrote:
>> The builtin symbol tables are now sorted, so we can use a binary
>> search.
>>     
>
> Hi Alan,
>
> There a large number hand-coded binary searches in the kernel (run
> "git grep search | grep binary" to find many of them).  Since getting
> binary searches right is difficult, I've been meaning to submit a
> patch adding a lib/bsearch.c for some time now, so that we only have
> to get binary search right in one place.
>
> This patch series contains a generic binary search implementation as
> well as something converting your module.c patch to use it.  I haven't
> had a chance to boot-test yet,

You might want to wait.  I found some weirdness in my patches - as if my 
bsearch is backwards but the tables are also being reversed.

Whatever the problem, it endorses the idea of having one known good 
bsearch function :-).

>  but this should give you a sense of
> what this is going to look like.  To me, you take some somewhat
> complex code and replace it with some very straightforward code.
>
> This generic binary search implementation comes from Ksplice.  It has
> the same basic API as the C library bsearch() function.  Ksplice uses
> it in half a dozen places with 4 different comparison functions, and I
> think our code is substantially cleaner because of this.
>
> I don't claim that this is a perfect implementation of binary search,
> though it is reasonably well tested.  My theory is that it is about as
> good as all the hand-coded copies all over the kernel, and we can
> optimize it to perfection later.
>
> Tim Abbott (2):
>   lib: Add generic binary search function to the kernel.
>   module: use bsearch in find_symbol_in_kernel_section.
>
>  include/linux/bsearch.h |    9 ++++++++
>  kernel/module.c         |   34 +++++++++++++----------------
>  lib/Makefile            |    2 +-
>  lib/bsearch.c           |   53 +++++++++++++++++++++++++++++++++++++++++++++++
>  4 files changed, 78 insertions(+), 20 deletions(-)
>  create mode 100644 include/linux/bsearch.h
>  create mode 100644 lib/bsearch.c
>
>