1 /*
2 File: walk_tree.c
3
4 Copyright (C) 2007 Andreas Gruenbacher <a.gruenbacher@computer.org>
5
6 This program is free software; you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License as published by the
8 Free Software Foundation; either version 2.1 of the License, or (at
9 your option) any later version.
10
11 This program is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
14 License for more details.
15
16 You should have received a copy of the GNU Lesser General Public
17 License along with this program. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include "config.h"
21
22 #include <sys/types.h>
23 #include <sys/stat.h>
24 #include <unistd.h>
25 #include <sys/time.h>
26 #include <sys/resource.h>
27 #include <dirent.h>
28 #include <stdio.h>
29 #include <string.h>
30 #include <errno.h>
31
32 #include "walk_tree.h"
33
34 struct entry_handle {
35 struct entry_handle *prev, *next;
36 dev_t dev;
37 ino_t ino;
38 DIR *stream;
39 long pos;
40 };
41
42 struct walk_tree_args {
43 char path[FILENAME_MAX];
44 int walk_flags;
45 int (*func)(const char *, const struct stat *, int, void *);
46 void *arg;
47 int depth;
48 struct entry_handle dirs;
49 struct entry_handle *closed;
50 unsigned int num_dir_handles;
51 struct stat st;
52 dev_t dev;
53 };
54
55 static int walk_tree_visited(struct entry_handle *dirs, dev_t dev, ino_t ino)
56 {
57 struct entry_handle *i;
58
59 for (i = dirs->next; i != dirs; i = i->next)
60 if (i->dev == dev && i->ino == ino)
61 return 1;
62 return 0;
63 }
64
65 static int walk_tree_rec(struct walk_tree_args *args)
66 {
67 int follow_symlinks = (args->walk_flags & WALK_TREE_LOGICAL) ||
68 ((args->walk_flags & WALK_TREE_DEREFERENCE) &&
69 !(args->walk_flags & WALK_TREE_PHYSICAL) &&
70 args->depth == 0);
71 int have_dir_stat = 0, flags = args->walk_flags, err;
72 struct entry_handle dir;
73
74 /*
75 * If (walk_flags & WALK_TREE_PHYSICAL), do not traverse symlinks.
76 * If (walk_flags & WALK_TREE_LOGICAL), traverse all symlinks.
77 * Otherwise, traverse only top-level symlinks.
78 */
79 if (args->depth == 0)
80 flags |= WALK_TREE_TOPLEVEL;
81
82 if (lstat(args->path, &args->st) != 0)
83 return args->func(args->path, NULL, flags | WALK_TREE_FAILED,
84 args->arg);
85
86 if (flags & WALK_TREE_ONE_FILESYSTEM) {
87 if (args->dev == 0)
88 args->dev = args->st.st_dev;
89 else if (args->st.st_dev != args->dev)
90 return 0;
91 }
92
93 if (S_ISLNK(args->st.st_mode)) {
94 flags |= WALK_TREE_SYMLINK;
95 if ((flags & WALK_TREE_DEREFERENCE) ||
96 ((flags & WALK_TREE_TOPLEVEL) &&
97 (flags & WALK_TREE_DEREFERENCE_TOPLEVEL))) {
98 if (stat(args->path, &args->st) != 0)
99 return args->func(args->path, NULL,
100 flags | WALK_TREE_FAILED,
101 args->arg);
102 dir.dev = args->st.st_dev;
103 dir.ino = args->st.st_ino;
104 have_dir_stat = 1;
105 }
106 } else if (S_ISDIR(args->st.st_mode)) {
107 dir.dev = args->st.st_dev;
108 dir.ino = args->st.st_ino;
109 have_dir_stat = 1;
110 }
111 err = args->func(args->path, &args->st, flags, args->arg);
112
113 /*
114 * Recurse if WALK_TREE_RECURSIVE and the path is:
115 * a dir not from a symlink
116 * a link and follow_symlinks
117 */
118 if ((flags & WALK_TREE_RECURSIVE) &&
119 ((!(flags & WALK_TREE_SYMLINK) && S_ISDIR(args->st.st_mode)) ||
120 ((flags & WALK_TREE_SYMLINK) && follow_symlinks))) {
121 struct dirent *entry;
122
123 /*
124 * Check if we have already visited this directory to break
125 * endless loops.
126 *
127 * If we haven't stat()ed the file yet, do an opendir() for
128 * figuring out whether we have a directory, and check whether
129 * the directory has been visited afterwards. This saves a
130 * system call for each non-directory found.
131 */
132 if (have_dir_stat && walk_tree_visited(&args->dirs, dir.dev, dir.ino))
133 return err;
134
135 if (args->num_dir_handles == 0 && args->closed->prev != &args->dirs) {
136 close_another_dir:
137 /* Close the topmost directory handle still open. */
138 args->closed = args->closed->prev;
139 args->closed->pos = telldir(args->closed->stream);
140 closedir(args->closed->stream);
141 args->closed->stream = NULL;
142 args->num_dir_handles++;
143 }
144
145 dir.stream = opendir(args->path);
146 if (!dir.stream) {
147 if (errno == ENFILE && args->closed->prev != &args->dirs) {
148 /* Ran out of file descriptors. */
149 args->num_dir_handles = 0;
150 goto close_another_dir;
151 }
152
153 /*
154 * PATH may be a symlink to a regular file, or a dead
155 * symlink which we didn't follow above.
156 */
157 if (errno != ENOTDIR && errno != ENOENT)
158 err += args->func(args->path, NULL, flags |
159 WALK_TREE_FAILED, args->arg);
160 return err;
161 }
162
163 /* See walk_tree_visited() comment above... */
164 if (!have_dir_stat) {
165 if (stat(args->path, &args->st) != 0)
166 goto skip_dir;
167 dir.dev = args->st.st_dev;
168 dir.ino = args->st.st_ino;
169 if (walk_tree_visited(&args->dirs, dir.dev, dir.ino))
170 goto skip_dir;
171 }
172
173 /* Insert into the list of handles. */
174 dir.next = args->dirs.next;
175 dir.prev = &args->dirs;
176 dir.prev->next = &dir;
177 dir.next->prev = &dir;
178 args->num_dir_handles--;
179
180 while ((entry = readdir(dir.stream)) != NULL) {
181 char *path_end;
182
183 if (!strcmp(entry->d_name, ".") ||
184 !strcmp(entry->d_name, ".."))
185 continue;
186 path_end = strchr(args->path, 0);
187 if ((path_end - args->path) + strlen(entry->d_name) + 1 >=
188 FILENAME_MAX) {
189 errno = ENAMETOOLONG;
190 err += args->func(args->path, NULL,
191 flags | WALK_TREE_FAILED,
192 args->arg);
193 continue;
194 }
195 *path_end++ = '/';
196 strcpy(path_end, entry->d_name);
197 args->depth++;
198 err += walk_tree_rec(args);
199 args->depth--;
200 *--path_end = 0;
201 if (!dir.stream) {
202 /* Reopen the directory handle. */
203 dir.stream = opendir(args->path);
204 if (!dir.stream)
205 return err + args->func(args->path,
206 NULL,
207 flags | WALK_TREE_FAILED,
208 args->arg);
209 seekdir(dir.stream, dir.pos);
210
211 args->closed = args->closed->next;
212 args->num_dir_handles--;
213 }
214 }
215
216 /* Remove from the list of handles. */
217 dir.prev->next = dir.next;
218 dir.next->prev = dir.prev;
219 args->num_dir_handles++;
220
221 skip_dir:
222 if (closedir(dir.stream) != 0)
223 err += args->func(args->path, NULL,
224 flags | WALK_TREE_FAILED, args->arg);
225 }
226 return err;
227 }
228
229 int walk_tree(const char *path, int walk_flags, unsigned int num,
230 int (*func)(const char *, const struct stat *, int, void *),
231 void *arg)
232 {
233 struct walk_tree_args args;
234
235 args.num_dir_handles = num;
236 if (args.num_dir_handles < 1) {
237 struct rlimit rlimit;
238
239 args.num_dir_handles = 1;
240 if (getrlimit(RLIMIT_NOFILE, &rlimit) == 0 &&
241 rlimit.rlim_cur >= 2)
242 args.num_dir_handles = rlimit.rlim_cur / 2;
243 }
244 args.dirs.next = &args.dirs;
245 args.dirs.prev = &args.dirs;
246 args.closed = &args.dirs;
247 if (strlen(path) >= FILENAME_MAX) {
248 errno = ENAMETOOLONG;
249 return func(path, NULL, WALK_TREE_FAILED, arg);
250 }
251 strcpy(args.path, path);
252 args.walk_flags = walk_flags;
253 args.func = func;
254 args.arg = arg;
255 args.depth = 0;
256 args.dev = 0;
257
258 return walk_tree_rec(&args);
259 }