From cd263e2cbcc3b5b3217fcbb88a0d474136152261 Mon Sep 17 00:00:00 2001 From: Tim Abbott Date: Sat, 7 Nov 2009 21:03:58 +0000 Subject: lib: Add generic binary search function to the kernel. There a large number hand-coded binary searches in the kernel (run "git grep search | grep binary" to find many of them). Since in my experience, hand-coding binary searches can be error-prone, it seems worth cleaning this up by providing a generic binary search function. 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. Signed-off-by: Tim Abbott Signed-off-by: Alan Jenkins Signed-off-by: Rusty Russell --- lib/Makefile | 2 +- lib/bsearch.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 54 insertions(+), 1 deletion(-) create mode 100644 lib/bsearch.c (limited to 'lib') diff --git a/lib/Makefile b/lib/Makefile index 2e78277eff9d..fb60af165607 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \ - string_helpers.o gcd.o + string_helpers.o gcd.o bsearch.o ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG diff --git a/lib/bsearch.c b/lib/bsearch.c new file mode 100644 index 000000000000..4297c980a635 --- /dev/null +++ b/lib/bsearch.c @@ -0,0 +1,53 @@ +/* + * A generic implementation of binary search for the Linux kernel + * + * Copyright (C) 2008-2009 Ksplice, Inc. + * Author: Tim Abbott + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; version 2. + */ + +#include +#include + +/* + * bsearch - binary search an array of elements + * @key: pointer to item being searched for + * @base: pointer to data to sort + * @num: number of elements + * @size: size of each element + * @cmp: pointer to comparison function + * + * This function does a binary search on the given array. The + * contents of the array should already be in ascending sorted order + * under the provided comparison function. + * + * Note that the key need not have the same type as the elements in + * the array, e.g. key could be a string and the comparison function + * could compare the string with the struct's name field. However, if + * the key and elements in the array are of the same type, you can use + * the same comparison function for both sort() and bsearch(). + */ +void *bsearch(const void *key, const void *base, size_t num, size_t size, + int (*cmp)(const void *key, const void *elt)) +{ + int start = 0, end = num - 1, mid, result; + if (num == 0) + return NULL; + + while (start <= end) { + mid = (start + end) / 2; + result = cmp(key, base + mid * size); + if (result < 0) + end = mid - 1; + else if (result > 0) + start = mid + 1; + else + return (void *)base + mid * size; + } + + return NULL; +} +EXPORT_SYMBOL(bsearch); -- cgit v1.2.3 From 9c19b171a3db79cd1b8a8bdb70a6bcc9bc230891 Mon Sep 17 00:00:00 2001 From: Alan Jenkins Date: Sat, 7 Nov 2009 21:03:59 +0000 Subject: lib: bsearch - remove redundant special case for arrays of size 0 > On Thu, 24 Sep 2009, Rusty Russell wrote: > >> The if (num == 0) line is superfluous. On 9/27/09, Tim Abbott wrote: > > You are quite right. Signed-off-by: Alan Jenkins Signed-off-by: Rusty Russell --- lib/bsearch.c | 2 -- 1 file changed, 2 deletions(-) (limited to 'lib') diff --git a/lib/bsearch.c b/lib/bsearch.c index 4297c980a635..2e70664bdcda 100644 --- a/lib/bsearch.c +++ b/lib/bsearch.c @@ -34,8 +34,6 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size, int (*cmp)(const void *key, const void *elt)) { int start = 0, end = num - 1, mid, result; - if (num == 0) - return NULL; while (start <= end) { mid = (start + end) / 2; -- cgit v1.2.3 From 0621af54a37b78ca4b80ca811d11b8dfc26a0511 Mon Sep 17 00:00:00 2001 From: André Goddard Rosa Date: Tue, 10 Nov 2009 13:00:24 -0200 Subject: bsearch: avoid unneeded decrement arithmetic MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: André Goddard Rosa Signed-off-by: Rusty Russell --- lib/bsearch.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/bsearch.c b/lib/bsearch.c index 2e70664bdcda..33cbba6b7a7c 100644 --- a/lib/bsearch.c +++ b/lib/bsearch.c @@ -33,13 +33,13 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size, int (*cmp)(const void *key, const void *elt)) { - int start = 0, end = num - 1, mid, result; + int start = 0, end = num, mid, result; - while (start <= end) { + while (start < end) { mid = (start + end) / 2; result = cmp(key, base + mid * size); if (result < 0) - end = mid - 1; + end = mid; else if (result > 0) start = mid + 1; else -- cgit v1.2.3 From dbc16ef98e5d5d8e1114d420e81be36ba080b0d9 Mon Sep 17 00:00:00 2001 From: André Goddard Rosa Date: Tue, 10 Nov 2009 13:00:25 -0200 Subject: bsearch: prevent overflow when computing middle comparison element MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit It's really difficult to occur in practice because the sum of the lower and higher limits must overflow an int variable, but it can occur when working with large arrays. We'd better safe than sorry by avoiding this overflow situation when computing the middle element for comparison. See: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582 The program below demonstrates the issue: $ ./a.out (glibc) Element is at the last position (patched) Element is at the last position Segmentation fault === #include #include #include /* A number that when doubled will be bigger than 2^31 - 1 */ #define BIG_NUMBER_TO_OVERFLOW_INT (1100000000) static int cmp_char(const void *p1, const void *p2) { char v1 = (*(char *)p1); char v2 = (*(char *)p2); if (v1 < v2) return -1; else if (v1 > v2) return 1; else return 0; } void *lib_bsearch(const void *key, const void *base, size_t num, size_t size , int (*cmp)(const void *key, const void *elt)) { int start = 0, end = num - 1, mid, result; while (start <= end) { mid = (start + end) / 2; result = cmp(key, base + mid * size); if (result < 0) end = mid - 1; else if (result > 0) start = mid + 1; else return (void *)base + mid * size; } return NULL; } void *patch_lib_bsearch(const void *key, const void *base, size_t num, size_t size , int (*cmp)(const void *key, const void *elt)) { size_t start = 0, end = num; int result; while (start < end) { size_t mid = start + (end - start) / 2; result = cmp(key, base + mid * size); if (result < 0) end = mid; else if (result > 0) start = mid + 1; else return (void *)base + mid * size; } return NULL; } int main(void) { char key = 1; char *array = calloc(BIG_NUMBER_TO_OVERFLOW_INT, sizeof(char)); void *ptr; if (!array) { printf("%s\n", "no memory"); return EXIT_FAILURE; } array[BIG_NUMBER_TO_OVERFLOW_INT - 1] = 1; ptr = bsearch(&key, array, BIG_NUMBER_TO_OVERFLOW_INT, sizeof(char), cmp_char); printf("(glibc) Element is%sat the last position\n" , (ptr == &array[BIG_NUMBER_TO_OVERFLOW_INT - 1]) ? " " : " NOT "); ptr = patch_lib_bsearch(&key, array, BIG_NUMBER_TO_OVERFLOW_INT, sizeof(char), cmp_char); printf("(patched) Element is%sat the last position\n" , (ptr == &array[BIG_NUMBER_TO_OVERFLOW_INT - 1]) ? " " : " NOT "); ptr = lib_bsearch(&key, array, BIG_NUMBER_TO_OVERFLOW_INT, sizeof(char), cmp_char); printf("(unpatched) Element is%sat the last position\n" , (ptr == &array[BIG_NUMBER_TO_OVERFLOW_INT - 1]) ? " " : " NOT "); free(array); return EXIT_SUCCESS; } Signed-off-by: André Goddard Rosa Signed-off-by: Rusty Russell --- lib/bsearch.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/bsearch.c b/lib/bsearch.c index 33cbba6b7a7c..29233eda58f3 100644 --- a/lib/bsearch.c +++ b/lib/bsearch.c @@ -33,10 +33,12 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size, int (*cmp)(const void *key, const void *elt)) { - int start = 0, end = num, mid, result; + size_t start = 0, end = num; + int result; while (start < end) { - mid = (start + end) / 2; + size_t mid = start + (end - start) / 2; + result = cmp(key, base + mid * size); if (result < 0) end = mid; -- cgit v1.2.3