Commits on Nov 21, 2018

1. pack-objects: fix tree_depth and layer invariants …

   Commit 108f530 (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.
   
   That doesn't happen in our test scripts, because the repositories they
   use are so small, but it's easy to trigger by running:
   
     echo HEAD | git pack-objects --revs --delta-islands --stdout >/dev/null
   
   in any reasonably-sized repo (like git.git).
   
   We can fix it by always growing the array to match pack->nr_alloc, not
   pack->nr_objects. Likewise for the "layer" array from fe0ac2f
   (pack-objects: move 'layer' into 'struct packing_data', 2018-08-16),
   which has the same bug.
   
   Signed-off-by: Jeff King <peff@peff.net>
   Signed-off-by: Junio C Hamano <gitster@pobox.com>

   

   peff authored and gitster committed Nov 21, 2018
   Configuration menu

   • View commit details
   • Copy full SHA for bc35ac1
   • Browse repository at this point

   Copy the full SHA

   bc35ac1 View commit details

   Browse the repository at this point in the history

2. pack-objects: zero-initialize tree_depth/layer arrays …

   Commit 108f530 (pack-objects: move tree_depth into 'struct
   packing_data', 2018-08-16) started maintaining a tree_depth array that
   matches the "objects" array. We extend the array when:
   
     1. The objects array is extended, in which case we use realloc to
        extend the tree_depth array.
   
     2. A caller asks to store a tree_depth for object N, and this is the
        first such request; we create the array from scratch and store the
        value for N.
   
   In the latter case, though, we use regular xmalloc(), and the depth
   values for any objects besides N is undefined. This happens to not
   trigger a bug with the current code, but the reasons are quite subtle:
   
    - we never ask about the depth for any object with index i < N. This is
      because we store the depth immediately for all trees and blobs. So
      any such "i" must be a non-tree, and therefore we will never need to
      care about its depth (in fact, we really only care about the depth of
      trees).
   
    - there are no objects at this point with index i > N, because we
      always fill in the depth for a tree immediately after its object
      entry is created (we may still allocate uninitialized depth entries,
      but they'll be initialized by packlist_alloc() when it initializes
      the entry in the "objects" array).
   
   So it works, but only by chance. To be defensive, let's zero the array,
   which matches the "unset" values which would be handed out by
   oe_tree_depth() already.
   
   Signed-off-by: Jeff King <peff@peff.net>
   Signed-off-by: Junio C Hamano <gitster@pobox.com>

   

   peff authored and gitster committed Nov 21, 2018
   Configuration menu

   • View commit details
   • Copy full SHA for e159b81
   • Browse repository at this point

   Copy the full SHA

   e159b81 View commit details

   Browse the repository at this point in the history

3. pack-objects: fix off-by-one in delta-island tree-depth computation …

   When delta-islands are in use, we need to record the deepest path at
   which we find each tree and blob. Our loop to do so counts slashes, so
   "foo" is depth 0, "foo/bar" is depth 1, and so on.
   
   However, this neglects root trees, which are represented by the empty
   string. Those also have depth 0, but are at a layer above "foo". Thus,
   "foo" should be 1, "foo/bar" at 2, and so on. We use this depth to
   topo-sort the trees in resolve_tree_islands(). As a result, we may fail
   to visit a root tree before the sub-trees it contains, and therefore not
   correctly pass down the island marks.
   
   That in turn could lead to missing some delta opportunities (objects are
   in the same island, but we didn't realize it) or creating unwanted
   cross-island deltas (one object is in an island another isn't, but we
   don't realize). In practice, it seems to have only a small effect.  Some
   experiments on the real-world git/git fork network at GitHub showed an
   improvement of only 0.14% in the resulting clone size.
   
   Signed-off-by: Jeff King <peff@peff.net>
   Signed-off-by: Junio C Hamano <gitster@pobox.com>

   

   peff authored and gitster committed Nov 21, 2018
   Configuration menu

   • View commit details
   • Copy full SHA for 3949053
   • Browse repository at this point

   Copy the full SHA

   3949053 View commit details

   Browse the repository at this point in the history