Debian Codegraph @

lib/fts.c

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