1 /* Traverse a file hierarchy.
3 Copyright (C) 2004-2012 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: FTS_NOCHDIR is now misnamed.
233 Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
234 #define FCHDIR(sp, fd) \
235 (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \
236 ? (cwd_advance_fd ((sp), (fd), true), 0) \
240 /* fts_build flags */
241 /* FIXME: make this an enum */
242 #define BCHILD 1 /* fts_children */
243 #define BNAMES 2 /* fts_children, names only */
244 #define BREAD 3 /* fts_read */
247 # include <inttypes.h>
250 # include "getcwdat.h"
251 bool fts_debug = false;
252 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
255 # define fd_ring_check(x)
256 # define fd_ring_print(a, b, c)
259 #define LEAVE_DIR(Fts, Ent, Tag) \
262 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
263 leave_dir (Fts, Ent); \
264 fd_ring_check (Fts); \
269 fd_ring_clear (I_ring *fd_ring)
271 while ( ! i_ring_empty (fd_ring))
273 int fd = i_ring_pop (fd_ring);
279 /* Overload the fts_statp->st_size member (otherwise unused, when
280 fts_info is FTS_NSOK) to indicate whether fts_read should stat
281 this entry or not. */
283 fts_set_stat_required (FTSENT *p, bool required)
285 fts_assert (p->fts_info == FTS_NSOK);
286 p->fts_statp->st_size = (required
288 : FTS_NO_STAT_REQUIRED);
291 /* file-descriptor-relative opendir. */
292 /* FIXME: if others need this function, move it into lib/openat.c */
295 opendirat (int fd, char const *dir, int extra_flags, int *pdir_fd)
297 int new_fd = openat (fd, dir,
298 (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
304 set_cloexec_flag (new_fd, true);
305 dirp = fdopendir (new_fd);
310 int saved_errno = errno;
317 /* Virtual fchdir. Advance SP's working directory file descriptor,
318 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
319 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
320 open on sp->fts_cwd_fd; i.e., to move the working directory one level
324 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
326 int old = sp->fts_cwd_fd;
327 fts_assert (old != fd || old == AT_FDCWD);
331 /* Push "old" onto the ring.
332 If the displaced file descriptor is non-negative, close it. */
333 int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);
334 fd_ring_print (sp, stderr, "post-push");
335 if (0 <= prev_fd_in_slot)
336 close (prev_fd_in_slot); /* ignore any close failure */
338 else if ( ! ISSET (FTS_NOCHDIR))
341 close (old); /* ignore any close failure */
347 /* Restore the initial, pre-traversal, "working directory".
348 In FTS_CWDFD mode, we merely call cwd_advance_fd, otherwise,
349 we may actually change the working directory.
350 Return 0 upon success. Upon failure, set errno and return nonzero. */
352 restore_initial_cwd (FTS *sp)
354 int fail = FCHDIR (sp, ISSET (FTS_CWDFD) ? AT_FDCWD : sp->fts_rfd);
355 fd_ring_clear (&(sp->fts_fd_ring));
359 /* Open the directory DIR if possible, and return a file
360 descriptor. Return -1 and set errno on failure. It doesn't matter
361 whether the file descriptor has read or write access. */
365 diropen (FTS const *sp, char const *dir)
367 int open_flags = (O_SEARCH | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
368 | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0)
369 | (ISSET (FTS_NOATIME) ? O_NOATIME : 0));
371 int fd = (ISSET (FTS_CWDFD)
372 ? openat (sp->fts_cwd_fd, dir, open_flags)
373 : open (dir, open_flags));
375 set_cloexec_flag (fd, true);
380 fts_open (char * const *argv,
381 register int options,
382 int (*compar) (FTSENT const **, FTSENT const **))
385 register FTSENT *p, *root;
386 register size_t nitems;
387 FTSENT *parent = NULL;
388 FTSENT *tmp = NULL; /* pacify gcc */
392 if (options & ~FTS_OPTIONMASK) {
393 __set_errno (EINVAL);
396 if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {
397 __set_errno (EINVAL);
400 if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {
401 __set_errno (EINVAL);
405 /* Allocate/initialize the stream */
406 if ((sp = malloc(sizeof(FTS))) == NULL)
408 memset(sp, 0, sizeof(FTS));
409 sp->fts_compar = compar;
410 sp->fts_options = options;
412 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
413 if (ISSET(FTS_LOGICAL)) {
418 /* Initialize fts_cwd_fd. */
419 sp->fts_cwd_fd = AT_FDCWD;
420 if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)
422 /* While it isn't technically necessary to open "." this
423 early, doing it here saves us the trouble of ensuring
424 later (where it'd be messier) that "." can in fact
425 be opened. If not, revert to FTS_NOCHDIR mode. */
427 O_SEARCH | (ISSET (FTS_NOATIME) ? O_NOATIME : 0));
430 /* Even if "." is unreadable, don't revert to FTS_NOCHDIR mode
431 on systems like Linux+PROC_FS, where our openat emulation
432 is good enough. Note: on a system that emulates
433 openat via /proc, this technique can still fail, but
434 only in extreme conditions, e.g., when the working
435 directory cannot be saved (i.e. save_cwd fails) --
436 and that happens on Linux only when "." is unreadable
437 and the CWD would be longer than PATH_MAX.
438 FIXME: once Linux kernel openat support is well established,
439 replace the above open call and this entire if/else block
440 with the body of the if-block below. */
441 if ( openat_needs_fchdir ())
454 * Start out with 1K of file name space, and enough, in any case,
455 * to hold the user's file names.
458 # define MAXPATHLEN 1024
461 size_t maxarglen = fts_maxarglen(argv);
462 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
466 /* Allocate/initialize root's parent. */
468 if ((parent = fts_alloc(sp, "", 0)) == NULL)
470 parent->fts_level = FTS_ROOTPARENTLEVEL;
473 /* The classic fts implementation would call fts_stat with
474 a new entry for each iteration of the loop below.
475 If the comparison function is not specified or if the
476 FTS_DEFER_STAT option is in effect, don't stat any entry
477 in this loop. This is an attempt to minimize the interval
478 between the initial stat/lstat/fstatat and the point at which
479 a directory argument is first opened. This matters for any
480 directory command line argument that resides on a file system
481 without genuine i-nodes. If you specify FTS_DEFER_STAT along
482 with a comparison function, that function must not access any
483 data via the fts_statp pointer. */
484 defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));
486 /* Allocate/initialize root(s). */
487 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
488 /* *Do* allow zero-length file names. */
489 size_t len = strlen(*argv);
491 /* If there are two or more trailing slashes, trim all but one,
492 but don't change "//" to "/", and do map "///" to "/". */
493 char const *v = *argv;
494 if (2 < len && v[len - 1] == '/')
495 while (1 < len && v[len - 2] == '/')
498 if ((p = fts_alloc(sp, *argv, len)) == NULL)
500 p->fts_level = FTS_ROOTLEVEL;
501 p->fts_parent = parent;
502 p->fts_accpath = p->fts_name;
503 /* Even when defer_stat is true, be sure to stat the first
504 command line argument, since fts_read (at least with
505 FTS_XDEV) requires that. */
506 if (defer_stat && root != NULL) {
507 p->fts_info = FTS_NSOK;
508 fts_set_stat_required(p, true);
510 p->fts_info = fts_stat(sp, p, false);
514 * If comparison routine supplied, traverse in sorted
515 * order; otherwise traverse in the order specified.
530 if (compar && nitems > 1)
531 root = fts_sort(sp, root, nitems);
534 * Allocate a dummy pointer and make fts_read think that we've just
535 * finished the node before the root(s); set p->fts_info to FTS_INIT
536 * so that everything about the "current" node is ignored.
538 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
540 sp->fts_cur->fts_link = root;
541 sp->fts_cur->fts_info = FTS_INIT;
542 if (! setup_dir (sp))
546 * If using chdir(2), grab a file descriptor pointing to dot to ensure
547 * that we can get back here; this could be avoided for some file names,
548 * but almost certainly not worth the effort. Slashes, symbolic links,
549 * and ".." are all fairly nasty problems. Note, if we can't get the
550 * descriptor we run anyway, just more slowly.
552 if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)
553 && (sp->fts_rfd = diropen (sp, ".")) < 0)
556 i_ring_init (&sp->fts_fd_ring, -1);
559 mem3: fts_lfree(root);
561 mem2: free(sp->fts_path);
568 fts_load (FTS *sp, register FTSENT *p)
574 * Load the stream structure for the next traversal. Since we don't
575 * actually enter the directory until after the preorder visit, set
576 * the fts_accpath field specially so the chdir gets done to the right
577 * place and the user can access the first node. From fts_open it's
578 * known that the file name will fit.
580 len = p->fts_pathlen = p->fts_namelen;
581 memmove(sp->fts_path, p->fts_name, len + 1);
582 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
584 memmove(p->fts_name, cp, len + 1);
585 p->fts_namelen = len;
587 p->fts_accpath = p->fts_path = sp->fts_path;
593 register FTSENT *freep, *p;
597 * This still works if we haven't read anything -- the dummy structure
598 * points to the root list, so we step through to the end of the root
599 * list which has a valid parent pointer.
602 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
604 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
610 /* Free up child linked list, sort array, file name buffer. */
612 fts_lfree(sp->fts_child);
616 if (ISSET(FTS_CWDFD))
618 if (0 <= sp->fts_cwd_fd)
619 if (close (sp->fts_cwd_fd))
622 else if (!ISSET(FTS_NOCHDIR))
624 /* Return to original directory, save errno if necessary. */
625 if (fchdir(sp->fts_rfd))
628 /* If close fails, record errno only if saved_errno is zero,
629 so that we report the probably-more-meaningful fchdir errno. */
630 if (close (sp->fts_rfd))
631 if (saved_errno == 0)
635 fd_ring_clear (&sp->fts_fd_ring);
637 if (sp->fts_leaf_optimization_works_ht)
638 hash_free (sp->fts_leaf_optimization_works_ht);
642 /* Free up the stream pointer. */
645 /* Set errno and return. */
647 __set_errno (saved_errno);
654 #if defined __linux__ \
655 && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
657 # include <sys/vfs.h>
659 /* Linux-specific constants from coreutils' src/fs.h */
660 # define S_MAGIC_TMPFS 0x1021994
661 # define S_MAGIC_NFS 0x6969
662 # define S_MAGIC_REISERFS 0x52654973
663 # define S_MAGIC_PROC 0x9FA0
665 /* Return false if it is easy to determine the file system type of
666 the directory on which DIR_FD is open, and sorting dirents on
667 inode numbers is known not to improve traversal performance with
668 that type of file system. Otherwise, return true. */
670 dirent_inode_sort_may_be_useful (int dir_fd)
672 /* Skip the sort only if we can determine efficiently
673 that skipping it is the right thing to do.
674 The cost of performing an unnecessary sort is negligible,
675 while the cost of *not* performing it can be O(N^2) with
676 a very large constant. */
677 struct statfs fs_buf;
679 /* If fstatfs fails, assume sorting would be useful. */
680 if (fstatfs (dir_fd, &fs_buf) != 0)
683 /* FIXME: what about when f_type is not an integral type?
684 deal with that if/when it's encountered. */
685 switch (fs_buf.f_type)
689 /* On a file system of any of these types, sorting
690 is unnecessary, and hence wasteful. */
698 /* Given a file descriptor DIR_FD open on a directory D,
699 return true if it is valid to apply the leaf-optimization
700 technique of counting directories in D via stat.st_nlink. */
702 leaf_optimization_applies (int dir_fd)
704 struct statfs fs_buf;
706 /* If fstatfs fails, assume we can't use the optimization. */
707 if (fstatfs (dir_fd, &fs_buf) != 0)
710 /* FIXME: do we need to detect AFS mount points? I doubt it,
711 unless fstatfs can report S_MAGIC_REISERFS for such a directory. */
713 switch (fs_buf.f_type)
715 /* List here the file system types that lack usable dirent.d_type
716 info, yet for which the optimization does apply. */
717 case S_MAGIC_REISERFS:
721 /* Explicitly listing this or any other file system type for which
722 the optimization is not applicable is not necessary, but we leave
723 it here to document the risk. Per http://bugs.debian.org/143111,
724 /proc may have bogus stat.st_nlink values. */
733 dirent_inode_sort_may_be_useful (int dir_fd _GL_UNUSED) { return true; }
735 leaf_optimization_applies (int dir_fd _GL_UNUSED) { return false; }
738 /* link-count-optimization entry:
739 map a stat.st_dev number to a boolean: leaf_optimization_works */
746 /* Use a tiny initial size. If a traversal encounters more than
747 a few devices, the cost of growing/rehashing this table will be
748 rendered negligible by the number of inodes processed. */
749 enum { LCO_HT_INITIAL_SIZE = 13 };
752 LCO_hash (void const *x, size_t table_size)
754 struct LCO_ent const *ax = x;
755 return (uintmax_t) ax->st_dev % table_size;
759 LCO_compare (void const *x, void const *y)
761 struct LCO_ent const *ax = x;
762 struct LCO_ent const *ay = y;
763 return ax->st_dev == ay->st_dev;
766 /* Ask the same question as leaf_optimization_applies, but query
767 the cache first (FTS.fts_leaf_optimization_works_ht), and if necessary,
768 update that cache. */
770 link_count_optimize_ok (FTSENT const *p)
772 FTS *sp = p->fts_fts;
773 Hash_table *h = sp->fts_leaf_optimization_works_ht;
779 /* If we're not in CWDFD mode, don't bother with this optimization,
780 since the caller is not serious about performance. */
781 if (!ISSET(FTS_CWDFD))
784 /* map st_dev to the boolean, leaf_optimization_works */
787 h = sp->fts_leaf_optimization_works_ht
788 = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash,
793 tmp.st_dev = p->fts_statp->st_dev;
794 ent = hash_lookup (h, &tmp);
798 /* Look-up failed. Query directly and cache the result. */
799 t2 = malloc (sizeof *t2);
803 /* Is it ok to perform the optimization in the dir, FTS_CWD_FD? */
804 opt_ok = leaf_optimization_applies (sp->fts_cwd_fd);
806 t2->st_dev = p->fts_statp->st_dev;
808 ent = hash_insert (h, t2);
811 /* insertion failed */
815 fts_assert (ent == t2);
821 * Special case of "/" at the end of the file name so that slashes aren't
822 * appended which would cause file names to be written as "....//foo".
825 (p->fts_path[p->fts_pathlen - 1] == '/' \
826 ? p->fts_pathlen - 1 : p->fts_pathlen)
829 fts_read (register FTS *sp)
831 register FTSENT *p, *tmp;
832 register unsigned short int instr;
835 /* If finished or unrecoverable error, return NULL. */
836 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
839 /* Set current node pointer. */
842 /* Save and zero out user instructions. */
843 instr = p->fts_instr;
844 p->fts_instr = FTS_NOINSTR;
846 /* Any type of file may be re-visited; re-stat and re-turn. */
847 if (instr == FTS_AGAIN) {
848 p->fts_info = fts_stat(sp, p, false);
851 Dprintf (("fts_read: p=%s\n",
852 p->fts_info == FTS_INIT ? "" : p->fts_path));
855 * Following a symlink -- SLNONE test allows application to see
856 * SLNONE and recover. If indirecting through a symlink, have
857 * keep a pointer to current location. If unable to get that
858 * pointer, follow fails.
860 if (instr == FTS_FOLLOW &&
861 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
862 p->fts_info = fts_stat(sp, p, true);
863 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
864 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
865 p->fts_errno = errno;
866 p->fts_info = FTS_ERR;
868 p->fts_flags |= FTS_SYMFOLLOW;
873 /* Directory in pre-order. */
874 if (p->fts_info == FTS_D) {
875 /* If skipped or crossed mount point, do post-order visit. */
876 if (instr == FTS_SKIP ||
877 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
878 if (p->fts_flags & FTS_SYMFOLLOW)
879 (void)close(p->fts_symfd);
881 fts_lfree(sp->fts_child);
882 sp->fts_child = NULL;
884 p->fts_info = FTS_DP;
885 LEAVE_DIR (sp, p, "1");
889 /* Rebuild if only read the names and now traversing. */
890 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
892 fts_lfree(sp->fts_child);
893 sp->fts_child = NULL;
897 * Cd to the subdirectory.
899 * If have already read and now fail to chdir, whack the list
900 * to make the names come out right, and set the parent errno
901 * so the application will eventually get an error condition.
902 * Set the FTS_DONTCHDIR flag so that when we logically change
903 * directories back to the parent we don't do a chdir.
905 * If haven't read do so. If the read fails, fts_build sets
906 * FTS_STOP or the fts_info field of the node.
908 if (sp->fts_child != NULL) {
909 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
910 p->fts_errno = errno;
911 p->fts_flags |= FTS_DONTCHDIR;
912 for (p = sp->fts_child; p != NULL;
915 p->fts_parent->fts_accpath;
917 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
920 /* If fts_build's call to fts_safe_changedir failed
921 because it was not able to fchdir into a
922 subdirectory, tell the caller. */
923 if (p->fts_errno && p->fts_info != FTS_DNR)
924 p->fts_info = FTS_ERR;
925 LEAVE_DIR (sp, p, "2");
929 sp->fts_child = NULL;
933 /* Move to the next node on this level. */
936 /* If we have so many directory entries that we're reading them
937 in batches, and we've reached the end of the current batch,
938 read in a new batch. */
939 if (p->fts_link == NULL && p->fts_parent->fts_dirp)
943 sp->fts_path[p->fts_pathlen] = '\0';
945 if ((p = fts_build (sp, BREAD)) == NULL)
956 if ((p = p->fts_link) != NULL) {
961 * If reached the top, return to the original directory (or
962 * the root of the tree), and load the file names for the next
965 if (p->fts_level == FTS_ROOTLEVEL) {
966 if (restore_initial_cwd(sp)) {
977 * User may have called fts_set on the node. If skipped,
978 * ignore. If followed, get a file descriptor so we can
979 * get back if necessary.
981 if (p->fts_instr == FTS_SKIP)
983 if (p->fts_instr == FTS_FOLLOW) {
984 p->fts_info = fts_stat(sp, p, true);
985 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
986 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
987 p->fts_errno = errno;
988 p->fts_info = FTS_ERR;
990 p->fts_flags |= FTS_SYMFOLLOW;
992 p->fts_instr = FTS_NOINSTR;
995 name: t = sp->fts_path + NAPPEND(p->fts_parent);
997 memmove(t, p->fts_name, p->fts_namelen + 1);
1000 if (p->fts_info == FTS_NSOK)
1002 if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
1004 FTSENT *parent = p->fts_parent;
1005 if (FTS_ROOTLEVEL < p->fts_level
1006 /* ->fts_n_dirs_remaining is not valid
1007 for command-line-specified names. */
1008 && parent->fts_n_dirs_remaining == 0
1009 && ISSET(FTS_NOSTAT)
1010 && ISSET(FTS_PHYSICAL)
1011 && link_count_optimize_ok (parent))
1013 /* nothing more needed */
1017 p->fts_info = fts_stat(sp, p, false);
1018 if (S_ISDIR(p->fts_statp->st_mode)
1019 && p->fts_level != FTS_ROOTLEVEL
1020 && parent->fts_n_dirs_remaining)
1021 parent->fts_n_dirs_remaining--;
1025 fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
1028 if (p->fts_info == FTS_D)
1030 /* Now that P->fts_statp is guaranteed to be valid,
1031 if this is a command-line directory, record its
1032 device number, to be used for FTS_XDEV. */
1033 if (p->fts_level == FTS_ROOTLEVEL)
1034 sp->fts_dev = p->fts_statp->st_dev;
1035 Dprintf ((" entering: %s\n", p->fts_path));
1036 if (! enter_dir (sp, p))
1038 __set_errno (ENOMEM);
1046 /* Move up to the parent node. */
1047 p = tmp->fts_parent;
1051 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
1053 * Done; free everything up and set errno to 0 so the user
1054 * can distinguish between error and EOF.
1058 return (sp->fts_cur = NULL);
1061 fts_assert (p->fts_info != FTS_NSOK);
1063 /* NUL terminate the file name. */
1064 sp->fts_path[p->fts_pathlen] = '\0';
1067 * Return to the parent directory. If at a root node, restore
1068 * the initial working directory. If we came through a symlink,
1069 * go back through the file descriptor. Otherwise, move up
1070 * one level, via "..".
1072 if (p->fts_level == FTS_ROOTLEVEL) {
1073 if (restore_initial_cwd(sp)) {
1074 p->fts_errno = errno;
1077 } else if (p->fts_flags & FTS_SYMFOLLOW) {
1078 if (FCHDIR(sp, p->fts_symfd)) {
1079 int saved_errno = errno;
1080 (void)close(p->fts_symfd);
1081 __set_errno (saved_errno);
1082 p->fts_errno = errno;
1085 (void)close(p->fts_symfd);
1086 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
1087 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
1088 p->fts_errno = errno;
1091 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
1092 if (p->fts_errno == 0)
1093 LEAVE_DIR (sp, p, "3");
1094 return ISSET(FTS_STOP) ? NULL : p;
1098 * Fts_set takes the stream as an argument although it's not used in this
1099 * implementation; it would be necessary if anyone wanted to add global
1100 * semantics to fts using fts_set. An error return is allowed for similar
1105 fts_set(FTS *sp _GL_UNUSED, FTSENT *p, int instr)
1107 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
1108 instr != FTS_NOINSTR && instr != FTS_SKIP) {
1109 __set_errno (EINVAL);
1112 p->fts_instr = instr;
1117 fts_children (register FTS *sp, int instr)
1122 if (instr != 0 && instr != FTS_NAMEONLY) {
1123 __set_errno (EINVAL);
1127 /* Set current node pointer. */
1131 * Errno set to 0 so user can distinguish empty directory from
1136 /* Fatal errors stop here. */
1137 if (ISSET(FTS_STOP))
1140 /* Return logical hierarchy of user's arguments. */
1141 if (p->fts_info == FTS_INIT)
1142 return (p->fts_link);
1145 * If not a directory being visited in pre-order, stop here. Could
1146 * allow FTS_DNR, assuming the user has fixed the problem, but the
1147 * same effect is available with FTS_AGAIN.
1149 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
1152 /* Free up any previous child list. */
1153 if (sp->fts_child != NULL)
1154 fts_lfree(sp->fts_child);
1156 if (instr == FTS_NAMEONLY) {
1163 * If using chdir on a relative file name and called BEFORE fts_read
1164 * does its chdir to the root of a traversal, we can lose -- we need to
1165 * chdir into the subdirectory, and we don't know where the current
1166 * directory is, so we can't get back so that the upcoming chdir by
1167 * fts_read will work.
1169 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
1171 return (sp->fts_child = fts_build(sp, instr));
1173 if ((fd = diropen (sp, ".")) < 0)
1174 return (sp->fts_child = NULL);
1175 sp->fts_child = fts_build(sp, instr);
1176 if (ISSET(FTS_CWDFD))
1178 cwd_advance_fd (sp, fd, true);
1184 int saved_errno = errno;
1186 __set_errno (saved_errno);
1191 return (sp->fts_child);
1194 /* A comparison function to sort on increasing inode number.
1195 For some file system types, sorting either way makes a huge
1196 performance difference for a directory with very many entries,
1197 but sorting on increasing values is slightly better than sorting
1198 on decreasing values. The difference is in the 5% range. */
1200 fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b)
1202 return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? -1
1203 : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? 1 : 0);
1206 /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode
1207 S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */
1209 set_stat_type (struct stat *st, unsigned int dtype)
1241 #define closedir_and_clear(dirp) \
1249 #define fts_opendir(file, Pdir_fd) \
1250 opendirat((! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
1251 ? sp->fts_cwd_fd : AT_FDCWD), \
1253 (((ISSET(FTS_PHYSICAL) \
1254 && ! (ISSET(FTS_COMFOLLOW) \
1255 && cur->fts_level == FTS_ROOTLEVEL)) \
1257 | (ISSET (FTS_NOATIME) ? O_NOATIME : 0)), \
1261 * This is the tricky part -- do not casually change *anything* in here. The
1262 * idea is to build the linked list of entries that are used by fts_children
1263 * and fts_read. There are lots of special cases.
1265 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
1266 * set and it's a physical walk (so that symbolic links can't be directories),
1267 * we can do things quickly. First, if it's a 4.4BSD file system, the type
1268 * of the file is in the directory entry. Otherwise, we assume that the number
1269 * of subdirectories in a node is equal to the number of links to the parent.
1270 * The former skips all stat calls. The latter skips stat calls in any leaf
1271 * directories and for any files after the subdirectories in the directory have
1272 * been found, cutting the stat calls by about 2/3.
1276 fts_build (register FTS *sp, int type)
1278 register FTSENT *p, *head;
1279 register size_t nitems;
1288 size_t len, maxlen, new_len;
1291 FTSENT *cur = sp->fts_cur;
1292 bool continue_readdir = !!cur->fts_dirp;
1294 /* When cur->fts_dirp is non-NULL, that means we should
1295 continue calling readdir on that existing DIR* pointer
1296 rather than opening a new one. */
1297 if (continue_readdir)
1299 DIR *dp = cur->fts_dirp;
1300 dir_fd = dirfd (dp);
1303 closedir_and_clear (cur->fts_dirp);
1306 cur->fts_info = FTS_DNR;
1307 cur->fts_errno = errno;
1314 /* Open the directory for reading. If this fails, we're done.
1315 If being called from fts_read, set the fts_info field. */
1316 if ((cur->fts_dirp = fts_opendir(cur->fts_accpath, &dir_fd)) == NULL)
1320 cur->fts_info = FTS_DNR;
1321 cur->fts_errno = errno;
1325 /* Rather than calling fts_stat for each and every entry encountered
1326 in the readdir loop (below), stat each directory only right after
1328 if (cur->fts_info == FTS_NSOK)
1329 cur->fts_info = fts_stat(sp, cur, false);
1330 else if (sp->fts_options & FTS_TIGHT_CYCLE_CHECK)
1332 /* Now read the stat info again after opening a directory to
1333 reveal eventual changes caused by a submount triggered by
1334 the traversal. But do it only for utilities which use
1335 FTS_TIGHT_CYCLE_CHECK. Therefore, only find and du
1336 benefit/suffer from this feature for now. */
1337 LEAVE_DIR (sp, cur, "4");
1338 fts_stat (sp, cur, false);
1339 if (! enter_dir (sp, cur))
1341 __set_errno (ENOMEM);
1347 /* Maximum number of readdir entries to read at one time. This
1348 limitation is to avoid reading millions of entries into memory
1349 at once. When an fts_compar function is specified, we have no
1350 choice: we must read all entries into memory before calling that
1351 function. But when no such function is specified, we can read
1352 entries in batches that are large enough to help us with inode-
1353 sorting, yet not so large that we risk exhausting memory. */
1354 size_t max_entries = (sp->fts_compar == NULL
1355 ? FTS_MAX_READDIR_ENTRIES : SIZE_MAX);
1358 * Nlinks is the number of possible entries of type directory in the
1359 * directory if we're cheating on stat calls, 0 if we're not doing
1360 * any stat calls at all, (nlink_t) -1 if we're statting everything.
1362 if (type == BNAMES) {
1364 /* Be quiet about nostat, GCC. */
1366 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
1367 nlinks = (cur->fts_statp->st_nlink
1368 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1376 * If we're going to need to stat anything or we want to descend
1377 * and stay in the directory, chdir. If this fails we keep going,
1378 * but set a flag so we don't chdir after the post-order visit.
1379 * We won't be able to stat anything, but we can still return the
1380 * names themselves. Note, that since fts_read won't be able to
1381 * chdir into the directory, it will have to return different file
1382 * names than before, i.e. "a/b" instead of "b". Since the node
1383 * has already been visited in pre-order, have to wait until the
1384 * post-order visit to return the error. There is a special case
1385 * here, if there was nothing to stat then it's not an error to
1386 * not be able to stat. This is all fairly nasty. If a program
1387 * needed sorted entries or stat information, they had better be
1388 * checking FTS_NS on the returned nodes.
1390 if (continue_readdir)
1392 /* When resuming a short readdir run, we already have
1393 the required dirp and dir_fd. */
1396 else if (nlinks || type == BREAD) {
1397 if (ISSET(FTS_CWDFD))
1399 dir_fd = dup (dir_fd);
1401 set_cloexec_flag (dir_fd, true);
1403 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
1404 if (nlinks && type == BREAD)
1405 cur->fts_errno = errno;
1406 cur->fts_flags |= FTS_DONTCHDIR;
1408 closedir_and_clear(cur->fts_dirp);
1409 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1411 cur->fts_dirp = NULL;
1418 * Figure out the max file name length that can be stored in the
1419 * current buffer -- the inner loop allocates more space as necessary.
1420 * We really wouldn't have to do the maxlen calculations here, we
1421 * could do them in fts_read before returning the name, but it's a
1422 * lot easier here since the length is part of the dirent structure.
1424 * If not changing directories set a pointer so that can just append
1425 * each new component into the file name.
1428 if (ISSET(FTS_NOCHDIR)) {
1429 cp = sp->fts_path + len;
1432 /* GCC, you're too verbose. */
1436 maxlen = sp->fts_pathlen - len;
1438 level = cur->fts_level + 1;
1440 /* Read the directory, attaching each entry to the "link" pointer. */
1445 while (cur->fts_dirp) {
1447 struct dirent *dp = readdir(cur->fts_dirp);
1450 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1453 if ((p = fts_alloc (sp, dp->d_name,
1454 _D_EXACT_NAMLEN (dp))) == NULL)
1456 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
1457 /* include space for NUL */
1458 oldaddr = sp->fts_path;
1459 if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
1461 * No more memory. Save
1462 * errno, free up the current structure and the
1463 * structures already allocated.
1465 mem1: saved_errno = errno;
1468 closedir_and_clear(cur->fts_dirp);
1469 cur->fts_info = FTS_ERR;
1471 __set_errno (saved_errno);
1474 /* Did realloc() change the pointer? */
1475 if (oldaddr != sp->fts_path) {
1477 if (ISSET(FTS_NOCHDIR))
1478 cp = sp->fts_path + len;
1480 maxlen = sp->fts_pathlen - len;
1483 new_len = len + _D_EXACT_NAMLEN (dp);
1484 if (new_len < len) {
1486 * In the unlikely event that we would end up
1487 * with a file name longer than SIZE_MAX, free up
1488 * the current structure and the structures already
1489 * allocated, then error out with ENAMETOOLONG.
1493 closedir_and_clear(cur->fts_dirp);
1494 cur->fts_info = FTS_ERR;
1496 __set_errno (ENAMETOOLONG);
1499 p->fts_level = level;
1500 p->fts_parent = sp->fts_cur;
1501 p->fts_pathlen = new_len;
1503 /* Store dirent.d_ino, in case we need to sort
1504 entries before processing them. */
1505 p->fts_statp->st_ino = D_INO (dp);
1507 /* Build a file name for fts_stat to stat. */
1508 if (ISSET(FTS_NOCHDIR)) {
1509 p->fts_accpath = p->fts_path;
1510 memmove(cp, p->fts_name, p->fts_namelen + 1);
1512 p->fts_accpath = p->fts_name;
1514 if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {
1515 /* Record what fts_read will have to do with this
1516 entry. In many cases, it will simply fts_stat it,
1517 but we can take advantage of any d_type information
1518 to optimize away the unnecessary stat calls. I.e.,
1519 if FTS_NOSTAT is in effect and we're not following
1520 symlinks (FTS_PHYSICAL) and d_type indicates this
1521 is *not* a directory, then we won't have to stat it
1522 at all. If it *is* a directory, then (currently)
1523 we stat it regardless, in order to get device and
1524 inode numbers. Some day we might optimize that
1525 away, too, for directories where d_ino is known to
1527 bool skip_stat = (ISSET(FTS_PHYSICAL)
1528 && ISSET(FTS_NOSTAT)
1530 && ! DT_MUST_BE(dp, DT_DIR));
1531 p->fts_info = FTS_NSOK;
1532 /* Propagate dirent.d_type information back
1533 to caller, when possible. */
1534 set_stat_type (p->fts_statp, D_TYPE (dp));
1535 fts_set_stat_required(p, !skip_stat);
1536 is_dir = (ISSET(FTS_PHYSICAL)
1537 && DT_MUST_BE(dp, DT_DIR));
1539 p->fts_info = fts_stat(sp, p, false);
1540 is_dir = (p->fts_info == FTS_D
1541 || p->fts_info == FTS_DC
1542 || p->fts_info == FTS_DOT);
1545 /* Decrement link count if applicable. */
1546 if (nlinks > 0 && is_dir)
1549 /* We walk in directory order so "ls -f" doesn't get upset. */
1558 if (max_entries <= nitems) {
1559 /* When there are too many dir entries, leave
1560 fts_dirp open, so that a subsequent fts_read
1561 can take up where we leave off. */
1562 goto break_without_closedir;
1567 closedir_and_clear(cur->fts_dirp);
1569 break_without_closedir:
1572 * If realloc() changed the address of the file name, adjust the
1573 * addresses for the rest of the tree and the dir list.
1576 fts_padjust(sp, head);
1579 * If not changing directories, reset the file name back to original
1582 if (ISSET(FTS_NOCHDIR)) {
1583 if (len == sp->fts_pathlen || nitems == 0)
1589 * If descended after called from fts_children or after called from
1590 * fts_read and nothing found, get back. At the root level we use
1591 * the saved fd; if one of fts_open()'s arguments is a relative name
1592 * to an empty directory, we wind up here with no other way back. If
1593 * can't get back, we're done.
1595 if (!continue_readdir && descend && (type == BCHILD || !nitems) &&
1596 (cur->fts_level == FTS_ROOTLEVEL
1597 ? restore_initial_cwd(sp)
1598 : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1599 cur->fts_info = FTS_ERR;
1605 /* If didn't find anything, return NULL. */
1608 cur->fts_info = FTS_DP;
1613 /* If there are many entries, no sorting function has been specified,
1614 and this file system is of a type that may be slow with a large
1615 number of entries, then sort the directory entries on increasing
1617 if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
1619 && ISSET (FTS_CWDFD)
1620 && dirent_inode_sort_may_be_useful (sp->fts_cwd_fd)) {
1621 sp->fts_compar = fts_compare_ino;
1622 head = fts_sort (sp, head, nitems);
1623 sp->fts_compar = NULL;
1626 /* Sort the entries. */
1627 if (sp->fts_compar && nitems > 1)
1628 head = fts_sort(sp, head, nitems);
1634 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1635 current hierarchy. There should be a directory with dev/inode
1636 matching those of AD. If not, print a lot of diagnostics. */
1638 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1641 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1643 if (ad->ino == ent->fts_statp->st_ino
1644 && ad->dev == ent->fts_statp->st_dev)
1647 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1648 printf ("active dirs:\n");
1650 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1651 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1652 ad->fts_ent->fts_accpath,
1653 (uintmax_t) ad->dev,
1654 (uintmax_t) ad->ino,
1656 (uintmax_t) ent->fts_statp->st_dev,
1657 (uintmax_t) ent->fts_statp->st_ino);
1661 fts_cross_check (FTS const *sp)
1663 FTSENT const *ent = sp->fts_cur;
1665 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1668 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1669 /* Make sure every parent dir is in the tree. */
1670 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1672 struct Active_dir ad;
1673 ad.ino = t->fts_statp->st_ino;
1674 ad.dev = t->fts_statp->st_dev;
1675 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1676 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1679 /* Make sure every dir in the tree is an active dir.
1680 But ENT is not necessarily a directory. If so, just skip this part. */
1681 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1682 && (ent->fts_info == FTS_DP
1683 || ent->fts_info == FTS_D))
1685 struct Active_dir *ad;
1686 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1687 ad = hash_get_next (sp->fts_cycle.ht, ad))
1689 find_matching_ancestor (ent, ad);
1695 same_fd (int fd1, int fd2)
1697 struct stat sb1, sb2;
1698 return (fstat (fd1, &sb1) == 0
1699 && fstat (fd2, &sb2) == 0
1700 && SAME_INODE (sb1, sb2));
1704 fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
1706 I_ring const *fd_ring = &sp->fts_fd_ring;
1707 unsigned int i = fd_ring->fts_front;
1708 char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0);
1709 fprintf (stream, "=== %s ========== %s\n", msg, cwd);
1711 if (i_ring_empty (fd_ring))
1716 int fd = fd_ring->fts_fd_ring[i];
1718 fprintf (stream, "%d: %d:\n", i, fd);
1721 char *wd = getcwdat (fd, NULL, 0);
1722 fprintf (stream, "%d: %d: %s\n", i, fd, wd);
1725 if (i == fd_ring->fts_back)
1727 i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
1731 /* Ensure that each file descriptor on the fd_ring matches a
1732 parent, grandparent, etc. of the current working directory. */
1734 fd_ring_check (FTS const *sp)
1739 /* Make a writable copy. */
1740 I_ring fd_w = sp->fts_fd_ring;
1742 int cwd_fd = sp->fts_cwd_fd;
1743 cwd_fd = dup (cwd_fd);
1744 char *dot = getcwdat (cwd_fd, NULL, 0);
1745 error (0, 0, "===== check ===== cwd: %s", dot);
1747 while ( ! i_ring_empty (&fd_w))
1749 int fd = i_ring_pop (&fd_w);
1752 int parent_fd = openat (cwd_fd, "..", O_SEARCH | O_NOATIME);
1758 if (!same_fd (fd, parent_fd))
1760 char *cwd = getcwdat (fd, NULL, 0);
1761 error (0, errno, "ring : %s", cwd);
1762 char *c2 = getcwdat (parent_fd, NULL, 0);
1763 error (0, errno, "parent: %s", c2);
1776 static unsigned short int
1778 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1780 struct stat *sbp = p->fts_statp;
1783 if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
1787 * If doing a logical walk, or application requested FTS_FOLLOW, do
1788 * a stat(2). If that fails, check for a non-existent symlink. If
1789 * fail, set the errno from the stat call.
1791 if (ISSET(FTS_LOGICAL) || follow) {
1792 if (stat(p->fts_accpath, sbp)) {
1793 saved_errno = errno;
1795 && lstat(p->fts_accpath, sbp) == 0) {
1797 return (FTS_SLNONE);
1799 p->fts_errno = saved_errno;
1802 } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp,
1803 AT_SYMLINK_NOFOLLOW)) {
1804 p->fts_errno = errno;
1805 err: memset(sbp, 0, sizeof(struct stat));
1809 if (S_ISDIR(sbp->st_mode)) {
1810 p->fts_n_dirs_remaining = (sbp->st_nlink
1811 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1812 if (ISDOT(p->fts_name)) {
1813 /* Command-line "." and ".." are real directories. */
1814 return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
1819 if (S_ISLNK(sbp->st_mode))
1821 if (S_ISREG(sbp->st_mode))
1823 return (FTS_DEFAULT);
1827 fts_compar (void const *a, void const *b)
1829 /* Convert A and B to the correct types, to pacify the compiler, and
1830 for portability to bizarre hosts where "void const *" and "FTSENT
1831 const **" differ in runtime representation. The comparison
1832 function cannot modify *a and *b, but there is no compile-time
1834 FTSENT const **pa = (FTSENT const **) a;
1835 FTSENT const **pb = (FTSENT const **) b;
1836 return pa[0]->fts_fts->fts_compar (pa, pb);
1841 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1843 register FTSENT **ap, *p;
1845 /* On most modern hosts, void * and FTSENT ** have the same
1846 run-time representation, and one can convert sp->fts_compar to
1847 the type qsort expects without problem. Use the heuristic that
1848 this is OK if the two pointer types are the same size, and if
1849 converting FTSENT ** to long int is the same as converting
1850 FTSENT ** to void * and then to long int. This heuristic isn't
1851 valid in general but we don't know of any counterexamples. */
1853 int (*compare) (void const *, void const *) =
1854 ((sizeof &dummy == sizeof (void *)
1855 && (long int) &dummy == (long int) (void *) &dummy)
1856 ? (int (*) (void const *, void const *)) sp->fts_compar
1860 * Construct an array of pointers to the structures and call qsort(3).
1861 * Reassemble the array in the order returned by qsort. If unable to
1862 * sort for memory reasons, return the directory entries in their
1863 * current order. Allocate enough space for the current needs plus
1864 * 40 so don't realloc one entry at a time.
1866 if (nitems > sp->fts_nitems) {
1869 sp->fts_nitems = nitems + 40;
1870 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1871 || ! (a = realloc (sp->fts_array,
1872 sp->fts_nitems * sizeof *a))) {
1873 free(sp->fts_array);
1874 sp->fts_array = NULL;
1880 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1882 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1883 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1884 ap[0]->fts_link = ap[1];
1885 ap[0]->fts_link = NULL;
1891 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1897 * The file name is a variable length array. Allocate the FTSENT
1898 * structure and the file name in one chunk.
1900 len = sizeof(FTSENT) + namelen;
1901 if ((p = malloc(len)) == NULL)
1904 /* Copy the name and guarantee NUL termination. */
1905 memcpy(p->fts_name, name, namelen);
1906 p->fts_name[namelen] = '\0';
1908 p->fts_namelen = namelen;
1910 p->fts_path = sp->fts_path;
1914 p->fts_instr = FTS_NOINSTR;
1916 p->fts_pointer = NULL;
1922 fts_lfree (register FTSENT *head)
1926 /* Free a linked list of structures. */
1927 while ((p = head)) {
1928 head = head->fts_link;
1930 closedir (p->fts_dirp);
1936 * Allow essentially unlimited file name lengths; find, rm, ls should
1937 * all work on any tree. Most systems will allow creation of file
1938 * names much longer than MAXPATHLEN, even though the kernel won't
1939 * resolve them. Add the size (not just what's needed) plus 256 bytes
1940 * so don't realloc the file name 2 bytes at a time.
1944 fts_palloc (FTS *sp, size_t more)
1947 size_t new_len = sp->fts_pathlen + more + 256;
1950 * See if fts_pathlen would overflow.
1952 if (new_len < sp->fts_pathlen) {
1954 sp->fts_path = NULL;
1955 __set_errno (ENAMETOOLONG);
1958 sp->fts_pathlen = new_len;
1959 p = realloc(sp->fts_path, sp->fts_pathlen);
1962 sp->fts_path = NULL;
1970 * When the file name is realloc'd, have to fix all of the pointers in
1971 * structures already returned.
1975 fts_padjust (FTS *sp, FTSENT *head)
1978 char *addr = sp->fts_path;
1980 #define ADJUST(p) do { \
1981 if ((p)->fts_accpath != (p)->fts_name) { \
1982 (p)->fts_accpath = \
1983 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1985 (p)->fts_path = addr; \
1987 /* Adjust the current set of children. */
1988 for (p = sp->fts_child; p; p = p->fts_link)
1991 /* Adjust the rest of the tree, including the current level. */
1992 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1994 p = p->fts_link ? p->fts_link : p->fts_parent;
1999 internal_function _GL_ATTRIBUTE_PURE
2000 fts_maxarglen (char * const *argv)
2004 for (max = 0; *argv; ++argv)
2005 if ((len = strlen(*argv)) > max)
2011 * Change to dir specified by fd or file name without getting
2012 * tricked by someone changing the world out from underneath us.
2013 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
2014 * If FD is non-negative, expect it to be used after this function returns,
2015 * and to be closed eventually. So don't pass e.g., 'dirfd(dirp)' and then
2016 * do closedir(dirp), because that would invalidate the saved FD.
2017 * Upon failure, close FD immediately and return nonzero.
2021 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
2024 bool is_dotdot = dir && STREQ (dir, "..");
2027 /* This clause handles the unusual case in which FTS_NOCHDIR
2028 is specified, along with FTS_CWDFD. In that case, there is
2029 no need to change even the virtual cwd file descriptor.
2030 However, if FD is non-negative, we do close it here. */
2031 if (ISSET (FTS_NOCHDIR))
2033 if (ISSET (FTS_CWDFD) && 0 <= fd)
2038 if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
2040 /* When possible, skip the diropen and subsequent fstat+dev/ino
2041 comparison. I.e., when changing to parent directory
2042 (chdir ("..")), use a file descriptor from the ring and
2043 save the overhead of diropen+fstat, as well as avoiding
2044 failure when we lack "x" access to the virtual cwd. */
2045 if ( ! i_ring_empty (&sp->fts_fd_ring))
2048 fd_ring_print (sp, stderr, "pre-pop");
2049 parent_fd = i_ring_pop (&sp->fts_fd_ring);
2060 if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
2063 /* The following dev/inode check is necessary if we're doing a
2064 "logical" traversal (through symlinks, a la chown -L), if the
2065 system lacks O_NOFOLLOW support, or if we're changing to ".."
2066 (but not via a popped file descriptor). When changing to the
2067 name "..", O_NOFOLLOW can't help. In general, when the target is
2068 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
2069 follow a symlink, so we can avoid the expense of this fstat. */
2070 if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
2071 || (dir && STREQ (dir, "..")))
2074 if (fstat(newfd, &sb))
2079 if (p->fts_statp->st_dev != sb.st_dev
2080 || p->fts_statp->st_ino != sb.st_ino)
2082 __set_errno (ENOENT); /* disinformation */
2088 if (ISSET(FTS_CWDFD))
2090 cwd_advance_fd (sp, newfd, ! is_dotdot);
2094 ret = fchdir(newfd);
2100 __set_errno (oerrno);