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