1 /* Traverse a file hierarchy.
3 Copyright (C) 2004-2017 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 GCC_LINT && !defined lint
50 static char sccsid
[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94";
55 #if HAVE_SYS_PARAM_H || defined _LIBC
56 # include <sys/param.h>
59 # include <include/sys/stat.h>
61 # include <sys/stat.h>
74 # include "dirent--.h"
75 # include "unistd--.h"
76 /* FIXME - use fcntl(F_DUPFD_CLOEXEC)/openat(O_CLOEXEC) once they are
79 # include "flexmember.h"
81 # include "same-inode.h"
85 #ifndef _D_EXACT_NAMLEN
86 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
89 #if HAVE_STRUCT_DIRENT_D_TYPE
90 /* True if the type of the directory entry D is known. */
91 # define DT_IS_KNOWN(d) ((d)->d_type != DT_UNKNOWN)
92 /* True if the type of the directory entry D must be T. */
93 # define DT_MUST_BE(d, t) ((d)->d_type == (t))
94 # define D_TYPE(d) ((d)->d_type)
96 # define DT_IS_KNOWN(d) false
97 # define DT_MUST_BE(d, t) false
98 # define D_TYPE(d) DT_UNKNOWN
101 # define DT_UNKNOWN 0
103 /* Any nonzero values will do here, so long as they're distinct.
104 Undef any existing macros out of the way. */
130 NOT_AN_INODE_NUMBER
= 0
133 #ifdef D_INO_IN_DIRENT
134 # define D_INO(dp) (dp)->d_ino
136 /* Some systems don't have inodes, so fake them to avoid lots of ifdefs. */
137 # define D_INO(dp) NOT_AN_INODE_NUMBER
140 /* If possible (see max_entries, below), read no more than this many directory
141 entries at a time. Without this limit (i.e., when using non-NULL
142 fts_compar), processing a directory with 4,000,000 entries requires ~1GiB
143 of memory, and handling 64M entries would require 16GiB of memory. */
144 #ifndef FTS_MAX_READDIR_ENTRIES
145 # define FTS_MAX_READDIR_ENTRIES 100000
148 /* If there are more than this many entries in a directory,
149 and the conditions mentioned below are satisfied, then sort
150 the entries on inode number before any further processing. */
151 #ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
152 # define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000
157 _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
= FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
162 FTS_NO_STAT_REQUIRED
= 1,
163 FTS_STAT_REQUIRED
= 2
168 # define close __close
170 # define closedir __closedir
172 # define fchdir __fchdir
176 # define readdir __readdir
178 # undef internal_function
179 # define internal_function /* empty */
183 # define __set_errno(Val) errno = (Val)
186 /* If this host provides the openat function, then we can avoid
187 attempting to open "." in some initialization code below. */
189 # define HAVE_OPENAT_SUPPORT 1
191 # define HAVE_OPENAT_SUPPORT 0
195 # define fts_assert(expr) ((void) (0 && (expr)))
197 # define fts_assert(expr) \
208 # define FALLTHROUGH ((void) 0)
210 # define FALLTHROUGH __attribute__ ((__fallthrough__))
214 static FTSENT
*fts_alloc (FTS
*, const char *, size_t) internal_function
;
215 static FTSENT
*fts_build (FTS
*, int) internal_function
;
216 static void fts_lfree (FTSENT
*) internal_function
;
217 static void fts_load (FTS
*, FTSENT
*) internal_function
;
218 static size_t fts_maxarglen (char * const *) internal_function
;
219 static void fts_padjust (FTS
*, FTSENT
*) internal_function
;
220 static bool fts_palloc (FTS
*, size_t) internal_function
;
221 static FTSENT
*fts_sort (FTS
*, FTSENT
*, size_t) internal_function
;
222 static unsigned short int fts_stat (FTS
*, FTSENT
*, bool) internal_function
;
223 static int fts_safe_changedir (FTS
*, FTSENT
*, int, const char *)
226 #include "fts-cycle.c"
229 # define MAX(a,b) ((a) > (b) ? (a) : (b))
233 # define SIZE_MAX ((size_t) -1)
236 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
237 #define STREQ(a, b) (strcmp (a, b) == 0)
239 #define CLR(opt) (sp->fts_options &= ~(opt))
240 #define ISSET(opt) (sp->fts_options & (opt))
241 #define SET(opt) (sp->fts_options |= (opt))
243 /* FIXME: FTS_NOCHDIR is now misnamed.
244 Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
245 #define FCHDIR(sp, fd) \
246 (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \
247 ? (cwd_advance_fd ((sp), (fd), true), 0) \
251 /* fts_build flags */
252 /* FIXME: make this an enum */
253 #define BCHILD 1 /* fts_children */
254 #define BNAMES 2 /* fts_children, names only */
255 #define BREAD 3 /* fts_read */
258 # include <inttypes.h>
261 # include "getcwdat.h"
262 bool fts_debug
= false;
263 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
266 # define fd_ring_check(x)
267 # define fd_ring_print(a, b, c)
270 #define LEAVE_DIR(Fts, Ent, Tag) \
273 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
274 leave_dir (Fts, Ent); \
275 fd_ring_check (Fts); \
280 fd_ring_clear (I_ring
*fd_ring
)
282 while ( ! i_ring_empty (fd_ring
))
284 int fd
= i_ring_pop (fd_ring
);
290 /* Overload the fts_statp->st_size member (otherwise unused, when
291 fts_info is FTS_NSOK) to indicate whether fts_read should stat
292 this entry or not. */
294 fts_set_stat_required (FTSENT
*p
, bool required
)
296 fts_assert (p
->fts_info
== FTS_NSOK
);
297 p
->fts_statp
->st_size
= (required
299 : FTS_NO_STAT_REQUIRED
);
302 /* file-descriptor-relative opendir. */
303 /* FIXME: if others need this function, move it into lib/openat.c */
306 opendirat (int fd
, char const *dir
, int extra_flags
, int *pdir_fd
)
308 int new_fd
= openat (fd
, dir
,
309 (O_RDONLY
| O_DIRECTORY
| O_NOCTTY
| O_NONBLOCK
315 set_cloexec_flag (new_fd
, true);
316 dirp
= fdopendir (new_fd
);
321 int saved_errno
= errno
;
328 /* Virtual fchdir. Advance SP's working directory file descriptor,
329 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
330 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
331 open on sp->fts_cwd_fd; i.e., to move the working directory one level
335 cwd_advance_fd (FTS
*sp
, int fd
, bool chdir_down_one
)
337 int old
= sp
->fts_cwd_fd
;
338 fts_assert (old
!= fd
|| old
== AT_FDCWD
);
342 /* Push "old" onto the ring.
343 If the displaced file descriptor is non-negative, close it. */
344 int prev_fd_in_slot
= i_ring_push (&sp
->fts_fd_ring
, old
);
345 fd_ring_print (sp
, stderr
, "post-push");
346 if (0 <= prev_fd_in_slot
)
347 close (prev_fd_in_slot
); /* ignore any close failure */
349 else if ( ! ISSET (FTS_NOCHDIR
))
352 close (old
); /* ignore any close failure */
358 /* Restore the initial, pre-traversal, "working directory".
359 In FTS_CWDFD mode, we merely call cwd_advance_fd, otherwise,
360 we may actually change the working directory.
361 Return 0 upon success. Upon failure, set errno and return nonzero. */
363 restore_initial_cwd (FTS
*sp
)
365 int fail
= FCHDIR (sp
, ISSET (FTS_CWDFD
) ? AT_FDCWD
: sp
->fts_rfd
);
366 fd_ring_clear (&(sp
->fts_fd_ring
));
370 /* Open the directory DIR if possible, and return a file
371 descriptor. Return -1 and set errno on failure. It doesn't matter
372 whether the file descriptor has read or write access. */
376 diropen (FTS
const *sp
, char const *dir
)
378 int open_flags
= (O_SEARCH
| O_DIRECTORY
| O_NOCTTY
| O_NONBLOCK
379 | (ISSET (FTS_PHYSICAL
) ? O_NOFOLLOW
: 0)
380 | (ISSET (FTS_NOATIME
) ? O_NOATIME
: 0));
382 int fd
= (ISSET (FTS_CWDFD
)
383 ? openat (sp
->fts_cwd_fd
, dir
, open_flags
)
384 : open (dir
, open_flags
));
386 set_cloexec_flag (fd
, true);
391 fts_open (char * const *argv
,
392 register int options
,
393 int (*compar
) (FTSENT
const **, FTSENT
const **))
396 register FTSENT
*p
, *root
;
397 register size_t nitems
;
398 FTSENT
*parent
= NULL
;
399 FTSENT
*tmp
= NULL
; /* pacify gcc */
403 if (options
& ~FTS_OPTIONMASK
) {
404 __set_errno (EINVAL
);
407 if ((options
& FTS_NOCHDIR
) && (options
& FTS_CWDFD
)) {
408 __set_errno (EINVAL
);
411 if ( ! (options
& (FTS_LOGICAL
| FTS_PHYSICAL
))) {
412 __set_errno (EINVAL
);
416 /* Allocate/initialize the stream */
417 if ((sp
= malloc(sizeof(FTS
))) == NULL
)
419 memset(sp
, 0, sizeof(FTS
));
420 sp
->fts_compar
= compar
;
421 sp
->fts_options
= options
;
423 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
424 if (ISSET(FTS_LOGICAL
)) {
429 /* Initialize fts_cwd_fd. */
430 sp
->fts_cwd_fd
= AT_FDCWD
;
431 if ( ISSET(FTS_CWDFD
) && ! HAVE_OPENAT_SUPPORT
)
433 /* While it isn't technically necessary to open "." this
434 early, doing it here saves us the trouble of ensuring
435 later (where it'd be messier) that "." can in fact
436 be opened. If not, revert to FTS_NOCHDIR mode. */
438 O_SEARCH
| (ISSET (FTS_NOATIME
) ? O_NOATIME
: 0));
441 /* Even if "." is unreadable, don't revert to FTS_NOCHDIR mode
442 on systems like Linux+PROC_FS, where our openat emulation
443 is good enough. Note: on a system that emulates
444 openat via /proc, this technique can still fail, but
445 only in extreme conditions, e.g., when the working
446 directory cannot be saved (i.e. save_cwd fails) --
447 and that happens on Linux only when "." is unreadable
448 and the CWD would be longer than PATH_MAX.
449 FIXME: once Linux kernel openat support is well established,
450 replace the above open call and this entire if/else block
451 with the body of the if-block below. */
452 if ( openat_needs_fchdir ())
465 * Start out with 1K of file name space, and enough, in any case,
466 * to hold the user's file names.
469 # define MAXPATHLEN 1024
472 size_t maxarglen
= fts_maxarglen(argv
);
473 if (! fts_palloc(sp
, MAX(maxarglen
, MAXPATHLEN
)))
477 /* Allocate/initialize root's parent. */
479 if ((parent
= fts_alloc(sp
, "", 0)) == NULL
)
481 parent
->fts_level
= FTS_ROOTPARENTLEVEL
;
482 parent
->fts_n_dirs_remaining
= -1;
485 /* The classic fts implementation would call fts_stat with
486 a new entry for each iteration of the loop below.
487 If the comparison function is not specified or if the
488 FTS_DEFER_STAT option is in effect, don't stat any entry
489 in this loop. This is an attempt to minimize the interval
490 between the initial stat/lstat/fstatat and the point at which
491 a directory argument is first opened. This matters for any
492 directory command line argument that resides on a file system
493 without genuine i-nodes. If you specify FTS_DEFER_STAT along
494 with a comparison function, that function must not access any
495 data via the fts_statp pointer. */
496 defer_stat
= (compar
== NULL
|| ISSET(FTS_DEFER_STAT
));
498 /* Allocate/initialize root(s). */
499 for (root
= NULL
, nitems
= 0; *argv
!= NULL
; ++argv
, ++nitems
) {
500 /* *Do* allow zero-length file names. */
501 size_t len
= strlen(*argv
);
503 if ( ! (options
& FTS_VERBATIM
))
505 /* If there are two or more trailing slashes, trim all but one,
506 but don't change "//" to "/", and do map "///" to "/". */
507 char const *v
= *argv
;
508 if (2 < len
&& v
[len
- 1] == '/')
509 while (1 < len
&& v
[len
- 2] == '/')
513 if ((p
= fts_alloc(sp
, *argv
, len
)) == NULL
)
515 p
->fts_level
= FTS_ROOTLEVEL
;
516 p
->fts_parent
= parent
;
517 p
->fts_accpath
= p
->fts_name
;
518 /* Even when defer_stat is true, be sure to stat the first
519 command line argument, since fts_read (at least with
520 FTS_XDEV) requires that. */
521 if (defer_stat
&& root
!= NULL
) {
522 p
->fts_info
= FTS_NSOK
;
523 fts_set_stat_required(p
, true);
525 p
->fts_info
= fts_stat(sp
, p
, false);
529 * If comparison routine supplied, traverse in sorted
530 * order; otherwise traverse in the order specified.
545 if (compar
&& nitems
> 1)
546 root
= fts_sort(sp
, root
, nitems
);
549 * Allocate a dummy pointer and make fts_read think that we've just
550 * finished the node before the root(s); set p->fts_info to FTS_INIT
551 * so that everything about the "current" node is ignored.
553 if ((sp
->fts_cur
= fts_alloc(sp
, "", 0)) == NULL
)
555 sp
->fts_cur
->fts_link
= root
;
556 sp
->fts_cur
->fts_info
= FTS_INIT
;
557 if (! setup_dir (sp
))
561 * If using chdir(2), grab a file descriptor pointing to dot to ensure
562 * that we can get back here; this could be avoided for some file names,
563 * but almost certainly not worth the effort. Slashes, symbolic links,
564 * and ".." are all fairly nasty problems. Note, if we can't get the
565 * descriptor we run anyway, just more slowly.
567 if (!ISSET(FTS_NOCHDIR
) && !ISSET(FTS_CWDFD
)
568 && (sp
->fts_rfd
= diropen (sp
, ".")) < 0)
571 i_ring_init (&sp
->fts_fd_ring
, -1);
574 mem3
: fts_lfree(root
);
576 mem2
: free(sp
->fts_path
);
583 fts_load (FTS
*sp
, register FTSENT
*p
)
589 * Load the stream structure for the next traversal. Since we don't
590 * actually enter the directory until after the preorder visit, set
591 * the fts_accpath field specially so the chdir gets done to the right
592 * place and the user can access the first node. From fts_open it's
593 * known that the file name will fit.
595 len
= p
->fts_pathlen
= p
->fts_namelen
;
596 memmove(sp
->fts_path
, p
->fts_name
, len
+ 1);
597 if ((cp
= strrchr(p
->fts_name
, '/')) && (cp
!= p
->fts_name
|| cp
[1])) {
599 memmove(p
->fts_name
, cp
, len
+ 1);
600 p
->fts_namelen
= len
;
602 p
->fts_accpath
= p
->fts_path
= sp
->fts_path
;
608 register FTSENT
*freep
, *p
;
612 * This still works if we haven't read anything -- the dummy structure
613 * points to the root list, so we step through to the end of the root
614 * list which has a valid parent pointer.
617 for (p
= sp
->fts_cur
; p
->fts_level
>= FTS_ROOTLEVEL
;) {
619 p
= p
->fts_link
!= NULL
? p
->fts_link
: p
->fts_parent
;
625 /* Free up child linked list, sort array, file name buffer. */
627 fts_lfree(sp
->fts_child
);
631 if (ISSET(FTS_CWDFD
))
633 if (0 <= sp
->fts_cwd_fd
)
634 if (close (sp
->fts_cwd_fd
))
637 else if (!ISSET(FTS_NOCHDIR
))
639 /* Return to original directory, save errno if necessary. */
640 if (fchdir(sp
->fts_rfd
))
643 /* If close fails, record errno only if saved_errno is zero,
644 so that we report the probably-more-meaningful fchdir errno. */
645 if (close (sp
->fts_rfd
))
646 if (saved_errno
== 0)
650 fd_ring_clear (&sp
->fts_fd_ring
);
652 if (sp
->fts_leaf_optimization_works_ht
)
653 hash_free (sp
->fts_leaf_optimization_works_ht
);
657 /* Free up the stream pointer. */
660 /* Set errno and return. */
662 __set_errno (saved_errno
);
669 /* Minimum link count of a traditional Unix directory. When leaf
670 optimization is OK and MIN_DIR_NLINK <= st_nlink, then st_nlink is
671 an upper bound on the number of subdirectories (counting "." and
673 enum { MIN_DIR_NLINK
= 2 };
675 /* Whether leaf optimization is OK for a directory. */
676 enum leaf_optimization
678 /* st_nlink is not reliable for this directory's subdirectories. */
679 NO_LEAF_OPTIMIZATION
,
681 /* Leaf optimization is OK, but is not useful for avoiding stat calls. */
682 OK_LEAF_OPTIMIZATION
,
684 /* Leaf optimization is not only OK: it is useful for avoiding
685 stat calls, because dirent.d_type does not work. */
686 NOSTAT_LEAF_OPTIMIZATION
689 #if defined __linux__ \
690 && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
692 # include <sys/vfs.h>
694 /* Linux-specific constants from coreutils' src/fs.h */
695 # define S_MAGIC_AFS 0x5346414F
696 # define S_MAGIC_NFS 0x6969
697 # define S_MAGIC_PROC 0x9FA0
698 # define S_MAGIC_REISERFS 0x52654973
699 # define S_MAGIC_TMPFS 0x1021994
700 # define S_MAGIC_XFS 0x58465342
702 /* Map a stat.st_dev number to a file system type number f_ftype. */
709 /* Use a tiny initial size. If a traversal encounters more than
710 a few devices, the cost of growing/rehashing this table will be
711 rendered negligible by the number of inodes processed. */
712 enum { DEV_TYPE_HT_INITIAL_SIZE
= 13 };
715 dev_type_hash (void const *x
, size_t table_size
)
717 struct dev_type
const *ax
= x
;
718 uintmax_t dev
= ax
->st_dev
;
719 return dev
% table_size
;
723 dev_type_compare (void const *x
, void const *y
)
725 struct dev_type
const *ax
= x
;
726 struct dev_type
const *ay
= y
;
727 return ax
->st_dev
== ay
->st_dev
;
730 /* Return the file system type of P, or 0 if not known.
731 Try to cache known values. */
734 filesystem_type (FTSENT
const *p
)
736 FTS
*sp
= p
->fts_fts
;
737 Hash_table
*h
= sp
->fts_leaf_optimization_works_ht
;
738 struct dev_type
*ent
;
739 struct statfs fs_buf
;
741 /* If we're not in CWDFD mode, don't bother with this optimization,
742 since the caller is not serious about performance. */
743 if (!ISSET (FTS_CWDFD
))
747 h
= sp
->fts_leaf_optimization_works_ht
748 = hash_initialize (DEV_TYPE_HT_INITIAL_SIZE
, NULL
, dev_type_hash
,
749 dev_type_compare
, free
);
753 tmp
.st_dev
= p
->fts_statp
->st_dev
;
754 ent
= hash_lookup (h
, &tmp
);
759 /* Look-up failed. Query directly and cache the result. */
760 if (fstatfs (p
->fts_fts
->fts_cwd_fd
, &fs_buf
) != 0)
765 struct dev_type
*t2
= malloc (sizeof *t2
);
768 t2
->st_dev
= p
->fts_statp
->st_dev
;
769 t2
->f_type
= fs_buf
.f_type
;
771 ent
= hash_insert (h
, t2
);
773 fts_assert (ent
== t2
);
779 return fs_buf
.f_type
;
782 /* Return false if it is easy to determine the file system type of the
783 directory P, and sorting dirents on inode numbers is known not to
784 improve traversal performance with that type of file system.
785 Otherwise, return true. */
787 dirent_inode_sort_may_be_useful (FTSENT
const *p
)
789 /* Skip the sort only if we can determine efficiently
790 that skipping it is the right thing to do.
791 The cost of performing an unnecessary sort is negligible,
792 while the cost of *not* performing it can be O(N^2) with
793 a very large constant. */
795 switch (filesystem_type (p
))
799 /* On a file system of any of these types, sorting
800 is unnecessary, and hence wasteful. */
808 /* Given an FTS entry P for a directory D,
809 return true if it is both useful and valid to apply leaf optimization.
810 The optimization is useful only for file systems that lack usable
811 dirent.d_type info. The optimization is valid if an st_nlink value
812 of at least MIN_DIR_NLINK is an upper bound on the number of
813 subdirectories of D, counting "." and ".." as subdirectories. */
814 static enum leaf_optimization
815 leaf_optimization (FTSENT
const *p
)
817 switch (filesystem_type (p
))
819 /* List here the file system types that lack usable dirent.d_type
820 info, yet for which the optimization does apply. */
821 case S_MAGIC_REISERFS
:
823 return NOSTAT_LEAF_OPTIMIZATION
;
826 /* Leaf optimization is unsafe if the file system type is unknown. */
829 /* Although AFS mount points are not counted in st_nlink, they
830 act like directories. See <https://bugs.debian.org/143111>. */
833 /* NFS provides usable dirent.d_type but not necessarily for all entries
834 of large directories, so as per <https://bugzilla.redhat.com/1252549>
835 NFS should return true. However st_nlink values are not accurate on
836 all implementations as per <https://bugzilla.redhat.com/1299169>. */
839 /* Per <http://bugs.debian.org/143111> /proc may have
840 bogus stat.st_nlink values. */
841 return NO_LEAF_OPTIMIZATION
;
844 return OK_LEAF_OPTIMIZATION
;
850 dirent_inode_sort_may_be_useful (FTSENT
const *p _GL_UNUSED
)
854 static enum leaf_optimization
855 leaf_optimization (FTSENT
const *p _GL_UNUSED
)
857 return NO_LEAF_OPTIMIZATION
;
862 * Special case of "/" at the end of the file name so that slashes aren't
863 * appended which would cause file names to be written as "....//foo".
866 (p->fts_path[p->fts_pathlen - 1] == '/' \
867 ? p->fts_pathlen - 1 : p->fts_pathlen)
870 fts_read (register FTS
*sp
)
872 register FTSENT
*p
, *tmp
;
873 register unsigned short int instr
;
876 /* If finished or unrecoverable error, return NULL. */
877 if (sp
->fts_cur
== NULL
|| ISSET(FTS_STOP
))
880 /* Set current node pointer. */
883 /* Save and zero out user instructions. */
884 instr
= p
->fts_instr
;
885 p
->fts_instr
= FTS_NOINSTR
;
887 /* Any type of file may be re-visited; re-stat and re-turn. */
888 if (instr
== FTS_AGAIN
) {
889 p
->fts_info
= fts_stat(sp
, p
, false);
892 Dprintf (("fts_read: p=%s\n",
893 p
->fts_info
== FTS_INIT
? "" : p
->fts_path
));
896 * Following a symlink -- SLNONE test allows application to see
897 * SLNONE and recover. If indirecting through a symlink, have
898 * keep a pointer to current location. If unable to get that
899 * pointer, follow fails.
901 if (instr
== FTS_FOLLOW
&&
902 (p
->fts_info
== FTS_SL
|| p
->fts_info
== FTS_SLNONE
)) {
903 p
->fts_info
= fts_stat(sp
, p
, true);
904 if (p
->fts_info
== FTS_D
&& !ISSET(FTS_NOCHDIR
)) {
905 if ((p
->fts_symfd
= diropen (sp
, ".")) < 0) {
906 p
->fts_errno
= errno
;
907 p
->fts_info
= FTS_ERR
;
909 p
->fts_flags
|= FTS_SYMFOLLOW
;
914 /* Directory in pre-order. */
915 if (p
->fts_info
== FTS_D
) {
916 /* If skipped or crossed mount point, do post-order visit. */
917 if (instr
== FTS_SKIP
||
918 (ISSET(FTS_XDEV
) && p
->fts_statp
->st_dev
!= sp
->fts_dev
)) {
919 if (p
->fts_flags
& FTS_SYMFOLLOW
)
920 (void)close(p
->fts_symfd
);
922 fts_lfree(sp
->fts_child
);
923 sp
->fts_child
= NULL
;
925 p
->fts_info
= FTS_DP
;
926 LEAVE_DIR (sp
, p
, "1");
930 /* Rebuild if only read the names and now traversing. */
931 if (sp
->fts_child
!= NULL
&& ISSET(FTS_NAMEONLY
)) {
933 fts_lfree(sp
->fts_child
);
934 sp
->fts_child
= NULL
;
938 * Cd to the subdirectory.
940 * If have already read and now fail to chdir, whack the list
941 * to make the names come out right, and set the parent errno
942 * so the application will eventually get an error condition.
943 * Set the FTS_DONTCHDIR flag so that when we logically change
944 * directories back to the parent we don't do a chdir.
946 * If haven't read do so. If the read fails, fts_build sets
947 * FTS_STOP or the fts_info field of the node.
949 if (sp
->fts_child
!= NULL
) {
950 if (fts_safe_changedir(sp
, p
, -1, p
->fts_accpath
)) {
951 p
->fts_errno
= errno
;
952 p
->fts_flags
|= FTS_DONTCHDIR
;
953 for (p
= sp
->fts_child
; p
!= NULL
;
956 p
->fts_parent
->fts_accpath
;
958 } else if ((sp
->fts_child
= fts_build(sp
, BREAD
)) == NULL
) {
961 /* If fts_build's call to fts_safe_changedir failed
962 because it was not able to fchdir into a
963 subdirectory, tell the caller. */
964 if (p
->fts_errno
&& p
->fts_info
!= FTS_DNR
)
965 p
->fts_info
= FTS_ERR
;
966 LEAVE_DIR (sp
, p
, "2");
970 sp
->fts_child
= NULL
;
974 /* Move to the next node on this level. */
977 /* If we have so many directory entries that we're reading them
978 in batches, and we've reached the end of the current batch,
979 read in a new batch. */
980 if (p
->fts_link
== NULL
&& p
->fts_parent
->fts_dirp
)
984 sp
->fts_path
[p
->fts_pathlen
] = '\0';
986 if ((p
= fts_build (sp
, BREAD
)) == NULL
)
997 if ((p
= p
->fts_link
) != NULL
) {
1002 * If reached the top, return to the original directory (or
1003 * the root of the tree), and load the file names for the next
1006 if (p
->fts_level
== FTS_ROOTLEVEL
) {
1007 if (restore_initial_cwd(sp
)) {
1018 * User may have called fts_set on the node. If skipped,
1019 * ignore. If followed, get a file descriptor so we can
1020 * get back if necessary.
1022 if (p
->fts_instr
== FTS_SKIP
)
1024 if (p
->fts_instr
== FTS_FOLLOW
) {
1025 p
->fts_info
= fts_stat(sp
, p
, true);
1026 if (p
->fts_info
== FTS_D
&& !ISSET(FTS_NOCHDIR
)) {
1027 if ((p
->fts_symfd
= diropen (sp
, ".")) < 0) {
1028 p
->fts_errno
= errno
;
1029 p
->fts_info
= FTS_ERR
;
1031 p
->fts_flags
|= FTS_SYMFOLLOW
;
1033 p
->fts_instr
= FTS_NOINSTR
;
1036 name
: t
= sp
->fts_path
+ NAPPEND(p
->fts_parent
);
1038 memmove(t
, p
->fts_name
, p
->fts_namelen
+ 1);
1041 if (p
->fts_info
== FTS_NSOK
)
1043 if (p
->fts_statp
->st_size
== FTS_STAT_REQUIRED
)
1045 FTSENT
*parent
= p
->fts_parent
;
1046 if (parent
->fts_n_dirs_remaining
== 0
1047 && ISSET(FTS_NOSTAT
)
1048 && ISSET(FTS_PHYSICAL
)
1049 && (leaf_optimization (parent
)
1050 == NOSTAT_LEAF_OPTIMIZATION
))
1052 /* nothing more needed */
1056 p
->fts_info
= fts_stat(sp
, p
, false);
1057 if (S_ISDIR(p
->fts_statp
->st_mode
)
1058 && p
->fts_level
!= FTS_ROOTLEVEL
1059 && 0 < parent
->fts_n_dirs_remaining
1060 && parent
->fts_n_dirs_remaining
!= (nlink_t
) -1)
1061 parent
->fts_n_dirs_remaining
--;
1065 fts_assert (p
->fts_statp
->st_size
== FTS_NO_STAT_REQUIRED
);
1068 if (p
->fts_info
== FTS_D
)
1070 /* Now that P->fts_statp is guaranteed to be valid,
1071 if this is a command-line directory, record its
1072 device number, to be used for FTS_XDEV. */
1073 if (p
->fts_level
== FTS_ROOTLEVEL
)
1074 sp
->fts_dev
= p
->fts_statp
->st_dev
;
1075 Dprintf ((" entering: %s\n", p
->fts_path
));
1076 if (! enter_dir (sp
, p
))
1078 __set_errno (ENOMEM
);
1086 /* Move up to the parent node. */
1087 p
= tmp
->fts_parent
;
1091 if (p
->fts_level
== FTS_ROOTPARENTLEVEL
) {
1093 * Done; free everything up and set errno to 0 so the user
1094 * can distinguish between error and EOF.
1098 return (sp
->fts_cur
= NULL
);
1101 fts_assert (p
->fts_info
!= FTS_NSOK
);
1103 /* NUL terminate the file name. */
1104 sp
->fts_path
[p
->fts_pathlen
] = '\0';
1107 * Return to the parent directory. If at a root node, restore
1108 * the initial working directory. If we came through a symlink,
1109 * go back through the file descriptor. Otherwise, move up
1110 * one level, via "..".
1112 if (p
->fts_level
== FTS_ROOTLEVEL
) {
1113 if (restore_initial_cwd(sp
)) {
1114 p
->fts_errno
= errno
;
1117 } else if (p
->fts_flags
& FTS_SYMFOLLOW
) {
1118 if (FCHDIR(sp
, p
->fts_symfd
)) {
1119 p
->fts_errno
= errno
;
1122 (void)close(p
->fts_symfd
);
1123 } else if (!(p
->fts_flags
& FTS_DONTCHDIR
) &&
1124 fts_safe_changedir(sp
, p
->fts_parent
, -1, "..")) {
1125 p
->fts_errno
= errno
;
1129 /* If the directory causes a cycle, preserve the FTS_DC flag and keep
1130 the corresponding dev/ino pair in the hash table. It is going to be
1131 removed when leaving the original directory. */
1132 if (p
->fts_info
!= FTS_DC
) {
1133 p
->fts_info
= p
->fts_errno
? FTS_ERR
: FTS_DP
;
1134 if (p
->fts_errno
== 0)
1135 LEAVE_DIR (sp
, p
, "3");
1137 return ISSET(FTS_STOP
) ? NULL
: p
;
1141 * Fts_set takes the stream as an argument although it's not used in this
1142 * implementation; it would be necessary if anyone wanted to add global
1143 * semantics to fts using fts_set. An error return is allowed for similar
1148 fts_set(FTS
*sp _GL_UNUSED
, FTSENT
*p
, int instr
)
1150 if (instr
!= 0 && instr
!= FTS_AGAIN
&& instr
!= FTS_FOLLOW
&&
1151 instr
!= FTS_NOINSTR
&& instr
!= FTS_SKIP
) {
1152 __set_errno (EINVAL
);
1155 p
->fts_instr
= instr
;
1160 fts_children (register FTS
*sp
, int instr
)
1165 if (instr
!= 0 && instr
!= FTS_NAMEONLY
) {
1166 __set_errno (EINVAL
);
1170 /* Set current node pointer. */
1174 * Errno set to 0 so user can distinguish empty directory from
1179 /* Fatal errors stop here. */
1180 if (ISSET(FTS_STOP
))
1183 /* Return logical hierarchy of user's arguments. */
1184 if (p
->fts_info
== FTS_INIT
)
1185 return (p
->fts_link
);
1188 * If not a directory being visited in pre-order, stop here. Could
1189 * allow FTS_DNR, assuming the user has fixed the problem, but the
1190 * same effect is available with FTS_AGAIN.
1192 if (p
->fts_info
!= FTS_D
/* && p->fts_info != FTS_DNR */)
1195 /* Free up any previous child list. */
1196 if (sp
->fts_child
!= NULL
)
1197 fts_lfree(sp
->fts_child
);
1199 if (instr
== FTS_NAMEONLY
) {
1206 * If using chdir on a relative file name and called BEFORE fts_read
1207 * does its chdir to the root of a traversal, we can lose -- we need to
1208 * chdir into the subdirectory, and we don't know where the current
1209 * directory is, so we can't get back so that the upcoming chdir by
1210 * fts_read will work.
1212 if (p
->fts_level
!= FTS_ROOTLEVEL
|| p
->fts_accpath
[0] == '/' ||
1214 return (sp
->fts_child
= fts_build(sp
, instr
));
1216 if ((fd
= diropen (sp
, ".")) < 0)
1217 return (sp
->fts_child
= NULL
);
1218 sp
->fts_child
= fts_build(sp
, instr
);
1219 if (ISSET(FTS_CWDFD
))
1221 cwd_advance_fd (sp
, fd
, true);
1227 int saved_errno
= errno
;
1229 __set_errno (saved_errno
);
1234 return (sp
->fts_child
);
1237 /* A comparison function to sort on increasing inode number.
1238 For some file system types, sorting either way makes a huge
1239 performance difference for a directory with very many entries,
1240 but sorting on increasing values is slightly better than sorting
1241 on decreasing values. The difference is in the 5% range. */
1243 fts_compare_ino (struct _ftsent
const **a
, struct _ftsent
const **b
)
1245 return (a
[0]->fts_statp
->st_ino
< b
[0]->fts_statp
->st_ino
? -1
1246 : b
[0]->fts_statp
->st_ino
< a
[0]->fts_statp
->st_ino
? 1 : 0);
1249 /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode
1250 S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */
1252 set_stat_type (struct stat
*st
, unsigned int dtype
)
1284 #define closedir_and_clear(dirp) \
1292 #define fts_opendir(file, Pdir_fd) \
1293 opendirat((! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
1294 ? sp->fts_cwd_fd : AT_FDCWD), \
1296 (((ISSET(FTS_PHYSICAL) \
1297 && ! (ISSET(FTS_COMFOLLOW) \
1298 && cur->fts_level == FTS_ROOTLEVEL)) \
1300 | (ISSET (FTS_NOATIME) ? O_NOATIME : 0)), \
1304 * This is the tricky part -- do not casually change *anything* in here. The
1305 * idea is to build the linked list of entries that are used by fts_children
1306 * and fts_read. There are lots of special cases.
1308 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
1309 * set and it's a physical walk (so that symbolic links can't be directories),
1310 * we can do things quickly. First, if it's a 4.4BSD file system, the type
1311 * of the file is in the directory entry. Otherwise, we assume that the number
1312 * of subdirectories in a node is equal to the number of links to the parent.
1313 * The former skips all stat calls. The latter skips stat calls in any leaf
1314 * directories and for any files after the subdirectories in the directory have
1315 * been found, cutting the stat calls by about 2/3.
1319 fts_build (register FTS
*sp
, int type
)
1321 register FTSENT
*p
, *head
;
1322 register size_t nitems
;
1329 size_t len
, maxlen
, new_len
;
1332 FTSENT
*cur
= sp
->fts_cur
;
1333 bool continue_readdir
= !!cur
->fts_dirp
;
1336 /* When cur->fts_dirp is non-NULL, that means we should
1337 continue calling readdir on that existing DIR* pointer
1338 rather than opening a new one. */
1339 if (continue_readdir
)
1341 DIR *dp
= cur
->fts_dirp
;
1342 dir_fd
= dirfd (dp
);
1345 closedir_and_clear (cur
->fts_dirp
);
1348 cur
->fts_info
= FTS_DNR
;
1349 cur
->fts_errno
= errno
;
1356 /* Open the directory for reading. If this fails, we're done.
1357 If being called from fts_read, set the fts_info field. */
1358 if ((cur
->fts_dirp
= fts_opendir(cur
->fts_accpath
, &dir_fd
)) == NULL
)
1362 cur
->fts_info
= FTS_DNR
;
1363 cur
->fts_errno
= errno
;
1367 /* Rather than calling fts_stat for each and every entry encountered
1368 in the readdir loop (below), stat each directory only right after
1370 if (cur
->fts_info
== FTS_NSOK
)
1371 cur
->fts_info
= fts_stat(sp
, cur
, false);
1372 else if (sp
->fts_options
& FTS_TIGHT_CYCLE_CHECK
)
1374 /* Now read the stat info again after opening a directory to
1375 reveal eventual changes caused by a submount triggered by
1376 the traversal. But do it only for utilities which use
1377 FTS_TIGHT_CYCLE_CHECK. Therefore, only find and du
1378 benefit/suffer from this feature for now. */
1379 LEAVE_DIR (sp
, cur
, "4");
1380 fts_stat (sp
, cur
, false);
1381 if (! enter_dir (sp
, cur
))
1383 __set_errno (ENOMEM
);
1389 /* Maximum number of readdir entries to read at one time. This
1390 limitation is to avoid reading millions of entries into memory
1391 at once. When an fts_compar function is specified, we have no
1392 choice: we must read all entries into memory before calling that
1393 function. But when no such function is specified, we can read
1394 entries in batches that are large enough to help us with inode-
1395 sorting, yet not so large that we risk exhausting memory. */
1396 max_entries
= sp
->fts_compar
? SIZE_MAX
: FTS_MAX_READDIR_ENTRIES
;
1399 * If we're going to need to stat anything or we want to descend
1400 * and stay in the directory, chdir. If this fails we keep going,
1401 * but set a flag so we don't chdir after the post-order visit.
1402 * We won't be able to stat anything, but we can still return the
1403 * names themselves. Note, that since fts_read won't be able to
1404 * chdir into the directory, it will have to return different file
1405 * names than before, i.e. "a/b" instead of "b". Since the node
1406 * has already been visited in pre-order, have to wait until the
1407 * post-order visit to return the error. There is a special case
1408 * here, if there was nothing to stat then it's not an error to
1409 * not be able to stat. This is all fairly nasty. If a program
1410 * needed sorted entries or stat information, they had better be
1411 * checking FTS_NS on the returned nodes.
1413 if (continue_readdir
)
1415 /* When resuming a short readdir run, we already have
1416 the required dirp and dir_fd. */
1421 /* Try to descend unless it is a names-only fts_children,
1422 or the directory is a known to lack subdirectories. */
1423 descend
= (type
!= BNAMES
1424 && ! (ISSET (FTS_NOSTAT
) && ISSET (FTS_PHYSICAL
)
1425 && ! ISSET (FTS_SEEDOT
)
1426 && cur
->fts_statp
->st_nlink
== MIN_DIR_NLINK
1427 && (leaf_optimization (cur
)
1428 != NO_LEAF_OPTIMIZATION
)));
1429 if (descend
|| type
== BREAD
)
1431 if (ISSET(FTS_CWDFD
))
1433 dir_fd
= dup (dir_fd
);
1435 set_cloexec_flag (dir_fd
, true);
1437 if (dir_fd
< 0 || fts_safe_changedir(sp
, cur
, dir_fd
, NULL
)) {
1438 if (descend
&& type
== BREAD
)
1439 cur
->fts_errno
= errno
;
1440 cur
->fts_flags
|= FTS_DONTCHDIR
;
1442 closedir_and_clear(cur
->fts_dirp
);
1443 if (ISSET(FTS_CWDFD
) && 0 <= dir_fd
)
1445 cur
->fts_dirp
= NULL
;
1452 * Figure out the max file name length that can be stored in the
1453 * current buffer -- the inner loop allocates more space as necessary.
1454 * We really wouldn't have to do the maxlen calculations here, we
1455 * could do them in fts_read before returning the name, but it's a
1456 * lot easier here since the length is part of the dirent structure.
1458 * If not changing directories set a pointer so that can just append
1459 * each new component into the file name.
1462 if (ISSET(FTS_NOCHDIR
)) {
1463 cp
= sp
->fts_path
+ len
;
1466 /* GCC, you're too verbose. */
1470 maxlen
= sp
->fts_pathlen
- len
;
1472 level
= cur
->fts_level
+ 1;
1474 /* Read the directory, attaching each entry to the "link" pointer. */
1479 while (cur
->fts_dirp
) {
1482 struct dirent
*dp
= readdir(cur
->fts_dirp
);
1485 cur
->fts_errno
= errno
;
1486 /* If we've not read any items yet, treat
1487 the error as if we can't access the dir. */
1488 cur
->fts_info
= (continue_readdir
|| nitems
)
1489 ? FTS_ERR
: FTS_DNR
;
1493 if (!ISSET(FTS_SEEDOT
) && ISDOT(dp
->d_name
))
1496 d_namelen
= _D_EXACT_NAMLEN (dp
);
1497 p
= fts_alloc (sp
, dp
->d_name
, d_namelen
);
1500 if (d_namelen
>= maxlen
) {
1501 /* include space for NUL */
1502 oldaddr
= sp
->fts_path
;
1503 if (! fts_palloc(sp
, d_namelen
+ len
+ 1)) {
1505 * No more memory. Save
1506 * errno, free up the current structure and the
1507 * structures already allocated.
1509 mem1
: saved_errno
= errno
;
1512 closedir_and_clear(cur
->fts_dirp
);
1513 cur
->fts_info
= FTS_ERR
;
1515 __set_errno (saved_errno
);
1518 /* Did realloc() change the pointer? */
1519 if (oldaddr
!= sp
->fts_path
) {
1521 if (ISSET(FTS_NOCHDIR
))
1522 cp
= sp
->fts_path
+ len
;
1524 maxlen
= sp
->fts_pathlen
- len
;
1527 new_len
= len
+ d_namelen
;
1528 if (new_len
< len
) {
1530 * In the unlikely event that we would end up
1531 * with a file name longer than SIZE_MAX, free up
1532 * the current structure and the structures already
1533 * allocated, then error out with ENAMETOOLONG.
1537 closedir_and_clear(cur
->fts_dirp
);
1538 cur
->fts_info
= FTS_ERR
;
1540 __set_errno (ENAMETOOLONG
);
1543 p
->fts_level
= level
;
1544 p
->fts_parent
= sp
->fts_cur
;
1545 p
->fts_pathlen
= new_len
;
1547 /* Store dirent.d_ino, in case we need to sort
1548 entries before processing them. */
1549 p
->fts_statp
->st_ino
= D_INO (dp
);
1551 /* Build a file name for fts_stat to stat. */
1552 if (ISSET(FTS_NOCHDIR
)) {
1553 p
->fts_accpath
= p
->fts_path
;
1554 memmove(cp
, p
->fts_name
, p
->fts_namelen
+ 1);
1556 p
->fts_accpath
= p
->fts_name
;
1558 if (sp
->fts_compar
== NULL
|| ISSET(FTS_DEFER_STAT
)) {
1559 /* Record what fts_read will have to do with this
1560 entry. In many cases, it will simply fts_stat it,
1561 but we can take advantage of any d_type information
1562 to optimize away the unnecessary stat calls. I.e.,
1563 if FTS_NOSTAT is in effect and we're not following
1564 symlinks (FTS_PHYSICAL) and d_type indicates this
1565 is *not* a directory, then we won't have to stat it
1566 at all. If it *is* a directory, then (currently)
1567 we stat it regardless, in order to get device and
1568 inode numbers. Some day we might optimize that
1569 away, too, for directories where d_ino is known to
1571 bool skip_stat
= (ISSET(FTS_PHYSICAL
)
1572 && ISSET(FTS_NOSTAT
)
1574 && ! DT_MUST_BE(dp
, DT_DIR
));
1575 p
->fts_info
= FTS_NSOK
;
1576 /* Propagate dirent.d_type information back
1577 to caller, when possible. */
1578 set_stat_type (p
->fts_statp
, D_TYPE (dp
));
1579 fts_set_stat_required(p
, !skip_stat
);
1581 p
->fts_info
= fts_stat(sp
, p
, false);
1584 /* We walk in directory order so "ls -f" doesn't get upset. */
1593 if (max_entries
<= nitems
) {
1594 /* When there are too many dir entries, leave
1595 fts_dirp open, so that a subsequent fts_read
1596 can take up where we leave off. */
1597 goto break_without_closedir
;
1602 closedir_and_clear(cur
->fts_dirp
);
1604 break_without_closedir
:
1607 * If realloc() changed the address of the file name, adjust the
1608 * addresses for the rest of the tree and the dir list.
1611 fts_padjust(sp
, head
);
1614 * If not changing directories, reset the file name back to original
1617 if (ISSET(FTS_NOCHDIR
)) {
1618 if (len
== sp
->fts_pathlen
|| nitems
== 0)
1624 * If descended after called from fts_children or after called from
1625 * fts_read and nothing found, get back. At the root level we use
1626 * the saved fd; if one of fts_open()'s arguments is a relative name
1627 * to an empty directory, we wind up here with no other way back. If
1628 * can't get back, we're done.
1630 if (!continue_readdir
&& descend
&& (type
== BCHILD
|| !nitems
) &&
1631 (cur
->fts_level
== FTS_ROOTLEVEL
1632 ? restore_initial_cwd(sp
)
1633 : fts_safe_changedir(sp
, cur
->fts_parent
, -1, ".."))) {
1634 cur
->fts_info
= FTS_ERR
;
1640 /* If didn't find anything, return NULL. */
1643 && cur
->fts_info
!= FTS_DNR
&& cur
->fts_info
!= FTS_ERR
)
1644 cur
->fts_info
= FTS_DP
;
1649 /* If there are many entries, no sorting function has been specified,
1650 and this file system is of a type that may be slow with a large
1651 number of entries, then sort the directory entries on increasing
1653 if (nitems
> _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
1655 && dirent_inode_sort_may_be_useful (cur
)) {
1656 sp
->fts_compar
= fts_compare_ino
;
1657 head
= fts_sort (sp
, head
, nitems
);
1658 sp
->fts_compar
= NULL
;
1661 /* Sort the entries. */
1662 if (sp
->fts_compar
&& nitems
> 1)
1663 head
= fts_sort(sp
, head
, nitems
);
1669 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1670 current hierarchy. There should be a directory with dev/inode
1671 matching those of AD. If not, print a lot of diagnostics. */
1673 find_matching_ancestor (FTSENT
const *e_curr
, struct Active_dir
const *ad
)
1676 for (ent
= e_curr
; ent
->fts_level
>= FTS_ROOTLEVEL
; ent
= ent
->fts_parent
)
1678 if (ad
->ino
== ent
->fts_statp
->st_ino
1679 && ad
->dev
== ent
->fts_statp
->st_dev
)
1682 printf ("ERROR: tree dir, %s, not active\n", ad
->fts_ent
->fts_accpath
);
1683 printf ("active dirs:\n");
1685 ent
->fts_level
>= FTS_ROOTLEVEL
; ent
= ent
->fts_parent
)
1686 printf (" %s(%"PRIuMAX
"/%"PRIuMAX
") to %s(%"PRIuMAX
"/%"PRIuMAX
")...\n",
1687 ad
->fts_ent
->fts_accpath
,
1688 (uintmax_t) ad
->dev
,
1689 (uintmax_t) ad
->ino
,
1691 (uintmax_t) ent
->fts_statp
->st_dev
,
1692 (uintmax_t) ent
->fts_statp
->st_ino
);
1696 fts_cross_check (FTS
const *sp
)
1698 FTSENT
const *ent
= sp
->fts_cur
;
1700 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK
))
1703 Dprintf (("fts-cross-check cur=%s\n", ent
->fts_path
));
1704 /* Make sure every parent dir is in the tree. */
1705 for (t
= ent
->fts_parent
; t
->fts_level
>= FTS_ROOTLEVEL
; t
= t
->fts_parent
)
1707 struct Active_dir ad
;
1708 ad
.ino
= t
->fts_statp
->st_ino
;
1709 ad
.dev
= t
->fts_statp
->st_dev
;
1710 if ( ! hash_lookup (sp
->fts_cycle
.ht
, &ad
))
1711 printf ("ERROR: active dir, %s, not in tree\n", t
->fts_path
);
1714 /* Make sure every dir in the tree is an active dir.
1715 But ENT is not necessarily a directory. If so, just skip this part. */
1716 if (ent
->fts_parent
->fts_level
>= FTS_ROOTLEVEL
1717 && (ent
->fts_info
== FTS_DP
1718 || ent
->fts_info
== FTS_D
))
1720 struct Active_dir
*ad
;
1721 for (ad
= hash_get_first (sp
->fts_cycle
.ht
); ad
!= NULL
;
1722 ad
= hash_get_next (sp
->fts_cycle
.ht
, ad
))
1724 find_matching_ancestor (ent
, ad
);
1730 same_fd (int fd1
, int fd2
)
1732 struct stat sb1
, sb2
;
1733 return (fstat (fd1
, &sb1
) == 0
1734 && fstat (fd2
, &sb2
) == 0
1735 && SAME_INODE (sb1
, sb2
));
1739 fd_ring_print (FTS
const *sp
, FILE *stream
, char const *msg
)
1741 I_ring
const *fd_ring
= &sp
->fts_fd_ring
;
1742 unsigned int i
= fd_ring
->fts_front
;
1743 char *cwd
= getcwdat (sp
->fts_cwd_fd
, NULL
, 0);
1744 fprintf (stream
, "=== %s ========== %s\n", msg
, cwd
);
1746 if (i_ring_empty (fd_ring
))
1751 int fd
= fd_ring
->fts_fd_ring
[i
];
1753 fprintf (stream
, "%d: %d:\n", i
, fd
);
1756 char *wd
= getcwdat (fd
, NULL
, 0);
1757 fprintf (stream
, "%d: %d: %s\n", i
, fd
, wd
);
1760 if (i
== fd_ring
->fts_back
)
1762 i
= (i
+ I_RING_SIZE
- 1) % I_RING_SIZE
;
1766 /* Ensure that each file descriptor on the fd_ring matches a
1767 parent, grandparent, etc. of the current working directory. */
1769 fd_ring_check (FTS
const *sp
)
1774 /* Make a writable copy. */
1775 I_ring fd_w
= sp
->fts_fd_ring
;
1777 int cwd_fd
= sp
->fts_cwd_fd
;
1778 cwd_fd
= dup (cwd_fd
);
1779 char *dot
= getcwdat (cwd_fd
, NULL
, 0);
1780 error (0, 0, "===== check ===== cwd: %s", dot
);
1782 while ( ! i_ring_empty (&fd_w
))
1784 int fd
= i_ring_pop (&fd_w
);
1787 int parent_fd
= openat (cwd_fd
, "..", O_SEARCH
| O_NOATIME
);
1793 if (!same_fd (fd
, parent_fd
))
1795 char *cwd
= getcwdat (fd
, NULL
, 0);
1796 error (0, errno
, "ring : %s", cwd
);
1797 char *c2
= getcwdat (parent_fd
, NULL
, 0);
1798 error (0, errno
, "parent: %s", c2
);
1811 static unsigned short int
1813 fts_stat(FTS
*sp
, register FTSENT
*p
, bool follow
)
1815 struct stat
*sbp
= p
->fts_statp
;
1818 if (p
->fts_level
== FTS_ROOTLEVEL
&& ISSET(FTS_COMFOLLOW
))
1822 * If doing a logical walk, or application requested FTS_FOLLOW, do
1823 * a stat(2). If that fails, check for a non-existent symlink. If
1824 * fail, set the errno from the stat call.
1826 if (ISSET(FTS_LOGICAL
) || follow
) {
1827 if (stat(p
->fts_accpath
, sbp
)) {
1828 saved_errno
= errno
;
1830 && lstat(p
->fts_accpath
, sbp
) == 0) {
1832 return (FTS_SLNONE
);
1834 p
->fts_errno
= saved_errno
;
1837 } else if (fstatat(sp
->fts_cwd_fd
, p
->fts_accpath
, sbp
,
1838 AT_SYMLINK_NOFOLLOW
)) {
1839 p
->fts_errno
= errno
;
1840 err
: memset(sbp
, 0, sizeof(struct stat
));
1844 if (S_ISDIR(sbp
->st_mode
)) {
1845 p
->fts_n_dirs_remaining
1846 = ((sbp
->st_nlink
< MIN_DIR_NLINK
1847 || p
->fts_level
<= FTS_ROOTLEVEL
)
1849 : sbp
->st_nlink
- (ISSET (FTS_SEEDOT
) ? 0 : MIN_DIR_NLINK
));
1850 if (ISDOT(p
->fts_name
)) {
1851 /* Command-line "." and ".." are real directories. */
1852 return (p
->fts_level
== FTS_ROOTLEVEL
? FTS_D
: FTS_DOT
);
1857 if (S_ISLNK(sbp
->st_mode
))
1859 if (S_ISREG(sbp
->st_mode
))
1861 return (FTS_DEFAULT
);
1865 fts_compar (void const *a
, void const *b
)
1867 /* Convert A and B to the correct types, to pacify the compiler, and
1868 for portability to bizarre hosts where "void const *" and "FTSENT
1869 const **" differ in runtime representation. The comparison
1870 function cannot modify *a and *b, but there is no compile-time
1872 FTSENT
const **pa
= (FTSENT
const **) a
;
1873 FTSENT
const **pb
= (FTSENT
const **) b
;
1874 return pa
[0]->fts_fts
->fts_compar (pa
, pb
);
1879 fts_sort (FTS
*sp
, FTSENT
*head
, register size_t nitems
)
1881 register FTSENT
**ap
, *p
;
1883 /* On most modern hosts, void * and FTSENT ** have the same
1884 run-time representation, and one can convert sp->fts_compar to
1885 the type qsort expects without problem. Use the heuristic that
1886 this is OK if the two pointer types are the same size, and if
1887 converting FTSENT ** to long int is the same as converting
1888 FTSENT ** to void * and then to long int. This heuristic isn't
1889 valid in general but we don't know of any counterexamples. */
1891 int (*compare
) (void const *, void const *) =
1892 ((sizeof &dummy
== sizeof (void *)
1893 && (long int) &dummy
== (long int) (void *) &dummy
)
1894 ? (int (*) (void const *, void const *)) sp
->fts_compar
1898 * Construct an array of pointers to the structures and call qsort(3).
1899 * Reassemble the array in the order returned by qsort. If unable to
1900 * sort for memory reasons, return the directory entries in their
1901 * current order. Allocate enough space for the current needs plus
1902 * 40 so don't realloc one entry at a time.
1904 if (nitems
> sp
->fts_nitems
) {
1907 sp
->fts_nitems
= nitems
+ 40;
1908 if (SIZE_MAX
/ sizeof *a
< sp
->fts_nitems
1909 || ! (a
= realloc (sp
->fts_array
,
1910 sp
->fts_nitems
* sizeof *a
))) {
1911 free(sp
->fts_array
);
1912 sp
->fts_array
= NULL
;
1918 for (ap
= sp
->fts_array
, p
= head
; p
; p
= p
->fts_link
)
1920 qsort((void *)sp
->fts_array
, nitems
, sizeof(FTSENT
*), compare
);
1921 for (head
= *(ap
= sp
->fts_array
); --nitems
; ++ap
)
1922 ap
[0]->fts_link
= ap
[1];
1923 ap
[0]->fts_link
= NULL
;
1929 fts_alloc (FTS
*sp
, const char *name
, register size_t namelen
)
1935 * The file name is a variable length array. Allocate the FTSENT
1936 * structure and the file name in one chunk.
1938 len
= FLEXSIZEOF(FTSENT
, fts_name
, namelen
+ 1);
1939 if ((p
= malloc(len
)) == NULL
)
1942 /* Copy the name and guarantee NUL termination. */
1943 memcpy(p
->fts_name
, name
, namelen
);
1944 p
->fts_name
[namelen
] = '\0';
1946 p
->fts_namelen
= namelen
;
1948 p
->fts_path
= sp
->fts_path
;
1952 p
->fts_instr
= FTS_NOINSTR
;
1954 p
->fts_pointer
= NULL
;
1960 fts_lfree (register FTSENT
*head
)
1964 /* Free a linked list of structures. */
1965 while ((p
= head
)) {
1966 head
= head
->fts_link
;
1968 closedir (p
->fts_dirp
);
1974 * Allow essentially unlimited file name lengths; find, rm, ls should
1975 * all work on any tree. Most systems will allow creation of file
1976 * names much longer than MAXPATHLEN, even though the kernel won't
1977 * resolve them. Add the size (not just what's needed) plus 256 bytes
1978 * so don't realloc the file name 2 bytes at a time.
1982 fts_palloc (FTS
*sp
, size_t more
)
1985 size_t new_len
= sp
->fts_pathlen
+ more
+ 256;
1988 * See if fts_pathlen would overflow.
1990 if (new_len
< sp
->fts_pathlen
) {
1992 sp
->fts_path
= NULL
;
1993 __set_errno (ENAMETOOLONG
);
1996 sp
->fts_pathlen
= new_len
;
1997 p
= realloc(sp
->fts_path
, sp
->fts_pathlen
);
2000 sp
->fts_path
= NULL
;
2008 * When the file name is realloc'd, have to fix all of the pointers in
2009 * structures already returned.
2013 fts_padjust (FTS
*sp
, FTSENT
*head
)
2016 char *addr
= sp
->fts_path
;
2018 #define ADJUST(p) do { \
2019 if ((p)->fts_accpath != (p)->fts_name) { \
2020 (p)->fts_accpath = \
2021 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
2023 (p)->fts_path = addr; \
2025 /* Adjust the current set of children. */
2026 for (p
= sp
->fts_child
; p
; p
= p
->fts_link
)
2029 /* Adjust the rest of the tree, including the current level. */
2030 for (p
= head
; p
->fts_level
>= FTS_ROOTLEVEL
;) {
2032 p
= p
->fts_link
? p
->fts_link
: p
->fts_parent
;
2037 internal_function _GL_ATTRIBUTE_PURE
2038 fts_maxarglen (char * const *argv
)
2042 for (max
= 0; *argv
; ++argv
)
2043 if ((len
= strlen(*argv
)) > max
)
2049 * Change to dir specified by fd or file name without getting
2050 * tricked by someone changing the world out from underneath us.
2051 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
2052 * If FD is non-negative, expect it to be used after this function returns,
2053 * and to be closed eventually. So don't pass e.g., 'dirfd(dirp)' and then
2054 * do closedir(dirp), because that would invalidate the saved FD.
2055 * Upon failure, close FD immediately and return nonzero.
2059 fts_safe_changedir (FTS
*sp
, FTSENT
*p
, int fd
, char const *dir
)
2062 bool is_dotdot
= dir
&& STREQ (dir
, "..");
2065 /* This clause handles the unusual case in which FTS_NOCHDIR
2066 is specified, along with FTS_CWDFD. In that case, there is
2067 no need to change even the virtual cwd file descriptor.
2068 However, if FD is non-negative, we do close it here. */
2069 if (ISSET (FTS_NOCHDIR
))
2071 if (ISSET (FTS_CWDFD
) && 0 <= fd
)
2076 if (fd
< 0 && is_dotdot
&& ISSET (FTS_CWDFD
))
2078 /* When possible, skip the diropen and subsequent fstat+dev/ino
2079 comparison. I.e., when changing to parent directory
2080 (chdir ("..")), use a file descriptor from the ring and
2081 save the overhead of diropen+fstat, as well as avoiding
2082 failure when we lack "x" access to the virtual cwd. */
2083 if ( ! i_ring_empty (&sp
->fts_fd_ring
))
2086 fd_ring_print (sp
, stderr
, "pre-pop");
2087 parent_fd
= i_ring_pop (&sp
->fts_fd_ring
);
2098 if (fd
< 0 && (newfd
= diropen (sp
, dir
)) < 0)
2101 /* The following dev/inode check is necessary if we're doing a
2102 "logical" traversal (through symlinks, a la chown -L), if the
2103 system lacks O_NOFOLLOW support, or if we're changing to ".."
2104 (but not via a popped file descriptor). When changing to the
2105 name "..", O_NOFOLLOW can't help. In general, when the target is
2106 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
2107 follow a symlink, so we can avoid the expense of this fstat. */
2108 if (ISSET(FTS_LOGICAL
) || ! HAVE_WORKING_O_NOFOLLOW
2109 || (dir
&& STREQ (dir
, "..")))
2112 if (fstat(newfd
, &sb
))
2117 if (p
->fts_statp
->st_dev
!= sb
.st_dev
2118 || p
->fts_statp
->st_ino
!= sb
.st_ino
)
2120 __set_errno (ENOENT
); /* disinformation */
2126 if (ISSET(FTS_CWDFD
))
2128 cwd_advance_fd (sp
, newfd
, ! is_dotdot
);
2132 ret
= fchdir(newfd
);
2138 __set_errno (oerrno
);