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