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