Index: head/lib/libc/gen/fts-compat.c =================================================================== --- head/lib/libc/gen/fts-compat.c (revision 287792) +++ head/lib/libc/gen/fts-compat.c (revision 287793) @@ -1,1246 +1,1225 @@ /*- * Copyright (c) 1990, 1993, 1994 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 4. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $OpenBSD: fts.c,v 1.22 1999/10/03 19:22:22 millert Exp $ */ #if 0 #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94"; #endif /* LIBC_SCCS and not lint */ #endif #include __FBSDID("$FreeBSD$"); #include "namespace.h" #include #include #include #include #include #include #include #include #include #include "fts-compat.h" #include "un-namespace.h" #include "gen-private.h" FTSENT *__fts_children_44bsd(FTS *, int); int __fts_close_44bsd(FTS *); void *__fts_get_clientptr_44bsd(FTS *); FTS *__fts_get_stream_44bsd(FTSENT *); FTS *__fts_open_44bsd(char * const *, int, int (*)(const FTSENT * const *, const FTSENT * const *)); FTSENT *__fts_read_44bsd(FTS *); int __fts_set_44bsd(FTS *, FTSENT *, int); void __fts_set_clientptr_44bsd(FTS *, void *); 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 *, FTSENT *); static int fts_palloc(FTS *, size_t); static FTSENT *fts_sort(FTS *, FTSENT *, int); static u_short fts_stat(FTS *, FTSENT *, int); static int fts_safe_changedir(FTS *, FTSENT *, int, char *); static int fts_ufslinks(FTS *, const FTSENT *); #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2]))) #define CLR(opt) (sp->fts_options &= ~(opt)) #define ISSET(opt) (sp->fts_options & (opt)) #define SET(opt) (sp->fts_options |= (opt)) #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd)) /* fts_build flags */ #define BCHILD 1 /* fts_children */ #define BNAMES 2 /* fts_children, names only */ #define BREAD 3 /* fts_read */ /* * Internal representation of an FTS, including extra implementation * details. The FTS returned from fts_open points to this structure's * ftsp_fts member (and can be cast to an _fts_private as required) */ struct _fts_private { FTS ftsp_fts; struct statfs ftsp_statfs; dev_t ftsp_dev; int ftsp_linksreliable; }; /* * The "FTS_NOSTAT" option can avoid a lot of calls to stat(2) if it * knows that a directory could not possibly have subdirectories. This * is decided by looking at the link count: a subdirectory would * increment its parent's link count by virtue of its own ".." entry. * This assumption only holds for UFS-like filesystems that implement * links and directories this way, so we must punt for others. */ static const char *ufslike_filesystems[] = { "ufs", "zfs", "nfs", "nfs4", "ext2fs", 0 }; FTS * __fts_open_44bsd(argv, options, compar) char * const *argv; int options; int (*compar)(const FTSENT * const *, const FTSENT * const *); { struct _fts_private *priv; FTS *sp; FTSENT *p, *root; int nitems; FTSENT *parent, *tmp; int len; /* Options check. */ if (options & ~FTS_OPTIONMASK) { errno = EINVAL; return (NULL); } /* Allocate/initialize the stream. */ if ((priv = malloc(sizeof(*priv))) == NULL) return (NULL); memset(priv, 0, sizeof(*priv)); sp = &priv->ftsp_fts; sp->fts_compar = compar; sp->fts_options = options; /* Shush, GCC. */ tmp = NULL; /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ if (ISSET(FTS_LOGICAL)) SET(FTS_NOCHDIR); /* * Start out with 1K of path space, and enough, in any case, * to hold the user's paths. */ if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN))) goto mem1; /* Allocate/initialize root's parent. */ if ((parent = fts_alloc(sp, "", 0)) == NULL) goto mem2; parent->fts_level = FTS_ROOTPARENTLEVEL; /* Allocate/initialize root(s). */ for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) { /* Don't allow zero-length paths. */ if ((len = strlen(*argv)) == 0) { errno = ENOENT; goto mem3; } p = fts_alloc(sp, *argv, len); 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)); /* Command-line "." and ".." are real directories. */ if (p->fts_info == FTS_DOT) p->fts_info = FTS_D; /* * If comparison routine supplied, traverse in sorted * order; otherwise traverse in the order specified. */ if (compar) { p->fts_link = root; root = p; } else { p->fts_link = NULL; if (root == NULL) tmp = root = p; else { tmp->fts_link = p; tmp = p; } } } if (compar && nitems > 1) root = fts_sort(sp, root, nitems); /* * Allocate a dummy pointer and make fts_read think that we've just * finished the node before the root(s); set p->fts_info to FTS_INIT * so that everything about the "current" node is ignored. */ if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL) goto mem3; sp->fts_cur->fts_link = root; sp->fts_cur->fts_info = FTS_INIT; /* * If using chdir(2), grab a file descriptor pointing to dot to ensure * that we can get back here; this could be avoided for some paths, * but almost certainly not worth the effort. Slashes, symbolic links, * and ".." are all fairly nasty problems. Note, if we can't get the * descriptor we run anyway, just more slowly. */ if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) SET(FTS_NOCHDIR); return (sp); mem3: fts_lfree(root); free(parent); mem2: free(sp->fts_path); mem1: free(sp); return (NULL); } static void fts_load(sp, p) FTS *sp; FTSENT *p; { int len; char *cp; /* * Load the stream structure for the next traversal. Since we don't * actually enter the directory until after the preorder visit, set * the fts_accpath field specially so the chdir gets done to the right * place and the user can access the first node. From fts_open it's * known that the path will fit. */ len = p->fts_pathlen = p->fts_namelen; memmove(sp->fts_path, p->fts_name, len + 1); if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { len = strlen(++cp); memmove(p->fts_name, cp, len + 1); p->fts_namelen = len; } p->fts_accpath = p->fts_path = sp->fts_path; sp->fts_dev = p->fts_dev; } int __fts_close_44bsd(sp) FTS *sp; { FTSENT *freep, *p; int saved_errno; /* * This still works if we haven't read anything -- the dummy structure * points to the root list, so we step through to the end of the root * list which has a valid parent pointer. */ if (sp->fts_cur) { for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { freep = p; p = p->fts_link != NULL ? p->fts_link : p->fts_parent; free(freep); } free(p); } /* Free up child linked list, sort array, path buffer. */ if (sp->fts_child) fts_lfree(sp->fts_child); if (sp->fts_array) free(sp->fts_array); free(sp->fts_path); /* Return to original directory, save errno if necessary. */ if (!ISSET(FTS_NOCHDIR)) { saved_errno = fchdir(sp->fts_rfd) ? errno : 0; (void)_close(sp->fts_rfd); /* Set errno and return. */ if (saved_errno != 0) { /* Free up the stream pointer. */ free(sp); errno = saved_errno; return (-1); } } /* Free up the stream pointer. */ free(sp); return (0); } /* * Special case of "/" at the end of the path so that slashes aren't * appended which would cause paths to be written as "....//foo". */ #define NAPPEND(p) \ (p->fts_path[p->fts_pathlen - 1] == '/' \ ? p->fts_pathlen - 1 : p->fts_pathlen) FTSENT * __fts_read_44bsd(sp) FTS *sp; { FTSENT *p, *tmp; int instr; char *t; int saved_errno; /* If finished or unrecoverable error, return NULL. */ if (sp->fts_cur == NULL || ISSET(FTS_STOP)) return (NULL); /* Set current node pointer. */ p = sp->fts_cur; /* Save and zero out user instructions. */ instr = p->fts_instr; p->fts_instr = FTS_NOINSTR; /* Any type of file may be re-visited; re-stat and re-turn. */ if (instr == FTS_AGAIN) { p->fts_info = fts_stat(sp, p, 0); return (p); } /* * Following a symlink -- SLNONE test allows application to see * SLNONE and recover. If indirecting through a symlink, have * keep a pointer to current location. If unable to get that * pointer, follow fails. */ if (instr == FTS_FOLLOW && (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { p->fts_info = fts_stat(sp, p, 1); if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { if ((p->fts_symfd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) { p->fts_errno = errno; p->fts_info = FTS_ERR; } else p->fts_flags |= FTS_SYMFOLLOW; } return (p); } /* Directory in pre-order. */ if (p->fts_info == FTS_D) { /* If skipped or crossed mount point, do post-order visit. */ if (instr == FTS_SKIP || (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) { if (p->fts_flags & FTS_SYMFOLLOW) (void)_close(p->fts_symfd); if (sp->fts_child) { fts_lfree(sp->fts_child); sp->fts_child = NULL; } p->fts_info = FTS_DP; return (p); } /* Rebuild if only read the names and now traversing. */ if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) { CLR(FTS_NAMEONLY); fts_lfree(sp->fts_child); sp->fts_child = NULL; } /* * Cd to the subdirectory. * * If have already read and now fail to chdir, whack the list * to make the names come out right, and set the parent errno * so the application will eventually get an error condition. * Set the FTS_DONTCHDIR flag so that when we logically change * directories back to the parent we don't do a chdir. * * If haven't read do so. If the read fails, fts_build sets * FTS_STOP or the fts_info field of the node. */ if (sp->fts_child != NULL) { if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) { p->fts_errno = errno; p->fts_flags |= FTS_DONTCHDIR; for (p = sp->fts_child; p != NULL; p = p->fts_link) p->fts_accpath = p->fts_parent->fts_accpath; } } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) { if (ISSET(FTS_STOP)) return (NULL); return (p); } p = sp->fts_child; sp->fts_child = NULL; goto name; } /* Move to the next node on this level. */ next: tmp = p; if ((p = p->fts_link) != NULL) { free(tmp); /* * If reached the top, return to the original directory (or * the root of the tree), and load the paths for the next root. */ if (p->fts_level == FTS_ROOTLEVEL) { if (FCHDIR(sp, sp->fts_rfd)) { SET(FTS_STOP); return (NULL); } fts_load(sp, p); return (sp->fts_cur = p); } /* * User may have called fts_set on the node. If skipped, * ignore. If followed, get a file descriptor so we can * get back if necessary. */ if (p->fts_instr == FTS_SKIP) goto next; if (p->fts_instr == FTS_FOLLOW) { p->fts_info = fts_stat(sp, p, 1); if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { if ((p->fts_symfd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) { p->fts_errno = errno; p->fts_info = FTS_ERR; } else p->fts_flags |= FTS_SYMFOLLOW; } p->fts_instr = FTS_NOINSTR; } name: t = sp->fts_path + NAPPEND(p->fts_parent); *t++ = '/'; memmove(t, p->fts_name, p->fts_namelen + 1); return (sp->fts_cur = p); } /* Move up to the parent node. */ p = tmp->fts_parent; free(tmp); if (p->fts_level == FTS_ROOTPARENTLEVEL) { /* * Done; free everything up and set errno to 0 so the user * can distinguish between error and EOF. */ free(p); errno = 0; return (sp->fts_cur = NULL); } /* NUL terminate the pathname. */ sp->fts_path[p->fts_pathlen] = '\0'; /* * Return to the parent directory. If at a root node or came through * a symlink, go back through the file descriptor. Otherwise, cd up * one directory. */ if (p->fts_level == FTS_ROOTLEVEL) { if (FCHDIR(sp, sp->fts_rfd)) { SET(FTS_STOP); return (NULL); } } else if (p->fts_flags & FTS_SYMFOLLOW) { if (FCHDIR(sp, p->fts_symfd)) { saved_errno = errno; (void)_close(p->fts_symfd); errno = saved_errno; SET(FTS_STOP); return (NULL); } (void)_close(p->fts_symfd); } else if (!(p->fts_flags & FTS_DONTCHDIR) && fts_safe_changedir(sp, p->fts_parent, -1, "..")) { SET(FTS_STOP); return (NULL); } p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP; return (sp->fts_cur = p); } /* * Fts_set takes the stream as an argument although it's not used in this * implementation; it would be necessary if anyone wanted to add global * semantics to fts using fts_set. An error return is allowed for similar * reasons. */ /* ARGSUSED */ int __fts_set_44bsd(sp, p, instr) FTS *sp; FTSENT *p; int instr; { if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW && instr != FTS_NOINSTR && instr != FTS_SKIP) { errno = EINVAL; return (1); } p->fts_instr = instr; return (0); } FTSENT * __fts_children_44bsd(sp, instr) FTS *sp; int instr; { FTSENT *p; int fd; if (instr != 0 && instr != FTS_NAMEONLY) { errno = EINVAL; return (NULL); } /* Set current node pointer. */ p = sp->fts_cur; /* * Errno set to 0 so user can distinguish empty directory from * an error. */ errno = 0; /* Fatal errors stop here. */ if (ISSET(FTS_STOP)) return (NULL); /* Return logical hierarchy of user's arguments. */ if (p->fts_info == FTS_INIT) return (p->fts_link); /* * If not a directory being visited in pre-order, stop here. Could * allow FTS_DNR, assuming the user has fixed the problem, but the * same effect is available with FTS_AGAIN. */ if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */) return (NULL); /* Free up any previous child list. */ if (sp->fts_child != NULL) fts_lfree(sp->fts_child); if (instr == FTS_NAMEONLY) { SET(FTS_NAMEONLY); instr = BNAMES; } else instr = BCHILD; /* * If using chdir on a relative path and called BEFORE fts_read does * its chdir to the root of a traversal, we can lose -- we need to * chdir into the subdirectory, and we don't know where the current * directory is, so we can't get back so that the upcoming chdir by * fts_read will work. */ if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || ISSET(FTS_NOCHDIR)) return (sp->fts_child = fts_build(sp, instr)); if ((fd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) return (NULL); sp->fts_child = fts_build(sp, instr); if (fchdir(fd)) return (NULL); (void)_close(fd); return (sp->fts_child); } #ifndef fts_get_clientptr #error "fts_get_clientptr not defined" #endif void * (__fts_get_clientptr_44bsd)(FTS *sp) { return (fts_get_clientptr(sp)); } #ifndef fts_get_stream #error "fts_get_stream not defined" #endif FTS * (__fts_get_stream_44bsd)(FTSENT *p) { return (fts_get_stream(p)); } void __fts_set_clientptr_44bsd(FTS *sp, void *clientptr) { sp->fts_clientptr = clientptr; } /* * This is the tricky part -- do not casually change *anything* in here. The * idea is to build the linked list of entries that are used by fts_children * 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. */ static FTSENT * -fts_build(sp, type) - FTS *sp; - int type; +fts_build(FTS *sp, int type) { struct dirent *dp; FTSENT *p, *head; int nitems; FTSENT *cur, *tail; DIR *dirp; void *oldaddr; size_t dnamlen; int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno, nostat, doadjust; char *cp; /* Set current node pointer. */ cur = sp->fts_cur; /* * Open the directory for reading. If this fails, we're done. * If being called from fts_read, set the fts_info field. */ #ifdef FTS_WHITEOUT if (ISSET(FTS_WHITEOUT)) oflag = DTF_NODUP | DTF_REWIND; else oflag = DTF_HIDEW | DTF_NODUP | DTF_REWIND; #else #define __opendir2(path, flag) opendir(path) #endif if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) { if (type == BREAD) { cur->fts_info = FTS_DNR; cur->fts_errno = errno; } 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; /* Be quiet about nostat, GCC. */ nostat = 0; } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) { if (fts_ufslinks(sp, cur)) nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2); else nlinks = -1; nostat = 1; } else { nlinks = -1; nostat = 0; } #ifdef notdef (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink); (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n", ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT)); #endif /* * If we're going to need to stat anything or we want to descend * and stay in the directory, chdir. If this fails we keep going, * but set a flag so we don't chdir after the post-order visit. * We won't be able to stat anything, but we can still return the * names themselves. Note, that since fts_read won't be able to * chdir into the directory, it will have to return different path * names than before, i.e. "a/b" instead of "b". Since the node * has already been visited in pre-order, have to wait until the * post-order visit to return the error. There is a special case * here, if there was nothing to stat then it's not an error to * not be able to stat. This is all fairly nasty. If a program * needed sorted entries or stat information, they had better be * checking FTS_NS on the returned nodes. */ cderrno = 0; if (nlinks || type == BREAD) { if (fts_safe_changedir(sp, cur, _dirfd(dirp), NULL)) { if (nlinks && type == BREAD) cur->fts_errno = errno; cur->fts_flags |= FTS_DONTCHDIR; descend = 0; cderrno = errno; } else descend = 1; } else descend = 0; /* * Figure out the max file name length that can be stored in the * current path -- the inner loop allocates more path as necessary. * We really wouldn't have to do the maxlen calculations here, we * could do them in fts_read before returning the path, but it's a * lot easier here since the length is part of the dirent structure. * * If not changing directories set a pointer so that can just append * each new name into the path. */ len = NAPPEND(cur); if (ISSET(FTS_NOCHDIR)) { cp = sp->fts_path + len; *cp++ = '/'; } else { /* GCC, you're too verbose. */ cp = NULL; } len++; maxlen = sp->fts_pathlen - len; level = cur->fts_level + 1; /* Read the directory, attaching each entry to the `link' pointer. */ doadjust = 0; for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) { dnamlen = dp->d_namlen; if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) continue; if ((p = fts_alloc(sp, dp->d_name, (int)dnamlen)) == NULL) goto mem1; if (dnamlen >= maxlen) { /* include space for NUL */ oldaddr = sp->fts_path; if (fts_palloc(sp, dnamlen + len + 1)) { /* * No more memory for path or structures. Save * errno, free up the current structure and the * structures already allocated. */ mem1: saved_errno = errno; if (p) free(p); fts_lfree(head); (void)closedir(dirp); cur->fts_info = FTS_ERR; SET(FTS_STOP); errno = saved_errno; return (NULL); } /* Did realloc() change the pointer? */ if (oldaddr != sp->fts_path) { doadjust = 1; if (ISSET(FTS_NOCHDIR)) cp = sp->fts_path + len; } maxlen = sp->fts_pathlen - len; } if (len + dnamlen >= USHRT_MAX) { /* * In an FTSENT, fts_pathlen is a u_short so it is * possible to wraparound here. If we do, free up * the current structure and the structures already * allocated, then error out with ENAMETOOLONG. */ free(p); fts_lfree(head); (void)closedir(dirp); cur->fts_info = FTS_ERR; SET(FTS_STOP); errno = ENAMETOOLONG; return (NULL); } p->fts_level = level; p->fts_parent = sp->fts_cur; p->fts_pathlen = len + dnamlen; #ifdef FTS_WHITEOUT if (dp->d_type == DT_WHT) p->fts_flags |= FTS_ISW; #endif if (cderrno) { if (nlinks) { 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 || (nostat && 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 walk in directory order so "ls -f" doesn't get upset. */ p->fts_link = NULL; if (head == NULL) head = tail = p; else { tail->fts_link = p; tail = p; } ++nitems; } if (dirp) (void)closedir(dirp); /* * If realloc() changed the address of the path, adjust the * addresses for the rest of the tree and the dir list. */ if (doadjust) fts_padjust(sp, head); /* * If not changing directories, reset the path back to original * state. */ if (ISSET(FTS_NOCHDIR)) { if (len == sp->fts_pathlen || nitems == 0) --cp; *cp = '\0'; } /* * If descended after called from fts_children or after called from * fts_read and nothing found, get back. At the root level we use * the saved fd; if one of fts_open()'s arguments is a relative path * to an empty directory, we wind up here with no other way back. If * can't get back, we're done. */ if (descend && (type == BCHILD || !nitems) && (cur->fts_level == FTS_ROOTLEVEL ? FCHDIR(sp, sp->fts_rfd) : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) { cur->fts_info = FTS_ERR; SET(FTS_STOP); return (NULL); } /* If didn't find anything, return NULL. */ if (!nitems) { if (type == BREAD) cur->fts_info = FTS_DP; return (NULL); } /* Sort the entries. */ if (sp->fts_compar && nitems > 1) head = fts_sort(sp, head, nitems); return (head); } static u_short -fts_stat(sp, p, follow) - FTS *sp; - FTSENT *p; - int follow; +fts_stat(FTS *sp, FTSENT *p, int follow) { FTSENT *t; dev_t dev; ino_t ino; struct stat *sbp, sb; int saved_errno; /* If user needs stat info, stat buffer already allocated. */ sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp; #ifdef FTS_WHITEOUT /* Check for whiteout. */ if (p->fts_flags & FTS_ISW) { if (sbp != &sb) { memset(sbp, '\0', sizeof(*sbp)); sbp->st_mode = S_IFWHT; } return (FTS_W); } #endif /* * If doing a logical walk, or application requested FTS_FOLLOW, do * a stat(2). If that fails, check for a non-existent symlink. If * fail, set the errno from the stat call. */ if (ISSET(FTS_LOGICAL) || follow) { if (stat(p->fts_accpath, sbp)) { saved_errno = errno; if (!lstat(p->fts_accpath, sbp)) { errno = 0; return (FTS_SLNONE); } p->fts_errno = saved_errno; goto err; } } else if (lstat(p->fts_accpath, sbp)) { p->fts_errno = errno; err: memset(sbp, 0, sizeof(struct stat)); return (FTS_NS); } if (S_ISDIR(sbp->st_mode)) { /* * Set the device/inode. Used to find cycles and check for * crossing mount points. Also remember the link count, used * in fts_build to limit the number of stat calls. It is * understood that these fields are only referenced if fts_info * is set to FTS_D. */ dev = p->fts_dev = sbp->st_dev; ino = p->fts_ino = sbp->st_ino; p->fts_nlink = sbp->st_nlink; if (ISDOT(p->fts_name)) return (FTS_DOT); /* * Cycle detection is done by brute force when the directory * is first encountered. If the tree gets deep enough or the * number of symbolic links to directories is high enough, * something faster might be worthwhile. */ for (t = p->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) if (ino == t->fts_ino && dev == t->fts_dev) { p->fts_cycle = t; return (FTS_DC); } return (FTS_D); } if (S_ISLNK(sbp->st_mode)) return (FTS_SL); if (S_ISREG(sbp->st_mode)) return (FTS_F); return (FTS_DEFAULT); } /* * The comparison function takes pointers to pointers to FTSENT structures. * Qsort wants a comparison function that takes pointers to void. * (Both with appropriate levels of const-poisoning, of course!) * Use a trampoline function to deal with the difference. */ static int fts_compar(const void *a, const void *b) { FTS *parent; parent = (*(const FTSENT * const *)a)->fts_fts; return (*parent->fts_compar)(a, b); } static FTSENT * -fts_sort(sp, head, nitems) - FTS *sp; - FTSENT *head; - int nitems; +fts_sort(FTS *sp, FTSENT *head, int nitems) { FTSENT **ap, *p; /* * Construct an array of pointers to the structures and call qsort(3). * Reassemble the array in the order returned by qsort. If unable to * sort for memory reasons, return the directory entries in their * current order. Allocate enough space for the current needs plus * 40 so don't realloc one entry at a time. */ if (nitems > sp->fts_nitems) { sp->fts_nitems = nitems + 40; if ((sp->fts_array = reallocf(sp->fts_array, sp->fts_nitems * sizeof(FTSENT *))) == NULL) { sp->fts_nitems = 0; return (head); } } for (ap = sp->fts_array, p = head; p; p = p->fts_link) *ap++ = p; qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar); for (head = *(ap = sp->fts_array); --nitems; ++ap) ap[0]->fts_link = ap[1]; ap[0]->fts_link = NULL; return (head); } static FTSENT * -fts_alloc(sp, name, namelen) - FTS *sp; - char *name; - int namelen; +fts_alloc(FTS *sp, char *name, int namelen) { FTSENT *p; size_t len; struct ftsent_withstat { FTSENT ent; struct stat statbuf; }; /* * The file name is a variable length array and no stat structure is * necessary if the user has set the nostat bit. Allocate the FTSENT * structure, the file name and the stat structure in one chunk, but * be careful that the stat structure is reasonably aligned. */ if (ISSET(FTS_NOSTAT)) len = sizeof(FTSENT) + namelen + 1; else len = sizeof(struct ftsent_withstat) + namelen + 1; if ((p = malloc(len)) == NULL) return (NULL); if (ISSET(FTS_NOSTAT)) { p->fts_name = (char *)(p + 1); p->fts_statp = NULL; } else { p->fts_name = (char *)((struct ftsent_withstat *)p + 1); p->fts_statp = &((struct ftsent_withstat *)p)->statbuf; } /* Copy the name and guarantee NUL termination. */ memcpy(p->fts_name, name, namelen); p->fts_name[namelen] = '\0'; p->fts_namelen = namelen; p->fts_path = sp->fts_path; p->fts_errno = 0; p->fts_flags = 0; p->fts_instr = FTS_NOINSTR; p->fts_number = 0; p->fts_pointer = NULL; p->fts_fts = sp; return (p); } static void -fts_lfree(head) - FTSENT *head; +fts_lfree(FTSENT *head) { FTSENT *p; /* Free a linked list of structures. */ while ((p = head)) { head = head->fts_link; free(p); } } /* * Allow essentially unlimited paths; find, rm, ls should all work on any tree. * Most systems will allow creation of paths much longer than MAXPATHLEN, even * though the kernel won't resolve them. Add the size (not just what's needed) * plus 256 bytes so don't realloc the path 2 bytes at a time. */ static int -fts_palloc(sp, more) - FTS *sp; - size_t more; +fts_palloc(FTS *sp, size_t more) { sp->fts_pathlen += more + 256; /* * Check for possible wraparound. In an FTS, fts_pathlen is * a signed int but in an FTSENT it is an unsigned short. * We limit fts_pathlen to USHRT_MAX to be safe in both cases. */ if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) { if (sp->fts_path) free(sp->fts_path); sp->fts_path = NULL; errno = ENAMETOOLONG; return (1); } sp->fts_path = reallocf(sp->fts_path, sp->fts_pathlen); return (sp->fts_path == NULL); } /* * When the path is realloc'd, have to fix all of the pointers in structures * already returned. */ static void -fts_padjust(sp, head) - FTS *sp; - FTSENT *head; +fts_padjust(FTS *sp, FTSENT *head) { FTSENT *p; char *addr = sp->fts_path; #define ADJUST(p) do { \ if ((p)->fts_accpath != (p)->fts_name) { \ (p)->fts_accpath = \ (char *)addr + ((p)->fts_accpath - (p)->fts_path); \ } \ (p)->fts_path = addr; \ } while (0) /* Adjust the current set of children. */ for (p = sp->fts_child; p; p = p->fts_link) ADJUST(p); /* Adjust the rest of the tree, including the current level. */ for (p = head; p->fts_level >= FTS_ROOTLEVEL;) { ADJUST(p); p = p->fts_link ? p->fts_link : p->fts_parent; } } static size_t -fts_maxarglen(argv) - char * const *argv; +fts_maxarglen(char * const *argv) { size_t len, max; for (max = 0; *argv; ++argv) if ((len = strlen(*argv)) > max) max = len; return (max + 1); } /* * Change to dir specified by fd or p->fts_accpath without getting * tricked by someone changing the world out from underneath us. * Assumes p->fts_dev and p->fts_ino are filled in. */ static int -fts_safe_changedir(sp, p, fd, path) - FTS *sp; - FTSENT *p; - int fd; - char *path; +fts_safe_changedir(FTS *sp, FTSENT *p, int fd, char *path) { int ret, oerrno, newfd; struct stat sb; newfd = fd; if (ISSET(FTS_NOCHDIR)) return (0); if (fd < 0 && (newfd = _open(path, O_RDONLY | O_CLOEXEC, 0)) < 0) return (-1); if (_fstat(newfd, &sb)) { ret = -1; goto bail; } if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) { errno = ENOENT; /* disinformation */ ret = -1; goto bail; } ret = fchdir(newfd); bail: oerrno = errno; if (fd < 0) (void)_close(newfd); errno = oerrno; return (ret); } /* * Check if the filesystem for "ent" has UFS-style links. */ static int fts_ufslinks(FTS *sp, const FTSENT *ent) { struct _fts_private *priv; const char **cpp; priv = (struct _fts_private *)sp; /* * If this node's device is different from the previous, grab * the filesystem information, and decide on the reliability * of the link information from this filesystem for stat(2) * avoidance. */ if (priv->ftsp_dev != ent->fts_dev) { if (statfs(ent->fts_path, &priv->ftsp_statfs) != -1) { priv->ftsp_dev = ent->fts_dev; priv->ftsp_linksreliable = 0; for (cpp = ufslike_filesystems; *cpp; cpp++) { if (strcmp(priv->ftsp_statfs.f_fstypename, *cpp) == 0) { priv->ftsp_linksreliable = 1; break; } } } else { priv->ftsp_linksreliable = 0; } } return (priv->ftsp_linksreliable); } __sym_compat(fts_open, __fts_open_44bsd, FBSD_1.0); __sym_compat(fts_close, __fts_close_44bsd, FBSD_1.0); __sym_compat(fts_read, __fts_read_44bsd, FBSD_1.0); __sym_compat(fts_set, __fts_set_44bsd, FBSD_1.0); __sym_compat(fts_children, __fts_children_44bsd, FBSD_1.0); __sym_compat(fts_get_clientptr, __fts_get_clientptr_44bsd, FBSD_1.0); __sym_compat(fts_get_stream, __fts_get_stream_44bsd, FBSD_1.0); __sym_compat(fts_set_clientptr, __fts_set_clientptr_44bsd, FBSD_1.0); Index: head/lib/libc/gen/getloadavg.c =================================================================== --- head/lib/libc/gen/getloadavg.c (revision 287792) +++ head/lib/libc/gen/getloadavg.c (revision 287793) @@ -1,69 +1,67 @@ /*- * Copyright (c) 1989, 1993 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 4. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)getloadavg.c 8.1 (Berkeley) 6/4/93"; #endif /* LIBC_SCCS and not lint */ #include __FBSDID("$FreeBSD$"); #include #include #include #include #include #include /* * getloadavg() -- Get system load averages. * * Put `nelem' samples into `loadavg' array. * Return number of samples retrieved, or -1 on error. */ int -getloadavg(loadavg, nelem) - double loadavg[]; - int nelem; +getloadavg(double loadavg[], int nelem) { struct loadavg loadinfo; int i, mib[2]; size_t size; mib[0] = CTL_VM; mib[1] = VM_LOADAVG; size = sizeof(loadinfo); if (sysctl(mib, 2, &loadinfo, &size, NULL, 0) < 0) return (-1); nelem = MIN(nelem, sizeof(loadinfo.ldavg) / sizeof(fixpt_t)); for (i = 0; i < nelem; i++) loadavg[i] = (double) loadinfo.ldavg[i] / loadinfo.fscale; return (nelem); } Index: head/lib/libc/gen/getmntinfo.c =================================================================== --- head/lib/libc/gen/getmntinfo.c (revision 287792) +++ head/lib/libc/gen/getmntinfo.c (revision 287793) @@ -1,68 +1,66 @@ /* * Copyright (c) 1989, 1993 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 4. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)getmntinfo.c 8.1 (Berkeley) 6/4/93"; #endif /* LIBC_SCCS and not lint */ #include __FBSDID("$FreeBSD$"); #include #include #include #include /* * Return information about mounted filesystems. */ int -getmntinfo(mntbufp, flags) - struct statfs **mntbufp; - int flags; +getmntinfo(struct statfs **mntbufp, int flags) { static struct statfs *mntbuf; static int mntsize; static long bufsize; if (mntsize <= 0 && (mntsize = getfsstat(0, 0, MNT_NOWAIT)) < 0) return (0); if (bufsize > 0 && (mntsize = getfsstat(mntbuf, bufsize, flags)) < 0) return (0); while (bufsize <= mntsize * sizeof(struct statfs)) { if (mntbuf) free(mntbuf); bufsize = (mntsize + 1) * sizeof(struct statfs); if ((mntbuf = (struct statfs *)malloc(bufsize)) == 0) return (0); if ((mntsize = getfsstat(mntbuf, bufsize, flags)) < 0) return (0); } *mntbufp = mntbuf; return (mntsize); } Index: head/lib/libc/gen/nlist.c =================================================================== --- head/lib/libc/gen/nlist.c (revision 287792) +++ head/lib/libc/gen/nlist.c (revision 287793) @@ -1,414 +1,403 @@ /* * Copyright (c) 1989, 1993 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 4. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)nlist.c 8.1 (Berkeley) 6/4/93"; #endif /* LIBC_SCCS and not lint */ #include __FBSDID("$FreeBSD$"); #include "namespace.h" #include #include #include #include #include #include #include #include #include #include #include "un-namespace.h" /* There is no a.out support on arm64 */ #ifndef __aarch64__ #define _NLIST_DO_AOUT #endif #define _NLIST_DO_ELF #ifdef _NLIST_DO_ELF #include #include #endif int __fdnlist(int, struct nlist *); int __aout_fdnlist(int, struct nlist *); int __elf_fdnlist(int, struct nlist *); int -nlist(name, list) - const char *name; - struct nlist *list; +nlist(const char *name, struct nlist *list) { int fd, n; fd = _open(name, O_RDONLY | O_CLOEXEC, 0); if (fd < 0) return (-1); n = __fdnlist(fd, list); (void)_close(fd); return (n); } static struct nlist_handlers { int (*fn)(int fd, struct nlist *list); } nlist_fn[] = { #ifdef _NLIST_DO_AOUT { __aout_fdnlist }, #endif #ifdef _NLIST_DO_ELF { __elf_fdnlist }, #endif }; int -__fdnlist(fd, list) - int fd; - struct nlist *list; +__fdnlist(int fd, struct nlist *list) { - int n = -1, i; + int n = -1; + unsigned int i; for (i = 0; i < sizeof(nlist_fn) / sizeof(nlist_fn[0]); i++) { n = (nlist_fn[i].fn)(fd, list); if (n != -1) break; } return (n); } #define ISLAST(p) (p->n_un.n_name == 0 || p->n_un.n_name[0] == 0) #ifdef _NLIST_DO_AOUT int -__aout_fdnlist(fd, list) - int fd; - struct nlist *list; +__aout_fdnlist(int fd, struct nlist *list) { struct nlist *p, *symtab; caddr_t strtab, a_out_mmap; off_t stroff, symoff; u_long symsize; int nent; struct exec * exec; struct stat st; /* check that file is at least as large as struct exec! */ if ((_fstat(fd, &st) < 0) || (st.st_size < sizeof(struct exec))) return (-1); /* Check for files too large to mmap. */ if (st.st_size > SIZE_T_MAX) { errno = EFBIG; return (-1); } /* * Map the whole a.out file into our address space. * We then find the string table withing this area. * We do not just mmap the string table, as it probably * does not start at a page boundary - we save ourselves a * lot of nastiness by mmapping the whole file. * * This gives us an easy way to randomly access all the strings, * without making the memory allocation permanent as with * malloc/free (i.e., munmap will return it to the system). */ a_out_mmap = mmap(NULL, (size_t)st.st_size, PROT_READ, MAP_PRIVATE, fd, (off_t)0); if (a_out_mmap == MAP_FAILED) return (-1); exec = (struct exec *)a_out_mmap; if (N_BADMAG(*exec)) { munmap(a_out_mmap, (size_t)st.st_size); return (-1); } symoff = N_SYMOFF(*exec); symsize = exec->a_syms; stroff = symoff + symsize; /* find the string table in our mmapped area */ strtab = a_out_mmap + stroff; symtab = (struct nlist *)(a_out_mmap + symoff); /* * clean out any left-over information for all valid entries. * Type and value defined to be 0 if not found; historical * versions cleared other and desc as well. Also figure out * the largest string length so don't read any more of the * string table than we have to. * * XXX clearing anything other than n_type and n_value violates * the semantics given in the man page. */ nent = 0; for (p = list; !ISLAST(p); ++p) { p->n_type = 0; p->n_other = 0; p->n_desc = 0; p->n_value = 0; ++nent; } while (symsize > 0) { int soff; symsize-= sizeof(struct nlist); soff = symtab->n_un.n_strx; if (soff != 0 && (symtab->n_type & N_STAB) == 0) for (p = list; !ISLAST(p); p++) if (!strcmp(&strtab[soff], p->n_un.n_name)) { p->n_value = symtab->n_value; p->n_type = symtab->n_type; p->n_desc = symtab->n_desc; p->n_other = symtab->n_other; if (--nent <= 0) break; } symtab++; } munmap(a_out_mmap, (size_t)st.st_size); return (nent); } #endif #ifdef _NLIST_DO_ELF static void elf_sym_to_nlist(struct nlist *, Elf_Sym *, Elf_Shdr *, int); /* * __elf_is_okay__ - Determine if ehdr really * is ELF and valid for the target platform. * * WARNING: This is NOT an ELF ABI function and * as such its use should be restricted. */ int __elf_is_okay__(Elf_Ehdr *ehdr) { int retval = 0; /* * We need to check magic, class size, endianess, * and version before we look at the rest of the * Elf_Ehdr structure. These few elements are * represented in a machine independant fashion. */ if (IS_ELF(*ehdr) && ehdr->e_ident[EI_CLASS] == ELF_TARG_CLASS && ehdr->e_ident[EI_DATA] == ELF_TARG_DATA && ehdr->e_ident[EI_VERSION] == ELF_TARG_VER) { /* Now check the machine dependant header */ if (ehdr->e_machine == ELF_TARG_MACH && ehdr->e_version == ELF_TARG_VER) retval = 1; } return retval; } int -__elf_fdnlist(fd, list) - int fd; - struct nlist *list; +__elf_fdnlist(int fd, struct nlist *list) { struct nlist *p; Elf_Off symoff = 0, symstroff = 0; Elf_Size symsize = 0, symstrsize = 0; Elf_Ssize cc, i; int nent = -1; int errsave; Elf_Sym sbuf[1024]; Elf_Sym *s; Elf_Ehdr ehdr; char *strtab = NULL; Elf_Shdr *shdr = NULL; Elf_Size shdr_size; void *base; struct stat st; /* Make sure obj is OK */ if (lseek(fd, (off_t)0, SEEK_SET) == -1 || _read(fd, &ehdr, sizeof(Elf_Ehdr)) != sizeof(Elf_Ehdr) || !__elf_is_okay__(&ehdr) || _fstat(fd, &st) < 0) return (-1); /* calculate section header table size */ shdr_size = ehdr.e_shentsize * ehdr.e_shnum; /* Make sure it's not too big to mmap */ if (shdr_size > SIZE_T_MAX) { errno = EFBIG; return (-1); } /* mmap section header table */ base = mmap(NULL, (size_t)shdr_size, PROT_READ, MAP_PRIVATE, fd, (off_t)ehdr.e_shoff); if (base == MAP_FAILED) return (-1); shdr = (Elf_Shdr *)base; /* * Find the symbol table entry and it's corresponding * string table entry. Version 1.1 of the ABI states * that there is only one symbol table but that this * could change in the future. */ for (i = 0; i < ehdr.e_shnum; i++) { if (shdr[i].sh_type == SHT_SYMTAB) { symoff = shdr[i].sh_offset; symsize = shdr[i].sh_size; symstroff = shdr[shdr[i].sh_link].sh_offset; symstrsize = shdr[shdr[i].sh_link].sh_size; break; } } /* Check for files too large to mmap. */ if (symstrsize > SIZE_T_MAX) { errno = EFBIG; goto done; } /* * Map string table into our address space. This gives us * an easy way to randomly access all the strings, without * making the memory allocation permanent as with malloc/free * (i.e., munmap will return it to the system). */ base = mmap(NULL, (size_t)symstrsize, PROT_READ, MAP_PRIVATE, fd, (off_t)symstroff); if (base == MAP_FAILED) goto done; strtab = (char *)base; /* * clean out any left-over information for all valid entries. * Type and value defined to be 0 if not found; historical * versions cleared other and desc as well. Also figure out * the largest string length so don't read any more of the * string table than we have to. * * XXX clearing anything other than n_type and n_value violates * the semantics given in the man page. */ nent = 0; for (p = list; !ISLAST(p); ++p) { p->n_type = 0; p->n_other = 0; p->n_desc = 0; p->n_value = 0; ++nent; } /* Don't process any further if object is stripped. */ if (symoff == 0) goto done; if (lseek(fd, (off_t) symoff, SEEK_SET) == -1) { nent = -1; goto done; } while (symsize > 0 && nent > 0) { cc = MIN(symsize, sizeof(sbuf)); if (_read(fd, sbuf, cc) != cc) break; symsize -= cc; for (s = sbuf; cc > 0 && nent > 0; ++s, cc -= sizeof(*s)) { char *name; struct nlist *p; name = strtab + s->st_name; if (name[0] == '\0') continue; for (p = list; !ISLAST(p); p++) { if ((p->n_un.n_name[0] == '_' && strcmp(name, p->n_un.n_name+1) == 0) || strcmp(name, p->n_un.n_name) == 0) { elf_sym_to_nlist(p, s, shdr, ehdr.e_shnum); if (--nent <= 0) break; } } } } done: errsave = errno; if (strtab != NULL) munmap(strtab, symstrsize); if (shdr != NULL) munmap(shdr, shdr_size); errno = errsave; return (nent); } /* * Convert an Elf_Sym into an nlist structure. This fills in only the * n_value and n_type members. */ static void -elf_sym_to_nlist(nl, s, shdr, shnum) - struct nlist *nl; - Elf_Sym *s; - Elf_Shdr *shdr; - int shnum; +elf_sym_to_nlist(struct nlist *nl, Elf_Sym *s, Elf_Shdr *shdr, int shnum) { nl->n_value = s->st_value; switch (s->st_shndx) { case SHN_UNDEF: case SHN_COMMON: nl->n_type = N_UNDF; break; case SHN_ABS: nl->n_type = ELF_ST_TYPE(s->st_info) == STT_FILE ? N_FN : N_ABS; break; default: if (s->st_shndx >= shnum) nl->n_type = N_UNDF; else { Elf_Shdr *sh = shdr + s->st_shndx; nl->n_type = sh->sh_type == SHT_PROGBITS ? (sh->sh_flags & SHF_WRITE ? N_DATA : N_TEXT) : (sh->sh_type == SHT_NOBITS ? N_BSS : N_UNDF); } break; } if (ELF_ST_BIND(s->st_info) == STB_GLOBAL || ELF_ST_BIND(s->st_info) == STB_WEAK) nl->n_type |= N_EXT; } #endif /* _NLIST_DO_ELF */ Index: head/lib/libc/gen/strtofflags.c =================================================================== --- head/lib/libc/gen/strtofflags.c (revision 287792) +++ head/lib/libc/gen/strtofflags.c (revision 287793) @@ -1,172 +1,169 @@ /*- * Copyright (c) 1993 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 4. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)stat_flags.c 8.1 (Berkeley) 5/31/93"; #endif /* LIBC_SCCS and not lint */ #include __FBSDID("$FreeBSD$"); #include #include #include #include #include #include #define longestflaglen 12 static struct { char name[longestflaglen + 1]; char invert; u_long flag; } const mapping[] = { /* shorter names per flag first, all prefixed by "no" */ { "nosappnd", 0, SF_APPEND }, { "nosappend", 0, SF_APPEND }, { "noarch", 0, SF_ARCHIVED }, { "noarchived", 0, SF_ARCHIVED }, { "noschg", 0, SF_IMMUTABLE }, { "noschange", 0, SF_IMMUTABLE }, { "nosimmutable", 0, SF_IMMUTABLE }, { "nosunlnk", 0, SF_NOUNLINK }, { "nosunlink", 0, SF_NOUNLINK }, #ifdef SF_SNAPSHOT { "nosnapshot", 0, SF_SNAPSHOT }, #endif { "nouappnd", 0, UF_APPEND }, { "nouappend", 0, UF_APPEND }, { "nouarch", 0, UF_ARCHIVE }, { "nouarchive", 0, UF_ARCHIVE }, { "nohidden", 0, UF_HIDDEN }, { "nouhidden", 0, UF_HIDDEN }, { "nouchg", 0, UF_IMMUTABLE }, { "nouchange", 0, UF_IMMUTABLE }, { "nouimmutable", 0, UF_IMMUTABLE }, { "nodump", 1, UF_NODUMP }, { "nouunlnk", 0, UF_NOUNLINK }, { "nouunlink", 0, UF_NOUNLINK }, { "nooffline", 0, UF_OFFLINE }, { "nouoffline", 0, UF_OFFLINE }, { "noopaque", 0, UF_OPAQUE }, { "nordonly", 0, UF_READONLY }, { "nourdonly", 0, UF_READONLY }, { "noreadonly", 0, UF_READONLY }, { "noureadonly", 0, UF_READONLY }, { "noreparse", 0, UF_REPARSE }, { "noureparse", 0, UF_REPARSE }, { "nosparse", 0, UF_SPARSE }, { "nousparse", 0, UF_SPARSE }, { "nosystem", 0, UF_SYSTEM }, { "nousystem", 0, UF_SYSTEM } }; #define nmappings (sizeof(mapping) / sizeof(mapping[0])) /* * fflagstostr -- * Convert file flags to a comma-separated string. If no flags * are set, return the empty string. */ char * -fflagstostr(flags) - u_long flags; +fflagstostr(u_long flags) { char *string; const char *sp; char *dp; u_long setflags; int i; if ((string = (char *)malloc(nmappings * (longestflaglen + 1))) == NULL) return (NULL); setflags = flags; dp = string; for (i = 0; i < nmappings; i++) { if (setflags & mapping[i].flag) { if (dp > string) *dp++ = ','; for (sp = mapping[i].invert ? mapping[i].name : mapping[i].name + 2; *sp; *dp++ = *sp++) ; setflags &= ~mapping[i].flag; } } *dp = '\0'; return (string); } /* * strtofflags -- * Take string of arguments and return file flags. Return 0 on * success, 1 on failure. On failure, stringp is set to point * to the offending token. */ int -strtofflags(stringp, setp, clrp) - char **stringp; - u_long *setp, *clrp; +strtofflags(char **stringp, u_long *setp, u_long *clrp) { char *string, *p; int i; if (setp) *setp = 0; if (clrp) *clrp = 0; string = *stringp; while ((p = strsep(&string, "\t ,")) != NULL) { *stringp = p; if (*p == '\0') continue; for (i = 0; i < nmappings; i++) { if (strcmp(p, mapping[i].name + 2) == 0) { if (mapping[i].invert) { if (clrp) *clrp |= mapping[i].flag; } else { if (setp) *setp |= mapping[i].flag; } break; } else if (strcmp(p, mapping[i].name) == 0) { if (mapping[i].invert) { if (setp) *setp |= mapping[i].flag; } else { if (clrp) *clrp |= mapping[i].flag; } break; } } if (i == nmappings) return 1; } return 0; } Index: head/lib/libc/gmon/gmon.c =================================================================== --- head/lib/libc/gmon/gmon.c (revision 287792) +++ head/lib/libc/gmon/gmon.c (revision 287793) @@ -1,255 +1,252 @@ /*- * Copyright (c) 1983, 1992, 1993 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 4. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)gmon.c 8.1 (Berkeley) 6/4/93"; #endif #include __FBSDID("$FreeBSD$"); #include "namespace.h" #include #include #include #include #include #include #include #include #include #include #include #include "un-namespace.h" #include "libc_private.h" #if defined(__i386__) || defined(__sparc64__) || defined(__amd64__) || (defined(__powerpc__) && !defined(__powerpc64__)) extern char *minbrk __asm (".minbrk"); #elif defined(__powerpc64__) extern char *minbrk __asm ("_minbrk"); #else extern char *minbrk __asm ("minbrk"); #endif struct gmonparam _gmonparam = { GMON_PROF_OFF }; static int s_scale; /* See profil(2) where this is described (incorrectly). */ #define SCALE_SHIFT 16 #define ERR(s) _write(2, s, sizeof(s)) void moncontrol(int); static int hertz(void); void -monstartup(lowpc, highpc) - u_long lowpc; - u_long highpc; +monstartup(u_long lowpc, u_long highpc) { int o; char *cp; struct gmonparam *p = &_gmonparam; /* * round lowpc and highpc to multiples of the density we're using * so the rest of the scaling (here and in gprof) stays in ints. */ p->lowpc = ROUNDDOWN(lowpc, HISTFRACTION * sizeof(HISTCOUNTER)); p->highpc = ROUNDUP(highpc, HISTFRACTION * sizeof(HISTCOUNTER)); p->textsize = p->highpc - p->lowpc; p->kcountsize = p->textsize / HISTFRACTION; p->hashfraction = HASHFRACTION; p->fromssize = p->textsize / HASHFRACTION; p->tolimit = p->textsize * ARCDENSITY / 100; if (p->tolimit < MINARCS) p->tolimit = MINARCS; else if (p->tolimit > MAXARCS) p->tolimit = MAXARCS; p->tossize = p->tolimit * sizeof(struct tostruct); cp = sbrk(p->kcountsize + p->fromssize + p->tossize); if (cp == (char *)-1) { ERR("monstartup: out of memory\n"); return; } #ifdef notdef bzero(cp, p->kcountsize + p->fromssize + p->tossize); #endif p->tos = (struct tostruct *)cp; cp += p->tossize; p->kcount = (u_short *)cp; cp += p->kcountsize; p->froms = (u_short *)cp; minbrk = sbrk(0); p->tos[0].link = 0; o = p->highpc - p->lowpc; s_scale = (p->kcountsize < o) ? ((uintmax_t)p->kcountsize << SCALE_SHIFT) / o : (1 << SCALE_SHIFT); moncontrol(1); } void _mcleanup(void) { int fd; int fromindex; int endfrom; u_long frompc; int toindex; struct rawarc rawarc; struct gmonparam *p = &_gmonparam; struct gmonhdr gmonhdr, *hdr; struct clockinfo clockinfo; char outname[128]; int mib[2]; size_t size; #ifdef DEBUG int log, len; char buf[200]; #endif if (p->state == GMON_PROF_ERROR) ERR("_mcleanup: tos overflow\n"); size = sizeof(clockinfo); mib[0] = CTL_KERN; mib[1] = KERN_CLOCKRATE; if (sysctl(mib, 2, &clockinfo, &size, NULL, 0) < 0) { /* * Best guess */ clockinfo.profhz = hertz(); } else if (clockinfo.profhz == 0) { if (clockinfo.hz != 0) clockinfo.profhz = clockinfo.hz; else clockinfo.profhz = hertz(); } moncontrol(0); if (getenv("PROFIL_USE_PID")) snprintf(outname, sizeof(outname), "%s.%d.gmon", _getprogname(), getpid()); else snprintf(outname, sizeof(outname), "%s.gmon", _getprogname()); fd = _open(outname, O_CREAT|O_TRUNC|O_WRONLY|O_CLOEXEC, 0666); if (fd < 0) { _warn("_mcleanup: %s", outname); return; } #ifdef DEBUG log = _open("gmon.log", O_CREAT|O_TRUNC|O_WRONLY|O_CLOEXEC, 0664); if (log < 0) { _warn("_mcleanup: gmon.log"); return; } len = sprintf(buf, "[mcleanup1] kcount 0x%p ssiz %lu\n", p->kcount, p->kcountsize); _write(log, buf, len); #endif hdr = (struct gmonhdr *)&gmonhdr; bzero(hdr, sizeof(*hdr)); hdr->lpc = p->lowpc; hdr->hpc = p->highpc; hdr->ncnt = p->kcountsize + sizeof(gmonhdr); hdr->version = GMONVERSION; hdr->profrate = clockinfo.profhz; _write(fd, (char *)hdr, sizeof *hdr); _write(fd, p->kcount, p->kcountsize); endfrom = p->fromssize / sizeof(*p->froms); for (fromindex = 0; fromindex < endfrom; fromindex++) { if (p->froms[fromindex] == 0) continue; frompc = p->lowpc; frompc += fromindex * p->hashfraction * sizeof(*p->froms); for (toindex = p->froms[fromindex]; toindex != 0; toindex = p->tos[toindex].link) { #ifdef DEBUG len = sprintf(buf, "[mcleanup2] frompc 0x%lx selfpc 0x%lx count %lu\n" , frompc, p->tos[toindex].selfpc, p->tos[toindex].count); _write(log, buf, len); #endif rawarc.raw_frompc = frompc; rawarc.raw_selfpc = p->tos[toindex].selfpc; rawarc.raw_count = p->tos[toindex].count; _write(fd, &rawarc, sizeof rawarc); } } _close(fd); } /* * Control profiling * profiling is what mcount checks to see if * all the data structures are ready. */ void -moncontrol(mode) - int mode; +moncontrol(int mode) { struct gmonparam *p = &_gmonparam; if (mode) { /* start */ profil((char *)p->kcount, p->kcountsize, p->lowpc, s_scale); p->state = GMON_PROF_ON; } else { /* stop */ profil((char *)0, 0, 0, 0); p->state = GMON_PROF_OFF; } } /* * discover the tick frequency of the machine * if something goes wrong, we return 0, an impossible hertz. */ static int -hertz() +hertz(void) { struct itimerval tim; tim.it_interval.tv_sec = 0; tim.it_interval.tv_usec = 1; tim.it_value.tv_sec = 0; tim.it_value.tv_usec = 0; setitimer(ITIMER_REAL, &tim, 0); setitimer(ITIMER_REAL, 0, &tim); if (tim.it_interval.tv_usec < 2) return(0); return (1000000 / tim.it_interval.tv_usec); } Index: head/lib/libc/stdlib/heapsort.c =================================================================== --- head/lib/libc/stdlib/heapsort.c (revision 287792) +++ head/lib/libc/stdlib/heapsort.c (revision 287793) @@ -1,199 +1,194 @@ /*- * Copyright (c) 1991, 1993 * The Regents of the University of California. All rights reserved. * Copyright (c) 2014 David T. Chisnall * All rights reserved. * * This code is derived from software contributed to Berkeley by * Ronnie Kon at Mindcraft Inc., Kevin Lew and Elmer Yglesias. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)heapsort.c 8.1 (Berkeley) 6/4/93"; #endif /* LIBC_SCCS and not lint */ #include __FBSDID("$FreeBSD$"); #include #include #include #ifdef I_AM_HEAPSORT_B #include "block_abi.h" #define COMPAR(x, y) CALL_BLOCK(compar, x, y) typedef DECLARE_BLOCK(int, heapsort_block, const void *, const void *); #else #define COMPAR(x, y) compar(x, y) #endif /* * Swap two areas of size number of bytes. Although qsort(3) permits random * blocks of memory to be sorted, sorting pointers is almost certainly the * common case (and, were it not, could easily be made so). Regardless, it * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer * arithmetic gets lost in the time required for comparison function calls. */ #define SWAP(a, b, count, size, tmp) { \ count = size; \ do { \ tmp = *a; \ *a++ = *b; \ *b++ = tmp; \ } while (--count); \ } /* Copy one block of size size to another. */ #define COPY(a, b, count, size, tmp1, tmp2) { \ count = size; \ tmp1 = a; \ tmp2 = b; \ do { \ *tmp1++ = *tmp2++; \ } while (--count); \ } /* * Build the list into a heap, where a heap is defined such that for * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N. * * There two cases. If j == nmemb, select largest of Ki and Kj. If * j < nmemb, select largest of Ki, Kj and Kj+1. */ #define CREATE(initval, nmemb, par_i, child_i, par, child, size, count, tmp) { \ for (par_i = initval; (child_i = par_i * 2) <= nmemb; \ par_i = child_i) { \ child = base + child_i * size; \ if (child_i < nmemb && COMPAR(child, child + size) < 0) { \ child += size; \ ++child_i; \ } \ par = base + par_i * size; \ if (COMPAR(child, par) <= 0) \ break; \ SWAP(par, child, count, size, tmp); \ } \ } /* * Select the top of the heap and 'heapify'. Since by far the most expensive * action is the call to the compar function, a considerable optimization * in the average case can be achieved due to the fact that k, the displaced * elememt, is ususally quite small, so it would be preferable to first * heapify, always maintaining the invariant that the larger child is copied * over its parent's record. * * Then, starting from the *bottom* of the heap, finding k's correct place, * again maintianing the invariant. As a result of the invariant no element * is 'lost' when k is assigned its correct place in the heap. * * The time savings from this optimization are on the order of 15-20% for the * average case. See Knuth, Vol. 3, page 158, problem 18. * * XXX Don't break the #define SELECT line, below. Reiser cpp gets upset. */ #define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) { \ for (par_i = 1; (child_i = par_i * 2) <= nmemb; par_i = child_i) { \ child = base + child_i * size; \ if (child_i < nmemb && COMPAR(child, child + size) < 0) { \ child += size; \ ++child_i; \ } \ par = base + par_i * size; \ COPY(par, child, count, size, tmp1, tmp2); \ } \ for (;;) { \ child_i = par_i; \ par_i = child_i / 2; \ child = base + child_i * size; \ par = base + par_i * size; \ if (child_i == 1 || COMPAR(k, par) < 0) { \ COPY(child, k, count, size, tmp1, tmp2); \ break; \ } \ COPY(child, par, count, size, tmp1, tmp2); \ } \ } /* * Heapsort -- Knuth, Vol. 3, page 145. Runs in O (N lg N), both average * and worst. While heapsort is faster than the worst case of quicksort, * the BSD quicksort does median selection so that the chance of finding * a data set that will trigger the worst case is nonexistent. Heapsort's * only advantage over quicksort is that it requires little additional memory. */ #ifdef I_AM_HEAPSORT_B int -heapsort_b(vbase, nmemb, size, compar) - void *vbase; - size_t nmemb, size; - heapsort_block compar; +heapsort_b(void *vbase, size_t nmemb, size_t size, heapsort_block compar) #else int -heapsort(vbase, nmemb, size, compar) - void *vbase; - size_t nmemb, size; - int (*compar)(const void *, const void *); +heapsort(void *vbase, size_t nmemb, size_t size, + int (*compar)(const void *, const void *)) #endif { size_t cnt, i, j, l; char tmp, *tmp1, *tmp2; char *base, *k, *p, *t; if (nmemb <= 1) return (0); if (!size) { errno = EINVAL; return (-1); } if ((k = malloc(size)) == NULL) return (-1); /* * Items are numbered from 1 to nmemb, so offset from size bytes * below the starting address. */ base = (char *)vbase - size; for (l = nmemb / 2 + 1; --l;) CREATE(l, nmemb, i, j, t, p, size, cnt, tmp); /* * For each element of the heap, save the largest element into its * final slot, save the displaced element (k), then recreate the * heap. */ while (nmemb > 1) { COPY(k, base + nmemb * size, cnt, size, tmp1, tmp2); COPY(base + nmemb * size, base + size, cnt, size, tmp1, tmp2); --nmemb; SELECT(i, j, nmemb, t, p, size, k, cnt, tmp1, tmp2); } free(k); return (0); } Index: head/lib/libc/stdlib/merge.c =================================================================== --- head/lib/libc/stdlib/merge.c (revision 287792) +++ head/lib/libc/stdlib/merge.c (revision 287793) @@ -1,363 +1,353 @@ /*- * Copyright (c) 1992, 1993 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by * Peter McIlroy. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)merge.c 8.2 (Berkeley) 2/14/94"; #endif /* LIBC_SCCS and not lint */ #include __FBSDID("$FreeBSD$"); /* * Hybrid exponential search/linear search merge sort with hybrid * natural/pairwise first pass. Requires about .3% more comparisons * for random data than LSMS with pairwise first pass alone. * It works for objects as small as two bytes. */ #define NATURAL #define THRESHOLD 16 /* Best choice for natural merge cut-off. */ /* #define NATURAL to get hybrid natural merge. * (The default is pairwise merging.) */ #include #include #include #include #ifdef I_AM_MERGESORT_B #include "block_abi.h" #define DECLARE_CMP DECLARE_BLOCK(int, cmp, const void *, const void *) typedef DECLARE_BLOCK(int, cmp_t, const void *, const void *); #define CMP(x, y) CALL_BLOCK(cmp, x, y) #else typedef int (*cmp_t)(const void *, const void *); #define CMP(x, y) cmp(x, y) #endif static void setup(u_char *, u_char *, size_t, size_t, cmp_t); static void insertionsort(u_char *, size_t, size_t, cmp_t); #define ISIZE sizeof(int) #define PSIZE sizeof(u_char *) #define ICOPY_LIST(src, dst, last) \ do \ *(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE; \ while(src < last) #define ICOPY_ELT(src, dst, i) \ do \ *(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE; \ while (i -= ISIZE) #define CCOPY_LIST(src, dst, last) \ do \ *dst++ = *src++; \ while (src < last) #define CCOPY_ELT(src, dst, i) \ do \ *dst++ = *src++; \ while (i -= 1) /* * Find the next possible pointer head. (Trickery for forcing an array * to do double duty as a linked list when objects do not align with word * boundaries. */ /* Assumption: PSIZE is a power of 2. */ #define EVAL(p) (u_char **) \ ((u_char *)0 + \ (((u_char *)p + PSIZE - 1 - (u_char *) 0) & ~(PSIZE - 1))) /* * Arguments are as for qsort. */ int #ifdef I_AM_MERGESORT_B -mergesort_b(base, nmemb, size, cmp) +mergesort_b(void *base, size_t nmemb, size_t size, cmp_t cmp) #else -mergesort(base, nmemb, size, cmp) +mergesort(void *base, size_t nmemb, size_t size, cmp_t cmp) #endif - void *base; - size_t nmemb; - size_t size; - cmp_t cmp; { size_t i; int sense; int big, iflag; u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2; u_char *list2, *list1, *p2, *p, *last, **p1; if (size < PSIZE / 2) { /* Pointers must fit into 2 * size. */ errno = EINVAL; return (-1); } if (nmemb == 0) return (0); /* * XXX * Stupid subtraction for the Cray. */ iflag = 0; if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE)) iflag = 1; if ((list2 = malloc(nmemb * size + PSIZE)) == NULL) return (-1); list1 = base; setup(list1, list2, nmemb, size, cmp); last = list2 + nmemb * size; i = big = 0; while (*EVAL(list2) != last) { l2 = list1; p1 = EVAL(list1); for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) { p2 = *EVAL(p2); f1 = l2; f2 = l1 = list1 + (p2 - list2); if (p2 != last) p2 = *EVAL(p2); l2 = list1 + (p2 - list2); while (f1 < l1 && f2 < l2) { if (CMP(f1, f2) <= 0) { q = f2; b = f1, t = l1; sense = -1; } else { q = f1; b = f2, t = l2; sense = 0; } if (!big) { /* here i = 0 */ while ((b += size) < t && CMP(q, b) >sense) if (++i == 6) { big = 1; goto EXPONENTIAL; } } else { EXPONENTIAL: for (i = size; ; i <<= 1) if ((p = (b + i)) >= t) { if ((p = t - size) > b && CMP(q, p) <= sense) t = p; else b = p; break; } else if (CMP(q, p) <= sense) { t = p; if (i == size) big = 0; goto FASTCASE; } else b = p; while (t > b+size) { i = (((t - b) / size) >> 1) * size; if (CMP(q, p = b + i) <= sense) t = p; else b = p; } goto COPY; FASTCASE: while (i > size) if (CMP(q, p = b + (i >>= 1)) <= sense) t = p; else b = p; COPY: b = t; } i = size; if (q == f1) { if (iflag) { ICOPY_LIST(f2, tp2, b); ICOPY_ELT(f1, tp2, i); } else { CCOPY_LIST(f2, tp2, b); CCOPY_ELT(f1, tp2, i); } } else { if (iflag) { ICOPY_LIST(f1, tp2, b); ICOPY_ELT(f2, tp2, i); } else { CCOPY_LIST(f1, tp2, b); CCOPY_ELT(f2, tp2, i); } } } if (f2 < l2) { if (iflag) ICOPY_LIST(f2, tp2, l2); else CCOPY_LIST(f2, tp2, l2); } else if (f1 < l1) { if (iflag) ICOPY_LIST(f1, tp2, l1); else CCOPY_LIST(f1, tp2, l1); } *p1 = l2; } tp2 = list1; /* swap list1, list2 */ list1 = list2; list2 = tp2; last = list2 + nmemb*size; } if (base == list2) { memmove(list2, list1, nmemb*size); list2 = list1; } free(list2); return (0); } #define swap(a, b) { \ s = b; \ i = size; \ do { \ tmp = *a; *a++ = *s; *s++ = tmp; \ } while (--i); \ a -= size; \ } #define reverse(bot, top) { \ s = top; \ do { \ i = size; \ do { \ tmp = *bot; *bot++ = *s; *s++ = tmp; \ } while (--i); \ s -= size2; \ } while(bot < s); \ } /* * Optional hybrid natural/pairwise first pass. Eats up list1 in runs of * increasing order, list2 in a corresponding linked list. Checks for runs * when THRESHOLD/2 pairs compare with same sense. (Only used when NATURAL * is defined. Otherwise simple pairwise merging is used.) */ void -setup(list1, list2, n, size, cmp) - size_t n, size; - u_char *list1, *list2; - cmp_t cmp; +setup(u_char *list1, u_char *list2, size_t n, size_t size, cmp_t cmp) { int i, length, size2, tmp, sense; u_char *f1, *f2, *s, *l2, *last, *p2; size2 = size*2; if (n <= 5) { insertionsort(list1, n, size, cmp); *EVAL(list2) = (u_char*) list2 + n*size; return; } /* * Avoid running pointers out of bounds; limit n to evens * for simplicity. */ i = 4 + (n & 1); insertionsort(list1 + (n - i) * size, i, size, cmp); last = list1 + size * (n - i); *EVAL(list2 + (last - list1)) = list2 + n * size; #ifdef NATURAL p2 = list2; f1 = list1; sense = (CMP(f1, f1 + size) > 0); for (; f1 < last; sense = !sense) { length = 2; /* Find pairs with same sense. */ for (f2 = f1 + size2; f2 < last; f2 += size2) { if ((CMP(f2, f2+ size) > 0) != sense) break; length += 2; } if (length < THRESHOLD) { /* Pairwise merge */ do { p2 = *EVAL(p2) = f1 + size2 - list1 + list2; if (sense > 0) swap (f1, f1 + size); } while ((f1 += size2) < f2); } else { /* Natural merge */ l2 = f2; for (f2 = f1 + size2; f2 < l2; f2 += size2) { if ((CMP(f2-size, f2) > 0) != sense) { p2 = *EVAL(p2) = f2 - list1 + list2; if (sense > 0) reverse(f1, f2-size); f1 = f2; } } if (sense > 0) reverse (f1, f2-size); f1 = f2; if (f2 < last || CMP(f2 - size, f2) > 0) p2 = *EVAL(p2) = f2 - list1 + list2; else p2 = *EVAL(p2) = list2 + n*size; } } #else /* pairwise merge only. */ for (f1 = list1, p2 = list2; f1 < last; f1 += size2) { p2 = *EVAL(p2) = p2 + size2; if (CMP (f1, f1 + size) > 0) swap(f1, f1 + size); } #endif /* NATURAL */ } /* * This is to avoid out-of-bounds addresses in sorting the * last 4 elements. */ static void -insertionsort(a, n, size, cmp) - u_char *a; - size_t n, size; - cmp_t cmp; +insertionsort(u_char *a, size_t n, size_t size, cmp_t cmp) { u_char *ai, *s, *t, *u, tmp; int i; for (ai = a+size; --n >= 1; ai += size) for (t = ai; t > a; t -= size) { u = t - size; if (CMP(u, t) <= 0) break; swap(u, t); } } Index: head/lib/libc/stdlib/radixsort.c =================================================================== --- head/lib/libc/stdlib/radixsort.c (revision 287792) +++ head/lib/libc/stdlib/radixsort.c (revision 287793) @@ -1,327 +1,311 @@ /*- * Copyright (c) 1990, 1993 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by * Peter McIlroy and by Dan Bernstein at New York University, * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)radixsort.c 8.2 (Berkeley) 4/28/95"; #endif /* LIBC_SCCS and not lint */ #include __FBSDID("$FreeBSD$"); /* * Radixsort routines. * * Program r_sort_a() is unstable but uses O(logN) extra memory for a stack. * Use radixsort(a, n, trace, endchar) for this case. * * For stable sorting (using N extra pointers) use sradixsort(), which calls * r_sort_b(). * * For a description of this code, see D. McIlroy, P. McIlroy, K. Bostic, * "Engineering Radix Sort". */ #include #include #include #include typedef struct { const u_char **sa; int sn, si; } stack; static inline void simplesort (const u_char **, int, int, const u_char *, u_int); static void r_sort_a(const u_char **, int, int, const u_char *, u_int); static void r_sort_b(const u_char **, const u_char **, int, int, const u_char *, u_int); #define THRESHOLD 20 /* Divert to simplesort(). */ #define SIZE 512 /* Default stack size. */ #define SETUP { \ if (tab == NULL) { \ tr = tr0; \ for (c = 0; c < endch; c++) \ tr0[c] = c + 1; \ tr0[c] = 0; \ for (c++; c < 256; c++) \ tr0[c] = c; \ endch = 0; \ } else { \ endch = tab[endch]; \ tr = tab; \ if (endch != 0 && endch != 255) { \ errno = EINVAL; \ return (-1); \ } \ } \ } int -radixsort(a, n, tab, endch) - const u_char **a, *tab; - int n; - u_int endch; +radixsort(const u_char **a, int n, const u_char *tab, u_int endch) { const u_char *tr; int c; u_char tr0[256]; SETUP; r_sort_a(a, n, 0, tr, endch); return (0); } int -sradixsort(a, n, tab, endch) - const u_char **a, *tab; - int n; - u_int endch; +sradixsort(const u_char **a, int n, const u_char *tab, u_int endch) { const u_char *tr, **ta; int c; u_char tr0[256]; SETUP; if (n < THRESHOLD) simplesort(a, n, 0, tr, endch); else { if ((ta = malloc(n * sizeof(a))) == NULL) return (-1); r_sort_b(a, ta, n, 0, tr, endch); free(ta); } return (0); } #define empty(s) (s >= sp) #define pop(a, n, i) a = (--sp)->sa, n = sp->sn, i = sp->si #define push(a, n, i) sp->sa = a, sp->sn = n, (sp++)->si = i #define swap(a, b, t) t = a, a = b, b = t /* Unstable, in-place sort. */ static void -r_sort_a(a, n, i, tr, endch) - const u_char **a; - int n, i; - const u_char *tr; - u_int endch; +r_sort_a(const u_char **a, int n, int i, const u_char *tr, u_int endch) { static int count[256], nc, bmin; int c; const u_char **ak, *r; stack s[SIZE], *sp, *sp0, *sp1, temp; int *cp, bigc; const u_char **an, *t, **aj, **top[256]; /* Set up stack. */ sp = s; push(a, n, i); while (!empty(s)) { pop(a, n, i); if (n < THRESHOLD) { simplesort(a, n, i, tr, endch); continue; } an = a + n; /* Make character histogram. */ if (nc == 0) { bmin = 255; /* First occupied bin, excluding eos. */ for (ak = a; ak < an;) { c = tr[(*ak++)[i]]; if (++count[c] == 1 && c != endch) { if (c < bmin) bmin = c; nc++; } } if (sp + nc > s + SIZE) { /* Get more stack. */ r_sort_a(a, n, i, tr, endch); continue; } } /* * Special case: if all strings have the same * character at position i, move on to the next * character. */ if (nc == 1 && count[bmin] == n) { push(a, n, i+1); nc = count[bmin] = 0; continue; } /* * Set top[]; push incompletely sorted bins onto stack. * top[] = pointers to last out-of-place element in bins. * count[] = counts of elements in bins. * Before permuting: top[c-1] + count[c] = top[c]; * during deal: top[c] counts down to top[c-1]. */ sp0 = sp1 = sp; /* Stack position of biggest bin. */ bigc = 2; /* Size of biggest bin. */ if (endch == 0) /* Special case: set top[eos]. */ top[0] = ak = a + count[0]; else { ak = a; top[255] = an; } for (cp = count + bmin; nc > 0; cp++) { while (*cp == 0) /* Find next non-empty pile. */ cp++; if (*cp > 1) { if (*cp > bigc) { bigc = *cp; sp1 = sp; } push(ak, *cp, i+1); } top[cp-count] = ak += *cp; nc--; } swap(*sp0, *sp1, temp); /* Play it safe -- biggest bin last. */ /* * Permute misplacements home. Already home: everything * before aj, and in bin[c], items from top[c] on. * Inner loop: * r = next element to put in place; * ak = top[r[i]] = location to put the next element. * aj = bottom of 1st disordered bin. * Outer loop: * Once the 1st disordered bin is done, ie. aj >= ak, * aj<-aj + count[c] connects the bins in a linked list; * reset count[c]. */ for (aj = a; aj < an; *aj = r, aj += count[c], count[c] = 0) for (r = *aj; aj < (ak = --top[c = tr[r[i]]]);) swap(*ak, r, t); } } /* Stable sort, requiring additional memory. */ static void -r_sort_b(a, ta, n, i, tr, endch) - const u_char **a, **ta; - int n, i; - const u_char *tr; - u_int endch; +r_sort_b(const u_char **a, const u_char **ta, int n, int i, const u_char *tr, + u_int endch) { static int count[256], nc, bmin; int c; const u_char **ak, **ai; stack s[512], *sp, *sp0, *sp1, temp; const u_char **top[256]; int *cp, bigc; sp = s; push(a, n, i); while (!empty(s)) { pop(a, n, i); if (n < THRESHOLD) { simplesort(a, n, i, tr, endch); continue; } if (nc == 0) { bmin = 255; for (ak = a + n; --ak >= a;) { c = tr[(*ak)[i]]; if (++count[c] == 1 && c != endch) { if (c < bmin) bmin = c; nc++; } } if (sp + nc > s + SIZE) { r_sort_b(a, ta, n, i, tr, endch); continue; } } sp0 = sp1 = sp; bigc = 2; if (endch == 0) { top[0] = ak = a + count[0]; count[0] = 0; } else { ak = a; top[255] = a + n; count[255] = 0; } for (cp = count + bmin; nc > 0; cp++) { while (*cp == 0) cp++; if ((c = *cp) > 1) { if (c > bigc) { bigc = c; sp1 = sp; } push(ak, c, i+1); } top[cp-count] = ak += c; *cp = 0; /* Reset count[]. */ nc--; } swap(*sp0, *sp1, temp); for (ak = ta + n, ai = a+n; ak > ta;) /* Copy to temp. */ *--ak = *--ai; for (ak = ta+n; --ak >= ta;) /* Deal to piles. */ *--top[tr[(*ak)[i]]] = *ak; } } +/* insertion sort */ static inline void -simplesort(a, n, b, tr, endch) /* insertion sort */ - const u_char **a; - int n, b; - const u_char *tr; - u_int endch; +simplesort(const u_char **a, int n, int b, const u_char *tr, u_int endch) { u_char ch; const u_char **ak, **ai, *s, *t; for (ak = a+1; --n >= 1; ak++) for (ai = ak; ai > a; ai--) { for (s = ai[0] + b, t = ai[-1] + b; (ch = tr[*s]) != endch; s++, t++) if (ch != tr[*t]) break; if (ch >= tr[*t]) break; swap(ai[0], ai[-1], s); } }