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

Rusty Russell
2009-11-12T13:06:14Z

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