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