lib/fts.c

   1 /* Traverse a file hierarchy.
   2
   3    Copyright (C) 2004, 2005 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 #ifdef HAVE_CONFIG_H
  49 # include <config.h>
  50 #endif
  51
  52 #if defined(LIBC_SCCS) && !defined(lint)
  53 static char sccsid[] = "@(#)fts.c       8.6 (Berkeley) 8/14/94";
  54 #endif /* LIBC_SCCS and not lint */
  55
  56 #include "fts_.h"
  57
  58 #if HAVE_SYS_PARAM_H || defined _LIBC
  59 # include <sys/param.h>
  60 #endif
  61 #ifdef _LIBC
  62 # include <include/sys/stat.h>
  63 #else
  64 # include <sys/stat.h>
  65 #endif
  66 #include <fcntl.h>
  67 #include <errno.h>
  68 #include "dirfd.h"
  69 #include "cycle-check.h"
  70 #include "hash.h"
  71 #include "unistd-safer.h"
  72 #include <stdbool.h>
  73 #include <stdlib.h>
  74 #include <string.h>
  75 #include <unistd.h>
  76 #if HAVE_INTTYPES_H
  77 # include <inttypes.h>
  78 #endif
  79 #if HAVE_STDINT_H
  80 # include <stdint.h>
  81 #endif
  82 #if ULONG_MAX < ULLONG_MAX
  83 # define LONGEST_MODIFIER "ll"
  84 #else
  85 # define LONGEST_MODIFIER "l"
  86 #endif
  87 #if PRI_MACROS_BROKEN
  88 # undef PRIuMAX
  89 #endif
  90 #ifndef PRIuMAX
  91 # define PRIuMAX LONGEST_MODIFIER "u"
  92 #endif
  93
  94 #if defined _LIBC
  95 # include <dirent.h>
  96 # define NAMLEN(dirent) _D_EXACT_NAMLEN (dirent)
  97 #else
  98 # if HAVE_DIRENT_H
  99 #  include <dirent.h>
 100 #  define NAMLEN(dirent) strlen ((dirent)->d_name)
 101 # else
 102 #  define dirent direct
 103 #  define NAMLEN(dirent) (dirent)->d_namlen
 104 #  if HAVE_SYS_NDIR_H
 105 #   include <sys/ndir.h>
 106 #  endif
 107 #  if HAVE_SYS_DIR_H
 108 #   include <sys/dir.h>
 109 #  endif
 110 #  if HAVE_NDIR_H
 111 #   include <ndir.h>
 112 #  endif
 113 # endif
 114 #endif
 115
 116 #ifdef _LIBC
 117 # undef close
 118 # define close __close
 119 # undef closedir
 120 # define closedir __closedir
 121 # undef fchdir
 122 # define fchdir __fchdir
 123 # undef open
 124 # define open __open
 125 # undef opendir
 126 # define opendir __opendir
 127 # undef readdir
 128 # define readdir __readdir
 129 #else
 130 # undef internal_function
 131 # define internal_function /* empty */
 132 #endif
 133
 134 /* Arrange to make lstat calls go through the wrapper function
 135    on systems with an lstat function that does not dereference symlinks
 136    that are specified with a trailing slash.  */
 137 #if ! _LIBC && ! LSTAT_FOLLOWS_SLASHED_SYMLINK
 138 int rpl_lstat (const char *, struct stat *);
 139 # undef lstat
 140 # define lstat(Name, Stat_buf) rpl_lstat(Name, Stat_buf)
 141 #endif
 142
 143 #ifndef __set_errno
 144 # define __set_errno(Val) errno = (Val)
 145 #endif
 146
 147 #ifndef __attribute__
 148 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
 149 #  define __attribute__(x) /* empty */
 150 # endif
 151 #endif
 152
 153 #ifndef ATTRIBUTE_UNUSED
 154 # define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
 155 #endif
 156
 157
 158 static FTSENT   *fts_alloc (FTS *, const char *, size_t) internal_function;
 159 static FTSENT   *fts_build (FTS *, int) internal_function;
 160 static void      fts_lfree (FTSENT *) internal_function;
 161 static void      fts_load (FTS *, FTSENT *) internal_function;
 162 static size_t    fts_maxarglen (char * const *) internal_function;
 163 static void      fts_padjust (FTS *, FTSENT *) internal_function;
 164 static bool      fts_palloc (FTS *, size_t) internal_function;
 165 static FTSENT   *fts_sort (FTS *, FTSENT *, size_t) internal_function;
 166 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
 167 static int      fts_safe_changedir (FTS *, FTSENT *, int, const char *)
 168      internal_function;
 169
 170 #ifndef MAX
 171 # define MAX(a,b) ((a) > (b) ? (a) : (b))
 172 #endif
 173
 174 #ifndef SIZE_MAX
 175 # define SIZE_MAX ((size_t) -1)
 176 #endif
 177
 178 #ifndef O_DIRECTORY
 179 # define O_DIRECTORY 0
 180 #endif
 181
 182 #define ISDOT(a)        (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
 183
 184 #define CLR(opt)        (sp->fts_options &= ~(opt))
 185 #define ISSET(opt)      (sp->fts_options & (opt))
 186 #define SET(opt)        (sp->fts_options |= (opt))
 187
 188 #define FCHDIR(sp, fd)  (!ISSET(FTS_NOCHDIR) && fchdir(fd))
 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 #define HT_INITIAL_SIZE 31
 196
 197 #if FTS_DEBUG
 198 bool fts_debug = false;
 199 # include <stdio.h>
 200 # define Dprintf(x) do { if (fts_debug) printf x; } while (0)
 201 #else
 202 # define Dprintf(x)
 203 #endif
 204
 205 #define ENTER_DIR(Fts, Ent, Tag)                                \
 206   do {                                                          \
 207       Dprintf (("  %s-entering: %s\n", Tag, (Ent)->fts_path));  \
 208       enter_dir (sp, p);                                        \
 209     } while (0)
 210
 211 #define LEAVE_DIR(Fts, Ent, Tag)                                \
 212   do {                                                          \
 213       Dprintf (("  %s-leaving: %s\n", Tag, (Ent)->fts_path));   \
 214       leave_dir (sp, p);                                        \
 215     } while (0)
 216
 217 /* Use these each of these to map a device/inode pair to an FTSENT.  */
 218 struct Active_dir
 219 {
 220   dev_t dev;
 221   ino_t ino;
 222   FTSENT *fts_ent;
 223 };
 224
 225 static bool
 226 AD_compare (void const *x, void const *y)
 227 {
 228   struct Active_dir const *ax = x;
 229   struct Active_dir const *ay = y;
 230   return ax->ino == ay->ino
 231       && ax->dev == ay->dev;
 232 }
 233
 234 static size_t
 235 AD_hash (void const *x, size_t table_size)
 236 {
 237   struct Active_dir const *ax = x;
 238   return (uintmax_t) ax->ino % table_size;
 239 }
 240
 241 static void
 242 enter_dir (FTS *fts, FTSENT *ent)
 243 {
 244   if (fts->active_dir_ht)
 245     {
 246       struct stat const *st = ent->fts_statp;
 247       struct Active_dir *ad = malloc (sizeof (struct Active_dir));
 248       struct Active_dir *ad_from_table;
 249
 250       if (ad == NULL)
 251         goto give_up;
 252
 253       ad->dev = st->st_dev;
 254       ad->ino = st->st_ino;
 255       ad->fts_ent = ent;
 256
 257       /* See if we've already encountered this directory.
 258          This can happen when following symlinks as well as
 259          with a corrupted directory hierarchy. */
 260       ad_from_table = hash_insert (fts->active_dir_ht, ad);
 261
 262       if (ad_from_table == NULL)
 263         {
 264         give_up:
 265           /* Insertion failed due to lack of memory.  Free the hash
 266              table and turn off this sort of cycle detection.  */
 267           hash_free (fts->active_dir_ht);
 268           fts->active_dir_ht = NULL;
 269           return;
 270         }
 271
 272       if (ad_from_table != ad)
 273         {
 274           /* There was an entry with matching dev/inode already in the table.
 275              Record the fact that we've found a cycle.  */
 276           ent->fts_cycle = ad_from_table->fts_ent;
 277           ent->fts_info = FTS_DC;
 278
 279           /* ad was not inserted, so free it.  */
 280           free (ad);
 281         }
 282     }
 283   else if (fts->cycle_state)
 284     {
 285       if (cycle_check (fts->cycle_state, ent->fts_statp))
 286         {
 287           /* FIXME: setting fts_cycle like this isn't proper.
 288              To do what the documentation requires, we'd have to
 289              go around the cycle again and find the right entry.
 290              But no callers in coreutils use the fts_cycle member. */
 291           ent->fts_cycle = ent;
 292           ent->fts_info = FTS_DC;
 293         }
 294     }
 295 }
 296
 297 static void
 298 leave_dir (FTS *fts, FTSENT *ent)
 299 {
 300   if (fts->active_dir_ht)
 301     {
 302       struct stat const *st = ent->fts_statp;
 303       struct Active_dir obj;
 304       void *found;
 305       obj.dev = st->st_dev;
 306       obj.ino = st->st_ino;
 307       found = hash_delete (fts->active_dir_ht, &obj);
 308       if (!found)
 309         abort ();
 310       free (found);
 311     }
 312 }
 313
 314 /* Open the directory DIR if possible, and return a file
 315    descriptor.  Return -1 and set errno on failure.  It doesn't matter
 316    whether the file descriptor has read or write access.  */
 317
 318 static int
 319 internal_function
 320 diropen (char const *dir)
 321 {
 322   int fd = open (dir, O_RDONLY | O_DIRECTORY);
 323   if (fd < 0)
 324     fd = open (dir, O_WRONLY | O_DIRECTORY);
 325   return fd;
 326 }
 327
 328 FTS *
 329 fts_open (char * const *argv,
 330           register int options,
 331           int (*compar) (FTSENT const **, FTSENT const **))
 332 {
 333         register FTS *sp;
 334         register FTSENT *p, *root;
 335         register size_t nitems;
 336         FTSENT *parent, *tmp = NULL;    /* pacify gcc */
 337         size_t len;
 338
 339         /* Options check. */
 340         if (options & ~FTS_OPTIONMASK) {
 341                 __set_errno (EINVAL);
 342                 return (NULL);
 343         }
 344
 345         /* Allocate/initialize the stream */
 346         if ((sp = malloc(sizeof(FTS))) == NULL)
 347                 return (NULL);
 348         memset(sp, 0, sizeof(FTS));
 349         sp->fts_compar = compar;
 350         sp->fts_options = options;
 351
 352         /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
 353         if (ISSET(FTS_LOGICAL))
 354                 SET(FTS_NOCHDIR);
 355
 356         /*
 357          * Start out with 1K of path space, and enough, in any case,
 358          * to hold the user's paths.
 359          */
 360 #ifndef MAXPATHLEN
 361 # define MAXPATHLEN 1024
 362 #endif
 363         if (! fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
 364                 goto mem1;
 365
 366         /* Allocate/initialize root's parent. */
 367         if ((parent = fts_alloc(sp, "", 0)) == NULL)
 368                 goto mem2;
 369         parent->fts_level = FTS_ROOTPARENTLEVEL;
 370
 371         /* Allocate/initialize root(s). */
 372         for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
 373                 /* Don't allow zero-length paths. */
 374                 if ((len = strlen(*argv)) == 0) {
 375                         __set_errno (ENOENT);
 376                         goto mem3;
 377                 }
 378
 379                 if ((p = fts_alloc(sp, *argv, len)) == NULL)
 380                         goto mem3;
 381                 p->fts_level = FTS_ROOTLEVEL;
 382                 p->fts_parent = parent;
 383                 p->fts_accpath = p->fts_name;
 384                 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW) != 0);
 385
 386                 /* Command-line "." and ".." are real directories. */
 387                 if (p->fts_info == FTS_DOT)
 388                         p->fts_info = FTS_D;
 389
 390                 /*
 391                  * If comparison routine supplied, traverse in sorted
 392                  * order; otherwise traverse in the order specified.
 393                  */
 394                 if (compar) {
 395                         p->fts_link = root;
 396                         root = p;
 397                 } else {
 398                         p->fts_link = NULL;
 399                         if (root == NULL)
 400                                 tmp = root = p;
 401                         else {
 402                                 tmp->fts_link = p;
 403                                 tmp = p;
 404                         }
 405                 }
 406         }
 407         if (compar && nitems > 1)
 408                 root = fts_sort(sp, root, nitems);
 409
 410         /*
 411          * Allocate a dummy pointer and make fts_read think that we've just
 412          * finished the node before the root(s); set p->fts_info to FTS_INIT
 413          * so that everything about the "current" node is ignored.
 414          */
 415         if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
 416                 goto mem3;
 417         sp->fts_cur->fts_link = root;
 418         sp->fts_cur->fts_info = FTS_INIT;
 419
 420         if (ISSET (FTS_TIGHT_CYCLE_CHECK))
 421           {
 422             sp->active_dir_ht = hash_initialize (HT_INITIAL_SIZE,
 423                                                  NULL, AD_hash,
 424                                                  AD_compare, free);
 425             if (sp->active_dir_ht == NULL)
 426               goto mem3;
 427             sp->cycle_state = malloc (sizeof *sp->cycle_state);
 428           }
 429         else
 430           {
 431             sp->cycle_state = malloc (sizeof *sp->cycle_state);
 432             if (sp->cycle_state == NULL)
 433               goto mem3;
 434             cycle_check_init (sp->cycle_state);
 435             sp->active_dir_ht = NULL;
 436           }
 437
 438         /*
 439          * If using chdir(2), grab a file descriptor pointing to dot to ensure
 440          * that we can get back here; this could be avoided for some paths,
 441          * but almost certainly not worth the effort.  Slashes, symbolic links,
 442          * and ".." are all fairly nasty problems.  Note, if we can't get the
 443          * descriptor we run anyway, just more slowly.
 444          */
 445         if (!ISSET(FTS_NOCHDIR)
 446             && (sp->fts_rfd = diropen (".")) < 0)
 447                 SET(FTS_NOCHDIR);
 448
 449         return (sp);
 450
 451 mem3:   fts_lfree(root);
 452         free(parent);
 453 mem2:   free(sp->fts_path);
 454 mem1:   free(sp);
 455         return (NULL);
 456 }
 457
 458 static void
 459 internal_function
 460 fts_load (FTS *sp, register FTSENT *p)
 461 {
 462         register size_t len;
 463         register char *cp;
 464
 465         /*
 466          * Load the stream structure for the next traversal.  Since we don't
 467          * actually enter the directory until after the preorder visit, set
 468          * the fts_accpath field specially so the chdir gets done to the right
 469          * place and the user can access the first node.  From fts_open it's
 470          * known that the path will fit.
 471          */
 472         len = p->fts_pathlen = p->fts_namelen;
 473         memmove(sp->fts_path, p->fts_name, len + 1);
 474         if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
 475                 len = strlen(++cp);
 476                 memmove(p->fts_name, cp, len + 1);
 477                 p->fts_namelen = len;
 478         }
 479         p->fts_accpath = p->fts_path = sp->fts_path;
 480         sp->fts_dev = p->fts_statp->st_dev;
 481 }
 482
 483 int
 484 fts_close (FTS *sp)
 485 {
 486         register FTSENT *freep, *p;
 487         int saved_errno = 0;
 488
 489         /*
 490          * This still works if we haven't read anything -- the dummy structure
 491          * points to the root list, so we step through to the end of the root
 492          * list which has a valid parent pointer.
 493          */
 494         if (sp->fts_cur) {
 495                 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
 496                         freep = p;
 497                         p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
 498                         free(freep);
 499                 }
 500                 free(p);
 501         }
 502
 503         /* Free up child linked list, sort array, path buffer. */
 504         if (sp->fts_child)
 505                 fts_lfree(sp->fts_child);
 506         if (sp->fts_array)
 507                 free(sp->fts_array);
 508         free(sp->fts_path);
 509
 510         /* Return to original directory, save errno if necessary. */
 511         if (!ISSET(FTS_NOCHDIR)) {
 512                 if (fchdir(sp->fts_rfd))
 513                         saved_errno = errno;
 514                 (void)close(sp->fts_rfd);
 515         }
 516
 517         /* Free any memory used for cycle detection.  */
 518         if (sp->active_dir_ht)
 519           hash_free (sp->active_dir_ht);
 520         if (sp->cycle_state)
 521           free (sp->cycle_state);
 522
 523         /* Free up the stream pointer. */
 524         free(sp);
 525
 526         /* Set errno and return. */
 527         if (saved_errno) {
 528                 __set_errno (saved_errno);
 529                 return (-1);
 530         }
 531
 532         return (0);
 533 }
 534
 535 /*
 536  * Special case of "/" at the end of the path so that slashes aren't
 537  * appended which would cause paths to be written as "....//foo".
 538  */
 539 #define NAPPEND(p)                                                      \
 540         (p->fts_path[p->fts_pathlen - 1] == '/'                         \
 541             ? p->fts_pathlen - 1 : p->fts_pathlen)
 542
 543 FTSENT *
 544 fts_read (register FTS *sp)
 545 {
 546         register FTSENT *p, *tmp;
 547         register unsigned short int instr;
 548         register char *t;
 549         int saved_errno;
 550
 551         /* If finished or unrecoverable error, return NULL. */
 552         if (sp->fts_cur == NULL || ISSET(FTS_STOP))
 553                 return (NULL);
 554
 555         /* Set current node pointer. */
 556         p = sp->fts_cur;
 557
 558         /* Save and zero out user instructions. */
 559         instr = p->fts_instr;
 560         p->fts_instr = FTS_NOINSTR;
 561
 562         /* Any type of file may be re-visited; re-stat and re-turn. */
 563         if (instr == FTS_AGAIN) {
 564                 p->fts_info = fts_stat(sp, p, false);
 565                 return (p);
 566         }
 567         Dprintf (("fts_read: p=%s\n",
 568                   p->fts_info == FTS_INIT ? "" : p->fts_path));
 569
 570         /*
 571          * Following a symlink -- SLNONE test allows application to see
 572          * SLNONE and recover.  If indirecting through a symlink, have
 573          * keep a pointer to current location.  If unable to get that
 574          * pointer, follow fails.
 575          */
 576         if (instr == FTS_FOLLOW &&
 577             (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
 578                 p->fts_info = fts_stat(sp, p, true);
 579                 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 580                         if ((p->fts_symfd = diropen (".")) < 0) {
 581                                 p->fts_errno = errno;
 582                                 p->fts_info = FTS_ERR;
 583                         } else
 584                                 p->fts_flags |= FTS_SYMFOLLOW;
 585                 }
 586                 if (p->fts_info == FTS_D)
 587                         ENTER_DIR (sp, p, "7");
 588                 return (p);
 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                         /* FIXME: see if this should be in an else block */
 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 paths for the next root.
 660                  */
 661                 if (p->fts_level == FTS_ROOTLEVEL) {
 662                         if (FCHDIR(sp, sp->fts_rfd)) {
 663                                 SET(FTS_STOP);
 664                                 return (NULL);
 665                         }
 666                         fts_load(sp, p);
 667                         if (p->fts_info == FTS_D)
 668                                 ENTER_DIR (sp, p, "8");
 669                         return (sp->fts_cur = p);
 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 (".")) < 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                 if (p->fts_info == FTS_D)
 695                         ENTER_DIR (sp, p, "9");
 696                 return (sp->fts_cur = p);
 697         }
 698
 699         /* Move up to the parent node. */
 700         p = tmp->fts_parent;
 701         free(tmp);
 702
 703         if (p->fts_level == FTS_ROOTPARENTLEVEL) {
 704                 /*
 705                  * Done; free everything up and set errno to 0 so the user
 706                  * can distinguish between error and EOF.
 707                  */
 708                 free(p);
 709                 __set_errno (0);
 710                 return (sp->fts_cur = NULL);
 711         }
 712
 713         /* NUL terminate the pathname. */
 714         sp->fts_path[p->fts_pathlen] = '\0';
 715
 716         /*
 717          * Return to the parent directory.  If at a root node or came through
 718          * a symlink, go back through the file descriptor.  Otherwise, cd up
 719          * one directory.
 720          */
 721         if (p->fts_level == FTS_ROOTLEVEL) {
 722                 if (FCHDIR(sp, sp->fts_rfd)) {
 723                         p->fts_errno = errno;
 724                         SET(FTS_STOP);
 725                 }
 726         } else if (p->fts_flags & FTS_SYMFOLLOW) {
 727                 if (FCHDIR(sp, p->fts_symfd)) {
 728                         saved_errno = errno;
 729                         (void)close(p->fts_symfd);
 730                         __set_errno (saved_errno);
 731                         p->fts_errno = errno;
 732                         SET(FTS_STOP);
 733                 }
 734                 (void)close(p->fts_symfd);
 735         } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
 736                    fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
 737                 p->fts_errno = errno;
 738                 SET(FTS_STOP);
 739         }
 740         p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
 741         if (p->fts_errno == 0)
 742                 LEAVE_DIR (sp, p, "3");
 743         sp->fts_cur = p;
 744         return ISSET(FTS_STOP) ? NULL : p;
 745 }
 746
 747 /*
 748  * Fts_set takes the stream as an argument although it's not used in this
 749  * implementation; it would be necessary if anyone wanted to add global
 750  * semantics to fts using fts_set.  An error return is allowed for similar
 751  * reasons.
 752  */
 753 /* ARGSUSED */
 754 int
 755 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
 756 {
 757         if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
 758             instr != FTS_NOINSTR && instr != FTS_SKIP) {
 759                 __set_errno (EINVAL);
 760                 return (1);
 761         }
 762         p->fts_instr = instr;
 763         return (0);
 764 }
 765
 766 FTSENT *
 767 fts_children (register FTS *sp, int instr)
 768 {
 769         register FTSENT *p;
 770         int fd;
 771
 772         if (instr != 0 && instr != FTS_NAMEONLY) {
 773                 __set_errno (EINVAL);
 774                 return (NULL);
 775         }
 776
 777         /* Set current node pointer. */
 778         p = sp->fts_cur;
 779
 780         /*
 781          * Errno set to 0 so user can distinguish empty directory from
 782          * an error.
 783          */
 784         __set_errno (0);
 785
 786         /* Fatal errors stop here. */
 787         if (ISSET(FTS_STOP))
 788                 return (NULL);
 789
 790         /* Return logical hierarchy of user's arguments. */
 791         if (p->fts_info == FTS_INIT)
 792                 return (p->fts_link);
 793
 794         /*
 795          * If not a directory being visited in pre-order, stop here.  Could
 796          * allow FTS_DNR, assuming the user has fixed the problem, but the
 797          * same effect is available with FTS_AGAIN.
 798          */
 799         if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
 800                 return (NULL);
 801
 802         /* Free up any previous child list. */
 803         if (sp->fts_child != NULL)
 804                 fts_lfree(sp->fts_child);
 805
 806         if (instr == FTS_NAMEONLY) {
 807                 SET(FTS_NAMEONLY);
 808                 instr = BNAMES;
 809         } else
 810                 instr = BCHILD;
 811
 812         /*
 813          * If using chdir on a relative path and called BEFORE fts_read does
 814          * its chdir to the root of a traversal, we can lose -- we need to
 815          * chdir into the subdirectory, and we don't know where the current
 816          * directory is, so we can't get back so that the upcoming chdir by
 817          * fts_read will work.
 818          */
 819         if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
 820             ISSET(FTS_NOCHDIR))
 821                 return (sp->fts_child = fts_build(sp, instr));
 822
 823         if ((fd = diropen (".")) < 0)
 824                 return (sp->fts_child = NULL);
 825         sp->fts_child = fts_build(sp, instr);
 826         if (fchdir(fd)) {
 827                 (void)close(fd);
 828                 return (NULL);
 829         }
 830         (void)close(fd);
 831         return (sp->fts_child);
 832 }
 833
 834 /*
 835  * This is the tricky part -- do not casually change *anything* in here.  The
 836  * idea is to build the linked list of entries that are used by fts_children
 837  * and fts_read.  There are lots of special cases.
 838  *
 839  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
 840  * set and it's a physical walk (so that symbolic links can't be directories),
 841  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
 842  * of the file is in the directory entry.  Otherwise, we assume that the number
 843  * of subdirectories in a node is equal to the number of links to the parent.
 844  * The former skips all stat calls.  The latter skips stat calls in any leaf
 845  * directories and for any files after the subdirectories in the directory have
 846  * been found, cutting the stat calls by about 2/3.
 847  */
 848 static FTSENT *
 849 internal_function
 850 fts_build (register FTS *sp, int type)
 851 {
 852         register struct dirent *dp;
 853         register FTSENT *p, *head;
 854         register size_t nitems;
 855         FTSENT *cur, *tail;
 856         DIR *dirp;
 857         void *oldaddr;
 858         int cderrno;
 859         int saved_errno;
 860         bool descend;
 861         bool doadjust;
 862         ptrdiff_t level;
 863         nlink_t nlinks;
 864         bool nostat;
 865         size_t len, maxlen, new_len;
 866         char *cp;
 867
 868         /* Set current node pointer. */
 869         cur = sp->fts_cur;
 870
 871         /*
 872          * Open the directory for reading.  If this fails, we're done.
 873          * If being called from fts_read, set the fts_info field.
 874          */
 875 #if defined FTS_WHITEOUT && 0
 876         if (ISSET(FTS_WHITEOUT))
 877                 oflag = DTF_NODUP|DTF_REWIND;
 878         else
 879                 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
 880 #else
 881 # define __opendir2(path, flag) opendir(path)
 882 #endif
 883        if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
 884                 if (type == BREAD) {
 885                         cur->fts_info = FTS_DNR;
 886                         cur->fts_errno = errno;
 887                 }
 888                 return (NULL);
 889         }
 890
 891         /*
 892          * Nlinks is the number of possible entries of type directory in the
 893          * directory if we're cheating on stat calls, 0 if we're not doing
 894          * any stat calls at all, (nlink_t) -1 if we're statting everything.
 895          */
 896         if (type == BNAMES) {
 897                 nlinks = 0;
 898                 /* Be quiet about nostat, GCC. */
 899                 nostat = false;
 900         } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
 901                 nlinks = (cur->fts_statp->st_nlink
 902                           - (ISSET(FTS_SEEDOT) ? 0 : 2));
 903                 nostat = true;
 904         } else {
 905                 nlinks = -1;
 906                 nostat = false;
 907         }
 908
 909         /*
 910          * If we're going to need to stat anything or we want to descend
 911          * and stay in the directory, chdir.  If this fails we keep going,
 912          * but set a flag so we don't chdir after the post-order visit.
 913          * We won't be able to stat anything, but we can still return the
 914          * names themselves.  Note, that since fts_read won't be able to
 915          * chdir into the directory, it will have to return different path
 916          * names than before, i.e. "a/b" instead of "b".  Since the node
 917          * has already been visited in pre-order, have to wait until the
 918          * post-order visit to return the error.  There is a special case
 919          * here, if there was nothing to stat then it's not an error to
 920          * not be able to stat.  This is all fairly nasty.  If a program
 921          * needed sorted entries or stat information, they had better be
 922          * checking FTS_NS on the returned nodes.
 923          */
 924         cderrno = 0;
 925         if (nlinks || type == BREAD) {
 926                 if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
 927                         if (nlinks && type == BREAD)
 928                                 cur->fts_errno = errno;
 929                         cur->fts_flags |= FTS_DONTCHDIR;
 930                         descend = false;
 931                         cderrno = errno;
 932                         closedir(dirp);
 933                         dirp = NULL;
 934                 } else
 935                         descend = true;
 936         } else
 937                 descend = false;
 938
 939         /*
 940          * Figure out the max file name length that can be stored in the
 941          * current path -- the inner loop allocates more path as necessary.
 942          * We really wouldn't have to do the maxlen calculations here, we
 943          * could do them in fts_read before returning the path, but it's a
 944          * lot easier here since the length is part of the dirent structure.
 945          *
 946          * If not changing directories set a pointer so that can just append
 947          * each new name into the path.
 948          */
 949         len = NAPPEND(cur);
 950         if (ISSET(FTS_NOCHDIR)) {
 951                 cp = sp->fts_path + len;
 952                 *cp++ = '/';
 953         } else {
 954                 /* GCC, you're too verbose. */
 955                 cp = NULL;
 956         }
 957         len++;
 958         maxlen = sp->fts_pathlen - len;
 959
 960         level = cur->fts_level + 1;
 961
 962         /* Read the directory, attaching each entry to the `link' pointer. */
 963         doadjust = false;
 964         for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
 965                 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
 966                         continue;
 967
 968                 if ((p = fts_alloc(sp, dp->d_name, NAMLEN (dp))) == NULL)
 969                         goto mem1;
 970                 if (NAMLEN (dp) >= maxlen) {/* include space for NUL */
 971                         oldaddr = sp->fts_path;
 972                         if (! fts_palloc(sp, NAMLEN (dp) + len + 1)) {
 973                                 /*
 974                                  * No more memory for path or structures.  Save
 975                                  * errno, free up the current structure and the
 976                                  * structures already allocated.
 977                                  */
 978 mem1:                           saved_errno = errno;
 979                                 if (p)
 980                                         free(p);
 981                                 fts_lfree(head);
 982                                 closedir(dirp);
 983                                 cur->fts_info = FTS_ERR;
 984                                 SET(FTS_STOP);
 985                                 __set_errno (saved_errno);
 986                                 return (NULL);
 987                         }
 988                         /* Did realloc() change the pointer? */
 989                         if (oldaddr != sp->fts_path) {
 990                                 doadjust = true;
 991                                 if (ISSET(FTS_NOCHDIR))
 992                                         cp = sp->fts_path + len;
 993                         }
 994                         maxlen = sp->fts_pathlen - len;
 995                 }
 996
 997                 new_len = len + NAMLEN (dp);
 998                 if (new_len < len) {
 999                         /*
1000                          * In the unlikely even that we would end up
1001                          * with a path longer than SIZE_MAX, free up
1002                          * the current structure and the structures already
1003                          * allocated, then error out with ENAMETOOLONG.
1004                          */
1005                         free(p);
1006                         fts_lfree(head);
1007                         closedir(dirp);
1008                         cur->fts_info = FTS_ERR;
1009                         SET(FTS_STOP);
1010                         __set_errno (ENAMETOOLONG);
1011                         return (NULL);
1012                 }
1013                 p->fts_level = level;
1014                 p->fts_parent = sp->fts_cur;
1015                 p->fts_pathlen = new_len;
1016
1017 #if defined FTS_WHITEOUT && 0
1018                 if (dp->d_type == DT_WHT)
1019                         p->fts_flags |= FTS_ISW;
1020 #endif
1021
1022                 if (cderrno) {
1023                         if (nlinks) {
1024                                 p->fts_info = FTS_NS;
1025                                 p->fts_errno = cderrno;
1026                         } else
1027                                 p->fts_info = FTS_NSOK;
1028                         p->fts_accpath = cur->fts_accpath;
1029                 } else if (nlinks == 0
1030 #if HAVE_STRUCT_DIRENT_D_TYPE
1031                            || (nostat &&
1032                                dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
1033 #endif
1034                     ) {
1035                         p->fts_accpath =
1036                             ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
1037                         p->fts_info = FTS_NSOK;
1038                 } else {
1039                         /* Build a file name for fts_stat to stat. */
1040                         if (ISSET(FTS_NOCHDIR)) {
1041                                 p->fts_accpath = p->fts_path;
1042                                 memmove(cp, p->fts_name, p->fts_namelen + 1);
1043                         } else
1044                                 p->fts_accpath = p->fts_name;
1045                         /* Stat it. */
1046                         p->fts_info = fts_stat(sp, p, false);
1047
1048                         /* Decrement link count if applicable. */
1049                         if (nlinks > 0 && (p->fts_info == FTS_D ||
1050                             p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
1051                                 nlinks -= nostat;
1052                 }
1053
1054                 /* We walk in directory order so "ls -f" doesn't get upset. */
1055                 p->fts_link = NULL;
1056                 if (head == NULL)
1057                         head = tail = p;
1058                 else {
1059                         tail->fts_link = p;
1060                         tail = p;
1061                 }
1062                 ++nitems;
1063         }
1064         if (dirp)
1065                 closedir(dirp);
1066
1067         /*
1068          * If realloc() changed the address of the path, adjust the
1069          * addresses for the rest of the tree and the dir list.
1070          */
1071         if (doadjust)
1072                 fts_padjust(sp, head);
1073
1074         /*
1075          * If not changing directories, reset the path back to original
1076          * state.
1077          */
1078         if (ISSET(FTS_NOCHDIR)) {
1079                 if (len == sp->fts_pathlen || nitems == 0)
1080                         --cp;
1081                 *cp = '\0';
1082         }
1083
1084         /*
1085          * If descended after called from fts_children or after called from
1086          * fts_read and nothing found, get back.  At the root level we use
1087          * the saved fd; if one of fts_open()'s arguments is a relative path
1088          * to an empty directory, we wind up here with no other way back.  If
1089          * can't get back, we're done.
1090          */
1091         if (descend && (type == BCHILD || !nitems) &&
1092             (cur->fts_level == FTS_ROOTLEVEL ?
1093              FCHDIR(sp, sp->fts_rfd) :
1094              fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1095                 cur->fts_info = FTS_ERR;
1096                 SET(FTS_STOP);
1097                 return (NULL);
1098         }
1099
1100         /* If didn't find anything, return NULL. */
1101         if (!nitems) {
1102                 if (type == BREAD)
1103                         cur->fts_info = FTS_DP;
1104                 return (NULL);
1105         }
1106
1107         /* Sort the entries. */
1108         if (sp->fts_compar && nitems > 1)
1109                 head = fts_sort(sp, head, nitems);
1110         return (head);
1111 }
1112
1113 #if FTS_DEBUG
1114
1115 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1116    current hierarchy.  There should be a directory with dev/inode
1117    matching those of AD.  If not, print a lot of diagnostics.  */
1118 static void
1119 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1120 {
1121   FTSENT const *ent;
1122   for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1123     {
1124       if (ad->ino == ent->fts_statp->st_ino
1125           && ad->dev == ent->fts_statp->st_dev)
1126         return;
1127     }
1128   printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1129   printf ("active dirs:\n");
1130   for (ent = e_curr;
1131        ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1132     printf ("  %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1133             ad->fts_ent->fts_accpath,
1134             (uintmax_t) ad->dev,
1135             (uintmax_t) ad->ino,
1136             ent->fts_accpath,
1137             (uintmax_t) ent->fts_statp->st_dev,
1138             (uintmax_t) ent->fts_statp->st_ino);
1139 }
1140
1141 void
1142 fts_cross_check (FTS const *sp)
1143 {
1144   FTSENT const *ent = sp->fts_cur;
1145   FTSENT const *t;
1146   if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1147     return;
1148
1149   Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1150   /* Make sure every parent dir is in the tree.  */
1151   for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1152     {
1153       struct Active_dir ad;
1154       ad.ino = t->fts_statp->st_ino;
1155       ad.dev = t->fts_statp->st_dev;
1156       if ( ! hash_lookup (sp->active_dir_ht, &ad))
1157         printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1158     }
1159
1160   /* Make sure every dir in the tree is an active dir.
1161      But ENT is not necessarily a directory.  If so, just skip this part. */
1162   if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1163       && (ent->fts_info == FTS_DP
1164           || ent->fts_info == FTS_D))
1165     {
1166       struct Active_dir *ad;
1167       for (ad = hash_get_first (sp->active_dir_ht); ad != NULL;
1168            ad = hash_get_next (sp->active_dir_ht, ad))
1169         {
1170           find_matching_ancestor (ent, ad);
1171         }
1172     }
1173 }
1174 #endif
1175
1176 static unsigned short int
1177 internal_function
1178 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1179 {
1180         struct stat *sbp = p->fts_statp;
1181         int saved_errno;
1182
1183 #if defined FTS_WHITEOUT && 0
1184         /* check for whiteout */
1185         if (p->fts_flags & FTS_ISW) {
1186                 memset(sbp, '\0', sizeof (*sbp));
1187                 sbp->st_mode = S_IFWHT;
1188                 return (FTS_W);
1189        }
1190 #endif
1191
1192         /*
1193          * If doing a logical walk, or application requested FTS_FOLLOW, do
1194          * a stat(2).  If that fails, check for a non-existent symlink.  If
1195          * fail, set the errno from the stat call.
1196          */
1197         if (ISSET(FTS_LOGICAL) || follow) {
1198                 if (stat(p->fts_accpath, sbp)) {
1199                         saved_errno = errno;
1200                         if (!lstat(p->fts_accpath, sbp)) {
1201                                 __set_errno (0);
1202                                 return (FTS_SLNONE);
1203                         }
1204                         p->fts_errno = saved_errno;
1205                         goto err;
1206                 }
1207         } else if (lstat(p->fts_accpath, sbp)) {
1208                 p->fts_errno = errno;
1209 err:            memset(sbp, 0, sizeof(struct stat));
1210                 return (FTS_NS);
1211         }
1212
1213         if (S_ISDIR(sbp->st_mode)) {
1214                 if (ISDOT(p->fts_name))
1215                         return (FTS_DOT);
1216                 return (FTS_D);
1217         }
1218         if (S_ISLNK(sbp->st_mode))
1219                 return (FTS_SL);
1220         if (S_ISREG(sbp->st_mode))
1221                 return (FTS_F);
1222         return (FTS_DEFAULT);
1223 }
1224
1225 static int
1226 fts_compar (void const *a, void const *b)
1227 {
1228   /* Convert A and B to the correct types, to pacify the compiler, and
1229      for portability to bizarre hosts where "void const *" and "FTSENT
1230      const **" differ in runtime representation.  The comparison
1231      function cannot modify *a and *b, but there is no compile-time
1232      check for this.  */
1233   FTSENT const **pa = (FTSENT const **) a;
1234   FTSENT const **pb = (FTSENT const **) b;
1235   return pa[0]->fts_fts->fts_compar (pa, pb);
1236 }
1237
1238 static FTSENT *
1239 internal_function
1240 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1241 {
1242         register FTSENT **ap, *p;
1243
1244         /* On most modern hosts, void * and FTSENT ** have the same
1245            run-time representation, and one can convert sp->fts_compar to
1246            the type qsort expects without problem.  Use the heuristic that
1247            this is OK if the two pointer types are the same size, and if
1248            converting FTSENT ** to long int is the same as converting
1249            FTSENT ** to void * and then to long int.  This heuristic isn't
1250            valid in general but we don't know of any counterexamples.  */
1251         FTSENT *dummy;
1252         int (*compare) (void const *, void const *) =
1253           ((sizeof &dummy == sizeof (void *)
1254             && (long int) &dummy == (long int) (void *) &dummy)
1255            ? (int (*) (void const *, void const *)) sp->fts_compar
1256            : fts_compar);
1257
1258         /*
1259          * Construct an array of pointers to the structures and call qsort(3).
1260          * Reassemble the array in the order returned by qsort.  If unable to
1261          * sort for memory reasons, return the directory entries in their
1262          * current order.  Allocate enough space for the current needs plus
1263          * 40 so don't realloc one entry at a time.
1264          */
1265         if (nitems > sp->fts_nitems) {
1266                 struct _ftsent **a;
1267
1268                 sp->fts_nitems = nitems + 40;
1269                 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1270                     || ! (a = realloc (sp->fts_array,
1271                                        sp->fts_nitems * sizeof *a))) {
1272                         free(sp->fts_array);
1273                         sp->fts_array = NULL;
1274                         sp->fts_nitems = 0;
1275                         return (head);
1276                 }
1277                 sp->fts_array = a;
1278         }
1279         for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1280                 *ap++ = p;
1281         qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1282         for (head = *(ap = sp->fts_array); --nitems; ++ap)
1283                 ap[0]->fts_link = ap[1];
1284         ap[0]->fts_link = NULL;
1285         return (head);
1286 }
1287
1288 static FTSENT *
1289 internal_function
1290 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1291 {
1292         register FTSENT *p;
1293         size_t len;
1294
1295         /*
1296          * The file name is a variable length array.  Allocate the FTSENT
1297          * structure and the file name in one chunk.
1298          */
1299         len = sizeof(FTSENT) + namelen;
1300         if ((p = malloc(len)) == NULL)
1301                 return (NULL);
1302
1303         /* Copy the name and guarantee NUL termination. */
1304         memmove(p->fts_name, name, namelen);
1305         p->fts_name[namelen] = '\0';
1306
1307         p->fts_namelen = namelen;
1308         p->fts_fts = sp;
1309         p->fts_path = sp->fts_path;
1310         p->fts_errno = 0;
1311         p->fts_flags = 0;
1312         p->fts_instr = FTS_NOINSTR;
1313         p->fts_number = 0;
1314         p->fts_pointer = NULL;
1315         return (p);
1316 }
1317
1318 static void
1319 internal_function
1320 fts_lfree (register FTSENT *head)
1321 {
1322         register FTSENT *p;
1323
1324         /* Free a linked list of structures. */
1325         while ((p = head)) {
1326                 head = head->fts_link;
1327                 free(p);
1328         }
1329 }
1330
1331 /*
1332  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
1333  * Most systems will allow creation of paths much longer than MAXPATHLEN, even
1334  * though the kernel won't resolve them.  Add the size (not just what's needed)
1335  * plus 256 bytes so don't realloc the path 2 bytes at a time.
1336  */
1337 static bool
1338 internal_function
1339 fts_palloc (FTS *sp, size_t more)
1340 {
1341         char *p;
1342         size_t new_len = sp->fts_pathlen + more + 256;
1343
1344         /*
1345          * See if fts_pathlen would overflow.
1346          */
1347         if (new_len < sp->fts_pathlen) {
1348                 if (sp->fts_path) {
1349                         free(sp->fts_path);
1350                         sp->fts_path = NULL;
1351                 }
1352                 sp->fts_path = NULL;
1353                 __set_errno (ENAMETOOLONG);
1354                 return false;
1355         }
1356         sp->fts_pathlen = new_len;
1357         p = realloc(sp->fts_path, sp->fts_pathlen);
1358         if (p == NULL) {
1359                 free(sp->fts_path);
1360                 sp->fts_path = NULL;
1361                 return false;
1362         }
1363         sp->fts_path = p;
1364         return true;
1365 }
1366
1367 /*
1368  * When the path is realloc'd, have to fix all of the pointers in structures
1369  * already returned.
1370  */
1371 static void
1372 internal_function
1373 fts_padjust (FTS *sp, FTSENT *head)
1374 {
1375         FTSENT *p;
1376         char *addr = sp->fts_path;
1377
1378 #define ADJUST(p) do {                                                  \
1379         if ((p)->fts_accpath != (p)->fts_name) {                        \
1380                 (p)->fts_accpath =                                      \
1381                     (char *)addr + ((p)->fts_accpath - (p)->fts_path);  \
1382         }                                                               \
1383         (p)->fts_path = addr;                                           \
1384 } while (0)
1385         /* Adjust the current set of children. */
1386         for (p = sp->fts_child; p; p = p->fts_link)
1387                 ADJUST(p);
1388
1389         /* Adjust the rest of the tree, including the current level. */
1390         for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1391                 ADJUST(p);
1392                 p = p->fts_link ? p->fts_link : p->fts_parent;
1393         }
1394 }
1395
1396 static size_t
1397 internal_function
1398 fts_maxarglen (char * const *argv)
1399 {
1400         size_t len, max;
1401
1402         for (max = 0; *argv; ++argv)
1403                 if ((len = strlen(*argv)) > max)
1404                         max = len;
1405         return (max + 1);
1406 }
1407
1408 /*
1409  * Change to dir specified by fd or path without getting
1410  * tricked by someone changing the world out from underneath us.
1411  * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1412  */
1413 static int
1414 internal_function
1415 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *path)
1416 {
1417         int ret, oerrno, newfd;
1418         struct stat sb;
1419
1420         newfd = fd;
1421         if (ISSET(FTS_NOCHDIR))
1422                 return (0);
1423         if (fd < 0 && (newfd = fd_safer (diropen (path))) < 0)
1424                 return (-1);
1425         if (fstat(newfd, &sb)) {
1426                 ret = -1;
1427                 goto bail;
1428         }
1429         if (p->fts_statp->st_dev != sb.st_dev
1430             || p->fts_statp->st_ino != sb.st_ino) {
1431                 __set_errno (ENOENT);           /* disinformation */
1432                 ret = -1;
1433                 goto bail;
1434         }
1435         ret = fchdir(newfd);
1436 bail:
1437         oerrno = errno;
1438         if (fd < 0)
1439                 (void)close(newfd);
1440         __set_errno (oerrno);
1441         return (ret);
1442 }