rpm  5.2.1
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;
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
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 *
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 =
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] == '/' ||
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",
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
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 @*/