11573Srgrimes/*- 21573Srgrimes * Copyright (c) 1990, 1993, 1994 31573Srgrimes * The Regents of the University of California. All rights reserved. 41573Srgrimes * 51573Srgrimes * Redistribution and use in source and binary forms, with or without 61573Srgrimes * modification, are permitted provided that the following conditions 71573Srgrimes * are met: 81573Srgrimes * 1. Redistributions of source code must retain the above copyright 91573Srgrimes * notice, this list of conditions and the following disclaimer. 101573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111573Srgrimes * notice, this list of conditions and the following disclaimer in the 121573Srgrimes * documentation and/or other materials provided with the distribution. 131573Srgrimes * 4. Neither the name of the University nor the names of its contributors 141573Srgrimes * may be used to endorse or promote products derived from this software 151573Srgrimes * without specific prior written permission. 161573Srgrimes * 171573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 181573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 211573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 221573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 231573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 241573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 251573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 261573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 271573Srgrimes * SUCH DAMAGE. 2854770Sgreen * 2954770Sgreen * $OpenBSD: fts.c,v 1.22 1999/10/03 19:22:22 millert Exp $ 301573Srgrimes */ 311573Srgrimes 32129184Sbde#if 0 331573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3423668Speterstatic char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94"; 351573Srgrimes#endif /* LIBC_SCCS and not lint */ 36129184Sbde#endif 37129184Sbde 3890045Sobrien#include <sys/cdefs.h> 3990045Sobrien__FBSDID("$FreeBSD$"); 401573Srgrimes 4171579Sdeischen#include "namespace.h" 421573Srgrimes#include <sys/param.h> 43129161Speadar#include <sys/mount.h> 441573Srgrimes#include <sys/stat.h> 451573Srgrimes 461573Srgrimes#include <dirent.h> 471573Srgrimes#include <errno.h> 481573Srgrimes#include <fcntl.h> 491573Srgrimes#include <stdlib.h> 501573Srgrimes#include <string.h> 511573Srgrimes#include <unistd.h> 52175688Syar#include "fts-compat.h" 5371579Sdeischen#include "un-namespace.h" 541573Srgrimes 55175688SyarFTSENT *__fts_children_44bsd(FTS *, int); 56175688Syarint __fts_close_44bsd(FTS *); 57175688Syarvoid *__fts_get_clientptr_44bsd(FTS *); 58175688SyarFTS *__fts_get_stream_44bsd(FTSENT *); 59175688SyarFTS *__fts_open_44bsd(char * const *, int, 60175688Syar int (*)(const FTSENT * const *, const FTSENT * const *)); 61175688SyarFTSENT *__fts_read_44bsd(FTS *); 62175688Syarint __fts_set_44bsd(FTS *, FTSENT *, int); 63175688Syarvoid __fts_set_clientptr_44bsd(FTS *, void *); 64175688Syar 6590045Sobrienstatic FTSENT *fts_alloc(FTS *, char *, int); 6690045Sobrienstatic FTSENT *fts_build(FTS *, int); 6790045Sobrienstatic void fts_lfree(FTSENT *); 6890045Sobrienstatic void fts_load(FTS *, FTSENT *); 6990045Sobrienstatic size_t fts_maxarglen(char * const *); 7090045Sobrienstatic void fts_padjust(FTS *, FTSENT *); 7190045Sobrienstatic int fts_palloc(FTS *, size_t); 7290045Sobrienstatic FTSENT *fts_sort(FTS *, FTSENT *, int); 7390045Sobrienstatic u_short fts_stat(FTS *, FTSENT *, int); 7490045Sobrienstatic int fts_safe_changedir(FTS *, FTSENT *, int, char *); 75129161Speadarstatic int fts_ufslinks(FTS *, const FTSENT *); 761573Srgrimes 7728913Simp#define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2]))) 781573Srgrimes 7928913Simp#define CLR(opt) (sp->fts_options &= ~(opt)) 8028913Simp#define ISSET(opt) (sp->fts_options & (opt)) 8128913Simp#define SET(opt) (sp->fts_options |= (opt)) 821573Srgrimes 831573Srgrimes#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd)) 841573Srgrimes 851573Srgrimes/* fts_build flags */ 861573Srgrimes#define BCHILD 1 /* fts_children */ 871573Srgrimes#define BNAMES 2 /* fts_children, names only */ 881573Srgrimes#define BREAD 3 /* fts_read */ 891573Srgrimes 90129052Speadar/* 91129161Speadar * Internal representation of an FTS, including extra implementation 92129161Speadar * details. The FTS returned from fts_open points to this structure's 93129161Speadar * ftsp_fts member (and can be cast to an _fts_private as required) 94129052Speadar */ 95129052Speadarstruct _fts_private { 96129161Speadar FTS ftsp_fts; 97129161Speadar struct statfs ftsp_statfs; 98129161Speadar dev_t ftsp_dev; 99129161Speadar int ftsp_linksreliable; 100129052Speadar}; 101129052Speadar 102129052Speadar/* 103129161Speadar * The "FTS_NOSTAT" option can avoid a lot of calls to stat(2) if it 104129161Speadar * knows that a directory could not possibly have subdirectories. This 105129161Speadar * is decided by looking at the link count: a subdirectory would 106129161Speadar * increment its parent's link count by virtue of its own ".." entry. 107129161Speadar * This assumption only holds for UFS-like filesystems that implement 108129161Speadar * links and directories this way, so we must punt for others. 109129052Speadar */ 110129052Speadar 111129052Speadarstatic const char *ufslike_filesystems[] = { 112129052Speadar "ufs", 113219696Spjd "zfs", 114129052Speadar "nfs", 115129052Speadar "nfs4", 116129052Speadar "ext2fs", 117129052Speadar 0 118129052Speadar}; 119129052Speadar 1201573SrgrimesFTS * 121175688Syar__fts_open_44bsd(argv, options, compar) 1221573Srgrimes char * const *argv; 12390045Sobrien int options; 124103726Swollman int (*compar)(const FTSENT * const *, const FTSENT * const *); 1251573Srgrimes{ 126129052Speadar struct _fts_private *priv; 12790045Sobrien FTS *sp; 12890045Sobrien FTSENT *p, *root; 12990045Sobrien int nitems; 1301573Srgrimes FTSENT *parent, *tmp; 1311573Srgrimes int len; 1321573Srgrimes 1331573Srgrimes /* Options check. */ 1341573Srgrimes if (options & ~FTS_OPTIONMASK) { 1351573Srgrimes errno = EINVAL; 1361573Srgrimes return (NULL); 1371573Srgrimes } 1381573Srgrimes 139129184Sbde /* Allocate/initialize the stream. */ 140129161Speadar if ((priv = malloc(sizeof(*priv))) == NULL) 1411573Srgrimes return (NULL); 142129161Speadar memset(priv, 0, sizeof(*priv)); 143129052Speadar sp = &priv->ftsp_fts; 1441573Srgrimes sp->fts_compar = compar; 1451573Srgrimes sp->fts_options = options; 1461573Srgrimes 14754770Sgreen /* Shush, GCC. */ 14854770Sgreen tmp = NULL; 14954770Sgreen 1501573Srgrimes /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ 1511573Srgrimes if (ISSET(FTS_LOGICAL)) 1521573Srgrimes SET(FTS_NOCHDIR); 1531573Srgrimes 1541573Srgrimes /* 1551573Srgrimes * Start out with 1K of path space, and enough, in any case, 1561573Srgrimes * to hold the user's paths. 1571573Srgrimes */ 1581573Srgrimes if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN))) 1591573Srgrimes goto mem1; 1601573Srgrimes 1611573Srgrimes /* Allocate/initialize root's parent. */ 1621573Srgrimes if ((parent = fts_alloc(sp, "", 0)) == NULL) 1631573Srgrimes goto mem2; 1641573Srgrimes parent->fts_level = FTS_ROOTPARENTLEVEL; 1651573Srgrimes 1661573Srgrimes /* Allocate/initialize root(s). */ 16764740Sgreen for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) { 1681573Srgrimes /* Don't allow zero-length paths. */ 1691573Srgrimes if ((len = strlen(*argv)) == 0) { 1701573Srgrimes errno = ENOENT; 1711573Srgrimes goto mem3; 1721573Srgrimes } 1731573Srgrimes 1741573Srgrimes p = fts_alloc(sp, *argv, len); 1751573Srgrimes p->fts_level = FTS_ROOTLEVEL; 1761573Srgrimes p->fts_parent = parent; 1771573Srgrimes p->fts_accpath = p->fts_name; 1781573Srgrimes p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW)); 1791573Srgrimes 1801573Srgrimes /* Command-line "." and ".." are real directories. */ 1811573Srgrimes if (p->fts_info == FTS_DOT) 1821573Srgrimes p->fts_info = FTS_D; 1831573Srgrimes 1841573Srgrimes /* 1851573Srgrimes * If comparison routine supplied, traverse in sorted 1861573Srgrimes * order; otherwise traverse in the order specified. 1871573Srgrimes */ 1881573Srgrimes if (compar) { 1891573Srgrimes p->fts_link = root; 1901573Srgrimes root = p; 1911573Srgrimes } else { 1921573Srgrimes p->fts_link = NULL; 1931573Srgrimes if (root == NULL) 1941573Srgrimes tmp = root = p; 1951573Srgrimes else { 1961573Srgrimes tmp->fts_link = p; 1971573Srgrimes tmp = p; 1981573Srgrimes } 1991573Srgrimes } 2001573Srgrimes } 2011573Srgrimes if (compar && nitems > 1) 2021573Srgrimes root = fts_sort(sp, root, nitems); 2031573Srgrimes 2041573Srgrimes /* 2051573Srgrimes * Allocate a dummy pointer and make fts_read think that we've just 2061573Srgrimes * finished the node before the root(s); set p->fts_info to FTS_INIT 2071573Srgrimes * so that everything about the "current" node is ignored. 2081573Srgrimes */ 2091573Srgrimes if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL) 2101573Srgrimes goto mem3; 2111573Srgrimes sp->fts_cur->fts_link = root; 2121573Srgrimes sp->fts_cur->fts_info = FTS_INIT; 2131573Srgrimes 2141573Srgrimes /* 21554770Sgreen * If using chdir(2), grab a file descriptor pointing to dot to ensure 2161573Srgrimes * that we can get back here; this could be avoided for some paths, 2171573Srgrimes * but almost certainly not worth the effort. Slashes, symbolic links, 2181573Srgrimes * and ".." are all fairly nasty problems. Note, if we can't get the 2191573Srgrimes * descriptor we run anyway, just more slowly. 2201573Srgrimes */ 221247273Sjilles if (!ISSET(FTS_NOCHDIR) && 222247273Sjilles (sp->fts_rfd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) 2231573Srgrimes SET(FTS_NOCHDIR); 2241573Srgrimes 2251573Srgrimes return (sp); 2261573Srgrimes 2271573Srgrimesmem3: fts_lfree(root); 2281573Srgrimes free(parent); 2291573Srgrimesmem2: free(sp->fts_path); 2301573Srgrimesmem1: free(sp); 2311573Srgrimes return (NULL); 2321573Srgrimes} 2331573Srgrimes 2341573Srgrimesstatic void 2351573Srgrimesfts_load(sp, p) 2361573Srgrimes FTS *sp; 23790045Sobrien FTSENT *p; 2381573Srgrimes{ 23990045Sobrien int len; 24090045Sobrien char *cp; 2411573Srgrimes 2421573Srgrimes /* 2431573Srgrimes * Load the stream structure for the next traversal. Since we don't 2441573Srgrimes * actually enter the directory until after the preorder visit, set 2451573Srgrimes * the fts_accpath field specially so the chdir gets done to the right 2461573Srgrimes * place and the user can access the first node. From fts_open it's 2471573Srgrimes * known that the path will fit. 2481573Srgrimes */ 2491573Srgrimes len = p->fts_pathlen = p->fts_namelen; 2501573Srgrimes memmove(sp->fts_path, p->fts_name, len + 1); 2511573Srgrimes if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { 2521573Srgrimes len = strlen(++cp); 2531573Srgrimes memmove(p->fts_name, cp, len + 1); 2541573Srgrimes p->fts_namelen = len; 2551573Srgrimes } 2561573Srgrimes p->fts_accpath = p->fts_path = sp->fts_path; 2571573Srgrimes sp->fts_dev = p->fts_dev; 2581573Srgrimes} 2591573Srgrimes 2601573Srgrimesint 261175688Syar__fts_close_44bsd(sp) 2621573Srgrimes FTS *sp; 2631573Srgrimes{ 26490045Sobrien FTSENT *freep, *p; 2651573Srgrimes int saved_errno; 2661573Srgrimes 2671573Srgrimes /* 2681573Srgrimes * This still works if we haven't read anything -- the dummy structure 2691573Srgrimes * points to the root list, so we step through to the end of the root 2701573Srgrimes * list which has a valid parent pointer. 2711573Srgrimes */ 2721573Srgrimes if (sp->fts_cur) { 2731573Srgrimes for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { 2741573Srgrimes freep = p; 27564740Sgreen p = p->fts_link != NULL ? p->fts_link : p->fts_parent; 2761573Srgrimes free(freep); 2771573Srgrimes } 2781573Srgrimes free(p); 2791573Srgrimes } 2801573Srgrimes 2811573Srgrimes /* Free up child linked list, sort array, path buffer. */ 2821573Srgrimes if (sp->fts_child) 2831573Srgrimes fts_lfree(sp->fts_child); 2841573Srgrimes if (sp->fts_array) 2851573Srgrimes free(sp->fts_array); 2861573Srgrimes free(sp->fts_path); 2871573Srgrimes 2881573Srgrimes /* Return to original directory, save errno if necessary. */ 2891573Srgrimes if (!ISSET(FTS_NOCHDIR)) { 2901573Srgrimes saved_errno = fchdir(sp->fts_rfd) ? errno : 0; 29156698Sjasone (void)_close(sp->fts_rfd); 29254770Sgreen 29354770Sgreen /* Set errno and return. */ 29454770Sgreen if (saved_errno != 0) { 29554770Sgreen /* Free up the stream pointer. */ 29654770Sgreen free(sp); 29754770Sgreen errno = saved_errno; 29854770Sgreen return (-1); 29954770Sgreen } 3001573Srgrimes } 3011573Srgrimes 30237349Sphk /* Free up the stream pointer. */ 30337349Sphk free(sp); 3041573Srgrimes return (0); 3051573Srgrimes} 3061573Srgrimes 3071573Srgrimes/* 30828913Simp * Special case of "/" at the end of the path so that slashes aren't 30928913Simp * appended which would cause paths to be written as "....//foo". 3101573Srgrimes */ 3111573Srgrimes#define NAPPEND(p) \ 31228913Simp (p->fts_path[p->fts_pathlen - 1] == '/' \ 31328913Simp ? p->fts_pathlen - 1 : p->fts_pathlen) 3141573Srgrimes 3151573SrgrimesFTSENT * 316175688Syar__fts_read_44bsd(sp) 31790045Sobrien FTS *sp; 3181573Srgrimes{ 31990045Sobrien FTSENT *p, *tmp; 32090045Sobrien int instr; 32190045Sobrien char *t; 3221573Srgrimes int saved_errno; 3231573Srgrimes 3241573Srgrimes /* If finished or unrecoverable error, return NULL. */ 3251573Srgrimes if (sp->fts_cur == NULL || ISSET(FTS_STOP)) 3261573Srgrimes return (NULL); 3271573Srgrimes 3281573Srgrimes /* Set current node pointer. */ 3291573Srgrimes p = sp->fts_cur; 3301573Srgrimes 3311573Srgrimes /* Save and zero out user instructions. */ 3321573Srgrimes instr = p->fts_instr; 3331573Srgrimes p->fts_instr = FTS_NOINSTR; 3341573Srgrimes 3351573Srgrimes /* Any type of file may be re-visited; re-stat and re-turn. */ 3361573Srgrimes if (instr == FTS_AGAIN) { 3371573Srgrimes p->fts_info = fts_stat(sp, p, 0); 3381573Srgrimes return (p); 3391573Srgrimes } 3401573Srgrimes 3411573Srgrimes /* 3421573Srgrimes * Following a symlink -- SLNONE test allows application to see 3431573Srgrimes * SLNONE and recover. If indirecting through a symlink, have 3441573Srgrimes * keep a pointer to current location. If unable to get that 3451573Srgrimes * pointer, follow fails. 3461573Srgrimes */ 3471573Srgrimes if (instr == FTS_FOLLOW && 3481573Srgrimes (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { 3491573Srgrimes p->fts_info = fts_stat(sp, p, 1); 35054770Sgreen if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { 351247273Sjilles if ((p->fts_symfd = _open(".", O_RDONLY | O_CLOEXEC, 352247273Sjilles 0)) < 0) { 3531573Srgrimes p->fts_errno = errno; 3541573Srgrimes p->fts_info = FTS_ERR; 3551573Srgrimes } else 3561573Srgrimes p->fts_flags |= FTS_SYMFOLLOW; 35754770Sgreen } 3581573Srgrimes return (p); 3591573Srgrimes } 3601573Srgrimes 3611573Srgrimes /* Directory in pre-order. */ 3621573Srgrimes if (p->fts_info == FTS_D) { 3631573Srgrimes /* If skipped or crossed mount point, do post-order visit. */ 3641573Srgrimes if (instr == FTS_SKIP || 36528913Simp (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) { 3661573Srgrimes if (p->fts_flags & FTS_SYMFOLLOW) 36756698Sjasone (void)_close(p->fts_symfd); 3681573Srgrimes if (sp->fts_child) { 3691573Srgrimes fts_lfree(sp->fts_child); 3701573Srgrimes sp->fts_child = NULL; 3711573Srgrimes } 3721573Srgrimes p->fts_info = FTS_DP; 3731573Srgrimes return (p); 3748870Srgrimes } 3751573Srgrimes 3761573Srgrimes /* Rebuild if only read the names and now traversing. */ 37764740Sgreen if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) { 37828913Simp CLR(FTS_NAMEONLY); 3791573Srgrimes fts_lfree(sp->fts_child); 3801573Srgrimes sp->fts_child = NULL; 3811573Srgrimes } 3821573Srgrimes 3831573Srgrimes /* 3841573Srgrimes * Cd to the subdirectory. 3851573Srgrimes * 3861573Srgrimes * If have already read and now fail to chdir, whack the list 3871573Srgrimes * to make the names come out right, and set the parent errno 3881573Srgrimes * so the application will eventually get an error condition. 3891573Srgrimes * Set the FTS_DONTCHDIR flag so that when we logically change 3901573Srgrimes * directories back to the parent we don't do a chdir. 3911573Srgrimes * 3921573Srgrimes * If haven't read do so. If the read fails, fts_build sets 3931573Srgrimes * FTS_STOP or the fts_info field of the node. 3941573Srgrimes */ 39564740Sgreen if (sp->fts_child != NULL) { 39677599Skris if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) { 3971573Srgrimes p->fts_errno = errno; 3981573Srgrimes p->fts_flags |= FTS_DONTCHDIR; 399129184Sbde for (p = sp->fts_child; p != NULL; 40064740Sgreen p = p->fts_link) 4011573Srgrimes p->fts_accpath = 4021573Srgrimes p->fts_parent->fts_accpath; 4031573Srgrimes } 4041573Srgrimes } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) { 4051573Srgrimes if (ISSET(FTS_STOP)) 4061573Srgrimes return (NULL); 4071573Srgrimes return (p); 4081573Srgrimes } 4091573Srgrimes p = sp->fts_child; 4101573Srgrimes sp->fts_child = NULL; 4111573Srgrimes goto name; 4121573Srgrimes } 4131573Srgrimes 4141573Srgrimes /* Move to the next node on this level. */ 4151573Srgrimesnext: tmp = p; 41664740Sgreen if ((p = p->fts_link) != NULL) { 4171573Srgrimes free(tmp); 4181573Srgrimes 4191573Srgrimes /* 42054770Sgreen * If reached the top, return to the original directory (or 42154770Sgreen * the root of the tree), and load the paths for the next root. 4221573Srgrimes */ 4231573Srgrimes if (p->fts_level == FTS_ROOTLEVEL) { 42428913Simp if (FCHDIR(sp, sp->fts_rfd)) { 4251573Srgrimes SET(FTS_STOP); 4261573Srgrimes return (NULL); 4271573Srgrimes } 4281573Srgrimes fts_load(sp, p); 4291573Srgrimes return (sp->fts_cur = p); 4301573Srgrimes } 4311573Srgrimes 4321573Srgrimes /* 4331573Srgrimes * User may have called fts_set on the node. If skipped, 4341573Srgrimes * ignore. If followed, get a file descriptor so we can 4351573Srgrimes * get back if necessary. 4361573Srgrimes */ 4371573Srgrimes if (p->fts_instr == FTS_SKIP) 4381573Srgrimes goto next; 4391573Srgrimes if (p->fts_instr == FTS_FOLLOW) { 4401573Srgrimes p->fts_info = fts_stat(sp, p, 1); 44154770Sgreen if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { 4421573Srgrimes if ((p->fts_symfd = 443247273Sjilles _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) { 4441573Srgrimes p->fts_errno = errno; 4451573Srgrimes p->fts_info = FTS_ERR; 4461573Srgrimes } else 4471573Srgrimes p->fts_flags |= FTS_SYMFOLLOW; 44854770Sgreen } 4491573Srgrimes p->fts_instr = FTS_NOINSTR; 4501573Srgrimes } 4511573Srgrimes 4521573Srgrimesname: t = sp->fts_path + NAPPEND(p->fts_parent); 4531573Srgrimes *t++ = '/'; 4541573Srgrimes memmove(t, p->fts_name, p->fts_namelen + 1); 4551573Srgrimes return (sp->fts_cur = p); 4561573Srgrimes } 4571573Srgrimes 4581573Srgrimes /* Move up to the parent node. */ 4591573Srgrimes p = tmp->fts_parent; 4601573Srgrimes free(tmp); 4611573Srgrimes 4621573Srgrimes if (p->fts_level == FTS_ROOTPARENTLEVEL) { 4631573Srgrimes /* 4641573Srgrimes * Done; free everything up and set errno to 0 so the user 4651573Srgrimes * can distinguish between error and EOF. 4661573Srgrimes */ 4671573Srgrimes free(p); 4681573Srgrimes errno = 0; 4691573Srgrimes return (sp->fts_cur = NULL); 4701573Srgrimes } 4711573Srgrimes 47254770Sgreen /* NUL terminate the pathname. */ 4731573Srgrimes sp->fts_path[p->fts_pathlen] = '\0'; 4741573Srgrimes 4751573Srgrimes /* 4761573Srgrimes * Return to the parent directory. If at a root node or came through 4771573Srgrimes * a symlink, go back through the file descriptor. Otherwise, cd up 4781573Srgrimes * one directory. 4791573Srgrimes */ 4801573Srgrimes if (p->fts_level == FTS_ROOTLEVEL) { 48128913Simp if (FCHDIR(sp, sp->fts_rfd)) { 4821573Srgrimes SET(FTS_STOP); 4831573Srgrimes return (NULL); 4841573Srgrimes } 4851573Srgrimes } else if (p->fts_flags & FTS_SYMFOLLOW) { 4861573Srgrimes if (FCHDIR(sp, p->fts_symfd)) { 4871573Srgrimes saved_errno = errno; 48856698Sjasone (void)_close(p->fts_symfd); 4891573Srgrimes errno = saved_errno; 4901573Srgrimes SET(FTS_STOP); 4911573Srgrimes return (NULL); 4921573Srgrimes } 49356698Sjasone (void)_close(p->fts_symfd); 49477497Skris } else if (!(p->fts_flags & FTS_DONTCHDIR) && 495129184Sbde fts_safe_changedir(sp, p->fts_parent, -1, "..")) { 49677599Skris SET(FTS_STOP); 49777599Skris return (NULL); 4981573Srgrimes } 4991573Srgrimes p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP; 5001573Srgrimes return (sp->fts_cur = p); 5011573Srgrimes} 5021573Srgrimes 5031573Srgrimes/* 5041573Srgrimes * Fts_set takes the stream as an argument although it's not used in this 5051573Srgrimes * implementation; it would be necessary if anyone wanted to add global 5061573Srgrimes * semantics to fts using fts_set. An error return is allowed for similar 5071573Srgrimes * reasons. 5081573Srgrimes */ 5091573Srgrimes/* ARGSUSED */ 5101573Srgrimesint 511175688Syar__fts_set_44bsd(sp, p, instr) 5121573Srgrimes FTS *sp; 5131573Srgrimes FTSENT *p; 5141573Srgrimes int instr; 5151573Srgrimes{ 51664740Sgreen if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW && 5171573Srgrimes instr != FTS_NOINSTR && instr != FTS_SKIP) { 5181573Srgrimes errno = EINVAL; 5191573Srgrimes return (1); 5201573Srgrimes } 5211573Srgrimes p->fts_instr = instr; 5221573Srgrimes return (0); 5231573Srgrimes} 5241573Srgrimes 5251573SrgrimesFTSENT * 526175688Syar__fts_children_44bsd(sp, instr) 52790045Sobrien FTS *sp; 5281573Srgrimes int instr; 5291573Srgrimes{ 53090045Sobrien FTSENT *p; 5311573Srgrimes int fd; 5321573Srgrimes 53364740Sgreen if (instr != 0 && instr != FTS_NAMEONLY) { 5341573Srgrimes errno = EINVAL; 5351573Srgrimes return (NULL); 5361573Srgrimes } 5371573Srgrimes 5381573Srgrimes /* Set current node pointer. */ 5391573Srgrimes p = sp->fts_cur; 5401573Srgrimes 5411573Srgrimes /* 5421573Srgrimes * Errno set to 0 so user can distinguish empty directory from 5431573Srgrimes * an error. 5441573Srgrimes */ 5451573Srgrimes errno = 0; 5461573Srgrimes 5471573Srgrimes /* Fatal errors stop here. */ 5481573Srgrimes if (ISSET(FTS_STOP)) 5491573Srgrimes return (NULL); 5501573Srgrimes 5511573Srgrimes /* Return logical hierarchy of user's arguments. */ 5521573Srgrimes if (p->fts_info == FTS_INIT) 5531573Srgrimes return (p->fts_link); 5541573Srgrimes 5551573Srgrimes /* 5561573Srgrimes * If not a directory being visited in pre-order, stop here. Could 5571573Srgrimes * allow FTS_DNR, assuming the user has fixed the problem, but the 5581573Srgrimes * same effect is available with FTS_AGAIN. 5591573Srgrimes */ 5601573Srgrimes if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */) 5611573Srgrimes return (NULL); 5621573Srgrimes 5631573Srgrimes /* Free up any previous child list. */ 56464740Sgreen if (sp->fts_child != NULL) 5651573Srgrimes fts_lfree(sp->fts_child); 5661573Srgrimes 5671573Srgrimes if (instr == FTS_NAMEONLY) { 56828913Simp SET(FTS_NAMEONLY); 5691573Srgrimes instr = BNAMES; 5708870Srgrimes } else 5711573Srgrimes instr = BCHILD; 5721573Srgrimes 5731573Srgrimes /* 5741573Srgrimes * If using chdir on a relative path and called BEFORE fts_read does 5751573Srgrimes * its chdir to the root of a traversal, we can lose -- we need to 5761573Srgrimes * chdir into the subdirectory, and we don't know where the current 5771573Srgrimes * directory is, so we can't get back so that the upcoming chdir by 5781573Srgrimes * fts_read will work. 5791573Srgrimes */ 5801573Srgrimes if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || 5811573Srgrimes ISSET(FTS_NOCHDIR)) 5821573Srgrimes return (sp->fts_child = fts_build(sp, instr)); 5831573Srgrimes 584247273Sjilles if ((fd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) 5851573Srgrimes return (NULL); 5861573Srgrimes sp->fts_child = fts_build(sp, instr); 5871573Srgrimes if (fchdir(fd)) 5881573Srgrimes return (NULL); 58956698Sjasone (void)_close(fd); 5901573Srgrimes return (sp->fts_child); 5911573Srgrimes} 5921573Srgrimes 593103726Swollman#ifndef fts_get_clientptr 594103726Swollman#error "fts_get_clientptr not defined" 595103726Swollman#endif 596103726Swollman 597103726Swollmanvoid * 598175688Syar(__fts_get_clientptr_44bsd)(FTS *sp) 599103726Swollman{ 600103726Swollman 601103726Swollman return (fts_get_clientptr(sp)); 602103726Swollman} 603103726Swollman 604103726Swollman#ifndef fts_get_stream 605103726Swollman#error "fts_get_stream not defined" 606103726Swollman#endif 607103726Swollman 608103726SwollmanFTS * 609175688Syar(__fts_get_stream_44bsd)(FTSENT *p) 610103726Swollman{ 611103726Swollman return (fts_get_stream(p)); 612103726Swollman} 613103726Swollman 614103726Swollmanvoid 615175688Syar__fts_set_clientptr_44bsd(FTS *sp, void *clientptr) 616103726Swollman{ 617103726Swollman 618103726Swollman sp->fts_clientptr = clientptr; 619103726Swollman} 620103726Swollman 6211573Srgrimes/* 6221573Srgrimes * This is the tricky part -- do not casually change *anything* in here. The 6231573Srgrimes * idea is to build the linked list of entries that are used by fts_children 6241573Srgrimes * and fts_read. There are lots of special cases. 6251573Srgrimes * 6261573Srgrimes * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is 6271573Srgrimes * set and it's a physical walk (so that symbolic links can't be directories), 6281573Srgrimes * we can do things quickly. First, if it's a 4.4BSD file system, the type 6291573Srgrimes * of the file is in the directory entry. Otherwise, we assume that the number 6301573Srgrimes * of subdirectories in a node is equal to the number of links to the parent. 6311573Srgrimes * The former skips all stat calls. The latter skips stat calls in any leaf 6321573Srgrimes * directories and for any files after the subdirectories in the directory have 6331573Srgrimes * been found, cutting the stat calls by about 2/3. 6341573Srgrimes */ 6351573Srgrimesstatic FTSENT * 6361573Srgrimesfts_build(sp, type) 63790045Sobrien FTS *sp; 6381573Srgrimes int type; 6391573Srgrimes{ 64090045Sobrien struct dirent *dp; 64190045Sobrien FTSENT *p, *head; 64290045Sobrien int nitems; 6431573Srgrimes FTSENT *cur, *tail; 6441573Srgrimes DIR *dirp; 64554770Sgreen void *oldaddr; 646128946Skientzle size_t dnamlen; 64754770Sgreen int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno, 64854770Sgreen nostat, doadjust; 6491573Srgrimes char *cp; 6501573Srgrimes 6511573Srgrimes /* Set current node pointer. */ 6521573Srgrimes cur = sp->fts_cur; 6531573Srgrimes 6541573Srgrimes /* 6551573Srgrimes * Open the directory for reading. If this fails, we're done. 6561573Srgrimes * If being called from fts_read, set the fts_info field. 6571573Srgrimes */ 65823668Speter#ifdef FTS_WHITEOUT 65923668Speter if (ISSET(FTS_WHITEOUT)) 660129184Sbde oflag = DTF_NODUP | DTF_REWIND; 66123668Speter else 662129184Sbde oflag = DTF_HIDEW | DTF_NODUP | DTF_REWIND; 66323668Speter#else 66423668Speter#define __opendir2(path, flag) opendir(path) 66523668Speter#endif 66623668Speter if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) { 6671573Srgrimes if (type == BREAD) { 6681573Srgrimes cur->fts_info = FTS_DNR; 6691573Srgrimes cur->fts_errno = errno; 6701573Srgrimes } 6711573Srgrimes return (NULL); 6721573Srgrimes } 6731573Srgrimes 6741573Srgrimes /* 6751573Srgrimes * Nlinks is the number of possible entries of type directory in the 6761573Srgrimes * directory if we're cheating on stat calls, 0 if we're not doing 6771573Srgrimes * any stat calls at all, -1 if we're doing stats on everything. 6781573Srgrimes */ 67954770Sgreen if (type == BNAMES) { 6801573Srgrimes nlinks = 0; 68154770Sgreen /* Be quiet about nostat, GCC. */ 68254770Sgreen nostat = 0; 68354770Sgreen } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) { 684129052Speadar if (fts_ufslinks(sp, cur)) 685129052Speadar nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2); 686129052Speadar else 687129052Speadar nlinks = -1; 68854770Sgreen nostat = 1; 68954770Sgreen } else { 6901573Srgrimes nlinks = -1; 69154770Sgreen nostat = 0; 69254770Sgreen } 6931573Srgrimes 6941573Srgrimes#ifdef notdef 6951573Srgrimes (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink); 6961573Srgrimes (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n", 6971573Srgrimes ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT)); 6981573Srgrimes#endif 6991573Srgrimes /* 7001573Srgrimes * If we're going to need to stat anything or we want to descend 7011573Srgrimes * and stay in the directory, chdir. If this fails we keep going, 7021573Srgrimes * but set a flag so we don't chdir after the post-order visit. 7031573Srgrimes * We won't be able to stat anything, but we can still return the 7041573Srgrimes * names themselves. Note, that since fts_read won't be able to 7051573Srgrimes * chdir into the directory, it will have to return different path 7061573Srgrimes * names than before, i.e. "a/b" instead of "b". Since the node 7071573Srgrimes * has already been visited in pre-order, have to wait until the 7081573Srgrimes * post-order visit to return the error. There is a special case 7091573Srgrimes * here, if there was nothing to stat then it's not an error to 7101573Srgrimes * not be able to stat. This is all fairly nasty. If a program 7111573Srgrimes * needed sorted entries or stat information, they had better be 7121573Srgrimes * checking FTS_NS on the returned nodes. 7131573Srgrimes */ 7141573Srgrimes cderrno = 0; 71554770Sgreen if (nlinks || type == BREAD) { 71677599Skris if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) { 7171573Srgrimes if (nlinks && type == BREAD) 7181573Srgrimes cur->fts_errno = errno; 7191573Srgrimes cur->fts_flags |= FTS_DONTCHDIR; 7201573Srgrimes descend = 0; 7211573Srgrimes cderrno = errno; 7221573Srgrimes } else 7231573Srgrimes descend = 1; 72454770Sgreen } else 7251573Srgrimes descend = 0; 7261573Srgrimes 7271573Srgrimes /* 7281573Srgrimes * Figure out the max file name length that can be stored in the 7291573Srgrimes * current path -- the inner loop allocates more path as necessary. 7301573Srgrimes * We really wouldn't have to do the maxlen calculations here, we 7311573Srgrimes * could do them in fts_read before returning the path, but it's a 7321573Srgrimes * lot easier here since the length is part of the dirent structure. 7331573Srgrimes * 7341573Srgrimes * If not changing directories set a pointer so that can just append 7351573Srgrimes * each new name into the path. 7361573Srgrimes */ 7371573Srgrimes len = NAPPEND(cur); 7381573Srgrimes if (ISSET(FTS_NOCHDIR)) { 7391573Srgrimes cp = sp->fts_path + len; 7401573Srgrimes *cp++ = '/'; 74154770Sgreen } else { 74254770Sgreen /* GCC, you're too verbose. */ 74354770Sgreen cp = NULL; 7441573Srgrimes } 74554770Sgreen len++; 74654770Sgreen maxlen = sp->fts_pathlen - len; 7471573Srgrimes 7481573Srgrimes level = cur->fts_level + 1; 7491573Srgrimes 7501573Srgrimes /* Read the directory, attaching each entry to the `link' pointer. */ 75154770Sgreen doadjust = 0; 75228913Simp for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) { 753128946Skientzle dnamlen = dp->d_namlen; 7541573Srgrimes if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) 7551573Srgrimes continue; 7561573Srgrimes 757128946Skientzle if ((p = fts_alloc(sp, dp->d_name, (int)dnamlen)) == NULL) 7581573Srgrimes goto mem1; 759128946Skientzle if (dnamlen >= maxlen) { /* include space for NUL */ 76054770Sgreen oldaddr = sp->fts_path; 761128946Skientzle if (fts_palloc(sp, dnamlen + len + 1)) { 7621573Srgrimes /* 7631573Srgrimes * No more memory for path or structures. Save 7641573Srgrimes * errno, free up the current structure and the 7651573Srgrimes * structures already allocated. 7661573Srgrimes */ 7671573Srgrimesmem1: saved_errno = errno; 7681573Srgrimes if (p) 7691573Srgrimes free(p); 7701573Srgrimes fts_lfree(head); 7711573Srgrimes (void)closedir(dirp); 7721573Srgrimes cur->fts_info = FTS_ERR; 7731573Srgrimes SET(FTS_STOP); 77454770Sgreen errno = saved_errno; 7751573Srgrimes return (NULL); 7761573Srgrimes } 77754770Sgreen /* Did realloc() change the pointer? */ 77854770Sgreen if (oldaddr != sp->fts_path) { 77954770Sgreen doadjust = 1; 78054770Sgreen if (ISSET(FTS_NOCHDIR)) 78154770Sgreen cp = sp->fts_path + len; 78254770Sgreen } 78354770Sgreen maxlen = sp->fts_pathlen - len; 7841573Srgrimes } 7851573Srgrimes 786128946Skientzle if (len + dnamlen >= USHRT_MAX) { 78754770Sgreen /* 78854770Sgreen * In an FTSENT, fts_pathlen is a u_short so it is 78954770Sgreen * possible to wraparound here. If we do, free up 79054770Sgreen * the current structure and the structures already 79154770Sgreen * allocated, then error out with ENAMETOOLONG. 79254770Sgreen */ 79354770Sgreen free(p); 79454770Sgreen fts_lfree(head); 79554770Sgreen (void)closedir(dirp); 79654770Sgreen cur->fts_info = FTS_ERR; 79754770Sgreen SET(FTS_STOP); 79854770Sgreen errno = ENAMETOOLONG; 79954770Sgreen return (NULL); 80054770Sgreen } 80154770Sgreen p->fts_level = level; 8021573Srgrimes p->fts_parent = sp->fts_cur; 803128946Skientzle p->fts_pathlen = len + dnamlen; 8041573Srgrimes 80523668Speter#ifdef FTS_WHITEOUT 80623668Speter if (dp->d_type == DT_WHT) 80723668Speter p->fts_flags |= FTS_ISW; 80823668Speter#endif 80923668Speter 8101573Srgrimes if (cderrno) { 8111573Srgrimes if (nlinks) { 8121573Srgrimes p->fts_info = FTS_NS; 8131573Srgrimes p->fts_errno = cderrno; 8141573Srgrimes } else 8151573Srgrimes p->fts_info = FTS_NSOK; 8161573Srgrimes p->fts_accpath = cur->fts_accpath; 8171573Srgrimes } else if (nlinks == 0 8181573Srgrimes#ifdef DT_DIR 81954770Sgreen || (nostat && 82017141Sjkh dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN) 8211573Srgrimes#endif 8221573Srgrimes ) { 8231573Srgrimes p->fts_accpath = 8241573Srgrimes ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; 8251573Srgrimes p->fts_info = FTS_NSOK; 8261573Srgrimes } else { 8271573Srgrimes /* Build a file name for fts_stat to stat. */ 8281573Srgrimes if (ISSET(FTS_NOCHDIR)) { 8291573Srgrimes p->fts_accpath = p->fts_path; 8301573Srgrimes memmove(cp, p->fts_name, p->fts_namelen + 1); 8311573Srgrimes } else 8321573Srgrimes p->fts_accpath = p->fts_name; 8331573Srgrimes /* Stat it. */ 8341573Srgrimes p->fts_info = fts_stat(sp, p, 0); 8351573Srgrimes 8361573Srgrimes /* Decrement link count if applicable. */ 8371573Srgrimes if (nlinks > 0 && (p->fts_info == FTS_D || 8381573Srgrimes p->fts_info == FTS_DC || p->fts_info == FTS_DOT)) 8391573Srgrimes --nlinks; 8401573Srgrimes } 8411573Srgrimes 8421573Srgrimes /* We walk in directory order so "ls -f" doesn't get upset. */ 8431573Srgrimes p->fts_link = NULL; 8441573Srgrimes if (head == NULL) 8451573Srgrimes head = tail = p; 8461573Srgrimes else { 8471573Srgrimes tail->fts_link = p; 8481573Srgrimes tail = p; 8491573Srgrimes } 8501573Srgrimes ++nitems; 8511573Srgrimes } 85228913Simp if (dirp) 85328913Simp (void)closedir(dirp); 8541573Srgrimes 8551573Srgrimes /* 85654770Sgreen * If realloc() changed the address of the path, adjust the 85754770Sgreen * addresses for the rest of the tree and the dir list. 8581573Srgrimes */ 85954770Sgreen if (doadjust) 86054770Sgreen fts_padjust(sp, head); 8611573Srgrimes 8621573Srgrimes /* 8631573Srgrimes * If not changing directories, reset the path back to original 8641573Srgrimes * state. 8651573Srgrimes */ 8661573Srgrimes if (ISSET(FTS_NOCHDIR)) { 86754770Sgreen if (len == sp->fts_pathlen || nitems == 0) 8681573Srgrimes --cp; 8691573Srgrimes *cp = '\0'; 8701573Srgrimes } 8711573Srgrimes 8721573Srgrimes /* 8731573Srgrimes * If descended after called from fts_children or after called from 8741573Srgrimes * fts_read and nothing found, get back. At the root level we use 8751573Srgrimes * the saved fd; if one of fts_open()'s arguments is a relative path 8761573Srgrimes * to an empty directory, we wind up here with no other way back. If 8771573Srgrimes * can't get back, we're done. 8781573Srgrimes */ 8791573Srgrimes if (descend && (type == BCHILD || !nitems) && 8801573Srgrimes (cur->fts_level == FTS_ROOTLEVEL ? 88177599Skris FCHDIR(sp, sp->fts_rfd) : 88277599Skris fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) { 8831573Srgrimes cur->fts_info = FTS_ERR; 8841573Srgrimes SET(FTS_STOP); 8851573Srgrimes return (NULL); 8861573Srgrimes } 8871573Srgrimes 8881573Srgrimes /* If didn't find anything, return NULL. */ 8891573Srgrimes if (!nitems) { 8901573Srgrimes if (type == BREAD) 8911573Srgrimes cur->fts_info = FTS_DP; 8921573Srgrimes return (NULL); 8931573Srgrimes } 8941573Srgrimes 8951573Srgrimes /* Sort the entries. */ 8961573Srgrimes if (sp->fts_compar && nitems > 1) 8971573Srgrimes head = fts_sort(sp, head, nitems); 8981573Srgrimes return (head); 8991573Srgrimes} 9001573Srgrimes 9011573Srgrimesstatic u_short 9021573Srgrimesfts_stat(sp, p, follow) 9031573Srgrimes FTS *sp; 90490045Sobrien FTSENT *p; 9051573Srgrimes int follow; 9061573Srgrimes{ 90790045Sobrien FTSENT *t; 90890045Sobrien dev_t dev; 90990045Sobrien ino_t ino; 9101573Srgrimes struct stat *sbp, sb; 9111573Srgrimes int saved_errno; 9121573Srgrimes 9131573Srgrimes /* If user needs stat info, stat buffer already allocated. */ 9141573Srgrimes sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp; 9158870Srgrimes 91623668Speter#ifdef FTS_WHITEOUT 917129184Sbde /* Check for whiteout. */ 91823668Speter if (p->fts_flags & FTS_ISW) { 91923668Speter if (sbp != &sb) { 920129184Sbde memset(sbp, '\0', sizeof(*sbp)); 92123668Speter sbp->st_mode = S_IFWHT; 92223668Speter } 92323668Speter return (FTS_W); 92423668Speter } 92523668Speter#endif 92623668Speter 9271573Srgrimes /* 9281573Srgrimes * If doing a logical walk, or application requested FTS_FOLLOW, do 9291573Srgrimes * a stat(2). If that fails, check for a non-existent symlink. If 9301573Srgrimes * fail, set the errno from the stat call. 9311573Srgrimes */ 9321573Srgrimes if (ISSET(FTS_LOGICAL) || follow) { 9331573Srgrimes if (stat(p->fts_accpath, sbp)) { 9341573Srgrimes saved_errno = errno; 9351573Srgrimes if (!lstat(p->fts_accpath, sbp)) { 9361573Srgrimes errno = 0; 9371573Srgrimes return (FTS_SLNONE); 9388870Srgrimes } 9391573Srgrimes p->fts_errno = saved_errno; 9401573Srgrimes goto err; 9411573Srgrimes } 9421573Srgrimes } else if (lstat(p->fts_accpath, sbp)) { 9431573Srgrimes p->fts_errno = errno; 9441573Srgrimeserr: memset(sbp, 0, sizeof(struct stat)); 9451573Srgrimes return (FTS_NS); 9461573Srgrimes } 9471573Srgrimes 9481573Srgrimes if (S_ISDIR(sbp->st_mode)) { 9491573Srgrimes /* 9501573Srgrimes * Set the device/inode. Used to find cycles and check for 9511573Srgrimes * crossing mount points. Also remember the link count, used 9521573Srgrimes * in fts_build to limit the number of stat calls. It is 9531573Srgrimes * understood that these fields are only referenced if fts_info 9541573Srgrimes * is set to FTS_D. 9551573Srgrimes */ 9561573Srgrimes dev = p->fts_dev = sbp->st_dev; 9571573Srgrimes ino = p->fts_ino = sbp->st_ino; 9581573Srgrimes p->fts_nlink = sbp->st_nlink; 9591573Srgrimes 9601573Srgrimes if (ISDOT(p->fts_name)) 9611573Srgrimes return (FTS_DOT); 9621573Srgrimes 9631573Srgrimes /* 9641573Srgrimes * Cycle detection is done by brute force when the directory 9651573Srgrimes * is first encountered. If the tree gets deep enough or the 9661573Srgrimes * number of symbolic links to directories is high enough, 9671573Srgrimes * something faster might be worthwhile. 9681573Srgrimes */ 9691573Srgrimes for (t = p->fts_parent; 9701573Srgrimes t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) 9711573Srgrimes if (ino == t->fts_ino && dev == t->fts_dev) { 9721573Srgrimes p->fts_cycle = t; 9731573Srgrimes return (FTS_DC); 9741573Srgrimes } 9751573Srgrimes return (FTS_D); 9761573Srgrimes } 9771573Srgrimes if (S_ISLNK(sbp->st_mode)) 9781573Srgrimes return (FTS_SL); 9791573Srgrimes if (S_ISREG(sbp->st_mode)) 9801573Srgrimes return (FTS_F); 9811573Srgrimes return (FTS_DEFAULT); 9821573Srgrimes} 9831573Srgrimes 984103726Swollman/* 985103726Swollman * The comparison function takes pointers to pointers to FTSENT structures. 986103726Swollman * Qsort wants a comparison function that takes pointers to void. 987103726Swollman * (Both with appropriate levels of const-poisoning, of course!) 988103726Swollman * Use a trampoline function to deal with the difference. 989103726Swollman */ 990103726Swollmanstatic int 991103726Swollmanfts_compar(const void *a, const void *b) 992103726Swollman{ 993103726Swollman FTS *parent; 994103726Swollman 995103726Swollman parent = (*(const FTSENT * const *)a)->fts_fts; 996103726Swollman return (*parent->fts_compar)(a, b); 997103726Swollman} 998103726Swollman 9991573Srgrimesstatic FTSENT * 10001573Srgrimesfts_sort(sp, head, nitems) 10011573Srgrimes FTS *sp; 10021573Srgrimes FTSENT *head; 100390045Sobrien int nitems; 10041573Srgrimes{ 100590045Sobrien FTSENT **ap, *p; 10061573Srgrimes 10071573Srgrimes /* 10081573Srgrimes * Construct an array of pointers to the structures and call qsort(3). 10091573Srgrimes * Reassemble the array in the order returned by qsort. If unable to 10101573Srgrimes * sort for memory reasons, return the directory entries in their 10111573Srgrimes * current order. Allocate enough space for the current needs plus 10121573Srgrimes * 40 so don't realloc one entry at a time. 10131573Srgrimes */ 10141573Srgrimes if (nitems > sp->fts_nitems) { 10151573Srgrimes sp->fts_nitems = nitems + 40; 101664740Sgreen if ((sp->fts_array = reallocf(sp->fts_array, 101754770Sgreen sp->fts_nitems * sizeof(FTSENT *))) == NULL) { 10181573Srgrimes sp->fts_nitems = 0; 10191573Srgrimes return (head); 10201573Srgrimes } 10211573Srgrimes } 10221573Srgrimes for (ap = sp->fts_array, p = head; p; p = p->fts_link) 10231573Srgrimes *ap++ = p; 1024103726Swollman qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar); 10251573Srgrimes for (head = *(ap = sp->fts_array); --nitems; ++ap) 10261573Srgrimes ap[0]->fts_link = ap[1]; 10271573Srgrimes ap[0]->fts_link = NULL; 10281573Srgrimes return (head); 10291573Srgrimes} 10301573Srgrimes 10311573Srgrimesstatic FTSENT * 10321573Srgrimesfts_alloc(sp, name, namelen) 10331573Srgrimes FTS *sp; 10341573Srgrimes char *name; 103590045Sobrien int namelen; 10361573Srgrimes{ 103790045Sobrien FTSENT *p; 10381573Srgrimes size_t len; 10391573Srgrimes 1040103726Swollman struct ftsent_withstat { 1041103726Swollman FTSENT ent; 1042103726Swollman struct stat statbuf; 1043103726Swollman }; 1044103726Swollman 10451573Srgrimes /* 10461573Srgrimes * The file name is a variable length array and no stat structure is 10471573Srgrimes * necessary if the user has set the nostat bit. Allocate the FTSENT 10481573Srgrimes * structure, the file name and the stat structure in one chunk, but 1049103726Swollman * be careful that the stat structure is reasonably aligned. 10501573Srgrimes */ 1051103726Swollman if (ISSET(FTS_NOSTAT)) 1052103726Swollman len = sizeof(FTSENT) + namelen + 1; 1053103726Swollman else 1054103726Swollman len = sizeof(struct ftsent_withstat) + namelen + 1; 1055103726Swollman 10561573Srgrimes if ((p = malloc(len)) == NULL) 10571573Srgrimes return (NULL); 10581573Srgrimes 1059103726Swollman if (ISSET(FTS_NOSTAT)) { 1060103726Swollman p->fts_name = (char *)(p + 1); 1061103726Swollman p->fts_statp = NULL; 1062103726Swollman } else { 1063103726Swollman p->fts_name = (char *)((struct ftsent_withstat *)p + 1); 1064103726Swollman p->fts_statp = &((struct ftsent_withstat *)p)->statbuf; 1065103726Swollman } 1066103726Swollman 106754770Sgreen /* Copy the name and guarantee NUL termination. */ 1068103726Swollman memcpy(p->fts_name, name, namelen); 106954770Sgreen p->fts_name[namelen] = '\0'; 10701573Srgrimes p->fts_namelen = namelen; 10711573Srgrimes p->fts_path = sp->fts_path; 10721573Srgrimes p->fts_errno = 0; 10731573Srgrimes p->fts_flags = 0; 10741573Srgrimes p->fts_instr = FTS_NOINSTR; 10751573Srgrimes p->fts_number = 0; 10761573Srgrimes p->fts_pointer = NULL; 1077103726Swollman p->fts_fts = sp; 10781573Srgrimes return (p); 10791573Srgrimes} 10801573Srgrimes 10811573Srgrimesstatic void 10821573Srgrimesfts_lfree(head) 108390045Sobrien FTSENT *head; 10841573Srgrimes{ 108590045Sobrien FTSENT *p; 10861573Srgrimes 10871573Srgrimes /* Free a linked list of structures. */ 108828913Simp while ((p = head)) { 10891573Srgrimes head = head->fts_link; 10901573Srgrimes free(p); 10911573Srgrimes } 10921573Srgrimes} 10931573Srgrimes 10941573Srgrimes/* 10951573Srgrimes * Allow essentially unlimited paths; find, rm, ls should all work on any tree. 10961573Srgrimes * Most systems will allow creation of paths much longer than MAXPATHLEN, even 10971573Srgrimes * though the kernel won't resolve them. Add the size (not just what's needed) 10988870Srgrimes * plus 256 bytes so don't realloc the path 2 bytes at a time. 10991573Srgrimes */ 11001573Srgrimesstatic int 11011573Srgrimesfts_palloc(sp, more) 11021573Srgrimes FTS *sp; 11031573Srgrimes size_t more; 11041573Srgrimes{ 110554770Sgreen 11061573Srgrimes sp->fts_pathlen += more + 256; 110754770Sgreen /* 110854770Sgreen * Check for possible wraparound. In an FTS, fts_pathlen is 110954770Sgreen * a signed int but in an FTSENT it is an unsigned short. 111054770Sgreen * We limit fts_pathlen to USHRT_MAX to be safe in both cases. 111154770Sgreen */ 111254770Sgreen if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) { 111354770Sgreen if (sp->fts_path) 111454770Sgreen free(sp->fts_path); 111554770Sgreen sp->fts_path = NULL; 111654770Sgreen errno = ENAMETOOLONG; 111754770Sgreen return (1); 111850790Simp } 111964740Sgreen sp->fts_path = reallocf(sp->fts_path, sp->fts_pathlen); 112064740Sgreen return (sp->fts_path == NULL); 112150790Simp} 112250790Simp 11231573Srgrimes/* 11241573Srgrimes * When the path is realloc'd, have to fix all of the pointers in structures 11251573Srgrimes * already returned. 11261573Srgrimes */ 11271573Srgrimesstatic void 112854770Sgreenfts_padjust(sp, head) 11291573Srgrimes FTS *sp; 113054770Sgreen FTSENT *head; 11311573Srgrimes{ 11321573Srgrimes FTSENT *p; 113354770Sgreen char *addr = sp->fts_path; 11341573Srgrimes 113564740Sgreen#define ADJUST(p) do { \ 113654770Sgreen if ((p)->fts_accpath != (p)->fts_name) { \ 113754770Sgreen (p)->fts_accpath = \ 113854770Sgreen (char *)addr + ((p)->fts_accpath - (p)->fts_path); \ 113954770Sgreen } \ 11401573Srgrimes (p)->fts_path = addr; \ 114164740Sgreen} while (0) 11421573Srgrimes /* Adjust the current set of children. */ 11431573Srgrimes for (p = sp->fts_child; p; p = p->fts_link) 114454770Sgreen ADJUST(p); 11451573Srgrimes 114654770Sgreen /* Adjust the rest of the tree, including the current level. */ 114754770Sgreen for (p = head; p->fts_level >= FTS_ROOTLEVEL;) { 114854770Sgreen ADJUST(p); 11491573Srgrimes p = p->fts_link ? p->fts_link : p->fts_parent; 11501573Srgrimes } 11511573Srgrimes} 11521573Srgrimes 11531573Srgrimesstatic size_t 11541573Srgrimesfts_maxarglen(argv) 11551573Srgrimes char * const *argv; 11561573Srgrimes{ 11571573Srgrimes size_t len, max; 11581573Srgrimes 11591573Srgrimes for (max = 0; *argv; ++argv) 11601573Srgrimes if ((len = strlen(*argv)) > max) 11611573Srgrimes max = len; 116254770Sgreen return (max + 1); 11631573Srgrimes} 116428913Simp 116528913Simp/* 116628913Simp * Change to dir specified by fd or p->fts_accpath without getting 116728913Simp * tricked by someone changing the world out from underneath us. 116828913Simp * Assumes p->fts_dev and p->fts_ino are filled in. 116928913Simp */ 117028913Simpstatic int 117177599Skrisfts_safe_changedir(sp, p, fd, path) 117228913Simp FTS *sp; 117328913Simp FTSENT *p; 117428913Simp int fd; 117577599Skris char *path; 117628913Simp{ 117728913Simp int ret, oerrno, newfd; 117828913Simp struct stat sb; 117928913Simp 118028913Simp newfd = fd; 118128913Simp if (ISSET(FTS_NOCHDIR)) 118228913Simp return (0); 1183247273Sjilles if (fd < 0 && (newfd = _open(path, O_RDONLY | O_CLOEXEC, 0)) < 0) 118428913Simp return (-1); 118571579Sdeischen if (_fstat(newfd, &sb)) { 118628913Simp ret = -1; 118728913Simp goto bail; 118828913Simp } 118928913Simp if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) { 119028913Simp errno = ENOENT; /* disinformation */ 119128913Simp ret = -1; 119228913Simp goto bail; 119328913Simp } 119428913Simp ret = fchdir(newfd); 119528913Simpbail: 119628913Simp oerrno = errno; 119728913Simp if (fd < 0) 119856698Sjasone (void)_close(newfd); 119928913Simp errno = oerrno; 120028913Simp return (ret); 120128913Simp} 1202129052Speadar 1203129052Speadar/* 1204129052Speadar * Check if the filesystem for "ent" has UFS-style links. 1205129052Speadar */ 1206129052Speadarstatic int 1207129052Speadarfts_ufslinks(FTS *sp, const FTSENT *ent) 1208129052Speadar{ 1209129052Speadar struct _fts_private *priv; 1210129052Speadar const char **cpp; 1211129052Speadar 1212129161Speadar priv = (struct _fts_private *)sp; 1213129052Speadar /* 1214129052Speadar * If this node's device is different from the previous, grab 1215129052Speadar * the filesystem information, and decide on the reliability 1216129052Speadar * of the link information from this filesystem for stat(2) 1217129052Speadar * avoidance. 1218129052Speadar */ 1219129052Speadar if (priv->ftsp_dev != ent->fts_dev) { 1220129052Speadar if (statfs(ent->fts_path, &priv->ftsp_statfs) != -1) { 1221129052Speadar priv->ftsp_dev = ent->fts_dev; 1222129052Speadar priv->ftsp_linksreliable = 0; 1223129052Speadar for (cpp = ufslike_filesystems; *cpp; cpp++) { 1224129052Speadar if (strcmp(priv->ftsp_statfs.f_fstypename, 1225129052Speadar *cpp) == 0) { 1226129052Speadar priv->ftsp_linksreliable = 1; 1227129052Speadar break; 1228129052Speadar } 1229129052Speadar } 1230129052Speadar } else { 1231129052Speadar priv->ftsp_linksreliable = 0; 1232129052Speadar } 1233129052Speadar } 1234129161Speadar return (priv->ftsp_linksreliable); 1235129052Speadar} 1236175688Syar 1237175688Syar__sym_compat(fts_open, __fts_open_44bsd, FBSD_1.0); 1238175688Syar__sym_compat(fts_close, __fts_close_44bsd, FBSD_1.0); 1239175688Syar__sym_compat(fts_read, __fts_read_44bsd, FBSD_1.0); 1240175688Syar__sym_compat(fts_set, __fts_set_44bsd, FBSD_1.0); 1241175688Syar__sym_compat(fts_children, __fts_children_44bsd, FBSD_1.0); 1242175688Syar__sym_compat(fts_get_clientptr, __fts_get_clientptr_44bsd, FBSD_1.0); 1243175688Syar__sym_compat(fts_get_stream, __fts_get_stream_44bsd, FBSD_1.0); 1244175688Syar__sym_compat(fts_set_clientptr, __fts_set_clientptr_44bsd, FBSD_1.0); 1245