lib/fts.c

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