git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Jeff King <peff@peff.net>
Date
Aug 4, 2016, 07:27 UTC
Message-ID
<20160804072705.a53mospcccksiz4e@sigill.intra.peff.net>
In-Reply-To
<ae7590443737a3996ec4973fd868ce89dc78a576.1470259583.git.mhagger@alum.mit.edu>
On Thu, Aug 04, 2016 at 12:00:33AM +0200, Michael Haggerty wrote:
Show 21 quoted lines
> 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. 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
Previous: Michael HaggertyNext: Michael Haggerty
Message 10 of 57 in “Better heuristics make prettier diffs”
  1. 0/8 Better heuristics make prettier diffsMichael Haggerty, Aug 3, 2016
  2. 2/8 xdl_change_compact(): clarify codeMichael Haggerty, Aug 3, 2016
  3. Stefan BellerAug 3, 2016
  4. Michael HaggertyAug 3, 2016
  5. Stefan BellerAug 3, 2016
  6. Jeff KingAug 4, 2016
  7. Michael HaggertyAug 10, 2016
  8. Stefan BellerAug 10, 2016
  9. 5/8 xdl_change_compact(): fix compaction heuristic to adjust ioMichael Haggerty, Aug 3, 2016
  10. Jeff KingAug 4, 2016
  11. Michael HaggertyAug 10, 2016
  12. Michael HaggertyAug 10, 2016
  13. Jeff KingAug 11, 2016
  14. Junio C HamanoAug 4, 2016
  15. Michael HaggertyAug 10, 2016
  16. 7/8 is_blank_line: take a single xrecord_t as argumentMichael Haggerty, Aug 3, 2016
  17. Junio C HamanoAug 4, 2016
  18. 6/8 xdl_change_compact(): keep track of the earliest endMichael Haggerty, Aug 3, 2016
  19. Junio C HamanoAug 4, 2016
  20. Michael HaggertyAug 10, 2016
  21. 4/8 xdl_change_compact(): do one final shift or the other, not bothMichael Haggerty, Aug 3, 2016
  22. 1/8 xdl_change_compact(): rename some local variables for clarityMichael Haggerty, Aug 3, 2016
  23. Jeff KingAug 4, 2016
  24. Junio C HamanoAug 4, 2016
  25. Michael HaggertyAug 13, 2016
  26. Jeff KingAug 14, 2016
  27. Michael HaggertyAug 3, 2016
  28. 3/8 xdl_change_compact(): rename i to endMichael Haggerty, Aug 3, 2016
  29. Jeff KingAug 4, 2016
  30. 8/8 diff: improve positioning of add/delete blocks in diffsMichael Haggerty, Aug 3, 2016
  31. Jacob KellerAug 3, 2016
  32. Michael HaggertyAug 3, 2016
  33. Jacob KellerAug 4, 2016
  34. Junio C HamanoAug 4, 2016
  35. Michael HaggertyAug 10, 2016
  36. Junio C HamanoAug 10, 2016
  37. Stefan BellerAug 3, 2016
  38. Michael HaggertyAug 3, 2016
  39. Stefan BellerAug 3, 2016
  40. Michael HaggertyAug 3, 2016
  41. Stefan BellerAug 4, 2016
  42. Michael HaggertyAug 10, 2016
  43. Jeff KingAug 4, 2016
  44. Stefan BellerAug 4, 2016
  45. Junio C HamanoAug 4, 2016
  46. Michael HaggertyAug 13, 2016
  47. Michael HaggertyAug 12, 2016
  48. Jeff KingAug 13, 2016
  49. Junio C HamanoAug 13, 2016
  50. Jacob KellerAug 14, 2016
  51. Stefan BellerAug 15, 2016
  52. Junio C HamanoAug 15, 2016
  53. Junio C HamanoAug 4, 2016
  54. Michael HaggertyAug 13, 2016
  55. Jeff KingAug 4, 2016
  56. Junio C HamanoAug 4, 2016
  57. Jeff KingAug 4, 2016

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.