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

/*
 * Copyright (c) 2002-2003 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * 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_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/malloc.h>
#include <sys/proc.h>
#include <sys/queue.h>

#include "hfs_cnode.h"


/*
 * Structures associated with cnode caching.
 */
LIST_HEAD(cnodehashhead, cnode) *cnodehashtbl;
u_long	cnodehash;		/* size of hash table - 1 */
#define CNODEHASH(device, inum) (&cnodehashtbl[((device) + (inum)) & cnodehash])
struct slock hfs_chash_slock;

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


/*
 * Use the device, inum pair to find the incore cnode.
 *
 * If it is in core, but locked, wait for it.
 *
 * If the requested vnode (fork) is not available, then
 * take a reference on the other vnode (fork) so that
 * the upcoming getnewvnode can not aquire it.
 */
__private_extern__
struct cnode *
hfs_chashget(dev_t dev, ino_t inum, int wantrsrc,
		struct vnode **vpp, struct vnode **rvpp)
{
	struct proc *p = current_proc();
	struct cnode *cp;
	struct vnode *vp;
	int error;

	*vpp = NULLVP;
	*rvpp = NULLVP;
	/* 
	 * Go through the hash list
	 * If a cnode is in the process of being cleaned out or being
	 * allocated, wait for it to be finished and then try again.
	 */
loop:
	simple_lock(&hfs_chash_slock);
	for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
		if ((cp->c_fileid != inum) || (cp->c_dev != dev))
			continue;
		if (ISSET(cp->c_flag, C_ALLOC)) {
			/*
			 * cnode is being created. Wait for it to finish.
			 */
			SET(cp->c_flag, C_WALLOC);
			simple_unlock(&hfs_chash_slock);
			(void) tsleep((caddr_t)cp, PINOD, "hfs_chashget-1", 0);
			goto loop;
		}	
		if (ISSET(cp->c_flag, C_TRANSIT)) {
			/*
			 * cnode is getting reclaimed wait for
			 * the operation to complete and return
			 * error
			 */
			SET(cp->c_flag, C_WTRANSIT);
			simple_unlock(&hfs_chash_slock);
			(void)tsleep((caddr_t)cp, PINOD, "hfs_chashget-2", 0);
			goto loop;
		}
		if (cp->c_flag & (C_NOEXISTS | C_DELETED))
			continue;

		/*
		 * Try getting the desired vnode first.  If
		 * it isn't available then take a reference
		 * on the other vnode.
		 */
		vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
		if (vp == NULLVP)
			vp = wantrsrc ? cp->c_vp : cp->c_rsrc_vp;
		if (vp == NULLVP)
			panic("hfs_chashget: orphaned cnode in hash");

		simple_lock(&vp->v_interlock);
		simple_unlock(&hfs_chash_slock);
		if (vget(vp, LK_EXCLUSIVE | LK_INTERLOCK, p))
			goto loop;
		else if (cp->c_flag & C_NOEXISTS) {
			/*
			 * While we were blocked the cnode got deleted.
			 */
			vput(vp);
			goto loop;
		}

		if (VNODE_IS_RSRC(vp))
			*rvpp = vp;
		else
			*vpp = vp;
		/*
		 * Note that vget can block before aquiring the
		 * cnode lock.  So we need to check if the vnode
		 * we wanted was created while we blocked.
		 */
		if (wantrsrc && *rvpp == NULL && cp->c_rsrc_vp) {
			error = vget(cp->c_rsrc_vp, 0, p);
			vrele(*vpp);	/* ref no longer needed */
			*vpp = NULL;
			if (error)
				goto loop;
			*rvpp = cp->c_rsrc_vp;

		} else if (!wantrsrc && *vpp == NULL && cp->c_vp) {
			error = vget(cp->c_vp, 0, p);
			vrele(*rvpp);	/* ref no longer needed */
			*rvpp = NULL;
			if (error)
				goto loop;
			*vpp = cp->c_vp;
		}
		return (cp);
	}
	simple_unlock(&hfs_chash_slock);
	return (NULL);
}


/*
 * Insert a cnode into the hash table.
 */
__private_extern__
void
hfs_chashinsert(struct cnode *cp)
{
	if (cp->c_fileid != 0) {
		simple_lock(&hfs_chash_slock);
		LIST_INSERT_HEAD(CNODEHASH(cp->c_dev, cp->c_fileid), cp, c_hash);
		simple_unlock(&hfs_chash_slock);
	}
}


/*
 * Remove a cnode from the hash table.
 */
__private_extern__
void
hfs_chashremove(struct cnode *cp)
{
	simple_lock(&hfs_chash_slock);
	LIST_REMOVE(cp, c_hash);
	cp->c_hash.le_next = NULL;
	cp->c_hash.le_prev = NULL;
	simple_unlock(&hfs_chash_slock);
}
Commit	Line	Data
9bccf70c	1	/*
55e303ae	2	* Copyright (c) 2002-2003 Apple Computer, Inc. All rights reserved.
9bccf70c A	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
43866e37	6	* Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
9bccf70c	7	*
43866e37 A	8	* This file contains Original Code and/or Modifications of Original Code
	9	* as defined in and that are subject to the Apple Public Source License
	10	* Version 2.0 (the 'License'). You may not use this file except in
	11	* compliance with the License. Please obtain a copy of the License at
	12	* http://www.opensource.apple.com/apsl/ and read it before using this
	13	* file.
	14	*
	15	* The Original Code and all software distributed under the License are
	16	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
9bccf70c A	17	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
9bccf70c A	18	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
43866e37 A	19	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	20	* Please see the License for the specific language governing rights and
	21	* limitations under the License.
9bccf70c A	22	*
	23	* @APPLE_LICENSE_HEADER_END@
	24	*/
	25
	26	/*
	27	* Copyright (c) 1982, 1986, 1989, 1991, 1993, 1995
	28	* The Regents of the University of California. All rights reserved.
	29	*
	30	* Redistribution and use in source and binary forms, with or without
	31	* modification, are permitted provided that the following conditions
	32	* are met:
	33	* 1. Redistributions of source code must retain the above copyright
	34	* notice, this list of conditions and the following disclaimer.
	35	* 2. Redistributions in binary form must reproduce the above copyright
	36	* notice, this list of conditions and the following disclaimer in the
	37	* documentation and/or other materials provided with the distribution.
	38	* 3. All advertising materials mentioning features or use of this software
	39	* must display the following acknowledgement:
	40	* This product includes software developed by the University of
	41	* California, Berkeley and its contributors.
	42	* 4. Neither the name of the University nor the names of its contributors
	43	* may be used to endorse or promote products derived from this software
	44	* without specific prior written permission.
	45	*
	46	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	47	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	48	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	49	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	50	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	51	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	52	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	53	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	54	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	55	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	56	* SUCH DAMAGE.
	57	*
	58	* @(#)hfs_chash.c
	59	* derived from @(#)ufs_ihash.c 8.7 (Berkeley) 5/17/95
	60	*/
	61
	62	#include <sys/param.h>
	63	#include <sys/systm.h>
	64	#include <sys/vnode.h>
	65	#include <sys/malloc.h>
	66	#include <sys/proc.h>
	67	#include <sys/queue.h>
	68
	69	#include "hfs_cnode.h"
	70
	71
	72	/*
	73	* Structures associated with cnode caching.
	74	*/
	75	LIST_HEAD(cnodehashhead, cnode) *cnodehashtbl;
	76	u_long cnodehash; /* size of hash table - 1 */
	77	#define CNODEHASH(device, inum) (&cnodehashtbl[((device) + (inum)) & cnodehash])
	78	struct slock hfs_chash_slock;
	79
	80	/*
	81	* Initialize cnode hash table.
	82	*/
	83	__private_extern__
	84	void
	85	hfs_chashinit()
86	{
87	cnodehashtbl = hashinit(desiredvnodes, M_HFSMNT, &cnodehash);
88	simple_lock_init(&hfs_chash_slock);
89	}
90
91
92	/*
93	* Use the device, inum pair to find the incore cnode.
94	*
95	* If it is in core, but locked, wait for it.
96	*
97	* If the requested vnode (fork) is not available, then
98	* take a reference on the other vnode (fork) so that
99	* the upcoming getnewvnode can not aquire it.
100	*/
101	__private_extern__
102	struct cnode *
103	hfs_chashget(dev_t dev, ino_t inum, int wantrsrc,
104	struct vnode vpp, struct vnode rvpp)
105	{
106	struct proc *p = current_proc();
107	struct cnode *cp;
108	struct vnode *vp;
109	int error;
110
111	*vpp = NULLVP;
112	*rvpp = NULLVP;
113	/*
114	* Go through the hash list
115	* If a cnode is in the process of being cleaned out or being
116	* allocated, wait for it to be finished and then try again.
117	*/
118	loop:
119	simple_lock(&hfs_chash_slock);
120	for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
121	if ((cp->c_fileid != inum) \|\| (cp->c_dev != dev))
122	continue;
123	if (ISSET(cp->c_flag, C_ALLOC)) {
124	/*
125	* cnode is being created. Wait for it to finish.
126	*/
127	SET(cp->c_flag, C_WALLOC);
128	simple_unlock(&hfs_chash_slock);
129	(void) tsleep((caddr_t)cp, PINOD, "hfs_chashget-1", 0);
130	goto loop;
131	}
132	if (ISSET(cp->c_flag, C_TRANSIT)) {
133	/*
134	* cnode is getting reclaimed wait for
135	* the operation to complete and return
136	* error
137	*/
138	SET(cp->c_flag, C_WTRANSIT);
139	simple_unlock(&hfs_chash_slock);
140	(void)tsleep((caddr_t)cp, PINOD, "hfs_chashget-2", 0);
141	goto loop;
142	}
55e303ae	143	if (cp->c_flag & (C_NOEXISTS \| C_DELETED))
9bccf70c A	144	continue;
	145
	146	/*
	147	* Try getting the desired vnode first. If
	148	* it isn't available then take a reference
	149	* on the other vnode.
	150	*/
	151	vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
	152	if (vp == NULLVP)
	153	vp = wantrsrc ? cp->c_vp : cp->c_rsrc_vp;
	154	if (vp == NULLVP)
	155	panic("hfs_chashget: orphaned cnode in hash");
	156
	157	simple_lock(&vp->v_interlock);
	158	simple_unlock(&hfs_chash_slock);
	159	if (vget(vp, LK_EXCLUSIVE \| LK_INTERLOCK, p))
	160	goto loop;
	161	else if (cp->c_flag & C_NOEXISTS) {
	162	/*
	163	* While we were blocked the cnode got deleted.
	164	*/
	165	vput(vp);
	166	goto loop;
	167	}
	168
	169	if (VNODE_IS_RSRC(vp))
	170	*rvpp = vp;
	171	else
	172	*vpp = vp;
	173	/*
	174	* Note that vget can block before aquiring the
	175	* cnode lock. So we need to check if the vnode
	176	* we wanted was created while we blocked.
	177	*/
	178	if (wantrsrc && *rvpp == NULL && cp->c_rsrc_vp) {
	179	error = vget(cp->c_rsrc_vp, 0, p);
55e303ae	180	vrele(vpp); / ref no longer needed */
9bccf70c A	181	*vpp = NULL;
	182	if (error)
	183	goto loop;
	184	*rvpp = cp->c_rsrc_vp;
	185
	186	} else if (!wantrsrc && *vpp == NULL && cp->c_vp) {
	187	error = vget(cp->c_vp, 0, p);
55e303ae	188	vrele(rvpp); / ref no longer needed */
9bccf70c A	189	*rvpp = NULL;
	190	if (error)
	191	goto loop;
	192	*vpp = cp->c_vp;
	193	}
	194	return (cp);
	195	}
	196	simple_unlock(&hfs_chash_slock);
	197	return (NULL);
	198	}
	199
	200
	201	/*
	202	* Insert a cnode into the hash table.
	203	*/
	204	__private_extern__
	205	void
	206	hfs_chashinsert(struct cnode *cp)
	207	{
55e303ae A	208	if (cp->c_fileid != 0) {
	209	simple_lock(&hfs_chash_slock);
	210	LIST_INSERT_HEAD(CNODEHASH(cp->c_dev, cp->c_fileid), cp, c_hash);
	211	simple_unlock(&hfs_chash_slock);
	212	}
9bccf70c A	213	}
	214
	215
	216	/*
	217	* Remove a cnode from the hash table.
	218	*/
	219	__private_extern__
	220	void
	221	hfs_chashremove(struct cnode *cp)
	222	{
	223	simple_lock(&hfs_chash_slock);
	224	LIST_REMOVE(cp, c_hash);
	225	cp->c_hash.le_next = NULL;
	226	cp->c_hash.le_prev = NULL;
	227	simple_unlock(&hfs_chash_slock);
	228	}
	229