Serialized Git Commit Graph

Documentation/technical/commit-graph-format.txt new file +7 -0

+  Commit Data (ID: {'C', 'G', 'E', 'T' }) (N * (H + 16) bytes)
+    * The first H bytes are for the OID of the root tree.
+    * The next 8 bytes are for the int-ids of the first two parents
+      of the ith commit. Stores value 0xffffffff if no parent in that
+      position. If there are more than two parents, the second value
+      has its most-significant bit on and the other bits store an array
+      position into the Large Edge List chunk.

Add Documentation/technical/commit-graph.txt with details of the planned commit graph feature, including future plans.

Signed-off-by Derrick Stolee <[email protected]>

---
 Documentation/technical/commit-graph.txt | 189 +++++++++++++++++++++++++++++++
 1 file changed, 189 insertions(+)
 create mode 100644 Documentation/technical/commit-graph.txt

Documentation/technical/commit-graph.txt new file +2 -0

new file mode 100644
index 0000000000..cbf88f7264
@@ -0,0 +1,189 @@
+Git Commit Graph Design Notes
+=============================

Documentation/technical/commit-graph.txt new file +176 -1

+There are two main costs here:
+
+1. Decompressing and parsing commits.
+2. Walking the entire graph to avoid topological order mistakes.
+
+The commit graph file is a supplemental data structure that accelerates
+commit graph walks. If a user downgrades or disables the 'core.commitgraph'
+config setting, then the existing ODB is sufficient. The file is stored
+next to packfiles either in the .git/objects/pack directory or in the pack
+directory of an alternate.
+
+The commit graph file stores the commit graph structure along with some
+extra metadata to speed up graph walks. By listing commit OIDs in lexi-
+cographic order, we can identify an integer position for each commit and
+refer to the parents of a commit using those integer positions. We use
+binary search to find initial commits and then use the integer positions
+for fast lookups during the walk.
+
+A consumer may load the following info for a commit from the graph:
+
+1. The commit OID.
+2. The list of parents, along with their integer position.
+3. The commit date.
+4. The root tree OID.
+5. The generation number (see definition below).
+
+Values 1-4 satisfy the requirements of parse_commit_gently().
+
+Define the "generation number" of a commit recursively as follows:
+
+ * A commit with no parents (a root commit) has generation number one.
+
+ * A commit with at least one parent has generation number one more than
+   the largest generation number among its parents.
+
+Equivalently, the generation number of a commit A is one more than the
+length of a longest path from A to a root commit. The recursive definition
+is easier to use for computation and observing the following property:
+
+    If A and B are commits with generation numbers N and M, respectively,
+    and N <= M, then A cannot reach B. That is, we know without searching
+    that B is not an ancestor of A because it is further from a root commit
+    than A.
+
+    Conversely, when checking if A is an ancestor of B, then we only need
+    to walk commits until all commits on the walk boundary have generation
+    number at most N. If we walk commits using a priority queue seeded by
+    generation numbers, then we always expand the boundary commit with highest
+    generation number and can easily detect the stopping condition.
+
+This property can be used to significantly reduce the time it takes to
+walk commits and determine topological relationships. Without generation
+numbers, the general heuristic is the following:
+
+    If A and B are commits with commit time X and Y, respectively, and
+    X < Y, then A _probably_ cannot reach B.
+
+This heuristic is currently used whenever the computation can make
+mistakes with topological orders (such as "git log" with default order),
+but is not used when the topological order is required (such as merge
+base calculations, "git log --graph").
+
+In practice, we expect some commits to be created recently and not stored
+in the commit graph. We can treat these commits as having "infinite"
+generation number and walk until reaching commits with known generation
+number.
+
+Design Details
+--------------
+
+- A graph file is stored in a file named 'graph-<hash>.graph' in the pack
+  directory. This could be stored in an alternate.
+
+- The most-recent graph file hash is stored in a 'graph-head' file for
+  immediate access and storing backup graphs. This could be stored in an
+  alternate, and refers to a 'graph-<hash>.graph' file in the same pack
+  directory.
+
+- The core.commitgraph config setting must be on to consume graph files.
+
+- The file format includes parameters for the object id length and hash
+  algorithm, so a future change of hash algorithm does not require a change
+  in format.
+
+Current Limitations
+-------------------
+
+- Only one graph file is used at one time. This allows the integer position
+  to seek into the single graph file. It is possible to extend the model
+  for multiple graph files, but that is currently not part of the design.
+
+- .graph files are managed only by the 'commit-graph' builtin. These are not
+  updated automatically during clone, fetch, repack, or creating new commits.
+
+- There is no '--verify' option for the 'commit-graph' builtin to verify the
+  contents of the graph file agree with the contents in the ODB.
+
+- When rewriting the graph, we do not check for a commit still existing
+  in the ODB, so garbage collection may remove commits.
+
+- Generation numbers are not computed in the current version. The file
+  format supports storing them, along with a mechanism to upgrade from
+  a file without generation numbers to one that uses them.
+
+Future Work
+-----------
+
+- The file format includes room for precomputed generation numbers. These
+  are not currently computed, so all generation numbers will be marked as
+  0 (or "uncomputed"). A later patch will include this calculation.
+
+- The commit graph is currently incompatible with commit grafts. This can be
+  remedied by duplicating or refactoring the current graft logic.
+
+- After computing and storing generation numbers, we must make graph
+  walks aware of generation numbers to gain the performance benefits they
+  enable. This will mostly be accomplished by swapping a commit-date-ordered
+  priority queue with one ordered by generation number. The following
+  operations are important candidates:
+
+    - paint_down_to_common()
+    - 'log --topo-order'
+
+- The graph currently only adds commits to a previously existing graph.
+  When writing a new graph, we could check that the ODB still contains
+  the commits and choose to remove the commits that are deleted from the
+  ODB. For performance reasons, this check should remain optional.
+
+- Currently, parse_commit_gently() requires filling in the root tree
+  object for a commit. This passes through lookup_tree() and consequently
+  lookup_object(). Also, it calls lookup_commit() when loading the parents.
+  These method calls check the ODB for object existence, even if the
+  consumer does not need the content. For example, we do not need the
+  tree contents when computing merge bases. Now that commit parsing is
+  removed from the computation time, these lookup operations are the
+  slowest operations keeping graph walks from being fast. Consider
+  loading these objects without verifying their existence in the ODB and
+  only loading them fully when consumers need them. Consider a method
+  such as "ensure_tree_loaded(commit)" that fully loads a tree before
+  using commit->tree.
+
+- The current design uses the 'commit-graph' builtin to generate the graph.
+  When this feature stabilizes enough to recommend to most users, we should
+  add automatic graph writes to common operations that create many commits.
+  For example, one coulde compute a graph on 'clone', 'fetch', or 'repack'
+  commands.
+
+- A server could provide a commit graph file as part of the network protocol
+  to avoid extra calculations by clients.
+
+Related Links
+-------------
+[0] https://bugs.chromium.org/p/git/issues/detail?id=8
+    Chromium work item for: Serialized Commit Graph
+
+[1] https://public-inbox.org/git/[email protected]/
+    An abandoned patch that introduced generation numbers.
+
+[2] https://public-inbox.org/git/[email protected]/
+    Discussion about generation numbers on commits and how they interact
+    with fsck.
+
+[3] https://public-inbox.org/git/[email protected]/t/#m7a2ea7b355aeda962e6b86404bcbadc648abfbba
+    More discussion about generation numbers and not storing them inside
+    commit objects. A valuable quote:
+
+    "I think we should be moving more in the direction of keeping
+     repo-local caches for optimizations. Reachability bitmaps have been
+     a big performance win. I think we should be doing the same with our
+     properties of commits. Not just generation numbers, but making it
+     cheap to access the graph structure without zlib-inflating whole
+     commit objects (i.e., packv4 or something like the "metapacks" I
+     proposed a few years ago)."
+
+[4] https://public-inbox.org/git/[email protected]/T/#u
+    A patch to remove the ahead-behind calculation from 'status'.
--

2.16.0.15.g9c3cf44.dirty

commit-graph.c new file +15 -0

+static void write_graph_chunk_fanout(struct sha1file *f,
+				     struct commit **commits,
+				     int nr_commits)
+{
+	uint32_t i, count = 0;
+	struct commit **list = commits;
+	struct commit **last = commits + nr_commits;
+
+	/*
+	 * Write the first-level table (the list is sorted,
+	 * but we use a 256-entry lookup to be able to avoid
+	 * having to do eight extra binary search iterations).
+	 */
+	for (i = 0; i < 256; i++) {
+		uint32_t swap_count;

commit-graph.c new file +15 -0

+static void write_graph_chunk_large_edges(struct sha1file *f,
+					  struct commit **commits,
+					  int nr_commits)
+{
+	struct commit **list = commits;
+	struct commit **last = commits + nr_commits;
+	struct commit_list *parent;
+
+	while (list < last) {
+		int num_parents = 0;
+		for (parent = (*list)->parents; num_parents < 3 && parent;
+		     parent = parent->next)
+			num_parents++;
+
+		if (num_parents <= 2) {

commit-graph.c new file +10 -0

+static int if_packed_commit_add_to_list(const struct object_id *oid,
+					struct packed_git *pack,
+					uint32_t pos,
+					void *data)
+{
+	struct packed_oid_list *list = (struct packed_oid_list*)data;
+	enum object_type type;
+	unsigned long size;
+	void *inner_data;
+	off_t offset = nth_packed_object_offset(pack, pos);

commit-graph.c new file +61 -0

+struct object_id *construct_commit_graph(const char *pack_dir)
+{
+	struct packed_oid_list oids;
+	struct packed_commit_list commits;
+	struct commit_graph_header hdr;
+	struct sha1file *f;
+	int i, count_distinct = 0;
+	struct strbuf tmp_file = STRBUF_INIT;
+	unsigned char final_hash[GIT_MAX_RAWSZ];
+	char *graph_name;
+	int fd;
+	uint32_t chunk_ids[5];
+	uint64_t chunk_offsets[5];
+	int num_long_edges;
+	struct object_id *f_hash;
+	char *fname;
+	struct commit_list *parent;
+
+	oids.num = 0;
+	oids.size = 1024;
+	ALLOC_ARRAY(oids.list, oids.size);
+	for_each_packed_object(if_packed_commit_add_to_list, &oids, 0);
+	QSORT(oids.list, oids.num, commit_compare);
+
+	count_distinct = 1;
+	for (i = 1; i < oids.num; i++) {
+		if (oidcmp(oids.list[i-1], oids.list[i]))
+			count_distinct++;
+	}
+
+	commits.num = 0;
+	commits.size = count_distinct;
+	ALLOC_ARRAY(commits.list, commits.size);
+
+	num_long_edges = 0;
+	for (i = 0; i < oids.num; i++) {
+		int num_parents = 0;
+		if (i > 0 && !oidcmp(oids.list[i-1], oids.list[i]))
+			continue;
+
+		commits.list[commits.num] = lookup_commit(oids.list[i]);
+		parse_commit(commits.list[commits.num]);
+
+		for (parent = commits.list[commits.num]->parents;
+		     parent; parent = parent->next)
+			num_parents++;
+
+		if (num_parents > 2)
+			num_long_edges += num_parents - 1;
+
+		commits.num++;
+	}
+
+	strbuf_addstr(&tmp_file, pack_dir);
+	strbuf_addstr(&tmp_file, "/tmp_graph_XXXXXX");
+
+	fd = git_mkstemp_mode(tmp_file.buf, 0444);
+	if (fd < 0)
+		die_errno("unable to create '%s'", tmp_file.buf);
+
+	graph_name = strbuf_detach(&tmp_file, NULL);

commit-graph.h new file +6 -0

new file mode 100644
index 0000000000..7b3469a7df
@@ -0,0 +1,20 @@
+#ifndef COMMIT_GRAPH_H
+#define COMMIT_GRAPH_H
+
+#include "git-compat-util.h"
+#include "commit.h"
+

Teach Git to write a commit graph file by checking all packed objects to see if they are commits, then store the file in the given pack directory.

Signed-off-by Derrick Stolee <[email protected]>

---
 Makefile       |   1 +
 commit-graph.c | 376 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 commit-graph.h |  20 +++
 3 files changed, 397 insertions(+)
 create mode 100644 commit-graph.c
 create mode 100644 commit-graph.h

commit-graph.c new file +1 -0

new file mode 100644
index 0000000000..db2b7390c7
 
+struct packed_commit_list {

commit-graph.c new file +118 -0

+static int if_packed_commit_add_to_list(const struct object_id *oid,
+					struct packed_git *pack,
+					uint32_t pos,
+					void *data)
+{
+	struct packed_oid_list *list = (struct packed_oid_list*)data;
+	enum object_type type;
+	unsigned long size;
+	void *inner_data;
+	off_t offset = nth_packed_object_offset(pack, pos);
+	inner_data = unpack_entry(pack, offset, &type, &size);
+
+	if (inner_data)
+		free(inner_data);
+
+	if (type != OBJ_COMMIT)
+		return 0;
+
+	ALLOC_GROW(list->list, list->num + 1, list->size);
+	list->list[list->num] = (struct object_id *)malloc(sizeof(struct object_id));
+	oidcpy(list->list[list->num], oid);
+	(list->num)++;
+
+	return 0;
+}
+
+struct object_id *construct_commit_graph(const char *pack_dir)
+{
+	struct packed_oid_list oids;
+	struct packed_commit_list commits;
+	struct commit_graph_header hdr;
+	struct sha1file *f;
+	int i, count_distinct = 0;
+	struct strbuf tmp_file = STRBUF_INIT;
+	unsigned char final_hash[GIT_MAX_RAWSZ];
+	char *graph_name;
+	int fd;
+	uint32_t chunk_ids[5];
+	uint64_t chunk_offsets[5];
+	int num_long_edges;
+	struct object_id *f_hash;
+	char *fname;
+	struct commit_list *parent;
+
+	oids.num = 0;
+	oids.size = 1024;
+	ALLOC_ARRAY(oids.list, oids.size);
+	for_each_packed_object(if_packed_commit_add_to_list, &oids, 0);
+	QSORT(oids.list, oids.num, commit_compare);
+
+	count_distinct = 1;
+	for (i = 1; i < oids.num; i++) {
+		if (oidcmp(oids.list[i-1], oids.list[i]))
+			count_distinct++;
+	}
+
+	commits.num = 0;
+	commits.size = count_distinct;
+	ALLOC_ARRAY(commits.list, commits.size);
+
+	num_long_edges = 0;
+	for (i = 0; i < oids.num; i++) {
+		int num_parents = 0;
+		if (i > 0 && !oidcmp(oids.list[i-1], oids.list[i]))
+			continue;
+
+		commits.list[commits.num] = lookup_commit(oids.list[i]);
+		parse_commit(commits.list[commits.num]);
+
+		for (parent = commits.list[commits.num]->parents;
+		     parent; parent = parent->next)
+			num_parents++;
+
+		if (num_parents > 2)
+			num_long_edges += num_parents - 1;
+
+		commits.num++;
+	}
+
+	strbuf_addstr(&tmp_file, pack_dir);
+	strbuf_addstr(&tmp_file, "/tmp_graph_XXXXXX");
+
+	fd = git_mkstemp_mode(tmp_file.buf, 0444);
+	if (fd < 0)
+		die_errno("unable to create '%s'", tmp_file.buf);
+
+	graph_name = strbuf_detach(&tmp_file, NULL);
+	f = sha1fd(fd, graph_name);
+
+	hdr.graph_signature = htonl(GRAPH_SIGNATURE);
+	hdr.graph_version = GRAPH_VERSION;
+	hdr.hash_version = GRAPH_OID_VERSION;
+	hdr.hash_len = GRAPH_OID_LEN;
+	hdr.num_chunks = 4;
+
+	assert(sizeof(hdr) == 8);
+	sha1write(f, &hdr, sizeof(hdr));
+
+	chunk_ids[0] = GRAPH_CHUNKID_OIDFANOUT;
+	chunk_ids[1] = GRAPH_CHUNKID_OIDLOOKUP;
+	chunk_ids[2] = GRAPH_CHUNKID_DATA;
+	chunk_ids[3] = GRAPH_CHUNKID_LARGEEDGES;
+	chunk_ids[4] = 0;
+
+	chunk_offsets[0] = sizeof(hdr) + GRAPH_CHUNKLOOKUP_SIZE;
+	chunk_offsets[1] = chunk_offsets[0] + GRAPH_FANOUT_SIZE;
+	chunk_offsets[2] = chunk_offsets[1] + GRAPH_OID_LEN * commits.num;
+	chunk_offsets[3] = chunk_offsets[2] + (GRAPH_OID_LEN + 16) * commits.num;
+	chunk_offsets[4] = chunk_offsets[3] + 4 * num_long_edges;
+
+	for (i = 0; i <= hdr.num_chunks; i++) {
+		uint32_t chunk_write[3];
+
+		chunk_write[0] = htonl(chunk_ids[i]);
+		chunk_write[1] = htonl(chunk_offsets[i] >> 32);
+		chunk_write[2] = htonl(chunk_offsets[i] & 0xffffffff);
+		sha1write(f, chunk_write, 12);
+	}

commit-graph.c new file +12 -0

+	fname = get_commit_graph_filename_hash(pack_dir, f_hash);
+
+	if (rename(graph_name, fname))
+		die("failed to rename %s to %s", graph_name, fname);
+
+	free(oids.list);
+	oids.size = 0;
+	oids.num = 0;
+
+	return f_hash;
+}
+

commit-graph.h new file +20 -0

new file mode 100644
index 0000000000..7b3469a7df
@@ -0,0 +1,20 @@
+#ifndef COMMIT_GRAPH_H
+#define COMMIT_GRAPH_H
+
+#include "git-compat-util.h"
+#include "commit.h"
+
+extern char* get_commit_graph_filename_hash(const char *pack_dir,
+					    struct object_id *hash);
+
+struct commit_graph_header {
+	uint32_t graph_signature;
+	unsigned char graph_version;
+	unsigned char hash_version;
+	unsigned char hash_len;
+	unsigned char num_chunks;
+};
+
+extern struct object_id *construct_commit_graph(const char *pack_dir);
+
+#endif

Signature · 1 line

2.16.0.15.g9c3cf44.dirty

Teach Git to write a commit graph file by checking all packed objects to see if they are commits, then store the file in the given pack directory.

commit-graph.c new file +3 -0

+
+	return strbuf_detach(&head_path, &len);
+}

Quoted 3 lines

Teach Git to write a commit graph file by checking all packed objects to see if they are commits, then store the file in the given pack directory.

I'm afraid that scanning all packed objects is a bit of a roundabout way to approach this.

In my git repo, with 9 pack files at the moment, i.e. not that big a repo and not that many pack files:

   $ time ./git commit-graph --write --update-head
   4df41a3d1cc408b7ad34bea87b51ec4ccbf4b803

   real    0m27.550s
   user    0m27.113s
   sys     0m0.376s

In comparison, performing a good old revision walk to gather all the info that is written into the graph file:

   $ time git log --all --topo-order --format='%H %T %P %cd' |wc -l
   52954

   real    0m0.903s
   user    0m0.972s
   sys     0m0.058s

commit-graph.c line 46

Quoted 10 lines

commit-graph.c new file +9 -0

+char* get_commit_graph_filename_hash(const char *pack_dir,
+				     struct object_id *hash)
+{
+	size_t len;
+	struct strbuf head_path = STRBUF_INIT;
+	strbuf_addstr(&head_path, pack_dir);
+	strbuf_addstr(&head_path, "/graph-");
+	strbuf_addstr(&head_path, oid_to_hex(hash));
+	strbuf_addstr(&head_path, ".graph");

Nit: this is assembling the path of a graph file, not that of a graph-head, so the strbuf should be renamed accordingly.

Quoted 3 lines

commit-graph.c new file +3 -0

+
+	return strbuf_detach(&head_path, &len);
+}

Quoted 13 lines · SZEDER Gábor

In my git repo, with 9 pack files at the moment, i.e. not that big a repo and not that many pack files:

   $ time ./git commit-graph --write --update-head
   4df41a3d1cc408b7ad34bea87b51ec4ccbf4b803

   real    0m27.550s
   user    0m27.113s
   sys     0m0.376s

In comparison, performing a good old revision walk to gather all the info that is written into the graph file:

Quoted 6 lines

   $ time git log --all --topo-order --format='%H %T %P %cd' |wc -l
   52954

   real    0m0.903s
   user    0m0.972s
   sys     0m0.058s

Two reasons this is in here:

(1) It's easier to get the write implemented this way and add the reachable closure later (which I do).

(2) For GVFS, we want to add all commits that arrived in a "prefetch pack" to the graph even if we do not have a ref that points to the commit yet. We expect many commits to become reachable soon and having them in the graph saves a lot of time in merge-base calculations.

So, (1) is for patch simplicity, and (2) is why I want it to be an option in the final version. See the --stdin-packs argument later for a way to do this incrementally.

I expect almost all users to use the reachable closure method with --stdin-commits (and that's how I will integrate automatic updates with 'fetch', 'repack', and 'gc' in a later patch).

Quoted 31 lines · Derrick Stolee

Quoted 13 lines · SZEDER Gábor

In my git repo, with 9 pack files at the moment, i.e. not that big a repo and not that many pack files:

    $ time ./git commit-graph --write --update-head
    4df41a3d1cc408b7ad34bea87b51ec4ccbf4b803

    real    0m27.550s
    user    0m27.113s
    sys     0m0.376s

In comparison, performing a good old revision walk to gather all the info that is written into the graph file:

Quoted 6 lines

    $ time git log --all --topo-order --format='%H %T %P %cd' |wc -l
    52954

    real    0m0.903s
    user    0m0.972s
    sys     0m0.058s

Two reasons this is in here:

(1) It's easier to get the write implemented this way and add the reachable closure later (which I do).

(2) For GVFS, we want to add all commits that arrived in a "prefetch pack" to the graph even if we do not have a ref that points to the commit yet. We expect many commits to become reachable soon and having them in the graph saves a lot of time in merge-base calculations.

Quoted 7 lines

So, (1) is for patch simplicity, and (2) is why I want it to be an option in the final version. See the --stdin-packs argument later for a way to do this incrementally.

I expect almost all users to use the reachable closure method with --stdin-commits (and that's how I will integrate automatic updates with 'fetch', 'repack', and 'gc' in a later patch).

I see. I was about to ask about the expected use-cases of the '--stdin-packs' option, considering how much slower it is to enumerate all objects in pack files, but run out of time after patch 10.

The run-time using '--stdin-commits' is indeed great:

   $ time { git for-each-ref --format='%(objectname)' refs/heads/ | ./git
     commit-graph --write --update-head --stdin-commits ; }
   82fe9a5cd715ff578f01f7f44e0611d7902d20c8

   real  0m0.985s
   user  0m0.916s
   sys   0m0.024s

Considering the run-time difference, I think in the end it would be a better default for a plain 'git commit-graph --write' to traverse history from all refs, and it should enumerate pack files only if explicitly told so via '--stdin-packs'.

To be clear: I'm not saying that traversing history should already be the default when introducing construct_commit_graph() and '--write'. If enumerating pack files keeps the earlier patches simpler and easier to review, then by all means stick with it, and only change the '--stdin-*'-less behavior near the end of the series, when all the building blocks are already in place (but then mention this in the early commit messages).

I have also noticed a segfault when feeding non-commit object names to '--stdin-commits', i.e. when I run the above command without restricting 'git for-each-ref' to branches and it listed object names of tags as well.

   $ git rev-parse v2.16.1 |./git commit-graph --write --update-head
--stdin-commits
   error: Object eb5fcb24f69e13335cf6a6a1b1d4553fa2b0f202 not a commit
   error: Object eb5fcb24f69e13335cf6a6a1b1d4553fa2b0f202 not a commit
   error: Object eb5fcb24f69e13335cf6a6a1b1d4553fa2b0f202 not a commit
   Segmentation fault

(gdb) bt
#0 __memcpy_avx_unaligned ()

     at ../sysdeps/x86_64/multiarch/memcpy-avx-unaligned.S:126
#1  0x00000000004ea97c in sha1write (f=0x356bbf0, buf=0x4, count=20)
     at csum-file.c:104
#2  0x00000000004d98e1 in write_graph_chunk_data (f=0x356bbf0, hash_len=20,
     commits=0x3508de0, nr_commits=50615) at commit-graph.c:506
#3  0x00000000004da9ca in construct_commit_graph (
     pack_dir=0x8ff360 ".git/objects/pack", pack_indexes=0x0, nr_packs=0,
     commit_hex=0x8ff790, nr_commits=1) at commit-graph.c:818
#4  0x000000000044184e in graph_write () at builtin/commit-graph.c:149
#5  0x0000000000441a8c in cmd_commit_graph (argc=0, argv=0x7fffffffe310,
     prefix=0x0) at builtin/commit-graph.c:224

#6 0x0000000000405a0a in run_builtin (p=0x8ad950 <commands+528>, argc=4,

     argv=0x7fffffffe310) at git.c:346
#7  0x0000000000405ce4 in handle_builtin (argc=4, argv=0x7fffffffe310)
     at git.c:555
#8  0x0000000000405ec8 in run_argv (argcp=0x7fffffffe1cc, argv=0x7fffffffe1c0)
     at git.c:607
#9  0x0000000000406079 in cmd_main (argc=4, argv=0x7fffffffe310) at git.c:684
#10 0x00000000004a85c8 in main (argc=5, argv=0x7fffffffe308)
     at common-main.c:43

Documentation/git-commit-graph.txt +9 -0

+# Current graph structure:
+#
+#      M3
+#     / |\_____
+#    / 10      15
+#   /   |      |
+#  /    9 M2   14
+# |     |/  \  |
+# |     8 M1 | 13

Quoted 8 lines · On Tue, 30 Jan 2018 16:39:34 -0500 Derrick Stolee <[email protected]> wrote:

Documentation/git-commit-graph.txt +0 -0

index c8ea548dfb..3f3790d9a8 100644
@@ -5,3 +5,21 @@ NAME
 ----
 git-commit-graph - Write and verify Git commit graphs (.graph files)
 

Documentation/git-commit-graph.txt NAME · line 12

Quoted 5 lines

Documentation/git-commit-graph.txt +5 -0

+
+SYNOPSIS
+--------
+[verse]
+'git commit-graph' --write <options> [--pack-dir <pack_dir>]

Subcommands (like those in git submodule) generally don't take "--", as far as I know.

It is true for git-submodule and a few others (the minority of commands IIRC) git-tag for example takes subcommands such as --list or --verify.
https://public-inbox.org/git/[email protected]/

Quoted 3 lines · Stefan Beller

It is true for git-submodule and a few others (the minority of commands IIRC) git-tag for example takes subcommands such as --list or --verify.
https://public-inbox.org/git/[email protected]/

Thanks. It refers to an article at gmane, which is not readily accessible unless you use newsreader. The original discussion it refers to appears at:

https://public-inbox.org/git/[email protected]/

for those who are interested.

I am still not sure if it is a good design to add a new command like this series does, though. I would naively have expected that this would be a new pack index format that is produced by pack-objects and index-pack, for example, in which case its maintenance would almost be invisible to end users (i.e. just like how the pack bitmap feature was added to the system).

I don't think pairing this with pack-objects or index-pack is a good direction, because the commit graph is not locked into a packfile the way the bitmap is. In fact, the entire ODB could be replaced independently and the graph is still valid (the commits in the graph may no longer have their paired commits in the ODB due to a GC; you should never navigate to those commits without having a ref pointing to them, so this is not immediately a problem).

This sort of interaction with GC is one reason why I did not include the automatic updates in this patch. The integration with existing maintenance tasks will be worth discussion in its own right. I'd rather demonstrate the value of having a graph (even if it is currently maintained manually) and then follow up with a focus to integrate with repack, gc, etc.

I plan to clean up this patch on Monday given the feedback I received the last two days (Thanks Jonathan and Szeder!). However, if the current builtin design will block merging, then I'll wait until we can find one that works.

The big advantage of your scheme is that you can update the graph index without repacking. The traditional advice has been that you should always do a full repack during a gc (since it gives the most delta opportunities). So metadata like reachability bitmaps were happy to tied to packs, since you're repacking anyway during a gc. But my understanding is that this doesn't really fly with the Windows repository, where it's simply so big that you never obtain a single pack, and just pass around slices of history in pack format.

So I think I'm OK with the direction here of keeping metadata caches separate from the pack storage.

If they're not tied to packs, then I think having a separate builtin like this is the best approach. It gives you a plumbing command to experiment with, and it can easily be called from git-gc.

-Peff

Quoted 9 lines · Jeff King

The big advantage of your scheme is that you can update the graph index without repacking. The traditional advice has been that you should always do a full repack during a gc (since it gives the most delta opportunities). So metadata like reachability bitmaps were happy to tied to packs, since you're repacking anyway during a gc. But my understanding is that this doesn't really fly with the Windows repository, where it's simply so big that you never obtain a single pack, and just pass around slices of history in pack format.

Quoted 2 lines

So I think I'm OK with the direction here of keeping metadata caches separate from the pack storage.

OK. I guess that the topology information surviving repacking is a reason good enough to keep this separate from pack files, and I agree with your "If they're not tied to packs,..." below, too.

Thanks.

Quoted 5 lines

If they're not tied to packs, then I think having a separate builtin like this is the best approach. It gives you a plumbing command to experiment with, and it can easily be called from git-gc.

-Peff

Teach git-commit-graph to write graph files. Create new test script to verify this command succeeds without failure.

Signed-off-by Derrick Stolee <[email protected]>

---
 Documentation/git-commit-graph.txt | 18 +++++++
 builtin/commit-graph.c             | 30 ++++++++++++
 t/t5318-commit-graph.sh            | 96 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 144 insertions(+)
 create mode 100755 t/t5318-commit-graph.sh

Documentation/git-commit-graph.txt +0 -0

index c8ea548dfb..3f3790d9a8 100644

Documentation/git-commit-graph.txt +12 -0

+EXAMPLES
+--------
+
+* Write a commit graph file for the packed commits in your local .git folder.
++
+------------------------------------------------
+$ git commit-graph --write
+------------------------------------------------
+
+GIT
+---
+Part of the linkgit:git[1] suite

t/t5318-commit-graph.sh new file +2 -0

new file mode 100755
index 0000000000..6bcd1cc264
@@ -0,0 +1,96 @@
+#!/bin/sh
+

t/t5318-commit-graph.sh new file +7 -0

+
+test_expect_success 'write graph with no packs' \
+    'git commit-graph --write --pack-dir .'
+
+test_expect_success 'create commits and repack' \
+    'for i in $(test_seq 5)
+     do

t/t5318-commit-graph.sh new file +64 -0

+    'git reset --hard commits/3 &&
+     for i in $(test_seq 6 10)
+     do
+        echo $i >$i.txt &&
+        git add $i.txt &&
+        git commit -m "commit $i" &&
+        git branch commits/$i
+     done &&
+     git reset --hard commits/3 &&
+     for i in $(test_seq 11 15)
+     do
+        echo $i >$i.txt &&
+        git add $i.txt &&
+        git commit -m "commit $i" &&
+        git branch commits/$i
+     done &&
+     git reset --hard commits/7 &&
+     git merge commits/11 &&
+     git branch merge/1 &&
+     git reset --hard commits/8 &&
+     git merge commits/12 &&
+     git branch merge/2 &&
+     git reset --hard commits/5 &&
+     git merge commits/10 commits/15 &&
+     git branch merge/3 &&
+     git repack'
+
+# Current graph structure:
+#
+#      M3
+#     / |\_____
+#    / 10      15
+#   /   |      |
+#  /    9 M2   14
+# |     |/  \  |
+# |     8 M1 | 13
+# |     |/ | \_|
+# 5     7  |   12
+# |     |   \__|
+# 4     6      11
+# |____/______/
+# 3
+# |
+# 2
+# |
+# 1
+
+test_expect_success 'write graph with merges' \
+    'graph2=$(git commit-graph --write) &&
+     test_path_is_file ${packdir}/graph-${graph2}.graph'
+
+test_expect_success 'setup bare repo' \
+    'cd .. &&
+     git clone --bare full bare &&
+     cd bare &&
+     git config core.graph true &&
+     git config pack.threads 1 &&
+     baredir="objects/pack"'
+
+test_expect_success 'write graph in bare repo' \
+    'graphbare=$(git commit-graph --write) &&
+     test_path_is_file ${baredir}/graph-${graphbare}.graph'
+
+test_done

Signature · 1 line

2.16.0.15.g9c3cf44.dirty

Quoted 16 lines

Teach git-commit-graph to write graph files. Create new test script to verify this command succeeds without failure.

Signed-off-by Derrick Stolee <[email protected]>

---
  Documentation/git-commit-graph.txt | 18 +++++++
  builtin/commit-graph.c             | 30 ++++++++++++
  t/t5318-commit-graph.sh            | 96 ++++++++++++++++++++++++++++++++++++++
  3 files changed, 144 insertions(+)

create mode 100755 t/t5318-commit-graph.sh

Documentation/git-commit-graph.txt +0 -0

index c8ea548dfb..3f3790d9a8 100644

Documentation/git-commit-graph.txt NAME · line 13

Quoted 9 lines

Documentation/git-commit-graph.txt +6 -0

@@ -5,3 +5,21 @@ NAME
  ----
  git-commit-graph - Write and verify Git commit graphs (.graph files)
 
+
+SYNOPSIS
+--------
+[verse]
+'git commit-graph' --write <options> [--pack-dir <pack_dir>]
+

What do these options do and what is the command's output? IOW, an 'OPTIONS' section would be nice.

Quoted 20 lines

Documentation/git-commit-graph.txt +12 -0

+EXAMPLES
+--------
+
+* Write a commit graph file for the packed commits in your local .git folder.
++
+------------------------------------------------
+$ git commit-graph --write
+------------------------------------------------
+
+GIT
+---
+Part of the linkgit:git[1] suite

t/t5318-commit-graph.sh new file +2 -0

new file mode 100755
index 0000000000..6bcd1cc264
@@ -0,0 +1,96 @@
+#!/bin/sh
+

t/t5318-commit-graph.sh line 12

Quoted 10 lines

t/t5318-commit-graph.sh new file +10 -0

+test_description='commit graph'
+. ./test-lib.sh
+
+test_expect_success 'setup full repo' \
+    'rm -rf .git &&
+     mkdir full &&
+     cd full &&
+     git init &&
+     git config core.commitgraph true &&
+     git config pack.threads 1 &&

Does this pack.threads=1 make a difference?

t/t5318-commit-graph.sh line 13

Quoted 1 line

t/t5318-commit-graph.sh new file +1 -0

+     packdir=".git/objects/pack"'

We tend to put single quotes around tests like this:

   test_expect_success 'setup full repo' '
         do-this &&
         check-that
   '

This is not a mere style nit: those newlines before and after the test block make the test's output with '--verbose-log' slightly more readable.

Furthermore, we prefer tabs for indentation.

Finally, 'cd'-ing around such that it affects subsequent tests is usually frowned upon. However, in this particular case (going into one repo, doing a bunch of tests there, then going into another repo, and doing another bunch of tests) I think it's better than changing directory in a subshell in every single test.

Quoted 7 lines

t/t5318-commit-graph.sh new file +7 -0

+
+test_expect_success 'write graph with no packs' \
+    'git commit-graph --write --pack-dir .'
+
+test_expect_success 'create commits and repack' \
+    'for i in $(test_seq 5)
+     do

t/t5318-commit-graph.sh line 30

Quoted 10 lines

t/t5318-commit-graph.sh new file +10 -0

+        echo $i >$i.txt &&
+        git add $i.txt &&
+        git commit -m "commit $i" &&
+        git branch commits/$i
+     done &&
+     git repack'
+
+test_expect_success 'write graph' \
+    'graph1=$(git commit-graph --write) &&
+     test_path_is_file ${packdir}/graph-${graph1}.graph'

Style nit: those {} around the variable names are unnecessary, but I see you use them a lot.

t/t5318-commit-graph.sh line 32

Quoted 2 lines

t/t5318-commit-graph.sh new file +2 -0

+
+t_expect_success 'Add more commits' \

This must be test_expect_success.

Quoted 66 lines

t/t5318-commit-graph.sh new file +64 -0

+    'git reset --hard commits/3 &&
+     for i in $(test_seq 6 10)
+     do
+        echo $i >$i.txt &&
+        git add $i.txt &&
+        git commit -m "commit $i" &&
+        git branch commits/$i
+     done &&
+     git reset --hard commits/3 &&
+     for i in $(test_seq 11 15)
+     do
+        echo $i >$i.txt &&
+        git add $i.txt &&
+        git commit -m "commit $i" &&
+        git branch commits/$i
+     done &&
+     git reset --hard commits/7 &&
+     git merge commits/11 &&
+     git branch merge/1 &&
+     git reset --hard commits/8 &&
+     git merge commits/12 &&
+     git branch merge/2 &&
+     git reset --hard commits/5 &&
+     git merge commits/10 commits/15 &&
+     git branch merge/3 &&
+     git repack'
+
+# Current graph structure:
+#
+#      M3
+#     / |\_____
+#    / 10      15
+#   /   |      |
+#  /    9 M2   14
+# |     |/  \  |
+# |     8 M1 | 13
+# |     |/ | \_|
+# 5     7  |   12
+# |     |   \__|
+# 4     6      11
+# |____/______/
+# 3
+# |
+# 2
+# |
+# 1
+
+test_expect_success 'write graph with merges' \
+    'graph2=$(git commit-graph --write) &&
+     test_path_is_file ${packdir}/graph-${graph2}.graph'
+
+test_expect_success 'setup bare repo' \
+    'cd .. &&
+     git clone --bare full bare &&
+     cd bare &&
+     git config core.graph true &&
+     git config pack.threads 1 &&
+     baredir="objects/pack"'
+
+test_expect_success 'write graph in bare repo' \
+    'graphbare=$(git commit-graph --write) &&
+     test_path_is_file ${baredir}/graph-${graphbare}.graph'
+
+test_done

Signature · 1 line

2.16.0.15.g9c3cf44.dirty

t/t5318-commit-graph.sh new file +1 -0

new file mode 100755
index 0000000000..6bcd1cc264
@@ -0,0 +1,96 @@
+#!/bin/sh

t/t5318-commit-graph.sh new file +2 -0

+     git config pack.threads 1 &&
+     baredir="objects/pack"'

Teach git-commit-graph to read commit graph files and summarize their contents.

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

Signed-off-by Derrick Stolee <[email protected]>

---
 Documentation/git-commit-graph.txt |   7 ++
 builtin/commit-graph.c             |  55 +++++++++++++++
 commit-graph.c                     | 138 ++++++++++++++++++++++++++++++++++++-
 commit-graph.h                     |  25 +++++++
 t/t5318-commit-graph.sh            |  28 ++++++--
 5 files changed, 247 insertions(+), 6 deletions(-)

Documentation/git-commit-graph.txt +0 -0

index 3f3790d9a8..09aeaf6c82 100644

Documentation/git-commit-graph.txt +6 -0

 EXAMPLES
 --------

@@ -20,6 +21,12 @@ EXAMPLES
 $ git commit-graph --write
 ------------------------------------------------
 
+* Read basic information from a graph file.
++
+------------------------------------------------
+$ git commit-graph --read --graph-hash=<hash>
+------------------------------------------------
+
 GIT
 ---
 Part of the linkgit:git[1] suite

builtin/commit-graph.c +0 -0

index 7affd512f1..218740b1f8 100644

builtin/commit-graph.c +71 -0

+{
+	if (g->graph_fd < 0)
+		return 0;
+
+	munmap((void *)g->data, g->data_len);
+	g->data = 0;
+
+	close(g->graph_fd);
+	g->graph_fd = -1;
+
+	return 1;
+}
+
+static void free_commit_graph(struct commit_graph **g)
+{
+	if (!g || !*g)
+		return;
+
+	close_commit_graph(*g);
+
+	free(*g);
+	*g = NULL;
+}
+
+struct commit_graph *load_commit_graph_one(const char *graph_file, const char *pack_dir)
+{
+	void *graph_map;
+	const unsigned char *data;
+	struct commit_graph_header *hdr;
+	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;
+
+	if (fd < 0)
+		return 0;
+	if (fstat(fd, &st)) {
+		close(fd);
+		return 0;
+	}
+	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;
+
+	hdr = graph_map;
+	if (ntohl(hdr->graph_signature) != GRAPH_SIGNATURE) {
+		uint32_t signature = ntohl(hdr->graph_signature);
+		munmap(graph_map, graph_size);
+		close(fd);
+		die("graph signature %X does not match signature %X",
+			signature, GRAPH_SIGNATURE);
+	}
+	if (hdr->graph_version != GRAPH_VERSION) {
+		unsigned char version = hdr->graph_version;
+		munmap(graph_map, graph_size);
+		close(fd);
+		die("graph version %X does not match version %X",
+			version, GRAPH_VERSION);
+	}
+
+	graph = alloc_commit_graph(strlen(pack_dir) + 1);
+
+	graph->hdr = hdr;

builtin/commit-graph.c +45 -0

+		uint64_t chunk_offset = (chunk_offset1 << 32) | chunk_offset2;
+
+		if (chunk_offset > graph_size - GIT_MAX_RAWSZ)
+			die("improper chunk offset %08x%08x", (uint32_t)(chunk_offset >> 32),
+			    (uint32_t)chunk_offset);
+
+		switch (chunk_id) {
+			case GRAPH_CHUNKID_OIDFANOUT:
+				graph->chunk_oid_fanout = data + chunk_offset;
+				break;
+
+			case GRAPH_CHUNKID_OIDLOOKUP:
+				graph->chunk_oid_lookup = data + chunk_offset;
+				break;
+
+			case GRAPH_CHUNKID_DATA:
+				graph->chunk_commit_data = data + chunk_offset;
+				break;
+
+			case GRAPH_CHUNKID_LARGEEDGES:
+				graph->chunk_large_edges = data + chunk_offset;
+				break;
+
+			case 0:
+				break;
+
+			default:
+				free_commit_graph(&graph);
+				die("unrecognized graph chunk id: %08x", chunk_id);
+		}
+
+		if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)
+		{
+			graph->num_commits = (chunk_offset - last_chunk_offset)
+					     / hdr->hash_len;
+		}
+
+		last_chunk_id = chunk_id;
+		last_chunk_offset = chunk_offset;
+	}
+
+	strcpy(graph->pack_dir, pack_dir);
+	return graph;
+}
+
 static void write_graph_chunk_fanout(struct sha1file *f,
 				     struct commit **commits,
 				     int nr_commits)

builtin/commit-graph.c +0 -0

 	fname = get_commit_graph_filename_hash(pack_dir, f_hash);
 
 	if (rename(graph_name, fname))

commit-graph.h +25 -0

index 7b3469a7df..e046ae575c 100644
@@ -15,6 +15,31 @@ struct commit_graph_header {
 	unsigned char num_chunks;
 };
 
+extern struct commit_graph {
+	int graph_fd;
+
+	const unsigned char *data;
+	size_t data_len;
+
+	const struct commit_graph_header *hdr;
+
+	struct object_id oid;
+
+	uint32_t num_commits;
+
+	const unsigned char *chunk_oid_fanout;
+	const unsigned char *chunk_oid_lookup;
+	const unsigned char *chunk_commit_data;
+	const unsigned char *chunk_large_edges;
+
+	/* something like ".git/objects/pack" */
+	char pack_dir[FLEX_ARRAY]; /* more */
+} *commit_graph;
+
+extern int close_commit_graph(struct commit_graph *g);
+
+extern struct commit_graph *load_commit_graph_one(const char *graph_file, const char *pack_dir);
+
 extern struct object_id *construct_commit_graph(const char *pack_dir);
 
 #endif

t/t5318-commit-graph.sh +0 -0

index 6bcd1cc264..da565624e3 100755
@@ -25,11 +25,23 @@ test_expect_success 'create commits and repack' \
      done &&

t/t5318-commit-graph.sh +4 -1

     'git reset --hard commits/3 &&
      for i in $(test_seq 6 10)
      do

@@ -79,7 +91,10 @@ t_expect_success 'Add more commits' \
 
 test_expect_success 'write graph with merges' \
     'graph2=$(git commit-graph --write) &&
-     test_path_is_file ${packdir}/graph-${graph2}.graph'
+     test_path_is_file ${packdir}/graph-${graph2}.graph &&
+     git commit-graph --read --graph-hash=${graph2} >output &&
+     _graph_read_expect "18" "${packdir}" &&
+     cmp expect output'
 
 test_expect_success 'setup bare repo' \
     'cd .. &&

t/t5318-commit-graph.sh +4 -1

 test_expect_success 'write graph in bare repo' \
     'graphbare=$(git commit-graph --write) &&
-     test_path_is_file ${baredir}/graph-${graphbare}.graph'
+     test_path_is_file ${baredir}/graph-${graphbare}.graph &&
+     git commit-graph --read --graph-hash=${graphbare} >output &&
+     _graph_read_expect "18" "${baredir}" &&
+     cmp expect output'
 
 test_done

Signature · 1 line

2.16.0.15.g9c3cf44.dirty

Teach git-commit-graph to read commit graph files and summarize their contents.

Quoted 1 line · On Tue, 30 Jan 2018 16:39:35 -0500 Derrick Stolee <[email protected]> wrote:

Teach git-commit-graph to read commit graph files and summarize their contents.

One overall question - is the "read" command meant to be a command used by the end user, or is it here just to test that some aspects of reading works? If the former, I'm not sure how useful it is. And if the latter, I think that it is more useful to just implementing something that reads it, then make the 11/14 change (modifying parse_commit_gently) and include a perf test to show that your commit graph reading is both correct and (performance-)effective.

It is possible to have multiple commit graph files in a pack directory, but only one is important at a time. Use a 'graph_head' file to point to the important file.

Teach git-commit-graph to write 'graph_head' upon
writing a new commit graph file.

Signed-off-by Derrick Stolee <[email protected]>

---
 Documentation/git-commit-graph.txt | 34 ++++++++++++++++++++++++++++++++++
 builtin/commit-graph.c             | 38 +++++++++++++++++++++++++++++++++++---
 commit-graph.c                     | 25 +++++++++++++++++++++++++
 commit-graph.h                     |  2 ++
 t/t5318-commit-graph.sh            | 12 ++++++++++--
 5 files changed, 106 insertions(+), 5 deletions(-)

Documentation/git-commit-graph.txt +0 -0

index 09aeaf6c82..99ced16ddc 100644

Documentation/git-commit-graph.txt +13 -0

 EXAMPLES
 --------
 
+* Output the hash of the graph file pointed to by <dir>/graph-head.
++
+------------------------------------------------
+$ git commit-graph --pack-dir=<dir>
+------------------------------------------------
+
 * Write a commit graph file for the packed commits in your local .git folder.
 +
 ------------------------------------------------
 $ git commit-graph --write
 ------------------------------------------------
 
+* Write a graph file for the packed commits in your local .git folder,
+* and update graph-head.
++
+------------------------------------------------
+$ git commit-graph --write --update-head
+------------------------------------------------
+
 * Read basic information from a graph file.
 +
 ------------------------------------------------

builtin/commit-graph.c +6 -3

index 218740b1f8..d73cbc907d 100644
@@ -11,7 +11,7 @@
 static char const * const builtin_commit_graph_usage[] = {
 	N_("git commit-graph [--pack-dir <packdir>]"),
 	N_("git commit-graph --read [--graph-hash=<hash>]"),
-	N_("git commit-graph --write [--pack-dir <packdir>]"),
+	N_("git commit-graph --write [--pack-dir <packdir>] [--update-head]"),
 	NULL
 };
 

@@ -20,6 +20,9 @@ static struct opts_commit_graph {
 	int read;
 	const char *graph_hash;
 	int write;
+	int update_head;
+	int has_existing;
+	struct object_id old_graph_hash;
 } opts;
 
 static int graph_read(void)

@@ -30,8 +33,8 @@ static int graph_read(void)
 
 	if (opts.graph_hash && strlen(opts.graph_hash) == GIT_MAX_HEXSZ)
 		get_oid_hex(opts.graph_hash, &graph_hash);
-	else
-		die("no graph hash specified");
+	else if (!get_graph_head_hash(opts.pack_dir, &graph_hash))
+		die("no graph-head exists");
 
 	graph_file = get_commit_graph_filename_hash(opts.pack_dir, &graph_hash);
 	graph = load_commit_graph_one(graph_file, opts.pack_dir);

@@ -62,10 +65,33 @@ static int graph_read(void)
 	return 0;
 }

builtin/commit-graph.c +3 -0

+
 	if (graph_hash)
 		printf("%s\n", oid_to_hex(graph_hash));
 

@@ -83,6 +109,8 @@ int cmd_commit_graph(int argc, const char **argv, const char *prefix)
 			N_("read graph file")),
 		OPT_BOOL('w', "write", &opts.write,
 			N_("write commit graph file")),
+		OPT_BOOL('u', "update-head", &opts.update_head,
+			N_("update graph-head to written graph file")),
 		{ OPTION_STRING, 'H', "graph-hash", &opts.graph_hash,
 			N_("hash"),
 			N_("A hash for a specific graph file in the pack-dir."),

@@ -109,10 +137,14 @@ int cmd_commit_graph(int argc, const char **argv, const char *prefix)
 		opts.pack_dir = strbuf_detach(&path, NULL);
 	}

builtin/commit-graph.c +0 -0

 	return 0;
 }

commit-graph.c +25 -0

index 622a650259..764e016ddb 100644
@@ -35,6 +35,31 @@
 #define GRAPH_MIN_SIZE (GRAPH_CHUNKLOOKUP_SIZE + GRAPH_FANOUT_SIZE + \
 			GRAPH_OID_LEN + sizeof(struct commit_graph_header))
 
+struct object_id *get_graph_head_hash(const char *pack_dir, struct object_id *hash)
+{
+	struct strbuf head_filename = STRBUF_INIT;
+	char hex[GIT_MAX_HEXSZ + 1];
+	FILE *f;
+
+	strbuf_addstr(&head_filename, pack_dir);
+	strbuf_addstr(&head_filename, "/graph-head");
+
+	f = fopen(head_filename.buf, "r");
+	strbuf_release(&head_filename);
+
+	if (!f)
+		return 0;
+
+	if (!fgets(hex, sizeof(hex), f))
+		die("failed to read graph-head");
+
+	fclose(f);
+
+	if (get_oid_hex(hex, hash))
+		return 0;
+	return hash;
+}
+
 char* get_commit_graph_filename_hash(const char *pack_dir,
 				     struct object_id *hash)
 {

commit-graph.h +2 -0

index e046ae575c..43eb0aec84 100644
@@ -4,6 +4,8 @@
 #include "git-compat-util.h"
 #include "commit.h"
 
+extern struct object_id *get_graph_head_hash(const char *pack_dir,
+					     struct object_id *hash);
 extern char* get_commit_graph_filename_hash(const char *pack_dir,
 					    struct object_id *hash);
 

t/t5318-commit-graph.sh +3 -1

index da565624e3..d1a23bcdaf 100755
@@ -13,7 +13,8 @@ test_expect_success 'setup full repo' \
      packdir=".git/objects/pack"'
 
 test_expect_success 'write graph with no packs' \
-    'git commit-graph --write --pack-dir .'
+    'git commit-graph --write --pack-dir . &&
+     test_path_is_missing graph-head'
 
 test_expect_success 'create commits and repack' \
     'for i in $(test_seq 5)

@@ -37,6 +38,7 @@ EOF
 test_expect_success 'write graph' \
     'graph1=$(git commit-graph --write) &&
      test_path_is_file ${packdir}/graph-${graph1}.graph &&
+     test_path_is_missing ${packdir}/graph-head &&
      git commit-graph --read --graph-hash=${graph1} >output &&
      _graph_read_expect "5" "${packdir}" &&
      cmp expect output'

t/t5318-commit-graph.sh +0 -0

      git commit-graph --read --graph-hash=${graphbare} >output &&
      _graph_read_expect "18" "${baredir}" &&
      cmp expect output'

Signature · 1 line

2.16.0.15.g9c3cf44.dirty

Quoted 3 lines

It is possible to have multiple commit graph files in a pack directory, but only one is important at a time. Use a 'graph_head' file to point to the important file.

This implies that all those other files are ignored, right?

Quoted 18 lines

Teach git-commit-graph to write 'graph_head' upon
writing a new commit graph file.

Signed-off-by Derrick Stolee <[email protected]>

---
  Documentation/git-commit-graph.txt | 34 ++++++++++++++++++++++++++++++++++
  builtin/commit-graph.c             | 38 +++++++++++++++++++++++++++++++++++---
  commit-graph.c                     | 25 +++++++++++++++++++++++++
  commit-graph.h                     |  2 ++
  t/t5318-commit-graph.sh            | 12 ++++++++++--
  5 files changed, 106 insertions(+), 5 deletions(-)

Documentation/git-commit-graph.txt +0 -0

index 09aeaf6c82..99ced16ddc 100644

Documentation/git-commit-graph.txt SYNOPSIS · line 16

Quoted 5 lines

Documentation/git-commit-graph.txt +2 -0

@@ -12,15 +12,49 @@ SYNOPSIS
  'git commit-graph' --write <options> [--pack-dir <pack_dir>]
  'git commit-graph' --read <options> [--pack-dir <pack_dir>]
 
+OPTIONS
+-------

Oh, look, the 'OPTIONS' section I missed in the previous patches! ;)

This should be split up and squashed into the previous patches where the individual --options are first mentioned.

Documentation/git-commit-graph.txt SYNOPSIS · line 23

Quoted 7 lines

Documentation/git-commit-graph.txt +7 -0

+--pack-dir::
+	Use given directory for the location of packfiles, graph-head,
+	and graph files.
+
+--read::
+	Read a graph file given by the graph-head file and output basic
+	details about the graph file. (Cannot be combined with --write.)

From the output of 'git commit-graph --read' it seems that it's not a
generally useful option to the user. Perhaps it should be mentioned that it's only intended as a debugging aid? Or maybe it doesn't really matter, because eventually this command will become irrelevant, as other commands (clone, fetch, gc) will invoke it automagically...

Documentation/git-commit-graph.txt SYNOPSIS · line 30

Quoted 7 lines

Documentation/git-commit-graph.txt +6 -0

+--graph-id::
+	When used with --read, consider the graph file graph-<oid>.graph.
+
+--write::
+	Write a new graph file to the pack directory. (Cannot be combined
+	with --read.)

I think this should also mention that it prints the generated graph file's checksum.

Documentation/git-commit-graph.txt SYNOPSIS · line 34

Quoted 4 lines

Documentation/git-commit-graph.txt +4 -0

+
+--update-head::
+	When used with --write, update the graph-head file to point to
+	the written graph file.

So it should be used with '--write', noted.

Quoted 62 lines

Documentation/git-commit-graph.txt +13 -0

  EXAMPLES
  --------
 
+* Output the hash of the graph file pointed to by <dir>/graph-head.
++
+------------------------------------------------
+$ git commit-graph --pack-dir=<dir>
+------------------------------------------------
+
  * Write a commit graph file for the packed commits in your local .git folder.
  +
  ------------------------------------------------
  $ git commit-graph --write
  ------------------------------------------------
 
+* Write a graph file for the packed commits in your local .git folder,
+* and update graph-head.
++
+------------------------------------------------
+$ git commit-graph --write --update-head
+------------------------------------------------
+
  * Read basic information from a graph file.
  +
  ------------------------------------------------

builtin/commit-graph.c +6 -3

index 218740b1f8..d73cbc907d 100644
@@ -11,7 +11,7 @@
  static char const * const builtin_commit_graph_usage[] = {
  	N_("git commit-graph [--pack-dir <packdir>]"),
  	N_("git commit-graph --read [--graph-hash=<hash>]"),
-	N_("git commit-graph --write [--pack-dir <packdir>]"),
+	N_("git commit-graph --write [--pack-dir <packdir>] [--update-head]"),
  	NULL
  };
 

@@ -20,6 +20,9 @@ static struct opts_commit_graph {
  	int read;
  	const char *graph_hash;
  	int write;
+	int update_head;
+	int has_existing;
+	struct object_id old_graph_hash;
  } opts;
 
  static int graph_read(void)

@@ -30,8 +33,8 @@ static int graph_read(void)
 
  	if (opts.graph_hash && strlen(opts.graph_hash) == GIT_MAX_HEXSZ)
  		get_oid_hex(opts.graph_hash, &graph_hash);
-	else
-		die("no graph hash specified");
+	else if (!get_graph_head_hash(opts.pack_dir, &graph_hash))
+		die("no graph-head exists");
 
  	graph_file = get_commit_graph_filename_hash(opts.pack_dir, &graph_hash);
  	graph = load_commit_graph_one(graph_file, opts.pack_dir);

@@ -62,10 +65,33 @@ static int graph_read(void)
  	return 0;
  }

builtin/commit-graph.c static int graph_read(void) · line 76

Quoted 10 lines

builtin/commit-graph.c +9 -0

 
+static void update_head_file(const char *pack_dir, const struct object_id *graph_hash)
+{
+	struct strbuf head_path = STRBUF_INIT;
+	int fd;
+	struct lock_file lk = LOCK_INIT;
+
+	strbuf_addstr(&head_path, pack_dir);
+	strbuf_addstr(&head_path, "/");
+	strbuf_addstr(&head_path, "graph-head");

strbuf_addstr(&head_path, "/graph-head"); ?

builtin/commit-graph.c static int graph_read(void) · line 85

Quoted 9 lines

builtin/commit-graph.c +9 -0

+
+	fd = hold_lock_file_for_update(&lk, head_path.buf, LOCK_DIE_ON_ERROR);
+	strbuf_release(&head_path);
+
+	if (fd < 0)
+		die_errno("unable to open graph-head");
+
+	write_in_full(fd, oid_to_hex(graph_hash), GIT_MAX_HEXSZ);
+	commit_lock_file(&lk);

The new graph-head file will be writable. All other files in .git/objects/pack are created read-only, including graph files. Just pointing it out, but I don't think it's a bit deal; other than consistency with the permissions of other files I don't have any argument for making it read-only.

t/t5318-commit-graph.sh +2 -0

+     echo ${graphbare} >expect &&
+     cmp -n 40 expect ${baredir}/graph-head &&
      git commit-graph --read --graph-hash=${graphbare} >output &&
      _graph_read_expect "18" "${baredir}" &&
      cmp expect output'

Teach Git to delete the current 'graph_head' file and the commit graph it references.

This is a good safety valve if somehow the file is corrupted and needs to be recalculated. Since the commit graph is a summary of contents already in the ODB, it can be regenerated.

Signed-off-by Derrick Stolee <[email protected]>

---
 Documentation/git-commit-graph.txt | 16 ++++++++++++++--
 builtin/commit-graph.c             | 32 +++++++++++++++++++++++++++++++-
 t/t5318-commit-graph.sh            |  7 ++++++-
 3 files changed, 51 insertions(+), 4 deletions(-)

Documentation/git-commit-graph.txt +5 -1

index 99ced16ddc..33d6567f11 100644
@@ -11,6 +11,7 @@ SYNOPSIS
 [verse]
 'git commit-graph' --write <options> [--pack-dir <pack_dir>]
 'git commit-graph' --read <options> [--pack-dir <pack_dir>]
+'git commit-graph' --clear [--pack-dir <pack_dir>]
 
 OPTIONS
 -------

@@ -18,16 +19,21 @@ OPTIONS
 	Use given directory for the location of packfiles, graph-head,
 	and graph files.
 
+--clear::
+	Delete the graph-head file and the graph file it references.
+	(Cannot be combined with --read or --write.)
+
 --read::
 	Read a graph file given by the graph-head file and output basic
-	details about the graph file. (Cannot be combined with --write.)

Documentation/git-commit-graph.txt +6 -0

 --update-head::
 	When used with --write, update the graph-head file to point to

@@ -61,6 +67,12 @@ $ git commit-graph --write --update-head
 $ git commit-graph --read --graph-hash=<hash>
 ------------------------------------------------
 
+* Delete <dir>/graph-head and the file it references.
++
+------------------------------------------------
+$ git commit-graph --clear --pack-dir=<dir>
+------------------------------------------------
+
 GIT
 ---
 Part of the linkgit:git[1] suite

builtin/commit-graph.c +3 -0

index d73cbc907d..4970dec133 100644
@@ -10,6 +10,7 @@
 
 static char const * const builtin_commit_graph_usage[] = {
 	N_("git commit-graph [--pack-dir <packdir>]"),
+	N_("git commit-graph --clear [--pack-dir <packdir>]"),
 	N_("git commit-graph --read [--graph-hash=<hash>]"),
 	N_("git commit-graph --write [--pack-dir <packdir>] [--update-head]"),
 	NULL

@@ -17,6 +18,7 @@ static char const * const builtin_commit_graph_usage[] = {
 
 static struct opts_commit_graph {
 	const char *pack_dir;
+	int clear;
 	int read;
 	const char *graph_hash;
 	int write;

@@ -25,6 +27,30 @@ static struct opts_commit_graph {
 	struct object_id old_graph_hash;
 } opts;
 
+static int graph_clear(void)

builtin/commit-graph.c +18 -1

+	if (remove_path(head_path.buf))
+		die("failed to remove path %s", head_path.buf);
+	strbuf_release(&head_path);
+
+	old_path = get_commit_graph_filename_hash(opts.pack_dir,
+						  &opts.old_graph_hash);
+	if (remove_path(old_path))
+		die("failed to remove path %s", old_path);
+	free(old_path);
+
+	return 0;
+}
+
 static int graph_read(void)
 {
 	struct object_id graph_hash;

@@ -105,6 +131,8 @@ int cmd_commit_graph(int argc, const char **argv, const char *prefix)
 		{ OPTION_STRING, 'p', "pack-dir", &opts.pack_dir,
 			N_("dir"),
 			N_("The pack directory to store the graph") },
+		OPT_BOOL('c', "clear", &opts.clear,
+			N_("clear graph file and graph-head")),
 		OPT_BOOL('r', "read", &opts.read,
 			N_("read graph file")),
 		OPT_BOOL('w', "write", &opts.write,

@@ -126,7 +154,7 @@ int cmd_commit_graph(int argc, const char **argv, const char *prefix)
 			     builtin_commit_graph_options,
 			     builtin_commit_graph_usage, 0);
 
-	if (opts.write + opts.read > 1)
+	if (opts.write + opts.read + opts.clear > 1)
 		usage_with_options(builtin_commit_graph_usage,
 				   builtin_commit_graph_options);
 

@@ -139,6 +167,8 @@ int cmd_commit_graph(int argc, const char **argv, const char *prefix)
 
 	opts.has_existing = !!get_graph_head_hash(opts.pack_dir, &opts.old_graph_hash);
 
+	if (opts.clear)
+		return graph_clear();
 	if (opts.read)
 		return graph_read();
 	if (opts.write)

t/t5318-commit-graph.sh +5 -0

index d1a23bcdaf..6e3b62b754 100755
@@ -101,6 +101,11 @@ test_expect_success 'write graph with merges' \
      _graph_read_expect "18" "${packdir}" &&
      cmp expect output'
 
+test_expect_success 'clear graph' \
+    'git commit-graph --clear &&
+     test_path_is_missing ${packdir}/graph-${graph2}.graph &&
+     test_path_is_missing ${packdir}/graph-head'
+
 test_expect_success 'setup bare repo' \
     'cd .. &&
      git clone --bare full bare &&

t/t5318-commit-graph.sh +0 -0

      test_path_is_file ${baredir}/graph-${graphbare}.graph &&
      test_path_is_file ${baredir}/graph-head &&
      echo ${graphbare} >expect &&

Signature · 1 line

2.16.0.15.g9c3cf44.dirty

Teach git-commit-graph to delete the graph previously referenced by 'graph_head' when writing a new graph file and updating 'graph_head'. This prevents data creep by storing a list of useless graphs. Be careful to not delete the graph if the file did not change.

builtin/commit-graph.c +11 -0

index 4970dec133..766f09e6fc 100644
@@ -121,6 +122,17 @@ static int graph_write(void)
 	if (graph_hash)
 		printf("%s\n", oid_to_hex(graph_hash));
 
+
+	if (opts.delete_expired && opts.update_head && opts.has_existing &&
+	    oidcmp(graph_hash, &opts.old_graph_hash)) {
+		char *old_path = get_commit_graph_filename_hash(opts.pack_dir,
+								&opts.old_graph_hash);
+		if (remove_path(old_path))
+			die("failed to remove path %s", old_path);
+
+		free(old_path);
+	}
+
 	free(graph_hash);
 	return 0;
 }

t/t5318-commit-graph.sh +6 -1

+     git commit-graph --read --graph-hash=${graph4} >output &&
+     _graph_read_expect "23" "${packdir}" &&
+     cmp expect output'
+
 test_expect_success 'clear graph' \
     'git commit-graph --clear &&
      test_path_is_missing ${packdir}/graph-${graph2}.graph &&
+     test_path_is_file ${packdir}/graph-${graph1}.graph &&
      test_path_is_missing ${packdir}/graph-head'
 
 test_expect_success 'setup bare repo' \

@@ -121,7 +185,7 @@ test_expect_success 'write graph in bare repo' \
      echo ${graphbare} >expect &&
      cmp -n 40 expect ${baredir}/graph-head &&
      git commit-graph --read --graph-hash=${graphbare} >output &&
-     _graph_read_expect "18" "${baredir}" &&
+     _graph_read_expect "23" "${baredir}" &&
      cmp expect output'
 
 test_done

Signature · 1 line

2.16.0.15.g9c3cf44.dirty

Documentation/config.txt +2 -0

+	Enable git commit graph feature. Allows reading from .graph files.
+
 core.sparseCheckout::
 	Enable "sparse checkout" feature. See section "Sparse checkout" in
 	linkgit:git-read-tree[1] for more information.

cache.h +0 -0

index d8b975a571..e50e447a4f 100644

cache.h +0 -0

 extern int precomposed_unicode;
 extern int protect_hfs;
 extern int protect_ntfs;

config.c +5 -0

index e617c2018d..99153fcfdb 100644
@@ -1223,6 +1223,11 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.commitgraph")) {
+		core_commitgraph = git_config_bool(var, value);
+		return 0;
+	}
+
 	if (!strcmp(var, "core.sparsecheckout")) {
 		core_apply_sparse_checkout = git_config_bool(var, value);
 		return 0;

environment.c +0 -0

index 63ac38a46f..faa4323cc5 100644

The commit graph feature is controlled by the new core.commitgraph config setting. This defaults to 0, so the feature is opt-in.

The intention of core.commitgraph is that a user can always stop checking for or parsing commit graph files if core.commitgraph=0.

Signed-off-by Derrick Stolee <[email protected]>

---
 Documentation/config.txt | 3 +++
 cache.h                  | 1 +
 config.c                 | 5 +++++
 environment.c            | 1 +
 4 files changed, 10 insertions(+)