bsearch: avoid unneeded decrement arithmetic
A message that is not in the archive (sent off-list or not yet received): [email protected]
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
@@ -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
PATCH v4 2/2 bsearch: prevent overflow when computing middle comparison element
In reply to a message not in the archiveIt'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
@@ -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
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_tnum,size_tsize, int (*cmp)(const void *key, const void *elt))
{
- int start = 0, end = num, mid, result;
+size_tstart = 0, end = num;
+ int result;while (start < end) {
- mid = (start + end) / 2;
+size_tmid = 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
Quoted 9 lines · Thiago Farina
Quoted 7 lines · André Goddard Rosa
void *bsearch(const void *key, const void *base,
size_tnum,size_tsize, int (*cmp)(const void *key, const void *elt))
{
- int start = 0, end = num, mid, result;
+size_tstart = 0, end = num;
+ int result;
Quoted 6 lines
Quoted 3 lines
while (start < end) {
- mid = (start + end) / 2;
+size_tmid = 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
In reply to André Goddard RosaQuoted 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 voireturn 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
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é
Re: [PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element
In reply to Rusty RussellHi 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?
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]
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
@@ -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
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
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 sortThe 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.