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