fts: sort dirent entries on inode number before traversing

This avoids a quadratic, seek-related performance penalty when
operating on a directory containing many entries (measurable at 10k;
3.5 hours at 2 million entries with a cold cache) on certain types
of file systems, including ext3 and ext4, but not tmpfs.
* lib/fts.c (DT_MUST_BE, NOT_AN_INODE_NUMBER, D_INO): Define.
(FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD): Define if not defined.
(S_MAGIC_TMPFS, S_MAGIC_NFS): Define.
(fs_handles_readdir_ordered_dirents_efficiently): New function.
(dirent_inode_sort_may_be_useful, fts_compare_ino): Likewise.
(fts_build): Set the stat.st_ino member from D_INO.
If it is likely to be useful, sort dirent entries on inode number.
* m4/fts.m4 (gl_FUNC_FTS_CORE): Check for fstatfs, sys/vfs.h,
and the struct statfs.f_type member.
* modules/fts (Depends-on): Add d-ino.

1 files changed, 1 insertions, 0 deletions

diff --git a/modules/fts b/modules/fts
index b45f0260ba..a412d0ac9d 100644
--- a/modules/fts
+++ b/modules/fts
@@ -9,6 +9,7 @@ m4/fts.m4
 
 Depends-on:
 cycle-check
+d-ino
 d-type
 dirfd
 fchdir