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