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