[PATCH 09/17] midx: do not require packs to be sorted in lexicographic order
- From
Taylor Blau <me@ttaylorr.com>
- Date
- Dec 6, 2025, 20:31 UTC
- Message-ID
- <d5389a93b16a4933b0c54f78f2d5ce84b9ecac53.1765053054.git.me@ttaylorr.com>
- In-Reply-To
- <cover.1765053054.git.me@ttaylorr.com>
The MIDX file format currently requires that pack files be identified by the lexicographic ordering of their names (that is, a pack having a checksum beginning with "abc" would have a numeric pack_int_id which is smaller than the same value for a pack beginning with "bcd").
As a result, it is impossible to combine adjacent MIDX layers together without permuting bits from bitmaps that are in more recent layer(s).
To see why, consider the following example:
| packs | preferred pack
--------+-------------+---------------
MIDX #0 | { X, Y, Z } | Y
MIDX #1 | { A, B, C } | B
MIDX #2 | { D, E, F } | D, where MIDX #2's base MIDX is MIDX #1, and so on. Suppose that we want to combine MIDX layers #0 and #1, to create a new layer #0' containing the packs from both layers. With the original three MIDX layers, objects are laid out in the bitmap in the order they appear in their source pack, and the packs themselves are arranged according to the pseudo-pack order. In this case, that ordering is Y, X, Z, B, A, C.
But recall that the pseudo-pack ordering is defined by the order that packs appear in the MIDX, with the exception of the preferred pack, which sorts ahead of all other packs regardless of its position within the MIDX. In the above example, that means that pack 'Y' could be placed anywhere (so long as it is designated as preferred), however, all other packs must be placed in the location listed above.
Because that ordering isn't sorted lexicographically, it is impossible to compact MIDX layers in the above configuration without permuting the object-to-bit-position mapping. Changing this mapping would affect all bitmaps belonging to newer layers, rendering the bitmaps associated with MIDX #2 unreadable.
One of the goals of MIDX compaction is that we are able to shrink the length of the MIDX chain *without* invalidating bitmaps that belong to newer layers, and the lexicographic ordering constraint is at odds with this goal.
However, packs do not *need* to be lexicographically ordered within the MIDX. As far as I can gather, the only reason they are sorted lexically is to make it possible to perform a binary search over the pack names in a MIDX, necessary to make `midx_contains_pack()`'s performance logarithmic in the number of packs rather than linear.
Relax this constraint by allowing MIDX writes to proceed with packs that are not arranged in lexicographic order. `midx_contains_pack()` will lazily instantiate a `pack_names_sorted` array on the MIDX, which will be used to implement the binary search over pack names.
Note that this produces MIDXs which may be incompatible with earlier versions of Git that have stricter requirements on the layout of packs within a MIDX. This patch does *not* modify the version number of the MIDX format, since existing versions of Git already know to gracefully ignore a MIDX with packs that appear out-of-order.
Signed-off-by: Taylor Blau <me@ttaylorr.com> --- midx-write.c | 5 ----- midx.c | 28 ++++++++++++++++++++++------ midx.h | 1 + t/t5319-multi-pack-index.sh | 5 ----- 4 files changed, 23 insertions(+), 16 deletions(-)
diff --git a/midx-write.c b/midx-write.c index b262631ae45..55342fcb6dd 100644 --- a/midx-write.c +++ b/midx-write.c @@ -410,11 +410,6 @@ static int write_midx_pack_names(struct hashfile *f, void *data) if (ctx->info[i].expired) continue; - if (i && strcmp(ctx->info[i].pack_name, ctx->info[i - 1].pack_name) <= 0) - BUG("incorrect pack-file order: %s before %s", - ctx->info[i - 1].pack_name, - ctx->info[i].pack_name); - writelen = strlen(ctx->info[i].pack_name) + 1; hashwrite(f, ctx->info[i].pack_name, writelen); written += writelen; diff --git a/midx.c b/midx.c index f9b11de9ca9..4d5fe880649 100644 --- a/midx.c +++ b/midx.c @@ -209,11 +209,6 @@ static struct multi_pack_index *load_multi_pack_index_one(struct odb_source *sou if (!end) die(_("multi-pack-index pack-name chunk is too short")); cur_pack_name = end + 1; - - if (i && strcmp(m->pack_names[i], m->pack_names[i - 1]) <= 0) - die(_("multi-pack-index pack names out of order: '%s' before '%s'"), - m->pack_names[i - 1], - m->pack_names[i]); } trace2_data_intmax("midx", r, "load/num_packs", m->num_packs); @@ -411,6 +406,7 @@ void close_midx(struct multi_pack_index *m) } FREE_AND_NULL(m->packs); FREE_AND_NULL(m->pack_names); + FREE_AND_NULL(m->pack_names_sorted); free(m); } @@ -656,17 +652,37 @@ int cmp_idx_or_pack_name(const char *idx_or_pack_name, return strcmp(idx_or_pack_name, idx_name); } + +static int midx_pack_names_cmp(const void *a, const void *b, void *m_) +{ + struct multi_pack_index *m = m_; + return strcmp(m->pack_names[*(const size_t *)a], + m->pack_names[*(const size_t *)b]); +} + static int midx_contains_pack_1(struct multi_pack_index *m, const char *idx_or_pack_name) { uint32_t first = 0, last = m->num_packs; + if (!m->pack_names_sorted) { + uint32_t i; + + ALLOC_ARRAY(m->pack_names_sorted, m->num_packs); + + for (i = 0; i < m->num_packs; i++) + m->pack_names_sorted[i] = i; + + QSORT_S(m->pack_names_sorted, m->num_packs, midx_pack_names_cmp, + m); + } + while (first < last) { uint32_t mid = first + (last - first) / 2; const char *current; int cmp; - current = m->pack_names[mid]; + current = m->pack_names[m->pack_names_sorted[mid]]; cmp = cmp_idx_or_pack_name(idx_or_pack_name, current); if (!cmp) return 1; diff --git a/midx.h b/midx.h index e188ffeb578..39bf04b18e5 100644 --- a/midx.h +++ b/midx.h @@ -71,6 +71,7 @@ struct multi_pack_index { uint32_t num_packs_in_base; const char **pack_names; + size_t *pack_names_sorted; struct packed_git **packs; }; diff --git a/t/t5319-multi-pack-index.sh b/t/t5319-multi-pack-index.sh index ca020091dda..03676d37b98 100755 --- a/t/t5319-multi-pack-index.sh +++ b/t/t5319-multi-pack-index.sh @@ -450,11 +450,6 @@ test_expect_success 'verify invalid chunk offset' ' "improper chunk offset(s)" ' -test_expect_success 'verify packnames out of order' ' - corrupt_midx_and_verify $MIDX_BYTE_PACKNAME_ORDER "z" $objdir \ - "pack names out of order" -' - test_expect_success 'verify missing pack' ' corrupt_midx_and_verify $MIDX_BYTE_PACKNAME_ORDER "a" $objdir \ "failed to load pack"
-- 2.52.0.171.gd6a4e6b6955