1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22/*
23 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
24 * Use is subject to license terms.
25 */
26
27/*	Copyright (c) 1988 AT&T	*/
28/*	  All Rights Reserved  	*/
29
30#pragma ident	"%Z%%M%	%I%	%E% SMI"
31
32/*
33 *	nftw - new file tree walk
34 *
35 *	int nftw(char *path, int (*fn)(), int depth, int flags);
36 *
37 *	Derived from System V ftw() by David Korn
38 *
39 *	nftw visits each file and directory in the tree starting at
40 *	path. It uses the generic directory reading library so it works
41 *	for any file system type.  The flags field is used to specify:
42 *		FTW_PHYS  Physical walk, does not follow symbolic links
43 *			  Otherwise, nftw will follow links but will not
44 *			  walk down any path the crosses itself.
45 *		FTW_MOUNT The walk will not cross a mount point.
46 *		FTW_DEPTH All subdirectories will be visited before the
47 *			  directory itself.
48 *		FTW_CHDIR The walk will change to each directory before
49 *			  reading it.  This is faster but core dumps
50 *			  may not get generated.
51 *
52 *	The following flags are private, and are used by the find
53 *	utility:
54 *		FTW_ANYERR Call the callback function and return
55 *			   FTW_NS on any stat failure, not just
56 *			   lack of permission.
57 *		FTW_HOPTION Use stat the first time the walk
58 *			    function is called, regardless of
59 *			    whether or not FTW_PHYS is specified.
60 *		FTW_NOLOOP Allow find utility to detect infinite loops created
61 *			   by both symbolic and hard linked directories.
62 *
63 *	fn is called with four arguments at each file and directory.
64 *	The first argument is the pathname of the object, the second
65 *	is a pointer to the stat buffer and the third is an integer
66 *	giving additional information as follows:
67 *
68 *		FTW_F	The object is a file.
69 *		FTW_D	The object is a directory.
70 *		FTW_DP	The object is a directory and subdirectories
71 *			have been visited.
72 *		FTW_SL	The object is a symbolic link.
73 *		FTW_SLN The object is a symbolic link pointing at a
74 *		        non-existing file.
75 *		FTW_DNR	The object is a directory that cannot be read.
76 *			fn will not be called for any of its descendants.
77 *		FTW_NS	Stat failed on the object because of lack of
78 *			appropriate permission. The stat buffer passed to fn
79 *			is undefined.  Stat failure for any reason is
80 *			considered an error and nftw will return -1.
81 *	The following value is private, and is used by the find utility:
82 *		FTW_DL	An infinite loop has been detected.
83 *	The fourth argument is a struct FTW* which contains the depth
84 *	and the offset into pathname to the base name.
85 *	If fn returns nonzero, nftw returns this value to its caller.
86 *
87 *	depth limits the number of open directories that ftw uses
88 *	before it starts recycling file descriptors.  In general,
89 *	a file descriptor is used for each level.  When FTW_CHDIR isn't set,
90 *	in order to descend to arbitrary depths, nftw requires 2 file
91 *	descriptors to be open during the call to openat(), therefore if
92 *	the depth argument is less than 2 nftw will not use openat(), and
93 *	it will fail with ENAMETOOLONG if it descends to a directory that
94 *	exceeds PATH_MAX.
95 *
96 */
97
98#include "lint.h"
99#include <mtlib.h>
100#include <sys/types.h>
101#include <sys/stat.h>
102#include <dirent.h>
103#include <errno.h>
104#include <limits.h>
105#include <ftw.h>
106#include <stdlib.h>
107#include <string.h>
108#include <unistd.h>
109#include <thread.h>
110#include <synch.h>
111#include <stdio.h>
112#include <strings.h>
113#include <fcntl.h>
114
115#if !defined(_LP64) && _FILE_OFFSET_BITS == 64
116#define	nftw	nftw64
117#define	stat	stat64
118#define	fstat	fstat64
119#define	fstatat	fstatat64
120#pragma weak _nftw64 = nftw64
121#else
122#pragma weak _nftw = nftw
123#endif /* !_LP64 && _FILE_OFFSET_BITS == 64 */
124
125#ifndef PATH_MAX
126#define	PATH_MAX	1023
127#endif
128
129/*
130 * Local variables (used to be static local).
131 * Putting them into a structure that is passed
132 * around makes nftw() MT-safe with no locking required.
133 */
134struct Save {
135	struct Save *last;
136	DIR	*fd;
137	char	*comp;
138	long	here;
139	dev_t	dev;
140	ino_t	inode;
141};
142
143struct Var {
144	char	*home;
145	size_t	len;
146	char	*fullpath;
147	char	*tmppath;
148	int	curflags;
149	dev_t	cur_mount;
150	struct FTW state;
151	int	walklevel;
152	int	(*statf)(const char *, struct stat *, struct Save *, int flags);
153	int	(*savedstatf)(const char *, struct stat *, struct Save *,
154	    int flags);
155	DIR	*(*opendirf)(const char *);
156};
157
158static int oldclose(struct Save *);
159static int cdlstat(const char *, struct stat *, struct Save *, int flags);
160static int cdstat(const char *, struct stat *, struct Save *, int flags);
161static int nocdlstat(const char *, struct stat *, struct Save *, int flags);
162static int nocdstat(const char *, struct stat *, struct Save *, int flags);
163static DIR *cdopendir(const char *);
164static DIR *nocdopendir(const char *);
165static const char *get_unrooted(const char *);
166
167/*
168 * This is the recursive walker.
169 */
170static int
171walk(char *component,
172    int (*fn)(const char *, const struct stat *, int, struct FTW *),
173    int depth, struct Save *last, struct Var *vp)
174{
175	struct stat statb;
176	char *p, *tmp;
177	int type;
178	char *comp;
179	struct dirent *dir;
180	char *q;
181	int rc = 0;
182	int val = -1;
183	int cdval = -1;
184	int oldbase;
185	int skip;
186	struct Save this;
187	size_t base_comp, base_component, base_this_comp, base_last_comp;
188	size_t base_fullpath, base_tmppath;
189
190	this.last = last;
191	this.fd = 0;
192	if ((vp->curflags & FTW_CHDIR) && last)
193		comp = last->comp;
194	else
195		comp = vp->tmppath;
196
197	if (vp->savedstatf == NULL)
198		vp->savedstatf = vp->statf;
199
200	if ((vp->walklevel++ == 0) && (vp->curflags & FTW_HOPTION)) {
201		if (((vp->curflags & FTW_CHDIR) == 0) && (depth >= 2)) {
202			vp->statf = nocdstat;
203		} else {
204			vp->statf = cdstat;
205		}
206	} else {
207		vp->statf = vp->savedstatf;
208	}
209
210	/*
211	 * Determine the type of the component.
212	 *
213	 * Note that if the component is a trigger mount, this
214	 * will cause it to load.
215	 */
216	if ((*vp->statf)(comp, &statb, last, _AT_TRIGGER) >= 0) {
217		if ((statb.st_mode & S_IFMT) == S_IFDIR) {
218			type = FTW_D;
219			if (depth <= 1)
220				(void) oldclose(last);
221			if ((this.fd = (*vp->opendirf)(comp)) == 0) {
222				if (errno == EMFILE && oldclose(last) &&
223				    (this.fd = (*vp->opendirf)(comp)) != 0) {
224					/*
225					 * If opendirf fails because there
226					 * are OPEN_MAX fd in the calling
227					 * process, and we close the oldest
228					 * fd, and another opendirf doesn't
229					 * fail, depth is set to 1.
230					 */
231					depth = 1;
232				} else {
233					type = FTW_DNR;
234					goto fail;
235				}
236			}
237		} else if ((statb.st_mode & S_IFMT) == S_IFLNK) {
238			type = FTW_SL;
239		} else {
240			type = FTW_F;
241		}
242	} else if ((vp->curflags & FTW_ANYERR) && errno != ENOENT) {
243		/*
244		 * If FTW_ANYERR is specified, then a stat error
245		 * other than ENOENT automatically results in
246		 * failure.  This allows the callback function
247		 * to properly handle ENAMETOOLONG and ELOOP and
248		 * things of that nature, that would be masked
249		 * by calling lstat before failing.
250		 */
251		type = FTW_NS;
252		goto fail;
253	} else {
254		/*
255		 * Statf has failed. If stat was used instead of lstat,
256		 * try using lstat. If lstat doesn't fail, "comp"
257		 * must be a symbolic link pointing to a non-existent
258		 * file. Such a symbolic link should be ignored.
259		 * Also check the file type, if possible, for symbolic
260		 * link.
261		 */
262		if (((vp->statf == cdstat) &&
263		    (cdlstat(comp, &statb, last, 0) >= 0) &&
264		    ((statb.st_mode & S_IFMT) == S_IFLNK)) ||
265		    ((vp->statf == nocdstat) &&
266		    (nocdlstat(comp, &statb, last, 0) >= 0) &&
267		    ((statb.st_mode & S_IFMT) == S_IFLNK))) {
268
269			/*
270			 * Ignore bad symbolic link, let "fn"
271			 * report it.
272			 */
273
274			errno = ENOENT;
275			type = FTW_SLN;
276		} else {
277			type = FTW_NS;
278	fail:
279			/*
280			 * if FTW_ANYERR is set in flags, we call
281			 * the user function with FTW_NS set, regardless
282			 * of the reason stat failed.
283			 */
284			if (!(vp->curflags & FTW_ANYERR))
285				if (errno != EACCES)
286					return (-1);
287		}
288	}
289
290	/*
291	 * If the walk is not supposed to cross a mount point,
292	 * and it did, get ready to return.
293	 */
294	if ((vp->curflags & FTW_MOUNT) && type != FTW_NS &&
295	    statb.st_dev != vp->cur_mount)
296		goto quit;
297	vp->state.quit = 0;
298
299	/*
300	 * If current component is not a directory, call user
301	 * specified function and get ready to return.
302	 */
303	if (type != FTW_D || (vp->curflags & FTW_DEPTH) == 0)
304		rc = (*fn)(vp->tmppath, &statb, type, &vp->state);
305	if (rc > 0)
306		val = rc;
307	skip = (vp->state.quit & FTW_SKD);
308	if (rc != 0 || type != FTW_D || (vp->state.quit & FTW_PRUNE))
309		goto quit;
310
311	if (vp->tmppath[0] != '\0' && component[-1] != '/')
312		*component++ = '/';
313	*component = 0;
314	if (vp->curflags & FTW_CHDIR) {
315		struct stat statb2;
316
317		/*
318		 * Security check (there is a window between
319		 * (*vp->statf)() and opendir() above).
320		 */
321		if ((vp->curflags & FTW_PHYS) &&
322		    (fstat(this.fd->dd_fd, &statb2) < 0 ||
323		    statb2.st_ino != statb.st_ino ||
324		    statb2.st_dev != statb.st_dev)) {
325			errno = EAGAIN;
326			rc = -1;
327			goto quit;
328		}
329
330		if ((cdval = fchdir(this.fd->dd_fd)) >= 0) {
331			this.comp = component;
332		} else {
333			type = FTW_DNR;
334			rc = (*fn)(vp->tmppath, &statb, type, &vp->state);
335			goto quit;
336		}
337	}
338
339	/*
340	 * If the walk has followed a symbolic link (FTW_PHYS is not set),
341	 * traverse the walk back to make sure there is not a loop.
342	 * The find utility (FTW_NOLOOP is set) detects infinite loops
343	 * in both symbolic and hard linked directories.
344	 */
345	if ((vp->curflags & FTW_NOLOOP) ||
346	    ((vp->curflags & FTW_PHYS) == 0)) {
347		struct Save *sp = last;
348		while (sp) {
349			/*
350			 * If the same node has already been visited, there
351			 * is a loop. Get ready to return.
352			 */
353			if (sp->dev == statb.st_dev &&
354			    sp->inode == statb.st_ino) {
355				if (vp->curflags & FTW_NOLOOP) {
356					/* private interface for find util */
357					type = FTW_DL;
358					goto fail;
359				}
360				goto quit;
361			}
362			sp = sp->last;
363		}
364	}
365	this.dev = statb.st_dev;
366	this.inode = statb.st_ino;
367	oldbase = vp->state.base;
368	vp->state.base = (int)(component - vp->tmppath);
369	while (dir = readdir(this.fd)) {
370		if (dir->d_ino == 0)
371			continue;
372		q = dir->d_name;
373		if (*q == '.') {
374			if (q[1] == 0)
375				continue;
376			else if (q[1] == '.' && q[2] == 0)
377				continue;
378		}
379		if (last != NULL && last->comp != NULL) {
380			base_last_comp = last->comp - vp->home;
381		}
382		base_comp = comp - vp->home;
383		base_component = component - vp->home;
384		if ((strlen(q) + strlen(vp->home) + 1) > vp->len) {
385			/*
386			 * When the space needed for vp->home has
387			 * exceeded the amount of space that has
388			 * been allocated, realloc() more space
389			 * and adjust pointers to point to the
390			 * (possibly moved) new block for vp->home
391			 */
392			base_this_comp = this.comp - vp->home;
393			base_fullpath = vp->fullpath - vp->home;
394			base_tmppath = vp->tmppath - vp->home;
395			vp->len *= 2;
396			tmp = (char *)realloc(vp->home, vp->len);
397			if (tmp == NULL) {
398				rc = -1;
399				goto quit;
400			}
401			vp->home = tmp;
402			comp = vp->home + base_comp;
403			component = vp->home + base_component;
404			this.comp = vp->home + base_this_comp;
405			vp->fullpath = vp->home + base_fullpath;
406			vp->tmppath = vp->home + base_tmppath;
407			if (last != NULL && last->comp != NULL) {
408				last->comp = vp->home + base_last_comp;
409			}
410		}
411		p = component;
412		while (*q != '\0')
413			*p++ = *q++;
414		*p = '\0';
415		vp->state.level++;
416
417		/* Call walk() recursively.  */
418		rc = walk(p, fn, depth-1, &this, vp);
419		if (last != NULL && last->comp != NULL) {
420			last->comp = vp->home + base_last_comp;
421		}
422		comp = vp->home + base_comp;
423		component = vp->home + base_component;
424		vp->state.level--;
425		if (this.fd == 0) {
426			*component = 0;
427			if (vp->curflags & FTW_CHDIR) {
428				this.fd = opendir(".");
429			} else {
430				this.fd = (*vp->opendirf)(comp);
431			}
432			if (this.fd == 0) {
433				rc = -1;
434				goto quit;
435			}
436			seekdir(this.fd, this.here);
437		}
438		if (rc != 0) {
439			if (errno == ENOENT) {
440				(void) fprintf(stderr, "cannot open %s: %s\n",
441				    vp->tmppath, strerror(errno));
442				val = rc;
443				continue;
444			}
445			goto quit;	/* this seems extreme */
446		}
447	}
448	vp->state.base = oldbase;
449	*--component = 0;
450	type = FTW_DP;
451	if ((vp->tmppath[0] != '\0') && (vp->curflags & FTW_DEPTH) && !skip)
452		rc = (*fn)(vp->tmppath, &statb, type, &vp->state);
453quit:
454	if (cdval >= 0 && last) {
455		/* try to change back to previous directory */
456		if (last->fd != NULL) {
457			if (fchdir(last->fd->dd_fd) < 0) {
458				rc = -1;
459			}
460		} else {
461			if ((cdval = chdir("..")) >= 0) {
462				if ((*vp->statf)(".", &statb, last, 0) < 0 ||
463				    statb.st_ino != last->inode ||
464				    statb.st_dev != last->dev)
465					cdval = -1;
466			}
467			*comp = 0;
468			if (cdval < 0) {
469				if (chdir(vp->fullpath) < 0) {
470					rc = -1;
471				} else {
472					/* Security check */
473					if ((vp->curflags & FTW_PHYS) &&
474					    ((*vp->statf)(".", &statb,
475					    last, 0) < 0 ||
476					    statb.st_ino != last->inode ||
477					    statb.st_dev != last->dev)) {
478						errno = EAGAIN;
479						rc = -1;
480					}
481				}
482			}
483		}
484	}
485
486	if (this.fd)
487		(void) closedir(this.fd);
488	if (val > rc)
489		return (val);
490	else
491		return (rc);
492}
493
494int
495nftw(const char *path,
496    int (*fn)(const char *, const struct stat *, int, struct FTW *),
497    int depth, int flags)
498{
499	struct Var var;
500	struct stat statb;
501	int rc = -1;
502	char *dp;
503	char *base;
504	char *endhome;
505	const char *savepath = path;
506	int save_errno;
507
508	var.walklevel = 0;
509	var.len = 2*(PATH_MAX+1);
510	var.home = (char *)malloc(var.len);
511	if (var.home == NULL)
512		return (-1);
513
514	var.home[0] = 0;
515
516	/*
517	 * If the walk is going to change directory before
518	 * reading it, save current working directory.
519	 */
520	if (flags & FTW_CHDIR) {
521		if (getcwd(var.home, PATH_MAX+1) == 0) {
522			free(var.home);
523			return (-1);
524		}
525	}
526	endhome = dp = var.home + strlen(var.home);
527	if (*path == '/')
528		var.fullpath = dp;
529	else {
530		*dp++ = '/';
531		var.fullpath = var.home;
532	}
533	var.tmppath =  dp;
534	base = dp-1;
535	while (*path) {
536		*dp = *path;
537		if (*dp == '/')
538			base = dp;
539		dp++, path++;
540	}
541	*dp = 0;
542	var.state.base = (int)(base + 1 - var.tmppath);
543	if (*path) {
544		free(var.home);
545		errno = ENAMETOOLONG;
546		return (-1);
547	}
548	var.curflags = flags;
549
550	/*
551	 * If doing chdir()'s, set var.opendirf to cdopendir.
552	 * If not doing chdir()'s and if nftw()'s depth arg >= 2,
553	 * set var.opendirf to nocdopendir.  In order to
554	 * descend to arbitrary depths without doing chdir()'s, nftw()
555	 * requires a depth arg >= 2 so that nocdopendir() can use openat()
556	 * to traverse the directories.  So when not doing
557	 * chdir()'s if nftw()'s depth arg <= 1, set var.opendirf to
558	 * cdopendir.
559	 * If doing a physical walk (not following symbolic link), set
560	 * var.statf to cdlstat() or nocdlstat(). Otherwise, set var.statf
561	 * to cdstat() or nocdstat().
562	 */
563	if (((flags & FTW_CHDIR) == 0) && (depth >= 2)) {
564		var.opendirf = nocdopendir;
565		if (flags & FTW_PHYS)
566			var.statf = nocdlstat;
567		else
568			var.statf = nocdstat;
569	} else {
570		var.opendirf = cdopendir;
571		if (flags & FTW_PHYS)
572			var.statf = cdlstat;
573		else
574			var.statf = cdstat;
575	}
576
577	/*
578	 * If walk is not going to cross a mount point,
579	 * save the current mount point.
580	 */
581	if (flags & FTW_MOUNT) {
582		if ((*var.statf)(savepath, &statb, NULL, 0) >= 0)
583			var.cur_mount = statb.st_dev;
584		else
585			goto done;
586	}
587	var.state.level = 0;
588
589	/*
590	 * Call walk() which does most of the work.
591	 * walk() uses errno in a rather obtuse way
592	 * so we shield any incoming errno.
593	 */
594	save_errno = errno;
595	errno = 0;
596	var.savedstatf = NULL;
597	rc = walk(dp, fn, depth, (struct Save *)0, &var);
598	if (errno == 0)
599		errno = save_errno;
600done:
601	*endhome = 0;
602	if (flags & FTW_CHDIR)
603		(void) chdir(var.home);
604	free(var.home);
605	return (rc);
606}
607
608/*
609 * Get stat info on path when FTW_CHDIR is set.
610 */
611/*ARGSUSED1*/
612static int
613cdstat(const char *path, struct stat *statp, struct Save *lp, int flags)
614{
615	return (fstatat(AT_FDCWD, path, statp, flags));
616}
617
618/*
619 * Get lstat info on path when FTW_CHDIR is set.
620 */
621/*ARGSUSED1*/
622static int
623cdlstat(const char *path, struct stat *statp, struct Save *lp, int flags)
624{
625	return (fstatat(AT_FDCWD, path, statp,
626	    flags | AT_SYMLINK_NOFOLLOW));
627}
628
629/*
630 * Get stat info on path when FTW_CHDIR is not set.
631 */
632static int
633nocdstat(const char *path, struct stat *statp, struct Save *lp, int flags)
634{
635	int		fd;
636	const char	*basepath;
637
638	if (lp && lp->fd) {
639		/* get basename of path */
640		basepath = get_unrooted(path);
641
642		fd = lp->fd->dd_fd;
643	} else {
644		basepath = path;
645
646		fd = AT_FDCWD;
647	}
648
649	return (fstatat(fd, basepath, statp, flags));
650}
651
652/*
653 * Get lstat info on path when FTW_CHDIR is not set.
654 */
655static int
656nocdlstat(const char *path, struct stat *statp, struct Save *lp, int flags)
657{
658	int		fd;
659	const char	*basepath;
660
661	if (lp && lp->fd) {
662		/* get basename of path */
663		basepath = get_unrooted(path);
664
665		fd = lp->fd->dd_fd;
666	} else {
667		basepath = path;
668
669		fd = AT_FDCWD;
670	}
671
672	return (fstatat(fd, basepath, statp, flags | AT_SYMLINK_NOFOLLOW));
673}
674
675/*
676 * Open path directory when FTW_CHDIR is set.
677 *
678 */
679static DIR *
680cdopendir(const char *path)
681{
682	return (opendir(path));
683}
684
685/*
686 * Open path directory when FTW_CHDIR is not set.
687 */
688static DIR *
689nocdopendir(const char *path)
690{
691	int fd, cfd;
692	DIR *fdd;
693	char *dirp, *token, *ptr;
694
695	if (((fdd = opendir(path)) == NULL) && (errno == ENAMETOOLONG)) {
696		if ((dirp = strdup(path)) == NULL) {
697			errno = ENAMETOOLONG;
698			return (NULL);
699		}
700		if ((token = strtok_r(dirp, "/", &ptr)) != NULL) {
701			if ((fd = openat(AT_FDCWD, dirp, O_RDONLY)) < 0) {
702				(void) free(dirp);
703				errno = ENAMETOOLONG;
704				return (NULL);
705			}
706			while ((token = strtok_r(NULL, "/", &ptr)) != NULL) {
707				if ((cfd = openat(fd, token, O_RDONLY)) < 0) {
708					(void) close(fd);
709					(void) free(dirp);
710					errno = ENAMETOOLONG;
711					return (NULL);
712				}
713				(void) close(fd);
714				fd = cfd;
715			}
716			(void) free(dirp);
717			return (fdopendir(fd));
718		}
719		(void) free(dirp);
720		errno = ENAMETOOLONG;
721	}
722	return (fdd);
723}
724
725/*
726 * return pointer basename of path, which may contain trailing slashes
727 *
728 * We do this when we do not chdir() on the input.
729 */
730static const char *
731get_unrooted(const char *path)
732{
733	const char *ptr;
734
735	if (!path || !*path)
736		return (NULL);
737
738	ptr = path + strlen(path);
739	/* find last char in path before any trailing slashes */
740	while (ptr != path && *--ptr == '/')
741		;
742
743	if (ptr == path)	/* all slashes */
744		return (ptr);
745
746	while (ptr != path)
747		if (*--ptr == '/')
748			return (++ptr);
749
750	return (ptr);
751}
752
753/*
754 * close the oldest directory.  It saves the seek offset.
755 * return value is 0 unless it was unable to close any descriptor
756 */
757
758static int
759oldclose(struct Save *sp)
760{
761	struct Save *spnext;
762	while (sp) {
763		spnext = sp->last;
764		if (spnext == 0 || spnext->fd == 0)
765			break;
766		sp = spnext;
767	}
768	if (sp == 0 || sp->fd == 0)
769		return (0);
770	sp->here = telldir(sp->fd);
771	(void) closedir(sp->fd);
772	sp->fd = 0;
773	return (1);
774}
775