bitmap: integrate a lookup table extension to the bitmap format

From: Abhradeep Chakraborty <[email protected]>

Teach Git to provide a way for users to enable/disable bitmap lookup table extension by providing a config option named 'writeBitmapLookupTable'. Default is false.

Also add test to verify writting of lookup table.

Mentored-by Taylor Blau <[email protected]>

Co-Mentored-by Kaartic Sivaraam <[email protected]>

Co-Authored-by Taylor Blau <[email protected]>

Signed-off-by Abhradeep Chakraborty <[email protected]>

---
 Documentation/config/pack.txt     |   7 +
 builtin/multi-pack-index.c        |   7 +
 builtin/pack-objects.c            |   8 +
 midx.c                            |   3 +
 midx.h                            |   1 +
 t/t5310-pack-bitmaps.sh           | 792 ++++++++++++++++--------------
 t/t5311-pack-bitmaps-shallow.sh   |  53 +-
 t/t5326-multi-pack-bitmaps.sh     | 421 +++++++++-------

 t/t5327-multi-pack-bitmaps-rev.sh |  24 +-
 9 files changed, 733 insertions(+), 583 deletions(-)

Documentation/config/pack.txt +7 -0

index ad7f73a1ead..b955ca572ec 100644
@@ -164,6 +164,13 @@ When writing a multi-pack reachability bitmap, no new namehashes are
 computed; instead, any namehashes stored in an existing bitmap are
 permuted into their appropriate location when writing a new bitmap.
 
+pack.writeBitmapLookupTable::
+	When true, Git will include a "lookup table" section in the
+	bitmap index (if one is written). This table is used to defer
+	loading individual bitmaps as late as possible. This can be
+	beneficial in repositories that have relatively large bitmap
+	indexes. Defaults to false.
+
 pack.writeReverseIndex::
 	When true, git will write a corresponding .rev file (see:
 	link:../technical/pack-format.html[Documentation/technical/pack-format.txt])

builtin/multi-pack-index.c +7 -0

index 5edbb7fe86e..55402b46f41 100644
@@ -87,6 +87,13 @@ static int git_multi_pack_index_write_config(const char *var, const char *value,
 			opts.flags &= ~MIDX_WRITE_BITMAP_HASH_CACHE;
 	}
 
+	if (!strcmp(var, "pack.writebitmaplookuptable")) {
+		if (git_config_bool(var, value))
+			opts.flags |= MIDX_WRITE_BITMAP_LOOKUP_TABLE;
+		else
+			opts.flags &= ~MIDX_WRITE_BITMAP_LOOKUP_TABLE;
+	}
+
 	/*
 	 * We should never make a fall-back call to 'git_default_config', since
 	 * this was already called in 'cmd_multi_pack_index()'.

builtin/pack-objects.c +8 -0

index 39e28cfcafc..46e26774963 100644
@@ -3148,6 +3148,14 @@ static int git_pack_config(const char *k, const char *v, void *cb)
 		else
 			write_bitmap_options &= ~BITMAP_OPT_HASH_CACHE;
 	}
+
+	if (!strcmp(k, "pack.writebitmaplookuptable")) {
+		if (git_config_bool(k, v))
+			write_bitmap_options |= BITMAP_OPT_LOOKUP_TABLE;
+		else
+			write_bitmap_options &= ~BITMAP_OPT_LOOKUP_TABLE;
+	}
+
 	if (!strcmp(k, "pack.usebitmaps")) {
 		use_bitmap_index_default = git_config_bool(k, v);
 		return 0;

midx.c +3 -0

index 5f0dd386b02..9c26d04bfde 100644
@@ -1072,6 +1072,9 @@ static int write_midx_bitmap(char *midx_name, unsigned char *midx_hash,
 	if (flags & MIDX_WRITE_BITMAP_HASH_CACHE)
 		options |= BITMAP_OPT_HASH_CACHE;
 
+	if (flags & MIDX_WRITE_BITMAP_LOOKUP_TABLE)
+		options |= BITMAP_OPT_LOOKUP_TABLE;
+
 	prepare_midx_packing_data(&pdata, ctx);
 
 	commits = find_commits_for_midx_bitmap(&commits_nr, refs_snapshot, ctx);

midx.h +1 -0

index 22e8e53288e..5578cd7b835 100644
@@ -47,6 +47,7 @@ struct multi_pack_index {
 #define MIDX_WRITE_REV_INDEX (1 << 1)
 #define MIDX_WRITE_BITMAP (1 << 2)
 #define MIDX_WRITE_BITMAP_HASH_CACHE (1 << 3)
+#define MIDX_WRITE_BITMAP_LOOKUP_TABLE (1 << 4)
 
 const unsigned char *get_midx_checksum(struct multi_pack_index *m);
 void get_midx_filename(struct strbuf *out, const char *object_dir);

t/t5310-pack-bitmaps.sh +410 -382

index f775fc1ce69..c0607172827 100755
@@ -26,22 +26,413 @@ has_any () {
 	grep -Ff "$1" "$2"
 }
 
-setup_bitmap_history
-
-test_expect_success 'setup writing bitmaps during repack' '
-	git config repack.writeBitmaps true
-'
-
-test_expect_success 'full repack creates bitmaps' '
-	GIT_TRACE2_EVENT="$(pwd)/trace" \
+test_bitmap_cases () {
+	writeLookupTable=false
+	for i in "$@"
+	do
+		case "$i" in
+		"pack.writeBitmapLookupTable") writeLookupTable=true;;
+		esac
+	done
+
+	test_expect_success 'setup test repository' '
+		rm -fr * .git &&
+		git init &&
+		git config pack.writeBitmapLookupTable '"$writeLookupTable"'
+	'
+	setup_bitmap_history
+
+	test_expect_success 'setup writing bitmaps during repack' '
+		git config repack.writeBitmaps true
+	'
+
+	test_expect_success 'full repack creates bitmaps' '
+		GIT_TRACE2_EVENT="$(pwd)/trace" \
+			git repack -ad &&
+		ls .git/objects/pack/ | grep bitmap >output &&
+		test_line_count = 1 output &&
+		grep "\"key\":\"num_selected_commits\",\"value\":\"106\"" trace &&
+		grep "\"key\":\"num_maximal_commits\",\"value\":\"107\"" trace
+	'
+
+	basic_bitmap_tests
+
+	test_expect_success 'pack-objects respects --local (non-local loose)' '
+		git init --bare alt.git &&
+		echo $(pwd)/alt.git/objects >.git/objects/info/alternates &&
+		echo content1 >file1 &&
+		# non-local loose object which is not present in bitmapped pack
+		altblob=$(GIT_DIR=alt.git git hash-object -w file1) &&
+		# non-local loose object which is also present in bitmapped pack
+		git cat-file blob $blob | GIT_DIR=alt.git git hash-object -w --stdin &&
+		git add file1 &&
+		test_tick &&
+		git commit -m commit_file1 &&
+		echo HEAD | git pack-objects --local --stdout --revs >1.pack &&
+		git index-pack 1.pack &&
+		list_packed_objects 1.idx >1.objects &&
+		printf "%s\n" "$altblob" "$blob" >nonlocal-loose &&
+		! has_any nonlocal-loose 1.objects
+	'
+
+	test_expect_success 'pack-objects respects --honor-pack-keep (local non-bitmapped pack)' '
+		echo content2 >file2 &&
+		blob2=$(git hash-object -w file2) &&
+		git add file2 &&
+		test_tick &&
+		git commit -m commit_file2 &&
+		printf "%s\n" "$blob2" "$bitmaptip" >keepobjects &&
+		pack2=$(git pack-objects pack2 <keepobjects) &&
+		mv pack2-$pack2.* .git/objects/pack/ &&
+		>.git/objects/pack/pack2-$pack2.keep &&
+		rm $(objpath $blob2) &&
+		echo HEAD | git pack-objects --honor-pack-keep --stdout --revs >2a.pack &&
+		git index-pack 2a.pack &&
+		list_packed_objects 2a.idx >2a.objects &&
+		! has_any keepobjects 2a.objects
+	'
+
+	test_expect_success 'pack-objects respects --local (non-local pack)' '
+		mv .git/objects/pack/pack2-$pack2.* alt.git/objects/pack/ &&
+		echo HEAD | git pack-objects --local --stdout --revs >2b.pack &&
+		git index-pack 2b.pack &&
+		list_packed_objects 2b.idx >2b.objects &&
+		! has_any keepobjects 2b.objects
+	'
+
+	test_expect_success 'pack-objects respects --honor-pack-keep (local bitmapped pack)' '
+		ls .git/objects/pack/ | grep bitmap >output &&
+		test_line_count = 1 output &&
+		packbitmap=$(basename $(cat output) .bitmap) &&
+		list_packed_objects .git/objects/pack/$packbitmap.idx >packbitmap.objects &&
+		test_when_finished "rm -f .git/objects/pack/$packbitmap.keep" &&
+		>.git/objects/pack/$packbitmap.keep &&
+		echo HEAD | git pack-objects --honor-pack-keep --stdout --revs >3a.pack &&
+		git index-pack 3a.pack &&
+		list_packed_objects 3a.idx >3a.objects &&
+		! has_any packbitmap.objects 3a.objects
+	'
+
+	test_expect_success 'pack-objects respects --local (non-local bitmapped pack)' '
+		mv .git/objects/pack/$packbitmap.* alt.git/objects/pack/ &&
+		rm -f .git/objects/pack/multi-pack-index &&
+		test_when_finished "mv alt.git/objects/pack/$packbitmap.* .git/objects/pack/" &&
+		echo HEAD | git pack-objects --local --stdout --revs >3b.pack &&
+		git index-pack 3b.pack &&
+		list_packed_objects 3b.idx >3b.objects &&
+		! has_any packbitmap.objects 3b.objects
+	'
+
+	test_expect_success 'pack-objects to file can use bitmap' '
+		# make sure we still have 1 bitmap index from previous tests
+		ls .git/objects/pack/ | grep bitmap >output &&
+		test_line_count = 1 output &&
+		# verify equivalent packs are generated with/without using bitmap index
+		packasha1=$(git pack-objects --no-use-bitmap-index --all packa </dev/null) &&
+		packbsha1=$(git pack-objects --use-bitmap-index --all packb </dev/null) &&
+		list_packed_objects packa-$packasha1.idx >packa.objects &&
+		list_packed_objects packb-$packbsha1.idx >packb.objects &&
+		test_cmp packa.objects packb.objects
+	'
+
+	test_expect_success 'full repack, reusing previous bitmaps' '
 		git repack -ad &&
-	ls .git/objects/pack/ | grep bitmap >output &&
-	test_line_count = 1 output &&
-	grep "\"key\":\"num_selected_commits\",\"value\":\"106\"" trace &&
-	grep "\"key\":\"num_maximal_commits\",\"value\":\"107\"" trace
-'
+		ls .git/objects/pack/ | grep bitmap >output &&
+		test_line_count = 1 output
+	'
+
+	test_expect_success 'fetch (full bitmap)' '
+		git --git-dir=clone.git fetch origin second:second &&
+		git rev-parse HEAD >expect &&
+		git --git-dir=clone.git rev-parse HEAD >actual &&
+		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-objects respects --incremental' '
+		cat >revs2 <<-EOF &&
+		HEAD
+		$commit
+		EOF
+		git pack-objects --incremental --stdout --revs <revs2 >4.pack &&
+		git index-pack 4.pack &&
+		list_packed_objects 4.idx >4.objects &&
+		test_line_count = 4 4.objects &&
+		git rev-list --objects $commit >revlist &&
+		cut -d" " -f1 revlist |sort >objects &&
+		test_cmp 4.objects objects
+	'
+
+	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_expect_success JGIT,SHA1 'we can read jgit bitmaps' '
+		git clone --bare . compat-jgit.git &&
+		(
+			cd compat-jgit.git &&
+			rm -f objects/pack/*.bitmap &&
+			jgit gc &&
+			git rev-list --test-bitmap HEAD
+		)
+	'
+
+	test_expect_success JGIT,SHA1 'jgit can read our bitmaps' '
+		git clone --bare . compat-us.git &&
+		(
+			cd compat-us.git &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
+			git repack -adb &&
+			# jgit gc will barf if it does not like our bitmaps
+			jgit gc
+		)
+	'
+
+	test_expect_success 'splitting packs does not generate bogus bitmaps' '
+		test-tool genrandom foo $((1024 * 1024)) >rand &&
+		git add rand &&
+		git commit -m "commit with big file" &&
+		git -c pack.packSizeLimit=500k repack -adb &&
+		git init --bare no-bitmaps.git &&
+		git -C no-bitmaps.git fetch .. HEAD
+	'
+
+	test_expect_success 'set up reusable pack' '
+		rm -f .git/objects/pack/*.keep &&
+		git repack -adb &&
+		reusable_pack () {
+			git for-each-ref --format="%(objectname)" |
+			git pack-objects --delta-base-offset --revs --stdout "$@"
+		}
+	'
+
+	test_expect_success 'pack reuse respects --honor-pack-keep' '
+		test_when_finished "rm -f .git/objects/pack/*.keep" &&
+		for i in .git/objects/pack/*.pack
+		do
+			>${i%.pack}.keep || return 1
+		done &&
+		reusable_pack --honor-pack-keep >empty.pack &&
+		git index-pack empty.pack &&
+		git show-index <empty.idx >actual &&
+		test_must_be_empty actual
+	'
+
+	test_expect_success 'pack reuse respects --local' '
+		mv .git/objects/pack/* alt.git/objects/pack/ &&
+		test_when_finished "mv alt.git/objects/pack/* .git/objects/pack/" &&
+		reusable_pack --local >empty.pack &&
+		git index-pack empty.pack &&
+		git show-index <empty.idx >actual &&
+		test_must_be_empty actual
+	'
+
+	test_expect_success 'pack reuse respects --incremental' '
+		reusable_pack --incremental >empty.pack &&
+		git index-pack empty.pack &&
+		git show-index <empty.idx >actual &&
+		test_must_be_empty actual
+	'
+
+	test_expect_success 'truncated bitmap fails gracefully (ewah)' '
+		test_config pack.writebitmaphashcache false &&
+		git repack -ad &&
+		git rev-list --use-bitmap-index --count --all >expect &&
+		bitmap=$(ls .git/objects/pack/*.bitmap) &&
+		test_when_finished "rm -f $bitmap" &&
+		test_copy_bytes 256 <$bitmap >$bitmap.tmp &&
+		mv -f $bitmap.tmp $bitmap &&
+		git rev-list --use-bitmap-index --count --all >actual 2>stderr &&
+		test_cmp expect actual &&
+		test_i18ngrep corrupt.ewah.bitmap stderr
+	'
+
+	test_expect_success 'truncated bitmap fails gracefully (cache)' '
+		git repack -ad &&
+		git rev-list --use-bitmap-index --count --all >expect &&
+		bitmap=$(ls .git/objects/pack/*.bitmap) &&
+		test_when_finished "rm -f $bitmap" &&
+		test_copy_bytes 512 <$bitmap >$bitmap.tmp &&
+		mv -f $bitmap.tmp $bitmap &&
+		git rev-list --use-bitmap-index --count --all >actual 2>stderr &&
+		test_cmp expect actual &&
+		test_i18ngrep corrupted.bitmap.index stderr
+	'
+
+	# Create a state of history with these properties:
+	#
+	#  - refs that allow a client to fetch some new history, while sharing some old
+	#    history with the server; we use branches delta-reuse-old and
+	#    delta-reuse-new here
+	#
+	#  - the new history contains an object that is stored on the server as a delta
+	#    against a base that is in the old history
+	#
+	#  - the base object is not immediately reachable from the tip of the old
+	#    history; finding it would involve digging down through history we know the
+	#    other side has
+	#
+	# This should result in a state where fetching from old->new would not
+	# traditionally reuse the on-disk delta (because we'd have to dig to realize
+	# that the client has it), but we will do so if bitmaps can tell us cheaply
+	# that the other side has it.
+	test_expect_success 'set up thin delta-reuse parent' '
+		# This first commit contains the buried base object.
+		test-tool genrandom delta 16384 >file &&
+		git add file &&
+		git commit -m "delta base" &&
+		base=$(git rev-parse --verify HEAD:file) &&
+
+		# These intermediate commits bury the base back in history.
+		# This becomes the "old" state.
+		for i in 1 2 3 4 5
+		do
+			echo $i >file &&
+			git commit -am "intermediate $i" || return 1
+		done &&
+		git branch delta-reuse-old &&
+
+		# And now our new history has a delta against the buried base. Note
+		# that this must be smaller than the original file, since pack-objects
+		# prefers to create deltas from smaller objects to larger.
+		test-tool genrandom delta 16300 >file &&
+		git commit -am "delta result" &&
+		delta=$(git rev-parse --verify HEAD:file) &&
+		git branch delta-reuse-new &&
+
+		# Repack with bitmaps and double check that we have the expected delta
+		# relationship.
+		git repack -adb &&
+		have_delta $delta $base
+	'
+
+	# Now we can sanity-check the non-bitmap behavior (that the server is not able
+	# to reuse the delta). This isn't strictly something we care about, so this
+	# test could be scrapped in the future. But it makes sure that the next test is
+	# actually triggering the feature we want.
+	#
+	# Note that our tools for working with on-the-wire "thin" packs are limited. So
+	# we actually perform the fetch, retain the resulting pack, and inspect the
+	# result.
+	test_expect_success 'fetch without bitmaps ignores delta against old base' '
+		test_config pack.usebitmaps false &&
+		test_when_finished "rm -rf client.git" &&
+		git init --bare client.git &&
+		(
+			cd client.git &&
+			git config transfer.unpackLimit 1 &&
+			git fetch .. delta-reuse-old:delta-reuse-old &&
+			git fetch .. delta-reuse-new:delta-reuse-new &&
+			have_delta $delta $ZERO_OID
+		)
+	'
+
+	# And do the same for the bitmap case, where we do expect to find the delta.
+	test_expect_success 'fetch with bitmaps can reuse old base' '
+		test_config pack.usebitmaps true &&
+		test_when_finished "rm -rf client.git" &&
+		git init --bare client.git &&
+		(
+			cd client.git &&
+			git config transfer.unpackLimit 1 &&
+			git fetch .. delta-reuse-old:delta-reuse-old &&
+			git fetch .. delta-reuse-new:delta-reuse-new &&
+			have_delta $delta $base
+		)
+	'
+
+	test_expect_success 'pack.preferBitmapTips' '
+		git init repo &&
+		test_when_finished "rm -fr repo" &&
+		(
+			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
+
+			# create enough commits that not all are receive bitmap
+			# coverage even if they are all at the tip of some reference.
+			test_commit_bulk --message="%s" 103 &&
+
+			git rev-list HEAD >commits.raw &&
+			sort <commits.raw >commits &&
+
+			git log --format="create refs/tags/%s %H" HEAD >refs &&
+			git update-ref --stdin <refs &&
+
+			git repack -adb &&
+			test-tool bitmap list-commits | sort >bitmaps &&
+
+			# remember which commits did not receive bitmaps
+			comm -13 bitmaps commits >before &&
+			test_file_not_empty before &&
+
+			# mark the commits which did not receive bitmaps as preferred,
+			# and generate the bitmap again
+			perl -pe "s{^}{create refs/tags/include/$. }" <before |
+				git update-ref --stdin &&
+			git -c pack.preferBitmapTips=refs/tags/include repack -adb &&
+
+			# finally, check that the commit(s) without bitmap coverage
+			# are not the same ones as before
+			test-tool bitmap list-commits | sort >bitmaps &&
+			comm -13 bitmaps commits >after &&
+
+			! test_cmp before after
+		)
+	'
+
+	test_expect_success 'complains about multiple pack bitmaps' '
+		rm -fr repo &&
+		git init repo &&
+		test_when_finished "rm -fr repo" &&
+		(
+			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
+
+			test_commit base &&
+
+			git repack -adb &&
+			bitmap="$(ls .git/objects/pack/pack-*.bitmap)" &&
+			mv "$bitmap" "$bitmap.bak" &&
+
+			test_commit other &&
+			git repack -ab &&
+
+			mv "$bitmap.bak" "$bitmap" &&
+
+			find .git/objects/pack -type f -name "*.pack" >packs &&
+			find .git/objects/pack -type f -name "*.bitmap" >bitmaps &&
+			test_line_count = 2 packs &&
+			test_line_count = 2 bitmaps &&
+
+			git rev-list --use-bitmap-index HEAD 2>err &&
+			grep "ignoring extra bitmap file" err
+		)
+	'
+}
 
-basic_bitmap_tests
+test_bitmap_cases
 
 test_expect_success 'incremental repack fails when bitmaps are requested' '
 	test_commit more-1 &&

@@ -54,375 +445,12 @@ test_expect_success 'incremental repack can disable bitmaps' '
 	git repack -d --no-write-bitmap-index
 '
 
-test_expect_success 'pack-objects respects --local (non-local loose)' '
-	git init --bare alt.git &&
-	echo $(pwd)/alt.git/objects >.git/objects/info/alternates &&
-	echo content1 >file1 &&
-	# non-local loose object which is not present in bitmapped pack
-	altblob=$(GIT_DIR=alt.git git hash-object -w file1) &&
-	# non-local loose object which is also present in bitmapped pack
-	git cat-file blob $blob | GIT_DIR=alt.git git hash-object -w --stdin &&
-	git add file1 &&
-	test_tick &&
-	git commit -m commit_file1 &&
-	echo HEAD | git pack-objects --local --stdout --revs >1.pack &&
-	git index-pack 1.pack &&
-	list_packed_objects 1.idx >1.objects &&
-	printf "%s\n" "$altblob" "$blob" >nonlocal-loose &&
-	! has_any nonlocal-loose 1.objects
-'
-
-test_expect_success 'pack-objects respects --honor-pack-keep (local non-bitmapped pack)' '
-	echo content2 >file2 &&
-	blob2=$(git hash-object -w file2) &&
-	git add file2 &&
-	test_tick &&
-	git commit -m commit_file2 &&
-	printf "%s\n" "$blob2" "$bitmaptip" >keepobjects &&
-	pack2=$(git pack-objects pack2 <keepobjects) &&
-	mv pack2-$pack2.* .git/objects/pack/ &&
-	>.git/objects/pack/pack2-$pack2.keep &&
-	rm $(objpath $blob2) &&
-	echo HEAD | git pack-objects --honor-pack-keep --stdout --revs >2a.pack &&
-	git index-pack 2a.pack &&
-	list_packed_objects 2a.idx >2a.objects &&
-	! has_any keepobjects 2a.objects
-'
-
-test_expect_success 'pack-objects respects --local (non-local pack)' '
-	mv .git/objects/pack/pack2-$pack2.* alt.git/objects/pack/ &&
-	echo HEAD | git pack-objects --local --stdout --revs >2b.pack &&
-	git index-pack 2b.pack &&
-	list_packed_objects 2b.idx >2b.objects &&
-	! has_any keepobjects 2b.objects
-'
-
-test_expect_success 'pack-objects respects --honor-pack-keep (local bitmapped pack)' '
-	ls .git/objects/pack/ | grep bitmap >output &&
-	test_line_count = 1 output &&
-	packbitmap=$(basename $(cat output) .bitmap) &&
-	list_packed_objects .git/objects/pack/$packbitmap.idx >packbitmap.objects &&
-	test_when_finished "rm -f .git/objects/pack/$packbitmap.keep" &&
-	>.git/objects/pack/$packbitmap.keep &&
-	echo HEAD | git pack-objects --honor-pack-keep --stdout --revs >3a.pack &&
-	git index-pack 3a.pack &&
-	list_packed_objects 3a.idx >3a.objects &&
-	! has_any packbitmap.objects 3a.objects
-'
-
-test_expect_success 'pack-objects respects --local (non-local bitmapped pack)' '
-	mv .git/objects/pack/$packbitmap.* alt.git/objects/pack/ &&
-	rm -f .git/objects/pack/multi-pack-index &&
-	test_when_finished "mv alt.git/objects/pack/$packbitmap.* .git/objects/pack/" &&
-	echo HEAD | git pack-objects --local --stdout --revs >3b.pack &&
-	git index-pack 3b.pack &&
-	list_packed_objects 3b.idx >3b.objects &&
-	! has_any packbitmap.objects 3b.objects
-'
-
-test_expect_success 'pack-objects to file can use bitmap' '
-	# make sure we still have 1 bitmap index from previous tests
-	ls .git/objects/pack/ | grep bitmap >output &&
-	test_line_count = 1 output &&
-	# verify equivalent packs are generated with/without using bitmap index
-	packasha1=$(git pack-objects --no-use-bitmap-index --all packa </dev/null) &&
-	packbsha1=$(git pack-objects --use-bitmap-index --all packb </dev/null) &&
-	list_packed_objects packa-$packasha1.idx >packa.objects &&
-	list_packed_objects packb-$packbsha1.idx >packb.objects &&
-	test_cmp packa.objects packb.objects
-'
-
-test_expect_success 'full repack, reusing previous bitmaps' '
-	git repack -ad &&
-	ls .git/objects/pack/ | grep bitmap >output &&
-	test_line_count = 1 output
-'
-
-test_expect_success 'fetch (full bitmap)' '
-	git --git-dir=clone.git fetch origin second:second &&
-	git rev-parse HEAD >expect &&
-	git --git-dir=clone.git rev-parse HEAD >actual &&
-	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-objects respects --incremental' '
-	cat >revs2 <<-EOF &&
-	HEAD
-	$commit
-	EOF
-	git pack-objects --incremental --stdout --revs <revs2 >4.pack &&
-	git index-pack 4.pack &&
-	list_packed_objects 4.idx >4.objects &&
-	test_line_count = 4 4.objects &&
-	git rev-list --objects $commit >revlist &&
-	cut -d" " -f1 revlist |sort >objects &&
-	test_cmp 4.objects objects
-'
-
-test_expect_success 'pack with missing blob' '
-	rm $(objpath $blob) &&
-	git pack-objects --stdout --revs <revs >/dev/null
-'
+test_bitmap_cases "pack.writeBitmapLookupTable"
 
-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_expect_success JGIT,SHA1 'we can read jgit bitmaps' '
-	git clone --bare . compat-jgit.git &&
-	(
-		cd compat-jgit.git &&
-		rm -f objects/pack/*.bitmap &&
-		jgit gc &&
-		git rev-list --test-bitmap HEAD
-	)
-'
-
-test_expect_success JGIT,SHA1 'jgit can read our bitmaps' '
-	git clone --bare . compat-us.git &&
-	(
-		cd compat-us.git &&
-		git repack -adb &&
-		# jgit gc will barf if it does not like our bitmaps
-		jgit gc
-	)
-'
-
-test_expect_success 'splitting packs does not generate bogus bitmaps' '
-	test-tool genrandom foo $((1024 * 1024)) >rand &&
-	git add rand &&
-	git commit -m "commit with big file" &&
-	git -c pack.packSizeLimit=500k repack -adb &&
-	git init --bare no-bitmaps.git &&
-	git -C no-bitmaps.git fetch .. HEAD
-'
-
-test_expect_success 'set up reusable pack' '
-	rm -f .git/objects/pack/*.keep &&
-	git repack -adb &&
-	reusable_pack () {
-		git for-each-ref --format="%(objectname)" |
-		git pack-objects --delta-base-offset --revs --stdout "$@"
-	}
-'
-
-test_expect_success 'pack reuse respects --honor-pack-keep' '
-	test_when_finished "rm -f .git/objects/pack/*.keep" &&
-	for i in .git/objects/pack/*.pack
-	do
-		>${i%.pack}.keep || return 1
-	done &&
-	reusable_pack --honor-pack-keep >empty.pack &&
-	git index-pack empty.pack &&
-	git show-index <empty.idx >actual &&
-	test_must_be_empty actual
-'
-
-test_expect_success 'pack reuse respects --local' '
-	mv .git/objects/pack/* alt.git/objects/pack/ &&
-	test_when_finished "mv alt.git/objects/pack/* .git/objects/pack/" &&
-	reusable_pack --local >empty.pack &&
-	git index-pack empty.pack &&
-	git show-index <empty.idx >actual &&
-	test_must_be_empty actual
-'
-
-test_expect_success 'pack reuse respects --incremental' '
-	reusable_pack --incremental >empty.pack &&
-	git index-pack empty.pack &&
-	git show-index <empty.idx >actual &&
-	test_must_be_empty actual
-'
-
-test_expect_success 'truncated bitmap fails gracefully (ewah)' '
-	test_config pack.writebitmaphashcache false &&
-	git repack -ad &&
-	git rev-list --use-bitmap-index --count --all >expect &&
-	bitmap=$(ls .git/objects/pack/*.bitmap) &&
-	test_when_finished "rm -f $bitmap" &&
-	test_copy_bytes 256 <$bitmap >$bitmap.tmp &&
-	mv -f $bitmap.tmp $bitmap &&
-	git rev-list --use-bitmap-index --count --all >actual 2>stderr &&
-	test_cmp expect actual &&
-	test_i18ngrep corrupt.ewah.bitmap stderr
-'
-
-test_expect_success 'truncated bitmap fails gracefully (cache)' '
-	git repack -ad &&
-	git rev-list --use-bitmap-index --count --all >expect &&
-	bitmap=$(ls .git/objects/pack/*.bitmap) &&
-	test_when_finished "rm -f $bitmap" &&
-	test_copy_bytes 512 <$bitmap >$bitmap.tmp &&
-	mv -f $bitmap.tmp $bitmap &&
-	git rev-list --use-bitmap-index --count --all >actual 2>stderr &&
-	test_cmp expect actual &&
-	test_i18ngrep corrupted.bitmap.index stderr
-'
-
-# Create a state of history with these properties:
-#
-#  - refs that allow a client to fetch some new history, while sharing some old
-#    history with the server; we use branches delta-reuse-old and
-#    delta-reuse-new here
-#
-#  - the new history contains an object that is stored on the server as a delta
-#    against a base that is in the old history
-#
-#  - the base object is not immediately reachable from the tip of the old
-#    history; finding it would involve digging down through history we know the
-#    other side has
-#
-# This should result in a state where fetching from old->new would not
-# traditionally reuse the on-disk delta (because we'd have to dig to realize
-# that the client has it), but we will do so if bitmaps can tell us cheaply
-# that the other side has it.
-test_expect_success 'set up thin delta-reuse parent' '
-	# This first commit contains the buried base object.
-	test-tool genrandom delta 16384 >file &&
-	git add file &&
-	git commit -m "delta base" &&
-	base=$(git rev-parse --verify HEAD:file) &&
-
-	# These intermediate commits bury the base back in history.
-	# This becomes the "old" state.
-	for i in 1 2 3 4 5
-	do
-		echo $i >file &&
-		git commit -am "intermediate $i" || return 1
-	done &&
-	git branch delta-reuse-old &&
-
-	# And now our new history has a delta against the buried base. Note
-	# that this must be smaller than the original file, since pack-objects
-	# prefers to create deltas from smaller objects to larger.
-	test-tool genrandom delta 16300 >file &&
-	git commit -am "delta result" &&
-	delta=$(git rev-parse --verify HEAD:file) &&
-	git branch delta-reuse-new &&
-
-	# Repack with bitmaps and double check that we have the expected delta
-	# relationship.
-	git repack -adb &&
-	have_delta $delta $base
-'
-
-# Now we can sanity-check the non-bitmap behavior (that the server is not able
-# to reuse the delta). This isn't strictly something we care about, so this
-# test could be scrapped in the future. But it makes sure that the next test is
-# actually triggering the feature we want.
-#
-# Note that our tools for working with on-the-wire "thin" packs are limited. So
-# we actually perform the fetch, retain the resulting pack, and inspect the
-# result.
-test_expect_success 'fetch without bitmaps ignores delta against old base' '
-	test_config pack.usebitmaps false &&
-	test_when_finished "rm -rf client.git" &&
-	git init --bare client.git &&
-	(
-		cd client.git &&
-		git config transfer.unpackLimit 1 &&
-		git fetch .. delta-reuse-old:delta-reuse-old &&
-		git fetch .. delta-reuse-new:delta-reuse-new &&
-		have_delta $delta $ZERO_OID
-	)
-'
-
-# And do the same for the bitmap case, where we do expect to find the delta.
-test_expect_success 'fetch with bitmaps can reuse old base' '
-	test_config pack.usebitmaps true &&
-	test_when_finished "rm -rf client.git" &&
-	git init --bare client.git &&
-	(
-		cd client.git &&
-		git config transfer.unpackLimit 1 &&
-		git fetch .. delta-reuse-old:delta-reuse-old &&
-		git fetch .. delta-reuse-new:delta-reuse-new &&
-		have_delta $delta $base
-	)
-'
-
-test_expect_success 'pack.preferBitmapTips' '
-	git init repo &&
-	test_when_finished "rm -fr repo" &&
-	(
-		cd repo &&
-
-		# create enough commits that not all are receive bitmap
-		# coverage even if they are all at the tip of some reference.
-		test_commit_bulk --message="%s" 103 &&
-
-		git rev-list HEAD >commits.raw &&
-		sort <commits.raw >commits &&
-
-		git log --format="create refs/tags/%s %H" HEAD >refs &&
-		git update-ref --stdin <refs &&
-
-		git repack -adb &&
-		test-tool bitmap list-commits | sort >bitmaps &&
-
-		# remember which commits did not receive bitmaps
-		comm -13 bitmaps commits >before &&
-		test_file_not_empty before &&
-
-		# mark the commits which did not receive bitmaps as preferred,
-		# and generate the bitmap again
-		perl -pe "s{^}{create refs/tags/include/$. }" <before |
-			git update-ref --stdin &&
-		git -c pack.preferBitmapTips=refs/tags/include repack -adb &&
-
-		# finally, check that the commit(s) without bitmap coverage
-		# are not the same ones as before
-		test-tool bitmap list-commits | sort >bitmaps &&
-		comm -13 bitmaps commits >after &&
-
-		! test_cmp before after
-	)
-'
-
-test_expect_success 'complains about multiple pack bitmaps' '
-	rm -fr repo &&
-	git init repo &&
-	test_when_finished "rm -fr repo" &&
-	(
-		cd repo &&
-
-		test_commit base &&
-
-		git repack -adb &&
-		bitmap="$(ls .git/objects/pack/pack-*.bitmap)" &&
-		mv "$bitmap" "$bitmap.bak" &&
-
-		test_commit other &&
-		git repack -ab &&
-
-		mv "$bitmap.bak" "$bitmap" &&
-
-		find .git/objects/pack -type f -name "*.pack" >packs &&
-		find .git/objects/pack -type f -name "*.bitmap" >bitmaps &&
-		test_line_count = 2 packs &&
-		test_line_count = 2 bitmaps &&
-
-		git rev-list --use-bitmap-index HEAD 2>err &&
-		grep "ignoring extra bitmap file" err
-	)
+test_expect_success 'verify writing bitmap lookup table when enabled' '
+	GIT_TRACE2_EVENT="$(pwd)/trace2" \
+		git repack -ad &&
+	grep "\"label\":\"writing_lookup_table\"" trace2
 '
 
 test_done

t/t5311-pack-bitmaps-shallow.sh +35 -18

index 872a95df338..9dae60f73e3 100755
@@ -17,23 +17,40 @@ test_description='check bitmap operation with shallow repositories'
 # the tree for A. But in a shallow one, we've grafted away
 # A, and fetching A to B requires that the other side send
 # us the tree for file=1.
-test_expect_success 'setup shallow repo' '
-	echo 1 >file &&
-	git add file &&
-	git commit -m orig &&
-	echo 2 >file &&
-	git commit -a -m update &&
-	git clone --no-local --bare --depth=1 . shallow.git &&
-	echo 1 >file &&
-	git commit -a -m repeat
-'
-
-test_expect_success 'turn on bitmaps in the parent' '
-	git repack -adb
-'
-
-test_expect_success 'shallow fetch from bitmapped repo' '
-	(cd shallow.git && git fetch)
-'
+test_shallow_bitmaps () {
+	writeLookupTable=false
+
+	for i in "$@"
+	do
+		case $i in
+		"pack.writeBitmapLookupTable") writeLookupTable=true;;
+		esac
+	done
+
+	test_expect_success 'setup shallow repo' '
+		rm -rf * .git &&
+		git init &&
+		git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
+		echo 1 >file &&
+		git add file &&
+		git commit -m orig &&
+		echo 2 >file &&
+		git commit -a -m update &&
+		git clone --no-local --bare --depth=1 . shallow.git &&
+		echo 1 >file &&
+		git commit -a -m repeat
+	'
+
+	test_expect_success 'turn on bitmaps in the parent' '
+		git repack -adb
+	'
+
+	test_expect_success 'shallow fetch from bitmapped repo' '
+		(cd shallow.git && git fetch)
+	'
+}
+
+test_shallow_bitmaps
+test_shallow_bitmaps "pack.writeBitmapLookupTable"
 
 test_done

t/t5326-multi-pack-bitmaps.sh +240 -181

index 4fe57414c13..3b206adcee6 100755
@@ -15,17 +15,24 @@ GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP=0
 sane_unset GIT_TEST_MIDX_WRITE_REV
 sane_unset GIT_TEST_MIDX_READ_RIDX
 
-midx_bitmap_core
-
 bitmap_reuse_tests() {
 	from=$1
 	to=$2
+	writeLookupTable=false
+
+	for i in $3-${$#}
+	do
+		case $i in
+		"pack.writeBitmapLookupTable") writeLookupTable=true;;
+		esac
+	done
 
 	test_expect_success "setup pack reuse tests ($from -> $to)" '
 		rm -fr repo &&
 		git init repo &&
 		(
 			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
 			test_commit_bulk 16 &&
 			git tag old-tip &&
 

@@ -43,6 +50,7 @@ bitmap_reuse_tests() {
 	test_expect_success "build bitmap from existing ($from -> $to)" '
 		(
 			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
 			test_commit_bulk --id=further 16 &&
 			git tag new-tip &&
 

@@ -59,6 +67,7 @@ bitmap_reuse_tests() {
 	test_expect_success "verify resulting bitmaps ($from -> $to)" '
 		(
 			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
 			git for-each-ref &&
 			git rev-list --test-bitmap refs/tags/old-tip &&
 			git rev-list --test-bitmap refs/tags/new-tip

@@ -66,244 +75,294 @@ bitmap_reuse_tests() {
 	'
 }
 
-bitmap_reuse_tests 'pack' 'MIDX'
-bitmap_reuse_tests 'MIDX' 'pack'
-bitmap_reuse_tests 'MIDX' 'MIDX'
+test_midx_bitmap_cases () {
+	writeLookupTable=false
+	writeBitmapLookupTable=
+
+	for i in "$@"
+	do
+		case $i in
+		"pack.writeBitmapLookupTable")
+			writeLookupTable=true
+			writeBitmapLookupTable="$i"
+			;;
+		esac
+	done
+
+	test_expect_success 'setup test_repository' '
+		rm -rf * .git &&
+		git init &&
+		git config pack.writeBitmapLookupTable '"$writeLookupTable"'
+	'
 
-test_expect_success 'missing object closure fails gracefully' '
-	rm -fr repo &&
-	git init repo &&
-	test_when_finished "rm -fr repo" &&
-	(
-		cd repo &&
+	midx_bitmap_core
 
-		test_commit loose &&
-		test_commit packed &&
+	bitmap_reuse_tests 'pack' 'MIDX' "$writeBitmapLookupTable"
+	bitmap_reuse_tests 'MIDX' 'pack' "$writeBitmapLookupTable"
+	bitmap_reuse_tests 'MIDX' 'MIDX' "$writeBitmapLookupTable"
 
-		# Do not pass "--revs"; we want a pack without the "loose"
-		# commit.
-		git pack-objects $objdir/pack/pack <<-EOF &&
-		$(git rev-parse packed)
-		EOF
+	test_expect_success 'missing object closure fails gracefully' '
+		rm -fr repo &&
+		git init repo &&
+		test_when_finished "rm -fr repo" &&
+		(
+			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
 
-		test_must_fail git multi-pack-index write --bitmap 2>err &&
-		grep "doesn.t have full closure" err &&
-		test_path_is_missing $midx
-	)
-'
+			test_commit loose &&
+			test_commit packed &&
 
-midx_bitmap_partial_tests
+			# Do not pass "--revs"; we want a pack without the "loose"
+			# commit.
+			git pack-objects $objdir/pack/pack <<-EOF &&
+			$(git rev-parse packed)
+			EOF
 
-test_expect_success 'removing a MIDX clears stale bitmaps' '
-	rm -fr repo &&
-	git init repo &&
-	test_when_finished "rm -fr repo" &&
-	(
-		cd repo &&
-		test_commit base &&
-		git repack &&
-		git multi-pack-index write --bitmap &&
+			test_must_fail git multi-pack-index write --bitmap 2>err &&
+			grep "doesn.t have full closure" err &&
+			test_path_is_missing $midx
+		)
+	'
 
-		# Write a MIDX and bitmap; remove the MIDX but leave the bitmap.
-		stale_bitmap=$midx-$(midx_checksum $objdir).bitmap &&
-		rm $midx &&
+	midx_bitmap_partial_tests
 
-		# Then write a new MIDX.
-		test_commit new &&
-		git repack &&
-		git multi-pack-index write --bitmap &&
+	test_expect_success 'removing a MIDX clears stale bitmaps' '
+		rm -fr repo &&
+		git init repo &&
+		test_when_finished "rm -fr repo" &&
+		(
+			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
+			test_commit base &&
+			git repack &&
+			git multi-pack-index write --bitmap &&
+
+			# Write a MIDX and bitmap; remove the MIDX but leave the bitmap.
+			stale_bitmap=$midx-$(midx_checksum $objdir).bitmap &&
+			rm $midx &&
+
+			# Then write a new MIDX.
+			test_commit new &&
+			git repack &&
+			git multi-pack-index write --bitmap &&
+
+			test_path_is_file $midx &&
+			test_path_is_file $midx-$(midx_checksum $objdir).bitmap &&
+			test_path_is_missing $stale_bitmap
+		)
+	'
 
-		test_path_is_file $midx &&
-		test_path_is_file $midx-$(midx_checksum $objdir).bitmap &&
-		test_path_is_missing $stale_bitmap
-	)
-'
+	test_expect_success 'pack.preferBitmapTips' '
+		git init repo &&
+		test_when_finished "rm -fr repo" &&
+		(
+			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
 
-test_expect_success 'pack.preferBitmapTips' '
-	git init repo &&
-	test_when_finished "rm -fr repo" &&
-	(
-		cd repo &&
+			test_commit_bulk --message="%s" 103 &&
 
-		test_commit_bulk --message="%s" 103 &&
+			git log --format="%H" >commits.raw &&
+			sort <commits.raw >commits &&
 
-		git log --format="%H" >commits.raw &&
-		sort <commits.raw >commits &&
+			git log --format="create refs/tags/%s %H" HEAD >refs &&
+			git update-ref --stdin <refs &&
 
-		git log --format="create refs/tags/%s %H" HEAD >refs &&
-		git update-ref --stdin <refs &&
+			git multi-pack-index write --bitmap &&
+			test_path_is_file $midx &&
+			test_path_is_file $midx-$(midx_checksum $objdir).bitmap &&
 
-		git multi-pack-index write --bitmap &&
-		test_path_is_file $midx &&
-		test_path_is_file $midx-$(midx_checksum $objdir).bitmap &&
+			test-tool bitmap list-commits | sort >bitmaps &&
+			comm -13 bitmaps commits >before &&
+			test_line_count = 1 before &&
 
-		test-tool bitmap list-commits | sort >bitmaps &&
-		comm -13 bitmaps commits >before &&
-		test_line_count = 1 before &&
+			perl -ne "printf(\"create refs/tags/include/%d \", $.); print" \
+				<before | git update-ref --stdin &&
 
-		perl -ne "printf(\"create refs/tags/include/%d \", $.); print" \
-			<before | git update-ref --stdin &&
+			rm -fr $midx-$(midx_checksum $objdir).bitmap &&
+			rm -fr $midx &&
 
-		rm -fr $midx-$(midx_checksum $objdir).bitmap &&
-		rm -fr $midx &&
+			git -c pack.preferBitmapTips=refs/tags/include \
+				multi-pack-index write --bitmap &&
+			test-tool bitmap list-commits | sort >bitmaps &&
+			comm -13 bitmaps commits >after &&
 
-		git -c pack.preferBitmapTips=refs/tags/include \
-			multi-pack-index write --bitmap &&
-		test-tool bitmap list-commits | sort >bitmaps &&
-		comm -13 bitmaps commits >after &&
+			! test_cmp before after
+		)
+	'
 
-		! test_cmp before after
-	)
-'
+	test_expect_success 'writing a bitmap with --refs-snapshot' '
+		git init repo &&
+		test_when_finished "rm -fr repo" &&
+		(
+			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
 
-test_expect_success 'writing a bitmap with --refs-snapshot' '
-	git init repo &&
-	test_when_finished "rm -fr repo" &&
-	(
-		cd repo &&
+			test_commit one &&
+			test_commit two &&
 
-		test_commit one &&
-		test_commit two &&
+			git rev-parse one >snapshot &&
 
-		git rev-parse one >snapshot &&
+			git repack -ad &&
 
-		git repack -ad &&
+			# First, write a MIDX which see both refs/tags/one and
+			# refs/tags/two (causing both of those commits to receive
+			# bitmaps).
+			git multi-pack-index write --bitmap &&
 
-		# First, write a MIDX which see both refs/tags/one and
-		# refs/tags/two (causing both of those commits to receive
-		# bitmaps).
-		git multi-pack-index write --bitmap &&
+			test_path_is_file $midx &&
+			test_path_is_file $midx-$(midx_checksum $objdir).bitmap &&
 
-		test_path_is_file $midx &&
-		test_path_is_file $midx-$(midx_checksum $objdir).bitmap &&
+			test-tool bitmap list-commits | sort >bitmaps &&
+			grep "$(git rev-parse one)" bitmaps &&
+			grep "$(git rev-parse two)" bitmaps &&
 
-		test-tool bitmap list-commits | sort >bitmaps &&
-		grep "$(git rev-parse one)" bitmaps &&
-		grep "$(git rev-parse two)" bitmaps &&
+			rm -fr $midx-$(midx_checksum $objdir).bitmap &&
+			rm -fr $midx &&
 
-		rm -fr $midx-$(midx_checksum $objdir).bitmap &&
-		rm -fr $midx &&
+			# Then again, but with a refs snapshot which only sees
+			# refs/tags/one.
+			git multi-pack-index write --bitmap --refs-snapshot=snapshot &&
 
-		# Then again, but with a refs snapshot which only sees
-		# refs/tags/one.
-		git multi-pack-index write --bitmap --refs-snapshot=snapshot &&
+			test_path_is_file $midx &&
+			test_path_is_file $midx-$(midx_checksum $objdir).bitmap &&
 
-		test_path_is_file $midx &&
-		test_path_is_file $midx-$(midx_checksum $objdir).bitmap &&
+			test-tool bitmap list-commits | sort >bitmaps &&
+			grep "$(git rev-parse one)" bitmaps &&
+			! grep "$(git rev-parse two)" bitmaps
+		)
+	'
 
-		test-tool bitmap list-commits | sort >bitmaps &&
-		grep "$(git rev-parse one)" bitmaps &&
-		! grep "$(git rev-parse two)" bitmaps
-	)
-'
+	test_expect_success 'write a bitmap with --refs-snapshot (preferred tips)' '
+		git init repo &&
+		test_when_finished "rm -fr repo" &&
+		(
+			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
 
-test_expect_success 'write a bitmap with --refs-snapshot (preferred tips)' '
-	git init repo &&
-	test_when_finished "rm -fr repo" &&
-	(
-		cd repo &&
+			test_commit_bulk --message="%s" 103 &&
 
-		test_commit_bulk --message="%s" 103 &&
+			git log --format="%H" >commits.raw &&
+			sort <commits.raw >commits &&
 
-		git log --format="%H" >commits.raw &&
-		sort <commits.raw >commits &&
+			git log --format="create refs/tags/%s %H" HEAD >refs &&
+			git update-ref --stdin <refs &&
 
-		git log --format="create refs/tags/%s %H" HEAD >refs &&
-		git update-ref --stdin <refs &&
+			git multi-pack-index write --bitmap &&
+			test_path_is_file $midx &&
+			test_path_is_file $midx-$(midx_checksum $objdir).bitmap &&
 
-		git multi-pack-index write --bitmap &&
-		test_path_is_file $midx &&
-		test_path_is_file $midx-$(midx_checksum $objdir).bitmap &&
+			test-tool bitmap list-commits | sort >bitmaps &&
+			comm -13 bitmaps commits >before &&
+			test_line_count = 1 before &&
 
-		test-tool bitmap list-commits | sort >bitmaps &&
-		comm -13 bitmaps commits >before &&
-		test_line_count = 1 before &&
+			(
+				grep -vf before commits.raw &&
+				# mark missing commits as preferred
+				sed "s/^/+/" before
+			) >snapshot &&
 
+			rm -fr $midx-$(midx_checksum $objdir).bitmap &&
+			rm -fr $midx &&
+
+			git multi-pack-index write --bitmap --refs-snapshot=snapshot &&
+			test-tool bitmap list-commits | sort >bitmaps &&
+			comm -13 bitmaps commits >after &&
+
+			! test_cmp before after
+		)
+	'
+
+	test_expect_success 'hash-cache values are propagated from pack bitmaps' '
+		rm -fr repo &&
+		git init repo &&
+		test_when_finished "rm -fr repo" &&
 		(
-			grep -vf before commits.raw &&
-			# mark missing commits as preferred
-			sed "s/^/+/" before
-		) >snapshot &&
+			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
 
-		rm -fr $midx-$(midx_checksum $objdir).bitmap &&
-		rm -fr $midx &&
+			test_commit base &&
+			test_commit base2 &&
+			git repack -adb &&
 
-		git multi-pack-index write --bitmap --refs-snapshot=snapshot &&
-		test-tool bitmap list-commits | sort >bitmaps &&
-		comm -13 bitmaps commits >after &&
+			test-tool bitmap dump-hashes >pack.raw &&
+			test_file_not_empty pack.raw &&
+			sort pack.raw >pack.hashes &&
 
-		! test_cmp before after
-	)
-'
+			test_commit new &&
+			git repack &&
+			git multi-pack-index write --bitmap &&
 
-test_expect_success 'hash-cache values are propagated from pack bitmaps' '
-	rm -fr repo &&
-	git init repo &&
-	test_when_finished "rm -fr repo" &&
-	(
-		cd repo &&
+			test-tool bitmap dump-hashes >midx.raw &&
+			sort midx.raw >midx.hashes &&
 
-		test_commit base &&
-		test_commit base2 &&
-		git repack -adb &&
+			# ensure that every namehash in the pack bitmap can be found in
+			# the midx bitmap (i.e., that there are no oid-namehash pairs
+			# unique to the pack bitmap).
+			comm -23 pack.hashes midx.hashes >dropped.hashes &&
+			test_must_be_empty dropped.hashes
+		)
+	'
 
-		test-tool bitmap dump-hashes >pack.raw &&
-		test_file_not_empty pack.raw &&
-		sort pack.raw >pack.hashes &&
+	test_expect_success 'no .bitmap is written without any objects' '
+		rm -fr repo &&
+		git init repo &&
+		test_when_finished "rm -fr repo" &&
+		(
+			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
 
-		test_commit new &&
-		git repack &&
-		git multi-pack-index write --bitmap &&
+			empty="$(git pack-objects $objdir/pack/pack </dev/null)" &&
+			cat >packs <<-EOF &&
+			pack-$empty.idx
+			EOF
 
-		test-tool bitmap dump-hashes >midx.raw &&
-		sort midx.raw >midx.hashes &&
+			git multi-pack-index write --bitmap --stdin-packs \
+				<packs 2>err &&
 
-		# ensure that every namehash in the pack bitmap can be found in
-		# the midx bitmap (i.e., that there are no oid-namehash pairs
-		# unique to the pack bitmap).
-		comm -23 pack.hashes midx.hashes >dropped.hashes &&
-		test_must_be_empty dropped.hashes
-	)
-'
+			grep "bitmap without any objects" err &&
 
-test_expect_success 'no .bitmap is written without any objects' '
-	rm -fr repo &&
-	git init repo &&
-	test_when_finished "rm -fr repo" &&
-	(
-		cd repo &&
+			test_path_is_file $midx &&
+			test_path_is_missing $midx-$(midx_checksum $objdir).bitmap
+		)
+	'
+
+	test_expect_success 'graceful fallback when missing reverse index' '
+		rm -fr repo &&
+		git init repo &&
+		test_when_finished "rm -fr repo" &&
+		(
+			cd repo &&
+			git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
 
-		empty="$(git pack-objects $objdir/pack/pack </dev/null)" &&
-		cat >packs <<-EOF &&
-		pack-$empty.idx
-		EOF
+			test_commit base &&
 
-		git multi-pack-index write --bitmap --stdin-packs \
-			<packs 2>err &&
+			# write a pack and MIDX bitmap containing base
+			git repack -adb &&
+			git multi-pack-index write --bitmap &&
 
-		grep "bitmap without any objects" err &&
+			GIT_TEST_MIDX_READ_RIDX=0 \
+				git rev-list --use-bitmap-index HEAD 2>err &&
+			! grep "ignoring extra bitmap file" err
+		)
+	'
+}
 
-		test_path_is_file $midx &&
-		test_path_is_missing $midx-$(midx_checksum $objdir).bitmap
-	)
-'
+test_midx_bitmap_cases
+
+test_midx_bitmap_cases "pack.writeBitmapLookupTable"
 
-test_expect_success 'graceful fallback when missing reverse index' '
+test_expect_success 'multi-pack-index write writes lookup table if enabled' '
 	rm -fr repo &&
 	git init repo &&
 	test_when_finished "rm -fr repo" &&
 	(
 		cd repo &&
-
 		test_commit base &&
-
-		# write a pack and MIDX bitmap containing base
-		git repack -adb &&
-		git multi-pack-index write --bitmap &&
-
-		GIT_TEST_MIDX_READ_RIDX=0 \
-			git rev-list --use-bitmap-index HEAD 2>err &&
-		! grep "ignoring extra bitmap file" err
+		git config pack.writeBitmapLookupTable true &&
+		git repack -ad &&
+		GIT_TRACE2_EVENT="$(pwd)/trace" \
+			git multi-pack-index write --bitmap &&
+		grep "\"label\":\"writing_lookup_table\"" trace
 	)
 '
 

t/t5327-multi-pack-bitmaps-rev.sh +22 -3

index d30ba632c87..5ed16a820d1 100755
@@ -17,7 +17,27 @@ GIT_TEST_MIDX_READ_RIDX=0
 export GIT_TEST_MIDX_WRITE_REV
 export GIT_TEST_MIDX_READ_RIDX
 
-midx_bitmap_core rev
-midx_bitmap_partial_tests rev
+test_midx_bitmap_rev () {
+     writeLookupTable=false
+
+ 	for i in "$@"
+ 	do
+ 		case $i in
+ 		"pack.writeBitmapLookupTable") writeLookupTable=true;;
+ 		esac
+ 	done
+
+     test_expect_success 'setup bitmap config' '
+         rm -rf * .git &&
+         git init &&
+         git config pack.writeBitmapLookupTable '"$writeLookupTable"'
+     '
+
+     midx_bitmap_core rev
+     midx_bitmap_partial_tests rev
+ }
+
+ test_midx_bitmap_rev
+ test_midx_bitmap_rev "pack.writeBitmapLookupTable"
 
 test_done
--

gitgitgadget

That's quite a large a change, and unfortunately I pinpointed a flake to this patch when running with GIT_TEST_DEFAULT_HASH=sha256. The symptom is this:

-- snip --
[...]
+ diff -u expect.normalized actual.normalized
+ rm -f expect.normalized actual.normalized
ok 317 - enumerate --objects (full bitmap, other)

expecting success of 5326.318 'bitmap --objects handles non-commit objects (full bitmap, other)':
git rev-list --objects --use-bitmap-index $branch tagged-blob >actual && grep $blob actual

+ git rev-list --objects --use-bitmap-index other tagged-blob
+ grep bff4ed5e839bd73e821f78b45a7fa34208aa85596535ec8e9ac5eab477ca6f81 actual bff4ed5e839bd73e821f78b45a7fa34208aa85596535ec8e9ac5eab477ca6f81 ok 318 - bitmap --objects handles non-commit objects (full bitmap, other)

expecting success of 5326.319 'clone from bitmapped repository':

                rm -fr clone.git &&
                git clone --no-local --bare . clone.git &&
                git rev-parse HEAD >expect &&
                git --git-dir=clone.git rev-parse HEAD >actual &&
                test_cmp expect actual

+ rm -fr clone.git
+ git clone --no-local --bare . clone.git
Cloning into bare repository 'clone.git'...
remote: Enumerating objects: 756, done.
remote: Counting objects: 100% (754/754), done.
remote: Compressing objects: 100% (281/281), done.
remote: Total 756 (delta 245), reused 740 (delta 234), pack-reused 2
Receiving objects: 100% (756/756), 77.50 KiB | 8.61 MiB/s, done.
fatal: REF_DELTA at offset 221 already resolved (duplicate base 4d332072f161629ffe4652ecd3ce377ef88447bec73f05ab0f3515f98bd061cf?)
fatal: fetch-pack: invalid index-pack output
error: last command exited with $?=128
not ok 319 - clone from bitmapped repository
#

#                       rm -fr clone.git &&
#                       git clone --no-local --bare . clone.git &&
#                       git rev-parse HEAD >expect &&
#                       git --git-dir=clone.git rev-parse HEAD >actual &&
#                       test_cmp expect actual

#
1..319
-- snap --

On a hunch, I ran this through valgrind (took a while) but it did not point out the problem.

Again, this is only with SHA-256 (and somewhat flaky), it passes every time with SHA-1. Maybe you can reproduce on your side with that information?

Quoted 3 lines · Johannes Schindelin

That's quite a large a change, and unfortunately I pinpointed a flake to this patch when running with GIT_TEST_DEFAULT_HASH=sha256. The symptom is this:

Hi Dscho, sorry for this long delay in response. I was quite busy for 3-4 days in hostel room shifting. So, I couldn't work properly during this time.

Quoted 44 lines

-- snip --
[...]
+ diff -u expect.normalized actual.normalized
+ rm -f expect.normalized actual.normalized
ok 317 - enumerate --objects (full bitmap, other)

expecting success of 5326.318 'bitmap --objects handles non-commit objects (full bitmap, other)':
git rev-list --objects --use-bitmap-index $branch tagged-blob >actual && grep $blob actual

+ git rev-list --objects --use-bitmap-index other tagged-blob
+ grep bff4ed5e839bd73e821f78b45a7fa34208aa85596535ec8e9ac5eab477ca6f81 actual bff4ed5e839bd73e821f78b45a7fa34208aa85596535ec8e9ac5eab477ca6f81 ok 318 - bitmap --objects handles non-commit objects (full bitmap, other)

expecting success of 5326.319 'clone from bitmapped repository':

                rm -fr clone.git &&
                git clone --no-local --bare . clone.git &&
                git rev-parse HEAD >expect &&
                git --git-dir=clone.git rev-parse HEAD >actual &&
                test_cmp expect actual

+ rm -fr clone.git
+ git clone --no-local --bare . clone.git
Cloning into bare repository 'clone.git'...
remote: Enumerating objects: 756, done.
remote: Counting objects: 100% (754/754), done.
remote: Compressing objects: 100% (281/281), done.
remote: Total 756 (delta 245), reused 740 (delta 234), pack-reused 2
Receiving objects: 100% (756/756), 77.50 KiB | 8.61 MiB/s, done.
fatal: REF_DELTA at offset 221 already resolved (duplicate base 4d332072f161629ffe4652ecd3ce377ef88447bec73f05ab0f3515f98bd061cf?)
fatal: fetch-pack: invalid index-pack output
error: last command exited with $?=128
not ok 319 - clone from bitmapped repository
#

#                       rm -fr clone.git &&
#                       git clone --no-local --bare . clone.git &&
#                       git rev-parse HEAD >expect &&
#                       git --git-dir=clone.git rev-parse HEAD >actual &&
#                       test_cmp expect actual

#
1..319
-- snap --

Quoted 6 lines

On a hunch, I ran this through valgrind (took a while) but it did not point out the problem.

Again, this is only with SHA-256 (and somewhat flaky), it passes every time with SHA-1. Maybe you can reproduce on your side with that information?

Yeah, I can reproduce it on my side.

But I am sure it is not related to the lookup table implementation code. Because when I swap the order of calling test_midx_bitmap_cases "pack.writeBitmapLookupTable" and test_midx_bitmap_cases (in t5326-multi-pack-bitmaps.sh), in that case, the error is being generated in test_midx_bitmap_cases call. Generally speaking, the error is always being generated in the second call.

For now, my understanding says that there is something fishy in the test script.

I am still not able to figure out the problem here. But let me further investigate.

If anyone has some idea about what could be the culprit, I will be very happy to know.

Quoted 6 lines

But I am sure it is not related to the lookup table implementation code. Because when I swap the order of calling test_midx_bitmap_cases "pack.writeBitmapLookupTable" and test_midx_bitmap_cases (in t5326-multi-pack-bitmaps.sh), in that case, the error is being generated in test_midx_bitmap_cases call. Generally speaking, the error is always being generated in the second call.

Indeed, it probably has something to do with the test tick (which gives rise to the author/committer date of the commits that are generated, and hence with the SHA order of said commits).

With this patch:

-- snip --

t/t5326-multi-pack-bitmaps.sh +5 -2

index 3b206adcee6..a340f005b89 100755
@@ -347,7 +347,11 @@ test_midx_bitmap_cases () {
        '
 }
 
-test_midx_bitmap_cases
+# test_midx_bitmap_cases
+
+GIT_COMMITTER_DATE='1112928553 -0700'
+GIT_AUTHOR_DATE='1112928553 -0700'
+test_tick='1112928553'
 
 test_midx_bitmap_cases "pack.writeBitmapLookupTable"
 
-- snap --

I can reproduce it quicker via

        GIT_TEST_DEFAULT_HASH=sha256 sh t5326-*.sh --run=1,71,91,92,93,124,145

Without setting those variables, I cannot skip the first test_midx_bitmap_cases invocation _and_ reproduce the failure.

Quoted 5 lines

I am still not able to figure out the problem here. But let me further investigate.

If anyone has some idea about what could be the culprit, I will be very happy to know.

So I noticed that the test will pass every 4th to 5th time over here, which means that it is a racy condition that is the culprit.

I dug a bit deeper and reduced the reproducer even further, by running this command with a trash directory just after above test script invocation failed:

        bin-wrappers/git -C t/trash\ directory.t5326-multi-pack-bitmaps/ \
                -c pack.threads=1 pack-objects --revs --thin --stdout \
                --progress --delta-base-offset </tmp/a5 |
        bin-wrappers/git -C t/trash\ directory.t5326-multi-pack-bitmaps/ \
                -c pack.threads=1 index-pack --stdin -v --fix-thin \
                '--keep=fetch-pack 12345 on labtop' \
                --check-self-contained-and-connected

where /tmp/a5 contains these lines:

-- snip -- 0ae5a358dcea86d81c0903aaec1e21857688cdb36c7fd89b04bd293fb2cceaa6 67df8a01ac84cf5f028855c48384eac3336bb02a52603bac285c4b31d66b3ab5 098a57f7753320c8a37cf0cb84526a9e50439d9f70fb673c91436a5283a7efe8 --not
-- snap --

This allowed me to instrument the code with _many_ debug printf statements (I actually use error("%s:d: ...", __FILE__, __LINE__, ...) calls) to dive deeper into the weeds.

One relatively obvious difference I can see is that when the code reaches builtin/pack-objects.c:1198, in the passing case after writing the reused pack we're at offset 900 in the written pack file, but in the failing case we're at offset 269.

Another difference I first saw was that the mtime of
.git/objects/pack/multi-pack-index was identical to the mtime of .git/objects/pack/multi-pack-index-2ec3c30357d2fff78db9b36cc749b393087e989bffdd278771d6f62089406061.bitmap in the failing case, while the mtimes of the corresponding files were
different in the passing case.

But in another failing run, the mtimes were also non-identical. Meaning:
the race cannot be caused by identical or non-identical timestamps there.

One consistent difference, however, was the SHA-256 in that .bitmap file
name: In the failing case it was always 2ec3c30357d2fff78db9b36cc749b393087e989bffdd278771d6f62089406061, while in the succeeding case it was always 0c275657a915eeff1f2a1c17e5ded43cc3b232b0e178923e44fc15c1970516fb.

My suspicion is that this .bitmap file is written out in an earlier test case, and is already incorrect at that stage. Maybe it should have been updated, but isn't, and the result is an incorrectly-reused partial pack file.

I also noticed that deleting the multi-pack-index-*.bitmap file in the failing case will "fix" the pack-objects | index-pack command I showed above.

Hopefully this will help you dig in further because even if the bug is not in your code, it needs to be fixed. And I suspect that it is a bug in the code we already have in the main branch, so that fix is really, really needed, now.

Since you are very familiar with the details of bitmaps now, I would like to encourage you to work on some kind of validator/inspector, e.g. something along the lines of a test-tool midx-bitmap dump (and later ... verify) that would help future you (and future me) investigate similar breakages. Ideally, that tool will not only parse the .bitmap file but immediately print out everything in a human-readable form.

The reason I suggest this: I got a bit tired of staring at the output of hexdump -C and comparing it to the documentation in
https://git-scm.com/docs/pack-format, so I had to stop after looking too long at one broken pack file (i.e. the output of the pack-objects command I showed above, where already the first entry seems to have an infinite delta chain that pretends that 4d332072f161629ffe4652ecd3ce377ef88447bec73f05ab0f3515f98bd061cf has itself as delta base) before I even could analyze the MIDX bitmap files.

The proposed tool would make analyzing MIDX bitmaps substantially more fun, and would also help stave off future breakages if it was taught some verify mode that would essentially automate what right now has to be done manually: to verify that the MIDX bitmap file contents are sound and consistent with the contents of the pack files.

Obviously, this verify command should be called in strategic places of t5326.

Quoted 7 lines · Johannes Schindelin

Since you are very familiar with the details of bitmaps now, I would like to encourage you to work on some kind of validator/inspector, e.g. something along the lines of a test-tool midx-bitmap dump (and later ... verify) that would help future you (and future me) investigate similar breakages. Ideally, that tool will not only parse the .bitmap file but immediately print out everything in a human-readable form.

Hi Abhradeep,

Quoted 10 lines · Abhradeep Chakraborty

Quoted 7 lines · Johannes Schindelin

Since you are very familiar with the details of bitmaps now, I would like to encourage you to work on some kind of validator/inspector, e.g. something along the lines of a test-tool midx-bitmap dump (and later ... verify) that would help future you (and future me) investigate similar breakages. Ideally, that tool will not only parse the .bitmap file but immediately print out everything in a human-readable form.

Have you made progress on this? I am interested mostly because I am trying very hard to maintain passing CI runs of Git for Windows' shears/seen branch (which essentially tries to rebase all of Git for Windows' patches on top of seen), and this failure is consistently causing said CI runs to fail for a while already.

Ciao,
Dscho

Quoted 14 lines · Johannes Schindelin

Quoted 10 lines · Abhradeep Chakraborty

Quoted 7 lines · Johannes Schindelin

Since you are very familiar with the details of bitmaps now, I would like to encourage you to work on some kind of validator/inspector, e.g. something along the lines of a test-tool midx-bitmap dump (and later ... verify) that would help future you (and future me) investigate similar breakages. Ideally, that tool will not only parse the .bitmap file but immediately print out everything in a human-readable form.

Quoted 5 lines

Have you made progress on this? I am interested mostly because I am trying very hard to maintain passing CI runs of Git for Windows' shears/seen branch (which essentially tries to rebase all of Git for Windows' patches on top of seen), and this failure is consistently causing said CI runs to fail for a while already.

Hey Dscho, I am trying hard to solve the issue but unfortunately I haven't found the key yet.

I investigated the bitmap code-base and used debug lines but didn't find a way to fix it.

Hi Abhradeep,

Quoted 22 lines · Abhradeep Chakraborty

Quoted 19 lines · Johannes Schindelin

Quoted 10 lines · Abhradeep Chakraborty

Quoted 7 lines · Johannes Schindelin

Since you are very familiar with the details of bitmaps now, I would like to encourage you to work on some kind of validator/inspector, e.g. something along the lines of a test-tool midx-bitmap dump (and later ... verify) that would help future you (and future me) investigate similar breakages. Ideally, that tool will not only parse the .bitmap file but immediately print out everything in a human-readable form.

Have you made progress on this? I am interested mostly because I am trying very hard to maintain passing CI runs of Git for Windows' shears/seen branch (which essentially tries to rebase all of Git for Windows' patches on top of seen), and this failure is consistently causing said CI runs to fail for a while already.

Quoted 2 lines

Hey Dscho, I am trying hard to solve the issue but unfortunately I haven't found the key yet.

The tool I proposed could potentially help, in particular with distributing the burden of the investigation on more shoulders than just yours.

Quoted 2 lines

I investigated the bitmap code-base and used debug lines but didn't find a way to fix it.

Have you investigated whether the .bitmap file was produced for the latest set of pack files? It should be relatively quick to investigate that, and if it turns out not to be the case, the fix should be quick, too.

I also checked whether the packing_data->in_pack_by_idx contained all the packs. For this I wrote a debug error message in prepare_in_pack_by_idx()[1] function and found that packing_data is using the latest packs.

I noticed in the 'setup partial bitmaps' test case that if we comment
out the line git repack && , it runs successfully.

    test_expect_success 'setup partial bitmaps' '
        test_commit packed &&
        # git repack &&
        test_commit loose &&
        git multi-pack-index write --bitmap 2>err &&
        ...
    '

Quoted 10 lines · Abhradeep Chakraborty

I noticed in the 'setup partial bitmaps' test case that if we comment
out the line git repack && , it runs successfully.

    test_expect_success 'setup partial bitmaps' '
        test_commit packed &&
        # git repack &&
        test_commit loose &&
        git multi-pack-index write --bitmap 2>err &&
        ...
    '

That's interesting. Are the .bitmap and .midx files updated as part of that repack?

Hi Abhradeep,
I instrumented this, and saw that the multi-pack-index and multi-pack-index*.bitmap files were unchanged by the git repack invocation.

Re-generating the MIDX bitmap forcefully after the repack seems to fix things over here:

-- snip --

t/lib-bitmap.sh +3 -1

index a95537e759b..564124bda27 100644
@@ -438,7 +438,10 @@ midx_bitmap_partial_tests () {
 
        test_expect_success 'setup partial bitmaps' '
                test_commit packed &&
+ls -l .git/objects/pack/ &&
                git repack &&
+git multi-pack-index write --bitmap &&
+ls -l .git/objects/pack/ &&
                test_commit loose &&
                git multi-pack-index write --bitmap 2>err &&
                test_path_is_file $midx &&
-- snap --

This suggests to me that the multi-pack-index write --bitmap 2>err call in this hunk might reuse a stale MIDX bitmap, and that _that_ might be the root cause of this breakage.

Quoted 5 lines · Johannes Schindelin

Hi Abhradeep,
I instrumented this, and saw that the multi-pack-index and multi-pack-index*.bitmap files were unchanged by the git repack invocation.

Yeah, those two files remain unchanged here.

Quoted 21 lines

Re-generating the MIDX bitmap forcefully after the repack seems to fix things over here:

-- snip --

t/lib-bitmap.sh +3 -1

index a95537e759b..564124bda27 100644
@@ -438,7 +438,10 @@ midx_bitmap_partial_tests () {
 
        test_expect_success 'setup partial bitmaps' '
                test_commit packed &&
+ls -l .git/objects/pack/ &&
                git repack &&
+git multi-pack-index write --bitmap &&
+ls -l .git/objects/pack/ &&
                test_commit loose &&
                git multi-pack-index write --bitmap 2>err &&
                test_path_is_file $midx &&
-- snap --

Quoted 3 lines

This suggests to me that the multi-pack-index write --bitmap 2>err call in this hunk might reuse a stale MIDX bitmap, and that _that_ might be the root cause of this breakage.

Yeah, the multi-pack-index write --bitmap 2>err is creating the problem. More specifically the multi-pack-index write part. As you can see in my previous comment (if you get the comment), I shared a screenshot there which pointed out that the multi-pack-index files in both cases are different. The portion from which it started to differ belongs to the RIDX chunk.

So, I used some debug lines in midx_pack_order() function[1] and found that the objects are sorted differently in those cases (i.e. passing case and failing case). For passing case, the RIDX chunk contents are like below -

pack_order = [ 1, 36, 11, 6, 18, 3, 19, 12, 5, 31, 27, 23, 29, 8, 38, 22, 9, 15, 14, 24, 37, 28, 7, 39, 10, 34, 26, 4, 30, 33, 2, 35, 17, 32, 0, 21, 16, 25, 13, 40, 20,]

And in the failing case, this is -

pack_order = [ 12, 18, 3, 19, 1, 36, 11, 6, 5, 31, 27, 23, 29, 8, 38, 22, 9, 15, 14, 24, 37, 28, 7, 39, 10, 34, 26, 4, 30, 33, 2, 35, 17, 32, 0, 21, 16, 25, 13, 40, 20,]

I went further and realized that this is due to the line[2] -

    if (!e->preferred)
        data[i].pack |= (1U << 31);

I.e. 4- 5 pack_midx_entry objects have different preferred values in those cases. For example, "46193a971f5045cb3ca6022957541f9ccddfbfe78591d8506e2d952f8113059b" (with pack order 12) is preferred in failing case (that's why it is in the first position) and the same is not preferred in the passing case.

It may be because of reusing a stale midx bitmap (as you said). But I am not sure. Just to ensure myself, I compared all the other packfiles, idx files and a pack .bitmap file (which you can see using ls command) of failing and passing cases and found that they are the same.

I think I have found the problem. Derrick was right that mtime part is not the culprit. I tried to understand the whole midx workflow and some questions were raised in my mind. I don't know whether those are features or bugs (because I do not have much experience in multi-pack-index code).

I am writing a brief description for the context of the issue and the questions I have.

Let us start from the write_midx_internal() function. As packs_to_include is null in our case, We can use the old midx to write a new midx file. The line ctx.m = lookup_multi_pack_index(the_repository, object_dir)[1] does this. It also loads packs that do not belong to any multi-pack-indexes. It also sets the_repository->objects->packed_git_intialized to 1. If we look at our test case (setup partial bitmap) the last .pack file (generated by git repack && ) does not belong to any midx. So, that pack will be loaded in this step.

[1] https://github.com/git/git/blob/5502f77b6944eda8e26813d8f542cffe7d110aea/midx.c#L1169

Next let us move to the if (ctx.m)[2] block. As we will be writing a bitmap, if (flags & MIDX_WRITE_REV_INDEX) is true. Thus all packs related to the old midx are loaded and ctx.info[ctx.nr].p stores the pointers of these packs.

[2] https://github.com/git/git/blob/5502f77b6944eda8e26813d8f542cffe7d110aea/midx.c#L1182

After that we come to the for_each_file_in_pack_dir(object_dir, add_pack_to_midx, &ctx); line[3] . The add_pack_to_midx[4] function adds packs (that are not in the old midx) to ctx.info. Now I have a question here - Why are we using the add_packed_git()[5] function provided we already loaded those packs in the lookup_multi_pack_index step (i.e. 1st step)? These packs are not added in r->objects->packed_git. This question is related to our current issue.

I.e. instead of this -

   ctx->info[ctx->nr].p = add_packed_git(full_path,

full_path_len, 0);

Why not this (or similar) -

    for (cp = the_repository->objects->packed_git; cp; cp = cp->next)
        if (!cmp_idx_or_pack_name(cp->pack_name, full_path))
            ctx->info[ctx->nr].p = cp;

[3] https://github.com/git/git/blob/5502f77b6944eda8e26813d8f542cffe7d110aea/midx.c#L1221
[4] https://github.com/git/git/blob/5502f77b6944eda8e26813d8f542cffe7d110aea/midx.c#L462
[5] https://github.com/git/git/blob/5502f77b6944eda8e26813d8f542cffe7d110aea/midx.c#L492

write_midx_bitmap() function is where bitmap related code starts.
let us directly jump into the prepare_packed_git() function (called by get_all_packs()[6]). As I said previously, r->objects->packed_git_initialized is already enabled so this function becomes a no-op function. Which means it does not load the newly written midx (by calling prepare_multi_pack_index_one function) and uses old midx to write the bitmap (though we still have new packs and they can be used with the old midx to generate the bitmap, maybe?) . Here comes my second question - Is this the desired case? or should we use the new midx to write the bitmaps?

One important point to note is that get_all_packs() returns r->objects->packed_git which now stores pointers of all the packs and only these packfiles have their ->index set.

[6] https://github.com/git/git/blob/5502f77b6944eda8e26813d8f542cffe7d110aea/packfile.c#L1043

Now let us move to the last function - oe_set_in_pack() (called by prepare_midx_packing_data()). Note that, we are passing ctx->info[ctx->pack_perm[from->pack_int_id]].p along with other parameters. As I have said in an earlier para (containing my first question), ctx->info has some packs (i.e. newer packs that are not related to the old midx) that are not installed in r->objects->packed_git . In other words, we have two instances of the same pack file - one in r->objects->packed_git list and another in ctx->info[id].p. As prepare_in_pack_by_idx function only sets ->index for r->objects->packed_git packs, these packs (i.e. ctx.info[id].p) do not have their p->index set and thus end up calling the oe_map_new_pack function.

So really, the problem is that we are handling the r->objects->packed_git list instead of an array of packs that are under the control of the new midx. This assumption is baked deep in the pack-objects flow, so it would be hard to separate this idea.

Perhaps doing the reprepare_packed_git() to regenerate the list would be sufficient as a band-aid for now, but we would want to later do the big dig of focusing the pack_data struct to a specific list of pack-files (by default the set from get_all_packs(), but for midx bitmaps we can supply a specific set of packs).

One thing that really worries me is what if the failure is not related to calling `oe_map_new_pack()? I did all my work assuming that this function is the culprit. But I don't know if it is.

Hi Abhradeep,

When I took a close look at the process to generate MIDX bitmaps, I found a couple of interesting things. The first more trivial fix is that we incorrectly propagate the "preferred"-ness bit from packs in an existing MIDX when generating a new one. If the identity of the preferred pack changes, we should not drag forward those bits on objects already known (and preferred) by the existing MIDX:

--- >8 ---

midx.c +3 -0

index 3ff6e91e6e..40e520534c 100644
@@ -619,6 +619,9 @@ static struct pack_midx_entry *get_sorted_entries(struct multi_pack_index *m,
 
                if (m) {
                        uint32_t start = 0, end;
+                       int orig_preferred_pack = -1;
+                       if (0 <= preferred_pack && preferred_pack < m->num_packs)
+                               orig_preferred_pack = info[preferred_pack].orig_pack_int_id;
 
                        if (cur_fanout)
                                start = ntohl(m->chunk_oid_fanout[cur_fanout - 1]);

But a more interesting problem arose when I took a closer look at the psuedo-pack order of objects generated according to prepare_midx_packing_data(). With Johannes' fixed $test_tick value, I was able to see the following in runs that succeeded:

    27bb4ecd3e96cd0b3bc37d92a78cb5cbf34c418afa67f74cc52517ff7df418e1 (12 in pack-63c460f99a5c08f631396b1828c64006170a9d543b064506fd11b504a62acf52.idx)
    c68154d69c19f010afce786c6debe926ae6e7decfb946a4549085a792cf9de7e (202 in pack-63c460f99a5c08f631396b1828c64006170a9d543b064506fd11b504a62acf52.idx)
    a0b85b314ede46aa9f9b5796a284a4cf0b86ebb8fa32f87ae246e21b5378b11c (392 in pack-63c460f99a5c08f631396b1828c64006170a9d543b064506fd11b504a62acf52.idx)
    [...]

and the following in runs that failed:

    46193a971f5045cb3ca6022957541f9ccddfbfe78591d8506e2d952f8113059b (221 in pack-3fc052de674e3d48096af7cc5125675c0ae1082aa798eb9358de357b2655f9ad.idx)
    67df8a01ac84cf5f028855c48384eac3336bb02a52603bac285c4b31d66b3ab5 (12 in pack-2021cdedb33b542b244eacf3d009d1384471a53286b0c1235c91d124355dc818.idx)
    1556b5f0ad7cb0c25a1fc47355fcffc00775e90d94ae8c511e5776b204796ce6 (200 in pack-2021cdedb33b542b244eacf3d009d1384471a53286b0c1235c91d124355dc818.idx)

In the successful case, pack 63c460f99a... is preferred, and its objects appear in ascending order of their pack offsets. But in the other case, pack 3fc052de67... is preferred, but its first object starts at offset
221. Huh? That's not right:

    $ git show-index <.git/objects/pack/pack-3fc052de674e3d48096af7cc5125675c0ae1082aa798eb9358de357b2655f9ad.idx
    221 46193a971f5045cb3ca6022957541f9ccddfbfe78591d8506e2d952f8113059b (1f4bd28e)
    12 4d332072f161629ffe4652ecd3ce377ef88447bec73f05ab0f3515f98bd061cf (fadf885b)

Indeed, there is another object there at offset 12. Missing that object (since it comes from a preferred pack) is an invariant violation (since all objects from the preferred pack should be selected when multiple copies are available).

It's missing because the existing MIDX selects that object from a different pack, and when we get to fanout 0x4d (the one which should include that object), we skip over seeing its copy in the preferred pack because that pack already appears in the existing MIDX, though it wasn't preferred.

I think there are a couple of ways to fix this. The easiest thing to do would be to force the identity of the preferred pack to be the same when generating a MIDX bitmap *while reusing an existing MIDX*, since that is the only time this bug can happen.

But that's a little magical for my taste. I think a more reasonable fix would be to include copies of all objects from the preferred pack including in the case where that pack was non-preferred in an existing MIDX and at least one object in that pack was selected from a different pack in the existing MIDX.

Abhradeep -- let me know if this is something you want to look into. I think it's a very worthwhile bug to fix, since it is definitely trigger-able in the wild (notably, only with git multi-pack-index write --bitmap without --stdin-packs and only under certain circumstances), and not just limited to SHA-256 mode.

If you are busy experimenting with CRoaring, that's no problem and I can fix this up, too. Either way, it would be worth you and others weighing in on which fix you think is worth pursuing.

Hello Taylor, extremely thanks for finding the reason for this failure.

I am not able to understand this modification. info[preferred_pack].orig_pack_int_id and preferred_pack have the same value, right? I see ctx.info getting sorted only after calling get_sorted_entries() function.

Quoted 10 lines

I think there are a couple of ways to fix this. The easiest thing to do would be to force the identity of the preferred pack to be the same when generating a MIDX bitmap *while reusing an existing MIDX*, since that is the only time this bug can happen.

But that's a little magical for my taste. I think a more reasonable fix would be to include copies of all objects from the preferred pack including in the case where that pack was non-preferred in an existing MIDX and at least one object in that pack was selected from a different pack in the existing MIDX.

I think the later approach makes the most sense to me. It might not be a good idea to keep the same pack as preferred as a better candidate would be ignored in that case.

Quoted 9 lines

Abhradeep -- let me know if this is something you want to look into. I think it's a very worthwhile bug to fix, since it is definitely trigger-able in the wild (notably, only with git multi-pack-index write --bitmap without --stdin-packs and only under certain circumstances), and not just limited to SHA-256 mode.

If you are busy experimenting with CRoaring, that's no problem and I can fix this up, too. Either way, it would be worth you and others weighing in on which fix you think is worth pursuing.

I will be happy to fix it but I can't work on it right now (neither on CRoaring) because I am currently preparing for my exam. I can continue my work after that (i.e. from 19 aug). If you feel it is getting too late then you can do this too. I am also thinking of writing a patch for bitmap specific test dump tool (as Johannes proposed previously).

Quoted 10 lines

Quoted 9 lines

Abhradeep -- let me know if this is something you want to look into. I think it's a very worthwhile bug to fix, since it is definitely trigger-able in the wild (notably, only with git multi-pack-index write --bitmap without --stdin-packs and only under certain circumstances), and not just limited to SHA-256 mode.

If you are busy experimenting with CRoaring, that's no problem and I can fix this up, too. Either way, it would be worth you and others weighing in on which fix you think is worth pursuing.

Quoted 5 lines

I will be happy to fix it but I can't work on it right now (neither on CRoaring) because I am currently preparing for my exam. I can continue my work after that (i.e. from 19 aug). If you feel it is getting too late then you can do this too. I am also thinking of writing a patch for bitmap specific test dump tool (as Johannes proposed previously).

No problem. I wrote up some patches today myself that implement the above fix. I haven't polished them up yet, but they are available here:

https://github.com/ttaylorr/git/compare/master...ttaylorr:git:tb/bitmap-use-existing-preferred

I want to add a more direct reproduction that works in both SHA-1 and SHA-256 to demonstrate that these patches fix the issue. But in the meantime, you can use Dscho's reproduction with these patches (based on the tip of master) applied on top and observe that it passes consistently.

Hi Abhradeep,

Quoted 13 lines · Johannes Schindelin

Quoted 10 lines · Abhradeep Chakraborty

I noticed in the 'setup partial bitmaps' test case that if we comment
out the line git repack && , it runs successfully.

    test_expect_success 'setup partial bitmaps' '
        test_commit packed &&
        # git repack &&
        test_commit loose &&
        git multi-pack-index write --bitmap 2>err &&
        ...
    '

Quoted 2 lines

That's interesting. Are the .bitmap and .midx files updated as part of that repack?

I instrumented this, and saw that the multi-pack-index and multi-pack-index*.bitmap files were unchanged by the git repack invocation.

Re-generating the MIDX bitmap forcefully after the repack seems to fix things over here:

-- snip --

t/lib-bitmap.sh +3 -1

index a95537e759b..564124bda27 100644
@@ -438,7 +438,10 @@ midx_bitmap_partial_tests () {
 
        test_expect_success 'setup partial bitmaps' '
                test_commit packed &&
+ls -l .git/objects/pack/ &&
                git repack &&
+git multi-pack-index write --bitmap &&
+ls -l .git/objects/pack/ &&
                test_commit loose &&
                git multi-pack-index write --bitmap 2>err &&
                test_path_is_file $midx &&
-- snap --

This suggests to me that the multi-pack-index write --bitmap 2>err call in this hunk might reuse a stale MIDX bitmap, and that _that_ might be the root cause of this breakage.

What do you think?

Hi Abhradeep,

Quoted 10 lines · Abhradeep Chakraborty

I noticed in the 'setup partial bitmaps' test case that if we comment
out the line git repack && , it runs successfully.

    test_expect_success 'setup partial bitmaps' '
        test_commit packed &&
        # git repack &&
        test_commit loose &&
        git multi-pack-index write --bitmap 2>err &&
        ...
    '

That's interesting. Are the .bitmap and .midx files updated as part of that repack?

pack-bitmap.c +19 -0

@@ -557,13 +575,238 @@ struct include_data {
 	struct bitmap *seen;
 };
 
+struct bitmap_lookup_table_triplet {
+	uint32_t commit_pos;
+	uint64_t offset;
+	uint32_t xor_row;
+};
+
+struct bitmap_lookup_table_xor_item {
+	struct object_id oid;
+	uint64_t offset;
+};
+
+/*
+ * Given a `triplet` struct pointer and pointer `p`, this
+ * function reads the triplet beginning at `p` into the struct.
+ * Note that this function assumes that there is enough memory
+ * left for filling the `triplet` struct from `p`.
+ */
+static int lookup_table_get_triplet_by_pointer(struct bitmap_lookup_table_triplet *triplet,
+					       const unsigned char *p)

pack-bitmap.c +6 -0

+/*
+ * This function gets the raw triplet from `row`'th row in the
+ * lookup table and fills that data to the `triplet`.
+ */
+static int lookup_table_get_triplet(struct bitmap_index *bitmap_git,
+				    uint32_t pos,

pack-bitmap.c +40 -0

+		int xor_flags;
+		khiter_t hash_pos;
+		struct bitmap_lookup_table_xor_item *xor_item;
+
+		while (xor_row != 0xffffffff) {
+			ALLOC_GROW(xor_items, xor_items_nr + 1, xor_items_alloc);
+
+			if (xor_items_nr + 1 >= bitmap_git->entry_count) {
+				error(_("corrupt bitmap lookup table: xor chain exceed entry count"));
+				goto corrupt;
+			}
+
+			if (lookup_table_get_triplet(bitmap_git, xor_row, &triplet) < 0)
+				goto corrupt;
+
+			xor_item = &xor_items[xor_items_nr];
+			xor_item->offset = triplet.offset;
+
+			if (nth_bitmap_object_oid(bitmap_git, &xor_item->oid, triplet.commit_pos) < 0) {
+				error(_("corrupt bitmap lookup table: commit index %u out of range"),
+					triplet.commit_pos);
+				goto corrupt;
+			}
+
+			hash_pos = kh_get_oid_map(bitmap_git->bitmaps, xor_item->oid);
+
+			/*
+			 * If desired bitmap is already stored, we don't need
+			 * to iterate further. Because we know that bitmaps
+			 * that are needed to be parsed to parse this bitmap
+			 * has already been stored. So, assign this stored bitmap
+			 * to the xor_bitmap.
+			 */
+			if (hash_pos < kh_end(bitmap_git->bitmaps) &&
+			    (xor_bitmap = kh_value(bitmap_git->bitmaps, hash_pos)))
+				break;
+			xor_items_nr++;
+			xor_row = triplet.xor_row;
+		}
+

pack-bitmap.c +22 -0

+			xor_flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
+			bitmap = read_bitmap_1(bitmap_git);
+
+			if (!bitmap)
+				goto corrupt;
+
+			xor_bitmap = store_bitmap(bitmap_git, bitmap, &xor_item->oid, xor_bitmap, xor_flags);
+			xor_items_nr--;
+		}
+	}
+
+	bitmap_git->map_pos = offset;
+	if (bitmap_git->map_size - bitmap_git->map_pos < bitmap_header_size) {
+		error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
+			oid_to_hex(oid));
+		goto corrupt;
+	}
+
+	bitmap_git->map_pos = bitmap_git->map_pos + sizeof(uint32_t) + sizeof(uint8_t);
+	flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
+	bitmap = read_bitmap_1(bitmap_git);
+

Just noticing this now, but I wonder if we could avoid incrementing p here and instead write something like:

    triplet->commit_pos = get_be32(p);
    triplet->offset = get_be64(p + sizeof(uint32_t));
    triplet->xor_row = get_be64(p + sizeof(uint64_t) + sizeof(uint32_t));

I don't have a strong feeling about it, though, it just seems to read a little more directly to me and avoid modifying a variable that is only going to live as long as the function executes (p).

Quoted 6 lines

pack-bitmap.c +6 -0

+/*
+ * This function gets the raw triplet from `row`'th row in the
+ * lookup table and fills that data to the `triplet`.
+ */
+static int lookup_table_get_triplet(struct bitmap_index *bitmap_git,
+                                 uint32_t pos,

pack-bitmap.c struct include_data { · line 624

Quoted 10 lines

pack-bitmap.c +10 -0

+                                 struct bitmap_lookup_table_triplet *triplet)
+{
+     unsigned char *p = NULL;
+     if (pos >= bitmap_git->entry_count)
+             return error(_("corrupt bitmap lookup table: triplet position out of index"));
+
+     p = bitmap_git->table_lookup + st_mult(pos, BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH);
+
+     return lookup_table_get_triplet_by_pointer(triplet, p);
+}

Very nice. This cleans things up nicely by being able to call lookup_table_get_triplet_by_pointer().

Since these are static functions, it doesn't really matter whether or not they are prefixed with 'bitmap_', since they won't be visible outside of pack-bitmap.c's compilation unit. But it may be nice to prefix them with 'bitmap_' just to make it extra clear that these are internal functions meant to be used within the bitmap machinery only.

pack-bitmap.c struct include_data { · line 694

Quoted 4 lines

pack-bitmap.c +4 -0

+     static int is_corrupt = 0;
+
+     if (is_corrupt)
+             return NULL;

What is the purpose of this conditional? We don't modify is_corrupt before reading it here, so this should be dead code, unless I'm missing something.

pack-bitmap.c struct include_data { · line 708

Quoted 5 lines

pack-bitmap.c +4 -0

+     offset = triplet.offset;
+     xor_row = triplet.xor_row;
+
+     if (xor_row != 0xffffffff) {

Is this outer conditional needed? I don't think it is. If xor_row is 0xffffffff, then the while loop below won't be entered, and xor_items_nr will be zero, meaning that the second while loop will also be skipped.

Quoted 1 line

+ bitmap_git->map_pos = bitmap_git->map_pos + sizeof(uint32_t) + sizeof(uint8_t);

Could we write:

    bitmap_git->map_pos += sizeof(uint32_t) + sizeof(uint8_t)

pack-bitmap.c struct include_data { · line 606

Quoted 6 lines · Abhradeep Chakraborty via GitGitGadget

pack-bitmap.c +6 -0

+     triplet->commit_pos = get_be32(p);
+     p += sizeof(uint32_t);
+     triplet->offset = get_be64(p);
+     p += sizeof(uint64_t);
+     triplet->xor_row = get_be32(p);
+     return 0;

Just noticing this now, but I wonder if we could avoid incrementing p here and instead write something like:

    triplet->commit_pos = get_be32(p);
    triplet->offset = get_be64(p + sizeof(uint32_t));
    triplet->xor_row = get_be64(p + sizeof(uint64_t) + sizeof(uint32_t));

I don't have a strong feeling about it, though, it just seems to read a little more directly to me and avoid modifying a variable that is only going to live as long as the function executes (p).

From: Abhradeep Chakraborty <[email protected]>

Enable pack.writeReverseIndex before running pack-bitmap related performance tests.

The performance difference with pack.writeReverseIndex enabled and with disabled are given below -

Quoted 7 lines · Abhradeep Chakraborty via GitGitGadget

From: Abhradeep Chakraborty <[email protected]>

Enable pack.writeReverseIndex before running pack-bitmap related performance tests.

The performance difference with pack.writeReverseIndex enabled and with disabled are given below -

Thanks; this order of changes in the t/perf suite makes sense to me. One note, this sort of change where we're comparing all of the tests in a single t/perf file against themselves before and after some change, it is helpful to do (in t/perf)

./run HEAD . p5310-pack-bitmaps.sh

which compares HEAD to what's in the current tree. You'll get the results side-by-side, which makes them a little easier to scan. You can also aggregate results together from multiple runs with the t/perf/aggregate.perl script.

One gotcha (that has often bitten me in the past) is that when running the perf suite with . as your build target, it uses whatever git binary is sitting in your tree. So make sure that it is both (a) up-to-date, ie., that it is the result of compiling what's currently in your tree, and (b) that it is compiled with the same settings as what you built HEAD with.

I have often scratched my head at why the result of running some perf suite on '.' seems much slower than it should be, only to realize that the "git" binary sitting in my tree was built with -O0 or something.

Rather than comparing HEAD to your current tree it's generally better to do something like:

	GIT_PERF_MAKE_OPTS='-j3' ./run HEAD~ HEAD [...]

Quoted 4 lines · Ævar Arnfjörð Bjarmason

Rather than comparing HEAD to your current tree it's generally better to do something like:

	GIT_PERF_MAKE_OPTS='-j3' ./run HEAD~ HEAD [...]

Using the 'run' script fixes the perf test in the worktree and tests different versions of the 'git' executable.

That doesn't work when the change is in the performance test itself.

But then we're losing the perf test coverage for the case where we don't have the *.rev files. Isn't it better to run both with & without *.rev, perhaps by splitting up the test file? We could make it a function in perf/lib-bitmap.sh that we call both with & without the wanted *.rev repack config.

I suspect that's also subtly broken, in that t/perf assumes that it can re-use the repo for a given <rev>, but this is modifying that repo, so if you run e.g. test Y after this Y, that Y will unexpectedly get a repack'd repo ...

But we could just start the test with a git clone . "$TEST_NAME" or whatever, then repack that with whatever options we want...