untracked cache: record .gitignore information and dir hierarchy

The idea is if we can capture all input and output of
read_directory_recursive() and verify at a later time that all the
input is the same, then read_directory_recursive() should produce the
same output, so we can bypass read_directory_recursive() and reuse the
cached output for the directory in question (the bypass code needs to
verify subdirectories separately)

The list of input of read_directory_recursive() is in the big comment
block in dir.h. This cache focuses on only untracked files as the
output from r_d_r(), not ignored files because the number of tracked
files is usually small, so small cache overhead, while the number of
ignored files could go really high (e.g. *.o files mixing with source
code).

This patch captures .gitignore information, check_only bit and the
list of directories that read_directory_recursive() examines.

Two hash_sha1_file() are required for $GIT_DIR/info/exclude and
core.excludesfile unless their stat data matches. hash_sha1_file() is
only needed when .gitignore files in the worktree are modified,
otherwise their SHA-1 in index is used.

We could store stat data for .gitignore files so we don't have to
rehash them if their content is different from index, but I think
.gitignore files are rarely modified, so not worth extra cache data
(and hashing penalty read-cache.c:verify_hdr(), as we will be storing
this as an index extension).

This means if you change .gitignore at root directory, you better add
it to the index soon or you lose all the benefit of untracked cache (a
change at root .gitignore invalidates everything) and pay the cache
overhead for nothing.
untracked cache: initial untracked cache validation
untracked cache: invalidate dirs recursively if .gitignore changes

It's easy to see that if an existing .gitignore changes, its SHA-1
would be different and invalidate_gitignore() is called.

If .gitignore is removed, add_excludes() will treat it like an empty
.gitignore, which again should invalidate the cached directory data.

if .gitignore is added, lookup_untracked() already fills initial
.gitignore SHA-1 as "empty file", so again invalidate_gitignore() is
called.
untracked cache: record/validate dir mtime and reuse cached output

The main readdir loop in read_directory_recursive() is replaced with a
new one that checks if cached results of a directory is still valid.

If a file is added or removed from the index, the containing directory
is invalidated (but not its subdirs). If directory's mtime is changed,
the same happens. If a .gitignore is updated, the containing directory
and all subdirs are invalidated recursively. If dir_struct#flags or
other conditions change, the cache is ignored.

If a directory is invalidated, we opendir/readdir/closedir and run the
exclude machinery on that directory listing as usual. If untracked
cache is also enabled, we'll update the cache along the way. If a
directory is validated, we simply pull the untracked listing out from
the cache. The cache also records the list of direct subdirs that we
have to recurse in. Fully excluded directories are seen as "untracked
files".

In the best case when no dirs are invalidated, read_directory()
becomes a series of stat(dir), open(.gitignore), fstat, read, close
and optionally hash_sha1_file. For comparison, standard
read_directory() is a sequence of opendir, readdir, open(gitignore),
fstat, read, close, (expensive) last_exclude_matching and closedir.

We already try not to open(gitignore) if we know it does not exist, so
open/fstat/read/close sequence does not apply to every directory. The
sequence could be reduced further, as noted in prep_exclude(). So in
theory, the entire best-case read_directory sequence could be reduced
to a series of stat() and nothing else.

This is not a silver bullet approach. When you compile a C file, for
example, the old .o file is removed and a new one with the same name
created, effectively invalidating the containing directory's cache
(but not its subdirectories). If your build process touches every
directory, this cache adds extra overhead for nothing, so it's a good
idea to separate generated files from tracked files.. Editors may use
the same strategy for saving files. And of course you're out of luck
running your repo on an unsupported filesytem and/or operating system.
untracked cache: mark what dirs should be recursed/saved

When we invalidate a cached directory, read_directory_recursive() will
be called again and it will decide what directories to recurse in,
which may not be the same as recorded in the cache.

Mark this "recurse" status for each directory, clear them at
invalidation time and set them again inside r_d_r(). Only dirs with
"recurse" bit set will need to be examined at the next run and be
stored on disk later. Note that we do not invalidate subdirs because
they may be still good for use.
untracked cache: don't open non-existent .gitignore

This cuts down a signficant number of open(.gitignore) because most
directories usually don't have .gitignore files.
untracked cache: save to an index extension

FIXME: save check_only
untracked cache: load from UNTR index extension

FIXME: load check_only
status: support untracked cache
update-index: manually enable or disable untracked cache

Some numbers below. In short, the saving on wt_status_collect_untracked()
is about 80%. There are some overhead on read/write_cache, but it seems
lower than 50ms, while the .._untracked() saving is in the 500ms range
(except linux-2.6, about 150ms). "git status" time saving ranges from
33% to 42%.

On gentoo-x86.git (100k files, 23k dirs, quite balance
tree, 8.5MB index v4, cache-tree fully populated), before turning
untracked cache on (the most important line is wt_status_collect:625)

   184.650 gitmodules_config:201 if (read_cache() < 0) die("index
     0.004 cmd_status:1299 read_cache_preload(&s.pathspec)
   226.231 cmd_status:1300 refresh_index(&the_index, REFRESH_QUIET
     3.096 cmd_status:1304 update_index_if_able(&the_index, &index_lock)
     6.788  wt_status_collect:619 wt_status_collect_changes_worktree(s)
     6.780  wt_status_collect:624 wt_status_collect_changes_index(s)
   772.866  wt_status_collect:625 wt_status_collect_untracked(s)
   786.686 cmd_status:1308 wt_status_collect(&s)

real    0m1.211s
user    0m0.566s
sys     0m0.638s

and after (saving 42% total time):

   220.888 gitmodules_config:201 if (read_cache() < 0) die("index
    36.368 cmd_status:1299 read_cache_preload(&s.pathspec)
   223.936 cmd_status:1300 refresh_index(&the_index, REFRESH_QUIET
     2.935 cmd_status:1304 update_index_if_able(&the_index, &index_lock)
     7.031  wt_status_collect:619 wt_status_collect_changes_worktree(s)
     7.156  wt_status_collect:624 wt_status_collect_changes_index(s)
   148.022  wt_status_collect:625 wt_status_collect_untracked(s)
   162.443 cmd_status:1308 wt_status_collect(&s)
    36.943 cmd_status:1348 if (the_index.untracked) { struct

real    0m0.696s
user    0m0.406s
sys     0m0.288s

On webkit.git (182k files, 6k dirs, 14M index v4), before:

   283.182 gitmodules_config:201 if (read_cache() < 0) die("index
     0.004 cmd_status:1299 read_cache_preload(&s.pathspec)
   515.836 cmd_status:1300 refresh_index(&the_index, REFRESH_QUIET
     5.428 cmd_status:1304 update_index_if_able(&the_index, &index_lock)
    11.162  wt_status_collect:619 wt_status_collect_changes_worktree(s)
    11.068  wt_status_collect:624 wt_status_collect_changes_index(s)
   887.247  wt_status_collect:625 wt_status_collect_untracked(s)
   909.722 cmd_status:1308 wt_status_collect(&s)

real    0m1.729s
user    0m0.785s
sys     0m0.941s

and after (saving 38% total time):

   290.994 gitmodules_config:201 if (read_cache() < 0) die("index
    10.132 cmd_status:1299 read_cache_preload(&s.pathspec)
   516.656 cmd_status:1300 refresh_index(&the_index, REFRESH_QUIET
     5.159 cmd_status:1304 update_index_if_able(&the_index, &index_lock)
    12.605  wt_status_collect:619 wt_status_collect_changes_worktree(s)
    11.262  wt_status_collect:624 wt_status_collect_changes_index(s)
   186.032  wt_status_collect:625 wt_status_collect_untracked(s)
   210.134 cmd_status:1308 wt_status_collect(&s)
    12.332 cmd_status:1348 if (the_index.untracked) { struct index_state

real    0m1.058s
user    0m0.525s
sys     0m0.532s

And linux-2.6 (45k files, 3k dirs, 3.2MB index v4), before:

    68.668 gitmodules_config:201 if (read_cache() < 0) die("index
     0.004 cmd_status:1299 read_cache_preload(&s.pathspec)
   114.270 cmd_status:1300 refresh_index(&the_index, REFRESH_QUIET
     1.180 cmd_status:1304 update_index_if_able(&the_index, &index_lock)
     4.027  wt_status_collect:619 wt_status_collect_changes_worktree(s)
     4.265  wt_status_collect:624 wt_status_collect_changes_index(s)
   191.285  wt_status_collect:625 wt_status_collect_untracked(s)
   199.825 cmd_status:1308 wt_status_collect(&s)

real    0m0.392s
user    0m0.177s
sys     0m0.215s

and after (saving 33%):

    71.756 gitmodules_config:201 if (read_cache() < 0) die("index
     5.201 cmd_status:1299 read_cache_preload(&s.pathspec)
   111.064 cmd_status:1300 refresh_index(&the_index, REFRESH_QUIET
     1.171 cmd_status:1304 update_index_if_able(&the_index, &index_lock)
     3.054  wt_status_collect:619 wt_status_collect_changes_worktree(s)
     4.945  wt_status_collect:624 wt_status_collect_changes_index(s)
    27.203  wt_status_collect:625 wt_status_collect_untracked(s)
    35.475 cmd_status:1308 wt_status_collect(&s)
    25.759 cmd_status:1348 if (the_index.untracked) { struct index_state

real    0m0.259s
user    0m0.106s
sys     0m0.132s
update-index: test the system before enabling untracked cache
t7063: tests for untracked cache
1
Add TIME() macro for measuring how long a block is executed

Convenient macro to measure how long a code block takes. Support
nested timing. _Not_ meant to be actually used in official code.
time
FIXME