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