Skip to contentSkip to conversation

pack-objects: brown-paper-bag fixes for multi-pack reuse

PATCH In review Taylor Blau 3 participants 17 messages Aug 27, 2024 – Sep 17, 2024

lore
Share & tools
lore
#0 lore raw

cover pack-objects: brown-paper-bag fixes for multi-pack reuse

This series fixes a couple of issues (some cosmetic, others less so) in multi-pack reuse noticed when rolling this out over a few real-world, internal repositories on GitHub's servers.

The patches are laid out as follows:

- The first three patches demonstrate, prepare for, and fix a significant bug with multi-pack reuse which results in all sorts of strange behavior (explained in detail in the third commit of this series).

- The fourth patch is a minor (mostly cosmetic) performance optimization that avoids duplicate calls to pack_pos_to_offset() when performing pack-reuse with a MIDX bitmap.

- The final patch is a cosmetic fix to avoid using the value of a constant instead of the name constant itself.

Thanks in advance for your review!

Taylor Blau (5):
t/t5332-multi-pack-reuse.sh: verify pack generation with --strict
pack-bitmap: tag bitmapped packs with their corresponding MIDX builtin/pack-objects.c: translate bit positions during pack-reuse pack-bitmap.c: avoid repeated pack_pos_to_offset() during reuse builtin/pack-objects.c: do not open-code MAX_PACK_OBJECT_HEADER

 builtin/pack-objects.c      | 46 +++++++++++++++++++++++++++++--------
 midx.c                      |  1 +
 pack-bitmap.c               | 12 ++++++----
 pack-bitmap.h               |  1 +
 t/t5332-multi-pack-reuse.sh | 35 ++++++++++++++++++++++++----
 5 files changed, 78 insertions(+), 17 deletions(-)

base-commit: 159f2d50e75c17382c9f4eb7cbda671a6fa612d1

Signature · 1 line
2.46.0.426.g82754d92509
#1 lore raw

PATCH 1/5 t/t5332-multi-pack-reuse.sh: verify pack generation with --strict

In our tests for multi-pack reuse, we have two helper functions:

- test_pack_objects_reused_all(), and
- test_pack_objects_reused()

which invoke pack-objects (either with --all, or the supplied tips via stdin, respectively) and ensure that (a) the number of reused objects, and (b) the number of packs which those objects were reused from both match the expected values.

Both functions discard the output of pack-objects and assert only on the contents of the trace2 stream.

However, if we store the pack and attempt to index it with --strict, we find that a number of our tests are broken, indicating a bug within multi-pack reuse.

That bug will be addressed in a subsequent commit. But let's first harden these tests by trying to index the resulting pack, marking the tests which fail appropriately.

---
 t/t5332-multi-pack-reuse.sh | 20 ++++++++++++--------
 1 file changed, 12 insertions(+), 8 deletions(-)
t/t5332-multi-pack-reuse.sh +12 -8
index 941e73d354..ba888a83d5 100755
@@ -31,20 +31,24 @@ test_pack_objects_reused_all () {
 	: >trace2.txt &&
 	GIT_TRACE2_EVENT="$PWD/trace2.txt" \
 		git pack-objects --stdout --revs --all --delta-base-offset \
-		>/dev/null &&
+		>got.pack &&
 
 	test_pack_reused "$1" <trace2.txt &&
-	test_packs_reused "$2" <trace2.txt
+	test_packs_reused "$2" <trace2.txt &&
+
+	git index-pack --strict -o got.idx got.pack
 }
 
 # test_pack_objects_reused <pack-reused> <packs-reused>
 test_pack_objects_reused () {
 	: >trace2.txt &&
 	GIT_TRACE2_EVENT="$PWD/trace2.txt" \
-		git pack-objects --stdout --revs >/dev/null &&
+		git pack-objects --stdout --revs >got.pack &&
 
 	test_pack_reused "$1" <trace2.txt &&
-	test_packs_reused "$2" <trace2.txt
+	test_packs_reused "$2" <trace2.txt &&
+
+	git index-pack --strict -o got.idx got.pack
 }
 
 test_expect_success 'preferred pack is reused for single-pack reuse' '
@@ -65,7 +69,7 @@ test_expect_success 'multi-pack reuse is disabled by default' '
 	test_pack_objects_reused_all 3 1
 '
 
-test_expect_success 'feature.experimental implies multi-pack reuse' '
+test_expect_failure 'feature.experimental implies multi-pack reuse' '
 	test_config feature.experimental true &&
 
 	test_pack_objects_reused_all 6 2
@@ -82,7 +86,7 @@ test_expect_success 'enable multi-pack reuse' '
 	git config pack.allowPackReuse multi
 '
 
-test_expect_success 'reuse all objects from subset of bitmapped packs' '
+test_expect_failure 'reuse all objects from subset of bitmapped packs' '
 	test_commit C &&
 	git repack -d &&
 
@@ -96,7 +100,7 @@ test_expect_success 'reuse all objects from subset of bitmapped packs' '
 	test_pack_objects_reused 6 2 <in
 '
 
-test_expect_success 'reuse all objects from all packs' '
+test_expect_failure 'reuse all objects from all packs' '
 	test_pack_objects_reused_all 9 3
 '
 
@@ -190,7 +194,7 @@ test_expect_success 'omit delta with uninteresting base (same pack)' '
 	test_pack_objects_reused 3 1 <in
 '
 
-test_expect_success 'omit delta from uninteresting base (cross pack)' '
+test_expect_failure 'omit delta from uninteresting base (cross pack)' '
 	cat >in <<-EOF &&
 	$(git rev-parse $base)
 	^$(git rev-parse $delta)
Signature · 1 line
2.46.0.426.g82754d92509
#2 lore raw

PATCH 2/5 pack-bitmap: tag bitmapped packs with their corresponding MIDX

In reply to Taylor Blau

The next commit will need to use the bitmap's MIDX (if one exists) to translate bit positions into pack-relative positions in the source pack.

Ordinarily, we'd use the "midx" field of the bitmap_index struct. But since that struct is defined within pack-bitmap.c, and our caller is in a separate compilation unit, we do not have access to the MIDX field.

Instead, add a "from_midx" field to the bitmapped_pack structure so that we can use that piece of data from outside of pack-bitmap.c. The caller that uses this new piece of information will be added in the following commit.

---
 midx.c        | 1 +
 pack-bitmap.c | 1 +
 pack-bitmap.h | 1 +
 3 files changed, 3 insertions(+)
midx.c +1 -0
index ca98bfd7c6..67e0d64004 100644
@@ -496,6 +496,7 @@ int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m,
 				 MIDX_CHUNK_BITMAPPED_PACKS_WIDTH * local_pack_int_id +
 				 sizeof(uint32_t));
 	bp->pack_int_id = pack_int_id;
+	bp->from_midx = m;
 
 	return 0;
 }
pack-bitmap.c +1 -0
index 2e657a2aa4..218d7ac2eb 100644
@@ -2322,6 +2322,7 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,
 		packs[packs_nr].pack_int_id = pack_int_id;
 		packs[packs_nr].bitmap_nr = pack->num_objects;
 		packs[packs_nr].bitmap_pos = 0;
+		packs[packs_nr].from_midx = bitmap_git->midx;
 
 		objects_nr = packs[packs_nr++].bitmap_nr;
 	}
pack-bitmap.h +1 -0
index ff0fd815b8..d7f4b8b8e9 100644
@@ -60,6 +60,7 @@ struct bitmapped_pack {
 	uint32_t bitmap_pos;
 	uint32_t bitmap_nr;
 
+	struct multi_pack_index *from_midx; /* MIDX only */
 	uint32_t pack_int_id; /* MIDX only */
 };
 
Signature · 1 line
2.46.0.426.g82754d92509
#3 lore raw

Re: [PATCH 2/5] pack-bitmap: tag bitmapped packs with their corresponding MIDX

Quoted 24 lines · Taylor Blau

The next commit will need to use the bitmap's MIDX (if one exists) to translate bit positions into pack-relative positions in the source pack.

Ordinarily, we'd use the "midx" field of the bitmap_index struct. But since that struct is defined within pack-bitmap.c, and our caller is in a separate compilation unit, we do not have access to the MIDX field.

Instead, add a "from_midx" field to the bitmapped_pack structure so that we can use that piece of data from outside of pack-bitmap.c. The caller that uses this new piece of information will be added in the following commit.

---
 midx.c        | 1 +
 pack-bitmap.c | 1 +
 pack-bitmap.h | 1 +
 3 files changed, 3 insertions(+)
midx.c +0 -0
index ca98bfd7c6..67e0d64004 100644

midx.c int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m, · line 499

Quoted 4 lines
midx.c +1 -0
@@ -496,6 +496,7 @@ int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m,
 				 MIDX_CHUNK_BITMAPPED_PACKS_WIDTH * local_pack_int_id +
 				 sizeof(uint32_t));
 	bp->pack_int_id = pack_int_id;
+	bp->from_midx = m;

Do multi_pack_index objects live as long as bitmapped_pack objects that point at them live? If m later goes away without letting the bitmapped_pack know about it, the borrowed pointer in from_midx would become dangling, which is not what we want to see.

"None of these objects are released or relocated while we are running pack-objects, so once the .from_midx member is assigned here, it will always be pointing at a valid multi_pack_index object" is a satisfactory answer, I guess.

#4 lore raw

Re: [PATCH 2/5] pack-bitmap: tag bitmapped packs with their corresponding MIDX

Quoted 15 lines · Junio C Hamano

midx.c int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m, · line 499

Quoted 9 lines
midx.c +1 -0
index ca98bfd7c6..67e0d64004 100644
@@ -496,6 +496,7 @@ int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m,
 				 MIDX_CHUNK_BITMAPPED_PACKS_WIDTH * local_pack_int_id +
 				 sizeof(uint32_t));
 	bp->pack_int_id = pack_int_id;
+	bp->from_midx = m;

Do multi_pack_index objects live as long as bitmapped_pack objects that point at them live? If m later goes away without letting the bitmapped_pack know about it, the borrowed pointer in from_midx would become dangling, which is not what we want to see.

Quoted 4 lines

"None of these objects are released or relocated while we are running pack-objects, so once the .from_midx member is assigned here, it will always be pointing at a valid multi_pack_index object" is a satisfactory answer, I guess.

Good question, and good answer ;-).

This is only relevant in a read-only path where we're generating a new pack from existing packs and not altering those pack or rewriting / deleting the MIDX attached to them. So I think we're OK here and don't have any lifetime/scope issues.

Thanks,
Taylor

#5 lore raw

Re: [PATCH 2/5] pack-bitmap: tag bitmapped packs with their corresponding MIDX

Quoted 21 lines · Taylor Blau
Quoted 15 lines · Junio C Hamano

midx.c int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m, · line 499

Quoted 9 lines
midx.c +1 -0
index ca98bfd7c6..67e0d64004 100644
@@ -496,6 +496,7 @@ int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m,
 				 MIDX_CHUNK_BITMAPPED_PACKS_WIDTH * local_pack_int_id +
 				 sizeof(uint32_t));
 	bp->pack_int_id = pack_int_id;
+	bp->from_midx = m;

Do multi_pack_index objects live as long as bitmapped_pack objects that point at them live? If m later goes away without letting the bitmapped_pack know about it, the borrowed pointer in from_midx would become dangling, which is not what we want to see.

Quoted 4 lines

"None of these objects are released or relocated while we are running pack-objects, so once the .from_midx member is assigned here, it will always be pointing at a valid multi_pack_index object" is a satisfactory answer, I guess.

Quoted 6 lines

Good question, and good answer ;-).

This is only relevant in a read-only path where we're generating a new pack from existing packs and not altering those pack or rewriting / deleting the MIDX attached to them. So I think we're OK here and don't have any lifetime/scope issues.

Do we ever close/reopen the midx? For example, if a simultaneous process wrote a new one and we triggered reprepare_packed_git()?

I think the answer is "no"; we might read a new midx, but we never ditch the old one (just like we do for packed_git structs). Which I suspect is needed even before this patch, since various other parts of the bitmap code (and probably others) rely on the struct staying in place across as we read many objects.

-Peff

#6 lore raw

Re: [PATCH 2/5] pack-bitmap: tag bitmapped packs with their corresponding MIDX

Quoted 30 lines · Jeff King
Quoted 21 lines · Taylor Blau
Quoted 15 lines · Junio C Hamano

midx.c int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m, · line 499

Quoted 9 lines
midx.c +1 -0
index ca98bfd7c6..67e0d64004 100644
@@ -496,6 +496,7 @@ int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m,
 				 MIDX_CHUNK_BITMAPPED_PACKS_WIDTH * local_pack_int_id +
 				 sizeof(uint32_t));
 	bp->pack_int_id = pack_int_id;
+	bp->from_midx = m;

Do multi_pack_index objects live as long as bitmapped_pack objects that point at them live? If m later goes away without letting the bitmapped_pack know about it, the borrowed pointer in from_midx would become dangling, which is not what we want to see.

Quoted 4 lines

"None of these objects are released or relocated while we are running pack-objects, so once the .from_midx member is assigned here, it will always be pointing at a valid multi_pack_index object" is a satisfactory answer, I guess.

Quoted 6 lines

Good question, and good answer ;-).

This is only relevant in a read-only path where we're generating a new pack from existing packs and not altering those pack or rewriting / deleting the MIDX attached to them. So I think we're OK here and don't have any lifetime/scope issues.

Quoted 8 lines

Do we ever close/reopen the midx? For example, if a simultaneous process wrote a new one and we triggered reprepare_packed_git()?

I think the answer is "no"; we might read a new midx, but we never ditch the old one (just like we do for packed_git structs). Which I suspect is needed even before this patch, since various other parts of the bitmap code (and probably others) rely on the struct staying in place across as we read many objects.

I think that we *could* close and reopen the MIDX via a call to close_object_store() (which dispatches a call to close_midx(), before NULL-ing out o->multi_pack_index) and then calling prepare_packed_git() or similar.

But I'm not aware of any such codepaths that deal with pack reuse and calling nth_bitmapped_pack that would do such a thing, so I think that we're OK here.

Thanks,
Taylor

#7 lore raw

PATCH 3/5 builtin/pack-objects.c: translate bit positions during pack-reuse

In reply to Taylor Blau

When reusing chunks verbatim from an existing source pack, the function write_reused_pack() first attempts to reuse whole words (via the function write_reused_pack_verbatim()), and then individual bits (via write_reused_pack_one()).

In the non-MIDX case, all of this code works fine. Likewise, in the MIDX case, processing bits individually from the first (preferred) pack works fine. However, processing subsequent packs in the MIDX case is broken when there are duplicate objects among the set of MIDX'd packs.

This is because we treat the individual bit positions as valid pack positions within the source pack(s), which does not account for gaps in the source pack, like we see when the MIDX must break ties between duplicate objects which appear in multiple packs.

The broken code looks like:

    for (; i < reuse_packfile_bitmap->word_alloc; i++) {
            for (offset = 0; offset < BITS_IN_EWORD, offset++) {
                    /* ... */

                    write_reused_pack_one(reuse_packfile->p,
                                          pos + offset - reuse_packfile->bitmap_pos,
                                          f, pack_start, &w_curs);
            }
    }

, where the second argument is incorrect and does not account for gaps.

Instead, make sure that we translate bit positions in the MIDX's pseudo-pack order to pack positions in the respective source packs by:

- Translating the bit position (pseudo-pack order) to a MIDX position (lexical order).

- Use the MIDX position to obtain the offset at which the given object occurs in the source pack.

- Then translate that offset back into a pack relative position within the source pack by calling offset_to_pack_pos().

After doing this, then we can safely use the result as a pack position. Note that when doing single-pack reuse, as well as reusing objects from the MIDX's preferred pack, such translation is not necessary, since either ties are broken in favor of the preferred pack, or there are no ties to break at all (in the case of non-MIDX bitmaps).

Failing to do this can result in strange failure modes. One example that can occur when misinterpreting bits in the above fashion is that Git thinks it's supposed to send a delta that the caller does not want. Under this (incorrect) assumption, we try to look up the delta's base (so that we can patch any OFS_DELTAs if necessary). We do this using find_reused_offset().

But if we try and call that function for an offset belonging to an object we did not send, we'll get back garbage. This can result in us computing a negative fixup value, which results in memory corruption when trying to write the (patched) OFS_DELTA header.

---
 builtin/pack-objects.c      | 44 ++++++++++++++++++++++++++++++-------
 t/t5332-multi-pack-reuse.sh | 31 ++++++++++++++++++++++----
 2 files changed, 63 insertions(+), 12 deletions(-)
builtin/pack-objects.c +36 -8
index 778be80f56..700adfb5a8 100644
@@ -1191,6 +1191,7 @@ static void write_reused_pack(struct bitmapped_pack *reuse_packfile,
 		size_t pos = (i * BITS_IN_EWORD);
 
 		for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
+			uint32_t pack_pos;
 			if ((word >> offset) == 0)
 				break;
 
@@ -1199,14 +1200,41 @@ static void write_reused_pack(struct bitmapped_pack *reuse_packfile,
 				continue;
 			if (pos + offset >= reuse_packfile->bitmap_pos + reuse_packfile->bitmap_nr)
 				goto done;
-			/*
-			 * Can use bit positions directly, even for MIDX
-			 * bitmaps. See comment in try_partial_reuse()
-			 * for why.
-			 */
-			write_reused_pack_one(reuse_packfile->p,
-					      pos + offset - reuse_packfile->bitmap_pos,
-					      f, pack_start, &w_curs);
+
+			if (reuse_packfile->bitmap_pos) {
+				/*
+				 * 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.
+				 */
+				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");
+
+				midx_pos = pack_pos_to_midx(m, pos + offset);
+				pack_ofs = nth_midxed_offset(m, midx_pos);
+
+				if (offset_to_pack_pos(reuse_packfile->p,
+						       pack_ofs, &pack_pos) < 0)
+					BUG("could not find expected object at offset %"PRIuMAX" in pack %s",
+					    (uintmax_t)pack_ofs,
+					    pack_basename(reuse_packfile->p));
+			} else {
+				/*
+				 * Can use bit positions directly, even for MIDX
+				 * bitmaps. See comment in try_partial_reuse()
+				 * for why.
+				 */
+				pack_pos = pos + offset;
+			}
+
+			write_reused_pack_one(reuse_packfile->p, pack_pos, f,
+					      pack_start, &w_curs);
 			display_progress(progress_state, ++written);
 		}
 	}
t/t5332-multi-pack-reuse.sh +27 -4
index ba888a83d5..955ea42769 100755
@@ -69,7 +69,7 @@ test_expect_success 'multi-pack reuse is disabled by default' '
 	test_pack_objects_reused_all 3 1
 '
 
-test_expect_failure 'feature.experimental implies multi-pack reuse' '
+test_expect_success 'feature.experimental implies multi-pack reuse' '
 	test_config feature.experimental true &&
 
 	test_pack_objects_reused_all 6 2
@@ -86,7 +86,7 @@ test_expect_success 'enable multi-pack reuse' '
 	git config pack.allowPackReuse multi
 '
 
-test_expect_failure 'reuse all objects from subset of bitmapped packs' '
+test_expect_success 'reuse all objects from subset of bitmapped packs' '
 	test_commit C &&
 	git repack -d &&
 
@@ -100,7 +100,7 @@ test_expect_failure 'reuse all objects from subset of bitmapped packs' '
 	test_pack_objects_reused 6 2 <in
 '
 
-test_expect_failure 'reuse all objects from all packs' '
+test_expect_success 'reuse all objects from all packs' '
 	test_pack_objects_reused_all 9 3
 '
 
@@ -194,7 +194,7 @@ test_expect_success 'omit delta with uninteresting base (same pack)' '
 	test_pack_objects_reused 3 1 <in
 '
 
-test_expect_failure 'omit delta from uninteresting base (cross pack)' '
+test_expect_success 'omit delta from uninteresting base (cross pack)' '
 	cat >in <<-EOF &&
 	$(git rev-parse $base)
 	^$(git rev-parse $delta)
@@ -236,4 +236,27 @@ test_expect_success 'non-omitted delta in MIDX preferred pack' '
 	test_pack_objects_reused_all $(wc -l <expect) 1
 '
 
+test_expect_success 'duplicate objects' '
+	git init duplicate-objects &&
+	(
+		cd duplicate-objects &&
+
+		git config pack.allowPackReuse multi &&
+
+		test_commit base &&
+
+		git repack -a &&
+
+		git rev-parse HEAD^{tree} >in &&
+		p="$(git pack-objects $packdir/pack <in)" &&
+
+		git multi-pack-index write --bitmap --preferred-pack=pack-$p.idx &&
+
+		objects_nr="$(git rev-list --count --all --objects)" &&
+		packs_nr="$(find $packdir -type f -name "pack-*.pack" | wc -l)" &&
+
+		test_pack_objects_reused_all $objects_nr $packs_nr
+	)
+'
+
 test_done
Signature · 1 line
2.46.0.426.g82754d92509
#8 lore raw

Re: [PATCH 3/5] builtin/pack-objects.c: translate bit positions during pack-reuse

Quoted 11 lines · Taylor Blau

Instead, make sure that we translate bit positions in the MIDX's pseudo-pack order to pack positions in the respective source packs by:

- Translating the bit position (pseudo-pack order) to a MIDX position (lexical order).

- Use the MIDX position to obtain the offset at which the given object occurs in the source pack.

- Then translate that offset back into a pack relative position within the source pack by calling offset_to_pack_pos().

Quite straight-forward, and the implementation below matches the design well.

#9 lore raw

PATCH 4/5 pack-bitmap.c: avoid repeated `pack_pos_to_offset()` during reuse

In reply to Taylor Blau

When calling try_partial_reuse(), the (sole) caller from the function reuse_partial_packfile_from_bitmap_1() has to translate its bit position to a pack position.

In the MIDX bitmap case, the caller translates from the bit position, to a position in the MIDX's pseudo-pack order (with pack_pos_to_midx()), then get a pack offset (with nth_midxed_offset()) before finally working backwards to get the pack position in the source pack by calling offset_to_pack_pos().

In the non-MIDX bitmap case, we can use the bit position as the pack position directly (see the comment at the beginning of the reuse_partial_packfile_from_bitmap_1() function for why).

In either case, the first thing that try_partial_reuse() does after being called is determine the offset of the object at the given pack position by calling pack_pos_to_offset(). But we already have that information in the MIDX case!

Avoid re-computing that information by instead passing it in. In the MIDX case, we already have that information stored. In the non-MIDX case, the call to pack_pos_to_offset() moves from the function try_partial_reuse() to its caller. In total, we'll save one call to pack_pos_to_offset() when processing MIDX bitmaps.

(On my machine, there is a slight speed-up on the order of ~2ms, but it is within the margin of error over 10 runs, so I think you'd have to have a truly gigantic repository to confidently measure any significant improvement here).

---
 pack-bitmap.c | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)
pack-bitmap.c +7 -4
index 218d7ac2eb..9d9b8c4bfb 100644
@@ -2055,17 +2055,18 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,
 			     struct bitmapped_pack *pack,
 			     size_t bitmap_pos,
 			     uint32_t pack_pos,
+			     off_t offset,
 			     struct bitmap *reuse,
 			     struct pack_window **w_curs)
 {
-	off_t offset, delta_obj_offset;
+	off_t delta_obj_offset;
 	enum object_type type;
 	unsigned long size;
 
 	if (pack_pos >= pack->p->num_objects)
 		return -1; /* not actually in the pack */
 
-	offset = delta_obj_offset = pack_pos_to_offset(pack->p, pack_pos);
+	delta_obj_offset = offset;
 	type = unpack_object_header(pack->p, w_curs, &offset, &size);
 	if (type < 0)
 		return -1; /* broken packfile, punt */
@@ -2184,6 +2185,7 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git
 		for (offset = 0; offset < BITS_IN_EWORD; offset++) {
 			size_t bit_pos;
 			uint32_t pack_pos;
+			off_t ofs;
 
 			if (word >> offset == 0)
 				break;
@@ -2198,7 +2200,6 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git
 
 			if (bitmap_is_midx(bitmap_git)) {
 				uint32_t midx_pos;
-				off_t ofs;
 
 				midx_pos = pack_pos_to_midx(bitmap_git->midx, bit_pos);
 				ofs = nth_midxed_offset(bitmap_git->midx, midx_pos);
@@ -2213,10 +2214,12 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git
 					BUG("advanced beyond the end of pack %s (%"PRIuMAX" > %"PRIu32")",
 					    pack_basename(pack->p), (uintmax_t)pack_pos,
 					    pack->p->num_objects);
+
+				ofs = pack_pos_to_offset(pack->p, pack_pos);
 			}
 
 			if (try_partial_reuse(bitmap_git, pack, bit_pos,
-					      pack_pos, reuse, &w_curs) < 0) {
+					      pack_pos, ofs, reuse, &w_curs) < 0) {
 				/*
 				 * try_partial_reuse indicated we couldn't reuse
 				 * any bits, so there is no point in trying more
Signature · 1 line
2.46.0.426.g82754d92509
#10 lore raw

Re: [PATCH 4/5] pack-bitmap.c: avoid repeated `pack_pos_to_offset()` during reuse

Quoted 7 lines · Taylor Blau
pack-bitmap.c +1 -0
@@ -2055,17 +2055,18 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,
 			     struct bitmapped_pack *pack,
 			     size_t bitmap_pos,
 			     uint32_t pack_pos,
+			     off_t offset,
 			     struct bitmap *reuse,
 			     struct pack_window **w_curs)

pack-bitmap.c static int try_partial_reuse(struct bitmap_index *bitmap_git, · line 2068

Quoted 10 lines
pack-bitmap.c +1 -2
 {
-	off_t offset, delta_obj_offset;
+	off_t delta_obj_offset;
 	enum object_type type;
 	unsigned long size;
 
 	if (pack_pos >= pack->p->num_objects)
 		return -1; /* not actually in the pack */
 
-	offset = delta_obj_offset = pack_pos_to_offset(pack->p, pack_pos);

We are now passing redundant piece of information "offset" that could be derived from two other parameters, which feels a bit icky,

I suspect that try_partial_reuse() can be taught not to require pack_pos and instead work entirely on offset

- The caller can pass a very large offset to represent "not actually in the pack" early return condition.

- The logic to punt on a delta pointing backwards can be done by comparing the base_offset and offset, instead of comparing the base_pos and pack_pos.

but it may not be worth the effort, unless we are going to do similar clean-up globally in all the codepaths that access packfiles.

Thanks.

#11 lore raw

Re: [PATCH 4/5] pack-bitmap.c: avoid repeated `pack_pos_to_offset()` during reuse

Quoted 15 lines · Junio C Hamano
Quoted 13 lines · Taylor Blau
(quoted diff) +2 -1
@@ -2055,17 +2055,18 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,
 			     struct bitmapped_pack *pack,
 			     size_t bitmap_pos,
 			     uint32_t pack_pos,
+			     off_t offset,
 			     struct bitmap *reuse,
 			     struct pack_window **w_curs)
 {
-	off_t offset, delta_obj_offset;
+	off_t delta_obj_offset;
 	enum object_type type;
 	unsigned long size;
 
Quoted 7 lines

Review static int try_partial_reuse(struct bitmap_index *bitmap_git, · line 2068

Quoted 4 lines
(quoted diff) +0 -1
 	if (pack_pos >= pack->p->num_objects)
 		return -1; /* not actually in the pack */
 
-	offset = delta_obj_offset = pack_pos_to_offset(pack->p, pack_pos);

We are now passing redundant piece of information "offset" that could be derived from two other parameters, which feels a bit icky,

Yeah, I agree. The only spot we use pack_pos in this function is in the hunk above, and in the check where we reject any deltas whose base has a greater than or equal to bit position than the delta object's bit position.

But I think both of those are redundant. The only caller in reuse_partial_packfile_from_bitmap_1() only passes bit positions that are set, so we'll never trip the bounds check above. For the latter check, it would suffice to compare object offsets in the single-pack case, since the bit positions corresponding to objects in a single pack are derived from the ordering of their actual offset.

Quoted 3 lines

- The logic to punt on a delta pointing backwards can be done by comparing the base_offset and offset, instead of comparing the base_pos and pack_pos.

Ah, yes -- exactly ;-). I should have read the email in its entirety before starting to respond.

Quoted 3 lines

but it may not be worth the effort, unless we are going to do similar clean-up globally in all the codepaths that access packfiles.

I'm not so sure we can do it in all cases, but at least in the case of try_partial_reuse(), doing something like this (which compiles and passes "make test") is fine:

--- 8< ---

pack-bitmap.c +8 -7
index 9d9b8c4bfb..fc51f298d5 100644
@@ -2054,7 +2054,6 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,
 static int try_partial_reuse(struct bitmap_index *bitmap_git,
 			     struct bitmapped_pack *pack,
 			     size_t bitmap_pos,
-			     uint32_t pack_pos,
 			     off_t offset,
 			     struct bitmap *reuse,
 			     struct pack_window **w_curs)
@@ -2063,9 +2062,6 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,
 	enum object_type type;
 	unsigned long size;
 
-	if (pack_pos >= pack->p->num_objects)
-		return -1; /* not actually in the pack */
-
 	delta_obj_offset = offset;
 	type = unpack_object_header(pack->p, w_curs, &offset, &size);
 	if (type < 0)
@@ -2121,8 +2117,13 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,
 			 * OFS_DELTA is the default). But let's double check to
 			 * make sure the pack wasn't written with odd
 			 * parameters.
+			 *
+			 * Since we're working on a single-pack bitmap, we can
+			 * use the object offset as a proxy for the bit
+			 * position, since the bits are ordered by their
+			 * positions within the pack.
 			 */
-			if (base_pos >= pack_pos)
+			if (base_offset >= offset)
 				return 0;
 			base_bitmap_pos = pack->bitmap_pos + base_pos;
 		}
@@ -2218,8 +2219,8 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git
 				ofs = pack_pos_to_offset(pack->p, pack_pos);
 			}
 
-			if (try_partial_reuse(bitmap_git, pack, bit_pos,
-					      pack_pos, ofs, reuse, &w_curs) < 0) {
+			if (try_partial_reuse(bitmap_git, pack, bit_pos, ofs,
+					      reuse, &w_curs) < 0) {
 				/*
 				 * try_partial_reuse indicated we couldn't reuse
 				 * any bits, so there is no point in trying more

--- >8 ---

Thanks,
Taylor

#12 lore raw

PATCH 5/5 builtin/pack-objects.c: do not open-code `MAX_PACK_OBJECT_HEADER`

In reply to Taylor Blau

The function write_reused_pack_one() defines an header to store the OFS_DELTA header, but uses the constant "10" instead of "MAX_PACK_OBJECT_HEADER" (as is done elsewhere in the same patch, circa bb514de356c (pack-objects: improve partial packfile reuse, 2019-12-18)).

Declare the ofs_header field to be sized according to MAX_PACK_OBJECT_HEADER (which is 10, as defined in "pack.h") instead of the constant 10.

---
 builtin/pack-objects.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
builtin/pack-objects.c +1 -1
index 700adfb5a8..c6e2852d3c 100644
@@ -1072,7 +1072,7 @@ static void write_reused_pack_one(struct packed_git *reuse_packfile,
 		fixup = find_reused_offset(offset) -
 			find_reused_offset(base_offset);
 		if (fixup) {
-			unsigned char ofs_header[10];
+			unsigned char ofs_header[MAX_PACK_OBJECT_HEADER];
 			unsigned i, ofs_len;
 			off_t ofs = offset - base_offset - fixup;
 
Signature · 1 line
2.46.0.426.g82754d92509
#13 lore raw
In reply to Taylor Blau
Quoted 3 lines · Taylor Blau

This series fixes a couple of issues (some cosmetic, others less so) in multi-pack reuse noticed when rolling this out over a few real-world, internal repositories on GitHub's servers.

I cannot claim I got all the detail that went into steps 2 & 3 right, but I was irritated enough that the topic was left in the "Needs review" state, so I gave a look at the tail end of the series, and they were pleasant read.

Thanks.

#14 lore raw
Quoted 10 lines · Junio C Hamano
Quoted 3 lines · Taylor Blau

This series fixes a couple of issues (some cosmetic, others less so) in multi-pack reuse noticed when rolling this out over a few real-world, internal repositories on GitHub's servers.

I cannot claim I got all the detail that went into steps 2 & 3 right, but I was irritated enough that the topic was left in the "Needs review" state, so I gave a look at the tail end of the series, and they were pleasant read.

Thanks. They were anything *but* a pleasant debugging session, but I'm glad that the end result was palatable ;-).

Thanks,
Taylor

#15 lore raw
In reply to Junio C Hamano
Quoted 10 lines · Junio C Hamano
Quoted 3 lines · Taylor Blau

This series fixes a couple of issues (some cosmetic, others less so) in multi-pack reuse noticed when rolling this out over a few real-world, internal repositories on GitHub's servers.

I cannot claim I got all the detail that went into steps 2 & 3 right, but I was irritated enough that the topic was left in the "Needs review" state, so I gave a look at the tail end of the series, and they were pleasant read.

Sorry, I'm probably the most qualified reviewer here. I read through the early patches, and I think the fix is correct, along with the preparation in patch 2.

With the partial disclaimer that I helped with the early debugging, and my blind flailing at suggestions accidentally led Taylor to the right answer. I don't think that biases my perspective, but maybe. ;)

-Peff

#16 lore raw
Quoted 13 lines · Jeff King
Quoted 10 lines · Junio C Hamano
Quoted 3 lines · Taylor Blau

This series fixes a couple of issues (some cosmetic, others less so) in multi-pack reuse noticed when rolling this out over a few real-world, internal repositories on GitHub's servers.

I cannot claim I got all the detail that went into steps 2 & 3 right, but I was irritated enough that the topic was left in the "Needs review" state, so I gave a look at the tail end of the series, and they were pleasant read.

Quoted 7 lines

Sorry, I'm probably the most qualified reviewer here. I read through the early patches, and I think the fix is correct, along with the preparation in patch 2.

With the partial disclaimer that I helped with the early debugging, and my blind flailing at suggestions accidentally led Taylor to the right answer. I don't think that biases my perspective, but maybe. ;)

Thanks.