Message ID | 20170316052615.7662-1-sergey.senozhatsky@gmail.com |
---|---|
State | New, archived |
Headers |
Received: (qmail 117085 invoked by alias); 16 Mar 2017 05:26:27 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: <libc-alpha.sourceware.org> List-Unsubscribe: <mailto:libc-alpha-unsubscribe-##L=##H@sourceware.org> List-Subscribe: <mailto:libc-alpha-subscribe@sourceware.org> List-Archive: <http://sourceware.org/ml/libc-alpha/> List-Post: <mailto:libc-alpha@sourceware.org> List-Help: <mailto:libc-alpha-help@sourceware.org>, <http://sourceware.org/ml/#faqs> Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 117070 invoked by uid 89); 16 Mar 2017 05:26:26 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.4 required=5.0 tests=BAYES_00, FREEMAIL_FROM, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM, SPF_PASS autolearn=ham version=3.3.2 spammy=distance X-HELO: mail-pg0-f65.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id; bh=fmnmWy1Z6zxUa/RjpLSjl6b0hFkK0RBCtz8qX7+3Yxg=; b=NJP2FJYD8wh6he18/0HAUNVCPvUZ/paYcX2MkRBiwBberb+F3bxzr2bMiGabgI/1DO mqIpKdLyb3yxz/c8jQH3w/yP1v/ZYAMSRtX8ha8NFVZZysXc0d57slzrsBa8RhjnKmZl mTw7nnz9KkEMEdXypmW0stpY0+jRcmz9ta85mH8hw6ESvIi2r5RxOCuZTHxL7nkA4ilA wBWB8LgxLJE1UaU1N286obGq28MUgp8XQmGQgyZbzHr04ucr2NyzPyMoJfcH4wSr1Fyh r6E1Cfhr3Jufn0btNe8MgdFlM/SJt6/AteRasEkWeWHyPNfPTX0HIhOUa/VWETIEyYWA by5g== X-Gm-Message-State: AFeK/H28Y6OAlF0X24evCFnhygALHu/kwMIe5GHyWba5SWq4L53yWedgsJcqhmkTUb62jg== X-Received: by 10.99.113.11 with SMTP id m11mr7891183pgc.36.1489641984653; Wed, 15 Mar 2017 22:26:24 -0700 (PDT) From: Sergey Senozhatsky <sergey.senozhatsky.work@gmail.com> X-Google-Original-From: Sergey Senozhatsky <sergey.senozhatsky@gmail.com> To: "libc-alpha@sourceware.org" <libc-alpha@sourceware.org> Cc: Sergey Senozhatsky <sergey.senozhatsky.work@gmail.com>, Sergey Senozhatsky <sergey.senozhatsky@gmail.com> Subject: [PATCH] stdlib-bsearch: middle element calculation may overflow Date: Thu, 16 Mar 2017 14:26:15 +0900 Message-Id: <20170316052615.7662-1-sergey.senozhatsky@gmail.com> |
Commit Message
Sergey Senozhatsky
March 16, 2017, 5:26 a.m. UTC
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
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)