X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Ffts.c;h=673693a67175a42ee2fe133ea7cdf5a132be4d38;hb=a6694a282b6d9c86beacd77b65a30626af293ba1;hp=6eca31089e4d53193ba0b7c38c3847923c1a8564;hpb=73d4f7aea9a7d30da20f7930d6d6fd46f5ebc336;p=gnulib.git diff --git a/lib/fts.c b/lib/fts.c index 6eca31089..673693a67 100644 --- a/lib/fts.c +++ b/lib/fts.c @@ -1,11 +1,11 @@ /* Traverse a file hierarchy. - Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. + Copyright (C) 2004, 2005, 2006, 2007, 2008 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 @@ -13,8 +13,7 @@ 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 . */ /*- * Copyright (c) 1990, 1993, 1994 @@ -74,6 +73,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 @@ -93,6 +93,29 @@ static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94"; enum { + NOT_AN_INODE_NUMBER = 0 +}; + +#ifdef D_INO_IN_DIRENT +# define D_INO(dp) (dp)->d_ino +#else +/* Some systems don't have inodes, so fake them to avoid lots of ifdefs. */ +# define D_INO(dp) NOT_AN_INODE_NUMBER +#endif + +/* If there are more than this many entries in a directory, + and the conditions mentioned below are satisfied, then sort + the entries on inode number before any further processing. */ +#ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD +# define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000 +#endif +enum +{ + _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD = FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD +}; + +enum Fts_stat +{ FTS_NO_STAT_REQUIRED = 1, FTS_STAT_REQUIRED = 2 }; @@ -120,7 +143,7 @@ enum #endif #ifndef __attribute__ -# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__ +# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) # define __attribute__(x) /* empty */ # endif #endif @@ -137,6 +160,18 @@ enum # 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; @@ -149,14 +184,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 @@ -178,17 +212,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 */ @@ -197,10 +235,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) \ @@ -208,17 +249,28 @@ 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) { - if (p->fts_info != FTS_NSOK) - abort (); + fts_assert (p->fts_info == FTS_NSOK); p->fts_statp->st_size = (required ? FTS_STAT_REQUIRED : FTS_NO_STAT_REQUIRED); @@ -245,19 +297,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 @@ -396,7 +463,10 @@ fts_open (char * const *argv, p->fts_level = FTS_ROOTLEVEL; p->fts_parent = parent; p->fts_accpath = p->fts_name; - if (defer_stat) { + /* 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 { @@ -433,7 +503,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 @@ -446,6 +516,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); @@ -477,7 +548,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 @@ -519,6 +589,7 @@ fts_close (FTS *sp) close(sp->fts_rfd); } + fd_ring_clear (&sp->fts_fd_ring); free_dir (sp); /* Free up the stream pointer. */ @@ -636,7 +707,7 @@ fts_read (register FTS *sp) /* 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); @@ -649,6 +720,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); /* @@ -659,7 +731,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); @@ -689,23 +760,23 @@ name: t = sp->fts_path + NAPPEND(p->fts_parent); *t++ = '/'; memmove(t, p->fts_name, p->fts_namelen + 1); check_for_dir: + sp->fts_cur = p; if (p->fts_info == FTS_NSOK) { - switch (p->fts_statp->st_size) - { - case FTS_STAT_REQUIRED: - p->fts_info = fts_stat(sp, p, false); - break; - case FTS_NO_STAT_REQUIRED: - break; - default: - abort (); - } + 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); } - sp->fts_cur = p; + 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); @@ -717,6 +788,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) { @@ -729,8 +801,7 @@ check_for_dir: return (sp->fts_cur = NULL); } - if (p->fts_info == FTS_NSOK) - abort (); + fts_assert (p->fts_info != FTS_NSOK); /* NUL terminate the file name. */ sp->fts_path[p->fts_pathlen] = '\0'; @@ -763,7 +834,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; } @@ -848,7 +918,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 { @@ -864,6 +934,57 @@ fts_children (register FTS *sp, int instr) return (sp->fts_child); } +#if defined HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE +# include +/* FIXME: what about when f_type is not an integral type? + deal with that if/when it's encountered. */ +static bool +fs_handles_readdir_ordered_dirents_efficiently (uintmax_t fs_type) +{ +/* From coreutils' src/fs.h */ +#define S_MAGIC_TMPFS 0x1021994 +#define S_MAGIC_NFS 0x6969 + switch (fs_type) + { + case S_MAGIC_TMPFS: + case S_MAGIC_NFS: + return true; + default: + return false; + } +} + +/* Return true if it is easy to determine the file system type of the + current directory, and sorting dirents on inode numbers is known to + improve traversal performance with that type of file system. */ +static bool +dirent_inode_sort_may_be_useful (FTS const *sp) +{ + struct statfs fs_buf; + /* Skip the sort only if we can determine efficiently + that it's the right thing to do. */ + bool skip = (ISSET (FTS_CWDFD) + && fstatfs (sp->fts_cwd_fd, &fs_buf) == 0 + && fs_handles_readdir_ordered_dirents_efficiently + (fs_buf.f_type)); + return !skip; +} +#else +static bool dirent_inode_sort_may_be_useful (FTS const *sp) { return true; } +#endif + +/* A comparison function to sort on increasing inode number. + For some file system types, sorting either way makes a huge + performance difference for a directory with very many entries, + but sorting on increasing values is slightly better than sorting + on decreasing values. The difference is in the 5% range. */ +static int +fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b) +{ + return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? -1 + : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? 1 : 0); +} + /* * This is the tricky part -- do not casually change *anything* in here. The * idea is to build the linked list of entries that are used by fts_children @@ -1005,6 +1126,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; @@ -1041,7 +1164,7 @@ mem1: saved_errno = errno; new_len = len + _D_EXACT_NAMLEN (dp); if (new_len < len) { /* - * In the unlikely even that we would end up + * In the unlikely event that we would end up * with a file name longer than SIZE_MAX, free up * the current structure and the structures already * allocated, then error out with ENAMETOOLONG. @@ -1062,6 +1185,9 @@ mem1: saved_errno = errno; if (dp->d_type == DT_WHT) p->fts_flags |= FTS_ISW; #endif + /* Store dirent.d_ino, in case we need to sort + entries before processing them. */ + p->fts_statp->st_ino = D_INO (dp); /* Build a file name for fts_stat to stat. */ if (ISSET(FTS_NOCHDIR)) { @@ -1070,7 +1196,6 @@ mem1: saved_errno = errno; } else p->fts_accpath = p->fts_name; - bool is_dir; 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, @@ -1158,6 +1283,18 @@ mem1: saved_errno = errno; return (NULL); } + /* If there are many entries, no sorting function has been specified, + and this file system is of a type that may be slow with a large + number of entries, then sort the directory entries on increasing + inode numbers. */ + if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD + && !sp->fts_compar + && dirent_inode_sort_may_be_useful (sp)) { + sp->fts_compar = fts_compare_ino; + head = fts_sort (sp, head, nitems); + sp->fts_compar = NULL; + } + /* Sort the entries. */ if (sp->fts_compar && nitems > 1) head = fts_sort(sp, head, nitems); @@ -1225,6 +1362,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 @@ -1275,7 +1493,7 @@ err: memset(sbp, 0, sizeof(struct stat)); 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 @@ -1346,7 +1564,7 @@ fts_sort (FTS *sp, FTSENT *head, register size_t nitems) * 40 so don't realloc one entry at a time. */ if (nitems > sp->fts_nitems) { - struct _ftsent **a; + FTSENT **a; sp->fts_nitems = nitems + 40; if (SIZE_MAX / sizeof *a < sp->fts_nitems @@ -1500,23 +1718,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, ".."))) { @@ -1537,7 +1784,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; } @@ -1549,5 +1796,5 @@ bail: (void)close(newfd); __set_errno (oerrno); } - return (ret); + return ret; }