lib/libc/gen/fts.c

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