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