rpmio/fts.c

Go to the documentation of this file.
00001 /*@-boundsread@*/
00002 /*@-sysunrecog -noeffectuncon -nullpass -sizeoftype -unrecog -usereleased @*/
00003 /*@-compdef -compmempass -dependenttrans -retalias @*/
00004 /*-
00005  * Copyright (c) 1990, 1993, 1994
00006  *      The Regents of the University of California.  All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 1. Redistributions of source code must retain the above copyright
00012  *    notice, this list of conditions and the following disclaimer.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in the
00015  *    documentation and/or other materials provided with the distribution.
00016  * 4. Neither the name of the University nor the names of its contributors
00017  *    may be used to endorse or promote products derived from this software
00018  *    without specific prior written permission.
00019  *
00020  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00021  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00022  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00023  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00024  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00025  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00026  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00027  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00028  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00029  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00030  * SUCH DAMAGE.
00031  */
00032 
00033 #if defined(LIBC_SCCS) && !defined(lint)
00034 static char sccsid[] = "@(#)fts.c       8.6 (Berkeley) 8/14/94";
00035 #endif /* LIBC_SCCS and not lint */
00036 
00037 #if defined(_LIBC)
00038 #include <sys/param.h>
00039 #include <include/sys/stat.h>
00040 #include <fcntl.h>
00041 #include <dirent.h>
00042 #include <errno.h>
00043 #include <fts.h>
00044 #include <stdlib.h>
00045 #include <string.h>
00046 #include <unistd.h>
00047 #else
00048 #if defined(hpux)
00049 # define        _INCLUDE_POSIX_SOURCE
00050 #   define __errno_location()   (&errno)
00051 #   define dirfd(dirp)          -1
00052 #   define stat64               stat
00053 #   define _STAT_VER            0
00054 #   define __fxstat64(_stat_ver, _fd, _sbp)     fstat((_fd), (_sbp))
00055 #endif
00056 #if defined(sun)
00057 #   define __errno_location()   (&errno)
00058 #   define dirfd(dirp)          -1
00059 #   define _STAT_VER            0
00060 #   define __fxstat64(_stat_ver, _fd, _sbp)     fstat((_fd), (_sbp))
00061 #endif
00062 #if defined(__APPLE__)
00063 #   define __errno_location()   (__error())
00064 #   define _STAT_VER            0
00065 #endif
00066 #include "system.h"
00067 #include "fts.h"
00068 #include "rpmio.h"
00069 #include "rpmurl.h"
00070 #   define __set_errno(val) (*__errno_location ()) = (val)
00071 #   define __open       open
00072 #   define __close      close
00073 #   define __fchdir     fchdir
00074 #endif
00075 
00076 
00077 /* Largest alignment size needed, minus one.
00078    Usually long double is the worst case.  */
00079 #ifndef ALIGNBYTES
00080 #define ALIGNBYTES      (__alignof__ (long double) - 1)
00081 #endif
00082 /* Align P to that size.  */
00083 #ifndef ALIGN
00084 #define ALIGN(p)        (((unsigned long int) (p) + ALIGNBYTES) & ~ALIGNBYTES)
00085 #endif
00086 
00087 
00088 /*@only@*/ /*@null@*/
00089 static FTSENT * fts_alloc(FTS * sp, const char * name, int namelen)
00090         /*@*/;
00091 /*@null@*/
00092 static FTSENT * fts_build(FTS * sp, int type)
00093         /*@globals fileSystem, internalState @*/
00094         /*@modifies *sp, fileSystem, internalState @*/;
00095 static void     fts_lfree(/*@only@*/ FTSENT * head)
00096         /*@modifies head @*/;
00097 static void     fts_load(FTS * sp, FTSENT * p)
00098         /*@modifies *sp, *p @*/;
00099 static size_t   fts_maxarglen(char * const * argv)
00100         /*@*/;
00101 static void     fts_padjust(FTS * sp, FTSENT * head)
00102         /*@modifies *sp, *head @*/;
00103 static int      fts_palloc(FTS * sp, size_t more)
00104         /*@modifies *sp @*/;
00105 static FTSENT * fts_sort(FTS * sp, /*@returned@*/ FTSENT * head, int nitems)
00106         /*@modifies *sp @*/;
00107 static u_short  fts_stat(FTS * sp, FTSENT * p, int follow)
00108         /*@modifies *p @*/;
00109 static int      fts_safe_changedir(FTS * sp, FTSENT * p, int fd,
00110                         const char * path)
00111         /*@globals fileSystem, internalState @*/
00112         /*@modifies fileSystem, internalState @*/;
00113 
00114 #ifndef MAX
00115 #define MAX(a, b)       ({ __typeof__ (a) _a = (a); \
00116                            __typeof__ (b) _b = (b); \
00117                            _a > _b ? _a : _b; })
00118 #endif
00119 
00120 #define ISDOT(a)        (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
00121 
00122 #define CLR(opt)        (sp->fts_options &= ~(opt))
00123 #define ISSET(opt)      (sp->fts_options & (opt))
00124 #define SET(opt)        (sp->fts_options |= (opt))
00125 
00126 #define FCHDIR(sp, fd)  (!ISSET(FTS_NOCHDIR) && __fchdir(fd))
00127 
00128 /* fts_build flags */
00129 #define BCHILD          1               /* fts_children */
00130 #define BNAMES          2               /* fts_children, names only */
00131 #define BREAD           3               /* fts_read */
00132 
00133 FTS *
00134 Fts_open(char * const * argv, int options,
00135                 int (*compar) (const FTSENT **, const FTSENT **))
00136 {
00137         register FTS *sp;
00138         register FTSENT *p, *root;
00139         register int nitems;
00140         FTSENT *parent, *tmp = NULL;
00141         int len;
00142 
00143         /* Options check. */
00144         if (options & ~FTS_OPTIONMASK) {
00145 /*@-boundswrite@*/
00146                 __set_errno (EINVAL);
00147 /*@=boundswrite@*/
00148                 return (NULL);
00149         }
00150 
00151         /* Allocate/initialize the stream */
00152         if ((sp = malloc((u_int)sizeof(*sp))) == NULL)
00153                 return (NULL);
00154         memset(sp, 0, sizeof(*sp));
00155         sp->fts_compar = (int (*) (const void *, const void *)) compar;
00156         sp->fts_opendir = Opendir;
00157         sp->fts_readdir = Readdir;
00158         sp->fts_closedir = Closedir;
00159         sp->fts_stat = Stat;
00160         sp->fts_lstat = Lstat;
00161         sp->fts_options = options;
00162 
00163         /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
00164         if (ISSET(FTS_LOGICAL))
00165                 SET(FTS_NOCHDIR);
00166 
00167         /*
00168          * Start out with 1K of path space, and enough, in any case,
00169          * to hold the user's paths.
00170          */
00171 #ifndef MAXPATHLEN
00172 #define MAXPATHLEN 1024
00173 #endif
00174         if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
00175                 goto mem1;
00176 
00177         /* Allocate/initialize root's parent. */
00178         if ((parent = fts_alloc(sp, "", 0)) == NULL)
00179                 goto mem2;
00180         parent->fts_level = FTS_ROOTPARENTLEVEL;
00181 
00182         /* Allocate/initialize root(s). */
00183         for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
00184                 /* Don't allow zero-length paths. */
00185                 if ((len = strlen(*argv)) == 0) {
00186 /*@-boundswrite@*/
00187                         __set_errno (ENOENT);
00188 /*@=boundswrite@*/
00189                         goto mem3;
00190                 }
00191 
00192                 /* Use fchdir(2) speedup only if local DASDI. */
00193                 switch (urlIsURL(*argv)) {
00194                 case URL_IS_DASH:
00195                 case URL_IS_HKP:
00196 /*@-boundswrite@*/
00197                         __set_errno (ENOENT);
00198 /*@=boundswrite@*/
00199                         goto mem3;
00200                         /*@notreached@*/ /*@switchbreak@*/ break;
00201                 case URL_IS_HTTPS:
00202                 case URL_IS_HTTP:
00203                 case URL_IS_FTP:
00204                         SET(FTS_NOCHDIR);
00205                         /*@switchbreak@*/ break;
00206                 case URL_IS_UNKNOWN:
00207                 case URL_IS_PATH:
00208                         /*@switchbreak@*/ break;
00209                 }
00210 
00211                 p = fts_alloc(sp, *argv, len);
00212                 if (p == NULL)
00213                         goto mem3;
00214                 p->fts_level = FTS_ROOTLEVEL;
00215                 p->fts_parent = parent;
00216                 p->fts_accpath = p->fts_name;
00217                 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));
00218 
00219                 /* Command-line "." and ".." are real directories. */
00220                 if (p->fts_info == FTS_DOT)
00221                         p->fts_info = FTS_D;
00222 
00223                 /*
00224                  * If comparison routine supplied, traverse in sorted
00225                  * order; otherwise traverse in the order specified.
00226                  */
00227                 if (compar) {
00228                         p->fts_link = root;
00229                         root = p;
00230                 } else {
00231                         p->fts_link = NULL;
00232                         if (root == NULL)
00233                                 tmp = root = p;
00234                         else {
00235                                 if (tmp != NULL)        /* XXX can't happen */
00236                                         tmp->fts_link = p;
00237                                 tmp = p;
00238                         }
00239                 }
00240         }
00241         /*@-branchstate@*/
00242         if (compar && nitems > 1)
00243                 root = fts_sort(sp, root, nitems);
00244         /*@=branchstate@*/
00245 
00246         /*
00247          * Allocate a dummy pointer and make fts_read think that we've just
00248          * finished the node before the root(s); set p->fts_info to FTS_INIT
00249          * so that everything about the "current" node is ignored.
00250          */
00251         if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
00252                 goto mem3;
00253         sp->fts_cur->fts_link = root;
00254         sp->fts_cur->fts_info = FTS_INIT;
00255 
00256         /*
00257          * If using chdir(2), grab a file descriptor pointing to dot to ensure
00258          * that we can get back here; this could be avoided for some paths,
00259          * but almost certainly not worth the effort.  Slashes, symbolic links,
00260          * and ".." are all fairly nasty problems.  Note, if we can't get the
00261          * descriptor we run anyway, just more slowly.
00262          */
00263         if (!ISSET(FTS_NOCHDIR)
00264             && (sp->fts_rfd = __open(".", O_RDONLY, 0)) < 0)
00265                 SET(FTS_NOCHDIR);
00266 
00267         return (sp);
00268 
00269 mem3:   fts_lfree(root);
00270         free(parent);
00271 mem2:   free(sp->fts_path);
00272 mem1:   free(sp);
00273         return (NULL);
00274 }
00275 
00276 static void
00277 fts_load(FTS * sp, FTSENT * p)
00278 {
00279         register int len;
00280         register char *cp;
00281 
00282         /*
00283          * Load the stream structure for the next traversal.  Since we don't
00284          * actually enter the directory until after the preorder visit, set
00285          * the fts_accpath field specially so the chdir gets done to the right
00286          * place and the user can access the first node.  From fts_open it's
00287          * known that the path will fit.
00288          */
00289         len = p->fts_pathlen = p->fts_namelen;
00290 /*@-boundswrite@*/
00291         memmove(sp->fts_path, p->fts_name, len + 1);
00292         if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
00293                 len = strlen(++cp);
00294                 memmove(p->fts_name, cp, len + 1);
00295                 p->fts_namelen = len;
00296         }
00297         p->fts_accpath = p->fts_path = sp->fts_path;
00298         sp->fts_dev = p->fts_dev;
00299 /*@=boundswrite@*/
00300 }
00301 
00302 int
00303 Fts_close(FTS * sp)
00304 {
00305         register FTSENT *freep, *p;
00306         int saved_errno;
00307 
00308         if (sp == NULL)
00309                 return 0;
00310 
00311         /*
00312          * This still works if we haven't read anything -- the dummy structure
00313          * points to the root list, so we step through to the end of the root
00314          * list which has a valid parent pointer.
00315          */
00316         /*@-branchstate@*/
00317         if (sp->fts_cur) {
00318                 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
00319                         freep = p;
00320                         p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
00321                         free(freep);
00322                 }
00323                 free(p);
00324         }
00325         /*@=branchstate@*/
00326 
00327         /* Free up child linked list, sort array, path buffer. */
00328         if (sp->fts_child)
00329                 fts_lfree(sp->fts_child);
00330         if (sp->fts_array)
00331                 free(sp->fts_array);
00332         free(sp->fts_path);
00333 
00334         /* Return to original directory, save errno if necessary. */
00335         if (!ISSET(FTS_NOCHDIR)) {
00336                 saved_errno = __fchdir(sp->fts_rfd) ? errno : 0;
00337                 (void)__close(sp->fts_rfd);
00338 
00339                 /* Set errno and return. */
00340                 if (saved_errno != 0) {
00341                         /* Free up the stream pointer. */
00342                         free(sp);
00343 /*@-boundswrite@*/
00344                         __set_errno (saved_errno);
00345 /*@=boundswrite@*/
00346                         return (-1);
00347                 }
00348         }
00349 
00350         /* Free up the stream pointer. */
00351         free(sp);
00352         return (0);
00353 }
00354 
00355 /*
00356  * Special case of "/" at the end of the path so that slashes aren't
00357  * appended which would cause paths to be written as "....//foo".
00358  */
00359 #define NAPPEND(p)                                                      \
00360         (p->fts_path[p->fts_pathlen - 1] == '/'                         \
00361             ? p->fts_pathlen - 1 : p->fts_pathlen)
00362 
00363 FTSENT *
00364 Fts_read(FTS * sp)
00365 {
00366         register FTSENT *p;
00367         register FTSENT *tmp;
00368         register int instr;
00369         register char *t;
00370         int saved_errno;
00371 
00372         /* If finished or unrecoverable error, return NULL. */
00373         if (sp == NULL || sp->fts_cur == NULL || ISSET(FTS_STOP))
00374                 return (NULL);
00375 
00376         /* Set current node pointer. */
00377         p = sp->fts_cur;
00378 
00379         /* Save and zero out user instructions. */
00380         instr = p->fts_instr;
00381         p->fts_instr = FTS_NOINSTR;
00382 
00383         /* Any type of file may be re-visited; re-stat and re-turn. */
00384         if (instr == FTS_AGAIN) {
00385                 p->fts_info = fts_stat(sp, p, 0);
00386                 return (p);
00387         }
00388 
00389         /*
00390          * Following a symlink -- SLNONE test allows application to see
00391          * SLNONE and recover.  If indirecting through a symlink, have
00392          * keep a pointer to current location.  If unable to get that
00393          * pointer, follow fails.
00394          */
00395         if (instr == FTS_FOLLOW &&
00396             (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
00397                 p->fts_info = fts_stat(sp, p, 1);
00398                 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
00399                         if ((p->fts_symfd = __open(".", O_RDONLY, 0)) < 0) {
00400                                 p->fts_errno = errno;
00401                                 p->fts_info = FTS_ERR;
00402                         } else
00403                                 p->fts_flags |= FTS_SYMFOLLOW;
00404                 }
00405                 return (p);
00406         }
00407 
00408         /* Directory in pre-order. */
00409         if (p->fts_info == FTS_D) {
00410                 /* If skipped or crossed mount point, do post-order visit. */
00411                 if (instr == FTS_SKIP ||
00412                     (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
00413                         if (p->fts_flags & FTS_SYMFOLLOW)
00414                                 (void)__close(p->fts_symfd);
00415                         if (sp->fts_child) {
00416                                 fts_lfree(sp->fts_child);
00417                                 sp->fts_child = NULL;
00418                         }
00419                         p->fts_info = FTS_DP;
00420                         return (p);
00421                 }
00422 
00423                 /* Rebuild if only read the names and now traversing. */
00424                 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
00425                         CLR(FTS_NAMEONLY);
00426                         fts_lfree(sp->fts_child);
00427                         sp->fts_child = NULL;
00428                 }
00429 
00430                 /*
00431                  * Cd to the subdirectory.
00432                  *
00433                  * If have already read and now fail to chdir, whack the list
00434                  * to make the names come out right, and set the parent errno
00435                  * so the application will eventually get an error condition.
00436                  * Set the FTS_DONTCHDIR flag so that when we logically change
00437                  * directories back to the parent we don't do a chdir.
00438                  *
00439                  * If haven't read do so.  If the read fails, fts_build sets
00440                  * FTS_STOP or the fts_info field of the node.
00441                  */
00442                 if (sp->fts_child != NULL) {
00443                         if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
00444                                 p->fts_errno = errno;
00445                                 p->fts_flags |= FTS_DONTCHDIR;
00446                                 for (p = sp->fts_child; p != NULL;
00447                                      p = p->fts_link)
00448                                         p->fts_accpath =
00449                                             p->fts_parent->fts_accpath;
00450                         }
00451                 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
00452                         if (ISSET(FTS_STOP))
00453                                 return (NULL);
00454                         return (p);
00455                 }
00456                 p = sp->fts_child;
00457                 sp->fts_child = NULL;
00458                 goto name;
00459         }
00460 
00461         /* Move to the next node on this level. */
00462 /*@-boundswrite@*/
00463 next:   tmp = p;
00464         if ((p = p->fts_link) != NULL) {
00465                 free(tmp);
00466 
00467                 /*
00468                  * If reached the top, return to the original directory (or
00469                  * the root of the tree), and load the paths for the next root.
00470                  */
00471                 if (p->fts_level == FTS_ROOTLEVEL) {
00472                         if (FCHDIR(sp, sp->fts_rfd)) {
00473                                 SET(FTS_STOP);
00474                                 return (NULL);
00475                         }
00476                         fts_load(sp, p);
00477                         return (sp->fts_cur = p);
00478                 }
00479 
00480                 /*
00481                  * User may have called fts_set on the node.  If skipped,
00482                  * ignore.  If followed, get a file descriptor so we can
00483                  * get back if necessary.
00484                  */
00485                 if (p->fts_instr == FTS_SKIP)
00486                         goto next;
00487                 /*@-branchstate@*/
00488                 if (p->fts_instr == FTS_FOLLOW) {
00489                         p->fts_info = fts_stat(sp, p, 1);
00490                         if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
00491                                 if ((p->fts_symfd =
00492                                     __open(".", O_RDONLY, 0)) < 0) {
00493                                         p->fts_errno = errno;
00494                                         p->fts_info = FTS_ERR;
00495                                 } else
00496                                         p->fts_flags |= FTS_SYMFOLLOW;
00497                         }
00498                         p->fts_instr = FTS_NOINSTR;
00499                 }
00500                 /*@=branchstate@*/
00501 
00502 name:           t = sp->fts_path + NAPPEND(p->fts_parent);
00503                 *t++ = '/';
00504                 memmove(t, p->fts_name, p->fts_namelen + 1);
00505                 return (sp->fts_cur = p);
00506         }
00507 
00508         /* Move up to the parent node. */
00509         p = tmp->fts_parent;
00510         free(tmp);
00511 
00512         if (p->fts_level == FTS_ROOTPARENTLEVEL) {
00513                 /*
00514                  * Done; free everything up and set errno to 0 so the user
00515                  * can distinguish between error and EOF.
00516                  */
00517                 free(p);
00518                 __set_errno (0);
00519                 return (sp->fts_cur = NULL);
00520         }
00521 
00522         /* NUL terminate the pathname. */
00523         sp->fts_path[p->fts_pathlen] = '\0';
00524 /*@=boundswrite@*/
00525 
00526         /*
00527          * Return to the parent directory.  If at a root node or came through
00528          * a symlink, go back through the file descriptor.  Otherwise, cd up
00529          * one directory.
00530          */
00531         if (p->fts_level == FTS_ROOTLEVEL) {
00532                 if (FCHDIR(sp, sp->fts_rfd)) {
00533                         SET(FTS_STOP);
00534                         return (NULL);
00535                 }
00536         } else if (p->fts_flags & FTS_SYMFOLLOW) {
00537                 if (FCHDIR(sp, p->fts_symfd)) {
00538                         saved_errno = errno;
00539                         (void)__close(p->fts_symfd);
00540 /*@-boundswrite@*/
00541                         __set_errno (saved_errno);
00542 /*@=boundswrite@*/
00543                         SET(FTS_STOP);
00544                         return (NULL);
00545                 }
00546                 (void)__close(p->fts_symfd);
00547         } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
00548                    fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
00549                 SET(FTS_STOP);
00550                 return (NULL);
00551         }
00552         p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
00553         return (sp->fts_cur = p);
00554 }
00555 
00556 /*
00557  * Fts_set takes the stream as an argument although it's not used in this
00558  * implementation; it would be necessary if anyone wanted to add global
00559  * semantics to fts using fts_set.  An error return is allowed for similar
00560  * reasons.
00561  */
00562 int
00563 Fts_set(/*@unused@*/ FTS * sp, FTSENT * p, int instr)
00564 {
00565         if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
00566             instr != FTS_NOINSTR && instr != FTS_SKIP) {
00567 /*@-boundswrite@*/
00568                 __set_errno (EINVAL);
00569 /*@=boundswrite@*/
00570                 return (1);
00571         }
00572         p->fts_instr = instr;
00573         return (0);
00574 }
00575 
00576 FTSENT *
00577 Fts_children(FTS * sp, int instr)
00578 {
00579         register FTSENT *p;
00580         int fd;
00581 
00582         if (instr != 0 && instr != FTS_NAMEONLY) {
00583 /*@-boundswrite@*/
00584                 __set_errno (EINVAL);
00585 /*@=boundswrite@*/
00586                 return (NULL);
00587         }
00588 
00589         /* Set current node pointer. */
00590         p = sp->fts_cur;
00591 
00592         /*
00593          * Errno set to 0 so user can distinguish empty directory from
00594          * an error.
00595          */
00596 /*@-boundswrite@*/
00597         __set_errno (0);
00598 /*@=boundswrite@*/
00599 
00600         /* Fatal errors stop here. */
00601         if (ISSET(FTS_STOP))
00602                 return (NULL);
00603 
00604         /* Return logical hierarchy of user's arguments. */
00605         if (p->fts_info == FTS_INIT)
00606                 return (p->fts_link);
00607 
00608         /*
00609          * If not a directory being visited in pre-order, stop here.  Could
00610          * allow FTS_DNR, assuming the user has fixed the problem, but the
00611          * same effect is available with FTS_AGAIN.
00612          */
00613         if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
00614                 return (NULL);
00615 
00616         /* Free up any previous child list. */
00617         if (sp->fts_child != NULL)
00618                 fts_lfree(sp->fts_child);
00619 
00620         if (instr == FTS_NAMEONLY) {
00621                 SET(FTS_NAMEONLY);
00622                 instr = BNAMES;
00623         } else
00624                 instr = BCHILD;
00625 
00626         /*
00627          * If using chdir on a relative path and called BEFORE fts_read does
00628          * its chdir to the root of a traversal, we can lose -- we need to
00629          * chdir into the subdirectory, and we don't know where the current
00630          * directory is, so we can't get back so that the upcoming chdir by
00631          * fts_read will work.
00632          */
00633         if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
00634             ISSET(FTS_NOCHDIR))
00635                 return (sp->fts_child = fts_build(sp, instr));
00636 
00637         if ((fd = __open(".", O_RDONLY, 0)) < 0)
00638                 return (NULL);
00639         sp->fts_child = fts_build(sp, instr);
00640         if (__fchdir(fd))
00641                 return (NULL);
00642         (void)__close(fd);
00643         return (sp->fts_child);
00644 }
00645 
00646 /*
00647  * This is the tricky part -- do not casually change *anything* in here.  The
00648  * idea is to build the linked list of entries that are used by fts_children
00649  * and fts_read.  There are lots of special cases.
00650  *
00651  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
00652  * set and it's a physical walk (so that symbolic links can't be directories),
00653  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
00654  * of the file is in the directory entry.  Otherwise, we assume that the number
00655  * of subdirectories in a node is equal to the number of links to the parent.
00656  * The former skips all stat calls.  The latter skips stat calls in any leaf
00657  * directories and for any files after the subdirectories in the directory have
00658  * been found, cutting the stat calls by about 2/3.
00659  */
00660 static FTSENT *
00661 fts_build(FTS * sp, int type)
00662 {
00663         register struct dirent *dp;
00664         register FTSENT *p, *head;
00665         register int nitems;
00666         FTSENT *cur, *tail;
00667         DIR *dirp;
00668         void *oldaddr;
00669         int cderrno, descend, len, level, maxlen, nlinks, saved_errno,
00670             nostat, doadjust;
00671         char *cp;
00672 
00673         /* Set current node pointer. */
00674         cur = sp->fts_cur;
00675 
00676         /*
00677          * Open the directory for reading.  If this fails, we're done.
00678          * If being called from fts_read, set the fts_info field.
00679          */
00680 #if defined FTS_WHITEOUT && 0
00681         if (ISSET(FTS_WHITEOUT))
00682                 oflag = DTF_NODUP|DTF_REWIND;
00683         else
00684                 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
00685 #else
00686 # define __opendir2(path, flag) (*sp->fts_opendir) (path)
00687 #endif
00688        if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
00689                 if (type == BREAD) {
00690                         cur->fts_info = FTS_DNR;
00691                         cur->fts_errno = errno;
00692                 }
00693                 return (NULL);
00694         }
00695 
00696         /*
00697          * Nlinks is the number of possible entries of type directory in the
00698          * directory if we're cheating on stat calls, 0 if we're not doing
00699          * any stat calls at all, -1 if we're doing stats on everything.
00700          */
00701         if (type == BNAMES) {
00702                 nlinks = 0;
00703                 /* Be quiet about nostat, GCC. */
00704                 nostat = 0;
00705         } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
00706                 nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
00707                 nostat = 1;
00708         } else {
00709                 nlinks = -1;
00710                 nostat = 0;
00711         }
00712 
00713 #ifdef notdef
00714         (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
00715         (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
00716             ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
00717 #endif
00718         /*
00719          * If we're going to need to stat anything or we want to descend
00720          * and stay in the directory, chdir.  If this fails we keep going,
00721          * but set a flag so we don't chdir after the post-order visit.
00722          * We won't be able to stat anything, but we can still return the
00723          * names themselves.  Note, that since fts_read won't be able to
00724          * chdir into the directory, it will have to return different path
00725          * names than before, i.e. "a/b" instead of "b".  Since the node
00726          * has already been visited in pre-order, have to wait until the
00727          * post-order visit to return the error.  There is a special case
00728          * here, if there was nothing to stat then it's not an error to
00729          * not be able to stat.  This is all fairly nasty.  If a program
00730          * needed sorted entries or stat information, they had better be
00731          * checking FTS_NS on the returned nodes.
00732          */
00733         cderrno = 0;
00734         if (nlinks || type == BREAD) {
00735                 if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
00736                         if (nlinks && type == BREAD)
00737                                 cur->fts_errno = errno;
00738                         cur->fts_flags |= FTS_DONTCHDIR;
00739                         descend = 0;
00740                         cderrno = errno;
00741                         (void) (*sp->fts_closedir) (dirp);
00742                         dirp = NULL;
00743                 } else
00744                         descend = 1;
00745         } else
00746                 descend = 0;
00747 
00748         /*
00749          * Figure out the max file name length that can be stored in the
00750          * current path -- the inner loop allocates more path as necessary.
00751          * We really wouldn't have to do the maxlen calculations here, we
00752          * could do them in fts_read before returning the path, but it's a
00753          * lot easier here since the length is part of the dirent structure.
00754          *
00755          * If not changing directories set a pointer so that can just append
00756          * each new name into the path.
00757          */
00758         len = NAPPEND(cur);
00759         if (ISSET(FTS_NOCHDIR)) {
00760                 cp = sp->fts_path + len;
00761 /*@-boundswrite@*/
00762                 *cp++ = '/';
00763 /*@=boundswrite@*/
00764         } else {
00765                 /* GCC, you're too verbose. */
00766                 cp = NULL;
00767         }
00768         len++;
00769         maxlen = sp->fts_pathlen - len;
00770 
00771         level = cur->fts_level + 1;
00772 
00773         /* Read the directory, attaching each entry to the `link' pointer. */
00774         doadjust = 0;
00775         for (head = tail = NULL, nitems = 0;
00776              dirp && (dp = (*sp->fts_readdir) (dirp));)
00777         {
00778                 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
00779                         continue;
00780 
00781                 if ((p = fts_alloc(sp, dp->d_name, (int)_D_EXACT_NAMLEN (dp))) == NULL)
00782                         goto mem1;
00783                 if (_D_EXACT_NAMLEN (dp) >= maxlen) {/* include space for NUL */
00784                         oldaddr = sp->fts_path;
00785                         if (fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
00786                                 /*
00787                                  * No more memory for path or structures.  Save
00788                                  * errno, free up the current structure and the
00789                                  * structures already allocated.
00790                                  */
00791 mem1:                           saved_errno = errno;
00792                                 if (p)
00793                                         free(p);
00794                                 fts_lfree(head);
00795                                 (void) (*sp->fts_closedir) (dirp);
00796                                 cur->fts_info = FTS_ERR;
00797                                 SET(FTS_STOP);
00798                                 __set_errno (saved_errno);
00799                                 return (NULL);
00800                         }
00801                         /* Did realloc() change the pointer? */
00802                         if (oldaddr != sp->fts_path) {
00803                                 doadjust = 1;
00804                                 if (ISSET(FTS_NOCHDIR))
00805                                         cp = sp->fts_path + len;
00806                         }
00807                         maxlen = sp->fts_pathlen - len;
00808                 }
00809 
00810                 if (len + _D_EXACT_NAMLEN (dp) >= USHRT_MAX) {
00811                         /*
00812                          * In an FTSENT, fts_pathlen is a u_short so it is
00813                          * possible to wraparound here.  If we do, free up
00814                          * the current structure and the structures already
00815                          * allocated, then error out with ENAMETOOLONG.
00816                          */
00817                         free(p);
00818                         fts_lfree(head);
00819                         (void) (*sp->fts_closedir) (dirp);
00820                         cur->fts_info = FTS_ERR;
00821                         SET(FTS_STOP);
00822                         __set_errno (ENAMETOOLONG);
00823                         return (NULL);
00824                 }
00825                 p->fts_level = level;
00826                 p->fts_parent = sp->fts_cur;
00827                 p->fts_pathlen = len + _D_EXACT_NAMLEN (dp);
00828 
00829 #if defined FTS_WHITEOUT && 0
00830                 if (dp->d_type == DT_WHT)
00831                         p->fts_flags |= FTS_ISW;
00832 #endif
00833 
00834                 if (cderrno) {
00835                         if (nlinks) {
00836                                 p->fts_info = FTS_NS;
00837                                 p->fts_errno = cderrno;
00838                         } else
00839                                 p->fts_info = FTS_NSOK;
00840                         p->fts_accpath = cur->fts_accpath;
00841                 } else if (nlinks == 0
00842 #if defined DT_DIR && defined _DIRENT_HAVE_D_TYPE
00843                            || (nostat &&
00844                                dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
00845 #endif
00846                     ) {
00847                         p->fts_accpath =
00848                             ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
00849                         p->fts_info = FTS_NSOK;
00850                 } else {
00851                         /* Build a file name for fts_stat to stat. */
00852                         if (ISSET(FTS_NOCHDIR)) {
00853                                 p->fts_accpath = p->fts_path;
00854                                 memmove(cp, p->fts_name, p->fts_namelen + 1);
00855                         } else
00856                                 p->fts_accpath = p->fts_name;
00857                         /* Stat it. */
00858                         p->fts_info = fts_stat(sp, p, 0);
00859 
00860                         /* Decrement link count if applicable. */
00861                         if (nlinks > 0 && (p->fts_info == FTS_D ||
00862                             p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
00863                                 --nlinks;
00864                 }
00865 
00866                 /* We walk in directory order so "ls -f" doesn't get upset. */
00867                 p->fts_link = NULL;
00868                 if (head == NULL)
00869                         head = tail = p;
00870                 else {
00871                         tail->fts_link = p;
00872                         tail = p;
00873                 }
00874                 ++nitems;
00875         }
00876         if (dirp)
00877                 (void) (*sp->fts_closedir) (dirp);
00878 
00879         /*
00880          * If realloc() changed the address of the path, adjust the
00881          * addresses for the rest of the tree and the dir list.
00882          */
00883         if (doadjust)
00884                 fts_padjust(sp, head);
00885 
00886         /*
00887          * If not changing directories, reset the path back to original
00888          * state.
00889          */
00890         if (ISSET(FTS_NOCHDIR)) {
00891                 if (len == sp->fts_pathlen || nitems == 0)
00892                         --cp;
00893 /*@-boundswrite@*/
00894                 if (cp != NULL) /* XXX can't happen */
00895                         *cp = '\0';
00896 /*@=boundswrite@*/
00897         }
00898 
00899         /*
00900          * If descended after called from fts_children or after called from
00901          * fts_read and nothing found, get back.  At the root level we use
00902          * the saved fd; if one of fts_open()'s arguments is a relative path
00903          * to an empty directory, we wind up here with no other way back.  If
00904          * can't get back, we're done.
00905          */
00906         if (descend && (type == BCHILD || !nitems) &&
00907             (cur->fts_level == FTS_ROOTLEVEL ?
00908              FCHDIR(sp, sp->fts_rfd) :
00909              fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
00910                 cur->fts_info = FTS_ERR;
00911                 SET(FTS_STOP);
00912                 return (NULL);
00913         }
00914 
00915         /* If didn't find anything, return NULL. */
00916         if (!nitems) {
00917                 if (type == BREAD)
00918                         cur->fts_info = FTS_DP;
00919                 return (NULL);
00920         }
00921 
00922         /* Sort the entries. */
00923         if (sp->fts_compar && nitems > 1)
00924                 head = fts_sort(sp, head, nitems);
00925         return (head);
00926 }
00927 
00928 static u_short
00929 fts_stat(FTS * sp, FTSENT * p, int follow)
00930 {
00931         register FTSENT *t;
00932         register dev_t dev;
00933         register ino_t ino;
00934         struct stat *sbp, sb;
00935         int saved_errno;
00936 
00937         /* If user needs stat info, stat buffer already allocated. */
00938         sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
00939 
00940 #if defined FTS_WHITEOUT && 0
00941         /* check for whiteout */
00942         if (p->fts_flags & FTS_ISW) {
00943                 if (sbp != &sb) {
00944                         memset(sbp, '\0', sizeof (*sbp));
00945                         sbp->st_mode = S_IFWHT;
00946                 }
00947                 return (FTS_W);
00948        }
00949 #endif
00950 
00951         /*
00952          * If doing a logical walk, or application requested FTS_FOLLOW, do
00953          * a stat(2).  If that fails, check for a non-existent symlink.  If
00954          * fail, set the errno from the stat call.
00955          */
00956         if (ISSET(FTS_LOGICAL) || follow) {
00957                 if ((*sp->fts_stat) (p->fts_accpath, sbp)) {
00958                         saved_errno = errno;
00959                         if (!(*sp->fts_lstat) (p->fts_accpath, sbp)) {
00960 /*@-boundswrite@*/
00961                                 __set_errno (0);
00962 /*@=boundswrite@*/
00963                                 return (FTS_SLNONE);
00964                         }
00965                         p->fts_errno = saved_errno;
00966                         goto err;
00967                 }
00968         } else if ((*sp->fts_lstat) (p->fts_accpath, sbp)) {
00969                 p->fts_errno = errno;
00970 /*@-boundswrite@*/
00971 err:            memset(sbp, 0, sizeof(*sbp));
00972 /*@=boundswrite@*/
00973                 return (FTS_NS);
00974         }
00975 
00976         if (S_ISDIR(sbp->st_mode)) {
00977                 /*
00978                  * Set the device/inode.  Used to find cycles and check for
00979                  * crossing mount points.  Also remember the link count, used
00980                  * in fts_build to limit the number of stat calls.  It is
00981                  * understood that these fields are only referenced if fts_info
00982                  * is set to FTS_D.
00983                  */
00984                 dev = p->fts_dev = sbp->st_dev;
00985                 ino = p->fts_ino = sbp->st_ino;
00986                 p->fts_nlink = sbp->st_nlink;
00987 
00988                 if (ISDOT(p->fts_name))
00989                         return (FTS_DOT);
00990 
00991                 /*
00992                  * Cycle detection is done by brute force when the directory
00993                  * is first encountered.  If the tree gets deep enough or the
00994                  * number of symbolic links to directories is high enough,
00995                  * something faster might be worthwhile.
00996                  */
00997                 for (t = p->fts_parent;
00998                     t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
00999                         if (ino == t->fts_ino && dev == t->fts_dev) {
01000                                 p->fts_cycle = t;
01001                                 return (FTS_DC);
01002                         }
01003                 return (FTS_D);
01004         }
01005         if (S_ISLNK(sbp->st_mode))
01006                 return (FTS_SL);
01007         if (S_ISREG(sbp->st_mode))
01008                 return (FTS_F);
01009         return (FTS_DEFAULT);
01010 }
01011 
01012 static FTSENT *
01013 fts_sort(FTS * sp, FTSENT * head, int nitems)
01014 {
01015         register FTSENT **ap, *p;
01016 
01017         /*
01018          * Construct an array of pointers to the structures and call qsort(3).
01019          * Reassemble the array in the order returned by qsort.  If unable to
01020          * sort for memory reasons, return the directory entries in their
01021          * current order.  Allocate enough space for the current needs plus
01022          * 40 so don't realloc one entry at a time.
01023          */
01024         if (nitems > sp->fts_nitems) {
01025                 struct _ftsent **a;
01026 
01027                 sp->fts_nitems = nitems + 40;
01028                 if ((a = realloc(sp->fts_array,
01029                     (size_t)(sp->fts_nitems * sizeof(*sp->fts_array)))) == NULL)
01030                 {
01031                         free(sp->fts_array);
01032                         sp->fts_array = NULL;
01033                         sp->fts_nitems = 0;
01034                         return (head);
01035                 }
01036                 sp->fts_array = a;
01037         }
01038 /*@-boundswrite@*/
01039         for (ap = sp->fts_array, p = head; p != NULL; p = p->fts_link)
01040                 *ap++ = p;
01041         qsort((void *)sp->fts_array, nitems, sizeof(*sp->fts_array),
01042                 sp->fts_compar);
01043         for (head = *(ap = sp->fts_array); --nitems; ++ap)
01044                 ap[0]->fts_link = ap[1];
01045         ap[0]->fts_link = NULL;
01046 /*@=boundswrite@*/
01047         return (head);
01048 }
01049 
01050 static FTSENT *
01051 fts_alloc(FTS * sp, const char * name, int namelen)
01052 {
01053         register FTSENT *p;
01054         size_t len;
01055 
01056         /*
01057          * The file name is a variable length array and no stat structure is
01058          * necessary if the user has set the nostat bit.  Allocate the FTSENT
01059          * structure, the file name and the stat structure in one chunk, but
01060          * be careful that the stat structure is reasonably aligned.  Since the
01061          * fts_name field is declared to be of size 1, the fts_name pointer is
01062          * namelen + 2 before the first possible address of the stat structure.
01063          */
01064         len = sizeof(*p) + namelen;
01065         if (!ISSET(FTS_NOSTAT))
01066                 len += sizeof(*p->fts_statp) + ALIGNBYTES;
01067         if ((p = malloc(len)) == NULL)
01068                 return (NULL);
01069 
01070         /* Copy the name and guarantee NUL termination. */
01071 /*@-boundswrite@*/
01072         memmove(p->fts_name, name, namelen);
01073         p->fts_name[namelen] = '\0';
01074 /*@=boundswrite@*/
01075 
01076         if (!ISSET(FTS_NOSTAT))
01077                 p->fts_statp = (struct stat *)ALIGN(p->fts_name + namelen + 2);
01078         p->fts_namelen = namelen;
01079         p->fts_path = sp->fts_path;
01080         p->fts_errno = 0;
01081         p->fts_flags = 0;
01082         p->fts_instr = FTS_NOINSTR;
01083         p->fts_number = 0;
01084         p->fts_pointer = NULL;
01085         return (p);
01086 }
01087 
01088 static void
01089 fts_lfree(FTSENT * head)
01090 {
01091         register FTSENT *p;
01092 
01093         /* Free a linked list of structures. */
01094         /*@-branchstate@*/
01095         while ((p = head)) {
01096                 head = head->fts_link;
01097                 free(p);
01098         }
01099         /*@=branchstate@*/
01100 }
01101 
01102 /*
01103  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
01104  * Most systems will allow creation of paths much longer than MAXPATHLEN, even
01105  * though the kernel won't resolve them.  Add the size (not just what's needed)
01106  * plus 256 bytes so don't realloc the path 2 bytes at a time.
01107  */
01108 static int
01109 fts_palloc(FTS * sp, size_t more)
01110 {
01111         char *p;
01112 
01113         sp->fts_pathlen += more + 256;
01114         /*
01115          * Check for possible wraparound.  In an FTS, fts_pathlen is
01116          * a signed int but in an FTSENT it is an unsigned short.
01117          * We limit fts_pathlen to USHRT_MAX to be safe in both cases.
01118          */
01119         if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) {
01120                 if (sp->fts_path) {
01121                         free(sp->fts_path);
01122                         sp->fts_path = NULL;
01123                 }
01124                 sp->fts_path = NULL;
01125 /*@-boundswrite@*/
01126                 __set_errno (ENAMETOOLONG);
01127 /*@=boundswrite@*/
01128                 return (1);
01129         }
01130         p = realloc(sp->fts_path, sp->fts_pathlen);
01131         if (p == NULL) {
01132                 free(sp->fts_path);
01133                 sp->fts_path = NULL;
01134                 return 1;
01135         }
01136         sp->fts_path = p;
01137         return 0;
01138 }
01139 
01140 /*
01141  * When the path is realloc'd, have to fix all of the pointers in structures
01142  * already returned.
01143  */
01144 static void
01145 fts_padjust(FTS * sp, FTSENT * head)
01146 {
01147         FTSENT *p;
01148         char *addr = sp->fts_path;
01149 
01150 #define ADJUST(p) do {                                                  \
01151         if ((p)->fts_accpath != (p)->fts_name) {                        \
01152                 (p)->fts_accpath =                                      \
01153                     (char *)addr + ((p)->fts_accpath - (p)->fts_path);  \
01154         }                                                               \
01155         (p)->fts_path = addr;                                           \
01156 } while (0)
01157         /* Adjust the current set of children. */
01158         for (p = sp->fts_child; p != NULL; p = p->fts_link)
01159                 ADJUST(p);
01160 
01161         /* Adjust the rest of the tree, including the current level. */
01162         for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
01163                 ADJUST(p);
01164                 p = p->fts_link ? p->fts_link : p->fts_parent;
01165         }
01166 }
01167 
01168 static size_t
01169 fts_maxarglen(char * const * argv)
01170 {
01171         size_t len, max;
01172 
01173         for (max = 0; *argv; ++argv)
01174                 if ((len = strlen(*argv)) > max)
01175                         max = len;
01176         return (max + 1);
01177 }
01178 
01179 /*
01180  * Change to dir specified by fd or p->fts_accpath without getting
01181  * tricked by someone changing the world out from underneath us.
01182  * Assumes p->fts_dev and p->fts_ino are filled in.
01183  */
01184 static int
01185 fts_safe_changedir(FTS * sp, FTSENT * p, int fd, const char * path)
01186 {
01187         int ret, oerrno, newfd;
01188         struct stat64 sb;
01189 
01190         newfd = fd;
01191         if (ISSET(FTS_NOCHDIR))
01192                 return (0);
01193         if (fd < 0 && (newfd = __open(path, O_RDONLY, 0)) < 0)
01194                 return (-1);
01195         if (__fxstat64(_STAT_VER, newfd, &sb)) {
01196                 ret = -1;
01197                 goto bail;
01198         }
01199         if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {
01200 /*@-boundswrite@*/
01201                 __set_errno (ENOENT);           /* disinformation */
01202 /*@=boundswrite@*/
01203                 ret = -1;
01204                 goto bail;
01205         }
01206         ret = __fchdir(newfd);
01207 bail:
01208         oerrno = errno;
01209         if (fd < 0)
01210                 (void)__close(newfd);
01211 /*@-boundswrite@*/
01212         __set_errno (oerrno);
01213 /*@=boundswrite@*/
01214         return (ret);
01215 }
01216 /*@=compdef =compmempass =dependenttrans =retalias @*/
01217 /*@=sysunrecog =noeffectuncon =nullpass =sizeoftype =unrecog =usereleased @*/
01218 /*@=boundsread@*/

Generated on Thu May 14 14:44:24 2009 for rpm by  doxygen 1.4.7