diff options
| -rw-r--r-- | builtin/pack-objects.c | 18 | ||||
| -rw-r--r-- | pack-objects.h | 4 | ||||
| -rwxr-xr-x | t/t5316-pack-delta-depth.sh | 93 |
3 files changed, 115 insertions, 0 deletions
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c index 0fd52bd6b..5c42a1d05 100644 --- a/builtin/pack-objects.c +++ b/builtin/pack-objects.c @@ -1541,6 +1541,8 @@ static int pack_offset_sort(const void *_a, const void *_b) * 2. Updating our size/type to the non-delta representation. These were * either not recorded initially (size) or overwritten with the delta type * (type) when check_object() decided to reuse the delta. + * + * 3. Resetting our delta depth, as we are now a base object. */ static void drop_reused_delta(struct object_entry *entry) { @@ -1554,6 +1556,7 @@ static void drop_reused_delta(struct object_entry *entry) p = &(*p)->delta_sibling; } entry->delta = NULL; + entry->depth = 0; oi.sizep = &entry->size; oi.typep = &entry->type; @@ -1572,6 +1575,9 @@ static void drop_reused_delta(struct object_entry *entry) * Follow the chain of deltas from this entry onward, throwing away any links * that cause us to hit a cycle (as determined by the DFS state flags in * the entries). + * + * We also detect too-long reused chains that would violate our --depth + * limit. */ static void break_delta_chains(struct object_entry *entry) { @@ -1589,6 +1595,18 @@ static void break_delta_chains(struct object_entry *entry) */ entry->dfs_state = DFS_ACTIVE; break_delta_chains(entry->delta); + + /* + * Once we've recursed, our base (if we still have one) knows + * its depth, so we can compute ours (and check it against + * the limit). + */ + if (entry->delta) { + entry->depth = entry->delta->depth + 1; + if (entry->depth > depth) + drop_reused_delta(entry); + } + entry->dfs_state = DFS_DONE; break; diff --git a/pack-objects.h b/pack-objects.h index cc9b9a9b9..03f119165 100644 --- a/pack-objects.h +++ b/pack-objects.h @@ -30,12 +30,16 @@ struct object_entry { /* * State flags for depth-first search used for analyzing delta cycles. + * + * The depth is measured in delta-links to the base (so if A is a delta + * against B, then A has a depth of 1, and B a depth of 0). */ enum { DFS_NONE = 0, DFS_ACTIVE, DFS_DONE } dfs_state; + int depth; }; struct packing_data { diff --git a/t/t5316-pack-delta-depth.sh b/t/t5316-pack-delta-depth.sh new file mode 100755 index 000000000..37143ea0a --- /dev/null +++ b/t/t5316-pack-delta-depth.sh @@ -0,0 +1,93 @@ +#!/bin/sh + +test_description='pack-objects breaks long cross-pack delta chains' +. ./test-lib.sh + +# This mirrors a repeated push setup: +# +# 1. A client repeatedly modifies some files, makes a +# commit, and pushes the result. It does this N times +# before we get around to repacking. +# +# 2. Each push generates a thin pack with the new version of +# various objects. Let's consider some file in the root tree +# which is updated in each commit. +# +# When generating push number X, we feed commit X-1 (and +# thus blob X-1) as a preferred base. The resulting pack has +# blob X as a thin delta against blob X-1. +# +# On the receiving end, "index-pack --fix-thin" will +# complete the pack with a base copy of blob X-1. +# +# 3. In older versions of git, if we used the delta from +# pack X, then we'd always find blob X-1 as a base in the +# same pack (and generate a fresh delta). +# +# But with the pack mru, we jump from delta to delta +# following the traversal order: +# +# a. We grab blob X from pack X as a delta, putting it at +# the tip of our mru list. +# +# b. Eventually we move onto commit X-1. We need other +# objects which are only in pack X-1 (in the test code +# below, it's the containing tree). That puts pack X-1 +# at the tip of our mru list. +# +# c. Eventually we look for blob X-1, and we find the +# version in pack X-1 (because it's the mru tip). +# +# Now we have blob X as a delta against X-1, which is a delta +# against X-2, and so forth. +# +# In the real world, these small pushes would get exploded by +# unpack-objects rather than "index-pack --fix-thin", but the +# same principle applies to larger pushes (they only need one +# repeatedly-modified file to generate the delta chain). + +test_expect_success 'create series of packs' ' + test-genrandom foo 4096 >content && + prev= && + for i in $(test_seq 1 10) + do + cat content >file && + echo $i >>file && + git add file && + git commit -m $i && + cur=$(git rev-parse HEAD^{tree}) && + { + test -n "$prev" && echo "-$prev" + echo $cur + echo "$(git rev-parse :file) file" + } | git pack-objects --stdout >tmp && + git index-pack --stdin --fix-thin <tmp || return 1 + prev=$cur + done +' + +max_chain() { + git index-pack --verify-stat-only "$1" >output && + perl -lne ' + /chain length = (\d+)/ and $len = $1; + END { print $len } + ' output +} + +# Note that this whole setup is pretty reliant on the current +# packing heuristics. We double-check that our test case +# actually produces a long chain. If it doesn't, it should be +# adjusted (or scrapped if the heuristics have become too unreliable) +test_expect_success 'packing produces a long delta' ' + # Use --window=0 to make sure we are seeing reused deltas, + # not computing a new long chain. + pack=$(git pack-objects --all --window=0 </dev/null pack) && + test 9 = "$(max_chain pack-$pack.pack)" +' + +test_expect_success '--depth limits depth' ' + pack=$(git pack-objects --all --depth=5 </dev/null pack) && + test 5 = "$(max_chain pack-$pack.pack)" +' + +test_done |