[PATCH v2 0/9] pack-bitmap: fix various pseudo-merge bugs

[Taylor Blau <me@ttaylorr.com>]

[Note to the maintainer: this series has been rebased onto the current
tip of master, which is 94f057755b7 (Git 2.54, 2026-04-19) at the time
of writing.]

This is a small reroll of my series to fix several bugs in the
pseudo-merge bitmap implementation. The main changes since last time
are:

 - Fixed a use-after-realloc bug in the test helper introduced in the
   first commit.

 - Swapped the order of initializing and cleaning up repositories in the
   new test scripts.

 - Updated bitmapPseudoMerge.<name>.sampleRate's documentation to
   describe the range as (0,1], and added a new commit fixing a broken
   example in gitpacking(7).

As usual, a range-diff is included below for convenience. The original
cover letter is as follows:

========================================================================

This series fixes several bugs in the pseudo-merge bitmap implementation
that caused the pseudo-merge application path to be effectively broken
during fill-in traversal.

Peff noticed that this code path was never triggered by the existing
test suite, and investigating that observation uncovered a handful of
bugs, some compounding.

The first two patches introduce test infrastructure: a 'bitmap write'
test helper that gives tests precise control over which commits receive
individual bitmaps, and a set of "test_expect_failure" tests
demonstrating each bug.

The next four patches fix the bugs in the per-commit pseudo-merge
lookup:

  - The pseudo-merge commit lookup table was sorted by OID rather than
    by bit position, causing the reader's binary search to fail.

  - The binary search in pseudo_merge_at() had its lo/hi updates
    swapped.

  - The extended pseudo-merge lookup path had three compounding bugs: a
    wrong entry-size calculation in the writer, a misinterpretation of
    extended table entries in the reader, and a silently-swallowed error
    check.

The final two patches fix issues in pseudo-merge group selection:

  - find_pseudo_merge_group_for_ref() did not parse commits before
    inspecting their dates, so all candidates had date == 0 and were
    unconditionally placed in the "stable" bucket.

  - The config validation for bitmapPseudoMerge.*.sampleRate accepted 0,
    which leads to a division by zero once the date classification is
    fixed and the unstable code path is exercised.

There is also a small fix for a regex leak when the pattern key is
overridden in config.

Thanks in advance for your review!

Taylor Blau (9):
  t/helper: add 'test-tool bitmap write' subcommand
  t5333: demonstrate various pseudo-merge bugs
  pack-bitmap-write: sort pseudo-merge commit lookup table in pack order
  pack-bitmap: fix inverted binary search in `pseudo_merge_at()`
  pack-bitmap: fix pseudo-merge lookup for shared commits
  pack-bitmap: parse commits in `find_pseudo_merge_group_for_ref()`
  pack-bitmap: reject pseudo-merge "sampleRate" of 0
  Documentation: fix broken `sampleRate` in gitpacking(7)
  pack-bitmap: prevent pattern leak on pseudo-merge re-assignment

 Documentation/config/bitmap-pseudo-merge.adoc |   4 +-
 Documentation/gitpacking.adoc                 |   4 +-
 pack-bitmap-write.c                           |  23 +-
 pseudo-merge.c                                |  19 +-
 t/helper/test-bitmap.c                        | 113 ++++++++-
 t/t5310-pack-bitmaps.sh                       |  24 ++
 t/t5333-pseudo-merge-bitmaps.sh               | 231 ++++++++++++++++++
 7 files changed, 404 insertions(+), 14 deletions(-)

Range-diff against v1:
 1:  d5ef6b959fd !  1:  c0df35f8ebd t/helper: add 'test-tool bitmap write' subcommand
    @@ t/helper/test-bitmap.c: static int bitmap_dump_pseudo_merge_objects(uint32_t n)
      	return test_bitmap_pseudo_merge_objects(the_repository, n);
      }
      
    -+struct bitmap_writer_data {
    -+	struct packing_data packed;
    -+	struct pack_idx_entry **index;
    -+	uint32_t nr;
    -+};
    -+
     +static int add_packed_object(const struct object_id *oid,
     +			     struct packed_git *pack,
     +			     uint32_t pos,
     +			     void *_data)
     +{
    -+	struct bitmap_writer_data *data = _data;
    ++	struct packing_data *packed = _data;
     +	struct object_entry *entry;
     +	struct object_info oi = OBJECT_INFO_INIT;
     +	enum object_type type;
     +
     +	oi.typep = &type;
     +
    -+	entry = packlist_alloc(&data->packed, oid);
    ++	entry = packlist_alloc(packed, oid);
     +	entry->idx.offset = nth_packed_object_offset(pack, pos);
     +	if (packed_object_info(pack, entry->idx.offset, &oi) < 0)
     +		die("could not get type of object %s",
     +		    oid_to_hex(oid));
     +	oe_set_type(entry, type);
    -+	oe_set_in_pack(&data->packed, entry, pack);
    -+	data->index[data->nr++] = &entry->idx;
    ++	oe_set_in_pack(packed, entry, pack);
     +
     +	return 0;
     +}
    @@ t/helper/test-bitmap.c: static int bitmap_dump_pseudo_merge_objects(uint32_t n)
     +static int bitmap_write(const char *basename)
     +{
     +	struct packed_git *p = NULL;
    -+	struct bitmap_writer_data data = { 0 };
    ++	struct packing_data packed = { 0 };
     +	struct bitmap_writer writer;
    ++	struct pack_idx_entry **index;
     +	struct strbuf buf = STRBUF_INIT;
    ++	uint32_t i;
     +
     +	prepare_repo_settings(the_repository);
     +	repo_for_each_pack(the_repository, p) {
    @@ t/helper/test-bitmap.c: static int bitmap_dump_pseudo_merge_objects(uint32_t n)
     +	if (open_pack_index(p))
     +		die("cannot open pack index for '%s'", p->pack_name);
     +
    -+	prepare_packing_data(the_repository, &data.packed);
    -+	ALLOC_ARRAY(data.index, p->num_objects);
    ++	prepare_packing_data(the_repository, &packed);
     +
    -+	for_each_object_in_pack(p, add_packed_object, &data,
    ++	for_each_object_in_pack(p, add_packed_object, &packed,
     +				ODB_FOR_EACH_OBJECT_PACK_ORDER);
     +
    -+	bitmap_writer_init(&writer, the_repository, &data.packed, NULL);
    -+	bitmap_writer_build_type_index(&writer, data.index);
    ++	/*
    ++	 * Build the index array now that data.packed.objects[] is
    ++	 * fully allocated (packlist_alloc() may have reallocated it
    ++	 * during the loop above).
    ++	 */
    ++	ALLOC_ARRAY(index, p->num_objects);
    ++	for (i = 0; i < p->num_objects; i++)
    ++		index[i] = &packed.objects[i].idx;
    ++
    ++	bitmap_writer_init(&writer, the_repository, &packed, NULL);
    ++	bitmap_writer_build_type_index(&writer, index);
     +
     +	while (strbuf_getline_lf(&buf, stdin) != EOF) {
     +		struct object_id oid;
    @@ t/helper/test-bitmap.c: static int bitmap_dump_pseudo_merge_objects(uint32_t n)
     +		if (!c || repo_parse_commit(the_repository, c))
     +			die("could not parse commit %s", buf.buf);
     +
    -+		bitmap_writer_push_commit(&writer, c, false);
    ++		bitmap_writer_push_commit(&writer, c, 0);
     +	}
     +
     +	select_pseudo_merges(&writer);
    @@ t/helper/test-bitmap.c: static int bitmap_dump_pseudo_merge_objects(uint32_t n)
     +
     +	bitmap_writer_set_checksum(&writer, p->hash);
     +
    -+	QSORT(data.index, p->num_objects, idx_oid_cmp);
    ++	QSORT(index, p->num_objects, idx_oid_cmp);
     +
     +	strbuf_reset(&buf);
     +	strbuf_addstr(&buf, p->pack_name);
     +	strbuf_strip_suffix(&buf, ".pack");
     +	strbuf_addstr(&buf, ".bitmap");
    -+	bitmap_writer_finish(&writer, data.index, buf.buf, 0);
    ++	bitmap_writer_finish(&writer, index, buf.buf, 0);
     +
     +	bitmap_writer_free(&writer);
     +	strbuf_release(&buf);
    -+	free(data.index);
    -+	clear_packing_data(&data.packed);
    ++	free(index);
    ++	clear_packing_data(&packed);
     +
     +	return 0;
     +}
    @@ t/t5310-pack-bitmaps.sh: test_expect_success 'truncated bitmap fails gracefully
      	test_grep corrupted.bitmap.index stderr
      '
      
    -+test_expect_success 'test-tool bitmap write' '
    -+	git init bitmap-write-helper &&
    ++test_expect_success 'test-tool bitmap write determines bitmap selection' '
     +	test_when_finished "rm -fr bitmap-write-helper" &&
    ++	git init bitmap-write-helper &&
     +	(
     +		cd bitmap-write-helper &&
     +
    @@ t/t5310-pack-bitmaps.sh: test_expect_success 'truncated bitmap fails gracefully
     +
     +		pack="$(ls .git/objects/pack/pack-*.pack)" &&
     +
    -+		git rev-parse HEAD >commits &&
    -+		test-tool bitmap write "$(basename $pack)" <commits &&
    ++		git rev-parse HEAD >in &&
    ++		test-tool bitmap write "$(basename $pack)" <in &&
     +
    -+		test-tool bitmap list-commits | sort >actual &&
    -+		sort commits >expect &&
    -+		test_cmp expect actual &&
    ++		test-tool bitmap list-commits >bitmaps.raw &&
    ++		sort bitmaps.raw >bitmaps &&
    ++		test_cmp in bitmaps &&
     +
     +		git rev-list --count --objects --use-bitmap-index HEAD >actual &&
     +		git rev-list --count --objects HEAD >expect &&
 2:  f4899b668e2 !  2:  11de3343726 t5333: demonstrate various pseudo-merge bugs
    @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'use pseudo-merge in bounda
      '
      
     +test_expect_failure 'apply pseudo-merges during fill-in traversal' '
    -+	git init pseudo-merge-fill-in-traversal &&
     +	test_when_finished "rm -fr pseudo-merge-fill-in-traversal" &&
    ++	git init pseudo-merge-fill-in-traversal &&
     +	(
     +		cd pseudo-merge-fill-in-traversal &&
     +
    @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'use pseudo-merge in bounda
     +'
     +
     +test_expect_failure 'apply pseudo-merges from multiple groups during fill-in' '
    -+	git init pseudo-merge-fill-in-multi &&
     +	test_when_finished "rm -fr pseudo-merge-fill-in-multi" &&
    ++	git init pseudo-merge-fill-in-multi &&
     +	(
     +		cd pseudo-merge-fill-in-multi &&
     +
    @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'use pseudo-merge in bounda
     +'
     +
     +test_expect_failure 'pseudo-merge commits are correctly classified by date' '
    -+	git init pseudo-merge-date-classification &&
     +	test_when_finished "rm -fr pseudo-merge-date-classification" &&
    ++	git init pseudo-merge-date-classification &&
     +	(
     +		cd pseudo-merge-date-classification &&
     +
    @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'use pseudo-merge in bounda
     +'
     +
     +test_expect_success 'sampleRate=0 does not cause division by zero' '
    -+	git init pseudo-merge-sample-rate-zero &&
     +	test_when_finished "rm -fr pseudo-merge-sample-rate-zero" &&
    ++	git init pseudo-merge-sample-rate-zero &&
     +	(
     +		cd pseudo-merge-sample-rate-zero &&
     +
 3:  1f5835e8c62 !  3:  8d908ab415e pack-bitmap-write: sort pseudo-merge commit lookup table in pack order
    @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'use pseudo-merge in bounda
      
     -test_expect_failure 'apply pseudo-merges during fill-in traversal' '
     +test_expect_success 'apply pseudo-merges during fill-in traversal' '
    - 	git init pseudo-merge-fill-in-traversal &&
      	test_when_finished "rm -fr pseudo-merge-fill-in-traversal" &&
    + 	git init pseudo-merge-fill-in-traversal &&
      	(
 4:  af9f651269d !  4:  07f70a07c20 pack-bitmap: fix inverted binary search in `pseudo_merge_at()`
    @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'apply pseudo-merges during
      
     -test_expect_failure 'apply pseudo-merges from multiple groups during fill-in' '
     +test_expect_success 'apply pseudo-merges from multiple groups during fill-in' '
    - 	git init pseudo-merge-fill-in-multi &&
      	test_when_finished "rm -fr pseudo-merge-fill-in-multi" &&
    + 	git init pseudo-merge-fill-in-multi &&
    ++	git init pseudo-merge-fill-in-multi &&
      	(
    + 		cd pseudo-merge-fill-in-multi &&
    + 
 5:  01f1d6f08c6 =  5:  3ed0b39843f pack-bitmap: fix pseudo-merge lookup for shared commits
 6:  6d74c0a177a !  6:  95f847211f3 pack-bitmap: parse commits in `find_pseudo_merge_group_for_ref()`
    @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'apply pseudo-merges with o
      
     -test_expect_failure 'pseudo-merge commits are correctly classified by date' '
     +test_expect_success 'pseudo-merge commits are correctly classified by date' '
    - 	git init pseudo-merge-date-classification &&
      	test_when_finished "rm -fr pseudo-merge-date-classification" &&
    + 	git init pseudo-merge-date-classification &&
      	(
      		cd pseudo-merge-date-classification &&
      
    @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_failure 'pseudo-merge commits are c
      
     -test_expect_success 'sampleRate=0 does not cause division by zero' '
     +test_expect_failure 'sampleRate=0 does not cause division by zero' '
    - 	git init pseudo-merge-sample-rate-zero &&
      	test_when_finished "rm -fr pseudo-merge-sample-rate-zero" &&
    + 	git init pseudo-merge-sample-rate-zero &&
      	(
 7:  1b0f7295c21 !  7:  f8a01cfb893 pack-bitmap: reject pseudo-merge "sampleRate" of 0
    @@ Commit message
     
         Signed-off-by: Taylor Blau <me@ttaylorr.com>
     
    + ## Documentation/config/bitmap-pseudo-merge.adoc ##
    +@@ Documentation/config/bitmap-pseudo-merge.adoc: will be updated more often than a reference pointing at an old commit.
    + bitmapPseudoMerge.<name>.sampleRate::
    + 	Determines the proportion of non-bitmapped commits (among
    + 	reference tips) which are selected for inclusion in an
    +-	unstable pseudo-merge bitmap. Must be between `0` and `1`
    +-	(inclusive). The default is `1`.
    ++	unstable pseudo-merge bitmap. Must be greater than `0` and
    ++	less than or equal to `1`. The default is `1`.
    + 
    + bitmapPseudoMerge.<name>.threshold::
    + 	Determines the minimum age of non-bitmapped commits (among
    +
      ## pseudo-merge.c ##
     @@ pseudo-merge.c: static int pseudo_merge_config(const char *var, const char *value,
      		}
    @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'pseudo-merge commits are c
      
     -test_expect_failure 'sampleRate=0 does not cause division by zero' '
     +test_expect_success 'sampleRate=0 does not cause division by zero' '
    - 	git init pseudo-merge-sample-rate-zero &&
      	test_when_finished "rm -fr pseudo-merge-sample-rate-zero" &&
    + 	git init pseudo-merge-sample-rate-zero &&
      	(
 -:  ----------- >  8:  c37156502c0 Documentation: fix broken `sampleRate` in gitpacking(7)
 8:  8f4e0170952 =  9:  b905fd5d0ae pack-bitmap: prevent pattern leak on pseudo-merge re-assignment

base-commit: 94f057755b7941b321fd11fec1b2e3ca5313a4e0
-- 
2.54.0.9.gb905fd5d0ae