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