lib/fts.c

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