* Re: [PATCH 2/3] revision: avoid leaking bloom keyvecs with multiple traversals
From: Derrick Stolee @ 2026-07-01 14:21 UTC (permalink / raw)
To: Jeff King, git; +Cc: Patrick Steinhardt
In-Reply-To: <20260701064052.GB2580331@coredump.intra.peff.net>
On 7/1/2026 2:40 AM, Jeff King wrote:
> In prepare_revision_walk(), we convert the pruning pathspecs into
> bloom-filter "keyvecs" via prepare_to_use_bloom_filter(). This allocates
> memory which is then freed eventually by release_revisions(), via
> release_revisions_bloom_keyvecs().
> static void prepare_to_use_bloom_filter(struct rev_info *revs)
> {
> + release_revisions_bloom_keyvecs(revs);
> +
I continue to support the obviously-correct and simple solution to
these leaks.
Thanks,
-Stolee
^ permalink raw reply
* Re: [PATCH 0/3] bloom-related leak fixes
From: Derrick Stolee @ 2026-07-01 14:32 UTC (permalink / raw)
To: Jeff King, git; +Cc: Patrick Steinhardt
In-Reply-To: <20260701063538.GA2579765@coredump.intra.peff.net>
On 7/1/2026 2:35 AM, Jeff King wrote:
> Here are a few small leak fixes that only show up when you run the test
> suite with GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1.
>
> Combined with the commit-graph leak-fix here:
>
> https://lore.kernel.org/git/20260630064301.GB3733961@coredump.intra.peff.net/
>
> and Kaartic's pending fix from this thread:
>
> https://lore.kernel.org/git/20260614141600.620272-1-kaartic.sivaraam@gmail.com/
>
> This will fix most of the leaks we'd see if we ran linux-TEST-vars jobs
> with leak-checking. There are a few more related to building with
> openssl for sha1, but I'll tackle those separately.
Thanks for fixing these leaks in the simplest way possible in
each scenario.
Thanks,
-Stolee
^ permalink raw reply
* Re: [PATCH RFC v2 2/2] Move libgit.a sources into separate "lib/" directory
From: Junio C Hamano @ 2026-07-01 14:45 UTC (permalink / raw)
To: Phillip Wood
Cc: Patrick Steinhardt, SZEDER Gábor, git, brian m. carlson,
Elijah Newren, Derrick Stolee, Phillip Wood
In-Reply-To: <cbbb08fc-fd4d-45ef-927b-05ac44602ff1@gmail.com>
Phillip Wood <phillip.wood123@gmail.com> writes:
> As I said last time this came up, I don't really buy the discoverability
> argument because there are just as many files to trawl through to find
> what you're looking through and now there is an extra directory to
> check. I think the solution to that is to recommend folks use "git grep"
> or ctags etc. not moving code to a new directory.
Hear, hear. Also it would be great if we can trick some talented
technical writer into writing the "map" of the source so that by
reading this one or two pager, any new person with reasonable
competence will know how things are partitioned into pieces and how
these pieces fit together. I wonder how good LLMs are these days?
;-)
> I do however think putting all the library code in a subdirectory makes
> it easier to say things like "please try to avoid new uses of
> 'the_repository' and prefer 'error()' over 'die()' in library code"
> because all the library code is in the same directory. I think that is a
> much stronger selling point.
Yes. "library code (things outside the subdirectories) should not
use X" would work just fine, though.
> Another cost is remembering things have moved - the other day I spent
> too long wondering why "git show origin/seen:wt-status.c" wasn't working
> until I ran "git log origin/seen" and realized it had move to
> lib/wt-status.c.
Yes, this has bit me multiple dozen times, as the tip of 'seen' is
contaminated with this rename, already. It is a huge pain.
^ permalink raw reply
* Re: [GSoC Blog] week 1 and 2: Complete and extend the remote-object-info command for git cat-file
From: Pablo Sabater @ 2026-07-01 15:03 UTC (permalink / raw)
To: git
In-Reply-To: <CAN5EUNT1C6O+xHKfbptO5eohx3Md=h4pKRdqpY8+pD9YT_-3Og@mail.gmail.com>
Hello!
I just posted my week 4 and 5 on the blog.
https://pablosabater.dev/posts/gsoc-week-4-and-5-coding-period/
As always any doubt, idea or opinion are welcome.
Thanks for reading it,
Pablo.
^ permalink raw reply
* Re: [PATCH v5 0/4] history: add squash subcommand to fold a range
From: Phillip Wood @ 2026-07-01 15:14 UTC (permalink / raw)
To: Junio C Hamano
Cc: Harald Nordgren, phillip.wood, Patrick Steinhardt,
Harald Nordgren via GitGitGadget, git
In-Reply-To: <xmqq8q7urfe1.fsf@gitster.g>
On 01/07/2026 14:47, Junio C Hamano wrote:
> Phillip Wood <phillip.wood123@gmail.com> writes:
>
>> The reason we're introducing the history command is to experiment with
>> providing a better user interface for rewriting history without being
>> bound by the limitations of "git rebase". So I think it would entirely
>> appropriate to try a different format for the squash message here. If it
>> turns out to be a success then we can see if we want to use it in "git
>> rebase" as well.
>
> Do we know concretely things that are bad in the current way "rebase
> -i" works, so that we can experiment deviation from?
Yes - if you apply the way "rebase -i" works to multiple commits you can
end up with a message template that has a screen full of commented lines
between uncommitted parts of the message. See the example below from
earlier in the thread. It is not so much of a problem in "rebase -i"
because it only fixes up a single commit at a time so all the commented
messages end up at the top of the buffer and at worst you have a few "#
fixup! ..." or "# squash! ..." lines mixed in with the uncommitted text.
# This is the combination of 4 commits
# This is the first commit message
Base subject
Base body
# This is the second commit message
# Another subject
# Another body
# This is the third commit message
# fixup! Base subject
# This is the fourth commit message
# amend! Another subject
A better subject
A better body
Thanks
Phillip
^ permalink raw reply
* Re: [PATCH 1/3] bloom: make bloom-filter slab initialization idempotent
From: Junio C Hamano @ 2026-07-01 15:50 UTC (permalink / raw)
To: Jeff King; +Cc: git, Patrick Steinhardt
In-Reply-To: <20260701063942.GA2580331@coredump.intra.peff.net>
Jeff King <peff@peff.net> writes:
> Before using any of the commit-graph bloom-filter code, somebody needs
> to call init_bloom_filters(). This initializes the commit-slab we use
> for storing filter information. But we don't want to call it twice
> (without a matching deinit call in the middle), since it overwrites the
> existing slab pointers, leaking the old values.
>
> Usually this init call is done lazily by parse_commit_graph() when we
> read a graph file that contains bloom data. But this can lead to some
> oddities:
>
> 1. We may call parse_commit_graph() multiple times when we have a
> split commit graph. I think this doesn't produce any user-visible
> bug, because we parse all of the files back-to-back. So even though
> we call init_bloom_filters() multiple times, we never look up any
> commits in between, so the slab is always empty and initializing it
> again happens to do nothing. This is a little sketchy to rely on,
> though.
Yeah, that sounds like an accident waiting to happen.
>
> 2. We call init_bloom_filters() directly in the "test-tool bloom"
> helper so we can call get_or_compute_bloom_filter(). Normally this
> is OK, as there is no bloom data in the on-disk graph file. But if
> you build with SANITIZE=leak and run:
>
> GIT_TEST_COMMIT_GRAPH=1 \
> GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1 \
> ./t0095-bloom.sh
>
> there's a leak that happens like this:
>
> a. Our direct init_bloom_filters() sets up the slab.
>
> b. In get_or_compute_bloom_filter() we look in the slab for a
> cached entry. We won't find anything yet, but since we don't
> use the read-only "peek" accessor (since we'll fill in the
> entry if not present), this actually populates the slab with
> an allocated chunk.
>
> c. Now we look for an entry in the graph files. So we have to
> load them and end up in parse_commit_graph(), which calls
> init_bloom_filters() again. That trashes our existing slab
> allocation, which is now leaked.
Besides, if the test-tool initializes explicitly and the production
code does not and relies on lazy initialization, we are not testing
the production setting, which may hide bugs in lazy initialization.
> 3. There's a similar case in write_commit_graph(), which calls
> init_bloom_filters() before get_or_compute_bloom_filter(). I think
> this code path is lucky to avoid the leak because it reads the
> graph files first, then calls its init_bloom_filters(), and then
> starts filling in entries. So even though it has the same overwrite
> problem, we'd never actually allocate any slab entries between
> overwrites.
>
> The easiest solution here is just to make initialization of the slab
> idempotent using an extra flag.
>
> We could actually get away without using the extra flag, for example by
> checking whether bloom_filters.stride has been set. But it's probably
> better to avoid being too intimate with the commit-slab details.
"bool bloom_filter_slab_initialied()" that is generated by including
commit-slab-impl.h can be as intimate with the implementation as we
want, though ;-)
> Likewise we don't actually need to re-initialize after a deinit call;
> the slab-clearing function leaves things in a usable state. But it
> seemed less surprising to pair the init/deinit calls explicitly.
Good.
> This patch takes a smaller and more direct route to just dealing with
> the potential leak issue.
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> bloom.c | 5 +++++
> 1 file changed, 5 insertions(+)
Looks trivially correct.
> diff --git a/bloom.c b/bloom.c
> index a805ac0c29..c98d1672ad 100644
> --- a/bloom.c
> +++ b/bloom.c
> @@ -16,6 +16,7 @@
> define_commit_slab(bloom_filter_slab, struct bloom_filter);
>
> static struct bloom_filter_slab bloom_filters;
> +static int bloom_filter_slab_initialized;
>
> struct pathmap_hash_entry {
> struct hashmap_entry entry;
> @@ -263,7 +264,10 @@ void add_key_to_filter(const struct bloom_key *key,
>
> void init_bloom_filters(void)
> {
> + if (bloom_filter_slab_initialized)
> + return;
> init_bloom_filter_slab(&bloom_filters);
> + bloom_filter_slab_initialized = 1;
> }
>
> static void free_one_bloom_filter(struct bloom_filter *filter)
> @@ -276,6 +280,7 @@ static void free_one_bloom_filter(struct bloom_filter *filter)
> void deinit_bloom_filters(void)
> {
> deep_clear_bloom_filter_slab(&bloom_filters, free_one_bloom_filter);
> + bloom_filter_slab_initialized = 0;
> }
>
> struct bloom_keyvec *bloom_keyvec_new(const char *path, size_t len,
^ permalink raw reply
* Re: [PATCH 2/3] revision: avoid leaking bloom keyvecs with multiple traversals
From: Junio C Hamano @ 2026-07-01 15:52 UTC (permalink / raw)
To: Jeff King; +Cc: git, Patrick Steinhardt
In-Reply-To: <20260701064052.GB2580331@coredump.intra.peff.net>
Jeff King <peff@peff.net> writes:
> I think it would _probably_ work in practice, since any caller using a
> rev_info for multiple traversals is probably doing so with the same
> pathspec. But it would also create a very subtle bug if that assumption
> is violated. So we'll do the safer thing here, and generate fresh keyvec
> entries for each traversal. The efficiency difference is probably not
> noticeable, and this is what was happening already (we just weren't
> bothering to free the old ones!).
Good to see the thinking behind the design recorded so clearly in the log
message. That thinking being on the more conservative side is a big plus.
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> revision.c | 2 ++
> 1 file changed, 2 insertions(+)
>
> diff --git a/revision.c b/revision.c
> index e91d7e1f11..0ef9d895f0 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -707,6 +707,8 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,
>
> static void prepare_to_use_bloom_filter(struct rev_info *revs)
> {
> + release_revisions_bloom_keyvecs(revs);
> +
> if (!revs->commits)
> return;
^ permalink raw reply
* Re: [PATCH 01/13] load_one_loose_object_map(): fix resource leak
From: Junio C Hamano @ 2026-07-01 16:25 UTC (permalink / raw)
To: Johannes Schindelin via GitGitGadget; +Cc: git, Johannes Schindelin
In-Reply-To: <17242c249f0beb387fd30634663f13ce42d34f79.1782889472.git.gitgitgadget@gmail.com>
"Johannes Schindelin via GitGitGadget" <gitgitgadget@gmail.com>
writes:
> From: Johannes Schindelin <johannes.schindelin@gmx.de>
>
> Pointed out by Coverity.
>
> While at it, reduce near-duplicate clean-up code at the end of the
> function.
>
> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
> ---
> loose.c | 8 ++++----
> 1 file changed, 4 insertions(+), 4 deletions(-)
>
> diff --git a/loose.c b/loose.c
> index 0b626c1b85..47b7f5ec38 100644
> --- a/loose.c
> +++ b/loose.c
> @@ -65,6 +65,7 @@ static int load_one_loose_object_map(struct repository *repo, struct odb_source_
> {
> struct strbuf buf = STRBUF_INIT, path = STRBUF_INIT;
> FILE *fp;
> + int ret = -1;
>
> if (!loose->map)
> loose_object_map_init(&loose->map);
> @@ -98,13 +99,12 @@ static int load_one_loose_object_map(struct repository *repo, struct odb_source_
> insert_loose_map(loose, &oid, &compat_oid);
> }
>
> - strbuf_release(&buf);
> - strbuf_release(&path);
> - return errno ? -1 : 0;
Wow, this is bad bad bad. We do not even know what is in errno as
we are supposed to have jumped to out-of-line err label in all error
cases.
> + ret = 0;
Or we can do
ret = ferror(fp) ? -1 : 0;
if we want to be sure that we have caught all the errors.
> err:
> + fclose(fp);
> strbuf_release(&buf);
> strbuf_release(&path);
> - return -1;
> + return ret;
> }
>
> int repo_read_loose_object_map(struct repository *repo)
^ permalink raw reply
* Re: RUST_LIB dependency on LIB_FILE in Makefile
From: brian m. carlson @ 2026-07-01 16:28 UTC (permalink / raw)
To: Jan Palus; +Cc: git
In-Reply-To: <akO9JTUIlHqBrgny@pine.grzadka>
[-- Attachment #1: Type: text/plain, Size: 782 bytes --]
On 2026-06-30 at 13:07:29, Jan Palus wrote:
> According to Makefile $(RUST_LIB) target depends on $(LIB_FILE):
>
> $(RUST_LIB): Cargo.toml $(RUST_SOURCES) $(LIB_FILE)
>
> but is that really the case? As far as I can tell $(RUST_LIB) does not
> use $(LIB_FILE) in any way and there's no such dependency in
> meson.build.
It is really the case. The Rust code in `src/hash.rs` requires C
functions in `libgit.a`. The tests won't run via `cargo test` if it's
not built. There will be additional uses of this code in the relatively
near future and they will definitely require calls to `libgit.a`.
The lack of Meson functionality is likely an oversight and I'm sure a
patch to fix that would be accepted.
--
brian m. carlson (they/them)
Toronto, Ontario, CA
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 325 bytes --]
^ permalink raw reply
* [PATCH v5 00/10] commit-reach: terminate merge-base walk when one side is exhausted
From: Kristofer Karlsson via GitGitGadget @ 2026-07-01 16:37 UTC (permalink / raw)
To: git; +Cc: Kristofer Karlsson
In-Reply-To: <pull.2149.v4.git.1782649547.gitgitgadget@gmail.com>
Optimize paint_down_to_common() for merge-base queries that hit large
one-sided histories.
When the walk from one side reaches a commit with a very low generation
number that the other side never paints, the walk is forced to drain most of
the graph. A common trigger is a repository import that grafts a separate
history with its own root, but any merge that introduces a low-generation
commit never painted by the other side has the same effect.
A new merge-base candidate can only be discovered when exclusive PARENT1 and
PARENT2 paint meet. This series teaches paint_down_to_common() to stop as
soon as one side has no exclusive commits left in the queue; once one side
is exhausted, no further candidates can appear.
origin/HEAD o o PR HEAD
| |
(import) o :
/ \ /
| o merge-base
| |
: : (~2.5M commits)
| |
import root main root
In the RFC thread [1], Derrick Stolee provided a criss-cross counterexample
that sharpened the halt condition, and Elijah Newren independently
discovered the same optimization and shared an implementation in PR #2150
[2]. Patch 3 incorporates test cases from Elijah's branch.
This series implements the optimization only after the walk enters the
finite-generation region, where generation ordering guarantees that paint on
visited commits is final.
Patch 2 adds a test_trace2_data_singular helper to test-lib-functions.sh
that reports expected/actual values on assertion failure instead of a silent
grep exit. This was invaluable during development for iterating on step
counts across the series, and should be valuable for repairing tests after
future algorithmic changes. Happy to drop it if it is considered unnecessary
infrastructure.
The final patch removes the commit-date ordering fallback introduced by
091f4cf3 (commit: don't use generation numbers if not needed, 2018-08-30).
With side-exhaustion in place, the fallback is no longer needed for
performance, and removing it ensures the queue is always generation-ordered
regardless of graph version, so every termination condition can rely on a
single ordering invariant. This patch can be dropped if the scope is too
broad for this series.
NOTE: If the final patch is kept, the separate "commit-reach: fix !FIND_ALL
early exit with v1 commit graph" topic becomes unnecessary. Either way, the
two topics conflict trivially and I am happy to reroll whichever lands
second.
Benchmarks
Trace2 step counts are deterministic (measured via trace2_data_intmax added
in patch 5). Wall-clock times are best-of-11 runs.
2.6M-commit monorepo with commit-graph:
steps wall-clock
merge-base --all (across import) 2143438 -> 3 3.67s -> 5ms
merge-base --all (1000 apart) 2692915 -> 1035 4.41s -> 7ms
merge-base --all (5000 apart) 2692915 -> 6401 4.45s -> 13ms
merge-base --all (HEAD vs import) 2698872 -> 45960 4.50s -> 79ms
merge-tree (across import) 2143438 -> 3 4.42s -> 11ms
git.git (88k commits, commit-graph):
steps wall-clock
merge-base --all v2.0.0 v2.55.0-rc1 72264 -> 44589 110ms -> 68ms
merge-base --all HEAD HEAD~1000 9891 -> 3828 18ms -> 10ms
merge-base --all HEAD HEAD~10000 72303 -> 41487 101ms -> 50ms
CC: Derrick Stolee stolee@gmail.com CC: Elijah Newren newren@gmail.com
[1]
https://lore.kernel.org/git/CAL71e4Ps-2_0+uuZu43N9pFnXBemoAohPs_eyRJf8taXHJPAXQ@mail.gmail.com/T/#u
[2] https://github.com/gitgitgadget/git/pull/2150
Changes since v4:
* New patch 2/10: added test_trace2_data_singular helper to
test-lib-functions.sh. Shows expected/actual values on assertion failure
instead of a silent grep failure. Makes iterating on step counts much
easier.
* New patch 6/10: added clock-skew topologies (se-, se2-) that expose
side-exhaustion bugs when the commit-date ordering fallback fires with a
v1 commit graph. All topologies use a shared skew_commit helper. Includes
step count assertions for edge-case tests from patch 3.
* Folded the nonstale_queue dedup wrapper removal (previously separate
patch 6/8) into the paint_state introduction in patch 7/10.
* New patch 10/10: remove the commit-date ordering fallback in
paint_down_to_common(). The fallback (091cf18e) was a performance
optimization for v1 commit graphs, but it breaks the generation ordering
invariant that both the side-exhaustion and single-result optimizations
depend on. With side-exhaustion in place, the fallback is no longer
needed. If kept, this supersedes the separate "commit-reach: fix
!FIND_ALL early exit with v1 commit graph" topic.
Changes since v3:
* Fixed BUG assertion that was accidentally made unconditional in v3:
restored the min_generation guard so it only fires when generation-based
ordering is active.
* Moved generation cutoff and single-result termination conditions into the
documentation in patch 1, since they describe existing behavior.
* Renamed paint_state counter fields for clarity: p1_count ->
parent1_count, p2_count -> parent2_count, pending_merge_bases ->
mb_candidate_count. Changed counter types from int to size_t. (Suggested
by Rene Scharfe.)
Changes since v2:
* New patch 9/10 (was 8/8): moved the min_generation termination check and
the last_gen monotonicity assertion into paint_queue_get(), consolidating
halt conditions. commit_graph_generation() is now called once per
dequeued commit and shared across all checks.
* Moved all halt conditions inside paint_queue_get() with the "pop first"
form: pop, check, then decrement counters. This keeps the optimization
commit's diff minimal (just inserting the new checks between pop and
decrement).
* Shortened the doc comment on paint_queue_get() to describe what it does
rather than how. Inline comments on each return NULL explain the specific
halt condition.
* Replaced the manual commit-graph setup in the step-count test with
run_all_modes, which now sets GIT_TRACE2_EVENT per mode and produces
trace-mode-{none,full,half,no-gdat}.txt files.
* Added a test_paint_down_steps helper for concise 4-mode step assertions
with diagnostic output on mismatch (prints "expected X, got Y" instead of
a silent grep failure).
* Added step-count assertions to the single-walk edge-case tests:
in_merge_bases_many:self, pending-stale, infinity-both-sides,
mixed-finite-infinity.
* Included step counts alongside wall-clock times in the benchmark tables.
Changes since v1:
* Reordered patches: documentation first (describing the existing
algorithm), tests before code changes, so they demonstrate passing with
old logic first.
* Dropped the ahead_behind decoupling patch. paint_state is now a NEW
struct alongside nonstale_queue instead of replacing it. ahead_behind()
is completely untouched.
* Removed nonstale_queue_put_dedup() and nonstale_queue_get_dedup() (dead
code after the conversion) in a separate commit.
* Renamed: struct paint_queue -> paint_state, field pq -> queue,
paint_count_add/remove -> paint_count_update (single function with signed
delta parameter).
* Split the old paint_count_transition (which handled both old and new
flags in one call) into separate remove/add calls with a signed delta.
This eliminates the need for the case 0 handler (which tracked "not in
the queue") and allows an exhaustive switch on (PARENT1 | PARENT2 |
STALE) that documents all valid flag combinations, with BUG() in default.
* Added trace2_data_intmax() instrumentation to report the number of
commits visited per paint walk (separate commit), with step-count
assertions in tests for deterministic regression detection.
Elijah Newren (1):
t6600: add test cases for side-exhaustion edge cases
Kristofer Karlsson (9):
Documentation/technical: add paint-down-to-common doc
test-lib-functions: improve diagnostic output for trace2 data
assertions
t6099, t6600: add side-exhaustion regression tests
commit-reach: add trace2 instrumentation to paint_down_to_common()
t6600: add clock-skew topologies and step counts for edge cases
commit-reach: introduce struct paint_state with per-side counters
commit-reach: terminate merge-base walk when one paint side is
exhausted
commit-reach: move min_generation check into paint_queue_get()
commit-reach: remove commit-date ordering fallback
Documentation/Makefile | 1 +
Documentation/technical/meson.build | 1 +
.../technical/paint-down-to-common.adoc | 151 +++++++++
commit-graph.c | 11 -
commit-graph.h | 6 -
commit-reach.c | 152 ++++++---
t/meson.build | 1 +
t/t6099-merge-base-side-exhaustion.sh | 82 +++++
t/t6600-test-reach.sh | 289 +++++++++++++++++-
t/test-lib-functions.sh | 36 +++
10 files changed, 663 insertions(+), 67 deletions(-)
create mode 100644 Documentation/technical/paint-down-to-common.adoc
create mode 100755 t/t6099-merge-base-side-exhaustion.sh
base-commit: e9019fcafe0040228b8631c30f97ae1adb61bcdc
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2149%2Fspkrka%2Fside-exhaust-pr-v5
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2149/spkrka/side-exhaust-pr-v5
Pull-Request: https://github.com/gitgitgadget/git/pull/2149
Range-diff vs v4:
1: 3efb095b03 ! 1: be00f5aaa1 Documentation/technical: add paint-down-to-common doc
@@ Documentation/technical/paint-down-to-common.adoc (new)
+ - PARENT1: reachable from `one`
+ - PARENT2: reachable from any commit in `twos[]`
+
-+The walk uses a priority queue ordered by generation number (falling
-+back to commit date when generation numbers are unavailable). Each
-+step dequeues the highest-priority commit (this is when we say a
-+commit is "visited") and propagates its paint flags to its parents,
-+enqueuing them if they gained new flags. When a commit receives
-+both PARENT1 and PARENT2, it is a merge-base candidate. A candidate
-+gains the STALE flag so its ancestors propagate staleness -- any
-+deeper common ancestor is necessarily redundant.
-+
++The walk uses a priority queue ordered by generation number
++(highest first), breaking ties by commit date. Each step dequeues
++the highest-priority commit (this is when we say a commit is
++"visited") and propagates its paint flags to its parents, enqueuing
++them if they gained new flags. When a commit receives both PARENT1
++and PARENT2, it is a merge-base candidate. A candidate gains the
++STALE flag so its ancestors propagate staleness -- any deeper common
++ancestor is necessarily redundant.
++
++NOTE: When the commit-graph uses only topological levels (generation
++number v1) and the caller passes `min_generation = 0`, a legacy
++fallback replaces the generation-ordered comparator with a pure
++commit-date comparator. This breaks the ordering invariants
++described below -- see <<date-ordering-fallback>>.
++
++[[generation-regions]]
+INFINITY and finite generation regions
+--------------------------------------
+
++The properties in this section assume generation-number ordering (the
++default comparator). They do NOT hold when the date-ordering fallback
++is active -- see <<date-ordering-fallback>>.
++
+The commit-graph stores a generation number for each commit. Commits
+not in the commit-graph have generation `GENERATION_NUMBER_INFINITY`. The
+graph is closed under reachability: if a commit is in the graph, all
@@ Documentation/technical/paint-down-to-common.adoc (new)
+
+Single result
+~~~~~~~~~~~~~
-+When only one merge base is needed and the walk is in the
-+finite-generation region, the first candidate found is necessarily
-+the highest-generation common ancestor. No remaining commit in the
-+queue can be a descendant of this candidate (generation ordering
-+guarantees children are visited first), so it cannot be redundant
-+and the walk can stop immediately.
++When only one merge base is needed, the walk is in the
++finite-generation region, and the queue uses generation ordering,
++the first candidate found is necessarily the highest-generation
++common ancestor. No remaining commit in the queue can be a
++descendant of this candidate (generation ordering guarantees
++children are visited first), so it cannot be redundant and the walk
++can stop immediately.
++
++This optimization is NOT safe when the date-ordering fallback is
++active, because commit-date order can visit a deeper ancestor
++before a shallower one -- see <<date-ordering-fallback>>.
++
++[[date-ordering-fallback]]
++Date-ordering fallback
++----------------------
++
++When `min_generation` is zero and the commit-graph does not contain
++corrected commit dates (generation number v1, which stores only
++topological levels), `paint_down_to_common()` replaces the default
++generation-ordered comparator with `compare_commits_by_commit_date`.
++
++This was introduced as a performance heuristic: topological levels
++are coarser than commit dates, so date ordering can reach merge
++bases in fewer steps when timestamps are well-behaved. However,
++commit dates are not required to be monotonic -- a parent can have
++a later date than its child (clock skew, rebases, etc.) -- so the
++queue may visit commits out of topological order.
++
++This disables optimizations that depend on generation ordering:
++
++ 1. *Single result*: the first merge-base candidate found may not
++ be the shallowest, because a deeper ancestor with a higher
++ commit date can be dequeued first.
++
++ 2. *Side-exhaustion* (see subsequent commits): one paint side can
++ appear to drain from the queue while commits from that side are
++ still waiting with lower dates, causing premature termination.
+
+Related documentation
+---------------------
-: ---------- > 2: 143f5e0cc1 test-lib-functions: improve diagnostic output for trace2 data assertions
2: 1a0154b406 ! 3: eec4a9d926 t6600: add test cases for side-exhaustion edge cases
@@ t/t6600-test-reach.sh: test_expect_success 'setup' '
+ pi_x="$(cat pi-X-oid)" &&
+ git branch -f pi-X-br "$pi_x" &&
+ git tag pi-X "$pi_x" &&
-+
git commit-graph write --reachable &&
mv .git/objects/info/commit-graph commit-graph-full &&
chmod u+w commit-graph-full &&
3: 017bf156c5 ! 4: 7f0efe6c73 t6099, t6600: add side-exhaustion regression tests
@@ t/t6099-merge-base-side-exhaustion.sh (new)
+'
+
+test_done
-
- ## t/t6600-test-reach.sh ##
-@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:infinity-both-sides' '
- test_all_modes get_merge_bases_many
- '
-
-+test_expect_success 'setup mixed finite/INFINITY topology' '
-+ # Create a commit outside all saved commit-graph files so it always
-+ # has INFINITY generation, while its parent (ps-X) is in the graph
-+ # with a finite generation. Use the ps-* orphan topology so we do
-+ # not pollute the grid-based rev-list tests.
-+ git checkout ps-X &&
-+ test_env GIT_TEST_COMMIT_GRAPH= test_commit pm-INF
-+'
-+
-+test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
-+ # One tip (pm-INF) is outside the commit-graph with INFINITY
-+ # generation; the other (ps-B) is in the graph with finite
-+ # generation. The walk starts in the INFINITY region and crosses
-+ # into the finite region where side-exhaustion can fire.
-+ cat >input <<-\EOF &&
-+ A:pm-INF
-+ X:ps-B
-+ EOF
-+ {
-+ echo "get_merge_bases_many(A,X):" &&
-+ git rev-parse ps-X
-+ } >expect &&
-+ test_all_modes get_merge_bases_many
-+'
-+
- test_expect_success 'reduce_heads' '
- cat >input <<-\EOF &&
- X:commit-1-10
4: df3b090a2b ! 5: b9fb8bfe26 commit-reach: add trace2 instrumentation to paint_down_to_common()
@@ t/t6600-test-reach.sh: test_expect_success 'setup' '
+test_paint_down_steps () {
+ for mode in none full half no-gdat
+ do
-+ test_trace2_data paint_down_to_common steps "$1" \
-+ <"trace-mode-${mode}.txt" || return 1
++ test_trace2_data_singular paint_down_to_common steps "$1" \
++ "mode=$mode" <"trace-mode-${mode}.txt" || return 1
+ shift
+ done
+}
@@ t/t6600-test-reach.sh: test_expect_success 'in_merge_bases_many:self' '
'
test_expect_success 'is_descendant_of:hit' '
-@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:pending-stale' '
- echo "get_merge_bases_many(A,X):" &&
- git rev-parse ps-B
- } >expect &&
-- test_all_modes get_merge_bases_many
-+ test_all_modes get_merge_bases_many &&
-+ test_paint_down_steps 6 6 6 6
- '
-
- test_expect_success 'get_merge_bases_many:infinity-both-sides' '
@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:infinity-both-sides' '
- echo "get_merge_bases_many(A,X):" &&
- git rev-parse pi-B
- } >expect &&
-- test_all_modes get_merge_bases_many
-+ test_all_modes get_merge_bases_many &&
-+ test_paint_down_steps 5 5 5 5
+ test_all_modes get_merge_bases_many
'
- test_expect_success 'setup mixed finite/INFINITY topology' '
-@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
- echo "get_merge_bases_many(A,X):" &&
- git rev-parse ps-X
- } >expect &&
-- test_all_modes get_merge_bases_many
-+ test_all_modes get_merge_bases_many &&
-+ test_paint_down_steps 3 3 3 3
-+'
-+
+test_expect_success 'merge-base --all commit-walk steps' '
+ >input &&
+ git rev-parse commit-9-1 >expect &&
+ run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
+ test_paint_down_steps 81 80 81 81
- '
-
++'
++
test_expect_success 'reduce_heads' '
+ cat >input <<-\EOF &&
+ X:commit-1-10
-: ---------- > 6: c6e3cc13f7 t6600: add clock-skew topologies and step counts for edge cases
5: fed9f2c368 ! 7: 42a75899f2 commit-reach: introduce struct paint_state with per-side counters
@@ Commit message
earlier than the old code in some topologies (the popped stale
commit is never processed), so a few step counts drop by one.
- The existing nonstale_queue is left in place for ahead_behind().
+ The existing nonstale_queue is left in place for ahead_behind(),
+ though nonstale_queue_put_dedup() and nonstale_queue_get_dedup()
+ became unused and are removed.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
@@ Documentation/technical/paint-down-to-common.adoc: re-enqueued is bounded by the
4. Single result: the caller only needs one merge base, one has
## commit-reach.c ##
-@@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
- return commit;
+@@ commit-reach.c: static void clear_nonstale_queue(struct nonstale_queue *queue)
+ queue->max_nonstale = NULL;
}
+-static void nonstale_queue_put_dedup(struct nonstale_queue *queue,
+- struct commit *c)
+/*
+ * Priority queue with per-side commit counters for paint_down_to_common().
+ * Each non-stale queued commit occupies exactly one bucket: PARENT1-only,
@@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
+ size_t parent1_count;
+ size_t parent2_count;
+ size_t mb_candidate_count;
++ int gen_ordered;
+};
+
+static void paint_count_update(struct paint_state *state,
+ unsigned flags, int delta)
-+{
+ {
+- if (c->object.flags & ENQUEUED)
+- return;
+- c->object.flags |= ENQUEUED;
+- nonstale_queue_put(queue, c);
+ switch (flags & (PARENT1 | PARENT2 | STALE)) {
+ case PARENT1:
+ state->parent1_count += delta;
@@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
+ default:
+ BUG("unexpected paint state");
+ }
-+}
-+
+ }
+
+-static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
+static void paint_queue_put(struct paint_state *state,
+ struct commit *c, unsigned add_flags)
-+{
+ {
+- struct commit *commit = nonstale_queue_get(queue);
+ unsigned old_flags = c->object.flags;
+ c->object.flags |= add_flags;
+
@@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
+ paint_count_update(state, c->object.flags, 1);
+ }
+}
-+
+
+- if (commit)
+- commit->object.flags &= ~ENQUEUED;
+static struct commit *paint_queue_get(struct paint_state *state)
+{
+ struct commit *commit = prio_queue_get(&state->queue);
@@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
+ return NULL;
+
+ paint_count_update(state, commit->object.flags, -1);
-+ return commit;
-+}
-+
- /*
- * See Documentation/technical/paint-down-to-common.adoc
- *
+ return commit;
+ }
+
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
enum merge_base_flags mb_flags,
struct commit_list **result)
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
- struct nonstale_queue queue = {
- { compare_commits_by_gen_then_commit_date }
+ struct paint_state state = {
-+ .queue = { compare_commits_by_gen_then_commit_date }
++ .queue = { compare_commits_by_gen_then_commit_date },
++ .gen_ordered = 1,
};
+ struct commit *commit;
int i;
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
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;
++ if (!min_generation && !corrected_commit_dates_enabled(r)) {
+ state.queue.compare = compare_commits_by_commit_date;
++ state.gen_ordered = 0;
++ }
one->object.flags |= PARENT1;
if (!n) {
@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:infinity-both-s
'
test_expect_success 'setup mixed finite/INFINITY topology' '
+@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all with clock skew returns wrong merge base (
+ >input &&
+ git rev-parse se2-MB1 >expect &&
+ run_all_modes git merge-base --all se2-A se2-B &&
+- test_paint_down_steps 8 7 8 8
++ test_paint_down_steps 8 6 8 8
+ '
+
+ test_expect_success 'reduce_heads' '
6: 4db485b48a < -: ---------- commit-reach: remove unused nonstale_queue dedup wrappers
7: 4506780649 ! 8: f8f00b7bcc commit-reach: terminate merge-base walk when one paint side is exhausted
@@ commit-reach.c: static struct commit *paint_queue_get(struct paint_state *state)
+
+ /* one side is exhausted */
+ if ((!state->parent1_count || !state->parent2_count) &&
++ state->gen_ordered &&
+ commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
+ return NULL;
+ }
@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps'
git rev-parse commit-9-1 >expect &&
run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
- test_paint_down_steps 81 80 81 81
-+ test_paint_down_steps 81 9 57 10
++ test_paint_down_steps 81 9 57 81
'
- test_expect_success 'reduce_heads' '
+ test_expect_success 'merge-base --all with clock skew and v1 commit-graph (side-exhaustion)' '
8: 8dd15d44e6 ! 9: b45c302caa commit-reach: move min_generation check into paint_queue_get()
@@ Commit message
## commit-reach.c ##
@@ commit-reach.c: struct paint_state {
- size_t parent1_count;
size_t parent2_count;
size_t mb_candidate_count;
+ int gen_ordered;
+ timestamp_t min_generation;
+ timestamp_t last_gen;
};
@@ commit-reach.c: static void paint_queue_put(struct paint_state *state,
if (!state->mb_candidate_count) {
/* only stale entries remain */
@@ commit-reach.c: static struct commit *paint_queue_get(struct paint_state *state)
-
/* one side is exhausted */
if ((!state->parent1_count || !state->parent2_count) &&
+ state->gen_ordered &&
- commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
+ generation < GENERATION_NUMBER_INFINITY)
return NULL;
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
+ state.min_generation = min_generation;
+ state.last_gen = GENERATION_NUMBER_INFINITY;
- if (!min_generation && !corrected_commit_dates_enabled(r))
+ if (!min_generation && !corrected_commit_dates_enabled(r)) {
state.queue.compare = compare_commits_by_commit_date;
-
+ state.gen_ordered = 0;
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
while ((commit = paint_queue_get(&state))) {
struct commit_list *parents;
-: ---------- > 10: d68972b1d7 commit-reach: remove commit-date ordering fallback
--
gitgitgadget
^ permalink raw reply
* [PATCH v5 01/10] Documentation/technical: add paint-down-to-common doc
From: Kristofer Karlsson via GitGitGadget @ 2026-07-01 16:37 UTC (permalink / raw)
To: git; +Cc: Kristofer Karlsson, Kristofer Karlsson
In-Reply-To: <pull.2149.v5.git.1782923832.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add a technical document describing the paint_down_to_common()
algorithm used for merge-base computation, covering the paint
walk, generation number regions, and termination conditions.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
Documentation/Makefile | 1 +
Documentation/technical/meson.build | 1 +
.../technical/paint-down-to-common.adoc | 177 ++++++++++++++++++
commit-reach.c | 6 +-
4 files changed, 184 insertions(+), 1 deletion(-)
create mode 100644 Documentation/technical/paint-down-to-common.adoc
diff --git a/Documentation/Makefile b/Documentation/Makefile
index 2699f0b24a..f8dea4b395 100644
--- a/Documentation/Makefile
+++ b/Documentation/Makefile
@@ -129,6 +129,7 @@ TECH_DOCS += technical/long-running-process-protocol
TECH_DOCS += technical/multi-pack-index
TECH_DOCS += technical/packfile-uri
TECH_DOCS += technical/pack-heuristics
+TECH_DOCS += technical/paint-down-to-common
TECH_DOCS += technical/parallel-checkout
TECH_DOCS += technical/partial-clone
TECH_DOCS += technical/platform-support
diff --git a/Documentation/technical/meson.build b/Documentation/technical/meson.build
index ec07088c57..9ce11d5e48 100644
--- a/Documentation/technical/meson.build
+++ b/Documentation/technical/meson.build
@@ -18,6 +18,7 @@ articles = [
'multi-pack-index.adoc',
'packfile-uri.adoc',
'pack-heuristics.adoc',
+ 'paint-down-to-common.adoc',
'parallel-checkout.adoc',
'partial-clone.adoc',
'platform-support.adoc',
diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
new file mode 100644
index 0000000000..ff015c5c8f
--- /dev/null
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -0,0 +1,177 @@
+Merge-Base Computation and paint_down_to_common()
+==================================================
+
+The function `paint_down_to_common()` in `commit-reach.c` computes merge
+bases by walking the commit graph backwards from two sets of tips and
+finding where their ancestry meets.
+
+Use cases
+---------
+
+Computing merge bases is used in two different ways:
+
+ 1. *Finding all merge bases* (`merge-base --all`, `merge-tree`,
+ `merge`, `rebase`). A merge base is a common ancestor that is
+ not itself an ancestor of another common ancestor.
+
+ 2. *Ancestry checks* (`in_merge_bases`, used by `merge-base
+ --is-ancestor`, `branch -d`, `fetch`). These ask: "is commit A
+ an ancestor of commit B?" If a common ancestor equals one of the
+ inputs, that input is necessarily the only merge base -- no other
+ common ancestor can be both as recent and not an ancestor of it.
+
+Both use cases share the same algorithm and implementation.
+
+Algorithm
+---------
+
+Given a commit `one` and a set of commits `twos[]`, the walk paints
+commits with two colors:
+
+ - PARENT1: reachable from `one`
+ - PARENT2: reachable from any commit in `twos[]`
+
+The walk uses a priority queue ordered by generation number
+(highest first), breaking ties by commit date. Each step dequeues
+the highest-priority commit (this is when we say a commit is
+"visited") and propagates its paint flags to its parents, enqueuing
+them if they gained new flags. When a commit receives both PARENT1
+and PARENT2, it is a merge-base candidate. A candidate gains the
+STALE flag so its ancestors propagate staleness -- any deeper common
+ancestor is necessarily redundant.
+
+NOTE: When the commit-graph uses only topological levels (generation
+number v1) and the caller passes `min_generation = 0`, a legacy
+fallback replaces the generation-ordered comparator with a pure
+commit-date comparator. This breaks the ordering invariants
+described below -- see <<date-ordering-fallback>>.
+
+[[generation-regions]]
+INFINITY and finite generation regions
+--------------------------------------
+
+The properties in this section assume generation-number ordering (the
+default comparator). They do NOT hold when the date-ordering fallback
+is active -- see <<date-ordering-fallback>>.
+
+The commit-graph stores a generation number for each commit. Commits
+not in the commit-graph have generation `GENERATION_NUMBER_INFINITY`. The
+graph is closed under reachability: if a commit is in the graph, all
+its ancestors are too. This partitions the commit graph into two regions:
+
+....
+ +---------------------------------------+
+ | INFINITY region |
+ | generation = INFINITY |
+ | queue order: heuristic (commit date) |
+ +---------------------------------------+
+ |
+ v
+ +---------------------------------------+
+ | Finite region |
+ | generation = finite |
+ | queue order: topological |
+ +---------------------------------------+
+....
+
+When the commit-graph is enabled, the INFINITY region is typically
+very small -- it only contains commits added since the last
+commit-graph refresh.
+
+All reachable INFINITY-generation commits are visited before any
+finite-generation commit, because INFINITY is larger than any finite
+value. Once the walk crosses into the finite region, it stays there.
+
+In the finite region, generation ordering guarantees topological
+traversal: children are always visited before their parents. This
+means that paint on already-visited commits is final -- no future
+traversal step can add paint to them.
+
+In the INFINITY region, commit-date ordering can violate this: a
+parent with a later date can be visited before a child with an earlier
+date. Paint flags are therefore NOT final at visit time, and a
+commit visited with only one side's paint may later gain the other.
+
+Paint flags are only added, never removed. Since each flag can be set
+at most once per commit, the number of times a commit can be
+re-enqueued is bounded by the number of flag transitions.
+
+Termination
+-----------
+
+The walk uses a `nonstale_queue` wrapper around `prio_queue` that
+tracks `max_nonstale`: the lowest-priority non-stale commit enqueued
+so far. Once that commit is dequeued, every remaining entry is known
+to be STALE and the loop terminates. Specifically, the main loop
+ends when one of the following conditions holds:
+
+ 1. The queue is empty.
+ 2. `max_nonstale` has been dequeued, meaning the queue only contains
+ STALE entries.
+ 3. Generation cutoff: the dequeued commit's generation is below
+ a caller-supplied `min_generation` threshold.
+ 4. Single result: the caller only needs one merge base, one has
+ been found, and the walk has entered the finite-generation
+ region.
+
+Stale entry condition
+~~~~~~~~~~~~~~~~~~~~~
+Once all queued entries are stale, no new merge-base candidates can
+be discovered -- that requires at least one non-stale commit from
+each side meeting. Continuing the walk could still invalidate
+existing candidates by proving one is an ancestor of another, but
+`remove_redundant()` handles that as a post-processing step, so it
+is safe to exit early.
+
+Generation cutoff
+~~~~~~~~~~~~~~~~~
+Some callers (notably `remove_redundant()`) supply a `min_generation`
+threshold -- the minimum generation of the input commits. No merge
+base can have a generation below this threshold, so the walk
+terminates as soon as it dequeues such a commit.
+
+Single result
+~~~~~~~~~~~~~
+When only one merge base is needed, the walk is in the
+finite-generation region, and the queue uses generation ordering,
+the first candidate found is necessarily the highest-generation
+common ancestor. No remaining commit in the queue can be a
+descendant of this candidate (generation ordering guarantees
+children are visited first), so it cannot be redundant and the walk
+can stop immediately.
+
+This optimization is NOT safe when the date-ordering fallback is
+active, because commit-date order can visit a deeper ancestor
+before a shallower one -- see <<date-ordering-fallback>>.
+
+[[date-ordering-fallback]]
+Date-ordering fallback
+----------------------
+
+When `min_generation` is zero and the commit-graph does not contain
+corrected commit dates (generation number v1, which stores only
+topological levels), `paint_down_to_common()` replaces the default
+generation-ordered comparator with `compare_commits_by_commit_date`.
+
+This was introduced as a performance heuristic: topological levels
+are coarser than commit dates, so date ordering can reach merge
+bases in fewer steps when timestamps are well-behaved. However,
+commit dates are not required to be monotonic -- a parent can have
+a later date than its child (clock skew, rebases, etc.) -- so the
+queue may visit commits out of topological order.
+
+This disables optimizations that depend on generation ordering:
+
+ 1. *Single result*: the first merge-base candidate found may not
+ be the shallowest, because a deeper ancestor with a higher
+ commit date can be dequeued first.
+
+ 2. *Side-exhaustion* (see subsequent commits): one paint side can
+ appear to drain from the queue while commits from that side are
+ still waiting with lower dates, causing premature termination.
+
+Related documentation
+---------------------
+
+ - `Documentation/technical/commit-graph.adoc` -- generation numbers
+ and the reachability closure property.
diff --git a/commit-reach.c b/commit-reach.c
index 5df471a313..a9483759e0 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -96,7 +96,11 @@ static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
return commit;
}
-/* all input commits in one and twos[] must have been parsed! */
+/*
+ * See Documentation/technical/paint-down-to-common.adoc
+ *
+ * All input commits in one and twos[] must have been parsed!
+ */
static int paint_down_to_common(struct repository *r,
struct commit *one, int n,
struct commit **twos,
--
gitgitgadget
^ permalink raw reply related
* [PATCH v5 02/10] test-lib-functions: improve diagnostic output for trace2 data assertions
From: Kristofer Karlsson via GitGitGadget @ 2026-07-01 16:37 UTC (permalink / raw)
To: git; +Cc: Kristofer Karlsson, Kristofer Karlsson
In-Reply-To: <pull.2149.v5.git.1782923832.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
test_trace2_data is a bare grep that silently exits on failure.
Add a more informative variant that verifies the event appears
exactly once and reports what went wrong: key not found, multiple
entries, or value mismatch. Diagnostics go to FD 4 like test_grep.
Before (value mismatch):
$ test_trace2_data status count/changed 999 <trace2.txt
$ echo $?
1
(no output)
After:
$ test_trace2_data_singular status count/changed 999 <trace2.txt
error: trace2 data 'status/count/changed'
expected: 999
actual: 0
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
t/test-lib-functions.sh | 36 ++++++++++++++++++++++++++++++++++++
1 file changed, 36 insertions(+)
diff --git a/t/test-lib-functions.sh b/t/test-lib-functions.sh
index 809c662124..3521efe5d7 100644
--- a/t/test-lib-functions.sh
+++ b/t/test-lib-functions.sh
@@ -1996,6 +1996,42 @@ test_trace2_data () {
grep -e '"category":"'"$1"'","key":"'"$2"'","value":"'"$3"'"'
}
+# Check that the given trace2 data event has the expected value and
+# appears exactly once. Produces a diagnostic on failure.
+#
+# test_trace2_data_singular <category> <key> <value> [<label>]
+test_trace2_data_singular () {
+ local category="$1" key="$2" expect_val="$3"
+ local label_suffix="${4:+ [$4]}"
+ local kv_pattern='"category":"'"$category"'","key":"'"$key"'","value":"\([^"]*\)"'
+ local actual
+
+ actual=$(sed -n "s|.*${kv_pattern}.*|\1|p") &&
+
+ if test -z "$actual"
+ then
+ echo >&4 "error: trace2 data '$category/$key'$label_suffix not found"
+ return 1
+ fi &&
+
+ case "$actual" in
+ *"
+"*)
+ echo >&4 "error: trace2 data '$category/$key'$label_suffix has multiple entries, expected 1"
+ printf '%s\n' "$actual" | sed 's/^/ actual: /' >&4
+ return 1
+ ;;
+ esac &&
+
+ if test "$actual" != "$expect_val"
+ then
+ echo >&4 "error: trace2 data '$category/$key'$label_suffix"
+ echo >&4 " expected: $expect_val"
+ echo >&4 " actual: $actual"
+ return 1
+ fi
+}
+
# Given a GIT_TRACE2_EVENT log over stdin, writes to stdout a list of URLs
# sent to git-remote-https child processes.
test_remote_https_urls() {
--
gitgitgadget
^ permalink raw reply related
* [PATCH v5 03/10] t6600: add test cases for side-exhaustion edge cases
From: Elijah Newren via GitGitGadget @ 2026-07-01 16:37 UTC (permalink / raw)
To: git; +Cc: Kristofer Karlsson, Elijah Newren
In-Reply-To: <pull.2149.v5.git.1782923832.gitgitgadget@gmail.com>
From: Elijah Newren <newren@gmail.com>
Add test cases to t6600-test-reach.sh that exercise edge cases in the
side-exhaustion optimization for paint_down_to_common():
- in_merge_bases_many:self: commit is both A and one of the X inputs
- get_merge_bases_many:duplicate-twos: duplicate entries in X list
- get_merge_bases_many:pending-stale: STALE transition on an
already-painted commit (ps-* diamond topology)
- get_merge_bases_many:infinity-both-sides: both tips outside the
commit-graph with non-monotonic dates (pi-* topology)
Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
t/t6600-test-reach.sh | 110 ++++++++++++++++++++++++++++++++++++++++++
1 file changed, 110 insertions(+)
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index b5b314e570..b536a5952a 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -49,6 +49,61 @@ test_expect_success 'setup' '
git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i || return 1
done
done &&
+
+ # Build a small side topology to exercise the (PARENT1|PARENT2) ->
+ # (PARENT1|PARENT2|STALE) transition in paint_down_to_common(); the
+ # 10x10 grid above does not exercise it because no merge-base candidate
+ # there is a descendant of another, so STALE never reaches a
+ # still-pending candidate.
+ #
+ # ps-X
+ # /|\
+ # / | \
+ # ps-Z ps-B ps-W
+ # | / \ |
+ # | / \ |
+ # |/ \|
+ # ps-T1 ps-T2
+ #
+ # where ps-T1=merge(ps-Z,ps-B), ps-T2=merge(ps-W,ps-B), so
+ # merge-base(ps-T1,ps-T2) = ps-B. During the walk, ps-X transitions
+ # to (PARENT1|PARENT2) via ps-Z and ps-W before ps-B is dequeued;
+ # then the STALE-walk from ps-B transitions ps-X to
+ # (PARENT1|PARENT2|STALE).
+ git checkout --orphan ps-orphan &&
+ test_commit ps-X &&
+ git checkout -b ps-B-br ps-X && test_commit ps-B &&
+ git checkout -b ps-Z-br ps-X && test_commit ps-Z &&
+ git checkout -b ps-W-br ps-X && test_commit ps-W &&
+ git checkout -b ps-T1 ps-Z &&
+ git merge --no-ff -m ps-T1 ps-B &&
+ git checkout -b ps-T2 ps-W &&
+ git merge --no-ff -m ps-T2 ps-B &&
+
+ # Build a side topology that lives entirely outside the half
+ # commit-graph and has non-monotonic commit dates, to exercise the
+ # INFINITY-gate in paint_down_to_common. With both tips outside
+ # the graph, generation is INFINITY and the queue falls back to
+ # commit-date order, which here is non-monotonic.
+ #
+ # pi-X (date 500, PARENT1 tip) --> pi-P, pi-D
+ # pi-D (date 480) --> pi-C
+ # pi-C (date 200) --> pi-B
+ # pi-B (date 100, PARENT2 tip) --> pi-P
+ # pi-P (date 450, root)
+ #
+ # merge-base(pi-X, pi-B) = pi-B (it is an ancestor of pi-X and is
+ # itself one of the queried tips).
+ git checkout --orphan pi-orphan &&
+ test_commit --date "@450 +0000" pi-P &&
+ test_commit --date "@100 +0000" pi-B &&
+ test_commit --date "@200 +0000" pi-C &&
+ test_commit --date "@480 +0000" pi-D &&
+ GIT_AUTHOR_DATE="@500 +0000" GIT_COMMITTER_DATE="@500 +0000" \
+ git commit-tree -p pi-D -p pi-P -m pi-X pi-D^{tree} >pi-X-oid &&
+ pi_x="$(cat pi-X-oid)" &&
+ git branch -f pi-X-br "$pi_x" &&
+ git tag pi-X "$pi_x" &&
git commit-graph write --reachable &&
mv .git/objects/info/commit-graph commit-graph-full &&
chmod u+w commit-graph-full &&
@@ -146,6 +201,16 @@ test_expect_success 'in_merge_bases_many:miss-heuristic' '
test_all_modes in_merge_bases_many
'
+test_expect_success 'in_merge_bases_many:self' '
+ cat >input <<-\EOF &&
+ A:commit-6-8
+ X:commit-5-9
+ X:commit-6-8
+ EOF
+ echo "in_merge_bases_many(A,X):1" >expect &&
+ test_all_modes in_merge_bases_many
+'
+
test_expect_success 'is_descendant_of:hit' '
cat >input <<-\EOF &&
A:commit-5-7
@@ -183,6 +248,51 @@ test_expect_success 'get_merge_bases_many' '
test_all_modes get_merge_bases_many
'
+test_expect_success 'get_merge_bases_many:duplicate-twos' '
+ cat >input <<-\EOF &&
+ A:commit-5-7
+ X:commit-4-8
+ X:commit-4-8
+ X:commit-6-6
+ X:commit-6-6
+ X:commit-8-3
+ EOF
+ {
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse commit-5-6 \
+ commit-4-7 | sort
+ } >expect &&
+ test_all_modes get_merge_bases_many
+'
+
+test_expect_success 'get_merge_bases_many:pending-stale' '
+ # Exercises the (PARENT1|PARENT2) -> (...|STALE) transition path in
+ # paint_down_to_common(). See the topology comment in the setup test.
+ cat >input <<-\EOF &&
+ A:ps-T1
+ X:ps-T2
+ EOF
+ {
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse ps-B
+ } >expect &&
+ test_all_modes get_merge_bases_many
+'
+
+test_expect_success 'get_merge_bases_many:infinity-both-sides' '
+ # Exercises the push-time INFINITY-gate in paint_down_to_common(). See
+ # the pi-* topology comment in the setup test.
+ cat >input <<-\EOF &&
+ A:pi-X
+ X:pi-B
+ EOF
+ {
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse pi-B
+ } >expect &&
+ test_all_modes get_merge_bases_many
+'
+
test_expect_success 'reduce_heads' '
cat >input <<-\EOF &&
X:commit-1-10
--
gitgitgadget
^ permalink raw reply related
* [PATCH v5 04/10] t6099, t6600: add side-exhaustion regression tests
From: Kristofer Karlsson via GitGitGadget @ 2026-07-01 16:37 UTC (permalink / raw)
To: git; +Cc: Kristofer Karlsson, Kristofer Karlsson
In-Reply-To: <pull.2149.v5.git.1782923832.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add t6099 to test the case where multiple merge-base candidates exist
and one is an ancestor of another. This exercises the side-exhaustion
optimization in paint_down_to_common together with the
remove_redundant safety net in get_merge_bases_many_0.
Add a mixed finite/INFINITY test to t6600 where one tip is outside
the commit-graph (INFINITY generation) and the other is inside.
This exercises the region transition: the walk starts in the
INFINITY region where side-exhaustion is disabled, then crosses
into the finite region where it can fire.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
t/meson.build | 1 +
t/t6099-merge-base-side-exhaustion.sh | 82 +++++++++++++++++++++++++++
2 files changed, 83 insertions(+)
create mode 100755 t/t6099-merge-base-side-exhaustion.sh
diff --git a/t/meson.build b/t/meson.build
index 3219264fe7..ee6ebdffb9 100644
--- a/t/meson.build
+++ b/t/meson.build
@@ -786,6 +786,7 @@ integration_tests = [
't6041-bisect-submodule.sh',
't6050-replace.sh',
't6060-merge-index.sh',
+ 't6099-merge-base-side-exhaustion.sh',
't6100-rev-list-in-order.sh',
't6101-rev-parse-parents.sh',
't6102-rev-list-unexpected-objects.sh',
diff --git a/t/t6099-merge-base-side-exhaustion.sh b/t/t6099-merge-base-side-exhaustion.sh
new file mode 100755
index 0000000000..4f1e0d50ef
--- /dev/null
+++ b/t/t6099-merge-base-side-exhaustion.sh
@@ -0,0 +1,82 @@
+#!/bin/sh
+
+test_description='merge-base with ancestor among merge-base candidates
+
+Test that merge-base --all correctly handles cases where
+multiple merge-base candidates exist and one is an ancestor
+of another. The side-exhaustion optimization in
+paint_down_to_common may exit before STALE propagation
+removes the ancestor, but remove_redundant catches it.
+
+Graph shape (parents are below children):
+
+ A ----------- X
+ |\ /|
+ | B---------/ |
+ | | |
+ e2 \ f2
+ | | |
+ e1 d1 f1
+ \ | /
+ \ | /
+ \| /
+ C
+
+A and X are the two tips.
+B and C are both reachable from A and X.
+B reaches C through d1.
+Only B should appear in merge-base --all output.
+'
+
+GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main
+export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
+
+TEST_PASSES_SANITIZE_LEAK=true
+. ./test-lib.sh
+
+test_expect_success 'setup ancestor merge-base candidate' '
+ test_commit C &&
+
+ git checkout -b d-chain HEAD &&
+ test_commit d1 &&
+ test_commit B &&
+
+ git checkout -b e-path C &&
+ test_commit e1 &&
+ test_commit e2 &&
+
+ git checkout -b f-path C &&
+ test_commit f1 &&
+ test_commit f2 &&
+
+ git checkout -b branch-A e-path &&
+ test_merge A B &&
+
+ git checkout -b branch-X f-path &&
+ test_merge X B &&
+
+ git commit-graph write --reachable
+'
+
+test_expect_success 'merge-base --all excludes ancestor candidate' '
+ git rev-parse B >expected &&
+ git merge-base --all A X >actual &&
+ test_cmp expected actual
+'
+
+test_expect_success 'merge-base (single) finds shallowest' '
+ git rev-parse B >expected &&
+ git merge-base A X >actual &&
+ test_cmp expected actual
+'
+
+# Without commit-graph: generation numbers are INFINITY,
+# side-exhaustion optimization does not fire.
+test_expect_success 'merge-base --all without commit-graph' '
+ rm -f .git/objects/info/commit-graph &&
+ git rev-parse B >expected &&
+ git merge-base --all A X >actual &&
+ test_cmp expected actual
+'
+
+test_done
--
gitgitgadget
^ permalink raw reply related
* [PATCH v5 05/10] commit-reach: add trace2 instrumentation to paint_down_to_common()
From: Kristofer Karlsson via GitGitGadget @ 2026-07-01 16:37 UTC (permalink / raw)
To: git; +Cc: Kristofer Karlsson, Kristofer Karlsson
In-Reply-To: <pull.2149.v5.git.1782923832.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add a step counter and trace2_data_intmax() call so that the number
of commits visited during the paint walk is observable via
GIT_TRACE2_EVENT. This provides a way to measure the impact of
future optimizations without relying on wall-clock benchmarks alone.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
commit-reach.c | 5 +++++
t/t6600-test-reach.sh | 44 ++++++++++++++++++++++++++++++-------------
2 files changed, 36 insertions(+), 13 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index a9483759e0..f6a438550b 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -11,6 +11,7 @@
#include "tag.h"
#include "commit-reach.h"
#include "ewah/ewok.h"
+#include "trace2.h"
/* Remember to update object flag allocation in object.h */
#define PARENT1 (1u<<16)
@@ -112,6 +113,7 @@ static int paint_down_to_common(struct repository *r,
{ compare_commits_by_gen_then_commit_date }
};
int i;
+ int steps = 0;
timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
struct commit_list **tail = result;
@@ -135,6 +137,7 @@ static int paint_down_to_common(struct repository *r,
struct commit_list *parents;
int flags;
timestamp_t generation = commit_graph_generation(commit);
+ steps++;
if (min_generation && generation > last_gen)
BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
@@ -190,6 +193,8 @@ static int paint_down_to_common(struct repository *r,
}
clear_nonstale_queue(&queue);
+ trace2_data_intmax("paint_down_to_common", r,
+ "steps", steps);
commit_list_sort_by_date(result);
return 0;
}
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index b536a5952a..7a9a35023f 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -117,24 +117,34 @@ test_expect_success 'setup' '
'
run_all_modes () {
- test_when_finished rm -rf .git/objects/info/commit-graph &&
- "$@" <input >actual &&
- test_cmp expect actual &&
- cp commit-graph-full .git/objects/info/commit-graph &&
- "$@" <input >actual &&
- test_cmp expect actual &&
- cp commit-graph-half .git/objects/info/commit-graph &&
- "$@" <input >actual &&
- test_cmp expect actual &&
- cp commit-graph-no-gdat .git/objects/info/commit-graph &&
- "$@" <input >actual &&
- test_cmp expect actual
+ graph=.git/objects/info/commit-graph &&
+ test_when_finished rm -rf "$graph" "${graph}s" &&
+ rm -f trace-mode-*.txt &&
+
+ for mode in none full half no-gdat
+ do
+ rm -rf "$graph" "${graph}s" &&
+ cp "commit-graph-${mode}" "$graph" 2>/dev/null ||
+ true &&
+ GIT_TRACE2_EVENT="$(pwd)/trace-mode-${mode}.txt" \
+ "$@" <input >actual &&
+ test_cmp expect actual || return 1
+ done
}
test_all_modes () {
run_all_modes test-tool reach "$@"
}
+test_paint_down_steps () {
+ for mode in none full half no-gdat
+ do
+ test_trace2_data_singular paint_down_to_common steps "$1" \
+ "mode=$mode" <"trace-mode-${mode}.txt" || return 1
+ shift
+ done
+}
+
test_expect_success 'ref_newer:miss' '
cat >input <<-\EOF &&
A:commit-5-7
@@ -208,7 +218,8 @@ test_expect_success 'in_merge_bases_many:self' '
X:commit-6-8
EOF
echo "in_merge_bases_many(A,X):1" >expect &&
- test_all_modes in_merge_bases_many
+ test_all_modes in_merge_bases_many &&
+ test_paint_down_steps 45 2 25 3
'
test_expect_success 'is_descendant_of:hit' '
@@ -293,6 +304,13 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
test_all_modes get_merge_bases_many
'
+test_expect_success 'merge-base --all commit-walk steps' '
+ >input &&
+ git rev-parse commit-9-1 >expect &&
+ run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
+ test_paint_down_steps 81 80 81 81
+'
+
test_expect_success 'reduce_heads' '
cat >input <<-\EOF &&
X:commit-1-10
--
gitgitgadget
^ permalink raw reply related
* [PATCH v5 06/10] t6600: add clock-skew topologies and step counts for edge cases
From: Kristofer Karlsson via GitGitGadget @ 2026-07-01 16:37 UTC (permalink / raw)
To: git; +Cc: Kristofer Karlsson, Kristofer Karlsson
In-Reply-To: <pull.2149.v5.git.1782923832.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add topologies and tests exercising paint_down_to_common() under
clock skew, where commit-date ordering (v1 commit-graph without
corrected commit dates) violates the topological invariant that
children are dequeued before parents:
- se-*: side-exhaustion fires too early when one paint side fully
drains from the queue while a low-date ancestor on the other
side is still queued
- se2-*: side-exhaustion returns a too-deep merge base because
the correct (closer) base never receives both paint sides
Also add step counts to the edge-case tests from the previous
commit, a mixed finite/INFINITY generation topology exercising
the transition from INFINITY-generation commits to graph-backed
commits, and step counts for the grid-based merge-base test.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
t/t6600-test-reach.sh | 141 +++++++++++++++++++++++++++++++++++++++++-
1 file changed, 139 insertions(+), 2 deletions(-)
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 7a9a35023f..26a2a0a62f 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -104,6 +104,85 @@ test_expect_success 'setup' '
pi_x="$(cat pi-X-oid)" &&
git branch -f pi-X-br "$pi_x" &&
git tag pi-X "$pi_x" &&
+
+ # 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 </dev/null) &&
+ skew_commit () {
+ GIT_COMMITTER_DATE="@$1 +0000" GIT_AUTHOR_DATE="@$1 +0000" \
+ git commit-tree -m "$2" "$skew_tree" $3 $4 $5 $6
+ } &&
+ skew_root=$(skew_commit 1000 root) &&
+ skew_M1=$(skew_commit 5000 M1 -p "$skew_root") &&
+ skew_M2=$(skew_commit 2000 M2 -p "$skew_M1") &&
+ skew_A=$(skew_commit 6000 A -p "$skew_M1" -p "$skew_M2") &&
+ skew_B=$(skew_commit 6000 B -p "$skew_M2") &&
+ skew_D=$(skew_commit 6000 D -p "$skew_M1") &&
+ skew_P1=$(skew_commit 7000 P1 -p "$skew_A") &&
+ skew_P2=$(skew_commit 7000 P2 -p "$skew_B" -p "$skew_D") &&
+ git branch -f skew-P1 "$skew_P1" &&
+ git branch -f skew-P2 "$skew_P2" &&
+ git tag skew-M2 "$skew_M2" &&
+
+ # Build a topology where clock skew causes the side-exhaustion
+ # optimization to fire too early with date ordering (v1 graph).
+ # D is the correct merge base but has a higher committer date
+ # than C (its child), so D is dequeued before C. The P2 side
+ # (B -> D -> root) fully drains while C (P1-only) is still
+ # queued. Side-exhaustion fires, missing D as a merge base.
+ #
+ # se-A (date 7000) --> se-C (date 3000) --> se-D (date 5000) --> se-root (date 4000)
+ # se-B (date 6000) --> se-D
+ #
+ se_root=$(skew_commit 4000 se-root) &&
+ se_D=$(skew_commit 5000 se-D -p "$se_root") &&
+ se_C=$(skew_commit 3000 se-C -p "$se_D") &&
+ se_A=$(skew_commit 7000 se-A -p "$se_C") &&
+ se_B=$(skew_commit 6000 se-B -p "$se_D") &&
+ git branch -f se-A "$se_A" &&
+ git branch -f se-B "$se_B" &&
+ git tag se-D "$se_D" &&
+
+ # Build a topology where side-exhaustion with date ordering
+ # returns a wrong (too-deep) merge base. MB1 is the correct
+ # merge base; MB2 is its parent and should be filtered as
+ # redundant. A reaches MB2 via E (high date) and MB1 via C
+ # (low date). B reaches MB1 via D. With date ordering, the
+ # P2 side drains after MB2 is found but before C is dequeued,
+ # so MB1 never receives P1 paint. Result: MB2 (wrong).
+ #
+ # se2-A (date 8000) --> se2-C (date 2000) --> se2-MB1 (date 5000) --> se2-MB2 (date 4000) --> se2-root (date 1000)
+ # se2-A --> se2-E (date 6500) --> se2-MB2
+ # se2-B (date 7000) --> se2-D (date 6000) --> se2-MB1
+ #
+ se2_root=$(skew_commit 1000 se2-root) &&
+ se2_MB2=$(skew_commit 4000 se2-MB2 -p "$se2_root") &&
+ se2_MB1=$(skew_commit 5000 se2-MB1 -p "$se2_MB2") &&
+ se2_C=$(skew_commit 2000 se2-C -p "$se2_MB1") &&
+ se2_D=$(skew_commit 6000 se2-D -p "$se2_MB1") &&
+ se2_E=$(skew_commit 6500 se2-E -p "$se2_MB2") &&
+ se2_A=$(skew_commit 8000 se2-A -p "$se2_C" -p "$se2_E") &&
+ se2_B=$(skew_commit 7000 se2-B -p "$se2_D") &&
+ git branch -f se2-A "$se2_A" &&
+ git branch -f se2-B "$se2_B" &&
+ git tag se2-MB1 "$se2_MB1" &&
git commit-graph write --reachable &&
mv .git/objects/info/commit-graph commit-graph-full &&
chmod u+w commit-graph-full &&
@@ -287,7 +366,8 @@ test_expect_success 'get_merge_bases_many:pending-stale' '
echo "get_merge_bases_many(A,X):" &&
git rev-parse ps-B
} >expect &&
- test_all_modes get_merge_bases_many
+ test_all_modes get_merge_bases_many &&
+ test_paint_down_steps 6 6 6 6
'
test_expect_success 'get_merge_bases_many:infinity-both-sides' '
@@ -301,7 +381,34 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
echo "get_merge_bases_many(A,X):" &&
git rev-parse pi-B
} >expect &&
- test_all_modes get_merge_bases_many
+ test_all_modes get_merge_bases_many &&
+ test_paint_down_steps 5 5 5 5
+'
+
+test_expect_success 'setup mixed finite/INFINITY topology' '
+ # Create a commit outside all saved commit-graph files so it always
+ # has INFINITY generation, while its parent (ps-X) is in the graph
+ # with a finite generation. Use the ps-* orphan topology so we do
+ # not pollute the grid-based rev-list tests.
+ git checkout ps-X &&
+ test_env GIT_TEST_COMMIT_GRAPH= test_commit pm-INF
+'
+
+test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
+ # One tip (pm-INF) is outside the commit-graph with INFINITY
+ # generation; the other (ps-B) is in the graph with finite
+ # generation. The walk starts in the INFINITY region and crosses
+ # into the finite region where side-exhaustion can fire.
+ cat >input <<-\EOF &&
+ A:pm-INF
+ X:ps-B
+ EOF
+ {
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse ps-X
+ } >expect &&
+ test_all_modes get_merge_bases_many &&
+ test_paint_down_steps 3 3 3 3
'
test_expect_success 'merge-base --all commit-walk steps' '
@@ -311,6 +418,36 @@ test_expect_success 'merge-base --all commit-walk steps' '
test_paint_down_steps 81 80 81 81
'
+test_expect_success 'merge-base --all with clock skew and v1 commit-graph (side-exhaustion)' '
+ # With date ordering (v1 graph), the side-exhaustion
+ # optimization can fire too early. In this topology, the P2
+ # side (se-B -> se-D -> se-root) fully drains from the queue
+ # while se-C (P1-only, low date) is still queued. With
+ # generation ordering, se-C would be dequeued before se-D
+ # (child before parent), propagating P1 to se-D and
+ # discovering the merge base. Date ordering violates this.
+ >input &&
+ git rev-parse se-D >expect &&
+ run_all_modes git merge-base --all se-A se-B &&
+ test_paint_down_steps 6 4 6 6
+'
+
+test_expect_success 'merge-base --all with clock skew returns wrong merge base (side-exhaustion)' '
+ # With date ordering (v1 graph), side-exhaustion causes
+ # merge-base --all to return MB2 (too deep) instead of MB1
+ # (the correct closest merge base). P1 paint reaches MB2
+ # via E (high date) before it reaches MB1 via C (low date).
+ # After MB2 is found as P1|P2, the P2 side drains and
+ # side-exhaustion fires while C is still in the queue.
+ # MB1 never receives P1 paint, so it is never identified
+ # as a merge base. remove_redundant cannot discard MB2
+ # because MB1 was never found.
+ >input &&
+ git rev-parse se2-MB1 >expect &&
+ run_all_modes git merge-base --all se2-A se2-B &&
+ test_paint_down_steps 8 7 8 8
+'
+
test_expect_success 'reduce_heads' '
cat >input <<-\EOF &&
X:commit-1-10
--
gitgitgadget
^ permalink raw reply related
* [PATCH v5 07/10] commit-reach: introduce struct paint_state with per-side counters
From: Kristofer Karlsson via GitGitGadget @ 2026-07-01 16:37 UTC (permalink / raw)
To: git; +Cc: Kristofer Karlsson, Kristofer Karlsson
In-Reply-To: <pull.2149.v5.git.1782923832.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add a paint_state struct for use by paint_down_to_common() that
wraps a prio_queue with per-side commit counters. Each non-stale
queued commit occupies exactly one counter bucket based on its
paint flags: PARENT1-only, PARENT2-only, or both sides (a pending
merge-base candidate).
The counters are maintained by paint_count_update() which adjusts
the appropriate bucket by a signed delta. An exhaustive switch on
the paint+stale bits documents all valid flag combinations in one
place.
Convert paint_down_to_common() to use paint_state. The loop now
drains the queue via paint_queue_get() which returns NULL when all
counters reach zero, replacing the old pointer-based termination
(max_nonstale). This is equivalent behavior -- both conditions
detect that no non-stale entries remain.
paint_queue_get() uses a "pop first" form: it dequeues a commit,
then checks the counters. This means the loop exits one iteration
earlier than the old code in some topologies (the popped stale
commit is never processed), so a few step counts drop by one.
The existing nonstale_queue is left in place for ahead_behind(),
though nonstale_queue_put_dedup() and nonstale_queue_get_dedup()
became unused and are removed.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
.../technical/paint-down-to-common.adoc | 9 +-
commit-reach.c | 102 +++++++++++++-----
t/t6600-test-reach.sh | 6 +-
3 files changed, 83 insertions(+), 34 deletions(-)
diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
index ff015c5c8f..74ba675643 100644
--- a/Documentation/technical/paint-down-to-common.adoc
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -99,15 +99,12 @@ re-enqueued is bounded by the number of flag transitions.
Termination
-----------
-The walk uses a `nonstale_queue` wrapper around `prio_queue` that
-tracks `max_nonstale`: the lowest-priority non-stale commit enqueued
-so far. Once that commit is dequeued, every remaining entry is known
-to be STALE and the loop terminates. Specifically, the main loop
+The walk tracks the number of commits of each type in the queue
+(PARENT1-only, PARENT2-only, pending merge-base). The main loop
ends when one of the following conditions holds:
1. The queue is empty.
- 2. `max_nonstale` has been dequeued, meaning the queue only contains
- STALE entries.
+ 2. The queue contains only stale entries.
3. Generation cutoff: the dequeued commit's generation is below
a caller-supplied `min_generation` threshold.
4. Single result: the caller only needs one merge base, one has
diff --git a/commit-reach.c b/commit-reach.c
index f6a438550b..dbbbea641f 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -79,21 +79,73 @@ static void clear_nonstale_queue(struct nonstale_queue *queue)
queue->max_nonstale = NULL;
}
-static void nonstale_queue_put_dedup(struct nonstale_queue *queue,
- struct commit *c)
+/*
+ * Priority queue with per-side commit counters for paint_down_to_common().
+ * Each non-stale queued commit occupies exactly one bucket: PARENT1-only,
+ * PARENT2-only, or both (a pending merge-base candidate).
+ */
+struct paint_state {
+ struct prio_queue queue;
+ size_t parent1_count;
+ size_t parent2_count;
+ size_t mb_candidate_count;
+ int gen_ordered;
+};
+
+static void paint_count_update(struct paint_state *state,
+ unsigned flags, int delta)
{
- if (c->object.flags & ENQUEUED)
- return;
- c->object.flags |= ENQUEUED;
- nonstale_queue_put(queue, c);
+ switch (flags & (PARENT1 | PARENT2 | STALE)) {
+ case PARENT1:
+ state->parent1_count += delta;
+ break;
+
+ case PARENT2:
+ state->parent2_count += delta;
+ break;
+
+ case PARENT1 | PARENT2:
+ state->mb_candidate_count += delta;
+ break;
+
+ case PARENT1 | PARENT2 | STALE:
+ break;
+
+ default:
+ BUG("unexpected paint state");
+ }
}
-static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
+static void paint_queue_put(struct paint_state *state,
+ struct commit *c, unsigned add_flags)
{
- struct commit *commit = nonstale_queue_get(queue);
+ unsigned old_flags = c->object.flags;
+ c->object.flags |= add_flags;
+
+ if (old_flags & ENQUEUED) {
+ paint_count_update(state, old_flags, -1);
+ paint_count_update(state, c->object.flags, 1);
+ } else {
+ c->object.flags |= ENQUEUED;
+ prio_queue_put(&state->queue, c);
+ paint_count_update(state, c->object.flags, 1);
+ }
+}
- if (commit)
- commit->object.flags &= ~ENQUEUED;
+static struct commit *paint_queue_get(struct paint_state *state)
+{
+ struct commit *commit = prio_queue_get(&state->queue);
+
+ if (!commit)
+ return NULL;
+
+ commit->object.flags &= ~ENQUEUED;
+
+ if (!state->parent1_count && !state->parent2_count &&
+ !state->mb_candidate_count)
+ return NULL;
+
+ paint_count_update(state, commit->object.flags, -1);
return commit;
}
@@ -109,31 +161,32 @@ static int paint_down_to_common(struct repository *r,
enum merge_base_flags mb_flags,
struct commit_list **result)
{
- struct nonstale_queue queue = {
- { compare_commits_by_gen_then_commit_date }
+ struct paint_state state = {
+ .queue = { compare_commits_by_gen_then_commit_date },
+ .gen_ordered = 1,
};
+ struct commit *commit;
int i;
int steps = 0;
timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
struct commit_list **tail = result;
- if (!min_generation && !corrected_commit_dates_enabled(r))
- queue.pq.compare = compare_commits_by_commit_date;
+ if (!min_generation && !corrected_commit_dates_enabled(r)) {
+ state.queue.compare = compare_commits_by_commit_date;
+ state.gen_ordered = 0;
+ }
one->object.flags |= PARENT1;
if (!n) {
commit_list_append(one, result);
return 0;
}
- nonstale_queue_put_dedup(&queue, one);
+ paint_queue_put(&state, one, 0);
- for (i = 0; i < n; i++) {
- twos[i]->object.flags |= PARENT2;
- nonstale_queue_put_dedup(&queue, twos[i]);
- }
+ for (i = 0; i < n; i++)
+ paint_queue_put(&state, twos[i], PARENT2);
- while (queue.max_nonstale) {
- struct commit *commit = nonstale_queue_get_dedup(&queue);
+ while ((commit = paint_queue_get(&state))) {
struct commit_list *parents;
int flags;
timestamp_t generation = commit_graph_generation(commit);
@@ -172,7 +225,7 @@ static int paint_down_to_common(struct repository *r,
if ((p->object.flags & flags) == flags)
continue;
if (repo_parse_commit(r, p)) {
- clear_nonstale_queue(&queue);
+ clear_prio_queue(&state.queue);
commit_list_free(*result);
*result = NULL;
/*
@@ -187,12 +240,11 @@ static int paint_down_to_common(struct repository *r,
return error(_("could not parse commit %s"),
oid_to_hex(&p->object.oid));
}
- p->object.flags |= flags;
- nonstale_queue_put_dedup(&queue, p);
+ paint_queue_put(&state, p, flags);
}
}
- clear_nonstale_queue(&queue);
+ clear_prio_queue(&state.queue);
trace2_data_intmax("paint_down_to_common", r,
"steps", steps);
commit_list_sort_by_date(result);
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 26a2a0a62f..11db9ec988 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -367,7 +367,7 @@ test_expect_success 'get_merge_bases_many:pending-stale' '
git rev-parse ps-B
} >expect &&
test_all_modes get_merge_bases_many &&
- test_paint_down_steps 6 6 6 6
+ test_paint_down_steps 5 5 5 5
'
test_expect_success 'get_merge_bases_many:infinity-both-sides' '
@@ -382,7 +382,7 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
git rev-parse pi-B
} >expect &&
test_all_modes get_merge_bases_many &&
- test_paint_down_steps 5 5 5 5
+ test_paint_down_steps 5 4 5 5
'
test_expect_success 'setup mixed finite/INFINITY topology' '
@@ -445,7 +445,7 @@ test_expect_success 'merge-base --all with clock skew returns wrong merge base (
>input &&
git rev-parse se2-MB1 >expect &&
run_all_modes git merge-base --all se2-A se2-B &&
- test_paint_down_steps 8 7 8 8
+ test_paint_down_steps 8 6 8 8
'
test_expect_success 'reduce_heads' '
--
gitgitgadget
^ permalink raw reply related
* [PATCH v5 08/10] commit-reach: terminate merge-base walk when one paint side is exhausted
From: Kristofer Karlsson via GitGitGadget @ 2026-07-01 16:37 UTC (permalink / raw)
To: git; +Cc: Kristofer Karlsson, Kristofer Karlsson
In-Reply-To: <pull.2149.v5.git.1782923832.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add an early termination check to paint_down_to_common() using the
per-side counters introduced earlier. Once the walk enters the
finite-generation region, terminate early when one side's exclusive
count drops to zero -- no new merge-base can form without both paint
sides meeting.
The check also waits for pending_merge_bases to reach zero, ensuring
all merge-base candidates have been dequeued and recorded before
exiting.
The INFINITY gate ensures correctness: commits without a commit-graph
entry have GENERATION_NUMBER_INFINITY and are ordered by commit date,
which is not topologically reliable. The optimization only fires
once the walk enters the finite-generation region where ordering
guarantees hold.
Step counts measured with trace2 on git.git with commit-graph:
merge-base --all v2.0.0 v2.55.0-rc1:
before: 72264 steps after: 44589 steps
merge-base --all v2.55.0-rc1 v2.55.0-rc1~5:
before: 110 steps after: 7 steps
Helped-by: Derrick Stolee <stolee@gmail.com>
Helped-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
.../technical/paint-down-to-common.adoc | 17 +++++++++++++++++
commit-reach.c | 18 +++++++++++++++---
t/t6600-test-reach.sh | 4 ++--
3 files changed, 34 insertions(+), 5 deletions(-)
diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
index 74ba675643..8a8a7a930e 100644
--- a/Documentation/technical/paint-down-to-common.adoc
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -110,6 +110,9 @@ ends when one of the following conditions holds:
4. Single result: the caller only needs one merge base, one has
been found, and the walk has entered the finite-generation
region.
+ 5. Side exhaustion: no pure PARENT1 or pure PARENT2 commits
+ remain in the queue, no pending merge-base candidates exist,
+ and the walk has entered the finite-generation region.
Stale entry condition
~~~~~~~~~~~~~~~~~~~~~
@@ -120,6 +123,20 @@ existing candidates by proving one is an ancestor of another, but
`remove_redundant()` handles that as a post-processing step, so it
is safe to exit early.
+Side-exhaustion condition
+~~~~~~~~~~~~~~~~~~~~~~~~~
+A new merge-base requires commits from both sides to meet. When one
+side's exclusive counter reaches zero and there are no pending
+merge-base candidates, no future traversal step can produce a new
+candidate.
+
+This optimization only activates in the finite-generation region
+where topological ordering holds. In that region, children are
+always visited before parents, so paint flags are final at visit
+time and an exhausted side cannot reappear. In the INFINITY region,
+commit-date ordering can violate this guarantee, so the check is
+skipped.
+
Generation cutoff
~~~~~~~~~~~~~~~~~
Some callers (notably `remove_redundant()`) supply a `min_generation`
diff --git a/commit-reach.c b/commit-reach.c
index dbbbea641f..2b9249105c 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -132,6 +132,10 @@ static void paint_queue_put(struct paint_state *state,
}
}
+/*
+ * Dequeue the next commit for the paint walk, or return NULL when
+ * no more merge bases can be discovered.
+ */
static struct commit *paint_queue_get(struct paint_state *state)
{
struct commit *commit = prio_queue_get(&state->queue);
@@ -141,9 +145,17 @@ static struct commit *paint_queue_get(struct paint_state *state)
commit->object.flags &= ~ENQUEUED;
- if (!state->parent1_count && !state->parent2_count &&
- !state->mb_candidate_count)
- return NULL;
+ if (!state->mb_candidate_count) {
+ /* only stale entries remain */
+ if (!state->parent1_count && !state->parent2_count)
+ return NULL;
+
+ /* one side is exhausted */
+ if ((!state->parent1_count || !state->parent2_count) &&
+ state->gen_ordered &&
+ commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
+ return NULL;
+ }
paint_count_update(state, commit->object.flags, -1);
return commit;
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 11db9ec988..fd11febf1a 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -298,7 +298,7 @@ test_expect_success 'in_merge_bases_many:self' '
EOF
echo "in_merge_bases_many(A,X):1" >expect &&
test_all_modes in_merge_bases_many &&
- test_paint_down_steps 45 2 25 3
+ test_paint_down_steps 45 1 25 1
'
test_expect_success 'is_descendant_of:hit' '
@@ -415,7 +415,7 @@ test_expect_success 'merge-base --all commit-walk steps' '
>input &&
git rev-parse commit-9-1 >expect &&
run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
- test_paint_down_steps 81 80 81 81
+ test_paint_down_steps 81 9 57 81
'
test_expect_success 'merge-base --all with clock skew and v1 commit-graph (side-exhaustion)' '
--
gitgitgadget
^ permalink raw reply related
* [PATCH v5 09/10] commit-reach: move min_generation check into paint_queue_get()
From: Kristofer Karlsson via GitGitGadget @ 2026-07-01 16:37 UTC (permalink / raw)
To: git; +Cc: Kristofer Karlsson, Kristofer Karlsson
In-Reply-To: <pull.2149.v5.git.1782923832.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Consolidate the min_generation termination condition into
paint_queue_get(), alongside the existing stale-entry and
side-exhaustion checks.
Move last_gen into struct paint_state so that
commit_graph_generation() is called exactly once per dequeued commit
and the result is shared across all termination checks and the
monotonicity BUG assertion.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
commit-reach.c | 31 ++++++++++++++++++-------------
1 file changed, 18 insertions(+), 13 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index 2b9249105c..871d67d07a 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -90,6 +90,8 @@ struct paint_state {
size_t parent2_count;
size_t mb_candidate_count;
int gen_ordered;
+ timestamp_t min_generation;
+ timestamp_t last_gen;
};
static void paint_count_update(struct paint_state *state,
@@ -139,11 +141,23 @@ static void paint_queue_put(struct paint_state *state,
static struct commit *paint_queue_get(struct paint_state *state)
{
struct commit *commit = prio_queue_get(&state->queue);
+ timestamp_t generation;
if (!commit)
return NULL;
commit->object.flags &= ~ENQUEUED;
+ generation = commit_graph_generation(commit);
+
+ if (state->min_generation && generation > state->last_gen)
+ BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
+ generation, state->last_gen,
+ oid_to_hex(&commit->object.oid));
+ state->last_gen = generation;
+
+ /* generation cutoff */
+ if (generation < state->min_generation)
+ return NULL;
if (!state->mb_candidate_count) {
/* only stale entries remain */
@@ -153,7 +167,7 @@ static struct commit *paint_queue_get(struct paint_state *state)
/* one side is exhausted */
if ((!state->parent1_count || !state->parent2_count) &&
state->gen_ordered &&
- commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
+ generation < GENERATION_NUMBER_INFINITY)
return NULL;
}
@@ -180,9 +194,10 @@ static int paint_down_to_common(struct repository *r,
struct commit *commit;
int i;
int steps = 0;
- timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
struct commit_list **tail = result;
+ state.min_generation = min_generation;
+ state.last_gen = GENERATION_NUMBER_INFINITY;
if (!min_generation && !corrected_commit_dates_enabled(r)) {
state.queue.compare = compare_commits_by_commit_date;
state.gen_ordered = 0;
@@ -201,18 +216,8 @@ static int paint_down_to_common(struct repository *r,
while ((commit = paint_queue_get(&state))) {
struct commit_list *parents;
int flags;
- timestamp_t generation = commit_graph_generation(commit);
steps++;
- if (min_generation && generation > last_gen)
- BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
- generation, last_gen,
- oid_to_hex(&commit->object.oid));
- last_gen = generation;
-
- if (generation < min_generation)
- break;
-
flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
if (flags == (PARENT1 | PARENT2)) {
if (!(commit->object.flags & RESULT)) {
@@ -224,7 +229,7 @@ static int paint_down_to_common(struct repository *r,
* descendant of this one.
*/
if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
- generation < GENERATION_NUMBER_INFINITY)
+ state.last_gen < GENERATION_NUMBER_INFINITY)
break;
}
/* Mark parents of a found merge stale */
--
gitgitgadget
^ permalink raw reply related
* [PATCH v5 10/10] commit-reach: remove commit-date ordering fallback
From: Kristofer Karlsson via GitGitGadget @ 2026-07-01 16:37 UTC (permalink / raw)
To: git; +Cc: Kristofer Karlsson, Kristofer Karlsson
In-Reply-To: <pull.2149.v5.git.1782923832.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Remove the fallback that switched paint_down_to_common() from
generation ordering to commit-date ordering when the commit-graph
lacks corrected commit dates (v1 graph with topo levels only).
The fallback was added in 091f4cf3 (commit: don't use generation
numbers if not needed, 2018-08-30) to avoid a performance
regression on the Linux kernel repo where v1 topo levels caused
"git merge-base v4.8 v4.9" to walk 636k commits instead of 167k.
A side branch with a low topo level stayed in the queue behind a
long chain, preventing early STALE propagation.
Side-exhaustion (added in the previous commits) solves this
differently by terminating the walk as soon as one paint side
empties from the queue, preventing the deep walk regardless of
queue ordering. Benchmarks of "git merge-base --all v4.8 v4.9"
on the Linux kernel repo show that side-exhaustion reduces the
step count far below what the date-ordering fallback achieved:
steps time
no graph, baseline: 167,413 3.25 s
v1 graph, baseline: 167,413 0.25 s
v2 graph, baseline: 167,441 0.29 s
v1 graph, this series: 5,725 0.02 s
v2 graph, this series: 3,887 0.01 s
With generation ordering always active, the existing min_generation
check in paint_queue_get() correctly identifies when the walk has
reached the finite generation region. The date ordering fallback
broke this invariant: a commit could have a finite topo level
while the queue was date-ordered, causing the early exit to fire
before all merge bases were found.
Also remove corrected_commit_dates_enabled() from commit-graph.c
which has no remaining callers.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
.../technical/paint-down-to-common.adoc | 40 -------------------
commit-graph.c | 11 -----
commit-graph.h | 6 ---
commit-reach.c | 14 +++----
t/t6600-test-reach.sh | 8 ++--
5 files changed, 10 insertions(+), 69 deletions(-)
diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
index 8a8a7a930e..7b8e483af2 100644
--- a/Documentation/technical/paint-down-to-common.adoc
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -40,20 +40,10 @@ and PARENT2, it is a merge-base candidate. A candidate gains the
STALE flag so its ancestors propagate staleness -- any deeper common
ancestor is necessarily redundant.
-NOTE: When the commit-graph uses only topological levels (generation
-number v1) and the caller passes `min_generation = 0`, a legacy
-fallback replaces the generation-ordered comparator with a pure
-commit-date comparator. This breaks the ordering invariants
-described below -- see <<date-ordering-fallback>>.
-
[[generation-regions]]
INFINITY and finite generation regions
--------------------------------------
-The properties in this section assume generation-number ordering (the
-default comparator). They do NOT hold when the date-ordering fallback
-is active -- see <<date-ordering-fallback>>.
-
The commit-graph stores a generation number for each commit. Commits
not in the commit-graph have generation `GENERATION_NUMBER_INFINITY`. The
graph is closed under reachability: if a commit is in the graph, all
@@ -154,36 +144,6 @@ descendant of this candidate (generation ordering guarantees
children are visited first), so it cannot be redundant and the walk
can stop immediately.
-This optimization is NOT safe when the date-ordering fallback is
-active, because commit-date order can visit a deeper ancestor
-before a shallower one -- see <<date-ordering-fallback>>.
-
-[[date-ordering-fallback]]
-Date-ordering fallback
-----------------------
-
-When `min_generation` is zero and the commit-graph does not contain
-corrected commit dates (generation number v1, which stores only
-topological levels), `paint_down_to_common()` replaces the default
-generation-ordered comparator with `compare_commits_by_commit_date`.
-
-This was introduced as a performance heuristic: topological levels
-are coarser than commit dates, so date ordering can reach merge
-bases in fewer steps when timestamps are well-behaved. However,
-commit dates are not required to be monotonic -- a parent can have
-a later date than its child (clock skew, rebases, etc.) -- so the
-queue may visit commits out of topological order.
-
-This disables optimizations that depend on generation ordering:
-
- 1. *Single result*: the first merge-base candidate found may not
- be the shallowest, because a deeper ancestor with a higher
- commit date can be dequeued first.
-
- 2. *Side-exhaustion* (see subsequent commits): one paint side can
- appear to drain from the queue while commits from that side are
- still waiting with lower dates, causing premature termination.
-
Related documentation
---------------------
diff --git a/commit-graph.c b/commit-graph.c
index 801471a098..3d5d41f65a 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -793,17 +793,6 @@ int generation_numbers_enabled(struct repository *r)
return !!first_generation;
}
-int corrected_commit_dates_enabled(struct repository *r)
-{
- struct commit_graph *g;
-
- g = prepare_commit_graph(r);
- if (!g || !g->num_commits)
- return 0;
-
- return g->read_generation_data;
-}
-
struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r)
{
struct commit_graph *g;
diff --git a/commit-graph.h b/commit-graph.h
index 13ca4ff010..d96147a07c 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -136,12 +136,6 @@ struct commit_graph *parse_commit_graph(struct repository *r,
*/
int generation_numbers_enabled(struct repository *r);
-/*
- * Return 1 if and only if the repository has a commit-graph
- * file and generation data chunk has been written for the file.
- */
-int corrected_commit_dates_enabled(struct repository *r);
-
struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r);
enum commit_graph_write_flags {
diff --git a/commit-reach.c b/commit-reach.c
index 871d67d07a..826c4324f2 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -89,7 +89,6 @@ struct paint_state {
size_t parent1_count;
size_t parent2_count;
size_t mb_candidate_count;
- int gen_ordered;
timestamp_t min_generation;
timestamp_t last_gen;
};
@@ -166,7 +165,6 @@ static struct commit *paint_queue_get(struct paint_state *state)
/* one side is exhausted */
if ((!state->parent1_count || !state->parent2_count) &&
- state->gen_ordered &&
generation < GENERATION_NUMBER_INFINITY)
return NULL;
}
@@ -187,9 +185,13 @@ static int paint_down_to_common(struct repository *r,
enum merge_base_flags mb_flags,
struct commit_list **result)
{
+ /*
+ * Generation ordering is required for the side-exhaustion and
+ * single-result early exits, which rely on topological traversal
+ * order (children visited before parents) in the finite region.
+ */
struct paint_state state = {
- .queue = { compare_commits_by_gen_then_commit_date },
- .gen_ordered = 1,
+ .queue = { compare_commits_by_gen_then_commit_date }
};
struct commit *commit;
int i;
@@ -198,10 +200,6 @@ static int paint_down_to_common(struct repository *r,
state.min_generation = min_generation;
state.last_gen = GENERATION_NUMBER_INFINITY;
- if (!min_generation && !corrected_commit_dates_enabled(r)) {
- state.queue.compare = compare_commits_by_commit_date;
- state.gen_ordered = 0;
- }
one->object.flags |= PARENT1;
if (!n) {
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index fd11febf1a..6a0899c44a 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -382,7 +382,7 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
git rev-parse pi-B
} >expect &&
test_all_modes get_merge_bases_many &&
- test_paint_down_steps 5 4 5 5
+ test_paint_down_steps 5 4 5 4
'
test_expect_success 'setup mixed finite/INFINITY topology' '
@@ -415,7 +415,7 @@ test_expect_success 'merge-base --all commit-walk steps' '
>input &&
git rev-parse commit-9-1 >expect &&
run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
- test_paint_down_steps 81 9 57 81
+ test_paint_down_steps 81 9 57 37
'
test_expect_success 'merge-base --all with clock skew and v1 commit-graph (side-exhaustion)' '
@@ -429,7 +429,7 @@ test_expect_success 'merge-base --all with clock skew and v1 commit-graph (side-
>input &&
git rev-parse se-D >expect &&
run_all_modes git merge-base --all se-A se-B &&
- test_paint_down_steps 6 4 6 6
+ test_paint_down_steps 6 4 6 4
'
test_expect_success 'merge-base --all with clock skew returns wrong merge base (side-exhaustion)' '
@@ -445,7 +445,7 @@ test_expect_success 'merge-base --all with clock skew returns wrong merge base (
>input &&
git rev-parse se2-MB1 >expect &&
run_all_modes git merge-base --all se2-A se2-B &&
- test_paint_down_steps 8 6 8 8
+ test_paint_down_steps 8 6 8 6
'
test_expect_success 'reduce_heads' '
--
gitgitgadget
^ permalink raw reply related
* Re: [PATCH] ci(dockerized): reduce the PID limit for private repositories
From: Junio C Hamano @ 2026-07-01 16:54 UTC (permalink / raw)
To: Johannes Schindelin via GitGitGadget; +Cc: git, Johannes Schindelin
In-Reply-To: <pull.2164.git.1782889484346.gitgitgadget@gmail.com>
"Johannes Schindelin via GitGitGadget" <gitgitgadget@gmail.com>
writes:
> The underlying reason seems to be a substantial difference in the hosted
> runners that execute these Dockerized jobs: forcing the PID limit of the
> container to a high number lets the jobs pass, even when running the
> complete matrix of all 13 Dockerized jobs concurrently.
Is the "reduce" in the title accurate? The above description tells
me that what you did was to "raise" the PID limit (i.e., forcing the
PID limit to a high number), presumably because the default PID
limit is way too low for the tests to pass?
And that fix turns constant failures into success (albeit the tests
run very slowly, which is a separate topic that you discuss next).
> But that's not
> the only difference: The jobs seem to take a lot longer in these
> containers than, say, in the containers made available to
> https://github.com/git/git.
>
> When forcing a PID limit of 64k in that private repository, the jobs
> completed successfully, but they also took a lot longer, between 2x to
> 2.5x longer, i.e. painfully much longer. Reducing the PID limit to 16k,
> the CI jobs still passed, but took an equally long amount of time.
> Reducing the PID limit to 8k caused the errors to reappear.
> ...
> It does not look as if the PID limit is the reason for the longer
> runtime, seeing as the 64k vs 16k timings deviate no more than as is
> usual with GitHub workflows. So let's go for 16k.
So 8k is too low to make them pass, just like the default setting
(whatever it is), but 16k is sufficient, so this patch settles at
that number, which makes sense.
> diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml
> index cf341d74db..85cfedf5b0 100644
> --- a/.github/workflows/main.yml
> +++ b/.github/workflows/main.yml
> @@ -420,7 +420,9 @@ jobs:
> CI_JOB_IMAGE: ${{matrix.vector.image}}
> CUSTOM_PATH: /custom
> runs-on: ubuntu-latest
> - container: ${{matrix.vector.image}}
> + container:
> + image: ${{ matrix.vector.image }}
> + options: ${{ github.repository_visibility == 'private' && '--pids-limit 16384 --ulimit nproc=16384:16384 --ulimit nofile=32768:32768' || '' }}
> steps:
> - name: prepare libc6 for actions
> if: matrix.vector.jobname == 'linux32'
>
> base-commit: e9019fcafe0040228b8631c30f97ae1adb61bcdc
^ permalink raw reply
* Re: [PATCH v8 00/11] builtin/history: introduce "drop" subcommand
From: Junio C Hamano @ 2026-07-01 17:12 UTC (permalink / raw)
To: Patrick Steinhardt
Cc: git, Pablo Sabater, Kristoffer Haugsbakk, Phillip Wood,
Christian Couder
In-Reply-To: <20260701-b4-pks-history-drop-v8-0-19b5cdf1facd@pks.im>
Patrick Steinhardt <ps@pks.im> writes:
> Changes in v8:
> - Pass `RESOLVE_REF_READING` to make `refs_resolve_ref_unsafe()`
> return a NULL pointer when it cannot resolve the reference.
OK.
> - Drop unneeded code that sets `head_target = "HEAD"` on detached
> HEAD.
OK.
> - Add a test case that verifies that we can drop commits with
> "--update-refs=head" and a detached HEAD.
OK.
Sounds good. Will replace.
Thanks.
^ permalink raw reply
* Re: [PATCH GSoC v15 02/13] git-compat-util: add `strtoumax_szt()` with error handling
From: Junio C Hamano @ 2026-07-01 17:30 UTC (permalink / raw)
To: Pablo Sabater
Cc: git, chandrapratap3519, chriscool, eric.peijian, jltobler,
karthik.188, peff, toon
In-Reply-To: <20260701-ps-eric-work-rebase-v15-2-c88a43b63917@gmail.com>
Pablo Sabater <pabloosabaterr@gmail.com> writes:
> From: Eric Ju <eric.peijian@gmail.com>
>
> We already have `strtoul_ui()` and similar functions that provide proper
> error handling using `strtoul` from the standard library. However,
> there isn't currently a variant that returns a `size_t`.
>
> Using `strtoul` is unreliable because `size_`t is platform-dependent,
> `unsigned long` could be too big to fit into a `size_t` or too small to
> hold a `size_t`.
It is somehow annoying to see that the commit log desciption, which
is *clearly* meant to be plaintext, is so heavily riddled with
backquoted references to code/program symbols. Yes, `literal` is a
correct way to format them in both AsciiDoc and Markdown, so we very
much welcome them in our documentation, but not in proposed log
messages.
In any case, you dropped 't' in 'size_t' outside the pair of
backquotes.
> Use `strtoumax` which returns a `uintmax_t` guaranteed to be at least as
`strtoumax()`, as the convention you used above for strtoul_ui() is
to suffix function names with ().
> large as `size_t`, add a range check against `SIZE_MAX` to prevent
> `size_t` overflow.
OK.
> This variant is needed in a subsequent commit to enable returning a
> `size_t` with proper error handling.
>
> Mentored-by: Karthik Nayak <karthik.188@gmail.com>
> Mentored-by: Chandra Pratap <chandrapratap3519@gmail.com>
> Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>
> ---
> git-compat-util.h | 20 ++++++++++++++++++++
> 1 file changed, 20 insertions(+)
>
> diff --git a/git-compat-util.h b/git-compat-util.h
> index 8809776407..5ecce5bbd2 100644
> --- a/git-compat-util.h
> +++ b/git-compat-util.h
> @@ -975,6 +975,26 @@ static inline int strtoul_ui(char const *s, int base, unsigned int *result)
> return 0;
> }
>
> +/*
> + * Convert a string to a size_t using the standard library's strtoumax, with
> + * additional error handling to ensure robustness.
> + */
> +static inline int strtoumax_szt(char const *s, int base, size_t *result)
> +{
> + uintmax_t uim;
> + char *p;
> +
> + errno = 0;
> + /* negative values would be accepted by strtoul */
> + if (strchr(s, '-'))
> + return -1;
Hmph, wouldn't
if (*s == '-' || !*s)
return -1
cut it? Since your call to strtoumax() checks that the string was
parsed to the end by insisting *p is NUL?
If you are trying to more explicitly insist that s[] has only
digits, which may not be a bad idea, as that is what we generally
expect, then
if (!s[0] || s[strspn(s, "0123456789")])
return -1;
perhaps.
> + uim = strtoumax(s, &p, base);
> + if ((errno || *p || p == s) || uim > SIZE_MAX)
> + return -1;
And with !s[0] upfront, we can discard (p==s) case from here. Other
strto*() wrappers we have may need the "cannot be empty" check,
because they do not need any upfront validation of s[] like we do
here (we do so to reject negative numbers), but since we do need to
check s[] before calling the system strto*() function anyway, it is
OK to be different here from the others.
If uintmax_t and size_t are of the same width, then (SIZE_MAX < uim)
becomes mathmatically impossible, but hopefully no compiler or
static checker is stupid enough to warn against it.
> + *result = uim;
> + return 0;
> +}
> +
> static inline int strtol_i(char const *s, int base, int *result)
> {
> long ul;
^ permalink raw reply
* Re: [PATCH 0/3] bloom-related leak fixes
From: Junio C Hamano @ 2026-07-01 17:33 UTC (permalink / raw)
To: Derrick Stolee; +Cc: Jeff King, git, Patrick Steinhardt
In-Reply-To: <b641aed4-ad52-477b-b1d8-9d8e470be46f@gmail.com>
Derrick Stolee <stolee@gmail.com> writes:
> On 7/1/2026 2:35 AM, Jeff King wrote:
>> Here are a few small leak fixes that only show up when you run the test
>> suite with GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1.
>>
>> Combined with the commit-graph leak-fix here:
>>
>> https://lore.kernel.org/git/20260630064301.GB3733961@coredump.intra.peff.net/
>>
>> and Kaartic's pending fix from this thread:
>>
>> https://lore.kernel.org/git/20260614141600.620272-1-kaartic.sivaraam@gmail.com/
>>
>> This will fix most of the leaks we'd see if we ran linux-TEST-vars jobs
>> with leak-checking. There are a few more related to building with
>> openssl for sha1, but I'll tackle those separately.
> Thanks for fixing these leaks in the simplest way possible in
> each scenario.
Yup, these were delight to read.
^ permalink raw reply
* Re: [PATCH 00/13] coverity: fix leaks and error paths
From: Junio C Hamano @ 2026-07-01 17:34 UTC (permalink / raw)
To: Johannes Schindelin via GitGitGadget; +Cc: git, Johannes Schindelin
In-Reply-To: <pull.2163.git.1782889472.gitgitgadget@gmail.com>
"Johannes Schindelin via GitGitGadget" <gitgitgadget@gmail.com>
writes:
> I wanted to whittle down the many issues reported by Coverity in the Git for
> Windows project. Turns out: The vast majority of the issues are false
> positives. Most of the remaining issues are in core Git proper.
I read through the series and did not see anything jumping at me as
wrong. Looking good. Will queue.
Thanks.
>
> This effort was forced on pause while Coverity was down from May 16
> [https://web.archive.org/web/20260516152422/https://scan.coverity.com/] to
> June 22
> [https://web.archive.org/web/20260622182153/https://scan.coverity.com/]).
>
> Here is a first batch of fixes for those issues.
>
> Johannes Schindelin (13):
> load_one_loose_object_map(): fix resource leak
> loose: avoid closing invalid fd on error path
> download_https_uri_to_file(): do not leak fd upon failure
> run-command: avoid close(-1) in start_command() error paths
> run_diff_files: avoid memory leak
> line-log: avoid redundant copy that leaks in process_ranges
> dir: free allocations on parse-error paths in read_one_dir()
> submodule: fix cwd leak in get_superproject_working_tree()
> worktree: fix resource leaks when branch creation fails
> imap-send: avoid leaking the IMAP upload buffer
> reftable/table: release filter on error path
> fsmonitor: plug token-data leak on early daemon-startup failures
> mingw: make exit_process() own the process handle on all paths
>
> builtin/fsmonitor--daemon.c | 2 ++
> builtin/worktree.c | 7 +++++--
> bundle-uri.c | 2 +-
> compat/mingw.c | 4 +---
> compat/win32/exit-process.h | 1 +
> diff-lib.c | 3 ++-
> dir.c | 9 +++++++--
> imap-send.c | 1 +
> line-log.c | 3 +--
> loose.c | 11 ++++++-----
> reftable/table.c | 4 ++++
> run-command.c | 6 +++---
> submodule.c | 8 ++++++--
> 13 files changed, 40 insertions(+), 21 deletions(-)
>
>
> base-commit: e9019fcafe0040228b8631c30f97ae1adb61bcdc
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2163%2Fdscho%2Fcoverity-fixes-leaks-and-error-paths-v1
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2163/dscho/coverity-fixes-leaks-and-error-paths-v1
> Pull-Request: https://github.com/gitgitgadget/git/pull/2163
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox