Re: git status --ignored hangs when a deep directory structure present in working tree

From: "SZEDER Gábor" <szeder.dev@gmail.com>
To: Martin Melka <martin.melka@gmail.com>
Cc: git@vger.kernel.org, Samuel Lijin <sxlijin@gmail.com>,
	Elijah Newren <newren@gmail.com>
Subject: Re: git status --ignored hangs when a deep directory structure present in working tree
Date: Mon, 27 Jan 2020 13:08:37 +0100	[thread overview]
Message-ID: <20200127120837.GA10482@szeder.dev> (raw)
In-Reply-To: <CANt4O2L_DZnMqVxZzTBMvr=BTWqB6L0uyORkoN_yMHLmUX7yHw@mail.gmail.com>

On Mon, Jan 27, 2020 at 11:55:01AM +0100, Martin Melka wrote:
> Hi all, I have ran across what might be a bug in git. When there is a
> deep directory structure (tried on 100+ nested dirs), then git status
> --ignored hangs indefinitely.
> Discovered this on OSX (Mojave, git 2.20.1 (Apple Git-117)), but it
> reproduces in Ubuntu (19.04, git 2.25.0) Docker container on OSX and
> also on baremetal Ubuntu server (16.04, git 2.17.1).
> 
> Steps to reproduce:
> 
> 1. Generate the deep dir structure:
> 
>     mkdir gittest; pushd gittest; git init; for i in $(seq 1 120); do
> mkdir dir; cd dir; done; touch leaf; popd
> 
> 2. Try to get git status --ignored
> 
>     cd gittest && git status --ignored
> 
> 
> If there is a dir depth limit, git should probably exit with an error
> rather than getting stuck endlessly.

This is interesting, thanks for the report.

There is no such directory depth limit, but the runtime of 'git status
--ignored' grows quickly with the depth of the untracked directory.
Running this shell loop produces the numbers below:

for depth in $(seq 10 30)
do
        dirs=$(for i in $(seq 1 $depth) ; do printf 'dir/' ; done)
        rm -rf dir
        mkdir -p $dirs
        >$dirs/untracked-file
        /usr/bin/time --format="$depth: %e" git status --ignored >/dev/null
done

10: 0.01
11: 0.03
12: 0.05
13: 0.11
14: 0.23
15: 0.47
16: 0.97
17: 1.97
18: 3.88
19: 7.85
20: 16.29
21: 32.92
22: 76.24

Beautifully quadratic, isn't it? :)

Unless I messed up my numbers, with a depth of 120 directories it
would take over 6*10^23 years to complete... so yeah, it does qualify
as indefinitely.

This slowdown was caused by commit df5bcdf83a (dir: recurse into
untracked dirs for ignored files, 2017-05-18), which was part of a
patch series to fix 'git clean -d' deleting untracked directories even
if they contained ignored files.

Cc'ing Samuel, author of that commit, and Elijah, who had quite some
fun with 'dir.c' recently.