Re: [PATCH] create_delta_index: simplify condition always evaluating to true

["Philip Oakley" <philipoakley@iee.org>]

From: "Eric Sunshine" <sunshine@sunshineco.com>
> On Thu, Aug 15, 2013 at 5:34 PM, Stefan Beller
> <stefanbeller@googlemail.com> wrote:
>> When checking the previous lines in that function, we can deduce that
>> hsize must always be smaller than (1u<<31), since 506049c7df2c6
>> (fix >4GiB source delta assertion failure), because entries is
>> capped at an upper bound of 0xfffffffeU, so hsize contains a maximum
>> value of 0x3fffffff, which is smaller than (1u<<31), so the value of
>> 'i' will never be larger than 31.
>>
>> Signed-off-by: Stefan Beller <stefanbeller@googlemail.com>
>> ---
>>
>> Eric, thanks for reviewing my patch.
>>
>> I applied the first 2 proposals (deduce, entries), but I disagree on
>> the third, so I reformulated the sentence, as I really meant the 
>> variable
>> i and not it as a pronoun.
>
> Thanks. Adding the quotes around 'i' makes your meaning clear. Without
> the quotes, apparently it was ambiguous, and my brain read it as a
> misspelling of 'it'.
>
>> Do I understand right, you're suggesting to remove the
>> source code comment? I did this now, but I have a bad feeling with 
>> it.
>>
>> The change of this patch surely removes dead code as of now and makes 
>> it
>> more readable. But also it could become alive again, once somebody
>> changes things nearby and forgets about the assumption, hsize not
>> exceeding a certain size. That's why I put a comment in there, so
>> the future changes nearby may be more careful.
>
> Indeed, I feel uncomfortable with the patch in general for the very
> reason that you state: it might become live again. Without the patch,
> the code remains safe without any extra effort.

The problem is that without the patch (or some change) the code was 
already unsafe.

The code sequence  ' (1u << i) < hsize && i < 31 ' is a multi step 
process, whose first step requires that 'i' is already less that 31, 
otherwise the result (1u << i)  is undefined (and  'undef_val < hsize' 
can therefore be assumed to be 'false'), and so the later test  i < 31 
can always be optimised away as dead code ('i' is already less than 31, 
or the short circuit 'and' applies).

Simply swapping around the code such that the i < 31 test is performed 
first would also solve the (latent optimisation) problem.

Section 2.2 of the "Undefined behavior: What happened to my code?" paper 
on http://css.csail.mit.edu/stack/ discusses this issue with an example 
from the Linux kernel.

> With this patch, even
> with the in-code comment, someone making changes needs to take special
> care. Sometimes it makes sense to leave safeties in place, even if
> they can't be triggered _today_; and safeties (such as i < 31) also
> serve as documentation.
>
>>
>> Thanks,
>> Stefan
>>
>>
>>  diff-delta.c | 2 +-
>>  1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/diff-delta.c b/diff-delta.c
>> index 93385e1..3797ce6 100644
>> --- a/diff-delta.c
>> +++ b/diff-delta.c
>> @@ -155,7 +155,7 @@ struct delta_index * create_delta_index(const 
>> void *buf, unsigned long bufsize)
>>                 entries = 0xfffffffeU / RABIN_WINDOW;
>>         }
>>         hsize = entries / 4;
>> -       for (i = 4; (1u << i) < hsize && i < 31; i++);
>> +       for (i = 4; (1u << i) < hsize; i++);
>>         hsize = 1 << i;
>>         hmask = hsize - 1;
>>
>> --
>> 1.8.4.rc3.1.gc1ebd90
>>
> --

Philip