lib/fts.c

   1 /* Traverse a file hierarchy.
   2
   3    Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   4
   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.
   9
  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.
  14
  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/>.  */
  17
  18 /*-
  19  * Copyright (c) 1990, 1993, 1994
  20  *      The Regents of the University of California.  All rights reserved.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  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.
  33  *
  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
  44  * SUCH DAMAGE.
  45  */
  46
  47 #include <config.h>
  48
  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 */
  52
  53 #include "fts_.h"
  54
  55 #if HAVE_SYS_PARAM_H || defined _LIBC
  56 # include <sys/param.h>
  57 #endif
  58 #ifdef _LIBC
  59 # include <include/sys/stat.h>
  60 #else
  61 # include <sys/stat.h>
  62 #endif
  63 #include <fcntl.h>
  64 #include <errno.h>
  65 #include "dirfd.h"
  66 #include <stdbool.h>
  67 #include <stdlib.h>
  68 #include <string.h>
  69 #include <unistd.h>
  70
  71 #if ! _LIBC
  72 # include "fcntl--.h"
  73 # include "lstat.h"
  74 # include "openat.h"
  75 # include "unistd--.h"
  76 # include "same-inode.h"
  77 #endif
  78
  79 #include <dirent.h>
  80 #ifndef _D_EXACT_NAMLEN
  81 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
  82 #endif
  83
  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))
  89 #else
  90 # define DT_IS_KNOWN(d) false
  91 # define DT_MUST_BE(d, t) false
  92 #endif
  93
  94 enum Fts_stat
  95 {
  96   FTS_NO_STAT_REQUIRED = 1,
  97   FTS_STAT_REQUIRED = 2
  98 };
  99
 100 #ifdef _LIBC
 101 # undef close
 102 # define close __close
 103 # undef closedir
 104 # define closedir __closedir
 105 # undef fchdir
 106 # define fchdir __fchdir
 107 # undef open
 108 # define open __open
 109 # undef opendir
 110 # define opendir __opendir
 111 # undef readdir
 112 # define readdir __readdir
 113 #else
 114 # undef internal_function
 115 # define internal_function /* empty */
 116 #endif
 117
 118 #ifndef __set_errno
 119 # define __set_errno(Val) errno = (Val)
 120 #endif
 121
 122 #ifndef __attribute__
 123 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
 124 #  define __attribute__(x) /* empty */
 125 # endif
 126 #endif
 127
 128 #ifndef ATTRIBUTE_UNUSED
 129 # define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
 130 #endif
 131
 132 /* If this host provides the openat function, then we can avoid
 133    attempting to open "." in some initialization code below.  */
 134 #ifdef HAVE_OPENAT
 135 # define HAVE_OPENAT_SUPPORT 1
 136 #else
 137 # define HAVE_OPENAT_SUPPORT 0
 138 #endif
 139
 140 #ifdef NDEBUG
 141 # define fts_assert(expr) ((void) 0)
 142 #else
 143 # define fts_assert(expr)       \
 144     do                          \
 145       {                         \
 146         if (!(expr))            \
 147           abort ();             \
 148       }                         \
 149     while (false)
 150 #endif
 151
 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 *)
 162      internal_function;
 163
 164 #if GNULIB_FTS
 165 # include "fts-cycle.c"
 166 #else
 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) {}
 171 #endif
 172
 173 #ifndef MAX
 174 # define MAX(a,b) ((a) > (b) ? (a) : (b))
 175 #endif
 176
 177 #ifndef SIZE_MAX
 178 # define SIZE_MAX ((size_t) -1)
 179 #endif
 180
 181 #ifndef O_DIRECTORY
 182 # define O_DIRECTORY 0
 183 #endif
 184
 185 #define ISDOT(a)        (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
 186 #define STREQ(a, b)     (strcmp ((a), (b)) == 0)
 187
 188 #define CLR(opt)        (sp->fts_options &= ~(opt))
 189 #define ISSET(opt)      (sp->fts_options & (opt))
 190 #define SET(opt)        (sp->fts_options |= (opt))
 191
 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)))
 196
 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) \
 202                            : fchdir (fd)))
 203
 204
 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 */
 210
 211 #if FTS_DEBUG
 212 # include <inttypes.h>
 213 # include <stdint.h>
 214 # include <stdio.h>
 215 # include "getcwdat.h"
 216 bool fts_debug = false;
 217 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
 218 #else
 219 # define Dprintf(x)
 220 # define fd_ring_check(x)
 221 # define fd_ring_print(a, b, c)
 222 #endif
 223
 224 #define LEAVE_DIR(Fts, Ent, Tag)                                \
 225   do                                                            \
 226     {                                                           \
 227       Dprintf (("  %s-leaving: %s\n", Tag, (Ent)->fts_path));   \
 228       leave_dir (Fts, Ent);                                     \
 229       fd_ring_check (Fts);                                      \
 230     }                                                           \
 231   while (false)
 232
 233 static void
 234 fd_ring_clear (I_ring *fd_ring)
 235 {
 236   while ( ! i_ring_empty (fd_ring))
 237     {
 238       int fd = i_ring_pop (fd_ring);
 239       if (0 <= fd)
 240         close (fd);
 241     }
 242 }
 243
 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.  */
 247 static void
 248 fts_set_stat_required (FTSENT *p, bool required)
 249 {
 250   fts_assert (p->fts_info == FTS_NSOK);
 251   p->fts_statp->st_size = (required
 252                            ? FTS_STAT_REQUIRED
 253                            : FTS_NO_STAT_REQUIRED);
 254 }
 255
 256 /* file-descriptor-relative opendir.  */
 257 /* FIXME: if others need this function, move it into lib/openat.c */
 258 static inline DIR *
 259 internal_function
 260 opendirat (int fd, char const *dir)
 261 {
 262   int new_fd = openat (fd, dir, O_RDONLY);
 263   DIR *dirp;
 264
 265   if (new_fd < 0)
 266     return NULL;
 267   dirp = fdopendir (new_fd);
 268   if (dirp == NULL)
 269     {
 270       int saved_errno = errno;
 271       close (new_fd);
 272       errno = saved_errno;
 273     }
 274   return dirp;
 275 }
 276
 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
 281    down.  */
 282 static void
 283 internal_function
 284 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
 285 {
 286   int old = sp->fts_cwd_fd;
 287   fts_assert (old != fd || old == AT_FDCWD);
 288
 289   if (chdir_down_one)
 290     {
 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 */
 297     }
 298   else if ( ! ISSET (FTS_NOCHDIR))
 299     {
 300       if (0 <= old)
 301         close (old); /* ignore any close failure */
 302     }
 303
 304   sp->fts_cwd_fd = fd;
 305 }
 306
 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.  */
 310
 311 static inline int
 312 internal_function
 313 diropen (FTS const *sp, char const *dir)
 314 {
 315   int open_flags = (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
 316                     | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0));
 317
 318   return (ISSET (FTS_CWDFD)
 319           ? openat (sp->fts_cwd_fd, dir, open_flags)
 320           : open (dir, open_flags));
 321 }
 322
 323 FTS *
 324 fts_open (char * const *argv,
 325           register int options,
 326           int (*compar) (FTSENT const **, FTSENT const **))
 327 {
 328         register FTS *sp;
 329         register FTSENT *p, *root;
 330         register size_t nitems;
 331         FTSENT *parent = NULL;
 332         FTSENT *tmp = NULL;     /* pacify gcc */
 333         size_t len;
 334         bool defer_stat;
 335
 336         /* Options check. */
 337         if (options & ~FTS_OPTIONMASK) {
 338                 __set_errno (EINVAL);
 339                 return (NULL);
 340         }
 341         if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {
 342                 __set_errno (EINVAL);
 343                 return (NULL);
 344         }
 345         if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {
 346                 __set_errno (EINVAL);
 347                 return (NULL);
 348         }
 349
 350         /* Allocate/initialize the stream */
 351         if ((sp = malloc(sizeof(FTS))) == NULL)
 352                 return (NULL);
 353         memset(sp, 0, sizeof(FTS));
 354         sp->fts_compar = compar;
 355         sp->fts_options = options;
 356
 357         /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
 358         if (ISSET(FTS_LOGICAL)) {
 359                 SET(FTS_NOCHDIR);
 360                 CLR(FTS_CWDFD);
 361         }
 362
 363         /* Initialize fts_cwd_fd.  */
 364         sp->fts_cwd_fd = AT_FDCWD;
 365         if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)
 366           {
 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);
 372             if (fd < 0)
 373               {
 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 ())
 386                   {
 387                     SET(FTS_NOCHDIR);
 388                     CLR(FTS_CWDFD);
 389                   }
 390               }
 391             else
 392               {
 393                 close (fd);
 394               }
 395           }
 396
 397         /*
 398          * Start out with 1K of file name space, and enough, in any case,
 399          * to hold the user's file names.
 400          */
 401 #ifndef MAXPATHLEN
 402 # define MAXPATHLEN 1024
 403 #endif
 404         {
 405           size_t maxarglen = fts_maxarglen(argv);
 406           if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
 407                   goto mem1;
 408         }
 409
 410         /* Allocate/initialize root's parent. */
 411         if (*argv != NULL) {
 412                 if ((parent = fts_alloc(sp, "", 0)) == NULL)
 413                         goto mem2;
 414                 parent->fts_level = FTS_ROOTPARENTLEVEL;
 415           }
 416
 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));
 429
 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);
 435                         goto mem3;
 436                 }
 437
 438                 if ((p = fts_alloc(sp, *argv, len)) == NULL)
 439                         goto mem3;
 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);
 449                 } else {
 450                         p->fts_info = fts_stat(sp, p, false);
 451                 }
 452
 453                 /*
 454                  * If comparison routine supplied, traverse in sorted
 455                  * order; otherwise traverse in the order specified.
 456                  */
 457                 if (compar) {
 458                         p->fts_link = root;
 459                         root = p;
 460                 } else {
 461                         p->fts_link = NULL;
 462                         if (root == NULL)
 463                                 tmp = root = p;
 464                         else {
 465                                 tmp->fts_link = p;
 466                                 tmp = p;
 467                         }
 468                 }
 469         }
 470         if (compar && nitems > 1)
 471                 root = fts_sort(sp, root, nitems);
 472
 473         /*
 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.
 477          */
 478         if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
 479                 goto mem3;
 480         sp->fts_cur->fts_link = root;
 481         sp->fts_cur->fts_info = FTS_INIT;
 482         if (! setup_dir (sp))
 483                 goto mem3;
 484
 485         /*
 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.
 491          */
 492         if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)
 493             && (sp->fts_rfd = diropen (sp, ".")) < 0)
 494                 SET(FTS_NOCHDIR);
 495
 496         i_ring_init (&sp->fts_fd_ring, -1);
 497         return (sp);
 498
 499 mem3:   fts_lfree(root);
 500         free(parent);
 501 mem2:   free(sp->fts_path);
 502 mem1:   free(sp);
 503         return (NULL);
 504 }
 505
 506 static void
 507 internal_function
 508 fts_load (FTS *sp, register FTSENT *p)
 509 {
 510         register size_t len;
 511         register char *cp;
 512
 513         /*
 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.
 519          */
 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])) {
 523                 len = strlen(++cp);
 524                 memmove(p->fts_name, cp, len + 1);
 525                 p->fts_namelen = len;
 526         }
 527         p->fts_accpath = p->fts_path = sp->fts_path;
 528 }
 529
 530 int
 531 fts_close (FTS *sp)
 532 {
 533         register FTSENT *freep, *p;
 534         int saved_errno = 0;
 535
 536         /*
 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.
 540          */
 541         if (sp->fts_cur) {
 542                 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
 543                         freep = p;
 544                         p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
 545                         free(freep);
 546                 }
 547                 free(p);
 548         }
 549
 550         /* Free up child linked list, sort array, file name buffer. */
 551         if (sp->fts_child)
 552                 fts_lfree(sp->fts_child);
 553         free(sp->fts_array);
 554         free(sp->fts_path);
 555
 556         if (ISSET(FTS_CWDFD))
 557           {
 558             if (0 <= sp->fts_cwd_fd)
 559               close (sp->fts_cwd_fd);
 560           }
 561         else if (!ISSET(FTS_NOCHDIR))
 562           {
 563             /* Return to original directory, save errno if necessary. */
 564             if (fchdir(sp->fts_rfd))
 565               saved_errno = errno;
 566             close(sp->fts_rfd);
 567           }
 568
 569         fd_ring_clear (&sp->fts_fd_ring);
 570         free_dir (sp);
 571
 572         /* Free up the stream pointer. */
 573         free(sp);
 574
 575         /* Set errno and return. */
 576         if (saved_errno) {
 577                 __set_errno (saved_errno);
 578                 return (-1);
 579         }
 580
 581         return (0);
 582 }
 583
 584 /*
 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".
 587  */
 588 #define NAPPEND(p)                                                      \
 589         (p->fts_path[p->fts_pathlen - 1] == '/'                         \
 590             ? p->fts_pathlen - 1 : p->fts_pathlen)
 591
 592 FTSENT *
 593 fts_read (register FTS *sp)
 594 {
 595         register FTSENT *p, *tmp;
 596         register unsigned short int instr;
 597         register char *t;
 598
 599         /* If finished or unrecoverable error, return NULL. */
 600         if (sp->fts_cur == NULL || ISSET(FTS_STOP))
 601                 return (NULL);
 602
 603         /* Set current node pointer. */
 604         p = sp->fts_cur;
 605
 606         /* Save and zero out user instructions. */
 607         instr = p->fts_instr;
 608         p->fts_instr = FTS_NOINSTR;
 609
 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);
 613                 return (p);
 614         }
 615         Dprintf (("fts_read: p=%s\n",
 616                   p->fts_info == FTS_INIT ? "" : p->fts_path));
 617
 618         /*
 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.
 623          */
 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;
 631                         } else
 632                                 p->fts_flags |= FTS_SYMFOLLOW;
 633                 }
 634                 goto check_for_dir;
 635         }
 636
 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);
 644                         if (sp->fts_child) {
 645                                 fts_lfree(sp->fts_child);
 646                                 sp->fts_child = NULL;
 647                         }
 648                         p->fts_info = FTS_DP;
 649                         LEAVE_DIR (sp, p, "1");
 650                         return (p);
 651                 }
 652
 653                 /* Rebuild if only read the names and now traversing. */
 654                 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
 655                         CLR(FTS_NAMEONLY);
 656                         fts_lfree(sp->fts_child);
 657                         sp->fts_child = NULL;
 658                 }
 659
 660                 /*
 661                  * Cd to the subdirectory.
 662                  *
 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.
 668                  *
 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.
 671                  */
 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;
 677                                      p = p->fts_link)
 678                                         p->fts_accpath =
 679                                             p->fts_parent->fts_accpath;
 680                         }
 681                 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
 682                         if (ISSET(FTS_STOP))
 683                                 return (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");
 690                         return (p);
 691                 }
 692                 p = sp->fts_child;
 693                 sp->fts_child = NULL;
 694                 goto name;
 695         }
 696
 697         /* Move to the next node on this level. */
 698 next:   tmp = p;
 699         if ((p = p->fts_link) != NULL) {
 700                 sp->fts_cur = p;
 701                 free(tmp);
 702
 703                 /*
 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
 706                  * root.
 707                  */
 708                 if (p->fts_level == FTS_ROOTLEVEL) {
 709                         if (RESTORE_INITIAL_CWD(sp)) {
 710                                 SET(FTS_STOP);
 711                                 return (NULL);
 712                         }
 713                         fts_load(sp, p);
 714                         goto check_for_dir;
 715                 }
 716
 717                 /*
 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.
 721                  */
 722                 if (p->fts_instr == FTS_SKIP)
 723                         goto next;
 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;
 730                                 } else
 731                                         p->fts_flags |= FTS_SYMFOLLOW;
 732                         }
 733                         p->fts_instr = FTS_NOINSTR;
 734                 }
 735
 736 name:           t = sp->fts_path + NAPPEND(p->fts_parent);
 737                 *t++ = '/';
 738                 memmove(t, p->fts_name, p->fts_namelen + 1);
 739 check_for_dir:
 740                 sp->fts_cur = p;
 741                 if (p->fts_info == FTS_NSOK)
 742                   {
 743                     if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
 744                       p->fts_info = fts_stat(sp, p, false);
 745                     else
 746                       fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
 747                   }
 748
 749                 if (p->fts_info == FTS_D)
 750                   {
 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))
 758                       {
 759                         __set_errno (ENOMEM);
 760                         return NULL;
 761                       }
 762                   }
 763                 return p;
 764         }
 765
 766         /* Move up to the parent node. */
 767         p = tmp->fts_parent;
 768         sp->fts_cur = p;
 769         free(tmp);
 770
 771         if (p->fts_level == FTS_ROOTPARENTLEVEL) {
 772                 /*
 773                  * Done; free everything up and set errno to 0 so the user
 774                  * can distinguish between error and EOF.
 775                  */
 776                 free(p);
 777                 __set_errno (0);
 778                 return (sp->fts_cur = NULL);
 779         }
 780
 781         fts_assert (p->fts_info != FTS_NSOK);
 782
 783         /* NUL terminate the file name.  */
 784         sp->fts_path[p->fts_pathlen] = '\0';
 785
 786         /*
 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 "..".
 791          */
 792         if (p->fts_level == FTS_ROOTLEVEL) {
 793                 if (RESTORE_INITIAL_CWD(sp)) {
 794                         p->fts_errno = errno;
 795                         SET(FTS_STOP);
 796                 }
 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;
 803                         SET(FTS_STOP);
 804                 }
 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;
 809                 SET(FTS_STOP);
 810         }
 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;
 815 }
 816
 817 /*
 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
 821  * reasons.
 822  */
 823 /* ARGSUSED */
 824 int
 825 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
 826 {
 827         if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
 828             instr != FTS_NOINSTR && instr != FTS_SKIP) {
 829                 __set_errno (EINVAL);
 830                 return (1);
 831         }
 832         p->fts_instr = instr;
 833         return (0);
 834 }
 835
 836 FTSENT *
 837 fts_children (register FTS *sp, int instr)
 838 {
 839         register FTSENT *p;
 840         int fd;
 841
 842         if (instr != 0 && instr != FTS_NAMEONLY) {
 843                 __set_errno (EINVAL);
 844                 return (NULL);
 845         }
 846
 847         /* Set current node pointer. */
 848         p = sp->fts_cur;
 849
 850         /*
 851          * Errno set to 0 so user can distinguish empty directory from
 852          * an error.
 853          */
 854         __set_errno (0);
 855
 856         /* Fatal errors stop here. */
 857         if (ISSET(FTS_STOP))
 858                 return (NULL);
 859
 860         /* Return logical hierarchy of user's arguments. */
 861         if (p->fts_info == FTS_INIT)
 862                 return (p->fts_link);
 863
 864         /*
 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.
 868          */
 869         if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
 870                 return (NULL);
 871
 872         /* Free up any previous child list. */
 873         if (sp->fts_child != NULL)
 874                 fts_lfree(sp->fts_child);
 875
 876         if (instr == FTS_NAMEONLY) {
 877                 SET(FTS_NAMEONLY);
 878                 instr = BNAMES;
 879         } else
 880                 instr = BCHILD;
 881
 882         /*
 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.
 888          */
 889         if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
 890             ISSET(FTS_NOCHDIR))
 891                 return (sp->fts_child = fts_build(sp, instr));
 892
 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))
 897           {
 898             cwd_advance_fd (sp, fd, true);
 899           }
 900         else
 901           {
 902             if (fchdir(fd))
 903               {
 904                 int saved_errno = errno;
 905                 close (fd);
 906                 __set_errno (saved_errno);
 907                 return NULL;
 908               }
 909             close (fd);
 910           }
 911         return (sp->fts_child);
 912 }
 913
 914 /*
 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.
 918  *
 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.
 927  */
 928 static FTSENT *
 929 internal_function
 930 fts_build (register FTS *sp, int type)
 931 {
 932         register struct dirent *dp;
 933         register FTSENT *p, *head;
 934         register size_t nitems;
 935         FTSENT *cur, *tail;
 936         DIR *dirp;
 937         void *oldaddr;
 938         int saved_errno;
 939         bool descend;
 940         bool doadjust;
 941         ptrdiff_t level;
 942         nlink_t nlinks;
 943         bool nostat;
 944         size_t len, maxlen, new_len;
 945         char *cp;
 946
 947         /* Set current node pointer. */
 948         cur = sp->fts_cur;
 949
 950         /*
 951          * Open the directory for reading.  If this fails, we're done.
 952          * If being called from fts_read, set the fts_info field.
 953          */
 954 #if defined FTS_WHITEOUT && 0
 955         if (ISSET(FTS_WHITEOUT))
 956                 oflag = DTF_NODUP|DTF_REWIND;
 957         else
 958                 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
 959 #else
 960 # define __opendir2(file, flag) \
 961         ( ! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
 962           ? opendirat(sp->fts_cwd_fd, file)        \
 963           : opendir(file))
 964 #endif
 965        if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
 966                 if (type == BREAD) {
 967                         cur->fts_info = FTS_DNR;
 968                         cur->fts_errno = errno;
 969                 }
 970                 return (NULL);
 971         }
 972        /* Rather than calling fts_stat for each and every entry encountered
 973           in the readdir loop (below), stat each directory only right after
 974           opening it.  */
 975        if (cur->fts_info == FTS_NSOK)
 976          cur->fts_info = fts_stat(sp, cur, false);
 977
 978         /*
 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.
 982          */
 983         if (type == BNAMES) {
 984                 nlinks = 0;
 985                 /* Be quiet about nostat, GCC. */
 986                 nostat = false;
 987         } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
 988                 nlinks = (cur->fts_statp->st_nlink
 989                           - (ISSET(FTS_SEEDOT) ? 0 : 2));
 990                 nostat = true;
 991         } else {
 992                 nlinks = -1;
 993                 nostat = false;
 994         }
 995
 996         /*
 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.
1010          */
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;
1019                         descend = false;
1020                         closedir(dirp);
1021                         if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1022                                 close (dir_fd);
1023                         dirp = NULL;
1024                 } else
1025                         descend = true;
1026         } else
1027                 descend = false;
1028
1029         /*
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.
1035          *
1036          * If not changing directories set a pointer so that can just append
1037          * each new component into the file name.
1038          */
1039         len = NAPPEND(cur);
1040         if (ISSET(FTS_NOCHDIR)) {
1041                 cp = sp->fts_path + len;
1042                 *cp++ = '/';
1043         } else {
1044                 /* GCC, you're too verbose. */
1045                 cp = NULL;
1046         }
1047         len++;
1048         maxlen = sp->fts_pathlen - len;
1049
1050         level = cur->fts_level + 1;
1051
1052         /* Read the directory, attaching each entry to the `link' pointer. */
1053         doadjust = false;
1054         for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
1055                 bool is_dir;
1056
1057                 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1058                         continue;
1059
1060                 if ((p = fts_alloc (sp, dp->d_name,
1061                                     _D_EXACT_NAMLEN (dp))) == NULL)
1062                         goto mem1;
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)) {
1067                                 /*
1068                                  * No more memory.  Save
1069                                  * errno, free up the current structure and the
1070                                  * structures already allocated.
1071                                  */
1072 mem1:                           saved_errno = errno;
1073                                 free(p);
1074                                 fts_lfree(head);
1075                                 closedir(dirp);
1076                                 cur->fts_info = FTS_ERR;
1077                                 SET(FTS_STOP);
1078                                 __set_errno (saved_errno);
1079                                 return (NULL);
1080                         }
1081                         /* Did realloc() change the pointer? */
1082                         if (oldaddr != sp->fts_path) {
1083                                 doadjust = true;
1084                                 if (ISSET(FTS_NOCHDIR))
1085                                         cp = sp->fts_path + len;
1086                         }
1087                         maxlen = sp->fts_pathlen - len;
1088                 }
1089
1090                 new_len = len + _D_EXACT_NAMLEN (dp);
1091                 if (new_len < len) {
1092                         /*
1093                          * In the unlikely even 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.
1097                          */
1098                         free(p);
1099                         fts_lfree(head);
1100                         closedir(dirp);
1101                         cur->fts_info = FTS_ERR;
1102                         SET(FTS_STOP);
1103                         __set_errno (ENAMETOOLONG);
1104                         return (NULL);
1105                 }
1106                 p->fts_level = level;
1107                 p->fts_parent = sp->fts_cur;
1108                 p->fts_pathlen = new_len;
1109
1110 #if defined FTS_WHITEOUT && 0
1111                 if (dp->d_type == DT_WHT)
1112                         p->fts_flags |= FTS_ISW;
1113 #endif
1114
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);
1119                 } else
1120                         p->fts_accpath = p->fts_name;
1121
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
1134                            be valid.  */
1135                         bool skip_stat = (ISSET(FTS_PHYSICAL)
1136                                           && ISSET(FTS_NOSTAT)
1137                                           && DT_IS_KNOWN(dp)
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));
1143                 } else {
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);
1148                 }
1149
1150                 /* Decrement link count if applicable. */
1151                 if (nlinks > 0 && is_dir)
1152                         nlinks -= nostat;
1153
1154                 /* We walk in directory order so "ls -f" doesn't get upset. */
1155                 p->fts_link = NULL;
1156                 if (head == NULL)
1157                         head = tail = p;
1158                 else {
1159                         tail->fts_link = p;
1160                         tail = p;
1161                 }
1162                 ++nitems;
1163         }
1164         if (dirp)
1165                 closedir(dirp);
1166
1167         /*
1168          * If realloc() changed the address of the file name, adjust the
1169          * addresses for the rest of the tree and the dir list.
1170          */
1171         if (doadjust)
1172                 fts_padjust(sp, head);
1173
1174         /*
1175          * If not changing directories, reset the file name back to original
1176          * state.
1177          */
1178         if (ISSET(FTS_NOCHDIR)) {
1179                 if (len == sp->fts_pathlen || nitems == 0)
1180                         --cp;
1181                 *cp = '\0';
1182         }
1183
1184         /*
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.
1190          */
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;
1196                 SET(FTS_STOP);
1197                 fts_lfree(head);
1198                 return (NULL);
1199         }
1200
1201         /* If didn't find anything, return NULL. */
1202         if (!nitems) {
1203                 if (type == BREAD)
1204                         cur->fts_info = FTS_DP;
1205                 fts_lfree(head);
1206                 return (NULL);
1207         }
1208
1209         /* Sort the entries. */
1210         if (sp->fts_compar && nitems > 1)
1211                 head = fts_sort(sp, head, nitems);
1212         return (head);
1213 }
1214
1215 #if FTS_DEBUG
1216
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.  */
1220 static void
1221 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1222 {
1223   FTSENT const *ent;
1224   for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1225     {
1226       if (ad->ino == ent->fts_statp->st_ino
1227           && ad->dev == ent->fts_statp->st_dev)
1228         return;
1229     }
1230   printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1231   printf ("active dirs:\n");
1232   for (ent = e_curr;
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,
1238             ent->fts_accpath,
1239             (uintmax_t) ent->fts_statp->st_dev,
1240             (uintmax_t) ent->fts_statp->st_ino);
1241 }
1242
1243 void
1244 fts_cross_check (FTS const *sp)
1245 {
1246   FTSENT const *ent = sp->fts_cur;
1247   FTSENT const *t;
1248   if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1249     return;
1250
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)
1254     {
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);
1260     }
1261
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))
1267     {
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))
1271         {
1272           find_matching_ancestor (ent, ad);
1273         }
1274     }
1275 }
1276
1277 static bool
1278 same_fd (int fd1, int fd2)
1279 {
1280   struct stat sb1, sb2;
1281   return (fstat (fd1, &sb1) == 0
1282           && fstat (fd2, &sb2) == 0
1283           && SAME_INODE (sb1, sb2));
1284 }
1285
1286 static void
1287 fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
1288 {
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);
1293   free (cwd);
1294   if (i_ring_empty (fd_ring))
1295     return;
1296
1297   while (true)
1298     {
1299       int fd = fd_ring->fts_fd_ring[i];
1300       if (fd < 0)
1301         fprintf (stream, "%d: %d:\n", i, fd);
1302       else
1303         {
1304           char *wd = getcwdat (fd, NULL, 0);
1305           fprintf (stream, "%d: %d: %s\n", i, fd, wd);
1306           free (wd);
1307         }
1308       if (i == fd_ring->fts_back)
1309         break;
1310       i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
1311     }
1312 }
1313
1314 /* Ensure that each file descriptor on the fd_ring matches a
1315    parent, grandparent, etc. of the current working directory.  */
1316 static void
1317 fd_ring_check (FTS const *sp)
1318 {
1319   if (!fts_debug)
1320     return;
1321
1322   /* Make a writable copy.  */
1323   I_ring fd_w = sp->fts_fd_ring;
1324
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);
1329   free (dot);
1330   while ( ! i_ring_empty (&fd_w))
1331     {
1332       int fd = i_ring_pop (&fd_w);
1333       if (0 <= fd)
1334         {
1335           int parent_fd = openat (cwd_fd, "..", O_RDONLY);
1336           if (parent_fd < 0)
1337             {
1338               // Warn?
1339               break;
1340             }
1341           if (!same_fd (fd, parent_fd))
1342             {
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);
1347               free (cwd);
1348               free (c2);
1349               fts_assert (0);
1350             }
1351           close (cwd_fd);
1352           cwd_fd = parent_fd;
1353         }
1354     }
1355   close (cwd_fd);
1356 }
1357 #endif
1358
1359 static unsigned short int
1360 internal_function
1361 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1362 {
1363         struct stat *sbp = p->fts_statp;
1364         int saved_errno;
1365
1366         if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
1367                 follow = true;
1368
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;
1374                 return (FTS_W);
1375        }
1376 #endif
1377
1378         /*
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.
1382          */
1383         if (ISSET(FTS_LOGICAL) || follow) {
1384                 if (stat(p->fts_accpath, sbp)) {
1385                         saved_errno = errno;
1386                         if (errno == ENOENT
1387                             && lstat(p->fts_accpath, sbp) == 0) {
1388                                 __set_errno (0);
1389                                 return (FTS_SLNONE);
1390                         }
1391                         p->fts_errno = saved_errno;
1392                         goto err;
1393                 }
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));
1398                 return (FTS_NS);
1399         }
1400
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);
1405                 }
1406
1407 #if !GNULIB_FTS
1408                 {
1409                   /*
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.
1414                    */
1415                   FTSENT *t;
1416
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)
1421                       {
1422                         p->fts_cycle = t;
1423                         return (FTS_DC);
1424                       }
1425                 }
1426 #endif
1427
1428                 return (FTS_D);
1429         }
1430         if (S_ISLNK(sbp->st_mode))
1431                 return (FTS_SL);
1432         if (S_ISREG(sbp->st_mode))
1433                 return (FTS_F);
1434         return (FTS_DEFAULT);
1435 }
1436
1437 static int
1438 fts_compar (void const *a, void const *b)
1439 {
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
1444      check for this.  */
1445   FTSENT const **pa = (FTSENT const **) a;
1446   FTSENT const **pb = (FTSENT const **) b;
1447   return pa[0]->fts_fts->fts_compar (pa, pb);
1448 }
1449
1450 static FTSENT *
1451 internal_function
1452 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1453 {
1454         register FTSENT **ap, *p;
1455
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.  */
1463         FTSENT *dummy;
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
1468            : fts_compar);
1469
1470         /*
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.
1476          */
1477         if (nitems > sp->fts_nitems) {
1478                 FTSENT **a;
1479
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;
1486                         sp->fts_nitems = 0;
1487                         return (head);
1488                 }
1489                 sp->fts_array = a;
1490         }
1491         for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1492                 *ap++ = p;
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;
1497         return (head);
1498 }
1499
1500 static FTSENT *
1501 internal_function
1502 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1503 {
1504         register FTSENT *p;
1505         size_t len;
1506
1507         /*
1508          * The file name is a variable length array.  Allocate the FTSENT
1509          * structure and the file name in one chunk.
1510          */
1511         len = sizeof(FTSENT) + namelen;
1512         if ((p = malloc(len)) == NULL)
1513                 return (NULL);
1514
1515         /* Copy the name and guarantee NUL termination. */
1516         memmove(p->fts_name, name, namelen);
1517         p->fts_name[namelen] = '\0';
1518
1519         p->fts_namelen = namelen;
1520         p->fts_fts = sp;
1521         p->fts_path = sp->fts_path;
1522         p->fts_errno = 0;
1523         p->fts_flags = 0;
1524         p->fts_instr = FTS_NOINSTR;
1525         p->fts_number = 0;
1526         p->fts_pointer = NULL;
1527         return (p);
1528 }
1529
1530 static void
1531 internal_function
1532 fts_lfree (register FTSENT *head)
1533 {
1534         register FTSENT *p;
1535
1536         /* Free a linked list of structures. */
1537         while ((p = head)) {
1538                 head = head->fts_link;
1539                 free(p);
1540         }
1541 }
1542
1543 /*
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.
1549  */
1550 static bool
1551 internal_function
1552 fts_palloc (FTS *sp, size_t more)
1553 {
1554         char *p;
1555         size_t new_len = sp->fts_pathlen + more + 256;
1556
1557         /*
1558          * See if fts_pathlen would overflow.
1559          */
1560         if (new_len < sp->fts_pathlen) {
1561                 free(sp->fts_path);
1562                 sp->fts_path = NULL;
1563                 __set_errno (ENAMETOOLONG);
1564                 return false;
1565         }
1566         sp->fts_pathlen = new_len;
1567         p = realloc(sp->fts_path, sp->fts_pathlen);
1568         if (p == NULL) {
1569                 free(sp->fts_path);
1570                 sp->fts_path = NULL;
1571                 return false;
1572         }
1573         sp->fts_path = p;
1574         return true;
1575 }
1576
1577 /*
1578  * When the file name is realloc'd, have to fix all of the pointers in
1579  *  structures already returned.
1580  */
1581 static void
1582 internal_function
1583 fts_padjust (FTS *sp, FTSENT *head)
1584 {
1585         FTSENT *p;
1586         char *addr = sp->fts_path;
1587
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);  \
1592         }                                                               \
1593         (p)->fts_path = addr;                                           \
1594 } while (0)
1595         /* Adjust the current set of children. */
1596         for (p = sp->fts_child; p; p = p->fts_link)
1597                 ADJUST(p);
1598
1599         /* Adjust the rest of the tree, including the current level. */
1600         for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1601                 ADJUST(p);
1602                 p = p->fts_link ? p->fts_link : p->fts_parent;
1603         }
1604 }
1605
1606 static size_t
1607 internal_function
1608 fts_maxarglen (char * const *argv)
1609 {
1610         size_t len, max;
1611
1612         for (max = 0; *argv; ++argv)
1613                 if ((len = strlen(*argv)) > max)
1614                         max = len;
1615         return (max + 1);
1616 }
1617
1618 /*
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.
1626  */
1627 static int
1628 internal_function
1629 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1630 {
1631         int ret;
1632         bool is_dotdot = dir && STREQ (dir, "..");
1633         int newfd;
1634
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))
1640           {
1641             if (ISSET (FTS_CWDFD) && 0 <= fd)
1642               close (fd);
1643             return 0;
1644           }
1645
1646         if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
1647           {
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))
1654               {
1655                 int parent_fd;
1656                 fd_ring_print (sp, stderr, "pre-pop");
1657                 parent_fd = i_ring_pop (&sp->fts_fd_ring);
1658                 is_dotdot = true;
1659                 if (0 <= parent_fd)
1660                   {
1661                     fd = parent_fd;
1662                     dir = NULL;
1663                   }
1664               }
1665           }
1666
1667         newfd = fd;
1668         if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
1669           return -1;
1670
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, "..")))
1680           {
1681             struct stat sb;
1682             if (fstat(newfd, &sb))
1683               {
1684                 ret = -1;
1685                 goto bail;
1686               }
1687             if (p->fts_statp->st_dev != sb.st_dev
1688                 || p->fts_statp->st_ino != sb.st_ino)
1689               {
1690                 __set_errno (ENOENT);           /* disinformation */
1691                 ret = -1;
1692                 goto bail;
1693               }
1694           }
1695
1696         if (ISSET(FTS_CWDFD))
1697           {
1698             cwd_advance_fd (sp, newfd, ! is_dotdot);
1699             return 0;
1700           }
1701
1702         ret = fchdir(newfd);
1703 bail:
1704         if (fd < 0)
1705           {
1706             int oerrno = errno;
1707             (void)close(newfd);
1708             __set_errno (oerrno);
1709           }
1710         return ret;
1711 }