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