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