{"thread":{"id":"44991","subject":"[PATCH 0/2] limit reused delta chains based on --depth","startedAt":"2017-01-27T22:03:03Z","lastAt":"2017-01-28T01:02:17Z","messageCount":6,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"310446","messageId":"20170127220143.boo5phhgogqlucsj@sigill.intra.peff.net","threadId":"44991","inReplyTo":null,"subject":"[PATCH 0/2] limit reused delta chains based on --depth","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-01-27T22:01:44Z","receivedAt":"2017-01-27T22:03:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Back when we switched pack-objects to visiting packs in\nmost-recently-used order last August, we realized that this could reuse\ncross-pack deltas, and that the result could have longer delta chains\nthan any single pack contains.\n\nI produced a patch back then[1], but we decided not to follow through\nwith it. Two things happened to make me revive that patch:\n\n 1. I hit a case in the wild with a really long delta chain that caused\n pack-objects' write_one() to run out of stack space.\n\n 2. We dropped the --aggressive depth to match the normal one. So\n there's less concern about mismatches throwing out on-disk deltas\n from a previous aggressive repack (but see the caveats in the first\n patch's commit message).\n\nSo here it is, plus another patch that converts the recursion to\niteration (the stack space needed by the function is small enough that\njust the first patch was enough to fix my problem case, but it seemed\nlike tempting fate to leave it recursive).\n\n [1/2]: pack-objects: enforce --depth limit in reused deltas\n [2/2]: pack-objects: convert recursion to iteration in break_delta_chain()\n\n builtin/pack-objects.c | 133 ++++++++++++++++++++++++++++++++++++--------\n pack-objects.h | 4 ++\n t/t5316-pack-delta-depth.sh | 93 +++++++++++++++++++++++++++++++\n 3 files changed, 207 insertions(+), 23 deletions(-)\n create mode 100755 t/t5316-pack-delta-depth.sh\n\n-Peff\n\n[1] http://public-inbox.org/git/20160811095710.p2bffympjlwmv3gc@sigill.intra.peff.net/\n"},{"id":"310447","messageId":"20170127220233.mwg36mgxdklwz7lr@sigill.intra.peff.net","threadId":"44991","inReplyTo":"20170127220143.boo5phhgogqlucsj@sigill.intra.peff.net","subject":"[PATCH 1/2] pack-objects: enforce --depth limit in reused deltas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-01-27T22:02:33Z","receivedAt":"2017-01-27T22:03:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Since 898b14c (pack-objects: rework check_delta_limit usage,\n2007-04-16), we check the delta depth limit only when\nfiguring out whether we should make a new delta. We don't\nconsider it at all when reusing deltas, which means that\npacking once with --depth=250, and then again with\n--depth=50, the second pack my still contain chains larger\nthan 50.\n\nThis is generally considered a feature, as the results of\nearlier high-depth repacks are carried forward, used for\nserving fetches, etc. However, since we started using\ncross-pack deltas in c9af708b1 (pack-objects: use mru list\nwhen iterating over packs, 2016-08-11), we are no longer\nbounded by the length of an existing delta chain in a single\npack.\n\nHere's one particular pathological case: a sequence of N\npacks, each with 2 objects, the base of which is stored as a\ndelta in a previous pack. If we chain all the deltas\ntogether, we have a cycle of length N. We break the cycle,\nbut the tip delta is still at depth N-1.\n\nThis is less unlikely than it might sound. See the included\ntest for a reconstruction based on real-world actions. I\nran into such a case in the wild, where a client was rapidly\nsending packs, and we had accumulated 10,000 before doing a\nserver-side repack. The pack that \"git repack\" tried to\ngenerate had a very deep chain, which caused pack-objects to\nrun out of stack space in the recursive write_one().\n\nThis patch bounds the length of delta chains in the output\npack based on --depth, regardless of whether they are caused\nby cross-pack deltas or existed in the input packs. This\nfixes the problem, but does have two possible downsides:\n\n 1. High-depth aggressive repacks followed by \"normal\"\n repacks will throw away the high-depth chains.\n\n In the long run this is probably OK; investigation\n showed that high-depth repacks aren't actually\n beneficial, and we dropped the aggressive depth default\n to match the normal case in 07e7dbf0d (gc: default\n aggressive depth to 50, 2016-08-11).\n\n 2. If you really do want to store high-depth deltas on\n disk, they may be discarded and new delta computed when\n serving a fetch, unless you set pack.depth to match\n your high-depth size.\n\nThe implementation uses the existing search for delta\ncycles. That lets us compute the depth of any node based on\nthe depth of its base, because we know the base is DFS_DONE\nby the time we look at it (modulo any cycles in the graph,\nbut we know there cannot be any because we break them as we\nsee them).\n\nThere is some subtlety worth mentioning, though. We record\nthe depth of each object as we compute it. It might seem\nlike we could save the per-object storage space by just\nkeeping track of the depth of our traversal (i.e., have\nbreak_delta_chains() report how deep it went). But we may\nvisit an object through multiple delta paths, and on\nsubsequent paths we want to know its depth immediately,\nwithout having to walk back down to its final base (doing so\nwould make our graph walk quadratic rather than linear).\n\nLikewise, one could try to record the depth not from the\nbase, but from our starting point (i.e., start\nrecursion_depth at 0, and pass \"recursion_depth + 1\" to each\ninvocation of break_delta_chains()). And then when\nrecursion_depth gets too big, we know that we must cut the\ndelta chain. But that technique is wrong if we do not visit\nthe nodes in topological order. In a chain A->B->C, it\nif we visit \"C\", then \"B\", then \"A\", we will never recurse\ndeeper than 1 link (because we see at each node that we have\nalready visited it).\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 18 +++++++++\n pack-objects.h | 4 ++\n t/t5316-pack-delta-depth.sh | 93 +++++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 115 insertions(+)\n create mode 100755 t/t5316-pack-delta-depth.sh\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 8841f8b36..2b08c8121 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1539,6 +1539,8 @@ static int pack_offset_sort(const void *_a, const void *_b)\n * 2. Updating our size/type to the non-delta representation. These were\n * either not recorded initially (size) or overwritten with the delta type\n * (type) when check_object() decided to reuse the delta.\n+ *\n+ * 3. Resetting our delta depth, as we are now a base object.\n */\n static void drop_reused_delta(struct object_entry *entry)\n {\n@@ -1552,6 +1554,7 @@ static void drop_reused_delta(struct object_entry *entry)\n \t\t\tp = &(*p)->delta_sibling;\n \t}\n \tentry->delta = NULL;\n+\tentry->depth = 0;\n \n \toi.sizep = &entry->size;\n \toi.typep = &entry->type;\n@@ -1570,6 +1573,9 @@ static void drop_reused_delta(struct object_entry *entry)\n * Follow the chain of deltas from this entry onward, throwing away any links\n * that cause us to hit a cycle (as determined by the DFS state flags in\n * the entries).\n+ *\n+ * We also detect too-long reused chains that would violate our --depth\n+ * limit.\n */\n static void break_delta_chains(struct object_entry *entry)\n {\n@@ -1587,6 +1593,18 @@ static void break_delta_chains(struct object_entry *entry)\n \t\t */\n \t\tentry->dfs_state = DFS_ACTIVE;\n \t\tbreak_delta_chains(entry->delta);\n+\n+\t\t/*\n+\t\t * Once we've recursed, our base (if we still have one) knows\n+\t\t * its depth, so we can compute ours (and check it against\n+\t\t * the limit).\n+\t\t */\n+\t\tif (entry->delta) {\n+\t\t\tentry->depth = entry->delta->depth + 1;\n+\t\t\tif (entry->depth > depth)\n+\t\t\t\tdrop_reused_delta(entry);\n+\t\t}\n+\n \t\tentry->dfs_state = DFS_DONE;\n \t\tbreak;\n \ndiff --git a/pack-objects.h b/pack-objects.h\nindex cc9b9a9b9..03f119165 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -30,12 +30,16 @@ struct object_entry {\n \n \t/*\n \t * State flags for depth-first search used for analyzing delta cycles.\n+\t *\n+\t * The depth is measured in delta-links to the base (so if A is a delta\n+\t * against B, then A has a depth of 1, and B a depth of 0).\n \t */\n \tenum {\n \t\tDFS_NONE = 0,\n \t\tDFS_ACTIVE,\n \t\tDFS_DONE\n \t} dfs_state;\n+\tint depth;\n };\n \n struct packing_data {\ndiff --git a/t/t5316-pack-delta-depth.sh b/t/t5316-pack-delta-depth.sh\nnew file mode 100755\nindex 000000000..236d60fe6\n--- /dev/null\n+++ b/t/t5316-pack-delta-depth.sh\n@@ -0,0 +1,93 @@\n+#!/bin/sh\n+\n+test_description='pack-objects breaks long cross-pack delta chains'\n+. ./test-lib.sh\n+\n+# This mirrors a repeated push setup:\n+#\n+# 1. A client repeatedly modifies some files, makes a\n+# commit, and pushes the result. It does this N times\n+# before we get around to repacking.\n+#\n+# 2. Each push generates a thin pack with the new version of\n+# various objects. Let's consider some file in the root tree\n+# which is updated in each commit.\n+#\n+# When generating push number X, we feed commit X-1 (and\n+# thus blob X-1) as a preferred base. The resulting pack has\n+# blob X as a thin delta against blob X-1.\n+#\n+# On the receiving end, \"index-pack --fix-thin\" will\n+# complete the pack with a base copy of tree X-1.\n+#\n+# 3. In older versions of git, if we used the delta from\n+# pack X, then we'd always find blob X-1 as a base in the\n+# same pack (and generate a fresh delta).\n+#\n+# But with the pack mru, we jump from delta to delta\n+# following the traversal order:\n+#\n+# a. We grab blob X from pack X as a delta, putting it at\n+# the tip of our mru list.\n+#\n+# b. Eventually we move onto commit X-1. We need other\n+# objects which are only in pack X-1 (in the test code\n+# below, it's the containing tree). That puts pack X-1\n+# at the tip of our mru list.\n+#\n+# c. Eventually we look for blob X-1, and we find the\n+# version in pack X-1 (because it's the mru tip).\n+#\n+# Now we have blob X as a delta against X-1, which is a delta\n+# against X-2, and so forth.\n+#\n+# In the real world, these small pushes would get exploded by\n+# unpack-objects rather than \"index-pack --fix-thin\", but the\n+# same principle applies to larger pushes (they only need one\n+# repeatedly-modified file to generate the delta chain).\n+\n+test_expect_success 'create series of packs' '\n+\ttest-genrandom foo 4096 >content &&\n+\tprev= &&\n+\tfor i in $(test_seq 1 10)\n+\tdo\n+\t\tcat content >file &&\n+\t\techo $i >>file &&\n+\t\tgit add file &&\n+\t\tgit commit -m $i &&\n+\t\tcur=$(git rev-parse HEAD^{tree}) &&\n+\t\t{\n+\t\t\ttest -n \"$prev\" && echo \"-$prev\"\n+\t\t\techo $cur\n+\t\t\techo \"$(git rev-parse :file) file\"\n+\t\t} | git pack-objects --stdout >tmp &&\n+\t\tgit index-pack --stdin --fix-thin output &&\n+\tperl -lne '\n+\t /chain length = (\\d+)/ and $len = $1;\n+\t END { print $len }\n+\t' output\n+}\n+\n+# Note that this whole setup is pretty reliant on the current\n+# packing heuristics. We double-check that our test case\n+# actually produces a long chain. If it doesn't, it should be\n+# adjusted (or scrapped if the heuristics have become too unreliable)\n+test_expect_success 'packing produces a long delta' '\n+\t# Use --window=0 to make sure we are seeing reused deltas,\n+\t# not computing a new long chain.\n+\tpack=$(git pack-objects --all --window=0 \n---\nThe diff is nearly impossible to read, so I'd recommend just looking at\nthe end result. I tried to document the tricky parts with comments.\nThere are a few parts that could be made more terse, but I screwed it up\nso many times while writing it that I decided to do it in a way that\ncarefully documents all of the assumptions.\n\n builtin/pack-objects.c | 129 +++++++++++++++++++++++++++++++++++++------------\n 1 file changed, 99 insertions(+), 30 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 2b08c8121..c7af47548 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1579,48 +1579,117 @@ static void drop_reused_delta(struct object_entry *entry)\n */\n static void break_delta_chains(struct object_entry *entry)\n {\n-\t/* If it's not a delta, it can't be part of a cycle. */\n-\tif (!entry->delta) {\n-\t\tentry->dfs_state = DFS_DONE;\n-\t\treturn;\n-\t}\n+\t/*\n+\t * The actual depth of each object we will write is stored as an int,\n+\t * as it cannot exceed our int \"depth\" limit. But before we break\n+\t * changes based no that limit, we may potentially go as deep as the\n+\t * number of objects, which is elsewhere bounded to a uint32_t.\n+\t */\n+\tuint32_t total_depth;\n+\tstruct object_entry *cur, *next;\n+\n+\tfor (cur = entry, total_depth = 0;\n+\t cur;\n+\t cur = cur->delta, total_depth++) {\n+\t\tif (cur->dfs_state == DFS_DONE) {\n+\t\t\t/*\n+\t\t\t * We've already seen this object and know it isn't\n+\t\t\t * part of a cycle. We do need to append its depth\n+\t\t\t * to our count.\n+\t\t\t */\n+\t\t\ttotal_depth += cur->depth;\n+\t\t\tbreak;\n+\t\t}\n \n-\tswitch (entry->dfs_state) {\n-\tcase DFS_NONE:\n \t\t/*\n-\t\t * This is the first time we've seen the object. We mark it as\n-\t\t * part of the active potential cycle and recurse.\n+\t\t * We break cycles before looping, so an ACTIVE state (or any\n+\t\t * other cruft which made its way into the state variable)\n+\t\t * is a bug.\n \t\t */\n-\t\tentry->dfs_state = DFS_ACTIVE;\n-\t\tbreak_delta_chains(entry->delta);\n+\t\tif (cur->dfs_state != DFS_NONE)\n+\t\t\tdie(\"BUG: confusing delta dfs state in first pass: %d\",\n+\t\t\t cur->dfs_state);\n \n \t\t/*\n-\t\t * Once we've recursed, our base (if we still have one) knows\n-\t\t * its depth, so we can compute ours (and check it against\n-\t\t * the limit).\n+\t\t * Now we know this is the first time we've seen the object. If\n+\t\t * it's not a delta, we're done traversing, but we'll mark it\n+\t\t * done to save time on future traversals.\n \t\t */\n-\t\tif (entry->delta) {\n-\t\t\tentry->depth = entry->delta->depth + 1;\n-\t\t\tif (entry->depth > depth)\n-\t\t\t\tdrop_reused_delta(entry);\n+\t\tif (!cur->delta) {\n+\t\t\tcur->dfs_state = DFS_DONE;\n+\t\t\tbreak;\n \t\t}\n \n-\t\tentry->dfs_state = DFS_DONE;\n-\t\tbreak;\n+\t\t/*\n+\t\t * Mark ourselves as active and see if the next step causes\n+\t\t * us to cycle to another active object. It's important to do\n+\t\t * this _before_ we loop, because it impacts where we make the\n+\t\t * cut, and thus how our total_depth counter works.\n+\t\t * E.g., We may see a partial loop like:\n+\t\t *\n+\t\t * A -> B -> C -> D -> B\n+\t\t *\n+\t\t * Cutting B->C breaks the cycle. But now the depth of A is\n+\t\t * only 1, and our total_depth counter is at 3. The size of the\n+\t\t * error is always one less than the size of the cycle we\n+\t\t * broke. Commits C and D were \"lost\" from A's chain.\n+\t\t *\n+\t\t * If we instead cut D->B, then the depth of A is correct at 3.\n+\t\t * We keep all commits in the chain that we examined.\n+\t\t */\n+\t\tcur->dfs_state = DFS_ACTIVE;\n+\t\tif (cur->delta->dfs_state == DFS_ACTIVE) {\n+\t\t\tdrop_reused_delta(cur);\n+\t\t\tcur->dfs_state = DFS_DONE;\n+\t\t\tbreak;\n+\t\t}\n+\t}\n \n-\tcase DFS_DONE:\n-\t\t/* object already examined, and not part of a cycle */\n-\t\tbreak;\n+\t/*\n+\t * And now that we've gone all the way to the bottom of the chain, we\n+\t * need to clear the active flags and set the depth fields as\n+\t * appropriate. Unlike the loop above, which can quit when it drops a\n+\t * delta, we need to keep going to look for more depth cuts. So we need\n+\t * an extra \"next\" pointer to keep going after we reset cur->delta.\n+\t */\n+\tfor (cur = entry; cur; cur = next) {\n+\t\tnext = cur->delta;\n \n-\tcase DFS_ACTIVE:\n \t\t/*\n-\t\t * We found a cycle that needs broken. It would be correct to\n-\t\t * break any link in the chain, but it's convenient to\n-\t\t * break this one.\n+\t\t * We should have a chain of zero or more ACTIVE states down to\n+\t\t * a final DONE. We can quit after the DONE, because either it\n+\t\t * has no bases, or we've already handled them in a previous\n+\t\t * call.\n \t\t */\n-\t\tdrop_reused_delta(entry);\n-\t\tentry->dfs_state = DFS_DONE;\n-\t\tbreak;\n+\t\tif (cur->dfs_state == DFS_DONE)\n+\t\t\tbreak;\n+\t\telse if (cur->dfs_state != DFS_ACTIVE)\n+\t\t\tdie(\"BUG: confusing delta dfs state in second pass: %d\",\n+\t\t\t cur->dfs_state);\n+\n+\t\t/*\n+\t\t * If the total_depth is more than depth, then we need to snip\n+\t\t * the chain into two or more smaller chains that don't exceed\n+\t\t * the maximum depth. Most of the resulting chains will contain\n+\t\t * (depth + 1) entries (i.e., depth deltas plus one base), and\n+\t\t * the last chain (i.e., the one containing entry) will contain\n+\t\t * whatever entries are left over, namely\n+\t\t * (total_depth % (depth + 1)) of them.\n+\t\t *\n+\t\t * Since we are iterating towards decreasing depth, we need to\n+\t\t * decrement total_depth as we go, and we need to write to the\n+\t\t * entry what its final depth will be after all of the\n+\t\t * snipping. Since we're snipping into chains of length (depth\n+\t\t * + 1) entries, the final depth of an entry will be its\n+\t\t * original depth modulo (depth + 1). Any time we encounter an\n+\t\t * entry whose final depth is supposed to be zero, we snip it\n+\t\t * from its delta base, thereby making it so.\n+\t\t */\n+\t\tcur->depth = (total_depth--) % (depth + 1);\n+\t\tif (!cur->depth)\n+\t\t\tdrop_reused_delta(cur);\n+\n+\t\tcur->dfs_state = DFS_DONE;\n \t}\n }\n \n-- \n2.11.0.914.gb3b960f50\n"},{"id":"310452","messageId":"xmqqinp0xep3.fsf@gitster.mtv.corp.google.com","threadId":"44991","inReplyTo":"20170127220233.mwg36mgxdklwz7lr@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] pack-objects: enforce --depth limit in reused deltas","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-01-27T23:31:36Z","receivedAt":"2017-01-27T23:31:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Since 898b14c (pack-objects: rework check_delta_limit usage,\n> 2007-04-16), we check the delta depth limit only when\n> figuring out whether we should make a new delta. We don't\n> consider it at all when reusing deltas, which means that\n> packing once with --depth=250, and then again with\n> --depth=50, the second pack my still contain chains larger\n> than 50.\n\n\"may still contain\", methinks.\n\n> ...\n>\n> This patch bounds the length of delta chains in the output\n> pack based on --depth, regardless of whether they are caused\n> by cross-pack deltas or existed in the input packs. This\n> fixes the problem, but does have two possible downsides:\n>\n> 1. High-depth aggressive repacks followed by \"normal\"\n> repacks will throw away the high-depth chains.\n\nI actually think it is a feature that the normal one that runs later\nis allowed to fix an over-deep delta chain.\n\n> 2. If you really do want to store high-depth deltas on\n> disk, they may be discarded and new delta computed when\n> serving a fetch, unless you set pack.depth to match\n> your high-depth size.\n\nLikewise.\n\n> ... But we may\n> visit an object through multiple delta paths, ...\n\nYes, good thinking.\n\n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index 8841f8b36..2b08c8121 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n> @@ -1539,6 +1539,8 @@ static int pack_offset_sort(const void *_a, const void *_b)\n> * 2. Updating our size/type to the non-delta representation. These were\n> * either not recorded initially (size) or overwritten with the delta type\n> * (type) when check_object() decided to reuse the delta.\n> + *\n> + * 3. Resetting our delta depth, as we are now a base object.\n> */\n> static void drop_reused_delta(struct object_entry *entry)\n> {\n> @@ -1552,6 +1554,7 @@ static void drop_reused_delta(struct object_entry *entry)\n> \t\t\tp = &(*p)->delta_sibling;\n> \t}\n> \tentry->delta = NULL;\n> +\tentry->depth = 0;\n> \n> \toi.sizep = &entry->size;\n> \toi.typep = &entry->type;\n\nMakes sense.\n\n> static void break_delta_chains(struct object_entry *entry)\n> {\n> @@ -1587,6 +1593,18 @@ static void break_delta_chains(struct object_entry *entry)\n> \t\t */\n> \t\tentry->dfs_state = DFS_ACTIVE;\n> \t\tbreak_delta_chains(entry->delta);\n> +\n> +\t\t/*\n> +\t\t * Once we've recursed, our base (if we still have one) knows\n> +\t\t * its depth, so we can compute ours (and check it against\n> +\t\t * the limit).\n> +\t\t */\n> +\t\tif (entry->delta) {\n> +\t\t\tentry->depth = entry->delta->depth + 1;\n> +\t\t\tif (entry->depth > depth)\n> +\t\t\t\tdrop_reused_delta(entry);\n> +\t\t}\n\n;-) Surprisingly simpple and effective.\n\n> diff --git a/t/t5316-pack-delta-depth.sh b/t/t5316-pack-delta-depth.sh\n> new file mode 100755\n> index 000000000..236d60fe6\n> --- /dev/null\n> +++ b/t/t5316-pack-delta-depth.sh\n> @@ -0,0 +1,93 @@\n> +#!/bin/sh\n> +\n> +test_description='pack-objects breaks long cross-pack delta chains'\n> +. ./test-lib.sh\n> +\n> +# This mirrors a repeated push setup:\n> +#\n> +# 1. A client repeatedly modifies some files, makes a\n> +# commit, and pushes the result. It does this N times\n> +# before we get around to repacking.\n> +#\n> +# 2. Each push generates a thin pack with the new version of\n> +# various objects. Let's consider some file in the root tree\n> +# which is updated in each commit.\n> +#\n> +# When generating push number X, we feed commit X-1 (and\n> +# thus blob X-1) as a preferred base. The resulting pack has\n> +# blob X as a thin delta against blob X-1.\n> +#\n> +# On the receiving end, \"index-pack --fix-thin\" will\n> +# complete the pack with a base copy of tree X-1.\n\nblob? tree? I think the argument would work the same way for either\ntype of objects, but the previous paragraph is using blob as the\nexample, so s/tree/blob/ here?\n\n> +# 3. In older versions of git, if we used the delta from\n> +# pack X, then we'd always find blob X-1 as a base in the\n> +# same pack (and generate a fresh delta).\n> +#\n> +# But with the pack mru, we jump from delta to delta\n> +# following the traversal order:\n> +# ...\n> +# Now we have blob X as a delta against X-1, which is a delta\n> +# against X-2, and so forth.\n\n> +# Note that this whole setup is pretty reliant on the current\n> +# packing heuristics. We double-check that our test case\n> +# actually produces a long chain. If it doesn't, it should be\n> +# adjusted (or scrapped if the heuristics have become too unreliable)\n\nIOW, we want something that says \"we first check X and if X still\nholds, then we expect Y to also hold; if X no longer hold, do not\nbother to test that Y holds\". Nice food for thought. Perhaps we\nwant a way to express that in our test framework, or is X in the\nabove merely another way to say \"prerequisite\"?\n\n> +test_expect_success 'packing produces a long delta' '\n> +\t# Use --window=0 to make sure we are seeing reused deltas,\n> +\t# not computing a new long chain.\n> +\tpack=$(git pack-objects --all --window=0 +\ttest 9 = \"$(max_chain pack-$pack.pack)\"\n> +'\n> +\n> +test_expect_success '--depth limits depth' '\n> +\tpack=$(git pack-objects --all --depth=5 +\ttest 5 = \"$(max_chain pack-$pack.pack)\"\n> +'\n> +\n> +test_done\n"},{"id":"310454","messageId":"20170128000959.l7aztgu46ytkhmk3@sigill.intra.peff.net","threadId":"44991","inReplyTo":"xmqqinp0xep3.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/2] pack-objects: enforce --depth limit in reused deltas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-01-28T00:09:59Z","receivedAt":"2017-01-28T00:16:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 27, 2017 at 03:31:36PM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > Since 898b14c (pack-objects: rework check_delta_limit usage,\n> > 2007-04-16), we check the delta depth limit only when\n> > figuring out whether we should make a new delta. We don't\n> > consider it at all when reusing deltas, which means that\n> > packing once with --depth=250, and then again with\n> > --depth=50, the second pack my still contain chains larger\n> > than 50.\n> \n> \"may still contain\", methinks.\n\nOops, yes. There was another typo there that I fixed while proofreading,\nand clearly I made it worse. :-/\n\n> > This patch bounds the length of delta chains in the output\n> > pack based on --depth, regardless of whether they are caused\n> > by cross-pack deltas or existed in the input packs. This\n> > fixes the problem, but does have two possible downsides:\n> >\n> > 1. High-depth aggressive repacks followed by \"normal\"\n> > repacks will throw away the high-depth chains.\n> \n> I actually think it is a feature that the normal one that runs later\n> is allowed to fix an over-deep delta chain.\n\nYeah, I saw you expressing that sentiment in the earlier thread, and I\nthink I agree with it.\n\nThe big problem to me is mostly that people may be surprised by the\nchange of behavior if they have a complicated setup. But those people\nread the release notes, right? ;)\n\nArguably setting gc.aggressiveDepth is a mistake after this patch (you\nshould just set pack.depth). Possibly we should ignore it with a\nwarning.\n\n> > +# On the receiving end, \"index-pack --fix-thin\" will\n> > +# complete the pack with a base copy of tree X-1.\n> \n> blob? tree? I think the argument would work the same way for either\n> type of objects, but the previous paragraph is using blob as the\n> example, so s/tree/blob/ here?\n\nOops, yes. I had originally sketched out the example to use trees, but\nit was easier to assemble with blobs so I switched (I never actually dug\ninto my \"wild\" case to see what it was segfaulting on, but I agree it\napplies equally well to either).\n\n> > +# Note that this whole setup is pretty reliant on the current\n> > +# packing heuristics. We double-check that our test case\n> > +# actually produces a long chain. If it doesn't, it should be\n> > +# adjusted (or scrapped if the heuristics have become too unreliable)\n> \n> IOW, we want something that says \"we first check X and if X still\n> holds, then we expect Y to also hold; if X no longer hold, do not\n> bother to test that Y holds\". Nice food for thought. Perhaps we\n> want a way to express that in our test framework, or is X in the\n> above merely another way to say \"prerequisite\"?\n\nIt _is_ a prerequisite, but I think unlike our normal prerequisites, we\nwouldn't want to just quietly skip the test if it fails. Because it's\nnot \"oops, this system doesn't support this test\" so much as \"something\nin Git changed, and a human needs to evaluate whether this test can\nstill be performed\".\n\nSo I hoped that if that prerequisite test ever broke due to a change in\npack-objects, the person making the change would find the comment and\ndecide the appropriate next step.\n\nI'll include a version below fixing the typos you found, in case you did\nnot just mark them up already.\n\n-- >8 --\nSubject: [PATCH] pack-objects: enforce --depth limit in reused deltas\n\nSince 898b14c (pack-objects: rework check_delta_limit usage,\n2007-04-16), we check the delta depth limit only when\nfiguring out whether we should make a new delta. We don't\nconsider it at all when reusing deltas, which means that\npacking once with --depth=250, and then again with\n--depth=50, the second pack may still contain chains larger\nthan 50.\n\nThis is generally considered a feature, as the results of\nearlier high-depth repacks are carried forward, used for\nserving fetches, etc. However, since we started using\ncross-pack deltas in c9af708b1 (pack-objects: use mru list\nwhen iterating over packs, 2016-08-11), we are no longer\nbounded by the length of an existing delta chain in a single\npack.\n\nHere's one particular pathological case: a sequence of N\npacks, each with 2 objects, the base of which is stored as a\ndelta in a previous pack. If we chain all the deltas\ntogether, we have a cycle of length N. We break the cycle,\nbut the tip delta is still at depth N-1.\n\nThis is less unlikely than it might sound. See the included\ntest for a reconstruction based on real-world actions. I\nran into such a case in the wild, where a client was rapidly\nsending packs, and we had accumulated 10,000 before doing a\nserver-side repack. The pack that \"git repack\" tried to\ngenerate had a very deep chain, which caused pack-objects to\nrun out of stack space in the recursive write_one().\n\nThis patch bounds the length of delta chains in the output\npack based on --depth, regardless of whether they are caused\nby cross-pack deltas or existed in the input packs. This\nfixes the problem, but does have two possible downsides:\n\n 1. High-depth aggressive repacks followed by \"normal\"\n repacks will throw away the high-depth chains.\n\n In the long run this is probably OK; investigation\n showed that high-depth repacks aren't actually\n beneficial, and we dropped the aggressive depth default\n to match the normal case in 07e7dbf0d (gc: default\n aggressive depth to 50, 2016-08-11).\n\n 2. If you really do want to store high-depth deltas on\n disk, they may be discarded and new delta computed when\n serving a fetch, unless you set pack.depth to match\n your high-depth size.\n\nThe implementation uses the existing search for delta\ncycles. That lets us compute the depth of any node based on\nthe depth of its base, because we know the base is DFS_DONE\nby the time we look at it (modulo any cycles in the graph,\nbut we know there cannot be any because we break them as we\nsee them).\n\nThere is some subtlety worth mentioning, though. We record\nthe depth of each object as we compute it. It might seem\nlike we could save the per-object storage space by just\nkeeping track of the depth of our traversal (i.e., have\nbreak_delta_chains() report how deep it went). But we may\nvisit an object through multiple delta paths, and on\nsubsequent paths we want to know its depth immediately,\nwithout having to walk back down to its final base (doing so\nwould make our graph walk quadratic rather than linear).\n\nLikewise, one could try to record the depth not from the\nbase, but from our starting point (i.e., start\nrecursion_depth at 0, and pass \"recursion_depth + 1\" to each\ninvocation of break_delta_chains()). And then when\nrecursion_depth gets too big, we know that we must cut the\ndelta chain. But that technique is wrong if we do not visit\nthe nodes in topological order. In a chain A->B->C, it\nif we visit \"C\", then \"B\", then \"A\", we will never recurse\ndeeper than 1 link (because we see at each node that we have\nalready visited it).\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 18 +++++++++\n pack-objects.h | 4 ++\n t/t5316-pack-delta-depth.sh | 93 +++++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 115 insertions(+)\n create mode 100755 t/t5316-pack-delta-depth.sh\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 8841f8b36..2b08c8121 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1539,6 +1539,8 @@ static int pack_offset_sort(const void *_a, const void *_b)\n * 2. Updating our size/type to the non-delta representation. These were\n * either not recorded initially (size) or overwritten with the delta type\n * (type) when check_object() decided to reuse the delta.\n+ *\n+ * 3. Resetting our delta depth, as we are now a base object.\n */\n static void drop_reused_delta(struct object_entry *entry)\n {\n@@ -1552,6 +1554,7 @@ static void drop_reused_delta(struct object_entry *entry)\n \t\t\tp = &(*p)->delta_sibling;\n \t}\n \tentry->delta = NULL;\n+\tentry->depth = 0;\n \n \toi.sizep = &entry->size;\n \toi.typep = &entry->type;\n@@ -1570,6 +1573,9 @@ static void drop_reused_delta(struct object_entry *entry)\n * Follow the chain of deltas from this entry onward, throwing away any links\n * that cause us to hit a cycle (as determined by the DFS state flags in\n * the entries).\n+ *\n+ * We also detect too-long reused chains that would violate our --depth\n+ * limit.\n */\n static void break_delta_chains(struct object_entry *entry)\n {\n@@ -1587,6 +1593,18 @@ static void break_delta_chains(struct object_entry *entry)\n \t\t */\n \t\tentry->dfs_state = DFS_ACTIVE;\n \t\tbreak_delta_chains(entry->delta);\n+\n+\t\t/*\n+\t\t * Once we've recursed, our base (if we still have one) knows\n+\t\t * its depth, so we can compute ours (and check it against\n+\t\t * the limit).\n+\t\t */\n+\t\tif (entry->delta) {\n+\t\t\tentry->depth = entry->delta->depth + 1;\n+\t\t\tif (entry->depth > depth)\n+\t\t\t\tdrop_reused_delta(entry);\n+\t\t}\n+\n \t\tentry->dfs_state = DFS_DONE;\n \t\tbreak;\n \ndiff --git a/pack-objects.h b/pack-objects.h\nindex cc9b9a9b9..03f119165 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -30,12 +30,16 @@ struct object_entry {\n \n \t/*\n \t * State flags for depth-first search used for analyzing delta cycles.\n+\t *\n+\t * The depth is measured in delta-links to the base (so if A is a delta\n+\t * against B, then A has a depth of 1, and B a depth of 0).\n \t */\n \tenum {\n \t\tDFS_NONE = 0,\n \t\tDFS_ACTIVE,\n \t\tDFS_DONE\n \t} dfs_state;\n+\tint depth;\n };\n \n struct packing_data {\ndiff --git a/t/t5316-pack-delta-depth.sh b/t/t5316-pack-delta-depth.sh\nnew file mode 100755\nindex 000000000..236d60fe6\n--- /dev/null\n+++ b/t/t5316-pack-delta-depth.sh\n@@ -0,0 +1,93 @@\n+#!/bin/sh\n+\n+test_description='pack-objects breaks long cross-pack delta chains'\n+. ./test-lib.sh\n+\n+# This mirrors a repeated push setup:\n+#\n+# 1. A client repeatedly modifies some files, makes a\n+# commit, and pushes the result. It does this N times\n+# before we get around to repacking.\n+#\n+# 2. Each push generates a thin pack with the new version of\n+# various objects. Let's consider some file in the root tree\n+# which is updated in each commit.\n+#\n+# When generating push number X, we feed commit X-1 (and\n+# thus blob X-1) as a preferred base. The resulting pack has\n+# blob X as a thin delta against blob X-1.\n+#\n+# On the receiving end, \"index-pack --fix-thin\" will\n+# complete the pack with a base copy of tree X-1.\n+#\n+# 3. In older versions of git, if we used the delta from\n+# pack X, then we'd always find blob X-1 as a base in the\n+# same pack (and generate a fresh delta).\n+#\n+# But with the pack mru, we jump from delta to delta\n+# following the traversal order:\n+#\n+# a. We grab blob X from pack X as a delta, putting it at\n+# the tip of our mru list.\n+#\n+# b. Eventually we move onto commit X-1. We need other\n+# objects which are only in pack X-1 (in the test code\n+# below, it's the containing tree). That puts pack X-1\n+# at the tip of our mru list.\n+#\n+# c. Eventually we look for blob X-1, and we find the\n+# version in pack X-1 (because it's the mru tip).\n+#\n+# Now we have blob X as a delta against X-1, which is a delta\n+# against X-2, and so forth.\n+#\n+# In the real world, these small pushes would get exploded by\n+# unpack-objects rather than \"index-pack --fix-thin\", but the\n+# same principle applies to larger pushes (they only need one\n+# repeatedly-modified file to generate the delta chain).\n+\n+test_expect_success 'create series of packs' '\n+\ttest-genrandom foo 4096 >content &&\n+\tprev= &&\n+\tfor i in $(test_seq 1 10)\n+\tdo\n+\t\tcat content >file &&\n+\t\techo $i >>file &&\n+\t\tgit add file &&\n+\t\tgit commit -m $i &&\n+\t\tcur=$(git rev-parse HEAD^{tree}) &&\n+\t\t{\n+\t\t\ttest -n \"$prev\" && echo \"-$prev\"\n+\t\t\techo $cur\n+\t\t\techo \"$(git rev-parse :file) file\"\n+\t\t} | git pack-objects --stdout >tmp &&\n+\t\tgit index-pack --stdin --fix-thin output &&\n+\tperl -lne '\n+\t /chain length = (\\d+)/ and $len = $1;\n+\t END { print $len }\n+\t' output\n+}\n+\n+# Note that this whole setup is pretty reliant on the current\n+# packing heuristics. We double-check that our test case\n+# actually produces a long chain. If it doesn't, it should be\n+# adjusted (or scrapped if the heuristics have become too unreliable)\n+test_expect_success 'packing produces a long delta' '\n+\t# Use --window=0 to make sure we are seeing reused deltas,\n+\t# not computing a new long chain.\n+\tpack=$(git pack-objects --all --window=0 writes:\n\n>> > +# On the receiving end, \"index-pack --fix-thin\" will\n>> > +# complete the pack with a base copy of tree X-1.\n>> \n>> blob? tree? I think the argument would work the same way for either\n>> type of objects, but the previous paragraph is using blob as the\n>> example, so s/tree/blob/ here?\n>\n> Oops, yes. I had originally sketched out the example to use trees, but\n> it was easier to assemble with blobs so I switched (I never actually dug\n> into my \"wild\" case to see what it was segfaulting on, but I agree it\n> applies equally well to either).\n\nOK, then I'll squash in s/tree/blob/ here, in addition to the \"my\"\nthing. Thanks.\n"}]}