[apple/xnu.git] / bsd / hfs / hfs_chash.c

/*
 * Copyright (c) 2002-2005 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_OSREFERENCE_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.  The rights granted to you under the 
 * License may not be used to create, or enable the creation or 
 * redistribution of, unlawful or unlicensed copies of an Apple operating 
 * system, or to circumvent, violate, or enable the circumvention or 
 * violation of, any terms of an Apple operating system software license 
 * agreement.
 *
 * Please obtain a copy of the License at 
 * http://www.opensource.apple.com/apsl/ and read it before using this 
 * file.
 *
 * The Original Code and all software distributed under the License are 
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 
 * Please see the License for the specific language governing rights and 
 * limitations under the License.
 *
 * @APPLE_LICENSE_OSREFERENCE_HEADER_END@
 */

/*
 * Copyright (c) 1982, 1986, 1989, 1991, 1993, 1995
 *	The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *	  notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *	  notice, this list of conditions and the following disclaimer in the
 *	  documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *	  must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *	  may be used to endorse or promote products derived from this software
 *	  without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.	IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	@(#)hfs_chash.c
 *	derived from @(#)ufs_ihash.c	8.7 (Berkeley) 5/17/95
 */

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/vnode.h>
#include <sys/kernel.h>
#include <sys/malloc.h>
#include <sys/proc.h>
#include <sys/queue.h>


#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;

/*
 * 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])

lck_mtx_t  hfs_chash_mutex;


/*
 * Initialize cnode hash table.
 */
__private_extern__
void
hfs_chashinit()
{
	cnodehashtbl = hashinit(desiredvnodes, M_HFSMNT, &cnodehash);

	chash_lck_grp_attr= lck_grp_attr_alloc_init();
	lck_grp_attr_setstat(chash_lck_grp_attr);
	chash_lck_grp  = lck_grp_alloc_init("cnode_hash", chash_lck_grp_attr);

	chash_lck_attr = lck_attr_alloc_init();
	//lck_attr_setdebug(chash_lck_attr);

	lck_mtx_init(&hfs_chash_mutex, chash_lck_grp, chash_lck_attr);
}


/*
 * Use the device, inum pair to find the incore cnode.
 *
 * If it is in core, but locked, wait for it.
 */
__private_extern__
struct vnode *
hfs_chash_getvnode(dev_t dev, ino_t inum, int wantrsrc, int skiplock)
{
	struct cnode *cp;
	struct vnode *vp;
	int error;
	uint32_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:
	lck_mtx_lock(&hfs_chash_mutex);
	for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
		if ((cp->c_fileid != inum) || (cp->c_dev != dev))
			continue;
		/* 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, &hfs_chash_mutex, PDROP | PINOD,
			              "hfs_chash_getvnode", 0);
			goto loop;
		}
		/*
		 * Skip cnodes that are not in the name space anymore
		 * note that this check is done outside of the proper
		 * lock to catch nodes already in this state... this
		 * state must be rechecked after we acquire the cnode lock
		 */
		if (cp->c_flag & (C_NOEXISTS | C_DELETED)) {
			continue;
		}
		/* Obtain the desired vnode. */
		vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
		if (vp == NULLVP)
			goto exit;

		vid = vnode_vid(vp);
		lck_mtx_unlock(&hfs_chash_mutex);

		if ((error = vnode_getwithvid(vp, vid))) {
		        /*
			 * If vnode is being reclaimed, or has
			 * already changed identity, no need to wait
			 */
		        return (NULL);
		}
		if (!skiplock && hfs_lock(cp, HFS_EXCLUSIVE_LOCK) != 0) {
			vnode_put(vp);
			return (NULL);
		}

		/*
		 * Skip cnodes that are not in the name space anymore
		 * we need to check again 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:
	lck_mtx_unlock(&hfs_chash_mutex);
	return (NULL);
}


/*
 * 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.
 */
__private_extern__
int
hfs_chash_snoop(dev_t dev, 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.
	 */
	lck_mtx_lock(&hfs_chash_mutex);
	for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
		if ((cp->c_fileid != inum) || (cp->c_dev != dev))
			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;
	}
	lck_mtx_unlock(&hfs_chash_mutex);
	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.
 */
__private_extern__
struct cnode *
hfs_chash_getcnode(dev_t dev, ino_t inum, struct vnode **vpp, int wantrsrc, int skiplock)
{
	struct cnode	*cp;
	struct cnode	*ncp = NULL;
	vnode_t		vp;
	uint32_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:
	lck_mtx_lock(&hfs_chash_mutex);

loop_with_lock:
	for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
		if ((cp->c_fileid != inum) || (cp->c_dev != dev))
			continue;
		/*
		 * Wait if cnode is being created, attached to or reclaimed.
		 */
		if (ISSET(cp->c_hflag, H_ALLOC | H_ATTACH | H_TRANSIT)) {
		        SET(cp->c_hflag, H_WAITING);

			(void) msleep(cp, &hfs_chash_mutex, PINOD,
			              "hfs_chash_getcnode", 0);
			goto loop_with_lock;
		}
		/*
		 * Skip cnodes that are not in the name space anymore
		 * note that this check is done outside of the proper
		 * lock to catch nodes already in this state... this
		 * state must be rechecked after we acquire the cnode lock
		 */
		if (cp->c_flag & (C_NOEXISTS | C_DELETED)) {
			continue;
		}
		vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
		if (vp == NULL) {
			/*
			 * The desired vnode isn't there so tag the cnode.
			 */
			SET(cp->c_hflag, H_ATTACH);

			lck_mtx_unlock(&hfs_chash_mutex);
		} else {
			vid = vnode_vid(vp);

			lck_mtx_unlock(&hfs_chash_mutex);

			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_EXCLUSIVE_LOCK) != 0) {
			if (vp != NULLVP)
				vnode_put(vp);
			lck_mtx_lock(&hfs_chash_mutex);

			if (vp == NULLVP)
			        CLR(cp->c_hflag, H_ATTACH);
			goto loop_with_lock;
		}
		/*
		 * Skip cnodes that are not in the name space anymore
		 * we need to check again 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);
			if (vp != NULLVP)
				vnode_put(vp);
			lck_mtx_lock(&hfs_chash_mutex);

			if (vp == NULLVP)
			        CLR(cp->c_hflag, H_ATTACH);
			goto loop_with_lock;
		}
		*vpp = vp;
		return (cp);
	}

	/* 
	 * Allocate a new cnode
	 */
	if (skiplock)
		panic("%s - should never get here when skiplock is set \n", __FUNCTION__);

	if (ncp == NULL) {
		lck_mtx_unlock(&hfs_chash_mutex);

	        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;
	}
	bzero(ncp, sizeof(struct cnode));
	SET(ncp->c_hflag, H_ALLOC);
	ncp->c_fileid = inum;
	ncp->c_dev = dev;
	TAILQ_INIT(&ncp->c_hintlist); /* make the list empty */

	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(dev, inum), ncp, c_hash);
	lck_mtx_unlock(&hfs_chash_mutex);

	*vpp = NULL;
	return (ncp);
}


__private_extern__
void
hfs_chashwakeup(struct cnode *cp, int hflags)
{
	lck_mtx_lock(&hfs_chash_mutex);

	CLR(cp->c_hflag, hflags);

	if (ISSET(cp->c_hflag, H_WAITING)) {
	        CLR(cp->c_hflag, H_WAITING);
		wakeup((caddr_t)cp);
	}
	lck_mtx_unlock(&hfs_chash_mutex);
}


/*
 * Re-hash two cnodes in the hash table.
 */
__private_extern__
void
hfs_chash_rehash(struct cnode *cp1, struct cnode *cp2)
{
	lck_mtx_lock(&hfs_chash_mutex);

	LIST_REMOVE(cp1, c_hash);
	LIST_REMOVE(cp2, c_hash);
	LIST_INSERT_HEAD(CNODEHASH(cp1->c_dev, cp1->c_fileid), cp1, c_hash);
	LIST_INSERT_HEAD(CNODEHASH(cp2->c_dev, cp2->c_fileid), cp2, c_hash);

	lck_mtx_unlock(&hfs_chash_mutex);
}


/*
 * Remove a cnode from the hash table.
 */
__private_extern__
int
hfs_chashremove(struct cnode *cp)
{
	lck_mtx_lock(&hfs_chash_mutex);

	/* Check if a vnode is getting attached */
	if (ISSET(cp->c_hflag, H_ATTACH)) {
		lck_mtx_unlock(&hfs_chash_mutex);
		return (EBUSY);
	}
	LIST_REMOVE(cp, c_hash);
	cp->c_hash.le_next = NULL;
	cp->c_hash.le_prev = NULL;
	
	lck_mtx_unlock(&hfs_chash_mutex);
	return (0);
}

/*
 * Remove a cnode from the hash table and wakeup any waiters.
 */
__private_extern__
void
hfs_chash_abort(struct cnode *cp)
{
	lck_mtx_lock(&hfs_chash_mutex);

	LIST_REMOVE(cp, c_hash);
	cp->c_hash.le_next = NULL;
	cp->c_hash.le_prev = NULL;

	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);
	}
	lck_mtx_unlock(&hfs_chash_mutex);
}


/*
 * mark a cnode as in transistion
 */
__private_extern__
void
hfs_chash_mark_in_transit(struct cnode *cp)
{
	lck_mtx_lock(&hfs_chash_mutex);

        SET(cp->c_hflag, H_TRANSIT);

	lck_mtx_unlock(&hfs_chash_mutex);
}
Commit	Line	Data
9bccf70c	1	/*
91447636	2	* Copyright (c) 2002-2005 Apple Computer, Inc. All rights reserved.
9bccf70c	3	*
8ad349bb	4	* @APPLE_LICENSE_OSREFERENCE_HEADER_START@
9bccf70c	5	*
8ad349bb A	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. The rights granted to you under the
	10	* License may not be used to create, or enable the creation or
	11	* redistribution of, unlawful or unlicensed copies of an Apple operating
	12	* system, or to circumvent, violate, or enable the circumvention or
	13	* violation of, any terms of an Apple operating system software license
	14	* agreement.
	15	*
	16	* Please obtain a copy of the License at
	17	* http://www.opensource.apple.com/apsl/ and read it before using this
	18	* file.
	19	*
	20	* The Original Code and all software distributed under the License are
	21	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	22	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	23	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	24	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	25	* Please see the License for the specific language governing rights and
	26	* limitations under the License.
	27	*
	28	* @APPLE_LICENSE_OSREFERENCE_HEADER_END@
9bccf70c A	29	*/
	30
	31	/*
	32	* Copyright (c) 1982, 1986, 1989, 1991, 1993, 1995
	33	* The Regents of the University of California. All rights reserved.
	34	*
	35	* Redistribution and use in source and binary forms, with or without
	36	* modification, are permitted provided that the following conditions
	37	* are met:
	38	* 1. Redistributions of source code must retain the above copyright
	39	* notice, this list of conditions and the following disclaimer.
	40	* 2. Redistributions in binary form must reproduce the above copyright
	41	* notice, this list of conditions and the following disclaimer in the
	42	* documentation and/or other materials provided with the distribution.
	43	* 3. All advertising materials mentioning features or use of this software
	44	* must display the following acknowledgement:
	45	* This product includes software developed by the University of
	46	* California, Berkeley and its contributors.
	47	* 4. Neither the name of the University nor the names of its contributors
	48	* may be used to endorse or promote products derived from this software
	49	* without specific prior written permission.
	50	*
	51	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	52	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	53	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	54	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	55	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	56	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	57	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	58	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	59	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	60	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	61	* SUCH DAMAGE.
	62	*
	63	* @(#)hfs_chash.c
	64	* derived from @(#)ufs_ihash.c 8.7 (Berkeley) 5/17/95
	65	*/
	66
	67	#include <sys/param.h>
	68	#include <sys/systm.h>
	69	#include <sys/vnode.h>
91447636	70	#include <sys/kernel.h>
9bccf70c A	71	#include <sys/malloc.h>
	72	#include <sys/proc.h>
	73	#include <sys/queue.h>
	74
91447636 A	75
91447636 A	76	#include "hfs.h" /* XXX bringup */
9bccf70c A	77	#include "hfs_cnode.h"
9bccf70c A	78
91447636 A	79	extern lck_attr_t * hfs_lock_attr;
	80	extern lck_grp_t * hfs_mutex_group;
	81	extern lck_grp_t * hfs_rwlock_group;
	82
	83	lck_grp_t * chash_lck_grp;
	84	lck_grp_attr_t * chash_lck_grp_attr;
	85	lck_attr_t * chash_lck_attr;
9bccf70c A	86
	87	/*
	88	* Structures associated with cnode caching.
	89	*/
	90	LIST_HEAD(cnodehashhead, cnode) *cnodehashtbl;
	91	u_long cnodehash; /* size of hash table - 1 */
	92	#define CNODEHASH(device, inum) (&cnodehashtbl[((device) + (inum)) & cnodehash])
91447636 A	93
	94	lck_mtx_t hfs_chash_mutex;
	95
9bccf70c A	96
	97	/*
	98	* Initialize cnode hash table.
	99	*/
	100	__private_extern__
	101	void
	102	hfs_chashinit()
	103	{
	104	cnodehashtbl = hashinit(desiredvnodes, M_HFSMNT, &cnodehash);
91447636 A	105
91447636 A	106	chash_lck_grp_attr= lck_grp_attr_alloc_init();
8ad349bb	107	lck_grp_attr_setstat(chash_lck_grp_attr);
91447636	108	chash_lck_grp = lck_grp_alloc_init("cnode_hash", chash_lck_grp_attr);
8ad349bb	109
91447636	110	chash_lck_attr = lck_attr_alloc_init();
8ad349bb	111	//lck_attr_setdebug(chash_lck_attr);
91447636 A	112
91447636 A	113	lck_mtx_init(&hfs_chash_mutex, chash_lck_grp, chash_lck_attr);
9bccf70c A	114	}
	115
	116
	117	/*
	118	* Use the device, inum pair to find the incore cnode.
	119	*
	120	* If it is in core, but locked, wait for it.
9bccf70c A	121	*/
9bccf70c A	122	__private_extern__
91447636 A	123	struct vnode *
91447636 A	124	hfs_chash_getvnode(dev_t dev, ino_t inum, int wantrsrc, int skiplock)
9bccf70c	125	{
9bccf70c A	126	struct cnode *cp;
	127	struct vnode *vp;
	128	int error;
91447636	129	uint32_t vid;
9bccf70c	130
9bccf70c A	131	/*
	132	* Go through the hash list
	133	* If a cnode is in the process of being cleaned out or being
	134	* allocated, wait for it to be finished and then try again.
	135	*/
	136	loop:
91447636	137	lck_mtx_lock(&hfs_chash_mutex);
9bccf70c A	138	for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
	139	if ((cp->c_fileid != inum) \|\| (cp->c_dev != dev))
	140	continue;
91447636 A	141	/* Wait if cnode is being created or reclaimed. */
	142	if (ISSET(cp->c_hflag, H_ALLOC \| H_TRANSIT \| H_ATTACH)) {
	143	SET(cp->c_hflag, H_WAITING);
	144
	145	(void) msleep(cp, &hfs_chash_mutex, PDROP \| PINOD,
	146	"hfs_chash_getvnode", 0);
9bccf70c	147	goto loop;
91447636 A	148	}
	149	/*
	150	* Skip cnodes that are not in the name space anymore
	151	* note that this check is done outside of the proper
	152	* lock to catch nodes already in this state... this
	153	* state must be rechecked after we acquire the cnode lock
	154	*/
	155	if (cp->c_flag & (C_NOEXISTS \| C_DELETED)) {
	156	continue;
	157	}
	158	/* Obtain the desired vnode. */
	159	vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
	160	if (vp == NULLVP)
	161	goto exit;
	162
	163	vid = vnode_vid(vp);
	164	lck_mtx_unlock(&hfs_chash_mutex);
	165
	166	if ((error = vnode_getwithvid(vp, vid))) {
	167	/*
	168	* If vnode is being reclaimed, or has
	169	* already changed identity, no need to wait
9bccf70c	170	*/
91447636	171	return (NULL);
9bccf70c	172	}
91447636 A	173	if (!skiplock && hfs_lock(cp, HFS_EXCLUSIVE_LOCK) != 0) {
	174	vnode_put(vp);
	175	return (NULL);
	176	}
	177
	178	/*
	179	* Skip cnodes that are not in the name space anymore
	180	* we need to check again with the cnode lock held
	181	* because we may have blocked acquiring the vnode ref
	182	* or the lock on the cnode which would allow the node
	183	* to be unlinked
	184	*/
	185	if (cp->c_flag & (C_NOEXISTS \| C_DELETED)) {
	186	if (!skiplock)
	187	hfs_unlock(cp);
	188	vnode_put(vp);
	189
	190	return (NULL);
	191	}
	192	return (vp);
	193	}
	194	exit:
	195	lck_mtx_unlock(&hfs_chash_mutex);
	196	return (NULL);
	197	}
	198
	199
	200	/*
	201	* Use the device, fileid pair to find the incore cnode.
	202	* If no cnode if found one is created
	203	*
	204	* If it is in core, but locked, wait for it.
	205	*/
	206	__private_extern__
	207	int
	208	hfs_chash_snoop(dev_t dev, ino_t inum, int (callout)(const struct cat_desc ,
	209	const struct cat_attr , void ), void * arg)
	210	{
	211	struct cnode *cp;
	212	int result = ENOENT;
	213
	214	/*
	215	* Go through the hash list
	216	* If a cnode is in the process of being cleaned out or being
	217	* allocated, wait for it to be finished and then try again.
	218	*/
	219	lck_mtx_lock(&hfs_chash_mutex);
	220	for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
	221	if ((cp->c_fileid != inum) \|\| (cp->c_dev != dev))
9bccf70c	222	continue;
91447636 A	223	/* Skip cnodes being created or reclaimed. */
	224	if (!ISSET(cp->c_hflag, H_ALLOC \| H_TRANSIT \| H_ATTACH)) {
	225	result = callout(&cp->c_desc, &cp->c_attr, arg);
	226	}
	227	break;
	228	}
	229	lck_mtx_unlock(&hfs_chash_mutex);
	230	return (result);
	231	}
	232
9bccf70c	233
91447636 A	234	/*
	235	* Use the device, fileid pair to find the incore cnode.
	236	* If no cnode if found one is created
	237	*
	238	* If it is in core, but locked, wait for it.
	239	*/
	240	__private_extern__
	241	struct cnode *
	242	hfs_chash_getcnode(dev_t dev, ino_t inum, struct vnode **vpp, int wantrsrc, int skiplock)
	243	{
	244	struct cnode *cp;
	245	struct cnode *ncp = NULL;
	246	vnode_t vp;
	247	uint32_t vid;
	248
	249	/*
	250	* Go through the hash list
	251	* If a cnode is in the process of being cleaned out or being
	252	* allocated, wait for it to be finished and then try again.
	253	*/
	254	loop:
	255	lck_mtx_lock(&hfs_chash_mutex);
	256
	257	loop_with_lock:
	258	for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
	259	if ((cp->c_fileid != inum) \|\| (cp->c_dev != dev))
	260	continue;
9bccf70c	261	/*
91447636	262	* Wait if cnode is being created, attached to or reclaimed.
9bccf70c	263	*/
91447636 A	264	if (ISSET(cp->c_hflag, H_ALLOC \| H_ATTACH \| H_TRANSIT)) {
91447636 A	265	SET(cp->c_hflag, H_WAITING);
9bccf70c	266
91447636 A	267	(void) msleep(cp, &hfs_chash_mutex, PINOD,
	268	"hfs_chash_getcnode", 0);
	269	goto loop_with_lock;
	270	}
	271	/*
	272	* Skip cnodes that are not in the name space anymore
	273	* note that this check is done outside of the proper
	274	* lock to catch nodes already in this state... this
	275	* state must be rechecked after we acquire the cnode lock
	276	*/
	277	if (cp->c_flag & (C_NOEXISTS \| C_DELETED)) {
	278	continue;
	279	}
	280	vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
	281	if (vp == NULL) {
9bccf70c	282	/*
91447636	283	* The desired vnode isn't there so tag the cnode.
9bccf70c	284	*/
91447636 A	285	SET(cp->c_hflag, H_ATTACH);
	286
	287	lck_mtx_unlock(&hfs_chash_mutex);
	288	} else {
	289	vid = vnode_vid(vp);
	290
	291	lck_mtx_unlock(&hfs_chash_mutex);
	292
	293	if (vnode_getwithvid(vp, vid))
	294	goto loop;
	295	}
	296	if (ncp) {
	297	/*
	298	* someone else won the race to create
	299	* this cnode and add it to the hash
	300	* just dump our allocation
	301	*/
	302	FREE_ZONE(ncp, sizeof(struct cnode), M_HFSNODE);
	303	ncp = NULL;
9bccf70c	304	}
91447636 A	305	if (!skiplock && hfs_lock(cp, HFS_EXCLUSIVE_LOCK) != 0) {
	306	if (vp != NULLVP)
	307	vnode_put(vp);
	308	lck_mtx_lock(&hfs_chash_mutex);
9bccf70c	309
91447636 A	310	if (vp == NULLVP)
	311	CLR(cp->c_hflag, H_ATTACH);
	312	goto loop_with_lock;
	313	}
9bccf70c	314	/*
91447636 A	315	* Skip cnodes that are not in the name space anymore
	316	* we need to check again with the cnode lock held
	317	* because we may have blocked acquiring the vnode ref
	318	* or the lock on the cnode which would allow the node
	319	* to be unlinked
9bccf70c	320	*/
91447636 A	321	if (cp->c_flag & (C_NOEXISTS \| C_DELETED)) {
	322	if (!skiplock)
	323	hfs_unlock(cp);
	324	if (vp != NULLVP)
	325	vnode_put(vp);
	326	lck_mtx_lock(&hfs_chash_mutex);
	327
	328	if (vp == NULLVP)
	329	CLR(cp->c_hflag, H_ATTACH);
	330	goto loop_with_lock;
9bccf70c	331	}
91447636	332	*vpp = vp;
9bccf70c A	333	return (cp);
9bccf70c A	334	}
91447636 A	335
	336	/*
	337	* Allocate a new cnode
	338	*/
	339	if (skiplock)
	340	panic("%s - should never get here when skiplock is set \n", __FUNCTION__);
	341
	342	if (ncp == NULL) {
	343	lck_mtx_unlock(&hfs_chash_mutex);
	344
	345	MALLOC_ZONE(ncp, struct cnode *, sizeof(struct cnode), M_HFSNODE, M_WAITOK);
	346	/*
	347	* since we dropped the chash lock,
	348	* we need to go back and re-verify
	349	* that this node hasn't come into
	350	* existence...
	351	*/
	352	goto loop;
	353	}
	354	bzero(ncp, sizeof(struct cnode));
	355	SET(ncp->c_hflag, H_ALLOC);
	356	ncp->c_fileid = inum;
	357	ncp->c_dev = dev;
b36670ce	358	TAILQ_INIT(&ncp->c_hintlist); /* make the list empty */
91447636 A	359
	360	lck_rw_init(&ncp->c_rwlock, hfs_rwlock_group, hfs_lock_attr);
	361	if (!skiplock)
	362	(void) hfs_lock(ncp, HFS_EXCLUSIVE_LOCK);
	363
	364	/* Insert the new cnode with it's H_ALLOC flag set */
	365	LIST_INSERT_HEAD(CNODEHASH(dev, inum), ncp, c_hash);
	366	lck_mtx_unlock(&hfs_chash_mutex);
	367
	368	*vpp = NULL;
	369	return (ncp);
	370	}
	371
	372
	373	__private_extern__
	374	void
	375	hfs_chashwakeup(struct cnode *cp, int hflags)
	376	{
	377	lck_mtx_lock(&hfs_chash_mutex);
	378
	379	CLR(cp->c_hflag, hflags);
	380
	381	if (ISSET(cp->c_hflag, H_WAITING)) {
	382	CLR(cp->c_hflag, H_WAITING);
	383	wakeup((caddr_t)cp);
	384	}
	385	lck_mtx_unlock(&hfs_chash_mutex);
9bccf70c A	386	}
	387
	388
	389	/*
91447636	390	* Re-hash two cnodes in the hash table.
9bccf70c A	391	*/
	392	__private_extern__
	393	void
91447636	394	hfs_chash_rehash(struct cnode cp1, struct cnode cp2)
9bccf70c	395	{
91447636 A	396	lck_mtx_lock(&hfs_chash_mutex);
	397
	398	LIST_REMOVE(cp1, c_hash);
	399	LIST_REMOVE(cp2, c_hash);
	400	LIST_INSERT_HEAD(CNODEHASH(cp1->c_dev, cp1->c_fileid), cp1, c_hash);
	401	LIST_INSERT_HEAD(CNODEHASH(cp2->c_dev, cp2->c_fileid), cp2, c_hash);
	402
	403	lck_mtx_unlock(&hfs_chash_mutex);
9bccf70c A	404	}
	405
	406
	407	/*
	408	* Remove a cnode from the hash table.
	409	*/
	410	__private_extern__
91447636	411	int
9bccf70c A	412	hfs_chashremove(struct cnode *cp)
9bccf70c A	413	{
91447636 A	414	lck_mtx_lock(&hfs_chash_mutex);
	415
	416	/* Check if a vnode is getting attached */
	417	if (ISSET(cp->c_hflag, H_ATTACH)) {
	418	lck_mtx_unlock(&hfs_chash_mutex);
	419	return (EBUSY);
	420	}
	421	LIST_REMOVE(cp, c_hash);
	422	cp->c_hash.le_next = NULL;
	423	cp->c_hash.le_prev = NULL;
	424
	425	lck_mtx_unlock(&hfs_chash_mutex);
	426	return (0);
	427	}
	428
	429	/*
	430	* Remove a cnode from the hash table and wakeup any waiters.
	431	*/
	432	__private_extern__
	433	void
	434	hfs_chash_abort(struct cnode *cp)
	435	{
	436	lck_mtx_lock(&hfs_chash_mutex);
	437
9bccf70c A	438	LIST_REMOVE(cp, c_hash);
	439	cp->c_hash.le_next = NULL;
	440	cp->c_hash.le_prev = NULL;
91447636 A	441
	442	CLR(cp->c_hflag, H_ATTACH \| H_ALLOC);
	443	if (ISSET(cp->c_hflag, H_WAITING)) {
	444	CLR(cp->c_hflag, H_WAITING);
	445	wakeup((caddr_t)cp);
	446	}
	447	lck_mtx_unlock(&hfs_chash_mutex);
9bccf70c A	448	}
9bccf70c A	449
91447636 A	450
	451	/*
	452	* mark a cnode as in transistion
	453	*/
	454	__private_extern__
	455	void
	456	hfs_chash_mark_in_transit(struct cnode *cp)
	457	{
	458	lck_mtx_lock(&hfs_chash_mutex);
	459
	460	SET(cp->c_hflag, H_TRANSIT);
	461
	462	lck_mtx_unlock(&hfs_chash_mutex);
	463	}