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

[PATCH 04/12] commit-graph: decide mergeable and chainable layers by depth

From
Patrick Steinhardt <ps@pks.im>
Date
Nov 16, 2026, 13:07 UTC
Message-ID
<20261116-pks-odb-pluggable-commit-graphs-v1-4-a83fc1ff0808@pks.im>
In-Reply-To
<20261116-pks-odb-pluggable-commit-graphs-v1-0-a83fc1ff0808@pks.im>

When writing a split commit graph, `split_graph_merge_strategy()` decides which layers of the existing chain get merged into the new layer and which layer the new one builds upon. This is decided on two simple rules:

  - A layer may be merged in case it is part of the same local object
    directory.
  - A layer may be added to the chain in case it is either a split
    commit graph layer, regardless of whether it is local or not. Or in
    case it is local, we may also add it to our chain in case it is a
    non-split commit graph, in which case we convert it to a split one.

These checks require us to know about where exactly these commit graphs are stored on disk as we compare directories of the respective files with one another to figure out whether or not a layer is local. So as a consequence, this policy becomes backend-specific once the backend controls where exactly commit graphs are stored.

Refactor the code so that we instead tell the merge strategy how many of the topmost layers are mergeable and chainable, respectively, which will let the backends decide on that property.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 commit-graph.c | 51 ++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 40 insertions(+), 11 deletions(-)
diff --git a/commit-graph.c b/commit-graph.c
index 9464522feb5..7f7146e752a 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1151,6 +1151,8 @@ struct write_commit_graph_context {
 	uint64_t progress_cnt;
 
 	char *base_graph_name;
+	size_t mergeable_layers;
+	size_t chainable_layers;
 	int num_commit_graphs_before;
 	int num_commit_graphs_after;
 	char **commit_graph_filenames_before;
@@ -2283,6 +2285,7 @@ static void split_graph_merge_strategy(struct write_commit_graph_context *ctx,
 	enum commit_graph_split_flags flags = ctx->opts->split_flags;
 	int max_commits = ctx->opts->max_commits;
 	int size_mult = 2;
+	size_t depth = 0;
 	uint32_t i;
 
 	if (ctx->opts->size_multiple)
@@ -2299,7 +2302,7 @@ static void split_graph_merge_strategy(struct write_commit_graph_context *ctx,
 	    flags != COMMIT_GRAPH_SPLIT_REPLACE) {
 		while (g && (g->num_commits <= st_mult(size_mult, num_commits) ||
 			    (max_commits && num_commits > max_commits))) {
-			if (strcmp(g->dir, ctx->dir))
+			if (depth >= ctx->mergeable_layers)
 				break;
 
 			if (unsigned_add_overflows(num_commits, g->num_commits))
@@ -2309,6 +2312,7 @@ static void split_graph_merge_strategy(struct write_commit_graph_context *ctx,
 				    (uintmax_t)g->num_commits);
 			num_commits += g->num_commits;
 			g = g->base_graph;
+			depth++;
 
 			ctx->num_commit_graphs_after--;
 		}
@@ -2320,16 +2324,13 @@ static void split_graph_merge_strategy(struct write_commit_graph_context *ctx,
 		BUG("split_graph_merge_strategy: num_commit_graphs_after "
 		    "should be 1 with --split=replace");
 
-	if (ctx->num_commit_graphs_after == 2) {
-		char *old_graph_name = get_commit_graph_filename(g->dir);
-
-		if (!strcmp(g->filename, old_graph_name) &&
-		    strcmp(g->dir, ctx->dir)) {
-			ctx->num_commit_graphs_after = 1;
-			ctx->new_base_graph = NULL;
-		}
-
-		free(old_graph_name);
+	/*
+	 * If we cannot add the new base to our chain we instead merge it and
+	 * all of its base layers.
+	 */
+	if (ctx->new_base_graph && depth >= ctx->chainable_layers) {
+		ctx->num_commit_graphs_after = 1;
+		ctx->new_base_graph = NULL;
 	}
 
 	CALLOC_ARRAY(ctx->commit_graph_filenames_after, ctx->num_commit_graphs_after);
@@ -2560,6 +2561,7 @@ int commit_graph_write(struct repository *r,
 	struct oidset reachable_commits = OIDSET_INIT;
 	struct topo_level_slab topo_levels;
 	struct commit_graph *g;
+	bool mergeable = true;
 
 	if (!!opts->pack_indexes + !!opts->commits + !!(opts->flags & COMMIT_GRAPH_WRITE_REACHABLE) > 1)
 		BUG("attempting to write commit-graph with mutually incompatible options");
@@ -2597,6 +2599,33 @@ int commit_graph_write(struct repository *r,
 	for (struct commit_graph *chain = g; chain; chain = chain->base_graph)
 		chain->topo_levels = &topo_levels;
 
+	/*
+	 * We only consider merging layers that belong to our own object
+	 * directory. Furthermore, we can only chain on top of either:
+	 *
+	 *   - A split commit graph layer, regardless of whether or not it is
+	 *     local.
+	 *
+	 *   - A local non-split commit graph, in which case we'll convert that
+	 *     layer into a split commit graph layer.
+	 */
+	for (struct commit_graph *layer = g; layer; layer = layer->base_graph) {
+		char *path = get_commit_graph_filename(layer->dir);
+		bool is_split = !!strcmp(layer->filename, path);
+		bool is_local = !strcmp(layer->dir, ctx.dir);
+
+		free(path);
+
+		if (!is_local && !is_split)
+			break;
+		if (!is_local)
+			mergeable = false;
+
+		if (mergeable)
+			ctx.mergeable_layers++;
+		ctx.chainable_layers++;
+	}
+
 	if (opts->flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS)
 		ctx.changed_paths = 1;
 	if (!(opts->flags & COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS)) {
-- 
2.56.1.763.g16177fe143.dirty
Previous: Patrick SteinhardtNext: Patrick Steinhardt
Message 6 of 14 in “Introduce pluggable commit graphs”
  1. 00/12 Introduce pluggable commit graphsPatrick Steinhardt, Nov 16, 2026
  2. 01/12 commit-graph: simplify linking commit graph chainsPatrick Steinhardt, Nov 16, 2026
  3. Junio C HamanoNov 16, 2026
  4. 02/12 commit-graph: simplify reading a single commit graphPatrick Steinhardt, Nov 16, 2026
  5. 03/12 commit-graph: expose function to validate a commit graph chainPatrick Steinhardt, Nov 16, 2026
  6. 04/12 commit-graph: decide mergeable and chainable layers by depthPatrick Steinhardt, Nov 16, 2026
  7. 05/12 commit-graph: introduce common exit for `write_commit_graph_file()`Patrick Steinhardt, Nov 16, 2026
  8. 06/12 commit-graph: derive layer infos from the passed-in chainPatrick Steinhardt, Nov 16, 2026
  9. 07/12 commit-graph: split out check whether writing commit graphs is allowedPatrick Steinhardt, Nov 16, 2026
  10. 08/12 commit-graph: split out logic to write a new commit graph layerPatrick Steinhardt, Nov 16, 2026
  11. 09/12 commit-graph: mark incomplete commit graph chainsPatrick Steinhardt, Nov 16, 2026
  12. 10/12 odb/source: make commit graphs pluggablePatrick Steinhardt, Nov 16, 2026
  13. 11/12 odb/source-files: move logic to derive commit graph pathsPatrick Steinhardt, Nov 16, 2026
  14. 12/12 odb/source-files: internalize logic to derive commit graph pathsPatrick Steinhardt, Nov 16, 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.