1 /* Traverse a file hierarchy.
3 Copyright (C) 2004-2009 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 opendir __opendir
166 # define readdir __readdir
168 # undef internal_function
169 # define internal_function /* empty */
173 # define __set_errno(Val) errno = (Val)
176 /* If this host provides the openat function, then we can avoid
177 attempting to open "." in some initialization code below. */
179 # define HAVE_OPENAT_SUPPORT 1
181 # define HAVE_OPENAT_SUPPORT 0
185 # define fts_assert(expr) ((void) 0)
187 # define fts_assert(expr) \
196 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
197 static FTSENT *fts_build (FTS *, int) internal_function;
198 static void fts_lfree (FTSENT *) internal_function;
199 static void fts_load (FTS *, FTSENT *) internal_function;
200 static size_t fts_maxarglen (char * const *) internal_function;
201 static void fts_padjust (FTS *, FTSENT *) internal_function;
202 static bool fts_palloc (FTS *, size_t) internal_function;
203 static FTSENT *fts_sort (FTS *, FTSENT *, size_t) internal_function;
204 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
205 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
209 # include "fts-cycle.c"
211 static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
212 static void leave_dir (FTS *fts, FTSENT *ent) {}
213 static bool setup_dir (FTS *fts) { return true; }
214 static void free_dir (FTS *fts) {}
218 # define MAX(a,b) ((a) > (b) ? (a) : (b))
222 # define SIZE_MAX ((size_t) -1)
225 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
226 #define STREQ(a, b) (strcmp ((a), (b)) == 0)
228 #define CLR(opt) (sp->fts_options &= ~(opt))
229 #define ISSET(opt) (sp->fts_options & (opt))
230 #define SET(opt) (sp->fts_options |= (opt))
232 /* FIXME: make this a function */
233 #define RESTORE_INITIAL_CWD(sp) \
234 (fd_ring_clear (&((sp)->fts_fd_ring)), \
235 FCHDIR ((sp), (ISSET (FTS_CWDFD) ? AT_FDCWD : (sp)->fts_rfd)))
237 /* FIXME: FTS_NOCHDIR is now misnamed.
238 Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
239 #define FCHDIR(sp, fd) \
240 (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \
241 ? (cwd_advance_fd ((sp), (fd), true), 0) \
245 /* fts_build flags */
246 /* FIXME: make this an enum */
247 #define BCHILD 1 /* fts_children */
248 #define BNAMES 2 /* fts_children, names only */
249 #define BREAD 3 /* fts_read */
252 # include <inttypes.h>
255 # include "getcwdat.h"
256 bool fts_debug = false;
257 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
260 # define fd_ring_check(x)
261 # define fd_ring_print(a, b, c)
264 #define LEAVE_DIR(Fts, Ent, Tag) \
267 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
268 leave_dir (Fts, Ent); \
269 fd_ring_check (Fts); \
274 fd_ring_clear (I_ring *fd_ring)
276 while ( ! i_ring_empty (fd_ring))
278 int fd = i_ring_pop (fd_ring);
284 /* Overload the fts_statp->st_size member (otherwise unused, when
285 fts_info is FTS_NSOK) to indicate whether fts_read should stat
286 this entry or not. */
288 fts_set_stat_required (FTSENT *p, bool required)
290 fts_assert (p->fts_info == FTS_NSOK);
291 p->fts_statp->st_size = (required
293 : FTS_NO_STAT_REQUIRED);
296 /* file-descriptor-relative opendir. */
297 /* FIXME: if others need this function, move it into lib/openat.c */
300 opendirat (int fd, char const *dir)
302 int new_fd = openat (fd, dir,
303 O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK);
308 set_cloexec_flag (new_fd, true);
309 dirp = fdopendir (new_fd);
312 int saved_errno = errno;
319 /* Virtual fchdir. Advance SP's working directory file descriptor,
320 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
321 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
322 open on sp->fts_cwd_fd; i.e., to move the working directory one level
326 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
328 int old = sp->fts_cwd_fd;
329 fts_assert (old != fd || old == AT_FDCWD);
333 /* Push "old" onto the ring.
334 If the displaced file descriptor is non-negative, close it. */
335 int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);
336 fd_ring_print (sp, stderr, "post-push");
337 if (0 <= prev_fd_in_slot)
338 close (prev_fd_in_slot); /* ignore any close failure */
340 else if ( ! ISSET (FTS_NOCHDIR))
343 close (old); /* ignore any close failure */
349 /* Open the directory DIR if possible, and return a file
350 descriptor. Return -1 and set errno on failure. It doesn't matter
351 whether the file descriptor has read or write access. */
355 diropen (FTS const *sp, char const *dir)
357 int open_flags = (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
358 | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0));
360 int fd = (ISSET (FTS_CWDFD)
361 ? openat (sp->fts_cwd_fd, dir, open_flags)
362 : open (dir, open_flags));
364 set_cloexec_flag (fd, true);
369 fts_open (char * const *argv,
370 register int options,
371 int (*compar) (FTSENT const **, FTSENT const **))
374 register FTSENT *p, *root;
375 register size_t nitems;
376 FTSENT *parent = NULL;
377 FTSENT *tmp = NULL; /* pacify gcc */
382 if (options & ~FTS_OPTIONMASK) {
383 __set_errno (EINVAL);
386 if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {
387 __set_errno (EINVAL);
390 if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {
391 __set_errno (EINVAL);
395 /* Allocate/initialize the stream */
396 if ((sp = malloc(sizeof(FTS))) == NULL)
398 memset(sp, 0, sizeof(FTS));
399 sp->fts_compar = compar;
400 sp->fts_options = options;
402 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
403 if (ISSET(FTS_LOGICAL)) {
408 /* Initialize fts_cwd_fd. */
409 sp->fts_cwd_fd = AT_FDCWD;
410 if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)
412 /* While it isn't technically necessary to open "." this
413 early, doing it here saves us the trouble of ensuring
414 later (where it'd be messier) that "." can in fact
415 be opened. If not, revert to FTS_NOCHDIR mode. */
416 int fd = open (".", O_RDONLY);
419 /* Even if `.' is unreadable, don't revert to FTS_NOCHDIR mode
420 on systems like Linux+PROC_FS, where our openat emulation
421 is good enough. Note: on a system that emulates
422 openat via /proc, this technique can still fail, but
423 only in extreme conditions, e.g., when the working
424 directory cannot be saved (i.e. save_cwd fails) --
425 and that happens on Linux only when "." is unreadable
426 and the CWD would be longer than PATH_MAX.
427 FIXME: once Linux kernel openat support is well established,
428 replace the above open call and this entire if/else block
429 with the body of the if-block below. */
430 if ( openat_needs_fchdir ())
443 * Start out with 1K of file name space, and enough, in any case,
444 * to hold the user's file names.
447 # define MAXPATHLEN 1024
450 size_t maxarglen = fts_maxarglen(argv);
451 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
455 /* Allocate/initialize root's parent. */
457 if ((parent = fts_alloc(sp, "", 0)) == NULL)
459 parent->fts_level = FTS_ROOTPARENTLEVEL;
462 /* The classic fts implementation would call fts_stat with
463 a new entry for each iteration of the loop below.
464 If the comparison function is not specified or if the
465 FTS_DEFER_STAT option is in effect, don't stat any entry
466 in this loop. This is an attempt to minimize the interval
467 between the initial stat/lstat/fstatat and the point at which
468 a directory argument is first opened. This matters for any
469 directory command line argument that resides on a file system
470 without genuine i-nodes. If you specify FTS_DEFER_STAT along
471 with a comparison function, that function must not access any
472 data via the fts_statp pointer. */
473 defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));
475 /* Allocate/initialize root(s). */
476 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
477 /* Don't allow zero-length file names. */
478 if ((len = strlen(*argv)) == 0) {
479 __set_errno (ENOENT);
483 if ((p = fts_alloc(sp, *argv, len)) == NULL)
485 p->fts_level = FTS_ROOTLEVEL;
486 p->fts_parent = parent;
487 p->fts_accpath = p->fts_name;
488 /* Even when defer_stat is true, be sure to stat the first
489 command line argument, since fts_read (at least with
490 FTS_XDEV) requires that. */
491 if (defer_stat && root != NULL) {
492 p->fts_info = FTS_NSOK;
493 fts_set_stat_required(p, true);
495 p->fts_info = fts_stat(sp, p, false);
499 * If comparison routine supplied, traverse in sorted
500 * order; otherwise traverse in the order specified.
515 if (compar && nitems > 1)
516 root = fts_sort(sp, root, nitems);
519 * Allocate a dummy pointer and make fts_read think that we've just
520 * finished the node before the root(s); set p->fts_info to FTS_INIT
521 * so that everything about the "current" node is ignored.
523 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
525 sp->fts_cur->fts_link = root;
526 sp->fts_cur->fts_info = FTS_INIT;
527 if (! setup_dir (sp))
531 * If using chdir(2), grab a file descriptor pointing to dot to ensure
532 * that we can get back here; this could be avoided for some file names,
533 * but almost certainly not worth the effort. Slashes, symbolic links,
534 * and ".." are all fairly nasty problems. Note, if we can't get the
535 * descriptor we run anyway, just more slowly.
537 if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)
538 && (sp->fts_rfd = diropen (sp, ".")) < 0)
541 i_ring_init (&sp->fts_fd_ring, -1);
544 mem3: fts_lfree(root);
546 mem2: free(sp->fts_path);
553 fts_load (FTS *sp, register FTSENT *p)
559 * Load the stream structure for the next traversal. Since we don't
560 * actually enter the directory until after the preorder visit, set
561 * the fts_accpath field specially so the chdir gets done to the right
562 * place and the user can access the first node. From fts_open it's
563 * known that the file name will fit.
565 len = p->fts_pathlen = p->fts_namelen;
566 memmove(sp->fts_path, p->fts_name, len + 1);
567 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
569 memmove(p->fts_name, cp, len + 1);
570 p->fts_namelen = len;
572 p->fts_accpath = p->fts_path = sp->fts_path;
578 register FTSENT *freep, *p;
582 * This still works if we haven't read anything -- the dummy structure
583 * points to the root list, so we step through to the end of the root
584 * list which has a valid parent pointer.
587 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
589 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
595 /* Free up child linked list, sort array, file name buffer. */
597 fts_lfree(sp->fts_child);
601 if (ISSET(FTS_CWDFD))
603 if (0 <= sp->fts_cwd_fd)
604 if (close (sp->fts_cwd_fd))
607 else if (!ISSET(FTS_NOCHDIR))
609 /* Return to original directory, save errno if necessary. */
610 if (fchdir(sp->fts_rfd))
613 /* If close fails, record errno only if saved_errno is zero,
614 so that we report the probably-more-meaningful fchdir errno. */
615 if (close (sp->fts_rfd))
616 if (saved_errno == 0)
620 fd_ring_clear (&sp->fts_fd_ring);
623 if (sp->fts_leaf_optimization_works_ht)
624 hash_free (sp->fts_leaf_optimization_works_ht);
629 /* Free up the stream pointer. */
632 /* Set errno and return. */
634 __set_errno (saved_errno);
641 #if defined __linux__ \
642 && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
646 /* Linux-specific constants from coreutils' src/fs.h */
647 # define S_MAGIC_TMPFS 0x1021994
648 # define S_MAGIC_NFS 0x6969
649 # define S_MAGIC_REISERFS 0x52654973
650 # define S_MAGIC_PROC 0x9FA0
652 /* Return false if it is easy to determine the file system type of
653 the directory on which DIR_FD is open, and sorting dirents on
654 inode numbers is known not to improve traversal performance with
655 that type of file system. Otherwise, return true. */
657 dirent_inode_sort_may_be_useful (int dir_fd)
659 /* Skip the sort only if we can determine efficiently
660 that skipping it is the right thing to do.
661 The cost of performing an unnecessary sort is negligible,
662 while the cost of *not* performing it can be O(N^2) with
663 a very large constant. */
664 struct statfs fs_buf;
666 /* If fstatfs fails, assume sorting would be useful. */
667 if (fstatfs (dir_fd, &fs_buf) != 0)
670 /* FIXME: what about when f_type is not an integral type?
671 deal with that if/when it's encountered. */
672 switch (fs_buf.f_type)
676 /* On a file system of any of these types, sorting
677 is unnecessary, and hence wasteful. */
685 /* Given a file descriptor DIR_FD open on a directory D,
686 return true if it is valid to apply the leaf-optimization
687 technique of counting directories in D via stat.st_nlink. */
689 leaf_optimization_applies (int dir_fd)
691 struct statfs fs_buf;
693 /* If fstatfs fails, assume we can't use the optimization. */
694 if (fstatfs (dir_fd, &fs_buf) != 0)
697 /* FIXME: do we need to detect AFS mount points? I doubt it,
698 unless fstatfs can report S_MAGIC_REISERFS for such a directory. */
700 switch (fs_buf.f_type)
702 /* List here the file system types that lack useable dirent.d_type
703 info, yet for which the optimization does apply. */
704 case S_MAGIC_REISERFS:
708 /* Explicitly listing this or any other file system type for which
709 the optimization is not applicable is not necessary, but we leave
710 it here to document the risk. Per http://bugs.debian.org/143111,
711 /proc may have bogus stat.st_nlink values. */
720 dirent_inode_sort_may_be_useful (int dir_fd _UNUSED_PARAMETER_) { return true; }
722 leaf_optimization_applies (int dir_fd _UNUSED_PARAMETER_) { return false; }
726 /* link-count-optimization entry:
727 map an stat.st_dev number to a boolean: leaf_optimization_works */
734 /* Use a tiny initial size. If a traversal encounters more than
735 a few devices, the cost of growing/rehashing this table will be
736 rendered negligible by the number of inodes processed. */
737 enum { LCO_HT_INITIAL_SIZE = 13 };
740 LCO_hash (void const *x, size_t table_size)
742 struct LCO_ent const *ax = x;
743 return (uintmax_t) ax->st_dev % table_size;
747 LCO_compare (void const *x, void const *y)
749 struct LCO_ent const *ax = x;
750 struct LCO_ent const *ay = y;
751 return ax->st_dev == ay->st_dev;
754 /* Ask the same question as leaf_optimization_applies, but query
755 the cache first (FTS.fts_leaf_optimization_works_ht), and if necessary,
756 update that cache. */
758 link_count_optimize_ok (FTSENT const *p)
760 FTS *sp = p->fts_fts;
761 Hash_table *h = sp->fts_leaf_optimization_works_ht;
767 /* If we're not in CWDFD mode, don't bother with this optimization,
768 since the caller is not serious about performance. */
769 if (!ISSET(FTS_CWDFD))
772 /* map st_dev to the boolean, leaf_optimization_works */
775 h = sp->fts_leaf_optimization_works_ht
776 = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash,
781 tmp.st_dev = p->fts_statp->st_dev;
782 ent = hash_lookup (h, &tmp);
786 /* Look-up failed. Query directly and cache the result. */
787 t2 = malloc (sizeof *t2);
791 /* Is it ok to perform the optimization in the dir, FTS_CWD_FD? */
792 opt_ok = leaf_optimization_applies (sp->fts_cwd_fd);
794 t2->st_dev = p->fts_statp->st_dev;
796 ent = hash_insert (h, t2);
799 /* insertion failed */
803 fts_assert (ent == t2);
810 * Special case of "/" at the end of the file name so that slashes aren't
811 * appended which would cause file names to be written as "....//foo".
814 (p->fts_path[p->fts_pathlen - 1] == '/' \
815 ? p->fts_pathlen - 1 : p->fts_pathlen)
818 fts_read (register FTS *sp)
820 register FTSENT *p, *tmp;
821 register unsigned short int instr;
824 /* If finished or unrecoverable error, return NULL. */
825 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
828 /* Set current node pointer. */
831 /* Save and zero out user instructions. */
832 instr = p->fts_instr;
833 p->fts_instr = FTS_NOINSTR;
835 /* Any type of file may be re-visited; re-stat and re-turn. */
836 if (instr == FTS_AGAIN) {
837 p->fts_info = fts_stat(sp, p, false);
840 Dprintf (("fts_read: p=%s\n",
841 p->fts_info == FTS_INIT ? "" : p->fts_path));
844 * Following a symlink -- SLNONE test allows application to see
845 * SLNONE and recover. If indirecting through a symlink, have
846 * keep a pointer to current location. If unable to get that
847 * pointer, follow fails.
849 if (instr == FTS_FOLLOW &&
850 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
851 p->fts_info = fts_stat(sp, p, true);
852 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
853 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
854 p->fts_errno = errno;
855 p->fts_info = FTS_ERR;
857 p->fts_flags |= FTS_SYMFOLLOW;
862 /* Directory in pre-order. */
863 if (p->fts_info == FTS_D) {
864 /* If skipped or crossed mount point, do post-order visit. */
865 if (instr == FTS_SKIP ||
866 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
867 if (p->fts_flags & FTS_SYMFOLLOW)
868 (void)close(p->fts_symfd);
870 fts_lfree(sp->fts_child);
871 sp->fts_child = NULL;
873 p->fts_info = FTS_DP;
874 LEAVE_DIR (sp, p, "1");
878 /* Rebuild if only read the names and now traversing. */
879 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
881 fts_lfree(sp->fts_child);
882 sp->fts_child = NULL;
886 * Cd to the subdirectory.
888 * If have already read and now fail to chdir, whack the list
889 * to make the names come out right, and set the parent errno
890 * so the application will eventually get an error condition.
891 * Set the FTS_DONTCHDIR flag so that when we logically change
892 * directories back to the parent we don't do a chdir.
894 * If haven't read do so. If the read fails, fts_build sets
895 * FTS_STOP or the fts_info field of the node.
897 if (sp->fts_child != NULL) {
898 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
899 p->fts_errno = errno;
900 p->fts_flags |= FTS_DONTCHDIR;
901 for (p = sp->fts_child; p != NULL;
904 p->fts_parent->fts_accpath;
906 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
909 /* If fts_build's call to fts_safe_changedir failed
910 because it was not able to fchdir into a
911 subdirectory, tell the caller. */
912 if (p->fts_errno && p->fts_info != FTS_DNR)
913 p->fts_info = FTS_ERR;
914 LEAVE_DIR (sp, p, "2");
918 sp->fts_child = NULL;
922 /* Move to the next node on this level. */
924 if ((p = p->fts_link) != NULL) {
929 * If reached the top, return to the original directory (or
930 * the root of the tree), and load the file names for the next
933 if (p->fts_level == FTS_ROOTLEVEL) {
934 if (RESTORE_INITIAL_CWD(sp)) {
945 * User may have called fts_set on the node. If skipped,
946 * ignore. If followed, get a file descriptor so we can
947 * get back if necessary.
949 if (p->fts_instr == FTS_SKIP)
951 if (p->fts_instr == FTS_FOLLOW) {
952 p->fts_info = fts_stat(sp, p, true);
953 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
954 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
955 p->fts_errno = errno;
956 p->fts_info = FTS_ERR;
958 p->fts_flags |= FTS_SYMFOLLOW;
960 p->fts_instr = FTS_NOINSTR;
963 name: t = sp->fts_path + NAPPEND(p->fts_parent);
965 memmove(t, p->fts_name, p->fts_namelen + 1);
968 if (p->fts_info == FTS_NSOK)
970 if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
972 FTSENT *parent = p->fts_parent;
973 if (FTS_ROOTLEVEL < p->fts_level
974 /* ->fts_n_dirs_remaining is not valid
975 for command-line-specified names. */
976 && parent->fts_n_dirs_remaining == 0
978 && ISSET(FTS_PHYSICAL)
979 && link_count_optimize_ok (parent))
981 /* nothing more needed */
985 p->fts_info = fts_stat(sp, p, false);
986 if (S_ISDIR(p->fts_statp->st_mode)
987 && p->fts_level != FTS_ROOTLEVEL
988 && parent->fts_n_dirs_remaining)
989 parent->fts_n_dirs_remaining--;
993 fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
996 if (p->fts_info == FTS_D)
998 /* Now that P->fts_statp is guaranteed to be valid,
999 if this is a command-line directory, record its
1000 device number, to be used for FTS_XDEV. */
1001 if (p->fts_level == FTS_ROOTLEVEL)
1002 sp->fts_dev = p->fts_statp->st_dev;
1003 Dprintf ((" entering: %s\n", p->fts_path));
1004 if (! enter_dir (sp, p))
1006 __set_errno (ENOMEM);
1013 /* Move up to the parent node. */
1014 p = tmp->fts_parent;
1018 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
1020 * Done; free everything up and set errno to 0 so the user
1021 * can distinguish between error and EOF.
1025 return (sp->fts_cur = NULL);
1028 fts_assert (p->fts_info != FTS_NSOK);
1030 /* NUL terminate the file name. */
1031 sp->fts_path[p->fts_pathlen] = '\0';
1034 * Return to the parent directory. If at a root node, restore
1035 * the initial working directory. If we came through a symlink,
1036 * go back through the file descriptor. Otherwise, move up
1037 * one level, via "..".
1039 if (p->fts_level == FTS_ROOTLEVEL) {
1040 if (RESTORE_INITIAL_CWD(sp)) {
1041 p->fts_errno = errno;
1044 } else if (p->fts_flags & FTS_SYMFOLLOW) {
1045 if (FCHDIR(sp, p->fts_symfd)) {
1046 int saved_errno = errno;
1047 (void)close(p->fts_symfd);
1048 __set_errno (saved_errno);
1049 p->fts_errno = errno;
1052 (void)close(p->fts_symfd);
1053 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
1054 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
1055 p->fts_errno = errno;
1058 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
1059 if (p->fts_errno == 0)
1060 LEAVE_DIR (sp, p, "3");
1061 return ISSET(FTS_STOP) ? NULL : p;
1065 * Fts_set takes the stream as an argument although it's not used in this
1066 * implementation; it would be necessary if anyone wanted to add global
1067 * semantics to fts using fts_set. An error return is allowed for similar
1072 fts_set(FTS *sp _UNUSED_PARAMETER_, FTSENT *p, int instr)
1074 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
1075 instr != FTS_NOINSTR && instr != FTS_SKIP) {
1076 __set_errno (EINVAL);
1079 p->fts_instr = instr;
1084 fts_children (register FTS *sp, int instr)
1089 if (instr != 0 && instr != FTS_NAMEONLY) {
1090 __set_errno (EINVAL);
1094 /* Set current node pointer. */
1098 * Errno set to 0 so user can distinguish empty directory from
1103 /* Fatal errors stop here. */
1104 if (ISSET(FTS_STOP))
1107 /* Return logical hierarchy of user's arguments. */
1108 if (p->fts_info == FTS_INIT)
1109 return (p->fts_link);
1112 * If not a directory being visited in pre-order, stop here. Could
1113 * allow FTS_DNR, assuming the user has fixed the problem, but the
1114 * same effect is available with FTS_AGAIN.
1116 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
1119 /* Free up any previous child list. */
1120 if (sp->fts_child != NULL)
1121 fts_lfree(sp->fts_child);
1123 if (instr == FTS_NAMEONLY) {
1130 * If using chdir on a relative file name and called BEFORE fts_read
1131 * does its chdir to the root of a traversal, we can lose -- we need to
1132 * chdir into the subdirectory, and we don't know where the current
1133 * directory is, so we can't get back so that the upcoming chdir by
1134 * fts_read will work.
1136 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
1138 return (sp->fts_child = fts_build(sp, instr));
1140 if ((fd = diropen (sp, ".")) < 0)
1141 return (sp->fts_child = NULL);
1142 sp->fts_child = fts_build(sp, instr);
1143 if (ISSET(FTS_CWDFD))
1145 cwd_advance_fd (sp, fd, true);
1151 int saved_errno = errno;
1153 __set_errno (saved_errno);
1158 return (sp->fts_child);
1161 /* A comparison function to sort on increasing inode number.
1162 For some file system types, sorting either way makes a huge
1163 performance difference for a directory with very many entries,
1164 but sorting on increasing values is slightly better than sorting
1165 on decreasing values. The difference is in the 5% range. */
1167 fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b)
1169 return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? -1
1170 : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? 1 : 0);
1173 /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode
1174 S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */
1176 set_stat_type (struct stat *st, unsigned int dtype)
1209 * This is the tricky part -- do not casually change *anything* in here. The
1210 * idea is to build the linked list of entries that are used by fts_children
1211 * and fts_read. There are lots of special cases.
1213 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
1214 * set and it's a physical walk (so that symbolic links can't be directories),
1215 * we can do things quickly. First, if it's a 4.4BSD file system, the type
1216 * of the file is in the directory entry. Otherwise, we assume that the number
1217 * of subdirectories in a node is equal to the number of links to the parent.
1218 * The former skips all stat calls. The latter skips stat calls in any leaf
1219 * directories and for any files after the subdirectories in the directory have
1220 * been found, cutting the stat calls by about 2/3.
1224 fts_build (register FTS *sp, int type)
1226 register struct dirent *dp;
1227 register FTSENT *p, *head;
1228 register size_t nitems;
1238 size_t len, maxlen, new_len;
1241 /* Set current node pointer. */
1245 * Open the directory for reading. If this fails, we're done.
1246 * If being called from fts_read, set the fts_info field.
1248 #if defined FTS_WHITEOUT && 0
1249 if (ISSET(FTS_WHITEOUT))
1250 oflag = DTF_NODUP|DTF_REWIND;
1252 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
1254 # define __opendir2(file, flag) \
1255 ( ! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
1256 ? opendirat(sp->fts_cwd_fd, file) \
1259 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
1260 if (type == BREAD) {
1261 cur->fts_info = FTS_DNR;
1262 cur->fts_errno = errno;
1266 /* Rather than calling fts_stat for each and every entry encountered
1267 in the readdir loop (below), stat each directory only right after
1269 if (cur->fts_info == FTS_NSOK)
1270 cur->fts_info = fts_stat(sp, cur, false);
1271 else if (sp->fts_options & FTS_TIGHT_CYCLE_CHECK) {
1272 /* Now read the stat info again after opening a directory to
1273 * reveal eventual changes caused by a submount triggered by
1274 * the traversal. But do it only for utilities which use
1275 * FTS_TIGHT_CYCLE_CHECK. Therefore, only find and du
1276 * benefit/suffer from this feature for now.
1278 LEAVE_DIR (sp, cur, "4");
1279 fts_stat (sp, cur, false);
1280 if (! enter_dir (sp, cur)) {
1281 __set_errno (ENOMEM);
1287 * Nlinks is the number of possible entries of type directory in the
1288 * directory if we're cheating on stat calls, 0 if we're not doing
1289 * any stat calls at all, (nlink_t) -1 if we're statting everything.
1291 if (type == BNAMES) {
1293 /* Be quiet about nostat, GCC. */
1295 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
1296 nlinks = (cur->fts_statp->st_nlink
1297 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1305 * If we're going to need to stat anything or we want to descend
1306 * and stay in the directory, chdir. If this fails we keep going,
1307 * but set a flag so we don't chdir after the post-order visit.
1308 * We won't be able to stat anything, but we can still return the
1309 * names themselves. Note, that since fts_read won't be able to
1310 * chdir into the directory, it will have to return different file
1311 * names than before, i.e. "a/b" instead of "b". Since the node
1312 * has already been visited in pre-order, have to wait until the
1313 * post-order visit to return the error. There is a special case
1314 * here, if there was nothing to stat then it's not an error to
1315 * not be able to stat. This is all fairly nasty. If a program
1316 * needed sorted entries or stat information, they had better be
1317 * checking FTS_NS on the returned nodes.
1319 if (nlinks || type == BREAD) {
1320 int dir_fd = dirfd(dirp);
1321 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1323 dir_fd = dup (dir_fd);
1324 set_cloexec_flag (dir_fd, true);
1326 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
1327 if (nlinks && type == BREAD)
1328 cur->fts_errno = errno;
1329 cur->fts_flags |= FTS_DONTCHDIR;
1332 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1341 * Figure out the max file name length that can be stored in the
1342 * current buffer -- the inner loop allocates more space as necessary.
1343 * We really wouldn't have to do the maxlen calculations here, we
1344 * could do them in fts_read before returning the name, but it's a
1345 * lot easier here since the length is part of the dirent structure.
1347 * If not changing directories set a pointer so that can just append
1348 * each new component into the file name.
1351 if (ISSET(FTS_NOCHDIR)) {
1352 cp = sp->fts_path + len;
1355 /* GCC, you're too verbose. */
1359 maxlen = sp->fts_pathlen - len;
1361 level = cur->fts_level + 1;
1363 /* Read the directory, attaching each entry to the `link' pointer. */
1365 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
1368 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1371 if ((p = fts_alloc (sp, dp->d_name,
1372 _D_EXACT_NAMLEN (dp))) == NULL)
1374 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
1375 /* include space for NUL */
1376 oldaddr = sp->fts_path;
1377 if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
1379 * No more memory. Save
1380 * errno, free up the current structure and the
1381 * structures already allocated.
1383 mem1: saved_errno = errno;
1387 cur->fts_info = FTS_ERR;
1389 __set_errno (saved_errno);
1392 /* Did realloc() change the pointer? */
1393 if (oldaddr != sp->fts_path) {
1395 if (ISSET(FTS_NOCHDIR))
1396 cp = sp->fts_path + len;
1398 maxlen = sp->fts_pathlen - len;
1401 new_len = len + _D_EXACT_NAMLEN (dp);
1402 if (new_len < len) {
1404 * In the unlikely event that we would end up
1405 * with a file name longer than SIZE_MAX, free up
1406 * the current structure and the structures already
1407 * allocated, then error out with ENAMETOOLONG.
1412 cur->fts_info = FTS_ERR;
1414 __set_errno (ENAMETOOLONG);
1417 p->fts_level = level;
1418 p->fts_parent = sp->fts_cur;
1419 p->fts_pathlen = new_len;
1421 #if defined FTS_WHITEOUT && 0
1422 if (dp->d_type == DT_WHT)
1423 p->fts_flags |= FTS_ISW;
1425 /* Store dirent.d_ino, in case we need to sort
1426 entries before processing them. */
1427 p->fts_statp->st_ino = D_INO (dp);
1429 /* Build a file name for fts_stat to stat. */
1430 if (ISSET(FTS_NOCHDIR)) {
1431 p->fts_accpath = p->fts_path;
1432 memmove(cp, p->fts_name, p->fts_namelen + 1);
1434 p->fts_accpath = p->fts_name;
1436 if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {
1437 /* Record what fts_read will have to do with this
1438 entry. In many cases, it will simply fts_stat it,
1439 but we can take advantage of any d_type information
1440 to optimize away the unnecessary stat calls. I.e.,
1441 if FTS_NOSTAT is in effect and we're not following
1442 symlinks (FTS_PHYSICAL) and d_type indicates this
1443 is *not* a directory, then we won't have to stat it
1444 at all. If it *is* a directory, then (currently)
1445 we stat it regardless, in order to get device and
1446 inode numbers. Some day we might optimize that
1447 away, too, for directories where d_ino is known to
1449 bool skip_stat = (ISSET(FTS_PHYSICAL)
1450 && ISSET(FTS_NOSTAT)
1452 && ! DT_MUST_BE(dp, DT_DIR));
1453 p->fts_info = FTS_NSOK;
1454 /* Propagate dirent.d_type information back
1455 to caller, when possible. */
1456 set_stat_type (p->fts_statp, D_TYPE (dp));
1457 fts_set_stat_required(p, !skip_stat);
1458 is_dir = (ISSET(FTS_PHYSICAL)
1459 && DT_MUST_BE(dp, DT_DIR));
1461 p->fts_info = fts_stat(sp, p, false);
1462 is_dir = (p->fts_info == FTS_D
1463 || p->fts_info == FTS_DC
1464 || p->fts_info == FTS_DOT);
1467 /* Decrement link count if applicable. */
1468 if (nlinks > 0 && is_dir)
1471 /* We walk in directory order so "ls -f" doesn't get upset. */
1485 * If realloc() changed the address of the file name, adjust the
1486 * addresses for the rest of the tree and the dir list.
1489 fts_padjust(sp, head);
1492 * If not changing directories, reset the file name back to original
1495 if (ISSET(FTS_NOCHDIR)) {
1496 if (len == sp->fts_pathlen || nitems == 0)
1502 * If descended after called from fts_children or after called from
1503 * fts_read and nothing found, get back. At the root level we use
1504 * the saved fd; if one of fts_open()'s arguments is a relative name
1505 * to an empty directory, we wind up here with no other way back. If
1506 * can't get back, we're done.
1508 if (descend && (type == BCHILD || !nitems) &&
1509 (cur->fts_level == FTS_ROOTLEVEL
1510 ? RESTORE_INITIAL_CWD(sp)
1511 : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1512 cur->fts_info = FTS_ERR;
1518 /* If didn't find anything, return NULL. */
1521 cur->fts_info = FTS_DP;
1526 /* If there are many entries, no sorting function has been specified,
1527 and this file system is of a type that may be slow with a large
1528 number of entries, then sort the directory entries on increasing
1530 if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
1532 && ISSET (FTS_CWDFD)
1533 && dirent_inode_sort_may_be_useful (sp->fts_cwd_fd)) {
1534 sp->fts_compar = fts_compare_ino;
1535 head = fts_sort (sp, head, nitems);
1536 sp->fts_compar = NULL;
1539 /* Sort the entries. */
1540 if (sp->fts_compar && nitems > 1)
1541 head = fts_sort(sp, head, nitems);
1547 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1548 current hierarchy. There should be a directory with dev/inode
1549 matching those of AD. If not, print a lot of diagnostics. */
1551 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1554 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1556 if (ad->ino == ent->fts_statp->st_ino
1557 && ad->dev == ent->fts_statp->st_dev)
1560 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1561 printf ("active dirs:\n");
1563 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1564 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1565 ad->fts_ent->fts_accpath,
1566 (uintmax_t) ad->dev,
1567 (uintmax_t) ad->ino,
1569 (uintmax_t) ent->fts_statp->st_dev,
1570 (uintmax_t) ent->fts_statp->st_ino);
1574 fts_cross_check (FTS const *sp)
1576 FTSENT const *ent = sp->fts_cur;
1578 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1581 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1582 /* Make sure every parent dir is in the tree. */
1583 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1585 struct Active_dir ad;
1586 ad.ino = t->fts_statp->st_ino;
1587 ad.dev = t->fts_statp->st_dev;
1588 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1589 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1592 /* Make sure every dir in the tree is an active dir.
1593 But ENT is not necessarily a directory. If so, just skip this part. */
1594 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1595 && (ent->fts_info == FTS_DP
1596 || ent->fts_info == FTS_D))
1598 struct Active_dir *ad;
1599 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1600 ad = hash_get_next (sp->fts_cycle.ht, ad))
1602 find_matching_ancestor (ent, ad);
1608 same_fd (int fd1, int fd2)
1610 struct stat sb1, sb2;
1611 return (fstat (fd1, &sb1) == 0
1612 && fstat (fd2, &sb2) == 0
1613 && SAME_INODE (sb1, sb2));
1617 fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
1619 I_ring const *fd_ring = &sp->fts_fd_ring;
1620 unsigned int i = fd_ring->fts_front;
1621 char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0);
1622 fprintf (stream, "=== %s ========== %s\n", msg, cwd);
1624 if (i_ring_empty (fd_ring))
1629 int fd = fd_ring->fts_fd_ring[i];
1631 fprintf (stream, "%d: %d:\n", i, fd);
1634 char *wd = getcwdat (fd, NULL, 0);
1635 fprintf (stream, "%d: %d: %s\n", i, fd, wd);
1638 if (i == fd_ring->fts_back)
1640 i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
1644 /* Ensure that each file descriptor on the fd_ring matches a
1645 parent, grandparent, etc. of the current working directory. */
1647 fd_ring_check (FTS const *sp)
1652 /* Make a writable copy. */
1653 I_ring fd_w = sp->fts_fd_ring;
1655 int cwd_fd = sp->fts_cwd_fd;
1656 cwd_fd = dup (cwd_fd);
1657 char *dot = getcwdat (cwd_fd, NULL, 0);
1658 error (0, 0, "===== check ===== cwd: %s", dot);
1660 while ( ! i_ring_empty (&fd_w))
1662 int fd = i_ring_pop (&fd_w);
1665 int parent_fd = openat (cwd_fd, "..", O_RDONLY);
1671 if (!same_fd (fd, parent_fd))
1673 char *cwd = getcwdat (fd, NULL, 0);
1674 error (0, errno, "ring : %s", cwd);
1675 char *c2 = getcwdat (parent_fd, NULL, 0);
1676 error (0, errno, "parent: %s", c2);
1689 static unsigned short int
1691 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1693 struct stat *sbp = p->fts_statp;
1696 if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
1699 #if defined FTS_WHITEOUT && 0
1700 /* check for whiteout */
1701 if (p->fts_flags & FTS_ISW) {
1702 memset(sbp, '\0', sizeof (*sbp));
1703 sbp->st_mode = S_IFWHT;
1709 * If doing a logical walk, or application requested FTS_FOLLOW, do
1710 * a stat(2). If that fails, check for a non-existent symlink. If
1711 * fail, set the errno from the stat call.
1713 if (ISSET(FTS_LOGICAL) || follow) {
1714 if (stat(p->fts_accpath, sbp)) {
1715 saved_errno = errno;
1717 && lstat(p->fts_accpath, sbp) == 0) {
1719 return (FTS_SLNONE);
1721 p->fts_errno = saved_errno;
1724 } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp,
1725 AT_SYMLINK_NOFOLLOW)) {
1726 p->fts_errno = errno;
1727 err: memset(sbp, 0, sizeof(struct stat));
1731 if (S_ISDIR(sbp->st_mode)) {
1732 p->fts_n_dirs_remaining = (sbp->st_nlink
1733 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1734 if (ISDOT(p->fts_name)) {
1735 /* Command-line "." and ".." are real directories. */
1736 return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
1742 * Cycle detection is done by brute force when the directory
1743 * is first encountered. If the tree gets deep enough or the
1744 * number of symbolic links to directories is high enough,
1745 * something faster might be worthwhile.
1749 for (t = p->fts_parent;
1750 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1751 if (sbp->st_ino == t->fts_statp->st_ino
1752 && sbp->st_dev == t->fts_statp->st_dev)
1762 if (S_ISLNK(sbp->st_mode))
1764 if (S_ISREG(sbp->st_mode))
1766 return (FTS_DEFAULT);
1770 fts_compar (void const *a, void const *b)
1772 /* Convert A and B to the correct types, to pacify the compiler, and
1773 for portability to bizarre hosts where "void const *" and "FTSENT
1774 const **" differ in runtime representation. The comparison
1775 function cannot modify *a and *b, but there is no compile-time
1777 FTSENT const **pa = (FTSENT const **) a;
1778 FTSENT const **pb = (FTSENT const **) b;
1779 return pa[0]->fts_fts->fts_compar (pa, pb);
1784 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1786 register FTSENT **ap, *p;
1788 /* On most modern hosts, void * and FTSENT ** have the same
1789 run-time representation, and one can convert sp->fts_compar to
1790 the type qsort expects without problem. Use the heuristic that
1791 this is OK if the two pointer types are the same size, and if
1792 converting FTSENT ** to long int is the same as converting
1793 FTSENT ** to void * and then to long int. This heuristic isn't
1794 valid in general but we don't know of any counterexamples. */
1796 int (*compare) (void const *, void const *) =
1797 ((sizeof &dummy == sizeof (void *)
1798 && (long int) &dummy == (long int) (void *) &dummy)
1799 ? (int (*) (void const *, void const *)) sp->fts_compar
1803 * Construct an array of pointers to the structures and call qsort(3).
1804 * Reassemble the array in the order returned by qsort. If unable to
1805 * sort for memory reasons, return the directory entries in their
1806 * current order. Allocate enough space for the current needs plus
1807 * 40 so don't realloc one entry at a time.
1809 if (nitems > sp->fts_nitems) {
1812 sp->fts_nitems = nitems + 40;
1813 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1814 || ! (a = realloc (sp->fts_array,
1815 sp->fts_nitems * sizeof *a))) {
1816 free(sp->fts_array);
1817 sp->fts_array = NULL;
1823 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1825 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1826 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1827 ap[0]->fts_link = ap[1];
1828 ap[0]->fts_link = NULL;
1834 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1840 * The file name is a variable length array. Allocate the FTSENT
1841 * structure and the file name in one chunk.
1843 len = sizeof(FTSENT) + namelen;
1844 if ((p = malloc(len)) == NULL)
1847 /* Copy the name and guarantee NUL termination. */
1848 memmove(p->fts_name, name, namelen);
1849 p->fts_name[namelen] = '\0';
1851 p->fts_namelen = namelen;
1853 p->fts_path = sp->fts_path;
1856 p->fts_instr = FTS_NOINSTR;
1858 p->fts_pointer = NULL;
1864 fts_lfree (register FTSENT *head)
1868 /* Free a linked list of structures. */
1869 while ((p = head)) {
1870 head = head->fts_link;
1876 * Allow essentially unlimited file name lengths; find, rm, ls should
1877 * all work on any tree. Most systems will allow creation of file
1878 * names much longer than MAXPATHLEN, even though the kernel won't
1879 * resolve them. Add the size (not just what's needed) plus 256 bytes
1880 * so don't realloc the file name 2 bytes at a time.
1884 fts_palloc (FTS *sp, size_t more)
1887 size_t new_len = sp->fts_pathlen + more + 256;
1890 * See if fts_pathlen would overflow.
1892 if (new_len < sp->fts_pathlen) {
1894 sp->fts_path = NULL;
1895 __set_errno (ENAMETOOLONG);
1898 sp->fts_pathlen = new_len;
1899 p = realloc(sp->fts_path, sp->fts_pathlen);
1902 sp->fts_path = NULL;
1910 * When the file name is realloc'd, have to fix all of the pointers in
1911 * structures already returned.
1915 fts_padjust (FTS *sp, FTSENT *head)
1918 char *addr = sp->fts_path;
1920 #define ADJUST(p) do { \
1921 if ((p)->fts_accpath != (p)->fts_name) { \
1922 (p)->fts_accpath = \
1923 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1925 (p)->fts_path = addr; \
1927 /* Adjust the current set of children. */
1928 for (p = sp->fts_child; p; p = p->fts_link)
1931 /* Adjust the rest of the tree, including the current level. */
1932 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1934 p = p->fts_link ? p->fts_link : p->fts_parent;
1940 fts_maxarglen (char * const *argv)
1944 for (max = 0; *argv; ++argv)
1945 if ((len = strlen(*argv)) > max)
1951 * Change to dir specified by fd or file name without getting
1952 * tricked by someone changing the world out from underneath us.
1953 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1954 * If FD is non-negative, expect it to be used after this function returns,
1955 * and to be closed eventually. So don't pass e.g., `dirfd(dirp)' and then
1956 * do closedir(dirp), because that would invalidate the saved FD.
1957 * Upon failure, close FD immediately and return nonzero.
1961 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1964 bool is_dotdot = dir && STREQ (dir, "..");
1967 /* This clause handles the unusual case in which FTS_NOCHDIR
1968 is specified, along with FTS_CWDFD. In that case, there is
1969 no need to change even the virtual cwd file descriptor.
1970 However, if FD is non-negative, we do close it here. */
1971 if (ISSET (FTS_NOCHDIR))
1973 if (ISSET (FTS_CWDFD) && 0 <= fd)
1978 if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
1980 /* When possible, skip the diropen and subsequent fstat+dev/ino
1981 comparison. I.e., when changing to parent directory
1982 (chdir ("..")), use a file descriptor from the ring and
1983 save the overhead of diropen+fstat, as well as avoiding
1984 failure when we lack "x" access to the virtual cwd. */
1985 if ( ! i_ring_empty (&sp->fts_fd_ring))
1988 fd_ring_print (sp, stderr, "pre-pop");
1989 parent_fd = i_ring_pop (&sp->fts_fd_ring);
2000 if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
2003 /* The following dev/inode check is necessary if we're doing a
2004 `logical' traversal (through symlinks, a la chown -L), if the
2005 system lacks O_NOFOLLOW support, or if we're changing to ".."
2006 (but not via a popped file descriptor). When changing to the
2007 name "..", O_NOFOLLOW can't help. In general, when the target is
2008 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
2009 follow a symlink, so we can avoid the expense of this fstat. */
2010 if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
2011 || (dir && STREQ (dir, "..")))
2014 if (fstat(newfd, &sb))
2019 if (p->fts_statp->st_dev != sb.st_dev
2020 || p->fts_statp->st_ino != sb.st_ino)
2022 __set_errno (ENOENT); /* disinformation */
2028 if (ISSET(FTS_CWDFD))
2030 cwd_advance_fd (sp, newfd, ! is_dotdot);
2034 ret = fchdir(newfd);
2040 __set_errno (oerrno);