Recent update to for_each_replace_name() to make it use a strbuf in
place of a fixed buffer forgot to release the memory held by the
strbuf before leaving the function.
Our struct child_process already has its own argv_array.
Let's use that to avoid having to format options into
separate buffers.
Note that we'll need to declare the child process outside of
the run_service_command() helper to do this. But that opens
up a further simplification, which is that the helper can
append to our argument list, saving each caller from
specifying "." manually.
We probe the "17/" loose object directory for auto-gc, and
use a local buffer to format the path. We can just use
git_path() for this. It handles paths of any length
(reducing our error handling). And because we feed the
result straight to a system call, we can just use the static
variant.
Note that git_path also knows the string "objects/" is
special, and will replace it with git_object_directory()
when necessary.
Another alternative would be to use sha1_file_name() for the
pretend object "170000...", but that ends up being more
hassle for no gain, as we have to truncate the final path
component.
transport-helper: replace checked snprintf with xsnprintf
We can use xsnprintf to do our truncation check with less
code. The error message isn't as specific, but the point is
that this isn't supposed to trigger in the first place
(because our buffer is big enough to handle any int).
These calls to snprintf should always succeed, because their
input is small and fixed. Let's use xsnprintf to make sure
this is the case (and to make auditing for actual truncation
easier).
These could be candidates for turning into heap buffers, but
they fall into a few broad categories that make it not worth
doing:
- formatting single numbers is simple enough that we can
see the result should fit
- the size of a sha1 is likewise well-known, and I didn't
want to cause unnecessary conflicts with the ongoing
process to convert these constants to GIT_MAX_HEXSZ
- the interface for curl_errorstr is dictated by curl
replace unchecked snprintf calls with heap buffers
We'd prefer to avoid unchecked snprintf calls because
truncation can lead to unexpected results.
These are all cases where truncation shouldn't ever happen,
because the input to snprintf is fixed in size. That makes
them candidates for xsnprintf(), but it's simpler still to
just use the heap, and then nobody has to wonder if "100" is
big enough.
We'll use xstrfmt() where possible, and a strbuf when we need
the resulting size or to reuse the same buffer in a loop.
receive-pack: print --pack-header directly into argv array
After receive-pack reads the pack header from the client, it
feeds the already-read part to index-pack and unpack-objects
via their --pack-header command-line options. To do so, we
format it into a fixed buffer, then duplicate it into the
child's argv_array.
Our buffer is long enough to handle any possible input, so
this isn't wrong. But it's more complicated than it needs to
be; we can just argv_array_pushf() the final value and avoid
the intermediate copy. This drops the magic number and is
more efficient, too.
Note that we need to push to the argv_array in order, which
means we can't do the push until we are in the "unpack-objects
versus index-pack" conditional. Rather than duplicate the
slightly complicated format specifier, I pushed it into a
helper function.
When name-rev needs to format an actual name, we do so into
a fixed-size buffer. That includes the actual ref tip, as
well as any traversal information. Since refs can exceed
1024 bytes, this means you can get a bogus result. E.g.,
doing:
We generate a reflog message that contains some fixed text
plus a branch name, and use a buffer of size PATH_MAX + 20.
This mostly works if you assume that refnames are shorter
than PATH_MAX, but:
1. That's not necessarily true. PATH_MAX is not always the
filesystem's limit.
2. The "20" is not sufficiently large for the fixed text
anyway.
Let's just switch to a heap buffer so we don't have to even
care.
create_branch: move msg setup closer to point of use
In create_branch() we write the reflog msg into a buffer in
the main function, but then use it only inside a
conditional. If you carefully follow the logic, you can
confirm that we never use the buffer uninitialized nor write
when it would not be used. But we can make this a lot more
obvious by simply moving the write step inside the
conditional.
Like the previous commit, we'd like to avoid the assumption
that refs fit into PATH_MAX-sized buffers. These callsites
have an extra twist, though: they write the refnames using
mksnpath. This does two things beyond a regular snprintf:
1. It quietly writes "/bad-path/" when truncation occurs.
This saves the caller having to check the error code,
but if you aren't actually feeding the result to a
system call (and we aren't here), it's questionable.
2. It calls cleanup_path(), which removes leading
instances of "./". That's questionable when dealing
with refnames, as we could silently canonicalize a
syntactically bogus refname into a valid one.
Let's convert each case to use a strbuf. This is preferable
to xstrfmt() because we can reuse the same buffer as we
loop.
Many functions which handle refs use a PATH_MAX-sized buffer
to do so. This is mostly reasonable as we have to write
loose refs into the filesystem, and at least on Linux the 4K
PATH_MAX is big enough that nobody would care. But:
1. The static PATH_MAX is not always the filesystem limit.
2. On other platforms, PATH_MAX may be much smaller.
3. As we move to alternate ref storage, we won't be bound
by filesystem limits.
Let's convert these to heap buffers so we don't have to
worry about truncation or size limits.
We may want to eventually constrain ref lengths for sanity
and to prevent malicious names, but we should do so
consistently across all platforms, and in a central place
(like the ref code).
Part of the reflog content comes from the environment, which
can be much larger than our fixed buffer. Let's use a heap
buffer so we avoid truncating it.
We format the tag header into a fixed 1024-byte buffer. But
since the tag-name and tagger ident can be arbitrarily
large, we may unceremoniously die with "tag header too big".
Let's just use a strbuf instead.
Note that it looks at first glance like we can just format
this directly into the "buf" strbuf where it will ultimately
go. But that buffer may already contain the tag message, and
we have no easy way to prepend formatted data to a strbuf
(we can only splice in an already-generated buffer). This
isn't a performance-critical path, so going through an extra
buffer isn't a big deal.
To generate a patch id, we format the diff header into a
fixed-size buffer, and then feed the result to our sha1
computation. The fixed buffer has size '4*PATH_MAX + 20',
which in theory accommodates the four filenames plus some
extra data. Except:
1. The filenames may not be constrained to PATH_MAX. The
static value may not be a real limit on the current
filesystem. Moreover, we may compute patch-ids for
names stored only in git, without touching the current
filesystem at all.
2. The 20 bytes is not nearly enough to cover the
extra content we put in the buffer.
As a result, the data we feed to the sha1 computation may be
truncated, and it's possible that a commit with a very long
filename could erroneously collide in the patch-id space
with another commit. For instance, if one commit modified
"really-long-filename/foo" and another modified "bar" in the
same directory.
In practice this is unlikely. Because the filenames are
repeated, and because there's a single cutoff at the end of
the buffer, the offending filename would have to be on the
order of four times larger than PATH_MAX.
We could fix this by moving to a strbuf. However, we can
observe that the purpose of formatting this in the first
place is to feed it to git_SHA1_Update(). So instead, let's
just feed each part of the formatted string directly. This
actually ends up more readable, and we can even factor out
some duplicated bits from the various conditional branches.
Technically this may change the output of patch-id for very
long filenames, but it's not worth making an exception for
this in the --stable output. It was a bug, and one that only
affected an unlikely set of paths. And anyway, the exact
value would have varied from platform to platform depending
on the value of PATH_MAX, so there is no "stable" value.
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Since git_path_buf() is smart enough to replace "objects/"
with the correct object path, we can use it instead of
manually assembling the path. That's slightly shorter, and
will clean up any non-canonical bits in the path.
The odb_mkstemp() function expects the caller to provide a
fixed buffer to write the resulting tempfile name into. But
it creates the template using snprintf without checking the
return value. This means we could silently truncate the
filename.
In practice, it's unlikely that the truncation would end in
the template-pattern that mkstemp needs to open the file. So
we'd probably end up failing either way, unless the path was
specially crafted.
The simplest fix would be to notice the truncation and die.
However, we can observe that most callers immediately
xstrdup() the result anyway. So instead, let's switch to
using a strbuf, which is easier for them (and isn't a big
deal for the other 2 callers, who can just strbuf_release
when they're done with it).
Note that many of the callers used static buffers, but this
was purely to avoid putting a large buffer on the stack. We
never passed the static buffers out of the function, so
there's no complicated memory handling we need to change.
The odb_mkstemp function does not return an error; it dies
on failure instead. But many of its callers compare the
resulting descriptor against -1 and die themselves.
Mostly this is just pointless, but it does raise a question
when looking at the callers: if they show the results of the
"template" buffer after a failure, what's in it? The answer
is: it doesn't matter, because it cannot happen.
So let's make that clear by removing the bogus error checks.
In bitmap_writer_finish(), we can drop the error-handling
code entirely. In the other two cases, it's shared with the
open() in another code path; we can just move the
error-check next to that open() call.
And while we're at it, let's flesh out the function's
docstring a bit to make the error behavior clear.
sha1dc/sha1.c wanted to check the endianness of the target platform
at compilation time and used a CPP macro with a rather overly
generic name, "BIGENDIAN", to pass the result of the check around
in the file. It wasn't prepared for the same macro set to 0
(false) by the platform to signal that the target is _not_ a big
endian box, and assumed that the endianness detection logic it has
alone would be the one that is setting the macro, resulting in a
breakage on Windows. This has been fixed by using a bit less
generic name for the same purpose.
The name-hash used for detecting paths that are different only in
cases (which matter on case insensitive filesystems) has been
optimized to take advantage of multi-threading when it makes sense.
* jh/memihash-opt:
name-hash: add test-lazy-init-name-hash to .gitignore
name-hash: add perf test for lazy_init_name_hash
name-hash: add test-lazy-init-name-hash
name-hash: perf improvement for lazy_init_name_hash
hashmap: document memihash_cont, hashmap_disallow_rehash api
hashmap: add disallow_rehash setting
hashmap: allow memihash computation to be continued
name-hash: specify initial size for istate.dir_hash table
* jk/fast-import-cleanup:
pack.h: define largest possible encoded object size
encode_in_pack_object_header: respect output buffer length
fast-import: use xsnprintf for formatting headers
fast-import: use xsnprintf for writing sha1s
Recent enhancement to "git stash push" command to support pathspec
to allow only a subset of working tree changes to be stashed away
was found to be too chatty and exposed the internal implementation
detail (e.g. when it uses reset to match the index to HEAD before
doing other things, output from reset seeped out). These, and
other chattyness has been fixed.
* tg/stash-push-fixup:
stash: keep untracked files intact in stash -k
stash: pass the pathspec argument to git reset
stash: don't show internal implementation details
"git checkout" is taught the "--recurse-submodules" option.
* sb/checkout-recurse-submodules:
builtin/read-tree: add --recurse-submodules switch
builtin/checkout: add --recurse-submodules switch
entry.c: create submodules when interesting
unpack-trees: check if we can perform the operation for submodules
unpack-trees: pass old oid to verify_clean_submodule
update submodules: add submodule_move_head
submodule.c: get_super_prefix_or_empty
update submodules: move up prepare_submodule_repo_env
submodules: introduce check to see whether to touch a submodule
update submodules: add a config option to determine if submodules are updated
update submodules: add submodule config parsing
make is_submodule_populated gently
lib-submodule-update.sh: define tests for recursing into submodules
lib-submodule-update.sh: replace sha1 by hash
lib-submodule-update: teach test_submodule_content the -C <dir> flag
lib-submodule-update.sh: do not use ./. as submodule remote
lib-submodule-update.sh: reorder create_lib_submodule_repo
submodule--helper.c: remove duplicate code
connect_work_tree_and_git_dir: safely create leading directories
* jk/pack-name-cleanups:
index-pack: make pointer-alias fallbacks safer
replace snprintf with odb_pack_name()
odb_pack_keep(): stop generating keepfile name
sha1_file.c: make pack-name helper globally accessible
move odb_* declarations out of git-compat-util.h
* jk/rev-parse-cleanup:
rev-parse: simplify parsing of ref options
rev-parse: add helper for parsing "--foo/--foo="
rev-parse: use skip_prefix when parsing options
Merge branch 'ew/http-alternates-as-redirects-warning' into maint
Recent versions of Git treats http alternates (used in dumb http
transport) just like HTTP redirects and requires the client to
enable following it, due to security concerns. But we forgot to
give a warning when we decide not to honor the alternates.
* ew/http-alternates-as-redirects-warning:
http: release strbuf on disabled alternates
http: inform about alternates-as-redirects behavior
Merge branch 'dp/filter-branch-prune-empty' into maint
"git filter-branch --prune-empty" drops a single-parent commit that
becomes a no-op, but did not drop a root commit whose tree is empty.
* dp/filter-branch-prune-empty:
p7000: add test for filter-branch with --prune-empty
filter-branch: fix --prune-empty on parentless commits
t7003: ensure --prune-empty removes entire branch when applicable
t7003: ensure --prune-empty can prune root commit
Merge branch 'mm/fetch-show-error-message-on-unadvertised-object' into maint
"git fetch" that requests a commit by object name, when the other
side does not allow such an request, failed without much
explanation.
* mm/fetch-show-error-message-on-unadvertised-object:
fetch-pack: add specific error for fetching an unadvertised object
fetch_refs_via_pack: call report_unmatched_refs
fetch-pack: move code to report unmatched refs to a function
Merge branch 'jk/interpret-branch-name' into maint
"git branch @" created refs/heads/@ as a branch, and in general the
code that handled @{-1} and @{upstream} was a bit too loose in
disambiguating.
* jk/interpret-branch-name:
checkout: restrict @-expansions when finding branch
strbuf_check_ref_format(): expand only local branches
branch: restrict @-expansions when deleting
t3204: test git-branch @-expansion corner cases
interpret_branch_name: allow callers to restrict expansions
strbuf_branchname: add docstring
strbuf_branchname: drop return value
interpret_branch_name: move docstring to header file
interpret_branch_name(): handle auto-namelen for @{-1}
A few tests were run conditionally under (rare) conditions where
they cannot be run (like running cvs tests under 'root' account).
* ab/cond-skip-tests:
gitweb tests: skip tests when we don't have Time::HiRes
gitweb tests: change confusing "skip_all" phrasing
cvs tests: skip tests that call "cvs commit" when running as root
user.email that consists of only cruft chars should consistently
error out, but didn't.
* jk/ident-empty:
ident: do not ignore empty config name/email
ident: reject all-crud ident name
ident: handle NULL email when complaining of empty name
ident: mark error messages for translation
The t/perf performance test suite was not prepared to test not so
old versions of Git, but now it covers versions of Git that are not
so ancient.
* jt/perf-updates:
t/perf: add fallback for pre-bin-wrappers versions of git
t/perf: use $MODERN_GIT for all repo-copying steps
t/perf: export variable used in other blocks
Merge branch 'jk/parse-config-key-cleanup' into maint
The "parse_config_key()" API function has been cleaned up.
* jk/parse-config-key-cleanup:
parse_hide_refs_config: tell parse_config_key we don't want a subsection
parse_config_key: allow matching single-level config
parse_config_key: use skip_prefix instead of starts_with
refs: parse_hide_refs_config to use parse_config_key
"git describe --dirty" dies when it cannot be determined if the
state in the working tree matches that of HEAD (e.g. broken
repository or broken submodule). The command learned a new option
"git describe --broken" to give "$name-broken" (where $name is the
description of HEAD) in such a case.
* sb/describe-broken:
builtin/describe: introduce --broken flag
Recently we started passing the "--push-options" through the
external remote helper interface; now the "smart HTTP" remote
helper understands what to do with the passed information.
* sb/push-options-via-transport:
remote-curl: allow push options
send-pack: send push options correctly in stateless-rpc case
* km/t1400-modernization:
t1400: use test_when_finished for cleanup
t1400: remove a set of unused output files
t1400: use test_path_is_* helpers
t1400: set core.logAllRefUpdates in "logged by touch" tests
t1400: rename test descriptions to be unique
* jk/prefix-filename:
bundle: use prefix_filename with bundle path
prefix_filename: simplify windows #ifdef
prefix_filename: return newly allocated string
prefix_filename: drop length parameter
prefix_filename: move docstring to header file
hash-object: fix buffer reuse with --path in a subdirectory
In an early part of sha1dc/sha1.c, the code checks the endianness of
the target platform by inspecting common CPP macros defined on
big-endian boxes, and sets BIGENDIAN macro to 1. If these common
CPP macros are not defined, the code declares that the target
platform is little endian and does nothing (most notably, it does
not #undef its BIGENDIAN macro).
The code that does so even has this comment
Note that all MSFT platforms are little endian,
so none of these will be defined under the MSC compiler.
and later, the defined-ness of the BIGENDIAN macro is used to switch
the implementation of sha1_load() macro.
One thing the code did not anticipate is that somebody might define
BIGENDIAN macro in some header it includes to 0 on a little-endian
target platform. Because the auto-detection based on common macros
do not touch BIGENDIAN macro when it detects a little-endian target,
such a definition is still valid and then defined-ness test will say
"Ah, BIGENDIAN is defined" and takes the wrong sha1_load().
As this auto-detection logic pretends as if it owns the BIGENDIAN
macro by ignoring the setting that may come from the outside and by
not explicitly unsetting when it decides that it is working for a
little-endian target, solve this problem without breaking that
assumption. Namely, we can rename BIGENDIAN this code uses to
something much less generic, i.e. SHA1DC_BIGENDIAN. For extra
protection, undef the macro on a little-endian target.
It is possible to work it around by instead #undef BIGENDIAN in
the auto-detection code, but a macro (or include) that happens later
in the code can be implemented in terms of BIGENDIAN on Windows and
it is possible that the implementation gets upset when it sees the
CPP macro undef'ed (instead of set to 0). Renaming the private macro
intended to be used only in this file to a less generic name relieves
us from having to worry about that kind of breakage.
Noticed-by: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
The "detect attempt to create collisions" variant of SHA-1
implementation by Marc Stevens (CWI) and Dan Shumow (Microsoft)
has been integrated and made the default.
* jk/sha1dc:
Makefile: make DC_SHA1 the default
t0013: add a basic sha1 collision detection test
Makefile: add DC_SHA1 knob
sha1dc: disable safe_hash feature
sha1dc: adjust header includes for git
sha1dc: add collision-detecting sha1 implementation
The default location "~/.git-credential-cache/socket" for the
socket used to communicate with the credential-cache daemon has
been moved to "~/.cache/git/credential/socket".
* dl/credential-cache-socket-in-xdg-cache:
credential-cache: add tests for XDG functionality
credential-cache: use XDG_CACHE_HOME for socket
path.c: add xdg_cache_home
Merge branch 'jc/config-case-cmdline-take-2' into maint
The code to parse "git -c VAR=VAL cmd" and set configuration
variable for the duration of cmd had two small bugs, which have
been fixed.
This supersedes jc/config-case-cmdline topic that has been discarded.
* jc/config-case-cmdline-take-2:
config: use git_config_parse_key() in git_config_parse_parameter()
config: move a few helper functions up
The code to parse the command line "git grep <patterns>... <rev>
[[--] <pathspec>...]" has been cleaned up, and a handful of bugs
have been fixed (e.g. we used to check "--" if it is a rev).
* jk/grep-no-index-fix:
grep: treat revs the same for --untracked as for --no-index
grep: do not diagnose misspelt revs with --no-index
grep: avoid resolving revision names in --no-index case
grep: fix "--" rev/pathspec disambiguation
grep: re-order rev-parsing loop
grep: do not unnecessarily query repo for "--"
grep: move thread initialization a little lower
Merge branch 'jn/remote-helpers-with-git-dir' into maint
"git ls-remote" and "git archive --remote" are designed to work
without being in a directory under Git's control. However, recent
updates revealed that we randomly look into a directory called
.git/ without actually doing necessary set-up when working in a
repository. Stop doing so.
* jn/remote-helpers-with-git-dir:
remote helpers: avoid blind fall-back to ".git" when setting GIT_DIR
remote: avoid reading $GIT_DIR config in non-repo
Merge branch 'jk/push-deadlock-regression-fix' into maint
"git push" had a handful of codepaths that could lead to a deadlock
when unexpected error happened, which has been fixed.
* jk/push-deadlock-regression-fix:
send-pack: report signal death of pack-objects
send-pack: read "unpack" status even on pack-objects failure
send-pack: improve unpack-status error messages
send-pack: use skip_prefix for parsing unpack status
send-pack: extract parsing of "unpack" response
receive-pack: fix deadlock when we cannot create tmpdir
pack.h: define largest possible encoded object size
Several callers use fixed buffers for storing the pack
object header, and they've picked 10 as a magic number. This
is reasonable, since it handles objects up to 2^67. But
let's give them a constant so it's clear that the number
isn't pulled out of thin air.
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
The encode_in_pack_object_header() writes a variable-length
header to an output buffer, but it doesn't actually know
long the buffer is. At first glance, this looks like it
might be possible to overflow.
In practice, this is probably impossible. The smallest
buffer we use is 10 bytes, which would hold the header for
an object up to 2^67 bytes. Obviously we're not likely to
see such an object, but we might worry that an object could
lie about its size (causing us to overflow before we realize
it does not actually have that many bytes). But the argument
is passed as a uintmax_t. Even on systems that have __int128
available, uintmax_t is typically restricted to 64-bit by
the ABI.
So it's unlikely that a system exists where this could be
exploited. Still, it's easy enough to use a normal out/len
pair and make sure we don't write too far. That protects the
hypothetical 128-bit system, makes it harder for callers to
accidentally specify a too-small buffer, and makes the
resulting code easier to audit.
Note that the one caller in fast-import tried to catch such
a case, but did so _after_ the call (at which point we'd
have already overflowed!). This check can now go away.
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
The stream_blob() function checks the return value of
snprintf and dies. This is more simply done with
xsnprintf (and matches the similar call in store_object).
The message the user would get is less specific, but since
the point is that this _shouldn't_ ever happen, that's OK.
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
When we have to write a sha1 with a newline, we do so by
copying both into a single buffer, so that we can issue a
single write() call.
We use snprintf but don't bother to check the output, since
we know it will fit. However, we should use xsnprintf() in
such a case so that we're notified if our assumption turns
out to be wrong (and to make it easier to audit for
unchecked snprintf calls).
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Map both old addresses to the new, hopefully more permanent one.
Signed-off-by: Michael J Gruber <git@drmicha.warpmail.net> Signed-off-by: Michael J Gruber <git@grubix.eu> Signed-off-by: Junio C Hamano <gitster@pobox.com>
The pager_in_use() function predates git_env_bool(), but
ends up doing the same thing. Let's make use of the latter,
which is shorter and less repetitive.
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Created t/perf/p0004-lazy-init-name-hash.sh test
to demonstrate correctness and performance gains
with the multithreaded version of lazy_init_name_hash().
Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Add t/helper/test-lazy-init-name-hash.c test code
to demonstrate performance times for lazy_init_name_hash()
using the original single-threaded and the new multi-threaded
code paths.
Includes a --dump option to dump the created hashmaps to
stdout. You can use this to run both code paths and
confirm that they generate the same hashmaps.
Includes a --analyze option to analyze performance of both
code paths over a range of index sizes to help you find a
lower bound for the LAZY_THREAD_COST in name-hash.c.
For example, passing "-a 4000" will set "istate.cache_nr"
to 4000 and then try the multi-threaded code -- probably
giving 2 threads with 2000 entries each. It will then
run both the single-threaded (1x4000) and the multi-threaded
(2x2000) and compare the times. It will then repeat the
test with 8000, 12000, and etc. so that you can see the
cross over.
Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
name-hash: perf improvement for lazy_init_name_hash
Improve performance of lazy_init_name_hash() when
ignore_case is set. Teach name-hash to build the
istate.name_hash and istate.dir_hash simultaneously
using a forward-diving technique on the pathname
of the index_entry, rather than adding name_hash
entries and then searching backwards in the pathname
for parent directories.
This borrows algorithm ideas from clear_ce_flags_{1,dir}.
Multiple threads are used with the new algorithm to
speed hashmap construction.
This new code path is only used when threads are present
(a compiler settings) and when the index is large enough
to warrant the pthread complexity.
The code in clear_ce_flags_dir() uses a linear search to
find the adjacent index entries with the same prefix; a
binary search is used here handle_range_dir() to further
speed things up.
The size of LAZY_THREAD_COST was determined from rough
analysis using:
t/helper/test-lazy-init-name-hash --analyze
Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>