git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Patrick Steinhardt <ps@pks.im>
Date
Oct 5, 2026, 08:00 UTC
Message-ID
<asNZD7AOC6QL9q1d@pks.im>
In-Reply-To
<6ad528f4bb42a960910eb4fe917a3766fa55d598.1790600552.git.gitgitgadget@gmail.com>
On Mon, Sep 28, 2026 at 01:02:32PM +0000, Kristofer Karlsson via GitGitGadget wrote:
Show 11 quoted lines
> From: Kristofer Karlsson <krka@spotify.com>
> 
> The full connectivity check uses rev-list to find commits
> reachable from the incoming tips but not from the
> already-connected side, then walks their object closure.  Commit
> traversal stops at the connectivity boundary, but trees and blobs
> reachable from that boundary still need to be walked so they can
> be marked uninteresting, allocating a struct object for each one.
> On repositories where the boundary commits have large trees, the
> connectivity check for small incoming changes visits and tracks
> more objects than needed.

Okay. In the old world we basically mark evertyhing as uninteresting, including trees and blobs, ...

Show 10 quoted lines
> Add an alternative connectivity check that verifies incoming
> commits incrementally against their parents.
> 
> The verifier processes incoming commits with ancestors first and
> compares each new tree against its trusted parent trees.  Entries
> already seen on the trusted side are skipped by OID, so unchanged
> subtrees need not remain at the same path to be recognized.
> Changed subtrees are recursively compared against same-path parent
> subtrees, and new subtrees without a comparison base are verified
> from scratch.

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

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.

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.

Show 29 quoted lines
> Incremental uses substantially less memory when it can prune
> most of the boundary tree walk.  In the long-history case the
> two modes visit similar object sets and memory converges.
> 
> The regression cases in the CPU benchmarks are in wall-clock
> time rather than memory, primarily from scanning some trees
> more than once.
> 
> Signed-off-by: Kristofer Karlsson <krka@spotify.com>
> ---
>  Documentation/config/transfer.adoc            |  20 +
>  Documentation/rev-list-options.adoc           |   6 +
>  .../technical/connectivity-check.adoc         | 134 ++++
>  Makefile                                      |   1 +
>  builtin/rev-list.c                            |  19 +
>  connected.c                                   |  24 +
>  meson.build                                   |   1 +
>  t/meson.build                                 |   1 +
>  ...enerate-repo-p5412-connectivity-check.perl |  44 ++
>  t/perf/p5412-connectivity-check.sh            |  92 +++
>  t/t5412-connectivity-check.sh                 | 680 ++++++++++++++++++
>  tree-verify.c                                 | 316 ++++++++
>  tree-verify.h                                 |  15 +
>  13 files changed, 1353 insertions(+)
>  create mode 100644 t/perf/generate-repo-p5412-connectivity-check.perl
>  create mode 100755 t/perf/p5412-connectivity-check.sh
>  create mode 100755 t/t5412-connectivity-check.sh
>  create mode 100644 tree-verify.c
>  create mode 100644 tree-verify.h
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.
Show 17 quoted lines
> diff --git a/Documentation/technical/connectivity-check.adoc b/Documentation/technical/connectivity-check.adoc
> index d20bff6af6..0a8f370546 100644
> --- a/Documentation/technical/connectivity-check.adoc
> +++ b/Documentation/technical/connectivity-check.adoc
> @@ -107,3 +107,137 @@ When a new reference points to a non-commit object, such as a
>  tag, tree, or blob, that object is not part of the commit walk.
>  These non-commit tips are handled by the subsequent object
>  traversal.
> +
> +Incremental connectivity check
> +------------------------------
> +
> +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?

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

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

> +Worked example
Worked?
[snip]
Show 6 quoted lines
> 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]
Show 12 quoted lines
> +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.

Show 46 quoted lines
> +	for (p = commit->parents; p; p = p->next) {
> +		const struct object_id *tree_oid;
> +		parse_commit_or_die(p->item);
> +		tree_oid = get_commit_tree_oid(p->item);
> +		if (!tree_oid)
> +			die(_("unable to load root tree for commit %s"),
> +			    oid_to_hex(&p->item->object.oid));
> +		tree_map_add(vs->trees, tree_oid, TREE_TRUSTED);
> +		oid_array_append(&base_trees, tree_oid);
> +	}
> +
> +	if (!get_commit_tree_oid(commit))
> +		die(_("unable to load root tree for commit %s"),
> +		    oid_to_hex(&commit->object.oid));
> +	verify_tree(repo, get_commit_tree_oid(commit),
> +		    &base_trees, vs, 0);
> +	oid_array_clear(&base_trees);
> +}
> +
> +void verify_commits_incremental(struct repository *repo,
> +				struct commit_list **commits,
> +				int exclude_promisor_objects)
> +{
> +	struct verify_state vs = { 0 };
> +	struct commit_list *iter;
> +	unsigned nr_before;
> +
> +	if (repo->fetch_if_missing)
> +		BUG("verify_commits_incremental must not be called "
> +		    "with fetch_if_missing set");
> +
> +	vs.trees = kh_init_oid_tree();
> +	vs.exclude_promisor_objects = exclude_promisor_objects;
> +
> +	/*
> +	 * Ancestors must be verified before descendants so that parent
> +	 * trees can be trusted without re-verification.  Sort explicitly
> +	 * rather than relying on the caller's ordering.
> +	 *
> +	 * sort_in_topological_order() silently drops cycle members,
> +	 * so explicitly check if the size has changed.
> +	 */
> +	nr_before = commit_list_count(*commits);
> +	sort_in_topological_order(commits, REV_SORT_IN_GRAPH_ORDER);
> +	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.

> +	*commits = commit_list_reverse(*commits);
> +
> +	for (iter = *commits; iter; iter = iter->next)
> +		verify_commit_tree(repo, iter->item, &vs);
Show 7 quoted lines
> +	kh_destroy_oid_tree(vs.trees);
> +	oidset_clear(&vs.trusted_blobs);
> +	trace2_data_intmax("connectivity", repo,
> +			   "trees_loaded", vs.trees_loaded);
> +	trace2_data_intmax("connectivity", repo,
> +			   "blobs_checked", vs.blobs_checked);
> +}
Patrick
Previous: Kristofer Karlsson via GitGitGadgetNext: Kristofer Karlsson
Message 15 of 18 in “connected: add incremental connectivity check”
  1. 0/2 connected: add incremental connectivity checkKristofer Karlsson via GitGitGadget, Sep 14, 2026
  2. 1/2 Documentation: describe connectivity checkingKristofer Karlsson via GitGitGadget, Sep 14, 2026
  3. 2/2 connected: add incremental connectivity check via rev-listKristofer Karlsson via GitGitGadget, Sep 14, 2026
  4. Junio C HamanoSep 14, 2026
  5. Kristofer KarlssonSep 14, 2026
  6. Junio C HamanoSep 14, 2026
  7. 0/2 connected: add incremental connectivity checkKristofer Karlsson via GitGitGadget, Sep 28, 2026
  8. 1/2 Documentation: describe connectivity checkingKristofer Karlsson via GitGitGadget, Sep 28, 2026
  9. Patrick SteinhardtOct 5, 2026
  10. Junio C HamanoOct 5, 2026
  11. Patrick SteinhardtOct 6, 2026
  12. Kristofer KarlssonOct 6, 2026
  13. Kristofer KarlssonOct 6, 2026
  14. 2/2 connected: add incremental connectivity check via rev-listKristofer Karlsson via GitGitGadget, Sep 28, 2026
  15. Patrick SteinhardtOct 5, 2026
  16. Kristofer KarlssonOct 6, 2026
  17. Patrick SteinhardtOct 6, 2026
  18. Kristofer KarlssonOct 6, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.