1 /* 2 * Copyright (c) 1989 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms are permitted 6 * provided that the above copyright notice and this paragraph are 7 * duplicated in all such forms and that any documentation, 8 * advertising materials, and other materials related to such 9 * distribution and use acknowledge that the software was developed 10 * by the University of California, Berkeley. The name of the 11 * University may not be used to endorse or promote products derived 12 * from this software without specific prior written permission. 13 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 14 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 15 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 16 */ 17 18 #if defined(LIBC_SCCS) && !defined(lint) 19 static char sccsid[] = "@(#)fts.c 5.1 (Berkeley) 12/30/89"; 20 #endif /* LIBC_SCCS and not lint */ 21 22 #include <sys/param.h> 23 #include <sys/stat.h> 24 #include <dirent.h> 25 #include <errno.h> 26 #include <fts.h> 27 #include <strings.h> 28 29 extern int errno; 30 31 FTSENT *fts_alloc(), *fts_build(), *fts_cycle(), *fts_sort(), *fts_root(); 32 short fts_stat(); 33 char *malloc(), *realloc(); 34 35 /* 36 * Special case a root of "/" so that slashes aren't appended causing 37 * paths to be written as "//foo". 38 */ 39 #define NAPPEND(p) \ 40 (p->level == ROOTLEVEL && p->pathlen == 1 && \ 41 p->path[0] == '/' ? 0 : p->pathlen) 42 43 #define CHDIR(sp, path) (!(sp->options & FTS_NOCHDIR) && chdir(path)) 44 45 #define ROOTLEVEL 0 46 #define ROOTPARENTLEVEL -1 47 48 static FTS *stream; /* current stream pointer */ 49 50 FTS * 51 ftsopen(argv, options, compar) 52 char *argv[]; 53 register int options; 54 int (*compar)(); 55 { 56 register FTS *sp; 57 register FTSENT *p, *root; 58 register int nitems, maxlen; 59 FTSENT *parent, *tmp; 60 char wd[MAXPATHLEN], *getwd(), *strdup(); 61 62 /* allocate/initialize the stream */ 63 if (!(stream = sp = (FTS *)malloc((u_int)sizeof(FTS)))) 64 return(NULL); 65 bzero(sp, sizeof(FTS)); 66 sp->compar = compar; 67 sp->options = options; 68 69 /* allocate/initialize root's parent */ 70 if (!(parent = fts_alloc("", 0))) 71 goto mem1; 72 parent->level = ROOTPARENTLEVEL; 73 74 /* allocate/initialize root(s) */ 75 if (options & FTS_MULTIPLE) { 76 maxlen = -1; 77 for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) { 78 if (!(p = fts_root(*argv))) 79 goto mem2; 80 if (maxlen < p->namelen) 81 maxlen = p->namelen; 82 /* 83 * if comparison routine supplied, traverse in sorted 84 * order; otherwise traverse in the order specified. 85 */ 86 if (compar) { 87 p->link = root; 88 root = p; 89 p->accpath = p->name; 90 p->info = fts_stat(p, 0); 91 } else { 92 p->link = NULL; 93 if (!root) 94 tmp = root = p; 95 else { 96 tmp->link = p; 97 tmp = p; 98 } 99 } 100 p->level = ROOTLEVEL; 101 p->parent = parent; 102 } 103 if (compar && nitems > 1) 104 root = fts_sort(root, nitems); 105 } else { 106 if (!(root = fts_root((char *)argv))) 107 goto mem2; 108 maxlen = root->namelen; 109 root->link = NULL; 110 root->level = ROOTLEVEL; 111 root->parent = parent; 112 } 113 114 /* start out with at least 1K+ of path space */ 115 if (!fts_path(MAX(maxlen, MAXPATHLEN))) 116 goto mem2; 117 118 /* 119 * some minor trickiness. Set the pointers so that ftsread thinks 120 * we've just finished the node before the root(s); set p->info to 121 * FTS_NS so that everything about the "current" node is ignored. 122 * Rather than allocate a dummy node use the root's parent's link 123 * pointer. This is handled specially in ftsclose() as well. 124 */ 125 sp->cur = parent; 126 parent->link = root; 127 parent->info = FTS_NS; 128 129 /* 130 * if using chdir(2), do a getwd() to insure that we can get back 131 * here; this could be avoided for some paths, but probably not 132 * worth the effort. Slashes, symbolic links, and ".." are all 133 * fairly nasty problems. Note, if we can't get the current 134 * working directory we run anyway, just more slowly. 135 */ 136 if (!(options & FTS_NOCHDIR) && (!getwd(wd) || !(sp->wd = strdup(wd)))) 137 sp->options |= FTS_NOCHDIR; 138 139 return(sp); 140 141 mem2: fts_lfree(root); 142 (void)free((char *)parent); 143 mem1: (void)free((char *)sp); 144 return(NULL); 145 } 146 147 static 148 fts_load(p) 149 register FTSENT *p; 150 { 151 register int len; 152 register char *cp; 153 154 /* 155 * load the stream structure for the next traversal; set the 156 * accpath field specially so the chdir gets done to the right 157 * place and the user can access the first node. 158 */ 159 len = p->pathlen = p->namelen; 160 bcopy(p->name, stream->path, len + 1); 161 if ((cp = rindex(p->name, '/')) && (cp != p->name || cp[1])) { 162 len = strlen(++cp); 163 bcopy(cp, p->name, len + 1); 164 p->namelen = len; 165 } 166 p->accpath = p->path = stream->path; 167 } 168 169 ftsclose(sp) 170 FTS *sp; 171 { 172 register FTSENT *freep, *p; 173 int saved_errno; 174 175 if (sp->cur) 176 /* check for never having read anything */ 177 if (sp->cur->level == ROOTPARENTLEVEL) 178 fts_lfree(sp->cur); 179 else { 180 for (p = sp->cur; p->level > ROOTPARENTLEVEL;) { 181 freep = p; 182 p = p->link ? p->link : p->parent; 183 (void)free((char *)freep); 184 } 185 (void)free((char *)p); 186 } 187 188 /* free up child linked list, sort array, path buffer */ 189 if (sp->child) 190 fts_lfree(sp->child); 191 if (sp->array) 192 (void)free((char *)sp->array); 193 (void)free((char *)sp->path); 194 195 /* 196 * return to original directory, save errno if necessary; 197 * free up the directory buffer 198 */ 199 if (!(sp->options & FTS_NOCHDIR)) { 200 saved_errno = chdir(sp->wd) ? errno : 0; 201 (void)free(sp->wd); 202 } 203 204 /* free up the stream pointer */ 205 (void)free((char *)sp); 206 207 /* set errno and return */ 208 if (!(sp->options & FTS_NOCHDIR) && saved_errno) { 209 errno = saved_errno; 210 return(-1); 211 } 212 return(0); 213 } 214 215 FTSENT * 216 ftsread(sp) 217 register FTS *sp; 218 { 219 register FTSENT *p; 220 register int instr; 221 static int cd; 222 FTSENT *tmp; 223 char *cp; 224 225 /* if finished or unrecoverable error, return NULL */ 226 if (!sp->cur || sp->options & FTS__STOP) 227 return(NULL); 228 229 /* set global stream pointer, and current node pointer */ 230 stream = sp; 231 p = sp->cur; 232 233 /* save and zero out user instructions */ 234 instr = p->instr; 235 p->instr = 0; 236 237 /* if used link pointer for cycle detection, restore it */ 238 if (sp->savelink) { 239 p->link = sp->savelink; 240 sp->savelink = NULL; 241 } 242 243 /* any type of file may be re-visited; re-stat and return */ 244 if (instr == FTS_AGAIN) { 245 p->info = fts_stat(p, 0); 246 return(p); 247 } 248 249 if (p->info == FTS_D) 250 if (instr == FTS_SKIP) { 251 if (sp->child) { 252 fts_lfree(sp->child); 253 sp->child = NULL; 254 } 255 } else { 256 if (sp->child) { 257 /* cd into child directory */ 258 if (CHDIR(sp, p->accpath)) { 259 sp->options |= FTS__STOP; 260 p->info = FTS_ERR; 261 return(p); 262 } 263 } else if (!(sp->child = fts_build(sp, 1))) 264 return(p); 265 p = sp->child; 266 sp->child = NULL; 267 cp = sp->path + NAPPEND(p->parent); 268 *cp++ = '/'; 269 bcopy(p->name, cp, p->namelen + 1); 270 return(sp->cur = p); 271 } 272 else if (p->info == FTS_SL && instr == FTS_FOLLOW) { 273 p->info = fts_stat(p, 1); 274 return(p); 275 } 276 277 /* 278 * user may have called ftsset on pointer returned by 279 * ftschildren; handle it here. 280 */ 281 for (p = p->link; p;) { 282 instr = p->instr; 283 if (instr == FTS_FOLLOW) { 284 p->info = fts_stat(p, 1); 285 p->instr = 0; 286 break; 287 } 288 if (instr == FTS_SKIP) { 289 tmp = p; 290 p = p->link; 291 (void)free((char *)tmp); 292 continue; 293 } 294 p->instr = 0; 295 break; 296 } 297 298 /* go to next node on this level */ 299 if (p) { 300 /* 301 * if root level node, set up paths and return. If not the 302 * first time, and it's not an absolute pathname, get back 303 * to wherever we started from. 304 */ 305 if (p->level == ROOTLEVEL) { 306 fts_load(p); 307 if (cd) { 308 (void)free((char *)sp->cur); 309 if (p->path[0] != '/' && CHDIR(sp, sp->wd)) { 310 /* return target path for error msg */ 311 p->path = sp->wd; 312 p->info = FTS_ERR; 313 sp->options |= FTS__STOP; 314 return(sp->cur = p); 315 } 316 } else 317 cd = 1; 318 p->info = fts_stat(p, 0); 319 } else { 320 (void)free((char *)sp->cur); 321 cp = sp->path + NAPPEND(p->parent); 322 *cp++ = '/'; 323 bcopy(p->name, cp, p->namelen + 1); 324 if (p->info == FTS_D && (tmp = fts_cycle(p))) { 325 sp->savelink = p->link; 326 p->link = tmp; 327 } 328 } 329 return(sp->cur = p); 330 } 331 332 /* go to parent */ 333 p = sp->cur->parent; 334 (void)free((char *)sp->cur); 335 if (p->level == ROOTPARENTLEVEL) { 336 /* 337 * done; free everything up and set errno to 0 so the user 338 * can distinguish between error and EOF. 339 */ 340 (void)free((char *)p); 341 errno = 0; 342 return(sp->cur = NULL); 343 } 344 345 sp->path[p->pathlen] = '\0'; 346 if (CHDIR(sp, "..")) { 347 sp->options |= FTS__STOP; 348 p->info = FTS_ERR; 349 } else 350 p->info = FTS_DP; 351 return(sp->cur = p); 352 } 353 354 /* 355 * ftsset takes the stream as an argument although it's not used in this 356 * implementation; it would be necessary if anyone wanted to add global 357 * semantics to fts using ftsset. A possible error return is allowed for 358 * similar reasons. 359 */ 360 /* ARGSUSED */ 361 ftsset(sp, p, instr) 362 FTS *sp; 363 FTSENT *p; 364 int instr; 365 { 366 p->instr = instr; 367 return(0); 368 } 369 370 FTSENT * 371 ftschildren(sp) 372 register FTS *sp; 373 { 374 /* 375 * set errno to 0 so that user can tell the difference between an 376 * error and a directory without entries. 377 */ 378 errno = 0; 379 if (sp->cur->info != FTS_D || sp->options & FTS__STOP) 380 return(NULL); 381 if (sp->child) 382 fts_lfree(sp->child); 383 if (sp->child = fts_build(sp, 0)) { 384 /* 385 * have to cd up so that the fields of the current node 386 * as returned from readfts will be correct. 387 */ 388 if (CHDIR(sp, "..")) { 389 sp->options |= FTS__STOP; 390 return(NULL); 391 } 392 } 393 return(sp->child); 394 } 395 396 #define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2])) 397 398 static FTSENT * 399 fts_build(sp, set_node_errors) 400 register FTS *sp; 401 int set_node_errors; 402 { 403 register struct dirent *dp; 404 register FTSENT *p, *head; 405 register int nitems; 406 DIR *dirp; 407 int len, level, maxlen, nlinks, saved_errno; 408 char *cp; 409 410 p = sp->cur; 411 if (!(dirp = opendir(p->accpath))) { 412 if (set_node_errors) { 413 errno = 0; 414 p->info = FTS_DNR; 415 } 416 return(NULL); 417 } 418 if (CHDIR(sp, p->accpath)) { 419 if (set_node_errors) { 420 errno = 0; 421 p->info = FTS_DNX; 422 } 423 return(NULL); 424 } 425 426 /* 427 * the real slowdown in walking the tree is the stat calls. If 428 * FTS_NOSTAT is set and it's a physical walk (so that symbolic 429 * links can't be directories), fts assumes that the number of 430 * subdirectories in a node is equal to the number of links to 431 * the parent. This allows stat calls to be skipped in any leaf 432 * directories and for any nodes after the directories in the 433 * parent node have been found. This empirically cuts the stat 434 * calls by about 2/3. 435 */ 436 nlinks = sp->options & FTS_NOSTAT && sp->options & FTS_PHYSICAL ? 437 p->statb.st_nlink - (sp->options & FTS_SEEDOT ? 0 : 2) : -1; 438 439 /* get max file name length that can be stored in current path */ 440 maxlen = sp->pathlen - p->pathlen - 1; 441 442 cp = sp->path + (len = NAPPEND(p)); 443 *cp++ = '/'; 444 445 level = p->level + 1; 446 447 /* read the directory, attching each new entry to the `link' pointer */ 448 for (head = NULL, nitems = 0; dp = readdir(dirp);) { 449 if (ISDOT(dp->d_name) && !(sp->options & FTS_SEEDOT)) 450 continue; 451 452 if (!(p = fts_alloc(dp->d_name, dp->d_namlen))) { 453 saved_errno = errno; 454 goto mem1; 455 } 456 if (dp->d_namlen > maxlen) { 457 if (!fts_path((int)dp->d_namlen)) { 458 /* quit: this stream no longer has a path */ 459 sp->options |= FTS__STOP; 460 saved_errno = errno; 461 (void)free((char *)p); 462 mem1: fts_lfree(head); 463 if (set_node_errors) 464 p->info = FTS_ERR; 465 if (CHDIR(sp, "..")) { 466 saved_errno = errno; 467 sp->options |= FTS__STOP; 468 } 469 errno = saved_errno; 470 return(NULL); 471 } 472 maxlen = sp->pathlen - sp->cur->pathlen - 1; 473 } 474 475 p->pathlen = len + dp->d_namlen + 1; 476 p->accpath = sp->options & FTS_NOCHDIR ? p->path : p->name; 477 478 p->parent = sp->cur; 479 p->level = level; 480 481 if (nlinks) { 482 /* make sure fts_stat has a filename to stat */ 483 if (sp->options & FTS_NOCHDIR) 484 bcopy(p->name, cp, p->namelen + 1); 485 p->info = fts_stat(p, 0); 486 if (nlinks > 0 && (p->info == FTS_D || 487 p->info == FTS_DNR || p->info == FTS_DNX)) 488 --nlinks; 489 } else 490 p->info = FTS_NS; 491 492 p->link = head; 493 head = p; 494 ++nitems; 495 } 496 (void)closedir(dirp); 497 498 if (!nitems) { 499 if (CHDIR(sp, "..")) { 500 sp->options |= FTS__STOP; 501 p->info = FTS_ERR; 502 } else if (set_node_errors) 503 p->info = FTS_DP; 504 *--cp = '\0'; 505 return(NULL); 506 } 507 508 if (sp->compar && nitems > 1) 509 head = fts_sort(head, nitems); 510 511 if (set_node_errors) 512 bcopy(head->name, cp, head->namelen + 1); 513 else 514 *--cp = '\0'; 515 return(head); 516 } 517 518 static short 519 fts_stat(p, symflag) 520 register FTSENT *p; 521 int symflag; 522 { 523 register int ngroups, *gp; 524 int gidset[NGROUPS]; 525 526 /* 527 * detection of symbolic links w/o targets. If FTS_FOLLOW is set, 528 * the symlink structure is overwritten with the stat structure of 529 * the target. 530 */ 531 if (stream->options & FTS_LOGICAL || symflag) { 532 if (stat(p->accpath, &p->statb)) 533 return(symflag || !lstat(p->accpath, &p->statb) ? 534 FTS_SLNONE : FTS_ERR); 535 } else if (lstat(p->accpath, &p->statb)) 536 return(FTS_ERR); 537 538 switch(p->statb.st_mode&S_IFMT) { 539 case S_IFDIR: 540 /* get new uid/groups each time, they may have changed */ 541 if (getuid() == p->statb.st_uid) { 542 if (!(p->statb.st_mode&S_IRUSR)) 543 return(FTS_DNR); 544 if (!(p->statb.st_mode&S_IXUSR)) 545 return(FTS_DNX); 546 return(FTS_D); 547 } 548 if ((ngroups = getgroups(NGROUPS, gidset)) == -1) 549 return(FTS_ERR); 550 for (gp = gidset; ngroups--;) 551 if (*gp++ == p->statb.st_gid) { 552 if (!(p->statb.st_mode&S_IRGRP)) 553 return(FTS_DNR); 554 if (!(p->statb.st_mode&S_IXGRP)) 555 return(FTS_DNX); 556 return(FTS_D); 557 } 558 if (!(p->statb.st_mode&S_IROTH)) 559 return(FTS_DNR); 560 if (!(p->statb.st_mode&S_IXOTH)) 561 return(FTS_DNX); 562 return(FTS_D); 563 case S_IFLNK: 564 return(FTS_SL); 565 case S_IFREG: 566 return(FTS_F); 567 default: 568 return(FTS_DEFAULT); 569 } 570 /* NOTREACHED */ 571 } 572 573 static FTSENT * 574 fts_cycle(p) 575 register FTSENT *p; 576 { 577 register dev_t dev; 578 register ino_t ino; 579 580 /* 581 * cycle detection is brute force; if the tree gets deep enough or 582 * the number of symbolic links to directories is really high 583 * something faster might be worthwhile. 584 */ 585 dev = p->statb.st_dev; 586 ino = p->statb.st_ino; 587 for (p = p->parent; p->level > ROOTLEVEL; p = p->parent) 588 if (ino == p->statb.st_ino && dev == p->statb.st_dev) 589 return(p); 590 return(NULL); 591 } 592 593 #define R(type, nelem, ptr) \ 594 (type *)realloc((char *)ptr, (u_int)((nelem) * sizeof(type))) 595 596 static FTSENT * 597 fts_sort(head, nitems) 598 FTSENT *head; 599 register int nitems; 600 { 601 register FTSENT **ap, *p; 602 603 /* 604 * construct an array of pointers to the structures and call qsort(3). 605 * Reassemble the array in the order returned by qsort. If unable to 606 * sort for memory reasons, return the directory entries in their 607 * current order. Allocate enough space for the current needs plus 608 * 40 so we don't realloc one entry at a time. 609 */ 610 if (nitems > stream->nitems) { 611 stream->nitems = nitems + 40; 612 if (!(stream->array = 613 R(FTSENT *, stream->nitems, stream->array))) { 614 stream->nitems = 0; 615 return(head); 616 } 617 } 618 for (ap = stream->array, p = head; p; p = p->link) 619 *ap++ = p; 620 qsort((char *)stream->array, nitems, sizeof(FTSENT *), stream->compar); 621 for (head = *(ap = stream->array); --nitems; ++ap) 622 ap[0]->link = ap[1]; 623 ap[0]->link = NULL; 624 return(head); 625 } 626 627 static FTSENT * 628 fts_alloc(name, len) 629 char *name; 630 register int len; 631 { 632 register FTSENT *p; 633 634 /* 635 * variable sized structures; the name is the last element so 636 * allocate enough extra space after the structure to hold it. 637 */ 638 if (!(p = (FTSENT *)malloc((u_int)(sizeof(FTSENT) + len)))) 639 return(NULL); 640 bcopy(name, p->name, len + 1); 641 p->namelen = len; 642 p->path = stream->path; 643 p->instr = 0; 644 p->local.number = 0; 645 p->local.pointer = NULL; 646 return(p); 647 } 648 649 static 650 fts_lfree(head) 651 register FTSENT *head; 652 { 653 register FTSENT *p; 654 655 while (p = head) { 656 head = head->link; 657 (void)free((char *)p); 658 } 659 } 660 661 /* 662 * allow essentially unlimited paths; certain programs (find, remove, ls) 663 * need to work on any tree. Most systems will allow creation of paths 664 * much longer than MAXPATHLEN, even though the kernel won't resolve them. 665 * Add an extra 128 bytes to the requested size so that we don't realloc 666 * the path 2 bytes at a time. 667 */ 668 static 669 fts_path(size) 670 int size; 671 { 672 stream->pathlen += size + 128; 673 return((int)(stream->path = R(char, stream->pathlen, stream->path))); 674 } 675 676 static FTSENT * 677 fts_root(name) 678 register char *name; 679 { 680 register char *cp; 681 682 /* 683 * rip trailing slashes; it's somewhat unclear in POSIX 1003.1 what 684 * /a/b/ really is, they don't talk about what a null path component 685 * resolves to. This hopefully does what the user intended. Don't 686 * allow null pathnames. 687 */ 688 for (cp = name; *cp; ++cp); 689 if (cp == name) { 690 errno = ENOENT; 691 return(NULL); 692 } 693 while (--cp > name && *cp == '/'); 694 *++cp = '\0'; 695 return(fts_alloc(name, cp - name)); 696 } 697