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 <https://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 "flexmember.h"
76 # include "same-inode.h"
80 #ifndef _D_EXACT_NAMLEN
81 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
84 #if HAVE_STRUCT_DIRENT_D_TYPE
85 /* True if the type of the directory entry D is known. */
86 # define DT_IS_KNOWN(d) ((d)->d_type != DT_UNKNOWN)
87 /* True if the type of the directory entry D must be T. */
88 # define DT_MUST_BE(d, t) ((d)->d_type == (t))
89 # define D_TYPE(d) ((d)->d_type)
91 # define DT_IS_KNOWN(d) false
92 # define DT_MUST_BE(d, t) false
93 # define D_TYPE(d) DT_UNKNOWN
98 /* Any nonzero values will do here, so long as they're distinct.
99 Undef any existing macros out of the way. */
125 NOT_AN_INODE_NUMBER
= 0
128 #ifdef D_INO_IN_DIRENT
129 # define D_INO(dp) (dp)->d_ino
131 /* Some systems don't have inodes, so fake them to avoid lots of ifdefs. */
132 # define D_INO(dp) NOT_AN_INODE_NUMBER
135 /* If possible (see max_entries, below), read no more than this many directory
136 entries at a time. Without this limit (i.e., when using non-NULL
137 fts_compar), processing a directory with 4,000,000 entries requires ~1GiB
138 of memory, and handling 64M entries would require 16GiB of memory. */
139 #ifndef FTS_MAX_READDIR_ENTRIES
140 # define FTS_MAX_READDIR_ENTRIES 100000
143 /* If there are more than this many entries in a directory,
144 and the conditions mentioned below are satisfied, then sort
145 the entries on inode number before any further processing. */
146 #ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
147 # define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000
152 _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
= FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
157 FTS_NO_STAT_REQUIRED
= 1,
158 FTS_STAT_REQUIRED
= 2
163 # define close __close
165 # define closedir __closedir
167 # define fchdir __fchdir
171 # define readdir __readdir
173 # undef internal_function
174 # define internal_function /* empty */
178 # define __set_errno(Val) errno = (Val)
181 /* If this host provides the openat function, then we can avoid
182 attempting to open "." in some initialization code below. */
184 # define HAVE_OPENAT_SUPPORT 1
186 # define HAVE_OPENAT_SUPPORT 0
190 # define fts_assert(expr) ((void) (0 && (expr)))
192 # define fts_assert(expr) \
203 # define FALLTHROUGH ((void) 0)
205 # define FALLTHROUGH __attribute__ ((__fallthrough__))
209 static FTSENT
*fts_alloc (FTS
*, const char *, size_t) internal_function
;
210 static FTSENT
*fts_build (FTS
*, int) internal_function
;
211 static void fts_lfree (FTSENT
*) internal_function
;
212 static void fts_load (FTS
*, FTSENT
*) internal_function
;
213 static size_t fts_maxarglen (char * const *) internal_function
;
214 static void fts_padjust (FTS
*, FTSENT
*) internal_function
;
215 static bool fts_palloc (FTS
*, size_t) internal_function
;
216 static FTSENT
*fts_sort (FTS
*, FTSENT
*, size_t) internal_function
;
217 static unsigned short int fts_stat (FTS
*, FTSENT
*, bool) internal_function
;
218 static int fts_safe_changedir (FTS
*, FTSENT
*, int, const char *)
221 #include "fts-cycle.c"
224 # define MAX(a,b) ((a) > (b) ? (a) : (b))
228 # define SIZE_MAX ((size_t) -1)
231 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
232 #define STREQ(a, b) (strcmp (a, b) == 0)
234 #define CLR(opt) (sp->fts_options &= ~(opt))
235 #define ISSET(opt) (sp->fts_options & (opt))
236 #define SET(opt) (sp->fts_options |= (opt))
238 /* FIXME: FTS_NOCHDIR is now misnamed.
239 Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
240 #define FCHDIR(sp, fd) \
241 (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \
242 ? (cwd_advance_fd ((sp), (fd), true), 0) \
246 /* fts_build flags */
247 /* FIXME: make this an enum */
248 #define BCHILD 1 /* fts_children */
249 #define BNAMES 2 /* fts_children, names only */
250 #define BREAD 3 /* fts_read */
253 # include <inttypes.h>
256 # include "getcwdat.h"
257 bool fts_debug
= false;
258 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
261 # define fd_ring_check(x)
262 # define fd_ring_print(a, b, c)
265 #define LEAVE_DIR(Fts, Ent, Tag) \
268 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
269 leave_dir (Fts, Ent); \
270 fd_ring_check (Fts); \
275 fd_ring_clear (I_ring
*fd_ring
)
277 while ( ! i_ring_empty (fd_ring
))
279 int fd
= i_ring_pop (fd_ring
);
285 /* Overload the fts_statp->st_size member (otherwise unused, when
286 fts_info is FTS_NSOK) to indicate whether fts_read should stat
287 this entry or not. */
289 fts_set_stat_required (FTSENT
*p
, bool required
)
291 fts_assert (p
->fts_info
== FTS_NSOK
);
292 p
->fts_statp
->st_size
= (required
294 : FTS_NO_STAT_REQUIRED
);
297 /* file-descriptor-relative opendir. */
298 /* FIXME: if others need this function, move it into lib/openat.c */
301 opendirat (int fd
, char const *dir
, int extra_flags
, int *pdir_fd
)
303 int open_flags
= (O_RDONLY
| O_CLOEXEC
| O_DIRECTORY
| O_NOCTTY
304 | O_NONBLOCK
| extra_flags
);
305 int new_fd
= openat (fd
, dir
, open_flags
);
310 dirp
= fdopendir (new_fd
);
315 int saved_errno
= errno
;
322 /* Virtual fchdir. Advance SP's working directory file descriptor,
323 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
324 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
325 open on sp->fts_cwd_fd; i.e., to move the working directory one level
329 cwd_advance_fd (FTS
*sp
, int fd
, bool chdir_down_one
)
331 int old
= sp
->fts_cwd_fd
;
332 fts_assert (old
!= fd
|| old
== AT_FDCWD
);
336 /* Push "old" onto the ring.
337 If the displaced file descriptor is non-negative, close it. */
338 int prev_fd_in_slot
= i_ring_push (&sp
->fts_fd_ring
, old
);
339 fd_ring_print (sp
, stderr
, "post-push");
340 if (0 <= prev_fd_in_slot
)
341 close (prev_fd_in_slot
); /* ignore any close failure */
343 else if ( ! ISSET (FTS_NOCHDIR
))
346 close (old
); /* ignore any close failure */
352 /* Restore the initial, pre-traversal, "working directory".
353 In FTS_CWDFD mode, we merely call cwd_advance_fd, otherwise,
354 we may actually change the working directory.
355 Return 0 upon success. Upon failure, set errno and return nonzero. */
357 restore_initial_cwd (FTS
*sp
)
359 int fail
= FCHDIR (sp
, ISSET (FTS_CWDFD
) ? AT_FDCWD
: sp
->fts_rfd
);
360 fd_ring_clear (&(sp
->fts_fd_ring
));
364 /* Open the directory DIR if possible, and return a file
365 descriptor. Return -1 and set errno on failure. It doesn't matter
366 whether the file descriptor has read or write access. */
370 diropen (FTS
const *sp
, char const *dir
)
372 int open_flags
= (O_SEARCH
| O_CLOEXEC
| O_DIRECTORY
| O_NOCTTY
| O_NONBLOCK
373 | (ISSET (FTS_PHYSICAL
) ? O_NOFOLLOW
: 0)
374 | (ISSET (FTS_NOATIME
) ? O_NOATIME
: 0));
376 int fd
= (ISSET (FTS_CWDFD
)
377 ? openat (sp
->fts_cwd_fd
, dir
, open_flags
)
378 : open (dir
, open_flags
));
383 fts_open (char * const *argv
,
384 register int options
,
385 int (*compar
) (FTSENT
const **, FTSENT
const **))
388 register FTSENT
*p
, *root
;
389 register size_t nitems
;
390 FTSENT
*parent
= NULL
;
391 FTSENT
*tmp
= NULL
; /* pacify gcc */
395 if (options
& ~FTS_OPTIONMASK
) {
396 __set_errno (EINVAL
);
399 if ((options
& FTS_NOCHDIR
) && (options
& FTS_CWDFD
)) {
400 __set_errno (EINVAL
);
403 if ( ! (options
& (FTS_LOGICAL
| FTS_PHYSICAL
))) {
404 __set_errno (EINVAL
);
408 /* Allocate/initialize the stream */
409 if ((sp
= malloc(sizeof(FTS
))) == NULL
)
411 memset(sp
, 0, sizeof(FTS
));
412 sp
->fts_compar
= compar
;
413 sp
->fts_options
= options
;
415 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
416 if (ISSET(FTS_LOGICAL
)) {
421 /* Initialize fts_cwd_fd. */
422 sp
->fts_cwd_fd
= AT_FDCWD
;
423 if ( ISSET(FTS_CWDFD
) && ! HAVE_OPENAT_SUPPORT
)
425 /* While it isn't technically necessary to open "." this
426 early, doing it here saves us the trouble of ensuring
427 later (where it'd be messier) that "." can in fact
428 be opened. If not, revert to FTS_NOCHDIR mode. */
430 O_SEARCH
| (ISSET (FTS_NOATIME
) ? O_NOATIME
: 0));
433 /* Even if "." is unreadable, don't revert to FTS_NOCHDIR mode
434 on systems like Linux+PROC_FS, where our openat emulation
435 is good enough. Note: on a system that emulates
436 openat via /proc, this technique can still fail, but
437 only in extreme conditions, e.g., when the working
438 directory cannot be saved (i.e. save_cwd fails) --
439 and that happens on Linux only when "." is unreadable
440 and the CWD would be longer than PATH_MAX.
441 FIXME: once Linux kernel openat support is well established,
442 replace the above open call and this entire if/else block
443 with the body of the if-block below. */
444 if ( openat_needs_fchdir ())
457 * Start out with 1K of file name space, and enough, in any case,
458 * to hold the user's file names.
461 # define MAXPATHLEN 1024
464 size_t maxarglen
= fts_maxarglen(argv
);
465 if (! fts_palloc(sp
, MAX(maxarglen
, MAXPATHLEN
)))
469 /* Allocate/initialize root's parent. */
471 if ((parent
= fts_alloc(sp
, "", 0)) == NULL
)
473 parent
->fts_level
= FTS_ROOTPARENTLEVEL
;
474 parent
->fts_n_dirs_remaining
= -1;
477 /* The classic fts implementation would call fts_stat with
478 a new entry for each iteration of the loop below.
479 If the comparison function is not specified or if the
480 FTS_DEFER_STAT option is in effect, don't stat any entry
481 in this loop. This is an attempt to minimize the interval
482 between the initial stat/lstat/fstatat and the point at which
483 a directory argument is first opened. This matters for any
484 directory command line argument that resides on a file system
485 without genuine i-nodes. If you specify FTS_DEFER_STAT along
486 with a comparison function, that function must not access any
487 data via the fts_statp pointer. */
488 defer_stat
= (compar
== NULL
|| ISSET(FTS_DEFER_STAT
));
490 /* Allocate/initialize root(s). */
491 for (root
= NULL
, nitems
= 0; *argv
!= NULL
; ++argv
, ++nitems
) {
492 /* *Do* allow zero-length file names. */
493 size_t len
= strlen(*argv
);
495 if ( ! (options
& FTS_VERBATIM
))
497 /* If there are two or more trailing slashes, trim all but one,
498 but don't change "//" to "/", and do map "///" to "/". */
499 char const *v
= *argv
;
500 if (2 < len
&& v
[len
- 1] == '/')
501 while (1 < len
&& v
[len
- 2] == '/')
505 if ((p
= fts_alloc(sp
, *argv
, len
)) == NULL
)
507 p
->fts_level
= FTS_ROOTLEVEL
;
508 p
->fts_parent
= parent
;
509 p
->fts_accpath
= p
->fts_name
;
510 /* Even when defer_stat is true, be sure to stat the first
511 command line argument, since fts_read (at least with
512 FTS_XDEV) requires that. */
513 if (defer_stat
&& root
!= NULL
) {
514 p
->fts_info
= FTS_NSOK
;
515 fts_set_stat_required(p
, true);
517 p
->fts_info
= fts_stat(sp
, p
, false);
521 * If comparison routine supplied, traverse in sorted
522 * order; otherwise traverse in the order specified.
537 if (compar
&& nitems
> 1)
538 root
= fts_sort(sp
, root
, nitems
);
541 * Allocate a dummy pointer and make fts_read think that we've just
542 * finished the node before the root(s); set p->fts_info to FTS_INIT
543 * so that everything about the "current" node is ignored.
545 if ((sp
->fts_cur
= fts_alloc(sp
, "", 0)) == NULL
)
547 sp
->fts_cur
->fts_link
= root
;
548 sp
->fts_cur
->fts_info
= FTS_INIT
;
549 if (! setup_dir (sp
))
553 * If using chdir(2), grab a file descriptor pointing to dot to ensure
554 * that we can get back here; this could be avoided for some file names,
555 * but almost certainly not worth the effort. Slashes, symbolic links,
556 * and ".." are all fairly nasty problems. Note, if we can't get the
557 * descriptor we run anyway, just more slowly.
559 if (!ISSET(FTS_NOCHDIR
) && !ISSET(FTS_CWDFD
)
560 && (sp
->fts_rfd
= diropen (sp
, ".")) < 0)
563 i_ring_init (&sp
->fts_fd_ring
, -1);
566 mem3
: fts_lfree(root
);
568 mem2
: free(sp
->fts_path
);
575 fts_load (FTS
*sp
, register FTSENT
*p
)
581 * Load the stream structure for the next traversal. Since we don't
582 * actually enter the directory until after the preorder visit, set
583 * the fts_accpath field specially so the chdir gets done to the right
584 * place and the user can access the first node. From fts_open it's
585 * known that the file name will fit.
587 len
= p
->fts_pathlen
= p
->fts_namelen
;
588 memmove(sp
->fts_path
, p
->fts_name
, len
+ 1);
589 if ((cp
= strrchr(p
->fts_name
, '/')) && (cp
!= p
->fts_name
|| cp
[1])) {
591 memmove(p
->fts_name
, cp
, len
+ 1);
592 p
->fts_namelen
= len
;
594 p
->fts_accpath
= p
->fts_path
= sp
->fts_path
;
600 register FTSENT
*freep
, *p
;
604 * This still works if we haven't read anything -- the dummy structure
605 * points to the root list, so we step through to the end of the root
606 * list which has a valid parent pointer.
609 for (p
= sp
->fts_cur
; p
->fts_level
>= FTS_ROOTLEVEL
;) {
611 p
= p
->fts_link
!= NULL
? p
->fts_link
: p
->fts_parent
;
617 /* Free up child linked list, sort array, file name buffer. */
619 fts_lfree(sp
->fts_child
);
623 if (ISSET(FTS_CWDFD
))
625 if (0 <= sp
->fts_cwd_fd
)
626 if (close (sp
->fts_cwd_fd
))
629 else if (!ISSET(FTS_NOCHDIR
))
631 /* Return to original directory, save errno if necessary. */
632 if (fchdir(sp
->fts_rfd
))
635 /* If close fails, record errno only if saved_errno is zero,
636 so that we report the probably-more-meaningful fchdir errno. */
637 if (close (sp
->fts_rfd
))
638 if (saved_errno
== 0)
642 fd_ring_clear (&sp
->fts_fd_ring
);
644 if (sp
->fts_leaf_optimization_works_ht
)
645 hash_free (sp
->fts_leaf_optimization_works_ht
);
649 /* Free up the stream pointer. */
652 /* Set errno and return. */
654 __set_errno (saved_errno
);
661 /* Minimum link count of a traditional Unix directory. When leaf
662 optimization is OK and MIN_DIR_NLINK <= st_nlink, then st_nlink is
663 an upper bound on the number of subdirectories (counting "." and
665 enum { MIN_DIR_NLINK
= 2 };
667 /* Whether leaf optimization is OK for a directory. */
668 enum leaf_optimization
670 /* st_nlink is not reliable for this directory's subdirectories. */
671 NO_LEAF_OPTIMIZATION
,
673 /* Leaf optimization is OK, but is not useful for avoiding stat calls. */
674 OK_LEAF_OPTIMIZATION
,
676 /* Leaf optimization is not only OK: it is useful for avoiding
677 stat calls, because dirent.d_type does not work. */
678 NOSTAT_LEAF_OPTIMIZATION
681 #if defined __linux__ \
682 && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
684 # include <sys/vfs.h>
686 /* Linux-specific constants from coreutils' src/fs.h */
687 # define S_MAGIC_AFS 0x5346414F
688 # define S_MAGIC_NFS 0x6969
689 # define S_MAGIC_PROC 0x9FA0
690 # define S_MAGIC_REISERFS 0x52654973
691 # define S_MAGIC_TMPFS 0x1021994
692 # define S_MAGIC_XFS 0x58465342
694 # ifdef HAVE___FSWORD_T
695 typedef __fsword_t fsword
;
697 typedef long int fsword
;
700 /* Map a stat.st_dev number to a file system type number f_ftype. */
707 /* Use a tiny initial size. If a traversal encounters more than
708 a few devices, the cost of growing/rehashing this table will be
709 rendered negligible by the number of inodes processed. */
710 enum { DEV_TYPE_HT_INITIAL_SIZE
= 13 };
713 dev_type_hash (void const *x
, size_t table_size
)
715 struct dev_type
const *ax
= x
;
716 uintmax_t dev
= ax
->st_dev
;
717 return dev
% table_size
;
721 dev_type_compare (void const *x
, void const *y
)
723 struct dev_type
const *ax
= x
;
724 struct dev_type
const *ay
= y
;
725 return ax
->st_dev
== ay
->st_dev
;
728 /* Return the file system type of P, or 0 if not known.
729 Try to cache known values. */
732 filesystem_type (FTSENT
const *p
)
734 FTS
*sp
= p
->fts_fts
;
735 Hash_table
*h
= sp
->fts_leaf_optimization_works_ht
;
736 struct dev_type
*ent
;
737 struct statfs fs_buf
;
739 /* If we're not in CWDFD mode, don't bother with this optimization,
740 since the caller is not serious about performance. */
741 if (!ISSET (FTS_CWDFD
))
745 h
= sp
->fts_leaf_optimization_works_ht
746 = hash_initialize (DEV_TYPE_HT_INITIAL_SIZE
, NULL
, dev_type_hash
,
747 dev_type_compare
, free
);
751 tmp
.st_dev
= p
->fts_statp
->st_dev
;
752 ent
= hash_lookup (h
, &tmp
);
757 /* Look-up failed. Query directly and cache the result. */
758 if (fstatfs (p
->fts_fts
->fts_cwd_fd
, &fs_buf
) != 0)
763 struct dev_type
*t2
= malloc (sizeof *t2
);
766 t2
->st_dev
= p
->fts_statp
->st_dev
;
767 t2
->f_type
= fs_buf
.f_type
;
769 ent
= hash_insert (h
, t2
);
771 fts_assert (ent
== t2
);
777 return fs_buf
.f_type
;
780 /* Return false if it is easy to determine the file system type of the
781 directory P, and sorting dirents on inode numbers is known not to
782 improve traversal performance with that type of file system.
783 Otherwise, return true. */
785 dirent_inode_sort_may_be_useful (FTSENT
const *p
)
787 /* Skip the sort only if we can determine efficiently
788 that skipping it is the right thing to do.
789 The cost of performing an unnecessary sort is negligible,
790 while the cost of *not* performing it can be O(N^2) with
791 a very large constant. */
793 switch (filesystem_type (p
))
797 /* On a file system of any of these types, sorting
798 is unnecessary, and hence wasteful. */
806 /* Given an FTS entry P for a directory D,
807 return true if it is both useful and valid to apply leaf optimization.
808 The optimization is useful only for file systems that lack usable
809 dirent.d_type info. The optimization is valid if an st_nlink value
810 of at least MIN_DIR_NLINK is an upper bound on the number of
811 subdirectories of D, counting "." and ".." as subdirectories. */
812 static enum leaf_optimization
813 leaf_optimization (FTSENT
const *p
)
815 switch (filesystem_type (p
))
817 /* List here the file system types that may lack usable dirent.d_type
818 info, yet for which the optimization does apply. */
819 case S_MAGIC_REISERFS
:
820 case S_MAGIC_XFS
: /* XFS lacked it until 2013-08-22 commit. */
821 return NOSTAT_LEAF_OPTIMIZATION
;
824 /* Leaf optimization is unsafe if the file system type is unknown. */
827 /* Although AFS mount points are not counted in st_nlink, they
828 act like directories. See <https://bugs.debian.org/143111>. */
831 /* NFS provides usable dirent.d_type but not necessarily for all entries
832 of large directories, so as per <https://bugzilla.redhat.com/1252549>
833 NFS should return true. However st_nlink values are not accurate on
834 all implementations as per <https://bugzilla.redhat.com/1299169>. */
837 /* Per <https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=143111> /proc
838 may have bogus stat.st_nlink values. */
839 return NO_LEAF_OPTIMIZATION
;
842 return OK_LEAF_OPTIMIZATION
;
848 dirent_inode_sort_may_be_useful (FTSENT
const *p _GL_UNUSED
)
852 static enum leaf_optimization
853 leaf_optimization (FTSENT
const *p _GL_UNUSED
)
855 return NO_LEAF_OPTIMIZATION
;
860 * Special case of "/" at the end of the file name so that slashes aren't
861 * appended which would cause file names to be written as "....//foo".
864 (p->fts_path[p->fts_pathlen - 1] == '/' \
865 ? p->fts_pathlen - 1 : p->fts_pathlen)
868 fts_read (register FTS
*sp
)
870 register FTSENT
*p
, *tmp
;
871 register unsigned short int instr
;
874 /* If finished or unrecoverable error, return NULL. */
875 if (sp
->fts_cur
== NULL
|| ISSET(FTS_STOP
))
878 /* Set current node pointer. */
881 /* Save and zero out user instructions. */
882 instr
= p
->fts_instr
;
883 p
->fts_instr
= FTS_NOINSTR
;
885 /* Any type of file may be re-visited; re-stat and re-turn. */
886 if (instr
== FTS_AGAIN
) {
887 p
->fts_info
= fts_stat(sp
, p
, false);
890 Dprintf (("fts_read: p=%s\n",
891 p
->fts_info
== FTS_INIT
? "" : p
->fts_path
));
894 * Following a symlink -- SLNONE test allows application to see
895 * SLNONE and recover. If indirecting through a symlink, have
896 * keep a pointer to current location. If unable to get that
897 * pointer, follow fails.
899 if (instr
== FTS_FOLLOW
&&
900 (p
->fts_info
== FTS_SL
|| p
->fts_info
== FTS_SLNONE
)) {
901 p
->fts_info
= fts_stat(sp
, p
, true);
902 if (p
->fts_info
== FTS_D
&& !ISSET(FTS_NOCHDIR
)) {
903 if ((p
->fts_symfd
= diropen (sp
, ".")) < 0) {
904 p
->fts_errno
= errno
;
905 p
->fts_info
= FTS_ERR
;
907 p
->fts_flags
|= FTS_SYMFOLLOW
;
912 /* Directory in pre-order. */
913 if (p
->fts_info
== FTS_D
) {
914 /* If skipped or crossed mount point, do post-order visit. */
915 if (instr
== FTS_SKIP
||
916 (ISSET(FTS_XDEV
) && p
->fts_statp
->st_dev
!= sp
->fts_dev
)) {
917 if (p
->fts_flags
& FTS_SYMFOLLOW
)
918 (void)close(p
->fts_symfd
);
920 fts_lfree(sp
->fts_child
);
921 sp
->fts_child
= NULL
;
923 p
->fts_info
= FTS_DP
;
924 LEAVE_DIR (sp
, p
, "1");
928 /* Rebuild if only read the names and now traversing. */
929 if (sp
->fts_child
!= NULL
&& ISSET(FTS_NAMEONLY
)) {
931 fts_lfree(sp
->fts_child
);
932 sp
->fts_child
= NULL
;
936 * Cd to the subdirectory.
938 * If have already read and now fail to chdir, whack the list
939 * to make the names come out right, and set the parent errno
940 * so the application will eventually get an error condition.
941 * Set the FTS_DONTCHDIR flag so that when we logically change
942 * directories back to the parent we don't do a chdir.
944 * If haven't read do so. If the read fails, fts_build sets
945 * FTS_STOP or the fts_info field of the node.
947 if (sp
->fts_child
!= NULL
) {
948 if (fts_safe_changedir(sp
, p
, -1, p
->fts_accpath
)) {
949 p
->fts_errno
= errno
;
950 p
->fts_flags
|= FTS_DONTCHDIR
;
951 for (p
= sp
->fts_child
; p
!= NULL
;
954 p
->fts_parent
->fts_accpath
;
956 } else if ((sp
->fts_child
= fts_build(sp
, BREAD
)) == NULL
) {
959 /* If fts_build's call to fts_safe_changedir failed
960 because it was not able to fchdir into a
961 subdirectory, tell the caller. */
962 if (p
->fts_errno
&& p
->fts_info
!= FTS_DNR
)
963 p
->fts_info
= FTS_ERR
;
964 LEAVE_DIR (sp
, p
, "2");
968 sp
->fts_child
= NULL
;
972 /* Move to the next node on this level. */
975 /* If we have so many directory entries that we're reading them
976 in batches, and we've reached the end of the current batch,
977 read in a new batch. */
978 if (p
->fts_link
== NULL
&& p
->fts_parent
->fts_dirp
)
982 sp
->fts_path
[p
->fts_pathlen
] = '\0';
984 if ((p
= fts_build (sp
, BREAD
)) == NULL
)
995 if ((p
= p
->fts_link
) != NULL
) {
1000 * If reached the top, return to the original directory (or
1001 * the root of the tree), and load the file names for the next
1004 if (p
->fts_level
== FTS_ROOTLEVEL
) {
1005 if (restore_initial_cwd(sp
)) {
1016 * User may have called fts_set on the node. If skipped,
1017 * ignore. If followed, get a file descriptor so we can
1018 * get back if necessary.
1020 if (p
->fts_instr
== FTS_SKIP
)
1022 if (p
->fts_instr
== FTS_FOLLOW
) {
1023 p
->fts_info
= fts_stat(sp
, p
, true);
1024 if (p
->fts_info
== FTS_D
&& !ISSET(FTS_NOCHDIR
)) {
1025 if ((p
->fts_symfd
= diropen (sp
, ".")) < 0) {
1026 p
->fts_errno
= errno
;
1027 p
->fts_info
= FTS_ERR
;
1029 p
->fts_flags
|= FTS_SYMFOLLOW
;
1031 p
->fts_instr
= FTS_NOINSTR
;
1034 name
: t
= sp
->fts_path
+ NAPPEND(p
->fts_parent
);
1036 memmove(t
, p
->fts_name
, p
->fts_namelen
+ 1);
1039 if (p
->fts_info
== FTS_NSOK
)
1041 if (p
->fts_statp
->st_size
== FTS_STAT_REQUIRED
)
1043 FTSENT
*parent
= p
->fts_parent
;
1044 if (parent
->fts_n_dirs_remaining
== 0
1045 && ISSET(FTS_NOSTAT
)
1046 && ISSET(FTS_PHYSICAL
)
1047 && (leaf_optimization (parent
)
1048 == NOSTAT_LEAF_OPTIMIZATION
))
1050 /* nothing more needed */
1054 p
->fts_info
= fts_stat(sp
, p
, false);
1055 if (S_ISDIR(p
->fts_statp
->st_mode
)
1056 && p
->fts_level
!= FTS_ROOTLEVEL
1057 && 0 < parent
->fts_n_dirs_remaining
1058 && parent
->fts_n_dirs_remaining
!= (nlink_t
) -1)
1059 parent
->fts_n_dirs_remaining
--;
1063 fts_assert (p
->fts_statp
->st_size
== FTS_NO_STAT_REQUIRED
);
1066 if (p
->fts_info
== FTS_D
)
1068 /* Now that P->fts_statp is guaranteed to be valid,
1069 if this is a command-line directory, record its
1070 device number, to be used for FTS_XDEV. */
1071 if (p
->fts_level
== FTS_ROOTLEVEL
)
1072 sp
->fts_dev
= p
->fts_statp
->st_dev
;
1073 Dprintf ((" entering: %s\n", p
->fts_path
));
1074 if (! enter_dir (sp
, p
))
1076 __set_errno (ENOMEM
);
1084 /* Move up to the parent node. */
1085 p
= tmp
->fts_parent
;
1089 if (p
->fts_level
== FTS_ROOTPARENTLEVEL
) {
1091 * Done; free everything up and set errno to 0 so the user
1092 * can distinguish between error and EOF.
1096 return (sp
->fts_cur
= NULL
);
1099 fts_assert (p
->fts_info
!= FTS_NSOK
);
1101 /* NUL terminate the file name. */
1102 sp
->fts_path
[p
->fts_pathlen
] = '\0';
1105 * Return to the parent directory. If at a root node, restore
1106 * the initial working directory. If we came through a symlink,
1107 * go back through the file descriptor. Otherwise, move up
1108 * one level, via "..".
1110 if (p
->fts_level
== FTS_ROOTLEVEL
) {
1111 if (restore_initial_cwd(sp
)) {
1112 p
->fts_errno
= errno
;
1115 } else if (p
->fts_flags
& FTS_SYMFOLLOW
) {
1116 if (FCHDIR(sp
, p
->fts_symfd
)) {
1117 p
->fts_errno
= errno
;
1120 (void)close(p
->fts_symfd
);
1121 } else if (!(p
->fts_flags
& FTS_DONTCHDIR
) &&
1122 fts_safe_changedir(sp
, p
->fts_parent
, -1, "..")) {
1123 p
->fts_errno
= errno
;
1127 /* If the directory causes a cycle, preserve the FTS_DC flag and keep
1128 the corresponding dev/ino pair in the hash table. It is going to be
1129 removed when leaving the original directory. */
1130 if (p
->fts_info
!= FTS_DC
) {
1131 p
->fts_info
= p
->fts_errno
? FTS_ERR
: FTS_DP
;
1132 if (p
->fts_errno
== 0)
1133 LEAVE_DIR (sp
, p
, "3");
1135 return ISSET(FTS_STOP
) ? NULL
: p
;
1139 * Fts_set takes the stream as an argument although it's not used in this
1140 * implementation; it would be necessary if anyone wanted to add global
1141 * semantics to fts using fts_set. An error return is allowed for similar
1146 fts_set(FTS
*sp _GL_UNUSED
, FTSENT
*p
, int instr
)
1148 if (instr
!= 0 && instr
!= FTS_AGAIN
&& instr
!= FTS_FOLLOW
&&
1149 instr
!= FTS_NOINSTR
&& instr
!= FTS_SKIP
) {
1150 __set_errno (EINVAL
);
1153 p
->fts_instr
= instr
;
1158 fts_children (register FTS
*sp
, int instr
)
1163 if (instr
!= 0 && instr
!= FTS_NAMEONLY
) {
1164 __set_errno (EINVAL
);
1168 /* Set current node pointer. */
1172 * Errno set to 0 so user can distinguish empty directory from
1177 /* Fatal errors stop here. */
1178 if (ISSET(FTS_STOP
))
1181 /* Return logical hierarchy of user's arguments. */
1182 if (p
->fts_info
== FTS_INIT
)
1183 return (p
->fts_link
);
1186 * If not a directory being visited in pre-order, stop here. Could
1187 * allow FTS_DNR, assuming the user has fixed the problem, but the
1188 * same effect is available with FTS_AGAIN.
1190 if (p
->fts_info
!= FTS_D
/* && p->fts_info != FTS_DNR */)
1193 /* Free up any previous child list. */
1194 if (sp
->fts_child
!= NULL
)
1195 fts_lfree(sp
->fts_child
);
1197 if (instr
== FTS_NAMEONLY
) {
1204 * If using chdir on a relative file name and called BEFORE fts_read
1205 * does its chdir to the root of a traversal, we can lose -- we need to
1206 * chdir into the subdirectory, and we don't know where the current
1207 * directory is, so we can't get back so that the upcoming chdir by
1208 * fts_read will work.
1210 if (p
->fts_level
!= FTS_ROOTLEVEL
|| p
->fts_accpath
[0] == '/' ||
1212 return (sp
->fts_child
= fts_build(sp
, instr
));
1214 if ((fd
= diropen (sp
, ".")) < 0)
1215 return (sp
->fts_child
= NULL
);
1216 sp
->fts_child
= fts_build(sp
, instr
);
1217 if (ISSET(FTS_CWDFD
))
1219 cwd_advance_fd (sp
, fd
, true);
1225 int saved_errno
= errno
;
1227 __set_errno (saved_errno
);
1232 return (sp
->fts_child
);
1235 /* A comparison function to sort on increasing inode number.
1236 For some file system types, sorting either way makes a huge
1237 performance difference for a directory with very many entries,
1238 but sorting on increasing values is slightly better than sorting
1239 on decreasing values. The difference is in the 5% range. */
1241 fts_compare_ino (struct _ftsent
const **a
, struct _ftsent
const **b
)
1243 return (a
[0]->fts_statp
->st_ino
< b
[0]->fts_statp
->st_ino
? -1
1244 : b
[0]->fts_statp
->st_ino
< a
[0]->fts_statp
->st_ino
? 1 : 0);
1247 /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode
1248 S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */
1250 set_stat_type (struct stat
*st
, unsigned int dtype
)
1282 #define closedir_and_clear(dirp) \
1290 #define fts_opendir(file, Pdir_fd) \
1291 opendirat((! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
1292 ? sp->fts_cwd_fd : AT_FDCWD), \
1294 (((ISSET(FTS_PHYSICAL) \
1295 && ! (ISSET(FTS_COMFOLLOW) \
1296 && cur->fts_level == FTS_ROOTLEVEL)) \
1298 | (ISSET (FTS_NOATIME) ? O_NOATIME : 0)), \
1302 * This is the tricky part -- do not casually change *anything* in here. The
1303 * idea is to build the linked list of entries that are used by fts_children
1304 * and fts_read. There are lots of special cases.
1306 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
1307 * set and it's a physical walk (so that symbolic links can't be directories),
1308 * we can do things quickly. First, if it's a 4.4BSD file system, the type
1309 * of the file is in the directory entry. Otherwise, we assume that the number
1310 * of subdirectories in a node is equal to the number of links to the parent.
1311 * The former skips all stat calls. The latter skips stat calls in any leaf
1312 * directories and for any files after the subdirectories in the directory have
1313 * been found, cutting the stat calls by about 2/3.
1317 fts_build (register FTS
*sp
, int type
)
1319 register FTSENT
*p
, *head
;
1320 register size_t nitems
;
1327 size_t len
, maxlen
, new_len
;
1330 FTSENT
*cur
= sp
->fts_cur
;
1331 bool continue_readdir
= !!cur
->fts_dirp
;
1334 /* When cur->fts_dirp is non-NULL, that means we should
1335 continue calling readdir on that existing DIR* pointer
1336 rather than opening a new one. */
1337 if (continue_readdir
)
1339 DIR *dp
= cur
->fts_dirp
;
1340 dir_fd
= dirfd (dp
);
1343 closedir_and_clear (cur
->fts_dirp
);
1346 cur
->fts_info
= FTS_DNR
;
1347 cur
->fts_errno
= errno
;
1354 /* Open the directory for reading. If this fails, we're done.
1355 If being called from fts_read, set the fts_info field. */
1356 if ((cur
->fts_dirp
= fts_opendir(cur
->fts_accpath
, &dir_fd
)) == NULL
)
1360 cur
->fts_info
= FTS_DNR
;
1361 cur
->fts_errno
= errno
;
1365 /* Rather than calling fts_stat for each and every entry encountered
1366 in the readdir loop (below), stat each directory only right after
1368 if (cur
->fts_info
== FTS_NSOK
)
1369 cur
->fts_info
= fts_stat(sp
, cur
, false);
1370 else if (sp
->fts_options
& FTS_TIGHT_CYCLE_CHECK
)
1372 /* Now read the stat info again after opening a directory to
1373 reveal eventual changes caused by a submount triggered by
1374 the traversal. But do it only for utilities which use
1375 FTS_TIGHT_CYCLE_CHECK. Therefore, only find and du
1376 benefit/suffer from this feature for now. */
1377 LEAVE_DIR (sp
, cur
, "4");
1378 fts_stat (sp
, cur
, false);
1379 if (! enter_dir (sp
, cur
))
1381 __set_errno (ENOMEM
);
1387 /* Maximum number of readdir entries to read at one time. This
1388 limitation is to avoid reading millions of entries into memory
1389 at once. When an fts_compar function is specified, we have no
1390 choice: we must read all entries into memory before calling that
1391 function. But when no such function is specified, we can read
1392 entries in batches that are large enough to help us with inode-
1393 sorting, yet not so large that we risk exhausting memory. */
1394 max_entries
= sp
->fts_compar
? SIZE_MAX
: FTS_MAX_READDIR_ENTRIES
;
1397 * If we're going to need to stat anything or we want to descend
1398 * and stay in the directory, chdir. If this fails we keep going,
1399 * but set a flag so we don't chdir after the post-order visit.
1400 * We won't be able to stat anything, but we can still return the
1401 * names themselves. Note, that since fts_read won't be able to
1402 * chdir into the directory, it will have to return different file
1403 * names than before, i.e. "a/b" instead of "b". Since the node
1404 * has already been visited in pre-order, have to wait until the
1405 * post-order visit to return the error. There is a special case
1406 * here, if there was nothing to stat then it's not an error to
1407 * not be able to stat. This is all fairly nasty. If a program
1408 * needed sorted entries or stat information, they had better be
1409 * checking FTS_NS on the returned nodes.
1411 if (continue_readdir
)
1413 /* When resuming a short readdir run, we already have
1414 the required dirp and dir_fd. */
1419 /* Try to descend unless it is a names-only fts_children,
1420 or the directory is known to lack subdirectories. */
1421 descend
= (type
!= BNAMES
1422 && ! (ISSET (FTS_NOSTAT
) && ISSET (FTS_PHYSICAL
)
1423 && ! ISSET (FTS_SEEDOT
)
1424 && cur
->fts_statp
->st_nlink
== MIN_DIR_NLINK
1425 && (leaf_optimization (cur
)
1426 != NO_LEAF_OPTIMIZATION
)));
1427 if (descend
|| type
== BREAD
)
1429 if (ISSET(FTS_CWDFD
))
1430 dir_fd
= fcntl (dir_fd
, F_DUPFD_CLOEXEC
, STDERR_FILENO
+ 1);
1431 if (dir_fd
< 0 || fts_safe_changedir(sp
, cur
, dir_fd
, NULL
)) {
1432 if (descend
&& type
== BREAD
)
1433 cur
->fts_errno
= errno
;
1434 cur
->fts_flags
|= FTS_DONTCHDIR
;
1436 closedir_and_clear(cur
->fts_dirp
);
1437 if (ISSET(FTS_CWDFD
) && 0 <= dir_fd
)
1439 cur
->fts_dirp
= NULL
;
1446 * Figure out the max file name length that can be stored in the
1447 * current buffer -- the inner loop allocates more space as necessary.
1448 * We really wouldn't have to do the maxlen calculations here, we
1449 * could do them in fts_read before returning the name, but it's a
1450 * lot easier here since the length is part of the dirent structure.
1452 * If not changing directories set a pointer so that can just append
1453 * each new component into the file name.
1456 if (ISSET(FTS_NOCHDIR
)) {
1457 cp
= sp
->fts_path
+ len
;
1460 /* GCC, you're too verbose. */
1464 maxlen
= sp
->fts_pathlen
- len
;
1466 level
= cur
->fts_level
+ 1;
1468 /* Read the directory, attaching each entry to the "link" pointer. */
1473 while (cur
->fts_dirp
) {
1476 struct dirent
*dp
= readdir(cur
->fts_dirp
);
1479 cur
->fts_errno
= errno
;
1480 /* If we've not read any items yet, treat
1481 the error as if we can't access the dir. */
1482 cur
->fts_info
= (continue_readdir
|| nitems
)
1483 ? FTS_ERR
: FTS_DNR
;
1487 if (!ISSET(FTS_SEEDOT
) && ISDOT(dp
->d_name
))
1490 d_namelen
= _D_EXACT_NAMLEN (dp
);
1491 p
= fts_alloc (sp
, dp
->d_name
, d_namelen
);
1494 if (d_namelen
>= maxlen
) {
1495 /* include space for NUL */
1496 oldaddr
= sp
->fts_path
;
1497 if (! fts_palloc(sp
, d_namelen
+ len
+ 1)) {
1499 * No more memory. Save
1500 * errno, free up the current structure and the
1501 * structures already allocated.
1503 mem1
: saved_errno
= errno
;
1506 closedir_and_clear(cur
->fts_dirp
);
1507 cur
->fts_info
= FTS_ERR
;
1509 __set_errno (saved_errno
);
1512 /* Did realloc() change the pointer? */
1513 if (oldaddr
!= sp
->fts_path
) {
1515 if (ISSET(FTS_NOCHDIR
))
1516 cp
= sp
->fts_path
+ len
;
1518 maxlen
= sp
->fts_pathlen
- len
;
1521 new_len
= len
+ d_namelen
;
1522 if (new_len
< len
) {
1524 * In the unlikely event that we would end up
1525 * with a file name longer than SIZE_MAX, free up
1526 * the current structure and the structures already
1527 * allocated, then error out with ENAMETOOLONG.
1531 closedir_and_clear(cur
->fts_dirp
);
1532 cur
->fts_info
= FTS_ERR
;
1534 __set_errno (ENAMETOOLONG
);
1537 p
->fts_level
= level
;
1538 p
->fts_parent
= sp
->fts_cur
;
1539 p
->fts_pathlen
= new_len
;
1541 /* Store dirent.d_ino, in case we need to sort
1542 entries before processing them. */
1543 p
->fts_statp
->st_ino
= D_INO (dp
);
1545 /* Build a file name for fts_stat to stat. */
1546 if (ISSET(FTS_NOCHDIR
)) {
1547 p
->fts_accpath
= p
->fts_path
;
1548 memmove(cp
, p
->fts_name
, p
->fts_namelen
+ 1);
1550 p
->fts_accpath
= p
->fts_name
;
1552 if (sp
->fts_compar
== NULL
|| ISSET(FTS_DEFER_STAT
)) {
1553 /* Record what fts_read will have to do with this
1554 entry. In many cases, it will simply fts_stat it,
1555 but we can take advantage of any d_type information
1556 to optimize away the unnecessary stat calls. I.e.,
1557 if FTS_NOSTAT is in effect and we're not following
1558 symlinks (FTS_PHYSICAL) and d_type indicates this
1559 is *not* a directory, then we won't have to stat it
1560 at all. If it *is* a directory, then (currently)
1561 we stat it regardless, in order to get device and
1562 inode numbers. Some day we might optimize that
1563 away, too, for directories where d_ino is known to
1565 bool skip_stat
= (ISSET(FTS_PHYSICAL
)
1566 && ISSET(FTS_NOSTAT
)
1568 && ! DT_MUST_BE(dp
, DT_DIR
));
1569 p
->fts_info
= FTS_NSOK
;
1570 /* Propagate dirent.d_type information back
1571 to caller, when possible. */
1572 set_stat_type (p
->fts_statp
, D_TYPE (dp
));
1573 fts_set_stat_required(p
, !skip_stat
);
1575 p
->fts_info
= fts_stat(sp
, p
, false);
1578 /* We walk in directory order so "ls -f" doesn't get upset. */
1587 if (max_entries
<= nitems
) {
1588 /* When there are too many dir entries, leave
1589 fts_dirp open, so that a subsequent fts_read
1590 can take up where we leave off. */
1591 goto break_without_closedir
;
1596 closedir_and_clear(cur
->fts_dirp
);
1598 break_without_closedir
:
1601 * If realloc() changed the address of the file name, adjust the
1602 * addresses for the rest of the tree and the dir list.
1605 fts_padjust(sp
, head
);
1608 * If not changing directories, reset the file name back to original
1611 if (ISSET(FTS_NOCHDIR
)) {
1612 if (len
== sp
->fts_pathlen
|| nitems
== 0)
1618 * If descended after called from fts_children or after called from
1619 * fts_read and nothing found, get back. At the root level we use
1620 * the saved fd; if one of fts_open()'s arguments is a relative name
1621 * to an empty directory, we wind up here with no other way back. If
1622 * can't get back, we're done.
1624 if (!continue_readdir
&& descend
&& (type
== BCHILD
|| !nitems
) &&
1625 (cur
->fts_level
== FTS_ROOTLEVEL
1626 ? restore_initial_cwd(sp
)
1627 : fts_safe_changedir(sp
, cur
->fts_parent
, -1, ".."))) {
1628 cur
->fts_info
= FTS_ERR
;
1634 /* If didn't find anything, return NULL. */
1637 && cur
->fts_info
!= FTS_DNR
&& cur
->fts_info
!= FTS_ERR
)
1638 cur
->fts_info
= FTS_DP
;
1643 /* If there are many entries, no sorting function has been specified,
1644 and this file system is of a type that may be slow with a large
1645 number of entries, then sort the directory entries on increasing
1647 if (nitems
> _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
1649 && dirent_inode_sort_may_be_useful (cur
)) {
1650 sp
->fts_compar
= fts_compare_ino
;
1651 head
= fts_sort (sp
, head
, nitems
);
1652 sp
->fts_compar
= NULL
;
1655 /* Sort the entries. */
1656 if (sp
->fts_compar
&& nitems
> 1)
1657 head
= fts_sort(sp
, head
, nitems
);
1663 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1664 current hierarchy. There should be a directory with dev/inode
1665 matching those of AD. If not, print a lot of diagnostics. */
1667 find_matching_ancestor (FTSENT
const *e_curr
, struct Active_dir
const *ad
)
1670 for (ent
= e_curr
; ent
->fts_level
>= FTS_ROOTLEVEL
; ent
= ent
->fts_parent
)
1672 if (ad
->ino
== ent
->fts_statp
->st_ino
1673 && ad
->dev
== ent
->fts_statp
->st_dev
)
1676 printf ("ERROR: tree dir, %s, not active\n", ad
->fts_ent
->fts_accpath
);
1677 printf ("active dirs:\n");
1679 ent
->fts_level
>= FTS_ROOTLEVEL
; ent
= ent
->fts_parent
)
1680 printf (" %s(%"PRIuMAX
"/%"PRIuMAX
") to %s(%"PRIuMAX
"/%"PRIuMAX
")...\n",
1681 ad
->fts_ent
->fts_accpath
,
1682 (uintmax_t) ad
->dev
,
1683 (uintmax_t) ad
->ino
,
1685 (uintmax_t) ent
->fts_statp
->st_dev
,
1686 (uintmax_t) ent
->fts_statp
->st_ino
);
1690 fts_cross_check (FTS
const *sp
)
1692 FTSENT
const *ent
= sp
->fts_cur
;
1694 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK
))
1697 Dprintf (("fts-cross-check cur=%s\n", ent
->fts_path
));
1698 /* Make sure every parent dir is in the tree. */
1699 for (t
= ent
->fts_parent
; t
->fts_level
>= FTS_ROOTLEVEL
; t
= t
->fts_parent
)
1701 struct Active_dir ad
;
1702 ad
.ino
= t
->fts_statp
->st_ino
;
1703 ad
.dev
= t
->fts_statp
->st_dev
;
1704 if ( ! hash_lookup (sp
->fts_cycle
.ht
, &ad
))
1705 printf ("ERROR: active dir, %s, not in tree\n", t
->fts_path
);
1708 /* Make sure every dir in the tree is an active dir.
1709 But ENT is not necessarily a directory. If so, just skip this part. */
1710 if (ent
->fts_parent
->fts_level
>= FTS_ROOTLEVEL
1711 && (ent
->fts_info
== FTS_DP
1712 || ent
->fts_info
== FTS_D
))
1714 struct Active_dir
*ad
;
1715 for (ad
= hash_get_first (sp
->fts_cycle
.ht
); ad
!= NULL
;
1716 ad
= hash_get_next (sp
->fts_cycle
.ht
, ad
))
1718 find_matching_ancestor (ent
, ad
);
1724 same_fd (int fd1
, int fd2
)
1726 struct stat sb1
, sb2
;
1727 return (fstat (fd1
, &sb1
) == 0
1728 && fstat (fd2
, &sb2
) == 0
1729 && SAME_INODE (sb1
, sb2
));
1733 fd_ring_print (FTS
const *sp
, FILE *stream
, char const *msg
)
1735 I_ring
const *fd_ring
= &sp
->fts_fd_ring
;
1736 unsigned int i
= fd_ring
->fts_front
;
1737 char *cwd
= getcwdat (sp
->fts_cwd_fd
, NULL
, 0);
1738 fprintf (stream
, "=== %s ========== %s\n", msg
, cwd
);
1740 if (i_ring_empty (fd_ring
))
1745 int fd
= fd_ring
->fts_fd_ring
[i
];
1747 fprintf (stream
, "%d: %d:\n", i
, fd
);
1750 char *wd
= getcwdat (fd
, NULL
, 0);
1751 fprintf (stream
, "%d: %d: %s\n", i
, fd
, wd
);
1754 if (i
== fd_ring
->fts_back
)
1756 i
= (i
+ I_RING_SIZE
- 1) % I_RING_SIZE
;
1760 /* Ensure that each file descriptor on the fd_ring matches a
1761 parent, grandparent, etc. of the current working directory. */
1763 fd_ring_check (FTS
const *sp
)
1768 /* Make a writable copy. */
1769 I_ring fd_w
= sp
->fts_fd_ring
;
1771 int cwd_fd
= sp
->fts_cwd_fd
;
1772 cwd_fd
= fcntl (cwd_fd
, F_DUPFD_CLOEXEC
, STDERR_FILENO
+ 1);
1773 char *dot
= getcwdat (cwd_fd
, NULL
, 0);
1774 error (0, 0, "===== check ===== cwd: %s", dot
);
1776 while ( ! i_ring_empty (&fd_w
))
1778 int fd
= i_ring_pop (&fd_w
);
1781 int open_flags
= O_SEARCH
| O_CLOEXEC
| O_NOATIME
;
1782 int parent_fd
= openat (cwd_fd
, "..", open_flags
);
1788 if (!same_fd (fd
, parent_fd
))
1790 char *cwd
= getcwdat (fd
, NULL
, 0);
1791 error (0, errno
, "ring : %s", cwd
);
1792 char *c2
= getcwdat (parent_fd
, NULL
, 0);
1793 error (0, errno
, "parent: %s", c2
);
1806 static unsigned short int
1808 fts_stat(FTS
*sp
, register FTSENT
*p
, bool follow
)
1810 struct stat
*sbp
= p
->fts_statp
;
1812 if (p
->fts_level
== FTS_ROOTLEVEL
&& ISSET(FTS_COMFOLLOW
))
1816 * If doing a logical walk, or application requested FTS_FOLLOW, do
1817 * a stat(2). If that fails, check for a non-existent symlink. If
1818 * fail, set the errno from the stat call.
1820 if (ISSET(FTS_LOGICAL
) || follow
) {
1821 if (stat(p
->fts_accpath
, sbp
)) {
1823 && lstat(p
->fts_accpath
, sbp
) == 0) {
1825 return (FTS_SLNONE
);
1827 p
->fts_errno
= errno
;
1830 } else if (fstatat(sp
->fts_cwd_fd
, p
->fts_accpath
, sbp
,
1831 AT_SYMLINK_NOFOLLOW
)) {
1832 p
->fts_errno
= errno
;
1833 err
: memset(sbp
, 0, sizeof(struct stat
));
1837 if (S_ISDIR(sbp
->st_mode
)) {
1838 p
->fts_n_dirs_remaining
1839 = ((sbp
->st_nlink
< MIN_DIR_NLINK
1840 || p
->fts_level
<= FTS_ROOTLEVEL
)
1842 : sbp
->st_nlink
- (ISSET (FTS_SEEDOT
) ? 0 : MIN_DIR_NLINK
));
1843 if (ISDOT(p
->fts_name
)) {
1844 /* Command-line "." and ".." are real directories. */
1845 return (p
->fts_level
== FTS_ROOTLEVEL
? FTS_D
: FTS_DOT
);
1850 if (S_ISLNK(sbp
->st_mode
))
1852 if (S_ISREG(sbp
->st_mode
))
1854 return (FTS_DEFAULT
);
1858 fts_compar (void const *a
, void const *b
)
1860 /* Convert A and B to the correct types, to pacify the compiler, and
1861 for portability to bizarre hosts where "void const *" and "FTSENT
1862 const **" differ in runtime representation. The comparison
1863 function cannot modify *a and *b, but there is no compile-time
1865 FTSENT
const **pa
= (FTSENT
const **) a
;
1866 FTSENT
const **pb
= (FTSENT
const **) b
;
1867 return pa
[0]->fts_fts
->fts_compar (pa
, pb
);
1872 fts_sort (FTS
*sp
, FTSENT
*head
, register size_t nitems
)
1874 register FTSENT
**ap
, *p
;
1876 /* On most modern hosts, void * and FTSENT ** have the same
1877 run-time representation, and one can convert sp->fts_compar to
1878 the type qsort expects without problem. Use the heuristic that
1879 this is OK if the two pointer types are the same size, and if
1880 converting FTSENT ** to long int is the same as converting
1881 FTSENT ** to void * and then to long int. This heuristic isn't
1882 valid in general but we don't know of any counterexamples. */
1884 int (*compare
) (void const *, void const *) =
1885 ((sizeof &dummy
== sizeof (void *)
1886 && (long int) &dummy
== (long int) (void *) &dummy
)
1887 ? (int (*) (void const *, void const *)) sp
->fts_compar
1891 * Construct an array of pointers to the structures and call qsort(3).
1892 * Reassemble the array in the order returned by qsort. If unable to
1893 * sort for memory reasons, return the directory entries in their
1894 * current order. Allocate enough space for the current needs plus
1895 * 40 so don't realloc one entry at a time.
1897 if (nitems
> sp
->fts_nitems
) {
1900 sp
->fts_nitems
= nitems
+ 40;
1901 if (SIZE_MAX
/ sizeof *a
< sp
->fts_nitems
1902 || ! (a
= realloc (sp
->fts_array
,
1903 sp
->fts_nitems
* sizeof *a
))) {
1904 free(sp
->fts_array
);
1905 sp
->fts_array
= NULL
;
1911 for (ap
= sp
->fts_array
, p
= head
; p
; p
= p
->fts_link
)
1913 qsort((void *)sp
->fts_array
, nitems
, sizeof(FTSENT
*), compare
);
1914 for (head
= *(ap
= sp
->fts_array
); --nitems
; ++ap
)
1915 ap
[0]->fts_link
= ap
[1];
1916 ap
[0]->fts_link
= NULL
;
1922 fts_alloc (FTS
*sp
, const char *name
, register size_t namelen
)
1928 * The file name is a variable length array. Allocate the FTSENT
1929 * structure and the file name in one chunk.
1931 len
= FLEXSIZEOF(FTSENT
, fts_name
, namelen
+ 1);
1932 if ((p
= malloc(len
)) == NULL
)
1935 /* Copy the name and guarantee NUL termination. */
1936 memcpy(p
->fts_name
, name
, namelen
);
1937 p
->fts_name
[namelen
] = '\0';
1939 p
->fts_namelen
= namelen
;
1941 p
->fts_path
= sp
->fts_path
;
1945 p
->fts_instr
= FTS_NOINSTR
;
1947 p
->fts_pointer
= NULL
;
1953 fts_lfree (register FTSENT
*head
)
1957 /* Free a linked list of structures. */
1958 while ((p
= head
)) {
1959 head
= head
->fts_link
;
1961 closedir (p
->fts_dirp
);
1967 * Allow essentially unlimited file name lengths; find, rm, ls should
1968 * all work on any tree. Most systems will allow creation of file
1969 * names much longer than MAXPATHLEN, even though the kernel won't
1970 * resolve them. Add the size (not just what's needed) plus 256 bytes
1971 * so don't realloc the file name 2 bytes at a time.
1975 fts_palloc (FTS
*sp
, size_t more
)
1978 size_t new_len
= sp
->fts_pathlen
+ more
+ 256;
1981 * See if fts_pathlen would overflow.
1983 if (new_len
< sp
->fts_pathlen
) {
1985 sp
->fts_path
= NULL
;
1986 __set_errno (ENAMETOOLONG
);
1989 sp
->fts_pathlen
= new_len
;
1990 p
= realloc(sp
->fts_path
, sp
->fts_pathlen
);
1993 sp
->fts_path
= NULL
;
2001 * When the file name is realloc'd, have to fix all of the pointers in
2002 * structures already returned.
2006 fts_padjust (FTS
*sp
, FTSENT
*head
)
2009 char *addr
= sp
->fts_path
;
2011 #define ADJUST(p) do { \
2012 if ((p)->fts_accpath != (p)->fts_name) { \
2013 (p)->fts_accpath = \
2014 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
2016 (p)->fts_path = addr; \
2018 /* Adjust the current set of children. */
2019 for (p
= sp
->fts_child
; p
; p
= p
->fts_link
)
2022 /* Adjust the rest of the tree, including the current level. */
2023 for (p
= head
; p
->fts_level
>= FTS_ROOTLEVEL
;) {
2025 p
= p
->fts_link
? p
->fts_link
: p
->fts_parent
;
2030 internal_function _GL_ATTRIBUTE_PURE
2031 fts_maxarglen (char * const *argv
)
2035 for (max
= 0; *argv
; ++argv
)
2036 if ((len
= strlen(*argv
)) > max
)
2042 * Change to dir specified by fd or file name without getting
2043 * tricked by someone changing the world out from underneath us.
2044 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
2045 * If FD is non-negative, expect it to be used after this function returns,
2046 * and to be closed eventually. So don't pass e.g., 'dirfd(dirp)' and then
2047 * do closedir(dirp), because that would invalidate the saved FD.
2048 * Upon failure, close FD immediately and return nonzero.
2052 fts_safe_changedir (FTS
*sp
, FTSENT
*p
, int fd
, char const *dir
)
2055 bool is_dotdot
= dir
&& STREQ (dir
, "..");
2058 /* This clause handles the unusual case in which FTS_NOCHDIR
2059 is specified, along with FTS_CWDFD. In that case, there is
2060 no need to change even the virtual cwd file descriptor.
2061 However, if FD is non-negative, we do close it here. */
2062 if (ISSET (FTS_NOCHDIR
))
2064 if (ISSET (FTS_CWDFD
) && 0 <= fd
)
2069 if (fd
< 0 && is_dotdot
&& ISSET (FTS_CWDFD
))
2071 /* When possible, skip the diropen and subsequent fstat+dev/ino
2072 comparison. I.e., when changing to parent directory
2073 (chdir ("..")), use a file descriptor from the ring and
2074 save the overhead of diropen+fstat, as well as avoiding
2075 failure when we lack "x" access to the virtual cwd. */
2076 if ( ! i_ring_empty (&sp
->fts_fd_ring
))
2079 fd_ring_print (sp
, stderr
, "pre-pop");
2080 parent_fd
= i_ring_pop (&sp
->fts_fd_ring
);
2091 if (fd
< 0 && (newfd
= diropen (sp
, dir
)) < 0)
2094 /* The following dev/inode check is necessary if we're doing a
2095 "logical" traversal (through symlinks, a la chown -L), if the
2096 system lacks O_NOFOLLOW support, or if we're changing to ".."
2097 (but not via a popped file descriptor). When changing to the
2098 name "..", O_NOFOLLOW can't help. In general, when the target is
2099 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
2100 follow a symlink, so we can avoid the expense of this fstat. */
2101 if (ISSET(FTS_LOGICAL
) || ! HAVE_WORKING_O_NOFOLLOW
2102 || (dir
&& STREQ (dir
, "..")))
2105 if (fstat(newfd
, &sb
))
2110 if (p
->fts_statp
->st_dev
!= sb
.st_dev
2111 || p
->fts_statp
->st_ino
!= sb
.st_ino
)
2113 __set_errno (ENOENT
); /* disinformation */
2119 if (ISSET(FTS_CWDFD
))
2121 cwd_advance_fd (sp
, newfd
, ! is_dotdot
);
2125 ret
= fchdir(newfd
);
2131 __set_errno (oerrno
);