Re: [PATCH] stdlib-bsearch: middle element calculation may overflow

[Joseph Myers <joseph at codesourcery dot com>]

On Fri, 17 Mar 2017, Sergey Senozhatsky wrote:

> 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.

As I understand it: it's a bug for an array the number of whose elements 
is more than SIZE_MAX / 2.

Now, there is certainly no need for the comparison function actually to 
look at the contents of the elements; it's completely valid for it to do 
something magic that depends on the position of the element in the array 
rather than (just) its contents.  And 1-byte elements are certainly valid.  
But the pointers do need to be valid - although when you enter the POSIX 
context there is a strong argument that as long as the addresses are all 
within the process's address space, it's OK for them to be mapped with 
PROT_NONE permissions (as long as the comparison function doesn't actually 
access the referenced objects).

Allocating objects occupying half or more of the address space, even with 
PROT_NONE permissions, is questionable because pointer subtraction cannot 
work reliably in them (so there is an argument for malloc, mmap etc. to 
disallow such allocations).  But it's believed, from past discussions, 
that some users of 32-bit systems (possibly 32-bit processes under a 
64-bit kernel) do in fact rely on being able to make a single allocation 
of 2 GB or more, and our existing practice for string functions is to 
consider it a bug if a string function doesn't work correctly for >= 2 GB 
strings on 32-bit systems.  So on the same basis, this bsearch issue 
should be considered a bug.

If the fix reduces performance, there's a case for making it conditional:

if (__builtin_constant_p (__size) && __size >= 2)
  /* old code */
else
  /* new code */

given that the issue can only apply with elements of size 1, and the 
common case probably *is* that the size is constant (__builtin_constant_p 
works in inline functions) and at least 2, so that would avoid affecting 
the code generated in the common case at all.

-- 
Joseph S. Myers
joseph@codesourcery.com