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