Re: [PATCH 5/8] xdl_change_compact(): fix compaction heuristic to adjust io
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
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
On 08/04/2016 08:43 PM, Junio C Hamano wrote: > Michael Haggertywrites: > >> 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
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
Michael Haggertywrites: > 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
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
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