/*
- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2003 Apple Computer, Inc. All rights reserved.
*
- * @APPLE_LICENSE_HEADER_START@
+ * @APPLE_LICENSE_OSREFERENCE_HEADER_START@
*
- * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
- *
- * This file contains Original Code and/or Modifications of Original Code
- * as defined in and that are subject to the Apple Public Source License
- * Version 2.0 (the 'License'). You may not use this file except in
- * compliance with the License. Please obtain a copy of the License at
- * http://www.opensource.apple.com/apsl/ and read it before using this
+ * This file contains Original Code and/or Modifications of Original Code
+ * as defined in and that are subject to the Apple Public Source License
+ * Version 2.0 (the 'License'). You may not use this file except in
+ * compliance with the License. The rights granted to you under the
+ * License may not be used to create, or enable the creation or
+ * redistribution of, unlawful or unlicensed copies of an Apple operating
+ * system, or to circumvent, violate, or enable the circumvention or
+ * violation of, any terms of an Apple operating system software license
+ * agreement.
+ *
+ * Please obtain a copy of the License at
+ * http://www.opensource.apple.com/apsl/ and read it before using this
* file.
- *
- * The Original Code and all software distributed under the License are
- * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
- * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
- * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
- * Please see the License for the specific language governing rights and
+ *
+ * The Original Code and all software distributed under the License are
+ * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
+ * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
* limitations under the License.
- *
- * @APPLE_LICENSE_HEADER_END@
+ *
+ * @APPLE_LICENSE_OSREFERENCE_HEADER_END@
*/
/* Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved */
/*
#include <sys/param.h>
#include <sys/systm.h>
#include <sys/time.h>
-#include <sys/mount.h>
-#include <sys/vnode.h>
+#include <sys/mount_internal.h>
+#include <sys/vnode_internal.h>
#include <sys/namei.h>
#include <sys/errno.h>
#include <sys/malloc.h>
+#include <sys/kauth.h>
+#include <sys/user.h>
/*
* Name caching works as follows:
* If it is a "negative" entry, (i.e. for a name that is known NOT to
* exist) the vnode pointer will be NULL.
*
- * For simplicity (and economy of storage), names longer than
- * a maximum length of NCHNAMLEN are not cached; they occur
- * infrequently in any case, and are almost never of interest.
- *
* Upon reaching the last segment of a path, if the reference
* is for DELETE, or NOCACHE is set (rewrite), and the
* name is located in the cache, it will be dropped.
/*
* Structures associated with name cacheing.
*/
-#define NCHHASH(dvp, cnp) \
- (&nchashtbl[((dvp)->v_id + (cnp)->cn_hash) & nchash])
+
LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */
+u_long nchashmask;
u_long nchash; /* size of hash table - 1 */
long numcache; /* number of cache entries allocated */
-TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */
+int desiredNodes;
+int desiredNegNodes;
+TAILQ_HEAD(, namecache) nchead; /* chain of all name cache entries */
+TAILQ_HEAD(, namecache) neghead; /* chain of only negative cache entries */
struct nchstats nchstats; /* cache effectiveness statistics */
-u_long nextvnodeid = 0;
-int doingcache = 1; /* 1 => enable the cache */
+
+/* vars for name cache list lock */
+lck_grp_t * namecache_lck_grp;
+lck_grp_attr_t * namecache_lck_grp_attr;
+lck_attr_t * namecache_lck_attr;
+lck_mtx_t * namecache_mtx_lock;
+
+static vnode_t cache_lookup_locked(vnode_t dvp, struct componentname *cnp);
+static int remove_name_locked(const char *);
+static char *add_name_locked(const char *, size_t, u_int, u_int);
+static void init_string_table(void);
+static void cache_delete(struct namecache *, int);
+static void dump_string_table(void);
+
+static void init_crc32(void);
+static unsigned int crc32tab[256];
+
+
+#define NCHHASH(dvp, hash_val) \
+ (&nchashtbl[(dvp->v_id ^ (hash_val)) & nchashmask])
+
+
+
+//
+// This function builds the path to a filename in "buff". The
+// length of the buffer *INCLUDING* the trailing zero byte is
+// returned in outlen. NOTE: the length includes the trailing
+// zero byte and thus the length is one greater than what strlen
+// would return. This is important and lots of code elsewhere
+// in the kernel assumes this behavior.
+//
+int
+build_path(vnode_t first_vp, char *buff, int buflen, int *outlen)
+{
+ vnode_t vp = first_vp;
+ char *end, *str;
+ int len, ret=0, counter=0;
+
+ end = &buff[buflen-1];
+ *end = '\0';
+
+ /*
+ * if this is the root dir of a file system...
+ */
+ if (vp && (vp->v_flag & VROOT) && vp->v_mount) {
+ /*
+ * then if it's the root fs, just put in a '/' and get out of here
+ */
+ if (vp->v_mount->mnt_flag & MNT_ROOTFS) {
+ *--end = '/';
+ goto out;
+ } else {
+ /*
+ * else just use the covered vnode to get the mount path
+ */
+ vp = vp->v_mount->mnt_vnodecovered;
+ }
+ }
+ name_cache_lock();
+
+ while (vp && vp->v_parent != vp) {
+ /*
+ * the maximum depth of a file system hierarchy is MAXPATHLEN/2
+ * (with single-char names separated by slashes). we panic if
+ * we've ever looped more than that.
+ */
+ if (counter++ > MAXPATHLEN/2) {
+ panic("build_path: vnode parent chain is too long! vp 0x%x\n", vp);
+ }
+ str = vp->v_name;
+
+ if (str == NULL) {
+ if (vp->v_parent != NULL) {
+ ret = EINVAL;
+ }
+ break;
+ }
+ len = strlen(str);
+
+ /*
+ * check that there's enough space (make sure to include space for the '/')
+ */
+ if ((end - buff) < (len + 1)) {
+ ret = ENOSPC;
+ break;
+ }
+ /*
+ * copy it backwards
+ */
+ str += len;
+
+ for (; len > 0; len--) {
+ *--end = *--str;
+ }
+ /*
+ * put in the path separator
+ */
+ *--end = '/';
+
+ /*
+ * walk up the chain (as long as we're not the root)
+ */
+ if (vp == first_vp && (vp->v_flag & VROOT)) {
+ if (vp->v_mount && vp->v_mount->mnt_vnodecovered) {
+ vp = vp->v_mount->mnt_vnodecovered->v_parent;
+ } else {
+ vp = NULLVP;
+ }
+ } else {
+ vp = vp->v_parent;
+ }
+ /*
+ * check if we're crossing a mount point and
+ * switch the vp if we are.
+ */
+ if (vp && (vp->v_flag & VROOT) && vp->v_mount) {
+ vp = vp->v_mount->mnt_vnodecovered;
+ }
+ }
+ name_cache_unlock();
+out:
+ /*
+ * slide it down to the beginning of the buffer
+ */
+ memmove(buff, end, &buff[buflen] - end);
+
+ *outlen = &buff[buflen] - end; // length includes the trailing zero byte
+
+ return ret;
+}
+
/*
- * Delete an entry from its hash list and move it to the front
- * of the LRU list for immediate reuse.
+ * return NULLVP if vp's parent doesn't
+ * exist, or we can't get a valid iocount
+ * else return the parent of vp
*/
-#if DIAGNOSTIC
-#define PURGE(ncp) { \
- if (ncp->nc_hash.le_prev == 0) \
- panic("namecache purge le_prev"); \
- if (ncp->nc_hash.le_next == ncp) \
- panic("namecache purge le_next"); \
- LIST_REMOVE(ncp, nc_hash); \
- ncp->nc_hash.le_prev = 0; \
- TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
- TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); \
+vnode_t
+vnode_getparent(vnode_t vp)
+{
+ vnode_t pvp = NULLVP;
+ int pvid;
+
+ name_cache_lock();
+ /*
+ * v_parent is stable behind the name_cache lock
+ * however, the only thing we can really guarantee
+ * is that we've grabbed a valid iocount on the
+ * parent of 'vp' at the time we took the name_cache lock...
+ * once we drop the lock, vp could get re-parented
+ */
+ if ( (pvp = vp->v_parent) != NULLVP ) {
+ pvid = pvp->v_id;
+
+ name_cache_unlock();
+
+ if (vnode_getwithvid(pvp, pvid) != 0)
+ pvp = NULL;
+ } else
+ name_cache_unlock();
+
+ return (pvp);
+}
+
+char *
+vnode_getname(vnode_t vp)
+{
+ char *name = NULL;
+
+ name_cache_lock();
+
+ if (vp->v_name)
+ name = add_name_locked(vp->v_name, strlen(vp->v_name), 0, 0);
+ name_cache_unlock();
+
+ return (name);
}
-#else
-#define PURGE(ncp) { \
- LIST_REMOVE(ncp, nc_hash); \
- ncp->nc_hash.le_prev = 0; \
- TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
- TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); \
+
+void
+vnode_putname(char *name)
+{
+ name_cache_lock();
+
+ remove_name_locked(name);
+
+ name_cache_unlock();
+}
+
+
+/*
+ * if VNODE_UPDATE_PARENT, and we can take
+ * a reference on dvp, then update vp with
+ * it's new parent... if vp already has a parent,
+ * then drop the reference vp held on it
+ *
+ * if VNODE_UPDATE_NAME,
+ * then drop string ref on v_name if it exists, and if name is non-NULL
+ * then pick up a string reference on name and record it in v_name...
+ * optionally pass in the length and hashval of name if known
+ *
+ * if VNODE_UPDATE_CACHE, flush the name cache entries associated with vp
+ */
+void
+vnode_update_identity(vnode_t vp, vnode_t dvp, char *name, int name_len, int name_hashval, int flags)
+{
+ struct namecache *ncp;
+ vnode_t old_parentvp = NULLVP;
+
+
+ if (flags & VNODE_UPDATE_PARENT) {
+ if (dvp && vnode_ref(dvp) != 0)
+ dvp = NULLVP;
+ } else
+ dvp = NULLVP;
+ name_cache_lock();
+
+ if ( (flags & VNODE_UPDATE_NAME) && (name != vp->v_name) ) {
+ if (vp->v_name != NULL) {
+ remove_name_locked(vp->v_name);
+ vp->v_name = NULL;
+ }
+ if (name && *name) {
+ if (name_len == 0)
+ name_len = strlen(name);
+ vp->v_name = add_name_locked(name, name_len, name_hashval, 0);
+ }
+ }
+ if (flags & VNODE_UPDATE_PARENT) {
+ if (dvp != vp && dvp != vp->v_parent) {
+ old_parentvp = vp->v_parent;
+ vp->v_parent = dvp;
+ dvp = NULLVP;
+
+ if (old_parentvp)
+ flags |= VNODE_UPDATE_CACHE;
+ }
+ }
+ if (flags & VNODE_UPDATE_CACHE) {
+ while ( (ncp = LIST_FIRST(&vp->v_nclinks)) )
+ cache_delete(ncp, 1);
+ }
+ name_cache_unlock();
+
+ if (dvp != NULLVP)
+ vnode_rele(dvp);
+
+ if (old_parentvp) {
+ struct uthread *ut;
+
+ ut = get_bsdthread_info(current_thread());
+
+ /*
+ * indicated to vnode_rele that it shouldn't do a
+ * vnode_reclaim at this time... instead it will
+ * chain the vnode to the uu_vreclaims list...
+ * we'll be responsible for calling vnode_reclaim
+ * on each of the vnodes in this list...
+ */
+ ut->uu_defer_reclaims = 1;
+ ut->uu_vreclaims = NULLVP;
+
+ while ( (vp = old_parentvp) != NULLVP ) {
+
+ vnode_lock(vp);
+
+ vnode_rele_internal(vp, 0, 0, 1);
+
+ /*
+ * check to see if the vnode is now in the state
+ * that would have triggered a vnode_reclaim in vnode_rele
+ * if it is, we save it's parent pointer and then NULL
+ * out the v_parent field... we'll drop the reference
+ * that was held on the next iteration of this loop...
+ * this short circuits a potential deep recursion if we
+ * have a long chain of parents in this state...
+ * we'll sit in this loop until we run into
+ * a parent in this chain that is not in this state
+ *
+ * make our check and the node_rele atomic
+ * with respect to the current vnode we're working on
+ * by holding the vnode lock
+ * if vnode_rele deferred the vnode_reclaim and has put
+ * this vnode on the list to be reaped by us, than
+ * it has left this vnode with an iocount == 1
+ */
+ if ( (vp->v_iocount == 1) && (vp->v_usecount == 0) &&
+ ((vp->v_lflag & (VL_MARKTERM | VL_TERMINATE | VL_DEAD)) == VL_MARKTERM)) {
+ /*
+ * vnode_rele wanted to do a vnode_reclaim on this vnode
+ * it should be sitting on the head of the uu_vreclaims chain
+ * pull the parent pointer now so that when we do the
+ * vnode_reclaim for each of the vnodes in the uu_vreclaims
+ * list, we won't recurse back through here
+ */
+ name_cache_lock();
+ old_parentvp = vp->v_parent;
+ vp->v_parent = NULLVP;
+ name_cache_unlock();
+ } else {
+ /*
+ * we're done... we ran into a vnode that isn't
+ * being terminated
+ */
+ old_parentvp = NULLVP;
+ }
+ vnode_unlock(vp);
+ }
+ ut->uu_defer_reclaims = 0;
+
+ while ( (vp = ut->uu_vreclaims) != NULLVP) {
+ ut->uu_vreclaims = vp->v_defer_reclaimlist;
+
+ /*
+ * vnode_put will drive the vnode_reclaim if
+ * we are still the only reference on this vnode
+ */
+ vnode_put(vp);
+ }
+ }
}
-#endif /* DIAGNOSTIC */
+
/*
- * Move an entry that has been used to the tail of the LRU list
- * so that it will be preserved for future use.
+ * Mark a vnode as having multiple hard links. HFS makes use of this
+ * because it keeps track of each link separately, and wants to know
+ * which link was actually used.
+ *
+ * This will cause the name cache to force a VNOP_LOOKUP on the vnode
+ * so that HFS can post-process the lookup. Also, volfs will call
+ * VNOP_GETATTR2 to determine the parent, instead of using v_parent.
*/
-#define TOUCH(ncp) { \
- if (ncp->nc_lru.tqe_next != 0) { \
- TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
- TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); \
- } \
+void vnode_set_hard_link(vnode_t vp)
+{
+ vnode_lock(vp);
+
+ /*
+ * In theory, we're changing the vnode's identity as far as the
+ * name cache is concerned, so we ought to grab the name cache lock
+ * here. However, there is already a race, and grabbing the name
+ * cache lock only makes the race window slightly smaller.
+ *
+ * The race happens because the vnode already exists in the name
+ * cache, and could be found by one thread before another thread
+ * can set the hard link flag.
+ */
+
+ vp->v_flag |= VISHARDLINK;
+
+ vnode_unlock(vp);
+}
+
+
+void vnode_uncache_credentials(vnode_t vp)
+{
+ kauth_cred_t ucred = NULL;
+
+ if (vp->v_cred) {
+ vnode_lock(vp);
+
+ ucred = vp->v_cred;
+ vp->v_cred = NULL;
+
+ vnode_unlock(vp);
+
+ if (ucred)
+ kauth_cred_rele(ucred);
+ }
+}
+
+
+void vnode_cache_credentials(vnode_t vp, vfs_context_t context)
+{
+ kauth_cred_t ucred;
+ kauth_cred_t tcred = NOCRED;
+ struct timeval tv;
+
+ ucred = vfs_context_ucred(context);
+
+ if (vp->v_cred != ucred || (vp->v_mount->mnt_kern_flag & MNTK_AUTH_OPAQUE)) {
+ vnode_lock(vp);
+
+ microuptime(&tv);
+ vp->v_cred_timestamp = tv.tv_sec;
+
+ if (vp->v_cred != ucred) {
+ kauth_cred_ref(ucred);
+
+ tcred = vp->v_cred;
+ vp->v_cred = ucred;
+ }
+ vnode_unlock(vp);
+
+ if (tcred)
+ kauth_cred_rele(tcred);
+ }
+}
+
+/* reverse_lookup - lookup by walking back up the parent chain while leveraging
+ * use of the name cache lock in order to protect our starting vnode.
+ * NOTE - assumes you already have search access to starting point.
+ * returns 0 when we have reached the root, current working dir, or chroot root
+ *
+ */
+int
+reverse_lookup(vnode_t start_vp, vnode_t *lookup_vpp, struct filedesc *fdp, vfs_context_t context, int *dp_authorized)
+{
+ int vid, done = 0;
+ int auth_opaque = 0;
+ vnode_t dp = start_vp;
+ vnode_t vp = NULLVP;
+ kauth_cred_t ucred;
+ struct timeval tv;
+
+ ucred = vfs_context_ucred(context);
+ *lookup_vpp = start_vp;
+
+ name_cache_lock();
+
+ if ( dp->v_mount && (dp->v_mount->mnt_kern_flag & MNTK_AUTH_OPAQUE) ) {
+ auth_opaque = 1;
+ microuptime(&tv);
+ }
+ for (;;) {
+ *dp_authorized = 0;
+
+ if (auth_opaque && ((tv.tv_sec - dp->v_cred_timestamp) > VCRED_EXPIRED))
+ break;
+ if (dp->v_cred != ucred)
+ break;
+ /*
+ * indicate that we're allowed to traverse this directory...
+ * even if we bail for some reason, this information is valid and is used
+ * to avoid doing a vnode_authorize
+ */
+ *dp_authorized = 1;
+
+ if ((dp->v_flag & VROOT) != 0 || /* Hit "/" */
+ (dp == fdp->fd_cdir) || /* Hit process's working directory */
+ (dp == fdp->fd_rdir)) { /* Hit process chroot()-ed root */
+ done = 1;
+ break;
+ }
+
+ if ( (vp = dp->v_parent) == NULLVP)
+ break;
+
+ dp = vp;
+ *lookup_vpp = dp;
+ } /* for (;;) */
+
+ vid = dp->v_id;
+
+ name_cache_unlock();
+
+ if (done == 0 && dp != start_vp) {
+ if (vnode_getwithvid(dp, vid) != 0) {
+ *lookup_vpp = start_vp;
+ }
+ }
+
+ return((done == 1) ? 0 : -1);
+}
+
+int
+cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp, vfs_context_t context, int *trailing_slash, int *dp_authorized)
+{
+ char *cp; /* pointer into pathname argument */
+ int vid, vvid;
+ int auth_opaque = 0;
+ vnode_t vp = NULLVP;
+ vnode_t tdp = NULLVP;
+ kauth_cred_t ucred;
+ struct timeval tv;
+ unsigned int hash;
+
+ ucred = vfs_context_ucred(context);
+ *trailing_slash = 0;
+
+ name_cache_lock();
+
+
+ if ( dp->v_mount && (dp->v_mount->mnt_kern_flag & MNTK_AUTH_OPAQUE) ) {
+ auth_opaque = 1;
+ microuptime(&tv);
+ }
+ for (;;) {
+ /*
+ * Search a directory.
+ *
+ * The cn_hash value is for use by cache_lookup
+ * The last component of the filename is left accessible via
+ * cnp->cn_nameptr for callers that need the name.
+ */
+ hash = 0;
+ cp = cnp->cn_nameptr;
+
+ while (*cp && (*cp != '/')) {
+ hash ^= crc32tab[((hash >> 24) ^ (unsigned char)*cp++)];
+ }
+ /*
+ * the crc generator can legitimately generate
+ * a 0... however, 0 for us means that we
+ * haven't computed a hash, so use 1 instead
+ */
+ if (hash == 0)
+ hash = 1;
+ cnp->cn_hash = hash;
+ cnp->cn_namelen = cp - cnp->cn_nameptr;
+
+ ndp->ni_pathlen -= cnp->cn_namelen;
+ ndp->ni_next = cp;
+
+ /*
+ * Replace multiple slashes by a single slash and trailing slashes
+ * by a null. This must be done before VNOP_LOOKUP() because some
+ * fs's don't know about trailing slashes. Remember if there were
+ * trailing slashes to handle symlinks, existing non-directories
+ * and non-existing files that won't be directories specially later.
+ */
+ while (*cp == '/' && (cp[1] == '/' || cp[1] == '\0')) {
+ cp++;
+ ndp->ni_pathlen--;
+
+ if (*cp == '\0') {
+ *trailing_slash = 1;
+ *ndp->ni_next = '\0';
+ }
+ }
+ ndp->ni_next = cp;
+
+ cnp->cn_flags &= ~(MAKEENTRY | ISLASTCN | ISDOTDOT);
+
+ if (*cp == '\0')
+ cnp->cn_flags |= ISLASTCN;
+
+ if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.' && cnp->cn_nameptr[0] == '.')
+ cnp->cn_flags |= ISDOTDOT;
+
+ *dp_authorized = 0;
+
+ if (auth_opaque && ((tv.tv_sec - dp->v_cred_timestamp) > VCRED_EXPIRED))
+ break;
+
+ if (dp->v_cred != ucred)
+ break;
+ /*
+ * indicate that we're allowed to traverse this directory...
+ * even if we fail the cache lookup or decide to bail for
+ * some other reason, this information is valid and is used
+ * to avoid doing a vnode_authorize before the call to VNOP_LOOKUP
+ */
+ *dp_authorized = 1;
+
+ if ( (cnp->cn_flags & (ISLASTCN | ISDOTDOT)) ) {
+ if (cnp->cn_nameiop != LOOKUP)
+ break;
+ if (cnp->cn_flags & (LOCKPARENT | NOCACHE))
+ break;
+ if (cnp->cn_flags & ISDOTDOT) {
+ /*
+ * Quit here only if we can't use
+ * the parent directory pointer or
+ * don't have one. Otherwise, we'll
+ * use it below.
+ */
+ if ((dp->v_flag & VROOT) ||
+ dp->v_parent == NULLVP)
+ break;
+ }
+ }
+
+ /*
+ * "." and ".." aren't supposed to be cached, so check
+ * for them before checking the cache.
+ */
+ if (cnp->cn_namelen == 1 && cnp->cn_nameptr[0] == '.')
+ vp = dp;
+ else if (cnp->cn_flags & ISDOTDOT)
+ vp = dp->v_parent;
+ else {
+ if ( (vp = cache_lookup_locked(dp, cnp)) == NULLVP)
+ break;
+ }
+
+ if ( (cnp->cn_flags & ISLASTCN) )
+ break;
+
+ if (vp->v_type != VDIR) {
+ if (vp->v_type != VLNK)
+ vp = NULL;
+ break;
+ }
+ if (vp->v_mountedhere && ((cnp->cn_flags & NOCROSSMOUNT) == 0))
+ break;
+
+ dp = vp;
+ vp = NULLVP;
+
+ cnp->cn_nameptr = ndp->ni_next + 1;
+ ndp->ni_pathlen--;
+ while (*cnp->cn_nameptr == '/') {
+ cnp->cn_nameptr++;
+ ndp->ni_pathlen--;
+ }
+ }
+ if (vp != NULLVP)
+ vvid = vp->v_id;
+ vid = dp->v_id;
+
+ name_cache_unlock();
+
+
+ if ((vp != NULLVP) && (vp->v_type != VLNK) &&
+ ((cnp->cn_flags & (ISLASTCN | LOCKPARENT | WANTPARENT | SAVESTART)) == ISLASTCN)) {
+ /*
+ * if we've got a child and it's the last component, and
+ * the lookup doesn't need to return the parent then we
+ * can skip grabbing an iocount on the parent, since all
+ * we're going to do with it is a vnode_put just before
+ * we return from 'lookup'. If it's a symbolic link,
+ * we need the parent in case the link happens to be
+ * a relative pathname.
+ */
+ tdp = dp;
+ dp = NULLVP;
+ } else {
+need_dp:
+ /*
+ * return the last directory we looked at
+ * with an io reference held
+ */
+ if (dp == ndp->ni_usedvp) {
+ /*
+ * if this vnode matches the one passed in via USEDVP
+ * than this context already holds an io_count... just
+ * use vnode_get to get an extra ref for lookup to play
+ * with... can't use the getwithvid variant here because
+ * it will block behind a vnode_drain which would result
+ * in a deadlock (since we already own an io_count that the
+ * vnode_drain is waiting on)... vnode_get grabs the io_count
+ * immediately w/o waiting... it always succeeds
+ */
+ vnode_get(dp);
+ } else if ( (vnode_getwithvid(dp, vid)) ) {
+ /*
+ * failure indicates the vnode
+ * changed identity or is being
+ * TERMINATED... in either case
+ * punt this lookup
+ */
+ return (ENOENT);
+ }
+ }
+ if (vp != NULLVP) {
+ if ( (vnode_getwithvid(vp, vvid)) ) {
+ vp = NULLVP;
+
+ /*
+ * can't get reference on the vp we'd like
+ * to return... if we didn't grab a reference
+ * on the directory (due to fast path bypass),
+ * then we need to do it now... we can't return
+ * with both ni_dvp and ni_vp NULL, and no
+ * error condition
+ */
+ if (dp == NULLVP) {
+ dp = tdp;
+ goto need_dp;
+ }
+ }
+ }
+ ndp->ni_dvp = dp;
+ ndp->ni_vp = vp;
+
+ return (0);
+}
+
+
+static vnode_t
+cache_lookup_locked(vnode_t dvp, struct componentname *cnp)
+{
+ register struct namecache *ncp;
+ register struct nchashhead *ncpp;
+ register long namelen = cnp->cn_namelen;
+ char *nameptr = cnp->cn_nameptr;
+ unsigned int hashval = (cnp->cn_hash & NCHASHMASK);
+ vnode_t vp;
+
+ ncpp = NCHHASH(dvp, cnp->cn_hash);
+ LIST_FOREACH(ncp, ncpp, nc_hash) {
+ if ((ncp->nc_dvp == dvp) && (ncp->nc_hashval == hashval)) {
+ if (memcmp(ncp->nc_name, nameptr, namelen) == 0 && ncp->nc_name[namelen] == 0)
+ break;
+ }
+ }
+ if (ncp == 0)
+ /*
+ * We failed to find an entry
+ */
+ return (NULL);
+
+ vp = ncp->nc_vp;
+ if (vp && (vp->v_flag & VISHARDLINK)) {
+ /*
+ * The file system wants a VNOP_LOOKUP on this vnode
+ */
+ vp = NULL;
+ }
+
+ return (vp);
+}
+
+
+//
+// Have to take a len argument because we may only need to
+// hash part of a componentname.
+//
+static unsigned int
+hash_string(const char *cp, int len)
+{
+ unsigned hash = 0;
+
+ if (len) {
+ while (len--) {
+ hash ^= crc32tab[((hash >> 24) ^ (unsigned char)*cp++)];
+ }
+ } else {
+ while (*cp != '\0') {
+ hash ^= crc32tab[((hash >> 24) ^ (unsigned char)*cp++)];
+ }
+ }
+ /*
+ * the crc generator can legitimately generate
+ * a 0... however, 0 for us means that we
+ * haven't computed a hash, so use 1 instead
+ */
+ if (hash == 0)
+ hash = 1;
+ return hash;
}
+
/*
* Lookup an entry in the cache
*
struct vnode **vpp;
struct componentname *cnp;
{
- register struct namecache *ncp, *nnp;
+ register struct namecache *ncp;
register struct nchashhead *ncpp;
+ register long namelen = cnp->cn_namelen;
+ char *nameptr = cnp->cn_nameptr;
+ unsigned int hashval = (cnp->cn_hash & NCHASHMASK);
+ uint32_t vid;
+ vnode_t vp;
- if (!doingcache) {
- cnp->cn_flags &= ~MAKEENTRY;
- return (0);
- }
- if (cnp->cn_namelen > NCHNAMLEN) {
- nchstats.ncs_long++;
- cnp->cn_flags &= ~MAKEENTRY;
- return (0);
- }
+ name_cache_lock();
- ncpp = NCHHASH(dvp, cnp);
- for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
- nnp = ncp->nc_hash.le_next;
- /* If one of the vp's went stale, don't bother anymore. */
- if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) ||
- (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id)) {
- nchstats.ncs_falsehits++;
- PURGE(ncp);
- continue;
- }
- /* Now that we know the vp's to be valid, is it ours ? */
- if (ncp->nc_dvp == dvp &&
- ncp->nc_nlen == cnp->cn_namelen &&
- !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
- break;
+ ncpp = NCHHASH(dvp, cnp->cn_hash);
+ LIST_FOREACH(ncp, ncpp, nc_hash) {
+ if ((ncp->nc_dvp == dvp) && (ncp->nc_hashval == hashval)) {
+ if (memcmp(ncp->nc_name, nameptr, namelen) == 0 && ncp->nc_name[namelen] == 0)
+ break;
+ }
}
-
/* We failed to find an entry */
if (ncp == 0) {
nchstats.ncs_miss++;
+ name_cache_unlock();
return (0);
}
/* We don't want to have an entry, so dump it */
if ((cnp->cn_flags & MAKEENTRY) == 0) {
nchstats.ncs_badhits++;
- PURGE(ncp);
+ cache_delete(ncp, 1);
+ name_cache_unlock();
return (0);
}
+ vp = ncp->nc_vp;
/* We found a "positive" match, return the vnode */
- if (ncp->nc_vp) {
+ if (vp) {
nchstats.ncs_goodhits++;
- TOUCH(ncp);
- *vpp = ncp->nc_vp;
+
+ vid = vp->v_id;
+ name_cache_unlock();
+
+ if (vnode_getwithvid(vp, vid)) {
+ name_cache_lock();
+ nchstats.ncs_badvid++;
+ name_cache_unlock();
+ return (0);
+ }
+ *vpp = vp;
return (-1);
}
/* We found a negative match, and want to create it, so purge */
- if (cnp->cn_nameiop == CREATE) {
+ if (cnp->cn_nameiop == CREATE || cnp->cn_nameiop == RENAME) {
nchstats.ncs_badhits++;
- PURGE(ncp);
+ cache_delete(ncp, 1);
+ name_cache_unlock();
return (0);
}
/*
* We found a "negative" match, ENOENT notifies client of this match.
- * The nc_vpid field records whether this is a whiteout.
+ * The nc_whiteout field records whether this is a whiteout.
*/
nchstats.ncs_neghits++;
- TOUCH(ncp);
- cnp->cn_flags |= ncp->nc_vpid;
+
+ if (ncp->nc_whiteout)
+ cnp->cn_flags |= ISWHITEOUT;
+ name_cache_unlock();
return (ENOENT);
}
struct vnode *vp;
struct componentname *cnp;
{
- register struct namecache *ncp;
+ register struct namecache *ncp, *negp;
register struct nchashhead *ncpp;
- if (!doingcache)
- return;
+ if (cnp->cn_hash == 0)
+ cnp->cn_hash = hash_string(cnp->cn_nameptr, cnp->cn_namelen);
- /*
- * If an entry that is too long, is entered, bad things happen.
- * cache_lookup acts as the sentinel to make sure longer names
- * are not stored. This here will prevent outsiders from doing
- * something that is unexpected.
- */
- if (cnp->cn_namelen > NCHNAMLEN)
- panic("cache_enter: name too long");
+ name_cache_lock();
+ /* if the entry is for -ve caching vp is null */
+ if ((vp != NULLVP) && (LIST_FIRST(&vp->v_nclinks))) {
+ /*
+ * someone beat us to the punch..
+ * this vnode is already in the cache
+ */
+ name_cache_unlock();
+ return;
+ }
/*
* We allocate a new entry if we are less than the maximum
- * allowed and the one at the front of the LRU list is in use.
- * Otherwise we use the one at the front of the LRU list.
+ * allowed and the one at the front of the list is in use.
+ * Otherwise we use the one at the front of the list.
*/
- if (numcache < desiredvnodes &&
- ((ncp = nclruhead.tqh_first) == NULL ||
- ncp->nc_hash.le_prev != 0)) {
- /* Add one more entry */
- ncp = (struct namecache *)
- _MALLOC_ZONE((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
+ if (numcache < desiredNodes &&
+ ((ncp = nchead.tqh_first) == NULL ||
+ ncp->nc_hash.le_prev != 0)) {
+ /*
+ * Allocate one more entry
+ */
+ ncp = (struct namecache *)_MALLOC_ZONE((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
numcache++;
- } else if (ncp = nclruhead.tqh_first) {
- /* reuse an old entry */
- TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
+ } else {
+ /*
+ * reuse an old entry
+ */
+ ncp = TAILQ_FIRST(&nchead);
+ TAILQ_REMOVE(&nchead, ncp, nc_entry);
+
if (ncp->nc_hash.le_prev != 0) {
-#if DIAGNOSTIC
- if (ncp->nc_hash.le_next == ncp)
- panic("cache_enter: le_next");
-#endif
- LIST_REMOVE(ncp, nc_hash);
- ncp->nc_hash.le_prev = 0;
+ /*
+ * still in use... we need to
+ * delete it before re-using it
+ */
+ nchstats.ncs_stolen++;
+ cache_delete(ncp, 0);
}
- } else {
- /* give up */
- return;
}
+ nchstats.ncs_enters++;
/*
* Fill in cache info, if vp is NULL this is a "negative" cache entry.
- * For negative entries, we have to record whether it is a whiteout.
- * the whiteout flag is stored in the nc_vpid field which is
- * otherwise unused.
*/
ncp->nc_vp = vp;
- if (vp)
- ncp->nc_vpid = vp->v_id;
- else
- ncp->nc_vpid = cnp->cn_flags & ISWHITEOUT;
ncp->nc_dvp = dvp;
- ncp->nc_dvpid = dvp->v_id;
- ncp->nc_nlen = cnp->cn_namelen;
- bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
- TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
- ncpp = NCHHASH(dvp, cnp);
+ ncp->nc_hashval = cnp->cn_hash;
+ ncp->nc_whiteout = FALSE;
+ ncp->nc_name = add_name_locked(cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_hash, 0);
+
+ /*
+ * make us the newest entry in the cache
+ * i.e. we'll be the last to be stolen
+ */
+ TAILQ_INSERT_TAIL(&nchead, ncp, nc_entry);
+
+ ncpp = NCHHASH(dvp, cnp->cn_hash);
#if DIAGNOSTIC
{
register struct namecache *p;
panic("cache_enter: duplicate");
}
#endif
+ /*
+ * make us available to be found via lookup
+ */
LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
+
+ if (vp) {
+ /*
+ * add to the list of name cache entries
+ * that point at vp
+ */
+ LIST_INSERT_HEAD(&vp->v_nclinks, ncp, nc_un.nc_link);
+ } else {
+ /*
+ * this is a negative cache entry (vp == NULL)
+ * stick it on the negative cache list
+ * and record the whiteout state
+ */
+ TAILQ_INSERT_TAIL(&neghead, ncp, nc_un.nc_negentry);
+
+ if (cnp->cn_flags & ISWHITEOUT)
+ ncp->nc_whiteout = TRUE;
+ nchstats.ncs_negtotal++;
+
+ if (nchstats.ncs_negtotal > desiredNegNodes) {
+ /*
+ * if we've reached our desired limit
+ * of negative cache entries, delete
+ * the oldest
+ */
+ negp = TAILQ_FIRST(&neghead);
+ TAILQ_REMOVE(&neghead, negp, nc_un.nc_negentry);
+
+ cache_delete(negp, 1);
+ }
+ }
+ /*
+ * add us to the list of name cache entries that
+ * are children of dvp
+ */
+ LIST_INSERT_HEAD(&dvp->v_ncchildren, ncp, nc_child);
+
+ name_cache_unlock();
}
+
+/*
+ * Initialize CRC-32 remainder table.
+ */
+static void init_crc32(void)
+{
+ /*
+ * the CRC-32 generator polynomial is:
+ * x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^10
+ * + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
+ */
+ unsigned int crc32_polynomial = 0x04c11db7;
+ unsigned int i,j;
+
+ /*
+ * pre-calculate the CRC-32 remainder for each possible octet encoding
+ */
+ for (i = 0; i < 256; i++) {
+ unsigned int crc_rem = i << 24;
+
+ for (j = 0; j < 8; j++) {
+ if (crc_rem & 0x80000000)
+ crc_rem = (crc_rem << 1) ^ crc32_polynomial;
+ else
+ crc_rem = (crc_rem << 1);
+ }
+ crc32tab[i] = crc_rem;
+ }
+}
+
+
/*
* Name cache initialization, from vfs_init() when we are booting
*/
void
-nchinit()
+nchinit(void)
+{
+ desiredNegNodes = (desiredvnodes / 10);
+ desiredNodes = desiredvnodes + desiredNegNodes;
+
+ TAILQ_INIT(&nchead);
+ TAILQ_INIT(&neghead);
+
+ init_crc32();
+
+ nchashtbl = hashinit(MAX(4096, (2 *desiredNodes)), M_CACHE, &nchash);
+ nchashmask = nchash;
+ nchash++;
+
+ init_string_table();
+
+ /* Allocate mount list lock group attribute and group */
+ namecache_lck_grp_attr= lck_grp_attr_alloc_init();
+ lck_grp_attr_setstat(namecache_lck_grp_attr);
+
+ namecache_lck_grp = lck_grp_alloc_init("Name Cache", namecache_lck_grp_attr);
+
+ /* Allocate mount list lock attribute */
+ namecache_lck_attr = lck_attr_alloc_init();
+ //lck_attr_setdebug(namecache_lck_attr);
+
+ /* Allocate mount list lock */
+ namecache_mtx_lock = lck_mtx_alloc_init(namecache_lck_grp, namecache_lck_attr);
+
+
+}
+
+void
+name_cache_lock(void)
+{
+ lck_mtx_lock(namecache_mtx_lock);
+}
+
+void
+name_cache_unlock(void)
{
+ lck_mtx_unlock(namecache_mtx_lock);
+
+}
+
+
+int
+resize_namecache(u_int newsize)
+{
+ struct nchashhead *new_table;
+ struct nchashhead *old_table;
+ struct nchashhead *old_head, *head;
+ struct namecache *entry, *next;
+ uint32_t i, hashval;
+ int dNodes, dNegNodes;
+ u_long new_size, old_size;
+
+ dNegNodes = (newsize / 10);
+ dNodes = newsize + dNegNodes;
+
+ // we don't support shrinking yet
+ if (dNodes < desiredNodes) {
+ return 0;
+ }
+ new_table = hashinit(2 * dNodes, M_CACHE, &nchashmask);
+ new_size = nchashmask + 1;
+
+ if (new_table == NULL) {
+ return ENOMEM;
+ }
+
+ name_cache_lock();
+ // do the switch!
+ old_table = nchashtbl;
+ nchashtbl = new_table;
+ old_size = nchash;
+ nchash = new_size;
+
+ // walk the old table and insert all the entries into
+ // the new table
+ //
+ for(i=0; i < old_size; i++) {
+ old_head = &old_table[i];
+ for (entry=old_head->lh_first; entry != NULL; entry=next) {
+ //
+ // XXXdbg - Beware: this assumes that hash_string() does
+ // the same thing as what happens in
+ // lookup() over in vfs_lookup.c
+ hashval = hash_string(entry->nc_name, 0);
+ entry->nc_hashval = hashval;
+ head = NCHHASH(entry->nc_dvp, hashval);
+
+ next = entry->nc_hash.le_next;
+ LIST_INSERT_HEAD(head, entry, nc_hash);
+ }
+ }
+ desiredNodes = dNodes;
+ desiredNegNodes = dNegNodes;
+
+ name_cache_unlock();
+ FREE(old_table, M_CACHE);
- TAILQ_INIT(&nclruhead);
- nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash);
+ return 0;
}
+static void
+cache_delete(struct namecache *ncp, int age_entry)
+{
+ nchstats.ncs_deletes++;
+
+ if (ncp->nc_vp) {
+ LIST_REMOVE(ncp, nc_un.nc_link);
+ } else {
+ TAILQ_REMOVE(&neghead, ncp, nc_un.nc_negentry);
+ nchstats.ncs_negtotal--;
+ }
+ LIST_REMOVE(ncp, nc_child);
+
+ LIST_REMOVE(ncp, nc_hash);
+ /*
+ * this field is used to indicate
+ * that the entry is in use and
+ * must be deleted before it can
+ * be reused...
+ */
+ ncp->nc_hash.le_prev = NULL;
+
+ if (age_entry) {
+ /*
+ * make it the next one available
+ * for cache_enter's use
+ */
+ TAILQ_REMOVE(&nchead, ncp, nc_entry);
+ TAILQ_INSERT_HEAD(&nchead, ncp, nc_entry);
+ }
+ remove_name_locked(ncp->nc_name);
+ ncp->nc_name = NULL;
+}
+
+
/*
- * Invalidate a all entries to particular vnode.
- *
- * We actually just increment the v_id, that will do it. The entries will
- * be purged by lookup as they get found. If the v_id wraps around, we
- * need to ditch the entire cache, to avoid confusion. No valid vnode will
- * ever have (v_id == 0).
+ * purge the entry associated with the
+ * specified vnode from the name cache
*/
void
-cache_purge(vp)
- struct vnode *vp;
+cache_purge(vnode_t vp)
+{
+ struct namecache *ncp;
+
+ if ((LIST_FIRST(&vp->v_nclinks) == NULL) && (LIST_FIRST(&vp->v_ncchildren) == NULL))
+ return;
+
+ name_cache_lock();
+
+ while ( (ncp = LIST_FIRST(&vp->v_nclinks)) )
+ cache_delete(ncp, 1);
+
+ while ( (ncp = LIST_FIRST(&vp->v_ncchildren)) )
+ cache_delete(ncp, 1);
+
+ name_cache_unlock();
+}
+
+/*
+ * Purge all negative cache entries that are children of the
+ * given vnode. A case-insensitive file system (or any file
+ * system that has multiple equivalent names for the same
+ * directory entry) can use this when creating or renaming
+ * to remove negative entries that may no longer apply.
+ */
+void
+cache_purge_negatives(vnode_t vp)
{
struct namecache *ncp;
- struct nchashhead *ncpp;
- vp->v_id = ++nextvnodeid;
- if (nextvnodeid != 0)
- return;
- for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
- while (ncp = ncpp->lh_first)
- PURGE(ncp);
- }
- vp->v_id = ++nextvnodeid;
+ name_cache_lock();
+
+ LIST_FOREACH(ncp, &vp->v_ncchildren, nc_child)
+ if (ncp->nc_vp == NULL)
+ cache_delete(ncp , 1);
+
+ name_cache_unlock();
}
/*
* Flush all entries referencing a particular filesystem.
*
* Since we need to check it anyway, we will flush all the invalid
- * entriess at the same time.
+ * entries at the same time.
*/
void
cache_purgevfs(mp)
struct mount *mp;
{
struct nchashhead *ncpp;
- struct namecache *ncp, *nnp;
+ struct namecache *ncp;
+ name_cache_lock();
/* Scan hash tables for applicable entries */
- for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
- for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
- nnp = ncp->nc_hash.le_next;
- if (ncp->nc_dvpid != ncp->nc_dvp->v_id ||
- (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id) ||
- ncp->nc_dvp->v_mount == mp) {
- PURGE(ncp);
+ for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) {
+restart:
+ for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) {
+ if (ncp->nc_dvp->v_mount == mp) {
+ cache_delete(ncp, 0);
+ goto restart;
}
}
}
+ name_cache_unlock();
+}
+
+
+
+//
+// String ref routines
+//
+static LIST_HEAD(stringhead, string_t) *string_ref_table;
+static u_long string_table_mask;
+static uint32_t max_chain_len=0;
+static struct stringhead *long_chain_head=NULL;
+static uint32_t filled_buckets=0;
+static uint32_t num_dups=0;
+static uint32_t nstrings=0;
+
+typedef struct string_t {
+ LIST_ENTRY(string_t) hash_chain;
+ unsigned char *str;
+ uint32_t refcount;
+} string_t;
+
+
+
+static int
+resize_string_ref_table(void)
+{
+ struct stringhead *new_table;
+ struct stringhead *old_table;
+ struct stringhead *old_head, *head;
+ string_t *entry, *next;
+ uint32_t i, hashval;
+ u_long new_mask, old_mask;
+
+ new_table = hashinit((string_table_mask + 1) * 2, M_CACHE, &new_mask);
+ if (new_table == NULL) {
+ return ENOMEM;
+ }
+
+ // do the switch!
+ old_table = string_ref_table;
+ string_ref_table = new_table;
+ old_mask = string_table_mask;
+ string_table_mask = new_mask;
+
+ printf("resize: max chain len %d, new table size %d\n",
+ max_chain_len, new_mask + 1);
+ max_chain_len = 0;
+ long_chain_head = NULL;
+ filled_buckets = 0;
+
+ // walk the old table and insert all the entries into
+ // the new table
+ //
+ for(i=0; i <= old_mask; i++) {
+ old_head = &old_table[i];
+ for (entry=old_head->lh_first; entry != NULL; entry=next) {
+ hashval = hash_string(entry->str, 0);
+ head = &string_ref_table[hashval & string_table_mask];
+ if (head->lh_first == NULL) {
+ filled_buckets++;
+ }
+
+ next = entry->hash_chain.le_next;
+ LIST_INSERT_HEAD(head, entry, hash_chain);
+ }
+ }
+
+ FREE(old_table, M_CACHE);
+
+ return 0;
+}
+
+
+static void
+init_string_table(void)
+{
+ string_ref_table = hashinit(4096, M_CACHE, &string_table_mask);
+}
+
+
+char *
+vfs_addname(const char *name, size_t len, u_int hashval, u_int flags)
+{
+ char * ptr;
+
+ name_cache_lock();
+ ptr = add_name_locked(name, len, hashval, flags);
+ name_cache_unlock();
+
+ return(ptr);
+}
+
+static char *
+add_name_locked(const char *name, size_t len, u_int hashval, __unused u_int flags)
+{
+ struct stringhead *head;
+ string_t *entry;
+ uint32_t chain_len = 0;
+
+ //
+ // If the table gets more than 3/4 full, resize it
+ //
+ if (4*filled_buckets >= ((string_table_mask + 1) * 3)) {
+ if (resize_string_ref_table() != 0) {
+ printf("failed to resize the hash table.\n");
+ }
+ }
+ if (hashval == 0) {
+ hashval = hash_string(name, 0);
+ }
+
+ head = &string_ref_table[hashval & string_table_mask];
+ for (entry=head->lh_first; entry != NULL; chain_len++, entry=entry->hash_chain.le_next) {
+ if (memcmp(entry->str, name, len) == 0 && entry->str[len] == '\0') {
+ entry->refcount++;
+ num_dups++;
+ break;
+ }
+ }
+
+ if (entry == NULL) {
+ // it wasn't already there so add it.
+ MALLOC(entry, string_t *, sizeof(string_t) + len + 1, M_TEMP, M_WAITOK);
+
+ // have to get "head" again because we could have blocked
+ // in malloc and thus head could have changed.
+ //
+ head = &string_ref_table[hashval & string_table_mask];
+ if (head->lh_first == NULL) {
+ filled_buckets++;
+ }
+
+ entry->str = (char *)((char *)entry + sizeof(string_t));
+ strncpy(entry->str, name, len);
+ entry->str[len] = '\0';
+ entry->refcount = 1;
+ LIST_INSERT_HEAD(head, entry, hash_chain);
+
+ if (chain_len > max_chain_len) {
+ max_chain_len = chain_len;
+ long_chain_head = head;
+ }
+
+ nstrings++;
+ }
+
+ return entry->str;
+}
+
+int
+vfs_removename(const char *nameref)
+{
+ int i;
+
+ name_cache_lock();
+ i = remove_name_locked(nameref);
+ name_cache_unlock();
+
+ return(i);
+
+}
+
+
+static int
+remove_name_locked(const char *nameref)
+{
+ struct stringhead *head;
+ string_t *entry;
+ uint32_t hashval;
+ char * ptr;
+
+ hashval = hash_string(nameref, 0);
+ head = &string_ref_table[hashval & string_table_mask];
+ for (entry=head->lh_first; entry != NULL; entry=entry->hash_chain.le_next) {
+ if (entry->str == (unsigned char *)nameref) {
+ entry->refcount--;
+ if (entry->refcount == 0) {
+ LIST_REMOVE(entry, hash_chain);
+ if (head->lh_first == NULL) {
+ filled_buckets--;
+ }
+ ptr = entry->str;
+ entry->str = NULL;
+ nstrings--;
+
+ FREE(entry, M_TEMP);
+ } else {
+ num_dups--;
+ }
+
+ return 0;
+ }
+ }
+
+ return ENOENT;
+}
+
+
+void
+dump_string_table(void)
+{
+ struct stringhead *head;
+ string_t *entry;
+ u_long i;
+
+ name_cache_lock();
+ for (i = 0; i <= string_table_mask; i++) {
+ head = &string_ref_table[i];
+ for (entry=head->lh_first; entry != NULL; entry=entry->hash_chain.le_next) {
+ printf("%6d - %s\n", entry->refcount, entry->str);
+ }
+ }
+ name_cache_unlock();
}
projects / apple / xnu.git / blobdiff