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