[PATCH v3 2/2] fetch: write commit-graph using updated refs only

["Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>]

From: Kristofer Karlsson <krka@spotify.com>

When fetch.writeCommitGraph was introduced in 50f26bd035 (fetch: add
fetch.writeCommitGraph config setting, 2019-09-02), the stated goal
was to stay updated with the latest commits after fetching new
objects.  The implementation used write_commit_graph_reachable()
because it was the only API available, but two things have changed
since then:

 1. write_commit_graph() was added, and it accepts an explicit set of
    commits as seeds, enabling more targeted commit-graph updates.

 2. The ref-scanning callback add_ref_to_set() became more expensive
    in 630cd5194e (commit-graph.c: peel refs in 'add_ref_to_set',
    2020-07-22) when it started to validate the refs against the odb
    for correctness.  On a repository with many refs, this makes the
    full reachable scan unnecessarily costly for a targeted fetch.

Optimize the commit-graph write by using only the newly updated refs
as seeds instead of scanning all refs after every fetch.  To keep
this change small, skip the optimization for multi-remote fetches
(since that would require propagating the set of refs across process
boundaries).

This relies on the commit-graph write being additive, keeping the
commits that are already in the graph.  fetch already operates in
this mode (COMMIT_GRAPH_WRITE_SPLIT) and now that becomes
required for correctness.  Without that mode, the write would
replace the commit-graph and lose other commits.

After fetch_one() returns, call prepare_commit_graph() (which is
made non-static by this commit) to determine the graph-write mode:

 - If no commit-graph exists yet, fall back to the full reachable
   scan so the first graph creation covers all refs.

 - If a commit-graph exists and the fetch updated at least one ref,
   write incrementally using only the new refs as seeds.

 - If a commit-graph exists but the fetch is a no-op, skip the
   commit-graph write entirely.

 - For the multi-remote path (fetch --all), where child processes
   do the actual fetching, fall back to the full reachable scan.

Full commit-graph coverage of all refs remains the responsibility
of "git maintenance", "git gc" and "git commit-graph write".
Regular Git operations may trigger "git maintenance run --auto",
which periodically rebuilds the commit-graph from all reachable
refs.

The effect was measured on a synthetic setup: git.git with 200K
extra packed refs (~206K total), a local file:// remote, an existing
split commit-graph and a warm page cache.  The times below are the
median of 9 runs of the trace2 region fetch/write-commit-graph:

    scenario          before    after
    no-op fetch       380 ms    (skipped)
    1 ref updated     357 ms    9.3 ms
    10 refs updated   359 ms    8.9 ms

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 builtin/fetch.c          | 69 ++++++++++++++++++++++++++++++++++------
 commit-graph.c           |  2 +-
 commit-graph.h           |  1 +
 t/t5510-fetch.sh         | 59 ++++++++++++++++++++++++++++++++++
 t/t5537-fetch-shallow.sh | 22 +++++++++++++
 5 files changed, 143 insertions(+), 10 deletions(-)

diff --git a/builtin/fetch.c b/builtin/fetch.c
index 533fdfe7d8..d73eca77aa 100644
--- a/builtin/fetch.c
+++ b/builtin/fetch.c
@@ -1903,10 +1903,34 @@ out:
 	return retcode;
 }
 
+static void collect_updated_tips(struct oidset *tips, struct ref *ref_map)
+{
+	struct ref *rm;
+	for (rm = ref_map; rm; rm = rm->next) {
+		struct commit *commit;
+		/*
+		 * Shallow-rejected refs are not stored and their history
+		 * is incomplete, so skip them.
+		 */
+		if (rm->status == REF_STATUS_REJECT_SHALLOW)
+			continue;
+		if (is_null_oid(&rm->old_oid))
+			continue;
+		if (rm->peer_ref &&
+		    oideq(&rm->old_oid, &rm->peer_ref->old_oid))
+			continue;
+		commit = lookup_commit_reference_gently(the_repository,
+							&rm->old_oid, 1);
+		if (commit)
+			oidset_insert(tips, &commit->object.oid);
+	}
+}
+
 static int do_fetch(struct transport *transport,
 		    struct refspec *rs,
 		    const struct fetch_config *config,
-		    struct list_objects_filter_options *filter_options)
+		    struct list_objects_filter_options *filter_options,
+		    struct oidset *updated_tips)
 {
 	struct ref_transaction *transaction = NULL;
 	struct ref *ref_map = NULL;
@@ -2111,6 +2135,8 @@ static int do_fetch(struct transport *transport,
 
 	commit_fetch_head(&fetch_head);
 
+	collect_updated_tips(updated_tips, ref_map);
+
 	if (set_upstream) {
 		struct branch *branch = branch_get("HEAD");
 		struct ref *rm;
@@ -2427,7 +2453,8 @@ static inline void fetch_one_setup_partial(struct remote *remote,
 static int fetch_one(struct remote *remote, int argc, const char **argv,
 		     int prune_tags_ok, int use_stdin_refspecs,
 		     const struct fetch_config *config,
-		     struct list_objects_filter_options *filter_options)
+		     struct list_objects_filter_options *filter_options,
+		     struct oidset *updated_tips)
 {
 	struct refspec rs = REFSPEC_INIT_FETCH(the_hash_algo);
 	int i;
@@ -2494,7 +2521,8 @@ static int fetch_one(struct remote *remote, int argc, const char **argv,
 	sigchain_push_common(unlock_pack_on_signal);
 	atexit(unlock_pack_atexit);
 	sigchain_push(SIGPIPE, SIG_IGN);
-	exit_code = do_fetch(gtransport, &rs, config, filter_options);
+	exit_code = do_fetch(gtransport, &rs, config, filter_options,
+			     updated_tips);
 	sigchain_pop(SIGPIPE);
 	refspec_clear(&rs);
 	transport_disconnect(gtransport);
@@ -2535,6 +2563,12 @@ int cmd_fetch(int argc,
 	int negotiate_only = 0;
 	int porcelain = 0;
 	int i;
+	enum {
+		GRAPH_WRITE_REACHABLE,
+		GRAPH_WRITE_TIPS,
+		GRAPH_WRITE_SKIP,
+	} graph_write_mode = GRAPH_WRITE_REACHABLE;
+	struct oidset updated_tips = OIDSET_INIT;
 
 	struct option builtin_fetch_options[] = {
 		OPT__VERBOSITY(&verbosity),
@@ -2822,7 +2856,13 @@ int cmd_fetch(int argc,
 		}
 		trace2_region_enter("fetch", "fetch-one", the_repository);
 		result = fetch_one(remote, argc, argv, prune_tags_ok, stdin_refspecs,
-				   &config, &filter_options);
+				   &config, &filter_options, &updated_tips);
+		if (prepare_commit_graph(the_repository)) {
+			if (oidset_size(&updated_tips))
+				graph_write_mode = GRAPH_WRITE_TIPS;
+			else
+				graph_write_mode = GRAPH_WRITE_SKIP;
+		}
 		trace2_region_leave("fetch", "fetch-one", the_repository);
 	} else {
 		int max_children = max_jobs;
@@ -2899,11 +2939,21 @@ int cmd_fetch(int argc,
 		if (progress)
 			commit_graph_flags |= COMMIT_GRAPH_WRITE_PROGRESS;
 
-		trace2_region_enter("fetch", "write-commit-graph", the_repository);
-		write_commit_graph_reachable(the_repository->objects->sources,
-					     commit_graph_flags,
-					     NULL);
-		trace2_region_leave("fetch", "write-commit-graph", the_repository);
+		if (graph_write_mode != GRAPH_WRITE_SKIP) {
+			trace2_region_enter("fetch", "write-commit-graph",
+					    the_repository);
+			if (graph_write_mode == GRAPH_WRITE_TIPS)
+				write_commit_graph(
+					the_repository->objects->sources,
+					NULL, &updated_tips,
+					commit_graph_flags, NULL);
+			else
+				write_commit_graph_reachable(
+					the_repository->objects->sources,
+					commit_graph_flags, NULL);
+			trace2_region_leave("fetch", "write-commit-graph",
+					    the_repository);
+		}
 	}
 
 	if (enable_auto_gc) {
@@ -2927,6 +2977,7 @@ int cmd_fetch(int argc,
 	}
 
  cleanup:
+	oidset_clear(&updated_tips);
 	string_list_clear(&list, 0);
 	list_objects_filter_release(&filter_options);
 	return result;
diff --git a/commit-graph.c b/commit-graph.c
index 983c11ce85..d042752ff4 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -733,7 +733,7 @@ struct commit_graph *read_commit_graph_one(struct odb_source *source)
  * On the first invocation, this function attempts to load the commit
  * graph if the repository is configured to have one.
  */
-static struct commit_graph *prepare_commit_graph(struct repository *r)
+struct commit_graph *prepare_commit_graph(struct repository *r)
 {
 	struct odb_source *source;
 
diff --git a/commit-graph.h b/commit-graph.h
index 13ca4ff010..7e48b0ccc0 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -31,6 +31,7 @@ struct string_list;
 
 char *get_commit_graph_filename(struct odb_source *source);
 char *get_commit_graph_chain_filename(struct odb_source *source);
+struct commit_graph *prepare_commit_graph(struct repository *r);
 int open_commit_graph(const char *graph_file, int *fd, struct stat *st);
 int open_commit_graph_chain(const char *chain_file, int *fd, struct stat *st,
 			    const struct git_hash_algo *hash_algo);
diff --git a/t/t5510-fetch.sh b/t/t5510-fetch.sh
index a8d38d9176..72dcb7fd43 100755
--- a/t/t5510-fetch.sh
+++ b/t/t5510-fetch.sh
@@ -1087,6 +1087,65 @@ test_expect_success 'fetch.writeCommitGraph' '
 	)
 '
 
+test_expect_success 'fetch.writeCommitGraph adds fetched commits incrementally' '
+	git init incremental-source &&
+	test_commit -C incremental-source one &&
+	git clone incremental-source incremental-dest &&
+	test_commit -C incremental-dest local &&
+	git -C incremental-dest commit-graph write --reachable --split &&
+	test_commit -C incremental-source two &&
+	test_commit -C incremental-source three &&
+	(
+		cd incremental-dest &&
+		git -c fetch.writeCommitGraph=true fetch origin &&
+		test-tool read-graph commit-info three two local
+	)
+'
+
+test_expect_success 'fetch.writeCommitGraph does not add unrelated commits' '
+	git init unrelated-source &&
+	test_commit -C unrelated-source initial &&
+	git clone unrelated-source unrelated-dest &&
+	git -C unrelated-dest commit-graph write --reachable --split &&
+	test_commit -C unrelated-source fetched &&
+	(
+		cd unrelated-dest &&
+		test_env GIT_TEST_COMMIT_GRAPH=0 test_commit local-only &&
+		git -c fetch.writeCommitGraph=true fetch origin &&
+		test-tool read-graph commit-info fetched &&
+		test_expect_code 1 \
+			test-tool read-graph commit-info local-only 2>/dev/null
+	)
+'
+
+test_expect_success 'fetch.writeCommitGraph skips write on no-op fetch' '
+	git init noop-source &&
+	test_commit -C noop-source one &&
+	git clone noop-source noop-dest &&
+	git -C noop-dest commit-graph write --reachable --split &&
+	(
+		cd noop-dest &&
+		GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
+			git -c fetch.writeCommitGraph=true fetch origin &&
+		test_region ! fetch write-commit-graph trace2.txt
+	)
+'
+
+test_expect_success 'fetch.writeCommitGraph falls back to reachable scan without existing graph' '
+	git init first-graph-source &&
+	test_commit -C first-graph-source base &&
+	git clone first-graph-source first-graph-dest &&
+	test_commit -C first-graph-source fetched &&
+	(
+		cd first-graph-dest &&
+		test_commit local &&
+		rm -rf .git/objects/info/commit-graphs &&
+		rm -f .git/objects/info/commit-graph &&
+		git -c fetch.writeCommitGraph=true fetch origin &&
+		test-tool read-graph commit-info fetched local base
+	)
+'
+
 test_expect_success 'fetch.writeCommitGraph with submodules' '
 	test_config_global protocol.file.allow always &&
 	git clone dups super &&
diff --git a/t/t5537-fetch-shallow.sh b/t/t5537-fetch-shallow.sh
index f323ceebd2..16bfaba0f0 100755
--- a/t/t5537-fetch-shallow.sh
+++ b/t/t5537-fetch-shallow.sh
@@ -135,6 +135,28 @@ test_expect_success 'fetch that requires changes in .git/shallow is filtered' '
 	)
 '
 
+test_expect_success 'fetch.writeCommitGraph skips refs that require changes in .git/shallow' '
+	git clone --no-local --depth=2 .git shallow-graph &&
+	git -C shallow-graph checkout --orphan no-shallow &&
+	test_commit -C shallow-graph --no-tag no-shallow &&
+	git init notshallow-graph &&
+	git -C notshallow-graph -c fetch.writeCommitGraph=true \
+		fetch ../shallow-graph/.git "refs/heads/*:refs/remotes/shallow/*" &&
+	test_commit -C shallow-graph --no-tag no-shallow-2 &&
+	rejected=$(git -C shallow-graph rev-parse main) &&
+	(
+		cd notshallow-graph &&
+		git -c fetch.writeCommitGraph=true \
+			fetch ../shallow-graph/.git "refs/heads/*:refs/remotes/shallow/*" &&
+		git for-each-ref --format="%(refname)" >actual.refs &&
+		echo refs/remotes/shallow/no-shallow >expect.refs &&
+		test_cmp expect.refs actual.refs &&
+		test-tool read-graph commit-info shallow/no-shallow &&
+		test_expect_code 1 \
+			test-tool read-graph commit-info $rejected 2>/dev/null
+	)
+'
+
 test_expect_success 'fetch --update-shallow' '
 	(
 	cd shallow &&
-- 
gitgitgadget