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