compat_fts.c

   1 #include "config.h"
   2
   3 #if HAVE_FTS
   4
   5 int dummy;
   6
   7 #else
   8
   9 /*      $Id: compat_fts.c,v 1.6 2014/12/11 18:20:07 schwarze Exp $      */
  10 /*      $OpenBSD: fts.c,v 1.49 2014/11/23 00:14:22 guenther Exp $       */
  11
  12 /*-
  13  * Copyright (c) 1990, 1993, 1994
  14  *      The Regents of the University of California.  All rights reserved.
  15  *
  16  * Redistribution and use in source and binary forms, with or without
  17  * modification, are permitted provided that the following conditions
  18  * are met:
  19  * 1. Redistributions of source code must retain the above copyright
  20  *    notice, this list of conditions and the following disclaimer.
  21  * 2. Redistributions in binary form must reproduce the above copyright
  22  *    notice, this list of conditions and the following disclaimer in the
  23  *    documentation and/or other materials provided with the distribution.
  24  * 3. Neither the name of the University nor the names of its contributors
  25  *    may be used to endorse or promote products derived from this software
  26  *    without specific prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  29  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  30  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  31  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  32  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  33  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  34  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  35  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  36  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  37  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  38  * SUCH DAMAGE.
  39  */
  40
  41 #include <sys/param.h>
  42 #include <sys/stat.h>
  43 #include <sys/types.h>
  44
  45 #include <dirent.h>
  46 #include <errno.h>
  47 #include <fcntl.h>
  48 #include <limits.h>
  49 #include <stdlib.h>
  50 #include <string.h>
  51 #include <unistd.h>
  52 #include "compat_fts.h"
  53
  54 static FTSENT   *fts_alloc(FTS *, const char *, size_t);
  55 static FTSENT   *fts_build(FTS *);
  56 static void      fts_lfree(FTSENT *);
  57 static void      fts_load(FTS *, FTSENT *);
  58 static size_t    fts_maxarglen(char * const *);
  59 static void      fts_padjust(FTS *, FTSENT *);
  60 static int       fts_palloc(FTS *, size_t);
  61 static unsigned short    fts_stat(FTS *, FTSENT *);
  62 static int       fts_safe_changedir(FTS *, FTSENT *, int, const char *);
  63
  64 #define ISDOT(a)        (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
  65 #define MAX(a,b)        (((a)>(b))?(a):(b))
  66 #ifndef O_DIRECTORY
  67 #define O_DIRECTORY     0
  68 #endif
  69
  70 #define CLR(opt)        (sp->fts_options &= ~(opt))
  71 #define ISSET(opt)      (sp->fts_options & (opt))
  72 #define SET(opt)        (sp->fts_options |= (opt))
  73
  74 #define FCHDIR(sp, fd)  (!ISSET(FTS_NOCHDIR) && fchdir(fd))
  75
  76 FTS *
  77 fts_open(char * const *argv, int options, void *dummy)
  78 {
  79         FTS *sp;
  80         FTSENT *p, *root;
  81         int nitems;
  82         FTSENT *parent, *tmp;
  83         size_t len;
  84
  85         /* Options check. */
  86         if (options & ~FTS_OPTIONMASK) {
  87                 errno = EINVAL;
  88                 return (NULL);
  89         }
  90
  91         /* Allocate/initialize the stream */
  92         if ((sp = calloc(1, sizeof(FTS))) == NULL)
  93                 return (NULL);
  94         sp->fts_options = options;
  95
  96         /*
  97          * Start out with 1K of path space, and enough, in any case,
  98          * to hold the user's paths.
  99          */
 100         if (fts_palloc(sp, MAX(fts_maxarglen(argv), PATH_MAX)))
 101                 goto mem1;
 102
 103         /* Allocate/initialize root's parent. */
 104         if ((parent = fts_alloc(sp, "", 0)) == NULL)
 105                 goto mem2;
 106         parent->fts_level = FTS_ROOTPARENTLEVEL;
 107
 108         /* Allocate/initialize root(s). */
 109         for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
 110                 /* Don't allow zero-length paths. */
 111                 if ((len = strlen(*argv)) == 0) {
 112                         errno = ENOENT;
 113                         goto mem3;
 114                 }
 115
 116                 if ((p = fts_alloc(sp, *argv, len)) == NULL)
 117                         goto mem3;
 118                 p->fts_level = FTS_ROOTLEVEL;
 119                 p->fts_parent = parent;
 120                 p->fts_accpath = p->fts_name;
 121                 p->fts_info = fts_stat(sp, p);
 122
 123                 /* Command-line "." and ".." are real directories. */
 124                 if (p->fts_info == FTS_DOT)
 125                         p->fts_info = FTS_D;
 126
 127                 p->fts_link = NULL;
 128                 if (root == NULL)
 129                         tmp = root = p;
 130                 else {
 131                         tmp->fts_link = p;
 132                         tmp = p;
 133                 }
 134         }
 135
 136         /*
 137          * Allocate a dummy pointer and make fts_read think that we've just
 138          * finished the node before the root(s); set p->fts_info to FTS_INIT
 139          * so that everything about the "current" node is ignored.
 140          */
 141         if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
 142                 goto mem3;
 143         sp->fts_cur->fts_link = root;
 144         sp->fts_cur->fts_info = FTS_INIT;
 145
 146         /*
 147          * If using chdir(2), grab a file descriptor pointing to dot to ensure
 148          * that we can get back here; this could be avoided for some paths,
 149          * but almost certainly not worth the effort.  Slashes, symbolic links,
 150          * and ".." are all fairly nasty problems.  Note, if we can't get the
 151          * descriptor we run anyway, just more slowly.
 152          */
 153         if (!ISSET(FTS_NOCHDIR) &&
 154             (sp->fts_rfd = open(".", O_RDONLY | O_CLOEXEC)) < 0)
 155                 SET(FTS_NOCHDIR);
 156
 157         if (nitems == 0)
 158                 free(parent);
 159
 160         return (sp);
 161
 162 mem3:   fts_lfree(root);
 163         free(parent);
 164 mem2:   free(sp->fts_path);
 165 mem1:   free(sp);
 166         return (NULL);
 167 }
 168
 169 static void
 170 fts_load(FTS *sp, FTSENT *p)
 171 {
 172         size_t len;
 173         char *cp;
 174
 175         /*
 176          * Load the stream structure for the next traversal.  Since we don't
 177          * actually enter the directory until after the preorder visit, set
 178          * the fts_accpath field specially so the chdir gets done to the right
 179          * place and the user can access the first node.  From fts_open it's
 180          * known that the path will fit.
 181          */
 182         len = p->fts_pathlen = p->fts_namelen;
 183         memmove(sp->fts_path, p->fts_name, len + 1);
 184         if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
 185                 len = strlen(++cp);
 186                 memmove(p->fts_name, cp, len + 1);
 187                 p->fts_namelen = len;
 188         }
 189         p->fts_accpath = p->fts_path = sp->fts_path;
 190         sp->fts_dev = p->fts_dev;
 191 }
 192
 193 int
 194 fts_close(FTS *sp)
 195 {
 196         FTSENT *freep, *p;
 197         int rfd, error = 0;
 198
 199         /*
 200          * This still works if we haven't read anything -- the dummy structure
 201          * points to the root list, so we step through to the end of the root
 202          * list which has a valid parent pointer.
 203          */
 204         if (sp->fts_cur) {
 205                 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
 206                         freep = p;
 207                         p = p->fts_link ? p->fts_link : p->fts_parent;
 208                         free(freep);
 209                 }
 210                 free(p);
 211         }
 212
 213         /* Stash the original directory fd if needed. */
 214         rfd = ISSET(FTS_NOCHDIR) ? -1 : sp->fts_rfd;
 215
 216         /* Free up child linked list, sort array, path buffer, stream ptr.*/
 217         if (sp->fts_child)
 218                 fts_lfree(sp->fts_child);
 219         free(sp->fts_path);
 220         free(sp);
 221
 222         /* Return to original directory, checking for error. */
 223         if (rfd != -1) {
 224                 int saved_errno;
 225                 error = fchdir(rfd);
 226                 saved_errno = errno;
 227                 (void)close(rfd);
 228                 errno = saved_errno;
 229         }
 230
 231         return (error);
 232 }
 233
 234 /*
 235  * Special case of "/" at the end of the path so that slashes aren't
 236  * appended which would cause paths to be written as "....//foo".
 237  */
 238 #define NAPPEND(p)                                                      \
 239         (p->fts_path[p->fts_pathlen - 1] == '/'                         \
 240             ? p->fts_pathlen - 1 : p->fts_pathlen)
 241
 242 FTSENT *
 243 fts_read(FTS *sp)
 244 {
 245         FTSENT *p, *tmp;
 246         int instr;
 247         char *t;
 248
 249         /* If finished or unrecoverable error, return NULL. */
 250         if (sp->fts_cur == NULL || ISSET(FTS_STOP))
 251                 return (NULL);
 252
 253         /* Set current node pointer. */
 254         p = sp->fts_cur;
 255
 256         /* Save and zero out user instructions. */
 257         instr = p->fts_instr;
 258         p->fts_instr = FTS_NOINSTR;
 259
 260         /* Directory in pre-order. */
 261         if (p->fts_info == FTS_D) {
 262                 /* If skipped or crossed mount point, do post-order visit. */
 263                 if (instr == FTS_SKIP ||
 264                     (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
 265                         if (sp->fts_child) {
 266                                 fts_lfree(sp->fts_child);
 267                                 sp->fts_child = NULL;
 268                         }
 269                         p->fts_info = FTS_DP;
 270                         return (p);
 271                 }
 272
 273                 /*
 274                  * Cd to the subdirectory.
 275                  *
 276                  * If have already read and now fail to chdir, whack the list
 277                  * to make the names come out right, and set the parent errno
 278                  * so the application will eventually get an error condition.
 279                  * Set the FTS_DONTCHDIR flag so that when we logically change
 280                  * directories back to the parent we don't do a chdir.
 281                  *
 282                  * If haven't read do so.  If the read fails, fts_build sets
 283                  * FTS_STOP or the fts_info field of the node.
 284                  */
 285                 if (sp->fts_child) {
 286                         if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
 287                                 p->fts_errno = errno;
 288                                 p->fts_flags |= FTS_DONTCHDIR;
 289                                 for (p = sp->fts_child; p; p = p->fts_link)
 290                                         p->fts_accpath =
 291                                             p->fts_parent->fts_accpath;
 292                         }
 293                 } else if ((sp->fts_child = fts_build(sp)) == NULL) {
 294                         if (ISSET(FTS_STOP))
 295                                 return (NULL);
 296                         return (p);
 297                 }
 298                 p = sp->fts_child;
 299                 sp->fts_child = NULL;
 300                 goto name;
 301         }
 302
 303         /* Move to the next node on this level. */
 304 next:   tmp = p;
 305         if ((p = p->fts_link)) {
 306                 free(tmp);
 307
 308                 /*
 309                  * If reached the top, return to the original directory (or
 310                  * the root of the tree), and load the paths for the next root.
 311                  */
 312                 if (p->fts_level == FTS_ROOTLEVEL) {
 313                         if (FCHDIR(sp, sp->fts_rfd)) {
 314                                 SET(FTS_STOP);
 315                                 return (NULL);
 316                         }
 317                         fts_load(sp, p);
 318                         return (sp->fts_cur = p);
 319                 }
 320
 321                 /*
 322                  * User may have called fts_set on the node.  If skipped,
 323                  * ignore.  If followed, get a file descriptor so we can
 324                  * get back if necessary.
 325                  */
 326                 if (p->fts_instr == FTS_SKIP)
 327                         goto next;
 328
 329 name:           t = sp->fts_path + NAPPEND(p->fts_parent);
 330                 *t++ = '/';
 331                 memmove(t, p->fts_name, p->fts_namelen + 1);
 332                 return (sp->fts_cur = p);
 333         }
 334
 335         /* Move up to the parent node. */
 336         p = tmp->fts_parent;
 337         free(tmp);
 338
 339         if (p->fts_level == FTS_ROOTPARENTLEVEL) {
 340                 /*
 341                  * Done; free everything up and set errno to 0 so the user
 342                  * can distinguish between error and EOF.
 343                  */
 344                 free(p);
 345                 errno = 0;
 346                 return (sp->fts_cur = NULL);
 347         }
 348
 349         /* NUL terminate the pathname. */
 350         sp->fts_path[p->fts_pathlen] = '\0';
 351
 352         /*
 353          * Return to the parent directory.  If at a root node or came through
 354          * a symlink, go back through the file descriptor.  Otherwise, cd up
 355          * one directory.
 356          */
 357         if (p->fts_level == FTS_ROOTLEVEL) {
 358                 if (FCHDIR(sp, sp->fts_rfd)) {
 359                         SET(FTS_STOP);
 360                         sp->fts_cur = p;
 361                         return (NULL);
 362                 }
 363         } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
 364             fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
 365                 SET(FTS_STOP);
 366                 sp->fts_cur = p;
 367                 return (NULL);
 368         }
 369         p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
 370         return (sp->fts_cur = p);
 371 }
 372
 373 /*
 374  * Fts_set takes the stream as an argument although it's not used in this
 375  * implementation; it would be necessary if anyone wanted to add global
 376  * semantics to fts using fts_set.  An error return is allowed for similar
 377  * reasons.
 378  */
 379 /* ARGSUSED */
 380 int
 381 fts_set(FTS *sp, FTSENT *p, int instr)
 382 {
 383         if (instr && instr != FTS_NOINSTR && instr != FTS_SKIP) {
 384                 errno = EINVAL;
 385                 return (1);
 386         }
 387         p->fts_instr = instr;
 388         return (0);
 389 }
 390
 391 /*
 392  * This is the tricky part -- do not casually change *anything* in here.  The
 393  * idea is to build the linked list of entries that are used by fts_children
 394  * and fts_read.  There are lots of special cases.
 395  *
 396  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
 397  * set and it's a physical walk (so that symbolic links can't be directories),
 398  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
 399  * of the file is in the directory entry.  Otherwise, we assume that the number
 400  * of subdirectories in a node is equal to the number of links to the parent.
 401  * The former skips all stat calls.  The latter skips stat calls in any leaf
 402  * directories and for any files after the subdirectories in the directory have
 403  * been found, cutting the stat calls by about 2/3.
 404  */
 405 static FTSENT *
 406 fts_build(FTS *sp)
 407 {
 408         struct dirent *dp;
 409         FTSENT *p, *head;
 410         FTSENT *cur, *tail;
 411         DIR *dirp;
 412         void *oldaddr;
 413         size_t dlen, len, maxlen;
 414         int nitems, cderrno, descend, level, doadjust;
 415         int saved_errno;
 416         char *cp;
 417
 418         /* Set current node pointer. */
 419         cur = sp->fts_cur;
 420
 421         /*
 422          * Open the directory for reading.  If this fails, we're done.
 423          * If being called from fts_read, set the fts_info field.
 424          */
 425         if ((dirp = opendir(cur->fts_accpath)) == NULL) {
 426                 cur->fts_info = FTS_DNR;
 427                 cur->fts_errno = errno;
 428                 return (NULL);
 429         }
 430
 431         /*
 432          * If we're going to need to stat anything or we want to descend
 433          * and stay in the directory, chdir.  If this fails we keep going,
 434          * but set a flag so we don't chdir after the post-order visit.
 435          * We won't be able to stat anything, but we can still return the
 436          * names themselves.  Note, that since fts_read won't be able to
 437          * chdir into the directory, it will have to return different path
 438          * names than before, i.e. "a/b" instead of "b".  Since the node
 439          * has already been visited in pre-order, have to wait until the
 440          * post-order visit to return the error.  There is a special case
 441          * here, if there was nothing to stat then it's not an error to
 442          * not be able to stat.  This is all fairly nasty.  If a program
 443          * needed sorted entries or stat information, they had better be
 444          * checking FTS_NS on the returned nodes.
 445          */
 446         cderrno = 0;
 447         if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
 448                 cur->fts_errno = errno;
 449                 cur->fts_flags |= FTS_DONTCHDIR;
 450                 descend = 0;
 451                 cderrno = errno;
 452                 (void)closedir(dirp);
 453                 dirp = NULL;
 454         } else
 455                 descend = 1;
 456
 457         /*
 458          * Figure out the max file name length that can be stored in the
 459          * current path -- the inner loop allocates more path as necessary.
 460          * We really wouldn't have to do the maxlen calculations here, we
 461          * could do them in fts_read before returning the path, but it's a
 462          * lot easier here since the length is part of the dirent structure.
 463          *
 464          * If not changing directories set a pointer so that can just append
 465          * each new name into the path.
 466          */
 467         len = NAPPEND(cur);
 468         if (ISSET(FTS_NOCHDIR)) {
 469                 cp = sp->fts_path + len;
 470                 *cp++ = '/';
 471         }
 472         len++;
 473         maxlen = sp->fts_pathlen - len;
 474
 475         /*
 476          * fts_level is signed so we must prevent it from wrapping
 477          * around to FTS_ROOTLEVEL and FTS_ROOTPARENTLEVEL.
 478          */
 479         level = cur->fts_level;
 480         if (level < FTS_MAXLEVEL)
 481             level++;
 482
 483         /* Read the directory, attaching each entry to the `link' pointer. */
 484         doadjust = 0;
 485         for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
 486                 if (ISDOT(dp->d_name))
 487                         continue;
 488
 489 #if HAVE_DIRENT_NAMLEN
 490                 dlen = dp->d_namlen;
 491 #else
 492                 dlen = strlen(dp->d_name);
 493 #endif
 494
 495                 if (!(p = fts_alloc(sp, dp->d_name, dlen)))
 496                         goto mem1;
 497                 if (dlen >= maxlen) {   /* include space for NUL */
 498                         oldaddr = sp->fts_path;
 499                         if (fts_palloc(sp, dlen + len + 1)) {
 500                                 /*
 501                                  * No more memory for path or structures.  Save
 502                                  * errno, free up the current structure and the
 503                                  * structures already allocated.
 504                                  */
 505 mem1:                           saved_errno = errno;
 506                                 if (p)
 507                                         free(p);
 508                                 fts_lfree(head);
 509                                 (void)closedir(dirp);
 510                                 cur->fts_info = FTS_ERR;
 511                                 SET(FTS_STOP);
 512                                 errno = saved_errno;
 513                                 return (NULL);
 514                         }
 515                         /* Did realloc() change the pointer? */
 516                         if (oldaddr != sp->fts_path) {
 517                                 doadjust = 1;
 518                                 if (ISSET(FTS_NOCHDIR))
 519                                         cp = sp->fts_path + len;
 520                         }
 521                         maxlen = sp->fts_pathlen - len;
 522                 }
 523
 524                 p->fts_level = level;
 525                 p->fts_parent = sp->fts_cur;
 526                 p->fts_pathlen = len + dlen;
 527                 if (p->fts_pathlen < len) {
 528                         /*
 529                          * If we wrap, free up the current structure and
 530                          * the structures already allocated, then error
 531                          * out with ENAMETOOLONG.
 532                          */
 533                         free(p);
 534                         fts_lfree(head);
 535                         (void)closedir(dirp);
 536                         cur->fts_info = FTS_ERR;
 537                         SET(FTS_STOP);
 538                         errno = ENAMETOOLONG;
 539                         return (NULL);
 540                 }
 541
 542                 if (cderrno) {
 543                         p->fts_info = FTS_NS;
 544                         p->fts_errno = cderrno;
 545                         p->fts_accpath = cur->fts_accpath;
 546                 } else {
 547                         /* Build a file name for fts_stat to stat. */
 548                         if (ISSET(FTS_NOCHDIR)) {
 549                                 p->fts_accpath = p->fts_path;
 550                                 memmove(cp, p->fts_name, p->fts_namelen + 1);
 551                         } else
 552                                 p->fts_accpath = p->fts_name;
 553                         /* Stat it. */
 554                         p->fts_info = fts_stat(sp, p);
 555                 }
 556
 557                 /* We walk in directory order so "ls -f" doesn't get upset. */
 558                 p->fts_link = NULL;
 559                 if (head == NULL)
 560                         head = tail = p;
 561                 else {
 562                         tail->fts_link = p;
 563                         tail = p;
 564                 }
 565                 ++nitems;
 566         }
 567         if (dirp)
 568                 (void)closedir(dirp);
 569
 570         /*
 571          * If realloc() changed the address of the path, adjust the
 572          * addresses for the rest of the tree and the dir list.
 573          */
 574         if (doadjust)
 575                 fts_padjust(sp, head);
 576
 577         /*
 578          * If not changing directories, reset the path back to original
 579          * state.
 580          */
 581         if (ISSET(FTS_NOCHDIR)) {
 582                 if (len == sp->fts_pathlen || nitems == 0)
 583                         --cp;
 584                 *cp = '\0';
 585         }
 586
 587         /*
 588          * If descended after called from fts_children or after called from
 589          * fts_read and nothing found, get back.  At the root level we use
 590          * the saved fd; if one of fts_open()'s arguments is a relative path
 591          * to an empty directory, we wind up here with no other way back.  If
 592          * can't get back, we're done.
 593          */
 594         if (descend && !nitems &&
 595             (cur->fts_level == FTS_ROOTLEVEL ? FCHDIR(sp, sp->fts_rfd) :
 596             fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
 597                 cur->fts_info = FTS_ERR;
 598                 SET(FTS_STOP);
 599                 return (NULL);
 600         }
 601
 602         /* If didn't find anything, return NULL. */
 603         if (!nitems) {
 604                 cur->fts_info = FTS_DP;
 605                 return (NULL);
 606         }
 607         return (head);
 608 }
 609
 610 static unsigned short
 611 fts_stat(FTS *sp, FTSENT *p)
 612 {
 613         FTSENT *t;
 614         dev_t dev;
 615         ino_t ino;
 616         struct stat *sbp;
 617
 618         /* If user needs stat info, stat buffer already allocated. */
 619         sbp = p->fts_statp;
 620
 621         if (lstat(p->fts_accpath, sbp)) {
 622                 p->fts_errno = errno;
 623                 memset(sbp, 0, sizeof(struct stat));
 624                 return (FTS_NS);
 625         }
 626
 627         if (S_ISDIR(sbp->st_mode)) {
 628                 /*
 629                  * Set the device/inode.  Used to find cycles and check for
 630                  * crossing mount points.  Also remember the link count, used
 631                  * in fts_build to limit the number of stat calls.  It is
 632                  * understood that these fields are only referenced if fts_info
 633                  * is set to FTS_D.
 634                  */
 635                 dev = p->fts_dev = sbp->st_dev;
 636                 ino = p->fts_ino = sbp->st_ino;
 637                 p->fts_nlink = sbp->st_nlink;
 638
 639                 if (ISDOT(p->fts_name))
 640                         return (FTS_DOT);
 641
 642                 /*
 643                  * Cycle detection is done by brute force when the directory
 644                  * is first encountered.  If the tree gets deep enough or the
 645                  * number of symbolic links to directories is high enough,
 646                  * something faster might be worthwhile.
 647                  */
 648                 for (t = p->fts_parent;
 649                     t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
 650                         if (ino == t->fts_ino && dev == t->fts_dev) {
 651                                 p->fts_cycle = t;
 652                                 return (FTS_DC);
 653                         }
 654                 return (FTS_D);
 655         }
 656         if (S_ISLNK(sbp->st_mode))
 657                 return (FTS_SL);
 658         if (S_ISREG(sbp->st_mode))
 659                 return (FTS_F);
 660         return (FTS_DEFAULT);
 661 }
 662
 663 static FTSENT *
 664 fts_alloc(FTS *sp, const char *name, size_t namelen)
 665 {
 666         FTSENT *p;
 667         size_t len;
 668
 669         len = sizeof(FTSENT) + namelen;
 670         if ((p = calloc(1, len)) == NULL)
 671                 return (NULL);
 672
 673         p->fts_path = sp->fts_path;
 674         p->fts_namelen = namelen;
 675         p->fts_instr = FTS_NOINSTR;
 676         p->fts_statp = malloc(sizeof(struct stat));
 677         if (p->fts_statp == NULL) {
 678                 free(p);
 679                 return (NULL);
 680         }
 681         memcpy(p->fts_name, name, namelen);
 682
 683         return (p);
 684 }
 685
 686 static void
 687 fts_lfree(FTSENT *head)
 688 {
 689         FTSENT *p;
 690
 691         /* Free a linked list of structures. */
 692         while ((p = head)) {
 693                 head = head->fts_link;
 694                 free(p);
 695         }
 696 }
 697
 698 /*
 699  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
 700  * Most systems will allow creation of paths much longer than PATH_MAX, even
 701  * though the kernel won't resolve them.  Add the size (not just what's needed)
 702  * plus 256 bytes so don't realloc the path 2 bytes at a time.
 703  */
 704 static int
 705 fts_palloc(FTS *sp, size_t more)
 706 {
 707         char *p;
 708
 709         /*
 710          * Check for possible wraparound.
 711          */
 712         more += 256;
 713         if (sp->fts_pathlen + more < sp->fts_pathlen) {
 714                 if (sp->fts_path)
 715                         free(sp->fts_path);
 716                 sp->fts_path = NULL;
 717                 errno = ENAMETOOLONG;
 718                 return (1);
 719         }
 720         sp->fts_pathlen += more;
 721         p = realloc(sp->fts_path, sp->fts_pathlen);
 722         if (p == NULL) {
 723                 if (sp->fts_path)
 724                         free(sp->fts_path);
 725                 sp->fts_path = NULL;
 726                 return (1);
 727         }
 728         sp->fts_path = p;
 729         return (0);
 730 }
 731
 732 /*
 733  * When the path is realloc'd, have to fix all of the pointers in structures
 734  * already returned.
 735  */
 736 static void
 737 fts_padjust(FTS *sp, FTSENT *head)
 738 {
 739         FTSENT *p;
 740         char *addr = sp->fts_path;
 741
 742 #define ADJUST(p) {                                                     \
 743         if ((p)->fts_accpath != (p)->fts_name) {                        \
 744                 (p)->fts_accpath =                                      \
 745                     (char *)addr + ((p)->fts_accpath - (p)->fts_path);  \
 746         }                                                               \
 747         (p)->fts_path = addr;                                           \
 748 }
 749         /* Adjust the current set of children. */
 750         for (p = sp->fts_child; p; p = p->fts_link)
 751                 ADJUST(p);
 752
 753         /* Adjust the rest of the tree, including the current level. */
 754         for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
 755                 ADJUST(p);
 756                 p = p->fts_link ? p->fts_link : p->fts_parent;
 757         }
 758 }
 759
 760 static size_t
 761 fts_maxarglen(char * const *argv)
 762 {
 763         size_t len, max;
 764
 765         for (max = 0; *argv; ++argv)
 766                 if ((len = strlen(*argv)) > max)
 767                         max = len;
 768         return (max + 1);
 769 }
 770
 771 /*
 772  * Change to dir specified by fd or p->fts_accpath without getting
 773  * tricked by someone changing the world out from underneath us.
 774  * Assumes p->fts_dev and p->fts_ino are filled in.
 775  */
 776 static int
 777 fts_safe_changedir(FTS *sp, FTSENT *p, int fd, const char *path)
 778 {
 779         int ret, oerrno, newfd;
 780         struct stat sb;
 781
 782         newfd = fd;
 783         if (ISSET(FTS_NOCHDIR))
 784                 return (0);
 785         if (fd < 0 && (newfd = open(path, O_RDONLY|O_DIRECTORY|O_CLOEXEC)) < 0)
 786                 return (-1);
 787         if (fstat(newfd, &sb)) {
 788                 ret = -1;
 789                 goto bail;
 790         }
 791         if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {
 792                 errno = ENOENT;         /* disinformation */
 793                 ret = -1;
 794                 goto bail;
 795         }
 796         ret = fchdir(newfd);
 797 bail:
 798         oerrno = errno;
 799         if (fd < 0)
 800                 (void)close(newfd);
 801         errno = oerrno;
 802         return (ret);
 803 }
 804
 805 #endif