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