pack-bitmap: fix memory leak if `load_bitmap_entries_v1` failed

From: Lidong Yan <[email protected]>

In pack-bitmap.c:load_bitmap_entries_v1, the function read_bitmap_1 allocates a bitmap and reads index data into it. However, if any of the validation checks following the allocation fail, the allocated bitmap is not freed, resulting in a memory leak. To avoid this, the validation checks should be performed before the bitmap is allocated.

Quoted 7 lines · Lidong Yan via GitGitGadget

From: Lidong Yan <[email protected]>

In pack-bitmap.c:load_bitmap_entries_v1, the function read_bitmap_1 allocates a bitmap and reads index data into it. However, if any of the validation checks following the allocation fail, the allocated bitmap is not freed, resulting in a memory leak. To avoid this, the validation checks should be performed before the bitmap is allocated.

Thanks, this looks correct to me.

Quoted 4 lines

(quoted diff) +0 -0

@@ -388,10 +388,6 @@ static int load_bitmap_entries_v1(struct bitmap_index *index)
 			return error(_("corrupt ewah bitmap: commit index %u out of range"),
 				     (unsigned)commit_idx_pos);
 

Review static int load_bitmap_entries_v1(struct bitmap_index *index) · line 392

Quoted 6 lines

(quoted diff) +0 -4

-		bitmap = read_bitmap_1(index);
-		if (!bitmap)
-			return -1;
-
 		if (xor_offset > MAX_XOR_OFFSET || xor_offset > i)
 			return error(_("corrupted bitmap pack index"));

I noticed that this code is also within a loop, so we could still return early on the next loop iteration. But by that point we will have called store_bitmap() on the result, so we only have to worry about leaking the bitmap from the current loop iteration.

After going through the "failed" label, load_bitmap() will return -1, and its caller (either prepare_bitmap_walk() or prepare_bitmap_git()) will then call free_bitmap_index().

That function would have done:

    struct stored_bitmap *sb;
    kh_foreach_value(b->bitmaps, sb {
      ewah_pool_free(sb->root);
      free(sb);
    });

, but won't since load_bitmap() already called kh_destroy_oid_map() and NULL'd the "bitmaps" pointer from within its "failed" label.

So I think if you got part of the way through loading bitmap entries and then failed, you would leak all of the previous entries that you were able to load successfully.

I suspect the fix looks something like:
...
--- 8< ---

pack-bitmap.c +0 -0

index 5299f49d59..7f28532a69 100644

pack-bitmap.c +0 -13

-failed:
-	munmap(bitmap_git->map, bitmap_git->map_size);
-	bitmap_git->map = NULL;
-	bitmap_git->map_size = 0;
-
-	kh_destroy_oid_map(bitmap_git->bitmaps);
-	bitmap_git->bitmaps = NULL;
-
-	kh_destroy_oid_pos(bitmap_git->ext_index.positions);
-	bitmap_git->ext_index.positions = NULL;
-
-	return -1;
 }
 
 static int open_pack_bitmap(struct repository *r,
--- >8 ---
 

, since all callers of load_bitmap() will themselves call free_bitmap_index(), so there is no need for us to open-code a portion of that function's implementation ourselves.

Quoted 7 lines

Quoted 5 lines

In pack-bitmap.c:load_bitmap_entries_v1, the function read_bitmap_1 allocates a bitmap and reads index data into it. However, if any of the validation checks following the allocation fail, the allocated bitmap is not freed, resulting in a memory leak. To avoid this, the validation checks should be performed before the bitmap is allocated.

Thanks, this looks correct to me.

It looks correct to me as well, and is a strict improvement. But I think there is a leak outside of this function as well that is not touched by this patch.

I suspect the fix looks something like:
[...]
, since all callers of load_bitmap() will themselves call free_bitmap_index(), so there is no need for us to open-code a portion of that function's implementation ourselves.

It would be nice if we triggered these cases in the test suite so that LSan could confirm that all leaks are covered. But I suspect it may not be worth the effort to craft a bitmap file that is broken in such particular ways.

Signed-off-by Taylor Blau <[email protected]>

Quoted 1 line · Taylor Blau via GitGitGadget

Signed-off-by Taylor Blau <[email protected]>

This commit forges my Signed-off-by, but I am happy with the result here.

I do think the series is structured a little awkwardly as a result of adding this patch to it. That this and the previous patch have the subject "pack-bitmap: fix memory leak if load_bitmap_entries_v1 failed" make the series not quite as clear as it could be.

I think there are a couple of things going on:

- This patch is a bug fix that could be applied independently of the first one. The rationale there would be that we shouldn't be leaking the EWAH bitmaps in 'b->bitmaps', but we are as a result of NULL'ing the pointer in the "failed" label. That patch can stand alone.

- The first patch (yours) is no longer fixing a leak, at least after this patch. But it does delay reading the bitmap until we have validated its XOR offset for sanity, which is a good thing mostly from a performance perspective.

I would probably swap the two patches around so that yours applies on top of mine, and then rewords the patch message in yours to reflect that it is no longer fixing a leak.

That all said, if you feel strongly that the structure is fine/better as-is, I'd be more than happy to discuss it further.

Thanks,
Taylor

Quoted 1 line · Taylor Blau via GitGitGadget

Signed-off-by Taylor Blau <[email protected]>

This commit forges my Signed-off-by, but I am happy with the result here.

I do think the series is structured a little awkwardly as a result of adding this patch to it. That this and the previous patch have the subject "pack-bitmap: fix memory leak if load_bitmap_entries_v1 failed" make the series not quite as clear as it could be.

I think there are a couple of things going on:

- This patch is a bug fix that could be applied independently of the first one. The rationale there would be that we shouldn't be leaking the EWAH bitmaps in 'b->bitmaps', but we are as a result of NULL'ing the pointer in the "failed" label. That patch can stand alone.

- The first patch (yours) is no longer fixing a leak, at least after this patch. But it does delay reading the bitmap until we have validated its XOR offset for sanity, which is a good thing mostly from a performance perspective.

I would probably swap the two patches around so that yours applies on top of mine, and then rewords the patch message in yours to reflect that it is no longer fixing a leak.

From: Lidong Yan <[email protected]>

This patch add "load corrupt bitmap" test case in t5310-pack-bitmaps.sh.

This test case intentionally corrupt the "xor_offset" field of the first entry. To find position of first entry in *.bitmap, we need to skip 4 ewah_bitmaps before entries. And I add a function skip_ewah_bitmap() to do this.

Signed-off-by Lidong Yan <[email protected]>

---
 t/t5310-pack-bitmaps.sh | 50 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 50 insertions(+)

t/t5310-pack-bitmaps.sh +12 -0

index a62b463eaf09..537a507957bb 100755
@@ -26,6 +26,18 @@ has_any () {
 	grep -Ff "$1" "$2"
 }
 
+skip_ewah_bitmap() {
+	local bitmap="$1" &&
+	local offset="$2" &&
+	local size= &&
+
+	offset=$(($offset + 4)) &&
+	size=0x$(od -An -v -t x1 -j $offset -N 4 $bitmap | tr -d ' \n') &&
+	size=$(($size * 8)) &&
+	offset=$(($offset + 4 + $size + 4)) &&
+	echo $offset
+}
+
 # Since name-hash values are stored in the .bitmap files, add a test
 # that checks that the name-hash calculations are stable across versions.
 # Not exhaustive, but these hashing algorithms would be hard to change

@@ -486,6 +498,44 @@ test_bitmap_cases () {
 			grep "ignoring extra bitmap" trace2.txt
 		)
 	'

Quoted 8 lines · Lidong Yan via GitGitGadget

From: Lidong Yan <[email protected]>

This patch add "load corrupt bitmap" test case in t5310-pack-bitmaps.sh.

This test case intentionally corrupt the "xor_offset" field of the first entry. To find position of first entry in *.bitmap, we need to skip 4 ewah_bitmaps before entries. And I add a function skip_ewah_bitmap() to do this.

I'm going to avoid commenting on the message itself, since I think we may be able to drop this patch entirely, see below.

Quoted 34 lines

Signed-off-by Lidong Yan <[email protected]>

---
t/t5310-pack-bitmaps.sh | 50 +++++++++++++++++++++++++++++++++++++++++

1 file changed, 50 insertions(+)

t/t5310-pack-bitmaps.sh +0 -0

index a62b463eaf09..537a507957bb 100755
@@ -26,6 +26,18 @@ has_any () {

grep -Ff "$1" "$2"
}

t/t5310-pack-bitmaps.sh +12 -0

+skip_ewah_bitmap() {
+ local bitmap="$1" &&
+ local offset="$2" &&
+ local size= &&
+
+ offset=$(($offset + 4)) &&
+ size=0x$(od -An -v -t x1 -j $offset -N 4 $bitmap | tr -d ' \n') &&
+ size=$(($size * 8)) &&
+ offset=$(($offset + 4 + $size + 4)) &&
+ echo $offset
+}
+

# Since name-hash values are stored in the .bitmap files, add a test

# that checks that the name-hash calculations are stable across versions.
# Not exhaustive, but these hashing algorithms would be hard to change

t/t5310-pack-bitmaps.sh +0 -0

@@ -486,6 +498,44 @@ test_bitmap_cases () {

grep "ignoring extra bitmap" trace2.txt
)
'
+
+ # A .bitmap file has the following structure:

Quoted 8 lines

+ # | Header | Commits | Trees | Blobs | Tags | Entries... |
+ #
+ # - The header is 32 bytes long when using SHA-1.
+ # - Commits, Trees, Blobs, and Tags are all stored as EWAH bitmaps.
+ #
+ # This test intentionally corrupts the xor_offset field of the first entry
+ # to verify robustness against malformed bitmap data.
+ test_expect_success 'load corrupt bitmap' '

I am not totally following what this case is supposed to be testing. Let me think aloud for a moment...

Quoted 6 lines

+ rm -fr repo &&
+ git init repo &&
+ test_when_finished "rm -fr repo" &&
+ (
+ cd repo &&
+ git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&

First we set up a temporary repository, change into it, and enable bitmap lookup tables. Makes sense.

Quoted 5 lines

+ test_commit base &&
+
+ git repack -adb &&
+ bitmap="$(ls .git/objects/pack/pack-*.bitmap)" &&
+ chmod +w "$bitmap" &&

Then we make a commit, and write a bitmap containing the objects from the commit we just made. Good.

Quoted 5 lines

+ hdr_sz=$((12 + $(test_oid rawsz))) &&
+ offset=$(skip_ewah_bitmap $bitmap $hdr_sz) &&
+ offset=$(skip_ewah_bitmap $bitmap $offset) &&
+ offset=$(skip_ewah_bitmap $bitmap $offset) &&
+ offset=$(skip_ewah_bitmap $bitmap $offset) &&

Then we read past the header and four type bitmaps. Makes sense.

Quoted 1 line

+ offset=$((offset + 4)) &&

Now we land at the bitmap for the commit we just wrote.

(As an aside unrelated to this part of the test, this skip_ewah_bitmap() function seems awfully fragile. I wonder if it would make more sense to implement this as a test helper that can dump the offsets of EWAH bitmaps in a *.bitmap file by object ID rather than trying to parse the file ourselves?

We don't currently store an offset for each stored_bitmap that we maintain, but doing so would be pretty straightforward (add it as a field to the structure, and store the value of bitmap_git->map_pos from immediately before reading the actual bitmap).)

Quoted 2 lines

+ printf '\161' |
+ dd of=$bitmap count=1 bs=1 conv=notrunc seek=$offset &&

OK. Now we break the XOR offset field of this bitmap by writing garbage into it.

Quoted 3 lines

+ git rev-list --count HEAD > expect &&
+ git rev-list --use-bitmap-index --count HEAD > actual &&
+ test_cmp expect actual

...and then we make sure that we still get the correct result.

Hmmph. I don't think this is quite testing what we want, since this test passes with or without your first patch. And that makes sense, we have tests elsewhere in this script that verify we can still fall back to classic traversal when the bitmap index can't be read. (For some examples, see: "truncated bitmap fails gracefully (ewah)" and "truncated bitmap fails gracefully (cache)".)

I think what we're really testing here is the absence of a memory leak, which we are as of 1fc7ddf35b (test-lib: unconditionally enable leak checking, 2024-11-20). I wonder whether or not we need this test at all?

Thanks,
Taylor

Quoted 6 lines

(As an aside unrelated to this part of the test, this skip_ewah_bitmap() function seems awfully fragile. I wonder if it would make more sense to implement this as a test helper that can dump the offsets of EWAH bitmaps in a *.bitmap file by object ID rather than trying to parse the file ourselves?

I am actually replaying the pack-bitmap.c:prepare_bitmap() here. Also I have had write a test helper version once. And since I want to use prepare_bitmap() I have to put the code in pack-bitmap.c. It looks like this

pack-bitmap.c +0 -0

index b9f1d866046..9642a06b3fe 100644

Quoted 6 lines

Hmmph. I don't think this is quite testing what we want, since this test passes with or without your first patch. And that makes sense, we have tests elsewhere in this script that verify we can still fall back to classic traversal when the bitmap index can't be read. (For some examples, see: "truncated bitmap fails gracefully (ewah)" and "truncated bitmap fails gracefully (cache)".)

I want to *test* for a memory leak here, not whether git can load a corrupt bitmap. Since git ci linux-leak test runs each test script with ASAN_OPTIONS=detect_leaks=1, I’m including this test case specifically to check whether it triggers a crash when SANITIZE_LEAK is enabled. And I do find if without the first patch, leak sanitizer running this test script would output error message.

Quoted 6 lines

I think what we're really testing here is the absence of a memory leak, which we are as of 1fc7ddf35b (test-lib: unconditionally enable leak checking, 2024-11-20). I wonder whether or not we need this test at all?

Thanks,
Taylor

I am not truly following what are you talking here. But If you think it’s unnecessary to check for potential leaks in load_bitmap() or load_bitmap_entries_v1(). Or this test script shouldn’t be put in this way. I’m happy to drop the final patch.

But the (elided) code below isn't quite what I was thinking. I think the "write garbage data" part is fine as-is and can continue to be written in shell. We have lots of examples of using dd to write garbage data into files (see for e.g., the "corrupt_data()" function in t5319).

What I was thinking is the test helper would print (via some new mode, or bolted onto "list-commits") line-delimited output like the following:

$COMMIT_OID $BITMAP_OFFSET $FLAGS $XOR_OFFSET

or similar. Then you could use the output of that to determine the location (replacing everything up to the actual "printf | dd of=$bitmap ...", which is the most fragile in my opinion).

I think the above scenario (writing a test that would have leaked memory otherwise behind a SANITIZE_LEAK prerequisite) is reasonable.

From: Taylor Blau <[email protected]>

After going through the "failed" label, load_bitmap() will return -1, and its caller (either prepare_bitmap_walk() or prepare_bitmap_git()) will then call free_bitmap_index().
...
The solution is to remove the error handling code in load_bitmap(), because its caller will always call free_bitmap_index() in case of an error.

Signed-off-by Taylor Blau <[email protected]>

---

Quoted 9 lines · Taylor Blau via GitGitGadget

From: Taylor Blau <[email protected]>

After going through the "failed" label, load_bitmap() will return -1, and its caller (either prepare_bitmap_walk() or prepare_bitmap_git()) will then call free_bitmap_index().
...
The solution is to remove the error handling code in load_bitmap(), because its caller will always call free_bitmap_index() in case of an error.

Quoted 2 lines

Signed-off-by Taylor Blau <[email protected]>

---

As this is Lidong relaying <[email protected]> that Taylor sent to the list, shouldn't Lidong's sign-off be after Taylor's?

In c11c3b5681 (Documentation/SubmittingPatches: What's Acked-by and Tested-by?, 2008-02-03) you added:

Notice that you can place your own Signed-off-by: line when forwarding somebody else's patch [...]. Indeed you are encouraged to do so. [...]

and that text survives into the current version of SubmittingPatches. So I think that while our documentation encourages people to add their own S-o-b to others' patches sent on their behalf, it doesn't explicitly require it.

2025年5月29日 23:33，Junio C Hamano <[email protected]> 写道：

Quoted 11 lines · Taylor Blau via GitGitGadget

From: Taylor Blau <[email protected]>

After going through the "failed" label, load_bitmap() will return -1, and its caller (either prepare_bitmap_walk() or prepare_bitmap_git()) will then call free_bitmap_index().
...
The solution is to remove the error handling code in load_bitmap(), because its caller will always call free_bitmap_index() in case of an error.

Signed-off-by Taylor Blau <[email protected]>

---

As this is Lidong relaying <[email protected]> that Taylor sent to the list, shouldn't Lidong's sign-off be after Taylor's?

From: Lidong Yan <[email protected]>

This patch add test_bitmap_list_commits_offset() in patch-bitmap.c,

a new test helper command test-tool bitmap list-commits-offset, and a load corrupt bitmap test case in t5310.

The load corrupt bitmap test case intentionally corrupt the "xor_offset" field of the first entry. And the newly added helper can help to find position of "xor_offset" in bitmap file.

Signed-off-by Lidong Yan <[email protected]>

---
 pack-bitmap.c           | 73 +++++++++++++++++++++++++++++++++++++----
 pack-bitmap.h           |  1 +
 t/helper/test-bitmap.c  |  8 +++++
 t/t5310-pack-bitmaps.sh | 27 +++++++++++++++
 4 files changed, 103 insertions(+), 6 deletions(-)

pack-bitmap.c +67 -6

index fd19c2255163..39c1c1bc4ce1 100644
@@ -34,6 +34,11 @@ struct stored_bitmap {
 	int flags;
 };
 
+struct stored_bitmap_tag_pos {
+	struct stored_bitmap stored;
+	size_t map_pos;
+};
+
 /*
  * The active bitmap index for a repository. By design, repositories only have
  * a single bitmap index available (the index for the biggest packfile in

@@ -148,6 +153,7 @@ static int existing_bitmaps_hits_nr;
 static int existing_bitmaps_misses_nr;
 static int roots_with_bitmaps_nr;
 static int roots_without_bitmaps_nr;
+static int tag_pos_on_bitmap;
 
 static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
 {

@@ -314,13 +320,18 @@ static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
 					  struct ewah_bitmap *root,
 					  const struct object_id *oid,
 					  struct stored_bitmap *xor_with,
-					  int flags)
+					  int flags, size_t map_pos)
 {
 	struct stored_bitmap *stored;
+	struct stored_bitmap_tag_pos *tagged;
 	khiter_t hash_pos;
 	int ret;
 
-	stored = xmalloc(sizeof(struct stored_bitmap));
+	tagged = xmalloc(tag_pos_on_bitmap ? sizeof(struct stored_bitmap_tag_pos) :
+					     sizeof(struct stored_bitmap));
+	stored = &tagged->stored;
+	if (tag_pos_on_bitmap)
+		tagged->map_pos = map_pos;
 	stored->root = root;
 	stored->xor = xor_with;
 	stored->flags = flags;

@@ -376,10 +387,12 @@ static int load_bitmap_entries_v1(struct bitmap_index *index)
 		struct stored_bitmap *xor_bitmap = NULL;
 		uint32_t commit_idx_pos;
 		struct object_id oid;
+		size_t entry_map_pos;
 
 		if (index->map_size - index->map_pos < 6)
 			return error(_("corrupt ewah bitmap: truncated header for entry %d"), i);
 
+		entry_map_pos = index->map_pos;
 		commit_idx_pos = read_be32(index->map, &index->map_pos);
 		xor_offset = read_u8(index->map, &index->map_pos);
 		flags = read_u8(index->map, &index->map_pos);

@@ -402,8 +415,9 @@ static int load_bitmap_entries_v1(struct bitmap_index *index)
 		if (!bitmap)
 			return -1;
 
-		recent_bitmaps[i % MAX_XOR_OFFSET] = store_bitmap(
-			index, bitmap, &oid, xor_bitmap, flags);
+		recent_bitmaps[i % MAX_XOR_OFFSET] =
+			store_bitmap(index, bitmap, &oid, xor_bitmap, flags,
+				     entry_map_pos);
 	}
 
 	return 0;

@@ -869,6 +883,7 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 	int xor_flags;
 	khiter_t hash_pos;
 	struct bitmap_lookup_table_xor_item *xor_item;
+	size_t entry_map_pos;
 
 	if (is_corrupt)
 		return NULL;

@@ -928,6 +943,7 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 			goto corrupt;
 		}
 
+		entry_map_pos = bitmap_git->map_pos;
 		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);

@@ -935,7 +951,8 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 		if (!bitmap)
 			goto corrupt;
 
-		xor_bitmap = store_bitmap(bitmap_git, bitmap, &xor_item->oid, xor_bitmap, xor_flags);
+		xor_bitmap = store_bitmap(bitmap_git, bitmap, &xor_item->oid,
+					  xor_bitmap, xor_flags, entry_map_pos);
 		xor_items_nr--;
 	}
 

@@ -969,6 +986,7 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 	 * Instead, we can skip ahead and immediately read the flags and
 	 * ewah bitmap.
 	 */
+	entry_map_pos = bitmap_git->map_pos;
 	bitmap_git->map_pos += sizeof(uint32_t) + sizeof(uint8_t);
 	flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
 	bitmap = read_bitmap_1(bitmap_git);

@@ -976,7 +994,8 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 	if (!bitmap)
 		goto corrupt;
 
-	return store_bitmap(bitmap_git, bitmap, oid, xor_bitmap, flags);
+	return store_bitmap(bitmap_git, bitmap, oid, xor_bitmap, flags,
+			    entry_map_pos);
 
 corrupt:
 	free(xor_items);

@@ -2856,6 +2875,48 @@ int test_bitmap_commits(struct repository *r)
 	return 0;
 }
 
+int test_bitmap_commits_offset(struct repository *r)
+{
+	struct object_id oid;
+	struct stored_bitmap_tag_pos *tagged;
+	struct bitmap_index *bitmap_git;
+	size_t commit_idx_pos_map_pos, xor_offset_map_pos, flag_map_pos,
+		ewah_bitmap_map_pos;
+
+	tag_pos_on_bitmap = 1;
+	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, tagged, {
+		commit_idx_pos_map_pos = tagged->map_pos;
+		xor_offset_map_pos = tagged->map_pos + sizeof(uint32_t);
+		flag_map_pos = xor_offset_map_pos + sizeof(uint8_t);
+		ewah_bitmap_map_pos = flag_map_pos + sizeof(uint8_t);
+
+		printf_ln("%s %"PRIuMAX" %"PRIuMAX" %"PRIuMAX" %"PRIuMAX,
+			  oid_to_hex(&oid),
+			  (uintmax_t)commit_idx_pos_map_pos,
+			  (uintmax_t)xor_offset_map_pos,
+			  (uintmax_t)flag_map_pos,
+			  (uintmax_t)ewah_bitmap_map_pos);
+	})
+		;
+
+	free_bitmap_index(bitmap_git);
+
+	return 0;
+}
+
 int test_bitmap_hashes(struct repository *r)
 {
 	struct bitmap_index *bitmap_git = prepare_bitmap_git(r);

pack-bitmap.h +1 -0

index 382d39499af2..96880ba3d72d 100644
@@ -81,6 +81,7 @@ void traverse_bitmap_commit_list(struct bitmap_index *,
 				 show_reachable_fn show_reachable);
 void test_bitmap_walk(struct rev_info *revs);
 int test_bitmap_commits(struct repository *r);
+int test_bitmap_commits_offset(struct repository *r);
 int test_bitmap_hashes(struct repository *r);
 int test_bitmap_pseudo_merges(struct repository *r);
 int test_bitmap_pseudo_merge_commits(struct repository *r, uint32_t n);

t/helper/test-bitmap.c +8 -0

index 3f23f2107268..65a1ab29192b 100644
@@ -10,6 +10,11 @@ static int bitmap_list_commits(void)
 	return test_bitmap_commits(the_repository);
 }
 
+static int bitmap_list_commits_offset(void)
+{
+	return test_bitmap_commits_offset(the_repository);
+}
+
 static int bitmap_dump_hashes(void)
 {
 	return test_bitmap_hashes(the_repository);

@@ -36,6 +41,8 @@ int cmd__bitmap(int argc, const char **argv)
 
 	if (argc == 2 && !strcmp(argv[1], "list-commits"))
 		return bitmap_list_commits();
+	if (argc == 2 && !strcmp(argv[1], "list-commits-offset"))
+		return bitmap_list_commits_offset();
 	if (argc == 2 && !strcmp(argv[1], "dump-hashes"))
 		return bitmap_dump_hashes();
 	if (argc == 2 && !strcmp(argv[1], "dump-pseudo-merges"))

@@ -46,6 +53,7 @@ int cmd__bitmap(int argc, const char **argv)
 		return bitmap_dump_pseudo_merge_objects(atoi(argv[2]));
 
 	usage("\ttest-tool bitmap list-commits\n"
+	      "\ttest-tool bitmap list-commits-offset\n"
 	      "\ttest-tool bitmap dump-hashes\n"
 	      "\ttest-tool bitmap dump-pseudo-merges\n"
 	      "\ttest-tool bitmap dump-pseudo-merge-commits <n>\n"

t/t5310-pack-bitmaps.sh +27 -0

index a62b463eaf09..ef4c5fbaae83 100755
@@ -486,6 +486,33 @@ test_bitmap_cases () {
 			grep "ignoring extra bitmap" trace2.txt
 		)
 	'
+
+	test_expect_success 'load corrupt bitmap' '
+		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)" &&
+			chmod +w $bitmap &&
+
+			read oid commit_off xor_off flag_off ewah_off <<-EOF &&
+				$(test-tool bitmap list-commits-offset | head -n 1)
+			EOF
+			printf '\161' |
+				dd of=$bitmap count=1 bs=1 conv=notrunc seek=$xor_off &&
+
+
+			git rev-list --count HEAD > expect &&
+			git rev-list --use-bitmap-index --count HEAD > actual &&
+			test_cmp expect actual
+		)
+	'
 }
 
 test_bitmap_cases

Quoted 7 lines

Signed-off-by Lidong Yan <[email protected]>

---
 pack-bitmap.c           | 73 +++++++++++++++++++++++++++++++++++++----
 pack-bitmap.h           |  1 +
 t/helper/test-bitmap.c  |  8 +++++
 t/t5310-pack-bitmaps.sh | 27 +++++++++++++++
 4 files changed, 103 insertions(+), 6 deletions(-)

After the second round of the series, no review comments seem to have been sent to the list. Is everybody happy with the latest iteration?

2025年5月29日 23:45，Junio C Hamano <[email protected]> 写道：

Quoted 3 lines · Lidong Yan via GitGitGadget

From: Lidong Yan <[email protected]>

This patch add test_bitmap_list_commits_offset() in patch-bitmap.c,

"pack-bitmap.c"?

Quoted 6 lines

a new test helper command test-tool bitmap list-commits-offset, and a load corrupt bitmap test case in t5310.

The load corrupt bitmap test case intentionally corrupt the "xor_offset" field of the first entry. And the newly added helper can help to find position of "xor_offset" in bitmap file.

[the structure of a log message]

The usual way to compose a log message of this project is to

- Give an observation on how the current system works in the present tense (so no need to say "Currently X is Y", or "Previously X was Y" to describe the state before your change; just "X is Y" is enough), and discuss what you perceive as a problem in it.

- Propose a solution (optional---often, problem description trivially leads to an obvious solution in reader's minds).

- Give commands to somebody editing the codebase to "make it so".

in this order.

The proposed log message lacks the motivation and only talks about what the patch does. We add a test-only code in a file, intermixed with production code. Let's explain why it is the best arrangement.

Quoted 8 lines

Signed-off-by Lidong Yan <[email protected]>

---

pack-bitmap.c           | 73 +++++++++++++++++++++++++++++++++++++----
pack-bitmap.h           |  1 +
t/helper/test-bitmap.c  |  8 +++++
t/t5310-pack-bitmaps.sh | 27 +++++++++++++++
4 files changed, 103 insertions(+), 6 deletions(-)

After the second round of the series, no review comments seem to have been sent to the list. Is everybody happy with the latest iteration?

Thanks.

Quoted 246 lines

pack-bitmap.c +25 -6

index fd19c2255163..39c1c1bc4ce1 100644
@@ -34,6 +34,11 @@ struct stored_bitmap {
 int flags;
 };
 
+struct stored_bitmap_tag_pos {
+ struct stored_bitmap stored;
+ size_t map_pos;
+};
+
 /*
 * The active bitmap index for a repository. By design, repositories only have
 * a single bitmap index available (the index for the biggest packfile in

@@ -148,6 +153,7 @@ static int existing_bitmaps_hits_nr;
 static int existing_bitmaps_misses_nr;
 static int roots_with_bitmaps_nr;
 static int roots_without_bitmaps_nr;
+static int tag_pos_on_bitmap;
 
 static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
 {

@@ -314,13 +320,18 @@ static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
 struct ewah_bitmap *root,
 const struct object_id *oid,
 struct stored_bitmap *xor_with,
-  int flags)
+  int flags, size_t map_pos)
 {
 struct stored_bitmap *stored;
+ struct stored_bitmap_tag_pos *tagged;
 khiter_t hash_pos;
 int ret;
 
- stored = xmalloc(sizeof(struct stored_bitmap));
+ tagged = xmalloc(tag_pos_on_bitmap ? sizeof(struct stored_bitmap_tag_pos) :
+     sizeof(struct stored_bitmap));
+ stored = &tagged->stored;
+ if (tag_pos_on_bitmap)
+ tagged->map_pos = map_pos;
 stored->root = root;
 stored->xor = xor_with;
 stored->flags = flags;

@@ -376,10 +387,12 @@ static int load_bitmap_entries_v1(struct bitmap_index *index)
 struct stored_bitmap *xor_bitmap = NULL;
 uint32_t commit_idx_pos;
 struct object_id oid;
+ size_t entry_map_pos;
 
 if (index->map_size - index->map_pos < 6)
 return error(_("corrupt ewah bitmap: truncated header for entry %d"), i);
 
+ entry_map_pos = index->map_pos;
 commit_idx_pos = read_be32(index->map, &index->map_pos);
 xor_offset = read_u8(index->map, &index->map_pos);
 flags = read_u8(index->map, &index->map_pos);

@@ -402,8 +415,9 @@ static int load_bitmap_entries_v1(struct bitmap_index *index)
 if (!bitmap)
 return -1;
 
- recent_bitmaps[i % MAX_XOR_OFFSET] = store_bitmap(
- index, bitmap, &oid, xor_bitmap, flags);
+ recent_bitmaps[i % MAX_XOR_OFFSET] =
+ store_bitmap(index, bitmap, &oid, xor_bitmap, flags,
+     entry_map_pos);
 }
 
 return 0;

@@ -869,6 +883,7 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 int xor_flags;
 khiter_t hash_pos;
 struct bitmap_lookup_table_xor_item *xor_item;
+ size_t entry_map_pos;
 
 if (is_corrupt)
 return NULL;

@@ -928,6 +943,7 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 goto corrupt;
 }
 
+ entry_map_pos = bitmap_git->map_pos;
 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);

@@ -935,7 +951,8 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 if (!bitmap)
 goto corrupt;
 
- xor_bitmap = store_bitmap(bitmap_git, bitmap, &xor_item->oid, xor_bitmap, xor_flags);
+ xor_bitmap = store_bitmap(bitmap_git, bitmap, &xor_item->oid,
+  xor_bitmap, xor_flags, entry_map_pos);
 xor_items_nr--;
 }
 

@@ -969,6 +986,7 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 * Instead, we can skip ahead and immediately read the flags and
 * ewah bitmap.
 */
+ entry_map_pos = bitmap_git->map_pos;
 bitmap_git->map_pos += sizeof(uint32_t) + sizeof(uint8_t);
 flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
 bitmap = read_bitmap_1(bitmap_git);

@@ -976,7 +994,8 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 if (!bitmap)
 goto corrupt;
 
- return store_bitmap(bitmap_git, bitmap, oid, xor_bitmap, flags);
+ return store_bitmap(bitmap_git, bitmap, oid, xor_bitmap, flags,
+    entry_map_pos);
 

corrupt:
free(xor_items);

pack-bitmap.c +42 -0

@@ -2856,6 +2875,48 @@ int test_bitmap_commits(struct repository *r)
 return 0;
 }
 
+int test_bitmap_commits_offset(struct repository *r)
+{
+ struct object_id oid;
+ struct stored_bitmap_tag_pos *tagged;
+ struct bitmap_index *bitmap_git;
+ size_t commit_idx_pos_map_pos, xor_offset_map_pos, flag_map_pos,
+ ewah_bitmap_map_pos;
+
+ tag_pos_on_bitmap = 1;
+ 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, tagged, {
+ commit_idx_pos_map_pos = tagged->map_pos;
+ xor_offset_map_pos = tagged->map_pos + sizeof(uint32_t);
+ flag_map_pos = xor_offset_map_pos + sizeof(uint8_t);
+ ewah_bitmap_map_pos = flag_map_pos + sizeof(uint8_t);
+
+ printf_ln("%s %"PRIuMAX" %"PRIuMAX" %"PRIuMAX" %"PRIuMAX,
+  oid_to_hex(&oid),
+  (uintmax_t)commit_idx_pos_map_pos,
+  (uintmax_t)xor_offset_map_pos,
+  (uintmax_t)flag_map_pos,
+  (uintmax_t)ewah_bitmap_map_pos);
+ })
+ ;
+
+ free_bitmap_index(bitmap_git);
+
+ return 0;
+}
+
 int test_bitmap_hashes(struct repository *r)
 {
 struct bitmap_index *bitmap_git = prepare_bitmap_git(r);

pack-bitmap.h +1 -0

index 382d39499af2..96880ba3d72d 100644
@@ -81,6 +81,7 @@ void traverse_bitmap_commit_list(struct bitmap_index *,
 show_reachable_fn show_reachable);
 void test_bitmap_walk(struct rev_info *revs);
 int test_bitmap_commits(struct repository *r);
+int test_bitmap_commits_offset(struct repository *r);
 int test_bitmap_hashes(struct repository *r);
 int test_bitmap_pseudo_merges(struct repository *r);
 int test_bitmap_pseudo_merge_commits(struct repository *r, uint32_t n);

t/helper/test-bitmap.c +7 -0

index 3f23f2107268..65a1ab29192b 100644
@@ -10,6 +10,11 @@ static int bitmap_list_commits(void)
 return test_bitmap_commits(the_repository);
 }
 
+static int bitmap_list_commits_offset(void)
+{
+ return test_bitmap_commits_offset(the_repository);
+}
+
 static int bitmap_dump_hashes(void)
 {
 return test_bitmap_hashes(the_repository);

@@ -36,6 +41,8 @@ int cmd__bitmap(int argc, const char **argv)
 
 if (argc == 2 && !strcmp(argv[1], "list-commits"))
 return bitmap_list_commits();
+ if (argc == 2 && !strcmp(argv[1], "list-commits-offset"))
+ return bitmap_list_commits_offset();
 if (argc == 2 && !strcmp(argv[1], "dump-hashes"))
 return bitmap_dump_hashes();
 if (argc == 2 && !strcmp(argv[1], "dump-pseudo-merges"))

@@ -46,6 +53,7 @@ int cmd__bitmap(int argc, const char **argv)
 return bitmap_dump_pseudo_merge_objects(atoi(argv[2]));
 

usage("\ttest-tool bitmap list-commits\n"

t/helper/test-bitmap.c +1 -0

+      "\ttest-tool bitmap list-commits-offset\n"
     "\ttest-tool bitmap dump-hashes\n"
     "\ttest-tool bitmap dump-pseudo-merges\n"
     "\ttest-tool bitmap dump-pseudo-merge-commits <n>\n"

t/t5310-pack-bitmaps.sh +0 -0

index a62b463eaf09..ef4c5fbaae83 100755
@@ -486,6 +486,33 @@ test_bitmap_cases () {

grep "ignoring extra bitmap" trace2.txt
)
'

t/t5310-pack-bitmaps.sh +27 -0

+
+ test_expect_success 'load corrupt bitmap' '
+ 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)" &&
+ chmod +w $bitmap &&
+
+ read oid commit_off xor_off flag_off ewah_off <<-EOF &&
+ $(test-tool bitmap list-commits-offset | head -n 1)
+ EOF
+ printf '\161' |
+ dd of=$bitmap count=1 bs=1 conv=notrunc seek=$xor_off &&
+
+
+ git rev-list --count HEAD > expect &&
+ git rev-list --use-bitmap-index --count HEAD > actual &&
+ test_cmp expect actual
+ )
+ '

}

test_bitmap_cases

pack-bitmap.h +1 -0

index 382d39499af2..96880ba3d72d 100644
@@ -81,6 +81,7 @@ void traverse_bitmap_commit_list(struct bitmap_index *,
 				 show_reachable_fn show_reachable);
 void test_bitmap_walk(struct rev_info *revs);
 int test_bitmap_commits(struct repository *r);
+int test_bitmap_commits_offset(struct repository *r);
 int test_bitmap_hashes(struct repository *r);
 int test_bitmap_pseudo_merges(struct repository *r);
 int test_bitmap_pseudo_merge_commits(struct repository *r, uint32_t n);

t/helper/test-bitmap.c +5 -0

index 3f23f2107268..65a1ab29192b 100644
@@ -10,6 +10,11 @@ static int bitmap_list_commits(void)
 	return test_bitmap_commits(the_repository);
 }
 
+static int bitmap_list_commits_offset(void)
+{
+	return test_bitmap_commits_offset(the_repository);
+}
+
 static int bitmap_dump_hashes(void)
 {
 	return test_bitmap_hashes(the_repository);

t/helper/test-bitmap.c +6 -0

+	test_expect_success 'load corrupt bitmap' '
+		rm -fr repo &&
+		git init repo &&
+		test_when_finished "rm -fr repo" &&
+		(
+			cd repo &&

pack-bitmap.c struct stored_bitmap { · line 41

Quoted 13 lines · Lidong Yan via GitGitGadget

pack-bitmap.c +5 -0

index fd19c2255163..39c1c1bc4ce1 100644
@@ -34,6 +34,11 @@ struct stored_bitmap {
 int flags;
 };
 
+struct stored_bitmap_tag_pos {
+ struct stored_bitmap stored;
+ size_t map_pos;
+};
+

Hmm. I was expecting you to add a new member to the stored_bitmap structure, not a new structure entirely. Let's read on...

pack-bitmap.c static int existing_bitmaps_hits_nr; · line 156

Quoted 8 lines

pack-bitmap.c +1 -0

 /*
 * The active bitmap index for a repository. By design, repositories only have
 * a single bitmap index available (the index for the biggest packfile in

@@ -148,6 +153,7 @@ static int existing_bitmaps_hits_nr;
 static int existing_bitmaps_misses_nr;
 static int roots_with_bitmaps_nr;
 static int roots_without_bitmaps_nr;
+static int tag_pos_on_bitmap;

Why are we only sometimes tagging bitmaps with their position?

pack-bitmap.c static struct stored_bitmap *store_bitmap(struct bitmap_index *index, · line 326

Quoted 12 lines

pack-bitmap.c +2 -1

 static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
 {

@@ -314,13 +320,18 @@ static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
 struct ewah_bitmap *root,
 const struct object_id *oid,
 struct stored_bitmap *xor_with,
-  int flags)
+  int flags, size_t map_pos)
 {
 struct stored_bitmap *stored;
+ struct stored_bitmap_tag_pos *tagged;

OK.

pack-bitmap.c static struct stored_bitmap *store_bitmap(struct bitmap_index *index, · line 334

Quoted 9 lines

pack-bitmap.c +5 -1

 khiter_t hash_pos;
 int ret;
 
- stored = xmalloc(sizeof(struct stored_bitmap));
+ tagged = xmalloc(tag_pos_on_bitmap ? sizeof(struct stored_bitmap_tag_pos) :
+     sizeof(struct stored_bitmap));
+ stored = &tagged->stored;
+ if (tag_pos_on_bitmap)
+ tagged->map_pos = map_pos;

I am quite worried about this portion of the diff.

Here you allocate memory for "tagged" which is a stored_bitmap_tag_pos. But the amount of bytes you allocate depends on whether the global variable tag_pos_on_bitmap is set or not. If it isn't, then you don't allocate enough memory here to hold an entire stored_bitmap_tag_pos structure.

I think within this function you're OK, since you only write into that field when tag_pos_on_bitmap is set. But this seems like a recipe for disaster if you ever try to read or write into the tagged->map_pos field when tag_pos_on_bitmap *isn't* set.

This happens to work because of where the pointer to the stored_bitmap structure lives within the stored_bitmap_tag_pos structure. But this seems *extremely* fragile to only save 4 bytes of allocated memory per bitmap. Even on a repository with ~1,000 bitmaps (which is rare from my experience), you're only saving ~3.91 KiB.

I would expect something more like the following (based on top of your patch here):

--- 8< ---

pack-bitmap.c +7 -18

index 39c1c1bc4c..4c3829dba9 100644
@@ -31,12 +31,8 @@ struct stored_bitmap {
 struct object_id oid;
 struct ewah_bitmap *root;
 struct stored_bitmap *xor;
- int flags;
-};
-
-struct stored_bitmap_tag_pos {
- struct stored_bitmap stored;
 size_t map_pos;
+ int flags;
 };
 
 /*

@@ -153,7 +149,6 @@ static int existing_bitmaps_hits_nr;
 static int existing_bitmaps_misses_nr;
 static int roots_with_bitmaps_nr;
 static int roots_without_bitmaps_nr;
-static int tag_pos_on_bitmap;
 
 static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
 {

@@ -323,17 +318,13 @@ static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
 int flags, size_t map_pos)
 {
 struct stored_bitmap *stored;
- struct stored_bitmap_tag_pos *tagged;
 khiter_t hash_pos;
 int ret;
 
- tagged = xmalloc(tag_pos_on_bitmap ? sizeof(struct stored_bitmap_tag_pos) :
-     sizeof(struct stored_bitmap));
- stored = &tagged->stored;
- if (tag_pos_on_bitmap)
- tagged->map_pos = map_pos;
+ stored = xmalloc(sizeof(struct stored_bitmap));
 stored->root = root;
 stored->xor = xor_with;
+ stored->map_pos = map_pos;
 stored->flags = flags;
 oidcpy(&stored->oid, oid);
 

@@ -2878,12 +2869,11 @@ int test_bitmap_commits(struct repository *r)
 int test_bitmap_commits_offset(struct repository *r)
 {
 struct object_id oid;
- struct stored_bitmap_tag_pos *tagged;
+ struct stored_bitmap *bitmap;
 struct bitmap_index *bitmap_git;
 size_t commit_idx_pos_map_pos, xor_offset_map_pos, flag_map_pos,
 ewah_bitmap_map_pos;
 
- tag_pos_on_bitmap = 1;
 bitmap_git = prepare_bitmap_git(r);
 if (!bitmap_git)
 die(_("failed to load bitmap indexes"));

@@ -2897,9 +2887,9 @@ int test_bitmap_commits_offset(struct repository *r)
 die(_("failed to load bitmap indexes"));
 }
 
- kh_foreach (bitmap_git->bitmaps, oid, tagged, {
- commit_idx_pos_map_pos = tagged->map_pos;
- xor_offset_map_pos = tagged->map_pos + sizeof(uint32_t);
+ kh_foreach (bitmap_git->bitmaps, oid, bitmap, {
+ commit_idx_pos_map_pos = bitmap->map_pos;
+ xor_offset_map_pos = bitmap->map_pos + sizeof(uint32_t);
 flag_map_pos = xor_offset_map_pos + sizeof(uint8_t);
 ewah_bitmap_map_pos = flag_map_pos + sizeof(uint8_t);
--- >8 ---

Quoted 5 lines

pack-bitmap.c +0 -0

 stored->root = root;
 stored->xor = xor_with;
 stored->flags = flags;

pack-bitmap.c static int load_bitmap_entries_v1(struct bitmap_index *index) · line 395

Quoted 9 lines

pack-bitmap.c +2 -0

@@ -376,10 +387,12 @@ static int load_bitmap_entries_v1(struct bitmap_index *index)
 struct stored_bitmap *xor_bitmap = NULL;
 uint32_t commit_idx_pos;
 struct object_id oid;
+ size_t entry_map_pos;
 
 if (index->map_size - index->map_pos < 6)
 return error(_("corrupt ewah bitmap: truncated header for entry %d"), i);
 
+ entry_map_pos = index->map_pos;

Good. This is important since the read_be32() and read_u8() calls below both adjust the value of index->map_pos past the beginning of the bitmap.

pack-bitmap.c static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_ · line 946

Quoted 13 lines

pack-bitmap.c +2 -0

@@ -869,6 +883,7 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 int xor_flags;
 khiter_t hash_pos;
 struct bitmap_lookup_table_xor_item *xor_item;
+ size_t entry_map_pos;
 
 if (is_corrupt)
 return NULL;

@@ -928,6 +943,7 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 goto corrupt;
 }
 
+ entry_map_pos = bitmap_git->map_pos;

Same here.

pack-bitmap.c static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_ · line 989

Quoted 5 lines

pack-bitmap.c +1 -0

@@ -969,6 +986,7 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_
 * Instead, we can skip ahead and immediately read the flags and
 * ewah bitmap.
 */
+ entry_map_pos = bitmap_git->map_pos;

And here.

pack-bitmap.c static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_

Quoted 13 lines

pack-bitmap.c +13 -0

+int test_bitmap_commits_offset(struct repository *r)
+{
+ struct object_id oid;
+ struct stored_bitmap_tag_pos *tagged;
+ struct bitmap_index *bitmap_git;
+ size_t commit_idx_pos_map_pos, xor_offset_map_pos, flag_map_pos,
+ ewah_bitmap_map_pos;
+
+ tag_pos_on_bitmap = 1;
+ bitmap_git = prepare_bitmap_git(r);
+ if (!bitmap_git)
+ die(_("failed to load bitmap indexes"));
+

If we either forgot to set this variable here or did so after calling prepare_bitmap_git(), then we wouldn't allocate enough memory to store the map_pos field in the stored_bitmap_tag_pos structure. When we then would try and read that field below, we'd read garbage heap data outside of our structure.

Quoted 8 lines

+ /*
+ * 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"));
+ }

This comment suggests that we can avoid reading the commit table altogether. Indeed, calling load_bitmap_entries_v1() here does that, since it is not called when loading a bitmap that has a lookup table.

So I think the behavior here is correct, but the comment is misleading. I suspect that the confusion would be resolved by instead writing:

/*
* Since this function needs to know the position of each individual
* bitmap, bypass the commit lookup table (if one exists) by forcing
* the bitmap to eagerly load its entries.
*/

I think this is copy-and-paste from 28cd730680 (pack-bitmap: prepare to read lookup table extension, 2022-08-14) via the 'test_bitmap_commits()' function immediately above this one. I think both would benefit from some clean-up, since this comment is equally misleading in that function.

For your purposes, I would either:

- remove or (preferably) reword the comment in your new function, leaving the one in test_bitmap_commits() as-is, or

- reword the comment in test_bitmap_commits() to be more like the one above, via a preparatory commit, and then introduce the new function using the same wording.

Between the two, I think the latter is preferable.

As an aside, I think that for bitmaps that do have a commit lookup table, you could go slightly faster here by walking over that portion of the *.bitmap file, since it directly encodes the information you're interested in here. But I would avoid doing that, since it too seems brittle and I would like to avoid having two separate spots that each implement reading the commit table format.

Quoted 2 lines

+ kh_foreach (bitmap_git->bitmaps, oid, tagged, {
+ commit_idx_pos_map_pos = tagged->map_pos;

OK, and here's where we pull out the actual position of the selected commit's bitmap.

pack-bitmap.c

Quoted 10 lines

+ xor_offset_map_pos = tagged->map_pos + sizeof(uint32_t);
+ flag_map_pos = xor_offset_map_pos + sizeof(uint8_t);
+ ewah_bitmap_map_pos = flag_map_pos + sizeof(uint8_t);

pack-bitmap.c +7 -0

+
+ printf_ln("%s %"PRIuMAX" %"PRIuMAX" %"PRIuMAX" %"PRIuMAX,
+  oid_to_hex(&oid),
+  (uintmax_t)commit_idx_pos_map_pos,
+  (uintmax_t)xor_offset_map_pos,
+  (uintmax_t)flag_map_pos,
+  (uintmax_t)ewah_bitmap_map_pos);

Hmm. We print more information here than just the map_pos. This is brittle if the on-disk format changes (e.g., to store the XOR offsets in some other part of the bitmap). But hopefully future updates to the bitmap format will come with updates to this function as well ;-).

It feels somewhat unsatisfying to print output like:

   $COMMIT_OID <map_pos> <map_pos+4> <map_pos+5> <map_pos+6>

, but I think it makes sense here for a couple of reasons:

- If we just print the <map_pos>, then the test is responsible for knowing the distance between that and the XOR offset, which extends the brittleness to the test code

- likewise, if we print out just the map_pos and the positions of the XOR offset, it feels strange to omit the others.

Quoted 29 lines

pack-bitmap.h +1 -0

index 382d39499af2..96880ba3d72d 100644
@@ -81,6 +81,7 @@ void traverse_bitmap_commit_list(struct bitmap_index *,
 show_reachable_fn show_reachable);
 void test_bitmap_walk(struct rev_info *revs);
 int test_bitmap_commits(struct repository *r);
+int test_bitmap_commits_offset(struct repository *r);
 int test_bitmap_hashes(struct repository *r);
 int test_bitmap_pseudo_merges(struct repository *r);
 int test_bitmap_pseudo_merge_commits(struct repository *r, uint32_t n);

t/helper/test-bitmap.c +5 -0

index 3f23f2107268..65a1ab29192b 100644
@@ -10,6 +10,11 @@ static int bitmap_list_commits(void)
 return test_bitmap_commits(the_repository);
 }
 
+static int bitmap_list_commits_offset(void)
+{
+ return test_bitmap_commits_offset(the_repository);
+}
+
 static int bitmap_dump_hashes(void)
 {
 return test_bitmap_hashes(the_repository);

t/helper/test-bitmap.c int cmd__bitmap(int argc, const char **argv) · line 45

Quoted 5 lines

t/helper/test-bitmap.c +2 -0

@@ -36,6 +41,8 @@ int cmd__bitmap(int argc, const char **argv)
 
 if (argc == 2 && !strcmp(argv[1], "list-commits"))
 return bitmap_list_commits();
+ if (argc == 2 && !strcmp(argv[1], "list-commits-offset"))
+ return bitmap_list_commits_offset();

All of the scaffolding here looks good.

This new mode reads a little awkwardly to me (but may not to others, in which case I am happy to back away from the following suggestion). Can we either call this 'list-commits-with-offset' or 'list-commit-offsets'? I have a vague preference towards the former since the new mode has a string prefix matching the existing mode.

Quoted 6 lines

t/helper/test-bitmap.c +6 -0

+ test_expect_success 'load corrupt bitmap' '
+ rm -fr repo &&
+ git init repo &&
+ test_when_finished "rm -fr repo" &&
+ (
+ cd repo &&

t/helper/test-bitmap.c int cmd__bitmap(int argc, const char **argv)

Quoted 10 lines

t/helper/test-bitmap.c +10 -0

+ git config pack.writeBitmapLookupTable '"$writeLookupTable"' &&
+
+ test_commit base &&
+
+ git repack -adb &&
+ bitmap="$(ls .git/objects/pack/pack-*.bitmap)" &&
+ chmod +w $bitmap &&
+
+ read oid commit_off xor_off flag_off ewah_off <<-EOF &&
+ $(test-tool bitmap list-commits-offset | head -n 1)

We avoid putting 'git' or 'test-tool' on the left-hand side of a pipe, since we want to avoid squelching any errors / segfaults from our code.

How about (assuming the rename above):

   test-tool bitmap list-commit-offsets >offsets &&
   xor_off="$(head -n1 offsets | awk '{print $3}')" &&
   ...

?

t/helper/test-bitmap.c

Quoted 6 lines

+ printf '\161' |
+ dd of=$bitmap count=1 bs=1 conv=notrunc seek=$xor_off &&

t/helper/test-bitmap.c +4 -0

+
+
+ git rev-list --count HEAD > expect &&
+ git rev-list --use-bitmap-index --count HEAD > actual &&

Using --count can mask failures in the bitmap code since it only guards you against getting the wrong number of objects, but doesn't guard you against getting the right amount of objects in a permuted order. I think we'd want just 'git rev-list --objects' here, but note that you have to use '--no-object-names' on the non-bitmap side, since rev-list does not print out paths when using bitmaps[^1].

How about:

   git rev-list --objects --no-object-names HEAD >expect.raw &&
   git rev-list --objects --use-bitmap-index --no-object-names HEAD \

Quoted 1 line

actual.raw &&

   sort expect.raw >expect &&
   sort actual.raw >actual &&

   test_cmp expect actual

(Note that you also have to sort the output here since rev-list does not output objects in a meaningful order when using bitmaps.)

Thanks,
Taylor

[^1]: Not that it matters here since we don't expect to load the bitmap
anyway, but it's worth doing regardless.

From: Lidong Yan <[email protected]>

In pack-bitmap.c:test_bitmap_commits(), it comments

/*
* As this function is only used to print bitmap selected
* commits, we don't have to read the commit table. */

This suggests that we can avoid reading the commit table altogether. However, this comment is misleading. The reason we load bitmap entries here is because test_bitmap_commits() needs to print the commit IDs from the bitmap, and we must read the bitmap entries to obtain those commit IDs. So reword this comment.

Signed-off-by Lidong Yan <[email protected]>

---
 pack-bitmap.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

pack-bitmap.c +0 -0

index fd19c2255163..e514c9da239b 100644

pack-bitmap.c +2 -1

+	 * commits, bypass the commit lookup table (if one exists)
+	 * by forcing the bitmap to eagerly load its entries.
 	 */
 	if (bitmap_git->table_lookup) {
 		if (load_bitmap_entries_v1(bitmap_git) < 0)
--

gitgitgadget

Lidong Yan (2):
pack-bitmap: reword comments in test_bitmap_commits()
pack-bitmap: add load corrupt bitmap test

Taylor Blau (1):
pack-bitmap: fix memory leak if load_bitmap() failed

Since it seems this patch has been inactive for some time, I have revised the comments according to Taylor's feedback and submitted a new version.

This patch prevents pack-bitmap.c:load_bitmap() from nulling bitmap_git->bitmap when loading failed. Thus eliminates memory leak. This patch also add a test case in t5310 which use clang leak sanitizer to detect whether leak happens when loading failed.

Lidong Yan (2):
pack-bitmap: reword comments in test_bitmap_commits()
pack-bitmap: add load corrupt bitmap test

Taylor Blau (1):
pack-bitmap: fix memory leak if load_bitmap() failed

Quoted 12 lines · Lidong Yan via GitGitGadget

Since it seems this patch has been inactive for some time, I have revised the comments according to Taylor's feedback and submitted a new version.

This patch prevents pack-bitmap.c:load_bitmap() from nulling bitmap_git->bitmap when loading failed. Thus eliminates memory leak. This patch also add a test case in t5310 which use clang leak sanitizer to detect whether leak happens when loading failed.

Lidong Yan (2):
pack-bitmap: reword comments in test_bitmap_commits()
pack-bitmap: add load corrupt bitmap test

Quoted 2 lines

Taylor Blau (1):
pack-bitmap: fix memory leak if load_bitmap() failed

OK, now, how does this iteration look to folks? We haven't heard anybody say yet. Is it ready to be marked for 'next' yet?

Quoted 14 lines · Junio C Hamano

Quoted 12 lines · Lidong Yan via GitGitGadget

Since it seems this patch has been inactive for some time, I have revised the comments according to Taylor's feedback and submitted a new version.

This patch prevents pack-bitmap.c:load_bitmap() from nulling bitmap_git->bitmap when loading failed. Thus eliminates memory leak. This patch also add a test case in t5310 which use clang leak sanitizer to detect whether leak happens when loading failed.

Lidong Yan (2):
pack-bitmap: reword comments in test_bitmap_commits()
pack-bitmap: add load corrupt bitmap test

Quoted 5 lines

Quoted 2 lines

Taylor Blau (1):
pack-bitmap: fix memory leak if load_bitmap() failed

OK, now, how does this iteration look to folks? We haven't heard anybody say yet. Is it ready to be marked for 'next' yet?

Oops, this fell off of my review queue. This version looks great to me. Thanks, Lidong!