[v5,3/6] pack-bitmap-write: learn pack.writeBitmapLookupTable and add tests

Commit Message

Abhradeep Chakraborty July 20, 2022, 6:38 p.m. UTC

From: Abhradeep Chakraborty <[e-mail]>

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 <[e-mail]>
Co-Mentored-by: Kaartic Sivaraam <[e-mail]>
Co-Authored-by: Taylor Blau <[e-mail]>
Signed-off-by: Abhradeep Chakraborty <[e-mail]>
---
 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(-)

Comments

Johannes Schindelin July 28, 2022, 7:22 p.m. UTC | #1

Hi Abhradeep,

On Wed, 20 Jul 2022, Abhradeep Chakraborty via GitGitGadget wrote:

> From: Abhradeep Chakraborty <[e-mail]>
>
> 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 <[e-mail]>
> Co-Mentored-by: Kaartic Sivaraam <[e-mail]>
> Co-Authored-by: Taylor Blau <[e-mail]>
> Signed-off-by: Abhradeep Chakraborty <[e-mail]>
> ---
>  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 +++++++++-------

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?

Sadly, this patch is way too large for me to do a drive-by debugging
session, so I will have to leave it to you to investigate further.

Ciao,
Dscho

>  t/t5327-multi-pack-bitmaps-rev.sh |  24 +-
>  9 files changed, 733 insertions(+), 583 deletions(-)
>
> diff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt
> index ad7f73a1ead..b955ca572ec 100644
> --- a/Documentation/config/pack.txt
> +++ b/Documentation/config/pack.txt
> @@ -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])
> diff --git a/builtin/multi-pack-index.c b/builtin/multi-pack-index.c
> index 5edbb7fe86e..55402b46f41 100644
> --- a/builtin/multi-pack-index.c
> +++ b/builtin/multi-pack-index.c
> @@ -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()'.
> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
> index 39e28cfcafc..46e26774963 100644
> --- a/builtin/pack-objects.c
> +++ b/builtin/pack-objects.c
> @@ -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;
> diff --git a/midx.c b/midx.c
> index 5f0dd386b02..9c26d04bfde 100644
> --- a/midx.c
> +++ b/midx.c
> @@ -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);
> diff --git a/midx.h b/midx.h
> index 22e8e53288e..5578cd7b835 100644
> --- a/midx.h
> +++ b/midx.h
> @@ -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);
> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
> index f775fc1ce69..c0607172827 100755
> --- a/t/t5310-pack-bitmaps.sh
> +++ b/t/t5310-pack-bitmaps.sh
> @@ -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
> diff --git a/t/t5311-pack-bitmaps-shallow.sh b/t/t5311-pack-bitmaps-shallow.sh
> index 872a95df338..9dae60f73e3 100755
> --- a/t/t5311-pack-bitmaps-shallow.sh
> +++ b/t/t5311-pack-bitmaps-shallow.sh
> @@ -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
> diff --git a/t/t5326-multi-pack-bitmaps.sh b/t/t5326-multi-pack-bitmaps.sh
> index 4fe57414c13..3b206adcee6 100755
> --- a/t/t5326-multi-pack-bitmaps.sh
> +++ b/t/t5326-multi-pack-bitmaps.sh
> @@ -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
>  	)
>  '
>
> diff --git a/t/t5327-multi-pack-bitmaps-rev.sh b/t/t5327-multi-pack-bitmaps-rev.sh
> index d30ba632c87..5ed16a820d1 100755
> --- a/t/t5327-multi-pack-bitmaps-rev.sh
> +++ b/t/t5327-multi-pack-bitmaps-rev.sh
> @@ -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
>
>
>

Abhradeep Chakraborty Aug. 2, 2022, 12:40 p.m. UTC | #2

On Fri, Jul 29, 2022 at 12:52 AM Johannes Schindelin
<[e-mail]> wrote:
> 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.

> -- 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?

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.

Thanks :)

Johannes Schindelin Aug. 2, 2022, 3:35 p.m. UTC | #3

Hi Abhradeep,

On Tue, 2 Aug 2022, Abhradeep Chakraborty wrote:

> On Fri, Jul 29, 2022 at 12:52 AM Johannes Schindelin
> <[e-mail]> wrote:
> > 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.
>
> > -- 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?
>
> Yeah, I can reproduce it on my side.

Good.

> 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 --
diff --git a/t/t5326-multi-pack-bitmaps.sh b/t/t5326-multi-pack-bitmaps.sh
index 3b206adcee6..a340f005b89 100755
--- a/t/t5326-multi-pack-bitmaps.sh
+++ b/t/t5326-multi-pack-bitmaps.sh
@@ -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.

For shiggles, I now also ran this command-line after deleting the
`"pack.writeBitmapLookupTable"` argument, and it fails in the exact same
way. So you're correct: this has nothing to do with the
`writeBitmapLookupTable` code, it's just a failure that is triggered by
those patches.

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

I do not actually think so. I believe that this just points out a bug in
the MIDX bitmap code.

> 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.

Thanks,
Dscho

Abhradeep Chakraborty Aug. 2, 2022, 5:44 p.m. UTC | #4

On Tue, Aug 2, 2022 at 9:05 PM Johannes Schindelin
<[e-mail]> wrote:
> > 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 --
> diff --git a/t/t5326-multi-pack-bitmaps.sh b/t/t5326-multi-pack-bitmaps.sh
> index 3b206adcee6..a340f005b89 100755
> --- a/t/t5326-multi-pack-bitmaps.sh
> +++ b/t/t5326-multi-pack-bitmaps.sh
> @@ -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.

Yeah, this works for me also.

> > 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 also encountered the same and it blew my mind at first (because it
is the first race condition that I faced in my life) :)

> 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 agree with you.

> 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.

Yeah, definitely! Thanks for all the information! It will truly help
me to identify the problem.

> 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.

Ok, sure!

Thanks :)

Johannes Schindelin Aug. 8, 2022, 1:06 p.m. UTC | #5

Hi Abhradeep,

On Tue, 2 Aug 2022, Abhradeep Chakraborty wrote:

> On Tue, Aug 2, 2022 at 9:05 PM Johannes Schindelin
> <[e-mail]> wrote:
>
> > 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

Abhradeep Chakraborty Aug. 8, 2022, 1:58 p.m. UTC | #6

On Mon, Aug 8, 2022 at 6:36 PM Johannes Schindelin
<[e-mail]> wrote:
>
> Hi Abhradeep,
>
> On Tue, 2 Aug 2022, Abhradeep Chakraborty wrote:
>
> > On Tue, Aug 2, 2022 at 9:05 PM Johannes Schindelin
> > <[e-mail]> wrote:
> >
> > > 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.

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. Sorry for that :|
I am still trying it.

Hope I will be able to share the good news soon. Thanks :)
> Ciao,
> Dscho

Johannes Schindelin Aug. 9, 2022, 9:03 a.m. UTC | #7

Hi Abhradeep,

On Mon, 8 Aug 2022, Abhradeep Chakraborty wrote:

> On Mon, Aug 8, 2022 at 6:36 PM Johannes Schindelin
> <[e-mail]> wrote:
> >
> > On Tue, 2 Aug 2022, Abhradeep Chakraborty wrote:
> >
> > > On Tue, Aug 2, 2022 at 9:05 PM Johannes Schindelin
> > > <[e-mail]> wrote:
> > >
> > > > 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.
>
> 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.

> 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.

Thanks,
Dscho

Abhradeep Chakraborty Aug. 9, 2022, 12:03 p.m. UTC | #8

On Tue, Aug 9, 2022 at 2:33 PM Johannes Schindelin
<[e-mail]> wrote:
>
> Hi Abhradeep,
>
> On Mon, 8 Aug 2022, Abhradeep Chakraborty wrote:
>
> > On Mon, Aug 8, 2022 at 6:36 PM Johannes Schindelin
> > <[e-mail]> wrote:
> > >
> > > On Tue, 2 Aug 2022, Abhradeep Chakraborty wrote:
> > >
> > > > On Tue, Aug 2, 2022 at 9:05 PM Johannes Schindelin
> > > > <[e-mail]> wrote:
> > > >
> > > > > 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.
> >
> > 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.

Yeah, it should. I thought that I would do that after fixing the bug.
Now I think I was wrong.

> > 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.

Frankly speaking, I doubt that the generated multi-pack-index file is
faulty. The first reason is the `.bitmap` filename. As you said before
(and as I noticed here), `.bitmap` filenames in failing case and in
passing case are different. As far as I know the hash value in the
filename depends on the content of its respective midx file. So, if
the midx contents were the same in both cases, `.bitmap` filename
should not differ.

I compared both the multi-pack-index files (i.e. passing case and
failing case) using `cmp ./trash\
directory.t5326-multi-pack-bitmaps/.git/objects/pack/multi-pack-index
../tmp/trash\ directory.t5326-multi-pack-bitmaps/.git/objects/pack/multi-pack-index`
and found that these both defers -

    differ: char 3124, line 10

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 &&
        ...
    '

Abhradeep Chakraborty Aug. 9, 2022, 12:07 p.m. UTC | #9

On Tue, Aug 9, 2022 at 5:33 PM Abhradeep Chakraborty
<[e-mail]> wrote:
> 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.

Looks like I forgot to specify the link -
https://github.com/git/git/blob/c50926e1f48891e2671e1830dbcd2912a4563450/pack-objects.c#L87

Johannes Schindelin Aug. 10, 2022, 9:09 a.m. UTC | #10

Hi Abhradeep,

On Tue, 9 Aug 2022, Abhradeep Chakraborty wrote:

>  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`?

Ciao,
Dscho

Johannes Schindelin Aug. 10, 2022, 9:20 a.m. UTC | #11

Hi Abhradeep,

On Wed, 10 Aug 2022, Johannes Schindelin wrote:

> On Tue, 9 Aug 2022, Abhradeep Chakraborty wrote:
>
> >  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`?

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 --
diff --git a/t/lib-bitmap.sh b/t/lib-bitmap.sh
index a95537e759b..564124bda27 100644
--- a/t/lib-bitmap.sh
+++ b/t/lib-bitmap.sh
@@ -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?

Ciao,
Dscho

Abhradeep Chakraborty Aug. 10, 2022, 10:04 a.m. UTC | #12

On Wed, Aug 10, 2022 at 2:50 PM Johannes Schindelin
<[e-mail]> wrote:
>
> 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.

> Re-generating the MIDX bitmap forcefully after the repack seems to fix
> things over here:
>
> -- snip --
> diff --git a/t/lib-bitmap.sh b/t/lib-bitmap.sh
> index a95537e759b..564124bda27 100644
> --- a/t/lib-bitmap.sh
> +++ b/t/lib-bitmap.sh
> @@ -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.

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.

Thanks :)

[1] https://github.com/git/git/blob/c50926e1f48891e2671e1830dbcd2912a4563450/midx.c#L861
[2] https://github.com/git/git/blob/c50926e1f48891e2671e1830dbcd2912a4563450/midx.c#L872

Derrick Stolee Aug. 10, 2022, 5:51 p.m. UTC | #13

On 8/10/2022 6:04 AM, Abhradeep Chakraborty wrote:
> On Wed, Aug 10, 2022 at 2:50 PM Johannes Schindelin
> <[e-mail]> wrote:
>>
>> 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.
> 
>> Re-generating the MIDX bitmap forcefully after the repack seems to fix
>> things over here:
>>
>> -- snip --
>> diff --git a/t/lib-bitmap.sh b/t/lib-bitmap.sh
>> index a95537e759b..564124bda27 100644
>> --- a/t/lib-bitmap.sh
>> +++ b/t/lib-bitmap.sh
>> @@ -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.
> 
> 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.

You are right that this choice of a 'preferred' pack is part of the
root cause for this flake. This choice is not deterministic if the
mtime of some pack-files are within the same second.

I can make the flake go away with this change:

diff --git a/t/lib-bitmap.sh b/t/lib-bitmap.sh
index a95537e759b0..30347285f10f 100644
--- a/t/lib-bitmap.sh
+++ b/t/lib-bitmap.sh
@@ -438,7 +438,9 @@ midx_bitmap_partial_tests () {
 
 	test_expect_success 'setup partial bitmaps' '
 		test_commit packed &&
+		test_tick &&
 		git repack &&
+		test_tick &&
 		test_commit loose &&
 		git multi-pack-index write --bitmap 2>err &&
 		test_path_is_file $midx &&


However, that doesn't help us actually find out what the problem is
in our case.

I've tried exploring other considerations, resulting in this diff:

diff --git a/midx.c b/midx.c
index 9c26d04bfded..3b9094d55ae5 100644
--- a/midx.c
+++ b/midx.c
@@ -921,8 +921,9 @@ static void prepare_midx_packing_data(struct packing_data *pdata,
 		struct pack_midx_entry *from = &ctx->entries[ctx->pack_order[i]];
 		struct object_entry *to = packlist_alloc(pdata, &from->oid);
 
+		/* Why does removing the permutation here not change the outcome? */
 		oe_set_in_pack(pdata, to,
-			       ctx->info[ctx->pack_perm[from->pack_int_id]].p);
+			       ctx->info[from->pack_int_id].p);
 	}
 }
 
This method is setting up some important information, supposedly, and
in the failing case I see that the ctx->pack_perm performs a 5-cycle
( 0->1, 1->2, 2->3, 3->4, 4->0 ) but this removal does not affect _any
existing test cases_!

Turns out that the packfile sent here goes through this very trivial
path in oe_set_in_pack() every time we are writing a multi-pack-index:

static inline void oe_set_in_pack(struct packing_data *pack,
				  struct object_entry *e,
				  struct packed_git *p)
{
	if (pack->in_pack_by_idx) {
		if (p->index) {
			e->in_pack_idx = p->index;
			return;
		}
		/*
		 * We're accessing packs by index, but this pack doesn't have
		 * an index (e.g., because it was added since we created the
		 * in_pack_by_idx array). Bail to oe_map_new_pack(), which
		 * will convert us to using the full in_pack array, and then
		 * fall through to our in_pack handling.
		 */
		oe_map_new_pack(pack);
	}
	pack->in_pack[e - pack->objects] = p;
}

By debugging, I discovered we are hitting the case that calls
oe_map_new_pack(pack). The documentation for that method provides
the following (**emphasis mine**):

/*
 * A new pack appears after prepare_in_pack_by_idx() has been
 * run. **This is likely a race.**
 *
 * We could map this new pack to in_pack_by_idx[] array, but then we
 * have to deal with full array anyway. And since it's hard to test
 * this fall back code, just stay simple and fall back to using
 * in_pack[] array.
 */
void oe_map_new_pack(struct packing_data *pack)

The issue being that prepare_packing_data() uses get_all_packs() to
get the list of pack-files, but that list is stale for some reason.
Adding a reprepare_packed_git() in advance of that call also removes
the flake (with always passing):

diff --git a/midx.c b/midx.c
index 9c26d04bfded..48db91d2728a 100644
--- a/midx.c
+++ b/midx.c
@@ -915,6 +915,7 @@ static void prepare_midx_packing_data(struct packing_data *pdata,
 	uint32_t i;
 
 	memset(pdata, 0, sizeof(struct packing_data));
+	reprepare_packed_git(the_repository);
 	prepare_packing_data(the_repository, pdata);
 
 	for (i = 0; i < ctx->entries_nr; i++) {

But this still appears like it is just a band-aid over a trickier
underlying issue.

Hopefully my rambling helps push you in a helpful direction to find
a more complete fix.

Thanks,
-Stolee

Abhradeep Chakraborty Aug. 12, 2022, 6:51 p.m. UTC | #14

Hello,

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.

Derrick Stolee Aug. 12, 2022, 7:22 p.m. UTC | #15

On 8/12/2022 2:51 PM, Abhradeep Chakraborty wrote:

> 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.

Thanks for the detailed writeup.

> 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?

The confusing part of all this is that the bitmaps are being written
while the "new" midx is written only to "multi-pack-index.lock" and
has not been renamed to "multi-pack-index". If we renamed first, then
the old .bitmap file would not match the new midx and all Git commands
would act as if there was no .bitmap file.
 
> 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).

Thanks,
-Stolee

Abhradeep Chakraborty Aug. 13, 2022, 10:59 a.m. UTC | #16

On Sat, Aug 13, 2022 at 12:52 AM Derrick Stolee
<[e-mail]> wrote:
>
> 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).

`reprepare_packed_git()` can not stop it. Because this function
updates `r->objects->packed_git` list (i.e. it reloads packs that are
not in the old midx) and as I said before, we are setting `->index`
for only r->objects->packed_git not ctx.info[id].p. So, it will call
the `oe_map_new_pack()` function in either way.  I have tested it.

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.

Abhradeep Chakraborty Aug. 13, 2022, 11:05 a.m. UTC | #17

On Wed, Aug 10, 2022 at 2:50 PM Johannes Schindelin
<[e-mail]> wrote:
>
> Hi Abhradeep,
>
> On Wed, 10 Aug 2022, Johannes Schindelin wrote:
>
> > On Tue, 9 Aug 2022, Abhradeep Chakraborty wrote:
> >
> > >  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`?
>
> 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 --
> diff --git a/t/lib-bitmap.sh b/t/lib-bitmap.sh
> index a95537e759b..564124bda27 100644
> --- a/t/lib-bitmap.sh
> +++ b/t/lib-bitmap.sh
> @@ -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 Dscho,
I used your code to see if it is the case but it doesn't affect the
result (at least in my laptop).

Taylor Blau Aug. 16, 2022, 6:47 p.m. UTC | #18

On Wed, Aug 10, 2022 at 11:09:40AM +0200, Johannes Schindelin wrote:
> Hi Abhradeep,
>
> On Tue, 9 Aug 2022, Abhradeep Chakraborty wrote:
>
> >  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`?

They aren't. You can cause a MIDX / bitmap to be updated during `git
repack` provided that the flags `--write-midx` and
`--write-bitmap-index` are given to `repack`.

But the point of that `git repack` in this test case specifically is to
ensure that the commit generated on the previous line is included in a
new pack, and that that pack makes its way into the MIDX.

So removing that invocation of `git repack` means that the set of packs
would be unchanged, and the `git multi-pack-index write --bitmap` would
be a noop. That should rule out the theory that the existing MIDX is
broken, since without the `git repack`, we'd be using that MIDX in
subsequent tests (which pass).

Thanks,
Taylor

Taylor Blau Aug. 16, 2022, 9:57 p.m. UTC | #19

Hi Abhradeep,

On Sat, Aug 13, 2022 at 04:29:32PM +0530, Abhradeep Chakraborty wrote:
> 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.

After much consternation, I was able to rule out `oe_map_new_pack()` as
the culprit.

(Your find that we call `add_packed_git()` with arguments corresponding
to pack(s) that we've already loaded is good, and I think that is
definitely something we can and should consider cleaning up. But it
ultimately doesn't affect correctness, just the memory efficiency of the
process).

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 ---

diff --git a/midx.c b/midx.c
index 3ff6e91e6e..40e520534c 100644
--- a/midx.c
+++ b/midx.c
@@ -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]);
@@ -629,7 +632,7 @@ static struct pack_midx_entry *get_sorted_entries(struct multi_pack_index *m,
 				nth_midxed_pack_midx_entry(m,
 							   &entries_by_fanout[nr_fanout],
 							   cur_object);
-				if (nth_midxed_pack_int_id(m, cur_object) == preferred_pack)
+				if (nth_midxed_pack_int_id(m, cur_object) == orig_preferred_pack)
 					entries_by_fanout[nr_fanout].preferred = 1;
 				else
 					entries_by_fanout[nr_fanout].preferred = 0;

--- 8< ---

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.

Phew.

Thanks,
Taylor

Abhradeep Chakraborty Aug. 17, 2022, 10:02 a.m. UTC | #20

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

On Wed, Aug 17, 2022 at 3:28 AM Taylor Blau <[e-mail]> wrote:
>
> 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 ---
>
> diff --git a/midx.c b/midx.c
> index 3ff6e91e6e..40e520534c 100644
> --- a/midx.c
> +++ b/midx.c
> @@ -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]);
> @@ -629,7 +632,7 @@ static struct pack_midx_entry *get_sorted_entries(struct multi_pack_index *m,
>                                 nth_midxed_pack_midx_entry(m,
>                                                            &entries_by_fanout[nr_fanout],
>                                                            cur_object);
> -                               if (nth_midxed_pack_int_id(m, cur_object) == preferred_pack)
> +                               if (nth_midxed_pack_int_id(m, cur_object) == orig_preferred_pack)
>                                         entries_by_fanout[nr_fanout].preferred = 1;
>                                 else
>                                         entries_by_fanout[nr_fanout].preferred = 0;
>
> --- 8< ---

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.

> 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.

ahh, now I understand what the problem was actually. Thanks :)

> 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.

> 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).

My exam dates are 18 Aug, 31 Aug, 1 Sep, 2 Sep and 3 Sep (I know the
dates are weird) The dates are adjusted on request for Smart India
Hackathon ( 24 Aug - 27 Aug).

Thanks :)

Taylor Blau Aug. 17, 2022, 8:38 p.m. UTC | #21

On Wed, Aug 17, 2022 at 03:32:31PM +0530, Abhradeep Chakraborty wrote:
> Hello Taylor, extremely thanks for finding the reason for this failure.

No problem. I appreciate all of the time and effort that you, Dscho, and
Stolee all put into looking into this (especially while I was out).

My experience with the bitmap code is that it can be somewhat difficult
to work in, because there are both (a) many ways to introduce bugs, and
(b) the effect of a bug can occur far away from the source of the bug.
Those two together make debugging difficult, at least for me.

I think that having a test-tool (like Dscho suggested) to dump some
basic information about a bitmap's structure would be quite helpful in
the future.

> On Wed, Aug 17, 2022 at 3:28 AM Taylor Blau <[e-mail]> wrote:
> 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.

Yeah, I realized that this is bogus. For one, (as you note) those have
the same value before setting up the pack_perm array. But it also goes
against the grain of what we're trying to do: the point is that the
prefered-ness of objects in an existing MIDX should be discarded when
generating a new pseudo-pack order.

> > 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.

Yep, I agree. Users should feel free to change the identity of the
preferred pack when rewriting a MIDX regardless of whether or not they
are using `--stdin-packs`.

> > 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).

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.

Thanks,
Taylor

Taylor Blau Aug. 19, 2022, 9:49 p.m. UTC | #22

Hi Abhradeep,

On Wed, Aug 17, 2022 at 04:38:14PM -0400, Taylor Blau wrote:
> > > 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).
>
> 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.

That is now done and I sent the resulting patch series to the list,
which I'd encourage you to review here:

    https://lore.kernel.org/git/[e-mail]/T/#t

Phew!

Thanks,
Taylor

Patch

diff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt
index ad7f73a1ead..b955ca572ec 100644
--- a/Documentation/config/pack.txt
+++ b/Documentation/config/pack.txt
@@ -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])
diff --git a/builtin/multi-pack-index.c b/builtin/multi-pack-index.c
index 5edbb7fe86e..55402b46f41 100644
--- a/builtin/multi-pack-index.c
+++ b/builtin/multi-pack-index.c
@@ -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()'.
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 39e28cfcafc..46e26774963 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -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;
diff --git a/midx.c b/midx.c
index 5f0dd386b02..9c26d04bfde 100644
--- a/midx.c
+++ b/midx.c
@@ -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);
diff --git a/midx.h b/midx.h
index 22e8e53288e..5578cd7b835 100644
--- a/midx.h
+++ b/midx.h
@@ -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);
diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
index f775fc1ce69..c0607172827 100755
--- a/t/t5310-pack-bitmaps.sh
+++ b/t/t5310-pack-bitmaps.sh
@@ -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
diff --git a/t/t5311-pack-bitmaps-shallow.sh b/t/t5311-pack-bitmaps-shallow.sh
index 872a95df338..9dae60f73e3 100755
--- a/t/t5311-pack-bitmaps-shallow.sh
+++ b/t/t5311-pack-bitmaps-shallow.sh
@@ -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
diff --git a/t/t5326-multi-pack-bitmaps.sh b/t/t5326-multi-pack-bitmaps.sh
index 4fe57414c13..3b206adcee6 100755
--- a/t/t5326-multi-pack-bitmaps.sh
+++ b/t/t5326-multi-pack-bitmaps.sh
@@ -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
 	)
 '
 
diff --git a/t/t5327-multi-pack-bitmaps-rev.sh b/t/t5327-multi-pack-bitmaps-rev.sh
index d30ba632c87..5ed16a820d1 100755
--- a/t/t5327-multi-pack-bitmaps-rev.sh
+++ b/t/t5327-multi-pack-bitmaps-rev.sh
@@ -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