1 /* Traverse a file hierarchy.
3 Copyright (C) 2004, 2005, 2006, 2007 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 2, or (at your option)
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, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
20 * Copyright (c) 1990, 1993, 1994
21 * The Regents of the University of California. All rights reserved.
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
26 * 1. Redistributions of source code must retain the above copyright
27 * notice, this list of conditions and the following disclaimer.
28 * 2. Redistributions in binary form must reproduce the above copyright
29 * notice, this list of conditions and the following disclaimer in the
30 * documentation and/or other materials provided with the distribution.
31 * 4. Neither the name of the University nor the names of its contributors
32 * may be used to endorse or promote products derived from this software
33 * without specific prior written permission.
35 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
36 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
37 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
38 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
39 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
40 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
41 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
42 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
43 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
44 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50 #if defined(LIBC_SCCS) && !defined(lint)
51 static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94";
52 #endif /* LIBC_SCCS and not lint */
56 #if HAVE_SYS_PARAM_H || defined _LIBC
57 # include <sys/param.h>
60 # include <include/sys/stat.h>
62 # include <sys/stat.h>
76 # include "unistd--.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))
91 # define DT_IS_KNOWN(d) false
92 # define DT_MUST_BE(d, t) false
97 FTS_NO_STAT_REQUIRED = 1,
103 # define close __close
105 # define closedir __closedir
107 # define fchdir __fchdir
111 # define opendir __opendir
113 # define readdir __readdir
115 # undef internal_function
116 # define internal_function /* empty */
120 # define __set_errno(Val) errno = (Val)
123 #ifndef __attribute__
124 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
125 # define __attribute__(x) /* empty */
129 #ifndef ATTRIBUTE_UNUSED
130 # define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
133 /* If this host provides the openat function, then we can avoid
134 attempting to open "." in some initialization code below. */
136 # define HAVE_OPENAT_SUPPORT 1
138 # define HAVE_OPENAT_SUPPORT 0
142 # define fts_assert(expr) ((void) 0)
144 # define fts_assert(expr) \
153 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
154 static FTSENT *fts_build (FTS *, int) internal_function;
155 static void fts_lfree (FTSENT *) internal_function;
156 static void fts_load (FTS *, FTSENT *) internal_function;
157 static size_t fts_maxarglen (char * const *) internal_function;
158 static void fts_padjust (FTS *, FTSENT *) internal_function;
159 static bool fts_palloc (FTS *, size_t) internal_function;
160 static FTSENT *fts_sort (FTS *, FTSENT *, size_t) internal_function;
161 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
162 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
166 # include "fts-cycle.c"
168 static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
169 static void leave_dir (FTS *fts, FTSENT *ent) {}
170 static bool setup_dir (FTS *fts) { return true; }
171 static void free_dir (FTS *fts) {}
175 # define MAX(a,b) ((a) > (b) ? (a) : (b))
179 # define SIZE_MAX ((size_t) -1)
183 # define O_DIRECTORY 0
186 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
187 #define STREQ(a, b) (strcmp ((a), (b)) == 0)
189 #define CLR(opt) (sp->fts_options &= ~(opt))
190 #define ISSET(opt) (sp->fts_options & (opt))
191 #define SET(opt) (sp->fts_options |= (opt))
193 /* FIXME: make this a function */
194 #define RESTORE_INITIAL_CWD(sp) \
195 (fd_ring_clear (&((sp)->fts_fd_ring)), \
196 FCHDIR ((sp), (ISSET (FTS_CWDFD) ? AT_FDCWD : (sp)->fts_rfd)))
198 /* FIXME: FTS_NOCHDIR is now misnamed.
199 Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
200 #define FCHDIR(sp, fd) \
201 (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \
202 ? (cwd_advance_fd ((sp), (fd), true), 0) \
206 /* fts_build flags */
207 /* FIXME: make this an enum */
208 #define BCHILD 1 /* fts_children */
209 #define BNAMES 2 /* fts_children, names only */
210 #define BREAD 3 /* fts_read */
213 # include <inttypes.h>
216 # include "getcwdat.h"
217 bool fts_debug = false;
218 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
221 # define fd_ring_check(x)
222 # define fd_ring_print(a, b, c)
225 #define LEAVE_DIR(Fts, Ent, Tag) \
228 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
229 leave_dir (Fts, Ent); \
230 fd_ring_check (Fts); \
235 fd_ring_clear (I_ring *fd_ring)
237 while ( ! i_ring_empty (fd_ring))
239 int fd = i_ring_pop (fd_ring);
245 /* Overload the fts_statp->st_size member (otherwise unused, when
246 fts_info is FTS_NSOK) to indicate whether fts_read should stat
247 this entry or not. */
249 fts_set_stat_required (FTSENT *p, bool required)
251 fts_assert (p->fts_info == FTS_NSOK);
252 p->fts_statp->st_size = (required
254 : FTS_NO_STAT_REQUIRED);
257 /* file-descriptor-relative opendir. */
258 /* FIXME: if others need this function, move it into lib/openat.c */
261 opendirat (int fd, char const *dir)
263 int new_fd = openat (fd, dir, O_RDONLY);
268 dirp = fdopendir (new_fd);
271 int saved_errno = errno;
278 /* Virtual fchdir. Advance SP's working directory file descriptor,
279 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
280 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
281 open on sp->fts_cwd_fd; i.e., to move the working directory one level
285 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
287 int old = sp->fts_cwd_fd;
288 fts_assert (old != fd || old == AT_FDCWD);
292 /* Push "old" onto the ring.
293 If the displaced file descriptor is non-negative, close it. */
294 int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);
295 fd_ring_print (sp, stderr, "post-push");
296 if (0 <= prev_fd_in_slot)
297 close (prev_fd_in_slot); /* ignore any close failure */
299 else if ( ! ISSET (FTS_NOCHDIR))
302 close (old); /* ignore any close failure */
308 /* Open the directory DIR if possible, and return a file
309 descriptor. Return -1 and set errno on failure. It doesn't matter
310 whether the file descriptor has read or write access. */
314 diropen (FTS const *sp, char const *dir)
316 int open_flags = (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
317 | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0));
319 return (ISSET (FTS_CWDFD)
320 ? openat (sp->fts_cwd_fd, dir, open_flags)
321 : open (dir, open_flags));
325 fts_open (char * const *argv,
326 register int options,
327 int (*compar) (FTSENT const **, FTSENT const **))
330 register FTSENT *p, *root;
331 register size_t nitems;
332 FTSENT *parent = NULL;
333 FTSENT *tmp = NULL; /* pacify gcc */
338 if (options & ~FTS_OPTIONMASK) {
339 __set_errno (EINVAL);
342 if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {
343 __set_errno (EINVAL);
346 if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {
347 __set_errno (EINVAL);
351 /* Allocate/initialize the stream */
352 if ((sp = malloc(sizeof(FTS))) == NULL)
354 memset(sp, 0, sizeof(FTS));
355 sp->fts_compar = compar;
356 sp->fts_options = options;
358 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
359 if (ISSET(FTS_LOGICAL)) {
364 /* Initialize fts_cwd_fd. */
365 sp->fts_cwd_fd = AT_FDCWD;
366 if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)
368 /* While it isn't technically necessary to open "." this
369 early, doing it here saves us the trouble of ensuring
370 later (where it'd be messier) that "." can in fact
371 be opened. If not, revert to FTS_NOCHDIR mode. */
372 int fd = open (".", O_RDONLY);
375 /* Even if `.' is unreadable, don't revert to FTS_NOCHDIR mode
376 on systems like Linux+PROC_FS, where our openat emulation
377 is good enough. Note: on a system that emulates
378 openat via /proc, this technique can still fail, but
379 only in extreme conditions, e.g., when the working
380 directory cannot be saved (i.e. save_cwd fails) --
381 and that happens on Linux only when "." is unreadable
382 and the CWD would be longer than PATH_MAX.
383 FIXME: once Linux kernel openat support is well established,
384 replace the above open call and this entire if/else block
385 with the body of the if-block below. */
386 if ( openat_needs_fchdir ())
399 * Start out with 1K of file name space, and enough, in any case,
400 * to hold the user's file names.
403 # define MAXPATHLEN 1024
406 size_t maxarglen = fts_maxarglen(argv);
407 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
411 /* Allocate/initialize root's parent. */
413 if ((parent = fts_alloc(sp, "", 0)) == NULL)
415 parent->fts_level = FTS_ROOTPARENTLEVEL;
418 /* The classic fts implementation would call fts_stat with
419 a new entry for each iteration of the loop below.
420 If the comparison function is not specified or if the
421 FTS_DEFER_STAT option is in effect, don't stat any entry
422 in this loop. This is an attempt to minimize the interval
423 between the initial stat/lstat/fstatat and the point at which
424 a directory argument is first opened. This matters for any
425 directory command line argument that resides on a file system
426 without genuine i-nodes. If you specify FTS_DEFER_STAT along
427 with a comparison function, that function must not access any
428 data via the fts_statp pointer. */
429 defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));
431 /* Allocate/initialize root(s). */
432 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
433 /* Don't allow zero-length file names. */
434 if ((len = strlen(*argv)) == 0) {
435 __set_errno (ENOENT);
439 if ((p = fts_alloc(sp, *argv, len)) == NULL)
441 p->fts_level = FTS_ROOTLEVEL;
442 p->fts_parent = parent;
443 p->fts_accpath = p->fts_name;
444 /* Even when defer_stat is true, be sure to stat the first
445 command line argument, since fts_read (at least with
446 FTS_XDEV) requires that. */
447 if (defer_stat && root != NULL) {
448 p->fts_info = FTS_NSOK;
449 fts_set_stat_required(p, true);
451 p->fts_info = fts_stat(sp, p, false);
455 * If comparison routine supplied, traverse in sorted
456 * order; otherwise traverse in the order specified.
471 if (compar && nitems > 1)
472 root = fts_sort(sp, root, nitems);
475 * Allocate a dummy pointer and make fts_read think that we've just
476 * finished the node before the root(s); set p->fts_info to FTS_INIT
477 * so that everything about the "current" node is ignored.
479 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
481 sp->fts_cur->fts_link = root;
482 sp->fts_cur->fts_info = FTS_INIT;
483 if (! setup_dir (sp))
487 * If using chdir(2), grab a file descriptor pointing to dot to ensure
488 * that we can get back here; this could be avoided for some file names,
489 * but almost certainly not worth the effort. Slashes, symbolic links,
490 * and ".." are all fairly nasty problems. Note, if we can't get the
491 * descriptor we run anyway, just more slowly.
493 if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)
494 && (sp->fts_rfd = diropen (sp, ".")) < 0)
497 i_ring_init (&sp->fts_fd_ring, -1);
500 mem3: fts_lfree(root);
502 mem2: free(sp->fts_path);
509 fts_load (FTS *sp, register FTSENT *p)
515 * Load the stream structure for the next traversal. Since we don't
516 * actually enter the directory until after the preorder visit, set
517 * the fts_accpath field specially so the chdir gets done to the right
518 * place and the user can access the first node. From fts_open it's
519 * known that the file name will fit.
521 len = p->fts_pathlen = p->fts_namelen;
522 memmove(sp->fts_path, p->fts_name, len + 1);
523 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
525 memmove(p->fts_name, cp, len + 1);
526 p->fts_namelen = len;
528 p->fts_accpath = p->fts_path = sp->fts_path;
534 register FTSENT *freep, *p;
538 * This still works if we haven't read anything -- the dummy structure
539 * points to the root list, so we step through to the end of the root
540 * list which has a valid parent pointer.
543 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
545 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
551 /* Free up child linked list, sort array, file name buffer. */
553 fts_lfree(sp->fts_child);
557 if (ISSET(FTS_CWDFD))
559 if (0 <= sp->fts_cwd_fd)
560 close (sp->fts_cwd_fd);
562 else if (!ISSET(FTS_NOCHDIR))
564 /* Return to original directory, save errno if necessary. */
565 if (fchdir(sp->fts_rfd))
570 fd_ring_clear (&sp->fts_fd_ring);
573 /* Free up the stream pointer. */
576 /* Set errno and return. */
578 __set_errno (saved_errno);
586 * Special case of "/" at the end of the file name so that slashes aren't
587 * appended which would cause file names to be written as "....//foo".
590 (p->fts_path[p->fts_pathlen - 1] == '/' \
591 ? p->fts_pathlen - 1 : p->fts_pathlen)
594 fts_read (register FTS *sp)
596 register FTSENT *p, *tmp;
597 register unsigned short int instr;
600 /* If finished or unrecoverable error, return NULL. */
601 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
604 /* Set current node pointer. */
607 /* Save and zero out user instructions. */
608 instr = p->fts_instr;
609 p->fts_instr = FTS_NOINSTR;
611 /* Any type of file may be re-visited; re-stat and re-turn. */
612 if (instr == FTS_AGAIN) {
613 p->fts_info = fts_stat(sp, p, false);
616 Dprintf (("fts_read: p=%s\n",
617 p->fts_info == FTS_INIT ? "" : p->fts_path));
620 * Following a symlink -- SLNONE test allows application to see
621 * SLNONE and recover. If indirecting through a symlink, have
622 * keep a pointer to current location. If unable to get that
623 * pointer, follow fails.
625 if (instr == FTS_FOLLOW &&
626 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
627 p->fts_info = fts_stat(sp, p, true);
628 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
629 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
630 p->fts_errno = errno;
631 p->fts_info = FTS_ERR;
633 p->fts_flags |= FTS_SYMFOLLOW;
638 /* Directory in pre-order. */
639 if (p->fts_info == FTS_D) {
640 /* If skipped or crossed mount point, do post-order visit. */
641 if (instr == FTS_SKIP ||
642 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
643 if (p->fts_flags & FTS_SYMFOLLOW)
644 (void)close(p->fts_symfd);
646 fts_lfree(sp->fts_child);
647 sp->fts_child = NULL;
649 p->fts_info = FTS_DP;
650 LEAVE_DIR (sp, p, "1");
654 /* Rebuild if only read the names and now traversing. */
655 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
657 fts_lfree(sp->fts_child);
658 sp->fts_child = NULL;
662 * Cd to the subdirectory.
664 * If have already read and now fail to chdir, whack the list
665 * to make the names come out right, and set the parent errno
666 * so the application will eventually get an error condition.
667 * Set the FTS_DONTCHDIR flag so that when we logically change
668 * directories back to the parent we don't do a chdir.
670 * If haven't read do so. If the read fails, fts_build sets
671 * FTS_STOP or the fts_info field of the node.
673 if (sp->fts_child != NULL) {
674 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
675 p->fts_errno = errno;
676 p->fts_flags |= FTS_DONTCHDIR;
677 for (p = sp->fts_child; p != NULL;
680 p->fts_parent->fts_accpath;
682 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
685 /* If fts_build's call to fts_safe_changedir failed
686 because it was not able to fchdir into a
687 subdirectory, tell the caller. */
689 p->fts_info = FTS_ERR;
690 LEAVE_DIR (sp, p, "2");
694 sp->fts_child = NULL;
698 /* Move to the next node on this level. */
700 if ((p = p->fts_link) != NULL) {
705 * If reached the top, return to the original directory (or
706 * the root of the tree), and load the file names for the next
709 if (p->fts_level == FTS_ROOTLEVEL) {
710 if (RESTORE_INITIAL_CWD(sp)) {
719 * User may have called fts_set on the node. If skipped,
720 * ignore. If followed, get a file descriptor so we can
721 * get back if necessary.
723 if (p->fts_instr == FTS_SKIP)
725 if (p->fts_instr == FTS_FOLLOW) {
726 p->fts_info = fts_stat(sp, p, true);
727 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
728 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
729 p->fts_errno = errno;
730 p->fts_info = FTS_ERR;
732 p->fts_flags |= FTS_SYMFOLLOW;
734 p->fts_instr = FTS_NOINSTR;
737 name: t = sp->fts_path + NAPPEND(p->fts_parent);
739 memmove(t, p->fts_name, p->fts_namelen + 1);
742 if (p->fts_info == FTS_NSOK)
744 if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
745 p->fts_info = fts_stat(sp, p, false);
747 fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
750 if (p->fts_info == FTS_D)
752 /* Now that P->fts_statp is guaranteed to be valid,
753 if this is a command-line directory, record its
754 device number, to be used for FTS_XDEV. */
755 if (p->fts_level == FTS_ROOTLEVEL)
756 sp->fts_dev = p->fts_statp->st_dev;
757 Dprintf ((" entering: %s\n", p->fts_path));
758 if (! enter_dir (sp, p))
760 __set_errno (ENOMEM);
767 /* Move up to the parent node. */
772 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
774 * Done; free everything up and set errno to 0 so the user
775 * can distinguish between error and EOF.
779 return (sp->fts_cur = NULL);
782 fts_assert (p->fts_info != FTS_NSOK);
784 /* NUL terminate the file name. */
785 sp->fts_path[p->fts_pathlen] = '\0';
788 * Return to the parent directory. If at a root node, restore
789 * the initial working directory. If we came through a symlink,
790 * go back through the file descriptor. Otherwise, move up
791 * one level, via "..".
793 if (p->fts_level == FTS_ROOTLEVEL) {
794 if (RESTORE_INITIAL_CWD(sp)) {
795 p->fts_errno = errno;
798 } else if (p->fts_flags & FTS_SYMFOLLOW) {
799 if (FCHDIR(sp, p->fts_symfd)) {
800 int saved_errno = errno;
801 (void)close(p->fts_symfd);
802 __set_errno (saved_errno);
803 p->fts_errno = errno;
806 (void)close(p->fts_symfd);
807 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
808 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
809 p->fts_errno = errno;
812 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
813 if (p->fts_errno == 0)
814 LEAVE_DIR (sp, p, "3");
815 return ISSET(FTS_STOP) ? NULL : p;
819 * Fts_set takes the stream as an argument although it's not used in this
820 * implementation; it would be necessary if anyone wanted to add global
821 * semantics to fts using fts_set. An error return is allowed for similar
826 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
828 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
829 instr != FTS_NOINSTR && instr != FTS_SKIP) {
830 __set_errno (EINVAL);
833 p->fts_instr = instr;
838 fts_children (register FTS *sp, int instr)
843 if (instr != 0 && instr != FTS_NAMEONLY) {
844 __set_errno (EINVAL);
848 /* Set current node pointer. */
852 * Errno set to 0 so user can distinguish empty directory from
857 /* Fatal errors stop here. */
861 /* Return logical hierarchy of user's arguments. */
862 if (p->fts_info == FTS_INIT)
863 return (p->fts_link);
866 * If not a directory being visited in pre-order, stop here. Could
867 * allow FTS_DNR, assuming the user has fixed the problem, but the
868 * same effect is available with FTS_AGAIN.
870 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
873 /* Free up any previous child list. */
874 if (sp->fts_child != NULL)
875 fts_lfree(sp->fts_child);
877 if (instr == FTS_NAMEONLY) {
884 * If using chdir on a relative file name and called BEFORE fts_read
885 * does its chdir to the root of a traversal, we can lose -- we need to
886 * chdir into the subdirectory, and we don't know where the current
887 * directory is, so we can't get back so that the upcoming chdir by
888 * fts_read will work.
890 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
892 return (sp->fts_child = fts_build(sp, instr));
894 if ((fd = diropen (sp, ".")) < 0)
895 return (sp->fts_child = NULL);
896 sp->fts_child = fts_build(sp, instr);
897 if (ISSET(FTS_CWDFD))
899 cwd_advance_fd (sp, fd, true);
905 int saved_errno = errno;
907 __set_errno (saved_errno);
912 return (sp->fts_child);
916 * This is the tricky part -- do not casually change *anything* in here. The
917 * idea is to build the linked list of entries that are used by fts_children
918 * and fts_read. There are lots of special cases.
920 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
921 * set and it's a physical walk (so that symbolic links can't be directories),
922 * we can do things quickly. First, if it's a 4.4BSD file system, the type
923 * of the file is in the directory entry. Otherwise, we assume that the number
924 * of subdirectories in a node is equal to the number of links to the parent.
925 * The former skips all stat calls. The latter skips stat calls in any leaf
926 * directories and for any files after the subdirectories in the directory have
927 * been found, cutting the stat calls by about 2/3.
931 fts_build (register FTS *sp, int type)
933 register struct dirent *dp;
934 register FTSENT *p, *head;
935 register size_t nitems;
945 size_t len, maxlen, new_len;
948 /* Set current node pointer. */
952 * Open the directory for reading. If this fails, we're done.
953 * If being called from fts_read, set the fts_info field.
955 #if defined FTS_WHITEOUT && 0
956 if (ISSET(FTS_WHITEOUT))
957 oflag = DTF_NODUP|DTF_REWIND;
959 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
961 # define __opendir2(file, flag) \
962 ( ! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
963 ? opendirat(sp->fts_cwd_fd, file) \
966 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
968 cur->fts_info = FTS_DNR;
969 cur->fts_errno = errno;
973 /* Rather than calling fts_stat for each and every entry encountered
974 in the readdir loop (below), stat each directory only right after
976 if (cur->fts_info == FTS_NSOK)
977 cur->fts_info = fts_stat(sp, cur, false);
980 * Nlinks is the number of possible entries of type directory in the
981 * directory if we're cheating on stat calls, 0 if we're not doing
982 * any stat calls at all, (nlink_t) -1 if we're statting everything.
984 if (type == BNAMES) {
986 /* Be quiet about nostat, GCC. */
988 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
989 nlinks = (cur->fts_statp->st_nlink
990 - (ISSET(FTS_SEEDOT) ? 0 : 2));
998 * If we're going to need to stat anything or we want to descend
999 * and stay in the directory, chdir. If this fails we keep going,
1000 * but set a flag so we don't chdir after the post-order visit.
1001 * We won't be able to stat anything, but we can still return the
1002 * names themselves. Note, that since fts_read won't be able to
1003 * chdir into the directory, it will have to return different file
1004 * names than before, i.e. "a/b" instead of "b". Since the node
1005 * has already been visited in pre-order, have to wait until the
1006 * post-order visit to return the error. There is a special case
1007 * here, if there was nothing to stat then it's not an error to
1008 * not be able to stat. This is all fairly nasty. If a program
1009 * needed sorted entries or stat information, they had better be
1010 * checking FTS_NS on the returned nodes.
1012 if (nlinks || type == BREAD) {
1013 int dir_fd = dirfd(dirp);
1014 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1015 dir_fd = dup (dir_fd);
1016 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
1017 if (nlinks && type == BREAD)
1018 cur->fts_errno = errno;
1019 cur->fts_flags |= FTS_DONTCHDIR;
1022 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1031 * Figure out the max file name length that can be stored in the
1032 * current buffer -- the inner loop allocates more space as necessary.
1033 * We really wouldn't have to do the maxlen calculations here, we
1034 * could do them in fts_read before returning the name, but it's a
1035 * lot easier here since the length is part of the dirent structure.
1037 * If not changing directories set a pointer so that can just append
1038 * each new component into the file name.
1041 if (ISSET(FTS_NOCHDIR)) {
1042 cp = sp->fts_path + len;
1045 /* GCC, you're too verbose. */
1049 maxlen = sp->fts_pathlen - len;
1051 level = cur->fts_level + 1;
1053 /* Read the directory, attaching each entry to the `link' pointer. */
1055 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
1058 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1061 if ((p = fts_alloc (sp, dp->d_name,
1062 _D_EXACT_NAMLEN (dp))) == NULL)
1064 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
1065 /* include space for NUL */
1066 oldaddr = sp->fts_path;
1067 if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
1069 * No more memory. Save
1070 * errno, free up the current structure and the
1071 * structures already allocated.
1073 mem1: saved_errno = errno;
1077 cur->fts_info = FTS_ERR;
1079 __set_errno (saved_errno);
1082 /* Did realloc() change the pointer? */
1083 if (oldaddr != sp->fts_path) {
1085 if (ISSET(FTS_NOCHDIR))
1086 cp = sp->fts_path + len;
1088 maxlen = sp->fts_pathlen - len;
1091 new_len = len + _D_EXACT_NAMLEN (dp);
1092 if (new_len < len) {
1094 * In the unlikely even that we would end up
1095 * with a file name longer than SIZE_MAX, free up
1096 * the current structure and the structures already
1097 * allocated, then error out with ENAMETOOLONG.
1102 cur->fts_info = FTS_ERR;
1104 __set_errno (ENAMETOOLONG);
1107 p->fts_level = level;
1108 p->fts_parent = sp->fts_cur;
1109 p->fts_pathlen = new_len;
1111 #if defined FTS_WHITEOUT && 0
1112 if (dp->d_type == DT_WHT)
1113 p->fts_flags |= FTS_ISW;
1116 /* Build a file name for fts_stat to stat. */
1117 if (ISSET(FTS_NOCHDIR)) {
1118 p->fts_accpath = p->fts_path;
1119 memmove(cp, p->fts_name, p->fts_namelen + 1);
1121 p->fts_accpath = p->fts_name;
1123 if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {
1124 /* Record what fts_read will have to do with this
1125 entry. In many cases, it will simply fts_stat it,
1126 but we can take advantage of any d_type information
1127 to optimize away the unnecessary stat calls. I.e.,
1128 if FTS_NOSTAT is in effect and we're not following
1129 symlinks (FTS_PHYSICAL) and d_type indicates this
1130 is *not* a directory, then we won't have to stat it
1131 at all. If it *is* a directory, then (currently)
1132 we stat it regardless, in order to get device and
1133 inode numbers. Some day we might optimize that
1134 away, too, for directories where d_ino is known to
1136 bool skip_stat = (ISSET(FTS_PHYSICAL)
1137 && ISSET(FTS_NOSTAT)
1139 && ! DT_MUST_BE(dp, DT_DIR));
1140 p->fts_info = FTS_NSOK;
1141 fts_set_stat_required(p, !skip_stat);
1142 is_dir = (ISSET(FTS_PHYSICAL) && ISSET(FTS_NOSTAT)
1143 && DT_MUST_BE(dp, DT_DIR));
1145 p->fts_info = fts_stat(sp, p, false);
1146 is_dir = (p->fts_info == FTS_D
1147 || p->fts_info == FTS_DC
1148 || p->fts_info == FTS_DOT);
1151 /* Decrement link count if applicable. */
1152 if (nlinks > 0 && is_dir)
1155 /* We walk in directory order so "ls -f" doesn't get upset. */
1169 * If realloc() changed the address of the file name, adjust the
1170 * addresses for the rest of the tree and the dir list.
1173 fts_padjust(sp, head);
1176 * If not changing directories, reset the file name back to original
1179 if (ISSET(FTS_NOCHDIR)) {
1180 if (len == sp->fts_pathlen || nitems == 0)
1186 * If descended after called from fts_children or after called from
1187 * fts_read and nothing found, get back. At the root level we use
1188 * the saved fd; if one of fts_open()'s arguments is a relative name
1189 * to an empty directory, we wind up here with no other way back. If
1190 * can't get back, we're done.
1192 if (descend && (type == BCHILD || !nitems) &&
1193 (cur->fts_level == FTS_ROOTLEVEL
1194 ? RESTORE_INITIAL_CWD(sp)
1195 : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1196 cur->fts_info = FTS_ERR;
1202 /* If didn't find anything, return NULL. */
1205 cur->fts_info = FTS_DP;
1210 /* Sort the entries. */
1211 if (sp->fts_compar && nitems > 1)
1212 head = fts_sort(sp, head, nitems);
1218 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1219 current hierarchy. There should be a directory with dev/inode
1220 matching those of AD. If not, print a lot of diagnostics. */
1222 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1225 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1227 if (ad->ino == ent->fts_statp->st_ino
1228 && ad->dev == ent->fts_statp->st_dev)
1231 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1232 printf ("active dirs:\n");
1234 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1235 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1236 ad->fts_ent->fts_accpath,
1237 (uintmax_t) ad->dev,
1238 (uintmax_t) ad->ino,
1240 (uintmax_t) ent->fts_statp->st_dev,
1241 (uintmax_t) ent->fts_statp->st_ino);
1245 fts_cross_check (FTS const *sp)
1247 FTSENT const *ent = sp->fts_cur;
1249 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1252 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1253 /* Make sure every parent dir is in the tree. */
1254 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1256 struct Active_dir ad;
1257 ad.ino = t->fts_statp->st_ino;
1258 ad.dev = t->fts_statp->st_dev;
1259 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1260 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1263 /* Make sure every dir in the tree is an active dir.
1264 But ENT is not necessarily a directory. If so, just skip this part. */
1265 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1266 && (ent->fts_info == FTS_DP
1267 || ent->fts_info == FTS_D))
1269 struct Active_dir *ad;
1270 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1271 ad = hash_get_next (sp->fts_cycle.ht, ad))
1273 find_matching_ancestor (ent, ad);
1279 same_fd (int fd1, int fd2)
1281 struct stat sb1, sb2;
1282 return (fstat (fd1, &sb1) == 0
1283 && fstat (fd2, &sb2) == 0
1284 && SAME_INODE (sb1, sb2));
1288 fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
1290 I_ring const *fd_ring = &sp->fts_fd_ring;
1291 unsigned int i = fd_ring->fts_front;
1292 char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0);
1293 fprintf (stream, "=== %s ========== %s\n", msg, cwd);
1295 if (i_ring_empty (fd_ring))
1300 int fd = fd_ring->fts_fd_ring[i];
1302 fprintf (stream, "%d: %d:\n", i, fd);
1305 char *wd = getcwdat (fd, NULL, 0);
1306 fprintf (stream, "%d: %d: %s\n", i, fd, wd);
1309 if (i == fd_ring->fts_back)
1311 i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
1315 /* Ensure that each file descriptor on the fd_ring matches a
1316 parent, grandparent, etc. of the current working directory. */
1318 fd_ring_check (FTS const *sp)
1323 /* Make a writable copy. */
1324 I_ring fd_w = sp->fts_fd_ring;
1326 int cwd_fd = sp->fts_cwd_fd;
1327 cwd_fd = dup (cwd_fd);
1328 char *dot = getcwdat (cwd_fd, NULL, 0);
1329 error (0, 0, "===== check ===== cwd: %s", dot);
1331 while ( ! i_ring_empty (&fd_w))
1333 int fd = i_ring_pop (&fd_w);
1336 int parent_fd = openat (cwd_fd, "..", O_RDONLY);
1342 if (!same_fd (fd, parent_fd))
1344 char *cwd = getcwdat (fd, NULL, 0);
1345 error (0, errno, "ring : %s", cwd);
1346 char *c2 = getcwdat (parent_fd, NULL, 0);
1347 error (0, errno, "parent: %s", c2);
1360 static unsigned short int
1362 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1364 struct stat *sbp = p->fts_statp;
1367 if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
1370 #if defined FTS_WHITEOUT && 0
1371 /* check for whiteout */
1372 if (p->fts_flags & FTS_ISW) {
1373 memset(sbp, '\0', sizeof (*sbp));
1374 sbp->st_mode = S_IFWHT;
1380 * If doing a logical walk, or application requested FTS_FOLLOW, do
1381 * a stat(2). If that fails, check for a non-existent symlink. If
1382 * fail, set the errno from the stat call.
1384 if (ISSET(FTS_LOGICAL) || follow) {
1385 if (stat(p->fts_accpath, sbp)) {
1386 saved_errno = errno;
1388 && lstat(p->fts_accpath, sbp) == 0) {
1390 return (FTS_SLNONE);
1392 p->fts_errno = saved_errno;
1395 } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp,
1396 AT_SYMLINK_NOFOLLOW)) {
1397 p->fts_errno = errno;
1398 err: memset(sbp, 0, sizeof(struct stat));
1402 if (S_ISDIR(sbp->st_mode)) {
1403 if (ISDOT(p->fts_name)) {
1404 /* Command-line "." and ".." are real directories. */
1405 return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
1411 * Cycle detection is done by brute force when the directory
1412 * is first encountered. If the tree gets deep enough or the
1413 * number of symbolic links to directories is high enough,
1414 * something faster might be worthwhile.
1418 for (t = p->fts_parent;
1419 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1420 if (sbp->st_ino == t->fts_statp->st_ino
1421 && sbp->st_dev == t->fts_statp->st_dev)
1431 if (S_ISLNK(sbp->st_mode))
1433 if (S_ISREG(sbp->st_mode))
1435 return (FTS_DEFAULT);
1439 fts_compar (void const *a, void const *b)
1441 /* Convert A and B to the correct types, to pacify the compiler, and
1442 for portability to bizarre hosts where "void const *" and "FTSENT
1443 const **" differ in runtime representation. The comparison
1444 function cannot modify *a and *b, but there is no compile-time
1446 FTSENT const **pa = (FTSENT const **) a;
1447 FTSENT const **pb = (FTSENT const **) b;
1448 return pa[0]->fts_fts->fts_compar (pa, pb);
1453 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1455 register FTSENT **ap, *p;
1457 /* On most modern hosts, void * and FTSENT ** have the same
1458 run-time representation, and one can convert sp->fts_compar to
1459 the type qsort expects without problem. Use the heuristic that
1460 this is OK if the two pointer types are the same size, and if
1461 converting FTSENT ** to long int is the same as converting
1462 FTSENT ** to void * and then to long int. This heuristic isn't
1463 valid in general but we don't know of any counterexamples. */
1465 int (*compare) (void const *, void const *) =
1466 ((sizeof &dummy == sizeof (void *)
1467 && (long int) &dummy == (long int) (void *) &dummy)
1468 ? (int (*) (void const *, void const *)) sp->fts_compar
1472 * Construct an array of pointers to the structures and call qsort(3).
1473 * Reassemble the array in the order returned by qsort. If unable to
1474 * sort for memory reasons, return the directory entries in their
1475 * current order. Allocate enough space for the current needs plus
1476 * 40 so don't realloc one entry at a time.
1478 if (nitems > sp->fts_nitems) {
1481 sp->fts_nitems = nitems + 40;
1482 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1483 || ! (a = realloc (sp->fts_array,
1484 sp->fts_nitems * sizeof *a))) {
1485 free(sp->fts_array);
1486 sp->fts_array = NULL;
1492 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1494 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1495 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1496 ap[0]->fts_link = ap[1];
1497 ap[0]->fts_link = NULL;
1503 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1509 * The file name is a variable length array. Allocate the FTSENT
1510 * structure and the file name in one chunk.
1512 len = sizeof(FTSENT) + namelen;
1513 if ((p = malloc(len)) == NULL)
1516 /* Copy the name and guarantee NUL termination. */
1517 memmove(p->fts_name, name, namelen);
1518 p->fts_name[namelen] = '\0';
1520 p->fts_namelen = namelen;
1522 p->fts_path = sp->fts_path;
1525 p->fts_instr = FTS_NOINSTR;
1527 p->fts_pointer = NULL;
1533 fts_lfree (register FTSENT *head)
1537 /* Free a linked list of structures. */
1538 while ((p = head)) {
1539 head = head->fts_link;
1545 * Allow essentially unlimited file name lengths; find, rm, ls should
1546 * all work on any tree. Most systems will allow creation of file
1547 * names much longer than MAXPATHLEN, even though the kernel won't
1548 * resolve them. Add the size (not just what's needed) plus 256 bytes
1549 * so don't realloc the file name 2 bytes at a time.
1553 fts_palloc (FTS *sp, size_t more)
1556 size_t new_len = sp->fts_pathlen + more + 256;
1559 * See if fts_pathlen would overflow.
1561 if (new_len < sp->fts_pathlen) {
1563 sp->fts_path = NULL;
1564 __set_errno (ENAMETOOLONG);
1567 sp->fts_pathlen = new_len;
1568 p = realloc(sp->fts_path, sp->fts_pathlen);
1571 sp->fts_path = NULL;
1579 * When the file name is realloc'd, have to fix all of the pointers in
1580 * structures already returned.
1584 fts_padjust (FTS *sp, FTSENT *head)
1587 char *addr = sp->fts_path;
1589 #define ADJUST(p) do { \
1590 if ((p)->fts_accpath != (p)->fts_name) { \
1591 (p)->fts_accpath = \
1592 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1594 (p)->fts_path = addr; \
1596 /* Adjust the current set of children. */
1597 for (p = sp->fts_child; p; p = p->fts_link)
1600 /* Adjust the rest of the tree, including the current level. */
1601 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1603 p = p->fts_link ? p->fts_link : p->fts_parent;
1609 fts_maxarglen (char * const *argv)
1613 for (max = 0; *argv; ++argv)
1614 if ((len = strlen(*argv)) > max)
1620 * Change to dir specified by fd or file name without getting
1621 * tricked by someone changing the world out from underneath us.
1622 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1623 * If FD is non-negative, expect it to be used after this function returns,
1624 * and to be closed eventually. So don't pass e.g., `dirfd(dirp)' and then
1625 * do closedir(dirp), because that would invalidate the saved FD.
1626 * Upon failure, close FD immediately and return nonzero.
1630 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1633 bool is_dotdot = dir && STREQ (dir, "..");
1636 /* This clause handles the unusual case in which FTS_NOCHDIR
1637 is specified, along with FTS_CWDFD. In that case, there is
1638 no need to change even the virtual cwd file descriptor.
1639 However, if FD is non-negative, we do close it here. */
1640 if (ISSET (FTS_NOCHDIR))
1642 if (ISSET (FTS_CWDFD) && 0 <= fd)
1647 if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
1649 /* When possible, skip the diropen and subsequent fstat+dev/ino
1650 comparison. I.e., when changing to parent directory
1651 (chdir ("..")), use a file descriptor from the ring and
1652 save the overhead of diropen+fstat, as well as avoiding
1653 failure when we lack "x" access to the virtual cwd. */
1654 if ( ! i_ring_empty (&sp->fts_fd_ring))
1657 fd_ring_print (sp, stderr, "pre-pop");
1658 parent_fd = i_ring_pop (&sp->fts_fd_ring);
1669 if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
1672 /* The following dev/inode check is necessary if we're doing a
1673 `logical' traversal (through symlinks, a la chown -L), if the
1674 system lacks O_NOFOLLOW support, or if we're changing to ".."
1675 (but not via a popped file descriptor). When changing to the
1676 name "..", O_NOFOLLOW can't help. In general, when the target is
1677 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
1678 follow a symlink, so we can avoid the expense of this fstat. */
1679 if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
1680 || (dir && STREQ (dir, "..")))
1683 if (fstat(newfd, &sb))
1688 if (p->fts_statp->st_dev != sb.st_dev
1689 || p->fts_statp->st_ino != sb.st_ino)
1691 __set_errno (ENOENT); /* disinformation */
1697 if (ISSET(FTS_CWDFD))
1699 cwd_advance_fd (sp, newfd, ! is_dotdot);
1703 ret = fchdir(newfd);
1709 __set_errno (oerrno);