{"thread":{"id":"36295","subject":"fetches with bitmaps enabled can cause accesses to already GC'd objects","startedAt":"2014-03-26T02:22:37Z","lastAt":"2014-04-01T07:54:52Z","messageCount":4,"participants":["Siddharth Agarwal","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"237779","messageId":"533239ED.5040503@fb.com","threadId":"36295","inReplyTo":null,"subject":"fetches with bitmaps enabled can cause accesses to already GC'd objects","fromName":"Siddharth Agarwal","fromEmail":"sid0@fb.com","sentAt":"2014-03-26T02:22:37Z","receivedAt":"2014-03-26T02:22:37Z","isPatch":false,"sender":{"key":"sid0@fb.com","avatar":null},"body":"Hi,\n\nWe're still experimenting with bitmaps, and we've have run into issues \nwhere fetching from a repository with bitmaps enabled can lead to \nobjects that used to be present on the server but have since been GC'd \nbeing accessed, and git pack-objects on the server failing because of that.\n\nI can consistently reproduce this with a particular pair of repos, and \ntip of git master (3f09db0) with no patches on top running on both ends. \ngit fetch fails with\n\nremote: error: Could not read be7cbe440a7b9a34f53515af4075e971c811cfb2\nremote: fatal: bad tree object be7cbe440a7b9a34f53515af4075e971c811cfb2\nerror: git upload-pack: git-pack-objects died with error.\nfatal: git upload-pack: aborting due to possible repository corruption \non the remote side.\nremote: aborting due to possible repository corruption on the remote side.\nfatal: protocol error: bad pack header\n\nRemoving the bitmap fixes this.\n\nbe7cbe440a7b9a34f53515af4075e971c811cfb2 is a tree object that is \npresent on the client but not on the server. It used to be present on \nthe server, but the any refs that it was reachable from have been \nremoved and the object has since been garbage collected. One ref that \nthis object was reachable from and that used to be on the server is \nstill present on the client though, under refs/remotes/origin/.\n\nThis tree object seems to be reachable from exactly one other tree \nobject, and so on, until I reach a commit object. Note that the commit \nand root tree pointing to be7cbe440a7b9a34f53515af4075e971c811cfb2 is \nstill present as a loose object in the repo.\n\nI dug into this a bit, and it looks like the bad access is inside \nhttps://github.com/git/git/blob/3f09db0/pack-bitmap.c#L730, and from \nthere inside https://github.com/git/git/blob/3f09db0/pack-bitmap.c#L575. \nThis ultimately calls traverse_commit_list at \nhttps://github.com/git/git/blob/3f09db0/list-objects.c#L195, which adds \nthe tree that transitively points to \nbe7cbe440a7b9a34f53515af4075e971c811cfb2 as pending. (Note again that \nthe commit and root tree objects still exist in the repo as loose \nobjects.) Further down in that function, process_tree is called, which \ntraverses the tree and ultimately dies at \nhttps://github.com/git/git/blob/3f09db0/list-objects.c#L85.\n\nUnfortunately, as before, I can't share the repo this is happening in.\n"},{"id":"237993","messageId":"20140328100043.GA16502@sigill.intra.peff.net","threadId":"36295","inReplyTo":"533239ED.5040503@fb.com","subject":"[PATCH] add `ignore_missing_links` mode to revwalk","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-03-28T10:00:43Z","receivedAt":"2014-03-28T10:00:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"From: Vicent Marti <tanoku@gmail.com>\n\nWhen pack-objects is computing the reachability bitmap to\nserve a fetch request, it can erroneously die() if some of\nthe UNINTERESTING objects are not present. Upload-pack\nthrows away HAVE lines from the client for objects we do not\nhave, but we may have a tip object without all of its\nancestors (e.g., if the tip is no longer reachable and was\nnew enough to survive a `git prune`, but some of its\nreachable objects did get pruned).\n\nIn the non-bitmap case, we do a revision walk with the HAVE\nobjects marked as UNINTERESTING. The revision walker\nexplicitly ignores errors in accessing UNINTERESTING commits\nto handle this case (and we do not bother looking at\nUNINTERESTING trees or blobs at all).\n\nWhen we have bitmaps, however, the process is quite\ndifferent.  The bitmap index for a pack-objects run is\ncalculated in two separate steps:\n\nFirst, we perform an extensive walk from all the HAVEs to\nfind the full set of objects reachable from them. This walk\nis usually optimized away because we are expected to hit an\nobject with a bitmap during the traversal, which allows us\nto terminate early.\n\nSecondly, we perform an extensive walk from all the WANTs,\nwhich usually also terminates early because we hit a commit\nwith an existing bitmap.\n\nOnce we have the resulting bitmaps from the two walks, we\nAND-NOT them together to obtain the resulting set of objects\nwe need to pack.\n\nWhen we are walking the HAVE objects, the revision walker\ndoes not know that we are walking it only to mark the\nresults as uninteresting. We strip out the UNINTERESTING flag,\nbecause those objects _are_ interesting to us during the\nfirst walk. We want to keep going to get a complete set of\nreachable objects if we can.\n\nWe need some way to tell the revision walker that it's OK to\nsilently truncate the HAVE walk, just like it does for the\nUNINTERESTING case. This patch introduces a new\n`ignore_missing_links` flag to the `rev_info` struct, which\nwe set only for the HAVE walk.\n\nIt also adds tests to cover UNINTERESTING objects missing\nfrom several positions: a missing blob, a missing tree, and\na missing parent commit. The missing blob already worked (as\nwe do not care about its contents at all), but the other two\ncases caused us to die().\n\nNote that there are a few cases we do not need to test:\n\n  1. We do not need to test a missing tree, with the blob\n     still present. Without the tree that refers to it, we\n     would not know that the blob is relevant to our walk.\n\n  2. We do not need to test a tip commit that is missing.\n     Upload-pack omits these for us (and in fact, we\n     complain even in the non-bitmap case if it fails to do\n     so).\n\nReported-by: Siddharth Agarwal <sid0@fb.com>\nSigned-off-by: Vicent Marti <tanoku@gmail.com>\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI believe this should solve the problem you're seeing, and I think any\nsolution is going to be along these lines.\n\nThis covers all code paths that can be triggered by pack-objects.  But\nit does not necessarily cover all code paths that a revision walker\nmight use (e.g., it is still possible to die in try_to_simplify_commit,\nbut we would never hit that in pack-objects, because we do not do\npathspec limiting).\n\nSo it's a tradeoff. On the one hand, leaving it like this creates a flag\nin rev_info that may surprise somebody later by not being as generally\nuseful. On the other hand, covering every die() is extra code churn, and\ncreates complexity for cases that cannot actually be triggered in\npractice (complexity because each site has to decide how to handle a\nfailure to access the object).\n\n list-objects.c          |  5 ++++-\n pack-bitmap.c           |  2 ++\n revision.c              |  8 +++++---\n revision.h              |  3 ++-\n t/t5310-pack-bitmaps.sh | 31 +++++++++++++++++++++++++++++++\n 5 files changed, 44 insertions(+), 5 deletions(-)\n\ndiff --git a/list-objects.c b/list-objects.c\nindex 206816f..3595ee7 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -81,8 +81,11 @@ static void process_tree(struct rev_info *revs,\n \t\tdie(\"bad tree object\");\n \tif (obj->flags & (UNINTERESTING | SEEN))\n \t\treturn;\n-\tif (parse_tree(tree) < 0)\n+\tif (parse_tree(tree) < 0) {\n+\t\tif (revs->ignore_missing_links)\n+\t\t\treturn;\n \t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n+\t}\n \tobj->flags |= SEEN;\n \tshow(obj, path, name, cb_data);\n \tme.up = path;\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex ae0b57b..91e4101 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -727,8 +727,10 @@ int prepare_bitmap_walk(struct rev_info *revs)\n \trevs->pending.objects = NULL;\n \n \tif (haves) {\n+\t\trevs->ignore_missing_links = 1;\n \t\thaves_bitmap = find_objects(revs, haves, NULL);\n \t\treset_revision_walk();\n+\t\trevs->ignore_missing_links = 0;\n \n \t\tif (haves_bitmap == NULL)\n \t\t\tdie(\"BUG: failed to perform bitmap walk\");\ndiff --git a/revision.c b/revision.c\nindex 8508550..b3b88e1 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2929,9 +2929,11 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\tif (revs->max_age != -1 &&\n \t\t\t    (commit->date < revs->max_age))\n \t\t\t\tcontinue;\n-\t\t\tif (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)\n-\t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n-\t\t\t\t    sha1_to_hex(commit->object.sha1));\n+\t\t\tif (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {\n+\t\t\t\tif (!revs->ignore_missing_links)\n+\t\t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n+\t\t\t\t\t\tsha1_to_hex(commit->object.sha1));\n+\t\t\t}\n \t\t}\n \n \t\tswitch (simplify_commit(revs, commit)) {\ndiff --git a/revision.h b/revision.h\nindex 1eb94c1..0d997de 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -73,7 +73,8 @@ struct rev_info {\n \tenum rev_sort_order sort_order;\n \n \tunsigned int\tearly_output:1,\n-\t\t\tignore_missing:1;\n+\t\t\tignore_missing:1,\n+\t\t\tignore_missing_links:1;\n \n \t/* Traversal flags */\n \tunsigned int\tdense:1,\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex d3a3afa..caea802 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -3,6 +3,10 @@\n test_description='exercise basic bitmap functionality'\n . ./test-lib.sh\n \n+objpath() {\n+\techo \".git/objects/$(echo \"$1\" | sed -e 's|\\(..\\)|\\1/|')\"\n+}\n+\n test_expect_success 'setup repo with moderate-sized history' '\n \tfor i in $(test_seq 1 10); do\n \t\ttest_commit $i\n@@ -112,6 +116,33 @@ test_expect_success 'fetch (full bitmap)' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'create objects for missing-HAVE tests' '\n+\tblob=$(echo \"missing have\" | git hash-object -w --stdin) &&\n+\ttree=$(printf \"100644 blob $blob\\tfile\\n\" | git mktree) &&\n+\tparent=$(echo parent | git commit-tree $tree) &&\n+\tcommit=$(echo commit | git commit-tree $tree -p $parent) &&\n+\tcat >revs <<-EOF\n+\tHEAD\n+\t^HEAD^\n+\t^$commit\n+\tEOF\n+'\n+\n+test_expect_success 'pack with missing blob' '\n+\trm $(objpath $blob) &&\n+\tgit pack-objects --stdout --revs <revs >/dev/null\n+'\n+\n+test_expect_success 'pack with missing tree' '\n+\trm $(objpath $tree) &&\n+\tgit pack-objects --stdout --revs <revs >/dev/null\n+'\n+\n+test_expect_success 'pack with missing parent' '\n+\trm $(objpath $parent) &&\n+\tgit pack-objects --stdout --revs <revs >/dev/null\n+'\n+\n test_lazy_prereq JGIT '\n \ttype jgit\n '\n-- \n1.9.1.656.ge8a0637\n"},{"id":"238158","messageId":"5339E2BD.3090303@fb.com","threadId":"36295","inReplyTo":"20140328100043.GA16502@sigill.intra.peff.net","subject":"Re: [PATCH] add `ignore_missing_links` mode to revwalk","fromName":"Siddharth Agarwal","fromEmail":"sid0@fb.com","sentAt":"2014-03-31T21:48:45Z","receivedAt":"2014-03-31T21:48:45Z","isPatch":true,"sender":{"key":"sid0@fb.com","avatar":null},"body":"On 03/28/2014 03:00 AM, Jeff King wrote:\n> From: Vicent Marti <tanoku@gmail.com>\n>\n> When pack-objects is computing the reachability bitmap to\n> serve a fetch request, it can erroneously die() if some of\n> the UNINTERESTING objects are not present. Upload-pack\n> throws away HAVE lines from the client for objects we do not\n> have, but we may have a tip object without all of its\n> ancestors (e.g., if the tip is no longer reachable and was\n> new enough to survive a `git prune`, but some of its\n> reachable objects did get pruned).\n\nThanks for this patch. It looks pretty sensible.\n\nUnfortunately, I can't provide feedback on running it in production \nbecause we've decided to set aside experimenting with bitmaps for a bit. \nI hope to get back to it in a couple of months.\n\n\n\n>\n> In the non-bitmap case, we do a revision walk with the HAVE\n> objects marked as UNINTERESTING. The revision walker\n> explicitly ignores errors in accessing UNINTERESTING commits\n> to handle this case (and we do not bother looking at\n> UNINTERESTING trees or blobs at all).\n>\n> When we have bitmaps, however, the process is quite\n> different.  The bitmap index for a pack-objects run is\n> calculated in two separate steps:\n>\n> First, we perform an extensive walk from all the HAVEs to\n> find the full set of objects reachable from them. This walk\n> is usually optimized away because we are expected to hit an\n> object with a bitmap during the traversal, which allows us\n> to terminate early.\n>\n> Secondly, we perform an extensive walk from all the WANTs,\n> which usually also terminates early because we hit a commit\n> with an existing bitmap.\n>\n> Once we have the resulting bitmaps from the two walks, we\n> AND-NOT them together to obtain the resulting set of objects\n> we need to pack.\n>\n> When we are walking the HAVE objects, the revision walker\n> does not know that we are walking it only to mark the\n> results as uninteresting. We strip out the UNINTERESTING flag,\n> because those objects _are_ interesting to us during the\n> first walk. We want to keep going to get a complete set of\n> reachable objects if we can.\n>\n> We need some way to tell the revision walker that it's OK to\n> silently truncate the HAVE walk, just like it does for the\n> UNINTERESTING case. This patch introduces a new\n> `ignore_missing_links` flag to the `rev_info` struct, which\n> we set only for the HAVE walk.\n>\n> It also adds tests to cover UNINTERESTING objects missing\n> from several positions: a missing blob, a missing tree, and\n> a missing parent commit. The missing blob already worked (as\n> we do not care about its contents at all), but the other two\n> cases caused us to die().\n>\n> Note that there are a few cases we do not need to test:\n>\n>    1. We do not need to test a missing tree, with the blob\n>       still present. Without the tree that refers to it, we\n>       would not know that the blob is relevant to our walk.\n>\n>    2. We do not need to test a tip commit that is missing.\n>       Upload-pack omits these for us (and in fact, we\n>       complain even in the non-bitmap case if it fails to do\n>       so).\n>\n> Reported-by: Siddharth Agarwal <sid0@fb.com>\n> Signed-off-by: Vicent Marti <tanoku@gmail.com>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> I believe this should solve the problem you're seeing, and I think any\n> solution is going to be along these lines.\n>\n> This covers all code paths that can be triggered by pack-objects.  But\n> it does not necessarily cover all code paths that a revision walker\n> might use (e.g., it is still possible to die in try_to_simplify_commit,\n> but we would never hit that in pack-objects, because we do not do\n> pathspec limiting).\n>\n> So it's a tradeoff. On the one hand, leaving it like this creates a flag\n> in rev_info that may surprise somebody later by not being as generally\n> useful. On the other hand, covering every die() is extra code churn, and\n> creates complexity for cases that cannot actually be triggered in\n> practice (complexity because each site has to decide how to handle a\n> failure to access the object).\n>\n>   list-objects.c          |  5 ++++-\n>   pack-bitmap.c           |  2 ++\n>   revision.c              |  8 +++++---\n>   revision.h              |  3 ++-\n>   t/t5310-pack-bitmaps.sh | 31 +++++++++++++++++++++++++++++++\n>   5 files changed, 44 insertions(+), 5 deletions(-)\n>\n> diff --git a/list-objects.c b/list-objects.c\n> index 206816f..3595ee7 100644\n> --- a/list-objects.c\n> +++ b/list-objects.c\n> @@ -81,8 +81,11 @@ static void process_tree(struct rev_info *revs,\n>   \t\tdie(\"bad tree object\");\n>   \tif (obj->flags & (UNINTERESTING | SEEN))\n>   \t\treturn;\n> -\tif (parse_tree(tree) < 0)\n> +\tif (parse_tree(tree) < 0) {\n> +\t\tif (revs->ignore_missing_links)\n> +\t\t\treturn;\n>   \t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n> +\t}\n>   \tobj->flags |= SEEN;\n>   \tshow(obj, path, name, cb_data);\n>   \tme.up = path;\n> diff --git a/pack-bitmap.c b/pack-bitmap.c\n> index ae0b57b..91e4101 100644\n> --- a/pack-bitmap.c\n> +++ b/pack-bitmap.c\n> @@ -727,8 +727,10 @@ int prepare_bitmap_walk(struct rev_info *revs)\n>   \trevs->pending.objects = NULL;\n>   \n>   \tif (haves) {\n> +\t\trevs->ignore_missing_links = 1;\n>   \t\thaves_bitmap = find_objects(revs, haves, NULL);\n>   \t\treset_revision_walk();\n> +\t\trevs->ignore_missing_links = 0;\n>   \n>   \t\tif (haves_bitmap == NULL)\n>   \t\t\tdie(\"BUG: failed to perform bitmap walk\");\n> diff --git a/revision.c b/revision.c\n> index 8508550..b3b88e1 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -2929,9 +2929,11 @@ static struct commit *get_revision_1(struct rev_info *revs)\n>   \t\t\tif (revs->max_age != -1 &&\n>   \t\t\t    (commit->date < revs->max_age))\n>   \t\t\t\tcontinue;\n> -\t\t\tif (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)\n> -\t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n> -\t\t\t\t    sha1_to_hex(commit->object.sha1));\n> +\t\t\tif (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {\n> +\t\t\t\tif (!revs->ignore_missing_links)\n> +\t\t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n> +\t\t\t\t\t\tsha1_to_hex(commit->object.sha1));\n> +\t\t\t}\n>   \t\t}\n>   \n>   \t\tswitch (simplify_commit(revs, commit)) {\n> diff --git a/revision.h b/revision.h\n> index 1eb94c1..0d997de 100644\n> --- a/revision.h\n> +++ b/revision.h\n> @@ -73,7 +73,8 @@ struct rev_info {\n>   \tenum rev_sort_order sort_order;\n>   \n>   \tunsigned int\tearly_output:1,\n> -\t\t\tignore_missing:1;\n> +\t\t\tignore_missing:1,\n> +\t\t\tignore_missing_links:1;\n>   \n>   \t/* Traversal flags */\n>   \tunsigned int\tdense:1,\n> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\n> index d3a3afa..caea802 100755\n> --- a/t/t5310-pack-bitmaps.sh\n> +++ b/t/t5310-pack-bitmaps.sh\n> @@ -3,6 +3,10 @@\n>   test_description='exercise basic bitmap functionality'\n>   . ./test-lib.sh\n>   \n> +objpath() {\n> +\techo \".git/objects/$(echo \"$1\" | sed -e 's|\\(..\\)|\\1/|')\"\n> +}\n> +\n>   test_expect_success 'setup repo with moderate-sized history' '\n>   \tfor i in $(test_seq 1 10); do\n>   \t\ttest_commit $i\n> @@ -112,6 +116,33 @@ test_expect_success 'fetch (full bitmap)' '\n>   \ttest_cmp expect actual\n>   '\n>   \n> +test_expect_success 'create objects for missing-HAVE tests' '\n> +\tblob=$(echo \"missing have\" | git hash-object -w --stdin) &&\n> +\ttree=$(printf \"100644 blob $blob\\tfile\\n\" | git mktree) &&\n> +\tparent=$(echo parent | git commit-tree $tree) &&\n> +\tcommit=$(echo commit | git commit-tree $tree -p $parent) &&\n> +\tcat >revs <<-EOF\n> +\tHEAD\n> +\t^HEAD^\n> +\t^$commit\n> +\tEOF\n> +'\n> +\n> +test_expect_success 'pack with missing blob' '\n> +\trm $(objpath $blob) &&\n> +\tgit pack-objects --stdout --revs <revs >/dev/null\n> +'\n> +\n> +test_expect_success 'pack with missing tree' '\n> +\trm $(objpath $tree) &&\n> +\tgit pack-objects --stdout --revs <revs >/dev/null\n> +'\n> +\n> +test_expect_success 'pack with missing parent' '\n> +\trm $(objpath $parent) &&\n> +\tgit pack-objects --stdout --revs <revs >/dev/null\n> +'\n> +\n>   test_lazy_prereq JGIT '\n>   \ttype jgit\n>   '\n"},{"id":"238191","messageId":"20140401075452.GB22591@sigill.intra.peff.net","threadId":"36295","inReplyTo":"5339E2BD.3090303@fb.com","subject":"Re: [PATCH] add `ignore_missing_links` mode to revwalk","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-04-01T07:54:52Z","receivedAt":"2014-04-01T07:54:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Mar 31, 2014 at 02:48:45PM -0700, Siddharth Agarwal wrote:\n\n> On 03/28/2014 03:00 AM, Jeff King wrote:\n> >From: Vicent Marti <tanoku@gmail.com>\n> >\n> >When pack-objects is computing the reachability bitmap to serve a\n> >fetch request, it can erroneously die() if some of the UNINTERESTING\n> >objects are not present. Upload-pack throws away HAVE lines from the\n> >client for objects we do not have, but we may have a tip object\n> >without all of its ancestors (e.g., if the tip is no longer reachable\n> >and was new enough to survive a `git prune`, but some of its\n> >reachable objects did get pruned).\n> \n> Thanks for this patch. It looks pretty sensible.\n> \n> Unfortunately, I can't provide feedback on running it in production\n> because we've decided to set aside experimenting with bitmaps for a\n> bit. I hope to get back to it in a couple of months.\n\nBummer. Thanks for taking a look at it.\n\nI do think this patch is definitely fixing a bug, and needs to be\npursued.  We've been running with bitmaps in production on GitHub since\nlast summer, but have never run into this situation. However, I think it\nis largely caused by our pruning parameters:\n\n  1. We tend not to prune very often, and instead keep unreachable\n     objects around as a safety mechanism.\n\n  2. When we do prune, we use a very tight cutoff, rather than the\n     default 2-week period. So the window of opportunity is much smaller\n     for a repo to prune an object but not its descendant (typically\n     either we keep both, or they both get pruned).\n\nSo if you do come back to it later, the fix should have filtered through\nto \"master\" by then. :)\n\n-Peff\n"}]}