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