X-Git-Url: https://git.saurik.com/apple/libc.git/blobdiff_plain/734aad71947a79037af64f74c683f5eb36fe6065..51282358e8fdbfc483c0c34e7eae9b89b51f2570:/gen/fts.c diff --git a/gen/fts.c b/gen/fts.c index 1f29f44..b06ef04 100644 --- a/gen/fts.c +++ b/gen/fts.c @@ -1,10 +1,8 @@ /* - * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. + * Copyright (c) 1999, 2000, 2003, 2005, 2008 Apple Inc. All rights reserved. * * @APPLE_LICENSE_HEADER_START@ * - * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved. - * * This file contains Original Code and/or Modifications of Original Code * as defined in and that are subject to the Apple Public Source License * Version 2.0 (the 'License'). You may not use this file except in @@ -66,16 +64,19 @@ #include #include #include - -static FTSENT *fts_alloc __P((FTS *, char *, int)); -static FTSENT *fts_build __P((FTS *, int)); -static void fts_lfree __P((FTSENT *)); -static void fts_load __P((FTS *, FTSENT *)); -static size_t fts_maxarglen __P((char * const *)); -static void fts_padjust __P((FTS *, void *)); -static int fts_palloc __P((FTS *, size_t)); -static FTSENT *fts_sort __P((FTS *, FTSENT *, int)); -static u_short fts_stat __P((FTS *, FTSENT *, int)); +#ifdef __BLOCKS__ +#include +#endif /* __BLOCKS__ */ + +static FTSENT *fts_alloc(FTS *, char *, int); +static FTSENT *fts_build(FTS *, int); +static void fts_lfree(FTSENT *); +static void fts_load(FTS *, FTSENT *); +static size_t fts_maxarglen(char * const *); +static void fts_padjust(FTS *, void *); +static int fts_palloc(FTS *, size_t); +static FTSENT *fts_sort(FTS *, FTSENT *, int); +static u_short fts_stat(FTS *, FTSENT *, int); #define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2])) @@ -90,31 +91,52 @@ static u_short fts_stat __P((FTS *, FTSENT *, int)); #define BNAMES 2 /* fts_children, names only */ #define BREAD 3 /* fts_read */ -FTS * -fts_open(argv, options, compar) +/* 5653270 + * For directories containing > 64k subdirectories (or HFS+ with > 64k files + * and subdirectories), struct stat's st_nlink (16 bits) will overflow. This + * causes the case with FTS_NOSTAT and FTS_PHYSICAL set to prematurely stop + * recursing into subdirectories, because of an optimization that expects + * st_nlink to be the number of subdirectories (once that number has been + * encountered, no further calls to stat should be needed). + * + * However, on Mac OS X, another optimization largely nullifies the st_nlink + * optimization. struct dirent contains d_type, which can distinguish + * directories from files without initially calling stat. So stat is only + * called on known directories, rather than on other files. With this + * optimization, the difference in also using the st_nlink optimization is + * pretty minimal (tests show an improvement of a percent or two, probably + * due to additional if statement clauses that need to be evaluated). + * + * So removing the st_nlink optimization code will fix the > 64k subdirectories + * problem. And if we replace the multiple if clause logic with a single + * switch statement, we can recover the minimal performance lose. We can + * go even further and for the case of FTS_NOSTAT and FTS_LOGICAL set, we + * can use d_type to also distinguish symbolic links, and so we only need to + * call stat on directories and symlinks, not on all files. This provides + * a significant performance boost in that special case. + */ +/* + * The following macros defines values of the dostat variable, which is or-ed + * with the value of d_type, and the result used in a switch statement to + * determine whether to call stat or not. (We order the macros to minimize + * the size of any jump table that the compiler may generate.) + */ +#define F_SHIFT 4 /* shift to leave space for d_type */ +#define F_NOSTAT (0 << F_SHIFT) /* don't do any stat's */ +#define F_STATDIRSYM (1 << F_SHIFT) /* only stat directories and symlinks (and unknowns) */ +#define F_ALWAYSSTAT (2 << F_SHIFT) /* always stat */ +#define F_STATDIR (3 << F_SHIFT) /* only stat directories (and unknowns) */ + +static FTS * +__fts_open(argv, sp) char * const *argv; - register int options; - int (*compar)(); -{ register FTS *sp; +{ register FTSENT *p, *root; register int nitems; FTSENT *parent, *tmp; int len; - /* Options check. */ - if (options & ~FTS_OPTIONMASK) { - errno = EINVAL; - return (NULL); - } - - /* Allocate/initialize the stream */ - if ((sp = malloc((u_int)sizeof(FTS))) == NULL) - return (NULL); - memset(sp, 0, sizeof(FTS)); - sp->fts_compar = compar; - sp->fts_options = options; - /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ if (ISSET(FTS_LOGICAL)) SET(FTS_NOCHDIR); @@ -143,7 +165,7 @@ fts_open(argv, options, compar) p->fts_level = FTS_ROOTLEVEL; p->fts_parent = parent; p->fts_accpath = p->fts_name; - p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW)); + p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOWDIR) ? -1 : ISSET(FTS_COMFOLLOW)); /* Command-line "." and ".." are real directories. */ if (p->fts_info == FTS_DOT) @@ -153,7 +175,7 @@ fts_open(argv, options, compar) * If comparison routine supplied, traverse in sorted * order; otherwise traverse in the order specified. */ - if (compar) { + if (sp->fts_compar) { p->fts_link = root; root = p; } else { @@ -166,7 +188,7 @@ fts_open(argv, options, compar) } } } - if (compar && nitems > 1) + if (sp->fts_compar && nitems > 1) root = fts_sort(sp, root, nitems); /* @@ -198,6 +220,56 @@ mem1: free(sp); return (NULL); } +FTS * +fts_open(argv, options, compar) + char * const *argv; + int options; + int (*compar)(); +{ + register FTS *sp; + + /* Options check. */ + if (options & ~FTS_OPTIONMASK) { + errno = EINVAL; + return (NULL); + } + + /* Allocate/initialize the stream */ + if ((sp = malloc((u_int)sizeof(FTS))) == NULL) + return (NULL); + memset(sp, 0, sizeof(FTS)); + sp->fts_compar = compar; + sp->fts_options = options; + + return __fts_open(argv, sp); +} + +#ifdef __BLOCKS__ +FTS * +fts_open_b(argv, options, compar) + char * const *argv; + int options; + int (^compar)(const FTSENT **, const FTSENT **); +{ + register FTS *sp; + + /* Options check. */ + if (options & ~FTS_OPTIONMASK) { + errno = EINVAL; + return (NULL); + } + + /* Allocate/initialize the stream */ + if ((sp = malloc((u_int)sizeof(FTS))) == NULL) + return (NULL); + memset(sp, 0, sizeof(FTS)); + sp->fts_compar_b = (int (^)())Block_copy(compar); + sp->fts_options = options | FTS_BLOCK_COMPAR; + + return __fts_open(argv, sp); +} +#endif /* __BLOCKS__ */ + static void fts_load(sp, p) FTS *sp; @@ -260,6 +332,12 @@ fts_close(sp) (void)close(sp->fts_rfd); } +#ifdef __BLOCKS__ + /* Free up any block pointer. */ + if (ISSET(FTS_BLOCK_COMPAR) && sp->fts_compar_b != NULL) + Block_release(sp->fts_compar_b); +#endif /* __BLOCKS__ */ + /* Free up the stream pointer. */ free(sp); @@ -560,13 +638,9 @@ fts_children(sp, instr) * and fts_read. There are lots of special cases. * * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is - * set and it's a physical walk (so that symbolic links can't be directories), - * we can do things quickly. First, if it's a 4.4BSD file system, the type - * of the file is in the directory entry. Otherwise, we assume that the number - * of subdirectories in a node is equal to the number of links to the parent. - * The former skips all stat calls. The latter skips stat calls in any leaf - * directories and for any files after the subdirectories in the directory have - * been found, cutting the stat calls by about 2/3. + * set, we can use d_type to determine if the entry is a directory (or for + * logical walks, a directory or symlink) and not call stat for other file + * types. This cuts the number of stat calls significantly. */ static FTSENT * fts_build(sp, type) @@ -579,7 +653,7 @@ fts_build(sp, type) FTSENT *cur, *tail; DIR *dirp; void *adjaddr; - int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno; + int cderrno, descend, len, level, maxlen, dostat, oflag, saved_errno; char *cp; /* Set current node pointer. */ @@ -605,20 +679,15 @@ fts_build(sp, type) return (NULL); } - /* - * Nlinks is the number of possible entries of type directory in the - * directory if we're cheating on stat calls, 0 if we're not doing - * any stat calls at all, -1 if we're doing stats on everything. - */ if (type == BNAMES) - nlinks = 0; - else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) - nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2); + dostat = F_NOSTAT; + else if (ISSET(FTS_NOSTAT)) + dostat = ISSET(FTS_PHYSICAL) ? F_STATDIR : F_STATDIRSYM; else - nlinks = -1; + dostat = F_ALWAYSSTAT; #ifdef notdef - (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink); + (void)printf("dostat == %d\n", dostat); (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n", ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT)); #endif @@ -638,9 +707,9 @@ fts_build(sp, type) * checking FTS_NS on the returned nodes. */ cderrno = 0; - if (nlinks || type == BREAD) + if (dostat || type == BREAD) if (FCHDIR(sp, dirfd(dirp))) { - if (nlinks && type == BREAD) + if (dostat && type == BREAD) cur->fts_errno = errno; cur->fts_flags |= FTS_DONTCHDIR; descend = 0; @@ -708,35 +777,49 @@ mem1: saved_errno = errno; #endif if (cderrno) { - if (nlinks) { + if (dostat) { p->fts_info = FTS_NS; p->fts_errno = cderrno; } else p->fts_info = FTS_NSOK; p->fts_accpath = cur->fts_accpath; - } else if (nlinks == 0 -#ifdef DT_DIR - || nlinks > 0 && - dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN -#endif - ) { - p->fts_accpath = - ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; - p->fts_info = FTS_NSOK; } else { - /* Build a file name for fts_stat to stat. */ - if (ISSET(FTS_NOCHDIR)) { - p->fts_accpath = p->fts_path; - memmove(cp, p->fts_name, p->fts_namelen + 1); - } else - p->fts_accpath = p->fts_name; - /* Stat it. */ - p->fts_info = fts_stat(sp, p, 0); - - /* Decrement link count if applicable. */ - if (nlinks > 0 && (p->fts_info == FTS_D || - p->fts_info == FTS_DC || p->fts_info == FTS_DOT)) - --nlinks; + /* + * We need to know all file types values that d_type may + * be set to. So if that changes, the following needs + * to be modified appropriately. + */ + switch(dostat | dp->d_type) { + case (F_STATDIR | DT_UNKNOWN): + case (F_STATDIR | DT_DIR): + case (F_STATDIRSYM | DT_UNKNOWN): + case (F_STATDIRSYM | DT_DIR): + case (F_STATDIRSYM | DT_LNK): + case (F_ALWAYSSTAT | DT_UNKNOWN): + case (F_ALWAYSSTAT | DT_FIFO): + case (F_ALWAYSSTAT | DT_CHR): + case (F_ALWAYSSTAT | DT_DIR): + case (F_ALWAYSSTAT | DT_BLK): + case (F_ALWAYSSTAT | DT_REG): + case (F_ALWAYSSTAT | DT_LNK): + case (F_ALWAYSSTAT | DT_SOCK): + case (F_ALWAYSSTAT | DT_WHT): + /* Build a file name for fts_stat to stat. */ + if (ISSET(FTS_NOCHDIR)) { + p->fts_accpath = p->fts_path; + memmove(cp, p->fts_name, p->fts_namelen + 1); + } else + p->fts_accpath = p->fts_name; + /* Stat it. */ + p->fts_info = fts_stat(sp, p, 0); + break; + default: + /* No stat necessary */ + p->fts_accpath = + ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; + p->fts_info = FTS_NSOK; + break; + } } /* We walk in directory order so "ls -f" doesn't get upset. */ @@ -831,12 +914,24 @@ fts_stat(sp, p, follow) if (stat(p->fts_accpath, sbp)) { saved_errno = errno; if (!lstat(p->fts_accpath, sbp)) { + if (saved_errno == ELOOP) + p->fts_errno = ELOOP; errno = 0; return (FTS_SLNONE); } p->fts_errno = saved_errno; goto err; } + /* + * For FTS_COMFOLLOWDIR, drop back to lstat unless we have + * a directory + */ + if (follow == -1 && !S_ISDIR(sbp->st_mode)) { + if (lstat(p->fts_accpath, sbp)) { + p->fts_errno = errno; + goto err; + } + } } else if (lstat(p->fts_accpath, sbp)) { p->fts_errno = errno; err: memset(sbp, 0, sizeof(struct stat)); @@ -904,7 +999,12 @@ fts_sort(sp, head, nitems) } for (ap = sp->fts_array, p = head; p; p = p->fts_link) *ap++ = p; - qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar); +#ifdef __BLOCKS__ + if (ISSET(FTS_BLOCK_COMPAR)) + qsort_b((void *)sp->fts_array, nitems, sizeof(FTSENT *), (int (^)(const void *, const void *))sp->fts_compar_b); + else +#endif /* __BLOCKS__ */ + qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar); for (head = *(ap = sp->fts_array); --nitems; ++ap) ap[0]->fts_link = ap[1]; ap[0]->fts_link = NULL;