git/commit-reach.c, branch v2.30.2

commit-reach: fix in_merge_bases_many bug

2020-10-02T17:26:31Z

Way back in f9b8908b (commit.c: use generation numbers for in_merge_bases(), 2018-05-01), a heuristic was used to short-circuit the in_merge_bases() walk. This works just fine as long as the caller is checking only two commits, but when there are multiple, there is a possibility that this heuristic is _very wrong_. Some code moves since then has changed this method to repo_in_merge_bases_many() inside commit-reach.c. The heuristic computes the minimum generation number of the "reference" list, then compares this number to the generation number of the "commit". In a recent topic, a test was added that used in_merge_bases_many() to test if a commit was reachable from a number of commits pulled from a reflog. However, this highlighted the problem: if any of the reference commits have a smaller generation number than the given commit, then the walk is skipped _even if there exist some with higher generation number_. This heuristic is wrong! It must check the MAXIMUM generation number of the reference commits, not the MINIMUM. This highlights a testing gap. t6600-test-reach.sh covers many methods in commit-reach.c, including in_merge_bases() and get_merge_bases_many(), but since these methods either restrict to two input commits or actually look for the full list of merge bases, they don't check this heuristic! Add a possible input to "test-tool reach" that tests in_merge_bases_many() and add tests to t6600-test-reach.sh that cover this heuristic. This includes cases for the reference commits having generation above and below the generation of the input commit, but also having maximum generation below the generation of the input commit. The fix itself is to swap min_generation with a max_generation in repo_in_merge_bases_many(). Reported-by: Srinidhi Kaushik Helped-by: Johannes Schindelin Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

Merge branch 'cb/is-descendant-of'

2020-07-07T05:09:16Z

Code clean-up. * cb/is-descendant-of: commit-reach: avoid is_descendant_of() shim

Merge branch 'ak/commit-graph-to-slab'

2020-07-07T05:09:14Z

A few fields in "struct commit" that do not have to always be present have been moved to commit slabs. * ak/commit-graph-to-slab: commit-graph: minimize commit_graph_data_slab access commit: move members graph_pos, generation to a slab commit-graph: introduce commit_graph_data_slab object: drop parsed_object_pool->commit_count

Merge branch 'rs/commit-reach-leakfix'

2020-06-29T21:17:27Z

Leakfix. * rs/commit-reach-leakfix: commit-reach: plug minor memory leak after using is_descendant_of()

commit-reach: avoid is_descendant_of() shim

2020-06-23T23:36:53Z

d91d6fbf26 (commit-reach: create repo_is_descendant_of(), 2020-06-17) adds a repository aware version of is_descendant_of() and a backward compatibility shim that is barely used. Update all callers to directly use the new repo_is_descendant_of() function instead; making the codebase simpler and pushing more the_repository references higher up the stack. Helped-by: Derrick Stolee Signed-off-by: Carlo Marcelo Arenas Belón Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano

commit-reach: plug minor memory leak after using is_descendant_of()

2020-06-19T18:06:01Z

ref_newer() builds a commit_list to pass a single potential ancestor to is_descendant_of(). The latter leaves the list intact. Release the allocated memory after the call. Signed-off-by: René Scharfe Acked-by: Derrick Stolee Signed-off-by: Junio C Hamano

commit-graph: minimize commit_graph_data_slab access

2020-06-17T21:37:52Z

In an earlier patch, multiple struct acccesses to `graph_pos` and `generation` were auto-converted to multiple method calls. Since the values are fixed and commit-slab access costly, we would be better off with storing the values as a local variable and reusing it. Signed-off-by: Abhishek Kumar Signed-off-by: Junio C Hamano

commit: move members graph_pos, generation to a slab

2020-06-17T21:37:30Z

We remove members `graph_pos` and `generation` from the struct commit. The default assignments in init_commit_node() are no longer valid, which is fine as the slab helpers return appropriate default values and the assignments are removed. We will replace existing use of commit->generation and commit->graph_pos by commit_graph_data_slab helpers using `contrib/coccinelle/commit.cocci'. Signed-off-by: Abhishek Kumar Signed-off-by: Junio C Hamano

commit-reach: use fast logic in repo_in_merge_base

2020-06-17T20:49:38Z

The repo_is_descendant_of() method is aware of the existence of the commit-graph file. It checks for generation_numbers_enabled() before deciding on using can_all_from_reach() or repo_in_merge_bases() depending on the situation. The reason here is that can_all_from_reach() uses a depth-first search that is limited by the minimum generation number of the target commits, and that algorithm can be very slow when generation numbers are not present. The alternative uses paint_down_to_common() which will walk the entire merge-base boundary, which is typically slower. This method is used by commands like "git tag --contains" and "git branch --contains" for very fast results when a commit-graph file exists. Unfortunately, it is _not_ used in commands like "git merge-base --is-ancestor" which is doing an even simpler request. This issue was raised recently [1] with respect to a change to how generation numbers are stored, but was also reported much earlier [2] before commit-reach.c existed to simplify these reachability queries. [1] https://lore.kernel.org/git/20200607195347.GA8232@szeder.dev/ [2] https://lore.kernel.org/git/87608bawoa.fsf@evledraar.gmail.com/ The root cause is that builtin/merge-base.c has a method handle_is_ancestor() that calls in_merge_bases(), an older version of repo_in_merge_bases(). It would be better if we have every caller to in_merge_bases() use the logic in can_all_from_reach() when possible. This is where things get a little tricky: repo_is_descendant_of() calls repo_in_merge_bases() in the non-generation numbers enabled case! If we simply update repo_in_merge_bases() to call repo_is_descendant_of() instead of repo_in_merge_bases_many(), then we will get a recursive call loop. Thankfully, this is caught by the test suite in the default mode (i.e. GIT_TEST_COMMIT_GRAPH=0). The trick, then, is to make the non-generation number case for repo_is_descendant_of() call repo_in_merge_bases_many() directly, skipping the non-_many version. This allows us to take advantage of this faster code path, when possible. The easiest way to measure the performance impact is to test the following command on the Linux kernel repository: git merge-base --is-ancestor | A | B | Time Before | Time After | |------|------|-------------|------------| | v3.0 | v5.7 | 0.459s | 0.028s | | v4.0 | v5.7 | 0.267s | 0.021s | | v5.0 | v5.7 | 0.074s | 0.013s | Note that each of these samples return success. The old code performed the same operation when and are swapped. However, can_all_from_reach() will return immediately if the generation numbers show that has larger generation number than . Thus, the time for the swapped case is universally 0.004s in each case. Reported-by: Ævar Arnfjörð Bjarmason Reported-by: SZEDER Gábor Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

commit-reach: create repo_is_descendant_of()

2020-06-17T20:49:36Z
The next change will make repo_in_merge_bases() depend on the logic in is_descendant_of(), but we need to make the method independent of the_repository first. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano