git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v2 3/9] pack-bitmap-write: sort pseudo-merge commit lookup table in pack order

From
Taylor Blau <me@ttaylorr.com>
Date
Apr 21, 2026, 20:02 UTC
Message-ID
<8d908ab415ed021fac113c63a093c3e72b0ba40b.1776801694.git.me@ttaylorr.com>
In-Reply-To
<cover.1776801694.git.me@ttaylorr.com>

The pseudo-merge commit lookup table stores each commit's position in the pack- or pseudo-pack order, and is used to perform a binary search in order to determine which pseudo-merge(s) a given commit belongs to.

However, the table was previously sorted in lexical order (via `oid_array_sort()`), causing the binary search to fail.

While this causes pseudo-merge bitmaps to be de-facto broken for fill-in traversal, there are a couple of important points to keep in mind:

 * Pseudo-merge application during the initial phases of a bitmap-based
   traversal are applied via `cascade_pseudo_merges_1()`. This function
   enumerates the known pseudo-merges and determines if its parents are
   a subset of the traversal roots.
   This is a different path than the fill-in traversal, where we are
   looking for any pseudo-merges which may be satisfied after visiting
   some commit along an object walk, which involves the aforementioned
   (broken) binary search.
   As a consequence, any pseudo-merges we apply at this stage are done
   so correctly.
 * While this bug makes applying pseudo-merges during fill-in traversal
   effectively broken, it does not produce wrong results. Instead of
   applying the *wrong* pseudo-merge, we will simply fail to find
   satisfied pseudo-merges, leaving the traversal to use the existing
   fill-in routines.

Fix this by sorting the table by bit position before writing, matching the order that the reader's binary search expects.

This does produce a change the on-disk format insofar as the actual code now complies with the documented format (for more details, refer to: Documentation/technical/bitmap-format.adoc). Given that this never worked in the first place, such a change should be OK to perform.

If an out-of-tree implementation of pseudo-merges happened to generate bitmaps that comply with the documented format, they will continue to be read and interpreted as normal.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-bitmap-write.c             | 21 ++++++++++++++++++++-
 t/t5333-pseudo-merge-bitmaps.sh |  2 +-
 2 files changed, 21 insertions(+), 2 deletions(-)
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 8338d7217ef..86ed6a5d78c 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -819,6 +819,20 @@ static void write_selected_commits_v1(struct bitmap_writer *writer,
 	}
 }
 
+static int pseudo_merge_commit_pos_cmp(const void *_va, const void *_vb,
+				       void *_data)
+{
+	struct bitmap_writer *writer = _data;
+	uint32_t pos_a = find_object_pos(writer, _va, NULL);
+	uint32_t pos_b = find_object_pos(writer, _vb, NULL);
+
+	if (pos_a < pos_b)
+		return -1;
+	if (pos_a > pos_b)
+		return 1;
+	return 0;
+}
+
 static void write_pseudo_merges(struct bitmap_writer *writer,
 				struct hashfile *f)
 {
@@ -876,7 +890,12 @@ static void write_pseudo_merges(struct bitmap_writer *writer,
 		oid_array_append(&commits, &kh_key(writer->pseudo_merge_commits, i));
 	}
 
-	oid_array_sort(&commits);
+	/*
+	 * Sort the commits by their bit position so that the lookup
+	 * table can be binary searched by the reader (see
+	 * find_pseudo_merge()).
+	 */
+	QSORT_S(commits.oid, commits.nr, pseudo_merge_commit_pos_cmp, writer);
 
 	/* write lookup table (non-extended) */
 	for (i = 0; i < commits.nr; i++) {
diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh
index 0e9638c31c3..3d7a7668121 100755
--- a/t/t5333-pseudo-merge-bitmaps.sh
+++ b/t/t5333-pseudo-merge-bitmaps.sh
@@ -462,7 +462,7 @@ test_expect_success 'use pseudo-merge in boundary traversal' '
 	)
 '
 
-test_expect_failure 'apply pseudo-merges during fill-in traversal' '
+test_expect_success 'apply pseudo-merges during fill-in traversal' '
 	test_when_finished "rm -fr pseudo-merge-fill-in-traversal" &&
 	git init pseudo-merge-fill-in-traversal &&
 	(
-- 
2.54.0.9.gb905fd5d0ae
Previous: Taylor BlauNext: Taylor Blau
Message 23 of 46 in “pack-bitmap: fix various pseudo-merge bugs”
  1. 0/8 pack-bitmap: fix various pseudo-merge bugsTaylor Blau, Apr 13, 2026
  2. 1/8 t/helper: add 'test-tool bitmap write' subcommandTaylor Blau, Apr 13, 2026
  3. Junio C HamanoApr 14, 2026
  4. Taylor BlauApr 14, 2026
  5. Junio C HamanoApr 14, 2026
  6. Taylor BlauApr 14, 2026
  7. Junio C HamanoApr 14, 2026
  8. Taylor BlauApr 14, 2026
  9. Elijah NewrenApr 19, 2026
  10. Taylor BlauApr 21, 2026
  11. 2/8 t5333: demonstrate various pseudo-merge bugsTaylor Blau, Apr 13, 2026
  12. Elijah NewrenApr 19, 2026
  13. 3/8 pack-bitmap-write: sort pseudo-merge commit lookup table in pack orderTaylor Blau, Apr 13, 2026
  14. 4/8 pack-bitmap: fix inverted binary search in `pseudo_merge_at()`Taylor Blau, Apr 13, 2026
  15. 5/8 pack-bitmap: fix pseudo-merge lookup for shared commitsTaylor Blau, Apr 13, 2026
  16. 6/8 pack-bitmap: parse commits in `find_pseudo_merge_group_for_ref()`Taylor Blau, Apr 13, 2026
  17. 7/8 pack-bitmap: reject pseudo-merge "sampleRate" of 0Taylor Blau, Apr 13, 2026
  18. Elijah NewrenApr 19, 2026
  19. 8/8 pack-bitmap: prevent pattern leak on pseudo-merge re-assignmentTaylor Blau, Apr 13, 2026
  20. 0/9 pack-bitmap: fix various pseudo-merge bugsTaylor Blau, Apr 21, 2026
  21. 1/9 t/helper: add 'test-tool bitmap write' subcommandTaylor Blau, Apr 21, 2026
  22. 2/9 t5333: demonstrate various pseudo-merge bugsTaylor Blau, Apr 21, 2026
  23. 3/9 pack-bitmap-write: sort pseudo-merge commit lookup table in pack orderTaylor Blau, Apr 21, 2026
  24. 4/9 pack-bitmap: fix inverted binary search in `pseudo_merge_at()`Taylor Blau, Apr 21, 2026
  25. 5/9 pack-bitmap: fix pseudo-merge lookup for shared commitsTaylor Blau, Apr 21, 2026
  26. 6/9 pack-bitmap: parse commits in `find_pseudo_merge_group_for_ref()`Taylor Blau, Apr 21, 2026
  27. 7/9 pack-bitmap: reject pseudo-merge "sampleRate" of 0Taylor Blau, Apr 21, 2026
  28. 8/9 Documentation: fix broken `sampleRate` in gitpacking(7)Taylor Blau, Apr 21, 2026
  29. 9/9 pack-bitmap: prevent pattern leak on pseudo-merge re-assignmentTaylor Blau, Apr 21, 2026
  30. Elijah NewrenApr 22, 2026
  31. Junio C HamanoMay 11, 2026
  32. Taylor BlauMay 12, 2026
  33. Taylor BlauMay 12, 2026
  34. 0/9 pack-bitmap: fix various pseudo-merge bugsTaylor Blau, May 12, 2026
  35. 1/9 t/helper: add 'test-tool bitmap write' subcommandTaylor Blau, May 12, 2026
  36. 2/9 t5333: demonstrate various pseudo-merge bugsTaylor Blau, May 12, 2026
  37. 3/9 pack-bitmap-write: sort pseudo-merge commit lookup table in pack orderTaylor Blau, May 12, 2026
  38. 4/9 pack-bitmap: fix inverted binary search in `pseudo_merge_at()`Taylor Blau, May 12, 2026
  39. 5/9 pack-bitmap: fix pseudo-merge lookup for shared commitsTaylor Blau, May 12, 2026
  40. 6/9 pack-bitmap: parse commits in `find_pseudo_merge_group_for_ref()`Taylor Blau, May 12, 2026
  41. 7/9 pack-bitmap: reject pseudo-merge "sampleRate" of 0Taylor Blau, May 12, 2026
  42. 8/9 Documentation: fix broken `sampleRate` in gitpacking(7)Taylor Blau, May 12, 2026
  43. 9/9 pack-bitmap: prevent pattern leak on pseudo-merge re-assignmentTaylor Blau, May 12, 2026
  44. Junio C HamanoMay 12, 2026
  45. Taylor BlauMay 12, 2026
  46. Junio C HamanoMay 12, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.