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
Duy Nguyen <pclouds@gmail.com>
Date
Nov 20, 2018, 16:37 UTC
Message-ID
<CACsJy8AETNxNnEq-8ROrQTkjy-_9mtoprmc=BQ554f7QECajPw@mail.gmail.com>
In-Reply-To
<20181120094638.GA22742@sigill.intra.peff.net>
On Tue, Nov 20, 2018 at 11:04 AM Jeff King <peff@peff.net> wrote:
Show 31 quoted lines
>
> Commit 108f530385 (pack-objects: move tree_depth into 'struct
> packing_data', 2018-08-16) dynamically manages a tree_depth array in
> packing_data that maintains one of these invariants:
>
>   1. tree_depth is NULL (i.e., the requested options don't require us to
>      track tree depths)
>
>   2. tree_depth is non-NULL and has as many entries as the "objects"
>      array
>
> We maintain (2) by:
>
>   a. When the objects array grows, grow tree_depth to the same size
>      (unless it's NULL, in which case we can leave it).
>
>   b. When a caller asks to set a depth via oe_set_tree_depth(), if
>      tree_depth is NULL we allocate it.
>
> 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.

Do you think if this splitting data to packing_data is too fragile that we should just scrape the whole thing and move all data back to object_entry[]? We would use more memory of course but higher memory usage is still better than more bugs (if these are likely to show up again).

-- 
Duy
Previous: Jeff KingNext: Jeff King
Message 3 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.