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

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

[Taylor Blau]

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

[PATCH 1/5] t5308: test reverse indexes with duplicate objects

[Taylor Blau]

A non-strict .idx has one entry for each object in the pack, even when
multiple entries have the same object ID. Thus a pack ordered A, B, A,
C has two .idx entries for A at distinct offsets. The corresponding
per-pack reverse index must represent both entries and map them back to
physical pack order.

Existing reverse-index tests do not cover packs with duplicate objects.
Add one and check that %(objectsize:disk) for B stops at the second A,
rather than extending through it to C. Exercise both the on-disk and
in-memory reverse-index implementations.

As part of validating Git's handling of packs containing duplicate
objects, cover their per-pack reverse indexes.

Signed-off-by: Taylor Blau <ttaylorr@openai.com>
---
 t/t5308-pack-detect-duplicates.sh | 39 +++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh
index 0f84137867..4ff8f5b449 100755
--- a/t/t5308-pack-detect-duplicates.sh
+++ b/t/t5308-pack-detect-duplicates.sh
@@ -27,6 +27,11 @@ HI_SHA1=$EMPTY_BLOB
 # duplicate runs).
 MISSING_SHA1=$(test_oid missing_oid)
 
+# Three distinct objects for tests where physical pack order matters.
+A=$(test_oid packlib_7_0)
+B=$LO_SHA1
+C=$HI_SHA1
+
 # git will never intentionally create packfiles with
 # duplicate objects, so we have to construct them by hand.
 #
@@ -72,6 +77,40 @@ test_expect_success 'lookup in duplicated pack' '
 	test_cmp expect actual
 '
 
+test_expect_success 'duplicate entries remain in pack reverse index' '
+	clear_packs &&
+	{
+		pack_header 4 &&
+		pack_obj $A &&
+		pack_obj $B &&
+		pack_obj $A &&
+		pack_obj $C
+	} >physical-order.pack &&
+	pack_trailer physical-order.pack &&
+
+	test_must_fail git index-pack --rev-index --stdin --strict \
+		<physical-order.pack 2>err &&
+	test_grep "appears twice in the pack" err &&
+
+	git index-pack --rev-index --stdin <physical-order.pack &&
+	git show-index <"$(ls .git/objects/pack/pack-*.idx)" >offsets.raw &&
+
+	sort -n offsets.raw | grep -A1 "$B" | cut -d" " -f1 >adjacent &&
+	echo $(($(tail -n1 adjacent) - $(head -n1 adjacent))) >expect &&
+	echo "$B" >in &&
+
+	GIT_TEST_REV_INDEX_DIE_IN_MEMORY=1 \
+		git cat-file --batch-check="%(objectsize:disk)" \
+		<in >actual.disk &&
+	GIT_TEST_REV_INDEX_DIE_ON_DISK=1 \
+		git -c pack.readReverseIndex=false \
+		cat-file --batch-check="%(objectsize:disk)" \
+		<in >actual.mem  &&
+
+	test_cmp expect actual.disk &&
+	test_cmp expect actual.mem
+'
+
 test_expect_success 'index-pack can reject packs with duplicates' '
 	clear_packs &&
 	create_pack dups.pack 2 &&
-- 
2.55.0.383.gde07827a19

[PATCH 2/5] packfile: recover delta cycles through duplicate entries

[Taylor Blau]

98f8854c94 (index-pack: allow revisiting REF_DELTA chains, 2025-04-28)
changed t5309's recoverable-cycle case to expect index-pack to accept
the pack, but did not read the resulting objects. The .idx for a pack
with duplicate OIDs retains every physical entry, with equal OIDs in a
contiguous run. Ordinary REF_DELTA lookup selects one representation
from such a run. If that choice closes a cycle, both type and content
readers follow the same physical offsets indefinitely even though
another representation is usable.

Keep the ordinary walk, and recognize a cycle only when its existing
stack shows an exact repeated pack offset. At that point, restart at the
requested object and search duplicate representations depth-first.
Treat each OID as a node, try each entry in its .idx run, and translate
OFS_DELTA bases back to OIDs. A bitmap marks each OID group already
visited. Reaching a full object records the exact offsets along the
acyclic path so unpack_entry() can replay it; packed_to_object_type()
needs only the resulting type.

Thus, acyclic lookups continue to use the existing single-entry lookup.
Duplicate-run scans, the visited bitmap, and OFS-to-OID translation
remain confined to recovery after a proven cycle.

Extend t5309 to read both type and content after indexing. Cover a
root-level full duplicate, a mixed REF/OFS cycle, and a tail into a
three-object cycle which must backtrack before taking an alternate
REF_DELTA/OFS_DELTA path to a full base. Keep the fixtures
hash-independent so the same cases run under SHA-1 and SHA-256. This
adds the reader validation missing from the earlier acceptance test.

Signed-off-by: Taylor Blau <ttaylorr@openai.com>
---
 packfile.c                   | 199 +++++++++++++++++++++++++++++++++++
 t/t5309-pack-delta-cycles.sh | 148 ++++++++++++++++++++++++--
 2 files changed, 341 insertions(+), 6 deletions(-)

diff --git a/packfile.c b/packfile.c
index 0eee45055f..6049d1fd8c 100644
--- a/packfile.c
+++ b/packfile.c
@@ -10,6 +10,7 @@
 #include "dir.h"
 #include "packfile.h"
 #include "delta.h"
+#include "ewah/ewok.h"
 #include "hash-lookup.h"
 #include "commit.h"
 #include "object.h"
@@ -1077,6 +1078,160 @@ static int get_delta_base_oid(struct packed_git *p,
 		return -1;
 }
 
+/*
+ * Search duplicate representations for a chain ending in a full object.
+ * Representations of the same OID are interchangeable as delta bases.
+ *
+ * Each path entry is the search frame for one OID. It walks that OID's
+ * contiguous .idx entries and retains the chosen entry's .pack offset
+ * for replay.
+ */
+struct delta_path_entry {
+	off_t selected_offset; /* zero until a candidate is selected */
+	uint32_t next; /* index position of the next candidate */
+	uint32_t remaining; /* total number of candidates remaining */
+};
+
+struct delta_path {
+	struct delta_path_entry *entries;
+	size_t nr, alloc;
+};
+
+static int push_oid_group(struct packed_git *p,
+			  const struct object_id *oid,
+			  struct bitmap *visited, struct delta_path *path)
+{
+	struct object_id candidate;
+	struct delta_path_entry *entry;
+	uint32_t first_index_pos, group_index_pos, index_pos;
+
+	/*
+	 * Determine the range of index positions referring to duplicate
+	 * copies of the given object.
+	 *
+	 * Any position within that range is OK, since we will determine
+	 * the exact range below.
+	 */
+	if (!bsearch_pack(oid, p, &group_index_pos))
+		return 0;
+	if (bitmap_get(visited, group_index_pos))
+		return 0;
+
+	first_index_pos = group_index_pos;
+	while (first_index_pos > 0) {
+		if (nth_packed_object_id(&candidate, p, first_index_pos - 1) < 0)
+			return -1;
+		if (!oideq(&candidate, oid))
+			break;
+		first_index_pos--;
+	}
+
+	for (index_pos = first_index_pos; index_pos < p->num_objects; index_pos++) {
+		if (nth_packed_object_id(&candidate, p, index_pos) < 0)
+			return -1;
+		if (!oideq(&candidate, oid))
+			break;
+	}
+
+	bitmap_set(visited, group_index_pos);
+
+	ALLOC_GROW(path->entries, path->nr + 1, path->alloc);
+	entry = &path->entries[path->nr++];
+	entry->selected_offset = 0;
+	entry->next = first_index_pos;
+	entry->remaining = index_pos - first_index_pos;
+
+	return 1;
+}
+
+static enum object_type find_delta_path(struct packed_git *p,
+					struct pack_window **w_curs,
+					off_t offset,
+					struct delta_path *path)
+{
+	struct object_id oid;
+	uint32_t pack_pos;
+	struct bitmap *visited;
+	enum object_type result = OBJ_BAD;
+
+	if (offset_to_pack_pos(p, offset, &pack_pos) < 0)
+		return OBJ_BAD;
+	if (nth_packed_object_id(&oid, p, pack_pos_to_index(p, pack_pos)) < 0)
+		return OBJ_BAD;
+
+	visited = bitmap_new();
+	if (push_oid_group(p, &oid, visited, path) != 1)
+		goto done;
+
+	/*
+	 * Search depth-first for a chain ending in a full object. Each frame
+	 * tries every representation of one OID; a delta pushes its base OID,
+	 * while exhausting a frame backtracks to its parent.
+	 */
+	while (path->nr) {
+		struct delta_path_entry *entry = &path->entries[path->nr - 1];
+		enum object_type candidate_type;
+		off_t curpos;
+		size_t size;
+
+		/*
+		 * This OID has no path to a full object. Let its parent try
+		 * another representation; exhausting the root fails the search.
+		 */
+		if (!entry->remaining) {
+			path->nr--;
+			continue;
+		}
+
+		entry->selected_offset =
+			nth_packed_object_offset(p, entry->next++);
+		entry->remaining--;
+		curpos = entry->selected_offset;
+		candidate_type = unpack_object_header(p, w_curs, &curpos, &size);
+
+		/*
+		 * A full object terminates the chain, and its type is
+		 * inherited by every delta above it. A delta continues
+		 * at its base; any other type rejects only this
+		 * representation.
+		 */
+		switch (candidate_type) {
+		case OBJ_COMMIT:
+		case OBJ_TREE:
+		case OBJ_BLOB:
+		case OBJ_TAG:
+			result = candidate_type;
+			goto done;
+		case OBJ_OFS_DELTA:
+		case OBJ_REF_DELTA:
+			break;
+		default:
+			/*
+			 * A bad or unknown type rejects only this copy;
+			 * another representation of the same OID may
+			 * still work.
+			 */
+			continue;
+		}
+
+		/*
+		 * Descend to this delta's base. A malformed reference
+		 * or a missing or already-visited base rejects this
+		 * copy. A newly pushed base is examined next; an index
+		 * error aborts the search.
+		 */
+		if (get_delta_base_oid(p, w_curs, curpos, &oid, candidate_type,
+				       entry->selected_offset))
+			continue;
+		if (push_oid_group(p, &oid, visited, path) < 0)
+			goto done;
+	}
+
+done:
+	bitmap_free(visited);
+	return result;
+}
+
 static int retry_bad_packed_offset(struct repository *r,
 				   struct packed_git *p,
 				   off_t obj_offset)
@@ -1105,11 +1260,27 @@ static enum object_type packed_to_object_type(struct repository *r,
 {
 	off_t small_poi_stack[POI_STACK_PREALLOC];
 	off_t *poi_stack = small_poi_stack;
+	off_t root_offset = obj_offset;
 	int poi_stack_nr = 0, poi_stack_alloc = POI_STACK_PREALLOC;
 
 	while (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
 		off_t base_offset;
 		size_t size;
+
+		if (poi_stack_nr > 0 && poi_stack_nr % 2 == 0 &&
+		    obj_offset == poi_stack[poi_stack_nr / 2]) {
+			struct delta_path path = { 0 };
+			/*
+			 * Normal lookup returned to the same pack
+			 * entry. Restart from the requested object
+			 * using alternate representations.
+			 */
+			type = find_delta_path(p, w_curs, root_offset, &path);
+			free(path.entries);
+			if (type == OBJ_BAD)
+				goto unwind;
+			break;
+		}
 		/* Push the object we're going to leave behind */
 		if (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {
 			poi_stack_alloc = alloc_nr(poi_stack_nr);
@@ -1525,9 +1696,11 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 {
 	struct pack_window *w_curs = NULL;
 	off_t curpos = obj_offset;
+	off_t root_offset = obj_offset;
 	void *data = NULL;
 	size_t size;
 	enum object_type type;
+	struct delta_path path = { 0 };
 	struct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];
 	struct unpack_entry_stack_ent *delta_stack = small_delta_stack;
 	int delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;
@@ -1553,6 +1726,22 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 			break;
 		}
 
+		if (!path.nr &&
+		    delta_stack_nr > 0 && delta_stack_nr % 2 == 0 &&
+		    obj_offset == delta_stack[delta_stack_nr / 2].obj_offset) {
+			/*
+			 * Normal lookup returned to the same pack
+			 * entry. Find an acyclic path if one exists,
+			 * discard this walk, and replay that path.
+			 */
+			if (find_delta_path(p, &w_curs, root_offset,
+					    &path) == OBJ_BAD)
+				break;
+			delta_stack_nr = 0;
+			curpos = obj_offset = path.entries[0].selected_offset;
+			continue;
+		}
+
 		if (do_check_packed_object_crc && p->index_version > 1) {
 			uint32_t pack_pos, index_pos;
 			off_t len;
@@ -1591,6 +1780,15 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 			break;
 		}
 
+		/* Use the base chosen by recovery, not the one from normal lookup. */
+		if (path.nr) {
+			size_t path_pos = (size_t)delta_stack_nr + 1;
+
+			if (path_pos >= path.nr)
+				BUG("alternate delta path ends in a delta");
+			base_offset = path.entries[path_pos].selected_offset;
+		}
+
 		/* push object, proceed to base */
 		if (delta_stack_nr >= delta_stack_alloc
 		    && delta_stack == small_delta_stack) {
@@ -1731,6 +1929,7 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 
 out:
 	unuse_pack(&w_curs);
+	free(path.entries);
 
 	if (delta_stack != small_delta_stack)
 		free(delta_stack);
diff --git a/t/t5309-pack-delta-cycles.sh b/t/t5309-pack-delta-cycles.sh
index 6b03675d91..f613950e38 100755
--- a/t/t5309-pack-delta-cycles.sh
+++ b/t/t5309-pack-delta-cycles.sh
@@ -9,6 +9,83 @@ test_description='test index-pack handling of delta cycles in packfiles'
 A=$(test_oid packlib_7_0)
 B=$(test_oid packlib_7_76)
 
+# Copy the entries from a complete pack without its header or trailer.
+pack_entries () {
+	entry_size=$(wc -c <"$1") &&
+	dd if="$1" bs=1 skip=12 \
+		count=$((entry_size - 12 - $(test_oid rawsz))) 2>/dev/null
+}
+
+# B as an OFS_DELTA against A at the given one-byte distance.
+pack_obj_b_ofs_a () {
+	pack_obj "$B" "$A" >b-ref.tmp &&
+	printf "\145" &&
+	printf "\\$(printf "%03o" "$1")" &&
+	dd if=b-ref.tmp bs=1 skip=$((1 + $(test_oid rawsz))) 2>/dev/null
+}
+
+# Return the base of the first one-byte-header REF_DELTA for the given OID.
+first_ref_base () {
+	idx=$(echo .git/objects/pack/*.idx) &&
+	offset=$(git show-index <"$idx" |
+		awk -v oid="$1" '$2 == oid { print $1; exit }') &&
+	dd if="${idx%.idx}.pack" bs=1 skip=$((offset + 1)) \
+		count=$(test_oid rawsz) 2>/dev/null |
+	test-tool hexdump |
+	tr -d " \n"
+}
+
+# The order of equal-OID entries in the .idx is unspecified. Retain a pack
+# which selects $1 as a delta against $2. Unless $3 is "-", also require the
+# first copy searched during recovery to be a REF_DELTA against $3.
+install_cycle () {
+	cycle_oid=$1 &&
+	cycle_base=$2 &&
+	first_base=$3 &&
+	shift 3 &&
+	for pack
+	do
+		clear_packs &&
+		git index-pack --fix-thin --stdin <"$pack" &&
+		selected_base=$(echo "$cycle_oid" |
+			git cat-file --batch-check="%(deltabase)") ||
+		return 1
+		if test "$selected_base" = "$cycle_base" &&
+		   { test "$first_base" = "-" ||
+		     test "$(first_ref_base "$cycle_oid")" = "$first_base"; }
+		then
+			return 0
+		fi
+	done
+	return 1
+}
+
+make_cycle_pack () {
+	cycle_pack=$1 &&
+	shift &&
+	test-tool -C alt-source pack-deltas --num-objects=6 >refs.tmp <<-EOF &&
+	REF_DELTA $T $X
+	REF_DELTA $X $1
+	REF_DELTA $Y $Z
+	REF_DELTA $Z $X
+	REF_DELTA $X $2
+	REF_DELTA $X $3
+	EOF
+	{
+		pack_header 8 &&
+		pack_entries refs.tmp &&
+		cat a-full &&
+		pack_obj_b_ofs_a "$a_full_size"
+	} >"$cycle_pack" &&
+	pack_trailer "$cycle_pack"
+}
+
+check_blob () {
+	test "$(git cat-file -t "$1")" = blob &&
+	git cat-file blob "$1" >actual &&
+	test_cmp_bin "$2" actual
+}
+
 # double-check our hand-constucted packs
 test_expect_success 'index-pack works with a single delta (A->B)' '
 	clear_packs &&
@@ -67,18 +144,77 @@ test_expect_success 'failover to an object in another pack' '
 '
 
 test_expect_success 'failover to a duplicate object in the same pack' '
-	clear_packs &&
+	{
+		pack_header 3 &&
+		pack_obj $A &&
+		pack_obj $B $A &&
+		pack_obj $A $B
+	} >recoverable-1.pack &&
+	pack_trailer recoverable-1.pack &&
 	{
 		pack_header 3 &&
 		pack_obj $A $B &&
 		pack_obj $B $A &&
 		pack_obj $A
-	} >recoverable.pack &&
-	pack_trailer recoverable.pack &&
+	} >recoverable-2.pack &&
+	pack_trailer recoverable-2.pack &&
 
-	# This cycle does not fail since the existence of a full copy
-	# of A in the pack allows us to resolve the cycle.
-	git index-pack --fix-thin --stdin <recoverable.pack
+	# The selected copy of A is part of the cycle, but the full copy
+	# lets both type and content lookups resolve it.
+	install_cycle "$A" "$B" - recoverable-1.pack recoverable-2.pack &&
+	printf "\7\0" >expect &&
+	check_blob "$A" expect
+'
+
+test_expect_success 'failover from a mixed REF/OFS cycle' '
+	pack_obj "$A" "$B" >a-ref &&
+	pack_obj "$B" >b-full &&
+	a_ref_size=$(wc -c <a-ref) &&
+	b_full_size=$(wc -c <b-full) &&
+
+	{
+		pack_header 3 &&
+		cat a-ref &&
+		cat b-full &&
+		pack_obj_b_ofs_a "$((a_ref_size + b_full_size))"
+	} >mixed-1.pack &&
+	pack_trailer mixed-1.pack &&
+	{
+		pack_header 3 &&
+		cat a-ref &&
+		pack_obj_b_ofs_a "$a_ref_size" &&
+		cat b-full
+	} >mixed-2.pack &&
+	pack_trailer mixed-2.pack &&
+
+	# The REF_DELTA for A selects the OFS_DELTA copy of B; the
+	# full B is its escape.
+	install_cycle "$B" "$A" - mixed-1.pack mixed-2.pack &&
+	printf "\7\0" >expect &&
+	check_blob "$A" expect
+'
+
+test_expect_success 'failover after a tail into a three-object delta cycle' '
+	git init alt-source &&
+	printf "\7\76" |
+		git -C alt-source hash-object -w --stdin >/dev/null &&
+	X=$(printf x | git -C alt-source hash-object -w --stdin) &&
+	Y=$(printf y | git -C alt-source hash-object -w --stdin) &&
+	Z=$(printf z | git -C alt-source hash-object -w --stdin) &&
+	printf "tail T\n" >tail &&
+	T=$(git -C alt-source hash-object -w --stdin <tail) &&
+
+	pack_obj "$A" >a-full &&
+	a_full_size=$(wc -c <a-full) &&
+	make_cycle_pack alternate-1.pack "$B" "$Y" "$Y" &&
+	make_cycle_pack alternate-2.pack "$Y" "$B" "$Y" &&
+	make_cycle_pack alternate-3.pack "$Y" "$Y" "$B" &&
+
+	# Lookup of T follows T->X->Y->Z->X. Recovery must exhaust that
+	# branch, then use X->B->A, whose final edge is an OFS_DELTA.
+	install_cycle "$X" "$Y" "$Y" \
+		alternate-1.pack alternate-2.pack alternate-3.pack &&
+	check_blob "$T" tail
 '
 
 test_expect_success 'index-pack works with thin pack A->B->C with B on disk' '
-- 
2.55.0.383.gde07827a19

[PATCH 3/5] midx: verify duplicate pack entries by OID and offset

[Taylor Blau]

A MIDX retains one entry per OID, while a non-strict pack index can
contain the same OID at several offsets. verify_midx_file() compares the
recorded offset with find_pack_entry_one(), which may return a different
member of that duplicate run and falsely report a valid MIDX as corrupt.

Check instead that the exact OID/offset pair exists anywhere in the
contiguous duplicate run in the source pack. That is the relevant
invariant: same-pack duplicates have no canonical representation, and
every matching physical copy is valid, including those recorded by
existing MIDXs.

This matches reader behavior. The OOFF chunk records the selected
(pack, offset), and midx_to_pack_pos() reconstructs its RIDX position
from that pair. If midx_pair_to_pack_pos() is given an unselected
duplicate offset, the lookup misses and its sole caller falls back from
partial reuse to normal packing. Readers therefore remain consistent
with whichever representation the MIDX records.

Write a MIDX over the existing duplicate-pack fixture, assert that its
selected offset differs from find_pack_entry_one(), and verify it. Then
run fsck as an application-level check.

Signed-off-by: Taylor Blau <ttaylorr@openai.com>
---
 midx.c                            | 59 +++++++++++++++++++++++++++----
 t/helper/test-find-pack.c         | 18 +++++++---
 t/t5308-pack-detect-duplicates.sh | 14 ++++++++
 3 files changed, 80 insertions(+), 11 deletions(-)

diff --git a/midx.c b/midx.c
index 76c3f92cc3..05fe99f8ca 100644
--- a/midx.c
+++ b/midx.c
@@ -906,6 +906,48 @@ static int compare_pair_pos_vs_id(const void *_a, const void *_b)
 	return b->pack_int_id - a->pack_int_id;
 }
 
+/*
+ * Return whether the pack index contains an entry with both "oid" and
+ * "offset". A pack index may contain duplicate OIDs, so an arbitrary
+ * OID lookup is not enough to validate a particular offset.
+ *
+ * Do not use offset_to_pack_pos() here: it may consult an optional '.rev'
+ * file, which is verified separately, or build an in-memory reverse index
+ * that remains attached to the pack. Verify the MIDX directly against its
+ * source pack index instead.
+ */
+static int pack_index_has_oid_at_offset(struct packed_git *p,
+					const struct object_id *oid,
+					off_t offset)
+{
+	struct object_id candidate;
+	uint32_t pos, i;
+
+	if (!bsearch_pack(oid, p, &pos))
+		return 0;
+
+	if (nth_packed_object_offset(p, pos) == offset)
+		return 1;
+
+	for (i = pos; i > 0; i--) {
+		if (nth_packed_object_id(&candidate, p, i - 1) ||
+		    !oideq(&candidate, oid))
+			break;
+		if (nth_packed_object_offset(p, i - 1) == offset)
+			return 1;
+	}
+
+	for (i = pos + 1; i < p->num_objects; i++) {
+		if (nth_packed_object_id(&candidate, p, i) ||
+		    !oideq(&candidate, oid))
+			break;
+		if (nth_packed_object_offset(p, i) == offset)
+			return 1;
+	}
+
+	return 0;
+}
+
 /*
  * Limit calls to display_progress() for performance reasons.
  * The interval here was arbitrarily chosen.
@@ -1015,7 +1057,6 @@ int verify_midx_file(struct odb_source_packed *source, unsigned flags)
 	for (i = 0; i < m->num_objects + m->num_objects_in_base; i++) {
 		struct object_id oid;
 		struct pack_entry e;
-		off_t m_offset, p_offset;
 
 		if (i > 0 && pairs[i-1].pack_int_id != pairs[i].pack_int_id &&
 		    nth_midxed_pack(m, pairs[i-1].pack_int_id)) {
@@ -1040,12 +1081,16 @@ int verify_midx_file(struct odb_source_packed *source, unsigned flags)
 			break;
 		}
 
-		m_offset = e.offset;
-		p_offset = find_pack_entry_one(&oid, e.p);
-
-		if (m_offset != p_offset)
-			midx_report(_("incorrect object offset for oid[%d] = %s: %"PRIx64" != %"PRIx64),
-				    pairs[i].pos, oid_to_hex(&oid), m_offset, p_offset);
+		/*
+		 * Check that the exact offset recorded in the MIDX
+		 * belongs to this OID. A pack index may contain
+		 * duplicate OIDs, in which case an arbitrary OID lookup
+		 * can return a different, equally valid copy than the
+		 * one selected by the MIDX writer.
+		 */
+		if (!pack_index_has_oid_at_offset(e.p, &oid, e.offset))
+			midx_report(_("incorrect object offset for oid[%d] = %s: %"PRIx64),
+				    pairs[i].pos, oid_to_hex(&oid), e.offset);
 
 		midx_display_sparse_progress(progress, i + 1);
 	}
diff --git a/t/helper/test-find-pack.c b/t/helper/test-find-pack.c
index 28d5b1fe09..51093a7030 100644
--- a/t/helper/test-find-pack.c
+++ b/t/helper/test-find-pack.c
@@ -11,12 +11,15 @@
  * Display the path(s), one per line, of the packfile(s) containing
  * the given object.
  *
+ * With '--show-offset', display the offset selected by
+ * find_pack_entry_one() instead of the packfile path.
+ *
  * If '--check-count <n>' is passed, then error out if the number of
  * packfiles containing the object is not <n>.
  */
 
 static const char *const find_pack_usage[] = {
-	"test-tool find-pack [--check-count <n>] <object>",
+	"test-tool find-pack [--check-count <n>] [--show-offset] <object>",
 	NULL
 };
 
@@ -24,11 +27,13 @@ int cmd__find_pack(int argc, const char **argv)
 {
 	struct object_id oid;
 	struct packed_git *p;
-	int count = -1, actual_count = 0;
+	int count = -1, actual_count = 0, show_offset = 0;
 	const char *prefix = setup_git_directory(the_repository);
 
 	struct option options[] = {
 		OPT_INTEGER('c', "check-count", &count, "expected number of packs"),
+		OPT_BOOL(0, "show-offset", &show_offset,
+			 "show matching pack offsets"),
 		OPT_END(),
 	};
 
@@ -40,8 +45,13 @@ int cmd__find_pack(int argc, const char **argv)
 		die("cannot parse %s as an object name", argv[0]);
 
 	repo_for_each_pack(the_repository, p) {
-		if (find_pack_entry_one(&oid, p)) {
-			printf("%s\n", p->pack_name);
+		off_t offset = find_pack_entry_one(&oid, p);
+
+		if (offset) {
+			if (show_offset)
+				printf("%"PRIuMAX"\n", (uintmax_t)offset);
+			else
+				printf("%s\n", p->pack_name);
 			actual_count++;
 		}
 	}
diff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh
index 4ff8f5b449..493ebbc4af 100755
--- a/t/t5308-pack-detect-duplicates.sh
+++ b/t/t5308-pack-detect-duplicates.sh
@@ -77,6 +77,20 @@ test_expect_success 'lookup in duplicated pack' '
 	test_cmp expect actual
 '
 
+test_expect_success 'verify MIDX containing duplicated pack objects' '
+	git multi-pack-index write &&
+	test-tool read-midx --show-objects .git/objects >midx-objects &&
+	midx_offset=$(
+		awk -v oid="$LO_SHA1" "\$1 == oid { print \$2 }" <midx-objects
+	) &&
+	lookup_offset=$(
+		test-tool find-pack --check-count=1 --show-offset "$LO_SHA1"
+	) &&
+	test "$midx_offset" -ne "$lookup_offset" &&
+	git multi-pack-index verify &&
+	git fsck --full
+'
+
 test_expect_success 'duplicate entries remain in pack reverse index' '
 	clear_packs &&
 	{
-- 
2.55.0.383.gde07827a19

[PATCH 4/5] test-tool bitmap: reject packs with duplicate objects

[Taylor Blau]

The bitmap writer builds its object-to-position map in packing_data,
whose hash table permits one entry per OID. The bitmap test helper
accepts an arbitrary existing pack, so a pack with duplicate entries
calls packlist_alloc() twice for the same OID and trips its internal
BUG().

Detect duplicate OIDs while ingesting the pack and die before calling
packlist_alloc(). This preserves the internal uniqueness check for
other callers while making unsupported helper input fail gracefully.

Reuse t5308's existing duplicate pack to exercise the fatal
diagnostic.

Signed-off-by: Taylor Blau <ttaylorr@openai.com>
---
 t/helper/test-bitmap.c            | 3 +++
 t/t5308-pack-detect-duplicates.sh | 7 +++++++
 2 files changed, 10 insertions(+)

diff --git a/t/helper/test-bitmap.c b/t/helper/test-bitmap.c
index 8547ef67e2..6f851e0421 100644
--- a/t/helper/test-bitmap.c
+++ b/t/helper/test-bitmap.c
@@ -50,6 +50,9 @@ static int add_packed_object(const struct object_id *oid,
 
 	oi.typep = &type;
 
+	if (packlist_find(packed, oid))
+		die("pack contains duplicate object %s", oid_to_hex(oid));
+
 	entry = packlist_alloc(packed, oid);
 	entry->idx.offset = nth_packed_object_offset(pack, pos);
 	if (packed_object_info(NULL, pack, entry->idx.offset, &oi) < 0)
diff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh
index 493ebbc4af..c6273a1aeb 100755
--- a/t/t5308-pack-detect-duplicates.sh
+++ b/t/t5308-pack-detect-duplicates.sh
@@ -59,6 +59,13 @@ test_expect_success 'index-pack will allow duplicate objects by default' '
 	git index-pack --stdin <dups.pack
 '
 
+test_expect_success 'bitmap writer rejects duplicate objects' '
+	pack=$(ls .git/objects/pack/pack-*.pack) &&
+	test_must_fail test-tool bitmap write "$(basename "$pack")" \
+		</dev/null 2>err &&
+	test_grep "fatal: pack contains duplicate object" err
+'
+
 test_expect_success 'create batch-check test vectors' '
 	cat >input <<-EOF &&
 	$LO_SHA1
-- 
2.55.0.383.gde07827a19

[PATCH 5/5] pack-bitmap: handle duplicate pack entries during MIDX reuse

[Taylor Blau]

A MIDX pseudo-pack assigns one bit position to each selected OID. Its
preferred-pack fast paths handle duplicate OIDs across packs in the
MIDX, where the MIDX chooses one copy, but assume that each individual
pack contains one entry per OID.

Consider a preferred pack ordered [A, B, A, C]. The MIDX retains one
copy of A, leaving three pseudo-pack positions for four physical
entries. This creates two problems:

 - In MIDX-backed single-pack reuse, bitmap_nr came from
   pack->num_objects and therefore counted both copies of A. Read the
   selected count from the root MIDX layer BTMP chunk instead. If that
   layer has no BTMP chunk, skip pack reuse and let the ordinary packing
   path handle the bitmap-selected objects. MIDXs without BTMP lose
   preferred-pack reuse until rewritten, rather than requiring a scan of
   the entire pseudo-pack to retain an optional optimization.

 - Correcting the range length still does not align the two orderings.
   Once one copy of A is omitted, MIDX position N need not name physical
   pack entry N.

That mismatch matters during both selection and output. Whole-word
selection bypasses the per-object check that the exact physical base of
a delta is present. Verbatim reuse copies the first N pack entries for
the first N bits. The per-object writer likewise used each bit as a
physical pack position.

Use the direct mapping only when the range begins at zero and its
selected count equals the physical entry count. Since selected entries
remain in pack-offset order, equal counts mean that none was omitted and
the two positions coincide.

For every other MIDX range, let whole-word selection fall through to
the existing per-bit path, which resolves the selected MIDX offset to a
physical pack position before checking the delta base. Disable verbatim
prefix reuse, and perform the same translation in the per-object writer.

Leave classic single-pack bitmap handling unchanged. The production
writer creates those bitmaps only for the pack it just wrote, which has
one entry per OID. The test helper can target an existing pack, but
rejects duplicate OIDs.

Cover the A, B, A, C case in a MIDX-backed preferred pack. Check reuse
with BTMP, then hide BTMP and check that the optional reuse path is
skipped. Also make B a delta against the omitted copy of A and require
normal packing to handle it.

Signed-off-by: Taylor Blau <ttaylorr@openai.com>
---
 builtin/pack-objects.c      | 24 +++++-----
 pack-bitmap.c               | 27 ++++++++++-
 t/t5332-multi-pack-reuse.sh | 89 +++++++++++++++++++++++++++++++++++++
 3 files changed, 125 insertions(+), 15 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 3673b14b89..c333922961 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1182,12 +1182,12 @@ static size_t write_reused_pack_verbatim(struct bitmapped_pack *reuse_packfile,
 	size_t pos = 0;
 	size_t end;
 
-	if (reuse_packfile->bitmap_pos) {
+	if (reuse_packfile->bitmap_pos ||
+	    reuse_packfile->bitmap_nr != reuse_packfile->p->num_objects) {
 		/*
-		 * We can't reuse whole chunks verbatim out of
-		 * non-preferred packs since we can't guarantee that
-		 * all duplicate objects were resolved in favor of
-		 * that pack.
+		 * We can't reuse whole chunks verbatim from non-preferred
+		 * packs or packs with entries missing from the bitmap because
+		 * bitmap and pack positions may differ.
 		 *
 		 * Even if we have a whole eword_t worth of bits that
 		 * could be reused, there may be objects between the
@@ -1196,7 +1196,7 @@ static size_t write_reused_pack_verbatim(struct bitmapped_pack *reuse_packfile,
 		 * pack, causing us to send duplicate or unwanted
 		 * objects.
 		 *
-		 * Handle non-preferred packs from within
+		 * Handle these packs from within
 		 * write_reused_pack(), which inspects and reuses
 		 * individual bits.
 		 */
@@ -1263,20 +1263,18 @@ static void write_reused_pack(struct bitmapped_pack *reuse_packfile,
 			if (pos + offset >= reuse_packfile->bitmap_pos + reuse_packfile->bitmap_nr)
 				goto done;
 
-			if (reuse_packfile->bitmap_pos) {
+			if (reuse_packfile->bitmap_pos ||
+			    reuse_packfile->bitmap_nr != reuse_packfile->p->num_objects) {
 				/*
-				 * When doing multi-pack reuse on a
-				 * non-preferred pack, translate bit positions
-				 * from the MIDX pseudo-pack order back to their
-				 * pack-relative positions before attempting
-				 * reuse.
+				 * Translate MIDX bitmap positions which do not
+				 * correspond directly to physical pack positions.
 				 */
 				struct multi_pack_index *m = reuse_packfile->from_midx;
 				uint32_t midx_pos;
 				off_t pack_ofs;
 
 				if (!m)
-					BUG("non-zero bitmap position without MIDX");
+					BUG("cannot translate bitmap position without MIDX");
 
 				midx_pos = pack_pos_to_midx(m, pos + offset);
 				pack_ofs = nth_midxed_offset(m, midx_pos);
diff --git a/pack-bitmap.c b/pack-bitmap.c
index d8dc4ae8d1..8141290436 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -2383,7 +2383,8 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git
 	struct pack_window *w_curs = NULL;
 	size_t pos = pack->bitmap_pos / BITS_IN_EWORD;
 
-	if (!pack->bitmap_pos) {
+	if (!pack->bitmap_pos &&
+	    pack->bitmap_nr == pack->p->num_objects) {
 		/*
 		 * If we're processing the first (in the case of a MIDX, the
 		 * preferred pack) or the only (in the case of single-pack
@@ -2399,6 +2400,9 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git
 		 *   all ties are broken in favor of that pack (i.e. the one
 		 *   we're currently processing). So any duplicate bases will be
 		 *   resolved in favor of the pack we're processing.
+		 *
+		 * The range must also contain every physical pack entry so that
+		 * bitmap and pack positions correspond.
 		 */
 		while (pos < result->word_alloc &&
 		       pos < pack->bitmap_nr / BITS_IN_EWORD &&
@@ -2527,14 +2531,26 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,
 	} else {
 		struct packed_git *pack;
 		uint32_t pack_int_id;
+		uint32_t bitmap_nr;
 
 		if (bitmap_is_midx(bitmap_git)) {
+			struct bitmapped_pack bitmapped_pack;
 			struct multi_pack_index *m = bitmap_git->midx;
 			uint32_t preferred_pack_pos;
 
 			while (m->base_midx)
 				m = m->base_midx;
 
+			if (!m->chunk_bitmapped_packs) {
+				/*
+				 * Without BTMP, determining the preferred
+				 * pack's range requires scanning the pseudo-pack.
+				 * Skip reuse and leave the bitmap result for
+				 * normal packing.
+				 */
+				return;
+			}
+
 			if (midx_preferred_pack(m, &preferred_pack_pos) < 0) {
 				warning(_("unable to compute preferred pack, disabling pack-reuse"));
 				return;
@@ -2542,6 +2558,12 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,
 
 			pack = nth_midxed_pack(m, preferred_pack_pos);
 			pack_int_id = preferred_pack_pos;
+
+			if (nth_bitmapped_pack(m, &bitmapped_pack,
+					       pack_int_id) < 0)
+				return;
+			pack = bitmapped_pack.p;
+			bitmap_nr = bitmapped_pack.bitmap_nr;
 		} else {
 			pack = bitmap_git->pack;
 			/*
@@ -2554,13 +2576,14 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,
 			 * that we do not expect to read this field.
 			 */
 			pack_int_id = -1;
+			bitmap_nr = pack->num_objects;
 		}
 
 		if (is_pack_valid(pack)) {
 			ALLOC_GROW(packs, packs_nr + 1, packs_alloc);
 			packs[packs_nr].p = pack;
 			packs[packs_nr].pack_int_id = pack_int_id;
-			packs[packs_nr].bitmap_nr = pack->num_objects;
+			packs[packs_nr].bitmap_nr = bitmap_nr;
 			packs[packs_nr].bitmap_pos = 0;
 			packs[packs_nr].from_midx = bitmap_git->midx;
 			packs_nr++;
diff --git a/t/t5332-multi-pack-reuse.sh b/t/t5332-multi-pack-reuse.sh
index 881ce668e1..126ab9df99 100755
--- a/t/t5332-multi-pack-reuse.sh
+++ b/t/t5332-multi-pack-reuse.sh
@@ -4,6 +4,7 @@ test_description='pack-objects multi-pack reuse'
 
 . ./test-lib.sh
 . "$TEST_DIRECTORY"/lib-bitmap.sh
+. "$TEST_DIRECTORY"/lib-pack.sh
 
 GIT_TEST_MULTI_PACK_INDEX=0
 GIT_TEST_MULTI_PACK_INDEX_WRITE_INCREMENTAL=0
@@ -32,6 +33,14 @@ pack_position () {
 	grep "$1" objects | cut -d" " -f1
 }
 
+# B as an OFS_DELTA against A at the given one-byte distance.
+pack_obj_b_ofs_a () {
+	pack_obj "$B" "$A" >b-ref.tmp &&
+	printf "\145" &&
+	printf "\\$(printf "%03o" "$1")" &&
+	dd if=b-ref.tmp bs=1 skip=$((1 + $(test_oid rawsz))) 2>/dev/null
+}
+
 # test_pack_objects_reused_all <pack-reused> <packs-reused>
 test_pack_objects_reused_all () {
 	: >trace2.txt &&
@@ -288,4 +297,84 @@ test_expect_success 'duplicate objects with verbatim reuse' '
 	)
 '
 
+test_expect_success 'reuse with intra-pack duplicate objects' '
+	git init intra-pack-duplicate-objects &&
+	(
+		cd intra-pack-duplicate-objects &&
+
+		# Make enough objects to exercise whole-word reuse.
+		test_commit_bulk 20 &&
+		test_commit --printf A a "\7\0" &&
+		test_commit --printf B b "\7\76" &&
+
+		objects_nr=$(git rev-list --count --objects --all) &&
+		git rev-list --objects --all |
+		cut -d" " -f1 >objects &&
+		A=$(test_oid packlib_7_0) &&
+		B=$(test_oid packlib_7_76) &&
+		grep -v -e "^$A$" -e "^$B$" objects >rest &&
+		pack_obj "$A" >a-full &&
+		pack_obj "$B" >b-full &&
+		while read oid
+		do
+			pack_obj "$oid" || exit 1
+		done <rest >rest.entries &&
+		{
+			# Arrange the pack as A, B, A, C..., so that physical
+			# positions diverge from MIDX pseudo-pack order.
+			pack_header $((objects_nr + 1)) &&
+			cat a-full b-full a-full rest.entries
+		} >duplicate.pack &&
+		pack_trailer duplicate.pack &&
+		clear_packs &&
+		git index-pack --stdin <duplicate.pack &&
+
+		git multi-pack-index write --bitmap &&
+		git config pack.allowPackReuse single &&
+		test_pack_objects_reused_all "$objects_nr" 1 &&
+		rm -f got.idx &&
+		test_env GIT_TEST_MIDX_READ_BTMP=false \
+			test_pack_objects_reused_all 0 0
+	)
+'
+
+test_expect_success 'omit delta whose duplicate base is not selected' '
+	(
+		cd intra-pack-duplicate-objects &&
+
+		A=$(test_oid packlib_7_0) &&
+		B=$(test_oid packlib_7_76) &&
+		objects_nr=$(wc -l <objects) &&
+
+		a_size=$(wc -c <a-full) &&
+		test "$((2 * a_size))" -lt 128 &&
+
+		# The .idx order of duplicate OIDs is unspecified. Try a delta
+		# against each copy and keep the pack whose base was omitted.
+		for distance in "$((2 * a_size))" "$a_size"
+		do
+			base_offset=$((12 + 2 * a_size - distance)) &&
+			pack_obj_b_ofs_a "$distance" >b-delta &&
+			{
+				pack_header "$((objects_nr + 1))" &&
+				cat a-full a-full b-delta rest.entries
+			} >candidate.pack &&
+			pack_trailer candidate.pack &&
+			clear_packs &&
+			git index-pack --stdin <candidate.pack &&
+			git multi-pack-index write --bitmap || return 1
+
+			selected_offset=$(
+				test-tool read-midx --show-objects "$objdir" |
+				awk -v oid="$A" "\$1 == oid { print \$2 }"
+			) || return 1
+			test -n "$selected_offset" || return 1
+			test "$selected_offset" = "$base_offset" || break
+		done &&
+		test "$selected_offset" != "$base_offset" &&
+
+		test_pack_objects_reused_all "$((objects_nr - 1))" 1
+	)
+'
+
 test_done
-- 
2.55.0.383.gde07827a19

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

[Junio C Hamano]

Taylor Blau <ttaylorr@openai.com> writes:

> Packfiles containing duplicate object entries are unusual, but Git
> already accepts them outside of strict indexing.

That is looser than what we intended.  "unusual" -> "invalid".  It
is just like Git does not immediately complain until "git fsck",
"git repack", or otherwise "git" tries to use the object if you
corrupted loose object files under .git/objects/??/ directories.

Detecting such a problematic pack early before the problem spreads
is a very welcome change.