Re: [PATCH] add `ignore_missing_links` mode to revwalk
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 tan...@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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] add `ignore_missing_links` mode to revwalk
On 03/28/2014 03:00 AM, Jeff King wrote: From: Vicent Marti tan...@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 s...@fb.com Signed-off-by: Vicent Marti tan...@gmail.com Signed-off-by: Jeff King p...@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;
[PATCH] add `ignore_missing_links` mode to revwalk
From: Vicent Marti tan...@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 s...@fb.com Signed-off-by: Vicent Marti tan...@gmail.com Signed-off-by: Jeff King p...@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