Re: [PATCH v2 2/2] connected: add incremental connectivity check via rev-list

On Mon, 5 Oct 2026 at 10:00, Patrick Steinhardt [off-list ref] wrote:

... whereas in the new world you propose to skip marking trees/blobs as
uninteresting. Instead, the idea is to compare the trees/blobs of the
old tips directly with the trees/blobs of the new tips and only verify
those parts that have changed between the two?

Yes, kind of, but I am not sure what you meant by old tips and
new tips -- to be clear (and I should also write this more
clearly) we only verify the commit-trees for all incoming
commits, and the comparisons are always between a commit and
its parents (i.e. X and X^1, X^2, ...).  The key insight that
makes the approach work is that we can skip any object we have
seen from a trusted base (e.g. a commit that was already
reachable before).

This can of course cause us to verify significantly more objects in some
scenarios. But it does have the consequence that we scale with the
number of changes, not with the number of preexisting objects in the
repository. And that's something I'd really appreciate, because marking
reachable objects as uninteresting is extremely expensive.

Yes, that's the goal in the happy case -- and I would argue it
does not produce significantly more work in the worst case,
due to caching and remembering everything we've seen so far
(only more work within a 2x bound or so).

One thing I wonder though... does this help with the scenario where we
have tons of references or do we still end up passing "--not --all"? I
have seen many times that parsing the refs by itself is dominating the
time of the connectivity check quite significantly. So ideally, I'd like
to have a solution that also catches this case. Your benchmarks do not
cover that scenario though.

Yes, the problem of scaling out with number of refs is a real
problem (and often a bigger one) and I want to address that
too, but it's out of scope for this particular patch series.

May I suggest splitting up this patch in the following way?

  - One commit that introduces the new option, but for now only accepts
    "full" as the algorithm.

  - One commit that introduces the benchmark.

  - One commit that introduces the new flag for git-rev-list(1).

  - One commit that then introduces the new strategy.

That may make it a bit easier to focus on the actual change.

Yes, I can definitely do that.  Initially I was thinking that
since it was basically only additions no obvious good in-between
state, it wouldn't help much to split it up, but I think you
convinced me there.

quoted

+The incremental mode, selected by
+`transfer.connectivityCheck=incremental`, avoids traversing the
+full tree walk of the boundary commits.  Instead, it verifies
+each incoming commit's tree against the already-trusted trees of
+its parents.

Can we define "parents" here? Specifically, I wonder how you define
"parent" in the case where you perform a force push or when creating a
new reference. Is it the parent of the first new commit? Is it the old
state of the ref, if it even exists?

Parent is always defined relative to the commit we are
currently verifying.  For example, a push may come with
3 commits (let's call the tip T), and then we do the
following comparisons:

    T   vs T^1, T^2
    T~1 vs T~1^1, T~1^2
    T~2 vs T~2^1, T~2^2

T~2^1 and T~2^2 must already exist and be reachable and
so we can trust them to be connected.  And since this is
relying on memoizing already seen results, it's important
to run the checks bottom-up (reverse topological order).

I will see if I can make this more obvious in the commit
message or documentation somehow.

quoted

+Trust model
+~~~~~~~~~~~
+
+A tree is trusted when its transitive object closure is known to
+be connected.  Trees reachable from commits on the
+already-connected side of the boundary are therefore trusted.

Where the "already-connected side of the boundary" is anything reachable
via a reference.

Yes, precisely.

quoted

+Incoming commits are processed with ancestors before descendants.
+Once an incoming commit's tree has been verified, it is trusted
+and can be used as a comparison base for later descendants.
+
+This gives an inductive correctness argument: every parent of the
+commit currently being verified is either already connected or is
+an earlier incoming commit whose tree has already been verified.

Right. The big question to me still is how you identify
already-connected trees without having to read all references.

That part works just as before -- rev-list finds the
already-connected commits implicitly with the --not --all query.
It actually finds all the new commits, but we can deduce the
boundary from there (and the pre-existing rev-list code also does
that).

quoted

+Worked example

Worked?

Hm, I suppose I could just use the phrase "Example" here instead.
Will change.

[snip]

quoted

diff --git a/tree-verify.c b/tree-verify.c
new file mode 100644
index 0000000000..5c11c2251a
--- /dev/null
+++ b/tree-verify.c

@@ -0,0 +1,316 @@

[snip]

quoted

+static void verify_commit_tree(struct repository *repo,
+                            struct commit *commit,
+                            struct verify_state *vs)
+{
+     struct oid_array base_trees = OID_ARRAY_INIT;
+     struct commit_list *p;
+
+     /*
+      * Parent trees are trusted: boundary parents are already
+      * connected, and earlier incoming parents were verified
+      * first due to the topological processing order.
+      */

I feel like I still miss where exactly you establish the trust boundary
between preexisting fully-connected commits and new commits.

This is the same as before -- git rev-list produces the trust
boundary based on reachability.  I think the only new thing here
is the inductive leap.  Once we have verified a commit just above
the trust boundary, that itself becomes a new trust boundary.

quoted

+     if (commit_list_count(*commits) < nr_before)
+             die(_("cycle detected in incoming commit graph"));

I don't think we should just die, should we? That may not interact well
with git-receive-pack(1) and others that expect a broken connectivity
check to bubble up errors so that they can properly report those to the
client and clean up their local state.

This is one of the advantages of running within a sub-process --
we can safely die without breaking things -- and this is in fact
how the existing rev-list based implementation work, it will also
die with an error message / return code that the parent process
picks up.

My original implementation tried to do it all within a single
process but it became painful because a lot of the internal
machinery did not have non-fatal variants.

That said, I think long term it would be good to rework it
into a single process and have the right infrastructure in place
to avoid dying.

Thanks,
Kristofer