Re: mt/dir-iterator-updates, was Re: What's cooking in git.git (Jul 2019, #01; Wed, 3)

> On Thu, Jul 4, 2019 at 6:30 PM Johannes Schindelin
> <Johannes.Schindelin@gmx.de> wrote:
> >
> > Hi Matheus,
> >
> > On Thu, 4 Jul 2019, Matheus Tavares Bernardino wrote:
> > >
> > > I wanted to take a look at the failures to see if I could help, [...]
> > > Could you point me to the right place, please?
> [...]
> >
> > I usually click on the "Tests" tab in that page:
> > https://dev.azure.com/gitgitgadget/git/_build/results?buildId=11495&view=ms.vss-test-web.build-test-results-tab
> >
> > You can click on any of the 1,384 (!) failing test cases, it will pop up a
> > pane on the right-hand side that shows the trace of that failing test
> > case. For the full trace of that test script, go to "Attachments" and
> > download the `Standard_Error_Output.log` (via the horizontal bread-crumbs
> > menu you can see when hovering over the file name).
>
> Thanks for the explanation! I inspected some of the
> `Standard_Error_Output.log`'s and it seems the problem is always with
> local clone (which started to use dir-iterator in this series). It
> seems all .git/objects/ dirs are being ignored. That makes sense,
> since st_ino will always be 0 on Windows. But your fixup patch should
> solve this. Is there any azure build for it?

> [...]
> > >
> > > Hm, I think `stat()` itself uses this strategy of an arbitrary cut-off
> > > when resolving a path. So we may also "ignore" circular symlinks and
> > > let the iteration continue until the point where `stat()` will return
> > > an ELOOP. (But it may be expensive...)
> >
> > This would not be equivalent, though, as your code also tried to address
> > circular references when two or more symlinks are involved, e.g. when
> > one symlink points to a directory that has another symlink that points to
> > the directory containing the first symlink.
>
> Hm, `stat()` also addresses this case doesn't it? For example:
>
> $ mkdir a b
> $ ln -s ../a b/s2a
> $ ln -s ../b a/s2b
> $ stat b/s2a/s2b/s2a/.../s2b
>
> Gives me:
> "too many levels of symbolic links"

> > > > Do we _have_ to, though? At some stage the path we come up with is beyond
> > > > `PATH_MAX` and we can stop right then and there.
> > > >
> > > > Besides, the way `find_recursive_symlinks()` is implemented adds quadratic
> > > > behavior.
> > >
> > > Yes, indeed. But it only happens when we have a path like this:
> > > `symlink_to_dir1/symlink_to_dir2/symlink_to_dir3/symlink_to_dir4/...`,
> > > right? I think this case won't be very usual on actual filesystems,
> > > thought.
> >
> > No, the check is performed in a loop, and that loop is executed whether
> > you have symlinks or not. That loop is executed for every item in the
> > iteration, and as we cannot assume a flat directory in general (in fact,
> > we should assume a directory depth proportional to the total number of
> > files), that adds that quadratic behavior.
>
> Oh, you're right. Sorry for the noise, I forgot this function was not
> only called for symlinks but for every directory entry :(
>
> An alternative solution would be to use `lstat()` together with
> `stat()` to only feed symlinked dirs to this function. This should
> reduce a lot the number of calls. Although it'd still be quadratic in
> the worst case, would that be any good?

> [...]
> > > > But I also think there are enough
> > > > reasons to do away with this function in the first place.
> > >
> > > We can delegate the circular symlinks problem to `stat()'s ELOOP`
> >
> > Not really. I mean, we _already_ delegate to the `ELOOP` condition, we
> > cannot even avoid it as long as we keep using `stat()` instead of
> > `lstat()`
>
> Yes, indeed. What I meant is that we may chose to _fully_ delegate to
> ELOOP. The way it is now, we should detect circular symlinks way
> before stat() fails. For example, with the case I showed above, we
> would stop at "b/s2a/s2b" whereas stat() would only fail at a much
> longer "b/s2a/s2b/s2a/s2b/...", far beyond in the iteration.

> > > The only downside is the overhead of iterating through directories which
> > > will be latter discarded for being in circular symlinks' chains. I mean,
> > > the overhead at dir-iterator shouldn't be much, but the one on the code
> > > using this API to do something for each of these directories (and its
> > > contents), may be. Also we would need to "undo" the work done for each
> > > of these directories if we want to ignore circular symlinks and continue
> > > the iteration, whereas if we try to detect it a priori, we can skip it
> > > from the beginning.
> >
> > Given that the intent of this patch series is a mere refactoring, I wonder
> > why the new, contentious circular symlink detection is slipped into it
> > anyway. It complicates the task, makes reviewing a lot harder, and it
> > holds up the refactoring.
>
> Yes, I apologize for that. I should have split this into 2 or maybe 3
> patchsets... This series started really simple just trying to apply
> the dir-iterator API into local clone. But then, other things became
> necessary and it got more complex.
>
> So, should I send a fixup patch removing find_recursive_symlinks() or
> reroll the series? There's also the option to use stat()+lstat() to
> reduce calls to this function, but it doesn't solve the problem on
> Windows, anyway.