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

[PATCH v7 08/14] commit-graph: implement git commit-graph read

From
Derrick Stolee <stolee@gmail.com>
Date
Apr 2, 2018, 20:34 UTC
Message-ID
<20180402203427.170177-9-dstolee@microsoft.com>
In-Reply-To
<20180402203427.170177-1-dstolee@microsoft.com>
From: Derrick Stolee <dstolee@microsoft.com>
Teach git-commit-graph to read commit graph files and summarize their contents.

Use the read subcommand to verify the contents of a commit graph file in the tests.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Documentation/git-commit-graph.txt |  12 +++
 builtin/commit-graph.c             |  56 ++++++++++++
 commit-graph.c                     | 137 ++++++++++++++++++++++++++++-
 commit-graph.h                     |  23 +++++
 t/t5318-commit-graph.sh            |  32 +++++--
 5 files changed, 254 insertions(+), 6 deletions(-)
diff --git a/Documentation/git-commit-graph.txt b/Documentation/git-commit-graph.txt
index 47996e8f89..8aad8303f5 100644
--- a/Documentation/git-commit-graph.txt
+++ b/Documentation/git-commit-graph.txt
@@ -9,6 +9,7 @@ git-commit-graph - Write and verify Git commit graph files
 SYNOPSIS
 --------
 [verse]
+'git commit-graph read' [--object-dir <dir>]
 'git commit-graph write' <options> [--object-dir <dir>]
 
 
@@ -35,6 +36,11 @@ COMMANDS
 Write a commit graph file based on the commits found in packfiles.
 Includes all commits from the existing commit graph file.
 
+'read'::
+
+Read a graph file given by the commit-graph file and output basic
+details about the graph file. Used for debugging purposes.
+
 
 EXAMPLES
 --------
@@ -45,6 +51,12 @@ EXAMPLES
 $ git commit-graph write
 ------------------------------------------------
 
+* Read basic information from the commit-graph file.
++
+------------------------------------------------
+$ git commit-graph read
+------------------------------------------------
+
 
 GIT
 ---
diff --git a/builtin/commit-graph.c b/builtin/commit-graph.c
index 26b6360289..e3f67401fb 100644
--- a/builtin/commit-graph.c
+++ b/builtin/commit-graph.c
@@ -7,10 +7,16 @@
 
 static char const * const builtin_commit_graph_usage[] = {
 	N_("git commit-graph [--object-dir <objdir>]"),
+	N_("git commit-graph read [--object-dir <objdir>]"),
 	N_("git commit-graph write [--object-dir <objdir>]"),
 	NULL
 };
 
+static const char * const builtin_commit_graph_read_usage[] = {
+	N_("git commit-graph read [--object-dir <objdir>]"),
+	NULL
+};
+
 static const char * const builtin_commit_graph_write_usage[] = {
 	N_("git commit-graph write [--object-dir <objdir>]"),
 	NULL
@@ -20,6 +26,54 @@ static struct opts_commit_graph {
 	const char *obj_dir;
 } opts;
 
+static int graph_read(int argc, const char **argv)
+{
+	struct commit_graph *graph = 0;
+	char *graph_name;
+
+	static struct option builtin_commit_graph_read_options[] = {
+		OPT_STRING(0, "object-dir", &opts.obj_dir,
+			N_("dir"),
+			N_("The object directory to store the graph")),
+		OPT_END(),
+	};
+
+	argc = parse_options(argc, argv, NULL,
+			     builtin_commit_graph_read_options,
+			     builtin_commit_graph_read_usage, 0);
+
+	if (!opts.obj_dir)
+		opts.obj_dir = get_object_directory();
+
+	graph_name = get_commit_graph_filename(opts.obj_dir);
+	graph = load_commit_graph_one(graph_name);
+
+	if (!graph)
+		die("graph file %s does not exist", graph_name);
+	FREE_AND_NULL(graph_name);
+
+	printf("header: %08x %d %d %d %d\n",
+		ntohl(*(uint32_t*)graph->data),
+		*(unsigned char*)(graph->data + 4),
+		*(unsigned char*)(graph->data + 5),
+		*(unsigned char*)(graph->data + 6),
+		*(unsigned char*)(graph->data + 7));
+	printf("num_commits: %u\n", graph->num_commits);
+	printf("chunks:");
+
+	if (graph->chunk_oid_fanout)
+		printf(" oid_fanout");
+	if (graph->chunk_oid_lookup)
+		printf(" oid_lookup");
+	if (graph->chunk_commit_data)
+		printf(" commit_metadata");
+	if (graph->chunk_large_edges)
+		printf(" large_edges");
+	printf("\n");
+
+	return 0;
+}
+
 static int graph_write(int argc, const char **argv)
 {
 	static struct option builtin_commit_graph_write_options[] = {
@@ -60,6 +114,8 @@ int cmd_commit_graph(int argc, const char **argv, const char *prefix)
 			     PARSE_OPT_STOP_AT_NON_OPTION);
 
 	if (argc > 0) {
+		if (!strcmp(argv[0], "read"))
+			return graph_read(argc, argv);
 		if (!strcmp(argv[0], "write"))
 			return graph_write(argc, argv);
 	}
diff --git a/commit-graph.c b/commit-graph.c
index f3f7c4f189..b1bd3a892d 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -39,11 +39,146 @@
 			GRAPH_OID_LEN + 8)
 
 
-static char *get_commit_graph_filename(const char *obj_dir)
+char *get_commit_graph_filename(const char *obj_dir)
 {
 	return xstrfmt("%s/info/commit-graph", obj_dir);
 }
 
+static struct commit_graph *alloc_commit_graph(void)
+{
+	struct commit_graph *g = xcalloc(1, sizeof(*g));
+	g->graph_fd = -1;
+
+	return g;
+}
+
+struct commit_graph *load_commit_graph_one(const char *graph_file)
+{
+	void *graph_map;
+	const unsigned char *data, *chunk_lookup;
+	size_t graph_size;
+	struct stat st;
+	uint32_t i;
+	struct commit_graph *graph;
+	int fd = git_open(graph_file);
+	uint64_t last_chunk_offset;
+	uint32_t last_chunk_id;
+	uint32_t graph_signature;
+	unsigned char graph_version, hash_version;
+
+	if (fd < 0)
+		return NULL;
+	if (fstat(fd, &st)) {
+		close(fd);
+		return NULL;
+	}
+	graph_size = xsize_t(st.st_size);
+
+	if (graph_size < GRAPH_MIN_SIZE) {
+		close(fd);
+		die("graph file %s is too small", graph_file);
+	}
+	graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	data = (const unsigned char *)graph_map;
+
+	graph_signature = get_be32(data);
+	if (graph_signature != GRAPH_SIGNATURE) {
+		error("graph signature %X does not match signature %X",
+		      graph_signature, GRAPH_SIGNATURE);
+		goto cleanup_fail;
+	}
+
+	graph_version = *(unsigned char*)(data + 4);
+	if (graph_version != GRAPH_VERSION) {
+		error("graph version %X does not match version %X",
+		      graph_version, GRAPH_VERSION);
+		goto cleanup_fail;
+	}
+
+	hash_version = *(unsigned char*)(data + 5);
+	if (hash_version != GRAPH_OID_VERSION) {
+		error("hash version %X does not match version %X",
+		      hash_version, GRAPH_OID_VERSION);
+		goto cleanup_fail;
+	}
+
+	graph = alloc_commit_graph();
+
+	graph->hash_len = GRAPH_OID_LEN;
+	graph->num_chunks = *(unsigned char*)(data + 6);
+	graph->graph_fd = fd;
+	graph->data = graph_map;
+	graph->data_len = graph_size;
+
+	last_chunk_id = 0;
+	last_chunk_offset = 8;
+	chunk_lookup = data + 8;
+	for (i = 0; i < graph->num_chunks; i++) {
+		uint32_t chunk_id = get_be32(chunk_lookup + 0);
+		uint64_t chunk_offset = get_be64(chunk_lookup + 4);
+		int chunk_repeated = 0;
+
+		chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
+
+		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
+			error("improper chunk offset %08x%08x", (uint32_t)(chunk_offset >> 32),
+			      (uint32_t)chunk_offset);
+			goto cleanup_fail;
+		}
+
+		switch (chunk_id) {
+		case GRAPH_CHUNKID_OIDFANOUT:
+			if (graph->chunk_oid_fanout)
+				chunk_repeated = 1;
+			else
+				graph->chunk_oid_fanout = (uint32_t*)(data + chunk_offset);
+			break;
+
+		case GRAPH_CHUNKID_OIDLOOKUP:
+			if (graph->chunk_oid_lookup)
+				chunk_repeated = 1;
+			else
+				graph->chunk_oid_lookup = data + chunk_offset;
+			break;
+
+		case GRAPH_CHUNKID_DATA:
+			if (graph->chunk_commit_data)
+				chunk_repeated = 1;
+			else
+				graph->chunk_commit_data = data + chunk_offset;
+			break;
+
+		case GRAPH_CHUNKID_LARGEEDGES:
+			if (graph->chunk_large_edges)
+				chunk_repeated = 1;
+			else
+				graph->chunk_large_edges = data + chunk_offset;
+			break;
+		}
+
+		if (chunk_repeated) {
+			error("chunk id %08x appears multiple times", chunk_id);
+			goto cleanup_fail;
+		}
+
+		if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)
+		{
+			graph->num_commits = (chunk_offset - last_chunk_offset)
+					     / graph->hash_len;
+		}
+
+		last_chunk_id = chunk_id;
+		last_chunk_offset = chunk_offset;
+	}
+
+	return graph;
+
+cleanup_fail:
+	munmap(graph_map, graph_size);
+	close(fd);
+	exit(1);
+}
+
 static void write_graph_chunk_fanout(struct hashfile *f,
 				     struct commit **commits,
 				     int nr_commits)
diff --git a/commit-graph.h b/commit-graph.h
index 16fea993ab..2528478f06 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -1,6 +1,29 @@
 #ifndef COMMIT_GRAPH_H
 #define COMMIT_GRAPH_H
 
+#include "git-compat-util.h"
+
+char *get_commit_graph_filename(const char *obj_dir);
+
+struct commit_graph {
+	int graph_fd;
+
+	const unsigned char *data;
+	size_t data_len;
+
+	unsigned char hash_len;
+	unsigned char num_chunks;
+	uint32_t num_commits;
+	struct object_id oid;
+
+	const uint32_t *chunk_oid_fanout;
+	const unsigned char *chunk_oid_lookup;
+	const unsigned char *chunk_commit_data;
+	const unsigned char *chunk_large_edges;
+};
+
+struct commit_graph *load_commit_graph_one(const char *graph_file);
+
 void write_commit_graph(const char *obj_dir);
 
 #endif
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index d7b635bd68..2f44f91193 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -26,10 +26,28 @@ test_expect_success 'create commits and repack' '
 	git repack
 '
 
+graph_read_expect() {
+	OPTIONAL=""
+	NUM_CHUNKS=3
+	if test ! -z $2
+	then
+		OPTIONAL=" $2"
+		NUM_CHUNKS=$((3 + $(echo "$2" | wc -w)))
+	fi
+	cat >expect <<- EOF
+	header: 43475048 1 1 $NUM_CHUNKS 0
+	num_commits: $1
+	chunks: oid_fanout oid_lookup commit_metadata$OPTIONAL
+	EOF
+	git commit-graph read >output &&
+	test_cmp expect output
+}
+
 test_expect_success 'write graph' '
 	cd "$TRASH_DIRECTORY/full" &&
 	graph1=$(git commit-graph write) &&
-	test_path_is_file $objdir/info/commit-graph
+	test_path_is_file $objdir/info/commit-graph &&
+	graph_read_expect "3"
 '
 
 test_expect_success 'Add more commits' '
@@ -72,7 +90,8 @@ test_expect_success 'Add more commits' '
 test_expect_success 'write graph with merges' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git commit-graph write &&
-	test_path_is_file $objdir/info/commit-graph
+	test_path_is_file $objdir/info/commit-graph &&
+	graph_read_expect "10" "large_edges"
 '
 
 test_expect_success 'Add one more commit' '
@@ -99,13 +118,15 @@ test_expect_success 'Add one more commit' '
 test_expect_success 'write graph with new commit' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git commit-graph write &&
-	test_path_is_file $objdir/info/commit-graph
+	test_path_is_file $objdir/info/commit-graph &&
+	graph_read_expect "11" "large_edges"
 '
 
 test_expect_success 'write graph with nothing new' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git commit-graph write &&
-	test_path_is_file $objdir/info/commit-graph
+	test_path_is_file $objdir/info/commit-graph &&
+	graph_read_expect "11" "large_edges"
 '
 
 test_expect_success 'setup bare repo' '
@@ -118,7 +139,8 @@ test_expect_success 'setup bare repo' '
 test_expect_success 'write graph in bare repo' '
 	cd "$TRASH_DIRECTORY/bare" &&
 	git commit-graph write &&
-	test_path_is_file $baredir/info/commit-graph
+	test_path_is_file $baredir/info/commit-graph &&
+	graph_read_expect "11" "large_edges"
 '
 
 test_done

-- 
2.17.0.14.gba1221a8ce
Previous: Jakub NarebskiNext: Junio C Hamano
Message 83 of 110 in “Serialized Git Commit Graph”
  1. 00/13 Serialized Git Commit GraphDerrick Stolee, Feb 27, 2018
  2. 01/13 commit-graph: add format documentDerrick Stolee, Feb 27, 2018
  3. 02/13 graph: add commit graph design documentDerrick Stolee, Feb 27, 2018
  4. 04/13 csum-file: add CSUM_KEEP_OPEN flagDerrick Stolee, Feb 27, 2018
  5. Derrick StoleeMar 12, 2018
  6. Junio C HamanoMar 13, 2018
  7. Derrick StoleeMar 14, 2018
  8. Junio C HamanoMar 14, 2018
  9. 06/13 commit-graph: implement 'git-commit-graph write'Derrick Stolee, Feb 27, 2018
  10. 05/13 commit-graph: implement write_commit_graph()Derrick Stolee, Feb 27, 2018
  11. 03/13 commit-graph: create git-commit-graph builtinDerrick Stolee, Feb 27, 2018
  12. 13/13 commit-graph: implement "--additive" optionDerrick Stolee, Feb 27, 2018
  13. 12/13 commit-graph: build graph from starting commitsDerrick Stolee, Feb 27, 2018
  14. 11/13 commit-graph: read only from specific pack-indexesDerrick Stolee, Feb 27, 2018
  15. Stefan BellerFeb 27, 2018
  16. 10/13 commit: integrate commit graph with commit parsingDerrick Stolee, Feb 27, 2018
  17. 07/13 commit-graph: implement git commit-graph readDerrick Stolee, Feb 27, 2018
  18. 08/13 commit-graph: add core.commitGraph settingDerrick Stolee, Feb 27, 2018
  19. 09/13 commit-graph: close under reachabilityDerrick Stolee, Feb 27, 2018
  20. Stefan BellerFeb 27, 2018
  21. 00/14 Serialized Git Commit GraphDerrick Stolee, Mar 14, 2018
  22. 02/14 csum-file: refactor finalize_hashfile() methodDerrick Stolee, Mar 14, 2018
  23. 03/14 commit-graph: add format documentDerrick Stolee, Mar 14, 2018
  24. 04/14 graph: add commit graph design documentDerrick Stolee, Mar 14, 2018
  25. 08/14 commit-graph: implement git commit-graph readDerrick Stolee, Mar 14, 2018
  26. 06/14 commit-graph: implement write_commit_graph()Derrick Stolee, Mar 14, 2018
  27. 10/14 commit-graph: close under reachabilityDerrick Stolee, Mar 14, 2018
  28. 12/14 commit-graph: read only from specific pack-indexesDerrick Stolee, Mar 14, 2018
  29. SZEDER GáborMar 15, 2018
  30. Derrick StoleeMar 19, 2018
  31. 09/14 commit-graph: add core.commitGraph settingDerrick Stolee, Mar 14, 2018
  32. 11/14 commit: integrate commit graph with commit parsingDerrick Stolee, Mar 14, 2018
  33. 13/14 commit-graph: build graph from starting commitsDerrick Stolee, Mar 14, 2018
  34. 14/14 commit-graph: implement "--additive" optionDerrick Stolee, Mar 14, 2018
  35. 05/14 commit-graph: create git-commit-graph builtinDerrick Stolee, Mar 14, 2018
  36. 07/14 commit-graph: implement 'git-commit-graph write'Derrick Stolee, Mar 14, 2018
  37. Ævar Arnfjörð BjarmasonMar 18, 2018
  38. Derrick StoleeMar 19, 2018
  39. Ævar Arnfjörð BjarmasonMar 19, 2018
  40. Derrick StoleeMar 19, 2018
  41. Ævar Arnfjörð BjarmasonMar 19, 2018
  42. 01/14 csum-file: rename hashclose() to finalize_hashfile()Derrick Stolee, Mar 14, 2018
  43. Ramsay JonesMar 14, 2018
  44. Junio C HamanoMar 14, 2018
  45. Johannes SchindelinMar 15, 2018
  46. Junio C HamanoMar 15, 2018
  47. Ramsay JonesMar 15, 2018
  48. Johannes SchindelinMar 16, 2018
  49. Junio C HamanoMar 16, 2018
  50. Johannes SchindelinMar 19, 2018
  51. Lars SchneiderMar 16, 2018
  52. Derrick StoleeMar 19, 2018
  53. Ævar Arnfjörð BjarmasonMar 16, 2018
  54. SZEDER GáborMar 16, 2018
  55. Junio C HamanoMar 16, 2018
  56. SZEDER GáborMar 16, 2018
  57. Jeff KingMar 16, 2018
  58. Jeff KingMar 16, 2018
  59. Derrick StoleeMar 19, 2018
  60. Derrick StoleeMar 20, 2018
  61. Jeff KingMar 16, 2018
  62. 00/14 Serialized Git Commit GraphDerrick Stolee, Apr 2, 2018
  63. 01/14 csum-file: rename hashclose() to finalize_hashfile()Derrick Stolee, Apr 2, 2018
  64. 02/14 csum-file: refactor finalize_hashfile() methodDerrick Stolee, Apr 2, 2018
  65. Jakub NarebskiApr 7, 2018
  66. 03/14 commit-graph: add format documentDerrick Stolee, Apr 2, 2018
  67. Jakub NarebskiApr 7, 2018
  68. 04/14 graph: add commit graph design documentDerrick Stolee, Apr 2, 2018
  69. Jakub NarebskiApr 8, 2018
  70. 06/14 commit-graph: implement write_commit_graph()Derrick Stolee, Apr 2, 2018
  71. 11/14 commit: integrate commit graph with commit parsingDerrick Stolee, Apr 2, 2018
  72. 13/14 commit-graph: build graph from starting commitsDerrick Stolee, Apr 2, 2018
  73. Jakub NarebskiApr 8, 2018
  74. 14/14 commit-graph: implement "--additive" optionDerrick Stolee, Apr 2, 2018
  75. SZEDER GáborApr 5, 2018
  76. 10/14 commit-graph: close under reachabilityDerrick Stolee, Apr 2, 2018
  77. 12/14 commit-graph: read only from specific pack-indexesDerrick Stolee, Apr 2, 2018
  78. 09/14 commit-graph: add core.commitGraph settingDerrick Stolee, Apr 2, 2018
  79. Jakub NarebskiApr 8, 2018
  80. 05/14 commit-graph: create git-commit-graph builtinDerrick Stolee, Apr 2, 2018
  81. 07/14 commit-graph: implement git-commit-graph writeDerrick Stolee, Apr 2, 2018
  82. Jakub NarebskiApr 8, 2018
  83. 08/14 commit-graph: implement git commit-graph readDerrick Stolee, Apr 2, 2018
  84. Junio C HamanoApr 2, 2018
  85. Derrick StoleeApr 3, 2018
  86. Jakub NarebskiApr 8, 2018
  87. 00/14 Serialized Git Commit GraphDerrick Stolee, Apr 10, 2018
  88. 01/14 csum-file: rename hashclose() to finalize_hashfile()Derrick Stolee, Apr 10, 2018
  89. 02/14 csum-file: refactor finalize_hashfile() methodDerrick Stolee, Apr 10, 2018
  90. 03/14 commit-graph: add format documentDerrick Stolee, Apr 10, 2018
  91. Stefan BellerApr 10, 2018
  92. Derrick StoleeApr 10, 2018
  93. Jakub NarebskiApr 11, 2018
  94. Derrick StoleeApr 12, 2018
  95. Jakub NarebskiApr 13, 2018
  96. 04/14 graph: add commit graph design documentDerrick Stolee, Apr 10, 2018
  97. Jakub NarebskiApr 15, 2018
  98. 05/14 commit-graph: create git-commit-graph builtinDerrick Stolee, Apr 10, 2018
  99. 07/14 commit-graph: implement git-commit-graph writeDerrick Stolee, Apr 10, 2018
  100. 08/14 commit-graph: implement git commit-graph readDerrick Stolee, Apr 10, 2018
  101. Jakub NarebskiApr 14, 2018
  102. Eric SunshineApr 15, 2018
  103. 09/14 commit-graph: add core.commitGraph settingDerrick Stolee, Apr 10, 2018
  104. Jakub NarebskiApr 14, 2018
  105. 06/14 commit-graph: implement write_commit_graph()Derrick Stolee, Apr 10, 2018
  106. 10/14 commit-graph: close under reachabilityDerrick Stolee, Apr 10, 2018
  107. 11/14 commit: integrate commit graph with commit parsingDerrick Stolee, Apr 10, 2018
  108. 12/14 commit-graph: read only from specific pack-indexesDerrick Stolee, Apr 10, 2018
  109. 13/14 commit-graph: build graph from starting commitsDerrick Stolee, Apr 10, 2018
  110. 14/14 commit-graph: implement "--append" optionDerrick Stolee, Apr 10, 2018

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.