lib/fts.c

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