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