This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] stdlib-bsearch: middle element calculation may overflow
- From: Ondřej Bílka <neleai at seznam dot cz>
- To: Sergey Senozhatsky <sergey dot senozhatsky at gmail dot com>, Joseph Myers <joseph at codesourcery dot com>, Sergey Senozhatsky <sergey dot senozhatsky dot work at gmail dot com>, "libc-alpha at sourceware dot org" <libc-alpha at sourceware dot org>
- Date: Tue, 28 Mar 2017 12:19:37 +0200
- Subject: Re: [PATCH] stdlib-bsearch: middle element calculation may overflow
- Authentication-results: sourceware.org; auth=none
- References: <20170316052615.7662-1-sergey.senozhatsky@gmail.com> <alpine.DEB.2.20.1703161401150.3566@digraph.polyomino.org.uk> <20170316154908.GA575@tigerII.localdomain> <20170316205440.GZ24205@vapier>
On Thu, Mar 16, 2017 at 04:54:40PM -0400, Mike Frysinger wrote:
> On 17 Mar 2017 00:49, Sergey Senozhatsky wrote:
> > On (03/16/17 14:02), Joseph Myers wrote:
> > > 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.
> >
> > a) um... I assume glibc Bugzilla is located at https://sourceware.org/bugzilla/
> > and 2753, thus, is https://sourceware.org/bugzilla/show_bug.cgi?id=2753
> > if so, then, yes looks like I'm not the first one to point that out.
> > I'm not sure I see Ulrich's "You do not even understand how binary
> > searching works, do you? The sum can never exceed nmemb and nmemb
> > obviously fits into an size_t" point. it's a bug.
>
> if you see a comment by Ulrich that looks to be unrelated/off, then you
> can probably safely assume it is. if the bug is open still, then we
> usually consider it *now* to be something worth fixing.
>
No, this is wrong fix as I probably write before. It isn't visible bug
unless programmer is idiot who tries to sort gigabyte long array of
single bytes and use binary search on it. Just keeping 256 byte table of positions
would be more effective than sorting.
For any bigger size there isn't overflow as difference between that
pointers is bounded.
This fix takes extra instruction which would harm performance for basically everybody for nonexistent problem.
If you want to fix this special-case one byte branch to make gcc
optimize it away for larger sizes.