Re: [PATCH 16/17] midx: implement MIDX compaction

[Taylor Blau <me@ttaylorr.com>]

On Tue, Dec 09, 2025 at 08:21:32AM +0100, Patrick Steinhardt wrote:
> On Sat, Dec 06, 2025 at 03:31:47PM -0500, Taylor Blau wrote:
> > diff --git a/Documentation/git-multi-pack-index.adoc b/Documentation/git-multi-pack-index.adoc
> > index 164cf1f2291..a9664e77411 100644
> > --- a/Documentation/git-multi-pack-index.adoc
> > +++ b/Documentation/git-multi-pack-index.adoc
> > @@ -12,6 +12,8 @@ SYNOPSIS
> >  'git multi-pack-index' [<options>] write [--preferred-pack=<pack>]
> >  		         [--[no-]bitmap] [--[no-]incremental] [--[no-]stdin-packs]
> >  		         [--refs-snapshot=<path>]
> > +'git multi-pack-index' [<options>] compact [--[no-]incremental]
> > +		         <from> <to>
> >  'git multi-pack-index' [<options>] verify
> >  'git multi-pack-index' [<options>] expire
> >  'git multi-pack-index' [<options>] repack [--batch-size=<size>]
> > @@ -83,6 +85,17 @@ marker).
> >  		necessary.
> >  --
> >
> > +compact::
> > +	Write a new MIDX layer containing only objects and packs present
> > +	in the range `<from>` to `<to>`, where both arguments are
> > +	checksums of existing layers in the MIDX chain.
> > ++
> > +--
> > +	--incremental::
> > +		Write the result to a MIDX chain instead of writing a
> > +		stand-alone MIDX. Incompatible with `--bitmap`.
>
> Interesting. What would happen if you compact a subrange of the MIDX
> chain without incremental? Would the MIDX be completely replaced with a
> MIDX that only covers these packs?

That's right.

> Also, the "--bitmap" flag does not exist yet, so the second sentence
> probably needs to be introduced in the next commit.

Ah, great catch -- I removed that line here. I don't think it needs to
be readded in the following commit, though, since that patch introduces
"--bitmap" and makes it compatible with MIDX compaction.

> > +	if (!from_midx)
> > +		die(_("could not find MIDX 'from': %s"), argv[0]);
> > +	if (!to_midx)
> > +		die(_("could not find MIDX 'to': %s"), argv[1]);
> > +
> > +	ret = write_midx_file_compact(source, from_midx, to_midx, opts.flags);
> > +
> > +	return ret;
> > +}
>
> Is it valid if `from_midx == to_midx`?

Yes, that would result in a noop write.

> > +	while (m != ctx->compact_from->base_midx) {
> > +		uint32_t pack_int_id, preferred_pack_id;
> > +		uint32_t i;
> > +
> > +		if (bitmap_order) {
> > +			if (midx_preferred_pack(m, &preferred_pack_id) < 0)
> > +				die(_("could not determine preferred pack"));
>
> `midx_preferred_pack()` only returns a valid pack ID in case we've got a
> reverse index, and as far as I understand we seem to only generate those
> when computing bitmaps. I assume that this means that we can only
> compact MIDX layers in bitmap order if they already were in bitmap order
> before?
>
> That would at least also make sense. We of course cannot randomly change
> the order in the middle of our layers, as that would break later layers
> that build on top.

Indeed, we only generate a reverse index for a MIDX if we are writing it
with bitmaps, since there is no other purpose for having a revindex
outside of reachability bitmaps.

So if we have a bitmap and are compacting, then we need to retain the
order of the packs as they appear in the pre-compaction pseudo-pack
order to avoid permuting the bits corresponding to those objects. In
other words, you're correct in saying that we cannot start writing
bitmaps during compaction if we did not have bitmaps to begin with
pre-compaction.

> > +		for (i = m->num_packs_in_base;
> > +		     i < m->num_packs_in_base + m->num_packs; i++) {
> > +			if (preferred_pack_id == i)
> > +				continue;
> > +
> > +			if (fill_pack_from_midx(&ctx->info[pack_int_id++], m,
> > +						i) < 0)
> > +				return -1;
> > +		}
> > +
>
> So the condition that should hold after this loop is `pack_int_id ==
> m->num_packs`. Which is somewhat obvious: we skip one pack, but that
> pack is the preferred pack that we have populated first.

Exactly!

> > @@ -1101,11 +1216,18 @@ static int write_midx_internal(struct write_midx_opts *opts)
> >  			 */
> >  			if (ctx.incremental)
> >  				ctx.base_midx = m;
> > -			else if (!opts->packs_to_include)
> > +			if (!opts->packs_to_include)
> >  				ctx.m = m;
>
> I'm a bit surprised by this change here. I would've expected that we
> never pass `packs_to_include` when compacting, so why is this change
> necessary?

Right, we do not pass packs_to_include here during compaction. But if we
are doing an incremental compaction, then we do want to assign ctx.m in
addition to ctx.base_midx.

> > diff --git a/t/t5335-compact-multi-pack-index.sh b/t/t5335-compact-multi-pack-index.sh
> > new file mode 100755
> > index 00000000000..f889af7fb1d
> > --- /dev/null
> > +++ b/t/t5335-compact-multi-pack-index.sh
> > @@ -0,0 +1,102 @@
> > +#!/bin/sh
> > +
> > +test_description='multi-pack-index compaction'
> > +
> > +. ./test-lib.sh
> > +
> > +GIT_TEST_MULTI_PACK_INDEX=0
> > +GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP=0
> > +GIT_TEST_MULTI_PACK_INDEX_WRITE_INCREMENTAL=0
> > +
> > +objdir=.git/objects
> > +packdir=$objdir/pack
> > +midxdir=$packdir/multi-pack-index.d
> > +midx_chain=$midxdir/multi-pack-index-chain
> > +
> > +nth_line() {
> > +	local n="$1"
> > +	shift
> > +	awk "NR==$n" "$@"
> > +}
> > +
> > +write_packs () {
> > +	for c in "$@"
> > +	do
> > +		test_commit "$c" &&
>
> Nit: it might be sensible to disable housekeeping here. You strongly
> depend on the on-disk shape of the objects, so if you by chance wrote
> two objects starting with "17" we'd end up repacking and racing.
>
> I've also got an upcoming patch series in mindthat I've got cooking to
> make geometric compaction the default for auto-maintenance. We've got
> many test suites that implicitly rely on the current algorithm used by
> git-gc(1), so I'd love to avoid adding more.

I'm not sure I follow what you mean by "housekeeping" here. Are you
referring to maintenance.auto? If so, we shouldn't be writing so many
packs as to trigger that during these tests, but I can disable it as a
sanity check just in case.

> [snip]
> > +test_expect_success 'MIDX compaction with lex-ordered pack names' '
> > +	git init midx-compact-lex-order &&
> > +	(
> > +		cd midx-compact-lex-order &&
> > +
> > +		write_packs A B C D E &&
> > +		test_line_count = 5 $midx_chain &&
> > +
> > +		git multi-pack-index compact --incremental \
> > +			"$(nth_line 2 "$midx_chain")" \
> > +			"$(nth_line 4 "$midx_chain")" &&
> > +		test_line_count = 3 $midx_chain &&
> > +
> > +		test_midx_layer_packs "$(nth_line 1 "$midx_chain")" A &&
> > +		test_midx_layer_packs "$(nth_line 2 "$midx_chain")" B C D &&
> > +		test_midx_layer_packs "$(nth_line 3 "$midx_chain")" E &&
> > +
> > +		test_midx_layer_object_uniqueness
> > +	)
> > +'
>
> It would be nice to also test for requests that don't make sense: "from"
> larger than "to", "from == to", missing "from" or "foo" and so on.

All good suggestions, thanks!

Thanks,
Taylor