This series adds an incremental mode for the connectivity check, gated
behind transfer.connectivityCheck=incremental (no expected changes unless
you opt in).

The intent is to solve the problem of the connectivity check slowing down as
the number of reachable objects from the boundary grows.

It relates to the RFC I sent out earlier:

[RFC] check_connected: toward incoming-proportional cost
https://lore.kernel.org/git/CAL71e4Nf=-zCrfN7ghEVGq11irajJhtdxYZgKe0Ycux0qs1ZvQ@mail.gmail.com/

Design
======

The verifier runs inside the same rev-list subprocess that check_connected()
already spawns, triggered by a new internal flag --verify-trees-incremental.
After get_revision() collects the incoming commits, the verifier processes
them in topological order (ancestors before descendants).

The idea is to keep a set of trusted objects, shared across the incoming
commits, that grows over time. We visit the new/untrusted commit trees and
do a comparison walk over the trees of their parents. Entries discovered on
the trusted parent side are remembered as trusted, which lets later
verification skip matching objects and avoid descending into unchanged
subtrees.

More algorithmic details are in
Documentation/technical/connectivity-check.adoc.

Benchmarks
==========

I'll just mention a short summary here, to avoid repeating what's already in
the commit message. The incremental mode is faster than the full mode when
there are few commits to verify and when the active object tree is large. In
the happy case, the work tracks the changed paths and their comparison trees
rather than the full reachable object closure, which substantially reduces
the dependence on total repository size. I've seen speedups up to around 20x
for the synthetic perf tests.

Running against a large real-world repo (3.4 GB boundary closure), the
numbers are more dramatic. All timings use rev-list directly with --not
HEADN, isolating the tree verification cost from the boundary-finding cost:

commits    full  incr.  speedup   full RSS  incr. RSS
      1    1.9s  0.01s    190x      3.4 GB     14 MB
     10    1.9s  0.04s     48x      3.4 GB    125 MB
    100    1.9s  0.37s      5x      3.4 GB    1.1 GB

The full mode takes ~1.9s regardless of commit count because it is dominated
by walking the boundary closure. Incremental scales with the number of
incoming commits and the paths they touch. Memory follows the same pattern:
incremental uses a fraction of the full mode's RSS for small pushes,
converging only when many commits are verified.

There are also regression cases in the synthetic fixtures. With long
incoming histories, the extra parent-tree scans accumulate; in the synthetic
fixture incremental is about 1.5x slower at 10000 commits. Per-commit
changes have less impact than expected: even when every directory is
touched, incremental remains competitive; bypassing the object cache for
tree reads likely helps here.

I cannot establish how common these regression cases are. In the cases I
have tested, however, the regression has remained modest; I have not been
able to provoke a substantially larger slowdown. My feeling is that this is
an acceptable tradeoff behind the opt-in config, since the target case
(small pushes to large repos) sees the largest speedup, while the regression
appears with long incoming histories.

A safety net for this regression could be to dynamically disable the
incremental mode if the number of incoming commits is too large, but this is
left out of the initial version to avoid overly speculative code.

Deepening fetches currently fall back to the full check because the full
check omits --not --all for deepening -- there is no existing-reference
boundary at which the walk can stop. An incremental approach is possible
here too -- using the old shallow roots as the trusted boundary and walking
the deepened ancestry forward -- but that is a separate change and left for
future work. Deepening is also less common than regular fetch and
receive-pack, where the speedup matters most.

Test coverage
=============

Most correctness cases in t5412-connectivity-check.sh are run in both full
and incremental modes to check semantic equivalence. Selected cases
additionally assert trace2 tree/blob counts for the incremental mode, to
verify that unchanged portions of the object graph are actually skipped. It
covers:

 * Corruption detection: missing blobs, missing trees, type mismatches,
   malformed trees (unparseable, mid-tree corruption)
 * Tree optimization: trace2 assertions confirm unchanged subtrees are
   skipped, subtree moves, merge parent boundaries
 * Root commits (no parents -- verifies full tree closure)
 * Partial clones: missing promised blobs, missing promised trees,
   verification of local commits
 * Replacement objects (with and without GIT_NO_REPLACE_OBJECTS)
 * Shallow boundaries
 * Deepening fetches (falls back to full check)
 * Integration: real push, fetch, and clone

Most tests call git rev-list directly with the appropriate flags;
integration tests exercise the full check_connected() path through push,
fetch, and clone.

Alternatives considered
=======================

My first prototype ran the verifier in-process inside connected.c. This
required a second rev-list subprocess just for boundary finding, _nofetch
variants of several object-reading functions to prevent lazy fetches in
partial clones, explicit shallow-file plumbing, and careful avoidance of
die() in all code paths reachable from the verifier. The result worked but
was fragile and touched many files.

Moving the verifier into the rev-list subprocess eliminated all of those
problems: in partial clones the existing --exclude-promisor-objects handling
already disables lazy fetching, die() is isolated by the process boundary,
shallow and replacement semantics are established before the verifier runs,
and error routing comes for free via stderr.

So while I liked the idea of being less reliant on checking within a
subprocess, making that work ended up being a lot more complex.

Next steps
==========

This series only addresses tree verification; the other significant cost is
finding the commit boundary, especially for repos with many refs. I already
have some prototypes for optimizing that too, and if this ends up landing,
that would be something I would start polishing up.

Thanks, Kristofer

Kristofer Karlsson (2):
  Documentation: describe connectivity checking
  connected: add incremental connectivity check via rev-list

 Documentation/config/transfer.adoc            |  20 +
 Documentation/rev-list-options.adoc           |   6 +
 .../technical/connectivity-check.adoc         | 243 +++++++
 Makefile                                      |   1 +
 builtin/rev-list.c                            |  18 +
 connected.c                                   |  24 +
 meson.build                                   |   1 +
 t/meson.build                                 |   1 +
 ...enerate-repo-p5412-connectivity-check.perl |  44 ++
 t/perf/p5412-connectivity-check.sh            |  92 +++
 t/t5412-connectivity-check.sh                 | 655 ++++++++++++++++++
 tree-verify.c                                 | 306 ++++++++
 tree-verify.h                                 |  15 +
 13 files changed, 1426 insertions(+)
 create mode 100644 Documentation/technical/connectivity-check.adoc
 create mode 100644 t/perf/generate-repo-p5412-connectivity-check.perl
 create mode 100755 t/perf/p5412-connectivity-check.sh
 create mode 100755 t/t5412-connectivity-check.sh
 create mode 100644 tree-verify.c
 create mode 100644 tree-verify.h

base-commit: 47ce80527c56f462cb97db4ca8125342204d3783

Submitted-As: https://lore.kernel.org/git/pull.2211.git.1789379276.gitgitgadget@gmail.com