/* Traverse a file hierarchy.
- Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
- This program is free software; you can redistribute it and/or modify
+ 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 2, or (at your option)
- any later version.
+ 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
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, write to the Free Software Foundation,
- Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
/*-
* Copyright (c) 1990, 1993, 1994
* SUCH DAMAGE.
*/
-#ifdef HAVE_CONFIG_H
-# include <config.h>
-#endif
+#include <config.h>
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94";
# include "lstat.h"
# include "openat.h"
# include "unistd--.h"
+# include "same-inode.h"
#endif
#include <dirent.h>
# define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
#endif
+#if HAVE_STRUCT_DIRENT_D_TYPE
+/* True if the type of the directory entry D is known. */
+# define DT_IS_KNOWN(d) ((d)->d_type != DT_UNKNOWN)
+/* True if the type of the directory entry D must be T. */
+# define DT_MUST_BE(d, t) ((d)->d_type == (t))
+#else
+# define DT_IS_KNOWN(d) false
+# define DT_MUST_BE(d, t) false
+#endif
+
+enum Fts_stat
+{
+ FTS_NO_STAT_REQUIRED = 1,
+ FTS_STAT_REQUIRED = 2
+};
+
#ifdef _LIBC
# undef close
# define close __close
# define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
#endif
-#if !defined O_NOFOLLOW
-# define O_NOFOLLOW 0
-#endif
-
/* If this host provides the openat function, then we can avoid
attempting to open "." in some initialization code below. */
#ifdef HAVE_OPENAT
# define HAVE_OPENAT_SUPPORT 0
#endif
+#ifdef NDEBUG
+# define fts_assert(expr) ((void) 0)
+#else
+# define fts_assert(expr) \
+ do \
+ { \
+ if (!(expr)) \
+ abort (); \
+ } \
+ while (false)
+#endif
+
static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
static FTSENT *fts_build (FTS *, int) internal_function;
static void fts_lfree (FTSENT *) internal_function;
static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
internal_function;
-#if _LGPL_PACKAGE
+#if GNULIB_FTS
+# include "fts-cycle.c"
+#else
static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
static void leave_dir (FTS *fts, FTSENT *ent) {}
static bool setup_dir (FTS *fts) { return true; }
static void free_dir (FTS *fts) {}
-#else
-# include "fcntl--.h"
-# include "fts-cycle.c"
#endif
#ifndef MAX
#define ISSET(opt) (sp->fts_options & (opt))
#define SET(opt) (sp->fts_options |= (opt))
-#define RESTORE_INITIAL_CWD(sp) FCHDIR (sp, (ISSET (FTS_CWDFD) \
- ? AT_FDCWD \
- : sp->fts_rfd))
+/* FIXME: make this a function */
+#define RESTORE_INITIAL_CWD(sp) \
+ (fd_ring_clear (&((sp)->fts_fd_ring)), \
+ FCHDIR ((sp), (ISSET (FTS_CWDFD) ? AT_FDCWD : (sp)->fts_rfd)))
-#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) \
- && (ISSET(FTS_CWDFD) \
- ? (cwd_advance_fd (sp, fd), 0) \
- : fchdir(fd)))
+/* FIXME: FTS_NOCHDIR is now misnamed.
+ Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
+#define FCHDIR(sp, fd) \
+ (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \
+ ? (cwd_advance_fd ((sp), (fd), true), 0) \
+ : fchdir (fd)))
/* fts_build flags */
+/* FIXME: make this an enum */
#define BCHILD 1 /* fts_children */
#define BNAMES 2 /* fts_children, names only */
#define BREAD 3 /* fts_read */
# include <inttypes.h>
# include <stdint.h>
# include <stdio.h>
+# include "getcwdat.h"
bool fts_debug = false;
-# define Dprintf(x) do { if (fts_debug) printf x; } while (0)
+# define Dprintf(x) do { if (fts_debug) printf x; } while (false)
#else
# define Dprintf(x)
+# define fd_ring_check(x)
+# define fd_ring_print(a, b, c)
#endif
#define LEAVE_DIR(Fts, Ent, Tag) \
{ \
Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
leave_dir (Fts, Ent); \
+ fd_ring_check (Fts); \
} \
while (false)
+static void
+fd_ring_clear (I_ring *fd_ring)
+{
+ while ( ! i_ring_empty (fd_ring))
+ {
+ int fd = i_ring_pop (fd_ring);
+ if (0 <= fd)
+ close (fd);
+ }
+}
+
+/* Overload the fts_statp->st_size member (otherwise unused, when
+ fts_info is FTS_NSOK) to indicate whether fts_read should stat
+ this entry or not. */
+static void
+fts_set_stat_required (FTSENT *p, bool required)
+{
+ fts_assert (p->fts_info == FTS_NSOK);
+ p->fts_statp->st_size = (required
+ ? FTS_STAT_REQUIRED
+ : FTS_NO_STAT_REQUIRED);
+}
+
/* file-descriptor-relative opendir. */
/* FIXME: if others need this function, move it into lib/openat.c */
static inline DIR *
return dirp;
}
-/* Virtual fchdir. Advance SP's working directory
- file descriptor, SP->fts_cwd_fd, to FD, and close
- the previous one, ignoring any error. */
+/* Virtual fchdir. Advance SP's working directory file descriptor,
+ SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
+ CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
+ open on sp->fts_cwd_fd; i.e., to move the working directory one level
+ down. */
static void
internal_function
-cwd_advance_fd (FTS *sp, int fd)
+cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
{
int old = sp->fts_cwd_fd;
- if (old == fd && old != AT_FDCWD)
- abort ();
+ fts_assert (old != fd || old == AT_FDCWD);
+
+ if (chdir_down_one)
+ {
+ /* Push "old" onto the ring.
+ If the displaced file descriptor is non-negative, close it. */
+ int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);
+ fd_ring_print (sp, stderr, "post-push");
+ if (0 <= prev_fd_in_slot)
+ close (prev_fd_in_slot); /* ignore any close failure */
+ }
+ else if ( ! ISSET (FTS_NOCHDIR))
+ {
+ if (0 <= old)
+ close (old); /* ignore any close failure */
+ }
+
sp->fts_cwd_fd = fd;
- if (0 <= old)
- close (old); /* ignore any close failure */
}
/* Open the directory DIR if possible, and return a file
FTSENT *parent = NULL;
FTSENT *tmp = NULL; /* pacify gcc */
size_t len;
+ bool defer_stat;
/* Options check. */
if (options & ~FTS_OPTIONMASK) {
openat via /proc, this technique can still fail, but
only in extreme conditions, e.g., when the working
directory cannot be saved (i.e. save_cwd fails) --
- and that happens only on Linux only when "." is unreadable
+ and that happens on Linux only when "." is unreadable
and the CWD would be longer than PATH_MAX.
FIXME: once Linux kernel openat support is well established,
replace the above open call and this entire if/else block
parent->fts_level = FTS_ROOTPARENTLEVEL;
}
+ /* The classic fts implementation would call fts_stat with
+ a new entry for each iteration of the loop below.
+ If the comparison function is not specified or if the
+ FTS_DEFER_STAT option is in effect, don't stat any entry
+ in this loop. This is an attempt to minimize the interval
+ between the initial stat/lstat/fstatat and the point at which
+ a directory argument is first opened. This matters for any
+ directory command line argument that resides on a file system
+ without genuine i-nodes. If you specify FTS_DEFER_STAT along
+ with a comparison function, that function must not access any
+ data via the fts_statp pointer. */
+ defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));
+
/* Allocate/initialize root(s). */
for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
/* Don't allow zero-length file names. */
p->fts_level = FTS_ROOTLEVEL;
p->fts_parent = parent;
p->fts_accpath = p->fts_name;
- p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW) != 0);
-
- /* Command-line "." and ".." are real directories. */
- if (p->fts_info == FTS_DOT)
- p->fts_info = FTS_D;
+ /* Even when defer_stat is true, be sure to stat the first
+ command line argument, since fts_read (at least with
+ FTS_XDEV) requires that. */
+ if (defer_stat && root != NULL) {
+ p->fts_info = FTS_NSOK;
+ fts_set_stat_required(p, true);
+ } else {
+ p->fts_info = fts_stat(sp, p, false);
+ }
/*
* If comparison routine supplied, traverse in sorted
sp->fts_cur->fts_link = root;
sp->fts_cur->fts_info = FTS_INIT;
if (! setup_dir (sp))
- goto mem3;
+ goto mem3;
/*
* If using chdir(2), grab a file descriptor pointing to dot to ensure
&& (sp->fts_rfd = diropen (sp, ".")) < 0)
SET(FTS_NOCHDIR);
+ i_ring_init (&sp->fts_fd_ring, -1);
return (sp);
mem3: fts_lfree(root);
p->fts_namelen = len;
}
p->fts_accpath = p->fts_path = sp->fts_path;
- sp->fts_dev = p->fts_statp->st_dev;
}
int
/* Free up child linked list, sort array, file name buffer. */
if (sp->fts_child)
fts_lfree(sp->fts_child);
- if (sp->fts_array)
- free(sp->fts_array);
+ free(sp->fts_array);
free(sp->fts_path);
if (ISSET(FTS_CWDFD))
close(sp->fts_rfd);
}
+ fd_ring_clear (&sp->fts_fd_ring);
free_dir (sp);
/* Free up the stream pointer. */
/* If fts_build's call to fts_safe_changedir failed
because it was not able to fchdir into a
subdirectory, tell the caller. */
- if (p->fts_errno)
+ if (p->fts_errno && p->fts_info != FTS_DNR)
p->fts_info = FTS_ERR;
LEAVE_DIR (sp, p, "2");
return (p);
/* Move to the next node on this level. */
next: tmp = p;
if ((p = p->fts_link) != NULL) {
+ sp->fts_cur = p;
free(tmp);
/*
if (p->fts_level == FTS_ROOTLEVEL) {
if (RESTORE_INITIAL_CWD(sp)) {
SET(FTS_STOP);
- sp->fts_cur = p;
return (NULL);
}
fts_load(sp, p);
memmove(t, p->fts_name, p->fts_namelen + 1);
check_for_dir:
sp->fts_cur = p;
+ if (p->fts_info == FTS_NSOK)
+ {
+ if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
+ p->fts_info = fts_stat(sp, p, false);
+ else
+ fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
+ }
+
if (p->fts_info == FTS_D)
{
- Dprintf ((" %s-entering: %s\n", sp, p->fts_path));
+ /* Now that P->fts_statp is guaranteed to be valid,
+ if this is a command-line directory, record its
+ device number, to be used for FTS_XDEV. */
+ if (p->fts_level == FTS_ROOTLEVEL)
+ sp->fts_dev = p->fts_statp->st_dev;
+ Dprintf ((" entering: %s\n", p->fts_path));
if (! enter_dir (sp, p))
{
__set_errno (ENOMEM);
/* Move up to the parent node. */
p = tmp->fts_parent;
+ sp->fts_cur = p;
free(tmp);
if (p->fts_level == FTS_ROOTPARENTLEVEL) {
return (sp->fts_cur = NULL);
}
+ fts_assert (p->fts_info != FTS_NSOK);
+
/* NUL terminate the file name. */
sp->fts_path[p->fts_pathlen] = '\0';
p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
if (p->fts_errno == 0)
LEAVE_DIR (sp, p, "3");
- sp->fts_cur = p;
return ISSET(FTS_STOP) ? NULL : p;
}
sp->fts_child = fts_build(sp, instr);
if (ISSET(FTS_CWDFD))
{
- cwd_advance_fd (sp, fd);
+ cwd_advance_fd (sp, fd, true);
}
else
{
}
return (NULL);
}
+ /* Rather than calling fts_stat for each and every entry encountered
+ in the readdir loop (below), stat each directory only right after
+ opening it. */
+ if (cur->fts_info == FTS_NSOK)
+ cur->fts_info = fts_stat(sp, cur, false);
/*
* Nlinks is the number of possible entries of type directory in the
/* Read the directory, attaching each entry to the `link' pointer. */
doadjust = false;
for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
+ bool is_dir;
+
if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
continue;
* structures already allocated.
*/
mem1: saved_errno = errno;
- if (p)
- free(p);
+ free(p);
fts_lfree(head);
closedir(dirp);
cur->fts_info = FTS_ERR;
memmove(cp, p->fts_name, p->fts_namelen + 1);
} else
p->fts_accpath = p->fts_name;
- /* Stat it. */
- p->fts_info = fts_stat(sp, p, false);
+
+ if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {
+ /* Record what fts_read will have to do with this
+ entry. In many cases, it will simply fts_stat it,
+ but we can take advantage of any d_type information
+ to optimize away the unnecessary stat calls. I.e.,
+ if FTS_NOSTAT is in effect and we're not following
+ symlinks (FTS_PHYSICAL) and d_type indicates this
+ is *not* a directory, then we won't have to stat it
+ at all. If it *is* a directory, then (currently)
+ we stat it regardless, in order to get device and
+ inode numbers. Some day we might optimize that
+ away, too, for directories where d_ino is known to
+ be valid. */
+ bool skip_stat = (ISSET(FTS_PHYSICAL)
+ && ISSET(FTS_NOSTAT)
+ && DT_IS_KNOWN(dp)
+ && ! DT_MUST_BE(dp, DT_DIR));
+ p->fts_info = FTS_NSOK;
+ fts_set_stat_required(p, !skip_stat);
+ is_dir = (ISSET(FTS_PHYSICAL) && ISSET(FTS_NOSTAT)
+ && 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 && (p->fts_info == FTS_D ||
- p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
+ if (nlinks > 0 && is_dir)
nlinks -= nostat;
/* We walk in directory order so "ls -f" doesn't get upset. */
}
}
}
+
+static bool
+same_fd (int fd1, int fd2)
+{
+ struct stat sb1, sb2;
+ return (fstat (fd1, &sb1) == 0
+ && fstat (fd2, &sb2) == 0
+ && SAME_INODE (sb1, sb2));
+}
+
+static void
+fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
+{
+ I_ring const *fd_ring = &sp->fts_fd_ring;
+ unsigned int i = fd_ring->fts_front;
+ char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0);
+ fprintf (stream, "=== %s ========== %s\n", msg, cwd);
+ free (cwd);
+ if (i_ring_empty (fd_ring))
+ return;
+
+ while (true)
+ {
+ int fd = fd_ring->fts_fd_ring[i];
+ if (fd < 0)
+ fprintf (stream, "%d: %d:\n", i, fd);
+ else
+ {
+ char *wd = getcwdat (fd, NULL, 0);
+ fprintf (stream, "%d: %d: %s\n", i, fd, wd);
+ free (wd);
+ }
+ if (i == fd_ring->fts_back)
+ break;
+ i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
+ }
+}
+
+/* Ensure that each file descriptor on the fd_ring matches a
+ parent, grandparent, etc. of the current working directory. */
+static void
+fd_ring_check (FTS const *sp)
+{
+ if (!fts_debug)
+ return;
+
+ /* Make a writable copy. */
+ I_ring fd_w = sp->fts_fd_ring;
+
+ int cwd_fd = sp->fts_cwd_fd;
+ cwd_fd = dup (cwd_fd);
+ char *dot = getcwdat (cwd_fd, NULL, 0);
+ error (0, 0, "===== check ===== cwd: %s", dot);
+ free (dot);
+ while ( ! i_ring_empty (&fd_w))
+ {
+ int fd = i_ring_pop (&fd_w);
+ if (0 <= fd)
+ {
+ int parent_fd = openat (cwd_fd, "..", O_RDONLY);
+ if (parent_fd < 0)
+ {
+ // Warn?
+ break;
+ }
+ if (!same_fd (fd, parent_fd))
+ {
+ char *cwd = getcwdat (fd, NULL, 0);
+ error (0, errno, "ring : %s", cwd);
+ char *c2 = getcwdat (parent_fd, NULL, 0);
+ error (0, errno, "parent: %s", c2);
+ free (cwd);
+ free (c2);
+ fts_assert (0);
+ }
+ close (cwd_fd);
+ cwd_fd = parent_fd;
+ }
+ }
+ close (cwd_fd);
+}
#endif
static unsigned short int
struct stat *sbp = p->fts_statp;
int saved_errno;
+ if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
+ follow = true;
+
#if defined FTS_WHITEOUT && 0
/* check for whiteout */
if (p->fts_flags & FTS_ISW) {
}
if (S_ISDIR(sbp->st_mode)) {
- if (ISDOT(p->fts_name))
- return (FTS_DOT);
+ if (ISDOT(p->fts_name)) {
+ /* Command-line "." and ".." are real directories. */
+ return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
+ }
-#if _LGPL_PACKAGE
+#if !GNULIB_FTS
{
/*
* Cycle detection is done by brute force when the directory
* See if fts_pathlen would overflow.
*/
if (new_len < sp->fts_pathlen) {
- if (sp->fts_path) {
- free(sp->fts_path);
- sp->fts_path = NULL;
- }
+ free(sp->fts_path);
sp->fts_path = NULL;
__set_errno (ENAMETOOLONG);
return false;
fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
{
int ret;
+ bool is_dotdot = dir && STREQ (dir, "..");
+ int newfd;
+
+ /* This clause handles the unusual case in which FTS_NOCHDIR
+ is specified, along with FTS_CWDFD. In that case, there is
+ no need to change even the virtual cwd file descriptor.
+ However, if FD is non-negative, we do close it here. */
+ if (ISSET (FTS_NOCHDIR))
+ {
+ if (ISSET (FTS_CWDFD) && 0 <= fd)
+ close (fd);
+ return 0;
+ }
- int newfd = fd;
- if (ISSET(FTS_NOCHDIR)) {
- if (ISSET(FTS_CWDFD) && 0 <= fd)
- close (fd);
- return (0);
- }
- if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
- return (-1);
+ if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
+ {
+ /* When possible, skip the diropen and subsequent fstat+dev/ino
+ comparison. I.e., when changing to parent directory
+ (chdir ("..")), use a file descriptor from the ring and
+ save the overhead of diropen+fstat, as well as avoiding
+ failure when we lack "x" access to the virtual cwd. */
+ if ( ! i_ring_empty (&sp->fts_fd_ring))
+ {
+ int parent_fd;
+ fd_ring_print (sp, stderr, "pre-pop");
+ parent_fd = i_ring_pop (&sp->fts_fd_ring);
+ is_dotdot = true;
+ if (0 <= parent_fd)
+ {
+ fd = parent_fd;
+ dir = NULL;
+ }
+ }
+ }
- /* The following dev/inode check is necessary if we're doing
- a `logical' traversal (through symlinks, a la chown -L),
- if the system lacks O_NOFOLLOW support, or if we're changing
- to "..". In the latter case, O_NOFOLLOW can't help. In
- general (when the target is not ".."), diropen's use of
- O_NOFOLLOW ensures we don't mistakenly follow a symlink,
- so we can avoid the expense of this fstat. */
- if (ISSET(FTS_LOGICAL) || O_NOFOLLOW == 0
+ newfd = fd;
+ if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
+ return -1;
+
+ /* The following dev/inode check is necessary if we're doing a
+ `logical' traversal (through symlinks, a la chown -L), if the
+ system lacks O_NOFOLLOW support, or if we're changing to ".."
+ (but not via a popped file descriptor). When changing to the
+ name "..", O_NOFOLLOW can't help. In general, when the target is
+ not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
+ follow a symlink, so we can avoid the expense of this fstat. */
+ if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
|| (dir && STREQ (dir, "..")))
{
struct stat sb;
if (ISSET(FTS_CWDFD))
{
- cwd_advance_fd (sp, newfd);
+ cwd_advance_fd (sp, newfd, ! is_dotdot);
return 0;
}
(void)close(newfd);
__set_errno (oerrno);
}
- return (ret);
+ return ret;
}
projects / gnulib.git / blobdiff