Re: [PATCH 17/17] midx: enable reachability bitmaps during MIDX compaction

From: Taylor Blau <me@ttaylorr.com>
Date: Jan 13, 2026, 23:47 UTC
Message-ID: <aWbZopq71ZUXvUsr@nand.local>
In-Reply-To: <aTfOBz3ElQYi6j8i@pks.im>

On Tue, Dec 09, 2025 at 08:21:43AM +0100, Patrick Steinhardt wrote:

Show 8 quoted lines

> On Sat, Dec 06, 2025 at 03:31:50PM -0500, Taylor Blau wrote:
> > Enable callers to generate reachability bitmaps when performing MIDX
> > layer compaction by combining all existing bitmaps from the compacted
> > layers.
> >
> > Note that the because of the object/pack ordering described by the
>
> s/that the because/that because/

;-) great catch!

Show 17 quoted lines

> > previous commit, the pseudo-pack order for the compacted MIDX is the
> > same as concatenating the individual pseudo-pack orderings for each
> > layer in the compaction range.
> >
> > As a result, the only non-test or documentation change necessary is to
> > treat all objects as non-preferred during compaction so as not to
> > disturb the object ordering.
> >
> > In the future, we may want to adjust which commit(s) receive
> > reachability bitmaps when compacting multiple .bitmap files into one, or
> > even generate new bitmaps (e.g., if the references have moved
> > significantly since the .bitmap was generated). This commit only
> > implements combining all existing bitmaps in range together in order to
> > demonstrate and lay the groundwork for more exotic strategies.
>
> Will there also be a follow-up patch series that introduces geometric
> repacking for multi-pack indices?

That's the plan, though I have been calling it "incremental MIDX/bitmap" repacking. The idea is roughly what I presented on slides 80-90 of my Git Merge talk from last year[1].

The gist is the following:

 1. Perform a geometric repack of all non-MIDX'd packs, optionally
    including any packs in the top-most MIDX layer if it has more than M
    packs.

 2. Generate a new MIDX layer containing the result of that geometric
    repack.

 3. Perform layer compaction on the new chain in order to ensure that
    each layer has no more than 2x the number of packs as the layer
    above it.

This is a conceptual overview, so there are a few white lies here. Namely, we do not write out a MIDX containing the result of the geometric repack from the first step in all cases. If it would be compacted in the following step, we'll optimize out that write and instead write a layer whose contents is the result of the geometric repack and the contents of the layer(s) below.

Compaction is also done in a single pass, so we don't compact the same layer multiple times during a single repack.

The result is that we end up with a MIDX chain with two properties (see slide 131 for more details):

 - Newer layers contain a greater number of packs which tend to be
   smaller by object count than older layers.

 - Older layers contain a smaller number of packs which tend to be
   larger by object count than newer layers.

I have that working in a WIP-quality branch[2], which I have been using as a base to pull patches out of (which has yielded parts 3.1 and 3.2 thus far).

Show 16 quoted lines

> > @@ -216,6 +216,8 @@ static int cmd_multi_pack_index_compact(int argc, const char **argv,
> >
> >  	struct option *options;
> >  	static struct option builtin_multi_pack_index_compact_options[] = {
> > +		OPT_BIT(0, "bitmap", &opts.flags, N_("write multi-pack bitmap"),
> > +			MIDX_WRITE_BITMAP | MIDX_WRITE_REV_INDEX),
> >  		OPT_BIT(0, "incremental", &opts.flags,
> >  			N_("write a new incremental MIDX"), MIDX_WRITE_INCREMENTAL),
> >  		OPT_END(),
>
> Is this new flag actually incompatible with the incremental flag like
> you claimed in the preceding commit? I had the impression that it should
> be possible to write incremental bitmaps now.
>
> If that's not the case, we should probably have a call to
> `die_for_imcopatible_opt2()` somewhere.

It's not incompatible, the comment is just stale, thanks for pointing it out!

Thanks, Taylor

[1]: https://ttaylorr.com/presentations/git-merge-2025.pdf

[2]: 'tb/incremental-midx-part-3.wip' from my 'ttaylorr/git' fork on
     GitHub.