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

/*
 * Copyright (c) 2002-2006 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. 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_OSREFERENCE_LICENSE_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()
{
	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();

	lck_mtx_init(&hfs_chash_mutex, chash_lck_grp, chash_lck_attr);
}

static void hfs_chash_lock(void) 
{
	lck_mtx_lock(&hfs_chash_mutex);
}

static void hfs_chash_unlock(void) 
{
	lck_mtx_unlock(&hfs_chash_mutex);
}

__private_extern__
void
hfs_chashinit_finish()
{
	hfs_chash_lock();
	if (!cnodehashtbl)
		cnodehashtbl = hashinit(desiredvnodes, M_HFSMNT, &cnodehash);
	hfs_chash_unlock();
}


/*
 * 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;
	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();
	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;
		}
		/* 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();

		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 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();
	return (NULL);
}


/*
 * Use the device, fileid pair to snoop an incore cnode.
 */
__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.
	 */
	hfs_chash_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;
		/* 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();
	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(dev_t dev, 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();

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;
		}
		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);

			hfs_chash_unlock();
		} else {
			vid = vnode_vid(vp);

			hfs_chash_unlock();

			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);
		}

		/*
		 * 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 ((cp->c_flag & (C_NOEXISTS | C_DELETED)) && !wantrsrc) {
			if (!skiplock)
				hfs_unlock(cp);
			if (vp != NULLVP) {
				vnode_put(vp);
			} else {
				hfs_chash_lock();
		        	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();
			}
			vp = NULL;
			cp = NULL;
		}
		*vpp = vp;
		return (cp);
	}

	/* 
	 * 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();

	        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 */
	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(dev, inum), ncp, c_hash);
	hfs_chash_unlock();

	*vpp = NULL;
	return (ncp);
}


__private_extern__
void
hfs_chashwakeup(struct cnode *cp, int hflags)
{
	hfs_chash_lock();

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


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

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

	hfs_chash_unlock();
}


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

	/* Check if a vnode is getting attached */
	if (ISSET(cp->c_hflag, H_ATTACH)) {
		hfs_chash_unlock();
		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();
	return (0);
}

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

	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);
	}
	hfs_chash_unlock();
}


/*
 * mark a cnode as in transition
 */
__private_extern__
void
hfs_chash_mark_in_transit(struct cnode *cp)
{
	hfs_chash_lock();

        SET(cp->c_hflag, H_TRANSIT);

	hfs_chash_unlock();
}

/* 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(dev_t dev, cnid_t cnid) 
{
	struct cnode *cp;

	for (cp = CNODEHASH(dev, cnid)->lh_first; cp; cp = cp->c_hash.le_next) {
		if ((cp->c_fileid == cnid) && (cp->c_dev == dev)) {
			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(dev_t dev, cnid_t cnid)
{
	int retval = -1;
	struct cnode *cp;

	hfs_chash_lock();
	cp = hfs_chash_search_cnid(dev, cnid);
	if (cp) {
		if (cp->c_attr.ca_recflags & kHFSHasChildLinkMask) {
			retval = 0;
		} else {
			cp->c_attr.ca_recflags |= kHFSHasChildLinkMask;
			retval = 1;
		}
	}
	hfs_chash_unlock();

	return retval;
}
Commit	Line	Data
9bccf70c	1	/*
2d21ac55	2	* Copyright (c) 2002-2006 Apple Computer, Inc. All rights reserved.
9bccf70c	3	*
2d21ac55	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
9bccf70c	5	*
2d21ac55 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 License
	10	* may not be used to create, or enable the creation or redistribution of,
	11	* unlawful or unlicensed copies of an Apple operating system, or to
	12	* circumvent, violate, or enable the circumvention or violation of, any
	13	* terms of an Apple operating system software license agreement.
8f6c56a5	14	*
2d21ac55 A	15	* Please obtain a copy of the License at
	16	* http://www.opensource.apple.com/apsl/ and read it before using this file.
	17	*
	18	* The Original Code and all software distributed under the License are
	19	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
8f6c56a5 A	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
8f6c56a5 A	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
2d21ac55 A	22	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	23	* Please see the License for the specific language governing rights and
	24	* limitations under the License.
8f6c56a5	25	*
2d21ac55	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
9bccf70c A	27	*/
	28
	29	/*
	30	* Copyright (c) 1982, 1986, 1989, 1991, 1993, 1995
	31	* The Regents of the University of California. All rights reserved.
	32	*
	33	* Redistribution and use in source and binary forms, with or without
	34	* modification, are permitted provided that the following conditions
	35	* are met:
	36	* 1. Redistributions of source code must retain the above copyright
	37	* notice, this list of conditions and the following disclaimer.
	38	* 2. Redistributions in binary form must reproduce the above copyright
	39	* notice, this list of conditions and the following disclaimer in the
	40	* documentation and/or other materials provided with the distribution.
	41	* 3. All advertising materials mentioning features or use of this software
	42	* must display the following acknowledgement:
	43	* This product includes software developed by the University of
	44	* California, Berkeley and its contributors.
	45	* 4. Neither the name of the University nor the names of its contributors
	46	* may be used to endorse or promote products derived from this software
	47	* without specific prior written permission.
	48	*
	49	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	50	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	51	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	52	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	53	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	54	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	55	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	56	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	57	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	58	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	59	* SUCH DAMAGE.
	60	*
	61	* @(#)hfs_chash.c
	62	* derived from @(#)ufs_ihash.c 8.7 (Berkeley) 5/17/95
	63	*/
	64
	65	#include <sys/param.h>
	66	#include <sys/systm.h>
	67	#include <sys/vnode.h>
91447636	68	#include <sys/kernel.h>
9bccf70c A	69	#include <sys/malloc.h>
	70	#include <sys/proc.h>
	71	#include <sys/queue.h>
	72
91447636 A	73
91447636 A	74	#include "hfs.h" /* XXX bringup */
9bccf70c A	75	#include "hfs_cnode.h"
9bccf70c A	76
91447636 A	77	extern lck_attr_t * hfs_lock_attr;
	78	extern lck_grp_t * hfs_mutex_group;
	79	extern lck_grp_t * hfs_rwlock_group;
	80
	81	lck_grp_t * chash_lck_grp;
	82	lck_grp_attr_t * chash_lck_grp_attr;
	83	lck_attr_t * chash_lck_attr;
9bccf70c A	84
	85	/*
	86	* Structures associated with cnode caching.
	87	*/
	88	LIST_HEAD(cnodehashhead, cnode) *cnodehashtbl;
	89	u_long cnodehash; /* size of hash table - 1 */
	90	#define CNODEHASH(device, inum) (&cnodehashtbl[((device) + (inum)) & cnodehash])
91447636 A	91
	92	lck_mtx_t hfs_chash_mutex;
	93
9bccf70c A	94	/*
	95	* Initialize cnode hash table.
	96	*/
	97	__private_extern__
	98	void
	99	hfs_chashinit()
	100	{
91447636	101	chash_lck_grp_attr= lck_grp_attr_alloc_init();
91447636	102	chash_lck_grp = lck_grp_alloc_init("cnode_hash", chash_lck_grp_attr);
91447636	103	chash_lck_attr = lck_attr_alloc_init();
91447636 A	104
91447636 A	105	lck_mtx_init(&hfs_chash_mutex, chash_lck_grp, chash_lck_attr);
9bccf70c A	106	}
9bccf70c A	107
2d21ac55 A	108	static void hfs_chash_lock(void)
	109	{
	110	lck_mtx_lock(&hfs_chash_mutex);
	111	}
	112
	113	static void hfs_chash_unlock(void)
	114	{
	115	lck_mtx_unlock(&hfs_chash_mutex);
	116	}
	117
	118	__private_extern__
	119	void
	120	hfs_chashinit_finish()
	121	{
	122	hfs_chash_lock();
	123	if (!cnodehashtbl)
	124	cnodehashtbl = hashinit(desiredvnodes, M_HFSMNT, &cnodehash);
	125	hfs_chash_unlock();
	126	}
	127
9bccf70c A	128
	129	/*
	130	* Use the device, inum pair to find the incore cnode.
	131	*
	132	* If it is in core, but locked, wait for it.
9bccf70c A	133	*/
9bccf70c A	134	__private_extern__
91447636 A	135	struct vnode *
91447636 A	136	hfs_chash_getvnode(dev_t dev, ino_t inum, int wantrsrc, int skiplock)
9bccf70c	137	{
9bccf70c A	138	struct cnode *cp;
	139	struct vnode *vp;
	140	int error;
2d21ac55	141	u_int32_t vid;
9bccf70c	142
9bccf70c A	143	/*
	144	* Go through the hash list
	145	* If a cnode is in the process of being cleaned out or being
	146	* allocated, wait for it to be finished and then try again.
	147	*/
	148	loop:
2d21ac55	149	hfs_chash_lock();
9bccf70c A	150	for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
	151	if ((cp->c_fileid != inum) \|\| (cp->c_dev != dev))
	152	continue;
91447636 A	153	/* Wait if cnode is being created or reclaimed. */
	154	if (ISSET(cp->c_hflag, H_ALLOC \| H_TRANSIT \| H_ATTACH)) {
	155	SET(cp->c_hflag, H_WAITING);
	156
	157	(void) msleep(cp, &hfs_chash_mutex, PDROP \| PINOD,
	158	"hfs_chash_getvnode", 0);
9bccf70c	159	goto loop;
91447636	160	}
91447636 A	161	/* Obtain the desired vnode. */
	162	vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
	163	if (vp == NULLVP)
	164	goto exit;
	165
	166	vid = vnode_vid(vp);
2d21ac55	167	hfs_chash_unlock();
91447636 A	168
	169	if ((error = vnode_getwithvid(vp, vid))) {
	170	/*
	171	* If vnode is being reclaimed, or has
	172	* already changed identity, no need to wait
9bccf70c	173	*/
91447636	174	return (NULL);
9bccf70c	175	}
91447636 A	176	if (!skiplock && hfs_lock(cp, HFS_EXCLUSIVE_LOCK) != 0) {
	177	vnode_put(vp);
	178	return (NULL);
	179	}
	180
	181	/*
	182	* Skip cnodes that are not in the name space anymore
2d21ac55 A	183	* we need to check with the cnode lock held because
	184	* we may have blocked acquiring the vnode ref or the
	185	* lock on the cnode which would allow the node to be
	186	* unlinked
91447636 A	187	*/
	188	if (cp->c_flag & (C_NOEXISTS \| C_DELETED)) {
	189	if (!skiplock)
	190	hfs_unlock(cp);
	191	vnode_put(vp);
	192
	193	return (NULL);
	194	}
	195	return (vp);
	196	}
	197	exit:
2d21ac55	198	hfs_chash_unlock();
91447636 A	199	return (NULL);
	200	}
	201
	202
	203	/*
2d21ac55	204	* Use the device, fileid pair to snoop an incore cnode.
91447636 A	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	*/
2d21ac55	219	hfs_chash_lock();
91447636 A	220	for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
91447636 A	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	}
2d21ac55	229	hfs_chash_unlock();
91447636 A	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.
2d21ac55 A	239	*
	240	* If the cnode is C_DELETED, then return NULL since that
	241	* inum is no longer valid for lookups (open-unlinked file).
91447636 A	242	*/
	243	__private_extern__
	244	struct cnode *
	245	hfs_chash_getcnode(dev_t dev, ino_t inum, struct vnode **vpp, int wantrsrc, int skiplock)
	246	{
	247	struct cnode *cp;
	248	struct cnode *ncp = NULL;
	249	vnode_t vp;
2d21ac55	250	u_int32_t vid;
91447636 A	251
	252	/*
	253	* Go through the hash list
	254	* If a cnode is in the process of being cleaned out or being
	255	* allocated, wait for it to be finished and then try again.
	256	*/
	257	loop:
2d21ac55	258	hfs_chash_lock();
91447636 A	259
	260	loop_with_lock:
	261	for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
	262	if ((cp->c_fileid != inum) \|\| (cp->c_dev != dev))
	263	continue;
9bccf70c	264	/*
91447636	265	* Wait if cnode is being created, attached to or reclaimed.
9bccf70c	266	*/
91447636 A	267	if (ISSET(cp->c_hflag, H_ALLOC \| H_ATTACH \| H_TRANSIT)) {
91447636 A	268	SET(cp->c_hflag, H_WAITING);
9bccf70c	269
91447636 A	270	(void) msleep(cp, &hfs_chash_mutex, PINOD,
	271	"hfs_chash_getcnode", 0);
	272	goto loop_with_lock;
	273	}
91447636 A	274	vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
91447636 A	275	if (vp == NULL) {
9bccf70c	276	/*
91447636	277	* The desired vnode isn't there so tag the cnode.
9bccf70c	278	*/
91447636 A	279	SET(cp->c_hflag, H_ATTACH);
91447636 A	280
2d21ac55	281	hfs_chash_unlock();
91447636 A	282	} else {
	283	vid = vnode_vid(vp);
	284
2d21ac55	285	hfs_chash_unlock();
91447636 A	286
	287	if (vnode_getwithvid(vp, vid))
	288	goto loop;
	289	}
	290	if (ncp) {
	291	/*
	292	* someone else won the race to create
	293	* this cnode and add it to the hash
	294	* just dump our allocation
	295	*/
	296	FREE_ZONE(ncp, sizeof(struct cnode), M_HFSNODE);
	297	ncp = NULL;
9bccf70c A	298	}
9bccf70c A	299
2d21ac55 A	300	if (!skiplock) {
2d21ac55 A	301	hfs_lock(cp, HFS_FORCE_LOCK);
91447636	302	}
2d21ac55	303
9bccf70c	304	/*
91447636	305	* Skip cnodes that are not in the name space anymore
2d21ac55 A	306	* we need to check with the cnode lock held because
	307	* we may have blocked acquiring the vnode ref or the
	308	* lock on the cnode which would allow the node to be
	309	* unlinked.
	310	*
	311	* Don't return a cnode in this case since the inum
	312	* is no longer valid for lookups.
9bccf70c	313	*/
2d21ac55	314	if ((cp->c_flag & (C_NOEXISTS \| C_DELETED)) && !wantrsrc) {
91447636 A	315	if (!skiplock)
91447636 A	316	hfs_unlock(cp);
2d21ac55	317	if (vp != NULLVP) {
91447636	318	vnode_put(vp);
2d21ac55 A	319	} else {
	320	hfs_chash_lock();
	321	CLR(cp->c_hflag, H_ATTACH);
	322	if (ISSET(cp->c_hflag, H_WAITING)) {
	323	CLR(cp->c_hflag, H_WAITING);
	324	wakeup((caddr_t)cp);
	325	}
	326	hfs_chash_unlock();
	327	}
	328	vp = NULL;
	329	cp = NULL;
9bccf70c	330	}
91447636	331	*vpp = vp;
9bccf70c A	332	return (cp);
9bccf70c A	333	}
91447636 A	334
	335	/*
	336	* Allocate a new cnode
	337	*/
2d21ac55	338	if (skiplock && !wantrsrc)
91447636 A	339	panic("%s - should never get here when skiplock is set \n", __FUNCTION__);
	340
	341	if (ncp == NULL) {
2d21ac55	342	hfs_chash_unlock();
91447636 A	343
	344	MALLOC_ZONE(ncp, struct cnode *, sizeof(struct cnode), M_HFSNODE, M_WAITOK);
	345	/*
	346	* since we dropped the chash lock,
	347	* we need to go back and re-verify
	348	* that this node hasn't come into
	349	* existence...
	350	*/
	351	goto loop;
	352	}
	353	bzero(ncp, sizeof(struct cnode));
	354	SET(ncp->c_hflag, H_ALLOC);
	355	ncp->c_fileid = inum;
	356	ncp->c_dev = dev;
b36670ce	357	TAILQ_INIT(&ncp->c_hintlist); /* make the list empty */
2d21ac55	358	TAILQ_INIT(&ncp->c_originlist);
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);
2d21ac55	366	hfs_chash_unlock();
91447636 A	367
	368	*vpp = NULL;
	369	return (ncp);
	370	}
	371
	372
	373	__private_extern__
	374	void
	375	hfs_chashwakeup(struct cnode *cp, int hflags)
	376	{
2d21ac55	377	hfs_chash_lock();
91447636 A	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	}
2d21ac55	385	hfs_chash_unlock();
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	{
2d21ac55	396	hfs_chash_lock();
91447636 A	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
2d21ac55	403	hfs_chash_unlock();
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	{
2d21ac55	414	hfs_chash_lock();
91447636 A	415
	416	/* Check if a vnode is getting attached */
	417	if (ISSET(cp->c_hflag, H_ATTACH)) {
2d21ac55	418	hfs_chash_unlock();
91447636 A	419	return (EBUSY);
91447636 A	420	}
2d21ac55 A	421	if (cp->c_hash.le_next \|\| cp->c_hash.le_prev) {
	422	LIST_REMOVE(cp, c_hash);
	423	cp->c_hash.le_next = NULL;
	424	cp->c_hash.le_prev = NULL;
	425	}
	426	hfs_chash_unlock();
91447636 A	427	return (0);
	428	}
	429
	430	/*
	431	* Remove a cnode from the hash table and wakeup any waiters.
	432	*/
	433	__private_extern__
	434	void
	435	hfs_chash_abort(struct cnode *cp)
	436	{
2d21ac55	437	hfs_chash_lock();
91447636	438
9bccf70c A	439	LIST_REMOVE(cp, c_hash);
	440	cp->c_hash.le_next = NULL;
	441	cp->c_hash.le_prev = NULL;
91447636 A	442
	443	CLR(cp->c_hflag, H_ATTACH \| H_ALLOC);
	444	if (ISSET(cp->c_hflag, H_WAITING)) {
	445	CLR(cp->c_hflag, H_WAITING);
	446	wakeup((caddr_t)cp);
	447	}
2d21ac55	448	hfs_chash_unlock();
9bccf70c A	449	}
9bccf70c A	450
91447636 A	451
91447636 A	452	/*
2d21ac55	453	* mark a cnode as in transition
91447636 A	454	*/
	455	__private_extern__
	456	void
	457	hfs_chash_mark_in_transit(struct cnode *cp)
	458	{
2d21ac55	459	hfs_chash_lock();
91447636 A	460
	461	SET(cp->c_hflag, H_TRANSIT);
	462
2d21ac55 A	463	hfs_chash_unlock();
	464	}
	465
	466	/* Search a cnode in the hash. This function does not return cnode which
	467	* are getting created, destroyed or in transition. Note that this function
	468	* does not acquire the cnode hash mutex, and expects the caller to acquire it.
	469	* On success, returns pointer to the cnode found. On failure, returns NULL.
	470	*/
	471	static
	472	struct cnode *
	473	hfs_chash_search_cnid(dev_t dev, cnid_t cnid)
	474	{
	475	struct cnode *cp;
	476
	477	for (cp = CNODEHASH(dev, cnid)->lh_first; cp; cp = cp->c_hash.le_next) {
	478	if ((cp->c_fileid == cnid) && (cp->c_dev == dev)) {
	479	break;
	480	}
	481	}
	482
	483	/* If cnode is being created or reclaimed, return error. */
	484	if (cp && ISSET(cp->c_hflag, H_ALLOC \| H_TRANSIT \| H_ATTACH)) {
	485	cp = NULL;
	486	}
	487
	488	return cp;
	489	}
	490
	491	/* Search a cnode corresponding to given device and ID in the hash. If the
	492	* found cnode has kHFSHasChildLinkBit cleared, set it. If the cnode is not
	493	* found, no new cnode is created and error is returned.
	494	*
	495	* Return values -
	496	* -1 : The cnode was not found.
	497	* 0 : The cnode was found, and the kHFSHasChildLinkBit was already set.
	498	* 1 : The cnode was found, the kHFSHasChildLinkBit was not set, and the
	499	* function had to set that bit.
	500	*/
	501	__private_extern__
	502	int
	503	hfs_chash_set_childlinkbit(dev_t dev, cnid_t cnid)
	504	{
	505	int retval = -1;
	506	struct cnode *cp;
	507
	508	hfs_chash_lock();
	509	cp = hfs_chash_search_cnid(dev, cnid);
	510	if (cp) {
	511	if (cp->c_attr.ca_recflags & kHFSHasChildLinkMask) {
	512	retval = 0;
	513	} else {
	514	cp->c_attr.ca_recflags \|= kHFSHasChildLinkMask;
	515	retval = 1;
	516	}
	517	}
	518	hfs_chash_unlock();
	519
	520	return retval;
91447636	521	}