stdlib-bsearch: middle element calculation may overflow

Submitted by Sergey Senozhatsky on March 16, 2017, 5:26 a.m.

Details

Message ID 20170316052615.7662-1-sergey.senozhatsky@gmail.com
State New
Headers show

Commit Message

Sergey Senozhatsky March 16, 2017, 5:26 a.m.
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(-)

Comments

Mike Frysinger March 16, 2017, 7:32 a.m.
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
Paul Eggert March 16, 2017, 8:17 a.m.
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....
Florian Weimer March 16, 2017, 8:19 a.m.
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
Sergey Senozhatsky March 16, 2017, 8:26 a.m.
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
Pip Cet March 16, 2017, 8:53 a.m.
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).
Sergey Senozhatsky March 16, 2017, 9:03 a.m.
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
Joseph S. Myers March 16, 2017, 2:02 p.m.
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.

Patch hide | download patch | download mbox

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)