1 /* Traverse a file hierarchy.
3 Copyright (C) 2004-2020 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 "opendirat.h"
77 # include "same-inode.h"
81 #ifndef _D_EXACT_NAMLEN
82 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
85 #if HAVE_STRUCT_DIRENT_D_TYPE
86 /* True if the type of the directory entry D is known. */
87 # define DT_IS_KNOWN(d) ((d)->d_type != DT_UNKNOWN)
88 /* True if the type of the directory entry D must be T. */
89 # define DT_MUST_BE(d, t) ((d)->d_type == (t))
90 # define D_TYPE(d) ((d)->d_type)
92 # define DT_IS_KNOWN(d) false
93 # define DT_MUST_BE(d, t) false
94 # define D_TYPE(d) DT_UNKNOWN
99 /* Any nonzero values will do here, so long as they're distinct.
100 Undef any existing macros out of the way. */
126 NOT_AN_INODE_NUMBER
= 0
129 #ifdef D_INO_IN_DIRENT
130 # define D_INO(dp) (dp)->d_ino
132 /* Some systems don't have inodes, so fake them to avoid lots of ifdefs. */
133 # define D_INO(dp) NOT_AN_INODE_NUMBER
136 /* If possible (see max_entries, below), read no more than this many directory
137 entries at a time. Without this limit (i.e., when using non-NULL
138 fts_compar), processing a directory with 4,000,000 entries requires ~1GiB
139 of memory, and handling 64M entries would require 16GiB of memory. */
140 #ifndef FTS_MAX_READDIR_ENTRIES
141 # define FTS_MAX_READDIR_ENTRIES 100000
144 /* If there are more than this many entries in a directory,
145 and the conditions mentioned below are satisfied, then sort
146 the entries on inode number before any further processing. */
147 #ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
148 # define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000
153 _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
= FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
158 FTS_NO_STAT_REQUIRED
= 1,
159 FTS_STAT_REQUIRED
= 2
164 # define close __close
166 # define closedir __closedir
168 # define fchdir __fchdir
172 # define readdir __readdir
174 # undef internal_function
175 # define internal_function /* empty */
179 # define __set_errno(Val) errno = (Val)
182 /* If this host provides the openat function, then we can avoid
183 attempting to open "." in some initialization code below. */
185 # define HAVE_OPENAT_SUPPORT 1
187 # define HAVE_OPENAT_SUPPORT 0
191 # define fts_assert(expr) ((void) (0 && (expr)))
193 # define fts_assert(expr) \
204 # define FALLTHROUGH ((void) 0)
206 # define FALLTHROUGH __attribute__ ((__fallthrough__))
210 static FTSENT
*fts_alloc (FTS
*, const char *, size_t) internal_function
;
211 static FTSENT
*fts_build (FTS
*, int) internal_function
;
212 static void fts_lfree (FTSENT
*) internal_function
;
213 static void fts_load (FTS
*, FTSENT
*) internal_function
;
214 static size_t fts_maxarglen (char * const *) internal_function
;
215 static void fts_padjust (FTS
*, FTSENT
*) internal_function
;
216 static bool fts_palloc (FTS
*, size_t) internal_function
;
217 static FTSENT
*fts_sort (FTS
*, FTSENT
*, size_t) internal_function
;
218 static unsigned short int fts_stat (FTS
*, FTSENT
*, bool) internal_function
;
219 static int fts_safe_changedir (FTS
*, FTSENT
*, int, const char *)
222 #include "fts-cycle.c"
225 # define MAX(a,b) ((a) > (b) ? (a) : (b))
229 # define SIZE_MAX ((size_t) -1)
232 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
233 #define STREQ(a, b) (strcmp (a, b) == 0)
235 #define CLR(opt) (sp->fts_options &= ~(opt))
236 #define ISSET(opt) (sp->fts_options & (opt))
237 #define SET(opt) (sp->fts_options |= (opt))
239 /* FIXME: FTS_NOCHDIR is now misnamed.
240 Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
241 #define FCHDIR(sp, fd) \
242 (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \
243 ? (cwd_advance_fd ((sp), (fd), true), 0) \
247 /* fts_build flags */
248 /* FIXME: make this an enum */
249 #define BCHILD 1 /* fts_children */
250 #define BNAMES 2 /* fts_children, names only */
251 #define BREAD 3 /* fts_read */
254 # include <inttypes.h>
257 # include "getcwdat.h"
258 bool fts_debug
= false;
259 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
262 # define fd_ring_check(x)
263 # define fd_ring_print(a, b, c)
266 #define LEAVE_DIR(Fts, Ent, Tag) \
269 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
270 leave_dir (Fts, Ent); \
271 fd_ring_check (Fts); \
276 fd_ring_clear (I_ring
*fd_ring
)
278 while ( ! i_ring_empty (fd_ring
))
280 int fd
= i_ring_pop (fd_ring
);
286 /* Overload the fts_statp->st_size member (otherwise unused, when
287 fts_info is FTS_NSOK) to indicate whether fts_read should stat
288 this entry or not. */
290 fts_set_stat_required (FTSENT
*p
, bool required
)
292 fts_assert (p
->fts_info
== FTS_NSOK
);
293 p
->fts_statp
->st_size
= (required
295 : FTS_NO_STAT_REQUIRED
);
298 /* Virtual fchdir. Advance SP's working directory file descriptor,
299 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
300 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
301 open on sp->fts_cwd_fd; i.e., to move the working directory one level
305 cwd_advance_fd (FTS
*sp
, int fd
, bool chdir_down_one
)
307 int old
= sp
->fts_cwd_fd
;
308 fts_assert (old
!= fd
|| old
== AT_FDCWD
);
312 /* Push "old" onto the ring.
313 If the displaced file descriptor is non-negative, close it. */
314 int prev_fd_in_slot
= i_ring_push (&sp
->fts_fd_ring
, old
);
315 fd_ring_print (sp
, stderr
, "post-push");
316 if (0 <= prev_fd_in_slot
)
317 close (prev_fd_in_slot
); /* ignore any close failure */
319 else if ( ! ISSET (FTS_NOCHDIR
))
322 close (old
); /* ignore any close failure */
328 /* Restore the initial, pre-traversal, "working directory".
329 In FTS_CWDFD mode, we merely call cwd_advance_fd, otherwise,
330 we may actually change the working directory.
331 Return 0 upon success. Upon failure, set errno and return nonzero. */
333 restore_initial_cwd (FTS
*sp
)
335 int fail
= FCHDIR (sp
, ISSET (FTS_CWDFD
) ? AT_FDCWD
: sp
->fts_rfd
);
336 fd_ring_clear (&(sp
->fts_fd_ring
));
340 /* Open the directory DIR if possible, and return a file
341 descriptor. Return -1 and set errno on failure. It doesn't matter
342 whether the file descriptor has read or write access. */
346 diropen (FTS
const *sp
, char const *dir
)
348 int open_flags
= (O_SEARCH
| O_CLOEXEC
| O_DIRECTORY
| O_NOCTTY
| O_NONBLOCK
349 | (ISSET (FTS_PHYSICAL
) ? O_NOFOLLOW
: 0));
351 int fd
= (ISSET (FTS_CWDFD
)
352 ? openat (sp
->fts_cwd_fd
, dir
, open_flags
)
353 : open (dir
, open_flags
));
358 fts_open (char * const *argv
,
359 register int options
,
360 int (*compar
) (FTSENT
const **, FTSENT
const **))
363 register FTSENT
*p
, *root
;
364 register size_t nitems
;
365 FTSENT
*parent
= NULL
;
366 FTSENT
*tmp
= NULL
; /* pacify gcc */
370 if (options
& ~FTS_OPTIONMASK
) {
371 __set_errno (EINVAL
);
374 if ((options
& FTS_NOCHDIR
) && (options
& FTS_CWDFD
)) {
375 __set_errno (EINVAL
);
378 if ( ! (options
& (FTS_LOGICAL
| FTS_PHYSICAL
))) {
379 __set_errno (EINVAL
);
383 /* Allocate/initialize the stream */
384 sp
= calloc (1, sizeof *sp
);
387 sp
->fts_compar
= compar
;
388 sp
->fts_options
= options
;
390 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
391 if (ISSET(FTS_LOGICAL
)) {
396 /* Initialize fts_cwd_fd. */
397 sp
->fts_cwd_fd
= AT_FDCWD
;
398 if ( ISSET(FTS_CWDFD
) && ! HAVE_OPENAT_SUPPORT
)
400 /* While it isn't technically necessary to open "." this
401 early, doing it here saves us the trouble of ensuring
402 later (where it'd be messier) that "." can in fact
403 be opened. If not, revert to FTS_NOCHDIR mode. */
404 int fd
= open (".", O_SEARCH
);
407 /* Even if "." is unreadable, don't revert to FTS_NOCHDIR mode
408 on systems like Linux+PROC_FS, where our openat emulation
409 is good enough. Note: on a system that emulates
410 openat via /proc, this technique can still fail, but
411 only in extreme conditions, e.g., when the working
412 directory cannot be saved (i.e. save_cwd fails) --
413 and that happens on Linux only when "." is unreadable
414 and the CWD would be longer than PATH_MAX.
415 FIXME: once Linux kernel openat support is well established,
416 replace the above open call and this entire if/else block
417 with the body of the if-block below. */
418 if ( openat_needs_fchdir ())
431 * Start out with 1K of file name space, and enough, in any case,
432 * to hold the user's file names.
435 # define MAXPATHLEN 1024
438 size_t maxarglen
= fts_maxarglen(argv
);
439 if (! fts_palloc(sp
, MAX(maxarglen
, MAXPATHLEN
)))
443 /* Allocate/initialize root's parent. */
445 if ((parent
= fts_alloc(sp
, "", 0)) == NULL
)
447 parent
->fts_level
= FTS_ROOTPARENTLEVEL
;
448 parent
->fts_n_dirs_remaining
= -1;
451 /* The classic fts implementation would call fts_stat with
452 a new entry for each iteration of the loop below.
453 If the comparison function is not specified or if the
454 FTS_DEFER_STAT option is in effect, don't stat any entry
455 in this loop. This is an attempt to minimize the interval
456 between the initial stat/lstat/fstatat and the point at which
457 a directory argument is first opened. This matters for any
458 directory command line argument that resides on a file system
459 without genuine i-nodes. If you specify FTS_DEFER_STAT along
460 with a comparison function, that function must not access any
461 data via the fts_statp pointer. */
462 defer_stat
= (compar
== NULL
|| ISSET(FTS_DEFER_STAT
));
464 /* Allocate/initialize root(s). */
465 for (root
= NULL
, nitems
= 0; *argv
!= NULL
; ++argv
, ++nitems
) {
466 /* *Do* allow zero-length file names. */
467 size_t len
= strlen(*argv
);
469 if ( ! (options
& FTS_VERBATIM
))
471 /* If there are two or more trailing slashes, trim all but one,
472 but don't change "//" to "/", and do map "///" to "/". */
473 char const *v
= *argv
;
474 if (2 < len
&& v
[len
- 1] == '/')
475 while (1 < len
&& v
[len
- 2] == '/')
479 if ((p
= fts_alloc(sp
, *argv
, len
)) == NULL
)
481 p
->fts_level
= FTS_ROOTLEVEL
;
482 p
->fts_parent
= parent
;
483 p
->fts_accpath
= p
->fts_name
;
484 /* Even when defer_stat is true, be sure to stat the first
485 command line argument, since fts_read (at least with
486 FTS_XDEV) requires that. */
487 if (defer_stat
&& root
!= NULL
) {
488 p
->fts_info
= FTS_NSOK
;
489 fts_set_stat_required(p
, true);
491 p
->fts_info
= fts_stat(sp
, p
, false);
495 * If comparison routine supplied, traverse in sorted
496 * order; otherwise traverse in the order specified.
511 if (compar
&& nitems
> 1)
512 root
= fts_sort(sp
, root
, nitems
);
515 * Allocate a dummy pointer and make fts_read think that we've just
516 * finished the node before the root(s); set p->fts_info to FTS_INIT
517 * so that everything about the "current" node is ignored.
519 if ((sp
->fts_cur
= fts_alloc(sp
, "", 0)) == NULL
)
521 sp
->fts_cur
->fts_link
= root
;
522 sp
->fts_cur
->fts_info
= FTS_INIT
;
523 sp
->fts_cur
->fts_level
= 1;
524 if (! setup_dir (sp
))
528 * If using chdir(2), grab a file descriptor pointing to dot to ensure
529 * that we can get back here; this could be avoided for some file names,
530 * but almost certainly not worth the effort. Slashes, symbolic links,
531 * and ".." are all fairly nasty problems. Note, if we can't get the
532 * descriptor we run anyway, just more slowly.
534 if (!ISSET(FTS_NOCHDIR
) && !ISSET(FTS_CWDFD
)
535 && (sp
->fts_rfd
= diropen (sp
, ".")) < 0)
538 i_ring_init (&sp
->fts_fd_ring
, -1);
541 mem3
: fts_lfree(root
);
543 mem2
: free(sp
->fts_path
);
550 fts_load (FTS
*sp
, register FTSENT
*p
)
556 * Load the stream structure for the next traversal. Since we don't
557 * actually enter the directory until after the preorder visit, set
558 * the fts_accpath field specially so the chdir gets done to the right
559 * place and the user can access the first node. From fts_open it's
560 * known that the file name will fit.
562 len
= p
->fts_pathlen
= p
->fts_namelen
;
563 memmove(sp
->fts_path
, p
->fts_name
, len
+ 1);
564 if ((cp
= strrchr(p
->fts_name
, '/')) && (cp
!= p
->fts_name
|| cp
[1])) {
566 memmove(p
->fts_name
, cp
, len
+ 1);
567 p
->fts_namelen
= len
;
569 p
->fts_accpath
= p
->fts_path
= sp
->fts_path
;
575 register FTSENT
*freep
, *p
;
579 * This still works if we haven't read anything -- the dummy structure
580 * points to the root list, so we step through to the end of the root
581 * list which has a valid parent pointer.
584 for (p
= sp
->fts_cur
; p
->fts_level
>= FTS_ROOTLEVEL
;) {
586 p
= p
->fts_link
!= NULL
? p
->fts_link
: p
->fts_parent
;
592 /* Free up child linked list, sort array, file name buffer. */
594 fts_lfree(sp
->fts_child
);
598 if (ISSET(FTS_CWDFD
))
600 if (0 <= sp
->fts_cwd_fd
)
601 if (close (sp
->fts_cwd_fd
))
604 else if (!ISSET(FTS_NOCHDIR
))
606 /* Return to original directory, save errno if necessary. */
607 if (fchdir(sp
->fts_rfd
))
610 /* If close fails, record errno only if saved_errno is zero,
611 so that we report the probably-more-meaningful fchdir errno. */
612 if (close (sp
->fts_rfd
))
613 if (saved_errno
== 0)
617 fd_ring_clear (&sp
->fts_fd_ring
);
619 if (sp
->fts_leaf_optimization_works_ht
)
620 hash_free (sp
->fts_leaf_optimization_works_ht
);
624 /* Free up the stream pointer. */
627 /* Set errno and return. */
629 __set_errno (saved_errno
);
636 /* Minimum link count of a traditional Unix directory. When leaf
637 optimization is OK and MIN_DIR_NLINK <= st_nlink, then st_nlink is
638 an upper bound on the number of subdirectories (counting "." and
640 enum { MIN_DIR_NLINK
= 2 };
642 /* Whether leaf optimization is OK for a directory. */
643 enum leaf_optimization
645 /* st_nlink is not reliable for this directory's subdirectories. */
646 NO_LEAF_OPTIMIZATION
,
648 /* Leaf optimization is OK, but is not useful for avoiding stat calls. */
649 OK_LEAF_OPTIMIZATION
,
651 /* Leaf optimization is not only OK: it is useful for avoiding
652 stat calls, because dirent.d_type does not work. */
653 NOSTAT_LEAF_OPTIMIZATION
656 #if (defined __linux__ || defined __ANDROID__) \
657 && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
659 # include <sys/vfs.h>
661 /* Linux-specific constants from coreutils' src/fs.h */
662 # define S_MAGIC_AFS 0x5346414F
663 # define S_MAGIC_CIFS 0xFF534D42
664 # define S_MAGIC_NFS 0x6969
665 # define S_MAGIC_PROC 0x9FA0
666 # define S_MAGIC_REISERFS 0x52654973
667 # define S_MAGIC_TMPFS 0x1021994
668 # define S_MAGIC_XFS 0x58465342
670 # ifdef HAVE___FSWORD_T
671 typedef __fsword_t fsword
;
673 typedef long int fsword
;
676 /* Map a stat.st_dev number to a file system type number f_ftype. */
683 /* Use a tiny initial size. If a traversal encounters more than
684 a few devices, the cost of growing/rehashing this table will be
685 rendered negligible by the number of inodes processed. */
686 enum { DEV_TYPE_HT_INITIAL_SIZE
= 13 };
689 dev_type_hash (void const *x
, size_t table_size
)
691 struct dev_type
const *ax
= x
;
692 uintmax_t dev
= ax
->st_dev
;
693 return dev
% table_size
;
697 dev_type_compare (void const *x
, void const *y
)
699 struct dev_type
const *ax
= x
;
700 struct dev_type
const *ay
= y
;
701 return ax
->st_dev
== ay
->st_dev
;
704 /* Return the file system type of P with file descriptor FD, or 0 if not known.
705 If FD is negative, P's file descriptor is unavailable.
706 Try to cache known values. */
709 filesystem_type (FTSENT
const *p
, int fd
)
711 FTS
*sp
= p
->fts_fts
;
712 Hash_table
*h
= sp
->fts_leaf_optimization_works_ht
;
713 struct dev_type
*ent
;
714 struct statfs fs_buf
;
716 /* If we're not in CWDFD mode, don't bother with this optimization,
717 since the caller is not serious about performance. */
718 if (!ISSET (FTS_CWDFD
))
722 h
= sp
->fts_leaf_optimization_works_ht
723 = hash_initialize (DEV_TYPE_HT_INITIAL_SIZE
, NULL
, dev_type_hash
,
724 dev_type_compare
, free
);
728 tmp
.st_dev
= p
->fts_statp
->st_dev
;
729 ent
= hash_lookup (h
, &tmp
);
734 /* Look-up failed. Query directly and cache the result. */
735 if (fd
< 0 || fstatfs (fd
, &fs_buf
) != 0)
740 struct dev_type
*t2
= malloc (sizeof *t2
);
743 t2
->st_dev
= p
->fts_statp
->st_dev
;
744 t2
->f_type
= fs_buf
.f_type
;
746 ent
= hash_insert (h
, t2
);
748 fts_assert (ent
== t2
);
754 return fs_buf
.f_type
;
757 /* Return true if sorting dirents on inode numbers is known to improve
758 traversal performance for the directory P with descriptor DIR_FD.
759 Return false otherwise. When in doubt, return true.
760 DIR_FD is negative if unavailable. */
762 dirent_inode_sort_may_be_useful (FTSENT
const *p
, int dir_fd
)
764 /* Skip the sort only if we can determine efficiently
765 that skipping it is the right thing to do.
766 The cost of performing an unnecessary sort is negligible,
767 while the cost of *not* performing it can be O(N^2) with
768 a very large constant. */
770 switch (filesystem_type (p
, dir_fd
))
775 /* On a file system of any of these types, sorting
776 is unnecessary, and hence wasteful. */
784 /* Given an FTS entry P for a directory with descriptor DIR_FD,
785 return true if it is both useful and valid to apply leaf optimization.
786 The optimization is useful only for file systems that lack usable
787 dirent.d_type info. The optimization is valid if an st_nlink value
788 of at least MIN_DIR_NLINK is an upper bound on the number of
789 subdirectories of D, counting "." and ".." as subdirectories.
790 DIR_FD is negative if unavailable. */
791 static enum leaf_optimization
792 leaf_optimization (FTSENT
const *p
, int dir_fd
)
794 switch (filesystem_type (p
, dir_fd
))
796 /* List here the file system types that may lack usable dirent.d_type
797 info, yet for which the optimization does apply. */
798 case S_MAGIC_REISERFS
:
799 case S_MAGIC_XFS
: /* XFS lacked it until 2013-08-22 commit. */
800 return NOSTAT_LEAF_OPTIMIZATION
;
803 /* Leaf optimization is unsafe if the file system type is unknown. */
806 /* Although AFS mount points are not counted in st_nlink, they
807 act like directories. See <https://bugs.debian.org/143111>. */
810 /* Leaf optimization causes 'find' to abort. See
811 <https://lists.gnu.org/r/bug-gnulib/2018-04/msg00015.html>. */
814 /* NFS provides usable dirent.d_type but not necessarily for all entries
815 of large directories, so as per <https://bugzilla.redhat.com/1252549>
816 NFS should return true. However st_nlink values are not accurate on
817 all implementations as per <https://bugzilla.redhat.com/1299169>. */
820 /* Per <https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=143111> /proc
821 may have bogus stat.st_nlink values. */
822 return NO_LEAF_OPTIMIZATION
;
825 return OK_LEAF_OPTIMIZATION
;
831 dirent_inode_sort_may_be_useful (FTSENT
const *p _GL_UNUSED
,
832 int dir_fd _GL_UNUSED
)
836 static enum leaf_optimization
837 leaf_optimization (FTSENT
const *p _GL_UNUSED
, int dir_fd _GL_UNUSED
)
839 return NO_LEAF_OPTIMIZATION
;
844 * Special case of "/" at the end of the file name so that slashes aren't
845 * appended which would cause file names to be written as "....//foo".
848 (p->fts_path[p->fts_pathlen - 1] == '/' \
849 ? p->fts_pathlen - 1 : p->fts_pathlen)
852 fts_read (register FTS
*sp
)
854 register FTSENT
*p
, *tmp
;
855 register unsigned short int instr
;
858 /* If finished or unrecoverable error, return NULL. */
859 if (sp
->fts_cur
== NULL
|| ISSET(FTS_STOP
))
862 /* Set current node pointer. */
865 /* Save and zero out user instructions. */
866 instr
= p
->fts_instr
;
867 p
->fts_instr
= FTS_NOINSTR
;
869 /* Any type of file may be re-visited; re-stat and re-turn. */
870 if (instr
== FTS_AGAIN
) {
871 p
->fts_info
= fts_stat(sp
, p
, false);
874 Dprintf (("fts_read: p=%s\n",
875 p
->fts_info
== FTS_INIT
? "" : p
->fts_path
));
878 * Following a symlink -- SLNONE test allows application to see
879 * SLNONE and recover. If indirecting through a symlink, have
880 * keep a pointer to current location. If unable to get that
881 * pointer, follow fails.
883 if (instr
== FTS_FOLLOW
&&
884 (p
->fts_info
== FTS_SL
|| p
->fts_info
== FTS_SLNONE
)) {
885 p
->fts_info
= fts_stat(sp
, p
, true);
886 if (p
->fts_info
== FTS_D
&& !ISSET(FTS_NOCHDIR
)) {
887 if ((p
->fts_symfd
= diropen (sp
, ".")) < 0) {
888 p
->fts_errno
= errno
;
889 p
->fts_info
= FTS_ERR
;
891 p
->fts_flags
|= FTS_SYMFOLLOW
;
896 /* Directory in pre-order. */
897 if (p
->fts_info
== FTS_D
) {
898 /* If skipped or crossed mount point, do post-order visit. */
899 if (instr
== FTS_SKIP
||
900 (ISSET(FTS_XDEV
) && p
->fts_statp
->st_dev
!= sp
->fts_dev
)) {
901 if (p
->fts_flags
& FTS_SYMFOLLOW
)
902 (void)close(p
->fts_symfd
);
904 fts_lfree(sp
->fts_child
);
905 sp
->fts_child
= NULL
;
907 p
->fts_info
= FTS_DP
;
908 LEAVE_DIR (sp
, p
, "1");
912 /* Rebuild if only read the names and now traversing. */
913 if (sp
->fts_child
!= NULL
&& ISSET(FTS_NAMEONLY
)) {
915 fts_lfree(sp
->fts_child
);
916 sp
->fts_child
= NULL
;
920 * Cd to the subdirectory.
922 * If have already read and now fail to chdir, whack the list
923 * to make the names come out right, and set the parent errno
924 * so the application will eventually get an error condition.
925 * Set the FTS_DONTCHDIR flag so that when we logically change
926 * directories back to the parent we don't do a chdir.
928 * If haven't read do so. If the read fails, fts_build sets
929 * FTS_STOP or the fts_info field of the node.
931 if (sp
->fts_child
!= NULL
) {
932 if (fts_safe_changedir(sp
, p
, -1, p
->fts_accpath
)) {
933 p
->fts_errno
= errno
;
934 p
->fts_flags
|= FTS_DONTCHDIR
;
935 for (p
= sp
->fts_child
; p
!= NULL
;
938 p
->fts_parent
->fts_accpath
;
940 } else if ((sp
->fts_child
= fts_build(sp
, BREAD
)) == NULL
) {
943 /* If fts_build's call to fts_safe_changedir failed
944 because it was not able to fchdir into a
945 subdirectory, tell the caller. */
946 if (p
->fts_errno
&& p
->fts_info
!= FTS_DNR
)
947 p
->fts_info
= FTS_ERR
;
948 LEAVE_DIR (sp
, p
, "2");
952 sp
->fts_child
= NULL
;
956 /* Move to the next node on this level. */
959 /* If we have so many directory entries that we're reading them
960 in batches, and we've reached the end of the current batch,
961 read in a new batch. */
962 if (p
->fts_link
== NULL
&& p
->fts_parent
->fts_dirp
)
966 sp
->fts_path
[p
->fts_pathlen
] = '\0';
968 if ((p
= fts_build (sp
, BREAD
)) == NULL
)
979 if ((p
= p
->fts_link
) != NULL
) {
984 * If reached the top, return to the original directory (or
985 * the root of the tree), and load the file names for the next
988 if (p
->fts_level
== FTS_ROOTLEVEL
) {
989 if (restore_initial_cwd(sp
)) {
1000 * User may have called fts_set on the node. If skipped,
1001 * ignore. If followed, get a file descriptor so we can
1002 * get back if necessary.
1004 if (p
->fts_instr
== FTS_SKIP
)
1006 if (p
->fts_instr
== FTS_FOLLOW
) {
1007 p
->fts_info
= fts_stat(sp
, p
, true);
1008 if (p
->fts_info
== FTS_D
&& !ISSET(FTS_NOCHDIR
)) {
1009 if ((p
->fts_symfd
= diropen (sp
, ".")) < 0) {
1010 p
->fts_errno
= errno
;
1011 p
->fts_info
= FTS_ERR
;
1013 p
->fts_flags
|= FTS_SYMFOLLOW
;
1015 p
->fts_instr
= FTS_NOINSTR
;
1018 name
: t
= sp
->fts_path
+ NAPPEND(p
->fts_parent
);
1020 memmove(t
, p
->fts_name
, p
->fts_namelen
+ 1);
1023 if (p
->fts_info
== FTS_NSOK
)
1025 if (p
->fts_statp
->st_size
== FTS_STAT_REQUIRED
)
1027 FTSENT
*parent
= p
->fts_parent
;
1028 if (parent
->fts_n_dirs_remaining
== 0
1029 && ISSET(FTS_NOSTAT
)
1030 && ISSET(FTS_PHYSICAL
)
1031 && (leaf_optimization (parent
, sp
->fts_cwd_fd
)
1032 == NOSTAT_LEAF_OPTIMIZATION
))
1034 /* nothing more needed */
1038 p
->fts_info
= fts_stat(sp
, p
, false);
1039 if (S_ISDIR(p
->fts_statp
->st_mode
)
1040 && p
->fts_level
!= FTS_ROOTLEVEL
1041 && 0 < parent
->fts_n_dirs_remaining
1042 && parent
->fts_n_dirs_remaining
!= (nlink_t
) -1)
1043 parent
->fts_n_dirs_remaining
--;
1047 fts_assert (p
->fts_statp
->st_size
== FTS_NO_STAT_REQUIRED
);
1050 if (p
->fts_info
== FTS_D
)
1052 /* Now that P->fts_statp is guaranteed to be valid,
1053 if this is a command-line directory, record its
1054 device number, to be used for FTS_XDEV. */
1055 if (p
->fts_level
== FTS_ROOTLEVEL
)
1056 sp
->fts_dev
= p
->fts_statp
->st_dev
;
1057 Dprintf ((" entering: %s\n", p
->fts_path
));
1058 if (! enter_dir (sp
, p
))
1060 __set_errno (ENOMEM
);
1068 /* Move up to the parent node. */
1069 p
= tmp
->fts_parent
;
1073 if (p
->fts_level
== FTS_ROOTPARENTLEVEL
) {
1075 * Done; free everything up and set errno to 0 so the user
1076 * can distinguish between error and EOF.
1080 return (sp
->fts_cur
= NULL
);
1083 fts_assert (p
->fts_info
!= FTS_NSOK
);
1085 /* NUL terminate the file name. */
1086 sp
->fts_path
[p
->fts_pathlen
] = '\0';
1089 * Return to the parent directory. If at a root node, restore
1090 * the initial working directory. If we came through a symlink,
1091 * go back through the file descriptor. Otherwise, move up
1092 * one level, via "..".
1094 if (p
->fts_level
== FTS_ROOTLEVEL
) {
1095 if (restore_initial_cwd(sp
)) {
1096 p
->fts_errno
= errno
;
1099 } else if (p
->fts_flags
& FTS_SYMFOLLOW
) {
1100 if (FCHDIR(sp
, p
->fts_symfd
)) {
1101 p
->fts_errno
= errno
;
1104 (void)close(p
->fts_symfd
);
1105 } else if (!(p
->fts_flags
& FTS_DONTCHDIR
) &&
1106 fts_safe_changedir(sp
, p
->fts_parent
, -1, "..")) {
1107 p
->fts_errno
= errno
;
1111 /* If the directory causes a cycle, preserve the FTS_DC flag and keep
1112 the corresponding dev/ino pair in the hash table. It is going to be
1113 removed when leaving the original directory. */
1114 if (p
->fts_info
!= FTS_DC
) {
1115 p
->fts_info
= p
->fts_errno
? FTS_ERR
: FTS_DP
;
1116 if (p
->fts_errno
== 0)
1117 LEAVE_DIR (sp
, p
, "3");
1119 return ISSET(FTS_STOP
) ? NULL
: p
;
1123 * Fts_set takes the stream as an argument although it's not used in this
1124 * implementation; it would be necessary if anyone wanted to add global
1125 * semantics to fts using fts_set. An error return is allowed for similar
1130 fts_set(FTS
*sp _GL_UNUSED
, FTSENT
*p
, int instr
)
1132 if (instr
!= 0 && instr
!= FTS_AGAIN
&& instr
!= FTS_FOLLOW
&&
1133 instr
!= FTS_NOINSTR
&& instr
!= FTS_SKIP
) {
1134 __set_errno (EINVAL
);
1137 p
->fts_instr
= instr
;
1142 fts_children (register FTS
*sp
, int instr
)
1147 if (instr
!= 0 && instr
!= FTS_NAMEONLY
) {
1148 __set_errno (EINVAL
);
1152 /* Set current node pointer. */
1156 * Errno set to 0 so user can distinguish empty directory from
1161 /* Fatal errors stop here. */
1162 if (ISSET(FTS_STOP
))
1165 /* Return logical hierarchy of user's arguments. */
1166 if (p
->fts_info
== FTS_INIT
)
1167 return (p
->fts_link
);
1170 * If not a directory being visited in pre-order, stop here. Could
1171 * allow FTS_DNR, assuming the user has fixed the problem, but the
1172 * same effect is available with FTS_AGAIN.
1174 if (p
->fts_info
!= FTS_D
/* && p->fts_info != FTS_DNR */)
1177 /* Free up any previous child list. */
1178 if (sp
->fts_child
!= NULL
)
1179 fts_lfree(sp
->fts_child
);
1181 if (instr
== FTS_NAMEONLY
) {
1188 * If using chdir on a relative file name and called BEFORE fts_read
1189 * does its chdir to the root of a traversal, we can lose -- we need to
1190 * chdir into the subdirectory, and we don't know where the current
1191 * directory is, so we can't get back so that the upcoming chdir by
1192 * fts_read will work.
1194 if (p
->fts_level
!= FTS_ROOTLEVEL
|| p
->fts_accpath
[0] == '/' ||
1196 return (sp
->fts_child
= fts_build(sp
, instr
));
1198 if ((fd
= diropen (sp
, ".")) < 0)
1199 return (sp
->fts_child
= NULL
);
1200 sp
->fts_child
= fts_build(sp
, instr
);
1201 if (ISSET(FTS_CWDFD
))
1203 cwd_advance_fd (sp
, fd
, true);
1209 int saved_errno
= errno
;
1211 __set_errno (saved_errno
);
1216 return (sp
->fts_child
);
1219 /* A comparison function to sort on increasing inode number.
1220 For some file system types, sorting either way makes a huge
1221 performance difference for a directory with very many entries,
1222 but sorting on increasing values is slightly better than sorting
1223 on decreasing values. The difference is in the 5% range. */
1225 fts_compare_ino (struct _ftsent
const **a
, struct _ftsent
const **b
)
1227 return (a
[0]->fts_statp
->st_ino
< b
[0]->fts_statp
->st_ino
? -1
1228 : b
[0]->fts_statp
->st_ino
< a
[0]->fts_statp
->st_ino
? 1 : 0);
1231 /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode
1232 S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */
1234 set_stat_type (struct stat
*st
, unsigned int dtype
)
1266 #define closedir_and_clear(dirp) \
1274 #define fts_opendir(file, Pdir_fd) \
1275 opendirat((! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
1276 ? sp->fts_cwd_fd : AT_FDCWD), \
1278 (((ISSET(FTS_PHYSICAL) \
1279 && ! (ISSET(FTS_COMFOLLOW) \
1280 && cur->fts_level == FTS_ROOTLEVEL)) \
1281 ? O_NOFOLLOW : 0)), \
1285 * This is the tricky part -- do not casually change *anything* in here. The
1286 * idea is to build the linked list of entries that are used by fts_children
1287 * and fts_read. There are lots of special cases.
1289 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
1290 * set and it's a physical walk (so that symbolic links can't be directories),
1291 * we can do things quickly. First, if it's a 4.4BSD file system, the type
1292 * of the file is in the directory entry. Otherwise, we assume that the number
1293 * of subdirectories in a node is equal to the number of links to the parent.
1294 * The former skips all stat calls. The latter skips stat calls in any leaf
1295 * directories and for any files after the subdirectories in the directory have
1296 * been found, cutting the stat calls by about 2/3.
1300 fts_build (register FTS
*sp
, int type
)
1302 register FTSENT
*p
, *head
;
1303 register size_t nitems
;
1310 size_t len
, maxlen
, new_len
;
1313 FTSENT
*cur
= sp
->fts_cur
;
1314 bool continue_readdir
= !!cur
->fts_dirp
;
1315 bool sort_by_inode
= false;
1318 /* When cur->fts_dirp is non-NULL, that means we should
1319 continue calling readdir on that existing DIR* pointer
1320 rather than opening a new one. */
1321 if (continue_readdir
)
1323 DIR *dp
= cur
->fts_dirp
;
1324 dir_fd
= dirfd (dp
);
1327 closedir_and_clear (cur
->fts_dirp
);
1330 cur
->fts_info
= FTS_DNR
;
1331 cur
->fts_errno
= errno
;
1338 /* Open the directory for reading. If this fails, we're done.
1339 If being called from fts_read, set the fts_info field. */
1340 if ((cur
->fts_dirp
= fts_opendir(cur
->fts_accpath
, &dir_fd
)) == NULL
)
1344 cur
->fts_info
= FTS_DNR
;
1345 cur
->fts_errno
= errno
;
1349 /* Rather than calling fts_stat for each and every entry encountered
1350 in the readdir loop (below), stat each directory only right after
1352 if (cur
->fts_info
== FTS_NSOK
)
1353 cur
->fts_info
= fts_stat(sp
, cur
, false);
1354 else if (sp
->fts_options
& FTS_TIGHT_CYCLE_CHECK
)
1356 /* Now read the stat info again after opening a directory to
1357 reveal eventual changes caused by a submount triggered by
1358 the traversal. But do it only for utilities which use
1359 FTS_TIGHT_CYCLE_CHECK. Therefore, only find and du
1360 benefit/suffer from this feature for now. */
1361 LEAVE_DIR (sp
, cur
, "4");
1362 fts_stat (sp
, cur
, false);
1363 if (! enter_dir (sp
, cur
))
1365 __set_errno (ENOMEM
);
1371 /* Maximum number of readdir entries to read at one time. This
1372 limitation is to avoid reading millions of entries into memory
1373 at once. When an fts_compar function is specified, we have no
1374 choice: we must read all entries into memory before calling that
1375 function. But when no such function is specified, we can read
1376 entries in batches that are large enough to help us with inode-
1377 sorting, yet not so large that we risk exhausting memory. */
1378 max_entries
= sp
->fts_compar
? SIZE_MAX
: FTS_MAX_READDIR_ENTRIES
;
1381 * If we're going to need to stat anything or we want to descend
1382 * and stay in the directory, chdir. If this fails we keep going,
1383 * but set a flag so we don't chdir after the post-order visit.
1384 * We won't be able to stat anything, but we can still return the
1385 * names themselves. Note, that since fts_read won't be able to
1386 * chdir into the directory, it will have to return different file
1387 * names than before, i.e. "a/b" instead of "b". Since the node
1388 * has already been visited in pre-order, have to wait until the
1389 * post-order visit to return the error. There is a special case
1390 * here, if there was nothing to stat then it's not an error to
1391 * not be able to stat. This is all fairly nasty. If a program
1392 * needed sorted entries or stat information, they had better be
1393 * checking FTS_NS on the returned nodes.
1395 if (continue_readdir
)
1397 /* When resuming a short readdir run, we already have
1398 the required dirp and dir_fd. */
1403 /* Try to descend unless it is a names-only fts_children,
1404 or the directory is known to lack subdirectories. */
1405 descend
= (type
!= BNAMES
1406 && ! (ISSET (FTS_NOSTAT
) && ISSET (FTS_PHYSICAL
)
1407 && ! ISSET (FTS_SEEDOT
)
1408 && cur
->fts_statp
->st_nlink
== MIN_DIR_NLINK
1409 && (leaf_optimization (cur
, dir_fd
)
1410 != NO_LEAF_OPTIMIZATION
)));
1411 if (descend
|| type
== BREAD
)
1413 if (ISSET(FTS_CWDFD
))
1414 dir_fd
= fcntl (dir_fd
, F_DUPFD_CLOEXEC
, STDERR_FILENO
+ 1);
1415 if (dir_fd
< 0 || fts_safe_changedir(sp
, cur
, dir_fd
, NULL
)) {
1416 if (descend
&& type
== BREAD
)
1417 cur
->fts_errno
= errno
;
1418 cur
->fts_flags
|= FTS_DONTCHDIR
;
1420 closedir_and_clear(cur
->fts_dirp
);
1421 if (ISSET(FTS_CWDFD
) && 0 <= dir_fd
)
1423 cur
->fts_dirp
= NULL
;
1430 * Figure out the max file name length that can be stored in the
1431 * current buffer -- the inner loop allocates more space as necessary.
1432 * We really wouldn't have to do the maxlen calculations here, we
1433 * could do them in fts_read before returning the name, but it's a
1434 * lot easier here since the length is part of the dirent structure.
1436 * If not changing directories set a pointer so that can just append
1437 * each new component into the file name.
1440 if (ISSET(FTS_NOCHDIR
)) {
1441 cp
= sp
->fts_path
+ len
;
1444 /* GCC, you're too verbose. */
1448 maxlen
= sp
->fts_pathlen
- len
;
1450 level
= cur
->fts_level
+ 1;
1452 /* Read the directory, attaching each entry to the "link" pointer. */
1457 while (cur
->fts_dirp
) {
1460 struct dirent
*dp
= readdir(cur
->fts_dirp
);
1463 cur
->fts_errno
= errno
;
1464 /* If we've not read any items yet, treat
1465 the error as if we can't access the dir. */
1466 cur
->fts_info
= (continue_readdir
|| nitems
)
1467 ? FTS_ERR
: FTS_DNR
;
1471 if (!ISSET(FTS_SEEDOT
) && ISDOT(dp
->d_name
))
1474 d_namelen
= _D_EXACT_NAMLEN (dp
);
1475 p
= fts_alloc (sp
, dp
->d_name
, d_namelen
);
1478 if (d_namelen
>= maxlen
) {
1479 /* include space for NUL */
1480 oldaddr
= sp
->fts_path
;
1481 if (! fts_palloc(sp
, d_namelen
+ len
+ 1)) {
1483 * No more memory. Save
1484 * errno, free up the current structure and the
1485 * structures already allocated.
1487 mem1
: saved_errno
= errno
;
1490 closedir_and_clear(cur
->fts_dirp
);
1491 cur
->fts_info
= FTS_ERR
;
1493 __set_errno (saved_errno
);
1496 /* Did realloc() change the pointer? */
1497 if (oldaddr
!= sp
->fts_path
) {
1499 if (ISSET(FTS_NOCHDIR
))
1500 cp
= sp
->fts_path
+ len
;
1502 maxlen
= sp
->fts_pathlen
- len
;
1505 new_len
= len
+ d_namelen
;
1506 if (new_len
< len
) {
1508 * In the unlikely event that we would end up
1509 * with a file name longer than SIZE_MAX, free up
1510 * the current structure and the structures already
1511 * allocated, then error out with ENAMETOOLONG.
1515 closedir_and_clear(cur
->fts_dirp
);
1516 cur
->fts_info
= FTS_ERR
;
1518 __set_errno (ENAMETOOLONG
);
1521 p
->fts_level
= level
;
1522 p
->fts_parent
= sp
->fts_cur
;
1523 p
->fts_pathlen
= new_len
;
1525 /* Store dirent.d_ino, in case we need to sort
1526 entries before processing them. */
1527 p
->fts_statp
->st_ino
= D_INO (dp
);
1529 /* Build a file name for fts_stat to stat. */
1530 if (ISSET(FTS_NOCHDIR
)) {
1531 p
->fts_accpath
= p
->fts_path
;
1532 memmove(cp
, p
->fts_name
, p
->fts_namelen
+ 1);
1534 p
->fts_accpath
= p
->fts_name
;
1536 if (sp
->fts_compar
== NULL
|| ISSET(FTS_DEFER_STAT
)) {
1537 /* Record what fts_read will have to do with this
1538 entry. In many cases, it will simply fts_stat it,
1539 but we can take advantage of any d_type information
1540 to optimize away the unnecessary stat calls. I.e.,
1541 if FTS_NOSTAT is in effect and we're not following
1542 symlinks (FTS_PHYSICAL) and d_type indicates this
1543 is *not* a directory, then we won't have to stat it
1544 at all. If it *is* a directory, then (currently)
1545 we stat it regardless, in order to get device and
1546 inode numbers. Some day we might optimize that
1547 away, too, for directories where d_ino is known to
1549 bool skip_stat
= (ISSET(FTS_PHYSICAL
)
1550 && ISSET(FTS_NOSTAT
)
1552 && ! DT_MUST_BE(dp
, DT_DIR
));
1553 p
->fts_info
= FTS_NSOK
;
1554 /* Propagate dirent.d_type information back
1555 to caller, when possible. */
1556 set_stat_type (p
->fts_statp
, D_TYPE (dp
));
1557 fts_set_stat_required(p
, !skip_stat
);
1559 p
->fts_info
= fts_stat(sp
, p
, false);
1562 /* We walk in directory order so "ls -f" doesn't get upset. */
1571 /* If there are many entries, no sorting function has been
1572 specified, and this file system is of a type that may be
1573 slow with a large number of entries, arrange to sort the
1574 directory entries on increasing inode numbers.
1576 The NITEMS comparison uses ==, not >, because the test
1577 needs to be tried at most once once, and NITEMS will exceed
1578 the threshold after it is incremented below. */
1579 if (nitems
== _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
1581 sort_by_inode
= dirent_inode_sort_may_be_useful (cur
, dir_fd
);
1584 if (max_entries
<= nitems
) {
1585 /* When there are too many dir entries, leave
1586 fts_dirp open, so that a subsequent fts_read
1587 can take up where we leave off. */
1588 goto break_without_closedir
;
1593 closedir_and_clear(cur
->fts_dirp
);
1595 break_without_closedir
:
1598 * If realloc() changed the address of the file name, adjust the
1599 * addresses for the rest of the tree and the dir list.
1602 fts_padjust(sp
, head
);
1605 * If not changing directories, reset the file name back to original
1608 if (ISSET(FTS_NOCHDIR
)) {
1609 if (len
== sp
->fts_pathlen
|| nitems
== 0)
1615 * If descended after called from fts_children or after called from
1616 * fts_read and nothing found, get back. At the root level we use
1617 * the saved fd; if one of fts_open()'s arguments is a relative name
1618 * to an empty directory, we wind up here with no other way back. If
1619 * can't get back, we're done.
1621 if (!continue_readdir
&& descend
&& (type
== BCHILD
|| !nitems
) &&
1622 (cur
->fts_level
== FTS_ROOTLEVEL
1623 ? restore_initial_cwd(sp
)
1624 : fts_safe_changedir(sp
, cur
->fts_parent
, -1, ".."))) {
1625 cur
->fts_info
= FTS_ERR
;
1631 /* If didn't find anything, return NULL. */
1634 && cur
->fts_info
!= FTS_DNR
&& cur
->fts_info
!= FTS_ERR
)
1635 cur
->fts_info
= FTS_DP
;
1640 if (sort_by_inode
) {
1641 sp
->fts_compar
= fts_compare_ino
;
1642 head
= fts_sort (sp
, head
, nitems
);
1643 sp
->fts_compar
= NULL
;
1646 /* Sort the entries. */
1647 if (sp
->fts_compar
&& nitems
> 1)
1648 head
= fts_sort(sp
, head
, nitems
);
1654 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1655 current hierarchy. There should be a directory with dev/inode
1656 matching those of AD. If not, print a lot of diagnostics. */
1658 find_matching_ancestor (FTSENT
const *e_curr
, struct Active_dir
const *ad
)
1661 for (ent
= e_curr
; ent
->fts_level
>= FTS_ROOTLEVEL
; ent
= ent
->fts_parent
)
1663 if (ad
->ino
== ent
->fts_statp
->st_ino
1664 && ad
->dev
== ent
->fts_statp
->st_dev
)
1667 printf ("ERROR: tree dir, %s, not active\n", ad
->fts_ent
->fts_accpath
);
1668 printf ("active dirs:\n");
1670 ent
->fts_level
>= FTS_ROOTLEVEL
; ent
= ent
->fts_parent
)
1671 printf (" %s(%"PRIuMAX
"/%"PRIuMAX
") to %s(%"PRIuMAX
"/%"PRIuMAX
")...\n",
1672 ad
->fts_ent
->fts_accpath
,
1673 (uintmax_t) ad
->dev
,
1674 (uintmax_t) ad
->ino
,
1676 (uintmax_t) ent
->fts_statp
->st_dev
,
1677 (uintmax_t) ent
->fts_statp
->st_ino
);
1681 fts_cross_check (FTS
const *sp
)
1683 FTSENT
const *ent
= sp
->fts_cur
;
1685 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK
))
1688 Dprintf (("fts-cross-check cur=%s\n", ent
->fts_path
));
1689 /* Make sure every parent dir is in the tree. */
1690 for (t
= ent
->fts_parent
; t
->fts_level
>= FTS_ROOTLEVEL
; t
= t
->fts_parent
)
1692 struct Active_dir ad
;
1693 ad
.ino
= t
->fts_statp
->st_ino
;
1694 ad
.dev
= t
->fts_statp
->st_dev
;
1695 if ( ! hash_lookup (sp
->fts_cycle
.ht
, &ad
))
1696 printf ("ERROR: active dir, %s, not in tree\n", t
->fts_path
);
1699 /* Make sure every dir in the tree is an active dir.
1700 But ENT is not necessarily a directory. If so, just skip this part. */
1701 if (ent
->fts_parent
->fts_level
>= FTS_ROOTLEVEL
1702 && (ent
->fts_info
== FTS_DP
1703 || ent
->fts_info
== FTS_D
))
1705 struct Active_dir
*ad
;
1706 for (ad
= hash_get_first (sp
->fts_cycle
.ht
); ad
!= NULL
;
1707 ad
= hash_get_next (sp
->fts_cycle
.ht
, ad
))
1709 find_matching_ancestor (ent
, ad
);
1715 same_fd (int fd1
, int fd2
)
1717 struct stat sb1
, sb2
;
1718 return (fstat (fd1
, &sb1
) == 0
1719 && fstat (fd2
, &sb2
) == 0
1720 && SAME_INODE (sb1
, sb2
));
1724 fd_ring_print (FTS
const *sp
, FILE *stream
, char const *msg
)
1726 I_ring
const *fd_ring
= &sp
->fts_fd_ring
;
1727 unsigned int i
= fd_ring
->fts_front
;
1728 char *cwd
= getcwdat (sp
->fts_cwd_fd
, NULL
, 0);
1729 fprintf (stream
, "=== %s ========== %s\n", msg
, cwd
);
1731 if (i_ring_empty (fd_ring
))
1736 int fd
= fd_ring
->fts_fd_ring
[i
];
1738 fprintf (stream
, "%d: %d:\n", i
, fd
);
1741 char *wd
= getcwdat (fd
, NULL
, 0);
1742 fprintf (stream
, "%d: %d: %s\n", i
, fd
, wd
);
1745 if (i
== fd_ring
->fts_back
)
1747 i
= (i
+ I_RING_SIZE
- 1) % I_RING_SIZE
;
1751 /* Ensure that each file descriptor on the fd_ring matches a
1752 parent, grandparent, etc. of the current working directory. */
1754 fd_ring_check (FTS
const *sp
)
1759 /* Make a writable copy. */
1760 I_ring fd_w
= sp
->fts_fd_ring
;
1762 int cwd_fd
= sp
->fts_cwd_fd
;
1763 cwd_fd
= fcntl (cwd_fd
, F_DUPFD_CLOEXEC
, STDERR_FILENO
+ 1);
1764 char *dot
= getcwdat (cwd_fd
, NULL
, 0);
1765 error (0, 0, "===== check ===== cwd: %s", dot
);
1767 while ( ! i_ring_empty (&fd_w
))
1769 int fd
= i_ring_pop (&fd_w
);
1772 int open_flags
= O_SEARCH
| O_CLOEXEC
;
1773 int parent_fd
= openat (cwd_fd
, "..", open_flags
);
1779 if (!same_fd (fd
, parent_fd
))
1781 char *cwd
= getcwdat (fd
, NULL
, 0);
1782 error (0, errno
, "ring : %s", cwd
);
1783 char *c2
= getcwdat (parent_fd
, NULL
, 0);
1784 error (0, errno
, "parent: %s", c2
);
1797 static unsigned short int
1799 fts_stat(FTS
*sp
, register FTSENT
*p
, bool follow
)
1801 struct stat
*sbp
= p
->fts_statp
;
1803 if (p
->fts_level
== FTS_ROOTLEVEL
&& ISSET(FTS_COMFOLLOW
))
1807 * If doing a logical walk, or application requested FTS_FOLLOW, do
1808 * a stat(2). If that fails, check for a non-existent symlink. If
1809 * fail, set the errno from the stat call.
1811 if (ISSET(FTS_LOGICAL
) || follow
) {
1812 if (stat(p
->fts_accpath
, sbp
)) {
1814 && lstat(p
->fts_accpath
, sbp
) == 0) {
1816 return (FTS_SLNONE
);
1818 p
->fts_errno
= errno
;
1821 } else if (fstatat(sp
->fts_cwd_fd
, p
->fts_accpath
, sbp
,
1822 AT_SYMLINK_NOFOLLOW
)) {
1823 p
->fts_errno
= errno
;
1824 err
: memset(sbp
, 0, sizeof(struct stat
));
1828 if (S_ISDIR(sbp
->st_mode
)) {
1829 p
->fts_n_dirs_remaining
1830 = ((sbp
->st_nlink
< MIN_DIR_NLINK
1831 || p
->fts_level
<= FTS_ROOTLEVEL
)
1833 : sbp
->st_nlink
- (ISSET (FTS_SEEDOT
) ? 0 : MIN_DIR_NLINK
));
1834 if (ISDOT(p
->fts_name
)) {
1835 /* Command-line "." and ".." are real directories. */
1836 return (p
->fts_level
== FTS_ROOTLEVEL
? FTS_D
: FTS_DOT
);
1841 if (S_ISLNK(sbp
->st_mode
))
1843 if (S_ISREG(sbp
->st_mode
))
1845 return (FTS_DEFAULT
);
1849 fts_compar (void const *a
, void const *b
)
1851 /* Convert A and B to the correct types, to pacify the compiler, and
1852 for portability to bizarre hosts where "void const *" and "FTSENT
1853 const **" differ in runtime representation. The comparison
1854 function cannot modify *a and *b, but there is no compile-time
1856 FTSENT
const **pa
= (FTSENT
const **) a
;
1857 FTSENT
const **pb
= (FTSENT
const **) b
;
1858 return pa
[0]->fts_fts
->fts_compar (pa
, pb
);
1863 fts_sort (FTS
*sp
, FTSENT
*head
, register size_t nitems
)
1865 register FTSENT
**ap
, *p
;
1867 /* On most modern hosts, void * and FTSENT ** have the same
1868 run-time representation, and one can convert sp->fts_compar to
1869 the type qsort expects without problem. Use the heuristic that
1870 this is OK if the two pointer types are the same size, and if
1871 converting FTSENT ** to long int is the same as converting
1872 FTSENT ** to void * and then to long int. This heuristic isn't
1873 valid in general but we don't know of any counterexamples. */
1875 int (*compare
) (void const *, void const *) =
1876 ((sizeof &dummy
== sizeof (void *)
1877 && (long int) &dummy
== (long int) (void *) &dummy
)
1878 ? (int (*) (void const *, void const *)) sp
->fts_compar
1882 * Construct an array of pointers to the structures and call qsort(3).
1883 * Reassemble the array in the order returned by qsort. If unable to
1884 * sort for memory reasons, return the directory entries in their
1885 * current order. Allocate enough space for the current needs plus
1886 * 40 so don't realloc one entry at a time.
1888 if (nitems
> sp
->fts_nitems
) {
1891 sp
->fts_nitems
= nitems
+ 40;
1892 if (SIZE_MAX
/ sizeof *a
< sp
->fts_nitems
1893 || ! (a
= realloc (sp
->fts_array
,
1894 sp
->fts_nitems
* sizeof *a
))) {
1895 free(sp
->fts_array
);
1896 sp
->fts_array
= NULL
;
1902 for (ap
= sp
->fts_array
, p
= head
; p
; p
= p
->fts_link
)
1904 qsort((void *)sp
->fts_array
, nitems
, sizeof(FTSENT
*), compare
);
1905 for (head
= *(ap
= sp
->fts_array
); --nitems
; ++ap
)
1906 ap
[0]->fts_link
= ap
[1];
1907 ap
[0]->fts_link
= NULL
;
1913 fts_alloc (FTS
*sp
, const char *name
, register size_t namelen
)
1919 * The file name is a variable length array. Allocate the FTSENT
1920 * structure and the file name in one chunk.
1922 len
= FLEXSIZEOF(FTSENT
, fts_name
, namelen
+ 1);
1923 if ((p
= malloc(len
)) == NULL
)
1926 /* Copy the name and guarantee NUL termination. */
1927 memcpy(p
->fts_name
, name
, namelen
);
1928 p
->fts_name
[namelen
] = '\0';
1930 p
->fts_namelen
= namelen
;
1932 p
->fts_path
= sp
->fts_path
;
1936 p
->fts_instr
= FTS_NOINSTR
;
1938 p
->fts_pointer
= NULL
;
1944 fts_lfree (register FTSENT
*head
)
1948 /* Free a linked list of structures. */
1949 while ((p
= head
)) {
1950 head
= head
->fts_link
;
1952 closedir (p
->fts_dirp
);
1958 * Allow essentially unlimited file name lengths; find, rm, ls should
1959 * all work on any tree. Most systems will allow creation of file
1960 * names much longer than MAXPATHLEN, even though the kernel won't
1961 * resolve them. Add the size (not just what's needed) plus 256 bytes
1962 * so don't realloc the file name 2 bytes at a time.
1966 fts_palloc (FTS
*sp
, size_t more
)
1969 size_t new_len
= sp
->fts_pathlen
+ more
+ 256;
1972 * See if fts_pathlen would overflow.
1974 if (new_len
< sp
->fts_pathlen
) {
1976 sp
->fts_path
= NULL
;
1977 __set_errno (ENAMETOOLONG
);
1980 sp
->fts_pathlen
= new_len
;
1981 p
= realloc(sp
->fts_path
, sp
->fts_pathlen
);
1984 sp
->fts_path
= NULL
;
1992 * When the file name is realloc'd, have to fix all of the pointers in
1993 * structures already returned.
1997 fts_padjust (FTS
*sp
, FTSENT
*head
)
2000 char *addr
= sp
->fts_path
;
2002 #define ADJUST(p) do { \
2003 if ((p)->fts_accpath != (p)->fts_name) { \
2004 (p)->fts_accpath = \
2005 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
2007 (p)->fts_path = addr; \
2009 /* Adjust the current set of children. */
2010 for (p
= sp
->fts_child
; p
; p
= p
->fts_link
)
2013 /* Adjust the rest of the tree, including the current level. */
2014 for (p
= head
; p
->fts_level
>= FTS_ROOTLEVEL
;) {
2016 p
= p
->fts_link
? p
->fts_link
: p
->fts_parent
;
2021 internal_function _GL_ATTRIBUTE_PURE
2022 fts_maxarglen (char * const *argv
)
2026 for (max
= 0; *argv
; ++argv
)
2027 if ((len
= strlen(*argv
)) > max
)
2033 * Change to dir specified by fd or file name without getting
2034 * tricked by someone changing the world out from underneath us.
2035 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
2036 * If FD is non-negative, expect it to be used after this function returns,
2037 * and to be closed eventually. So don't pass e.g., 'dirfd(dirp)' and then
2038 * do closedir(dirp), because that would invalidate the saved FD.
2039 * Upon failure, close FD immediately and return nonzero.
2043 fts_safe_changedir (FTS
*sp
, FTSENT
*p
, int fd
, char const *dir
)
2046 bool is_dotdot
= dir
&& STREQ (dir
, "..");
2049 /* This clause handles the unusual case in which FTS_NOCHDIR
2050 is specified, along with FTS_CWDFD. In that case, there is
2051 no need to change even the virtual cwd file descriptor.
2052 However, if FD is non-negative, we do close it here. */
2053 if (ISSET (FTS_NOCHDIR
))
2055 if (ISSET (FTS_CWDFD
) && 0 <= fd
)
2060 if (fd
< 0 && is_dotdot
&& ISSET (FTS_CWDFD
))
2062 /* When possible, skip the diropen and subsequent fstat+dev/ino
2063 comparison. I.e., when changing to parent directory
2064 (chdir ("..")), use a file descriptor from the ring and
2065 save the overhead of diropen+fstat, as well as avoiding
2066 failure when we lack "x" access to the virtual cwd. */
2067 if ( ! i_ring_empty (&sp
->fts_fd_ring
))
2070 fd_ring_print (sp
, stderr
, "pre-pop");
2071 parent_fd
= i_ring_pop (&sp
->fts_fd_ring
);
2081 if (fd
< 0 && (newfd
= diropen (sp
, dir
)) < 0)
2084 /* The following dev/inode check is necessary if we're doing a
2085 "logical" traversal (through symlinks, a la chown -L), if the
2086 system lacks O_NOFOLLOW support, or if we're changing to ".."
2087 (but not via a popped file descriptor). When changing to the
2088 name "..", O_NOFOLLOW can't help. In general, when the target is
2089 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
2090 follow a symlink, so we can avoid the expense of this fstat. */
2091 if (ISSET(FTS_LOGICAL
) || ! HAVE_WORKING_O_NOFOLLOW
2092 || (dir
&& STREQ (dir
, "..")))
2095 if (fstat(newfd
, &sb
))
2100 if (p
->fts_statp
->st_dev
!= sb
.st_dev
2101 || p
->fts_statp
->st_ino
!= sb
.st_ino
)
2103 __set_errno (ENOENT
); /* disinformation */
2109 if (ISSET(FTS_CWDFD
))
2111 cwd_advance_fd (sp
, newfd
, ! is_dotdot
);
2115 ret
= fchdir(newfd
);
2121 __set_errno (oerrno
);