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