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 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         free(sp->fts_array);
 463         free(sp->fts_path);
 464
 465         if (ISSET(FTS_CWDFD))
 466           {
 467             if (0 <= sp->fts_cwd_fd)
 468               close (sp->fts_cwd_fd);
 469           }
 470         else if (!ISSET(FTS_NOCHDIR))
 471           {
 472             /* Return to original directory, save errno if necessary. */
 473             if (fchdir(sp->fts_rfd))
 474               saved_errno = errno;
 475             close(sp->fts_rfd);
 476           }
 477
 478         free_dir (sp);
 479
 480         /* Free up the stream pointer. */
 481         free(sp);
 482
 483         /* Set errno and return. */
 484         if (saved_errno) {
 485                 __set_errno (saved_errno);
 486                 return (-1);
 487         }
 488
 489         return (0);
 490 }
 491
 492 /*
 493  * Special case of "/" at the end of the file name so that slashes aren't
 494  * appended which would cause file names to be written as "....//foo".
 495  */
 496 #define NAPPEND(p)                                                      \
 497         (p->fts_path[p->fts_pathlen - 1] == '/'                         \
 498             ? p->fts_pathlen - 1 : p->fts_pathlen)
 499
 500 FTSENT *
 501 fts_read (register FTS *sp)
 502 {
 503         register FTSENT *p, *tmp;
 504         register unsigned short int instr;
 505         register char *t;
 506
 507         /* If finished or unrecoverable error, return NULL. */
 508         if (sp->fts_cur == NULL || ISSET(FTS_STOP))
 509                 return (NULL);
 510
 511         /* Set current node pointer. */
 512         p = sp->fts_cur;
 513
 514         /* Save and zero out user instructions. */
 515         instr = p->fts_instr;
 516         p->fts_instr = FTS_NOINSTR;
 517
 518         /* Any type of file may be re-visited; re-stat and re-turn. */
 519         if (instr == FTS_AGAIN) {
 520                 p->fts_info = fts_stat(sp, p, false);
 521                 return (p);
 522         }
 523         Dprintf (("fts_read: p=%s\n",
 524                   p->fts_info == FTS_INIT ? "" : p->fts_path));
 525
 526         /*
 527          * Following a symlink -- SLNONE test allows application to see
 528          * SLNONE and recover.  If indirecting through a symlink, have
 529          * keep a pointer to current location.  If unable to get that
 530          * pointer, follow fails.
 531          */
 532         if (instr == FTS_FOLLOW &&
 533             (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
 534                 p->fts_info = fts_stat(sp, p, true);
 535                 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 536                         if ((p->fts_symfd = diropen (sp, ".")) < 0) {
 537                                 p->fts_errno = errno;
 538                                 p->fts_info = FTS_ERR;
 539                         } else
 540                                 p->fts_flags |= FTS_SYMFOLLOW;
 541                 }
 542                 goto check_for_dir;
 543         }
 544
 545         /* Directory in pre-order. */
 546         if (p->fts_info == FTS_D) {
 547                 /* If skipped or crossed mount point, do post-order visit. */
 548                 if (instr == FTS_SKIP ||
 549                     (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
 550                         if (p->fts_flags & FTS_SYMFOLLOW)
 551                                 (void)close(p->fts_symfd);
 552                         if (sp->fts_child) {
 553                                 fts_lfree(sp->fts_child);
 554                                 sp->fts_child = NULL;
 555                         }
 556                         p->fts_info = FTS_DP;
 557                         LEAVE_DIR (sp, p, "1");
 558                         return (p);
 559                 }
 560
 561                 /* Rebuild if only read the names and now traversing. */
 562                 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
 563                         CLR(FTS_NAMEONLY);
 564                         fts_lfree(sp->fts_child);
 565                         sp->fts_child = NULL;
 566                 }
 567
 568                 /*
 569                  * Cd to the subdirectory.
 570                  *
 571                  * If have already read and now fail to chdir, whack the list
 572                  * to make the names come out right, and set the parent errno
 573                  * so the application will eventually get an error condition.
 574                  * Set the FTS_DONTCHDIR flag so that when we logically change
 575                  * directories back to the parent we don't do a chdir.
 576                  *
 577                  * If haven't read do so.  If the read fails, fts_build sets
 578                  * FTS_STOP or the fts_info field of the node.
 579                  */
 580                 if (sp->fts_child != NULL) {
 581                         if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
 582                                 p->fts_errno = errno;
 583                                 p->fts_flags |= FTS_DONTCHDIR;
 584                                 for (p = sp->fts_child; p != NULL;
 585                                      p = p->fts_link)
 586                                         p->fts_accpath =
 587                                             p->fts_parent->fts_accpath;
 588                         }
 589                 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
 590                         if (ISSET(FTS_STOP))
 591                                 return (NULL);
 592                         /* If fts_build's call to fts_safe_changedir failed
 593                            because it was not able to fchdir into a
 594                            subdirectory, tell the caller.  */
 595                         if (p->fts_errno)
 596                                 p->fts_info = FTS_ERR;
 597                         LEAVE_DIR (sp, p, "2");
 598                         return (p);
 599                 }
 600                 p = sp->fts_child;
 601                 sp->fts_child = NULL;
 602                 goto name;
 603         }
 604
 605         /* Move to the next node on this level. */
 606 next:   tmp = p;
 607         if ((p = p->fts_link) != NULL) {
 608                 free(tmp);
 609
 610                 /*
 611                  * If reached the top, return to the original directory (or
 612                  * the root of the tree), and load the file names for the next
 613                  * root.
 614                  */
 615                 if (p->fts_level == FTS_ROOTLEVEL) {
 616                         if (RESTORE_INITIAL_CWD(sp)) {
 617                                 SET(FTS_STOP);
 618                                 sp->fts_cur = p;
 619                                 return (NULL);
 620                         }
 621                         fts_load(sp, p);
 622                         goto check_for_dir;
 623                 }
 624
 625                 /*
 626                  * User may have called fts_set on the node.  If skipped,
 627                  * ignore.  If followed, get a file descriptor so we can
 628                  * get back if necessary.
 629                  */
 630                 if (p->fts_instr == FTS_SKIP)
 631                         goto next;
 632                 if (p->fts_instr == FTS_FOLLOW) {
 633                         p->fts_info = fts_stat(sp, p, true);
 634                         if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 635                                 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
 636                                         p->fts_errno = errno;
 637                                         p->fts_info = FTS_ERR;
 638                                 } else
 639                                         p->fts_flags |= FTS_SYMFOLLOW;
 640                         }
 641                         p->fts_instr = FTS_NOINSTR;
 642                 }
 643
 644 name:           t = sp->fts_path + NAPPEND(p->fts_parent);
 645                 *t++ = '/';
 646                 memmove(t, p->fts_name, p->fts_namelen + 1);
 647 check_for_dir:
 648                 sp->fts_cur = p;
 649                 if (p->fts_info == FTS_D)
 650                   {
 651                     Dprintf (("  %s-entering: %s\n", sp, p->fts_path));
 652                     if (! enter_dir (sp, p))
 653                       {
 654                         __set_errno (ENOMEM);
 655                         return NULL;
 656                       }
 657                   }
 658                 return p;
 659         }
 660
 661         /* Move up to the parent node. */
 662         p = tmp->fts_parent;
 663         free(tmp);
 664
 665         if (p->fts_level == FTS_ROOTPARENTLEVEL) {
 666                 /*
 667                  * Done; free everything up and set errno to 0 so the user
 668                  * can distinguish between error and EOF.
 669                  */
 670                 free(p);
 671                 __set_errno (0);
 672                 return (sp->fts_cur = NULL);
 673         }
 674
 675         /* NUL terminate the file name.  */
 676         sp->fts_path[p->fts_pathlen] = '\0';
 677
 678         /*
 679          * Return to the parent directory.  If at a root node, restore
 680          * the initial working directory.  If we came through a symlink,
 681          * go back through the file descriptor.  Otherwise, move up
 682          * one level, via "..".
 683          */
 684         if (p->fts_level == FTS_ROOTLEVEL) {
 685                 if (RESTORE_INITIAL_CWD(sp)) {
 686                         p->fts_errno = errno;
 687                         SET(FTS_STOP);
 688                 }
 689         } else if (p->fts_flags & FTS_SYMFOLLOW) {
 690                 if (FCHDIR(sp, p->fts_symfd)) {
 691                         int saved_errno = errno;
 692                         (void)close(p->fts_symfd);
 693                         __set_errno (saved_errno);
 694                         p->fts_errno = errno;
 695                         SET(FTS_STOP);
 696                 }
 697                 (void)close(p->fts_symfd);
 698         } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
 699                    fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
 700                 p->fts_errno = errno;
 701                 SET(FTS_STOP);
 702         }
 703         p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
 704         if (p->fts_errno == 0)
 705                 LEAVE_DIR (sp, p, "3");
 706         sp->fts_cur = p;
 707         return ISSET(FTS_STOP) ? NULL : p;
 708 }
 709
 710 /*
 711  * Fts_set takes the stream as an argument although it's not used in this
 712  * implementation; it would be necessary if anyone wanted to add global
 713  * semantics to fts using fts_set.  An error return is allowed for similar
 714  * reasons.
 715  */
 716 /* ARGSUSED */
 717 int
 718 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
 719 {
 720         if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
 721             instr != FTS_NOINSTR && instr != FTS_SKIP) {
 722                 __set_errno (EINVAL);
 723                 return (1);
 724         }
 725         p->fts_instr = instr;
 726         return (0);
 727 }
 728
 729 FTSENT *
 730 fts_children (register FTS *sp, int instr)
 731 {
 732         register FTSENT *p;
 733         int fd;
 734
 735         if (instr != 0 && instr != FTS_NAMEONLY) {
 736                 __set_errno (EINVAL);
 737                 return (NULL);
 738         }
 739
 740         /* Set current node pointer. */
 741         p = sp->fts_cur;
 742
 743         /*
 744          * Errno set to 0 so user can distinguish empty directory from
 745          * an error.
 746          */
 747         __set_errno (0);
 748
 749         /* Fatal errors stop here. */
 750         if (ISSET(FTS_STOP))
 751                 return (NULL);
 752
 753         /* Return logical hierarchy of user's arguments. */
 754         if (p->fts_info == FTS_INIT)
 755                 return (p->fts_link);
 756
 757         /*
 758          * If not a directory being visited in pre-order, stop here.  Could
 759          * allow FTS_DNR, assuming the user has fixed the problem, but the
 760          * same effect is available with FTS_AGAIN.
 761          */
 762         if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
 763                 return (NULL);
 764
 765         /* Free up any previous child list. */
 766         if (sp->fts_child != NULL)
 767                 fts_lfree(sp->fts_child);
 768
 769         if (instr == FTS_NAMEONLY) {
 770                 SET(FTS_NAMEONLY);
 771                 instr = BNAMES;
 772         } else
 773                 instr = BCHILD;
 774
 775         /*
 776          * If using chdir on a relative file name and called BEFORE fts_read
 777          * does its chdir to the root of a traversal, we can lose -- we need to
 778          * chdir into the subdirectory, and we don't know where the current
 779          * directory is, so we can't get back so that the upcoming chdir by
 780          * fts_read will work.
 781          */
 782         if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
 783             ISSET(FTS_NOCHDIR))
 784                 return (sp->fts_child = fts_build(sp, instr));
 785
 786         if ((fd = diropen (sp, ".")) < 0)
 787                 return (sp->fts_child = NULL);
 788         sp->fts_child = fts_build(sp, instr);
 789         if (ISSET(FTS_CWDFD))
 790           {
 791             cwd_advance_fd (sp, fd);
 792           }
 793         else
 794           {
 795             if (fchdir(fd))
 796               {
 797                 int saved_errno = errno;
 798                 close (fd);
 799                 __set_errno (saved_errno);
 800                 return NULL;
 801               }
 802             close (fd);
 803           }
 804         return (sp->fts_child);
 805 }
 806
 807 /*
 808  * This is the tricky part -- do not casually change *anything* in here.  The
 809  * idea is to build the linked list of entries that are used by fts_children
 810  * and fts_read.  There are lots of special cases.
 811  *
 812  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
 813  * set and it's a physical walk (so that symbolic links can't be directories),
 814  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
 815  * of the file is in the directory entry.  Otherwise, we assume that the number
 816  * of subdirectories in a node is equal to the number of links to the parent.
 817  * The former skips all stat calls.  The latter skips stat calls in any leaf
 818  * directories and for any files after the subdirectories in the directory have
 819  * been found, cutting the stat calls by about 2/3.
 820  */
 821 static FTSENT *
 822 internal_function
 823 fts_build (register FTS *sp, int type)
 824 {
 825         register struct dirent *dp;
 826         register FTSENT *p, *head;
 827         register size_t nitems;
 828         FTSENT *cur, *tail;
 829         DIR *dirp;
 830         void *oldaddr;
 831         int saved_errno;
 832         bool descend;
 833         bool doadjust;
 834         ptrdiff_t level;
 835         nlink_t nlinks;
 836         bool nostat;
 837         size_t len, maxlen, new_len;
 838         char *cp;
 839
 840         /* Set current node pointer. */
 841         cur = sp->fts_cur;
 842
 843         /*
 844          * Open the directory for reading.  If this fails, we're done.
 845          * If being called from fts_read, set the fts_info field.
 846          */
 847 #if defined FTS_WHITEOUT && 0
 848         if (ISSET(FTS_WHITEOUT))
 849                 oflag = DTF_NODUP|DTF_REWIND;
 850         else
 851                 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
 852 #else
 853 # define __opendir2(file, flag) \
 854         ( ! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
 855           ? opendirat(sp->fts_cwd_fd, file)        \
 856           : opendir(file))
 857 #endif
 858        if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
 859                 if (type == BREAD) {
 860                         cur->fts_info = FTS_DNR;
 861                         cur->fts_errno = errno;
 862                 }
 863                 return (NULL);
 864         }
 865
 866         /*
 867          * Nlinks is the number of possible entries of type directory in the
 868          * directory if we're cheating on stat calls, 0 if we're not doing
 869          * any stat calls at all, (nlink_t) -1 if we're statting everything.
 870          */
 871         if (type == BNAMES) {
 872                 nlinks = 0;
 873                 /* Be quiet about nostat, GCC. */
 874                 nostat = false;
 875         } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
 876                 nlinks = (cur->fts_statp->st_nlink
 877                           - (ISSET(FTS_SEEDOT) ? 0 : 2));
 878                 nostat = true;
 879         } else {
 880                 nlinks = -1;
 881                 nostat = false;
 882         }
 883
 884         /*
 885          * If we're going to need to stat anything or we want to descend
 886          * and stay in the directory, chdir.  If this fails we keep going,
 887          * but set a flag so we don't chdir after the post-order visit.
 888          * We won't be able to stat anything, but we can still return the
 889          * names themselves.  Note, that since fts_read won't be able to
 890          * chdir into the directory, it will have to return different file
 891          * names than before, i.e. "a/b" instead of "b".  Since the node
 892          * has already been visited in pre-order, have to wait until the
 893          * post-order visit to return the error.  There is a special case
 894          * here, if there was nothing to stat then it's not an error to
 895          * not be able to stat.  This is all fairly nasty.  If a program
 896          * needed sorted entries or stat information, they had better be
 897          * checking FTS_NS on the returned nodes.
 898          */
 899         if (nlinks || type == BREAD) {
 900                 int dir_fd = dirfd(dirp);
 901                 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
 902                   dir_fd = dup (dir_fd);
 903                 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
 904                         if (nlinks && type == BREAD)
 905                                 cur->fts_errno = errno;
 906                         cur->fts_flags |= FTS_DONTCHDIR;
 907                         descend = false;
 908                         closedir(dirp);
 909                         if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
 910                                 close (dir_fd);
 911                         dirp = NULL;
 912                 } else
 913                         descend = true;
 914         } else
 915                 descend = false;
 916
 917         /*
 918          * Figure out the max file name length that can be stored in the
 919          * current buffer -- the inner loop allocates more space as necessary.
 920          * We really wouldn't have to do the maxlen calculations here, we
 921          * could do them in fts_read before returning the name, but it's a
 922          * lot easier here since the length is part of the dirent structure.
 923          *
 924          * If not changing directories set a pointer so that can just append
 925          * each new component into the file name.
 926          */
 927         len = NAPPEND(cur);
 928         if (ISSET(FTS_NOCHDIR)) {
 929                 cp = sp->fts_path + len;
 930                 *cp++ = '/';
 931         } else {
 932                 /* GCC, you're too verbose. */
 933                 cp = NULL;
 934         }
 935         len++;
 936         maxlen = sp->fts_pathlen - len;
 937
 938         level = cur->fts_level + 1;
 939
 940         /* Read the directory, attaching each entry to the `link' pointer. */
 941         doadjust = false;
 942         for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
 943                 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
 944                         continue;
 945
 946                 if ((p = fts_alloc (sp, dp->d_name,
 947                                     _D_EXACT_NAMLEN (dp))) == NULL)
 948                         goto mem1;
 949                 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
 950                         /* include space for NUL */
 951                         oldaddr = sp->fts_path;
 952                         if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
 953                                 /*
 954                                  * No more memory.  Save
 955                                  * errno, free up the current structure and the
 956                                  * structures already allocated.
 957                                  */
 958 mem1:                           saved_errno = errno;
 959                                 free(p);
 960                                 fts_lfree(head);
 961                                 closedir(dirp);
 962                                 cur->fts_info = FTS_ERR;
 963                                 SET(FTS_STOP);
 964                                 __set_errno (saved_errno);
 965                                 return (NULL);
 966                         }
 967                         /* Did realloc() change the pointer? */
 968                         if (oldaddr != sp->fts_path) {
 969                                 doadjust = true;
 970                                 if (ISSET(FTS_NOCHDIR))
 971                                         cp = sp->fts_path + len;
 972                         }
 973                         maxlen = sp->fts_pathlen - len;
 974                 }
 975
 976                 new_len = len + _D_EXACT_NAMLEN (dp);
 977                 if (new_len < len) {
 978                         /*
 979                          * In the unlikely even that we would end up
 980                          * with a file name longer than SIZE_MAX, free up
 981                          * the current structure and the structures already
 982                          * allocated, then error out with ENAMETOOLONG.
 983                          */
 984                         free(p);
 985                         fts_lfree(head);
 986                         closedir(dirp);
 987                         cur->fts_info = FTS_ERR;
 988                         SET(FTS_STOP);
 989                         __set_errno (ENAMETOOLONG);
 990                         return (NULL);
 991                 }
 992                 p->fts_level = level;
 993                 p->fts_parent = sp->fts_cur;
 994                 p->fts_pathlen = new_len;
 995
 996 #if defined FTS_WHITEOUT && 0
 997                 if (dp->d_type == DT_WHT)
 998                         p->fts_flags |= FTS_ISW;
 999 #endif
1000
1001                 /* Build a file name for fts_stat to stat. */
1002                 if (ISSET(FTS_NOCHDIR)) {
1003                         p->fts_accpath = p->fts_path;
1004                         memmove(cp, p->fts_name, p->fts_namelen + 1);
1005                 } else
1006                         p->fts_accpath = p->fts_name;
1007                 /* Stat it. */
1008                 p->fts_info = fts_stat(sp, p, false);
1009
1010                 /* Decrement link count if applicable. */
1011                 if (nlinks > 0 && (p->fts_info == FTS_D ||
1012                     p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
1013                         nlinks -= nostat;
1014
1015                 /* We walk in directory order so "ls -f" doesn't get upset. */
1016                 p->fts_link = NULL;
1017                 if (head == NULL)
1018                         head = tail = p;
1019                 else {
1020                         tail->fts_link = p;
1021                         tail = p;
1022                 }
1023                 ++nitems;
1024         }
1025         if (dirp)
1026                 closedir(dirp);
1027
1028         /*
1029          * If realloc() changed the address of the file name, adjust the
1030          * addresses for the rest of the tree and the dir list.
1031          */
1032         if (doadjust)
1033                 fts_padjust(sp, head);
1034
1035         /*
1036          * If not changing directories, reset the file name back to original
1037          * state.
1038          */
1039         if (ISSET(FTS_NOCHDIR)) {
1040                 if (len == sp->fts_pathlen || nitems == 0)
1041                         --cp;
1042                 *cp = '\0';
1043         }
1044
1045         /*
1046          * If descended after called from fts_children or after called from
1047          * fts_read and nothing found, get back.  At the root level we use
1048          * the saved fd; if one of fts_open()'s arguments is a relative name
1049          * to an empty directory, we wind up here with no other way back.  If
1050          * can't get back, we're done.
1051          */
1052         if (descend && (type == BCHILD || !nitems) &&
1053             (cur->fts_level == FTS_ROOTLEVEL
1054              ? RESTORE_INITIAL_CWD(sp)
1055              : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1056                 cur->fts_info = FTS_ERR;
1057                 SET(FTS_STOP);
1058                 fts_lfree(head);
1059                 return (NULL);
1060         }
1061
1062         /* If didn't find anything, return NULL. */
1063         if (!nitems) {
1064                 if (type == BREAD)
1065                         cur->fts_info = FTS_DP;
1066                 fts_lfree(head);
1067                 return (NULL);
1068         }
1069
1070         /* Sort the entries. */
1071         if (sp->fts_compar && nitems > 1)
1072                 head = fts_sort(sp, head, nitems);
1073         return (head);
1074 }
1075
1076 #if FTS_DEBUG
1077
1078 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1079    current hierarchy.  There should be a directory with dev/inode
1080    matching those of AD.  If not, print a lot of diagnostics.  */
1081 static void
1082 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1083 {
1084   FTSENT const *ent;
1085   for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1086     {
1087       if (ad->ino == ent->fts_statp->st_ino
1088           && ad->dev == ent->fts_statp->st_dev)
1089         return;
1090     }
1091   printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1092   printf ("active dirs:\n");
1093   for (ent = e_curr;
1094        ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1095     printf ("  %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1096             ad->fts_ent->fts_accpath,
1097             (uintmax_t) ad->dev,
1098             (uintmax_t) ad->ino,
1099             ent->fts_accpath,
1100             (uintmax_t) ent->fts_statp->st_dev,
1101             (uintmax_t) ent->fts_statp->st_ino);
1102 }
1103
1104 void
1105 fts_cross_check (FTS const *sp)
1106 {
1107   FTSENT const *ent = sp->fts_cur;
1108   FTSENT const *t;
1109   if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1110     return;
1111
1112   Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1113   /* Make sure every parent dir is in the tree.  */
1114   for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1115     {
1116       struct Active_dir ad;
1117       ad.ino = t->fts_statp->st_ino;
1118       ad.dev = t->fts_statp->st_dev;
1119       if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1120         printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1121     }
1122
1123   /* Make sure every dir in the tree is an active dir.
1124      But ENT is not necessarily a directory.  If so, just skip this part. */
1125   if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1126       && (ent->fts_info == FTS_DP
1127           || ent->fts_info == FTS_D))
1128     {
1129       struct Active_dir *ad;
1130       for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1131            ad = hash_get_next (sp->fts_cycle.ht, ad))
1132         {
1133           find_matching_ancestor (ent, ad);
1134         }
1135     }
1136 }
1137 #endif
1138
1139 static unsigned short int
1140 internal_function
1141 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1142 {
1143         struct stat *sbp = p->fts_statp;
1144         int saved_errno;
1145
1146 #if defined FTS_WHITEOUT && 0
1147         /* check for whiteout */
1148         if (p->fts_flags & FTS_ISW) {
1149                 memset(sbp, '\0', sizeof (*sbp));
1150                 sbp->st_mode = S_IFWHT;
1151                 return (FTS_W);
1152        }
1153 #endif
1154
1155         /*
1156          * If doing a logical walk, or application requested FTS_FOLLOW, do
1157          * a stat(2).  If that fails, check for a non-existent symlink.  If
1158          * fail, set the errno from the stat call.
1159          */
1160         if (ISSET(FTS_LOGICAL) || follow) {
1161                 if (stat(p->fts_accpath, sbp)) {
1162                         saved_errno = errno;
1163                         if (errno == ENOENT
1164                             && lstat(p->fts_accpath, sbp) == 0) {
1165                                 __set_errno (0);
1166                                 return (FTS_SLNONE);
1167                         }
1168                         p->fts_errno = saved_errno;
1169                         goto err;
1170                 }
1171         } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp,
1172                            AT_SYMLINK_NOFOLLOW)) {
1173                 p->fts_errno = errno;
1174 err:            memset(sbp, 0, sizeof(struct stat));
1175                 return (FTS_NS);
1176         }
1177
1178         if (S_ISDIR(sbp->st_mode)) {
1179                 if (ISDOT(p->fts_name))
1180                         return (FTS_DOT);
1181
1182 #if _LGPL_PACKAGE
1183                 {
1184                   /*
1185                    * Cycle detection is done by brute force when the directory
1186                    * is first encountered.  If the tree gets deep enough or the
1187                    * number of symbolic links to directories is high enough,
1188                    * something faster might be worthwhile.
1189                    */
1190                   FTSENT *t;
1191
1192                   for (t = p->fts_parent;
1193                        t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1194                     if (sbp->st_ino == t->fts_statp->st_ino
1195                         && sbp->st_dev == t->fts_statp->st_dev)
1196                       {
1197                         p->fts_cycle = t;
1198                         return (FTS_DC);
1199                       }
1200                 }
1201 #endif
1202
1203                 return (FTS_D);
1204         }
1205         if (S_ISLNK(sbp->st_mode))
1206                 return (FTS_SL);
1207         if (S_ISREG(sbp->st_mode))
1208                 return (FTS_F);
1209         return (FTS_DEFAULT);
1210 }
1211
1212 static int
1213 fts_compar (void const *a, void const *b)
1214 {
1215   /* Convert A and B to the correct types, to pacify the compiler, and
1216      for portability to bizarre hosts where "void const *" and "FTSENT
1217      const **" differ in runtime representation.  The comparison
1218      function cannot modify *a and *b, but there is no compile-time
1219      check for this.  */
1220   FTSENT const **pa = (FTSENT const **) a;
1221   FTSENT const **pb = (FTSENT const **) b;
1222   return pa[0]->fts_fts->fts_compar (pa, pb);
1223 }
1224
1225 static FTSENT *
1226 internal_function
1227 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1228 {
1229         register FTSENT **ap, *p;
1230
1231         /* On most modern hosts, void * and FTSENT ** have the same
1232            run-time representation, and one can convert sp->fts_compar to
1233            the type qsort expects without problem.  Use the heuristic that
1234            this is OK if the two pointer types are the same size, and if
1235            converting FTSENT ** to long int is the same as converting
1236            FTSENT ** to void * and then to long int.  This heuristic isn't
1237            valid in general but we don't know of any counterexamples.  */
1238         FTSENT *dummy;
1239         int (*compare) (void const *, void const *) =
1240           ((sizeof &dummy == sizeof (void *)
1241             && (long int) &dummy == (long int) (void *) &dummy)
1242            ? (int (*) (void const *, void const *)) sp->fts_compar
1243            : fts_compar);
1244
1245         /*
1246          * Construct an array of pointers to the structures and call qsort(3).
1247          * Reassemble the array in the order returned by qsort.  If unable to
1248          * sort for memory reasons, return the directory entries in their
1249          * current order.  Allocate enough space for the current needs plus
1250          * 40 so don't realloc one entry at a time.
1251          */
1252         if (nitems > sp->fts_nitems) {
1253                 struct _ftsent **a;
1254
1255                 sp->fts_nitems = nitems + 40;
1256                 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1257                     || ! (a = realloc (sp->fts_array,
1258                                        sp->fts_nitems * sizeof *a))) {
1259                         free(sp->fts_array);
1260                         sp->fts_array = NULL;
1261                         sp->fts_nitems = 0;
1262                         return (head);
1263                 }
1264                 sp->fts_array = a;
1265         }
1266         for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1267                 *ap++ = p;
1268         qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1269         for (head = *(ap = sp->fts_array); --nitems; ++ap)
1270                 ap[0]->fts_link = ap[1];
1271         ap[0]->fts_link = NULL;
1272         return (head);
1273 }
1274
1275 static FTSENT *
1276 internal_function
1277 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1278 {
1279         register FTSENT *p;
1280         size_t len;
1281
1282         /*
1283          * The file name is a variable length array.  Allocate the FTSENT
1284          * structure and the file name in one chunk.
1285          */
1286         len = sizeof(FTSENT) + namelen;
1287         if ((p = malloc(len)) == NULL)
1288                 return (NULL);
1289
1290         /* Copy the name and guarantee NUL termination. */
1291         memmove(p->fts_name, name, namelen);
1292         p->fts_name[namelen] = '\0';
1293
1294         p->fts_namelen = namelen;
1295         p->fts_fts = sp;
1296         p->fts_path = sp->fts_path;
1297         p->fts_errno = 0;
1298         p->fts_flags = 0;
1299         p->fts_instr = FTS_NOINSTR;
1300         p->fts_number = 0;
1301         p->fts_pointer = NULL;
1302         return (p);
1303 }
1304
1305 static void
1306 internal_function
1307 fts_lfree (register FTSENT *head)
1308 {
1309         register FTSENT *p;
1310
1311         /* Free a linked list of structures. */
1312         while ((p = head)) {
1313                 head = head->fts_link;
1314                 free(p);
1315         }
1316 }
1317
1318 /*
1319  * Allow essentially unlimited file name lengths; find, rm, ls should
1320  * all work on any tree.  Most systems will allow creation of file
1321  * names much longer than MAXPATHLEN, even though the kernel won't
1322  * resolve them.  Add the size (not just what's needed) plus 256 bytes
1323  * so don't realloc the file name 2 bytes at a time.
1324  */
1325 static bool
1326 internal_function
1327 fts_palloc (FTS *sp, size_t more)
1328 {
1329         char *p;
1330         size_t new_len = sp->fts_pathlen + more + 256;
1331
1332         /*
1333          * See if fts_pathlen would overflow.
1334          */
1335         if (new_len < sp->fts_pathlen) {
1336                 free(sp->fts_path);
1337                 sp->fts_path = NULL;
1338                 __set_errno (ENAMETOOLONG);
1339                 return false;
1340         }
1341         sp->fts_pathlen = new_len;
1342         p = realloc(sp->fts_path, sp->fts_pathlen);
1343         if (p == NULL) {
1344                 free(sp->fts_path);
1345                 sp->fts_path = NULL;
1346                 return false;
1347         }
1348         sp->fts_path = p;
1349         return true;
1350 }
1351
1352 /*
1353  * When the file name is realloc'd, have to fix all of the pointers in
1354  *  structures already returned.
1355  */
1356 static void
1357 internal_function
1358 fts_padjust (FTS *sp, FTSENT *head)
1359 {
1360         FTSENT *p;
1361         char *addr = sp->fts_path;
1362
1363 #define ADJUST(p) do {                                                  \
1364         if ((p)->fts_accpath != (p)->fts_name) {                        \
1365                 (p)->fts_accpath =                                      \
1366                     (char *)addr + ((p)->fts_accpath - (p)->fts_path);  \
1367         }                                                               \
1368         (p)->fts_path = addr;                                           \
1369 } while (0)
1370         /* Adjust the current set of children. */
1371         for (p = sp->fts_child; p; p = p->fts_link)
1372                 ADJUST(p);
1373
1374         /* Adjust the rest of the tree, including the current level. */
1375         for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1376                 ADJUST(p);
1377                 p = p->fts_link ? p->fts_link : p->fts_parent;
1378         }
1379 }
1380
1381 static size_t
1382 internal_function
1383 fts_maxarglen (char * const *argv)
1384 {
1385         size_t len, max;
1386
1387         for (max = 0; *argv; ++argv)
1388                 if ((len = strlen(*argv)) > max)
1389                         max = len;
1390         return (max + 1);
1391 }
1392
1393 /*
1394  * Change to dir specified by fd or file name without getting
1395  * tricked by someone changing the world out from underneath us.
1396  * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1397  * If FD is non-negative, expect it to be used after this function returns,
1398  * and to be closed eventually.  So don't pass e.g., `dirfd(dirp)' and then
1399  * do closedir(dirp), because that would invalidate the saved FD.
1400  * Upon failure, close FD immediately and return nonzero.
1401  */
1402 static int
1403 internal_function
1404 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1405 {
1406         int ret;
1407
1408         int newfd = fd;
1409         if (ISSET(FTS_NOCHDIR)) {
1410                 if (ISSET(FTS_CWDFD) && 0 <= fd)
1411                         close (fd);
1412                 return (0);
1413         }
1414         if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
1415                 return (-1);
1416
1417         /* The following dev/inode check is necessary if we're doing
1418            a `logical' traversal (through symlinks, a la chown -L),
1419            if the system lacks O_NOFOLLOW support, or if we're changing
1420            to "..".  In the latter case, O_NOFOLLOW can't help.  In
1421            general (when the target is not ".."), diropen's use of
1422            O_NOFOLLOW ensures we don't mistakenly follow a symlink,
1423            so we can avoid the expense of this fstat.  */
1424         if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
1425             || (dir && STREQ (dir, "..")))
1426           {
1427             struct stat sb;
1428             if (fstat(newfd, &sb))
1429               {
1430                 ret = -1;
1431                 goto bail;
1432               }
1433             if (p->fts_statp->st_dev != sb.st_dev
1434                 || p->fts_statp->st_ino != sb.st_ino)
1435               {
1436                 __set_errno (ENOENT);           /* disinformation */
1437                 ret = -1;
1438                 goto bail;
1439               }
1440           }
1441
1442         if (ISSET(FTS_CWDFD))
1443           {
1444             cwd_advance_fd (sp, newfd);
1445             return 0;
1446           }
1447
1448         ret = fchdir(newfd);
1449 bail:
1450         if (fd < 0)
1451           {
1452             int oerrno = errno;
1453             (void)close(newfd);
1454             __set_errno (oerrno);
1455           }
1456         return (ret);
1457 }