We already have tests for the basic parallel-checkout operations. But
this code can also run in other commands, such as git-read-tree and
git-sparse-checkout, which are currently not tested with multiple
workers. To promote a wider test coverage without duplicating tests:

1. Add the GIT_TEST_CHECKOUT_WORKERS environment variable, to optionally
   force parallel-checkout execution during the whole test suite.

2. Include this variable in the second test round of the linux-gcc job
   of our ci scripts. This round runs `make test` again with some
   optional GIT_TEST_* variables enabled, so there is no additional
   overhead in exercising the parallel-checkout code here.

Note: the specific parallel-checkout tests t208* cannot be used in
combination with GIT_TEST_CHECKOUT_WORKERS as they need to set and check
the number of workers by themselves. So skip those tests when this flag
is set.
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Add tests to confirm that `struct conv_attrs` data is correctly passed
from the main process to the workers, and that they properly smudge
files before writing to the working tree. Also check that
non-parallel-eligible entries, such as regular files that require
external filters, are correctly smudge and written when
parallel-checkout is enabled.

Note: to avoid repeating code, some helper functions are extracted from
t0028 into a common lib file.
Original-patch-by: NJeff Hostetler <jeffhost@microsoft.com>
Signed-off-by: NJeff Hostetler <jeffhost@microsoft.com>
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Add tests to confirm that path collisions are properly reported during a
clone operation using parallel-checkout.
Original-patch-by: NJeff Hostetler <jeffhost@microsoft.com>
Signed-off-by: NJeff Hostetler <jeffhost@microsoft.com>
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Add tests to populate the working tree during clone and checkout using
the sequential and parallel modes, to confirm that they produce
identical results. Also test basic checkout mechanics, such as checking
for symlinks in the leading directories and the abidance to --force.

Note: some helper functions are added to a common lib file which is only
included by t2080 for now. But it will also be used by another
parallel-checkout test in a following patch.
Original-patch-by: NJeff Hostetler <jeffhost@microsoft.com>
Signed-off-by: NJeff Hostetler <jeffhost@microsoft.com>
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

There is one code path in builtin/checkout.c which still doesn't benefit
from parallel checkout because it calls checkout_entry() directly,
instead of unpack_trees(). Let's add parallel support for this missing
spot as well. Note: the transient cache entries allocated in
checkout_merged() are now allocated in a mem_pool which is only
discarded after parallel checkout finishes. This is done because the
entries need to be valid when run_parallel_checkout() is called.
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Allow make_transient_cache_entry() to optionally receive a mem_pool
struct in which it should allocate the entry. This will be used in the
following patch, to store some transient entries which should persist
until parallel checkout finishes.
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Original-patch-by: NNguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: NNguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Use multiple worker processes to distribute the queued entries and call
write_checkout_item() in parallel for them. The items are distributed
uniformly in contiguous chunks. This minimizes the chances of two
workers writing to the same directory simultaneously, which could
affect performance due to lock contention in the kernel. Work stealing
(or any other format of re-distribution) is not implemented yet.

The parallel version was benchmarked during three operations in the
linux repo, with cold cache: cloning v5.8, checking out v5.8 from
v2.6.15 (checkout I) and checking out v5.8 from v5.7 (checkout II). The
four tables below show the mean run times and standard deviations for
5 runs in: a local file system with SSD, a local file system with HDD, a
Linux NFS server, and Amazon EFS. The numbers of workers were chosen
based on what produces the best result for each case.

Local SSD:

            Clone                  Checkout I             Checkout II
Sequential  8.171 s ± 0.206 s      8.735 s ± 0.230 s      4.166 s ± 0.246 s
10 workers  3.277 s ± 0.138 s      3.774 s ± 0.188 s      2.561 s ± 0.120 s
Speedup     2.49 ± 0.12            2.31 ± 0.13            1.63 ± 0.12

Local HDD:

            Clone                  Checkout I             Checkout II
Sequential  35.157 s ± 0.205 s     48.835 s ± 0.407 s     47.302 s ± 1.435 s
8 workers   35.538 s ± 0.325 s     49.353 s ± 0.826 s     48.919 s ± 0.416 s
Speedup     0.99 ± 0.01            0.99 ± 0.02            0.97 ± 0.03

Linux NFS server (v4.1, on EBS, single availability zone):

            Clone                  Checkout I             Checkout II
Sequential  216.070 s ± 3.611 s    211.169 s ± 3.147 s    57.446 s ± 1.301 s
32 workers  67.997 s ± 0.740 s     66.563 s ± 0.457 s     23.708 s ± 0.622 s
Speedup     3.18 ± 0.06            3.17 ± 0.05            2.42 ± 0.08

EFS (v4.1, replicated over multiple availability zones):

            Clone                  Checkout I             Checkout II
Sequential  1249.329 s ± 13.857 s  1438.979 s ± 78.792 s  543.919 s ± 18.745 s
64 workers  225.864 s ± 12.433 s   316.345 s ± 1.887 s    183.648 s ± 10.095 s
Speedup     5.53 ± 0.31            4.55 ± 0.25            2.96 ± 0.19

The above benchmarks show that parallel checkout is most effective on
repositories located on an SSD or over a distributed file system. For
local file systems on spinning disks, and/or older machines, the
parallelism does not always bring a good performance. In fact, it can
even increase the run time. For this reason, the sequential code is
still the default. Two settings are added to optionally enable and
configure the new parallel version as desired.

Local SSD tests were executed in an i7-7700HQ (4 cores with
hyper-threading) running Manjaro Linux. Local HDD tests were executed in
an i7-2600 (also 4 cores with hyper-threading), HDD Seagate Barracuda
7200 rpm SATA 3.0, running Debian 9.13. NFS and EFS tests were
executed in an Amazon EC2 c5n.large instance, with 2 vCPUs. The Linux
NFS server was running on a m6g.large instance with 1 TB, EBS GP2
volume. Before each timing, the linux repository was removed (or checked
out back), and `sync && sysctl vm.drop_caches=3` was executed.
Co-authored-by: NNguyễn Thái Ngọc Duy <pclouds@gmail.com>
Co-authored-by: NJeff Hostetler <jeffhost@microsoft.com>
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This new interface allows us to enqueue some of the entries being
checked out to later call write_entry() for them in parallel. For now,
the parallel checkout machinery is enabled by default and there is no
user configuration, but run_parallel_checkout() just writes the queued
entries in sequence (without spawning additional workers). The next
patch will actually implement the parallelism and, later, we will make
it configurable.

When there are path collisions among the entries being written (which
can happen e.g. with case-sensitive files in case-insensitive file
systems), the parallel checkout code detects the problem and marks the
item with PC_ITEM_COLLIDED. Later, these items are sequentially fed to
checkout_entry() again. This is similar to the way the sequential code
deals with collisions, overwriting the previously checked out entries
with the subsequent ones. The only difference is that, when we start
writing the entries in parallel, we won't be able to determine which of
the colliding entries will survive on disk (for the sequential
algorithm, it is always the last one).

I also experimented with the idea of not overwriting colliding entries,
and it seemed to work well in my simple tests. However, because just one
entry of each colliding group would be actually written, the others
would have null lstat() fields on the index. This might not be a problem
by itself, but it could cause performance penalties for subsequent
commands that need to refresh the index: when the st_size value cached
is 0, read-cache.c:ie_modified() will go to the filesystem to see if the
contents match. As mentioned in the function:

    * Immediately after read-tree or update-index --cacheinfo,
    * the length field is zero, as we have never even read the
    * lstat(2) information once, and we cannot trust DATA_CHANGED
    * returned by ie_match_stat() which in turn was returned by
    * ce_match_stat_basic() to signal that the filesize of the
    * blob changed.  We have to actually go to the filesystem to
    * see if the contents match, and if so, should answer "unchanged".

So, if we have N entries in a colliding group and we decide to write and
lstat() only one of them, every subsequent git-status will have to read,
convert, and hash the written file N - 1 times, to check that the N - 1
unwritten entries are dirty. By checking out all colliding entries (like
the sequential code does), we only pay the overhead once.
Co-authored-by: NNguyễn Thái Ngọc Duy <pclouds@gmail.com>
Co-authored-by: NJeff Hostetler <jeffhost@microsoft.com>
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The parallel checkout machinery will call checkout_entry() for entries
that could not be written in parallel due to path collisions. At this
point, we will already be holding the conversion attributes for each
entry, and it would be wasteful to let checkout_entry() load these
again. Instead, let's add the checkout_entry_ca() variant, which
optionally takes a preloaded conv_attrs struct.
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

In a following patch, checkout_entry() will use conv_attrs to decide
whether an entry should be enqueued for parallel checkout or not. But
the attributes lookup only happens lower in this call stack. To avoid
the unnecessary work of loading the attributes twice, let's move it up
to checkout_entry(), and pass the loaded struct down to write_entry().
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This code will be used by the parallel checkout functions, outside
entry.c, so extract it to a public function.
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

These two functions will be used by the parallel checkout code, so let's
make them public. Note: fstat_output() is renamed to
fstat_checkout_output(), now that it has become public, seeking to avoid
future name collisions.
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The declarations of entry.c's public functions and structures currently
reside in cache.h. Although not many, they contribute to the size of
cache.h and, when changed, cause the unnecessary recompilation of
modules that don't really use these functions. So let's move them to a
new entry.h header.
Original-patch-by: NNguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: NNguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Create `enum conv_attrs_classification` to express the different ways
that attributes are handled for a blob during checkout.

This will be used in a later commit when deciding whether to add a file
to the parallel or delayed queue during checkout. For now, we can also
use it in get_stream_filter_ca() to simplify the function (as the
classifying logic is the same).
Signed-off-by: NJeff Hostetler <jeffhost@microsoft.com>
[matheus.bernardino: use classification in get_stream_filter_ca()]
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Like the previous patch, we will also need to call get_stream_filter()
with a precomputed `struct conv_attrs`, when we add support for parallel
checkout workers. So add the _ca() variant which takes the conversion
attributes struct as a parameter.
Signed-off-by: NJeff Hostetler <jeffhost@microsoft.com>
[matheus.bernardino: move header comment to ca() variant and reword msg]
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Separate the attribute gathering from the actual conversion by adding
_ca() variants of the conversion functions. These variants receive a
precomputed 'struct conv_attrs', not relying, thus, on a index state.
They will be used in a future patch adding parallel checkout support,
for two reasons:

- We will already load the conversion attributes in checkout_entry(),
  before conversion, to decide whether a path is eligible for parallel
  checkout. Therefore, it would be wasteful to load them again later,
  for the actual conversion.

- The parallel workers will be responsible for reading, converting and
  writing blobs to the working tree. They won't have access to the main
  process' index state, so they cannot load the attributes. Instead,
  they will receive the preloaded ones and call the _ca() variant of
  the conversion functions. Furthermore, the attributes machinery is
  optimized to handle paths in sequential order, so it's better to leave
  it for the main process, anyway.
Signed-off-by: NJeff Hostetler <jeffhost@microsoft.com>
[matheus.bernardino: squash, remove one function definition and reword]
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Move convert_attrs() declaration from convert.c to convert.h, together
with the conv_attrs struct and the crlf_action enum. This function and
the data structures will be used outside convert.c in the upcoming
parallel checkout implementation.
Signed-off-by: NJeff Hostetler <jeffhost@microsoft.com>
[matheus.bernardino: squash and reword msg]
Signed-off-by: NMatheus Tavares <matheus.bernardino@usp.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Signed-off-by: NJunio C Hamano <gitster@pobox.com>

"git fetch --all --ipv4/--ipv6" forgot to pass the protocol options
to instances of the "git fetch" that talk to individual remotes,
which has been corrected.

* ar/fetch-ipversion-in-all:
  fetch: pass --ipv4 and --ipv6 options to sub-fetches

Update to command line completion (in contrib/)

* dl/complete-format-patch-recent-features:
  contrib/completion: complete options that take refs for format-patch

"git remote set-head" that failed still said something that hints
the operation went through, which was misleading.

* cs/don-t-pretend-a-failed-remote-set-head-succeeded:
  remote: don't show success message when set-head fails

There is a logic to estimate how many objects are in the
repository, which is mean to run once per process invocation, but
it ran every time the estimated value was requested.

* jk/dont-count-existing-objects-twice:
  packfile: actually set approximate_object_count_valid

"git for-each-ref" and friends that list refs used to allow only
one --merged or --no-merged to filter them; they learned to take
combination of both kind of filtering.

* al/ref-filter-merged-and-no-merged:
  Doc: prefer more specific file name
  ref-filter: make internal reachable-filter API more precise
  ref-filter: allow merged and no-merged filters
  Doc: cover multiple contains/no-contains filters
  t3201: test multiple branch filter combinations

Doc update.

* cd/commit-graph-doc:
  commit-graph-format.txt: fix no-parent value

Portability tweak for some shell scripts used while building.

* kk/build-portability-fix:
  Fit to Plan 9's ANSI/POSIX compatibility layer

The 'meld' backend of the "git mergetool" learned to give the
underlying 'meld' the '--auto-merge' option, which would help
reduce the amount of text that requires manual merging.

* ls/mergetool-meld-auto-merge:
  mergetool: allow auto-merge for meld to follow the vim-diff behavior

"add -p" now allows editing paths that were only added in intent.

* pw/add-p-edit-ita-path:
  add -p: fix editing of intent-to-add paths

Developer support.

* hn/refs-trace-backend:
  refs: add GIT_TRACE_REFS debugging mechanism

"git index-pack" learned to resolve deltified objects with greater
parallelism.

* jt/threaded-index-pack:
  index-pack: make quantum of work smaller
  index-pack: make resolve_delta() assume base data
  index-pack: calculate {ref,ofs}_{first,last} early
  index-pack: remove redundant child field
  index-pack: unify threaded and unthreaded code
  index-pack: remove redundant parameter
  Documentation: deltaBaseCacheLimit is per-thread

"format-patch --range-diff=<prev> <origin>..HEAD" has been taught
not to ignore <origin> when <prev> is a single version.

* es/format-patch-interdiff-cleanup:
  format-patch: use 'origin' as start of current-series-range when known
  diff-lib: tighten show_interdiff()'s interface
  diff: move show_interdiff() from its own file to diff-lib

Optimization around submodule handling.

* os/fetch-submodule-optim:
  fetch: do not look for submodule changes in unchanged refs

Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Unlike "git config --local", "git config --worktree" did not fail
early and cleanly when started outside a git repository.

* mt/config-fail-nongit-early:
  config: complain about --worktree outside of a git repo

Allow maintainers to tweak $(TAR) invocations done while making
distribution tarballs.

* jc/dist-tarball-tweak:
  Makefile: allow extra tweaking of distribution tarball

"git diff/show" on a change that involves a submodule used to read
the information on commits in the submodule from a wrong repository
and gave a wrong information when the commit-graph is involved.

* mf/submodule-summary-with-correct-repository:
  submodule: use submodule repository when preparing summary
  revision: use repository from rev_info when parsing commits

"git status --short" quoted a path with SP in it when tracked, but
not those that are untracked, ignored or unmerged.  They are all
shown quoted consistently.

* jc/quote-path-cleanup:
  quote: turn 'nodq' parameter into a set of flags
  quote: rename misnamed sq_lookup[] to cq_lookup[]
  wt-status: consistently quote paths in "status --short" output
  quote_path: code clarification
  quote_path: optionally allow quoting a path with SP in it
  quote_path: give flags parameter to quote_path()
  quote_path: rename quote_path_relative() to quote_path()

Optimization around submodule handling.

* os/collect-changed-submodules-optim:
  submodule: suppress checking for file name and ref ambiguity for object ids

"git worktree add" learns that the "-d" is a synonym to "--detach"
option to create a new worktree without being on a branch.

* es/wt-add-detach:
  git-worktree.txt: discuss branch-based vs. throwaway worktrees
  worktree: teach `add` to recognize -d as shorthand for --detach
  git-checkout.txt: document -d short option for --detach