1 #include "config.h" 2 3 #if HAVE_FTS 4 5 int dummy; 6 7 #else 8 9 /* $Id: compat_fts.c,v 1.14 2017/02/18 12:24:24 schwarze Exp $ */ 10 /* $OpenBSD: fts.c,v 1.56 2016/09/21 04:38:56 guenther Exp $ */ 11 12 /*- 13 * Copyright (c) 1990, 1993, 1994 14 * The Regents of the University of California. All rights reserved. 15 * 16 * Redistribution and use in source and binary forms, with or without 17 * modification, are permitted provided that the following conditions 18 * are met: 19 * 1. Redistributions of source code must retain the above copyright 20 * notice, this list of conditions and the following disclaimer. 21 * 2. Redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution. 24 * 3. Neither the name of the University nor the names of its contributors 25 * may be used to endorse or promote products derived from this software 26 * without specific prior written permission. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 29 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 31 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 37 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 38 * SUCH DAMAGE. 39 */ 40 41 #include <sys/stat.h> 42 #include <sys/types.h> 43 44 #include <dirent.h> 45 #include <errno.h> 46 #include <fcntl.h> 47 #include <limits.h> 48 #include <stdlib.h> 49 #include <string.h> 50 #include <unistd.h> 51 #include "compat_fts.h" 52 53 #define MAXIMUM(a, b) (((a) > (b)) ? (a) : (b)) 54 55 static FTSENT *fts_alloc(FTS *, const char *, size_t); 56 static FTSENT *fts_build(FTS *); 57 static void fts_lfree(FTSENT *); 58 static void fts_load(FTS *, FTSENT *); 59 static size_t fts_maxarglen(char * const *); 60 static void fts_padjust(FTS *, FTSENT *); 61 static int fts_palloc(FTS *, size_t); 62 static FTSENT *fts_sort(FTS *, FTSENT *, int); 63 static unsigned short fts_stat(FTS *, FTSENT *); 64 65 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2]))) 66 #ifndef O_CLOEXEC 67 #define O_CLOEXEC 0 68 #endif 69 70 #define CLR(opt) (sp->fts_options &= ~(opt)) 71 #define ISSET(opt) (sp->fts_options & (opt)) 72 #define SET(opt) (sp->fts_options |= (opt)) 73 74 FTS * 75 fts_open(char * const *argv, int options, 76 int (*compar)(const FTSENT **, const FTSENT **)) 77 { 78 FTS *sp; 79 FTSENT *p, *root; 80 int nitems; 81 FTSENT *parent, *prev; 82 83 /* Options check. */ 84 if (options & ~FTS_OPTIONMASK) { 85 errno = EINVAL; 86 return (NULL); 87 } 88 89 /* At least one path must be specified. */ 90 if (*argv == NULL) { 91 errno = EINVAL; 92 return (NULL); 93 } 94 95 /* Allocate/initialize the stream */ 96 if ((sp = calloc(1, sizeof(FTS))) == NULL) 97 return (NULL); 98 sp->fts_compar = compar; 99 sp->fts_options = options; 100 101 /* 102 * Start out with 1K of path space, and enough, in any case, 103 * to hold the user's paths. 104 */ 105 if (fts_palloc(sp, MAXIMUM(fts_maxarglen(argv), PATH_MAX))) 106 goto mem1; 107 108 /* Allocate/initialize root's parent. */ 109 if ((parent = fts_alloc(sp, "", 0)) == NULL) 110 goto mem2; 111 parent->fts_level = FTS_ROOTPARENTLEVEL; 112 113 /* Allocate/initialize root(s). */ 114 for (root = prev = NULL, nitems = 0; *argv; ++argv, ++nitems) { 115 if ((p = fts_alloc(sp, *argv, strlen(*argv))) == NULL) 116 goto mem3; 117 p->fts_level = FTS_ROOTLEVEL; 118 p->fts_parent = parent; 119 p->fts_accpath = p->fts_name; 120 p->fts_info = fts_stat(sp, p); 121 122 /* Command-line "." and ".." are real directories. */ 123 if (p->fts_info == FTS_DOT) 124 p->fts_info = FTS_D; 125 126 /* 127 * If comparison routine supplied, traverse in sorted 128 * order; otherwise traverse in the order specified. 129 */ 130 if (compar) { 131 p->fts_link = root; 132 root = p; 133 } else { 134 p->fts_link = NULL; 135 if (root == NULL) 136 root = p; 137 else 138 prev->fts_link = p; 139 prev = p; 140 } 141 } 142 if (compar && nitems > 1) 143 root = fts_sort(sp, root, nitems); 144 145 /* 146 * Allocate a dummy pointer and make fts_read think that we've just 147 * finished the node before the root(s); set p->fts_info to FTS_INIT 148 * so that everything about the "current" node is ignored. 149 */ 150 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL) 151 goto mem3; 152 sp->fts_cur->fts_link = root; 153 sp->fts_cur->fts_info = FTS_INIT; 154 155 if (nitems == 0) 156 free(parent); 157 158 return (sp); 159 160 mem3: fts_lfree(root); 161 free(parent); 162 mem2: free(sp->fts_path); 163 mem1: free(sp); 164 return (NULL); 165 } 166 167 static void 168 fts_load(FTS *sp, FTSENT *p) 169 { 170 size_t len; 171 char *cp; 172 173 /* 174 * Load the stream structure for the next traversal. Since we don't 175 * actually enter the directory until after the preorder visit, set 176 * the fts_accpath field specially so the chdir gets done to the right 177 * place and the user can access the first node. From fts_open it's 178 * known that the path will fit. 179 */ 180 len = p->fts_pathlen = p->fts_namelen; 181 memmove(sp->fts_path, p->fts_name, len + 1); 182 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { 183 len = strlen(++cp); 184 memmove(p->fts_name, cp, len + 1); 185 p->fts_namelen = len; 186 } 187 p->fts_accpath = p->fts_path = sp->fts_path; 188 sp->fts_dev = p->fts_dev; 189 } 190 191 int 192 fts_close(FTS *sp) 193 { 194 FTSENT *freep, *p; 195 196 /* 197 * This still works if we haven't read anything -- the dummy structure 198 * points to the root list, so we step through to the end of the root 199 * list which has a valid parent pointer. 200 */ 201 if (sp->fts_cur) { 202 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { 203 freep = p; 204 p = p->fts_link ? p->fts_link : p->fts_parent; 205 free(freep); 206 } 207 free(p); 208 } 209 210 /* Free up child linked list, sort array, path buffer, stream ptr.*/ 211 if (sp->fts_child) 212 fts_lfree(sp->fts_child); 213 free(sp->fts_array); 214 free(sp->fts_path); 215 free(sp); 216 217 return (0); 218 } 219 220 /* 221 * Special case of "/" at the end of the path so that slashes aren't 222 * appended which would cause paths to be written as "....//foo". 223 */ 224 #define NAPPEND(p) \ 225 (p->fts_path[p->fts_pathlen - 1] == '/' \ 226 ? p->fts_pathlen - 1 : p->fts_pathlen) 227 228 FTSENT * 229 fts_read(FTS *sp) 230 { 231 FTSENT *p, *tmp; 232 int instr; 233 char *t; 234 235 /* If finished or unrecoverable error, return NULL. */ 236 if (sp->fts_cur == NULL || ISSET(FTS_STOP)) 237 return (NULL); 238 239 /* Set current node pointer. */ 240 p = sp->fts_cur; 241 242 /* Save and zero out user instructions. */ 243 instr = p->fts_instr; 244 p->fts_instr = FTS_NOINSTR; 245 246 /* Directory in pre-order. */ 247 if (p->fts_info == FTS_D) { 248 /* If skipped or crossed mount point, do post-order visit. */ 249 if (instr == FTS_SKIP || 250 (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) { 251 if (sp->fts_child) { 252 fts_lfree(sp->fts_child); 253 sp->fts_child = NULL; 254 } 255 p->fts_info = FTS_DP; 256 return (p); 257 } 258 259 /* 260 * If haven't read do so. If the read fails, fts_build sets 261 * FTS_STOP or the fts_info field of the node. 262 */ 263 if (sp->fts_child) { 264 /* nothing */ 265 } else if ((sp->fts_child = fts_build(sp)) == NULL) { 266 if (ISSET(FTS_STOP)) 267 return (NULL); 268 return (p); 269 } 270 p = sp->fts_child; 271 sp->fts_child = NULL; 272 goto name; 273 } 274 275 /* Move to the next node on this level. */ 276 next: tmp = p; 277 if ((p = p->fts_link)) { 278 free(tmp); 279 280 /* 281 * If reached the top, return to the original directory (or 282 * the root of the tree), and load the paths for the next root. 283 */ 284 if (p->fts_level == FTS_ROOTLEVEL) { 285 fts_load(sp, p); 286 return (sp->fts_cur = p); 287 } 288 289 /* 290 * User may have called fts_set on the node. If skipped, 291 * ignore. If followed, get a file descriptor so we can 292 * get back if necessary. 293 */ 294 if (p->fts_instr == FTS_SKIP) 295 goto next; 296 297 name: t = sp->fts_path + NAPPEND(p->fts_parent); 298 *t++ = '/'; 299 memmove(t, p->fts_name, p->fts_namelen + 1); 300 return (sp->fts_cur = p); 301 } 302 303 /* Move up to the parent node. */ 304 p = tmp->fts_parent; 305 free(tmp); 306 307 if (p->fts_level == FTS_ROOTPARENTLEVEL) { 308 /* 309 * Done; free everything up and set errno to 0 so the user 310 * can distinguish between error and EOF. 311 */ 312 free(p); 313 errno = 0; 314 return (sp->fts_cur = NULL); 315 } 316 317 /* NUL terminate the pathname. */ 318 sp->fts_path[p->fts_pathlen] = '\0'; 319 320 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP; 321 return (sp->fts_cur = p); 322 } 323 324 /* 325 * Fts_set takes the stream as an argument although it's not used in this 326 * implementation; it would be necessary if anyone wanted to add global 327 * semantics to fts using fts_set. An error return is allowed for similar 328 * reasons. 329 */ 330 int 331 fts_set(FTS *sp, FTSENT *p, int instr) 332 { 333 if (instr && instr != FTS_NOINSTR && instr != FTS_SKIP) { 334 errno = EINVAL; 335 return (1); 336 } 337 p->fts_instr = instr; 338 return (0); 339 } 340 341 /* 342 * This is the tricky part -- do not casually change *anything* in here. The 343 * idea is to build the linked list of entries that are used by fts_children 344 * and fts_read. There are lots of special cases. 345 * 346 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is 347 * set and it's a physical walk (so that symbolic links can't be directories), 348 * we can do things quickly. First, if it's a 4.4BSD file system, the type 349 * of the file is in the directory entry. Otherwise, we assume that the number 350 * of subdirectories in a node is equal to the number of links to the parent. 351 * The former skips all stat calls. The latter skips stat calls in any leaf 352 * directories and for any files after the subdirectories in the directory have 353 * been found, cutting the stat calls by about 2/3. 354 */ 355 static FTSENT * 356 fts_build(FTS *sp) 357 { 358 struct dirent *dp; 359 FTSENT *p, *head; 360 FTSENT *cur, *tail; 361 DIR *dirp; 362 void *oldaddr; 363 size_t dlen, len, maxlen; 364 int nitems, level, doadjust; 365 int saved_errno; 366 char *cp; 367 368 /* Set current node pointer. */ 369 cur = sp->fts_cur; 370 371 /* 372 * Open the directory for reading. If this fails, we're done. 373 * If being called from fts_read, set the fts_info field. 374 */ 375 if ((dirp = opendir(cur->fts_accpath)) == NULL) { 376 cur->fts_info = FTS_DNR; 377 cur->fts_errno = errno; 378 return (NULL); 379 } 380 381 /* 382 * Figure out the max file name length that can be stored in the 383 * current path -- the inner loop allocates more path as necessary. 384 * We really wouldn't have to do the maxlen calculations here, we 385 * could do them in fts_read before returning the path, but it's a 386 * lot easier here since the length is part of the dirent structure. 387 * 388 * If not changing directories set a pointer so that can just append 389 * each new name into the path. 390 */ 391 len = NAPPEND(cur); 392 cp = sp->fts_path + len; 393 *cp++ = '/'; 394 len++; 395 maxlen = sp->fts_pathlen - len; 396 397 /* 398 * fts_level is signed so we must prevent it from wrapping 399 * around to FTS_ROOTLEVEL and FTS_ROOTPARENTLEVEL. 400 */ 401 level = cur->fts_level; 402 if (level < FTS_MAXLEVEL) 403 level++; 404 405 /* Read the directory, attaching each entry to the `link' pointer. */ 406 doadjust = 0; 407 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) { 408 if (ISDOT(dp->d_name)) 409 continue; 410 411 #if HAVE_DIRENT_NAMLEN 412 dlen = dp->d_namlen; 413 #else 414 dlen = strlen(dp->d_name); 415 #endif 416 417 if (!(p = fts_alloc(sp, dp->d_name, dlen))) 418 goto mem1; 419 if (dlen >= maxlen) { /* include space for NUL */ 420 oldaddr = sp->fts_path; 421 if (fts_palloc(sp, dlen + len + 1)) { 422 /* 423 * No more memory for path or structures. Save 424 * errno, free up the current structure and the 425 * structures already allocated. 426 */ 427 mem1: saved_errno = errno; 428 free(p); 429 fts_lfree(head); 430 (void)closedir(dirp); 431 cur->fts_info = FTS_ERR; 432 SET(FTS_STOP); 433 errno = saved_errno; 434 return (NULL); 435 } 436 /* Did realloc() change the pointer? */ 437 if (oldaddr != sp->fts_path) { 438 doadjust = 1; 439 cp = sp->fts_path + len; 440 } 441 maxlen = sp->fts_pathlen - len; 442 } 443 444 p->fts_level = level; 445 p->fts_parent = sp->fts_cur; 446 p->fts_pathlen = len + dlen; 447 if (p->fts_pathlen < len) { 448 /* 449 * If we wrap, free up the current structure and 450 * the structures already allocated, then error 451 * out with ENAMETOOLONG. 452 */ 453 free(p); 454 fts_lfree(head); 455 (void)closedir(dirp); 456 cur->fts_info = FTS_ERR; 457 SET(FTS_STOP); 458 errno = ENAMETOOLONG; 459 return (NULL); 460 } 461 462 /* Build a file name for fts_stat to stat. */ 463 p->fts_accpath = p->fts_path; 464 memmove(cp, p->fts_name, p->fts_namelen + 1); 465 /* Stat it. */ 466 p->fts_info = fts_stat(sp, p); 467 468 /* We walk in directory order so "ls -f" doesn't get upset. */ 469 p->fts_link = NULL; 470 if (head == NULL) 471 head = tail = p; 472 else { 473 tail->fts_link = p; 474 tail = p; 475 } 476 ++nitems; 477 } 478 if (dirp) 479 (void)closedir(dirp); 480 481 /* 482 * If realloc() changed the address of the path, adjust the 483 * addresses for the rest of the tree and the dir list. 484 */ 485 if (doadjust) 486 fts_padjust(sp, head); 487 488 /* 489 * If not changing directories, reset the path back to original 490 * state. 491 */ 492 if (len == sp->fts_pathlen || nitems == 0) 493 --cp; 494 *cp = '\0'; 495 496 /* If didn't find anything, return NULL. */ 497 if (!nitems) { 498 cur->fts_info = FTS_DP; 499 return (NULL); 500 } 501 502 /* Sort the entries. */ 503 if (sp->fts_compar && nitems > 1) 504 head = fts_sort(sp, head, nitems); 505 return (head); 506 } 507 508 static unsigned short 509 fts_stat(FTS *sp, FTSENT *p) 510 { 511 FTSENT *t; 512 dev_t dev; 513 ino_t ino; 514 struct stat *sbp; 515 516 /* If user needs stat info, stat buffer already allocated. */ 517 sbp = p->fts_statp; 518 519 if (lstat(p->fts_accpath, sbp)) { 520 p->fts_errno = errno; 521 memset(sbp, 0, sizeof(struct stat)); 522 return (FTS_NS); 523 } 524 525 if (S_ISDIR(sbp->st_mode)) { 526 /* 527 * Set the device/inode. Used to find cycles and check for 528 * crossing mount points. Also remember the link count, used 529 * in fts_build to limit the number of stat calls. It is 530 * understood that these fields are only referenced if fts_info 531 * is set to FTS_D. 532 */ 533 dev = p->fts_dev = sbp->st_dev; 534 ino = p->fts_ino = sbp->st_ino; 535 p->fts_nlink = sbp->st_nlink; 536 537 if (ISDOT(p->fts_name)) 538 return (FTS_DOT); 539 540 /* 541 * Cycle detection is done by brute force when the directory 542 * is first encountered. If the tree gets deep enough or the 543 * number of symbolic links to directories is high enough, 544 * something faster might be worthwhile. 545 */ 546 for (t = p->fts_parent; 547 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) 548 if (ino == t->fts_ino && dev == t->fts_dev) { 549 p->fts_cycle = t; 550 return (FTS_DC); 551 } 552 return (FTS_D); 553 } 554 if (S_ISLNK(sbp->st_mode)) 555 return (FTS_SL); 556 if (S_ISREG(sbp->st_mode)) 557 return (FTS_F); 558 return (FTS_DEFAULT); 559 } 560 561 static FTSENT * 562 fts_sort(FTS *sp, FTSENT *head, int nitems) 563 { 564 FTSENT **ap, *p; 565 566 /* 567 * Construct an array of pointers to the structures and call qsort(3). 568 * Reassemble the array in the order returned by qsort. If unable to 569 * sort for memory reasons, return the directory entries in their 570 * current order. Allocate enough space for the current needs plus 571 * 40 so don't realloc one entry at a time. 572 */ 573 if (nitems > sp->fts_nitems) { 574 struct _ftsent **a; 575 576 sp->fts_nitems = nitems + 40; 577 if ((a = reallocarray(sp->fts_array, 578 sp->fts_nitems, sizeof(FTSENT *))) == NULL) { 579 free(sp->fts_array); 580 sp->fts_array = NULL; 581 sp->fts_nitems = 0; 582 return (head); 583 } 584 sp->fts_array = a; 585 } 586 for (ap = sp->fts_array, p = head; p; p = p->fts_link) 587 *ap++ = p; 588 qsort(sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar); 589 for (head = *(ap = sp->fts_array); --nitems; ++ap) 590 ap[0]->fts_link = ap[1]; 591 ap[0]->fts_link = NULL; 592 return (head); 593 } 594 595 static FTSENT * 596 fts_alloc(FTS *sp, const char *name, size_t namelen) 597 { 598 FTSENT *p; 599 size_t len; 600 601 len = sizeof(FTSENT) + namelen; 602 if ((p = calloc(1, len)) == NULL) 603 return (NULL); 604 605 p->fts_path = sp->fts_path; 606 p->fts_namelen = namelen; 607 p->fts_instr = FTS_NOINSTR; 608 p->fts_statp = malloc(sizeof(struct stat)); 609 if (p->fts_statp == NULL) { 610 free(p); 611 return (NULL); 612 } 613 memcpy(p->fts_name, name, namelen); 614 615 return (p); 616 } 617 618 static void 619 fts_lfree(FTSENT *head) 620 { 621 FTSENT *p; 622 623 /* Free a linked list of structures. */ 624 while ((p = head)) { 625 head = head->fts_link; 626 free(p); 627 } 628 } 629 630 /* 631 * Allow essentially unlimited paths; find, rm, ls should all work on any tree. 632 * Most systems will allow creation of paths much longer than PATH_MAX, even 633 * though the kernel won't resolve them. Add the size (not just what's needed) 634 * plus 256 bytes so don't realloc the path 2 bytes at a time. 635 */ 636 static int 637 fts_palloc(FTS *sp, size_t more) 638 { 639 char *p; 640 641 /* 642 * Check for possible wraparound. 643 */ 644 more += 256; 645 if (sp->fts_pathlen + more < sp->fts_pathlen) { 646 free(sp->fts_path); 647 sp->fts_path = NULL; 648 errno = ENAMETOOLONG; 649 return (1); 650 } 651 sp->fts_pathlen += more; 652 p = realloc(sp->fts_path, sp->fts_pathlen); 653 if (p == NULL) { 654 free(sp->fts_path); 655 sp->fts_path = NULL; 656 return (1); 657 } 658 sp->fts_path = p; 659 return (0); 660 } 661 662 /* 663 * When the path is realloc'd, have to fix all of the pointers in structures 664 * already returned. 665 */ 666 static void 667 fts_padjust(FTS *sp, FTSENT *head) 668 { 669 FTSENT *p; 670 char *addr = sp->fts_path; 671 672 #define ADJUST(p) { \ 673 if ((p)->fts_accpath != (p)->fts_name) { \ 674 (p)->fts_accpath = \ 675 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \ 676 } \ 677 (p)->fts_path = addr; \ 678 } 679 /* Adjust the current set of children. */ 680 for (p = sp->fts_child; p; p = p->fts_link) 681 ADJUST(p); 682 683 /* Adjust the rest of the tree, including the current level. */ 684 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) { 685 ADJUST(p); 686 p = p->fts_link ? p->fts_link : p->fts_parent; 687 } 688 } 689 690 static size_t 691 fts_maxarglen(char * const *argv) 692 { 693 size_t len, max; 694 695 for (max = 0; *argv; ++argv) 696 if ((len = strlen(*argv)) > max) 697 max = len; 698 return (max + 1); 699 } 700 701 #endif 702