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