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