/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*	Copyright (c) 1988 AT&T	*/
/*	  All Rights Reserved  	*/

#pragma ident	"%Z%%M%	%I%	%E% SMI"

/*
 *	nftw - new file tree walk
 *
 *	int nftw(char *path, int (*fn)(), int depth, int flags);
 *
 *	Derived from System V ftw() by David Korn
 *
 *	nftw visits each file and directory in the tree starting at
 *	path. It uses the generic directory reading library so it works
 *	for any file system type.  The flags field is used to specify:
 *		FTW_PHYS  Physical walk, does not follow symbolic links
 *			  Otherwise, nftw will follow links but will not
 *			  walk down any path the crosses itself.
 *		FTW_MOUNT The walk will not cross a mount point.
 *		FTW_DEPTH All subdirectories will be visited before the
 *			  directory itself.
 *		FTW_CHDIR The walk will change to each directory before
 *			  reading it.  This is faster but core dumps
 *			  may not get generated.
 *
 *	The following flags are private, and are used by the find
 *	utility:
 *		FTW_ANYERR Call the callback function and return
 *			   FTW_NS on any stat failure, not just
 *			   lack of permission.
 *		FTW_HOPTION Use stat the first time the walk
 *			    function is called, regardless of
 *			    whether or not FTW_PHYS is specified.
 *		FTW_NOLOOP Allow find utility to detect infinite loops created
 *			   by both symbolic and hard linked directories.
 *
 *	fn is called with four arguments at each file and directory.
 *	The first argument is the pathname of the object, the second
 *	is a pointer to the stat buffer and the third is an integer
 *	giving additional information as follows:
 *
 *		FTW_F	The object is a file.
 *		FTW_D	The object is a directory.
 *		FTW_DP	The object is a directory and subdirectories
 *			have been visited.
 *		FTW_SL	The object is a symbolic link.
 *		FTW_SLN The object is a symbolic link pointing at a
 *		        non-existing file.
 *		FTW_DNR	The object is a directory that cannot be read.
 *			fn will not be called for any of its descendants.
 *		FTW_NS	Stat failed on the object because of lack of
 *			appropriate permission. The stat buffer passed to fn
 *			is undefined.  Stat failure for any reason is
 *			considered an error and nftw will return -1.
 *	The following value is private, and is used by the find utility:
 *		FTW_DL	An infinite loop has been detected.
 *	The fourth argument is a struct FTW* which contains the depth
 *	and the offset into pathname to the base name.
 *	If fn returns nonzero, nftw returns this value to its caller.
 *
 *	depth limits the number of open directories that ftw uses
 *	before it starts recycling file descriptors.  In general,
 *	a file descriptor is used for each level.  When FTW_CHDIR isn't set,
 *	in order to descend to arbitrary depths, nftw requires 2 file
 *	descriptors to be open during the call to openat(), therefore if
 *	the depth argument is less than 2 nftw will not use openat(), and
 *	it will fail with ENAMETOOLONG if it descends to a directory that
 *	exceeds PATH_MAX.
 *
 */

#include "lint.h"
#include <mtlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>
#include <errno.h>
#include <limits.h>
#include <ftw.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <thread.h>
#include <synch.h>
#include <stdio.h>
#include <strings.h>
#include <fcntl.h>

#if !defined(_LP64) && _FILE_OFFSET_BITS == 64
#define	nftw	nftw64
#define	stat	stat64
#define	fstat	fstat64
#define	fstatat	fstatat64
#pragma weak _nftw64 = nftw64
#else
#pragma weak _nftw = nftw
#endif /* !_LP64 && _FILE_OFFSET_BITS == 64 */

#ifndef PATH_MAX
#define	PATH_MAX	1023
#endif

/*
 * Local variables (used to be static local).
 * Putting them into a structure that is passed
 * around makes nftw() MT-safe with no locking required.
 */
struct Save {
	struct Save *last;
	DIR	*fd;
	char	*comp;
	long	here;
	dev_t	dev;
	ino_t	inode;
};

struct Var {
	char	*home;
	size_t	len;
	char	*fullpath;
	char	*tmppath;
	int	curflags;
	dev_t	cur_mount;
	struct FTW state;
	int	walklevel;
	int	(*statf)(const char *, struct stat *, struct Save *, int flags);
	int	(*savedstatf)(const char *, struct stat *, struct Save *,
	    int flags);
	DIR	*(*opendirf)(const char *);
};

static int oldclose(struct Save *);
static int cdlstat(const char *, struct stat *, struct Save *, int flags);
static int cdstat(const char *, struct stat *, struct Save *, int flags);
static int nocdlstat(const char *, struct stat *, struct Save *, int flags);
static int nocdstat(const char *, struct stat *, struct Save *, int flags);
static DIR *cdopendir(const char *);
static DIR *nocdopendir(const char *);
static const char *get_unrooted(const char *);

/*
 * This is the recursive walker.
 */
static int
walk(char *component,
    int (*fn)(const char *, const struct stat *, int, struct FTW *),
    int depth, struct Save *last, struct Var *vp)
{
	struct stat statb;
	char *p, *tmp;
	int type;
	char *comp;
	struct dirent *dir;
	char *q;
	int rc = 0;
	int val = -1;
	int cdval = -1;
	int oldbase;
	int skip;
	struct Save this;
	size_t base_comp, base_component, base_this_comp, base_last_comp;
	size_t base_fullpath, base_tmppath;

	this.last = last;
	this.fd = 0;
	if ((vp->curflags & FTW_CHDIR) && last)
		comp = last->comp;
	else
		comp = vp->tmppath;

	if (vp->savedstatf == NULL)
		vp->savedstatf = vp->statf;

	if ((vp->walklevel++ == 0) && (vp->curflags & FTW_HOPTION)) {
		if (((vp->curflags & FTW_CHDIR) == 0) && (depth >= 2)) {
			vp->statf = nocdstat;
		} else {
			vp->statf = cdstat;
		}
	} else {
		vp->statf = vp->savedstatf;
	}

	/*
	 * Determine the type of the component.
	 *
	 * Note that if the component is a trigger mount, this
	 * will cause it to load.
	 */
	if ((*vp->statf)(comp, &statb, last, _AT_TRIGGER) >= 0) {
		if ((statb.st_mode & S_IFMT) == S_IFDIR) {
			type = FTW_D;
			if (depth <= 1)
				(void) oldclose(last);
			if ((this.fd = (*vp->opendirf)(comp)) == 0) {
				if (errno == EMFILE && oldclose(last) &&
				    (this.fd = (*vp->opendirf)(comp)) != 0) {
					/*
					 * If opendirf fails because there
					 * are OPEN_MAX fd in the calling
					 * process, and we close the oldest
					 * fd, and another opendirf doesn't
					 * fail, depth is set to 1.
					 */
					depth = 1;
				} else {
					type = FTW_DNR;
					goto fail;
				}
			}
		} else if ((statb.st_mode & S_IFMT) == S_IFLNK) {
			type = FTW_SL;
		} else {
			type = FTW_F;
		}
	} else if ((vp->curflags & FTW_ANYERR) && errno != ENOENT) {
		/*
		 * If FTW_ANYERR is specified, then a stat error
		 * other than ENOENT automatically results in
		 * failure.  This allows the callback function
		 * to properly handle ENAMETOOLONG and ELOOP and
		 * things of that nature, that would be masked
		 * by calling lstat before failing.
		 */
		type = FTW_NS;
		goto fail;
	} else {
		/*
		 * Statf has failed. If stat was used instead of lstat,
		 * try using lstat. If lstat doesn't fail, "comp"
		 * must be a symbolic link pointing to a non-existent
		 * file. Such a symbolic link should be ignored.
		 * Also check the file type, if possible, for symbolic
		 * link.
		 */
		if (((vp->statf == cdstat) &&
		    (cdlstat(comp, &statb, last, 0) >= 0) &&
		    ((statb.st_mode & S_IFMT) == S_IFLNK)) ||
		    ((vp->statf == nocdstat) &&
		    (nocdlstat(comp, &statb, last, 0) >= 0) &&
		    ((statb.st_mode & S_IFMT) == S_IFLNK))) {

			/*
			 * Ignore bad symbolic link, let "fn"
			 * report it.
			 */

			errno = ENOENT;
			type = FTW_SLN;
		} else {
			type = FTW_NS;
	fail:
			/*
			 * if FTW_ANYERR is set in flags, we call
			 * the user function with FTW_NS set, regardless
			 * of the reason stat failed.
			 */
			if (!(vp->curflags & FTW_ANYERR))
				if (errno != EACCES)
					return (-1);
		}
	}

	/*
	 * If the walk is not supposed to cross a mount point,
	 * and it did, get ready to return.
	 */
	if ((vp->curflags & FTW_MOUNT) && type != FTW_NS &&
	    statb.st_dev != vp->cur_mount)
		goto quit;
	vp->state.quit = 0;

	/*
	 * If current component is not a directory, call user
	 * specified function and get ready to return.
	 */
	if (type != FTW_D || (vp->curflags & FTW_DEPTH) == 0)
		rc = (*fn)(vp->tmppath, &statb, type, &vp->state);
	if (rc > 0)
		val = rc;
	skip = (vp->state.quit & FTW_SKD);
	if (rc != 0 || type != FTW_D || (vp->state.quit & FTW_PRUNE))
		goto quit;

	if (vp->tmppath[0] != '\0' && component[-1] != '/')
		*component++ = '/';
	*component = 0;
	if (vp->curflags & FTW_CHDIR) {
		struct stat statb2;

		/*
		 * Security check (there is a window between
		 * (*vp->statf)() and opendir() above).
		 */
		if ((vp->curflags & FTW_PHYS) &&
		    (fstat(this.fd->dd_fd, &statb2) < 0 ||
		    statb2.st_ino != statb.st_ino ||
		    statb2.st_dev != statb.st_dev)) {
			errno = EAGAIN;
			rc = -1;
			goto quit;
		}

		if ((cdval = fchdir(this.fd->dd_fd)) >= 0) {
			this.comp = component;
		} else {
			type = FTW_DNR;
			rc = (*fn)(vp->tmppath, &statb, type, &vp->state);
			goto quit;
		}
	}

	/*
	 * If the walk has followed a symbolic link (FTW_PHYS is not set),
	 * traverse the walk back to make sure there is not a loop.
	 * The find utility (FTW_NOLOOP is set) detects infinite loops
	 * in both symbolic and hard linked directories.
	 */
	if ((vp->curflags & FTW_NOLOOP) ||
	    ((vp->curflags & FTW_PHYS) == 0)) {
		struct Save *sp = last;
		while (sp) {
			/*
			 * If the same node has already been visited, there
			 * is a loop. Get ready to return.
			 */
			if (sp->dev == statb.st_dev &&
			    sp->inode == statb.st_ino) {
				if (vp->curflags & FTW_NOLOOP) {
					/* private interface for find util */
					type = FTW_DL;
					goto fail;
				}
				goto quit;
			}
			sp = sp->last;
		}
	}
	this.dev = statb.st_dev;
	this.inode = statb.st_ino;
	oldbase = vp->state.base;
	vp->state.base = (int)(component - vp->tmppath);
	while (dir = readdir(this.fd)) {
		if (dir->d_ino == 0)
			continue;
		q = dir->d_name;
		if (*q == '.') {
			if (q[1] == 0)
				continue;
			else if (q[1] == '.' && q[2] == 0)
				continue;
		}
		if (last != NULL && last->comp != NULL) {
			base_last_comp = last->comp - vp->home;
		}
		base_comp = comp - vp->home;
		base_component = component - vp->home;
		if ((strlen(q) + strlen(vp->home) + 1) > vp->len) {
			/*
			 * When the space needed for vp->home has
			 * exceeded the amount of space that has
			 * been allocated, realloc() more space
			 * and adjust pointers to point to the
			 * (possibly moved) new block for vp->home
			 */
			base_this_comp = this.comp - vp->home;
			base_fullpath = vp->fullpath - vp->home;
			base_tmppath = vp->tmppath - vp->home;
			vp->len *= 2;
			tmp = (char *)realloc(vp->home, vp->len);
			if (tmp == NULL) {
				rc = -1;
				goto quit;
			}
			vp->home = tmp;
			comp = vp->home + base_comp;
			component = vp->home + base_component;
			this.comp = vp->home + base_this_comp;
			vp->fullpath = vp->home + base_fullpath;
			vp->tmppath = vp->home + base_tmppath;
			if (last != NULL && last->comp != NULL) {
				last->comp = vp->home + base_last_comp;
			}
		}
		p = component;
		while (*q != '\0')
			*p++ = *q++;
		*p = '\0';
		vp->state.level++;

		/* Call walk() recursively.  */
		rc = walk(p, fn, depth-1, &this, vp);
		if (last != NULL && last->comp != NULL) {
			last->comp = vp->home + base_last_comp;
		}
		comp = vp->home + base_comp;
		component = vp->home + base_component;
		vp->state.level--;
		if (this.fd == 0) {
			*component = 0;
			if (vp->curflags & FTW_CHDIR) {
				this.fd = opendir(".");
			} else {
				this.fd = (*vp->opendirf)(comp);
			}
			if (this.fd == 0) {
				rc = -1;
				goto quit;
			}
			seekdir(this.fd, this.here);
		}
		if (rc != 0) {
			if (errno == ENOENT) {
				(void) fprintf(stderr, "cannot open %s: %s\n",
				    vp->tmppath, strerror(errno));
				val = rc;
				continue;
			}
			goto quit;	/* this seems extreme */
		}
	}
	vp->state.base = oldbase;
	*--component = 0;
	type = FTW_DP;
	if ((vp->tmppath[0] != '\0') && (vp->curflags & FTW_DEPTH) && !skip)
		rc = (*fn)(vp->tmppath, &statb, type, &vp->state);
quit:
	if (cdval >= 0 && last) {
		/* try to change back to previous directory */
		if (last->fd != NULL) {
			if (fchdir(last->fd->dd_fd) < 0) {
				rc = -1;
			}
		} else {
			if ((cdval = chdir("..")) >= 0) {
				if ((*vp->statf)(".", &statb, last, 0) < 0 ||
				    statb.st_ino != last->inode ||
				    statb.st_dev != last->dev)
					cdval = -1;
			}
			*comp = 0;
			if (cdval < 0) {
				if (chdir(vp->fullpath) < 0) {
					rc = -1;
				} else {
					/* Security check */
					if ((vp->curflags & FTW_PHYS) &&
					    ((*vp->statf)(".", &statb,
					    last, 0) < 0 ||
					    statb.st_ino != last->inode ||
					    statb.st_dev != last->dev)) {
						errno = EAGAIN;
						rc = -1;
					}
				}
			}
		}
	}

	if (this.fd)
		(void) closedir(this.fd);
	if (val > rc)
		return (val);
	else
		return (rc);
}

int
nftw(const char *path,
    int (*fn)(const char *, const struct stat *, int, struct FTW *),
    int depth, int flags)
{
	struct Var var;
	struct stat statb;
	int rc = -1;
	char *dp;
	char *base;
	char *endhome;
	const char *savepath = path;
	int save_errno;

	var.walklevel = 0;
	var.len = 2*(PATH_MAX+1);
	var.home = (char *)malloc(var.len);
	if (var.home == NULL)
		return (-1);

	var.home[0] = 0;

	/*
	 * If the walk is going to change directory before
	 * reading it, save current working directory.
	 */
	if (flags & FTW_CHDIR) {
		if (getcwd(var.home, PATH_MAX+1) == 0) {
			free(var.home);
			return (-1);
		}
	}
	endhome = dp = var.home + strlen(var.home);
	if (*path == '/')
		var.fullpath = dp;
	else {
		*dp++ = '/';
		var.fullpath = var.home;
	}
	var.tmppath =  dp;
	base = dp-1;
	while (*path) {
		*dp = *path;
		if (*dp == '/')
			base = dp;
		dp++, path++;
	}
	*dp = 0;
	var.state.base = (int)(base + 1 - var.tmppath);
	if (*path) {
		free(var.home);
		errno = ENAMETOOLONG;
		return (-1);
	}
	var.curflags = flags;

	/*
	 * If doing chdir()'s, set var.opendirf to cdopendir.
	 * If not doing chdir()'s and if nftw()'s depth arg >= 2,
	 * set var.opendirf to nocdopendir.  In order to
	 * descend to arbitrary depths without doing chdir()'s, nftw()
	 * requires a depth arg >= 2 so that nocdopendir() can use openat()
	 * to traverse the directories.  So when not doing
	 * chdir()'s if nftw()'s depth arg <= 1, set var.opendirf to
	 * cdopendir.
	 * If doing a physical walk (not following symbolic link), set
	 * var.statf to cdlstat() or nocdlstat(). Otherwise, set var.statf
	 * to cdstat() or nocdstat().
	 */
	if (((flags & FTW_CHDIR) == 0) && (depth >= 2)) {
		var.opendirf = nocdopendir;
		if (flags & FTW_PHYS)
			var.statf = nocdlstat;
		else
			var.statf = nocdstat;
	} else {
		var.opendirf = cdopendir;
		if (flags & FTW_PHYS)
			var.statf = cdlstat;
		else
			var.statf = cdstat;
	}

	/*
	 * If walk is not going to cross a mount point,
	 * save the current mount point.
	 */
	if (flags & FTW_MOUNT) {
		if ((*var.statf)(savepath, &statb, NULL, 0) >= 0)
			var.cur_mount = statb.st_dev;
		else
			goto done;
	}
	var.state.level = 0;

	/*
	 * Call walk() which does most of the work.
	 * walk() uses errno in a rather obtuse way
	 * so we shield any incoming errno.
	 */
	save_errno = errno;
	errno = 0;
	var.savedstatf = NULL;
	rc = walk(dp, fn, depth, (struct Save *)0, &var);
	if (errno == 0)
		errno = save_errno;
done:
	*endhome = 0;
	if (flags & FTW_CHDIR)
		(void) chdir(var.home);
	free(var.home);
	return (rc);
}

/*
 * Get stat info on path when FTW_CHDIR is set.
 */
/*ARGSUSED1*/
static int
cdstat(const char *path, struct stat *statp, struct Save *lp, int flags)
{
	return (fstatat(AT_FDCWD, path, statp, flags));
}

/*
 * Get lstat info on path when FTW_CHDIR is set.
 */
/*ARGSUSED1*/
static int
cdlstat(const char *path, struct stat *statp, struct Save *lp, int flags)
{
	return (fstatat(AT_FDCWD, path, statp,
	    flags | AT_SYMLINK_NOFOLLOW));
}

/*
 * Get stat info on path when FTW_CHDIR is not set.
 */
static int
nocdstat(const char *path, struct stat *statp, struct Save *lp, int flags)
{
	int		fd;
	const char	*basepath;

	if (lp && lp->fd) {
		/* get basename of path */
		basepath = get_unrooted(path);

		fd = lp->fd->dd_fd;
	} else {
		basepath = path;

		fd = AT_FDCWD;
	}

	return (fstatat(fd, basepath, statp, flags));
}

/*
 * Get lstat info on path when FTW_CHDIR is not set.
 */
static int
nocdlstat(const char *path, struct stat *statp, struct Save *lp, int flags)
{
	int		fd;
	const char	*basepath;

	if (lp && lp->fd) {
		/* get basename of path */
		basepath = get_unrooted(path);

		fd = lp->fd->dd_fd;
	} else {
		basepath = path;

		fd = AT_FDCWD;
	}

	return (fstatat(fd, basepath, statp, flags | AT_SYMLINK_NOFOLLOW));
}

/*
 * Open path directory when FTW_CHDIR is set.
 *
 */
static DIR *
cdopendir(const char *path)
{
	return (opendir(path));
}

/*
 * Open path directory when FTW_CHDIR is not set.
 */
static DIR *
nocdopendir(const char *path)
{
	int fd, cfd;
	DIR *fdd;
	char *dirp, *token, *ptr;

	if (((fdd = opendir(path)) == NULL) && (errno == ENAMETOOLONG)) {
		if ((dirp = strdup(path)) == NULL) {
			errno = ENAMETOOLONG;
			return (NULL);
		}
		if ((token = strtok_r(dirp, "/", &ptr)) != NULL) {
			if ((fd = openat(AT_FDCWD, dirp, O_RDONLY)) < 0) {
				(void) free(dirp);
				errno = ENAMETOOLONG;
				return (NULL);
			}
			while ((token = strtok_r(NULL, "/", &ptr)) != NULL) {
				if ((cfd = openat(fd, token, O_RDONLY)) < 0) {
					(void) close(fd);
					(void) free(dirp);
					errno = ENAMETOOLONG;
					return (NULL);
				}
				(void) close(fd);
				fd = cfd;
			}
			(void) free(dirp);
			return (fdopendir(fd));
		}
		(void) free(dirp);
		errno = ENAMETOOLONG;
	}
	return (fdd);
}

/*
 * return pointer basename of path, which may contain trailing slashes
 *
 * We do this when we do not chdir() on the input.
 */
static const char *
get_unrooted(const char *path)
{
	const char *ptr;

	if (!path || !*path)
		return (NULL);

	ptr = path + strlen(path);
	/* find last char in path before any trailing slashes */
	while (ptr != path && *--ptr == '/')
		;

	if (ptr == path)	/* all slashes */
		return (ptr);

	while (ptr != path)
		if (*--ptr == '/')
			return (++ptr);

	return (ptr);
}

/*
 * close the oldest directory.  It saves the seek offset.
 * return value is 0 unless it was unable to close any descriptor
 */

static int
oldclose(struct Save *sp)
{
	struct Save *spnext;
	while (sp) {
		spnext = sp->last;
		if (spnext == 0 || spnext->fd == 0)
			break;
		sp = spnext;
	}
	if (sp == 0 || sp->fd == 0)
		return (0);
	sp->here = telldir(sp->fd);
	(void) closedir(sp->fd);
	sp->fd = 0;
	return (1);
}