1 /* Traverse a file hierarchy. 2 3 Copyright (C) 2004-2015 Free Software Foundation, Inc. 4 5 This program is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 17 18 /*- 19 * Copyright (c) 1990, 1993, 1994 20 * The Regents of the University of California. All rights reserved. 21 * 22 * Redistribution and use in source and binary forms, with or without 23 * modification, are permitted provided that the following conditions 24 * are met: 25 * 1. Redistributions of source code must retain the above copyright 26 * notice, this list of conditions and the following disclaimer. 27 * 2. Redistributions in binary form must reproduce the above copyright 28 * notice, this list of conditions and the following disclaimer in the 29 * documentation and/or other materials provided with the distribution. 30 * 4. Neither the name of the University nor the names of its contributors 31 * may be used to endorse or promote products derived from this software 32 * without specific prior written permission. 33 * 34 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" AND 35 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 36 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 37 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 38 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 39 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 40 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 41 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 42 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 43 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 44 * SUCH DAMAGE. 45 */ 46 47 #include <config.h> 48 49 #if defined(LIBC_SCCS) && !defined(lint) 50 static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94"; 51 #endif /* LIBC_SCCS and not lint */ 52 53 #include "fts_.h" 54 55 #if HAVE_SYS_PARAM_H || defined _LIBC 56 # include <sys/param.h> 57 #endif 58 #ifdef _LIBC 59 # include <include/sys/stat.h> 60 #else 61 # include <sys/stat.h> 62 #endif 63 #include <fcntl.h> 64 #include <errno.h> 65 #include <stdalign.h> 66 #include <stdbool.h> 67 #include <stddef.h> 68 #include <stdlib.h> 69 #include <string.h> 70 #include <unistd.h> 71 72 #if ! _LIBC 73 # include "fcntl--.h" 74 # include "dirent--.h" 75 # include "unistd--.h" 76 /* FIXME - use fcntl(F_DUPFD_CLOEXEC)/openat(O_CLOEXEC) once they are 77 supported. */ 78 # include "cloexec.h" 79 # include "openat.h" 80 # include "same-inode.h" 81 #endif 82 83 #include <dirent.h> 84 #ifndef _D_EXACT_NAMLEN 85 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name) 86 #endif 87 88 #if HAVE_STRUCT_DIRENT_D_TYPE 89 /* True if the type of the directory entry D is known. */ 90 # define DT_IS_KNOWN(d) ((d)->d_type != DT_UNKNOWN) 91 /* True if the type of the directory entry D must be T. */ 92 # define DT_MUST_BE(d, t) ((d)->d_type == (t)) 93 # define D_TYPE(d) ((d)->d_type) 94 #else 95 # define DT_IS_KNOWN(d) false 96 # define DT_MUST_BE(d, t) false 97 # define D_TYPE(d) DT_UNKNOWN 98 99 # undef DT_UNKNOWN 100 # define DT_UNKNOWN 0 101 102 /* Any nonzero values will do here, so long as they're distinct. 103 Undef any existing macros out of the way. */ 104 # undef DT_BLK 105 # undef DT_CHR 106 # undef DT_DIR 107 # undef DT_FIFO 108 # undef DT_LNK 109 # undef DT_REG 110 # undef DT_SOCK 111 # define DT_BLK 1 112 # define DT_CHR 2 113 # define DT_DIR 3 114 # define DT_FIFO 4 115 # define DT_LNK 5 116 # define DT_REG 6 117 # define DT_SOCK 7 118 #endif 119 120 #ifndef S_IFLNK 121 # define S_IFLNK 0 122 #endif 123 #ifndef S_IFSOCK 124 # define S_IFSOCK 0 125 #endif 126 127 enum 128 { 129 NOT_AN_INODE_NUMBER = 0 130 }; 131 132 #ifdef D_INO_IN_DIRENT 133 # define D_INO(dp) (dp)->d_ino 134 #else 135 /* Some systems don't have inodes, so fake them to avoid lots of ifdefs. */ 136 # define D_INO(dp) NOT_AN_INODE_NUMBER 137 #endif 138 139 /* If possible (see max_entries, below), read no more than this many directory 140 entries at a time. Without this limit (i.e., when using non-NULL 141 fts_compar), processing a directory with 4,000,000 entries requires ~1GiB 142 of memory, and handling 64M entries would require 16GiB of memory. */ 143 #ifndef FTS_MAX_READDIR_ENTRIES 144 # define FTS_MAX_READDIR_ENTRIES 100000 145 #endif 146 147 /* If there are more than this many entries in a directory, 148 and the conditions mentioned below are satisfied, then sort 149 the entries on inode number before any further processing. */ 150 #ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 151 # define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000 152 #endif 153 154 enum 155 { 156 _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD = FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 157 }; 158 159 enum Fts_stat 160 { 161 FTS_NO_STAT_REQUIRED = 1, 162 FTS_STAT_REQUIRED = 2 163 }; 164 165 #ifdef _LIBC 166 # undef close 167 # define close __close 168 # undef closedir 169 # define closedir __closedir 170 # undef fchdir 171 # define fchdir __fchdir 172 # undef open 173 # define open __open 174 # undef readdir 175 # define readdir __readdir 176 #else 177 # undef internal_function 178 # define internal_function /* empty */ 179 #endif 180 181 #ifndef __set_errno 182 # define __set_errno(Val) errno = (Val) 183 #endif 184 185 /* If this host provides the openat function, then we can avoid 186 attempting to open "." in some initialization code below. */ 187 #ifdef HAVE_OPENAT 188 # define HAVE_OPENAT_SUPPORT 1 189 #else 190 # define HAVE_OPENAT_SUPPORT 0 191 #endif 192 193 #ifdef NDEBUG 194 # define fts_assert(expr) ((void) (0 && (expr))) 195 #else 196 # define fts_assert(expr) \ 197 do \ 198 { \ 199 if (!(expr)) \ 200 abort (); \ 201 } \ 202 while (false) 203 #endif 204 205 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function; 206 static FTSENT *fts_build (FTS *, int) internal_function; 207 static void fts_lfree (FTSENT *) internal_function; 208 static void fts_load (FTS *, FTSENT *) internal_function; 209 static size_t fts_maxarglen (char * const *) internal_function; 210 static void fts_padjust (FTS *, FTSENT *) internal_function; 211 static bool fts_palloc (FTS *, size_t) internal_function; 212 static FTSENT *fts_sort (FTS *, FTSENT *, size_t) internal_function; 213 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function; 214 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *) 215 internal_function; 216 217 #include "fts-cycle.c" 218 219 #ifndef MAX 220 # define MAX(a,b) ((a) > (b) ? (a) : (b)) 221 #endif 222 223 #ifndef SIZE_MAX 224 # define SIZE_MAX ((size_t) -1) 225 #endif 226 227 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2]))) 228 #define STREQ(a, b) (strcmp (a, b) == 0) 229 230 #define CLR(opt) (sp->fts_options &= ~(opt)) 231 #define ISSET(opt) (sp->fts_options & (opt)) 232 #define SET(opt) (sp->fts_options |= (opt)) 233 234 /* FIXME: FTS_NOCHDIR is now misnamed. 235 Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */ 236 #define FCHDIR(sp, fd) \ 237 (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \ 238 ? (cwd_advance_fd ((sp), (fd), true), 0) \ 239 : fchdir (fd))) 240 241 242 /* fts_build flags */ 243 /* FIXME: make this an enum */ 244 #define BCHILD 1 /* fts_children */ 245 #define BNAMES 2 /* fts_children, names only */ 246 #define BREAD 3 /* fts_read */ 247 248 #if FTS_DEBUG 249 # include <inttypes.h> 250 # include <stdint.h> 251 # include <stdio.h> 252 # include "getcwdat.h" 253 bool fts_debug = false; 254 # define Dprintf(x) do { if (fts_debug) printf x; } while (false) 255 #else 256 # define Dprintf(x) 257 # define fd_ring_check(x) 258 # define fd_ring_print(a, b, c) 259 #endif 260 261 #define LEAVE_DIR(Fts, Ent, Tag) \ 262 do \ 263 { \ 264 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \ 265 leave_dir (Fts, Ent); \ 266 fd_ring_check (Fts); \ 267 } \ 268 while (false) 269 270 static void 271 fd_ring_clear (I_ring *fd_ring) 272 { 273 while ( ! i_ring_empty (fd_ring)) 274 { 275 int fd = i_ring_pop (fd_ring); 276 if (0 <= fd) 277 close (fd); 278 } 279 } 280 281 /* Overload the fts_statp->st_size member (otherwise unused, when 282 fts_info is FTS_NSOK) to indicate whether fts_read should stat 283 this entry or not. */ 284 static void 285 fts_set_stat_required (FTSENT *p, bool required) 286 { 287 fts_assert (p->fts_info == FTS_NSOK); 288 p->fts_statp->st_size = (required 289 ? FTS_STAT_REQUIRED 290 : FTS_NO_STAT_REQUIRED); 291 } 292 293 /* file-descriptor-relative opendir. */ 294 /* FIXME: if others need this function, move it into lib/openat.c */ 295 static DIR * 296 internal_function 297 opendirat (int fd, char const *dir, int extra_flags, int *pdir_fd) 298 { 299 int new_fd = openat (fd, dir, 300 (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK 301 | extra_flags)); 302 DIR *dirp; 303 304 if (new_fd < 0) 305 return NULL; 306 set_cloexec_flag (new_fd, true); 307 dirp = fdopendir (new_fd); 308 if (dirp) 309 *pdir_fd = new_fd; 310 else 311 { 312 int saved_errno = errno; 313 close (new_fd); 314 errno = saved_errno; 315 } 316 return dirp; 317 } 318 319 /* Virtual fchdir. Advance SP's working directory file descriptor, 320 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring. 321 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory 322 open on sp->fts_cwd_fd; i.e., to move the working directory one level 323 down. */ 324 static void 325 internal_function 326 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one) 327 { 328 int old = sp->fts_cwd_fd; 329 fts_assert (old != fd || old == AT_FDCWD); 330 331 if (chdir_down_one) 332 { 333 /* Push "old" onto the ring. 334 If the displaced file descriptor is non-negative, close it. */ 335 int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old); 336 fd_ring_print (sp, stderr, "post-push"); 337 if (0 <= prev_fd_in_slot) 338 close (prev_fd_in_slot); /* ignore any close failure */ 339 } 340 else if ( ! ISSET (FTS_NOCHDIR)) 341 { 342 if (0 <= old) 343 close (old); /* ignore any close failure */ 344 } 345 346 sp->fts_cwd_fd = fd; 347 } 348 349 /* Restore the initial, pre-traversal, "working directory". 350 In FTS_CWDFD mode, we merely call cwd_advance_fd, otherwise, 351 we may actually change the working directory. 352 Return 0 upon success. Upon failure, set errno and return nonzero. */ 353 static int 354 restore_initial_cwd (FTS *sp) 355 { 356 int fail = FCHDIR (sp, ISSET (FTS_CWDFD) ? AT_FDCWD : sp->fts_rfd); 357 fd_ring_clear (&(sp->fts_fd_ring)); 358 return fail; 359 } 360 361 /* Open the directory DIR if possible, and return a file 362 descriptor. Return -1 and set errno on failure. It doesn't matter 363 whether the file descriptor has read or write access. */ 364 365 static int 366 internal_function 367 diropen (FTS const *sp, char const *dir) 368 { 369 int open_flags = (O_SEARCH | O_DIRECTORY | O_NOCTTY | O_NONBLOCK 370 | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0) 371 | (ISSET (FTS_NOATIME) ? O_NOATIME : 0)); 372 373 int fd = (ISSET (FTS_CWDFD) 374 ? openat (sp->fts_cwd_fd, dir, open_flags) 375 : open (dir, open_flags)); 376 if (0 <= fd) 377 set_cloexec_flag (fd, true); 378 return fd; 379 } 380 381 FTS * 382 fts_open (char * const *argv, 383 register int options, 384 int (*compar) (FTSENT const **, FTSENT const **)) 385 { 386 register FTS *sp; 387 register FTSENT *p, *root; 388 register size_t nitems; 389 FTSENT *parent = NULL; 390 FTSENT *tmp = NULL; /* pacify gcc */ 391 bool defer_stat; 392 393 /* Options check. */ 394 if (options & ~FTS_OPTIONMASK) { 395 __set_errno (EINVAL); 396 return (NULL); 397 } 398 if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) { 399 __set_errno (EINVAL); 400 return (NULL); 401 } 402 if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) { 403 __set_errno (EINVAL); 404 return (NULL); 405 } 406 407 /* Allocate/initialize the stream */ 408 if ((sp = malloc(sizeof(FTS))) == NULL) 409 return (NULL); 410 memset(sp, 0, sizeof(FTS)); 411 sp->fts_compar = compar; 412 sp->fts_options = options; 413 414 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ 415 if (ISSET(FTS_LOGICAL)) { 416 SET(FTS_NOCHDIR); 417 CLR(FTS_CWDFD); 418 } 419 420 /* Initialize fts_cwd_fd. */ 421 sp->fts_cwd_fd = AT_FDCWD; 422 if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT) 423 { 424 /* While it isn't technically necessary to open "." this 425 early, doing it here saves us the trouble of ensuring 426 later (where it'd be messier) that "." can in fact 427 be opened. If not, revert to FTS_NOCHDIR mode. */ 428 int fd = open (".", 429 O_SEARCH | (ISSET (FTS_NOATIME) ? O_NOATIME : 0)); 430 if (fd < 0) 431 { 432 /* Even if "." is unreadable, don't revert to FTS_NOCHDIR mode 433 on systems like Linux+PROC_FS, where our openat emulation 434 is good enough. Note: on a system that emulates 435 openat via /proc, this technique can still fail, but 436 only in extreme conditions, e.g., when the working 437 directory cannot be saved (i.e. save_cwd fails) -- 438 and that happens on Linux only when "." is unreadable 439 and the CWD would be longer than PATH_MAX. 440 FIXME: once Linux kernel openat support is well established, 441 replace the above open call and this entire if/else block 442 with the body of the if-block below. */ 443 if ( openat_needs_fchdir ()) 444 { 445 SET(FTS_NOCHDIR); 446 CLR(FTS_CWDFD); 447 } 448 } 449 else 450 { 451 close (fd); 452 } 453 } 454 455 /* 456 * Start out with 1K of file name space, and enough, in any case, 457 * to hold the user's file names. 458 */ 459 #ifndef MAXPATHLEN 460 # define MAXPATHLEN 1024 461 #endif 462 { 463 size_t maxarglen = fts_maxarglen(argv); 464 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN))) 465 goto mem1; 466 } 467 468 /* Allocate/initialize root's parent. */ 469 if (*argv != NULL) { 470 if ((parent = fts_alloc(sp, "", 0)) == NULL) 471 goto mem2; 472 parent->fts_level = FTS_ROOTPARENTLEVEL; 473 } 474 475 /* The classic fts implementation would call fts_stat with 476 a new entry for each iteration of the loop below. 477 If the comparison function is not specified or if the 478 FTS_DEFER_STAT option is in effect, don't stat any entry 479 in this loop. This is an attempt to minimize the interval 480 between the initial stat/lstat/fstatat and the point at which 481 a directory argument is first opened. This matters for any 482 directory command line argument that resides on a file system 483 without genuine i-nodes. If you specify FTS_DEFER_STAT along 484 with a comparison function, that function must not access any 485 data via the fts_statp pointer. */ 486 defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT)); 487 488 /* Allocate/initialize root(s). */ 489 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) { 490 /* *Do* allow zero-length file names. */ 491 size_t len = strlen(*argv); 492 493 if ( ! (options & FTS_VERBATIM)) 494 { 495 /* If there are two or more trailing slashes, trim all but one, 496 but don't change "//" to "/", and do map "///" to "/". */ 497 char const *v = *argv; 498 if (2 < len && v[len - 1] == '/') 499 while (1 < len && v[len - 2] == '/') 500 --len; 501 } 502 503 if ((p = fts_alloc(sp, *argv, len)) == NULL) 504 goto mem3; 505 p->fts_level = FTS_ROOTLEVEL; 506 p->fts_parent = parent; 507 p->fts_accpath = p->fts_name; 508 /* Even when defer_stat is true, be sure to stat the first 509 command line argument, since fts_read (at least with 510 FTS_XDEV) requires that. */ 511 if (defer_stat && root != NULL) { 512 p->fts_info = FTS_NSOK; 513 fts_set_stat_required(p, true); 514 } else { 515 p->fts_info = fts_stat(sp, p, false); 516 } 517 518 /* 519 * If comparison routine supplied, traverse in sorted 520 * order; otherwise traverse in the order specified. 521 */ 522 if (compar) { 523 p->fts_link = root; 524 root = p; 525 } else { 526 p->fts_link = NULL; 527 if (root == NULL) 528 tmp = root = p; 529 else { 530 tmp->fts_link = p; 531 tmp = p; 532 } 533 } 534 } 535 if (compar && nitems > 1) 536 root = fts_sort(sp, root, nitems); 537 538 /* 539 * Allocate a dummy pointer and make fts_read think that we've just 540 * finished the node before the root(s); set p->fts_info to FTS_INIT 541 * so that everything about the "current" node is ignored. 542 */ 543 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL) 544 goto mem3; 545 sp->fts_cur->fts_link = root; 546 sp->fts_cur->fts_info = FTS_INIT; 547 if (! setup_dir (sp)) 548 goto mem3; 549 550 /* 551 * If using chdir(2), grab a file descriptor pointing to dot to ensure 552 * that we can get back here; this could be avoided for some file names, 553 * but almost certainly not worth the effort. Slashes, symbolic links, 554 * and ".." are all fairly nasty problems. Note, if we can't get the 555 * descriptor we run anyway, just more slowly. 556 */ 557 if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD) 558 && (sp->fts_rfd = diropen (sp, ".")) < 0) 559 SET(FTS_NOCHDIR); 560 561 i_ring_init (&sp->fts_fd_ring, -1); 562 return (sp); 563 564 mem3: fts_lfree(root); 565 free(parent); 566 mem2: free(sp->fts_path); 567 mem1: free(sp); 568 return (NULL); 569 } 570 571 static void 572 internal_function 573 fts_load (FTS *sp, register FTSENT *p) 574 { 575 register size_t len; 576 register char *cp; 577 578 /* 579 * Load the stream structure for the next traversal. Since we don't 580 * actually enter the directory until after the preorder visit, set 581 * the fts_accpath field specially so the chdir gets done to the right 582 * place and the user can access the first node. From fts_open it's 583 * known that the file name will fit. 584 */ 585 len = p->fts_pathlen = p->fts_namelen; 586 memmove(sp->fts_path, p->fts_name, len + 1); 587 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { 588 len = strlen(++cp); 589 memmove(p->fts_name, cp, len + 1); 590 p->fts_namelen = len; 591 } 592 p->fts_accpath = p->fts_path = sp->fts_path; 593 } 594 595 int 596 fts_close (FTS *sp) 597 { 598 register FTSENT *freep, *p; 599 int saved_errno = 0; 600 601 /* 602 * This still works if we haven't read anything -- the dummy structure 603 * points to the root list, so we step through to the end of the root 604 * list which has a valid parent pointer. 605 */ 606 if (sp->fts_cur) { 607 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { 608 freep = p; 609 p = p->fts_link != NULL ? p->fts_link : p->fts_parent; 610 free(freep); 611 } 612 free(p); 613 } 614 615 /* Free up child linked list, sort array, file name buffer. */ 616 if (sp->fts_child) 617 fts_lfree(sp->fts_child); 618 free(sp->fts_array); 619 free(sp->fts_path); 620 621 if (ISSET(FTS_CWDFD)) 622 { 623 if (0 <= sp->fts_cwd_fd) 624 if (close (sp->fts_cwd_fd)) 625 saved_errno = errno; 626 } 627 else if (!ISSET(FTS_NOCHDIR)) 628 { 629 /* Return to original directory, save errno if necessary. */ 630 if (fchdir(sp->fts_rfd)) 631 saved_errno = errno; 632 633 /* If close fails, record errno only if saved_errno is zero, 634 so that we report the probably-more-meaningful fchdir errno. */ 635 if (close (sp->fts_rfd)) 636 if (saved_errno == 0) 637 saved_errno = errno; 638 } 639 640 fd_ring_clear (&sp->fts_fd_ring); 641 642 if (sp->fts_leaf_optimization_works_ht) 643 hash_free (sp->fts_leaf_optimization_works_ht); 644 645 free_dir (sp); 646 647 /* Free up the stream pointer. */ 648 free(sp); 649 650 /* Set errno and return. */ 651 if (saved_errno) { 652 __set_errno (saved_errno); 653 return (-1); 654 } 655 656 return (0); 657 } 658 659 #if defined __linux__ \ 660 && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE 661 662 # include <sys/vfs.h> 663 664 /* Linux-specific constants from coreutils' src/fs.h */ 665 # define S_MAGIC_TMPFS 0x1021994 666 # define S_MAGIC_NFS 0x6969 667 # define S_MAGIC_REISERFS 0x52654973 668 # define S_MAGIC_PROC 0x9FA0 669 670 /* Return false if it is easy to determine the file system type of 671 the directory on which DIR_FD is open, and sorting dirents on 672 inode numbers is known not to improve traversal performance with 673 that type of file system. Otherwise, return true. */ 674 static bool 675 dirent_inode_sort_may_be_useful (int dir_fd) 676 { 677 /* Skip the sort only if we can determine efficiently 678 that skipping it is the right thing to do. 679 The cost of performing an unnecessary sort is negligible, 680 while the cost of *not* performing it can be O(N^2) with 681 a very large constant. */ 682 struct statfs fs_buf; 683 684 /* If fstatfs fails, assume sorting would be useful. */ 685 if (fstatfs (dir_fd, &fs_buf) != 0) 686 return true; 687 688 /* FIXME: what about when f_type is not an integral type? 689 deal with that if/when it's encountered. */ 690 switch (fs_buf.f_type) 691 { 692 case S_MAGIC_TMPFS: 693 case S_MAGIC_NFS: 694 /* On a file system of any of these types, sorting 695 is unnecessary, and hence wasteful. */ 696 return false; 697 698 default: 699 return true; 700 } 701 } 702 703 /* Given a file descriptor DIR_FD open on a directory D, 704 return true if it is valid to apply the leaf-optimization 705 technique of counting directories in D via stat.st_nlink. */ 706 static bool 707 leaf_optimization_applies (int dir_fd) 708 { 709 struct statfs fs_buf; 710 711 /* If fstatfs fails, assume we can't use the optimization. */ 712 if (fstatfs (dir_fd, &fs_buf) != 0) 713 return false; 714 715 /* FIXME: do we need to detect AFS mount points? I doubt it, 716 unless fstatfs can report S_MAGIC_REISERFS for such a directory. */ 717 718 switch (fs_buf.f_type) 719 { 720 /* List here the file system types that lack usable dirent.d_type 721 info, yet for which the optimization does apply. */ 722 case S_MAGIC_REISERFS: 723 return true; 724 725 case S_MAGIC_PROC: 726 /* Explicitly listing this or any other file system type for which 727 the optimization is not applicable is not necessary, but we leave 728 it here to document the risk. Per http://bugs.debian.org/143111, 729 /proc may have bogus stat.st_nlink values. */ 730 /* fall through */ 731 default: 732 return false; 733 } 734 } 735 736 #else 737 static bool 738 dirent_inode_sort_may_be_useful (int dir_fd _GL_UNUSED) { return true; } 739 static bool 740 leaf_optimization_applies (int dir_fd _GL_UNUSED) { return false; } 741 #endif 742 743 /* link-count-optimization entry: 744 map a stat.st_dev number to a boolean: leaf_optimization_works */ 745 struct LCO_ent 746 { 747 dev_t st_dev; 748 bool opt_ok; 749 }; 750 751 /* Use a tiny initial size. If a traversal encounters more than 752 a few devices, the cost of growing/rehashing this table will be 753 rendered negligible by the number of inodes processed. */ 754 enum { LCO_HT_INITIAL_SIZE = 13 }; 755 756 static size_t 757 LCO_hash (void const *x, size_t table_size) 758 { 759 struct LCO_ent const *ax = x; 760 return (uintmax_t) ax->st_dev % table_size; 761 } 762 763 static bool 764 LCO_compare (void const *x, void const *y) 765 { 766 struct LCO_ent const *ax = x; 767 struct LCO_ent const *ay = y; 768 return ax->st_dev == ay->st_dev; 769 } 770 771 /* Ask the same question as leaf_optimization_applies, but query 772 the cache first (FTS.fts_leaf_optimization_works_ht), and if necessary, 773 update that cache. */ 774 static bool 775 link_count_optimize_ok (FTSENT const *p) 776 { 777 FTS *sp = p->fts_fts; 778 Hash_table *h = sp->fts_leaf_optimization_works_ht; 779 struct LCO_ent tmp; 780 struct LCO_ent *ent; 781 bool opt_ok; 782 struct LCO_ent *t2; 783 784 /* If we're not in CWDFD mode, don't bother with this optimization, 785 since the caller is not serious about performance. */ 786 if (!ISSET(FTS_CWDFD)) 787 return false; 788 789 /* map st_dev to the boolean, leaf_optimization_works */ 790 if (h == NULL) 791 { 792 h = sp->fts_leaf_optimization_works_ht 793 = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash, 794 LCO_compare, free); 795 if (h == NULL) 796 return false; 797 } 798 tmp.st_dev = p->fts_statp->st_dev; 799 ent = hash_lookup (h, &tmp); 800 if (ent) 801 return ent->opt_ok; 802 803 /* Look-up failed. Query directly and cache the result. */ 804 t2 = malloc (sizeof *t2); 805 if (t2 == NULL) 806 return false; 807 808 /* Is it ok to perform the optimization in the dir, FTS_CWD_FD? */ 809 opt_ok = leaf_optimization_applies (sp->fts_cwd_fd); 810 t2->opt_ok = opt_ok; 811 t2->st_dev = p->fts_statp->st_dev; 812 813 ent = hash_insert (h, t2); 814 if (ent == NULL) 815 { 816 /* insertion failed */ 817 free (t2); 818 return false; 819 } 820 fts_assert (ent == t2); 821 822 return opt_ok; 823 } 824 825 /* 826 * Special case of "/" at the end of the file name so that slashes aren't 827 * appended which would cause file names to be written as "....//foo". 828 */ 829 #define NAPPEND(p) \ 830 (p->fts_path[p->fts_pathlen - 1] == '/' \ 831 ? p->fts_pathlen - 1 : p->fts_pathlen) 832 833 FTSENT * 834 fts_read (register FTS *sp) 835 { 836 register FTSENT *p, *tmp; 837 register unsigned short int instr; 838 register char *t; 839 840 /* If finished or unrecoverable error, return NULL. */ 841 if (sp->fts_cur == NULL || ISSET(FTS_STOP)) 842 return (NULL); 843 844 /* Set current node pointer. */ 845 p = sp->fts_cur; 846 847 /* Save and zero out user instructions. */ 848 instr = p->fts_instr; 849 p->fts_instr = FTS_NOINSTR; 850 851 /* Any type of file may be re-visited; re-stat and re-turn. */ 852 if (instr == FTS_AGAIN) { 853 p->fts_info = fts_stat(sp, p, false); 854 return (p); 855 } 856 Dprintf (("fts_read: p=%s\n", 857 p->fts_info == FTS_INIT ? "" : p->fts_path)); 858 859 /* 860 * Following a symlink -- SLNONE test allows application to see 861 * SLNONE and recover. If indirecting through a symlink, have 862 * keep a pointer to current location. If unable to get that 863 * pointer, follow fails. 864 */ 865 if (instr == FTS_FOLLOW && 866 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { 867 p->fts_info = fts_stat(sp, p, true); 868 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { 869 if ((p->fts_symfd = diropen (sp, ".")) < 0) { 870 p->fts_errno = errno; 871 p->fts_info = FTS_ERR; 872 } else 873 p->fts_flags |= FTS_SYMFOLLOW; 874 } 875 goto check_for_dir; 876 } 877 878 /* Directory in pre-order. */ 879 if (p->fts_info == FTS_D) { 880 /* If skipped or crossed mount point, do post-order visit. */ 881 if (instr == FTS_SKIP || 882 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) { 883 if (p->fts_flags & FTS_SYMFOLLOW) 884 (void)close(p->fts_symfd); 885 if (sp->fts_child) { 886 fts_lfree(sp->fts_child); 887 sp->fts_child = NULL; 888 } 889 p->fts_info = FTS_DP; 890 LEAVE_DIR (sp, p, "1"); 891 return (p); 892 } 893 894 /* Rebuild if only read the names and now traversing. */ 895 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) { 896 CLR(FTS_NAMEONLY); 897 fts_lfree(sp->fts_child); 898 sp->fts_child = NULL; 899 } 900 901 /* 902 * Cd to the subdirectory. 903 * 904 * If have already read and now fail to chdir, whack the list 905 * to make the names come out right, and set the parent errno 906 * so the application will eventually get an error condition. 907 * Set the FTS_DONTCHDIR flag so that when we logically change 908 * directories back to the parent we don't do a chdir. 909 * 910 * If haven't read do so. If the read fails, fts_build sets 911 * FTS_STOP or the fts_info field of the node. 912 */ 913 if (sp->fts_child != NULL) { 914 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) { 915 p->fts_errno = errno; 916 p->fts_flags |= FTS_DONTCHDIR; 917 for (p = sp->fts_child; p != NULL; 918 p = p->fts_link) 919 p->fts_accpath = 920 p->fts_parent->fts_accpath; 921 } 922 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) { 923 if (ISSET(FTS_STOP)) 924 return (NULL); 925 /* If fts_build's call to fts_safe_changedir failed 926 because it was not able to fchdir into a 927 subdirectory, tell the caller. */ 928 if (p->fts_errno && p->fts_info != FTS_DNR) 929 p->fts_info = FTS_ERR; 930 LEAVE_DIR (sp, p, "2"); 931 return (p); 932 } 933 p = sp->fts_child; 934 sp->fts_child = NULL; 935 goto name; 936 } 937 938 /* Move to the next node on this level. */ 939 next: tmp = p; 940 941 /* If we have so many directory entries that we're reading them 942 in batches, and we've reached the end of the current batch, 943 read in a new batch. */ 944 if (p->fts_link == NULL && p->fts_parent->fts_dirp) 945 { 946 p = tmp->fts_parent; 947 sp->fts_cur = p; 948 sp->fts_path[p->fts_pathlen] = '\0'; 949 950 if ((p = fts_build (sp, BREAD)) == NULL) 951 { 952 if (ISSET(FTS_STOP)) 953 return NULL; 954 goto cd_dot_dot; 955 } 956 957 free(tmp); 958 goto name; 959 } 960 961 if ((p = p->fts_link) != NULL) { 962 sp->fts_cur = p; 963 free(tmp); 964 965 /* 966 * If reached the top, return to the original directory (or 967 * the root of the tree), and load the file names for the next 968 * root. 969 */ 970 if (p->fts_level == FTS_ROOTLEVEL) { 971 if (restore_initial_cwd(sp)) { 972 SET(FTS_STOP); 973 return (NULL); 974 } 975 free_dir(sp); 976 fts_load(sp, p); 977 setup_dir(sp); 978 goto check_for_dir; 979 } 980 981 /* 982 * User may have called fts_set on the node. If skipped, 983 * ignore. If followed, get a file descriptor so we can 984 * get back if necessary. 985 */ 986 if (p->fts_instr == FTS_SKIP) 987 goto next; 988 if (p->fts_instr == FTS_FOLLOW) { 989 p->fts_info = fts_stat(sp, p, true); 990 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { 991 if ((p->fts_symfd = diropen (sp, ".")) < 0) { 992 p->fts_errno = errno; 993 p->fts_info = FTS_ERR; 994 } else 995 p->fts_flags |= FTS_SYMFOLLOW; 996 } 997 p->fts_instr = FTS_NOINSTR; 998 } 999 1000 name: t = sp->fts_path + NAPPEND(p->fts_parent); 1001 *t++ = '/'; 1002 memmove(t, p->fts_name, p->fts_namelen + 1); 1003 check_for_dir: 1004 sp->fts_cur = p; 1005 if (p->fts_info == FTS_NSOK) 1006 { 1007 if (p->fts_statp->st_size == FTS_STAT_REQUIRED) 1008 { 1009 FTSENT *parent = p->fts_parent; 1010 if (FTS_ROOTLEVEL < p->fts_level 1011 /* ->fts_n_dirs_remaining is not valid 1012 for command-line-specified names. */ 1013 && parent->fts_n_dirs_remaining == 0 1014 && ISSET(FTS_NOSTAT) 1015 && ISSET(FTS_PHYSICAL) 1016 && link_count_optimize_ok (parent)) 1017 { 1018 /* nothing more needed */ 1019 } 1020 else 1021 { 1022 p->fts_info = fts_stat(sp, p, false); 1023 if (S_ISDIR(p->fts_statp->st_mode) 1024 && p->fts_level != FTS_ROOTLEVEL 1025 && parent->fts_n_dirs_remaining) 1026 parent->fts_n_dirs_remaining--; 1027 } 1028 } 1029 else 1030 fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED); 1031 } 1032 1033 if (p->fts_info == FTS_D) 1034 { 1035 /* Now that P->fts_statp is guaranteed to be valid, 1036 if this is a command-line directory, record its 1037 device number, to be used for FTS_XDEV. */ 1038 if (p->fts_level == FTS_ROOTLEVEL) 1039 sp->fts_dev = p->fts_statp->st_dev; 1040 Dprintf ((" entering: %s\n", p->fts_path)); 1041 if (! enter_dir (sp, p)) 1042 { 1043 __set_errno (ENOMEM); 1044 return NULL; 1045 } 1046 } 1047 return p; 1048 } 1049 cd_dot_dot: 1050 1051 /* Move up to the parent node. */ 1052 p = tmp->fts_parent; 1053 sp->fts_cur = p; 1054 free(tmp); 1055 1056 if (p->fts_level == FTS_ROOTPARENTLEVEL) { 1057 /* 1058 * Done; free everything up and set errno to 0 so the user 1059 * can distinguish between error and EOF. 1060 */ 1061 free(p); 1062 __set_errno (0); 1063 return (sp->fts_cur = NULL); 1064 } 1065 1066 fts_assert (p->fts_info != FTS_NSOK); 1067 1068 /* NUL terminate the file name. */ 1069 sp->fts_path[p->fts_pathlen] = '\0'; 1070 1071 /* 1072 * Return to the parent directory. If at a root node, restore 1073 * the initial working directory. If we came through a symlink, 1074 * go back through the file descriptor. Otherwise, move up 1075 * one level, via "..". 1076 */ 1077 if (p->fts_level == FTS_ROOTLEVEL) { 1078 if (restore_initial_cwd(sp)) { 1079 p->fts_errno = errno; 1080 SET(FTS_STOP); 1081 } 1082 } else if (p->fts_flags & FTS_SYMFOLLOW) { 1083 if (FCHDIR(sp, p->fts_symfd)) { 1084 p->fts_errno = errno; 1085 SET(FTS_STOP); 1086 } 1087 (void)close(p->fts_symfd); 1088 } else if (!(p->fts_flags & FTS_DONTCHDIR) && 1089 fts_safe_changedir(sp, p->fts_parent, -1, "..")) { 1090 p->fts_errno = errno; 1091 SET(FTS_STOP); 1092 } 1093 1094 /* If the directory causes a cycle, preserve the FTS_DC flag and keep 1095 the corresponding dev/ino pair in the hash table. It is going to be 1096 removed when leaving the original directory. */ 1097 if (p->fts_info != FTS_DC) { 1098 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP; 1099 if (p->fts_errno == 0) 1100 LEAVE_DIR (sp, p, "3"); 1101 } 1102 return ISSET(FTS_STOP) ? NULL : p; 1103 } 1104 1105 /* 1106 * Fts_set takes the stream as an argument although it's not used in this 1107 * implementation; it would be necessary if anyone wanted to add global 1108 * semantics to fts using fts_set. An error return is allowed for similar 1109 * reasons. 1110 */ 1111 /* ARGSUSED */ 1112 int 1113 fts_set(FTS *sp _GL_UNUSED, FTSENT *p, int instr) 1114 { 1115 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW && 1116 instr != FTS_NOINSTR && instr != FTS_SKIP) { 1117 __set_errno (EINVAL); 1118 return (1); 1119 } 1120 p->fts_instr = instr; 1121 return (0); 1122 } 1123 1124 FTSENT * 1125 fts_children (register FTS *sp, int instr) 1126 { 1127 register FTSENT *p; 1128 int fd; 1129 1130 if (instr != 0 && instr != FTS_NAMEONLY) { 1131 __set_errno (EINVAL); 1132 return (NULL); 1133 } 1134 1135 /* Set current node pointer. */ 1136 p = sp->fts_cur; 1137 1138 /* 1139 * Errno set to 0 so user can distinguish empty directory from 1140 * an error. 1141 */ 1142 __set_errno (0); 1143 1144 /* Fatal errors stop here. */ 1145 if (ISSET(FTS_STOP)) 1146 return (NULL); 1147 1148 /* Return logical hierarchy of user's arguments. */ 1149 if (p->fts_info == FTS_INIT) 1150 return (p->fts_link); 1151 1152 /* 1153 * If not a directory being visited in pre-order, stop here. Could 1154 * allow FTS_DNR, assuming the user has fixed the problem, but the 1155 * same effect is available with FTS_AGAIN. 1156 */ 1157 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */) 1158 return (NULL); 1159 1160 /* Free up any previous child list. */ 1161 if (sp->fts_child != NULL) 1162 fts_lfree(sp->fts_child); 1163 1164 if (instr == FTS_NAMEONLY) { 1165 SET(FTS_NAMEONLY); 1166 instr = BNAMES; 1167 } else 1168 instr = BCHILD; 1169 1170 /* 1171 * If using chdir on a relative file name and called BEFORE fts_read 1172 * does its chdir to the root of a traversal, we can lose -- we need to 1173 * chdir into the subdirectory, and we don't know where the current 1174 * directory is, so we can't get back so that the upcoming chdir by 1175 * fts_read will work. 1176 */ 1177 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || 1178 ISSET(FTS_NOCHDIR)) 1179 return (sp->fts_child = fts_build(sp, instr)); 1180 1181 if ((fd = diropen (sp, ".")) < 0) 1182 return (sp->fts_child = NULL); 1183 sp->fts_child = fts_build(sp, instr); 1184 if (ISSET(FTS_CWDFD)) 1185 { 1186 cwd_advance_fd (sp, fd, true); 1187 } 1188 else 1189 { 1190 if (fchdir(fd)) 1191 { 1192 int saved_errno = errno; 1193 close (fd); 1194 __set_errno (saved_errno); 1195 return NULL; 1196 } 1197 close (fd); 1198 } 1199 return (sp->fts_child); 1200 } 1201 1202 /* A comparison function to sort on increasing inode number. 1203 For some file system types, sorting either way makes a huge 1204 performance difference for a directory with very many entries, 1205 but sorting on increasing values is slightly better than sorting 1206 on decreasing values. The difference is in the 5% range. */ 1207 static int 1208 fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b) 1209 { 1210 return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? -1 1211 : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? 1 : 0); 1212 } 1213 1214 /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode 1215 S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */ 1216 static void 1217 set_stat_type (struct stat *st, unsigned int dtype) 1218 { 1219 mode_t type; 1220 switch (dtype) 1221 { 1222 case DT_BLK: 1223 type = S_IFBLK; 1224 break; 1225 case DT_CHR: 1226 type = S_IFCHR; 1227 break; 1228 case DT_DIR: 1229 type = S_IFDIR; 1230 break; 1231 case DT_FIFO: 1232 type = S_IFIFO; 1233 break; 1234 case DT_LNK: 1235 type = S_IFLNK; 1236 break; 1237 case DT_REG: 1238 type = S_IFREG; 1239 break; 1240 case DT_SOCK: 1241 type = S_IFSOCK; 1242 break; 1243 default: 1244 type = 0; 1245 } 1246 st->st_mode = type; 1247 } 1248 1249 #define closedir_and_clear(dirp) \ 1250 do \ 1251 { \ 1252 closedir (dirp); \ 1253 dirp = NULL; \ 1254 } \ 1255 while (0) 1256 1257 #define fts_opendir(file, Pdir_fd) \ 1258 opendirat((! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \ 1259 ? sp->fts_cwd_fd : AT_FDCWD), \ 1260 file, \ 1261 (((ISSET(FTS_PHYSICAL) \ 1262 && ! (ISSET(FTS_COMFOLLOW) \ 1263 && cur->fts_level == FTS_ROOTLEVEL)) \ 1264 ? O_NOFOLLOW : 0) \ 1265 | (ISSET (FTS_NOATIME) ? O_NOATIME : 0)), \ 1266 Pdir_fd) 1267 1268 /* 1269 * This is the tricky part -- do not casually change *anything* in here. The 1270 * idea is to build the linked list of entries that are used by fts_children 1271 * and fts_read. There are lots of special cases. 1272 * 1273 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is 1274 * set and it's a physical walk (so that symbolic links can't be directories), 1275 * we can do things quickly. First, if it's a 4.4BSD file system, the type 1276 * of the file is in the directory entry. Otherwise, we assume that the number 1277 * of subdirectories in a node is equal to the number of links to the parent. 1278 * The former skips all stat calls. The latter skips stat calls in any leaf 1279 * directories and for any files after the subdirectories in the directory have 1280 * been found, cutting the stat calls by about 2/3. 1281 */ 1282 static FTSENT * 1283 internal_function 1284 fts_build (register FTS *sp, int type) 1285 { 1286 register FTSENT *p, *head; 1287 register size_t nitems; 1288 FTSENT *tail; 1289 void *oldaddr; 1290 int saved_errno; 1291 bool descend; 1292 bool doadjust; 1293 ptrdiff_t level; 1294 nlink_t nlinks; 1295 bool nostat; 1296 size_t len, maxlen, new_len; 1297 char *cp; 1298 int dir_fd; 1299 FTSENT *cur = sp->fts_cur; 1300 bool continue_readdir = !!cur->fts_dirp; 1301 size_t max_entries; 1302 1303 /* When cur->fts_dirp is non-NULL, that means we should 1304 continue calling readdir on that existing DIR* pointer 1305 rather than opening a new one. */ 1306 if (continue_readdir) 1307 { 1308 DIR *dp = cur->fts_dirp; 1309 dir_fd = dirfd (dp); 1310 if (dir_fd < 0) 1311 { 1312 closedir_and_clear (cur->fts_dirp); 1313 if (type == BREAD) 1314 { 1315 cur->fts_info = FTS_DNR; 1316 cur->fts_errno = errno; 1317 } 1318 return NULL; 1319 } 1320 } 1321 else 1322 { 1323 /* Open the directory for reading. If this fails, we're done. 1324 If being called from fts_read, set the fts_info field. */ 1325 if ((cur->fts_dirp = fts_opendir(cur->fts_accpath, &dir_fd)) == NULL) 1326 { 1327 if (type == BREAD) 1328 { 1329 cur->fts_info = FTS_DNR; 1330 cur->fts_errno = errno; 1331 } 1332 return NULL; 1333 } 1334 /* Rather than calling fts_stat for each and every entry encountered 1335 in the readdir loop (below), stat each directory only right after 1336 opening it. */ 1337 if (cur->fts_info == FTS_NSOK) 1338 cur->fts_info = fts_stat(sp, cur, false); 1339 else if (sp->fts_options & FTS_TIGHT_CYCLE_CHECK) 1340 { 1341 /* Now read the stat info again after opening a directory to 1342 reveal eventual changes caused by a submount triggered by 1343 the traversal. But do it only for utilities which use 1344 FTS_TIGHT_CYCLE_CHECK. Therefore, only find and du 1345 benefit/suffer from this feature for now. */ 1346 LEAVE_DIR (sp, cur, "4"); 1347 fts_stat (sp, cur, false); 1348 if (! enter_dir (sp, cur)) 1349 { 1350 __set_errno (ENOMEM); 1351 return NULL; 1352 } 1353 } 1354 } 1355 1356 /* Maximum number of readdir entries to read at one time. This 1357 limitation is to avoid reading millions of entries into memory 1358 at once. When an fts_compar function is specified, we have no 1359 choice: we must read all entries into memory before calling that 1360 function. But when no such function is specified, we can read 1361 entries in batches that are large enough to help us with inode- 1362 sorting, yet not so large that we risk exhausting memory. */ 1363 max_entries = sp->fts_compar ? SIZE_MAX : FTS_MAX_READDIR_ENTRIES; 1364 1365 /* 1366 * Nlinks is the number of possible entries of type directory in the 1367 * directory if we're cheating on stat calls, 0 if we're not doing 1368 * any stat calls at all, (nlink_t) -1 if we're statting everything. 1369 */ 1370 if (type == BNAMES) { 1371 nlinks = 0; 1372 /* Be quiet about nostat, GCC. */ 1373 nostat = false; 1374 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) { 1375 nlinks = (cur->fts_statp->st_nlink 1376 - (ISSET(FTS_SEEDOT) ? 0 : 2)); 1377 nostat = true; 1378 } else { 1379 nlinks = -1; 1380 nostat = false; 1381 } 1382 1383 /* 1384 * If we're going to need to stat anything or we want to descend 1385 * and stay in the directory, chdir. If this fails we keep going, 1386 * but set a flag so we don't chdir after the post-order visit. 1387 * We won't be able to stat anything, but we can still return the 1388 * names themselves. Note, that since fts_read won't be able to 1389 * chdir into the directory, it will have to return different file 1390 * names than before, i.e. "a/b" instead of "b". Since the node 1391 * has already been visited in pre-order, have to wait until the 1392 * post-order visit to return the error. There is a special case 1393 * here, if there was nothing to stat then it's not an error to 1394 * not be able to stat. This is all fairly nasty. If a program 1395 * needed sorted entries or stat information, they had better be 1396 * checking FTS_NS on the returned nodes. 1397 */ 1398 if (continue_readdir) 1399 { 1400 /* When resuming a short readdir run, we already have 1401 the required dirp and dir_fd. */ 1402 descend = true; 1403 } 1404 else if (nlinks || type == BREAD) { 1405 if (ISSET(FTS_CWDFD)) 1406 { 1407 dir_fd = dup (dir_fd); 1408 if (0 <= dir_fd) 1409 set_cloexec_flag (dir_fd, true); 1410 } 1411 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) { 1412 if (nlinks && type == BREAD) 1413 cur->fts_errno = errno; 1414 cur->fts_flags |= FTS_DONTCHDIR; 1415 descend = false; 1416 closedir_and_clear(cur->fts_dirp); 1417 if (ISSET(FTS_CWDFD) && 0 <= dir_fd) 1418 close (dir_fd); 1419 cur->fts_dirp = NULL; 1420 } else 1421 descend = true; 1422 } else 1423 descend = false; 1424 1425 /* 1426 * Figure out the max file name length that can be stored in the 1427 * current buffer -- the inner loop allocates more space as necessary. 1428 * We really wouldn't have to do the maxlen calculations here, we 1429 * could do them in fts_read before returning the name, but it's a 1430 * lot easier here since the length is part of the dirent structure. 1431 * 1432 * If not changing directories set a pointer so that can just append 1433 * each new component into the file name. 1434 */ 1435 len = NAPPEND(cur); 1436 if (ISSET(FTS_NOCHDIR)) { 1437 cp = sp->fts_path + len; 1438 *cp++ = '/'; 1439 } else { 1440 /* GCC, you're too verbose. */ 1441 cp = NULL; 1442 } 1443 len++; 1444 maxlen = sp->fts_pathlen - len; 1445 1446 level = cur->fts_level + 1; 1447 1448 /* Read the directory, attaching each entry to the "link" pointer. */ 1449 doadjust = false; 1450 head = NULL; 1451 tail = NULL; 1452 nitems = 0; 1453 while (cur->fts_dirp) { 1454 bool is_dir; 1455 size_t d_namelen; 1456 struct dirent *dp = readdir(cur->fts_dirp); 1457 if (dp == NULL) 1458 break; 1459 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) 1460 continue; 1461 1462 d_namelen = _D_EXACT_NAMLEN (dp); 1463 p = fts_alloc (sp, dp->d_name, d_namelen); 1464 if (!p) 1465 goto mem1; 1466 if (d_namelen >= maxlen) { 1467 /* include space for NUL */ 1468 oldaddr = sp->fts_path; 1469 if (! fts_palloc(sp, d_namelen + len + 1)) { 1470 /* 1471 * No more memory. Save 1472 * errno, free up the current structure and the 1473 * structures already allocated. 1474 */ 1475 mem1: saved_errno = errno; 1476 free(p); 1477 fts_lfree(head); 1478 closedir_and_clear(cur->fts_dirp); 1479 cur->fts_info = FTS_ERR; 1480 SET(FTS_STOP); 1481 __set_errno (saved_errno); 1482 return (NULL); 1483 } 1484 /* Did realloc() change the pointer? */ 1485 if (oldaddr != sp->fts_path) { 1486 doadjust = true; 1487 if (ISSET(FTS_NOCHDIR)) 1488 cp = sp->fts_path + len; 1489 } 1490 maxlen = sp->fts_pathlen - len; 1491 } 1492 1493 new_len = len + d_namelen; 1494 if (new_len < len) { 1495 /* 1496 * In the unlikely event that we would end up 1497 * with a file name longer than SIZE_MAX, free up 1498 * the current structure and the structures already 1499 * allocated, then error out with ENAMETOOLONG. 1500 */ 1501 free(p); 1502 fts_lfree(head); 1503 closedir_and_clear(cur->fts_dirp); 1504 cur->fts_info = FTS_ERR; 1505 SET(FTS_STOP); 1506 __set_errno (ENAMETOOLONG); 1507 return (NULL); 1508 } 1509 p->fts_level = level; 1510 p->fts_parent = sp->fts_cur; 1511 p->fts_pathlen = new_len; 1512 1513 /* Store dirent.d_ino, in case we need to sort 1514 entries before processing them. */ 1515 p->fts_statp->st_ino = D_INO (dp); 1516 1517 /* Build a file name for fts_stat to stat. */ 1518 if (ISSET(FTS_NOCHDIR)) { 1519 p->fts_accpath = p->fts_path; 1520 memmove(cp, p->fts_name, p->fts_namelen + 1); 1521 } else 1522 p->fts_accpath = p->fts_name; 1523 1524 if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) { 1525 /* Record what fts_read will have to do with this 1526 entry. In many cases, it will simply fts_stat it, 1527 but we can take advantage of any d_type information 1528 to optimize away the unnecessary stat calls. I.e., 1529 if FTS_NOSTAT is in effect and we're not following 1530 symlinks (FTS_PHYSICAL) and d_type indicates this 1531 is *not* a directory, then we won't have to stat it 1532 at all. If it *is* a directory, then (currently) 1533 we stat it regardless, in order to get device and 1534 inode numbers. Some day we might optimize that 1535 away, too, for directories where d_ino is known to 1536 be valid. */ 1537 bool skip_stat = (ISSET(FTS_PHYSICAL) 1538 && ISSET(FTS_NOSTAT) 1539 && DT_IS_KNOWN(dp) 1540 && ! DT_MUST_BE(dp, DT_DIR)); 1541 p->fts_info = FTS_NSOK; 1542 /* Propagate dirent.d_type information back 1543 to caller, when possible. */ 1544 set_stat_type (p->fts_statp, D_TYPE (dp)); 1545 fts_set_stat_required(p, !skip_stat); 1546 is_dir = (ISSET(FTS_PHYSICAL) 1547 && DT_MUST_BE(dp, DT_DIR)); 1548 } else { 1549 p->fts_info = fts_stat(sp, p, false); 1550 is_dir = (p->fts_info == FTS_D 1551 || p->fts_info == FTS_DC 1552 || p->fts_info == FTS_DOT); 1553 } 1554 1555 /* Decrement link count if applicable. */ 1556 if (nlinks > 0 && is_dir) 1557 nlinks -= nostat; 1558 1559 /* We walk in directory order so "ls -f" doesn't get upset. */ 1560 p->fts_link = NULL; 1561 if (head == NULL) 1562 head = tail = p; 1563 else { 1564 tail->fts_link = p; 1565 tail = p; 1566 } 1567 ++nitems; 1568 if (max_entries <= nitems) { 1569 /* When there are too many dir entries, leave 1570 fts_dirp open, so that a subsequent fts_read 1571 can take up where we leave off. */ 1572 goto break_without_closedir; 1573 } 1574 } 1575 1576 if (cur->fts_dirp) 1577 closedir_and_clear(cur->fts_dirp); 1578 1579 break_without_closedir: 1580 1581 /* 1582 * If realloc() changed the address of the file name, adjust the 1583 * addresses for the rest of the tree and the dir list. 1584 */ 1585 if (doadjust) 1586 fts_padjust(sp, head); 1587 1588 /* 1589 * If not changing directories, reset the file name back to original 1590 * state. 1591 */ 1592 if (ISSET(FTS_NOCHDIR)) { 1593 if (len == sp->fts_pathlen || nitems == 0) 1594 --cp; 1595 *cp = '\0'; 1596 } 1597 1598 /* 1599 * If descended after called from fts_children or after called from 1600 * fts_read and nothing found, get back. At the root level we use 1601 * the saved fd; if one of fts_open()'s arguments is a relative name 1602 * to an empty directory, we wind up here with no other way back. If 1603 * can't get back, we're done. 1604 */ 1605 if (!continue_readdir && descend && (type == BCHILD || !nitems) && 1606 (cur->fts_level == FTS_ROOTLEVEL 1607 ? restore_initial_cwd(sp) 1608 : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) { 1609 cur->fts_info = FTS_ERR; 1610 SET(FTS_STOP); 1611 fts_lfree(head); 1612 return (NULL); 1613 } 1614 1615 /* If didn't find anything, return NULL. */ 1616 if (!nitems) { 1617 if (type == BREAD) 1618 cur->fts_info = FTS_DP; 1619 fts_lfree(head); 1620 return (NULL); 1621 } 1622 1623 /* If there are many entries, no sorting function has been specified, 1624 and this file system is of a type that may be slow with a large 1625 number of entries, then sort the directory entries on increasing 1626 inode numbers. */ 1627 if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 1628 && !sp->fts_compar 1629 && ISSET (FTS_CWDFD) 1630 && dirent_inode_sort_may_be_useful (sp->fts_cwd_fd)) { 1631 sp->fts_compar = fts_compare_ino; 1632 head = fts_sort (sp, head, nitems); 1633 sp->fts_compar = NULL; 1634 } 1635 1636 /* Sort the entries. */ 1637 if (sp->fts_compar && nitems > 1) 1638 head = fts_sort(sp, head, nitems); 1639 return (head); 1640 } 1641 1642 #if FTS_DEBUG 1643 1644 /* Walk ->fts_parent links starting at E_CURR, until the root of the 1645 current hierarchy. There should be a directory with dev/inode 1646 matching those of AD. If not, print a lot of diagnostics. */ 1647 static void 1648 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad) 1649 { 1650 FTSENT const *ent; 1651 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent) 1652 { 1653 if (ad->ino == ent->fts_statp->st_ino 1654 && ad->dev == ent->fts_statp->st_dev) 1655 return; 1656 } 1657 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath); 1658 printf ("active dirs:\n"); 1659 for (ent = e_curr; 1660 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent) 1661 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n", 1662 ad->fts_ent->fts_accpath, 1663 (uintmax_t) ad->dev, 1664 (uintmax_t) ad->ino, 1665 ent->fts_accpath, 1666 (uintmax_t) ent->fts_statp->st_dev, 1667 (uintmax_t) ent->fts_statp->st_ino); 1668 } 1669 1670 void 1671 fts_cross_check (FTS const *sp) 1672 { 1673 FTSENT const *ent = sp->fts_cur; 1674 FTSENT const *t; 1675 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK)) 1676 return; 1677 1678 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path)); 1679 /* Make sure every parent dir is in the tree. */ 1680 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) 1681 { 1682 struct Active_dir ad; 1683 ad.ino = t->fts_statp->st_ino; 1684 ad.dev = t->fts_statp->st_dev; 1685 if ( ! hash_lookup (sp->fts_cycle.ht, &ad)) 1686 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path); 1687 } 1688 1689 /* Make sure every dir in the tree is an active dir. 1690 But ENT is not necessarily a directory. If so, just skip this part. */ 1691 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL 1692 && (ent->fts_info == FTS_DP 1693 || ent->fts_info == FTS_D)) 1694 { 1695 struct Active_dir *ad; 1696 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL; 1697 ad = hash_get_next (sp->fts_cycle.ht, ad)) 1698 { 1699 find_matching_ancestor (ent, ad); 1700 } 1701 } 1702 } 1703 1704 static bool 1705 same_fd (int fd1, int fd2) 1706 { 1707 struct stat sb1, sb2; 1708 return (fstat (fd1, &sb1) == 0 1709 && fstat (fd2, &sb2) == 0 1710 && SAME_INODE (sb1, sb2)); 1711 } 1712 1713 static void 1714 fd_ring_print (FTS const *sp, FILE *stream, char const *msg) 1715 { 1716 I_ring const *fd_ring = &sp->fts_fd_ring; 1717 unsigned int i = fd_ring->fts_front; 1718 char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0); 1719 fprintf (stream, "=== %s ========== %s\n", msg, cwd); 1720 free (cwd); 1721 if (i_ring_empty (fd_ring)) 1722 return; 1723 1724 while (true) 1725 { 1726 int fd = fd_ring->fts_fd_ring[i]; 1727 if (fd < 0) 1728 fprintf (stream, "%d: %d:\n", i, fd); 1729 else 1730 { 1731 char *wd = getcwdat (fd, NULL, 0); 1732 fprintf (stream, "%d: %d: %s\n", i, fd, wd); 1733 free (wd); 1734 } 1735 if (i == fd_ring->fts_back) 1736 break; 1737 i = (i + I_RING_SIZE - 1) % I_RING_SIZE; 1738 } 1739 } 1740 1741 /* Ensure that each file descriptor on the fd_ring matches a 1742 parent, grandparent, etc. of the current working directory. */ 1743 static void 1744 fd_ring_check (FTS const *sp) 1745 { 1746 if (!fts_debug) 1747 return; 1748 1749 /* Make a writable copy. */ 1750 I_ring fd_w = sp->fts_fd_ring; 1751 1752 int cwd_fd = sp->fts_cwd_fd; 1753 cwd_fd = dup (cwd_fd); 1754 char *dot = getcwdat (cwd_fd, NULL, 0); 1755 error (0, 0, "===== check ===== cwd: %s", dot); 1756 free (dot); 1757 while ( ! i_ring_empty (&fd_w)) 1758 { 1759 int fd = i_ring_pop (&fd_w); 1760 if (0 <= fd) 1761 { 1762 int parent_fd = openat (cwd_fd, "..", O_SEARCH | O_NOATIME); 1763 if (parent_fd < 0) 1764 { 1765 // Warn? 1766 break; 1767 } 1768 if (!same_fd (fd, parent_fd)) 1769 { 1770 char *cwd = getcwdat (fd, NULL, 0); 1771 error (0, errno, "ring : %s", cwd); 1772 char *c2 = getcwdat (parent_fd, NULL, 0); 1773 error (0, errno, "parent: %s", c2); 1774 free (cwd); 1775 free (c2); 1776 fts_assert (0); 1777 } 1778 close (cwd_fd); 1779 cwd_fd = parent_fd; 1780 } 1781 } 1782 close (cwd_fd); 1783 } 1784 #endif 1785 1786 static unsigned short int 1787 internal_function 1788 fts_stat(FTS *sp, register FTSENT *p, bool follow) 1789 { 1790 struct stat *sbp = p->fts_statp; 1791 int saved_errno; 1792 1793 if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW)) 1794 follow = true; 1795 1796 /* 1797 * If doing a logical walk, or application requested FTS_FOLLOW, do 1798 * a stat(2). If that fails, check for a non-existent symlink. If 1799 * fail, set the errno from the stat call. 1800 */ 1801 if (ISSET(FTS_LOGICAL) || follow) { 1802 if (stat(p->fts_accpath, sbp)) { 1803 saved_errno = errno; 1804 if (errno == ENOENT 1805 && lstat(p->fts_accpath, sbp) == 0) { 1806 __set_errno (0); 1807 return (FTS_SLNONE); 1808 } 1809 p->fts_errno = saved_errno; 1810 goto err; 1811 } 1812 } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp, 1813 AT_SYMLINK_NOFOLLOW)) { 1814 p->fts_errno = errno; 1815 err: memset(sbp, 0, sizeof(struct stat)); 1816 return (FTS_NS); 1817 } 1818 1819 if (S_ISDIR(sbp->st_mode)) { 1820 p->fts_n_dirs_remaining = (sbp->st_nlink 1821 - (ISSET(FTS_SEEDOT) ? 0 : 2)); 1822 if (ISDOT(p->fts_name)) { 1823 /* Command-line "." and ".." are real directories. */ 1824 return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT); 1825 } 1826 1827 return (FTS_D); 1828 } 1829 if (S_ISLNK(sbp->st_mode)) 1830 return (FTS_SL); 1831 if (S_ISREG(sbp->st_mode)) 1832 return (FTS_F); 1833 return (FTS_DEFAULT); 1834 } 1835 1836 static int 1837 fts_compar (void const *a, void const *b) 1838 { 1839 /* Convert A and B to the correct types, to pacify the compiler, and 1840 for portability to bizarre hosts where "void const *" and "FTSENT 1841 const **" differ in runtime representation. The comparison 1842 function cannot modify *a and *b, but there is no compile-time 1843 check for this. */ 1844 FTSENT const **pa = (FTSENT const **) a; 1845 FTSENT const **pb = (FTSENT const **) b; 1846 return pa[0]->fts_fts->fts_compar (pa, pb); 1847 } 1848 1849 static FTSENT * 1850 internal_function 1851 fts_sort (FTS *sp, FTSENT *head, register size_t nitems) 1852 { 1853 register FTSENT **ap, *p; 1854 1855 /* On most modern hosts, void * and FTSENT ** have the same 1856 run-time representation, and one can convert sp->fts_compar to 1857 the type qsort expects without problem. Use the heuristic that 1858 this is OK if the two pointer types are the same size, and if 1859 converting FTSENT ** to long int is the same as converting 1860 FTSENT ** to void * and then to long int. This heuristic isn't 1861 valid in general but we don't know of any counterexamples. */ 1862 FTSENT *dummy; 1863 int (*compare) (void const *, void const *) = 1864 ((sizeof &dummy == sizeof (void *) 1865 && (long int) &dummy == (long int) (void *) &dummy) 1866 ? (int (*) (void const *, void const *)) sp->fts_compar 1867 : fts_compar); 1868 1869 /* 1870 * Construct an array of pointers to the structures and call qsort(3). 1871 * Reassemble the array in the order returned by qsort. If unable to 1872 * sort for memory reasons, return the directory entries in their 1873 * current order. Allocate enough space for the current needs plus 1874 * 40 so don't realloc one entry at a time. 1875 */ 1876 if (nitems > sp->fts_nitems) { 1877 FTSENT **a; 1878 1879 sp->fts_nitems = nitems + 40; 1880 if (SIZE_MAX / sizeof *a < sp->fts_nitems 1881 || ! (a = realloc (sp->fts_array, 1882 sp->fts_nitems * sizeof *a))) { 1883 free(sp->fts_array); 1884 sp->fts_array = NULL; 1885 sp->fts_nitems = 0; 1886 return (head); 1887 } 1888 sp->fts_array = a; 1889 } 1890 for (ap = sp->fts_array, p = head; p; p = p->fts_link) 1891 *ap++ = p; 1892 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare); 1893 for (head = *(ap = sp->fts_array); --nitems; ++ap) 1894 ap[0]->fts_link = ap[1]; 1895 ap[0]->fts_link = NULL; 1896 return (head); 1897 } 1898 1899 static FTSENT * 1900 internal_function 1901 fts_alloc (FTS *sp, const char *name, register size_t namelen) 1902 { 1903 register FTSENT *p; 1904 size_t len; 1905 1906 /* 1907 * The file name is a variable length array. Allocate the FTSENT 1908 * structure and the file name in one chunk. 1909 */ 1910 len = offsetof(FTSENT, fts_name) + namelen + 1; 1911 /* Align the allocation size so that it works for FTSENT, 1912 so that trailing padding may be referenced by direct access 1913 to the flexible array members, without triggering undefined behavior 1914 by accessing bytes beyond the heap allocation. This implicit access 1915 was seen for example with ISDOT() and GCC 5.1.1 at -O2. 1916 Do not use alignof (FTSENT) here, since C11 prohibits 1917 taking the alignment of a structure containing a flexible 1918 array member. */ 1919 len += alignof (max_align_t) - 1; 1920 len &= ~ (alignof (max_align_t) - 1); 1921 if ((p = malloc(len)) == NULL) 1922 return (NULL); 1923 1924 /* Copy the name and guarantee NUL termination. */ 1925 memcpy(p->fts_name, name, namelen); 1926 p->fts_name[namelen] = '\0'; 1927 1928 p->fts_namelen = namelen; 1929 p->fts_fts = sp; 1930 p->fts_path = sp->fts_path; 1931 p->fts_errno = 0; 1932 p->fts_dirp = NULL; 1933 p->fts_flags = 0; 1934 p->fts_instr = FTS_NOINSTR; 1935 p->fts_number = 0; 1936 p->fts_pointer = NULL; 1937 return (p); 1938 } 1939 1940 static void 1941 internal_function 1942 fts_lfree (register FTSENT *head) 1943 { 1944 register FTSENT *p; 1945 1946 /* Free a linked list of structures. */ 1947 while ((p = head)) { 1948 head = head->fts_link; 1949 if (p->fts_dirp) 1950 closedir (p->fts_dirp); 1951 free(p); 1952 } 1953 } 1954 1955 /* 1956 * Allow essentially unlimited file name lengths; find, rm, ls should 1957 * all work on any tree. Most systems will allow creation of file 1958 * names much longer than MAXPATHLEN, even though the kernel won't 1959 * resolve them. Add the size (not just what's needed) plus 256 bytes 1960 * so don't realloc the file name 2 bytes at a time. 1961 */ 1962 static bool 1963 internal_function 1964 fts_palloc (FTS *sp, size_t more) 1965 { 1966 char *p; 1967 size_t new_len = sp->fts_pathlen + more + 256; 1968 1969 /* 1970 * See if fts_pathlen would overflow. 1971 */ 1972 if (new_len < sp->fts_pathlen) { 1973 free(sp->fts_path); 1974 sp->fts_path = NULL; 1975 __set_errno (ENAMETOOLONG); 1976 return false; 1977 } 1978 sp->fts_pathlen = new_len; 1979 p = realloc(sp->fts_path, sp->fts_pathlen); 1980 if (p == NULL) { 1981 free(sp->fts_path); 1982 sp->fts_path = NULL; 1983 return false; 1984 } 1985 sp->fts_path = p; 1986 return true; 1987 } 1988 1989 /* 1990 * When the file name is realloc'd, have to fix all of the pointers in 1991 * structures already returned. 1992 */ 1993 static void 1994 internal_function 1995 fts_padjust (FTS *sp, FTSENT *head) 1996 { 1997 FTSENT *p; 1998 char *addr = sp->fts_path; 1999 2000 #define ADJUST(p) do { \ 2001 if ((p)->fts_accpath != (p)->fts_name) { \ 2002 (p)->fts_accpath = \ 2003 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \ 2004 } \ 2005 (p)->fts_path = addr; \ 2006 } while (0) 2007 /* Adjust the current set of children. */ 2008 for (p = sp->fts_child; p; p = p->fts_link) 2009 ADJUST(p); 2010 2011 /* Adjust the rest of the tree, including the current level. */ 2012 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) { 2013 ADJUST(p); 2014 p = p->fts_link ? p->fts_link : p->fts_parent; 2015 } 2016 } 2017 2018 static size_t 2019 internal_function _GL_ATTRIBUTE_PURE 2020 fts_maxarglen (char * const *argv) 2021 { 2022 size_t len, max; 2023 2024 for (max = 0; *argv; ++argv) 2025 if ((len = strlen(*argv)) > max) 2026 max = len; 2027 return (max + 1); 2028 } 2029 2030 /* 2031 * Change to dir specified by fd or file name without getting 2032 * tricked by someone changing the world out from underneath us. 2033 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in. 2034 * If FD is non-negative, expect it to be used after this function returns, 2035 * and to be closed eventually. So don't pass e.g., 'dirfd(dirp)' and then 2036 * do closedir(dirp), because that would invalidate the saved FD. 2037 * Upon failure, close FD immediately and return nonzero. 2038 */ 2039 static int 2040 internal_function 2041 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir) 2042 { 2043 int ret; 2044 bool is_dotdot = dir && STREQ (dir, ".."); 2045 int newfd; 2046 2047 /* This clause handles the unusual case in which FTS_NOCHDIR 2048 is specified, along with FTS_CWDFD. In that case, there is 2049 no need to change even the virtual cwd file descriptor. 2050 However, if FD is non-negative, we do close it here. */ 2051 if (ISSET (FTS_NOCHDIR)) 2052 { 2053 if (ISSET (FTS_CWDFD) && 0 <= fd) 2054 close (fd); 2055 return 0; 2056 } 2057 2058 if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD)) 2059 { 2060 /* When possible, skip the diropen and subsequent fstat+dev/ino 2061 comparison. I.e., when changing to parent directory 2062 (chdir ("..")), use a file descriptor from the ring and 2063 save the overhead of diropen+fstat, as well as avoiding 2064 failure when we lack "x" access to the virtual cwd. */ 2065 if ( ! i_ring_empty (&sp->fts_fd_ring)) 2066 { 2067 int parent_fd; 2068 fd_ring_print (sp, stderr, "pre-pop"); 2069 parent_fd = i_ring_pop (&sp->fts_fd_ring); 2070 is_dotdot = true; 2071 if (0 <= parent_fd) 2072 { 2073 fd = parent_fd; 2074 dir = NULL; 2075 } 2076 } 2077 } 2078 2079 newfd = fd; 2080 if (fd < 0 && (newfd = diropen (sp, dir)) < 0) 2081 return -1; 2082 2083 /* The following dev/inode check is necessary if we're doing a 2084 "logical" traversal (through symlinks, a la chown -L), if the 2085 system lacks O_NOFOLLOW support, or if we're changing to ".." 2086 (but not via a popped file descriptor). When changing to the 2087 name "..", O_NOFOLLOW can't help. In general, when the target is 2088 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly 2089 follow a symlink, so we can avoid the expense of this fstat. */ 2090 if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW 2091 || (dir && STREQ (dir, ".."))) 2092 { 2093 struct stat sb; 2094 if (fstat(newfd, &sb)) 2095 { 2096 ret = -1; 2097 goto bail; 2098 } 2099 if (p->fts_statp->st_dev != sb.st_dev 2100 || p->fts_statp->st_ino != sb.st_ino) 2101 { 2102 __set_errno (ENOENT); /* disinformation */ 2103 ret = -1; 2104 goto bail; 2105 } 2106 } 2107 2108 if (ISSET(FTS_CWDFD)) 2109 { 2110 cwd_advance_fd (sp, newfd, ! is_dotdot); 2111 return 0; 2112 } 2113 2114 ret = fchdir(newfd); 2115 bail: 2116 if (fd < 0) 2117 { 2118 int oerrno = errno; 2119 (void)close(newfd); 2120 __set_errno (oerrno); 2121 } 2122 return ret; 2123 } 2124