{"thread":{"id":"49864","subject":"[PATCH 0/3] delta-island fixes","startedAt":"2018-11-20T09:44:54Z","lastAt":"2018-11-22T16:50:16Z","messageCount":9,"participants":["Jeff King","Derrick Stolee","Duy Nguyen","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"363717","messageId":"20181120094451.GA21725@sigill.intra.peff.net","threadId":"49864","inReplyTo":null,"subject":"[PATCH 0/3] delta-island fixes","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-11-20T09:44:51Z","receivedAt":"2018-11-20T09:44:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This fixes a few bugs in the cc/delta-islands topic: one major, and two\nminor.\n\nSadly, the major one was not caught by our test suite, and I'm not sure\nhow to remedy that. The problem is a memory management one, and happens\nonly when you have a reasonably large number of objects. So it triggers\nreadily when run on a real repository, but not on the toy one in t5320.\nCreating a much larger repository there would make the test suite more\nexpensive.\n\nIn cases like this I think it's often a good idea to have a perf test.\nThose are expensive anyway, and we'd have the double benefit of\nexercising the code and showing off the performance improvement. But the\ndelta-island code only makes sense on a very specialized repo: one where\nyou have multiple related but diverging histories. You could simulate\nthat by picking two branches in a repository, but the effect is going to\nbe miniscule.\n\nAnyway, here are the fixes without tests. We should at least apply these\nbefore v2.20 ships with the bugs.\n\n [1/3]: pack-objects: fix tree_depth and layer invariants\n [2/3]: pack-objects: zero-initialize tree_depth/layer arrays\n [3/3]: pack-objects: fix off-by-one in delta-island tree-depth computation\n\n builtin/pack-objects.c | 4 +++-\n git-compat-util.h | 1 +\n pack-objects.h | 4 ++--\n 3 files changed, 6 insertions(+), 3 deletions(-)\n\n"},{"id":"363718","messageId":"20181120094638.GA22742@sigill.intra.peff.net","threadId":"49864","inReplyTo":"20181120094451.GA21725@sigill.intra.peff.net","subject":"[PATCH 1/3] pack-objects: fix tree_depth and layer invariants","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-11-20T09:46:38Z","receivedAt":"2018-11-20T09:46:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Commit 108f530385 (pack-objects: move tree_depth into 'struct\npacking_data', 2018-08-16) dynamically manages a tree_depth array in\npacking_data that maintains one of these invariants:\n\n 1. tree_depth is NULL (i.e., the requested options don't require us to\n track tree depths)\n\n 2. tree_depth is non-NULL and has as many entries as the \"objects\"\n array\n\nWe maintain (2) by:\n\n a. When the objects array grows, grow tree_depth to the same size\n (unless it's NULL, in which case we can leave it).\n\n b. When a caller asks to set a depth via oe_set_tree_depth(), if\n tree_depth is NULL we allocate it.\n\nBut in (b), we use the number of stored objects, _not_ the allocated\nsize of the objects array. So we can run into a situation like this:\n\n 1. packlist_alloc() needs to store the Nth object, so it grows the\n objects array to M, where M > N.\n\n 2. oe_set_tree_depth() wants to store a depth, so it allocates an\n array of length N. Now we've violated our invariant.\n\n 3. packlist_alloc() needs to store the N+1th object. But it _doesn't_\n grow the objects array, since N <= M still holds. We try to assign\n to tree_depth[N+1], which is out of bounds.\n\nThat doesn't happen in our test scripts, because the repositories they\nuse are so small, but it's easy to trigger by running:\n\n echo HEAD | git pack-objects --revs --delta-islands --stdout >/dev/null\n\nin any reasonably-sized repo (like git.git).\n\nWe can fix it by always growing the array to match pack->nr_alloc, not\npack->nr_objects. Likewise for the \"layer\" array from fe0ac2fb7f\n(pack-objects: move 'layer' into 'struct packing_data', 2018-08-16),\nwhich has the same bug.\n\nSigned-off-by: Jeff King \n---\n pack-objects.h | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/pack-objects.h b/pack-objects.h\nindex feb6a6a05e..f31ac1c81c 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -412,7 +412,7 @@ static inline void oe_set_tree_depth(struct packing_data *pack,\n \t\t\t\t unsigned int tree_depth)\n {\n \tif (!pack->tree_depth)\n-\t\tALLOC_ARRAY(pack->tree_depth, pack->nr_objects);\n+\t\tALLOC_ARRAY(pack->tree_depth, pack->nr_alloc);\n \tpack->tree_depth[e - pack->objects] = tree_depth;\n }\n \n@@ -429,7 +429,7 @@ static inline void oe_set_layer(struct packing_data *pack,\n \t\t\t\tunsigned char layer)\n {\n \tif (!pack->layer)\n-\t\tALLOC_ARRAY(pack->layer, pack->nr_objects);\n+\t\tALLOC_ARRAY(pack->layer, pack->nr_alloc);\n \tpack->layer[e - pack->objects] = layer;\n }\n \n-- \n2.20.0.rc0.715.gf6b01ab3e1\n\n"},{"id":"363719","messageId":"20181120094856.GB22742@sigill.intra.peff.net","threadId":"49864","inReplyTo":"20181120094451.GA21725@sigill.intra.peff.net","subject":"[PATCH 2/3] pack-objects: zero-initialize tree_depth/layer arrays","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-11-20T09:48:57Z","receivedAt":"2018-11-20T09:49:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Commit 108f530385 (pack-objects: move tree_depth into 'struct\npacking_data', 2018-08-16) started maintaining a tree_depth array that\nmatches the \"objects\" array. We extend the array when:\n\n 1. The objects array is extended, in which case we use realloc to\n extend the tree_depth array.\n\n 2. A caller asks to store a tree_depth for object N, and this is the\n first such request; we create the array from scratch and store the\n value for N.\n\nIn the latter case, though, we use regular xmalloc(), and the depth\nvalues for any objects besides N is undefined. This happens to not\ntrigger a bug with the current code, but the reasons are quite subtle:\n\n - we never ask about the depth for any object with index i < N. This is\n because we store the depth immediately for all trees and blobs. So\n any such \"i\" must be a non-tree, and therefore we will never need to\n care about its depth (in fact, we really only care about the depth of\n trees).\n\n - there are no objects at this point with index i > N, because we\n always fill in the depth for a tree immediately after its object\n entry is created (we may still allocate uninitialized depth entries,\n but they'll be initialized by packlist_alloc() when it initializes\n the entry in the \"objects\" array).\n\nSo it works, but only by chance. To be defensive, let's zero the array,\nwhich matches the \"unset\" values which would be handed out by\noe_tree_depth() already.\n\nSigned-off-by: Jeff King \n---\n git-compat-util.h | 1 +\n pack-objects.h | 4 ++--\n 2 files changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex f16058182f..09b0102cae 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -861,6 +861,7 @@ extern FILE *fopen_or_warn(const char *path, const char *mode);\n #define FREE_AND_NULL(p) do { free(p); (p) = NULL; } while (0)\n \n #define ALLOC_ARRAY(x, alloc) (x) = xmalloc(st_mult(sizeof(*(x)), (alloc)))\n+#define CALLOC_ARRAY(x, alloc) (x) = xcalloc((alloc), sizeof(*(x)));\n #define REALLOC_ARRAY(x, alloc) (x) = xrealloc((x), st_mult(sizeof(*(x)), (alloc)))\n \n #define COPY_ARRAY(dst, src, n) copy_array((dst), (src), (n), sizeof(*(dst)) + \\\ndiff --git a/pack-objects.h b/pack-objects.h\nindex f31ac1c81c..dc869f26c2 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -412,7 +412,7 @@ static inline void oe_set_tree_depth(struct packing_data *pack,\n \t\t\t\t unsigned int tree_depth)\n {\n \tif (!pack->tree_depth)\n-\t\tALLOC_ARRAY(pack->tree_depth, pack->nr_alloc);\n+\t\tCALLOC_ARRAY(pack->tree_depth, pack->nr_alloc);\n \tpack->tree_depth[e - pack->objects] = tree_depth;\n }\n \n@@ -429,7 +429,7 @@ static inline void oe_set_layer(struct packing_data *pack,\n \t\t\t\tunsigned char layer)\n {\n \tif (!pack->layer)\n-\t\tALLOC_ARRAY(pack->layer, pack->nr_alloc);\n+\t\tCALLOC_ARRAY(pack->layer, pack->nr_alloc);\n \tpack->layer[e - pack->objects] = layer;\n }\n \n-- \n2.20.0.rc0.715.gf6b01ab3e1\n\n"},{"id":"363720","messageId":"20181120095053.GC22742@sigill.intra.peff.net","threadId":"49864","inReplyTo":"20181120094451.GA21725@sigill.intra.peff.net","subject":"[PATCH 3/3] pack-objects: fix off-by-one in delta-island tree-depth computation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-11-20T09:50:53Z","receivedAt":"2018-11-20T09:50:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When delta-islands are in use, we need to record the deepest path at\nwhich we find each tree and blob. Our loop to do so counts slashes, so\n\"foo\" is depth 0, \"foo/bar\" is depth 1, and so on.\n\nHowever, this neglects root trees, which are represented by the empty\nstring. Those also have depth 0, but are at a layer above \"foo\". Thus,\n\"foo\" should be 1, \"foo/bar\" at 2, and so on. We use this depth to\ntopo-sort the trees in resolve_tree_islands(). As a result, we may fail\nto visit a root tree before the sub-trees it contains, and therefore not\ncorrectly pass down the island marks.\n\nThat in turn could lead to missing some delta opportunities (objects are\nin the same island, but we didn't realize it) or creating unwanted\ncross-island deltas (one object is in an island another isn't, but we\ndon't realize). In practice, it seems to have only a small effect. Some\nexperiments on the real-world git/git fork network at GitHub showed an\nimprovement of only 0.14% in the resulting clone size.\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex e7ea206c08..411aefd687 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2786,9 +2786,11 @@ static void show_object(struct object *obj, const char *name, void *data)\n \n \tif (use_delta_islands) {\n \t\tconst char *p;\n-\t\tunsigned depth = 0;\n+\t\tunsigned depth;\n \t\tstruct object_entry *ent;\n \n+\t\t/* the empty string is a root tree, which is depth 0 */\n+\t\tdepth = *name ? 1 : 0;\n \t\tfor (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))\n \t\t\tdepth++;\n \n-- \n2.20.0.rc0.715.gf6b01ab3e1\n"},{"id":"363753","messageId":"778f1fcb-8988-de42-8264-d4394ede8540@gmail.com","threadId":"49864","inReplyTo":"20181120094451.GA21725@sigill.intra.peff.net","subject":"Re: [PATCH 0/3] delta-island fixes","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-11-20T15:06:57Z","receivedAt":"2018-11-20T15:07:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 11/20/2018 4:44 AM, Jeff King wrote:\n> In cases like this I think it's often a good idea to have a perf test.\n> Those are expensive anyway, and we'd have the double benefit of\n> exercising the code and showing off the performance improvement. But the\n> delta-island code only makes sense on a very specialized repo: one where\n> you have multiple related but diverging histories. You could simulate\n> that by picking two branches in a repository, but the effect is going to\n> be miniscule.\n\nThe changes in this series look correct. Too bad it is difficult to test.\n\nPerhaps we should add a performance test for the --delta-islands check \nthat would trigger the failure (and maybe a clone afterwards). There are \nlots of freely available forks of git.git that present interesting fork \nstructure. Here are three that would suffice to make this interesting:\n\n     https://github.com/git/git\n     https://github.com/git-for-windows/git\n     https://github.com/microsoft/git\n\nOf course, running it on a specific repo is up to the person running the \nperf suite.\n\nThanks,\n-Stolee\n"},{"id":"363755","messageId":"CACsJy8AETNxNnEq-8ROrQTkjy-_9mtoprmc=BQ554f7QECajPw@mail.gmail.com","threadId":"49864","inReplyTo":"20181120094638.GA22742@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] pack-objects: fix tree_depth and layer invariants","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2018-11-20T16:37:18Z","receivedAt":"2018-11-20T16:37:47Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Nov 20, 2018 at 11:04 AM Jeff King wrote:\n>\n> Commit 108f530385 (pack-objects: move tree_depth into 'struct\n> packing_data', 2018-08-16) dynamically manages a tree_depth array in\n> packing_data that maintains one of these invariants:\n>\n> 1. tree_depth is NULL (i.e., the requested options don't require us to\n> track tree depths)\n>\n> 2. tree_depth is non-NULL and has as many entries as the \"objects\"\n> array\n>\n> We maintain (2) by:\n>\n> a. When the objects array grows, grow tree_depth to the same size\n> (unless it's NULL, in which case we can leave it).\n>\n> b. When a caller asks to set a depth via oe_set_tree_depth(), if\n> tree_depth is NULL we allocate it.\n>\n> But in (b), we use the number of stored objects, _not_ the allocated\n> size of the objects array. So we can run into a situation like this:\n>\n> 1. packlist_alloc() needs to store the Nth object, so it grows the\n> objects array to M, where M > N.\n>\n> 2. oe_set_tree_depth() wants to store a depth, so it allocates an\n> array of length N. Now we've violated our invariant.\n>\n> 3. packlist_alloc() needs to store the N+1th object. But it _doesn't_\n> grow the objects array, since N <= M still holds. We try to assign\n> to tree_depth[N+1], which is out of bounds.\n\nDo you think if this splitting data to packing_data is too fragile\nthat we should just scrape the whole thing and move all data back to\nobject_entry[]? We would use more memory of course but higher memory\nusage is still better than more bugs (if these are likely to show up\nagain).\n-- \nDuy\n"},{"id":"363806","messageId":"xmqqa7m3822q.fsf@gitster-ct.c.googlers.com","threadId":"49864","inReplyTo":"20181120094638.GA22742@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] pack-objects: fix tree_depth and layer invariants","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-11-21T04:52:13Z","receivedAt":"2018-11-21T04:52:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> But in (b), we use the number of stored objects, _not_ the allocated\n> size of the objects array. So we can run into a situation like this:\n>\n> 1. packlist_alloc() needs to store the Nth object, so it grows the\n> objects array to M, where M > N.\n>\n> 2. oe_set_tree_depth() wants to store a depth, so it allocates an\n> array of length N. Now we've violated our invariant.\n>\n> 3. packlist_alloc() needs to store the N+1th object. But it _doesn't_\n> grow the objects array, since N <= M still holds. We try to assign\n> to tree_depth[N+1], which is out of bounds.\n\nOuch. I see counting and allocationg is hard (I think I spotted a\nbug in another area that comes from the same \"count while filtering\nand then allocate\" pattern during this cycle). Thanks for spotting.\n\n"},{"id":"363914","messageId":"20181122164318.GG28192@sigill.intra.peff.net","threadId":"49864","inReplyTo":"778f1fcb-8988-de42-8264-d4394ede8540@gmail.com","subject":"Re: [PATCH 0/3] delta-island fixes","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-11-22T16:43:18Z","receivedAt":"2018-11-22T16:43:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 20, 2018 at 10:06:57AM -0500, Derrick Stolee wrote:\n\n> On 11/20/2018 4:44 AM, Jeff King wrote:\n> > In cases like this I think it's often a good idea to have a perf test.\n> > Those are expensive anyway, and we'd have the double benefit of\n> > exercising the code and showing off the performance improvement. But the\n> > delta-island code only makes sense on a very specialized repo: one where\n> > you have multiple related but diverging histories. You could simulate\n> > that by picking two branches in a repository, but the effect is going to\n> > be miniscule.\n> \n> The changes in this series look correct. Too bad it is difficult to test.\n> \n> Perhaps we should add a performance test for the --delta-islands check that\n> would trigger the failure (and maybe a clone afterwards). There are lots of\n> freely available forks of git.git that present interesting fork structure.\n> Here are three that would suffice to make this interesting:\n> \n>     https://github.com/git/git\n>     https://github.com/git-for-windows/git\n>     https://github.com/microsoft/git\n> \n> Of course, running it on a specific repo is up to the person running the\n> perf suite.\n\nI hadn't really considered the possibility of reconstructing a fork\nnetwork repository from public repos. It probably would be possible to\ninclude a script which does so, although:\n\n - I suspect it's going to be pretty expensive. We can use --reference\n to reduce the size of subsequent clones, but just the repacks you\n have to do to assemble the final shared repo can get pretty\n expensive.\n\n - That's 3 forks. Our real-world case has over 4000. I'm not sure of\n the size of the effects for smaller cases.\n\nSo in short, I think it's an interesting avenue to explore, but it might\nturn out to be a dead-end. I'm not going to prioritize it right now, but\nif somebody wants to play with it, I'd be happy to look over the\nresults.\n\n-Peff\n"},{"id":"363915","messageId":"20181122165012.GH28192@sigill.intra.peff.net","threadId":"49864","inReplyTo":"CACsJy8AETNxNnEq-8ROrQTkjy-_9mtoprmc=BQ554f7QECajPw@mail.gmail.com","subject":"Re: [PATCH 1/3] pack-objects: fix tree_depth and layer invariants","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-11-22T16:50:12Z","receivedAt":"2018-11-22T16:50:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 20, 2018 at 05:37:18PM +0100, Duy Nguyen wrote:\n\n> > But in (b), we use the number of stored objects, _not_ the allocated\n> > size of the objects array. So we can run into a situation like this:\n> >\n> > 1. packlist_alloc() needs to store the Nth object, so it grows the\n> > objects array to M, where M > N.\n> >\n> > 2. oe_set_tree_depth() wants to store a depth, so it allocates an\n> > array of length N. Now we've violated our invariant.\n> >\n> > 3. packlist_alloc() needs to store the N+1th object. But it _doesn't_\n> > grow the objects array, since N <= M still holds. We try to assign\n> > to tree_depth[N+1], which is out of bounds.\n> \n> Do you think if this splitting data to packing_data is too fragile\n> that we should just scrape the whole thing and move all data back to\n> object_entry[]? We would use more memory of course but higher memory\n> usage is still better than more bugs (if these are likely to show up\n> again).\n\nCertainly that thought crossed my mind while working on these patches. :)\n\nEspecially given the difficulties it introduced into the recent\nbitmap-reuse topic, and the size fixes we had to deal with in v2.19.\n\nOverall, though, I dunno. This fix, while subtle, turned out not to be\ntoo complicated. And the memory savings are real. I consider 100M\nobjects to be on the large size of feasible for stock Git these days,\nand I think we are talking about on the order of 4GB memory savings\nthere. You need a big machine to handle a repository of that size, but\n4GB is still appreciable.\n\nSo I guess at this point, with all (known) bugs fixed, we should stick\nwith it for now. If it becomes a problem for development of a future\nfeature, then we can re-evaluate then.\n\n-Peff\n"}]}