Annotation of mandoc/compat_fts.c, Revision 1.10
1.1 schwarze 1: #include "config.h"
2:
1.3 schwarze 3: #if HAVE_FTS
1.1 schwarze 4:
5: int dummy;
6:
7: #else
8:
1.10 ! schwarze 9: /* $Id: compat_fts.c,v 1.9 2015/03/18 19:29:48 schwarze Exp $ */
1.7 schwarze 10: /* $OpenBSD: fts.c,v 1.50 2015/01/16 16:48:51 deraadt Exp $ */
1.1 schwarze 11:
12: /*-
13: * Copyright (c) 1990, 1993, 1994
14: * The Regents of the University of California. All rights reserved.
15: *
16: * Redistribution and use in source and binary forms, with or without
17: * modification, are permitted provided that the following conditions
18: * are met:
19: * 1. Redistributions of source code must retain the above copyright
20: * notice, this list of conditions and the following disclaimer.
21: * 2. Redistributions in binary form must reproduce the above copyright
22: * notice, this list of conditions and the following disclaimer in the
23: * documentation and/or other materials provided with the distribution.
24: * 3. Neither the name of the University nor the names of its contributors
25: * may be used to endorse or promote products derived from this software
26: * without specific prior written permission.
27: *
28: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
29: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
32: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38: * SUCH DAMAGE.
39: */
40:
41: #include <sys/stat.h>
42: #include <sys/types.h>
43:
44: #include <dirent.h>
45: #include <errno.h>
46: #include <fcntl.h>
47: #include <limits.h>
48: #include <stdlib.h>
49: #include <string.h>
50: #include <unistd.h>
51: #include "compat_fts.h"
52:
1.7 schwarze 53: #define MAXIMUM(a, b) (((a) > (b)) ? (a) : (b))
54:
1.1 schwarze 55: static FTSENT *fts_alloc(FTS *, const char *, size_t);
56: static FTSENT *fts_build(FTS *);
57: static void fts_lfree(FTSENT *);
58: static void fts_load(FTS *, FTSENT *);
59: static size_t fts_maxarglen(char * const *);
60: static void fts_padjust(FTS *, FTSENT *);
61: static int fts_palloc(FTS *, size_t);
62: static unsigned short fts_stat(FTS *, FTSENT *);
63:
64: #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
1.6 schwarze 65: #ifndef O_DIRECTORY
66: #define O_DIRECTORY 0
1.8 schwarze 67: #endif
68: #ifndef O_CLOEXEC
69: #define O_CLOEXEC 0
1.10 ! schwarze 70: #endif
! 71: #ifndef PATH_MAX
! 72: #define PATH_MAX 4096
1.6 schwarze 73: #endif
1.1 schwarze 74:
75: #define CLR(opt) (sp->fts_options &= ~(opt))
76: #define ISSET(opt) (sp->fts_options & (opt))
77: #define SET(opt) (sp->fts_options |= (opt))
78:
79: FTS *
80: fts_open(char * const *argv, int options, void *dummy)
81: {
82: FTS *sp;
83: FTSENT *p, *root;
84: int nitems;
85: FTSENT *parent, *tmp;
86: size_t len;
87:
88: /* Options check. */
89: if (options & ~FTS_OPTIONMASK) {
90: errno = EINVAL;
91: return (NULL);
92: }
93:
94: /* Allocate/initialize the stream */
95: if ((sp = calloc(1, sizeof(FTS))) == NULL)
96: return (NULL);
97: sp->fts_options = options;
98:
99: /*
100: * Start out with 1K of path space, and enough, in any case,
101: * to hold the user's paths.
102: */
1.7 schwarze 103: if (fts_palloc(sp, MAXIMUM(fts_maxarglen(argv), PATH_MAX)))
1.1 schwarze 104: goto mem1;
105:
106: /* Allocate/initialize root's parent. */
107: if ((parent = fts_alloc(sp, "", 0)) == NULL)
108: goto mem2;
109: parent->fts_level = FTS_ROOTPARENTLEVEL;
110:
111: /* Allocate/initialize root(s). */
112: for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
113: /* Don't allow zero-length paths. */
114: if ((len = strlen(*argv)) == 0) {
115: errno = ENOENT;
116: goto mem3;
117: }
118:
119: if ((p = fts_alloc(sp, *argv, len)) == NULL)
120: goto mem3;
121: p->fts_level = FTS_ROOTLEVEL;
122: p->fts_parent = parent;
123: p->fts_accpath = p->fts_name;
124: p->fts_info = fts_stat(sp, p);
125:
126: /* Command-line "." and ".." are real directories. */
127: if (p->fts_info == FTS_DOT)
128: p->fts_info = FTS_D;
129:
130: p->fts_link = NULL;
131: if (root == NULL)
132: tmp = root = p;
133: else {
134: tmp->fts_link = p;
135: tmp = p;
136: }
137: }
138:
139: /*
140: * Allocate a dummy pointer and make fts_read think that we've just
141: * finished the node before the root(s); set p->fts_info to FTS_INIT
142: * so that everything about the "current" node is ignored.
143: */
144: if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
145: goto mem3;
146: sp->fts_cur->fts_link = root;
147: sp->fts_cur->fts_info = FTS_INIT;
148:
149: if (nitems == 0)
150: free(parent);
151:
152: return (sp);
153:
154: mem3: fts_lfree(root);
155: free(parent);
156: mem2: free(sp->fts_path);
157: mem1: free(sp);
158: return (NULL);
159: }
160:
161: static void
162: fts_load(FTS *sp, FTSENT *p)
163: {
164: size_t len;
165: char *cp;
166:
167: /*
168: * Load the stream structure for the next traversal. Since we don't
169: * actually enter the directory until after the preorder visit, set
170: * the fts_accpath field specially so the chdir gets done to the right
171: * place and the user can access the first node. From fts_open it's
172: * known that the path will fit.
173: */
174: len = p->fts_pathlen = p->fts_namelen;
175: memmove(sp->fts_path, p->fts_name, len + 1);
176: if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
177: len = strlen(++cp);
178: memmove(p->fts_name, cp, len + 1);
179: p->fts_namelen = len;
180: }
181: p->fts_accpath = p->fts_path = sp->fts_path;
182: sp->fts_dev = p->fts_dev;
183: }
184:
185: int
186: fts_close(FTS *sp)
187: {
188: FTSENT *freep, *p;
189:
190: /*
191: * This still works if we haven't read anything -- the dummy structure
192: * points to the root list, so we step through to the end of the root
193: * list which has a valid parent pointer.
194: */
195: if (sp->fts_cur) {
196: for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
197: freep = p;
198: p = p->fts_link ? p->fts_link : p->fts_parent;
199: free(freep);
200: }
201: free(p);
202: }
203:
204: /* Free up child linked list, sort array, path buffer, stream ptr.*/
205: if (sp->fts_child)
206: fts_lfree(sp->fts_child);
207: free(sp->fts_path);
208: free(sp);
209:
1.9 schwarze 210: return (0);
1.1 schwarze 211: }
212:
213: /*
214: * Special case of "/" at the end of the path so that slashes aren't
215: * appended which would cause paths to be written as "....//foo".
216: */
217: #define NAPPEND(p) \
218: (p->fts_path[p->fts_pathlen - 1] == '/' \
219: ? p->fts_pathlen - 1 : p->fts_pathlen)
220:
221: FTSENT *
222: fts_read(FTS *sp)
223: {
224: FTSENT *p, *tmp;
225: int instr;
226: char *t;
227:
228: /* If finished or unrecoverable error, return NULL. */
229: if (sp->fts_cur == NULL || ISSET(FTS_STOP))
230: return (NULL);
231:
232: /* Set current node pointer. */
233: p = sp->fts_cur;
234:
235: /* Save and zero out user instructions. */
236: instr = p->fts_instr;
237: p->fts_instr = FTS_NOINSTR;
238:
239: /* Directory in pre-order. */
240: if (p->fts_info == FTS_D) {
241: /* If skipped or crossed mount point, do post-order visit. */
242: if (instr == FTS_SKIP ||
243: (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
244: if (sp->fts_child) {
245: fts_lfree(sp->fts_child);
246: sp->fts_child = NULL;
247: }
248: p->fts_info = FTS_DP;
249: return (p);
250: }
251:
252: /*
253: * If haven't read do so. If the read fails, fts_build sets
254: * FTS_STOP or the fts_info field of the node.
255: */
256: if (sp->fts_child) {
1.9 schwarze 257: /* nothing */
1.1 schwarze 258: } else if ((sp->fts_child = fts_build(sp)) == NULL) {
259: if (ISSET(FTS_STOP))
260: return (NULL);
261: return (p);
262: }
263: p = sp->fts_child;
264: sp->fts_child = NULL;
265: goto name;
266: }
267:
268: /* Move to the next node on this level. */
269: next: tmp = p;
270: if ((p = p->fts_link)) {
271: free(tmp);
272:
273: /*
274: * If reached the top, return to the original directory (or
275: * the root of the tree), and load the paths for the next root.
276: */
277: if (p->fts_level == FTS_ROOTLEVEL) {
278: fts_load(sp, p);
279: return (sp->fts_cur = p);
280: }
281:
282: /*
283: * User may have called fts_set on the node. If skipped,
284: * ignore. If followed, get a file descriptor so we can
285: * get back if necessary.
286: */
287: if (p->fts_instr == FTS_SKIP)
288: goto next;
289:
290: name: t = sp->fts_path + NAPPEND(p->fts_parent);
291: *t++ = '/';
292: memmove(t, p->fts_name, p->fts_namelen + 1);
293: return (sp->fts_cur = p);
294: }
295:
296: /* Move up to the parent node. */
297: p = tmp->fts_parent;
298: free(tmp);
299:
300: if (p->fts_level == FTS_ROOTPARENTLEVEL) {
301: /*
302: * Done; free everything up and set errno to 0 so the user
303: * can distinguish between error and EOF.
304: */
305: free(p);
306: errno = 0;
307: return (sp->fts_cur = NULL);
308: }
309:
310: /* NUL terminate the pathname. */
311: sp->fts_path[p->fts_pathlen] = '\0';
312:
313: p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
314: return (sp->fts_cur = p);
315: }
316:
317: /*
318: * Fts_set takes the stream as an argument although it's not used in this
319: * implementation; it would be necessary if anyone wanted to add global
320: * semantics to fts using fts_set. An error return is allowed for similar
321: * reasons.
322: */
323: /* ARGSUSED */
324: int
325: fts_set(FTS *sp, FTSENT *p, int instr)
326: {
327: if (instr && instr != FTS_NOINSTR && instr != FTS_SKIP) {
328: errno = EINVAL;
329: return (1);
330: }
331: p->fts_instr = instr;
332: return (0);
333: }
334:
335: /*
336: * This is the tricky part -- do not casually change *anything* in here. The
337: * idea is to build the linked list of entries that are used by fts_children
338: * and fts_read. There are lots of special cases.
339: *
340: * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
341: * set and it's a physical walk (so that symbolic links can't be directories),
342: * we can do things quickly. First, if it's a 4.4BSD file system, the type
343: * of the file is in the directory entry. Otherwise, we assume that the number
344: * of subdirectories in a node is equal to the number of links to the parent.
345: * The former skips all stat calls. The latter skips stat calls in any leaf
346: * directories and for any files after the subdirectories in the directory have
347: * been found, cutting the stat calls by about 2/3.
348: */
349: static FTSENT *
350: fts_build(FTS *sp)
351: {
352: struct dirent *dp;
353: FTSENT *p, *head;
354: FTSENT *cur, *tail;
355: DIR *dirp;
356: void *oldaddr;
1.2 schwarze 357: size_t dlen, len, maxlen;
1.9 schwarze 358: int nitems, level, doadjust;
1.1 schwarze 359: int saved_errno;
360: char *cp;
361:
362: /* Set current node pointer. */
363: cur = sp->fts_cur;
364:
365: /*
366: * Open the directory for reading. If this fails, we're done.
367: * If being called from fts_read, set the fts_info field.
368: */
369: if ((dirp = opendir(cur->fts_accpath)) == NULL) {
370: cur->fts_info = FTS_DNR;
371: cur->fts_errno = errno;
372: return (NULL);
373: }
374:
375: /*
376: * Figure out the max file name length that can be stored in the
377: * current path -- the inner loop allocates more path as necessary.
378: * We really wouldn't have to do the maxlen calculations here, we
379: * could do them in fts_read before returning the path, but it's a
380: * lot easier here since the length is part of the dirent structure.
381: *
382: * If not changing directories set a pointer so that can just append
383: * each new name into the path.
384: */
385: len = NAPPEND(cur);
1.9 schwarze 386: cp = sp->fts_path + len;
387: *cp++ = '/';
1.1 schwarze 388: len++;
389: maxlen = sp->fts_pathlen - len;
390:
391: /*
392: * fts_level is signed so we must prevent it from wrapping
393: * around to FTS_ROOTLEVEL and FTS_ROOTPARENTLEVEL.
394: */
395: level = cur->fts_level;
396: if (level < FTS_MAXLEVEL)
397: level++;
398:
399: /* Read the directory, attaching each entry to the `link' pointer. */
400: doadjust = 0;
401: for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
402: if (ISDOT(dp->d_name))
403: continue;
404:
1.4 schwarze 405: #if HAVE_DIRENT_NAMLEN
1.2 schwarze 406: dlen = dp->d_namlen;
407: #else
408: dlen = strlen(dp->d_name);
409: #endif
410:
411: if (!(p = fts_alloc(sp, dp->d_name, dlen)))
1.1 schwarze 412: goto mem1;
1.2 schwarze 413: if (dlen >= maxlen) { /* include space for NUL */
1.1 schwarze 414: oldaddr = sp->fts_path;
1.2 schwarze 415: if (fts_palloc(sp, dlen + len + 1)) {
1.1 schwarze 416: /*
417: * No more memory for path or structures. Save
418: * errno, free up the current structure and the
419: * structures already allocated.
420: */
421: mem1: saved_errno = errno;
422: if (p)
423: free(p);
424: fts_lfree(head);
425: (void)closedir(dirp);
426: cur->fts_info = FTS_ERR;
427: SET(FTS_STOP);
428: errno = saved_errno;
429: return (NULL);
430: }
431: /* Did realloc() change the pointer? */
432: if (oldaddr != sp->fts_path) {
433: doadjust = 1;
1.9 schwarze 434: cp = sp->fts_path + len;
1.1 schwarze 435: }
436: maxlen = sp->fts_pathlen - len;
437: }
438:
439: p->fts_level = level;
440: p->fts_parent = sp->fts_cur;
1.2 schwarze 441: p->fts_pathlen = len + dlen;
1.1 schwarze 442: if (p->fts_pathlen < len) {
443: /*
444: * If we wrap, free up the current structure and
445: * the structures already allocated, then error
446: * out with ENAMETOOLONG.
447: */
448: free(p);
449: fts_lfree(head);
450: (void)closedir(dirp);
451: cur->fts_info = FTS_ERR;
452: SET(FTS_STOP);
453: errno = ENAMETOOLONG;
454: return (NULL);
455: }
456:
1.9 schwarze 457: /* Build a file name for fts_stat to stat. */
458: p->fts_accpath = p->fts_path;
459: memmove(cp, p->fts_name, p->fts_namelen + 1);
460: /* Stat it. */
461: p->fts_info = fts_stat(sp, p);
1.1 schwarze 462:
463: /* We walk in directory order so "ls -f" doesn't get upset. */
464: p->fts_link = NULL;
465: if (head == NULL)
466: head = tail = p;
467: else {
468: tail->fts_link = p;
469: tail = p;
470: }
471: ++nitems;
472: }
473: if (dirp)
474: (void)closedir(dirp);
475:
476: /*
477: * If realloc() changed the address of the path, adjust the
478: * addresses for the rest of the tree and the dir list.
479: */
480: if (doadjust)
481: fts_padjust(sp, head);
482:
483: /*
484: * If not changing directories, reset the path back to original
485: * state.
486: */
1.9 schwarze 487: if (len == sp->fts_pathlen || nitems == 0)
488: --cp;
489: *cp = '\0';
1.1 schwarze 490:
491: /* If didn't find anything, return NULL. */
492: if (!nitems) {
493: cur->fts_info = FTS_DP;
494: return (NULL);
495: }
496: return (head);
497: }
498:
499: static unsigned short
500: fts_stat(FTS *sp, FTSENT *p)
501: {
502: FTSENT *t;
503: dev_t dev;
504: ino_t ino;
505: struct stat *sbp;
506:
507: /* If user needs stat info, stat buffer already allocated. */
508: sbp = p->fts_statp;
509:
510: if (lstat(p->fts_accpath, sbp)) {
511: p->fts_errno = errno;
512: memset(sbp, 0, sizeof(struct stat));
513: return (FTS_NS);
514: }
515:
516: if (S_ISDIR(sbp->st_mode)) {
517: /*
518: * Set the device/inode. Used to find cycles and check for
519: * crossing mount points. Also remember the link count, used
520: * in fts_build to limit the number of stat calls. It is
521: * understood that these fields are only referenced if fts_info
522: * is set to FTS_D.
523: */
524: dev = p->fts_dev = sbp->st_dev;
525: ino = p->fts_ino = sbp->st_ino;
526: p->fts_nlink = sbp->st_nlink;
527:
528: if (ISDOT(p->fts_name))
529: return (FTS_DOT);
530:
531: /*
532: * Cycle detection is done by brute force when the directory
533: * is first encountered. If the tree gets deep enough or the
534: * number of symbolic links to directories is high enough,
535: * something faster might be worthwhile.
536: */
537: for (t = p->fts_parent;
538: t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
539: if (ino == t->fts_ino && dev == t->fts_dev) {
540: p->fts_cycle = t;
541: return (FTS_DC);
542: }
543: return (FTS_D);
544: }
545: if (S_ISLNK(sbp->st_mode))
546: return (FTS_SL);
547: if (S_ISREG(sbp->st_mode))
548: return (FTS_F);
549: return (FTS_DEFAULT);
550: }
551:
552: static FTSENT *
553: fts_alloc(FTS *sp, const char *name, size_t namelen)
554: {
555: FTSENT *p;
556: size_t len;
557:
558: len = sizeof(FTSENT) + namelen;
559: if ((p = calloc(1, len)) == NULL)
560: return (NULL);
561:
562: p->fts_path = sp->fts_path;
563: p->fts_namelen = namelen;
564: p->fts_instr = FTS_NOINSTR;
1.2 schwarze 565: p->fts_statp = malloc(sizeof(struct stat));
566: if (p->fts_statp == NULL) {
567: free(p);
568: return (NULL);
569: }
1.1 schwarze 570: memcpy(p->fts_name, name, namelen);
571:
572: return (p);
573: }
574:
575: static void
576: fts_lfree(FTSENT *head)
577: {
578: FTSENT *p;
579:
580: /* Free a linked list of structures. */
581: while ((p = head)) {
582: head = head->fts_link;
583: free(p);
584: }
585: }
586:
587: /*
588: * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
589: * Most systems will allow creation of paths much longer than PATH_MAX, even
590: * though the kernel won't resolve them. Add the size (not just what's needed)
591: * plus 256 bytes so don't realloc the path 2 bytes at a time.
592: */
593: static int
594: fts_palloc(FTS *sp, size_t more)
595: {
596: char *p;
597:
598: /*
599: * Check for possible wraparound.
600: */
601: more += 256;
602: if (sp->fts_pathlen + more < sp->fts_pathlen) {
603: if (sp->fts_path)
604: free(sp->fts_path);
605: sp->fts_path = NULL;
606: errno = ENAMETOOLONG;
607: return (1);
608: }
609: sp->fts_pathlen += more;
610: p = realloc(sp->fts_path, sp->fts_pathlen);
611: if (p == NULL) {
612: if (sp->fts_path)
613: free(sp->fts_path);
614: sp->fts_path = NULL;
615: return (1);
616: }
617: sp->fts_path = p;
618: return (0);
619: }
620:
621: /*
622: * When the path is realloc'd, have to fix all of the pointers in structures
623: * already returned.
624: */
625: static void
626: fts_padjust(FTS *sp, FTSENT *head)
627: {
628: FTSENT *p;
629: char *addr = sp->fts_path;
630:
631: #define ADJUST(p) { \
632: if ((p)->fts_accpath != (p)->fts_name) { \
633: (p)->fts_accpath = \
634: (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
635: } \
636: (p)->fts_path = addr; \
637: }
638: /* Adjust the current set of children. */
639: for (p = sp->fts_child; p; p = p->fts_link)
640: ADJUST(p);
641:
642: /* Adjust the rest of the tree, including the current level. */
643: for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
644: ADJUST(p);
645: p = p->fts_link ? p->fts_link : p->fts_parent;
646: }
647: }
648:
649: static size_t
650: fts_maxarglen(char * const *argv)
651: {
652: size_t len, max;
653:
654: for (max = 0; *argv; ++argv)
655: if ((len = strlen(*argv)) > max)
656: max = len;
657: return (max + 1);
658: }
659:
660: #endif
CVSweb
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to compat_fts.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [cvsweb.bsd.lv] / mandoc