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

Re: [PATCH v2 11/14] commit: integrate commit graph with commit parsing

From
JTJonathan Tan <jonathantanmy@google.com>
Date
Feb 2, 2018, 01:51 UTC
Message-ID
<20180201175151.89555950582a2e6c5279849a@google.com>
In-Reply-To
<1517348383-112294-12-git-send-email-dstolee@microsoft.com>

On Tue, 30 Jan 2018 16:39:40 -0500 Derrick Stolee <stolee@gmail.com> wrote:

> +/* global storage */
> +struct commit_graph *commit_graph = 0;
NULL, not 0.
Show 29 quoted lines
> +static int bsearch_graph(struct commit_graph *g, struct object_id *oid, uint32_t *pos)
> +{
> +	uint32_t last, first = 0;
> +
> +	if (oid->hash[0])
> +		first = ntohl(*(uint32_t*)(g->chunk_oid_fanout + 4 * (oid->hash[0] - 1)));
> +	last = ntohl(*(uint32_t*)(g->chunk_oid_fanout + 4 * oid->hash[0]));
> +
> +	while (first < last) {
> +		uint32_t mid = first + (last - first) / 2;
> +		const unsigned char *current;
> +		int cmp;
> +
> +		current = g->chunk_oid_lookup + g->hdr->hash_len * mid;
> +		cmp = hashcmp(oid->hash, current);
> +		if (!cmp) {
> +			*pos = mid;
> +			return 1;
> +		}
> +		if (cmp > 0) {
> +			first = mid + 1;
> +			continue;
> +		}
> +		last = mid;
> +	}
> +
> +	*pos = first;
> +	return 0;
> +}

This would be better in sha1-lookup.c, something like the reverse of commit f1068efefe6d ("sha1_file: drop experimental GIT_USE_LOOKUP search", 2017-08-09), except that it can be done using a simple binary search.

Show 64 quoted lines
> +static int full_parse_commit(struct commit *item, struct commit_graph *g,
> +			     uint32_t pos, const unsigned char *commit_data)
> +{
> +	struct object_id oid;
> +	struct commit *new_parent;
> +	uint32_t new_parent_pos;
> +	uint32_t *parent_data_ptr;
> +	uint64_t date_low, date_high;
> +	struct commit_list **pptr;
> +
> +	item->object.parsed = 1;
> +	item->graph_pos = pos;
> +
> +	hashcpy(oid.hash, commit_data);
> +	item->tree = lookup_tree(&oid);
> +
> +	date_high = ntohl(*(uint32_t*)(commit_data + g->hdr->hash_len + 8)) & 0x3;
> +	date_low = ntohl(*(uint32_t*)(commit_data + g->hdr->hash_len + 12));
> +	item->date = (timestamp_t)((date_high << 32) | date_low);
> +
> +	pptr = &item->parents;
> +
> +	new_parent_pos = ntohl(*(uint32_t*)(commit_data + g->hdr->hash_len));
> +	if (new_parent_pos == GRAPH_PARENT_NONE)
> +		return 1;
> +	get_nth_commit_oid(g, new_parent_pos, &oid);
> +	new_parent = lookup_commit(&oid);
> +	if (new_parent) {
> +		new_parent->graph_pos = new_parent_pos;
> +		pptr = &commit_list_insert(new_parent, pptr)->next;
> +	} else {
> +		die("could not find commit %s", oid_to_hex(&oid));
> +	}
> +
> +	new_parent_pos = ntohl(*(uint32_t*)(commit_data + g->hdr->hash_len + 4));
> +	if (new_parent_pos == GRAPH_PARENT_NONE)
> +		return 1;
> +	if (!(new_parent_pos & GRAPH_LARGE_EDGES_NEEDED)) {
> +		get_nth_commit_oid(g, new_parent_pos, &oid);
> +		new_parent = lookup_commit(&oid);
> +		if (new_parent) {
> +			new_parent->graph_pos = new_parent_pos;
> +			pptr = &commit_list_insert(new_parent, pptr)->next;
> +		} else
> +			die("could not find commit %s", oid_to_hex(&oid));
> +		return 1;
> +	}
> +
> +	parent_data_ptr = (uint32_t*)(g->chunk_large_edges + 4 * (new_parent_pos ^ GRAPH_LARGE_EDGES_NEEDED));
> +	do {
> +		new_parent_pos = ntohl(*parent_data_ptr);
> +
> +		get_nth_commit_oid(g, new_parent_pos & GRAPH_EDGE_LAST_MASK, &oid);
> +		new_parent = lookup_commit(&oid);
> +		if (new_parent) {
> +			new_parent->graph_pos = new_parent_pos & GRAPH_EDGE_LAST_MASK;
> +			pptr = &commit_list_insert(new_parent, pptr)->next;
> +		} else
> +			die("could not find commit %s", oid_to_hex(&oid));
> +		parent_data_ptr++;
> +	} while (!(new_parent_pos & GRAPH_LAST_EDGE));
> +
> +	return 1;
> +}

The part that converts <pointer to parent data> into <struct commit *> seems to be duplicated 3 times. Refactor into a function?

Show 41 quoted lines
> +/**
> + * Fill 'item' to contain all information that would be parsed by parse_commit_buffer.
> + */
> +static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t pos)
> +{
> +	uint32_t new_parent_pos;
> +	uint32_t *parent_data_ptr;
> +	const unsigned char *commit_data = g->chunk_commit_data + (g->hdr->hash_len + 16) * pos;
> +
> +	new_parent_pos = ntohl(*(uint32_t*)(commit_data + g->hdr->hash_len));
> +
> +	if (new_parent_pos == GRAPH_PARENT_MISSING)
> +		return 0;
> +
> +	if (new_parent_pos == GRAPH_PARENT_NONE)
> +		return full_parse_commit(item, g, pos, commit_data);
> +
> +	new_parent_pos = ntohl(*(uint32_t*)(commit_data + g->hdr->hash_len + 4));
> +
> +	if (new_parent_pos == GRAPH_PARENT_MISSING)
> +		return 0;
> +	if (!(new_parent_pos & GRAPH_LARGE_EDGES_NEEDED))
> +		return full_parse_commit(item, g, pos, commit_data);
> +
> +	new_parent_pos = new_parent_pos ^ GRAPH_LARGE_EDGES_NEEDED;
> +
> +	if (new_parent_pos == GRAPH_PARENT_MISSING)
> +		return 0;
> +
> +	parent_data_ptr = (uint32_t*)(g->chunk_large_edges + 4 * new_parent_pos);
> +	do {
> +		new_parent_pos = ntohl(*parent_data_ptr);
> +
> +		if ((new_parent_pos & GRAPH_EDGE_LAST_MASK) == GRAPH_PARENT_MISSING)
> +			return 0;
> +
> +		parent_data_ptr++;
> +	} while (!(new_parent_pos & GRAPH_LAST_EDGE));
> +
> +	return full_parse_commit(item, g, pos, commit_data);
> +}

This function seems to just check for GRAPH_PARENT_MISSING - could that check be folded into full_parse_commit() instead? (Then full_parse_commit can be renamed to fill_commit_in_graph.)

Show 36 quoted lines
> @@ -439,9 +656,24 @@ struct object_id *construct_commit_graph(const char *pack_dir)
>  	char *fname;
>  	struct commit_list *parent;
>  
> +	prepare_commit_graph();
> +
>  	oids.num = 0;
>  	oids.size = 1024;
> +
> +	if (commit_graph && oids.size < commit_graph->num_commits)
> +		oids.size = commit_graph->num_commits;
> +
>  	ALLOC_ARRAY(oids.list, oids.size);
> +
> +	if (commit_graph) {
> +		for (i = 0; i < commit_graph->num_commits; i++) {
> +			oids.list[i] = malloc(sizeof(struct object_id));
> +			get_nth_commit_oid(commit_graph, i, oids.list[i]);
> +		}
> +		oids.num = commit_graph->num_commits;
> +	}
> +
>  	for_each_packed_object(if_packed_commit_add_to_list, &oids, 0);
>  	QSORT(oids.list, oids.num, commit_compare);
>  
> @@ -525,6 +757,11 @@ struct object_id *construct_commit_graph(const char *pack_dir)
>  	hashcpy(f_hash->hash, final_hash);
>  	fname = get_commit_graph_filename_hash(pack_dir, f_hash);
>  
> +	if (commit_graph) {
> +		close_commit_graph(commit_graph);
> +		FREE_AND_NULL(commit_graph);
> +	}
> +
>  	if (rename(graph_name, fname))
>  		die("failed to rename %s to %s", graph_name, fname);

What is the relation of these changes to construct_commit_graph() to the rest of the patch?

Show 37 quoted lines
> diff --git a/commit-graph.h b/commit-graph.h
> index 43eb0aec84..05ddbbe165 100644
> --- a/commit-graph.h
> +++ b/commit-graph.h
> @@ -4,6 +4,18 @@
>  #include "git-compat-util.h"
>  #include "commit.h"
>  
> +/**
> + * Given a commit struct, try to fill the commit struct info, including:
> + *  1. tree object
> + *  2. date
> + *  3. parents.
> + *
> + * Returns 1 if and only if the commit was found in the packed graph.
> + *
> + * See parse_commit_buffer() for the fallback after this call.
> + */
> +extern int parse_commit_in_graph(struct commit *item);
> +
>  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,
> @@ -40,7 +52,13 @@ extern struct 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 commit_graph *load_commit_graph_one(const char *graph_file,
> +						  const char *pack_dir);
> +extern void prepare_commit_graph(void);
> +
> +extern struct object_id *get_nth_commit_oid(struct commit_graph *g,
> +					    uint32_t n,
> +					    struct object_id *oid);
>  
>  extern struct object_id *construct_commit_graph(const char *pack_dir);

This header file now contains functions for reading the commit graph, and functions for writing one. It seems to me that those are (and should be) quite disjoint, so it might be better to separate them into two.

Show 22 quoted lines
> -int parse_commit_gently(struct commit *item, int quiet_on_missing)
> +int parse_commit_internal(struct commit *item, int quiet_on_missing, int check_packed)
>  {
>  	enum object_type type;
>  	void *buffer;
> @@ -385,6 +386,8 @@ int parse_commit_gently(struct commit *item, int quiet_on_missing)
>  		return -1;
>  	if (item->object.parsed)
>  		return 0;
> +	if (check_packed && parse_commit_in_graph(item))
> +		return 0;
>  	buffer = read_sha1_file(item->object.oid.hash, &type, &size);
>  	if (!buffer)
>  		return quiet_on_missing ? -1 :
> @@ -404,6 +407,11 @@ int parse_commit_gently(struct commit *item, int quiet_on_missing)
>  	return ret;
>  }
>  
> +int parse_commit_gently(struct commit *item, int quiet_on_missing)
> +{
> +	return parse_commit_internal(item, quiet_on_missing, 1);
> +}

Are you planning to use parse_commit_internal() from elsewhere? (It doesn't seem to be the case, at least from this patch series.)

Show 11 quoted lines
> diff --git a/log-tree.c b/log-tree.c
> index fca29d4799..156aed4541 100644
> --- a/log-tree.c
> +++ b/log-tree.c
> @@ -659,8 +659,7 @@ void show_log(struct rev_info *opt)
>  		show_mergetag(opt, commit);
>  	}
>  
> -	if (!get_cached_commit_buffer(commit, NULL))
> -		return;
> +	get_commit_buffer(commit, NULL);

This undoes an optimization that I discuss in my e-mail message here [1]. If we decide to do this, it should at least be called out in the commit message.

[1] https://public-inbox.org/git/b88725476d9f13ba4381d85e5fe049f6ef93f621.1506714999.git.jonathantanmy@google.com/
> +_graph_git_two_modes() {
No need for the name to start with an underscore, I think.
> +    git -c core.commitgraph=true $1 >output
> +    git -c core.commitgraph=false $1 >expect
> +    cmp output expect
Use test_cmp.
Show 11 quoted lines
> +}
> +
> +_graph_git_behavior() {
> +    BRANCH=$1
> +    COMPARE=$2
> +    test_expect_success 'check normal git operations' \
> +        '_graph_git_two_modes "log --oneline ${BRANCH}" &&
> +         _graph_git_two_modes "log --topo-order ${BRANCH}" &&
> +         _graph_git_two_modes "branch -vv" &&
> +         _graph_git_two_modes "merge-base -a ${BRANCH} ${COMPARE}"'
> +}

This makes it difficult to debug failing tests, since they're all named the same. Better to just run the commands inline, and wrap the invocations of _graph_git_behavior in an appropriately named test_expect_success.

Previous: Derrick StoleeNext: Derrick Stolee
Message 14 of 146 in “Serialized Git Commit Graph”
  1. 00/14 Serialized Git Commit GraphDerrick Stolee, Jan 30, 2018
  2. 01/14 commit-graph: add format documentDerrick Stolee, Jan 30, 2018
  3. Jonathan TanFeb 1, 2018
  4. 03/14 commit-graph: create git-commit-graph builtinDerrick Stolee, Jan 30, 2018
  5. SZEDER GáborFeb 2, 2018
  6. 06/14 commit-graph: implement git-commit-graph --readDerrick Stolee, Jan 30, 2018
  7. Stefan BellerJan 31, 2018
  8. SZEDER GáborFeb 2, 2018
  9. Jonathan TanFeb 2, 2018
  10. Derrick StoleeFeb 5, 2018
  11. 08/14 commit-graph: implement git-commit-graph --clearDerrick Stolee, Jan 30, 2018
  12. SZEDER GáborFeb 2, 2018
  13. 11/14 commit: integrate commit graph with commit parsingDerrick Stolee, Jan 30, 2018
  14. Jonathan TanFeb 2, 2018
  15. Derrick StoleeFeb 6, 2018
  16. 13/14 commit-graph: close under reachabilityDerrick Stolee, Jan 30, 2018
  17. 09/14 commit-graph: teach git-commit-graph --delete-expiredDerrick Stolee, Jan 30, 2018
  18. SZEDER GáborFeb 2, 2018
  19. 12/14 commit-graph: read only from specific pack-indexesDerrick Stolee, Jan 30, 2018
  20. 14/14 commit-graph: build graph from starting commitsDerrick Stolee, Jan 30, 2018
  21. 10/14 commit-graph: add core.commitgraph settingDerrick Stolee, Jan 30, 2018
  22. Igor DjordjevicJan 31, 2018
  23. SZEDER GáborFeb 2, 2018
  24. 02/14 graph: add commit graph design documentDerrick Stolee, Jan 30, 2018
  25. Stefan BellerJan 31, 2018
  26. 05/14 commit-graph: implement git-commit-graph --writeDerrick Stolee, Jan 30, 2018
  27. Jonathan TanFeb 1, 2018
  28. Stefan BellerFeb 2, 2018
  29. Junio C HamanoFeb 2, 2018
  30. Derrick StoleeFeb 3, 2018
  31. Jeff KingFeb 3, 2018
  32. Junio C HamanoFeb 5, 2018
  33. Derrick StoleeFeb 6, 2018
  34. SZEDER GáborFeb 1, 2018
  35. Derrick StoleeFeb 5, 2018
  36. SZEDER GáborFeb 2, 2018
  37. 07/14 commit-graph: implement git-commit-graph --update-headDerrick Stolee, Jan 30, 2018
  38. SZEDER GáborFeb 2, 2018
  39. Derrick StoleeFeb 5, 2018
  40. SZEDER GáborFeb 2, 2018
  41. 04/14 commit-graph: implement construct_commit_graph()Derrick Stolee, Jan 30, 2018
  42. Jonathan TanFeb 1, 2018
  43. SZEDER GáborFeb 1, 2018
  44. SZEDER GáborFeb 2, 2018
  45. Derrick StoleeFeb 5, 2018
  46. SZEDER GáborFeb 7, 2018
  47. Derrick StoleeFeb 7, 2018
  48. Stefan BellerJan 30, 2018
  49. Stefan BellerFeb 1, 2018
  50. 00/14 Serialized Git Commit GraphDerrick Stolee, Feb 8, 2018
  51. 01/14 commit-graph: add format documentDerrick Stolee, Feb 8, 2018
  52. Junio C HamanoFeb 8, 2018
  53. Derrick StoleeFeb 8, 2018
  54. Junio C HamanoFeb 8, 2018
  55. 03/14 commit-graph: create git-commit-graph builtinDerrick Stolee, Feb 8, 2018
  56. Junio C HamanoFeb 8, 2018
  57. Derrick StoleeFeb 8, 2018
  58. Junio C HamanoFeb 8, 2018
  59. 07/14 commit-graph: update graph-head during writeDerrick Stolee, Feb 8, 2018
  60. Junio C HamanoFeb 12, 2018
  61. Junio C HamanoFeb 12, 2018
  62. Derrick StoleeFeb 12, 2018
  63. Jonathan TanFeb 13, 2018
  64. 10/14 commit-graph: add core.commitGraph settingDerrick Stolee, Feb 8, 2018
  65. 12/14 commit-graph: close under reachabilityDerrick Stolee, Feb 8, 2018
  66. 11/14 commit: integrate commit graph with commit parsingDerrick Stolee, Feb 8, 2018
  67. Jonathan TanFeb 14, 2018
  68. Derrick StoleeFeb 14, 2018
  69. Junio C HamanoFeb 15, 2018
  70. 05/14 commit-graph: implement 'git-commit-graph write'Derrick Stolee, Feb 8, 2018
  71. Jonathan TanFeb 13, 2018
  72. 08/14 commit-graph: implement 'git-commit-graph clear'Derrick Stolee, Feb 8, 2018
  73. Jonathan TanFeb 13, 2018
  74. 09/14 commit-graph: implement --delete-expiredDerrick Stolee, Feb 8, 2018
  75. 13/14 commit-graph: read only from specific pack-indexesDerrick Stolee, Feb 8, 2018
  76. 14/14 commit-graph: build graph from starting commitsDerrick Stolee, Feb 8, 2018
  77. SZEDER GáborFeb 9, 2018
  78. Derrick StoleeFeb 9, 2018
  79. 06/14 commit-graph: implement 'git-commit-graph read'Derrick Stolee, Feb 8, 2018
  80. Junio C HamanoFeb 8, 2018
  81. 02/14 graph: add commit graph design documentDerrick Stolee, Feb 8, 2018
  82. 04/14 commit-graph: implement write_commit_graph()Derrick Stolee, Feb 8, 2018
  83. Junio C HamanoFeb 8, 2018
  84. Junio C HamanoFeb 15, 2018
  85. Derrick StoleeFeb 15, 2018
  86. Derrick StoleeFeb 14, 2018
  87. Stefan BellerFeb 14, 2018
  88. Derrick StoleeFeb 14, 2018
  89. 00/13 Serialized Git Commit GraphDerrick Stolee, Feb 19, 2018
  90. 01/13 commit-graph: add format documentDerrick Stolee, Feb 19, 2018
  91. Junio C HamanoFeb 20, 2018
  92. Stefan BellerFeb 21, 2018
  93. Derrick StoleeFeb 21, 2018
  94. Stefan BellerFeb 21, 2018
  95. Jakub NarebskiMar 30, 2018
  96. Derrick StoleeApr 2, 2018
  97. Jakub NarebskiApr 2, 2018
  98. 03/13 commit-graph: create git-commit-graph builtinDerrick Stolee, Feb 19, 2018
  99. Junio C HamanoFeb 20, 2018
  100. Junio C HamanoFeb 21, 2018
  101. Derrick StoleeFeb 23, 2018
  102. SZEDER GáborFeb 26, 2018
  103. Derrick StoleeFeb 26, 2018
  104. 06/13 commit-graph: implement git commit-graph readDerrick Stolee, Feb 19, 2018
  105. Junio C HamanoFeb 21, 2018
  106. Junio C HamanoFeb 22, 2018
  107. 08/13 commit-graph: implement --delete-expiredDerrick Stolee, Feb 19, 2018
  108. Stefan BellerFeb 21, 2018
  109. Derrick StoleeFeb 23, 2018
  110. Junio C HamanoFeb 22, 2018
  111. Derrick StoleeFeb 23, 2018
  112. Junio C HamanoFeb 23, 2018
  113. Derrick StoleeFeb 23, 2018
  114. Junio C HamanoFeb 23, 2018
  115. 09/13 commit-graph: add core.commitGraph settingDerrick Stolee, Feb 19, 2018
  116. 10/13 commit-graph: close under reachabilityDerrick Stolee, Feb 19, 2018
  117. 11/13 commit: integrate commit graph with commit parsingDerrick Stolee, Feb 19, 2018
  118. 12/13 commit-graph: read only from specific pack-indexesDerrick Stolee, Feb 19, 2018
  119. Stefan BellerFeb 21, 2018
  120. Derrick StoleeFeb 23, 2018
  121. 13/13 commit-graph: build graph from starting commitsDerrick Stolee, Feb 19, 2018
  122. 07/13 commit-graph: implement --set-latestDerrick Stolee, Feb 19, 2018
  123. Junio C HamanoFeb 22, 2018
  124. Derrick StoleeFeb 23, 2018
  125. 02/13 graph: add commit graph design documentDerrick Stolee, Feb 19, 2018
  126. Junio C HamanoFeb 20, 2018
  127. Derrick StoleeFeb 23, 2018
  128. Stefan BellerFeb 21, 2018
  129. 04/13 commit-graph: implement write_commit_graph()Derrick Stolee, Feb 19, 2018
  130. Junio C HamanoFeb 20, 2018
  131. Derrick StoleeFeb 23, 2018
  132. Junio C HamanoFeb 23, 2018
  133. Junio C HamanoFeb 23, 2018
  134. Derrick StoleeFeb 23, 2018
  135. SZEDER GáborFeb 26, 2018
  136. Junio C HamanoFeb 28, 2018
  137. 05/13 commit-graph: implement 'git-commit-graph write'Derrick Stolee, Feb 19, 2018
  138. Junio C HamanoFeb 21, 2018
  139. Jakub NarebskiMar 30, 2018
  140. Derrick StoleeApr 2, 2018
  141. Jakub NarebskiApr 2, 2018
  142. Derrick StoleeApr 2, 2018
  143. Stefan BellerApr 2, 2018
  144. Derrick StoleeApr 2, 2018
  145. Stefan BellerApr 2, 2018
  146. Jakub NarebskiApr 7, 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.