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