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

[PATCH 01/12] commit-graph: simplify linking commit graph chains

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

When we load a commit graph chain we verify for every layer that the hash of the base commit graph matches what the current tip has in its base graphs chunk. To do so we pass both the chain itself as well as the array of object IDs that we have read from the commit-graph chain file to `add_graph_to_chain()`.

But the array of object IDs is redundant information: we have already loaded and linked the base layers, and as part of that we have stored their respective hashes in the structure itself. Consequently, we can already derive the hashes by walking the chain of base layers.

Refactor the function to only take the new tip and base layers as input and derive all the other information ad-hoc and make the function public. This prepares for a subsequent commit, where we are about to move the logic that creates commit graph chains into the object database backend.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 commit-graph.c | 52 ++++++++++++++++++++++++----------------------------
 commit-graph.h |  8 ++++++++
 2 files changed, 32 insertions(+), 28 deletions(-)
diff --git a/commit-graph.c b/commit-graph.c
index da65cd3deb9..94c761907a0 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -575,50 +575,48 @@ static void validate_mixed_bloom_settings(struct commit_graph *g)
 	}
 }
 
-static int add_graph_to_chain(struct commit_graph *g,
-			      struct commit_graph *chain,
-			      struct object_id *oids,
-			      int n)
+int commit_graph_link_base(struct commit_graph *g,
+			   struct commit_graph *base)
 {
-	struct commit_graph *cur_g = chain;
+	struct commit_graph *layer;
+	size_t n = 0;
+
+	for (layer = base; layer; layer = layer->base_graph)
+		n++;
 
 	if (n && !g->chunk_base_graphs) {
 		warning(_("commit-graph has no base graphs chunk"));
-		return 0;
+		return -1;
 	}
 
 	if (g->chunk_base_graphs_size / g->hash_algo->rawsz < n) {
 		warning(_("commit-graph base graphs chunk is too small"));
-		return 0;
+		return -1;
 	}
 
-	while (n) {
+	for (layer = base; layer; layer = layer->base_graph) {
 		n--;
-
-		if (!cur_g ||
-		    !oideq(&oids[n], &cur_g->oid) ||
-		    !hasheq(oids[n].hash, g->chunk_base_graphs + st_mult(g->hash_algo->rawsz, n),
+		if (!hasheq(layer->oid.hash,
+			    g->chunk_base_graphs + st_mult(g->hash_algo->rawsz, n),
 			    g->hash_algo)) {
 			warning(_("commit-graph chain does not match"));
-			return 0;
+			return -1;
 		}
-
-		cur_g = cur_g->base_graph;
 	}
 
-	if (chain) {
-		if (unsigned_add_overflows(chain->num_commits,
-					   chain->num_commits_in_base)) {
+	if (base) {
+		if (unsigned_add_overflows(base->num_commits,
+					   base->num_commits_in_base)) {
 			warning(_("commit count in base graph too high: %"PRIuMAX),
-				(uintmax_t)chain->num_commits_in_base);
-			return 0;
+				(uintmax_t)base->num_commits_in_base);
+			return -1;
 		}
-		g->num_commits_in_base = chain->num_commits + chain->num_commits_in_base;
+		g->num_commits_in_base = base->num_commits + base->num_commits_in_base;
 	}
 
-	g->base_graph = chain;
+	g->base_graph = base;
 
-	return 1;
+	return 0;
 }
 
 int open_commit_graph_chain(const char *chain_file,
@@ -652,20 +650,19 @@ struct commit_graph *load_commit_graph_chain_fd_st(struct object_database *odb,
 {
 	struct commit_graph *graph_chain = NULL;
 	struct strbuf line = STRBUF_INIT;
-	struct object_id *oids;
 	int i = 0, valid = 1, count;
 	FILE *fp = xfdopen(fd, "r");
 
 	count = st->st_size / (odb->repo->hash_algo->hexsz + 1);
-	CALLOC_ARRAY(oids, count);
 
 	for (i = 0; i < count; i++) {
 		struct odb_source_files *files;
+		struct object_id oid;
 
 		if (strbuf_getline_lf(&line, fp) == EOF)
 			break;
 
-		if (get_oid_hex_algop(line.buf, &oids[i], odb->repo->hash_algo)) {
+		if (get_oid_hex_algop(line.buf, &oid, odb->repo->hash_algo)) {
 			warning(_("invalid commit-graph chain: line '%s' not a hash"),
 				line.buf);
 			valid = 0;
@@ -682,7 +679,7 @@ struct commit_graph *load_commit_graph_chain_fd_st(struct object_database *odb,
 			free(graph_name);
 
 			if (g) {
-				if (add_graph_to_chain(g, graph_chain, oids, i)) {
+				if (!commit_graph_link_base(g, graph_chain)) {
 					graph_chain = g;
 					valid = 1;
 				} else {
@@ -702,7 +699,6 @@ struct commit_graph *load_commit_graph_chain_fd_st(struct object_database *odb,
 	validate_mixed_generation_chain(graph_chain);
 	validate_mixed_bloom_settings(graph_chain);
 
-	free(oids);
 	fclose(fp);
 	strbuf_release(&line);
 
diff --git a/commit-graph.h b/commit-graph.h
index 2156499a688..f0e7cc93461 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -128,6 +128,14 @@ struct commit_graph *load_commit_graph_one_fd_st(struct repository *repo,
 struct commit_graph *load_commit_graph_chain_fd_st(struct object_database *odb,
 						   int fd, struct stat *st,
 						   int *incomplete_chain);
+
+/*
+ * Link the commit graph layer `g` on top of the chain `base`. `base` may be
+ * NULL if `g` is the root of a new chain. Returns 0 on success, a negative
+ * error code otherwise.
+ */
+int commit_graph_link_base(struct commit_graph *g,
+			   struct commit_graph *base);
 struct commit_graph *read_commit_graph_one(struct repository *repo,
 					   const char *dir);
 
-- 
2.56.1.763.g16177fe143.dirty
Previous: Patrick SteinhardtNext: Junio C Hamano
Message 2 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.