diff mbox series

prune: save reachable-from-recent objects with bitmaps

Message ID YIgxPtDmr9sYj0ft@coredump.intra.peff.net (mailing list archive)
State Superseded
Headers show
Series prune: save reachable-from-recent objects with bitmaps | expand

Commit Message

Jeff King April 27, 2021, 3:43 p.m. UTC 
On Tue, Apr 27, 2021 at 11:45:01AM +0100, David Emett wrote:

> I assume (2) is not intentional, given that "git gc --help" explicitly says
> "Any object with modification time newer than the --prune date is kept, along
> with everything reachable from it." Is it safe to just run the mark_recent
> block after the bitmap_git block? Could add_unseen_recent_objects_to_traversal
> just be called at the start of the bitmap_git block if mark_recent?

Here's a fix. Thanks very much for reporting.

I was a little surprised you saw this with "git gc", as when I tried
testing with that, I found that the "git repack" run before "git prune"
works around the bug (see the discussion of t6501 below). But I think
perhaps it is just that "gc --auto" is more willing to do a "repack -d"
sometimes, rather than a full "repack -A". At any rate, I was able to
easily reproduce it for the tests with just git-prune.

-- >8 --
Subject: prune: save reachable-from-recent objects with bitmaps

We pass our prune expiration to mark_reachable_objects(), which will
traverse not only the reachable objects, but consider any recent ones as
tips for reachability; see d3038d22f9 (prune: keep objects reachable
from recent objects, 2014-10-15) for details.

However, this interacts badly with the bitmap code path added in
fde67d6896 (prune: use bitmaps for reachability traversal, 2019-02-13).
If we hit the bitmap-optimized path, we return immediately to avoid the
regular traversal, accidentally skipping the "also traverse recent"
code.

Instead, we should do an if-else for the bitmap versus regular
traversal, and then follow up with the "recent" traversal in either
case. This reuses the "rev_info" for a bitmap and then a regular
traversal, but that should work OK (the bitmap code clears the pending
array in the usual way, just like a regular traversal would).

Note that I dropped the comment above the regular traversal here.  It
has little explanatory value, and makes the if-else logic much harder to
read.

Here are a few variants that I rejected:

  - it seems like both the reachability and recent traversals could be
    done in a single traversal. This was rejected by d3038d22f9 (prune:
    keep objects reachable from recent objects, 2014-10-15), though the
    balance may be different when using bitmaps. However, there's a
    subtle correctness issue, too: we use revs->ignore_missing_links for
    the recent traversal, but not the reachability one.

  - we could try using bitmaps for the recent traversal, too, which
    could possibly improve performance. But it would require some fixes
    in the bitmap code, which uses ignore_missing_links for its own
    purposes. Plus it would probably not help all that much in practice.
    We use the reachable tips to generate bitmaps, so those objects are
    likely not covered by bitmaps (unless they just became unreachable).
    And in general, we expect the set of unreachable objects to be much
    smaller anyway, so there's less to gain.

The test in t5304 detects the bug and confirms the fix.

I also beefed up the tests in t6501, which covers the mtime-checking
code more thoroughly, to handle the bitmap case (in addition to just
"loose" and "packed" cases). Interestingly, this test doesn't actually
detect the bug, because it is running "git gc", and not "prune"
directly. And "gc" will call "repack" first, which does not suffer the
same bug. So the old-but-reachable-from-recent objects get scooped up
into the new pack along with the actually-recent objects, which gives
both a recent mtime. But it seemed prudent to get more coverage of the
bitmap case for related code.

Reported-by: David Emett <dave@sp4m.net>
Signed-off-by: Jeff King <peff@peff.net>
---
 reachable.c                | 13 ++++---------
 t/t5304-prune.sh           | 13 +++++++++++++
 t/t6501-freshen-objects.sh | 21 +++++++++++++++------
 3 files changed, 32 insertions(+), 15 deletions(-)

Comments

David Emett April 28, 2021, 12:20 p.m. UTC | #1 
> Here's a fix. Thanks very much for reporting.

Thanks for the quick response! I tried the fix out on the repo I was having
trouble with. It's hitting a segfault in traverse_commit_list in the
mark_recent block. It looks like the issue is that the bitmap code leaves
revs->include_check set, with revs->include_check_data pointing at the stack.
Setting revs->include_check to NULL after the traverse_commit_list call in
find_objects in pack-bitmap.c fixes the segfault for me. And the original issue
appears to be resolved as well, so thanks!

> I was a little surprised you saw this with "git gc", as when I tried
> testing with that, I found that the "git repack" run before "git prune"
> works around the bug (see the discussion of t6501 below). But I think
> perhaps it is just that "gc --auto" is more willing to do a "repack -d"
> sometimes, rather than a full "repack -A". At any rate, I was able to
> easily reproduce it for the tests with just git-prune.

I can't say for sure that this bug is what I was seeing originally, however it
does seem quite likely -- the commits that hit issues were minor updates of
commits that had been fetched a month or so earlier, and so would certainly fit
the bill. Like you though I've just been reproducing with git prune.
Jeff King April 28, 2021, 3:13 p.m. UTC | #2 
On Wed, Apr 28, 2021 at 01:20:03PM +0100, David Emett wrote:

> > Here's a fix. Thanks very much for reporting.
> 
> Thanks for the quick response! I tried the fix out on the repo I was having
> trouble with. It's hitting a segfault in traverse_commit_list in the
> mark_recent block. It looks like the issue is that the bitmap code leaves
> revs->include_check set, with revs->include_check_data pointing at the stack.
> Setting revs->include_check to NULL after the traverse_commit_list call in
> find_objects in pack-bitmap.c fixes the segfault for me. And the original issue
> appears to be resolved as well, so thanks!

Oof, good catch. I wondered why my test didn't see this. The answer is
that the include_check only applies to commits, not trees. And my test
only has a recent-but-unreachable tree. Beefing it up to include an
actual commit shows the problem (and ASan nicely pinpoints the issue).

The solution, as you noted, is to have the bitmap code clean up after
itself.

I'll prepare a re-roll of the series.

-Peff
diff mbox series

Patch

diff --git a/reachable.c b/reachable.c
index 77a60c70a5..a088717eb5 100644
--- a/reachable.c
+++ b/reachable.c
@@ -227,17 +227,12 @@  void mark_reachable_objects(struct rev_info *revs, int mark_reflog,
 	if (bitmap_git) {
 		traverse_bitmap_commit_list(bitmap_git, revs, mark_object_seen);
 		free_bitmap_index(bitmap_git);
-		return;
+	} else {
+		if (prepare_revision_walk(revs))
+			die("revision walk setup failed");
+		traverse_commit_list(revs, mark_commit, mark_object, &cp);
 	}
 
-	/*
-	 * Set up the revision walk - this will move all commits
-	 * from the pending list to the commit walking list.
-	 */
-	if (prepare_revision_walk(revs))
-		die("revision walk setup failed");
-	traverse_commit_list(revs, mark_commit, mark_object, &cp);
-
 	if (mark_recent) {
 		revs->ignore_missing_links = 1;
 		if (add_unseen_recent_objects_to_traversal(revs, mark_recent))
diff --git a/t/t5304-prune.sh b/t/t5304-prune.sh
index b447ce56a9..20fcc2da1f 100755
--- a/t/t5304-prune.sh
+++ b/t/t5304-prune.sh
@@ -352,4 +352,17 @@  test_expect_success 'trivial prune with bitmaps enabled' '
 	test_must_fail git cat-file -e $blob
 '
 
+test_expect_success 'old reachable-from-recent retained with bitmaps' '
+	git repack -adb &&
+	to_drop=$(echo bitmap-from-recent-1 | git hash-object -w --stdin) &&
+	test-tool chmtime -86400 .git/objects/$(test_oid_to_path $to_drop) &&
+	to_save=$(echo bitmap-from-recent-2 | git hash-object -w --stdin) &&
+	test-tool chmtime -86400 .git/objects/$(test_oid_to_path $to_save) &&
+	tree=$(printf "100644 blob $to_save\tfile\n" | git mktree) &&
+	git prune --expire=12.hours.ago &&
+	git cat-file -e $tree &&
+	git cat-file -e $to_save &&
+	test_must_fail git cat-file -e $to_drop
+'
+
 test_done
diff --git a/t/t6501-freshen-objects.sh b/t/t6501-freshen-objects.sh
index 75210f012b..de7742cc51 100755
--- a/t/t6501-freshen-objects.sh
+++ b/t/t6501-freshen-objects.sh
@@ -43,15 +43,24 @@  commit () {
 }
 
 maybe_repack () {
-	if test -n "$repack"; then
+	case "$title" in
+	loose)
+		: skip repack
+		;;
+	repack)
 		git repack -ad
-	fi
+		;;
+	bitmap)
+		git repack -adb
+		;;
+	*)
+		echo >&2 "unknown test type in maybe_repack"
+		return 1
+		;;
+	esac
 }
 
-for repack in '' true; do
-	title=${repack:+repack}
-	title=${title:-loose}
-
+for title in loose repack bitmap; do
 	test_expect_success "make repo completely empty ($title)" '
 		rm -rf .git &&
 		git init