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

/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (the
 * "License").  You may not use this file except in compliance with the
 * License.  Please obtain a copy of the License at
 * http://www.apple.com/publicsource and read it before using this file.
 * 
 * This 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 OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */

/* Copyright (c) 1998 Apple Computer, Inc. All Rights Reserved */
/*
 * 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_vhash.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/malloc.h>
#include <sys/proc.h>
#include <sys/queue.h>

#include "hfs.h"
#include "hfs_dbg.h"


/*
 * Structures associated with hfsnode cacheing.
 */
LIST_HEAD(vhashhead, hfsnode) *vhashtbl;
u_long	vhash;		/* size of hash table - 1 */
#define HFSNODEHASH(device, nodeID) (&vhashtbl[((device) + (nodeID)) & vhash])
struct slock hfs_vhash_slock;

/*
 * Initialize hfsnode hash table.
 */
void
hfs_vhashinit()
{

	vhashtbl = hashinit(desiredvnodes, M_HFSMNT, &vhash);
	simple_lock_init(&hfs_vhash_slock);
}

/*
 * Use the device/dirID/forkType tuple to find the incore hfsnode, and return a pointer
 * to it. If it is in core, but locked, wait for it.
 * 
 * Acceptable forkTypes are kData, kRsrcFork, kDirectory, or kDefault which translates to either
 * kDataFork or kDirectory
 *
 * While traversing the hash, expext that a hfsnode is in the midst of being allocated, if so, 
 * then sleep and try again
 */
struct vnode *
hfs_vhashget(dev, nodeID, forkType)
	dev_t dev;
	UInt32 nodeID;
	UInt8	forkType;
{
	struct proc *p = current_proc();	/* XXX */
	struct hfsnode *hp;
	struct vnode *vp;

	DBG_ASSERT(forkType!=kUndefinedFork);
	/* 
	 * Go through the hash list
	 * If a vnode 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_vhash_slock);
	for (hp = HFSNODEHASH(dev, nodeID)->lh_first; hp; hp = hp->h_hash.le_next) {
		/* The vnode might be in an incomplete state, so sleep until its ready */
		if (hp->h_nodeflags & IN_ALLOCATING) {
			simple_unlock(&hfs_vhash_slock);
			tsleep((caddr_t)hp, PINOD, "hfs_vhashlookup", 0);
			goto loop;
		};
			
		DBG_ASSERT(hp->h_meta != NULL);
		if ((H_FILEID(hp) == nodeID)  &&
			(H_DEV(hp) == dev)  &&
			!(hp->h_meta->h_metaflags & IN_NOEXISTS)) {
			/* SER XXX kDefault of meta data (ksysfile) is not assumed here */
			if ( (forkType == kAnyFork) ||
				 (H_FORKTYPE(hp) == forkType) || 
				 ((forkType == kDefault) && ((H_FORKTYPE(hp) == kDirectory)
							|| (H_FORKTYPE(hp) == kDataFork)))) {
				vp = HTOV(hp);
				simple_lock(&vp->v_interlock);
				simple_unlock(&hfs_vhash_slock);
				if (vget(vp, LK_EXCLUSIVE | LK_INTERLOCK, p))
					goto loop;
				return (vp);
			};
		};
	};
	simple_unlock(&hfs_vhash_slock);
	return (NULL);
}


/*
 * Lock the hfsnode and insert the hfsnode into the hash table, and return it locked.
 * Returns the sibling meta data if it exists, elses return NULL
 */
void
hfs_vhashins_sibling(dev, nodeID, hp, fm)
	dev_t dev;
	UInt32 nodeID;
	struct hfsnode *hp;
	struct hfsfilemeta **fm;
{
	struct vhashhead *ipp;
	struct hfsnode *thp;
	struct hfsfilemeta *tfm;

	DBG_ASSERT(fm != NULL);
	DBG_ASSERT(hp != NULL);
	DBG_ASSERT(hp->h_meta == NULL);
	DBG_ASSERT(H_FORKTYPE(hp)==kDataFork || H_FORKTYPE(hp)==kRsrcFork);

	tfm = NULL;
	lockmgr(&hp->h_lock, LK_EXCLUSIVE, (struct slock *)0, current_proc());


	/* 
	 * Go through the hash list to see if a sibling exists
	 * If it does, store it to return
	 * If a vnode is in the process of being cleaned out or being
	 * allocated, wait for it to be finished and then try again
	 */

	ipp = HFSNODEHASH(dev, nodeID);

loop:
	simple_lock(&hfs_vhash_slock);
	for (thp = ipp->lh_first; thp; thp = thp->h_hash.le_next)	{
		if (thp->h_nodeflags & IN_ALLOCATING) {		/* Its in the process of being allocated */
			simple_unlock(&hfs_vhash_slock);
			tsleep((caddr_t)thp, PINOD, "hfs_vhash_ins_meta", 0);
			goto loop;
		};
			
		DBG_ASSERT(thp->h_meta != NULL);
		if ((H_FILEID(thp) == nodeID) && (H_DEV(thp) == dev)) {
			tfm = hp->h_meta = thp->h_meta;
			break;
		};
	};
	
	/* Add to sibling list..if it can have them */
	if (tfm && (H_FORKTYPE(hp)==kDataFork || H_FORKTYPE(hp)==kRsrcFork)) {
		DBG_ASSERT(tfm->h_siblinghead.cqh_first != NULL && tfm->h_siblinghead.cqh_last != NULL);
		simple_lock(&tfm->h_siblinglock);
		CIRCLEQ_INSERT_HEAD(&tfm->h_siblinghead, hp, h_sibling);
		simple_unlock(&tfm->h_siblinglock);
	};

	LIST_INSERT_HEAD(ipp, hp, h_hash);
	simple_unlock(&hfs_vhash_slock);
	*fm = tfm;
}


/*
* Lock the hfsnode and insert the hfsnode into the hash table, and return it locked.
 */
void
hfs_vhashins(dev, nodeID, hp)
	dev_t dev;
	UInt32 nodeID;
     struct hfsnode *hp;
{
    struct vhashhead *ipp;

    DBG_ASSERT(hp != NULL);
    DBG_ASSERT(nodeID != 0);

    lockmgr(&hp->h_lock, LK_EXCLUSIVE, (struct slock *)0, current_proc());

    simple_lock(&hfs_vhash_slock);
    ipp = HFSNODEHASH(dev, nodeID);
    LIST_INSERT_HEAD(ipp, hp, h_hash);
    simple_unlock(&hfs_vhash_slock);
}


/*
 * Remove the hfsnode from the hash table and then checks to see if another forks exists.
 */
void
hfs_vhashrem(hp)
	struct hfsnode *hp;
{

	DBG_ASSERT(hp != NULL);
	DBG_ASSERT(hp->h_meta != NULL);
	
	simple_lock(&hfs_vhash_slock);
	
	/* Test to see if there are siblings, should only apply to forks */
	if (hp->h_meta->h_siblinghead.cqh_first != NULL) {
		simple_lock(&hp->h_meta->h_siblinglock);
		CIRCLEQ_REMOVE(&hp->h_meta->h_siblinghead, hp, h_sibling);
		simple_unlock(&hp->h_meta->h_siblinglock);
	};
	
	LIST_REMOVE(hp, h_hash);

#if HFS_DIAGNOSTIC
	hp->h_hash.le_next = NULL;
	hp->h_hash.le_prev = NULL;
#endif

	
	simple_unlock(&hfs_vhash_slock);


}


/*
 * Moves the entries from one bucket to another
 * nodeID is the old bucket id
 */
void
hfs_vhashmove(hp, oldNodeID)
	struct hfsnode *hp;
	UInt32 oldNodeID;
{
	struct vhashhead *oldHeadIndex, *newHeadIndex;
	struct hfsnode *thp, *nextNode;
	UInt32 newNodeID;

	DBG_ASSERT(hp != NULL);
	DBG_ASSERT(hp->h_meta != NULL);
	
    newNodeID = H_FILEID(hp);

    oldHeadIndex = HFSNODEHASH(H_DEV(hp), oldNodeID);
    newHeadIndex = HFSNODEHASH(H_DEV(hp), newNodeID);
	
	/* If it is moving to the same bucket...then we are done */
    if (oldHeadIndex == newHeadIndex)
		return;

loop:
	
	/* 
	 * Go through the old hash list
	 * If there is a nodeid mismatch, or the nodeid doesnt match the current bucket
	 * remove it and add it to the right bucket.
	 * If a vnode is in the process of being cleaned out or being
	 * allocated, wait for it to be finished and then try again
	 */
	simple_lock(&hfs_vhash_slock);
    for (nextNode = oldHeadIndex->lh_first; nextNode; )	{
        if (nextNode->h_nodeflags & IN_ALLOCATING) {		/* Its in the process of being allocated */
			simple_unlock(&hfs_vhash_slock);
            tsleep((caddr_t)nextNode, PINOD, "hfs_vhashmove", 0);
			goto loop;
			};
			
        DBG_ASSERT(nextNode->h_meta != NULL);
		thp = nextNode;
        nextNode = nextNode->h_hash.le_next;
		if (newNodeID == H_FILEID(thp)) {
			LIST_REMOVE(thp, h_hash);
            thp->h_hash.le_next = NULL;
            thp->h_hash.le_next = NULL;
            LIST_INSERT_HEAD(newHeadIndex, thp, h_hash);
			};
		};
	
	simple_unlock(&hfs_vhash_slock);
}

#if HFS_DIAGNOSTIC
/*
 * This will test the hash entry for a given hfsnode
 * It will test:
 *		1. The uniqei existance of the node
 *		2. All other nodes, proper membership to the hash
 *		3. Proper termination of the hash
 *		4. All members have a non-null h_meta
 */
void hfs_vhash_dbg(hp)
	struct hfsnode *hp;
{
	struct proc *p = current_proc();	/* XXX */
	struct vnode *vp;
	struct hfsnode *thp, *tthp;
	int			maxsiblings = 1;
	int			wasFound = false;
	struct vhashhead *ipp, *jpp;
	dev_t 		dev = H_DEV(hp);
	UInt32 		nodeID = H_FILEID(hp);
	UInt8		forkType = H_FORKTYPE(hp);
	u_long		forksfound = 0;
	
	if (forkType==kDataFork || forkType==kRsrcFork)
		maxsiblings++;
		
	if (hp == NULL)
    	DEBUG_BREAK_MSG(("hash_dgh: Null hfsnode"));
	/* 
	 * Go through the hash list
	 * If a vnode is in the process of being cleaned out or being
	 * allocated, wait for it to be finished and then try again
	 */
	ipp = HFSNODEHASH(dev, nodeID);

loop:
	simple_lock(&hfs_vhash_slock);
	for (thp = ipp->lh_first; thp; thp = thp->h_hash.le_next)	{
		if (thp->h_nodeflags & IN_ALLOCATING) {		/* Its in the process of being allocated */
			simple_unlock(&hfs_vhash_slock);
			tsleep((caddr_t)thp, PINOD, "hfs_vhash_ins_meta", 0);
			goto loop;
		};
			
		if (thp->h_meta == NULL)
	    	DEBUG_BREAK_MSG(("hash_dgh: Null hfs_meta"));
	    jpp = (HFSNODEHASH(H_DEV(thp), H_FILEID(thp)));
	    if (ipp != jpp)
	    	DEBUG_BREAK_MSG(("hash_dgh: Member on wrong hash"));

		if ((H_FILEID(thp) == nodeID) && (H_DEV(thp) == dev)) {
			maxsiblings--;
			if (maxsiblings < 0)
		    	DEBUG_BREAK_MSG(("hash_dgh: Too many siblings"));
		    if ((1<<H_FORKTYPE(thp)) & forksfound)
		    	DEBUG_BREAK_MSG(("hash_dgh: Fork already found"));
		    forksfound |= (1<<H_FORKTYPE(thp));
		    
		    if (H_FORKTYPE(thp) == forkType) {
				if (wasFound == true)
			    	DEBUG_BREAK_MSG(("hash_dgh: Already found"));
		    	wasFound = true;
		    };
		};
	};
	simple_unlock(&hfs_vhash_slock);

	if (! wasFound)
    	DEBUG_BREAK_MSG(("hash_dgh: Not found"));

}

#endif /* HFS_DIAGNOSTIC */
Commit	Line	Data
1c79356b A	1	/*
	2	* Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
	6	* The contents of this file constitute Original Code as defined in and
	7	* are subject to the Apple Public Source License Version 1.1 (the
	8	* "License"). You may not use this file except in compliance with the
	9	* License. Please obtain a copy of the License at
	10	* http://www.apple.com/publicsource and read it before using this file.
	11	*
	12	* This Original Code and all software distributed under the License are
	13	* distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	14	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	15	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	16	* FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
	17	* License for the specific language governing rights and limitations
	18	* under the License.
	19	*
	20	* @APPLE_LICENSE_HEADER_END@
	21	*/
	22
	23	/* Copyright (c) 1998 Apple Computer, Inc. All Rights Reserved */
	24	/*
	25	* Copyright (c) 1982, 1986, 1989, 1991, 1993, 1995
	26	* The Regents of the University of California. All rights reserved.
	27	*
	28	* Redistribution and use in source and binary forms, with or without
	29	* modification, are permitted provided that the following conditions
	30	* are met:
	31	* 1. Redistributions of source code must retain the above copyright
	32	* notice, this list of conditions and the following disclaimer.
	33	* 2. Redistributions in binary form must reproduce the above copyright
	34	* notice, this list of conditions and the following disclaimer in the
	35	* documentation and/or other materials provided with the distribution.
	36	* 3. All advertising materials mentioning features or use of this software
	37	* must display the following acknowledgement:
	38	* This product includes software developed by the University of
	39	* California, Berkeley and its contributors.
	40	* 4. Neither the name of the University nor the names of its contributors
	41	* may be used to endorse or promote products derived from this software
	42	* without specific prior written permission.
	43	*
	44	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	45	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	46	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	47	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	48	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	49	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	50	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	51	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	52	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	53	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	54	* SUCH DAMAGE.
	55	*
	56	* @(#)hfs_vhash.c
	57	* derived from @(#)ufs_ihash.c 8.7 (Berkeley) 5/17/95
	58	*/
	59
	60	#include <sys/param.h>
	61	#include <sys/systm.h>
	62	#include <sys/vnode.h>
	63	#include <sys/malloc.h>
	64	#include <sys/proc.h>
65	#include <sys/queue.h>
66
67	#include "hfs.h"
68	#include "hfs_dbg.h"
69
70
71	/*
72	* Structures associated with hfsnode cacheing.
73	*/
74	LIST_HEAD(vhashhead, hfsnode) *vhashtbl;
75	u_long vhash; /* size of hash table - 1 */
76	#define HFSNODEHASH(device, nodeID) (&vhashtbl[((device) + (nodeID)) & vhash])
77	struct slock hfs_vhash_slock;
78
79	/*
80	* Initialize hfsnode hash table.
81	*/
82	void
83	hfs_vhashinit()
84	{
85
86	vhashtbl = hashinit(desiredvnodes, M_HFSMNT, &vhash);
87	simple_lock_init(&hfs_vhash_slock);
88	}
89
90	/*
91	* Use the device/dirID/forkType tuple to find the incore hfsnode, and return a pointer
92	* to it. If it is in core, but locked, wait for it.
93	*
94	* Acceptable forkTypes are kData, kRsrcFork, kDirectory, or kDefault which translates to either
95	* kDataFork or kDirectory
96	*
97	* While traversing the hash, expext that a hfsnode is in the midst of being allocated, if so,
98	* then sleep and try again
99	*/
100	struct vnode *
101	hfs_vhashget(dev, nodeID, forkType)
102	dev_t dev;
103	UInt32 nodeID;
104	UInt8 forkType;
105	{
106	struct proc p = current_proc(); / XXX */
107	struct hfsnode *hp;
108	struct vnode *vp;
109
110	DBG_ASSERT(forkType!=kUndefinedFork);
111	/*
112	* Go through the hash list
113	* If a vnode is in the process of being cleaned out or being
114	* allocated, wait for it to be finished and then try again
115	*/
116	loop:
117	simple_lock(&hfs_vhash_slock);
118	for (hp = HFSNODEHASH(dev, nodeID)->lh_first; hp; hp = hp->h_hash.le_next) {
119	/* The vnode might be in an incomplete state, so sleep until its ready */
120	if (hp->h_nodeflags & IN_ALLOCATING) {
121	simple_unlock(&hfs_vhash_slock);
122	tsleep((caddr_t)hp, PINOD, "hfs_vhashlookup", 0);
123	goto loop;
124	};
125
126	DBG_ASSERT(hp->h_meta != NULL);
127	if ((H_FILEID(hp) == nodeID) &&
128	(H_DEV(hp) == dev) &&
129	!(hp->h_meta->h_metaflags & IN_NOEXISTS)) {
130	/* SER XXX kDefault of meta data (ksysfile) is not assumed here */
0b4e3aa0 A	131	if ( (forkType == kAnyFork) \|\|
	132	(H_FORKTYPE(hp) == forkType) \|\|
	133	((forkType == kDefault) && ((H_FORKTYPE(hp) == kDirectory)
1c79356b A	134	\|\| (H_FORKTYPE(hp) == kDataFork)))) {
	135	vp = HTOV(hp);
	136	simple_lock(&vp->v_interlock);
	137	simple_unlock(&hfs_vhash_slock);
	138	if (vget(vp, LK_EXCLUSIVE \| LK_INTERLOCK, p))
	139	goto loop;
	140	return (vp);
	141	};
	142	};
	143	};
	144	simple_unlock(&hfs_vhash_slock);
	145	return (NULL);
	146	}
	147
	148
	149
	150
	151	/*
	152	* Lock the hfsnode and insert the hfsnode into the hash table, and return it locked.
	153	* Returns the sibling meta data if it exists, elses return NULL
	154	*/
	155	void
	156	hfs_vhashins_sibling(dev, nodeID, hp, fm)
	157	dev_t dev;
	158	UInt32 nodeID;
	159	struct hfsnode *hp;
	160	struct hfsfilemeta **fm;
	161	{
	162	struct vhashhead *ipp;
	163	struct hfsnode *thp;
	164	struct hfsfilemeta *tfm;
	165
	166	DBG_ASSERT(fm != NULL);
	167	DBG_ASSERT(hp != NULL);
	168	DBG_ASSERT(hp->h_meta == NULL);
	169	DBG_ASSERT(H_FORKTYPE(hp)==kDataFork \|\| H_FORKTYPE(hp)==kRsrcFork);
	170
	171	tfm = NULL;
	172	lockmgr(&hp->h_lock, LK_EXCLUSIVE, (struct slock *)0, current_proc());
	173
	174
	175	/*
	176	* Go through the hash list to see if a sibling exists
	177	* If it does, store it to return
	178	* If a vnode is in the process of being cleaned out or being
	179	* allocated, wait for it to be finished and then try again
	180	*/
	181
	182	ipp = HFSNODEHASH(dev, nodeID);
	183
	184	loop:
	185	simple_lock(&hfs_vhash_slock);
	186	for (thp = ipp->lh_first; thp; thp = thp->h_hash.le_next) {
	187	if (thp->h_nodeflags & IN_ALLOCATING) { /* Its in the process of being allocated */
	188	simple_unlock(&hfs_vhash_slock);
	189	tsleep((caddr_t)thp, PINOD, "hfs_vhash_ins_meta", 0);
	190	goto loop;
	191	};
	192
	193	DBG_ASSERT(thp->h_meta != NULL);
	194	if ((H_FILEID(thp) == nodeID) && (H_DEV(thp) == dev)) {
	195	tfm = hp->h_meta = thp->h_meta;
	196	break;
	197	};
198	};
199
200	/* Add to sibling list..if it can have them */
201	if (tfm && (H_FORKTYPE(hp)==kDataFork \|\| H_FORKTYPE(hp)==kRsrcFork)) {
202	DBG_ASSERT(tfm->h_siblinghead.cqh_first != NULL && tfm->h_siblinghead.cqh_last != NULL);
203	simple_lock(&tfm->h_siblinglock);
204	CIRCLEQ_INSERT_HEAD(&tfm->h_siblinghead, hp, h_sibling);
205	simple_unlock(&tfm->h_siblinglock);
206	};
207
208	LIST_INSERT_HEAD(ipp, hp, h_hash);
209	simple_unlock(&hfs_vhash_slock);
210	*fm = tfm;
211	}
212
213
214
215	/*
216	* Lock the hfsnode and insert the hfsnode into the hash table, and return it locked.
217	*/
218	void
219	hfs_vhashins(dev, nodeID, hp)
220	dev_t dev;
221	UInt32 nodeID;
222	struct hfsnode *hp;
223	{
224	struct vhashhead *ipp;
225
226	DBG_ASSERT(hp != NULL);
227	DBG_ASSERT(nodeID != 0);
228
229	lockmgr(&hp->h_lock, LK_EXCLUSIVE, (struct slock *)0, current_proc());
230
231	simple_lock(&hfs_vhash_slock);
232	ipp = HFSNODEHASH(dev, nodeID);
233	LIST_INSERT_HEAD(ipp, hp, h_hash);
234	simple_unlock(&hfs_vhash_slock);
235	}
236
237
238	/*
239	* Remove the hfsnode from the hash table and then checks to see if another forks exists.
240	*/
241	void
242	hfs_vhashrem(hp)
243	struct hfsnode *hp;
244	{
245
246	DBG_ASSERT(hp != NULL);
247	DBG_ASSERT(hp->h_meta != NULL);
248
249	simple_lock(&hfs_vhash_slock);
250
251	/* Test to see if there are siblings, should only apply to forks */
252	if (hp->h_meta->h_siblinghead.cqh_first != NULL) {
253	simple_lock(&hp->h_meta->h_siblinglock);
254	CIRCLEQ_REMOVE(&hp->h_meta->h_siblinghead, hp, h_sibling);
255	simple_unlock(&hp->h_meta->h_siblinglock);
256	};
257
258	LIST_REMOVE(hp, h_hash);
259
260	#if HFS_DIAGNOSTIC
261	hp->h_hash.le_next = NULL;
262	hp->h_hash.le_prev = NULL;
263	#endif
264
265
266	simple_unlock(&hfs_vhash_slock);
267
268
269	}
270
271
272	/*
273	* Moves the entries from one bucket to another
274	* nodeID is the old bucket id
275	*/
276	void
277	hfs_vhashmove(hp, oldNodeID)
278	struct hfsnode *hp;
279	UInt32 oldNodeID;
280	{
281	struct vhashhead oldHeadIndex, newHeadIndex;
282	struct hfsnode thp, nextNode;
283	UInt32 newNodeID;
284
285	DBG_ASSERT(hp != NULL);
286	DBG_ASSERT(hp->h_meta != NULL);
287
288	newNodeID = H_FILEID(hp);
289
290	oldHeadIndex = HFSNODEHASH(H_DEV(hp), oldNodeID);
291	newHeadIndex = HFSNODEHASH(H_DEV(hp), newNodeID);
292
293	/* If it is moving to the same bucket...then we are done */
294	if (oldHeadIndex == newHeadIndex)
295	return;
296
297	loop:
298
299	/*
300	* Go through the old hash list
301	* If there is a nodeid mismatch, or the nodeid doesnt match the current bucket
302	* remove it and add it to the right bucket.
303	* If a vnode is in the process of being cleaned out or being
304	* allocated, wait for it to be finished and then try again
305	*/
306	simple_lock(&hfs_vhash_slock);
307	for (nextNode = oldHeadIndex->lh_first; nextNode; ) {
308	if (nextNode->h_nodeflags & IN_ALLOCATING) { /* Its in the process of being allocated */
309	simple_unlock(&hfs_vhash_slock);
310	tsleep((caddr_t)nextNode, PINOD, "hfs_vhashmove", 0);
311	goto loop;
312	};
313
314	DBG_ASSERT(nextNode->h_meta != NULL);
315	thp = nextNode;
316	nextNode = nextNode->h_hash.le_next;
317	if (newNodeID == H_FILEID(thp)) {
318	LIST_REMOVE(thp, h_hash);
319	thp->h_hash.le_next = NULL;
320	thp->h_hash.le_next = NULL;
321	LIST_INSERT_HEAD(newHeadIndex, thp, h_hash);
322	};
323	};
324
325	simple_unlock(&hfs_vhash_slock);
326	}
327
328	#if HFS_DIAGNOSTIC
329	/*
330	* This will test the hash entry for a given hfsnode
331	* It will test:
332	* 1. The uniqei existance of the node
333	* 2. All other nodes, proper membership to the hash
334	* 3. Proper termination of the hash
335	* 4. All members have a non-null h_meta
336	*/
337	void hfs_vhash_dbg(hp)
338	struct hfsnode *hp;
339	{
340	struct proc p = current_proc(); / XXX */
341	struct vnode *vp;
342	struct hfsnode thp, tthp;
343	int maxsiblings = 1;
344	int wasFound = false;
345	struct vhashhead ipp, jpp;
346	dev_t dev = H_DEV(hp);
347	UInt32 nodeID = H_FILEID(hp);
348	UInt8 forkType = H_FORKTYPE(hp);
349	u_long forksfound = 0;
350
351	if (forkType==kDataFork \|\| forkType==kRsrcFork)
352	maxsiblings++;
353
354	if (hp == NULL)
355	DEBUG_BREAK_MSG(("hash_dgh: Null hfsnode"));
356	/*
357	* Go through the hash list
358	* If a vnode is in the process of being cleaned out or being
359	* allocated, wait for it to be finished and then try again
360	*/
361	ipp = HFSNODEHASH(dev, nodeID);
362
363	loop:
364	simple_lock(&hfs_vhash_slock);
365	for (thp = ipp->lh_first; thp; thp = thp->h_hash.le_next) {
366	if (thp->h_nodeflags & IN_ALLOCATING) { /* Its in the process of being allocated */
367	simple_unlock(&hfs_vhash_slock);
368	tsleep((caddr_t)thp, PINOD, "hfs_vhash_ins_meta", 0);
369	goto loop;
370	};
371
372	if (thp->h_meta == NULL)
373	DEBUG_BREAK_MSG(("hash_dgh: Null hfs_meta"));
374	jpp = (HFSNODEHASH(H_DEV(thp), H_FILEID(thp)));
375	if (ipp != jpp)
376	DEBUG_BREAK_MSG(("hash_dgh: Member on wrong hash"));
377
378	if ((H_FILEID(thp) == nodeID) && (H_DEV(thp) == dev)) {
379	maxsiblings--;
380	if (maxsiblings < 0)
381	DEBUG_BREAK_MSG(("hash_dgh: Too many siblings"));
382	if ((1<<H_FORKTYPE(thp)) & forksfound)
383	DEBUG_BREAK_MSG(("hash_dgh: Fork already found"));
384	forksfound \|= (1<<H_FORKTYPE(thp));
385
386	if (H_FORKTYPE(thp) == forkType) {
387	if (wasFound == true)
388	DEBUG_BREAK_MSG(("hash_dgh: Already found"));
389	wasFound = true;
390	};
391	};
392	};
393	simple_unlock(&hfs_vhash_slock);
394
395	if (! wasFound)
396	DEBUG_BREAK_MSG(("hash_dgh: Not found"));
397
398	}
399
400	#endif /* HFS_DIAGNOSTIC */