Re: [PATCH 5/8] xdl_change_compact(): fix compaction heuristic to adjust io

[Michael Haggerty <mhagger@alum.mit.edu>]

On 08/10/2016 06:58 PM, Michael Haggerty wrote:
> On 08/04/2016 09:27 AM, Jeff King wrote:
>> On Thu, Aug 04, 2016 at 12:00:33AM +0200, Michael Haggerty wrote:
>>
>>> The code branch used for the compaction heuristic incorrectly forgot to
>>> keep io in sync while the group was shifted. I think that could have
>>> led to reading past the end of the rchgo array.
>>>
>>> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
>>> ---
>>> I didn't actually try to verify the presence of a bug, because it
>>> seems like more work than worthwhile. But here is my reasoning:
>>>
>>> If io is not decremented correctly during one iteration of the outer
>>> `while` loop, then it will loose sync with the `end` counter. In
>>> particular it will be too large.
>>>
>>> Suppose that the next iterations of the outer `while` loop (i.e.,
>>> processing the next block of add/delete lines) don't have any sliders.
>>> Then the `io` counter would be incremented by the number of
>>> non-changed lines in xdf, which is the same as the number of
>>> non-changed lines in xdfo that *should have* followed the group that
>>> experienced the malfunction. But since `io` was too large at the end
>>> of that iteration, it will be incremented past the end of the
>>> xdfo->rchg array, and will try to read that memory illegally.
>>
>> Hmm. In the loop:
>>
>>   while (rchgo[io])
>> 	io++;
>>
>> that implies that rchgo has a zero-marker that we can rely on hitting.
> 
> I agree.
> 
>> And it looks like rchgo[io] always ends the loop on a 0. So it seems
>> like we would just hit that condition again.
> 
> Correct...in this loop. But there is another place where `io` is
> incremented unconditionally. In the version before my changes, it is via
> the preincrement operator in this while statement conditional:
> 
> https://github.com/mhagger/git/blob/a28705da929ad746abcb34270947f738549d3246/xdiff/xdiffi.c#L502
> 
> After my changes, the unconditional increment is more obvious because I
> took it out of the while condition:
> 
> https://github.com/mhagger/git/blob/39a135da93834fd72ee923d95d0cebfe525dfe7a/xdiff/xdiffi.c#L541
> 
> (BTW, I think this is a good example of how patch 2/8 makes the code
> easier to reason about.)

Actually, for the case that no more sliders are found in the file, the
key lines where io is incremented unconditionally are

https://github.com/mhagger/git/blob/a28705da929ad746abcb34270947f738549d3246/xdiff/xdiffi.c#L438

before the change (note that the post-increment happens even if the
while condition returns false), and

https://github.com/mhagger/git/blob/39a135da93834fd72ee923d95d0cebfe525dfe7a/xdiff/xdiffi.c#L443-L444

after the change. (The lines I mentioned in my previous email are also
unconditional increments, but those are only executed in the case that
more sliders are found.)

Michael