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