1#include "config.h"
2
3#if HAVE_FTS
4
5int dummy;
6
7#else
8
9/*	$Id: compat_fts.c,v 1.14 2017/02/18 12:24:24 schwarze Exp $	*/
10/*	$OpenBSD: fts.c,v 1.56 2016/09/21 04:38:56 guenther Exp $	*/
11
12/*-
13 * Copyright (c) 1990, 1993, 1994
14 *	The Regents of the University of California.  All rights reserved.
15 *
16 * Redistribution and use in source and binary forms, with or without
17 * modification, are permitted provided that the following conditions
18 * are met:
19 * 1. Redistributions of source code must retain the above copyright
20 *    notice, this list of conditions and the following disclaimer.
21 * 2. Redistributions in binary form must reproduce the above copyright
22 *    notice, this list of conditions and the following disclaimer in the
23 *    documentation and/or other materials provided with the distribution.
24 * 3. Neither the name of the University nor the names of its contributors
25 *    may be used to endorse or promote products derived from this software
26 *    without specific prior written permission.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
29 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 * SUCH DAMAGE.
39 */
40
41#include <sys/stat.h>
42#include <sys/types.h>
43
44#include <dirent.h>
45#include <errno.h>
46#include <fcntl.h>
47#include <limits.h>
48#include <stdlib.h>
49#include <string.h>
50#include <unistd.h>
51#include "compat_fts.h"
52
53#define MAXIMUM(a, b)	(((a) > (b)) ? (a) : (b))
54
55static FTSENT	*fts_alloc(FTS *, const char *, size_t);
56static FTSENT	*fts_build(FTS *);
57static void	 fts_lfree(FTSENT *);
58static void	 fts_load(FTS *, FTSENT *);
59static size_t	 fts_maxarglen(char * const *);
60static void	 fts_padjust(FTS *, FTSENT *);
61static int	 fts_palloc(FTS *, size_t);
62static FTSENT	*fts_sort(FTS *, FTSENT *, int);
63static unsigned short	 fts_stat(FTS *, FTSENT *);
64
65#define	ISDOT(a)	(a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
66#ifndef	O_CLOEXEC
67#define	O_CLOEXEC	0
68#endif
69
70#define	CLR(opt)	(sp->fts_options &= ~(opt))
71#define	ISSET(opt)	(sp->fts_options & (opt))
72#define	SET(opt)	(sp->fts_options |= (opt))
73
74FTS *
75fts_open(char * const *argv, int options,
76    int (*compar)(const FTSENT **, const FTSENT **))
77{
78	FTS *sp;
79	FTSENT *p, *root;
80	int nitems;
81	FTSENT *parent, *prev;
82
83	/* Options check. */
84	if (options & ~FTS_OPTIONMASK) {
85		errno = EINVAL;
86		return (NULL);
87	}
88
89	/* At least one path must be specified. */
90	if (*argv == NULL) {
91		errno = EINVAL;
92		return (NULL);
93	}
94
95	/* Allocate/initialize the stream */
96	if ((sp = calloc(1, sizeof(FTS))) == NULL)
97		return (NULL);
98	sp->fts_compar = compar;
99	sp->fts_options = options;
100
101	/*
102	 * Start out with 1K of path space, and enough, in any case,
103	 * to hold the user's paths.
104	 */
105	if (fts_palloc(sp, MAXIMUM(fts_maxarglen(argv), PATH_MAX)))
106		goto mem1;
107
108	/* Allocate/initialize root's parent. */
109	if ((parent = fts_alloc(sp, "", 0)) == NULL)
110		goto mem2;
111	parent->fts_level = FTS_ROOTPARENTLEVEL;
112
113	/* Allocate/initialize root(s). */
114	for (root = prev = NULL, nitems = 0; *argv; ++argv, ++nitems) {
115		if ((p = fts_alloc(sp, *argv, strlen(*argv))) == NULL)
116			goto mem3;
117		p->fts_level = FTS_ROOTLEVEL;
118		p->fts_parent = parent;
119		p->fts_accpath = p->fts_name;
120		p->fts_info = fts_stat(sp, p);
121
122		/* Command-line "." and ".." are real directories. */
123		if (p->fts_info == FTS_DOT)
124			p->fts_info = FTS_D;
125
126		/*
127		 * If comparison routine supplied, traverse in sorted
128		 * order; otherwise traverse in the order specified.
129		 */
130		if (compar) {
131			p->fts_link = root;
132			root = p;
133		} else {
134			p->fts_link = NULL;
135			if (root == NULL)
136				root = p;
137			else
138				prev->fts_link = p;
139			prev = p;
140		}
141	}
142	if (compar && nitems > 1)
143		root = fts_sort(sp, root, nitems);
144
145	/*
146	 * Allocate a dummy pointer and make fts_read think that we've just
147	 * finished the node before the root(s); set p->fts_info to FTS_INIT
148	 * so that everything about the "current" node is ignored.
149	 */
150	if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
151		goto mem3;
152	sp->fts_cur->fts_link = root;
153	sp->fts_cur->fts_info = FTS_INIT;
154
155	if (nitems == 0)
156		free(parent);
157
158	return (sp);
159
160mem3:	fts_lfree(root);
161	free(parent);
162mem2:	free(sp->fts_path);
163mem1:	free(sp);
164	return (NULL);
165}
166
167static void
168fts_load(FTS *sp, FTSENT *p)
169{
170	size_t len;
171	char *cp;
172
173	/*
174	 * Load the stream structure for the next traversal.  Since we don't
175	 * actually enter the directory until after the preorder visit, set
176	 * the fts_accpath field specially so the chdir gets done to the right
177	 * place and the user can access the first node.  From fts_open it's
178	 * known that the path will fit.
179	 */
180	len = p->fts_pathlen = p->fts_namelen;
181	memmove(sp->fts_path, p->fts_name, len + 1);
182	if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
183		len = strlen(++cp);
184		memmove(p->fts_name, cp, len + 1);
185		p->fts_namelen = len;
186	}
187	p->fts_accpath = p->fts_path = sp->fts_path;
188	sp->fts_dev = p->fts_dev;
189}
190
191int
192fts_close(FTS *sp)
193{
194	FTSENT *freep, *p;
195
196	/*
197	 * This still works if we haven't read anything -- the dummy structure
198	 * points to the root list, so we step through to the end of the root
199	 * list which has a valid parent pointer.
200	 */
201	if (sp->fts_cur) {
202		for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
203			freep = p;
204			p = p->fts_link ? p->fts_link : p->fts_parent;
205			free(freep);
206		}
207		free(p);
208	}
209
210	/* Free up child linked list, sort array, path buffer, stream ptr.*/
211	if (sp->fts_child)
212		fts_lfree(sp->fts_child);
213	free(sp->fts_array);
214	free(sp->fts_path);
215	free(sp);
216
217	return (0);
218}
219
220/*
221 * Special case of "/" at the end of the path so that slashes aren't
222 * appended which would cause paths to be written as "....//foo".
223 */
224#define	NAPPEND(p)							\
225	(p->fts_path[p->fts_pathlen - 1] == '/'				\
226	    ? p->fts_pathlen - 1 : p->fts_pathlen)
227
228FTSENT *
229fts_read(FTS *sp)
230{
231	FTSENT *p, *tmp;
232	int instr;
233	char *t;
234
235	/* If finished or unrecoverable error, return NULL. */
236	if (sp->fts_cur == NULL || ISSET(FTS_STOP))
237		return (NULL);
238
239	/* Set current node pointer. */
240	p = sp->fts_cur;
241
242	/* Save and zero out user instructions. */
243	instr = p->fts_instr;
244	p->fts_instr = FTS_NOINSTR;
245
246	/* Directory in pre-order. */
247	if (p->fts_info == FTS_D) {
248		/* If skipped or crossed mount point, do post-order visit. */
249		if (instr == FTS_SKIP ||
250		    (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
251			if (sp->fts_child) {
252				fts_lfree(sp->fts_child);
253				sp->fts_child = NULL;
254			}
255			p->fts_info = FTS_DP;
256			return (p);
257		}
258
259		/*
260		 * If haven't read do so.  If the read fails, fts_build sets
261		 * FTS_STOP or the fts_info field of the node.
262		 */
263		if (sp->fts_child) {
264			/* nothing */
265		} else if ((sp->fts_child = fts_build(sp)) == NULL) {
266			if (ISSET(FTS_STOP))
267				return (NULL);
268			return (p);
269		}
270		p = sp->fts_child;
271		sp->fts_child = NULL;
272		goto name;
273	}
274
275	/* Move to the next node on this level. */
276next:	tmp = p;
277	if ((p = p->fts_link)) {
278		free(tmp);
279
280		/*
281		 * If reached the top, return to the original directory (or
282		 * the root of the tree), and load the paths for the next root.
283		 */
284		if (p->fts_level == FTS_ROOTLEVEL) {
285			fts_load(sp, p);
286			return (sp->fts_cur = p);
287		}
288
289		/*
290		 * User may have called fts_set on the node.  If skipped,
291		 * ignore.  If followed, get a file descriptor so we can
292		 * get back if necessary.
293		 */
294		if (p->fts_instr == FTS_SKIP)
295			goto next;
296
297name:		t = sp->fts_path + NAPPEND(p->fts_parent);
298		*t++ = '/';
299		memmove(t, p->fts_name, p->fts_namelen + 1);
300		return (sp->fts_cur = p);
301	}
302
303	/* Move up to the parent node. */
304	p = tmp->fts_parent;
305	free(tmp);
306
307	if (p->fts_level == FTS_ROOTPARENTLEVEL) {
308		/*
309		 * Done; free everything up and set errno to 0 so the user
310		 * can distinguish between error and EOF.
311		 */
312		free(p);
313		errno = 0;
314		return (sp->fts_cur = NULL);
315	}
316
317	/* NUL terminate the pathname. */
318	sp->fts_path[p->fts_pathlen] = '\0';
319
320	p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
321	return (sp->fts_cur = p);
322}
323
324/*
325 * Fts_set takes the stream as an argument although it's not used in this
326 * implementation; it would be necessary if anyone wanted to add global
327 * semantics to fts using fts_set.  An error return is allowed for similar
328 * reasons.
329 */
330int
331fts_set(FTS *sp, FTSENT *p, int instr)
332{
333	if (instr && instr != FTS_NOINSTR && instr != FTS_SKIP) {
334		errno = EINVAL;
335		return (1);
336	}
337	p->fts_instr = instr;
338	return (0);
339}
340
341/*
342 * This is the tricky part -- do not casually change *anything* in here.  The
343 * idea is to build the linked list of entries that are used by fts_children
344 * and fts_read.  There are lots of special cases.
345 *
346 * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
347 * set and it's a physical walk (so that symbolic links can't be directories),
348 * we can do things quickly.  First, if it's a 4.4BSD file system, the type
349 * of the file is in the directory entry.  Otherwise, we assume that the number
350 * of subdirectories in a node is equal to the number of links to the parent.
351 * The former skips all stat calls.  The latter skips stat calls in any leaf
352 * directories and for any files after the subdirectories in the directory have
353 * been found, cutting the stat calls by about 2/3.
354 */
355static FTSENT *
356fts_build(FTS *sp)
357{
358	struct dirent *dp;
359	FTSENT *p, *head;
360	FTSENT *cur, *tail;
361	DIR *dirp;
362	void *oldaddr;
363	size_t dlen, len, maxlen;
364	int nitems, level, doadjust;
365	int saved_errno;
366	char *cp;
367
368	/* Set current node pointer. */
369	cur = sp->fts_cur;
370
371	/*
372	 * Open the directory for reading.  If this fails, we're done.
373	 * If being called from fts_read, set the fts_info field.
374	 */
375	if ((dirp = opendir(cur->fts_accpath)) == NULL) {
376		cur->fts_info = FTS_DNR;
377		cur->fts_errno = errno;
378		return (NULL);
379	}
380
381	/*
382	 * Figure out the max file name length that can be stored in the
383	 * current path -- the inner loop allocates more path as necessary.
384	 * We really wouldn't have to do the maxlen calculations here, we
385	 * could do them in fts_read before returning the path, but it's a
386	 * lot easier here since the length is part of the dirent structure.
387	 *
388	 * If not changing directories set a pointer so that can just append
389	 * each new name into the path.
390	 */
391	len = NAPPEND(cur);
392	cp = sp->fts_path + len;
393	*cp++ = '/';
394	len++;
395	maxlen = sp->fts_pathlen - len;
396
397	/*
398	 * fts_level is signed so we must prevent it from wrapping
399	 * around to FTS_ROOTLEVEL and FTS_ROOTPARENTLEVEL.
400	 */
401	level = cur->fts_level;
402	if (level < FTS_MAXLEVEL)
403	    level++;
404
405	/* Read the directory, attaching each entry to the `link' pointer. */
406	doadjust = 0;
407	for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
408		if (ISDOT(dp->d_name))
409			continue;
410
411#if HAVE_DIRENT_NAMLEN
412		dlen = dp->d_namlen;
413#else
414		dlen = strlen(dp->d_name);
415#endif
416
417		if (!(p = fts_alloc(sp, dp->d_name, dlen)))
418			goto mem1;
419		if (dlen >= maxlen) {	/* include space for NUL */
420			oldaddr = sp->fts_path;
421			if (fts_palloc(sp, dlen + len + 1)) {
422				/*
423				 * No more memory for path or structures.  Save
424				 * errno, free up the current structure and the
425				 * structures already allocated.
426				 */
427mem1:				saved_errno = errno;
428				free(p);
429				fts_lfree(head);
430				(void)closedir(dirp);
431				cur->fts_info = FTS_ERR;
432				SET(FTS_STOP);
433				errno = saved_errno;
434				return (NULL);
435			}
436			/* Did realloc() change the pointer? */
437			if (oldaddr != sp->fts_path) {
438				doadjust = 1;
439				cp = sp->fts_path + len;
440			}
441			maxlen = sp->fts_pathlen - len;
442		}
443
444		p->fts_level = level;
445		p->fts_parent = sp->fts_cur;
446		p->fts_pathlen = len + dlen;
447		if (p->fts_pathlen < len) {
448			/*
449			 * If we wrap, free up the current structure and
450			 * the structures already allocated, then error
451			 * out with ENAMETOOLONG.
452			 */
453			free(p);
454			fts_lfree(head);
455			(void)closedir(dirp);
456			cur->fts_info = FTS_ERR;
457			SET(FTS_STOP);
458			errno = ENAMETOOLONG;
459			return (NULL);
460		}
461
462		/* Build a file name for fts_stat to stat. */
463		p->fts_accpath = p->fts_path;
464		memmove(cp, p->fts_name, p->fts_namelen + 1);
465		/* Stat it. */
466		p->fts_info = fts_stat(sp, p);
467
468		/* We walk in directory order so "ls -f" doesn't get upset. */
469		p->fts_link = NULL;
470		if (head == NULL)
471			head = tail = p;
472		else {
473			tail->fts_link = p;
474			tail = p;
475		}
476		++nitems;
477	}
478	if (dirp)
479		(void)closedir(dirp);
480
481	/*
482	 * If realloc() changed the address of the path, adjust the
483	 * addresses for the rest of the tree and the dir list.
484	 */
485	if (doadjust)
486		fts_padjust(sp, head);
487
488	/*
489	 * If not changing directories, reset the path back to original
490	 * state.
491	 */
492	if (len == sp->fts_pathlen || nitems == 0)
493		--cp;
494	*cp = '\0';
495
496	/* If didn't find anything, return NULL. */
497	if (!nitems) {
498		cur->fts_info = FTS_DP;
499		return (NULL);
500	}
501
502	/* Sort the entries. */
503	if (sp->fts_compar && nitems > 1)
504		head = fts_sort(sp, head, nitems);
505	return (head);
506}
507
508static unsigned short
509fts_stat(FTS *sp, FTSENT *p)
510{
511	FTSENT *t;
512	dev_t dev;
513	ino_t ino;
514	struct stat *sbp;
515
516	/* If user needs stat info, stat buffer already allocated. */
517	sbp = p->fts_statp;
518
519	if (lstat(p->fts_accpath, sbp)) {
520		p->fts_errno = errno;
521		memset(sbp, 0, sizeof(struct stat));
522		return (FTS_NS);
523	}
524
525	if (S_ISDIR(sbp->st_mode)) {
526		/*
527		 * Set the device/inode.  Used to find cycles and check for
528		 * crossing mount points.  Also remember the link count, used
529		 * in fts_build to limit the number of stat calls.  It is
530		 * understood that these fields are only referenced if fts_info
531		 * is set to FTS_D.
532		 */
533		dev = p->fts_dev = sbp->st_dev;
534		ino = p->fts_ino = sbp->st_ino;
535		p->fts_nlink = sbp->st_nlink;
536
537		if (ISDOT(p->fts_name))
538			return (FTS_DOT);
539
540		/*
541		 * Cycle detection is done by brute force when the directory
542		 * is first encountered.  If the tree gets deep enough or the
543		 * number of symbolic links to directories is high enough,
544		 * something faster might be worthwhile.
545		 */
546		for (t = p->fts_parent;
547		    t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
548			if (ino == t->fts_ino && dev == t->fts_dev) {
549				p->fts_cycle = t;
550				return (FTS_DC);
551			}
552		return (FTS_D);
553	}
554	if (S_ISLNK(sbp->st_mode))
555		return (FTS_SL);
556	if (S_ISREG(sbp->st_mode))
557		return (FTS_F);
558	return (FTS_DEFAULT);
559}
560
561static FTSENT *
562fts_sort(FTS *sp, FTSENT *head, int nitems)
563{
564	FTSENT **ap, *p;
565
566	/*
567	 * Construct an array of pointers to the structures and call qsort(3).
568	 * Reassemble the array in the order returned by qsort.  If unable to
569	 * sort for memory reasons, return the directory entries in their
570	 * current order.  Allocate enough space for the current needs plus
571	 * 40 so don't realloc one entry at a time.
572	 */
573	if (nitems > sp->fts_nitems) {
574		struct _ftsent **a;
575
576		sp->fts_nitems = nitems + 40;
577		if ((a = reallocarray(sp->fts_array,
578		    sp->fts_nitems, sizeof(FTSENT *))) == NULL) {
579			free(sp->fts_array);
580			sp->fts_array = NULL;
581			sp->fts_nitems = 0;
582			return (head);
583		}
584		sp->fts_array = a;
585	}
586	for (ap = sp->fts_array, p = head; p; p = p->fts_link)
587		*ap++ = p;
588	qsort(sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
589	for (head = *(ap = sp->fts_array); --nitems; ++ap)
590		ap[0]->fts_link = ap[1];
591	ap[0]->fts_link = NULL;
592	return (head);
593}
594
595static FTSENT *
596fts_alloc(FTS *sp, const char *name, size_t namelen)
597{
598	FTSENT *p;
599	size_t len;
600
601	len = sizeof(FTSENT) + namelen;
602	if ((p = calloc(1, len)) == NULL)
603		return (NULL);
604
605	p->fts_path = sp->fts_path;
606	p->fts_namelen = namelen;
607	p->fts_instr = FTS_NOINSTR;
608	p->fts_statp = malloc(sizeof(struct stat));
609	if (p->fts_statp == NULL) {
610		free(p);
611		return (NULL);
612	}
613	memcpy(p->fts_name, name, namelen);
614
615	return (p);
616}
617
618static void
619fts_lfree(FTSENT *head)
620{
621	FTSENT *p;
622
623	/* Free a linked list of structures. */
624	while ((p = head)) {
625		head = head->fts_link;
626		free(p);
627	}
628}
629
630/*
631 * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
632 * Most systems will allow creation of paths much longer than PATH_MAX, even
633 * though the kernel won't resolve them.  Add the size (not just what's needed)
634 * plus 256 bytes so don't realloc the path 2 bytes at a time.
635 */
636static int
637fts_palloc(FTS *sp, size_t more)
638{
639	char *p;
640
641	/*
642	 * Check for possible wraparound.
643	 */
644	more += 256;
645	if (sp->fts_pathlen + more < sp->fts_pathlen) {
646		free(sp->fts_path);
647		sp->fts_path = NULL;
648		errno = ENAMETOOLONG;
649		return (1);
650	}
651	sp->fts_pathlen += more;
652	p = realloc(sp->fts_path, sp->fts_pathlen);
653	if (p == NULL) {
654		free(sp->fts_path);
655		sp->fts_path = NULL;
656		return (1);
657	}
658	sp->fts_path = p;
659	return (0);
660}
661
662/*
663 * When the path is realloc'd, have to fix all of the pointers in structures
664 * already returned.
665 */
666static void
667fts_padjust(FTS *sp, FTSENT *head)
668{
669	FTSENT *p;
670	char *addr = sp->fts_path;
671
672#define	ADJUST(p) {							\
673	if ((p)->fts_accpath != (p)->fts_name) {			\
674		(p)->fts_accpath =					\
675		    (char *)addr + ((p)->fts_accpath - (p)->fts_path);	\
676	}								\
677	(p)->fts_path = addr;						\
678}
679	/* Adjust the current set of children. */
680	for (p = sp->fts_child; p; p = p->fts_link)
681		ADJUST(p);
682
683	/* Adjust the rest of the tree, including the current level. */
684	for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
685		ADJUST(p);
686		p = p->fts_link ? p->fts_link : p->fts_parent;
687	}
688}
689
690static size_t
691fts_maxarglen(char * const *argv)
692{
693	size_t len, max;
694
695	for (max = 0; *argv; ++argv)
696		if ((len = strlen(*argv)) > max)
697			max = len;
698	return (max + 1);
699}
700
701#endif
702