X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Ffts.c;h=1b5384b007e09aec317375f2f26af569dc75b179;hb=d90f751e2a857949f6eca74876dc0921bffa01d9;hp=07fe170f2e83ca34be31fad69fd96f48186da8b8;hpb=2e749d9876b6c6cbc098dff94b94d4df3981cbb0;p=gnulib.git diff --git a/lib/fts.c b/lib/fts.c index 07fe170f2..1b5384b00 100644 --- a/lib/fts.c +++ b/lib/fts.c @@ -1,6 +1,6 @@ /* 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 it under the terms of the GNU General Public License as published by @@ -74,6 +74,7 @@ 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 @@ -81,6 +82,22 @@ static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94"; # 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 @@ -121,6 +138,18 @@ static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94"; # 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; @@ -133,14 +162,13 @@ static unsigned short int fts_stat (FTS *, FTSENT *, bool) 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 @@ -162,17 +190,21 @@ static void free_dir (FTS *fts) {} #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 */ @@ -181,10 +213,13 @@ static void free_dir (FTS *fts) {} # include # include # include +# 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) \ @@ -192,9 +227,33 @@ bool fts_debug = false; { \ 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 * @@ -216,19 +275,34 @@ opendirat (int fd, char const *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 @@ -258,6 +332,7 @@ fts_open (char * const *argv, FTSENT *parent = NULL; FTSENT *tmp = NULL; /* pacify gcc */ size_t len; + bool defer_stat; /* Options check. */ if (options & ~FTS_OPTIONMASK) { @@ -340,6 +415,19 @@ fts_open (char * const *argv, 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. */ @@ -353,11 +441,15 @@ fts_open (char * const *argv, 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 @@ -389,7 +481,7 @@ fts_open (char * const *argv, 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 @@ -402,6 +494,7 @@ fts_open (char * const *argv, && (sp->fts_rfd = diropen (sp, ".")) < 0) SET(FTS_NOCHDIR); + i_ring_init (&sp->fts_fd_ring, -1); return (sp); mem3: fts_lfree(root); @@ -433,7 +526,6 @@ fts_load (FTS *sp, register FTSENT *p) p->fts_namelen = len; } p->fts_accpath = p->fts_path = sp->fts_path; - sp->fts_dev = p->fts_statp->st_dev; } int @@ -475,6 +567,7 @@ fts_close (FTS *sp) close(sp->fts_rfd); } + fd_ring_clear (&sp->fts_fd_ring); free_dir (sp); /* Free up the stream pointer. */ @@ -605,6 +698,7 @@ fts_read (register FTS *sp) /* Move to the next node on this level. */ next: tmp = p; if ((p = p->fts_link) != NULL) { + sp->fts_cur = p; free(tmp); /* @@ -615,7 +709,6 @@ next: tmp = p; if (p->fts_level == FTS_ROOTLEVEL) { if (RESTORE_INITIAL_CWD(sp)) { SET(FTS_STOP); - sp->fts_cur = p; return (NULL); } fts_load(sp, p); @@ -646,9 +739,22 @@ name: t = sp->fts_path + NAPPEND(p->fts_parent); 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); @@ -660,6 +766,7 @@ check_for_dir: /* Move up to the parent node. */ p = tmp->fts_parent; + sp->fts_cur = p; free(tmp); if (p->fts_level == FTS_ROOTPARENTLEVEL) { @@ -672,6 +779,8 @@ check_for_dir: return (sp->fts_cur = NULL); } + fts_assert (p->fts_info != FTS_NSOK); + /* NUL terminate the file name. */ sp->fts_path[p->fts_pathlen] = '\0'; @@ -703,7 +812,6 @@ check_for_dir: 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; } @@ -788,7 +896,7 @@ fts_children (register FTS *sp, int instr) sp->fts_child = fts_build(sp, instr); if (ISSET(FTS_CWDFD)) { - cwd_advance_fd (sp, fd); + cwd_advance_fd (sp, fd, true); } else { @@ -862,6 +970,11 @@ fts_build (register FTS *sp, int type) } 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 @@ -940,6 +1053,8 @@ fts_build (register FTS *sp, int type) /* 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; @@ -1004,12 +1119,37 @@ mem1: saved_errno = errno; 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. */ @@ -1134,6 +1274,87 @@ fts_cross_check (FTS const *sp) } } } + +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 @@ -1143,6 +1364,9 @@ fts_stat(FTS *sp, register FTSENT *p, bool follow) 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) { @@ -1176,10 +1400,12 @@ err: memset(sbp, 0, sizeof(struct stat)); } 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 @@ -1404,23 +1630,52 @@ internal_function 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. */ + 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, ".."))) { @@ -1441,7 +1696,7 @@ fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir) if (ISSET(FTS_CWDFD)) { - cwd_advance_fd (sp, newfd); + cwd_advance_fd (sp, newfd, ! is_dotdot); return 0; } @@ -1453,5 +1708,5 @@ bail: (void)close(newfd); __set_errno (oerrno); } - return (ret); + return ret; }