X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/d7e50217d7adf6e52786a38bcaa4cd698cb9a79e..0b4c1975fb5e4eccf1012a35081f7e7799b81046:/bsd/hfs/hfs_chash.c diff --git a/bsd/hfs/hfs_chash.c b/bsd/hfs/hfs_chash.c index eb2204aa8..b2db58e75 100644 --- a/bsd/hfs/hfs_chash.c +++ b/bsd/hfs/hfs_chash.c @@ -1,16 +1,19 @@ /* - * Copyright (c) 2002 Apple Computer, Inc. All rights reserved. + * Copyright (c) 2002-2008 Apple Computer, Inc. All rights reserved. * - * @APPLE_LICENSE_HEADER_START@ - * - * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved. + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ * * This file contains Original Code and/or Modifications of Original Code * as defined in and that are subject to the Apple Public Source License * Version 2.0 (the 'License'). You may not use this file except in - * compliance with the License. Please obtain a copy of the License at - * http://www.opensource.apple.com/apsl/ and read it before using this - * file. + * compliance with the License. The rights granted to you under the License + * may not be used to create, or enable the creation or redistribution of, + * unlawful or unlicensed copies of an Apple operating system, or to + * circumvent, violate, or enable the circumvention or violation of, any + * terms of an Apple operating system software license agreement. + * + * Please obtain a copy of the License at + * http://www.opensource.apple.com/apsl/ and read it before using this file. * * The Original Code and all software distributed under the License are * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER @@ -20,7 +23,7 @@ * Please see the License for the specific language governing rights and * limitations under the License. * - * @APPLE_LICENSE_HEADER_END@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ */ /* @@ -62,20 +65,26 @@ #include #include #include +#include #include #include #include + +#include "hfs.h" /* XXX bringup */ #include "hfs_cnode.h" +extern lck_attr_t * hfs_lock_attr; +extern lck_grp_t * hfs_mutex_group; +extern lck_grp_t * hfs_rwlock_group; + +lck_grp_t * chash_lck_grp; +lck_grp_attr_t * chash_lck_grp_attr; +lck_attr_t * chash_lck_attr; + + +#define CNODEHASH(hfsmp, inum) (&hfsmp->hfs_cnodehashtbl[(inum) & hfsmp->hfs_cnodehash]) -/* - * Structures associated with cnode caching. - */ -LIST_HEAD(cnodehashhead, cnode) *cnodehashtbl; -u_long cnodehash; /* size of hash table - 1 */ -#define CNODEHASH(device, inum) (&cnodehashtbl[((device) + (inum)) & cnodehash]) -struct slock hfs_chash_slock; /* * Initialize cnode hash table. @@ -84,8 +93,51 @@ __private_extern__ void hfs_chashinit() { - cnodehashtbl = hashinit(desiredvnodes, M_HFSMNT, &cnodehash); - simple_lock_init(&hfs_chash_slock); + chash_lck_grp_attr= lck_grp_attr_alloc_init(); + chash_lck_grp = lck_grp_alloc_init("cnode_hash", chash_lck_grp_attr); + chash_lck_attr = lck_attr_alloc_init(); +} + +static void hfs_chash_lock(struct hfsmount *hfsmp) +{ + lck_mtx_lock(&hfsmp->hfs_chash_mutex); +} + +static void hfs_chash_lock_spin(struct hfsmount *hfsmp) +{ + lck_mtx_lock_spin(&hfsmp->hfs_chash_mutex); +} + +#ifdef i386 +static void hfs_chash_lock_convert (struct hfsmount *hfsmp) +#else +static void hfs_chash_lock_convert (__unused struct hfsmount *hfsmp) +#endif +{ + lck_mtx_convert_spin(&hfsmp->hfs_chash_mutex); +} + +static void hfs_chash_unlock(struct hfsmount *hfsmp) +{ + lck_mtx_unlock(&hfsmp->hfs_chash_mutex); +} + +__private_extern__ +void +hfs_chashinit_finish(struct hfsmount *hfsmp) +{ + lck_mtx_init(&hfsmp->hfs_chash_mutex, chash_lck_grp, chash_lck_attr); + + hfsmp->hfs_cnodehashtbl = hashinit(desiredvnodes / 4, M_HFSMNT, &hfsmp->hfs_cnodehash); +} + +__private_extern__ +void +hfs_delete_chash(struct hfsmount *hfsmp) +{ + lck_mtx_destroy(&hfsmp->hfs_chash_mutex, chash_lck_grp); + + FREE(hfsmp->hfs_cnodehashtbl, M_HFSMNT); } @@ -93,123 +145,281 @@ hfs_chashinit() * Use the device, inum pair to find the incore cnode. * * If it is in core, but locked, wait for it. - * - * If the requested vnode (fork) is not available, then - * take a reference on the other vnode (fork) so that - * the upcoming getnewvnode can not aquire it. */ __private_extern__ -struct cnode * -hfs_chashget(dev_t dev, ino_t inum, int wantrsrc, - struct vnode **vpp, struct vnode **rvpp) +struct vnode * +hfs_chash_getvnode(struct hfsmount *hfsmp, ino_t inum, int wantrsrc, int skiplock) { - struct proc *p = current_proc(); struct cnode *cp; struct vnode *vp; int error; + u_int32_t vid; - *vpp = NULLVP; - *rvpp = NULLVP; /* * Go through the hash list * If a cnode is in the process of being cleaned out or being * allocated, wait for it to be finished and then try again. */ loop: - simple_lock(&hfs_chash_slock); - for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) { - if ((cp->c_fileid != inum) || (cp->c_dev != dev)) + hfs_chash_lock_spin(hfsmp); + + for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) { + if (cp->c_fileid != inum) continue; - if (ISSET(cp->c_flag, C_ALLOC)) { - /* - * cnode is being created. Wait for it to finish. - */ - SET(cp->c_flag, C_WALLOC); - simple_unlock(&hfs_chash_slock); - (void) tsleep((caddr_t)cp, PINOD, "hfs_chashget-1", 0); + /* Wait if cnode is being created or reclaimed. */ + if (ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) { + SET(cp->c_hflag, H_WAITING); + + (void) msleep(cp, &hfsmp->hfs_chash_mutex, PDROP | PINOD, + "hfs_chash_getvnode", 0); goto loop; - } - if (ISSET(cp->c_flag, C_TRANSIT)) { - /* - * cnode is getting reclaimed wait for - * the operation to complete and return - * error + } + /* Obtain the desired vnode. */ + vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp; + if (vp == NULLVP) + goto exit; + + vid = vnode_vid(vp); + hfs_chash_unlock(hfsmp); + + if ((error = vnode_getwithvid(vp, vid))) { + /* + * If vnode is being reclaimed, or has + * already changed identity, no need to wait */ - SET(cp->c_flag, C_WTRANSIT); - simple_unlock(&hfs_chash_slock); - (void)tsleep((caddr_t)cp, PINOD, "hfs_chashget-2", 0); - goto loop; + return (NULL); + } + if (!skiplock && hfs_lock(cp, HFS_EXCLUSIVE_LOCK) != 0) { + vnode_put(vp); + return (NULL); } - if (cp->c_flag & (C_NOEXISTS | C_DELETED)) + + /* + * Skip cnodes that are not in the name space anymore + * we need to check with the cnode lock held because + * we may have blocked acquiring the vnode ref or the + * lock on the cnode which would allow the node to be + * unlinked + */ + if (cp->c_flag & (C_NOEXISTS | C_DELETED)) { + if (!skiplock) + hfs_unlock(cp); + vnode_put(vp); + + return (NULL); + } + return (vp); + } +exit: + hfs_chash_unlock(hfsmp); + return (NULL); +} + + +/* + * Use the device, fileid pair to snoop an incore cnode. + */ +__private_extern__ +int +hfs_chash_snoop(struct hfsmount *hfsmp, ino_t inum, int (*callout)(const struct cat_desc *, + const struct cat_attr *, void *), void * arg) +{ + struct cnode *cp; + int result = ENOENT; + + /* + * Go through the hash list + * If a cnode is in the process of being cleaned out or being + * allocated, wait for it to be finished and then try again. + */ + hfs_chash_lock(hfsmp); + + for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) { + if (cp->c_fileid != inum) continue; + /* Skip cnodes being created or reclaimed. */ + if (!ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) { + result = callout(&cp->c_desc, &cp->c_attr, arg); + } + break; + } + hfs_chash_unlock(hfsmp); + + return (result); +} + + +/* + * Use the device, fileid pair to find the incore cnode. + * If no cnode if found one is created + * + * If it is in core, but locked, wait for it. + * + * If the cnode is C_DELETED, then return NULL since that + * inum is no longer valid for lookups (open-unlinked file). + */ +__private_extern__ +struct cnode * +hfs_chash_getcnode(struct hfsmount *hfsmp, ino_t inum, struct vnode **vpp, int wantrsrc, int skiplock) +{ + struct cnode *cp; + struct cnode *ncp = NULL; + vnode_t vp; + u_int32_t vid; + + /* + * Go through the hash list + * If a cnode is in the process of being cleaned out or being + * allocated, wait for it to be finished and then try again. + */ +loop: + hfs_chash_lock_spin(hfsmp); +loop_with_lock: + for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) { + if (cp->c_fileid != inum) + continue; /* - * Try getting the desired vnode first. If - * it isn't available then take a reference - * on the other vnode. + * Wait if cnode is being created, attached to or reclaimed. */ - vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp; - if (vp == NULLVP) - vp = wantrsrc ? cp->c_vp : cp->c_rsrc_vp; - if (vp == NULLVP) - panic("hfs_chashget: orphaned cnode in hash"); + if (ISSET(cp->c_hflag, H_ALLOC | H_ATTACH | H_TRANSIT)) { + SET(cp->c_hflag, H_WAITING); - simple_lock(&vp->v_interlock); - simple_unlock(&hfs_chash_slock); - if (vget(vp, LK_EXCLUSIVE | LK_INTERLOCK, p)) - goto loop; - else if (cp->c_flag & C_NOEXISTS) { + (void) msleep(cp, &hfsmp->hfs_chash_mutex, PINOD, + "hfs_chash_getcnode", 0); + goto loop_with_lock; + } + vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp; + if (vp == NULL) { /* - * While we were blocked the cnode got deleted. + * The desired vnode isn't there so tag the cnode. */ - vput(vp); - goto loop; + SET(cp->c_hflag, H_ATTACH); + + hfs_chash_unlock(hfsmp); + } else { + vid = vnode_vid(vp); + + hfs_chash_unlock(hfsmp); + + if (vnode_getwithvid(vp, vid)) + goto loop; + } + if (ncp) { + /* + * someone else won the race to create + * this cnode and add it to the hash + * just dump our allocation + */ + FREE_ZONE(ncp, sizeof(struct cnode), M_HFSNODE); + ncp = NULL; + } + + if (!skiplock) { + hfs_lock(cp, HFS_FORCE_LOCK); } - if (VNODE_IS_RSRC(vp)) - *rvpp = vp; - else - *vpp = vp; /* - * Note that vget can block before aquiring the - * cnode lock. So we need to check if the vnode - * we wanted was created while we blocked. + * Skip cnodes that are not in the name space anymore + * we need to check with the cnode lock held because + * we may have blocked acquiring the vnode ref or the + * lock on the cnode which would allow the node to be + * unlinked. + * + * Don't return a cnode in this case since the inum + * is no longer valid for lookups. */ - if (wantrsrc && *rvpp == NULL && cp->c_rsrc_vp) { - error = vget(cp->c_rsrc_vp, 0, p); - vput(*vpp); /* ref no longer needed */ - *vpp = NULL; - if (error) - goto loop; - *rvpp = cp->c_rsrc_vp; - - } else if (!wantrsrc && *vpp == NULL && cp->c_vp) { - error = vget(cp->c_vp, 0, p); - vput(*rvpp); /* ref no longer needed */ - *rvpp = NULL; - if (error) - goto loop; - *vpp = cp->c_vp; + if ((cp->c_flag & (C_NOEXISTS | C_DELETED)) && !wantrsrc) { + if (!skiplock) + hfs_unlock(cp); + if (vp != NULLVP) { + vnode_put(vp); + } else { + hfs_chash_lock_spin(hfsmp); + CLR(cp->c_hflag, H_ATTACH); + if (ISSET(cp->c_hflag, H_WAITING)) { + CLR(cp->c_hflag, H_WAITING); + wakeup((caddr_t)cp); + } + hfs_chash_unlock(hfsmp); + } + vp = NULL; + cp = NULL; } + *vpp = vp; return (cp); } - simple_unlock(&hfs_chash_slock); - return (NULL); + + /* + * Allocate a new cnode + */ + if (skiplock && !wantrsrc) + panic("%s - should never get here when skiplock is set \n", __FUNCTION__); + + if (ncp == NULL) { + hfs_chash_unlock(hfsmp); + + MALLOC_ZONE(ncp, struct cnode *, sizeof(struct cnode), M_HFSNODE, M_WAITOK); + /* + * since we dropped the chash lock, + * we need to go back and re-verify + * that this node hasn't come into + * existence... + */ + goto loop; + } + hfs_chash_lock_convert(hfsmp); + + bzero(ncp, sizeof(struct cnode)); + SET(ncp->c_hflag, H_ALLOC); + ncp->c_fileid = inum; + TAILQ_INIT(&ncp->c_hintlist); /* make the list empty */ + TAILQ_INIT(&ncp->c_originlist); + + lck_rw_init(&ncp->c_rwlock, hfs_rwlock_group, hfs_lock_attr); + if (!skiplock) + (void) hfs_lock(ncp, HFS_EXCLUSIVE_LOCK); + + /* Insert the new cnode with it's H_ALLOC flag set */ + LIST_INSERT_HEAD(CNODEHASH(hfsmp, inum), ncp, c_hash); + hfs_chash_unlock(hfsmp); + + *vpp = NULL; + return (ncp); +} + + +__private_extern__ +void +hfs_chashwakeup(struct hfsmount *hfsmp, struct cnode *cp, int hflags) +{ + hfs_chash_lock_spin(hfsmp); + + CLR(cp->c_hflag, hflags); + + if (ISSET(cp->c_hflag, H_WAITING)) { + CLR(cp->c_hflag, H_WAITING); + wakeup((caddr_t)cp); + } + hfs_chash_unlock(hfsmp); } /* - * Insert a cnode into the hash table. + * Re-hash two cnodes in the hash table. */ __private_extern__ void -hfs_chashinsert(struct cnode *cp) +hfs_chash_rehash(struct hfsmount *hfsmp, struct cnode *cp1, struct cnode *cp2) { - if (cp->c_fileid == 0) - panic("hfs_chashinsert: trying to insert file id 0"); - simple_lock(&hfs_chash_slock); - LIST_INSERT_HEAD(CNODEHASH(cp->c_dev, cp->c_fileid), cp, c_hash); - simple_unlock(&hfs_chash_slock); + hfs_chash_lock_spin(hfsmp); + + LIST_REMOVE(cp1, c_hash); + LIST_REMOVE(cp2, c_hash); + LIST_INSERT_HEAD(CNODEHASH(hfsmp, cp1->c_fileid), cp1, c_hash); + LIST_INSERT_HEAD(CNODEHASH(hfsmp, cp2->c_fileid), cp2, c_hash); + + hfs_chash_unlock(hfsmp); } @@ -217,13 +427,116 @@ hfs_chashinsert(struct cnode *cp) * Remove a cnode from the hash table. */ __private_extern__ +int +hfs_chashremove(struct hfsmount *hfsmp, struct cnode *cp) +{ + hfs_chash_lock_spin(hfsmp); + + /* Check if a vnode is getting attached */ + if (ISSET(cp->c_hflag, H_ATTACH)) { + hfs_chash_unlock(hfsmp); + return (EBUSY); + } + if (cp->c_hash.le_next || cp->c_hash.le_prev) { + LIST_REMOVE(cp, c_hash); + cp->c_hash.le_next = NULL; + cp->c_hash.le_prev = NULL; + } + hfs_chash_unlock(hfsmp); + + return (0); +} + +/* + * Remove a cnode from the hash table and wakeup any waiters. + */ +__private_extern__ void -hfs_chashremove(struct cnode *cp) +hfs_chash_abort(struct hfsmount *hfsmp, struct cnode *cp) { - simple_lock(&hfs_chash_slock); + hfs_chash_lock_spin(hfsmp); + LIST_REMOVE(cp, c_hash); cp->c_hash.le_next = NULL; cp->c_hash.le_prev = NULL; - simple_unlock(&hfs_chash_slock); + + CLR(cp->c_hflag, H_ATTACH | H_ALLOC); + if (ISSET(cp->c_hflag, H_WAITING)) { + CLR(cp->c_hflag, H_WAITING); + wakeup((caddr_t)cp); + } + hfs_chash_unlock(hfsmp); } + +/* + * mark a cnode as in transition + */ +__private_extern__ +void +hfs_chash_mark_in_transit(struct hfsmount *hfsmp, struct cnode *cp) +{ + hfs_chash_lock_spin(hfsmp); + + SET(cp->c_hflag, H_TRANSIT); + + hfs_chash_unlock(hfsmp); +} + +/* Search a cnode in the hash. This function does not return cnode which + * are getting created, destroyed or in transition. Note that this function + * does not acquire the cnode hash mutex, and expects the caller to acquire it. + * On success, returns pointer to the cnode found. On failure, returns NULL. + */ +static +struct cnode * +hfs_chash_search_cnid(struct hfsmount *hfsmp, cnid_t cnid) +{ + struct cnode *cp; + + for (cp = CNODEHASH(hfsmp, cnid)->lh_first; cp; cp = cp->c_hash.le_next) { + if (cp->c_fileid == cnid) { + break; + } + } + + /* If cnode is being created or reclaimed, return error. */ + if (cp && ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) { + cp = NULL; + } + + return cp; +} + +/* Search a cnode corresponding to given device and ID in the hash. If the + * found cnode has kHFSHasChildLinkBit cleared, set it. If the cnode is not + * found, no new cnode is created and error is returned. + * + * Return values - + * -1 : The cnode was not found. + * 0 : The cnode was found, and the kHFSHasChildLinkBit was already set. + * 1 : The cnode was found, the kHFSHasChildLinkBit was not set, and the + * function had to set that bit. + */ +__private_extern__ +int +hfs_chash_set_childlinkbit(struct hfsmount *hfsmp, cnid_t cnid) +{ + int retval = -1; + struct cnode *cp; + + hfs_chash_lock_spin(hfsmp); + + cp = hfs_chash_search_cnid(hfsmp, cnid); + if (cp) { + if (cp->c_attr.ca_recflags & kHFSHasChildLinkMask) { + retval = 0; + } else { + cp->c_attr.ca_recflags |= kHFSHasChildLinkMask; + retval = 1; + } + } + hfs_chash_unlock(hfsmp); + + return retval; +}