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); \
264 /* The attribute __pure__ was added in gcc 2.96. */
265 #undef _GL_ATTRIBUTE_PURE
266 #if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 96)
267 # define _GL_ATTRIBUTE_PURE __attribute__ ((__pure__))
269 # define _GL_ATTRIBUTE_PURE /* empty */
273 fd_ring_clear (I_ring *fd_ring)
275 while ( ! i_ring_empty (fd_ring))
277 int fd = i_ring_pop (fd_ring);
283 /* Overload the fts_statp->st_size member (otherwise unused, when
284 fts_info is FTS_NSOK) to indicate whether fts_read should stat
285 this entry or not. */
287 fts_set_stat_required (FTSENT *p, bool required)
289 fts_assert (p->fts_info == FTS_NSOK);
290 p->fts_statp->st_size = (required
292 : FTS_NO_STAT_REQUIRED);
295 /* file-descriptor-relative opendir. */
296 /* FIXME: if others need this function, move it into lib/openat.c */
299 opendirat (int fd, char const *dir, int extra_flags, int *pdir_fd)
301 int new_fd = openat (fd, dir,
302 (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
308 set_cloexec_flag (new_fd, true);
309 dirp = fdopendir (new_fd);
314 int saved_errno = errno;
321 /* Virtual fchdir. Advance SP's working directory file descriptor,
322 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
323 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
324 open on sp->fts_cwd_fd; i.e., to move the working directory one level
328 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
330 int old = sp->fts_cwd_fd;
331 fts_assert (old != fd || old == AT_FDCWD);
335 /* Push "old" onto the ring.
336 If the displaced file descriptor is non-negative, close it. */
337 int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);
338 fd_ring_print (sp, stderr, "post-push");
339 if (0 <= prev_fd_in_slot)
340 close (prev_fd_in_slot); /* ignore any close failure */
342 else if ( ! ISSET (FTS_NOCHDIR))
345 close (old); /* ignore any close failure */
351 /* Open the directory DIR if possible, and return a file
352 descriptor. Return -1 and set errno on failure. It doesn't matter
353 whether the file descriptor has read or write access. */
357 diropen (FTS const *sp, char const *dir)
359 int open_flags = (O_SEARCH | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
360 | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0));
362 int fd = (ISSET (FTS_CWDFD)
363 ? openat (sp->fts_cwd_fd, dir, open_flags)
364 : open (dir, open_flags));
366 set_cloexec_flag (fd, true);
371 fts_open (char * const *argv,
372 register int options,
373 int (*compar) (FTSENT const **, FTSENT const **))
376 register FTSENT *p, *root;
377 register size_t nitems;
378 FTSENT *parent = NULL;
379 FTSENT *tmp = NULL; /* pacify gcc */
383 if (options & ~FTS_OPTIONMASK) {
384 __set_errno (EINVAL);
387 if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {
388 __set_errno (EINVAL);
391 if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {
392 __set_errno (EINVAL);
396 /* Allocate/initialize the stream */
397 if ((sp = malloc(sizeof(FTS))) == NULL)
399 memset(sp, 0, sizeof(FTS));
400 sp->fts_compar = compar;
401 sp->fts_options = options;
403 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
404 if (ISSET(FTS_LOGICAL)) {
409 /* Initialize fts_cwd_fd. */
410 sp->fts_cwd_fd = AT_FDCWD;
411 if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)
413 /* While it isn't technically necessary to open "." this
414 early, doing it here saves us the trouble of ensuring
415 later (where it'd be messier) that "." can in fact
416 be opened. If not, revert to FTS_NOCHDIR mode. */
417 int fd = open (".", O_SEARCH);
420 /* Even if `.' is unreadable, don't revert to FTS_NOCHDIR mode
421 on systems like Linux+PROC_FS, where our openat emulation
422 is good enough. Note: on a system that emulates
423 openat via /proc, this technique can still fail, but
424 only in extreme conditions, e.g., when the working
425 directory cannot be saved (i.e. save_cwd fails) --
426 and that happens on Linux only when "." is unreadable
427 and the CWD would be longer than PATH_MAX.
428 FIXME: once Linux kernel openat support is well established,
429 replace the above open call and this entire if/else block
430 with the body of the if-block below. */
431 if ( openat_needs_fchdir ())
444 * Start out with 1K of file name space, and enough, in any case,
445 * to hold the user's file names.
448 # define MAXPATHLEN 1024
451 size_t maxarglen = fts_maxarglen(argv);
452 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
456 /* Allocate/initialize root's parent. */
458 if ((parent = fts_alloc(sp, "", 0)) == NULL)
460 parent->fts_level = FTS_ROOTPARENTLEVEL;
463 /* The classic fts implementation would call fts_stat with
464 a new entry for each iteration of the loop below.
465 If the comparison function is not specified or if the
466 FTS_DEFER_STAT option is in effect, don't stat any entry
467 in this loop. This is an attempt to minimize the interval
468 between the initial stat/lstat/fstatat and the point at which
469 a directory argument is first opened. This matters for any
470 directory command line argument that resides on a file system
471 without genuine i-nodes. If you specify FTS_DEFER_STAT along
472 with a comparison function, that function must not access any
473 data via the fts_statp pointer. */
474 defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));
476 /* Allocate/initialize root(s). */
477 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
478 /* *Do* allow zero-length file names. */
479 size_t len = strlen(*argv);
480 if ((p = fts_alloc(sp, *argv, len)) == NULL)
482 p->fts_level = FTS_ROOTLEVEL;
483 p->fts_parent = parent;
484 p->fts_accpath = p->fts_name;
485 /* Even when defer_stat is true, be sure to stat the first
486 command line argument, since fts_read (at least with
487 FTS_XDEV) requires that. */
488 if (defer_stat && root != NULL) {
489 p->fts_info = FTS_NSOK;
490 fts_set_stat_required(p, true);
492 p->fts_info = fts_stat(sp, p, false);
496 * If comparison routine supplied, traverse in sorted
497 * order; otherwise traverse in the order specified.
512 if (compar && nitems > 1)
513 root = fts_sort(sp, root, nitems);
516 * Allocate a dummy pointer and make fts_read think that we've just
517 * finished the node before the root(s); set p->fts_info to FTS_INIT
518 * so that everything about the "current" node is ignored.
520 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
522 sp->fts_cur->fts_link = root;
523 sp->fts_cur->fts_info = FTS_INIT;
524 if (! setup_dir (sp))
528 * If using chdir(2), grab a file descriptor pointing to dot to ensure
529 * that we can get back here; this could be avoided for some file names,
530 * but almost certainly not worth the effort. Slashes, symbolic links,
531 * and ".." are all fairly nasty problems. Note, if we can't get the
532 * descriptor we run anyway, just more slowly.
534 if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)
535 && (sp->fts_rfd = diropen (sp, ".")) < 0)
538 i_ring_init (&sp->fts_fd_ring, -1);
541 mem3: fts_lfree(root);
543 mem2: free(sp->fts_path);
550 fts_load (FTS *sp, register FTSENT *p)
556 * Load the stream structure for the next traversal. Since we don't
557 * actually enter the directory until after the preorder visit, set
558 * the fts_accpath field specially so the chdir gets done to the right
559 * place and the user can access the first node. From fts_open it's
560 * known that the file name will fit.
562 len = p->fts_pathlen = p->fts_namelen;
563 memmove(sp->fts_path, p->fts_name, len + 1);
564 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
566 memmove(p->fts_name, cp, len + 1);
567 p->fts_namelen = len;
569 p->fts_accpath = p->fts_path = sp->fts_path;
575 register FTSENT *freep, *p;
579 * This still works if we haven't read anything -- the dummy structure
580 * points to the root list, so we step through to the end of the root
581 * list which has a valid parent pointer.
584 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
586 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
592 /* Free up child linked list, sort array, file name buffer. */
594 fts_lfree(sp->fts_child);
598 if (ISSET(FTS_CWDFD))
600 if (0 <= sp->fts_cwd_fd)
601 if (close (sp->fts_cwd_fd))
604 else if (!ISSET(FTS_NOCHDIR))
606 /* Return to original directory, save errno if necessary. */
607 if (fchdir(sp->fts_rfd))
610 /* If close fails, record errno only if saved_errno is zero,
611 so that we report the probably-more-meaningful fchdir errno. */
612 if (close (sp->fts_rfd))
613 if (saved_errno == 0)
617 fd_ring_clear (&sp->fts_fd_ring);
619 if (sp->fts_leaf_optimization_works_ht)
620 hash_free (sp->fts_leaf_optimization_works_ht);
624 /* Free up the stream pointer. */
627 /* Set errno and return. */
629 __set_errno (saved_errno);
636 #if defined __linux__ \
637 && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
639 # include <sys/vfs.h>
641 /* Linux-specific constants from coreutils' src/fs.h */
642 # define S_MAGIC_TMPFS 0x1021994
643 # define S_MAGIC_NFS 0x6969
644 # define S_MAGIC_REISERFS 0x52654973
645 # define S_MAGIC_PROC 0x9FA0
647 /* Return false if it is easy to determine the file system type of
648 the directory on which DIR_FD is open, and sorting dirents on
649 inode numbers is known not to improve traversal performance with
650 that type of file system. Otherwise, return true. */
652 dirent_inode_sort_may_be_useful (int dir_fd)
654 /* Skip the sort only if we can determine efficiently
655 that skipping it is the right thing to do.
656 The cost of performing an unnecessary sort is negligible,
657 while the cost of *not* performing it can be O(N^2) with
658 a very large constant. */
659 struct statfs fs_buf;
661 /* If fstatfs fails, assume sorting would be useful. */
662 if (fstatfs (dir_fd, &fs_buf) != 0)
665 /* FIXME: what about when f_type is not an integral type?
666 deal with that if/when it's encountered. */
667 switch (fs_buf.f_type)
671 /* On a file system of any of these types, sorting
672 is unnecessary, and hence wasteful. */
680 /* Given a file descriptor DIR_FD open on a directory D,
681 return true if it is valid to apply the leaf-optimization
682 technique of counting directories in D via stat.st_nlink. */
684 leaf_optimization_applies (int dir_fd)
686 struct statfs fs_buf;
688 /* If fstatfs fails, assume we can't use the optimization. */
689 if (fstatfs (dir_fd, &fs_buf) != 0)
692 /* FIXME: do we need to detect AFS mount points? I doubt it,
693 unless fstatfs can report S_MAGIC_REISERFS for such a directory. */
695 switch (fs_buf.f_type)
697 /* List here the file system types that lack useable dirent.d_type
698 info, yet for which the optimization does apply. */
699 case S_MAGIC_REISERFS:
703 /* Explicitly listing this or any other file system type for which
704 the optimization is not applicable is not necessary, but we leave
705 it here to document the risk. Per http://bugs.debian.org/143111,
706 /proc may have bogus stat.st_nlink values. */
715 dirent_inode_sort_may_be_useful (int dir_fd _GL_UNUSED) { return true; }
717 leaf_optimization_applies (int dir_fd _GL_UNUSED) { return false; }
720 /* link-count-optimization entry:
721 map an stat.st_dev number to a boolean: leaf_optimization_works */
728 /* Use a tiny initial size. If a traversal encounters more than
729 a few devices, the cost of growing/rehashing this table will be
730 rendered negligible by the number of inodes processed. */
731 enum { LCO_HT_INITIAL_SIZE = 13 };
734 LCO_hash (void const *x, size_t table_size)
736 struct LCO_ent const *ax = x;
737 return (uintmax_t) ax->st_dev % table_size;
741 LCO_compare (void const *x, void const *y)
743 struct LCO_ent const *ax = x;
744 struct LCO_ent const *ay = y;
745 return ax->st_dev == ay->st_dev;
748 /* Ask the same question as leaf_optimization_applies, but query
749 the cache first (FTS.fts_leaf_optimization_works_ht), and if necessary,
750 update that cache. */
752 link_count_optimize_ok (FTSENT const *p)
754 FTS *sp = p->fts_fts;
755 Hash_table *h = sp->fts_leaf_optimization_works_ht;
761 /* If we're not in CWDFD mode, don't bother with this optimization,
762 since the caller is not serious about performance. */
763 if (!ISSET(FTS_CWDFD))
766 /* map st_dev to the boolean, leaf_optimization_works */
769 h = sp->fts_leaf_optimization_works_ht
770 = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash,
775 tmp.st_dev = p->fts_statp->st_dev;
776 ent = hash_lookup (h, &tmp);
780 /* Look-up failed. Query directly and cache the result. */
781 t2 = malloc (sizeof *t2);
785 /* Is it ok to perform the optimization in the dir, FTS_CWD_FD? */
786 opt_ok = leaf_optimization_applies (sp->fts_cwd_fd);
788 t2->st_dev = p->fts_statp->st_dev;
790 ent = hash_insert (h, t2);
793 /* insertion failed */
797 fts_assert (ent == t2);
803 * Special case of "/" at the end of the file name so that slashes aren't
804 * appended which would cause file names to be written as "....//foo".
807 (p->fts_path[p->fts_pathlen - 1] == '/' \
808 ? p->fts_pathlen - 1 : p->fts_pathlen)
811 fts_read (register FTS *sp)
813 register FTSENT *p, *tmp;
814 register unsigned short int instr;
817 /* If finished or unrecoverable error, return NULL. */
818 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
821 /* Set current node pointer. */
824 /* Save and zero out user instructions. */
825 instr = p->fts_instr;
826 p->fts_instr = FTS_NOINSTR;
828 /* Any type of file may be re-visited; re-stat and re-turn. */
829 if (instr == FTS_AGAIN) {
830 p->fts_info = fts_stat(sp, p, false);
833 Dprintf (("fts_read: p=%s\n",
834 p->fts_info == FTS_INIT ? "" : p->fts_path));
837 * Following a symlink -- SLNONE test allows application to see
838 * SLNONE and recover. If indirecting through a symlink, have
839 * keep a pointer to current location. If unable to get that
840 * pointer, follow fails.
842 if (instr == FTS_FOLLOW &&
843 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
844 p->fts_info = fts_stat(sp, p, true);
845 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
846 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
847 p->fts_errno = errno;
848 p->fts_info = FTS_ERR;
850 p->fts_flags |= FTS_SYMFOLLOW;
855 /* Directory in pre-order. */
856 if (p->fts_info == FTS_D) {
857 /* If skipped or crossed mount point, do post-order visit. */
858 if (instr == FTS_SKIP ||
859 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
860 if (p->fts_flags & FTS_SYMFOLLOW)
861 (void)close(p->fts_symfd);
863 fts_lfree(sp->fts_child);
864 sp->fts_child = NULL;
866 p->fts_info = FTS_DP;
867 LEAVE_DIR (sp, p, "1");
871 /* Rebuild if only read the names and now traversing. */
872 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
874 fts_lfree(sp->fts_child);
875 sp->fts_child = NULL;
879 * Cd to the subdirectory.
881 * If have already read and now fail to chdir, whack the list
882 * to make the names come out right, and set the parent errno
883 * so the application will eventually get an error condition.
884 * Set the FTS_DONTCHDIR flag so that when we logically change
885 * directories back to the parent we don't do a chdir.
887 * If haven't read do so. If the read fails, fts_build sets
888 * FTS_STOP or the fts_info field of the node.
890 if (sp->fts_child != NULL) {
891 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
892 p->fts_errno = errno;
893 p->fts_flags |= FTS_DONTCHDIR;
894 for (p = sp->fts_child; p != NULL;
897 p->fts_parent->fts_accpath;
899 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
902 /* If fts_build's call to fts_safe_changedir failed
903 because it was not able to fchdir into a
904 subdirectory, tell the caller. */
905 if (p->fts_errno && p->fts_info != FTS_DNR)
906 p->fts_info = FTS_ERR;
907 LEAVE_DIR (sp, p, "2");
911 sp->fts_child = NULL;
915 /* Move to the next node on this level. */
917 if ((p = p->fts_link) != NULL) {
922 * If reached the top, return to the original directory (or
923 * the root of the tree), and load the file names for the next
926 if (p->fts_level == FTS_ROOTLEVEL) {
927 if (RESTORE_INITIAL_CWD(sp)) {
938 * User may have called fts_set on the node. If skipped,
939 * ignore. If followed, get a file descriptor so we can
940 * get back if necessary.
942 if (p->fts_instr == FTS_SKIP)
944 if (p->fts_instr == FTS_FOLLOW) {
945 p->fts_info = fts_stat(sp, p, true);
946 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
947 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
948 p->fts_errno = errno;
949 p->fts_info = FTS_ERR;
951 p->fts_flags |= FTS_SYMFOLLOW;
953 p->fts_instr = FTS_NOINSTR;
956 name: t = sp->fts_path + NAPPEND(p->fts_parent);
958 memmove(t, p->fts_name, p->fts_namelen + 1);
961 if (p->fts_info == FTS_NSOK)
963 if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
965 FTSENT *parent = p->fts_parent;
966 if (FTS_ROOTLEVEL < p->fts_level
967 /* ->fts_n_dirs_remaining is not valid
968 for command-line-specified names. */
969 && parent->fts_n_dirs_remaining == 0
971 && ISSET(FTS_PHYSICAL)
972 && link_count_optimize_ok (parent))
974 /* nothing more needed */
978 p->fts_info = fts_stat(sp, p, false);
979 if (S_ISDIR(p->fts_statp->st_mode)
980 && p->fts_level != FTS_ROOTLEVEL
981 && parent->fts_n_dirs_remaining)
982 parent->fts_n_dirs_remaining--;
986 fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
989 if (p->fts_info == FTS_D)
991 /* Now that P->fts_statp is guaranteed to be valid,
992 if this is a command-line directory, record its
993 device number, to be used for FTS_XDEV. */
994 if (p->fts_level == FTS_ROOTLEVEL)
995 sp->fts_dev = p->fts_statp->st_dev;
996 Dprintf ((" entering: %s\n", p->fts_path));
997 if (! enter_dir (sp, p))
999 __set_errno (ENOMEM);
1006 /* Move up to the parent node. */
1007 p = tmp->fts_parent;
1011 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
1013 * Done; free everything up and set errno to 0 so the user
1014 * can distinguish between error and EOF.
1018 return (sp->fts_cur = NULL);
1021 fts_assert (p->fts_info != FTS_NSOK);
1023 /* NUL terminate the file name. */
1024 sp->fts_path[p->fts_pathlen] = '\0';
1027 * Return to the parent directory. If at a root node, restore
1028 * the initial working directory. If we came through a symlink,
1029 * go back through the file descriptor. Otherwise, move up
1030 * one level, via "..".
1032 if (p->fts_level == FTS_ROOTLEVEL) {
1033 if (RESTORE_INITIAL_CWD(sp)) {
1034 p->fts_errno = errno;
1037 } else if (p->fts_flags & FTS_SYMFOLLOW) {
1038 if (FCHDIR(sp, p->fts_symfd)) {
1039 int saved_errno = errno;
1040 (void)close(p->fts_symfd);
1041 __set_errno (saved_errno);
1042 p->fts_errno = errno;
1045 (void)close(p->fts_symfd);
1046 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
1047 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
1048 p->fts_errno = errno;
1051 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
1052 if (p->fts_errno == 0)
1053 LEAVE_DIR (sp, p, "3");
1054 return ISSET(FTS_STOP) ? NULL : p;
1058 * Fts_set takes the stream as an argument although it's not used in this
1059 * implementation; it would be necessary if anyone wanted to add global
1060 * semantics to fts using fts_set. An error return is allowed for similar
1065 fts_set(FTS *sp _GL_UNUSED, FTSENT *p, int instr)
1067 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
1068 instr != FTS_NOINSTR && instr != FTS_SKIP) {
1069 __set_errno (EINVAL);
1072 p->fts_instr = instr;
1077 fts_children (register FTS *sp, int instr)
1082 if (instr != 0 && instr != FTS_NAMEONLY) {
1083 __set_errno (EINVAL);
1087 /* Set current node pointer. */
1091 * Errno set to 0 so user can distinguish empty directory from
1096 /* Fatal errors stop here. */
1097 if (ISSET(FTS_STOP))
1100 /* Return logical hierarchy of user's arguments. */
1101 if (p->fts_info == FTS_INIT)
1102 return (p->fts_link);
1105 * If not a directory being visited in pre-order, stop here. Could
1106 * allow FTS_DNR, assuming the user has fixed the problem, but the
1107 * same effect is available with FTS_AGAIN.
1109 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
1112 /* Free up any previous child list. */
1113 if (sp->fts_child != NULL)
1114 fts_lfree(sp->fts_child);
1116 if (instr == FTS_NAMEONLY) {
1123 * If using chdir on a relative file name and called BEFORE fts_read
1124 * does its chdir to the root of a traversal, we can lose -- we need to
1125 * chdir into the subdirectory, and we don't know where the current
1126 * directory is, so we can't get back so that the upcoming chdir by
1127 * fts_read will work.
1129 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
1131 return (sp->fts_child = fts_build(sp, instr));
1133 if ((fd = diropen (sp, ".")) < 0)
1134 return (sp->fts_child = NULL);
1135 sp->fts_child = fts_build(sp, instr);
1136 if (ISSET(FTS_CWDFD))
1138 cwd_advance_fd (sp, fd, true);
1144 int saved_errno = errno;
1146 __set_errno (saved_errno);
1151 return (sp->fts_child);
1154 /* A comparison function to sort on increasing inode number.
1155 For some file system types, sorting either way makes a huge
1156 performance difference for a directory with very many entries,
1157 but sorting on increasing values is slightly better than sorting
1158 on decreasing values. The difference is in the 5% range. */
1160 fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b)
1162 return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? -1
1163 : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? 1 : 0);
1166 /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode
1167 S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */
1169 set_stat_type (struct stat *st, unsigned int dtype)
1202 * This is the tricky part -- do not casually change *anything* in here. The
1203 * idea is to build the linked list of entries that are used by fts_children
1204 * and fts_read. There are lots of special cases.
1206 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
1207 * set and it's a physical walk (so that symbolic links can't be directories),
1208 * we can do things quickly. First, if it's a 4.4BSD file system, the type
1209 * of the file is in the directory entry. Otherwise, we assume that the number
1210 * of subdirectories in a node is equal to the number of links to the parent.
1211 * The former skips all stat calls. The latter skips stat calls in any leaf
1212 * directories and for any files after the subdirectories in the directory have
1213 * been found, cutting the stat calls by about 2/3.
1217 fts_build (register FTS *sp, int type)
1219 register struct dirent *dp;
1220 register FTSENT *p, *head;
1221 register size_t nitems;
1231 size_t len, maxlen, new_len;
1235 /* Set current node pointer. */
1239 * Open the directory for reading. If this fails, we're done.
1240 * If being called from fts_read, set the fts_info field.
1242 #if defined FTS_WHITEOUT && 0
1243 if (ISSET(FTS_WHITEOUT))
1244 oflag = DTF_NODUP|DTF_REWIND;
1246 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
1248 # define __opendir2(file, flag) \
1249 opendirat((! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
1250 ? sp->fts_cwd_fd : AT_FDCWD), \
1252 ((ISSET(FTS_PHYSICAL) \
1253 && ! (ISSET(FTS_COMFOLLOW) \
1254 && cur->fts_level == FTS_ROOTLEVEL)) \
1255 ? O_NOFOLLOW : 0), \
1258 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
1259 if (type == BREAD) {
1260 cur->fts_info = FTS_DNR;
1261 cur->fts_errno = errno;
1265 /* Rather than calling fts_stat for each and every entry encountered
1266 in the readdir loop (below), stat each directory only right after
1268 if (cur->fts_info == FTS_NSOK)
1269 cur->fts_info = fts_stat(sp, cur, false);
1270 else if (sp->fts_options & FTS_TIGHT_CYCLE_CHECK) {
1271 /* Now read the stat info again after opening a directory to
1272 * reveal eventual changes caused by a submount triggered by
1273 * the traversal. But do it only for utilities which use
1274 * FTS_TIGHT_CYCLE_CHECK. Therefore, only find and du
1275 * benefit/suffer from this feature for now.
1277 LEAVE_DIR (sp, cur, "4");
1278 fts_stat (sp, cur, false);
1279 if (! enter_dir (sp, cur)) {
1280 __set_errno (ENOMEM);
1286 * Nlinks is the number of possible entries of type directory in the
1287 * directory if we're cheating on stat calls, 0 if we're not doing
1288 * any stat calls at all, (nlink_t) -1 if we're statting everything.
1290 if (type == BNAMES) {
1292 /* Be quiet about nostat, GCC. */
1294 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
1295 nlinks = (cur->fts_statp->st_nlink
1296 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1304 * If we're going to need to stat anything or we want to descend
1305 * and stay in the directory, chdir. If this fails we keep going,
1306 * but set a flag so we don't chdir after the post-order visit.
1307 * We won't be able to stat anything, but we can still return the
1308 * names themselves. Note, that since fts_read won't be able to
1309 * chdir into the directory, it will have to return different file
1310 * names than before, i.e. "a/b" instead of "b". Since the node
1311 * has already been visited in pre-order, have to wait until the
1312 * post-order visit to return the error. There is a special case
1313 * here, if there was nothing to stat then it's not an error to
1314 * not be able to stat. This is all fairly nasty. If a program
1315 * needed sorted entries or stat information, they had better be
1316 * checking FTS_NS on the returned nodes.
1318 if (nlinks || type == BREAD) {
1319 if (ISSET(FTS_CWDFD))
1321 dir_fd = dup (dir_fd);
1323 set_cloexec_flag (dir_fd, true);
1325 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
1326 if (nlinks && type == BREAD)
1327 cur->fts_errno = errno;
1328 cur->fts_flags |= FTS_DONTCHDIR;
1331 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1340 * Figure out the max file name length that can be stored in the
1341 * current buffer -- the inner loop allocates more space as necessary.
1342 * We really wouldn't have to do the maxlen calculations here, we
1343 * could do them in fts_read before returning the name, but it's a
1344 * lot easier here since the length is part of the dirent structure.
1346 * If not changing directories set a pointer so that can just append
1347 * each new component into the file name.
1350 if (ISSET(FTS_NOCHDIR)) {
1351 cp = sp->fts_path + len;
1354 /* GCC, you're too verbose. */
1358 maxlen = sp->fts_pathlen - len;
1360 level = cur->fts_level + 1;
1362 /* Read the directory, attaching each entry to the `link' pointer. */
1364 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
1367 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1370 if ((p = fts_alloc (sp, dp->d_name,
1371 _D_EXACT_NAMLEN (dp))) == NULL)
1373 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
1374 /* include space for NUL */
1375 oldaddr = sp->fts_path;
1376 if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
1378 * No more memory. Save
1379 * errno, free up the current structure and the
1380 * structures already allocated.
1382 mem1: saved_errno = errno;
1386 cur->fts_info = FTS_ERR;
1388 __set_errno (saved_errno);
1391 /* Did realloc() change the pointer? */
1392 if (oldaddr != sp->fts_path) {
1394 if (ISSET(FTS_NOCHDIR))
1395 cp = sp->fts_path + len;
1397 maxlen = sp->fts_pathlen - len;
1400 new_len = len + _D_EXACT_NAMLEN (dp);
1401 if (new_len < len) {
1403 * In the unlikely event that we would end up
1404 * with a file name longer than SIZE_MAX, free up
1405 * the current structure and the structures already
1406 * allocated, then error out with ENAMETOOLONG.
1411 cur->fts_info = FTS_ERR;
1413 __set_errno (ENAMETOOLONG);
1416 p->fts_level = level;
1417 p->fts_parent = sp->fts_cur;
1418 p->fts_pathlen = new_len;
1420 #if defined FTS_WHITEOUT && 0
1421 if (dp->d_type == DT_WHT)
1422 p->fts_flags |= FTS_ISW;
1424 /* Store dirent.d_ino, in case we need to sort
1425 entries before processing them. */
1426 p->fts_statp->st_ino = D_INO (dp);
1428 /* Build a file name for fts_stat to stat. */
1429 if (ISSET(FTS_NOCHDIR)) {
1430 p->fts_accpath = p->fts_path;
1431 memmove(cp, p->fts_name, p->fts_namelen + 1);
1433 p->fts_accpath = p->fts_name;
1435 if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {
1436 /* Record what fts_read will have to do with this
1437 entry. In many cases, it will simply fts_stat it,
1438 but we can take advantage of any d_type information
1439 to optimize away the unnecessary stat calls. I.e.,
1440 if FTS_NOSTAT is in effect and we're not following
1441 symlinks (FTS_PHYSICAL) and d_type indicates this
1442 is *not* a directory, then we won't have to stat it
1443 at all. If it *is* a directory, then (currently)
1444 we stat it regardless, in order to get device and
1445 inode numbers. Some day we might optimize that
1446 away, too, for directories where d_ino is known to
1448 bool skip_stat = (ISSET(FTS_PHYSICAL)
1449 && ISSET(FTS_NOSTAT)
1451 && ! DT_MUST_BE(dp, DT_DIR));
1452 p->fts_info = FTS_NSOK;
1453 /* Propagate dirent.d_type information back
1454 to caller, when possible. */
1455 set_stat_type (p->fts_statp, D_TYPE (dp));
1456 fts_set_stat_required(p, !skip_stat);
1457 is_dir = (ISSET(FTS_PHYSICAL)
1458 && DT_MUST_BE(dp, DT_DIR));
1460 p->fts_info = fts_stat(sp, p, false);
1461 is_dir = (p->fts_info == FTS_D
1462 || p->fts_info == FTS_DC
1463 || p->fts_info == FTS_DOT);
1466 /* Decrement link count if applicable. */
1467 if (nlinks > 0 && is_dir)
1470 /* We walk in directory order so "ls -f" doesn't get upset. */
1484 * If realloc() changed the address of the file name, adjust the
1485 * addresses for the rest of the tree and the dir list.
1488 fts_padjust(sp, head);
1491 * If not changing directories, reset the file name back to original
1494 if (ISSET(FTS_NOCHDIR)) {
1495 if (len == sp->fts_pathlen || nitems == 0)
1501 * If descended after called from fts_children or after called from
1502 * fts_read and nothing found, get back. At the root level we use
1503 * the saved fd; if one of fts_open()'s arguments is a relative name
1504 * to an empty directory, we wind up here with no other way back. If
1505 * can't get back, we're done.
1507 if (descend && (type == BCHILD || !nitems) &&
1508 (cur->fts_level == FTS_ROOTLEVEL
1509 ? RESTORE_INITIAL_CWD(sp)
1510 : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1511 cur->fts_info = FTS_ERR;
1517 /* If didn't find anything, return NULL. */
1520 cur->fts_info = FTS_DP;
1525 /* If there are many entries, no sorting function has been specified,
1526 and this file system is of a type that may be slow with a large
1527 number of entries, then sort the directory entries on increasing
1529 if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
1531 && ISSET (FTS_CWDFD)
1532 && dirent_inode_sort_may_be_useful (sp->fts_cwd_fd)) {
1533 sp->fts_compar = fts_compare_ino;
1534 head = fts_sort (sp, head, nitems);
1535 sp->fts_compar = NULL;
1538 /* Sort the entries. */
1539 if (sp->fts_compar && nitems > 1)
1540 head = fts_sort(sp, head, nitems);
1546 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1547 current hierarchy. There should be a directory with dev/inode
1548 matching those of AD. If not, print a lot of diagnostics. */
1550 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1553 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1555 if (ad->ino == ent->fts_statp->st_ino
1556 && ad->dev == ent->fts_statp->st_dev)
1559 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1560 printf ("active dirs:\n");
1562 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1563 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1564 ad->fts_ent->fts_accpath,
1565 (uintmax_t) ad->dev,
1566 (uintmax_t) ad->ino,
1568 (uintmax_t) ent->fts_statp->st_dev,
1569 (uintmax_t) ent->fts_statp->st_ino);
1573 fts_cross_check (FTS const *sp)
1575 FTSENT const *ent = sp->fts_cur;
1577 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1580 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1581 /* Make sure every parent dir is in the tree. */
1582 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1584 struct Active_dir ad;
1585 ad.ino = t->fts_statp->st_ino;
1586 ad.dev = t->fts_statp->st_dev;
1587 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1588 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1591 /* Make sure every dir in the tree is an active dir.
1592 But ENT is not necessarily a directory. If so, just skip this part. */
1593 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1594 && (ent->fts_info == FTS_DP
1595 || ent->fts_info == FTS_D))
1597 struct Active_dir *ad;
1598 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1599 ad = hash_get_next (sp->fts_cycle.ht, ad))
1601 find_matching_ancestor (ent, ad);
1607 same_fd (int fd1, int fd2)
1609 struct stat sb1, sb2;
1610 return (fstat (fd1, &sb1) == 0
1611 && fstat (fd2, &sb2) == 0
1612 && SAME_INODE (sb1, sb2));
1616 fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
1618 I_ring const *fd_ring = &sp->fts_fd_ring;
1619 unsigned int i = fd_ring->fts_front;
1620 char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0);
1621 fprintf (stream, "=== %s ========== %s\n", msg, cwd);
1623 if (i_ring_empty (fd_ring))
1628 int fd = fd_ring->fts_fd_ring[i];
1630 fprintf (stream, "%d: %d:\n", i, fd);
1633 char *wd = getcwdat (fd, NULL, 0);
1634 fprintf (stream, "%d: %d: %s\n", i, fd, wd);
1637 if (i == fd_ring->fts_back)
1639 i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
1643 /* Ensure that each file descriptor on the fd_ring matches a
1644 parent, grandparent, etc. of the current working directory. */
1646 fd_ring_check (FTS const *sp)
1651 /* Make a writable copy. */
1652 I_ring fd_w = sp->fts_fd_ring;
1654 int cwd_fd = sp->fts_cwd_fd;
1655 cwd_fd = dup (cwd_fd);
1656 char *dot = getcwdat (cwd_fd, NULL, 0);
1657 error (0, 0, "===== check ===== cwd: %s", dot);
1659 while ( ! i_ring_empty (&fd_w))
1661 int fd = i_ring_pop (&fd_w);
1664 int parent_fd = openat (cwd_fd, "..", O_SEARCH);
1670 if (!same_fd (fd, parent_fd))
1672 char *cwd = getcwdat (fd, NULL, 0);
1673 error (0, errno, "ring : %s", cwd);
1674 char *c2 = getcwdat (parent_fd, NULL, 0);
1675 error (0, errno, "parent: %s", c2);
1688 static unsigned short int
1690 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1692 struct stat *sbp = p->fts_statp;
1695 if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
1698 #if defined FTS_WHITEOUT && 0
1699 /* check for whiteout */
1700 if (p->fts_flags & FTS_ISW) {
1701 memset(sbp, '\0', sizeof (*sbp));
1702 sbp->st_mode = S_IFWHT;
1708 * If doing a logical walk, or application requested FTS_FOLLOW, do
1709 * a stat(2). If that fails, check for a non-existent symlink. If
1710 * fail, set the errno from the stat call.
1712 if (ISSET(FTS_LOGICAL) || follow) {
1713 if (stat(p->fts_accpath, sbp)) {
1714 saved_errno = errno;
1716 && lstat(p->fts_accpath, sbp) == 0) {
1718 return (FTS_SLNONE);
1720 p->fts_errno = saved_errno;
1723 } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp,
1724 AT_SYMLINK_NOFOLLOW)) {
1725 p->fts_errno = errno;
1726 err: memset(sbp, 0, sizeof(struct stat));
1730 if (S_ISDIR(sbp->st_mode)) {
1731 p->fts_n_dirs_remaining = (sbp->st_nlink
1732 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1733 if (ISDOT(p->fts_name)) {
1734 /* Command-line "." and ".." are real directories. */
1735 return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
1740 if (S_ISLNK(sbp->st_mode))
1742 if (S_ISREG(sbp->st_mode))
1744 return (FTS_DEFAULT);
1748 fts_compar (void const *a, void const *b)
1750 /* Convert A and B to the correct types, to pacify the compiler, and
1751 for portability to bizarre hosts where "void const *" and "FTSENT
1752 const **" differ in runtime representation. The comparison
1753 function cannot modify *a and *b, but there is no compile-time
1755 FTSENT const **pa = (FTSENT const **) a;
1756 FTSENT const **pb = (FTSENT const **) b;
1757 return pa[0]->fts_fts->fts_compar (pa, pb);
1762 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1764 register FTSENT **ap, *p;
1766 /* On most modern hosts, void * and FTSENT ** have the same
1767 run-time representation, and one can convert sp->fts_compar to
1768 the type qsort expects without problem. Use the heuristic that
1769 this is OK if the two pointer types are the same size, and if
1770 converting FTSENT ** to long int is the same as converting
1771 FTSENT ** to void * and then to long int. This heuristic isn't
1772 valid in general but we don't know of any counterexamples. */
1774 int (*compare) (void const *, void const *) =
1775 ((sizeof &dummy == sizeof (void *)
1776 && (long int) &dummy == (long int) (void *) &dummy)
1777 ? (int (*) (void const *, void const *)) sp->fts_compar
1781 * Construct an array of pointers to the structures and call qsort(3).
1782 * Reassemble the array in the order returned by qsort. If unable to
1783 * sort for memory reasons, return the directory entries in their
1784 * current order. Allocate enough space for the current needs plus
1785 * 40 so don't realloc one entry at a time.
1787 if (nitems > sp->fts_nitems) {
1790 sp->fts_nitems = nitems + 40;
1791 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1792 || ! (a = realloc (sp->fts_array,
1793 sp->fts_nitems * sizeof *a))) {
1794 free(sp->fts_array);
1795 sp->fts_array = NULL;
1801 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1803 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1804 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1805 ap[0]->fts_link = ap[1];
1806 ap[0]->fts_link = NULL;
1812 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1818 * The file name is a variable length array. Allocate the FTSENT
1819 * structure and the file name in one chunk.
1821 len = sizeof(FTSENT) + namelen;
1822 if ((p = malloc(len)) == NULL)
1825 /* Copy the name and guarantee NUL termination. */
1826 memmove(p->fts_name, name, namelen);
1827 p->fts_name[namelen] = '\0';
1829 p->fts_namelen = namelen;
1831 p->fts_path = sp->fts_path;
1834 p->fts_instr = FTS_NOINSTR;
1836 p->fts_pointer = NULL;
1842 fts_lfree (register FTSENT *head)
1846 /* Free a linked list of structures. */
1847 while ((p = head)) {
1848 head = head->fts_link;
1854 * Allow essentially unlimited file name lengths; find, rm, ls should
1855 * all work on any tree. Most systems will allow creation of file
1856 * names much longer than MAXPATHLEN, even though the kernel won't
1857 * resolve them. Add the size (not just what's needed) plus 256 bytes
1858 * so don't realloc the file name 2 bytes at a time.
1862 fts_palloc (FTS *sp, size_t more)
1865 size_t new_len = sp->fts_pathlen + more + 256;
1868 * See if fts_pathlen would overflow.
1870 if (new_len < sp->fts_pathlen) {
1872 sp->fts_path = NULL;
1873 __set_errno (ENAMETOOLONG);
1876 sp->fts_pathlen = new_len;
1877 p = realloc(sp->fts_path, sp->fts_pathlen);
1880 sp->fts_path = NULL;
1888 * When the file name is realloc'd, have to fix all of the pointers in
1889 * structures already returned.
1893 fts_padjust (FTS *sp, FTSENT *head)
1896 char *addr = sp->fts_path;
1898 #define ADJUST(p) do { \
1899 if ((p)->fts_accpath != (p)->fts_name) { \
1900 (p)->fts_accpath = \
1901 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1903 (p)->fts_path = addr; \
1905 /* Adjust the current set of children. */
1906 for (p = sp->fts_child; p; p = p->fts_link)
1909 /* Adjust the rest of the tree, including the current level. */
1910 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1912 p = p->fts_link ? p->fts_link : p->fts_parent;
1917 internal_function _GL_ATTRIBUTE_PURE
1918 fts_maxarglen (char * const *argv)
1922 for (max = 0; *argv; ++argv)
1923 if ((len = strlen(*argv)) > max)
1929 * Change to dir specified by fd or file name without getting
1930 * tricked by someone changing the world out from underneath us.
1931 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1932 * If FD is non-negative, expect it to be used after this function returns,
1933 * and to be closed eventually. So don't pass e.g., `dirfd(dirp)' and then
1934 * do closedir(dirp), because that would invalidate the saved FD.
1935 * Upon failure, close FD immediately and return nonzero.
1939 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1942 bool is_dotdot = dir && STREQ (dir, "..");
1945 /* This clause handles the unusual case in which FTS_NOCHDIR
1946 is specified, along with FTS_CWDFD. In that case, there is
1947 no need to change even the virtual cwd file descriptor.
1948 However, if FD is non-negative, we do close it here. */
1949 if (ISSET (FTS_NOCHDIR))
1951 if (ISSET (FTS_CWDFD) && 0 <= fd)
1956 if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
1958 /* When possible, skip the diropen and subsequent fstat+dev/ino
1959 comparison. I.e., when changing to parent directory
1960 (chdir ("..")), use a file descriptor from the ring and
1961 save the overhead of diropen+fstat, as well as avoiding
1962 failure when we lack "x" access to the virtual cwd. */
1963 if ( ! i_ring_empty (&sp->fts_fd_ring))
1966 fd_ring_print (sp, stderr, "pre-pop");
1967 parent_fd = i_ring_pop (&sp->fts_fd_ring);
1978 if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
1981 /* The following dev/inode check is necessary if we're doing a
1982 `logical' traversal (through symlinks, a la chown -L), if the
1983 system lacks O_NOFOLLOW support, or if we're changing to ".."
1984 (but not via a popped file descriptor). When changing to the
1985 name "..", O_NOFOLLOW can't help. In general, when the target is
1986 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
1987 follow a symlink, so we can avoid the expense of this fstat. */
1988 if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
1989 || (dir && STREQ (dir, "..")))
1992 if (fstat(newfd, &sb))
1997 if (p->fts_statp->st_dev != sb.st_dev
1998 || p->fts_statp->st_ino != sb.st_ino)
2000 __set_errno (ENOENT); /* disinformation */
2006 if (ISSET(FTS_CWDFD))
2008 cwd_advance_fd (sp, newfd, ! is_dotdot);
2012 ret = fchdir(newfd);
2018 __set_errno (oerrno);