xref: /freebsd/lib/libc/gen/fts.c (revision 380a989b3223d455375b4fae70fd0b9bdd43bafb)
1 /*	$OpenBSD: fts.c,v 1.9 1997/08/02 00:13:49 millert Exp $	*/
2 
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. All advertising materials mentioning features or use of this software
16  *    must display the following acknowledgement:
17  *	This product includes software developed by the University of
18  *	California, Berkeley and its contributors.
19  * 4. Neither the name of the University nor the names of its contributors
20  *    may be used to endorse or promote products derived from this software
21  *    without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33  * SUCH DAMAGE.
34  */
35 
36 #if defined(LIBC_SCCS) && !defined(lint)
37 static char sccsid[] = "@(#)fts.c	8.6 (Berkeley) 8/14/94";
38 #endif /* LIBC_SCCS and not lint */
39 
40 #include <sys/param.h>
41 #include <sys/stat.h>
42 
43 #include <dirent.h>
44 #include <errno.h>
45 #include <fcntl.h>
46 #include <fts.h>
47 #include <stdlib.h>
48 #include <string.h>
49 #include <unistd.h>
50 
51 static FTSENT	*fts_alloc __P((FTS *, char *, int));
52 static FTSENT	*fts_build __P((FTS *, int));
53 static void	 fts_lfree __P((FTSENT *));
54 static void	 fts_load __P((FTS *, FTSENT *));
55 static size_t	 fts_maxarglen __P((char * const *));
56 static void	 fts_padjust __P((FTS *, void *));
57 static int	 fts_palloc __P((FTS *, size_t));
58 static FTSENT	*fts_sort __P((FTS *, FTSENT *, int));
59 static u_short	 fts_stat __P((FTS *, FTSENT *, int));
60 static int	 fts_safe_changedir __P((FTS *, FTSENT *, int));
61 
62 #define	ISDOT(a)	(a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
63 
64 #define	CLR(opt)	(sp->fts_options &= ~(opt))
65 #define	ISSET(opt)	(sp->fts_options & (opt))
66 #define	SET(opt)	(sp->fts_options |= (opt))
67 
68 #define	CHDIR(sp, path)	(!ISSET(FTS_NOCHDIR) && chdir(path))
69 #define	FCHDIR(sp, fd)	(!ISSET(FTS_NOCHDIR) && fchdir(fd))
70 
71 /* fts_build flags */
72 #define	BCHILD		1		/* fts_children */
73 #define	BNAMES		2		/* fts_children, names only */
74 #define	BREAD		3		/* fts_read */
75 
76 FTS *
77 fts_open(argv, options, compar)
78 	char * const *argv;
79 	register int options;
80 	int (*compar) __P((const FTSENT **, const FTSENT **));
81 {
82 	register FTS *sp;
83 	register FTSENT *p, *root;
84 	register int nitems;
85 	FTSENT *parent, *tmp;
86 	int len;
87 
88 	/* Options check. */
89 	if (options & ~FTS_OPTIONMASK) {
90 		errno = EINVAL;
91 		return (NULL);
92 	}
93 
94 	/* Allocate/initialize the stream */
95 	if ((sp = malloc((u_int)sizeof(FTS))) == NULL)
96 		return (NULL);
97 	memset(sp, 0, sizeof(FTS));
98 	sp->fts_compar = compar;
99 	sp->fts_options = options;
100 
101 	/* Logical walks turn on NOCHDIR; symbolic links are too hard. */
102 	if (ISSET(FTS_LOGICAL))
103 		SET(FTS_NOCHDIR);
104 
105 	/*
106 	 * Start out with 1K of path space, and enough, in any case,
107 	 * to hold the user's paths.
108 	 */
109 	if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
110 		goto mem1;
111 
112 	/* Allocate/initialize root's parent. */
113 	if ((parent = fts_alloc(sp, "", 0)) == NULL)
114 		goto mem2;
115 	parent->fts_level = FTS_ROOTPARENTLEVEL;
116 
117 	/* Allocate/initialize root(s). */
118 	for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
119 		/* Don't allow zero-length paths. */
120 		if ((len = strlen(*argv)) == 0) {
121 			errno = ENOENT;
122 			goto mem3;
123 		}
124 
125 		p = fts_alloc(sp, *argv, len);
126 		p->fts_level = FTS_ROOTLEVEL;
127 		p->fts_parent = parent;
128 		p->fts_accpath = p->fts_name;
129 		p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));
130 
131 		/* Command-line "." and ".." are real directories. */
132 		if (p->fts_info == FTS_DOT)
133 			p->fts_info = FTS_D;
134 
135 		/*
136 		 * If comparison routine supplied, traverse in sorted
137 		 * order; otherwise traverse in the order specified.
138 		 */
139 		if (compar) {
140 			p->fts_link = root;
141 			root = p;
142 		} else {
143 			p->fts_link = NULL;
144 			if (root == NULL)
145 				tmp = root = p;
146 			else {
147 				tmp->fts_link = p;
148 				tmp = p;
149 			}
150 		}
151 	}
152 	if (compar && nitems > 1)
153 		root = fts_sort(sp, root, nitems);
154 
155 	/*
156 	 * Allocate a dummy pointer and make fts_read think that we've just
157 	 * finished the node before the root(s); set p->fts_info to FTS_INIT
158 	 * so that everything about the "current" node is ignored.
159 	 */
160 	if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
161 		goto mem3;
162 	sp->fts_cur->fts_link = root;
163 	sp->fts_cur->fts_info = FTS_INIT;
164 
165 	/*
166 	 * If using chdir(2), grab a file descriptor pointing to dot to insure
167 	 * that we can get back here; this could be avoided for some paths,
168 	 * but almost certainly not worth the effort.  Slashes, symbolic links,
169 	 * and ".." are all fairly nasty problems.  Note, if we can't get the
170 	 * descriptor we run anyway, just more slowly.
171 	 */
172 	if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)
173 		SET(FTS_NOCHDIR);
174 
175 	return (sp);
176 
177 mem3:	fts_lfree(root);
178 	free(parent);
179 mem2:	free(sp->fts_path);
180 mem1:	free(sp);
181 	return (NULL);
182 }
183 
184 static void
185 fts_load(sp, p)
186 	FTS *sp;
187 	register FTSENT *p;
188 {
189 	register int len;
190 	register char *cp;
191 
192 	/*
193 	 * Load the stream structure for the next traversal.  Since we don't
194 	 * actually enter the directory until after the preorder visit, set
195 	 * the fts_accpath field specially so the chdir gets done to the right
196 	 * place and the user can access the first node.  From fts_open it's
197 	 * known that the path will fit.
198 	 */
199 	len = p->fts_pathlen = p->fts_namelen;
200 	memmove(sp->fts_path, p->fts_name, len + 1);
201 	if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
202 		len = strlen(++cp);
203 		memmove(p->fts_name, cp, len + 1);
204 		p->fts_namelen = len;
205 	}
206 	p->fts_accpath = p->fts_path = sp->fts_path;
207 	sp->fts_dev = p->fts_dev;
208 }
209 
210 int
211 fts_close(sp)
212 	FTS *sp;
213 {
214 	register FTSENT *freep, *p;
215 	int saved_errno;
216 
217 	/*
218 	 * This still works if we haven't read anything -- the dummy structure
219 	 * points to the root list, so we step through to the end of the root
220 	 * list which has a valid parent pointer.
221 	 */
222 	if (sp->fts_cur) {
223 		for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
224 			freep = p;
225 			p = p->fts_link ? p->fts_link : p->fts_parent;
226 			free(freep);
227 		}
228 		free(p);
229 	}
230 
231 	/* Free up child linked list, sort array, path buffer. */
232 	if (sp->fts_child)
233 		fts_lfree(sp->fts_child);
234 	if (sp->fts_array)
235 		free(sp->fts_array);
236 	free(sp->fts_path);
237 
238 	/* Return to original directory, save errno if necessary. */
239 	if (!ISSET(FTS_NOCHDIR)) {
240 		saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
241 		(void)close(sp->fts_rfd);
242 	}
243 
244 	/* Set errno and return. */
245 	if (!ISSET(FTS_NOCHDIR) && saved_errno) {
246 		/* Free up the stream pointer. */
247 		free(sp);
248 		errno = saved_errno;
249 		return (-1);
250 	}
251 	/* Free up the stream pointer. */
252 	free(sp);
253 	return (0);
254 }
255 
256 /*
257  * Special case of "/" at the end of the path so that slashes aren't
258  * appended which would cause paths to be written as "....//foo".
259  */
260 #define	NAPPEND(p)							\
261 	(p->fts_path[p->fts_pathlen - 1] == '/'				\
262 	    ? p->fts_pathlen - 1 : p->fts_pathlen)
263 
264 FTSENT *
265 fts_read(sp)
266 	register FTS *sp;
267 {
268 	register FTSENT *p, *tmp;
269 	register int instr;
270 	register char *t;
271 	int saved_errno;
272 
273 	/* If finished or unrecoverable error, return NULL. */
274 	if (sp->fts_cur == NULL || ISSET(FTS_STOP))
275 		return (NULL);
276 
277 	/* Set current node pointer. */
278 	p = sp->fts_cur;
279 
280 	/* Save and zero out user instructions. */
281 	instr = p->fts_instr;
282 	p->fts_instr = FTS_NOINSTR;
283 
284 	/* Any type of file may be re-visited; re-stat and re-turn. */
285 	if (instr == FTS_AGAIN) {
286 		p->fts_info = fts_stat(sp, p, 0);
287 		return (p);
288 	}
289 
290 	/*
291 	 * Following a symlink -- SLNONE test allows application to see
292 	 * SLNONE and recover.  If indirecting through a symlink, have
293 	 * keep a pointer to current location.  If unable to get that
294 	 * pointer, follow fails.
295 	 */
296 	if (instr == FTS_FOLLOW &&
297 	    (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
298 		p->fts_info = fts_stat(sp, p, 1);
299 		if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR))
300 			if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) {
301 				p->fts_errno = errno;
302 				p->fts_info = FTS_ERR;
303 			} else
304 				p->fts_flags |= FTS_SYMFOLLOW;
305 		return (p);
306 	}
307 
308 	/* Directory in pre-order. */
309 	if (p->fts_info == FTS_D) {
310 		/* If skipped or crossed mount point, do post-order visit. */
311 		if (instr == FTS_SKIP ||
312 		    (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
313 			if (p->fts_flags & FTS_SYMFOLLOW)
314 				(void)close(p->fts_symfd);
315 			if (sp->fts_child) {
316 				fts_lfree(sp->fts_child);
317 				sp->fts_child = NULL;
318 			}
319 			p->fts_info = FTS_DP;
320 			return (p);
321 		}
322 
323 		/* Rebuild if only read the names and now traversing. */
324 		if (sp->fts_child && ISSET(FTS_NAMEONLY)) {
325 			CLR(FTS_NAMEONLY);
326 			fts_lfree(sp->fts_child);
327 			sp->fts_child = NULL;
328 		}
329 
330 		/*
331 		 * Cd to the subdirectory.
332 		 *
333 		 * If have already read and now fail to chdir, whack the list
334 		 * to make the names come out right, and set the parent errno
335 		 * so the application will eventually get an error condition.
336 		 * Set the FTS_DONTCHDIR flag so that when we logically change
337 		 * directories back to the parent we don't do a chdir.
338 		 *
339 		 * If haven't read do so.  If the read fails, fts_build sets
340 		 * FTS_STOP or the fts_info field of the node.
341 		 */
342 		if (sp->fts_child) {
343 			if (fts_safe_changedir(sp, p, -1)) {
344 				p->fts_errno = errno;
345 				p->fts_flags |= FTS_DONTCHDIR;
346 				for (p = sp->fts_child; p; p = p->fts_link)
347 					p->fts_accpath =
348 					    p->fts_parent->fts_accpath;
349 			}
350 		} else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
351 			if (ISSET(FTS_STOP))
352 				return (NULL);
353 			return (p);
354 		}
355 		p = sp->fts_child;
356 		sp->fts_child = NULL;
357 		goto name;
358 	}
359 
360 	/* Move to the next node on this level. */
361 next:	tmp = p;
362 	if ((p = p->fts_link)) {
363 		free(tmp);
364 
365 		/*
366 		 * If reached the top, return to the original directory, and
367 		 * load the paths for the next root.
368 		 */
369 		if (p->fts_level == FTS_ROOTLEVEL) {
370 			if (FCHDIR(sp, sp->fts_rfd)) {
371 				SET(FTS_STOP);
372 				return (NULL);
373 			}
374 			fts_load(sp, p);
375 			return (sp->fts_cur = p);
376 		}
377 
378 		/*
379 		 * User may have called fts_set on the node.  If skipped,
380 		 * ignore.  If followed, get a file descriptor so we can
381 		 * get back if necessary.
382 		 */
383 		if (p->fts_instr == FTS_SKIP)
384 			goto next;
385 		if (p->fts_instr == FTS_FOLLOW) {
386 			p->fts_info = fts_stat(sp, p, 1);
387 			if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR))
388 				if ((p->fts_symfd =
389 				    open(".", O_RDONLY, 0)) < 0) {
390 					p->fts_errno = errno;
391 					p->fts_info = FTS_ERR;
392 				} else
393 					p->fts_flags |= FTS_SYMFOLLOW;
394 			p->fts_instr = FTS_NOINSTR;
395 		}
396 
397 name:		t = sp->fts_path + NAPPEND(p->fts_parent);
398 		*t++ = '/';
399 		memmove(t, p->fts_name, p->fts_namelen + 1);
400 		return (sp->fts_cur = p);
401 	}
402 
403 	/* Move up to the parent node. */
404 	p = tmp->fts_parent;
405 	free(tmp);
406 
407 	if (p->fts_level == FTS_ROOTPARENTLEVEL) {
408 		/*
409 		 * Done; free everything up and set errno to 0 so the user
410 		 * can distinguish between error and EOF.
411 		 */
412 		free(p);
413 		errno = 0;
414 		return (sp->fts_cur = NULL);
415 	}
416 
417 	/* Nul terminate the pathname. */
418 	sp->fts_path[p->fts_pathlen] = '\0';
419 
420 	/*
421 	 * Return to the parent directory.  If at a root node or came through
422 	 * a symlink, go back through the file descriptor.  Otherwise, cd up
423 	 * one directory.
424 	 */
425 	if (p->fts_level == FTS_ROOTLEVEL) {
426 		if (FCHDIR(sp, sp->fts_rfd)) {
427 			SET(FTS_STOP);
428 			return (NULL);
429 		}
430 	} else if (p->fts_flags & FTS_SYMFOLLOW) {
431 		if (FCHDIR(sp, p->fts_symfd)) {
432 			saved_errno = errno;
433 			(void)close(p->fts_symfd);
434 			errno = saved_errno;
435 			SET(FTS_STOP);
436 			return (NULL);
437 		}
438 		(void)close(p->fts_symfd);
439 	} else if (!(p->fts_flags & FTS_DONTCHDIR)) {
440 		if (CHDIR(sp, "..")) {
441 			SET(FTS_STOP);
442 			return (NULL);
443 		}
444 	}
445 	p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
446 	return (sp->fts_cur = p);
447 }
448 
449 /*
450  * Fts_set takes the stream as an argument although it's not used in this
451  * implementation; it would be necessary if anyone wanted to add global
452  * semantics to fts using fts_set.  An error return is allowed for similar
453  * reasons.
454  */
455 /* ARGSUSED */
456 int
457 fts_set(sp, p, instr)
458 	FTS *sp;
459 	FTSENT *p;
460 	int instr;
461 {
462 	if (instr && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
463 	    instr != FTS_NOINSTR && instr != FTS_SKIP) {
464 		errno = EINVAL;
465 		return (1);
466 	}
467 	p->fts_instr = instr;
468 	return (0);
469 }
470 
471 FTSENT *
472 fts_children(sp, instr)
473 	register FTS *sp;
474 	int instr;
475 {
476 	register FTSENT *p;
477 	int fd;
478 
479 	if (instr && instr != FTS_NAMEONLY) {
480 		errno = EINVAL;
481 		return (NULL);
482 	}
483 
484 	/* Set current node pointer. */
485 	p = sp->fts_cur;
486 
487 	/*
488 	 * Errno set to 0 so user can distinguish empty directory from
489 	 * an error.
490 	 */
491 	errno = 0;
492 
493 	/* Fatal errors stop here. */
494 	if (ISSET(FTS_STOP))
495 		return (NULL);
496 
497 	/* Return logical hierarchy of user's arguments. */
498 	if (p->fts_info == FTS_INIT)
499 		return (p->fts_link);
500 
501 	/*
502 	 * If not a directory being visited in pre-order, stop here.  Could
503 	 * allow FTS_DNR, assuming the user has fixed the problem, but the
504 	 * same effect is available with FTS_AGAIN.
505 	 */
506 	if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
507 		return (NULL);
508 
509 	/* Free up any previous child list. */
510 	if (sp->fts_child)
511 		fts_lfree(sp->fts_child);
512 
513 	if (instr == FTS_NAMEONLY) {
514 		SET(FTS_NAMEONLY);
515 		instr = BNAMES;
516 	} else
517 		instr = BCHILD;
518 
519 	/*
520 	 * If using chdir on a relative path and called BEFORE fts_read does
521 	 * its chdir to the root of a traversal, we can lose -- we need to
522 	 * chdir into the subdirectory, and we don't know where the current
523 	 * directory is, so we can't get back so that the upcoming chdir by
524 	 * fts_read will work.
525 	 */
526 	if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
527 	    ISSET(FTS_NOCHDIR))
528 		return (sp->fts_child = fts_build(sp, instr));
529 
530 	if ((fd = open(".", O_RDONLY, 0)) < 0)
531 		return (NULL);
532 	sp->fts_child = fts_build(sp, instr);
533 	if (fchdir(fd))
534 		return (NULL);
535 	(void)close(fd);
536 	return (sp->fts_child);
537 }
538 
539 /*
540  * This is the tricky part -- do not casually change *anything* in here.  The
541  * idea is to build the linked list of entries that are used by fts_children
542  * and fts_read.  There are lots of special cases.
543  *
544  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
545  * set and it's a physical walk (so that symbolic links can't be directories),
546  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
547  * of the file is in the directory entry.  Otherwise, we assume that the number
548  * of subdirectories in a node is equal to the number of links to the parent.
549  * The former skips all stat calls.  The latter skips stat calls in any leaf
550  * directories and for any files after the subdirectories in the directory have
551  * been found, cutting the stat calls by about 2/3.
552  */
553 static FTSENT *
554 fts_build(sp, type)
555 	register FTS *sp;
556 	int type;
557 {
558 	register struct dirent *dp;
559 	register FTSENT *p, *head;
560 	register int nitems;
561 	FTSENT *cur, *tail;
562 	DIR *dirp;
563 	void *adjaddr;
564 	int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno;
565 	char *cp;
566 
567 	/* Set current node pointer. */
568 	cur = sp->fts_cur;
569 
570 	/*
571 	 * Open the directory for reading.  If this fails, we're done.
572 	 * If being called from fts_read, set the fts_info field.
573 	 */
574 #ifdef FTS_WHITEOUT
575 	if (ISSET(FTS_WHITEOUT))
576 		oflag = DTF_NODUP|DTF_REWIND;
577 	else
578 		oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
579 #else
580 #define __opendir2(path, flag) opendir(path)
581 #endif
582 	if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
583 		if (type == BREAD) {
584 			cur->fts_info = FTS_DNR;
585 			cur->fts_errno = errno;
586 		}
587 		return (NULL);
588 	}
589 
590 	/*
591 	 * Nlinks is the number of possible entries of type directory in the
592 	 * directory if we're cheating on stat calls, 0 if we're not doing
593 	 * any stat calls at all, -1 if we're doing stats on everything.
594 	 */
595 	if (type == BNAMES)
596 		nlinks = 0;
597 	else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL))
598 		nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
599 	else
600 		nlinks = -1;
601 
602 #ifdef notdef
603 	(void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
604 	(void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
605 	    ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
606 #endif
607 	/*
608 	 * If we're going to need to stat anything or we want to descend
609 	 * and stay in the directory, chdir.  If this fails we keep going,
610 	 * but set a flag so we don't chdir after the post-order visit.
611 	 * We won't be able to stat anything, but we can still return the
612 	 * names themselves.  Note, that since fts_read won't be able to
613 	 * chdir into the directory, it will have to return different path
614 	 * names than before, i.e. "a/b" instead of "b".  Since the node
615 	 * has already been visited in pre-order, have to wait until the
616 	 * post-order visit to return the error.  There is a special case
617 	 * here, if there was nothing to stat then it's not an error to
618 	 * not be able to stat.  This is all fairly nasty.  If a program
619 	 * needed sorted entries or stat information, they had better be
620 	 * checking FTS_NS on the returned nodes.
621 	 */
622 	cderrno = 0;
623 	if (nlinks || type == BREAD)
624 		if (fts_safe_changedir(sp, cur, dirfd(dirp))) {
625 			if (nlinks && type == BREAD)
626 				cur->fts_errno = errno;
627 			cur->fts_flags |= FTS_DONTCHDIR;
628 			descend = 0;
629 			cderrno = errno;
630 			(void)closedir(dirp);
631 			dirp = NULL;
632 		} else
633 			descend = 1;
634 	else
635 		descend = 0;
636 
637 	/*
638 	 * Figure out the max file name length that can be stored in the
639 	 * current path -- the inner loop allocates more path as necessary.
640 	 * We really wouldn't have to do the maxlen calculations here, we
641 	 * could do them in fts_read before returning the path, but it's a
642 	 * lot easier here since the length is part of the dirent structure.
643 	 *
644 	 * If not changing directories set a pointer so that can just append
645 	 * each new name into the path.
646 	 */
647 	maxlen = sp->fts_pathlen - cur->fts_pathlen - 1;
648 	len = NAPPEND(cur);
649 	if (ISSET(FTS_NOCHDIR)) {
650 		cp = sp->fts_path + len;
651 		*cp++ = '/';
652 	}
653 
654 	level = cur->fts_level + 1;
655 
656 	/* Read the directory, attaching each entry to the `link' pointer. */
657 	adjaddr = NULL;
658 	for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
659 		if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
660 			continue;
661 
662 		if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL)
663 			goto mem1;
664 		if (dp->d_namlen > maxlen) {
665 			if (fts_palloc(sp, (size_t)dp->d_namlen)) {
666 				/*
667 				 * No more memory for path or structures.  Save
668 				 * errno, free up the current structure and the
669 				 * structures already allocated.
670 				 */
671 mem1:				saved_errno = errno;
672 				if (p)
673 					free(p);
674 				fts_lfree(head);
675 				(void)closedir(dirp);
676 				errno = saved_errno;
677 				cur->fts_info = FTS_ERR;
678 				SET(FTS_STOP);
679 				return (NULL);
680 			}
681 			adjaddr = sp->fts_path;
682 			maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
683 		}
684 
685 		p->fts_pathlen = len + dp->d_namlen + 1;
686 		p->fts_parent = sp->fts_cur;
687 		p->fts_level = level;
688 
689 #ifdef FTS_WHITEOUT
690 		if (dp->d_type == DT_WHT)
691 			p->fts_flags |= FTS_ISW;
692 #endif
693 
694 		if (cderrno) {
695 			if (nlinks) {
696 				p->fts_info = FTS_NS;
697 				p->fts_errno = cderrno;
698 			} else
699 				p->fts_info = FTS_NSOK;
700 			p->fts_accpath = cur->fts_accpath;
701 		} else if (nlinks == 0
702 #ifdef DT_DIR
703 		    || (nlinks > 0 &&
704 		    dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
705 #endif
706 		    ) {
707 			p->fts_accpath =
708 			    ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
709 			p->fts_info = FTS_NSOK;
710 		} else {
711 			/* Build a file name for fts_stat to stat. */
712 			if (ISSET(FTS_NOCHDIR)) {
713 				p->fts_accpath = p->fts_path;
714 				memmove(cp, p->fts_name, p->fts_namelen + 1);
715 			} else
716 				p->fts_accpath = p->fts_name;
717 			/* Stat it. */
718 			p->fts_info = fts_stat(sp, p, 0);
719 
720 			/* Decrement link count if applicable. */
721 			if (nlinks > 0 && (p->fts_info == FTS_D ||
722 			    p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
723 				--nlinks;
724 		}
725 
726 		/* We walk in directory order so "ls -f" doesn't get upset. */
727 		p->fts_link = NULL;
728 		if (head == NULL)
729 			head = tail = p;
730 		else {
731 			tail->fts_link = p;
732 			tail = p;
733 		}
734 		++nitems;
735 	}
736 	if (dirp)
737 		(void)closedir(dirp);
738 
739 	/*
740 	 * If had to realloc the path, adjust the addresses for the rest
741 	 * of the tree.
742 	 */
743 	if (adjaddr)
744 		fts_padjust(sp, adjaddr);
745 
746 	/*
747 	 * If not changing directories, reset the path back to original
748 	 * state.
749 	 */
750 	if (ISSET(FTS_NOCHDIR)) {
751 		if (len == sp->fts_pathlen)
752 			--cp;
753 		*cp = '\0';
754 	}
755 
756 	/*
757 	 * If descended after called from fts_children or after called from
758 	 * fts_read and nothing found, get back.  At the root level we use
759 	 * the saved fd; if one of fts_open()'s arguments is a relative path
760 	 * to an empty directory, we wind up here with no other way back.  If
761 	 * can't get back, we're done.
762 	 */
763 	if (descend && (type == BCHILD || !nitems) &&
764 	    (cur->fts_level == FTS_ROOTLEVEL ?
765 	    FCHDIR(sp, sp->fts_rfd) : CHDIR(sp, ".."))) {
766 		cur->fts_info = FTS_ERR;
767 		SET(FTS_STOP);
768 		return (NULL);
769 	}
770 
771 	/* If didn't find anything, return NULL. */
772 	if (!nitems) {
773 		if (type == BREAD)
774 			cur->fts_info = FTS_DP;
775 		return (NULL);
776 	}
777 
778 	/* Sort the entries. */
779 	if (sp->fts_compar && nitems > 1)
780 		head = fts_sort(sp, head, nitems);
781 	return (head);
782 }
783 
784 static u_short
785 fts_stat(sp, p, follow)
786 	FTS *sp;
787 	register FTSENT *p;
788 	int follow;
789 {
790 	register FTSENT *t;
791 	register dev_t dev;
792 	register ino_t ino;
793 	struct stat *sbp, sb;
794 	int saved_errno;
795 
796 	/* If user needs stat info, stat buffer already allocated. */
797 	sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
798 
799 #ifdef FTS_WHITEOUT
800 	/* check for whiteout */
801 	if (p->fts_flags & FTS_ISW) {
802 		if (sbp != &sb) {
803 			memset(sbp, '\0', sizeof (*sbp));
804 			sbp->st_mode = S_IFWHT;
805 		}
806 		return (FTS_W);
807 	}
808 #endif
809 
810 	/*
811 	 * If doing a logical walk, or application requested FTS_FOLLOW, do
812 	 * a stat(2).  If that fails, check for a non-existent symlink.  If
813 	 * fail, set the errno from the stat call.
814 	 */
815 	if (ISSET(FTS_LOGICAL) || follow) {
816 		if (stat(p->fts_accpath, sbp)) {
817 			saved_errno = errno;
818 			if (!lstat(p->fts_accpath, sbp)) {
819 				errno = 0;
820 				return (FTS_SLNONE);
821 			}
822 			p->fts_errno = saved_errno;
823 			goto err;
824 		}
825 	} else if (lstat(p->fts_accpath, sbp)) {
826 		p->fts_errno = errno;
827 err:		memset(sbp, 0, sizeof(struct stat));
828 		return (FTS_NS);
829 	}
830 
831 	if (S_ISDIR(sbp->st_mode)) {
832 		/*
833 		 * Set the device/inode.  Used to find cycles and check for
834 		 * crossing mount points.  Also remember the link count, used
835 		 * in fts_build to limit the number of stat calls.  It is
836 		 * understood that these fields are only referenced if fts_info
837 		 * is set to FTS_D.
838 		 */
839 		dev = p->fts_dev = sbp->st_dev;
840 		ino = p->fts_ino = sbp->st_ino;
841 		p->fts_nlink = sbp->st_nlink;
842 
843 		if (ISDOT(p->fts_name))
844 			return (FTS_DOT);
845 
846 		/*
847 		 * Cycle detection is done by brute force when the directory
848 		 * is first encountered.  If the tree gets deep enough or the
849 		 * number of symbolic links to directories is high enough,
850 		 * something faster might be worthwhile.
851 		 */
852 		for (t = p->fts_parent;
853 		    t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
854 			if (ino == t->fts_ino && dev == t->fts_dev) {
855 				p->fts_cycle = t;
856 				return (FTS_DC);
857 			}
858 		return (FTS_D);
859 	}
860 	if (S_ISLNK(sbp->st_mode))
861 		return (FTS_SL);
862 	if (S_ISREG(sbp->st_mode))
863 		return (FTS_F);
864 	return (FTS_DEFAULT);
865 }
866 
867 static FTSENT *
868 fts_sort(sp, head, nitems)
869 	FTS *sp;
870 	FTSENT *head;
871 	register int nitems;
872 {
873 	register FTSENT **ap, *p;
874 
875 	/*
876 	 * Construct an array of pointers to the structures and call qsort(3).
877 	 * Reassemble the array in the order returned by qsort.  If unable to
878 	 * sort for memory reasons, return the directory entries in their
879 	 * current order.  Allocate enough space for the current needs plus
880 	 * 40 so don't realloc one entry at a time.
881 	 */
882 	if (nitems > sp->fts_nitems) {
883 		sp->fts_nitems = nitems + 40;
884 		if ((sp->fts_array = reallocf(sp->fts_array,
885 		    (size_t)(sp->fts_nitems * sizeof(FTSENT *)))) == NULL) {
886 			sp->fts_nitems = 0;
887 			return (head);
888 		}
889 	}
890 	for (ap = sp->fts_array, p = head; p; p = p->fts_link)
891 		*ap++ = p;
892 	qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
893 	for (head = *(ap = sp->fts_array); --nitems; ++ap)
894 		ap[0]->fts_link = ap[1];
895 	ap[0]->fts_link = NULL;
896 	return (head);
897 }
898 
899 static FTSENT *
900 fts_alloc(sp, name, namelen)
901 	FTS *sp;
902 	char *name;
903 	register int namelen;
904 {
905 	register FTSENT *p;
906 	size_t len;
907 
908 	/*
909 	 * The file name is a variable length array and no stat structure is
910 	 * necessary if the user has set the nostat bit.  Allocate the FTSENT
911 	 * structure, the file name and the stat structure in one chunk, but
912 	 * be careful that the stat structure is reasonably aligned.  Since the
913 	 * fts_name field is declared to be of size 1, the fts_name pointer is
914 	 * namelen + 2 before the first possible address of the stat structure.
915 	 */
916 	len = sizeof(FTSENT) + namelen;
917 	if (!ISSET(FTS_NOSTAT))
918 		len += sizeof(struct stat) + ALIGNBYTES;
919 	if ((p = malloc(len)) == NULL)
920 		return (NULL);
921 
922 	/* Copy the name plus the trailing NULL. */
923 	memmove(p->fts_name, name, namelen + 1);
924 
925 	if (!ISSET(FTS_NOSTAT))
926 		p->fts_statp = (struct stat *)ALIGN(p->fts_name + namelen + 2);
927 	p->fts_namelen = namelen;
928 	p->fts_path = sp->fts_path;
929 	p->fts_errno = 0;
930 	p->fts_flags = 0;
931 	p->fts_instr = FTS_NOINSTR;
932 	p->fts_number = 0;
933 	p->fts_pointer = NULL;
934 	return (p);
935 }
936 
937 static void
938 fts_lfree(head)
939 	register FTSENT *head;
940 {
941 	register FTSENT *p;
942 
943 	/* Free a linked list of structures. */
944 	while ((p = head)) {
945 		head = head->fts_link;
946 		free(p);
947 	}
948 }
949 
950 /*
951  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
952  * Most systems will allow creation of paths much longer than MAXPATHLEN, even
953  * though the kernel won't resolve them.  Add the size (not just what's needed)
954  * plus 256 bytes so don't realloc the path 2 bytes at a time.
955  */
956 static int
957 fts_palloc(sp, more)
958 	FTS *sp;
959 	size_t more;
960 {
961 	sp->fts_pathlen += more + 256;
962 	sp->fts_path = reallocf(sp->fts_path, (size_t)sp->fts_pathlen);
963 	return (sp->fts_path == NULL);
964 }
965 
966 /*
967  * When the path is realloc'd, have to fix all of the pointers in structures
968  * already returned.
969  */
970 static void
971 fts_padjust(sp, addr)
972 	FTS *sp;
973 	void *addr;
974 {
975 	FTSENT *p;
976 
977 #define	ADJUST(p) {							\
978 	(p)->fts_accpath =						\
979 	    (char *)addr + ((p)->fts_accpath - (p)->fts_path);		\
980 	(p)->fts_path = addr;						\
981 }
982 	/* Adjust the current set of children. */
983 	for (p = sp->fts_child; p; p = p->fts_link)
984 		ADJUST(p);
985 
986 	/* Adjust the rest of the tree. */
987 	for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
988 		ADJUST(p);
989 		p = p->fts_link ? p->fts_link : p->fts_parent;
990 	}
991 }
992 
993 static size_t
994 fts_maxarglen(argv)
995 	char * const *argv;
996 {
997 	size_t len, max;
998 
999 	for (max = 0; *argv; ++argv)
1000 		if ((len = strlen(*argv)) > max)
1001 			max = len;
1002 	return (max);
1003 }
1004 
1005 /*
1006  * Change to dir specified by fd or p->fts_accpath without getting
1007  * tricked by someone changing the world out from underneath us.
1008  * Assumes p->fts_dev and p->fts_ino are filled in.
1009  */
1010 static int
1011 fts_safe_changedir(sp, p, fd)
1012 	FTS *sp;
1013 	FTSENT *p;
1014 	int fd;
1015 {
1016 	int ret, oerrno, newfd;
1017 	struct stat sb;
1018 
1019 	newfd = fd;
1020 	if (ISSET(FTS_NOCHDIR))
1021 		return (0);
1022 	if (fd < 0 && (newfd = open(p->fts_accpath, O_RDONLY, 0)) < 0)
1023 		return (-1);
1024 	if (fstat(newfd, &sb)) {
1025 		ret = -1;
1026 		goto bail;
1027 	}
1028 	if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {
1029 		errno = ENOENT;		/* disinformation */
1030 		ret = -1;
1031 		goto bail;
1032 	}
1033 	ret = fchdir(newfd);
1034 bail:
1035 	oerrno = errno;
1036 	if (fd < 0)
1037 		(void)close(newfd);
1038 	errno = oerrno;
1039 	return (ret);
1040 }
1041