xref: /freebsd/lib/libc/gen/fts-compat.c (revision 271c3a9060f2ee55607ebe146523f888e1db2654)
1 /*-
2  * Copyright (c) 1990, 1993, 1994
3  *	The Regents of the University of California.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  * 4. Neither the name of the University nor the names of its contributors
14  *    may be used to endorse or promote products derived from this software
15  *    without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  *
29  * $OpenBSD: fts.c,v 1.22 1999/10/03 19:22:22 millert Exp $
30  */
31 
32 #if 0
33 #if defined(LIBC_SCCS) && !defined(lint)
34 static char sccsid[] = "@(#)fts.c	8.6 (Berkeley) 8/14/94";
35 #endif /* LIBC_SCCS and not lint */
36 #endif
37 
38 #include <sys/cdefs.h>
39 __FBSDID("$FreeBSD$");
40 
41 #include "namespace.h"
42 #include <sys/param.h>
43 #include <sys/mount.h>
44 #include <sys/stat.h>
45 
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 "fts-compat.h"
53 #include "un-namespace.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 statfs	ftsp_statfs;
98 	dev_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 	"nfs",
114 	"nfs4",
115 	"ext2fs",
116 	0
117 };
118 
119 FTS *
120 __fts_open_44bsd(argv, options, compar)
121 	char * const *argv;
122 	int options;
123 	int (*compar)(const FTSENT * const *, const FTSENT * const *);
124 {
125 	struct _fts_private *priv;
126 	FTS *sp;
127 	FTSENT *p, *root;
128 	int nitems;
129 	FTSENT *parent, *tmp;
130 	int len;
131 
132 	/* Options check. */
133 	if (options & ~FTS_OPTIONMASK) {
134 		errno = EINVAL;
135 		return (NULL);
136 	}
137 
138 	/* Allocate/initialize the stream. */
139 	if ((priv = malloc(sizeof(*priv))) == NULL)
140 		return (NULL);
141 	memset(priv, 0, sizeof(*priv));
142 	sp = &priv->ftsp_fts;
143 	sp->fts_compar = compar;
144 	sp->fts_options = options;
145 
146 	/* Shush, GCC. */
147 	tmp = NULL;
148 
149 	/* Logical walks turn on NOCHDIR; symbolic links are too hard. */
150 	if (ISSET(FTS_LOGICAL))
151 		SET(FTS_NOCHDIR);
152 
153 	/*
154 	 * Start out with 1K of path space, and enough, in any case,
155 	 * to hold the user's paths.
156 	 */
157 	if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
158 		goto mem1;
159 
160 	/* Allocate/initialize root's parent. */
161 	if ((parent = fts_alloc(sp, "", 0)) == NULL)
162 		goto mem2;
163 	parent->fts_level = FTS_ROOTPARENTLEVEL;
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) && (sp->fts_rfd = _open(".", O_RDONLY, 0)) < 0)
221 		SET(FTS_NOCHDIR);
222 
223 	return (sp);
224 
225 mem3:	fts_lfree(root);
226 	free(parent);
227 mem2:	free(sp->fts_path);
228 mem1:	free(sp);
229 	return (NULL);
230 }
231 
232 static void
233 fts_load(sp, p)
234 	FTS *sp;
235 	FTSENT *p;
236 {
237 	int len;
238 	char *cp;
239 
240 	/*
241 	 * Load the stream structure for the next traversal.  Since we don't
242 	 * actually enter the directory until after the preorder visit, set
243 	 * the fts_accpath field specially so the chdir gets done to the right
244 	 * place and the user can access the first node.  From fts_open it's
245 	 * known that the path will fit.
246 	 */
247 	len = p->fts_pathlen = p->fts_namelen;
248 	memmove(sp->fts_path, p->fts_name, len + 1);
249 	if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
250 		len = strlen(++cp);
251 		memmove(p->fts_name, cp, len + 1);
252 		p->fts_namelen = len;
253 	}
254 	p->fts_accpath = p->fts_path = sp->fts_path;
255 	sp->fts_dev = p->fts_dev;
256 }
257 
258 int
259 __fts_close_44bsd(sp)
260 	FTS *sp;
261 {
262 	FTSENT *freep, *p;
263 	int saved_errno;
264 
265 	/*
266 	 * This still works if we haven't read anything -- the dummy structure
267 	 * points to the root list, so we step through to the end of the root
268 	 * list which has a valid parent pointer.
269 	 */
270 	if (sp->fts_cur) {
271 		for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
272 			freep = p;
273 			p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
274 			free(freep);
275 		}
276 		free(p);
277 	}
278 
279 	/* Free up child linked list, sort array, path buffer. */
280 	if (sp->fts_child)
281 		fts_lfree(sp->fts_child);
282 	if (sp->fts_array)
283 		free(sp->fts_array);
284 	free(sp->fts_path);
285 
286 	/* Return to original directory, save errno if necessary. */
287 	if (!ISSET(FTS_NOCHDIR)) {
288 		saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
289 		(void)_close(sp->fts_rfd);
290 
291 		/* Set errno and return. */
292 		if (saved_errno != 0) {
293 			/* Free up the stream pointer. */
294 			free(sp);
295 			errno = saved_errno;
296 			return (-1);
297 		}
298 	}
299 
300 	/* Free up the stream pointer. */
301 	free(sp);
302 	return (0);
303 }
304 
305 /*
306  * Special case of "/" at the end of the path so that slashes aren't
307  * appended which would cause paths to be written as "....//foo".
308  */
309 #define	NAPPEND(p)							\
310 	(p->fts_path[p->fts_pathlen - 1] == '/'				\
311 	    ? p->fts_pathlen - 1 : p->fts_pathlen)
312 
313 FTSENT *
314 __fts_read_44bsd(sp)
315 	FTS *sp;
316 {
317 	FTSENT *p, *tmp;
318 	int instr;
319 	char *t;
320 	int saved_errno;
321 
322 	/* If finished or unrecoverable error, return NULL. */
323 	if (sp->fts_cur == NULL || ISSET(FTS_STOP))
324 		return (NULL);
325 
326 	/* Set current node pointer. */
327 	p = sp->fts_cur;
328 
329 	/* Save and zero out user instructions. */
330 	instr = p->fts_instr;
331 	p->fts_instr = FTS_NOINSTR;
332 
333 	/* Any type of file may be re-visited; re-stat and re-turn. */
334 	if (instr == FTS_AGAIN) {
335 		p->fts_info = fts_stat(sp, p, 0);
336 		return (p);
337 	}
338 
339 	/*
340 	 * Following a symlink -- SLNONE test allows application to see
341 	 * SLNONE and recover.  If indirecting through a symlink, have
342 	 * keep a pointer to current location.  If unable to get that
343 	 * pointer, follow fails.
344 	 */
345 	if (instr == FTS_FOLLOW &&
346 	    (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
347 		p->fts_info = fts_stat(sp, p, 1);
348 		if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
349 			if ((p->fts_symfd = _open(".", O_RDONLY, 0)) < 0) {
350 				p->fts_errno = errno;
351 				p->fts_info = FTS_ERR;
352 			} else
353 				p->fts_flags |= FTS_SYMFOLLOW;
354 		}
355 		return (p);
356 	}
357 
358 	/* Directory in pre-order. */
359 	if (p->fts_info == FTS_D) {
360 		/* If skipped or crossed mount point, do post-order visit. */
361 		if (instr == FTS_SKIP ||
362 		    (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
363 			if (p->fts_flags & FTS_SYMFOLLOW)
364 				(void)_close(p->fts_symfd);
365 			if (sp->fts_child) {
366 				fts_lfree(sp->fts_child);
367 				sp->fts_child = NULL;
368 			}
369 			p->fts_info = FTS_DP;
370 			return (p);
371 		}
372 
373 		/* Rebuild if only read the names and now traversing. */
374 		if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
375 			CLR(FTS_NAMEONLY);
376 			fts_lfree(sp->fts_child);
377 			sp->fts_child = NULL;
378 		}
379 
380 		/*
381 		 * Cd to the subdirectory.
382 		 *
383 		 * If have already read and now fail to chdir, whack the list
384 		 * to make the names come out right, and set the parent errno
385 		 * so the application will eventually get an error condition.
386 		 * Set the FTS_DONTCHDIR flag so that when we logically change
387 		 * directories back to the parent we don't do a chdir.
388 		 *
389 		 * If haven't read do so.  If the read fails, fts_build sets
390 		 * FTS_STOP or the fts_info field of the node.
391 		 */
392 		if (sp->fts_child != NULL) {
393 			if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
394 				p->fts_errno = errno;
395 				p->fts_flags |= FTS_DONTCHDIR;
396 				for (p = sp->fts_child; p != NULL;
397 				    p = p->fts_link)
398 					p->fts_accpath =
399 					    p->fts_parent->fts_accpath;
400 			}
401 		} else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
402 			if (ISSET(FTS_STOP))
403 				return (NULL);
404 			return (p);
405 		}
406 		p = sp->fts_child;
407 		sp->fts_child = NULL;
408 		goto name;
409 	}
410 
411 	/* Move to the next node on this level. */
412 next:	tmp = p;
413 	if ((p = p->fts_link) != NULL) {
414 		free(tmp);
415 
416 		/*
417 		 * If reached the top, return to the original directory (or
418 		 * the root of the tree), and load the paths for the next root.
419 		 */
420 		if (p->fts_level == FTS_ROOTLEVEL) {
421 			if (FCHDIR(sp, sp->fts_rfd)) {
422 				SET(FTS_STOP);
423 				return (NULL);
424 			}
425 			fts_load(sp, p);
426 			return (sp->fts_cur = p);
427 		}
428 
429 		/*
430 		 * User may have called fts_set on the node.  If skipped,
431 		 * ignore.  If followed, get a file descriptor so we can
432 		 * get back if necessary.
433 		 */
434 		if (p->fts_instr == FTS_SKIP)
435 			goto next;
436 		if (p->fts_instr == FTS_FOLLOW) {
437 			p->fts_info = fts_stat(sp, p, 1);
438 			if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
439 				if ((p->fts_symfd =
440 				    _open(".", O_RDONLY, 0)) < 0) {
441 					p->fts_errno = errno;
442 					p->fts_info = FTS_ERR;
443 				} else
444 					p->fts_flags |= FTS_SYMFOLLOW;
445 			}
446 			p->fts_instr = FTS_NOINSTR;
447 		}
448 
449 name:		t = sp->fts_path + NAPPEND(p->fts_parent);
450 		*t++ = '/';
451 		memmove(t, p->fts_name, p->fts_namelen + 1);
452 		return (sp->fts_cur = p);
453 	}
454 
455 	/* Move up to the parent node. */
456 	p = tmp->fts_parent;
457 	free(tmp);
458 
459 	if (p->fts_level == FTS_ROOTPARENTLEVEL) {
460 		/*
461 		 * Done; free everything up and set errno to 0 so the user
462 		 * can distinguish between error and EOF.
463 		 */
464 		free(p);
465 		errno = 0;
466 		return (sp->fts_cur = NULL);
467 	}
468 
469 	/* NUL terminate the pathname. */
470 	sp->fts_path[p->fts_pathlen] = '\0';
471 
472 	/*
473 	 * Return to the parent directory.  If at a root node or came through
474 	 * a symlink, go back through the file descriptor.  Otherwise, cd up
475 	 * one directory.
476 	 */
477 	if (p->fts_level == FTS_ROOTLEVEL) {
478 		if (FCHDIR(sp, sp->fts_rfd)) {
479 			SET(FTS_STOP);
480 			return (NULL);
481 		}
482 	} else if (p->fts_flags & FTS_SYMFOLLOW) {
483 		if (FCHDIR(sp, p->fts_symfd)) {
484 			saved_errno = errno;
485 			(void)_close(p->fts_symfd);
486 			errno = saved_errno;
487 			SET(FTS_STOP);
488 			return (NULL);
489 		}
490 		(void)_close(p->fts_symfd);
491 	} else if (!(p->fts_flags & FTS_DONTCHDIR) &&
492 	    fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
493 		SET(FTS_STOP);
494 		return (NULL);
495 	}
496 	p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
497 	return (sp->fts_cur = p);
498 }
499 
500 /*
501  * Fts_set takes the stream as an argument although it's not used in this
502  * implementation; it would be necessary if anyone wanted to add global
503  * semantics to fts using fts_set.  An error return is allowed for similar
504  * reasons.
505  */
506 /* ARGSUSED */
507 int
508 __fts_set_44bsd(sp, p, instr)
509 	FTS *sp;
510 	FTSENT *p;
511 	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(sp, instr)
524 	FTS *sp;
525 	int instr;
526 {
527 	FTSENT *p;
528 	int fd;
529 
530 	if (instr != 0 && instr != FTS_NAMEONLY) {
531 		errno = EINVAL;
532 		return (NULL);
533 	}
534 
535 	/* Set current node pointer. */
536 	p = sp->fts_cur;
537 
538 	/*
539 	 * Errno set to 0 so user can distinguish empty directory from
540 	 * an error.
541 	 */
542 	errno = 0;
543 
544 	/* Fatal errors stop here. */
545 	if (ISSET(FTS_STOP))
546 		return (NULL);
547 
548 	/* Return logical hierarchy of user's arguments. */
549 	if (p->fts_info == FTS_INIT)
550 		return (p->fts_link);
551 
552 	/*
553 	 * If not a directory being visited in pre-order, stop here.  Could
554 	 * allow FTS_DNR, assuming the user has fixed the problem, but the
555 	 * same effect is available with FTS_AGAIN.
556 	 */
557 	if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
558 		return (NULL);
559 
560 	/* Free up any previous child list. */
561 	if (sp->fts_child != NULL)
562 		fts_lfree(sp->fts_child);
563 
564 	if (instr == FTS_NAMEONLY) {
565 		SET(FTS_NAMEONLY);
566 		instr = BNAMES;
567 	} else
568 		instr = BCHILD;
569 
570 	/*
571 	 * If using chdir on a relative path and called BEFORE fts_read does
572 	 * its chdir to the root of a traversal, we can lose -- we need to
573 	 * chdir into the subdirectory, and we don't know where the current
574 	 * directory is, so we can't get back so that the upcoming chdir by
575 	 * fts_read will work.
576 	 */
577 	if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
578 	    ISSET(FTS_NOCHDIR))
579 		return (sp->fts_child = fts_build(sp, instr));
580 
581 	if ((fd = _open(".", O_RDONLY, 0)) < 0)
582 		return (NULL);
583 	sp->fts_child = fts_build(sp, instr);
584 	if (fchdir(fd))
585 		return (NULL);
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(sp, type)
634 	FTS *sp;
635 	int type;
636 {
637 	struct dirent *dp;
638 	FTSENT *p, *head;
639 	int nitems;
640 	FTSENT *cur, *tail;
641 	DIR *dirp;
642 	void *oldaddr;
643 	size_t dnamlen;
644 	int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno,
645 	    nostat, doadjust;
646 	char *cp;
647 
648 	/* Set current node pointer. */
649 	cur = sp->fts_cur;
650 
651 	/*
652 	 * Open the directory for reading.  If this fails, we're done.
653 	 * If being called from fts_read, set the fts_info field.
654 	 */
655 #ifdef FTS_WHITEOUT
656 	if (ISSET(FTS_WHITEOUT))
657 		oflag = DTF_NODUP | DTF_REWIND;
658 	else
659 		oflag = DTF_HIDEW | DTF_NODUP | DTF_REWIND;
660 #else
661 #define __opendir2(path, flag) opendir(path)
662 #endif
663 	if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
664 		if (type == BREAD) {
665 			cur->fts_info = FTS_DNR;
666 			cur->fts_errno = errno;
667 		}
668 		return (NULL);
669 	}
670 
671 	/*
672 	 * Nlinks is the number of possible entries of type directory in the
673 	 * directory if we're cheating on stat calls, 0 if we're not doing
674 	 * any stat calls at all, -1 if we're doing stats on everything.
675 	 */
676 	if (type == BNAMES) {
677 		nlinks = 0;
678 		/* Be quiet about nostat, GCC. */
679 		nostat = 0;
680 	} else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
681 		if (fts_ufslinks(sp, cur))
682 			nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
683 		else
684 			nlinks = -1;
685 		nostat = 1;
686 	} else {
687 		nlinks = -1;
688 		nostat = 0;
689 	}
690 
691 #ifdef notdef
692 	(void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
693 	(void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
694 	    ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
695 #endif
696 	/*
697 	 * If we're going to need to stat anything or we want to descend
698 	 * and stay in the directory, chdir.  If this fails we keep going,
699 	 * but set a flag so we don't chdir after the post-order visit.
700 	 * We won't be able to stat anything, but we can still return the
701 	 * names themselves.  Note, that since fts_read won't be able to
702 	 * chdir into the directory, it will have to return different path
703 	 * names than before, i.e. "a/b" instead of "b".  Since the node
704 	 * has already been visited in pre-order, have to wait until the
705 	 * post-order visit to return the error.  There is a special case
706 	 * here, if there was nothing to stat then it's not an error to
707 	 * not be able to stat.  This is all fairly nasty.  If a program
708 	 * needed sorted entries or stat information, they had better be
709 	 * checking FTS_NS on the returned nodes.
710 	 */
711 	cderrno = 0;
712 	if (nlinks || type == BREAD) {
713 		if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
714 			if (nlinks && type == BREAD)
715 				cur->fts_errno = errno;
716 			cur->fts_flags |= FTS_DONTCHDIR;
717 			descend = 0;
718 			cderrno = errno;
719 		} else
720 			descend = 1;
721 	} else
722 		descend = 0;
723 
724 	/*
725 	 * Figure out the max file name length that can be stored in the
726 	 * current path -- the inner loop allocates more path as necessary.
727 	 * We really wouldn't have to do the maxlen calculations here, we
728 	 * could do them in fts_read before returning the path, but it's a
729 	 * lot easier here since the length is part of the dirent structure.
730 	 *
731 	 * If not changing directories set a pointer so that can just append
732 	 * each new name into the path.
733 	 */
734 	len = NAPPEND(cur);
735 	if (ISSET(FTS_NOCHDIR)) {
736 		cp = sp->fts_path + len;
737 		*cp++ = '/';
738 	} else {
739 		/* GCC, you're too verbose. */
740 		cp = NULL;
741 	}
742 	len++;
743 	maxlen = sp->fts_pathlen - len;
744 
745 	level = cur->fts_level + 1;
746 
747 	/* Read the directory, attaching each entry to the `link' pointer. */
748 	doadjust = 0;
749 	for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
750 		dnamlen = dp->d_namlen;
751 		if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
752 			continue;
753 
754 		if ((p = fts_alloc(sp, dp->d_name, (int)dnamlen)) == NULL)
755 			goto mem1;
756 		if (dnamlen >= maxlen) {	/* include space for NUL */
757 			oldaddr = sp->fts_path;
758 			if (fts_palloc(sp, dnamlen + len + 1)) {
759 				/*
760 				 * No more memory for path or structures.  Save
761 				 * errno, free up the current structure and the
762 				 * structures already allocated.
763 				 */
764 mem1:				saved_errno = errno;
765 				if (p)
766 					free(p);
767 				fts_lfree(head);
768 				(void)closedir(dirp);
769 				cur->fts_info = FTS_ERR;
770 				SET(FTS_STOP);
771 				errno = saved_errno;
772 				return (NULL);
773 			}
774 			/* Did realloc() change the pointer? */
775 			if (oldaddr != sp->fts_path) {
776 				doadjust = 1;
777 				if (ISSET(FTS_NOCHDIR))
778 					cp = sp->fts_path + len;
779 			}
780 			maxlen = sp->fts_pathlen - len;
781 		}
782 
783 		if (len + dnamlen >= USHRT_MAX) {
784 			/*
785 			 * In an FTSENT, fts_pathlen is a u_short so it is
786 			 * possible to wraparound here.  If we do, free up
787 			 * the current structure and the structures already
788 			 * allocated, then error out with ENAMETOOLONG.
789 			 */
790 			free(p);
791 			fts_lfree(head);
792 			(void)closedir(dirp);
793 			cur->fts_info = FTS_ERR;
794 			SET(FTS_STOP);
795 			errno = ENAMETOOLONG;
796 			return (NULL);
797 		}
798 		p->fts_level = level;
799 		p->fts_parent = sp->fts_cur;
800 		p->fts_pathlen = len + dnamlen;
801 
802 #ifdef FTS_WHITEOUT
803 		if (dp->d_type == DT_WHT)
804 			p->fts_flags |= FTS_ISW;
805 #endif
806 
807 		if (cderrno) {
808 			if (nlinks) {
809 				p->fts_info = FTS_NS;
810 				p->fts_errno = cderrno;
811 			} else
812 				p->fts_info = FTS_NSOK;
813 			p->fts_accpath = cur->fts_accpath;
814 		} else if (nlinks == 0
815 #ifdef DT_DIR
816 		    || (nostat &&
817 		    dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
818 #endif
819 		    ) {
820 			p->fts_accpath =
821 			    ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
822 			p->fts_info = FTS_NSOK;
823 		} else {
824 			/* Build a file name for fts_stat to stat. */
825 			if (ISSET(FTS_NOCHDIR)) {
826 				p->fts_accpath = p->fts_path;
827 				memmove(cp, p->fts_name, p->fts_namelen + 1);
828 			} else
829 				p->fts_accpath = p->fts_name;
830 			/* Stat it. */
831 			p->fts_info = fts_stat(sp, p, 0);
832 
833 			/* Decrement link count if applicable. */
834 			if (nlinks > 0 && (p->fts_info == FTS_D ||
835 			    p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
836 				--nlinks;
837 		}
838 
839 		/* We walk in directory order so "ls -f" doesn't get upset. */
840 		p->fts_link = NULL;
841 		if (head == NULL)
842 			head = tail = p;
843 		else {
844 			tail->fts_link = p;
845 			tail = p;
846 		}
847 		++nitems;
848 	}
849 	if (dirp)
850 		(void)closedir(dirp);
851 
852 	/*
853 	 * If realloc() changed the address of the path, adjust the
854 	 * addresses for the rest of the tree and the dir list.
855 	 */
856 	if (doadjust)
857 		fts_padjust(sp, head);
858 
859 	/*
860 	 * If not changing directories, reset the path back to original
861 	 * state.
862 	 */
863 	if (ISSET(FTS_NOCHDIR)) {
864 		if (len == sp->fts_pathlen || nitems == 0)
865 			--cp;
866 		*cp = '\0';
867 	}
868 
869 	/*
870 	 * If descended after called from fts_children or after called from
871 	 * fts_read and nothing found, get back.  At the root level we use
872 	 * the saved fd; if one of fts_open()'s arguments is a relative path
873 	 * to an empty directory, we wind up here with no other way back.  If
874 	 * can't get back, we're done.
875 	 */
876 	if (descend && (type == BCHILD || !nitems) &&
877 	    (cur->fts_level == FTS_ROOTLEVEL ?
878 	    FCHDIR(sp, sp->fts_rfd) :
879 	    fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
880 		cur->fts_info = FTS_ERR;
881 		SET(FTS_STOP);
882 		return (NULL);
883 	}
884 
885 	/* If didn't find anything, return NULL. */
886 	if (!nitems) {
887 		if (type == BREAD)
888 			cur->fts_info = FTS_DP;
889 		return (NULL);
890 	}
891 
892 	/* Sort the entries. */
893 	if (sp->fts_compar && nitems > 1)
894 		head = fts_sort(sp, head, nitems);
895 	return (head);
896 }
897 
898 static u_short
899 fts_stat(sp, p, follow)
900 	FTS *sp;
901 	FTSENT *p;
902 	int follow;
903 {
904 	FTSENT *t;
905 	dev_t dev;
906 	ino_t ino;
907 	struct stat *sbp, sb;
908 	int saved_errno;
909 
910 	/* If user needs stat info, stat buffer already allocated. */
911 	sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
912 
913 #ifdef FTS_WHITEOUT
914 	/* Check for whiteout. */
915 	if (p->fts_flags & FTS_ISW) {
916 		if (sbp != &sb) {
917 			memset(sbp, '\0', sizeof(*sbp));
918 			sbp->st_mode = S_IFWHT;
919 		}
920 		return (FTS_W);
921 	}
922 #endif
923 
924 	/*
925 	 * If doing a logical walk, or application requested FTS_FOLLOW, do
926 	 * a stat(2).  If that fails, check for a non-existent symlink.  If
927 	 * fail, set the errno from the stat call.
928 	 */
929 	if (ISSET(FTS_LOGICAL) || follow) {
930 		if (stat(p->fts_accpath, sbp)) {
931 			saved_errno = errno;
932 			if (!lstat(p->fts_accpath, sbp)) {
933 				errno = 0;
934 				return (FTS_SLNONE);
935 			}
936 			p->fts_errno = saved_errno;
937 			goto err;
938 		}
939 	} else if (lstat(p->fts_accpath, sbp)) {
940 		p->fts_errno = errno;
941 err:		memset(sbp, 0, sizeof(struct stat));
942 		return (FTS_NS);
943 	}
944 
945 	if (S_ISDIR(sbp->st_mode)) {
946 		/*
947 		 * Set the device/inode.  Used to find cycles and check for
948 		 * crossing mount points.  Also remember the link count, used
949 		 * in fts_build to limit the number of stat calls.  It is
950 		 * understood that these fields are only referenced if fts_info
951 		 * is set to FTS_D.
952 		 */
953 		dev = p->fts_dev = sbp->st_dev;
954 		ino = p->fts_ino = sbp->st_ino;
955 		p->fts_nlink = sbp->st_nlink;
956 
957 		if (ISDOT(p->fts_name))
958 			return (FTS_DOT);
959 
960 		/*
961 		 * Cycle detection is done by brute force when the directory
962 		 * is first encountered.  If the tree gets deep enough or the
963 		 * number of symbolic links to directories is high enough,
964 		 * something faster might be worthwhile.
965 		 */
966 		for (t = p->fts_parent;
967 		    t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
968 			if (ino == t->fts_ino && dev == t->fts_dev) {
969 				p->fts_cycle = t;
970 				return (FTS_DC);
971 			}
972 		return (FTS_D);
973 	}
974 	if (S_ISLNK(sbp->st_mode))
975 		return (FTS_SL);
976 	if (S_ISREG(sbp->st_mode))
977 		return (FTS_F);
978 	return (FTS_DEFAULT);
979 }
980 
981 /*
982  * The comparison function takes pointers to pointers to FTSENT structures.
983  * Qsort wants a comparison function that takes pointers to void.
984  * (Both with appropriate levels of const-poisoning, of course!)
985  * Use a trampoline function to deal with the difference.
986  */
987 static int
988 fts_compar(const void *a, const void *b)
989 {
990 	FTS *parent;
991 
992 	parent = (*(const FTSENT * const *)a)->fts_fts;
993 	return (*parent->fts_compar)(a, b);
994 }
995 
996 static FTSENT *
997 fts_sort(sp, head, nitems)
998 	FTS *sp;
999 	FTSENT *head;
1000 	int nitems;
1001 {
1002 	FTSENT **ap, *p;
1003 
1004 	/*
1005 	 * Construct an array of pointers to the structures and call qsort(3).
1006 	 * Reassemble the array in the order returned by qsort.  If unable to
1007 	 * sort for memory reasons, return the directory entries in their
1008 	 * current order.  Allocate enough space for the current needs plus
1009 	 * 40 so don't realloc one entry at a time.
1010 	 */
1011 	if (nitems > sp->fts_nitems) {
1012 		sp->fts_nitems = nitems + 40;
1013 		if ((sp->fts_array = reallocf(sp->fts_array,
1014 		    sp->fts_nitems * sizeof(FTSENT *))) == NULL) {
1015 			sp->fts_nitems = 0;
1016 			return (head);
1017 		}
1018 	}
1019 	for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1020 		*ap++ = p;
1021 	qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar);
1022 	for (head = *(ap = sp->fts_array); --nitems; ++ap)
1023 		ap[0]->fts_link = ap[1];
1024 	ap[0]->fts_link = NULL;
1025 	return (head);
1026 }
1027 
1028 static FTSENT *
1029 fts_alloc(sp, name, namelen)
1030 	FTS *sp;
1031 	char *name;
1032 	int namelen;
1033 {
1034 	FTSENT *p;
1035 	size_t len;
1036 
1037 	struct ftsent_withstat {
1038 		FTSENT	ent;
1039 		struct	stat statbuf;
1040 	};
1041 
1042 	/*
1043 	 * The file name is a variable length array and no stat structure is
1044 	 * necessary if the user has set the nostat bit.  Allocate the FTSENT
1045 	 * structure, the file name and the stat structure in one chunk, but
1046 	 * be careful that the stat structure is reasonably aligned.
1047 	 */
1048 	if (ISSET(FTS_NOSTAT))
1049 		len = sizeof(FTSENT) + namelen + 1;
1050 	else
1051 		len = sizeof(struct ftsent_withstat) + namelen + 1;
1052 
1053 	if ((p = malloc(len)) == NULL)
1054 		return (NULL);
1055 
1056 	if (ISSET(FTS_NOSTAT)) {
1057 		p->fts_name = (char *)(p + 1);
1058 		p->fts_statp = NULL;
1059 	} else {
1060 		p->fts_name = (char *)((struct ftsent_withstat *)p + 1);
1061 		p->fts_statp = &((struct ftsent_withstat *)p)->statbuf;
1062 	}
1063 
1064 	/* Copy the name and guarantee NUL termination. */
1065 	memcpy(p->fts_name, name, namelen);
1066 	p->fts_name[namelen] = '\0';
1067 	p->fts_namelen = namelen;
1068 	p->fts_path = sp->fts_path;
1069 	p->fts_errno = 0;
1070 	p->fts_flags = 0;
1071 	p->fts_instr = FTS_NOINSTR;
1072 	p->fts_number = 0;
1073 	p->fts_pointer = NULL;
1074 	p->fts_fts = sp;
1075 	return (p);
1076 }
1077 
1078 static void
1079 fts_lfree(head)
1080 	FTSENT *head;
1081 {
1082 	FTSENT *p;
1083 
1084 	/* Free a linked list of structures. */
1085 	while ((p = head)) {
1086 		head = head->fts_link;
1087 		free(p);
1088 	}
1089 }
1090 
1091 /*
1092  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
1093  * Most systems will allow creation of paths much longer than MAXPATHLEN, even
1094  * though the kernel won't resolve them.  Add the size (not just what's needed)
1095  * plus 256 bytes so don't realloc the path 2 bytes at a time.
1096  */
1097 static int
1098 fts_palloc(sp, more)
1099 	FTS *sp;
1100 	size_t more;
1101 {
1102 
1103 	sp->fts_pathlen += more + 256;
1104 	/*
1105 	 * Check for possible wraparound.  In an FTS, fts_pathlen is
1106 	 * a signed int but in an FTSENT it is an unsigned short.
1107 	 * We limit fts_pathlen to USHRT_MAX to be safe in both cases.
1108 	 */
1109 	if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) {
1110 		if (sp->fts_path)
1111 			free(sp->fts_path);
1112 		sp->fts_path = NULL;
1113 		errno = ENAMETOOLONG;
1114 		return (1);
1115 	}
1116 	sp->fts_path = reallocf(sp->fts_path, sp->fts_pathlen);
1117 	return (sp->fts_path == NULL);
1118 }
1119 
1120 /*
1121  * When the path is realloc'd, have to fix all of the pointers in structures
1122  * already returned.
1123  */
1124 static void
1125 fts_padjust(sp, head)
1126 	FTS *sp;
1127 	FTSENT *head;
1128 {
1129 	FTSENT *p;
1130 	char *addr = sp->fts_path;
1131 
1132 #define	ADJUST(p) do {							\
1133 	if ((p)->fts_accpath != (p)->fts_name) {			\
1134 		(p)->fts_accpath =					\
1135 		    (char *)addr + ((p)->fts_accpath - (p)->fts_path);	\
1136 	}								\
1137 	(p)->fts_path = addr;						\
1138 } while (0)
1139 	/* Adjust the current set of children. */
1140 	for (p = sp->fts_child; p; p = p->fts_link)
1141 		ADJUST(p);
1142 
1143 	/* Adjust the rest of the tree, including the current level. */
1144 	for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1145 		ADJUST(p);
1146 		p = p->fts_link ? p->fts_link : p->fts_parent;
1147 	}
1148 }
1149 
1150 static size_t
1151 fts_maxarglen(argv)
1152 	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(sp, p, fd, path)
1169 	FTS *sp;
1170 	FTSENT *p;
1171 	int fd;
1172 	char *path;
1173 {
1174 	int ret, oerrno, newfd;
1175 	struct stat sb;
1176 
1177 	newfd = fd;
1178 	if (ISSET(FTS_NOCHDIR))
1179 		return (0);
1180 	if (fd < 0 && (newfd = _open(path, O_RDONLY, 0)) < 0)
1181 		return (-1);
1182 	if (_fstat(newfd, &sb)) {
1183 		ret = -1;
1184 		goto bail;
1185 	}
1186 	if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {
1187 		errno = ENOENT;		/* disinformation */
1188 		ret = -1;
1189 		goto bail;
1190 	}
1191 	ret = fchdir(newfd);
1192 bail:
1193 	oerrno = errno;
1194 	if (fd < 0)
1195 		(void)_close(newfd);
1196 	errno = oerrno;
1197 	return (ret);
1198 }
1199 
1200 /*
1201  * Check if the filesystem for "ent" has UFS-style links.
1202  */
1203 static int
1204 fts_ufslinks(FTS *sp, const FTSENT *ent)
1205 {
1206 	struct _fts_private *priv;
1207 	const char **cpp;
1208 
1209 	priv = (struct _fts_private *)sp;
1210 	/*
1211 	 * If this node's device is different from the previous, grab
1212 	 * the filesystem information, and decide on the reliability
1213 	 * of the link information from this filesystem for stat(2)
1214 	 * avoidance.
1215 	 */
1216 	if (priv->ftsp_dev != ent->fts_dev) {
1217 		if (statfs(ent->fts_path, &priv->ftsp_statfs) != -1) {
1218 			priv->ftsp_dev = ent->fts_dev;
1219 			priv->ftsp_linksreliable = 0;
1220 			for (cpp = ufslike_filesystems; *cpp; cpp++) {
1221 				if (strcmp(priv->ftsp_statfs.f_fstypename,
1222 				    *cpp) == 0) {
1223 					priv->ftsp_linksreliable = 1;
1224 					break;
1225 				}
1226 			}
1227 		} else {
1228 			priv->ftsp_linksreliable = 0;
1229 		}
1230 	}
1231 	return (priv->ftsp_linksreliable);
1232 }
1233 
1234 __sym_compat(fts_open, __fts_open_44bsd, FBSD_1.0);
1235 __sym_compat(fts_close, __fts_close_44bsd, FBSD_1.0);
1236 __sym_compat(fts_read, __fts_read_44bsd, FBSD_1.0);
1237 __sym_compat(fts_set, __fts_set_44bsd, FBSD_1.0);
1238 __sym_compat(fts_children, __fts_children_44bsd, FBSD_1.0);
1239 __sym_compat(fts_get_clientptr, __fts_get_clientptr_44bsd, FBSD_1.0);
1240 __sym_compat(fts_get_stream, __fts_get_stream_44bsd, FBSD_1.0);
1241 __sym_compat(fts_set_clientptr, __fts_set_clientptr_44bsd, FBSD_1.0);
1242