lib/libc/gen/fts.c

   1 /*-
   2  * Copyright (c) 1990, 1993, 1994
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. All advertising materials mentioning features or use of this software
  14  *    must display the following acknowledgement:
  15  *      This product includes software developed by the University of
  16  *      California, Berkeley and its contributors.
  17  * 4. Neither the name of the University nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  *
  33  * $OpenBSD: fts.c,v 1.22 1999/10/03 19:22:22 millert Exp $
  34  *
  35  * $FreeBSD: src/lib/libc/gen/fts.c,v 1.14.2.4 2001/06/01 22:00:34 kris Exp $
  36  * $DragonFly: src/lib/libc/gen/fts.c,v 1.7 2005/11/13 00:07:42 swildner Exp $
  37  *
  38  * @(#)fts.c    8.6 (Berkeley) 8/14/94
  39  * $FreeBSD: src/lib/libc/gen/fts.c,v 1.14.2.4 2001/06/01 22:00:34 kris Exp $
  40  */
  41
  42 #include "namespace.h"
  43 #include <sys/param.h>
  44 #include <sys/stat.h>
  45
  46 #include <dirent.h>
  47 #include <errno.h>
  48 #include <fcntl.h>
  49 #include <fts.h>
  50 #include <stdlib.h>
  51 #include <string.h>
  52 #include <unistd.h>
  53 #include "un-namespace.h"
  54
  55 static FTSENT   *fts_alloc(FTS *, const char *, int);
  56 static FTSENT   *fts_build(FTS *, int);
  57 static void      fts_lfree(FTSENT *);
  58 static void      fts_load(FTS *, FTSENT *);
  59 static size_t    fts_maxarglen(char * const *);
  60 static void      fts_padjust(FTS *, FTSENT *);
  61 static int       fts_palloc(FTS *, size_t);
  62 static FTSENT   *fts_sort(FTS *, FTSENT *, int);
  63 static u_short   fts_stat(FTS *, FTSENT *, int);
  64 static int       fts_safe_changedir(FTS *, FTSENT *, int, const char *);
  65
  66 #define ISDOT(a)        (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
  67
  68 #define CLR(opt)        (sp->fts_options &= ~(opt))
  69 #define ISSET(opt)      (sp->fts_options & (opt))
  70 #define SET(opt)        (sp->fts_options |= (opt))
  71
  72 #define FCHDIR(sp, fd)  (!ISSET(FTS_NOCHDIR) && fchdir(fd))
  73
  74 /* fts_build flags */
  75 #define BCHILD          1               /* fts_children */
  76 #define BNAMES          2               /* fts_children, names only */
  77 #define BREAD           3               /* fts_read */
  78
  79 FTS *
  80 fts_open(char * const *argv, int options,
  81          int (*compar)(const FTSENT **, const FTSENT **))
  82 {
  83         FTS *sp;
  84         FTSENT *p, *root;
  85         FTSENT *parent, *tmp;
  86         size_t len, nitems;
  87
  88         /* Options check. */
  89         if (options & ~FTS_OPTIONMASK) {
  90                 errno = EINVAL;
  91                 return (NULL);
  92         }
  93
  94         /* Allocate/initialize the stream */
  95         if ((sp = malloc((u_int)sizeof(FTS))) == NULL)
  96                 return (NULL);
  97         memset(sp, 0, sizeof(FTS));
  98         sp->fts_compar = compar;
  99         sp->fts_options = options;
 100
 101         /* Shush, GCC. */
 102         tmp = NULL;
 103
 104         /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
 105         if (ISSET(FTS_LOGICAL))
 106                 SET(FTS_NOCHDIR);
 107
 108         /*
 109          * Start out with 1K of path space, and enough, in any case,
 110          * to hold the user's paths.
 111          */
 112         if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
 113                 goto mem1;
 114
 115         /* Allocate/initialize root's parent. */
 116         if ((parent = fts_alloc(sp, "", 0)) == NULL)
 117                 goto mem2;
 118         parent->fts_level = FTS_ROOTPARENTLEVEL;
 119
 120         /* Allocate/initialize root(s). */
 121         for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
 122                 /* Don't allow zero-length paths. */
 123                 if ((len = strlen(*argv)) == 0) {
 124                         errno = ENOENT;
 125                         goto mem3;
 126                 }
 127
 128                 p = fts_alloc(sp, *argv, len);
 129                 p->fts_level = FTS_ROOTLEVEL;
 130                 p->fts_parent = parent;
 131                 p->fts_accpath = p->fts_name;
 132                 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));
 133
 134                 /* Command-line "." and ".." are real directories. */
 135                 if (p->fts_info == FTS_DOT)
 136                         p->fts_info = FTS_D;
 137
 138                 /*
 139                  * If comparison routine supplied, traverse in sorted
 140                  * order; otherwise traverse in the order specified.
 141                  */
 142                 if (compar) {
 143                         p->fts_link = root;
 144                         root = p;
 145                 } else {
 146                         p->fts_link = NULL;
 147                         if (root == NULL)
 148                                 tmp = root = p;
 149                         else {
 150                                 tmp->fts_link = p;
 151                                 tmp = p;
 152                         }
 153                 }
 154         }
 155         if (compar && nitems > 1)
 156                 root = fts_sort(sp, root, nitems);
 157
 158         /*
 159          * Allocate a dummy pointer and make fts_read think that we've just
 160          * finished the node before the root(s); set p->fts_info to FTS_INIT
 161          * so that everything about the "current" node is ignored.
 162          */
 163         if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
 164                 goto mem3;
 165         sp->fts_cur->fts_link = root;
 166         sp->fts_cur->fts_info = FTS_INIT;
 167
 168         /*
 169          * If using chdir(2), grab a file descriptor pointing to dot to ensure
 170          * that we can get back here; this could be avoided for some paths,
 171          * but almost certainly not worth the effort.  Slashes, symbolic links,
 172          * and ".." are all fairly nasty problems.  Note, if we can't get the
 173          * descriptor we run anyway, just more slowly.
 174          */
 175         if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = _open(".", O_RDONLY, 0)) < 0)
 176                 SET(FTS_NOCHDIR);
 177
 178         return (sp);
 179
 180 mem3:   fts_lfree(root);
 181         free(parent);
 182 mem2:   free(sp->fts_path);
 183 mem1:   free(sp);
 184         return (NULL);
 185 }
 186
 187 static void
 188 fts_load(FTS *sp, FTSENT *p)
 189 {
 190         size_t len;
 191         char *cp;
 192
 193         /*
 194          * Load the stream structure for the next traversal.  Since we don't
 195          * actually enter the directory until after the preorder visit, set
 196          * the fts_accpath field specially so the chdir gets done to the right
 197          * place and the user can access the first node.  From fts_open it's
 198          * known that the path will fit.
 199          */
 200         len = p->fts_pathlen = p->fts_namelen;
 201         memmove(sp->fts_path, p->fts_name, len + 1);
 202         if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
 203                 len = strlen(++cp);
 204                 memmove(p->fts_name, cp, len + 1);
 205                 p->fts_namelen = len;
 206         }
 207         p->fts_accpath = p->fts_path = sp->fts_path;
 208         sp->fts_dev = p->fts_dev;
 209 }
 210
 211 int
 212 fts_close(FTS *sp)
 213 {
 214         FTSENT *freep, *p;
 215         int saved_errno;
 216
 217         /*
 218          * This still works if we haven't read anything -- the dummy structure
 219          * points to the root list, so we step through to the end of the root
 220          * list which has a valid parent pointer.
 221          */
 222         if (sp->fts_cur) {
 223                 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
 224                         freep = p;
 225                         p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
 226                         free(freep);
 227                 }
 228                 free(p);
 229         }
 230
 231         /* Free up child linked list, sort array, path buffer. */
 232         if (sp->fts_child)
 233                 fts_lfree(sp->fts_child);
 234         if (sp->fts_array)
 235                 free(sp->fts_array);
 236         free(sp->fts_path);
 237
 238         /* Return to original directory, save errno if necessary. */
 239         if (!ISSET(FTS_NOCHDIR)) {
 240                 saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
 241                 _close(sp->fts_rfd);
 242
 243                 /* Set errno and return. */
 244                 if (saved_errno != 0) {
 245                         /* Free up the stream pointer. */
 246                         free(sp);
 247                         errno = saved_errno;
 248                         return (-1);
 249                 }
 250         }
 251
 252         /* Free up the stream pointer. */
 253         free(sp);
 254         return (0);
 255 }
 256
 257 /*
 258  * Special case of "/" at the end of the path so that slashes aren't
 259  * appended which would cause paths to be written as "....//foo".
 260  */
 261 #define NAPPEND(p)                                                      \
 262         (p->fts_path[p->fts_pathlen - 1] == '/'                         \
 263             ? p->fts_pathlen - 1 : p->fts_pathlen)
 264
 265 FTSENT *
 266 fts_read(FTS *sp)
 267 {
 268         FTSENT *p, *tmp;
 269         int instr;
 270         char *t;
 271         int saved_errno;
 272
 273         /* If finished or unrecoverable error, return NULL. */
 274         if (sp->fts_cur == NULL || ISSET(FTS_STOP))
 275                 return (NULL);
 276
 277         /* Set current node pointer. */
 278         p = sp->fts_cur;
 279
 280         /* Save and zero out user instructions. */
 281         instr = p->fts_instr;
 282         p->fts_instr = FTS_NOINSTR;
 283
 284         /* Any type of file may be re-visited; re-stat and re-turn. */
 285         if (instr == FTS_AGAIN) {
 286                 p->fts_info = fts_stat(sp, p, 0);
 287                 return (p);
 288         }
 289
 290         /*
 291          * Following a symlink -- SLNONE test allows application to see
 292          * SLNONE and recover.  If indirecting through a symlink, have
 293          * keep a pointer to current location.  If unable to get that
 294          * pointer, follow fails.
 295          */
 296         if (instr == FTS_FOLLOW &&
 297             (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
 298                 p->fts_info = fts_stat(sp, p, 1);
 299                 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 300                         if ((p->fts_symfd = _open(".", O_RDONLY, 0)) < 0) {
 301                                 p->fts_errno = errno;
 302                                 p->fts_info = FTS_ERR;
 303                         } else
 304                                 p->fts_flags |= FTS_SYMFOLLOW;
 305                 }
 306                 return (p);
 307         }
 308
 309         /* Directory in pre-order. */
 310         if (p->fts_info == FTS_D) {
 311                 /* If skipped or crossed mount point, do post-order visit. */
 312                 if (instr == FTS_SKIP ||
 313                     (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
 314                         if (p->fts_flags & FTS_SYMFOLLOW)
 315                                 _close(p->fts_symfd);
 316                         if (sp->fts_child) {
 317                                 fts_lfree(sp->fts_child);
 318                                 sp->fts_child = NULL;
 319                         }
 320                         p->fts_info = FTS_DP;
 321                         return (p);
 322                 }
 323
 324                 /* Rebuild if only read the names and now traversing. */
 325                 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
 326                         CLR(FTS_NAMEONLY);
 327                         fts_lfree(sp->fts_child);
 328                         sp->fts_child = NULL;
 329                 }
 330
 331                 /*
 332                  * Cd to the subdirectory.
 333                  *
 334                  * If have already read and now fail to chdir, whack the list
 335                  * to make the names come out right, and set the parent errno
 336                  * so the application will eventually get an error condition.
 337                  * Set the FTS_DONTCHDIR flag so that when we logically change
 338                  * directories back to the parent we don't do a chdir.
 339                  *
 340                  * If haven't read do so.  If the read fails, fts_build sets
 341                  * FTS_STOP or the fts_info field of the node.
 342                  */
 343                 if (sp->fts_child != NULL) {
 344                         if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
 345                                 p->fts_errno = errno;
 346                                 p->fts_flags |= FTS_DONTCHDIR;
 347                                 for (p = sp->fts_child; p != NULL;
 348                                     p = p->fts_link)
 349                                         p->fts_accpath =
 350                                             p->fts_parent->fts_accpath;
 351                         }
 352                 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
 353                         if (ISSET(FTS_STOP))
 354                                 return (NULL);
 355                         return (p);
 356                 }
 357                 p = sp->fts_child;
 358                 sp->fts_child = NULL;
 359                 goto name;
 360         }
 361
 362         /* Move to the next node on this level. */
 363 next:   tmp = p;
 364         if ((p = p->fts_link) != NULL) {
 365                 free(tmp);
 366
 367                 /*
 368                  * If reached the top, return to the original directory (or
 369                  * the root of the tree), and load the paths for the next root.
 370                  */
 371                 if (p->fts_level == FTS_ROOTLEVEL) {
 372                         if (FCHDIR(sp, sp->fts_rfd)) {
 373                                 SET(FTS_STOP);
 374                                 return (NULL);
 375                         }
 376                         fts_load(sp, p);
 377                         return (sp->fts_cur = p);
 378                 }
 379
 380                 /*
 381                  * User may have called fts_set on the node.  If skipped,
 382                  * ignore.  If followed, get a file descriptor so we can
 383                  * get back if necessary.
 384                  */
 385                 if (p->fts_instr == FTS_SKIP)
 386                         goto next;
 387                 if (p->fts_instr == FTS_FOLLOW) {
 388                         p->fts_info = fts_stat(sp, p, 1);
 389                         if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 390                                 if ((p->fts_symfd =
 391                                     _open(".", O_RDONLY, 0)) < 0) {
 392                                         p->fts_errno = errno;
 393                                         p->fts_info = FTS_ERR;
 394                                 } else
 395                                         p->fts_flags |= FTS_SYMFOLLOW;
 396                         }
 397                         p->fts_instr = FTS_NOINSTR;
 398                 }
 399
 400 name:           t = sp->fts_path + NAPPEND(p->fts_parent);
 401                 *t++ = '/';
 402                 memmove(t, p->fts_name, p->fts_namelen + 1);
 403                 return (sp->fts_cur = p);
 404         }
 405
 406         /* Move up to the parent node. */
 407         p = tmp->fts_parent;
 408         free(tmp);
 409
 410         if (p->fts_level == FTS_ROOTPARENTLEVEL) {
 411                 /*
 412                  * Done; free everything up and set errno to 0 so the user
 413                  * can distinguish between error and EOF.
 414                  */
 415                 free(p);
 416                 errno = 0;
 417                 return (sp->fts_cur = NULL);
 418         }
 419
 420         /* NUL terminate the pathname. */
 421         sp->fts_path[p->fts_pathlen] = '\0';
 422
 423         /*
 424          * Return to the parent directory.  If at a root node or came through
 425          * a symlink, go back through the file descriptor.  Otherwise, cd up
 426          * one directory.
 427          */
 428         if (p->fts_level == FTS_ROOTLEVEL) {
 429                 if (FCHDIR(sp, sp->fts_rfd)) {
 430                         SET(FTS_STOP);
 431                         return (NULL);
 432                 }
 433         } else if (p->fts_flags & FTS_SYMFOLLOW) {
 434                 if (FCHDIR(sp, p->fts_symfd)) {
 435                         saved_errno = errno;
 436                         _close(p->fts_symfd);
 437                         errno = saved_errno;
 438                         SET(FTS_STOP);
 439                         return (NULL);
 440                 }
 441                 _close(p->fts_symfd);
 442         } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
 443                    fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
 444                 SET(FTS_STOP);
 445                 return (NULL);
 446         }
 447         p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
 448         return (sp->fts_cur = p);
 449 }
 450
 451 /*
 452  * Fts_set takes the stream as an argument although it's not used in this
 453  * implementation; it would be necessary if anyone wanted to add global
 454  * semantics to fts using fts_set.  An error return is allowed for similar
 455  * reasons.
 456  */
 457 /* ARGSUSED */
 458 int
 459 fts_set(FTS *sp __unused, FTSENT *p, int instr)
 460 {
 461         if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
 462             instr != FTS_NOINSTR && instr != FTS_SKIP) {
 463                 errno = EINVAL;
 464                 return (1);
 465         }
 466         p->fts_instr = instr;
 467         return (0);
 468 }
 469
 470 FTSENT *
 471 fts_children(FTS *sp, int instr)
 472 {
 473         FTSENT *p;
 474         int fd;
 475
 476         if (instr != 0 && instr != FTS_NAMEONLY) {
 477                 errno = EINVAL;
 478                 return (NULL);
 479         }
 480
 481         /* Set current node pointer. */
 482         p = sp->fts_cur;
 483
 484         /*
 485          * Errno set to 0 so user can distinguish empty directory from
 486          * an error.
 487          */
 488         errno = 0;
 489
 490         /* Fatal errors stop here. */
 491         if (ISSET(FTS_STOP))
 492                 return (NULL);
 493
 494         /* Return logical hierarchy of user's arguments. */
 495         if (p->fts_info == FTS_INIT)
 496                 return (p->fts_link);
 497
 498         /*
 499          * If not a directory being visited in pre-order, stop here.  Could
 500          * allow FTS_DNR, assuming the user has fixed the problem, but the
 501          * same effect is available with FTS_AGAIN.
 502          */
 503         if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
 504                 return (NULL);
 505
 506         /* Free up any previous child list. */
 507         if (sp->fts_child != NULL)
 508                 fts_lfree(sp->fts_child);
 509
 510         if (instr == FTS_NAMEONLY) {
 511                 SET(FTS_NAMEONLY);
 512                 instr = BNAMES;
 513         } else
 514                 instr = BCHILD;
 515
 516         /*
 517          * If using chdir on a relative path and called BEFORE fts_read does
 518          * its chdir to the root of a traversal, we can lose -- we need to
 519          * chdir into the subdirectory, and we don't know where the current
 520          * directory is, so we can't get back so that the upcoming chdir by
 521          * fts_read will work.
 522          */
 523         if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
 524             ISSET(FTS_NOCHDIR))
 525                 return (sp->fts_child = fts_build(sp, instr));
 526
 527         if ((fd = _open(".", O_RDONLY, 0)) < 0)
 528                 return (NULL);
 529         sp->fts_child = fts_build(sp, instr);
 530         if (fchdir(fd))
 531                 return (NULL);
 532         _close(fd);
 533         return (sp->fts_child);
 534 }
 535
 536 /*
 537  * This is the tricky part -- do not casually change *anything* in here.  The
 538  * idea is to build the linked list of entries that are used by fts_children
 539  * and fts_read.  There are lots of special cases.
 540  *
 541  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
 542  * set and it's a physical walk (so that symbolic links can't be directories),
 543  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
 544  * of the file is in the directory entry.  Otherwise, we assume that the number
 545  * of subdirectories in a node is equal to the number of links to the parent.
 546  * The former skips all stat calls.  The latter skips stat calls in any leaf
 547  * directories and for any files after the subdirectories in the directory have
 548  * been found, cutting the stat calls by about 2/3.
 549  */
 550 static FTSENT *
 551 fts_build(FTS *sp, int type)
 552 {
 553         struct dirent *dp;
 554         FTSENT *p, *head;
 555         int nitems;
 556         FTSENT *cur, *tail;
 557         DIR *dirp;
 558         void *oldaddr;
 559         int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno,
 560             nostat, doadjust;
 561         char *cp;
 562
 563         /* Set current node pointer. */
 564         cur = sp->fts_cur;
 565
 566         /*
 567          * Open the directory for reading.  If this fails, we're done.
 568          * If being called from fts_read, set the fts_info field.
 569          */
 570 #ifdef FTS_WHITEOUT
 571         if (ISSET(FTS_WHITEOUT))
 572                 oflag = DTF_NODUP|DTF_REWIND;
 573         else
 574                 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
 575 #else
 576 #define __opendir2(path, flag) opendir(path)
 577 #endif
 578         if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
 579                 if (type == BREAD) {
 580                         cur->fts_info = FTS_DNR;
 581                         cur->fts_errno = errno;
 582                 }
 583                 return (NULL);
 584         }
 585
 586         /*
 587          * Nlinks is the number of possible entries of type directory in the
 588          * directory if we're cheating on stat calls, 0 if we're not doing
 589          * any stat calls at all, -1 if we're doing stats on everything.
 590          */
 591         if (type == BNAMES) {
 592                 nlinks = 0;
 593                 /* Be quiet about nostat, GCC. */
 594                 nostat = 0;
 595         } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
 596                 nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
 597                 nostat = 1;
 598         } else {
 599                 nlinks = -1;
 600                 nostat = 0;
 601         }
 602
 603 #ifdef notdef
 604         printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
 605         printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
 606             ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
 607 #endif
 608         /*
 609          * If we're going to need to stat anything or we want to descend
 610          * and stay in the directory, chdir.  If this fails we keep going,
 611          * but set a flag so we don't chdir after the post-order visit.
 612          * We won't be able to stat anything, but we can still return the
 613          * names themselves.  Note, that since fts_read won't be able to
 614          * chdir into the directory, it will have to return different path
 615          * names than before, i.e. "a/b" instead of "b".  Since the node
 616          * has already been visited in pre-order, have to wait until the
 617          * post-order visit to return the error.  There is a special case
 618          * here, if there was nothing to stat then it's not an error to
 619          * not be able to stat.  This is all fairly nasty.  If a program
 620          * needed sorted entries or stat information, they had better be
 621          * checking FTS_NS on the returned nodes.
 622          */
 623         cderrno = 0;
 624         if (nlinks || type == BREAD) {
 625                 if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
 626                         if (nlinks && type == BREAD)
 627                                 cur->fts_errno = errno;
 628                         cur->fts_flags |= FTS_DONTCHDIR;
 629                         descend = 0;
 630                         cderrno = errno;
 631                         closedir(dirp);
 632                         dirp = NULL;
 633                 } else
 634                         descend = 1;
 635         } else
 636                 descend = 0;
 637
 638         /*
 639          * Figure out the max file name length that can be stored in the
 640          * current path -- the inner loop allocates more path as necessary.
 641          * We really wouldn't have to do the maxlen calculations here, we
 642          * could do them in fts_read before returning the path, but it's a
 643          * lot easier here since the length is part of the dirent structure.
 644          *
 645          * If not changing directories set a pointer so that can just append
 646          * each new name into the path.
 647          */
 648         len = NAPPEND(cur);
 649         if (ISSET(FTS_NOCHDIR)) {
 650                 cp = sp->fts_path + len;
 651                 *cp++ = '/';
 652         } else {
 653                 /* GCC, you're too verbose. */
 654                 cp = NULL;
 655         }
 656         len++;
 657         maxlen = sp->fts_pathlen - len;
 658
 659         level = cur->fts_level + 1;
 660
 661         /* Read the directory, attaching each entry to the `link' pointer. */
 662         doadjust = 0;
 663         for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
 664                 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
 665                         continue;
 666
 667                 if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL)
 668                         goto mem1;
 669                 if (dp->d_namlen >= maxlen) {   /* include space for NUL */
 670                         oldaddr = sp->fts_path;
 671                         if (fts_palloc(sp, dp->d_namlen + len + 1)) {
 672                                 /*
 673                                  * No more memory for path or structures.  Save
 674                                  * errno, free up the current structure and the
 675                                  * structures already allocated.
 676                                  */
 677 mem1:                           saved_errno = errno;
 678                                 if (p)
 679                                         free(p);
 680                                 fts_lfree(head);
 681                                 closedir(dirp);
 682                                 cur->fts_info = FTS_ERR;
 683                                 SET(FTS_STOP);
 684                                 errno = saved_errno;
 685                                 return (NULL);
 686                         }
 687                         /* Did realloc() change the pointer? */
 688                         if (oldaddr != sp->fts_path) {
 689                                 doadjust = 1;
 690                                 if (ISSET(FTS_NOCHDIR))
 691                                         cp = sp->fts_path + len;
 692                         }
 693                         maxlen = sp->fts_pathlen - len;
 694                 }
 695
 696                 if (len + dp->d_namlen >= USHRT_MAX) {
 697                         /*
 698                          * In an FTSENT, fts_pathlen is a u_short so it is
 699                          * possible to wraparound here.  If we do, free up
 700                          * the current structure and the structures already
 701                          * allocated, then error out with ENAMETOOLONG.
 702                          */
 703                         free(p);
 704                         fts_lfree(head);
 705                         closedir(dirp);
 706                         cur->fts_info = FTS_ERR;
 707                         SET(FTS_STOP);
 708                         errno = ENAMETOOLONG;
 709                         return (NULL);
 710                 }
 711                 p->fts_level = level;
 712                 p->fts_parent = sp->fts_cur;
 713                 p->fts_pathlen = len + dp->d_namlen;
 714
 715 #ifdef FTS_WHITEOUT
 716                 if (dp->d_type == DT_WHT)
 717                         p->fts_flags |= FTS_ISW;
 718 #endif
 719
 720                 if (cderrno) {
 721                         if (nlinks) {
 722                                 p->fts_info = FTS_NS;
 723                                 p->fts_errno = cderrno;
 724                         } else
 725                                 p->fts_info = FTS_NSOK;
 726                         p->fts_accpath = cur->fts_accpath;
 727                 } else if (nlinks == 0
 728 #ifdef DT_DIR
 729                     || (nostat &&
 730                     dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
 731 #endif
 732                     ) {
 733                         p->fts_accpath =
 734                             ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
 735                         p->fts_info = FTS_NSOK;
 736                 } else {
 737                         /* Build a file name for fts_stat to stat. */
 738                         if (ISSET(FTS_NOCHDIR)) {
 739                                 p->fts_accpath = p->fts_path;
 740                                 memmove(cp, p->fts_name, p->fts_namelen + 1);
 741                         } else
 742                                 p->fts_accpath = p->fts_name;
 743                         /* Stat it. */
 744                         p->fts_info = fts_stat(sp, p, 0);
 745
 746                         /* Decrement link count if applicable. */
 747                         if (nlinks > 0 && (p->fts_info == FTS_D ||
 748                             p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
 749                                 --nlinks;
 750                 }
 751
 752                 /* We walk in directory order so "ls -f" doesn't get upset. */
 753                 p->fts_link = NULL;
 754                 if (head == NULL)
 755                         head = tail = p;
 756                 else {
 757                         tail->fts_link = p;
 758                         tail = p;
 759                 }
 760                 ++nitems;
 761         }
 762         if (dirp)
 763                 closedir(dirp);
 764
 765         /*
 766          * If realloc() changed the address of the path, adjust the
 767          * addresses for the rest of the tree and the dir list.
 768          */
 769         if (doadjust)
 770                 fts_padjust(sp, head);
 771
 772         /*
 773          * If not changing directories, reset the path back to original
 774          * state.
 775          */
 776         if (ISSET(FTS_NOCHDIR)) {
 777                 if (len == sp->fts_pathlen || nitems == 0)
 778                         --cp;
 779                 *cp = '\0';
 780         }
 781
 782         /*
 783          * If descended after called from fts_children or after called from
 784          * fts_read and nothing found, get back.  At the root level we use
 785          * the saved fd; if one of fts_open()'s arguments is a relative path
 786          * to an empty directory, we wind up here with no other way back.  If
 787          * can't get back, we're done.
 788          */
 789         if (descend && (type == BCHILD || !nitems) &&
 790             (cur->fts_level == FTS_ROOTLEVEL ?
 791             FCHDIR(sp, sp->fts_rfd) :
 792             fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
 793                 cur->fts_info = FTS_ERR;
 794                 SET(FTS_STOP);
 795                 return (NULL);
 796         }
 797
 798         /* If didn't find anything, return NULL. */
 799         if (!nitems) {
 800                 if (type == BREAD)
 801                         cur->fts_info = FTS_DP;
 802                 return (NULL);
 803         }
 804
 805         /* Sort the entries. */
 806         if (sp->fts_compar && nitems > 1)
 807                 head = fts_sort(sp, head, nitems);
 808         return (head);
 809 }
 810
 811 static u_short
 812 fts_stat(FTS *sp, FTSENT *p, int follow)
 813 {
 814         FTSENT *t;
 815         dev_t dev;
 816         ino_t ino;
 817         struct stat *sbp, sb;
 818         int saved_errno;
 819
 820         /* If user needs stat info, stat buffer already allocated. */
 821         sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
 822
 823 #ifdef FTS_WHITEOUT
 824         /* check for whiteout */
 825         if (p->fts_flags & FTS_ISW) {
 826                 if (sbp != &sb) {
 827                         memset(sbp, '\0', sizeof (*sbp));
 828                         sbp->st_mode = S_IFWHT;
 829                 }
 830                 return (FTS_W);
 831         }
 832 #endif
 833
 834         /*
 835          * If doing a logical walk, or application requested FTS_FOLLOW, do
 836          * a stat(2).  If that fails, check for a non-existent symlink.  If
 837          * fail, set the errno from the stat call.
 838          */
 839         if (ISSET(FTS_LOGICAL) || follow) {
 840                 if (stat(p->fts_accpath, sbp)) {
 841                         saved_errno = errno;
 842                         if (!lstat(p->fts_accpath, sbp)) {
 843                                 errno = 0;
 844                                 return (FTS_SLNONE);
 845                         }
 846                         p->fts_errno = saved_errno;
 847                         goto err;
 848                 }
 849         } else if (lstat(p->fts_accpath, sbp)) {
 850                 p->fts_errno = errno;
 851 err:            memset(sbp, 0, sizeof(struct stat));
 852                 return (FTS_NS);
 853         }
 854
 855         if (S_ISDIR(sbp->st_mode)) {
 856                 /*
 857                  * Set the device/inode.  Used to find cycles and check for
 858                  * crossing mount points.  Also remember the link count, used
 859                  * in fts_build to limit the number of stat calls.  It is
 860                  * understood that these fields are only referenced if fts_info
 861                  * is set to FTS_D.
 862                  */
 863                 dev = p->fts_dev = sbp->st_dev;
 864                 ino = p->fts_ino = sbp->st_ino;
 865                 p->fts_nlink = sbp->st_nlink;
 866
 867                 if (ISDOT(p->fts_name))
 868                         return (FTS_DOT);
 869
 870                 /*
 871                  * Cycle detection is done by brute force when the directory
 872                  * is first encountered.  If the tree gets deep enough or the
 873                  * number of symbolic links to directories is high enough,
 874                  * something faster might be worthwhile.
 875                  */
 876                 for (t = p->fts_parent;
 877                     t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
 878                         if (ino == t->fts_ino && dev == t->fts_dev) {
 879                                 p->fts_cycle = t;
 880                                 return (FTS_DC);
 881                         }
 882                 return (FTS_D);
 883         }
 884         if (S_ISLNK(sbp->st_mode))
 885                 return (FTS_SL);
 886         if (S_ISREG(sbp->st_mode))
 887                 return (FTS_F);
 888         return (FTS_DEFAULT);
 889 }
 890
 891 static FTSENT *
 892 fts_sort(FTS *sp, FTSENT *head, int nitems)
 893 {
 894         FTSENT **ap, *p;
 895
 896         /*
 897          * Construct an array of pointers to the structures and call qsort(3).
 898          * Reassemble the array in the order returned by qsort.  If unable to
 899          * sort for memory reasons, return the directory entries in their
 900          * current order.  Allocate enough space for the current needs plus
 901          * 40 so don't realloc one entry at a time.
 902          */
 903         if (nitems > sp->fts_nitems) {
 904                 sp->fts_nitems = nitems + 40;
 905                 if ((sp->fts_array = reallocf(sp->fts_array,
 906                     sp->fts_nitems * sizeof(FTSENT *))) == NULL) {
 907                         sp->fts_nitems = 0;
 908                         return (head);
 909                 }
 910         }
 911         for (ap = sp->fts_array, p = head; p; p = p->fts_link)
 912                 *ap++ = p;
 913         qsort(sp->fts_array, nitems, sizeof(FTSENT *),
 914               (int (*)(const void *, const void *))sp->fts_compar);
 915         for (head = *(ap = sp->fts_array); --nitems; ++ap)
 916                 ap[0]->fts_link = ap[1];
 917         ap[0]->fts_link = NULL;
 918         return (head);
 919 }
 920
 921 static FTSENT *
 922 fts_alloc(FTS *sp, const char *name, int namelen)
 923 {
 924         FTSENT *p;
 925         size_t len;
 926
 927         /*
 928          * The file name is a variable length array and no stat structure is
 929          * necessary if the user has set the nostat bit.  Allocate the FTSENT
 930          * structure, the file name and the stat structure in one chunk, but
 931          * be careful that the stat structure is reasonably aligned.  Since the
 932          * fts_name field is declared to be of size 1, the fts_name pointer is
 933          * namelen + 2 before the first possible address of the stat structure.
 934          */
 935         len = sizeof(FTSENT) + namelen;
 936         if (!ISSET(FTS_NOSTAT))
 937                 len += sizeof(struct stat) + ALIGNBYTES;
 938         if ((p = malloc(len)) == NULL)
 939                 return (NULL);
 940
 941         /* Copy the name and guarantee NUL termination. */
 942         memmove(p->fts_name, name, namelen);
 943         p->fts_name[namelen] = '\0';
 944
 945         if (!ISSET(FTS_NOSTAT))
 946                 p->fts_statp = (struct stat *)ALIGN(p->fts_name + namelen + 2);
 947         p->fts_namelen = namelen;
 948         p->fts_path = sp->fts_path;
 949         p->fts_errno = 0;
 950         p->fts_flags = 0;
 951         p->fts_instr = FTS_NOINSTR;
 952         p->fts_number = 0;
 953         p->fts_pointer = NULL;
 954         return (p);
 955 }
 956
 957 static void
 958 fts_lfree(FTSENT *head)
 959 {
 960         FTSENT *p;
 961
 962         /* Free a linked list of structures. */
 963         while ((p = head)) {
 964                 head = head->fts_link;
 965                 free(p);
 966         }
 967 }
 968
 969 /*
 970  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
 971  * Most systems will allow creation of paths much longer than MAXPATHLEN, even
 972  * though the kernel won't resolve them.  Add the size (not just what's needed)
 973  * plus 256 bytes so don't realloc the path 2 bytes at a time.
 974  */
 975 static int
 976 fts_palloc(FTS *sp, size_t more)
 977 {
 978
 979         sp->fts_pathlen += more + 256;
 980         /*
 981          * Check for possible wraparound.  In an FTS, fts_pathlen is
 982          * a signed int but in an FTSENT it is an unsigned short.
 983          * We limit fts_pathlen to USHRT_MAX to be safe in both cases.
 984          */
 985         if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) {
 986                 if (sp->fts_path)
 987                         free(sp->fts_path);
 988                 sp->fts_path = NULL;
 989                 errno = ENAMETOOLONG;
 990                 return (1);
 991         }
 992         sp->fts_path = reallocf(sp->fts_path, sp->fts_pathlen);
 993         return (sp->fts_path == NULL);
 994 }
 995
 996 /*
 997  * When the path is realloc'd, have to fix all of the pointers in structures
 998  * already returned.
 999  */
1000 static void
1001 fts_padjust(FTS *sp, FTSENT *head)
1002 {
1003         FTSENT *p;
1004         char *addr = sp->fts_path;
1005
1006 #define ADJUST(p) do {                                                  \
1007         if ((p)->fts_accpath != (p)->fts_name) {                        \
1008                 (p)->fts_accpath =                                      \
1009                     (char *)addr + ((p)->fts_accpath - (p)->fts_path);  \
1010         }                                                               \
1011         (p)->fts_path = addr;                                           \
1012 } while (0)
1013         /* Adjust the current set of children. */
1014         for (p = sp->fts_child; p; p = p->fts_link)
1015                 ADJUST(p);
1016
1017         /* Adjust the rest of the tree, including the current level. */
1018         for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1019                 ADJUST(p);
1020                 p = p->fts_link ? p->fts_link : p->fts_parent;
1021         }
1022 }
1023
1024 static size_t
1025 fts_maxarglen(char * const *argv)
1026 {
1027         size_t len, max;
1028
1029         for (max = 0; *argv; ++argv)
1030                 if ((len = strlen(*argv)) > max)
1031                         max = len;
1032         return (max + 1);
1033 }
1034
1035 /*
1036  * Change to dir specified by fd or p->fts_accpath without getting
1037  * tricked by someone changing the world out from underneath us.
1038  * Assumes p->fts_dev and p->fts_ino are filled in.
1039  */
1040 static int
1041 fts_safe_changedir(FTS *sp, FTSENT *p, int fd, const char *path)
1042 {
1043         int ret, oerrno, newfd;
1044         struct stat sb;
1045
1046         newfd = fd;
1047         if (ISSET(FTS_NOCHDIR))
1048                 return (0);
1049         if (fd < 0 && (newfd = _open(path, O_RDONLY, 0)) < 0)
1050                 return (-1);
1051         if (_fstat(newfd, &sb)) {
1052                 ret = -1;
1053                 goto bail;
1054         }
1055         if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {
1056                 errno = ENOENT;         /* disinformation */
1057                 ret = -1;
1058                 goto bail;
1059         }
1060         ret = fchdir(newfd);
1061 bail:
1062         oerrno = errno;
1063         if (fd < 0)
1064                 _close(newfd);
1065         errno = oerrno;
1066         return (ret);
1067 }