[PATCH 2/2] fts: enable leaf optimization for NFS

[Kamil Dudka]

NFS provides usable dirent.d_type but not necessarily for all entries
of large directories. See <https://bugzilla.redhat.com/1252549> for
details.
* lib/fts.c (leaf_optimization_applies): Append NFS on the white list.
---
lib/fts.c | 5 +++++
1 file changed, 5 insertions(+)

diff --git a/lib/fts.c b/lib/fts.c
index 76bbc06..c833242 100644
--- a/lib/fts.c
+++ b/lib/fts.c
@@ -717,6 +717,11 @@ leaf_optimization_applies (int dir_fd)

switch (fs_buf.f_type)
{
+ case S_MAGIC_NFS:
+ /* NFS provides usable dirent.d_type but not necessarily for all entries
+ of large directories. See <https://bugzilla.redhat.com/1252549>. */
+ return true;
+
/* List here the file system types that lack usable dirent.d_type
info, yet for which the optimization does apply. */
case S_MAGIC_REISERFS:

[Pádraig Brady]

The flag is needed to implement the -noleaf option of find.
* lib/fts.c (link_count_optimize_ok): Implement the FTS_NOLEAF flag.
* lib/fts_.h (FTS_NOLEAF): New macro, shifted conflicting constants.

Is this exposed to fix issues with certain file systems,
or just in case there may be issues, or support easily
testing find without the leaf optimization?

I see Jim said the current FTS implementation
would make -noleaf a no-op there:
https://lists.gnu.org/archive/html/bug-gnulib/2008-12/msg00280.html

cheers,
Pádraig.

p.s. I see that find does a stat per file on XFS,
while d_type can be used to distinguish dirs there.
On XFS DT_DIR is set for dirs and DT_UNKNOWN otherwise.
I wonder is there some optimization we could do for that case.

[Kamil Dudka]

Post by Pádraig Brady

The flag is needed to implement the -noleaf option of find.
* lib/fts.c (link_count_optimize_ok): Implement the FTS_NOLEAF flag.
* lib/fts_.h (FTS_NOLEAF): New macro, shifted conflicting constants.

Is this exposed to fix issues with certain file systems,
or just in case there may be issues, or support easily
testing find without the leaf optimization?

All of the above I would say. We can never verify that it works properly
for all white-listed file systems in all kernel versions (and all their
supported configurations). There should always be a way for the user to
disable the optimization if needed, either for debugging, or to work around
a file system bug.

Post by Pádraig Brady
I see Jim said the current FTS implementation
https://lists.gnu.org/archive/html/bug-gnulib/2008-12/msg00280.html

Yes but it has never been reflected in find's documentation so the current
behavior hardly matches what users would expect.

Post by Pádraig Brady
cheers,
Pádraig.
p.s. I see that find does a stat per file on XFS,
while d_type can be used to distinguish dirs there.
On XFS DT_DIR is set for dirs and DT_UNKNOWN otherwise.

I am afraid this is not sufficient for FTS to eliminate all calls to stat()
unless it is guaranteed that DT_UNKNOWN is never returned for a directory.

Post by Pádraig Brady
I wonder is there some optimization we could do for that case.

After quick check I can see the leaf optimization applies to that case too.

Given the fact that it was already enabled by default in RHEL-5 findutils,
it is difficult to explain why the feature is not available in the latest
upstream.

Kamil

[Pádraig Brady]

Post by Kamil Dudka

Post by Pádraig Brady
p.s. I see that find does a stat per file on XFS,
while d_type can be used to distinguish dirs there.
On XFS DT_DIR is set for dirs and DT_UNKNOWN otherwise.

I am afraid this is not sufficient for FTS to eliminate all calls to stat()
unless it is guaranteed that DT_UNKNOWN is never returned for a directory.

I'm fairly sure XFS never returns DT_UNKNOWN for a directory.

[Pádraig Brady]

Post by Kamil Dudka

Post by Pádraig Brady

The flag is needed to implement the -noleaf option of find.
* lib/fts.c (link_count_optimize_ok): Implement the FTS_NOLEAF flag.
* lib/fts_.h (FTS_NOLEAF): New macro, shifted conflicting constants.

Is this exposed to fix issues with certain file systems,
or just in case there may be issues, or support easily
testing find without the leaf optimization?

All of the above I would say. We can never verify that it works properly
for all white-listed file systems in all kernel versions (and all their
supported configurations). There should always be a way for the user to
disable the optimization if needed, either for debugging, or to work around
a file system bug.

Post by Pádraig Brady
I see Jim said the current FTS implementation
https://lists.gnu.org/archive/html/bug-gnulib/2008-12/msg00280.html

Yes but it has never been reflected in find's documentation so the current
behavior hardly matches what users would expect.

On the other hand we've had no reports of issues with the
existing auto config done by FTS. In my experience one
should jump through hoops to avoid config where possible.
Until we see a case where dirent.d_type is accurate while
noleaf is not appropriate, then I'm inclined to avoid the config.
If this was an issue then there would need to be associated
-noleaf patches to find(1), and also other FTS using tools.

I've applied the patch to ensure noleaf optimization is
enabled for NFS, and also applied my patch enabling it for XFS.

thanks,
Pádraig.

[Kamil Dudka]

Post by Pádraig Brady
On the other hand we've had no reports of issues with the
existing auto config done by FTS.

Because the leaf optimization has been enabled for reiserfs only until now.
I suspect that NFS will not be that easy and such file system issues might
be difficult to debug without the -noleaf option actually implemented.

Post by Pádraig Brady
In my experience one
should jump through hoops to avoid config where possible.
Until we see a case where dirent.d_type is accurate while
noleaf is not appropriate, then I'm inclined to avoid the config.
If this was an issue then there would need to be associated
-noleaf patches to find(1), and also other FTS using tools.

That sounds like a reasonable approach for tools that do not implement any
-noleaf option yet. However, GNU find has provided this option since 1996
(if not even longer) and the option has never been properly deprecated.

Post by Pádraig Brady
I've applied the patch to ensure noleaf optimization is
enabled for NFS, and also applied my patch enabling it for XFS.
thanks,
Pádraig.

Thank you for applying those patches!

Kamil

[Kamil Dudka]

Post by Kamil Dudka

Post by Pádraig Brady
On the other hand we've had no reports of issues with the
existing auto config done by FTS.

Because the leaf optimization has been enabled for reiserfs only until now.
I suspect that NFS will not be that easy and such file system issues might
be difficult to debug without the -noleaf option actually implemented.

So we have the first bug report about the leaf optimization causing problems
to users of find(1):

https://bugzilla.redhat.com/1299169

Is this a reason to implement the -noleaf option of find (and consequently
the FTS_NOLEAF flag of gnulib's FTS)?

Kamil

Post by Kamil Dudka

Post by Pádraig Brady
In my experience one
should jump through hoops to avoid config where possible.
Until we see a case where dirent.d_type is accurate while
noleaf is not appropriate, then I'm inclined to avoid the config.
If this was an issue then there would need to be associated
-noleaf patches to find(1), and also other FTS using tools.

That sounds like a reasonable approach for tools that do not implement any
-noleaf option yet. However, GNU find has provided this option since 1996
(if not even longer) and the option has never been properly deprecated.

Post by Pádraig Brady
I've applied the patch to ensure noleaf optimization is
enabled for NFS, and also applied my patch enabling it for XFS.
thanks,
Pádraig.

Thank you for applying those patches!
Kamil

[Pádraig Brady]

Post by Kamil Dudka

Post by Kamil Dudka

Post by Pádraig Brady
On the other hand we've had no reports of issues with the
existing auto config done by FTS.

Because the leaf optimization has been enabled for reiserfs only until now.
I suspect that NFS will not be that easy and such file system issues might
be difficult to debug without the -noleaf option actually implemented.

So we have the first bug report about the leaf optimization causing problems
https://bugzilla.redhat.com/1299169
Is this a reason to implement the -noleaf option of find (and consequently
the FTS_NOLEAF flag of gnulib's FTS)?

Maybe. But I'm also thinking it might mean we
can't enable this optimization for NFS
as the implementations are too disparate in this regard?

It seems prudent for example to disable this
optimization for the imminent coreutils 8.25 release :(

thanks,
Pádraig

[Pádraig Brady]

Post by Pádraig Brady

Post by Kamil Dudka

Post by Kamil Dudka

Post by Pádraig Brady
On the other hand we've had no reports of issues with the
existing auto config done by FTS.

Because the leaf optimization has been enabled for reiserfs only until now.
I suspect that NFS will not be that easy and such file system issues might
be difficult to debug without the -noleaf option actually implemented.

So we have the first bug report about the leaf optimization causing problems
https://bugzilla.redhat.com/1299169
Is this a reason to implement the -noleaf option of find (and consequently
the FTS_NOLEAF flag of gnulib's FTS)?

Maybe. But I'm also thinking it might mean we
can't enable this optimization for NFS
as the implementations are too disparate in this regard?
It seems prudent for example to disable this
optimization for the imminent coreutils 8.25 release :(

Patch attaced

[Kamil Dudka]

Post by Pádraig Brady

Post by Pádraig Brady

Post by Kamil Dudka

Post by Kamil Dudka

Post by Pádraig Brady
On the other hand we've had no reports of issues with the
existing auto config done by FTS.

Because the leaf optimization has been enabled for reiserfs only until now.
I suspect that NFS will not be that easy and such file system issues might
be difficult to debug without the -noleaf option actually implemented.

So we have the first bug report about the leaf optimization causing
https://bugzilla.redhat.com/1299169
Is this a reason to implement the -noleaf option of find (and consequently
the FTS_NOLEAF flag of gnulib's FTS)?

Maybe. But I'm also thinking it might mean we
can't enable this optimization for NFS
as the implementations are too disparate in this regard?
It seems prudent for example to disable this
optimization for the imminent coreutils 8.25 release :(

Patch attaced

Looks good for coreutils needs if there is a new release behind the door.

Now I need to have a closer look at how such cases were handled by findutils
before it was rewritten to use FTS. The recursive implementation of find has
the leaf optimization enabled by default but it supports an error recovery
for cases like this. It still works in RHEL-5 and nobody has reported such
assertion failures yet...

Kamil

[James Youngman]

Coming to this thread late, but this patch should be included now in
current findutils git.

Post by Kamil Dudka

Post by Kamil Dudka

Post by Pádraig Brady
On the other hand we've had no reports of issues with the
existing auto config done by FTS.

Because the leaf optimization has been enabled for reiserfs only until

now.

Post by Kamil Dudka
I suspect that NFS will not be that easy and such file system issues

might

Post by Kamil Dudka
be difficult to debug without the -noleaf option actually implemented.

So we have the first bug report about the leaf optimization causing problems
https://bugzilla.redhat.com/1299169
Is this a reason to implement the -noleaf option of find (and consequently
the FTS_NOLEAF flag of gnulib's FTS)?
Kamil

Post by Kamil Dudka

Post by Pádraig Brady
In my experience one
should jump through hoops to avoid config where possible.
Until we see a case where dirent.d_type is accurate while
noleaf is not appropriate, then I'm inclined to avoid the config.
If this was an issue then there would need to be associated
-noleaf patches to find(1), and also other FTS using tools.

That sounds like a reasonable approach for tools that do not implement

any

Post by Kamil Dudka
-noleaf option yet. However, GNU find has provided this option since

1996

Post by Kamil Dudka
(if not even longer) and the option has never been properly deprecated.

Post by Pádraig Brady
I've applied the patch to ensure noleaf optimization is
enabled for NFS, and also applied my patch enabling it for XFS.
thanks,
Pádraig.

Thank you for applying those patches!
Kamil

--
--
This email is intended solely for the use of its addressee, sender, and any
readers of a mailing list archive in which it happens to appear. If you
have received this email in error, please say or type three times, "I
believe in the utility of email disclaimers," and then reply to the author
correcting any spellings (and, optionally, any incorrect spellings),
accompanying these with humorous jests about the author's parentage. If
you are not the addressee, you are nevertheless permitted to both copy and
forward this email since without such permissions email systems are unable
to transmit email to anybody, intended recipient or not. To those still
reading by this point, the author would like to apologise for being unable
to maintain a consistent level of humour throughout this disclaimer.
Contents may settle during transit. Do not feed the animals.

[Pádraig Brady]

Post by Pádraig Brady

The flag is needed to implement the -noleaf option of find.
* lib/fts.c (link_count_optimize_ok): Implement the FTS_NOLEAF flag.
* lib/fts_.h (FTS_NOLEAF): New macro, shifted conflicting constants.

Is this exposed to fix issues with certain file systems,
or just in case there may be issues, or support easily
testing find without the leaf optimization?
I see Jim said the current FTS implementation
https://lists.gnu.org/archive/html/bug-gnulib/2008-12/msg00280.html
cheers,
Pádraig.
p.s. I see that find does a stat per file on XFS,
while d_type can be used to distinguish dirs there.
On XFS DT_DIR is set for dirs and DT_UNKNOWN otherwise.
I wonder is there some optimization we could do for that case.

I did a quick check on XFS which suggests the leaf optimization
based on st_nlink is valid:
test $(($(find . -maxdepth 1 -type d | wc -l) + 1)) = $(stat -c %h .) && echo leaf_ok

Applying this diff:
@@ -717,6 +718,7 @@ leaf_optimization_applies (int dir_fd)
{
/* List here the file system types that lack usable dirent.d_type
info, yet for which the optimization does apply. */
+ case S_MAGIC_XFS:
case S_MAGIC_REISERFS:
return true;

Gives this significant speedup:
$ time find/find-before /usr/share >/dev/null
real 0m0.410s
user 0m0.145s
sys 0m0.266s

$ time find/find-after /usr/share >/dev/null
real 0m0.278s
user 0m0.147s
sys 0m0.131s

I also noticed a lot of fcntl calls on XFS
(basically one per file), which I need to look further into:
$ strace -c find/find /usr/share >/dev/null
% time seconds usecs/call calls errors syscall
------ ----------- ----------- --------- --------- ----------------
40.03 0.147809 1 151710 fcntl
17.62 0.065069 1 63154 close
14.52 0.053608 1 40071 newfstatat
13.15 0.048547 1 35400 getdents

cheers,
Pádraig

[Kamil Dudka]

Post by Pádraig Brady
I also noticed a lot of fcntl calls on XFS
$ strace -c find/find /usr/share >/dev/null
% time seconds usecs/call calls errors syscall
------ ----------- ----------- --------- --------- ----------------
40.03 0.147809 1 151710 fcntl
17.62 0.065069 1 63154 close
14.52 0.053608 1 40071 newfstatat
13.15 0.048547 1 35400 getdents

In my testing, fcntl() was called 8x for each directory traversed.

It was mainly caused by the implementation of opendirat(). It calls
set_cloexec_flag(), which calls fcntl() two times. Then it calls
fdopendir(), which also calls fcntl() two times. fts_build() also
calls set_cloexec_flag(). Then inside_dir() calls dup_cloexec(),
which is fcntl (fd, F_DUPFD_CLOEXEC, 0).

Perhaps some syscalls could be optimized out by using dup_cloexec()
also in fts_build()?

Kamil

[Kamil Dudka]

Post by Pádraig Brady

Post by Pádraig Brady

The flag is needed to implement the -noleaf option of find.
* lib/fts.c (link_count_optimize_ok): Implement the FTS_NOLEAF flag.
* lib/fts_.h (FTS_NOLEAF): New macro, shifted conflicting constants.

Is this exposed to fix issues with certain file systems,
or just in case there may be issues, or support easily
testing find without the leaf optimization?
I see Jim said the current FTS implementation
https://lists.gnu.org/archive/html/bug-gnulib/2008-12/msg00280.html
cheers,
Pádraig.
p.s. I see that find does a stat per file on XFS,
while d_type can be used to distinguish dirs there.
On XFS DT_DIR is set for dirs and DT_UNKNOWN otherwise.
I wonder is there some optimization we could do for that case.

I did a quick check on XFS which suggests the leaf optimization
test $(($(find . -maxdepth 1 -type d | wc -l) + 1)) = $(stat -c %h .) && echo leaf_ok
@@ -717,6 +718,7 @@ leaf_optimization_applies (int dir_fd)
{
/* List here the file system types that lack usable dirent.d_type
info, yet for which the optimization does apply. */
return true;
$ time find/find-before /usr/share >/dev/null
real 0m0.410s
user 0m0.145s
sys 0m0.266s
$ time find/find-after /usr/share >/dev/null
real 0m0.278s
user 0m0.147s
sys 0m0.131s

Pádraig, do you remember which kernel you tested it with?

I am currently not able to get any speedup on XFS with Fedora/el7 kernels...

Kamil

Post by Pádraig Brady
I also noticed a lot of fcntl calls on XFS
$ strace -c find/find /usr/share >/dev/null
% time seconds usecs/call calls errors syscall
------ ----------- ----------- --------- --------- ----------------
40.03 0.147809 1 151710 fcntl
17.62 0.065069 1 63154 close
14.52 0.053608 1 40071 newfstatat
13.15 0.048547 1 35400 getdents
cheers,
Pádraig

[Pádraig Brady]

Post by Kamil Dudka

Post by Pádraig Brady

Post by Pádraig Brady

The flag is needed to implement the -noleaf option of find.
* lib/fts.c (link_count_optimize_ok): Implement the FTS_NOLEAF flag.
* lib/fts_.h (FTS_NOLEAF): New macro, shifted conflicting constants.

Is this exposed to fix issues with certain file systems,
or just in case there may be issues, or support easily
testing find without the leaf optimization?
I see Jim said the current FTS implementation
https://lists.gnu.org/archive/html/bug-gnulib/2008-12/msg00280.html
cheers,
Pádraig.
p.s. I see that find does a stat per file on XFS,
while d_type can be used to distinguish dirs there.
On XFS DT_DIR is set for dirs and DT_UNKNOWN otherwise.
I wonder is there some optimization we could do for that case.

I did a quick check on XFS which suggests the leaf optimization
test $(($(find . -maxdepth 1 -type d | wc -l) + 1)) = $(stat -c %h .) && echo leaf_ok
@@ -717,6 +718,7 @@ leaf_optimization_applies (int dir_fd)
{
/* List here the file system types that lack usable dirent.d_type
info, yet for which the optimization does apply. */
return true;
$ time find/find-before /usr/share >/dev/null
real 0m0.410s
user 0m0.145s
sys 0m0.266s
$ time find/find-after /usr/share >/dev/null
real 0m0.278s
user 0m0.147s
sys 0m0.131s

Pádraig, do you remember which kernel you tested it with?
I am currently not able to get any speedup on XFS with Fedora/el7 kernels...

Eek that's getting towards 2 years ago :)
I _vaguely_ remember creating a loopback XFS for testing on Fedora.
Me goes spelunking on an old laptop...
Ah found a perf.data indicating 4.2.5-300.fc23.x86_64 (glibc-2.22)
I don't have the code changes though I vaguely remember having
to tweak things so that the gnulib FTS was used.

cheers,
Pádraig

[Paul Eggert]

Post by Pádraig Brady
p.s. I see that find does a stat per file on XFS,
while d_type can be used to distinguish dirs there.
On XFS DT_DIR is set for dirs and DT_UNKNOWN otherwise.
I wonder is there some optimization we could do for that case.

There might be, but what are you basing this summary on? Although I don't use
XFS and don't know much about it, I just looked in
linux-4.13-rc1/fs/xfs/xfs_dir2_readdir.c and its xfs_dir3_get_dtype function
suggests that readdir's d_type either generally works, or always returns
DT_UNKNOWN, depending on how the xfs filesystem is set up. See
linux-4.13-rc1/fs/xfs/libxfs/xfs_format.h and its xfs_sb_version_hasftype function.

This might explain why Gnulib fts (which has your change) improves performance
for you (if your xfs had an appropriate setup) whereas it is no faster for Kamil
(if Kamil's xfs had an inappropriate setup).

Anyway, this comment in Gnulib fts.c:

/* List here the file system types that lack usable dirent.d_type
info, yet for which the optimization does apply. */
case S_MAGIC_REISERFS:
case S_MAGIC_XFS:
return NOSTAT_LEAF_OPTIMIZATION;

seems wrong or at least incomplete, since XFS either has usable dirent.d_type
info, or lacks it, depending on how the filesystem is set up.

Perhaps someone with more XFS expertise could comment?

[Kamil Dudka]

Post by Paul Eggert

Post by Pádraig Brady
p.s. I see that find does a stat per file on XFS,
while d_type can be used to distinguish dirs there.
On XFS DT_DIR is set for dirs and DT_UNKNOWN otherwise.
I wonder is there some optimization we could do for that case.

There might be, but what are you basing this summary on? Although I don't
use XFS and don't know much about it, I just looked in
linux-4.13-rc1/fs/xfs/xfs_dir2_readdir.c and its xfs_dir3_get_dtype function
suggests that readdir's d_type either generally works, or always returns
DT_UNKNOWN, depending on how the xfs filesystem is set up. See
linux-4.13-rc1/fs/xfs/libxfs/xfs_format.h and its xfs_sb_version_hasftype function.
This might explain why Gnulib fts (which has your change) improves
performance for you (if your xfs had an appropriate setup) whereas it is no
faster for Kamil (if Kamil's xfs had an inappropriate setup).

Yes. In my testing environment, readdir() always returned valid dtype, so
the leaf optimization was not needed. Anyway, it should be safe to keep it
enabled for XFS. It has been enabled in Fedora since December 2015 without
causing any bug reports so far.

Post by Paul Eggert
/* List here the file system types that lack usable dirent.d_type
info, yet for which the optimization does apply. */
return NOSTAT_LEAF_OPTIMIZATION;
seems wrong or at least incomplete, since XFS either has usable
dirent.d_type info, or lacks it, depending on how the filesystem is set up.
Perhaps someone with more XFS expertise could comment?

The following linux commit seems to be related:

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=v3.11-rc1-93-g0cb97766f292

Kamil

[Paul Eggert]

Thanks, I installed the attached.