lib/fts.c

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