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

Re: [PATCH v3 4/4] connected: add incremental connectivity check via rev-list

From
Patrick Steinhardt <ps@pks.im>
Date
Oct 15, 2026, 06:55 UTC
Message-ID
<atB48HLgZr3ssOfx@pks.im>
In-Reply-To
<efaada0b6a8ffdb4d1c01d7f34a0d6596a99c149.1791806877.git.gitgitgadget@gmail.com>
On Mon, Oct 12, 2026 at 12:07:57PM +0000, Kristofer Karlsson via GitGitGadget wrote:
> From: Kristofer Karlsson <krka@spotify.com>
[snip]
Show 12 quoted lines
> Scaling tree size (10 incoming commits, 10 files/commit):
> 
>     files    full  incr.  full/incr
>       5K    0.01s  0.01s    1.0x
>      50K    0.04s  0.01s    4.0x
>     200K    0.15s  0.01s   15.0x
>     800K    0.61s  0.03s   20.3x
> 
> The full mode must walk the trees of boundary commits, which
> grows with overall tree size.  Incremental still scans the
> root trees, but avoids descending into unchanged subtrees,
> so it grows much more slowly with repository size.
Okay, so this is getting better the larger the trees.
Show 15 quoted lines
> Scaling incoming commit count (200K files, 10 files/commit):
> 
>     commits    full  incr.  full/incr
>           1    0.14s  0.01s   14.0x
>          10    0.15s  0.01s   15.0x
>         100    0.19s  0.05s    3.8x
>         500    0.32s  0.27s    1.2x
>        3000    1.23s  1.52s    0.8x
>        5000    1.88s  2.43s    0.8x
>       10000    3.72s  5.36s    0.7x
> 
> With many commits the per-commit overhead of scanning both
> the new and parent root trees accumulates and incremental
> becomes slower.  Breakeven is between 500 and 3000 commits
> and the ratio stabilizes near 0.7x for this fixture.

And worse the more commits we have. So the new mode is only really applicable in scenarios where you know what your typical workload looks like. The big question is of course whether we can have the best of both worlds, where Git knows to switch between the two modes once it crosses the threshold.

Show 14 quoted lines
> diff --git a/Documentation/technical/connectivity-check.adoc b/Documentation/technical/connectivity-check.adoc
> index abef02debd..a1d2e9709c 100644
> --- a/Documentation/technical/connectivity-check.adoc
> +++ b/Documentation/technical/connectivity-check.adoc
> +Algorithm
> +~~~~~~~~~
> +
> +At a high level:
> +
> +    verify(commits):
> +        sort topologically (ancestors first)
> +        for each commit:
> +            mark parent root trees as trusted
> +            verify_tree(commit.tree, parent root trees)

So based on this, `verify()` already knows which commits it will be checking for connectivity. So wouldn't it be possible to fall back to the original algortihm here in case we see more than N commits?

Show 28 quoted lines
> diff --git a/tree-verify.c b/tree-verify.c
> new file mode 100644
> index 0000000000..b381a50102
> --- /dev/null
> +++ b/tree-verify.c
> @@ -0,0 +1,316 @@
> +#include "git-compat-util.h"
> +#include "commit.h"
> +#include "gettext.h"
> +#include "hex.h"
> +#include "khash.h"
> +#include "object.h"
> +#include "odb.h"
> +#include "oid-array.h"
> +#include "oidset.h"
> +#include "tree.h"
> +#include "tree-walk.h"
> +#include "tree-verify.h"
> +#include "packfile.h"
> +#include "trace2.h"
> +
> +enum tree_state {
> +	TREE_UNTRUSTED = 0,
> +	TREE_TRUSTED   = 1,
> +	TREE_EXPANDED  = 2,
> +};
> +
> +KHASH_INIT(oid_tree, struct object_id, unsigned char, 1,

The values are `enum tree_state`s, right? Why don't we use that type here?

Show 32 quoted lines
> +	   oidhash_by_value, oideq_by_value)
> +
> +static enum tree_state tree_map_get(kh_oid_tree_t *m,
> +				    const struct object_id *oid)
> +{
> +	khint_t pos = kh_get_oid_tree(m, *oid);
> +	if (pos == kh_end(m))
> +		return TREE_UNTRUSTED;
> +	return kh_val(m, pos);
> +}
> +
> +static void tree_map_add(kh_oid_tree_t *m, const struct object_id *oid,
> +			 enum tree_state state)
> +{
> +	int added;
> +	khint_t pos = kh_put_oid_tree(m, *oid, &added);
> +	if (added)
> +		kh_val(m, pos) = state;
> +	else if (state > kh_val(m, pos))
> +		kh_val(m, pos) = state;
> +}
> +
> +struct work_item {
> +	struct name_entry entry;
> +	struct oid_array parent_trees;
> +};
> +
> +struct verify_state {
> +	kh_oid_tree_t *trees;
> +	struct oidset trusted_blobs;
> +	int trees_loaded;
> +	int blobs_checked;
These probably should be `size_t`.
Show 50 quoted lines
> +	int exclude_promisor_objects;
> +};
> +
> +/*
> + * Merge-walk the work list against one base tree entry, recording
> + * same-path parent subtrees as recursive comparison bases.
> + * Returns the updated work-list cursor.
> + */
> +static size_t collect_subtree_bases(struct work_item *work, size_t nr_work,
> +				    size_t wi, const struct name_entry *entry)
> +{
> +	while (wi < nr_work) {
> +		int cmp = base_name_compare(
> +			work[wi].entry.path, work[wi].entry.pathlen,
> +			work[wi].entry.mode,
> +			entry->path, entry->pathlen,
> +			entry->mode);
> +		if (cmp > 0)
> +			break;
> +		if (cmp < 0) {
> +			wi++;
> +			continue;
> +		}
> +		if (S_ISDIR(work[wi].entry.mode) &&
> +		    S_ISDIR(entry->mode))
> +			oid_array_append(&work[wi].parent_trees,
> +					 &entry->oid);
> +		return wi + 1;
> +	}
> +	return wi;
> +}
> +
> +static void verify_blob(struct repository *repo,
> +			const struct object_id *oid,
> +			struct verify_state *vs)
> +{
> +	int type;
> +
> +	if (oidset_contains(&vs->trusted_blobs, oid))
> +		return;
> +
> +	vs->blobs_checked++;
> +	type = odb_read_object_info(repo->objects, oid, NULL);
> +	if (type == OBJ_BLOB) {
> +		oidset_insert(&vs->trusted_blobs, oid);
> +		return;
> +	}
> +	if (type >= 0)
> +		die(_("object %s is a %s, not a %s"),
> +		    oid_to_hex(oid), type_name(type), "blob");

I'd love not having all these calls to `die()`, as this logic is essentially part of a library, and dying inside a library is a bad smell. We do this everywhere else in Git, too, but we're slowly getting rid of this as part of our libification efforts.

> +	if (vs->exclude_promisor_objects &&
> +	    is_promisor_object(repo, oid))
> +		return;
> +	die(_("missing blob object '%s'"), oid_to_hex(oid));

Maybe the object is missing, but it may just as well be corrupt. So this should probably say "unable to read".

Show 20 quoted lines
> +}
> +
> +static void *read_tree_object(struct object_database *odb,
> +			      const struct object_id *oid,
> +			      size_t *sizep)
> +{
> +	enum object_type type;
> +	void *buf = odb_read_object(odb, oid, &type, sizep);
> +
> +	if (buf && type != OBJ_TREE) {
> +		free(buf);
> +		die(_("object %s is a %s, not a %s"),
> +		    oid_to_hex(oid), type_name(type), "tree");
> +	}
> +	return buf;
> +}
> +
> +static void verify_tree(struct repository *repo,
> +			const struct object_id *new_tree_oid,
> +			const struct oid_array *base_trees,

I think `base_trees` is a bit of a confusing term, as I think those always are the parent's trees, right? Should we maybe name it accordingly?

Show 7 quoted lines
> +			struct verify_state *vs, int depth)
> +{
> +	struct tree_desc desc;
> +	struct name_entry entry;
> +	struct work_item *work = NULL;
> +	size_t nr_work = 0, alloc_work = 0;
> +	int need_subtree_bases = 0;
Nit: this should be a `bool`.
Show 37 quoted lines
> +	size_t i, tree_size;
> +	void *tree_buf;
> +
> +	if (depth > repo->settings.max_allowed_tree_depth)
> +		die(_("exceeded maximum allowed tree depth"));
> +
> +	if (tree_map_get(vs->trees, new_tree_oid) >= TREE_TRUSTED)
> +		return;
> +
> +	tree_buf = read_tree_object(repo->objects, new_tree_oid, &tree_size);
> +	if (!tree_buf) {
> +		if (vs->exclude_promisor_objects &&
> +		    is_promisor_object(repo, new_tree_oid))
> +			return;
> +		die(_("bad tree object %s"),
> +		    oid_to_hex(new_tree_oid));
> +	}
> +
> +	vs->trees_loaded++;
> +	init_tree_desc(&desc, new_tree_oid, tree_buf, tree_size);
> +
> +	while (tree_entry(&desc, &entry)) {
> +		if (S_ISGITLINK(entry.mode))
> +			continue;
> +		if (S_ISDIR(entry.mode)) {
> +			if (tree_map_get(vs->trees, &entry.oid) >= TREE_TRUSTED)
> +				continue;
> +			need_subtree_bases = 1;
> +		} else {
> +			if (oidset_contains(&vs->trusted_blobs, &entry.oid))
> +				continue;
> +		}
> +		ALLOC_GROW(work, nr_work + 1, alloc_work);
> +		memset(&work[nr_work], 0, sizeof(work[nr_work]));
> +		work[nr_work].entry = entry;
> +		nr_work++;
> +	}

Okay, so first we gather all the tree entries that need verification becaues we don't trust them yet.

Show 54 quoted lines
> +
> +	if (!nr_work) {
> +		free(tree_buf);
> +		goto done;
> +	}
> +
> +	for (i = 0; base_trees && i < base_trees->nr; i++) {
> +		const struct object_id *base_oid = &base_trees->oid[i];
> +		int expanded = tree_map_get(vs->trees, base_oid) >= TREE_EXPANDED;
> +		struct tree_desc base_desc;
> +		struct name_entry scan_entry;
> +		size_t wi = 0, base_size;
> +		void *base_buf;
> +
> +		if (expanded && !need_subtree_bases)
> +			continue;
> +
> +		base_buf = read_tree_object(repo->objects, base_oid,
> +					    &base_size);
> +		if (!base_buf) {
> +			if (vs->exclude_promisor_objects &&
> +			    is_promisor_object(repo, base_oid))
> +				continue;
> +			die(_("bad tree object %s"),
> +			    oid_to_hex(base_oid));
> +		}
> +
> +		vs->trees_loaded++;
> +		init_tree_desc(&base_desc, base_oid, base_buf, base_size);
> +
> +		while (tree_entry(&base_desc, &scan_entry)) {
> +			if (S_ISGITLINK(scan_entry.mode))
> +				continue;
> +
> +			if (need_subtree_bases)
> +				wi = collect_subtree_bases(work, nr_work,
> +							   wi, &scan_entry);
> +
> +			if (!expanded) {
> +				if (S_ISDIR(scan_entry.mode))
> +					tree_map_add(vs->trees,
> +						     &scan_entry.oid,
> +						     TREE_TRUSTED);
> +				else
> +					oidset_insert(&vs->trusted_blobs,
> +						      &scan_entry.oid);
> +			}
> +		}
> +
> +		if (!expanded)
> +			tree_map_add(vs->trees, base_oid, TREE_EXPANDED);
> +
> +		free(base_buf);
> +	}

Then we expand all of our parent trees to exand the trust boundary. I think this part is rather non-obvious though, and could really use some code comments to explain what's even going on here.

Show 5 quoted lines
> +	for (i = 0; i < nr_work; i++) {
> +		if (S_ISDIR(work[i].entry.mode))
> +			verify_tree(repo, &work[i].entry.oid,
> +				    &work[i].parent_trees, vs,
> +				    depth + 1);

And here we then recurse. The recursion isn't unbounded, but we may go up to 2048 layers deep here. We already do this recursively in other places, but I do wonder whether we can maybe avoid the recursion and instead use a work queue so that we don't bust the stack.

Show 26 quoted lines
> +		else
> +			verify_blob(repo, &work[i].entry.oid, vs);
> +	}
> +
> +	free(tree_buf);
> +
> +done:
> +	tree_map_add(vs->trees, new_tree_oid, TREE_EXPANDED);
> +	for (i = 0; i < nr_work; i++)
> +		oid_array_clear(&work[i].parent_trees);
> +	free(work);
> +}
> +
> +static void verify_commit_tree(struct repository *repo,
> +			       struct commit *commit,
> +			       struct verify_state *vs)
> +{
> +	struct oid_array base_trees = OID_ARRAY_INIT;
> +	const struct object_id *tree_oid;
> +	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.
> +	 */

Okay. Parents are trusted because we go from oldest to newest in topological order.

> +	for (p = commit->parents; p; p = p->next) {
> +		parse_commit_or_die(p->item);

This part here may die in case the repository is a partial clone with missing commits because we enforce that `fetch_if_missing` is disabled.

Show 6 quoted lines
> +		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);

And we only mark those trees as TRUSTED, not EXPANDED, as we didn't read the trees themselves.

Show 7 quoted lines
> +	}
> +
> +	tree_oid = get_commit_tree_oid(commit);
> +	if (!tree_oid)
> +		die(_("unable to load root tree for commit %s"),
> +		    oid_to_hex(&commit->object.oid));
> +	verify_tree(repo, tree_oid, &base_trees, vs, 0);
And this function here recursively verifies the root tree itself.
Show 43 quoted lines
> +	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"));
> +
> +	*commits = commit_list_reverse(*commits);
> +
> +	for (iter = *commits; iter; iter = iter->next)
> +		verify_commit_tree(repo, iter->item, &vs);
> +
> +	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);
> +}
Thanks!
Patrick
Previous: Kristofer Karlsson via GitGitGadgetNext: Kristofer Karlsson
Message 33 of 60 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
  19. 0/4 connected: add incremental connectivity checkKristofer Karlsson via GitGitGadget, Oct 12, 2026
  20. 1/4 Documentation: describe connectivity checkingKristofer Karlsson via GitGitGadget, Oct 12, 2026
  21. Patrick SteinhardtOct 15, 2026
  22. Kristofer KarlssonOct 15, 2026
  23. 2/4 p5413: add perf tests for connectivity checkKristofer Karlsson via GitGitGadget, Oct 12, 2026
  24. Patrick SteinhardtOct 15, 2026
  25. Kristofer KarlssonOct 15, 2026
  26. 3/4 connected: add transfer.connectivityCheck config and rev-list flagKristofer Karlsson via GitGitGadget, Oct 12, 2026
  27. Junio C HamanoOct 12, 2026
  28. Kristofer KarlssonOct 13, 2026
  29. Junio C HamanoOct 13, 2026
  30. Patrick SteinhardtOct 15, 2026
  31. Kristofer KarlssonOct 15, 2026
  32. 4/4 connected: add incremental connectivity check via rev-listKristofer Karlsson via GitGitGadget, Oct 12, 2026
  33. Patrick SteinhardtOct 15, 2026
  34. Kristofer KarlssonOct 15, 2026
  35. Patrick SteinhardtOct 15, 2026
  36. Kristofer KarlssonOct 16, 2026
  37. Patrick SteinhardtOct 19, 2026
  38. Junio C HamanoOct 12, 2026
  39. Kristofer KarlssonOct 13, 2026
  40. 0/6 connected: add incremental connectivity checkKristofer Karlsson via GitGitGadget, Oct 21, 2026
  41. 1/6 Documentation: describe connectivity checkingKristofer Karlsson via GitGitGadget, Oct 21, 2026
  42. 2/6 p5413: add perf tests for connectivity checkKristofer Karlsson via GitGitGadget, Oct 21, 2026
  43. 3/6 connected: drop dependency on `the_repository`Kristofer Karlsson via GitGitGadget, Oct 21, 2026
  44. 4/6 connected: add transfer.connectivityCheck configKristofer Karlsson via GitGitGadget, Oct 21, 2026
  45. 5/6 connected: add incremental connectivity check via rev-listKristofer Karlsson via GitGitGadget, Oct 21, 2026
  46. Junio C HamanoOct 21, 2026
  47. Kristofer KarlssonOct 22, 2026
  48. Kristofer KarlssonOct 22, 2026
  49. Junio C HamanoOct 22, 2026
  50. Kristofer KarlssonOct 22, 2026
  51. Junio C HamanoOct 23, 2026
  52. 6/6 connected: add "auto" connectivity check modeKristofer Karlsson via GitGitGadget, Oct 21, 2026
  53. 0/6 connected: add incremental connectivity checkKristofer Karlsson via GitGitGadget, Oct 23, 2026
  54. 1/6 Documentation: describe connectivity checkingKristofer Karlsson via GitGitGadget, Oct 23, 2026
  55. 2/6 p5413: add perf tests for connectivity checkKristofer Karlsson via GitGitGadget, Oct 23, 2026
  56. 3/6 connected: drop dependency on `the_repository`Kristofer Karlsson via GitGitGadget, Oct 23, 2026
  57. 4/6 connected: add transfer.connectivityCheck configKristofer Karlsson via GitGitGadget, Oct 23, 2026
  58. 5/6 connected: add incremental connectivity check via rev-listKristofer Karlsson via GitGitGadget, Oct 23, 2026
  59. 6/6 connected: add "auto" connectivity check modeKristofer Karlsson via GitGitGadget, Oct 23, 2026
  60. Junio C HamanoOct 23, 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.