This series adds an incremental mode for the connectivity check, gated
behind transfer.connectivityCheck=incremental or "auto" (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 option --connectivity-check=.
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 messages (5/6 and 6/6). 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 of up to about 18x in the synthetic perf tests.

Running against a large real-world repo (3.4 GB boundary closure), the
numbers are more dramatic. These were measured on v1 and not re-run since;
the real-repo numbers for v4 are in 6/6. 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.

In the cases I have tested the regression has remained modest, and it shows
up with long incoming histories, while the target case (small pushes to
large repositories) sees the largest speedup. That is what the "auto" mode
is for: it uses the incremental check for small numbers of incoming commits
and the full check otherwise, with a cutoff that can be configured.

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 t5413-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. The
tests cover:

 * Corruption detection: missing blobs, missing trees, type mismatches,
   malformed trees (unparseable, mid-tree corruption), and corrupt blobs
   (incremental only, since the full check does not read blobs)
 * 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, missing
   promised parent commits, verification of local commits
 * Replacement objects (with and without GIT_NO_REPLACE_OBJECTS)
 * Shallow boundaries
 * Deepening fetches (falls back to full check)
 * Algorithm selection: clones and pushes into an empty repository use the
   full check, "auto" and its cutoff, and unknown config values
 * Tree depth: the incremental check honors core.maxTreeDepth (t6700)
 * 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, a die() in existing helpers only ends the
subprocess, 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 doing the check in-process, 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.

Changes since v4
================

 * The series no longer touches repo->fetch_if_missing, which Junio pointed
   out was a trap when cleared only for some modes. The incremental verifier
   instead reads blobs and trees with odb_read_object_info_extended() and
   OBJECT_INFO_SKIP_FETCH_OBJECT, so it never lazily fetches on its own;
   commit parsing already never fetches. The BUG() guard on the flag is
   gone, and parse_connectivity_check() no longer takes a repository. The
   full check is unchanged: in a partial clone check_connected() passes
   --exclude-promisor-objects as before.
 * A tree that cannot be read because it is corrupt is now reported as an
   error, like a corrupt blob, instead of dying.

Changes since v3
================

 * Split, along the lines Patrick suggested, into three steps: the config
   option and the internal --connectivity-check= rev-list option with only
   "full" (4/6), the incremental check (5/6), and the "auto" mode (6/6),
   since choosing between the two is subtle enough to review on its own.

 * The internal rev-list option --verify-trees-incremental is replaced by
   --connectivity-check=, which check_connected() now always passes.
   rev-list dies on an unknown mode, since only check_connected() passes it.

 * An unknown transfer.connectivityCheck value now falls back to full with a
   warning instead of dying, so config written for a newer Git does not
   break fetches.

 * "auto" takes an optional cutoff, "auto=", as Patrick suggested,
   defaulting to 1000.

 * Clones and pushes into an empty repository use the full check even with
   incremental or auto, since there is no boundary to compare against (see
   5/6). check_connected() now decides the deepening fallback before reading
   the config.

 * New patch 3/6 drops the dependency on the_repository in connected.c, as
   Junio suggested. The repository is passed to check_connected() as a
   parameter rather than in check_connected_options, like other functions
   that take a repository.

 * Use parse_commit_gently() instead of dying on a parent that cannot be
   parsed, which Patrick pointed out could happen in a partial clone with
   missing commits. As in the revision walk, a missing parent that is
   promised is skipped; added a test for that. More generally, the verifier
   adds no new die() calls: it returns errors, and rev-list dies once when
   the check fails.

 * An object that cannot be read is now reported as "missing" only when it
   does not exist, and as "unable to read" otherwise, e.g. for a corrupt
   blob.

 * Renamed variables to parent_trees / trusted_bases to make the trust
   direction clearer.

 * size_t for counts and sizes.

 * verify_tree() still recurses, bounded by core.maxTreeDepth like the other
   tree walkers. Its frame was made smaller by moving the tree descriptor
   scratch space into the shared state: with gcc -O2 its frame is 272 bytes,
   against 240 for process_tree(), so at the default depth of 2048 it needs
   about the same stack as "rev-list --objects". The listing of untrusted
   entries and the scan of the base trees are split out into helpers,
   without changing the logic. New t6700 tests check that the incremental
   check (given a boundary, so that it is not replaced by the full check)
   honors core.maxTreeDepth and fails gracefully at the default limit.

   I tried a work queue as suggested, but it got messy, and it would be
   stricter than the code we already rely on: the full check's
   process_tree() recurses over trees in the same way, and be20128bfa (add
   core.maxTreeDepth) settled on bounding tree recursion rather than
   removing it. If we want an iterative walk, I think it belongs in a
   separate series that also covers process_tree().

 * Also addressed from v3 review: the technical doc is listed in the
   Makefile and in meson.build, the perf tests require PERL, the leftover
   p5412 is now p5413, "verified against these marks" is reworded, int flags
   are bool, the tree state map's byte-sized values are explained in a
   comment, and the parent tree expansion in tree-verify.c has comments
   explaining it.

 * Documentation: reworded the technical doc, including a shorter
   description of the promisor fast path; transfer.connectivityCheck
   documents the fallbacks to full; and the rev-list option description is
   trimmed to an internal-use note.

 * The --connectivity-check parsing in rev-list moved into a small helper,
   with the mode and cutoff in a struct local to cmd_rev_list() instead of
   globals.

 * Tests are faster and simpler: the auto cutoff is tested with "auto="
   instead of building long histories, and the mode selection tests share
   two small helpers.

 * p5413 passes the mode explicitly, and the tables in 5/6 were re-measured;
   they now report the best of 3 runs, which is what the perf framework
   reports, rather than "median of 3".

Changes since v2
================

Addresses Patrick's review (thanks!).

 * Split from 2 commits to 4: documentation, perf test baseline, config
   plumbing + rev-list flag, then the incremental implementation.
 * Documentation rewrites: added unreachable-objects caveat, removed code
   references to reduce staleness risk, replaced three-phase list with
   cost-focused prose, rewrote trust model to explicitly describe boundary
   mechanism and inductive argument, and several smaller clarifications.
 * Extracted tree_oid variable in verify_commit_tree() to avoid calling
   get_commit_tree_oid(commit) twice.
 * Rebased onto latest master to resolve a meson.build conflict (t5412 was
   taken by another topic). Renumbered test and perf files to t5413/p5413.

Changes since v1
================

 * Guard against get_commit_tree_oid() returning NULL in
   verify_commit_tree(), dying with a clear message instead of a NULL
   dereference. (Thanks Junio for catching this)
 * Set fetch_if_missing = 0 in the rev-list early option parse when
   --verify-trees-incremental is seen, and add a BUG() assertion in
   verify_commits_incremental() to catch any future caller that forgets.
   This makes the lazy-fetch protection explicit rather than relying solely
   on --exclude-promisor-objects having set it earlier. (Thanks again to
   Junio)
 * Add a test that verifies promised blobs are not lazy-fetched during the
   incremental check.
 * Reuse the existing 3-argument type-mismatch format string to avoid adding
   new strings for localization.

Thanks, Kristofer

cc: Kristofer Karlsson krka@spotify.com cc: Patrick Steinhardt ps@pks.im

Kristofer Karlsson (6):
  Documentation: describe connectivity checking
  p5413: add perf tests for connectivity check
  connected: drop dependency on `the_repository`
  connected: add transfer.connectivityCheck config
  connected: add incremental connectivity check via rev-list
  connected: add "auto" connectivity check mode

 Documentation/Makefile                        |   1 +
 Documentation/config/transfer.adoc            |  30 +
 Documentation/rev-list-options.adoc           |   5 +
 .../technical/connectivity-check.adoc         | 259 ++++++
 Documentation/technical/meson.build           |   1 +
 Makefile                                      |   1 +
 builtin/clone.c                               |   2 +-
 builtin/fetch.c                               |   5 +-
 builtin/receive-pack.c                        |  12 +-
 builtin/rev-list.c                            |  73 ++
 bundle.c                                      |   2 +-
 connected.c                                   |  67 +-
 connected.h                                   |   4 +-
 fetch-pack.c                                  |   3 +-
 meson.build                                   |   1 +
 t/meson.build                                 |   1 +
 ...enerate-repo-p5413-connectivity-check.perl |  44 +
 t/perf/p5413-connectivity-check.sh            |  92 ++
 t/t5413-connectivity-check.sh                 | 795 ++++++++++++++++++
 t/t6700-tree-depth.sh                         |  17 +
 tree-verify.c                                 | 433 ++++++++++
 tree-verify.h                                 |  15 +
 22 files changed, 1842 insertions(+), 21 deletions(-)
 create mode 100644 Documentation/technical/connectivity-check.adoc
 create mode 100644 t/perf/generate-repo-p5413-connectivity-check.perl
 create mode 100755 t/perf/p5413-connectivity-check.sh
 create mode 100755 t/t5413-connectivity-check.sh
 create mode 100644 tree-verify.c
 create mode 100644 tree-verify.h

base-commit: 6de20f6092dcf9bdb1c8efe03db4b70c82b423dd

Submitted-As: https://lore.kernel.org/git/pull.2211.v5.git.1792761119.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2211.git.1789379276.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2211.v2.git.1790600552.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2211.v3.git.1791806877.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2211.v4.git.1792581744.gitgitgadget@gmail.com