1 /* Traverse a file hierarchy.
3 Copyright (C) 2004-2011 Free Software Foundation, Inc.
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
19 * Copyright (c) 1990, 1993, 1994
20 * The Regents of the University of California. All rights reserved.
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
25 * 1. Redistributions of source code must retain the above copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 4. Neither the name of the University nor the names of its contributors
31 * may be used to endorse or promote products derived from this software
32 * without specific prior written permission.
34 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
35 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
49 #if defined(LIBC_SCCS) && !defined(lint)
50 static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94";
51 #endif /* LIBC_SCCS and not lint */
55 #if HAVE_SYS_PARAM_H || defined _LIBC
56 # include <sys/param.h>
59 # include <include/sys/stat.h>
61 # include <sys/stat.h>
72 # include "dirent--.h"
73 # include "unistd--.h"
74 /* FIXME - use fcntl(F_DUPFD_CLOEXEC)/openat(O_CLOEXEC) once they are
78 # include "same-inode.h"
82 #ifndef _D_EXACT_NAMLEN
83 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
86 #if HAVE_STRUCT_DIRENT_D_TYPE
87 /* True if the type of the directory entry D is known. */
88 # define DT_IS_KNOWN(d) ((d)->d_type != DT_UNKNOWN)
89 /* True if the type of the directory entry D must be T. */
90 # define DT_MUST_BE(d, t) ((d)->d_type == (t))
91 # define D_TYPE(d) ((d)->d_type)
93 # define DT_IS_KNOWN(d) false
94 # define DT_MUST_BE(d, t) false
95 # define D_TYPE(d) DT_UNKNOWN
100 /* Any nonzero values will do here, so long as they're distinct.
101 Undef any existing macros out of the way. */
127 NOT_AN_INODE_NUMBER = 0
130 #ifdef D_INO_IN_DIRENT
131 # define D_INO(dp) (dp)->d_ino
133 /* Some systems don't have inodes, so fake them to avoid lots of ifdefs. */
134 # define D_INO(dp) NOT_AN_INODE_NUMBER
137 /* If there are more than this many entries in a directory,
138 and the conditions mentioned below are satisfied, then sort
139 the entries on inode number before any further processing. */
140 #ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
141 # define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000
145 _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD = FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
150 FTS_NO_STAT_REQUIRED = 1,
151 FTS_STAT_REQUIRED = 2
156 # define close __close
158 # define closedir __closedir
160 # define fchdir __fchdir
164 # define readdir __readdir
166 # undef internal_function
167 # define internal_function /* empty */
171 # define __set_errno(Val) errno = (Val)
174 /* If this host provides the openat function, then we can avoid
175 attempting to open "." in some initialization code below. */
177 # define HAVE_OPENAT_SUPPORT 1
179 # define HAVE_OPENAT_SUPPORT 0
183 # define fts_assert(expr) ((void) 0)
185 # define fts_assert(expr) \
194 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
195 static FTSENT *fts_build (FTS *, int) internal_function;
196 static void fts_lfree (FTSENT *) internal_function;
197 static void fts_load (FTS *, FTSENT *) internal_function;
198 static size_t fts_maxarglen (char * const *) internal_function;
199 static void fts_padjust (FTS *, FTSENT *) internal_function;
200 static bool fts_palloc (FTS *, size_t) internal_function;
201 static FTSENT *fts_sort (FTS *, FTSENT *, size_t) internal_function;
202 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
203 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
206 #include "fts-cycle.c"
209 # define MAX(a,b) ((a) > (b) ? (a) : (b))
213 # define SIZE_MAX ((size_t) -1)
216 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
217 #define STREQ(a, b) (strcmp (a, b) == 0)
219 #define CLR(opt) (sp->fts_options &= ~(opt))
220 #define ISSET(opt) (sp->fts_options & (opt))
221 #define SET(opt) (sp->fts_options |= (opt))
223 /* FIXME: make this a function */
224 #define RESTORE_INITIAL_CWD(sp) \
225 (fd_ring_clear (&((sp)->fts_fd_ring)), \
226 FCHDIR ((sp), (ISSET (FTS_CWDFD) ? AT_FDCWD : (sp)->fts_rfd)))
228 /* FIXME: FTS_NOCHDIR is now misnamed.
229 Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
230 #define FCHDIR(sp, fd) \
231 (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \
232 ? (cwd_advance_fd ((sp), (fd), true), 0) \
236 /* fts_build flags */
237 /* FIXME: make this an enum */
238 #define BCHILD 1 /* fts_children */
239 #define BNAMES 2 /* fts_children, names only */
240 #define BREAD 3 /* fts_read */
243 # include <inttypes.h>
246 # include "getcwdat.h"
247 bool fts_debug = false;
248 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
251 # define fd_ring_check(x)
252 # define fd_ring_print(a, b, c)
255 #define LEAVE_DIR(Fts, Ent, Tag) \
258 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
259 leave_dir (Fts, Ent); \
260 fd_ring_check (Fts); \
265 fd_ring_clear (I_ring *fd_ring)
267 while ( ! i_ring_empty (fd_ring))
269 int fd = i_ring_pop (fd_ring);
275 /* Overload the fts_statp->st_size member (otherwise unused, when
276 fts_info is FTS_NSOK) to indicate whether fts_read should stat
277 this entry or not. */
279 fts_set_stat_required (FTSENT *p, bool required)
281 fts_assert (p->fts_info == FTS_NSOK);
282 p->fts_statp->st_size = (required
284 : FTS_NO_STAT_REQUIRED);
287 /* file-descriptor-relative opendir. */
288 /* FIXME: if others need this function, move it into lib/openat.c */
291 opendirat (int fd, char const *dir, int extra_flags, int *pdir_fd)
293 int new_fd = openat (fd, dir,
294 (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
300 set_cloexec_flag (new_fd, true);
301 dirp = fdopendir (new_fd);
306 int saved_errno = errno;
313 /* Virtual fchdir. Advance SP's working directory file descriptor,
314 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
315 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
316 open on sp->fts_cwd_fd; i.e., to move the working directory one level
320 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
322 int old = sp->fts_cwd_fd;
323 fts_assert (old != fd || old == AT_FDCWD);
327 /* Push "old" onto the ring.
328 If the displaced file descriptor is non-negative, close it. */
329 int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);
330 fd_ring_print (sp, stderr, "post-push");
331 if (0 <= prev_fd_in_slot)
332 close (prev_fd_in_slot); /* ignore any close failure */
334 else if ( ! ISSET (FTS_NOCHDIR))
337 close (old); /* ignore any close failure */
343 /* Open the directory DIR if possible, and return a file
344 descriptor. Return -1 and set errno on failure. It doesn't matter
345 whether the file descriptor has read or write access. */
349 diropen (FTS const *sp, char const *dir)
351 int open_flags = (O_SEARCH | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
352 | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0)
353 | (ISSET (FTS_NOATIME) ? O_NOATIME : 0));
355 int fd = (ISSET (FTS_CWDFD)
356 ? openat (sp->fts_cwd_fd, dir, open_flags)
357 : open (dir, open_flags));
359 set_cloexec_flag (fd, true);
364 fts_open (char * const *argv,
365 register int options,
366 int (*compar) (FTSENT const **, FTSENT const **))
369 register FTSENT *p, *root;
370 register size_t nitems;
371 FTSENT *parent = NULL;
372 FTSENT *tmp = NULL; /* pacify gcc */
376 if (options & ~FTS_OPTIONMASK) {
377 __set_errno (EINVAL);
380 if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {
381 __set_errno (EINVAL);
384 if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {
385 __set_errno (EINVAL);
389 /* Allocate/initialize the stream */
390 if ((sp = malloc(sizeof(FTS))) == NULL)
392 memset(sp, 0, sizeof(FTS));
393 sp->fts_compar = compar;
394 sp->fts_options = options;
396 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
397 if (ISSET(FTS_LOGICAL)) {
402 /* Initialize fts_cwd_fd. */
403 sp->fts_cwd_fd = AT_FDCWD;
404 if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)
406 /* While it isn't technically necessary to open "." this
407 early, doing it here saves us the trouble of ensuring
408 later (where it'd be messier) that "." can in fact
409 be opened. If not, revert to FTS_NOCHDIR mode. */
411 O_SEARCH | (ISSET (FTS_NOATIME) ? O_NOATIME : 0));
414 /* Even if `.' is unreadable, don't revert to FTS_NOCHDIR mode
415 on systems like Linux+PROC_FS, where our openat emulation
416 is good enough. Note: on a system that emulates
417 openat via /proc, this technique can still fail, but
418 only in extreme conditions, e.g., when the working
419 directory cannot be saved (i.e. save_cwd fails) --
420 and that happens on Linux only when "." is unreadable
421 and the CWD would be longer than PATH_MAX.
422 FIXME: once Linux kernel openat support is well established,
423 replace the above open call and this entire if/else block
424 with the body of the if-block below. */
425 if ( openat_needs_fchdir ())
438 * Start out with 1K of file name space, and enough, in any case,
439 * to hold the user's file names.
442 # define MAXPATHLEN 1024
445 size_t maxarglen = fts_maxarglen(argv);
446 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
450 /* Allocate/initialize root's parent. */
452 if ((parent = fts_alloc(sp, "", 0)) == NULL)
454 parent->fts_level = FTS_ROOTPARENTLEVEL;
457 /* The classic fts implementation would call fts_stat with
458 a new entry for each iteration of the loop below.
459 If the comparison function is not specified or if the
460 FTS_DEFER_STAT option is in effect, don't stat any entry
461 in this loop. This is an attempt to minimize the interval
462 between the initial stat/lstat/fstatat and the point at which
463 a directory argument is first opened. This matters for any
464 directory command line argument that resides on a file system
465 without genuine i-nodes. If you specify FTS_DEFER_STAT along
466 with a comparison function, that function must not access any
467 data via the fts_statp pointer. */
468 defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));
470 /* Allocate/initialize root(s). */
471 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
472 /* *Do* allow zero-length file names. */
473 size_t len = strlen(*argv);
474 if ((p = fts_alloc(sp, *argv, len)) == NULL)
476 p->fts_level = FTS_ROOTLEVEL;
477 p->fts_parent = parent;
478 p->fts_accpath = p->fts_name;
479 /* Even when defer_stat is true, be sure to stat the first
480 command line argument, since fts_read (at least with
481 FTS_XDEV) requires that. */
482 if (defer_stat && root != NULL) {
483 p->fts_info = FTS_NSOK;
484 fts_set_stat_required(p, true);
486 p->fts_info = fts_stat(sp, p, false);
490 * If comparison routine supplied, traverse in sorted
491 * order; otherwise traverse in the order specified.
506 if (compar && nitems > 1)
507 root = fts_sort(sp, root, nitems);
510 * Allocate a dummy pointer and make fts_read think that we've just
511 * finished the node before the root(s); set p->fts_info to FTS_INIT
512 * so that everything about the "current" node is ignored.
514 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
516 sp->fts_cur->fts_link = root;
517 sp->fts_cur->fts_info = FTS_INIT;
518 if (! setup_dir (sp))
522 * If using chdir(2), grab a file descriptor pointing to dot to ensure
523 * that we can get back here; this could be avoided for some file names,
524 * but almost certainly not worth the effort. Slashes, symbolic links,
525 * and ".." are all fairly nasty problems. Note, if we can't get the
526 * descriptor we run anyway, just more slowly.
528 if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)
529 && (sp->fts_rfd = diropen (sp, ".")) < 0)
532 i_ring_init (&sp->fts_fd_ring, -1);
535 mem3: fts_lfree(root);
537 mem2: free(sp->fts_path);
544 fts_load (FTS *sp, register FTSENT *p)
550 * Load the stream structure for the next traversal. Since we don't
551 * actually enter the directory until after the preorder visit, set
552 * the fts_accpath field specially so the chdir gets done to the right
553 * place and the user can access the first node. From fts_open it's
554 * known that the file name will fit.
556 len = p->fts_pathlen = p->fts_namelen;
557 memmove(sp->fts_path, p->fts_name, len + 1);
558 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
560 memmove(p->fts_name, cp, len + 1);
561 p->fts_namelen = len;
563 p->fts_accpath = p->fts_path = sp->fts_path;
569 register FTSENT *freep, *p;
573 * This still works if we haven't read anything -- the dummy structure
574 * points to the root list, so we step through to the end of the root
575 * list which has a valid parent pointer.
578 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
580 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
586 /* Free up child linked list, sort array, file name buffer. */
588 fts_lfree(sp->fts_child);
592 if (ISSET(FTS_CWDFD))
594 if (0 <= sp->fts_cwd_fd)
595 if (close (sp->fts_cwd_fd))
598 else if (!ISSET(FTS_NOCHDIR))
600 /* Return to original directory, save errno if necessary. */
601 if (fchdir(sp->fts_rfd))
604 /* If close fails, record errno only if saved_errno is zero,
605 so that we report the probably-more-meaningful fchdir errno. */
606 if (close (sp->fts_rfd))
607 if (saved_errno == 0)
611 fd_ring_clear (&sp->fts_fd_ring);
613 if (sp->fts_leaf_optimization_works_ht)
614 hash_free (sp->fts_leaf_optimization_works_ht);
618 /* Free up the stream pointer. */
621 /* Set errno and return. */
623 __set_errno (saved_errno);
630 #if defined __linux__ \
631 && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
633 # include <sys/vfs.h>
635 /* Linux-specific constants from coreutils' src/fs.h */
636 # define S_MAGIC_TMPFS 0x1021994
637 # define S_MAGIC_NFS 0x6969
638 # define S_MAGIC_REISERFS 0x52654973
639 # define S_MAGIC_PROC 0x9FA0
641 /* Return false if it is easy to determine the file system type of
642 the directory on which DIR_FD is open, and sorting dirents on
643 inode numbers is known not to improve traversal performance with
644 that type of file system. Otherwise, return true. */
646 dirent_inode_sort_may_be_useful (int dir_fd)
648 /* Skip the sort only if we can determine efficiently
649 that skipping it is the right thing to do.
650 The cost of performing an unnecessary sort is negligible,
651 while the cost of *not* performing it can be O(N^2) with
652 a very large constant. */
653 struct statfs fs_buf;
655 /* If fstatfs fails, assume sorting would be useful. */
656 if (fstatfs (dir_fd, &fs_buf) != 0)
659 /* FIXME: what about when f_type is not an integral type?
660 deal with that if/when it's encountered. */
661 switch (fs_buf.f_type)
665 /* On a file system of any of these types, sorting
666 is unnecessary, and hence wasteful. */
674 /* Given a file descriptor DIR_FD open on a directory D,
675 return true if it is valid to apply the leaf-optimization
676 technique of counting directories in D via stat.st_nlink. */
678 leaf_optimization_applies (int dir_fd)
680 struct statfs fs_buf;
682 /* If fstatfs fails, assume we can't use the optimization. */
683 if (fstatfs (dir_fd, &fs_buf) != 0)
686 /* FIXME: do we need to detect AFS mount points? I doubt it,
687 unless fstatfs can report S_MAGIC_REISERFS for such a directory. */
689 switch (fs_buf.f_type)
691 /* List here the file system types that lack useable dirent.d_type
692 info, yet for which the optimization does apply. */
693 case S_MAGIC_REISERFS:
697 /* Explicitly listing this or any other file system type for which
698 the optimization is not applicable is not necessary, but we leave
699 it here to document the risk. Per http://bugs.debian.org/143111,
700 /proc may have bogus stat.st_nlink values. */
709 dirent_inode_sort_may_be_useful (int dir_fd _GL_UNUSED) { return true; }
711 leaf_optimization_applies (int dir_fd _GL_UNUSED) { return false; }
714 /* link-count-optimization entry:
715 map a stat.st_dev number to a boolean: leaf_optimization_works */
722 /* Use a tiny initial size. If a traversal encounters more than
723 a few devices, the cost of growing/rehashing this table will be
724 rendered negligible by the number of inodes processed. */
725 enum { LCO_HT_INITIAL_SIZE = 13 };
728 LCO_hash (void const *x, size_t table_size)
730 struct LCO_ent const *ax = x;
731 return (uintmax_t) ax->st_dev % table_size;
735 LCO_compare (void const *x, void const *y)
737 struct LCO_ent const *ax = x;
738 struct LCO_ent const *ay = y;
739 return ax->st_dev == ay->st_dev;
742 /* Ask the same question as leaf_optimization_applies, but query
743 the cache first (FTS.fts_leaf_optimization_works_ht), and if necessary,
744 update that cache. */
746 link_count_optimize_ok (FTSENT const *p)
748 FTS *sp = p->fts_fts;
749 Hash_table *h = sp->fts_leaf_optimization_works_ht;
755 /* If we're not in CWDFD mode, don't bother with this optimization,
756 since the caller is not serious about performance. */
757 if (!ISSET(FTS_CWDFD))
760 /* map st_dev to the boolean, leaf_optimization_works */
763 h = sp->fts_leaf_optimization_works_ht
764 = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash,
769 tmp.st_dev = p->fts_statp->st_dev;
770 ent = hash_lookup (h, &tmp);
774 /* Look-up failed. Query directly and cache the result. */
775 t2 = malloc (sizeof *t2);
779 /* Is it ok to perform the optimization in the dir, FTS_CWD_FD? */
780 opt_ok = leaf_optimization_applies (sp->fts_cwd_fd);
782 t2->st_dev = p->fts_statp->st_dev;
784 ent = hash_insert (h, t2);
787 /* insertion failed */
791 fts_assert (ent == t2);
797 * Special case of "/" at the end of the file name so that slashes aren't
798 * appended which would cause file names to be written as "....//foo".
801 (p->fts_path[p->fts_pathlen - 1] == '/' \
802 ? p->fts_pathlen - 1 : p->fts_pathlen)
805 fts_read (register FTS *sp)
807 register FTSENT *p, *tmp;
808 register unsigned short int instr;
811 /* If finished or unrecoverable error, return NULL. */
812 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
815 /* Set current node pointer. */
818 /* Save and zero out user instructions. */
819 instr = p->fts_instr;
820 p->fts_instr = FTS_NOINSTR;
822 /* Any type of file may be re-visited; re-stat and re-turn. */
823 if (instr == FTS_AGAIN) {
824 p->fts_info = fts_stat(sp, p, false);
827 Dprintf (("fts_read: p=%s\n",
828 p->fts_info == FTS_INIT ? "" : p->fts_path));
831 * Following a symlink -- SLNONE test allows application to see
832 * SLNONE and recover. If indirecting through a symlink, have
833 * keep a pointer to current location. If unable to get that
834 * pointer, follow fails.
836 if (instr == FTS_FOLLOW &&
837 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
838 p->fts_info = fts_stat(sp, p, true);
839 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
840 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
841 p->fts_errno = errno;
842 p->fts_info = FTS_ERR;
844 p->fts_flags |= FTS_SYMFOLLOW;
849 /* Directory in pre-order. */
850 if (p->fts_info == FTS_D) {
851 /* If skipped or crossed mount point, do post-order visit. */
852 if (instr == FTS_SKIP ||
853 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
854 if (p->fts_flags & FTS_SYMFOLLOW)
855 (void)close(p->fts_symfd);
857 fts_lfree(sp->fts_child);
858 sp->fts_child = NULL;
860 p->fts_info = FTS_DP;
861 LEAVE_DIR (sp, p, "1");
865 /* Rebuild if only read the names and now traversing. */
866 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
868 fts_lfree(sp->fts_child);
869 sp->fts_child = NULL;
873 * Cd to the subdirectory.
875 * If have already read and now fail to chdir, whack the list
876 * to make the names come out right, and set the parent errno
877 * so the application will eventually get an error condition.
878 * Set the FTS_DONTCHDIR flag so that when we logically change
879 * directories back to the parent we don't do a chdir.
881 * If haven't read do so. If the read fails, fts_build sets
882 * FTS_STOP or the fts_info field of the node.
884 if (sp->fts_child != NULL) {
885 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
886 p->fts_errno = errno;
887 p->fts_flags |= FTS_DONTCHDIR;
888 for (p = sp->fts_child; p != NULL;
891 p->fts_parent->fts_accpath;
893 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
896 /* If fts_build's call to fts_safe_changedir failed
897 because it was not able to fchdir into a
898 subdirectory, tell the caller. */
899 if (p->fts_errno && p->fts_info != FTS_DNR)
900 p->fts_info = FTS_ERR;
901 LEAVE_DIR (sp, p, "2");
905 sp->fts_child = NULL;
909 /* Move to the next node on this level. */
911 if ((p = p->fts_link) != NULL) {
916 * If reached the top, return to the original directory (or
917 * the root of the tree), and load the file names for the next
920 if (p->fts_level == FTS_ROOTLEVEL) {
921 if (RESTORE_INITIAL_CWD(sp)) {
932 * User may have called fts_set on the node. If skipped,
933 * ignore. If followed, get a file descriptor so we can
934 * get back if necessary.
936 if (p->fts_instr == FTS_SKIP)
938 if (p->fts_instr == FTS_FOLLOW) {
939 p->fts_info = fts_stat(sp, p, true);
940 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
941 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
942 p->fts_errno = errno;
943 p->fts_info = FTS_ERR;
945 p->fts_flags |= FTS_SYMFOLLOW;
947 p->fts_instr = FTS_NOINSTR;
950 name: t = sp->fts_path + NAPPEND(p->fts_parent);
952 memmove(t, p->fts_name, p->fts_namelen + 1);
955 if (p->fts_info == FTS_NSOK)
957 if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
959 FTSENT *parent = p->fts_parent;
960 if (FTS_ROOTLEVEL < p->fts_level
961 /* ->fts_n_dirs_remaining is not valid
962 for command-line-specified names. */
963 && parent->fts_n_dirs_remaining == 0
965 && ISSET(FTS_PHYSICAL)
966 && link_count_optimize_ok (parent))
968 /* nothing more needed */
972 p->fts_info = fts_stat(sp, p, false);
973 if (S_ISDIR(p->fts_statp->st_mode)
974 && p->fts_level != FTS_ROOTLEVEL
975 && parent->fts_n_dirs_remaining)
976 parent->fts_n_dirs_remaining--;
980 fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
983 if (p->fts_info == FTS_D)
985 /* Now that P->fts_statp is guaranteed to be valid,
986 if this is a command-line directory, record its
987 device number, to be used for FTS_XDEV. */
988 if (p->fts_level == FTS_ROOTLEVEL)
989 sp->fts_dev = p->fts_statp->st_dev;
990 Dprintf ((" entering: %s\n", p->fts_path));
991 if (! enter_dir (sp, p))
993 __set_errno (ENOMEM);
1000 /* Move up to the parent node. */
1001 p = tmp->fts_parent;
1005 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
1007 * Done; free everything up and set errno to 0 so the user
1008 * can distinguish between error and EOF.
1012 return (sp->fts_cur = NULL);
1015 fts_assert (p->fts_info != FTS_NSOK);
1017 /* NUL terminate the file name. */
1018 sp->fts_path[p->fts_pathlen] = '\0';
1021 * Return to the parent directory. If at a root node, restore
1022 * the initial working directory. If we came through a symlink,
1023 * go back through the file descriptor. Otherwise, move up
1024 * one level, via "..".
1026 if (p->fts_level == FTS_ROOTLEVEL) {
1027 if (RESTORE_INITIAL_CWD(sp)) {
1028 p->fts_errno = errno;
1031 } else if (p->fts_flags & FTS_SYMFOLLOW) {
1032 if (FCHDIR(sp, p->fts_symfd)) {
1033 int saved_errno = errno;
1034 (void)close(p->fts_symfd);
1035 __set_errno (saved_errno);
1036 p->fts_errno = errno;
1039 (void)close(p->fts_symfd);
1040 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
1041 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
1042 p->fts_errno = errno;
1045 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
1046 if (p->fts_errno == 0)
1047 LEAVE_DIR (sp, p, "3");
1048 return ISSET(FTS_STOP) ? NULL : p;
1052 * Fts_set takes the stream as an argument although it's not used in this
1053 * implementation; it would be necessary if anyone wanted to add global
1054 * semantics to fts using fts_set. An error return is allowed for similar
1059 fts_set(FTS *sp _GL_UNUSED, FTSENT *p, int instr)
1061 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
1062 instr != FTS_NOINSTR && instr != FTS_SKIP) {
1063 __set_errno (EINVAL);
1066 p->fts_instr = instr;
1071 fts_children (register FTS *sp, int instr)
1076 if (instr != 0 && instr != FTS_NAMEONLY) {
1077 __set_errno (EINVAL);
1081 /* Set current node pointer. */
1085 * Errno set to 0 so user can distinguish empty directory from
1090 /* Fatal errors stop here. */
1091 if (ISSET(FTS_STOP))
1094 /* Return logical hierarchy of user's arguments. */
1095 if (p->fts_info == FTS_INIT)
1096 return (p->fts_link);
1099 * If not a directory being visited in pre-order, stop here. Could
1100 * allow FTS_DNR, assuming the user has fixed the problem, but the
1101 * same effect is available with FTS_AGAIN.
1103 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
1106 /* Free up any previous child list. */
1107 if (sp->fts_child != NULL)
1108 fts_lfree(sp->fts_child);
1110 if (instr == FTS_NAMEONLY) {
1117 * If using chdir on a relative file name and called BEFORE fts_read
1118 * does its chdir to the root of a traversal, we can lose -- we need to
1119 * chdir into the subdirectory, and we don't know where the current
1120 * directory is, so we can't get back so that the upcoming chdir by
1121 * fts_read will work.
1123 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
1125 return (sp->fts_child = fts_build(sp, instr));
1127 if ((fd = diropen (sp, ".")) < 0)
1128 return (sp->fts_child = NULL);
1129 sp->fts_child = fts_build(sp, instr);
1130 if (ISSET(FTS_CWDFD))
1132 cwd_advance_fd (sp, fd, true);
1138 int saved_errno = errno;
1140 __set_errno (saved_errno);
1145 return (sp->fts_child);
1148 /* A comparison function to sort on increasing inode number.
1149 For some file system types, sorting either way makes a huge
1150 performance difference for a directory with very many entries,
1151 but sorting on increasing values is slightly better than sorting
1152 on decreasing values. The difference is in the 5% range. */
1154 fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b)
1156 return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? -1
1157 : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? 1 : 0);
1160 /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode
1161 S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */
1163 set_stat_type (struct stat *st, unsigned int dtype)
1195 #define closedir_and_clear(dirp) \
1203 #define fts_opendir(file, Pdir_fd) \
1204 opendirat((! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
1205 ? sp->fts_cwd_fd : AT_FDCWD), \
1207 (((ISSET(FTS_PHYSICAL) \
1208 && ! (ISSET(FTS_COMFOLLOW) \
1209 && cur->fts_level == FTS_ROOTLEVEL)) \
1211 | (ISSET (FTS_NOATIME) ? O_NOATIME : 0)), \
1215 * This is the tricky part -- do not casually change *anything* in here. The
1216 * idea is to build the linked list of entries that are used by fts_children
1217 * and fts_read. There are lots of special cases.
1219 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
1220 * set and it's a physical walk (so that symbolic links can't be directories),
1221 * we can do things quickly. First, if it's a 4.4BSD file system, the type
1222 * of the file is in the directory entry. Otherwise, we assume that the number
1223 * of subdirectories in a node is equal to the number of links to the parent.
1224 * The former skips all stat calls. The latter skips stat calls in any leaf
1225 * directories and for any files after the subdirectories in the directory have
1226 * been found, cutting the stat calls by about 2/3.
1230 fts_build (register FTS *sp, int type)
1232 register struct dirent *dp;
1233 register FTSENT *p, *head;
1234 register size_t nitems;
1243 size_t len, maxlen, new_len;
1246 FTSENT *cur = sp->fts_cur;
1248 /* Open the directory for reading. If this fails, we're done.
1249 If being called from fts_read, set the fts_info field. */
1250 if ((cur->fts_dirp = fts_opendir(cur->fts_accpath, &dir_fd)) == NULL) {
1251 if (type == BREAD) {
1252 cur->fts_info = FTS_DNR;
1253 cur->fts_errno = errno;
1257 /* Rather than calling fts_stat for each and every entry encountered
1258 in the readdir loop (below), stat each directory only right after
1260 if (cur->fts_info == FTS_NSOK)
1261 cur->fts_info = fts_stat(sp, cur, false);
1262 else if (sp->fts_options & FTS_TIGHT_CYCLE_CHECK)
1264 /* Now read the stat info again after opening a directory to
1265 reveal eventual changes caused by a submount triggered by
1266 the traversal. But do it only for utilities which use
1267 FTS_TIGHT_CYCLE_CHECK. Therefore, only find and du
1268 benefit/suffer from this feature for now. */
1269 LEAVE_DIR (sp, cur, "4");
1270 fts_stat (sp, cur, false);
1271 if (! enter_dir (sp, cur))
1273 __set_errno (ENOMEM);
1278 /* Nlinks is the number of possible entries of type directory in the
1279 directory if we're cheating on stat calls, 0 if we're not doing
1280 any stat calls at all, (nlink_t) -1 if we're statting everything. */
1281 if (type == BNAMES) {
1283 /* Be quiet about nostat, GCC. */
1285 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
1286 nlinks = (cur->fts_statp->st_nlink
1287 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1295 * If we're going to need to stat anything or we want to descend
1296 * and stay in the directory, chdir. If this fails we keep going,
1297 * but set a flag so we don't chdir after the post-order visit.
1298 * We won't be able to stat anything, but we can still return the
1299 * names themselves. Note, that since fts_read won't be able to
1300 * chdir into the directory, it will have to return different file
1301 * names than before, i.e. "a/b" instead of "b". Since the node
1302 * has already been visited in pre-order, have to wait until the
1303 * post-order visit to return the error. There is a special case
1304 * here, if there was nothing to stat then it's not an error to
1305 * not be able to stat. This is all fairly nasty. If a program
1306 * needed sorted entries or stat information, they had better be
1307 * checking FTS_NS on the returned nodes.
1309 if (nlinks || type == BREAD) {
1310 if (ISSET(FTS_CWDFD))
1312 dir_fd = dup (dir_fd);
1314 set_cloexec_flag (dir_fd, true);
1316 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
1317 if (nlinks && type == BREAD)
1318 cur->fts_errno = errno;
1319 cur->fts_flags |= FTS_DONTCHDIR;
1321 closedir_and_clear(cur->fts_dirp);
1322 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1324 cur->fts_dirp = NULL;
1331 * Figure out the max file name length that can be stored in the
1332 * current buffer -- the inner loop allocates more space as necessary.
1333 * We really wouldn't have to do the maxlen calculations here, we
1334 * could do them in fts_read before returning the name, but it's a
1335 * lot easier here since the length is part of the dirent structure.
1337 * If not changing directories set a pointer so that can just append
1338 * each new component into the file name.
1341 if (ISSET(FTS_NOCHDIR)) {
1342 cp = sp->fts_path + len;
1345 /* GCC, you're too verbose. */
1349 maxlen = sp->fts_pathlen - len;
1351 level = cur->fts_level + 1;
1353 /* Read the directory, attaching each entry to the `link' pointer. */
1355 for (head = tail = NULL, nitems = 0; cur->fts_dirp && (dp = readdir(cur->fts_dirp));) {
1358 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1361 if ((p = fts_alloc (sp, dp->d_name,
1362 _D_EXACT_NAMLEN (dp))) == NULL)
1364 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
1365 /* include space for NUL */
1366 oldaddr = sp->fts_path;
1367 if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
1369 * No more memory. Save
1370 * errno, free up the current structure and the
1371 * structures already allocated.
1373 mem1: saved_errno = errno;
1376 closedir_and_clear(cur->fts_dirp);
1377 cur->fts_info = FTS_ERR;
1379 __set_errno (saved_errno);
1382 /* Did realloc() change the pointer? */
1383 if (oldaddr != sp->fts_path) {
1385 if (ISSET(FTS_NOCHDIR))
1386 cp = sp->fts_path + len;
1388 maxlen = sp->fts_pathlen - len;
1391 new_len = len + _D_EXACT_NAMLEN (dp);
1392 if (new_len < len) {
1394 * In the unlikely event that we would end up
1395 * with a file name longer than SIZE_MAX, free up
1396 * the current structure and the structures already
1397 * allocated, then error out with ENAMETOOLONG.
1401 closedir_and_clear(cur->fts_dirp);
1402 cur->fts_info = FTS_ERR;
1404 __set_errno (ENAMETOOLONG);
1407 p->fts_level = level;
1408 p->fts_parent = sp->fts_cur;
1409 p->fts_pathlen = new_len;
1411 /* Store dirent.d_ino, in case we need to sort
1412 entries before processing them. */
1413 p->fts_statp->st_ino = D_INO (dp);
1415 /* Build a file name for fts_stat to stat. */
1416 if (ISSET(FTS_NOCHDIR)) {
1417 p->fts_accpath = p->fts_path;
1418 memmove(cp, p->fts_name, p->fts_namelen + 1);
1420 p->fts_accpath = p->fts_name;
1422 if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {
1423 /* Record what fts_read will have to do with this
1424 entry. In many cases, it will simply fts_stat it,
1425 but we can take advantage of any d_type information
1426 to optimize away the unnecessary stat calls. I.e.,
1427 if FTS_NOSTAT is in effect and we're not following
1428 symlinks (FTS_PHYSICAL) and d_type indicates this
1429 is *not* a directory, then we won't have to stat it
1430 at all. If it *is* a directory, then (currently)
1431 we stat it regardless, in order to get device and
1432 inode numbers. Some day we might optimize that
1433 away, too, for directories where d_ino is known to
1435 bool skip_stat = (ISSET(FTS_PHYSICAL)
1436 && ISSET(FTS_NOSTAT)
1438 && ! DT_MUST_BE(dp, DT_DIR));
1439 p->fts_info = FTS_NSOK;
1440 /* Propagate dirent.d_type information back
1441 to caller, when possible. */
1442 set_stat_type (p->fts_statp, D_TYPE (dp));
1443 fts_set_stat_required(p, !skip_stat);
1444 is_dir = (ISSET(FTS_PHYSICAL)
1445 && DT_MUST_BE(dp, DT_DIR));
1447 p->fts_info = fts_stat(sp, p, false);
1448 is_dir = (p->fts_info == FTS_D
1449 || p->fts_info == FTS_DC
1450 || p->fts_info == FTS_DOT);
1453 /* Decrement link count if applicable. */
1454 if (nlinks > 0 && is_dir)
1457 /* We walk in directory order so "ls -f" doesn't get upset. */
1468 closedir_and_clear(cur->fts_dirp);
1471 * If realloc() changed the address of the file name, adjust the
1472 * addresses for the rest of the tree and the dir list.
1475 fts_padjust(sp, head);
1478 * If not changing directories, reset the file name back to original
1481 if (ISSET(FTS_NOCHDIR)) {
1482 if (len == sp->fts_pathlen || nitems == 0)
1488 * If descended after called from fts_children or after called from
1489 * fts_read and nothing found, get back. At the root level we use
1490 * the saved fd; if one of fts_open()'s arguments is a relative name
1491 * to an empty directory, we wind up here with no other way back. If
1492 * can't get back, we're done.
1494 if (descend && (type == BCHILD || !nitems) &&
1495 (cur->fts_level == FTS_ROOTLEVEL
1496 ? RESTORE_INITIAL_CWD(sp)
1497 : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1498 cur->fts_info = FTS_ERR;
1504 /* If didn't find anything, return NULL. */
1507 cur->fts_info = FTS_DP;
1512 /* If there are many entries, no sorting function has been specified,
1513 and this file system is of a type that may be slow with a large
1514 number of entries, then sort the directory entries on increasing
1516 if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
1518 && ISSET (FTS_CWDFD)
1519 && dirent_inode_sort_may_be_useful (sp->fts_cwd_fd)) {
1520 sp->fts_compar = fts_compare_ino;
1521 head = fts_sort (sp, head, nitems);
1522 sp->fts_compar = NULL;
1525 /* Sort the entries. */
1526 if (sp->fts_compar && nitems > 1)
1527 head = fts_sort(sp, head, nitems);
1533 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1534 current hierarchy. There should be a directory with dev/inode
1535 matching those of AD. If not, print a lot of diagnostics. */
1537 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1540 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1542 if (ad->ino == ent->fts_statp->st_ino
1543 && ad->dev == ent->fts_statp->st_dev)
1546 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1547 printf ("active dirs:\n");
1549 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1550 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1551 ad->fts_ent->fts_accpath,
1552 (uintmax_t) ad->dev,
1553 (uintmax_t) ad->ino,
1555 (uintmax_t) ent->fts_statp->st_dev,
1556 (uintmax_t) ent->fts_statp->st_ino);
1560 fts_cross_check (FTS const *sp)
1562 FTSENT const *ent = sp->fts_cur;
1564 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1567 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1568 /* Make sure every parent dir is in the tree. */
1569 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1571 struct Active_dir ad;
1572 ad.ino = t->fts_statp->st_ino;
1573 ad.dev = t->fts_statp->st_dev;
1574 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1575 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1578 /* Make sure every dir in the tree is an active dir.
1579 But ENT is not necessarily a directory. If so, just skip this part. */
1580 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1581 && (ent->fts_info == FTS_DP
1582 || ent->fts_info == FTS_D))
1584 struct Active_dir *ad;
1585 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1586 ad = hash_get_next (sp->fts_cycle.ht, ad))
1588 find_matching_ancestor (ent, ad);
1594 same_fd (int fd1, int fd2)
1596 struct stat sb1, sb2;
1597 return (fstat (fd1, &sb1) == 0
1598 && fstat (fd2, &sb2) == 0
1599 && SAME_INODE (sb1, sb2));
1603 fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
1605 I_ring const *fd_ring = &sp->fts_fd_ring;
1606 unsigned int i = fd_ring->fts_front;
1607 char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0);
1608 fprintf (stream, "=== %s ========== %s\n", msg, cwd);
1610 if (i_ring_empty (fd_ring))
1615 int fd = fd_ring->fts_fd_ring[i];
1617 fprintf (stream, "%d: %d:\n", i, fd);
1620 char *wd = getcwdat (fd, NULL, 0);
1621 fprintf (stream, "%d: %d: %s\n", i, fd, wd);
1624 if (i == fd_ring->fts_back)
1626 i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
1630 /* Ensure that each file descriptor on the fd_ring matches a
1631 parent, grandparent, etc. of the current working directory. */
1633 fd_ring_check (FTS const *sp)
1638 /* Make a writable copy. */
1639 I_ring fd_w = sp->fts_fd_ring;
1641 int cwd_fd = sp->fts_cwd_fd;
1642 cwd_fd = dup (cwd_fd);
1643 char *dot = getcwdat (cwd_fd, NULL, 0);
1644 error (0, 0, "===== check ===== cwd: %s", dot);
1646 while ( ! i_ring_empty (&fd_w))
1648 int fd = i_ring_pop (&fd_w);
1651 int parent_fd = openat (cwd_fd, "..", O_SEARCH | O_NOATIME);
1657 if (!same_fd (fd, parent_fd))
1659 char *cwd = getcwdat (fd, NULL, 0);
1660 error (0, errno, "ring : %s", cwd);
1661 char *c2 = getcwdat (parent_fd, NULL, 0);
1662 error (0, errno, "parent: %s", c2);
1675 static unsigned short int
1677 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1679 struct stat *sbp = p->fts_statp;
1682 if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
1686 * If doing a logical walk, or application requested FTS_FOLLOW, do
1687 * a stat(2). If that fails, check for a non-existent symlink. If
1688 * fail, set the errno from the stat call.
1690 if (ISSET(FTS_LOGICAL) || follow) {
1691 if (stat(p->fts_accpath, sbp)) {
1692 saved_errno = errno;
1694 && lstat(p->fts_accpath, sbp) == 0) {
1696 return (FTS_SLNONE);
1698 p->fts_errno = saved_errno;
1701 } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp,
1702 AT_SYMLINK_NOFOLLOW)) {
1703 p->fts_errno = errno;
1704 err: memset(sbp, 0, sizeof(struct stat));
1708 if (S_ISDIR(sbp->st_mode)) {
1709 p->fts_n_dirs_remaining = (sbp->st_nlink
1710 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1711 if (ISDOT(p->fts_name)) {
1712 /* Command-line "." and ".." are real directories. */
1713 return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
1718 if (S_ISLNK(sbp->st_mode))
1720 if (S_ISREG(sbp->st_mode))
1722 return (FTS_DEFAULT);
1726 fts_compar (void const *a, void const *b)
1728 /* Convert A and B to the correct types, to pacify the compiler, and
1729 for portability to bizarre hosts where "void const *" and "FTSENT
1730 const **" differ in runtime representation. The comparison
1731 function cannot modify *a and *b, but there is no compile-time
1733 FTSENT const **pa = (FTSENT const **) a;
1734 FTSENT const **pb = (FTSENT const **) b;
1735 return pa[0]->fts_fts->fts_compar (pa, pb);
1740 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1742 register FTSENT **ap, *p;
1744 /* On most modern hosts, void * and FTSENT ** have the same
1745 run-time representation, and one can convert sp->fts_compar to
1746 the type qsort expects without problem. Use the heuristic that
1747 this is OK if the two pointer types are the same size, and if
1748 converting FTSENT ** to long int is the same as converting
1749 FTSENT ** to void * and then to long int. This heuristic isn't
1750 valid in general but we don't know of any counterexamples. */
1752 int (*compare) (void const *, void const *) =
1753 ((sizeof &dummy == sizeof (void *)
1754 && (long int) &dummy == (long int) (void *) &dummy)
1755 ? (int (*) (void const *, void const *)) sp->fts_compar
1759 * Construct an array of pointers to the structures and call qsort(3).
1760 * Reassemble the array in the order returned by qsort. If unable to
1761 * sort for memory reasons, return the directory entries in their
1762 * current order. Allocate enough space for the current needs plus
1763 * 40 so don't realloc one entry at a time.
1765 if (nitems > sp->fts_nitems) {
1768 sp->fts_nitems = nitems + 40;
1769 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1770 || ! (a = realloc (sp->fts_array,
1771 sp->fts_nitems * sizeof *a))) {
1772 free(sp->fts_array);
1773 sp->fts_array = NULL;
1779 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1781 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1782 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1783 ap[0]->fts_link = ap[1];
1784 ap[0]->fts_link = NULL;
1790 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1796 * The file name is a variable length array. Allocate the FTSENT
1797 * structure and the file name in one chunk.
1799 len = sizeof(FTSENT) + namelen;
1800 if ((p = malloc(len)) == NULL)
1803 /* Copy the name and guarantee NUL termination. */
1804 memmove(p->fts_name, name, namelen);
1805 p->fts_name[namelen] = '\0';
1807 p->fts_namelen = namelen;
1809 p->fts_path = sp->fts_path;
1813 p->fts_instr = FTS_NOINSTR;
1815 p->fts_pointer = NULL;
1821 fts_lfree (register FTSENT *head)
1825 /* Free a linked list of structures. */
1826 while ((p = head)) {
1827 head = head->fts_link;
1829 closedir (p->fts_dirp);
1835 * Allow essentially unlimited file name lengths; find, rm, ls should
1836 * all work on any tree. Most systems will allow creation of file
1837 * names much longer than MAXPATHLEN, even though the kernel won't
1838 * resolve them. Add the size (not just what's needed) plus 256 bytes
1839 * so don't realloc the file name 2 bytes at a time.
1843 fts_palloc (FTS *sp, size_t more)
1846 size_t new_len = sp->fts_pathlen + more + 256;
1849 * See if fts_pathlen would overflow.
1851 if (new_len < sp->fts_pathlen) {
1853 sp->fts_path = NULL;
1854 __set_errno (ENAMETOOLONG);
1857 sp->fts_pathlen = new_len;
1858 p = realloc(sp->fts_path, sp->fts_pathlen);
1861 sp->fts_path = NULL;
1869 * When the file name is realloc'd, have to fix all of the pointers in
1870 * structures already returned.
1874 fts_padjust (FTS *sp, FTSENT *head)
1877 char *addr = sp->fts_path;
1879 #define ADJUST(p) do { \
1880 if ((p)->fts_accpath != (p)->fts_name) { \
1881 (p)->fts_accpath = \
1882 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1884 (p)->fts_path = addr; \
1886 /* Adjust the current set of children. */
1887 for (p = sp->fts_child; p; p = p->fts_link)
1890 /* Adjust the rest of the tree, including the current level. */
1891 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1893 p = p->fts_link ? p->fts_link : p->fts_parent;
1899 fts_maxarglen (char * const *argv)
1903 for (max = 0; *argv; ++argv)
1904 if ((len = strlen(*argv)) > max)
1910 * Change to dir specified by fd or file name without getting
1911 * tricked by someone changing the world out from underneath us.
1912 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1913 * If FD is non-negative, expect it to be used after this function returns,
1914 * and to be closed eventually. So don't pass e.g., `dirfd(dirp)' and then
1915 * do closedir(dirp), because that would invalidate the saved FD.
1916 * Upon failure, close FD immediately and return nonzero.
1920 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1923 bool is_dotdot = dir && STREQ (dir, "..");
1926 /* This clause handles the unusual case in which FTS_NOCHDIR
1927 is specified, along with FTS_CWDFD. In that case, there is
1928 no need to change even the virtual cwd file descriptor.
1929 However, if FD is non-negative, we do close it here. */
1930 if (ISSET (FTS_NOCHDIR))
1932 if (ISSET (FTS_CWDFD) && 0 <= fd)
1937 if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
1939 /* When possible, skip the diropen and subsequent fstat+dev/ino
1940 comparison. I.e., when changing to parent directory
1941 (chdir ("..")), use a file descriptor from the ring and
1942 save the overhead of diropen+fstat, as well as avoiding
1943 failure when we lack "x" access to the virtual cwd. */
1944 if ( ! i_ring_empty (&sp->fts_fd_ring))
1947 fd_ring_print (sp, stderr, "pre-pop");
1948 parent_fd = i_ring_pop (&sp->fts_fd_ring);
1959 if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
1962 /* The following dev/inode check is necessary if we're doing a
1963 `logical' traversal (through symlinks, a la chown -L), if the
1964 system lacks O_NOFOLLOW support, or if we're changing to ".."
1965 (but not via a popped file descriptor). When changing to the
1966 name "..", O_NOFOLLOW can't help. In general, when the target is
1967 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
1968 follow a symlink, so we can avoid the expense of this fstat. */
1969 if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
1970 || (dir && STREQ (dir, "..")))
1973 if (fstat(newfd, &sb))
1978 if (p->fts_statp->st_dev != sb.st_dev
1979 || p->fts_statp->st_ino != sb.st_ino)
1981 __set_errno (ENOENT); /* disinformation */
1987 if (ISSET(FTS_CWDFD))
1989 cwd_advance_fd (sp, newfd, ! is_dotdot);
1993 ret = fchdir(newfd);
1999 __set_errno (oerrno);