rpm 5.2.1

- Main Page
- Related Pages
- Modules
- Data Structures
- Files

- File List
- Globals

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