Discussion:
[PATCH 1/6] fts-tests: new module
(too old to reply)
Paul Eggert
2017-07-25 07:28:01 UTC
Permalink
Raw Message
* modules/fts-tests, tests/test-fts.c: New files.
---
ChangeLog | 5 ++
modules/fts-tests | 13 +++++
tests/test-fts.c | 142 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 160 insertions(+)
create mode 100644 modules/fts-tests
create mode 100644 tests/test-fts.c

diff --git a/ChangeLog b/ChangeLog
index 43401d2ad..05ac15d93 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2017-07-24 Paul Eggert <***@cs.ucla.edu>
+
+ fts-tests: new module
+ * modules/fts-tests, tests/test-fts.c: New files.
+
2017-07-23 Bruno Haible <***@clisp.org>

Rename module 'strftime' to 'nstrftime'.
diff --git a/modules/fts-tests b/modules/fts-tests
new file mode 100644
index 000000000..115bf669a
--- /dev/null
+++ b/modules/fts-tests
@@ -0,0 +1,13 @@
+Files:
+tests/test-fts.c
+
+Depends-on:
+errno
+remove
+unlinkat
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-fts
+check_PROGRAMS += test-fts
diff --git a/tests/test-fts.c b/tests/test-fts.c
new file mode 100644
index 000000000..2ce72c96a
--- /dev/null
+++ b/tests/test-fts.c
@@ -0,0 +1,142 @@
+/* Test the fts function.
+ Copyright 2017 Free Software Foundation, Inc.
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include <config.h>
+
+#include <fts_.h>
+
+#include <errno.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#define BASE "t-fts.tmp"
+static char *const argv[2] = { BASE, 0 };
+
+static void
+perror_exit (char const *message, int status)
+{
+ perror (message);
+ exit (status);
+}
+
+/* Remove BASE and all files under it. */
+static void
+remove_tree (void)
+{
+ FTSENT *e;
+ FTS *ftsp = fts_open (argv, FTS_NOSTAT | FTS_PHYSICAL | FTS_CWDFD, 0);
+ if (ftsp)
+ {
+ while ((e = fts_read (ftsp)))
+ {
+ int status = 0;
+ switch (e->fts_info)
+ {
+ case FTS_DP:
+ status = unlinkat (ftsp->fts_cwd_fd, e->fts_accpath,
+ AT_REMOVEDIR);
+ break;
+
+ case FTS_F: case FTS_NSOK:
+ status = unlinkat (ftsp->fts_cwd_fd, e->fts_accpath, 0);
+ break;
+ }
+ if (status != 0)
+ perror_exit (e->fts_path, 1);
+ }
+ if (fts_close (ftsp) != 0)
+ perror_exit ("fts_close", 2);
+ }
+ else if (errno != ENOENT)
+ perror_exit (BASE, 3);
+}
+
+int
+main (void)
+{
+ FTS *ftsp;
+ FTSENT *e;
+ char buf[sizeof BASE + 100];
+ int i;
+ enum { needles = 4 };
+ int needles_seen = 0;
+ struct stat st;
+
+ remove_tree ();
+
+ /* Create directories BASE, BASE/d, BASE/d/1, BASE/d/2, ..., BASE/d/65536,
+ to stress-test fts. Stop if directory creation fails due to
+ EMFILE problems, or if BASE/d's link count no longer matches the
+ Unix tradition. See:
+ https://bugzilla.kernel.org/show_bug.cgi?id=196405
+ for more info. */
+ if (mkdir (BASE, 0777) != 0)
+ perror_exit (BASE, 4);
+ if (mkdir (BASE "/d", 0777) != 0)
+ perror_exit (BASE "/d", 5);
+ for (i = 1; i <= 65536; i++)
+ {
+ sprintf (buf, "%s/d/%i", BASE, i);
+ if (mkdir (buf, 0777) != 0)
+ {
+ if (errno != EMFILE || i <= needles)
+ perror_exit (buf, 77);
+ break;
+ }
+ if (needles < i && stat (BASE "/d", &st) == 0 && st.st_nlink != i + 2)
+ break;
+ }
+
+ /* Create empty files BASE/d/1/needle etc. */
+ for (i = 1; i <= needles; i++)
+ {
+ int fd;
+ sprintf (buf, "%s/d/%d/needle", BASE, i);
+ fd = open (buf, O_WRONLY | O_CREAT, 0666);
+ if (fd < 0 || close (fd) != 0)
+ perror_exit (buf, 77);
+ }
+
+ /* Use fts to look for the needles. */
+ ftsp = fts_open (argv, FTS_SEEDOT | FTS_NOSTAT | FTS_PHYSICAL | FTS_CWDFD, 0);
+ if (!ftsp)
+ perror_exit (BASE, 6);
+ while ((e = fts_read (ftsp)))
+ needles_seen += strcmp (e->fts_name, "needle") == 0;
+ fflush (stdout);
+ if (errno)
+ perror_exit ("fts_read", 7);
+
+ /* Report an error if we did not find the needles. */
+ if (needles_seen != needles)
+ {
+ fprintf (stderr, "%d needles found (should be %d)\n",
+ needles_seen, needles);
+ return 1;
+ }
+
+ remove_tree ();
+ if (stat (BASE, &st) == 0)
+ {
+ fprintf (stderr, "fts could not remove directory\n");
+ return 1;
+ }
+ return 0;
+}
--
2.13.3
Paul Eggert
2017-07-25 07:28:02 UTC
Permalink
Raw Message
* lib/fts.c (fts_open): Set rootparent n_dirs_remaining to -1
so that root need not be a special case later.
(fts_read): Remove now-redundant test for fts_level.
Do not assume that nlink_t is signed.
(fts_build): Remove useless decrement of nlinks.
(fts_stat): Avoid unlikely signed integer overflow later, if
nlink_t is signed.
---
ChangeLog | 9 +++++++++
lib/fts.c | 26 +++++++++-----------------
lib/fts_.h | 6 +++++-
3 files changed, 23 insertions(+), 18 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 05ac15d93..da1fda1ad 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,14 @@
2017-07-24 Paul Eggert <***@cs.ucla.edu>

+ fts: nlink_t signedness fixups
+ * lib/fts.c (fts_open): Set rootparent n_dirs_remaining to -1
+ so that root need not be a special case later.
+ (fts_read): Remove now-redundant test for fts_level.
+ Do not assume that nlink_t is signed.
+ (fts_build): Remove useless decrement of nlinks.
+ (fts_stat): Avoid unlikely signed integer overflow later, if
+ nlink_t is signed.
+
fts-tests: new module
* modules/fts-tests, tests/test-fts.c: New files.

diff --git a/lib/fts.c b/lib/fts.c
index 3bac3244e..d5fc051a0 100644
--- a/lib/fts.c
+++ b/lib/fts.c
@@ -479,6 +479,7 @@ fts_open (char * const *argv,
if ((parent = fts_alloc(sp, "", 0)) == NULL)
goto mem2;
parent->fts_level = FTS_ROOTPARENTLEVEL;
+ parent->fts_n_dirs_remaining = -1;
}

/* The classic fts implementation would call fts_stat with
@@ -1024,10 +1025,7 @@ check_for_dir:
if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
{
FTSENT *parent = p->fts_parent;
- if (FTS_ROOTLEVEL < p->fts_level
- /* ->fts_n_dirs_remaining is not valid
- for command-line-specified names. */
- && parent->fts_n_dirs_remaining == 0
+ if (parent->fts_n_dirs_remaining == 0
&& ISSET(FTS_NOSTAT)
&& ISSET(FTS_PHYSICAL)
&& link_count_optimize_ok (parent))
@@ -1039,7 +1037,8 @@ check_for_dir:
p->fts_info = fts_stat(sp, p, false);
if (S_ISDIR(p->fts_statp->st_mode)
&& p->fts_level != FTS_ROOTLEVEL
- && parent->fts_n_dirs_remaining)
+ && 0 < parent->fts_n_dirs_remaining
+ && parent->fts_n_dirs_remaining != (nlink_t) -1)
parent->fts_n_dirs_remaining--;
}
}
@@ -1468,7 +1467,6 @@ fts_build (register FTS *sp, int type)
tail = NULL;
nitems = 0;
while (cur->fts_dirp) {
- bool is_dir;
size_t d_namelen;
__set_errno (0);
struct dirent *dp = readdir(cur->fts_dirp);
@@ -1569,19 +1567,10 @@ mem1: saved_errno = errno;
to caller, when possible. */
set_stat_type (p->fts_statp, D_TYPE (dp));
fts_set_stat_required(p, !skip_stat);
- is_dir = (ISSET(FTS_PHYSICAL)
- && DT_MUST_BE(dp, DT_DIR));
} else {
p->fts_info = fts_stat(sp, p, false);
- is_dir = (p->fts_info == FTS_D
- || p->fts_info == FTS_DC
- || p->fts_info == FTS_DOT);
}

- /* Decrement link count if applicable. */
- if (nlinks > 0 && is_dir)
- nlinks -= nostat;
-
/* We walk in directory order so "ls -f" doesn't get upset. */
p->fts_link = NULL;
if (head == NULL)
@@ -1844,8 +1833,11 @@ err: memset(sbp, 0, sizeof(struct stat));
}

if (S_ISDIR(sbp->st_mode)) {
- p->fts_n_dirs_remaining = (sbp->st_nlink
- - (ISSET(FTS_SEEDOT) ? 0 : 2));
+ p->fts_n_dirs_remaining
+ = ((sbp->st_nlink < 2
+ || p->fts_level <= FTS_ROOTLEVEL)
+ ? -1
+ : sbp->st_nlink - (ISSET (FTS_SEEDOT) ? 0 : 2));
if (ISDOT(p->fts_name)) {
/* Command-line "." and ".." are real directories. */
return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
diff --git a/lib/fts_.h b/lib/fts_.h
index 46fd0df52..e8346dafb 100644
--- a/lib/fts_.h
+++ b/lib/fts_.h
@@ -220,7 +220,11 @@ typedef struct _ftsent {
ptrdiff_t fts_level; /* depth (-1 to N) */

size_t fts_namelen; /* strlen(fts_name) */
- nlink_t fts_n_dirs_remaining; /* count down from st_nlink */
+
+ /* If not (nlink_t) -1, an upper bound on the number of
+ remaining subdirectories of interest. If this becomes
+ zero, some work can be avoided. */
+ nlink_t fts_n_dirs_remaining;

# define FTS_D 1 /* preorder directory */
# define FTS_DC 2 /* directory that causes cycles */
--
2.13.3
Paul Eggert
2017-07-25 07:28:04 UTC
Permalink
Raw Message
* lib/fts.c (struct dev_type): New struct.
(DEV_TYPE_HT_INITIAL_SIZE): New constant.
(dev_type_hash, dev_type_compare, filesystem_type): New functions.
(dirent_inode_sort_may_be_useful, leaf_optimization_applies):
Now takes FTSENT const *, not int. All uses changed. Use
filesystem_type to cache.
(link_count_optimize_ok): Remove. Caller changed to use
leaf_optimization_applies, which now uses shared cache.
---
ChangeLog | 10 ++++
lib/fts.c | 202 +++++++++++++++++++++++++++++---------------------------------
2 files changed, 106 insertions(+), 106 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 7f532d411..2c194327d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,15 @@
2017-07-24 Paul Eggert <***@cs.ucla.edu>

+ fts: cache dirent_inode_sort_may_be_useful too
+ * lib/fts.c (struct dev_type): New struct.
+ (DEV_TYPE_HT_INITIAL_SIZE): New constant.
+ (dev_type_hash, dev_type_compare, filesystem_type): New functions.
+ (dirent_inode_sort_may_be_useful, leaf_optimization_applies):
+ Now takes FTSENT const *, not int. All uses changed. Use
+ filesystem_type to cache.
+ (link_count_optimize_ok): Remove. Caller changed to use
+ leaf_optimization_applies, which now uses shared cache.
+
fts: introduce MIN_DIR_NLINK
* lib/fts.c (MIN_DIR_NLINK): New constant.
Use it instead of 2, whenever we are talking about link counts.
diff --git a/lib/fts.c b/lib/fts.c
index 95d646c1f..a8de3f910 100644
--- a/lib/fts.c
+++ b/lib/fts.c
@@ -684,27 +684,100 @@ enum { MIN_DIR_NLINK = 2 };
# define S_MAGIC_XFS 0x58465342
# define S_MAGIC_PROC 0x9FA0

-/* Return false if it is easy to determine the file system type of
- the directory on which DIR_FD is open, and sorting dirents on
- inode numbers is known not to improve traversal performance with
- that type of file system. Otherwise, return true. */
+/* Map a stat.st_dev number to a file system type number f_ftype. */
+struct dev_type
+{
+ dev_t st_dev;
+ __fsword_t f_type;
+};
+
+/* Use a tiny initial size. If a traversal encounters more than
+ a few devices, the cost of growing/rehashing this table will be
+ rendered negligible by the number of inodes processed. */
+enum { DEV_TYPE_HT_INITIAL_SIZE = 13 };
+
+static size_t
+dev_type_hash (void const *x, size_t table_size)
+{
+ struct dev_type const *ax = x;
+ uintmax_t dev = ax->st_dev;
+ return dev % table_size;
+}
+
+static bool
+dev_type_compare (void const *x, void const *y)
+{
+ struct dev_type const *ax = x;
+ struct dev_type const *ay = y;
+ return ax->st_dev == ay->st_dev;
+}
+
+/* Return the file system type of P, or 0 if not known.
+ Try to cache known values. */
+
+static __fsword_t
+filesystem_type (FTSENT const *p)
+{
+ FTS *sp = p->fts_fts;
+ Hash_table *h = sp->fts_leaf_optimization_works_ht;
+ struct dev_type *ent;
+ struct statfs fs_buf;
+
+ /* If we're not in CWDFD mode, don't bother with this optimization,
+ since the caller is not serious about performance. */
+ if (!ISSET (FTS_CWDFD))
+ return 0;
+
+ if (! h)
+ h = sp->fts_leaf_optimization_works_ht
+ = hash_initialize (DEV_TYPE_HT_INITIAL_SIZE, NULL, dev_type_hash,
+ dev_type_compare, free);
+ if (h)
+ {
+ struct dev_type tmp;
+ tmp.st_dev = p->fts_statp->st_dev;
+ ent = hash_lookup (h, &tmp);
+ if (ent)
+ return ent->f_type;
+ }
+
+ /* Look-up failed. Query directly and cache the result. */
+ if (fstatfs (p->fts_fts->fts_cwd_fd, &fs_buf) != 0)
+ return 0;
+
+ if (h)
+ {
+ struct dev_type *t2 = malloc (sizeof *t2);
+ if (t2)
+ {
+ t2->st_dev = p->fts_statp->st_dev;
+ t2->f_type = fs_buf.f_type;
+
+ ent = hash_insert (h, t2);
+ if (ent)
+ fts_assert (ent == t2);
+ else
+ free (t2);
+ }
+ }
+
+ return fs_buf.f_type;
+}
+
+/* Return false if it is easy to determine the file system type of the
+ directory P, and sorting dirents on inode numbers is known not to
+ improve traversal performance with that type of file system.
+ Otherwise, return true. */
static bool
-dirent_inode_sort_may_be_useful (int dir_fd)
+dirent_inode_sort_may_be_useful (FTSENT const *p)
{
/* Skip the sort only if we can determine efficiently
that skipping it is the right thing to do.
The cost of performing an unnecessary sort is negligible,
while the cost of *not* performing it can be O(N^2) with
a very large constant. */
- struct statfs fs_buf;
-
- /* If fstatfs fails, assume sorting would be useful. */
- if (fstatfs (dir_fd, &fs_buf) != 0)
- return true;

- /* FIXME: what about when f_type is not an integral type?
- deal with that if/when it's encountered. */
- switch (fs_buf.f_type)
+ switch (filesystem_type (p))
{
case S_MAGIC_TMPFS:
case S_MAGIC_NFS:
@@ -717,25 +790,19 @@ dirent_inode_sort_may_be_useful (int dir_fd)
}
}

-/* Given a file descriptor DIR_FD open on a directory D,
+/* Given an FTS entry P for a directory D,
return true if it is both useful and valid to apply leaf optimization.
The optimization is useful only for file systems that lack usable
dirent.d_type info. The optimization is valid if an st_nlink value
of at least MIN_DIR_NLINK is an upper bound on the number of
subdirectories of D, counting "." and ".." as subdirectories. */
static bool
-leaf_optimization_applies (int dir_fd)
+leaf_optimization_applies (FTSENT const *p)
{
- struct statfs fs_buf;
-
- /* If fstatfs fails, assume we can't use the optimization. */
- if (fstatfs (dir_fd, &fs_buf) != 0)
- return false;
-
/* FIXME: do we need to detect AFS mount points? I doubt it,
unless fstatfs can report S_MAGIC_REISERFS for such a directory. */

- switch (fs_buf.f_type)
+ switch (filesystem_type (p))
{
/* List here the file system types that lack usable dirent.d_type
info, yet for which the optimization does apply. */
@@ -762,92 +829,16 @@ leaf_optimization_applies (int dir_fd)

#else
static bool
-dirent_inode_sort_may_be_useful (int dir_fd _GL_UNUSED) { return true; }
-static bool
-leaf_optimization_applies (int dir_fd _GL_UNUSED) { return false; }
-#endif
-
-/* link-count-optimization entry:
- map a stat.st_dev number to a boolean: leaf_optimization_works */
-struct LCO_ent
+dirent_inode_sort_may_be_useful (FTSENT const *p _GL_UNUSED)
{
- dev_t st_dev;
- bool opt_ok;
-};
-
-/* Use a tiny initial size. If a traversal encounters more than
- a few devices, the cost of growing/rehashing this table will be
- rendered negligible by the number of inodes processed. */
-enum { LCO_HT_INITIAL_SIZE = 13 };
-
-static size_t
-LCO_hash (void const *x, size_t table_size)
-{
- struct LCO_ent const *ax = x;
- return (uintmax_t) ax->st_dev % table_size;
+ return true;
}
-
static bool
-LCO_compare (void const *x, void const *y)
+leaf_optimization_applies (FTSENT const *p _GL_UNUSED)
{
- struct LCO_ent const *ax = x;
- struct LCO_ent const *ay = y;
- return ax->st_dev == ay->st_dev;
-}
-
-/* Ask the same question as leaf_optimization_applies, but query
- the cache first (FTS.fts_leaf_optimization_works_ht), and if necessary,
- update that cache. */
-static bool
-link_count_optimize_ok (FTSENT const *p)
-{
- FTS *sp = p->fts_fts;
- Hash_table *h = sp->fts_leaf_optimization_works_ht;
- struct LCO_ent tmp;
- struct LCO_ent *ent;
- bool opt_ok;
- struct LCO_ent *t2;
-
- /* If we're not in CWDFD mode, don't bother with this optimization,
- since the caller is not serious about performance. */
- if (!ISSET(FTS_CWDFD))
- return false;
-
- /* map st_dev to the boolean, leaf_optimization_works */
- if (h == NULL)
- {
- h = sp->fts_leaf_optimization_works_ht
- = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash,
- LCO_compare, free);
- if (h == NULL)
- return false;
- }
- tmp.st_dev = p->fts_statp->st_dev;
- ent = hash_lookup (h, &tmp);
- if (ent)
- return ent->opt_ok;
-
- /* Look-up failed. Query directly and cache the result. */
- t2 = malloc (sizeof *t2);
- if (t2 == NULL)
- return false;
-
- /* Is it ok to perform the optimization in the dir, FTS_CWD_FD? */
- opt_ok = leaf_optimization_applies (sp->fts_cwd_fd);
- t2->opt_ok = opt_ok;
- t2->st_dev = p->fts_statp->st_dev;
-
- ent = hash_insert (h, t2);
- if (ent == NULL)
- {
- /* insertion failed */
- free (t2);
- return false;
- }
- fts_assert (ent == t2);
-
- return opt_ok;
+ return false;
}
+#endif

/*
* Special case of "/" at the end of the file name so that slashes aren't
@@ -1037,7 +1028,7 @@ check_for_dir:
if (parent->fts_n_dirs_remaining == 0
&& ISSET(FTS_NOSTAT)
&& ISSET(FTS_PHYSICAL)
- && link_count_optimize_ok (parent))
+ && leaf_optimization_applies (parent))
{
/* nothing more needed */
}
@@ -1651,8 +1642,7 @@ mem1: saved_errno = errno;
inode numbers. */
if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
&& !sp->fts_compar
- && ISSET (FTS_CWDFD)
- && dirent_inode_sort_may_be_useful (sp->fts_cwd_fd)) {
+ && dirent_inode_sort_may_be_useful (cur)) {
sp->fts_compar = fts_compare_ino;
head = fts_sort (sp, head, nitems);
sp->fts_compar = NULL;
--
2.13.3
Tom G. Christensen
2017-08-09 10:22:07 UTC
Permalink
Raw Message
Post by Paul Eggert
* lib/fts.c (struct dev_type): New struct.
(DEV_TYPE_HT_INITIAL_SIZE): New constant.
(dev_type_hash, dev_type_compare, filesystem_type): New functions.
Now takes FTSENT const *, not int. All uses changed. Use
filesystem_type to cache.
(link_count_optimize_ok): Remove. Caller changed to use
leaf_optimization_applies, which now uses shared cache.
This broke the build on CentOS 6 since it has glibc 2.12 which is from
before the introduction of the internal __fsword_t type.

gcc -std=gnu99 -DHAVE_CONFIG_H -DEXEEXT=\"\" -DEXEEXT=\"\"
-DNO_XMALLOC -DEXEEXT=\"\" -I. -I.. -DGNULIB_STRICT_CHECKING=1
-fvisibility=hidden -g -O2 -Wall -MT fts.o -MD -MP -MF $depbase.Tpo -c
-o fts.o fts.c &&\
mv -f $depbase.Tpo $depbase.Po
fts.c:706: error: expected specifier-qualifier-list before '__fsword_t'
fts.c:734: error: expected '=', ',', ';', 'asm' or '__attribute__'
before 'filesystem_type'
fts.c: In function 'dirent_inode_sort_may_be_useful':
fts.c:795: warning: implicit declaration of function 'filesystem_type'
make[4]: *** [fts.o] Error 1

-tgc
Paul Eggert
2017-08-10 13:10:24 UTC
Permalink
Raw Message
This broke the build on CentOS 6 since it has glibc 2.12 which is from before
the introduction of the internal __fsword_t type.
Thanks for reporting that. I reproduced the problem on a nearby old server and
fixed it by installing the attached patch.
Tom G. Christensen
2017-08-11 18:21:04 UTC
Permalink
Raw Message
Post by Paul Eggert
Post by Tom G. Christensen
This broke the build on CentOS 6 since it has glibc 2.12 which is from
before the introduction of the internal __fsword_t type.
Thanks for reporting that. I reproduced the problem on a nearby old
server and fixed it by installing the attached patch.
Thank you.

This exposed another problem when using external gettext:
/usr/tgcware/gcc45/bin/gcc -std=gnu99 -g -O2 -L/usr/tgcware/lib
-R/usr/tgcware/lib -o test-fts test-
fts.o ../gllib/libgnu.a -lm -lm -lm -lm -lm -lm
Undefined first referenced
symbol in file
libintl_gettext ../gllib/libgnu.a(openat-die.o)
ld: fatal: Symbol referencing errors. No output written to test-fts
collect2: ld returned 1 exit status
make[4]: *** [test-fts] Error 1

-tgc
Bruno Haible
2017-08-11 18:46:23 UTC
Permalink
Raw Message
Post by Tom G. Christensen
/usr/tgcware/gcc45/bin/gcc -std=gnu99 -g -O2 -L/usr/tgcware/lib
-R/usr/tgcware/lib -o test-fts test-
fts.o ../gllib/libgnu.a -lm -lm -lm -lm -lm -lm
Undefined first referenced
symbol in file
libintl_gettext ../gllib/libgnu.a(openat-die.o)
ld: fatal: Symbol referencing errors. No output written to test-fts
collect2: ld returned 1 exit status
make[4]: *** [test-fts] Error 1
This should fix it:


2017-08-11 Bruno Haible <***@clisp.org>

fts tests: Fix link error.
Reported by Tom G. Christensen in
https://lists.gnu.org/archive/html/bug-gnulib/2017-08/msg00078.html
* modules/fts-tests (Makefile.am): Link test-fts against LIBINTL.

diff --git a/modules/fts-tests b/modules/fts-tests
index 115bf66..1651290 100644
--- a/modules/fts-tests
+++ b/modules/fts-tests
@@ -11,3 +11,4 @@ configure.ac:
Makefile.am:
TESTS += test-fts
check_PROGRAMS += test-fts
+test_fts_LDADD = $(LDADD) @LIBINTL@
Paul Eggert
2017-08-11 19:56:12 UTC
Permalink
Raw Message
Ah, thanks, please ignore my previous message on this topic.

Paul Eggert
2017-08-11 19:54:27 UTC
Permalink
Raw Message
Post by Tom G. Christensen
/usr/tgcware/gcc45/bin/gcc -std=gnu99 -g -O2 -L/usr/tgcware/lib
-R/usr/tgcware/lib -o test-fts test-
fts.o ../gllib/libgnu.a -lm -lm -lm -lm -lm -lm
Undefined first referenced
symbol in file
libintl_gettext ../gllib/libgnu.a(openat-die.o)
Thanks, was this also on CentOS 6? I could not reproduce the problem on
RHEL 6.9, via the following recipe. I am using the bundled GCC, which
says it is version 4.4.7 20120313 (Red Hat 4.4.7-18). What am I doing wrong?


./gnulib-tool --create-testdir --dir foo gettext-h fts

cd foo

./configure

make

make check
Paul Eggert
2017-07-25 07:28:03 UTC
Permalink
Raw Message
* lib/fts.c (MIN_DIR_NLINK): New constant.
Use it instead of 2, whenever we are talking about link counts.
---
ChangeLog | 4 ++++
lib/fts.c | 19 ++++++++++++++-----
2 files changed, 18 insertions(+), 5 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index da1fda1ad..7f532d411 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
2017-07-24 Paul Eggert <***@cs.ucla.edu>

+ fts: introduce MIN_DIR_NLINK
+ * lib/fts.c (MIN_DIR_NLINK): New constant.
+ Use it instead of 2, whenever we are talking about link counts.
+
fts: nlink_t signedness fixups
* lib/fts.c (fts_open): Set rootparent n_dirs_remaining to -1
so that root need not be a special case later.
diff --git a/lib/fts.c b/lib/fts.c
index d5fc051a0..95d646c1f 100644
--- a/lib/fts.c
+++ b/lib/fts.c
@@ -666,6 +666,12 @@ fts_close (FTS *sp)
return (0);
}

+/* Minimum link count of a traditional Unix directory. When leaf
+ optimization is OK and MIN_DIR_NLINK <= st_nlink, then st_nlink is
+ an upper bound on the number of subdirectories (counting "." and
+ ".."). */
+enum { MIN_DIR_NLINK = 2 };
+
#if defined __linux__ \
&& HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE

@@ -712,8 +718,11 @@ dirent_inode_sort_may_be_useful (int dir_fd)
}

/* Given a file descriptor DIR_FD open on a directory D,
- return true if it is valid to apply the leaf-optimization
- technique of counting directories in D via stat.st_nlink. */
+ return true if it is both useful and valid to apply leaf optimization.
+ The optimization is useful only for file systems that lack usable
+ dirent.d_type info. The optimization is valid if an st_nlink value
+ of at least MIN_DIR_NLINK is an upper bound on the number of
+ subdirectories of D, counting "." and ".." as subdirectories. */
static bool
leaf_optimization_applies (int dir_fd)
{
@@ -1389,7 +1398,7 @@ fts_build (register FTS *sp, int type)
nostat = false;
} else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
nlinks = (cur->fts_statp->st_nlink
- - (ISSET(FTS_SEEDOT) ? 0 : 2));
+ - (ISSET (FTS_SEEDOT) ? 0 : MIN_DIR_NLINK));
nostat = true;
} else {
nlinks = -1;
@@ -1834,10 +1843,10 @@ err: memset(sbp, 0, sizeof(struct stat));

if (S_ISDIR(sbp->st_mode)) {
p->fts_n_dirs_remaining
- = ((sbp->st_nlink < 2
+ = ((sbp->st_nlink < MIN_DIR_NLINK
|| p->fts_level <= FTS_ROOTLEVEL)
? -1
- : sbp->st_nlink - (ISSET (FTS_SEEDOT) ? 0 : 2));
+ : sbp->st_nlink - (ISSET (FTS_SEEDOT) ? 0 : MIN_DIR_NLINK));
if (ISDOT(p->fts_name)) {
/* Command-line "." and ".." are real directories. */
return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
--
2.13.3
Paul Eggert
2017-07-25 07:28:06 UTC
Permalink
Raw Message
* lib/fts.c (fts_build): Simplify, and be lazier about
calling leaf_optimization.
---
ChangeLog | 4 ++++
lib/fts.c | 40 +++++++++++++++-------------------------
2 files changed, 19 insertions(+), 25 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index cbe4c9e27..ae2b049b4 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
2017-07-24 Paul Eggert <***@cs.ucla.edu>

+ fts: simplify fts_build
+ * lib/fts.c (fts_build): Simplify, and be lazier about
+ calling leaf_optimization.
+
fts: three levels of leaf optimization
* lib/fts.c (enum leaf_optimization): New type with three values.
(S_MAGIC_AFS): New macro. Sort them.
diff --git a/lib/fts.c b/lib/fts.c
index 663a09b5e..790f71c46 100644
--- a/lib/fts.c
+++ b/lib/fts.c
@@ -1326,8 +1326,6 @@ fts_build (register FTS *sp, int type)
bool descend;
bool doadjust;
ptrdiff_t level;
- nlink_t nlinks;
- bool nostat;
size_t len, maxlen, new_len;
char *cp;
int dir_fd;
@@ -1398,25 +1396,6 @@ fts_build (register FTS *sp, int type)
max_entries = sp->fts_compar ? SIZE_MAX : FTS_MAX_READDIR_ENTRIES;

/*
- * Nlinks is the number of possible entries of type directory in the
- * directory if we're cheating on stat calls, 0 if we're not doing
- * any stat calls at all, (nlink_t) -1 if we're statting everything.
- */
- if (type == BNAMES) {
- nlinks = 0;
- /* Be quiet about nostat, GCC. */
- nostat = false;
- } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)
- && leaf_optimization (cur) != NO_LEAF_OPTIMIZATION) {
- nlinks = (cur->fts_statp->st_nlink
- - (ISSET (FTS_SEEDOT) ? 0 : MIN_DIR_NLINK));
- nostat = true;
- } else {
- nlinks = -1;
- nostat = false;
- }
-
- /*
* If we're going to need to stat anything or we want to descend
* and stay in the directory, chdir. If this fails we keep going,
* but set a flag so we don't chdir after the post-order visit.
@@ -1437,7 +1416,18 @@ fts_build (register FTS *sp, int type)
the required dirp and dir_fd. */
descend = true;
}
- else if (nlinks || type == BREAD) {
+ else
+ {
+ /* Try to descend unless it is a names-only fts_children,
+ or the directory is a known to lack subdirectories. */
+ descend = (type != BNAMES
+ && ! (ISSET (FTS_NOSTAT) && ISSET (FTS_PHYSICAL)
+ && ! ISSET (FTS_SEEDOT)
+ && cur->fts_statp->st_nlink == MIN_DIR_NLINK
+ && (leaf_optimization (cur)
+ != NO_LEAF_OPTIMIZATION)));
+ if (descend || type == BREAD)
+ {
if (ISSET(FTS_CWDFD))
{
dir_fd = dup (dir_fd);
@@ -1445,7 +1435,7 @@ fts_build (register FTS *sp, int type)
set_cloexec_flag (dir_fd, true);
}
if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
- if (nlinks && type == BREAD)
+ if (descend && type == BREAD)
cur->fts_errno = errno;
cur->fts_flags |= FTS_DONTCHDIR;
descend = false;
@@ -1455,8 +1445,8 @@ fts_build (register FTS *sp, int type)
cur->fts_dirp = NULL;
} else
descend = true;
- } else
- descend = false;
+ }
+ }

/*
* Figure out the max file name length that can be stored in the
--
2.13.3
Paul Eggert
2017-07-25 07:28:05 UTC
Permalink
Raw Message
* lib/fts.c (enum leaf_optimization): New type with three values.
(S_MAGIC_AFS): New macro. Sort them.
(leaf_optimization): Rename from leaf_optimization_applies, and
return enum leaf_optimization instead of bool. All uses changed.
Add cases for unknown type and for AFS.
(fts_build): Don’t rely on link counts if NO_LEAF_OPTIMIZATION.
---
ChangeLog | 8 ++++++++
lib/fts.c | 54 +++++++++++++++++++++++++++++++++++++-----------------
2 files changed, 45 insertions(+), 17 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 2c194327d..cbe4c9e27 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,13 @@
2017-07-24 Paul Eggert <***@cs.ucla.edu>

+ fts: three levels of leaf optimization
+ * lib/fts.c (enum leaf_optimization): New type with three values.
+ (S_MAGIC_AFS): New macro. Sort them.
+ (leaf_optimization): Rename from leaf_optimization_applies, and
+ return enum leaf_optimization instead of bool. All uses changed.
+ Add cases for unknown type and for AFS.
+ (fts_build): Don’t rely on link counts if NO_LEAF_OPTIMIZATION.
+
fts: cache dirent_inode_sort_may_be_useful too
* lib/fts.c (struct dev_type): New struct.
(DEV_TYPE_HT_INITIAL_SIZE): New constant.
diff --git a/lib/fts.c b/lib/fts.c
index a8de3f910..663a09b5e 100644
--- a/lib/fts.c
+++ b/lib/fts.c
@@ -672,17 +672,32 @@ fts_close (FTS *sp)
".."). */
enum { MIN_DIR_NLINK = 2 };

+/* Whether leaf optimization is OK for a directory. */
+enum leaf_optimization
+ {
+ /* st_nlink is not reliable for this directory's subdirectories. */
+ NO_LEAF_OPTIMIZATION,
+
+ /* Leaf optimization is OK, but is not useful for avoiding stat calls. */
+ OK_LEAF_OPTIMIZATION,
+
+ /* Leaf optimization is not only OK: it is useful for avoiding
+ stat calls, because dirent.d_type does not work. */
+ NOSTAT_LEAF_OPTIMIZATION
+ };
+
#if defined __linux__ \
&& HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE

# include <sys/vfs.h>

/* Linux-specific constants from coreutils' src/fs.h */
-# define S_MAGIC_TMPFS 0x1021994
+# define S_MAGIC_AFS 0x5346414F
# define S_MAGIC_NFS 0x6969
+# define S_MAGIC_PROC 0x9FA0
# define S_MAGIC_REISERFS 0x52654973
+# define S_MAGIC_TMPFS 0x1021994
# define S_MAGIC_XFS 0x58465342
-# define S_MAGIC_PROC 0x9FA0

/* Map a stat.st_dev number to a file system type number f_ftype. */
struct dev_type
@@ -796,22 +811,24 @@ dirent_inode_sort_may_be_useful (FTSENT const *p)
dirent.d_type info. The optimization is valid if an st_nlink value
of at least MIN_DIR_NLINK is an upper bound on the number of
subdirectories of D, counting "." and ".." as subdirectories. */
-static bool
-leaf_optimization_applies (FTSENT const *p)
+static enum leaf_optimization
+leaf_optimization (FTSENT const *p)
{
- /* FIXME: do we need to detect AFS mount points? I doubt it,
- unless fstatfs can report S_MAGIC_REISERFS for such a directory. */
-
switch (filesystem_type (p))
{
/* 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 true;
+ return NOSTAT_LEAF_OPTIMIZATION;

- /* Explicitly list here any other file system type for which the
- optimization is not applicable, but need documentation. */
+ case 0:
+ /* Leaf optimization is unsafe if the file system type is unknown. */
+ FALLTHROUGH;
+ case S_MAGIC_AFS:
+ /* Although AFS mount points are not counted in st_nlink, they
+ act like directories. See <https://bugs.debian.org/143111>. */
+ FALLTHROUGH;
case S_MAGIC_NFS:
/* NFS provides usable dirent.d_type but not necessarily for all entries
of large directories, so as per <https://bugzilla.redhat.com/1252549>
@@ -821,9 +838,10 @@ leaf_optimization_applies (FTSENT const *p)
case S_MAGIC_PROC:
/* Per <http://bugs.debian.org/143111> /proc may have
bogus stat.st_nlink values. */
- FALLTHROUGH;
+ return NO_LEAF_OPTIMIZATION;
+
default:
- return false;
+ return OK_LEAF_OPTIMIZATION;
}
}

@@ -833,10 +851,10 @@ dirent_inode_sort_may_be_useful (FTSENT const *p _GL_UNUSED)
{
return true;
}
-static bool
-leaf_optimization_applies (FTSENT const *p _GL_UNUSED)
+static enum leaf_optimization
+leaf_optimization (FTSENT const *p _GL_UNUSED)
{
- return false;
+ return NO_LEAF_OPTIMIZATION;
}
#endif

@@ -1028,7 +1046,8 @@ check_for_dir:
if (parent->fts_n_dirs_remaining == 0
&& ISSET(FTS_NOSTAT)
&& ISSET(FTS_PHYSICAL)
- && leaf_optimization_applies (parent))
+ && (leaf_optimization (parent)
+ == NOSTAT_LEAF_OPTIMIZATION))
{
/* nothing more needed */
}
@@ -1387,7 +1406,8 @@ fts_build (register FTS *sp, int type)
nlinks = 0;
/* Be quiet about nostat, GCC. */
nostat = false;
- } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
+ } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)
+ && leaf_optimization (cur) != NO_LEAF_OPTIMIZATION) {
nlinks = (cur->fts_statp->st_nlink
- (ISSET (FTS_SEEDOT) ? 0 : MIN_DIR_NLINK));
nostat = true;
--
2.13.3
Loading...