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