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