[00/22] multi-pack reachability bitmaps

Message

Taylor Blau April 9, 2021, 6:10 p.m. UTC

This series implements multi-pack reachability bitmaps. It is based on
'master' after merging 'tb/pack-preferred-tips-to-give-bitmap'.

This is an extension of the classic single-pack bitmaps. Instead of
mapping between objects and bit positions according to each object's
pack-relative position, multi-pack bitmaps use each object's position in
a kind of "pseudo pack".

The pseudo pack doesn't refer to a physical packfile, but instead a
conceptual ordering of objects in a multi-pack index. This ordering is
reflected in the MIDX's .rev file, which is used extensively to power
multi-pack bitmaps.

This somewhat lengthy series is organized as follows:

  - The first eight patches are cleanup and preparation.

  - The next three patches factor out functions which have different
    implementations based on whether a bitmap is tied to a pack or MIDX.

  - The next two patches implement support for reading and writing
    multi-pack bitmaps.

  - The remaining tests prepare for a new
    GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP mode of running the test
    suite, and add new tests covering the new multi-pack bitmap
    behavior.

You can experiment with the new functionality by running "git
multi-pack-index write --bitmap", which updates the multi-pack index (if
necessary), and writes out a corresponding .bitmap file. Eventually,
support for invoking the above during "git repack" will be introduced,
but this is done in a separate series.

These patches have been extracted from a version which has been running
on every repository on GitHub for the past few weeks.

Thanks in advance for your review (including on all of the many series leading
up to this one).

Jeff King (1):
  t5310: disable GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP

Taylor Blau (21):
  pack-bitmap.c: harden 'test_bitmap_walk()' to check type bitmaps
  pack-bitmap-write.c: gracefully fail to write non-closed bitmaps
  pack-bitmap-write.c: free existing bitmaps
  Documentation: build 'technical/bitmap-format' by default
  Documentation: describe MIDX-based bitmaps
  midx: make a number of functions non-static
  midx: clear auxiliary .rev after replacing the MIDX
  midx: respect 'core.multiPackIndex' when writing
  pack-bitmap.c: introduce 'bitmap_num_objects()'
  pack-bitmap.c: introduce 'nth_bitmap_object_oid()'
  pack-bitmap.c: introduce 'bitmap_is_preferred_refname()'
  pack-bitmap: read multi-pack bitmaps
  pack-bitmap: write multi-pack bitmaps
  t5310: move some tests to lib-bitmap.sh
  t/helper/test-read-midx.c: add --checksum mode
  t5326: test multi-pack bitmap behavior
  t5319: don't write MIDX bitmaps in t5319
  t7700: update to work with MIDX bitmap test knob
  midx: respect 'GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP'
  p5310: extract full and partial bitmap tests
  p5326: perf tests for MIDX bitmaps

 Documentation/Makefile                       |   1 +
 Documentation/git-multi-pack-index.txt       |  12 +-
 Documentation/technical/bitmap-format.txt    |  72 ++-
 Documentation/technical/multi-pack-index.txt |  10 +-
 builtin/multi-pack-index.c                   |   2 +
 builtin/pack-objects.c                       |  15 +-
 builtin/repack.c                             |  13 +-
 ci/run-build-and-tests.sh                    |   1 +
 midx.c                                       | 216 ++++++++-
 midx.h                                       |   5 +
 pack-bitmap-write.c                          |  79 +++-
 pack-bitmap.c                                | 463 +++++++++++++++++--
 pack-bitmap.h                                |   8 +-
 packfile.c                                   |   2 +-
 t/README                                     |   4 +
 t/helper/test-read-midx.c                    |  16 +-
 t/lib-bitmap.sh                              | 216 +++++++++
 t/perf/lib-bitmap.sh                         |  69 +++
 t/perf/p5310-pack-bitmaps.sh                 |  65 +--
 t/perf/p5326-multi-pack-bitmaps.sh           |  43 ++
 t/t5310-pack-bitmaps.sh                      | 208 +--------
 t/t5319-multi-pack-index.sh                  |   3 +-
 t/t5326-multi-pack-bitmaps.sh                | 278 +++++++++++
 t/t7700-repack.sh                            |  18 +-
 24 files changed, 1435 insertions(+), 384 deletions(-)
 create mode 100644 t/perf/lib-bitmap.sh
 create mode 100755 t/perf/p5326-multi-pack-bitmaps.sh
 create mode 100755 t/t5326-multi-pack-bitmaps.sh