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                 /* Even when defer_stat is true, be sure to stat the first
 400                    command line argument, since fts_read (at least with
 401                    FTS_XDEV) requires that.  */
 402                 if (defer_stat && root != NULL) {
 403                         p->fts_info = FTS_NSOK;
 404                         fts_set_stat_required(p, true);
 405                 } else {
 406                         p->fts_info = fts_stat(sp, p, false);
 407                 }
 408
 409                 /*
 410                  * If comparison routine supplied, traverse in sorted
 411                  * order; otherwise traverse in the order specified.
 412                  */
 413                 if (compar) {
 414                         p->fts_link = root;
 415                         root = p;
 416                 } else {
 417                         p->fts_link = NULL;
 418                         if (root == NULL)
 419                                 tmp = root = p;
 420                         else {
 421                                 tmp->fts_link = p;
 422                                 tmp = p;
 423                         }
 424                 }
 425         }
 426         if (compar && nitems > 1)
 427                 root = fts_sort(sp, root, nitems);
 428
 429         /*
 430          * Allocate a dummy pointer and make fts_read think that we've just
 431          * finished the node before the root(s); set p->fts_info to FTS_INIT
 432          * so that everything about the "current" node is ignored.
 433          */
 434         if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
 435                 goto mem3;
 436         sp->fts_cur->fts_link = root;
 437         sp->fts_cur->fts_info = FTS_INIT;
 438         if (! setup_dir (sp))
 439                 goto mem3;
 440
 441         /*
 442          * If using chdir(2), grab a file descriptor pointing to dot to ensure
 443          * that we can get back here; this could be avoided for some file names,
 444          * but almost certainly not worth the effort.  Slashes, symbolic links,
 445          * and ".." are all fairly nasty problems.  Note, if we can't get the
 446          * descriptor we run anyway, just more slowly.
 447          */
 448         if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)
 449             && (sp->fts_rfd = diropen (sp, ".")) < 0)
 450                 SET(FTS_NOCHDIR);
 451
 452         return (sp);
 453
 454 mem3:   fts_lfree(root);
 455         free(parent);
 456 mem2:   free(sp->fts_path);
 457 mem1:   free(sp);
 458         return (NULL);
 459 }
 460
 461 static void
 462 internal_function
 463 fts_load (FTS *sp, register FTSENT *p)
 464 {
 465         register size_t len;
 466         register char *cp;
 467
 468         /*
 469          * Load the stream structure for the next traversal.  Since we don't
 470          * actually enter the directory until after the preorder visit, set
 471          * the fts_accpath field specially so the chdir gets done to the right
 472          * place and the user can access the first node.  From fts_open it's
 473          * known that the file name will fit.
 474          */
 475         len = p->fts_pathlen = p->fts_namelen;
 476         memmove(sp->fts_path, p->fts_name, len + 1);
 477         if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
 478                 len = strlen(++cp);
 479                 memmove(p->fts_name, cp, len + 1);
 480                 p->fts_namelen = len;
 481         }
 482         p->fts_accpath = p->fts_path = sp->fts_path;
 483         sp->fts_dev = p->fts_statp->st_dev;
 484 }
 485
 486 int
 487 fts_close (FTS *sp)
 488 {
 489         register FTSENT *freep, *p;
 490         int saved_errno = 0;
 491
 492         /*
 493          * This still works if we haven't read anything -- the dummy structure
 494          * points to the root list, so we step through to the end of the root
 495          * list which has a valid parent pointer.
 496          */
 497         if (sp->fts_cur) {
 498                 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
 499                         freep = p;
 500                         p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
 501                         free(freep);
 502                 }
 503                 free(p);
 504         }
 505
 506         /* Free up child linked list, sort array, file name buffer. */
 507         if (sp->fts_child)
 508                 fts_lfree(sp->fts_child);
 509         free(sp->fts_array);
 510         free(sp->fts_path);
 511
 512         if (ISSET(FTS_CWDFD))
 513           {
 514             if (0 <= sp->fts_cwd_fd)
 515               close (sp->fts_cwd_fd);
 516           }
 517         else if (!ISSET(FTS_NOCHDIR))
 518           {
 519             /* Return to original directory, save errno if necessary. */
 520             if (fchdir(sp->fts_rfd))
 521               saved_errno = errno;
 522             close(sp->fts_rfd);
 523           }
 524
 525         free_dir (sp);
 526
 527         /* Free up the stream pointer. */
 528         free(sp);
 529
 530         /* Set errno and return. */
 531         if (saved_errno) {
 532                 __set_errno (saved_errno);
 533                 return (-1);
 534         }
 535
 536         return (0);
 537 }
 538
 539 /*
 540  * Special case of "/" at the end of the file name so that slashes aren't
 541  * appended which would cause file names to be written as "....//foo".
 542  */
 543 #define NAPPEND(p)                                                      \
 544         (p->fts_path[p->fts_pathlen - 1] == '/'                         \
 545             ? p->fts_pathlen - 1 : p->fts_pathlen)
 546
 547 FTSENT *
 548 fts_read (register FTS *sp)
 549 {
 550         register FTSENT *p, *tmp;
 551         register unsigned short int instr;
 552         register char *t;
 553
 554         /* If finished or unrecoverable error, return NULL. */
 555         if (sp->fts_cur == NULL || ISSET(FTS_STOP))
 556                 return (NULL);
 557
 558         /* Set current node pointer. */
 559         p = sp->fts_cur;
 560
 561         /* Save and zero out user instructions. */
 562         instr = p->fts_instr;
 563         p->fts_instr = FTS_NOINSTR;
 564
 565         /* Any type of file may be re-visited; re-stat and re-turn. */
 566         if (instr == FTS_AGAIN) {
 567                 p->fts_info = fts_stat(sp, p, false);
 568                 return (p);
 569         }
 570         Dprintf (("fts_read: p=%s\n",
 571                   p->fts_info == FTS_INIT ? "" : p->fts_path));
 572
 573         /*
 574          * Following a symlink -- SLNONE test allows application to see
 575          * SLNONE and recover.  If indirecting through a symlink, have
 576          * keep a pointer to current location.  If unable to get that
 577          * pointer, follow fails.
 578          */
 579         if (instr == FTS_FOLLOW &&
 580             (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
 581                 p->fts_info = fts_stat(sp, p, true);
 582                 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 583                         if ((p->fts_symfd = diropen (sp, ".")) < 0) {
 584                                 p->fts_errno = errno;
 585                                 p->fts_info = FTS_ERR;
 586                         } else
 587                                 p->fts_flags |= FTS_SYMFOLLOW;
 588                 }
 589                 goto check_for_dir;
 590         }
 591
 592         /* Directory in pre-order. */
 593         if (p->fts_info == FTS_D) {
 594                 /* If skipped or crossed mount point, do post-order visit. */
 595                 if (instr == FTS_SKIP ||
 596                     (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
 597                         if (p->fts_flags & FTS_SYMFOLLOW)
 598                                 (void)close(p->fts_symfd);
 599                         if (sp->fts_child) {
 600                                 fts_lfree(sp->fts_child);
 601                                 sp->fts_child = NULL;
 602                         }
 603                         p->fts_info = FTS_DP;
 604                         LEAVE_DIR (sp, p, "1");
 605                         return (p);
 606                 }
 607
 608                 /* Rebuild if only read the names and now traversing. */
 609                 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
 610                         CLR(FTS_NAMEONLY);
 611                         fts_lfree(sp->fts_child);
 612                         sp->fts_child = NULL;
 613                 }
 614
 615                 /*
 616                  * Cd to the subdirectory.
 617                  *
 618                  * If have already read and now fail to chdir, whack the list
 619                  * to make the names come out right, and set the parent errno
 620                  * so the application will eventually get an error condition.
 621                  * Set the FTS_DONTCHDIR flag so that when we logically change
 622                  * directories back to the parent we don't do a chdir.
 623                  *
 624                  * If haven't read do so.  If the read fails, fts_build sets
 625                  * FTS_STOP or the fts_info field of the node.
 626                  */
 627                 if (sp->fts_child != NULL) {
 628                         if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
 629                                 p->fts_errno = errno;
 630                                 p->fts_flags |= FTS_DONTCHDIR;
 631                                 for (p = sp->fts_child; p != NULL;
 632                                      p = p->fts_link)
 633                                         p->fts_accpath =
 634                                             p->fts_parent->fts_accpath;
 635                         }
 636                 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
 637                         if (ISSET(FTS_STOP))
 638                                 return (NULL);
 639                         /* If fts_build's call to fts_safe_changedir failed
 640                            because it was not able to fchdir into a
 641                            subdirectory, tell the caller.  */
 642                         if (p->fts_errno)
 643                                 p->fts_info = FTS_ERR;
 644                         LEAVE_DIR (sp, p, "2");
 645                         return (p);
 646                 }
 647                 p = sp->fts_child;
 648                 sp->fts_child = NULL;
 649                 goto name;
 650         }
 651
 652         /* Move to the next node on this level. */
 653 next:   tmp = p;
 654         if ((p = p->fts_link) != NULL) {
 655                 free(tmp);
 656
 657                 /*
 658                  * If reached the top, return to the original directory (or
 659                  * the root of the tree), and load the file names for the next
 660                  * root.
 661                  */
 662                 if (p->fts_level == FTS_ROOTLEVEL) {
 663                         if (RESTORE_INITIAL_CWD(sp)) {
 664                                 SET(FTS_STOP);
 665                                 sp->fts_cur = p;
 666                                 return (NULL);
 667                         }
 668                         fts_load(sp, p);
 669                         goto check_for_dir;
 670                 }
 671
 672                 /*
 673                  * User may have called fts_set on the node.  If skipped,
 674                  * ignore.  If followed, get a file descriptor so we can
 675                  * get back if necessary.
 676                  */
 677                 if (p->fts_instr == FTS_SKIP)
 678                         goto next;
 679                 if (p->fts_instr == FTS_FOLLOW) {
 680                         p->fts_info = fts_stat(sp, p, true);
 681                         if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 682                                 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
 683                                         p->fts_errno = errno;
 684                                         p->fts_info = FTS_ERR;
 685                                 } else
 686                                         p->fts_flags |= FTS_SYMFOLLOW;
 687                         }
 688                         p->fts_instr = FTS_NOINSTR;
 689                 }
 690
 691 name:           t = sp->fts_path + NAPPEND(p->fts_parent);
 692                 *t++ = '/';
 693                 memmove(t, p->fts_name, p->fts_namelen + 1);
 694 check_for_dir:
 695                 if (p->fts_info == FTS_NSOK)
 696                   {
 697                     switch (p->fts_statp->st_size)
 698                       {
 699                       case FTS_STAT_REQUIRED:
 700                         p->fts_info = fts_stat(sp, p, false);
 701                         break;
 702                       case FTS_NO_STAT_REQUIRED:
 703                         break;
 704                       default:
 705                         abort ();
 706                       }
 707                   }
 708                 sp->fts_cur = p;
 709                 if (p->fts_info == FTS_D)
 710                   {
 711                     Dprintf (("  %s-entering: %s\n", sp, p->fts_path));
 712                     if (! enter_dir (sp, p))
 713                       {
 714                         __set_errno (ENOMEM);
 715                         return NULL;
 716                       }
 717                   }
 718                 return p;
 719         }
 720
 721         /* Move up to the parent node. */
 722         p = tmp->fts_parent;
 723         free(tmp);
 724
 725         if (p->fts_level == FTS_ROOTPARENTLEVEL) {
 726                 /*
 727                  * Done; free everything up and set errno to 0 so the user
 728                  * can distinguish between error and EOF.
 729                  */
 730                 free(p);
 731                 __set_errno (0);
 732                 return (sp->fts_cur = NULL);
 733         }
 734
 735         if (p->fts_info == FTS_NSOK)
 736           abort ();
 737
 738         /* NUL terminate the file name.  */
 739         sp->fts_path[p->fts_pathlen] = '\0';
 740
 741         /*
 742          * Return to the parent directory.  If at a root node, restore
 743          * the initial working directory.  If we came through a symlink,
 744          * go back through the file descriptor.  Otherwise, move up
 745          * one level, via "..".
 746          */
 747         if (p->fts_level == FTS_ROOTLEVEL) {
 748                 if (RESTORE_INITIAL_CWD(sp)) {
 749                         p->fts_errno = errno;
 750                         SET(FTS_STOP);
 751                 }
 752         } else if (p->fts_flags & FTS_SYMFOLLOW) {
 753                 if (FCHDIR(sp, p->fts_symfd)) {
 754                         int saved_errno = errno;
 755                         (void)close(p->fts_symfd);
 756                         __set_errno (saved_errno);
 757                         p->fts_errno = errno;
 758                         SET(FTS_STOP);
 759                 }
 760                 (void)close(p->fts_symfd);
 761         } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
 762                    fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
 763                 p->fts_errno = errno;
 764                 SET(FTS_STOP);
 765         }
 766         p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
 767         if (p->fts_errno == 0)
 768                 LEAVE_DIR (sp, p, "3");
 769         sp->fts_cur = p;
 770         return ISSET(FTS_STOP) ? NULL : p;
 771 }
 772
 773 /*
 774  * Fts_set takes the stream as an argument although it's not used in this
 775  * implementation; it would be necessary if anyone wanted to add global
 776  * semantics to fts using fts_set.  An error return is allowed for similar
 777  * reasons.
 778  */
 779 /* ARGSUSED */
 780 int
 781 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
 782 {
 783         if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
 784             instr != FTS_NOINSTR && instr != FTS_SKIP) {
 785                 __set_errno (EINVAL);
 786                 return (1);
 787         }
 788         p->fts_instr = instr;
 789         return (0);
 790 }
 791
 792 FTSENT *
 793 fts_children (register FTS *sp, int instr)
 794 {
 795         register FTSENT *p;
 796         int fd;
 797
 798         if (instr != 0 && instr != FTS_NAMEONLY) {
 799                 __set_errno (EINVAL);
 800                 return (NULL);
 801         }
 802
 803         /* Set current node pointer. */
 804         p = sp->fts_cur;
 805
 806         /*
 807          * Errno set to 0 so user can distinguish empty directory from
 808          * an error.
 809          */
 810         __set_errno (0);
 811
 812         /* Fatal errors stop here. */
 813         if (ISSET(FTS_STOP))
 814                 return (NULL);
 815
 816         /* Return logical hierarchy of user's arguments. */
 817         if (p->fts_info == FTS_INIT)
 818                 return (p->fts_link);
 819
 820         /*
 821          * If not a directory being visited in pre-order, stop here.  Could
 822          * allow FTS_DNR, assuming the user has fixed the problem, but the
 823          * same effect is available with FTS_AGAIN.
 824          */
 825         if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
 826                 return (NULL);
 827
 828         /* Free up any previous child list. */
 829         if (sp->fts_child != NULL)
 830                 fts_lfree(sp->fts_child);
 831
 832         if (instr == FTS_NAMEONLY) {
 833                 SET(FTS_NAMEONLY);
 834                 instr = BNAMES;
 835         } else
 836                 instr = BCHILD;
 837
 838         /*
 839          * If using chdir on a relative file name and called BEFORE fts_read
 840          * does its chdir to the root of a traversal, we can lose -- we need to
 841          * chdir into the subdirectory, and we don't know where the current
 842          * directory is, so we can't get back so that the upcoming chdir by
 843          * fts_read will work.
 844          */
 845         if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
 846             ISSET(FTS_NOCHDIR))
 847                 return (sp->fts_child = fts_build(sp, instr));
 848
 849         if ((fd = diropen (sp, ".")) < 0)
 850                 return (sp->fts_child = NULL);
 851         sp->fts_child = fts_build(sp, instr);
 852         if (ISSET(FTS_CWDFD))
 853           {
 854             cwd_advance_fd (sp, fd);
 855           }
 856         else
 857           {
 858             if (fchdir(fd))
 859               {
 860                 int saved_errno = errno;
 861                 close (fd);
 862                 __set_errno (saved_errno);
 863                 return NULL;
 864               }
 865             close (fd);
 866           }
 867         return (sp->fts_child);
 868 }
 869
 870 /*
 871  * This is the tricky part -- do not casually change *anything* in here.  The
 872  * idea is to build the linked list of entries that are used by fts_children
 873  * and fts_read.  There are lots of special cases.
 874  *
 875  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
 876  * set and it's a physical walk (so that symbolic links can't be directories),
 877  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
 878  * of the file is in the directory entry.  Otherwise, we assume that the number
 879  * of subdirectories in a node is equal to the number of links to the parent.
 880  * The former skips all stat calls.  The latter skips stat calls in any leaf
 881  * directories and for any files after the subdirectories in the directory have
 882  * been found, cutting the stat calls by about 2/3.
 883  */
 884 static FTSENT *
 885 internal_function
 886 fts_build (register FTS *sp, int type)
 887 {
 888         register struct dirent *dp;
 889         register FTSENT *p, *head;
 890         register size_t nitems;
 891         FTSENT *cur, *tail;
 892         DIR *dirp;
 893         void *oldaddr;
 894         int saved_errno;
 895         bool descend;
 896         bool doadjust;
 897         ptrdiff_t level;
 898         nlink_t nlinks;
 899         bool nostat;
 900         size_t len, maxlen, new_len;
 901         char *cp;
 902
 903         /* Set current node pointer. */
 904         cur = sp->fts_cur;
 905
 906         /*
 907          * Open the directory for reading.  If this fails, we're done.
 908          * If being called from fts_read, set the fts_info field.
 909          */
 910 #if defined FTS_WHITEOUT && 0
 911         if (ISSET(FTS_WHITEOUT))
 912                 oflag = DTF_NODUP|DTF_REWIND;
 913         else
 914                 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
 915 #else
 916 # define __opendir2(file, flag) \
 917         ( ! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
 918           ? opendirat(sp->fts_cwd_fd, file)        \
 919           : opendir(file))
 920 #endif
 921        if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
 922                 if (type == BREAD) {
 923                         cur->fts_info = FTS_DNR;
 924                         cur->fts_errno = errno;
 925                 }
 926                 return (NULL);
 927         }
 928        /* Rather than calling fts_stat for each and every entry encountered
 929           in the readdir loop (below), stat each directory only right after
 930           opening it.  */
 931        if (cur->fts_info == FTS_NSOK)
 932          cur->fts_info = fts_stat(sp, cur, false);
 933
 934         /*
 935          * Nlinks is the number of possible entries of type directory in the
 936          * directory if we're cheating on stat calls, 0 if we're not doing
 937          * any stat calls at all, (nlink_t) -1 if we're statting everything.
 938          */
 939         if (type == BNAMES) {
 940                 nlinks = 0;
 941                 /* Be quiet about nostat, GCC. */
 942                 nostat = false;
 943         } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
 944                 nlinks = (cur->fts_statp->st_nlink
 945                           - (ISSET(FTS_SEEDOT) ? 0 : 2));
 946                 nostat = true;
 947         } else {
 948                 nlinks = -1;
 949                 nostat = false;
 950         }
 951
 952         /*
 953          * If we're going to need to stat anything or we want to descend
 954          * and stay in the directory, chdir.  If this fails we keep going,
 955          * but set a flag so we don't chdir after the post-order visit.
 956          * We won't be able to stat anything, but we can still return the
 957          * names themselves.  Note, that since fts_read won't be able to
 958          * chdir into the directory, it will have to return different file
 959          * names than before, i.e. "a/b" instead of "b".  Since the node
 960          * has already been visited in pre-order, have to wait until the
 961          * post-order visit to return the error.  There is a special case
 962          * here, if there was nothing to stat then it's not an error to
 963          * not be able to stat.  This is all fairly nasty.  If a program
 964          * needed sorted entries or stat information, they had better be
 965          * checking FTS_NS on the returned nodes.
 966          */
 967         if (nlinks || type == BREAD) {
 968                 int dir_fd = dirfd(dirp);
 969                 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
 970                   dir_fd = dup (dir_fd);
 971                 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
 972                         if (nlinks && type == BREAD)
 973                                 cur->fts_errno = errno;
 974                         cur->fts_flags |= FTS_DONTCHDIR;
 975                         descend = false;
 976                         closedir(dirp);
 977                         if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
 978                                 close (dir_fd);
 979                         dirp = NULL;
 980                 } else
 981                         descend = true;
 982         } else
 983                 descend = false;
 984
 985         /*
 986          * Figure out the max file name length that can be stored in the
 987          * current buffer -- the inner loop allocates more space as necessary.
 988          * We really wouldn't have to do the maxlen calculations here, we
 989          * could do them in fts_read before returning the name, but it's a
 990          * lot easier here since the length is part of the dirent structure.
 991          *
 992          * If not changing directories set a pointer so that can just append
 993          * each new component into the file name.
 994          */
 995         len = NAPPEND(cur);
 996         if (ISSET(FTS_NOCHDIR)) {
 997                 cp = sp->fts_path + len;
 998                 *cp++ = '/';
 999         } else {
1000                 /* GCC, you're too verbose. */
1001                 cp = NULL;
1002         }
1003         len++;
1004         maxlen = sp->fts_pathlen - len;
1005
1006         level = cur->fts_level + 1;
1007
1008         /* Read the directory, attaching each entry to the `link' pointer. */
1009         doadjust = false;
1010         for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
1011                 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1012                         continue;
1013
1014                 if ((p = fts_alloc (sp, dp->d_name,
1015                                     _D_EXACT_NAMLEN (dp))) == NULL)
1016                         goto mem1;
1017                 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
1018                         /* include space for NUL */
1019                         oldaddr = sp->fts_path;
1020                         if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
1021                                 /*
1022                                  * No more memory.  Save
1023                                  * errno, free up the current structure and the
1024                                  * structures already allocated.
1025                                  */
1026 mem1:                           saved_errno = errno;
1027                                 free(p);
1028                                 fts_lfree(head);
1029                                 closedir(dirp);
1030                                 cur->fts_info = FTS_ERR;
1031                                 SET(FTS_STOP);
1032                                 __set_errno (saved_errno);
1033                                 return (NULL);
1034                         }
1035                         /* Did realloc() change the pointer? */
1036                         if (oldaddr != sp->fts_path) {
1037                                 doadjust = true;
1038                                 if (ISSET(FTS_NOCHDIR))
1039                                         cp = sp->fts_path + len;
1040                         }
1041                         maxlen = sp->fts_pathlen - len;
1042                 }
1043
1044                 new_len = len + _D_EXACT_NAMLEN (dp);
1045                 if (new_len < len) {
1046                         /*
1047                          * In the unlikely even that we would end up
1048                          * with a file name longer than SIZE_MAX, free up
1049                          * the current structure and the structures already
1050                          * allocated, then error out with ENAMETOOLONG.
1051                          */
1052                         free(p);
1053                         fts_lfree(head);
1054                         closedir(dirp);
1055                         cur->fts_info = FTS_ERR;
1056                         SET(FTS_STOP);
1057                         __set_errno (ENAMETOOLONG);
1058                         return (NULL);
1059                 }
1060                 p->fts_level = level;
1061                 p->fts_parent = sp->fts_cur;
1062                 p->fts_pathlen = new_len;
1063
1064 #if defined FTS_WHITEOUT && 0
1065                 if (dp->d_type == DT_WHT)
1066                         p->fts_flags |= FTS_ISW;
1067 #endif
1068
1069                 /* Build a file name for fts_stat to stat. */
1070                 if (ISSET(FTS_NOCHDIR)) {
1071                         p->fts_accpath = p->fts_path;
1072                         memmove(cp, p->fts_name, p->fts_namelen + 1);
1073                 } else
1074                         p->fts_accpath = p->fts_name;
1075
1076                 bool is_dir;
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 }