[PATCH 3/8] pack-bitmap-write: sort pseudo-merge commit lookup table in pack order
- From
Taylor Blau <me@ttaylorr.com>
- Date
- Apr 13, 2026, 23:56 UTC
- Message-ID
- <1f5835e8c62880d40187989466fdc70dfe89989f.1776124588.git.me@ttaylorr.com>
- In-Reply-To
- <cover.1776124588.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 20e77ab4390..dce43ed8dc6 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' ' git init pseudo-merge-fill-in-traversal && test_when_finished "rm -fr pseudo-merge-fill-in-traversal" && (
-- 2.54.0.rc1.73.g8f4e0170952