Skip to content

packfile: harden handling of packs with duplicate entries

Taylor Blau git 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest5 patches 1 replyIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/5t5308: test reverse indexes with duplicate objectst/t5308-pack-detect-duplicates.sh+39 -00 replies
2/5packfile: recover delta cycles through duplicate entriespackfile.c t/t5309-pack-delta-cycles.sh+341 -60 replies
3/5midx: verify duplicate pack entries by OID and offsetmidx.c t/helper/test-find-pack.c t/t5308-pack-detect-duplicates.sh+80 -110 replies
4/5test-tool bitmap: reject packs with duplicate objectst/helper/test-bitmap.c t/t5308-pack-detect-duplicates.sh+10 -00 replies
5/5pack-bitmap: handle duplicate pack entries during MIDX reusebuiltin/pack-objects.c pack-bitmap.c t/t5332-multi-pack-reuse.sh+125 -150 replies

Reviews trailers per patch

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

Read the v1 thread

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

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

Signature · 1 line
2.55.0.383.gde07827a19