Messages in this thread | | | Date | Wed, 23 Sep 2009 19:08:00 +0100 | From | Alan Jenkins <> | Subject | Re: [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 > >
| |