[PATCH 0/2] Use generic binary search function

[PATCH 0/2] Use generic binary search function

[Tim Abbott]

> 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

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

[Alan Jenkins]

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
>
>   

[PATCH 1/2] lib: Add generic binary search function to the kernel.

[Tim Abbott]

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 <tabbott@ksplice.com>
---
 include/linux/bsearch.h |    9 ++++++++
 lib/Makefile            |    2 +-
 lib/bsearch.c           |   53 +++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 63 insertions(+), 1 deletions(-)
 create mode 100644 include/linux/bsearch.h
 create mode 100644 lib/bsearch.c

diff --git a/include/linux/bsearch.h b/include/linux/bsearch.h
new file mode 100644
index 0000000..90b1aa8
--- /dev/null
+++ b/include/linux/bsearch.h
@@ -0,0 +1,9 @@
+#ifndef _LINUX_BSEARCH_H
+#define _LINUX_BSEARCH_H
+
+#include <linux/types.h>
+
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+	      int (*cmp)(const void *key, const void *elt));
+
+#endif /* _LINUX_BSEARCH_H */
diff --git a/lib/Makefile b/lib/Makefile
index 2e78277..fb60af1 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 0000000..4297c98
--- /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 <tabbott@ksplice.com>
+ *
+ * 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 <linux/module.h>
+#include <linux/bsearch.h>
+
+/*
+ * 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);
-- 
1.6.3.3

Re: [PATCH 1/2] lib: Add generic binary search function to the kernel.

[Rusty Russell]

On Thu, 24 Sep 2009 02:58:45 am Tim Abbott wrote:
> 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 <tabbott@ksplice.com>
> ---
>  include/linux/bsearch.h |    9 ++++++++
>  lib/Makefile            |    2 +-
>  lib/bsearch.c           |   53 +++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 63 insertions(+), 1 deletions(-)
>  create mode 100644 include/linux/bsearch.h
>  create mode 100644 lib/bsearch.c
> 
> diff --git a/include/linux/bsearch.h b/include/linux/bsearch.h
> new file mode 100644
> index 0000000..90b1aa8
> --- /dev/null
> +++ b/include/linux/bsearch.h
> @@ -0,0 +1,9 @@
> +#ifndef _LINUX_BSEARCH_H
> +#define _LINUX_BSEARCH_H
> +
> +#include <linux/types.h>
> +
> +void *bsearch(const void *key, const void *base, size_t num, size_t size,
> +	      int (*cmp)(const void *key, const void *elt));
> +
> +#endif /* _LINUX_BSEARCH_H */
> diff --git a/lib/Makefile b/lib/Makefile
> index 2e78277..fb60af1 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 0000000..4297c98
> --- /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 <tabbott@ksplice.com>
> + *
> + * 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 <linux/module.h>
> +#include <linux/bsearch.h>
> +
> +/*
> + * 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) {

The if (num == 0) line is superfluous.

But I'd be happy to take this as part of Alan's patches.

Thanks!
Rusty.

Re: [PATCH 1/2] lib: Add generic binary search function to the kernel.

[Tim Abbott]

On Thu, 24 Sep 2009, Rusty Russell wrote:

> On Thu, 24 Sep 2009 02:58:45 am Tim Abbott wrote:
> > +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) {
> 
> The if (num == 0) line is superfluous.

You are quite right.

	-Tim Abbott

Re: [PATCH 1/2] lib: Add generic binary search function to the kernel.

[Thiago Farina]

Hi, this patch was landed? It seems not to be in the tree
(git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6).

Re: [PATCH 1/2] lib: Add generic binary search function to the kernel.

[Alan Jenkins]

Thiago Farina wrote:
> Hi, this patch was landed? It seems not to be in the tree
> (git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6).
>   

I guess I'm sitting on it at the moment, having folded it into a patch 
series which I have yet to submit.

There are apparently already a number of implementations scattered 
around the kernel tree.  Perhaps you can add another copy of this 
implementation, wherever it is you need it :-).

Alan

[PATCH 2/2] module: use bsearch in find_symbol_in_kernel_section.

[Tim Abbott]

Signed-off-by: Tim Abbott <tabbott@ksplice.com>
---
 kernel/module.c |   34 +++++++++++++++-------------------
 1 files changed, 15 insertions(+), 19 deletions(-)

diff --git a/kernel/module.c b/kernel/module.c
index 9b19f23..25ff16b 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -55,6 +55,7 @@
 #include <linux/async.h>
 #include <linux/percpu.h>
 #include <linux/kmemleak.h>
+#include <linux/bsearch.h>
 
 #define CREATE_TRACE_POINTS
 #include <trace/events/module.h>
@@ -209,31 +210,26 @@ struct symsearch {
 #define symversion(base, idx) ((base != NULL) ? ((base) + (idx)) : NULL)
 #endif
 
-/* binary search on sorted symbols */
+static int symbol_compare(const void *key, const void *elt)
+{
+	const char *str = key;
+	const struct kernel_symbol *sym = elt;
+	return strcmp(sym->name, str);
+}
+
 static bool find_symbol_in_kernel_section(const struct symsearch *syms,
 					  const char *name,
 					  unsigned int *symnum)
 {
-	int lo = 0, hi = syms->stop - syms->start - 1;
-	int mid, cmp;
-
-	while (lo <= hi) {
-		mid = (lo + hi) / 2;
-		cmp = strcmp(syms->start[mid].name, name);
-		if (cmp == 0) {
-			*symnum = mid;
-			return true;
-		}
-		else if (cmp < 0)
-			hi = mid - 1;
-		else
-			lo = mid + 1;
-	}
-
-	return false;
+	const struct kernel_symbol *sym =
+	    bsearch(name, syms->start, syms->stop - syms->start,
+		    sizeof(*syms->start), symbol_compare);
+	if (sym == NULL)
+		return false;
+	*symnum = sym - syms->start;
+	return true;
 }
 
-
 static bool find_symbol_in_kernel(const char *name,
 				  struct symsearch *sym,
 				  unsigned int *symnum)
-- 
1.6.3.3