1 /* Traverse a file hierarchy.
3 Copyright (C) 2004-2010 Free Software Foundation, Inc.
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
19 * Copyright (c) 1990, 1993, 1994
20 * The Regents of the University of California. All rights reserved.
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
25 * 1. Redistributions of source code must retain the above copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 4. Neither the name of the University nor the names of its contributors
31 * may be used to endorse or promote products derived from this software
32 * without specific prior written permission.
34 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
35 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
49 #if defined(LIBC_SCCS) && !defined(lint)
50 static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94";
51 #endif /* LIBC_SCCS and not lint */
55 #if HAVE_SYS_PARAM_H || defined _LIBC
56 # include <sys/param.h>
59 # include <include/sys/stat.h>
61 # include <sys/stat.h>
72 # include "dirent--.h"
73 # include "unistd--.h"
74 /* FIXME - use fcntl(F_DUPFD_CLOEXEC)/openat(O_CLOEXEC) once they are
78 # include "same-inode.h"
82 #ifndef _D_EXACT_NAMLEN
83 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
86 #if HAVE_STRUCT_DIRENT_D_TYPE
87 /* True if the type of the directory entry D is known. */
88 # define DT_IS_KNOWN(d) ((d)->d_type != DT_UNKNOWN)
89 /* True if the type of the directory entry D must be T. */
90 # define DT_MUST_BE(d, t) ((d)->d_type == (t))
91 # define D_TYPE(d) ((d)->d_type)
93 # define DT_IS_KNOWN(d) false
94 # define DT_MUST_BE(d, t) false
95 # define D_TYPE(d) DT_UNKNOWN
100 /* Any nonzero values will do here, so long as they're distinct.
101 Undef any existing macros out of the way. */
127 NOT_AN_INODE_NUMBER = 0
130 #ifdef D_INO_IN_DIRENT
131 # define D_INO(dp) (dp)->d_ino
133 /* Some systems don't have inodes, so fake them to avoid lots of ifdefs. */
134 # define D_INO(dp) NOT_AN_INODE_NUMBER
137 /* If there are more than this many entries in a directory,
138 and the conditions mentioned below are satisfied, then sort
139 the entries on inode number before any further processing. */
140 #ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
141 # define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000
145 _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD = FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
150 FTS_NO_STAT_REQUIRED = 1,
151 FTS_STAT_REQUIRED = 2
156 # define close __close
158 # define closedir __closedir
160 # define fchdir __fchdir
164 # define opendir __opendir
166 # define readdir __readdir
168 # undef internal_function
169 # define internal_function /* empty */
173 # define __set_errno(Val) errno = (Val)
176 /* If this host provides the openat function, then we can avoid
177 attempting to open "." in some initialization code below. */
179 # define HAVE_OPENAT_SUPPORT 1
181 # define HAVE_OPENAT_SUPPORT 0
185 # define fts_assert(expr) ((void) 0)
187 # define fts_assert(expr) \
196 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
197 static FTSENT *fts_build (FTS *, int) internal_function;
198 static void fts_lfree (FTSENT *) internal_function;
199 static void fts_load (FTS *, FTSENT *) internal_function;
200 static size_t fts_maxarglen (char * const *) internal_function;
201 static void fts_padjust (FTS *, FTSENT *) internal_function;
202 static bool fts_palloc (FTS *, size_t) internal_function;
203 static FTSENT *fts_sort (FTS *, FTSENT *, size_t) internal_function;
204 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
205 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
208 #include "fts-cycle.c"
211 # define MAX(a,b) ((a) > (b) ? (a) : (b))
215 # define SIZE_MAX ((size_t) -1)
218 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
219 #define STREQ(a, b) (strcmp (a, b) == 0)
221 #define CLR(opt) (sp->fts_options &= ~(opt))
222 #define ISSET(opt) (sp->fts_options & (opt))
223 #define SET(opt) (sp->fts_options |= (opt))
225 /* FIXME: make this a function */
226 #define RESTORE_INITIAL_CWD(sp) \
227 (fd_ring_clear (&((sp)->fts_fd_ring)), \
228 FCHDIR ((sp), (ISSET (FTS_CWDFD) ? AT_FDCWD : (sp)->fts_rfd)))
230 /* FIXME: FTS_NOCHDIR is now misnamed.
231 Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
232 #define FCHDIR(sp, fd) \
233 (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \
234 ? (cwd_advance_fd ((sp), (fd), true), 0) \
238 /* fts_build flags */
239 /* FIXME: make this an enum */
240 #define BCHILD 1 /* fts_children */
241 #define BNAMES 2 /* fts_children, names only */
242 #define BREAD 3 /* fts_read */
245 # include <inttypes.h>
248 # include "getcwdat.h"
249 bool fts_debug = false;
250 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
253 # define fd_ring_check(x)
254 # define fd_ring_print(a, b, c)
257 #define LEAVE_DIR(Fts, Ent, Tag) \
260 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
261 leave_dir (Fts, Ent); \
262 fd_ring_check (Fts); \
267 fd_ring_clear (I_ring *fd_ring)
269 while ( ! i_ring_empty (fd_ring))
271 int fd = i_ring_pop (fd_ring);
277 /* Overload the fts_statp->st_size member (otherwise unused, when
278 fts_info is FTS_NSOK) to indicate whether fts_read should stat
279 this entry or not. */
281 fts_set_stat_required (FTSENT *p, bool required)
283 fts_assert (p->fts_info == FTS_NSOK);
284 p->fts_statp->st_size = (required
286 : FTS_NO_STAT_REQUIRED);
289 /* file-descriptor-relative opendir. */
290 /* FIXME: if others need this function, move it into lib/openat.c */
293 opendirat (int fd, char const *dir)
295 int new_fd = openat (fd, dir,
296 O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK);
301 set_cloexec_flag (new_fd, true);
302 dirp = fdopendir (new_fd);
305 int saved_errno = errno;
312 /* Virtual fchdir. Advance SP's working directory file descriptor,
313 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
314 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
315 open on sp->fts_cwd_fd; i.e., to move the working directory one level
319 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
321 int old = sp->fts_cwd_fd;
322 fts_assert (old != fd || old == AT_FDCWD);
326 /* Push "old" onto the ring.
327 If the displaced file descriptor is non-negative, close it. */
328 int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);
329 fd_ring_print (sp, stderr, "post-push");
330 if (0 <= prev_fd_in_slot)
331 close (prev_fd_in_slot); /* ignore any close failure */
333 else if ( ! ISSET (FTS_NOCHDIR))
336 close (old); /* ignore any close failure */
342 /* Open the directory DIR if possible, and return a file
343 descriptor. Return -1 and set errno on failure. It doesn't matter
344 whether the file descriptor has read or write access. */
348 diropen (FTS const *sp, char const *dir)
350 int open_flags = (O_SEARCH | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
351 | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0));
353 int fd = (ISSET (FTS_CWDFD)
354 ? openat (sp->fts_cwd_fd, dir, open_flags)
355 : open (dir, open_flags));
357 set_cloexec_flag (fd, true);
362 fts_open (char * const *argv,
363 register int options,
364 int (*compar) (FTSENT const **, FTSENT const **))
367 register FTSENT *p, *root;
368 register size_t nitems;
369 FTSENT *parent = NULL;
370 FTSENT *tmp = NULL; /* pacify gcc */
374 if (options & ~FTS_OPTIONMASK) {
375 __set_errno (EINVAL);
378 if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {
379 __set_errno (EINVAL);
382 if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {
383 __set_errno (EINVAL);
387 /* Allocate/initialize the stream */
388 if ((sp = malloc(sizeof(FTS))) == NULL)
390 memset(sp, 0, sizeof(FTS));
391 sp->fts_compar = compar;
392 sp->fts_options = options;
394 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
395 if (ISSET(FTS_LOGICAL)) {
400 /* Initialize fts_cwd_fd. */
401 sp->fts_cwd_fd = AT_FDCWD;
402 if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)
404 /* While it isn't technically necessary to open "." this
405 early, doing it here saves us the trouble of ensuring
406 later (where it'd be messier) that "." can in fact
407 be opened. If not, revert to FTS_NOCHDIR mode. */
408 int fd = open (".", O_SEARCH);
411 /* Even if `.' is unreadable, don't revert to FTS_NOCHDIR mode
412 on systems like Linux+PROC_FS, where our openat emulation
413 is good enough. Note: on a system that emulates
414 openat via /proc, this technique can still fail, but
415 only in extreme conditions, e.g., when the working
416 directory cannot be saved (i.e. save_cwd fails) --
417 and that happens on Linux only when "." is unreadable
418 and the CWD would be longer than PATH_MAX.
419 FIXME: once Linux kernel openat support is well established,
420 replace the above open call and this entire if/else block
421 with the body of the if-block below. */
422 if ( openat_needs_fchdir ())
435 * Start out with 1K of file name space, and enough, in any case,
436 * to hold the user's file names.
439 # define MAXPATHLEN 1024
442 size_t maxarglen = fts_maxarglen(argv);
443 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
447 /* Allocate/initialize root's parent. */
449 if ((parent = fts_alloc(sp, "", 0)) == NULL)
451 parent->fts_level = FTS_ROOTPARENTLEVEL;
454 /* The classic fts implementation would call fts_stat with
455 a new entry for each iteration of the loop below.
456 If the comparison function is not specified or if the
457 FTS_DEFER_STAT option is in effect, don't stat any entry
458 in this loop. This is an attempt to minimize the interval
459 between the initial stat/lstat/fstatat and the point at which
460 a directory argument is first opened. This matters for any
461 directory command line argument that resides on a file system
462 without genuine i-nodes. If you specify FTS_DEFER_STAT along
463 with a comparison function, that function must not access any
464 data via the fts_statp pointer. */
465 defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));
467 /* Allocate/initialize root(s). */
468 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
469 /* *Do* allow zero-length file names. */
470 size_t len = strlen(*argv);
471 if ((p = fts_alloc(sp, *argv, len)) == NULL)
473 p->fts_level = FTS_ROOTLEVEL;
474 p->fts_parent = parent;
475 p->fts_accpath = p->fts_name;
476 /* Even when defer_stat is true, be sure to stat the first
477 command line argument, since fts_read (at least with
478 FTS_XDEV) requires that. */
479 if (defer_stat && root != NULL) {
480 p->fts_info = FTS_NSOK;
481 fts_set_stat_required(p, true);
483 p->fts_info = fts_stat(sp, p, false);
487 * If comparison routine supplied, traverse in sorted
488 * order; otherwise traverse in the order specified.
503 if (compar && nitems > 1)
504 root = fts_sort(sp, root, nitems);
507 * Allocate a dummy pointer and make fts_read think that we've just
508 * finished the node before the root(s); set p->fts_info to FTS_INIT
509 * so that everything about the "current" node is ignored.
511 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
513 sp->fts_cur->fts_link = root;
514 sp->fts_cur->fts_info = FTS_INIT;
515 if (! setup_dir (sp))
519 * If using chdir(2), grab a file descriptor pointing to dot to ensure
520 * that we can get back here; this could be avoided for some file names,
521 * but almost certainly not worth the effort. Slashes, symbolic links,
522 * and ".." are all fairly nasty problems. Note, if we can't get the
523 * descriptor we run anyway, just more slowly.
525 if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)
526 && (sp->fts_rfd = diropen (sp, ".")) < 0)
529 i_ring_init (&sp->fts_fd_ring, -1);
532 mem3: fts_lfree(root);
534 mem2: free(sp->fts_path);
541 fts_load (FTS *sp, register FTSENT *p)
547 * Load the stream structure for the next traversal. Since we don't
548 * actually enter the directory until after the preorder visit, set
549 * the fts_accpath field specially so the chdir gets done to the right
550 * place and the user can access the first node. From fts_open it's
551 * known that the file name will fit.
553 len = p->fts_pathlen = p->fts_namelen;
554 memmove(sp->fts_path, p->fts_name, len + 1);
555 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
557 memmove(p->fts_name, cp, len + 1);
558 p->fts_namelen = len;
560 p->fts_accpath = p->fts_path = sp->fts_path;
566 register FTSENT *freep, *p;
570 * This still works if we haven't read anything -- the dummy structure
571 * points to the root list, so we step through to the end of the root
572 * list which has a valid parent pointer.
575 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
577 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
583 /* Free up child linked list, sort array, file name buffer. */
585 fts_lfree(sp->fts_child);
589 if (ISSET(FTS_CWDFD))
591 if (0 <= sp->fts_cwd_fd)
592 if (close (sp->fts_cwd_fd))
595 else if (!ISSET(FTS_NOCHDIR))
597 /* Return to original directory, save errno if necessary. */
598 if (fchdir(sp->fts_rfd))
601 /* If close fails, record errno only if saved_errno is zero,
602 so that we report the probably-more-meaningful fchdir errno. */
603 if (close (sp->fts_rfd))
604 if (saved_errno == 0)
608 fd_ring_clear (&sp->fts_fd_ring);
610 if (sp->fts_leaf_optimization_works_ht)
611 hash_free (sp->fts_leaf_optimization_works_ht);
615 /* Free up the stream pointer. */
618 /* Set errno and return. */
620 __set_errno (saved_errno);
627 #if defined __linux__ \
628 && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
632 /* Linux-specific constants from coreutils' src/fs.h */
633 # define S_MAGIC_TMPFS 0x1021994
634 # define S_MAGIC_NFS 0x6969
635 # define S_MAGIC_REISERFS 0x52654973
636 # define S_MAGIC_PROC 0x9FA0
638 /* Return false if it is easy to determine the file system type of
639 the directory on which DIR_FD is open, and sorting dirents on
640 inode numbers is known not to improve traversal performance with
641 that type of file system. Otherwise, return true. */
643 dirent_inode_sort_may_be_useful (int dir_fd)
645 /* Skip the sort only if we can determine efficiently
646 that skipping it is the right thing to do.
647 The cost of performing an unnecessary sort is negligible,
648 while the cost of *not* performing it can be O(N^2) with
649 a very large constant. */
650 struct statfs fs_buf;
652 /* If fstatfs fails, assume sorting would be useful. */
653 if (fstatfs (dir_fd, &fs_buf) != 0)
656 /* FIXME: what about when f_type is not an integral type?
657 deal with that if/when it's encountered. */
658 switch (fs_buf.f_type)
662 /* On a file system of any of these types, sorting
663 is unnecessary, and hence wasteful. */
671 /* Given a file descriptor DIR_FD open on a directory D,
672 return true if it is valid to apply the leaf-optimization
673 technique of counting directories in D via stat.st_nlink. */
675 leaf_optimization_applies (int dir_fd)
677 struct statfs fs_buf;
679 /* If fstatfs fails, assume we can't use the optimization. */
680 if (fstatfs (dir_fd, &fs_buf) != 0)
683 /* FIXME: do we need to detect AFS mount points? I doubt it,
684 unless fstatfs can report S_MAGIC_REISERFS for such a directory. */
686 switch (fs_buf.f_type)
688 /* List here the file system types that lack useable dirent.d_type
689 info, yet for which the optimization does apply. */
690 case S_MAGIC_REISERFS:
694 /* Explicitly listing this or any other file system type for which
695 the optimization is not applicable is not necessary, but we leave
696 it here to document the risk. Per http://bugs.debian.org/143111,
697 /proc may have bogus stat.st_nlink values. */
706 dirent_inode_sort_may_be_useful (int dir_fd _GL_UNUSED) { return true; }
708 leaf_optimization_applies (int dir_fd _GL_UNUSED) { return false; }
711 /* link-count-optimization entry:
712 map an stat.st_dev number to a boolean: leaf_optimization_works */
719 /* Use a tiny initial size. If a traversal encounters more than
720 a few devices, the cost of growing/rehashing this table will be
721 rendered negligible by the number of inodes processed. */
722 enum { LCO_HT_INITIAL_SIZE = 13 };
725 LCO_hash (void const *x, size_t table_size)
727 struct LCO_ent const *ax = x;
728 return (uintmax_t) ax->st_dev % table_size;
732 LCO_compare (void const *x, void const *y)
734 struct LCO_ent const *ax = x;
735 struct LCO_ent const *ay = y;
736 return ax->st_dev == ay->st_dev;
739 /* Ask the same question as leaf_optimization_applies, but query
740 the cache first (FTS.fts_leaf_optimization_works_ht), and if necessary,
741 update that cache. */
743 link_count_optimize_ok (FTSENT const *p)
745 FTS *sp = p->fts_fts;
746 Hash_table *h = sp->fts_leaf_optimization_works_ht;
752 /* If we're not in CWDFD mode, don't bother with this optimization,
753 since the caller is not serious about performance. */
754 if (!ISSET(FTS_CWDFD))
757 /* map st_dev to the boolean, leaf_optimization_works */
760 h = sp->fts_leaf_optimization_works_ht
761 = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash,
766 tmp.st_dev = p->fts_statp->st_dev;
767 ent = hash_lookup (h, &tmp);
771 /* Look-up failed. Query directly and cache the result. */
772 t2 = malloc (sizeof *t2);
776 /* Is it ok to perform the optimization in the dir, FTS_CWD_FD? */
777 opt_ok = leaf_optimization_applies (sp->fts_cwd_fd);
779 t2->st_dev = p->fts_statp->st_dev;
781 ent = hash_insert (h, t2);
784 /* insertion failed */
788 fts_assert (ent == t2);
794 * Special case of "/" at the end of the file name so that slashes aren't
795 * appended which would cause file names to be written as "....//foo".
798 (p->fts_path[p->fts_pathlen - 1] == '/' \
799 ? p->fts_pathlen - 1 : p->fts_pathlen)
802 fts_read (register FTS *sp)
804 register FTSENT *p, *tmp;
805 register unsigned short int instr;
808 /* If finished or unrecoverable error, return NULL. */
809 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
812 /* Set current node pointer. */
815 /* Save and zero out user instructions. */
816 instr = p->fts_instr;
817 p->fts_instr = FTS_NOINSTR;
819 /* Any type of file may be re-visited; re-stat and re-turn. */
820 if (instr == FTS_AGAIN) {
821 p->fts_info = fts_stat(sp, p, false);
824 Dprintf (("fts_read: p=%s\n",
825 p->fts_info == FTS_INIT ? "" : p->fts_path));
828 * Following a symlink -- SLNONE test allows application to see
829 * SLNONE and recover. If indirecting through a symlink, have
830 * keep a pointer to current location. If unable to get that
831 * pointer, follow fails.
833 if (instr == FTS_FOLLOW &&
834 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
835 p->fts_info = fts_stat(sp, p, true);
836 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
837 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
838 p->fts_errno = errno;
839 p->fts_info = FTS_ERR;
841 p->fts_flags |= FTS_SYMFOLLOW;
846 /* Directory in pre-order. */
847 if (p->fts_info == FTS_D) {
848 /* If skipped or crossed mount point, do post-order visit. */
849 if (instr == FTS_SKIP ||
850 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
851 if (p->fts_flags & FTS_SYMFOLLOW)
852 (void)close(p->fts_symfd);
854 fts_lfree(sp->fts_child);
855 sp->fts_child = NULL;
857 p->fts_info = FTS_DP;
858 LEAVE_DIR (sp, p, "1");
862 /* Rebuild if only read the names and now traversing. */
863 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
865 fts_lfree(sp->fts_child);
866 sp->fts_child = NULL;
870 * Cd to the subdirectory.
872 * If have already read and now fail to chdir, whack the list
873 * to make the names come out right, and set the parent errno
874 * so the application will eventually get an error condition.
875 * Set the FTS_DONTCHDIR flag so that when we logically change
876 * directories back to the parent we don't do a chdir.
878 * If haven't read do so. If the read fails, fts_build sets
879 * FTS_STOP or the fts_info field of the node.
881 if (sp->fts_child != NULL) {
882 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
883 p->fts_errno = errno;
884 p->fts_flags |= FTS_DONTCHDIR;
885 for (p = sp->fts_child; p != NULL;
888 p->fts_parent->fts_accpath;
890 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
893 /* If fts_build's call to fts_safe_changedir failed
894 because it was not able to fchdir into a
895 subdirectory, tell the caller. */
896 if (p->fts_errno && p->fts_info != FTS_DNR)
897 p->fts_info = FTS_ERR;
898 LEAVE_DIR (sp, p, "2");
902 sp->fts_child = NULL;
906 /* Move to the next node on this level. */
908 if ((p = p->fts_link) != NULL) {
913 * If reached the top, return to the original directory (or
914 * the root of the tree), and load the file names for the next
917 if (p->fts_level == FTS_ROOTLEVEL) {
918 if (RESTORE_INITIAL_CWD(sp)) {
929 * User may have called fts_set on the node. If skipped,
930 * ignore. If followed, get a file descriptor so we can
931 * get back if necessary.
933 if (p->fts_instr == FTS_SKIP)
935 if (p->fts_instr == FTS_FOLLOW) {
936 p->fts_info = fts_stat(sp, p, true);
937 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
938 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
939 p->fts_errno = errno;
940 p->fts_info = FTS_ERR;
942 p->fts_flags |= FTS_SYMFOLLOW;
944 p->fts_instr = FTS_NOINSTR;
947 name: t = sp->fts_path + NAPPEND(p->fts_parent);
949 memmove(t, p->fts_name, p->fts_namelen + 1);
952 if (p->fts_info == FTS_NSOK)
954 if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
956 FTSENT *parent = p->fts_parent;
957 if (FTS_ROOTLEVEL < p->fts_level
958 /* ->fts_n_dirs_remaining is not valid
959 for command-line-specified names. */
960 && parent->fts_n_dirs_remaining == 0
962 && ISSET(FTS_PHYSICAL)
963 && link_count_optimize_ok (parent))
965 /* nothing more needed */
969 p->fts_info = fts_stat(sp, p, false);
970 if (S_ISDIR(p->fts_statp->st_mode)
971 && p->fts_level != FTS_ROOTLEVEL
972 && parent->fts_n_dirs_remaining)
973 parent->fts_n_dirs_remaining--;
977 fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
980 if (p->fts_info == FTS_D)
982 /* Now that P->fts_statp is guaranteed to be valid,
983 if this is a command-line directory, record its
984 device number, to be used for FTS_XDEV. */
985 if (p->fts_level == FTS_ROOTLEVEL)
986 sp->fts_dev = p->fts_statp->st_dev;
987 Dprintf ((" entering: %s\n", p->fts_path));
988 if (! enter_dir (sp, p))
990 __set_errno (ENOMEM);
997 /* Move up to the parent node. */
1002 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
1004 * Done; free everything up and set errno to 0 so the user
1005 * can distinguish between error and EOF.
1009 return (sp->fts_cur = NULL);
1012 fts_assert (p->fts_info != FTS_NSOK);
1014 /* NUL terminate the file name. */
1015 sp->fts_path[p->fts_pathlen] = '\0';
1018 * Return to the parent directory. If at a root node, restore
1019 * the initial working directory. If we came through a symlink,
1020 * go back through the file descriptor. Otherwise, move up
1021 * one level, via "..".
1023 if (p->fts_level == FTS_ROOTLEVEL) {
1024 if (RESTORE_INITIAL_CWD(sp)) {
1025 p->fts_errno = errno;
1028 } else if (p->fts_flags & FTS_SYMFOLLOW) {
1029 if (FCHDIR(sp, p->fts_symfd)) {
1030 int saved_errno = errno;
1031 (void)close(p->fts_symfd);
1032 __set_errno (saved_errno);
1033 p->fts_errno = errno;
1036 (void)close(p->fts_symfd);
1037 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
1038 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
1039 p->fts_errno = errno;
1042 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
1043 if (p->fts_errno == 0)
1044 LEAVE_DIR (sp, p, "3");
1045 return ISSET(FTS_STOP) ? NULL : p;
1049 * Fts_set takes the stream as an argument although it's not used in this
1050 * implementation; it would be necessary if anyone wanted to add global
1051 * semantics to fts using fts_set. An error return is allowed for similar
1056 fts_set(FTS *sp _GL_UNUSED, FTSENT *p, int instr)
1058 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
1059 instr != FTS_NOINSTR && instr != FTS_SKIP) {
1060 __set_errno (EINVAL);
1063 p->fts_instr = instr;
1068 fts_children (register FTS *sp, int instr)
1073 if (instr != 0 && instr != FTS_NAMEONLY) {
1074 __set_errno (EINVAL);
1078 /* Set current node pointer. */
1082 * Errno set to 0 so user can distinguish empty directory from
1087 /* Fatal errors stop here. */
1088 if (ISSET(FTS_STOP))
1091 /* Return logical hierarchy of user's arguments. */
1092 if (p->fts_info == FTS_INIT)
1093 return (p->fts_link);
1096 * If not a directory being visited in pre-order, stop here. Could
1097 * allow FTS_DNR, assuming the user has fixed the problem, but the
1098 * same effect is available with FTS_AGAIN.
1100 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
1103 /* Free up any previous child list. */
1104 if (sp->fts_child != NULL)
1105 fts_lfree(sp->fts_child);
1107 if (instr == FTS_NAMEONLY) {
1114 * If using chdir on a relative file name and called BEFORE fts_read
1115 * does its chdir to the root of a traversal, we can lose -- we need to
1116 * chdir into the subdirectory, and we don't know where the current
1117 * directory is, so we can't get back so that the upcoming chdir by
1118 * fts_read will work.
1120 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
1122 return (sp->fts_child = fts_build(sp, instr));
1124 if ((fd = diropen (sp, ".")) < 0)
1125 return (sp->fts_child = NULL);
1126 sp->fts_child = fts_build(sp, instr);
1127 if (ISSET(FTS_CWDFD))
1129 cwd_advance_fd (sp, fd, true);
1135 int saved_errno = errno;
1137 __set_errno (saved_errno);
1142 return (sp->fts_child);
1145 /* A comparison function to sort on increasing inode number.
1146 For some file system types, sorting either way makes a huge
1147 performance difference for a directory with very many entries,
1148 but sorting on increasing values is slightly better than sorting
1149 on decreasing values. The difference is in the 5% range. */
1151 fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b)
1153 return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? -1
1154 : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? 1 : 0);
1157 /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode
1158 S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */
1160 set_stat_type (struct stat *st, unsigned int dtype)
1193 * This is the tricky part -- do not casually change *anything* in here. The
1194 * idea is to build the linked list of entries that are used by fts_children
1195 * and fts_read. There are lots of special cases.
1197 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
1198 * set and it's a physical walk (so that symbolic links can't be directories),
1199 * we can do things quickly. First, if it's a 4.4BSD file system, the type
1200 * of the file is in the directory entry. Otherwise, we assume that the number
1201 * of subdirectories in a node is equal to the number of links to the parent.
1202 * The former skips all stat calls. The latter skips stat calls in any leaf
1203 * directories and for any files after the subdirectories in the directory have
1204 * been found, cutting the stat calls by about 2/3.
1208 fts_build (register FTS *sp, int type)
1210 register struct dirent *dp;
1211 register FTSENT *p, *head;
1212 register size_t nitems;
1222 size_t len, maxlen, new_len;
1225 /* Set current node pointer. */
1229 * Open the directory for reading. If this fails, we're done.
1230 * If being called from fts_read, set the fts_info field.
1232 #if defined FTS_WHITEOUT && 0
1233 if (ISSET(FTS_WHITEOUT))
1234 oflag = DTF_NODUP|DTF_REWIND;
1236 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
1238 # define __opendir2(file, flag) \
1239 ( ! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
1240 ? opendirat(sp->fts_cwd_fd, file) \
1243 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
1244 if (type == BREAD) {
1245 cur->fts_info = FTS_DNR;
1246 cur->fts_errno = errno;
1250 /* Rather than calling fts_stat for each and every entry encountered
1251 in the readdir loop (below), stat each directory only right after
1253 if (cur->fts_info == FTS_NSOK)
1254 cur->fts_info = fts_stat(sp, cur, false);
1255 else if (sp->fts_options & FTS_TIGHT_CYCLE_CHECK) {
1256 /* Now read the stat info again after opening a directory to
1257 * reveal eventual changes caused by a submount triggered by
1258 * the traversal. But do it only for utilities which use
1259 * FTS_TIGHT_CYCLE_CHECK. Therefore, only find and du
1260 * benefit/suffer from this feature for now.
1262 LEAVE_DIR (sp, cur, "4");
1263 fts_stat (sp, cur, false);
1264 if (! enter_dir (sp, cur)) {
1265 __set_errno (ENOMEM);
1271 * Nlinks is the number of possible entries of type directory in the
1272 * directory if we're cheating on stat calls, 0 if we're not doing
1273 * any stat calls at all, (nlink_t) -1 if we're statting everything.
1275 if (type == BNAMES) {
1277 /* Be quiet about nostat, GCC. */
1279 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
1280 nlinks = (cur->fts_statp->st_nlink
1281 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1289 * If we're going to need to stat anything or we want to descend
1290 * and stay in the directory, chdir. If this fails we keep going,
1291 * but set a flag so we don't chdir after the post-order visit.
1292 * We won't be able to stat anything, but we can still return the
1293 * names themselves. Note, that since fts_read won't be able to
1294 * chdir into the directory, it will have to return different file
1295 * names than before, i.e. "a/b" instead of "b". Since the node
1296 * has already been visited in pre-order, have to wait until the
1297 * post-order visit to return the error. There is a special case
1298 * here, if there was nothing to stat then it's not an error to
1299 * not be able to stat. This is all fairly nasty. If a program
1300 * needed sorted entries or stat information, they had better be
1301 * checking FTS_NS on the returned nodes.
1303 if (nlinks || type == BREAD) {
1304 int dir_fd = dirfd(dirp);
1305 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1307 dir_fd = dup (dir_fd);
1308 set_cloexec_flag (dir_fd, true);
1310 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
1311 if (nlinks && type == BREAD)
1312 cur->fts_errno = errno;
1313 cur->fts_flags |= FTS_DONTCHDIR;
1316 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1325 * Figure out the max file name length that can be stored in the
1326 * current buffer -- the inner loop allocates more space as necessary.
1327 * We really wouldn't have to do the maxlen calculations here, we
1328 * could do them in fts_read before returning the name, but it's a
1329 * lot easier here since the length is part of the dirent structure.
1331 * If not changing directories set a pointer so that can just append
1332 * each new component into the file name.
1335 if (ISSET(FTS_NOCHDIR)) {
1336 cp = sp->fts_path + len;
1339 /* GCC, you're too verbose. */
1343 maxlen = sp->fts_pathlen - len;
1345 level = cur->fts_level + 1;
1347 /* Read the directory, attaching each entry to the `link' pointer. */
1349 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
1352 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1355 if ((p = fts_alloc (sp, dp->d_name,
1356 _D_EXACT_NAMLEN (dp))) == NULL)
1358 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
1359 /* include space for NUL */
1360 oldaddr = sp->fts_path;
1361 if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
1363 * No more memory. Save
1364 * errno, free up the current structure and the
1365 * structures already allocated.
1367 mem1: saved_errno = errno;
1371 cur->fts_info = FTS_ERR;
1373 __set_errno (saved_errno);
1376 /* Did realloc() change the pointer? */
1377 if (oldaddr != sp->fts_path) {
1379 if (ISSET(FTS_NOCHDIR))
1380 cp = sp->fts_path + len;
1382 maxlen = sp->fts_pathlen - len;
1385 new_len = len + _D_EXACT_NAMLEN (dp);
1386 if (new_len < len) {
1388 * In the unlikely event that we would end up
1389 * with a file name longer than SIZE_MAX, free up
1390 * the current structure and the structures already
1391 * allocated, then error out with ENAMETOOLONG.
1396 cur->fts_info = FTS_ERR;
1398 __set_errno (ENAMETOOLONG);
1401 p->fts_level = level;
1402 p->fts_parent = sp->fts_cur;
1403 p->fts_pathlen = new_len;
1405 #if defined FTS_WHITEOUT && 0
1406 if (dp->d_type == DT_WHT)
1407 p->fts_flags |= FTS_ISW;
1409 /* Store dirent.d_ino, in case we need to sort
1410 entries before processing them. */
1411 p->fts_statp->st_ino = D_INO (dp);
1413 /* Build a file name for fts_stat to stat. */
1414 if (ISSET(FTS_NOCHDIR)) {
1415 p->fts_accpath = p->fts_path;
1416 memmove(cp, p->fts_name, p->fts_namelen + 1);
1418 p->fts_accpath = p->fts_name;
1420 if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {
1421 /* Record what fts_read will have to do with this
1422 entry. In many cases, it will simply fts_stat it,
1423 but we can take advantage of any d_type information
1424 to optimize away the unnecessary stat calls. I.e.,
1425 if FTS_NOSTAT is in effect and we're not following
1426 symlinks (FTS_PHYSICAL) and d_type indicates this
1427 is *not* a directory, then we won't have to stat it
1428 at all. If it *is* a directory, then (currently)
1429 we stat it regardless, in order to get device and
1430 inode numbers. Some day we might optimize that
1431 away, too, for directories where d_ino is known to
1433 bool skip_stat = (ISSET(FTS_PHYSICAL)
1434 && ISSET(FTS_NOSTAT)
1436 && ! DT_MUST_BE(dp, DT_DIR));
1437 p->fts_info = FTS_NSOK;
1438 /* Propagate dirent.d_type information back
1439 to caller, when possible. */
1440 set_stat_type (p->fts_statp, D_TYPE (dp));
1441 fts_set_stat_required(p, !skip_stat);
1442 is_dir = (ISSET(FTS_PHYSICAL)
1443 && DT_MUST_BE(dp, DT_DIR));
1445 p->fts_info = fts_stat(sp, p, false);
1446 is_dir = (p->fts_info == FTS_D
1447 || p->fts_info == FTS_DC
1448 || p->fts_info == FTS_DOT);
1451 /* Decrement link count if applicable. */
1452 if (nlinks > 0 && is_dir)
1455 /* We walk in directory order so "ls -f" doesn't get upset. */
1469 * If realloc() changed the address of the file name, adjust the
1470 * addresses for the rest of the tree and the dir list.
1473 fts_padjust(sp, head);
1476 * If not changing directories, reset the file name back to original
1479 if (ISSET(FTS_NOCHDIR)) {
1480 if (len == sp->fts_pathlen || nitems == 0)
1486 * If descended after called from fts_children or after called from
1487 * fts_read and nothing found, get back. At the root level we use
1488 * the saved fd; if one of fts_open()'s arguments is a relative name
1489 * to an empty directory, we wind up here with no other way back. If
1490 * can't get back, we're done.
1492 if (descend && (type == BCHILD || !nitems) &&
1493 (cur->fts_level == FTS_ROOTLEVEL
1494 ? RESTORE_INITIAL_CWD(sp)
1495 : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1496 cur->fts_info = FTS_ERR;
1502 /* If didn't find anything, return NULL. */
1505 cur->fts_info = FTS_DP;
1510 /* If there are many entries, no sorting function has been specified,
1511 and this file system is of a type that may be slow with a large
1512 number of entries, then sort the directory entries on increasing
1514 if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
1516 && ISSET (FTS_CWDFD)
1517 && dirent_inode_sort_may_be_useful (sp->fts_cwd_fd)) {
1518 sp->fts_compar = fts_compare_ino;
1519 head = fts_sort (sp, head, nitems);
1520 sp->fts_compar = NULL;
1523 /* Sort the entries. */
1524 if (sp->fts_compar && nitems > 1)
1525 head = fts_sort(sp, head, nitems);
1531 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1532 current hierarchy. There should be a directory with dev/inode
1533 matching those of AD. If not, print a lot of diagnostics. */
1535 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1538 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1540 if (ad->ino == ent->fts_statp->st_ino
1541 && ad->dev == ent->fts_statp->st_dev)
1544 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1545 printf ("active dirs:\n");
1547 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1548 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1549 ad->fts_ent->fts_accpath,
1550 (uintmax_t) ad->dev,
1551 (uintmax_t) ad->ino,
1553 (uintmax_t) ent->fts_statp->st_dev,
1554 (uintmax_t) ent->fts_statp->st_ino);
1558 fts_cross_check (FTS const *sp)
1560 FTSENT const *ent = sp->fts_cur;
1562 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1565 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1566 /* Make sure every parent dir is in the tree. */
1567 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1569 struct Active_dir ad;
1570 ad.ino = t->fts_statp->st_ino;
1571 ad.dev = t->fts_statp->st_dev;
1572 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1573 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1576 /* Make sure every dir in the tree is an active dir.
1577 But ENT is not necessarily a directory. If so, just skip this part. */
1578 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1579 && (ent->fts_info == FTS_DP
1580 || ent->fts_info == FTS_D))
1582 struct Active_dir *ad;
1583 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1584 ad = hash_get_next (sp->fts_cycle.ht, ad))
1586 find_matching_ancestor (ent, ad);
1592 same_fd (int fd1, int fd2)
1594 struct stat sb1, sb2;
1595 return (fstat (fd1, &sb1) == 0
1596 && fstat (fd2, &sb2) == 0
1597 && SAME_INODE (sb1, sb2));
1601 fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
1603 I_ring const *fd_ring = &sp->fts_fd_ring;
1604 unsigned int i = fd_ring->fts_front;
1605 char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0);
1606 fprintf (stream, "=== %s ========== %s\n", msg, cwd);
1608 if (i_ring_empty (fd_ring))
1613 int fd = fd_ring->fts_fd_ring[i];
1615 fprintf (stream, "%d: %d:\n", i, fd);
1618 char *wd = getcwdat (fd, NULL, 0);
1619 fprintf (stream, "%d: %d: %s\n", i, fd, wd);
1622 if (i == fd_ring->fts_back)
1624 i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
1628 /* Ensure that each file descriptor on the fd_ring matches a
1629 parent, grandparent, etc. of the current working directory. */
1631 fd_ring_check (FTS const *sp)
1636 /* Make a writable copy. */
1637 I_ring fd_w = sp->fts_fd_ring;
1639 int cwd_fd = sp->fts_cwd_fd;
1640 cwd_fd = dup (cwd_fd);
1641 char *dot = getcwdat (cwd_fd, NULL, 0);
1642 error (0, 0, "===== check ===== cwd: %s", dot);
1644 while ( ! i_ring_empty (&fd_w))
1646 int fd = i_ring_pop (&fd_w);
1649 int parent_fd = openat (cwd_fd, "..", O_SEARCH);
1655 if (!same_fd (fd, parent_fd))
1657 char *cwd = getcwdat (fd, NULL, 0);
1658 error (0, errno, "ring : %s", cwd);
1659 char *c2 = getcwdat (parent_fd, NULL, 0);
1660 error (0, errno, "parent: %s", c2);
1673 static unsigned short int
1675 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1677 struct stat *sbp = p->fts_statp;
1680 if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
1683 #if defined FTS_WHITEOUT && 0
1684 /* check for whiteout */
1685 if (p->fts_flags & FTS_ISW) {
1686 memset(sbp, '\0', sizeof (*sbp));
1687 sbp->st_mode = S_IFWHT;
1693 * If doing a logical walk, or application requested FTS_FOLLOW, do
1694 * a stat(2). If that fails, check for a non-existent symlink. If
1695 * fail, set the errno from the stat call.
1697 if (ISSET(FTS_LOGICAL) || follow) {
1698 if (stat(p->fts_accpath, sbp)) {
1699 saved_errno = errno;
1701 && lstat(p->fts_accpath, sbp) == 0) {
1703 return (FTS_SLNONE);
1705 p->fts_errno = saved_errno;
1708 } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp,
1709 AT_SYMLINK_NOFOLLOW)) {
1710 p->fts_errno = errno;
1711 err: memset(sbp, 0, sizeof(struct stat));
1715 if (S_ISDIR(sbp->st_mode)) {
1716 p->fts_n_dirs_remaining = (sbp->st_nlink
1717 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1718 if (ISDOT(p->fts_name)) {
1719 /* Command-line "." and ".." are real directories. */
1720 return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
1725 if (S_ISLNK(sbp->st_mode))
1727 if (S_ISREG(sbp->st_mode))
1729 return (FTS_DEFAULT);
1733 fts_compar (void const *a, void const *b)
1735 /* Convert A and B to the correct types, to pacify the compiler, and
1736 for portability to bizarre hosts where "void const *" and "FTSENT
1737 const **" differ in runtime representation. The comparison
1738 function cannot modify *a and *b, but there is no compile-time
1740 FTSENT const **pa = (FTSENT const **) a;
1741 FTSENT const **pb = (FTSENT const **) b;
1742 return pa[0]->fts_fts->fts_compar (pa, pb);
1747 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1749 register FTSENT **ap, *p;
1751 /* On most modern hosts, void * and FTSENT ** have the same
1752 run-time representation, and one can convert sp->fts_compar to
1753 the type qsort expects without problem. Use the heuristic that
1754 this is OK if the two pointer types are the same size, and if
1755 converting FTSENT ** to long int is the same as converting
1756 FTSENT ** to void * and then to long int. This heuristic isn't
1757 valid in general but we don't know of any counterexamples. */
1759 int (*compare) (void const *, void const *) =
1760 ((sizeof &dummy == sizeof (void *)
1761 && (long int) &dummy == (long int) (void *) &dummy)
1762 ? (int (*) (void const *, void const *)) sp->fts_compar
1766 * Construct an array of pointers to the structures and call qsort(3).
1767 * Reassemble the array in the order returned by qsort. If unable to
1768 * sort for memory reasons, return the directory entries in their
1769 * current order. Allocate enough space for the current needs plus
1770 * 40 so don't realloc one entry at a time.
1772 if (nitems > sp->fts_nitems) {
1775 sp->fts_nitems = nitems + 40;
1776 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1777 || ! (a = realloc (sp->fts_array,
1778 sp->fts_nitems * sizeof *a))) {
1779 free(sp->fts_array);
1780 sp->fts_array = NULL;
1786 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1788 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1789 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1790 ap[0]->fts_link = ap[1];
1791 ap[0]->fts_link = NULL;
1797 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1803 * The file name is a variable length array. Allocate the FTSENT
1804 * structure and the file name in one chunk.
1806 len = sizeof(FTSENT) + namelen;
1807 if ((p = malloc(len)) == NULL)
1810 /* Copy the name and guarantee NUL termination. */
1811 memmove(p->fts_name, name, namelen);
1812 p->fts_name[namelen] = '\0';
1814 p->fts_namelen = namelen;
1816 p->fts_path = sp->fts_path;
1819 p->fts_instr = FTS_NOINSTR;
1821 p->fts_pointer = NULL;
1827 fts_lfree (register FTSENT *head)
1831 /* Free a linked list of structures. */
1832 while ((p = head)) {
1833 head = head->fts_link;
1839 * Allow essentially unlimited file name lengths; find, rm, ls should
1840 * all work on any tree. Most systems will allow creation of file
1841 * names much longer than MAXPATHLEN, even though the kernel won't
1842 * resolve them. Add the size (not just what's needed) plus 256 bytes
1843 * so don't realloc the file name 2 bytes at a time.
1847 fts_palloc (FTS *sp, size_t more)
1850 size_t new_len = sp->fts_pathlen + more + 256;
1853 * See if fts_pathlen would overflow.
1855 if (new_len < sp->fts_pathlen) {
1857 sp->fts_path = NULL;
1858 __set_errno (ENAMETOOLONG);
1861 sp->fts_pathlen = new_len;
1862 p = realloc(sp->fts_path, sp->fts_pathlen);
1865 sp->fts_path = NULL;
1873 * When the file name is realloc'd, have to fix all of the pointers in
1874 * structures already returned.
1878 fts_padjust (FTS *sp, FTSENT *head)
1881 char *addr = sp->fts_path;
1883 #define ADJUST(p) do { \
1884 if ((p)->fts_accpath != (p)->fts_name) { \
1885 (p)->fts_accpath = \
1886 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1888 (p)->fts_path = addr; \
1890 /* Adjust the current set of children. */
1891 for (p = sp->fts_child; p; p = p->fts_link)
1894 /* Adjust the rest of the tree, including the current level. */
1895 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1897 p = p->fts_link ? p->fts_link : p->fts_parent;
1903 fts_maxarglen (char * const *argv)
1907 for (max = 0; *argv; ++argv)
1908 if ((len = strlen(*argv)) > max)
1914 * Change to dir specified by fd or file name without getting
1915 * tricked by someone changing the world out from underneath us.
1916 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1917 * If FD is non-negative, expect it to be used after this function returns,
1918 * and to be closed eventually. So don't pass e.g., `dirfd(dirp)' and then
1919 * do closedir(dirp), because that would invalidate the saved FD.
1920 * Upon failure, close FD immediately and return nonzero.
1924 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1927 bool is_dotdot = dir && STREQ (dir, "..");
1930 /* This clause handles the unusual case in which FTS_NOCHDIR
1931 is specified, along with FTS_CWDFD. In that case, there is
1932 no need to change even the virtual cwd file descriptor.
1933 However, if FD is non-negative, we do close it here. */
1934 if (ISSET (FTS_NOCHDIR))
1936 if (ISSET (FTS_CWDFD) && 0 <= fd)
1941 if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
1943 /* When possible, skip the diropen and subsequent fstat+dev/ino
1944 comparison. I.e., when changing to parent directory
1945 (chdir ("..")), use a file descriptor from the ring and
1946 save the overhead of diropen+fstat, as well as avoiding
1947 failure when we lack "x" access to the virtual cwd. */
1948 if ( ! i_ring_empty (&sp->fts_fd_ring))
1951 fd_ring_print (sp, stderr, "pre-pop");
1952 parent_fd = i_ring_pop (&sp->fts_fd_ring);
1963 if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
1966 /* The following dev/inode check is necessary if we're doing a
1967 `logical' traversal (through symlinks, a la chown -L), if the
1968 system lacks O_NOFOLLOW support, or if we're changing to ".."
1969 (but not via a popped file descriptor). When changing to the
1970 name "..", O_NOFOLLOW can't help. In general, when the target is
1971 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
1972 follow a symlink, so we can avoid the expense of this fstat. */
1973 if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
1974 || (dir && STREQ (dir, "..")))
1977 if (fstat(newfd, &sb))
1982 if (p->fts_statp->st_dev != sb.st_dev
1983 || p->fts_statp->st_ino != sb.st_ino)
1985 __set_errno (ENOENT); /* disinformation */
1991 if (ISSET(FTS_CWDFD))
1993 cwd_advance_fd (sp, newfd, ! is_dotdot);
1997 ret = fchdir(newfd);
2003 __set_errno (oerrno);