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