[PATCH v4 1/2] bsearch: avoid unneeded decrement arithmetic

[PATCH v4 1/2] bsearch: avoid unneeded decrement arithmetic

[André Goddard Rosa]

Signed-off-by: André Goddard Rosa <andre.goddard@gmail.com>
---
 lib/bsearch.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/lib/bsearch.c b/lib/bsearch.c
index 2e70664..33cbba6 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
-- 
1.6.5.2.153.g6e31f.dirty

[PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element

[André Goddard Rosa]

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 <search.h>
#include <stdlib.h>
#include <stdio.h>

/* 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 <andre.goddard@gmail.com>
---
 lib/bsearch.c |    6 ++++--
 1 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/lib/bsearch.c b/lib/bsearch.c
index 33cbba6..29233ed 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;
-- 
1.6.5.2.153.g6e31f.dirty

Re: [PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element

[Thiago Farina]

On Tue, Nov 10, 2009 at 1:00 PM, André Goddard Rosa
<andre.goddard@gmail.com> 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, mid, result;
> +       size_t start = 0, end = num;
> +       int result;
>
>        while (start < end) {
> -               mid = (start + end) / 2;
> +               size_t mid = start + (end - start) / 2;
I think it is more readable if you could keep the mid variable outside
of the while loop.

Re: [PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element

[Thiago Farina]

On Wed, Nov 11, 2009 at 1:09 PM, Thiago Farina <tfransosi@gmail.com> wrote:
> On Tue, Nov 10, 2009 at 1:00 PM, André Goddard Rosa
> <andre.goddard@gmail.com> 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, mid, result;
>> +       size_t start = 0, end = num;
>> +       int result;
>>
>>        while (start < end) {
>> -               mid = (start + end) / 2;
>> +               size_t mid = start + (end - start) / 2;
> I think it is more readable if you could keep the mid variable outside
> of the while loop.
>
I mean: size_t start = 0, end = num, mid;

Re: [PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element

[Rusty Russell]

On Wed, 11 Nov 2009 01:30:25 am André Goddard Rosa wrote:
> 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.

I applied all these, after testing.  In future would have been nice for you
to have posted a test patch so I didn't have make my own...

Thanks,
Rusty.

diff --git a/lib/bsearch.c b/lib/bsearch.c
--- a/lib/bsearch.c
+++ b/lib/bsearch.c
@@ -51,3 +51,50 @@ void *bsearch(const void *key, const voi
 	return NULL;
 }
 EXPORT_SYMBOL(bsearch);
+
+#if 1
+static int test_cmp(const void *_key, const void *_elt)
+{
+	int key = *(int *)_key, elt = *(int *)_elt;
+
+	if (key < elt)
+		return -1;
+	else if (key > elt)
+		return 1;
+	return 0;
+}
+
+static int test_bsearch(void)
+{
+	const int arr[] = { INT_MIN, 0, 1, 2, 3, 4, 5, 6, INT_MAX };
+	unsigned int start, num, i, total = 0;
+	int key;
+
+	for (start = 0; start < ARRAY_SIZE(arr); start++) {
+		for (num = 0; num < ARRAY_SIZE(arr) - start; num++) {
+			key = 7;
+			BUG_ON(bsearch(&key, &arr[start], num, sizeof(arr[0]),
+				       test_cmp));
+			total++;
+			for (i = start; i < start+num; i++) {
+				int *ret;
+				key = arr[i];
+				ret = bsearch(&key, &arr[start], num,
+					      sizeof(arr[0]), test_cmp);
+				if (!ret) {
+					printk("Could not find %i in %u-%u"
+					       "(between %i and %i)\n",
+					       key, start, start+num,
+					       arr[start], arr[start+num]);
+				}
+				BUG_ON(!ret);
+				BUG_ON(*ret != key);
+				total++;
+			}
+		}
+	}
+	printk("Tested %u bsearches\n", total);
+	return 0;
+}
+module_init(test_bsearch);
+#endif

Re: [PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element

[André Goddard Rosa]

On Thu, Nov 12, 2009 at 11:06 AM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> On Wed, 11 Nov 2009 01:30:25 am André Goddard Rosa wrote:
>> 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.
>
> I applied all these, after testing.  In future would have been nice for you
> to have posted a test patch so I didn't have make my own...
>

Sure, no problem, thanks!

Kind regards,
André

Re: [PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element

[Thiago Farina]

Hi Rusty,

On Thu, Nov 12, 2009 at 11:06 AM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> On Wed, 11 Nov 2009 01:30:25 am André Goddard Rosa wrote:
>> 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.
>
> I applied all these, after testing.  In future would have been nice for you
> to have posted a test patch so I didn't have make my own...

Where did you apply this patch?

Re: [PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element

[Rusty Russell]

On Sat, 14 Nov 2009 01:33:04 am Thiago Farina wrote:
> Hi Rusty,
> 
> On Thu, Nov 12, 2009 at 11:06 AM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> > On Wed, 11 Nov 2009 01:30:25 am André Goddard Rosa wrote:
> >> 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.
> >
> > I applied all these, after testing.  In future would have been nice for you
> > to have posted a test patch so I didn't have make my own...
> 
> Where did you apply this patch?

To my kernel series, which means it is now in linux-next.

Hope that helps,
Rusty.

Re: [PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element

[Rusty Russell]

On Thu, 23 Sep 2010 12:12:13 am André Goddard Rosa wrote:
> On Fri, Nov 13, 2009 at 8:42 PM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> > On Sat, 14 Nov 2009 01:33:04 am Thiago Farina wrote:
> >> Hi Rusty,
> >>
> >> On Thu, Nov 12, 2009 at 11:06 AM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> >> > On Wed, 11 Nov 2009 01:30:25 am André Goddard Rosa wrote:
> >> >> 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.
> >> >
> >> > I applied all these, after testing.  In future would have been nice for you
> >> > to have posted a test patch so I didn't have make my own...
> >>
> >> Where did you apply this patch?
> >
> > To my kernel series, which means it is now in linux-next.
> >
> > Hope that helps,
> > Rusty.
> >
> 
> Hi, Rusty!
> 
>     Is there any chance that this patchset will land into mainline anytime soon?
> 
>     Here we have another use for the binary search function:
>         http://marc.info/?l=linux-kernel&m=128515012817787&w=2

"Unused code is buggy code".  Can we have some users please?  Do people
care that uninlining means an indirect fn call now for cmp?

Nonetheless, I've merged all the fixes together:

From: Tim Abbott <tabbott@ksplice.com>
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 <tabbott@ksplice.com>
Extra-bikeshedding-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
Extra-bikeshedding-by: André Goddard Rosa <andre.goddard@gmail.com>
Extra-bikeshedding-by: Rusty Russell <rusty@rustcorp.com.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 include/linux/bsearch.h |    9 ++++++++
 lib/Makefile            |    2 -
 lib/bsearch.c           |   53 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 63 insertions(+), 1 deletion(-)

diff --git a/include/linux/bsearch.h b/include/linux/bsearch.h
new file mode 100644
--- /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
--- 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 lcm.o list_sort.o uuid.o
+	 string_helpers.o gcd.o lcm.o list_sort.o uuid.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
--- /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))
+{
+	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;
+}
+EXPORT_SYMBOL(bsearch);

Re: [PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element

[matt mooney]

On 10:56 Thu 23 Sep     , Rusty Russell wrote:
> On Thu, 23 Sep 2010 12:12:13 am André Goddard Rosa wrote:
> > On Fri, Nov 13, 2009 at 8:42 PM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> > > On Sat, 14 Nov 2009 01:33:04 am Thiago Farina wrote:
> > >> Hi Rusty,
> > >>
> > >> On Thu, Nov 12, 2009 at 11:06 AM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> > >> > On Wed, 11 Nov 2009 01:30:25 am André Goddard Rosa wrote:
> > >> >> 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.
> > >> >
> > >> > I applied all these, after testing.  In future would have been nice for you
> > >> > to have posted a test patch so I didn't have make my own...
> > >>
> > >> Where did you apply this patch?
> > >
> > > To my kernel series, which means it is now in linux-next.
> > >
> > > Hope that helps,
> > > Rusty.
> > >
> > 
> > Hi, Rusty!
> > 
> >     Is there any chance that this patchset will land into mainline anytime soon?
> > 
> >     Here we have another use for the binary search function:
> >         http://marc.info/?l=linux-kernel&m=128515012817787&w=2
> 
> "Unused code is buggy code".  Can we have some users please?  Do people
> care that uninlining means an indirect fn call now for cmp?
> 
> Nonetheless, I've merged all the fixes together:
>

[snip]

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

The comment for "@base" seems wrong. It appears that it should say "pointer to
sorted data" or "pointer to search data" instead.

-mfm

Re: [PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element

[Rusty Russell]

On Fri, 24 Sep 2010 03:20:12 pm matt mooney wrote:
> > + * bsearch - binary search an array of elements
> > + * @key: pointer to item being searched for
> > + * @base: pointer to data to sort
> 
> The comment for "@base" seems wrong. It appears that it should say "pointer to
> sorted data" or "pointer to search data" instead.

Thanks, fixed:

+ * @base: pointer to first element to search

Cheers,
Rusty.