X-Git-Url: https://git.saurik.com/apple/libc.git/blobdiff_plain/224c70764cab4e0e39a26aaf3ad3016552f62f55..34e8f8296870d0e8695f90e1a54240a589d41312:/gen/fts.c diff --git a/gen/fts.c b/gen/fts.c index b8630c8..b06ef04 100644 --- a/gen/fts.c +++ b/gen/fts.c @@ -1,5 +1,5 @@ /* - * 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@ * @@ -64,6 +64,9 @@ #include #include #include +#ifdef __BLOCKS__ +#include +#endif /* __BLOCKS__ */ static FTSENT *fts_alloc(FTS *, char *, int); static FTSENT *fts_build(FTS *, int); @@ -88,31 +91,52 @@ static u_short fts_stat(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); @@ -151,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 { @@ -164,7 +188,7 @@ fts_open(argv, options, compar) } } } - if (compar && nitems > 1) + if (sp->fts_compar && nitems > 1) root = fts_sort(sp, root, nitems); /* @@ -196,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; @@ -258,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); @@ -558,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) @@ -577,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. */ @@ -603,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 @@ -636,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; @@ -706,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. */ @@ -914,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;