1 | /* File tree traversal functions. |
2 | Copyright (C) 1994-2019 Free Software Foundation, Inc. |
3 | This file is part of the GNU C Library. |
4 | |
5 | The GNU C Library is free software; you can redistribute it and/or |
6 | modify it under the terms of the GNU Lesser General Public |
7 | License as published by the Free Software Foundation; either |
8 | version 2.1 of the License, or (at your option) any later version. |
9 | |
10 | The GNU C Library 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 GNU |
13 | Lesser General Public License for more details. |
14 | |
15 | You should have received a copy of the GNU Lesser General Public |
16 | License along with the GNU C Library; if not, see |
17 | <http://www.gnu.org/licenses/>. */ |
18 | |
19 | /*- |
20 | * Copyright (c) 1990, 1993, 1994 |
21 | * The Regents of the University of California. All rights reserved. |
22 | * |
23 | * Redistribution and use in source and binary forms, with or without |
24 | * modification, are permitted provided that the following conditions |
25 | * are met: |
26 | * 1. Redistributions of source code must retain the above copyright |
27 | * notice, this list of conditions and the following disclaimer. |
28 | * 2. Redistributions in binary form must reproduce the above copyright |
29 | * notice, this list of conditions and the following disclaimer in the |
30 | * documentation and/or other materials provided with the distribution. |
31 | * 4. Neither the name of the University nor the names of its contributors |
32 | * may be used to endorse or promote products derived from this software |
33 | * without specific prior written permission. |
34 | * |
35 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
36 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
37 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
38 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
39 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
40 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
41 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
42 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
43 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
44 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
45 | * SUCH DAMAGE. |
46 | */ |
47 | |
48 | #if defined(LIBC_SCCS) && !defined(lint) |
49 | static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94" ; |
50 | #endif /* LIBC_SCCS and not lint */ |
51 | |
52 | #include <sys/param.h> |
53 | #include <include/sys/stat.h> |
54 | #include <fcntl.h> |
55 | #include <dirent.h> |
56 | #include <errno.h> |
57 | #include <fts.h> |
58 | #include <stdlib.h> |
59 | #include <string.h> |
60 | #include <unistd.h> |
61 | |
62 | |
63 | /* Largest alignment size needed, minus one. |
64 | Usually long double is the worst case. */ |
65 | #ifndef ALIGNBYTES |
66 | #define ALIGNBYTES (__alignof__ (long double) - 1) |
67 | #endif |
68 | /* Align P to that size. */ |
69 | #ifndef ALIGN |
70 | #define ALIGN(p) (((unsigned long int) (p) + ALIGNBYTES) & ~ALIGNBYTES) |
71 | #endif |
72 | |
73 | |
74 | /* Support for the LFS API version. */ |
75 | #ifndef FTS_OPEN |
76 | #define FTS_OPEN fts_open |
77 | #define FTS_CLOSE fts_close |
78 | #define FTS_READ fts_read |
79 | #define FTS_SET fts_set |
80 | #define FTS_CHILDREN fts_children |
81 | # define FTSOBJ FTS |
82 | # define FTSENTRY FTSENT |
83 | # define INO_T ino_t |
84 | # define STAT stat |
85 | # define LSTAT lstat |
86 | #endif |
87 | |
88 | static FTSENTRY *fts_alloc (FTSOBJ *, const char *, size_t); |
89 | static FTSENTRY *fts_build (FTSOBJ *, int); |
90 | static void fts_lfree (FTSENTRY *); |
91 | static void fts_load (FTSOBJ *, FTSENTRY *); |
92 | static size_t fts_maxarglen (char * const *); |
93 | static void fts_padjust (FTSOBJ *, FTSENTRY *); |
94 | static int fts_palloc (FTSOBJ *, size_t); |
95 | static FTSENTRY *fts_sort (FTSOBJ *, FTSENTRY *, int); |
96 | static u_short fts_stat (FTSOBJ *, FTSENTRY *, int); |
97 | static int fts_safe_changedir (FTSOBJ *, FTSENTRY *, int, const char *); |
98 | |
99 | #ifndef MAX |
100 | #define MAX(a, b) ({ __typeof__ (a) _a = (a); \ |
101 | __typeof__ (b) _b = (b); \ |
102 | _a > _b ? _a : _b; }) |
103 | #endif |
104 | |
105 | #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2]))) |
106 | |
107 | #define CLR(opt) (sp->fts_options &= ~(opt)) |
108 | #define ISSET(opt) (sp->fts_options & (opt)) |
109 | #define SET(opt) (sp->fts_options |= (opt)) |
110 | |
111 | #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && __fchdir(fd)) |
112 | |
113 | /* fts_build flags */ |
114 | #define BCHILD 1 /* fts_children */ |
115 | #define BNAMES 2 /* fts_children, names only */ |
116 | #define BREAD 3 /* fts_read */ |
117 | |
118 | FTSOBJ * |
119 | FTS_OPEN (char * const *argv, int options, |
120 | int (*compar) (const FTSENTRY **, const FTSENTRY **)) |
121 | { |
122 | FTSOBJ *sp; |
123 | FTSENTRY *p, *root; |
124 | int nitems; |
125 | FTSENTRY *parent = NULL; |
126 | FTSENTRY *tmp; |
127 | |
128 | /* Options check. */ |
129 | if (options & ~FTS_OPTIONMASK) { |
130 | __set_errno (EINVAL); |
131 | return (NULL); |
132 | } |
133 | |
134 | /* Allocate/initialize the stream */ |
135 | if ((sp = malloc((u_int)sizeof(FTSOBJ))) == NULL) |
136 | return (NULL); |
137 | memset(sp, 0, sizeof(FTSOBJ)); |
138 | sp->fts_compar = (int (*) (const void *, const void *)) compar; |
139 | sp->fts_options = options; |
140 | |
141 | /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ |
142 | if (ISSET(FTS_LOGICAL)) |
143 | SET(FTS_NOCHDIR); |
144 | |
145 | /* |
146 | * Start out with 1K of path space, and enough, in any case, |
147 | * to hold the user's paths. |
148 | */ |
149 | #ifndef MAXPATHLEN |
150 | #define MAXPATHLEN 1024 |
151 | #endif |
152 | size_t maxarglen = fts_maxarglen(argv); |
153 | if (fts_palloc(sp, MAX(maxarglen, MAXPATHLEN))) |
154 | goto mem1; |
155 | |
156 | /* Allocate/initialize root's parent. */ |
157 | if (*argv != NULL) { |
158 | if ((parent = fts_alloc(sp, "" , 0)) == NULL) |
159 | goto mem2; |
160 | parent->fts_level = FTS_ROOTPARENTLEVEL; |
161 | } |
162 | |
163 | /* Allocate/initialize root(s). */ |
164 | for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) { |
165 | /* Don't allow zero-length paths. */ |
166 | size_t len = strlen(*argv); |
167 | if (len == 0) { |
168 | __set_errno (ENOENT); |
169 | goto mem3; |
170 | } |
171 | |
172 | p = fts_alloc(sp, *argv, len); |
173 | p->fts_level = FTS_ROOTLEVEL; |
174 | p->fts_parent = parent; |
175 | p->fts_accpath = p->fts_name; |
176 | p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW)); |
177 | |
178 | /* Command-line "." and ".." are real directories. */ |
179 | if (p->fts_info == FTS_DOT) |
180 | p->fts_info = FTS_D; |
181 | |
182 | /* |
183 | * If comparison routine supplied, traverse in sorted |
184 | * order; otherwise traverse in the order specified. |
185 | */ |
186 | if (compar) { |
187 | p->fts_link = root; |
188 | root = p; |
189 | } else { |
190 | p->fts_link = NULL; |
191 | if (root == NULL) |
192 | tmp = root = p; |
193 | else { |
194 | tmp->fts_link = p; |
195 | tmp = p; |
196 | } |
197 | } |
198 | } |
199 | if (compar && nitems > 1) |
200 | root = fts_sort(sp, root, nitems); |
201 | |
202 | /* |
203 | * Allocate a dummy pointer and make fts_read think that we've just |
204 | * finished the node before the root(s); set p->fts_info to FTS_INIT |
205 | * so that everything about the "current" node is ignored. |
206 | */ |
207 | if ((sp->fts_cur = fts_alloc(sp, "" , 0)) == NULL) |
208 | goto mem3; |
209 | sp->fts_cur->fts_link = root; |
210 | sp->fts_cur->fts_info = FTS_INIT; |
211 | |
212 | /* |
213 | * If using chdir(2), grab a file descriptor pointing to dot to ensure |
214 | * that we can get back here; this could be avoided for some paths, |
215 | * but almost certainly not worth the effort. Slashes, symbolic links, |
216 | * and ".." are all fairly nasty problems. Note, if we can't get the |
217 | * descriptor we run anyway, just more slowly. |
218 | */ |
219 | if (!ISSET(FTS_NOCHDIR) |
220 | && (sp->fts_rfd = __open("." , O_RDONLY, 0)) < 0) |
221 | SET(FTS_NOCHDIR); |
222 | |
223 | return (sp); |
224 | |
225 | mem3: fts_lfree(root); |
226 | free(parent); |
227 | mem2: free(sp->fts_path); |
228 | mem1: free(sp); |
229 | return (NULL); |
230 | } |
231 | |
232 | static void |
233 | fts_load (FTSOBJ *sp, FTSENTRY *p) |
234 | { |
235 | int len; |
236 | char *cp; |
237 | |
238 | /* |
239 | * Load the stream structure for the next traversal. Since we don't |
240 | * actually enter the directory until after the preorder visit, set |
241 | * the fts_accpath field specially so the chdir gets done to the right |
242 | * place and the user can access the first node. From fts_open it's |
243 | * known that the path will fit. |
244 | */ |
245 | len = p->fts_pathlen = p->fts_namelen; |
246 | memmove(sp->fts_path, p->fts_name, len + 1); |
247 | if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { |
248 | len = strlen(++cp); |
249 | memmove(p->fts_name, cp, len + 1); |
250 | p->fts_namelen = len; |
251 | } |
252 | p->fts_accpath = p->fts_path = sp->fts_path; |
253 | sp->fts_dev = p->fts_dev; |
254 | } |
255 | |
256 | int |
257 | FTS_CLOSE (FTSOBJ *sp) |
258 | { |
259 | FTSENTRY *freep, *p; |
260 | int saved_errno; |
261 | |
262 | /* |
263 | * This still works if we haven't read anything -- the dummy structure |
264 | * points to the root list, so we step through to the end of the root |
265 | * list which has a valid parent pointer. |
266 | */ |
267 | if (sp->fts_cur) { |
268 | for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { |
269 | freep = p; |
270 | p = p->fts_link != NULL ? p->fts_link : p->fts_parent; |
271 | free(freep); |
272 | } |
273 | free(p); |
274 | } |
275 | |
276 | /* Free up child linked list, sort array, path buffer. */ |
277 | if (sp->fts_child) |
278 | fts_lfree(sp->fts_child); |
279 | free(sp->fts_array); |
280 | free(sp->fts_path); |
281 | |
282 | /* Return to original directory, save errno if necessary. */ |
283 | if (!ISSET(FTS_NOCHDIR)) { |
284 | saved_errno = __fchdir(sp->fts_rfd) ? errno : 0; |
285 | (void)__close(sp->fts_rfd); |
286 | |
287 | /* Set errno and return. */ |
288 | if (saved_errno != 0) { |
289 | /* Free up the stream pointer. */ |
290 | free(sp); |
291 | __set_errno (saved_errno); |
292 | return (-1); |
293 | } |
294 | } |
295 | |
296 | /* Free up the stream pointer. */ |
297 | free(sp); |
298 | return (0); |
299 | } |
300 | |
301 | /* |
302 | * Special case of "/" at the end of the path so that slashes aren't |
303 | * appended which would cause paths to be written as "....//foo". |
304 | */ |
305 | #define NAPPEND(p) \ |
306 | (p->fts_path[p->fts_pathlen - 1] == '/' \ |
307 | ? p->fts_pathlen - 1 : p->fts_pathlen) |
308 | |
309 | FTSENTRY * |
310 | FTS_READ (FTSOBJ *sp) |
311 | { |
312 | FTSENTRY *p, *tmp; |
313 | int instr; |
314 | char *t; |
315 | int saved_errno; |
316 | |
317 | /* If finished or unrecoverable error, return NULL. */ |
318 | if (sp->fts_cur == NULL || ISSET(FTS_STOP)) |
319 | return (NULL); |
320 | |
321 | /* Set current node pointer. */ |
322 | p = sp->fts_cur; |
323 | |
324 | /* Save and zero out user instructions. */ |
325 | instr = p->fts_instr; |
326 | p->fts_instr = FTS_NOINSTR; |
327 | |
328 | /* Any type of file may be re-visited; re-stat and re-turn. */ |
329 | if (instr == FTS_AGAIN) { |
330 | p->fts_info = fts_stat(sp, p, 0); |
331 | return (p); |
332 | } |
333 | |
334 | /* |
335 | * Following a symlink -- SLNONE test allows application to see |
336 | * SLNONE and recover. If indirecting through a symlink, have |
337 | * keep a pointer to current location. If unable to get that |
338 | * pointer, follow fails. |
339 | */ |
340 | if (instr == FTS_FOLLOW && |
341 | (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { |
342 | p->fts_info = fts_stat(sp, p, 1); |
343 | if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { |
344 | if ((p->fts_symfd = __open("." , O_RDONLY, 0)) < 0) { |
345 | p->fts_errno = errno; |
346 | p->fts_info = FTS_ERR; |
347 | } else |
348 | p->fts_flags |= FTS_SYMFOLLOW; |
349 | } |
350 | return (p); |
351 | } |
352 | |
353 | /* Directory in pre-order. */ |
354 | if (p->fts_info == FTS_D) { |
355 | /* If skipped or crossed mount point, do post-order visit. */ |
356 | if (instr == FTS_SKIP || |
357 | (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) { |
358 | if (p->fts_flags & FTS_SYMFOLLOW) |
359 | (void)__close(p->fts_symfd); |
360 | if (sp->fts_child) { |
361 | fts_lfree(sp->fts_child); |
362 | sp->fts_child = NULL; |
363 | } |
364 | p->fts_info = FTS_DP; |
365 | return (p); |
366 | } |
367 | |
368 | /* Rebuild if only read the names and now traversing. */ |
369 | if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) { |
370 | CLR(FTS_NAMEONLY); |
371 | fts_lfree(sp->fts_child); |
372 | sp->fts_child = NULL; |
373 | } |
374 | |
375 | /* |
376 | * Cd to the subdirectory. |
377 | * |
378 | * If have already read and now fail to chdir, whack the list |
379 | * to make the names come out right, and set the parent errno |
380 | * so the application will eventually get an error condition. |
381 | * Set the FTS_DONTCHDIR flag so that when we logically change |
382 | * directories back to the parent we don't do a chdir. |
383 | * |
384 | * If haven't read do so. If the read fails, fts_build sets |
385 | * FTS_STOP or the fts_info field of the node. |
386 | */ |
387 | if (sp->fts_child != NULL) { |
388 | if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) { |
389 | p->fts_errno = errno; |
390 | p->fts_flags |= FTS_DONTCHDIR; |
391 | for (p = sp->fts_child; p != NULL; |
392 | p = p->fts_link) |
393 | p->fts_accpath = |
394 | p->fts_parent->fts_accpath; |
395 | } |
396 | } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) { |
397 | if (ISSET(FTS_STOP)) |
398 | return (NULL); |
399 | return (p); |
400 | } |
401 | p = sp->fts_child; |
402 | sp->fts_child = NULL; |
403 | sp->fts_cur = p; |
404 | goto name; |
405 | } |
406 | |
407 | /* Move to the next node on this level. */ |
408 | next: tmp = p; |
409 | if ((p = p->fts_link) != NULL) { |
410 | sp->fts_cur = p; |
411 | free(tmp); |
412 | |
413 | /* |
414 | * If reached the top, return to the original directory (or |
415 | * the root of the tree), and load the paths for the next root. |
416 | */ |
417 | if (p->fts_level == FTS_ROOTLEVEL) { |
418 | if (FCHDIR(sp, sp->fts_rfd)) { |
419 | SET(FTS_STOP); |
420 | return (NULL); |
421 | } |
422 | fts_load(sp, p); |
423 | return p; |
424 | } |
425 | |
426 | /* |
427 | * User may have called fts_set on the node. If skipped, |
428 | * ignore. If followed, get a file descriptor so we can |
429 | * get back if necessary. |
430 | */ |
431 | if (p->fts_instr == FTS_SKIP) |
432 | goto next; |
433 | if (p->fts_instr == FTS_FOLLOW) { |
434 | p->fts_info = fts_stat(sp, p, 1); |
435 | if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { |
436 | if ((p->fts_symfd = |
437 | __open("." , O_RDONLY, 0)) < 0) { |
438 | p->fts_errno = errno; |
439 | p->fts_info = FTS_ERR; |
440 | } else |
441 | p->fts_flags |= FTS_SYMFOLLOW; |
442 | } |
443 | p->fts_instr = FTS_NOINSTR; |
444 | } |
445 | |
446 | name: t = sp->fts_path + NAPPEND(p->fts_parent); |
447 | *t++ = '/'; |
448 | memmove(t, p->fts_name, p->fts_namelen + 1); |
449 | return p; |
450 | } |
451 | |
452 | /* Move up to the parent node. */ |
453 | p = tmp->fts_parent; |
454 | sp->fts_cur = p; |
455 | free(tmp); |
456 | |
457 | if (p->fts_level == FTS_ROOTPARENTLEVEL) { |
458 | /* |
459 | * Done; free everything up and set errno to 0 so the user |
460 | * can distinguish between error and EOF. |
461 | */ |
462 | free(p); |
463 | __set_errno (0); |
464 | return (sp->fts_cur = NULL); |
465 | } |
466 | |
467 | /* NUL terminate the pathname. */ |
468 | sp->fts_path[p->fts_pathlen] = '\0'; |
469 | |
470 | /* |
471 | * Return to the parent directory. If at a root node or came through |
472 | * a symlink, go back through the file descriptor. Otherwise, cd up |
473 | * one directory. |
474 | */ |
475 | if (p->fts_level == FTS_ROOTLEVEL) { |
476 | if (FCHDIR(sp, sp->fts_rfd)) { |
477 | SET(FTS_STOP); |
478 | return (NULL); |
479 | } |
480 | } else if (p->fts_flags & FTS_SYMFOLLOW) { |
481 | if (FCHDIR(sp, p->fts_symfd)) { |
482 | saved_errno = errno; |
483 | (void)__close(p->fts_symfd); |
484 | __set_errno (saved_errno); |
485 | SET(FTS_STOP); |
486 | return (NULL); |
487 | } |
488 | (void)__close(p->fts_symfd); |
489 | } else if (!(p->fts_flags & FTS_DONTCHDIR) && |
490 | fts_safe_changedir(sp, p->fts_parent, -1, ".." )) { |
491 | SET(FTS_STOP); |
492 | return (NULL); |
493 | } |
494 | p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP; |
495 | return p; |
496 | } |
497 | |
498 | /* |
499 | * Fts_set takes the stream as an argument although it's not used in this |
500 | * implementation; it would be necessary if anyone wanted to add global |
501 | * semantics to fts using fts_set. An error return is allowed for similar |
502 | * reasons. |
503 | */ |
504 | /* ARGSUSED */ |
505 | int |
506 | FTS_SET (FTSOBJ *sp, FTSENTRY *p, int instr) |
507 | { |
508 | if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW && |
509 | instr != FTS_NOINSTR && instr != FTS_SKIP) { |
510 | __set_errno (EINVAL); |
511 | return (1); |
512 | } |
513 | p->fts_instr = instr; |
514 | return (0); |
515 | } |
516 | |
517 | FTSENTRY * |
518 | FTS_CHILDREN(FTSOBJ *sp, int instr) |
519 | { |
520 | FTSENTRY *p; |
521 | int fd; |
522 | |
523 | if (instr != 0 && instr != FTS_NAMEONLY) { |
524 | __set_errno (EINVAL); |
525 | return (NULL); |
526 | } |
527 | |
528 | /* Set current node pointer. */ |
529 | p = sp->fts_cur; |
530 | |
531 | /* |
532 | * Errno set to 0 so user can distinguish empty directory from |
533 | * an error. |
534 | */ |
535 | __set_errno (0); |
536 | |
537 | /* Fatal errors stop here. */ |
538 | if (ISSET(FTS_STOP)) |
539 | return (NULL); |
540 | |
541 | /* Return logical hierarchy of user's arguments. */ |
542 | if (p->fts_info == FTS_INIT) |
543 | return (p->fts_link); |
544 | |
545 | /* |
546 | * If not a directory being visited in pre-order, stop here. Could |
547 | * allow FTS_DNR, assuming the user has fixed the problem, but the |
548 | * same effect is available with FTS_AGAIN. |
549 | */ |
550 | if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */) |
551 | return (NULL); |
552 | |
553 | /* Free up any previous child list. */ |
554 | if (sp->fts_child != NULL) |
555 | fts_lfree(sp->fts_child); |
556 | |
557 | if (instr == FTS_NAMEONLY) { |
558 | SET(FTS_NAMEONLY); |
559 | instr = BNAMES; |
560 | } else |
561 | instr = BCHILD; |
562 | |
563 | /* |
564 | * If using chdir on a relative path and called BEFORE fts_read does |
565 | * its chdir to the root of a traversal, we can lose -- we need to |
566 | * chdir into the subdirectory, and we don't know where the current |
567 | * directory is, so we can't get back so that the upcoming chdir by |
568 | * fts_read will work. |
569 | */ |
570 | if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || |
571 | ISSET(FTS_NOCHDIR)) |
572 | return (sp->fts_child = fts_build(sp, instr)); |
573 | |
574 | if ((fd = __open("." , O_RDONLY, 0)) < 0) |
575 | return (NULL); |
576 | sp->fts_child = fts_build(sp, instr); |
577 | if (__fchdir(fd)) |
578 | return (NULL); |
579 | (void)__close(fd); |
580 | return (sp->fts_child); |
581 | } |
582 | |
583 | static inline int |
584 | dirent_not_directory(const struct dirent *dp) |
585 | { |
586 | #if defined DT_DIR && defined _DIRENT_HAVE_D_TYPE |
587 | return dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN; |
588 | #else |
589 | return 0; |
590 | #endif |
591 | } |
592 | |
593 | /* |
594 | * This is the tricky part -- do not casually change *anything* in here. The |
595 | * idea is to build the linked list of entries that are used by fts_children |
596 | * and fts_read. There are lots of special cases. |
597 | * |
598 | * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is |
599 | * set and it's a physical walk (so that symbolic links can't be directories), |
600 | * we can do things quickly. First, if it's a 4.4BSD file system, the type |
601 | * of the file is in the directory entry. Otherwise, we assume that the number |
602 | * of subdirectories in a node is equal to the number of links to the parent. |
603 | * The former skips all stat calls. The latter skips stat calls in any leaf |
604 | * directories and for any files after the subdirectories in the directory have |
605 | * been found, cutting the stat calls by about 2/3. |
606 | */ |
607 | static FTSENTRY * |
608 | fts_build (FTSOBJ *sp, int type) |
609 | { |
610 | struct dirent *dp; |
611 | FTSENTRY *p, *head; |
612 | int nitems; |
613 | FTSENTRY *cur, *tail; |
614 | DIR *dirp; |
615 | void *oldaddr; |
616 | int cderrno, descend, len, level, nlinks, saved_errno, |
617 | nostat, doadjust; |
618 | size_t maxlen; |
619 | char *cp; |
620 | |
621 | /* Set current node pointer. */ |
622 | cur = sp->fts_cur; |
623 | |
624 | /* |
625 | * Open the directory for reading. If this fails, we're done. |
626 | * If being called from fts_read, set the fts_info field. |
627 | */ |
628 | #if defined FTS_WHITEOUT && 0 |
629 | if (ISSET(FTS_WHITEOUT)) |
630 | oflag = DTF_NODUP|DTF_REWIND; |
631 | else |
632 | oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND; |
633 | #else |
634 | # define __opendir2(path, flag) __opendir(path) |
635 | #endif |
636 | if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) { |
637 | if (type == BREAD) { |
638 | cur->fts_info = FTS_DNR; |
639 | cur->fts_errno = errno; |
640 | } |
641 | return (NULL); |
642 | } |
643 | |
644 | /* |
645 | * Nlinks is the number of possible entries of type directory in the |
646 | * directory if we're cheating on stat calls, 0 if we're not doing |
647 | * any stat calls at all, -1 if we're doing stats on everything. |
648 | */ |
649 | if (type == BNAMES) { |
650 | nlinks = 0; |
651 | /* Be quiet about nostat, GCC. */ |
652 | nostat = 0; |
653 | } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) { |
654 | nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2); |
655 | nostat = 1; |
656 | } else { |
657 | nlinks = -1; |
658 | nostat = 0; |
659 | } |
660 | |
661 | #ifdef notdef |
662 | (void)printf("nlinks == %d (cur: %d)\n" , nlinks, cur->fts_nlink); |
663 | (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n" , |
664 | ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT)); |
665 | #endif |
666 | /* |
667 | * If we're going to need to stat anything or we want to descend |
668 | * and stay in the directory, chdir. If this fails we keep going, |
669 | * but set a flag so we don't chdir after the post-order visit. |
670 | * We won't be able to stat anything, but we can still return the |
671 | * names themselves. Note, that since fts_read won't be able to |
672 | * chdir into the directory, it will have to return different path |
673 | * names than before, i.e. "a/b" instead of "b". Since the node |
674 | * has already been visited in pre-order, have to wait until the |
675 | * post-order visit to return the error. There is a special case |
676 | * here, if there was nothing to stat then it's not an error to |
677 | * not be able to stat. This is all fairly nasty. If a program |
678 | * needed sorted entries or stat information, they had better be |
679 | * checking FTS_NS on the returned nodes. |
680 | */ |
681 | cderrno = 0; |
682 | if (nlinks || type == BREAD) { |
683 | if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) { |
684 | if (nlinks && type == BREAD) |
685 | cur->fts_errno = errno; |
686 | cur->fts_flags |= FTS_DONTCHDIR; |
687 | descend = 0; |
688 | cderrno = errno; |
689 | (void)__closedir(dirp); |
690 | dirp = NULL; |
691 | } else |
692 | descend = 1; |
693 | } else |
694 | descend = 0; |
695 | |
696 | /* |
697 | * Figure out the max file name length that can be stored in the |
698 | * current path -- the inner loop allocates more path as necessary. |
699 | * We really wouldn't have to do the maxlen calculations here, we |
700 | * could do them in fts_read before returning the path, but it's a |
701 | * lot easier here since the length is part of the dirent structure. |
702 | * |
703 | * If not changing directories set a pointer so that can just append |
704 | * each new name into the path. |
705 | */ |
706 | len = NAPPEND(cur); |
707 | if (ISSET(FTS_NOCHDIR)) { |
708 | cp = sp->fts_path + len; |
709 | *cp++ = '/'; |
710 | } else { |
711 | /* GCC, you're too verbose. */ |
712 | cp = NULL; |
713 | } |
714 | len++; |
715 | maxlen = sp->fts_pathlen - len; |
716 | |
717 | level = cur->fts_level + 1; |
718 | |
719 | /* Read the directory, attaching each entry to the `link' pointer. */ |
720 | doadjust = 0; |
721 | for (head = tail = NULL, nitems = 0; dirp && (dp = __readdir(dirp));) { |
722 | if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) |
723 | continue; |
724 | |
725 | if ((p = fts_alloc(sp, dp->d_name, _D_EXACT_NAMLEN (dp))) == NULL) |
726 | goto mem1; |
727 | if (_D_EXACT_NAMLEN (dp) >= maxlen) {/* include space for NUL */ |
728 | oldaddr = sp->fts_path; |
729 | if (fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) { |
730 | /* |
731 | * No more memory for path or structures. Save |
732 | * errno, free up the current structure and the |
733 | * structures already allocated. |
734 | */ |
735 | mem1: saved_errno = errno; |
736 | free(p); |
737 | fts_lfree(head); |
738 | (void)__closedir(dirp); |
739 | cur->fts_info = FTS_ERR; |
740 | SET(FTS_STOP); |
741 | __set_errno (saved_errno); |
742 | return (NULL); |
743 | } |
744 | /* Did realloc() change the pointer? */ |
745 | if (oldaddr != sp->fts_path) { |
746 | doadjust = 1; |
747 | if (ISSET(FTS_NOCHDIR)) |
748 | cp = sp->fts_path + len; |
749 | } |
750 | maxlen = sp->fts_pathlen - len; |
751 | } |
752 | |
753 | if (len + _D_EXACT_NAMLEN (dp) >= USHRT_MAX) { |
754 | /* |
755 | * In an FTSENT, fts_pathlen is a u_short so it is |
756 | * possible to wraparound here. If we do, free up |
757 | * the current structure and the structures already |
758 | * allocated, then error out with ENAMETOOLONG. |
759 | */ |
760 | free(p); |
761 | fts_lfree(head); |
762 | (void)__closedir(dirp); |
763 | cur->fts_info = FTS_ERR; |
764 | SET(FTS_STOP); |
765 | __set_errno (ENAMETOOLONG); |
766 | return (NULL); |
767 | } |
768 | p->fts_level = level; |
769 | p->fts_parent = sp->fts_cur; |
770 | p->fts_pathlen = len + _D_EXACT_NAMLEN (dp); |
771 | |
772 | #if defined FTS_WHITEOUT && 0 |
773 | if (dp->d_type == DT_WHT) |
774 | p->fts_flags |= FTS_ISW; |
775 | #endif |
776 | |
777 | /* Unreachable code. cderrno is only ever set to a nonnull |
778 | value if dirp is closed at the same time. But then we |
779 | cannot enter this loop. */ |
780 | if (0 && cderrno) { |
781 | if (nlinks) { |
782 | p->fts_info = FTS_NS; |
783 | p->fts_errno = cderrno; |
784 | } else |
785 | p->fts_info = FTS_NSOK; |
786 | p->fts_accpath = cur->fts_accpath; |
787 | } else if (nlinks == 0 |
788 | || (nostat && dirent_not_directory(dp))) { |
789 | p->fts_accpath = |
790 | ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; |
791 | p->fts_info = FTS_NSOK; |
792 | } else { |
793 | /* Build a file name for fts_stat to stat. */ |
794 | if (ISSET(FTS_NOCHDIR)) { |
795 | p->fts_accpath = p->fts_path; |
796 | memmove(cp, p->fts_name, p->fts_namelen + 1); |
797 | } else |
798 | p->fts_accpath = p->fts_name; |
799 | /* Stat it. */ |
800 | p->fts_info = fts_stat(sp, p, 0); |
801 | |
802 | /* Decrement link count if applicable. */ |
803 | if (nlinks > 0 && (p->fts_info == FTS_D || |
804 | p->fts_info == FTS_DC || p->fts_info == FTS_DOT)) |
805 | --nlinks; |
806 | } |
807 | |
808 | /* We walk in directory order so "ls -f" doesn't get upset. */ |
809 | p->fts_link = NULL; |
810 | if (head == NULL) |
811 | head = tail = p; |
812 | else { |
813 | tail->fts_link = p; |
814 | tail = p; |
815 | } |
816 | ++nitems; |
817 | } |
818 | if (dirp) |
819 | (void)__closedir(dirp); |
820 | |
821 | /* |
822 | * If realloc() changed the address of the path, adjust the |
823 | * addresses for the rest of the tree and the dir list. |
824 | */ |
825 | if (doadjust) |
826 | fts_padjust(sp, head); |
827 | |
828 | /* |
829 | * If not changing directories, reset the path back to original |
830 | * state. |
831 | */ |
832 | if (ISSET(FTS_NOCHDIR)) { |
833 | if (len == sp->fts_pathlen || nitems == 0) |
834 | --cp; |
835 | *cp = '\0'; |
836 | } |
837 | |
838 | /* |
839 | * If descended after called from fts_children or after called from |
840 | * fts_read and nothing found, get back. At the root level we use |
841 | * the saved fd; if one of fts_open()'s arguments is a relative path |
842 | * to an empty directory, we wind up here with no other way back. If |
843 | * can't get back, we're done. |
844 | */ |
845 | if (descend && (type == BCHILD || !nitems) && |
846 | (cur->fts_level == FTS_ROOTLEVEL ? |
847 | FCHDIR(sp, sp->fts_rfd) : |
848 | fts_safe_changedir(sp, cur->fts_parent, -1, ".." ))) { |
849 | cur->fts_info = FTS_ERR; |
850 | SET(FTS_STOP); |
851 | fts_lfree(head); |
852 | return (NULL); |
853 | } |
854 | |
855 | /* If didn't find anything, return NULL. */ |
856 | if (!nitems) { |
857 | if (type == BREAD) |
858 | cur->fts_info = FTS_DP; |
859 | fts_lfree(head); |
860 | return (NULL); |
861 | } |
862 | |
863 | /* Sort the entries. */ |
864 | if (sp->fts_compar && nitems > 1) |
865 | head = fts_sort(sp, head, nitems); |
866 | return (head); |
867 | } |
868 | |
869 | static u_short |
870 | fts_stat (FTSOBJ *sp, FTSENTRY *p, int follow) |
871 | { |
872 | FTSENTRY *t; |
873 | dev_t dev; |
874 | INO_T ino; |
875 | struct STAT *sbp, sb; |
876 | int saved_errno; |
877 | |
878 | /* If user needs stat info, stat buffer already allocated. */ |
879 | sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp; |
880 | |
881 | #if defined FTS_WHITEOUT && 0 |
882 | /* check for whiteout */ |
883 | if (p->fts_flags & FTS_ISW) { |
884 | if (sbp != &sb) { |
885 | memset(sbp, '\0', sizeof (*sbp)); |
886 | sbp->st_mode = S_IFWHT; |
887 | } |
888 | return (FTS_W); |
889 | } |
890 | #endif |
891 | |
892 | /* |
893 | * If doing a logical walk, or application requested FTS_FOLLOW, do |
894 | * a stat(2). If that fails, check for a non-existent symlink. If |
895 | * fail, set the errno from the stat call. |
896 | */ |
897 | if (ISSET(FTS_LOGICAL) || follow) { |
898 | if (STAT(p->fts_accpath, sbp)) { |
899 | saved_errno = errno; |
900 | if (!LSTAT(p->fts_accpath, sbp)) { |
901 | __set_errno (0); |
902 | return (FTS_SLNONE); |
903 | } |
904 | p->fts_errno = saved_errno; |
905 | goto err; |
906 | } |
907 | } else if (LSTAT(p->fts_accpath, sbp)) { |
908 | p->fts_errno = errno; |
909 | err: memset(sbp, 0, sizeof(struct STAT)); |
910 | return (FTS_NS); |
911 | } |
912 | |
913 | if (S_ISDIR(sbp->st_mode)) { |
914 | /* |
915 | * Set the device/inode. Used to find cycles and check for |
916 | * crossing mount points. Also remember the link count, used |
917 | * in fts_build to limit the number of stat calls. It is |
918 | * understood that these fields are only referenced if fts_info |
919 | * is set to FTS_D. |
920 | */ |
921 | dev = p->fts_dev = sbp->st_dev; |
922 | ino = p->fts_ino = sbp->st_ino; |
923 | p->fts_nlink = sbp->st_nlink; |
924 | |
925 | if (ISDOT(p->fts_name)) |
926 | return (FTS_DOT); |
927 | |
928 | /* |
929 | * Cycle detection is done by brute force when the directory |
930 | * is first encountered. If the tree gets deep enough or the |
931 | * number of symbolic links to directories is high enough, |
932 | * something faster might be worthwhile. |
933 | */ |
934 | for (t = p->fts_parent; |
935 | t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) |
936 | if (ino == t->fts_ino && dev == t->fts_dev) { |
937 | p->fts_cycle = t; |
938 | return (FTS_DC); |
939 | } |
940 | return (FTS_D); |
941 | } |
942 | if (S_ISLNK(sbp->st_mode)) |
943 | return (FTS_SL); |
944 | if (S_ISREG(sbp->st_mode)) |
945 | return (FTS_F); |
946 | return (FTS_DEFAULT); |
947 | } |
948 | |
949 | static FTSENTRY * |
950 | fts_sort (FTSOBJ *sp, FTSENTRY *head, int nitems) |
951 | { |
952 | FTSENTRY **ap, *p; |
953 | |
954 | /* |
955 | * Construct an array of pointers to the structures and call qsort(3). |
956 | * Reassemble the array in the order returned by qsort. If unable to |
957 | * sort for memory reasons, return the directory entries in their |
958 | * current order. Allocate enough space for the current needs plus |
959 | * 40 so don't realloc one entry at a time. |
960 | */ |
961 | if (nitems > sp->fts_nitems) { |
962 | FTSENTRY **a; |
963 | |
964 | sp->fts_nitems = nitems + 40; |
965 | if ((a = realloc(sp->fts_array, |
966 | (size_t)(sp->fts_nitems * sizeof(FTSENTRY *)))) == NULL) { |
967 | free(sp->fts_array); |
968 | sp->fts_array = NULL; |
969 | sp->fts_nitems = 0; |
970 | return (head); |
971 | } |
972 | sp->fts_array = a; |
973 | } |
974 | for (ap = sp->fts_array, p = head; p; p = p->fts_link) |
975 | *ap++ = p; |
976 | qsort((void *)sp->fts_array, nitems, sizeof(FTSENTRY *), sp->fts_compar); |
977 | for (head = *(ap = sp->fts_array); --nitems; ++ap) |
978 | ap[0]->fts_link = ap[1]; |
979 | ap[0]->fts_link = NULL; |
980 | return (head); |
981 | } |
982 | |
983 | static FTSENTRY * |
984 | fts_alloc (FTSOBJ *sp, const char *name, size_t namelen) |
985 | { |
986 | FTSENTRY *p; |
987 | size_t len; |
988 | |
989 | /* |
990 | * The file name is a variable length array and no stat structure is |
991 | * necessary if the user has set the nostat bit. Allocate the FTSENT |
992 | * structure, the file name and the stat structure in one chunk, but |
993 | * be careful that the stat structure is reasonably aligned. Since the |
994 | * fts_name field is declared to be of size 1, the fts_name pointer is |
995 | * namelen + 2 before the first possible address of the stat structure. |
996 | */ |
997 | len = sizeof(FTSENTRY) + namelen; |
998 | if (!ISSET(FTS_NOSTAT)) |
999 | len += sizeof(struct STAT) + ALIGNBYTES; |
1000 | if ((p = malloc(len)) == NULL) |
1001 | return (NULL); |
1002 | |
1003 | /* Copy the name and guarantee NUL termination. */ |
1004 | memmove(p->fts_name, name, namelen); |
1005 | p->fts_name[namelen] = '\0'; |
1006 | |
1007 | if (!ISSET(FTS_NOSTAT)) |
1008 | p->fts_statp = (struct STAT *)ALIGN(p->fts_name + namelen + 2); |
1009 | p->fts_namelen = namelen; |
1010 | p->fts_path = sp->fts_path; |
1011 | p->fts_errno = 0; |
1012 | p->fts_flags = 0; |
1013 | p->fts_instr = FTS_NOINSTR; |
1014 | p->fts_number = 0; |
1015 | p->fts_pointer = NULL; |
1016 | return (p); |
1017 | } |
1018 | |
1019 | static void |
1020 | fts_lfree (FTSENTRY *head) |
1021 | { |
1022 | FTSENTRY *p; |
1023 | |
1024 | /* Free a linked list of structures. */ |
1025 | while ((p = head)) { |
1026 | head = head->fts_link; |
1027 | free(p); |
1028 | } |
1029 | } |
1030 | |
1031 | /* |
1032 | * Allow essentially unlimited paths; find, rm, ls should all work on any tree. |
1033 | * Most systems will allow creation of paths much longer than MAXPATHLEN, even |
1034 | * though the kernel won't resolve them. Add the size (not just what's needed) |
1035 | * plus 256 bytes so don't realloc the path 2 bytes at a time. |
1036 | */ |
1037 | static int |
1038 | fts_palloc (FTSOBJ *sp, size_t more) |
1039 | { |
1040 | char *p; |
1041 | |
1042 | sp->fts_pathlen += more + 256; |
1043 | /* |
1044 | * Check for possible wraparound. In an FTS, fts_pathlen is |
1045 | * a signed int but in an FTSENT it is an unsigned short. |
1046 | * We limit fts_pathlen to USHRT_MAX to be safe in both cases. |
1047 | */ |
1048 | if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) { |
1049 | free(sp->fts_path); |
1050 | sp->fts_path = NULL; |
1051 | __set_errno (ENAMETOOLONG); |
1052 | return (1); |
1053 | } |
1054 | p = realloc(sp->fts_path, sp->fts_pathlen); |
1055 | if (p == NULL) { |
1056 | free(sp->fts_path); |
1057 | sp->fts_path = NULL; |
1058 | return 1; |
1059 | } |
1060 | sp->fts_path = p; |
1061 | return 0; |
1062 | } |
1063 | |
1064 | /* |
1065 | * When the path is realloc'd, have to fix all of the pointers in structures |
1066 | * already returned. |
1067 | */ |
1068 | static void |
1069 | fts_padjust (FTSOBJ *sp, FTSENTRY *head) |
1070 | { |
1071 | FTSENTRY *p; |
1072 | char *addr = sp->fts_path; |
1073 | |
1074 | #define ADJUST(p) do { \ |
1075 | if ((p)->fts_accpath != (p)->fts_name) { \ |
1076 | (p)->fts_accpath = \ |
1077 | (char *)addr + ((p)->fts_accpath - (p)->fts_path); \ |
1078 | } \ |
1079 | (p)->fts_path = addr; \ |
1080 | } while (0) |
1081 | /* Adjust the current set of children. */ |
1082 | for (p = sp->fts_child; p; p = p->fts_link) |
1083 | ADJUST(p); |
1084 | |
1085 | /* Adjust the rest of the tree, including the current level. */ |
1086 | for (p = head; p->fts_level >= FTS_ROOTLEVEL;) { |
1087 | ADJUST(p); |
1088 | p = p->fts_link ? p->fts_link : p->fts_parent; |
1089 | } |
1090 | } |
1091 | |
1092 | static size_t |
1093 | fts_maxarglen (char * const *argv) |
1094 | { |
1095 | size_t len, max; |
1096 | |
1097 | for (max = 0; *argv; ++argv) |
1098 | if ((len = strlen(*argv)) > max) |
1099 | max = len; |
1100 | return (max + 1); |
1101 | } |
1102 | |
1103 | /* |
1104 | * Change to dir specified by fd or p->fts_accpath without getting |
1105 | * tricked by someone changing the world out from underneath us. |
1106 | * Assumes p->fts_dev and p->fts_ino are filled in. |
1107 | */ |
1108 | static int |
1109 | fts_safe_changedir (FTSOBJ *sp, FTSENTRY *p, int fd, const char *path) |
1110 | { |
1111 | int ret, oerrno, newfd; |
1112 | struct stat64 sb; |
1113 | |
1114 | newfd = fd; |
1115 | if (ISSET(FTS_NOCHDIR)) |
1116 | return (0); |
1117 | if (fd < 0 && (newfd = __open(path, O_RDONLY, 0)) < 0) |
1118 | return (-1); |
1119 | if (__fxstat64(_STAT_VER, newfd, &sb)) { |
1120 | ret = -1; |
1121 | goto bail; |
1122 | } |
1123 | if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) { |
1124 | __set_errno (ENOENT); /* disinformation */ |
1125 | ret = -1; |
1126 | goto bail; |
1127 | } |
1128 | ret = __fchdir(newfd); |
1129 | bail: |
1130 | oerrno = errno; |
1131 | if (fd < 0) |
1132 | (void)__close(newfd); |
1133 | __set_errno (oerrno); |
1134 | return (ret); |
1135 | } |
1136 | |