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

Re: [PATCH 1/3] pack-objects: fix tree_depth and layer invariants

From
Junio C Hamano <gitster@pobox.com>
Date
Nov 21, 2018, 04:52 UTC
Message-ID
<xmqqa7m3822q.fsf@gitster-ct.c.googlers.com>
In-Reply-To
<20181120094638.GA22742@sigill.intra.peff.net>
Jeff King <peff@peff.net> writes:
Show 12 quoted lines
> But in (b), we use the number of stored objects, _not_ the allocated
> size of the objects array. So we can run into a situation like this:
>
>   1. packlist_alloc() needs to store the Nth object, so it grows the
>      objects array to M, where M > N.
>
>   2. oe_set_tree_depth() wants to store a depth, so it allocates an
>      array of length N. Now we've violated our invariant.
>
>   3. packlist_alloc() needs to store the N+1th object. But it _doesn't_
>      grow the objects array, since N <= M still holds. We try to assign
>      to tree_depth[N+1], which is out of bounds.

Ouch. I see counting and allocationg is hard (I think I spotted a bug in another area that comes from the same "count while filtering and then allocate" pattern during this cycle). Thanks for spotting.

Previous: Jeff KingNext: Jeff King
Message 5 of 9 in “delta-island fixes”
  1. 0/3 delta-island fixesJeff King, Nov 20, 2018
  2. 1/3 pack-objects: fix tree_depth and layer invariantsJeff King, Nov 20, 2018
  3. Duy NguyenNov 20, 2018
  4. Jeff KingNov 22, 2018
  5. Junio C HamanoNov 21, 2018
  6. 2/3 pack-objects: zero-initialize tree_depth/layer arraysJeff King, Nov 20, 2018
  7. 3/3 pack-objects: fix off-by-one in delta-island tree-depth computationJeff King, Nov 20, 2018
  8. Derrick StoleeNov 20, 2018
  9. Jeff KingNov 22, 2018

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.