vfs_cache.c revision 6990
1227825Stheraven/* 2227825Stheraven * Copyright (c) 1989, 1993 3227825Stheraven * The Regents of the University of California. All rights reserved. 4227825Stheraven * Copyright (c) 1995 5227825Stheraven * Poul-Henning Kamp. All rights reserved. 6227825Stheraven * 7227825Stheraven * Redistribution and use in source and binary forms, with or without 8227825Stheraven * modification, are permitted provided that the following conditions 9227825Stheraven * are met: 10227825Stheraven * 1. Redistributions of source code must retain the above copyright 11227825Stheraven * notice, this list of conditions and the following disclaimer. 12227825Stheraven * 2. Redistributions in binary form must reproduce the above copyright 13227825Stheraven * notice, this list of conditions and the following disclaimer in the 14227825Stheraven * documentation and/or other materials provided with the distribution. 15227825Stheraven * 3. All advertising materials mentioning features or use of this software 16227825Stheraven * must display the following acknowledgement: 17227825Stheraven * This product includes software developed by the University of 18227825Stheraven * California, Berkeley and its contributors. 19227825Stheraven * 4. Neither the name of the University nor the names of its contributors 20227825Stheraven * may be used to endorse or promote products derived from this software 21227825Stheraven * without specific prior written permission. 22227825Stheraven * 23227825Stheraven * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24227825Stheraven * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25227825Stheraven * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26227825Stheraven * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27227825Stheraven * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28227825Stheraven * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29227825Stheraven * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30227825Stheraven * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31227825Stheraven * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32227825Stheraven * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33227825Stheraven * SUCH DAMAGE. 34227825Stheraven * 35227825Stheraven * @(#)vfs_cache.c 8.3 (Berkeley) 8/22/94 36227825Stheraven * $Id: vfs_cache.c,v 1.9 1995/03/10 20:26:29 davidg Exp $ 37227825Stheraven */ 38227825Stheraven 39227825Stheraven#include <sys/param.h> 40227825Stheraven#include <sys/systm.h> 41227825Stheraven#include <sys/time.h> 42227825Stheraven#include <sys/mount.h> 43227825Stheraven#include <sys/vnode.h> 44227825Stheraven#include <sys/namei.h> 45227825Stheraven#include <sys/errno.h> 46227825Stheraven#include <sys/malloc.h> 47227825Stheraven 48227825Stheraven/* 49227825Stheraven * Name caching works as follows: 50227825Stheraven * 51227825Stheraven * Names found by directory scans are retained in a cache 52227825Stheraven * for future reference. It is managed LRU, so frequently 53227825Stheraven * used names will hang around. Cache is indexed by hash value 54227825Stheraven * obtained from (vp, name) where vp refers to the directory 55227825Stheraven * containing name. 56227825Stheraven * 57227825Stheraven * If it is a "negative" entry, (that we know a name to >not< exist) 58227825Stheraven * we point out entry at our own "nchENOENT", to avoid too much special 59227825Stheraven * casing in the inner loops of lookup. 60227825Stheraven * 61227825Stheraven * For simplicity (and economy of storage), names longer than 62227825Stheraven * a maximum length of NCHNAMLEN are not cached; they occur 63227825Stheraven * infrequently in any case, and are almost never of interest. 64227825Stheraven * 65227825Stheraven * Upon reaching the last segment of a path, if the reference 66227825Stheraven * is for DELETE, or NOCACHE is set (rewrite), and the 67227825Stheraven * name is located in the cache, it will be dropped. 68227825Stheraven */ 69227825Stheraven 70227825Stheraven/* 71227825Stheraven * Structures associated with name cacheing. 72227825Stheraven */ 73227825StheravenLIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */ 74227825StheravenTAILQ_HEAD(, namecache) nclruhead; /* LRU chain */ 75227825Stheravenu_long nchash; /* size of hash table - 1 */ 76227825Stheravenstruct nchstats nchstats; /* cache effectiveness statistics */ 77227825Stheravenstruct vnode nchENOENT; /* our own "novnode" */ 78227825Stheravenint doingcache = 1; /* 1 => enable the cache */ 79227825Stheraven 80227825Stheraven#ifdef NCH_STATISTICS 81227825Stheravenu_long nchnbr; 82227825Stheraven#define NCHNBR(ncp) (ncp)->nc_nbr = ++nchnbr; 83227825Stheraven#define NCHHIT(ncp) (ncp)->nc_hits++ 84227825Stheraven#else 85227825Stheraven#define NCHNBR(ncp) 86227825Stheraven#define NCHHIT(ncp) 87227825Stheraven#endif 88227825Stheraven 89227825Stheraven#define PURGE(ncp) { \ 90227825Stheraven LIST_REMOVE(ncp, nc_hash); \ 91227825Stheraven ncp->nc_hash.le_prev = 0; \ 92227825Stheraven TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 93227825Stheraven TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); } 94227825Stheraven 95227825Stheraven#define TOUCH(ncp) { \ 96227825Stheraven if (ncp->nc_lru.tqe_next == 0) { } else { \ 97227825Stheraven TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 98227825Stheraven TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); \ 99227825Stheraven NCHNBR(ncp); } } 100227825Stheraven 101227825Stheraven/* 102227825Stheraven * Lookup an entry in the cache 103227825Stheraven * 104227825Stheraven * We don't do this if the segment name is long, simply so the cache 105227825Stheraven * can avoid holding long names (which would either waste space, or 106227825Stheraven * add greatly to the complexity). 107227825Stheraven * 108227825Stheraven * Lookup is called with dvp pointing to the directory to search, 109227825Stheraven * cnp pointing to the name of the entry being sought. 110227825Stheraven * If the lookup succeeds, the vnode is returned in *vpp, and a status 111227825Stheraven * of -1 is returned. 112227825Stheraven * If the lookup determines that the name does not exist (negative cacheing), 113227825Stheraven * a status of ENOENT is returned. 114227825Stheraven * If the lookup fails, a status of zero is returned. 115227825Stheraven */ 116227825Stheraven 117227825Stheravenint 118227825Stheravencache_lookup(dvp, vpp, cnp) 119227825Stheraven struct vnode *dvp; 120227825Stheraven struct vnode **vpp; 121227825Stheraven struct componentname *cnp; 122227825Stheraven{ 123227825Stheraven register struct namecache *ncp,*nnp; 124227825Stheraven register struct nchashhead *ncpp; 125227825Stheraven 126227825Stheraven if (!doingcache) { 127227825Stheraven cnp->cn_flags &= ~MAKEENTRY; 128227825Stheraven return (0); 129227825Stheraven } 130227825Stheraven 131227825Stheraven if (cnp->cn_namelen > NCHNAMLEN) { 132227825Stheraven nchstats.ncs_long++; 133227825Stheraven cnp->cn_flags &= ~MAKEENTRY; 134227825Stheraven return (0); 135227825Stheraven } 136227825Stheraven 137227825Stheraven ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) & nchash]; 138227825Stheraven for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) { 139227825Stheraven nnp = ncp->nc_hash.le_next; 140227825Stheraven /* If one of the vp's went stale, don't bother anymore. */ 141227825Stheraven if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) || 142227825Stheraven (ncp->nc_vpid != ncp->nc_vp->v_id)) { 143227825Stheraven PURGE(ncp); 144227825Stheraven continue; 145227825Stheraven } 146227825Stheraven /* Now that we know the vp's to be valid, is it ours ? */ 147227825Stheraven if (ncp->nc_dvp == dvp && 148227825Stheraven ncp->nc_nlen == cnp->cn_namelen && 149227825Stheraven !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 150227825Stheraven goto found; /* Fanatism considered bad. */ 151227825Stheraven } 152227825Stheraven nchstats.ncs_miss++; 153227825Stheraven return (0); 154227825Stheraven 155227825Stheraven found: 156227825Stheraven NCHHIT(ncp); 157227825Stheraven 158227825Stheraven /* We don't want to have an entry, so dump it */ 159227825Stheraven if ((cnp->cn_flags & MAKEENTRY) == 0) { 160227825Stheraven nchstats.ncs_badhits++; 161227825Stheraven PURGE(ncp); 162227825Stheraven return (0); 163227825Stheraven } 164227825Stheraven 165227825Stheraven /* We found a "positive" match, return the vnode */ 166227825Stheraven if (ncp->nc_vp != &nchENOENT) { 167227825Stheraven nchstats.ncs_goodhits++; 168227825Stheraven TOUCH(ncp); 169227825Stheraven *vpp = ncp->nc_vp; 170227825Stheraven return (-1); 171227825Stheraven } 172227825Stheraven 173227825Stheraven /* We found a negative match, and want to create it, so purge */ 174227825Stheraven if (cnp->cn_nameiop == CREATE) { 175227825Stheraven PURGE(ncp); 176227825Stheraven return (0); 177227825Stheraven } 178227825Stheraven 179227825Stheraven /* The name does not exists */ 180227825Stheraven nchstats.ncs_neghits++; 181227825Stheraven TOUCH(ncp); 182227825Stheraven return (ENOENT); 183227825Stheraven} 184227825Stheraven 185227825Stheraven/* 186227825Stheraven * Add an entry to the cache. 187227825Stheraven */ 188227825Stheraven 189227825Stheravenvoid 190227825Stheravencache_enter(dvp, vp, cnp) 191227825Stheraven struct vnode *dvp; 192227825Stheraven struct vnode *vp; 193227825Stheraven struct componentname *cnp; 194227825Stheraven{ 195227825Stheraven register struct namecache *ncp; 196227825Stheraven register struct nchashhead *ncpp; 197227825Stheraven 198227825Stheraven if (!doingcache) 199227825Stheraven return; 200227825Stheraven 201227825Stheraven if (cnp->cn_namelen > NCHNAMLEN) { 202227825Stheraven printf("cache_enter: name too long"); 203227825Stheraven return; 204227825Stheraven } 205227825Stheraven 206227825Stheraven if (numcache < numvnodes) { 207227825Stheraven /* Add one more entry */ 208227825Stheraven ncp = (struct namecache *) 209227825Stheraven malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 210227825Stheraven bzero((char *)ncp, sizeof *ncp); 211227825Stheraven numcache++; 212227825Stheraven } else if (ncp = nclruhead.tqh_first) { 213227825Stheraven /* reuse an old entry */ 214227825Stheraven TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 215227825Stheraven if (ncp->nc_hash.le_prev != 0) { 216227825Stheraven LIST_REMOVE(ncp, nc_hash); 217227825Stheraven ncp->nc_hash.le_prev = 0; 218227825Stheraven } 219227825Stheraven } else { 220227825Stheraven /* give up */ 221227825Stheraven return; 222227825Stheraven } 223227825Stheraven 224227825Stheraven /* If vp is NULL this is a "negative" cache entry */ 225227825Stheraven if (!vp) 226227825Stheraven vp = &nchENOENT; 227227825Stheraven 228227825Stheraven /* fill in cache info */ 229227825Stheraven ncp->nc_vp = vp; 230227825Stheraven ncp->nc_vpid = vp->v_id; 231227825Stheraven ncp->nc_dvp = dvp; 232227825Stheraven ncp->nc_dvpid = dvp->v_id; 233227825Stheraven ncp->nc_nlen = cnp->cn_namelen; 234227825Stheraven bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 235227825Stheraven TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 236227825Stheraven ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) & nchash]; 237227825Stheraven LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 238227825Stheraven} 239227825Stheraven 240227825Stheraven/* 241227825Stheraven * Name cache initialization, from vfs_init() when we are booting 242227825Stheraven */ 243227825Stheraven 244227825Stheravenvoid 245227825Stheravennchinit() 246227825Stheraven{ 247227825Stheraven 248227825Stheraven TAILQ_INIT(&nclruhead); 249227825Stheraven nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash); 250227825Stheraven nchENOENT.v_id = 1; 251227825Stheraven} 252227825Stheraven 253227825Stheraven/* 254227825Stheraven * Invalidate a all entries to particular vnode. 255227825Stheraven * 256227825Stheraven * We actually just increment the v_id, that will do it. The entries will 257227825Stheraven * be purged by lookup as they get found. 258227825Stheraven * If the v_id wraps around, we need to ditch the entire cache, to avoid 259227825Stheraven * confusion. 260227825Stheraven * No valid vnode will ever have (v_id == 0). 261227825Stheraven */ 262227825Stheraven 263227825Stheravenvoid 264227825Stheravencache_purge(vp) 265227825Stheraven struct vnode *vp; 266227825Stheraven{ 267227825Stheraven struct nchashhead *ncpp; 268227825Stheraven 269227825Stheraven vp->v_id = ++nextvnodeid; 270227825Stheraven if (nextvnodeid != 0) 271227825Stheraven return; 272227825Stheraven for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 273227825Stheraven while(ncpp->lh_first) 274227825Stheraven PURGE(ncpp->lh_first); 275227825Stheraven } 276227825Stheraven vp->v_id = ++nextvnodeid; 277227825Stheraven} 278227825Stheraven 279227825Stheraven/* 280227825Stheraven * Flush all entries referencing a particular filesystem. 281227825Stheraven * 282227825Stheraven * Since we need to check it anyway, we will flush all the invalid 283227825Stheraven * entriess at the same time. 284227825Stheraven * 285227825Stheraven * If we purge anything, we scan the hash-bucket again. There is only 286227825Stheraven * a handful of entries, so it cheap and simple. 287227825Stheraven */ 288227825Stheraven 289227825Stheravenvoid 290227825Stheravencache_purgevfs(mp) 291227825Stheraven struct mount *mp; 292227825Stheraven{ 293227825Stheraven struct nchashhead *ncpp; 294227825Stheraven struct namecache *ncp, *nxtcp; 295227825Stheraven 296227825Stheraven /* Scan hash tables for applicable entries */ 297227825Stheraven for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 298227825Stheraven ncp = ncpp->lh_first; 299227825Stheraven while(ncp) { 300227825Stheraven if (ncp->nc_dvpid != ncp->nc_dvp->v_id || 301227825Stheraven ncp->nc_vpid != ncp->nc_vp->v_id || 302227825Stheraven ncp->nc_dvp->v_mount == mp) { 303227825Stheraven PURGE(ncp); 304227825Stheraven ncp = ncpp->lh_first; 305227825Stheraven } else { 306227825Stheraven ncp = ncp->nc_lru.tqe_next; 307227825Stheraven } 308227825Stheraven } 309227825Stheraven } 310227825Stheraven} 311227825Stheraven