[PATCH v2 0/6] Avoid multiple recursive calls for same path in read_directory_recursive()

From: "Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: "Martin Melka" <martin.melka@gmail.com>,
	"SZEDER Gábor" <szeder.dev@gmail.com>,
	"Samuel Lijin" <sxlijin@gmail.com>,
	"Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>,
	"Derrick Stolee" <stolee@gmail.com>,
	"Elijah Newren" <newren@gmail.com>
Subject: [PATCH v2 0/6] Avoid multiple recursive calls for same path in read_directory_recursive()
Date: Fri, 31 Jan 2020 18:31:20 +0000	[thread overview]
Message-ID: <pull.700.v2.git.git.1580495486.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.700.git.git.1580335424.gitgitgadget@gmail.com>

This patch series builds on en/fill-directory-fixes-more. This series should
be considered an RFC because of the untracked-cache changes (see the last
two commits), for which I'm hoping to get an untracked-cache expert to
comment. This series does provide some modest speedups (see second to last
commit message), and should allow 'git status --ignored' to complete in a
more reasonable timeframe for Martin Melka (see 
https://lore.kernel.org/git/CANt4O2L_DZnMqVxZzTBMvr=BTWqB6L0uyORkoN_yMHLmUX7yHw@mail.gmail.com/
)

Changes since v1:

 * Replaced patch 4 with improved version from Stolee (with additional
   improvement of my own)
 * Clarifications, wording fixes, and more about linear perf in commit
   message to patch 5
 * More detail in patch 5 about why "whackamole" particularly makes me
   uneasy for dir.c

Stuff clearly still missing from v2:

 * I didn't make the DIR_KEEP_UNTRACKED_CONTENTS changes I mentioned in 
   https://lore.kernel.org/git/CABPp-BEQ5s=+6Rnb-A+pdEaoPXxfo-hMSegSe1eai=RE74A3Og@mail.gmail.com/ 
   which I think would make the code cleaner & clearer.
 * I still have not addressed the untracked-cache issue mentioned in the
   last two commits. I looked at it very, very briefly, but I was really
   close to doing something similar to [1] and just dropping my patches in
   this series before even submitting them on Wednesday[2] (dir.c is a
   really unpleasant to work in). Other than wording fixes, I just need a
   week or two off from this area before I dig further, unless someone else
   wants to dive in and needs me to provide pointers on what I've done so
   far.

[1] 
https://lore.kernel.org/git/pull.676.v3.git.git.1576571586.gitgitgadget@gmail.com/
[2] I was inches from doing that Wednesday morning. I had done several
rounds of "Okay, I fixed all the tests that broke with my changes last time,
let's re-run the testsuite -- wow, four totally different tests from
testfiles I hadn't looked at before now break", and decided that I would
only do one more before dropping it an maybe coming back in a month or two.
That time happened to work, minus the untracked-cache, so I decided to put
it in front of other eyeballs.

Derrick Stolee (1):
  dir: refactor treat_directory to clarify control flow

Elijah Newren (5):
  dir: consolidate treat_path() and treat_one_path()
  dir: fix broken comment
  dir: fix confusion based on variable tense
  dir: replace exponential algorithm with a linear one
  t7063: blindly accept diffs

 dir.c                             | 331 +++++++++++++++++-------------
 t/t7063-status-untracked-cache.sh |  50 ++---
 2 files changed, 208 insertions(+), 173 deletions(-)

base-commit: 0cbb60574e741e8255ba457606c4c90898cfc755
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-700%2Fnewren%2Ffill-directory-exponential-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-700/newren/fill-directory-exponential-v2
Pull-Request: https://github.com/git/git/pull/700

Range-diff vs v1:

 1:  27bc135796 = 1:  27bc135796 dir: consolidate treat_path() and treat_one_path()
 2:  2ceb64ae61 = 2:  2ceb64ae61 dir: fix broken comment
 3:  e6d21228d1 = 3:  e6d21228d1 dir: fix confusion based on variable tense
 4:  3b2ec5eaf6 ! 4:  f73f0d66d1 dir: move setting of nested_repo next to its actual usage
     @@ -1,26 +1,73 @@
     -Author: Elijah Newren <newren@gmail.com>
     +Author: Derrick Stolee <dstolee@microsoft.com>

     -    dir: move setting of nested_repo next to its actual usage
     +    dir: refactor treat_directory to clarify control flow

     +    The logic in treat_directory() is handled by a multi-case
     +    switch statement, but this switch is very asymmetrical, as
     +    the first two cases are simple but the third is more
     +    complicated than the rest of the method. In fact, the third
     +    case includes a "break" statement that leads to the block
     +    of code outside the switch statement. That is the only way
     +    to reach that block, as the switch handles all possible
     +    values from directory_exists_in_index();
     +
     +    Extract the switch statement into a series of "if" statements.
     +    This simplifies the trivial cases, while clarifying how to
     +    reach the "show_other_directories" case. This is particularly
     +    important as the "show_other_directories" case will expand
     +    in a later change.
     +
     +    Helped-by: Elijah Newren <newren@gmail.com>
     +    Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
          Signed-off-by: Elijah Newren <newren@gmail.com>

       diff --git a/dir.c b/dir.c
       --- a/dir.c
       +++ b/dir.c
      @@
     - 	const char *dirname, int len, int baselen, int excluded,
       	const struct pathspec *pathspec)
       {
     --	int nested_repo = 0;
     -+	int nested_repo;
     - 
     + 	int nested_repo = 0;
     +-
       	/* The "len-1" is to strip the final '/' */
     - 	switch (directory_exists_in_index(istate, dirname, len-1)) {
     -@@
     +-	switch (directory_exists_in_index(istate, dirname, len-1)) {
     +-	case index_directory:
     +-		return path_recurse;
     ++	enum exist_status status = directory_exists_in_index(istate, dirname, len-1);
     + 
     +-	case index_gitdir:
     ++	if (status == index_directory)
     ++		return path_recurse;
     ++	if (status == index_gitdir)
       		return path_none;
     ++	if (status != index_nonexistent)
     ++		BUG("Unhandled value for directory_exists_in_index: %d\n", status);
     + 
     +-	case index_nonexistent:
     +-		if ((dir->flags & DIR_SKIP_NESTED_GIT) ||
     +-		    !(dir->flags & DIR_NO_GITLINKS)) {
     +-			struct strbuf sb = STRBUF_INIT;
     +-			strbuf_addstr(&sb, dirname);
     +-			nested_repo = is_nonbare_repository_dir(&sb);
     +-			strbuf_release(&sb);
     +-		}
     +-		if (nested_repo)
     +-			return ((dir->flags & DIR_SKIP_NESTED_GIT) ? path_none :
     +-				(excluded ? path_excluded : path_untracked));
     ++	if ((dir->flags & DIR_SKIP_NESTED_GIT) ||
     ++		!(dir->flags & DIR_NO_GITLINKS)) {
     ++		struct strbuf sb = STRBUF_INIT;
     ++		strbuf_addstr(&sb, dirname);
     ++		nested_repo = is_nonbare_repository_dir(&sb);
     ++		strbuf_release(&sb);
     ++	}
     ++	if (nested_repo)
     ++		return ((dir->flags & DIR_SKIP_NESTED_GIT) ? path_none :
     ++			(excluded ? path_excluded : path_untracked));

     - 	case index_nonexistent:
     -+		nested_repo = 0;
     - 		if ((dir->flags & DIR_SKIP_NESTED_GIT) ||
     - 		    !(dir->flags & DIR_NO_GITLINKS)) {
     - 			struct strbuf sb = STRBUF_INIT;
     +-		if (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)
     +-			break;
     ++	if (!(dir->flags & DIR_SHOW_OTHER_DIRECTORIES)) {
     + 		if (excluded &&
     + 		    (dir->flags & DIR_SHOW_IGNORED_TOO) &&
     + 		    (dir->flags & DIR_SHOW_IGNORED_TOO_MODE_MATCHING)) {
 5:  40b378e7ad ! 5:  d3136ef52f dir: replace exponential algorithm with a linear one
     @@ -20,26 +20,29 @@
               and report all the ignored entries and then report the directory as
               untracked -- UNLESS all the entries under the directory are
               ignored, in which case we don't print any of the entries under the
     -         directory and just report the directory itself as ignored.
     +         directory and just report the directory itself as ignored.  (Note
     +         that although this forces us to walk all untracked files underneath
     +         the directory as well, we strip them from the output, except for
     +         users like 'git clean' who also set DIR_KEEP_TRACKED_CONTENTS.)

             * For 'git clean', we may need to recurse into a directory that
               doesn't match any specified pathspecs, if it's possible that there
               is an entry underneath the directory that can match one of the
               pathspecs.  In such a case, we need to be careful to omit the
     -         directory itself from the list of paths (see e.g. commit
     -         404ebceda01c ("dir: also check directories for matching pathspecs",
     -         2019-09-17))
     +         directory itself from the list of paths (see commit 404ebceda01c
     +         ("dir: also check directories for matching pathspecs", 2019-09-17))

          Part of the tension noted above is that the treatment of a directory can
     -    changed based on the files within it, and based on the various settings
     +    change based on the files within it, and based on the various settings
          in dir->flags.  Trying to keep this in mind while reading over the code,
     -    it is easy to (accidentally?) think in terms of "treat_directory() tells
     -    us what to do with a directory, and read_directory_recursive() is the
     -    thing that recurses".  Since we need to look into a directory to know
     -    how to treat it, though, it was quite easy to decide to recurse into the
     +    it is easy to think in terms of "treat_directory() tells us what to do
     +    with a directory, and read_directory_recursive() is the thing that
     +    recurses".  Since we need to look into a directory to know how to treat
     +    it, though, it is quite easy to decide to (also) recurse into the
          directory from treat_directory() by adding a read_directory_recursive()
     -    call.  Adding such a call is actually fine, IF we didn't also cause
     -    read_directory_recursive() to recurse into the same directory again.
     +    call.  Adding such a call is actually fine, IF we make sure that
     +    read_directory_recursive() does not also recurse into that same
     +    directory.

          Unfortunately, commit df5bcdf83aeb ("dir: recurse into untracked dirs
          for ignored files", 2017-05-18), added exactly such a case to the code,
     @@ -58,10 +61,12 @@
          Since dir.c is somewhat complex, extra cruft built up around this over
          time.  While trying to unravel it, I noticed several instances where the
          first call to read_directory_recursive() would return e.g.
     -    path_untracked for a some directory and a later one would return e.g.
     -    path_none, and the code relied on the side-effect of the first adding
     -    untracked entries to dir->entries in order to get the correct output
     -    despite the supposed override in return value by the later call.
     +    path_untracked for some directory and a later one would return e.g.
     +    path_none, despite the fact that the directory clearly should have been
     +    considered untracked.  The code happened to work due to the side-effect
     +    from the first invocation of adding untracked entries to dir->entries;
     +    this allowed it to get the correct output despite the supposed override
     +    in return value by the later call.

          I am somewhat concerned that there are still bugs and maybe even
          testcases with the wrong expectation.  I have tried to carefully
     @@ -74,9 +79,40 @@
          but the rules of existing behavior had so many special cases that I had
          a hard time coming up with some overarching rules about what correct
          behavior is for all cases, forcing me to hope that the regression tests
     -    are correct and sufficient.  (I'll note that this turmoil makes working
     -    with dir.c extremely unpleasant for me; I keep hoping it'll get better,
     -    but it never seems to.)
     +    are correct and sufficient.  Such a hope seems likely to be ill-founded,
     +    given my experience with dir.c-related testcases in the last few months:
     +
     +      Examples where the documentation was hard to parse or even just wrong:
     +       * 3aca58045f4f (git-clean.txt: do not claim we will delete files with
     +                       -n/--dry-run, 2019-09-17)
     +       * 09487f2cbad3 (clean: avoid removing untracked files in a nested git
     +                       repository, 2019-09-17)
     +       * e86bbcf987fa (clean: disambiguate the definition of -d, 2019-09-17)
     +      Examples where testcases were declared wrong and changed:
     +       * 09487f2cbad3 (clean: avoid removing untracked files in a nested git
     +                       repository, 2019-09-17)
     +       * e86bbcf987fa (clean: disambiguate the definition of -d, 2019-09-17)
     +       * a2b13367fe55 (Revert "dir.c: make 'git-status --ignored' work within
     +                       leading directories", 2019-12-10)
     +      Examples where testcases were clearly inadequate:
     +       * 502c386ff944 (t7300-clean: demonstrate deleting nested repo with an
     +                       ignored file breakage, 2019-08-25)
     +       * 7541cc530239 (t7300: add testcases showing failure to clean specified
     +                       pathspecs, 2019-09-17)
     +       * a5e916c7453b (dir: fix off-by-one error in match_pathspec_item,
     +                       2019-09-17)
     +       * 404ebceda01c (dir: also check directories for matching pathspecs,
     +                       2019-09-17)
     +       * 09487f2cbad3 (clean: avoid removing untracked files in a nested git
     +                       repository, 2019-09-17)
     +       * e86bbcf987fa (clean: disambiguate the definition of -d, 2019-09-17)
     +       * 452efd11fbf6 (t3011: demonstrate directory traversal failures,
     +                       2019-12-10)
     +       * b9670c1f5e6b (dir: fix checks on common prefix directory, 2019-12-19)
     +      Examples where "correct behavior" was unclear to everyone:
     +        https://lore.kernel.org/git/20190905154735.29784-1-newren@gmail.com/
     +      Other commits of note:
     +       * 902b90cf42bc (clean: fix theoretical path corruption, 2019-09-17)

          However, on the positive side, it does make the code much faster.  For
          the following simple shell loop in an empty repository:
     @@ -111,27 +147,14 @@
              24: 274.45
              25: 551.15

     -    After this fix, those drop to:
     -
     -        10: 0.00
     -        11: 0.00
     -        12: 0.00
     -        13: 0.00
     -        14: 0.00
     -        15: 0.00
     -        16: 0.00
     -        17: 0.00
     -        18: 0.00
     -        19: 0.00
     -        20: 0.00
     -        21: 0.00
     -        22: 0.00
     -        23: 0.00
     -        24: 0.00
     -        25: 0.00
     +    For the above run, using strace I can look for the number of untracked
     +    directories opened and can verify that it matches the expected
     +    2^($depth+1)-2 (the sum of 2^1 + 2^2 + 2^3 + ... + 2^$depth).

     -    In fact, it isn't until a depth of 190 nested directories that it
     -    sometimes starts reporting a time of 0.01 seconds and doesn't
     +    After this fix, with strace I can verify that the number of untracked
     +    directories that are opened drops to just $depth, and the timings all
     +    drop to 0.00.  In fact, it isn't until a depth of 190 nested directories
     +    that it sometimes starts reporting a time of 0.01 seconds and doesn't
          consistently report 0.01 seconds until there are 240 nested directories.
          The previous code would have taken
            17.55 * 2^220 / (60*60*24*365) = 9.4 * 10^59 YEARS
     @@ -152,17 +175,17 @@
       	const char *dirname, int len, int baselen, int excluded,
       	const struct pathspec *pathspec)
       {
     --	int nested_repo;
     +-	int nested_repo = 0;
      +	/*
      +	 * WARNING: From this function, you can return path_recurse or you
      +	 *          can call read_directory_recursive() (or neither), but
      +	 *          you CAN'T DO BOTH.
      +	 */
      +	enum path_treatment state;
     -+	int nested_repo, old_ignored_nr, stop_early;
     - 
     ++	int nested_repo = 0, old_ignored_nr, stop_early;
       	/* The "len-1" is to strip the final '/' */
     - 	switch (directory_exists_in_index(istate, dirname, len-1)) {
     + 	enum exist_status status = directory_exists_in_index(istate, dirname, len-1);
     + 
      @@

       	/* This is the "show_other_directories" case */
     @@ -292,9 +315,9 @@
      -	 * updates in treat_leading_path().  See the commit message for the
      -	 * commit adding this warning as well as the commit preceding it
      -	 * for details.
     -+	 * WARNING: Do NOT call recurse unless path_recurse is returned
     -+	 *          from treat_path().  Recursing on any other return value
     -+	 *          results in exponential slowdown.
     ++	 * WARNING: Do NOT recurse unless path_recurse is returned from
     ++	 *          treat_path().  Recursing on any other return value
     ++	 *          can result in exponential slowdown.
       	 */
      -
       	struct cached_dir cdir;
 6:  7fb8063541 = 6:  9a3f20656e t7063: blindly accept diffs

-- 
gitgitgadget