lib/fts.c

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