* [PATCH v2 0/7] commit-reach: terminate merge-base walk when one side is exhausted
From: Kristofer Karlsson via GitGitGadget @ 2026-06-24 12:14 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson
In-Reply-To: <pull.2149.git.1781951820.gitgitgadget@gmail.com>
commit-reach: terminate merge-base walk when one side is exhausted
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]. Patches 2-3 incorporate 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 layout:
1/7 Documentation/technical: add paint-down-to-common doc 2/7 t6600: add
test cases for side-exhaustion edge cases 3/7 t6099, t6600: add
side-exhaustion regression tests 4/7 commit-reach: add trace2
instrumentation to paint_down_to_common() 5/7 commit-reach: introduce struct
paint_state with per-side counters 6/7 commit-reach: remove unused
nonstale_queue dedup wrappers 7/7 commit-reach: terminate merge-base walk
when one paint side is exhausted
Benchmarks
Step counts are deterministic (measured via trace2_data_intmax added in
patch 4). Wall-clock times are medians over 10-20 runs with CPU governor set
to performance.
2.6M-commit monorepo with commit-graph (baseline v2.55.0-rc1):
steps wall-clock
merge-base --all (across import) 2682391 -> 53521 7.26s -> 88ms
merge-base --all (1000 apart) 2659607 -> 1106 6.98s -> 8ms
merge-tree (across import) - 8.11s -> 100ms
git.git (88k commits, commit-graph):
steps wall-clock
merge-base --all v2.0.0 v2.55.0-rc1 72264 -> 44589 82ms -> 49ms
merge-base --all HEAD HEAD~1000 9873 -> 3817 19ms -> 9ms
merge-base --all HEAD HEAD~10000 72285 -> 41523 80ms -> 48ms
merge-base HEAD HEAD~1000 - 9ms -> 9ms
merge-base --is-ancestor HEAD~1000 HEAD - 6ms -> 6ms
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.
* Moved all termination conditions into paint_queue_get(). The all-zero
check and the side-exhaustion check are merged under a shared
!pending_merge_bases guard. paint_queue_get() derives the generation from
the dequeued commit itself, so no extra parameter is needed.
* Added trace2_data_intmax() instrumentation to report the number of
commits visited per paint walk (separate commit), with deterministic
step-count assertions in t6600.
* Expanded switch statements to multi-line format per .clang-format.
* Used !count style throughout instead of count == 0.
* Updated technical documentation alongside code changes.
* Added benchmark data (both git-bench wall-clock and trace2 step counts)
to commit messages.
[1]
https://lore.kernel.org/git/CAL71e4Ps-2_0+uuZu43N9pFnXBemoAohPs_eyRJf8taXHJPAXQ@mail.gmail.com/T/#u
[2] https://github.com/gitgitgadget/git/pull/2150
Elijah Newren (1):
t6600: add test cases for side-exhaustion edge cases
Kristofer Karlsson (6):
Documentation/technical: add paint-down-to-common doc
t6099, t6600: add side-exhaustion regression tests
commit-reach: add trace2 instrumentation to paint_down_to_common()
commit-reach: introduce struct paint_state with per-side counters
commit-reach: remove unused nonstale_queue dedup wrappers
commit-reach: terminate merge-base walk when one paint side is
exhausted
Documentation/Makefile | 1 +
Documentation/technical/meson.build | 1 +
.../technical/paint-down-to-common.adoc | 128 ++++++++++++++
commit-reach.c | 119 ++++++++++---
t/meson.build | 1 +
t/t6099-merge-base-side-exhaustion.sh | 82 +++++++++
t/t6600-test-reach.sh | 157 ++++++++++++++++++
7 files changed, 464 insertions(+), 25 deletions(-)
create mode 100644 Documentation/technical/paint-down-to-common.adoc
create mode 100755 t/t6099-merge-base-side-exhaustion.sh
base-commit: ab776a62a78576513ee121424adb19597fbb7613
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2149%2Fspkrka%2Fside-exhaust-pr-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2149/spkrka/side-exhaust-pr-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/2149
Range-diff vs v1:
1: 5492acda0a < -: ---------- commit-reach: decouple ahead_behind from nonstale_queue
6: 9cbfc67d72 ! 1: 19ed743bd1 Documentation/technical: add paint-down-to-common doc
@@ Commit message
Documentation/technical: add paint-down-to-common doc
Add a technical document describing the paint_down_to_common()
- algorithm used for merge-base computation.
+ 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/technical/paint-down-to-common.adoc (new)
+Termination
+-----------
+
-+Termination happens when we can prove that no extra progress is
-+possible. We are done with the main loop when one of the following
-+conditions holds:
++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. The queue only contains STALE entries.
-+ 3. Side-exhaustion: the walk has reached the finite region and one
-+ of the sides is fully exhausted.
-+
-+The loop waits for all pending merge-base candidates to be popped
-+and recorded before any early exit fires, so no separate drain phase
-+is needed after termination.
++ 2. `max_nonstale` has been dequeued, meaning the queue only contains
++ STALE entries.
+
+Stale entry condition
+~~~~~~~~~~~~~~~~~~~~~
-+If all entries are stale we cannot find any new merge bases since
-+that requires at least one enqueued side node meeting the other side.
-+However, we could still invalidate merge bases (if there are more
-+than one). This is unnecessary since `remove_redundant()` will clean
-+that up as a post-process step.
-+
-+Side-exhaustion
-+~~~~~~~~~~~~~~~
-+A commit is *exclusive* to one side if it carries that side's paint
-+but not the other (e.g. PARENT1 without PARENT2).
-+
-+If we have reached the finite region of the graph, no future
-+traversal step can add paint to an already-visited commit. Thus if
-+there are no exclusive PARENT2 commits in the queue, no additional
-+PARENT2 paint can be introduced into the walk. Even if exclusive
-+PARENT1 commits remain, no new merge-base candidates can be
-+discovered. The same holds symmetrically for PARENT1.
-+
-+This invariant is only valid in the finite region of the graph.
++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.
+
+Related documentation
+---------------------
+
+ - `Documentation/technical/commit-graph.adoc` -- generation numbers
+ and the reachability closure property.
+
+ ## commit-reach.c ##
+@@ commit-reach.c: 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,
4: 91372b975f ! 2: 6151b8e0a3 t6600: add test cases for side-exhaustion edge cases
@@ t/t6600-test-reach.sh: test_expect_success 'setup' '
+ # 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
++ # 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).
@@ t/t6600-test-reach.sh: test_expect_success 'setup' '
+
+ # 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
++ # 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.
+ #
@@ t/t6600-test-reach.sh: test_expect_success '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.
++ # paint_down_to_common(). See the topology comment in the setup test.
+ cat >input <<-\EOF &&
+ A:ps-T1
+ X:ps-T2
@@ t/t6600-test-reach.sh: test_expect_success '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
++ # 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
5: faf5bc98ed ! 3: 90f09ecb5c t6099, t6600: add side-exhaustion regression tests
@@ t/t6099-merge-base-side-exhaustion.sh (new)
+
+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
++of another. The side-exhaustion optimization in
+paint_down_to_common may exit before STALE propagation
+removes the ancestor, but remove_redundant catches it.
+
@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:infinity-both-s
+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
++ # 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
@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:infinity-both-s
+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
++ # 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
-: ---------- > 4: 6ade4df2ed commit-reach: add trace2 instrumentation to paint_down_to_common()
2: 316e4dfe26 ! 5: f24edd45f0 commit-reach: introduce struct paint_queue with per-side counters
@@ Metadata
Author: Kristofer Karlsson <krka@spotify.com>
## Commit message ##
- commit-reach: introduce struct paint_queue with per-side counters
+ commit-reach: introduce struct paint_state with per-side counters
- Replace the nonstale_queue abstraction in paint_down_to_common() with
- a new paint_queue struct that tracks per-side commit counts. Each
- non-stale queued commit occupies exactly one counter bucket based on
- its paint flags: PARENT1-only, PARENT2-only, or both sides (a pending
+ 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_transition() which handles
- all flag changes as bucket transfers: remove from the old bucket, add
- to the new one. Either step is a no-op when the respective state has
- no bucket (stale or zero).
+ 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.
- The loop now drains the queue via paint_queue_get() and breaks when
- all counters reach zero, replacing the old pointer-based termination
- (max_nonstale). This is equivalent behavior.
+ 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.
+
+ The existing nonstale_queue is left in place for ahead_behind().
+
+ Step counts (via trace2 from the previous commit) are identical
+ before and after this refactoring, confirming no behavioral change.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
+ ## Documentation/technical/paint-down-to-common.adoc ##
+@@ Documentation/technical/paint-down-to-common.adoc: 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.
+
+ Stale entry condition
+ ~~~~~~~~~~~~~~~~~~~~~
+
## commit-reach.c ##
-@@ commit-reach.c: static int compare_commits_by_gen(const void *_a, const void *_b)
+@@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
+ return commit;
}
- /*
-- * A prio_queue with O(1) termination check. 'max_nonstale' tracks
-- * the lowest-priority non-stale commit enqueued so far; once it is
-- * popped, every remaining entry is known to be STALE.
++/*
+ * 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 nonstale_queue {
-+struct paint_queue {
- struct prio_queue pq;
-- struct commit *max_nonstale;
++ */
++struct paint_state {
++ struct prio_queue queue;
+ int p1_count;
+ int p2_count;
+ int pending_merge_bases;
- };
-
--static void nonstale_queue_put(struct nonstale_queue *queue,
-- struct commit *c)
-+/*
-+ * Adjust per-side counters for a paint-state transition. Non-stale
-+ * commits are counted in one of three counters: PARENT1-only,
-+ * PARENT2-only, or both. Zero means "not in the queue" (used on
-+ * enqueue/dequeue); stale commits are not counted at all.
-+ */
-+static void paint_count_transition(struct paint_queue *queue,
-+ unsigned old_flags, unsigned new_flags)
- {
-- struct commit *old = queue->max_nonstale;
-+ unsigned old_paint = old_flags & (PARENT1 | PARENT2 | STALE);
-+ unsigned new_paint = new_flags & (PARENT1 | PARENT2 | STALE);
-
-- prio_queue_put(&queue->pq, c);
-- if (c->object.flags & STALE)
-+ if (old_paint == new_paint)
- return;
-- if (!old || queue->pq.compare(old, c, queue->pq.cb_data) <= 0)
-- queue->max_nonstale = c;
--}
--
--static struct commit *nonstale_queue_get(struct nonstale_queue *queue)
--{
-- struct commit *commit = prio_queue_get(&queue->pq);
-
-- if (commit == queue->max_nonstale)
-- queue->max_nonstale = NULL;
--
-- return commit;
-+ if (!(old_paint & STALE)) {
-+ switch (old_paint & (PARENT1 | PARENT2)) {
-+ case 0: break;
-+ case PARENT1: queue->p1_count--; break;
-+ case PARENT2: queue->p2_count--; break;
-+ case PARENT1 | PARENT2: queue->pending_merge_bases--; break;
-+ default: BUG("unexpected paint state");
-+ }
-+ }
-+ if (!(new_paint & STALE)) {
-+ switch (new_paint & (PARENT1 | PARENT2)) {
-+ case 0: break;
-+ case PARENT1: queue->p1_count++; break;
-+ case PARENT2: queue->p2_count++; break;
-+ case PARENT1 | PARENT2: queue->pending_merge_bases++; break;
-+ default: BUG("unexpected paint state");
-+ }
++};
++
++static void paint_count_update(struct paint_state *state,
++ unsigned flags, int delta)
++{
++ switch (flags & (PARENT1 | PARENT2 | STALE)) {
++ case PARENT1:
++ state->p1_count += delta;
++ break;
++
++ case PARENT2:
++ state->p2_count += delta;
++ break;
++
++ case PARENT1 | PARENT2:
++ state->pending_merge_bases += delta;
++ break;
++
++ case PARENT1 | PARENT2 | STALE:
++ break;
++
++ default:
++ BUG("unexpected paint state");
+ }
- }
-
--static void clear_nonstale_queue(struct nonstale_queue *queue)
-+static void paint_queue_put(struct paint_queue *queue,
++}
++
++static void paint_queue_put(struct paint_state *state,
+ struct commit *c, unsigned add_flags)
- {
-- clear_prio_queue(&queue->pq);
-- queue->max_nonstale = NULL;
--}
++{
+ unsigned old_flags = c->object.flags;
+ c->object.flags |= add_flags;
-
--static void nonstale_queue_put_dedup(struct nonstale_queue *queue,
-- struct commit *c)
--{
-- if (c->object.flags & ENQUEUED)
-- return;
-- c->object.flags |= ENQUEUED;
-- nonstale_queue_put(queue, c);
++
+ if (old_flags & ENQUEUED) {
-+ paint_count_transition(queue, old_flags, c->object.flags);
++ paint_count_update(state, old_flags, -1);
++ paint_count_update(state, c->object.flags, 1);
+ } else {
+ c->object.flags |= ENQUEUED;
-+ prio_queue_put(&queue->pq, c);
-+ paint_count_transition(queue, 0, c->object.flags);
++ prio_queue_put(&state->queue, c);
++ paint_count_update(state, c->object.flags, 1);
+ }
- }
-
--static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
-+static struct commit *paint_queue_get(struct paint_queue *queue)
- {
-- struct commit *commit = nonstale_queue_get(queue);
-+ struct commit *commit = prio_queue_get(&queue->pq);
-
-- if (commit)
++}
++
++static struct commit *paint_queue_get(struct paint_state *state)
++{
++ struct commit *commit;
++
++ if (!state->p1_count && !state->p2_count &&
++ !state->pending_merge_bases)
++ return NULL;
++
++ commit = prio_queue_get(&state->queue);
+ if (commit) {
- commit->object.flags &= ~ENQUEUED;
-+ paint_count_transition(queue, commit->object.flags, 0);
++ commit->object.flags &= ~ENQUEUED;
++ paint_count_update(state, commit->object.flags, -1);
+ }
- return commit;
- }
-
++ return commit;
++}
++
+ /*
+ * See Documentation/technical/paint-down-to-common.adoc
+ *
@@ commit-reach.c: 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_queue queue = {
-+ .pq = { compare_commits_by_gen_then_commit_date }
++ struct paint_state state = {
++ .queue = { compare_commits_by_gen_then_commit_date }
};
+ struct commit *commit;
int i;
+ int steps = 0;
timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
struct commit_list **tail = result;
-@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
+
+ if (!min_generation && !corrected_commit_dates_enabled(r))
+- queue.pq.compare = compare_commits_by_commit_date;
++ state.queue.compare = compare_commits_by_commit_date;
+
+ one->object.flags |= PARENT1;
+ if (!n) {
commit_list_append(one, result);
return 0;
}
- nonstale_queue_put_dedup(&queue, one);
-+ paint_queue_put(&queue, one, 0);
++ 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(&queue, twos[i], PARENT2);
++ paint_queue_put(&state, twos[i], PARENT2);
- while (queue.max_nonstale) {
- struct commit *commit = nonstale_queue_get_dedup(&queue);
-+ while ((commit = paint_queue_get(&queue))) {
++ while ((commit = paint_queue_get(&state))) {
struct commit_list *parents;
int flags;
timestamp_t generation = commit_graph_generation(commit);
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
continue;
if (repo_parse_commit(r, p)) {
- clear_nonstale_queue(&queue);
-+ clear_prio_queue(&queue.pq);
++ clear_prio_queue(&state.queue);
commit_list_free(*result);
*result = NULL;
/*
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
}
- p->object.flags |= flags;
- nonstale_queue_put_dedup(&queue, p);
-+ paint_queue_put(&queue, p, flags);
++ paint_queue_put(&state, p, flags);
}
-+
-+ if (queue.p1_count + queue.p2_count +
-+ queue.pending_merge_bases == 0)
-+ break;
}
- clear_nonstale_queue(&queue);
-+ clear_prio_queue(&queue.pq);
++ clear_prio_queue(&state.queue);
+ trace2_data_intmax("paint_down_to_common", r,
+ "steps", steps);
commit_list_sort_by_date(result);
- return 0;
- }
-: ---------- > 6: 8c72f01083 commit-reach: remove unused nonstale_queue dedup wrappers
3: ed12a5cb5b ! 7: d84b932e5b commit-reach: terminate merge-base walk when one paint side is exhausted
@@ Commit message
commit-reach: terminate merge-base walk when one paint side is exhausted
Add an early termination check to paint_down_to_common() using the
- per-side counters introduced in the previous commit. 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.
+ 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 popped and recorded before
+ all merge-base candidates have been dequeued and recorded before
exiting.
The INFINITY gate ensures correctness: commits without a commit-graph
@@ Commit message
once the walk enters the finite-generation region where ordering
guarantees hold.
- On large repositories with commit-graph, this yields 100-1000x
- speedups for merge-base queries where one side (e.g. a PR branch) is
- much smaller than the other.
+ 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>
+ ## Documentation/technical/paint-down-to-common.adoc ##
+@@ Documentation/technical/paint-down-to-common.adoc: ends when one of the following conditions holds:
+
+ 1. The queue is empty.
+ 2. The queue contains only stale entries.
++ 3. 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
+ ~~~~~~~~~~~~~~~~~~~~~
+@@ Documentation/technical/paint-down-to-common.adoc: 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.
++
+ Related documentation
+ ---------------------
+
+
## commit-reach.c ##
-@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
- if (queue.p1_count + queue.p2_count +
- queue.pending_merge_bases == 0)
- break;
+@@ commit-reach.c: static void paint_queue_put(struct paint_state *state,
+
+ static struct commit *paint_queue_get(struct paint_state *state)
+ {
+- struct commit *commit;
++ struct commit *commit = prio_queue_get(&state->queue);
+
+- if (!state->p1_count && !state->p2_count &&
+- !state->pending_merge_bases)
++ if (!commit)
+ return NULL;
+
+- commit = prio_queue_get(&state->queue);
+- if (commit) {
+- commit->object.flags &= ~ENQUEUED;
+- paint_count_update(state, commit->object.flags, -1);
++ commit->object.flags &= ~ENQUEUED;
+
++ if (!state->pending_merge_bases) {
++ if (!state->p1_count && !state->p2_count)
++ return NULL;
+ /*
+ * Side exhaustion: a new merge-base can only form
+ * when both PARENT1-only and PARENT2-only commits
-+ * remain in the queue. In the finite-generation
++ * remain in the queue. In the finite-generation
+ * region the queue is ordered topologically, so
+ * no future step can add paint to visited commits
+ * and an exhausted side cannot reappear.
+ */
-+ if (generation < GENERATION_NUMBER_INFINITY &&
-+ queue.pending_merge_bases == 0 &&
-+ (queue.p1_count == 0 || queue.p2_count == 0))
-+ break;
++ if ((!state->p1_count || !state->p2_count) &&
++ commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
++ return NULL;
}
++
++ paint_count_update(state, commit->object.flags, -1);
+ return commit;
+ }
+
+
+ ## t/t6600-test-reach.sh ##
+@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps' '
+ cp commit-graph-full .git/objects/info/commit-graph &&
+ GIT_TRACE2_EVENT="$(pwd)/trace-full.txt" \
+ git merge-base --all commit-9-9 commit-9-1 >actual &&
+- test_trace2_data paint_down_to_common steps 80 <trace-full.txt &&
++ test_trace2_data paint_down_to_common steps 9 <trace-full.txt &&
+
+ cp commit-graph-half .git/objects/info/commit-graph &&
+ GIT_TRACE2_EVENT="$(pwd)/trace-half.txt" \
+ git merge-base --all commit-9-9 commit-9-1 >actual &&
+- test_trace2_data paint_down_to_common steps 81 <trace-half.txt
++ test_trace2_data paint_down_to_common steps 57 <trace-half.txt
+ '
- clear_prio_queue(&queue.pq);
+ test_expect_success 'reduce_heads' '
--
gitgitgadget
^ permalink raw reply
* Re: [PATCH GSoC RFC v13 06/12] connect: refactor packet writing
From: Pablo Sabater @ 2026-06-24 12:08 UTC (permalink / raw)
To: Karthik Nayak
Cc: gitster, peff, eric.peijian, chriscool, git, jltobler, toon,
chandrapratap3519
In-Reply-To: <CAOLa=ZSvxXuf_bSzKMvViNQ5MuDAqxnQdo4asF9vfMhJaDQcVw@mail.gmail.com>
El lun, 22 jun 2026 a las 22:43, Karthik Nayak
(<karthik.188@gmail.com>) escribió:
>
> Pablo Sabater <pabloosabaterr@gmail.com> writes:
>
> [snip]
>
> > diff --git a/connect.c b/connect.c
> > index 1dced8e632..78c69d4485 100644
> > --- a/connect.c
> > +++ b/connect.c
> > @@ -700,16 +700,16 @@ int server_supports(const char *feature)
> > return !!server_feature_value(feature, NULL);
> > }
> >
> > -void write_fetch_command_and_capabilities(struct strbuf *req_buf,
> > - const struct string_list *server_options)
> > +void write_command_and_capabilities(struct strbuf *req_buf, const char *command,
> > + const struct string_list *server_options)
> > {
> > const char *hash_name;
> > int advertise_sid;
> >
> > repo_config_get_bool(the_repository, "transfer.advertisesid", &advertise_sid);
> >
> > - ensure_server_supports_v2("fetch");
> > - packet_buf_write(req_buf, "command=fetch");
> > + ensure_server_supports_v2(command);
> > + packet_buf_write(req_buf, "command=%s", command);
> > if (server_supports_v2("agent"))
> > packet_buf_write(req_buf, "agent=%s", git_user_agent_sanitized());
> > if (advertise_sid && server_supports_v2("session-id"))
> > @@ -727,7 +727,7 @@ void write_fetch_command_and_capabilities(struct strbuf *req_buf,
> > die(_("mismatched algorithms: client %s; server %s"),
> > the_hash_algo->name, hash_name);
> > packet_buf_write(req_buf, "object-format=%s", the_hash_algo->name);
> > - } else if (hash_algo_by_ptr(the_hash_algo) != GIT_HASH_SHA1_LEGACY) {
> > + } else if (hash_algo_by_ptr(the_hash_algo) != GIT_HASH_SHA1) {
> > die(_("the server does not support algorithm '%s'"),
> > the_hash_algo->name);
> > }
>
> Why did we make this change? If the server doesn't support v2, then the
> object format should be `GIT_HASH_SHA1_LEGACY`. While the value of it is
> indeed `GIT_HASH_SHA1`, it indicates a scenario where there was no
> option to select object hash, which is the scenario here.
>
> If there is a reason to make such a change, perhaps we should highlight
> this in the commit message.
Hi!
There should be no diff related to that line, In some point between
Eric's last version (v11) and mine's firs (v12) the original code
changed. On the diff from v11 [1] the object format is the same, i
didn't notice this change and it's wrong, I'll fix it for v14, Thanks!
>
> > diff --git a/connect.h b/connect.h
> > index c4f6ea4b0a..8f4c523892 100644
> > --- a/connect.h
> > +++ b/connect.h
> > @@ -34,8 +34,12 @@ void check_stateless_delimiter(int stateless_rpc,
> > struct packet_reader *reader,
> > const char *error);
> >
> > +/*
> > + * Writes a command along with the requested server capabilities/features into a
> > + * request buffer.
> > + */
> > struct string_list;
>
> The comment should be above the function and not the forward
> declaration.
True, I'll fix it for v14.
>
> While we're here, why not `#include "string-list.h"` and remove the
> forward declaration, is there a circular dependency?
I believe this was right because from what I know forward declarations
are prefered in headers when in this case, the struct is only used as
a pointer. Investigating, this came from a review from patrick [2].
[snip]
[1]: https://lore.kernel.org/git/20250221190451.12536-5-eric.peijian@gmail.com/
[2]: https://lore.kernel.org/git/Z0RIqUAoEob8lGfM@pks.im/
Thanks for the review,
Pablo.
^ permalink raw reply
* Re: [PATCH v3 0/2] doc: clarify review replies and reroll timing
From: Patrick Steinhardt @ 2026-06-24 11:47 UTC (permalink / raw)
To: Weijie Yuan; +Cc: git, gitster
In-Reply-To: <cover.1782028813.git.wy@wyuan.org>
On Sun, Jun 21, 2026 at 04:04:36PM +0800, Weijie Yuan wrote:
> Changes in v3:
>
> - Reworked the substantial-rework case. Instead of suggesting that
> authors send a new version sooner, the text now advises authors not
> to rush out an updated version before reviewing the larger changes
> carefully. It recommends replying to the review that prompted the
> rewrite, saying that a substantial rework is planned, and pointing
> out which parts of the current series will become obsolete.
>
> - Dropped the advice that a topic close to being accepted may justify
> a quicker reroll.
>
> - Removed "how close the topic is to being accepted" from the short
> reroll-timing guidance in Documentation/SubmittingPatches.
>
> - Updated the commit message of patch 2 accordingly.
I'm happy with this version, thanks!
Patrick
^ permalink raw reply
* Re: [PATCH v3 2/2] doc: advise batching patch rerolls
From: Patrick Steinhardt @ 2026-06-24 11:46 UTC (permalink / raw)
To: Weijie Yuan; +Cc: git, gitster
In-Reply-To: <e1050a6ef5e26299b2c6d9743067fe3d7f4f8071.1782028813.git.wy@wyuan.org>
On Sun, Jun 21, 2026 at 04:05:34PM +0800, Weijie Yuan wrote:
> diff --git a/Documentation/MyFirstContribution.adoc b/Documentation/MyFirstContribution.adoc
> index 00704ab91e..35105bc3b4 100644
> --- a/Documentation/MyFirstContribution.adoc
> +++ b/Documentation/MyFirstContribution.adoc
> @@ -1330,6 +1330,28 @@ previous one" patches over 2 days), reviewers would strongly prefer if a
> single polished version came 2 days later instead, and that version with
> fewer mistakes were the only one they would need to review.
>
> +This consideration applies not only when going from the initial patch to v2,
> +but also to later iterations of the same series. There is no fixed rule for how
> +long to wait before sending a new version. A useful default is to send at most
> +one new version of the same patch series per day. This gives multiple reviewers
> +time to comment, gives reviewers across time zones a fair chance to
> +participate, lets you batch feedback together, and gives you time to think
> +through the comments you received. Knowing that you should not immediately send
> +another version also encourages you to review the patches more carefully before
> +sending them, catch small mistakes such as typos and off-by-one errors
> +yourself, and let reviewers spend more of their attention on design,
> +algorithms, and other substantial issues.
> +
> +The right timing depends on the topic and the feedback. Larger series usually
> +need more review time. If the only comments so far are minor, such as typo
> +fixes, it often makes sense to wait a little longer in case deeper reviews are
> +still coming. If the comments call for substantial rework, do not rush out an
> +updated version before you have reviewed the larger changes carefully. Instead,
> +reply to the review that prompted the rewrite, say that you are preparing a
> +substantial rework, and mention which parts of the current series will become
> +obsolete so reviewers can avoid spending time on them until the updated series
> +is ready.
Makes sense.
Patrick
^ permalink raw reply
* Re: [PATCH v2 2/2] doc: advise batching patch rerolls
From: Patrick Steinhardt @ 2026-06-24 11:46 UTC (permalink / raw)
To: Weijie Yuan; +Cc: Junio C Hamano, git
In-Reply-To: <ajVCD51lLvHreyJB@wyuan.org>
On Fri, Jun 19, 2026 at 09:20:15PM +0800, Weijie Yuan wrote:
> Sorry for the late reply. I spent some time looking back through the
> discussions on earlier patch series, to check my patch itself, of course
> because I'm apparently a newcomer here.
>
> On Wed, Jun 17, 2026 at 10:50:53AM -0700, Junio C Hamano wrote:
> > > If the comments require substantial rework, sending a new version
> > > +sooner may save reviewers from spending time on a version you already know will
> > > +change significantly.
> >
> > I am not sure about this one. Even though the intention to avoid
> > wasting reviewers' time spent on reading through the previous
> > version that will be invalidated is a good one, by definition, a
> > substantial rework will naturally take time, and it is better not to
> > rush and send an updated version with substantial changes that you
> > yourself haven't had a chance to thoroughly review yet.
> >
> > In such a case, it would be a better idea to respond to the review
> > that made you realize a substantial rewrite is needed with a simple
> > "I'll make a substantial rework based on this comment, which would
> > invalidate this and that part of the current patch series, so please
> > do not waste reviewer cycles on these parts until I send an updated
> > series out" message.
>
> I think the approach you recommended is obviously more reasonable.
>
> It would be better to give everyone a heads-up "I am working on a
> new version."
>
> I will improve this part accordingly.
Yeah, that works for me, as well.
> > > If the topic is close to being accepted and the remaining
> > > +comments are small, a quicker new version may also be fine.
> >
> > I am not sure if this needs to be codified.
> >
> > I often see (e.g., in patches from Patrick) that an iteration is
> > marked clearly as final candidate that the author is not aware of
> > any outstanding issues. This encourages reviewers to ask "what
> > about this one raised there?" to remind what is missed, or chime in
> > with "yup, this looks good" to show support. Such a note is highly
> > recommended, but I do not see a need to say "the (supposedly) final
> > one is specifically allowed to be sent without waiting" even then.
>
> Actually I thought Patrick would say something here ;-) so I waited a
> few more days to see whether anyone else had any suggestions.
>
> But here I think Patrick's original intention is: If your series is
> *close* to be accepted, (while I'm not sure what the precise definition
> of this "close to be accepted", does it means: commented by Junio with
> "Looks good", or reviewed by the community/core contributors with "Makes
> sense"?) and this time there happens to be a small issue, you can
> re-roll quickly to make your series more "sturdy" to wait for
> maintainer's final examination and further merges.
>
> So, I think the situation you are describing here is that this version
> of the patch has already been declared by the *author* to be the final
> version. (i.e. waiting for Junio to do the last exam)
My "close to be accepted" feeling is when you've had multiple rounds of
design discussions already, everyone is on the same page, and all you
got on the last review round is a couple of typo fixes.
But all of this is highly subjective, so it'll always depend and it
won't be easy to codify all of that. Nor is that necessary, I guess. We
really only want to provide some rough guidance.
> Therefore, I do not think the two situations conflict with each other,
> or are directly related. One concerns a patch that is already close to
> receiving the maintainer's final verdict, where a minor issue is
> discovered and the author quickly rerolls it. The other concerns an
> author who, without realizing that some issues remain unresolved, rushes
> to send what they believe to be the final version and then waits for the
> maintainer to review it.
>
> For the latter case, I think it would be better to add a sentence along
> the lines of: "Before sending a new version/the final version, check
> once more whether there are any unresolved issues," if the existing
> documentation does not already make this clear.
I think that should mostly be clear with our documentation. And
eventually, we should also expect people to have some common sense :)
> That said, I am not familiar with how patch discussions have played out
> in the past, so please directly point out any mistakes in my
> understanding. I have to admit that, by this point in writing the
> message, I have become a little tangled up in my own reasoning.
I guess that's kind of expected, mostly because many of these things are
highly subjective and will depend on the situation. The guidance does
not have to be perfect, you'll probably be able to find counterexamples
for many of the cases.
Patrick
^ permalink raw reply
* Re: [PATCH 0/6] receive-pack: use ODB transactions to stage object writes
From: Patrick Steinhardt @ 2026-06-24 11:27 UTC (permalink / raw)
To: Justin Tobler; +Cc: git
In-Reply-To: <20260624041920.2601961-1-jltobler@gmail.com>
On Tue, Jun 23, 2026 at 11:19:14PM -0500, Justin Tobler wrote:
> Greetings,
>
> This patch series replaces direct usage of the `tmp_objdir` interfaces
> in git-receive-pack(1) to instead use the `odb_transaction` interfaces
> to create/manage a staging area to write objects to. The purpose of this
> change is to get git-receive-pack(1) one step closer to being ODB
> backend agnostic. For now, the object writes themselves are still
> "files" backend specific due to being handled by the git-index-pack(1)
> and git-unpack-objects(1) child processes. This will be tackled in a
> separate series though.
Thanks, this was a pleasant read. I've got a bunch of comments, but
overall I really like the direction of this patch series.
Patrick
^ permalink raw reply
* Re: [PATCH 6/6] builtin/receive-pack: stage incoming objects via ODB transactions
From: Patrick Steinhardt @ 2026-06-24 11:26 UTC (permalink / raw)
To: Justin Tobler; +Cc: git
In-Reply-To: <20260624041920.2601961-7-jltobler@gmail.com>
On Tue, Jun 23, 2026 at 11:19:20PM -0500, Justin Tobler wrote:
> Objects received by git-receive-pack(1) are quarantined in a temporary
> "incoming" directory and migrated into the object database prior to the
> reference updates. The quarantine is currently managed through
> `tmp_objdir` directly. In a pluggable ODB future, how exactly an object
> gets written to a transaction may vary for a given ODB source. Refactor
> git-receive-pack(1) to use the ODB transaction interfaces to manage the
> object staging area in a more agnostic manner accordingly.
>
> Note that the temporary directory created for git-receive-pack(1) is
> eagerly created and uses a different prefix name. This behavior is
A different prefix name compared to what?
> special cased in the "files" backend by having `odb_transaction_begin()`
> callers that require this behavior provide an `ODB_TRANSACTION_RECEIVE`
> flag.
Okay. I guess this is to retain existing behaviour where the temporary
directory is created lazily everywhere else. Makes me wonder whether we
should eventually change this to just unconditionally create the
directory in all cases so that we can drop this new flag.
It might've also made sense to split this commit up into two: one to
introduce the flag parameter, and then one to do the changes to
git-receive-pack(1).
> diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
> index 19eb6a1b61..ee8e03e2ab 100644
> --- a/builtin/receive-pack.c
> +++ b/builtin/receive-pack.c
> @@ -112,8 +112,6 @@ static enum {
> } use_keepalive;
> static int keepalive_in_sec = 5;
>
> -static struct tmp_objdir *tmp_objdir;
> -
> static struct proc_receive_ref {
> unsigned int want_add:1,
> want_delete:1,
I assume the goal is that we convert all other users of the tmp-objdir
subsystem to also use transactions eventually, so that this becomes an
implementation detail fo the files transaction?
> @@ -2106,14 +2104,13 @@ static void execute_commands(struct command *commands,
> * Now we'll start writing out refs, which means the objects need
> * to be in their final positions so that other processes can see them.
> */
> - if (tmp_objdir_migrate(tmp_objdir) < 0) {
> + if (odb_transaction_commit(the_repository->objects->transaction)) {
> for (cmd = commands; cmd; cmd = cmd->next) {
> if (!cmd->error_string)
> cmd->error_string = "unable to migrate objects to permanent storage";
> }
> return;
> }
> - tmp_objdir = NULL;
We don't need to unset the transaction because that's what
`odb_transaction_commit()` already does for us, I assume?
> @@ -2326,7 +2323,8 @@ static void push_header_arg(struct strvec *args, struct pack_header *hdr)
> ntohl(hdr->hdr_version), ntohl(hdr->hdr_entries));
> }
>
> -static const char *unpack(int err_fd, struct shallow_info *si)
> +static const char *unpack(int err_fd, struct shallow_info *si,
> + struct odb_transaction *transaction)
> {
> struct pack_header hdr;
> const char *hdr_err;
It feels a bit weird that we sometimes pass the transaction as
parameter, whereas othertimes we access it via `the_repository`.
> @@ -2351,20 +2349,7 @@ static const char *unpack(int err_fd, struct shallow_info *si)
> strvec_push(&child.args, alt_shallow_file);
> }
>
> - tmp_objdir = tmp_objdir_create(the_repository, "incoming");
> - if (!tmp_objdir) {
> - if (err_fd > 0)
> - close(err_fd);
> - return "unable to create temporary object directory";
> - }
> - strvec_pushv(&child.env, tmp_objdir_env(tmp_objdir));
> -
> - /*
> - * Normally we just pass the tmp_objdir environment to the child
> - * processes that do the heavy lifting, but we may need to see these
> - * objects ourselves to set up shallow information.
> - */
> - tmp_objdir_add_as_alternate(tmp_objdir);
> + strvec_pushv(&child.env, odb_transaction_env(transaction));
Interesting, this here seems like a change in behaviour. Previously we
added the transactions as an alternate, but now we only propagate it via
the environment. I didn't see this mentioned in the commit message.
> @@ -2707,7 +2694,10 @@ int cmd_receive_pack(int argc,
> if (!si.nr_ours && !si.nr_theirs)
> shallow_update = 0;
> if (!delete_only(commands)) {
> - unpack_status = unpack_with_sideband(&si);
> + if (odb_transaction_begin(the_repository->objects, &transaction, ODB_TRANSACTION_RECEIVE))
> + unpack_status = "unable to start ODB transaction";
s/ODB/object/
This may be visible to the user, and "ODB" may mean nothing to them.
> diff --git a/object-file.c b/object-file.c
> index 14064d188a..e7958753ec 100644
> --- a/object-file.c
> +++ b/object-file.c
> @@ -1702,7 +1703,8 @@ static const char **odb_transaction_files_env(struct odb_transaction *base)
> }
>
> int odb_transaction_files_begin(struct odb_source *source,
> - struct odb_transaction **out)
> + struct odb_transaction **out,
> + enum odb_transaction_flags flags)
> {
> struct odb_transaction_files *transaction;
> struct object_database *odb = source->odb;
> @@ -1717,6 +1719,20 @@ int odb_transaction_files_begin(struct odb_source *source,
> transaction->base.commit = odb_transaction_files_commit;
> transaction->base.write_object_stream = odb_transaction_files_write_object_stream;
> transaction->base.env = odb_transaction_files_env;
> +
> + transaction->prefix = "bulk-fsync";
> + if (flags & ODB_TRANSACTION_RECEIVE) {
> + /*
> + * ODB transactions for git-receive-pack(1) eagerly create a
> + * temporary directory and use a different prefix.
> + */
> + transaction->prefix = "incoming";
> + if (odb_transaction_files_prepare(&transaction->base)) {
> + free(transaction);
> + return -1;
> + }
> + }
> +
Okay, makes sense. I really wonder whether we need to insist this much
on the exact name used by this, but better be safe than sorry for now I
guess.
And as mentioned before, I also wonder whether it really makes sense to
have the lazy creation of the tmp-objdir. Maybe add a NEEDSWORK item
here that mentions we want to investigate whether this is even needed at
all?
> diff --git a/odb/transaction.h b/odb/transaction.h
> index 536458297b..78392ff13d 100644
> --- a/odb/transaction.h
> +++ b/odb/transaction.h
> @@ -44,6 +43,10 @@ struct odb_transaction {
> const char **(*env)(struct odb_transaction *transaction);
> };
>
> +enum odb_transaction_flags {
> + ODB_TRANSACTION_RECEIVE = (1 << 0),
> +};
It's not clear at all what this flag does based on its name, so we
should have documentation for it.
Patrick
^ permalink raw reply
* Re: [PATCH 5/6] odb/transaction: add transaction env interface
From: Patrick Steinhardt @ 2026-06-24 11:26 UTC (permalink / raw)
To: Justin Tobler; +Cc: git
In-Reply-To: <20260624041920.2601961-6-jltobler@gmail.com>
On Tue, Jun 23, 2026 at 11:19:19PM -0500, Justin Tobler wrote:
> The ODB transaction backend is responsible for creating/managing its own
> staging area for writing objects. Other child processes spawned by Git
> may need to access to uncommitted objects or write new objects in the
s/may need to access to/may need access to/
> staging area though.
>
> Introduce `odb_transaction_env()` which is expected to provide the set
> of environment variables needed by a child process to access the
> transaction staging area.
Possessive s is missing, I think.
> diff --git a/object-file.c b/object-file.c
> index 696f05dc2d..14064d188a 100644
> --- a/object-file.c
> +++ b/object-file.c
> @@ -1691,6 +1691,16 @@ static int odb_transaction_files_commit(struct odb_transaction *base)
> return 0;
> }
>
> +static const char **odb_transaction_files_env(struct odb_transaction *base)
> +{
> + struct odb_transaction_files *transaction =
> + container_of(base, struct odb_transaction_files, base);
> +
> + odb_transaction_files_prepare(&transaction->base);
> +
> + return tmp_objdir_env(transaction->objdir);
> +}
> +
> int odb_transaction_files_begin(struct odb_source *source,
> struct odb_transaction **out)
> {
Makes sense. Transactions may have a different way to quarantine the
write than using a quarantine directory. So making this functionality
pluggable so that backends may expose a separate set of environment
variables feels sensible.
> diff --git a/odb/transaction.h b/odb/transaction.h
> index 7898770071..536458297b 100644
> --- a/odb/transaction.h
> +++ b/odb/transaction.h
> @@ -32,6 +32,16 @@ struct odb_transaction {
> int (*write_object_stream)(struct odb_transaction *transaction,
> struct odb_write_stream *stream, size_t len,
> struct object_id *oid);
> +
> + /*
> + * This callback is expected to return a NULL-terminated array of
> + * environment variables that a child process should inherit so
> + * that its object writes participate in the transaction. The
> + * returned array is owned by the backend and remains valid until
> + * the transaction ends. May return NULL when the backend does not
> + * need to expose any state to child processes.
> + */
> + const char **(*env)(struct odb_transaction *transaction);
Would it make more sense to adapt this function so that:
- It receives a `struct strvec` as input that the environment
variables are to be amended to.
- It returns a normal error code to indicate errors?
Patrick
^ permalink raw reply
* Re: [PATCH 4/6] odb/transaction: propagate commit errors
From: Patrick Steinhardt @ 2026-06-24 11:26 UTC (permalink / raw)
To: Justin Tobler; +Cc: git
In-Reply-To: <20260624041920.2601961-5-jltobler@gmail.com>
On Tue, Jun 23, 2026 at 11:19:18PM -0500, Justin Tobler wrote:
> diff --git a/odb/transaction.h b/odb/transaction.h
> index cd6d50f2e5..7898770071 100644
> --- a/odb/transaction.h
> +++ b/odb/transaction.h
> @@ -54,7 +54,7 @@ static inline void odb_transaction_begin_or_die(struct object_database *odb,
> * Commits an ODB transaction making the written objects visible. If the
> * specified transaction is NULL, the function is a no-op.
> */
> -void odb_transaction_commit(struct odb_transaction *transaction);
> +int odb_transaction_commit(struct odb_transaction *transaction);
Should the function comment be amended, as well? We should definitely
point out that calling this with a NULL transaction also returns
success.
Patrick
^ permalink raw reply
* Re: [PATCH 3/6] odb/transaction: propagate begin errors
From: Patrick Steinhardt @ 2026-06-24 11:26 UTC (permalink / raw)
To: Justin Tobler; +Cc: git
In-Reply-To: <20260624041920.2601961-4-jltobler@gmail.com>
On Tue, Jun 23, 2026 at 11:19:17PM -0500, Justin Tobler wrote:
> diff --git a/odb/transaction.c b/odb/transaction.c
> index b16e07aebf..d3de01db50 100644
> --- a/odb/transaction.c
> +++ b/odb/transaction.c
> @@ -2,14 +2,20 @@
> #include "odb/source.h"
> #include "odb/transaction.h"
>
> -struct odb_transaction *odb_transaction_begin(struct object_database *odb)
> +int odb_transaction_begin(struct object_database *odb,
> + struct odb_transaction **out)
> {
> - if (odb->transaction)
> - return NULL;
> + int ret;
>
> - odb_source_begin_transaction(odb->sources, &odb->transaction);
> + if (odb->transaction) {
> + *out = NULL;
> + return 0;
> + }
Hm. So we may return successful, but not set the `out` pointer to a
transaction. And...
> diff --git a/odb/transaction.h b/odb/transaction.h
> index f4c1ebfaaa..cd6d50f2e5 100644
> --- a/odb/transaction.h
> +++ b/odb/transaction.h
> @@ -33,11 +35,20 @@ struct odb_transaction {
> };
>
> /*
> - * Starts an ODB transaction. Subsequent objects are written to the transaction
> - * and not committed until odb_transaction_commit() is invoked on the
> - * transaction. If the ODB already has a pending transaction, NULL is returned.
> + * Starts an ODB transaction and returns it via `out`. Subsequent objects are
> + * written to the transaction and not committed until odb_transaction_commit()
> + * is invoked on the transaction. Returns 0 on success and a negative value on
> + * error. If the ODB already has a pending transaction, `out` is set to NULL.
> */
> -struct odb_transaction *odb_transaction_begin(struct object_database *odb);
> +int odb_transaction_begin(struct object_database *odb,
> + struct odb_transaction **out);
> +
> +static inline void odb_transaction_begin_or_die(struct object_database *odb,
> + struct odb_transaction **out)
> +{
> + if (odb_transaction_begin(odb, out))
> + die(_("failed to start ODB transaction"));
> +}
... we don't special-case that here, either. So a caller may invoke the
function, not die, but it might still not have a valid transaction. That
feels wrong to me.
Patrick
^ permalink raw reply
* Re: [PATCH 2/6] object-file: propagate files transaction errors
From: Patrick Steinhardt @ 2026-06-24 11:26 UTC (permalink / raw)
To: Justin Tobler; +Cc: git
In-Reply-To: <20260624041920.2601961-3-jltobler@gmail.com>
On Tue, Jun 23, 2026 at 11:19:16PM -0500, Justin Tobler wrote:
> The "files" transaction backend may encounter errors related to managing
> the temporary directory used to stage objects, but silently ignores
> these errors. Instead return errors encountered in the
> `odb_transaction_files_{prepare,begin,commit}()` interfaces to allow
> callers to handle as needed.
Missing a then? "to handle as needed" -> "to handle them as needed"
Makes sense. It always felt a bit off that those functions didn't have a
way to signal errors to the caller.
> diff --git a/object-file.c b/object-file.c
> index a3eb8d71dd..18c2df75fb 100644
> --- a/object-file.c
> +++ b/object-file.c
> @@ -499,7 +499,7 @@ struct odb_transaction_files {
> struct transaction_packfile packfile;
> };
>
> -static void odb_transaction_files_prepare(struct odb_transaction *base)
> +static int odb_transaction_files_prepare(struct odb_transaction *base)
> {
> struct odb_transaction_files *transaction =
> container_of_or_null(base, struct odb_transaction_files, base);
By the way, is there any reason why those functions are still hosted in
"object-file.c" instead of in "odb/source-files.c"? I should probably
know, but I forgot.
> @@ -511,11 +511,15 @@ static void odb_transaction_files_prepare(struct odb_transaction *base)
> * added at the time they call odb_transaction_files_begin.
> */
> if (!transaction || transaction->objdir)
> - return;
> + return 0;
>
> transaction->objdir = tmp_objdir_create(base->source->odb->repo, "bulk-fsync");
> - if (transaction->objdir)
> - tmp_objdir_replace_primary_odb(transaction->objdir, 0);
> + if (!transaction->objdir)
> + return -1;
Huh. So previously we just didn't handle this error at all and just
continued to tag along? Did that result in anything sensible or was this
just YOLOing it?
> @@ -542,13 +546,13 @@ static void fsync_loose_object_transaction(struct odb_transaction *base,
> /*
> * Cleanup after batch-mode fsync_object_files.
> */
> -static void flush_loose_object_transaction(struct odb_transaction_files *transaction)
> +static int flush_loose_object_transaction(struct odb_transaction_files *transaction)
Feels like this function should've been renamed in the preceding commit,
as well.
> {
> struct strbuf temp_path = STRBUF_INIT;
> struct tempfile *temp;
>
> if (!transaction->objdir)
> - return;
> + return 0;
>
> /*
> * Issue a full hardware flush against a temporary file to ensure
> @@ -570,8 +574,12 @@ static void flush_loose_object_transaction(struct odb_transaction_files *transac
There is a call to `xmks_tempfile()` hidden that can fail, but that
failure is already handled in that function itself by dying.
> * Make the object files visible in the primary ODB after their data is
> * fully durable.
> */
> - tmp_objdir_migrate(transaction->objdir);
> + if (tmp_objdir_migrate(transaction->objdir))
> + return -1;
Feels like another case of YOLOing it. The migration could have failed,
but we just ignored that failure and never told the user about it. The
result may be silent corruption, I assume?
> @@ -1670,27 +1678,34 @@ int read_loose_object(struct repository *repo,
> return ret;
> }
>
> -static void odb_transaction_files_commit(struct odb_transaction *base)
> +static int odb_transaction_files_commit(struct odb_transaction *base)
> {
> struct odb_transaction_files *transaction =
> container_of(base, struct odb_transaction_files, base);
>
> - flush_loose_object_transaction(transaction);
> + if (flush_loose_object_transaction(transaction))
> + return -1;
> flush_packfile_transaction(transaction);
> +
> + return 0;
> }
>
> -struct odb_transaction *odb_transaction_files_begin(struct odb_source *source)
> +int odb_transaction_files_begin(struct odb_source *source,
> + struct odb_transaction **out)
> {
> struct odb_transaction_files *transaction;
> struct object_database *odb = source->odb;
>
> - if (odb->transaction)
> - return NULL;
> + if (odb->transaction) {
> + *out = NULL;
> + return 0;
> + }
>
> transaction = xcalloc(1, sizeof(*transaction));
> transaction->base.source = source;
> transaction->base.commit = odb_transaction_files_commit;
> transaction->base.write_object_stream = odb_transaction_files_write_object_stream;
> + *out = &transaction->base;
>
> - return &transaction->base;
> + return 0;
> }
It's still somewhat fishy that we have this ODB-level transaction, but
that's a preexisting issue and thus outside the scope of this patch
series. Ideally though, it would be possible for there to be multiple
transactions, and it would be the caller's responsibility for juggling
these transactions. Just as it happens with reference transactions.
> diff --git a/odb/transaction.h b/odb/transaction.h
> index 854fda06f5..f4c1ebfaaa 100644
> --- a/odb/transaction.h
> +++ b/odb/transaction.h
> @@ -17,7 +17,7 @@ struct odb_transaction {
> struct odb_source *source;
>
> /* The ODB source specific callback invoked to commit a transaction. */
> - void (*commit)(struct odb_transaction *transaction);
> + int (*commit)(struct odb_transaction *transaction);
We might want to document the returned error code here.
Patrick
^ permalink raw reply
* Re: [PATCH/RFC 2/6] commit-reach: introduce struct paint_queue with per-side counters
From: Kristofer Karlsson @ 2026-06-24 11:25 UTC (permalink / raw)
To: Derrick Stolee; +Cc: Kristofer Karlsson via GitGitGadget, git, Elijah Newren
In-Reply-To: <ec241a02-546c-4b5f-8ef7-06b4355d8fec@gmail.com>
On Tue, 23 Jun 2026 at 16:17, Derrick Stolee <stolee@gmail.com> wrote:
>
> I think this would be an appropriate way to handle this. If we
> pop and return NULL then it's ok that we removed data from the
> queue because it shouldn't be reused.
I have prepared v2 on GGG which I believe addresses all of the
feedback. The halt conditions now live inside paint_queue_get()
as you suggested.
I am not 100% happy with the halt-condition placement yet --
the existing loop in master already has several exit paths
(while condition, min_generation break, FIND_ALL break) and I
think there is an opportunity to consolidate them. But that is
a separate discussion and I do not want to derail this series.
I can propose some alternatives in a follow-up after this
lands.
Thanks,
Kristofer
^ permalink raw reply
* Re: [PATCH RFC v2 2/2] Move libgit.a sources into separate "lib/" directory
From: Oswald Buddenhagen @ 2026-06-24 11:23 UTC (permalink / raw)
To: Junio C Hamano
Cc: Patrick Steinhardt, git, brian m. carlson, Elijah Newren,
Derrick Stolee, Phillip Wood
In-Reply-To: <xmqqcxxi3eov.fsf@gitster.g>
On Mon, Jun 22, 2026 at 06:08:48AM -0700, Junio C Hamano wrote:
>it will make it harder to make
>fixes that can apply both to 2.55 and before and newer codebase.
>
which is why i would recommend applying this _before_ the release. it
affects only the build, which ci checks rather thoroughly, so the risk
of doing it late in the cycle is low.
this obviously won't help with backporting further back, nor will it
avoid having to rebase many pending branches, but see patrick's response
for that.
fwiw, i'm totally in favor of the change. i've always found the current
tree messy and confusing.
^ permalink raw reply
* [PATCH v2 4/4] connected: search promisor objects generically
From: Patrick Steinhardt @ 2026-06-24 10:37 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Christian Couder
In-Reply-To: <20260624-pks-connected-generic-promisor-checks-v2-0-132d73ee47b9@pks.im>
When performing connectivity checks we have to figure out whether any of
the new objects are promisor objects, as we cannot assume full
connectivity if so.
This check is performed by iterating through all packfiles in the
repository and searching each of them for the given object. Of course,
this mechanism is quite specific to implementation details of the object
database, as we assume that it uses packfiles in the first place.
Refactor the logic so that we instead use `odb_for_each_object_ext()`
with an object prefix filter and the `ODB_FOR_EACH_OBJECT_PROMISOR_ONLY`
flag. This will yield all objects that have the exact object name and
that are part of a promisor pack in a generic way.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
connected.c | 32 +++++++++++++++++++++-----------
1 file changed, 21 insertions(+), 11 deletions(-)
diff --git a/connected.c b/connected.c
index d2b334173f..b557ff5db9 100644
--- a/connected.c
+++ b/connected.c
@@ -11,6 +11,13 @@
#include "packfile.h"
#include "promisor-remote.h"
+static int promised_object_cb(const struct object_id *oid UNUSED,
+ struct object_info *oi UNUSED,
+ void *payload UNUSED)
+{
+ return 1;
+}
+
/*
* For partial clones, we don't want to have to do a regular connectivity check
* because we have to enumerate and exclude all promisor objects (slow), and
@@ -30,25 +37,28 @@ static int check_connected_promisor(oid_iterate_fn fn,
void *cb_data,
const struct object_id **oid)
{
+ struct odb_for_each_object_options opts = {
+ .flags = ODB_FOR_EACH_OBJECT_PROMISOR_ONLY,
+ .prefix_hex_len = the_repository->hash_algo->hexsz,
+ };
+ int err;
+
odb_reprepare(the_repository->objects);
do {
- struct packed_git *p;
+ opts.prefix = *oid;
- repo_for_each_pack(the_repository, p) {
- if (!p->pack_promisor)
- continue;
- if (find_pack_entry_one(*oid, p))
- goto promisor_pack_found;
- }
+ err = odb_for_each_object_ext(the_repository->objects,
+ NULL, promised_object_cb,
+ NULL, &opts);
+ if (err < 0)
+ return err;
/*
* We have found an object that is not part of a promisor pack,
* and thus we cannot skip the full connectivity check.
*/
- return 0;
-
-promisor_pack_found:
- ;
+ if (err > 0)
+ return 0;
} while ((*oid = fn(cb_data)) != NULL);
return 1;
--
2.55.0.rc1.745.g43192e7977.dirty
^ permalink raw reply related
* [PATCH v2 3/4] connected: split out promisor-based connectivity check
From: Patrick Steinhardt @ 2026-06-24 10:37 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Christian Couder
In-Reply-To: <20260624-pks-connected-generic-promisor-checks-v2-0-132d73ee47b9@pks.im>
When performing a connectivity check in a partial clone we try to avoid
doing the connectivity check by checking whether all new tips are part
of a promisor pack. This makes use of the fact that we don't expect full
connectivity for promised objects anyway, so it's basically fine if
those objects are not fully connected.
The logic that handles this promisor-based check is somewhat hard to
read though as it uses nested loops and gotos. Pull it out into a
standalone function, which makes it a bit easier to reason about.
We'll also further simplify the function in the next commit.
Suggested-by: Christian Couder <christian.couder@gmail.com>
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
connected.c | 85 ++++++++++++++++++++++++++++++++++++-------------------------
1 file changed, 51 insertions(+), 34 deletions(-)
diff --git a/connected.c b/connected.c
index 7e26976832..d2b334173f 100644
--- a/connected.c
+++ b/connected.c
@@ -11,6 +11,49 @@
#include "packfile.h"
#include "promisor-remote.h"
+/*
+ * For partial clones, we don't want to have to do a regular connectivity check
+ * because we have to enumerate and exclude all promisor objects (slow), and
+ * then the connectivity check itself becomes a no-op because in a partial
+ * clone every object is a promisor object. Instead, just make sure we
+ * received, in a promisor packfile, the objects pointed to by each wanted ref.
+ *
+ * Before checking for promisor packs, be sure we have the latest pack-files
+ * loaded into memory.
+ *
+ * Returns 1 when all object IDs have been found in promisor packs, in which
+ * case we're fully connected and thus done. Returns 0 when we have found
+ * objects in non-promisor packs, in which case we'll have to fall back to the
+ * rev-list-based connectivity checks. Returns a negative error code on error.
+ */
+static int check_connected_promisor(oid_iterate_fn fn,
+ void *cb_data,
+ const struct object_id **oid)
+{
+ odb_reprepare(the_repository->objects);
+ do {
+ struct packed_git *p;
+
+ repo_for_each_pack(the_repository, p) {
+ if (!p->pack_promisor)
+ continue;
+ if (find_pack_entry_one(*oid, p))
+ goto promisor_pack_found;
+ }
+
+ /*
+ * We have found an object that is not part of a promisor pack,
+ * and thus we cannot skip the full connectivity check.
+ */
+ return 0;
+
+promisor_pack_found:
+ ;
+ } while ((*oid = fn(cb_data)) != NULL);
+
+ return 1;
+}
+
/*
* If we feed all the commits we want to verify to this command
*
@@ -46,42 +89,16 @@ int check_connected(oid_iterate_fn fn, void *cb_data,
}
if (repo_has_promisor_remote(the_repository)) {
- /*
- * For partial clones, we don't want to have to do a regular
- * connectivity check because we have to enumerate and exclude
- * all promisor objects (slow), and then the connectivity check
- * itself becomes a no-op because in a partial clone every
- * object is a promisor object. Instead, just make sure we
- * received, in a promisor packfile, the objects pointed to by
- * each wanted ref.
- *
- * Before checking for promisor packs, be sure we have the
- * latest pack-files loaded into memory.
- */
- odb_reprepare(the_repository->objects);
- do {
- struct packed_git *p;
-
- repo_for_each_pack(the_repository, p) {
- if (!p->pack_promisor)
- continue;
- if (find_pack_entry_one(oid, p))
- goto promisor_pack_found;
- }
- /*
- * Fallback to rev-list with oid and the rest of the
- * object IDs provided by fn.
- */
- goto no_promisor_pack_found;
-promisor_pack_found:
- ;
- } while ((oid = fn(cb_data)) != NULL);
- if (opt->err_fd)
- close(opt->err_fd);
- return 0;
+ err = check_connected_promisor(fn, cb_data, &oid);
+ if (err) {
+ if (opt->err_fd)
+ close(opt->err_fd);
+ if (err > 0)
+ err = 0;
+ return err;
+ }
}
-no_promisor_pack_found:
if (opt->shallow_file) {
strvec_push(&rev_list.args, "--shallow-file");
strvec_push(&rev_list.args, opt->shallow_file);
--
2.55.0.rc1.745.g43192e7977.dirty
^ permalink raw reply related
* [PATCH v2 2/4] odb/source-packed: support flags when iterating an object prefix
From: Patrick Steinhardt @ 2026-06-24 10:37 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Christian Couder
In-Reply-To: <20260624-pks-connected-generic-promisor-checks-v2-0-132d73ee47b9@pks.im>
Callers of `odb_for_each_object()` can specify an optional object name
prefix so that we only yield objects that match it. This is incompatible
though with passing flags at the same time, as we don't yet know to
handle them.
Loosen this restriction by calling `should_exclude_pack()`.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
odb/source-packed.c | 22 +++++++++++++++++++---
1 file changed, 19 insertions(+), 3 deletions(-)
diff --git a/odb/source-packed.c b/odb/source-packed.c
index 3afc4bf01f..6f31f0ff94 100644
--- a/odb/source-packed.c
+++ b/odb/source-packed.c
@@ -148,6 +148,7 @@ static int for_each_prefixed_object_in_midx(
const struct odb_for_each_object_options *opts,
struct odb_source_packed_for_each_object_wrapper_data *data)
{
+ bool pack_errors = false;
int ret;
for (; m; m = m->base_midx) {
@@ -171,6 +172,20 @@ static int for_each_prefixed_object_in_midx(
const struct object_id *current = NULL;
struct object_id oid;
+ if (opts->flags) {
+ uint32_t pack_id = nth_midxed_pack_int_id(m, i);
+ struct packed_git *pack;
+
+ if (prepare_midx_pack(m, pack_id)) {
+ pack_errors = true;
+ continue;
+ }
+
+ pack = nth_midxed_pack(m, pack_id);
+ if (should_exclude_pack(pack, opts->flags))
+ continue;
+ }
+
current = nth_midxed_object_oid(&oid, m, i);
if (!match_hash(len, opts->prefix->hash, current->hash))
@@ -198,6 +213,8 @@ static int for_each_prefixed_object_in_midx(
ret = 0;
out:
+ if (!ret && pack_errors)
+ ret = -1;
return ret;
}
@@ -260,9 +277,6 @@ static int odb_source_packed_for_each_prefixed_object(
bool pack_errors = false;
int ret;
- if (opts->flags)
- BUG("flags unsupported");
-
store->skip_mru_updates = true;
m = get_multi_pack_index(store);
@@ -275,6 +289,8 @@ static int odb_source_packed_for_each_prefixed_object(
for (e = packfile_store_get_packs(store); e; e = e->next) {
if (e->pack->multi_pack_index)
continue;
+ if (should_exclude_pack(e->pack, opts->flags))
+ continue;
if (open_pack_index(e->pack)) {
pack_errors = true;
--
2.55.0.rc1.745.g43192e7977.dirty
^ permalink raw reply related
* [PATCH v2 1/4] odb/source-packed: extract logic to skip certain packs
From: Patrick Steinhardt @ 2026-06-24 10:37 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Christian Couder
In-Reply-To: <20260624-pks-connected-generic-promisor-checks-v2-0-132d73ee47b9@pks.im>
The caller can pass flags that allow them to filter out specific kinds
of objects when iterating objects via `odb_for_each_object()`. This only
works for "normal" iteration though, as we `BUG()` when the user passes
flags and specifies an object prefix.
This limitation will be lifted in the next commit. Prepare for this by
extracting the logic that skips certain kinds of packs so that we can
easily reuse it.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
odb/source-packed.c | 28 ++++++++++++++++++----------
1 file changed, 18 insertions(+), 10 deletions(-)
diff --git a/odb/source-packed.c b/odb/source-packed.c
index 42c28fba0e..3afc4bf01f 100644
--- a/odb/source-packed.c
+++ b/odb/source-packed.c
@@ -126,6 +126,22 @@ static int match_hash(unsigned len, const unsigned char *a, const unsigned char
return 1;
}
+static bool should_exclude_pack(struct packed_git *p, enum odb_for_each_object_flags flags)
+{
+ if ((flags & ODB_FOR_EACH_OBJECT_LOCAL_ONLY) && !p->pack_local)
+ return true;
+ if ((flags & ODB_FOR_EACH_OBJECT_PROMISOR_ONLY) &&
+ !p->pack_promisor)
+ return true;
+ if ((flags & ODB_FOR_EACH_OBJECT_SKIP_IN_CORE_KEPT_PACKS) &&
+ p->pack_keep_in_core)
+ return true;
+ if ((flags & ODB_FOR_EACH_OBJECT_SKIP_ON_DISK_KEPT_PACKS) &&
+ p->pack_keep)
+ return true;
+ return false;
+}
+
static int for_each_prefixed_object_in_midx(
struct odb_source_packed *store,
struct multi_pack_index *m,
@@ -306,17 +322,9 @@ static int odb_source_packed_for_each_object(struct odb_source *source,
for (e = packfile_store_get_packs(packed); e; e = e->next) {
struct packed_git *p = e->pack;
- if ((opts->flags & ODB_FOR_EACH_OBJECT_LOCAL_ONLY) && !p->pack_local)
- continue;
- if ((opts->flags & ODB_FOR_EACH_OBJECT_PROMISOR_ONLY) &&
- !p->pack_promisor)
- continue;
- if ((opts->flags & ODB_FOR_EACH_OBJECT_SKIP_IN_CORE_KEPT_PACKS) &&
- p->pack_keep_in_core)
- continue;
- if ((opts->flags & ODB_FOR_EACH_OBJECT_SKIP_ON_DISK_KEPT_PACKS) &&
- p->pack_keep)
+ if (should_exclude_pack(p, opts->flags))
continue;
+
if (open_pack_index(p)) {
pack_errors = 1;
continue;
--
2.55.0.rc1.745.g43192e7977.dirty
^ permalink raw reply related
* [PATCH v2 0/4] connected: search promisor objects generically
From: Patrick Steinhardt @ 2026-06-24 10:37 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Christian Couder
In-Reply-To: <20260622-pks-connected-generic-promisor-checks-v1-0-25eba2698202@pks.im>
Hi,
this patch series refactors "connected.c" so that we search for promisor
objects in a generic way instead of reaching into internal of the object
database. As a result, the connectivity checks will work properly in
repos that don't use packfiles in the first place.
The series is built on top of 8d96f09e92 (Merge branch
'js/objects-larger-than-4gb-on-windows', 2026-06-19) with
ps/odb-source-packed at 1bba3c035d (odb/source-packed: drop pointer to
"files" parent source, 2026-06-17) merged into it.
Changes in v2:
- Fix the accidentally-dropped call to `odb_reprepare()`.
- Add a preparatory commit that splits out `check_connected_promisor()`.
I think also splitting out `check_connected_rev_list()` would only
have diminishing returns, so I skipped that part.
- Link to v1: https://patch.msgid.link/20260622-pks-connected-generic-promisor-checks-v1-0-25eba2698202@pks.im
Thanks!
Patrick
---
Patrick Steinhardt (4):
odb/source-packed: extract logic to skip certain packs
odb/source-packed: support flags when iterating an object prefix
connected: split out promisor-based connectivity check
connected: search promisor objects generically
connected.c | 95 ++++++++++++++++++++++++++++++++++-------------------
odb/source-packed.c | 50 ++++++++++++++++++++--------
2 files changed, 98 insertions(+), 47 deletions(-)
Range-diff versus v1:
1: 6ff1fc8d89 = 1: a1a1af0fc6 odb/source-packed: extract logic to skip certain packs
2: 1022a1fdcc = 2: bd81a9e478 odb/source-packed: support flags when iterating an object prefix
3: 102fab7df2 < -: ---------- connected: search promisor objects generically
-: ---------- > 3: f39ef68c3e connected: split out promisor-based connectivity check
-: ---------- > 4: 558f30a6f2 connected: search promisor objects generically
---
base-commit: 4a8e7a446f41435e157131162dfe901eca9250fe
change-id: 20260612-pks-connected-generic-promisor-checks-2933bff3028d
^ permalink raw reply
* Re: [PATCH RFC v2 2/2] Move libgit.a sources into separate "lib/" directory
From: Patrick Steinhardt @ 2026-06-24 10:32 UTC (permalink / raw)
To: Junio C Hamano
Cc: git, brian m. carlson, Elijah Newren, Derrick Stolee,
Phillip Wood
In-Reply-To: <xmqqcxxi3eov.fsf@gitster.g>
On Mon, Jun 22, 2026 at 06:08:48AM -0700, Junio C Hamano wrote:
> Patrick Steinhardt <ps@pks.im> writes:
>
> > The Git project is not exactly the easiest project to get started in:
> > it's written in C and POSIX shell, with bits of Perl, Rust and other
> > languages sprinkled into it. On top of that, the project has grown
> > somewhat organically over time, making the codebase hard to navigate.
> >
> > But there is a rather practical problem: finding your way around in our
> > project's tree is not easy. Doing a directory listing in the top-level
> > directory will present you with more than 550 files, which makes it
> > extremely hard for a newcomer to figure out what files they are even
> > supposed to look at.
>
> Well, many things already live in the dedicated corner of their own
> universe, like tests in t/, builtins in builtins/, and documentation
> in Documentation/. This is pretty much moving everything else in a
> single directory lib/. Surely there are things like top-level
> Makefile and other build- and ci-related things that do not move to
> lib/ for obvious reasons, but I view this move essentially to change
> "for core-ish and library-ish things, look at the top level
> directory" to "for core-ish and library-ish things look at lib/
> directory".
Right. It does drown out the things that have to live in the root
directory though, for example files like README.md or SECURITY.md.
> Would that make it easier to navigate? I am not sure. What I am
> sure is that this will force many in-flight topic (and soon to be
> in-flight because people are holding them back during the prerelease
> freeze period) to be updated, and it will make it harder to make
> fixes that can apply both to 2.55 and before and newer codebase.
That's definitely a downside, I agree.
I have a bit of a different angle on the second part: it's not uncommon
that projects move stuff around, and if Git cannot handle those
scenarios well that's a usability issue that we'd ideally fix. And by
doing such a rename we basically subject ourselves to the same pain that
other projects are seeing, which might give us more incentive to
actually fix those pain points.
This might be a bit of a weird take and might raise some eyebrows. But
it's basically a tooling issue, and we are the ones who provide the
tooling. So we're in the best position to fix it, and by doing so make
everyone elses lives easier, as well.
Who knows how good submodules would have been nowadays if we had used
them ourselves? :P
> So, my initial reaction is somewhat negative, but I am known to
> accept changes that I myself do not necessarily agree with, so...
That's fair, and just to state the obvious: I'm still happy if the
community decides that this is not worth doing. But from what I've seen
until now it seems like most feedback I got was rather positive. Which
honestly surprised me, I was expecting more pushback.
Thanks!
Patrick
^ permalink raw reply
* Re: [PATCH v3 4/4] notes: support an external command to display notes
From: Siddh Raman Pant @ 2026-06-24 9:53 UTC (permalink / raw)
To: j6t@kdbg.org
Cc: oswald.buddenhagen@gmx.de, gitster@pobox.com,
code@khaugsbakk.name, peff@peff.net, ps@pks.im,
git@vger.kernel.org, sandals@crustytoothpaste.net,
newren@gmail.com
In-Reply-To: <3a2ba6c0-4ced-4d2c-820e-401c2dff1dd1@kdbg.org>
[-- Attachment #1: Type: text/plain, Size: 2495 bytes --]
On Wed, Jun 24 2026 at 13:19:26 +0530, Johannes Sixt wrote:
> > One solution to this is to move the freshness policy out of git so that
> > it is someone else's problem. We can have a realtime fetch or faster
> > updation via external helper means. But unfortunately we lose the
> > coherence in the display of information, and so the user would end up
> > reinventing git log in his quest to have same workflow.
>
> You are presenting one solution here. But a more obvious solution would
> have been to make Git's notes implementation capable enough to keep up
> with the volume of notes that are produced by your team.
Git storage is inherently based on refs, so that would require massive
changes IMO. The actual fundamental problem here is that only the
latest state is useful at any given point of time, and not the past
history.
> Another solution would be to track the information outside of Git notes
> entirely, similar to how pull requests, issues, reviews, and
> conversations are tracked by Git hosters in databases outside of Git.
This is precisely what this allows for. The information is tracked
outside of Git, and the notes path just shows it along with the commit.
A developer works on the code using Git. An external website doesn't
allow the same level of coherence in display of information as a note.
The commit is a fundamental unit of change. IMO it makes sense for Git
to be able to show a note about it from a provided external medium.
> > Let's add support for notes.externalCommand, a protected-configuration
> > command that git runs as a long-lived helper when displaying notes. git
> > sends commit IDs to the helper and displays any returned text through
> > the existing notes formatting path. This keeps presentation in git
> > while letting the helper decide how fresh note text is obtained.
>
> To my eyes, this looks like an overengineered solution that helps one
> user of a niche feature of Git.
This can also allow for other uses too. For example, searching lore I
just found out that a colleague in Oracle Linux (Vegard) was trying to
solve a related problem in 2022:
https://lore.kernel.org/git/20220802075401.2393-1-vegard.nossum@oracle.com/
I think it was for achieving something like this more generally:
https://git.kernel.org/pub/scm/linux/kernel/git/vegard/linux.git/commit/?id=339f83612f3a569b194680768b22bf113c26a29d
An external notes command can be a solution for it.
Thanks,
Siddh
[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
^ permalink raw reply
* Re: [PATCH 11/11] reftable/table: fix OOB read on truncated table
From: Patrick Steinhardt @ 2026-06-24 9:46 UTC (permalink / raw)
To: oxsignal; +Cc: git
In-Reply-To: <20260624181426.NJDNpVd1RE-qJjBVh5jtQg@awo.kakao.com>
On Wed, Jun 24, 2026 at 06:14:26PM +0900, oxsignal wrote:
> Hi Patrick,
>
> Thanks for the patch series, for adding the dedicated reftable fuzzer, and for
> the credit.
>
> I reviewed the cover letter and the reftable hardening patches. Patch 05/11
> matches the OOB write case I reported:
> the new minimum block-size validation before handling the log block prevents
> the bogus inflated-size underflow from reaching the inflate/copy path.
>
> The rest of the series also looks like a good cleanup of the corrupted reftable
> parser surface, especially the restart-count/restart-offset and truncated-table
> checks.
> If I find any remaining malformed-table case that is not covered by this
> series, I will follow up with the reproducer.
>
> Thanks again for handling this so quickly.
Perfect, thanks for the report and reading through the patches!
Patrick
^ permalink raw reply
* [PATCH] gpg-interface: fix strip_cr_before_lf to only remove CR before LF
From: Antonio De Stefani @ 2026-06-24 9:36 UTC (permalink / raw)
To: git; +Cc: Antonio De Stefani
c4adea82 (Convert CR/LF to LF in tag signatures, 2008-07-11)
introduced CR stripping for GPG output on Windows, but intentionally
stripped all CR characters unconditionally to "keep the code simpler",
even though only \r\n sequences (Windows line endings) needed to be
normalized. 2f47eae2 (Split GPG interface into its own helper library,
2011-09-07) moved the code into gpg-interface.c, and 29b31577 (ssh
signing: add ssh key format and signing code, 2021-09-10) extracted
it into the remove_cr_after() helper when adding SSH signing support.
The original laziness was safe at the time because lone CR characters
are not expected in GPG signature output. However, the NEEDSWORK
comment left by a previous reader correctly identified that only
\r\n pairs should be stripped, not lone \r characters.
Fix the loop to skip \r only when immediately followed by \n, keeping
lone trailing CR characters intact. Rename the function to
strip_cr_before_lf to reflect its corrected behavior, and update
both call sites and their comments accordingly.
Signed-off-by: Antonio De Stefani <antonio.destefani08@gmail.com>
---
gpg-interface.c | 25 +++++++++++--------------
1 file changed, 11 insertions(+), 14 deletions(-)
diff --git a/gpg-interface.c b/gpg-interface.c
index dafd5371fa..95abf1ef4e 100644
--- a/gpg-interface.c
+++ b/gpg-interface.c
@@ -990,21 +990,18 @@ int sign_buffer(struct strbuf *buffer, struct strbuf *signature,
return ret;
}
-/*
- * Strip CR from the line endings, in case we are on Windows.
- * NEEDSWORK: make it trim only CRs before LFs and rename
- */
-static void remove_cr_after(struct strbuf *buffer, size_t offset)
+/* Strip CR before LF from the line endings, in case we are on Windows. */
+static void strip_cr_before_lf(struct strbuf *buffer, size_t offset)
{
size_t i, j;
for (i = j = offset; i < buffer->len; i++) {
- if (buffer->buf[i] != '\r') {
- if (i != j)
- buffer->buf[j] = buffer->buf[i];
- j++;
- }
+ if (buffer->buf[i] == '\r' &&
+ i + 1 < buffer->len && buffer->buf[i + 1] == '\n')
+ continue;
+ buffer->buf[j++] = buffer->buf[i];
}
+
strbuf_setlen(buffer, j);
}
@@ -1049,8 +1046,8 @@ static int sign_buffer_gpg(struct strbuf *buffer, struct strbuf *signature,
}
strbuf_release(&gpg_status);
- /* Strip CR from the line endings, in case we are on Windows. */
- remove_cr_after(signature, bottom);
+ /* Strip CR before LF from the line endings, in case we are on Windows. */
+ strip_cr_before_lf(signature, bottom);
return 0;
}
@@ -1136,8 +1133,8 @@ static int sign_buffer_ssh(struct strbuf *buffer, struct strbuf *signature,
ssh_signature_filename.buf);
goto out;
}
- /* Strip CR from the line endings, in case we are on Windows. */
- remove_cr_after(signature, bottom);
+ /* Strip CR before LF from the line endings, in case we are on Windows. */
+ strip_cr_before_lf(signature, bottom);
out:
if (key_file)
--
2.54.0
^ permalink raw reply related
* Re: [PATCH 3/3] connected: search promisor objects generically
From: Patrick Steinhardt @ 2026-06-24 9:33 UTC (permalink / raw)
To: Christian Couder; +Cc: git
In-Reply-To: <CAP8UFD1tqBBRiJV18xBMcDDT4Q7xCkqOLrtJGAO7o4oA=-Vr=w@mail.gmail.com>
On Tue, Jun 23, 2026 at 09:45:44AM +0200, Christian Couder wrote:
> On Mon, Jun 22, 2026 at 10:50 AM Patrick Steinhardt <ps@pks.im> wrote:
> > diff --git a/connected.c b/connected.c
> > index 7e26976832..9a666f0cdf 100644
> > --- a/connected.c
> > +++ b/connected.c
> > @@ -54,31 +66,30 @@ int check_connected(oid_iterate_fn fn, void *cb_data,
> > * object is a promisor object. Instead, just make sure we
> > * received, in a promisor packfile, the objects pointed to by
> > * each wanted ref.
> > - *
> > - * Before checking for promisor packs, be sure we have the
> > - * latest pack-files loaded into memory.
> > */
> > - odb_reprepare(the_repository->objects);
>
> Like Junio, I am not sure it's correct to remove the
> `odb_reprepare(the_repository->objects)` call.
>
> I think it was added for good reasons in b739d971 (connected.c:
> reprepare packs for corner cases, 2020-03-13) and I am not sure
> odb_for_each_object_ext() is performing something similar.
>
> At least the commit message should mention this change and explain a
> bit why the reasons the call was added are not valid anymore.
Yeah, I think you're both correct. The only explanation I have is that I
might have repeatedly misread this as `odb_prepare_alternates()`, which
is something we often call before suck loops.
> > do {
> > - struct packed_git *p;
> > -
> > - repo_for_each_pack(the_repository, p) {
> > - if (!p->pack_promisor)
> > - continue;
> > - if (find_pack_entry_one(oid, p))
> > - goto promisor_pack_found;
> > + opts.prefix = oid;
> > +
> > + err = odb_for_each_object_ext(the_repository->objects,
> > + NULL, promised_object_cb,
> > + NULL, &opts);
> > + if (err < 0)
> > + break;
> > + if (err > 0) {
> > + err = 0;
> > + continue;
> > }
> > +
> > /*
> > * Fallback to rev-list with oid and the rest of the
> > * object IDs provided by fn.
> > */
> > goto no_promisor_pack_found;
> > -promisor_pack_found:
> > - ;
> > } while ((oid = fn(cb_data)) != NULL);
> > +
> > if (opt->err_fd)
> > close(opt->err_fd);
> > - return 0;
> > + return err;
> > }
> >
> > no_promisor_pack_found:
>
> These changes are difficult to understand as there are a number of
> `goto`, `break`, `return`, etc involved.
Yeah, agreed. I had my issues understanding this logic, too.
> I think it comes in the first place from check_connected() doing too
> many things, and adding a preparatory commit to refactor it would
> help.
>
> For example the preparatory commit could move a lot of code from
> check_connected() to the following new functions:
I'll give that a try, thanks!
Patrick
^ permalink raw reply
* Re: [PATCH 3/3] connected: search promisor objects generically
From: Patrick Steinhardt @ 2026-06-24 9:33 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <xmqq4iiu1mrt.fsf@gitster.g>
On Mon, Jun 22, 2026 at 10:57:10AM -0700, Junio C Hamano wrote:
> Patrick Steinhardt <ps@pks.im> writes:
[snip]
> > - *
> > - * Before checking for promisor packs, be sure we have the
> > - * latest pack-files loaded into memory.
> > */
> > - odb_reprepare(the_repository->objects);
>
> Hmph?
Oh, I think I completely misread this as `odb_alternates_prepare()`,
which is something you typically see before loops like this. By using a
helper like `odb_for_each_object_ext()` we of course wouldn't have to
call that function anymore.
But this here is of course different, as this call would also cause us
to reload packfiles and loose objects.
> > do {
> > - struct packed_git *p;
> > -
> > - repo_for_each_pack(the_repository, p) {
> > - if (!p->pack_promisor)
> > - continue;
> > - if (find_pack_entry_one(oid, p))
> > - goto promisor_pack_found;
> > + opts.prefix = oid;
> > +
> > + err = odb_for_each_object_ext(the_repository->objects,
> > + NULL, promised_object_cb,
> > + NULL, &opts);
> > + if (err < 0)
> > + break;
> > + if (err > 0) {
> > + err = 0;
> > + continue;
> > }
>
> So we used to manually iterate and stop when we have a matching pack
> entry, but now "stop when we find" is done by promisor_object_cb
> callback that returns 1.
>
> What is the reason why we no longer odb_(re)prepare() upfront before
> going into the loop? Would it make us miss a newly added promisor
> packs? We will fall back to rev-list for correctness, so it may not
> matter, though.
So yes, this is a bug.
Thanks!
Patrick
^ permalink raw reply
* [PATCH 11/11] reftable/table: fix OOB read on truncated table
From: Patrick Steinhardt @ 2026-06-24 8:23 UTC (permalink / raw)
To: git; +Cc: oxsignal
In-Reply-To: <20260624-pks-reftable-hardening-v1-0-66e4ce87c6b9@pks.im>
When opening a table we compute the size of its data section by
subtracting the footer size from the file size. We do not verify that
the file is actually large enough to contain both the header and the
footer though. With a truncated table the subtraction can thus
underflow, causing us to read the footer out of bounds:
SUMMARY: AddressSanitizer: heap-buffer-overflow (/home/pks/Development/git/build/t/unit-tests+0x2479a4) in __asan_memcpy
Shadow bytes around the buggy address:
0x7ccff6e0de80: fa fa fa fa fa fa fa fa fd fd fd fd fd fd fd fd
0x7ccff6e0df00: fd fd fd fd fd fd fd fd fd fa fa fa fa fa fa fa
0x7ccff6e0df80: fa fa fd fd fd fd fd fd fd fd fd fd fd fd fd fd
0x7ccff6e0e000: fd fd fd fd fa fa fa fa fa fa fa fa fd fd fd fd
0x7ccff6e0e080: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fa fa
=>0x7ccff6e0e100: fa fa fa fa fa[fa]00 00 00 00 00 00 00 00 00 00
0x7ccff6e0e180: 00 00 00 00 00 00 00 04 fa fa fa fa fa fa fa fa
0x7ccff6e0e200: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x7ccff6e0e280: 00 00 fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x7ccff6e0e300: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x7ccff6e0e380: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
==1500371==ABORTING
Verify that the file is large enough to contain both the header and the
footer before computing the table size.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
reftable/table.c | 5 +++++
t/unit-tests/u-reftable-table.c | 28 ++++++++++++++++++++++++++++
2 files changed, 33 insertions(+)
diff --git a/reftable/table.c b/reftable/table.c
index f4bc86a29d..b4d3f9e211 100644
--- a/reftable/table.c
+++ b/reftable/table.c
@@ -562,6 +562,11 @@ int reftable_table_new(struct reftable_table **out,
goto done;
}
+ if (file_size < header_size(t->version) + footer_size(t->version)) {
+ err = REFTABLE_FORMAT_ERROR;
+ goto done;
+ }
+
t->size = file_size - footer_size(t->version);
t->source = *source;
t->name = reftable_strdup(name);
diff --git a/t/unit-tests/u-reftable-table.c b/t/unit-tests/u-reftable-table.c
index c7dca45e70..28b0ef5258 100644
--- a/t/unit-tests/u-reftable-table.c
+++ b/t/unit-tests/u-reftable-table.c
@@ -262,3 +262,31 @@ void test_reftable_table__seek_invalid_log_offset(void)
reftable_table_decref(table);
reftable_buf_release(&buf);
}
+
+void test_reftable_table__new_with_truncated_table(void)
+{
+ struct reftable_ref_record refs[] = {
+ {
+ .refname = (char *) "refs/heads/main",
+ .value_type = REFTABLE_REF_VAL1,
+ .value.val1 = { 42 },
+ },
+ };
+ struct reftable_block_source source = { 0 };
+ struct reftable_table *table;
+ struct reftable_buf buf = REFTABLE_BUF_INIT;
+
+ cl_reftable_write_to_buf(&buf, refs, ARRAY_SIZE(refs), NULL, 0, NULL);
+
+ /*
+ * Truncate the table so that it is large enough to read the header, but
+ * too small to also contain the footer.
+ */
+ buf.len = footer_size(1) - 1;
+ block_source_from_buf(&source, &buf);
+
+ cl_assert_equal_i(reftable_table_new(&table, &source, "name"),
+ REFTABLE_FORMAT_ERROR);
+
+ reftable_buf_release(&buf);
+}
--
2.55.0.rc1.745.g43192e7977.dirty
^ permalink raw reply related
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