1 /*- 2 * Copyright (c) 1990 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 */ 7 8 #if defined(LIBC_SCCS) && !defined(lint) 9 static char sccsid[] = "@(#)fts.c 5.12 (Berkeley) 11/18/90"; 10 #endif /* LIBC_SCCS and not lint */ 11 12 #include <sys/param.h> 13 #include <sys/stat.h> 14 #include <fcntl.h> 15 #include <dirent.h> 16 #include <errno.h> 17 #include <fts.h> 18 #include <string.h> 19 #include <stdlib.h> 20 21 FTSENT *fts_alloc(), *fts_build(), *fts_cycle(), *fts_root(), *fts_sort(); 22 void fts_lfree(), fts_load(); 23 u_short fts_stat(); 24 25 /* 26 * Special case a root of "/" so that slashes aren't appended causing 27 * paths to be written as "//foo". 28 */ 29 #define NAPPEND(p) \ 30 (p->fts_level == ROOTLEVEL && p->fts_pathlen == 1 && \ 31 p->fts_path[0] == '/' ? 0 : p->fts_pathlen) 32 33 #define ISSET(opt) (sp->fts_options & opt) 34 #define SET(opt) (sp->fts_options |= opt) 35 36 #define CHDIR(sp, path) (!ISSET(FTS_NOCHDIR) && chdir(path)) 37 #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd)) 38 39 /* fts_build flags */ 40 #define BCHILD 1 /* from fts_children */ 41 #define BREAD 2 /* from fts_read */ 42 43 /* fts_level values */ 44 #define ROOTLEVEL 0 45 #define ROOTPARENTLEVEL -1 46 47 FTS * 48 fts_open(argv, options, compar) 49 char *argv[]; 50 register int options; 51 int (*compar)(); 52 { 53 register FTS *sp; 54 register FTSENT *p, *root; 55 register int nitems, maxlen; 56 FTSENT *parent, *tmp; 57 char *fts_path(); 58 59 /* Allocate/initialize the stream */ 60 if (!(sp = (FTS *)malloc((u_int)sizeof(FTS)))) 61 return(NULL); 62 bzero(sp, sizeof(FTS)); 63 sp->fts_compar = compar; 64 sp->fts_options = options; 65 66 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ 67 if (ISSET(FTS_LOGICAL)) 68 SET(FTS_NOCHDIR); 69 70 /* Allocate/initialize root's parent. */ 71 if (!(parent = fts_alloc(sp, "", 0))) 72 goto mem1; 73 parent->fts_level = ROOTPARENTLEVEL; 74 75 /* Allocate/initialize root(s). */ 76 maxlen = -1; 77 for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) { 78 if (!(p = fts_root(sp, *argv))) 79 goto mem2; 80 if (maxlen < p->fts_namelen) 81 maxlen = p->fts_namelen; 82 /* 83 * If comparison routine supplied, traverse in sorted 84 * order; otherwise traverse in the order specified. 85 */ 86 if (compar) { 87 p->fts_link = root; 88 root = p; 89 p->fts_accpath = p->fts_name; 90 if (!(options & FTS_NOSTAT)) 91 p->fts_info = fts_stat(sp, p, 0); 92 } else { 93 p->fts_link = NULL; 94 if (!root) 95 tmp = root = p; 96 else { 97 tmp->fts_link = p; 98 tmp = p; 99 } 100 } 101 p->fts_level = ROOTLEVEL; 102 p->fts_parent = parent; 103 } 104 if (compar && nitems > 1) 105 root = fts_sort(sp, root, nitems); 106 107 /* 108 * Allocate a dummy pointer and make fts_read think that we've just 109 * finished the node before the root(s); set p->fts_info to FTS_NS 110 * so that everything about the "current" node is ignored. 111 */ 112 if (!(sp->fts_cur = fts_alloc(sp, "", 0))) 113 goto mem2; 114 sp->fts_cur->fts_link = root; 115 sp->fts_cur->fts_info = FTS_NS; 116 117 /* Start out with at least 1K+ of path space. */ 118 if (!fts_path(sp, MAX(maxlen, MAXPATHLEN))) 119 goto mem3; 120 121 /* 122 * If using chdir(2), grab a file descriptor pointing to dot to insure 123 * that we can get back here; this could be avoided for some paths, 124 * but almost certainly not worth the effort. Slashes, symbolic links, 125 * and ".." are all fairly nasty problems. Note, if we can't get the 126 * descriptor we run anyway, just more slowly. 127 */ 128 if (!ISSET(FTS_NOCHDIR) && (sp->fts_sd = open(".", O_RDONLY, 0)) < 0) 129 SET(FTS_NOCHDIR); 130 131 return(sp); 132 133 mem3: free((void *)sp->fts_cur); 134 mem2: fts_lfree(root); 135 free((void *)parent); 136 mem1: free((void *)sp); 137 return(NULL); 138 } 139 140 static void 141 fts_load(sp, p) 142 FTS *sp; 143 register FTSENT *p; 144 { 145 register int len; 146 register char *cp; 147 148 /* 149 * Load the stream structure for the next traversal; set the 150 * fts_accpath field specially so the chdir gets done to the 151 * right place and the user can access the first node. 152 */ 153 len = p->fts_pathlen = p->fts_namelen; 154 bcopy(p->fts_name, sp->fts_path, len + 1); 155 if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { 156 len = strlen(++cp); 157 bcopy(cp, p->fts_name, len + 1); 158 p->fts_namelen = len; 159 } 160 p->fts_accpath = p->fts_path = sp->fts_path; 161 } 162 163 fts_close(sp) 164 FTS *sp; 165 { 166 register FTSENT *freep, *p; 167 int saved_errno; 168 169 if (sp->fts_cur) { 170 /* 171 * This still works if we haven't read anything -- the dummy 172 * structure points to the root list, so we step through to 173 * the end of the root list which has a valid parent pointer. 174 */ 175 for (p = sp->fts_cur; p->fts_level > ROOTPARENTLEVEL;) { 176 freep = p; 177 p = p->fts_link ? p->fts_link : p->fts_parent; 178 free((void *)freep); 179 } 180 free((void *)p); 181 } 182 183 /* Free up child linked list, sort array, path buffer. */ 184 if (sp->fts_child) 185 fts_lfree(sp->fts_child); 186 if (sp->fts_array) 187 free((void *)sp->fts_array); 188 free((char *)sp->fts_path); 189 190 /* 191 * Return to original directory, save errno if necessary; free up 192 * the directory buffer. 193 */ 194 if (!ISSET(FTS_NOCHDIR)) { 195 saved_errno = fchdir(sp->fts_sd) ? errno : 0; 196 (void)close(sp->fts_sd); 197 } 198 199 /* Free up the stream pointer. */ 200 free((void *)sp); 201 202 /* Set errno and return. */ 203 if (!ISSET(FTS_NOCHDIR) && saved_errno) { 204 errno = saved_errno; 205 return(-1); 206 } 207 return(0); 208 } 209 210 FTSENT * 211 fts_read(sp) 212 register FTS *sp; 213 { 214 register FTSENT *p, *tmp; 215 register int instr; 216 register char *cp; 217 static int cd; 218 219 /* If finished or unrecoverable error, return NULL. */ 220 if (!sp->fts_cur || ISSET(FTS__STOP)) 221 return(NULL); 222 223 /* Set current node pointer. */ 224 p = sp->fts_cur; 225 226 /* Save and zero out user instructions. */ 227 instr = p->fts_instr; 228 p->fts_instr = FTS__NOINSTR; 229 230 /* If used fts_link pointer for cycle detection, restore it. */ 231 if (sp->fts_savelink) { 232 p->fts_link = sp->fts_savelink; 233 sp->fts_savelink = NULL; 234 } 235 236 /* Any type of file may be re-visited; re-stat and return. */ 237 if (instr == FTS_AGAIN) { 238 p->fts_info = fts_stat(sp, p, 0); 239 return(p); 240 } 241 242 /* Following a symbolic link. */ 243 if (p->fts_info == FTS_SL && instr == FTS_FOLLOW) { 244 p->fts_info = fts_stat(sp, p, 1); 245 return(p); 246 } 247 248 /* Directory in pre-order. */ 249 if (p->fts_info == FTS_D) { 250 /* If skipped or crossed mount point, do post-order visit. */ 251 if (instr == FTS_SKIP || ISSET(FTS_XDEV) && 252 p->fts_statb.st_dev != sp->sdev) { 253 if (sp->fts_child) { 254 fts_lfree(sp->fts_child); 255 sp->fts_child = NULL; 256 } 257 p->fts_info = FTS_DP; 258 return(p); 259 } 260 261 /* Read the directory if necessary, and return first entry. */ 262 if (sp->fts_child) 263 if (CHDIR(sp, p->fts_accpath)) { 264 fts_lfree(sp->fts_child); 265 p->fts_info = FTS_DNX; 266 } else { 267 p = sp->fts_child; 268 cp = sp->fts_path + NAPPEND(p->fts_parent); 269 *cp++ = '/'; 270 bcopy(p->fts_name, cp, p->fts_namelen + 1); 271 } 272 else { 273 if (!(sp->fts_child = fts_build(sp, BREAD))) 274 return(p); 275 p = sp->fts_child; 276 } 277 sp->fts_child = NULL; 278 return(sp->fts_cur = p); 279 } 280 281 /* Move to next node on this level. */ 282 next: tmp = p; 283 if (p = p->fts_link) { 284 /* 285 * If root level node, set up paths and return. If not the 286 * first time, and it's not an absolute pathname, get back 287 * to starting directory. If that fails, we're dead. 288 */ 289 if (p->fts_level == ROOTLEVEL) { 290 fts_load(sp, p); 291 free((void *)tmp); 292 if (cd && 293 p->fts_path[0] != '/' && FCHDIR(sp, sp->fts_sd)) { 294 /* Can't get back to start; we're dead. */ 295 p->fts_path = "starting directory"; 296 p->fts_info = FTS_ERR; 297 SET(FTS__STOP); 298 return(sp->fts_cur = p); 299 } 300 cd = 1; 301 p->fts_info = fts_stat(sp, p, 0); 302 sp->sdev = p->fts_statb.st_dev; 303 } else { 304 free((void *)tmp); 305 306 /* User may have called fts_set on node. */ 307 if (p->fts_instr == FTS_SKIP) 308 goto next; 309 if (p->fts_instr == FTS_FOLLOW) { 310 p->fts_info = fts_stat(sp, p, 1); 311 p->fts_instr = FTS__NOINSTR; 312 } 313 314 /* Fill in the paths. */ 315 cp = sp->fts_path + NAPPEND(p->fts_parent); 316 *cp++ = '/'; 317 bcopy(p->fts_name, cp, p->fts_namelen + 1); 318 319 /* Check for directory cycles. */ 320 if (p->fts_info == FTS_D && (tmp = fts_cycle(p))) { 321 sp->fts_savelink = p->fts_link; 322 p->fts_link = tmp; 323 p->fts_info = FTS_DC; 324 } 325 } 326 return(sp->fts_cur = p); 327 } 328 329 /* Move to parent. */ 330 p = tmp->fts_parent; 331 free((void *)tmp); 332 333 if (p->fts_level == ROOTPARENTLEVEL) { 334 /* 335 * Done; free everything up and set errno to 0 so the user 336 * can distinguish between error and EOF. 337 */ 338 free((void *)p); 339 errno = 0; 340 return(sp->fts_cur = NULL); 341 } 342 343 sp->fts_path[p->fts_pathlen] = '\0'; 344 if (CHDIR(sp, "..")) { 345 SET(FTS__STOP); 346 p->fts_info = FTS_ERR; 347 } else 348 p->fts_info = FTS_DP; 349 return(sp->fts_cur = p); 350 } 351 352 /* 353 * fts_set takes the stream as an argument although it's not used in this 354 * implementation; it would be necessary if anyone wanted to add global 355 * semantics to fts using fts_set. An error return is allowed for similar 356 * reasons. 357 */ 358 /* ARGSUSED */ 359 fts_set(sp, p, instr) 360 FTS *sp; 361 FTSENT *p; 362 int instr; 363 { 364 p->fts_instr = instr; 365 return(0); 366 } 367 368 FTSENT * 369 fts_children(sp) 370 register FTS *sp; 371 { 372 register FTSENT *p; 373 int fd; 374 375 /* Set current node pointer. */ 376 p = sp->fts_cur; 377 378 /* 379 * Set errno to 0 so that user can tell the difference between an 380 * error and a directory without entries. 381 */ 382 errno = 0; 383 if (ISSET(FTS__STOP) || 384 p->fts_info != FTS_D && p->fts_info != FTS_DNX && 385 p->fts_info != FTS_DNR) 386 return(NULL); 387 388 /* Free up any previous child list. */ 389 if (sp->fts_child) 390 fts_lfree(sp->fts_child); 391 392 /* 393 * If using chdir on a relative path and called BEFORE fts_read does 394 * its chdir to the root of a traversal, we can lose because we need 395 * to chdir into the subdirectory, and we don't know where the current 396 * directory is to get back so that the upcoming chdir by fts_read 397 * will work. 398 */ 399 if (p->fts_level != ROOTLEVEL || p->fts_accpath[0] == '/' || 400 ISSET(FTS_NOCHDIR)) 401 return(sp->fts_child = fts_build(sp, BCHILD)); 402 403 if ((fd = open(".", O_RDONLY, 0)) < 0) 404 return(NULL); 405 sp->fts_child = fts_build(sp, BCHILD); 406 if (fchdir(fd)) 407 return(NULL); 408 (void)close(fd); 409 return(sp->fts_child); 410 } 411 412 #define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2])) 413 414 FTSENT * 415 fts_build(sp, type) 416 register FTS *sp; 417 int type; 418 { 419 register struct dirent *dp; 420 register FTSENT *p, *head; 421 register int nitems; 422 DIR *dirp; 423 int descend, len, level, maxlen, nlinks, saved_errno; 424 char *cp; 425 426 /* Set current node pointer. */ 427 p = sp->fts_cur; 428 429 if (!(dirp = opendir(p->fts_accpath))) { 430 if (type == BREAD) { 431 p->fts_info = FTS_DNR; 432 errno = 0; 433 } 434 return(NULL); 435 } 436 437 /* 438 * The real slowdown in walking the tree is the stat calls. If 439 * FTS_NOSTAT is set and it's a physical walk (so that symbolic 440 * links can't be directories), fts assumes that the number of 441 * subdirectories in a node is equal to the number of links to 442 * the parent. This allows stat calls to be skipped in any leaf 443 * directories and for any nodes after the directories in the 444 * parent node have been found. This empirically cuts the stat 445 * calls by about 2/3. 446 */ 447 nlinks = 448 ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ? 449 p->fts_statb.st_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1; 450 451 /* If told to descend or found links and not told not to descend. */ 452 descend = 0; 453 if (nlinks || type == BREAD) 454 if (!FCHDIR(sp, dirfd(dirp))) 455 descend = 1; 456 /* 457 * Return all the information possible; an fts_read doing a 458 * relative walk of the tree will have to descend, so it can't 459 * succeed. Fts_children or absolute walks of the tree can 460 * succeed, but no stat information will be available. Reset 461 * errno as necessary. 462 */ 463 else { 464 errno = 0; 465 if (type == BREAD) { 466 (void)closedir(dirp); 467 p->fts_info = FTS_DNX; 468 return(NULL); 469 } 470 nlinks = 0; 471 } 472 473 /* Get max file name length that can be stored in current path. */ 474 maxlen = sp->fts_pathlen - p->fts_pathlen - 1; 475 476 cp = sp->fts_path + (len = NAPPEND(p)); 477 *cp++ = '/'; 478 479 level = p->fts_level + 1; 480 481 /* Read the directory, attching each new entry to the `link' pointer. */ 482 for (head = NULL, nitems = 0; dp = readdir(dirp);) { 483 if (ISDOT(dp->d_name) && !ISSET(FTS_SEEDOT)) 484 continue; 485 486 if (!(p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen))) { 487 saved_errno = errno; 488 goto mem1; 489 } 490 if (dp->d_namlen > maxlen) { 491 if (!fts_path(sp, (int)dp->d_namlen)) { 492 /* Quit: this stream no longer has a path. */ 493 SET(FTS__STOP); 494 saved_errno = errno; 495 free((void *)p); 496 mem1: fts_lfree(head); 497 if (type == BREAD) 498 p->fts_info = FTS_ERR; 499 if (descend && CHDIR(sp, "..")) { 500 /* 501 * chdir error is more interesting 502 * than memory error, since it stops 503 * everything. 504 */ 505 saved_errno = errno; 506 SET(FTS__STOP); 507 } 508 errno = saved_errno; 509 (void)closedir(dirp); 510 return(NULL); 511 } 512 maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1; 513 } 514 515 p->fts_pathlen = len + dp->d_namlen + 1; 516 p->fts_accpath = ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; 517 518 p->fts_parent = sp->fts_cur; 519 p->fts_level = level; 520 521 if (nlinks) { 522 /* Make sure fts_stat has a filename to stat. */ 523 if (ISSET(FTS_NOCHDIR)) 524 bcopy(p->fts_name, cp, p->fts_namelen + 1); 525 p->fts_info = fts_stat(sp, p, 0); 526 if (nlinks > 0 && (p->fts_info == FTS_D || 527 p->fts_info == FTS_DNR || p->fts_info == FTS_DNX)) 528 --nlinks; 529 } else 530 p->fts_info = FTS_NS; 531 532 p->fts_link = head; 533 head = p; 534 ++nitems; 535 } 536 (void)closedir(dirp); 537 538 /* Reset the path. */ 539 if (cp - 1 > sp->fts_path) 540 --cp; 541 *cp = '\0'; 542 543 /* 544 * If descended: if were called from fts_read and didn't find anything, 545 * or were called from fts_children, get back. 546 */ 547 if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) { 548 SET(FTS__STOP); 549 p->fts_info = FTS_ERR; 550 return(NULL); 551 } 552 553 if (!nitems) { 554 if (type == BREAD) 555 p->fts_info = FTS_DP; 556 return(NULL); 557 } 558 559 if (sp->fts_compar && nitems > 1) 560 head = fts_sort(sp, head, nitems); 561 562 if (type == BREAD) { 563 *cp = '/'; 564 bcopy(head->fts_name, cp + 1, head->fts_namelen + 1); 565 } 566 return(head); 567 } 568 569 static u_short 570 fts_stat(sp, p, follow) 571 FTS *sp; 572 register FTSENT *p; 573 int follow; 574 { 575 /* 576 * If doing a logical walk, or application requested FTS_FOLLOW, do 577 * a stat(2). If that fails, either fail or do an lstat(2) for a 578 * non-existent symlink. (The check has to be done, or we wouldn't 579 * detect a symlink being deleted.) 580 * 581 * Don't leave errno set for FTS_NS cases. XXX 582 */ 583 if (ISSET(FTS_LOGICAL) || follow) { 584 if (stat(p->fts_accpath, &p->fts_statb)) { 585 errno = 0; 586 if (follow && !lstat(p->fts_accpath, &p->fts_statb)) 587 return(FTS_SLNONE); 588 else { 589 errno = 0; 590 return(FTS_NS); 591 } 592 } 593 } else if (lstat(p->fts_accpath, &p->fts_statb)) { 594 errno = 0; 595 return(FTS_NS); 596 } 597 598 if (S_ISDIR(p->fts_statb.st_mode)) 599 return(FTS_D); 600 if (S_ISLNK(p->fts_statb.st_mode)) 601 return(FTS_SL); 602 if (S_ISREG(p->fts_statb.st_mode)) 603 return(FTS_F); 604 return(FTS_DEFAULT); 605 } 606 607 static FTSENT * 608 fts_cycle(p) 609 register FTSENT *p; 610 { 611 register dev_t dev; 612 register ino_t ino; 613 614 /* 615 * Cycle detection is brute force; if the tree gets deep enough or 616 * the number of symbolic links to directories is really high 617 * something faster might be worthwhile. 618 */ 619 dev = p->fts_statb.st_dev; 620 ino = p->fts_statb.st_ino; 621 for (p = p->fts_parent; p->fts_level > ROOTLEVEL; p = p->fts_parent) 622 if (ino == p->fts_statb.st_ino && dev == p->fts_statb.st_dev) 623 return(p); 624 return(NULL); 625 } 626 627 #define R(type, nelem, ptr) \ 628 (type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type))) 629 630 static FTSENT * 631 fts_sort(sp, head, nitems) 632 FTS *sp; 633 FTSENT *head; 634 register int nitems; 635 { 636 register FTSENT **ap, *p; 637 638 /* 639 * Construct an array of pointers to the structures and call qsort(3). 640 * Reassemble the array in the order returned by qsort. If unable to 641 * sort for memory reasons, return the directory entries in their 642 * current order. Allocate enough space for the current needs plus 643 * 40 so we don't realloc one entry at a time. 644 */ 645 if (nitems > sp->fts_nitems) { 646 sp->fts_nitems = nitems + 40; 647 if (!(sp->fts_array = 648 R(FTSENT *, sp->fts_nitems, sp->fts_array))) { 649 sp->fts_nitems = 0; 650 return(head); 651 } 652 } 653 for (ap = sp->fts_array, p = head; p; p = p->fts_link) 654 *ap++ = p; 655 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar); 656 for (head = *(ap = sp->fts_array); --nitems; ++ap) 657 ap[0]->fts_link = ap[1]; 658 ap[0]->fts_link = NULL; 659 return(head); 660 } 661 662 static FTSENT * 663 fts_alloc(sp, name, len) 664 FTS *sp; 665 char *name; 666 register int len; 667 { 668 register FTSENT *p; 669 670 /* 671 * Variable sized structures; the name is the last element so 672 * allocate enough extra space after the structure to hold it. 673 */ 674 if (!(p = (FTSENT *)malloc((size_t)(sizeof(FTSENT) + len)))) 675 return(NULL); 676 bcopy(name, p->fts_name, len + 1); 677 p->fts_namelen = len; 678 p->fts_path = sp->fts_path; 679 p->fts_instr = FTS__NOINSTR; 680 p->fts_number = 0; 681 p->fts_pointer = NULL; 682 return(p); 683 } 684 685 static void 686 fts_lfree(head) 687 register FTSENT *head; 688 { 689 register FTSENT *p; 690 691 /* Free a linked list of structures. */ 692 while (p = head) { 693 head = head->fts_link; 694 free((void *)p); 695 } 696 } 697 698 /* 699 * Allow essentially unlimited paths; certain programs (find, rm, ls) need to 700 * work on any tree. Most systems will allow creation of paths much longer 701 * than MAXPATHLEN, even though the kernel won't resolve them. Add an extra 702 * 128 bytes to the requested size so that we don't realloc the path 2 bytes 703 * at a time. 704 */ 705 static char * 706 fts_path(sp, size) 707 FTS *sp; 708 int size; 709 { 710 sp->fts_pathlen += size + 128; 711 return(sp->fts_path = R(char, sp->fts_pathlen, sp->fts_path)); } 712 713 static FTSENT * 714 fts_root(sp, name) 715 FTS *sp; 716 register char *name; 717 { 718 register char *cp; 719 720 /* 721 * Rip trailing slashes; it's somewhat unclear in POSIX 1003.1 what 722 * /a/b/ really is, they don't talk about what a null path component 723 * resolves to. This hopefully does what the user intended. Don't 724 * allow null pathnames. 725 */ 726 for (cp = name; *cp; ++cp); 727 if (cp == name) { 728 errno = ENOENT; 729 return(NULL); 730 } 731 while (--cp > name && *cp == '/'); 732 *++cp = '\0'; 733 return(fts_alloc(sp, name, cp - name)); 734 } 735