Optimize pathologic case of telldir()

[mav]

Summary

When application reads large directory, calling telldir() for each entry, it creates exponential performance drop as number of entries reach tenths to hundreds of thousands. It is caused by full search through the internal list, that never finds matches in that scenario, but creates O(n^2) delays. My patch optimizes that search, limiting it to entries of the same buffer, turning time from O(n^2) closer to O(n) in the case of linear directory scan.

PR: 218622

Test Plan

With this synthetic test tool run on tmpfs directory with different number of files:

#include <dirent.h>
#include <err.h>

int
main(int argc, char **argv)
{
        DIR *d;

        d = opendir("/tmp/td");
        if (d == NULL)
                errx(1, "opendir() failed");
        while (readdir(d)) {
                telldir(d);
        }
        closedir(d);
}

I've got such results

        Head            Patch
1k       0.005/00.00     0.000/00.00
10k      0.258/00.33     0.005/00.01
20k      0.868/00.87     0.017/00.01
50k      5.728/05.47     0.029/00.04
100k    21.932/21.98     0.040/00.08
200k    87.754/87.81     0.080/00.16
500k    ***              0.220/00.41
1m      ***              0.430/00.70
2m      ***              0.780/01.61
5m      ***              2.136/03.47

[jilles]

This seems to have been designed to minimize changes to struct _dirdesc which used to be public in <dirent.h>. That seems a reasonable thing to do.

As a result, however, the O(N^2) behaviour is eliminated only in an initial traversal. When returning to the beginning (e.g. using seekdir) after doing a complete readdir/telldir loop and again doing readdir/telldir for every entry, the first telldir will traverse the entire list.

If you have verified that Samba does not do this in common situations, I have no objection. As @jhb wrote in the PR, the proper fix is to return a seek location for each entry in struct dirent.

[mav]

In D10408#215687, @jilles wrote:

If you have verified that Samba does not do this in common situations, I have no objection.

Ash tested it with Samba and reports good results.

As @jhb wrote in the PR, the proper fix is to return a seek location for each entry in struct dirent.

Yes, that will be a proper fix for head, but I need something I could use on stable/11 now.

[jhb]

Note that the proper fix might take a while to appear, so I think an intermediate one (even if a hack) is fine. Ironically the original PR was about samba, and the new PR is also about samba.