Re: [PATCH v3 2/2] bsearch: prevent overflow when computing middle comparison element

On Tue, Nov 10, 2009 at 10:18 PM, Rusty Russell <rusty@xxxxxxxxxxxxxxx> wrote:
On Tue, 10 Nov 2009 02:12:31 am André Goddard Rosa wrote:
It's really difficult to occur in practice because the sum of the lower
and higher limits must overflow an int variable, but it can occur when
working with large arrays. We'd better safe than sorry by avoiding this
overflow situation when computing the middle element for comparison.

I always thought the obvious answer was:

       mid = start + (end - start)/2;

Hi, Rusty!

Yes, you're right! The previous patch fixes the case where the
number of elements approach the
maximum int value (2^31 - 1 on my computer). If the number of elements
(parameter num) were an
integer amount (Java's array length case), just making those unsigned
would be enough, because
in the worst case we would have:

(max int) * 2 < (max unsigned int)
(2^31 - 1) * 2 < (2^32 - 1)

But it does not fix the case where the number of elements
approaches the maximum unsigned int
value (parameter size_t num).

So, the worst case happens when the number we search for is stored
at the highest extreme of the array.
In that case, 'start' tends toward 'end', and if 'end' is near the
maximum allowed value for a specific data type,
the overflow could still happen.

I'm sending a fixed patch in a moment as per your suggestion.

Thank you,
André
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Relevant Pages

  • Re: Segmentation Fault
    ... You shouldn't assume that you will be able to allocate an array this ... i*i gives overflow and overflow of int is not defined ... Visit http://www.ecomstation.de the home of german eComStation ...
    (comp.lang.c)
  • Re: Pointer arithmetics in 2D arrays
    ... so it becomes int *. ... are, strictly speaking, breaking the rules. ... overstepping the bounds of an array. ... overflow was declared UB in the first place (i.e. speeding up run time by ...
    (comp.lang.c)
  • Re: bad programming practice?
    ... int array; ... to define an array after the retreival (via input data ... since calloc() doe size checking for you, ... The thing is that you might overflow your type's here, ...
    (comp.lang.c)
  • Re: type of array index?
    ... >> must be able to represent any possible array subscript. ... dozen other coders) overflows that int but size_t would have worked. ... whether the index will overflow ten years later and crash some ...
    (comp.lang.c)
  • (patch for Bash) regex case statement
    ... Following up on my previous patch for regex conditional tests, ... /* Return an array of strings; ... int dollarflag, zeropad, compareflag; ... SHELL_VAR *var; ...
    (comp.unix.shell)