Skip to content

midx: incremental multi-pack indexes, part one

Taylor Blau git 3 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v3 Latest19 patches 1 replyIn review
  2. v219 patches 34 repliesSuperseded
  3. v119 patches 7 repliesSuperseded

Patches in v3 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/19Documentation: describe incremental MIDX formatDocumentation/technical/multi-pack-index.txt+103 -00 replies
2/19midx: add new fields for incremental MIDX chainsmidx.h+4 -00 replies
3/19midx: teach `nth_midxed_pack_int_id()` about incremental MIDXsmidx.c+21 -20 replies
4/19midx: teach `prepare_midx_pack()` about incremental MIDXsmidx.c+23 -50 replies
5/19midx: teach `nth_midxed_object_oid()` about incremental MIDXsmidx.c+3 -10 replies
6/19midx: teach `nth_bitmapped_pack()` about incremental MIDXsmidx.c+5 -30 replies
7/19midx: introduce `bsearch_one_midx()`midx.c midx.h object-name.c+71 -500 replies
8/19midx: teach `bsearch_midx()` about incremental MIDXsmidx.c+4 -10 replies
9/19midx: teach `nth_midxed_offset()` about incremental MIDXsmidx.c+2 -00 replies
10/19midx: teach `fill_midx_entry()` about incremental MIDXsmidx.c+2 -40 replies
11/19midx: remove unused `midx_locate_pack()`midx.c midx.h+2 -130 replies
12/19midx: teach `midx_contains_pack()` about incremental MIDXsmidx.c+10 -10 replies
13/19midx: teach `midx_preferred_pack()` about incremental MIDXsmidx.c+5 -20 replies
14/19midx: teach `midx_fanout_add_midx_fanout()` about incremental MIDXsmidx-write.c+8 -40 replies
15/19midx: support reading incremental MIDX chainsmidx.c midx.h packfile.c +1 more+201 -190 replies
16/19midx: implement verification support for incremental MIDXsmidx.c midx.h+32 -170 replies
17/19t: retire 'GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP'builtin/repack.c ci/run-build-and-tests.sh midx.h +7 more+13 -440 replies
18/19t/t5313-pack-bounds-checks.sh: prepare for sub-directoriest/t5313-pack-bounds-checks.sh+4 -40 replies
19/19midx: implement support for writing incremental MIDX chainsDocumentation/git-multi-pack-index.txt builtin/multi-pack-index.c builtin/repack.c +15 more+460 -1040 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v3 yet.

Read the v3 thread

Cover letter [PATCH v3 00/19] midx: incremental multi-pack indexes, part one

This series implements incremental MIDXs, which allow for storing a MIDX across multiple layers, each with their own distinct set of packs.

This round is also similar to the previous one, but is rebased on current 'master' (406f326d27 (The second batch, 2024-08-01)) and has been updated in response to review from Peff on the previous round.

As usual, a range-diff is below, but the main changes since last time are as follows:

- Documentation improvements to clarify what happens when both an incremental- and non-incremental MIDX are both present in a repository.

- Commit message typofix on 3/19 to fix an error in one of the technical examples.

- Dropped a custom 'local_pack_int_id' in 4/19 to make the remaining diff easier to read.

- Minor bugfix in 7/19 where we incorrectly terminated the object abbreviation disambiguation step for incremental MIDXs.

- Various additional bits of information in the commit message to explain anything that was subtle.

Thanks in advance for any review! :-)

Taylor Blau (19):
Documentation: describe incremental MIDX format
midx: add new fields for incremental MIDX chains
midx: teach nth_midxed_pack_int_id() about incremental MIDXs
midx: teach prepare_midx_pack() about incremental MIDXs
midx: teach nth_midxed_object_oid() about incremental MIDXs
midx: teach nth_bitmapped_pack() about incremental MIDXs
midx: introduce bsearch_one_midx()
midx: teach bsearch_midx() about incremental MIDXs
midx: teach nth_midxed_offset() about incremental MIDXs
midx: teach fill_midx_entry() about incremental MIDXs
midx: remove unused midx_locate_pack()
midx: teach midx_contains_pack() about incremental MIDXs
midx: teach midx_preferred_pack() about incremental MIDXs
midx: teach midx_fanout_add_midx_fanout() about incremental MIDXs
midx: support reading incremental MIDX chains
midx: implement verification support for incremental MIDXs
t: retire 'GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP' t/t5313-pack-bounds-checks.sh: prepare for sub-directories
midx: implement support for writing incremental MIDX chains

 Documentation/git-multi-pack-index.txt       |  11 +-
 Documentation/technical/multi-pack-index.txt | 103 +++++
 builtin/multi-pack-index.c                   |   2 +
 builtin/repack.c                             |   8 +-
 ci/run-build-and-tests.sh                    |   2 +-
 midx-write.c                                 | 326 ++++++++++++---
 midx.c                                       | 405 ++++++++++++++++---
 midx.h                                       |  26 +-
 object-name.c                                |  99 ++---
 packfile.c                                   |  21 +-
 packfile.h                                   |   4 +
 t/README                                     |   6 +-
 t/helper/test-read-midx.c                    |  24 +-
 t/lib-bitmap.sh                              |   6 +-
 t/lib-midx.sh                                |  28 ++
 t/t0410-partial-clone.sh                     |   2 -
 t/t5310-pack-bitmaps.sh                      |   4 -
 t/t5313-pack-bounds-checks.sh                |   8 +-
 t/t5319-multi-pack-index.sh                  |  30 +-
 t/t5326-multi-pack-bitmaps.sh                |   4 +-
 t/t5327-multi-pack-bitmaps-rev.sh            |   6 +-
 t/t5332-multi-pack-reuse.sh                  |   2 +
 t/t5334-incremental-multi-pack-index.sh      |  46 +++
 t/t7700-repack.sh                            |  48 +--
 24 files changed, 960 insertions(+), 261 deletions(-)
 create mode 100755 t/t5334-incremental-multi-pack-index.sh

Range-diff against v2:
1: 014588b3ec ! 1: 90b21b11ed Documentation: describe incremental MIDX format
@@ Documentation/technical/multi-pack-index.txt: Design Details
+extending the incremental MIDX format to support reachability bitmaps. +The design below specifically takes this into account, and support for +reachability bitmaps will be added in a future patch series. It is
-+omitted from this series for the same reason as above. ++omitted from the current implementation for the same reason as above.
++
+In brief, to support reachability bitmaps with the incremental MIDX +feature, the concept of the pseudo-pack order is extended across each
@@ Documentation/technical/multi-pack-index.txt: Design Details
+multi-pack-index chain. The multi-pack-index-$H2.midx file contains +the second layer of the chain, and so on.
+
++When both an incremental- and non-incremental MIDX are present, the ++non-incremental MIDX is always read first.
++
+=== Object positions for incremental MIDXs
+
+In the original multi-pack-index design, we refer to objects via their

 2:  337ebc6de7 =  2:  0d3b19c59f midx: add new fields for incremental MIDX chains
 3:  f449a72877 !  3:  5cd742b677 midx: teach `nth_midxed_pack_int_id()` about incremental MIDXs

@@ Commit message
objects contained in all layers of the incremental MIDX chain, not any particular layer. For example, consider MIDX chain with two individual MIDXs, one with 4 objects and another with 3 objects. If the MIDX with
- 4 objects appears earlier in the chain, then asking for pack "6" would
+ 4 objects appears earlier in the chain, then asking for object 6 would
return the second object in the MIDX with 3 objects.

[^2]: Building on the previous example, asking for object 6 in a MIDX
4: f88569c819 ! 4: 372104c73d midx: teach prepare_midx_pack() about incremental MIDXs

    @@ midx.c: static uint32_t midx_for_object(struct multi_pack_index **_m, uint32_t p
      		die(_("bad pack-int-id: %u (%u total packs)"),
     -		    pack_int_id, m->num_packs);
     +		    pack_int_id, m->num_packs + m->num_packs_in_base);
    - 
    --	if (m->packs[pack_int_id])
    ++
     +	*_m = m;
     +
     +	return pack_int_id - m->num_packs_in_base;
    @@ midx.c: static uint32_t midx_for_object(struct multi_pack_index **_m, uint32_t p
     +{
     +	struct strbuf pack_name = STRBUF_INIT;
     +	struct packed_git *p;
    -+	uint32_t local_pack_int_id = midx_for_pack(&m, pack_int_id);
     +
    -+	if (m->packs[local_pack_int_id])
    ++	pack_int_id = midx_for_pack(&m, pack_int_id);
    + 
    + 	if (m->packs[pack_int_id])
      		return 0;
    - 
    - 	strbuf_addf(&pack_name, "%s/pack/%s", m->object_dir,
    --		    m->pack_names[pack_int_id]);
    -+		    m->pack_names[local_pack_int_id]);
    - 
    - 	p = add_packed_git(pack_name.buf, pack_name.len, m->local);
    - 	strbuf_release(&pack_name);
    -@@ midx.c: int prepare_midx_pack(struct repository *r, struct multi_pack_index *m, uint32_t
    - 		return 1;
    - 
    - 	p->multi_pack_index = 1;
    --	m->packs[pack_int_id] = p;
    -+	m->packs[local_pack_int_id] = p;
    - 	install_packed_git(r, p);
    - 	list_add_tail(&p->mru, &r->objects->packed_git_mru);
    - 
 5:  ec57ff4349 =  5:  e68a3ceff9 midx: teach `nth_midxed_object_oid()` about incremental MIDXs
 6:  650b8c8c21 !  6:  ff2d7bc5ca midx: teach `nth_bitmapped_pack()` about incremental MIDXs

@@ Commit message
ID. Likewise, when reading the 'BTMP' chunk, use the MIDX-local offset when accessing the data within that chunk.

+ (Note that the both the call to prepare_midx_pack() and the assignment
+ of bp->pack_int_id both care about the global pack_int_id, so avoid
+ shadowing the given 'pack_int_id' parameter).
+

## midx.c ##
7: bfd1dadbf1 ! 7: 32c3fceada midx: introduce bsearch_one_midx()

    @@ object-name.c: static int match_hash(unsigned len, const unsigned char *a, const
      
     -	if (!num)
     -		return;
    -+		num = m->num_objects + m->num_objects_in_base;
    ++		if (!m->num_objects)
    ++			continue;
      
     -	bsearch_midx(&ds->bin_pfx, m, &first);
    -+		if (!num)
    -+			continue;
    ++		num = m->num_objects + m->num_objects_in_base;
      
     -	/*
     -	 * At this point, "first" is the location of the lowest object
 8:  38bd45bd24 =  8:  16db6c98ce midx: teach `bsearch_midx()` about incremental MIDXs
 9:  342ed56033 =  9:  761c7c59ba midx: teach `nth_midxed_offset()` about incremental MIDXs
10:  2b335c45ae = 10:  8366456d29 midx: teach `fill_midx_entry()` about incremental MIDXs
11:  22de5898f3 = 11:  909d927c47 midx: remove unused `midx_locate_pack()`
12:  fb60f2b022 = 12:  71127601b5 midx: teach `midx_contains_pack()` about incremental MIDXs
13:  38b642d404 = 13:  2f98ebb141 midx: teach `midx_preferred_pack()` about incremental MIDXs
14:  594386da10 ! 14:  550ae2dc93 midx: teach `midx_fanout_add_midx_fanout()` about incremental MIDXs

@@ Commit message
MIDX layers when dealing with an incremental MIDX chain by calling itself when given a MIDX with a non-NULL base_midx.

+ Note that after 0c5a62f14b (midx-write.c: do not read existing MIDX with
+ packs_to_include, 2024-06-11), we do not use this function with an
+ existing MIDX (incremental or not) when generating a MIDX with
+ --stdin-packs, and likewise for incremental MIDXs.
+
+ But it is still used when adding the fanout table from an incremental
+ MIDX when generating a non-incremental MIDX (without --stdin-packs, of
+ course).
+

## midx-write.c ##
15: dad130799c ! 15: 9ae1bc415e midx: support reading incremental MIDX chains
@@ Commit message
in the commit after next.)

The core of this change involves following the order specified in the
- MIDX chain and opening up MIDXs in the chain one-by-one, adding them to
- the previous layer's ->base_midx pointer at each step.
+ MIDX chain in reverse and opening up MIDXs in the chain one-by-one,
+ adding them to the previous layer's ->base_midx pointer at each step.

In order to implement this, the load_multi_pack_index() function is taught to call a new load_multi_pack_index_chain() function if loading

16:  ad976ef413 = 16:  3d4181df51 midx: implement verification support for incremental MIDXs
17:  23912425bf = 17:  3b268f91bf t: retire 'GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP'
18:  814da1916d = 18:  09d74f8942 t/t5313-pack-bounds-checks.sh: prepare for sub-directories
19:  e2b5961b45 = 19:  5d467d38a8 midx: implement support for writing incremental MIDX chains

base-commit: 406f326d271e0bacecdb00425422c5fa3f314930

Signature · 1 line
2.46.0.46.g406f326d27.dirty