]> git.saurik.com Git - apple/xnu.git/blobdiff - bsd/vfs/vfs_cache.c
xnu-4903.231.4.tar.gz
[apple/xnu.git] / bsd / vfs / vfs_cache.c
index ed6ea3203bbe1d81ad5e404abf171121b79e841d..56c69754c777d576f84a2cf98aee950068274545 100644 (file)
@@ -1,5 +1,5 @@
 /*
 /*
- * Copyright (c) 2000-2007 Apple Inc. All rights reserved.
+ * Copyright (c) 2000-2015 Apple Inc. All rights reserved.
  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
  * 
  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
  * 
 #include <sys/time.h>
 #include <sys/mount_internal.h>
 #include <sys/vnode_internal.h>
 #include <sys/time.h>
 #include <sys/mount_internal.h>
 #include <sys/vnode_internal.h>
+#include <miscfs/specfs/specdev.h>
 #include <sys/namei.h>
 #include <sys/errno.h>
 #include <sys/malloc.h>
 #include <sys/kauth.h>
 #include <sys/user.h>
 #include <sys/paths.h>
 #include <sys/namei.h>
 #include <sys/errno.h>
 #include <sys/malloc.h>
 #include <sys/kauth.h>
 #include <sys/user.h>
 #include <sys/paths.h>
+#include <os/overflow.h>
 
 #if CONFIG_MACF
 #include <security/mac_framework.h>
 
 #if CONFIG_MACF
 #include <security/mac_framework.h>
@@ -114,6 +116,7 @@ long        numcache;                       /* number of cache entries allocated */
 int    desiredNodes;
 int    desiredNegNodes;
 int    ncs_negtotal;
 int    desiredNodes;
 int    desiredNegNodes;
 int    ncs_negtotal;
+int    nc_disabled = 0;
 TAILQ_HEAD(, namecache) nchead;                /* chain of all name cache entries */
 TAILQ_HEAD(, namecache) neghead;       /* chain of only negative cache entries */
 
 TAILQ_HEAD(, namecache) nchead;                /* chain of all name cache entries */
 TAILQ_HEAD(, namecache) neghead;       /* chain of only negative cache entries */
 
@@ -143,14 +146,24 @@ struct    nchstats nchstats;              /* cache effectiveness statistics */
 lck_grp_t * namecache_lck_grp;
 lck_grp_attr_t * namecache_lck_grp_attr;
 lck_attr_t * namecache_lck_attr;
 lck_grp_t * namecache_lck_grp;
 lck_grp_attr_t * namecache_lck_grp_attr;
 lck_attr_t * namecache_lck_attr;
-lck_rw_t * namecache_rw_lock;
+
+lck_grp_t * strcache_lck_grp;
+lck_grp_attr_t * strcache_lck_grp_attr;
+lck_attr_t * strcache_lck_attr;
+
+lck_rw_t  * namecache_rw_lock;
+lck_rw_t  * strtable_rw_lock;
+
+#define NUM_STRCACHE_LOCKS 1024
+
+lck_mtx_t strcache_mtx_locks[NUM_STRCACHE_LOCKS];
+
 
 static vnode_t cache_lookup_locked(vnode_t dvp, struct componentname *cnp);
 
 static vnode_t cache_lookup_locked(vnode_t dvp, struct componentname *cnp);
-static int  remove_name_locked(const char *);
-static const char *add_name_locked(const char *, size_t, u_int, u_int);
-static void init_string_table(void) __attribute__((section("__TEXT, initcode")));
+static const char *add_name_internal(const char *, uint32_t, u_int, boolean_t, u_int);
+static void init_string_table(void);
 static void cache_delete(struct namecache *, int);
 static void cache_delete(struct namecache *, int);
-static void cache_enter_locked(vnode_t dvp, vnode_t vp, struct componentname *cnp);
+static void cache_enter_locked(vnode_t dvp, vnode_t vp, struct componentname *cnp, const char *strname);
 
 #ifdef DUMP_STRING_TABLE
 /*
 
 #ifdef DUMP_STRING_TABLE
 /*
@@ -159,32 +172,261 @@ static void cache_enter_locked(vnode_t dvp, vnode_t vp, struct componentname *cn
 void dump_string_table(void);
 #endif /* DUMP_STRING_TABLE */
 
 void dump_string_table(void);
 #endif /* DUMP_STRING_TABLE */
 
-static void init_crc32(void) __attribute__((section("__TEXT, initcode")));
+static void init_crc32(void);
 static unsigned int crc32tab[256];
 
 
 #define NCHHASH(dvp, hash_val) \
        (&nchashtbl[(dvp->v_id ^ (hash_val)) & nchashmask])
 
 static unsigned int crc32tab[256];
 
 
 #define NCHHASH(dvp, hash_val) \
        (&nchashtbl[(dvp->v_id ^ (hash_val)) & nchashmask])
 
+/*
+ * This function tries to check if a directory vp is a subdirectory of dvp
+ * only from valid v_parent pointers. It is called with the name cache lock
+ * held and does not drop the lock anytime inside the function.
+ *
+ * It returns a boolean that indicates whether or not it was able to
+ * successfully infer the parent/descendent relationship via the v_parent
+ * pointers, or if it could not infer such relationship and that the decision
+ * must be delegated to the owning filesystem.
+ *
+ * If it does not defer the decision, i.e. it was successfuly able to determine
+ * the parent/descendent relationship,  *is_subdir tells the caller if vp is a
+ * subdirectory of dvp.
+ *
+ * If the decision is deferred, *next_vp is where it stopped i.e. *next_vp
+ * is the vnode whose parent is to be determined from the filesystem.
+ * *is_subdir, in this case, is not indicative of anything and should be
+ * ignored.
+ *
+ * The return value and output args should be used as follows :
+ *
+ * defer = cache_check_vnode_issubdir(vp, dvp, is_subdir, next_vp);
+ * if (!defer) {
+ *     if (*is_subdir)
+ *             vp is subdirectory;
+ *     else
+ *             vp is not a subdirectory;
+ * } else {
+ *     if (*next_vp)
+ *             check this vnode's parent from the filesystem
+ *     else
+ *             error (likely because of forced unmount).
+ * }
+ *
+ */
+static boolean_t
+cache_check_vnode_issubdir(vnode_t vp, vnode_t dvp, boolean_t *is_subdir,
+    vnode_t *next_vp)
+{
+       vnode_t tvp = vp;
+       int defer = FALSE;
+
+       *is_subdir = FALSE;
+       *next_vp = NULLVP;
+       while (1) {
+               mount_t tmp;
+
+               if (tvp == dvp) {
+                       *is_subdir = TRUE;
+                       break;
+               } else if (tvp == rootvnode) {
+                       /* *is_subdir = FALSE */
+                       break;
+               }
 
 
+               tmp = tvp->v_mount;
+               while ((tvp->v_flag & VROOT) && tmp && tmp->mnt_vnodecovered &&
+                   tvp != dvp && tvp != rootvnode) {
+                       tvp = tmp->mnt_vnodecovered;
+                       tmp = tvp->v_mount;
+               }
 
 
-//
-// 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.
-// 
-// This function can call vnop in file system if the parent vnode 
-// does not exist or when called for hardlinks via volfs path.  
-// If BUILDPATH_NO_FS_ENTER is set in flags, it only uses values present
-// in the name cache and does not enter the file system.
-//
+               /*
+                * If dvp is not at the top of a mount "stack" then
+                * vp is not a subdirectory of dvp either.
+                */
+               if (tvp == dvp || tvp == rootvnode) {
+                       /* *is_subdir = FALSE */
+                       break;
+               }
+
+               if (!tmp) {
+                       defer = TRUE;
+                       *next_vp = NULLVP;
+                       break;
+               }
+
+               if ((tvp->v_flag & VISHARDLINK) || !(tvp->v_parent)) {
+                       defer = TRUE;
+                       *next_vp = tvp;
+                       break;
+               }
+
+               tvp = tvp->v_parent;
+       }
+
+       return (defer);
+}
+
+/* maximum times retry from potentially transient errors in vnode_issubdir */
+#define MAX_ERROR_RETRY 3
+
+/*
+ * This function checks if a given directory (vp) is a subdirectory of dvp.
+ * It walks backwards from vp and if it hits dvp in its parent chain,
+ * it is a subdirectory. If it encounters the root directory, it is not
+ * a subdirectory.
+ *
+ * This function returns an error if it is unsuccessful and 0 on success.
+ *
+ * On entry (and exit) vp has an iocount and if this function has to take
+ * any iocounts on other vnodes in the parent chain traversal, it releases them.
+ */
 int
 int
-build_path(vnode_t first_vp, char *buff, int buflen, int *outlen, int flags, vfs_context_t ctx)
+vnode_issubdir(vnode_t vp, vnode_t dvp, int *is_subdir, vfs_context_t ctx)
+{
+       vnode_t start_vp, tvp;
+       vnode_t vp_with_iocount;
+       int error = 0;
+       char dotdotbuf[] = "..";
+       int error_retry_count = 0; /* retry count for potentially transient
+                                     errors */
+
+       *is_subdir = FALSE;
+       tvp = start_vp = vp;
+       /*
+        * Anytime we acquire an iocount in this function, we save the vnode
+        * in this variable and release it before exiting.
+        */
+       vp_with_iocount = NULLVP;
+
+       while (1) {
+               boolean_t defer;
+               vnode_t pvp;
+               uint32_t vid;
+               struct componentname cn;
+               boolean_t is_subdir_locked = FALSE;
+
+               if (tvp == dvp) {
+                       *is_subdir = TRUE;
+                       break;
+               } else if (tvp == rootvnode) {
+                       /* *is_subdir = FALSE */
+                       break;
+               }
+
+               NAME_CACHE_LOCK_SHARED();
+
+               defer = cache_check_vnode_issubdir(tvp, dvp, &is_subdir_locked,
+                   &tvp);
+
+               if (defer && tvp)
+                       vid = vnode_vid(tvp);
+
+               NAME_CACHE_UNLOCK();
+
+               if (!defer) {
+                       *is_subdir = is_subdir_locked;
+                       break;
+               }
+
+               if (!tvp) {
+                       if (error_retry_count++ < MAX_ERROR_RETRY) {
+                               tvp = vp;
+                               continue;
+                       }
+                       error = ENOENT;
+                       break;
+               }
+
+               if (tvp != start_vp) {
+                       if (vp_with_iocount) {
+                               vnode_put(vp_with_iocount);
+                               vp_with_iocount = NULLVP;
+                       }
+
+                       error = vnode_getwithvid(tvp, vid);
+                       if (error) {
+                               if (error_retry_count++ < MAX_ERROR_RETRY) {
+                                       tvp = vp;
+                                       error = 0;
+                                       continue;
+                               }
+                               break;
+                       }
+
+                       vp_with_iocount = tvp;
+               }
+
+               bzero(&cn, sizeof(cn));
+               cn.cn_nameiop = LOOKUP;
+               cn.cn_flags = ISLASTCN | ISDOTDOT;
+               cn.cn_context = ctx;
+               cn.cn_pnbuf = &dotdotbuf[0];
+               cn.cn_pnlen = sizeof(dotdotbuf);
+               cn.cn_nameptr = cn.cn_pnbuf;
+               cn.cn_namelen = 2;
+
+               pvp = NULLVP;
+               if ((error = VNOP_LOOKUP(tvp, &pvp, &cn, ctx)))
+                       break;
+
+               if (!(tvp->v_flag & VISHARDLINK) && tvp->v_parent != pvp) {
+                       (void)vnode_update_identity(tvp, pvp, NULL, 0, 0,
+                           VNODE_UPDATE_PARENT);
+               }
+
+               if (vp_with_iocount)
+                       vnode_put(vp_with_iocount);
+
+               vp_with_iocount = tvp = pvp;
+       }
+
+       if (vp_with_iocount)
+               vnode_put(vp_with_iocount);
+
+       return (error);
+}
+
+/*
+ * This function builds the path in "buff" from the supplied vnode.
+ * 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.
+ * 
+ * This function can call vnop in file system if the parent vnode 
+ * does not exist or when called for hardlinks via volfs path.  
+ * If BUILDPATH_NO_FS_ENTER is set in flags, it only uses values present
+ * in the name cache and does not enter the file system.
+ *
+ * If BUILDPATH_CHECK_MOVED is set in flags, we return EAGAIN when 
+ * we encounter ENOENT during path reconstruction.  ENOENT means that 
+ * one of the parents moved while we were building the path.  The 
+ * caller can special handle this case by calling build_path again.
+ *
+ * If BUILDPATH_VOLUME_RELATIVE is set in flags, we return path 
+ * that is relative to the nearest mount point, i.e. do not 
+ * cross over mount points during building the path. 
+ *
+ * passed in vp must have a valid io_count reference
+ *
+ * If parent vnode is non-NULL it also must have an io count.  This
+ * allows build_path_with_parent to be safely called for operations
+ * unlink, rmdir and rename that already have io counts on the target
+ * and the directory. In this way build_path_with_parent does not have
+ * to try and obtain an additional io count on the parent.  Taking an
+ * io count ont the parent can lead to dead lock if a forced unmount
+ * occures at the right moment. For a fuller explaination on how this
+ * can occur see the comment for vn_getpath_with_parent.
+ *
+ */
+int
+build_path_with_parent(vnode_t first_vp, vnode_t parent_vp, char *buff, int buflen, int *outlen, int flags, vfs_context_t ctx)
 {
 {
-        vnode_t vp;
+        vnode_t vp, tvp;
+       vnode_t vp_with_iocount;
         vnode_t proc_root_dir_vp;
        char *end;
        const char *str;
         vnode_t proc_root_dir_vp;
        char *end;
        const char *str;
@@ -192,24 +434,51 @@ build_path(vnode_t first_vp, char *buff, int buflen, int *outlen, int flags, vfs
        int  ret = 0;
        int  fixhardlink;
 
        int  ret = 0;
        int  fixhardlink;
 
-       if (first_vp == NULLVP) {
+       if (first_vp == NULLVP)
                return (EINVAL);
                return (EINVAL);
-       }
-       /* Grab the process fd so we can evaluate fd_rdir. */
-       if (vfs_context_proc(ctx)->p_fd) {
-           proc_root_dir_vp = vfs_context_proc(ctx)->p_fd->fd_rdir;
-       } else {
-           proc_root_dir_vp = NULL;
-       }
+               
+       if (buflen <= 1)
+               return (ENOSPC);
+
+       /*
+        * Grab the process fd so we can evaluate fd_rdir.
+        */
+       if (vfs_context_proc(ctx)->p_fd)
+               proc_root_dir_vp = vfs_context_proc(ctx)->p_fd->fd_rdir;
+       else
+               proc_root_dir_vp = NULL;
+
+       vp_with_iocount = NULLVP;
 again:
        vp = first_vp;
 again:
        vp = first_vp;
+
        end = &buff[buflen-1];
        *end = '\0';
 
        end = &buff[buflen-1];
        *end = '\0';
 
-       /* Check if this is the root of a file system. */
+       /*
+        * holding the NAME_CACHE_LOCK in shared mode is
+        * sufficient to stabilize both the vp->v_parent chain
+        * and the 'vp->v_mount->mnt_vnodecovered' chain
+        *
+        * if we need to drop this lock, we must first grab the v_id
+        * from the vnode we're currently working with... if that
+        * vnode doesn't already have an io_count reference (the vp
+        * passed in comes with one), we must grab a reference
+        * after we drop the NAME_CACHE_LOCK via vnode_getwithvid...
+        * deadlocks may result if you call vnode_get while holding
+        * the NAME_CACHE_LOCK... we lazily release the reference
+        * we pick up the next time we encounter a need to drop 
+        * the NAME_CACHE_LOCK or before we return from this routine
+        */
+       NAME_CACHE_LOCK_SHARED();
+
+       /*
+        * Check if this is the root of a file system.
+        */
        while (vp && vp->v_flag & VROOT) {
                if (vp->v_mount == NULL) {
        while (vp && vp->v_flag & VROOT) {
                if (vp->v_mount == NULL) {
-                       return (EINVAL);
+                       ret = EINVAL;
+                       goto out_unlock;
                }
                if ((vp->v_mount->mnt_flag & MNT_ROOTFS) || (vp == proc_root_dir_vp)) {
                        /*
                }
                if ((vp->v_mount->mnt_flag & MNT_ROOTFS) || (vp == proc_root_dir_vp)) {
                        /*
@@ -217,14 +486,26 @@ again:
                         * just "/".
                         */
                        *--end = '/';
                         * just "/".
                         */
                        *--end = '/';
-                       goto out;
+
+                       goto out_unlock;
                } else {
                } else {
-                       vp = vp->v_mount->mnt_vnodecovered;
+                       /* 
+                        * This the root of the volume and the caller does not 
+                        * want to cross mount points.  Therefore just return 
+                        * '/' as the relative path. 
+                        */
+                       if (flags & BUILDPATH_VOLUME_RELATIVE) {
+                               *--end = '/';
+                               goto out_unlock;
+                       } else {
+                               vp = vp->v_mount->mnt_vnodecovered;
+                       }
                }
        }
                }
        }
-       NAME_CACHE_LOCK_SHARED();
 
        while ((vp != NULLVP) && (vp->v_parent != vp)) {
 
        while ((vp != NULLVP) && (vp->v_parent != vp)) {
+               int  vid;
+
                /*
                 * For hardlinks the v_name may be stale, so if its OK
                 * to enter a file system, ask the file system for the
                /*
                 * For hardlinks the v_name may be stale, so if its OK
                 * to enter a file system, ask the file system for the
@@ -233,15 +514,16 @@ again:
                fixhardlink = (vp->v_flag & VISHARDLINK) &&
                              (vp->v_mount->mnt_kern_flag & MNTK_PATH_FROM_ID) &&
                              !(flags & BUILDPATH_NO_FS_ENTER);
                fixhardlink = (vp->v_flag & VISHARDLINK) &&
                              (vp->v_mount->mnt_kern_flag & MNTK_PATH_FROM_ID) &&
                              !(flags & BUILDPATH_NO_FS_ENTER);
+
                if (!fixhardlink) {
                        str = vp->v_name;
                if (!fixhardlink) {
                        str = vp->v_name;
+
                        if (str == NULL || *str == '\0') {
                        if (str == NULL || *str == '\0') {
-                               if (vp->v_parent != NULL) {
+                               if (vp->v_parent != NULL)
                                        ret = EINVAL;
                                        ret = EINVAL;
-                               } else {
+                               else
                                        ret = ENOENT;
                                        ret = ENOENT;
-                               }
-                               break;
+                               goto out_unlock;
                        }
                        len = strlen(str);
                        /*
                        }
                        len = strlen(str);
                        /*
@@ -249,15 +531,18 @@ again:
                         */
                        if ((end - buff) < (len + 1)) {
                                ret = ENOSPC;
                         */
                        if ((end - buff) < (len + 1)) {
                                ret = ENOSPC;
-                               break;
+                               goto out_unlock;
                        }
                        }
-                       /* Copy the name backwards. */
+                       /*
+                        * Copy the name backwards.
+                        */
                        str += len;
        
                        str += len;
        
-                       for (; len > 0; len--) {
+                       for (; len > 0; len--)
                               *--end = *--str;
                               *--end = *--str;
-                       }
-                       /* Add a path separator. */
+                       /*
+                        * Add a path separator.
+                        */
                        *--end = '/';
                }
 
                        *--end = '/';
                }
 
@@ -265,144 +550,217 @@ again:
                 * Walk up the parent chain.
                 */
                if (((vp->v_parent != NULLVP) && !fixhardlink) ||
                 * Walk up the parent chain.
                 */
                if (((vp->v_parent != NULLVP) && !fixhardlink) ||
-                   (flags & BUILDPATH_NO_FS_ENTER)) {
+                               (flags & BUILDPATH_NO_FS_ENTER)) {
+
+                       /*
+                        * In this if () block we are not allowed to enter the filesystem
+                        * to conclusively get the most accurate parent identifier.
+                        * As a result, if 'vp' does not identify '/' and it
+                        * does not have a valid v_parent, then error out
+                        * and disallow further path construction
+                        */
+                       if ((vp->v_parent == NULLVP) && (rootvnode != vp)) {
+                               /*
+                                * Only '/' is allowed to have a NULL parent
+                                * pointer. Upper level callers should ideally
+                                * re-drive name lookup on receiving a ENOENT.
+                                */
+                               ret = ENOENT;
+
+                               /* The code below will exit early if 'tvp = vp' == NULL */
+                       }
                        vp = vp->v_parent;
 
                        vp = vp->v_parent;
 
-                       // if the vnode we have in hand isn't a directory and it
-                       // has a v_parent, then we started with the resource fork
-                       // so skip up to avoid getting a duplicate copy of the
-                       // file name in the path.
+                       /*
+                        * if the vnode we have in hand isn't a directory and it
+                        * has a v_parent, then we started with the resource fork
+                        * so skip up to avoid getting a duplicate copy of the
+                        * file name in the path.
+                        */
                        if (vp && !vnode_isdir(vp) && vp->v_parent) {
                        if (vp && !vnode_isdir(vp) && vp->v_parent) {
-                           vp = vp->v_parent;
+                               vp = vp->v_parent;
                        }
                        }
-               } else /* No parent, go get it if supported. */ {
+               } else {
+                       /*
+                        * No parent, go get it if supported.
+                        */
                        struct vnode_attr  va;
                        vnode_t  dvp;
                        struct vnode_attr  va;
                        vnode_t  dvp;
-                       int  vid;
 
 
-                       /* Make sure file system supports obtaining a path from id. */
+                       /*
+                        * Make sure file system supports obtaining a path from id.
+                        */
                        if (!(vp->v_mount->mnt_kern_flag & MNTK_PATH_FROM_ID)) {
                                ret = ENOENT;
                        if (!(vp->v_mount->mnt_kern_flag & MNTK_PATH_FROM_ID)) {
                                ret = ENOENT;
-                               break;
+                               goto out_unlock;
                        }
                        }
-                       vid = vp->v_id;
+                       vid = vp->v_id;
+
                        NAME_CACHE_UNLOCK();
 
                        NAME_CACHE_UNLOCK();
 
-                       if (vnode_getwithvid(vp, vid) != 0) {
-                               /* vnode was recycled, so start over. */
-                               goto again;
-                       }
-                       
+                       if (vp != first_vp && vp != parent_vp && vp != vp_with_iocount) {
+                               if (vp_with_iocount) {
+                                       vnode_put(vp_with_iocount);
+                                       vp_with_iocount = NULLVP;
+                               }
+                               if (vnode_getwithvid(vp, vid))
+                                       goto again;
+                               vp_with_iocount = vp;
+                       }
                        VATTR_INIT(&va);
                        VATTR_WANTED(&va, va_parentid);
                        VATTR_INIT(&va);
                        VATTR_WANTED(&va, va_parentid);
+
                        if (fixhardlink) {
                                VATTR_WANTED(&va, va_name);
                                MALLOC_ZONE(va.va_name, caddr_t, MAXPATHLEN, M_NAMEI, M_WAITOK);
                        } else {
                                va.va_name = NULL;
                        }
                        if (fixhardlink) {
                                VATTR_WANTED(&va, va_name);
                                MALLOC_ZONE(va.va_name, caddr_t, MAXPATHLEN, M_NAMEI, M_WAITOK);
                        } else {
                                va.va_name = NULL;
                        }
-                       /* Ask the file system for its parent id and for its name (optional). */
+                       /*
+                        * Ask the file system for its parent id and for its name (optional).
+                        */
                        ret = vnode_getattr(vp, &va, ctx);
                        ret = vnode_getattr(vp, &va, ctx);
+
                        if (fixhardlink) {
                        if (fixhardlink) {
-                               if (vp->v_name || VATTR_IS_SUPPORTED(&va, va_name)) {
-                                       if (ret == 0) {
-                                               str = va.va_name;
-                                       } else if (vp->v_name) {
-                                               str = vp->v_name;
-                                               ret = 0;
-                                       } else {
-                                               ret = ENOENT;
-                                               goto bad_news;
-                                       }
+                               if ((ret == 0) && (VATTR_IS_SUPPORTED(&va, va_name))) {
+                                       str = va.va_name;
+                                       vnode_update_identity(vp, NULL, str, strlen(str), 0, VNODE_UPDATE_NAME);
+                               } else if (vp->v_name) {
+                                       str = vp->v_name;
+                                       ret = 0;
+                               } else {
+                                       ret = ENOENT;
+                                       goto bad_news;
+                               }
+                               len = strlen(str);
 
 
-                                       len = strlen(str);
-
-                                       /* Check that there's enough space. */
-                                       if ((end - buff) < (len + 1)) {
-                                               ret = ENOSPC;
-                                       } else {
-                                               /* Copy the name backwards. */
-                                               str += len;
-                               
-                                               for (; len > 0; len--) {
-                                                      *--end = *--str;
-                                               }
-                                               /* Add a path separator. */
-                                               *--end = '/';
+                               /*
+                                * Check that there's enough space.
+                                */
+                               if ((end - buff) < (len + 1)) {
+                                       ret = ENOSPC;
+                               } else {
+                                       /* Copy the name backwards. */
+                                       str += len;
+
+                                       for (; len > 0; len--) {
+                                               *--end = *--str;
                                        }
                                        }
+                                       /*
+                                        * Add a path separator.
+                                        */
+                                       *--end = '/';
                                }
                                }
-                         bad_news:
+bad_news:
                                FREE_ZONE(va.va_name, MAXPATHLEN, M_NAMEI);
                        }
                        if (ret || !VATTR_IS_SUPPORTED(&va, va_parentid)) {
                                FREE_ZONE(va.va_name, MAXPATHLEN, M_NAMEI);
                        }
                        if (ret || !VATTR_IS_SUPPORTED(&va, va_parentid)) {
-                               vnode_put(vp);
                                ret = ENOENT;
                                goto out;
                        }
                                ret = ENOENT;
                                goto out;
                        }
-                       /* Ask the file system for the parent vnode. */
-                       ret = VFS_VGET(vp->v_mount, (ino64_t)va.va_parentid, &dvp, ctx);
-                       if (ret) {
-                               vnode_put(vp);
+                       /*
+                        * Ask the file system for the parent vnode.
+                        */
+                       if ((ret = VFS_VGET(vp->v_mount, (ino64_t)va.va_parentid, &dvp, ctx)))
                                goto out;
                                goto out;
-                       }
-                       if (!fixhardlink && (vp->v_parent != dvp)) {
+
+                       if (!fixhardlink && (vp->v_parent != dvp))
                                vnode_update_identity(vp, dvp, NULL, 0, 0, VNODE_UPDATE_PARENT);
                                vnode_update_identity(vp, dvp, NULL, 0, 0, VNODE_UPDATE_PARENT);
-                       }
-                       vnode_put(vp);
+
+                       if (vp_with_iocount)
+                               vnode_put(vp_with_iocount);
                        vp = dvp;
                        vp = dvp;
+                       vp_with_iocount = vp;
+
+                       NAME_CACHE_LOCK_SHARED();
+
                        /*
                        /*
-                        * We are no longer under the name cache lock here.
-                        * So to avoid a race for vnode termination, take a
-                        * reference on the vnode and drop that reference
-                        * after reacquiring the name cache lock. We use the
-                        * vnode_rele_ext call with the dont_reenter flag
-                        * set to avoid re-entering the file system which
-                        * could possibly re-enter the name cache.
+                        * if the vnode we have in hand isn't a directory and it
+                        * has a v_parent, then we started with the resource fork
+                        * so skip up to avoid getting a duplicate copy of the
+                        * file name in the path.
                         */
                         */
-                       if (vnode_ref(dvp) != 0) {
-                               dvp = NULLVP;
-                       }
-                       vnode_put(vp);
-                       NAME_CACHE_LOCK_SHARED();
+                       if (vp && !vnode_isdir(vp) && vp->v_parent)
+                               vp = vp->v_parent;
+               }
 
 
-                       if (dvp) {
-                               vnode_rele_ext(dvp, 0, 1);
-                       }
+               if (vp && (flags & BUILDPATH_CHECKACCESS)) {
+                       vid = vp->v_id;
 
 
-                       // if the vnode we have in hand isn't a directory and it
-                       // has a v_parent, then we started with the resource fork
-                       // so skip up to avoid getting a duplicate copy of the
-                       // file name in the path.
-                       if (vp && !vnode_isdir(vp) && vp->v_parent) {
-                           vp = vp->v_parent;
+                       NAME_CACHE_UNLOCK();
+
+                       if (vp != first_vp && vp != parent_vp && vp != vp_with_iocount) {
+                               if (vp_with_iocount) {
+                                       vnode_put(vp_with_iocount);
+                                       vp_with_iocount = NULLVP;
+                               }
+                               if (vnode_getwithvid(vp, vid))
+                                       goto again;
+                               vp_with_iocount = vp;
                        }
                        }
+                       if ((ret = vnode_authorize(vp, NULL, KAUTH_VNODE_SEARCH, ctx)))
+                               goto out;       /* no peeking */
+
+                       NAME_CACHE_LOCK_SHARED();
                }
                }
+
                /*
                 * When a mount point is crossed switch the vp.
                 * Continue until we find the root or we find
                 * a vnode that's not the root of a mounted
                 * file system.
                 */
                /*
                 * When a mount point is crossed switch the vp.
                 * Continue until we find the root or we find
                 * a vnode that's not the root of a mounted
                 * file system.
                 */
-               while (vp) {
-                       if (vp == proc_root_dir_vp) {
-                               NAME_CACHE_UNLOCK();
-                               goto out;  /* encountered the root */
+               tvp = vp;
+
+               while (tvp) {
+                       if (tvp == proc_root_dir_vp)
+                               goto out_unlock;        /* encountered the root */
+
+                       if (!(tvp->v_flag & VROOT) || !tvp->v_mount)
+                               break;                  /* not the root of a mounted FS */
+
+                       if (flags & BUILDPATH_VOLUME_RELATIVE) {
+                               /* Do not cross over mount points */
+                               tvp = NULL;
+                       } else {
+                               tvp = tvp->v_mount->mnt_vnodecovered;
                        }
                        }
-                       if (!(vp->v_flag & VROOT) || !vp->v_mount)
-                               break;  /* not the root of a mounted FS */
-                       vp = vp->v_mount->mnt_vnodecovered;
                }
                }
+               if (tvp == NULLVP)
+                       goto out_unlock;
+               vp = tvp;
        }
        }
+out_unlock:
        NAME_CACHE_UNLOCK();
 out:
        NAME_CACHE_UNLOCK();
 out:
-       /* Slide the name down to the beginning of the buffer. */
+       if (vp_with_iocount)
+               vnode_put(vp_with_iocount);
+       /*
+        * Slide the name down to the beginning of the buffer.
+        */
        memmove(buff, end, &buff[buflen] - end);
        memmove(buff, end, &buff[buflen] - end);
-    
-       *outlen = &buff[buflen] - end;  /* length includes the trailing zero byte */
+
+       /*
+        * length includes the trailing zero byte
+        */
+       *outlen = &buff[buflen] - end;
  
  
+       /* One of the parents was moved during path reconstruction. 
+        * The caller is interested in knowing whether any of the 
+        * parents moved via BUILDPATH_CHECK_MOVED, so return EAGAIN.
+        */
+       if ((ret == ENOENT) && (flags & BUILDPATH_CHECK_MOVED)) {
+               ret = EAGAIN;
+       }
+
        return (ret);
 }
 
        return (ret);
 }
 
+int
+build_path(vnode_t first_vp, char *buff, int buflen, int *outlen, int flags, vfs_context_t ctx)
+{
+       return (build_path_with_parent(first_vp, NULL, buff, buflen, outlen, flags, ctx));
+}
 
 /*
  * return NULLVP if vp's parent doesn't
 
 /*
  * return NULLVP if vp's parent doesn't
@@ -439,11 +797,11 @@ const char *
 vnode_getname(vnode_t vp)
 {
         const char *name = NULL;
 vnode_getname(vnode_t vp)
 {
         const char *name = NULL;
-
-       NAME_CACHE_LOCK();
+       
+       NAME_CACHE_LOCK_SHARED();
        
        if (vp->v_name)
        
        if (vp->v_name)
-               name = add_name_locked(vp->v_name, strlen(vp->v_name), 0, 0);
+               name = vfs_addname(vp->v_name, strlen(vp->v_name), 0, 0);
        NAME_CACHE_UNLOCK();
 
        return (name);
        NAME_CACHE_UNLOCK();
 
        return (name);
@@ -452,13 +810,54 @@ vnode_getname(vnode_t vp)
 void
 vnode_putname(const char *name)
 {
 void
 vnode_putname(const char *name)
 {
-        NAME_CACHE_LOCK();
+       vfs_removename(name);
+}
 
 
-       remove_name_locked(name);
+static const char unknown_vnodename[] = "(unknown vnode name)";
 
 
-       NAME_CACHE_UNLOCK();
+const char *
+vnode_getname_printable(vnode_t vp)
+{
+       const char *name = vnode_getname(vp);
+       if (name != NULL)
+               return name;
+       
+       switch (vp->v_type) {
+               case VCHR:
+               case VBLK:
+                       {
+                       /*
+                        * Create an artificial dev name from
+                        * major and minor device number
+                        */
+                       char dev_name[64];
+                       (void) snprintf(dev_name, sizeof(dev_name),
+                                       "%c(%u, %u)", VCHR == vp->v_type ? 'c':'b',
+                                       major(vp->v_rdev), minor(vp->v_rdev));
+                       /*
+                        * Add the newly created dev name to the name
+                        * cache to allow easier cleanup. Also,
+                        * vfs_addname allocates memory for the new name
+                        * and returns it.
+                        */
+                       NAME_CACHE_LOCK_SHARED();
+                       name = vfs_addname(dev_name, strlen(dev_name), 0, 0);
+                       NAME_CACHE_UNLOCK();
+                       return name;
+                       }
+               default:
+                       return unknown_vnodename;
+       }
 }
 
 }
 
+void 
+vnode_putname_printable(const char *name)
+{
+       if (name == unknown_vnodename)
+               return;
+       vnode_putname(name);
+}
+               
 
 /*
  * if VNODE_UPDATE_PARENT, and we can take
 
 /*
  * if VNODE_UPDATE_PARENT, and we can take
@@ -474,20 +873,20 @@ vnode_putname(const char *name)
  * if VNODE_UPDATE_CACHE, flush the name cache entries associated with vp
  */
 void
  * if VNODE_UPDATE_CACHE, flush the name cache entries associated with vp
  */
 void
-vnode_update_identity(vnode_t vp, vnode_t dvp, const char *name, int name_len, int name_hashval, int flags)
+vnode_update_identity(vnode_t vp, vnode_t dvp, const char *name, int name_len, uint32_t name_hashval, int flags)
 {
        struct  namecache *ncp;
         vnode_t        old_parentvp = NULLVP;
 {
        struct  namecache *ncp;
         vnode_t        old_parentvp = NULLVP;
-#if NAMEDSTREAMS
        int isstream = (vp->v_flag & VISNAMEDSTREAM);
        int kusecountbumped = 0;
        int isstream = (vp->v_flag & VISNAMEDSTREAM);
        int kusecountbumped = 0;
-#endif
+       kauth_cred_t tcred = NULL;
+       const char *vname = NULL;
+       const char *tname = NULL;
 
        if (flags & VNODE_UPDATE_PARENT) {
                if (dvp && vnode_ref(dvp) != 0) {
                        dvp = NULLVP;
                }
 
        if (flags & VNODE_UPDATE_PARENT) {
                if (dvp && vnode_ref(dvp) != 0) {
                        dvp = NULLVP;
                }
-#if NAMEDSTREAMS
                /* Don't count a stream's parent ref during unmounts */
                if (isstream && dvp && (dvp != vp) && (dvp != vp->v_parent) && (dvp->v_type == VREG)) {
                        vnode_lock_spin(dvp);
                /* Don't count a stream's parent ref during unmounts */
                if (isstream && dvp && (dvp != vp) && (dvp != vp->v_parent) && (dvp->v_type == VREG)) {
                        vnode_lock_spin(dvp);
@@ -495,41 +894,69 @@ vnode_update_identity(vnode_t vp, vnode_t dvp, const char *name, int name_len, i
                        kusecountbumped = 1;
                        vnode_unlock(dvp);
                }
                        kusecountbumped = 1;
                        vnode_unlock(dvp);
                }
-#endif
        } else {
                dvp = NULLVP;
        }
        } else {
                dvp = NULLVP;
        }
-       NAME_CACHE_LOCK();
+       if ( (flags & VNODE_UPDATE_NAME) ) {
+               if (name != vp->v_name) {
+                       if (name && *name) {
+                               if (name_len == 0)
+                                       name_len = strlen(name);
+                               tname = vfs_addname(name, name_len, name_hashval, 0);
+                       }
+               } else
+                       flags &= ~VNODE_UPDATE_NAME;
+       }
+       if ( (flags & (VNODE_UPDATE_PURGE | VNODE_UPDATE_PARENT | VNODE_UPDATE_CACHE | VNODE_UPDATE_NAME)) ) {
+
+               NAME_CACHE_LOCK();
+
+               if ( (flags & VNODE_UPDATE_PURGE) ) {
+
+                       if (vp->v_parent)
+                               vp->v_parent->v_nc_generation++;
+
+                       while ( (ncp = LIST_FIRST(&vp->v_nclinks)) )
+                               cache_delete(ncp, 1);
 
 
-       if ( (flags & VNODE_UPDATE_NAME) && (name != vp->v_name) ) {
-               if (vp->v_name != NULL) {
-                       remove_name_locked(vp->v_name);
-                       vp->v_name = NULL;
+                       while ( (ncp = TAILQ_FIRST(&vp->v_ncchildren)) )
+                               cache_delete(ncp, 1);
+
+                       /*
+                        * Use a temp variable to avoid kauth_cred_unref() while NAME_CACHE_LOCK is held
+                        */
+                       tcred = vp->v_cred;
+                       vp->v_cred = NOCRED;
+                       vp->v_authorized_actions = 0;
+                       vp->v_cred_timestamp = 0;
                }
                }
-               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_NAME) ) {
+                       vname = vp->v_name;
+                       vp->v_name = tname;
                }
                }
-       }
-       if (flags & VNODE_UPDATE_PARENT) {
-               if (dvp != vp && dvp != vp->v_parent) {
-                       old_parentvp = vp->v_parent;
-                       vp->v_parent = dvp;
-                       dvp = NULLVP;
+               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 (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 (flags & VNODE_UPDATE_CACHE) {
+                       while ( (ncp = LIST_FIRST(&vp->v_nclinks)) )
+                               cache_delete(ncp, 1);
+               }
+               NAME_CACHE_UNLOCK();
        
        
+               if (vname != NULL)
+                       vfs_removename(vname);
+
+               if (IS_VALID_CRED(tcred))
+                       kauth_cred_unref(&tcred);
+       }
        if (dvp != NULLVP) {
        if (dvp != NULLVP) {
-#if NAMEDSTREAMS
                /* Back-out the ref we took if we lost a race for vp->v_parent. */
                if (kusecountbumped) {
                        vnode_lock_spin(dvp);
                /* Back-out the ref we took if we lost a race for vp->v_parent. */
                if (kusecountbumped) {
                        vnode_lock_spin(dvp);
@@ -537,20 +964,17 @@ vnode_update_identity(vnode_t vp, vnode_t dvp, const char *name, int name_len, i
                                --dvp->v_kusecount;  
                        vnode_unlock(dvp);
                }
                                --dvp->v_kusecount;  
                        vnode_unlock(dvp);
                }
-#endif
                vnode_rele(dvp);
        }
        if (old_parentvp) {
                struct  uthread *ut;
 
                vnode_rele(dvp);
        }
        if (old_parentvp) {
                struct  uthread *ut;
 
-#if NAMEDSTREAMS
                if (isstream) {
                        vnode_lock_spin(old_parentvp);
                        if ((old_parentvp->v_type != VDIR) && (old_parentvp->v_kusecount > 0))
                                --old_parentvp->v_kusecount;
                        vnode_unlock(old_parentvp);
                }
                if (isstream) {
                        vnode_lock_spin(old_parentvp);
                        if ((old_parentvp->v_type != VDIR) && (old_parentvp->v_kusecount > 0))
                                --old_parentvp->v_kusecount;
                        vnode_unlock(old_parentvp);
                }
-#endif
                ut = get_bsdthread_info(current_thread());
 
                /*
                ut = get_bsdthread_info(current_thread());
 
                /*
@@ -565,7 +989,7 @@ vnode_update_identity(vnode_t vp, vnode_t dvp, const char *name, int name_len, i
 
                while ( (vp = old_parentvp) != NULLVP ) {
          
 
                while ( (vp = old_parentvp) != NULLVP ) {
          
-                       vnode_lock(vp);
+                       vnode_lock_spin(vp);
                        vnode_rele_internal(vp, 0, 0, 1);
 
                        /*
                        vnode_rele_internal(vp, 0, 0, 1);
 
                        /*
@@ -579,7 +1003,7 @@ vnode_update_identity(vnode_t vp, vnode_t dvp, const char *name, int name_len, i
                         * we'll sit in this loop until we run into
                         * a parent in this chain that is not 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
+                        * make our check and the vnode_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
                         * 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
@@ -703,11 +1127,18 @@ void vnode_uncache_authorized_action(vnode_t vp, kauth_action_t action)
 }
 
 
 }
 
 
-boolean_t vnode_cache_is_authorized(vnode_t vp, vfs_context_t ctx, kauth_action_t action)
+extern int bootarg_vnode_cache_defeat; /* default = 0, from bsd_init.c */
+
+boolean_t
+vnode_cache_is_authorized(vnode_t vp, vfs_context_t ctx, kauth_action_t action)
 {
        kauth_cred_t    ucred;
        boolean_t       retval = FALSE;
 
 {
        kauth_cred_t    ucred;
        boolean_t       retval = FALSE;
 
+       /* Boot argument to defeat rights caching */
+       if (bootarg_vnode_cache_defeat)
+               return FALSE;
+
        if ( (vp->v_mount->mnt_kern_flag & (MNTK_AUTH_OPAQUE | MNTK_AUTH_CACHE_TTL)) ) {
                /*
                 * a TTL is enabled on the rights cache... handle it here
        if ( (vp->v_mount->mnt_kern_flag & (MNTK_AUTH_OPAQUE | MNTK_AUTH_CACHE_TTL)) ) {
                /*
                 * a TTL is enabled on the rights cache... handle it here
@@ -827,10 +1258,12 @@ boolean_t vnode_cache_is_stale(vnode_t vp)
 
 /*
  * Returns:    0                       Success
 
 /*
  * Returns:    0                       Success
- *             ENOENT                  No such file or directory
+ *             ERECYCLE                vnode was recycled from underneath us.  Force lookup to be re-driven from namei.
+ *                                             This errno value should not be seen by anyone outside of the kernel.
  */
 int 
  */
 int 
-cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp, vfs_context_t ctx, int *trailing_slash, int *dp_authorized)
+cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp, 
+               vfs_context_t ctx, int *dp_authorized, vnode_t last_dp)
 {
        char            *cp;            /* pointer into pathname argument */
        int             vid;
 {
        char            *cp;            /* pointer into pathname argument */
        int             vid;
@@ -842,12 +1275,15 @@ cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp,
        struct timeval  tv;
         mount_t                mp;
        unsigned int    hash;
        struct timeval  tv;
         mount_t                mp;
        unsigned int    hash;
-#if CONFIG_MACF
-       int             error;
-#endif
+       int             error = 0;
+       boolean_t       dotdotchecked = FALSE;
+
+#if CONFIG_TRIGGERS
+       vnode_t         trigger_vp;
+#endif /* CONFIG_TRIGGERS */
 
        ucred = vfs_context_ucred(ctx);
 
        ucred = vfs_context_ucred(ctx);
-       *trailing_slash = 0;
+       ndp->ni_flag &= ~(NAMEI_TRAILINGSLASH);
 
        NAME_CACHE_LOCK_SHARED();
 
 
        NAME_CACHE_LOCK_SHARED();
 
@@ -856,7 +1292,7 @@ cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp,
                microuptime(&tv);
        }
        for (;;) {
                microuptime(&tv);
        }
        for (;;) {
-               /*
+               /*
                 * Search a directory.
                 *
                 * The cn_hash value is for use by cache_lookup
                 * Search a directory.
                 *
                 * The cn_hash value is for use by cache_lookup
@@ -867,7 +1303,7 @@ cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp,
                cp = cnp->cn_nameptr;
 
                while (*cp && (*cp != '/')) {
                cp = cnp->cn_nameptr;
 
                while (*cp && (*cp != '/')) {
-                       hash ^= crc32tab[((hash >> 24) ^ (unsigned char)*cp++)];
+                       hash = crc32tab[((hash >> 24) ^ (unsigned char)*cp++)] ^ hash << 8;
                }
                /*
                 * the crc generator can legitimately generate
                }
                /*
                 * the crc generator can legitimately generate
@@ -894,7 +1330,7 @@ cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp,
                        ndp->ni_pathlen--;
 
                        if (*cp == '\0') {
                        ndp->ni_pathlen--;
 
                        if (*cp == '\0') {
-                               *trailing_slash = 1;
+                               ndp->ni_flag |= NAMEI_TRAILINGSLASH;
                                *ndp->ni_next = '\0';
                        }
                }
                                *ndp->ni_next = '\0';
                        }
                }
@@ -934,7 +1370,7 @@ skiprsrcfork:
 
 #if CONFIG_MACF
 
 
 #if CONFIG_MACF
 
-               /* 
+               /*
                 * Name cache provides authorization caching (see below)
                 * that will short circuit MAC checks in lookup().
                 * We must perform MAC check here.  On denial
                 * Name cache provides authorization caching (see below)
                 * that will short circuit MAC checks in lookup().
                 * We must perform MAC check here.  On denial
@@ -944,20 +1380,35 @@ skiprsrcfork:
                if (!(cnp->cn_flags & DONOTAUTH)) {
                        error = mac_vnode_check_lookup(ctx, dp, cnp);
                        if (error) {
                if (!(cnp->cn_flags & DONOTAUTH)) {
                        error = mac_vnode_check_lookup(ctx, dp, cnp);
                        if (error) {
-                               name_cache_unlock();
-                               return (error);
+                               NAME_CACHE_UNLOCK();
+                               goto errorout;
                        }
                }
 #endif /* MAC */
                        }
                }
 #endif /* MAC */
-               if (ttl_enabled && ((tv.tv_sec - dp->v_cred_timestamp) > dp->v_mount->mnt_authcache_ttl))
+               if (ttl_enabled &&
+                   (dp->v_mount->mnt_authcache_ttl == 0 ||
+                   ((tv.tv_sec - dp->v_cred_timestamp) > dp->v_mount->mnt_authcache_ttl))) {
                        break;
                        break;
+               }
 
                /*
                 * NAME_CACHE_LOCK holds these fields stable
 
                /*
                 * NAME_CACHE_LOCK holds these fields stable
+                *
+                * We can't cache KAUTH_VNODE_SEARCHBYANYONE for root correctly
+                * so we make an ugly check for root here. root is always
+                * allowed and breaking out of here only to find out that is
+                * authorized by virtue of being root is very very expensive.
+                * However, the check for not root is valid only for filesystems
+                * which use local authorization.
+                *
+                * XXX: Remove the check for root when we can reliably set
+                * KAUTH_VNODE_SEARCHBYANYONE as root.
                 */
                if ((dp->v_cred != ucred || !(dp->v_authorized_actions & KAUTH_VNODE_SEARCH)) &&
                 */
                if ((dp->v_cred != ucred || !(dp->v_authorized_actions & KAUTH_VNODE_SEARCH)) &&
-                   !(dp->v_authorized_actions & KAUTH_VNODE_SEARCHBYANYONE))
+                   !(dp->v_authorized_actions & KAUTH_VNODE_SEARCHBYANYONE) &&
+                   (ttl_enabled || !vfs_context_issuser(ctx)))  {
                        break;
                        break;
+               }
 
                /*
                 * indicate that we're allowed to traverse this directory...
 
                /*
                 * indicate that we're allowed to traverse this directory...
@@ -968,16 +1419,18 @@ skiprsrcfork:
                *dp_authorized = 1;
 
                if ( (cnp->cn_flags & (ISLASTCN | ISDOTDOT)) ) {
                *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_nameiop != LOOKUP)
+                               break;
+                       if (cnp->cn_flags & LOCKPARENT) 
+                               break;
+                       if (cnp->cn_flags & NOCACHE)
+                               break;
                        if (cnp->cn_flags & ISDOTDOT) {
                                /*
                                 * Force directory hardlinks to go to
                                 * file system for ".." requests.
                                 */
                        if (cnp->cn_flags & ISDOTDOT) {
                                /*
                                 * Force directory hardlinks to go to
                                 * file system for ".." requests.
                                 */
-                               if (dp && (dp->v_flag & VISHARDLINK)) {
+                               if ((dp->v_flag & VISHARDLINK)) {
                                        break;
                                }
                                /*
                                        break;
                                }
                                /*
@@ -993,19 +1446,78 @@ skiprsrcfork:
                        }
                }
 
                        }
                }
 
+               if ((cnp->cn_flags & CN_SKIPNAMECACHE)) {
+                       /*
+                        * Force lookup to go to the filesystem with
+                        * all cnp fields set up.
+                        */
+                       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;
                /*
                 * "." 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) && dp->v_parent)
-                       vp = dp->v_parent;
-               else {
+               else if ( (cnp->cn_flags & ISDOTDOT) ) {
+                       /*
+                        * If this is a chrooted process, we need to check if
+                        * the process is trying to break out of its chrooted
+                        * jail. We do that by trying to determine if dp is
+                        * a subdirectory of ndp->ni_rootdir. If we aren't
+                        * able to determine that by the v_parent pointers, we
+                        * will leave the fast path.
+                        *
+                        * Since this function may see dotdot components
+                        * many times and it has the name cache lock held for
+                        * the entire duration, we optimise this by doing this
+                        * check only once per cache_lookup_path call.
+                        * If dotdotchecked is set, it means we've done this
+                        * check once already and don't need to do it again.
+                        */
+                       if (!dotdotchecked && (ndp->ni_rootdir != rootvnode)) {
+                               vnode_t tvp = dp;
+                               boolean_t defer = FALSE;
+                               boolean_t is_subdir = FALSE;
+
+                               defer = cache_check_vnode_issubdir(tvp,
+                                   ndp->ni_rootdir, &is_subdir, &tvp);
+
+                               if (defer) {
+                                       /* defer to Filesystem */
+                                       break;
+                               } else if (!is_subdir) {
+                                       /*
+                                        * This process is trying to break  out
+                                        * of its chrooted jail, so all its
+                                        * dotdot accesses will be translated to
+                                        * its root directory.
+                                        */
+                                       vp = ndp->ni_rootdir;
+                               } else {
+                                       /*
+                                        * All good, let this dotdot access
+                                        * proceed normally
+                                        */
+                                       vp = dp->v_parent;
+                               }
+                               dotdotchecked = TRUE;
+                       } else {
+                               vp = dp->v_parent;
+                       }
+               } else {
                        if ( (vp = cache_lookup_locked(dp, cnp)) == NULLVP)
                                break;
                        if ( (vp = cache_lookup_locked(dp, cnp)) == NULLVP)
                                break;
-               }
 
 
+                       if ( (vp->v_flag & VISHARDLINK) ) {
+                               /*
+                                * The file system wants a VNOP_LOOKUP on this vnode
+                                */
+                               vp = NULL;
+                               break;
+                       }
+               }
                if ( (cnp->cn_flags & ISLASTCN) )
                        break;
 
                if ( (cnp->cn_flags & ISLASTCN) )
                        break;
 
@@ -1014,13 +1526,26 @@ skiprsrcfork:
                                vp = NULL;
                        break;
                }
                                vp = NULL;
                        break;
                }
-               if ( (mp = vp->v_mountedhere) && ((cnp->cn_flags & NOCROSSMOUNT) == 0)) {
 
 
-                       if (mp->mnt_realrootvp == NULLVP || mp->mnt_generation != mount_generation ||
-                               mp->mnt_realrootvp_vid != mp->mnt_realrootvp->v_id)
-                               break;
-                       vp = mp->mnt_realrootvp;
+               if ( (mp = vp->v_mountedhere) && ((cnp->cn_flags & NOCROSSMOUNT) == 0)) {
+                       vnode_t tmp_vp = mp->mnt_realrootvp;
+                       if (tmp_vp == NULLVP || mp->mnt_generation != mount_generation ||
+                               mp->mnt_realrootvp_vid != tmp_vp->v_id)
+                               break;
+                       vp = tmp_vp;
                }
                }
+
+#if CONFIG_TRIGGERS
+               /*
+                * After traversing all mountpoints stacked here, if we have a
+                * trigger in hand, resolve it.  Note that we don't need to 
+                * leave the fast path if the mount has already happened.
+                */
+               if (vp->v_resolve)
+                       break;
+#endif /* CONFIG_TRIGGERS */
+
+
                dp = vp;
                vp = NULLVP;
 
                dp = vp;
                vp = NULLVP;
 
@@ -1052,39 +1577,54 @@ skiprsrcfork:
                dp = NULLVP;
        } else {
 need_dp:
                dp = NULLVP;
        } else {
 need_dp:
-               /*
+               /*
                 * return the last directory we looked at
                 * return the last directory we looked at
-                * with an io reference held
+                * with an io reference held. If it was the one passed
+                * in as a result of the last iteration of VNOP_LOOKUP,
+                * it should already hold an io ref. No need to increase ref.
                 */
                 */
-               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.
-                        * 
-                        * don't necessarily return ENOENT, though, because
-                        * we really want to go back to disk and make sure it's
-                        * there or not if someone else is changing this
-                        * vnode.
-                        */
-                       return (ERESTART);
+               if (last_dp != dp){
+                       
+                       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 ((error = vnode_getwithvid_drainok(dp, vid))) {
+                               /*
+                                * failure indicates the vnode
+                                * changed identity or is being
+                                * TERMINATED... in either case
+                                * punt this lookup.
+                                * 
+                                * don't necessarily return ENOENT, though, because
+                                * we really want to go back to disk and make sure it's
+                                * there or not if someone else is changing this
+                                * vnode. That being said, the one case where we do want
+                                * to return ENOENT is when the vnode's mount point is
+                                * in the process of unmounting and we might cause a deadlock
+                                * in our attempt to take an iocount. An ENODEV error return
+                                * is from vnode_get* is an indication this but we change that
+                                * ENOENT for upper layers.
+                                */
+                               if (error == ENODEV) {
+                                       error = ENOENT;
+                               } else {
+                                       error = ERECYCLE;
+                               }
+                               goto errorout;
+                       }
                }
        }
        if (vp != NULLVP) {
                }
        }
        if (vp != NULLVP) {
-               if ( (vnode_getwithvid(vp, vvid)) ) {
+               if ( (vnode_getwithvid_drainok(vp, vvid)) ) {
                        vp = NULLVP;
 
                        /*
                        vp = NULLVP;
 
                        /*
@@ -1101,10 +1641,40 @@ need_dp:
                        }
                }
        }
                        }
                }
        }
+
        ndp->ni_dvp = dp;
        ndp->ni_vp  = vp;
 
        ndp->ni_dvp = dp;
        ndp->ni_vp  = vp;
 
-       return (0);
+#if CONFIG_TRIGGERS
+       trigger_vp = vp ? vp : dp;
+       if ((error == 0) && (trigger_vp != NULLVP) && vnode_isdir(trigger_vp)) {
+               error = vnode_trigger_resolve(trigger_vp, ndp, ctx);
+               if (error) {
+                       if (vp)
+                               vnode_put(vp);
+                       if (dp) 
+                               vnode_put(dp);
+                       goto errorout;
+               }
+       } 
+#endif /* CONFIG_TRIGGERS */
+
+errorout:
+       /* 
+        * If we came into cache_lookup_path after an iteration of the lookup loop that
+        * resulted in a call to VNOP_LOOKUP, then VNOP_LOOKUP returned a vnode with a io ref
+        * on it.  It is now the job of cache_lookup_path to drop the ref on this vnode 
+        * when it is no longer needed.  If we get to this point, and last_dp is not NULL
+        * and it is ALSO not the dvp we want to return to caller of this function, it MUST be
+        * the case that we got to a subsequent path component and this previous vnode is 
+        * no longer needed.  We can then drop the io ref on it.
+        */
+       if ((last_dp != NULLVP) && (last_dp != ndp->ni_dvp)){
+               vnode_put(last_dp);
+       }
+       
+       //initialized to 0, should be the same if no error cases occurred.
+       return error;
 }
 
 
 }
 
 
@@ -1114,14 +1684,16 @@ cache_lookup_locked(vnode_t dvp, struct componentname *cnp)
        struct namecache *ncp;
        struct nchashhead *ncpp;
        long namelen = cnp->cn_namelen;
        struct namecache *ncp;
        struct nchashhead *ncpp;
        long namelen = cnp->cn_namelen;
-       char *nameptr = cnp->cn_nameptr;
-       unsigned int hashval = (cnp->cn_hash & NCHASHMASK);
-       vnode_t vp;
+       unsigned int hashval = cnp->cn_hash;
        
        
+       if (nc_disabled) {
+               return NULL;
+       }
+
        ncpp = NCHHASH(dvp, cnp->cn_hash);
        LIST_FOREACH(ncp, ncpp, nc_hash) {
                if ((ncp->nc_dvp == dvp) && (ncp->nc_hashval == hashval)) {
        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)
+                       if (strncmp(ncp->nc_name, cnp->cn_nameptr, namelen) == 0 && ncp->nc_name[namelen] == 0)
                                break;
                }
        }
                                break;
                }
        }
@@ -1134,34 +1706,27 @@ cache_lookup_locked(vnode_t dvp, struct componentname *cnp)
        }
        NCHSTAT(ncs_goodhits);
 
        }
        NCHSTAT(ncs_goodhits);
 
-       vp = ncp->nc_vp;
-       if (vp && (vp->v_flag & VISHARDLINK)) {
-                       /*
-                        * The file system wants a VNOP_LOOKUP on this vnode
-                        */
-                       vp = NULL;
-       }
-       
-       return (vp);
+       return (ncp->nc_vp);
 }
 
 
 }
 
 
+unsigned int hash_string(const char *cp, int len);
 //
 // Have to take a len argument because we may only need to
 // hash part of a componentname.
 //
 //
 // Have to take a len argument because we may only need to
 // hash part of a componentname.
 //
-static unsigned int
+unsigned int
 hash_string(const char *cp, int len)
 {
     unsigned hash = 0;
 
     if (len) {
             while (len--) {
 hash_string(const char *cp, int len)
 {
     unsigned hash = 0;
 
     if (len) {
             while (len--) {
-                   hash ^= crc32tab[((hash >> 24) ^ (unsigned char)*cp++)];
+                   hash = crc32tab[((hash >> 24) ^ (unsigned char)*cp++)] ^ hash << 8;
            }
     } else {
             while (*cp != '\0') {
            }
     } else {
             while (*cp != '\0') {
-                   hash ^= crc32tab[((hash >> 24) ^ (unsigned char)*cp++)];
+                   hash = crc32tab[((hash >> 24) ^ (unsigned char)*cp++)] ^ hash << 8;
            }
     }
     /*
            }
     }
     /*
@@ -1196,19 +1761,26 @@ cache_lookup(struct vnode *dvp, struct vnode **vpp, struct componentname *cnp)
        struct namecache *ncp;
        struct nchashhead *ncpp;
        long namelen = cnp->cn_namelen;
        struct namecache *ncp;
        struct nchashhead *ncpp;
        long namelen = cnp->cn_namelen;
-       char *nameptr = cnp->cn_nameptr;
-       unsigned int hashval = (cnp->cn_hash & NCHASHMASK);
+       unsigned int hashval;
        boolean_t       have_exclusive = FALSE;
        uint32_t vid;
        vnode_t  vp;
 
        boolean_t       have_exclusive = FALSE;
        uint32_t vid;
        vnode_t  vp;
 
+       if (cnp->cn_hash == 0)
+               cnp->cn_hash = hash_string(cnp->cn_nameptr, cnp->cn_namelen);
+       hashval = cnp->cn_hash;
+
+       if (nc_disabled) {
+               return 0;
+       }
+
        NAME_CACHE_LOCK_SHARED();
 
        NAME_CACHE_LOCK_SHARED();
 
-       ncpp = NCHHASH(dvp, cnp->cn_hash);
 relook:
 relook:
+       ncpp = NCHHASH(dvp, cnp->cn_hash);
        LIST_FOREACH(ncp, ncpp, nc_hash) {
                if ((ncp->nc_dvp == dvp) && (ncp->nc_hashval == hashval)) {
        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)
+                       if (strncmp(ncp->nc_name, cnp->cn_nameptr, namelen) == 0 && ncp->nc_name[namelen] == 0)
                                break;
                }
        }
                                break;
                }
        }
@@ -1269,16 +1841,37 @@ relook:
 
        /*
         * We found a "negative" match, ENOENT notifies client of this match.
 
        /*
         * We found a "negative" match, ENOENT notifies client of this match.
-        * The nc_whiteout field records whether this is a whiteout.
         */
        NCHSTAT(ncs_neghits);
 
         */
        NCHSTAT(ncs_neghits);
 
-       if (ncp->nc_whiteout)
-               cnp->cn_flags |= ISWHITEOUT;
        NAME_CACHE_UNLOCK();
        return (ENOENT);
 }
 
        NAME_CACHE_UNLOCK();
        return (ENOENT);
 }
 
+const char *
+cache_enter_create(vnode_t dvp, vnode_t vp, struct componentname *cnp)
+{
+       const char *strname;
+
+        if (cnp->cn_hash == 0)
+               cnp->cn_hash = hash_string(cnp->cn_nameptr, cnp->cn_namelen);
+
+       /*
+        * grab 2 references on the string entered
+        * one for the cache_enter_locked to consume
+        * and the second to be consumed by v_name (vnode_create call point)
+        */
+       strname = add_name_internal(cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_hash, TRUE, 0);
+
+       NAME_CACHE_LOCK();
+
+       cache_enter_locked(dvp, vp, cnp, strname);
+
+       NAME_CACHE_UNLOCK();
+
+       return (strname);
+}
+
 
 /*
  * Add an entry to the cache...
 
 /*
  * Add an entry to the cache...
@@ -1298,7 +1891,7 @@ cache_enter_with_gen(struct vnode *dvp, struct vnode *vp, struct componentname *
        NAME_CACHE_LOCK();
 
        if (dvp->v_nc_generation == gen)
        NAME_CACHE_LOCK();
 
        if (dvp->v_nc_generation == gen)
-               cache_enter_locked(dvp, vp, cnp);
+               (void)cache_enter_locked(dvp, vp, cnp, NULL);
 
        NAME_CACHE_UNLOCK();
 }
 
        NAME_CACHE_UNLOCK();
 }
@@ -1310,23 +1903,34 @@ cache_enter_with_gen(struct vnode *dvp, struct vnode *vp, struct componentname *
 void
 cache_enter(struct vnode *dvp, struct vnode *vp, struct componentname *cnp)
 {
 void
 cache_enter(struct vnode *dvp, struct vnode *vp, struct componentname *cnp)
 {
+       const char *strname;
+
         if (cnp->cn_hash == 0)
                cnp->cn_hash = hash_string(cnp->cn_nameptr, cnp->cn_namelen);
 
         if (cnp->cn_hash == 0)
                cnp->cn_hash = hash_string(cnp->cn_nameptr, cnp->cn_namelen);
 
+       /*
+        * grab 1 reference on the string entered
+        * for the cache_enter_locked to consume
+        */
+       strname = add_name_internal(cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_hash, FALSE, 0);
+
        NAME_CACHE_LOCK();
 
        NAME_CACHE_LOCK();
 
-       cache_enter_locked(dvp, vp, cnp);
+       cache_enter_locked(dvp, vp, cnp, strname);
 
        NAME_CACHE_UNLOCK();
 }
 
 
 static void
 
        NAME_CACHE_UNLOCK();
 }
 
 
 static void
-cache_enter_locked(struct vnode *dvp, struct vnode *vp, struct componentname *cnp)
+cache_enter_locked(struct vnode *dvp, struct vnode *vp, struct componentname *cnp, const char *strname)
 {
         struct namecache *ncp, *negp;
        struct nchashhead *ncpp;
 
 {
         struct namecache *ncp, *negp;
        struct nchashhead *ncpp;
 
+       if (nc_disabled) 
+               return;
+
        /*
         * if the entry is for -ve caching vp is null
         */
        /*
         * if the entry is for -ve caching vp is null
         */
@@ -1335,6 +1939,8 @@ cache_enter_locked(struct vnode *dvp, struct vnode *vp, struct componentname *cn
                 * someone beat us to the punch..
                 * this vnode is already in the cache
                 */
                 * someone beat us to the punch..
                 * this vnode is already in the cache
                 */
+               if (strname != NULL)
+                       vfs_removename(strname);
                return;
        }
        /*
                return;
        }
        /*
@@ -1348,7 +1954,7 @@ cache_enter_locked(struct vnode *dvp, struct vnode *vp, struct componentname *cn
                /*
                 * Allocate one more entry
                 */
                /*
                 * Allocate one more entry
                 */
-               ncp = (struct namecache *)_MALLOC_ZONE((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
+               ncp = (struct namecache *)_MALLOC_ZONE(sizeof(*ncp), M_CACHE, M_WAITOK);
                numcache++;
        } else {
                /*
                numcache++;
        } else {
                /*
@@ -1374,8 +1980,29 @@ cache_enter_locked(struct vnode *dvp, struct vnode *vp, struct componentname *cn
        ncp->nc_vp = vp;
        ncp->nc_dvp = dvp;
        ncp->nc_hashval = cnp->cn_hash;
        ncp->nc_vp = vp;
        ncp->nc_dvp = dvp;
        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);
+
+       if (strname == NULL)
+               ncp->nc_name = add_name_internal(cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_hash, FALSE, 0);
+       else
+               ncp->nc_name = strname;
+
+       //
+       // If the bytes of the name associated with the vnode differ,
+       // use the name associated with the vnode since the file system
+       // may have set that explicitly in the case of a lookup on a
+       // case-insensitive file system where the case of the looked up
+       // name differs from what is on disk.  For more details, see:
+       //   <rdar://problem/8044697> FSEvents doesn't always decompose diacritical unicode chars in the paths of the changed directories
+       // 
+       const char *vn_name = vp ? vp->v_name : NULL;
+       unsigned int len = vn_name ? strlen(vn_name) : 0;
+       if (vn_name && ncp && ncp->nc_name && strncmp(ncp->nc_name, vn_name, len) != 0) {
+               unsigned int hash = hash_string(vn_name, len);
+               
+               vfs_removename(ncp->nc_name);
+               ncp->nc_name = add_name_internal(vn_name, len, hash, FALSE, 0);
+               ncp->nc_hashval = hash;
+       }
 
        /*
         * make us the newest entry in the cache
 
        /*
         * make us the newest entry in the cache
@@ -1407,13 +2034,10 @@ cache_enter_locked(struct vnode *dvp, struct vnode *vp, struct componentname *cn
        } else {
                /*
                 * this is a negative cache entry (vp == NULL)
        } else {
                /*
                 * this is a negative cache entry (vp == NULL)
-                * stick it on the negative cache list
-                * and record the whiteout state
+                * stick it on the negative cache list.
                 */
                TAILQ_INSERT_TAIL(&neghead, ncp, nc_un.nc_negentry);
          
                 */
                TAILQ_INSERT_TAIL(&neghead, ncp, nc_un.nc_negentry);
          
-               if (cnp->cn_flags & ISWHITEOUT)
-                       ncp->nc_whiteout = TRUE;
                ncs_negtotal++;
 
                if (ncs_negtotal > desiredNegNodes) {
                ncs_negtotal++;
 
                if (ncs_negtotal > desiredNegNodes) {
@@ -1423,8 +2047,6 @@ cache_enter_locked(struct vnode *dvp, struct vnode *vp, struct componentname *cn
                        * the oldest
                        */
                        negp = TAILQ_FIRST(&neghead);
                        * the oldest
                        */
                        negp = TAILQ_FIRST(&neghead);
-                       TAILQ_REMOVE(&neghead, negp, nc_un.nc_negentry);
-
                        cache_delete(negp, 1);
                }
        }
                        cache_delete(negp, 1);
                }
        }
@@ -1432,7 +2054,10 @@ cache_enter_locked(struct vnode *dvp, struct vnode *vp, struct componentname *cn
         * add us to the list of name cache entries that
         * are children of dvp
         */
         * add us to the list of name cache entries that
         * are children of dvp
         */
-       LIST_INSERT_HEAD(&dvp->v_ncchildren, ncp, nc_child);
+       if (vp)
+               TAILQ_INSERT_TAIL(&dvp->v_ncchildren, ncp, nc_child);
+       else
+               TAILQ_INSERT_HEAD(&dvp->v_ncchildren, ncp, nc_child);
 }
 
 
 }
 
 
@@ -1472,6 +2097,8 @@ static void init_crc32(void)
 void
 nchinit(void)
 {
 void
 nchinit(void)
 {
+       int     i;
+
        desiredNegNodes = (desiredvnodes / 10);
        desiredNodes = desiredvnodes + desiredNegNodes;
 
        desiredNegNodes = (desiredvnodes / 10);
        desiredNodes = desiredvnodes + desiredNegNodes;
 
@@ -1486,18 +2113,31 @@ nchinit(void)
 
        init_string_table();
        
 
        init_string_table();
        
-       /* Allocate mount list lock group attribute and group */
+       /* Allocate name cache lock group attribute and group */
        namecache_lck_grp_attr= lck_grp_attr_alloc_init();
 
        namecache_lck_grp = lck_grp_alloc_init("Name Cache",  namecache_lck_grp_attr);
        
        namecache_lck_grp_attr= lck_grp_attr_alloc_init();
 
        namecache_lck_grp = lck_grp_alloc_init("Name Cache",  namecache_lck_grp_attr);
        
-       /* Allocate mount list lock attribute */
+       /* Allocate name cache lock attribute */
        namecache_lck_attr = lck_attr_alloc_init();
 
        namecache_lck_attr = lck_attr_alloc_init();
 
-       /* Allocate mount list lock */
+       /* Allocate name cache lock */
        namecache_rw_lock = lck_rw_alloc_init(namecache_lck_grp, namecache_lck_attr);
 
 
        namecache_rw_lock = lck_rw_alloc_init(namecache_lck_grp, namecache_lck_attr);
 
 
+       /* Allocate string cache lock group attribute and group */
+       strcache_lck_grp_attr= lck_grp_attr_alloc_init();
+
+       strcache_lck_grp = lck_grp_alloc_init("String Cache",  strcache_lck_grp_attr);
+       
+       /* Allocate string cache lock attribute */
+       strcache_lck_attr = lck_attr_alloc_init();
+
+       /* Allocate string cache lock */
+       strtable_rw_lock = lck_rw_alloc_init(strcache_lck_grp, strcache_lck_attr);
+
+       for (i = 0; i < NUM_STRCACHE_LOCKS; i++)
+               lck_mtx_init(&strcache_mtx_locks[i], strcache_lck_grp, strcache_lck_attr);
 }
 
 void
 }
 
 void
@@ -1520,28 +2160,35 @@ name_cache_unlock(void)
 
 
 int
 
 
 int
-resize_namecache(u_int newsize)
+resize_namecache(int newsize)
 {
     struct nchashhead  *new_table;
     struct nchashhead  *old_table;
     struct nchashhead  *old_head, *head;
     struct namecache   *entry, *next;
     uint32_t           i, hashval;
 {
     struct nchashhead  *new_table;
     struct nchashhead  *old_table;
     struct nchashhead  *old_head, *head;
     struct namecache   *entry, *next;
     uint32_t           i, hashval;
-    int                        dNodes, dNegNodes;
+    int                        dNodes, dNegNodes, nelements;
     u_long             new_size, old_size;
 
     u_long             new_size, old_size;
 
+    if (newsize < 0)
+        return EINVAL;
+
     dNegNodes = (newsize / 10);
     dNodes = newsize + dNegNodes;
     dNegNodes = (newsize / 10);
     dNodes = newsize + dNegNodes;
-
     // we don't support shrinking yet
     // we don't support shrinking yet
-    if (dNodes < desiredNodes) {
-       return 0;
+    if (dNodes <= desiredNodes) {
+        return 0;
     }
     }
-    new_table = hashinit(2 * dNodes, M_CACHE, &nchashmask);
+
+    if (os_mul_overflow(dNodes, 2, &nelements)) {
+        return EINVAL;
+    }
+
+    new_table = hashinit(nelements, M_CACHE, &nchashmask);
     new_size  = nchashmask + 1;
 
     if (new_table == NULL) {
     new_size  = nchashmask + 1;
 
     if (new_table == NULL) {
-       return ENOMEM;
+        return ENOMEM;
     }
 
     NAME_CACHE_LOCK();
     }
 
     NAME_CACHE_LOCK();
@@ -1579,7 +2226,7 @@ resize_namecache(u_int newsize)
 }
 
 static void
 }
 
 static void
-cache_delete(struct namecache *ncp, int age_entry)
+cache_delete(struct namecache *ncp, int free_entry)
 {
         NCHSTAT(ncs_deletes);
 
 {
         NCHSTAT(ncs_deletes);
 
@@ -1589,7 +2236,7 @@ cache_delete(struct namecache *ncp, int age_entry)
                TAILQ_REMOVE(&neghead, ncp, nc_un.nc_negentry);
                ncs_negtotal--;
        }
                TAILQ_REMOVE(&neghead, ncp, nc_un.nc_negentry);
                ncs_negtotal--;
        }
-        LIST_REMOVE(ncp, nc_child);
+        TAILQ_REMOVE(&(ncp->nc_dvp->v_ncchildren), ncp, nc_child);
 
        LIST_REMOVE(ncp, nc_hash);
        /*
 
        LIST_REMOVE(ncp, nc_hash);
        /*
@@ -1600,16 +2247,13 @@ cache_delete(struct namecache *ncp, int age_entry)
         */
        ncp->nc_hash.le_prev = NULL;
 
         */
        ncp->nc_hash.le_prev = NULL;
 
-       if (age_entry) {
-               /*
-                * make it the next one available
-                * for cache_enter's use
-                */
+       vfs_removename(ncp->nc_name);
+       ncp->nc_name = NULL;
+       if (free_entry) {
                TAILQ_REMOVE(&nchead, ncp, nc_entry);
                TAILQ_REMOVE(&nchead, ncp, nc_entry);
-               TAILQ_INSERT_HEAD(&nchead, ncp, nc_entry);
+               FREE_ZONE(ncp, sizeof(*ncp), M_CACHE);
+               numcache--;
        }
        }
-       remove_name_locked(ncp->nc_name);
-       ncp->nc_name = NULL;
 }
 
 
 }
 
 
@@ -1623,7 +2267,10 @@ cache_purge(vnode_t vp)
         struct namecache *ncp;
        kauth_cred_t tcred = NULL;
 
         struct namecache *ncp;
        kauth_cred_t tcred = NULL;
 
-       if ((LIST_FIRST(&vp->v_nclinks) == NULL) && (LIST_FIRST(&vp->v_ncchildren) == NULL))
+       if ((LIST_FIRST(&vp->v_nclinks) == NULL) && 
+                       (TAILQ_FIRST(&vp->v_ncchildren) == NULL) &&
+                       (vp->v_cred == NOCRED) &&
+                       (vp->v_parent == NULLVP))
                return;
 
        NAME_CACHE_LOCK();
                return;
 
        NAME_CACHE_LOCK();
@@ -1634,7 +2281,7 @@ cache_purge(vnode_t vp)
        while ( (ncp = LIST_FIRST(&vp->v_nclinks)) )
                cache_delete(ncp, 1);
 
        while ( (ncp = LIST_FIRST(&vp->v_nclinks)) )
                cache_delete(ncp, 1);
 
-       while ( (ncp = LIST_FIRST(&vp->v_ncchildren)) )
+       while ( (ncp = TAILQ_FIRST(&vp->v_ncchildren)) )
                cache_delete(ncp, 1);
 
        /*
                cache_delete(ncp, 1);
 
        /*
@@ -1660,13 +2307,16 @@ cache_purge(vnode_t vp)
 void
 cache_purge_negatives(vnode_t vp)
 {
 void
 cache_purge_negatives(vnode_t vp)
 {
-       struct namecache *ncp;
+       struct namecache *ncp, *next_ncp;
 
        NAME_CACHE_LOCK();
 
 
        NAME_CACHE_LOCK();
 
-       LIST_FOREACH(ncp, &vp->v_ncchildren, nc_child)
-               if (ncp->nc_vp == NULL)
-                       cache_delete(ncp , 1);
+       TAILQ_FOREACH_SAFE(ncp, &vp->v_ncchildren, nc_child, next_ncp) {
+               if (ncp->nc_vp)
+                       break;
+
+               cache_delete(ncp, 1);
+       }
 
        NAME_CACHE_UNLOCK();
 }
 
        NAME_CACHE_UNLOCK();
 }
@@ -1704,11 +2354,8 @@ restart:
 //
 static LIST_HEAD(stringhead, string_t) *string_ref_table;
 static u_long   string_table_mask;
 //
 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 filled_buckets=0;
-static uint32_t num_dups=0;
-static uint32_t nstrings=0;
+
 
 typedef struct string_t {
     LIST_ENTRY(string_t)  hash_chain;
 
 typedef struct string_t {
     LIST_ENTRY(string_t)  hash_chain;
@@ -1717,54 +2364,62 @@ typedef struct string_t {
 } string_t;
 
 
 } string_t;
 
 
-
-static int
+static void
 resize_string_ref_table(void)
 {
 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;
-    }
+       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;
 
 
-    // do the switch!
-    old_table         = string_ref_table;
-    string_ref_table  = new_table;
-    old_mask          = string_table_mask;
-    string_table_mask = new_mask;
+       /*
+        * need to hold the table lock exclusively
+        * in order to grow the table... need to recheck
+        * the need to resize again after we've taken
+        * the lock exclusively in case some other thread
+        * beat us to the punch
+        */
+       lck_rw_lock_exclusive(strtable_rw_lock);
 
 
-    printf("resize: max chain len %d, new table size %lu\n",
-          max_chain_len, new_mask + 1);
-    max_chain_len   = 0;
-    long_chain_head = NULL;
-    filled_buckets  = 0;
+       if (4 * filled_buckets < ((string_table_mask + 1) * 3)) {
+               lck_rw_done(strtable_rw_lock);
+               return;
+       }
+       new_table = hashinit((string_table_mask + 1) * 2, M_CACHE, &new_mask);
 
 
-    // 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((const char *)entry->str, 0);
-           head = &string_ref_table[hashval & string_table_mask];
-           if (head->lh_first == NULL) {
-               filled_buckets++;
-           }
+       if (new_table == NULL) {
+               printf("failed to resize the hash table.\n");
+               lck_rw_done(strtable_rw_lock);
+               return;
+       }
 
 
-           next = entry->hash_chain.le_next;
-           LIST_INSERT_HEAD(head, entry, hash_chain);
+       // do the switch!
+       old_table         = string_ref_table;
+       string_ref_table  = new_table;
+       old_mask          = string_table_mask;
+       string_table_mask = new_mask;
+       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((const char *)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);
+       lck_rw_done(strtable_rw_lock);
 
 
-    return 0;
+       FREE(old_table, M_CACHE);
 }
 
 
 }
 
 
@@ -1776,131 +2431,148 @@ init_string_table(void)
 
 
 const char *
 
 
 const char *
-vfs_addname(const char *name, size_t len, u_int hashval, u_int flags)
+vfs_addname(const char *name, uint32_t len, u_int hashval, u_int flags)
 {
 {
-        const char * ptr;
-
-       NAME_CACHE_LOCK();
-       ptr = add_name_locked(name, len, hashval, flags);
-       NAME_CACHE_UNLOCK();
-
-       return(ptr);
+       return (add_name_internal(name, len, hashval, FALSE, flags));
 }
 
 }
 
+
 static const char *
 static const char *
-add_name_locked(const char *name, size_t len, u_int hashval, __unused u_int flags)
+add_name_internal(const char *name, uint32_t len, u_int hashval, boolean_t need_extra_ref, __unused u_int flags)
 {
 {
-    struct stringhead *head;
-    string_t          *entry;
-    uint32_t          chain_len = 0;
-    char              *ptr;
+       struct stringhead *head;
+       string_t          *entry;
+       uint32_t          chain_len = 0;
+       uint32_t          hash_index;
+        uint32_t         lock_index;
+       char              *ptr;
     
     
-    //
-    // 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);
-    }
-
-    //
-    // if the length already accounts for the null-byte, then
-    // subtract one so later on we don't index past the end
-    // of the string.
-    //
-    if (len > 0 && name[len-1] == '\0') {
-       len--;
-    }
+       if (len > MAXPATHLEN)
+               len = MAXPATHLEN;
 
 
-    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 the length already accounts for the null-byte, then
+        * subtract one so later on we don't index past the end
+        * of the string.
+        */
+       if (len > 0 && name[len-1] == '\0') {
+               len--;
+       }
+       if (hashval == 0) {
+               hashval = hash_string(name, len);
        }
        }
-    }
 
 
-    if (entry == NULL) {
-       // it wasn't already there so add it.
-       MALLOC(entry, string_t *, sizeof(string_t) + len + 1, M_TEMP, M_WAITOK);
+       /*
+        * take this lock 'shared' to keep the hash stable
+        * if someone else decides to grow the pool they
+        * will take this lock exclusively
+        */
+       lck_rw_lock_shared(strtable_rw_lock);
 
 
-       // 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++;
+       /*
+        * If the table gets more than 3/4 full, resize it
+        */
+       if (4 * filled_buckets >= ((string_table_mask + 1) * 3)) {
+               lck_rw_done(strtable_rw_lock);
+
+               resize_string_ref_table();
+
+               lck_rw_lock_shared(strtable_rw_lock);
        }
        }
+       hash_index = hashval & string_table_mask;
+       lock_index = hash_index % NUM_STRCACHE_LOCKS;
 
 
-       ptr = (char *)((char *)entry + sizeof(string_t));
-       strncpy(ptr, name, len);
-       ptr[len] = '\0';
-       entry->str = ptr;
-       entry->refcount = 1;
-       LIST_INSERT_HEAD(head, entry, hash_chain);
+       head = &string_ref_table[hash_index];
 
 
-       if (chain_len > max_chain_len) {
-           max_chain_len   = chain_len;
-           long_chain_head = head;
+       lck_mtx_lock_spin(&strcache_mtx_locks[lock_index]);
+
+       for (entry = head->lh_first; entry != NULL; chain_len++, entry = entry->hash_chain.le_next) {
+               if (strncmp(entry->str, name, len) == 0 && entry->str[len] == 0) {
+                       entry->refcount++;
+                       break;
+               }
        }
        }
+       if (entry == NULL) {
+               lck_mtx_convert_spin(&strcache_mtx_locks[lock_index]);
+               /*
+                * it wasn't already there so add it.
+                */
+               MALLOC(entry, string_t *, sizeof(string_t) + len + 1, M_TEMP, M_WAITOK);
 
 
-       nstrings++;
-    }
+               if (head->lh_first == NULL) {
+                       OSAddAtomic(1, &filled_buckets);
+               }
+               ptr = (char *)((char *)entry + sizeof(string_t));
+               strncpy(ptr, name, len);
+               ptr[len] = '\0';
+               entry->str = ptr;
+               entry->refcount = 1;
+               LIST_INSERT_HEAD(head, entry, hash_chain);
+       }
+       if (need_extra_ref == TRUE)
+               entry->refcount++;
     
     
-    return (const char *)entry->str;
+       lck_mtx_unlock(&strcache_mtx_locks[lock_index]);
+       lck_rw_done(strtable_rw_lock);
+
+       return (const char *)entry->str;
 }
 
 }
 
+
 int
 vfs_removename(const char *nameref)
 {
 int
 vfs_removename(const char *nameref)
 {
-       int i;
+       struct stringhead *head;
+       string_t          *entry;
+       uint32_t           hashval;
+       uint32_t           hash_index;
+        uint32_t          lock_index;
+       int                retval = ENOENT;
 
 
-       NAME_CACHE_LOCK();
-       i = remove_name_locked(nameref);
-       NAME_CACHE_UNLOCK();
+       hashval = hash_string(nameref, 0);
 
 
-       return(i);
-       
-}
+       /*
+        * take this lock 'shared' to keep the hash stable
+        * if someone else decides to grow the pool they
+        * will take this lock exclusively
+        */
+       lck_rw_lock_shared(strtable_rw_lock);
+       /*
+        * must compute the head behind the table lock
+        * since the size and location of the table
+        * can change on the fly
+        */
+       hash_index = hashval & string_table_mask;
+       lock_index = hash_index % NUM_STRCACHE_LOCKS;
 
 
+       head = &string_ref_table[hash_index];
 
 
-static int
-remove_name_locked(const char *nameref)
-{
-    struct stringhead *head;
-    string_t          *entry;
-    uint32_t           hashval;
-    const 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 == 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--;
+       lck_mtx_lock_spin(&strcache_mtx_locks[lock_index]);
 
 
-               FREE(entry, M_TEMP);
-           } else {
-               num_dups--;
-           }
+       for (entry = head->lh_first; entry != NULL; entry = entry->hash_chain.le_next) {
+               if (entry->str == nameref) {
+                       entry->refcount--;
 
 
-           return 0;
+                       if (entry->refcount == 0) {
+                               LIST_REMOVE(entry, hash_chain);
+
+                               if (head->lh_first == NULL) {
+                                       OSAddAtomic(-1, &filled_buckets);
+                               }
+                       } else {
+                               entry = NULL;
+                       }
+                       retval = 0;
+                       break;
+               }
        }
        }
-    }
+       lck_mtx_unlock(&strcache_mtx_locks[lock_index]);
+       lck_rw_done(strtable_rw_lock);
 
 
-    return ENOENT;
+       if (entry != NULL)
+               FREE(entry, M_TEMP);
+
+       return retval;
 }
 
 
 }
 
 
@@ -1912,7 +2584,7 @@ dump_string_table(void)
     string_t          *entry;
     u_long            i;
     
     string_t          *entry;
     u_long            i;
     
-    NAME_CACHE_LOCK_SHARED();
+    lck_rw_lock_shared(strtable_rw_lock);
 
     for (i = 0; i <= string_table_mask; i++) {
        head = &string_ref_table[i];
 
     for (i = 0; i <= string_table_mask; i++) {
        head = &string_ref_table[i];
@@ -1920,6 +2592,6 @@ dump_string_table(void)
            printf("%6d - %s\n", entry->refcount, entry->str);
        }
     }
            printf("%6d - %s\n", entry->refcount, entry->str);
        }
     }
-    NAME_CACHE_UNLOCK();
+    lck_rw_done(strtable_rw_lock);
 }
 #endif /* DUMP_STRING_TABLE */
 }
 #endif /* DUMP_STRING_TABLE */