| Message ID | 20170316052615.7662-1-sergey.senozhatsky@gmail.com |
|---|---|
| State | New |
| Headers | show |
On 16 Mar 2017 14:26, Sergey Senozhatsky wrote: > Middle element calculation may overflow at '__l + __u' when > __l and __u are large enough. Use distance between __u and > __l instead. do you a simple test case we can include ? -mike
Mike Frysinger wrote:
> do you a simple test case we can include ?
On x86-64 any such test would require more than 2**63 members in the array. Not
sure I'd want to run that....
On 03/16/2017 09:17 AM, Paul Eggert wrote: > Mike Frysinger wrote: >> do you a simple test case we can include ? > > On x86-64 any such test would require more than 2**63 members in the > array. Not sure I'd want to run that.... It's impossible to write a test case for x86_64 because it's more like a 47-bit architecture. Most of the array elements do not actually have to be present, so it should be possible to write a test on those architectures which can allocate more than half of the address space. Thanks, Florian
On (03/16/17 03:32), Mike Frysinger wrote: > On 16 Mar 2017 14:26, Sergey Senozhatsky wrote: > > Middle element calculation may overflow at '__l + __u' when > > __l and __u are large enough. Use distance between __u and > > __l instead. > > do you a simple test case we can include ? Hello Mike, well... no, I don't. but something like below (composed in mail client, basically) should do the trick in 32-bit mode. sorry, I'm really not familiar with the way you guys usually write tests for glibc. hope this helps. ==== test.c ==== // includes #define ARRAY_SZ 3100000000U static int char_compare(const void *a, const void *b) { const char *ca = (const char *)a; const char *cb = (const char *)b; return *ca - *cb; } int main() { char *array; char *ret; char key = '2'; array = malloc(sizeof(char) * ARRAY_SZ); if (!array) abort(); memset(array, '1', ARRAY_SZ); array[ARRAY_SZ - 1] = '2'; ret = bsearch(&key, array, ARRAY_SZ, sizeof(char), char_compare); if (!ret || *ret != key) abort(); return 0; } --- gcc -m32 test.c -o a.out ./a.out most likely will never stop. while the patched bsearch() should. -ss
I don't see why any of the array elements need to be valid, it's
purely a test of void*/char* arithmetic.
int c(const void *a, const void *b)
{
return (b > a) ? -1 : ((b < a) ? 1 : 0);
}
int main(void)
{
printf("%p\n", bsearch((void *)0xfffffffffffffffeULL, NULL,
0xffffffffffffffffULL, 1, c));
return 0;
}
works with the patch, and fails without it, on x86_64. (I'm not sure
whether the behavior is defined by the C standard, but I'm pretty sure
it's defined by the x86_64 ABI).
On (03/16/17 08:53), Pip Cet wrote:
> I don't see why any of the array elements need to be valid
hm, indeed ;)
-ss
If this fixes a user-visible bug then the ChangeLog entry needs to include [BZ #N] referencing the bug filed in Bugzilla (and once the fix is in the bug needs to be resolved as FIXED with appropriate target milestone set). Is this bug 2753? If not, a new bug would need to be filed for it.
diff --git a/bits/stdlib-bsearch.h b/bits/stdlib-bsearch.h index eb145381fd..5fd8a8b607 100644 --- a/bits/stdlib-bsearch.h +++ b/bits/stdlib-bsearch.h @@ -28,7 +28,7 @@ bsearch (const void *__key, const void *__base, size_t __nmemb, size_t __size, __u = __nmemb; while (__l < __u) { - __idx = (__l + __u) / 2; + __idx = __l + (__u - __l) / 2; __p = (void *) (((const char *) __base) + (__idx * __size)); __comparison = (*__compar) (__key, __p); if (__comparison < 0)
Middle element calculation may overflow at '__l + __u' when __l and __u are large enough. Use distance between __u and __l instead. Signed-off-by: Sergey Senozhatsky <sergey.senozhatsky@gmail.com> --- bits/stdlib-bsearch.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)