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 possible (see max_entries, below), read no more than this many directory
138 entries at a time. Without this limit (i.e., when using non-NULL
139 fts_compar), processing a directory with 4,000,000 entries requires ~1GiB
140 of memory, and handling 64M entries would require 16GiB of memory. */
141 #ifndef FTS_MAX_READDIR_ENTRIES
142 # define FTS_MAX_READDIR_ENTRIES 100000
145 /* If there are more than this many entries in a directory,
146 and the conditions mentioned below are satisfied, then sort
147 the entries on inode number before any further processing. */
148 #ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
149 # define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000
154 _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD = FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
159 FTS_NO_STAT_REQUIRED = 1,
160 FTS_STAT_REQUIRED = 2
165 # define close __close
167 # define closedir __closedir
169 # define fchdir __fchdir
173 # define readdir __readdir
175 # undef internal_function
176 # define internal_function /* empty */
180 # define __set_errno(Val) errno = (Val)
183 /* If this host provides the openat function, then we can avoid
184 attempting to open "." in some initialization code below. */
186 # define HAVE_OPENAT_SUPPORT 1
188 # define HAVE_OPENAT_SUPPORT 0
192 # define fts_assert(expr) ((void) 0)
194 # define fts_assert(expr) \
203 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
204 static FTSENT *fts_build (FTS *, int) internal_function;
205 static void fts_lfree (FTSENT *) internal_function;
206 static void fts_load (FTS *, FTSENT *) internal_function;
207 static size_t fts_maxarglen (char * const *) internal_function;
208 static void fts_padjust (FTS *, FTSENT *) internal_function;
209 static bool fts_palloc (FTS *, size_t) internal_function;
210 static FTSENT *fts_sort (FTS *, FTSENT *, size_t) internal_function;
211 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
212 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
215 #include "fts-cycle.c"
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, int extra_flags, int *pdir_fd)
302 int new_fd = openat (fd, dir,
303 (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
309 set_cloexec_flag (new_fd, true);
310 dirp = fdopendir (new_fd);
315 int saved_errno = errno;
322 /* Virtual fchdir. Advance SP's working directory file descriptor,
323 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
324 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
325 open on sp->fts_cwd_fd; i.e., to move the working directory one level
329 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
331 int old = sp->fts_cwd_fd;
332 fts_assert (old != fd || old == AT_FDCWD);
336 /* Push "old" onto the ring.
337 If the displaced file descriptor is non-negative, close it. */
338 int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);
339 fd_ring_print (sp, stderr, "post-push");
340 if (0 <= prev_fd_in_slot)
341 close (prev_fd_in_slot); /* ignore any close failure */
343 else if ( ! ISSET (FTS_NOCHDIR))
346 close (old); /* ignore any close failure */
352 /* Open the directory DIR if possible, and return a file
353 descriptor. Return -1 and set errno on failure. It doesn't matter
354 whether the file descriptor has read or write access. */
358 diropen (FTS const *sp, char const *dir)
360 int open_flags = (O_SEARCH | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
361 | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0)
362 | (ISSET (FTS_NOATIME) ? O_NOATIME : 0));
364 int fd = (ISSET (FTS_CWDFD)
365 ? openat (sp->fts_cwd_fd, dir, open_flags)
366 : open (dir, open_flags));
368 set_cloexec_flag (fd, true);
373 fts_open (char * const *argv,
374 register int options,
375 int (*compar) (FTSENT const **, FTSENT const **))
378 register FTSENT *p, *root;
379 register size_t nitems;
380 FTSENT *parent = NULL;
381 FTSENT *tmp = NULL; /* pacify gcc */
385 if (options & ~FTS_OPTIONMASK) {
386 __set_errno (EINVAL);
389 if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {
390 __set_errno (EINVAL);
393 if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {
394 __set_errno (EINVAL);
398 /* Allocate/initialize the stream */
399 if ((sp = malloc(sizeof(FTS))) == NULL)
401 memset(sp, 0, sizeof(FTS));
402 sp->fts_compar = compar;
403 sp->fts_options = options;
405 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
406 if (ISSET(FTS_LOGICAL)) {
411 /* Initialize fts_cwd_fd. */
412 sp->fts_cwd_fd = AT_FDCWD;
413 if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)
415 /* While it isn't technically necessary to open "." this
416 early, doing it here saves us the trouble of ensuring
417 later (where it'd be messier) that "." can in fact
418 be opened. If not, revert to FTS_NOCHDIR mode. */
420 O_SEARCH | (ISSET (FTS_NOATIME) ? O_NOATIME : 0));
423 /* Even if `.' is unreadable, don't revert to FTS_NOCHDIR mode
424 on systems like Linux+PROC_FS, where our openat emulation
425 is good enough. Note: on a system that emulates
426 openat via /proc, this technique can still fail, but
427 only in extreme conditions, e.g., when the working
428 directory cannot be saved (i.e. save_cwd fails) --
429 and that happens on Linux only when "." is unreadable
430 and the CWD would be longer than PATH_MAX.
431 FIXME: once Linux kernel openat support is well established,
432 replace the above open call and this entire if/else block
433 with the body of the if-block below. */
434 if ( openat_needs_fchdir ())
447 * Start out with 1K of file name space, and enough, in any case,
448 * to hold the user's file names.
451 # define MAXPATHLEN 1024
454 size_t maxarglen = fts_maxarglen(argv);
455 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
459 /* Allocate/initialize root's parent. */
461 if ((parent = fts_alloc(sp, "", 0)) == NULL)
463 parent->fts_level = FTS_ROOTPARENTLEVEL;
466 /* The classic fts implementation would call fts_stat with
467 a new entry for each iteration of the loop below.
468 If the comparison function is not specified or if the
469 FTS_DEFER_STAT option is in effect, don't stat any entry
470 in this loop. This is an attempt to minimize the interval
471 between the initial stat/lstat/fstatat and the point at which
472 a directory argument is first opened. This matters for any
473 directory command line argument that resides on a file system
474 without genuine i-nodes. If you specify FTS_DEFER_STAT along
475 with a comparison function, that function must not access any
476 data via the fts_statp pointer. */
477 defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));
479 /* Allocate/initialize root(s). */
480 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
481 /* *Do* allow zero-length file names. */
482 size_t len = strlen(*argv);
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);
622 if (sp->fts_leaf_optimization_works_ht)
623 hash_free (sp->fts_leaf_optimization_works_ht);
627 /* Free up the stream pointer. */
630 /* Set errno and return. */
632 __set_errno (saved_errno);
639 #if defined __linux__ \
640 && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
642 # include <sys/vfs.h>
644 /* Linux-specific constants from coreutils' src/fs.h */
645 # define S_MAGIC_TMPFS 0x1021994
646 # define S_MAGIC_NFS 0x6969
647 # define S_MAGIC_REISERFS 0x52654973
648 # define S_MAGIC_PROC 0x9FA0
650 /* Return false if it is easy to determine the file system type of
651 the directory on which DIR_FD is open, and sorting dirents on
652 inode numbers is known not to improve traversal performance with
653 that type of file system. Otherwise, return true. */
655 dirent_inode_sort_may_be_useful (int dir_fd)
657 /* Skip the sort only if we can determine efficiently
658 that skipping it is the right thing to do.
659 The cost of performing an unnecessary sort is negligible,
660 while the cost of *not* performing it can be O(N^2) with
661 a very large constant. */
662 struct statfs fs_buf;
664 /* If fstatfs fails, assume sorting would be useful. */
665 if (fstatfs (dir_fd, &fs_buf) != 0)
668 /* FIXME: what about when f_type is not an integral type?
669 deal with that if/when it's encountered. */
670 switch (fs_buf.f_type)
674 /* On a file system of any of these types, sorting
675 is unnecessary, and hence wasteful. */
683 /* Given a file descriptor DIR_FD open on a directory D,
684 return true if it is valid to apply the leaf-optimization
685 technique of counting directories in D via stat.st_nlink. */
687 leaf_optimization_applies (int dir_fd)
689 struct statfs fs_buf;
691 /* If fstatfs fails, assume we can't use the optimization. */
692 if (fstatfs (dir_fd, &fs_buf) != 0)
695 /* FIXME: do we need to detect AFS mount points? I doubt it,
696 unless fstatfs can report S_MAGIC_REISERFS for such a directory. */
698 switch (fs_buf.f_type)
700 /* List here the file system types that lack useable dirent.d_type
701 info, yet for which the optimization does apply. */
702 case S_MAGIC_REISERFS:
706 /* Explicitly listing this or any other file system type for which
707 the optimization is not applicable is not necessary, but we leave
708 it here to document the risk. Per http://bugs.debian.org/143111,
709 /proc may have bogus stat.st_nlink values. */
718 dirent_inode_sort_may_be_useful (int dir_fd _GL_UNUSED) { return true; }
720 leaf_optimization_applies (int dir_fd _GL_UNUSED) { return false; }
723 /* link-count-optimization entry:
724 map a stat.st_dev number to a boolean: leaf_optimization_works */
731 /* Use a tiny initial size. If a traversal encounters more than
732 a few devices, the cost of growing/rehashing this table will be
733 rendered negligible by the number of inodes processed. */
734 enum { LCO_HT_INITIAL_SIZE = 13 };
737 LCO_hash (void const *x, size_t table_size)
739 struct LCO_ent const *ax = x;
740 return (uintmax_t) ax->st_dev % table_size;
744 LCO_compare (void const *x, void const *y)
746 struct LCO_ent const *ax = x;
747 struct LCO_ent const *ay = y;
748 return ax->st_dev == ay->st_dev;
751 /* Ask the same question as leaf_optimization_applies, but query
752 the cache first (FTS.fts_leaf_optimization_works_ht), and if necessary,
753 update that cache. */
755 link_count_optimize_ok (FTSENT const *p)
757 FTS *sp = p->fts_fts;
758 Hash_table *h = sp->fts_leaf_optimization_works_ht;
764 /* If we're not in CWDFD mode, don't bother with this optimization,
765 since the caller is not serious about performance. */
766 if (!ISSET(FTS_CWDFD))
769 /* map st_dev to the boolean, leaf_optimization_works */
772 h = sp->fts_leaf_optimization_works_ht
773 = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash,
778 tmp.st_dev = p->fts_statp->st_dev;
779 ent = hash_lookup (h, &tmp);
783 /* Look-up failed. Query directly and cache the result. */
784 t2 = malloc (sizeof *t2);
788 /* Is it ok to perform the optimization in the dir, FTS_CWD_FD? */
789 opt_ok = leaf_optimization_applies (sp->fts_cwd_fd);
791 t2->st_dev = p->fts_statp->st_dev;
793 ent = hash_insert (h, t2);
796 /* insertion failed */
800 fts_assert (ent == t2);
806 * Special case of "/" at the end of the file name so that slashes aren't
807 * appended which would cause file names to be written as "....//foo".
810 (p->fts_path[p->fts_pathlen - 1] == '/' \
811 ? p->fts_pathlen - 1 : p->fts_pathlen)
814 fts_read (register FTS *sp)
816 register FTSENT *p, *tmp;
817 register unsigned short int instr;
820 /* If finished or unrecoverable error, return NULL. */
821 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
824 /* Set current node pointer. */
827 /* Save and zero out user instructions. */
828 instr = p->fts_instr;
829 p->fts_instr = FTS_NOINSTR;
831 /* Any type of file may be re-visited; re-stat and re-turn. */
832 if (instr == FTS_AGAIN) {
833 p->fts_info = fts_stat(sp, p, false);
836 Dprintf (("fts_read: p=%s\n",
837 p->fts_info == FTS_INIT ? "" : p->fts_path));
840 * Following a symlink -- SLNONE test allows application to see
841 * SLNONE and recover. If indirecting through a symlink, have
842 * keep a pointer to current location. If unable to get that
843 * pointer, follow fails.
845 if (instr == FTS_FOLLOW &&
846 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
847 p->fts_info = fts_stat(sp, p, true);
848 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
849 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
850 p->fts_errno = errno;
851 p->fts_info = FTS_ERR;
853 p->fts_flags |= FTS_SYMFOLLOW;
858 /* Directory in pre-order. */
859 if (p->fts_info == FTS_D) {
860 /* If skipped or crossed mount point, do post-order visit. */
861 if (instr == FTS_SKIP ||
862 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
863 if (p->fts_flags & FTS_SYMFOLLOW)
864 (void)close(p->fts_symfd);
866 fts_lfree(sp->fts_child);
867 sp->fts_child = NULL;
869 p->fts_info = FTS_DP;
870 LEAVE_DIR (sp, p, "1");
874 /* Rebuild if only read the names and now traversing. */
875 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
877 fts_lfree(sp->fts_child);
878 sp->fts_child = NULL;
882 * Cd to the subdirectory.
884 * If have already read and now fail to chdir, whack the list
885 * to make the names come out right, and set the parent errno
886 * so the application will eventually get an error condition.
887 * Set the FTS_DONTCHDIR flag so that when we logically change
888 * directories back to the parent we don't do a chdir.
890 * If haven't read do so. If the read fails, fts_build sets
891 * FTS_STOP or the fts_info field of the node.
893 if (sp->fts_child != NULL) {
894 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
895 p->fts_errno = errno;
896 p->fts_flags |= FTS_DONTCHDIR;
897 for (p = sp->fts_child; p != NULL;
900 p->fts_parent->fts_accpath;
902 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
905 /* If fts_build's call to fts_safe_changedir failed
906 because it was not able to fchdir into a
907 subdirectory, tell the caller. */
908 if (p->fts_errno && p->fts_info != FTS_DNR)
909 p->fts_info = FTS_ERR;
910 LEAVE_DIR (sp, p, "2");
914 sp->fts_child = NULL;
918 /* Move to the next node on this level. */
921 /* If we have so many directory entries that we're reading them
922 in batches, and we've reached the end of the current batch,
923 read in a new batch. */
924 if (p->fts_link == NULL && p->fts_parent->fts_dirp)
928 sp->fts_path[p->fts_pathlen] = '\0';
930 if ((p = fts_build (sp, BREAD)) == NULL)
941 if ((p = p->fts_link) != NULL) {
946 * If reached the top, return to the original directory (or
947 * the root of the tree), and load the file names for the next
950 if (p->fts_level == FTS_ROOTLEVEL) {
951 if (RESTORE_INITIAL_CWD(sp)) {
962 * User may have called fts_set on the node. If skipped,
963 * ignore. If followed, get a file descriptor so we can
964 * get back if necessary.
966 if (p->fts_instr == FTS_SKIP)
968 if (p->fts_instr == FTS_FOLLOW) {
969 p->fts_info = fts_stat(sp, p, true);
970 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
971 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
972 p->fts_errno = errno;
973 p->fts_info = FTS_ERR;
975 p->fts_flags |= FTS_SYMFOLLOW;
977 p->fts_instr = FTS_NOINSTR;
980 name: t = sp->fts_path + NAPPEND(p->fts_parent);
982 memmove(t, p->fts_name, p->fts_namelen + 1);
985 if (p->fts_info == FTS_NSOK)
987 if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
989 FTSENT *parent = p->fts_parent;
990 if (FTS_ROOTLEVEL < p->fts_level
991 /* ->fts_n_dirs_remaining is not valid
992 for command-line-specified names. */
993 && parent->fts_n_dirs_remaining == 0
995 && ISSET(FTS_PHYSICAL)
996 && link_count_optimize_ok (parent))
998 /* nothing more needed */
1002 p->fts_info = fts_stat(sp, p, false);
1003 if (S_ISDIR(p->fts_statp->st_mode)
1004 && p->fts_level != FTS_ROOTLEVEL
1005 && parent->fts_n_dirs_remaining)
1006 parent->fts_n_dirs_remaining--;
1010 fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
1013 if (p->fts_info == FTS_D)
1015 /* Now that P->fts_statp is guaranteed to be valid,
1016 if this is a command-line directory, record its
1017 device number, to be used for FTS_XDEV. */
1018 if (p->fts_level == FTS_ROOTLEVEL)
1019 sp->fts_dev = p->fts_statp->st_dev;
1020 Dprintf ((" entering: %s\n", p->fts_path));
1021 if (! enter_dir (sp, p))
1023 __set_errno (ENOMEM);
1031 /* Move up to the parent node. */
1032 p = tmp->fts_parent;
1036 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
1038 * Done; free everything up and set errno to 0 so the user
1039 * can distinguish between error and EOF.
1043 return (sp->fts_cur = NULL);
1046 fts_assert (p->fts_info != FTS_NSOK);
1048 /* NUL terminate the file name. */
1049 sp->fts_path[p->fts_pathlen] = '\0';
1052 * Return to the parent directory. If at a root node, restore
1053 * the initial working directory. If we came through a symlink,
1054 * go back through the file descriptor. Otherwise, move up
1055 * one level, via "..".
1057 if (p->fts_level == FTS_ROOTLEVEL) {
1058 if (RESTORE_INITIAL_CWD(sp)) {
1059 p->fts_errno = errno;
1062 } else if (p->fts_flags & FTS_SYMFOLLOW) {
1063 if (FCHDIR(sp, p->fts_symfd)) {
1064 int saved_errno = errno;
1065 (void)close(p->fts_symfd);
1066 __set_errno (saved_errno);
1067 p->fts_errno = errno;
1070 (void)close(p->fts_symfd);
1071 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
1072 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
1073 p->fts_errno = errno;
1076 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
1077 if (p->fts_errno == 0)
1078 LEAVE_DIR (sp, p, "3");
1079 return ISSET(FTS_STOP) ? NULL : p;
1083 * Fts_set takes the stream as an argument although it's not used in this
1084 * implementation; it would be necessary if anyone wanted to add global
1085 * semantics to fts using fts_set. An error return is allowed for similar
1090 fts_set(FTS *sp _GL_UNUSED, FTSENT *p, int instr)
1092 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
1093 instr != FTS_NOINSTR && instr != FTS_SKIP) {
1094 __set_errno (EINVAL);
1097 p->fts_instr = instr;
1102 fts_children (register FTS *sp, int instr)
1107 if (instr != 0 && instr != FTS_NAMEONLY) {
1108 __set_errno (EINVAL);
1112 /* Set current node pointer. */
1116 * Errno set to 0 so user can distinguish empty directory from
1121 /* Fatal errors stop here. */
1122 if (ISSET(FTS_STOP))
1125 /* Return logical hierarchy of user's arguments. */
1126 if (p->fts_info == FTS_INIT)
1127 return (p->fts_link);
1130 * If not a directory being visited in pre-order, stop here. Could
1131 * allow FTS_DNR, assuming the user has fixed the problem, but the
1132 * same effect is available with FTS_AGAIN.
1134 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
1137 /* Free up any previous child list. */
1138 if (sp->fts_child != NULL)
1139 fts_lfree(sp->fts_child);
1141 if (instr == FTS_NAMEONLY) {
1148 * If using chdir on a relative file name and called BEFORE fts_read
1149 * does its chdir to the root of a traversal, we can lose -- we need to
1150 * chdir into the subdirectory, and we don't know where the current
1151 * directory is, so we can't get back so that the upcoming chdir by
1152 * fts_read will work.
1154 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
1156 return (sp->fts_child = fts_build(sp, instr));
1158 if ((fd = diropen (sp, ".")) < 0)
1159 return (sp->fts_child = NULL);
1160 sp->fts_child = fts_build(sp, instr);
1161 if (ISSET(FTS_CWDFD))
1163 cwd_advance_fd (sp, fd, true);
1169 int saved_errno = errno;
1171 __set_errno (saved_errno);
1176 return (sp->fts_child);
1179 /* A comparison function to sort on increasing inode number.
1180 For some file system types, sorting either way makes a huge
1181 performance difference for a directory with very many entries,
1182 but sorting on increasing values is slightly better than sorting
1183 on decreasing values. The difference is in the 5% range. */
1185 fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b)
1187 return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? -1
1188 : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? 1 : 0);
1191 /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode
1192 S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */
1194 set_stat_type (struct stat *st, unsigned int dtype)
1226 #define closedir_and_clear(dirp) \
1234 #define fts_opendir(file, Pdir_fd) \
1235 opendirat((! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
1236 ? sp->fts_cwd_fd : AT_FDCWD), \
1238 (((ISSET(FTS_PHYSICAL) \
1239 && ! (ISSET(FTS_COMFOLLOW) \
1240 && cur->fts_level == FTS_ROOTLEVEL)) \
1242 | (ISSET (FTS_NOATIME) ? O_NOATIME : 0)), \
1246 * This is the tricky part -- do not casually change *anything* in here. The
1247 * idea is to build the linked list of entries that are used by fts_children
1248 * and fts_read. There are lots of special cases.
1250 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
1251 * set and it's a physical walk (so that symbolic links can't be directories),
1252 * we can do things quickly. First, if it's a 4.4BSD file system, the type
1253 * of the file is in the directory entry. Otherwise, we assume that the number
1254 * of subdirectories in a node is equal to the number of links to the parent.
1255 * The former skips all stat calls. The latter skips stat calls in any leaf
1256 * directories and for any files after the subdirectories in the directory have
1257 * been found, cutting the stat calls by about 2/3.
1261 fts_build (register FTS *sp, int type)
1263 register FTSENT *p, *head;
1264 register size_t nitems;
1273 size_t len, maxlen, new_len;
1276 FTSENT *cur = sp->fts_cur;
1277 bool continue_readdir = !!cur->fts_dirp;
1279 /* When cur->fts_dirp is non-NULL, that means we should
1280 continue calling readdir on that existing DIR* pointer
1281 rather than opening a new one. */
1282 if (continue_readdir)
1284 DIR *dp = cur->fts_dirp;
1285 dir_fd = dirfd (dp);
1288 closedir_and_clear (cur->fts_dirp);
1291 cur->fts_info = FTS_DNR;
1292 cur->fts_errno = errno;
1299 /* Open the directory for reading. If this fails, we're done.
1300 If being called from fts_read, set the fts_info field. */
1301 if ((cur->fts_dirp = fts_opendir(cur->fts_accpath, &dir_fd)) == NULL)
1305 cur->fts_info = FTS_DNR;
1306 cur->fts_errno = errno;
1310 /* Rather than calling fts_stat for each and every entry encountered
1311 in the readdir loop (below), stat each directory only right after
1313 if (cur->fts_info == FTS_NSOK)
1314 cur->fts_info = fts_stat(sp, cur, false);
1315 else if (sp->fts_options & FTS_TIGHT_CYCLE_CHECK)
1317 /* Now read the stat info again after opening a directory to
1318 reveal eventual changes caused by a submount triggered by
1319 the traversal. But do it only for utilities which use
1320 FTS_TIGHT_CYCLE_CHECK. Therefore, only find and du
1321 benefit/suffer from this feature for now. */
1322 LEAVE_DIR (sp, cur, "4");
1323 fts_stat (sp, cur, false);
1324 if (! enter_dir (sp, cur))
1326 __set_errno (ENOMEM);
1332 /* Maximum number of readdir entries to read at one time. This
1333 limitation is to avoid reading millions of entries into memory
1334 at once. When an fts_compar function is specified, we have no
1335 choice: we must read all entries into memory before calling that
1336 function. But when no such function is specified, we can read
1337 entries in batches that are large enough to help us with inode-
1338 sorting, yet not so large that we risk exhausting memory. */
1339 size_t max_entries = (sp->fts_compar == NULL
1340 ? FTS_MAX_READDIR_ENTRIES : SIZE_MAX);
1343 * Nlinks is the number of possible entries of type directory in the
1344 * directory if we're cheating on stat calls, 0 if we're not doing
1345 * any stat calls at all, (nlink_t) -1 if we're statting everything.
1347 if (type == BNAMES) {
1349 /* Be quiet about nostat, GCC. */
1351 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
1352 nlinks = (cur->fts_statp->st_nlink
1353 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1361 * If we're going to need to stat anything or we want to descend
1362 * and stay in the directory, chdir. If this fails we keep going,
1363 * but set a flag so we don't chdir after the post-order visit.
1364 * We won't be able to stat anything, but we can still return the
1365 * names themselves. Note, that since fts_read won't be able to
1366 * chdir into the directory, it will have to return different file
1367 * names than before, i.e. "a/b" instead of "b". Since the node
1368 * has already been visited in pre-order, have to wait until the
1369 * post-order visit to return the error. There is a special case
1370 * here, if there was nothing to stat then it's not an error to
1371 * not be able to stat. This is all fairly nasty. If a program
1372 * needed sorted entries or stat information, they had better be
1373 * checking FTS_NS on the returned nodes.
1375 if (continue_readdir)
1377 /* When resuming a short readdir run, we already have
1378 the required dirp and dir_fd. */
1381 else if (nlinks || type == BREAD) {
1382 if (ISSET(FTS_CWDFD))
1384 dir_fd = dup (dir_fd);
1386 set_cloexec_flag (dir_fd, true);
1388 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
1389 if (nlinks && type == BREAD)
1390 cur->fts_errno = errno;
1391 cur->fts_flags |= FTS_DONTCHDIR;
1393 closedir_and_clear(cur->fts_dirp);
1394 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1396 cur->fts_dirp = NULL;
1403 * Figure out the max file name length that can be stored in the
1404 * current buffer -- the inner loop allocates more space as necessary.
1405 * We really wouldn't have to do the maxlen calculations here, we
1406 * could do them in fts_read before returning the name, but it's a
1407 * lot easier here since the length is part of the dirent structure.
1409 * If not changing directories set a pointer so that can just append
1410 * each new component into the file name.
1413 if (ISSET(FTS_NOCHDIR)) {
1414 cp = sp->fts_path + len;
1417 /* GCC, you're too verbose. */
1421 maxlen = sp->fts_pathlen - len;
1423 level = cur->fts_level + 1;
1425 /* Read the directory, attaching each entry to the `link' pointer. */
1430 while (cur->fts_dirp) {
1432 struct dirent *dp = readdir(cur->fts_dirp);
1435 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1438 if ((p = fts_alloc (sp, dp->d_name,
1439 _D_EXACT_NAMLEN (dp))) == NULL)
1441 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
1442 /* include space for NUL */
1443 oldaddr = sp->fts_path;
1444 if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
1446 * No more memory. Save
1447 * errno, free up the current structure and the
1448 * structures already allocated.
1450 mem1: saved_errno = errno;
1453 closedir_and_clear(cur->fts_dirp);
1454 cur->fts_info = FTS_ERR;
1456 __set_errno (saved_errno);
1459 /* Did realloc() change the pointer? */
1460 if (oldaddr != sp->fts_path) {
1462 if (ISSET(FTS_NOCHDIR))
1463 cp = sp->fts_path + len;
1465 maxlen = sp->fts_pathlen - len;
1468 new_len = len + _D_EXACT_NAMLEN (dp);
1469 if (new_len < len) {
1471 * In the unlikely event that we would end up
1472 * with a file name longer than SIZE_MAX, free up
1473 * the current structure and the structures already
1474 * allocated, then error out with ENAMETOOLONG.
1478 closedir_and_clear(cur->fts_dirp);
1479 cur->fts_info = FTS_ERR;
1481 __set_errno (ENAMETOOLONG);
1484 p->fts_level = level;
1485 p->fts_parent = sp->fts_cur;
1486 p->fts_pathlen = new_len;
1488 /* Store dirent.d_ino, in case we need to sort
1489 entries before processing them. */
1490 p->fts_statp->st_ino = D_INO (dp);
1492 /* Build a file name for fts_stat to stat. */
1493 if (ISSET(FTS_NOCHDIR)) {
1494 p->fts_accpath = p->fts_path;
1495 memmove(cp, p->fts_name, p->fts_namelen + 1);
1497 p->fts_accpath = p->fts_name;
1499 if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {
1500 /* Record what fts_read will have to do with this
1501 entry. In many cases, it will simply fts_stat it,
1502 but we can take advantage of any d_type information
1503 to optimize away the unnecessary stat calls. I.e.,
1504 if FTS_NOSTAT is in effect and we're not following
1505 symlinks (FTS_PHYSICAL) and d_type indicates this
1506 is *not* a directory, then we won't have to stat it
1507 at all. If it *is* a directory, then (currently)
1508 we stat it regardless, in order to get device and
1509 inode numbers. Some day we might optimize that
1510 away, too, for directories where d_ino is known to
1512 bool skip_stat = (ISSET(FTS_PHYSICAL)
1513 && ISSET(FTS_NOSTAT)
1515 && ! DT_MUST_BE(dp, DT_DIR));
1516 p->fts_info = FTS_NSOK;
1517 /* Propagate dirent.d_type information back
1518 to caller, when possible. */
1519 set_stat_type (p->fts_statp, D_TYPE (dp));
1520 fts_set_stat_required(p, !skip_stat);
1521 is_dir = (ISSET(FTS_PHYSICAL)
1522 && DT_MUST_BE(dp, DT_DIR));
1524 p->fts_info = fts_stat(sp, p, false);
1525 is_dir = (p->fts_info == FTS_D
1526 || p->fts_info == FTS_DC
1527 || p->fts_info == FTS_DOT);
1530 /* Decrement link count if applicable. */
1531 if (nlinks > 0 && is_dir)
1534 /* We walk in directory order so "ls -f" doesn't get upset. */
1543 if (max_entries <= nitems) {
1544 /* When there are too many dir entries, leave
1545 fts_dirp open, so that a subsequent fts_read
1546 can take up where we leave off. */
1547 goto break_without_closedir;
1552 closedir_and_clear(cur->fts_dirp);
1554 break_without_closedir:
1557 * If realloc() changed the address of the file name, adjust the
1558 * addresses for the rest of the tree and the dir list.
1561 fts_padjust(sp, head);
1564 * If not changing directories, reset the file name back to original
1567 if (ISSET(FTS_NOCHDIR)) {
1568 if (len == sp->fts_pathlen || nitems == 0)
1574 * If descended after called from fts_children or after called from
1575 * fts_read and nothing found, get back. At the root level we use
1576 * the saved fd; if one of fts_open()'s arguments is a relative name
1577 * to an empty directory, we wind up here with no other way back. If
1578 * can't get back, we're done.
1580 if (!continue_readdir && descend && (type == BCHILD || !nitems) &&
1581 (cur->fts_level == FTS_ROOTLEVEL
1582 ? RESTORE_INITIAL_CWD(sp)
1583 : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1584 cur->fts_info = FTS_ERR;
1590 /* If didn't find anything, return NULL. */
1593 cur->fts_info = FTS_DP;
1598 /* If there are many entries, no sorting function has been specified,
1599 and this file system is of a type that may be slow with a large
1600 number of entries, then sort the directory entries on increasing
1602 if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
1604 && ISSET (FTS_CWDFD)
1605 && dirent_inode_sort_may_be_useful (sp->fts_cwd_fd)) {
1606 sp->fts_compar = fts_compare_ino;
1607 head = fts_sort (sp, head, nitems);
1608 sp->fts_compar = NULL;
1611 /* Sort the entries. */
1612 if (sp->fts_compar && nitems > 1)
1613 head = fts_sort(sp, head, nitems);
1619 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1620 current hierarchy. There should be a directory with dev/inode
1621 matching those of AD. If not, print a lot of diagnostics. */
1623 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1626 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1628 if (ad->ino == ent->fts_statp->st_ino
1629 && ad->dev == ent->fts_statp->st_dev)
1632 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1633 printf ("active dirs:\n");
1635 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1636 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1637 ad->fts_ent->fts_accpath,
1638 (uintmax_t) ad->dev,
1639 (uintmax_t) ad->ino,
1641 (uintmax_t) ent->fts_statp->st_dev,
1642 (uintmax_t) ent->fts_statp->st_ino);
1646 fts_cross_check (FTS const *sp)
1648 FTSENT const *ent = sp->fts_cur;
1650 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1653 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1654 /* Make sure every parent dir is in the tree. */
1655 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1657 struct Active_dir ad;
1658 ad.ino = t->fts_statp->st_ino;
1659 ad.dev = t->fts_statp->st_dev;
1660 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1661 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1664 /* Make sure every dir in the tree is an active dir.
1665 But ENT is not necessarily a directory. If so, just skip this part. */
1666 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1667 && (ent->fts_info == FTS_DP
1668 || ent->fts_info == FTS_D))
1670 struct Active_dir *ad;
1671 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1672 ad = hash_get_next (sp->fts_cycle.ht, ad))
1674 find_matching_ancestor (ent, ad);
1680 same_fd (int fd1, int fd2)
1682 struct stat sb1, sb2;
1683 return (fstat (fd1, &sb1) == 0
1684 && fstat (fd2, &sb2) == 0
1685 && SAME_INODE (sb1, sb2));
1689 fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
1691 I_ring const *fd_ring = &sp->fts_fd_ring;
1692 unsigned int i = fd_ring->fts_front;
1693 char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0);
1694 fprintf (stream, "=== %s ========== %s\n", msg, cwd);
1696 if (i_ring_empty (fd_ring))
1701 int fd = fd_ring->fts_fd_ring[i];
1703 fprintf (stream, "%d: %d:\n", i, fd);
1706 char *wd = getcwdat (fd, NULL, 0);
1707 fprintf (stream, "%d: %d: %s\n", i, fd, wd);
1710 if (i == fd_ring->fts_back)
1712 i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
1716 /* Ensure that each file descriptor on the fd_ring matches a
1717 parent, grandparent, etc. of the current working directory. */
1719 fd_ring_check (FTS const *sp)
1724 /* Make a writable copy. */
1725 I_ring fd_w = sp->fts_fd_ring;
1727 int cwd_fd = sp->fts_cwd_fd;
1728 cwd_fd = dup (cwd_fd);
1729 char *dot = getcwdat (cwd_fd, NULL, 0);
1730 error (0, 0, "===== check ===== cwd: %s", dot);
1732 while ( ! i_ring_empty (&fd_w))
1734 int fd = i_ring_pop (&fd_w);
1737 int parent_fd = openat (cwd_fd, "..", O_SEARCH | O_NOATIME);
1743 if (!same_fd (fd, parent_fd))
1745 char *cwd = getcwdat (fd, NULL, 0);
1746 error (0, errno, "ring : %s", cwd);
1747 char *c2 = getcwdat (parent_fd, NULL, 0);
1748 error (0, errno, "parent: %s", c2);
1761 static unsigned short int
1763 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1765 struct stat *sbp = p->fts_statp;
1768 if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
1772 * If doing a logical walk, or application requested FTS_FOLLOW, do
1773 * a stat(2). If that fails, check for a non-existent symlink. If
1774 * fail, set the errno from the stat call.
1776 if (ISSET(FTS_LOGICAL) || follow) {
1777 if (stat(p->fts_accpath, sbp)) {
1778 saved_errno = errno;
1780 && lstat(p->fts_accpath, sbp) == 0) {
1782 return (FTS_SLNONE);
1784 p->fts_errno = saved_errno;
1787 } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp,
1788 AT_SYMLINK_NOFOLLOW)) {
1789 p->fts_errno = errno;
1790 err: memset(sbp, 0, sizeof(struct stat));
1794 if (S_ISDIR(sbp->st_mode)) {
1795 p->fts_n_dirs_remaining = (sbp->st_nlink
1796 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1797 if (ISDOT(p->fts_name)) {
1798 /* Command-line "." and ".." are real directories. */
1799 return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
1804 if (S_ISLNK(sbp->st_mode))
1806 if (S_ISREG(sbp->st_mode))
1808 return (FTS_DEFAULT);
1812 fts_compar (void const *a, void const *b)
1814 /* Convert A and B to the correct types, to pacify the compiler, and
1815 for portability to bizarre hosts where "void const *" and "FTSENT
1816 const **" differ in runtime representation. The comparison
1817 function cannot modify *a and *b, but there is no compile-time
1819 FTSENT const **pa = (FTSENT const **) a;
1820 FTSENT const **pb = (FTSENT const **) b;
1821 return pa[0]->fts_fts->fts_compar (pa, pb);
1826 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1828 register FTSENT **ap, *p;
1830 /* On most modern hosts, void * and FTSENT ** have the same
1831 run-time representation, and one can convert sp->fts_compar to
1832 the type qsort expects without problem. Use the heuristic that
1833 this is OK if the two pointer types are the same size, and if
1834 converting FTSENT ** to long int is the same as converting
1835 FTSENT ** to void * and then to long int. This heuristic isn't
1836 valid in general but we don't know of any counterexamples. */
1838 int (*compare) (void const *, void const *) =
1839 ((sizeof &dummy == sizeof (void *)
1840 && (long int) &dummy == (long int) (void *) &dummy)
1841 ? (int (*) (void const *, void const *)) sp->fts_compar
1845 * Construct an array of pointers to the structures and call qsort(3).
1846 * Reassemble the array in the order returned by qsort. If unable to
1847 * sort for memory reasons, return the directory entries in their
1848 * current order. Allocate enough space for the current needs plus
1849 * 40 so don't realloc one entry at a time.
1851 if (nitems > sp->fts_nitems) {
1854 sp->fts_nitems = nitems + 40;
1855 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1856 || ! (a = realloc (sp->fts_array,
1857 sp->fts_nitems * sizeof *a))) {
1858 free(sp->fts_array);
1859 sp->fts_array = NULL;
1865 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1867 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1868 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1869 ap[0]->fts_link = ap[1];
1870 ap[0]->fts_link = NULL;
1876 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1882 * The file name is a variable length array. Allocate the FTSENT
1883 * structure and the file name in one chunk.
1885 len = sizeof(FTSENT) + namelen;
1886 if ((p = malloc(len)) == NULL)
1889 /* Copy the name and guarantee NUL termination. */
1890 memmove(p->fts_name, name, namelen);
1891 p->fts_name[namelen] = '\0';
1893 p->fts_namelen = namelen;
1895 p->fts_path = sp->fts_path;
1899 p->fts_instr = FTS_NOINSTR;
1901 p->fts_pointer = NULL;
1907 fts_lfree (register FTSENT *head)
1911 /* Free a linked list of structures. */
1912 while ((p = head)) {
1913 head = head->fts_link;
1915 closedir (p->fts_dirp);
1921 * Allow essentially unlimited file name lengths; find, rm, ls should
1922 * all work on any tree. Most systems will allow creation of file
1923 * names much longer than MAXPATHLEN, even though the kernel won't
1924 * resolve them. Add the size (not just what's needed) plus 256 bytes
1925 * so don't realloc the file name 2 bytes at a time.
1929 fts_palloc (FTS *sp, size_t more)
1932 size_t new_len = sp->fts_pathlen + more + 256;
1935 * See if fts_pathlen would overflow.
1937 if (new_len < sp->fts_pathlen) {
1939 sp->fts_path = NULL;
1940 __set_errno (ENAMETOOLONG);
1943 sp->fts_pathlen = new_len;
1944 p = realloc(sp->fts_path, sp->fts_pathlen);
1947 sp->fts_path = NULL;
1955 * When the file name is realloc'd, have to fix all of the pointers in
1956 * structures already returned.
1960 fts_padjust (FTS *sp, FTSENT *head)
1963 char *addr = sp->fts_path;
1965 #define ADJUST(p) do { \
1966 if ((p)->fts_accpath != (p)->fts_name) { \
1967 (p)->fts_accpath = \
1968 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1970 (p)->fts_path = addr; \
1972 /* Adjust the current set of children. */
1973 for (p = sp->fts_child; p; p = p->fts_link)
1976 /* Adjust the rest of the tree, including the current level. */
1977 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1979 p = p->fts_link ? p->fts_link : p->fts_parent;
1985 fts_maxarglen (char * const *argv)
1989 for (max = 0; *argv; ++argv)
1990 if ((len = strlen(*argv)) > max)
1996 * Change to dir specified by fd or file name without getting
1997 * tricked by someone changing the world out from underneath us.
1998 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1999 * If FD is non-negative, expect it to be used after this function returns,
2000 * and to be closed eventually. So don't pass e.g., `dirfd(dirp)' and then
2001 * do closedir(dirp), because that would invalidate the saved FD.
2002 * Upon failure, close FD immediately and return nonzero.
2006 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
2009 bool is_dotdot = dir && STREQ (dir, "..");
2012 /* This clause handles the unusual case in which FTS_NOCHDIR
2013 is specified, along with FTS_CWDFD. In that case, there is
2014 no need to change even the virtual cwd file descriptor.
2015 However, if FD is non-negative, we do close it here. */
2016 if (ISSET (FTS_NOCHDIR))
2018 if (ISSET (FTS_CWDFD) && 0 <= fd)
2023 if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
2025 /* When possible, skip the diropen and subsequent fstat+dev/ino
2026 comparison. I.e., when changing to parent directory
2027 (chdir ("..")), use a file descriptor from the ring and
2028 save the overhead of diropen+fstat, as well as avoiding
2029 failure when we lack "x" access to the virtual cwd. */
2030 if ( ! i_ring_empty (&sp->fts_fd_ring))
2033 fd_ring_print (sp, stderr, "pre-pop");
2034 parent_fd = i_ring_pop (&sp->fts_fd_ring);
2045 if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
2048 /* The following dev/inode check is necessary if we're doing a
2049 `logical' traversal (through symlinks, a la chown -L), if the
2050 system lacks O_NOFOLLOW support, or if we're changing to ".."
2051 (but not via a popped file descriptor). When changing to the
2052 name "..", O_NOFOLLOW can't help. In general, when the target is
2053 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
2054 follow a symlink, so we can avoid the expense of this fstat. */
2055 if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
2056 || (dir && STREQ (dir, "..")))
2059 if (fstat(newfd, &sb))
2064 if (p->fts_statp->st_dev != sb.st_dev
2065 || p->fts_statp->st_ino != sb.st_ino)
2067 __set_errno (ENOENT); /* disinformation */
2073 if (ISSET(FTS_CWDFD))
2075 cwd_advance_fd (sp, newfd, ! is_dotdot);
2079 ret = fchdir(newfd);
2085 __set_errno (oerrno);