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

From: Kristofer Karlsson <krka@spotify.com>
Date: Oct 6, 2026, 10:37 UTC
Message-ID: <CAL71e4PFpMPoSxFdnscRFiMB3ozudr64TjeQc8VKcO_M_MfJ=w@mail.gmail.com>
In-Reply-To: <asNZD7AOC6QL9q1d@pks.im>

On Mon, 5 Oct 2026 at 10:00, Patrick Steinhardt <ps@pks.im> wrote:

Show 5 quoted lines

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

Show 6 quoted lines

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

Show 6 quoted lines

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

Show 12 quoted lines

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

Show 10 quoted lines

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

Show 9 quoted lines

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

Show 10 quoted lines

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

> > +Worked example
>
> Worked?

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

Show 24 quoted lines

>
> [snip]
> > 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]
> > +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.

Show 7 quoted lines

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