X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/935ed37a5c468c8a1c07408573c08b8b7ef80e8b..e8c3f78193f1895ea514044358b93b1add9322f3:/bsd/vfs/vfs_cache.c?ds=sidebyside diff --git a/bsd/vfs/vfs_cache.c b/bsd/vfs/vfs_cache.c index 95a07d69a..56c69754c 100644 --- a/bsd/vfs/vfs_cache.c +++ b/bsd/vfs/vfs_cache.c @@ -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@ * @@ -75,12 +75,14 @@ #include #include #include +#include #include #include #include #include #include #include +#include #if CONFIG_MACF #include @@ -114,6 +116,7 @@ long numcache; /* number of cache entries allocated */ 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 */ @@ -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_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 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_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 /* @@ -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 */ -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]) +/* + * 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 -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; @@ -192,24 +434,51 @@ build_path(vnode_t first_vp, char *buff, int buflen, int *outlen, int flags, vfs int ret = 0; int fixhardlink; - if (first_vp == NULLVP) { + if (first_vp == NULLVP) 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; + 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) { - return (EINVAL); + ret = EINVAL; + goto out_unlock; } if ((vp->v_mount->mnt_flag & MNT_ROOTFS) || (vp == proc_root_dir_vp)) { /* @@ -217,14 +486,26 @@ again: * just "/". */ *--end = '/'; - goto out; + + goto out_unlock; } 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)) { + 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 @@ -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); + if (!fixhardlink) { str = vp->v_name; + if (str == NULL || *str == '\0') { - if (vp->v_parent != NULL) { + if (vp->v_parent != NULL) ret = EINVAL; - } else { + else ret = ENOENT; - } - break; + goto out_unlock; } len = strlen(str); /* @@ -249,15 +531,18 @@ again: */ if ((end - buff) < (len + 1)) { ret = ENOSPC; - break; + goto out_unlock; } - /* Copy the name backwards. */ + /* + * Copy the name backwards. + */ str += len; - for (; len > 0; len--) { + for (; len > 0; len--) *--end = *--str; - } - /* Add a path separator. */ + /* + * Add a path separator. + */ *--end = '/'; } @@ -265,48 +550,81 @@ again: * 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; - // 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) { - 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; - 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; - break; + goto out_unlock; } - vid = vp->v_id; + vid = vp->v_id; + 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); + 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); if (fixhardlink) { 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; @@ -316,91 +634,133 @@ again: } len = strlen(str); - /* Check that there's enough space. */ + /* + * 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. */ + /* + * 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)) { - vnode_put(vp); 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; - } - if (!fixhardlink && (vp->v_parent != dvp)) { + + if (!fixhardlink && (vp->v_parent != dvp)) 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_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. */ - 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: - /* 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); - - *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); } +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 @@ -437,11 +797,11 @@ const char * vnode_getname(vnode_t vp) { const char *name = NULL; - - NAME_CACHE_LOCK(); + + NAME_CACHE_LOCK_SHARED(); 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); @@ -450,13 +810,54 @@ vnode_getname(vnode_t vp) 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 @@ -472,20 +873,20 @@ vnode_putname(const char *name) * 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; -#if NAMEDSTREAMS 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 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); @@ -493,41 +894,69 @@ vnode_update_identity(vnode_t vp, vnode_t dvp, const char *name, int name_len, i kusecountbumped = 1; vnode_unlock(dvp); } -#endif } 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)) ) { - if ( (flags & VNODE_UPDATE_NAME) && (name != vp->v_name) ) { - if (vp->v_name != NULL) { - remove_name_locked(vp->v_name); - vp->v_name = NULL; + 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); + + 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 NAMEDSTREAMS /* Back-out the ref we took if we lost a race for vp->v_parent. */ if (kusecountbumped) { vnode_lock_spin(dvp); @@ -535,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); } -#endif 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); } -#endif ut = get_bsdthread_info(current_thread()); /* @@ -563,7 +989,7 @@ vnode_update_identity(vnode_t vp, vnode_t dvp, const char *name, int name_len, i while ( (vp = old_parentvp) != NULLVP ) { - vnode_lock(vp); + vnode_lock_spin(vp); vnode_rele_internal(vp, 0, 0, 1); /* @@ -577,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 * - * 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 @@ -701,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; + /* 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 @@ -830,7 +1263,7 @@ boolean_t vnode_cache_is_stale(vnode_t vp) */ int cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp, - vfs_context_t ctx, int *trailing_slash, int *dp_authorized, vnode_t last_dp) + vfs_context_t ctx, int *dp_authorized, vnode_t last_dp) { char *cp; /* pointer into pathname argument */ int vid; @@ -840,12 +1273,17 @@ cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp, kauth_cred_t ucred; boolean_t ttl_enabled = FALSE; struct timeval tv; - mount_t mp; + mount_t mp; unsigned int hash; int error = 0; + boolean_t dotdotchecked = FALSE; + +#if CONFIG_TRIGGERS + vnode_t trigger_vp; +#endif /* CONFIG_TRIGGERS */ ucred = vfs_context_ucred(ctx); - *trailing_slash = 0; + ndp->ni_flag &= ~(NAMEI_TRAILINGSLASH); NAME_CACHE_LOCK_SHARED(); @@ -854,7 +1292,7 @@ cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp, microuptime(&tv); } for (;;) { - /* + /* * Search a directory. * * The cn_hash value is for use by cache_lookup @@ -865,7 +1303,7 @@ cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp, 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 @@ -892,7 +1330,7 @@ cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp, ndp->ni_pathlen--; if (*cp == '\0') { - *trailing_slash = 1; + ndp->ni_flag |= NAMEI_TRAILINGSLASH; *ndp->ni_next = '\0'; } } @@ -932,7 +1370,7 @@ skiprsrcfork: #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 @@ -942,20 +1380,35 @@ skiprsrcfork: if (!(cnp->cn_flags & DONOTAUTH)) { error = mac_vnode_check_lookup(ctx, dp, cnp); if (error) { - name_cache_unlock(); + NAME_CACHE_UNLOCK(); goto errorout; } } #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; + } /* * 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)) && - !(dp->v_authorized_actions & KAUTH_VNODE_SEARCHBYANYONE)) + !(dp->v_authorized_actions & KAUTH_VNODE_SEARCHBYANYONE) && + (ttl_enabled || !vfs_context_issuser(ctx))) { break; + } /* * indicate that we're allowed to traverse this directory... @@ -966,16 +1419,18 @@ skiprsrcfork: *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 (dp && (dp->v_flag & VISHARDLINK)) { + if ((dp->v_flag & VISHARDLINK)) { break; } /* @@ -991,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; - 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->v_flag & VISHARDLINK) ) { + /* + * The file system wants a VNOP_LOOKUP on this vnode + */ + vp = NULL; + break; + } + } if ( (cnp->cn_flags & ISLASTCN) ) break; @@ -1012,13 +1526,26 @@ skiprsrcfork: 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; @@ -1070,7 +1597,7 @@ need_dp: * immediately w/o waiting... it always succeeds */ vnode_get(dp); - } else if ( (vnode_getwithvid(dp, vid)) ) { + } else if ((error = vnode_getwithvid_drainok(dp, vid))) { /* * failure indicates the vnode * changed identity or is being @@ -1080,15 +1607,24 @@ need_dp: * 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. + * 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. */ - error = ERECYCLE; + if (error == ENODEV) { + error = ENOENT; + } else { + error = ERECYCLE; + } goto errorout; } } } if (vp != NULLVP) { - if ( (vnode_getwithvid(vp, vvid)) ) { + if ( (vnode_getwithvid_drainok(vp, vvid)) ) { vp = NULLVP; /* @@ -1105,9 +1641,24 @@ need_dp: } } } + ndp->ni_dvp = dp; ndp->ni_vp = vp; +#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 @@ -1133,14 +1684,16 @@ cache_lookup_locked(vnode_t dvp, struct componentname *cnp) 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)) { - 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; } } @@ -1153,34 +1706,27 @@ cache_lookup_locked(vnode_t dvp, struct componentname *cnp) } 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. // -static unsigned int +unsigned int 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') { - hash ^= crc32tab[((hash >> 24) ^ (unsigned char)*cp++)]; + hash = crc32tab[((hash >> 24) ^ (unsigned char)*cp++)] ^ hash << 8; } } /* @@ -1215,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; - 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; + 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(); - ncpp = NCHHASH(dvp, cnp->cn_hash); relook: + 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; } } @@ -1288,16 +1841,37 @@ relook: /* * We found a "negative" match, ENOENT notifies client of this match. - * The nc_whiteout field records whether this is a whiteout. */ NCHSTAT(ncs_neghits); - if (ncp->nc_whiteout) - cnp->cn_flags |= ISWHITEOUT; 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... @@ -1317,7 +1891,7 @@ cache_enter_with_gen(struct vnode *dvp, struct vnode *vp, struct componentname * 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(); } @@ -1329,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) { + const char *strname; + 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(); - cache_enter_locked(dvp, vp, cnp); + cache_enter_locked(dvp, vp, cnp, strname); 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; + if (nc_disabled) + return; + /* * if the entry is for -ve caching vp is null */ @@ -1354,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 */ + if (strname != NULL) + vfs_removename(strname); return; } /* @@ -1367,7 +1954,7 @@ cache_enter_locked(struct vnode *dvp, struct vnode *vp, struct componentname *cn /* * 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 { /* @@ -1393,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_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: + // 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 @@ -1426,13 +2034,10 @@ cache_enter_locked(struct vnode *dvp, struct vnode *vp, struct componentname *cn } 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); - if (cnp->cn_flags & ISWHITEOUT) - ncp->nc_whiteout = TRUE; ncs_negtotal++; if (ncs_negtotal > desiredNegNodes) { @@ -1442,8 +2047,6 @@ cache_enter_locked(struct vnode *dvp, struct vnode *vp, struct componentname *cn * the oldest */ negp = TAILQ_FIRST(&neghead); - TAILQ_REMOVE(&neghead, negp, nc_un.nc_negentry); - cache_delete(negp, 1); } } @@ -1451,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 */ - 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); } @@ -1491,6 +2097,8 @@ static void init_crc32(void) void nchinit(void) { + int i; + desiredNegNodes = (desiredvnodes / 10); desiredNodes = desiredvnodes + desiredNegNodes; @@ -1505,18 +2113,31 @@ nchinit(void) 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); - /* Allocate mount list lock attribute */ + /* Allocate name cache lock attribute */ 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); + /* 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 @@ -1539,28 +2160,35 @@ name_cache_unlock(void) 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; - int dNodes, dNegNodes; + int dNodes, dNegNodes, nelements; u_long new_size, old_size; + if (newsize < 0) + return EINVAL; + dNegNodes = (newsize / 10); dNodes = newsize + dNegNodes; - // 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) { - return ENOMEM; + return ENOMEM; } NAME_CACHE_LOCK(); @@ -1598,7 +2226,7 @@ resize_namecache(u_int newsize) } static void -cache_delete(struct namecache *ncp, int age_entry) +cache_delete(struct namecache *ncp, int free_entry) { NCHSTAT(ncs_deletes); @@ -1608,7 +2236,7 @@ cache_delete(struct namecache *ncp, int age_entry) 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); /* @@ -1619,16 +2247,13 @@ cache_delete(struct namecache *ncp, int age_entry) */ 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_INSERT_HEAD(&nchead, ncp, nc_entry); + FREE_ZONE(ncp, sizeof(*ncp), M_CACHE); + numcache--; } - remove_name_locked(ncp->nc_name); - ncp->nc_name = NULL; } @@ -1642,7 +2267,10 @@ cache_purge(vnode_t vp) struct namecache *ncp; kauth_cred_t tcred = NULL; - if ((LIST_FIRST(&vp->v_nclinks) == NULL) && (LIST_FIRST(&vp->v_ncchildren) == NULL) && (vp->v_cred == NOCRED)) + 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(); @@ -1653,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_ncchildren)) ) + while ( (ncp = TAILQ_FIRST(&vp->v_ncchildren)) ) cache_delete(ncp, 1); /* @@ -1679,13 +2307,16 @@ cache_purge(vnode_t vp) void cache_purge_negatives(vnode_t vp) { - struct namecache *ncp; + struct namecache *ncp, *next_ncp; 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(); } @@ -1723,11 +2354,8 @@ restart: // static LIST_HEAD(stringhead, string_t) *string_ref_table; static u_long string_table_mask; -static uint32_t max_chain_len=0; -static struct stringhead *long_chain_head=NULL; static uint32_t filled_buckets=0; -static uint32_t num_dups=0; -static uint32_t nstrings=0; + typedef struct string_t { LIST_ENTRY(string_t) hash_chain; @@ -1736,54 +2364,62 @@ typedef struct string_t { } string_t; - -static int +static 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); } @@ -1795,131 +2431,148 @@ init_string_table(void) 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 * -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; + + head = &string_ref_table[hash_index]; - 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); + lck_mtx_lock_spin(&strcache_mtx_locks[lock_index]); - if (chain_len > max_chain_len) { - max_chain_len = chain_len; - long_chain_head = head; + 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 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--; + + if (entry->refcount == 0) { + LIST_REMOVE(entry, hash_chain); - return 0; + 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); + + if (entry != NULL) + FREE(entry, M_TEMP); - return ENOENT; + return retval; } @@ -1931,7 +2584,7 @@ dump_string_table(void) 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]; @@ -1939,6 +2592,6 @@ dump_string_table(void) printf("%6d - %s\n", entry->refcount, entry->str); } } - NAME_CACHE_UNLOCK(); + lck_rw_done(strtable_rw_lock); } #endif /* DUMP_STRING_TABLE */