Skip to contentSkip to conversation

bsearch: avoid unneeded decrement arithmetic

PATCH In review André Goddard Rosa 4 participants 11 messages Nov 11, 2009 – Oct 4, 2010 2 messages not in the archive Library code

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw

PATCH v4 1/2 bsearch: avoid unneeded decrement arithmetic

---
 lib/bsearch.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)
lib/bsearch.c +3 -3
index 2e70664..33cbba6 100644
@@ -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
Signature · 1 line
1.6.5.2.153.g6e31f.dirty
#2 lore raw

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

In reply to a message not in the archive

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;
}
---
 lib/bsearch.c |    6 ++++--
 1 files changed, 4 insertions(+), 2 deletions(-)
lib/bsearch.c +4 -2
index 33cbba6..29233ed 100644
@@ -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;
Signature · 1 line
1.6.5.2.153.g6e31f.dirty
#3 lore raw

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

Quoted 10 lines · André Goddard Rosa

 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.

#4 lore raw

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

Quoted 9 lines · Thiago Farina
Quoted 7 lines · André Goddard Rosa

 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;

Quoted 6 lines
Quoted 3 lines

       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;

#5 lore raw

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

In reply to André Goddard Rosa
Quoted 4 lines · 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.

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.

lib/bsearch.c +47 -0
@@ -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
#6 lore raw

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

Quoted 9 lines · Rusty Russell
Quoted 4 lines · 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.

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é

#7 lore raw

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

In reply to Rusty Russell

Hi Rusty,

Quoted 8 lines · Rusty Russell
Quoted 4 lines · 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.

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?

#8 lore raw

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

Quoted 9 lines · Thiago Farina

Hi Rusty,

Quoted 6 lines · Rusty Russell
Quoted 4 lines · 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.

Quoted 4 lines
Quoted 2 lines

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.

A message that is not in the archive (sent off-list or not yet received): [email protected]

#10 lore raw

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

Quoted 22 lines · André Goddard Rosa
Quoted 13 lines · Rusty Russell
Quoted 12 lines · Thiago Farina

Hi Rusty,

Quoted 8 lines · Rusty Russell
Quoted 4 lines · 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.

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

Quoted 7 lines
Quoted 1 line

Where did you apply this patch?

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

Hope that helps,
Rusty.

Quoted 6 lines

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 <[email protected]>
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.

---
 include/linux/bsearch.h |    9 ++++++++
 lib/Makefile            |    2 -
 lib/bsearch.c           |   53 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 63 insertions(+), 1 deletion(-)
include/linux/bsearch.h new file +9 -0
new file mode 100644
@@ -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 */
lib/Makefile +1 -1
@@ -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
lib/bsearch.c new file +53 -0

53 lines not on this page · raw message

#11 lore raw

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

Quoted 35 lines · Rusty Russell
Quoted 22 lines · André Goddard Rosa
Quoted 13 lines · Rusty Russell
Quoted 12 lines · Thiago Farina

Hi Rusty,

Quoted 8 lines · Rusty Russell
Quoted 4 lines · 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.

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

Quoted 7 lines
Quoted 1 line

Where did you apply this patch?

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

Hope that helps,
Rusty.

Quoted 6 lines

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]

lib/bsearch.c line 18

Quoted 7 lines
lib/bsearch.c new file +7 -0
+#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

#12 lore raw

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

Quoted 6 lines · matt mooney
Quoted 3 lines

+ * 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.