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