fetches with bitmaps enabled can cause accesses to already GC'd objects

fetches with bitmaps enabled can cause accesses to already GC'd objects

[Siddharth Agarwal]

Hi,

We're still experimenting with bitmaps, and we've have run into issues 
where fetching from a repository with bitmaps enabled can lead to 
objects that used to be present on the server but have since been GC'd 
being accessed, and git pack-objects on the server failing because of that.

I can consistently reproduce this with a particular pair of repos, and 
tip of git master (3f09db0) with no patches on top running on both ends. 
git fetch fails with

remote: error: Could not read be7cbe440a7b9a34f53515af4075e971c811cfb2
remote: fatal: bad tree object be7cbe440a7b9a34f53515af4075e971c811cfb2
error: git upload-pack: git-pack-objects died with error.
fatal: git upload-pack: aborting due to possible repository corruption 
on the remote side.
remote: aborting due to possible repository corruption on the remote side.
fatal: protocol error: bad pack header

Removing the bitmap fixes this.

be7cbe440a7b9a34f53515af4075e971c811cfb2 is a tree object that is 
present on the client but not on the server. It used to be present on 
the server, but the any refs that it was reachable from have been 
removed and the object has since been garbage collected. One ref that 
this object was reachable from and that used to be on the server is 
still present on the client though, under refs/remotes/origin/.

This tree object seems to be reachable from exactly one other tree 
object, and so on, until I reach a commit object. Note that the commit 
and root tree pointing to be7cbe440a7b9a34f53515af4075e971c811cfb2 is 
still present as a loose object in the repo.

I dug into this a bit, and it looks like the bad access is inside 
https://github.com/git/git/blob/3f09db0/pack-bitmap.c#L730, and from 
there inside https://github.com/git/git/blob/3f09db0/pack-bitmap.c#L575. 
This ultimately calls traverse_commit_list at 
https://github.com/git/git/blob/3f09db0/list-objects.c#L195, which adds 
the tree that transitively points to 
be7cbe440a7b9a34f53515af4075e971c811cfb2 as pending. (Note again that 
the commit and root tree objects still exist in the repo as loose 
objects.) Further down in that function, process_tree is called, which 
traverses the tree and ultimately dies at 
https://github.com/git/git/blob/3f09db0/list-objects.c#L85.

Unfortunately, as before, I can't share the repo this is happening in.

[PATCH] add `ignore_missing_links` mode to revwalk

[Jeff King]

From: Vicent Marti <tanoku@gmail.com>

When pack-objects is computing the reachability bitmap to
serve a fetch request, it can erroneously die() if some of
the UNINTERESTING objects are not present. Upload-pack
throws away HAVE lines from the client for objects we do not
have, but we may have a tip object without all of its
ancestors (e.g., if the tip is no longer reachable and was
new enough to survive a `git prune`, but some of its
reachable objects did get pruned).

In the non-bitmap case, we do a revision walk with the HAVE
objects marked as UNINTERESTING. The revision walker
explicitly ignores errors in accessing UNINTERESTING commits
to handle this case (and we do not bother looking at
UNINTERESTING trees or blobs at all).

When we have bitmaps, however, the process is quite
different.  The bitmap index for a pack-objects run is
calculated in two separate steps:

First, we perform an extensive walk from all the HAVEs to
find the full set of objects reachable from them. This walk
is usually optimized away because we are expected to hit an
object with a bitmap during the traversal, which allows us
to terminate early.

Secondly, we perform an extensive walk from all the WANTs,
which usually also terminates early because we hit a commit
with an existing bitmap.

Once we have the resulting bitmaps from the two walks, we
AND-NOT them together to obtain the resulting set of objects
we need to pack.

When we are walking the HAVE objects, the revision walker
does not know that we are walking it only to mark the
results as uninteresting. We strip out the UNINTERESTING flag,
because those objects _are_ interesting to us during the
first walk. We want to keep going to get a complete set of
reachable objects if we can.

We need some way to tell the revision walker that it's OK to
silently truncate the HAVE walk, just like it does for the
UNINTERESTING case. This patch introduces a new
`ignore_missing_links` flag to the `rev_info` struct, which
we set only for the HAVE walk.

It also adds tests to cover UNINTERESTING objects missing
from several positions: a missing blob, a missing tree, and
a missing parent commit. The missing blob already worked (as
we do not care about its contents at all), but the other two
cases caused us to die().

Note that there are a few cases we do not need to test:

  1. We do not need to test a missing tree, with the blob
     still present. Without the tree that refers to it, we
     would not know that the blob is relevant to our walk.

  2. We do not need to test a tip commit that is missing.
     Upload-pack omits these for us (and in fact, we
     complain even in the non-bitmap case if it fails to do
     so).

Reported-by: Siddharth Agarwal <sid0@fb.com>
Signed-off-by: Vicent Marti <tanoku@gmail.com>
Signed-off-by: Jeff King <peff@peff.net>
---
I believe this should solve the problem you're seeing, and I think any
solution is going to be along these lines.

This covers all code paths that can be triggered by pack-objects.  But
it does not necessarily cover all code paths that a revision walker
might use (e.g., it is still possible to die in try_to_simplify_commit,
but we would never hit that in pack-objects, because we do not do
pathspec limiting).

So it's a tradeoff. On the one hand, leaving it like this creates a flag
in rev_info that may surprise somebody later by not being as generally
useful. On the other hand, covering every die() is extra code churn, and
creates complexity for cases that cannot actually be triggered in
practice (complexity because each site has to decide how to handle a
failure to access the object).

 list-objects.c          |  5 ++++-
 pack-bitmap.c           |  2 ++
 revision.c              |  8 +++++---
 revision.h              |  3 ++-
 t/t5310-pack-bitmaps.sh | 31 +++++++++++++++++++++++++++++++
 5 files changed, 44 insertions(+), 5 deletions(-)

diff --git a/list-objects.c b/list-objects.c
index 206816f..3595ee7 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -81,8 +81,11 @@ static void process_tree(struct rev_info *revs,
 		die("bad tree object");
 	if (obj->flags & (UNINTERESTING | SEEN))
 		return;
-	if (parse_tree(tree) < 0)
+	if (parse_tree(tree) < 0) {
+		if (revs->ignore_missing_links)
+			return;
 		die("bad tree object %s", sha1_to_hex(obj->sha1));
+	}
 	obj->flags |= SEEN;
 	show(obj, path, name, cb_data);
 	me.up = path;
diff --git a/pack-bitmap.c b/pack-bitmap.c
index ae0b57b..91e4101 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -727,8 +727,10 @@ int prepare_bitmap_walk(struct rev_info *revs)
 	revs->pending.objects = NULL;
 
 	if (haves) {
+		revs->ignore_missing_links = 1;
 		haves_bitmap = find_objects(revs, haves, NULL);
 		reset_revision_walk();
+		revs->ignore_missing_links = 0;
 
 		if (haves_bitmap == NULL)
 			die("BUG: failed to perform bitmap walk");
diff --git a/revision.c b/revision.c
index 8508550..b3b88e1 100644
--- a/revision.c
+++ b/revision.c
@@ -2929,9 +2929,11 @@ static struct commit *get_revision_1(struct rev_info *revs)
 			if (revs->max_age != -1 &&
 			    (commit->date < revs->max_age))
 				continue;
-			if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)
-				die("Failed to traverse parents of commit %s",
-				    sha1_to_hex(commit->object.sha1));
+			if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
+				if (!revs->ignore_missing_links)
+					die("Failed to traverse parents of commit %s",
+						sha1_to_hex(commit->object.sha1));
+			}
 		}
 
 		switch (simplify_commit(revs, commit)) {
diff --git a/revision.h b/revision.h
index 1eb94c1..0d997de 100644
--- a/revision.h
+++ b/revision.h
@@ -73,7 +73,8 @@ struct rev_info {
 	enum rev_sort_order sort_order;
 
 	unsigned int	early_output:1,
-			ignore_missing:1;
+			ignore_missing:1,
+			ignore_missing_links:1;
 
 	/* Traversal flags */
 	unsigned int	dense:1,
diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
index d3a3afa..caea802 100755
--- a/t/t5310-pack-bitmaps.sh
+++ b/t/t5310-pack-bitmaps.sh
@@ -3,6 +3,10 @@
 test_description='exercise basic bitmap functionality'
 . ./test-lib.sh
 
+objpath() {
+	echo ".git/objects/$(echo "$1" | sed -e 's|\(..\)|\1/|')"
+}
+
 test_expect_success 'setup repo with moderate-sized history' '
 	for i in $(test_seq 1 10); do
 		test_commit $i
@@ -112,6 +116,33 @@ test_expect_success 'fetch (full bitmap)' '
 	test_cmp expect actual
 '
 
+test_expect_success 'create objects for missing-HAVE tests' '
+	blob=$(echo "missing have" | git hash-object -w --stdin) &&
+	tree=$(printf "100644 blob $blob\tfile\n" | git mktree) &&
+	parent=$(echo parent | git commit-tree $tree) &&
+	commit=$(echo commit | git commit-tree $tree -p $parent) &&
+	cat >revs <<-EOF
+	HEAD
+	^HEAD^
+	^$commit
+	EOF
+'
+
+test_expect_success 'pack with missing blob' '
+	rm $(objpath $blob) &&
+	git pack-objects --stdout --revs <revs >/dev/null
+'
+
+test_expect_success 'pack with missing tree' '
+	rm $(objpath $tree) &&
+	git pack-objects --stdout --revs <revs >/dev/null
+'
+
+test_expect_success 'pack with missing parent' '
+	rm $(objpath $parent) &&
+	git pack-objects --stdout --revs <revs >/dev/null
+'
+
 test_lazy_prereq JGIT '
 	type jgit
 '
-- 
1.9.1.656.ge8a0637

Re: [PATCH] add `ignore_missing_links` mode to revwalk

[Siddharth Agarwal]

On 03/28/2014 03:00 AM, Jeff King wrote:
> From: Vicent Marti <tanoku@gmail.com>
>
> When pack-objects is computing the reachability bitmap to
> serve a fetch request, it can erroneously die() if some of
> the UNINTERESTING objects are not present. Upload-pack
> throws away HAVE lines from the client for objects we do not
> have, but we may have a tip object without all of its
> ancestors (e.g., if the tip is no longer reachable and was
> new enough to survive a `git prune`, but some of its
> reachable objects did get pruned).

Thanks for this patch. It looks pretty sensible.

Unfortunately, I can't provide feedback on running it in production 
because we've decided to set aside experimenting with bitmaps for a bit. 
I hope to get back to it in a couple of months.



>
> In the non-bitmap case, we do a revision walk with the HAVE
> objects marked as UNINTERESTING. The revision walker
> explicitly ignores errors in accessing UNINTERESTING commits
> to handle this case (and we do not bother looking at
> UNINTERESTING trees or blobs at all).
>
> When we have bitmaps, however, the process is quite
> different.  The bitmap index for a pack-objects run is
> calculated in two separate steps:
>
> First, we perform an extensive walk from all the HAVEs to
> find the full set of objects reachable from them. This walk
> is usually optimized away because we are expected to hit an
> object with a bitmap during the traversal, which allows us
> to terminate early.
>
> Secondly, we perform an extensive walk from all the WANTs,
> which usually also terminates early because we hit a commit
> with an existing bitmap.
>
> Once we have the resulting bitmaps from the two walks, we
> AND-NOT them together to obtain the resulting set of objects
> we need to pack.
>
> When we are walking the HAVE objects, the revision walker
> does not know that we are walking it only to mark the
> results as uninteresting. We strip out the UNINTERESTING flag,
> because those objects _are_ interesting to us during the
> first walk. We want to keep going to get a complete set of
> reachable objects if we can.
>
> We need some way to tell the revision walker that it's OK to
> silently truncate the HAVE walk, just like it does for the
> UNINTERESTING case. This patch introduces a new
> `ignore_missing_links` flag to the `rev_info` struct, which
> we set only for the HAVE walk.
>
> It also adds tests to cover UNINTERESTING objects missing
> from several positions: a missing blob, a missing tree, and
> a missing parent commit. The missing blob already worked (as
> we do not care about its contents at all), but the other two
> cases caused us to die().
>
> Note that there are a few cases we do not need to test:
>
>    1. We do not need to test a missing tree, with the blob
>       still present. Without the tree that refers to it, we
>       would not know that the blob is relevant to our walk.
>
>    2. We do not need to test a tip commit that is missing.
>       Upload-pack omits these for us (and in fact, we
>       complain even in the non-bitmap case if it fails to do
>       so).
>
> Reported-by: Siddharth Agarwal <sid0@fb.com>
> Signed-off-by: Vicent Marti <tanoku@gmail.com>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> I believe this should solve the problem you're seeing, and I think any
> solution is going to be along these lines.
>
> This covers all code paths that can be triggered by pack-objects.  But
> it does not necessarily cover all code paths that a revision walker
> might use (e.g., it is still possible to die in try_to_simplify_commit,
> but we would never hit that in pack-objects, because we do not do
> pathspec limiting).
>
> So it's a tradeoff. On the one hand, leaving it like this creates a flag
> in rev_info that may surprise somebody later by not being as generally
> useful. On the other hand, covering every die() is extra code churn, and
> creates complexity for cases that cannot actually be triggered in
> practice (complexity because each site has to decide how to handle a
> failure to access the object).
>
>   list-objects.c          |  5 ++++-
>   pack-bitmap.c           |  2 ++
>   revision.c              |  8 +++++---
>   revision.h              |  3 ++-
>   t/t5310-pack-bitmaps.sh | 31 +++++++++++++++++++++++++++++++
>   5 files changed, 44 insertions(+), 5 deletions(-)
>
> diff --git a/list-objects.c b/list-objects.c
> index 206816f..3595ee7 100644
> --- a/list-objects.c
> +++ b/list-objects.c
> @@ -81,8 +81,11 @@ static void process_tree(struct rev_info *revs,
>   		die("bad tree object");
>   	if (obj->flags & (UNINTERESTING | SEEN))
>   		return;
> -	if (parse_tree(tree) < 0)
> +	if (parse_tree(tree) < 0) {
> +		if (revs->ignore_missing_links)
> +			return;
>   		die("bad tree object %s", sha1_to_hex(obj->sha1));
> +	}
>   	obj->flags |= SEEN;
>   	show(obj, path, name, cb_data);
>   	me.up = path;
> diff --git a/pack-bitmap.c b/pack-bitmap.c
> index ae0b57b..91e4101 100644
> --- a/pack-bitmap.c
> +++ b/pack-bitmap.c
> @@ -727,8 +727,10 @@ int prepare_bitmap_walk(struct rev_info *revs)
>   	revs->pending.objects = NULL;
>   
>   	if (haves) {
> +		revs->ignore_missing_links = 1;
>   		haves_bitmap = find_objects(revs, haves, NULL);
>   		reset_revision_walk();
> +		revs->ignore_missing_links = 0;
>   
>   		if (haves_bitmap == NULL)
>   			die("BUG: failed to perform bitmap walk");
> diff --git a/revision.c b/revision.c
> index 8508550..b3b88e1 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -2929,9 +2929,11 @@ static struct commit *get_revision_1(struct rev_info *revs)
>   			if (revs->max_age != -1 &&
>   			    (commit->date < revs->max_age))
>   				continue;
> -			if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)
> -				die("Failed to traverse parents of commit %s",
> -				    sha1_to_hex(commit->object.sha1));
> +			if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
> +				if (!revs->ignore_missing_links)
> +					die("Failed to traverse parents of commit %s",
> +						sha1_to_hex(commit->object.sha1));
> +			}
>   		}
>   
>   		switch (simplify_commit(revs, commit)) {
> diff --git a/revision.h b/revision.h
> index 1eb94c1..0d997de 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -73,7 +73,8 @@ struct rev_info {
>   	enum rev_sort_order sort_order;
>   
>   	unsigned int	early_output:1,
> -			ignore_missing:1;
> +			ignore_missing:1,
> +			ignore_missing_links:1;
>   
>   	/* Traversal flags */
>   	unsigned int	dense:1,
> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
> index d3a3afa..caea802 100755
> --- a/t/t5310-pack-bitmaps.sh
> +++ b/t/t5310-pack-bitmaps.sh
> @@ -3,6 +3,10 @@
>   test_description='exercise basic bitmap functionality'
>   . ./test-lib.sh
>   
> +objpath() {
> +	echo ".git/objects/$(echo "$1" | sed -e 's|\(..\)|\1/|')"
> +}
> +
>   test_expect_success 'setup repo with moderate-sized history' '
>   	for i in $(test_seq 1 10); do
>   		test_commit $i
> @@ -112,6 +116,33 @@ test_expect_success 'fetch (full bitmap)' '
>   	test_cmp expect actual
>   '
>   
> +test_expect_success 'create objects for missing-HAVE tests' '
> +	blob=$(echo "missing have" | git hash-object -w --stdin) &&
> +	tree=$(printf "100644 blob $blob\tfile\n" | git mktree) &&
> +	parent=$(echo parent | git commit-tree $tree) &&
> +	commit=$(echo commit | git commit-tree $tree -p $parent) &&
> +	cat >revs <<-EOF
> +	HEAD
> +	^HEAD^
> +	^$commit
> +	EOF
> +'
> +
> +test_expect_success 'pack with missing blob' '
> +	rm $(objpath $blob) &&
> +	git pack-objects --stdout --revs <revs >/dev/null
> +'
> +
> +test_expect_success 'pack with missing tree' '
> +	rm $(objpath $tree) &&
> +	git pack-objects --stdout --revs <revs >/dev/null
> +'
> +
> +test_expect_success 'pack with missing parent' '
> +	rm $(objpath $parent) &&
> +	git pack-objects --stdout --revs <revs >/dev/null
> +'
> +
>   test_lazy_prereq JGIT '
>   	type jgit
>   '

Re: [PATCH] add `ignore_missing_links` mode to revwalk

[Jeff King]

On Mon, Mar 31, 2014 at 02:48:45PM -0700, Siddharth Agarwal wrote:

> On 03/28/2014 03:00 AM, Jeff King wrote:
> >From: Vicent Marti <tanoku@gmail.com>
> >
> >When pack-objects is computing the reachability bitmap to serve a
> >fetch request, it can erroneously die() if some of the UNINTERESTING
> >objects are not present. Upload-pack throws away HAVE lines from the
> >client for objects we do not have, but we may have a tip object
> >without all of its ancestors (e.g., if the tip is no longer reachable
> >and was new enough to survive a `git prune`, but some of its
> >reachable objects did get pruned).
> 
> Thanks for this patch. It looks pretty sensible.
> 
> Unfortunately, I can't provide feedback on running it in production
> because we've decided to set aside experimenting with bitmaps for a
> bit. I hope to get back to it in a couple of months.

Bummer. Thanks for taking a look at it.

I do think this patch is definitely fixing a bug, and needs to be
pursued.  We've been running with bitmaps in production on GitHub since
last summer, but have never run into this situation. However, I think it
is largely caused by our pruning parameters:

  1. We tend not to prune very often, and instead keep unreachable
     objects around as a safety mechanism.

  2. When we do prune, we use a very tight cutoff, rather than the
     default 2-week period. So the window of opportunity is much smaller
     for a repo to prune an object but not its descendant (typically
     either we keep both, or they both get pruned).

So if you do come back to it later, the fix should have filtered through
to "master" by then. :)

-Peff