1143561Sphk/*- 2143561Sphk * Copyright (c) 2005 Poul-Henning Kamp 3143561Sphk * All rights reserved. 4143561Sphk * 5143561Sphk * Redistribution and use in source and binary forms, with or without 6143561Sphk * modification, are permitted provided that the following conditions 7143561Sphk * are met: 8143561Sphk * 1. Redistributions of source code must retain the above copyright 9143561Sphk * notice, this list of conditions and the following disclaimer. 10143561Sphk * 2. Redistributions in binary form must reproduce the above copyright 11143561Sphk * notice, this list of conditions and the following disclaimer in the 12143561Sphk * documentation and/or other materials provided with the distribution. 13143561Sphk * 14143561Sphk * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15143561Sphk * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16143561Sphk * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17143561Sphk * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18143561Sphk * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19143561Sphk * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20143561Sphk * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21143561Sphk * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22143561Sphk * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23143561Sphk * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24143561Sphk * SUCH DAMAGE. 25143561Sphk * 26143561Sphk */ 27143561Sphk 28143561Sphk#include <sys/cdefs.h> 29143561Sphk__FBSDID("$FreeBSD$"); 30143561Sphk 31143561Sphk#include <sys/param.h> 32143561Sphk#include <sys/systm.h> 33143561Sphk#include <sys/kernel.h> 34143561Sphk#include <sys/malloc.h> 35143680Sphk#include <sys/mount.h> 36276424Smjg#include <sys/rwlock.h> 37143561Sphk#include <sys/vnode.h> 38143561Sphk 39151897Srwatsonstatic MALLOC_DEFINE(M_VFS_HASH, "vfs_hash", "VFS hash table"); 40143561Sphk 41143680Sphkstatic LIST_HEAD(vfs_hash_head, vnode) *vfs_hash_tbl; 42143680Sphkstatic LIST_HEAD(,vnode) vfs_hash_side; 43143561Sphkstatic u_long vfs_hash_mask; 44276424Smjgstatic struct rwlock vfs_hash_lock; 45143561Sphk 46143561Sphkstatic void 47143561Sphkvfs_hashinit(void *dummy __unused) 48143561Sphk{ 49143561Sphk 50143561Sphk vfs_hash_tbl = hashinit(desiredvnodes, M_VFS_HASH, &vfs_hash_mask); 51276424Smjg rw_init(&vfs_hash_lock, "vfs hash"); 52143680Sphk LIST_INIT(&vfs_hash_side); 53143561Sphk} 54143561Sphk 55143561Sphk/* Must be SI_ORDER_SECOND so desiredvnodes is available */ 56177253SrwatsonSYSINIT(vfs_hash, SI_SUB_VFS, SI_ORDER_SECOND, vfs_hashinit, NULL); 57143561Sphk 58245406Skibu_int 59245406Skibvfs_hash_index(struct vnode *vp) 60245406Skib{ 61245406Skib 62245406Skib return (vp->v_hash + vp->v_mount->mnt_hashseed); 63245406Skib} 64245406Skib 65143680Sphkstatic struct vfs_hash_head * 66245405Skibvfs_hash_bucket(const struct mount *mp, u_int hash) 67143680Sphk{ 68143680Sphk 69245405Skib return (&vfs_hash_tbl[(hash + mp->mnt_hashseed) & vfs_hash_mask]); 70143680Sphk} 71143680Sphk 72143561Sphkint 73299408Skibvfs_hash_get(const struct mount *mp, u_int hash, int flags, struct thread *td, 74299408Skib struct vnode **vpp, vfs_hash_cmp_t *fn, void *arg) 75143561Sphk{ 76143561Sphk struct vnode *vp; 77143561Sphk int error; 78143561Sphk 79143561Sphk while (1) { 80276424Smjg rw_rlock(&vfs_hash_lock); 81245405Skib LIST_FOREACH(vp, vfs_hash_bucket(mp, hash), v_hashlist) { 82143561Sphk if (vp->v_hash != hash) 83143561Sphk continue; 84143561Sphk if (vp->v_mount != mp) 85143561Sphk continue; 86143692Sphk if (fn != NULL && fn(vp, arg)) 87143692Sphk continue; 88285632Smjg vhold(vp); 89276424Smjg rw_runlock(&vfs_hash_lock); 90285632Smjg error = vget(vp, flags | LK_VNHELD, td); 91150011Stegge if (error == ENOENT && (flags & LK_NOWAIT) == 0) 92143561Sphk break; 93143561Sphk if (error) 94143561Sphk return (error); 95143561Sphk *vpp = vp; 96143561Sphk return (0); 97143561Sphk } 98143561Sphk if (vp == NULL) { 99276424Smjg rw_runlock(&vfs_hash_lock); 100143561Sphk *vpp = NULL; 101143561Sphk return (0); 102143561Sphk } 103143561Sphk } 104143561Sphk} 105143561Sphk 106143561Sphkvoid 107299412Skibvfs_hash_ref(const struct mount *mp, u_int hash, struct thread *td, 108299412Skib struct vnode **vpp, vfs_hash_cmp_t *fn, void *arg) 109299412Skib{ 110299412Skib struct vnode *vp; 111299412Skib 112299412Skib while (1) { 113299412Skib rw_rlock(&vfs_hash_lock); 114299412Skib LIST_FOREACH(vp, vfs_hash_bucket(mp, hash), v_hashlist) { 115299412Skib if (vp->v_hash != hash) 116299412Skib continue; 117299412Skib if (vp->v_mount != mp) 118299412Skib continue; 119299412Skib if (fn != NULL && fn(vp, arg)) 120299412Skib continue; 121299412Skib vhold(vp); 122299412Skib rw_runlock(&vfs_hash_lock); 123299412Skib vref(vp); 124299412Skib vdrop(vp); 125299412Skib *vpp = vp; 126299412Skib return; 127299412Skib } 128299412Skib if (vp == NULL) { 129299412Skib rw_runlock(&vfs_hash_lock); 130299412Skib *vpp = NULL; 131299412Skib return; 132299412Skib } 133299412Skib } 134299412Skib} 135299412Skib 136299412Skibvoid 137143561Sphkvfs_hash_remove(struct vnode *vp) 138143561Sphk{ 139143561Sphk 140276424Smjg rw_wlock(&vfs_hash_lock); 141143561Sphk LIST_REMOVE(vp, v_hashlist); 142276424Smjg rw_wunlock(&vfs_hash_lock); 143143561Sphk} 144143561Sphk 145143561Sphkint 146299408Skibvfs_hash_insert(struct vnode *vp, u_int hash, int flags, struct thread *td, 147299408Skib struct vnode **vpp, vfs_hash_cmp_t *fn, void *arg) 148143561Sphk{ 149143561Sphk struct vnode *vp2; 150143561Sphk int error; 151143561Sphk 152143619Sphk *vpp = NULL; 153143561Sphk while (1) { 154276424Smjg rw_wlock(&vfs_hash_lock); 155143561Sphk LIST_FOREACH(vp2, 156245405Skib vfs_hash_bucket(vp->v_mount, hash), v_hashlist) { 157143561Sphk if (vp2->v_hash != hash) 158143561Sphk continue; 159143561Sphk if (vp2->v_mount != vp->v_mount) 160143561Sphk continue; 161143789Sphk if (fn != NULL && fn(vp2, arg)) 162143692Sphk continue; 163285632Smjg vhold(vp2); 164276424Smjg rw_wunlock(&vfs_hash_lock); 165285632Smjg error = vget(vp2, flags | LK_VNHELD, td); 166150011Stegge if (error == ENOENT && (flags & LK_NOWAIT) == 0) 167143561Sphk break; 168276424Smjg rw_wlock(&vfs_hash_lock); 169143680Sphk LIST_INSERT_HEAD(&vfs_hash_side, vp, v_hashlist); 170276424Smjg rw_wunlock(&vfs_hash_lock); 171143663Sphk vput(vp); 172143663Sphk if (!error) 173143663Sphk *vpp = vp2; 174143663Sphk return (error); 175143561Sphk } 176143561Sphk if (vp2 == NULL) 177143561Sphk break; 178143561Sphk 179143561Sphk } 180143561Sphk vp->v_hash = hash; 181245405Skib LIST_INSERT_HEAD(vfs_hash_bucket(vp->v_mount, hash), vp, v_hashlist); 182276424Smjg rw_wunlock(&vfs_hash_lock); 183143561Sphk return (0); 184143561Sphk} 185143561Sphk 186143561Sphkvoid 187143561Sphkvfs_hash_rehash(struct vnode *vp, u_int hash) 188143561Sphk{ 189143561Sphk 190276424Smjg rw_wlock(&vfs_hash_lock); 191143561Sphk LIST_REMOVE(vp, v_hashlist); 192245405Skib LIST_INSERT_HEAD(vfs_hash_bucket(vp->v_mount, hash), vp, v_hashlist); 193143561Sphk vp->v_hash = hash; 194276424Smjg rw_wunlock(&vfs_hash_lock); 195143561Sphk} 196287497Smckusick 197287497Smckusickvoid 198287497Smckusickvfs_hash_changesize(int newmaxvnodes) 199287497Smckusick{ 200287497Smckusick struct vfs_hash_head *vfs_hash_newtbl, *vfs_hash_oldtbl; 201287497Smckusick u_long vfs_hash_newmask, vfs_hash_oldmask; 202287497Smckusick struct vnode *vp; 203287497Smckusick int i; 204287497Smckusick 205287497Smckusick vfs_hash_newtbl = hashinit(newmaxvnodes, M_VFS_HASH, 206287497Smckusick &vfs_hash_newmask); 207287497Smckusick /* If same hash table size, nothing to do */ 208287497Smckusick if (vfs_hash_mask == vfs_hash_newmask) { 209287497Smckusick free(vfs_hash_newtbl, M_VFS_HASH); 210287497Smckusick return; 211287497Smckusick } 212287497Smckusick /* 213287497Smckusick * Move everything from the old hash table to the new table. 214287497Smckusick * None of the vnodes in the table can be recycled because to 215287497Smckusick * do so, they have to be removed from the hash table. 216287497Smckusick */ 217287497Smckusick rw_wlock(&vfs_hash_lock); 218287497Smckusick vfs_hash_oldtbl = vfs_hash_tbl; 219287497Smckusick vfs_hash_oldmask = vfs_hash_mask; 220287497Smckusick vfs_hash_tbl = vfs_hash_newtbl; 221287497Smckusick vfs_hash_mask = vfs_hash_newmask; 222287497Smckusick for (i = 0; i <= vfs_hash_oldmask; i++) { 223287497Smckusick while ((vp = LIST_FIRST(&vfs_hash_oldtbl[i])) != NULL) { 224287497Smckusick LIST_REMOVE(vp, v_hashlist); 225287497Smckusick LIST_INSERT_HEAD( 226287497Smckusick vfs_hash_bucket(vp->v_mount, vp->v_hash), 227287497Smckusick vp, v_hashlist); 228287497Smckusick } 229287497Smckusick } 230287497Smckusick rw_wunlock(&vfs_hash_lock); 231287497Smckusick free(vfs_hash_oldtbl, M_VFS_HASH); 232287497Smckusick} 233