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