This series is based on 'master', with an additional merge between
tb/incremental-midx-part-1[1] and my newer series to fix a handful of
bugs related to pseudo-merge bitmaps[2].
This is the second of three series to implement support for incremental
multi-pack indexes (MIDXs). This series brings support for bitmaps that
are tied to incremental MIDXs in addition to regular MIDX bitmaps.
The details are laid out in the commits themselves, but the high-level
approach is as follows:
- Each layer in the incremental MIDX chain has its own corresponding
*.bitmap file. Each bitmap contains commits / pseudo-merges which
are selected only from the commits in that layer. Likewise, only
that layer's objects are written in the type-level bitmaps.
- The reachability traversal is only conducted on the top-most bitmap
corresponding to the most recent layer in the incremental MIDX
chain. Earlier layers may be consulted to retrieve commit /
pseudo-merge reachability bitmaps, but only the top-most bitmap's
"result" and "haves" fields are used.
- In essence, the top-most bitmap is the only one that "matters", and
earlier bitmaps are merely used to look up commit and pseudo-merge
bitmaps from that layer.
- Whenever we need to look at the type-level bitmaps corresponding to
the whole incremental MIDX chain, a new "ewah_or_iterator" is used.
This works in concept like a typical ewah_iterator, except works
over many EWAH bitmaps in parallel, OR-ing their results together
before returning them to the user.
In effect, this allows us to treat the union of all type-level
bitmaps (each of which only stores information about the objects its
corresponding layer within the incremental MIDX chain) as a single
type-level bitmap corresponding to all of the objects across every
layer of the incremental MIDX chain.
The sum total of this series is that we are able to append new commits /
pseudo-merges to a repository's reachability bitmaps without having to
rewrite existing bitmaps, making the operation much cheaper to perform
in large repositories.
The series is laid out roughly as follows:
- The first patch describes the technical details of incremental MIDX
bitmaps.
- The second patch adjusts the pack-revindex internals to prepare for
incremental MIDX bitmaps.
- The next seven patches adjust various components of the pack-bitmap
internals to do the same.
- The next three patches introduce and adjust callers to use the
ewah_or_iterator (as above).
- The final patch implements writing incremental MIDX bitmaps, and
introduces tests.
After this series, the remaining goals for this project include being
able to compact contiguous runs of incremental MIDX layers into a single
layer to support growing the chain of MIDX layers without the chain
itself becoming too long.
Thanks in advance for your review!
[1]: https://lore.kernel.org/git/cover.1722958595.git.me@xxxxxxxxxxxx/
[2]: https://lore.kernel.org/git/cover.1723743050.git.me@xxxxxxxxxxxx/
Taylor Blau (13):
Documentation: describe incremental MIDX bitmaps
pack-revindex: prepare for incremental MIDX bitmaps
pack-bitmap.c: open and store incremental bitmap layers
pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs
pack-bitmap.c: teach `show_objects_for_type()` about incremental MIDXs
pack-bitmap.c: support bitmap pack-reuse with incremental MIDXs
pack-bitmap.c: teach `rev-list --test-bitmap` about incremental MIDXs
pack-bitmap.c: compute disk-usage with incremental MIDXs
pack-bitmap.c: apply pseudo-merge commits with incremental MIDXs
ewah: implement `struct ewah_or_iterator`
pack-bitmap.c: keep track of each layer's type bitmaps
pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators
midx: implement writing incremental MIDX bitmaps
Documentation/technical/multi-pack-index.txt | 64 ++++
builtin/pack-objects.c | 3 +-
ewah/ewah_bitmap.c | 33 ++
ewah/ewok.h | 12 +
midx-write.c | 35 +-
pack-bitmap-write.c | 65 +++-
pack-bitmap.c | 328 ++++++++++++++-----
pack-bitmap.h | 4 +-
pack-revindex.c | 32 +-
t/t5334-incremental-multi-pack-index.sh | 84 +++++
10 files changed, 548 insertions(+), 112 deletions(-)
base-commit: f28e4ef872c247b0b35f48b1c3d2c5f77753b908
--
2.46.0.86.ge766d390f0.dirty
