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