Re: [PATCH] cleanup: fix possible overflow errors in binary search, part 2

From: Martin Ågren <martin.agren@gmail.com>
Date: Jun 14, 2019, 04:18 UTC
Message-ID: <CAN0heSrEK80XHFYYuXhb4rg76Xv6n7-p-oUdyLH39vpAfjkxZg@mail.gmail.com>
In-Reply-To: <1473675e-4d27-8221-0e7a-f88eb31ee11f@web.de>

On Thu, 13 Jun 2019 at 23:33, René Scharfe <l.s.r@web.de> wrote:

>
> Am 13.06.19 um 21:42 schrieb Martin Ågren:
> > On Thu, 13 Jun 2019 at 19:54, René Scharfe <l.s.r@web.de> wrote:

Show 10 quoted lines

> >> Make sure the intermediate value stays within the boundaries instead,
> >> like this:
> >>
> >>         mid = first + ((last - first) >> 1);
> >>
> >> The loop condition of the binary search makes sure that 'last' is
> >> always greater than 'first', so this is safe as long as 'first' is
> >> not negative.  And that can be verified easily using the pre-context
> >> of each change, except for name-hash.c, so add an assertion to that
> >> effect there.

Show 10 quoted lines

> > So all is well. But maybe we should write `(last - first) / 2` anyway.
> > We could then drop the extra parenthesis, and we would keep future
> > readers (and static analysis?) from wondering whether we might ever be
> > shifting a signed value with the sign bit set. A few spots fewer to
> > audit in the future...
>
> Yes, thought about that.  When I saw Clang 8 emitting extra opcodes for
> handling the sign for the version with division I decided to restrict
> the patch to just do overflow prevention and leave the right shifts in
> place..

Ah, ok, I should have known you were on top of it. I guess that means that clang isn't able to figure out we're guaranteed to be working with non-negative numbers. Which I guess means that it can't be sure the shift is safe, but with undefined behavior it has the leeway it needs, so...

Martin