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

[PATCH v3 10/17] midx: do not require packs to be sorted in lexicographic order

From
Taylor Blau <me@ttaylorr.com>
Date
Feb 24, 2026, 19:00 UTC
Message-ID
<3682bfd0e0872b9b8831d5c481db306e316c78ef.1771959555.git.me@ttaylorr.com>
In-Reply-To
<cover.1771959555.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.

This change produces MIDXs which may not be correctly read with external tools or older versions of Git. Though older versions of Git know how to gracefully degrade and ignore any MIDX(s) they consider corrupt, external tools may not be as robust. To avoid unintentionally breaking any such tools, guard this change behind a version bump in the MIDX's on-disk format.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/gitformat-pack.adoc |  8 ++++++--
 midx-write.c                      | 26 ++++++++++++++++++++++----
 midx.c                            | 31 ++++++++++++++++++++++++++++---
 midx.h                            |  4 +++-
 t/t5319-multi-pack-index.sh       | 16 ++++++++++------
 5 files changed, 69 insertions(+), 16 deletions(-)
diff --git a/Documentation/gitformat-pack.adoc b/Documentation/gitformat-pack.adoc
index 1b4db4aa611..3416edceab8 100644
--- a/Documentation/gitformat-pack.adoc
+++ b/Documentation/gitformat-pack.adoc
@@ -374,7 +374,9 @@ HEADER:
 	    The signature is: {'M', 'I', 'D', 'X'}
 
 	1-byte version number:
-	    Git only writes or recognizes version 1.
+	    Git writes the version specified by the "midx.version"
+	    configuration option, which defaults to 2. It recognizes
+	    both versions 1 and 2.
 
 	1-byte Object Id Version
 	    We infer the length of object IDs (OIDs) from this value:
@@ -413,7 +415,9 @@ CHUNK DATA:
 	    strings. There is no extra padding between the filenames,
 	    and they are listed in lexicographic order. The chunk itself
 	    is padded at the end with between 0 and 3 NUL bytes to make the
-	    chunk size a multiple of 4 bytes.
+	    chunk size a multiple of 4 bytes. Version 1 MIDXs are required to
+	    list their packs in lexicographic order, but version 2 MIDXs may
+	    list their packs in any arbitrary order.
 
 	Bitmapped Packfiles (ID: {'B', 'T', 'M', 'P'})
 	    Stores a table of two 4-byte unsigned integers in network order.
diff --git a/midx-write.c b/midx-write.c
index 8a54644e427..5c8700065a1 100644
--- a/midx-write.c
+++ b/midx-write.c
@@ -36,10 +36,13 @@ extern int cmp_idx_or_pack_name(const char *idx_or_pack_name,
 
 static size_t write_midx_header(const struct git_hash_algo *hash_algo,
 				struct hashfile *f, unsigned char num_chunks,
-				uint32_t num_packs)
+				uint32_t num_packs, int version)
 {
+	if (version != MIDX_VERSION_V1 && version != MIDX_VERSION_V2)
+		BUG("unexpected MIDX version: %d", version);
+
 	hashwrite_be32(f, MIDX_SIGNATURE);
-	hashwrite_u8(f, MIDX_VERSION);
+	hashwrite_u8(f, version);
 	hashwrite_u8(f, oid_version(hash_algo));
 	hashwrite_u8(f, num_chunks);
 	hashwrite_u8(f, 0); /* unused */
@@ -105,6 +108,8 @@ struct write_midx_context {
 
 	uint32_t preferred_pack_idx;
 
+	int version; /* must be MIDX_VERSION_V1 or _V2 */
+
 	int incremental;
 	uint32_t num_multi_pack_indexes_before;
 
@@ -410,7 +415,9 @@ 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)
+		if (ctx->version == MIDX_VERSION_V1 &&
+		    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);
@@ -1025,6 +1032,12 @@ static bool midx_needs_update(struct multi_pack_index *midx, struct write_midx_c
 	if (!midx_checksum_valid(midx))
 		goto out;
 
+	/*
+	 * If the version differs, we need to update.
+	 */
+	if (midx->version != ctx->version)
+		goto out;
+
 	/*
 	 * Ignore incremental updates for now. The assumption is that any
 	 * incremental update would be either empty (in which case we will bail
@@ -1100,6 +1113,7 @@ static int write_midx_internal(struct write_midx_opts *opts)
 	struct tempfile *incr;
 	struct write_midx_context ctx = {
 		.preferred_pack_idx = NO_PREFERRED_PACK,
+		.version = MIDX_VERSION_V2,
 	 };
 	struct multi_pack_index *midx_to_free = NULL;
 	int bitmapped_packs_concat_len = 0;
@@ -1114,6 +1128,10 @@ static int write_midx_internal(struct write_midx_opts *opts)
 	ctx.repo = r;
 	ctx.source = opts->source;
 
+	repo_config_get_int(ctx.repo, "midx.version", &ctx.version);
+	if (ctx.version != MIDX_VERSION_V1 && ctx.version != MIDX_VERSION_V2)
+		die(_("unknown MIDX version: %d"), ctx.version);
+
 	ctx.incremental = !!(opts->flags & MIDX_WRITE_INCREMENTAL);
 
 	if (ctx.incremental)
@@ -1445,7 +1463,7 @@ static int write_midx_internal(struct write_midx_opts *opts)
 	}
 
 	write_midx_header(r->hash_algo, f, get_num_chunks(cf),
-			  ctx.nr - dropped_packs);
+			  ctx.nr - dropped_packs, ctx.version);
 	write_chunkfile(cf, &ctx);
 
 	finalize_hashfile(f, midx_hash, FSYNC_COMPONENT_PACK_METADATA,
diff --git a/midx.c b/midx.c
index bae45892323..c1b9658240d 100644
--- a/midx.c
+++ b/midx.c
@@ -149,7 +149,7 @@ static struct multi_pack_index *load_multi_pack_index_one(struct odb_source *sou
 		      m->signature, MIDX_SIGNATURE);
 
 	m->version = m->data[MIDX_BYTE_FILE_VERSION];
-	if (m->version != MIDX_VERSION)
+	if (m->version != MIDX_VERSION_V1 && m->version != MIDX_VERSION_V2)
 		die(_("multi-pack-index version %d not recognized"),
 		      m->version);
 
@@ -210,7 +210,8 @@ static struct multi_pack_index *load_multi_pack_index_one(struct odb_source *sou
 			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)
+		if (m->version == MIDX_VERSION_V1 &&
+		    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]);
@@ -411,6 +412,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);
 }
 
@@ -655,17 +657,40 @@ 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->version == MIDX_VERSION_V2 && !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];
+		if (m->pack_names_sorted)
+			current = m->pack_names[m->pack_names_sorted[mid]];
+		else
+			current = m->pack_names[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 a39bcc9d03f..aa99a6cb215 100644
--- a/midx.h
+++ b/midx.h
@@ -11,7 +11,8 @@ struct git_hash_algo;
 struct odb_source;
 
 #define MIDX_SIGNATURE 0x4d494458 /* "MIDX" */
-#define MIDX_VERSION 1
+#define MIDX_VERSION_V1 1
+#define MIDX_VERSION_V2 2
 #define MIDX_BYTE_FILE_VERSION 4
 #define MIDX_BYTE_HASH_VERSION 5
 #define MIDX_BYTE_NUM_CHUNKS 6
@@ -71,6 +72,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 efeab4d22b7..250d21dbd67 100755
--- a/t/t5319-multi-pack-index.sh
+++ b/t/t5319-multi-pack-index.sh
@@ -21,7 +21,7 @@ midx_read_expect () {
 	EXTRA_CHUNKS="$5"
 	{
 		cat <<-EOF &&
-		header: 4d494458 1 $HASH_LEN $NUM_CHUNKS $NUM_PACKS
+		header: 4d494458 2 $HASH_LEN $NUM_CHUNKS $NUM_PACKS
 		chunks: pack-names oid-fanout oid-lookup object-offsets$EXTRA_CHUNKS
 		num_objects: $NUM_OBJECTS
 		packs:
@@ -512,11 +512,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"
@@ -578,6 +573,15 @@ test_expect_success 'verify incorrect checksum' '
 		$objdir "incorrect checksum"
 '
 
+test_expect_success 'setup for v1-specific fsck tests' '
+	git -c midx.version=1 multi-pack-index write
+'
+
+test_expect_success 'verify packnames out of order (v1)' '
+	corrupt_midx_and_verify $MIDX_BYTE_PACKNAME_ORDER "z" $objdir \
+		"pack names out of order"
+'
+
 test_expect_success 'repack progress off for redirected stderr' '
 	GIT_PROGRESS_DELAY=0 git multi-pack-index --object-dir=$objdir repack 2>err &&
 	test_line_count = 0 err

-- 
2.53.0.171.gde83996e422
Previous: Taylor BlauNext: Taylor Blau
Message 92 of 99 in “midx: incremental MIDX/bitmap layer compaction”
  1. 00/17 midx: incremental MIDX/bitmap layer compactionTaylor Blau, Dec 6, 2025
  2. 01/17 midx: mark `get_midx_checksum()` arguments as constTaylor Blau, Dec 6, 2025
  3. Patrick SteinhardtDec 8, 2025
  4. Taylor BlauDec 9, 2025
  5. 02/17 midx: split `get_midx_checksum()` by adding `get_midx_hash()`Taylor Blau, Dec 6, 2025
  6. Patrick SteinhardtDec 8, 2025
  7. Taylor BlauDec 9, 2025
  8. Taylor BlauDec 9, 2025
  9. Patrick SteinhardtDec 9, 2025
  10. Taylor BlauJan 13, 2026
  11. 03/17 builtin/multi-pack-index.c: make '--progress' a common optionTaylor Blau, Dec 6, 2025
  12. 04/17 git-multi-pack-index(1): remove non-existent incompatibilityTaylor Blau, Dec 6, 2025
  13. 05/17 git-multi-pack-index(1): align SYNOPSIS with 'git multi-pack-index -h'Taylor Blau, Dec 6, 2025
  14. 06/17 t/t5319-multi-pack-index.sh: fix copy-and-paste error in t5319.39Taylor Blau, Dec 6, 2025
  15. 07/17 midx-write.c: don't use `pack_perm` when assigning `bitmap_pos`Taylor Blau, Dec 6, 2025
  16. Patrick SteinhardtDec 8, 2025
  17. Taylor BlauDec 9, 2025
  18. 08/17 midx-write.c: introduce `struct write_midx_opts`Taylor Blau, Dec 6, 2025
  19. Patrick SteinhardtDec 8, 2025
  20. Taylor BlauDec 9, 2025
  21. 09/17 midx: do not require packs to be sorted in lexicographic orderTaylor Blau, Dec 6, 2025
  22. Patrick SteinhardtDec 8, 2025
  23. Taylor BlauDec 9, 2025
  24. Taylor BlauDec 9, 2025
  25. 10/17 git-compat-util.h: introduce `u32_add()`Taylor Blau, Dec 6, 2025
  26. Patrick SteinhardtDec 8, 2025
  27. Taylor BlauDec 9, 2025
  28. 11/17 midx-write.c: introduce `midx_pack_perm()` helperTaylor Blau, Dec 6, 2025
  29. 12/17 midx-write.c: extract `fill_pack_from_midx()`Taylor Blau, Dec 6, 2025
  30. 13/17 midx-write.c: enumerate `pack_int_id` values directlyTaylor Blau, Dec 6, 2025
  31. Patrick SteinhardtDec 8, 2025
  32. Taylor BlauDec 9, 2025
  33. 14/17 midx-write.c: factor fanout layering from `compute_sorted_entries()`Taylor Blau, Dec 6, 2025
  34. 15/17 t/helper/test-read-midx.c: plug memory leak when selecting layerTaylor Blau, Dec 6, 2025
  35. Patrick SteinhardtDec 8, 2025
  36. Taylor BlauDec 9, 2025
  37. 16/17 midx: implement MIDX compactionTaylor Blau, Dec 6, 2025
  38. Patrick SteinhardtDec 9, 2025
  39. Taylor BlauJan 13, 2026
  40. 17/17 midx: enable reachability bitmaps during MIDX compactionTaylor Blau, Dec 6, 2025
  41. Patrick SteinhardtDec 9, 2025
  42. Taylor BlauJan 13, 2026
  43. 00/18 midx: incremental MIDX/bitmap layer compactionTaylor Blau, Jan 14, 2026
  44. 01/18 midx: mark `get_midx_checksum()` arguments as constTaylor Blau, Jan 14, 2026
  45. 02/18 midx: rename `get_midx_checksum()` to `midx_get_checksum_hash()`Taylor Blau, Jan 14, 2026
  46. 03/18 midx: introduce `midx_get_checksum_hex()`Taylor Blau, Jan 14, 2026
  47. 04/18 builtin/multi-pack-index.c: make '--progress' a common optionTaylor Blau, Jan 14, 2026
  48. 05/18 git-multi-pack-index(1): remove non-existent incompatibilityTaylor Blau, Jan 14, 2026
  49. 06/18 git-multi-pack-index(1): align SYNOPSIS with 'git multi-pack-index -h'Taylor Blau, Jan 14, 2026
  50. 07/18 t/t5319-multi-pack-index.sh: fix copy-and-paste error in t5319.39Taylor Blau, Jan 14, 2026
  51. 08/18 midx-write.c: don't use `pack_perm` when assigning `bitmap_pos`Taylor Blau, Jan 14, 2026
  52. Junio C HamanoJan 14, 2026
  53. Taylor BlauJan 14, 2026
  54. 09/18 midx-write.c: introduce `struct write_midx_opts`Taylor Blau, Jan 14, 2026
  55. 10/18 midx: do not require packs to be sorted in lexicographic orderTaylor Blau, Jan 14, 2026
  56. Junio C HamanoJan 14, 2026
  57. Taylor BlauJan 14, 2026
  58. Patrick SteinhardtJan 27, 2026
  59. Taylor BlauFeb 24, 2026
  60. 11/18 git-compat-util.h: introduce `u32_add()`Taylor Blau, Jan 14, 2026
  61. Junio C HamanoJan 14, 2026
  62. Taylor BlauJan 14, 2026
  63. Taylor BlauJan 15, 2026
  64. Patrick SteinhardtJan 21, 2026
  65. Taylor BlauJan 21, 2026
  66. rsbecker@nexbridge.comJan 22, 2026
  67. Junio C HamanoJan 22, 2026
  68. Jeff KingFeb 23, 2026
  69. Taylor BlauFeb 24, 2026
  70. 12/18 midx-write.c: introduce `midx_pack_perm()` helperTaylor Blau, Jan 14, 2026
  71. 13/18 midx-write.c: extract `fill_pack_from_midx()`Taylor Blau, Jan 14, 2026
  72. 14/18 midx-write.c: enumerate `pack_int_id` values directlyTaylor Blau, Jan 14, 2026
  73. 15/18 midx-write.c: factor fanout layering from `compute_sorted_entries()`Taylor Blau, Jan 14, 2026
  74. 16/18 t/helper/test-read-midx.c: plug memory leak when selecting layerTaylor Blau, Jan 14, 2026
  75. 17/18 midx: implement MIDX compactionTaylor Blau, Jan 14, 2026
  76. Patrick SteinhardtJan 27, 2026
  77. Taylor BlauJan 27, 2026
  78. 18/18 midx: enable reachability bitmaps during MIDX compactionTaylor Blau, Jan 14, 2026
  79. Junio C HamanoFeb 20, 2026
  80. Jeff KingFeb 23, 2026
  81. Taylor BlauFeb 24, 2026
  82. 00/17 midx: incremental MIDX/bitmap layer compactionTaylor Blau, Feb 24, 2026
  83. 01/17 midx: mark `get_midx_checksum()` arguments as constTaylor Blau, Feb 24, 2026
  84. 02/17 midx: rename `get_midx_checksum()` to `midx_get_checksum_hash()`Taylor Blau, Feb 24, 2026
  85. 03/17 midx: introduce `midx_get_checksum_hex()`Taylor Blau, Feb 24, 2026
  86. 04/17 builtin/multi-pack-index.c: make '--progress' a common optionTaylor Blau, Feb 24, 2026
  87. 05/17 git-multi-pack-index(1): remove non-existent incompatibilityTaylor Blau, Feb 24, 2026
  88. 06/17 git-multi-pack-index(1): align SYNOPSIS with 'git multi-pack-index -h'Taylor Blau, Feb 24, 2026
  89. 07/17 t/t5319-multi-pack-index.sh: fix copy-and-paste error in t5319.39Taylor Blau, Feb 24, 2026
  90. 08/17 midx-write.c: don't use `pack_perm` when assigning `bitmap_pos`Taylor Blau, Feb 24, 2026
  91. 09/17 midx-write.c: introduce `struct write_midx_opts`Taylor Blau, Feb 24, 2026
  92. 10/17 midx: do not require packs to be sorted in lexicographic orderTaylor Blau, Feb 24, 2026
  93. 11/17 midx-write.c: introduce `midx_pack_perm()` helperTaylor Blau, Feb 24, 2026
  94. 13/17 midx-write.c: enumerate `pack_int_id` values directlyTaylor Blau, Feb 24, 2026
  95. 14/17 midx-write.c: factor fanout layering from `compute_sorted_entries()`Taylor Blau, Feb 24, 2026
  96. 15/17 t/helper/test-read-midx.c: plug memory leak when selecting layerTaylor Blau, Feb 24, 2026
  97. 16/17 midx: implement MIDX compactionTaylor Blau, Feb 24, 2026
  98. 17/17 midx: enable reachability bitmaps during MIDX compactionTaylor Blau, Feb 24, 2026
  99. 12/17 midx-write.c: extract `fill_pack_from_midx()`Taylor Blau, Feb 24, 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.