> 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, 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 -- To unsubscribe from this list: send the line "unsubscribe linux-modules" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
