reftable/pq: allocation-less comparison of entry keys
The priority queue is used by the merged iterator to iterate over
reftable records from multiple tables in the correct order. The queue
ends up having one record for each table that is being iterated over,
with the record that is supposed to be shown next at the top. For
example, the key of a ref record is equal to its name so that we end up
sorting the priority queue lexicographically by ref name.
To figure out the order we need to compare the reftable record keys with
each other. This comparison is done by formatting them into a `struct
strbuf` and then doing `strbuf_strcmp()` on the result. We then discard
the buffers immediately after the comparison.
This ends up being very expensive. Because the priority queue usually
contains as many records as we have tables, we call the comparison
function `O(log($tablecount))` many times for every record we insert.
Furthermore, when iterating over many refs, we will insert at least one
record for every ref we are iterating over. So ultimately, this ends up
being called `O($refcount * log($tablecount))` many times.
Refactor the code to use the new `refatble_record_cmp()` function that
has been implemented in a preceding commit. This function does not need
to allocate memory and is thus significantly more efficient.
The following benchmark prints a single ref matching a specific pattern
out of 1 million refs via git-show-ref(1), where the reftable stack
consists of three tables:
Benchmark 1: show-ref: single matching ref (revision = HEAD~)
Time (mean ± σ): 224.4 ms ± 6.5 ms [User: 220.6 ms, System: 3.6 ms]
Range (min … max): 216.5 ms … 261.1 ms 1000 runs
Benchmark 2: show-ref: single matching ref (revision = HEAD)
Time (mean ± σ): 172.9 ms ± 4.4 ms [User: 169.2 ms, System: 3.6 ms]
Range (min … max): 166.5 ms … 204.6 ms 1000 runs
Summary
show-ref: single matching ref (revision = HEAD) ran
1.30 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)
Signed-off-by: Patrick Steinhardt <ps@pks.im> Signed-off-by: Junio C Hamano <gitster@pobox.com>
reftable/merged: skip comparison for records of the same subiter
When retrieving the next entry of a merged iterator we need to drop all
records of other sub-iterators that would be shadowed by the record that
we are about to return. We do this by comparing record keys, dropping
all keys that are smaller or equal to the key of the record we are about
to return.
There is an edge case here where we can skip that comparison: when the
record in the priority queue comes from the same subiterator as the
record we are about to return then we know that its key must be larger
than the key of the record we are about to return. This property is
guaranteed by the sub-iterators, and if it didn't hold then the whole
merged iterator would return records in the wrong order, too.
While this may seem like a very specific edge case it's in fact quite
likely to happen. For most repositories out there you can assume that we
will end up with one large table and several smaller ones on top of it.
Thus, it is very likely that the next entry will sort towards the top of
the priority queue.
Special case this and break out of the loop in that case. The following
benchmark uses git-show-ref(1) to print a single ref matching a pattern
out of 1 million refs:
Benchmark 1: show-ref: single matching ref (revision = HEAD~)
Time (mean ± σ): 162.6 ms ± 4.5 ms [User: 159.0 ms, System: 3.5 ms]
Range (min … max): 156.6 ms … 188.5 ms 1000 runs
Benchmark 2: show-ref: single matching ref (revision = HEAD)
Time (mean ± σ): 156.8 ms ± 4.7 ms [User: 153.0 ms, System: 3.6 ms]
Range (min … max): 151.4 ms … 188.4 ms 1000 runs
Summary
show-ref: single matching ref (revision = HEAD) ran
1.04 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)
Signed-off-by: Patrick Steinhardt <ps@pks.im> Signed-off-by: Junio C Hamano <gitster@pobox.com>
reftable/merged: allocation-less dropping of shadowed records
The purpose of the merged reftable iterator is to iterate through all
entries of a set of tables in the correct order. This is implemented by
using a sub-iterator for each table, where the next entry of each of
these iterators gets put into a priority queue. For each iteration, we
do roughly the following steps:
1. Retrieve the top record of the priority queue. This is the entry we
want to return to the caller.
2. Retrieve the next record of the sub-iterator that this record came
from. If any, add it to the priority queue at the correct position.
The position is determined by comparing the record keys, which e.g.
corresponds to the refname for ref records.
3. Keep removing the top record of the priority queue until we hit the
first entry whose key is larger than the returned record's key.
This is required to drop "shadowed" records.
The last step will lead to at least one comparison to the next entry,
but may lead to many comparisons in case the reftable stack consists of
many tables with shadowed records. It is thus part of the hot code path
when iterating through records.
The code to compare the entries with each other is quite inefficient
though. Instead of comparing record keys with each other directly, we
first format them into `struct strbuf`s and only then compare them with
each other. While we already optimized this code path to reuse buffers
in 829231dc20 (reftable/merged: reuse buffer to compute record keys,
2023-12-11), the cost to format the keys into the buffers still adds up
quite significantly.
Refactor the code to use `reftable_record_cmp()` instead, which has been
introduced in the preceding commit. This function compares records with
each other directly without requiring any memory allocations or copying
and is thus way more efficient.
The following benchmark uses git-show-ref(1) to print a single ref
matching a pattern out of 1 million refs. This is the most direct way to
exercise ref iteration speed as we remove all overhead of having to show
the refs, too.
Benchmark 1: show-ref: single matching ref (revision = HEAD~)
Time (mean ± σ): 180.7 ms ± 4.7 ms [User: 177.1 ms, System: 3.4 ms]
Range (min … max): 174.9 ms … 211.7 ms 1000 runs
Benchmark 2: show-ref: single matching ref (revision = HEAD)
Time (mean ± σ): 162.1 ms ± 4.4 ms [User: 158.5 ms, System: 3.4 ms]
Range (min … max): 155.4 ms … 189.3 ms 1000 runs
Summary
show-ref: single matching ref (revision = HEAD) ran
1.11 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)
Signed-off-by: Patrick Steinhardt <ps@pks.im> Signed-off-by: Junio C Hamano <gitster@pobox.com>
reftable/record: introduce function to compare records by key
In some places we need to sort reftable records by their keys to
determine their ordering. This is done by first formatting the keys into
a `struct strbuf` and then using `strbuf_cmp()` to compare them. This
logic is needlessly roundabout and can end up costing quite a bit of CPU
cycles, both due to the allocation and formatting logic.
Introduce a new `reftable_record_cmp()` function that knows how to
compare two records with each other without requiring allocations.
Signed-off-by: Patrick Steinhardt <ps@pks.im> Signed-off-by: Junio C Hamano <gitster@pobox.com>
ci(linux32): add a note about Actions that must not be updated
The Docker container used by the `linux32` job comes without Node.js,
and therefore the `actions/checkout` and `actions/upload-artifact`
Actions cannot be upgraded to the latest versions (because they use
Node.js).
One time too many, I accidentally tried to update them, where
`actions/checkout` at least fails immediately, but the
`actions/upload-artifact` step is only used when any test fails, and
therefore the CI run usually passes even though that Action was updated
to a version that is incompatible with the Docker container in which
this job runs.
So let's add a big fat warning, mainly for my own benefit, to avoid
running into the very same issue over and over again.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
After activating automatic Dependabot updates in the
git-for-windows/git repository, Dependabot noticed a couple
of yet-unaddressed updates. They avoid "Node.js 16 Actions"
deprecation messages by bumping the following Actions'
versions:
- actions/upload-artifact from 3 to 4
- actions/download-artifact from 3 to 4
- actions/cache from 3 to 4
Helped-by: Matthias Aßhauer <mha1993@live.de> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Junio C Hamano [Sun, 11 Feb 2024 15:58:04 +0000 (07:58 -0800)]
unit-tests: do show relative file paths on non-Windows, too
There are compilers other than Visual C that want to show absolute
paths. Generalize the helper introduced by a2c5e294 (unit-tests: do
show relative file paths, 2023-09-25) so that it can also work with
a path that uses slash as the directory separator, and becomes
almost no-op once one-time preparation finds out that we are using a
compiler that already gives relative paths. Incidentally, this also
should do the right thing on Windows with a compiler that shows
relative paths but with backslash as the directory separator (if
such a thing exists and is used to build git).
Reported-by: Randall S. Becker <rsbecker@nexbridge.com> Helped-by: Phillip Wood <phillip.wood@dunelm.org.uk> Signed-off-by: Junio C Hamano <gitster@pobox.com>
René Scharfe [Fri, 9 Feb 2024 20:36:40 +0000 (21:36 +0100)]
receive-pack: use find_commit_header() in check_cert_push_options()
Use the public function find_commit_header() instead of find_header() to
simplify the code. This is possible and safe because we're operating on
a strbuf, which is always NUL-terminated, so there is no risk of running
over the end of the buffer. It cannot contain NUL within the buffer, as
it is built using strbuf_addstr(), only.
The string comparison becomes more complicated because we need to check
for NUL explicitly after comparing the length-limited option, but on the
flip side we don't need to clean up allocations or track the remaining
buffer length.
Signed-off-by: René Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Phillip Wood [Fri, 9 Feb 2024 16:19:39 +0000 (16:19 +0000)]
prune: mark rebase autostash and orig-head as reachable
Rebase records the oid of HEAD before rebasing and the commit created by
"--autostash" in files in the rebase state directory. This means that
the autostash commit is never reachable from any ref or reflog and when
rebasing a detached HEAD the original HEAD can become unreachable if the
user expires HEAD's the reflog while the rebase is running. Fix this by
reading the relevant files when marking reachable commits.
Note that it is possible for the commit recorded in
.git/rebase-merge/amend to be unreachable but pruning that object does
not affect the operation of "git rebase --continue" as we're only
interested in the object id, not in the object itself.
Reported-by: Orgad Shaneh <orgads@gmail.com> Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Junio C Hamano [Fri, 9 Feb 2024 00:22:11 +0000 (16:22 -0800)]
Merge branch 'jx/sideband-chomp-newline-fix' into maint-2.43
Sideband demultiplexer fixes.
* jx/sideband-chomp-newline-fix:
pkt-line: do not chomp newlines for sideband messages
pkt-line: memorize sideband fragment in reader
test-pkt-line: add option parser for unpack-sideband
Junio C Hamano [Fri, 9 Feb 2024 00:22:11 +0000 (16:22 -0800)]
Merge branch 'js/contributor-docs-updates' into maint-2.43
Doc update.
* js/contributor-docs-updates:
SubmittingPatches: hyphenate non-ASCII
SubmittingPatches: clarify GitHub artifact format
SubmittingPatches: clarify GitHub visual
SubmittingPatches: provide tag naming advice
SubmittingPatches: update extra tags list
SubmittingPatches: discourage new trailers
SubmittingPatches: drop ref to "What's in git.git"
CodingGuidelines: write punctuation marks
CodingGuidelines: move period inside parentheses
Junio C Hamano [Fri, 9 Feb 2024 00:22:10 +0000 (16:22 -0800)]
Merge branch 'en/header-cleanup' into maint-2.43
Remove unused header "#include".
* en/header-cleanup:
treewide: remove unnecessary includes in source files
treewide: add direct includes currently only pulled in transitively
trace2/tr2_tls.h: remove unnecessary include
submodule-config.h: remove unnecessary include
pkt-line.h: remove unnecessary include
line-log.h: remove unnecessary include
http.h: remove unnecessary include
fsmonitor--daemon.h: remove unnecessary includes
blame.h: remove unnecessary includes
archive.h: remove unnecessary include
treewide: remove unnecessary includes in source files
treewide: remove unnecessary includes from header files
Junio C Hamano [Fri, 9 Feb 2024 00:22:09 +0000 (16:22 -0800)]
Merge branch 'la/trailer-cleanups' into maint-2.43
Code clean-up.
* la/trailer-cleanups:
trailer: use offsets for trailer_start/trailer_end
trailer: find the end of the log message
commit: ignore_non_trailer computes number of bytes to ignore
Junio C Hamano [Fri, 9 Feb 2024 00:22:08 +0000 (16:22 -0800)]
Merge branch 'jc/doc-most-refs-are-not-that-special' into maint-2.43
Doc updates.
* jc/doc-most-refs-are-not-that-special:
docs: MERGE_AUTOSTASH is not that special
docs: AUTO_MERGE is not that special
refs.h: HEAD is not that special
git-bisect.txt: BISECT_HEAD is not that special
git.txt: HEAD is not that special
Junio C Hamano [Fri, 9 Feb 2024 00:22:07 +0000 (16:22 -0800)]
Merge branch 'jk/config-cleanup' into maint-2.43
Code clean-up around use of configuration variables.
* jk/config-cleanup:
sequencer: simplify away extra git_config_string() call
gpg-interface: drop pointless config_error_nonbool() checks
push: drop confusing configset/callback redundancy
config: use git_config_string() for core.checkRoundTripEncoding
diff: give more detailed messages for bogus diff.* config
config: use config_error_nonbool() instead of custom messages
imap-send: don't use git_die_config() inside callback
git_xmerge_config(): prefer error() to die()
config: reject bogus values for core.checkstat
Junio C Hamano [Fri, 9 Feb 2024 00:22:06 +0000 (16:22 -0800)]
Merge branch 'rs/incompatible-options-messages' into maint-2.43
Clean-up code that handles combinations of incompatible options.
* rs/incompatible-options-messages:
worktree: simplify incompatibility message for --orphan and commit-ish
worktree: standardize incompatibility messages
clean: factorize incompatibility message
revision, rev-parse: factorize incompatibility messages about - -exclude-hidden
revision: use die_for_incompatible_opt3() for - -graph/--reverse/--walk-reflogs
repack: use die_for_incompatible_opt3() for -A/-k/--cruft
push: use die_for_incompatible_opt4() for - -delete/--tags/--all/--mirror
Junio C Hamano [Fri, 9 Feb 2024 00:22:06 +0000 (16:22 -0800)]
Merge branch 'ps/ref-tests-update-more' into maint-2.43
Tests update.
* ps/ref-tests-update-more:
t6301: write invalid object ID via `test-tool ref-store`
t5551: stop writing packed-refs directly
t5401: speed up creation of many branches
t4013: simplify magic parsing and drop "failure"
t3310: stop checking for reference existence via `test -f`
t1417: make `reflog --updateref` tests backend agnostic
t1410: use test-tool to create empty reflog
t1401: stop treating FETCH_HEAD as real reference
t1400: split up generic reflog tests from the reffile-specific ones
t0410: mark tests to require the reffiles backend
Junio C Hamano [Fri, 9 Feb 2024 00:22:05 +0000 (16:22 -0800)]
Merge branch 'jk/commit-graph-slab-clear-fix' into maint-2.43
Clearing in-core repository (happens during e.g., "git fetch
--recurse-submodules" with commit graph enabled) made in-core
commit object in an inconsistent state by discarding the necessary
data from commit-graph too early, which has been corrected.
* jk/commit-graph-slab-clear-fix:
commit-graph: retain commit slab when closing NULL commit_graph
Junio C Hamano [Fri, 9 Feb 2024 00:22:04 +0000 (16:22 -0800)]
Merge branch 'rj/status-bisect-while-rebase' into maint-2.43
"git status" is taught to show both the branch being bisected and
being rebased when both are in effect at the same time.
cf. <xmqqil76kyov.fsf@gitster.g>
* rj/status-bisect-while-rebase:
status: fix branch shown when not only bisecting
Junio C Hamano [Fri, 9 Feb 2024 00:22:03 +0000 (16:22 -0800)]
Merge branch 'jk/mailinfo-iterative-unquote-comment' into maint-2.43
The code to parse the From e-mail header has been updated to avoid
recursion.
* jk/mailinfo-iterative-unquote-comment:
mailinfo: avoid recursion when unquoting From headers
t5100: make rfc822 comment test more careful
mailinfo: fix out-of-bounds memory reads in unquote_quoted_pair()
Junio C Hamano [Fri, 9 Feb 2024 00:22:03 +0000 (16:22 -0800)]
Merge branch 'jk/implicit-true' into maint-2.43
Some codepaths did not correctly parse configuration variables
specified with valueless "true", which has been corrected.
* jk/implicit-true:
fsck: handle NULL value when parsing message config
trailer: handle NULL value when parsing trailer-specific config
submodule: handle NULL value when parsing submodule.*.branch
help: handle NULL value for alias.* config
trace2: handle NULL values in tr2_sysenv config callback
setup: handle NULL value when parsing extensions
config: handle NULL value when parsing non-bools
Junio C Hamano [Fri, 9 Feb 2024 00:22:02 +0000 (16:22 -0800)]
Merge branch 'jk/end-of-options' into maint-2.43
"git $cmd --end-of-options --rev -- --path" for some $cmd failed
to interpret "--rev" as a rev, and "--path" as a path. This was
fixed for many programs like "reset" and "checkout".
* jk/end-of-options:
parse-options: decouple "--end-of-options" and "--"
Junio C Hamano [Fri, 9 Feb 2024 00:22:02 +0000 (16:22 -0800)]
Merge branch 'jc/revision-parse-int' into maint-2.43
The command line parser for the "log" family of commands was too
loose when parsing certain numbers, e.g., silently ignoring the
extra 'q' in "git log -n 1q" without complaining, which has been
tightened up.
* jc/revision-parse-int:
revision: parse integer arguments to --max-count, --skip, etc., more carefully
Junio C Hamano [Fri, 9 Feb 2024 00:22:02 +0000 (16:22 -0800)]
Merge branch 'jp/use-diff-index-in-pre-commit-sample' into maint-2.43
The sample pre-commit hook that tries to catch introduction of new
paths that use potentially non-portable characters did not notice
an existing path getting renamed to such a problematic path, when
rename detection was enabled.
* jp/use-diff-index-in-pre-commit-sample:
hooks--pre-commit: detect non-ASCII when renaming
Junio C Hamano [Fri, 9 Feb 2024 00:22:01 +0000 (16:22 -0800)]
Merge branch 'jh/trace2-redact-auth' into maint-2.43
trace2 streams used to record the URLs that potentially embed
authentication material, which has been corrected.
* jh/trace2-redact-auth:
t0212: test URL redacting in EVENT format
t0211: test URL redacting in PERF format
trace2: redact passwords from https:// URLs by default
trace2: fix signature of trace2_def_param() macro
Junio C Hamano [Fri, 9 Feb 2024 00:22:01 +0000 (16:22 -0800)]
Merge branch 'js/update-urls-in-doc-and-comment' into maint-2.43
Stale URLs have been updated to their current counterparts (or
archive.org) and HTTP links are replaced with working HTTPS links.
* js/update-urls-in-doc-and-comment:
doc: refer to internet archive
doc: update links for andre-simon.de
doc: switch links to https
doc: update links to current pages
Junio C Hamano [Fri, 9 Feb 2024 00:22:01 +0000 (16:22 -0800)]
Merge branch 'ps/commit-graph-less-paranoid' into maint-2.43
Earlier we stopped relying on commit-graph that (still) records
information about commits that are lost from the object store,
which has negative performance implications. The default has been
flipped to disable this pessimization.
* ps/commit-graph-less-paranoid:
commit-graph: disable GIT_COMMIT_GRAPH_PARANOIA by default
Junio C Hamano [Fri, 9 Feb 2024 00:22:00 +0000 (16:22 -0800)]
Merge branch 'tz/send-email-negatable-options' into maint-2.43
Newer versions of Getopt::Long started giving warnings against our
(ab)use of it in "git send-email". Bump the minimum version
requirement for Perl to 5.8.1 (from September 2002) to allow
simplifying our implementation.
* tz/send-email-negatable-options:
send-email: avoid duplicate specification warnings
perl: bump the required Perl version to 5.8.1 from 5.8.0
Junio C Hamano [Fri, 9 Feb 2024 00:22:00 +0000 (16:22 -0800)]
Merge branch 'js/ci-discard-prove-state' into maint-2.43
The way CI testing used "prove" could lead to running the test
suite twice needlessly, which has been corrected.
* js/ci-discard-prove-state:
ci: avoid running the test suite _twice_
ci: add support for GitLab CI
ci: install test dependencies for linux-musl
ci: squelch warnings when testing with unusable Git repo
ci: unify setup of some environment variables
ci: split out logic to set up failed test artifacts
ci: group installation of Docker dependencies
ci: make grouping setup more generic
ci: reorder definitions for grouping functions
Junio C Hamano [Thu, 8 Feb 2024 23:15:12 +0000 (15:15 -0800)]
t9210: do not rely on lazy fetching to fail
With "rev-list --missing=print $start", where "$start" is a 40-hex
object name, the object may or may not be lazily fetched from the
promisor. Make sure it fails by forcing dereference of "$start"
at that point.
Junio C Hamano [Thu, 8 Feb 2024 21:20:33 +0000 (13:20 -0800)]
Merge branch 'jk/unit-tests-buildfix'
Build dependency around unit tests has been fixed.
* jk/unit-tests-buildfix:
t/Makefile: say the default target upfront
t/Makefile: get UNIT_TESTS list from C sources
Makefile: remove UNIT_TEST_BIN directory with "make clean"
Makefile: use mkdir_p_parent_template for UNIT_TEST_BIN
Junio C Hamano [Thu, 8 Feb 2024 21:20:33 +0000 (13:20 -0800)]
Merge branch 'jc/index-pack-fsck-levels'
The "--fsck-objects" option of "git index-pack" now can take the
optional parameter to tweak severity of different fsck errors.
* jc/index-pack-fsck-levels:
index-pack: --fsck-objects to take an optional argument for fsck msgs
index-pack: test and document --strict=<msg-id>=<severity>...
Victoria Dye [Thu, 8 Feb 2024 01:57:19 +0000 (01:57 +0000)]
ref-filter.c: sort formatted dates by byte value
Update the ref sorting functions of 'ref-filter.c' so that when date fields
are specified with a format string (such as in 'git for-each-ref
--sort=creatordate:<something>'), they are sorted by their formatted string
value rather than by the underlying numeric timestamp. Currently, date
fields are always sorted by timestamp, regardless of whether formatting
information is included in the '--sort' key.
Leaving the default (unformatted) date sorting unchanged, sorting by the
formatted date string adds some flexibility to 'for-each-ref' by allowing
for behavior like "sort by year, then by refname within each year" or "sort
by time of day". Because the inclusion of a format string previously had no
effect on sort behavior, this change likely will not affect existing usage
of 'for-each-ref' or other ref listing commands.
Additionally, update documentation & tests to document the new sorting
mechanism.
Signed-off-by: Victoria Dye <vdye@github.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Junio C Hamano [Thu, 8 Feb 2024 05:29:00 +0000 (21:29 -0800)]
ssh signing: signal an error with a negative return value
The other backend for the sign_buffer() function followed our usual
"an error is signalled with a negative return" convention, but the
SSH signer did not. Even though we already fixed the caller that
assumed only a negative return value is an error, tighten the callee
to signal an error with a negative return as well. This way, the
callees will be strict on what they produce, while the callers will
be lenient in what they accept.
When copying a ref with the reftable backend we also copy the
corresponding log records. When seeking the first log record that we're
about to copy fails though we directly return from `write_copy_table()`
without doing any cleanup, leaking several allocated data structures.
Fix this by exiting via our common cleanup logic instead.
Reported-by: Jeff King <peff@peff.net> via Coverity Signed-off-by: Patrick Steinhardt <ps@pks.im> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Junio C Hamano [Wed, 7 Feb 2024 21:44:36 +0000 (13:44 -0800)]
bisect: document command line arguments for "bisect start"
The syntax commonly used for alternatives is --opt-(a|b), not
--opt-{a,b}.
List bad/new and good/old consistently in this order, to be
consistent with the description for "git bisect terms". Clarify
<term> to either <term-old> or <term-new> to make them consistent
with the description of "git bisect (good|bad)" subcommands.
Suggested-by: Matthieu Moy <git@matthieu-moy.fr> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Junio C Hamano [Wed, 7 Feb 2024 21:44:35 +0000 (13:44 -0800)]
bisect: document "terms" subcommand more fully
The documentation for "git bisect terms", although it did not hide
any information, was a bit incomplete and forced readers to fill in
the blanks to get the complete picture.
Acked-by: Matthieu Moy <git@matthieu-moy.fr> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Junio C Hamano [Wed, 7 Feb 2024 18:46:54 +0000 (10:46 -0800)]
tag: fix sign_buffer() call to create a signed tag
The command "git tag -s" internally calls sign_buffer() to make a
cryptographic signature using the chosen backend like GPG and SSH.
The internal helper functions used by "git tag" implementation seem
to use a "negative return values are errors, zero or positive return
values are not" convention, and there are places (e.g., verify_tag()
that calls gpg_verify_tag()) that these internal helper functions
translate return values that signal errors to conform to this
convention, but do_sign() that calls sign_buffer() forgets to do so.
Fix it, so that a failed call to sign_buffer() that can return the
exit status from pipe_command() will not be overlooked.
Reported-by: Sergey Kosukhin <skosukhin@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Phillip Wood [Wed, 7 Feb 2024 16:44:36 +0000 (16:44 +0000)]
t1400: use show-ref to check pseudorefs
Now that "git show-ref --verify" accepts pseudorefs use that in
preference to "git rev-parse" when checking pseudorefs as we do when
checking branches etc.
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Phillip Wood [Wed, 7 Feb 2024 16:44:35 +0000 (16:44 +0000)]
show-ref --verify: accept pseudorefs
"git show-ref --verify" is useful for scripts that want to look up a
fully qualified refname without falling back to the DWIM rules used by
"git rev-parse" rules when the ref does not exist. Currently it will
only accept "HEAD" or a refname beginning with "refs/". Running
git show-ref --verify CHERRY_PICK_HEAD
will always result in
fatal: 'CHERRY_PICK_HEAD' - not a valid ref
even when CHERRY_PICK_HEAD exists. By calling refname_is_safe() instead
of comparing the refname to "HEAD" we can accept all one-level refs that
contain only uppercase ascii letters and underscores.
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Due to scalability issues, Shawn Pearce has originally proposed a new
"reftable" format more than six years ago [1]. Initially, this new
format was implemented in JGit with promising results. Around two years
ago, we have then added the "reftable" library to the Git codebase via a4bbd13be3 (Merge branch 'hn/reftable', 2021-12-15). With this we have
landed all the low-level code to read and write reftables. Notably
missing though was the integration of this low-level code into the Git
code base in the form of a new ref backend that ties all of this
together.
This gap is now finally closed by introducing a new "reftable" backend
into the Git codebase. This new backend promises to bring some notable
improvements to Git repositories:
- It becomes possible to do truly atomic writes where either all refs
are committed to disk or none are. This was not possible with the
"files" backend because ref updates were split across multiple loose
files.
- The disk space required to store many refs is reduced, both compared
to loose refs and packed-refs. This is enabled both by the reftable
format being a binary format, which is more compact, and by prefix
compression.
- We can ignore filesystem-specific behaviour as ref names are not
encoded via paths anymore. This means there is no need to handle
case sensitivity on Windows systems or Unicode precomposition on
macOS.
- There is no need to rewrite the complete refdb anymore every time a
ref is being deleted like it was the case for packed-refs. This
means that ref deletions are now constant time instead of scaling
linearly with the number of refs.
- We can ignore file/directory conflicts so that it becomes possible
to store both "refs/heads/foo" and "refs/heads/foo/bar".
- Due to this property we can retain reflogs for deleted refs. We have
previously been deleting reflogs together with their refs to avoid
file/directory conflicts, which is not necessary anymore.
- We can properly enumerate all refs. With the "files" backend it is
not easily possible to distinguish between refs and non-refs because
they may live side by side in the gitdir.
Not all of these improvements are realized with the current "reftable"
backend implementation. At this point, the new backend is supposed to be
a drop-in replacement for the "files" backend that is used by basically
all Git repositories nowadays. It strives for 1:1 compatibility, which
means that a user can expect the same behaviour regardless of whether
they use the "reftable" backend or the "files" backend for most of the
part.
Most notably, this means we artificially limit the capabilities of the
"reftable" backend to match the limits of the "files" backend. It is not
possible to create refs that would end up with file/directory conflicts,
we do not retain reflogs, we perform stricter-than-necessary checks.
This is done intentionally due to two main reasons:
- It makes it significantly easier to land the "reftable" backend as
tests behave the same. It would be tough to argue for each and every
single test that doesn't pass with the "reftable" backend.
- It ensures compatibility between repositories that use the "files"
backend and repositories that use the "reftable" backend. Like this,
hosters can migrate their repositories to use the "reftable" backend
without causing issues for clients that use the "files" backend in
their clones.
It is expected that these artificial limitations may eventually go away
in the long term.
Performance-wise things very much depend on the actual workload. The
following benchmarks compare the "files" and "reftable" backends in the
current version:
- Creating N refs in separate transactions shows that the "files"
backend is ~50% faster. This is not surprising given that creating a
ref only requires us to create a single loose ref. The "reftable"
backend will also perform auto compaction on updates. In real-world
workloads we would likely also want to perform pack loose refs,
which would likely change the picture.
Benchmark 1: update-ref: create refs sequentially (refformat = files, refcount = 1)
Time (mean ± σ): 2.1 ms ± 0.3 ms [User: 0.6 ms, System: 1.7 ms]
Range (min … max): 1.8 ms … 4.3 ms 133 runs
Benchmark 2: update-ref: create refs sequentially (refformat = reftable, refcount = 1)
Time (mean ± σ): 2.7 ms ± 0.1 ms [User: 0.6 ms, System: 2.2 ms]
Range (min … max): 2.4 ms … 2.9 ms 132 runs
Benchmark 3: update-ref: create refs sequentially (refformat = files, refcount = 1000)
Time (mean ± σ): 1.975 s ± 0.006 s [User: 0.437 s, System: 1.535 s]
Range (min … max): 1.969 s … 1.980 s 3 runs
Benchmark 4: update-ref: create refs sequentially (refformat = reftable, refcount = 1000)
Time (mean ± σ): 2.611 s ± 0.013 s [User: 0.782 s, System: 1.825 s]
Range (min … max): 2.597 s … 2.622 s 3 runs
Benchmark 5: update-ref: create refs sequentially (refformat = files, refcount = 100000)
Time (mean ± σ): 198.442 s ± 0.241 s [User: 43.051 s, System: 155.250 s]
Range (min … max): 198.189 s … 198.670 s 3 runs
Benchmark 6: update-ref: create refs sequentially (refformat = reftable, refcount = 100000)
Time (mean ± σ): 294.509 s ± 4.269 s [User: 104.046 s, System: 190.326 s]
Range (min … max): 290.223 s … 298.761 s 3 runs
- Creating N refs in a single transaction shows that the "files"
backend is significantly slower once we start to write many refs.
The "reftable" backend only needs to update two files, whereas the
"files" backend needs to write one file per ref.
Benchmark 1: update-ref: create many refs (refformat = files, refcount = 1)
Time (mean ± σ): 1.9 ms ± 0.1 ms [User: 0.4 ms, System: 1.4 ms]
Range (min … max): 1.8 ms … 2.6 ms 151 runs
Benchmark 2: update-ref: create many refs (refformat = reftable, refcount = 1)
Time (mean ± σ): 2.5 ms ± 0.1 ms [User: 0.7 ms, System: 1.7 ms]
Range (min … max): 2.4 ms … 3.4 ms 148 runs
Benchmark 3: update-ref: create many refs (refformat = files, refcount = 1000)
Time (mean ± σ): 152.5 ms ± 5.2 ms [User: 19.1 ms, System: 133.1 ms]
Range (min … max): 148.5 ms … 167.8 ms 15 runs
Benchmark 4: update-ref: create many refs (refformat = reftable, refcount = 1000)
Time (mean ± σ): 58.0 ms ± 2.5 ms [User: 28.4 ms, System: 29.4 ms]
Range (min … max): 56.3 ms … 72.9 ms 40 runs
Benchmark 5: update-ref: create many refs (refformat = files, refcount = 1000000)
Time (mean ± σ): 152.752 s ± 0.710 s [User: 20.315 s, System: 131.310 s]
Range (min … max): 152.165 s … 153.542 s 3 runs
Benchmark 6: update-ref: create many refs (refformat = reftable, refcount = 1000000)
Time (mean ± σ): 51.912 s ± 0.127 s [User: 26.483 s, System: 25.424 s]
Range (min … max): 51.769 s … 52.012 s 3 runs
- Deleting a ref in a fully-packed repository shows that the "files"
backend scales with the number of refs. The "reftable" backend has
constant-time deletions.
Benchmark 1: update-ref: delete ref (refformat = files, refcount = 1)
Time (mean ± σ): 1.7 ms ± 0.1 ms [User: 0.4 ms, System: 1.2 ms]
Range (min … max): 1.6 ms … 2.1 ms 316 runs
Benchmark 2: update-ref: delete ref (refformat = reftable, refcount = 1)
Time (mean ± σ): 1.8 ms ± 0.1 ms [User: 0.4 ms, System: 1.3 ms]
Range (min … max): 1.7 ms … 2.1 ms 294 runs
Benchmark 3: update-ref: delete ref (refformat = files, refcount = 1000)
Time (mean ± σ): 2.0 ms ± 0.1 ms [User: 0.5 ms, System: 1.4 ms]
Range (min … max): 1.9 ms … 2.5 ms 287 runs
Benchmark 4: update-ref: delete ref (refformat = reftable, refcount = 1000)
Time (mean ± σ): 1.9 ms ± 0.1 ms [User: 0.5 ms, System: 1.3 ms]
Range (min … max): 1.8 ms … 2.1 ms 217 runs
Benchmark 5: update-ref: delete ref (refformat = files, refcount = 1000000)
Time (mean ± σ): 229.8 ms ± 7.9 ms [User: 182.6 ms, System: 46.8 ms]
Range (min … max): 224.6 ms … 245.2 ms 6 runs
Benchmark 6: update-ref: delete ref (refformat = reftable, refcount = 1000000)
Time (mean ± σ): 2.0 ms ± 0.0 ms [User: 0.6 ms, System: 1.3 ms]
Range (min … max): 2.0 ms … 2.1 ms 3 runs
- Listing all refs shows no significant advantage for either of the
backends. The "files" backend is a bit faster, but not by a
significant margin. When repositories are not packed the "reftable"
backend outperforms the "files" backend because the "reftable"
backend performs auto-compaction.
Benchmark 1: show-ref: print all refs (refformat = files, refcount = 1, packed = true)
Time (mean ± σ): 1.6 ms ± 0.1 ms [User: 0.4 ms, System: 1.1 ms]
Range (min … max): 1.5 ms … 2.0 ms 1729 runs
Benchmark 2: show-ref: print all refs (refformat = reftable, refcount = 1, packed = true)
Time (mean ± σ): 1.6 ms ± 0.1 ms [User: 0.4 ms, System: 1.1 ms]
Range (min … max): 1.5 ms … 1.8 ms 1816 runs
Benchmark 3: show-ref: print all refs (refformat = files, refcount = 1000, packed = true)
Time (mean ± σ): 4.3 ms ± 0.1 ms [User: 0.9 ms, System: 3.3 ms]
Range (min … max): 4.1 ms … 4.6 ms 645 runs
Benchmark 4: show-ref: print all refs (refformat = reftable, refcount = 1000, packed = true)
Time (mean ± σ): 4.5 ms ± 0.2 ms [User: 1.0 ms, System: 3.3 ms]
Range (min … max): 4.2 ms … 5.9 ms 643 runs
Benchmark 5: show-ref: print all refs (refformat = files, refcount = 1000000, packed = true)
Time (mean ± σ): 2.537 s ± 0.034 s [User: 0.488 s, System: 2.048 s]
Range (min … max): 2.511 s … 2.627 s 10 runs
Benchmark 6: show-ref: print all refs (refformat = reftable, refcount = 1000000, packed = true)
Time (mean ± σ): 2.712 s ± 0.017 s [User: 0.653 s, System: 2.059 s]
Range (min … max): 2.692 s … 2.752 s 10 runs
Benchmark 7: show-ref: print all refs (refformat = files, refcount = 1, packed = false)
Time (mean ± σ): 1.6 ms ± 0.1 ms [User: 0.4 ms, System: 1.1 ms]
Range (min … max): 1.5 ms … 1.9 ms 1834 runs
Benchmark 8: show-ref: print all refs (refformat = reftable, refcount = 1, packed = false)
Time (mean ± σ): 1.6 ms ± 0.1 ms [User: 0.4 ms, System: 1.1 ms]
Range (min … max): 1.4 ms … 2.0 ms 1840 runs
Benchmark 9: show-ref: print all refs (refformat = files, refcount = 1000, packed = false)
Time (mean ± σ): 13.8 ms ± 0.2 ms [User: 2.8 ms, System: 10.8 ms]
Range (min … max): 13.3 ms … 14.5 ms 208 runs
Benchmark 10: show-ref: print all refs (refformat = reftable, refcount = 1000, packed = false)
Time (mean ± σ): 4.5 ms ± 0.2 ms [User: 1.2 ms, System: 3.3 ms]
Range (min … max): 4.3 ms … 6.2 ms 624 runs
Benchmark 11: show-ref: print all refs (refformat = files, refcount = 1000000, packed = false)
Time (mean ± σ): 12.127 s ± 0.129 s [User: 2.675 s, System: 9.451 s]
Range (min … max): 11.965 s … 12.370 s 10 runs
Benchmark 12: show-ref: print all refs (refformat = reftable, refcount = 1000000, packed = false)
Time (mean ± σ): 2.799 s ± 0.022 s [User: 0.735 s, System: 2.063 s]
Range (min … max): 2.769 s … 2.836 s 10 runs
- Printing a single ref shows no real difference between the "files"
and "reftable" backends.
Benchmark 1: show-ref: print single ref (refformat = files, refcount = 1)
Time (mean ± σ): 1.5 ms ± 0.1 ms [User: 0.4 ms, System: 1.0 ms]
Range (min … max): 1.4 ms … 1.8 ms 1779 runs
Benchmark 2: show-ref: print single ref (refformat = reftable, refcount = 1)
Time (mean ± σ): 1.6 ms ± 0.1 ms [User: 0.4 ms, System: 1.1 ms]
Range (min … max): 1.4 ms … 2.5 ms 1753 runs
Benchmark 3: show-ref: print single ref (refformat = files, refcount = 1000)
Time (mean ± σ): 1.5 ms ± 0.1 ms [User: 0.3 ms, System: 1.1 ms]
Range (min … max): 1.4 ms … 1.9 ms 1840 runs
Benchmark 4: show-ref: print single ref (refformat = reftable, refcount = 1000)
Time (mean ± σ): 1.6 ms ± 0.1 ms [User: 0.4 ms, System: 1.1 ms]
Range (min … max): 1.5 ms … 2.0 ms 1831 runs
Benchmark 5: show-ref: print single ref (refformat = files, refcount = 1000000)
Time (mean ± σ): 1.6 ms ± 0.1 ms [User: 0.4 ms, System: 1.1 ms]
Range (min … max): 1.5 ms … 2.1 ms 1848 runs
Benchmark 6: show-ref: print single ref (refformat = reftable, refcount = 1000000)
Time (mean ± σ): 1.6 ms ± 0.1 ms [User: 0.4 ms, System: 1.1 ms]
Range (min … max): 1.5 ms … 2.1 ms 1762 runs
So overall, performance depends on the usecases. Except for many
sequential writes the "reftable" backend is roughly on par or
significantly faster than the "files" backend though. Given that the
"files" backend has received 18 years of optimizations by now this can
be seen as a win. Furthermore, we can expect that the "reftable" backend
will grow faster over time when attention turns more towards
optimizations.
The complete test suite passes, except for those tests explicitly marked
to require the REFFILES prerequisite. Some tests in t0610 are marked as
failing because they depend on still-in-flight bug fixes. Tests can be
run with the new backend by setting the GIT_TEST_DEFAULT_REF_FORMAT
environment variable to "reftable".
There is a single known conceptual incompatibility with the dumb HTTP
transport. As "info/refs" SHOULD NOT contain the HEAD reference, and
because the "HEAD" file is not valid anymore, it is impossible for the
remote client to figure out the default branch without changing the
protocol. This shortcoming needs to be handled in a subsequent patch
series.
As the reftable library has already been introduced a while ago, this
commit message will not go into the details of how exactly the on-disk
format works. Please refer to our preexisting technical documentation at
Documentation/technical/reftable for this.
completion: bisect: recognize but do not complete view subcommand
The "view" alias for the visualize subcommand is neither completed nor
recognized. It's undesirable to complete it because it's first letters
are the same as for visualize, making completion less rather than more
efficient without adding much in the way of interface discovery.
However, it needs to be recognized in order to enable log option
completion for it.
Recognize but do not complete the view command by creating and using
separate lists of completable_subcommands and all_subcommands. Add
tests.
Signed-off-by: Britton Leo Kerin <britton.kerin@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
completion: bisect: complete log opts for visualize subcommand
Arguments passed to the "visualize" subcommand of git-bisect(1) get
forwarded to git-log(1). It thus supports the same options as git-log(1)
would, but our Bash completion script does not know to handle this.
Make completion of porcelain git-log options and option arguments to the
visualize subcommand work by calling __git_complete_log_opts when the
start of an option to the subcommand is seen (visualize doesn't support
any options besides the git-log options). Add test.
Signed-off-by: Britton Leo Kerin <britton.kerin@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
The options accepted by git-log are also accepted by at least one other
command (git-bisect). Factor the common option completion code into a
new function and use it from _git_log. The new function leaves
COMPREPLY empty if no option candidates are found, so that callers can
safely check it to determine if completion for other arguments should be
attempted.
Signed-off-by: Britton Leo Kerin <britton.kerin@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
completion: bisect: complete custom terms and related options
git bisect supports the use of custom terms via the --term-(new|bad) and
--term-(old|good) options, but the completion code doesn't know about
these options or the new subcommands they define.
Add support for these options and the custom subcommands by checking for
BISECT_TERMS and adding them to the list of subcommands. Add tests.
Signed-off-by: Britton Leo Kerin <britton.kerin@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
completion: tests: always use 'master' for default initial branch name
The default initial branch name can normally be configured using the
GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME environment variable. However,
when testing e.g. <rev> completion it's convenient to know the
exact initial branch name that will be used.
To achieve that without too much trouble it is considered sufficient
to force the default initial branch name to 'master' for all of
t9902-completion.sh.
Signed-off-by: Britton Leo Kerin <britton.kerin@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Junio C Hamano [Tue, 6 Feb 2024 22:31:22 +0000 (14:31 -0800)]
Merge branch 'jc/make-libpath-template'
The Makefile often had to say "-L$(path) -R$(path)" that repeats
the path to the same library directory for link time and runtime.
A Makefile template is used to reduce such repetition.
* jc/make-libpath-template:
Makefile: simplify output of the libpath_template
Makefile: reduce repetitive library paths
Junio C Hamano [Tue, 6 Feb 2024 22:31:21 +0000 (14:31 -0800)]
Merge branch 'ps/tests-with-ref-files-backend'
Prepare existing tests on refs to work better with non-default
backends.
* ps/tests-with-ref-files-backend:
t: mark tests regarding git-pack-refs(1) to be backend specific
t5526: break test submodule differently
t1419: mark test suite as files-backend specific
t1302: make tests more robust with new extensions
t1301: mark test for `core.sharedRepository` as reffiles specific
t1300: make tests more robust with non-default ref backends