source: trunk/src/kmk/kmkbuiltin/fts.c@ 1832

Last change on this file since 1832 was 1582, checked in by bird, 18 years ago

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