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