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