xref: /freebsd/lib/libc/gen/fts.c (revision 764a9bbee12bbdaefaf9739ed37555fef477eab4)
158f0484fSRodney W. Grimes /*-
258f0484fSRodney W. Grimes  * Copyright (c) 1990, 1993, 1994
358f0484fSRodney W. Grimes  *	The Regents of the University of California.  All rights reserved.
458f0484fSRodney W. Grimes  *
558f0484fSRodney W. Grimes  * Redistribution and use in source and binary forms, with or without
658f0484fSRodney W. Grimes  * modification, are permitted provided that the following conditions
758f0484fSRodney W. Grimes  * are met:
858f0484fSRodney W. Grimes  * 1. Redistributions of source code must retain the above copyright
958f0484fSRodney W. Grimes  *    notice, this list of conditions and the following disclaimer.
1058f0484fSRodney W. Grimes  * 2. Redistributions in binary form must reproduce the above copyright
1158f0484fSRodney W. Grimes  *    notice, this list of conditions and the following disclaimer in the
1258f0484fSRodney W. Grimes  *    documentation and/or other materials provided with the distribution.
1358f0484fSRodney W. Grimes  * 4. Neither the name of the University nor the names of its contributors
1458f0484fSRodney W. Grimes  *    may be used to endorse or promote products derived from this software
1558f0484fSRodney W. Grimes  *    without specific prior written permission.
1658f0484fSRodney W. Grimes  *
1758f0484fSRodney W. Grimes  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
1858f0484fSRodney W. Grimes  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1958f0484fSRodney W. Grimes  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2058f0484fSRodney W. Grimes  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
2158f0484fSRodney W. Grimes  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
2258f0484fSRodney W. Grimes  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
2358f0484fSRodney W. Grimes  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
2458f0484fSRodney W. Grimes  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
2558f0484fSRodney W. Grimes  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
2658f0484fSRodney W. Grimes  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
2758f0484fSRodney W. Grimes  * SUCH DAMAGE.
281a9b5f47SBrian Feldman  *
291a9b5f47SBrian Feldman  * $OpenBSD: fts.c,v 1.22 1999/10/03 19:22:22 millert Exp $
3058f0484fSRodney W. Grimes  */
3158f0484fSRodney W. Grimes 
32a1acdbf0SBruce Evans #if 0
3358f0484fSRodney W. Grimes #if defined(LIBC_SCCS) && !defined(lint)
34adf6ad9eSPeter Wemm static char sccsid[] = "@(#)fts.c	8.6 (Berkeley) 8/14/94";
3558f0484fSRodney W. Grimes #endif /* LIBC_SCCS and not lint */
36a1acdbf0SBruce Evans #endif
37a1acdbf0SBruce Evans 
38b231cb39SDavid E. O'Brien #include <sys/cdefs.h>
39b231cb39SDavid E. O'Brien __FBSDID("$FreeBSD$");
4058f0484fSRodney W. Grimes 
41d201fe46SDaniel Eischen #include "namespace.h"
4258f0484fSRodney W. Grimes #include <sys/param.h>
4399ca5b88SPeter Edwards #include <sys/mount.h>
4407dee1a7SPeter Edwards #include <sys/stat.h>
4558f0484fSRodney W. Grimes 
4658f0484fSRodney W. Grimes #include <dirent.h>
4758f0484fSRodney W. Grimes #include <errno.h>
4858f0484fSRodney W. Grimes #include <fcntl.h>
4958f0484fSRodney W. Grimes #include <fts.h>
5058f0484fSRodney W. Grimes #include <stdlib.h>
5158f0484fSRodney W. Grimes #include <string.h>
5258f0484fSRodney W. Grimes #include <unistd.h>
53d201fe46SDaniel Eischen #include "un-namespace.h"
5458f0484fSRodney W. Grimes 
550bb2aabfSGleb Kurtsou #include "gen-private.h"
560bb2aabfSGleb Kurtsou 
5748aaad5fSYaroslav Tykhiy static FTSENT	*fts_alloc(FTS *, char *, size_t);
58b231cb39SDavid E. O'Brien static FTSENT	*fts_build(FTS *, int);
59b231cb39SDavid E. O'Brien static void	 fts_lfree(FTSENT *);
60b231cb39SDavid E. O'Brien static void	 fts_load(FTS *, FTSENT *);
61b231cb39SDavid E. O'Brien static size_t	 fts_maxarglen(char * const *);
62b231cb39SDavid E. O'Brien static void	 fts_padjust(FTS *, FTSENT *);
63b231cb39SDavid E. O'Brien static int	 fts_palloc(FTS *, size_t);
6448aaad5fSYaroslav Tykhiy static FTSENT	*fts_sort(FTS *, FTSENT *, size_t);
6554cc1f88SJilles Tjoelker static int	 fts_stat(FTS *, FTSENT *, int, int);
66b231cb39SDavid E. O'Brien static int	 fts_safe_changedir(FTS *, FTSENT *, int, char *);
6707dee1a7SPeter Edwards static int	 fts_ufslinks(FTS *, const FTSENT *);
6858f0484fSRodney W. Grimes 
6951295a4dSJordan K. Hubbard #define	ISDOT(a)	(a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
7058f0484fSRodney W. Grimes 
719a91f1ccSWarner Losh #define	CLR(opt)	(sp->fts_options &= ~(opt))
729a91f1ccSWarner Losh #define	ISSET(opt)	(sp->fts_options & (opt))
739a91f1ccSWarner Losh #define	SET(opt)	(sp->fts_options |= (opt))
7458f0484fSRodney W. Grimes 
7558f0484fSRodney W. Grimes #define	FCHDIR(sp, fd)	(!ISSET(FTS_NOCHDIR) && fchdir(fd))
7658f0484fSRodney W. Grimes 
7758f0484fSRodney W. Grimes /* fts_build flags */
7858f0484fSRodney W. Grimes #define	BCHILD		1		/* fts_children */
7958f0484fSRodney W. Grimes #define	BNAMES		2		/* fts_children, names only */
8058f0484fSRodney W. Grimes #define	BREAD		3		/* fts_read */
8158f0484fSRodney W. Grimes 
8299ca5b88SPeter Edwards /*
8307dee1a7SPeter Edwards  * Internal representation of an FTS, including extra implementation
8407dee1a7SPeter Edwards  * details.  The FTS returned from fts_open points to this structure's
8507dee1a7SPeter Edwards  * ftsp_fts member (and can be cast to an _fts_private as required)
8699ca5b88SPeter Edwards  */
8799ca5b88SPeter Edwards struct _fts_private {
8899ca5b88SPeter Edwards 	FTS		ftsp_fts;
8999ca5b88SPeter Edwards 	struct statfs	ftsp_statfs;
9099ca5b88SPeter Edwards 	dev_t		ftsp_dev;
9199ca5b88SPeter Edwards 	int		ftsp_linksreliable;
9299ca5b88SPeter Edwards };
9399ca5b88SPeter Edwards 
9499ca5b88SPeter Edwards /*
9507dee1a7SPeter Edwards  * The "FTS_NOSTAT" option can avoid a lot of calls to stat(2) if it
9607dee1a7SPeter Edwards  * knows that a directory could not possibly have subdirectories.  This
9707dee1a7SPeter Edwards  * is decided by looking at the link count: a subdirectory would
9807dee1a7SPeter Edwards  * increment its parent's link count by virtue of its own ".." entry.
9907dee1a7SPeter Edwards  * This assumption only holds for UFS-like filesystems that implement
10007dee1a7SPeter Edwards  * links and directories this way, so we must punt for others.
10199ca5b88SPeter Edwards  */
10299ca5b88SPeter Edwards 
10399ca5b88SPeter Edwards static const char *ufslike_filesystems[] = {
10499ca5b88SPeter Edwards 	"ufs",
105681ff708SPawel Jakub Dawidek 	"zfs",
10699ca5b88SPeter Edwards 	"nfs",
10799ca5b88SPeter Edwards 	"nfs4",
10899ca5b88SPeter Edwards 	"ext2fs",
10999ca5b88SPeter Edwards 	0
11099ca5b88SPeter Edwards };
11199ca5b88SPeter Edwards 
11258f0484fSRodney W. Grimes FTS *
11358f0484fSRodney W. Grimes fts_open(argv, options, compar)
11458f0484fSRodney W. Grimes 	char * const *argv;
115b231cb39SDavid E. O'Brien 	int options;
1160d3bcc2eSGarrett Wollman 	int (*compar)(const FTSENT * const *, const FTSENT * const *);
11758f0484fSRodney W. Grimes {
11899ca5b88SPeter Edwards 	struct _fts_private *priv;
119b231cb39SDavid E. O'Brien 	FTS *sp;
120b231cb39SDavid E. O'Brien 	FTSENT *p, *root;
12158f0484fSRodney W. Grimes 	FTSENT *parent, *tmp;
12248aaad5fSYaroslav Tykhiy 	size_t len, nitems;
12358f0484fSRodney W. Grimes 
12458f0484fSRodney W. Grimes 	/* Options check. */
12558f0484fSRodney W. Grimes 	if (options & ~FTS_OPTIONMASK) {
12658f0484fSRodney W. Grimes 		errno = EINVAL;
12758f0484fSRodney W. Grimes 		return (NULL);
12858f0484fSRodney W. Grimes 	}
12958f0484fSRodney W. Grimes 
1308b8a820dSXin LI 	/* fts_open() requires at least one path */
1318b8a820dSXin LI 	if (*argv == NULL) {
1328b8a820dSXin LI 		errno = EINVAL;
1338b8a820dSXin LI 		return (NULL);
1348b8a820dSXin LI 	}
1358b8a820dSXin LI 
136a1acdbf0SBruce Evans 	/* Allocate/initialize the stream. */
1370dfbbb33SXin LI 	if ((priv = calloc(1, sizeof(*priv))) == NULL)
13858f0484fSRodney W. Grimes 		return (NULL);
13999ca5b88SPeter Edwards 	sp = &priv->ftsp_fts;
14058f0484fSRodney W. Grimes 	sp->fts_compar = compar;
14158f0484fSRodney W. Grimes 	sp->fts_options = options;
14258f0484fSRodney W. Grimes 
1431a9b5f47SBrian Feldman 	/* Shush, GCC. */
1441a9b5f47SBrian Feldman 	tmp = NULL;
1451a9b5f47SBrian Feldman 
14658f0484fSRodney W. Grimes 	/* Logical walks turn on NOCHDIR; symbolic links are too hard. */
14758f0484fSRodney W. Grimes 	if (ISSET(FTS_LOGICAL))
14858f0484fSRodney W. Grimes 		SET(FTS_NOCHDIR);
14958f0484fSRodney W. Grimes 
15058f0484fSRodney W. Grimes 	/*
15158f0484fSRodney W. Grimes 	 * Start out with 1K of path space, and enough, in any case,
15258f0484fSRodney W. Grimes 	 * to hold the user's paths.
15358f0484fSRodney W. Grimes 	 */
15458f0484fSRodney W. Grimes 	if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
15558f0484fSRodney W. Grimes 		goto mem1;
15658f0484fSRodney W. Grimes 
15758f0484fSRodney W. Grimes 	/* Allocate/initialize root's parent. */
15858f0484fSRodney W. Grimes 	if ((parent = fts_alloc(sp, "", 0)) == NULL)
15958f0484fSRodney W. Grimes 		goto mem2;
16058f0484fSRodney W. Grimes 	parent->fts_level = FTS_ROOTPARENTLEVEL;
16158f0484fSRodney W. Grimes 
16258f0484fSRodney W. Grimes 	/* Allocate/initialize root(s). */
1638ca72379SBrian Feldman 	for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
164c8a17392SJilles Tjoelker 		len = strlen(*argv);
16558f0484fSRodney W. Grimes 
16658f0484fSRodney W. Grimes 		p = fts_alloc(sp, *argv, len);
16758f0484fSRodney W. Grimes 		p->fts_level = FTS_ROOTLEVEL;
16858f0484fSRodney W. Grimes 		p->fts_parent = parent;
16958f0484fSRodney W. Grimes 		p->fts_accpath = p->fts_name;
17054cc1f88SJilles Tjoelker 		p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW), -1);
17158f0484fSRodney W. Grimes 
17258f0484fSRodney W. Grimes 		/* Command-line "." and ".." are real directories. */
17358f0484fSRodney W. Grimes 		if (p->fts_info == FTS_DOT)
17458f0484fSRodney W. Grimes 			p->fts_info = FTS_D;
17558f0484fSRodney W. Grimes 
17658f0484fSRodney W. Grimes 		/*
17758f0484fSRodney W. Grimes 		 * If comparison routine supplied, traverse in sorted
17858f0484fSRodney W. Grimes 		 * order; otherwise traverse in the order specified.
17958f0484fSRodney W. Grimes 		 */
18058f0484fSRodney W. Grimes 		if (compar) {
18158f0484fSRodney W. Grimes 			p->fts_link = root;
18258f0484fSRodney W. Grimes 			root = p;
18358f0484fSRodney W. Grimes 		} else {
18458f0484fSRodney W. Grimes 			p->fts_link = NULL;
18558f0484fSRodney W. Grimes 			if (root == NULL)
18658f0484fSRodney W. Grimes 				tmp = root = p;
18758f0484fSRodney W. Grimes 			else {
18858f0484fSRodney W. Grimes 				tmp->fts_link = p;
18958f0484fSRodney W. Grimes 				tmp = p;
19058f0484fSRodney W. Grimes 			}
19158f0484fSRodney W. Grimes 		}
19258f0484fSRodney W. Grimes 	}
19358f0484fSRodney W. Grimes 	if (compar && nitems > 1)
19458f0484fSRodney W. Grimes 		root = fts_sort(sp, root, nitems);
19558f0484fSRodney W. Grimes 
19658f0484fSRodney W. Grimes 	/*
19758f0484fSRodney W. Grimes 	 * Allocate a dummy pointer and make fts_read think that we've just
19858f0484fSRodney W. Grimes 	 * finished the node before the root(s); set p->fts_info to FTS_INIT
19958f0484fSRodney W. Grimes 	 * so that everything about the "current" node is ignored.
20058f0484fSRodney W. Grimes 	 */
20158f0484fSRodney W. Grimes 	if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
20258f0484fSRodney W. Grimes 		goto mem3;
20358f0484fSRodney W. Grimes 	sp->fts_cur->fts_link = root;
20458f0484fSRodney W. Grimes 	sp->fts_cur->fts_info = FTS_INIT;
20558f0484fSRodney W. Grimes 
20658f0484fSRodney W. Grimes 	/*
2071a9b5f47SBrian Feldman 	 * If using chdir(2), grab a file descriptor pointing to dot to ensure
20858f0484fSRodney W. Grimes 	 * that we can get back here; this could be avoided for some paths,
20958f0484fSRodney W. Grimes 	 * but almost certainly not worth the effort.  Slashes, symbolic links,
21058f0484fSRodney W. Grimes 	 * and ".." are all fairly nasty problems.  Note, if we can't get the
21158f0484fSRodney W. Grimes 	 * descriptor we run anyway, just more slowly.
21258f0484fSRodney W. Grimes 	 */
2136b422721SJilles Tjoelker 	if (!ISSET(FTS_NOCHDIR) &&
2146b422721SJilles Tjoelker 	    (sp->fts_rfd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0)
21558f0484fSRodney W. Grimes 		SET(FTS_NOCHDIR);
21658f0484fSRodney W. Grimes 
21758f0484fSRodney W. Grimes 	return (sp);
21858f0484fSRodney W. Grimes 
21958f0484fSRodney W. Grimes mem3:	fts_lfree(root);
22058f0484fSRodney W. Grimes 	free(parent);
22158f0484fSRodney W. Grimes mem2:	free(sp->fts_path);
22258f0484fSRodney W. Grimes mem1:	free(sp);
22358f0484fSRodney W. Grimes 	return (NULL);
22458f0484fSRodney W. Grimes }
22558f0484fSRodney W. Grimes 
22658f0484fSRodney W. Grimes static void
2273a12c046SXin LI fts_load(FTS *sp, FTSENT *p)
22858f0484fSRodney W. Grimes {
22948aaad5fSYaroslav Tykhiy 	size_t len;
230b231cb39SDavid E. O'Brien 	char *cp;
23158f0484fSRodney W. Grimes 
23258f0484fSRodney W. Grimes 	/*
23358f0484fSRodney W. Grimes 	 * Load the stream structure for the next traversal.  Since we don't
23458f0484fSRodney W. Grimes 	 * actually enter the directory until after the preorder visit, set
23558f0484fSRodney W. Grimes 	 * the fts_accpath field specially so the chdir gets done to the right
23658f0484fSRodney W. Grimes 	 * place and the user can access the first node.  From fts_open it's
23758f0484fSRodney W. Grimes 	 * known that the path will fit.
23858f0484fSRodney W. Grimes 	 */
23958f0484fSRodney W. Grimes 	len = p->fts_pathlen = p->fts_namelen;
24058f0484fSRodney W. Grimes 	memmove(sp->fts_path, p->fts_name, len + 1);
24158f0484fSRodney W. Grimes 	if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
24258f0484fSRodney W. Grimes 		len = strlen(++cp);
24358f0484fSRodney W. Grimes 		memmove(p->fts_name, cp, len + 1);
24458f0484fSRodney W. Grimes 		p->fts_namelen = len;
24558f0484fSRodney W. Grimes 	}
24658f0484fSRodney W. Grimes 	p->fts_accpath = p->fts_path = sp->fts_path;
24758f0484fSRodney W. Grimes 	sp->fts_dev = p->fts_dev;
24858f0484fSRodney W. Grimes }
24958f0484fSRodney W. Grimes 
25058f0484fSRodney W. Grimes int
2513a12c046SXin LI fts_close(FTS *sp)
25258f0484fSRodney W. Grimes {
253b231cb39SDavid E. O'Brien 	FTSENT *freep, *p;
25458f0484fSRodney W. Grimes 	int saved_errno;
25558f0484fSRodney W. Grimes 
25658f0484fSRodney W. Grimes 	/*
25758f0484fSRodney W. Grimes 	 * This still works if we haven't read anything -- the dummy structure
25858f0484fSRodney W. Grimes 	 * points to the root list, so we step through to the end of the root
25958f0484fSRodney W. Grimes 	 * list which has a valid parent pointer.
26058f0484fSRodney W. Grimes 	 */
26158f0484fSRodney W. Grimes 	if (sp->fts_cur) {
26258f0484fSRodney W. Grimes 		for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
26358f0484fSRodney W. Grimes 			freep = p;
2648ca72379SBrian Feldman 			p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
26558f0484fSRodney W. Grimes 			free(freep);
26658f0484fSRodney W. Grimes 		}
26758f0484fSRodney W. Grimes 		free(p);
26858f0484fSRodney W. Grimes 	}
26958f0484fSRodney W. Grimes 
27058f0484fSRodney W. Grimes 	/* Free up child linked list, sort array, path buffer. */
27158f0484fSRodney W. Grimes 	if (sp->fts_child)
27258f0484fSRodney W. Grimes 		fts_lfree(sp->fts_child);
27358f0484fSRodney W. Grimes 	if (sp->fts_array)
27458f0484fSRodney W. Grimes 		free(sp->fts_array);
27558f0484fSRodney W. Grimes 	free(sp->fts_path);
27658f0484fSRodney W. Grimes 
27758f0484fSRodney W. Grimes 	/* Return to original directory, save errno if necessary. */
27858f0484fSRodney W. Grimes 	if (!ISSET(FTS_NOCHDIR)) {
27958f0484fSRodney W. Grimes 		saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
2809233c4d9SJason Evans 		(void)_close(sp->fts_rfd);
28158f0484fSRodney W. Grimes 
28258f0484fSRodney W. Grimes 		/* Set errno and return. */
2831a9b5f47SBrian Feldman 		if (saved_errno != 0) {
2848a507b98SPoul-Henning Kamp 			/* Free up the stream pointer. */
2858a507b98SPoul-Henning Kamp 			free(sp);
28658f0484fSRodney W. Grimes 			errno = saved_errno;
28758f0484fSRodney W. Grimes 			return (-1);
28858f0484fSRodney W. Grimes 		}
2891a9b5f47SBrian Feldman 	}
2901a9b5f47SBrian Feldman 
2918a507b98SPoul-Henning Kamp 	/* Free up the stream pointer. */
2928a507b98SPoul-Henning Kamp 	free(sp);
29358f0484fSRodney W. Grimes 	return (0);
29458f0484fSRodney W. Grimes }
29558f0484fSRodney W. Grimes 
29658f0484fSRodney W. Grimes /*
2979a91f1ccSWarner Losh  * Special case of "/" at the end of the path so that slashes aren't
2989a91f1ccSWarner Losh  * appended which would cause paths to be written as "....//foo".
29958f0484fSRodney W. Grimes  */
30058f0484fSRodney W. Grimes #define	NAPPEND(p)							\
3019a91f1ccSWarner Losh 	(p->fts_path[p->fts_pathlen - 1] == '/'				\
3029a91f1ccSWarner Losh 	    ? p->fts_pathlen - 1 : p->fts_pathlen)
30358f0484fSRodney W. Grimes 
30458f0484fSRodney W. Grimes FTSENT *
3053a12c046SXin LI fts_read(FTS *sp)
30658f0484fSRodney W. Grimes {
307b231cb39SDavid E. O'Brien 	FTSENT *p, *tmp;
308b231cb39SDavid E. O'Brien 	int instr;
309b231cb39SDavid E. O'Brien 	char *t;
31058f0484fSRodney W. Grimes 	int saved_errno;
31158f0484fSRodney W. Grimes 
31258f0484fSRodney W. Grimes 	/* If finished or unrecoverable error, return NULL. */
31358f0484fSRodney W. Grimes 	if (sp->fts_cur == NULL || ISSET(FTS_STOP))
31458f0484fSRodney W. Grimes 		return (NULL);
31558f0484fSRodney W. Grimes 
31658f0484fSRodney W. Grimes 	/* Set current node pointer. */
31758f0484fSRodney W. Grimes 	p = sp->fts_cur;
31858f0484fSRodney W. Grimes 
31958f0484fSRodney W. Grimes 	/* Save and zero out user instructions. */
32058f0484fSRodney W. Grimes 	instr = p->fts_instr;
32158f0484fSRodney W. Grimes 	p->fts_instr = FTS_NOINSTR;
32258f0484fSRodney W. Grimes 
32358f0484fSRodney W. Grimes 	/* Any type of file may be re-visited; re-stat and re-turn. */
32458f0484fSRodney W. Grimes 	if (instr == FTS_AGAIN) {
32554cc1f88SJilles Tjoelker 		p->fts_info = fts_stat(sp, p, 0, -1);
32658f0484fSRodney W. Grimes 		return (p);
32758f0484fSRodney W. Grimes 	}
32858f0484fSRodney W. Grimes 
32958f0484fSRodney W. Grimes 	/*
33058f0484fSRodney W. Grimes 	 * Following a symlink -- SLNONE test allows application to see
33158f0484fSRodney W. Grimes 	 * SLNONE and recover.  If indirecting through a symlink, have
33258f0484fSRodney W. Grimes 	 * keep a pointer to current location.  If unable to get that
33358f0484fSRodney W. Grimes 	 * pointer, follow fails.
33458f0484fSRodney W. Grimes 	 */
33558f0484fSRodney W. Grimes 	if (instr == FTS_FOLLOW &&
33658f0484fSRodney W. Grimes 	    (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
33754cc1f88SJilles Tjoelker 		p->fts_info = fts_stat(sp, p, 1, -1);
3381a9b5f47SBrian Feldman 		if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
3396b422721SJilles Tjoelker 			if ((p->fts_symfd = _open(".", O_RDONLY | O_CLOEXEC,
3406b422721SJilles Tjoelker 			    0)) < 0) {
34158f0484fSRodney W. Grimes 				p->fts_errno = errno;
34258f0484fSRodney W. Grimes 				p->fts_info = FTS_ERR;
34358f0484fSRodney W. Grimes 			} else
34458f0484fSRodney W. Grimes 				p->fts_flags |= FTS_SYMFOLLOW;
3451a9b5f47SBrian Feldman 		}
34658f0484fSRodney W. Grimes 		return (p);
34758f0484fSRodney W. Grimes 	}
34858f0484fSRodney W. Grimes 
34958f0484fSRodney W. Grimes 	/* Directory in pre-order. */
35058f0484fSRodney W. Grimes 	if (p->fts_info == FTS_D) {
35158f0484fSRodney W. Grimes 		/* If skipped or crossed mount point, do post-order visit. */
35258f0484fSRodney W. Grimes 		if (instr == FTS_SKIP ||
35351295a4dSJordan K. Hubbard 		    (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
35458f0484fSRodney W. Grimes 			if (p->fts_flags & FTS_SYMFOLLOW)
3559233c4d9SJason Evans 				(void)_close(p->fts_symfd);
35658f0484fSRodney W. Grimes 			if (sp->fts_child) {
35758f0484fSRodney W. Grimes 				fts_lfree(sp->fts_child);
35858f0484fSRodney W. Grimes 				sp->fts_child = NULL;
35958f0484fSRodney W. Grimes 			}
36058f0484fSRodney W. Grimes 			p->fts_info = FTS_DP;
36158f0484fSRodney W. Grimes 			return (p);
36258f0484fSRodney W. Grimes 		}
36358f0484fSRodney W. Grimes 
36458f0484fSRodney W. Grimes 		/* Rebuild if only read the names and now traversing. */
3658ca72379SBrian Feldman 		if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
3669a91f1ccSWarner Losh 			CLR(FTS_NAMEONLY);
36758f0484fSRodney W. Grimes 			fts_lfree(sp->fts_child);
36858f0484fSRodney W. Grimes 			sp->fts_child = NULL;
36958f0484fSRodney W. Grimes 		}
37058f0484fSRodney W. Grimes 
37158f0484fSRodney W. Grimes 		/*
37258f0484fSRodney W. Grimes 		 * Cd to the subdirectory.
37358f0484fSRodney W. Grimes 		 *
37458f0484fSRodney W. Grimes 		 * If have already read and now fail to chdir, whack the list
37558f0484fSRodney W. Grimes 		 * to make the names come out right, and set the parent errno
37658f0484fSRodney W. Grimes 		 * so the application will eventually get an error condition.
37758f0484fSRodney W. Grimes 		 * Set the FTS_DONTCHDIR flag so that when we logically change
37858f0484fSRodney W. Grimes 		 * directories back to the parent we don't do a chdir.
37958f0484fSRodney W. Grimes 		 *
38058f0484fSRodney W. Grimes 		 * If haven't read do so.  If the read fails, fts_build sets
38158f0484fSRodney W. Grimes 		 * FTS_STOP or the fts_info field of the node.
38258f0484fSRodney W. Grimes 		 */
3838ca72379SBrian Feldman 		if (sp->fts_child != NULL) {
38493a85518SKris Kennaway 			if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
38558f0484fSRodney W. Grimes 				p->fts_errno = errno;
38658f0484fSRodney W. Grimes 				p->fts_flags |= FTS_DONTCHDIR;
3878ca72379SBrian Feldman 				for (p = sp->fts_child; p != NULL;
3888ca72379SBrian Feldman 				    p = p->fts_link)
38958f0484fSRodney W. Grimes 					p->fts_accpath =
39058f0484fSRodney W. Grimes 					    p->fts_parent->fts_accpath;
39158f0484fSRodney W. Grimes 			}
39258f0484fSRodney W. Grimes 		} else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
39358f0484fSRodney W. Grimes 			if (ISSET(FTS_STOP))
39458f0484fSRodney W. Grimes 				return (NULL);
39558f0484fSRodney W. Grimes 			return (p);
39658f0484fSRodney W. Grimes 		}
39758f0484fSRodney W. Grimes 		p = sp->fts_child;
39858f0484fSRodney W. Grimes 		sp->fts_child = NULL;
39958f0484fSRodney W. Grimes 		goto name;
40058f0484fSRodney W. Grimes 	}
40158f0484fSRodney W. Grimes 
40258f0484fSRodney W. Grimes 	/* Move to the next node on this level. */
40358f0484fSRodney W. Grimes next:	tmp = p;
4048ca72379SBrian Feldman 	if ((p = p->fts_link) != NULL) {
40558f0484fSRodney W. Grimes 		/*
4061a9b5f47SBrian Feldman 		 * If reached the top, return to the original directory (or
4071a9b5f47SBrian Feldman 		 * the root of the tree), and load the paths for the next root.
40858f0484fSRodney W. Grimes 		 */
40958f0484fSRodney W. Grimes 		if (p->fts_level == FTS_ROOTLEVEL) {
4109a91f1ccSWarner Losh 			if (FCHDIR(sp, sp->fts_rfd)) {
41158f0484fSRodney W. Grimes 				SET(FTS_STOP);
41258f0484fSRodney W. Grimes 				return (NULL);
41358f0484fSRodney W. Grimes 			}
4145de8a0fdSJilles Tjoelker 			free(tmp);
41558f0484fSRodney W. Grimes 			fts_load(sp, p);
41658f0484fSRodney W. Grimes 			return (sp->fts_cur = p);
41758f0484fSRodney W. Grimes 		}
41858f0484fSRodney W. Grimes 
41958f0484fSRodney W. Grimes 		/*
42058f0484fSRodney W. Grimes 		 * User may have called fts_set on the node.  If skipped,
42158f0484fSRodney W. Grimes 		 * ignore.  If followed, get a file descriptor so we can
42258f0484fSRodney W. Grimes 		 * get back if necessary.
42358f0484fSRodney W. Grimes 		 */
4245de8a0fdSJilles Tjoelker 		if (p->fts_instr == FTS_SKIP) {
4255de8a0fdSJilles Tjoelker 			free(tmp);
42658f0484fSRodney W. Grimes 			goto next;
4275de8a0fdSJilles Tjoelker 		}
42858f0484fSRodney W. Grimes 		if (p->fts_instr == FTS_FOLLOW) {
42954cc1f88SJilles Tjoelker 			p->fts_info = fts_stat(sp, p, 1, -1);
4301a9b5f47SBrian Feldman 			if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
43158f0484fSRodney W. Grimes 				if ((p->fts_symfd =
4326b422721SJilles Tjoelker 				    _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) {
43358f0484fSRodney W. Grimes 					p->fts_errno = errno;
43458f0484fSRodney W. Grimes 					p->fts_info = FTS_ERR;
43558f0484fSRodney W. Grimes 				} else
43658f0484fSRodney W. Grimes 					p->fts_flags |= FTS_SYMFOLLOW;
4371a9b5f47SBrian Feldman 			}
43858f0484fSRodney W. Grimes 			p->fts_instr = FTS_NOINSTR;
43958f0484fSRodney W. Grimes 		}
44058f0484fSRodney W. Grimes 
4415de8a0fdSJilles Tjoelker 		free(tmp);
4425de8a0fdSJilles Tjoelker 
44358f0484fSRodney W. Grimes name:		t = sp->fts_path + NAPPEND(p->fts_parent);
44458f0484fSRodney W. Grimes 		*t++ = '/';
44558f0484fSRodney W. Grimes 		memmove(t, p->fts_name, p->fts_namelen + 1);
44658f0484fSRodney W. Grimes 		return (sp->fts_cur = p);
44758f0484fSRodney W. Grimes 	}
44858f0484fSRodney W. Grimes 
44958f0484fSRodney W. Grimes 	/* Move up to the parent node. */
45058f0484fSRodney W. Grimes 	p = tmp->fts_parent;
45158f0484fSRodney W. Grimes 
45258f0484fSRodney W. Grimes 	if (p->fts_level == FTS_ROOTPARENTLEVEL) {
45358f0484fSRodney W. Grimes 		/*
45458f0484fSRodney W. Grimes 		 * Done; free everything up and set errno to 0 so the user
45558f0484fSRodney W. Grimes 		 * can distinguish between error and EOF.
45658f0484fSRodney W. Grimes 		 */
4575de8a0fdSJilles Tjoelker 		free(tmp);
45858f0484fSRodney W. Grimes 		free(p);
45958f0484fSRodney W. Grimes 		errno = 0;
46058f0484fSRodney W. Grimes 		return (sp->fts_cur = NULL);
46158f0484fSRodney W. Grimes 	}
46258f0484fSRodney W. Grimes 
4631a9b5f47SBrian Feldman 	/* NUL terminate the pathname. */
46458f0484fSRodney W. Grimes 	sp->fts_path[p->fts_pathlen] = '\0';
46558f0484fSRodney W. Grimes 
46658f0484fSRodney W. Grimes 	/*
46758f0484fSRodney W. Grimes 	 * Return to the parent directory.  If at a root node or came through
46858f0484fSRodney W. Grimes 	 * a symlink, go back through the file descriptor.  Otherwise, cd up
46958f0484fSRodney W. Grimes 	 * one directory.
47058f0484fSRodney W. Grimes 	 */
47158f0484fSRodney W. Grimes 	if (p->fts_level == FTS_ROOTLEVEL) {
4729a91f1ccSWarner Losh 		if (FCHDIR(sp, sp->fts_rfd)) {
47358f0484fSRodney W. Grimes 			SET(FTS_STOP);
47458f0484fSRodney W. Grimes 			return (NULL);
47558f0484fSRodney W. Grimes 		}
47658f0484fSRodney W. Grimes 	} else if (p->fts_flags & FTS_SYMFOLLOW) {
47758f0484fSRodney W. Grimes 		if (FCHDIR(sp, p->fts_symfd)) {
47858f0484fSRodney W. Grimes 			saved_errno = errno;
4799233c4d9SJason Evans 			(void)_close(p->fts_symfd);
48058f0484fSRodney W. Grimes 			errno = saved_errno;
48158f0484fSRodney W. Grimes 			SET(FTS_STOP);
48258f0484fSRodney W. Grimes 			return (NULL);
48358f0484fSRodney W. Grimes 		}
4849233c4d9SJason Evans 		(void)_close(p->fts_symfd);
485fdeb0156SKris Kennaway 	} else if (!(p->fts_flags & FTS_DONTCHDIR) &&
48693a85518SKris Kennaway 	    fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
48758f0484fSRodney W. Grimes 		SET(FTS_STOP);
48858f0484fSRodney W. Grimes 		return (NULL);
48958f0484fSRodney W. Grimes 	}
4905de8a0fdSJilles Tjoelker 	free(tmp);
49158f0484fSRodney W. Grimes 	p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
49258f0484fSRodney W. Grimes 	return (sp->fts_cur = p);
49358f0484fSRodney W. Grimes }
49458f0484fSRodney W. Grimes 
49558f0484fSRodney W. Grimes /*
49658f0484fSRodney W. Grimes  * Fts_set takes the stream as an argument although it's not used in this
49758f0484fSRodney W. Grimes  * implementation; it would be necessary if anyone wanted to add global
49858f0484fSRodney W. Grimes  * semantics to fts using fts_set.  An error return is allowed for similar
49958f0484fSRodney W. Grimes  * reasons.
50058f0484fSRodney W. Grimes  */
50158f0484fSRodney W. Grimes /* ARGSUSED */
50258f0484fSRodney W. Grimes int
5033a12c046SXin LI fts_set(FTS *sp, FTSENT *p, int instr)
50458f0484fSRodney W. Grimes {
5058ca72379SBrian Feldman 	if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
50658f0484fSRodney W. Grimes 	    instr != FTS_NOINSTR && instr != FTS_SKIP) {
50758f0484fSRodney W. Grimes 		errno = EINVAL;
50858f0484fSRodney W. Grimes 		return (1);
50958f0484fSRodney W. Grimes 	}
51058f0484fSRodney W. Grimes 	p->fts_instr = instr;
51158f0484fSRodney W. Grimes 	return (0);
51258f0484fSRodney W. Grimes }
51358f0484fSRodney W. Grimes 
51458f0484fSRodney W. Grimes FTSENT *
5153a12c046SXin LI fts_children(FTS *sp, int instr)
51658f0484fSRodney W. Grimes {
517b231cb39SDavid E. O'Brien 	FTSENT *p;
518*764a9bbeSJilles Tjoelker 	int fd, rc, serrno;
51958f0484fSRodney W. Grimes 
5208ca72379SBrian Feldman 	if (instr != 0 && instr != FTS_NAMEONLY) {
52158f0484fSRodney W. Grimes 		errno = EINVAL;
52258f0484fSRodney W. Grimes 		return (NULL);
52358f0484fSRodney W. Grimes 	}
52458f0484fSRodney W. Grimes 
52558f0484fSRodney W. Grimes 	/* Set current node pointer. */
52658f0484fSRodney W. Grimes 	p = sp->fts_cur;
52758f0484fSRodney W. Grimes 
52858f0484fSRodney W. Grimes 	/*
52958f0484fSRodney W. Grimes 	 * Errno set to 0 so user can distinguish empty directory from
53058f0484fSRodney W. Grimes 	 * an error.
53158f0484fSRodney W. Grimes 	 */
53258f0484fSRodney W. Grimes 	errno = 0;
53358f0484fSRodney W. Grimes 
53458f0484fSRodney W. Grimes 	/* Fatal errors stop here. */
53558f0484fSRodney W. Grimes 	if (ISSET(FTS_STOP))
53658f0484fSRodney W. Grimes 		return (NULL);
53758f0484fSRodney W. Grimes 
53858f0484fSRodney W. Grimes 	/* Return logical hierarchy of user's arguments. */
53958f0484fSRodney W. Grimes 	if (p->fts_info == FTS_INIT)
54058f0484fSRodney W. Grimes 		return (p->fts_link);
54158f0484fSRodney W. Grimes 
54258f0484fSRodney W. Grimes 	/*
54358f0484fSRodney W. Grimes 	 * If not a directory being visited in pre-order, stop here.  Could
54458f0484fSRodney W. Grimes 	 * allow FTS_DNR, assuming the user has fixed the problem, but the
54558f0484fSRodney W. Grimes 	 * same effect is available with FTS_AGAIN.
54658f0484fSRodney W. Grimes 	 */
54758f0484fSRodney W. Grimes 	if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
54858f0484fSRodney W. Grimes 		return (NULL);
54958f0484fSRodney W. Grimes 
55058f0484fSRodney W. Grimes 	/* Free up any previous child list. */
5518ca72379SBrian Feldman 	if (sp->fts_child != NULL)
55258f0484fSRodney W. Grimes 		fts_lfree(sp->fts_child);
55358f0484fSRodney W. Grimes 
55458f0484fSRodney W. Grimes 	if (instr == FTS_NAMEONLY) {
5559a91f1ccSWarner Losh 		SET(FTS_NAMEONLY);
55658f0484fSRodney W. Grimes 		instr = BNAMES;
55758f0484fSRodney W. Grimes 	} else
55858f0484fSRodney W. Grimes 		instr = BCHILD;
55958f0484fSRodney W. Grimes 
56058f0484fSRodney W. Grimes 	/*
56158f0484fSRodney W. Grimes 	 * If using chdir on a relative path and called BEFORE fts_read does
56258f0484fSRodney W. Grimes 	 * its chdir to the root of a traversal, we can lose -- we need to
56358f0484fSRodney W. Grimes 	 * chdir into the subdirectory, and we don't know where the current
56458f0484fSRodney W. Grimes 	 * directory is, so we can't get back so that the upcoming chdir by
56558f0484fSRodney W. Grimes 	 * fts_read will work.
56658f0484fSRodney W. Grimes 	 */
56758f0484fSRodney W. Grimes 	if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
56858f0484fSRodney W. Grimes 	    ISSET(FTS_NOCHDIR))
56958f0484fSRodney W. Grimes 		return (sp->fts_child = fts_build(sp, instr));
57058f0484fSRodney W. Grimes 
5716b422721SJilles Tjoelker 	if ((fd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0)
57258f0484fSRodney W. Grimes 		return (NULL);
57358f0484fSRodney W. Grimes 	sp->fts_child = fts_build(sp, instr);
574*764a9bbeSJilles Tjoelker 	serrno = (sp->fts_child == NULL) ? errno : 0;
575*764a9bbeSJilles Tjoelker 	rc = fchdir(fd);
576*764a9bbeSJilles Tjoelker 	if (rc < 0 && serrno == 0)
577*764a9bbeSJilles Tjoelker 		serrno = errno;
578ce5c3df1SDavid Schultz 	(void)_close(fd);
579*764a9bbeSJilles Tjoelker 	errno = serrno;
580*764a9bbeSJilles Tjoelker 	if (rc < 0)
58158f0484fSRodney W. Grimes 		return (NULL);
58258f0484fSRodney W. Grimes 	return (sp->fts_child);
58358f0484fSRodney W. Grimes }
58458f0484fSRodney W. Grimes 
5850d3bcc2eSGarrett Wollman #ifndef fts_get_clientptr
5860d3bcc2eSGarrett Wollman #error "fts_get_clientptr not defined"
5870d3bcc2eSGarrett Wollman #endif
5880d3bcc2eSGarrett Wollman 
5890d3bcc2eSGarrett Wollman void *
5900d3bcc2eSGarrett Wollman (fts_get_clientptr)(FTS *sp)
5910d3bcc2eSGarrett Wollman {
5920d3bcc2eSGarrett Wollman 
5930d3bcc2eSGarrett Wollman 	return (fts_get_clientptr(sp));
5940d3bcc2eSGarrett Wollman }
5950d3bcc2eSGarrett Wollman 
5960d3bcc2eSGarrett Wollman #ifndef fts_get_stream
5970d3bcc2eSGarrett Wollman #error "fts_get_stream not defined"
5980d3bcc2eSGarrett Wollman #endif
5990d3bcc2eSGarrett Wollman 
6000d3bcc2eSGarrett Wollman FTS *
6010d3bcc2eSGarrett Wollman (fts_get_stream)(FTSENT *p)
6020d3bcc2eSGarrett Wollman {
6030d3bcc2eSGarrett Wollman 	return (fts_get_stream(p));
6040d3bcc2eSGarrett Wollman }
6050d3bcc2eSGarrett Wollman 
6060d3bcc2eSGarrett Wollman void
6070d3bcc2eSGarrett Wollman fts_set_clientptr(FTS *sp, void *clientptr)
6080d3bcc2eSGarrett Wollman {
6090d3bcc2eSGarrett Wollman 
6100d3bcc2eSGarrett Wollman 	sp->fts_clientptr = clientptr;
6110d3bcc2eSGarrett Wollman }
6120d3bcc2eSGarrett Wollman 
61358f0484fSRodney W. Grimes /*
61458f0484fSRodney W. Grimes  * This is the tricky part -- do not casually change *anything* in here.  The
61558f0484fSRodney W. Grimes  * idea is to build the linked list of entries that are used by fts_children
61658f0484fSRodney W. Grimes  * and fts_read.  There are lots of special cases.
61758f0484fSRodney W. Grimes  *
61858f0484fSRodney W. Grimes  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
61958f0484fSRodney W. Grimes  * set and it's a physical walk (so that symbolic links can't be directories),
62058f0484fSRodney W. Grimes  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
62158f0484fSRodney W. Grimes  * of the file is in the directory entry.  Otherwise, we assume that the number
62258f0484fSRodney W. Grimes  * of subdirectories in a node is equal to the number of links to the parent.
62358f0484fSRodney W. Grimes  * The former skips all stat calls.  The latter skips stat calls in any leaf
62458f0484fSRodney W. Grimes  * directories and for any files after the subdirectories in the directory have
62558f0484fSRodney W. Grimes  * been found, cutting the stat calls by about 2/3.
62658f0484fSRodney W. Grimes  */
62758f0484fSRodney W. Grimes static FTSENT *
6283a12c046SXin LI fts_build(FTS *sp, int type)
62958f0484fSRodney W. Grimes {
630b231cb39SDavid E. O'Brien 	struct dirent *dp;
631b231cb39SDavid E. O'Brien 	FTSENT *p, *head;
63258f0484fSRodney W. Grimes 	FTSENT *cur, *tail;
63358f0484fSRodney W. Grimes 	DIR *dirp;
6341a9b5f47SBrian Feldman 	void *oldaddr;
63558f0484fSRodney W. Grimes 	char *cp;
63648aaad5fSYaroslav Tykhiy 	int cderrno, descend, oflag, saved_errno, nostat, doadjust;
63748aaad5fSYaroslav Tykhiy 	long level;
63848aaad5fSYaroslav Tykhiy 	long nlinks;	/* has to be signed because -1 is a magic value */
63948aaad5fSYaroslav Tykhiy 	size_t dnamlen, len, maxlen, nitems;
64058f0484fSRodney W. Grimes 
64158f0484fSRodney W. Grimes 	/* Set current node pointer. */
64258f0484fSRodney W. Grimes 	cur = sp->fts_cur;
64358f0484fSRodney W. Grimes 
64458f0484fSRodney W. Grimes 	/*
64558f0484fSRodney W. Grimes 	 * Open the directory for reading.  If this fails, we're done.
64658f0484fSRodney W. Grimes 	 * If being called from fts_read, set the fts_info field.
64758f0484fSRodney W. Grimes 	 */
648adf6ad9eSPeter Wemm #ifdef FTS_WHITEOUT
649adf6ad9eSPeter Wemm 	if (ISSET(FTS_WHITEOUT))
650adf6ad9eSPeter Wemm 		oflag = DTF_NODUP | DTF_REWIND;
651adf6ad9eSPeter Wemm 	else
652adf6ad9eSPeter Wemm 		oflag = DTF_HIDEW | DTF_NODUP | DTF_REWIND;
653adf6ad9eSPeter Wemm #else
654adf6ad9eSPeter Wemm #define __opendir2(path, flag) opendir(path)
655adf6ad9eSPeter Wemm #endif
656adf6ad9eSPeter Wemm 	if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
65758f0484fSRodney W. Grimes 		if (type == BREAD) {
65858f0484fSRodney W. Grimes 			cur->fts_info = FTS_DNR;
65958f0484fSRodney W. Grimes 			cur->fts_errno = errno;
66058f0484fSRodney W. Grimes 		}
66158f0484fSRodney W. Grimes 		return (NULL);
66258f0484fSRodney W. Grimes 	}
66358f0484fSRodney W. Grimes 
66458f0484fSRodney W. Grimes 	/*
66558f0484fSRodney W. Grimes 	 * Nlinks is the number of possible entries of type directory in the
66658f0484fSRodney W. Grimes 	 * directory if we're cheating on stat calls, 0 if we're not doing
66758f0484fSRodney W. Grimes 	 * any stat calls at all, -1 if we're doing stats on everything.
66858f0484fSRodney W. Grimes 	 */
6691a9b5f47SBrian Feldman 	if (type == BNAMES) {
67058f0484fSRodney W. Grimes 		nlinks = 0;
6711a9b5f47SBrian Feldman 		/* Be quiet about nostat, GCC. */
6721a9b5f47SBrian Feldman 		nostat = 0;
6731a9b5f47SBrian Feldman 	} else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
67499ca5b88SPeter Edwards 		if (fts_ufslinks(sp, cur))
67558f0484fSRodney W. Grimes 			nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
67699ca5b88SPeter Edwards 		else
67799ca5b88SPeter Edwards 			nlinks = -1;
6781a9b5f47SBrian Feldman 		nostat = 1;
6791a9b5f47SBrian Feldman 	} else {
68058f0484fSRodney W. Grimes 		nlinks = -1;
6811a9b5f47SBrian Feldman 		nostat = 0;
6821a9b5f47SBrian Feldman 	}
68358f0484fSRodney W. Grimes 
68458f0484fSRodney W. Grimes #ifdef notdef
68558f0484fSRodney W. Grimes 	(void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
68658f0484fSRodney W. Grimes 	(void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
68758f0484fSRodney W. Grimes 	    ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
68858f0484fSRodney W. Grimes #endif
68958f0484fSRodney W. Grimes 	/*
69058f0484fSRodney W. Grimes 	 * If we're going to need to stat anything or we want to descend
69158f0484fSRodney W. Grimes 	 * and stay in the directory, chdir.  If this fails we keep going,
69258f0484fSRodney W. Grimes 	 * but set a flag so we don't chdir after the post-order visit.
69358f0484fSRodney W. Grimes 	 * We won't be able to stat anything, but we can still return the
69458f0484fSRodney W. Grimes 	 * names themselves.  Note, that since fts_read won't be able to
69558f0484fSRodney W. Grimes 	 * chdir into the directory, it will have to return different path
69658f0484fSRodney W. Grimes 	 * names than before, i.e. "a/b" instead of "b".  Since the node
69758f0484fSRodney W. Grimes 	 * has already been visited in pre-order, have to wait until the
69858f0484fSRodney W. Grimes 	 * post-order visit to return the error.  There is a special case
69958f0484fSRodney W. Grimes 	 * here, if there was nothing to stat then it's not an error to
70058f0484fSRodney W. Grimes 	 * not be able to stat.  This is all fairly nasty.  If a program
70158f0484fSRodney W. Grimes 	 * needed sorted entries or stat information, they had better be
70258f0484fSRodney W. Grimes 	 * checking FTS_NS on the returned nodes.
70358f0484fSRodney W. Grimes 	 */
70458f0484fSRodney W. Grimes 	cderrno = 0;
7051a9b5f47SBrian Feldman 	if (nlinks || type == BREAD) {
7060bb2aabfSGleb Kurtsou 		if (fts_safe_changedir(sp, cur, _dirfd(dirp), NULL)) {
70758f0484fSRodney W. Grimes 			if (nlinks && type == BREAD)
70858f0484fSRodney W. Grimes 				cur->fts_errno = errno;
70958f0484fSRodney W. Grimes 			cur->fts_flags |= FTS_DONTCHDIR;
71058f0484fSRodney W. Grimes 			descend = 0;
71158f0484fSRodney W. Grimes 			cderrno = errno;
71258f0484fSRodney W. Grimes 		} else
71358f0484fSRodney W. Grimes 			descend = 1;
7141a9b5f47SBrian Feldman 	} else
71558f0484fSRodney W. Grimes 		descend = 0;
71658f0484fSRodney W. Grimes 
71758f0484fSRodney W. Grimes 	/*
71858f0484fSRodney W. Grimes 	 * Figure out the max file name length that can be stored in the
71958f0484fSRodney W. Grimes 	 * current path -- the inner loop allocates more path as necessary.
72058f0484fSRodney W. Grimes 	 * We really wouldn't have to do the maxlen calculations here, we
72158f0484fSRodney W. Grimes 	 * could do them in fts_read before returning the path, but it's a
72258f0484fSRodney W. Grimes 	 * lot easier here since the length is part of the dirent structure.
72358f0484fSRodney W. Grimes 	 *
72458f0484fSRodney W. Grimes 	 * If not changing directories set a pointer so that can just append
72558f0484fSRodney W. Grimes 	 * each new name into the path.
72658f0484fSRodney W. Grimes 	 */
72758f0484fSRodney W. Grimes 	len = NAPPEND(cur);
72858f0484fSRodney W. Grimes 	if (ISSET(FTS_NOCHDIR)) {
72958f0484fSRodney W. Grimes 		cp = sp->fts_path + len;
73058f0484fSRodney W. Grimes 		*cp++ = '/';
7311a9b5f47SBrian Feldman 	} else {
7321a9b5f47SBrian Feldman 		/* GCC, you're too verbose. */
7331a9b5f47SBrian Feldman 		cp = NULL;
73458f0484fSRodney W. Grimes 	}
7351a9b5f47SBrian Feldman 	len++;
7361a9b5f47SBrian Feldman 	maxlen = sp->fts_pathlen - len;
73758f0484fSRodney W. Grimes 
73858f0484fSRodney W. Grimes 	level = cur->fts_level + 1;
73958f0484fSRodney W. Grimes 
74058f0484fSRodney W. Grimes 	/* Read the directory, attaching each entry to the `link' pointer. */
7411a9b5f47SBrian Feldman 	doadjust = 0;
7429a91f1ccSWarner Losh 	for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
743542fc104STim Kientzle 		dnamlen = dp->d_namlen;
74458f0484fSRodney W. Grimes 		if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
74558f0484fSRodney W. Grimes 			continue;
74658f0484fSRodney W. Grimes 
74748aaad5fSYaroslav Tykhiy 		if ((p = fts_alloc(sp, dp->d_name, dnamlen)) == NULL)
74858f0484fSRodney W. Grimes 			goto mem1;
749542fc104STim Kientzle 		if (dnamlen >= maxlen) {	/* include space for NUL */
7501a9b5f47SBrian Feldman 			oldaddr = sp->fts_path;
751542fc104STim Kientzle 			if (fts_palloc(sp, dnamlen + len + 1)) {
75258f0484fSRodney W. Grimes 				/*
75358f0484fSRodney W. Grimes 				 * No more memory for path or structures.  Save
75458f0484fSRodney W. Grimes 				 * errno, free up the current structure and the
75558f0484fSRodney W. Grimes 				 * structures already allocated.
75658f0484fSRodney W. Grimes 				 */
75758f0484fSRodney W. Grimes mem1:				saved_errno = errno;
75858f0484fSRodney W. Grimes 				if (p)
75958f0484fSRodney W. Grimes 					free(p);
76058f0484fSRodney W. Grimes 				fts_lfree(head);
76158f0484fSRodney W. Grimes 				(void)closedir(dirp);
76258f0484fSRodney W. Grimes 				cur->fts_info = FTS_ERR;
76358f0484fSRodney W. Grimes 				SET(FTS_STOP);
7641a9b5f47SBrian Feldman 				errno = saved_errno;
76558f0484fSRodney W. Grimes 				return (NULL);
76658f0484fSRodney W. Grimes 			}
7671a9b5f47SBrian Feldman 			/* Did realloc() change the pointer? */
7681a9b5f47SBrian Feldman 			if (oldaddr != sp->fts_path) {
7691a9b5f47SBrian Feldman 				doadjust = 1;
7701a9b5f47SBrian Feldman 				if (ISSET(FTS_NOCHDIR))
7711a9b5f47SBrian Feldman 					cp = sp->fts_path + len;
7721a9b5f47SBrian Feldman 			}
7731a9b5f47SBrian Feldman 			maxlen = sp->fts_pathlen - len;
77458f0484fSRodney W. Grimes 		}
77558f0484fSRodney W. Grimes 
77658f0484fSRodney W. Grimes 		p->fts_level = level;
7771a9b5f47SBrian Feldman 		p->fts_parent = sp->fts_cur;
778542fc104STim Kientzle 		p->fts_pathlen = len + dnamlen;
77958f0484fSRodney W. Grimes 
780adf6ad9eSPeter Wemm #ifdef FTS_WHITEOUT
781adf6ad9eSPeter Wemm 		if (dp->d_type == DT_WHT)
782adf6ad9eSPeter Wemm 			p->fts_flags |= FTS_ISW;
783adf6ad9eSPeter Wemm #endif
784adf6ad9eSPeter Wemm 
78558f0484fSRodney W. Grimes 		if (cderrno) {
78658f0484fSRodney W. Grimes 			if (nlinks) {
78758f0484fSRodney W. Grimes 				p->fts_info = FTS_NS;
78858f0484fSRodney W. Grimes 				p->fts_errno = cderrno;
78958f0484fSRodney W. Grimes 			} else
79058f0484fSRodney W. Grimes 				p->fts_info = FTS_NSOK;
79158f0484fSRodney W. Grimes 			p->fts_accpath = cur->fts_accpath;
79258f0484fSRodney W. Grimes 		} else if (nlinks == 0
79358f0484fSRodney W. Grimes #ifdef DT_DIR
7941a9b5f47SBrian Feldman 		    || (nostat &&
79551295a4dSJordan K. Hubbard 		    dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
79658f0484fSRodney W. Grimes #endif
79758f0484fSRodney W. Grimes 		    ) {
79858f0484fSRodney W. Grimes 			p->fts_accpath =
79958f0484fSRodney W. Grimes 			    ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
80058f0484fSRodney W. Grimes 			p->fts_info = FTS_NSOK;
80158f0484fSRodney W. Grimes 		} else {
80258f0484fSRodney W. Grimes 			/* Build a file name for fts_stat to stat. */
80358f0484fSRodney W. Grimes 			if (ISSET(FTS_NOCHDIR)) {
80458f0484fSRodney W. Grimes 				p->fts_accpath = p->fts_path;
80558f0484fSRodney W. Grimes 				memmove(cp, p->fts_name, p->fts_namelen + 1);
80654cc1f88SJilles Tjoelker 				p->fts_info = fts_stat(sp, p, 0, _dirfd(dirp));
80754cc1f88SJilles Tjoelker 			} else {
80858f0484fSRodney W. Grimes 				p->fts_accpath = p->fts_name;
80954cc1f88SJilles Tjoelker 				p->fts_info = fts_stat(sp, p, 0, -1);
81054cc1f88SJilles Tjoelker 			}
81158f0484fSRodney W. Grimes 
81258f0484fSRodney W. Grimes 			/* Decrement link count if applicable. */
81358f0484fSRodney W. Grimes 			if (nlinks > 0 && (p->fts_info == FTS_D ||
81458f0484fSRodney W. Grimes 			    p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
81558f0484fSRodney W. Grimes 				--nlinks;
81658f0484fSRodney W. Grimes 		}
81758f0484fSRodney W. Grimes 
81858f0484fSRodney W. Grimes 		/* We walk in directory order so "ls -f" doesn't get upset. */
81958f0484fSRodney W. Grimes 		p->fts_link = NULL;
82058f0484fSRodney W. Grimes 		if (head == NULL)
82158f0484fSRodney W. Grimes 			head = tail = p;
82258f0484fSRodney W. Grimes 		else {
82358f0484fSRodney W. Grimes 			tail->fts_link = p;
82458f0484fSRodney W. Grimes 			tail = p;
82558f0484fSRodney W. Grimes 		}
82658f0484fSRodney W. Grimes 		++nitems;
82758f0484fSRodney W. Grimes 	}
8289a91f1ccSWarner Losh 	if (dirp)
82958f0484fSRodney W. Grimes 		(void)closedir(dirp);
83058f0484fSRodney W. Grimes 
83158f0484fSRodney W. Grimes 	/*
8321a9b5f47SBrian Feldman 	 * If realloc() changed the address of the path, adjust the
8331a9b5f47SBrian Feldman 	 * addresses for the rest of the tree and the dir list.
83458f0484fSRodney W. Grimes 	 */
8351a9b5f47SBrian Feldman 	if (doadjust)
8361a9b5f47SBrian Feldman 		fts_padjust(sp, head);
83758f0484fSRodney W. Grimes 
83858f0484fSRodney W. Grimes 	/*
83958f0484fSRodney W. Grimes 	 * If not changing directories, reset the path back to original
84058f0484fSRodney W. Grimes 	 * state.
84158f0484fSRodney W. Grimes 	 */
842909e2601SJaakko Heinonen 	if (ISSET(FTS_NOCHDIR))
843909e2601SJaakko Heinonen 		sp->fts_path[cur->fts_pathlen] = '\0';
84458f0484fSRodney W. Grimes 
84558f0484fSRodney W. Grimes 	/*
84658f0484fSRodney W. Grimes 	 * If descended after called from fts_children or after called from
84758f0484fSRodney W. Grimes 	 * fts_read and nothing found, get back.  At the root level we use
84858f0484fSRodney W. Grimes 	 * the saved fd; if one of fts_open()'s arguments is a relative path
84958f0484fSRodney W. Grimes 	 * to an empty directory, we wind up here with no other way back.  If
85058f0484fSRodney W. Grimes 	 * can't get back, we're done.
85158f0484fSRodney W. Grimes 	 */
85258f0484fSRodney W. Grimes 	if (descend && (type == BCHILD || !nitems) &&
85358f0484fSRodney W. Grimes 	    (cur->fts_level == FTS_ROOTLEVEL ?
85493a85518SKris Kennaway 	    FCHDIR(sp, sp->fts_rfd) :
85593a85518SKris Kennaway 	    fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
85658f0484fSRodney W. Grimes 		cur->fts_info = FTS_ERR;
85758f0484fSRodney W. Grimes 		SET(FTS_STOP);
85858f0484fSRodney W. Grimes 		return (NULL);
85958f0484fSRodney W. Grimes 	}
86058f0484fSRodney W. Grimes 
86158f0484fSRodney W. Grimes 	/* If didn't find anything, return NULL. */
86258f0484fSRodney W. Grimes 	if (!nitems) {
86358f0484fSRodney W. Grimes 		if (type == BREAD)
86458f0484fSRodney W. Grimes 			cur->fts_info = FTS_DP;
86558f0484fSRodney W. Grimes 		return (NULL);
86658f0484fSRodney W. Grimes 	}
86758f0484fSRodney W. Grimes 
86858f0484fSRodney W. Grimes 	/* Sort the entries. */
86958f0484fSRodney W. Grimes 	if (sp->fts_compar && nitems > 1)
87058f0484fSRodney W. Grimes 		head = fts_sort(sp, head, nitems);
87158f0484fSRodney W. Grimes 	return (head);
87258f0484fSRodney W. Grimes }
87358f0484fSRodney W. Grimes 
87448aaad5fSYaroslav Tykhiy static int
87554cc1f88SJilles Tjoelker fts_stat(FTS *sp, FTSENT *p, int follow, int dfd)
87658f0484fSRodney W. Grimes {
877b231cb39SDavid E. O'Brien 	FTSENT *t;
878b231cb39SDavid E. O'Brien 	dev_t dev;
879b231cb39SDavid E. O'Brien 	ino_t ino;
88058f0484fSRodney W. Grimes 	struct stat *sbp, sb;
88158f0484fSRodney W. Grimes 	int saved_errno;
88254cc1f88SJilles Tjoelker 	const char *path;
88354cc1f88SJilles Tjoelker 
88454cc1f88SJilles Tjoelker 	if (dfd == -1)
88554cc1f88SJilles Tjoelker 		path = p->fts_accpath, dfd = AT_FDCWD;
88654cc1f88SJilles Tjoelker 	else
88754cc1f88SJilles Tjoelker 		path = p->fts_name;
88858f0484fSRodney W. Grimes 
88958f0484fSRodney W. Grimes 	/* If user needs stat info, stat buffer already allocated. */
89058f0484fSRodney W. Grimes 	sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
89158f0484fSRodney W. Grimes 
892adf6ad9eSPeter Wemm #ifdef FTS_WHITEOUT
893a1acdbf0SBruce Evans 	/* Check for whiteout. */
894adf6ad9eSPeter Wemm 	if (p->fts_flags & FTS_ISW) {
895adf6ad9eSPeter Wemm 		if (sbp != &sb) {
896adf6ad9eSPeter Wemm 			memset(sbp, '\0', sizeof(*sbp));
897adf6ad9eSPeter Wemm 			sbp->st_mode = S_IFWHT;
898adf6ad9eSPeter Wemm 		}
899adf6ad9eSPeter Wemm 		return (FTS_W);
900adf6ad9eSPeter Wemm 	}
901adf6ad9eSPeter Wemm #endif
902adf6ad9eSPeter Wemm 
90358f0484fSRodney W. Grimes 	/*
90458f0484fSRodney W. Grimes 	 * If doing a logical walk, or application requested FTS_FOLLOW, do
90558f0484fSRodney W. Grimes 	 * a stat(2).  If that fails, check for a non-existent symlink.  If
90658f0484fSRodney W. Grimes 	 * fail, set the errno from the stat call.
90758f0484fSRodney W. Grimes 	 */
90858f0484fSRodney W. Grimes 	if (ISSET(FTS_LOGICAL) || follow) {
90954cc1f88SJilles Tjoelker 		if (fstatat(dfd, path, sbp, 0)) {
91058f0484fSRodney W. Grimes 			saved_errno = errno;
911d30c6f8eSJilles Tjoelker 			if (fstatat(dfd, path, sbp, AT_SYMLINK_NOFOLLOW)) {
91258f0484fSRodney W. Grimes 				p->fts_errno = saved_errno;
91358f0484fSRodney W. Grimes 				goto err;
91458f0484fSRodney W. Grimes 			}
915d30c6f8eSJilles Tjoelker 			errno = 0;
916d30c6f8eSJilles Tjoelker 			if (S_ISLNK(sbp->st_mode))
917d30c6f8eSJilles Tjoelker 				return (FTS_SLNONE);
918d30c6f8eSJilles Tjoelker 		}
91954cc1f88SJilles Tjoelker 	} else if (fstatat(dfd, path, sbp, AT_SYMLINK_NOFOLLOW)) {
92058f0484fSRodney W. Grimes 		p->fts_errno = errno;
92158f0484fSRodney W. Grimes err:		memset(sbp, 0, sizeof(struct stat));
92258f0484fSRodney W. Grimes 		return (FTS_NS);
92358f0484fSRodney W. Grimes 	}
92458f0484fSRodney W. Grimes 
92558f0484fSRodney W. Grimes 	if (S_ISDIR(sbp->st_mode)) {
92658f0484fSRodney W. Grimes 		/*
92758f0484fSRodney W. Grimes 		 * Set the device/inode.  Used to find cycles and check for
92858f0484fSRodney W. Grimes 		 * crossing mount points.  Also remember the link count, used
92958f0484fSRodney W. Grimes 		 * in fts_build to limit the number of stat calls.  It is
93058f0484fSRodney W. Grimes 		 * understood that these fields are only referenced if fts_info
93158f0484fSRodney W. Grimes 		 * is set to FTS_D.
93258f0484fSRodney W. Grimes 		 */
93358f0484fSRodney W. Grimes 		dev = p->fts_dev = sbp->st_dev;
93458f0484fSRodney W. Grimes 		ino = p->fts_ino = sbp->st_ino;
93558f0484fSRodney W. Grimes 		p->fts_nlink = sbp->st_nlink;
93658f0484fSRodney W. Grimes 
93758f0484fSRodney W. Grimes 		if (ISDOT(p->fts_name))
93858f0484fSRodney W. Grimes 			return (FTS_DOT);
93958f0484fSRodney W. Grimes 
94058f0484fSRodney W. Grimes 		/*
94158f0484fSRodney W. Grimes 		 * Cycle detection is done by brute force when the directory
94258f0484fSRodney W. Grimes 		 * is first encountered.  If the tree gets deep enough or the
94358f0484fSRodney W. Grimes 		 * number of symbolic links to directories is high enough,
94458f0484fSRodney W. Grimes 		 * something faster might be worthwhile.
94558f0484fSRodney W. Grimes 		 */
94658f0484fSRodney W. Grimes 		for (t = p->fts_parent;
94758f0484fSRodney W. Grimes 		    t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
94858f0484fSRodney W. Grimes 			if (ino == t->fts_ino && dev == t->fts_dev) {
94958f0484fSRodney W. Grimes 				p->fts_cycle = t;
95058f0484fSRodney W. Grimes 				return (FTS_DC);
95158f0484fSRodney W. Grimes 			}
95258f0484fSRodney W. Grimes 		return (FTS_D);
95358f0484fSRodney W. Grimes 	}
95458f0484fSRodney W. Grimes 	if (S_ISLNK(sbp->st_mode))
95558f0484fSRodney W. Grimes 		return (FTS_SL);
95658f0484fSRodney W. Grimes 	if (S_ISREG(sbp->st_mode))
95758f0484fSRodney W. Grimes 		return (FTS_F);
95858f0484fSRodney W. Grimes 	return (FTS_DEFAULT);
95958f0484fSRodney W. Grimes }
96058f0484fSRodney W. Grimes 
9610d3bcc2eSGarrett Wollman /*
9620d3bcc2eSGarrett Wollman  * The comparison function takes pointers to pointers to FTSENT structures.
9630d3bcc2eSGarrett Wollman  * Qsort wants a comparison function that takes pointers to void.
9640d3bcc2eSGarrett Wollman  * (Both with appropriate levels of const-poisoning, of course!)
9650d3bcc2eSGarrett Wollman  * Use a trampoline function to deal with the difference.
9660d3bcc2eSGarrett Wollman  */
9670d3bcc2eSGarrett Wollman static int
9680d3bcc2eSGarrett Wollman fts_compar(const void *a, const void *b)
9690d3bcc2eSGarrett Wollman {
9700d3bcc2eSGarrett Wollman 	FTS *parent;
9710d3bcc2eSGarrett Wollman 
9720d3bcc2eSGarrett Wollman 	parent = (*(const FTSENT * const *)a)->fts_fts;
9730d3bcc2eSGarrett Wollman 	return (*parent->fts_compar)(a, b);
9740d3bcc2eSGarrett Wollman }
9750d3bcc2eSGarrett Wollman 
97658f0484fSRodney W. Grimes static FTSENT *
9773a12c046SXin LI fts_sort(FTS *sp, FTSENT *head, size_t nitems)
97858f0484fSRodney W. Grimes {
979b231cb39SDavid E. O'Brien 	FTSENT **ap, *p;
98058f0484fSRodney W. Grimes 
98158f0484fSRodney W. Grimes 	/*
98258f0484fSRodney W. Grimes 	 * Construct an array of pointers to the structures and call qsort(3).
98358f0484fSRodney W. Grimes 	 * Reassemble the array in the order returned by qsort.  If unable to
98458f0484fSRodney W. Grimes 	 * sort for memory reasons, return the directory entries in their
98558f0484fSRodney W. Grimes 	 * current order.  Allocate enough space for the current needs plus
98658f0484fSRodney W. Grimes 	 * 40 so don't realloc one entry at a time.
98758f0484fSRodney W. Grimes 	 */
98858f0484fSRodney W. Grimes 	if (nitems > sp->fts_nitems) {
98958f0484fSRodney W. Grimes 		sp->fts_nitems = nitems + 40;
9908ca72379SBrian Feldman 		if ((sp->fts_array = reallocf(sp->fts_array,
9911a9b5f47SBrian Feldman 		    sp->fts_nitems * sizeof(FTSENT *))) == NULL) {
99258f0484fSRodney W. Grimes 			sp->fts_nitems = 0;
99358f0484fSRodney W. Grimes 			return (head);
99458f0484fSRodney W. Grimes 		}
99558f0484fSRodney W. Grimes 	}
99658f0484fSRodney W. Grimes 	for (ap = sp->fts_array, p = head; p; p = p->fts_link)
99758f0484fSRodney W. Grimes 		*ap++ = p;
9980d3bcc2eSGarrett Wollman 	qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar);
99958f0484fSRodney W. Grimes 	for (head = *(ap = sp->fts_array); --nitems; ++ap)
100058f0484fSRodney W. Grimes 		ap[0]->fts_link = ap[1];
100158f0484fSRodney W. Grimes 	ap[0]->fts_link = NULL;
100258f0484fSRodney W. Grimes 	return (head);
100358f0484fSRodney W. Grimes }
100458f0484fSRodney W. Grimes 
100558f0484fSRodney W. Grimes static FTSENT *
10063a12c046SXin LI fts_alloc(FTS *sp, char *name, size_t namelen)
100758f0484fSRodney W. Grimes {
1008b231cb39SDavid E. O'Brien 	FTSENT *p;
100958f0484fSRodney W. Grimes 	size_t len;
101058f0484fSRodney W. Grimes 
10110d3bcc2eSGarrett Wollman 	struct ftsent_withstat {
10120d3bcc2eSGarrett Wollman 		FTSENT	ent;
10130d3bcc2eSGarrett Wollman 		struct	stat statbuf;
10140d3bcc2eSGarrett Wollman 	};
10150d3bcc2eSGarrett Wollman 
101658f0484fSRodney W. Grimes 	/*
101758f0484fSRodney W. Grimes 	 * The file name is a variable length array and no stat structure is
101858f0484fSRodney W. Grimes 	 * necessary if the user has set the nostat bit.  Allocate the FTSENT
101958f0484fSRodney W. Grimes 	 * structure, the file name and the stat structure in one chunk, but
10200d3bcc2eSGarrett Wollman 	 * be careful that the stat structure is reasonably aligned.
102158f0484fSRodney W. Grimes 	 */
10220d3bcc2eSGarrett Wollman 	if (ISSET(FTS_NOSTAT))
10230d3bcc2eSGarrett Wollman 		len = sizeof(FTSENT) + namelen + 1;
10240d3bcc2eSGarrett Wollman 	else
10250d3bcc2eSGarrett Wollman 		len = sizeof(struct ftsent_withstat) + namelen + 1;
10260d3bcc2eSGarrett Wollman 
102758f0484fSRodney W. Grimes 	if ((p = malloc(len)) == NULL)
102858f0484fSRodney W. Grimes 		return (NULL);
102958f0484fSRodney W. Grimes 
10300d3bcc2eSGarrett Wollman 	if (ISSET(FTS_NOSTAT)) {
10310d3bcc2eSGarrett Wollman 		p->fts_name = (char *)(p + 1);
10320d3bcc2eSGarrett Wollman 		p->fts_statp = NULL;
10330d3bcc2eSGarrett Wollman 	} else {
10340d3bcc2eSGarrett Wollman 		p->fts_name = (char *)((struct ftsent_withstat *)p + 1);
10350d3bcc2eSGarrett Wollman 		p->fts_statp = &((struct ftsent_withstat *)p)->statbuf;
10360d3bcc2eSGarrett Wollman 	}
103758f0484fSRodney W. Grimes 
10380d3bcc2eSGarrett Wollman 	/* Copy the name and guarantee NUL termination. */
10390d3bcc2eSGarrett Wollman 	memcpy(p->fts_name, name, namelen);
10400d3bcc2eSGarrett Wollman 	p->fts_name[namelen] = '\0';
104158f0484fSRodney W. Grimes 	p->fts_namelen = namelen;
104258f0484fSRodney W. Grimes 	p->fts_path = sp->fts_path;
104358f0484fSRodney W. Grimes 	p->fts_errno = 0;
104458f0484fSRodney W. Grimes 	p->fts_flags = 0;
104558f0484fSRodney W. Grimes 	p->fts_instr = FTS_NOINSTR;
104658f0484fSRodney W. Grimes 	p->fts_number = 0;
104758f0484fSRodney W. Grimes 	p->fts_pointer = NULL;
10480d3bcc2eSGarrett Wollman 	p->fts_fts = sp;
104958f0484fSRodney W. Grimes 	return (p);
105058f0484fSRodney W. Grimes }
105158f0484fSRodney W. Grimes 
105258f0484fSRodney W. Grimes static void
10533a12c046SXin LI fts_lfree(FTSENT *head)
105458f0484fSRodney W. Grimes {
1055b231cb39SDavid E. O'Brien 	FTSENT *p;
105658f0484fSRodney W. Grimes 
105758f0484fSRodney W. Grimes 	/* Free a linked list of structures. */
105851295a4dSJordan K. Hubbard 	while ((p = head)) {
105958f0484fSRodney W. Grimes 		head = head->fts_link;
106058f0484fSRodney W. Grimes 		free(p);
106158f0484fSRodney W. Grimes 	}
106258f0484fSRodney W. Grimes }
106358f0484fSRodney W. Grimes 
106458f0484fSRodney W. Grimes /*
106558f0484fSRodney W. Grimes  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
106658f0484fSRodney W. Grimes  * Most systems will allow creation of paths much longer than MAXPATHLEN, even
106758f0484fSRodney W. Grimes  * though the kernel won't resolve them.  Add the size (not just what's needed)
106858f0484fSRodney W. Grimes  * plus 256 bytes so don't realloc the path 2 bytes at a time.
106958f0484fSRodney W. Grimes  */
107058f0484fSRodney W. Grimes static int
10713a12c046SXin LI fts_palloc(FTS *sp, size_t more)
107258f0484fSRodney W. Grimes {
107358f0484fSRodney W. Grimes 
10741a9b5f47SBrian Feldman 	sp->fts_pathlen += more + 256;
10758ca72379SBrian Feldman 	sp->fts_path = reallocf(sp->fts_path, sp->fts_pathlen);
10768ca72379SBrian Feldman 	return (sp->fts_path == NULL);
1077f183d53eSWarner Losh }
1078f183d53eSWarner Losh 
107958f0484fSRodney W. Grimes /*
108058f0484fSRodney W. Grimes  * When the path is realloc'd, have to fix all of the pointers in structures
108158f0484fSRodney W. Grimes  * already returned.
108258f0484fSRodney W. Grimes  */
108358f0484fSRodney W. Grimes static void
10843a12c046SXin LI fts_padjust(FTS *sp, FTSENT *head)
108558f0484fSRodney W. Grimes {
108658f0484fSRodney W. Grimes 	FTSENT *p;
10871a9b5f47SBrian Feldman 	char *addr = sp->fts_path;
108858f0484fSRodney W. Grimes 
10898ca72379SBrian Feldman #define	ADJUST(p) do {							\
10901a9b5f47SBrian Feldman 	if ((p)->fts_accpath != (p)->fts_name) {			\
10911a9b5f47SBrian Feldman 		(p)->fts_accpath =					\
10921a9b5f47SBrian Feldman 		    (char *)addr + ((p)->fts_accpath - (p)->fts_path);	\
10931a9b5f47SBrian Feldman 	}								\
109458f0484fSRodney W. Grimes 	(p)->fts_path = addr;						\
10958ca72379SBrian Feldman } while (0)
109658f0484fSRodney W. Grimes 	/* Adjust the current set of children. */
109758f0484fSRodney W. Grimes 	for (p = sp->fts_child; p; p = p->fts_link)
10981a9b5f47SBrian Feldman 		ADJUST(p);
109958f0484fSRodney W. Grimes 
11001a9b5f47SBrian Feldman 	/* Adjust the rest of the tree, including the current level. */
11011a9b5f47SBrian Feldman 	for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
11021a9b5f47SBrian Feldman 		ADJUST(p);
110358f0484fSRodney W. Grimes 		p = p->fts_link ? p->fts_link : p->fts_parent;
110458f0484fSRodney W. Grimes 	}
110558f0484fSRodney W. Grimes }
110658f0484fSRodney W. Grimes 
110758f0484fSRodney W. Grimes static size_t
110858f0484fSRodney W. Grimes fts_maxarglen(argv)
110958f0484fSRodney W. Grimes 	char * const *argv;
111058f0484fSRodney W. Grimes {
111158f0484fSRodney W. Grimes 	size_t len, max;
111258f0484fSRodney W. Grimes 
111358f0484fSRodney W. Grimes 	for (max = 0; *argv; ++argv)
111458f0484fSRodney W. Grimes 		if ((len = strlen(*argv)) > max)
111558f0484fSRodney W. Grimes 			max = len;
11161a9b5f47SBrian Feldman 	return (max + 1);
111758f0484fSRodney W. Grimes }
11189a91f1ccSWarner Losh 
11199a91f1ccSWarner Losh /*
11209a91f1ccSWarner Losh  * Change to dir specified by fd or p->fts_accpath without getting
11219a91f1ccSWarner Losh  * tricked by someone changing the world out from underneath us.
11229a91f1ccSWarner Losh  * Assumes p->fts_dev and p->fts_ino are filled in.
11239a91f1ccSWarner Losh  */
11249a91f1ccSWarner Losh static int
11253a12c046SXin LI fts_safe_changedir(FTS *sp, FTSENT *p, int fd, char *path)
11269a91f1ccSWarner Losh {
11279a91f1ccSWarner Losh 	int ret, oerrno, newfd;
11289a91f1ccSWarner Losh 	struct stat sb;
11299a91f1ccSWarner Losh 
11309a91f1ccSWarner Losh 	newfd = fd;
11319a91f1ccSWarner Losh 	if (ISSET(FTS_NOCHDIR))
11329a91f1ccSWarner Losh 		return (0);
1133ad7d20c9SJilles Tjoelker 	if (fd < 0 && (newfd = _open(path, O_RDONLY | O_DIRECTORY |
1134ad7d20c9SJilles Tjoelker 	    O_CLOEXEC, 0)) < 0)
11359a91f1ccSWarner Losh 		return (-1);
1136d201fe46SDaniel Eischen 	if (_fstat(newfd, &sb)) {
11379a91f1ccSWarner Losh 		ret = -1;
11389a91f1ccSWarner Losh 		goto bail;
11399a91f1ccSWarner Losh 	}
11409a91f1ccSWarner Losh 	if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {
11419a91f1ccSWarner Losh 		errno = ENOENT;		/* disinformation */
11429a91f1ccSWarner Losh 		ret = -1;
11439a91f1ccSWarner Losh 		goto bail;
11449a91f1ccSWarner Losh 	}
11459a91f1ccSWarner Losh 	ret = fchdir(newfd);
11469a91f1ccSWarner Losh bail:
11479a91f1ccSWarner Losh 	oerrno = errno;
11489a91f1ccSWarner Losh 	if (fd < 0)
11499233c4d9SJason Evans 		(void)_close(newfd);
11509a91f1ccSWarner Losh 	errno = oerrno;
11519a91f1ccSWarner Losh 	return (ret);
11529a91f1ccSWarner Losh }
115399ca5b88SPeter Edwards 
115499ca5b88SPeter Edwards /*
115599ca5b88SPeter Edwards  * Check if the filesystem for "ent" has UFS-style links.
115699ca5b88SPeter Edwards  */
115799ca5b88SPeter Edwards static int
115899ca5b88SPeter Edwards fts_ufslinks(FTS *sp, const FTSENT *ent)
115999ca5b88SPeter Edwards {
116099ca5b88SPeter Edwards 	struct _fts_private *priv;
116199ca5b88SPeter Edwards 	const char **cpp;
116299ca5b88SPeter Edwards 
116307dee1a7SPeter Edwards 	priv = (struct _fts_private *)sp;
116499ca5b88SPeter Edwards 	/*
116599ca5b88SPeter Edwards 	 * If this node's device is different from the previous, grab
116699ca5b88SPeter Edwards 	 * the filesystem information, and decide on the reliability
116799ca5b88SPeter Edwards 	 * of the link information from this filesystem for stat(2)
116899ca5b88SPeter Edwards 	 * avoidance.
116999ca5b88SPeter Edwards 	 */
117099ca5b88SPeter Edwards 	if (priv->ftsp_dev != ent->fts_dev) {
117199ca5b88SPeter Edwards 		if (statfs(ent->fts_path, &priv->ftsp_statfs) != -1) {
117299ca5b88SPeter Edwards 			priv->ftsp_dev = ent->fts_dev;
117399ca5b88SPeter Edwards 			priv->ftsp_linksreliable = 0;
117499ca5b88SPeter Edwards 			for (cpp = ufslike_filesystems; *cpp; cpp++) {
117599ca5b88SPeter Edwards 				if (strcmp(priv->ftsp_statfs.f_fstypename,
117699ca5b88SPeter Edwards 				    *cpp) == 0) {
117799ca5b88SPeter Edwards 					priv->ftsp_linksreliable = 1;
117899ca5b88SPeter Edwards 					break;
117999ca5b88SPeter Edwards 				}
118099ca5b88SPeter Edwards 			}
118199ca5b88SPeter Edwards 		} else {
118299ca5b88SPeter Edwards 			priv->ftsp_linksreliable = 0;
118399ca5b88SPeter Edwards 		}
118499ca5b88SPeter Edwards 	}
118507dee1a7SPeter Edwards 	return (priv->ftsp_linksreliable);
118699ca5b88SPeter Edwards }
1187