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