1 /* Traverse a file hierarchy.
3 Copyright (C) 2004, 2005, 2006, 2007, 2008 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>
75 # include "unistd--.h"
76 # include "same-inode.h"
80 #ifndef _D_EXACT_NAMLEN
81 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
84 #if HAVE_STRUCT_DIRENT_D_TYPE
85 /* True if the type of the directory entry D is known. */
86 # define DT_IS_KNOWN(d) ((d)->d_type != DT_UNKNOWN)
87 /* True if the type of the directory entry D must be T. */
88 # define DT_MUST_BE(d, t) ((d)->d_type == (t))
90 # define DT_IS_KNOWN(d) false
91 # define DT_MUST_BE(d, t) false
96 FTS_NO_STAT_REQUIRED = 1,
102 # define close __close
104 # define closedir __closedir
106 # define fchdir __fchdir
110 # define opendir __opendir
112 # define readdir __readdir
114 # undef internal_function
115 # define internal_function /* empty */
119 # define __set_errno(Val) errno = (Val)
122 #ifndef __attribute__
123 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8)
124 # define __attribute__(x) /* empty */
128 #ifndef ATTRIBUTE_UNUSED
129 # define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
132 /* If this host provides the openat function, then we can avoid
133 attempting to open "." in some initialization code below. */
135 # define HAVE_OPENAT_SUPPORT 1
137 # define HAVE_OPENAT_SUPPORT 0
141 # define fts_assert(expr) ((void) 0)
143 # define fts_assert(expr) \
152 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
153 static FTSENT *fts_build (FTS *, int) internal_function;
154 static void fts_lfree (FTSENT *) internal_function;
155 static void fts_load (FTS *, FTSENT *) internal_function;
156 static size_t fts_maxarglen (char * const *) internal_function;
157 static void fts_padjust (FTS *, FTSENT *) internal_function;
158 static bool fts_palloc (FTS *, size_t) internal_function;
159 static FTSENT *fts_sort (FTS *, FTSENT *, size_t) internal_function;
160 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
161 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
165 # include "fts-cycle.c"
167 static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
168 static void leave_dir (FTS *fts, FTSENT *ent) {}
169 static bool setup_dir (FTS *fts) { return true; }
170 static void free_dir (FTS *fts) {}
174 # define MAX(a,b) ((a) > (b) ? (a) : (b))
178 # define SIZE_MAX ((size_t) -1)
182 # define O_DIRECTORY 0
185 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
186 #define STREQ(a, b) (strcmp ((a), (b)) == 0)
188 #define CLR(opt) (sp->fts_options &= ~(opt))
189 #define ISSET(opt) (sp->fts_options & (opt))
190 #define SET(opt) (sp->fts_options |= (opt))
192 /* FIXME: make this a function */
193 #define RESTORE_INITIAL_CWD(sp) \
194 (fd_ring_clear (&((sp)->fts_fd_ring)), \
195 FCHDIR ((sp), (ISSET (FTS_CWDFD) ? AT_FDCWD : (sp)->fts_rfd)))
197 /* FIXME: FTS_NOCHDIR is now misnamed.
198 Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
199 #define FCHDIR(sp, fd) \
200 (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \
201 ? (cwd_advance_fd ((sp), (fd), true), 0) \
205 /* fts_build flags */
206 /* FIXME: make this an enum */
207 #define BCHILD 1 /* fts_children */
208 #define BNAMES 2 /* fts_children, names only */
209 #define BREAD 3 /* fts_read */
212 # include <inttypes.h>
215 # include "getcwdat.h"
216 bool fts_debug = false;
217 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
220 # define fd_ring_check(x)
221 # define fd_ring_print(a, b, c)
224 #define LEAVE_DIR(Fts, Ent, Tag) \
227 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
228 leave_dir (Fts, Ent); \
229 fd_ring_check (Fts); \
234 fd_ring_clear (I_ring *fd_ring)
236 while ( ! i_ring_empty (fd_ring))
238 int fd = i_ring_pop (fd_ring);
244 /* Overload the fts_statp->st_size member (otherwise unused, when
245 fts_info is FTS_NSOK) to indicate whether fts_read should stat
246 this entry or not. */
248 fts_set_stat_required (FTSENT *p, bool required)
250 fts_assert (p->fts_info == FTS_NSOK);
251 p->fts_statp->st_size = (required
253 : FTS_NO_STAT_REQUIRED);
256 /* file-descriptor-relative opendir. */
257 /* FIXME: if others need this function, move it into lib/openat.c */
260 opendirat (int fd, char const *dir)
262 int new_fd = openat (fd, dir, O_RDONLY);
267 dirp = fdopendir (new_fd);
270 int saved_errno = errno;
277 /* Virtual fchdir. Advance SP's working directory file descriptor,
278 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
279 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
280 open on sp->fts_cwd_fd; i.e., to move the working directory one level
284 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
286 int old = sp->fts_cwd_fd;
287 fts_assert (old != fd || old == AT_FDCWD);
291 /* Push "old" onto the ring.
292 If the displaced file descriptor is non-negative, close it. */
293 int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);
294 fd_ring_print (sp, stderr, "post-push");
295 if (0 <= prev_fd_in_slot)
296 close (prev_fd_in_slot); /* ignore any close failure */
298 else if ( ! ISSET (FTS_NOCHDIR))
301 close (old); /* ignore any close failure */
307 /* Open the directory DIR if possible, and return a file
308 descriptor. Return -1 and set errno on failure. It doesn't matter
309 whether the file descriptor has read or write access. */
313 diropen (FTS const *sp, char const *dir)
315 int open_flags = (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
316 | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0));
318 return (ISSET (FTS_CWDFD)
319 ? openat (sp->fts_cwd_fd, dir, open_flags)
320 : open (dir, open_flags));
324 fts_open (char * const *argv,
325 register int options,
326 int (*compar) (FTSENT const **, FTSENT const **))
329 register FTSENT *p, *root;
330 register size_t nitems;
331 FTSENT *parent = NULL;
332 FTSENT *tmp = NULL; /* pacify gcc */
337 if (options & ~FTS_OPTIONMASK) {
338 __set_errno (EINVAL);
341 if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {
342 __set_errno (EINVAL);
345 if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {
346 __set_errno (EINVAL);
350 /* Allocate/initialize the stream */
351 if ((sp = malloc(sizeof(FTS))) == NULL)
353 memset(sp, 0, sizeof(FTS));
354 sp->fts_compar = compar;
355 sp->fts_options = options;
357 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
358 if (ISSET(FTS_LOGICAL)) {
363 /* Initialize fts_cwd_fd. */
364 sp->fts_cwd_fd = AT_FDCWD;
365 if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)
367 /* While it isn't technically necessary to open "." this
368 early, doing it here saves us the trouble of ensuring
369 later (where it'd be messier) that "." can in fact
370 be opened. If not, revert to FTS_NOCHDIR mode. */
371 int fd = open (".", O_RDONLY);
374 /* Even if `.' is unreadable, don't revert to FTS_NOCHDIR mode
375 on systems like Linux+PROC_FS, where our openat emulation
376 is good enough. Note: on a system that emulates
377 openat via /proc, this technique can still fail, but
378 only in extreme conditions, e.g., when the working
379 directory cannot be saved (i.e. save_cwd fails) --
380 and that happens on Linux only when "." is unreadable
381 and the CWD would be longer than PATH_MAX.
382 FIXME: once Linux kernel openat support is well established,
383 replace the above open call and this entire if/else block
384 with the body of the if-block below. */
385 if ( openat_needs_fchdir ())
398 * Start out with 1K of file name space, and enough, in any case,
399 * to hold the user's file names.
402 # define MAXPATHLEN 1024
405 size_t maxarglen = fts_maxarglen(argv);
406 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
410 /* Allocate/initialize root's parent. */
412 if ((parent = fts_alloc(sp, "", 0)) == NULL)
414 parent->fts_level = FTS_ROOTPARENTLEVEL;
417 /* The classic fts implementation would call fts_stat with
418 a new entry for each iteration of the loop below.
419 If the comparison function is not specified or if the
420 FTS_DEFER_STAT option is in effect, don't stat any entry
421 in this loop. This is an attempt to minimize the interval
422 between the initial stat/lstat/fstatat and the point at which
423 a directory argument is first opened. This matters for any
424 directory command line argument that resides on a file system
425 without genuine i-nodes. If you specify FTS_DEFER_STAT along
426 with a comparison function, that function must not access any
427 data via the fts_statp pointer. */
428 defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));
430 /* Allocate/initialize root(s). */
431 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
432 /* Don't allow zero-length file names. */
433 if ((len = strlen(*argv)) == 0) {
434 __set_errno (ENOENT);
438 if ((p = fts_alloc(sp, *argv, len)) == NULL)
440 p->fts_level = FTS_ROOTLEVEL;
441 p->fts_parent = parent;
442 p->fts_accpath = p->fts_name;
443 /* Even when defer_stat is true, be sure to stat the first
444 command line argument, since fts_read (at least with
445 FTS_XDEV) requires that. */
446 if (defer_stat && root != NULL) {
447 p->fts_info = FTS_NSOK;
448 fts_set_stat_required(p, true);
450 p->fts_info = fts_stat(sp, p, false);
454 * If comparison routine supplied, traverse in sorted
455 * order; otherwise traverse in the order specified.
470 if (compar && nitems > 1)
471 root = fts_sort(sp, root, nitems);
474 * Allocate a dummy pointer and make fts_read think that we've just
475 * finished the node before the root(s); set p->fts_info to FTS_INIT
476 * so that everything about the "current" node is ignored.
478 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
480 sp->fts_cur->fts_link = root;
481 sp->fts_cur->fts_info = FTS_INIT;
482 if (! setup_dir (sp))
486 * If using chdir(2), grab a file descriptor pointing to dot to ensure
487 * that we can get back here; this could be avoided for some file names,
488 * but almost certainly not worth the effort. Slashes, symbolic links,
489 * and ".." are all fairly nasty problems. Note, if we can't get the
490 * descriptor we run anyway, just more slowly.
492 if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)
493 && (sp->fts_rfd = diropen (sp, ".")) < 0)
496 i_ring_init (&sp->fts_fd_ring, -1);
499 mem3: fts_lfree(root);
501 mem2: free(sp->fts_path);
508 fts_load (FTS *sp, register FTSENT *p)
514 * Load the stream structure for the next traversal. Since we don't
515 * actually enter the directory until after the preorder visit, set
516 * the fts_accpath field specially so the chdir gets done to the right
517 * place and the user can access the first node. From fts_open it's
518 * known that the file name will fit.
520 len = p->fts_pathlen = p->fts_namelen;
521 memmove(sp->fts_path, p->fts_name, len + 1);
522 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
524 memmove(p->fts_name, cp, len + 1);
525 p->fts_namelen = len;
527 p->fts_accpath = p->fts_path = sp->fts_path;
533 register FTSENT *freep, *p;
537 * This still works if we haven't read anything -- the dummy structure
538 * points to the root list, so we step through to the end of the root
539 * list which has a valid parent pointer.
542 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
544 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
550 /* Free up child linked list, sort array, file name buffer. */
552 fts_lfree(sp->fts_child);
556 if (ISSET(FTS_CWDFD))
558 if (0 <= sp->fts_cwd_fd)
559 close (sp->fts_cwd_fd);
561 else if (!ISSET(FTS_NOCHDIR))
563 /* Return to original directory, save errno if necessary. */
564 if (fchdir(sp->fts_rfd))
569 fd_ring_clear (&sp->fts_fd_ring);
572 /* Free up the stream pointer. */
575 /* Set errno and return. */
577 __set_errno (saved_errno);
585 * Special case of "/" at the end of the file name so that slashes aren't
586 * appended which would cause file names to be written as "....//foo".
589 (p->fts_path[p->fts_pathlen - 1] == '/' \
590 ? p->fts_pathlen - 1 : p->fts_pathlen)
593 fts_read (register FTS *sp)
595 register FTSENT *p, *tmp;
596 register unsigned short int instr;
599 /* If finished or unrecoverable error, return NULL. */
600 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
603 /* Set current node pointer. */
606 /* Save and zero out user instructions. */
607 instr = p->fts_instr;
608 p->fts_instr = FTS_NOINSTR;
610 /* Any type of file may be re-visited; re-stat and re-turn. */
611 if (instr == FTS_AGAIN) {
612 p->fts_info = fts_stat(sp, p, false);
615 Dprintf (("fts_read: p=%s\n",
616 p->fts_info == FTS_INIT ? "" : p->fts_path));
619 * Following a symlink -- SLNONE test allows application to see
620 * SLNONE and recover. If indirecting through a symlink, have
621 * keep a pointer to current location. If unable to get that
622 * pointer, follow fails.
624 if (instr == FTS_FOLLOW &&
625 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
626 p->fts_info = fts_stat(sp, p, true);
627 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
628 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
629 p->fts_errno = errno;
630 p->fts_info = FTS_ERR;
632 p->fts_flags |= FTS_SYMFOLLOW;
637 /* Directory in pre-order. */
638 if (p->fts_info == FTS_D) {
639 /* If skipped or crossed mount point, do post-order visit. */
640 if (instr == FTS_SKIP ||
641 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
642 if (p->fts_flags & FTS_SYMFOLLOW)
643 (void)close(p->fts_symfd);
645 fts_lfree(sp->fts_child);
646 sp->fts_child = NULL;
648 p->fts_info = FTS_DP;
649 LEAVE_DIR (sp, p, "1");
653 /* Rebuild if only read the names and now traversing. */
654 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
656 fts_lfree(sp->fts_child);
657 sp->fts_child = NULL;
661 * Cd to the subdirectory.
663 * If have already read and now fail to chdir, whack the list
664 * to make the names come out right, and set the parent errno
665 * so the application will eventually get an error condition.
666 * Set the FTS_DONTCHDIR flag so that when we logically change
667 * directories back to the parent we don't do a chdir.
669 * If haven't read do so. If the read fails, fts_build sets
670 * FTS_STOP or the fts_info field of the node.
672 if (sp->fts_child != NULL) {
673 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
674 p->fts_errno = errno;
675 p->fts_flags |= FTS_DONTCHDIR;
676 for (p = sp->fts_child; p != NULL;
679 p->fts_parent->fts_accpath;
681 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
684 /* If fts_build's call to fts_safe_changedir failed
685 because it was not able to fchdir into a
686 subdirectory, tell the caller. */
687 if (p->fts_errno && p->fts_info != FTS_DNR)
688 p->fts_info = FTS_ERR;
689 LEAVE_DIR (sp, p, "2");
693 sp->fts_child = NULL;
697 /* Move to the next node on this level. */
699 if ((p = p->fts_link) != NULL) {
704 * If reached the top, return to the original directory (or
705 * the root of the tree), and load the file names for the next
708 if (p->fts_level == FTS_ROOTLEVEL) {
709 if (RESTORE_INITIAL_CWD(sp)) {
718 * User may have called fts_set on the node. If skipped,
719 * ignore. If followed, get a file descriptor so we can
720 * get back if necessary.
722 if (p->fts_instr == FTS_SKIP)
724 if (p->fts_instr == FTS_FOLLOW) {
725 p->fts_info = fts_stat(sp, p, true);
726 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
727 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
728 p->fts_errno = errno;
729 p->fts_info = FTS_ERR;
731 p->fts_flags |= FTS_SYMFOLLOW;
733 p->fts_instr = FTS_NOINSTR;
736 name: t = sp->fts_path + NAPPEND(p->fts_parent);
738 memmove(t, p->fts_name, p->fts_namelen + 1);
741 if (p->fts_info == FTS_NSOK)
743 if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
744 p->fts_info = fts_stat(sp, p, false);
746 fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
749 if (p->fts_info == FTS_D)
751 /* Now that P->fts_statp is guaranteed to be valid,
752 if this is a command-line directory, record its
753 device number, to be used for FTS_XDEV. */
754 if (p->fts_level == FTS_ROOTLEVEL)
755 sp->fts_dev = p->fts_statp->st_dev;
756 Dprintf ((" entering: %s\n", p->fts_path));
757 if (! enter_dir (sp, p))
759 __set_errno (ENOMEM);
766 /* Move up to the parent node. */
771 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
773 * Done; free everything up and set errno to 0 so the user
774 * can distinguish between error and EOF.
778 return (sp->fts_cur = NULL);
781 fts_assert (p->fts_info != FTS_NSOK);
783 /* NUL terminate the file name. */
784 sp->fts_path[p->fts_pathlen] = '\0';
787 * Return to the parent directory. If at a root node, restore
788 * the initial working directory. If we came through a symlink,
789 * go back through the file descriptor. Otherwise, move up
790 * one level, via "..".
792 if (p->fts_level == FTS_ROOTLEVEL) {
793 if (RESTORE_INITIAL_CWD(sp)) {
794 p->fts_errno = errno;
797 } else if (p->fts_flags & FTS_SYMFOLLOW) {
798 if (FCHDIR(sp, p->fts_symfd)) {
799 int saved_errno = errno;
800 (void)close(p->fts_symfd);
801 __set_errno (saved_errno);
802 p->fts_errno = errno;
805 (void)close(p->fts_symfd);
806 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
807 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
808 p->fts_errno = errno;
811 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
812 if (p->fts_errno == 0)
813 LEAVE_DIR (sp, p, "3");
814 return ISSET(FTS_STOP) ? NULL : p;
818 * Fts_set takes the stream as an argument although it's not used in this
819 * implementation; it would be necessary if anyone wanted to add global
820 * semantics to fts using fts_set. An error return is allowed for similar
825 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
827 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
828 instr != FTS_NOINSTR && instr != FTS_SKIP) {
829 __set_errno (EINVAL);
832 p->fts_instr = instr;
837 fts_children (register FTS *sp, int instr)
842 if (instr != 0 && instr != FTS_NAMEONLY) {
843 __set_errno (EINVAL);
847 /* Set current node pointer. */
851 * Errno set to 0 so user can distinguish empty directory from
856 /* Fatal errors stop here. */
860 /* Return logical hierarchy of user's arguments. */
861 if (p->fts_info == FTS_INIT)
862 return (p->fts_link);
865 * If not a directory being visited in pre-order, stop here. Could
866 * allow FTS_DNR, assuming the user has fixed the problem, but the
867 * same effect is available with FTS_AGAIN.
869 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
872 /* Free up any previous child list. */
873 if (sp->fts_child != NULL)
874 fts_lfree(sp->fts_child);
876 if (instr == FTS_NAMEONLY) {
883 * If using chdir on a relative file name and called BEFORE fts_read
884 * does its chdir to the root of a traversal, we can lose -- we need to
885 * chdir into the subdirectory, and we don't know where the current
886 * directory is, so we can't get back so that the upcoming chdir by
887 * fts_read will work.
889 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
891 return (sp->fts_child = fts_build(sp, instr));
893 if ((fd = diropen (sp, ".")) < 0)
894 return (sp->fts_child = NULL);
895 sp->fts_child = fts_build(sp, instr);
896 if (ISSET(FTS_CWDFD))
898 cwd_advance_fd (sp, fd, true);
904 int saved_errno = errno;
906 __set_errno (saved_errno);
911 return (sp->fts_child);
915 * This is the tricky part -- do not casually change *anything* in here. The
916 * idea is to build the linked list of entries that are used by fts_children
917 * and fts_read. There are lots of special cases.
919 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
920 * set and it's a physical walk (so that symbolic links can't be directories),
921 * we can do things quickly. First, if it's a 4.4BSD file system, the type
922 * of the file is in the directory entry. Otherwise, we assume that the number
923 * of subdirectories in a node is equal to the number of links to the parent.
924 * The former skips all stat calls. The latter skips stat calls in any leaf
925 * directories and for any files after the subdirectories in the directory have
926 * been found, cutting the stat calls by about 2/3.
930 fts_build (register FTS *sp, int type)
932 register struct dirent *dp;
933 register FTSENT *p, *head;
934 register size_t nitems;
944 size_t len, maxlen, new_len;
947 /* Set current node pointer. */
951 * Open the directory for reading. If this fails, we're done.
952 * If being called from fts_read, set the fts_info field.
954 #if defined FTS_WHITEOUT && 0
955 if (ISSET(FTS_WHITEOUT))
956 oflag = DTF_NODUP|DTF_REWIND;
958 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
960 # define __opendir2(file, flag) \
961 ( ! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
962 ? opendirat(sp->fts_cwd_fd, file) \
965 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
967 cur->fts_info = FTS_DNR;
968 cur->fts_errno = errno;
972 /* Rather than calling fts_stat for each and every entry encountered
973 in the readdir loop (below), stat each directory only right after
975 if (cur->fts_info == FTS_NSOK)
976 cur->fts_info = fts_stat(sp, cur, false);
979 * Nlinks is the number of possible entries of type directory in the
980 * directory if we're cheating on stat calls, 0 if we're not doing
981 * any stat calls at all, (nlink_t) -1 if we're statting everything.
983 if (type == BNAMES) {
985 /* Be quiet about nostat, GCC. */
987 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
988 nlinks = (cur->fts_statp->st_nlink
989 - (ISSET(FTS_SEEDOT) ? 0 : 2));
997 * If we're going to need to stat anything or we want to descend
998 * and stay in the directory, chdir. If this fails we keep going,
999 * but set a flag so we don't chdir after the post-order visit.
1000 * We won't be able to stat anything, but we can still return the
1001 * names themselves. Note, that since fts_read won't be able to
1002 * chdir into the directory, it will have to return different file
1003 * names than before, i.e. "a/b" instead of "b". Since the node
1004 * has already been visited in pre-order, have to wait until the
1005 * post-order visit to return the error. There is a special case
1006 * here, if there was nothing to stat then it's not an error to
1007 * not be able to stat. This is all fairly nasty. If a program
1008 * needed sorted entries or stat information, they had better be
1009 * checking FTS_NS on the returned nodes.
1011 if (nlinks || type == BREAD) {
1012 int dir_fd = dirfd(dirp);
1013 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1014 dir_fd = dup (dir_fd);
1015 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
1016 if (nlinks && type == BREAD)
1017 cur->fts_errno = errno;
1018 cur->fts_flags |= FTS_DONTCHDIR;
1021 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1030 * Figure out the max file name length that can be stored in the
1031 * current buffer -- the inner loop allocates more space as necessary.
1032 * We really wouldn't have to do the maxlen calculations here, we
1033 * could do them in fts_read before returning the name, but it's a
1034 * lot easier here since the length is part of the dirent structure.
1036 * If not changing directories set a pointer so that can just append
1037 * each new component into the file name.
1040 if (ISSET(FTS_NOCHDIR)) {
1041 cp = sp->fts_path + len;
1044 /* GCC, you're too verbose. */
1048 maxlen = sp->fts_pathlen - len;
1050 level = cur->fts_level + 1;
1052 /* Read the directory, attaching each entry to the `link' pointer. */
1054 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
1057 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1060 if ((p = fts_alloc (sp, dp->d_name,
1061 _D_EXACT_NAMLEN (dp))) == NULL)
1063 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
1064 /* include space for NUL */
1065 oldaddr = sp->fts_path;
1066 if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
1068 * No more memory. Save
1069 * errno, free up the current structure and the
1070 * structures already allocated.
1072 mem1: saved_errno = errno;
1076 cur->fts_info = FTS_ERR;
1078 __set_errno (saved_errno);
1081 /* Did realloc() change the pointer? */
1082 if (oldaddr != sp->fts_path) {
1084 if (ISSET(FTS_NOCHDIR))
1085 cp = sp->fts_path + len;
1087 maxlen = sp->fts_pathlen - len;
1090 new_len = len + _D_EXACT_NAMLEN (dp);
1091 if (new_len < len) {
1093 * In the unlikely event that we would end up
1094 * with a file name longer than SIZE_MAX, free up
1095 * the current structure and the structures already
1096 * allocated, then error out with ENAMETOOLONG.
1101 cur->fts_info = FTS_ERR;
1103 __set_errno (ENAMETOOLONG);
1106 p->fts_level = level;
1107 p->fts_parent = sp->fts_cur;
1108 p->fts_pathlen = new_len;
1110 #if defined FTS_WHITEOUT && 0
1111 if (dp->d_type == DT_WHT)
1112 p->fts_flags |= FTS_ISW;
1115 /* Build a file name for fts_stat to stat. */
1116 if (ISSET(FTS_NOCHDIR)) {
1117 p->fts_accpath = p->fts_path;
1118 memmove(cp, p->fts_name, p->fts_namelen + 1);
1120 p->fts_accpath = p->fts_name;
1122 if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {
1123 /* Record what fts_read will have to do with this
1124 entry. In many cases, it will simply fts_stat it,
1125 but we can take advantage of any d_type information
1126 to optimize away the unnecessary stat calls. I.e.,
1127 if FTS_NOSTAT is in effect and we're not following
1128 symlinks (FTS_PHYSICAL) and d_type indicates this
1129 is *not* a directory, then we won't have to stat it
1130 at all. If it *is* a directory, then (currently)
1131 we stat it regardless, in order to get device and
1132 inode numbers. Some day we might optimize that
1133 away, too, for directories where d_ino is known to
1135 bool skip_stat = (ISSET(FTS_PHYSICAL)
1136 && ISSET(FTS_NOSTAT)
1138 && ! DT_MUST_BE(dp, DT_DIR));
1139 p->fts_info = FTS_NSOK;
1140 fts_set_stat_required(p, !skip_stat);
1141 is_dir = (ISSET(FTS_PHYSICAL) && ISSET(FTS_NOSTAT)
1142 && DT_MUST_BE(dp, DT_DIR));
1144 p->fts_info = fts_stat(sp, p, false);
1145 is_dir = (p->fts_info == FTS_D
1146 || p->fts_info == FTS_DC
1147 || p->fts_info == FTS_DOT);
1150 /* Decrement link count if applicable. */
1151 if (nlinks > 0 && is_dir)
1154 /* We walk in directory order so "ls -f" doesn't get upset. */
1168 * If realloc() changed the address of the file name, adjust the
1169 * addresses for the rest of the tree and the dir list.
1172 fts_padjust(sp, head);
1175 * If not changing directories, reset the file name back to original
1178 if (ISSET(FTS_NOCHDIR)) {
1179 if (len == sp->fts_pathlen || nitems == 0)
1185 * If descended after called from fts_children or after called from
1186 * fts_read and nothing found, get back. At the root level we use
1187 * the saved fd; if one of fts_open()'s arguments is a relative name
1188 * to an empty directory, we wind up here with no other way back. If
1189 * can't get back, we're done.
1191 if (descend && (type == BCHILD || !nitems) &&
1192 (cur->fts_level == FTS_ROOTLEVEL
1193 ? RESTORE_INITIAL_CWD(sp)
1194 : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1195 cur->fts_info = FTS_ERR;
1201 /* If didn't find anything, return NULL. */
1204 cur->fts_info = FTS_DP;
1209 /* Sort the entries. */
1210 if (sp->fts_compar && nitems > 1)
1211 head = fts_sort(sp, head, nitems);
1217 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1218 current hierarchy. There should be a directory with dev/inode
1219 matching those of AD. If not, print a lot of diagnostics. */
1221 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1224 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1226 if (ad->ino == ent->fts_statp->st_ino
1227 && ad->dev == ent->fts_statp->st_dev)
1230 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1231 printf ("active dirs:\n");
1233 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1234 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1235 ad->fts_ent->fts_accpath,
1236 (uintmax_t) ad->dev,
1237 (uintmax_t) ad->ino,
1239 (uintmax_t) ent->fts_statp->st_dev,
1240 (uintmax_t) ent->fts_statp->st_ino);
1244 fts_cross_check (FTS const *sp)
1246 FTSENT const *ent = sp->fts_cur;
1248 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1251 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1252 /* Make sure every parent dir is in the tree. */
1253 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1255 struct Active_dir ad;
1256 ad.ino = t->fts_statp->st_ino;
1257 ad.dev = t->fts_statp->st_dev;
1258 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1259 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1262 /* Make sure every dir in the tree is an active dir.
1263 But ENT is not necessarily a directory. If so, just skip this part. */
1264 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1265 && (ent->fts_info == FTS_DP
1266 || ent->fts_info == FTS_D))
1268 struct Active_dir *ad;
1269 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1270 ad = hash_get_next (sp->fts_cycle.ht, ad))
1272 find_matching_ancestor (ent, ad);
1278 same_fd (int fd1, int fd2)
1280 struct stat sb1, sb2;
1281 return (fstat (fd1, &sb1) == 0
1282 && fstat (fd2, &sb2) == 0
1283 && SAME_INODE (sb1, sb2));
1287 fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
1289 I_ring const *fd_ring = &sp->fts_fd_ring;
1290 unsigned int i = fd_ring->fts_front;
1291 char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0);
1292 fprintf (stream, "=== %s ========== %s\n", msg, cwd);
1294 if (i_ring_empty (fd_ring))
1299 int fd = fd_ring->fts_fd_ring[i];
1301 fprintf (stream, "%d: %d:\n", i, fd);
1304 char *wd = getcwdat (fd, NULL, 0);
1305 fprintf (stream, "%d: %d: %s\n", i, fd, wd);
1308 if (i == fd_ring->fts_back)
1310 i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
1314 /* Ensure that each file descriptor on the fd_ring matches a
1315 parent, grandparent, etc. of the current working directory. */
1317 fd_ring_check (FTS const *sp)
1322 /* Make a writable copy. */
1323 I_ring fd_w = sp->fts_fd_ring;
1325 int cwd_fd = sp->fts_cwd_fd;
1326 cwd_fd = dup (cwd_fd);
1327 char *dot = getcwdat (cwd_fd, NULL, 0);
1328 error (0, 0, "===== check ===== cwd: %s", dot);
1330 while ( ! i_ring_empty (&fd_w))
1332 int fd = i_ring_pop (&fd_w);
1335 int parent_fd = openat (cwd_fd, "..", O_RDONLY);
1341 if (!same_fd (fd, parent_fd))
1343 char *cwd = getcwdat (fd, NULL, 0);
1344 error (0, errno, "ring : %s", cwd);
1345 char *c2 = getcwdat (parent_fd, NULL, 0);
1346 error (0, errno, "parent: %s", c2);
1359 static unsigned short int
1361 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1363 struct stat *sbp = p->fts_statp;
1366 if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
1369 #if defined FTS_WHITEOUT && 0
1370 /* check for whiteout */
1371 if (p->fts_flags & FTS_ISW) {
1372 memset(sbp, '\0', sizeof (*sbp));
1373 sbp->st_mode = S_IFWHT;
1379 * If doing a logical walk, or application requested FTS_FOLLOW, do
1380 * a stat(2). If that fails, check for a non-existent symlink. If
1381 * fail, set the errno from the stat call.
1383 if (ISSET(FTS_LOGICAL) || follow) {
1384 if (stat(p->fts_accpath, sbp)) {
1385 saved_errno = errno;
1387 && lstat(p->fts_accpath, sbp) == 0) {
1389 return (FTS_SLNONE);
1391 p->fts_errno = saved_errno;
1394 } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp,
1395 AT_SYMLINK_NOFOLLOW)) {
1396 p->fts_errno = errno;
1397 err: memset(sbp, 0, sizeof(struct stat));
1401 if (S_ISDIR(sbp->st_mode)) {
1402 if (ISDOT(p->fts_name)) {
1403 /* Command-line "." and ".." are real directories. */
1404 return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
1410 * Cycle detection is done by brute force when the directory
1411 * is first encountered. If the tree gets deep enough or the
1412 * number of symbolic links to directories is high enough,
1413 * something faster might be worthwhile.
1417 for (t = p->fts_parent;
1418 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1419 if (sbp->st_ino == t->fts_statp->st_ino
1420 && sbp->st_dev == t->fts_statp->st_dev)
1430 if (S_ISLNK(sbp->st_mode))
1432 if (S_ISREG(sbp->st_mode))
1434 return (FTS_DEFAULT);
1438 fts_compar (void const *a, void const *b)
1440 /* Convert A and B to the correct types, to pacify the compiler, and
1441 for portability to bizarre hosts where "void const *" and "FTSENT
1442 const **" differ in runtime representation. The comparison
1443 function cannot modify *a and *b, but there is no compile-time
1445 FTSENT const **pa = (FTSENT const **) a;
1446 FTSENT const **pb = (FTSENT const **) b;
1447 return pa[0]->fts_fts->fts_compar (pa, pb);
1452 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1454 register FTSENT **ap, *p;
1456 /* On most modern hosts, void * and FTSENT ** have the same
1457 run-time representation, and one can convert sp->fts_compar to
1458 the type qsort expects without problem. Use the heuristic that
1459 this is OK if the two pointer types are the same size, and if
1460 converting FTSENT ** to long int is the same as converting
1461 FTSENT ** to void * and then to long int. This heuristic isn't
1462 valid in general but we don't know of any counterexamples. */
1464 int (*compare) (void const *, void const *) =
1465 ((sizeof &dummy == sizeof (void *)
1466 && (long int) &dummy == (long int) (void *) &dummy)
1467 ? (int (*) (void const *, void const *)) sp->fts_compar
1471 * Construct an array of pointers to the structures and call qsort(3).
1472 * Reassemble the array in the order returned by qsort. If unable to
1473 * sort for memory reasons, return the directory entries in their
1474 * current order. Allocate enough space for the current needs plus
1475 * 40 so don't realloc one entry at a time.
1477 if (nitems > sp->fts_nitems) {
1480 sp->fts_nitems = nitems + 40;
1481 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1482 || ! (a = realloc (sp->fts_array,
1483 sp->fts_nitems * sizeof *a))) {
1484 free(sp->fts_array);
1485 sp->fts_array = NULL;
1491 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1493 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1494 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1495 ap[0]->fts_link = ap[1];
1496 ap[0]->fts_link = NULL;
1502 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1508 * The file name is a variable length array. Allocate the FTSENT
1509 * structure and the file name in one chunk.
1511 len = sizeof(FTSENT) + namelen;
1512 if ((p = malloc(len)) == NULL)
1515 /* Copy the name and guarantee NUL termination. */
1516 memmove(p->fts_name, name, namelen);
1517 p->fts_name[namelen] = '\0';
1519 p->fts_namelen = namelen;
1521 p->fts_path = sp->fts_path;
1524 p->fts_instr = FTS_NOINSTR;
1526 p->fts_pointer = NULL;
1532 fts_lfree (register FTSENT *head)
1536 /* Free a linked list of structures. */
1537 while ((p = head)) {
1538 head = head->fts_link;
1544 * Allow essentially unlimited file name lengths; find, rm, ls should
1545 * all work on any tree. Most systems will allow creation of file
1546 * names much longer than MAXPATHLEN, even though the kernel won't
1547 * resolve them. Add the size (not just what's needed) plus 256 bytes
1548 * so don't realloc the file name 2 bytes at a time.
1552 fts_palloc (FTS *sp, size_t more)
1555 size_t new_len = sp->fts_pathlen + more + 256;
1558 * See if fts_pathlen would overflow.
1560 if (new_len < sp->fts_pathlen) {
1562 sp->fts_path = NULL;
1563 __set_errno (ENAMETOOLONG);
1566 sp->fts_pathlen = new_len;
1567 p = realloc(sp->fts_path, sp->fts_pathlen);
1570 sp->fts_path = NULL;
1578 * When the file name is realloc'd, have to fix all of the pointers in
1579 * structures already returned.
1583 fts_padjust (FTS *sp, FTSENT *head)
1586 char *addr = sp->fts_path;
1588 #define ADJUST(p) do { \
1589 if ((p)->fts_accpath != (p)->fts_name) { \
1590 (p)->fts_accpath = \
1591 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1593 (p)->fts_path = addr; \
1595 /* Adjust the current set of children. */
1596 for (p = sp->fts_child; p; p = p->fts_link)
1599 /* Adjust the rest of the tree, including the current level. */
1600 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1602 p = p->fts_link ? p->fts_link : p->fts_parent;
1608 fts_maxarglen (char * const *argv)
1612 for (max = 0; *argv; ++argv)
1613 if ((len = strlen(*argv)) > max)
1619 * Change to dir specified by fd or file name without getting
1620 * tricked by someone changing the world out from underneath us.
1621 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1622 * If FD is non-negative, expect it to be used after this function returns,
1623 * and to be closed eventually. So don't pass e.g., `dirfd(dirp)' and then
1624 * do closedir(dirp), because that would invalidate the saved FD.
1625 * Upon failure, close FD immediately and return nonzero.
1629 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1632 bool is_dotdot = dir && STREQ (dir, "..");
1635 /* This clause handles the unusual case in which FTS_NOCHDIR
1636 is specified, along with FTS_CWDFD. In that case, there is
1637 no need to change even the virtual cwd file descriptor.
1638 However, if FD is non-negative, we do close it here. */
1639 if (ISSET (FTS_NOCHDIR))
1641 if (ISSET (FTS_CWDFD) && 0 <= fd)
1646 if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
1648 /* When possible, skip the diropen and subsequent fstat+dev/ino
1649 comparison. I.e., when changing to parent directory
1650 (chdir ("..")), use a file descriptor from the ring and
1651 save the overhead of diropen+fstat, as well as avoiding
1652 failure when we lack "x" access to the virtual cwd. */
1653 if ( ! i_ring_empty (&sp->fts_fd_ring))
1656 fd_ring_print (sp, stderr, "pre-pop");
1657 parent_fd = i_ring_pop (&sp->fts_fd_ring);
1668 if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
1671 /* The following dev/inode check is necessary if we're doing a
1672 `logical' traversal (through symlinks, a la chown -L), if the
1673 system lacks O_NOFOLLOW support, or if we're changing to ".."
1674 (but not via a popped file descriptor). When changing to the
1675 name "..", O_NOFOLLOW can't help. In general, when the target is
1676 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
1677 follow a symlink, so we can avoid the expense of this fstat. */
1678 if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
1679 || (dir && STREQ (dir, "..")))
1682 if (fstat(newfd, &sb))
1687 if (p->fts_statp->st_dev != sb.st_dev
1688 || p->fts_statp->st_ino != sb.st_ino)
1690 __set_errno (ENOENT); /* disinformation */
1696 if (ISSET(FTS_CWDFD))
1698 cwd_advance_fd (sp, newfd, ! is_dotdot);
1702 ret = fchdir(newfd);
1708 __set_errno (oerrno);