1 /* Traverse a file hierarchy. 2 3 Copyright (C) 2004-2015 Free Software Foundation, Inc. 4 5 This program is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 17 18 /* 19 * Copyright (c) 1989, 1993 20 * The Regents of the University of California. All rights reserved. 21 * 22 * Redistribution and use in source and binary forms, with or without 23 * modification, are permitted provided that the following conditions 24 * are met: 25 * 1. Redistributions of source code must retain the above copyright 26 * notice, this list of conditions and the following disclaimer. 27 * 2. Redistributions in binary form must reproduce the above copyright 28 * notice, this list of conditions and the following disclaimer in the 29 * documentation and/or other materials provided with the distribution. 30 * 4. Neither the name of the University nor the names of its contributors 31 * may be used to endorse or promote products derived from this software 32 * without specific prior written permission. 33 * 34 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" AND 35 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 36 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 37 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 38 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 39 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 40 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 41 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 42 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 43 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 44 * SUCH DAMAGE. 45 * 46 * @(#)fts.h 8.3 (Berkeley) 8/14/94 47 */ 48 49 #ifndef _FTS_H 50 # define _FTS_H 1 51 52 # ifdef _LIBC 53 # include <features.h> 54 # if __STDC_VERSION__ < 199901L 55 # define __FLEXIBLE_ARRAY_MEMBER 1 56 # else 57 # define __FLEXIBLE_ARRAY_MEMBER 58 # endif 59 # else 60 # define __FLEXIBLE_ARRAY_MEMBER FLEXIBLE_ARRAY_MEMBER 61 # undef __THROW 62 # define __THROW 63 # undef __BEGIN_DECLS 64 # undef __END_DECLS 65 # ifdef __cplusplus 66 # define __BEGIN_DECLS extern "C" { 67 # define __END_DECLS } 68 # else 69 # define __BEGIN_DECLS 70 # define __END_DECLS 71 # endif 72 # endif 73 74 # include <stddef.h> 75 # include <sys/types.h> 76 # include <dirent.h> 77 # include <sys/stat.h> 78 # include "i-ring.h" 79 80 typedef struct { 81 struct _ftsent *fts_cur; /* current node */ 82 struct _ftsent *fts_child; /* linked list of children */ 83 struct _ftsent **fts_array; /* sort array */ 84 dev_t fts_dev; /* starting device # */ 85 char *fts_path; /* file name for this descent */ 86 int fts_rfd; /* fd for root */ 87 int fts_cwd_fd; /* the file descriptor on which the 88 virtual cwd is open, or AT_FDCWD */ 89 size_t fts_pathlen; /* sizeof(path) */ 90 size_t fts_nitems; /* elements in the sort array */ 91 int (*fts_compar) (struct _ftsent const **, struct _ftsent const **); 92 /* compare fn */ 93 94 # define FTS_COMFOLLOW 0x0001 /* follow command line symlinks */ 95 # define FTS_LOGICAL 0x0002 /* logical walk */ 96 # define FTS_NOCHDIR 0x0004 /* don't change directories */ 97 # define FTS_NOSTAT 0x0008 /* don't get stat info */ 98 # define FTS_PHYSICAL 0x0010 /* physical walk */ 99 # define FTS_SEEDOT 0x0020 /* return dot and dot-dot */ 100 # define FTS_XDEV 0x0040 /* don't cross devices */ 101 # define FTS_WHITEOUT 0x0080 /* return whiteout information */ 102 103 /* There are two ways to detect cycles. 104 The lazy way (which works only with FTS_PHYSICAL), 105 with which one may process a directory that is a 106 part of the cycle several times before detecting the cycle. 107 The "tight" way, whereby fts uses more memory (proportional 108 to number of "active" directories, aka distance from root 109 of current tree to current directory -- see active_dir_ht) 110 to detect any cycle right away. For example, du must use 111 this option to avoid counting disk space in a cycle multiple 112 times, but chown -R need not. 113 The default is to use the constant-memory lazy way, when possible 114 (see below). 115 116 However, with FTS_LOGICAL (when following symlinks, e.g., chown -L) 117 using lazy cycle detection is inadequate. For example, traversing 118 a directory containing a symbolic link to a peer directory, it is 119 possible to encounter the same directory twice even though there 120 is no cycle: 121 dir 122 ... 123 slink -> dir 124 So, when FTS_LOGICAL is selected, we have to use a different 125 mode of cycle detection: FTS_TIGHT_CYCLE_CHECK. */ 126 # define FTS_TIGHT_CYCLE_CHECK 0x0100 127 128 /* Use this flag to enable semantics with which the parent 129 application may be made both more efficient and more robust. 130 Whereas the default is to visit each directory in a recursive 131 traversal (via chdir), using this flag makes it so the initial 132 working directory is never changed. Instead, these functions 133 perform the traversal via a virtual working directory, maintained 134 through the file descriptor member, fts_cwd_fd. */ 135 # define FTS_CWDFD 0x0200 136 137 /* Historically, for each directory that fts initially encounters, it would 138 open it, read all entries, and stat each entry, storing the results, and 139 then it would process the first entry. But that behavior is bad for 140 locality of reference, and also causes trouble with inode-simulating 141 file systems like FAT, CIFS, FUSE-based ones, etc., when entries from 142 their name/inode cache are flushed too early. 143 Use this flag to make fts_open and fts_read defer the stat/lstat/fststat 144 of each entry until it is actually processed. However, note that if you 145 use this option and also specify a comparison function, that function may 146 not examine any data via fts_statp. However, when fts_statp->st_mode is 147 nonzero, the S_IFMT type bits are valid, with mapped dirent.d_type data. 148 Of course, that happens only on file systems that provide useful 149 dirent.d_type data. */ 150 # define FTS_DEFER_STAT 0x0400 151 152 # define FTS_NOATIME 0x0800 /* use O_NOATIME during traversal */ 153 154 /* Use this flag to disable stripping of trailing slashes 155 from input path names during fts_open initialization. */ 156 # define FTS_VERBATIM 0x1000 157 158 # define FTS_OPTIONMASK 0x1fff /* valid user option mask */ 159 160 # define FTS_NAMEONLY 0x2000 /* (private) child names only */ 161 # define FTS_STOP 0x4000 /* (private) unrecoverable error */ 162 int fts_options; /* fts_open options, global flags */ 163 164 /* Map a directory's device number to a boolean. The boolean is 165 true if for that file system (type determined by a single fstatfs 166 call per FS) st_nlink can be used to calculate the number of 167 sub-directory entries in a directory. 168 Using this table is an optimization that permits us to look up 169 file system type on a per-inode basis at the minimal cost of 170 calling fstatfs only once per traversed device. */ 171 struct hash_table *fts_leaf_optimization_works_ht; 172 173 union { 174 /* This data structure is used if FTS_TIGHT_CYCLE_CHECK is 175 specified. It records the directories between a starting 176 point and the current directory. I.e., a directory is 177 recorded here IFF we have visited it once, but we have not 178 yet completed processing of all its entries. Every time we 179 visit a new directory, we add that directory to this set. 180 When we finish with a directory (usually by visiting it a 181 second time), we remove it from this set. Each entry in 182 this data structure is a device/inode pair. This data 183 structure is used to detect directory cycles efficiently and 184 promptly even when the depth of a hierarchy is in the tens 185 of thousands. */ 186 struct hash_table *ht; 187 188 /* FIXME: rename these two members to have the fts_ prefix */ 189 /* This data structure uses a lazy cycle-detection algorithm, 190 as done by rm via cycle-check.c. It's the default, 191 but it's not appropriate for programs like du. */ 192 struct cycle_check_state *state; 193 } fts_cycle; 194 195 /* A stack of the file descriptors corresponding to the 196 most-recently traversed parent directories. 197 Currently used only in FTS_CWDFD mode. */ 198 I_ring fts_fd_ring; 199 } FTS; 200 201 typedef struct _ftsent { 202 struct _ftsent *fts_cycle; /* cycle node */ 203 struct _ftsent *fts_parent; /* parent directory */ 204 struct _ftsent *fts_link; /* next file in directory */ 205 DIR *fts_dirp; /* Dir pointer for any directory 206 containing more entries than we 207 read at one time. */ 208 long fts_number; /* local numeric value */ 209 void *fts_pointer; /* local address value */ 210 char *fts_accpath; /* access file name */ 211 char *fts_path; /* root name; == fts_fts->fts_path */ 212 int fts_errno; /* errno for this node */ 213 int fts_symfd; /* fd for symlink */ 214 size_t fts_pathlen; /* strlen(fts_path) */ 215 216 FTS *fts_fts; /* the file hierarchy itself */ 217 218 # define FTS_ROOTPARENTLEVEL (-1) 219 # define FTS_ROOTLEVEL 0 220 ptrdiff_t fts_level; /* depth (-1 to N) */ 221 222 size_t fts_namelen; /* strlen(fts_name) */ 223 nlink_t fts_n_dirs_remaining; /* count down from st_nlink */ 224 225 # define FTS_D 1 /* preorder directory */ 226 # define FTS_DC 2 /* directory that causes cycles */ 227 # define FTS_DEFAULT 3 /* none of the above */ 228 # define FTS_DNR 4 /* unreadable directory */ 229 # define FTS_DOT 5 /* dot or dot-dot */ 230 # define FTS_DP 6 /* postorder directory */ 231 # define FTS_ERR 7 /* error; errno is set */ 232 # define FTS_F 8 /* regular file */ 233 # define FTS_INIT 9 /* initialized only */ 234 # define FTS_NS 10 /* stat(2) failed */ 235 # define FTS_NSOK 11 /* no stat(2) requested */ 236 # define FTS_SL 12 /* symbolic link */ 237 # define FTS_SLNONE 13 /* symbolic link without target */ 238 # define FTS_W 14 /* whiteout object */ 239 unsigned short int fts_info; /* user flags for FTSENT structure */ 240 241 # define FTS_DONTCHDIR 0x01 /* don't chdir .. to the parent */ 242 # define FTS_SYMFOLLOW 0x02 /* followed a symlink to get here */ 243 unsigned short int fts_flags; /* private flags for FTSENT structure */ 244 245 # define FTS_AGAIN 1 /* read node again */ 246 # define FTS_FOLLOW 2 /* follow symbolic link */ 247 # define FTS_NOINSTR 3 /* no instructions */ 248 # define FTS_SKIP 4 /* discard node */ 249 unsigned short int fts_instr; /* fts_set() instructions */ 250 251 struct stat fts_statp[1]; /* stat(2) information */ 252 char fts_name[__FLEXIBLE_ARRAY_MEMBER]; /* file name */ 253 } FTSENT; 254 255 #ifndef __GNUC_PREREQ 256 # if defined __GNUC__ && defined __GNUC_MINOR__ 257 # define __GNUC_PREREQ(maj, min) \ 258 ((__GNUC__ << 16) + __GNUC_MINOR__ >= ((maj) << 16) + (min)) 259 # else 260 # define __GNUC_PREREQ(maj, min) 0 261 # endif 262 #endif 263 264 #if __GNUC_PREREQ (3,4) 265 # undef __attribute_warn_unused_result__ 266 # define __attribute_warn_unused_result__ \ 267 __attribute__ ((__warn_unused_result__)) 268 #else 269 # define __attribute_warn_unused_result__ /* empty */ 270 #endif 271 272 __BEGIN_DECLS 273 FTSENT *fts_children (FTS *, int) __THROW __attribute_warn_unused_result__; 274 int fts_close (FTS *) __THROW __attribute_warn_unused_result__; 275 FTS *fts_open (char * const *, int, 276 int (*)(const FTSENT **, const FTSENT **)) 277 __THROW __attribute_warn_unused_result__; 278 FTSENT *fts_read (FTS *) __THROW __attribute_warn_unused_result__; 279 int fts_set (FTS *, FTSENT *, int) __THROW; 280 __END_DECLS 281 282 #endif /* fts.h */ 283