[PATCH 0/2] revision: exclude all packed objects with `--unpacked`

[PATCH 0/2] revision: exclude all packed objects with `--unpacked`

[Taylor Blau]

While working on my longer series to enable verbatim pack reuse across
multiple packs[^1], I noticed a couple of oddities with the `--unpacked`
rev-walk flag.

While it does exclude packed commits, it does not exclude (all) packed
trees/blobs/annotated tags. This problem exists in the pack-bitmap
machinery, too, which will over-count queries like:

    $ git rev-list --use-bitmap-index --all --unpacked --objects

, etc.

The fix is relatively straightforward, split across two patches that
Peff and I worked on together earlier today.

This is technically a backwards-incompatible change, but the existing
behavior is broken and does not match the documented behavior, so I
think in this case we are OK to change --unpacked to faithfully
implement its documentation.

[^1]: Which, I'm very excited to say, is working :-).

Taylor Blau (2):
  list-objects: drop --unpacked non-commit objects from results
  pack-bitmap: drop --unpacked non-commit objects from results

 list-objects.c                     |  3 +++
 pack-bitmap.c                      | 27 +++++++++++++++++++++++++++
 t/t6000-rev-list-misc.sh           | 13 +++++++++++++
 t/t6113-rev-list-bitmap-filters.sh | 13 +++++++++++++
 t/t6115-rev-list-du.sh             |  7 +++++++
 5 files changed, 63 insertions(+)


base-commit: bc5204569f7db44d22477485afd52ea410d83743
-- 
2.43.0.rc0.2.gef6b2154a3

[PATCH 1/2] list-objects: drop --unpacked non-commit objects from results

[Taylor Blau]

In git-rev-list(1), we describe the `--unpacked` option as:

    Only useful with `--objects`; print the object IDs that are not in
    packs.

This is true of commits, which we discard via get_commit_action(), but
not of the objects they reach. So if we ask for an --objects traversal
with --unpacked, we may get arbitrarily many objects which are indeed
packed.

I am nearly certain this behavior dates back to the introduction of
`--unpacked` via 12d2a18780 ("git rev-list --unpacked" shows only
unpacked commits, 2005-07-03), but I couldn't get that revision of Git
to compile for me. At least as early as v2.0.0 this has been subtly
broken:

    $ git.compile --version
    git version 2.0.0

    $ git.compile rev-list --objects --all --unpacked
    72791fe96c93f9ec5c311b8bc966ab349b3b5bbe
    05713d991c18bbeef7e154f99660005311b5004d v1.0
    153ed8b7719c6f5a68ce7ffc43133e95a6ac0fdb
    8e4020bb5a8d8c873b25de15933e75cc0fc275df one
    9200b628cf9dc883a85a7abc8d6e6730baee589c two
    3e6b46e1b7e3b91acce99f6a823104c28aae0b58 unpacked.t

There, only the first, third, and sixth entries are loose, with the
remaining set of objects belonging to at least one pack.

The implications for this are relatively benign: bare 'git repack'
invocations which invoke pack-objects with --unpacked are impacted, and
at worst we'll store a few extra objects that should have been excluded.

Arguably changing this behavior is a backwards-incompatible change,
since it alters the set of objects emitted from rev-list queries with
`--objects` and `--unpacked`. But I argue that this change is still
sensible, since the existing implementation deviates from
clearly-written documentation.

The fix here is straightforward: avoid showing any non-commit objects
which are contained in packs by discarding them within list-objects.c,
before they are shown to the user. Note that similar treatment for
`list-objects.c::show_commit()` is not needed, since that case is
already handled by `revision.c::get_commit_action()`.

Co-authored-by: Jeff King <peff@peff.net>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 list-objects.c           |  3 +++
 t/t6000-rev-list-misc.sh | 13 +++++++++++++
 2 files changed, 16 insertions(+)

diff --git a/list-objects.c b/list-objects.c
index c25c72b32c..c8a5fb998e 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -39,6 +39,9 @@ static void show_object(struct traversal_context *ctx,
 {
 	if (!ctx->show_object)
 		return;
+	if (ctx->revs->unpacked && has_object_pack(&object->oid))
+		return;
+
 	ctx->show_object(object, name, ctx->show_data);
 }
 
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index 12def7bcbf..6289a2e8b0 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -169,4 +169,17 @@ test_expect_success 'rev-list --count --objects' '
 	test_line_count = $count actual
 '
 
+test_expect_success 'rev-list --unpacked' '
+	git repack -ad &&
+	test_commit unpacked &&
+
+	git rev-list --objects --no-object-names unpacked^.. >expect.raw &&
+	sort expect.raw >expect &&
+
+	git rev-list --all --objects --unpacked --no-object-names >actual.raw &&
+	sort actual.raw >actual &&
+
+	test_cmp expect actual
+'
+
 test_done
-- 
2.43.0.rc0.2.gef6b2154a3

Re: [PATCH 1/2] list-objects: drop --unpacked non-commit objects from results

[Junio C Hamano]

Taylor Blau <me@ttaylorr.com> writes:

> Subject: Re: [PATCH 1/2] list-objects: drop --unpacked non-commit objects from results

I thought the purpose of this change is to make sure that we drop
packed objects from results when --unpacked is given?  This makes
it sound as if we are dropping unpacked ones instead?  I dunno.

> In git-rev-list(1), we describe the `--unpacked` option as:
>
>     Only useful with `--objects`; print the object IDs that are not in
>     packs.
>
> This is true of commits, which we discard via get_commit_action(), but
> not of the objects they reach. So if we ask for an --objects traversal
> with --unpacked, we may get arbitrarily many objects which are indeed
> packed.

Strictly speaking, as long as all the objects that are not in packs
are shown, "print the object IDs that are not in packs" is satisfied.
With this fix, perhaps we would want to tighten the explanation a
little bit while we are at it.  Perhaps

	print the object names but exclude those that are in packs

or something along that line?

> diff --git a/list-objects.c b/list-objects.c
> index c25c72b32c..c8a5fb998e 100644
> --- a/list-objects.c
> +++ b/list-objects.c
> @@ -39,6 +39,9 @@ static void show_object(struct traversal_context *ctx,
>  {
>  	if (!ctx->show_object)
>  		return;
> +	if (ctx->revs->unpacked && has_object_pack(&object->oid))
> +		return;
> +
>  	ctx->show_object(object, name, ctx->show_data);
>  }

The implementation is as straight-forward as it can get.  Very
pleasing.

> diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
> index 12def7bcbf..6289a2e8b0 100755
> --- a/t/t6000-rev-list-misc.sh
> +++ b/t/t6000-rev-list-misc.sh
> @@ -169,4 +169,17 @@ test_expect_success 'rev-list --count --objects' '
>  	test_line_count = $count actual
>  '
>  
> +test_expect_success 'rev-list --unpacked' '
> +	git repack -ad &&
> +	test_commit unpacked &&
> +
> +	git rev-list --objects --no-object-names unpacked^.. >expect.raw &&
> +	sort expect.raw >expect &&
> +
> +	git rev-list --all --objects --unpacked --no-object-names >actual.raw &&
> +	sort actual.raw >actual &&
> +
> +	test_cmp expect actual
> +'
> +
>  test_done

Re: [PATCH 1/2] list-objects: drop --unpacked non-commit objects from results

[Jeff King]

On Tue, Nov 07, 2023 at 11:21:29AM +0900, Junio C Hamano wrote:

> > In git-rev-list(1), we describe the `--unpacked` option as:
> >
> >     Only useful with `--objects`; print the object IDs that are not in
> >     packs.
> >
> > This is true of commits, which we discard via get_commit_action(), but
> > not of the objects they reach. So if we ask for an --objects traversal
> > with --unpacked, we may get arbitrarily many objects which are indeed
> > packed.
> 
> Strictly speaking, as long as all the objects that are not in packs
> are shown, "print the object IDs that are not in packs" is satisfied.
> With this fix, perhaps we would want to tighten the explanation a
> little bit while we are at it.  Perhaps
> 
> 	print the object names but exclude those that are in packs
> 
> or something along that line?

I think using the word "exclude" is a good idea, as it makes it clear
that we are omitting objects that otherwise would be traversed (as
opposed to just showing unpacked objects, reachable or not).

But I wanted to point out one other subtlety here. The existing code
(before this patch) checks for already-packed commits, and avoids adding
them to the traversal. The problem this patch is fixing is that we may
see objects they point to via other non-packed commits. But the opposite
problem exists, too: we have unpacked objects that are reachable from
those packed commits.

It's probably reasonably rare, since we _tend_ to make packs by rolling
up reachable chunks of history. But that's not a guarantee. One way I
can think of for it to happen in practice is that somebody pushes (or
fetches) a thin pack with commit C as a delta against an unpacked C'. In
that case "index-pack --fix-thin" will create a duplicate of C' in the
new pack, but its trees and blobs may remain unpacked.

I think with the patch in this series we could actually drop that "do
not traverse commits that are unpacked" line of code, and end up "more
correct". But I suspect performance of an incremental "git repack -d"
would suffer. This is kind of analagous to the "we do not traverse every
UNINTERESTING commit just to mark its trees/blobs as UNINTERESTING"
optimization. We know that it is not a true set difference, but it is OK
in practice and it buys us a lot of performance. And just like that
case, bitmaps do let us cheaply compute the true set difference. ;)

-Peff

[PATCH 2/2] pack-bitmap: drop --unpacked non-commit objects from results

[Taylor Blau]

When performing revision queries with `--objects` and
`--use-bitmap-index`, the output may incorrectly contain objects which
are packed, even when the `--unpacked` option is given. This affects
traversals, but also other querying operations, like `--count`,
`--disk-usage`, etc.

Like in the previous commit, the fix is to exclude those objects from
the result set before they are shown to the user (or, in this case,
before the bitmap containing the result of the traversal is enumerated
and its objects listed).

This is performed by a new function in pack-bitmap.c, called
`filter_packed_objects_from_bitmap()`. Note that we do not have to
inspect individual bits in the result bitmap, since we know that the
first N (where N is the number of objects in the bitmap's pack/MIDX)
bits correspond to objects which packed by definition.

In other words, for an object to have a bitmap position (not in the
extended index), it must appear in either the bitmap's pack or one of
the packs in its MIDX.

This presents an appealing optimization to us, which is that we can
simply memset() the corresponding number of `eword_t`'s to zero,
provided that we handle any objects which spill into the next word (but
don't occupy all 64 bits of the word itself).

We only have to handle objects in the bitmap's extended index. These
objects may (or may not) appear in one or more pack(s). Since these
objects are known to not appear in either the bitmap's MIDX or pack,
they may be stored as loose, appear in other pack(s), or both.

Before returning a bitmap containing the result of the traversal back to
the caller, drop any bits from the extended index which appear in one or
more packs. This implements the correct behavior for rev-list operations
which use the bitmap index to compute their result.

Co-authored-by: Jeff King <peff@peff.net>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-bitmap.c                      | 27 +++++++++++++++++++++++++++
 t/t6113-rev-list-bitmap-filters.sh | 13 +++++++++++++
 t/t6115-rev-list-du.sh             |  7 +++++++
 3 files changed, 47 insertions(+)

diff --git a/pack-bitmap.c b/pack-bitmap.c
index ca8319b87c..0260890341 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -1666,6 +1666,30 @@ static int can_filter_bitmap(struct list_objects_filter_options *filter)
 	return !filter_bitmap(NULL, NULL, NULL, filter);
 }
 
+
+static void filter_packed_objects_from_bitmap(struct bitmap_index *bitmap_git,
+					      struct bitmap *result)
+{
+	struct eindex *eindex = &bitmap_git->ext_index;
+	uint32_t objects_nr;
+	size_t i, pos;
+
+	objects_nr = bitmap_num_objects(bitmap_git);
+	pos = objects_nr / BITS_IN_EWORD;
+
+	if (pos > result->word_alloc)
+		pos = result->word_alloc;
+
+	memset(result->words, 0x00, sizeof(eword_t) * pos);
+	for (i = pos * BITS_IN_EWORD; i < objects_nr; i++)
+		bitmap_unset(result, i);
+
+	for (i = 0; i < eindex->count; ++i) {
+		if (has_object_pack(&eindex->objects[i]->oid))
+			bitmap_unset(result, objects_nr + i);
+	}
+}
+
 struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,
 					 int filter_provided_objects)
 {
@@ -1788,6 +1812,9 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,
 		      wants_bitmap,
 		      &revs->filter);
 
+	if (revs->unpacked)
+		filter_packed_objects_from_bitmap(bitmap_git, wants_bitmap);
+
 	bitmap_git->result = wants_bitmap;
 	bitmap_git->haves = haves_bitmap;
 
diff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh
index 4d8e09167e..86c70521f1 100755
--- a/t/t6113-rev-list-bitmap-filters.sh
+++ b/t/t6113-rev-list-bitmap-filters.sh
@@ -141,4 +141,17 @@ test_expect_success 'combine filter with --filter-provided-objects' '
 	done <objects
 '
 
+test_expect_success 'bitmap traversal with --unpacked' '
+	git repack -adb &&
+	test_commit unpacked &&
+
+	git rev-list --objects --no-object-names unpacked^.. >expect.raw &&
+	sort expect.raw >expect &&
+
+	git rev-list --use-bitmap-index --objects --all --unpacked >actual.raw &&
+	sort actual.raw >actual &&
+
+	test_cmp expect actual
+'
+
 test_done
diff --git a/t/t6115-rev-list-du.sh b/t/t6115-rev-list-du.sh
index d59111dede..c0cfda62fa 100755
--- a/t/t6115-rev-list-du.sh
+++ b/t/t6115-rev-list-du.sh
@@ -48,6 +48,13 @@ check_du HEAD
 check_du --objects HEAD
 check_du --objects HEAD^..HEAD
 
+test_expect_success 'setup for --unpacked tests' '
+	git repack -adb &&
+	test_commit unpacked
+'
+
+check_du --all --objects --unpacked
+
 # As mentioned above, don't use hardcode sizes as actual size, but use the
 # output from git cat-file.
 test_expect_success 'rev-list --disk-usage=human' '
-- 
2.43.0.rc0.2.gef6b2154a3

Re: [PATCH 2/2] pack-bitmap: drop --unpacked non-commit objects from results

[Junio C Hamano]

Taylor Blau <me@ttaylorr.com> writes:

The same comment to the commit title applies here.

> .... Note that we do not have to
> inspect individual bits in the result bitmap, since we know that the
> first N (where N is the number of objects in the bitmap's pack/MIDX)
> bits correspond to objects which packed by definition.

;-)

Very nice.  Since we are omitting any object that appears in some
packfile, this produces an expected result even when some of these
objects also appear in loose form.

> +test_expect_success 'bitmap traversal with --unpacked' '
> +	git repack -adb &&
> +	test_commit unpacked &&
> +
> +	git rev-list --objects --no-object-names unpacked^.. >expect.raw &&
> +	sort expect.raw >expect &&
> +
> +	git rev-list --use-bitmap-index --objects --all --unpacked >actual.raw &&
> +	sort actual.raw >actual &&
> +
> +	test_cmp expect actual
> +'

OK.

Re: [PATCH 2/2] pack-bitmap: drop --unpacked non-commit objects from results

[Jeff King]

On Mon, Nov 06, 2023 at 05:56:33PM -0500, Taylor Blau wrote:

> Before returning a bitmap containing the result of the traversal back to
> the caller, drop any bits from the extended index which appear in one or
> more packs. This implements the correct behavior for rev-list operations
> which use the bitmap index to compute their result.

Nice. I was very happy to see the extra test for "rev-list --disk-usage"
to demonstrate this. The same should apply for "pack-objects --unpacked
--use-bitmap-index" (though in practice I don't think we'd do that, as
"--unpacked" implies on-disk repacking, which we do not generally use
with bitmaps).

-Peff

Re: [PATCH 0/2] revision: exclude all packed objects with `--unpacked`

[Junio C Hamano]

Taylor Blau <me@ttaylorr.com> writes:

> While working on my longer series to enable verbatim pack reuse across
> multiple packs[^1], I noticed a couple of oddities with the `--unpacked`
> rev-walk flag.
>
> While it does exclude packed commits, it does not exclude (all) packed
> trees/blobs/annotated tags. This problem exists in the pack-bitmap
> machinery, too, which will over-count queries like:
>
>     $ git rev-list --use-bitmap-index --all --unpacked --objects
>
> , etc.
>
> The fix is relatively straightforward, split across two patches that
> Peff and I worked on together earlier today.
>
> This is technically a backwards-incompatible change, but the existing
> behavior is broken and does not match the documented behavior, so I
> think in this case we are OK to change --unpacked to faithfully
> implement its documentation.

Yeah, it does sound like a straight bugfix to me.

>
> [^1]: Which, I'm very excited to say, is working :-).
>
> Taylor Blau (2):
>   list-objects: drop --unpacked non-commit objects from results
>   pack-bitmap: drop --unpacked non-commit objects from results
>
>  list-objects.c                     |  3 +++
>  pack-bitmap.c                      | 27 +++++++++++++++++++++++++++
>  t/t6000-rev-list-misc.sh           | 13 +++++++++++++
>  t/t6113-rev-list-bitmap-filters.sh | 13 +++++++++++++
>  t/t6115-rev-list-du.sh             |  7 +++++++
>  5 files changed, 63 insertions(+)
>
>
> base-commit: bc5204569f7db44d22477485afd52ea410d83743

Re: [PATCH 0/2] revision: exclude all packed objects with `--unpacked`

[Jeff King]

On Mon, Nov 06, 2023 at 05:56:27PM -0500, Taylor Blau wrote:

> While working on my longer series to enable verbatim pack reuse across
> multiple packs[^1], I noticed a couple of oddities with the `--unpacked`
> rev-walk flag.
> 
> While it does exclude packed commits, it does not exclude (all) packed
> trees/blobs/annotated tags. This problem exists in the pack-bitmap
> machinery, too, which will over-count queries like:
> 
>     $ git rev-list --use-bitmap-index --all --unpacked --objects
> 
> , etc.
> 
> The fix is relatively straightforward, split across two patches that
> Peff and I worked on together earlier today.

I'm not sure my review is worth anything, but this looks good to me. ;)
I do think it might be worth tightening up the docs as Junio suggested,
but I would be fine to see that as a patch on top.

-Peff

Re: [PATCH 0/2] revision: exclude all packed objects with `--unpacked`

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1047 bytes --]

On Mon, Nov 06, 2023 at 11:02:35PM -0500, Jeff King wrote:
> On Mon, Nov 06, 2023 at 05:56:27PM -0500, Taylor Blau wrote:
> 
> > While working on my longer series to enable verbatim pack reuse across
> > multiple packs[^1], I noticed a couple of oddities with the `--unpacked`
> > rev-walk flag.
> > 
> > While it does exclude packed commits, it does not exclude (all) packed
> > trees/blobs/annotated tags. This problem exists in the pack-bitmap
> > machinery, too, which will over-count queries like:
> > 
> >     $ git rev-list --use-bitmap-index --all --unpacked --objects
> > 
> > , etc.
> > 
> > The fix is relatively straightforward, split across two patches that
> > Peff and I worked on together earlier today.
> 
> I'm not sure my review is worth anything, but this looks good to me. ;)
> I do think it might be worth tightening up the docs as Junio suggested,
> but I would be fine to see that as a patch on top.
> 
> -Peff

I also read through the patches and agree, this looks good to me.
Thanks!

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]