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

From: Philip Oakley <philipoakley@iee.org>
Date: Aug 16, 2013, 16:47 UTC
Message-ID: <EE5B338564E14F89B349550B37741AFF@PhilipOakley>
In-Reply-To: <CAPig+cQ5Y9irLk=9Bhz09c=5yzZEcyMKn2kbhcrO_zDpgmkhGw@mail.gmail.com>

From: "Eric Sunshine" <sunshine@sunshineco.com>

Show 37 quoted lines

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

Show 32 quoted lines

> 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