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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/