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

>
> 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).

> >
> > 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.

> > > 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.

> > > 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()`

> but as I demonstrated above, that only catches part of the
> circular symlinks.
>
> > or `path_len > PATH_MAX`.
>
> This would have the advantage of _not_ adding quadratic behavior.
>
> And just in case you think quadratic behavior would not matter much: Git
> is used to manage the largest repository on this planet, which has over 3
> million index entries when checked out.
>
> Quadratic behavior matters.
>
> I don't know where the dir-iterator is used, but we simply should try our
> best to aim for the optimal time complexity in the first place.

> > 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.