Compute and consume generation numbers
PATCH v5 10/11 merge: check config before loading commits
In reply to Derrick StoleeNow that we use generation numbers from the commit-graph, we must ensure that all commits that exist in the commit-graph are loaded from that file instead of from the object database. Since the commit-graph file is only checked if core.commitGraph is true, we must check the default config before we load any commits.
In the merge builtin, the config was checked after loading the HEAD commit. This was due to the use of the global 'branch' when checking merge-specific config settings.
Move the config load to be between the initialization of 'branch' and the commit lookup.
Without this change, a fast-forward merge would hit a BUG("bad generation skip") statement in commit.c during paint_down_to_common(). This is because the HEAD commit would be loaded with "infinite" generation but then reached by commits with "finite" generation numbers.
Add a test to t5318-commit-graph.sh that exercises this code path to prevent a regression.
--- builtin/merge.c | 7 ++++--- t/t5318-commit-graph.sh | 9 +++++++++ 2 files changed, 13 insertions(+), 3 deletions(-)
builtin/merge.c +4 -3
@@ -1148,14 +1148,15 @@ int cmd_merge(int argc, const char **argv, const char *prefix) branch = branch_to_free =resolve_refdup ("HEAD" ,0 , &head_oid,NULL );if (branch)skip_prefix (branch,"refs/heads/" , &branch); + +init_diff_ui_defaults (); +git_config (git_merge_config,NULL ); +if (!branch ||is_null_oid (&head_oid)) head_commit =NULL ;else head_commit =lookup_commit_or_die (&head_oid,"HEAD" ); -init_diff_ui_defaults (); -git_config (git_merge_config,NULL ); -if (branch_mergeoptions)parse_branch_merge_options (branch_mergeoptions); argc = parse_options(argc, argv, prefix, builtin_merge_options,
t/t5318-commit-graph.sh +9 -0
@@ -221,4 +221,13 @@ test_expect_success 'write graph in bare repo' ' graph_git_behavior 'bare repo with graph, commit 8 vs merge 1' bare commits/8 merge/1 graph_git_behavior 'bare repo with graph, commit 8 vs merge 2' bare commits/8 merge/2 +test_expect_success 'perform fast-forward merge in full repo' ' + cd "$TRASH_DIRECTORY/full" && + git checkout -b merge-5-to-8 commits/5 && + git merge commits/8 && + git show-ref -s merge-5-to-8 >output && + git show-ref -s commits/8 >expect && + test_cmp expect output +' + test_done
Signature · 1 line
2.17.0.39.g685157f7fb
PATCH v5 11/11 commit-graph.txt: update design document
In reply to Derrick StoleeWe now calculate generation numbers in the commit-graph file and use them in paint_down_to_common().
Expand the section on generation numbers to discuss how the three special generation numbers GENERATION_NUMBER_INFINITY, _ZERO, and _MAX interact with other generation numbers.
--- Documentation/technical/commit-graph.txt | 29 ++++++++++++++++++++---- 1 file changed, 24 insertions(+), 5 deletions(-)
Documentation/technical/commit-graph.txt +24 -5
@@ -77,6 +77,29 @@ in the commit graph. We can treat these commits as having "infinite" generation number and walk until reaching commits with known generation number. +We use the macro GENERATION_NUMBER_INFINITY = 0xFFFFFFFF to mark commits not +in the commit-graph file. If a commit-graph file was written by a version +of Git that did not compute generation numbers, then those commits will +have generation number represented by the macro GENERATION_NUMBER_ZERO = 0. + +Since the commit-graph file is closed under reachability, we can guarantee +the following weaker condition on all commits: + + If A and B are commits with generation numbers N amd M, respectively, + and N < M, then A cannot reach B. + +Note how the strict inequality differs from the inequality when we have +fully-computed generation numbers. Using strict inequality may result in +walking a few extra commits, but the simplicity in dealing with commits +with generation number *_INFINITY or *_ZERO is valuable. + +We use the macro GENERATION_NUMBER_MAX = 0x3FFFFFFF to for commits whose +generation numbers are computed to be at least this value. We limit at +this value since it is the largest value that can be stored in the +commit-graph file using the 30 bits available to generation numbers. This +presents another case where a commit can have generation number equal to +that of a parent. + Design Details --------------
@@ -98,18 +121,14 @@ Future Work - The 'commit-graph' subcommand does not have a "verify" mode that is necessary for integration with fsck. -- 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. - - 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' + - 'tag --merged' - Currently, parse_commit_gently() requires filling in the root tree object for a commit. This passes through lookup_tree() and consequently
Signature · 1 line
2.17.0.39.g685157f7fb
Quoted 5 lines · Derrick Stolee
Most of the changes from v4 are cosmetic, but there is one new commit:
commit: use generation number in
remove_redundant()Other changes are non-functional, but do clarify things.
I wonder if out perf framework in t/perf could help here to show performance gains for the whole series. Though it may not include operations that are most helped by this one.
For commit-graph feature if would be nice, if feasible, to see changes in performance from before version, checking both state where feature is enabled to see the gains, and state where feature is disabled to see if there are no performance regressions.
Quoted 2 lines
Inter-diff from v4:
O.K., now to commenting on inter-changes.
Quoted 6 lines
Documentation/technical/commit-graph.txt +0
-0@@ -125,9 +125,10 @@ Future Work walks aware of generation numbers to gain the performance benefits they
Documentation/technical/commit-graph.txt Future Work · line 134
Quoted 10 lines
Documentation/technical/commit-graph.txt +2
-1enable. This will mostly be accomplished by swapping a commit-date-ordered priority queue with one ordered by generation number. The following - operation is an important candidate: + operations are important candidates: - 'log --topo-order' + - 'tag --merged' - Currently, parse_commit_gently() requires filling in the root tree object for a commit. This passes through lookup_tree() and consequently
O.K., this is about discussion in "branch --contains / tag --merged inconsistency" thread:
commit-graph.c static struct commit_list **insert_parent_or_die(struct commit_graph *g, · line 254
Quoted 12 lines
commit-graph.c +1
-0@@ -248,6 +248,7 @@ static struct commit_list **insert_parent_or_die(struct commit_graph *g,static void fill_commit_graph_info (struct commit *item,struct commit_graph *g,uint32_t pos) {const unsigned char *commit_data = g->chunk_commit_data +GRAPH_DATA_WIDTH * pos; + item->graph_pos = pos; item->generation =get_be32 (commit_data + g->hash_len +8 ) >>2 ; }
Minor bugfix.
commit-graph.c static void write_graph_chunk_data(struct hashfile *f, int hash_len, · line 461
Quoted 10 lines
commit-graph.c +1
-2@@ -454,8 +455,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,else packedDate[0 ] =0 ; -if ((*list)->generation !=GENERATION_NUMBER_INFINITY ) - packedDate[0 ] |=htonl ((*list)->generation <<2 ); + packedDate[0 ] |=htonl ((*list)->generation <<2 ); packedDate[1 ] =htonl ((*list)->date);hashwrite (f, packedDate,8 );
Minor bugfix.
Quoted 14 lines
commit-graph.c +1
-5@@ -589,18 +589,17 @@ static void close_reachable(struct packed_oid_list *oids) } } -static void compute_generation_numbers (struct commit ** commits, -int nr_commits) +static void compute_generation_numbers (struct packed_commit_list * commits) {int i;struct commit_list *list =NULL ; -for (i =0 ; i < nr_commits; i++) { -if (commits[i]->generation !=GENERATION_NUMBER_INFINITY && - commits[i]->generation !=GENERATION_NUMBER_ZERO )
commit-graph.c static void close_reachable(struct packed_oid_list *oids) · line 605
Quoted 10 lines
commit-graph.c +4
-1+for (i =0 ; i < commits->nr; i++) { +if (commits->list[i]->generation !=GENERATION_NUMBER_INFINITY && + commits->list[i]->generation !=GENERATION_NUMBER_ZERO )continue ; -commit_list_insert (commits[i], &list); +commit_list_insert (commits->list[i], &list);while (list) {struct commit *current = list->item;struct commit_list *parent;
Refactoring: signature change from pair of struct commit** + int to struct packed_commit_list*.
I think that it makes code a bit uglier for no gain, but that is just my personal opinion; it is a matter of taste.
Quoted 4 lines
commit-graph.c +0
-0@@ -621,10 +620,10 @@ static void compute_generation_numbers(struct commit** commits,if (all_parents_computed) { current->generation = max_generation +1 ;pop_commit (&list);
commit-graph.c static void compute_generation_numbers(struct commit** commits, · line 629
Quoted 10 lines
commit-graph.c +3
-3- } -if (current->generation >GENERATION_NUMBER_MAX ) - current->generation =GENERATION_NUMBER_MAX ; +if (current->generation >GENERATION_NUMBER_MAX ) + current->generation =GENERATION_NUMBER_MAX ; + } } } }
Bugfix (though it didn't result in wrong information writen out, just in inconsistent state in the middle of computation).
commit-graph.c void write_commit_graph(const char *obj_dir, · line 757
Quoted 9 lines
commit-graph.c +1
-1@@ -752,7 +751,7 @@ void write_commit_graph(const char *obj_dir,if (commits.nr >=GRAPH_PARENT_MISSING )die (_ ("too many commits to write graph" )); -compute_generation_numbers (commits.list, commits.nr); +compute_generation_numbers (&commits); graph_name =get_commit_graph_filename (obj_dir); fd =hold_lock_file_for_update (&lk, graph_name,0 );
The other side of signature change.
Quoted 5 lines
commit.c +0
-0
commit.c static struct commit_list *paint_down_to_common(struct commit *one, int n, · line 843
Quoted 10 lines
commit.c +3
-1@@ -835,7 +835,9 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n,int flags;if (commit->generation > last_gen) -BUG ("bad generation skip" ); +BUG ("bad generation skip %8x > %8x at %s" , + commit->generation, last_gen, +oid_to_hex (&commit->object.oid)); last_gen = commit->generation;if (commit->generation < min_generation)
More detailed BUG() message, always nice to have.
Quoted 12 lines
commit.c +1
-0@@ -947,6 +949,7 @@ static int remove_redundant(struct commit **array, int cnt)parse_commit (array[i]);for (i =0 ; i < cnt; i++) {struct commit_list *common; +uint32_t min_generation =GENERATION_NUMBER_INFINITY ;if (redundant[i])continue ;@@ -955,8 +958,12 @@ static int remove_redundant(struct commit **array, int cnt)continue ; filled_index[filled] = j; work[filled++] = array[j];
commit.c static int remove_redundant(struct commit **array, int cnt) · line 969
Quoted 10 lines
commit.c +5
-1+ +if (array[j]->generation < min_generation) + min_generation = array[j]->generation; } - common =paint_down_to_common (array[i], filled, work,0 ); + common =paint_down_to_common (array[i], filled, work, + min_generation);if (array[i]->object.flags &PARENT2 ) redundant[i] =1 ;for (j =0 ; j < filled; j++)
New commit in series. Change looks quite short, gives measurable performance gains (in appropriate case).
commit.c int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit * · line 1086
Quoted 10 lines
commit.c +1
-1@@ -1073,7 +1080,7 @@ int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit *for (i =0 ; i < nr_reference; i++) {if (parse_commit (reference[i]))return ret; -if (min_generation > reference[i]->generation) +if (reference[i]->generation < min_generation) min_generation = reference[i]->generation; }
Style change.
Quoted 14 lines
-- >8 --
Derrick Stolee (11):
ref-filter: fix outdated comment onin_commit_list
commit: add generation number to struct commmit
commit-graph: compute generation numbers
commit: use generations inpaint_down_to_common()
commit-graph: always load commit-graph information
ref-filter: use generation number for --contains
commit: use generation numbers forin_merge_bases()
commit: add short-circuit topaint_down_to_common()
commit: use generation number inremove_redundant()
merge: check config before loading commits commit-graph.txt: update design document
It looks like the series is maturing nicely.
Best,
Signature · 1 line
Jakub Narębski