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

[PATCH v3 1/3] builtin/commit-graph.c: support '--split[=<strategy>]'

From
Taylor Blau <me@ttaylorr.com>
Date
Feb 12, 2020, 05:47 UTC
Message-ID
<e1635a0e34de62095e85ee3e42222c8fa2384688.1581486293.git.me@ttaylorr.com>
In-Reply-To
<cover.1581486293.git.me@ttaylorr.com>

With '--split', the commit-graph machinery writes new commits in another incremental commit-graph which is part of the existing chain, and optionally decides to condense the chain into a single commit-graph. This is done to ensure that the asymptotic behavior of looking up a commit in an incremental chain is dominated by the number of incrementals in that chain. It can be controlled by the '--max-commits' and '--size-multiple' options.

On occasion, callers may want to ensure that 'git commit-graph write --split' always writes an incremental, and never spends effort condensing the incremental chain [1]. Previously, this was possible by passing '--size-multiple=0', but this no longer the case following 63020f175f (commit-graph: prefer default size_mult when given zero, 2020-01-02).

Reintroduce a less-magical variant of the above with a new pair of arguments to '--split': '--split=no-merge' and '--split=merge-all'. When '--split=no-merge' is given, the commit-graph machinery will never condense an existing chain and will always write a new incremental. Conversely, if '--split=merge-all' is given, any invocation including it will always condense a chain if one exists. If '--split' is given with no arguments, it behaves as before and defers to '--size-multiple', and so on.

[1]: This might occur when, for example, a server administrator running some program after each push may want to ensure that each job runs proportional in time to the size of the push, and does not "jump" when the commit-graph machinery decides to trigger a merge.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/git-commit-graph.txt | 17 ++++++++++-----
 builtin/commit-graph.c             | 35 ++++++++++++++++++++++++++----
 commit-graph.c                     | 22 ++++++++++++-------
 commit-graph.h                     |  7 ++++++
 t/t5324-split-commit-graph.sh      | 25 +++++++++++++++++++++
 5 files changed, 89 insertions(+), 17 deletions(-)
diff --git a/Documentation/git-commit-graph.txt b/Documentation/git-commit-graph.txt
index 28d1fee505..269c355b0a 100644
--- a/Documentation/git-commit-graph.txt
+++ b/Documentation/git-commit-graph.txt
@@ -57,11 +57,18 @@ or `--stdin-packs`.)
 With the `--append` option, include all commits that are present in the
 existing commit-graph file.
 +
-With the `--split` option, write the commit-graph as a chain of multiple
-commit-graph files stored in `<dir>/info/commit-graphs`. The new commits
-not already in the commit-graph are added in a new "tip" file. This file
-is merged with the existing file if the following merge conditions are
-met:
+With the `--split[=<strategy>]` option, write the commit-graph as a
+chain of multiple commit-graph files stored in
+`<dir>/info/commit-graphs`. Commit-graph layers are merged based on the
+strategy and other splitting options. The new commits not already in the
+commit-graph are added in a new "tip" file. This file is merged with the
+existing file if the following merge conditions are met:
++
+* If `--split=merge-always` is specified, then a merge is always
+conducted, and the remaining options are ignored. Conversely, if
+`--split=no-merge` is specified, a merge is never performed, and the
+remaining options are ignored. A bare `--split` defers to the remaining
+options.
 +
 * If `--size-multiple=<X>` is not specified, let `X` equal 2. If the new
 tip file would have `N` commits and the previous tip has `M` commits and
diff --git a/builtin/commit-graph.c b/builtin/commit-graph.c
index 4a70b33fb5..4d3c1c46c2 100644
--- a/builtin/commit-graph.c
+++ b/builtin/commit-graph.c
@@ -9,7 +9,9 @@
 
 static char const * const builtin_commit_graph_usage[] = {
 	N_("git commit-graph verify [--object-dir <objdir>] [--shallow] [--[no-]progress]"),
-	N_("git commit-graph write [--object-dir <objdir>] [--append|--split] [--reachable|--stdin-packs|--stdin-commits] [--[no-]progress] <split options>"),
+	N_("git commit-graph write [--object-dir <objdir>] [--append] "
+	   "[--split[=<strategy>]] [--reachable|--stdin-packs|--stdin-commits] "
+	   "[--[no-]progress] <split options>"),
 	NULL
 };
 
@@ -19,7 +21,9 @@ static const char * const builtin_commit_graph_verify_usage[] = {
 };
 
 static const char * const builtin_commit_graph_write_usage[] = {
-	N_("git commit-graph write [--object-dir <objdir>] [--append|--split] [--reachable|--stdin-packs|--stdin-commits] [--[no-]progress] <split options>"),
+	N_("git commit-graph write [--object-dir <objdir>] [--append] "
+	   "[--split[=<strategy>]] [--reachable|--stdin-packs|--stdin-commits] "
+	   "[--[no-]progress] <split options>"),
 	NULL
 };
 
@@ -111,6 +115,27 @@ static int graph_verify(int argc, const char **argv)
 extern int read_replace_refs;
 static struct split_commit_graph_opts split_opts;
 
+static int write_option_parse_split(const struct option *opt, const char *arg,
+				    int unset)
+{
+	enum commit_graph_split_flags *flags = opt->value;
+
+	opts.split = 1;
+	if (!arg) {
+		*flags = COMMIT_GRAPH_SPLIT_MERGE_AUTO;
+		return 0;
+	}
+
+	if (!strcmp(arg, "merge-all"))
+		*flags = COMMIT_GRAPH_SPLIT_MERGE_REQUIRED;
+	else if (!strcmp(arg, "no-merge"))
+		*flags = COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED;
+	else
+		die(_("unrecognized --split argument, %s"), arg);
+
+	return 0;
+}
+
 static int graph_write(int argc, const char **argv)
 {
 	struct string_list *pack_indexes = NULL;
@@ -133,8 +158,10 @@ static int graph_write(int argc, const char **argv)
 		OPT_BOOL(0, "append", &opts.append,
 			N_("include all commits already in the commit-graph file")),
 		OPT_BOOL(0, "progress", &opts.progress, N_("force progress reporting")),
-		OPT_BOOL(0, "split", &opts.split,
-			N_("allow writing an incremental commit-graph file")),
+		OPT_CALLBACK_F(0, "split", &split_opts.flags, NULL,
+			N_("allow writing an incremental commit-graph file"),
+			PARSE_OPT_OPTARG | PARSE_OPT_NONEG,
+			write_option_parse_split),
 		OPT_INTEGER(0, "max-commits", &split_opts.max_commits,
 			N_("maximum number of commits in a non-base split commit-graph")),
 		OPT_INTEGER(0, "size-multiple", &split_opts.size_multiple,
diff --git a/commit-graph.c b/commit-graph.c
index 656dd647d5..3a5cb23cd7 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1533,27 +1533,33 @@ static void split_graph_merge_strategy(struct write_commit_graph_context *ctx)
 
 	int max_commits = 0;
 	int size_mult = 2;
+	enum commit_graph_split_flags flags = COMMIT_GRAPH_SPLIT_MERGE_AUTO;
 
 	if (ctx->split_opts) {
 		max_commits = ctx->split_opts->max_commits;
 
 		if (ctx->split_opts->size_multiple)
 			size_mult = ctx->split_opts->size_multiple;
+
+		flags = ctx->split_opts->flags;
 	}
 
 	g = ctx->r->objects->commit_graph;
 	num_commits = ctx->commits.nr;
 	ctx->num_commit_graphs_after = ctx->num_commit_graphs_before + 1;
 
-	while (g && (g->num_commits <= size_mult * num_commits ||
-		    (max_commits && num_commits > max_commits))) {
-		if (g->odb != ctx->odb)
-			break;
+	if (flags != COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED) {
+		while (g && (g->num_commits <= size_mult * num_commits ||
+			    (max_commits && num_commits > max_commits) ||
+			    (flags == COMMIT_GRAPH_SPLIT_MERGE_REQUIRED))) {
+			if (g->odb != ctx->odb)
+				break;
 
-		num_commits += g->num_commits;
-		g = g->base_graph;
+			num_commits += g->num_commits;
+			g = g->base_graph;
 
-		ctx->num_commit_graphs_after--;
+			ctx->num_commit_graphs_after--;
+		}
 	}
 
 	ctx->new_base_graph = g;
@@ -1861,7 +1867,7 @@ int write_commit_graph(struct object_directory *odb,
 		goto cleanup;
 	}
 
-	if (!ctx->commits.nr)
+	if (!ctx->commits.nr && (!ctx->split_opts || ctx->split_opts->flags != COMMIT_GRAPH_SPLIT_MERGE_REQUIRED))
 		goto cleanup;
 
 	if (ctx->split) {
diff --git a/commit-graph.h b/commit-graph.h
index e87a6f6360..65a7d2edae 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -82,10 +82,17 @@ enum commit_graph_write_flags {
 	COMMIT_GRAPH_WRITE_CHECK_OIDS = (1 << 3)
 };
 
+enum commit_graph_split_flags {
+	COMMIT_GRAPH_SPLIT_MERGE_AUTO       = 0,
+	COMMIT_GRAPH_SPLIT_MERGE_REQUIRED   = 1,
+	COMMIT_GRAPH_SPLIT_MERGE_PROHIBITED = 2
+};
+
 struct split_commit_graph_opts {
 	int size_multiple;
 	int max_commits;
 	timestamp_t expire_time;
+	enum commit_graph_split_flags flags;
 };
 
 /*
diff --git a/t/t5324-split-commit-graph.sh b/t/t5324-split-commit-graph.sh
index 53b2e6b455..bb2b724178 100755
--- a/t/t5324-split-commit-graph.sh
+++ b/t/t5324-split-commit-graph.sh
@@ -351,4 +351,29 @@ test_expect_success 'split across alternate where alternate is not split' '
 	test_cmp commit-graph .git/objects/info/commit-graph
 '
 
+test_expect_success '--split=merge-all always merges incrementals' '
+	test_when_finished rm -rf a b c &&
+	rm -rf $graphdir $infodir/commit-graph &&
+	git reset --hard commits/10 &&
+	git rev-list -3 HEAD~4 >a &&
+	git rev-list -2 HEAD~2 >b &&
+	git rev-list -2 HEAD >c &&
+	git commit-graph write --split=no-merge --stdin-commits <a &&
+	git commit-graph write --split=no-merge --stdin-commits <b &&
+	test_line_count = 2 $graphdir/commit-graph-chain &&
+	git commit-graph write --split=merge-all --stdin-commits <c &&
+	test_line_count = 1 $graphdir/commit-graph-chain
+'
+
+test_expect_success '--split=no-merge always writes an incremental' '
+	test_when_finished rm -rf a b &&
+	rm -rf $graphdir &&
+	git reset --hard commits/2 &&
+	git rev-list HEAD~1 >a &&
+	git rev-list HEAD >b &&
+	git commit-graph write --split --stdin-commits <a &&
+	git commit-graph write --split=no-merge --stdin-commits <b &&
+	test_line_count = 2 $graphdir/commit-graph-chain
+'
+
 test_done

-- 
2.25.0.119.gaa12b7378b
Previous: Taylor BlauNext: Taylor Blau
Message 48 of 58 in “builtin/commit-graph.c: new split/merge options”
  1. 0/3 builtin/commit-graph.c: new split/merge optionsTaylor Blau, Jan 31, 2020
  2. 1/3 builtin/commit-graph.c: support '--split[=<strategy>]'Taylor Blau, Jan 31, 2020
  3. Derrick StoleeJan 31, 2020
  4. Taylor BlauFeb 4, 2020
  5. Martin ÅgrenJan 31, 2020
  6. Taylor BlauFeb 4, 2020
  7. Martin ÅgrenFeb 6, 2020
  8. Taylor BlauFeb 9, 2020
  9. SZEDER GáborJan 31, 2020
  10. Johannes SchindelinFeb 1, 2020
  11. SZEDER GáborFeb 3, 2020
  12. Jeff KingFeb 3, 2020
  13. Taylor BlauFeb 4, 2020
  14. Jeff KingFeb 4, 2020
  15. Taylor BlauFeb 4, 2020
  16. Taylor BlauFeb 4, 2020
  17. 2/3 builtin/commit-graph.c: introduce '--input=<source>'Taylor Blau, Jan 31, 2020
  18. Derrick StoleeJan 31, 2020
  19. Taylor BlauFeb 4, 2020
  20. Martin ÅgrenJan 31, 2020
  21. Taylor BlauFeb 4, 2020
  22. SZEDER GáborFeb 13, 2020
  23. SZEDER GáborFeb 13, 2020
  24. Taylor BlauFeb 13, 2020
  25. 3/3 builtin/commit-graph.c: support '--input=none'Taylor Blau, Jan 31, 2020
  26. Derrick StoleeJan 31, 2020
  27. Martin ÅgrenJan 31, 2020
  28. Taylor BlauFeb 4, 2020
  29. Taylor BlauJan 31, 2020
  30. Derrick StoleeJan 31, 2020
  31. Derrick StoleeJan 31, 2020
  32. Junio C HamanoFeb 4, 2020
  33. Taylor BlauFeb 5, 2020
  34. 0/3 builtin/commit-graph.c: new split/merge optionsTaylor Blau, Feb 5, 2020
  35. 1/3 builtin/commit-graph.c: support '--split[=<strategy>]'Taylor Blau, Feb 5, 2020
  36. Martin ÅgrenFeb 6, 2020
  37. Derrick StoleeFeb 7, 2020
  38. Taylor BlauFeb 9, 2020
  39. Martin ÅgrenFeb 12, 2020
  40. Taylor BlauFeb 12, 2020
  41. Taylor BlauFeb 9, 2020
  42. 2/3 builtin/commit-graph.c: introduce '--input=<source>'Taylor Blau, Feb 5, 2020
  43. 3/3 builtin/commit-graph.c: support '--input=none'Taylor Blau, Feb 5, 2020
  44. Martin ÅgrenFeb 6, 2020
  45. Taylor BlauFeb 9, 2020
  46. Junio C HamanoFeb 5, 2020
  47. 0/3 builtin/commit-graph.c: new split/merge optionsTaylor Blau, Feb 12, 2020
  48. 1/3 builtin/commit-graph.c: support '--split[=<strategy>]'Taylor Blau, Feb 12, 2020
  49. 2/3 builtin/commit-graph.c: introduce '--input=<source>'Taylor Blau, Feb 12, 2020
  50. 3/3 builtin/commit-graph.c: support '--input=none'Taylor Blau, Feb 12, 2020
  51. SZEDER GáborFeb 13, 2020
  52. SZEDER GáborFeb 13, 2020
  53. Junio C HamanoFeb 13, 2020
  54. Taylor BlauFeb 13, 2020
  55. Taylor BlauFeb 13, 2020
  56. Junio C HamanoFeb 12, 2020
  57. Taylor BlauFeb 13, 2020
  58. Martin ÅgrenFeb 17, 2020

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.