Merge branch 'ac/bitmap-lookup-table'

The pack bitmap file gained a bitmap-lookup table to speed up
locating the necessary bitmap for a given commit.

* ac/bitmap-lookup-table:
  pack-bitmap-write: drop unused pack_idx_entry parameters
  bitmap-lookup-table: add performance tests for lookup table
  pack-bitmap: prepare to read lookup table extension
  pack-bitmap-write: learn pack.writeBitmapLookupTable and add tests
  pack-bitmap-write.c: write lookup table extension
  bitmap: move `get commit positions` code to `bitmap_writer_finish`
  Documentation/technical: describe bitmap lookup table extension

18 files changed, 1375 insertions, 711 deletions

diff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt
index 3e581eab84..53093d9996 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:
 	linkgit:gitformat-pack[5])
diff --git a/Documentation/technical/bitmap-format.txt b/Documentation/technical/bitmap-format.txt
index a85f58f515..c2e652b71a 100644
--- a/Documentation/technical/bitmap-format.txt
+++ b/Documentation/technical/bitmap-format.txt
@@ -72,6 +72,17 @@ MIDXs, both the bit-cache and rev-cache extensions are required.
 	    pack/MIDX. The format and meaning of the name-hash is
 	    described below.
 
+		** {empty}
+		BITMAP_OPT_LOOKUP_TABLE (0x10): :::
+		If present, the end of the bitmap file contains a table
+		containing a list of `N` <commit_pos, offset, xor_row>
+		triplets. The format and meaning of the table is described
+		below.
++
+NOTE: Unlike the xor_offset used to compress an individual bitmap,
+`xor_row` stores an *absolute* index into the lookup table, not a location
+relative to the current entry.
+
 	4-byte entry count (network byte order): ::
 	    The total count of entries (bitmapped commits) in this bitmap index.
 
@@ -216,3 +227,31 @@ Note that this hashing scheme is tied to the BITMAP_OPT_HASH_CACHE flag.
 If implementations want to choose a different hashing scheme, they are
 free to do so, but MUST allocate a new header flag (because comparing
 hashes made under two different schemes would be pointless).
+
+Commit lookup table
+-------------------
+
+If the BITMAP_OPT_LOOKUP_TABLE flag is set, the last `N * (4 + 8 + 4)`
+bytes (preceding the name-hash cache and trailing hash) of the `.bitmap`
+file contains a lookup table specifying the information needed to get
+the desired bitmap from the entries without parsing previous unnecessary
+bitmaps.
+
+For a `.bitmap` containing `nr_entries` reachability bitmaps, the table
+contains a list of `nr_entries` <commit_pos, offset, xor_row> triplets
+(sorted in the ascending order of `commit_pos`). The content of i'th
+triplet is -
+
+	* {empty}
+	commit_pos (4 byte integer, network byte order): ::
+	It stores the object position of a commit (in the midx or pack
+	index).
+
+	* {empty}
+	offset (8 byte integer, network byte order): ::
+	The offset from which that commit's bitmap can be read.
+
+	* {empty}
+	xor_row (4 byte integer, network byte order): ::
+	The position of the triplet whose bitmap is used to compress
+	this one, or `0xffffffff` if no such bitmap exists.
diff --git a/builtin/multi-pack-index.c b/builtin/multi-pack-index.c
index 248929f2e6..3bfad9149d 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 39e28cfcaf..46e2677496 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 148ecc2f14..c27d0e5f15 100644
--- a/midx.c
+++ b/midx.c
@@ -1119,6 +1119,9 @@ static int write_midx_bitmap(const char *midx_name,
 	if (flags & MIDX_WRITE_BITMAP_HASH_CACHE)
 		options |= BITMAP_OPT_HASH_CACHE;
 
+	if (flags & MIDX_WRITE_BITMAP_LOOKUP_TABLE)
+		options |= BITMAP_OPT_LOOKUP_TABLE;
+
 	/*
 	 * Build the MIDX-order index based on pdata.objects (which is already
 	 * in MIDX order; c.f., 'midx_pack_order_cmp()' for the definition of
diff --git a/midx.h b/midx.h
index 22e8e53288..5578cd7b83 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/pack-bitmap-write.c b/pack-bitmap-write.c
index 4fcfaed428..a213f5eddc 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -649,21 +649,18 @@ static const struct object_id *oid_access(size_t pos, const void *table)
 }
 
 static void write_selected_commits_v1(struct hashfile *f,
-				      struct pack_idx_entry **index,
-				      uint32_t index_nr)
+				      uint32_t *commit_positions,
+				      off_t *offsets)
 {
 	int i;
 
 	for (i = 0; i < writer.selected_nr; ++i) {
 		struct bitmapped_commit *stored = &writer.selected[i];
 
-		int commit_pos =
-			oid_pos(&stored->commit->object.oid, index, index_nr, oid_access);
+		if (offsets)
+			offsets[i] = hashfile_total(f);
 
-		if (commit_pos < 0)
-			BUG("trying to write commit not in index");
-
-		hashwrite_be32(f, commit_pos);
+		hashwrite_be32(f, commit_positions[i]);
 		hashwrite_u8(f, stored->xor_offset);
 		hashwrite_u8(f, stored->flags);
 
@@ -671,6 +668,79 @@ static void write_selected_commits_v1(struct hashfile *f,
 	}
 }
 
+static int table_cmp(const void *_va, const void *_vb, void *_data)
+{
+	uint32_t *commit_positions = _data;
+	uint32_t a = commit_positions[*(uint32_t *)_va];
+	uint32_t b = commit_positions[*(uint32_t *)_vb];
+
+	if (a > b)
+		return 1;
+	else if (a < b)
+		return -1;
+
+	return 0;
+}
+
+static void write_lookup_table(struct hashfile *f,
+			       uint32_t *commit_positions,
+			       off_t *offsets)
+{
+	uint32_t i;
+	uint32_t *table, *table_inv;
+
+	ALLOC_ARRAY(table, writer.selected_nr);
+	ALLOC_ARRAY(table_inv, writer.selected_nr);
+
+	for (i = 0; i < writer.selected_nr; i++)
+		table[i] = i;
+
+	/*
+	 * At the end of this sort table[j] = i means that the i'th
+	 * bitmap corresponds to j'th bitmapped commit (among the selected
+	 * commits) in lex order of OIDs.
+	 */
+	QSORT_S(table, writer.selected_nr, table_cmp, commit_positions);
+
+	/* table_inv helps us discover that relationship (i'th bitmap
+	 * to j'th commit by j = table_inv[i])
+	 */
+	for (i = 0; i < writer.selected_nr; i++)
+		table_inv[table[i]] = i;
+
+	trace2_region_enter("pack-bitmap-write", "writing_lookup_table", the_repository);
+	for (i = 0; i < writer.selected_nr; i++) {
+		struct bitmapped_commit *selected = &writer.selected[table[i]];
+		uint32_t xor_offset = selected->xor_offset;
+		uint32_t xor_row;
+
+		if (xor_offset) {
+			/*
+			 * xor_index stores the index (in the bitmap entries)
+			 * of the corresponding xor bitmap. But we need to convert
+			 * this index into lookup table's index. So, table_inv[xor_index]
+			 * gives us the index position w.r.t. the lookup table.
+			 *
+			 * If "k = table[i] - xor_offset" then the xor base is the k'th
+			 * bitmap. `table_inv[k]` gives us the position of that bitmap
+			 * in the lookup table.
+			 */
+			uint32_t xor_index = table[i] - xor_offset;
+			xor_row = table_inv[xor_index];
+		} else {
+			xor_row = 0xffffffff;
+		}
+
+		hashwrite_be32(f, commit_positions[table[i]]);
+		hashwrite_be64(f, (uint64_t)offsets[table[i]]);
+		hashwrite_be32(f, xor_row);
+	}
+	trace2_region_leave("pack-bitmap-write", "writing_lookup_table", the_repository);
+
+	free(table);
+	free(table_inv);
+}
+
 static void write_hash_cache(struct hashfile *f,
 			     struct pack_idx_entry **index,
 			     uint32_t index_nr)
@@ -697,6 +767,9 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 	static uint16_t flags = BITMAP_OPT_FULL_DAG;
 	struct strbuf tmp_file = STRBUF_INIT;
 	struct hashfile *f;
+	uint32_t *commit_positions = NULL;
+	off_t *offsets = NULL;
+	uint32_t i;
 
 	struct bitmap_disk_header header;
 
@@ -715,7 +788,26 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 	dump_bitmap(f, writer.trees);
 	dump_bitmap(f, writer.blobs);
 	dump_bitmap(f, writer.tags);
-	write_selected_commits_v1(f, index, index_nr);
+
+	if (options & BITMAP_OPT_LOOKUP_TABLE)
+		CALLOC_ARRAY(offsets, index_nr);
+
+	ALLOC_ARRAY(commit_positions, writer.selected_nr);
+
+	for (i = 0; i < writer.selected_nr; i++) {
+		struct bitmapped_commit *stored = &writer.selected[i];
+		int commit_pos = oid_pos(&stored->commit->object.oid, index, index_nr, oid_access);
+
+		if (commit_pos < 0)
+			BUG(_("trying to write commit not in index"));
+
+		commit_positions[i] = commit_pos;
+	}
+
+	write_selected_commits_v1(f, commit_positions, offsets);
+
+	if (options & BITMAP_OPT_LOOKUP_TABLE)
+		write_lookup_table(f, commit_positions, offsets);
 
 	if (options & BITMAP_OPT_HASH_CACHE)
 		write_hash_cache(f, index, index_nr);
@@ -730,4 +822,6 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 		die_errno("unable to rename temporary bitmap file to '%s'", filename);
 
 	strbuf_release(&tmp_file);
+	free(commit_positions);
+	free(offsets);
 }
diff --git a/pack-bitmap.c b/pack-bitmap.c
index ef580be9e3..9a208abc1f 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -84,6 +84,12 @@ struct bitmap_index {
 	const unsigned char *checksum;
 
 	/*
+	 * If not NULL, this point into the commit table extension
+	 * (within the memory mapped region `map`).
+	 */
+	unsigned char *table_lookup;
+
+	/*
 	 * Extended index.
 	 *
 	 * When trying to perform bitmap operations with objects that are not
@@ -186,6 +192,16 @@ static int load_bitmap_header(struct bitmap_index *index)
 			index->hashes = (void *)(index_end - cache_size);
 			index_end -= cache_size;
 		}
+
+		if (flags & BITMAP_OPT_LOOKUP_TABLE) {
+			size_t table_size = st_mult(ntohl(header->entry_count),
+						    BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH);
+			if (table_size > index_end - index->map - header_size)
+				return error(_("corrupted bitmap index file (too short to fit lookup table)"));
+			if (git_env_bool("GIT_TEST_READ_COMMIT_TABLE", 1))
+				index->table_lookup = (void *)(index_end - table_size);
+			index_end -= table_size;
+		}
 	}
 
 	index->entry_count = ntohl(header->entry_count);
@@ -212,9 +228,11 @@ static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
 
 	hash_pos = kh_put_oid_map(index->bitmaps, stored->oid, &ret);
 
-	/* a 0 return code means the insertion succeeded with no changes,
-	 * because the SHA1 already existed on the map. this is bad, there
-	 * shouldn't be duplicated commits in the index */
+	/*
+	 * A 0 return code means the insertion succeeded with no changes,
+	 * because the SHA1 already existed on the map. This is bad, there
+	 * shouldn't be duplicated commits in the index.
+	 */
 	if (ret == 0) {
 		error(_("duplicate entry in bitmap index: '%s'"), oid_to_hex(oid));
 		return NULL;
@@ -482,7 +500,7 @@ static int load_bitmap(struct bitmap_index *bitmap_git)
 		!(bitmap_git->tags = read_bitmap_1(bitmap_git)))
 		goto failed;
 
-	if (load_bitmap_entries_v1(bitmap_git) < 0)
+	if (!bitmap_git->table_lookup && load_bitmap_entries_v1(bitmap_git) < 0)
 		goto failed;
 
 	return 0;
@@ -570,13 +588,256 @@ struct include_data {
 	struct bitmap *seen;
 };
 
+struct bitmap_lookup_table_triplet {
+	uint32_t commit_pos;
+	uint64_t offset;
+	uint32_t xor_row;
+};
+
+struct bitmap_lookup_table_xor_item {
+	struct object_id oid;
+	uint64_t offset;
+};
+
+/*
+ * Given a `triplet` struct pointer and pointer `p`, this
+ * function reads the triplet beginning at `p` into the struct.
+ * Note that this function assumes that there is enough memory
+ * left for filling the `triplet` struct from `p`.
+ */
+static int bitmap_lookup_table_get_triplet_by_pointer(struct bitmap_lookup_table_triplet *triplet,
+						      const unsigned char *p)
+{
+	if (!triplet)
+		return -1;
+
+	triplet->commit_pos = get_be32(p);
+	p += sizeof(uint32_t);
+	triplet->offset = get_be64(p);
+	p += sizeof(uint64_t);
+	triplet->xor_row = get_be32(p);
+	return 0;
+}
+
+/*
+ * This function gets the raw triplet from `row`'th row in the
+ * lookup table and fills that data to the `triplet`.
+ */
+static int bitmap_lookup_table_get_triplet(struct bitmap_index *bitmap_git,
+					   uint32_t pos,
+					   struct bitmap_lookup_table_triplet *triplet)
+{
+	unsigned char *p = NULL;
+	if (pos >= bitmap_git->entry_count)
+		return error(_("corrupt bitmap lookup table: triplet position out of index"));
+
+	p = bitmap_git->table_lookup + st_mult(pos, BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH);
+
+	return bitmap_lookup_table_get_triplet_by_pointer(triplet, p);
+}
+
+/*
+ * Searches for a matching triplet. `commit_pos` is a pointer
+ * to the wanted commit position value. `table_entry` points to
+ * a triplet in lookup table. The first 4 bytes of each
+ * triplet (pointed by `table_entry`) are compared with `*commit_pos`.
+ */
+static int triplet_cmp(const void *commit_pos, const void *table_entry)
+{
+
+	uint32_t a = *(uint32_t *)commit_pos;
+	uint32_t b = get_be32(table_entry);
+	if (a > b)
+		return 1;
+	else if (a < b)
+		return -1;
+
+	return 0;
+}
+
+static uint32_t bitmap_bsearch_pos(struct bitmap_index *bitmap_git,
+			    struct object_id *oid,
+			    uint32_t *result)
+{
+	int found;
+
+	if (bitmap_is_midx(bitmap_git))
+		found = bsearch_midx(oid, bitmap_git->midx, result);
+	else
+		found = bsearch_pack(oid, bitmap_git->pack, result);
+
+	return found;
+}
+
+/*
+ * `bsearch_triplet_by_pos` function searches for the raw triplet
+ * having commit position same as `commit_pos` and fills `triplet`
+ * object from the raw triplet. Returns 1 on success and 0 on
+ * failure.
+ */
+static int bitmap_bsearch_triplet_by_pos(uint32_t commit_pos,
+				  struct bitmap_index *bitmap_git,
+				  struct bitmap_lookup_table_triplet *triplet)
+{
+	unsigned char *p = bsearch(&commit_pos, bitmap_git->table_lookup, bitmap_git->entry_count,
+				   BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH, triplet_cmp);
+
+	if (!p)
+		return -1;
+
+	return bitmap_lookup_table_get_triplet_by_pointer(triplet, p);
+}
+
+static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_git,
+						    struct commit *commit)
+{
+	uint32_t commit_pos, xor_row;
+	uint64_t offset;
+	int flags;
+	struct bitmap_lookup_table_triplet triplet;
+	struct object_id *oid = &commit->object.oid;
+	struct ewah_bitmap *bitmap;
+	struct stored_bitmap *xor_bitmap = NULL;
+	const int bitmap_header_size = 6;
+	static struct bitmap_lookup_table_xor_item *xor_items = NULL;
+	static size_t xor_items_nr = 0, xor_items_alloc = 0;
+	static int is_corrupt = 0;
+	int xor_flags;
+	khiter_t hash_pos;
+	struct bitmap_lookup_table_xor_item *xor_item;
+
+	if (is_corrupt)
+		return NULL;
+
+	if (!bitmap_bsearch_pos(bitmap_git, oid, &commit_pos))
+		return NULL;
+
+	if (bitmap_bsearch_triplet_by_pos(commit_pos, bitmap_git, &triplet) < 0)
+		return NULL;
+
+	xor_items_nr = 0;
+	offset = triplet.offset;
+	xor_row = triplet.xor_row;
+
+	while (xor_row != 0xffffffff) {
+		ALLOC_GROW(xor_items, xor_items_nr + 1, xor_items_alloc);
+
+		if (xor_items_nr + 1 >= bitmap_git->entry_count) {
+			error(_("corrupt bitmap lookup table: xor chain exceed entry count"));
+			goto corrupt;
+		}
+
+		if (bitmap_lookup_table_get_triplet(bitmap_git, xor_row, &triplet) < 0)
+			goto corrupt;
+
+		xor_item = &xor_items[xor_items_nr];
+		xor_item->offset = triplet.offset;
+
+		if (nth_bitmap_object_oid(bitmap_git, &xor_item->oid, triplet.commit_pos) < 0) {
+			error(_("corrupt bitmap lookup table: commit index %u out of range"),
+				triplet.commit_pos);
+			goto corrupt;
+		}
+
+		hash_pos = kh_get_oid_map(bitmap_git->bitmaps, xor_item->oid);
+
+		/*
+		 * If desired bitmap is already stored, we don't need
+		 * to iterate further. Because we know that bitmaps
+		 * that are needed to be parsed to parse this bitmap
+		 * has already been stored. So, assign this stored bitmap
+		 * to the xor_bitmap.
+		 */
+		if (hash_pos < kh_end(bitmap_git->bitmaps) &&
+			(xor_bitmap = kh_value(bitmap_git->bitmaps, hash_pos)))
+			break;
+		xor_items_nr++;
+		xor_row = triplet.xor_row;
+	}
+
+	while (xor_items_nr) {
+		xor_item = &xor_items[xor_items_nr - 1];
+		bitmap_git->map_pos = xor_item->offset;
+		if (bitmap_git->map_size - bitmap_git->map_pos < bitmap_header_size) {
+			error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
+				oid_to_hex(&xor_item->oid));
+			goto corrupt;
+		}
+
+		bitmap_git->map_pos += sizeof(uint32_t) + sizeof(uint8_t);
+		xor_flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
+		bitmap = read_bitmap_1(bitmap_git);
+
+		if (!bitmap)
+			goto corrupt;
+
+		xor_bitmap = store_bitmap(bitmap_git, bitmap, &xor_item->oid, xor_bitmap, xor_flags);
+		xor_items_nr--;
+	}
+
+	bitmap_git->map_pos = offset;
+	if (bitmap_git->map_size - bitmap_git->map_pos < bitmap_header_size) {
+		error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
+			oid_to_hex(oid));
+		goto corrupt;
+	}
+
+	/*
+	 * Don't bother reading the commit's index position or its xor
+	 * offset:
+	 *
+	 *   - The commit's index position is irrelevant to us, since
+	 *     load_bitmap_entries_v1 only uses it to learn the object
+	 *     id which is used to compute the hashmap's key. We already
+	 *     have an object id, so no need to look it up again.
+	 *
+	 *   - The xor_offset is unusable for us, since it specifies how
+	 *     many entries previous to ours we should look at. This
+	 *     makes sense when reading the bitmaps sequentially (as in
+	 *     load_bitmap_entries_v1()), since we can keep track of
+	 *     each bitmap as we read them.
+	 *
+	 *     But it can't work for us, since the bitmap's don't have a
+	 *     fixed size. So we learn the position of the xor'd bitmap
+	 *     from the commit table (and resolve it to a bitmap in the
+	 *     above if-statement).
+	 *
+	 * Instead, we can skip ahead and immediately read the flags and
+	 * ewah bitmap.
+	 */
+	bitmap_git->map_pos += sizeof(uint32_t) + sizeof(uint8_t);
+	flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
+	bitmap = read_bitmap_1(bitmap_git);
+
+	if (!bitmap)
+		goto corrupt;
+
+	return store_bitmap(bitmap_git, bitmap, oid, xor_bitmap, flags);
+
+corrupt:
+	free(xor_items);
+	is_corrupt = 1;
+	return NULL;
+}
+
 struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
 				      struct commit *commit)
 {
 	khiter_t hash_pos = kh_get_oid_map(bitmap_git->bitmaps,
 					   commit->object.oid);
-	if (hash_pos >= kh_end(bitmap_git->bitmaps))
-		return NULL;
+	if (hash_pos >= kh_end(bitmap_git->bitmaps)) {
+		struct stored_bitmap *bitmap = NULL;
+		if (!bitmap_git->table_lookup)
+			return NULL;
+
+		trace2_region_enter("pack-bitmap", "reading_lookup_table", the_repository);
+		/* NEEDSWORK: cache misses aren't recorded */
+		bitmap = lazy_bitmap_for_commit(bitmap_git, commit);
+		trace2_region_leave("pack-bitmap", "reading_lookup_table", the_repository);
+		if (!bitmap)
+			return NULL;
+		return lookup_stored_bitmap(bitmap);
+	}
 	return lookup_stored_bitmap(kh_value(bitmap_git->bitmaps, hash_pos));
 }
 
@@ -1712,8 +1973,10 @@ void test_bitmap_walk(struct rev_info *revs)
 	if (revs->pending.nr != 1)
 		die(_("you must specify exactly one commit to test"));
 
-	fprintf_ln(stderr, "Bitmap v%d test (%d entries loaded)",
-		bitmap_git->version, bitmap_git->entry_count);
+	fprintf_ln(stderr, "Bitmap v%d test (%d entries%s)",
+		bitmap_git->version,
+		bitmap_git->entry_count,
+		bitmap_git->table_lookup ? "" : " loaded");
 
 	root = revs->pending.objects[0].item;
 	bm = bitmap_for_commit(bitmap_git, (struct commit *)root);
@@ -1766,13 +2029,22 @@ void test_bitmap_walk(struct rev_info *revs)
 
 int test_bitmap_commits(struct repository *r)
 {
-	struct bitmap_index *bitmap_git = prepare_bitmap_git(r);
 	struct object_id oid;
 	MAYBE_UNUSED void *value;
+	struct bitmap_index *bitmap_git = prepare_bitmap_git(r);
 
 	if (!bitmap_git)
 		die(_("failed to load bitmap indexes"));
 
+	/*
+	 * As this function is only used to print bitmap selected
+	 * commits, we don't have to read the commit table.
+	 */
+	if (bitmap_git->table_lookup) {
+		if (load_bitmap_entries_v1(bitmap_git) < 0)
+			die(_("failed to load bitmap indexes"));
+	}
+
 	kh_foreach(bitmap_git->bitmaps, oid, value, {
 		printf_ln("%s", oid_to_hex(&oid));
 	});
diff --git a/pack-bitmap.h b/pack-bitmap.h
index f3a57ca065..f0180b5276 100644
--- a/pack-bitmap.h
+++ b/pack-bitmap.h
@@ -23,9 +23,19 @@ struct bitmap_disk_header {
 
 #define NEEDS_BITMAP (1u<<22)
 
+/*
+ * The width in bytes of a single triplet in the lookup table
+ * extension:
+ *     (commit_pos, offset, xor_row)
+ *
+ * whose fields ar 32-, 64-, 32- bits wide, respectively.
+ */
+#define BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH (16)
+
 enum pack_bitmap_opts {
-	BITMAP_OPT_FULL_DAG = 1,
-	BITMAP_OPT_HASH_CACHE = 4,
+	BITMAP_OPT_FULL_DAG = 0x1,
+	BITMAP_OPT_HASH_CACHE = 0x4,
+	BITMAP_OPT_LOOKUP_TABLE = 0x10,
 };
 
 enum pack_bitmap_flags {
diff --git a/t/perf/lib-bitmap.sh b/t/perf/lib-bitmap.sh
index 63d3bc7cec..55a8feb1dc 100644
--- a/t/perf/lib-bitmap.sh
+++ b/t/perf/lib-bitmap.sh
@@ -67,3 +67,34 @@ test_partial_bitmap () {
 			--filter=tree:0 >/dev/null
 	'
 }
+
+test_pack_bitmap () {
+	test_perf "repack to disk" '
+		git repack -ad
+	'
+
+	test_full_bitmap
+
+	test_expect_success "create partial bitmap state" '
+		# pick a commit to represent the repo tip in the past
+		cutoff=$(git rev-list HEAD~100 -1) &&
+		orig_tip=$(git rev-parse HEAD) &&
+
+		# now kill off all of the refs and pretend we had
+		# just the one tip
+		rm -rf .git/logs .git/refs/* .git/packed-refs &&
+		git update-ref HEAD $cutoff &&
+
+		# and then repack, which will leave us with a nice
+		# big bitmap pack of the "old" history, and all of
+		# the new history will be loose, as if it had been pushed
+		# up incrementally and exploded via unpack-objects
+		git repack -Ad &&
+
+		# and now restore our original tip, as if the pushes
+		# had happened
+		git update-ref HEAD $orig_tip
+	'
+
+	test_partial_bitmap
+}
diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh
index 7ad4f237bc..b1399f1007 100755
--- a/t/perf/p5310-pack-bitmaps.sh
+++ b/t/perf/p5310-pack-bitmaps.sh
@@ -4,51 +4,37 @@ test_description='Tests pack performance using bitmaps'
 . ./perf-lib.sh
 . "${TEST_DIRECTORY}/perf/lib-bitmap.sh"
 
-test_perf_large_repo
-
-# note that we do everything through config,
-# since we want to be able to compare bitmap-aware
-# git versus non-bitmap git
-#
-# We intentionally use the deprecated pack.writebitmaps
-# config so that we can test against older versions of git.
-test_expect_success 'setup bitmap config' '
-	git config pack.writebitmaps true
-'
-
-# we need to create the tag up front such that it is covered by the repack and
-# thus by generated bitmaps.
-test_expect_success 'create tags' '
-	git tag --message="tag pointing to HEAD" perf-tag HEAD
-'
-
-test_perf 'repack to disk' '
-	git repack -ad
-'
-
-test_full_bitmap
-
-test_expect_success 'create partial bitmap state' '
-	# pick a commit to represent the repo tip in the past
-	cutoff=$(git rev-list HEAD~100 -1) &&
-	orig_tip=$(git rev-parse HEAD) &&
-
-	# now kill off all of the refs and pretend we had
-	# just the one tip
-	rm -rf .git/logs .git/refs/* .git/packed-refs &&
-	git update-ref HEAD $cutoff &&
-
-	# and then repack, which will leave us with a nice
-	# big bitmap pack of the "old" history, and all of
-	# the new history will be loose, as if it had been pushed
-	# up incrementally and exploded via unpack-objects
-	git repack -Ad &&
-
-	# and now restore our original tip, as if the pushes
-	# had happened
-	git update-ref HEAD $orig_tip
-'
-
-test_partial_bitmap
+test_lookup_pack_bitmap () {
+	test_expect_success 'start the test from scratch' '
+		rm -rf * .git
+	'
+
+	test_perf_large_repo
+
+	# note that we do everything through config,
+	# since we want to be able to compare bitmap-aware
+	# git versus non-bitmap git
+	#
+	# We intentionally use the deprecated pack.writebitmaps
+	# config so that we can test against older versions of git.
+	test_expect_success 'setup bitmap config' '
+		git config pack.writebitmaps true
+	'
+
+	# we need to create the tag up front such that it is covered by the repack and
+	# thus by generated bitmaps.
+	test_expect_success 'create tags' '
+		git tag --message="tag pointing to HEAD" perf-tag HEAD
+	'
+
+	test_perf "enable lookup table: $1" '
+		git config pack.writeBitmapLookupTable '"$1"'
+	'
+
+	test_pack_bitmap
+}
+
+test_lookup_pack_bitmap false
+test_lookup_pack_bitmap true
 
 test_done
diff --git a/t/perf/p5311-pack-bitmaps-fetch.sh b/t/perf/p5311-pack-bitmaps-fetch.sh
index 47c3fd7581..426fab87e3 100755
--- a/t/perf/p5311-pack-bitmaps-fetch.sh
+++ b/t/perf/p5311-pack-bitmaps-fetch.sh
@@ -3,42 +3,52 @@
 test_description='performance of fetches from bitmapped packs'
 . ./perf-lib.sh
 
-test_perf_default_repo
-
-test_expect_success 'create bitmapped server repo' '
-	git config pack.writebitmaps true &&
-	git repack -ad
-'
-
-# simulate a fetch from a repository that last fetched N days ago, for
-# various values of N. We do so by following the first-parent chain,
-# and assume the first entry in the chain that is N days older than the current
-# HEAD is where the HEAD would have been then.
-for days in 1 2 4 8 16 32 64 128; do
-	title=$(printf '%10s' "($days days)")
-	test_expect_success "setup revs from $days days ago" '
-		now=$(git log -1 --format=%ct HEAD) &&
-		then=$(($now - ($days * 86400))) &&
-		tip=$(git rev-list -1 --first-parent --until=$then HEAD) &&
-		{
-			echo HEAD &&
-			echo ^$tip
-		} >revs
+test_fetch_bitmaps () {
+	test_expect_success 'setup test directory' '
+		rm -fr * .git
 	'
 
-	test_perf "server $title" '
-		git pack-objects --stdout --revs \
-				 --thin --delta-base-offset \
-				 <revs >tmp.pack
-	'
+	test_perf_default_repo
 
-	test_size "size   $title" '
-		wc -c <tmp.pack
+	test_expect_success 'create bitmapped server repo' '
+		git config pack.writebitmaps true &&
+		git config pack.writeBitmapLookupTable '"$1"' &&
+		git repack -ad
 	'
 
-	test_perf "client $title" '
-		git index-pack --stdin --fix-thin <tmp.pack
-	'
-done
+	# simulate a fetch from a repository that last fetched N days ago, for
+	# various values of N. We do so by following the first-parent chain,
+	# and assume the first entry in the chain that is N days older than the current
+	# HEAD is where the HEAD would have been then.
+	for days in 1 2 4 8 16 32 64 128; do
+		title=$(printf '%10s' "($days days)")
+		test_expect_success "setup revs from $days days ago" '
+			now=$(git log -1 --format=%ct HEAD) &&
+			then=$(($now - ($days * 86400))) &&
+			tip=$(git rev-list -1 --first-parent --until=$then HEAD) &&
+			{
+				echo HEAD &&
+				echo ^$tip
+			} >revs
+		'
+
+		test_perf "server $title (lookup=$1)" '
+			git pack-objects --stdout --revs \
+					--thin --delta-base-offset \
+					<revs >tmp.pack
+		'
+
+		test_size "size   $title" '
+			wc -c <tmp.pack
+		'
+
+		test_perf "client $title (lookup=$1)" '
+			git index-pack --stdin --fix-thin <tmp.pack
+		'
+	done
+}
+
+test_fetch_bitmaps true
+test_fetch_bitmaps false
 
 test_done
diff --git a/t/perf/p5312-pack-bitmaps-revs.sh b/t/perf/p5312-pack-bitmaps-revs.sh
new file mode 100755
index 0000000000..0684b690af
--- /dev/null
+++ b/t/perf/p5312-pack-bitmaps-revs.sh
@@ -0,0 +1,35 @@
+#!/bin/sh
+
+test_description='Tests pack performance using bitmaps (rev index enabled)'
+. ./perf-lib.sh
+. "${TEST_DIRECTORY}/perf/lib-bitmap.sh"
+
+test_lookup_pack_bitmap () {
+	test_expect_success 'start the test from scratch' '
+		rm -rf * .git
+	'
+
+	test_perf_large_repo
+
+	test_expect_success 'setup bitmap config' '
+		git config pack.writebitmaps true &&
+		git config pack.writeReverseIndex true
+	'
+
+	# we need to create the tag up front such that it is covered by the repack and
+	# thus by generated bitmaps.
+	test_expect_success 'create tags' '
+		git tag --message="tag pointing to HEAD" perf-tag HEAD
+	'
+
+	test_perf "enable lookup table: $1" '
+		git config pack.writeBitmapLookupTable '"$1"'
+	'
+
+	test_pack_bitmap
+}
+
+test_lookup_pack_bitmap false
+test_lookup_pack_bitmap true
+
+test_done
diff --git a/t/perf/p5326-multi-pack-bitmaps.sh b/t/perf/p5326-multi-pack-bitmaps.sh
index f2fa228f16..d082e6cacb 100755
--- a/t/perf/p5326-multi-pack-bitmaps.sh
+++ b/t/perf/p5326-multi-pack-bitmaps.sh
@@ -4,49 +4,64 @@ test_description='Tests performance using midx bitmaps'
 . ./perf-lib.sh
 . "${TEST_DIRECTORY}/perf/lib-bitmap.sh"
 
-test_perf_large_repo
-
-# we need to create the tag up front such that it is covered by the repack and
-# thus by generated bitmaps.
-test_expect_success 'create tags' '
-	git tag --message="tag pointing to HEAD" perf-tag HEAD
-'
-
-test_expect_success 'start with bitmapped pack' '
-	git repack -adb
-'
-
-test_perf 'setup multi-pack index' '
-	git multi-pack-index write --bitmap
-'
-
-test_expect_success 'drop pack bitmap' '
-	rm -f .git/objects/pack/pack-*.bitmap
-'
-
-test_full_bitmap
-
-test_expect_success 'create partial bitmap state' '
-	# pick a commit to represent the repo tip in the past
-	cutoff=$(git rev-list HEAD~100 -1) &&
-	orig_tip=$(git rev-parse HEAD) &&
-
-	# now pretend we have just one tip
-	rm -rf .git/logs .git/refs/* .git/packed-refs &&
-	git update-ref HEAD $cutoff &&
-
-	# and then repack, which will leave us with a nice
-	# big bitmap pack of the "old" history, and all of
-	# the new history will be loose, as if it had been pushed
-	# up incrementally and exploded via unpack-objects
-	git repack -Ad &&
-	git multi-pack-index write --bitmap &&
-
-	# and now restore our original tip, as if the pushes
-	# had happened
-	git update-ref HEAD $orig_tip
-'
-
-test_partial_bitmap
+test_bitmap () {
+	local enabled="$1"
+
+	test_expect_success "remove existing repo (lookup=$enabled)" '
+		rm -fr * .git
+	'
+
+	test_perf_large_repo
+
+	# we need to create the tag up front such that it is covered by the repack and
+	# thus by generated bitmaps.
+	test_expect_success 'create tags' '
+		git tag --message="tag pointing to HEAD" perf-tag HEAD
+	'
+
+	test_expect_success "use lookup table: $enabled" '
+		git config pack.writeBitmapLookupTable '"$enabled"'
+	'
+
+	test_expect_success "start with bitmapped pack (lookup=$enabled)" '
+		git repack -adb
+	'
+
+	test_perf "setup multi-pack index (lookup=$enabled)" '
+		git multi-pack-index write --bitmap
+	'
+
+	test_expect_success "drop pack bitmap (lookup=$enabled)" '
+		rm -f .git/objects/pack/pack-*.bitmap
+	'
+
+	test_full_bitmap
+
+	test_expect_success "create partial bitmap state (lookup=$enabled)" '
+		# pick a commit to represent the repo tip in the past
+		cutoff=$(git rev-list HEAD~100 -1) &&
+		orig_tip=$(git rev-parse HEAD) &&
+
+		# now pretend we have just one tip
+		rm -rf .git/logs .git/refs/* .git/packed-refs &&
+		git update-ref HEAD $cutoff &&
+
+		# and then repack, which will leave us with a nice
+		# big bitmap pack of the "old" history, and all of
+		# the new history will be loose, as if it had been pushed
+		# up incrementally and exploded via unpack-objects
+		git repack -Ad &&
+		git multi-pack-index write --bitmap &&
+
+		# and now restore our original tip, as if the pushes
+		# had happened
+		git update-ref HEAD $orig_tip
+	'
+
+	test_partial_bitmap
+}
+
+test_bitmap false
+test_bitmap true
 
 test_done
diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
index f775fc1ce6..7e50f8e765 100755
--- a/t/t5310-pack-bitmaps.sh
+++ b/t/t5310-pack-bitmaps.sh
@@ -26,22 +26,415 @@ 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 &&
+		test_config pack.writebitmaplookuptable 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 config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
+		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,219 +447,24 @@ 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_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_bitmap_cases "pack.writeBitmapLookupTable"
 
-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 'verify writing bitmap lookup table when enabled' '
+	GIT_TRACE2_EVENT="$(pwd)/trace2" \
+		git repack -ad &&
+	grep "\"label\":\"writing_lookup_table\"" trace2
 '
 
-test_expect_success 'set up reusable pack' '
-	rm -f .git/objects/pack/*.keep &&
+test_expect_success 'lookup table is actually used to traverse objects' '
 	git repack -adb &&
-	reusable_pack () {
-		git for-each-ref --format="%(objectname)" |
-		git pack-objects --delta-base-offset --revs --stdout "$@"
-	}
+	GIT_TRACE2_EVENT="$(pwd)/trace3" \
+		git rev-list --use-bitmap-index --count --all &&
+	grep "\"label\":\"reading_lookup_table\"" trace3
 '
 
-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_expect_success 'truncated bitmap fails gracefully (lookup table)' '
 	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 repack -adb &&
 	git rev-list --use-bitmap-index --count --all >expect &&
 	bitmap=$(ls .git/objects/pack/*.bitmap) &&
 	test_when_finished "rm -f $bitmap" &&
@@ -277,152 +475,4 @@ test_expect_success 'truncated bitmap fails gracefully (cache)' '
 	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_done
diff --git a/t/t5311-pack-bitmaps-shallow.sh b/t/t5311-pack-bitmaps-shallow.sh
index 872a95df33..9dae60f73e 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 89ecd1062c..ad6eea5fa0 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 &&
+
+			(
+				grep -vf before commits.raw &&
+				# mark missing commits as preferred
+				sed "s/^/+/" before
+			) >snapshot &&
 
-		test-tool bitmap list-commits | sort >bitmaps &&
-		comm -13 bitmaps commits >before &&
-		test_line_count = 1 before &&
+			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
+		)
+	'
 
-		empty="$(git pack-objects $objdir/pack/pack </dev/null)" &&
-		cat >packs <<-EOF &&
-		pack-$empty.idx
-		EOF
+	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"' &&
 
-		git multi-pack-index write --bitmap --stdin-packs \
-			<packs 2>err &&
+			test_commit base &&
 
-		grep "bitmap without any objects" err &&
+			# write a pack and MIDX bitmap containing base
+			git repack -adb &&
+			git multi-pack-index write --bitmap &&
 
-		test_path_is_file $midx &&
-		test_path_is_missing $midx-$(midx_checksum $objdir).bitmap
-	)
-'
+			GIT_TEST_MIDX_READ_RIDX=0 \
+				git rev-list --use-bitmap-index HEAD 2>err &&
+			! grep "ignoring extra bitmap file" err
+		)
+	'
+}
+
+test_midx_bitmap_cases
 
-test_expect_success 'graceful fallback when missing reverse index' '
+test_midx_bitmap_cases "pack.writeBitmapLookupTable"
+
+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 d30ba632c8..e65e311cd7 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