lkml.org 
[lkml]   [2009]   [Sep]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH 0/2] Use generic binary search function
    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
    >
    >



    \
     
     \ /
      Last update: 2009-09-23 20:11    [W:0.026 / U:0.324 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site