1 /* 2 * Copyright (c) 1982, 1986, 1989, 1991, 1993, 1995 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. Neither the name of the University nor the names of its contributors 14 * may be used to endorse or promote products derived from this software 15 * without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 * 29 * @(#)ufs_ihash.c 8.7 (Berkeley) 5/17/95 30 * $FreeBSD: src/sys/ufs/ufs/ufs_ihash.c,v 1.20 1999/08/28 00:52:29 peter Exp $ 31 */ 32 33 #include <sys/param.h> 34 #include <sys/systm.h> 35 #include <sys/kernel.h> 36 #include <sys/lock.h> 37 #include <sys/vnode.h> 38 #include <sys/malloc.h> 39 #include <sys/proc.h> 40 #include <sys/mount.h> 41 42 #include "quota.h" 43 #include "inode.h" 44 #include "ufs_extern.h" 45 #include "ufsmount.h" 46 47 static MALLOC_DEFINE(M_UFSIHASH, "UFS ihash", "UFS Inode hash tables"); 48 49 #define INOHASH(ump, inum) \ 50 (&ump->um_ihashtbl[inum & ump->um_ihash]) 51 52 /* 53 * Initialize inode hash table. 54 */ 55 void 56 ufs_ihashinit(struct ufsmount *ump) 57 { 58 u_long target = desiredvnodes / 4 + 1; 59 60 ump->um_ihash = 16; 61 while (ump->um_ihash < target) 62 ump->um_ihash <<= 1; 63 ump->um_ihashtbl = kmalloc(sizeof(void *) * ump->um_ihash, M_UFSIHASH, 64 M_WAITOK|M_ZERO); 65 --ump->um_ihash; 66 } 67 68 void 69 ufs_ihashuninit(struct ufsmount *ump) 70 { 71 if (ump->um_ihashtbl) { 72 kfree(ump->um_ihashtbl, M_UFSIHASH); 73 ump->um_ihashtbl = NULL; 74 } 75 } 76 77 /* 78 * Use the device/inum pair to find the incore inode, and return a pointer 79 * to it. If it is in core, return it, even if it is locked. 80 */ 81 struct vnode * 82 ufs_ihashlookup(struct ufsmount *ump, cdev_t dev, ino_t inum) 83 { 84 struct inode *ip = NULL; 85 86 for (ip = *INOHASH(ump, inum); ip; ip = ip->i_next) { 87 if (inum == ip->i_number && dev == ip->i_dev) 88 break; 89 } 90 if (ip) 91 return (ITOV(ip)); 92 return (NULLVP); 93 } 94 95 /* 96 * Use the device/inum pair to find the incore inode, and return a pointer 97 * to it. If it is in core, but locked, wait for it. 98 * 99 * This subroutine may block. 100 */ 101 struct vnode * 102 ufs_ihashget(struct ufsmount *ump, cdev_t dev, ino_t inum) 103 { 104 struct inode *ip; 105 struct vnode *vp; 106 107 loop: 108 for (ip = *INOHASH(ump, inum); ip; ip = ip->i_next) { 109 if (inum != ip->i_number || dev != ip->i_dev) 110 continue; 111 vp = ITOV(ip); 112 if (vget(vp, LK_EXCLUSIVE)) 113 goto loop; 114 /* 115 * We must check to see if the inode has been ripped 116 * out from under us after blocking. 117 */ 118 for (ip = *INOHASH(ump, inum); ip; ip = ip->i_next) { 119 if (inum == ip->i_number && dev == ip->i_dev) 120 break; 121 } 122 if (ip == NULL || ITOV(ip) != vp) { 123 vput(vp); 124 goto loop; 125 } 126 return (vp); 127 } 128 return (NULL); 129 } 130 131 /* 132 * Check to see if an inode is in the hash table. This is used to interlock 133 * file free operations to ensure that the vnode is not reused due to a 134 * reallocate of its inode number before we have had a chance to recycle it. 135 */ 136 int 137 ufs_ihashcheck(struct ufsmount *ump, cdev_t dev, ino_t inum) 138 { 139 struct inode *ip; 140 141 for (ip = *INOHASH(ump, inum); ip; ip = ip->i_next) { 142 if (inum == ip->i_number && dev == ip->i_dev) 143 break; 144 } 145 return(ip ? 1 : 0); 146 } 147 148 /* 149 * Insert the inode into the hash table, and return it locked. 150 */ 151 int 152 ufs_ihashins(struct ufsmount *ump, struct inode *ip) 153 { 154 struct inode **ipp; 155 struct inode *iq; 156 157 KKASSERT((ip->i_flag & IN_HASHED) == 0); 158 ipp = INOHASH(ump, ip->i_number); 159 while ((iq = *ipp) != NULL) { 160 if (ip->i_dev == iq->i_dev && ip->i_number == iq->i_number) { 161 return(EBUSY); 162 } 163 ipp = &iq->i_next; 164 } 165 ip->i_next = NULL; 166 *ipp = ip; 167 ip->i_flag |= IN_HASHED; 168 return(0); 169 } 170 171 /* 172 * Remove the inode from the hash table. 173 */ 174 void 175 ufs_ihashrem(struct ufsmount *ump, struct inode *ip) 176 { 177 struct inode **ipp; 178 struct inode *iq; 179 180 if (ip->i_flag & IN_HASHED) { 181 ipp = INOHASH(ump, ip->i_number); 182 while ((iq = *ipp) != NULL) { 183 if (ip == iq) 184 break; 185 ipp = &iq->i_next; 186 } 187 KKASSERT(ip == iq); 188 *ipp = ip->i_next; 189 ip->i_next = NULL; 190 ip->i_flag &= ~IN_HASHED; 191 } 192 } 193 194