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 <fts.h> 501573Srgrimes#include <stdlib.h> 511573Srgrimes#include <string.h> 521573Srgrimes#include <unistd.h> 5371579Sdeischen#include "un-namespace.h" 541573Srgrimes 55175688Syarstatic FTSENT *fts_alloc(FTS *, char *, size_t); 5690045Sobrienstatic FTSENT *fts_build(FTS *, int); 5790045Sobrienstatic void fts_lfree(FTSENT *); 5890045Sobrienstatic void fts_load(FTS *, FTSENT *); 5990045Sobrienstatic size_t fts_maxarglen(char * const *); 6090045Sobrienstatic void fts_padjust(FTS *, FTSENT *); 6190045Sobrienstatic int fts_palloc(FTS *, size_t); 62175688Syarstatic FTSENT *fts_sort(FTS *, FTSENT *, size_t); 63175688Syarstatic int fts_stat(FTS *, FTSENT *, int); 6490045Sobrienstatic int fts_safe_changedir(FTS *, FTSENT *, int, char *); 65129161Speadarstatic int fts_ufslinks(FTS *, const FTSENT *); 661573Srgrimes 6728913Simp#define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2]))) 681573Srgrimes 6928913Simp#define CLR(opt) (sp->fts_options &= ~(opt)) 7028913Simp#define ISSET(opt) (sp->fts_options & (opt)) 7128913Simp#define SET(opt) (sp->fts_options |= (opt)) 721573Srgrimes 731573Srgrimes#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd)) 741573Srgrimes 751573Srgrimes/* fts_build flags */ 761573Srgrimes#define BCHILD 1 /* fts_children */ 771573Srgrimes#define BNAMES 2 /* fts_children, names only */ 781573Srgrimes#define BREAD 3 /* fts_read */ 791573Srgrimes 80129052Speadar/* 81129161Speadar * Internal representation of an FTS, including extra implementation 82129161Speadar * details. The FTS returned from fts_open points to this structure's 83129161Speadar * ftsp_fts member (and can be cast to an _fts_private as required) 84129052Speadar */ 85129052Speadarstruct _fts_private { 86129161Speadar FTS ftsp_fts; 87129161Speadar struct statfs ftsp_statfs; 88129161Speadar dev_t ftsp_dev; 89129161Speadar int ftsp_linksreliable; 90129052Speadar}; 91129052Speadar 92129052Speadar/* 93129161Speadar * The "FTS_NOSTAT" option can avoid a lot of calls to stat(2) if it 94129161Speadar * knows that a directory could not possibly have subdirectories. This 95129161Speadar * is decided by looking at the link count: a subdirectory would 96129161Speadar * increment its parent's link count by virtue of its own ".." entry. 97129161Speadar * This assumption only holds for UFS-like filesystems that implement 98129161Speadar * links and directories this way, so we must punt for others. 99129052Speadar */ 100129052Speadar 101129052Speadarstatic const char *ufslike_filesystems[] = { 102129052Speadar "ufs", 103219696Spjd "zfs", 104129052Speadar "nfs", 105129052Speadar "nfs4", 106129052Speadar "ext2fs", 107129052Speadar 0 108129052Speadar}; 109129052Speadar 1101573SrgrimesFTS * 1111573Srgrimesfts_open(argv, options, compar) 1121573Srgrimes char * const *argv; 11390045Sobrien int options; 114103726Swollman int (*compar)(const FTSENT * const *, const FTSENT * const *); 1151573Srgrimes{ 116129052Speadar struct _fts_private *priv; 11790045Sobrien FTS *sp; 11890045Sobrien FTSENT *p, *root; 1191573Srgrimes FTSENT *parent, *tmp; 120175688Syar size_t len, nitems; 1211573Srgrimes 1221573Srgrimes /* Options check. */ 1231573Srgrimes if (options & ~FTS_OPTIONMASK) { 1241573Srgrimes errno = EINVAL; 1251573Srgrimes return (NULL); 1261573Srgrimes } 1271573Srgrimes 128197793Sdelphij /* fts_open() requires at least one path */ 129197793Sdelphij if (*argv == NULL) { 130197793Sdelphij errno = EINVAL; 131197793Sdelphij return (NULL); 132197793Sdelphij } 133197793Sdelphij 134129184Sbde /* Allocate/initialize the stream. */ 135129161Speadar if ((priv = malloc(sizeof(*priv))) == NULL) 1361573Srgrimes return (NULL); 137129161Speadar memset(priv, 0, sizeof(*priv)); 138129052Speadar sp = &priv->ftsp_fts; 1391573Srgrimes sp->fts_compar = compar; 1401573Srgrimes sp->fts_options = options; 1411573Srgrimes 14254770Sgreen /* Shush, GCC. */ 14354770Sgreen tmp = NULL; 14454770Sgreen 1451573Srgrimes /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ 1461573Srgrimes if (ISSET(FTS_LOGICAL)) 1471573Srgrimes SET(FTS_NOCHDIR); 1481573Srgrimes 1491573Srgrimes /* 1501573Srgrimes * Start out with 1K of path space, and enough, in any case, 1511573Srgrimes * to hold the user's paths. 1521573Srgrimes */ 1531573Srgrimes if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN))) 1541573Srgrimes goto mem1; 1551573Srgrimes 1561573Srgrimes /* Allocate/initialize root's parent. */ 1571573Srgrimes if ((parent = fts_alloc(sp, "", 0)) == NULL) 1581573Srgrimes goto mem2; 1591573Srgrimes parent->fts_level = FTS_ROOTPARENTLEVEL; 1601573Srgrimes 1611573Srgrimes /* Allocate/initialize root(s). */ 16264740Sgreen for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) { 1631573Srgrimes /* Don't allow zero-length paths. */ 1641573Srgrimes if ((len = strlen(*argv)) == 0) { 1651573Srgrimes errno = ENOENT; 1661573Srgrimes goto mem3; 1671573Srgrimes } 1681573Srgrimes 1691573Srgrimes p = fts_alloc(sp, *argv, len); 1701573Srgrimes p->fts_level = FTS_ROOTLEVEL; 1711573Srgrimes p->fts_parent = parent; 1721573Srgrimes p->fts_accpath = p->fts_name; 1731573Srgrimes p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW)); 1741573Srgrimes 1751573Srgrimes /* Command-line "." and ".." are real directories. */ 1761573Srgrimes if (p->fts_info == FTS_DOT) 1771573Srgrimes p->fts_info = FTS_D; 1781573Srgrimes 1791573Srgrimes /* 1801573Srgrimes * If comparison routine supplied, traverse in sorted 1811573Srgrimes * order; otherwise traverse in the order specified. 1821573Srgrimes */ 1831573Srgrimes if (compar) { 1841573Srgrimes p->fts_link = root; 1851573Srgrimes root = p; 1861573Srgrimes } else { 1871573Srgrimes p->fts_link = NULL; 1881573Srgrimes if (root == NULL) 1891573Srgrimes tmp = root = p; 1901573Srgrimes else { 1911573Srgrimes tmp->fts_link = p; 1921573Srgrimes tmp = p; 1931573Srgrimes } 1941573Srgrimes } 1951573Srgrimes } 1961573Srgrimes if (compar && nitems > 1) 1971573Srgrimes root = fts_sort(sp, root, nitems); 1981573Srgrimes 1991573Srgrimes /* 2001573Srgrimes * Allocate a dummy pointer and make fts_read think that we've just 2011573Srgrimes * finished the node before the root(s); set p->fts_info to FTS_INIT 2021573Srgrimes * so that everything about the "current" node is ignored. 2031573Srgrimes */ 2041573Srgrimes if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL) 2051573Srgrimes goto mem3; 2061573Srgrimes sp->fts_cur->fts_link = root; 2071573Srgrimes sp->fts_cur->fts_info = FTS_INIT; 2081573Srgrimes 2091573Srgrimes /* 21054770Sgreen * If using chdir(2), grab a file descriptor pointing to dot to ensure 2111573Srgrimes * that we can get back here; this could be avoided for some paths, 2121573Srgrimes * but almost certainly not worth the effort. Slashes, symbolic links, 2131573Srgrimes * and ".." are all fairly nasty problems. Note, if we can't get the 2141573Srgrimes * descriptor we run anyway, just more slowly. 2151573Srgrimes */ 216247273Sjilles if (!ISSET(FTS_NOCHDIR) && 217247273Sjilles (sp->fts_rfd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) 2181573Srgrimes SET(FTS_NOCHDIR); 2191573Srgrimes 2201573Srgrimes return (sp); 2211573Srgrimes 2221573Srgrimesmem3: fts_lfree(root); 2231573Srgrimes free(parent); 2241573Srgrimesmem2: free(sp->fts_path); 2251573Srgrimesmem1: free(sp); 2261573Srgrimes return (NULL); 2271573Srgrimes} 2281573Srgrimes 2291573Srgrimesstatic void 2301573Srgrimesfts_load(sp, p) 2311573Srgrimes FTS *sp; 23290045Sobrien FTSENT *p; 2331573Srgrimes{ 234175688Syar size_t len; 23590045Sobrien char *cp; 2361573Srgrimes 2371573Srgrimes /* 2381573Srgrimes * Load the stream structure for the next traversal. Since we don't 2391573Srgrimes * actually enter the directory until after the preorder visit, set 2401573Srgrimes * the fts_accpath field specially so the chdir gets done to the right 2411573Srgrimes * place and the user can access the first node. From fts_open it's 2421573Srgrimes * known that the path will fit. 2431573Srgrimes */ 2441573Srgrimes len = p->fts_pathlen = p->fts_namelen; 2451573Srgrimes memmove(sp->fts_path, p->fts_name, len + 1); 2461573Srgrimes if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { 2471573Srgrimes len = strlen(++cp); 2481573Srgrimes memmove(p->fts_name, cp, len + 1); 2491573Srgrimes p->fts_namelen = len; 2501573Srgrimes } 2511573Srgrimes p->fts_accpath = p->fts_path = sp->fts_path; 2521573Srgrimes sp->fts_dev = p->fts_dev; 2531573Srgrimes} 2541573Srgrimes 2551573Srgrimesint 2561573Srgrimesfts_close(sp) 2571573Srgrimes FTS *sp; 2581573Srgrimes{ 25990045Sobrien FTSENT *freep, *p; 2601573Srgrimes int saved_errno; 2611573Srgrimes 2621573Srgrimes /* 2631573Srgrimes * This still works if we haven't read anything -- the dummy structure 2641573Srgrimes * points to the root list, so we step through to the end of the root 2651573Srgrimes * list which has a valid parent pointer. 2661573Srgrimes */ 2671573Srgrimes if (sp->fts_cur) { 2681573Srgrimes for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { 2691573Srgrimes freep = p; 27064740Sgreen p = p->fts_link != NULL ? p->fts_link : p->fts_parent; 2711573Srgrimes free(freep); 2721573Srgrimes } 2731573Srgrimes free(p); 2741573Srgrimes } 2751573Srgrimes 2761573Srgrimes /* Free up child linked list, sort array, path buffer. */ 2771573Srgrimes if (sp->fts_child) 2781573Srgrimes fts_lfree(sp->fts_child); 2791573Srgrimes if (sp->fts_array) 2801573Srgrimes free(sp->fts_array); 2811573Srgrimes free(sp->fts_path); 2821573Srgrimes 2831573Srgrimes /* Return to original directory, save errno if necessary. */ 2841573Srgrimes if (!ISSET(FTS_NOCHDIR)) { 2851573Srgrimes saved_errno = fchdir(sp->fts_rfd) ? errno : 0; 28656698Sjasone (void)_close(sp->fts_rfd); 28754770Sgreen 28854770Sgreen /* Set errno and return. */ 28954770Sgreen if (saved_errno != 0) { 29054770Sgreen /* Free up the stream pointer. */ 29154770Sgreen free(sp); 29254770Sgreen errno = saved_errno; 29354770Sgreen return (-1); 29454770Sgreen } 2951573Srgrimes } 2961573Srgrimes 29737349Sphk /* Free up the stream pointer. */ 29837349Sphk free(sp); 2991573Srgrimes return (0); 3001573Srgrimes} 3011573Srgrimes 3021573Srgrimes/* 30328913Simp * Special case of "/" at the end of the path so that slashes aren't 30428913Simp * appended which would cause paths to be written as "....//foo". 3051573Srgrimes */ 3061573Srgrimes#define NAPPEND(p) \ 30728913Simp (p->fts_path[p->fts_pathlen - 1] == '/' \ 30828913Simp ? p->fts_pathlen - 1 : p->fts_pathlen) 3091573Srgrimes 3101573SrgrimesFTSENT * 3111573Srgrimesfts_read(sp) 31290045Sobrien FTS *sp; 3131573Srgrimes{ 31490045Sobrien FTSENT *p, *tmp; 31590045Sobrien int instr; 31690045Sobrien char *t; 3171573Srgrimes int saved_errno; 3181573Srgrimes 3191573Srgrimes /* If finished or unrecoverable error, return NULL. */ 3201573Srgrimes if (sp->fts_cur == NULL || ISSET(FTS_STOP)) 3211573Srgrimes return (NULL); 3221573Srgrimes 3231573Srgrimes /* Set current node pointer. */ 3241573Srgrimes p = sp->fts_cur; 3251573Srgrimes 3261573Srgrimes /* Save and zero out user instructions. */ 3271573Srgrimes instr = p->fts_instr; 3281573Srgrimes p->fts_instr = FTS_NOINSTR; 3291573Srgrimes 3301573Srgrimes /* Any type of file may be re-visited; re-stat and re-turn. */ 3311573Srgrimes if (instr == FTS_AGAIN) { 3321573Srgrimes p->fts_info = fts_stat(sp, p, 0); 3331573Srgrimes return (p); 3341573Srgrimes } 3351573Srgrimes 3361573Srgrimes /* 3371573Srgrimes * Following a symlink -- SLNONE test allows application to see 3381573Srgrimes * SLNONE and recover. If indirecting through a symlink, have 3391573Srgrimes * keep a pointer to current location. If unable to get that 3401573Srgrimes * pointer, follow fails. 3411573Srgrimes */ 3421573Srgrimes if (instr == FTS_FOLLOW && 3431573Srgrimes (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { 3441573Srgrimes p->fts_info = fts_stat(sp, p, 1); 34554770Sgreen if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { 346247273Sjilles if ((p->fts_symfd = _open(".", O_RDONLY | O_CLOEXEC, 347247273Sjilles 0)) < 0) { 3481573Srgrimes p->fts_errno = errno; 3491573Srgrimes p->fts_info = FTS_ERR; 3501573Srgrimes } else 3511573Srgrimes p->fts_flags |= FTS_SYMFOLLOW; 35254770Sgreen } 3531573Srgrimes return (p); 3541573Srgrimes } 3551573Srgrimes 3561573Srgrimes /* Directory in pre-order. */ 3571573Srgrimes if (p->fts_info == FTS_D) { 3581573Srgrimes /* If skipped or crossed mount point, do post-order visit. */ 3591573Srgrimes if (instr == FTS_SKIP || 36028913Simp (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) { 3611573Srgrimes if (p->fts_flags & FTS_SYMFOLLOW) 36256698Sjasone (void)_close(p->fts_symfd); 3631573Srgrimes if (sp->fts_child) { 3641573Srgrimes fts_lfree(sp->fts_child); 3651573Srgrimes sp->fts_child = NULL; 3661573Srgrimes } 3671573Srgrimes p->fts_info = FTS_DP; 3681573Srgrimes return (p); 3698870Srgrimes } 3701573Srgrimes 3711573Srgrimes /* Rebuild if only read the names and now traversing. */ 37264740Sgreen if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) { 37328913Simp CLR(FTS_NAMEONLY); 3741573Srgrimes fts_lfree(sp->fts_child); 3751573Srgrimes sp->fts_child = NULL; 3761573Srgrimes } 3771573Srgrimes 3781573Srgrimes /* 3791573Srgrimes * Cd to the subdirectory. 3801573Srgrimes * 3811573Srgrimes * If have already read and now fail to chdir, whack the list 3821573Srgrimes * to make the names come out right, and set the parent errno 3831573Srgrimes * so the application will eventually get an error condition. 3841573Srgrimes * Set the FTS_DONTCHDIR flag so that when we logically change 3851573Srgrimes * directories back to the parent we don't do a chdir. 3861573Srgrimes * 3871573Srgrimes * If haven't read do so. If the read fails, fts_build sets 3881573Srgrimes * FTS_STOP or the fts_info field of the node. 3891573Srgrimes */ 39064740Sgreen if (sp->fts_child != NULL) { 39177599Skris if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) { 3921573Srgrimes p->fts_errno = errno; 3931573Srgrimes p->fts_flags |= FTS_DONTCHDIR; 394129184Sbde for (p = sp->fts_child; p != NULL; 39564740Sgreen p = p->fts_link) 3961573Srgrimes p->fts_accpath = 3971573Srgrimes p->fts_parent->fts_accpath; 3981573Srgrimes } 3991573Srgrimes } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) { 4001573Srgrimes if (ISSET(FTS_STOP)) 4011573Srgrimes return (NULL); 4021573Srgrimes return (p); 4031573Srgrimes } 4041573Srgrimes p = sp->fts_child; 4051573Srgrimes sp->fts_child = NULL; 4061573Srgrimes goto name; 4071573Srgrimes } 4081573Srgrimes 4091573Srgrimes /* Move to the next node on this level. */ 4101573Srgrimesnext: tmp = p; 41164740Sgreen if ((p = p->fts_link) != NULL) { 4121573Srgrimes free(tmp); 4131573Srgrimes 4141573Srgrimes /* 41554770Sgreen * If reached the top, return to the original directory (or 41654770Sgreen * the root of the tree), and load the paths for the next root. 4171573Srgrimes */ 4181573Srgrimes if (p->fts_level == FTS_ROOTLEVEL) { 41928913Simp if (FCHDIR(sp, sp->fts_rfd)) { 4201573Srgrimes SET(FTS_STOP); 4211573Srgrimes return (NULL); 4221573Srgrimes } 4231573Srgrimes fts_load(sp, p); 4241573Srgrimes return (sp->fts_cur = p); 4251573Srgrimes } 4261573Srgrimes 4271573Srgrimes /* 4281573Srgrimes * User may have called fts_set on the node. If skipped, 4291573Srgrimes * ignore. If followed, get a file descriptor so we can 4301573Srgrimes * get back if necessary. 4311573Srgrimes */ 4321573Srgrimes if (p->fts_instr == FTS_SKIP) 4331573Srgrimes goto next; 4341573Srgrimes if (p->fts_instr == FTS_FOLLOW) { 4351573Srgrimes p->fts_info = fts_stat(sp, p, 1); 43654770Sgreen if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { 4371573Srgrimes if ((p->fts_symfd = 438247273Sjilles _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) { 4391573Srgrimes p->fts_errno = errno; 4401573Srgrimes p->fts_info = FTS_ERR; 4411573Srgrimes } else 4421573Srgrimes p->fts_flags |= FTS_SYMFOLLOW; 44354770Sgreen } 4441573Srgrimes p->fts_instr = FTS_NOINSTR; 4451573Srgrimes } 4461573Srgrimes 4471573Srgrimesname: t = sp->fts_path + NAPPEND(p->fts_parent); 4481573Srgrimes *t++ = '/'; 4491573Srgrimes memmove(t, p->fts_name, p->fts_namelen + 1); 4501573Srgrimes return (sp->fts_cur = p); 4511573Srgrimes } 4521573Srgrimes 4531573Srgrimes /* Move up to the parent node. */ 4541573Srgrimes p = tmp->fts_parent; 4551573Srgrimes free(tmp); 4561573Srgrimes 4571573Srgrimes if (p->fts_level == FTS_ROOTPARENTLEVEL) { 4581573Srgrimes /* 4591573Srgrimes * Done; free everything up and set errno to 0 so the user 4601573Srgrimes * can distinguish between error and EOF. 4611573Srgrimes */ 4621573Srgrimes free(p); 4631573Srgrimes errno = 0; 4641573Srgrimes return (sp->fts_cur = NULL); 4651573Srgrimes } 4661573Srgrimes 46754770Sgreen /* NUL terminate the pathname. */ 4681573Srgrimes sp->fts_path[p->fts_pathlen] = '\0'; 4691573Srgrimes 4701573Srgrimes /* 4711573Srgrimes * Return to the parent directory. If at a root node or came through 4721573Srgrimes * a symlink, go back through the file descriptor. Otherwise, cd up 4731573Srgrimes * one directory. 4741573Srgrimes */ 4751573Srgrimes if (p->fts_level == FTS_ROOTLEVEL) { 47628913Simp if (FCHDIR(sp, sp->fts_rfd)) { 4771573Srgrimes SET(FTS_STOP); 4781573Srgrimes return (NULL); 4791573Srgrimes } 4801573Srgrimes } else if (p->fts_flags & FTS_SYMFOLLOW) { 4811573Srgrimes if (FCHDIR(sp, p->fts_symfd)) { 4821573Srgrimes saved_errno = errno; 48356698Sjasone (void)_close(p->fts_symfd); 4841573Srgrimes errno = saved_errno; 4851573Srgrimes SET(FTS_STOP); 4861573Srgrimes return (NULL); 4871573Srgrimes } 48856698Sjasone (void)_close(p->fts_symfd); 48977497Skris } else if (!(p->fts_flags & FTS_DONTCHDIR) && 490129184Sbde fts_safe_changedir(sp, p->fts_parent, -1, "..")) { 49177599Skris SET(FTS_STOP); 49277599Skris return (NULL); 4931573Srgrimes } 4941573Srgrimes p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP; 4951573Srgrimes return (sp->fts_cur = p); 4961573Srgrimes} 4971573Srgrimes 4981573Srgrimes/* 4991573Srgrimes * Fts_set takes the stream as an argument although it's not used in this 5001573Srgrimes * implementation; it would be necessary if anyone wanted to add global 5011573Srgrimes * semantics to fts using fts_set. An error return is allowed for similar 5021573Srgrimes * reasons. 5031573Srgrimes */ 5041573Srgrimes/* ARGSUSED */ 5051573Srgrimesint 5061573Srgrimesfts_set(sp, p, instr) 5071573Srgrimes FTS *sp; 5081573Srgrimes FTSENT *p; 5091573Srgrimes int instr; 5101573Srgrimes{ 51164740Sgreen if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW && 5121573Srgrimes instr != FTS_NOINSTR && instr != FTS_SKIP) { 5131573Srgrimes errno = EINVAL; 5141573Srgrimes return (1); 5151573Srgrimes } 5161573Srgrimes p->fts_instr = instr; 5171573Srgrimes return (0); 5181573Srgrimes} 5191573Srgrimes 5201573SrgrimesFTSENT * 5211573Srgrimesfts_children(sp, instr) 52290045Sobrien FTS *sp; 5231573Srgrimes int instr; 5241573Srgrimes{ 52590045Sobrien FTSENT *p; 5261573Srgrimes int fd; 5271573Srgrimes 52864740Sgreen if (instr != 0 && instr != FTS_NAMEONLY) { 5291573Srgrimes errno = EINVAL; 5301573Srgrimes return (NULL); 5311573Srgrimes } 5321573Srgrimes 5331573Srgrimes /* Set current node pointer. */ 5341573Srgrimes p = sp->fts_cur; 5351573Srgrimes 5361573Srgrimes /* 5371573Srgrimes * Errno set to 0 so user can distinguish empty directory from 5381573Srgrimes * an error. 5391573Srgrimes */ 5401573Srgrimes errno = 0; 5411573Srgrimes 5421573Srgrimes /* Fatal errors stop here. */ 5431573Srgrimes if (ISSET(FTS_STOP)) 5441573Srgrimes return (NULL); 5451573Srgrimes 5461573Srgrimes /* Return logical hierarchy of user's arguments. */ 5471573Srgrimes if (p->fts_info == FTS_INIT) 5481573Srgrimes return (p->fts_link); 5491573Srgrimes 5501573Srgrimes /* 5511573Srgrimes * If not a directory being visited in pre-order, stop here. Could 5521573Srgrimes * allow FTS_DNR, assuming the user has fixed the problem, but the 5531573Srgrimes * same effect is available with FTS_AGAIN. 5541573Srgrimes */ 5551573Srgrimes if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */) 5561573Srgrimes return (NULL); 5571573Srgrimes 5581573Srgrimes /* Free up any previous child list. */ 55964740Sgreen if (sp->fts_child != NULL) 5601573Srgrimes fts_lfree(sp->fts_child); 5611573Srgrimes 5621573Srgrimes if (instr == FTS_NAMEONLY) { 56328913Simp SET(FTS_NAMEONLY); 5641573Srgrimes instr = BNAMES; 5658870Srgrimes } else 5661573Srgrimes instr = BCHILD; 5671573Srgrimes 5681573Srgrimes /* 5691573Srgrimes * If using chdir on a relative path and called BEFORE fts_read does 5701573Srgrimes * its chdir to the root of a traversal, we can lose -- we need to 5711573Srgrimes * chdir into the subdirectory, and we don't know where the current 5721573Srgrimes * directory is, so we can't get back so that the upcoming chdir by 5731573Srgrimes * fts_read will work. 5741573Srgrimes */ 5751573Srgrimes if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || 5761573Srgrimes ISSET(FTS_NOCHDIR)) 5771573Srgrimes return (sp->fts_child = fts_build(sp, instr)); 5781573Srgrimes 579247273Sjilles if ((fd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) 5801573Srgrimes return (NULL); 5811573Srgrimes sp->fts_child = fts_build(sp, instr); 582189348Sdas if (fchdir(fd)) { 583189348Sdas (void)_close(fd); 5841573Srgrimes return (NULL); 585189348Sdas } 58656698Sjasone (void)_close(fd); 5871573Srgrimes return (sp->fts_child); 5881573Srgrimes} 5891573Srgrimes 590103726Swollman#ifndef fts_get_clientptr 591103726Swollman#error "fts_get_clientptr not defined" 592103726Swollman#endif 593103726Swollman 594103726Swollmanvoid * 595103726Swollman(fts_get_clientptr)(FTS *sp) 596103726Swollman{ 597103726Swollman 598103726Swollman return (fts_get_clientptr(sp)); 599103726Swollman} 600103726Swollman 601103726Swollman#ifndef fts_get_stream 602103726Swollman#error "fts_get_stream not defined" 603103726Swollman#endif 604103726Swollman 605103726SwollmanFTS * 606103726Swollman(fts_get_stream)(FTSENT *p) 607103726Swollman{ 608103726Swollman return (fts_get_stream(p)); 609103726Swollman} 610103726Swollman 611103726Swollmanvoid 612103726Swollmanfts_set_clientptr(FTS *sp, void *clientptr) 613103726Swollman{ 614103726Swollman 615103726Swollman sp->fts_clientptr = clientptr; 616103726Swollman} 617103726Swollman 6181573Srgrimes/* 6191573Srgrimes * This is the tricky part -- do not casually change *anything* in here. The 6201573Srgrimes * idea is to build the linked list of entries that are used by fts_children 6211573Srgrimes * and fts_read. There are lots of special cases. 6221573Srgrimes * 6231573Srgrimes * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is 6241573Srgrimes * set and it's a physical walk (so that symbolic links can't be directories), 6251573Srgrimes * we can do things quickly. First, if it's a 4.4BSD file system, the type 6261573Srgrimes * of the file is in the directory entry. Otherwise, we assume that the number 6271573Srgrimes * of subdirectories in a node is equal to the number of links to the parent. 6281573Srgrimes * The former skips all stat calls. The latter skips stat calls in any leaf 6291573Srgrimes * directories and for any files after the subdirectories in the directory have 6301573Srgrimes * been found, cutting the stat calls by about 2/3. 6311573Srgrimes */ 6321573Srgrimesstatic FTSENT * 6331573Srgrimesfts_build(sp, type) 63490045Sobrien FTS *sp; 6351573Srgrimes int type; 6361573Srgrimes{ 63790045Sobrien struct dirent *dp; 63890045Sobrien FTSENT *p, *head; 6391573Srgrimes FTSENT *cur, *tail; 6401573Srgrimes DIR *dirp; 64154770Sgreen void *oldaddr; 6421573Srgrimes char *cp; 643175688Syar int cderrno, descend, oflag, saved_errno, nostat, doadjust; 644175688Syar long level; 645175688Syar long nlinks; /* has to be signed because -1 is a magic value */ 646175688Syar size_t dnamlen, len, maxlen, nitems; 6471573Srgrimes 6481573Srgrimes /* Set current node pointer. */ 6491573Srgrimes cur = sp->fts_cur; 6501573Srgrimes 6511573Srgrimes /* 6521573Srgrimes * Open the directory for reading. If this fails, we're done. 6531573Srgrimes * If being called from fts_read, set the fts_info field. 6541573Srgrimes */ 65523668Speter#ifdef FTS_WHITEOUT 65623668Speter if (ISSET(FTS_WHITEOUT)) 657129184Sbde oflag = DTF_NODUP | DTF_REWIND; 65823668Speter else 659129184Sbde oflag = DTF_HIDEW | DTF_NODUP | DTF_REWIND; 66023668Speter#else 66123668Speter#define __opendir2(path, flag) opendir(path) 66223668Speter#endif 66323668Speter if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) { 6641573Srgrimes if (type == BREAD) { 6651573Srgrimes cur->fts_info = FTS_DNR; 6661573Srgrimes cur->fts_errno = errno; 6671573Srgrimes } 6681573Srgrimes return (NULL); 6691573Srgrimes } 6701573Srgrimes 6711573Srgrimes /* 6721573Srgrimes * Nlinks is the number of possible entries of type directory in the 6731573Srgrimes * directory if we're cheating on stat calls, 0 if we're not doing 6741573Srgrimes * any stat calls at all, -1 if we're doing stats on everything. 6751573Srgrimes */ 67654770Sgreen if (type == BNAMES) { 6771573Srgrimes nlinks = 0; 67854770Sgreen /* Be quiet about nostat, GCC. */ 67954770Sgreen nostat = 0; 68054770Sgreen } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) { 681129052Speadar if (fts_ufslinks(sp, cur)) 682129052Speadar nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2); 683129052Speadar else 684129052Speadar nlinks = -1; 68554770Sgreen nostat = 1; 68654770Sgreen } else { 6871573Srgrimes nlinks = -1; 68854770Sgreen nostat = 0; 68954770Sgreen } 6901573Srgrimes 6911573Srgrimes#ifdef notdef 6921573Srgrimes (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink); 6931573Srgrimes (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n", 6941573Srgrimes ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT)); 6951573Srgrimes#endif 6961573Srgrimes /* 6971573Srgrimes * If we're going to need to stat anything or we want to descend 6981573Srgrimes * and stay in the directory, chdir. If this fails we keep going, 6991573Srgrimes * but set a flag so we don't chdir after the post-order visit. 7001573Srgrimes * We won't be able to stat anything, but we can still return the 7011573Srgrimes * names themselves. Note, that since fts_read won't be able to 7021573Srgrimes * chdir into the directory, it will have to return different path 7031573Srgrimes * names than before, i.e. "a/b" instead of "b". Since the node 7041573Srgrimes * has already been visited in pre-order, have to wait until the 7051573Srgrimes * post-order visit to return the error. There is a special case 7061573Srgrimes * here, if there was nothing to stat then it's not an error to 7071573Srgrimes * not be able to stat. This is all fairly nasty. If a program 7081573Srgrimes * needed sorted entries or stat information, they had better be 7091573Srgrimes * checking FTS_NS on the returned nodes. 7101573Srgrimes */ 7111573Srgrimes cderrno = 0; 71254770Sgreen if (nlinks || type == BREAD) { 71377599Skris if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) { 7141573Srgrimes if (nlinks && type == BREAD) 7151573Srgrimes cur->fts_errno = errno; 7161573Srgrimes cur->fts_flags |= FTS_DONTCHDIR; 7171573Srgrimes descend = 0; 7181573Srgrimes cderrno = errno; 7191573Srgrimes } else 7201573Srgrimes descend = 1; 72154770Sgreen } else 7221573Srgrimes descend = 0; 7231573Srgrimes 7241573Srgrimes /* 7251573Srgrimes * Figure out the max file name length that can be stored in the 7261573Srgrimes * current path -- the inner loop allocates more path as necessary. 7271573Srgrimes * We really wouldn't have to do the maxlen calculations here, we 7281573Srgrimes * could do them in fts_read before returning the path, but it's a 7291573Srgrimes * lot easier here since the length is part of the dirent structure. 7301573Srgrimes * 7311573Srgrimes * If not changing directories set a pointer so that can just append 7321573Srgrimes * each new name into the path. 7331573Srgrimes */ 7341573Srgrimes len = NAPPEND(cur); 7351573Srgrimes if (ISSET(FTS_NOCHDIR)) { 7361573Srgrimes cp = sp->fts_path + len; 7371573Srgrimes *cp++ = '/'; 73854770Sgreen } else { 73954770Sgreen /* GCC, you're too verbose. */ 74054770Sgreen cp = NULL; 7411573Srgrimes } 74254770Sgreen len++; 74354770Sgreen maxlen = sp->fts_pathlen - len; 7441573Srgrimes 7451573Srgrimes level = cur->fts_level + 1; 7461573Srgrimes 7471573Srgrimes /* Read the directory, attaching each entry to the `link' pointer. */ 74854770Sgreen doadjust = 0; 74928913Simp for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) { 750128946Skientzle dnamlen = dp->d_namlen; 7511573Srgrimes if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) 7521573Srgrimes continue; 7531573Srgrimes 754175688Syar if ((p = fts_alloc(sp, dp->d_name, dnamlen)) == NULL) 7551573Srgrimes goto mem1; 756128946Skientzle if (dnamlen >= maxlen) { /* include space for NUL */ 75754770Sgreen oldaddr = sp->fts_path; 758128946Skientzle if (fts_palloc(sp, dnamlen + len + 1)) { 7591573Srgrimes /* 7601573Srgrimes * No more memory for path or structures. Save 7611573Srgrimes * errno, free up the current structure and the 7621573Srgrimes * structures already allocated. 7631573Srgrimes */ 7641573Srgrimesmem1: saved_errno = errno; 7651573Srgrimes if (p) 7661573Srgrimes free(p); 7671573Srgrimes fts_lfree(head); 7681573Srgrimes (void)closedir(dirp); 7691573Srgrimes cur->fts_info = FTS_ERR; 7701573Srgrimes SET(FTS_STOP); 77154770Sgreen errno = saved_errno; 7721573Srgrimes return (NULL); 7731573Srgrimes } 77454770Sgreen /* Did realloc() change the pointer? */ 77554770Sgreen if (oldaddr != sp->fts_path) { 77654770Sgreen doadjust = 1; 77754770Sgreen if (ISSET(FTS_NOCHDIR)) 77854770Sgreen cp = sp->fts_path + len; 77954770Sgreen } 78054770Sgreen maxlen = sp->fts_pathlen - len; 7811573Srgrimes } 7821573Srgrimes 78354770Sgreen p->fts_level = level; 7841573Srgrimes p->fts_parent = sp->fts_cur; 785128946Skientzle p->fts_pathlen = len + dnamlen; 7861573Srgrimes 78723668Speter#ifdef FTS_WHITEOUT 78823668Speter if (dp->d_type == DT_WHT) 78923668Speter p->fts_flags |= FTS_ISW; 79023668Speter#endif 79123668Speter 7921573Srgrimes if (cderrno) { 7931573Srgrimes if (nlinks) { 7941573Srgrimes p->fts_info = FTS_NS; 7951573Srgrimes p->fts_errno = cderrno; 7961573Srgrimes } else 7971573Srgrimes p->fts_info = FTS_NSOK; 7981573Srgrimes p->fts_accpath = cur->fts_accpath; 7991573Srgrimes } else if (nlinks == 0 8001573Srgrimes#ifdef DT_DIR 80154770Sgreen || (nostat && 80217141Sjkh dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN) 8031573Srgrimes#endif 8041573Srgrimes ) { 8051573Srgrimes p->fts_accpath = 8061573Srgrimes ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; 8071573Srgrimes p->fts_info = FTS_NSOK; 8081573Srgrimes } else { 8091573Srgrimes /* Build a file name for fts_stat to stat. */ 8101573Srgrimes if (ISSET(FTS_NOCHDIR)) { 8111573Srgrimes p->fts_accpath = p->fts_path; 8121573Srgrimes memmove(cp, p->fts_name, p->fts_namelen + 1); 8131573Srgrimes } else 8141573Srgrimes p->fts_accpath = p->fts_name; 8151573Srgrimes /* Stat it. */ 8161573Srgrimes p->fts_info = fts_stat(sp, p, 0); 8171573Srgrimes 8181573Srgrimes /* Decrement link count if applicable. */ 8191573Srgrimes if (nlinks > 0 && (p->fts_info == FTS_D || 8201573Srgrimes p->fts_info == FTS_DC || p->fts_info == FTS_DOT)) 8211573Srgrimes --nlinks; 8221573Srgrimes } 8231573Srgrimes 8241573Srgrimes /* We walk in directory order so "ls -f" doesn't get upset. */ 8251573Srgrimes p->fts_link = NULL; 8261573Srgrimes if (head == NULL) 8271573Srgrimes head = tail = p; 8281573Srgrimes else { 8291573Srgrimes tail->fts_link = p; 8301573Srgrimes tail = p; 8311573Srgrimes } 8321573Srgrimes ++nitems; 8331573Srgrimes } 83428913Simp if (dirp) 83528913Simp (void)closedir(dirp); 8361573Srgrimes 8371573Srgrimes /* 83854770Sgreen * If realloc() changed the address of the path, adjust the 83954770Sgreen * addresses for the rest of the tree and the dir list. 8401573Srgrimes */ 84154770Sgreen if (doadjust) 84254770Sgreen fts_padjust(sp, head); 8431573Srgrimes 8441573Srgrimes /* 8451573Srgrimes * If not changing directories, reset the path back to original 8461573Srgrimes * state. 8471573Srgrimes */ 848199844Sjh if (ISSET(FTS_NOCHDIR)) 849199844Sjh sp->fts_path[cur->fts_pathlen] = '\0'; 8501573Srgrimes 8511573Srgrimes /* 8521573Srgrimes * If descended after called from fts_children or after called from 8531573Srgrimes * fts_read and nothing found, get back. At the root level we use 8541573Srgrimes * the saved fd; if one of fts_open()'s arguments is a relative path 8551573Srgrimes * to an empty directory, we wind up here with no other way back. If 8561573Srgrimes * can't get back, we're done. 8571573Srgrimes */ 8581573Srgrimes if (descend && (type == BCHILD || !nitems) && 8591573Srgrimes (cur->fts_level == FTS_ROOTLEVEL ? 86077599Skris FCHDIR(sp, sp->fts_rfd) : 86177599Skris fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) { 8621573Srgrimes cur->fts_info = FTS_ERR; 8631573Srgrimes SET(FTS_STOP); 8641573Srgrimes return (NULL); 8651573Srgrimes } 8661573Srgrimes 8671573Srgrimes /* If didn't find anything, return NULL. */ 8681573Srgrimes if (!nitems) { 8691573Srgrimes if (type == BREAD) 8701573Srgrimes cur->fts_info = FTS_DP; 8711573Srgrimes return (NULL); 8721573Srgrimes } 8731573Srgrimes 8741573Srgrimes /* Sort the entries. */ 8751573Srgrimes if (sp->fts_compar && nitems > 1) 8761573Srgrimes head = fts_sort(sp, head, nitems); 8771573Srgrimes return (head); 8781573Srgrimes} 8791573Srgrimes 880175688Syarstatic int 8811573Srgrimesfts_stat(sp, p, follow) 8821573Srgrimes FTS *sp; 88390045Sobrien FTSENT *p; 8841573Srgrimes int follow; 8851573Srgrimes{ 88690045Sobrien FTSENT *t; 88790045Sobrien dev_t dev; 88890045Sobrien ino_t ino; 8891573Srgrimes struct stat *sbp, sb; 8901573Srgrimes int saved_errno; 8911573Srgrimes 8921573Srgrimes /* If user needs stat info, stat buffer already allocated. */ 8931573Srgrimes sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp; 8948870Srgrimes 89523668Speter#ifdef FTS_WHITEOUT 896129184Sbde /* Check for whiteout. */ 89723668Speter if (p->fts_flags & FTS_ISW) { 89823668Speter if (sbp != &sb) { 899129184Sbde memset(sbp, '\0', sizeof(*sbp)); 90023668Speter sbp->st_mode = S_IFWHT; 90123668Speter } 90223668Speter return (FTS_W); 90323668Speter } 90423668Speter#endif 90523668Speter 9061573Srgrimes /* 9071573Srgrimes * If doing a logical walk, or application requested FTS_FOLLOW, do 9081573Srgrimes * a stat(2). If that fails, check for a non-existent symlink. If 9091573Srgrimes * fail, set the errno from the stat call. 9101573Srgrimes */ 9111573Srgrimes if (ISSET(FTS_LOGICAL) || follow) { 9121573Srgrimes if (stat(p->fts_accpath, sbp)) { 9131573Srgrimes saved_errno = errno; 9141573Srgrimes if (!lstat(p->fts_accpath, sbp)) { 9151573Srgrimes errno = 0; 9161573Srgrimes return (FTS_SLNONE); 9178870Srgrimes } 9181573Srgrimes p->fts_errno = saved_errno; 9191573Srgrimes goto err; 9201573Srgrimes } 9211573Srgrimes } else if (lstat(p->fts_accpath, sbp)) { 9221573Srgrimes p->fts_errno = errno; 9231573Srgrimeserr: memset(sbp, 0, sizeof(struct stat)); 9241573Srgrimes return (FTS_NS); 9251573Srgrimes } 9261573Srgrimes 9271573Srgrimes if (S_ISDIR(sbp->st_mode)) { 9281573Srgrimes /* 9291573Srgrimes * Set the device/inode. Used to find cycles and check for 9301573Srgrimes * crossing mount points. Also remember the link count, used 9311573Srgrimes * in fts_build to limit the number of stat calls. It is 9321573Srgrimes * understood that these fields are only referenced if fts_info 9331573Srgrimes * is set to FTS_D. 9341573Srgrimes */ 9351573Srgrimes dev = p->fts_dev = sbp->st_dev; 9361573Srgrimes ino = p->fts_ino = sbp->st_ino; 9371573Srgrimes p->fts_nlink = sbp->st_nlink; 9381573Srgrimes 9391573Srgrimes if (ISDOT(p->fts_name)) 9401573Srgrimes return (FTS_DOT); 9411573Srgrimes 9421573Srgrimes /* 9431573Srgrimes * Cycle detection is done by brute force when the directory 9441573Srgrimes * is first encountered. If the tree gets deep enough or the 9451573Srgrimes * number of symbolic links to directories is high enough, 9461573Srgrimes * something faster might be worthwhile. 9471573Srgrimes */ 9481573Srgrimes for (t = p->fts_parent; 9491573Srgrimes t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) 9501573Srgrimes if (ino == t->fts_ino && dev == t->fts_dev) { 9511573Srgrimes p->fts_cycle = t; 9521573Srgrimes return (FTS_DC); 9531573Srgrimes } 9541573Srgrimes return (FTS_D); 9551573Srgrimes } 9561573Srgrimes if (S_ISLNK(sbp->st_mode)) 9571573Srgrimes return (FTS_SL); 9581573Srgrimes if (S_ISREG(sbp->st_mode)) 9591573Srgrimes return (FTS_F); 9601573Srgrimes return (FTS_DEFAULT); 9611573Srgrimes} 9621573Srgrimes 963103726Swollman/* 964103726Swollman * The comparison function takes pointers to pointers to FTSENT structures. 965103726Swollman * Qsort wants a comparison function that takes pointers to void. 966103726Swollman * (Both with appropriate levels of const-poisoning, of course!) 967103726Swollman * Use a trampoline function to deal with the difference. 968103726Swollman */ 969103726Swollmanstatic int 970103726Swollmanfts_compar(const void *a, const void *b) 971103726Swollman{ 972103726Swollman FTS *parent; 973103726Swollman 974103726Swollman parent = (*(const FTSENT * const *)a)->fts_fts; 975103726Swollman return (*parent->fts_compar)(a, b); 976103726Swollman} 977103726Swollman 9781573Srgrimesstatic FTSENT * 9791573Srgrimesfts_sort(sp, head, nitems) 9801573Srgrimes FTS *sp; 9811573Srgrimes FTSENT *head; 982175688Syar size_t nitems; 9831573Srgrimes{ 98490045Sobrien FTSENT **ap, *p; 9851573Srgrimes 9861573Srgrimes /* 9871573Srgrimes * Construct an array of pointers to the structures and call qsort(3). 9881573Srgrimes * Reassemble the array in the order returned by qsort. If unable to 9891573Srgrimes * sort for memory reasons, return the directory entries in their 9901573Srgrimes * current order. Allocate enough space for the current needs plus 9911573Srgrimes * 40 so don't realloc one entry at a time. 9921573Srgrimes */ 9931573Srgrimes if (nitems > sp->fts_nitems) { 9941573Srgrimes sp->fts_nitems = nitems + 40; 99564740Sgreen if ((sp->fts_array = reallocf(sp->fts_array, 99654770Sgreen sp->fts_nitems * sizeof(FTSENT *))) == NULL) { 9971573Srgrimes sp->fts_nitems = 0; 9981573Srgrimes return (head); 9991573Srgrimes } 10001573Srgrimes } 10011573Srgrimes for (ap = sp->fts_array, p = head; p; p = p->fts_link) 10021573Srgrimes *ap++ = p; 1003103726Swollman qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar); 10041573Srgrimes for (head = *(ap = sp->fts_array); --nitems; ++ap) 10051573Srgrimes ap[0]->fts_link = ap[1]; 10061573Srgrimes ap[0]->fts_link = NULL; 10071573Srgrimes return (head); 10081573Srgrimes} 10091573Srgrimes 10101573Srgrimesstatic FTSENT * 10111573Srgrimesfts_alloc(sp, name, namelen) 10121573Srgrimes FTS *sp; 10131573Srgrimes char *name; 1014175688Syar size_t namelen; 10151573Srgrimes{ 101690045Sobrien FTSENT *p; 10171573Srgrimes size_t len; 10181573Srgrimes 1019103726Swollman struct ftsent_withstat { 1020103726Swollman FTSENT ent; 1021103726Swollman struct stat statbuf; 1022103726Swollman }; 1023103726Swollman 10241573Srgrimes /* 10251573Srgrimes * The file name is a variable length array and no stat structure is 10261573Srgrimes * necessary if the user has set the nostat bit. Allocate the FTSENT 10271573Srgrimes * structure, the file name and the stat structure in one chunk, but 1028103726Swollman * be careful that the stat structure is reasonably aligned. 10291573Srgrimes */ 1030103726Swollman if (ISSET(FTS_NOSTAT)) 1031103726Swollman len = sizeof(FTSENT) + namelen + 1; 1032103726Swollman else 1033103726Swollman len = sizeof(struct ftsent_withstat) + namelen + 1; 1034103726Swollman 10351573Srgrimes if ((p = malloc(len)) == NULL) 10361573Srgrimes return (NULL); 10371573Srgrimes 1038103726Swollman if (ISSET(FTS_NOSTAT)) { 1039103726Swollman p->fts_name = (char *)(p + 1); 1040103726Swollman p->fts_statp = NULL; 1041103726Swollman } else { 1042103726Swollman p->fts_name = (char *)((struct ftsent_withstat *)p + 1); 1043103726Swollman p->fts_statp = &((struct ftsent_withstat *)p)->statbuf; 1044103726Swollman } 1045103726Swollman 104654770Sgreen /* Copy the name and guarantee NUL termination. */ 1047103726Swollman memcpy(p->fts_name, name, namelen); 104854770Sgreen p->fts_name[namelen] = '\0'; 10491573Srgrimes p->fts_namelen = namelen; 10501573Srgrimes p->fts_path = sp->fts_path; 10511573Srgrimes p->fts_errno = 0; 10521573Srgrimes p->fts_flags = 0; 10531573Srgrimes p->fts_instr = FTS_NOINSTR; 10541573Srgrimes p->fts_number = 0; 10551573Srgrimes p->fts_pointer = NULL; 1056103726Swollman p->fts_fts = sp; 10571573Srgrimes return (p); 10581573Srgrimes} 10591573Srgrimes 10601573Srgrimesstatic void 10611573Srgrimesfts_lfree(head) 106290045Sobrien FTSENT *head; 10631573Srgrimes{ 106490045Sobrien FTSENT *p; 10651573Srgrimes 10661573Srgrimes /* Free a linked list of structures. */ 106728913Simp while ((p = head)) { 10681573Srgrimes head = head->fts_link; 10691573Srgrimes free(p); 10701573Srgrimes } 10711573Srgrimes} 10721573Srgrimes 10731573Srgrimes/* 10741573Srgrimes * Allow essentially unlimited paths; find, rm, ls should all work on any tree. 10751573Srgrimes * Most systems will allow creation of paths much longer than MAXPATHLEN, even 10761573Srgrimes * though the kernel won't resolve them. Add the size (not just what's needed) 10778870Srgrimes * plus 256 bytes so don't realloc the path 2 bytes at a time. 10781573Srgrimes */ 10791573Srgrimesstatic int 10801573Srgrimesfts_palloc(sp, more) 10811573Srgrimes FTS *sp; 10821573Srgrimes size_t more; 10831573Srgrimes{ 108454770Sgreen 10851573Srgrimes sp->fts_pathlen += more + 256; 108664740Sgreen sp->fts_path = reallocf(sp->fts_path, sp->fts_pathlen); 108764740Sgreen return (sp->fts_path == NULL); 108850790Simp} 108950790Simp 10901573Srgrimes/* 10911573Srgrimes * When the path is realloc'd, have to fix all of the pointers in structures 10921573Srgrimes * already returned. 10931573Srgrimes */ 10941573Srgrimesstatic void 109554770Sgreenfts_padjust(sp, head) 10961573Srgrimes FTS *sp; 109754770Sgreen FTSENT *head; 10981573Srgrimes{ 10991573Srgrimes FTSENT *p; 110054770Sgreen char *addr = sp->fts_path; 11011573Srgrimes 110264740Sgreen#define ADJUST(p) do { \ 110354770Sgreen if ((p)->fts_accpath != (p)->fts_name) { \ 110454770Sgreen (p)->fts_accpath = \ 110554770Sgreen (char *)addr + ((p)->fts_accpath - (p)->fts_path); \ 110654770Sgreen } \ 11071573Srgrimes (p)->fts_path = addr; \ 110864740Sgreen} while (0) 11091573Srgrimes /* Adjust the current set of children. */ 11101573Srgrimes for (p = sp->fts_child; p; p = p->fts_link) 111154770Sgreen ADJUST(p); 11121573Srgrimes 111354770Sgreen /* Adjust the rest of the tree, including the current level. */ 111454770Sgreen for (p = head; p->fts_level >= FTS_ROOTLEVEL;) { 111554770Sgreen ADJUST(p); 11161573Srgrimes p = p->fts_link ? p->fts_link : p->fts_parent; 11171573Srgrimes } 11181573Srgrimes} 11191573Srgrimes 11201573Srgrimesstatic size_t 11211573Srgrimesfts_maxarglen(argv) 11221573Srgrimes char * const *argv; 11231573Srgrimes{ 11241573Srgrimes size_t len, max; 11251573Srgrimes 11261573Srgrimes for (max = 0; *argv; ++argv) 11271573Srgrimes if ((len = strlen(*argv)) > max) 11281573Srgrimes max = len; 112954770Sgreen return (max + 1); 11301573Srgrimes} 113128913Simp 113228913Simp/* 113328913Simp * Change to dir specified by fd or p->fts_accpath without getting 113428913Simp * tricked by someone changing the world out from underneath us. 113528913Simp * Assumes p->fts_dev and p->fts_ino are filled in. 113628913Simp */ 113728913Simpstatic int 113877599Skrisfts_safe_changedir(sp, p, fd, path) 113928913Simp FTS *sp; 114028913Simp FTSENT *p; 114128913Simp int fd; 114277599Skris char *path; 114328913Simp{ 114428913Simp int ret, oerrno, newfd; 114528913Simp struct stat sb; 114628913Simp 114728913Simp newfd = fd; 114828913Simp if (ISSET(FTS_NOCHDIR)) 114928913Simp return (0); 1150248650Sjilles if (fd < 0 && (newfd = _open(path, O_RDONLY | O_DIRECTORY | 1151248650Sjilles O_CLOEXEC, 0)) < 0) 115228913Simp return (-1); 115371579Sdeischen if (_fstat(newfd, &sb)) { 115428913Simp ret = -1; 115528913Simp goto bail; 115628913Simp } 115728913Simp if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) { 115828913Simp errno = ENOENT; /* disinformation */ 115928913Simp ret = -1; 116028913Simp goto bail; 116128913Simp } 116228913Simp ret = fchdir(newfd); 116328913Simpbail: 116428913Simp oerrno = errno; 116528913Simp if (fd < 0) 116656698Sjasone (void)_close(newfd); 116728913Simp errno = oerrno; 116828913Simp return (ret); 116928913Simp} 1170129052Speadar 1171129052Speadar/* 1172129052Speadar * Check if the filesystem for "ent" has UFS-style links. 1173129052Speadar */ 1174129052Speadarstatic int 1175129052Speadarfts_ufslinks(FTS *sp, const FTSENT *ent) 1176129052Speadar{ 1177129052Speadar struct _fts_private *priv; 1178129052Speadar const char **cpp; 1179129052Speadar 1180129161Speadar priv = (struct _fts_private *)sp; 1181129052Speadar /* 1182129052Speadar * If this node's device is different from the previous, grab 1183129052Speadar * the filesystem information, and decide on the reliability 1184129052Speadar * of the link information from this filesystem for stat(2) 1185129052Speadar * avoidance. 1186129052Speadar */ 1187129052Speadar if (priv->ftsp_dev != ent->fts_dev) { 1188129052Speadar if (statfs(ent->fts_path, &priv->ftsp_statfs) != -1) { 1189129052Speadar priv->ftsp_dev = ent->fts_dev; 1190129052Speadar priv->ftsp_linksreliable = 0; 1191129052Speadar for (cpp = ufslike_filesystems; *cpp; cpp++) { 1192129052Speadar if (strcmp(priv->ftsp_statfs.f_fstypename, 1193129052Speadar *cpp) == 0) { 1194129052Speadar priv->ftsp_linksreliable = 1; 1195129052Speadar break; 1196129052Speadar } 1197129052Speadar } 1198129052Speadar } else { 1199129052Speadar priv->ftsp_linksreliable = 0; 1200129052Speadar } 1201129052Speadar } 1202129161Speadar return (priv->ftsp_linksreliable); 1203129052Speadar} 1204