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