[PATCH 0/5] pack-objects: brown-paper-bag fixes for multi-pack reuse

[PATCH 0/5] pack-objects: brown-paper-bag fixes for multi-pack reuse

[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.

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
-- 
2.46.0.426.g82754d92509

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

[Taylor Blau]

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.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 t/t5332-multi-pack-reuse.sh | 20 ++++++++++++--------
 1 file changed, 12 insertions(+), 8 deletions(-)

diff --git a/t/t5332-multi-pack-reuse.sh b/t/t5332-multi-pack-reuse.sh
index 941e73d354..ba888a83d5 100755
--- a/t/t5332-multi-pack-reuse.sh
+++ b/t/t5332-multi-pack-reuse.sh
@@ -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)
-- 
2.46.0.426.g82754d92509

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

[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.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 midx.c        | 1 +
 pack-bitmap.c | 1 +
 pack-bitmap.h | 1 +
 3 files changed, 3 insertions(+)

diff --git a/midx.c b/midx.c
index ca98bfd7c6..67e0d64004 100644
--- a/midx.c
+++ b/midx.c
@@ -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;
 }
diff --git a/pack-bitmap.c b/pack-bitmap.c
index 2e657a2aa4..218d7ac2eb 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -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;
 	}
diff --git a/pack-bitmap.h b/pack-bitmap.h
index ff0fd815b8..d7f4b8b8e9 100644
--- a/pack-bitmap.h
+++ b/pack-bitmap.h
@@ -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 */
 };
 
-- 
2.46.0.426.g82754d92509

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

[Junio C Hamano]

Taylor Blau <me@ttaylorr.com> writes:

> 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.
>
> Signed-off-by: Taylor Blau <me@ttaylorr.com>
> ---
>  midx.c        | 1 +
>  pack-bitmap.c | 1 +
>  pack-bitmap.h | 1 +
>  3 files changed, 3 insertions(+)
>
> diff --git a/midx.c b/midx.c
> index ca98bfd7c6..67e0d64004 100644
> --- a/midx.c
> +++ b/midx.c
> @@ -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.

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

[Taylor Blau]

On Tue, Aug 27, 2024 at 05:14:14PM -0700, Junio C Hamano wrote:
> > diff --git a/midx.c b/midx.c
> > index ca98bfd7c6..67e0d64004 100644
> > --- a/midx.c
> > +++ b/midx.c
> > @@ -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.

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

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

[Jeff King]

On Thu, Aug 29, 2024 at 02:58:19PM -0400, Taylor Blau wrote:

> On Tue, Aug 27, 2024 at 05:14:14PM -0700, Junio C Hamano wrote:
> > > diff --git a/midx.c b/midx.c
> > > index ca98bfd7c6..67e0d64004 100644
> > > --- a/midx.c
> > > +++ b/midx.c
> > > @@ -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.
> 
> 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

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

[Taylor Blau]

On Thu, Sep 05, 2024 at 05:00:24AM -0400, Jeff King wrote:
> On Thu, Aug 29, 2024 at 02:58:19PM -0400, Taylor Blau wrote:
>
> > On Tue, Aug 27, 2024 at 05:14:14PM -0700, Junio C Hamano wrote:
> > > > diff --git a/midx.c b/midx.c
> > > > index ca98bfd7c6..67e0d64004 100644
> > > > --- a/midx.c
> > > > +++ b/midx.c
> > > > @@ -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.
> >
> > 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.

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

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

[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.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/pack-objects.c      | 44 ++++++++++++++++++++++++++++++-------
 t/t5332-multi-pack-reuse.sh | 31 ++++++++++++++++++++++----
 2 files changed, 63 insertions(+), 12 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 778be80f56..700adfb5a8 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -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);
 		}
 	}
diff --git a/t/t5332-multi-pack-reuse.sh b/t/t5332-multi-pack-reuse.sh
index ba888a83d5..955ea42769 100755
--- a/t/t5332-multi-pack-reuse.sh
+++ b/t/t5332-multi-pack-reuse.sh
@@ -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
-- 
2.46.0.426.g82754d92509

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

[Junio C Hamano]

Taylor Blau <me@ttaylorr.com> writes:

> 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.

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

[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).

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-bitmap.c | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)

diff --git a/pack-bitmap.c b/pack-bitmap.c
index 218d7ac2eb..9d9b8c4bfb 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -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
-- 
2.46.0.426.g82754d92509

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

[Junio C Hamano]

Taylor Blau <me@ttaylorr.com> writes:

> @@ -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);

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.

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

[Taylor Blau]

On Wed, Sep 04, 2024 at 11:54:18AM -0700, Junio C Hamano wrote:
> Taylor Blau <me@ttaylorr.com> writes:
>
> > @@ -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);
>
> 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.

>  - 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.

> 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< ---
diff --git a/pack-bitmap.c b/pack-bitmap.c
index 9d9b8c4bfb..fc51f298d5 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -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

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

[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.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/pack-objects.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 700adfb5a8..c6e2852d3c 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -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;
 
-- 
2.46.0.426.g82754d92509

Re: [PATCH 0/5] pack-objects: brown-paper-bag fixes for multi-pack reuse

[Junio C Hamano]

Taylor Blau <me@ttaylorr.com> writes:

> 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.

Re: [PATCH 0/5] pack-objects: brown-paper-bag fixes for multi-pack reuse

[Taylor Blau]

On Wed, Sep 04, 2024 at 11:56:27AM -0700, Junio C Hamano wrote:
> Taylor Blau <me@ttaylorr.com> writes:
>
> > 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

Re: [PATCH 0/5] pack-objects: brown-paper-bag fixes for multi-pack reuse

[Jeff King]

On Wed, Sep 04, 2024 at 11:56:27AM -0700, Junio C Hamano wrote:

> Taylor Blau <me@ttaylorr.com> writes:
> 
> > 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

Re: [PATCH 0/5] pack-objects: brown-paper-bag fixes for multi-pack reuse

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Wed, Sep 04, 2024 at 11:56:27AM -0700, Junio C Hamano wrote:
>
>> Taylor Blau <me@ttaylorr.com> writes:
>> 
>> > 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. ;)

Thanks.