The post-fetch connectivity check in 'git fetch' has been corrected
to avoid passing alternate refs as positive revisions during a
deepening fetch, plugging a severe performance bug.
* iw/connected-deepen-fetch-no-alternate-refs:
odb: ignore refs of shallow and grafted alternates
connected: negate alternate refs in deepening fetches too
The incremental connectivity check pays a per-commit cost. For
every incoming commit it reads the new trees along the changed
paths, and the trees at the same paths in its parents to compare
against. A parent tree is often read again even though an earlier
commit already read it: on git.git, about a third of the tree reads
for 2000 incoming commits are such re-reads. The full check
instead pays a mostly fixed cost for walking the boundary trees,
so with many incoming commits the incremental check becomes the
slower one (see the previous commit). Users who mostly
receive small pushes but occasionally a large one should not have
to choose between the two.
Add an "auto" value for transfer.connectivityCheck that picks the
mode based on the incoming history. When the revision walk is
limited, which is the case whenever the receiving repository has
references, the incoming commit list is already computed by
limit_list(), so counting it is cheap. "auto" then uses the
incremental check for up to 1000 incoming commits, and the full
check above that.
The cutoff is a fixed constant based on the p5413 fixture in the
previous commit, where breakeven is between 500 and 3000 commits.
It is conservative for repositories with large trees, where the
fixed cost of the full check is higher. Measured on real
repositories (rev-list against a single boundary commit, mean
of at least 10 runs):
repository files commits full incr. full/incr
internal A 556K 1000 1.71s 0.61s 2.8x
internal A 556K 4000 2.78s 2.83s 1.0x
internal B 288K 1000 1.78s 0.88s 2.0x
linux 95K 598 0.33s 0.12s 2.7x
linux 95K 1728 0.56s 0.35s 1.6x
git 4.9K 984 0.22s 0.27s 0.8x
With small trees incremental can be slower within the cutoff,
but both modes are fast enough there (0.22s vs 0.27s for git
above) that the difference does not matter in practice.
No single cutoff is optimal for every repository, so it can be set
with "auto=<cutoff>"; plain "auto" uses 1000. A malformed cutoff
is treated like any other unknown value: it falls back to "full"
with a warning.
Suggested-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
The full connectivity check uses rev-list to find commits
reachable from the incoming tips but not from the
already-connected side, then walks their object closure. Commit
traversal stops at the connectivity boundary, but trees and blobs
reachable from that boundary still need to be walked so they can
be marked uninteresting, allocating a struct object for each one.
On repositories where the boundary commits have large trees, the
connectivity check for small incoming changes visits and tracks
more objects than needed.
Add an alternative connectivity check that verifies incoming
commits incrementally against their parents.
The verifier processes incoming commits with ancestors first and
compares each new tree against its trusted parent trees. Entries
already seen on the trusted side are skipped by OID, so unchanged
subtrees need not remain at the same path to be recognized.
Changed subtrees are recursively compared against same-path parent
subtrees, and new subtrees without a comparison base are verified
from scratch.
See Documentation/technical/connectivity-check.adoc for the trust
invariants and detailed algorithm.
The incremental check runs inside rev-list, selected by the
internal --connectivity-check option. After the normal
revision walk identifies the incoming commits, the verifier
consumes them before the usual object traversal; any pending
non-commit tips are still handled by the existing traversal.
Partial-clone semantics are preserved: objects promised by a
promisor remote are accepted as connected, and on-demand fetching
is prevented by excluding promisor objects from traversal.
A new transfer.connectivityCheck value "incremental" selects the
new mode, with "full" remaining the default. Deepening fetches
fall back to the full check because they do not have the normal
existing-reference boundary, and traversal instead follows the
effective shallow boundary.
Clones and pushes into an empty repository also use the full
check. Without negative revisions there is no trusted boundary,
and the incremental check would have to verify all of history
from scratch like the full check does, with extra per-commit
overhead on top. On git.git, checking 70K commits without a
boundary takes 5.3s with the full check and 9.2s with the
incremental one.
p5413 results (best of 3), scaling one dimension at a time.
Each fixture is a repository with a flat tree of many
directories containing 100 files each. The incoming set is a
chain of commits on top of the existing history, with each
commit changing files in different directories round-robin.
The three axes vary the total repository tree size, the number
of incoming commits, and the number of files changed per
incoming commit.
Scaling tree size (10 incoming commits, 10 files/commit):
files full incr. full/incr
5K 0.01s 0.01s 1.0x
50K 0.04s 0.01s 4.0x
200K 0.13s 0.01s 13.0x
800K 0.54s 0.03s 18.0x
The full mode must walk the trees of boundary commits, which
grows with overall tree size. Incremental still scans the
root trees, but avoids descending into unchanged subtrees,
so it grows much more slowly with repository size.
Scaling incoming commit count (200K files, 10 files/commit):
commits full incr. full/incr
1 0.13s 0.01s 13.0x
10 0.13s 0.01s 13.0x
100 0.16s 0.06s 2.7x
500 0.29s 0.25s 1.2x
3000 1.14s 1.44s 0.8x
5000 1.87s 2.39s 0.8x
10000 3.45s 5.13s 0.7x
With many commits the per-commit overhead of scanning both
the new and parent root trees accumulates and incremental
becomes slower. Breakeven is between 500 and 3000 commits
and the ratio stabilizes near 0.7x for this fixture.
Scaling files per incoming commit (200K files, 10 commits):
files/commit full incr. full/incr
1 0.13s 0.01s 13.0x
10 0.13s 0.01s 13.0x
100 0.15s 0.03s 5.0x
500 0.23s 0.13s 1.8x
1000 0.34s 0.27s 1.3x
2000 0.65s 0.56s 1.2x
The advantage shrinks as more files change per commit, but
incremental stays slightly faster even at 2000 files/commit,
where every directory is touched.
Selected peak RSS measurements from the same fixtures:
case full incr. ratio
200K files, 10 commits 31 MB 12 MB 0.4x
800K files, 10 commits 110 MB 26 MB 0.2x
200K files, 5000 commits 155 MB 151 MB 1.0x
Incremental uses less memory when it can prune enough of the
boundary tree walk. In the long-history case the two modes
visit similar object sets and memory converges.
The regression cases in the CPU benchmarks are in wall-clock
time rather than memory, primarily from scanning some trees
more than once: a commit's tree is read as a candidate when the
commit is verified, and again as a trusted parent tree when its
children are verified.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Add the transfer.connectivityCheck configuration option to choose
the algorithm used for the connectivity check. For now the only
accepted value is "full", which is the existing behavior and the
default. Unknown values fall back to "full" with a warning, so
that configuration written for a newer version of Git does not
break fetches and pushes; "full" is always a correct check.
check_connected() now always tells its rev-list subprocess which
algorithm to use with an internal --connectivity-check=<mode>
option, which so far only accepts "full". Passing the mode
explicitly means rev-list knows it is running a connectivity
check, so later optimizations can be limited to that case.
This prepares for an incremental check added in the next commit.
Suggested-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
The next commits will need to use the repository to read configuration
in check_connected(). Rather than accessing `the_repository`, refactor
the code to instead require the caller to pass in a repository so that
we can remove `USE_THE_REPOSITORY_VARIABLE`.
Suggested-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
The connectivity check spawned by check_connected() uses
git rev-list --objects --stdin --not --all --quiet --alternate-refs
where 39b44ba771 (check_everything_connected: assume alternate ref
tips are valid, 2019-07-01) added "--alternate-refs" so that the walk
from the fetched tips stops at the refs of any alternate object store,
on the assumption that the alternate is already fully connected.
That only works because "--alternate-refs" comes after "--not".
cf1e7c0770 (fetch-pack: write shallow, then check connectivity,
2018-07-02) drops "--not --all" for deepening fetches, since those
need to verify the whole chain up to the new shallow boundary rather
than stopping at refs we already had. For such fetches we therefore
run
git --shallow-file ... rev-list --objects --stdin --quiet --alternate-refs
with the alternate's refs as positive revisions, and rev-list
enumerates every object reachable from them. Unless one of those refs
happens to lie inside the newly fetched shallow range, where the
grafts cut the walk short, that is the alternate's entire history.
This is slow for setups that attach a large alternate to a fresh
repository and then do a shallow fetch of a ref that is a few commits
ahead of the alternate, which is how CI runners share a clone of a
big repository between jobs. With a 7M-object alternate (a bare clone
of gitlab-org/gitlab), "git fetch --depth 1" transfers an empty pack
in under a second and the connectivity check then takes 227s. With
the alternate's refs negated the same rev-list finishes in 0.0s.
Pass "--not" in both cases, before the branch that adds "--all" for
non-deepening fetches, so that "--alternate-refs" is negated for
deepening fetches as well. Such a fetch still has to reach the new
shallow boundary from the fetched tips without stopping at our own
refs, which is what cf1e7c0770 wanted. It stops at the alternate's
refs, as every other fetch already does. Move "--alternate-refs" up
next to "--all" so that the arguments that bound the walk are in one
place.
Add tests to t5618 that check the arguments of the rev-list child via
GIT_TRACE2_EVENT for a regular and for a deepening fetch. The result
of the check is the same either way for a complete alternate, so
there is no behavioural difference to assert on. The difference is
only in which objects are walked.
Helped-by: Patrick Steinhardt <ps@pks.im>
Helped-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Igor Wiedler <iwiedler@gitlab.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
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.
Add a test to verify that we indeed use the optimization.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
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>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
connected.h documents that err_fd is closed before check_connected()
returns. It is, on three of four exit paths. The promisor-pack fast
path added in 50033772d (connected: verify promisor-ness of partial
clone, 2020-01-30) returns 0 without closing it.
receive-pack uses err_fd as the write end of an async sideband
muxer's pipe, and the muxer thread waits for EOF. The same omission
has caused deadlocks there twice before: 49ecfa13f (receive-pack:
close sideband fd on early pack errors, 2013-04-19) and 6cdad1f13
(receive-pack: fix deadlock when we cannot create tmpdir,
2017-03-07).
Signed-off-by: Ethan Dickson <ethanndickson@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Since c6807a40dc (clone: open a shortcut for connectivity check,
2013-05-26), we may open a one-off packed_git struct to check what's in
the pack we just received. At the end of the function we throw away the
struct (rather than linking it into the repository struct as usual).
We used to leak the struct until dd4143e7bf (connected.c: free the
"struct packed_git", 2022-11-08), which calls free(). But that's not
sufficient; inside the struct we'll have mmap'd the pack idx data from
disk, which needs an munmap() call.
Building with SANITIZE=leak doesn't detect this, because we are leaking
our own mmap(), and it only finds heap allocations from malloc(). But if
we use our compat mmap implementation like this:
make NO_MMAP=MapsBecomeMallocs SANITIZE=leak
then LSan will notice the leak, because now it's a regular heap buffer
allocated by malloc().
We can fix it by calling close_pack(), which will free any associated
memory. Note that we need to check for NULL ourselves; unlike free(), it
is not safe to pass a NULL pointer to close_pack().
Signed-off-by: Jeff King <peff@peff.net>
Reviewed-by: Jacob Keller <jacob.e.keller@intel.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
In check_connected(), if the transport tells us we got a single packfile
that has already been verified as self-contained and connected, then we
can skip checking connectivity for any tips that are mentioned in that
pack. This goes back to c6807a40dc (clone: open a shortcut for
connectivity check, 2013-05-26).
We don't need to open that pack until we are about to start sending oids
to our child rev-list process, since that's when we check whether they
are in the self-contained pack. Let's push the opening of that pack
further down in the function. That saves us from having to clean it up
when we leave the function early (and by the time have opened the
rev-list process, we never leave the function early, since we have to
clean up the child process).
Signed-off-by: Jeff King <peff@peff.net>
Reviewed-by: Jacob Keller <jacob.e.keller@intel.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
We have a bunch of different sites that want to iterate through all
packs of a given `struct packfile_store`. This pattern is somewhat
verbose and repetitive, which makes it somewhat cumbersome.
Introduce a new macro `repo_for_each_pack()` that removes some of the
boilerplate.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
The `get_all_packs()` function prepares the packfile store and then
returns its packfiles. Refactor it to accept a packfile store instead of
a repository to clarify its scope.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
In `reprepare_packed_git()` we perform a couple of operations:
- We reload alternate object directories.
- We clear the loose object cache.
- We reprepare packfiles.
While the logic is hosted in "packfile.c", it clearly reaches into other
subsystems that aren't related to packfiles.
Split up the responsibility and introduce `odb_reprepare()` which now
becomes responsible for repreparing the whole object database. The
existing `reprepare_packed_git()` function is refactored accordingly and
only cares about reloading the packfile store now.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
In the preceding commits we have renamed the structures contained in
"object-store.h" to `struct object_database` and `struct odb_backend`.
As such, the code files "object-store.{c,h}" are confusingly named now.
Rename them to "odb.{c,h}" accordingly.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
The "object-store-ll.h" header has been introduced to keep transitive
header dependendcies and compile times at bay. Now that we have created
a new "object-store.c" file though we can easily move the last remaining
additional bit of "object-store.h", the `odb_path_map`, out of the
header.
Do so. As the "object-store.h" header is now equivalent to its low-level
alternative we drop the latter and inline it into the former.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
The struct `packed_git` holds information regarding a packed object
file. Let's add the repository variable to this object, to represent the
repository that this packfile belongs to. This helps remove dependency
on the global `the_repository` object in `packfile.c` by simply using
repository information now readily available in the struct.
We do need to consider that a packfile could be part of the alternates
of a repository, but considering that we only have one repository struct
and also that we currently anyways use 'the_repository', we should be
OK with this change.
We also modify `alloc_packed_git` to ensure that the repository is added
to newly created `packed_git` structs. This requires modifying the
function and all its callee to pass the repository object down the
levels.
Helped-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
The main function we use to search a pack index for an object is
find_pack_entry_one(). That function still takes a bare pointer to the
hash, despite the fact that its underlying bsearch_pack() function needs
an object_id struct. And so we end up making an extra copy of the hash
into the struct just to do a lookup.
As it turns out, all callers but one already have such an object_id. So
we can just take a pointer to that struct and use it directly. This
avoids the extra copy and provides a more type-safe interface.
The one exception is get_delta_base() in packfile.c, when we are chasing
a REF_DELTA from inside the pack (and thus we have a pointer directly to
the mmap'd pack memory, not a struct). We can just bump the hashcpy()
from inside find_pack_entry_one() to this one caller that needs it.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Use of the `the_repository` variable is deprecated nowadays, and we
slowly but steadily convert the codebase to not use it anymore. Instead,
callers should be passing down the repository to work on via parameters.
It is hard though to prove that a given code unit does not use this
variable anymore. The most trivial case, merely demonstrating that there
is no direct use of `the_repository`, is already a bit of a pain during
code reviews as the reviewer needs to manually verify claims made by the
patch author. The bigger problem though is that we have many interfaces
that implicitly rely on `the_repository`.
Introduce a new `USE_THE_REPOSITORY_VARIABLE` macro that allows code
units to opt into usage of `the_repository`. The intent of this macro is
to demonstrate that a certain code unit does not use this variable
anymore, and to keep it from new dependencies on it in future changes,
be it explicit or implicit
For now, the macro only guards `the_repository` itself as well as
`the_hash_algo`. There are many more known interfaces where we have an
implicit dependency on `the_repository`, but those are not guarded at
the current point in time. Over time though, we should start to add
guards as required (or even better, just remove them).
Define the macro as required in our code units. As expected, most of our
code still relies on the global variable. Nearly all of our builtins
rely on the variable as there is no way yet to pass `the_repository` to
their entry point. For now, declare the macro in "biultin.h" to keep the
required changes at least a little bit more contained.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
The vast majority of files including object-store.h did not need dir.h
nor khash.h. Split the header into two files, and let most just depend
upon object-store-ll.h, while letting the two callers that need it
depend on the full object-store.h.
After this patch:
$ git grep -h include..object-store | sort | uniq -c
2 #include "object-store.h"
129 #include "object-store-ll.h"
Diff best viewed with `--color-moved`.
Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Split key function and data structure definitions out of cache.h to
new header files and adjust the users.
* en/header-split-cleanup:
csum-file.h: remove unnecessary inclusion of cache.h
write-or-die.h: move declarations for write-or-die.c functions from cache.h
treewide: remove cache.h inclusion due to setup.h changes
setup.h: move declarations for setup.c functions from cache.h
treewide: remove cache.h inclusion due to environment.h changes
environment.h: move declarations for environment.c functions from cache.h
treewide: remove unnecessary includes of cache.h
wrapper.h: move declarations for wrapper.c functions from cache.h
path.h: move function declarations for path.c functions from cache.h
cache.h: remove expand_user_path()
abspath.h: move absolute path functions from cache.h
environment: move comment_line_char from cache.h
treewide: remove unnecessary cache.h inclusion from several sources
treewide: remove unnecessary inclusion of gettext.h
treewide: be explicit about dependence on gettext.h
treewide: remove unnecessary cache.h inclusion from a few headers
Code clean-up around the use of the_repository.
* ab/remove-implicit-use-of-the-repository:
libs: use "struct repository *" argument, not "the_repository"
post-cocci: adjust comments for recent repo_* migration
cocci: apply the "revision.h" part of "the_repository.pending"
cocci: apply the "rerere.h" part of "the_repository.pending"
cocci: apply the "refs.h" part of "the_repository.pending"
cocci: apply the "promisor-remote.h" part of "the_repository.pending"
cocci: apply the "packfile.h" part of "the_repository.pending"
cocci: apply the "pretty.h" part of "the_repository.pending"
cocci: apply the "object-store.h" part of "the_repository.pending"
cocci: apply the "diff.h" part of "the_repository.pending"
cocci: apply the "commit.h" part of "the_repository.pending"
cocci: apply the "commit-reach.h" part of "the_repository.pending"
cocci: apply the "cache.h" part of "the_repository.pending"
cocci: add missing "the_repository" macros to "pending"
cocci: sort "the_repository" rules by header
cocci: fix incorrect & verbose "the_repository" rules
cocci: remove dead rule from "the_repository.pending.cocci"
Apply the part of "the_repository.pending.cocci" pertaining to
"promisor-remote.h".
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
A number of files were apparently including cache.h solely to get
gettext.h. By making those files explicitly include gettext.h, we can
already drop the include of cache.h in these files. On top of that,
there were some files using cache.h that didn't need to for any reason.
Remove these unnecessary includes.
Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Dozens of files made use of gettext functions, without explicitly
including gettext.h. This made it more difficult to find which files
could remove a dependence on cache.h. Make C files explicitly include
gettext.h if they are using it.
However, while compat/fsmonitor/fsm-ipc-darwin.c should also gain an
include of gettext.h, it was left out to avoid conflicting with an
in-flight topic.
Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Various leak fixes.
* ab/various-leak-fixes:
built-ins: use free() not UNLEAK() if trivial, rm dead code
revert: fix parse_options_concat() leak
cherry-pick: free "struct replay_opts" members
rebase: don't leak on "--abort"
connected.c: free the "struct packed_git"
sequencer.c: fix "opts->strategy" leak in read_strategy_opts()
ls-files: fix a --with-tree memory leak
revision API: call graph_clear() in release_revisions()
unpack-file: fix ancient leak in create_temp_file()
built-ins & libs & helpers: add/move destructors, fix leaks
dir.c: free "ident" and "exclude_per_dir" in "struct untracked_cache"
read-cache.c: clear and free "sparse_checkout_patterns"
commit: discard partial cache before (re-)reading it
{reset,merge}: call discard_index() before returning
tests: mark tests as passing with SANITIZE=leak
The "new_pack" we allocate in check_connected() wasn't being
free'd. Let's do that before we return from the function. This has
leaked ever since "new_pack" was added to this function in
c6807a40dc (clone: open a shortcut for connectivity check,
2013-05-26).
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
When serving a push, git-receive-pack(1) needs to verify that the
packfile sent by the client contains all objects that are required by
the updated references. This connectivity check works by marking all
preexisting references as uninteresting and using the new reference tips
as starting point for a graph walk.
Marking all preexisting references as uninteresting can be a problem
when it comes to performance. Git forges tend to do internal bookkeeping
to keep alive sets of objects for internal use or make them easy to find
via certain references. These references are typically hidden away from
the user so that they are neither advertised nor writeable. At GitLab,
we have one particular repository that contains a total of 7 million
references, of which 6.8 million are indeed internal references. With
the current connectivity check we are forced to load all these
references in order to mark them as uninteresting, and this alone takes
around 15 seconds to compute.
We can optimize this by only taking into account the set of visible refs
when marking objects as uninteresting. This means that we may now walk
more objects until we hit any object that is marked as uninteresting.
But it is rather unlikely that clients send objects that make large
parts of objects reachable that have previously only ever been hidden,
whereas the common case is to push incremental changes that build on top
of the visible object graph.
This provides a huge boost to performance in the mentioned repository,
where the vast majority of its refs hidden. Pushing a new commit into
this repo with `transfer.hideRefs` set up to hide 6.8 million of 7 refs
as it is configured in Gitaly leads to a 4.5-fold speedup:
Benchmark 1: main
Time (mean ± σ): 30.977 s ± 0.157 s [User: 30.226 s, System: 1.083 s]
Range (min … max): 30.796 s … 31.071 s 3 runs
Benchmark 2: pks-connectivity-check-hide-refs
Time (mean ± σ): 6.799 s ± 0.063 s [User: 6.803 s, System: 0.354 s]
Range (min … max): 6.729 s … 6.850 s 3 runs
Summary
'pks-connectivity-check-hide-refs' ran
4.56 ± 0.05 times faster than 'main'
As we mostly go through the same codepaths even in the case where there
are no hidden refs at all compared to the code before there is no change
in performance when no refs are hidden:
Benchmark 1: main
Time (mean ± σ): 48.188 s ± 0.432 s [User: 49.326 s, System: 5.009 s]
Range (min … max): 47.706 s … 48.539 s 3 runs
Benchmark 2: pks-connectivity-check-hide-refs
Time (mean ± σ): 48.027 s ± 0.500 s [User: 48.934 s, System: 5.025 s]
Range (min … max): 47.504 s … 48.500 s 3 runs
Summary
'pks-connectivity-check-hide-refs' ran
1.00 ± 0.01 times faster than 'main'
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Start following-up on the rename mentioned in c7c4bdeccf (run-command
API: remove "env" member, always use "env_array", 2021-11-25) of
"env_array" to "env".
The "env_array" name was picked in 19a583dc39 (run-command: add
env_array, an optional argv_array for env, 2014-10-19) because "env"
was taken. Let's not forever keep the oddity of "*_array" for this
"struct strvec", but not for its "args" sibling.
This commit is almost entirely made with a coccinelle rule[1]. The
only manual change here is in run-command.h to rename the struct
member itself and to change "env_array" to "env" in the
CHILD_PROCESS_INIT initializer.
The rest of this is all a result of applying [1]:
* make contrib/coccinelle/run_command.cocci.patch
* patch -p1 <contrib/coccinelle/run_command.cocci.patch
* git add -u
1. cat contrib/coccinelle/run_command.pending.cocci
@@
struct child_process E;
@@
- E.env_array
+ E.env
@@
struct child_process *E;
@@
- E->env_array
+ E->env
I've avoided changing any comments and derived variable names here,
that will all be done in the next commit.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Remove the "env" member from "struct child_process" in favor of always
using the "env_array". As with the preceding removal of "argv" in
favor of "args" this gets rid of current and future oddities around
memory management at the API boundary (see the amended API docs).
For some of the conversions we can replace patterns like:
child.env = env->v;
With:
strvec_pushv(&child.env_array, env->v);
But for others we need to guard the strvec_pushv() with a NULL check,
since we're not passing in the "v" member of a "struct strvec",
e.g. in the case of tmp_objdir_env()'s return value.
Ideally we'd rename the "env_array" member to simply "env" as a
follow-up, since it and "args" are now inconsistent in not having an
"_array" suffix, and seemingly without any good reason, unless we look
at the history of how they came to be.
But as we've currently got 122 in-tree hits for a "git grep env_array"
let's leave that for now (and possibly forever). Doing that rename
would be too disruptive.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
This reverts commit f45022dc2f,
as this is like breakage in the traversal more likely. In a
history with 10 single strand of pearls,
1-->2-->3--...->7-->8-->9-->10
asking "rev-list --unsorted-input 1 10 --not 9 8 7 6 5 4" fails to
paint the bottom 1 uninteresting as the traversal stops, without
completing the propagation of uninteresting bit starting at 4 down
through 3 and 2 to 1.
Optimize code that handles large number of refs in the "git fetch"
code path.
* ps/fetch-optim:
fetch: avoid second connectivity check if we already have all objects
fetch: merge fetching and consuming refs
fetch: refactor fetch refs to be more extendable
fetch-pack: optimize loading of refs via commit graph
connected: refactor iterator to return next object ID directly
fetch: avoid unpacking headers in object existence check
fetch: speed up lookup of want refs via commit-graph
The object ID iterator used by the connectivity checks returns the next
object ID via an out-parameter and then uses a return code to indicate
whether an item was found. This is a bit roundabout: instead of a
separate error code, we can just return the next object ID directly and
use `NULL` pointers as indicator that the iterator got no items left.
Furthermore, this avoids a copy of the object ID.
Refactor the iterator and all its implementations to return object IDs
directly. This brings a tiny performance improvement when doing a mirror-fetch of a repository with about 2.3M refs:
Benchmark #1: 328dc58b49919c43897240f2eabfa30be2ce32a4~: git-fetch
Time (mean ± σ): 30.110 s ± 0.148 s [User: 27.161 s, System: 5.075 s]
Range (min … max): 29.934 s … 30.406 s 10 runs
Benchmark #2: 328dc58b49919c43897240f2eabfa30be2ce32a4: git-fetch
Time (mean ± σ): 29.899 s ± 0.109 s [User: 26.916 s, System: 5.104 s]
Range (min … max): 29.696 s … 29.996 s 10 runs
Summary
'328dc58b49919c43897240f2eabfa30be2ce32a4: git-fetch' ran
1.01 ± 0.01 times faster than '328dc58b49919c43897240f2eabfa30be2ce32a4~: git-fetch'
While this 1% speedup could be labelled as statistically insignificant,
the speedup is consistent on my machine. Furthermore, this is an end to
end test, so it is expected that the improvement in the connectivity
check itself is more significant.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
In order to compute whether objects reachable from a set of tips are all
connected, we do a revision walk with these tips as positive references
and `--not --all`. `--not --all` will cause the revision walk to load
all preexisting references as uninteresting, which can be very expensive
in repositories with many references.
Benchmarking the git-rev-list(1) command highlights that by far the most
expensive single phase is initial sorting of the input revisions: after
all references have been loaded, we first sort commits by author date.
In a real-world repository with about 2.2 million references, it makes
up about 40% of the total runtime of git-rev-list(1).
Ultimately, the connectivity check shouldn't really bother about the
order of input revisions at all. We only care whether we can actually
walk all objects until we hit the cut-off point. So sorting the input is
a complete waste of time.
Introduce a new "--unsorted-input" flag to git-rev-list(1) which will
cause it to not sort the commits and adjust the connectivity check to
always pass the flag. This results in the following speedups, executed
in a clone of gitlab-org/gitlab [1]:
Benchmark #1: git rev-list --objects --quiet --not --all --not $(cat newrev)
Time (mean ± σ): 7.639 s ± 0.065 s [User: 7.304 s, System: 0.335 s]
Range (min … max): 7.543 s … 7.742 s 10 runs
Benchmark #2: git rev-list --unsorted-input --objects --quiet --not --all --not $newrev
Time (mean ± σ): 4.995 s ± 0.044 s [User: 4.657 s, System: 0.337 s]
Range (min … max): 4.909 s … 5.048 s 10 runs
Summary
'git rev-list --unsorted-input --objects --quiet --not --all --not $(cat newrev)' ran
1.53 ± 0.02 times faster than 'git rev-list --objects --quiet --not --all --not $newrev'
[1]: https://gitlab.com/gitlab-org/gitlab.git. Note that not all refs
are visible to clients.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Use more buffered I/O where we used to call many small write(2)s.
* rs/more-buffered-io:
upload-pack: use buffered I/O to talk to rev-list
midx: use buffered I/O to talk to pack-objects
connected: use buffered I/O to talk to rev-list
Like f0bca72dc7 (send-pack: use buffered I/O to talk to pack-objects,
2016-06-08), significantly reduce the number of system calls and
simplify the code for sending object IDs to rev-list by using stdio's
buffering.
Take care to handle errors immediately to get the correct error code,
and to flush the buffer explicitly before closing the stream in order to
catch any write errors for these last bytes.
Helped-by: Chris Torek <chris.torek@gmail.com>
Helped-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Code which split an argv_array call across multiple lines, like:
argv_array_pushl(&args, "one argument",
"another argument", "and more",
NULL);
was recently mechanically renamed to use strvec, which results in
mis-matched indentation like:
strvec_pushl(&args, "one argument",
"another argument", "and more",
NULL);
Let's fix these up to align the arguments with the opening paren. I did
this manually by sifting through the results of:
git jump grep 'strvec_.*,$'
and liberally applying my editor's auto-format. Most of the changes are
of the form shown above, though I also normalized a few that had
originally used a single-tab indentation (rather than our usual style of
aligning with the open paren). I also rewrapped a couple of obvious
cases (e.g., where previously too-long lines became short enough to fit
on one), but I wasn't aggressive about it. In cases broken to three or
more lines, the grouping of arguments is sometimes meaningful, and it
wasn't worth my time or reviewer time to ponder each case individually.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
We eventually want to drop the argv_array name and just use strvec
consistently. There's no particular reason we have to do it all at once,
or care about interactions between converted and unconverted bits.
Because of our preprocessor compat layer, the names are interchangeable
to the compiler (so even a definition and declaration using different
names is OK).
This patch converts remaining files from the first half of the alphabet,
to keep the diff to a manageable size.
The conversion was done purely mechanically with:
git ls-files '*.c' '*.h' |
xargs perl -i -pe '
s/ARGV_ARRAY/STRVEC/g;
s/argv_array/strvec/g;
'
and then selectively staging files with "git add '[abcdefghjkl]*'".
We'll deal with any indentation/style fallouts separately.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Whenever a fetch results in a packfile being downloaded, a .keep file is
generated, so that the packfile can be preserved (from, say, a running
"git repack") until refs are written referring to the contents of the
packfile.
In a subsequent patch, a successful fetch using protocol v2 may result
in more than one .keep file being generated. Therefore, teach
fetch_pack() and the transport mechanism to support multiple .keep
files.
Implementation notes:
- builtin/fetch-pack.c normally does not generate .keep files, and thus
is unaffected by this or future changes. However, it has an
undocumented "--lock-pack" feature, used by remote-curl.c when
implementing the "fetch" remote helper command. In keeping with the
remote helper protocol, only one "lock" line will ever be written;
the rest will result in warnings to stderr. However, in practice,
warnings will never be written because the remote-curl.c "fetch" is
only used for protocol v0/v1 (which will not generate multiple .keep
files). (Protocol v2 uses the "stateless-connect" command, not the
"fetch" command.)
- connected.c has an optimization in that connectivity checks on a ref
need not be done if the target object is in a pack known to be
self-contained and connected. If there are multiple packfiles, this
optimization can no longer be done.
Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Simplify the commit ancestry connectedness check in a partial clone
repository in which "promised" objects are assumed to be obtainable
lazily on-demand from promisor remote repositories.
* jt/connectivity-check-optim-in-partial-clone:
connected: always use partial clone optimization
With 50033772d5 ("connected: verify promisor-ness of partial clone",
2020-01-30), the fast path (checking promisor packs) in
check_connected() now passes a subset of the slow path (rev-list) - if
all objects to be checked are found in promisor packs, both the fast
path and the slow path will pass; otherwise, the fast path will
definitely not pass. This means that we can always attempt the fast path
whenever we need to do the slow path.
The fast path is currently guarded by a flag; therefore, remove that
flag. Also, make the fast path fallback to the slow path - if the fast
path fails, the failing OID and all remaining OIDs will be passed to
rev-list.
The main user-visible benefit is the performance of fetch from a partial
clone - specifically, the speedup of the connectivity check done before
the fetch. In particular, a no-op fetch into a partial clone on my
computer was sped up from 7 seconds to 0.01 seconds. This is a
complement to the work in 2df1aa239c ("fetch: forgo full
connectivity check if --filter", 2020-01-30), which is the child of the
aforementioned 50033772d5. In that commit, the connectivity check
*after* the fetch was sped up.
The addition of the fast path might cause performance reductions in
these cases:
- If a partial clone or a fetch into a partial clone fails, Git will
fruitlessly run rev-list (it is expected that everything fetched
would go into promisor packs, so if that didn't happen, it is most
likely that rev-list will fail too).
- Any connectivity checks done by receive-pack, in the (in my opinion,
unlikely) event that a partial clone serves receive-pack.
I think that these cases are rare enough, and the performance reduction
in this case minor enough (additional object DB access), that the
benefit of avoiding a flag outweighs these.
Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Reviewed-by: Josh Steadmon <steadmon@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
While updating the microsoft/git fork on top of v2.26.0-rc0 and
consuming that build into Scalar, I noticed a corner case bug around
partial clone.
The "scalar clone" command can create a Git repository with the
proper config for using partial clone with the "blob:none" filter.
Instead of calling "git clone", it runs "git init" then sets a few
more config values before running "git fetch".
In our builds on v2.26.0-rc0, we noticed that our "git fetch"
command was failing with
error: https://github.com/microsoft/scalar did not send all necessary objects
This does not happen if you copy the config file from a repository
created by "git clone --filter=blob:none <url>", but it does happen
when adding the config option "core.logAllRefUpdates = true".
By debugging, I was able to see that the loop inside
check_connnected() that checks if all refs are contained in
promisor packs actually did not have any packfiles in the packed_git
list.
I'm not sure what corner-case issues caused this config option to
prevent the reprepare_packed_git() from being called at the proper
spot during the fetch operation. This approach requires a situation
where we use the remote helper process, which makes it difficult to
test.
It is possible to place a reprepare_packed_git() call in the fetch code
closer to where we receive a pack, but that leaves an opening for a
later change to re-introduce this problem. Further, a concurrent repack
operation could replace the pack-file list we already loaded into
memory, causing this issue in an even harder to reproduce scenario.
It is really the responsibility of anyone looping through the list of
pack-files for a certain object to fall back to reprepare_packed_git()
on a fail-to-find. The loop in check_connected() does not have this
fallback, leading to this bug.
We _could_ try looping through the packs and only reprepare the packs
after a miss, but that change is more involved and has little value.
Since this case is isolated to the case when
opt->check_refs_are_promisor_objects_only is true, we are confident that
we are verifying the refs after downloading new data. This implies that
calling reprepare_packed_git() in advance is not a huge cost compared to
the rest of the operations already made.
Helped-by: Jeff King <peff@peff.net>
Helped-by: Junio Hamano <gitster@pobox.com>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Commit dfa33a298d ("clone: do faster object check for partial clones",
2019-04-21) optimized the connectivity check done when cloning with
--filter to check only the existence of objects directly pointed to by
refs. But this is not sufficient: they also need to be promisor objects.
Make this check more robust by instead checking that these objects are
promisor objects, that is, they appear in a promisor pack.
Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Commit 6462d5eb9a ("fetch: remove fetch_if_missing=0", 2019-11-08)
strove to remove the need for fetch_if_missing=0 from the fetching
mechanism, so it is plausible to attempt removing fetch_if_missing=0
from clone as well. But doing so reveals a bug - when the server does
not send an object directly pointed to by a ref, this should be an
error, not a trigger for a lazy fetch. (This case in the fetching
mechanism was covered by a test using "git clone", not "git fetch",
which is why the aforementioned commit didn't uncover the bug.)
The bug can be fixed by suppressing lazy-fetching during the
connectivity check. Fix this bug, and remove fetch_if_missing from
clone.
Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Preparation for SHA-256 upgrade continues.
* bc/object-id-part17: (26 commits)
midx: switch to using the_hash_algo
builtin/show-index: replace sha1_to_hex
rerere: replace sha1_to_hex
builtin/receive-pack: replace sha1_to_hex
builtin/index-pack: replace sha1_to_hex
packfile: replace sha1_to_hex
wt-status: convert struct wt_status to object_id
cache: remove null_sha1
builtin/worktree: switch null_sha1 to null_oid
builtin/repack: write object IDs of the proper length
pack-write: use hash_to_hex when writing checksums
sequencer: convert to use the_hash_algo
bisect: switch to using the_hash_algo
sha1-lookup: switch hard-coded constants to the_hash_algo
config: use the_hash_algo in abbrev comparison
combine-diff: replace GIT_SHA1_HEXSZ with the_hash_algo
bundle: switch to use the_hash_algo
connected: switch GIT_SHA1_HEXSZ to the_hash_algo
show-index: switch hard-coded constants to the_hash_algo
blame: remove needless comparison with GIT_SHA1_HEXSZ
...
Teach the lazy clone machinery that there can be more than one
promisor remote and consult them in order when downloading missing
objects on demand.
* cc/multi-promisor:
Move core_partial_clone_filter_default to promisor-remote.c
Move repository_format_partial_clone to promisor-remote.c
Remove fetch-object.{c,h} in favor of promisor-remote.{c,h}
remote: add promisor and partial clone config to the doc
partial-clone: add multiple remotes in the doc
t0410: test fetching from many promisor remotes
builtin/fetch: remove unique promisor remote limitation
promisor-remote: parse remote.*.partialclonefilter
Use promisor_remote_get_direct() and has_promisor_remote()
promisor-remote: use repository_format_partial_clone
promisor-remote: add promisor_remote_reinit()
promisor-remote: implement promisor_remote_get_direct()
Add initial support for many promisor remotes
fetch-object: make functions return an error code
t0410: remove pipes after git commands
Switch various uses of GIT_SHA1_HEXSZ to reference the_hash_algo
instead.
Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Junio C Hamano