lib/fts.c

   1 /* Traverse a file hierarchy.
   2
   3    Copyright (C) 2004, 2005, 2006 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 2, or (at your option)
   8    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, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 /*-
  20  * Copyright (c) 1990, 1993, 1994
  21  *      The Regents of the University of California.  All rights reserved.
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that the following conditions
  25  * are met:
  26  * 1. Redistributions of source code must retain the above copyright
  27  *    notice, this list of conditions and the following disclaimer.
  28  * 2. Redistributions in binary form must reproduce the above copyright
  29  *    notice, this list of conditions and the following disclaimer in the
  30  *    documentation and/or other materials provided with the distribution.
  31  * 4. Neither the name of the University nor the names of its contributors
  32  *    may be used to endorse or promote products derived from this software
  33  *    without specific prior written permission.
  34  *
  35  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  36  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  37  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  38  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  39  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  40  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  41  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  42  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  43  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  44  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  45  * SUCH DAMAGE.
  46  */
  47
  48 #include <config.h>
  49
  50 #if defined(LIBC_SCCS) && !defined(lint)
  51 static char sccsid[] = "@(#)fts.c       8.6 (Berkeley) 8/14/94";
  52 #endif /* LIBC_SCCS and not lint */
  53
  54 #include "fts_.h"
  55
  56 #if HAVE_SYS_PARAM_H || defined _LIBC
  57 # include <sys/param.h>
  58 #endif
  59 #ifdef _LIBC
  60 # include <include/sys/stat.h>
  61 #else
  62 # include <sys/stat.h>
  63 #endif
  64 #include <fcntl.h>
  65 #include <errno.h>
  66 #include "dirfd.h"
  67 #include <stdbool.h>
  68 #include <stdlib.h>
  69 #include <string.h>
  70 #include <unistd.h>
  71
  72 #if ! _LIBC
  73 # include "fcntl--.h"
  74 # include "lstat.h"
  75 # include "openat.h"
  76 # include "unistd--.h"
  77 # include "same-inode.h"
  78 #endif
  79
  80 #include <dirent.h>
  81 #ifndef _D_EXACT_NAMLEN
  82 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
  83 #endif
  84
  85 #if HAVE_STRUCT_DIRENT_D_TYPE
  86 /* True if the type of the directory entry D is known.  */
  87 # define DT_IS_KNOWN(d) ((d)->d_type != DT_UNKNOWN)
  88 /* True if the type of the directory entry D must be T.  */
  89 # define DT_MUST_BE(d, t) ((d)->d_type == (t))
  90 #else
  91 # define DT_IS_KNOWN(d) false
  92 # define DT_MUST_BE(d, t) false
  93 #endif
  94
  95 enum Fts_stat
  96 {
  97   FTS_NO_STAT_REQUIRED = 1,
  98   FTS_STAT_REQUIRED = 2
  99 };
 100
 101 #ifdef _LIBC
 102 # undef close
 103 # define close __close
 104 # undef closedir
 105 # define closedir __closedir
 106 # undef fchdir
 107 # define fchdir __fchdir
 108 # undef open
 109 # define open __open
 110 # undef opendir
 111 # define opendir __opendir
 112 # undef readdir
 113 # define readdir __readdir
 114 #else
 115 # undef internal_function
 116 # define internal_function /* empty */
 117 #endif
 118
 119 #ifndef __set_errno
 120 # define __set_errno(Val) errno = (Val)
 121 #endif
 122
 123 #ifndef __attribute__
 124 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
 125 #  define __attribute__(x) /* empty */
 126 # endif
 127 #endif
 128
 129 #ifndef ATTRIBUTE_UNUSED
 130 # define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
 131 #endif
 132
 133 /* If this host provides the openat function, then we can avoid
 134    attempting to open "." in some initialization code below.  */
 135 #ifdef HAVE_OPENAT
 136 # define HAVE_OPENAT_SUPPORT 1
 137 #else
 138 # define HAVE_OPENAT_SUPPORT 0
 139 #endif
 140
 141 static FTSENT   *fts_alloc (FTS *, const char *, size_t) internal_function;
 142 static FTSENT   *fts_build (FTS *, int) internal_function;
 143 static void      fts_lfree (FTSENT *) internal_function;
 144 static void      fts_load (FTS *, FTSENT *) internal_function;
 145 static size_t    fts_maxarglen (char * const *) internal_function;
 146 static void      fts_padjust (FTS *, FTSENT *) internal_function;
 147 static bool      fts_palloc (FTS *, size_t) internal_function;
 148 static FTSENT   *fts_sort (FTS *, FTSENT *, size_t) internal_function;
 149 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
 150 static int      fts_safe_changedir (FTS *, FTSENT *, int, const char *)
 151      internal_function;
 152
 153 #if _LGPL_PACKAGE
 154 static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
 155 static void leave_dir (FTS *fts, FTSENT *ent) {}
 156 static bool setup_dir (FTS *fts) { return true; }
 157 static void free_dir (FTS *fts) {}
 158 #else
 159 # include "fts-cycle.c"
 160 #endif
 161
 162 #ifndef MAX
 163 # define MAX(a,b) ((a) > (b) ? (a) : (b))
 164 #endif
 165
 166 #ifndef SIZE_MAX
 167 # define SIZE_MAX ((size_t) -1)
 168 #endif
 169
 170 #ifndef O_DIRECTORY
 171 # define O_DIRECTORY 0
 172 #endif
 173
 174 #define ISDOT(a)        (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
 175 #define STREQ(a, b)     (strcmp ((a), (b)) == 0)
 176
 177 #define CLR(opt)        (sp->fts_options &= ~(opt))
 178 #define ISSET(opt)      (sp->fts_options & (opt))
 179 #define SET(opt)        (sp->fts_options |= (opt))
 180
 181 /* FIXME: make this a function */
 182 #define RESTORE_INITIAL_CWD(sp)                 \
 183   (fd_ring_clear (&((sp)->fts_fd_ring)),        \
 184    FCHDIR ((sp), (ISSET (FTS_CWDFD) ? AT_FDCWD : (sp)->fts_rfd)))
 185
 186 /* FIXME: FTS_NOCHDIR is now misnamed.
 187    Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
 188 #define FCHDIR(sp, fd)                                  \
 189   (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD)             \
 190                            ? (cwd_advance_fd ((sp), (fd), true), 0) \
 191                            : fchdir (fd)))
 192
 193
 194 /* fts_build flags */
 195 /* FIXME: make this an enum */
 196 #define BCHILD          1               /* fts_children */
 197 #define BNAMES          2               /* fts_children, names only */
 198 #define BREAD           3               /* fts_read */
 199
 200 #if FTS_DEBUG
 201 # include <inttypes.h>
 202 # include <stdint.h>
 203 # include <stdio.h>
 204 # include "getcwdat.h"
 205 bool fts_debug = false;
 206 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
 207 #else
 208 # define Dprintf(x)
 209 # define fd_ring_check(x)
 210 # define fd_ring_print(a, b, c)
 211 #endif
 212
 213 #define LEAVE_DIR(Fts, Ent, Tag)                                \
 214   do                                                            \
 215     {                                                           \
 216       Dprintf (("  %s-leaving: %s\n", Tag, (Ent)->fts_path));   \
 217       leave_dir (Fts, Ent);                                     \
 218       fd_ring_check (Fts);                                      \
 219     }                                                           \
 220   while (false)
 221
 222 static void
 223 fd_ring_clear (I_ring *fd_ring)
 224 {
 225   while ( ! i_ring_empty (fd_ring))
 226     {
 227       int fd = i_ring_pop (fd_ring);
 228       if (0 <= fd)
 229         close (fd);
 230     }
 231 }
 232
 233 /* Overload the fts_statp->st_size member (otherwise unused, when
 234    fts_info is FTS_NSOK) to indicate whether fts_read should stat
 235    this entry or not.  */
 236 static void
 237 fts_set_stat_required (FTSENT *p, bool required)
 238 {
 239   if (p->fts_info != FTS_NSOK)
 240     abort ();
 241   p->fts_statp->st_size = (required
 242                            ? FTS_STAT_REQUIRED
 243                            : FTS_NO_STAT_REQUIRED);
 244 }
 245
 246 /* file-descriptor-relative opendir.  */
 247 /* FIXME: if others need this function, move it into lib/openat.c */
 248 static inline DIR *
 249 internal_function
 250 opendirat (int fd, char const *dir)
 251 {
 252   int new_fd = openat (fd, dir, O_RDONLY);
 253   DIR *dirp;
 254
 255   if (new_fd < 0)
 256     return NULL;
 257   dirp = fdopendir (new_fd);
 258   if (dirp == NULL)
 259     {
 260       int saved_errno = errno;
 261       close (new_fd);
 262       errno = saved_errno;
 263     }
 264   return dirp;
 265 }
 266
 267 /* Virtual fchdir.  Advance SP's working directory file descriptor,
 268    SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
 269    CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
 270    open on sp->fts_cwd_fd; i.e., to move the working directory one level
 271    down.  */
 272 static void
 273 internal_function
 274 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
 275 {
 276   int old = sp->fts_cwd_fd;
 277   if (old == fd && old != AT_FDCWD)
 278     abort ();
 279
 280   if (chdir_down_one)
 281     {
 282       /* Push "old" onto the ring.
 283          If the displaced file descriptor is non-negative, close it.  */
 284       int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);
 285       fd_ring_print (sp, stderr, "post-push");
 286       if (0 <= prev_fd_in_slot)
 287         close (prev_fd_in_slot); /* ignore any close failure */
 288     }
 289   else if ( ! ISSET (FTS_NOCHDIR))
 290     {
 291       if (0 <= old)
 292         close (old); /* ignore any close failure */
 293     }
 294
 295   sp->fts_cwd_fd = fd;
 296 }
 297
 298 /* Open the directory DIR if possible, and return a file
 299    descriptor.  Return -1 and set errno on failure.  It doesn't matter
 300    whether the file descriptor has read or write access.  */
 301
 302 static inline int
 303 internal_function
 304 diropen (FTS const *sp, char const *dir)
 305 {
 306   int open_flags = (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
 307                     | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0));
 308
 309   return (ISSET (FTS_CWDFD)
 310           ? openat (sp->fts_cwd_fd, dir, open_flags)
 311           : open (dir, open_flags));
 312 }
 313
 314 FTS *
 315 fts_open (char * const *argv,
 316           register int options,
 317           int (*compar) (FTSENT const **, FTSENT const **))
 318 {
 319         register FTS *sp;
 320         register FTSENT *p, *root;
 321         register size_t nitems;
 322         FTSENT *parent = NULL;
 323         FTSENT *tmp = NULL;     /* pacify gcc */
 324         size_t len;
 325         bool defer_stat;
 326
 327         /* Options check. */
 328         if (options & ~FTS_OPTIONMASK) {
 329                 __set_errno (EINVAL);
 330                 return (NULL);
 331         }
 332         if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {
 333                 __set_errno (EINVAL);
 334                 return (NULL);
 335         }
 336         if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {
 337                 __set_errno (EINVAL);
 338                 return (NULL);
 339         }
 340
 341         /* Allocate/initialize the stream */
 342         if ((sp = malloc(sizeof(FTS))) == NULL)
 343                 return (NULL);
 344         memset(sp, 0, sizeof(FTS));
 345         sp->fts_compar = compar;
 346         sp->fts_options = options;
 347
 348         /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
 349         if (ISSET(FTS_LOGICAL)) {
 350                 SET(FTS_NOCHDIR);
 351                 CLR(FTS_CWDFD);
 352         }
 353
 354         /* Initialize fts_cwd_fd.  */
 355         sp->fts_cwd_fd = AT_FDCWD;
 356         if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)
 357           {
 358             /* While it isn't technically necessary to open "." this
 359                early, doing it here saves us the trouble of ensuring
 360                later (where it'd be messier) that "." can in fact
 361                be opened.  If not, revert to FTS_NOCHDIR mode.  */
 362             int fd = open (".", O_RDONLY);
 363             if (fd < 0)
 364               {
 365                 /* Even if `.' is unreadable, don't revert to FTS_NOCHDIR mode
 366                    on systems like Linux+PROC_FS, where our openat emulation
 367                    is good enough.  Note: on a system that emulates
 368                    openat via /proc, this technique can still fail, but
 369                    only in extreme conditions, e.g., when the working
 370                    directory cannot be saved (i.e. save_cwd fails) --
 371                    and that happens on Linux only when "." is unreadable
 372                    and the CWD would be longer than PATH_MAX.
 373                    FIXME: once Linux kernel openat support is well established,
 374                    replace the above open call and this entire if/else block
 375                    with the body of the if-block below.  */
 376                 if ( openat_needs_fchdir ())
 377                   {
 378                     SET(FTS_NOCHDIR);
 379                     CLR(FTS_CWDFD);
 380                   }
 381               }
 382             else
 383               {
 384                 close (fd);
 385               }
 386           }
 387
 388         /*
 389          * Start out with 1K of file name space, and enough, in any case,
 390          * to hold the user's file names.
 391          */
 392 #ifndef MAXPATHLEN
 393 # define MAXPATHLEN 1024
 394 #endif
 395         {
 396           size_t maxarglen = fts_maxarglen(argv);
 397           if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
 398                   goto mem1;
 399         }
 400
 401         /* Allocate/initialize root's parent. */
 402         if (*argv != NULL) {
 403                 if ((parent = fts_alloc(sp, "", 0)) == NULL)
 404                         goto mem2;
 405                 parent->fts_level = FTS_ROOTPARENTLEVEL;
 406           }
 407
 408         /* The classic fts implementation would call fts_stat with
 409            a new entry for each iteration of the loop below.
 410            If the comparison function is not specified or if the
 411            FTS_DEFER_STAT option is in effect, don't stat any entry
 412            in this loop.  This is an attempt to minimize the interval
 413            between the initial stat/lstat/fstatat and the point at which
 414            a directory argument is first opened.  This matters for any
 415            directory command line argument that resides on a file system
 416            without genuine i-nodes.  If you specify FTS_DEFER_STAT along
 417            with a comparison function, that function must not access any
 418            data via the fts_statp pointer.  */
 419         defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));
 420
 421         /* Allocate/initialize root(s). */
 422         for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
 423                 /* Don't allow zero-length file names. */
 424                 if ((len = strlen(*argv)) == 0) {
 425                         __set_errno (ENOENT);
 426                         goto mem3;
 427                 }
 428
 429                 if ((p = fts_alloc(sp, *argv, len)) == NULL)
 430                         goto mem3;
 431                 p->fts_level = FTS_ROOTLEVEL;
 432                 p->fts_parent = parent;
 433                 p->fts_accpath = p->fts_name;
 434                 /* Even when defer_stat is true, be sure to stat the first
 435                    command line argument, since fts_read (at least with
 436                    FTS_XDEV) requires that.  */
 437                 if (defer_stat && root != NULL) {
 438                         p->fts_info = FTS_NSOK;
 439                         fts_set_stat_required(p, true);
 440                 } else {
 441                         p->fts_info = fts_stat(sp, p, false);
 442                 }
 443
 444                 /*
 445                  * If comparison routine supplied, traverse in sorted
 446                  * order; otherwise traverse in the order specified.
 447                  */
 448                 if (compar) {
 449                         p->fts_link = root;
 450                         root = p;
 451                 } else {
 452                         p->fts_link = NULL;
 453                         if (root == NULL)
 454                                 tmp = root = p;
 455                         else {
 456                                 tmp->fts_link = p;
 457                                 tmp = p;
 458                         }
 459                 }
 460         }
 461         if (compar && nitems > 1)
 462                 root = fts_sort(sp, root, nitems);
 463
 464         /*
 465          * Allocate a dummy pointer and make fts_read think that we've just
 466          * finished the node before the root(s); set p->fts_info to FTS_INIT
 467          * so that everything about the "current" node is ignored.
 468          */
 469         if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
 470                 goto mem3;
 471         sp->fts_cur->fts_link = root;
 472         sp->fts_cur->fts_info = FTS_INIT;
 473         if (! setup_dir (sp))
 474                 goto mem3;
 475
 476         /*
 477          * If using chdir(2), grab a file descriptor pointing to dot to ensure
 478          * that we can get back here; this could be avoided for some file names,
 479          * but almost certainly not worth the effort.  Slashes, symbolic links,
 480          * and ".." are all fairly nasty problems.  Note, if we can't get the
 481          * descriptor we run anyway, just more slowly.
 482          */
 483         if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)
 484             && (sp->fts_rfd = diropen (sp, ".")) < 0)
 485                 SET(FTS_NOCHDIR);
 486
 487         i_ring_init (&sp->fts_fd_ring, -1);
 488         return (sp);
 489
 490 mem3:   fts_lfree(root);
 491         free(parent);
 492 mem2:   free(sp->fts_path);
 493 mem1:   free(sp);
 494         return (NULL);
 495 }
 496
 497 static void
 498 internal_function
 499 fts_load (FTS *sp, register FTSENT *p)
 500 {
 501         register size_t len;
 502         register char *cp;
 503
 504         /*
 505          * Load the stream structure for the next traversal.  Since we don't
 506          * actually enter the directory until after the preorder visit, set
 507          * the fts_accpath field specially so the chdir gets done to the right
 508          * place and the user can access the first node.  From fts_open it's
 509          * known that the file name will fit.
 510          */
 511         len = p->fts_pathlen = p->fts_namelen;
 512         memmove(sp->fts_path, p->fts_name, len + 1);
 513         if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
 514                 len = strlen(++cp);
 515                 memmove(p->fts_name, cp, len + 1);
 516                 p->fts_namelen = len;
 517         }
 518         p->fts_accpath = p->fts_path = sp->fts_path;
 519         sp->fts_dev = p->fts_statp->st_dev;
 520 }
 521
 522 int
 523 fts_close (FTS *sp)
 524 {
 525         register FTSENT *freep, *p;
 526         int saved_errno = 0;
 527
 528         /*
 529          * This still works if we haven't read anything -- the dummy structure
 530          * points to the root list, so we step through to the end of the root
 531          * list which has a valid parent pointer.
 532          */
 533         if (sp->fts_cur) {
 534                 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
 535                         freep = p;
 536                         p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
 537                         free(freep);
 538                 }
 539                 free(p);
 540         }
 541
 542         /* Free up child linked list, sort array, file name buffer. */
 543         if (sp->fts_child)
 544                 fts_lfree(sp->fts_child);
 545         free(sp->fts_array);
 546         free(sp->fts_path);
 547
 548         if (ISSET(FTS_CWDFD))
 549           {
 550             if (0 <= sp->fts_cwd_fd)
 551               close (sp->fts_cwd_fd);
 552           }
 553         else if (!ISSET(FTS_NOCHDIR))
 554           {
 555             /* Return to original directory, save errno if necessary. */
 556             if (fchdir(sp->fts_rfd))
 557               saved_errno = errno;
 558             close(sp->fts_rfd);
 559           }
 560
 561         fd_ring_clear (&sp->fts_fd_ring);
 562         free_dir (sp);
 563
 564         /* Free up the stream pointer. */
 565         free(sp);
 566
 567         /* Set errno and return. */
 568         if (saved_errno) {
 569                 __set_errno (saved_errno);
 570                 return (-1);
 571         }
 572
 573         return (0);
 574 }
 575
 576 /*
 577  * Special case of "/" at the end of the file name so that slashes aren't
 578  * appended which would cause file names to be written as "....//foo".
 579  */
 580 #define NAPPEND(p)                                                      \
 581         (p->fts_path[p->fts_pathlen - 1] == '/'                         \
 582             ? p->fts_pathlen - 1 : p->fts_pathlen)
 583
 584 FTSENT *
 585 fts_read (register FTS *sp)
 586 {
 587         register FTSENT *p, *tmp;
 588         register unsigned short int instr;
 589         register char *t;
 590
 591         /* If finished or unrecoverable error, return NULL. */
 592         if (sp->fts_cur == NULL || ISSET(FTS_STOP))
 593                 return (NULL);
 594
 595         /* Set current node pointer. */
 596         p = sp->fts_cur;
 597
 598         /* Save and zero out user instructions. */
 599         instr = p->fts_instr;
 600         p->fts_instr = FTS_NOINSTR;
 601
 602         /* Any type of file may be re-visited; re-stat and re-turn. */
 603         if (instr == FTS_AGAIN) {
 604                 p->fts_info = fts_stat(sp, p, false);
 605                 return (p);
 606         }
 607         Dprintf (("fts_read: p=%s\n",
 608                   p->fts_info == FTS_INIT ? "" : p->fts_path));
 609
 610         /*
 611          * Following a symlink -- SLNONE test allows application to see
 612          * SLNONE and recover.  If indirecting through a symlink, have
 613          * keep a pointer to current location.  If unable to get that
 614          * pointer, follow fails.
 615          */
 616         if (instr == FTS_FOLLOW &&
 617             (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
 618                 p->fts_info = fts_stat(sp, p, true);
 619                 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 620                         if ((p->fts_symfd = diropen (sp, ".")) < 0) {
 621                                 p->fts_errno = errno;
 622                                 p->fts_info = FTS_ERR;
 623                         } else
 624                                 p->fts_flags |= FTS_SYMFOLLOW;
 625                 }
 626                 goto check_for_dir;
 627         }
 628
 629         /* Directory in pre-order. */
 630         if (p->fts_info == FTS_D) {
 631                 /* If skipped or crossed mount point, do post-order visit. */
 632                 if (instr == FTS_SKIP ||
 633                     (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
 634                         if (p->fts_flags & FTS_SYMFOLLOW)
 635                                 (void)close(p->fts_symfd);
 636                         if (sp->fts_child) {
 637                                 fts_lfree(sp->fts_child);
 638                                 sp->fts_child = NULL;
 639                         }
 640                         p->fts_info = FTS_DP;
 641                         LEAVE_DIR (sp, p, "1");
 642                         return (p);
 643                 }
 644
 645                 /* Rebuild if only read the names and now traversing. */
 646                 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
 647                         CLR(FTS_NAMEONLY);
 648                         fts_lfree(sp->fts_child);
 649                         sp->fts_child = NULL;
 650                 }
 651
 652                 /*
 653                  * Cd to the subdirectory.
 654                  *
 655                  * If have already read and now fail to chdir, whack the list
 656                  * to make the names come out right, and set the parent errno
 657                  * so the application will eventually get an error condition.
 658                  * Set the FTS_DONTCHDIR flag so that when we logically change
 659                  * directories back to the parent we don't do a chdir.
 660                  *
 661                  * If haven't read do so.  If the read fails, fts_build sets
 662                  * FTS_STOP or the fts_info field of the node.
 663                  */
 664                 if (sp->fts_child != NULL) {
 665                         if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
 666                                 p->fts_errno = errno;
 667                                 p->fts_flags |= FTS_DONTCHDIR;
 668                                 for (p = sp->fts_child; p != NULL;
 669                                      p = p->fts_link)
 670                                         p->fts_accpath =
 671                                             p->fts_parent->fts_accpath;
 672                         }
 673                 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
 674                         if (ISSET(FTS_STOP))
 675                                 return (NULL);
 676                         /* If fts_build's call to fts_safe_changedir failed
 677                            because it was not able to fchdir into a
 678                            subdirectory, tell the caller.  */
 679                         if (p->fts_errno)
 680                                 p->fts_info = FTS_ERR;
 681                         LEAVE_DIR (sp, p, "2");
 682                         return (p);
 683                 }
 684                 p = sp->fts_child;
 685                 sp->fts_child = NULL;
 686                 goto name;
 687         }
 688
 689         /* Move to the next node on this level. */
 690 next:   tmp = p;
 691         if ((p = p->fts_link) != NULL) {
 692                 free(tmp);
 693
 694                 /*
 695                  * If reached the top, return to the original directory (or
 696                  * the root of the tree), and load the file names for the next
 697                  * root.
 698                  */
 699                 if (p->fts_level == FTS_ROOTLEVEL) {
 700                         if (RESTORE_INITIAL_CWD(sp)) {
 701                                 SET(FTS_STOP);
 702                                 sp->fts_cur = p;
 703                                 return (NULL);
 704                         }
 705                         fts_load(sp, p);
 706                         goto check_for_dir;
 707                 }
 708
 709                 /*
 710                  * User may have called fts_set on the node.  If skipped,
 711                  * ignore.  If followed, get a file descriptor so we can
 712                  * get back if necessary.
 713                  */
 714                 if (p->fts_instr == FTS_SKIP)
 715                         goto next;
 716                 if (p->fts_instr == FTS_FOLLOW) {
 717                         p->fts_info = fts_stat(sp, p, true);
 718                         if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 719                                 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
 720                                         p->fts_errno = errno;
 721                                         p->fts_info = FTS_ERR;
 722                                 } else
 723                                         p->fts_flags |= FTS_SYMFOLLOW;
 724                         }
 725                         p->fts_instr = FTS_NOINSTR;
 726                 }
 727
 728 name:           t = sp->fts_path + NAPPEND(p->fts_parent);
 729                 *t++ = '/';
 730                 memmove(t, p->fts_name, p->fts_namelen + 1);
 731 check_for_dir:
 732                 if (p->fts_info == FTS_NSOK)
 733                   {
 734                     enum Fts_stat need_stat = p->fts_statp->st_size;
 735                     switch (need_stat)
 736                       {
 737                       case FTS_STAT_REQUIRED:
 738                         p->fts_info = fts_stat(sp, p, false);
 739                         break;
 740                       case FTS_NO_STAT_REQUIRED:
 741                         break;
 742                       default:
 743                         abort ();
 744                       }
 745                   }
 746                 sp->fts_cur = p;
 747                 if (p->fts_info == FTS_D)
 748                   {
 749                     Dprintf (("  entering: %s\n", p->fts_path));
 750                     if (! enter_dir (sp, p))
 751                       {
 752                         __set_errno (ENOMEM);
 753                         return NULL;
 754                       }
 755                   }
 756                 return p;
 757         }
 758
 759         /* Move up to the parent node. */
 760         p = tmp->fts_parent;
 761         free(tmp);
 762
 763         if (p->fts_level == FTS_ROOTPARENTLEVEL) {
 764                 /*
 765                  * Done; free everything up and set errno to 0 so the user
 766                  * can distinguish between error and EOF.
 767                  */
 768                 free(p);
 769                 __set_errno (0);
 770                 return (sp->fts_cur = NULL);
 771         }
 772
 773         if (p->fts_info == FTS_NSOK)
 774           abort ();
 775
 776         /* NUL terminate the file name.  */
 777         sp->fts_path[p->fts_pathlen] = '\0';
 778
 779         /*
 780          * Return to the parent directory.  If at a root node, restore
 781          * the initial working directory.  If we came through a symlink,
 782          * go back through the file descriptor.  Otherwise, move up
 783          * one level, via "..".
 784          */
 785         if (p->fts_level == FTS_ROOTLEVEL) {
 786                 if (RESTORE_INITIAL_CWD(sp)) {
 787                         p->fts_errno = errno;
 788                         SET(FTS_STOP);
 789                 }
 790         } else if (p->fts_flags & FTS_SYMFOLLOW) {
 791                 if (FCHDIR(sp, p->fts_symfd)) {
 792                         int saved_errno = errno;
 793                         (void)close(p->fts_symfd);
 794                         __set_errno (saved_errno);
 795                         p->fts_errno = errno;
 796                         SET(FTS_STOP);
 797                 }
 798                 (void)close(p->fts_symfd);
 799         } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
 800                    fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
 801                 p->fts_errno = errno;
 802                 SET(FTS_STOP);
 803         }
 804         p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
 805         if (p->fts_errno == 0)
 806                 LEAVE_DIR (sp, p, "3");
 807         sp->fts_cur = p;
 808         return ISSET(FTS_STOP) ? NULL : p;
 809 }
 810
 811 /*
 812  * Fts_set takes the stream as an argument although it's not used in this
 813  * implementation; it would be necessary if anyone wanted to add global
 814  * semantics to fts using fts_set.  An error return is allowed for similar
 815  * reasons.
 816  */
 817 /* ARGSUSED */
 818 int
 819 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
 820 {
 821         if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
 822             instr != FTS_NOINSTR && instr != FTS_SKIP) {
 823                 __set_errno (EINVAL);
 824                 return (1);
 825         }
 826         p->fts_instr = instr;
 827         return (0);
 828 }
 829
 830 FTSENT *
 831 fts_children (register FTS *sp, int instr)
 832 {
 833         register FTSENT *p;
 834         int fd;
 835
 836         if (instr != 0 && instr != FTS_NAMEONLY) {
 837                 __set_errno (EINVAL);
 838                 return (NULL);
 839         }
 840
 841         /* Set current node pointer. */
 842         p = sp->fts_cur;
 843
 844         /*
 845          * Errno set to 0 so user can distinguish empty directory from
 846          * an error.
 847          */
 848         __set_errno (0);
 849
 850         /* Fatal errors stop here. */
 851         if (ISSET(FTS_STOP))
 852                 return (NULL);
 853
 854         /* Return logical hierarchy of user's arguments. */
 855         if (p->fts_info == FTS_INIT)
 856                 return (p->fts_link);
 857
 858         /*
 859          * If not a directory being visited in pre-order, stop here.  Could
 860          * allow FTS_DNR, assuming the user has fixed the problem, but the
 861          * same effect is available with FTS_AGAIN.
 862          */
 863         if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
 864                 return (NULL);
 865
 866         /* Free up any previous child list. */
 867         if (sp->fts_child != NULL)
 868                 fts_lfree(sp->fts_child);
 869
 870         if (instr == FTS_NAMEONLY) {
 871                 SET(FTS_NAMEONLY);
 872                 instr = BNAMES;
 873         } else
 874                 instr = BCHILD;
 875
 876         /*
 877          * If using chdir on a relative file name and called BEFORE fts_read
 878          * does its chdir to the root of a traversal, we can lose -- we need to
 879          * chdir into the subdirectory, and we don't know where the current
 880          * directory is, so we can't get back so that the upcoming chdir by
 881          * fts_read will work.
 882          */
 883         if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
 884             ISSET(FTS_NOCHDIR))
 885                 return (sp->fts_child = fts_build(sp, instr));
 886
 887         if ((fd = diropen (sp, ".")) < 0)
 888                 return (sp->fts_child = NULL);
 889         sp->fts_child = fts_build(sp, instr);
 890         if (ISSET(FTS_CWDFD))
 891           {
 892             cwd_advance_fd (sp, fd, true);
 893           }
 894         else
 895           {
 896             if (fchdir(fd))
 897               {
 898                 int saved_errno = errno;
 899                 close (fd);
 900                 __set_errno (saved_errno);
 901                 return NULL;
 902               }
 903             close (fd);
 904           }
 905         return (sp->fts_child);
 906 }
 907
 908 /*
 909  * This is the tricky part -- do not casually change *anything* in here.  The
 910  * idea is to build the linked list of entries that are used by fts_children
 911  * and fts_read.  There are lots of special cases.
 912  *
 913  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
 914  * set and it's a physical walk (so that symbolic links can't be directories),
 915  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
 916  * of the file is in the directory entry.  Otherwise, we assume that the number
 917  * of subdirectories in a node is equal to the number of links to the parent.
 918  * The former skips all stat calls.  The latter skips stat calls in any leaf
 919  * directories and for any files after the subdirectories in the directory have
 920  * been found, cutting the stat calls by about 2/3.
 921  */
 922 static FTSENT *
 923 internal_function
 924 fts_build (register FTS *sp, int type)
 925 {
 926         register struct dirent *dp;
 927         register FTSENT *p, *head;
 928         register size_t nitems;
 929         FTSENT *cur, *tail;
 930         DIR *dirp;
 931         void *oldaddr;
 932         int saved_errno;
 933         bool descend;
 934         bool doadjust;
 935         ptrdiff_t level;
 936         nlink_t nlinks;
 937         bool nostat;
 938         size_t len, maxlen, new_len;
 939         char *cp;
 940
 941         /* Set current node pointer. */
 942         cur = sp->fts_cur;
 943
 944         /*
 945          * Open the directory for reading.  If this fails, we're done.
 946          * If being called from fts_read, set the fts_info field.
 947          */
 948 #if defined FTS_WHITEOUT && 0
 949         if (ISSET(FTS_WHITEOUT))
 950                 oflag = DTF_NODUP|DTF_REWIND;
 951         else
 952                 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
 953 #else
 954 # define __opendir2(file, flag) \
 955         ( ! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
 956           ? opendirat(sp->fts_cwd_fd, file)        \
 957           : opendir(file))
 958 #endif
 959        if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
 960                 if (type == BREAD) {
 961                         cur->fts_info = FTS_DNR;
 962                         cur->fts_errno = errno;
 963                 }
 964                 return (NULL);
 965         }
 966        /* Rather than calling fts_stat for each and every entry encountered
 967           in the readdir loop (below), stat each directory only right after
 968           opening it.  */
 969        if (cur->fts_info == FTS_NSOK)
 970          cur->fts_info = fts_stat(sp, cur, false);
 971
 972         /*
 973          * Nlinks is the number of possible entries of type directory in the
 974          * directory if we're cheating on stat calls, 0 if we're not doing
 975          * any stat calls at all, (nlink_t) -1 if we're statting everything.
 976          */
 977         if (type == BNAMES) {
 978                 nlinks = 0;
 979                 /* Be quiet about nostat, GCC. */
 980                 nostat = false;
 981         } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
 982                 nlinks = (cur->fts_statp->st_nlink
 983                           - (ISSET(FTS_SEEDOT) ? 0 : 2));
 984                 nostat = true;
 985         } else {
 986                 nlinks = -1;
 987                 nostat = false;
 988         }
 989
 990         /*
 991          * If we're going to need to stat anything or we want to descend
 992          * and stay in the directory, chdir.  If this fails we keep going,
 993          * but set a flag so we don't chdir after the post-order visit.
 994          * We won't be able to stat anything, but we can still return the
 995          * names themselves.  Note, that since fts_read won't be able to
 996          * chdir into the directory, it will have to return different file
 997          * names than before, i.e. "a/b" instead of "b".  Since the node
 998          * has already been visited in pre-order, have to wait until the
 999          * post-order visit to return the error.  There is a special case
1000          * here, if there was nothing to stat then it's not an error to
1001          * not be able to stat.  This is all fairly nasty.  If a program
1002          * needed sorted entries or stat information, they had better be
1003          * checking FTS_NS on the returned nodes.
1004          */
1005         if (nlinks || type == BREAD) {
1006                 int dir_fd = dirfd(dirp);
1007                 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1008                   dir_fd = dup (dir_fd);
1009                 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
1010                         if (nlinks && type == BREAD)
1011                                 cur->fts_errno = errno;
1012                         cur->fts_flags |= FTS_DONTCHDIR;
1013                         descend = false;
1014                         closedir(dirp);
1015                         if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1016                                 close (dir_fd);
1017                         dirp = NULL;
1018                 } else
1019                         descend = true;
1020         } else
1021                 descend = false;
1022
1023         /*
1024          * Figure out the max file name length that can be stored in the
1025          * current buffer -- the inner loop allocates more space as necessary.
1026          * We really wouldn't have to do the maxlen calculations here, we
1027          * could do them in fts_read before returning the name, but it's a
1028          * lot easier here since the length is part of the dirent structure.
1029          *
1030          * If not changing directories set a pointer so that can just append
1031          * each new component into the file name.
1032          */
1033         len = NAPPEND(cur);
1034         if (ISSET(FTS_NOCHDIR)) {
1035                 cp = sp->fts_path + len;
1036                 *cp++ = '/';
1037         } else {
1038                 /* GCC, you're too verbose. */
1039                 cp = NULL;
1040         }
1041         len++;
1042         maxlen = sp->fts_pathlen - len;
1043
1044         level = cur->fts_level + 1;
1045
1046         /* Read the directory, attaching each entry to the `link' pointer. */
1047         doadjust = false;
1048         for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
1049                 bool is_dir;
1050
1051                 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1052                         continue;
1053
1054                 if ((p = fts_alloc (sp, dp->d_name,
1055                                     _D_EXACT_NAMLEN (dp))) == NULL)
1056                         goto mem1;
1057                 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
1058                         /* include space for NUL */
1059                         oldaddr = sp->fts_path;
1060                         if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
1061                                 /*
1062                                  * No more memory.  Save
1063                                  * errno, free up the current structure and the
1064                                  * structures already allocated.
1065                                  */
1066 mem1:                           saved_errno = errno;
1067                                 free(p);
1068                                 fts_lfree(head);
1069                                 closedir(dirp);
1070                                 cur->fts_info = FTS_ERR;
1071                                 SET(FTS_STOP);
1072                                 __set_errno (saved_errno);
1073                                 return (NULL);
1074                         }
1075                         /* Did realloc() change the pointer? */
1076                         if (oldaddr != sp->fts_path) {
1077                                 doadjust = true;
1078                                 if (ISSET(FTS_NOCHDIR))
1079                                         cp = sp->fts_path + len;
1080                         }
1081                         maxlen = sp->fts_pathlen - len;
1082                 }
1083
1084                 new_len = len + _D_EXACT_NAMLEN (dp);
1085                 if (new_len < len) {
1086                         /*
1087                          * In the unlikely even that we would end up
1088                          * with a file name longer than SIZE_MAX, free up
1089                          * the current structure and the structures already
1090                          * allocated, then error out with ENAMETOOLONG.
1091                          */
1092                         free(p);
1093                         fts_lfree(head);
1094                         closedir(dirp);
1095                         cur->fts_info = FTS_ERR;
1096                         SET(FTS_STOP);
1097                         __set_errno (ENAMETOOLONG);
1098                         return (NULL);
1099                 }
1100                 p->fts_level = level;
1101                 p->fts_parent = sp->fts_cur;
1102                 p->fts_pathlen = new_len;
1103
1104 #if defined FTS_WHITEOUT && 0
1105                 if (dp->d_type == DT_WHT)
1106                         p->fts_flags |= FTS_ISW;
1107 #endif
1108
1109                 /* Build a file name for fts_stat to stat. */
1110                 if (ISSET(FTS_NOCHDIR)) {
1111                         p->fts_accpath = p->fts_path;
1112                         memmove(cp, p->fts_name, p->fts_namelen + 1);
1113                 } else
1114                         p->fts_accpath = p->fts_name;
1115
1116                 if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {
1117                         /* Record what fts_read will have to do with this
1118                            entry. In many cases, it will simply fts_stat it,
1119                            but we can take advantage of any d_type information
1120                            to optimize away the unnecessary stat calls.  I.e.,
1121                            if FTS_NOSTAT is in effect and we're not following
1122                            symlinks (FTS_PHYSICAL) and d_type indicates this
1123                            is *not* a directory, then we won't have to stat it
1124                            at all.  If it *is* a directory, then (currently)
1125                            we stat it regardless, in order to get device and
1126                            inode numbers.  Some day we might optimize that
1127                            away, too, for directories where d_ino is known to
1128                            be valid.  */
1129                         bool skip_stat = (ISSET(FTS_PHYSICAL)
1130                                           && ISSET(FTS_NOSTAT)
1131                                           && DT_IS_KNOWN(dp)
1132                                           && ! DT_MUST_BE(dp, DT_DIR));
1133                         p->fts_info = FTS_NSOK;
1134                         fts_set_stat_required(p, !skip_stat);
1135                         is_dir = (ISSET(FTS_PHYSICAL) && ISSET(FTS_NOSTAT)
1136                                   && DT_MUST_BE(dp, DT_DIR));
1137                 } else {
1138                         p->fts_info = fts_stat(sp, p, false);
1139                         is_dir = (p->fts_info == FTS_D
1140                                   || p->fts_info == FTS_DC
1141                                   || p->fts_info == FTS_DOT);
1142                 }
1143
1144                 /* Decrement link count if applicable. */
1145                 if (nlinks > 0 && is_dir)
1146                         nlinks -= nostat;
1147
1148                 /* We walk in directory order so "ls -f" doesn't get upset. */
1149                 p->fts_link = NULL;
1150                 if (head == NULL)
1151                         head = tail = p;
1152                 else {
1153                         tail->fts_link = p;
1154                         tail = p;
1155                 }
1156                 ++nitems;
1157         }
1158         if (dirp)
1159                 closedir(dirp);
1160
1161         /*
1162          * If realloc() changed the address of the file name, adjust the
1163          * addresses for the rest of the tree and the dir list.
1164          */
1165         if (doadjust)
1166                 fts_padjust(sp, head);
1167
1168         /*
1169          * If not changing directories, reset the file name back to original
1170          * state.
1171          */
1172         if (ISSET(FTS_NOCHDIR)) {
1173                 if (len == sp->fts_pathlen || nitems == 0)
1174                         --cp;
1175                 *cp = '\0';
1176         }
1177
1178         /*
1179          * If descended after called from fts_children or after called from
1180          * fts_read and nothing found, get back.  At the root level we use
1181          * the saved fd; if one of fts_open()'s arguments is a relative name
1182          * to an empty directory, we wind up here with no other way back.  If
1183          * can't get back, we're done.
1184          */
1185         if (descend && (type == BCHILD || !nitems) &&
1186             (cur->fts_level == FTS_ROOTLEVEL
1187              ? RESTORE_INITIAL_CWD(sp)
1188              : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1189                 cur->fts_info = FTS_ERR;
1190                 SET(FTS_STOP);
1191                 fts_lfree(head);
1192                 return (NULL);
1193         }
1194
1195         /* If didn't find anything, return NULL. */
1196         if (!nitems) {
1197                 if (type == BREAD)
1198                         cur->fts_info = FTS_DP;
1199                 fts_lfree(head);
1200                 return (NULL);
1201         }
1202
1203         /* Sort the entries. */
1204         if (sp->fts_compar && nitems > 1)
1205                 head = fts_sort(sp, head, nitems);
1206         return (head);
1207 }
1208
1209 #if FTS_DEBUG
1210
1211 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1212    current hierarchy.  There should be a directory with dev/inode
1213    matching those of AD.  If not, print a lot of diagnostics.  */
1214 static void
1215 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1216 {
1217   FTSENT const *ent;
1218   for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1219     {
1220       if (ad->ino == ent->fts_statp->st_ino
1221           && ad->dev == ent->fts_statp->st_dev)
1222         return;
1223     }
1224   printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1225   printf ("active dirs:\n");
1226   for (ent = e_curr;
1227        ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1228     printf ("  %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1229             ad->fts_ent->fts_accpath,
1230             (uintmax_t) ad->dev,
1231             (uintmax_t) ad->ino,
1232             ent->fts_accpath,
1233             (uintmax_t) ent->fts_statp->st_dev,
1234             (uintmax_t) ent->fts_statp->st_ino);
1235 }
1236
1237 void
1238 fts_cross_check (FTS const *sp)
1239 {
1240   FTSENT const *ent = sp->fts_cur;
1241   FTSENT const *t;
1242   if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1243     return;
1244
1245   Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1246   /* Make sure every parent dir is in the tree.  */
1247   for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1248     {
1249       struct Active_dir ad;
1250       ad.ino = t->fts_statp->st_ino;
1251       ad.dev = t->fts_statp->st_dev;
1252       if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1253         printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1254     }
1255
1256   /* Make sure every dir in the tree is an active dir.
1257      But ENT is not necessarily a directory.  If so, just skip this part. */
1258   if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1259       && (ent->fts_info == FTS_DP
1260           || ent->fts_info == FTS_D))
1261     {
1262       struct Active_dir *ad;
1263       for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1264            ad = hash_get_next (sp->fts_cycle.ht, ad))
1265         {
1266           find_matching_ancestor (ent, ad);
1267         }
1268     }
1269 }
1270
1271 static bool
1272 same_fd (int fd1, int fd2)
1273 {
1274   struct stat sb1, sb2;
1275   return (fstat (fd1, &sb1) == 0
1276           && fstat (fd2, &sb2) == 0
1277           && SAME_INODE (sb1, sb2));
1278 }
1279
1280 static void
1281 fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
1282 {
1283   I_ring const *fd_ring = &sp->fts_fd_ring;
1284   unsigned int i = fd_ring->fts_front;
1285   char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0);
1286   fprintf (stream, "=== %s ========== %s\n", msg, cwd);
1287   free (cwd);
1288   if (i_ring_empty (fd_ring))
1289     return;
1290
1291   while (true)
1292     {
1293       int fd = fd_ring->fts_fd_ring[i];
1294       if (fd < 0)
1295         fprintf (stream, "%d: %d:\n", i, fd);
1296       else
1297         {
1298           char *wd = getcwdat (fd, NULL, 0);
1299           fprintf (stream, "%d: %d: %s\n", i, fd, wd);
1300           free (wd);
1301         }
1302       if (i == fd_ring->fts_back)
1303         break;
1304       i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
1305     }
1306 }
1307
1308 /* Ensure that each file descriptor on the fd_ring matches a
1309    parent, grandparent, etc. of the current working directory.  */
1310 static void
1311 fd_ring_check (FTS const *sp)
1312 {
1313   if (!fts_debug)
1314     return;
1315
1316   /* Make a writable copy.  */
1317   I_ring fd_w = sp->fts_fd_ring;
1318
1319   int cwd_fd = sp->fts_cwd_fd;
1320   cwd_fd = dup (cwd_fd);
1321   char *dot = getcwdat (cwd_fd, NULL, 0);
1322   error (0, 0, "===== check ===== cwd: %s", dot);
1323   free (dot);
1324   while ( ! i_ring_empty (&fd_w))
1325     {
1326       int fd = i_ring_pop (&fd_w);
1327       if (0 <= fd)
1328         {
1329           int parent_fd = openat (cwd_fd, "..", O_RDONLY);
1330           if (parent_fd < 0)
1331             {
1332               // Warn?
1333               break;
1334             }
1335           if (!same_fd (fd, parent_fd))
1336             {
1337               char *cwd = getcwdat (fd, NULL, 0);
1338               error (0, errno, "ring  : %s", cwd);
1339               char *c2 = getcwdat (parent_fd, NULL, 0);
1340               error (0, errno, "parent: %s", c2);
1341               free (cwd);
1342               free (c2);
1343               abort ();
1344             }
1345           close (cwd_fd);
1346           cwd_fd = parent_fd;
1347         }
1348     }
1349   close (cwd_fd);
1350 }
1351 #endif
1352
1353 static unsigned short int
1354 internal_function
1355 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1356 {
1357         struct stat *sbp = p->fts_statp;
1358         int saved_errno;
1359
1360         if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
1361                 follow = true;
1362
1363 #if defined FTS_WHITEOUT && 0
1364         /* check for whiteout */
1365         if (p->fts_flags & FTS_ISW) {
1366                 memset(sbp, '\0', sizeof (*sbp));
1367                 sbp->st_mode = S_IFWHT;
1368                 return (FTS_W);
1369        }
1370 #endif
1371
1372         /*
1373          * If doing a logical walk, or application requested FTS_FOLLOW, do
1374          * a stat(2).  If that fails, check for a non-existent symlink.  If
1375          * fail, set the errno from the stat call.
1376          */
1377         if (ISSET(FTS_LOGICAL) || follow) {
1378                 if (stat(p->fts_accpath, sbp)) {
1379                         saved_errno = errno;
1380                         if (errno == ENOENT
1381                             && lstat(p->fts_accpath, sbp) == 0) {
1382                                 __set_errno (0);
1383                                 return (FTS_SLNONE);
1384                         }
1385                         p->fts_errno = saved_errno;
1386                         goto err;
1387                 }
1388         } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp,
1389                            AT_SYMLINK_NOFOLLOW)) {
1390                 p->fts_errno = errno;
1391 err:            memset(sbp, 0, sizeof(struct stat));
1392                 return (FTS_NS);
1393         }
1394
1395         if (S_ISDIR(sbp->st_mode)) {
1396                 if (ISDOT(p->fts_name)) {
1397                         /* Command-line "." and ".." are real directories. */
1398                         return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
1399                 }
1400
1401 #if _LGPL_PACKAGE
1402                 {
1403                   /*
1404                    * Cycle detection is done by brute force when the directory
1405                    * is first encountered.  If the tree gets deep enough or the
1406                    * number of symbolic links to directories is high enough,
1407                    * something faster might be worthwhile.
1408                    */
1409                   FTSENT *t;
1410
1411                   for (t = p->fts_parent;
1412                        t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1413                     if (sbp->st_ino == t->fts_statp->st_ino
1414                         && sbp->st_dev == t->fts_statp->st_dev)
1415                       {
1416                         p->fts_cycle = t;
1417                         return (FTS_DC);
1418                       }
1419                 }
1420 #endif
1421
1422                 return (FTS_D);
1423         }
1424         if (S_ISLNK(sbp->st_mode))
1425                 return (FTS_SL);
1426         if (S_ISREG(sbp->st_mode))
1427                 return (FTS_F);
1428         return (FTS_DEFAULT);
1429 }
1430
1431 static int
1432 fts_compar (void const *a, void const *b)
1433 {
1434   /* Convert A and B to the correct types, to pacify the compiler, and
1435      for portability to bizarre hosts where "void const *" and "FTSENT
1436      const **" differ in runtime representation.  The comparison
1437      function cannot modify *a and *b, but there is no compile-time
1438      check for this.  */
1439   FTSENT const **pa = (FTSENT const **) a;
1440   FTSENT const **pb = (FTSENT const **) b;
1441   return pa[0]->fts_fts->fts_compar (pa, pb);
1442 }
1443
1444 static FTSENT *
1445 internal_function
1446 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1447 {
1448         register FTSENT **ap, *p;
1449
1450         /* On most modern hosts, void * and FTSENT ** have the same
1451            run-time representation, and one can convert sp->fts_compar to
1452            the type qsort expects without problem.  Use the heuristic that
1453            this is OK if the two pointer types are the same size, and if
1454            converting FTSENT ** to long int is the same as converting
1455            FTSENT ** to void * and then to long int.  This heuristic isn't
1456            valid in general but we don't know of any counterexamples.  */
1457         FTSENT *dummy;
1458         int (*compare) (void const *, void const *) =
1459           ((sizeof &dummy == sizeof (void *)
1460             && (long int) &dummy == (long int) (void *) &dummy)
1461            ? (int (*) (void const *, void const *)) sp->fts_compar
1462            : fts_compar);
1463
1464         /*
1465          * Construct an array of pointers to the structures and call qsort(3).
1466          * Reassemble the array in the order returned by qsort.  If unable to
1467          * sort for memory reasons, return the directory entries in their
1468          * current order.  Allocate enough space for the current needs plus
1469          * 40 so don't realloc one entry at a time.
1470          */
1471         if (nitems > sp->fts_nitems) {
1472                 struct _ftsent **a;
1473
1474                 sp->fts_nitems = nitems + 40;
1475                 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1476                     || ! (a = realloc (sp->fts_array,
1477                                        sp->fts_nitems * sizeof *a))) {
1478                         free(sp->fts_array);
1479                         sp->fts_array = NULL;
1480                         sp->fts_nitems = 0;
1481                         return (head);
1482                 }
1483                 sp->fts_array = a;
1484         }
1485         for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1486                 *ap++ = p;
1487         qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1488         for (head = *(ap = sp->fts_array); --nitems; ++ap)
1489                 ap[0]->fts_link = ap[1];
1490         ap[0]->fts_link = NULL;
1491         return (head);
1492 }
1493
1494 static FTSENT *
1495 internal_function
1496 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1497 {
1498         register FTSENT *p;
1499         size_t len;
1500
1501         /*
1502          * The file name is a variable length array.  Allocate the FTSENT
1503          * structure and the file name in one chunk.
1504          */
1505         len = sizeof(FTSENT) + namelen;
1506         if ((p = malloc(len)) == NULL)
1507                 return (NULL);
1508
1509         /* Copy the name and guarantee NUL termination. */
1510         memmove(p->fts_name, name, namelen);
1511         p->fts_name[namelen] = '\0';
1512
1513         p->fts_namelen = namelen;
1514         p->fts_fts = sp;
1515         p->fts_path = sp->fts_path;
1516         p->fts_errno = 0;
1517         p->fts_flags = 0;
1518         p->fts_instr = FTS_NOINSTR;
1519         p->fts_number = 0;
1520         p->fts_pointer = NULL;
1521         return (p);
1522 }
1523
1524 static void
1525 internal_function
1526 fts_lfree (register FTSENT *head)
1527 {
1528         register FTSENT *p;
1529
1530         /* Free a linked list of structures. */
1531         while ((p = head)) {
1532                 head = head->fts_link;
1533                 free(p);
1534         }
1535 }
1536
1537 /*
1538  * Allow essentially unlimited file name lengths; find, rm, ls should
1539  * all work on any tree.  Most systems will allow creation of file
1540  * names much longer than MAXPATHLEN, even though the kernel won't
1541  * resolve them.  Add the size (not just what's needed) plus 256 bytes
1542  * so don't realloc the file name 2 bytes at a time.
1543  */
1544 static bool
1545 internal_function
1546 fts_palloc (FTS *sp, size_t more)
1547 {
1548         char *p;
1549         size_t new_len = sp->fts_pathlen + more + 256;
1550
1551         /*
1552          * See if fts_pathlen would overflow.
1553          */
1554         if (new_len < sp->fts_pathlen) {
1555                 free(sp->fts_path);
1556                 sp->fts_path = NULL;
1557                 __set_errno (ENAMETOOLONG);
1558                 return false;
1559         }
1560         sp->fts_pathlen = new_len;
1561         p = realloc(sp->fts_path, sp->fts_pathlen);
1562         if (p == NULL) {
1563                 free(sp->fts_path);
1564                 sp->fts_path = NULL;
1565                 return false;
1566         }
1567         sp->fts_path = p;
1568         return true;
1569 }
1570
1571 /*
1572  * When the file name is realloc'd, have to fix all of the pointers in
1573  *  structures already returned.
1574  */
1575 static void
1576 internal_function
1577 fts_padjust (FTS *sp, FTSENT *head)
1578 {
1579         FTSENT *p;
1580         char *addr = sp->fts_path;
1581
1582 #define ADJUST(p) do {                                                  \
1583         if ((p)->fts_accpath != (p)->fts_name) {                        \
1584                 (p)->fts_accpath =                                      \
1585                     (char *)addr + ((p)->fts_accpath - (p)->fts_path);  \
1586         }                                                               \
1587         (p)->fts_path = addr;                                           \
1588 } while (0)
1589         /* Adjust the current set of children. */
1590         for (p = sp->fts_child; p; p = p->fts_link)
1591                 ADJUST(p);
1592
1593         /* Adjust the rest of the tree, including the current level. */
1594         for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1595                 ADJUST(p);
1596                 p = p->fts_link ? p->fts_link : p->fts_parent;
1597         }
1598 }
1599
1600 static size_t
1601 internal_function
1602 fts_maxarglen (char * const *argv)
1603 {
1604         size_t len, max;
1605
1606         for (max = 0; *argv; ++argv)
1607                 if ((len = strlen(*argv)) > max)
1608                         max = len;
1609         return (max + 1);
1610 }
1611
1612 /*
1613  * Change to dir specified by fd or file name without getting
1614  * tricked by someone changing the world out from underneath us.
1615  * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1616  * If FD is non-negative, expect it to be used after this function returns,
1617  * and to be closed eventually.  So don't pass e.g., `dirfd(dirp)' and then
1618  * do closedir(dirp), because that would invalidate the saved FD.
1619  * Upon failure, close FD immediately and return nonzero.
1620  */
1621 static int
1622 internal_function
1623 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1624 {
1625         int ret;
1626         bool is_dotdot = dir && STREQ (dir, "..");
1627         int newfd;
1628
1629         /* This clause handles the unusual case in which FTS_NOCHDIR
1630            is specified, along with FTS_CWDFD.  In that case, there is
1631            no need to change even the virtual cwd file descriptor.
1632            However, if FD is non-negative, we do close it here.  */
1633         if (ISSET (FTS_NOCHDIR))
1634           {
1635             if (ISSET (FTS_CWDFD) && 0 <= fd)
1636               close (fd);
1637             return 0;
1638           }
1639
1640         if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
1641           {
1642             /* When possible, skip the diropen and subsequent fstat+dev/ino
1643                comparison.  I.e., when changing to parent directory
1644                (chdir ("..")), use a file descriptor from the ring and
1645                save the overhead of diropen+fstat, as well as avoiding
1646                failure when we lack "x" access to the virtual cwd.  */
1647             if ( ! i_ring_empty (&sp->fts_fd_ring))
1648               {
1649                 int parent_fd;
1650                 fd_ring_print (sp, stderr, "pre-pop");
1651                 parent_fd = i_ring_pop (&sp->fts_fd_ring);
1652                 is_dotdot = true;
1653                 if (0 <= parent_fd)
1654                   {
1655                     fd = parent_fd;
1656                     dir = NULL;
1657                   }
1658               }
1659           }
1660
1661         newfd = fd;
1662         if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
1663           return -1;
1664
1665         /* The following dev/inode check is necessary if we're doing a
1666            `logical' traversal (through symlinks, a la chown -L), if the
1667            system lacks O_NOFOLLOW support, or if we're changing to ".."
1668            (but not via a popped file descriptor).  When changing to the
1669            name "..", O_NOFOLLOW can't help.  In general, when the target is
1670            not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
1671            follow a symlink, so we can avoid the expense of this fstat.  */
1672         if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
1673             || (dir && STREQ (dir, "..")))
1674           {
1675             struct stat sb;
1676             if (fstat(newfd, &sb))
1677               {
1678                 ret = -1;
1679                 goto bail;
1680               }
1681             if (p->fts_statp->st_dev != sb.st_dev
1682                 || p->fts_statp->st_ino != sb.st_ino)
1683               {
1684                 __set_errno (ENOENT);           /* disinformation */
1685                 ret = -1;
1686                 goto bail;
1687               }
1688           }
1689
1690         if (ISSET(FTS_CWDFD))
1691           {
1692             cwd_advance_fd (sp, newfd, ! is_dotdot);
1693             return 0;
1694           }
1695
1696         ret = fchdir(newfd);
1697 bail:
1698         if (fd < 0)
1699           {
1700             int oerrno = errno;
1701             (void)close(newfd);
1702             __set_errno (oerrno);
1703           }
1704         return ret;
1705 }