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