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: releng/11.0/lib/libc/gen/fts-compat.c 300660 2016-05-25 06:55:53Z truckman $"); 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 55235647Sgleb#include "gen-private.h" 56235647Sgleb 57175688SyarFTSENT *__fts_children_44bsd(FTS *, int); 58175688Syarint __fts_close_44bsd(FTS *); 59175688Syarvoid *__fts_get_clientptr_44bsd(FTS *); 60175688SyarFTS *__fts_get_stream_44bsd(FTSENT *); 61175688SyarFTS *__fts_open_44bsd(char * const *, int, 62175688Syar int (*)(const FTSENT * const *, const FTSENT * const *)); 63175688SyarFTSENT *__fts_read_44bsd(FTS *); 64175688Syarint __fts_set_44bsd(FTS *, FTSENT *, int); 65175688Syarvoid __fts_set_clientptr_44bsd(FTS *, void *); 66175688Syar 6790045Sobrienstatic FTSENT *fts_alloc(FTS *, char *, int); 6890045Sobrienstatic FTSENT *fts_build(FTS *, int); 6990045Sobrienstatic void fts_lfree(FTSENT *); 7090045Sobrienstatic void fts_load(FTS *, FTSENT *); 7190045Sobrienstatic size_t fts_maxarglen(char * const *); 7290045Sobrienstatic void fts_padjust(FTS *, FTSENT *); 7390045Sobrienstatic int fts_palloc(FTS *, size_t); 7490045Sobrienstatic FTSENT *fts_sort(FTS *, FTSENT *, int); 7590045Sobrienstatic u_short fts_stat(FTS *, FTSENT *, int); 7690045Sobrienstatic int fts_safe_changedir(FTS *, FTSENT *, int, char *); 77129161Speadarstatic int fts_ufslinks(FTS *, const FTSENT *); 781573Srgrimes 7928913Simp#define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2]))) 801573Srgrimes 8128913Simp#define CLR(opt) (sp->fts_options &= ~(opt)) 8228913Simp#define ISSET(opt) (sp->fts_options & (opt)) 8328913Simp#define SET(opt) (sp->fts_options |= (opt)) 841573Srgrimes 851573Srgrimes#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd)) 861573Srgrimes 871573Srgrimes/* fts_build flags */ 881573Srgrimes#define BCHILD 1 /* fts_children */ 891573Srgrimes#define BNAMES 2 /* fts_children, names only */ 901573Srgrimes#define BREAD 3 /* fts_read */ 911573Srgrimes 92129052Speadar/* 93129161Speadar * Internal representation of an FTS, including extra implementation 94129161Speadar * details. The FTS returned from fts_open points to this structure's 95129161Speadar * ftsp_fts member (and can be cast to an _fts_private as required) 96129052Speadar */ 97129052Speadarstruct _fts_private { 98129161Speadar FTS ftsp_fts; 99129161Speadar struct statfs ftsp_statfs; 100129161Speadar dev_t ftsp_dev; 101129161Speadar int ftsp_linksreliable; 102129052Speadar}; 103129052Speadar 104129052Speadar/* 105129161Speadar * The "FTS_NOSTAT" option can avoid a lot of calls to stat(2) if it 106129161Speadar * knows that a directory could not possibly have subdirectories. This 107129161Speadar * is decided by looking at the link count: a subdirectory would 108129161Speadar * increment its parent's link count by virtue of its own ".." entry. 109129161Speadar * This assumption only holds for UFS-like filesystems that implement 110129161Speadar * links and directories this way, so we must punt for others. 111129052Speadar */ 112129052Speadar 113129052Speadarstatic const char *ufslike_filesystems[] = { 114129052Speadar "ufs", 115219696Spjd "zfs", 116129052Speadar "nfs", 117129052Speadar "ext2fs", 118129052Speadar 0 119129052Speadar}; 120129052Speadar 1211573SrgrimesFTS * 122288029Srodrigc__fts_open_44bsd(char * const *argv, int options, 123288029Srodrigc int (*compar)(const FTSENT * const *, const FTSENT * const *)) 1241573Srgrimes{ 125129052Speadar struct _fts_private *priv; 12690045Sobrien FTS *sp; 12790045Sobrien FTSENT *p, *root; 12890045Sobrien int nitems; 1291573Srgrimes FTSENT *parent, *tmp; 1301573Srgrimes int len; 1311573Srgrimes 1321573Srgrimes /* Options check. */ 1331573Srgrimes if (options & ~FTS_OPTIONMASK) { 1341573Srgrimes errno = EINVAL; 1351573Srgrimes return (NULL); 1361573Srgrimes } 1371573Srgrimes 138129184Sbde /* Allocate/initialize the stream. */ 139288351Sdelphij if ((priv = calloc(1, sizeof(*priv))) == NULL) 1401573Srgrimes return (NULL); 141129052Speadar sp = &priv->ftsp_fts; 1421573Srgrimes sp->fts_compar = compar; 1431573Srgrimes sp->fts_options = options; 1441573Srgrimes 14554770Sgreen /* Shush, GCC. */ 14654770Sgreen tmp = NULL; 14754770Sgreen 1481573Srgrimes /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ 1491573Srgrimes if (ISSET(FTS_LOGICAL)) 1501573Srgrimes SET(FTS_NOCHDIR); 1511573Srgrimes 1521573Srgrimes /* 1531573Srgrimes * Start out with 1K of path space, and enough, in any case, 1541573Srgrimes * to hold the user's paths. 1551573Srgrimes */ 1561573Srgrimes if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN))) 1571573Srgrimes goto mem1; 1581573Srgrimes 1591573Srgrimes /* Allocate/initialize root's parent. */ 1601573Srgrimes if ((parent = fts_alloc(sp, "", 0)) == NULL) 1611573Srgrimes goto mem2; 1621573Srgrimes parent->fts_level = FTS_ROOTPARENTLEVEL; 1631573Srgrimes 1641573Srgrimes /* Allocate/initialize root(s). */ 16564740Sgreen for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) { 1661573Srgrimes /* Don't allow zero-length paths. */ 1671573Srgrimes if ((len = strlen(*argv)) == 0) { 1681573Srgrimes errno = ENOENT; 1691573Srgrimes goto mem3; 1701573Srgrimes } 1711573Srgrimes 1721573Srgrimes p = fts_alloc(sp, *argv, len); 1731573Srgrimes p->fts_level = FTS_ROOTLEVEL; 1741573Srgrimes p->fts_parent = parent; 1751573Srgrimes p->fts_accpath = p->fts_name; 1761573Srgrimes p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW)); 1771573Srgrimes 1781573Srgrimes /* Command-line "." and ".." are real directories. */ 1791573Srgrimes if (p->fts_info == FTS_DOT) 1801573Srgrimes p->fts_info = FTS_D; 1811573Srgrimes 1821573Srgrimes /* 1831573Srgrimes * If comparison routine supplied, traverse in sorted 1841573Srgrimes * order; otherwise traverse in the order specified. 1851573Srgrimes */ 1861573Srgrimes if (compar) { 1871573Srgrimes p->fts_link = root; 1881573Srgrimes root = p; 1891573Srgrimes } else { 1901573Srgrimes p->fts_link = NULL; 1911573Srgrimes if (root == NULL) 1921573Srgrimes tmp = root = p; 1931573Srgrimes else { 1941573Srgrimes tmp->fts_link = p; 1951573Srgrimes tmp = p; 1961573Srgrimes } 1971573Srgrimes } 1981573Srgrimes } 1991573Srgrimes if (compar && nitems > 1) 2001573Srgrimes root = fts_sort(sp, root, nitems); 2011573Srgrimes 2021573Srgrimes /* 2031573Srgrimes * Allocate a dummy pointer and make fts_read think that we've just 2041573Srgrimes * finished the node before the root(s); set p->fts_info to FTS_INIT 2051573Srgrimes * so that everything about the "current" node is ignored. 2061573Srgrimes */ 2071573Srgrimes if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL) 2081573Srgrimes goto mem3; 2091573Srgrimes sp->fts_cur->fts_link = root; 2101573Srgrimes sp->fts_cur->fts_info = FTS_INIT; 2111573Srgrimes 2121573Srgrimes /* 21354770Sgreen * If using chdir(2), grab a file descriptor pointing to dot to ensure 2141573Srgrimes * that we can get back here; this could be avoided for some paths, 2151573Srgrimes * but almost certainly not worth the effort. Slashes, symbolic links, 2161573Srgrimes * and ".." are all fairly nasty problems. Note, if we can't get the 2171573Srgrimes * descriptor we run anyway, just more slowly. 2181573Srgrimes */ 219241010Sjilles if (!ISSET(FTS_NOCHDIR) && 220241010Sjilles (sp->fts_rfd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) 2211573Srgrimes SET(FTS_NOCHDIR); 2221573Srgrimes 2231573Srgrimes return (sp); 2241573Srgrimes 2251573Srgrimesmem3: fts_lfree(root); 2261573Srgrimes free(parent); 2271573Srgrimesmem2: free(sp->fts_path); 2281573Srgrimesmem1: free(sp); 2291573Srgrimes return (NULL); 2301573Srgrimes} 2311573Srgrimes 2321573Srgrimesstatic void 233288029Srodrigcfts_load(FTS *sp, FTSENT *p) 2341573Srgrimes{ 23590045Sobrien int len; 23690045Sobrien char *cp; 2371573Srgrimes 2381573Srgrimes /* 2391573Srgrimes * Load the stream structure for the next traversal. Since we don't 2401573Srgrimes * actually enter the directory until after the preorder visit, set 2411573Srgrimes * the fts_accpath field specially so the chdir gets done to the right 2421573Srgrimes * place and the user can access the first node. From fts_open it's 2431573Srgrimes * known that the path will fit. 2441573Srgrimes */ 2451573Srgrimes len = p->fts_pathlen = p->fts_namelen; 2461573Srgrimes memmove(sp->fts_path, p->fts_name, len + 1); 2471573Srgrimes if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { 2481573Srgrimes len = strlen(++cp); 2491573Srgrimes memmove(p->fts_name, cp, len + 1); 2501573Srgrimes p->fts_namelen = len; 2511573Srgrimes } 2521573Srgrimes p->fts_accpath = p->fts_path = sp->fts_path; 2531573Srgrimes sp->fts_dev = p->fts_dev; 2541573Srgrimes} 2551573Srgrimes 2561573Srgrimesint 257288029Srodrigc__fts_close_44bsd(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 * 311288029Srodrigc__fts_read_44bsd(FTS *sp) 3121573Srgrimes{ 31390045Sobrien FTSENT *p, *tmp; 31490045Sobrien int instr; 31590045Sobrien char *t; 3161573Srgrimes int saved_errno; 3171573Srgrimes 3181573Srgrimes /* If finished or unrecoverable error, return NULL. */ 3191573Srgrimes if (sp->fts_cur == NULL || ISSET(FTS_STOP)) 3201573Srgrimes return (NULL); 3211573Srgrimes 3221573Srgrimes /* Set current node pointer. */ 3231573Srgrimes p = sp->fts_cur; 3241573Srgrimes 3251573Srgrimes /* Save and zero out user instructions. */ 3261573Srgrimes instr = p->fts_instr; 3271573Srgrimes p->fts_instr = FTS_NOINSTR; 3281573Srgrimes 3291573Srgrimes /* Any type of file may be re-visited; re-stat and re-turn. */ 3301573Srgrimes if (instr == FTS_AGAIN) { 3311573Srgrimes p->fts_info = fts_stat(sp, p, 0); 3321573Srgrimes return (p); 3331573Srgrimes } 3341573Srgrimes 3351573Srgrimes /* 3361573Srgrimes * Following a symlink -- SLNONE test allows application to see 3371573Srgrimes * SLNONE and recover. If indirecting through a symlink, have 3381573Srgrimes * keep a pointer to current location. If unable to get that 3391573Srgrimes * pointer, follow fails. 3401573Srgrimes */ 3411573Srgrimes if (instr == FTS_FOLLOW && 3421573Srgrimes (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { 3431573Srgrimes p->fts_info = fts_stat(sp, p, 1); 34454770Sgreen if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { 345241010Sjilles if ((p->fts_symfd = _open(".", O_RDONLY | O_CLOEXEC, 346241010Sjilles 0)) < 0) { 3471573Srgrimes p->fts_errno = errno; 3481573Srgrimes p->fts_info = FTS_ERR; 3491573Srgrimes } else 3501573Srgrimes p->fts_flags |= FTS_SYMFOLLOW; 35154770Sgreen } 3521573Srgrimes return (p); 3531573Srgrimes } 3541573Srgrimes 3551573Srgrimes /* Directory in pre-order. */ 3561573Srgrimes if (p->fts_info == FTS_D) { 3571573Srgrimes /* If skipped or crossed mount point, do post-order visit. */ 3581573Srgrimes if (instr == FTS_SKIP || 35928913Simp (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) { 3601573Srgrimes if (p->fts_flags & FTS_SYMFOLLOW) 36156698Sjasone (void)_close(p->fts_symfd); 3621573Srgrimes if (sp->fts_child) { 3631573Srgrimes fts_lfree(sp->fts_child); 3641573Srgrimes sp->fts_child = NULL; 3651573Srgrimes } 3661573Srgrimes p->fts_info = FTS_DP; 3671573Srgrimes return (p); 3688870Srgrimes } 3691573Srgrimes 3701573Srgrimes /* Rebuild if only read the names and now traversing. */ 37164740Sgreen if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) { 37228913Simp CLR(FTS_NAMEONLY); 3731573Srgrimes fts_lfree(sp->fts_child); 3741573Srgrimes sp->fts_child = NULL; 3751573Srgrimes } 3761573Srgrimes 3771573Srgrimes /* 3781573Srgrimes * Cd to the subdirectory. 3791573Srgrimes * 3801573Srgrimes * If have already read and now fail to chdir, whack the list 3811573Srgrimes * to make the names come out right, and set the parent errno 3821573Srgrimes * so the application will eventually get an error condition. 3831573Srgrimes * Set the FTS_DONTCHDIR flag so that when we logically change 3841573Srgrimes * directories back to the parent we don't do a chdir. 3851573Srgrimes * 3861573Srgrimes * If haven't read do so. If the read fails, fts_build sets 3871573Srgrimes * FTS_STOP or the fts_info field of the node. 3881573Srgrimes */ 38964740Sgreen if (sp->fts_child != NULL) { 39077599Skris if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) { 3911573Srgrimes p->fts_errno = errno; 3921573Srgrimes p->fts_flags |= FTS_DONTCHDIR; 393129184Sbde for (p = sp->fts_child; p != NULL; 39464740Sgreen p = p->fts_link) 3951573Srgrimes p->fts_accpath = 3961573Srgrimes p->fts_parent->fts_accpath; 3971573Srgrimes } 3981573Srgrimes } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) { 3991573Srgrimes if (ISSET(FTS_STOP)) 4001573Srgrimes return (NULL); 4011573Srgrimes return (p); 4021573Srgrimes } 4031573Srgrimes p = sp->fts_child; 4041573Srgrimes sp->fts_child = NULL; 4051573Srgrimes goto name; 4061573Srgrimes } 4071573Srgrimes 4081573Srgrimes /* Move to the next node on this level. */ 4091573Srgrimesnext: tmp = p; 41064740Sgreen if ((p = p->fts_link) != NULL) { 4111573Srgrimes free(tmp); 4121573Srgrimes 4131573Srgrimes /* 41454770Sgreen * If reached the top, return to the original directory (or 41554770Sgreen * the root of the tree), and load the paths for the next root. 4161573Srgrimes */ 4171573Srgrimes if (p->fts_level == FTS_ROOTLEVEL) { 41828913Simp if (FCHDIR(sp, sp->fts_rfd)) { 4191573Srgrimes SET(FTS_STOP); 4201573Srgrimes return (NULL); 4211573Srgrimes } 4221573Srgrimes fts_load(sp, p); 4231573Srgrimes return (sp->fts_cur = p); 4241573Srgrimes } 4251573Srgrimes 4261573Srgrimes /* 4271573Srgrimes * User may have called fts_set on the node. If skipped, 4281573Srgrimes * ignore. If followed, get a file descriptor so we can 4291573Srgrimes * get back if necessary. 4301573Srgrimes */ 4311573Srgrimes if (p->fts_instr == FTS_SKIP) 4321573Srgrimes goto next; 4331573Srgrimes if (p->fts_instr == FTS_FOLLOW) { 4341573Srgrimes p->fts_info = fts_stat(sp, p, 1); 43554770Sgreen if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { 4361573Srgrimes if ((p->fts_symfd = 437241010Sjilles _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) { 4381573Srgrimes p->fts_errno = errno; 4391573Srgrimes p->fts_info = FTS_ERR; 4401573Srgrimes } else 4411573Srgrimes p->fts_flags |= FTS_SYMFOLLOW; 44254770Sgreen } 4431573Srgrimes p->fts_instr = FTS_NOINSTR; 4441573Srgrimes } 4451573Srgrimes 4461573Srgrimesname: t = sp->fts_path + NAPPEND(p->fts_parent); 4471573Srgrimes *t++ = '/'; 4481573Srgrimes memmove(t, p->fts_name, p->fts_namelen + 1); 4491573Srgrimes return (sp->fts_cur = p); 4501573Srgrimes } 4511573Srgrimes 4521573Srgrimes /* Move up to the parent node. */ 4531573Srgrimes p = tmp->fts_parent; 4541573Srgrimes free(tmp); 4551573Srgrimes 4561573Srgrimes if (p->fts_level == FTS_ROOTPARENTLEVEL) { 4571573Srgrimes /* 4581573Srgrimes * Done; free everything up and set errno to 0 so the user 4591573Srgrimes * can distinguish between error and EOF. 4601573Srgrimes */ 4611573Srgrimes free(p); 4621573Srgrimes errno = 0; 4631573Srgrimes return (sp->fts_cur = NULL); 4641573Srgrimes } 4651573Srgrimes 46654770Sgreen /* NUL terminate the pathname. */ 4671573Srgrimes sp->fts_path[p->fts_pathlen] = '\0'; 4681573Srgrimes 4691573Srgrimes /* 4701573Srgrimes * Return to the parent directory. If at a root node or came through 4711573Srgrimes * a symlink, go back through the file descriptor. Otherwise, cd up 4721573Srgrimes * one directory. 4731573Srgrimes */ 4741573Srgrimes if (p->fts_level == FTS_ROOTLEVEL) { 47528913Simp if (FCHDIR(sp, sp->fts_rfd)) { 4761573Srgrimes SET(FTS_STOP); 4771573Srgrimes return (NULL); 4781573Srgrimes } 4791573Srgrimes } else if (p->fts_flags & FTS_SYMFOLLOW) { 4801573Srgrimes if (FCHDIR(sp, p->fts_symfd)) { 4811573Srgrimes saved_errno = errno; 48256698Sjasone (void)_close(p->fts_symfd); 4831573Srgrimes errno = saved_errno; 4841573Srgrimes SET(FTS_STOP); 4851573Srgrimes return (NULL); 4861573Srgrimes } 48756698Sjasone (void)_close(p->fts_symfd); 48877497Skris } else if (!(p->fts_flags & FTS_DONTCHDIR) && 489129184Sbde fts_safe_changedir(sp, p->fts_parent, -1, "..")) { 49077599Skris SET(FTS_STOP); 49177599Skris return (NULL); 4921573Srgrimes } 4931573Srgrimes p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP; 4941573Srgrimes return (sp->fts_cur = p); 4951573Srgrimes} 4961573Srgrimes 4971573Srgrimes/* 4981573Srgrimes * Fts_set takes the stream as an argument although it's not used in this 4991573Srgrimes * implementation; it would be necessary if anyone wanted to add global 5001573Srgrimes * semantics to fts using fts_set. An error return is allowed for similar 5011573Srgrimes * reasons. 5021573Srgrimes */ 5031573Srgrimes/* ARGSUSED */ 5041573Srgrimesint 505288029Srodrigc__fts_set_44bsd(FTS *sp, FTSENT *p, int instr) 5061573Srgrimes{ 50764740Sgreen if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW && 5081573Srgrimes instr != FTS_NOINSTR && instr != FTS_SKIP) { 5091573Srgrimes errno = EINVAL; 5101573Srgrimes return (1); 5111573Srgrimes } 5121573Srgrimes p->fts_instr = instr; 5131573Srgrimes return (0); 5141573Srgrimes} 5151573Srgrimes 5161573SrgrimesFTSENT * 517288029Srodrigc__fts_children_44bsd(FTS *sp, int instr) 5181573Srgrimes{ 51990045Sobrien FTSENT *p; 5201573Srgrimes int fd; 5211573Srgrimes 52264740Sgreen if (instr != 0 && instr != FTS_NAMEONLY) { 5231573Srgrimes errno = EINVAL; 5241573Srgrimes return (NULL); 5251573Srgrimes } 5261573Srgrimes 5271573Srgrimes /* Set current node pointer. */ 5281573Srgrimes p = sp->fts_cur; 5291573Srgrimes 5301573Srgrimes /* 5311573Srgrimes * Errno set to 0 so user can distinguish empty directory from 5321573Srgrimes * an error. 5331573Srgrimes */ 5341573Srgrimes errno = 0; 5351573Srgrimes 5361573Srgrimes /* Fatal errors stop here. */ 5371573Srgrimes if (ISSET(FTS_STOP)) 5381573Srgrimes return (NULL); 5391573Srgrimes 5401573Srgrimes /* Return logical hierarchy of user's arguments. */ 5411573Srgrimes if (p->fts_info == FTS_INIT) 5421573Srgrimes return (p->fts_link); 5431573Srgrimes 5441573Srgrimes /* 5451573Srgrimes * If not a directory being visited in pre-order, stop here. Could 5461573Srgrimes * allow FTS_DNR, assuming the user has fixed the problem, but the 5471573Srgrimes * same effect is available with FTS_AGAIN. 5481573Srgrimes */ 5491573Srgrimes if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */) 5501573Srgrimes return (NULL); 5511573Srgrimes 5521573Srgrimes /* Free up any previous child list. */ 55364740Sgreen if (sp->fts_child != NULL) 5541573Srgrimes fts_lfree(sp->fts_child); 5551573Srgrimes 5561573Srgrimes if (instr == FTS_NAMEONLY) { 55728913Simp SET(FTS_NAMEONLY); 5581573Srgrimes instr = BNAMES; 5598870Srgrimes } else 5601573Srgrimes instr = BCHILD; 5611573Srgrimes 5621573Srgrimes /* 5631573Srgrimes * If using chdir on a relative path and called BEFORE fts_read does 5641573Srgrimes * its chdir to the root of a traversal, we can lose -- we need to 5651573Srgrimes * chdir into the subdirectory, and we don't know where the current 5661573Srgrimes * directory is, so we can't get back so that the upcoming chdir by 5671573Srgrimes * fts_read will work. 5681573Srgrimes */ 5691573Srgrimes if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || 5701573Srgrimes ISSET(FTS_NOCHDIR)) 5711573Srgrimes return (sp->fts_child = fts_build(sp, instr)); 5721573Srgrimes 573241010Sjilles if ((fd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) 5741573Srgrimes return (NULL); 5751573Srgrimes sp->fts_child = fts_build(sp, instr); 576300660Struckman if (fchdir(fd)) { 577300660Struckman (void)_close(fd); 5781573Srgrimes return (NULL); 579300660Struckman } 58056698Sjasone (void)_close(fd); 5811573Srgrimes return (sp->fts_child); 5821573Srgrimes} 5831573Srgrimes 584103726Swollman#ifndef fts_get_clientptr 585103726Swollman#error "fts_get_clientptr not defined" 586103726Swollman#endif 587103726Swollman 588103726Swollmanvoid * 589175688Syar(__fts_get_clientptr_44bsd)(FTS *sp) 590103726Swollman{ 591103726Swollman 592103726Swollman return (fts_get_clientptr(sp)); 593103726Swollman} 594103726Swollman 595103726Swollman#ifndef fts_get_stream 596103726Swollman#error "fts_get_stream not defined" 597103726Swollman#endif 598103726Swollman 599103726SwollmanFTS * 600175688Syar(__fts_get_stream_44bsd)(FTSENT *p) 601103726Swollman{ 602103726Swollman return (fts_get_stream(p)); 603103726Swollman} 604103726Swollman 605103726Swollmanvoid 606175688Syar__fts_set_clientptr_44bsd(FTS *sp, void *clientptr) 607103726Swollman{ 608103726Swollman 609103726Swollman sp->fts_clientptr = clientptr; 610103726Swollman} 611103726Swollman 6121573Srgrimes/* 6131573Srgrimes * This is the tricky part -- do not casually change *anything* in here. The 6141573Srgrimes * idea is to build the linked list of entries that are used by fts_children 6151573Srgrimes * and fts_read. There are lots of special cases. 6161573Srgrimes * 6171573Srgrimes * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is 6181573Srgrimes * set and it's a physical walk (so that symbolic links can't be directories), 6191573Srgrimes * we can do things quickly. First, if it's a 4.4BSD file system, the type 6201573Srgrimes * of the file is in the directory entry. Otherwise, we assume that the number 6211573Srgrimes * of subdirectories in a node is equal to the number of links to the parent. 6221573Srgrimes * The former skips all stat calls. The latter skips stat calls in any leaf 6231573Srgrimes * directories and for any files after the subdirectories in the directory have 6241573Srgrimes * been found, cutting the stat calls by about 2/3. 6251573Srgrimes */ 6261573Srgrimesstatic FTSENT * 627287793Srodrigcfts_build(FTS *sp, int type) 6281573Srgrimes{ 62990045Sobrien struct dirent *dp; 63090045Sobrien FTSENT *p, *head; 63190045Sobrien int nitems; 6321573Srgrimes FTSENT *cur, *tail; 6331573Srgrimes DIR *dirp; 63454770Sgreen void *oldaddr; 635128946Skientzle size_t dnamlen; 63654770Sgreen int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno, 63754770Sgreen nostat, doadjust; 6381573Srgrimes char *cp; 6391573Srgrimes 6401573Srgrimes /* Set current node pointer. */ 6411573Srgrimes cur = sp->fts_cur; 6421573Srgrimes 6431573Srgrimes /* 6441573Srgrimes * Open the directory for reading. If this fails, we're done. 6451573Srgrimes * If being called from fts_read, set the fts_info field. 6461573Srgrimes */ 64723668Speter#ifdef FTS_WHITEOUT 64823668Speter if (ISSET(FTS_WHITEOUT)) 649129184Sbde oflag = DTF_NODUP | DTF_REWIND; 65023668Speter else 651129184Sbde oflag = DTF_HIDEW | DTF_NODUP | DTF_REWIND; 65223668Speter#else 65323668Speter#define __opendir2(path, flag) opendir(path) 65423668Speter#endif 65523668Speter if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) { 6561573Srgrimes if (type == BREAD) { 6571573Srgrimes cur->fts_info = FTS_DNR; 6581573Srgrimes cur->fts_errno = errno; 6591573Srgrimes } 6601573Srgrimes return (NULL); 6611573Srgrimes } 6621573Srgrimes 6631573Srgrimes /* 6641573Srgrimes * Nlinks is the number of possible entries of type directory in the 6651573Srgrimes * directory if we're cheating on stat calls, 0 if we're not doing 6661573Srgrimes * any stat calls at all, -1 if we're doing stats on everything. 6671573Srgrimes */ 66854770Sgreen if (type == BNAMES) { 6691573Srgrimes nlinks = 0; 67054770Sgreen /* Be quiet about nostat, GCC. */ 67154770Sgreen nostat = 0; 67254770Sgreen } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) { 673129052Speadar if (fts_ufslinks(sp, cur)) 674129052Speadar nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2); 675129052Speadar else 676129052Speadar nlinks = -1; 67754770Sgreen nostat = 1; 67854770Sgreen } else { 6791573Srgrimes nlinks = -1; 68054770Sgreen nostat = 0; 68154770Sgreen } 6821573Srgrimes 6831573Srgrimes#ifdef notdef 6841573Srgrimes (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink); 6851573Srgrimes (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n", 6861573Srgrimes ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT)); 6871573Srgrimes#endif 6881573Srgrimes /* 6891573Srgrimes * If we're going to need to stat anything or we want to descend 6901573Srgrimes * and stay in the directory, chdir. If this fails we keep going, 6911573Srgrimes * but set a flag so we don't chdir after the post-order visit. 6921573Srgrimes * We won't be able to stat anything, but we can still return the 6931573Srgrimes * names themselves. Note, that since fts_read won't be able to 6941573Srgrimes * chdir into the directory, it will have to return different path 6951573Srgrimes * names than before, i.e. "a/b" instead of "b". Since the node 6961573Srgrimes * has already been visited in pre-order, have to wait until the 6971573Srgrimes * post-order visit to return the error. There is a special case 6981573Srgrimes * here, if there was nothing to stat then it's not an error to 6991573Srgrimes * not be able to stat. This is all fairly nasty. If a program 7001573Srgrimes * needed sorted entries or stat information, they had better be 7011573Srgrimes * checking FTS_NS on the returned nodes. 7021573Srgrimes */ 7031573Srgrimes cderrno = 0; 70454770Sgreen if (nlinks || type == BREAD) { 705235647Sgleb if (fts_safe_changedir(sp, cur, _dirfd(dirp), NULL)) { 7061573Srgrimes if (nlinks && type == BREAD) 7071573Srgrimes cur->fts_errno = errno; 7081573Srgrimes cur->fts_flags |= FTS_DONTCHDIR; 7091573Srgrimes descend = 0; 7101573Srgrimes cderrno = errno; 7111573Srgrimes } else 7121573Srgrimes descend = 1; 71354770Sgreen } else 7141573Srgrimes descend = 0; 7151573Srgrimes 7161573Srgrimes /* 7171573Srgrimes * Figure out the max file name length that can be stored in the 7181573Srgrimes * current path -- the inner loop allocates more path as necessary. 7191573Srgrimes * We really wouldn't have to do the maxlen calculations here, we 7201573Srgrimes * could do them in fts_read before returning the path, but it's a 7211573Srgrimes * lot easier here since the length is part of the dirent structure. 7221573Srgrimes * 7231573Srgrimes * If not changing directories set a pointer so that can just append 7241573Srgrimes * each new name into the path. 7251573Srgrimes */ 7261573Srgrimes len = NAPPEND(cur); 7271573Srgrimes if (ISSET(FTS_NOCHDIR)) { 7281573Srgrimes cp = sp->fts_path + len; 7291573Srgrimes *cp++ = '/'; 73054770Sgreen } else { 73154770Sgreen /* GCC, you're too verbose. */ 73254770Sgreen cp = NULL; 7331573Srgrimes } 73454770Sgreen len++; 73554770Sgreen maxlen = sp->fts_pathlen - len; 7361573Srgrimes 7371573Srgrimes level = cur->fts_level + 1; 7381573Srgrimes 7391573Srgrimes /* Read the directory, attaching each entry to the `link' pointer. */ 74054770Sgreen doadjust = 0; 74128913Simp for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) { 742128946Skientzle dnamlen = dp->d_namlen; 7431573Srgrimes if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) 7441573Srgrimes continue; 7451573Srgrimes 746128946Skientzle if ((p = fts_alloc(sp, dp->d_name, (int)dnamlen)) == NULL) 7471573Srgrimes goto mem1; 748128946Skientzle if (dnamlen >= maxlen) { /* include space for NUL */ 74954770Sgreen oldaddr = sp->fts_path; 750128946Skientzle if (fts_palloc(sp, dnamlen + len + 1)) { 7511573Srgrimes /* 7521573Srgrimes * No more memory for path or structures. Save 7531573Srgrimes * errno, free up the current structure and the 7541573Srgrimes * structures already allocated. 7551573Srgrimes */ 7561573Srgrimesmem1: saved_errno = errno; 7571573Srgrimes if (p) 7581573Srgrimes free(p); 7591573Srgrimes fts_lfree(head); 7601573Srgrimes (void)closedir(dirp); 7611573Srgrimes cur->fts_info = FTS_ERR; 7621573Srgrimes SET(FTS_STOP); 76354770Sgreen errno = saved_errno; 7641573Srgrimes return (NULL); 7651573Srgrimes } 76654770Sgreen /* Did realloc() change the pointer? */ 76754770Sgreen if (oldaddr != sp->fts_path) { 76854770Sgreen doadjust = 1; 76954770Sgreen if (ISSET(FTS_NOCHDIR)) 77054770Sgreen cp = sp->fts_path + len; 77154770Sgreen } 77254770Sgreen maxlen = sp->fts_pathlen - len; 7731573Srgrimes } 7741573Srgrimes 775128946Skientzle if (len + dnamlen >= USHRT_MAX) { 77654770Sgreen /* 77754770Sgreen * In an FTSENT, fts_pathlen is a u_short so it is 77854770Sgreen * possible to wraparound here. If we do, free up 77954770Sgreen * the current structure and the structures already 78054770Sgreen * allocated, then error out with ENAMETOOLONG. 78154770Sgreen */ 78254770Sgreen free(p); 78354770Sgreen fts_lfree(head); 78454770Sgreen (void)closedir(dirp); 78554770Sgreen cur->fts_info = FTS_ERR; 78654770Sgreen SET(FTS_STOP); 78754770Sgreen errno = ENAMETOOLONG; 78854770Sgreen return (NULL); 78954770Sgreen } 79054770Sgreen p->fts_level = level; 7911573Srgrimes p->fts_parent = sp->fts_cur; 792128946Skientzle p->fts_pathlen = len + dnamlen; 7931573Srgrimes 79423668Speter#ifdef FTS_WHITEOUT 79523668Speter if (dp->d_type == DT_WHT) 79623668Speter p->fts_flags |= FTS_ISW; 79723668Speter#endif 79823668Speter 7991573Srgrimes if (cderrno) { 8001573Srgrimes if (nlinks) { 8011573Srgrimes p->fts_info = FTS_NS; 8021573Srgrimes p->fts_errno = cderrno; 8031573Srgrimes } else 8041573Srgrimes p->fts_info = FTS_NSOK; 8051573Srgrimes p->fts_accpath = cur->fts_accpath; 8061573Srgrimes } else if (nlinks == 0 8071573Srgrimes#ifdef DT_DIR 80854770Sgreen || (nostat && 80917141Sjkh dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN) 8101573Srgrimes#endif 8111573Srgrimes ) { 8121573Srgrimes p->fts_accpath = 8131573Srgrimes ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; 8141573Srgrimes p->fts_info = FTS_NSOK; 8151573Srgrimes } else { 8161573Srgrimes /* Build a file name for fts_stat to stat. */ 8171573Srgrimes if (ISSET(FTS_NOCHDIR)) { 8181573Srgrimes p->fts_accpath = p->fts_path; 8191573Srgrimes memmove(cp, p->fts_name, p->fts_namelen + 1); 8201573Srgrimes } else 8211573Srgrimes p->fts_accpath = p->fts_name; 8221573Srgrimes /* Stat it. */ 8231573Srgrimes p->fts_info = fts_stat(sp, p, 0); 8241573Srgrimes 8251573Srgrimes /* Decrement link count if applicable. */ 8261573Srgrimes if (nlinks > 0 && (p->fts_info == FTS_D || 8271573Srgrimes p->fts_info == FTS_DC || p->fts_info == FTS_DOT)) 8281573Srgrimes --nlinks; 8291573Srgrimes } 8301573Srgrimes 8311573Srgrimes /* We walk in directory order so "ls -f" doesn't get upset. */ 8321573Srgrimes p->fts_link = NULL; 8331573Srgrimes if (head == NULL) 8341573Srgrimes head = tail = p; 8351573Srgrimes else { 8361573Srgrimes tail->fts_link = p; 8371573Srgrimes tail = p; 8381573Srgrimes } 8391573Srgrimes ++nitems; 8401573Srgrimes } 84128913Simp if (dirp) 84228913Simp (void)closedir(dirp); 8431573Srgrimes 8441573Srgrimes /* 84554770Sgreen * If realloc() changed the address of the path, adjust the 84654770Sgreen * addresses for the rest of the tree and the dir list. 8471573Srgrimes */ 84854770Sgreen if (doadjust) 84954770Sgreen fts_padjust(sp, head); 8501573Srgrimes 8511573Srgrimes /* 8521573Srgrimes * If not changing directories, reset the path back to original 8531573Srgrimes * state. 8541573Srgrimes */ 8551573Srgrimes if (ISSET(FTS_NOCHDIR)) { 85654770Sgreen if (len == sp->fts_pathlen || nitems == 0) 8571573Srgrimes --cp; 8581573Srgrimes *cp = '\0'; 8591573Srgrimes } 8601573Srgrimes 8611573Srgrimes /* 8621573Srgrimes * If descended after called from fts_children or after called from 8631573Srgrimes * fts_read and nothing found, get back. At the root level we use 8641573Srgrimes * the saved fd; if one of fts_open()'s arguments is a relative path 8651573Srgrimes * to an empty directory, we wind up here with no other way back. If 8661573Srgrimes * can't get back, we're done. 8671573Srgrimes */ 8681573Srgrimes if (descend && (type == BCHILD || !nitems) && 8691573Srgrimes (cur->fts_level == FTS_ROOTLEVEL ? 87077599Skris FCHDIR(sp, sp->fts_rfd) : 87177599Skris fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) { 8721573Srgrimes cur->fts_info = FTS_ERR; 8731573Srgrimes SET(FTS_STOP); 8741573Srgrimes return (NULL); 8751573Srgrimes } 8761573Srgrimes 8771573Srgrimes /* If didn't find anything, return NULL. */ 8781573Srgrimes if (!nitems) { 8791573Srgrimes if (type == BREAD) 8801573Srgrimes cur->fts_info = FTS_DP; 8811573Srgrimes return (NULL); 8821573Srgrimes } 8831573Srgrimes 8841573Srgrimes /* Sort the entries. */ 8851573Srgrimes if (sp->fts_compar && nitems > 1) 8861573Srgrimes head = fts_sort(sp, head, nitems); 8871573Srgrimes return (head); 8881573Srgrimes} 8891573Srgrimes 8901573Srgrimesstatic u_short 891287793Srodrigcfts_stat(FTS *sp, FTSENT *p, int follow) 8921573Srgrimes{ 89390045Sobrien FTSENT *t; 89490045Sobrien dev_t dev; 89590045Sobrien ino_t ino; 8961573Srgrimes struct stat *sbp, sb; 8971573Srgrimes int saved_errno; 8981573Srgrimes 8991573Srgrimes /* If user needs stat info, stat buffer already allocated. */ 9001573Srgrimes sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp; 9018870Srgrimes 90223668Speter#ifdef FTS_WHITEOUT 903129184Sbde /* Check for whiteout. */ 90423668Speter if (p->fts_flags & FTS_ISW) { 90523668Speter if (sbp != &sb) { 906129184Sbde memset(sbp, '\0', sizeof(*sbp)); 90723668Speter sbp->st_mode = S_IFWHT; 90823668Speter } 90923668Speter return (FTS_W); 91023668Speter } 91123668Speter#endif 91223668Speter 9131573Srgrimes /* 9141573Srgrimes * If doing a logical walk, or application requested FTS_FOLLOW, do 9151573Srgrimes * a stat(2). If that fails, check for a non-existent symlink. If 9161573Srgrimes * fail, set the errno from the stat call. 9171573Srgrimes */ 9181573Srgrimes if (ISSET(FTS_LOGICAL) || follow) { 9191573Srgrimes if (stat(p->fts_accpath, sbp)) { 9201573Srgrimes saved_errno = errno; 9211573Srgrimes if (!lstat(p->fts_accpath, sbp)) { 9221573Srgrimes errno = 0; 9231573Srgrimes return (FTS_SLNONE); 9248870Srgrimes } 9251573Srgrimes p->fts_errno = saved_errno; 9261573Srgrimes goto err; 9271573Srgrimes } 9281573Srgrimes } else if (lstat(p->fts_accpath, sbp)) { 9291573Srgrimes p->fts_errno = errno; 9301573Srgrimeserr: memset(sbp, 0, sizeof(struct stat)); 9311573Srgrimes return (FTS_NS); 9321573Srgrimes } 9331573Srgrimes 9341573Srgrimes if (S_ISDIR(sbp->st_mode)) { 9351573Srgrimes /* 9361573Srgrimes * Set the device/inode. Used to find cycles and check for 9371573Srgrimes * crossing mount points. Also remember the link count, used 9381573Srgrimes * in fts_build to limit the number of stat calls. It is 9391573Srgrimes * understood that these fields are only referenced if fts_info 9401573Srgrimes * is set to FTS_D. 9411573Srgrimes */ 9421573Srgrimes dev = p->fts_dev = sbp->st_dev; 9431573Srgrimes ino = p->fts_ino = sbp->st_ino; 9441573Srgrimes p->fts_nlink = sbp->st_nlink; 9451573Srgrimes 9461573Srgrimes if (ISDOT(p->fts_name)) 9471573Srgrimes return (FTS_DOT); 9481573Srgrimes 9491573Srgrimes /* 9501573Srgrimes * Cycle detection is done by brute force when the directory 9511573Srgrimes * is first encountered. If the tree gets deep enough or the 9521573Srgrimes * number of symbolic links to directories is high enough, 9531573Srgrimes * something faster might be worthwhile. 9541573Srgrimes */ 9551573Srgrimes for (t = p->fts_parent; 9561573Srgrimes t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) 9571573Srgrimes if (ino == t->fts_ino && dev == t->fts_dev) { 9581573Srgrimes p->fts_cycle = t; 9591573Srgrimes return (FTS_DC); 9601573Srgrimes } 9611573Srgrimes return (FTS_D); 9621573Srgrimes } 9631573Srgrimes if (S_ISLNK(sbp->st_mode)) 9641573Srgrimes return (FTS_SL); 9651573Srgrimes if (S_ISREG(sbp->st_mode)) 9661573Srgrimes return (FTS_F); 9671573Srgrimes return (FTS_DEFAULT); 9681573Srgrimes} 9691573Srgrimes 970103726Swollman/* 971103726Swollman * The comparison function takes pointers to pointers to FTSENT structures. 972103726Swollman * Qsort wants a comparison function that takes pointers to void. 973103726Swollman * (Both with appropriate levels of const-poisoning, of course!) 974103726Swollman * Use a trampoline function to deal with the difference. 975103726Swollman */ 976103726Swollmanstatic int 977103726Swollmanfts_compar(const void *a, const void *b) 978103726Swollman{ 979103726Swollman FTS *parent; 980103726Swollman 981103726Swollman parent = (*(const FTSENT * const *)a)->fts_fts; 982103726Swollman return (*parent->fts_compar)(a, b); 983103726Swollman} 984103726Swollman 9851573Srgrimesstatic FTSENT * 986287793Srodrigcfts_sort(FTS *sp, FTSENT *head, int nitems) 9871573Srgrimes{ 98890045Sobrien FTSENT **ap, *p; 9891573Srgrimes 9901573Srgrimes /* 9911573Srgrimes * Construct an array of pointers to the structures and call qsort(3). 9921573Srgrimes * Reassemble the array in the order returned by qsort. If unable to 9931573Srgrimes * sort for memory reasons, return the directory entries in their 9941573Srgrimes * current order. Allocate enough space for the current needs plus 9951573Srgrimes * 40 so don't realloc one entry at a time. 9961573Srgrimes */ 9971573Srgrimes if (nitems > sp->fts_nitems) { 9981573Srgrimes sp->fts_nitems = nitems + 40; 99964740Sgreen if ((sp->fts_array = reallocf(sp->fts_array, 100054770Sgreen sp->fts_nitems * sizeof(FTSENT *))) == NULL) { 10011573Srgrimes sp->fts_nitems = 0; 10021573Srgrimes return (head); 10031573Srgrimes } 10041573Srgrimes } 10051573Srgrimes for (ap = sp->fts_array, p = head; p; p = p->fts_link) 10061573Srgrimes *ap++ = p; 1007103726Swollman qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar); 10081573Srgrimes for (head = *(ap = sp->fts_array); --nitems; ++ap) 10091573Srgrimes ap[0]->fts_link = ap[1]; 10101573Srgrimes ap[0]->fts_link = NULL; 10111573Srgrimes return (head); 10121573Srgrimes} 10131573Srgrimes 10141573Srgrimesstatic FTSENT * 1015287793Srodrigcfts_alloc(FTS *sp, char *name, int namelen) 10161573Srgrimes{ 101790045Sobrien FTSENT *p; 10181573Srgrimes size_t len; 10191573Srgrimes 1020103726Swollman struct ftsent_withstat { 1021103726Swollman FTSENT ent; 1022103726Swollman struct stat statbuf; 1023103726Swollman }; 1024103726Swollman 10251573Srgrimes /* 10261573Srgrimes * The file name is a variable length array and no stat structure is 10271573Srgrimes * necessary if the user has set the nostat bit. Allocate the FTSENT 10281573Srgrimes * structure, the file name and the stat structure in one chunk, but 1029103726Swollman * be careful that the stat structure is reasonably aligned. 10301573Srgrimes */ 1031103726Swollman if (ISSET(FTS_NOSTAT)) 1032103726Swollman len = sizeof(FTSENT) + namelen + 1; 1033103726Swollman else 1034103726Swollman len = sizeof(struct ftsent_withstat) + namelen + 1; 1035103726Swollman 10361573Srgrimes if ((p = malloc(len)) == NULL) 10371573Srgrimes return (NULL); 10381573Srgrimes 1039103726Swollman if (ISSET(FTS_NOSTAT)) { 1040103726Swollman p->fts_name = (char *)(p + 1); 1041103726Swollman p->fts_statp = NULL; 1042103726Swollman } else { 1043103726Swollman p->fts_name = (char *)((struct ftsent_withstat *)p + 1); 1044103726Swollman p->fts_statp = &((struct ftsent_withstat *)p)->statbuf; 1045103726Swollman } 1046103726Swollman 104754770Sgreen /* Copy the name and guarantee NUL termination. */ 1048103726Swollman memcpy(p->fts_name, name, namelen); 104954770Sgreen p->fts_name[namelen] = '\0'; 10501573Srgrimes p->fts_namelen = namelen; 10511573Srgrimes p->fts_path = sp->fts_path; 10521573Srgrimes p->fts_errno = 0; 10531573Srgrimes p->fts_flags = 0; 10541573Srgrimes p->fts_instr = FTS_NOINSTR; 10551573Srgrimes p->fts_number = 0; 10561573Srgrimes p->fts_pointer = NULL; 1057103726Swollman p->fts_fts = sp; 10581573Srgrimes return (p); 10591573Srgrimes} 10601573Srgrimes 10611573Srgrimesstatic void 1062287793Srodrigcfts_lfree(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 1080287793Srodrigcfts_palloc(FTS *sp, size_t more) 10811573Srgrimes{ 108254770Sgreen 10831573Srgrimes sp->fts_pathlen += more + 256; 108454770Sgreen /* 108554770Sgreen * Check for possible wraparound. In an FTS, fts_pathlen is 108654770Sgreen * a signed int but in an FTSENT it is an unsigned short. 108754770Sgreen * We limit fts_pathlen to USHRT_MAX to be safe in both cases. 108854770Sgreen */ 108954770Sgreen if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) { 109054770Sgreen if (sp->fts_path) 109154770Sgreen free(sp->fts_path); 109254770Sgreen sp->fts_path = NULL; 109354770Sgreen errno = ENAMETOOLONG; 109454770Sgreen return (1); 109550790Simp } 109664740Sgreen sp->fts_path = reallocf(sp->fts_path, sp->fts_pathlen); 109764740Sgreen return (sp->fts_path == NULL); 109850790Simp} 109950790Simp 11001573Srgrimes/* 11011573Srgrimes * When the path is realloc'd, have to fix all of the pointers in structures 11021573Srgrimes * already returned. 11031573Srgrimes */ 11041573Srgrimesstatic void 1105287793Srodrigcfts_padjust(FTS *sp, FTSENT *head) 11061573Srgrimes{ 11071573Srgrimes FTSENT *p; 110854770Sgreen char *addr = sp->fts_path; 11091573Srgrimes 111064740Sgreen#define ADJUST(p) do { \ 111154770Sgreen if ((p)->fts_accpath != (p)->fts_name) { \ 111254770Sgreen (p)->fts_accpath = \ 111354770Sgreen (char *)addr + ((p)->fts_accpath - (p)->fts_path); \ 111454770Sgreen } \ 11151573Srgrimes (p)->fts_path = addr; \ 111664740Sgreen} while (0) 11171573Srgrimes /* Adjust the current set of children. */ 11181573Srgrimes for (p = sp->fts_child; p; p = p->fts_link) 111954770Sgreen ADJUST(p); 11201573Srgrimes 112154770Sgreen /* Adjust the rest of the tree, including the current level. */ 112254770Sgreen for (p = head; p->fts_level >= FTS_ROOTLEVEL;) { 112354770Sgreen ADJUST(p); 11241573Srgrimes p = p->fts_link ? p->fts_link : p->fts_parent; 11251573Srgrimes } 11261573Srgrimes} 11271573Srgrimes 11281573Srgrimesstatic size_t 1129287793Srodrigcfts_maxarglen(char * const *argv) 11301573Srgrimes{ 11311573Srgrimes size_t len, max; 11321573Srgrimes 11331573Srgrimes for (max = 0; *argv; ++argv) 11341573Srgrimes if ((len = strlen(*argv)) > max) 11351573Srgrimes max = len; 113654770Sgreen return (max + 1); 11371573Srgrimes} 113828913Simp 113928913Simp/* 114028913Simp * Change to dir specified by fd or p->fts_accpath without getting 114128913Simp * tricked by someone changing the world out from underneath us. 114228913Simp * Assumes p->fts_dev and p->fts_ino are filled in. 114328913Simp */ 114428913Simpstatic int 1145287793Srodrigcfts_safe_changedir(FTS *sp, FTSENT *p, int fd, char *path) 114628913Simp{ 114728913Simp int ret, oerrno, newfd; 114828913Simp struct stat sb; 114928913Simp 115028913Simp newfd = fd; 115128913Simp if (ISSET(FTS_NOCHDIR)) 115228913Simp return (0); 1153241010Sjilles if (fd < 0 && (newfd = _open(path, O_RDONLY | O_CLOEXEC, 0)) < 0) 115428913Simp return (-1); 115571579Sdeischen if (_fstat(newfd, &sb)) { 115628913Simp ret = -1; 115728913Simp goto bail; 115828913Simp } 115928913Simp if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) { 116028913Simp errno = ENOENT; /* disinformation */ 116128913Simp ret = -1; 116228913Simp goto bail; 116328913Simp } 116428913Simp ret = fchdir(newfd); 116528913Simpbail: 116628913Simp oerrno = errno; 116728913Simp if (fd < 0) 116856698Sjasone (void)_close(newfd); 116928913Simp errno = oerrno; 117028913Simp return (ret); 117128913Simp} 1172129052Speadar 1173129052Speadar/* 1174129052Speadar * Check if the filesystem for "ent" has UFS-style links. 1175129052Speadar */ 1176129052Speadarstatic int 1177129052Speadarfts_ufslinks(FTS *sp, const FTSENT *ent) 1178129052Speadar{ 1179129052Speadar struct _fts_private *priv; 1180129052Speadar const char **cpp; 1181129052Speadar 1182129161Speadar priv = (struct _fts_private *)sp; 1183129052Speadar /* 1184129052Speadar * If this node's device is different from the previous, grab 1185129052Speadar * the filesystem information, and decide on the reliability 1186129052Speadar * of the link information from this filesystem for stat(2) 1187129052Speadar * avoidance. 1188129052Speadar */ 1189129052Speadar if (priv->ftsp_dev != ent->fts_dev) { 1190129052Speadar if (statfs(ent->fts_path, &priv->ftsp_statfs) != -1) { 1191129052Speadar priv->ftsp_dev = ent->fts_dev; 1192129052Speadar priv->ftsp_linksreliable = 0; 1193129052Speadar for (cpp = ufslike_filesystems; *cpp; cpp++) { 1194129052Speadar if (strcmp(priv->ftsp_statfs.f_fstypename, 1195129052Speadar *cpp) == 0) { 1196129052Speadar priv->ftsp_linksreliable = 1; 1197129052Speadar break; 1198129052Speadar } 1199129052Speadar } 1200129052Speadar } else { 1201129052Speadar priv->ftsp_linksreliable = 0; 1202129052Speadar } 1203129052Speadar } 1204129161Speadar return (priv->ftsp_linksreliable); 1205129052Speadar} 1206175688Syar 1207175688Syar__sym_compat(fts_open, __fts_open_44bsd, FBSD_1.0); 1208175688Syar__sym_compat(fts_close, __fts_close_44bsd, FBSD_1.0); 1209175688Syar__sym_compat(fts_read, __fts_read_44bsd, FBSD_1.0); 1210175688Syar__sym_compat(fts_set, __fts_set_44bsd, FBSD_1.0); 1211175688Syar__sym_compat(fts_children, __fts_children_44bsd, FBSD_1.0); 1212175688Syar__sym_compat(fts_get_clientptr, __fts_get_clientptr_44bsd, FBSD_1.0); 1213175688Syar__sym_compat(fts_get_stream, __fts_get_stream_44bsd, FBSD_1.0); 1214175688Syar__sym_compat(fts_set_clientptr, __fts_set_clientptr_44bsd, FBSD_1.0); 1215