1 /* $OpenBSD: ufs_ihash.c,v 1.31 2024/12/03 14:41:45 claudio Exp $ */ 2 /* $NetBSD: ufs_ihash.c,v 1.3 1996/02/09 22:36:04 christos Exp $ */ 3 4 /* 5 * Copyright (c) 1982, 1986, 1989, 1991, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 * 32 * @(#)ufs_ihash.c 8.4 (Berkeley) 12/30/93 33 */ 34 35 #include <sys/param.h> 36 #include <sys/systm.h> 37 #include <sys/vnode.h> 38 #include <sys/malloc.h> 39 #include <sys/mount.h> 40 41 #include <ufs/ufs/quota.h> 42 #include <ufs/ufs/inode.h> 43 #include <ufs/ufs/ufs_extern.h> 44 #include <ufs/ufs/ufsmount.h> 45 #include <ufs/ext2fs/ext2fs_extern.h> 46 47 #include <crypto/siphash.h> 48 49 /* 50 * Structures associated with inode caching. 51 */ 52 LIST_HEAD(ihashhead, inode) *ihashtbl; 53 u_long ihash; /* size of hash table - 1 */ 54 SIPHASH_KEY ihashkey; 55 56 struct ihashhead *ufs_ihash(dev_t, ufsino_t); 57 #define INOHASH(device, inum) ufs_ihash((device), (inum)) 58 59 struct ihashhead * 60 ufs_ihash(dev_t dev, ufsino_t inum) 61 { 62 SIPHASH_CTX ctx; 63 64 SipHash24_Init(&ctx, &ihashkey); 65 SipHash24_Update(&ctx, &dev, sizeof(dev)); 66 SipHash24_Update(&ctx, &inum, sizeof(inum)); 67 68 return (&ihashtbl[SipHash24_End(&ctx) & ihash]); 69 } 70 71 /* 72 * Initialize inode hash table. 73 */ 74 void 75 ufs_ihashinit(void) 76 { 77 ihashtbl = hashinit(initialvnodes, M_UFSMNT, M_WAITOK, &ihash); 78 arc4random_buf(&ihashkey, sizeof(ihashkey)); 79 } 80 81 /* 82 * Use the device/inum pair to find the incore inode, and return a pointer 83 * to it. If it is in core, but locked, wait for it. 84 */ 85 struct vnode * 86 ufs_ihashget(dev_t dev, ufsino_t inum) 87 { 88 struct ihashhead *ipp; 89 struct inode *ip; 90 struct vnode *vp; 91 loop: 92 /* XXXLOCKING lock hash list */ 93 ipp = INOHASH(dev, inum); 94 LIST_FOREACH(ip, ipp, i_hash) { 95 if (inum == ip->i_number && dev == ip->i_dev) { 96 vp = ITOV(ip); 97 /* XXXLOCKING unlock hash list? */ 98 if (vget(vp, LK_EXCLUSIVE)) 99 goto loop; 100 /* 101 * Check if the inode is valid. 102 * The condition has been adapted from ufs_inactive(). 103 * 104 * This is needed in case our vget above grabbed a vnode 105 * while ufs_inactive was reclaiming it. 106 * 107 * XXX this is a workaround and kind of a gross hack. 108 * realistically this should get fixed something like 109 * the previously committed vdoom() or this should be 110 * dealt with so this can't happen. 111 */ 112 if (VTOI(vp) != ip || 113 (( 114 #ifdef EXT2FS 115 /* 116 * XXX DIP does not cover ext2fs so hack 117 * around this for now since this is using 118 * ufs_ihashget as well. 119 */ 120 IS_EXT2_VNODE(vp) ? ip->i_e2fs_nlink <= 0 : 121 #endif 122 DIP(ip, nlink) <= 0) && 123 (vp->v_mount->mnt_flag & MNT_RDONLY) == 0)) { 124 /* 125 * This should recycle the inode immediately, 126 * unless there are other threads that 127 * try to access it. 128 * Pause to give the threads a chance to finish 129 * with the inode. 130 */ 131 vput(vp); 132 yield(); 133 goto loop; 134 } 135 136 return (vp); 137 } 138 } 139 /* XXXLOCKING unlock hash list? */ 140 return (NULL); 141 } 142 143 /* 144 * Insert the inode into the hash table, and return it locked. 145 */ 146 int 147 ufs_ihashins(struct inode *ip) 148 { 149 struct inode *curip; 150 struct ihashhead *ipp; 151 dev_t dev = ip->i_dev; 152 ufsino_t inum = ip->i_number; 153 154 /* lock the inode, then put it on the appropriate hash list */ 155 VOP_LOCK(ITOV(ip), LK_EXCLUSIVE); 156 157 /* XXXLOCKING lock hash list */ 158 159 ipp = INOHASH(dev, inum); 160 LIST_FOREACH(curip, ipp, i_hash) { 161 if (inum == curip->i_number && dev == curip->i_dev) { 162 /* XXXLOCKING unlock hash list? */ 163 VOP_UNLOCK(ITOV(ip)); 164 return (EEXIST); 165 } 166 } 167 168 SET(ip->i_flag, IN_HASHED); 169 LIST_INSERT_HEAD(ipp, ip, i_hash); 170 /* XXXLOCKING unlock hash list? */ 171 172 return (0); 173 } 174 175 /* 176 * Remove the inode from the hash table. 177 */ 178 void 179 ufs_ihashrem(struct inode *ip) 180 { 181 /* XXXLOCKING lock hash list */ 182 183 if (ip->i_hash.le_prev == NULL) 184 return; 185 if (ISSET(ip->i_flag, IN_HASHED)) { 186 LIST_REMOVE(ip, i_hash); 187 CLR(ip->i_flag, IN_HASHED); 188 } 189 #ifdef DIAGNOSTIC 190 ip->i_hash.le_next = NULL; 191 ip->i_hash.le_prev = NULL; 192 #endif 193 /* XXXLOCKING unlock hash list? */ 194 } 195