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