1/* File tree traversal functions.
2 Copyright (C) 1994-2023 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 <stdint.h>
59#include <stdlib.h>
60#include <string.h>
61#include <unistd.h>
62
63
64/* Largest alignment size needed, minus one.
65 Usually long double is the worst case. */
66#ifndef ALIGNBYTES
67#define ALIGNBYTES (__alignof__ (long double) - 1)
68#endif
69/* Align P to that size. */
70#ifndef ALIGN
71#define ALIGN(p) (((uintptr_t) (p) + ALIGNBYTES) & ~ALIGNBYTES)
72#endif
73
74
75/* Support for the LFS API version. */
76#ifndef FTS_OPEN
77#define FTS_OPEN fts_open
78#define FTS_CLOSE fts_close
79#define FTS_READ fts_read
80#define FTS_SET fts_set
81#define FTS_CHILDREN fts_children
82# define FTSOBJ FTS
83# define FTSENTRY FTSENT
84# define INO_T ino_t
85# define STRUCT_STAT stat
86# define STAT __stat
87# define LSTAT __lstat
88#endif
89
90static FTSENTRY *fts_alloc (FTSOBJ *, const char *, size_t);
91static FTSENTRY *fts_build (FTSOBJ *, int);
92static void fts_lfree (FTSENTRY *);
93static void fts_load (FTSOBJ *, FTSENTRY *);
94static size_t fts_maxarglen (char * const *);
95static void fts_padjust (FTSOBJ *, FTSENTRY *);
96static int fts_palloc (FTSOBJ *, size_t);
97static FTSENTRY *fts_sort (FTSOBJ *, FTSENTRY *, int);
98static u_short fts_stat (FTSOBJ *, FTSENTRY *, int);
99static int fts_safe_changedir (FTSOBJ *, FTSENTRY *, int, const char *);
100
101#ifndef MAX
102#define MAX(a, b) ({ __typeof__ (a) _a = (a); \
103 __typeof__ (b) _b = (b); \
104 _a > _b ? _a : _b; })
105#endif
106
107#define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
108
109#define CLR(opt) (sp->fts_options &= ~(opt))
110#define ISSET(opt) (sp->fts_options & (opt))
111#define SET(opt) (sp->fts_options |= (opt))
112
113#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && __fchdir(fd))
114
115/* fts_build flags */
116#define BCHILD 1 /* fts_children */
117#define BNAMES 2 /* fts_children, names only */
118#define BREAD 3 /* fts_read */
119
120FTSOBJ *
121FTS_OPEN (char * const *argv, int options,
122 int (*compar) (const FTSENTRY **, const FTSENTRY **))
123{
124 FTSOBJ *sp;
125 FTSENTRY *p, *root;
126 int nitems;
127 FTSENTRY *parent = NULL;
128 FTSENTRY *tmp;
129
130 /* Options check. */
131 if (options & ~FTS_OPTIONMASK) {
132 __set_errno (EINVAL);
133 return (NULL);
134 }
135
136 /* Allocate/initialize the stream */
137 if ((sp = malloc((u_int)sizeof(FTSOBJ))) == NULL)
138 return (NULL);
139 memset(sp, 0, sizeof(FTSOBJ));
140 sp->fts_compar = (int (*) (const void *, const void *)) compar;
141 sp->fts_options = options;
142
143 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
144 if (ISSET(FTS_LOGICAL))
145 SET(FTS_NOCHDIR);
146
147 /*
148 * Start out with 1K of path space, and enough, in any case,
149 * to hold the user's paths.
150 */
151#ifndef MAXPATHLEN
152#define MAXPATHLEN 1024
153#endif
154 size_t maxarglen = fts_maxarglen(argv);
155 if (fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
156 goto mem1;
157
158 /* Allocate/initialize root's parent. */
159 if (*argv != NULL) {
160 if ((parent = fts_alloc(sp, "", 0)) == NULL)
161 goto mem2;
162 parent->fts_level = FTS_ROOTPARENTLEVEL;
163 }
164
165 /* Allocate/initialize root(s). */
166 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
167 /* Don't allow zero-length paths. */
168 size_t len = strlen(*argv);
169 if (len == 0) {
170 __set_errno (ENOENT);
171 goto mem3;
172 }
173
174 p = fts_alloc(sp, *argv, len);
175 p->fts_level = FTS_ROOTLEVEL;
176 p->fts_parent = parent;
177 p->fts_accpath = p->fts_name;
178 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));
179
180 /* Command-line "." and ".." are real directories. */
181 if (p->fts_info == FTS_DOT)
182 p->fts_info = FTS_D;
183
184 /*
185 * If comparison routine supplied, traverse in sorted
186 * order; otherwise traverse in the order specified.
187 */
188 if (compar) {
189 p->fts_link = root;
190 root = p;
191 } else {
192 p->fts_link = NULL;
193 if (root == NULL)
194 tmp = root = p;
195 else {
196 tmp->fts_link = p;
197 tmp = p;
198 }
199 }
200 }
201 if (compar && nitems > 1)
202 root = fts_sort(sp, root, nitems);
203
204 /*
205 * Allocate a dummy pointer and make fts_read think that we've just
206 * finished the node before the root(s); set p->fts_info to FTS_INIT
207 * so that everything about the "current" node is ignored.
208 */
209 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
210 goto mem3;
211 sp->fts_cur->fts_link = root;
212 sp->fts_cur->fts_info = FTS_INIT;
213
214 /*
215 * If using chdir(2), grab a file descriptor pointing to dot to ensure
216 * that we can get back here; this could be avoided for some paths,
217 * but almost certainly not worth the effort. Slashes, symbolic links,
218 * and ".." are all fairly nasty problems. Note, if we can't get the
219 * descriptor we run anyway, just more slowly.
220 */
221 if (!ISSET(FTS_NOCHDIR)
222 && (sp->fts_rfd = __open(".", O_RDONLY, 0)) < 0)
223 SET(FTS_NOCHDIR);
224
225 return (sp);
226
227mem3: fts_lfree(root);
228 free(parent);
229mem2: free(sp->fts_path);
230mem1: free(sp);
231 return (NULL);
232}
233
234static void
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 *
610fts_build (FTSOBJ *sp, int type)
611{
612 struct dirent *dp;
613 FTSENTRY *p, *head;
614 int nitems;
615 FTSENTRY *cur, *tail;
616 DIR *dirp;
617 void *oldaddr;
618 int cderrno, descend, len, level, nlinks, saved_errno,
619 nostat, doadjust;
620 size_t maxlen;
621 char *cp;
622
623 /* Set current node pointer. */
624 cur = sp->fts_cur;
625
626 /*
627 * Open the directory for reading. If this fails, we're done.
628 * If being called from fts_read, set the fts_info field.
629 */
630#if defined FTS_WHITEOUT && 0
631 if (ISSET(FTS_WHITEOUT))
632 oflag = DTF_NODUP|DTF_REWIND;
633 else
634 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
635#else
636# define __opendir2(path, flag) __opendir(path)
637#endif
638 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
639 if (type == BREAD) {
640 cur->fts_info = FTS_DNR;
641 cur->fts_errno = errno;
642 }
643 return (NULL);
644 }
645
646 /*
647 * Nlinks is the number of possible entries of type directory in the
648 * directory if we're cheating on stat calls, 0 if we're not doing
649 * any stat calls at all, -1 if we're doing stats on everything.
650 */
651 if (type == BNAMES) {
652 nlinks = 0;
653 /* Be quiet about nostat, GCC. */
654 nostat = 0;
655 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
656 nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
657 nostat = 1;
658 } else {
659 nlinks = -1;
660 nostat = 0;
661 }
662
663#ifdef notdef
664 (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
665 (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
666 ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
667#endif
668 /*
669 * If we're going to need to stat anything or we want to descend
670 * and stay in the directory, chdir. If this fails we keep going,
671 * but set a flag so we don't chdir after the post-order visit.
672 * We won't be able to stat anything, but we can still return the
673 * names themselves. Note, that since fts_read won't be able to
674 * chdir into the directory, it will have to return different path
675 * names than before, i.e. "a/b" instead of "b". Since the node
676 * has already been visited in pre-order, have to wait until the
677 * post-order visit to return the error. There is a special case
678 * here, if there was nothing to stat then it's not an error to
679 * not be able to stat. This is all fairly nasty. If a program
680 * needed sorted entries or stat information, they had better be
681 * checking FTS_NS on the returned nodes.
682 */
683 cderrno = 0;
684 if (nlinks || type == BREAD) {
685 if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
686 if (nlinks && type == BREAD)
687 cur->fts_errno = errno;
688 cur->fts_flags |= FTS_DONTCHDIR;
689 descend = 0;
690 cderrno = errno;
691 (void)__closedir(dirp);
692 dirp = NULL;
693 } else
694 descend = 1;
695 } else
696 descend = 0;
697
698 /*
699 * Figure out the max file name length that can be stored in the
700 * current path -- the inner loop allocates more path as necessary.
701 * We really wouldn't have to do the maxlen calculations here, we
702 * could do them in fts_read before returning the path, but it's a
703 * lot easier here since the length is part of the dirent structure.
704 *
705 * If not changing directories set a pointer so that can just append
706 * each new name into the path.
707 */
708 len = NAPPEND(cur);
709 if (ISSET(FTS_NOCHDIR)) {
710 cp = sp->fts_path + len;
711 *cp++ = '/';
712 } else {
713 /* GCC, you're too verbose. */
714 cp = NULL;
715 }
716 len++;
717 maxlen = sp->fts_pathlen - len;
718
719 level = cur->fts_level + 1;
720
721 /* Read the directory, attaching each entry to the `link' pointer. */
722 doadjust = 0;
723 for (head = tail = NULL, nitems = 0; dirp && (dp = __readdir(dirp));) {
724 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
725 continue;
726
727 if ((p = fts_alloc(sp, dp->d_name, _D_EXACT_NAMLEN (dp))) == NULL)
728 goto mem1;
729 if (_D_EXACT_NAMLEN (dp) >= maxlen) {/* include space for NUL */
730 oldaddr = sp->fts_path;
731 if (fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
732 /*
733 * No more memory for path or structures. Save
734 * errno, free up the current structure and the
735 * structures already allocated.
736 */
737mem1: saved_errno = errno;
738 free(p);
739 fts_lfree(head);
740 (void)__closedir(dirp);
741 cur->fts_info = FTS_ERR;
742 SET(FTS_STOP);
743 __set_errno (saved_errno);
744 return (NULL);
745 }
746 /* Did realloc() change the pointer? */
747 if (oldaddr != sp->fts_path) {
748 doadjust = 1;
749 if (ISSET(FTS_NOCHDIR))
750 cp = sp->fts_path + len;
751 }
752 maxlen = sp->fts_pathlen - len;
753 }
754
755 if (len + _D_EXACT_NAMLEN (dp) >= USHRT_MAX) {
756 /*
757 * In an FTSENT, fts_pathlen is a u_short so it is
758 * possible to wraparound here. If we do, free up
759 * the current structure and the structures already
760 * allocated, then error out with ENAMETOOLONG.
761 */
762 free(p);
763 fts_lfree(head);
764 (void)__closedir(dirp);
765 cur->fts_info = FTS_ERR;
766 SET(FTS_STOP);
767 __set_errno (ENAMETOOLONG);
768 return (NULL);
769 }
770 p->fts_level = level;
771 p->fts_parent = sp->fts_cur;
772 p->fts_pathlen = len + _D_EXACT_NAMLEN (dp);
773
774#if defined FTS_WHITEOUT && 0
775 if (dp->d_type == DT_WHT)
776 p->fts_flags |= FTS_ISW;
777#endif
778
779 /* Unreachable code. cderrno is only ever set to a nonnull
780 value if dirp is closed at the same time. But then we
781 cannot enter this loop. */
782 if (0 && cderrno) {
783 if (nlinks) {
784 p->fts_info = FTS_NS;
785 p->fts_errno = cderrno;
786 } else
787 p->fts_info = FTS_NSOK;
788 p->fts_accpath = cur->fts_accpath;
789 } else if (nlinks == 0
790 || (nostat && dirent_not_directory(dp))) {
791 p->fts_accpath =
792 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
793 p->fts_info = FTS_NSOK;
794 } else {
795 /* Build a file name for fts_stat to stat. */
796 if (ISSET(FTS_NOCHDIR)) {
797 p->fts_accpath = p->fts_path;
798 memmove(cp, p->fts_name, p->fts_namelen + 1);
799 } else
800 p->fts_accpath = p->fts_name;
801 /* Stat it. */
802 p->fts_info = fts_stat(sp, p, 0);
803
804 /* Decrement link count if applicable. */
805 if (nlinks > 0 && (p->fts_info == FTS_D ||
806 p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
807 --nlinks;
808 }
809
810 /* We walk in directory order so "ls -f" doesn't get upset. */
811 p->fts_link = NULL;
812 if (head == NULL)
813 head = tail = p;
814 else {
815 tail->fts_link = p;
816 tail = p;
817 }
818 ++nitems;
819 }
820 if (dirp)
821 (void)__closedir(dirp);
822
823 /*
824 * If realloc() changed the address of the path, adjust the
825 * addresses for the rest of the tree and the dir list.
826 */
827 if (doadjust)
828 fts_padjust(sp, head);
829
830 /*
831 * If not changing directories, reset the path back to original
832 * state.
833 */
834 if (ISSET(FTS_NOCHDIR)) {
835 if (len == sp->fts_pathlen || nitems == 0)
836 --cp;
837 *cp = '\0';
838 }
839
840 /*
841 * If descended after called from fts_children or after called from
842 * fts_read and nothing found, get back. At the root level we use
843 * the saved fd; if one of fts_open()'s arguments is a relative path
844 * to an empty directory, we wind up here with no other way back. If
845 * can't get back, we're done.
846 */
847 if (descend && (type == BCHILD || !nitems) &&
848 (cur->fts_level == FTS_ROOTLEVEL ?
849 FCHDIR(sp, sp->fts_rfd) :
850 fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
851 cur->fts_info = FTS_ERR;
852 SET(FTS_STOP);
853 fts_lfree(head);
854 return (NULL);
855 }
856
857 /* If didn't find anything, return NULL. */
858 if (!nitems) {
859 if (type == BREAD)
860 cur->fts_info = FTS_DP;
861 fts_lfree(head);
862 return (NULL);
863 }
864
865 /* Sort the entries. */
866 if (sp->fts_compar && nitems > 1)
867 head = fts_sort(sp, head, nitems);
868 return (head);
869}
870
871static u_short
872fts_stat (FTSOBJ *sp, FTSENTRY *p, int follow)
873{
874 FTSENTRY *t;
875 dev_t dev;
876 INO_T ino;
877 struct STRUCT_STAT *sbp, sb;
878 int saved_errno;
879
880 /* If user needs stat info, stat buffer already allocated. */
881 sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
882
883#if defined FTS_WHITEOUT && 0
884 /* check for whiteout */
885 if (p->fts_flags & FTS_ISW) {
886 if (sbp != &sb) {
887 memset(sbp, '\0', sizeof (*sbp));
888 sbp->st_mode = S_IFWHT;
889 }
890 return (FTS_W);
891 }
892#endif
893
894 /*
895 * If doing a logical walk, or application requested FTS_FOLLOW, do
896 * a stat(2). If that fails, check for a non-existent symlink. If
897 * fail, set the errno from the stat call.
898 */
899 if (ISSET(FTS_LOGICAL) || follow) {
900 if (STAT(p->fts_accpath, sbp)) {
901 saved_errno = errno;
902 if (!LSTAT(p->fts_accpath, sbp)) {
903 __set_errno (0);
904 return (FTS_SLNONE);
905 }
906 p->fts_errno = saved_errno;
907 goto err;
908 }
909 } else if (LSTAT(p->fts_accpath, sbp)) {
910 p->fts_errno = errno;
911err: memset(sbp, 0, sizeof(struct STRUCT_STAT));
912 return (FTS_NS);
913 }
914
915 if (S_ISDIR(sbp->st_mode)) {
916 /*
917 * Set the device/inode. Used to find cycles and check for
918 * crossing mount points. Also remember the link count, used
919 * in fts_build to limit the number of stat calls. It is
920 * understood that these fields are only referenced if fts_info
921 * is set to FTS_D.
922 */
923 dev = p->fts_dev = sbp->st_dev;
924 ino = p->fts_ino = sbp->st_ino;
925 p->fts_nlink = sbp->st_nlink;
926
927 if (ISDOT(p->fts_name))
928 return (FTS_DOT);
929
930 /*
931 * Cycle detection is done by brute force when the directory
932 * is first encountered. If the tree gets deep enough or the
933 * number of symbolic links to directories is high enough,
934 * something faster might be worthwhile.
935 */
936 for (t = p->fts_parent;
937 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
938 if (ino == t->fts_ino && dev == t->fts_dev) {
939 p->fts_cycle = t;
940 return (FTS_DC);
941 }
942 return (FTS_D);
943 }
944 if (S_ISLNK(sbp->st_mode))
945 return (FTS_SL);
946 if (S_ISREG(sbp->st_mode))
947 return (FTS_F);
948 return (FTS_DEFAULT);
949}
950
951static FTSENTRY *
952fts_sort (FTSOBJ *sp, FTSENTRY *head, int nitems)
953{
954 FTSENTRY **ap, *p;
955
956 /*
957 * Construct an array of pointers to the structures and call qsort(3).
958 * Reassemble the array in the order returned by qsort. If unable to
959 * sort for memory reasons, return the directory entries in their
960 * current order. Allocate enough space for the current needs plus
961 * 40 so don't realloc one entry at a time.
962 */
963 if (nitems > sp->fts_nitems) {
964 FTSENTRY **a;
965
966 sp->fts_nitems = nitems + 40;
967 if ((a = realloc(sp->fts_array,
968 (size_t)(sp->fts_nitems * sizeof(FTSENTRY *)))) == NULL) {
969 free(sp->fts_array);
970 sp->fts_array = NULL;
971 sp->fts_nitems = 0;
972 return (head);
973 }
974 sp->fts_array = a;
975 }
976 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
977 *ap++ = p;
978 qsort((void *)sp->fts_array, nitems, sizeof(FTSENTRY *), sp->fts_compar);
979 for (head = *(ap = sp->fts_array); --nitems; ++ap)
980 ap[0]->fts_link = ap[1];
981 ap[0]->fts_link = NULL;
982 return (head);
983}
984
985static FTSENTRY *
986fts_alloc (FTSOBJ *sp, const char *name, size_t namelen)
987{
988 FTSENTRY *p;
989 size_t len;
990
991 /*
992 * The file name is a variable length array and no stat structure is
993 * necessary if the user has set the nostat bit. Allocate the FTSENT
994 * structure, the file name and the stat structure in one chunk, but
995 * be careful that the stat structure is reasonably aligned. Since the
996 * fts_name field is declared to be of size 1, the fts_name pointer is
997 * namelen + 2 before the first possible address of the stat structure.
998 */
999 len = sizeof(FTSENTRY) + namelen;
1000 if (!ISSET(FTS_NOSTAT))
1001 len += sizeof(struct STRUCT_STAT) + ALIGNBYTES;
1002 if ((p = malloc(len)) == NULL)
1003 return (NULL);
1004
1005 /* Copy the name and guarantee NUL termination. */
1006 memmove(p->fts_name, name, namelen);
1007 p->fts_name[namelen] = '\0';
1008
1009 if (!ISSET(FTS_NOSTAT))
1010 p->fts_statp = (struct STRUCT_STAT *)ALIGN(p->fts_name + namelen + 2);
1011 p->fts_namelen = namelen;
1012 p->fts_path = sp->fts_path;
1013 p->fts_errno = 0;
1014 p->fts_flags = 0;
1015 p->fts_instr = FTS_NOINSTR;
1016 p->fts_number = 0;
1017 p->fts_pointer = NULL;
1018 return (p);
1019}
1020
1021static void
1022fts_lfree (FTSENTRY *head)
1023{
1024 FTSENTRY *p;
1025
1026 /* Free a linked list of structures. */
1027 while ((p = head)) {
1028 head = head->fts_link;
1029 free(p);
1030 }
1031}
1032
1033/*
1034 * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
1035 * Most systems will allow creation of paths much longer than MAXPATHLEN, even
1036 * though the kernel won't resolve them. Add the size (not just what's needed)
1037 * plus 256 bytes so don't realloc the path 2 bytes at a time.
1038 */
1039static int
1040fts_palloc (FTSOBJ *sp, size_t more)
1041{
1042 char *p;
1043
1044 sp->fts_pathlen += more + 256;
1045 /*
1046 * Check for possible wraparound. In an FTS, fts_pathlen is
1047 * a signed int but in an FTSENT it is an unsigned short.
1048 * We limit fts_pathlen to USHRT_MAX to be safe in both cases.
1049 */
1050 if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) {
1051 free(sp->fts_path);
1052 sp->fts_path = NULL;
1053 __set_errno (ENAMETOOLONG);
1054 return (1);
1055 }
1056 p = realloc(sp->fts_path, sp->fts_pathlen);
1057 if (p == NULL) {
1058 free(sp->fts_path);
1059 sp->fts_path = NULL;
1060 return 1;
1061 }
1062 sp->fts_path = p;
1063 return 0;
1064}
1065
1066/*
1067 * When the path is realloc'd, have to fix all of the pointers in structures
1068 * already returned.
1069 */
1070static void
1071fts_padjust (FTSOBJ *sp, FTSENTRY *head)
1072{
1073 FTSENTRY *p;
1074 char *addr = sp->fts_path;
1075
1076#define ADJUST(p) do { \
1077 if ((p)->fts_accpath != (p)->fts_name) { \
1078 (p)->fts_accpath = \
1079 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1080 } \
1081 (p)->fts_path = addr; \
1082} while (0)
1083 /* Adjust the current set of children. */
1084 for (p = sp->fts_child; p; p = p->fts_link)
1085 ADJUST(p);
1086
1087 /* Adjust the rest of the tree, including the current level. */
1088 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1089 ADJUST(p);
1090 p = p->fts_link ? p->fts_link : p->fts_parent;
1091 }
1092}
1093
1094static size_t
1095fts_maxarglen (char * const *argv)
1096{
1097 size_t len, max;
1098
1099 for (max = 0; *argv; ++argv)
1100 if ((len = strlen(*argv)) > max)
1101 max = len;
1102 return (max + 1);
1103}
1104
1105/*
1106 * Change to dir specified by fd or p->fts_accpath without getting
1107 * tricked by someone changing the world out from underneath us.
1108 * Assumes p->fts_dev and p->fts_ino are filled in.
1109 */
1110static int
1111fts_safe_changedir (FTSOBJ *sp, FTSENTRY *p, int fd, const char *path)
1112{
1113 int ret, oerrno, newfd;
1114 struct stat64 sb;
1115
1116 newfd = fd;
1117 if (ISSET(FTS_NOCHDIR))
1118 return (0);
1119 if (fd < 0 && (newfd = __open(path, O_RDONLY, 0)) < 0)
1120 return (-1);
1121 if (__fstat64(newfd, &sb)) {
1122 ret = -1;
1123 goto bail;
1124 }
1125 if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {
1126 __set_errno (ENOENT); /* disinformation */
1127 ret = -1;
1128 goto bail;
1129 }
1130 ret = __fchdir(newfd);
1131bail:
1132 oerrno = errno;
1133 if (fd < 0)
1134 (void)__close(newfd);
1135 __set_errno (oerrno);
1136 return (ret);
1137}
1138