lib/fts.c

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