# [PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph 7 messages from 2026-06-29 to 2026-07-08. Participants: Kristofer Karlsson via GitGitGadget, Junio C Hamano, Kristofer Karlsson. Thread: https://gitlist.dev/t/65885 ## Kristofer Karlsson via GitGitGadget, 2026-06-29 13:19 Subject: [PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph Message-ID: ``` Fixes a bug introduced by 93e5b1680e (commit-reach: early exit paint_down_to_common for single merge-base, 2025-04-10) where git merge-base can return the wrong result. The bug requires all of the following to trigger: 1. A v1 commit graph (topological levels only, no corrected commit dates). Generation v2 with corrected commit dates has been the default since 2021, so only repos that have not rewritten their commit graph in over four years would be affected. 2. git merge-base without --all (the common case, but --all is unaffected because it disables the early exit). 3. A topology with clock skew: the correct merge base has a lower committer date than one of its ancestors that is also a common ancestor. With date ordering, the deeper ancestor pops first and the early exit fires before the correct result is found. This two-patch series: 1. Adds a test demonstrating the bug (clock-skew topology where the correct merge base has a lower date than its ancestor) 2. Fixes it by tracking whether the queue is generation-ordered and gating the early exit on that flag Kristofer Karlsson (2): t6600: add test for merge-base early exit with clock skew commit-reach: guard !FIND_ALL early exit with generation ordering check commit-reach.c | 10 +++++++--- t/t6600-test-reach.sh | 41 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 48 insertions(+), 3 deletions(-) base-commit: 9aa172cd1f113276d360d4e48937dc95ef46b780 Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2162%2Fspkrka%2Ffind-all-fix-v1 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2162/spkrka/find-all-fix-v1 Pull-Request: https://github.com/gitgitgadget/git/pull/2162 -- gitgitgadget ``` ## Kristofer Karlsson via GitGitGadget, 2026-06-29 13:19 Subject: [PATCH 1/2] t6600: add test for merge-base early exit with clock skew Message-ID: In-Reply-To: ``` From: Kristofer Karlsson Add a topology where the correct merge base (M2) has a lower committer date than its ancestor (M1) due to clock skew. With a v1 commit graph (topological levels only, no corrected commit dates), paint_down_to_common() falls back to commit-date ordering. In that mode, M1 pops before M2, acquires both paint sides, and the !FIND_ALL early exit fires -- returning the wrong merge base. Mark the test as test_expect_failure to document the bug; the next commit will fix it. Signed-off-by: Kristofer Karlsson --- t/t6600-test-reach.sh | 41 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 41 insertions(+) diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index b5b314e570..1090104220 100755 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@ -49,6 +49,42 @@ test_expect_success 'setup' ' git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i || return 1 done done && + # Build a topology with clock skew to test the !FIND_ALL early + # exit in paint_down_to_common(). M2 is the correct merge base + # of P1 and P2, but its ancestor M1 has a higher committer date + # due to clock skew. With date-only ordering (v1 commit graph + # without corrected commit dates), M1 pops from the queue first, + # gets both paint sides, and the early exit fires before M2 is + # ever visited. + # + # P1 P2 @7000 + # | / \ + # A B D @6000 + # / \ | | + # | M2--+ | @2000 (correct merge base) + # \ | | + # M1--------+ @5000 (clock skew: date > M2) + # | + # root @1000 + # + git checkout --orphan skew-orphan && + skew_tree=$(git mktree expect && + merge_base_all_modes skew-P1 skew-P2 +' + test_done -- gitgitgadget ``` ## Kristofer Karlsson via GitGitGadget, 2026-06-29 13:19 Subject: [PATCH 2/2] commit-reach: guard !FIND_ALL early exit with generation ordering check Message-ID: In-Reply-To: ``` From: Kristofer Karlsson When paint_down_to_common() falls back to commit-date ordering (for v1 commit graphs without corrected commit dates), the !FIND_ALL early exit incorrectly fires. The exit assumes the queue is generation- ordered, so the first RESULT commit found must be the shallowest. With date ordering this is not guaranteed: a closer merge base with a lower committer date (clock skew) may still be in the queue behind deeper commits. Add a gen_ordered flag that is cleared when the date fallback fires, and require it for the early exit. Update the test from the previous commit to test_expect_success. Signed-off-by: Kristofer Karlsson --- commit-reach.c | 10 +++++++--- t/t6600-test-reach.sh | 2 +- 2 files changed, 8 insertions(+), 4 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index 5df471a313..708798a39b 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -108,11 +108,14 @@ static int paint_down_to_common(struct repository *r, { compare_commits_by_gen_then_commit_date } }; int i; + int gen_ordered = 1; timestamp_t last_gen = GENERATION_NUMBER_INFINITY; struct commit_list **tail = result; - if (!min_generation && !corrected_commit_dates_enabled(r)) + if (!min_generation && !corrected_commit_dates_enabled(r)) { queue.pq.compare = compare_commits_by_commit_date; + gen_ordered = 0; + } one->object.flags |= PARENT1; if (!n) { @@ -147,11 +150,12 @@ static int paint_down_to_common(struct repository *r, commit->object.flags |= RESULT; tail = commit_list_append(commit, tail); /* - * The queue is generation-ordered; no - * remaining common ancestor can be a + * When the queue is generation-ordered, + * no remaining common ancestor can be a * descendant of this one. */ if (!(mb_flags & MERGE_BASE_FIND_ALL) && + gen_ordered && generation < GENERATION_NUMBER_INFINITY) break; } diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index 1090104220..0ff41381ff 100755 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@ -1003,7 +1003,7 @@ test_expect_success 'merge-base without --all is one of --all results' ' grep -F -f single all ' -test_expect_failure 'merge-base without --all, clock skew, v1 commit-graph' ' +test_expect_success 'merge-base without --all, clock skew, v1 commit-graph' ' git rev-parse skew-M2 >expect && merge_base_all_modes skew-P1 skew-P2 ' -- gitgitgadget ``` ## Junio C Hamano, 2026-06-29 17:50 Subject: Re: [PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph Message-ID: In-Reply-To: ``` "Kristofer Karlsson via GitGitGadget" writes: > Fixes a bug introduced by 93e5b1680e (commit-reach: early exit > paint_down_to_common for single merge-base, 2025-04-10) where git merge-base > can return the wrong result. > > The bug requires all of the following to trigger: > > 1. A v1 commit graph (topological levels only, no corrected commit dates). > Generation v2 with corrected commit dates has been the default since > 2021, so only repos that have not rewritten their commit graph in over > four years would be affected. > 2. git merge-base without --all (the common case, but --all is unaffected > because it disables the early exit). > 3. A topology with clock skew: the correct merge base has a lower committer > date than one of its ancestors that is also a common ancestor. With date > ordering, the deeper ancestor pops first and the early exit fires before > the correct result is found. > > This two-patch series: > > 1. Adds a test demonstrating the bug (clock-skew topology where the correct > merge base has a lower date than its ancestor) > 2. Fixes it by tracking whether the queue is generation-ordered and gating > the early exit on that flag Where should this new "gen_ordered" flag go in the world with kk/merge-base-exhaustion topic merged in? Does it also belong to the paint_state struct or can it be on-stack independent variable to the function? ``` ## Kristofer Karlsson, 2026-06-29 18:27 Subject: Re: [PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph Message-ID: In-Reply-To: ``` On Mon, 29 Jun 2026 at 19:50, Junio C Hamano wrote: > > Where should this new "gen_ordered" flag go in the world with > kk/merge-base-exhaustion topic merged in? Does it also belong > to the paint_state struct or can it be on-stack independent variable > to the function? I don't think kk/merge-base-exhaustion is ready to be merged as-is and you are right that these two topics would conflict. I will need to reroll v5 and exactly how/when I do that depends on what we do here. I wanted to quickly share this small patch as a bugfix since the related code is already merged. I think the bug itself might be a very unlikely edge case but I can't really be sure. My preference would be to merge this as-is, and then I can rework v5 of kk/merge-base-exhaustion on top of it later - it will add some delay but I don't want to rush it since it's a non-trivial change. The other option is to drop this topic if the risk is deemed low enough, and then I will rework v5 to either apply a similar gen_ordered flag or eliminate that different ordering entirely - I see that as a good long-term goal that simplifies the code while retaining or improving the performance. I realize the timing is terrible, I wish I had spotted this a week ago instead of right at the 2.55 finalization period. Thanks, Kristofer ``` ## Junio C Hamano, 2026-06-29 18:52 Subject: Re: [PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph Message-ID: In-Reply-To: ``` Kristofer Karlsson writes: > My preference would be to merge this as-is, and then I can rework > v5 of kk/merge-base-exhaustion on top of it later - it will > add some delay but I don't want to rush it since it's a non-trivial > change. That sounds very sensible. Let's do that. I've taken a look at both of these two patches and found the solution quite sensible, but I'd prefer a second set of eyes to confirm. Thanks. ``` ## Junio C Hamano, 2026-07-08 17:24 Subject: Re: [PATCH 2/2] commit-reach: guard !FIND_ALL early exit with generation ordering check Message-ID: In-Reply-To: ``` "Kristofer Karlsson via GitGitGadget" writes: > From: Kristofer Karlsson > > When paint_down_to_common() falls back to commit-date ordering (for > v1 commit graphs without corrected commit dates), the !FIND_ALL early > exit incorrectly fires. The exit assumes the queue is generation- > ordered, so the first RESULT commit found must be the shallowest. > With date ordering this is not guaranteed: a closer merge base with > a lower committer date (clock skew) may still be in the queue behind > deeper commits. Excellent description of a good observation. > Add a gen_ordered flag that is cleared when the date fallback fires, > and require it for the early exit. The solution is simple and straight-forward. The flag is initialized to true but we drop it when generation order is not in effect, and the early exit requires the flag to be still true. > Update the test from the previous commit to test_expect_success. > > Signed-off-by: Kristofer Karlsson > --- Let's mark it for 'next'. Thanks. > commit-reach.c | 10 +++++++--- > t/t6600-test-reach.sh | 2 +- > 2 files changed, 8 insertions(+), 4 deletions(-) > > diff --git a/commit-reach.c b/commit-reach.c > index 5df471a313..708798a39b 100644 > --- a/commit-reach.c > +++ b/commit-reach.c > @@ -108,11 +108,14 @@ static int paint_down_to_common(struct repository *r, > { compare_commits_by_gen_then_commit_date } > }; > int i; > + int gen_ordered = 1; > timestamp_t last_gen = GENERATION_NUMBER_INFINITY; > struct commit_list **tail = result; > > - if (!min_generation && !corrected_commit_dates_enabled(r)) > + if (!min_generation && !corrected_commit_dates_enabled(r)) { > queue.pq.compare = compare_commits_by_commit_date; > + gen_ordered = 0; > + } > > one->object.flags |= PARENT1; > if (!n) { > @@ -147,11 +150,12 @@ static int paint_down_to_common(struct repository *r, > commit->object.flags |= RESULT; > tail = commit_list_append(commit, tail); > /* > - * The queue is generation-ordered; no > - * remaining common ancestor can be a > + * When the queue is generation-ordered, > + * no remaining common ancestor can be a > * descendant of this one. > */ > if (!(mb_flags & MERGE_BASE_FIND_ALL) && > + gen_ordered && > generation < GENERATION_NUMBER_INFINITY) > break; > } > diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh > index 1090104220..0ff41381ff 100755 > --- a/t/t6600-test-reach.sh > +++ b/t/t6600-test-reach.sh > @@ -1003,7 +1003,7 @@ test_expect_success 'merge-base without --all is one of --all results' ' > grep -F -f single all > ' > > -test_expect_failure 'merge-base without --all, clock skew, v1 commit-graph' ' > +test_expect_success 'merge-base without --all, clock skew, v1 commit-graph' ' > git rev-parse skew-M2 >expect && > merge_base_all_modes skew-P1 skew-P2 > ' ```