[PATCH 0/5] packfile: harden handling of packs with duplicate entries

[Taylor Blau <ttaylorr@openai.com>]

Packfiles containing duplicate object entries are unusual, but Git
already accepts them outside of strict indexing. Both pack indexes and
reverse indexes maintain a 1-to-1 mapping between themselves and the
physical layout of objects in the pack (including duplicate).

While testing packs containing duplicate objects with MIDXs and MIDX
bitmaps, I found various bugs which are addressed by this series. It is
organized as follows:

- The first patch establishes that reverse indexes already do the right
  thing: they retain duplicate .idx rows. So asking cat-file to produce
  the on-disk size of some object with '%(objectsize:disk)' produces the
  right answer (even in cases like asking for the on-disk size of object
  'B' in a pack layout like [A, B, A, C]).

- The second fixes a bug exposed when ordinary 'REF_DELTA' lookup
  chooses a duplicate representation of some object that creates a
  cycle, even when a different copy of that same object could resolve
  the delta chain without cycles.

  Importantly, we only take the more expensive path after the usual
  lookup encounters a cycle, which should hopefully be rare.

The remaining patches deal with miscellaneous MIDX and bitmap consumers
which are sensitive to packs containing duplicate objects:

 - MIDX verification can now accept any copy of a duplicate object
   (keyed by its OID *only*, as opposed to an (OID, offset) pair).

 - The 'bitmap' test helper now cleanly die()s when trying to write a
   bitmap for packs containing duplicate objects, since the bitmap
   writer cannot tolerate single pack bitmaps with duplicate objects.

 - Finally, multi-pack reuse stops treating pseudo-pack[^1] positions as
   physical pack positions when a pack contains duplicate entries. It
   disables optional fast paths when their mapping cannot be proven and
   uses the existing per-object path otherwise.

This does not change index-pack's duplicate policy or make duplicate
entries a preferred pack format. It makes existing non-strict packs
readable, verifiable, and safe for bitmap-assisted packing while keeping
ordinary packs on their current paths.

Thanks,
Taylor

[^1]: This is a good example of the types of problems this series
  addresses. We currently assume that all objects in a MIDX's preferred
  pack have a unique bit position, which is the same as their
  pack-relative position. That assumption is safe as a consequence of
  how the pseudo-pack ordering is defined, but *only* when the pack in
  question contains no duplicate object entries.

Taylor Blau (5):
  t5308: test reverse indexes with duplicate objects
  packfile: recover delta cycles through duplicate entries
  midx: verify duplicate pack entries by OID and offset
  test-tool bitmap: reject packs with duplicate objects
  pack-bitmap: handle duplicate pack entries during MIDX reuse

 builtin/pack-objects.c            |  24 ++--
 midx.c                            |  59 +++++++--
 pack-bitmap.c                     |  27 +++-
 packfile.c                        | 199 ++++++++++++++++++++++++++++++
 t/helper/test-bitmap.c            |   3 +
 t/helper/test-find-pack.c         |  18 ++-
 t/t5308-pack-detect-duplicates.sh |  60 +++++++++
 t/t5309-pack-delta-cycles.sh      | 148 +++++++++++++++++++++-
 t/t5332-multi-pack-reuse.sh       |  89 +++++++++++++
 9 files changed, 595 insertions(+), 32 deletions(-)


base-commit: 9a0c4701dcd5725c4184599322b52933ff5005ca
-- 
2.55.0.383.gde07827a19