Order files by first physical extent before reading

Inspired by a similar change in dpkg.  This takes 'mandb -c' from
104 to 32 seconds in a test installation, and 'man -K' from 74 to 38
seconds.  On non-Linux systems where FIEMAP is not available, use
posix_fadvise instead to preload files.

Fixes Debian bug #574410.

* gnulib: Import nonblocking and openat modules.
* configure.ac: Check for <linux/fiemap.h> and posix_fadvise.
* lib/orderfiles.c: New file.
* lib/orderfiles.h: New file.
* lib/Makefile.am (libman_la_SOURCES): Add orderfiles.c and
orderfiles.h.
* src/check_mandirs.c (add_dir_entries): Order files before reading
them.
* src/man.c (try_section, do_global_apropos_section): Likewise.
* src/straycats.c (check_for_stray): Likewise.
* NEWS: Document this.

1 files changed, 30 insertions, 10 deletions

diff --git a/src/check_mandirs.c b/src/check_mandirs.c
index 858b43d5..3b0680c1 100644
--- a/src/check_mandirs.c
+++ b/src/check_mandirs.c
@@ -54,6 +54,7 @@
 
 #include "error.h"
 #include "hashtable.h"
+#include "orderfiles.h"
 #include "security.h"
 
 #include "mydbm.h"
@@ -310,6 +311,8 @@ static inline void add_dir_entries (const char *path, char *infile)
 	int len;
 	struct dirent *newdir;
 	DIR *dir;
+	char **names;
+	size_t names_len, names_max, i;
 
 	manpage = xasprintf ("%s/%s/", path, infile);
 	len = strlen (manpage);
@@ -325,19 +328,36 @@ static inline void add_dir_entries (const char *path, char *infile)
 		free (manpage);
                 return;
         }
-        
+
+	names_len = 0;
+	names_max = 1024;
+	names = XNMALLOC (names_max, char *);
+
         /* strlen(newdir->d_name) could be replaced by newdir->d_reclen */
-        
-	while ( (newdir = readdir (dir)) )
-		if (!(*newdir->d_name == '.' && 
-		      strlen (newdir->d_name) < (size_t) 3)) {
-			manpage = appendstr (manpage, newdir->d_name, NULL);
-			test_manfile (manpage, path);
-			*(manpage + len) = '\0';
+
+	while ((newdir = readdir (dir)) != NULL) {
+		if (*newdir->d_name == '.' &&
+		    strlen (newdir->d_name) < (size_t) 3)
+			continue;
+		if (names_len >= names_max) {
+			names_max *= 2;
+			names = xnrealloc (names, names_max, sizeof (char *));
 		}
-		
-	free (manpage);
+		names[names_len++] = xstrdup (newdir->d_name);
+	}
 	closedir (dir);
+
+	order_files (infile, names, names_len);
+
+	for (i = 0; i < names_len; ++i) {
+		manpage = appendstr (manpage, names[i], NULL);
+		test_manfile (manpage, path);
+		*(manpage + len) = '\0';
+		free (names[i]);
+	}
+
+	free (names);
+	free (manpage);
 }
 
 #ifdef SECURE_MAN_UID