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>
73 # include "unistd--.h"
74 # include "same-inode.h"
78 #ifndef _D_EXACT_NAMLEN
79 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
82 #if HAVE_STRUCT_DIRENT_D_TYPE
83 /* True if the type of the directory entry D is known. */
84 # define DT_IS_KNOWN(d) ((d)->d_type != DT_UNKNOWN)
85 /* True if the type of the directory entry D must be T. */
86 # define DT_MUST_BE(d, t) ((d)->d_type == (t))
87 # define D_TYPE(d) ((d)->d_type)
89 # define DT_IS_KNOWN(d) false
90 # define DT_MUST_BE(d, t) false
91 # define D_TYPE(d) DT_UNKNOWN
96 /* Any nonzero values will do here, so long as they're distinct.
97 Undef any existing macros out of the way. */
116 NOT_AN_INODE_NUMBER = 0
119 #ifdef D_INO_IN_DIRENT
120 # define D_INO(dp) (dp)->d_ino
122 /* Some systems don't have inodes, so fake them to avoid lots of ifdefs. */
123 # define D_INO(dp) NOT_AN_INODE_NUMBER
126 /* If there are more than this many entries in a directory,
127 and the conditions mentioned below are satisfied, then sort
128 the entries on inode number before any further processing. */
129 #ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
130 # define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000
134 _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD = FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
139 FTS_NO_STAT_REQUIRED = 1,
140 FTS_STAT_REQUIRED = 2
145 # define close __close
147 # define closedir __closedir
149 # define fchdir __fchdir
153 # define opendir __opendir
155 # define readdir __readdir
157 # undef internal_function
158 # define internal_function /* empty */
162 # define __set_errno(Val) errno = (Val)
165 #ifndef __attribute__
166 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8)
167 # define __attribute__(x) /* empty */
171 #ifndef ATTRIBUTE_UNUSED
172 # define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
175 /* If this host provides the openat function, then we can avoid
176 attempting to open "." in some initialization code below. */
178 # define HAVE_OPENAT_SUPPORT 1
180 # define HAVE_OPENAT_SUPPORT 0
184 # define fts_assert(expr) ((void) 0)
186 # define fts_assert(expr) \
195 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
196 static FTSENT *fts_build (FTS *, int) internal_function;
197 static void fts_lfree (FTSENT *) internal_function;
198 static void fts_load (FTS *, FTSENT *) internal_function;
199 static size_t fts_maxarglen (char * const *) internal_function;
200 static void fts_padjust (FTS *, FTSENT *) internal_function;
201 static bool fts_palloc (FTS *, size_t) internal_function;
202 static FTSENT *fts_sort (FTS *, FTSENT *, size_t) internal_function;
203 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
204 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
208 # include "fts-cycle.c"
210 static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
211 static void leave_dir (FTS *fts, FTSENT *ent) {}
212 static bool setup_dir (FTS *fts) { return true; }
213 static void free_dir (FTS *fts) {}
217 # define MAX(a,b) ((a) > (b) ? (a) : (b))
221 # define SIZE_MAX ((size_t) -1)
225 # define O_DIRECTORY 0
228 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
229 #define STREQ(a, b) (strcmp ((a), (b)) == 0)
231 #define CLR(opt) (sp->fts_options &= ~(opt))
232 #define ISSET(opt) (sp->fts_options & (opt))
233 #define SET(opt) (sp->fts_options |= (opt))
235 /* FIXME: make this a function */
236 #define RESTORE_INITIAL_CWD(sp) \
237 (fd_ring_clear (&((sp)->fts_fd_ring)), \
238 FCHDIR ((sp), (ISSET (FTS_CWDFD) ? AT_FDCWD : (sp)->fts_rfd)))
240 /* FIXME: FTS_NOCHDIR is now misnamed.
241 Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
242 #define FCHDIR(sp, fd) \
243 (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \
244 ? (cwd_advance_fd ((sp), (fd), true), 0) \
248 /* fts_build flags */
249 /* FIXME: make this an enum */
250 #define BCHILD 1 /* fts_children */
251 #define BNAMES 2 /* fts_children, names only */
252 #define BREAD 3 /* fts_read */
255 # include <inttypes.h>
258 # include "getcwdat.h"
259 bool fts_debug = false;
260 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
263 # define fd_ring_check(x)
264 # define fd_ring_print(a, b, c)
267 #define LEAVE_DIR(Fts, Ent, Tag) \
270 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
271 leave_dir (Fts, Ent); \
272 fd_ring_check (Fts); \
277 fd_ring_clear (I_ring *fd_ring)
279 while ( ! i_ring_empty (fd_ring))
281 int fd = i_ring_pop (fd_ring);
287 /* Overload the fts_statp->st_size member (otherwise unused, when
288 fts_info is FTS_NSOK) to indicate whether fts_read should stat
289 this entry or not. */
291 fts_set_stat_required (FTSENT *p, bool required)
293 fts_assert (p->fts_info == FTS_NSOK);
294 p->fts_statp->st_size = (required
296 : FTS_NO_STAT_REQUIRED);
299 /* file-descriptor-relative opendir. */
300 /* FIXME: if others need this function, move it into lib/openat.c */
303 opendirat (int fd, char const *dir)
305 int new_fd = openat (fd, dir, O_RDONLY);
310 dirp = fdopendir (new_fd);
313 int saved_errno = errno;
320 /* Virtual fchdir. Advance SP's working directory file descriptor,
321 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
322 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
323 open on sp->fts_cwd_fd; i.e., to move the working directory one level
327 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
329 int old = sp->fts_cwd_fd;
330 fts_assert (old != fd || old == AT_FDCWD);
334 /* Push "old" onto the ring.
335 If the displaced file descriptor is non-negative, close it. */
336 int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);
337 fd_ring_print (sp, stderr, "post-push");
338 if (0 <= prev_fd_in_slot)
339 close (prev_fd_in_slot); /* ignore any close failure */
341 else if ( ! ISSET (FTS_NOCHDIR))
344 close (old); /* ignore any close failure */
350 /* Open the directory DIR if possible, and return a file
351 descriptor. Return -1 and set errno on failure. It doesn't matter
352 whether the file descriptor has read or write access. */
356 diropen (FTS const *sp, char const *dir)
358 int open_flags = (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
359 | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0));
361 return (ISSET (FTS_CWDFD)
362 ? openat (sp->fts_cwd_fd, dir, open_flags)
363 : open (dir, open_flags));
367 fts_open (char * const *argv,
368 register int options,
369 int (*compar) (FTSENT const **, FTSENT const **))
372 register FTSENT *p, *root;
373 register size_t nitems;
374 FTSENT *parent = NULL;
375 FTSENT *tmp = NULL; /* pacify gcc */
380 if (options & ~FTS_OPTIONMASK) {
381 __set_errno (EINVAL);
384 if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {
385 __set_errno (EINVAL);
388 if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {
389 __set_errno (EINVAL);
393 /* Allocate/initialize the stream */
394 if ((sp = malloc(sizeof(FTS))) == NULL)
396 memset(sp, 0, sizeof(FTS));
397 sp->fts_compar = compar;
398 sp->fts_options = options;
400 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
401 if (ISSET(FTS_LOGICAL)) {
406 /* Initialize fts_cwd_fd. */
407 sp->fts_cwd_fd = AT_FDCWD;
408 if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)
410 /* While it isn't technically necessary to open "." this
411 early, doing it here saves us the trouble of ensuring
412 later (where it'd be messier) that "." can in fact
413 be opened. If not, revert to FTS_NOCHDIR mode. */
414 int fd = open (".", O_RDONLY);
417 /* Even if `.' is unreadable, don't revert to FTS_NOCHDIR mode
418 on systems like Linux+PROC_FS, where our openat emulation
419 is good enough. Note: on a system that emulates
420 openat via /proc, this technique can still fail, but
421 only in extreme conditions, e.g., when the working
422 directory cannot be saved (i.e. save_cwd fails) --
423 and that happens on Linux only when "." is unreadable
424 and the CWD would be longer than PATH_MAX.
425 FIXME: once Linux kernel openat support is well established,
426 replace the above open call and this entire if/else block
427 with the body of the if-block below. */
428 if ( openat_needs_fchdir ())
441 * Start out with 1K of file name space, and enough, in any case,
442 * to hold the user's file names.
445 # define MAXPATHLEN 1024
448 size_t maxarglen = fts_maxarglen(argv);
449 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
453 /* Allocate/initialize root's parent. */
455 if ((parent = fts_alloc(sp, "", 0)) == NULL)
457 parent->fts_level = FTS_ROOTPARENTLEVEL;
460 /* The classic fts implementation would call fts_stat with
461 a new entry for each iteration of the loop below.
462 If the comparison function is not specified or if the
463 FTS_DEFER_STAT option is in effect, don't stat any entry
464 in this loop. This is an attempt to minimize the interval
465 between the initial stat/lstat/fstatat and the point at which
466 a directory argument is first opened. This matters for any
467 directory command line argument that resides on a file system
468 without genuine i-nodes. If you specify FTS_DEFER_STAT along
469 with a comparison function, that function must not access any
470 data via the fts_statp pointer. */
471 defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));
473 /* Allocate/initialize root(s). */
474 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
475 /* Don't allow zero-length file names. */
476 if ((len = strlen(*argv)) == 0) {
477 __set_errno (ENOENT);
481 if ((p = fts_alloc(sp, *argv, len)) == NULL)
483 p->fts_level = FTS_ROOTLEVEL;
484 p->fts_parent = parent;
485 p->fts_accpath = p->fts_name;
486 /* Even when defer_stat is true, be sure to stat the first
487 command line argument, since fts_read (at least with
488 FTS_XDEV) requires that. */
489 if (defer_stat && root != NULL) {
490 p->fts_info = FTS_NSOK;
491 fts_set_stat_required(p, true);
493 p->fts_info = fts_stat(sp, p, false);
497 * If comparison routine supplied, traverse in sorted
498 * order; otherwise traverse in the order specified.
513 if (compar && nitems > 1)
514 root = fts_sort(sp, root, nitems);
517 * Allocate a dummy pointer and make fts_read think that we've just
518 * finished the node before the root(s); set p->fts_info to FTS_INIT
519 * so that everything about the "current" node is ignored.
521 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
523 sp->fts_cur->fts_link = root;
524 sp->fts_cur->fts_info = FTS_INIT;
525 if (! setup_dir (sp))
529 * If using chdir(2), grab a file descriptor pointing to dot to ensure
530 * that we can get back here; this could be avoided for some file names,
531 * but almost certainly not worth the effort. Slashes, symbolic links,
532 * and ".." are all fairly nasty problems. Note, if we can't get the
533 * descriptor we run anyway, just more slowly.
535 if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)
536 && (sp->fts_rfd = diropen (sp, ".")) < 0)
539 i_ring_init (&sp->fts_fd_ring, -1);
542 mem3: fts_lfree(root);
544 mem2: free(sp->fts_path);
551 fts_load (FTS *sp, register FTSENT *p)
557 * Load the stream structure for the next traversal. Since we don't
558 * actually enter the directory until after the preorder visit, set
559 * the fts_accpath field specially so the chdir gets done to the right
560 * place and the user can access the first node. From fts_open it's
561 * known that the file name will fit.
563 len = p->fts_pathlen = p->fts_namelen;
564 memmove(sp->fts_path, p->fts_name, len + 1);
565 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
567 memmove(p->fts_name, cp, len + 1);
568 p->fts_namelen = len;
570 p->fts_accpath = p->fts_path = sp->fts_path;
576 register FTSENT *freep, *p;
580 * This still works if we haven't read anything -- the dummy structure
581 * points to the root list, so we step through to the end of the root
582 * list which has a valid parent pointer.
585 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
587 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
593 /* Free up child linked list, sort array, file name buffer. */
595 fts_lfree(sp->fts_child);
599 if (ISSET(FTS_CWDFD))
601 if (0 <= sp->fts_cwd_fd)
602 close (sp->fts_cwd_fd);
604 else if (!ISSET(FTS_NOCHDIR))
606 /* Return to original directory, save errno if necessary. */
607 if (fchdir(sp->fts_rfd))
612 fd_ring_clear (&sp->fts_fd_ring);
615 /* Free up the stream pointer. */
618 /* Set errno and return. */
620 __set_errno (saved_errno);
628 * Special case of "/" at the end of the file name so that slashes aren't
629 * appended which would cause file names to be written as "....//foo".
632 (p->fts_path[p->fts_pathlen - 1] == '/' \
633 ? p->fts_pathlen - 1 : p->fts_pathlen)
636 fts_read (register FTS *sp)
638 register FTSENT *p, *tmp;
639 register unsigned short int instr;
642 /* If finished or unrecoverable error, return NULL. */
643 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
646 /* Set current node pointer. */
649 /* Save and zero out user instructions. */
650 instr = p->fts_instr;
651 p->fts_instr = FTS_NOINSTR;
653 /* Any type of file may be re-visited; re-stat and re-turn. */
654 if (instr == FTS_AGAIN) {
655 p->fts_info = fts_stat(sp, p, false);
658 Dprintf (("fts_read: p=%s\n",
659 p->fts_info == FTS_INIT ? "" : p->fts_path));
662 * Following a symlink -- SLNONE test allows application to see
663 * SLNONE and recover. If indirecting through a symlink, have
664 * keep a pointer to current location. If unable to get that
665 * pointer, follow fails.
667 if (instr == FTS_FOLLOW &&
668 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
669 p->fts_info = fts_stat(sp, p, true);
670 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
671 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
672 p->fts_errno = errno;
673 p->fts_info = FTS_ERR;
675 p->fts_flags |= FTS_SYMFOLLOW;
680 /* Directory in pre-order. */
681 if (p->fts_info == FTS_D) {
682 /* If skipped or crossed mount point, do post-order visit. */
683 if (instr == FTS_SKIP ||
684 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
685 if (p->fts_flags & FTS_SYMFOLLOW)
686 (void)close(p->fts_symfd);
688 fts_lfree(sp->fts_child);
689 sp->fts_child = NULL;
691 p->fts_info = FTS_DP;
692 LEAVE_DIR (sp, p, "1");
696 /* Rebuild if only read the names and now traversing. */
697 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
699 fts_lfree(sp->fts_child);
700 sp->fts_child = NULL;
704 * Cd to the subdirectory.
706 * If have already read and now fail to chdir, whack the list
707 * to make the names come out right, and set the parent errno
708 * so the application will eventually get an error condition.
709 * Set the FTS_DONTCHDIR flag so that when we logically change
710 * directories back to the parent we don't do a chdir.
712 * If haven't read do so. If the read fails, fts_build sets
713 * FTS_STOP or the fts_info field of the node.
715 if (sp->fts_child != NULL) {
716 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
717 p->fts_errno = errno;
718 p->fts_flags |= FTS_DONTCHDIR;
719 for (p = sp->fts_child; p != NULL;
722 p->fts_parent->fts_accpath;
724 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
727 /* If fts_build's call to fts_safe_changedir failed
728 because it was not able to fchdir into a
729 subdirectory, tell the caller. */
730 if (p->fts_errno && p->fts_info != FTS_DNR)
731 p->fts_info = FTS_ERR;
732 LEAVE_DIR (sp, p, "2");
736 sp->fts_child = NULL;
740 /* Move to the next node on this level. */
742 if ((p = p->fts_link) != NULL) {
747 * If reached the top, return to the original directory (or
748 * the root of the tree), and load the file names for the next
751 if (p->fts_level == FTS_ROOTLEVEL) {
752 if (RESTORE_INITIAL_CWD(sp)) {
761 * User may have called fts_set on the node. If skipped,
762 * ignore. If followed, get a file descriptor so we can
763 * get back if necessary.
765 if (p->fts_instr == FTS_SKIP)
767 if (p->fts_instr == FTS_FOLLOW) {
768 p->fts_info = fts_stat(sp, p, true);
769 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
770 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
771 p->fts_errno = errno;
772 p->fts_info = FTS_ERR;
774 p->fts_flags |= FTS_SYMFOLLOW;
776 p->fts_instr = FTS_NOINSTR;
779 name: t = sp->fts_path + NAPPEND(p->fts_parent);
781 memmove(t, p->fts_name, p->fts_namelen + 1);
784 if (p->fts_info == FTS_NSOK)
786 if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
787 p->fts_info = fts_stat(sp, p, false);
789 fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
792 if (p->fts_info == FTS_D)
794 /* Now that P->fts_statp is guaranteed to be valid,
795 if this is a command-line directory, record its
796 device number, to be used for FTS_XDEV. */
797 if (p->fts_level == FTS_ROOTLEVEL)
798 sp->fts_dev = p->fts_statp->st_dev;
799 Dprintf ((" entering: %s\n", p->fts_path));
800 if (! enter_dir (sp, p))
802 __set_errno (ENOMEM);
809 /* Move up to the parent node. */
814 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
816 * Done; free everything up and set errno to 0 so the user
817 * can distinguish between error and EOF.
821 return (sp->fts_cur = NULL);
824 fts_assert (p->fts_info != FTS_NSOK);
826 /* NUL terminate the file name. */
827 sp->fts_path[p->fts_pathlen] = '\0';
830 * Return to the parent directory. If at a root node, restore
831 * the initial working directory. If we came through a symlink,
832 * go back through the file descriptor. Otherwise, move up
833 * one level, via "..".
835 if (p->fts_level == FTS_ROOTLEVEL) {
836 if (RESTORE_INITIAL_CWD(sp)) {
837 p->fts_errno = errno;
840 } else if (p->fts_flags & FTS_SYMFOLLOW) {
841 if (FCHDIR(sp, p->fts_symfd)) {
842 int saved_errno = errno;
843 (void)close(p->fts_symfd);
844 __set_errno (saved_errno);
845 p->fts_errno = errno;
848 (void)close(p->fts_symfd);
849 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
850 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
851 p->fts_errno = errno;
854 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
855 if (p->fts_errno == 0)
856 LEAVE_DIR (sp, p, "3");
857 return ISSET(FTS_STOP) ? NULL : p;
861 * Fts_set takes the stream as an argument although it's not used in this
862 * implementation; it would be necessary if anyone wanted to add global
863 * semantics to fts using fts_set. An error return is allowed for similar
868 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
870 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
871 instr != FTS_NOINSTR && instr != FTS_SKIP) {
872 __set_errno (EINVAL);
875 p->fts_instr = instr;
880 fts_children (register FTS *sp, int instr)
885 if (instr != 0 && instr != FTS_NAMEONLY) {
886 __set_errno (EINVAL);
890 /* Set current node pointer. */
894 * Errno set to 0 so user can distinguish empty directory from
899 /* Fatal errors stop here. */
903 /* Return logical hierarchy of user's arguments. */
904 if (p->fts_info == FTS_INIT)
905 return (p->fts_link);
908 * If not a directory being visited in pre-order, stop here. Could
909 * allow FTS_DNR, assuming the user has fixed the problem, but the
910 * same effect is available with FTS_AGAIN.
912 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
915 /* Free up any previous child list. */
916 if (sp->fts_child != NULL)
917 fts_lfree(sp->fts_child);
919 if (instr == FTS_NAMEONLY) {
926 * If using chdir on a relative file name and called BEFORE fts_read
927 * does its chdir to the root of a traversal, we can lose -- we need to
928 * chdir into the subdirectory, and we don't know where the current
929 * directory is, so we can't get back so that the upcoming chdir by
930 * fts_read will work.
932 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
934 return (sp->fts_child = fts_build(sp, instr));
936 if ((fd = diropen (sp, ".")) < 0)
937 return (sp->fts_child = NULL);
938 sp->fts_child = fts_build(sp, instr);
939 if (ISSET(FTS_CWDFD))
941 cwd_advance_fd (sp, fd, true);
947 int saved_errno = errno;
949 __set_errno (saved_errno);
954 return (sp->fts_child);
957 #if defined __linux__ \
958 && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
962 /* Linux-specific constants from coreutils' src/fs.h */
963 # define S_MAGIC_TMPFS 0x1021994
964 # define S_MAGIC_NFS 0x6969
966 /* Return false if it is easy to determine the file system type of
967 the directory on which DIR_FD is open, and sorting dirents on
968 inode numbers is known not to improve traversal performance with
969 that type of file system. Otherwise, return true. */
971 dirent_inode_sort_may_be_useful (int dir_fd)
973 /* Skip the sort only if we can determine efficiently
974 that skipping it is the right thing to do.
975 The cost of performing an unnecessary sort is negligible,
976 while the cost of *not* performing it can be O(N^2) with
977 a very large constant. */
978 struct statfs fs_buf;
980 /* If fstatfs fails, assume sorting would be useful. */
981 if (fstatfs (dir_fd, &fs_buf) != 0)
984 /* FIXME: what about when f_type is not an integral type?
985 deal with that if/when it's encountered. */
986 switch (fs_buf.f_type)
990 /* On a file system of any of these types, sorting
991 is unnecessary, and hence wasteful. */
999 static bool dirent_inode_sort_may_be_useful (int dir_fd) { return true; }
1002 /* A comparison function to sort on increasing inode number.
1003 For some file system types, sorting either way makes a huge
1004 performance difference for a directory with very many entries,
1005 but sorting on increasing values is slightly better than sorting
1006 on decreasing values. The difference is in the 5% range. */
1008 fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b)
1010 return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? -1
1011 : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? 1 : 0);
1014 /* Return the number of bits by which a d_type value must be shifted
1015 left in order to put it into the S_IFMT bits of stat.st_mode. */
1017 s_ifmt_shift_bits (void)
1019 unsigned int v = S_IFMT; /* usually, 0170000 */
1020 static const int MultiplyDeBruijnBitPosition[32] =
1022 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
1023 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
1026 /* Find the smallest power of two, P (e.g., 0010000) such that P & V == P. */
1027 unsigned int p = v ^ (v & (v - 1));
1029 /* Compute and return r = log2 (p), using code from
1030 http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn */
1031 return MultiplyDeBruijnBitPosition[(uint32_t) (p * 0x077CB531UL) >> 27];
1034 /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode
1035 S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */
1037 set_stat_type (struct stat *st, unsigned int dtype)
1066 st->st_mode = dtype << s_ifmt_shift_bits ();
1070 * This is the tricky part -- do not casually change *anything* in here. The
1071 * idea is to build the linked list of entries that are used by fts_children
1072 * and fts_read. There are lots of special cases.
1074 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
1075 * set and it's a physical walk (so that symbolic links can't be directories),
1076 * we can do things quickly. First, if it's a 4.4BSD file system, the type
1077 * of the file is in the directory entry. Otherwise, we assume that the number
1078 * of subdirectories in a node is equal to the number of links to the parent.
1079 * The former skips all stat calls. The latter skips stat calls in any leaf
1080 * directories and for any files after the subdirectories in the directory have
1081 * been found, cutting the stat calls by about 2/3.
1085 fts_build (register FTS *sp, int type)
1087 register struct dirent *dp;
1088 register FTSENT *p, *head;
1089 register size_t nitems;
1099 size_t len, maxlen, new_len;
1102 /* Set current node pointer. */
1106 * Open the directory for reading. If this fails, we're done.
1107 * If being called from fts_read, set the fts_info field.
1109 #if defined FTS_WHITEOUT && 0
1110 if (ISSET(FTS_WHITEOUT))
1111 oflag = DTF_NODUP|DTF_REWIND;
1113 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
1115 # define __opendir2(file, flag) \
1116 ( ! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
1117 ? opendirat(sp->fts_cwd_fd, file) \
1120 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
1121 if (type == BREAD) {
1122 cur->fts_info = FTS_DNR;
1123 cur->fts_errno = errno;
1127 /* Rather than calling fts_stat for each and every entry encountered
1128 in the readdir loop (below), stat each directory only right after
1130 if (cur->fts_info == FTS_NSOK)
1131 cur->fts_info = fts_stat(sp, cur, false);
1134 * Nlinks is the number of possible entries of type directory in the
1135 * directory if we're cheating on stat calls, 0 if we're not doing
1136 * any stat calls at all, (nlink_t) -1 if we're statting everything.
1138 if (type == BNAMES) {
1140 /* Be quiet about nostat, GCC. */
1142 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
1143 nlinks = (cur->fts_statp->st_nlink
1144 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1152 * If we're going to need to stat anything or we want to descend
1153 * and stay in the directory, chdir. If this fails we keep going,
1154 * but set a flag so we don't chdir after the post-order visit.
1155 * We won't be able to stat anything, but we can still return the
1156 * names themselves. Note, that since fts_read won't be able to
1157 * chdir into the directory, it will have to return different file
1158 * names than before, i.e. "a/b" instead of "b". Since the node
1159 * has already been visited in pre-order, have to wait until the
1160 * post-order visit to return the error. There is a special case
1161 * here, if there was nothing to stat then it's not an error to
1162 * not be able to stat. This is all fairly nasty. If a program
1163 * needed sorted entries or stat information, they had better be
1164 * checking FTS_NS on the returned nodes.
1166 if (nlinks || type == BREAD) {
1167 int dir_fd = dirfd(dirp);
1168 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1169 dir_fd = dup (dir_fd);
1170 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
1171 if (nlinks && type == BREAD)
1172 cur->fts_errno = errno;
1173 cur->fts_flags |= FTS_DONTCHDIR;
1176 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1185 * Figure out the max file name length that can be stored in the
1186 * current buffer -- the inner loop allocates more space as necessary.
1187 * We really wouldn't have to do the maxlen calculations here, we
1188 * could do them in fts_read before returning the name, but it's a
1189 * lot easier here since the length is part of the dirent structure.
1191 * If not changing directories set a pointer so that can just append
1192 * each new component into the file name.
1195 if (ISSET(FTS_NOCHDIR)) {
1196 cp = sp->fts_path + len;
1199 /* GCC, you're too verbose. */
1203 maxlen = sp->fts_pathlen - len;
1205 level = cur->fts_level + 1;
1207 /* Read the directory, attaching each entry to the `link' pointer. */
1209 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
1212 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1215 if ((p = fts_alloc (sp, dp->d_name,
1216 _D_EXACT_NAMLEN (dp))) == NULL)
1218 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
1219 /* include space for NUL */
1220 oldaddr = sp->fts_path;
1221 if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
1223 * No more memory. Save
1224 * errno, free up the current structure and the
1225 * structures already allocated.
1227 mem1: saved_errno = errno;
1231 cur->fts_info = FTS_ERR;
1233 __set_errno (saved_errno);
1236 /* Did realloc() change the pointer? */
1237 if (oldaddr != sp->fts_path) {
1239 if (ISSET(FTS_NOCHDIR))
1240 cp = sp->fts_path + len;
1242 maxlen = sp->fts_pathlen - len;
1245 new_len = len + _D_EXACT_NAMLEN (dp);
1246 if (new_len < len) {
1248 * In the unlikely event that we would end up
1249 * with a file name longer than SIZE_MAX, free up
1250 * the current structure and the structures already
1251 * allocated, then error out with ENAMETOOLONG.
1256 cur->fts_info = FTS_ERR;
1258 __set_errno (ENAMETOOLONG);
1261 p->fts_level = level;
1262 p->fts_parent = sp->fts_cur;
1263 p->fts_pathlen = new_len;
1265 #if defined FTS_WHITEOUT && 0
1266 if (dp->d_type == DT_WHT)
1267 p->fts_flags |= FTS_ISW;
1269 /* Store dirent.d_ino, in case we need to sort
1270 entries before processing them. */
1271 p->fts_statp->st_ino = D_INO (dp);
1273 /* Build a file name for fts_stat to stat. */
1274 if (ISSET(FTS_NOCHDIR)) {
1275 p->fts_accpath = p->fts_path;
1276 memmove(cp, p->fts_name, p->fts_namelen + 1);
1278 p->fts_accpath = p->fts_name;
1280 if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {
1281 /* Record what fts_read will have to do with this
1282 entry. In many cases, it will simply fts_stat it,
1283 but we can take advantage of any d_type information
1284 to optimize away the unnecessary stat calls. I.e.,
1285 if FTS_NOSTAT is in effect and we're not following
1286 symlinks (FTS_PHYSICAL) and d_type indicates this
1287 is *not* a directory, then we won't have to stat it
1288 at all. If it *is* a directory, then (currently)
1289 we stat it regardless, in order to get device and
1290 inode numbers. Some day we might optimize that
1291 away, too, for directories where d_ino is known to
1293 bool skip_stat = (ISSET(FTS_PHYSICAL)
1294 && ISSET(FTS_NOSTAT)
1296 && ! DT_MUST_BE(dp, DT_DIR));
1297 p->fts_info = FTS_NSOK;
1298 /* Propagate dirent.d_type information back
1299 to caller, when possible. */
1300 set_stat_type (p->fts_statp, D_TYPE (dp));
1301 fts_set_stat_required(p, !skip_stat);
1302 is_dir = (ISSET(FTS_PHYSICAL) && ISSET(FTS_NOSTAT)
1303 && DT_MUST_BE(dp, DT_DIR));
1305 p->fts_info = fts_stat(sp, p, false);
1306 is_dir = (p->fts_info == FTS_D
1307 || p->fts_info == FTS_DC
1308 || p->fts_info == FTS_DOT);
1311 /* Decrement link count if applicable. */
1312 if (nlinks > 0 && is_dir)
1315 /* We walk in directory order so "ls -f" doesn't get upset. */
1329 * If realloc() changed the address of the file name, adjust the
1330 * addresses for the rest of the tree and the dir list.
1333 fts_padjust(sp, head);
1336 * If not changing directories, reset the file name back to original
1339 if (ISSET(FTS_NOCHDIR)) {
1340 if (len == sp->fts_pathlen || nitems == 0)
1346 * If descended after called from fts_children or after called from
1347 * fts_read and nothing found, get back. At the root level we use
1348 * the saved fd; if one of fts_open()'s arguments is a relative name
1349 * to an empty directory, we wind up here with no other way back. If
1350 * can't get back, we're done.
1352 if (descend && (type == BCHILD || !nitems) &&
1353 (cur->fts_level == FTS_ROOTLEVEL
1354 ? RESTORE_INITIAL_CWD(sp)
1355 : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1356 cur->fts_info = FTS_ERR;
1362 /* If didn't find anything, return NULL. */
1365 cur->fts_info = FTS_DP;
1370 /* If there are many entries, no sorting function has been specified,
1371 and this file system is of a type that may be slow with a large
1372 number of entries, then sort the directory entries on increasing
1374 if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
1376 && ISSET (FTS_CWDFD)
1377 && dirent_inode_sort_may_be_useful (sp->fts_cwd_fd)) {
1378 sp->fts_compar = fts_compare_ino;
1379 head = fts_sort (sp, head, nitems);
1380 sp->fts_compar = NULL;
1383 /* Sort the entries. */
1384 if (sp->fts_compar && nitems > 1)
1385 head = fts_sort(sp, head, nitems);
1391 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1392 current hierarchy. There should be a directory with dev/inode
1393 matching those of AD. If not, print a lot of diagnostics. */
1395 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1398 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1400 if (ad->ino == ent->fts_statp->st_ino
1401 && ad->dev == ent->fts_statp->st_dev)
1404 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1405 printf ("active dirs:\n");
1407 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1408 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1409 ad->fts_ent->fts_accpath,
1410 (uintmax_t) ad->dev,
1411 (uintmax_t) ad->ino,
1413 (uintmax_t) ent->fts_statp->st_dev,
1414 (uintmax_t) ent->fts_statp->st_ino);
1418 fts_cross_check (FTS const *sp)
1420 FTSENT const *ent = sp->fts_cur;
1422 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1425 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1426 /* Make sure every parent dir is in the tree. */
1427 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1429 struct Active_dir ad;
1430 ad.ino = t->fts_statp->st_ino;
1431 ad.dev = t->fts_statp->st_dev;
1432 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1433 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1436 /* Make sure every dir in the tree is an active dir.
1437 But ENT is not necessarily a directory. If so, just skip this part. */
1438 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1439 && (ent->fts_info == FTS_DP
1440 || ent->fts_info == FTS_D))
1442 struct Active_dir *ad;
1443 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1444 ad = hash_get_next (sp->fts_cycle.ht, ad))
1446 find_matching_ancestor (ent, ad);
1452 same_fd (int fd1, int fd2)
1454 struct stat sb1, sb2;
1455 return (fstat (fd1, &sb1) == 0
1456 && fstat (fd2, &sb2) == 0
1457 && SAME_INODE (sb1, sb2));
1461 fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
1463 I_ring const *fd_ring = &sp->fts_fd_ring;
1464 unsigned int i = fd_ring->fts_front;
1465 char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0);
1466 fprintf (stream, "=== %s ========== %s\n", msg, cwd);
1468 if (i_ring_empty (fd_ring))
1473 int fd = fd_ring->fts_fd_ring[i];
1475 fprintf (stream, "%d: %d:\n", i, fd);
1478 char *wd = getcwdat (fd, NULL, 0);
1479 fprintf (stream, "%d: %d: %s\n", i, fd, wd);
1482 if (i == fd_ring->fts_back)
1484 i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
1488 /* Ensure that each file descriptor on the fd_ring matches a
1489 parent, grandparent, etc. of the current working directory. */
1491 fd_ring_check (FTS const *sp)
1496 /* Make a writable copy. */
1497 I_ring fd_w = sp->fts_fd_ring;
1499 int cwd_fd = sp->fts_cwd_fd;
1500 cwd_fd = dup (cwd_fd);
1501 char *dot = getcwdat (cwd_fd, NULL, 0);
1502 error (0, 0, "===== check ===== cwd: %s", dot);
1504 while ( ! i_ring_empty (&fd_w))
1506 int fd = i_ring_pop (&fd_w);
1509 int parent_fd = openat (cwd_fd, "..", O_RDONLY);
1515 if (!same_fd (fd, parent_fd))
1517 char *cwd = getcwdat (fd, NULL, 0);
1518 error (0, errno, "ring : %s", cwd);
1519 char *c2 = getcwdat (parent_fd, NULL, 0);
1520 error (0, errno, "parent: %s", c2);
1533 static unsigned short int
1535 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1537 struct stat *sbp = p->fts_statp;
1540 if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
1543 #if defined FTS_WHITEOUT && 0
1544 /* check for whiteout */
1545 if (p->fts_flags & FTS_ISW) {
1546 memset(sbp, '\0', sizeof (*sbp));
1547 sbp->st_mode = S_IFWHT;
1553 * If doing a logical walk, or application requested FTS_FOLLOW, do
1554 * a stat(2). If that fails, check for a non-existent symlink. If
1555 * fail, set the errno from the stat call.
1557 if (ISSET(FTS_LOGICAL) || follow) {
1558 if (stat(p->fts_accpath, sbp)) {
1559 saved_errno = errno;
1561 && lstat(p->fts_accpath, sbp) == 0) {
1563 return (FTS_SLNONE);
1565 p->fts_errno = saved_errno;
1568 } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp,
1569 AT_SYMLINK_NOFOLLOW)) {
1570 p->fts_errno = errno;
1571 err: memset(sbp, 0, sizeof(struct stat));
1575 if (S_ISDIR(sbp->st_mode)) {
1576 if (ISDOT(p->fts_name)) {
1577 /* Command-line "." and ".." are real directories. */
1578 return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
1584 * Cycle detection is done by brute force when the directory
1585 * is first encountered. If the tree gets deep enough or the
1586 * number of symbolic links to directories is high enough,
1587 * something faster might be worthwhile.
1591 for (t = p->fts_parent;
1592 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1593 if (sbp->st_ino == t->fts_statp->st_ino
1594 && sbp->st_dev == t->fts_statp->st_dev)
1604 if (S_ISLNK(sbp->st_mode))
1606 if (S_ISREG(sbp->st_mode))
1608 return (FTS_DEFAULT);
1612 fts_compar (void const *a, void const *b)
1614 /* Convert A and B to the correct types, to pacify the compiler, and
1615 for portability to bizarre hosts where "void const *" and "FTSENT
1616 const **" differ in runtime representation. The comparison
1617 function cannot modify *a and *b, but there is no compile-time
1619 FTSENT const **pa = (FTSENT const **) a;
1620 FTSENT const **pb = (FTSENT const **) b;
1621 return pa[0]->fts_fts->fts_compar (pa, pb);
1626 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1628 register FTSENT **ap, *p;
1630 /* On most modern hosts, void * and FTSENT ** have the same
1631 run-time representation, and one can convert sp->fts_compar to
1632 the type qsort expects without problem. Use the heuristic that
1633 this is OK if the two pointer types are the same size, and if
1634 converting FTSENT ** to long int is the same as converting
1635 FTSENT ** to void * and then to long int. This heuristic isn't
1636 valid in general but we don't know of any counterexamples. */
1638 int (*compare) (void const *, void const *) =
1639 ((sizeof &dummy == sizeof (void *)
1640 && (long int) &dummy == (long int) (void *) &dummy)
1641 ? (int (*) (void const *, void const *)) sp->fts_compar
1645 * Construct an array of pointers to the structures and call qsort(3).
1646 * Reassemble the array in the order returned by qsort. If unable to
1647 * sort for memory reasons, return the directory entries in their
1648 * current order. Allocate enough space for the current needs plus
1649 * 40 so don't realloc one entry at a time.
1651 if (nitems > sp->fts_nitems) {
1654 sp->fts_nitems = nitems + 40;
1655 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1656 || ! (a = realloc (sp->fts_array,
1657 sp->fts_nitems * sizeof *a))) {
1658 free(sp->fts_array);
1659 sp->fts_array = NULL;
1665 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1667 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1668 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1669 ap[0]->fts_link = ap[1];
1670 ap[0]->fts_link = NULL;
1676 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1682 * The file name is a variable length array. Allocate the FTSENT
1683 * structure and the file name in one chunk.
1685 len = sizeof(FTSENT) + namelen;
1686 if ((p = malloc(len)) == NULL)
1689 /* Copy the name and guarantee NUL termination. */
1690 memmove(p->fts_name, name, namelen);
1691 p->fts_name[namelen] = '\0';
1693 p->fts_namelen = namelen;
1695 p->fts_path = sp->fts_path;
1698 p->fts_instr = FTS_NOINSTR;
1700 p->fts_pointer = NULL;
1706 fts_lfree (register FTSENT *head)
1710 /* Free a linked list of structures. */
1711 while ((p = head)) {
1712 head = head->fts_link;
1718 * Allow essentially unlimited file name lengths; find, rm, ls should
1719 * all work on any tree. Most systems will allow creation of file
1720 * names much longer than MAXPATHLEN, even though the kernel won't
1721 * resolve them. Add the size (not just what's needed) plus 256 bytes
1722 * so don't realloc the file name 2 bytes at a time.
1726 fts_palloc (FTS *sp, size_t more)
1729 size_t new_len = sp->fts_pathlen + more + 256;
1732 * See if fts_pathlen would overflow.
1734 if (new_len < sp->fts_pathlen) {
1736 sp->fts_path = NULL;
1737 __set_errno (ENAMETOOLONG);
1740 sp->fts_pathlen = new_len;
1741 p = realloc(sp->fts_path, sp->fts_pathlen);
1744 sp->fts_path = NULL;
1752 * When the file name is realloc'd, have to fix all of the pointers in
1753 * structures already returned.
1757 fts_padjust (FTS *sp, FTSENT *head)
1760 char *addr = sp->fts_path;
1762 #define ADJUST(p) do { \
1763 if ((p)->fts_accpath != (p)->fts_name) { \
1764 (p)->fts_accpath = \
1765 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1767 (p)->fts_path = addr; \
1769 /* Adjust the current set of children. */
1770 for (p = sp->fts_child; p; p = p->fts_link)
1773 /* Adjust the rest of the tree, including the current level. */
1774 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1776 p = p->fts_link ? p->fts_link : p->fts_parent;
1782 fts_maxarglen (char * const *argv)
1786 for (max = 0; *argv; ++argv)
1787 if ((len = strlen(*argv)) > max)
1793 * Change to dir specified by fd or file name without getting
1794 * tricked by someone changing the world out from underneath us.
1795 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1796 * If FD is non-negative, expect it to be used after this function returns,
1797 * and to be closed eventually. So don't pass e.g., `dirfd(dirp)' and then
1798 * do closedir(dirp), because that would invalidate the saved FD.
1799 * Upon failure, close FD immediately and return nonzero.
1803 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1806 bool is_dotdot = dir && STREQ (dir, "..");
1809 /* This clause handles the unusual case in which FTS_NOCHDIR
1810 is specified, along with FTS_CWDFD. In that case, there is
1811 no need to change even the virtual cwd file descriptor.
1812 However, if FD is non-negative, we do close it here. */
1813 if (ISSET (FTS_NOCHDIR))
1815 if (ISSET (FTS_CWDFD) && 0 <= fd)
1820 if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
1822 /* When possible, skip the diropen and subsequent fstat+dev/ino
1823 comparison. I.e., when changing to parent directory
1824 (chdir ("..")), use a file descriptor from the ring and
1825 save the overhead of diropen+fstat, as well as avoiding
1826 failure when we lack "x" access to the virtual cwd. */
1827 if ( ! i_ring_empty (&sp->fts_fd_ring))
1830 fd_ring_print (sp, stderr, "pre-pop");
1831 parent_fd = i_ring_pop (&sp->fts_fd_ring);
1842 if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
1845 /* The following dev/inode check is necessary if we're doing a
1846 `logical' traversal (through symlinks, a la chown -L), if the
1847 system lacks O_NOFOLLOW support, or if we're changing to ".."
1848 (but not via a popped file descriptor). When changing to the
1849 name "..", O_NOFOLLOW can't help. In general, when the target is
1850 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
1851 follow a symlink, so we can avoid the expense of this fstat. */
1852 if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
1853 || (dir && STREQ (dir, "..")))
1856 if (fstat(newfd, &sb))
1861 if (p->fts_statp->st_dev != sb.st_dev
1862 || p->fts_statp->st_ino != sb.st_ino)
1864 __set_errno (ENOENT); /* disinformation */
1870 if (ISSET(FTS_CWDFD))
1872 cwd_advance_fd (sp, newfd, ! is_dotdot);
1876 ret = fchdir(newfd);
1882 __set_errno (oerrno);