Skip to content

Commit 22b2310

Browse files
gitstergitster
committed
Merge branch 'kk/connectivity-check-incremental'
The connectivity check in 'git fetch' and 'git receive-pack' has been optimized with an alternative incremental mode, available via 'transfer.connectivityCheck=incremental'. Instead of walking the full object closure of the boundary commits, it compares the trees of incoming commits against their trusted parent trees, skipping unchanged subtrees. * kk/connectivity-check-incremental: connected: add "auto" connectivity check mode connected: add incremental connectivity check via rev-list connected: add transfer.connectivityCheck config connected: drop dependency on `the_repository` p5413: add perf tests for connectivity check Documentation: describe connectivity checking
2 parents cc3b09a + 656be59 commit 22b2310

22 files changed

Lines changed: 1842 additions & 21 deletions

‎Documentation/Makefile‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -122,6 +122,7 @@ TECH_DOCS += technical/bitmap-format
122122
TECH_DOCS += technical/build-systems
123123
TECH_DOCS += technical/bundle-uri
124124
TECH_DOCS += technical/commit-graph
125+
TECH_DOCS += technical/connectivity-check
125126
TECH_DOCS += technical/directory-rename-detection
126127
TECH_DOCS += technical/hash-function-transition
127128
TECH_DOCS += technical/large-object-promisors

‎Documentation/config/transfer.adoc‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,33 @@
1+
transfer.connectivityCheck::
2+
Choose which algorithm to use for the connectivity check
3+
performed during object transfer operations such as
4+
linkgit:git-fetch[1] and linkgit:git-receive-pack[1].
5+
The connectivity check verifies that all objects reachable
6+
from the incoming tips are available locally or, in a partial
7+
clone, promised by a promisor remote.
8+
The variants are as follows:
9+
+
10+
--
11+
`full` (default);;
12+
Walk the full object closure of the boundary commits.
13+
`incremental`;;
14+
Verify incoming commits by diffing their trees against parent
15+
trees, recursively descending only into entries that differ.
16+
The largest benefits occur when incoming commits change a
17+
small fraction of a large tree closure, and it can be slower
18+
than `full` when there are many incoming commits.
19+
Falls back to `full` for clones, pushes into an empty
20+
repository and deepening fetches.
21+
`auto`;;
22+
`auto=<cutoff>`;;
23+
Choose between `full` and `incremental` with a heuristic.
24+
Currently `incremental` is used when there are at most
25+
_<cutoff>_ incoming commits (1000 by default), and `full`
26+
otherwise. The heuristic may change in future versions.
27+
--
28+
+
29+
Unknown values are treated as `full`, with a warning.
30+
131
transfer.credentialsInUrl::
232
A configured URL can contain plaintext credentials in the form
333
`<protocol>://<user>:<password>@<domain>/<path>`. You may want

‎Documentation/rev-list-options.adoc‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1102,6 +1102,11 @@ It is an error to use `--missing-only` without `--missing=print` or
11021102
stronger than `--missing=allow-promisor` because it limits the
11031103
traversal, rather than just silencing errors about missing
11041104
objects.
1105+
1106+
`--connectivity-check=(full|incremental|auto[=<cutoff>])`::
1107+
(For internal use only.) Used by `check_connected()` to
1108+
select the connectivity check algorithm; see
1109+
`transfer.connectivityCheck` in linkgit:git-config[1].
11051110
endif::git-rev-list[]
11061111

11071112
`--no-walk[=(sorted|unsorted)]`::

‎Documentation/technical/connectivity-check.adoc‎

Lines changed: 259 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,259 @@
1+
Connectivity checking
2+
=====================
3+
4+
After receiving new objects via fetch, push (receive-pack), clone,
5+
or bundle, Git verifies that the new reference tips do not leave
6+
the repository in a state where reachable objects are missing.
7+
This verification is called the connectivity check.
8+
9+
Connectivity invariant
10+
----------------------
11+
12+
A repository is connected when every object reachable from its
13+
references is available locally (with exceptions noted below).
14+
The reverse does not hold: objects that exist in the object
15+
database but are not reachable from any reference may be
16+
incomplete or lack a connected closure.
17+
18+
The connectivity check maintains this invariant when references
19+
are updated. It trusts that all objects reachable from existing
20+
reference tips are already fully connected and verifies that the
21+
new reference tips do not introduce references to unavailable
22+
objects. Verification is permitted to stop when it reaches
23+
objects already reachable from existing references, since their
24+
closure is already connected. These trusted references include
25+
local references and references from alternate object stores.
26+
27+
Without this check, a truncated or corrupted transfer could leave
28+
a repository in a state where later history walks encounter
29+
missing objects.
30+
31+
Exceptions
32+
~~~~~~~~~~
33+
34+
Gitlink entries (submodule references) are excluded from
35+
connectivity checking. Their target objects belong to a separate
36+
repository.
37+
38+
In partial clones, objects promised by a promisor remote are
39+
accepted as connected without requiring local existence. The
40+
check excludes promisor objects from traversal so that it does
41+
not trigger on-demand fetches for them.
42+
43+
Full connectivity check
44+
-----------------------
45+
46+
The full connectivity check runs a `rev-list` subprocess, feeding
47+
the new reference tips via stdin. A normal invocation is roughly:
48+
49+
git rev-list --objects --stdin --not --all --quiet
50+
--alternate-refs [--exclude-promisor-objects]
51+
52+
In a partial clone, objects received from a promisor remote do
53+
not need to be checked: anything they reference is promised by
54+
that remote and can be fetched on demand. So if every new tip is
55+
found in a promisor packfile, `rev-list` is not run at all.
56+
Otherwise it runs with `--exclude-promisor-objects`, so that the
57+
traversal stops at promisor objects instead of fetching them.
58+
59+
Consider the following graph after a fetch, where all reference
60+
tips point directly to commits. For simplicity, only local
61+
references appear on the already-connected side; alternate refs
62+
play the same role. N3 is a merge commit:
63+
64+
/-------------L2
65+
/
66+
C1---B1---C2---B2-----L1
67+
\ \
68+
N1 N3---T2
69+
\ /
70+
N2-----------T1
71+
72+
L1, L2: local refs
73+
T1, T2: incoming tips (new refs)
74+
N1, N2, N3: incoming commits (N3 is a merge)
75+
B1, B2: boundary commits (already connected)
76+
C1, C2: already connected (but not boundary)
77+
78+
The incoming set is the commits reachable from the incoming
79+
tips but not from the already-connected side. Boundary commits
80+
are the already-connected commits at the edge of that set. Here
81+
B1 is an ancestor of B2, which happens when incoming branches
82+
fork at different depths in the existing history.
83+
84+
The `--not --all` arguments establish the trust boundary: the
85+
incoming set is the commits reachable from the new tips but not
86+
from any existing reference.
87+
88+
The traversal then walks the trees of the boundary commits and
89+
marks those objects uninteresting. Trees of incoming commits
90+
are then walked, stopping at objects already marked as
91+
uninteresting. The cost of marking boundary trees uninteresting
92+
dominates when the boundary commits have large trees, even when
93+
the incoming changes are small.
94+
95+
Deepening fetches
96+
~~~~~~~~~~~~~~~~~
97+
98+
For deepening fetches (where the shallow boundary moves), the
99+
full check omits `--not --all`. There is no existing-reference
100+
boundary at which the walk can stop. Instead, traversal follows
101+
the effective shallow boundary supplied for the deepened
102+
repository. The new content may be below the old shallow
103+
boundary even when the tips themselves have not changed.
104+
105+
Non-commit tips
106+
~~~~~~~~~~~~~~~
107+
108+
When a new reference points to a non-commit object, such as a
109+
tag, tree, or blob, that object is not part of the commit walk.
110+
These non-commit tips are verified during the tree and blob
111+
traversal that follows the commit walk within the same rev-list
112+
invocation.
113+
114+
Incremental connectivity check
115+
------------------------------
116+
117+
The incremental mode, selected by
118+
`transfer.connectivityCheck=incremental`, avoids traversing the
119+
full tree walk of the boundary commits. Instead, it verifies
120+
each incoming commit's tree against the already-trusted trees of
121+
its parent commits.
122+
123+
The same `--not --all` boundary as the full check identifies the
124+
incoming commits. The incremental mode reuses this boundary but
125+
replaces what happens afterwards: rather than walking boundary
126+
trees to mark objects uninteresting, it compares each incoming
127+
commit's tree against its parents' trees, processing commits in
128+
topological order (ancestors first). This all happens inside
129+
the same `rev-list` invocation, and the promisor fast path above
130+
still runs first.
131+
132+
Trust model
133+
~~~~~~~~~~~
134+
135+
A tree is trusted when its transitive object closure is known to
136+
be connected.
137+
138+
Every parent of an incoming commit is either on the
139+
already-connected side of the `--not --all` boundary (a boundary
140+
parent whose tree is trusted by definition) or is an earlier
141+
incoming commit that was already verified due to the topological
142+
processing order. In both cases the parent's tree is trusted, so
143+
all parent trees can be unconditionally used as comparison bases.
144+
145+
Once an incoming commit's tree has been verified, it is trusted
146+
and can serve as a comparison base for later descendants. This
147+
gives an inductive correctness argument: the base case is the
148+
trust boundary established by `--not --all`, and the inductive
149+
step is that verifying a commit extends the trusted set.
150+
151+
Tree states
152+
~~~~~~~~~~~
153+
154+
The verifier tracks tree OIDs in three states:
155+
156+
untrusted::
157+
The tree has not yet been established as connected. This
158+
is the implicit state of an OID not present in the state
159+
map.
160+
161+
trusted::
162+
The tree is known to have a connected transitive closure,
163+
but its direct entries have not yet been published into the
164+
verifier's trusted object sets.
165+
166+
expanded::
167+
The tree is trusted and its direct non-gitlink entries
168+
have also been published into the trusted object sets.
169+
170+
State transitions are monotonic: a tree may move from untrusted
171+
to trusted to expanded, but never backwards. An untrusted tree
172+
that is successfully verified goes directly to expanded.
173+
174+
Blobs require only trusted/untrusted state: a blob becomes
175+
trusted when it is found in a trusted tree or when its existence
176+
and type have been verified directly.
177+
178+
The trusted/expanded distinction is an optimization. An expanded
179+
parent does not need to be reread merely to publish entries that
180+
are already trusted, though it may still be read when same-path
181+
subtree bases are needed for recursive comparison.
182+
183+
Algorithm
184+
~~~~~~~~~
185+
186+
At a high level:
187+
188+
verify(commits):
189+
sort topologically (ancestors first)
190+
for each commit:
191+
mark parent root trees as trusted
192+
verify_tree(commit.tree, parent root trees)
193+
194+
verify_tree(tree, base_trees):
195+
if tree already trusted: return
196+
read tree, collect entries not already trusted
197+
for each available base tree:
198+
publish its entries as trusted
199+
record same-path subtrees as bases
200+
for each collected entry:
201+
if now trusted: skip
202+
if blob: verify blob connectivity and type
203+
if tree: verify_tree(entry, its recorded bases)
204+
mark tree as expanded
205+
206+
The important ordering within `verify_tree` is that entries from
207+
the new tree are collected before the base trees are scanned, but
208+
are processed only afterwards. Trust learned from any base can
209+
therefore eliminate work before recursive verification begins.
210+
211+
Same-path parent subtrees are passed down as comparison bases
212+
during recursive descent. If no comparison base is available,
213+
the new subtree is verified from scratch.
214+
215+
Example
216+
~~~~~~~
217+
218+
Consider a commit that changes one file under `lib/` and moves an
219+
unchanged subtree from `src/` to `dev/`:
220+
221+
Parent tree New tree
222+
+-- src/ (aaa) +-- dev/ (aaa)
223+
+-- lib/ (bbb) +-- lib/ (ccc)
224+
+-- foo.c (ddd) +-- foo.c (ddd)
225+
+-- bar.c (eee) +-- bar.c (fff)
226+
227+
Scanning the parent makes `aaa` trusted even though it moved from
228+
`src/` to `dev/`, so that subtree is skipped. The changed `ccc`
229+
subtree is compared against its same-path parent `bbb`; scanning
230+
`bbb` makes `ddd` and `eee` trusted, leaving only the new `fff`
231+
blob to be checked.
232+
233+
This illustrates two properties:
234+
235+
* Trust is OID-based rather than path-based. An unchanged subtree
236+
is recognized after a move.
237+
238+
* Same-path parent subtrees provide recursive comparison bases.
239+
These bases improve pruning efficiency but are not required for
240+
correctness; a new subtree can always be verified from scratch.
241+
242+
Multiple parents
243+
~~~~~~~~~~~~~~~~
244+
245+
For a merge commit, root trees from all parents are comparison
246+
bases. When several parents contain a same-path subtree, each
247+
matching subtree is collected as a recursive comparison base.
248+
249+
Entries published from any trusted parent become globally trusted,
250+
so a matching tree or blob entry present in any parent can be
251+
skipped while verifying the merge tree.
252+
253+
Missing comparison bases
254+
~~~~~~~~~~~~~~~~~~~~~~~~
255+
256+
A promised base tree may not be locally available for comparison.
257+
In that case the verifier skips that base and verifies the new
258+
subtree without it. The missing comparison can reduce pruning but
259+
does not affect correctness.

‎Documentation/technical/meson.build‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,7 @@ articles = [
1111
'build-systems.adoc',
1212
'bundle-uri.adoc',
1313
'commit-graph.adoc',
14+
'connectivity-check.adoc',
1415
'directory-rename-detection.adoc',
1516
'hash-function-transition.adoc',
1617
'large-object-promisors.adoc',

‎Makefile‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1339,6 +1339,7 @@ LIB_OBJS += trailer.o
13391339
LIB_OBJS += transport-helper.o
13401340
LIB_OBJS += transport.o
13411341
LIB_OBJS += tree-diff.o
1342+
LIB_OBJS += tree-verify.o
13421343
LIB_OBJS += tree-walk.o
13431344
LIB_OBJS += tree.o
13441345
LIB_OBJS += unpack-trees.o

‎builtin/clone.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -572,7 +572,7 @@ static void update_remote_refs(const struct ref *refs,
572572
opt.transport = transport;
573573
opt.progress = transport->progress;
574574

575-
if (check_connected(iterate_ref_map, &rm, &opt))
575+
if (check_connected(the_repository, iterate_ref_map, &rm, &opt))
576576
die(_("remote did not send all necessary objects"));
577577
}
578578

‎builtin/fetch.c‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1259,7 +1259,8 @@ static int store_updated_refs(struct display_state *display_state,
12591259

12601260
opt.exclude_hidden_refs_section = "fetch";
12611261
rm = ref_map;
1262-
if (check_connected(iterate_ref_map, &rm, &opt)) {
1262+
if (check_connected(the_repository, iterate_ref_map,
1263+
&rm, &opt)) {
12631264
rc = error(_("%s did not send all necessary objects"),
12641265
display_state->url);
12651266
goto abort;
@@ -1431,7 +1432,7 @@ static int check_exist_and_connected(struct ref *ref_map)
14311432

14321433
opt.quiet = 1;
14331434
opt.exclude_hidden_refs_section = "fetch";
1434-
return check_connected(iterate_ref_map, &rm, &opt);
1435+
return check_connected(the_repository, iterate_ref_map, &rm, &opt);
14351436
}
14361437

14371438
static int fetch_and_consume_refs(struct display_state *display_state,

‎builtin/receive-pack.c‎

Lines changed: 8 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1385,7 +1385,8 @@ static int update_shallow_ref(struct command *cmd, struct shallow_info *si)
13851385
oid_array_append(&extra, &si->shallow->oid[i]);
13861386

13871387
setup_alternate_shallow(&shallow_lock, &opt.shallow_file, &extra);
1388-
if (check_connected(command_singleton_iterator, cmd, &opt)) {
1388+
if (check_connected(the_repository, command_singleton_iterator,
1389+
cmd, &opt)) {
13891390
rollback_shallow_file(the_repository, &shallow_lock);
13901391
oid_array_clear(&extra);
13911392
return -1;
@@ -1827,8 +1828,9 @@ static void set_connectivity_errors(struct command *commands,
18271828
odb_transaction_env(transaction, &env);
18281829
opt.env = env.v;
18291830

1830-
if (!check_connected(command_singleton_iterator, &singleton,
1831-
&opt))
1831+
if (!check_connected(the_repository,
1832+
command_singleton_iterator,
1833+
&singleton, &opt))
18321834
continue;
18331835

18341836
cmd->error_string = "missing necessary objects";
@@ -2090,7 +2092,9 @@ static void execute_commands(struct command *commands,
20902092
opt.env = env.v;
20912093
opt.exclude_hidden_refs_section = "receive";
20922094

2093-
if (check_connected(iterate_receive_command_list, &data, &opt))
2095+
if (check_connected(the_repository,
2096+
iterate_receive_command_list,
2097+
&data, &opt))
20942098
set_connectivity_errors(commands, si, transaction);
20952099

20962100
if (use_sideband)

0 commit comments

Comments
 (0)