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 55235647Sgleb#include "gen-private.h" 56235647Sgleb 57175688Syarstatic FTSENT *fts_alloc(FTS *, char *, size_t); 5890045Sobrienstatic FTSENT *fts_build(FTS *, int); 5990045Sobrienstatic void fts_lfree(FTSENT *); 6090045Sobrienstatic void fts_load(FTS *, FTSENT *); 6190045Sobrienstatic size_t fts_maxarglen(char * const *); 6290045Sobrienstatic void fts_padjust(FTS *, FTSENT *); 6390045Sobrienstatic int fts_palloc(FTS *, size_t); 64175688Syarstatic FTSENT *fts_sort(FTS *, FTSENT *, size_t); 65175688Syarstatic int fts_stat(FTS *, FTSENT *, int); 6690045Sobrienstatic int fts_safe_changedir(FTS *, FTSENT *, int, char *); 67129161Speadarstatic int fts_ufslinks(FTS *, const FTSENT *); 681573Srgrimes 6928913Simp#define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2]))) 701573Srgrimes 7128913Simp#define CLR(opt) (sp->fts_options &= ~(opt)) 7228913Simp#define ISSET(opt) (sp->fts_options & (opt)) 7328913Simp#define SET(opt) (sp->fts_options |= (opt)) 741573Srgrimes 751573Srgrimes#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd)) 761573Srgrimes 771573Srgrimes/* fts_build flags */ 781573Srgrimes#define BCHILD 1 /* fts_children */ 791573Srgrimes#define BNAMES 2 /* fts_children, names only */ 801573Srgrimes#define BREAD 3 /* fts_read */ 811573Srgrimes 82129052Speadar/* 83129161Speadar * Internal representation of an FTS, including extra implementation 84129161Speadar * details. The FTS returned from fts_open points to this structure's 85129161Speadar * ftsp_fts member (and can be cast to an _fts_private as required) 86129052Speadar */ 87129052Speadarstruct _fts_private { 88129161Speadar FTS ftsp_fts; 89129161Speadar struct statfs ftsp_statfs; 90129161Speadar dev_t ftsp_dev; 91129161Speadar int ftsp_linksreliable; 92129052Speadar}; 93129052Speadar 94129052Speadar/* 95129161Speadar * The "FTS_NOSTAT" option can avoid a lot of calls to stat(2) if it 96129161Speadar * knows that a directory could not possibly have subdirectories. This 97129161Speadar * is decided by looking at the link count: a subdirectory would 98129161Speadar * increment its parent's link count by virtue of its own ".." entry. 99129161Speadar * This assumption only holds for UFS-like filesystems that implement 100129161Speadar * links and directories this way, so we must punt for others. 101129052Speadar */ 102129052Speadar 103129052Speadarstatic const char *ufslike_filesystems[] = { 104129052Speadar "ufs", 105219696Spjd "zfs", 106129052Speadar "nfs", 107129052Speadar "nfs4", 108129052Speadar "ext2fs", 109129052Speadar 0 110129052Speadar}; 111129052Speadar 1121573SrgrimesFTS * 1131573Srgrimesfts_open(argv, options, compar) 1141573Srgrimes char * const *argv; 11590045Sobrien int options; 116103726Swollman int (*compar)(const FTSENT * const *, const FTSENT * const *); 1171573Srgrimes{ 118129052Speadar struct _fts_private *priv; 11990045Sobrien FTS *sp; 12090045Sobrien FTSENT *p, *root; 1211573Srgrimes FTSENT *parent, *tmp; 122175688Syar size_t len, nitems; 1231573Srgrimes 1241573Srgrimes /* Options check. */ 1251573Srgrimes if (options & ~FTS_OPTIONMASK) { 1261573Srgrimes errno = EINVAL; 1271573Srgrimes return (NULL); 1281573Srgrimes } 1291573Srgrimes 130197793Sdelphij /* fts_open() requires at least one path */ 131197793Sdelphij if (*argv == NULL) { 132197793Sdelphij errno = EINVAL; 133197793Sdelphij return (NULL); 134197793Sdelphij } 135197793Sdelphij 136129184Sbde /* Allocate/initialize the stream. */ 137238963Sdelphij if ((priv = calloc(1, sizeof(*priv))) == NULL) 1381573Srgrimes return (NULL); 139129052Speadar sp = &priv->ftsp_fts; 1401573Srgrimes sp->fts_compar = compar; 1411573Srgrimes sp->fts_options = options; 1421573Srgrimes 14354770Sgreen /* Shush, GCC. */ 14454770Sgreen tmp = NULL; 14554770Sgreen 1461573Srgrimes /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ 1471573Srgrimes if (ISSET(FTS_LOGICAL)) 1481573Srgrimes SET(FTS_NOCHDIR); 1491573Srgrimes 1501573Srgrimes /* 1511573Srgrimes * Start out with 1K of path space, and enough, in any case, 1521573Srgrimes * to hold the user's paths. 1531573Srgrimes */ 1541573Srgrimes if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN))) 1551573Srgrimes goto mem1; 1561573Srgrimes 1571573Srgrimes /* Allocate/initialize root's parent. */ 1581573Srgrimes if ((parent = fts_alloc(sp, "", 0)) == NULL) 1591573Srgrimes goto mem2; 1601573Srgrimes parent->fts_level = FTS_ROOTPARENTLEVEL; 1611573Srgrimes 1621573Srgrimes /* Allocate/initialize root(s). */ 16364740Sgreen for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) { 164264172Sjilles len = strlen(*argv); 1651573Srgrimes 1661573Srgrimes p = fts_alloc(sp, *argv, len); 1671573Srgrimes p->fts_level = FTS_ROOTLEVEL; 1681573Srgrimes p->fts_parent = parent; 1691573Srgrimes p->fts_accpath = p->fts_name; 1701573Srgrimes p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW)); 1711573Srgrimes 1721573Srgrimes /* Command-line "." and ".." are real directories. */ 1731573Srgrimes if (p->fts_info == FTS_DOT) 1741573Srgrimes p->fts_info = FTS_D; 1751573Srgrimes 1761573Srgrimes /* 1771573Srgrimes * If comparison routine supplied, traverse in sorted 1781573Srgrimes * order; otherwise traverse in the order specified. 1791573Srgrimes */ 1801573Srgrimes if (compar) { 1811573Srgrimes p->fts_link = root; 1821573Srgrimes root = p; 1831573Srgrimes } else { 1841573Srgrimes p->fts_link = NULL; 1851573Srgrimes if (root == NULL) 1861573Srgrimes tmp = root = p; 1871573Srgrimes else { 1881573Srgrimes tmp->fts_link = p; 1891573Srgrimes tmp = p; 1901573Srgrimes } 1911573Srgrimes } 1921573Srgrimes } 1931573Srgrimes if (compar && nitems > 1) 1941573Srgrimes root = fts_sort(sp, root, nitems); 1951573Srgrimes 1961573Srgrimes /* 1971573Srgrimes * Allocate a dummy pointer and make fts_read think that we've just 1981573Srgrimes * finished the node before the root(s); set p->fts_info to FTS_INIT 1991573Srgrimes * so that everything about the "current" node is ignored. 2001573Srgrimes */ 2011573Srgrimes if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL) 2021573Srgrimes goto mem3; 2031573Srgrimes sp->fts_cur->fts_link = root; 2041573Srgrimes sp->fts_cur->fts_info = FTS_INIT; 2051573Srgrimes 2061573Srgrimes /* 20754770Sgreen * If using chdir(2), grab a file descriptor pointing to dot to ensure 2081573Srgrimes * that we can get back here; this could be avoided for some paths, 2091573Srgrimes * but almost certainly not worth the effort. Slashes, symbolic links, 2101573Srgrimes * and ".." are all fairly nasty problems. Note, if we can't get the 2111573Srgrimes * descriptor we run anyway, just more slowly. 2121573Srgrimes */ 213241010Sjilles if (!ISSET(FTS_NOCHDIR) && 214241010Sjilles (sp->fts_rfd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) 2151573Srgrimes SET(FTS_NOCHDIR); 2161573Srgrimes 2171573Srgrimes return (sp); 2181573Srgrimes 2191573Srgrimesmem3: fts_lfree(root); 2201573Srgrimes free(parent); 2211573Srgrimesmem2: free(sp->fts_path); 2221573Srgrimesmem1: free(sp); 2231573Srgrimes return (NULL); 2241573Srgrimes} 2251573Srgrimes 2261573Srgrimesstatic void 227231891Sdelphijfts_load(FTS *sp, FTSENT *p) 2281573Srgrimes{ 229175688Syar size_t len; 23090045Sobrien char *cp; 2311573Srgrimes 2321573Srgrimes /* 2331573Srgrimes * Load the stream structure for the next traversal. Since we don't 2341573Srgrimes * actually enter the directory until after the preorder visit, set 2351573Srgrimes * the fts_accpath field specially so the chdir gets done to the right 2361573Srgrimes * place and the user can access the first node. From fts_open it's 2371573Srgrimes * known that the path will fit. 2381573Srgrimes */ 2391573Srgrimes len = p->fts_pathlen = p->fts_namelen; 2401573Srgrimes memmove(sp->fts_path, p->fts_name, len + 1); 2411573Srgrimes if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { 2421573Srgrimes len = strlen(++cp); 2431573Srgrimes memmove(p->fts_name, cp, len + 1); 2441573Srgrimes p->fts_namelen = len; 2451573Srgrimes } 2461573Srgrimes p->fts_accpath = p->fts_path = sp->fts_path; 2471573Srgrimes sp->fts_dev = p->fts_dev; 2481573Srgrimes} 2491573Srgrimes 2501573Srgrimesint 251231891Sdelphijfts_close(FTS *sp) 2521573Srgrimes{ 25390045Sobrien FTSENT *freep, *p; 2541573Srgrimes int saved_errno; 2551573Srgrimes 2561573Srgrimes /* 2571573Srgrimes * This still works if we haven't read anything -- the dummy structure 2581573Srgrimes * points to the root list, so we step through to the end of the root 2591573Srgrimes * list which has a valid parent pointer. 2601573Srgrimes */ 2611573Srgrimes if (sp->fts_cur) { 2621573Srgrimes for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { 2631573Srgrimes freep = p; 26464740Sgreen p = p->fts_link != NULL ? p->fts_link : p->fts_parent; 2651573Srgrimes free(freep); 2661573Srgrimes } 2671573Srgrimes free(p); 2681573Srgrimes } 2691573Srgrimes 2701573Srgrimes /* Free up child linked list, sort array, path buffer. */ 2711573Srgrimes if (sp->fts_child) 2721573Srgrimes fts_lfree(sp->fts_child); 2731573Srgrimes if (sp->fts_array) 2741573Srgrimes free(sp->fts_array); 2751573Srgrimes free(sp->fts_path); 2761573Srgrimes 2771573Srgrimes /* Return to original directory, save errno if necessary. */ 2781573Srgrimes if (!ISSET(FTS_NOCHDIR)) { 2791573Srgrimes saved_errno = fchdir(sp->fts_rfd) ? errno : 0; 28056698Sjasone (void)_close(sp->fts_rfd); 28154770Sgreen 28254770Sgreen /* Set errno and return. */ 28354770Sgreen if (saved_errno != 0) { 28454770Sgreen /* Free up the stream pointer. */ 28554770Sgreen free(sp); 28654770Sgreen errno = saved_errno; 28754770Sgreen return (-1); 28854770Sgreen } 2891573Srgrimes } 2901573Srgrimes 29137349Sphk /* Free up the stream pointer. */ 29237349Sphk free(sp); 2931573Srgrimes return (0); 2941573Srgrimes} 2951573Srgrimes 2961573Srgrimes/* 29728913Simp * Special case of "/" at the end of the path so that slashes aren't 29828913Simp * appended which would cause paths to be written as "....//foo". 2991573Srgrimes */ 3001573Srgrimes#define NAPPEND(p) \ 30128913Simp (p->fts_path[p->fts_pathlen - 1] == '/' \ 30228913Simp ? p->fts_pathlen - 1 : p->fts_pathlen) 3031573Srgrimes 3041573SrgrimesFTSENT * 305231891Sdelphijfts_read(FTS *sp) 3061573Srgrimes{ 30790045Sobrien FTSENT *p, *tmp; 30890045Sobrien int instr; 30990045Sobrien char *t; 3101573Srgrimes int saved_errno; 3111573Srgrimes 3121573Srgrimes /* If finished or unrecoverable error, return NULL. */ 3131573Srgrimes if (sp->fts_cur == NULL || ISSET(FTS_STOP)) 3141573Srgrimes return (NULL); 3151573Srgrimes 3161573Srgrimes /* Set current node pointer. */ 3171573Srgrimes p = sp->fts_cur; 3181573Srgrimes 3191573Srgrimes /* Save and zero out user instructions. */ 3201573Srgrimes instr = p->fts_instr; 3211573Srgrimes p->fts_instr = FTS_NOINSTR; 3221573Srgrimes 3231573Srgrimes /* Any type of file may be re-visited; re-stat and re-turn. */ 3241573Srgrimes if (instr == FTS_AGAIN) { 3251573Srgrimes p->fts_info = fts_stat(sp, p, 0); 3261573Srgrimes return (p); 3271573Srgrimes } 3281573Srgrimes 3291573Srgrimes /* 3301573Srgrimes * Following a symlink -- SLNONE test allows application to see 3311573Srgrimes * SLNONE and recover. If indirecting through a symlink, have 3321573Srgrimes * keep a pointer to current location. If unable to get that 3331573Srgrimes * pointer, follow fails. 3341573Srgrimes */ 3351573Srgrimes if (instr == FTS_FOLLOW && 3361573Srgrimes (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { 3371573Srgrimes p->fts_info = fts_stat(sp, p, 1); 33854770Sgreen if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { 339241010Sjilles if ((p->fts_symfd = _open(".", O_RDONLY | O_CLOEXEC, 340241010Sjilles 0)) < 0) { 3411573Srgrimes p->fts_errno = errno; 3421573Srgrimes p->fts_info = FTS_ERR; 3431573Srgrimes } else 3441573Srgrimes p->fts_flags |= FTS_SYMFOLLOW; 34554770Sgreen } 3461573Srgrimes return (p); 3471573Srgrimes } 3481573Srgrimes 3491573Srgrimes /* Directory in pre-order. */ 3501573Srgrimes if (p->fts_info == FTS_D) { 3511573Srgrimes /* If skipped or crossed mount point, do post-order visit. */ 3521573Srgrimes if (instr == FTS_SKIP || 35328913Simp (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) { 3541573Srgrimes if (p->fts_flags & FTS_SYMFOLLOW) 35556698Sjasone (void)_close(p->fts_symfd); 3561573Srgrimes if (sp->fts_child) { 3571573Srgrimes fts_lfree(sp->fts_child); 3581573Srgrimes sp->fts_child = NULL; 3591573Srgrimes } 3601573Srgrimes p->fts_info = FTS_DP; 3611573Srgrimes return (p); 3628870Srgrimes } 3631573Srgrimes 3641573Srgrimes /* Rebuild if only read the names and now traversing. */ 36564740Sgreen if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) { 36628913Simp CLR(FTS_NAMEONLY); 3671573Srgrimes fts_lfree(sp->fts_child); 3681573Srgrimes sp->fts_child = NULL; 3691573Srgrimes } 3701573Srgrimes 3711573Srgrimes /* 3721573Srgrimes * Cd to the subdirectory. 3731573Srgrimes * 3741573Srgrimes * If have already read and now fail to chdir, whack the list 3751573Srgrimes * to make the names come out right, and set the parent errno 3761573Srgrimes * so the application will eventually get an error condition. 3771573Srgrimes * Set the FTS_DONTCHDIR flag so that when we logically change 3781573Srgrimes * directories back to the parent we don't do a chdir. 3791573Srgrimes * 3801573Srgrimes * If haven't read do so. If the read fails, fts_build sets 3811573Srgrimes * FTS_STOP or the fts_info field of the node. 3821573Srgrimes */ 38364740Sgreen if (sp->fts_child != NULL) { 38477599Skris if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) { 3851573Srgrimes p->fts_errno = errno; 3861573Srgrimes p->fts_flags |= FTS_DONTCHDIR; 387129184Sbde for (p = sp->fts_child; p != NULL; 38864740Sgreen p = p->fts_link) 3891573Srgrimes p->fts_accpath = 3901573Srgrimes p->fts_parent->fts_accpath; 3911573Srgrimes } 3921573Srgrimes } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) { 3931573Srgrimes if (ISSET(FTS_STOP)) 3941573Srgrimes return (NULL); 3951573Srgrimes return (p); 3961573Srgrimes } 3971573Srgrimes p = sp->fts_child; 3981573Srgrimes sp->fts_child = NULL; 3991573Srgrimes goto name; 4001573Srgrimes } 4011573Srgrimes 4021573Srgrimes /* Move to the next node on this level. */ 4031573Srgrimesnext: tmp = p; 40464740Sgreen if ((p = p->fts_link) != NULL) { 4051573Srgrimes /* 40654770Sgreen * If reached the top, return to the original directory (or 40754770Sgreen * the root of the tree), and load the paths for the next root. 4081573Srgrimes */ 4091573Srgrimes if (p->fts_level == FTS_ROOTLEVEL) { 41028913Simp if (FCHDIR(sp, sp->fts_rfd)) { 4111573Srgrimes SET(FTS_STOP); 4121573Srgrimes return (NULL); 4131573Srgrimes } 414262892Sjilles free(tmp); 4151573Srgrimes fts_load(sp, p); 4161573Srgrimes return (sp->fts_cur = p); 4171573Srgrimes } 4181573Srgrimes 4191573Srgrimes /* 4201573Srgrimes * User may have called fts_set on the node. If skipped, 4211573Srgrimes * ignore. If followed, get a file descriptor so we can 4221573Srgrimes * get back if necessary. 4231573Srgrimes */ 424262892Sjilles if (p->fts_instr == FTS_SKIP) { 425262892Sjilles free(tmp); 4261573Srgrimes goto next; 427262892Sjilles } 4281573Srgrimes if (p->fts_instr == FTS_FOLLOW) { 4291573Srgrimes p->fts_info = fts_stat(sp, p, 1); 43054770Sgreen if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { 4311573Srgrimes if ((p->fts_symfd = 432241010Sjilles _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) { 4331573Srgrimes p->fts_errno = errno; 4341573Srgrimes p->fts_info = FTS_ERR; 4351573Srgrimes } else 4361573Srgrimes p->fts_flags |= FTS_SYMFOLLOW; 43754770Sgreen } 4381573Srgrimes p->fts_instr = FTS_NOINSTR; 4391573Srgrimes } 4401573Srgrimes 441262892Sjilles free(tmp); 442262892Sjilles 4431573Srgrimesname: t = sp->fts_path + NAPPEND(p->fts_parent); 4441573Srgrimes *t++ = '/'; 4451573Srgrimes memmove(t, p->fts_name, p->fts_namelen + 1); 4461573Srgrimes return (sp->fts_cur = p); 4471573Srgrimes } 4481573Srgrimes 4491573Srgrimes /* Move up to the parent node. */ 4501573Srgrimes p = tmp->fts_parent; 4511573Srgrimes 4521573Srgrimes if (p->fts_level == FTS_ROOTPARENTLEVEL) { 4531573Srgrimes /* 4541573Srgrimes * Done; free everything up and set errno to 0 so the user 4551573Srgrimes * can distinguish between error and EOF. 4561573Srgrimes */ 457262892Sjilles free(tmp); 4581573Srgrimes free(p); 4591573Srgrimes errno = 0; 4601573Srgrimes return (sp->fts_cur = NULL); 4611573Srgrimes } 4621573Srgrimes 46354770Sgreen /* NUL terminate the pathname. */ 4641573Srgrimes sp->fts_path[p->fts_pathlen] = '\0'; 4651573Srgrimes 4661573Srgrimes /* 4671573Srgrimes * Return to the parent directory. If at a root node or came through 4681573Srgrimes * a symlink, go back through the file descriptor. Otherwise, cd up 4691573Srgrimes * one directory. 4701573Srgrimes */ 4711573Srgrimes if (p->fts_level == FTS_ROOTLEVEL) { 47228913Simp if (FCHDIR(sp, sp->fts_rfd)) { 4731573Srgrimes SET(FTS_STOP); 4741573Srgrimes return (NULL); 4751573Srgrimes } 4761573Srgrimes } else if (p->fts_flags & FTS_SYMFOLLOW) { 4771573Srgrimes if (FCHDIR(sp, p->fts_symfd)) { 4781573Srgrimes saved_errno = errno; 47956698Sjasone (void)_close(p->fts_symfd); 4801573Srgrimes errno = saved_errno; 4811573Srgrimes SET(FTS_STOP); 4821573Srgrimes return (NULL); 4831573Srgrimes } 48456698Sjasone (void)_close(p->fts_symfd); 48577497Skris } else if (!(p->fts_flags & FTS_DONTCHDIR) && 486129184Sbde fts_safe_changedir(sp, p->fts_parent, -1, "..")) { 48777599Skris SET(FTS_STOP); 48877599Skris return (NULL); 4891573Srgrimes } 490262892Sjilles free(tmp); 4911573Srgrimes p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP; 4921573Srgrimes return (sp->fts_cur = p); 4931573Srgrimes} 4941573Srgrimes 4951573Srgrimes/* 4961573Srgrimes * Fts_set takes the stream as an argument although it's not used in this 4971573Srgrimes * implementation; it would be necessary if anyone wanted to add global 4981573Srgrimes * semantics to fts using fts_set. An error return is allowed for similar 4991573Srgrimes * reasons. 5001573Srgrimes */ 5011573Srgrimes/* ARGSUSED */ 5021573Srgrimesint 503231891Sdelphijfts_set(FTS *sp, FTSENT *p, int instr) 5041573Srgrimes{ 50564740Sgreen if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW && 5061573Srgrimes instr != FTS_NOINSTR && instr != FTS_SKIP) { 5071573Srgrimes errno = EINVAL; 5081573Srgrimes return (1); 5091573Srgrimes } 5101573Srgrimes p->fts_instr = instr; 5111573Srgrimes return (0); 5121573Srgrimes} 5131573Srgrimes 5141573SrgrimesFTSENT * 515231891Sdelphijfts_children(FTS *sp, int instr) 5161573Srgrimes{ 51790045Sobrien FTSENT *p; 5181573Srgrimes int fd; 5191573Srgrimes 52064740Sgreen if (instr != 0 && instr != FTS_NAMEONLY) { 5211573Srgrimes errno = EINVAL; 5221573Srgrimes return (NULL); 5231573Srgrimes } 5241573Srgrimes 5251573Srgrimes /* Set current node pointer. */ 5261573Srgrimes p = sp->fts_cur; 5271573Srgrimes 5281573Srgrimes /* 5291573Srgrimes * Errno set to 0 so user can distinguish empty directory from 5301573Srgrimes * an error. 5311573Srgrimes */ 5321573Srgrimes errno = 0; 5331573Srgrimes 5341573Srgrimes /* Fatal errors stop here. */ 5351573Srgrimes if (ISSET(FTS_STOP)) 5361573Srgrimes return (NULL); 5371573Srgrimes 5381573Srgrimes /* Return logical hierarchy of user's arguments. */ 5391573Srgrimes if (p->fts_info == FTS_INIT) 5401573Srgrimes return (p->fts_link); 5411573Srgrimes 5421573Srgrimes /* 5431573Srgrimes * If not a directory being visited in pre-order, stop here. Could 5441573Srgrimes * allow FTS_DNR, assuming the user has fixed the problem, but the 5451573Srgrimes * same effect is available with FTS_AGAIN. 5461573Srgrimes */ 5471573Srgrimes if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */) 5481573Srgrimes return (NULL); 5491573Srgrimes 5501573Srgrimes /* Free up any previous child list. */ 55164740Sgreen if (sp->fts_child != NULL) 5521573Srgrimes fts_lfree(sp->fts_child); 5531573Srgrimes 5541573Srgrimes if (instr == FTS_NAMEONLY) { 55528913Simp SET(FTS_NAMEONLY); 5561573Srgrimes instr = BNAMES; 5578870Srgrimes } else 5581573Srgrimes instr = BCHILD; 5591573Srgrimes 5601573Srgrimes /* 5611573Srgrimes * If using chdir on a relative path and called BEFORE fts_read does 5621573Srgrimes * its chdir to the root of a traversal, we can lose -- we need to 5631573Srgrimes * chdir into the subdirectory, and we don't know where the current 5641573Srgrimes * directory is, so we can't get back so that the upcoming chdir by 5651573Srgrimes * fts_read will work. 5661573Srgrimes */ 5671573Srgrimes if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || 5681573Srgrimes ISSET(FTS_NOCHDIR)) 5691573Srgrimes return (sp->fts_child = fts_build(sp, instr)); 5701573Srgrimes 571241010Sjilles if ((fd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) 5721573Srgrimes return (NULL); 5731573Srgrimes sp->fts_child = fts_build(sp, instr); 574189348Sdas if (fchdir(fd)) { 575189348Sdas (void)_close(fd); 5761573Srgrimes return (NULL); 577189348Sdas } 57856698Sjasone (void)_close(fd); 5791573Srgrimes return (sp->fts_child); 5801573Srgrimes} 5811573Srgrimes 582103726Swollman#ifndef fts_get_clientptr 583103726Swollman#error "fts_get_clientptr not defined" 584103726Swollman#endif 585103726Swollman 586103726Swollmanvoid * 587103726Swollman(fts_get_clientptr)(FTS *sp) 588103726Swollman{ 589103726Swollman 590103726Swollman return (fts_get_clientptr(sp)); 591103726Swollman} 592103726Swollman 593103726Swollman#ifndef fts_get_stream 594103726Swollman#error "fts_get_stream not defined" 595103726Swollman#endif 596103726Swollman 597103726SwollmanFTS * 598103726Swollman(fts_get_stream)(FTSENT *p) 599103726Swollman{ 600103726Swollman return (fts_get_stream(p)); 601103726Swollman} 602103726Swollman 603103726Swollmanvoid 604103726Swollmanfts_set_clientptr(FTS *sp, void *clientptr) 605103726Swollman{ 606103726Swollman 607103726Swollman sp->fts_clientptr = clientptr; 608103726Swollman} 609103726Swollman 6101573Srgrimes/* 6111573Srgrimes * This is the tricky part -- do not casually change *anything* in here. The 6121573Srgrimes * idea is to build the linked list of entries that are used by fts_children 6131573Srgrimes * and fts_read. There are lots of special cases. 6141573Srgrimes * 6151573Srgrimes * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is 6161573Srgrimes * set and it's a physical walk (so that symbolic links can't be directories), 6171573Srgrimes * we can do things quickly. First, if it's a 4.4BSD file system, the type 6181573Srgrimes * of the file is in the directory entry. Otherwise, we assume that the number 6191573Srgrimes * of subdirectories in a node is equal to the number of links to the parent. 6201573Srgrimes * The former skips all stat calls. The latter skips stat calls in any leaf 6211573Srgrimes * directories and for any files after the subdirectories in the directory have 6221573Srgrimes * been found, cutting the stat calls by about 2/3. 6231573Srgrimes */ 6241573Srgrimesstatic FTSENT * 625231891Sdelphijfts_build(FTS *sp, int type) 6261573Srgrimes{ 62790045Sobrien struct dirent *dp; 62890045Sobrien FTSENT *p, *head; 6291573Srgrimes FTSENT *cur, *tail; 6301573Srgrimes DIR *dirp; 63154770Sgreen void *oldaddr; 6321573Srgrimes char *cp; 633175688Syar int cderrno, descend, oflag, saved_errno, nostat, doadjust; 634175688Syar long level; 635175688Syar long nlinks; /* has to be signed because -1 is a magic value */ 636175688Syar size_t dnamlen, len, maxlen, nitems; 6371573Srgrimes 6381573Srgrimes /* Set current node pointer. */ 6391573Srgrimes cur = sp->fts_cur; 6401573Srgrimes 6411573Srgrimes /* 6421573Srgrimes * Open the directory for reading. If this fails, we're done. 6431573Srgrimes * If being called from fts_read, set the fts_info field. 6441573Srgrimes */ 64523668Speter#ifdef FTS_WHITEOUT 64623668Speter if (ISSET(FTS_WHITEOUT)) 647129184Sbde oflag = DTF_NODUP | DTF_REWIND; 64823668Speter else 649129184Sbde oflag = DTF_HIDEW | DTF_NODUP | DTF_REWIND; 65023668Speter#else 65123668Speter#define __opendir2(path, flag) opendir(path) 65223668Speter#endif 65323668Speter if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) { 6541573Srgrimes if (type == BREAD) { 6551573Srgrimes cur->fts_info = FTS_DNR; 6561573Srgrimes cur->fts_errno = errno; 6571573Srgrimes } 6581573Srgrimes return (NULL); 6591573Srgrimes } 6601573Srgrimes 6611573Srgrimes /* 6621573Srgrimes * Nlinks is the number of possible entries of type directory in the 6631573Srgrimes * directory if we're cheating on stat calls, 0 if we're not doing 6641573Srgrimes * any stat calls at all, -1 if we're doing stats on everything. 6651573Srgrimes */ 66654770Sgreen if (type == BNAMES) { 6671573Srgrimes nlinks = 0; 66854770Sgreen /* Be quiet about nostat, GCC. */ 66954770Sgreen nostat = 0; 67054770Sgreen } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) { 671129052Speadar if (fts_ufslinks(sp, cur)) 672129052Speadar nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2); 673129052Speadar else 674129052Speadar nlinks = -1; 67554770Sgreen nostat = 1; 67654770Sgreen } else { 6771573Srgrimes nlinks = -1; 67854770Sgreen nostat = 0; 67954770Sgreen } 6801573Srgrimes 6811573Srgrimes#ifdef notdef 6821573Srgrimes (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink); 6831573Srgrimes (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n", 6841573Srgrimes ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT)); 6851573Srgrimes#endif 6861573Srgrimes /* 6871573Srgrimes * If we're going to need to stat anything or we want to descend 6881573Srgrimes * and stay in the directory, chdir. If this fails we keep going, 6891573Srgrimes * but set a flag so we don't chdir after the post-order visit. 6901573Srgrimes * We won't be able to stat anything, but we can still return the 6911573Srgrimes * names themselves. Note, that since fts_read won't be able to 6921573Srgrimes * chdir into the directory, it will have to return different path 6931573Srgrimes * names than before, i.e. "a/b" instead of "b". Since the node 6941573Srgrimes * has already been visited in pre-order, have to wait until the 6951573Srgrimes * post-order visit to return the error. There is a special case 6961573Srgrimes * here, if there was nothing to stat then it's not an error to 6971573Srgrimes * not be able to stat. This is all fairly nasty. If a program 6981573Srgrimes * needed sorted entries or stat information, they had better be 6991573Srgrimes * checking FTS_NS on the returned nodes. 7001573Srgrimes */ 7011573Srgrimes cderrno = 0; 70254770Sgreen if (nlinks || type == BREAD) { 703235647Sgleb if (fts_safe_changedir(sp, cur, _dirfd(dirp), NULL)) { 7041573Srgrimes if (nlinks && type == BREAD) 7051573Srgrimes cur->fts_errno = errno; 7061573Srgrimes cur->fts_flags |= FTS_DONTCHDIR; 7071573Srgrimes descend = 0; 7081573Srgrimes cderrno = errno; 7091573Srgrimes } else 7101573Srgrimes descend = 1; 71154770Sgreen } else 7121573Srgrimes descend = 0; 7131573Srgrimes 7141573Srgrimes /* 7151573Srgrimes * Figure out the max file name length that can be stored in the 7161573Srgrimes * current path -- the inner loop allocates more path as necessary. 7171573Srgrimes * We really wouldn't have to do the maxlen calculations here, we 7181573Srgrimes * could do them in fts_read before returning the path, but it's a 7191573Srgrimes * lot easier here since the length is part of the dirent structure. 7201573Srgrimes * 7211573Srgrimes * If not changing directories set a pointer so that can just append 7221573Srgrimes * each new name into the path. 7231573Srgrimes */ 7241573Srgrimes len = NAPPEND(cur); 7251573Srgrimes if (ISSET(FTS_NOCHDIR)) { 7261573Srgrimes cp = sp->fts_path + len; 7271573Srgrimes *cp++ = '/'; 72854770Sgreen } else { 72954770Sgreen /* GCC, you're too verbose. */ 73054770Sgreen cp = NULL; 7311573Srgrimes } 73254770Sgreen len++; 73354770Sgreen maxlen = sp->fts_pathlen - len; 7341573Srgrimes 7351573Srgrimes level = cur->fts_level + 1; 7361573Srgrimes 7371573Srgrimes /* Read the directory, attaching each entry to the `link' pointer. */ 73854770Sgreen doadjust = 0; 73928913Simp for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) { 740128946Skientzle dnamlen = dp->d_namlen; 7411573Srgrimes if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) 7421573Srgrimes continue; 7431573Srgrimes 744175688Syar if ((p = fts_alloc(sp, dp->d_name, dnamlen)) == NULL) 7451573Srgrimes goto mem1; 746128946Skientzle if (dnamlen >= maxlen) { /* include space for NUL */ 74754770Sgreen oldaddr = sp->fts_path; 748128946Skientzle if (fts_palloc(sp, dnamlen + len + 1)) { 7491573Srgrimes /* 7501573Srgrimes * No more memory for path or structures. Save 7511573Srgrimes * errno, free up the current structure and the 7521573Srgrimes * structures already allocated. 7531573Srgrimes */ 7541573Srgrimesmem1: saved_errno = errno; 7551573Srgrimes if (p) 7561573Srgrimes free(p); 7571573Srgrimes fts_lfree(head); 7581573Srgrimes (void)closedir(dirp); 7591573Srgrimes cur->fts_info = FTS_ERR; 7601573Srgrimes SET(FTS_STOP); 76154770Sgreen errno = saved_errno; 7621573Srgrimes return (NULL); 7631573Srgrimes } 76454770Sgreen /* Did realloc() change the pointer? */ 76554770Sgreen if (oldaddr != sp->fts_path) { 76654770Sgreen doadjust = 1; 76754770Sgreen if (ISSET(FTS_NOCHDIR)) 76854770Sgreen cp = sp->fts_path + len; 76954770Sgreen } 77054770Sgreen maxlen = sp->fts_pathlen - len; 7711573Srgrimes } 7721573Srgrimes 77354770Sgreen p->fts_level = level; 7741573Srgrimes p->fts_parent = sp->fts_cur; 775128946Skientzle p->fts_pathlen = len + dnamlen; 7761573Srgrimes 77723668Speter#ifdef FTS_WHITEOUT 77823668Speter if (dp->d_type == DT_WHT) 77923668Speter p->fts_flags |= FTS_ISW; 78023668Speter#endif 78123668Speter 7821573Srgrimes if (cderrno) { 7831573Srgrimes if (nlinks) { 7841573Srgrimes p->fts_info = FTS_NS; 7851573Srgrimes p->fts_errno = cderrno; 7861573Srgrimes } else 7871573Srgrimes p->fts_info = FTS_NSOK; 7881573Srgrimes p->fts_accpath = cur->fts_accpath; 7891573Srgrimes } else if (nlinks == 0 7901573Srgrimes#ifdef DT_DIR 79154770Sgreen || (nostat && 79217141Sjkh dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN) 7931573Srgrimes#endif 7941573Srgrimes ) { 7951573Srgrimes p->fts_accpath = 7961573Srgrimes ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; 7971573Srgrimes p->fts_info = FTS_NSOK; 7981573Srgrimes } else { 7991573Srgrimes /* Build a file name for fts_stat to stat. */ 8001573Srgrimes if (ISSET(FTS_NOCHDIR)) { 8011573Srgrimes p->fts_accpath = p->fts_path; 8021573Srgrimes memmove(cp, p->fts_name, p->fts_namelen + 1); 8031573Srgrimes } else 8041573Srgrimes p->fts_accpath = p->fts_name; 8051573Srgrimes /* Stat it. */ 8061573Srgrimes p->fts_info = fts_stat(sp, p, 0); 8071573Srgrimes 8081573Srgrimes /* Decrement link count if applicable. */ 8091573Srgrimes if (nlinks > 0 && (p->fts_info == FTS_D || 8101573Srgrimes p->fts_info == FTS_DC || p->fts_info == FTS_DOT)) 8111573Srgrimes --nlinks; 8121573Srgrimes } 8131573Srgrimes 8141573Srgrimes /* We walk in directory order so "ls -f" doesn't get upset. */ 8151573Srgrimes p->fts_link = NULL; 8161573Srgrimes if (head == NULL) 8171573Srgrimes head = tail = p; 8181573Srgrimes else { 8191573Srgrimes tail->fts_link = p; 8201573Srgrimes tail = p; 8211573Srgrimes } 8221573Srgrimes ++nitems; 8231573Srgrimes } 82428913Simp if (dirp) 82528913Simp (void)closedir(dirp); 8261573Srgrimes 8271573Srgrimes /* 82854770Sgreen * If realloc() changed the address of the path, adjust the 82954770Sgreen * addresses for the rest of the tree and the dir list. 8301573Srgrimes */ 83154770Sgreen if (doadjust) 83254770Sgreen fts_padjust(sp, head); 8331573Srgrimes 8341573Srgrimes /* 8351573Srgrimes * If not changing directories, reset the path back to original 8361573Srgrimes * state. 8371573Srgrimes */ 838199844Sjh if (ISSET(FTS_NOCHDIR)) 839199844Sjh sp->fts_path[cur->fts_pathlen] = '\0'; 8401573Srgrimes 8411573Srgrimes /* 8421573Srgrimes * If descended after called from fts_children or after called from 8431573Srgrimes * fts_read and nothing found, get back. At the root level we use 8441573Srgrimes * the saved fd; if one of fts_open()'s arguments is a relative path 8451573Srgrimes * to an empty directory, we wind up here with no other way back. If 8461573Srgrimes * can't get back, we're done. 8471573Srgrimes */ 8481573Srgrimes if (descend && (type == BCHILD || !nitems) && 8491573Srgrimes (cur->fts_level == FTS_ROOTLEVEL ? 85077599Skris FCHDIR(sp, sp->fts_rfd) : 85177599Skris fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) { 8521573Srgrimes cur->fts_info = FTS_ERR; 8531573Srgrimes SET(FTS_STOP); 8541573Srgrimes return (NULL); 8551573Srgrimes } 8561573Srgrimes 8571573Srgrimes /* If didn't find anything, return NULL. */ 8581573Srgrimes if (!nitems) { 8591573Srgrimes if (type == BREAD) 8601573Srgrimes cur->fts_info = FTS_DP; 8611573Srgrimes return (NULL); 8621573Srgrimes } 8631573Srgrimes 8641573Srgrimes /* Sort the entries. */ 8651573Srgrimes if (sp->fts_compar && nitems > 1) 8661573Srgrimes head = fts_sort(sp, head, nitems); 8671573Srgrimes return (head); 8681573Srgrimes} 8691573Srgrimes 870175688Syarstatic int 871231891Sdelphijfts_stat(FTS *sp, FTSENT *p, int follow) 8721573Srgrimes{ 87390045Sobrien FTSENT *t; 87490045Sobrien dev_t dev; 87590045Sobrien ino_t ino; 8761573Srgrimes struct stat *sbp, sb; 8771573Srgrimes int saved_errno; 8781573Srgrimes 8791573Srgrimes /* If user needs stat info, stat buffer already allocated. */ 8801573Srgrimes sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp; 8818870Srgrimes 88223668Speter#ifdef FTS_WHITEOUT 883129184Sbde /* Check for whiteout. */ 88423668Speter if (p->fts_flags & FTS_ISW) { 88523668Speter if (sbp != &sb) { 886129184Sbde memset(sbp, '\0', sizeof(*sbp)); 88723668Speter sbp->st_mode = S_IFWHT; 88823668Speter } 88923668Speter return (FTS_W); 89023668Speter } 89123668Speter#endif 89223668Speter 8931573Srgrimes /* 8941573Srgrimes * If doing a logical walk, or application requested FTS_FOLLOW, do 8951573Srgrimes * a stat(2). If that fails, check for a non-existent symlink. If 8961573Srgrimes * fail, set the errno from the stat call. 8971573Srgrimes */ 8981573Srgrimes if (ISSET(FTS_LOGICAL) || follow) { 8991573Srgrimes if (stat(p->fts_accpath, sbp)) { 9001573Srgrimes saved_errno = errno; 9011573Srgrimes if (!lstat(p->fts_accpath, sbp)) { 9021573Srgrimes errno = 0; 9031573Srgrimes return (FTS_SLNONE); 9048870Srgrimes } 9051573Srgrimes p->fts_errno = saved_errno; 9061573Srgrimes goto err; 9071573Srgrimes } 9081573Srgrimes } else if (lstat(p->fts_accpath, sbp)) { 9091573Srgrimes p->fts_errno = errno; 9101573Srgrimeserr: memset(sbp, 0, sizeof(struct stat)); 9111573Srgrimes return (FTS_NS); 9121573Srgrimes } 9131573Srgrimes 9141573Srgrimes if (S_ISDIR(sbp->st_mode)) { 9151573Srgrimes /* 9161573Srgrimes * Set the device/inode. Used to find cycles and check for 9171573Srgrimes * crossing mount points. Also remember the link count, used 9181573Srgrimes * in fts_build to limit the number of stat calls. It is 9191573Srgrimes * understood that these fields are only referenced if fts_info 9201573Srgrimes * is set to FTS_D. 9211573Srgrimes */ 9221573Srgrimes dev = p->fts_dev = sbp->st_dev; 9231573Srgrimes ino = p->fts_ino = sbp->st_ino; 9241573Srgrimes p->fts_nlink = sbp->st_nlink; 9251573Srgrimes 9261573Srgrimes if (ISDOT(p->fts_name)) 9271573Srgrimes return (FTS_DOT); 9281573Srgrimes 9291573Srgrimes /* 9301573Srgrimes * Cycle detection is done by brute force when the directory 9311573Srgrimes * is first encountered. If the tree gets deep enough or the 9321573Srgrimes * number of symbolic links to directories is high enough, 9331573Srgrimes * something faster might be worthwhile. 9341573Srgrimes */ 9351573Srgrimes for (t = p->fts_parent; 9361573Srgrimes t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) 9371573Srgrimes if (ino == t->fts_ino && dev == t->fts_dev) { 9381573Srgrimes p->fts_cycle = t; 9391573Srgrimes return (FTS_DC); 9401573Srgrimes } 9411573Srgrimes return (FTS_D); 9421573Srgrimes } 9431573Srgrimes if (S_ISLNK(sbp->st_mode)) 9441573Srgrimes return (FTS_SL); 9451573Srgrimes if (S_ISREG(sbp->st_mode)) 9461573Srgrimes return (FTS_F); 9471573Srgrimes return (FTS_DEFAULT); 9481573Srgrimes} 9491573Srgrimes 950103726Swollman/* 951103726Swollman * The comparison function takes pointers to pointers to FTSENT structures. 952103726Swollman * Qsort wants a comparison function that takes pointers to void. 953103726Swollman * (Both with appropriate levels of const-poisoning, of course!) 954103726Swollman * Use a trampoline function to deal with the difference. 955103726Swollman */ 956103726Swollmanstatic int 957103726Swollmanfts_compar(const void *a, const void *b) 958103726Swollman{ 959103726Swollman FTS *parent; 960103726Swollman 961103726Swollman parent = (*(const FTSENT * const *)a)->fts_fts; 962103726Swollman return (*parent->fts_compar)(a, b); 963103726Swollman} 964103726Swollman 9651573Srgrimesstatic FTSENT * 966231891Sdelphijfts_sort(FTS *sp, FTSENT *head, size_t nitems) 9671573Srgrimes{ 96890045Sobrien FTSENT **ap, *p; 9691573Srgrimes 9701573Srgrimes /* 9711573Srgrimes * Construct an array of pointers to the structures and call qsort(3). 9721573Srgrimes * Reassemble the array in the order returned by qsort. If unable to 9731573Srgrimes * sort for memory reasons, return the directory entries in their 9741573Srgrimes * current order. Allocate enough space for the current needs plus 9751573Srgrimes * 40 so don't realloc one entry at a time. 9761573Srgrimes */ 9771573Srgrimes if (nitems > sp->fts_nitems) { 9781573Srgrimes sp->fts_nitems = nitems + 40; 97964740Sgreen if ((sp->fts_array = reallocf(sp->fts_array, 98054770Sgreen sp->fts_nitems * sizeof(FTSENT *))) == NULL) { 9811573Srgrimes sp->fts_nitems = 0; 9821573Srgrimes return (head); 9831573Srgrimes } 9841573Srgrimes } 9851573Srgrimes for (ap = sp->fts_array, p = head; p; p = p->fts_link) 9861573Srgrimes *ap++ = p; 987103726Swollman qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar); 9881573Srgrimes for (head = *(ap = sp->fts_array); --nitems; ++ap) 9891573Srgrimes ap[0]->fts_link = ap[1]; 9901573Srgrimes ap[0]->fts_link = NULL; 9911573Srgrimes return (head); 9921573Srgrimes} 9931573Srgrimes 9941573Srgrimesstatic FTSENT * 995231891Sdelphijfts_alloc(FTS *sp, char *name, size_t namelen) 9961573Srgrimes{ 99790045Sobrien FTSENT *p; 9981573Srgrimes size_t len; 9991573Srgrimes 1000103726Swollman struct ftsent_withstat { 1001103726Swollman FTSENT ent; 1002103726Swollman struct stat statbuf; 1003103726Swollman }; 1004103726Swollman 10051573Srgrimes /* 10061573Srgrimes * The file name is a variable length array and no stat structure is 10071573Srgrimes * necessary if the user has set the nostat bit. Allocate the FTSENT 10081573Srgrimes * structure, the file name and the stat structure in one chunk, but 1009103726Swollman * be careful that the stat structure is reasonably aligned. 10101573Srgrimes */ 1011103726Swollman if (ISSET(FTS_NOSTAT)) 1012103726Swollman len = sizeof(FTSENT) + namelen + 1; 1013103726Swollman else 1014103726Swollman len = sizeof(struct ftsent_withstat) + namelen + 1; 1015103726Swollman 10161573Srgrimes if ((p = malloc(len)) == NULL) 10171573Srgrimes return (NULL); 10181573Srgrimes 1019103726Swollman if (ISSET(FTS_NOSTAT)) { 1020103726Swollman p->fts_name = (char *)(p + 1); 1021103726Swollman p->fts_statp = NULL; 1022103726Swollman } else { 1023103726Swollman p->fts_name = (char *)((struct ftsent_withstat *)p + 1); 1024103726Swollman p->fts_statp = &((struct ftsent_withstat *)p)->statbuf; 1025103726Swollman } 1026103726Swollman 102754770Sgreen /* Copy the name and guarantee NUL termination. */ 1028103726Swollman memcpy(p->fts_name, name, namelen); 102954770Sgreen p->fts_name[namelen] = '\0'; 10301573Srgrimes p->fts_namelen = namelen; 10311573Srgrimes p->fts_path = sp->fts_path; 10321573Srgrimes p->fts_errno = 0; 10331573Srgrimes p->fts_flags = 0; 10341573Srgrimes p->fts_instr = FTS_NOINSTR; 10351573Srgrimes p->fts_number = 0; 10361573Srgrimes p->fts_pointer = NULL; 1037103726Swollman p->fts_fts = sp; 10381573Srgrimes return (p); 10391573Srgrimes} 10401573Srgrimes 10411573Srgrimesstatic void 1042231891Sdelphijfts_lfree(FTSENT *head) 10431573Srgrimes{ 104490045Sobrien FTSENT *p; 10451573Srgrimes 10461573Srgrimes /* Free a linked list of structures. */ 104728913Simp while ((p = head)) { 10481573Srgrimes head = head->fts_link; 10491573Srgrimes free(p); 10501573Srgrimes } 10511573Srgrimes} 10521573Srgrimes 10531573Srgrimes/* 10541573Srgrimes * Allow essentially unlimited paths; find, rm, ls should all work on any tree. 10551573Srgrimes * Most systems will allow creation of paths much longer than MAXPATHLEN, even 10561573Srgrimes * though the kernel won't resolve them. Add the size (not just what's needed) 10578870Srgrimes * plus 256 bytes so don't realloc the path 2 bytes at a time. 10581573Srgrimes */ 10591573Srgrimesstatic int 1060231891Sdelphijfts_palloc(FTS *sp, size_t more) 10611573Srgrimes{ 106254770Sgreen 10631573Srgrimes sp->fts_pathlen += more + 256; 106464740Sgreen sp->fts_path = reallocf(sp->fts_path, sp->fts_pathlen); 106564740Sgreen return (sp->fts_path == NULL); 106650790Simp} 106750790Simp 10681573Srgrimes/* 10691573Srgrimes * When the path is realloc'd, have to fix all of the pointers in structures 10701573Srgrimes * already returned. 10711573Srgrimes */ 10721573Srgrimesstatic void 1073231891Sdelphijfts_padjust(FTS *sp, FTSENT *head) 10741573Srgrimes{ 10751573Srgrimes FTSENT *p; 107654770Sgreen char *addr = sp->fts_path; 10771573Srgrimes 107864740Sgreen#define ADJUST(p) do { \ 107954770Sgreen if ((p)->fts_accpath != (p)->fts_name) { \ 108054770Sgreen (p)->fts_accpath = \ 108154770Sgreen (char *)addr + ((p)->fts_accpath - (p)->fts_path); \ 108254770Sgreen } \ 10831573Srgrimes (p)->fts_path = addr; \ 108464740Sgreen} while (0) 10851573Srgrimes /* Adjust the current set of children. */ 10861573Srgrimes for (p = sp->fts_child; p; p = p->fts_link) 108754770Sgreen ADJUST(p); 10881573Srgrimes 108954770Sgreen /* Adjust the rest of the tree, including the current level. */ 109054770Sgreen for (p = head; p->fts_level >= FTS_ROOTLEVEL;) { 109154770Sgreen ADJUST(p); 10921573Srgrimes p = p->fts_link ? p->fts_link : p->fts_parent; 10931573Srgrimes } 10941573Srgrimes} 10951573Srgrimes 10961573Srgrimesstatic size_t 10971573Srgrimesfts_maxarglen(argv) 10981573Srgrimes char * const *argv; 10991573Srgrimes{ 11001573Srgrimes size_t len, max; 11011573Srgrimes 11021573Srgrimes for (max = 0; *argv; ++argv) 11031573Srgrimes if ((len = strlen(*argv)) > max) 11041573Srgrimes max = len; 110554770Sgreen return (max + 1); 11061573Srgrimes} 110728913Simp 110828913Simp/* 110928913Simp * Change to dir specified by fd or p->fts_accpath without getting 111028913Simp * tricked by someone changing the world out from underneath us. 111128913Simp * Assumes p->fts_dev and p->fts_ino are filled in. 111228913Simp */ 111328913Simpstatic int 1114231891Sdelphijfts_safe_changedir(FTS *sp, FTSENT *p, int fd, char *path) 111528913Simp{ 111628913Simp int ret, oerrno, newfd; 111728913Simp struct stat sb; 111828913Simp 111928913Simp newfd = fd; 112028913Simp if (ISSET(FTS_NOCHDIR)) 112128913Simp return (0); 1122246641Sjilles if (fd < 0 && (newfd = _open(path, O_RDONLY | O_DIRECTORY | 1123246641Sjilles O_CLOEXEC, 0)) < 0) 112428913Simp return (-1); 112571579Sdeischen if (_fstat(newfd, &sb)) { 112628913Simp ret = -1; 112728913Simp goto bail; 112828913Simp } 112928913Simp if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) { 113028913Simp errno = ENOENT; /* disinformation */ 113128913Simp ret = -1; 113228913Simp goto bail; 113328913Simp } 113428913Simp ret = fchdir(newfd); 113528913Simpbail: 113628913Simp oerrno = errno; 113728913Simp if (fd < 0) 113856698Sjasone (void)_close(newfd); 113928913Simp errno = oerrno; 114028913Simp return (ret); 114128913Simp} 1142129052Speadar 1143129052Speadar/* 1144129052Speadar * Check if the filesystem for "ent" has UFS-style links. 1145129052Speadar */ 1146129052Speadarstatic int 1147129052Speadarfts_ufslinks(FTS *sp, const FTSENT *ent) 1148129052Speadar{ 1149129052Speadar struct _fts_private *priv; 1150129052Speadar const char **cpp; 1151129052Speadar 1152129161Speadar priv = (struct _fts_private *)sp; 1153129052Speadar /* 1154129052Speadar * If this node's device is different from the previous, grab 1155129052Speadar * the filesystem information, and decide on the reliability 1156129052Speadar * of the link information from this filesystem for stat(2) 1157129052Speadar * avoidance. 1158129052Speadar */ 1159129052Speadar if (priv->ftsp_dev != ent->fts_dev) { 1160129052Speadar if (statfs(ent->fts_path, &priv->ftsp_statfs) != -1) { 1161129052Speadar priv->ftsp_dev = ent->fts_dev; 1162129052Speadar priv->ftsp_linksreliable = 0; 1163129052Speadar for (cpp = ufslike_filesystems; *cpp; cpp++) { 1164129052Speadar if (strcmp(priv->ftsp_statfs.f_fstypename, 1165129052Speadar *cpp) == 0) { 1166129052Speadar priv->ftsp_linksreliable = 1; 1167129052Speadar break; 1168129052Speadar } 1169129052Speadar } 1170129052Speadar } else { 1171129052Speadar priv->ftsp_linksreliable = 0; 1172129052Speadar } 1173129052Speadar } 1174129161Speadar return (priv->ftsp_linksreliable); 1175129052Speadar} 1176