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

/*
 * Copyright (c) 2002-2008 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;


#define CNODEHASH(hfsmp, inum) (&hfsmp->hfs_cnodehashtbl[(inum) & hfsmp->hfs_cnodehash])


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

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


/*
 * 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(struct hfsmount *hfsmp, 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_spin(hfsmp);

	for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
		if (cp->c_fileid != inum)
			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, &hfsmp->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(hfsmp);

		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(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;
		/*
		 * 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, &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) {
			/*
			 * The desired vnode isn't there so tag the cnode.
			 */
			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);
		}

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

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


/*
 * Re-hash two cnodes in the hash table.
 */
__private_extern__
void
hfs_chash_rehash(struct hfsmount *hfsmp, struct cnode *cp1, struct cnode *cp2)
{
	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);
}


/*
 * 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_chash_abort(struct hfsmount *hfsmp, struct cnode *cp)
{
	hfs_chash_lock_spin(hfsmp);

	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(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;
}
Commit	Line	Data
9bccf70c	1	/*
b0d623f7	2	* Copyright (c) 2002-2008 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	84
91447636	85
b0d623f7 A	86	#define CNODEHASH(hfsmp, inum) (&hfsmp->hfs_cnodehashtbl[(inum) & hfsmp->hfs_cnodehash])
b0d623f7 A	87
91447636	88
9bccf70c A	89	/*
	90	* Initialize cnode hash table.
	91	*/
	92	__private_extern__
	93	void
	94	hfs_chashinit()
	95	{
91447636	96	chash_lck_grp_attr= lck_grp_attr_alloc_init();
91447636	97	chash_lck_grp = lck_grp_alloc_init("cnode_hash", chash_lck_grp_attr);
91447636	98	chash_lck_attr = lck_attr_alloc_init();
b0d623f7	99	}
91447636	100
b0d623f7 A	101	static void hfs_chash_lock(struct hfsmount *hfsmp)
	102	{
	103	lck_mtx_lock(&hfsmp->hfs_chash_mutex);
9bccf70c A	104	}
9bccf70c A	105
b0d623f7	106	static void hfs_chash_lock_spin(struct hfsmount *hfsmp)
2d21ac55	107	{
b0d623f7	108	lck_mtx_lock_spin(&hfsmp->hfs_chash_mutex);
2d21ac55 A	109	}
2d21ac55 A	110
b0d623f7 A	111	#ifdef i386
	112	static void hfs_chash_lock_convert (struct hfsmount *hfsmp)
	113	#else
	114	static void hfs_chash_lock_convert (__unused struct hfsmount *hfsmp)
	115	#endif
2d21ac55	116	{
b0d623f7 A	117	lck_mtx_convert_spin(&hfsmp->hfs_chash_mutex);
	118	}
	119
	120	static void hfs_chash_unlock(struct hfsmount *hfsmp)
	121	{
	122	lck_mtx_unlock(&hfsmp->hfs_chash_mutex);
2d21ac55 A	123	}
	124
	125	__private_extern__
	126	void
b0d623f7	127	hfs_chashinit_finish(struct hfsmount *hfsmp)
2d21ac55	128	{
b0d623f7 A	129	lck_mtx_init(&hfsmp->hfs_chash_mutex, chash_lck_grp, chash_lck_attr);
	130
	131	hfsmp->hfs_cnodehashtbl = hashinit(desiredvnodes / 4, M_HFSMNT, &hfsmp->hfs_cnodehash);
	132	}
	133
	134	__private_extern__
	135	void
	136	hfs_delete_chash(struct hfsmount *hfsmp)
	137	{
	138	lck_mtx_destroy(&hfsmp->hfs_chash_mutex, chash_lck_grp);
	139
	140	FREE(hfsmp->hfs_cnodehashtbl, M_HFSMNT);
2d21ac55 A	141	}
2d21ac55 A	142
9bccf70c A	143
	144	/*
	145	* Use the device, inum pair to find the incore cnode.
	146	*
	147	* If it is in core, but locked, wait for it.
9bccf70c A	148	*/
9bccf70c A	149	__private_extern__
91447636	150	struct vnode *
b0d623f7	151	hfs_chash_getvnode(struct hfsmount *hfsmp, ino_t inum, int wantrsrc, int skiplock)
9bccf70c	152	{
9bccf70c A	153	struct cnode *cp;
	154	struct vnode *vp;
	155	int error;
2d21ac55	156	u_int32_t vid;
9bccf70c	157
9bccf70c A	158	/*
	159	* Go through the hash list
	160	* If a cnode is in the process of being cleaned out or being
	161	* allocated, wait for it to be finished and then try again.
	162	*/
	163	loop:
b0d623f7 A	164	hfs_chash_lock_spin(hfsmp);
	165
	166	for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
	167	if (cp->c_fileid != inum)
9bccf70c	168	continue;
91447636 A	169	/* Wait if cnode is being created or reclaimed. */
	170	if (ISSET(cp->c_hflag, H_ALLOC \| H_TRANSIT \| H_ATTACH)) {
	171	SET(cp->c_hflag, H_WAITING);
	172
b0d623f7	173	(void) msleep(cp, &hfsmp->hfs_chash_mutex, PDROP \| PINOD,
91447636	174	"hfs_chash_getvnode", 0);
9bccf70c	175	goto loop;
91447636	176	}
91447636 A	177	/* Obtain the desired vnode. */
	178	vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
	179	if (vp == NULLVP)
	180	goto exit;
	181
	182	vid = vnode_vid(vp);
b0d623f7	183	hfs_chash_unlock(hfsmp);
91447636 A	184
	185	if ((error = vnode_getwithvid(vp, vid))) {
	186	/*
	187	* If vnode is being reclaimed, or has
	188	* already changed identity, no need to wait
9bccf70c	189	*/
91447636	190	return (NULL);
9bccf70c	191	}
91447636 A	192	if (!skiplock && hfs_lock(cp, HFS_EXCLUSIVE_LOCK) != 0) {
	193	vnode_put(vp);
	194	return (NULL);
	195	}
	196
	197	/*
	198	* Skip cnodes that are not in the name space anymore
2d21ac55 A	199	* we need to check with the cnode lock held because
	200	* we may have blocked acquiring the vnode ref or the
	201	* lock on the cnode which would allow the node to be
	202	* unlinked
91447636 A	203	*/
	204	if (cp->c_flag & (C_NOEXISTS \| C_DELETED)) {
	205	if (!skiplock)
	206	hfs_unlock(cp);
	207	vnode_put(vp);
	208
	209	return (NULL);
	210	}
	211	return (vp);
	212	}
	213	exit:
b0d623f7	214	hfs_chash_unlock(hfsmp);
91447636 A	215	return (NULL);
	216	}
	217
	218
	219	/*
2d21ac55	220	* Use the device, fileid pair to snoop an incore cnode.
91447636 A	221	*/
	222	__private_extern__
	223	int
b0d623f7	224	hfs_chash_snoop(struct hfsmount hfsmp, ino_t inum, int (callout)(const struct cat_desc *,
91447636 A	225	const struct cat_attr , void ), void * arg)
	226	{
	227	struct cnode *cp;
	228	int result = ENOENT;
	229
	230	/*
	231	* Go through the hash list
	232	* If a cnode is in the process of being cleaned out or being
	233	* allocated, wait for it to be finished and then try again.
	234	*/
b0d623f7 A	235	hfs_chash_lock(hfsmp);
	236
	237	for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
	238	if (cp->c_fileid != inum)
9bccf70c	239	continue;
91447636 A	240	/* Skip cnodes being created or reclaimed. */
	241	if (!ISSET(cp->c_hflag, H_ALLOC \| H_TRANSIT \| H_ATTACH)) {
	242	result = callout(&cp->c_desc, &cp->c_attr, arg);
	243	}
	244	break;
	245	}
b0d623f7 A	246	hfs_chash_unlock(hfsmp);
b0d623f7 A	247
91447636 A	248	return (result);
	249	}
	250
9bccf70c	251
91447636 A	252	/*
	253	* Use the device, fileid pair to find the incore cnode.
	254	* If no cnode if found one is created
	255	*
	256	* If it is in core, but locked, wait for it.
2d21ac55 A	257	*
	258	* If the cnode is C_DELETED, then return NULL since that
	259	* inum is no longer valid for lookups (open-unlinked file).
91447636 A	260	*/
	261	__private_extern__
	262	struct cnode *
b0d623f7	263	hfs_chash_getcnode(struct hfsmount hfsmp, ino_t inum, struct vnode *vpp, int wantrsrc, int skiplock)
91447636 A	264	{
	265	struct cnode *cp;
	266	struct cnode *ncp = NULL;
	267	vnode_t vp;
2d21ac55	268	u_int32_t vid;
91447636 A	269
	270	/*
	271	* Go through the hash list
	272	* If a cnode is in the process of being cleaned out or being
	273	* allocated, wait for it to be finished and then try again.
	274	*/
	275	loop:
b0d623f7	276	hfs_chash_lock_spin(hfsmp);
91447636 A	277
91447636 A	278	loop_with_lock:
b0d623f7 A	279	for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
b0d623f7 A	280	if (cp->c_fileid != inum)
91447636	281	continue;
9bccf70c	282	/*
91447636	283	* Wait if cnode is being created, attached to or reclaimed.
9bccf70c	284	*/
91447636 A	285	if (ISSET(cp->c_hflag, H_ALLOC \| H_ATTACH \| H_TRANSIT)) {
91447636 A	286	SET(cp->c_hflag, H_WAITING);
9bccf70c	287
b0d623f7	288	(void) msleep(cp, &hfsmp->hfs_chash_mutex, PINOD,
91447636 A	289	"hfs_chash_getcnode", 0);
	290	goto loop_with_lock;
	291	}
91447636 A	292	vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
91447636 A	293	if (vp == NULL) {
9bccf70c	294	/*
91447636	295	* The desired vnode isn't there so tag the cnode.
9bccf70c	296	*/
91447636 A	297	SET(cp->c_hflag, H_ATTACH);
91447636 A	298
b0d623f7	299	hfs_chash_unlock(hfsmp);
91447636 A	300	} else {
	301	vid = vnode_vid(vp);
	302
b0d623f7	303	hfs_chash_unlock(hfsmp);
91447636 A	304
	305	if (vnode_getwithvid(vp, vid))
	306	goto loop;
	307	}
	308	if (ncp) {
	309	/*
	310	* someone else won the race to create
	311	* this cnode and add it to the hash
	312	* just dump our allocation
	313	*/
	314	FREE_ZONE(ncp, sizeof(struct cnode), M_HFSNODE);
	315	ncp = NULL;
9bccf70c A	316	}
9bccf70c A	317
2d21ac55 A	318	if (!skiplock) {
2d21ac55 A	319	hfs_lock(cp, HFS_FORCE_LOCK);
91447636	320	}
2d21ac55	321
9bccf70c	322	/*
91447636	323	* Skip cnodes that are not in the name space anymore
2d21ac55 A	324	* we need to check with the cnode lock held because
	325	* we may have blocked acquiring the vnode ref or the
	326	* lock on the cnode which would allow the node to be
	327	* unlinked.
	328	*
	329	* Don't return a cnode in this case since the inum
	330	* is no longer valid for lookups.
9bccf70c	331	*/
2d21ac55	332	if ((cp->c_flag & (C_NOEXISTS \| C_DELETED)) && !wantrsrc) {
91447636 A	333	if (!skiplock)
91447636 A	334	hfs_unlock(cp);
2d21ac55	335	if (vp != NULLVP) {
91447636	336	vnode_put(vp);
2d21ac55	337	} else {
b0d623f7	338	hfs_chash_lock_spin(hfsmp);
2d21ac55 A	339	CLR(cp->c_hflag, H_ATTACH);
	340	if (ISSET(cp->c_hflag, H_WAITING)) {
	341	CLR(cp->c_hflag, H_WAITING);
	342	wakeup((caddr_t)cp);
	343	}
b0d623f7	344	hfs_chash_unlock(hfsmp);
2d21ac55 A	345	}
	346	vp = NULL;
	347	cp = NULL;
9bccf70c	348	}
91447636	349	*vpp = vp;
9bccf70c A	350	return (cp);
9bccf70c A	351	}
91447636 A	352
	353	/*
	354	* Allocate a new cnode
	355	*/
2d21ac55	356	if (skiplock && !wantrsrc)
91447636 A	357	panic("%s - should never get here when skiplock is set \n", __FUNCTION__);
	358
	359	if (ncp == NULL) {
b0d623f7	360	hfs_chash_unlock(hfsmp);
91447636 A	361
	362	MALLOC_ZONE(ncp, struct cnode *, sizeof(struct cnode), M_HFSNODE, M_WAITOK);
	363	/*
	364	* since we dropped the chash lock,
	365	* we need to go back and re-verify
	366	* that this node hasn't come into
	367	* existence...
	368	*/
	369	goto loop;
	370	}
b0d623f7 A	371	hfs_chash_lock_convert(hfsmp);
b0d623f7 A	372
91447636 A	373	bzero(ncp, sizeof(struct cnode));
	374	SET(ncp->c_hflag, H_ALLOC);
	375	ncp->c_fileid = inum;
b36670ce	376	TAILQ_INIT(&ncp->c_hintlist); /* make the list empty */
2d21ac55	377	TAILQ_INIT(&ncp->c_originlist);
91447636 A	378
	379	lck_rw_init(&ncp->c_rwlock, hfs_rwlock_group, hfs_lock_attr);
	380	if (!skiplock)
	381	(void) hfs_lock(ncp, HFS_EXCLUSIVE_LOCK);
	382
	383	/* Insert the new cnode with it's H_ALLOC flag set */
b0d623f7 A	384	LIST_INSERT_HEAD(CNODEHASH(hfsmp, inum), ncp, c_hash);
b0d623f7 A	385	hfs_chash_unlock(hfsmp);
91447636 A	386
	387	*vpp = NULL;
	388	return (ncp);
	389	}
	390
	391
	392	__private_extern__
	393	void
b0d623f7	394	hfs_chashwakeup(struct hfsmount hfsmp, struct cnode cp, int hflags)
91447636	395	{
b0d623f7	396	hfs_chash_lock_spin(hfsmp);
91447636 A	397
	398	CLR(cp->c_hflag, hflags);
	399
	400	if (ISSET(cp->c_hflag, H_WAITING)) {
	401	CLR(cp->c_hflag, H_WAITING);
	402	wakeup((caddr_t)cp);
	403	}
b0d623f7	404	hfs_chash_unlock(hfsmp);
9bccf70c A	405	}
	406
	407
	408	/*
91447636	409	* Re-hash two cnodes in the hash table.
9bccf70c A	410	*/
	411	__private_extern__
	412	void
b0d623f7	413	hfs_chash_rehash(struct hfsmount hfsmp, struct cnode cp1, struct cnode *cp2)
9bccf70c	414	{
b0d623f7	415	hfs_chash_lock_spin(hfsmp);
91447636 A	416
	417	LIST_REMOVE(cp1, c_hash);
	418	LIST_REMOVE(cp2, c_hash);
b0d623f7 A	419	LIST_INSERT_HEAD(CNODEHASH(hfsmp, cp1->c_fileid), cp1, c_hash);
b0d623f7 A	420	LIST_INSERT_HEAD(CNODEHASH(hfsmp, cp2->c_fileid), cp2, c_hash);
91447636	421
b0d623f7	422	hfs_chash_unlock(hfsmp);
9bccf70c A	423	}
	424
	425
	426	/*
	427	* Remove a cnode from the hash table.
	428	*/
	429	__private_extern__
91447636	430	int
b0d623f7	431	hfs_chashremove(struct hfsmount hfsmp, struct cnode cp)
9bccf70c	432	{
b0d623f7	433	hfs_chash_lock_spin(hfsmp);
91447636 A	434
	435	/* Check if a vnode is getting attached */
	436	if (ISSET(cp->c_hflag, H_ATTACH)) {
b0d623f7	437	hfs_chash_unlock(hfsmp);
91447636 A	438	return (EBUSY);
91447636 A	439	}
2d21ac55 A	440	if (cp->c_hash.le_next \|\| cp->c_hash.le_prev) {
	441	LIST_REMOVE(cp, c_hash);
	442	cp->c_hash.le_next = NULL;
	443	cp->c_hash.le_prev = NULL;
	444	}
b0d623f7 A	445	hfs_chash_unlock(hfsmp);
b0d623f7 A	446
91447636 A	447	return (0);
	448	}
	449
	450	/*
	451	* Remove a cnode from the hash table and wakeup any waiters.
	452	*/
	453	__private_extern__
	454	void
b0d623f7	455	hfs_chash_abort(struct hfsmount hfsmp, struct cnode cp)
91447636	456	{
b0d623f7	457	hfs_chash_lock_spin(hfsmp);
91447636	458
9bccf70c A	459	LIST_REMOVE(cp, c_hash);
	460	cp->c_hash.le_next = NULL;
	461	cp->c_hash.le_prev = NULL;
91447636 A	462
	463	CLR(cp->c_hflag, H_ATTACH \| H_ALLOC);
	464	if (ISSET(cp->c_hflag, H_WAITING)) {
	465	CLR(cp->c_hflag, H_WAITING);
	466	wakeup((caddr_t)cp);
	467	}
b0d623f7	468	hfs_chash_unlock(hfsmp);
9bccf70c A	469	}
9bccf70c A	470
91447636 A	471
91447636 A	472	/*
2d21ac55	473	* mark a cnode as in transition
91447636 A	474	*/
	475	__private_extern__
	476	void
b0d623f7	477	hfs_chash_mark_in_transit(struct hfsmount hfsmp, struct cnode cp)
91447636	478	{
b0d623f7	479	hfs_chash_lock_spin(hfsmp);
91447636 A	480
	481	SET(cp->c_hflag, H_TRANSIT);
	482
b0d623f7	483	hfs_chash_unlock(hfsmp);
2d21ac55 A	484	}
	485
	486	/* Search a cnode in the hash. This function does not return cnode which
	487	* are getting created, destroyed or in transition. Note that this function
	488	* does not acquire the cnode hash mutex, and expects the caller to acquire it.
	489	* On success, returns pointer to the cnode found. On failure, returns NULL.
	490	*/
	491	static
	492	struct cnode *
b0d623f7	493	hfs_chash_search_cnid(struct hfsmount *hfsmp, cnid_t cnid)
2d21ac55 A	494	{
	495	struct cnode *cp;
	496
b0d623f7 A	497	for (cp = CNODEHASH(hfsmp, cnid)->lh_first; cp; cp = cp->c_hash.le_next) {
b0d623f7 A	498	if (cp->c_fileid == cnid) {
2d21ac55 A	499	break;
	500	}
	501	}
	502
	503	/* If cnode is being created or reclaimed, return error. */
	504	if (cp && ISSET(cp->c_hflag, H_ALLOC \| H_TRANSIT \| H_ATTACH)) {
	505	cp = NULL;
	506	}
	507
	508	return cp;
	509	}
	510
	511	/* Search a cnode corresponding to given device and ID in the hash. If the
	512	* found cnode has kHFSHasChildLinkBit cleared, set it. If the cnode is not
	513	* found, no new cnode is created and error is returned.
	514	*
	515	* Return values -
	516	* -1 : The cnode was not found.
	517	* 0 : The cnode was found, and the kHFSHasChildLinkBit was already set.
	518	* 1 : The cnode was found, the kHFSHasChildLinkBit was not set, and the
	519	* function had to set that bit.
	520	*/
	521	__private_extern__
	522	int
b0d623f7	523	hfs_chash_set_childlinkbit(struct hfsmount *hfsmp, cnid_t cnid)
2d21ac55 A	524	{
	525	int retval = -1;
	526	struct cnode *cp;
	527
b0d623f7 A	528	hfs_chash_lock_spin(hfsmp);
	529
	530	cp = hfs_chash_search_cnid(hfsmp, cnid);
2d21ac55 A	531	if (cp) {
	532	if (cp->c_attr.ca_recflags & kHFSHasChildLinkMask) {
	533	retval = 0;
	534	} else {
	535	cp->c_attr.ca_recflags \|= kHFSHasChildLinkMask;
	536	retval = 1;
	537	}
	538	}
b0d623f7	539	hfs_chash_unlock(hfsmp);
2d21ac55 A	540
2d21ac55 A	541	return retval;
91447636	542	}