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

[Jeff King]

On Wed, Aug 10, 2016 at 06:58:06PM +0200, Michael Haggerty wrote:

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

Ah, yeah, I totally missed that case (and I agree the code after your
2/8 makes it much more obvious).

> I didn't do the hard work to determine whether `io` could *really* walk
> off the end of the array, but I don't see an obvious reason why it
> *couldn't*.

Yeah, I'm in agreement.

-Peff
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

[Michael Haggerty]

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

I didn't do the hard work to determine whether `io` could *really* walk
off the end of the array, but I don't see an obvious reason why it
*couldn't*.

> Anyway, I'd suggest putting your cover letter bits into the commit
> message. Even though they are all suppositions, they are the kind of
> thing that could really help somebody debugging this in 2 years, and are
> better than nothing.

Good idea. Will do.

Michael

--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

[Michael Haggerty]

On 08/04/2016 08:43 PM, Junio C Hamano wrote:
> Michael Haggerty  writes:
> 
>> 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.
> 
> I had to read the first sentence three times as "incorrectly forgot"
> was a bit strange thing to say (as if there is a situation where
> 'forgetting to do' is the correct thing to do, but in that case we
> would phrase it to stress that not doing is a deliberate choice,
> e.g. 'refraining from doing').  Perhaps s/incorrectly // is the
> simplest readability improvement?

Yes, that makes it clearer. Will change.

Michael

--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

[Michael Haggerty]

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

--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

[Junio C Hamano]

Michael Haggerty  writes:

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

I had to read the first sentence three times as "incorrectly forgot"
was a bit strange thing to say (as if there is a situation where
'forgetting to do' is the correct thing to do, but in that case we
would phrase it to stress that not doing is a deliberate choice,
e.g. 'refraining from doing').  Perhaps s/incorrectly // is the
simplest readability improvement?

> Signed-off-by: Michael Haggerty 
> ---
> 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.

I agree with Peff that these should be in the log message.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

[Jeff King]

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 
> ---
> 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.
And it looks like rchgo[io] always ends the loop on a 0. So it seems
like we would just hit that condition again.

That doesn't make it _right_, but I'm not sure I see how it would walk
off the end of the array.  But I'm very sure I don't understand this
code completely, so I may be missing something.

Anyway, I'd suggest putting your cover letter bits into the commit
message. Even though they are all suppositions, they are the kind of
thing that could really help somebody debugging this in 2 years, and are
better than nothing.

-Peff
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

[Michael Haggerty]

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

 xdiff/xdiffi.c | 4 
 1 file changed, 4 insertions(+)

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index c67cfe3..66129db 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -562,6 +562,10 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long 
flags) {
   recs_match(recs, start - 1, end - 1, flags)) {
rchg[--start] = 1;
rchg[--end] = 0;
+
+   io--;
+   while (rchgo[io])
+   io--;
}
} else if (end_matching_other != -1) {
/*
-- 
2.8.1

--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html