Sync with upstream OpenBSD fts.c.
[android-sdk/platform-bionic.git] / libc / bionic / fts.c
1 /*      $OpenBSD: fts.c,v 1.48 2014/11/20 04:14:15 guenther Exp $       */
3 /*-
4  * Copyright (c) 1990, 1993, 1994
5  *      The Regents of the University of California.  All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  * 3. Neither the name of the University nor the names of its contributors
16  *    may be used to endorse or promote products derived from this software
17  *    without specific prior written permission.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29  * SUCH DAMAGE.
30  */
32 #include <sys/param.h>
33 #include <sys/stat.h>
35 #include <dirent.h>
36 #include <errno.h>
37 #include <fcntl.h>
38 #include <fts.h>
39 #include <limits.h>
40 #include <stdlib.h>
41 #include <string.h>
42 #include <unistd.h>
44 static FTSENT   *fts_alloc(FTS *, char *, size_t);
45 static FTSENT   *fts_build(FTS *, int);
46 static void      fts_lfree(FTSENT *);
47 static void      fts_load(FTS *, FTSENT *);
48 static size_t    fts_maxarglen(char * const *);
49 static void      fts_padjust(FTS *, FTSENT *);
50 static int       fts_palloc(FTS *, size_t);
51 static FTSENT   *fts_sort(FTS *, FTSENT *, int);
52 static u_short   fts_stat(FTS *, FTSENT *, int, int);
53 static int       fts_safe_changedir(FTS *, FTSENT *, int, char *);
55 #define ALIGNBYTES (sizeof(uintptr_t) - 1)
56 #define ALIGN(p) (((uintptr_t)(p) + ALIGNBYTES) &~ ALIGNBYTES)
57 void* reallocarray(void*, size_t, size_t);
59 #define ISDOT(a)        (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
61 #define CLR(opt)        (sp->fts_options &= ~(opt))
62 #define ISSET(opt)      (sp->fts_options & (opt))
63 #define SET(opt)        (sp->fts_options |= (opt))
65 #define FCHDIR(sp, fd)  (!ISSET(FTS_NOCHDIR) && fchdir(fd))
67 /* fts_build flags */
68 #define BCHILD          1               /* fts_children */
69 #define BNAMES          2               /* fts_children, names only */
70 #define BREAD           3               /* fts_read */
72 FTS *
73 fts_open(char * const *argv, int options,
74     int (*compar)(const FTSENT **, const FTSENT **))
75 {
76         FTS *sp;
77         FTSENT *p, *root;
78         int nitems;
79         FTSENT *parent, *tmp;
80         size_t len;
82         /* Options check. */
83         if (options & ~FTS_OPTIONMASK) {
84                 errno = EINVAL;
85                 return (NULL);
86         }
88         /* Allocate/initialize the stream */
89         if ((sp = calloc(1, sizeof(FTS))) == NULL)
90                 return (NULL);
91         sp->fts_compar = compar;
92         sp->fts_options = options;
94         /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
95         if (ISSET(FTS_LOGICAL))
96                 SET(FTS_NOCHDIR);
98         /*
99          * Start out with 1K of path space, and enough, in any case,
100          * to hold the user's paths.
101          */
102         if (fts_palloc(sp, MAX(fts_maxarglen(argv), PATH_MAX)))
103                 goto mem1;
105         /* Allocate/initialize root's parent. */
106         if ((parent = fts_alloc(sp, "", 0)) == NULL)
107                 goto mem2;
108         parent->fts_level = FTS_ROOTPARENTLEVEL;
110         /* Allocate/initialize root(s). */
111         for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
112                 /* Don't allow zero-length paths. */
113                 if ((len = strlen(*argv)) == 0) {
114                         errno = ENOENT;
115                         goto mem3;
116                 }
118                 if ((p = fts_alloc(sp, *argv, len)) == NULL)
119                         goto mem3;
120                 p->fts_level = FTS_ROOTLEVEL;
121                 p->fts_parent = parent;
122                 p->fts_accpath = p->fts_name;
123                 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW), -1);
125                 /* Command-line "." and ".." are real directories. */
126                 if (p->fts_info == FTS_DOT)
127                         p->fts_info = FTS_D;
129                 /*
130                  * If comparison routine supplied, traverse in sorted
131                  * order; otherwise traverse in the order specified.
132                  */
133                 if (compar) {
134                         p->fts_link = root;
135                         root = p;
136                 } else {
137                         p->fts_link = NULL;
138                         if (root == NULL)
139                                 tmp = root = p;
140                         else {
141                                 tmp->fts_link = p;
142                                 tmp = p;
143                         }
144                 }
145         }
146         if (compar && nitems > 1)
147                 root = fts_sort(sp, root, nitems);
149         /*
150          * Allocate a dummy pointer and make fts_read think that we've just
151          * finished the node before the root(s); set p->fts_info to FTS_INIT
152          * so that everything about the "current" node is ignored.
153          */
154         if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
155                 goto mem3;
156         sp->fts_cur->fts_link = root;
157         sp->fts_cur->fts_info = FTS_INIT;
159         /*
160          * If using chdir(2), grab a file descriptor pointing to dot to ensure
161          * that we can get back here; this could be avoided for some paths,
162          * but almost certainly not worth the effort.  Slashes, symbolic links,
163          * and ".." are all fairly nasty problems.  Note, if we can't get the
164          * descriptor we run anyway, just more slowly.
165          */
166         if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)
167                 SET(FTS_NOCHDIR);
169         if (nitems == 0)
170                 free(parent);
172         return (sp);
174 mem3:   fts_lfree(root);
175         free(parent);
176 mem2:   free(sp->fts_path);
177 mem1:   free(sp);
178         return (NULL);
181 static void
182 fts_load(FTS *sp, FTSENT *p)
184         size_t len;
185         char *cp;
187         /*
188          * Load the stream structure for the next traversal.  Since we don't
189          * actually enter the directory until after the preorder visit, set
190          * the fts_accpath field specially so the chdir gets done to the right
191          * place and the user can access the first node.  From fts_open it's
192          * known that the path will fit.
193          */
194         len = p->fts_pathlen = p->fts_namelen;
195         memmove(sp->fts_path, p->fts_name, len + 1);
196         if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
197                 len = strlen(++cp);
198                 memmove(p->fts_name, cp, len + 1);
199                 p->fts_namelen = len;
200         }
201         p->fts_accpath = p->fts_path = sp->fts_path;
202         sp->fts_dev = p->fts_dev;
205 int
206 fts_close(FTS *sp)
208         FTSENT *freep, *p;
209         int rfd, error = 0;
211         /*
212          * This still works if we haven't read anything -- the dummy structure
213          * points to the root list, so we step through to the end of the root
214          * list which has a valid parent pointer.
215          */
216         if (sp->fts_cur) {
217                 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
218                         freep = p;
219                         p = p->fts_link ? p->fts_link : p->fts_parent;
220                         free(freep);
221                 }
222                 free(p);
223         }
225         /* Stash the original directory fd if needed. */
226         rfd = ISSET(FTS_NOCHDIR) ? -1 : sp->fts_rfd;
228         /* Free up child linked list, sort array, path buffer, stream ptr.*/
229         if (sp->fts_child)
230                 fts_lfree(sp->fts_child);
231         if (sp->fts_array)
232                 free(sp->fts_array);
233         free(sp->fts_path);
234         free(sp);
236         /* Return to original directory, checking for error. */
237         if (rfd != -1) {
238                 int saved_errno;
239                 error = fchdir(rfd);
240                 saved_errno = errno;
241                 (void)close(rfd);
242                 errno = saved_errno;
243         }
245         return (error);
248 /*
249  * Special case of "/" at the end of the path so that slashes aren't
250  * appended which would cause paths to be written as "....//foo".
251  */
252 #define NAPPEND(p)                                                      \
253         (p->fts_path[p->fts_pathlen - 1] == '/'                         \
254             ? p->fts_pathlen - 1 : p->fts_pathlen)
256 FTSENT *
257 fts_read(FTS *sp)
259         FTSENT *p, *tmp;
260         int instr;
261         char *t;
262         int saved_errno;
264         /* If finished or unrecoverable error, return NULL. */
265         if (sp->fts_cur == NULL || ISSET(FTS_STOP))
266                 return (NULL);
268         /* Set current node pointer. */
269         p = sp->fts_cur;
271         /* Save and zero out user instructions. */
272         instr = p->fts_instr;
273         p->fts_instr = FTS_NOINSTR;
275         /* Any type of file may be re-visited; re-stat and re-turn. */
276         if (instr == FTS_AGAIN) {
277                 p->fts_info = fts_stat(sp, p, 0, -1);
278                 return (p);
279         }
281         /*
282          * Following a symlink -- SLNONE test allows application to see
283          * SLNONE and recover.  If indirecting through a symlink, have
284          * keep a pointer to current location.  If unable to get that
285          * pointer, follow fails.
286          */
287         if (instr == FTS_FOLLOW &&
288             (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
289                 p->fts_info = fts_stat(sp, p, 1, -1);
290                 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
291                         if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) {
292                                 p->fts_errno = errno;
293                                 p->fts_info = FTS_ERR;
294                         } else
295                                 p->fts_flags |= FTS_SYMFOLLOW;
296                 }
297                 return (p);
298         }
300         /* Directory in pre-order. */
301         if (p->fts_info == FTS_D) {
302                 /* If skipped or crossed mount point, do post-order visit. */
303                 if (instr == FTS_SKIP ||
304                     (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
305                         if (p->fts_flags & FTS_SYMFOLLOW)
306                                 (void)close(p->fts_symfd);
307                         if (sp->fts_child) {
308                                 fts_lfree(sp->fts_child);
309                                 sp->fts_child = NULL;
310                         }
311                         p->fts_info = FTS_DP;
312                         return (p);
313                 }
315                 /* Rebuild if only read the names and now traversing. */
316                 if (sp->fts_child && ISSET(FTS_NAMEONLY)) {
317                         CLR(FTS_NAMEONLY);
318                         fts_lfree(sp->fts_child);
319                         sp->fts_child = NULL;
320                 }
322                 /*
323                  * Cd to the subdirectory.
324                  *
325                  * If have already read and now fail to chdir, whack the list
326                  * to make the names come out right, and set the parent errno
327                  * so the application will eventually get an error condition.
328                  * Set the FTS_DONTCHDIR flag so that when we logically change
329                  * directories back to the parent we don't do a chdir.
330                  *
331                  * If haven't read do so.  If the read fails, fts_build sets
332                  * FTS_STOP or the fts_info field of the node.
333                  */
334                 if (sp->fts_child) {
335                         if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
336                                 p->fts_errno = errno;
337                                 p->fts_flags |= FTS_DONTCHDIR;
338                                 for (p = sp->fts_child; p; p = p->fts_link)
339                                         p->fts_accpath =
340                                             p->fts_parent->fts_accpath;
341                         }
342                 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
343                         if (ISSET(FTS_STOP))
344                                 return (NULL);
345                         return (p);
346                 }
347                 p = sp->fts_child;
348                 sp->fts_child = NULL;
349                 goto name;
350         }
352         /* Move to the next node on this level. */
353 next:   tmp = p;
354         if ((p = p->fts_link)) {
355                 free(tmp);
357                 /*
358                  * If reached the top, return to the original directory (or
359                  * the root of the tree), and load the paths for the next root.
360                  */
361                 if (p->fts_level == FTS_ROOTLEVEL) {
362                         if (FCHDIR(sp, sp->fts_rfd)) {
363                                 SET(FTS_STOP);
364                                 return (NULL);
365                         }
366                         fts_load(sp, p);
367                         return (sp->fts_cur = p);
368                 }
370                 /*
371                  * User may have called fts_set on the node.  If skipped,
372                  * ignore.  If followed, get a file descriptor so we can
373                  * get back if necessary.
374                  */
375                 if (p->fts_instr == FTS_SKIP)
376                         goto next;
377                 if (p->fts_instr == FTS_FOLLOW) {
378                         p->fts_info = fts_stat(sp, p, 1, -1);
379                         if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
380                                 if ((p->fts_symfd =
381                                     open(".", O_RDONLY, 0)) < 0) {
382                                         p->fts_errno = errno;
383                                         p->fts_info = FTS_ERR;
384                                 } else
385                                         p->fts_flags |= FTS_SYMFOLLOW;
386                         }
387                         p->fts_instr = FTS_NOINSTR;
388                 }
390 name:           t = sp->fts_path + NAPPEND(p->fts_parent);
391                 *t++ = '/';
392                 memmove(t, p->fts_name, p->fts_namelen + 1);
393                 return (sp->fts_cur = p);
394         }
396         /* Move up to the parent node. */
397         p = tmp->fts_parent;
398         free(tmp);
400         if (p->fts_level == FTS_ROOTPARENTLEVEL) {
401                 /*
402                  * Done; free everything up and set errno to 0 so the user
403                  * can distinguish between error and EOF.
404                  */
405                 free(p);
406                 errno = 0;
407                 return (sp->fts_cur = NULL);
408         }
410         /* NUL terminate the pathname. */
411         sp->fts_path[p->fts_pathlen] = '\0';
413         /*
414          * Return to the parent directory.  If at a root node or came through
415          * a symlink, go back through the file descriptor.  Otherwise, cd up
416          * one directory.
417          */
418         if (p->fts_level == FTS_ROOTLEVEL) {
419                 if (FCHDIR(sp, sp->fts_rfd)) {
420                         SET(FTS_STOP);
421                         sp->fts_cur = p;
422                         return (NULL);
423                 }
424         } else if (p->fts_flags & FTS_SYMFOLLOW) {
425                 if (FCHDIR(sp, p->fts_symfd)) {
426                         saved_errno = errno;
427                         (void)close(p->fts_symfd);
428                         errno = saved_errno;
429                         SET(FTS_STOP);
430                         sp->fts_cur = p;
431                         return (NULL);
432                 }
433                 (void)close(p->fts_symfd);
434         } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
435             fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
436                 SET(FTS_STOP);
437                 sp->fts_cur = p;
438                 return (NULL);
439         }
440         p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
441         return (sp->fts_cur = p);
444 /*
445  * Fts_set takes the stream as an argument although it's not used in this
446  * implementation; it would be necessary if anyone wanted to add global
447  * semantics to fts using fts_set.  An error return is allowed for similar
448  * reasons.
449  */
450 /* ARGSUSED */
451 int
452 fts_set(FTS *sp __unused, FTSENT *p, int instr)
454         if (instr && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
455             instr != FTS_NOINSTR && instr != FTS_SKIP) {
456                 errno = EINVAL;
457                 return (1);
458         }
459         p->fts_instr = instr;
460         return (0);
463 FTSENT *
464 fts_children(FTS *sp, int instr)
466         FTSENT *p;
467         int fd;
469         if (instr && instr != FTS_NAMEONLY) {
470                 errno = EINVAL;
471                 return (NULL);
472         }
474         /* Set current node pointer. */
475         p = sp->fts_cur;
477         /*
478          * Errno set to 0 so user can distinguish empty directory from
479          * an error.
480          */
481         errno = 0;
483         /* Fatal errors stop here. */
484         if (ISSET(FTS_STOP))
485                 return (NULL);
487         /* Return logical hierarchy of user's arguments. */
488         if (p->fts_info == FTS_INIT)
489                 return (p->fts_link);
491         /*
492          * If not a directory being visited in pre-order, stop here.  Could
493          * allow FTS_DNR, assuming the user has fixed the problem, but the
494          * same effect is available with FTS_AGAIN.
495          */
496         if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
497                 return (NULL);
499         /* Free up any previous child list. */
500         if (sp->fts_child)
501                 fts_lfree(sp->fts_child);
503         if (instr == FTS_NAMEONLY) {
504                 SET(FTS_NAMEONLY);
505                 instr = BNAMES;
506         } else
507                 instr = BCHILD;
509         /*
510          * If using chdir on a relative path and called BEFORE fts_read does
511          * its chdir to the root of a traversal, we can lose -- we need to
512          * chdir into the subdirectory, and we don't know where the current
513          * directory is, so we can't get back so that the upcoming chdir by
514          * fts_read will work.
515          */
516         if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
517             ISSET(FTS_NOCHDIR))
518                 return (sp->fts_child = fts_build(sp, instr));
520         if ((fd = open(".", O_RDONLY, 0)) < 0)
521                 return (NULL);
522         sp->fts_child = fts_build(sp, instr);
523         if (fchdir(fd)) {
524                 (void)close(fd);
525                 return (NULL);
526         }
527         (void)close(fd);
528         return (sp->fts_child);
531 /*
532  * This is the tricky part -- do not casually change *anything* in here.  The
533  * idea is to build the linked list of entries that are used by fts_children
534  * and fts_read.  There are lots of special cases.
535  *
536  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
537  * set and it's a physical walk (so that symbolic links can't be directories),
538  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
539  * of the file is in the directory entry.  Otherwise, we assume that the number
540  * of subdirectories in a node is equal to the number of links to the parent.
541  * The former skips all stat calls.  The latter skips stat calls in any leaf
542  * directories and for any files after the subdirectories in the directory have
543  * been found, cutting the stat calls by about 2/3.
544  */
545 static FTSENT *
546 fts_build(FTS *sp, int type)
548         struct dirent *dp;
549         FTSENT *p, *head;
550         FTSENT *cur, *tail;
551         DIR *dirp;
552         void *oldaddr;
553         size_t len, maxlen;
554         int nitems, cderrno, descend, level, nlinks, nostat = 0, doadjust;
555         int saved_errno;
556         char *cp = NULL;
558         /* Set current node pointer. */
559         cur = sp->fts_cur;
561         /*
562          * Open the directory for reading.  If this fails, we're done.
563          * If being called from fts_read, set the fts_info field.
564          */
565         if ((dirp = opendir(cur->fts_accpath)) == NULL) {
566                 if (type == BREAD) {
567                         cur->fts_info = FTS_DNR;
568                         cur->fts_errno = errno;
569                 }
570                 return (NULL);
571         }
573         /*
574          * Nlinks is the number of possible entries of type directory in the
575          * directory if we're cheating on stat calls, 0 if we're not doing
576          * any stat calls at all, -1 if we're doing stats on everything.
577          */
578         if (type == BNAMES)
579                 nlinks = 0;
580         else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
581                 nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
582                 nostat = 1;
583         } else {
584                 nlinks = -1;
585                 nostat = 0;
586         }
588 #ifdef notdef
589         (void)printf("nlinks == %d (cur: %u)\n", nlinks, cur->fts_nlink);
590         (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
591             ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
592 #endif
593         /*
594          * If we're going to need to stat anything or we want to descend
595          * and stay in the directory, chdir.  If this fails we keep going,
596          * but set a flag so we don't chdir after the post-order visit.
597          * We won't be able to stat anything, but we can still return the
598          * names themselves.  Note, that since fts_read won't be able to
599          * chdir into the directory, it will have to return different path
600          * names than before, i.e. "a/b" instead of "b".  Since the node
601          * has already been visited in pre-order, have to wait until the
602          * post-order visit to return the error.  There is a special case
603          * here, if there was nothing to stat then it's not an error to
604          * not be able to stat.  This is all fairly nasty.  If a program
605          * needed sorted entries or stat information, they had better be
606          * checking FTS_NS on the returned nodes.
607          */
608         cderrno = 0;
609         if (nlinks || type == BREAD) {
610                 if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
611                         if (nlinks && type == BREAD)
612                                 cur->fts_errno = errno;
613                         cur->fts_flags |= FTS_DONTCHDIR;
614                         descend = 0;
615                         cderrno = errno;
616                         (void)closedir(dirp);
617                         dirp = NULL;
618                 } else
619                         descend = 1;
620         } else
621                 descend = 0;
623         /*
624          * Figure out the max file name length that can be stored in the
625          * current path -- the inner loop allocates more path as necessary.
626          * We really wouldn't have to do the maxlen calculations here, we
627          * could do them in fts_read before returning the path, but it's a
628          * lot easier here since the length is part of the dirent structure.
629          *
630          * If not changing directories set a pointer so that can just append
631          * each new name into the path.
632          */
633         len = NAPPEND(cur);
634         if (ISSET(FTS_NOCHDIR)) {
635                 cp = sp->fts_path + len;
636                 *cp++ = '/';
637         }
638         len++;
639         maxlen = sp->fts_pathlen - len;
641         /*
642          * fts_level is signed so we must prevent it from wrapping
643          * around to FTS_ROOTLEVEL and FTS_ROOTPARENTLEVEL.
644          */
645         level = cur->fts_level;
646         if (level < FTS_MAXLEVEL)
647             level++;
649         /* Read the directory, attaching each entry to the `link' pointer. */
650         doadjust = 0;
651         for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
652                 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
653                         continue;
655                 if (!(p = fts_alloc(sp, dp->d_name, strlen(dp->d_name))))
656                         goto mem1;
657                 if (strlen(dp->d_name) >= maxlen) {     /* include space for NUL */
658                         oldaddr = sp->fts_path;
659                         if (fts_palloc(sp, strlen(dp->d_name) +len + 1)) {
660                                 /*
661                                  * No more memory for path or structures.  Save
662                                  * errno, free up the current structure and the
663                                  * structures already allocated.
664                                  */
665 mem1:                           saved_errno = errno;
666                                 if (p)
667                                         free(p);
668                                 fts_lfree(head);
669                                 (void)closedir(dirp);
670                                 cur->fts_info = FTS_ERR;
671                                 SET(FTS_STOP);
672                                 errno = saved_errno;
673                                 return (NULL);
674                         }
675                         /* Did realloc() change the pointer? */
676                         if (oldaddr != sp->fts_path) {
677                                 doadjust = 1;
678                                 if (ISSET(FTS_NOCHDIR))
679                                         cp = sp->fts_path + len;
680                         }
681                         maxlen = sp->fts_pathlen - len;
682                 }
684                 p->fts_level = level;
685                 p->fts_parent = sp->fts_cur;
686                 p->fts_pathlen = len + strlen(dp->d_name);
687                 if (p->fts_pathlen < len) {
688                         /*
689                          * If we wrap, free up the current structure and
690                          * the structures already allocated, then error
691                          * out with ENAMETOOLONG.
692                          */
693                         free(p);
694                         fts_lfree(head);
695                         (void)closedir(dirp);
696                         cur->fts_info = FTS_ERR;
697                         SET(FTS_STOP);
698                         errno = ENAMETOOLONG;
699                         return (NULL);
700                 }
702                 if (cderrno) {
703                         if (nlinks) {
704                                 p->fts_info = FTS_NS;
705                                 p->fts_errno = cderrno;
706                         } else
707                                 p->fts_info = FTS_NSOK;
708                         p->fts_accpath = cur->fts_accpath;
709                 } else if (nlinks == 0
710 #ifdef DT_DIR
711                     || (nostat &&
712                     dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
713 #endif
714                     ) {
715                         p->fts_accpath =
716                             ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
717                         p->fts_info = FTS_NSOK;
718                 } else {
719                         /* Build a file name for fts_stat to stat. */
720                         if (ISSET(FTS_NOCHDIR)) {
721                                 p->fts_accpath = p->fts_path;
722                                 memmove(cp, p->fts_name, p->fts_namelen + 1);
723                                 p->fts_info = fts_stat(sp, p, 0, dirfd(dirp));
724                         } else {
725                                 p->fts_accpath = p->fts_name;
726                                 p->fts_info = fts_stat(sp, p, 0, -1);
727                         }
729                         /* Decrement link count if applicable. */
730                         if (nlinks > 0 && (p->fts_info == FTS_D ||
731                             p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
732                                 --nlinks;
733                 }
735                 /* We walk in directory order so "ls -f" doesn't get upset. */
736                 p->fts_link = NULL;
737                 if (head == NULL)
738                         head = tail = p;
739                 else {
740                         tail->fts_link = p;
741                         tail = p;
742                 }
743                 ++nitems;
744         }
745         if (dirp)
746                 (void)closedir(dirp);
748         /*
749          * If realloc() changed the address of the path, adjust the
750          * addresses for the rest of the tree and the dir list.
751          */
752         if (doadjust)
753                 fts_padjust(sp, head);
755         /*
756          * If not changing directories, reset the path back to original
757          * state.
758          */
759         if (ISSET(FTS_NOCHDIR)) {
760                 if (len == sp->fts_pathlen || nitems == 0)
761                         --cp;
762                 *cp = '\0';
763         }
765         /*
766          * If descended after called from fts_children or after called from
767          * fts_read and nothing found, get back.  At the root level we use
768          * the saved fd; if one of fts_open()'s arguments is a relative path
769          * to an empty directory, we wind up here with no other way back.  If
770          * can't get back, we're done.
771          */
772         if (descend && (type == BCHILD || !nitems) &&
773             (cur->fts_level == FTS_ROOTLEVEL ? FCHDIR(sp, sp->fts_rfd) :
774             fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
775                 cur->fts_info = FTS_ERR;
776                 SET(FTS_STOP);
777                 return (NULL);
778         }
780         /* If didn't find anything, return NULL. */
781         if (!nitems) {
782                 if (type == BREAD)
783                         cur->fts_info = FTS_DP;
784                 return (NULL);
785         }
787         /* Sort the entries. */
788         if (sp->fts_compar && nitems > 1)
789                 head = fts_sort(sp, head, nitems);
790         return (head);
793 static u_short
794 fts_stat(FTS *sp, FTSENT *p, int follow, int dfd)
796         FTSENT *t;
797         dev_t dev;
798         ino_t ino;
799         struct stat *sbp, sb;
800         int saved_errno;
801         const char *path;
803         if (dfd == -1) {
804                 path = p->fts_accpath;
805                 dfd = AT_FDCWD;
806         } else
807                 path = p->fts_name;
809         /* If user needs stat info, stat buffer already allocated. */
810         sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
812         /*
813          * If doing a logical walk, or application requested FTS_FOLLOW, do
814          * a stat(2).  If that fails, check for a non-existent symlink.  If
815          * fail, set the errno from the stat call.
816          */
817         if (ISSET(FTS_LOGICAL) || follow) {
818                 if (fstatat(dfd, path, sbp, 0)) {
819                         saved_errno = errno;
820                         if (!fstatat(dfd, path, sbp, AT_SYMLINK_NOFOLLOW)) {
821                                 errno = 0;
822                                 return (FTS_SLNONE);
823                         }
824                         p->fts_errno = saved_errno;
825                         goto err;
826                 }
827         } else if (fstatat(dfd, path, sbp, AT_SYMLINK_NOFOLLOW)) {
828                 p->fts_errno = errno;
829 err:            memset(sbp, 0, sizeof(struct stat));
830                 return (FTS_NS);
831         }
833         if (S_ISDIR(sbp->st_mode)) {
834                 /*
835                  * Set the device/inode.  Used to find cycles and check for
836                  * crossing mount points.  Also remember the link count, used
837                  * in fts_build to limit the number of stat calls.  It is
838                  * understood that these fields are only referenced if fts_info
839                  * is set to FTS_D.
840                  */
841                 dev = p->fts_dev = sbp->st_dev;
842                 ino = p->fts_ino = sbp->st_ino;
843                 p->fts_nlink = sbp->st_nlink;
845                 if (ISDOT(p->fts_name))
846                         return (FTS_DOT);
848                 /*
849                  * Cycle detection is done by brute force when the directory
850                  * is first encountered.  If the tree gets deep enough or the
851                  * number of symbolic links to directories is high enough,
852                  * something faster might be worthwhile.
853                  */
854                 for (t = p->fts_parent;
855                     t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
856                         if (ino == t->fts_ino && dev == t->fts_dev) {
857                                 p->fts_cycle = t;
858                                 return (FTS_DC);
859                         }
860                 return (FTS_D);
861         }
862         if (S_ISLNK(sbp->st_mode))
863                 return (FTS_SL);
864         if (S_ISREG(sbp->st_mode))
865                 return (FTS_F);
866         return (FTS_DEFAULT);
869 static FTSENT *
870 fts_sort(FTS *sp, FTSENT *head, int nitems)
872         FTSENT **ap, *p;
874         /*
875          * Construct an array of pointers to the structures and call qsort(3).
876          * Reassemble the array in the order returned by qsort.  If unable to
877          * sort for memory reasons, return the directory entries in their
878          * current order.  Allocate enough space for the current needs plus
879          * 40 so don't realloc one entry at a time.
880          */
881         if (nitems > sp->fts_nitems) {
882                 struct _ftsent **a;
884                 sp->fts_nitems = nitems + 40;
885                 if ((a = reallocarray(sp->fts_array,
886                     sp->fts_nitems, sizeof(FTSENT *))) == NULL) {
887                         if (sp->fts_array)
888                                 free(sp->fts_array);
889                         sp->fts_array = NULL;
890                         sp->fts_nitems = 0;
891                         return (head);
892                 }
893                 sp->fts_array = a;
894         }
895         for (ap = sp->fts_array, p = head; p; p = p->fts_link)
896                 *ap++ = p;
897         qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
898         for (head = *(ap = sp->fts_array); --nitems; ++ap)
899                 ap[0]->fts_link = ap[1];
900         ap[0]->fts_link = NULL;
901         return (head);
904 static FTSENT *
905 fts_alloc(FTS *sp, char *name, size_t namelen)
907         FTSENT *p;
908         size_t len;
910         /*
911          * The file name is a variable length array and no stat structure is
912          * necessary if the user has set the nostat bit.  Allocate the FTSENT
913          * structure, the file name and the stat structure in one chunk, but
914          * be careful that the stat structure is reasonably aligned.  Since the
915          * fts_name field is declared to be of size 1, the fts_name pointer is
916          * namelen + 2 before the first possible address of the stat structure.
917          */
918         len = sizeof(FTSENT) + namelen;
919         if (!ISSET(FTS_NOSTAT))
920                 len += sizeof(struct stat) + ALIGNBYTES;
921         if ((p = calloc(1, len)) == NULL)
922                 return (NULL);
924         p->fts_path = sp->fts_path;
925         p->fts_namelen = namelen;
926         p->fts_instr = FTS_NOINSTR;
927         if (!ISSET(FTS_NOSTAT))
928                 p->fts_statp = (struct stat *)ALIGN(p->fts_name + namelen + 2);
929         memcpy(p->fts_name, name, namelen);
931         return (p);
934 static void
935 fts_lfree(FTSENT *head)
937         FTSENT *p;
939         /* Free a linked list of structures. */
940         while ((p = head)) {
941                 head = head->fts_link;
942                 free(p);
943         }
946 /*
947  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
948  * Most systems will allow creation of paths much longer than PATH_MAX, even
949  * though the kernel won't resolve them.  Add the size (not just what's needed)
950  * plus 256 bytes so don't realloc the path 2 bytes at a time.
951  */
952 static int
953 fts_palloc(FTS *sp, size_t more)
955         char *p;
957         /*
958          * Check for possible wraparound.
959          */
960         more += 256;
961         if (sp->fts_pathlen + more < sp->fts_pathlen) {
962                 if (sp->fts_path)
963                         free(sp->fts_path);
964                 sp->fts_path = NULL;
965                 errno = ENAMETOOLONG;
966                 return (1);
967         }
968         sp->fts_pathlen += more;
969         p = realloc(sp->fts_path, sp->fts_pathlen);
970         if (p == NULL) {
971                 if (sp->fts_path)
972                         free(sp->fts_path);
973                 sp->fts_path = NULL;
974                 return (1);
975         }
976         sp->fts_path = p;
977         return (0);
980 /*
981  * When the path is realloc'd, have to fix all of the pointers in structures
982  * already returned.
983  */
984 static void
985 fts_padjust(FTS *sp, FTSENT *head)
987         FTSENT *p;
988         char *addr = sp->fts_path;
990 #define ADJUST(p) {                                                     \
991         if ((p)->fts_accpath != (p)->fts_name) {                        \
992                 (p)->fts_accpath =                                      \
993                     (char *)addr + ((p)->fts_accpath - (p)->fts_path);  \
994         }                                                               \
995         (p)->fts_path = addr;                                           \
997         /* Adjust the current set of children. */
998         for (p = sp->fts_child; p; p = p->fts_link)
999                 ADJUST(p);
1001         /* Adjust the rest of the tree, including the current level. */
1002         for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1003                 ADJUST(p);
1004                 p = p->fts_link ? p->fts_link : p->fts_parent;
1005         }
1008 static size_t
1009 fts_maxarglen(char * const *argv)
1011         size_t len, max;
1013         for (max = 0; *argv; ++argv)
1014                 if ((len = strlen(*argv)) > max)
1015                         max = len;
1016         return (max + 1);
1019 /*
1020  * Change to dir specified by fd or p->fts_accpath without getting
1021  * tricked by someone changing the world out from underneath us.
1022  * Assumes p->fts_dev and p->fts_ino are filled in.
1023  */
1024 static int
1025 fts_safe_changedir(FTS *sp, FTSENT *p, int fd, char *path)
1027         int ret, oerrno, newfd;
1028         struct stat sb;
1030         newfd = fd;
1031         if (ISSET(FTS_NOCHDIR))
1032                 return (0);
1033         if (fd < 0 && (newfd = open(path, O_RDONLY, 0)) < 0)
1034                 return (-1);
1035         if (fstat(newfd, &sb)) {
1036                 ret = -1;
1037                 goto bail;
1038         }
1039         if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {
1040                 errno = ENOENT;         /* disinformation */
1041                 ret = -1;
1042                 goto bail;
1043         }
1044         ret = fchdir(newfd);
1045 bail:
1046         oerrno = errno;
1047         if (fd < 0)
1048                 (void)close(newfd);
1049         errno = oerrno;
1050         return (ret);