vfs_cache.c revision 12968
1/* 2 * Copyright (c) 1989, 1993 3 * The Regents of the University of California. All rights reserved. 4 * Copyright (c) 1995 5 * Poul-Henning Kamp. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by the University of 18 * California, Berkeley and its contributors. 19 * 4. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 * 35 * @(#)vfs_cache.c 8.3 (Berkeley) 8/22/94 36 * $Id: vfs_cache.c,v 1.18 1995/12/14 09:52:47 phk Exp $ 37 */ 38 39#include <sys/param.h> 40#include <sys/systm.h> 41#include <sys/kernel.h> 42#include <sys/sysctl.h> 43#include <sys/time.h> 44#include <sys/mount.h> 45#include <sys/vnode.h> 46#include <sys/namei.h> 47#include <sys/errno.h> 48#include <sys/malloc.h> 49 50/* 51 * Name caching works as follows: 52 * 53 * Names found by directory scans are retained in a cache 54 * for future reference. It is managed LRU, so frequently 55 * used names will hang around. Cache is indexed by hash value 56 * obtained from (vp, name) where vp refers to the directory 57 * containing name. 58 * 59 * If it is a "negative" entry, (that we know a name to >not< exist) 60 * we point out entry at our own "nchENOENT", to avoid too much special 61 * casing in the inner loops of lookup. 62 * 63 * For simplicity (and economy of storage), names longer than 64 * a maximum length of NCHNAMLEN are not cached; they occur 65 * infrequently in any case, and are almost never of interest. 66 * 67 * Upon reaching the last segment of a path, if the reference 68 * is for DELETE, or NOCACHE is set (rewrite), and the 69 * name is located in the cache, it will be dropped. 70 */ 71 72/* 73 * Structures associated with name cacheing. 74 */ 75static LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */ 76static TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */ 77static u_long nchash; /* size of hash table */ 78struct nchstats nchstats; /* cache effectiveness statistics */ 79static struct vnode nchENOENT; /* our own "novnode" */ 80static int doingcache = 1; /* 1 => enable the cache */ 81SYSCTL_INT(_debug, OID_AUTO, vfscache, CTLFLAG_RW, &doingcache, 0, ""); 82static u_long numcache; 83u_long numvnodes; 84 85#ifdef NCH_STATISTICS 86u_long nchnbr; 87#define NCHNBR(ncp) (ncp)->nc_nbr = ++nchnbr; 88#define NCHHIT(ncp) (ncp)->nc_hits++ 89#else 90#define NCHNBR(ncp) 91#define NCHHIT(ncp) 92#endif 93 94#define PURGE(ncp) { \ 95 LIST_REMOVE(ncp, nc_hash); \ 96 ncp->nc_hash.le_prev = 0; \ 97 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 98 TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); } 99 100#define TOUCH(ncp) { \ 101 if (ncp->nc_lru.tqe_next == 0) { } else { \ 102 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 103 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); \ 104 NCHNBR(ncp); } } 105 106/* 107 * Lookup an entry in the cache 108 * 109 * We don't do this if the segment name is long, simply so the cache 110 * can avoid holding long names (which would either waste space, or 111 * add greatly to the complexity). 112 * 113 * Lookup is called with dvp pointing to the directory to search, 114 * cnp pointing to the name of the entry being sought. 115 * If the lookup succeeds, the vnode is returned in *vpp, and a status 116 * of -1 is returned. 117 * If the lookup determines that the name does not exist (negative cacheing), 118 * a status of ENOENT is returned. 119 * If the lookup fails, a status of zero is returned. 120 */ 121 122int 123cache_lookup(dvp, vpp, cnp) 124 struct vnode *dvp; 125 struct vnode **vpp; 126 struct componentname *cnp; 127{ 128 register struct namecache *ncp,*nnp; 129 register struct nchashhead *ncpp; 130 131 if (!doingcache) { 132 cnp->cn_flags &= ~MAKEENTRY; 133 return (0); 134 } 135 136 if (cnp->cn_namelen > NCHNAMLEN) { 137 nchstats.ncs_long++; 138 cnp->cn_flags &= ~MAKEENTRY; 139 return (0); 140 } 141 142 ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) % nchash]; 143 for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) { 144 nnp = ncp->nc_hash.le_next; 145 /* If one of the vp's went stale, don't bother anymore. */ 146 if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) || 147 (ncp->nc_vpid != ncp->nc_vp->v_id)) { 148 nchstats.ncs_falsehits++; 149 PURGE(ncp); 150 continue; 151 } 152 /* Now that we know the vp's to be valid, is it ours ? */ 153 if (ncp->nc_dvp == dvp && 154 ncp->nc_nlen == cnp->cn_namelen && 155 !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 156 goto found; /* Fanatism considered bad. */ 157 } 158 nchstats.ncs_miss++; 159 return (0); 160 161 found: 162 NCHHIT(ncp); 163 164 /* We don't want to have an entry, so dump it */ 165 if ((cnp->cn_flags & MAKEENTRY) == 0) { 166 nchstats.ncs_badhits++; 167 PURGE(ncp); 168 return (0); 169 } 170 171 /* We found a "positive" match, return the vnode */ 172 if (ncp->nc_vp != &nchENOENT) { 173 nchstats.ncs_goodhits++; 174 TOUCH(ncp); 175 *vpp = ncp->nc_vp; 176 return (-1); 177 } 178 179 /* We found a negative match, and want to create it, so purge */ 180 if (cnp->cn_nameiop == CREATE) { 181 nchstats.ncs_badhits++; 182 PURGE(ncp); 183 return (0); 184 } 185 186 /* The name does not exists */ 187 nchstats.ncs_neghits++; 188 TOUCH(ncp); 189 return (ENOENT); 190} 191 192/* 193 * Add an entry to the cache. 194 */ 195 196void 197cache_enter(dvp, vp, cnp) 198 struct vnode *dvp; 199 struct vnode *vp; 200 struct componentname *cnp; 201{ 202 register struct namecache *ncp; 203 register struct nchashhead *ncpp; 204 205 if (!doingcache) 206 return; 207 208 if (cnp->cn_namelen > NCHNAMLEN) { 209 printf("cache_enter: name too long"); 210 return; 211 } 212 213 if (numcache < numvnodes) { 214 /* Add one more entry */ 215 ncp = (struct namecache *) 216 malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 217 bzero((char *)ncp, sizeof *ncp); 218 numcache++; 219 } else if (ncp = nclruhead.tqh_first) { 220 /* reuse an old entry */ 221 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 222 if (ncp->nc_hash.le_prev != 0) { 223 LIST_REMOVE(ncp, nc_hash); 224 ncp->nc_hash.le_prev = 0; 225 } 226 } else { 227 /* give up */ 228 return; 229 } 230 231 /* If vp is NULL this is a "negative" cache entry */ 232 if (!vp) 233 vp = &nchENOENT; 234 235 /* fill in cache info */ 236 ncp->nc_vp = vp; 237 ncp->nc_vpid = vp->v_id; 238 ncp->nc_dvp = dvp; 239 ncp->nc_dvpid = dvp->v_id; 240 ncp->nc_nlen = cnp->cn_namelen; 241 bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 242 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 243 ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) % nchash]; 244 LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 245} 246 247/* 248 * Name cache initialization, from vfs_init() when we are booting 249 */ 250 251void 252nchinit() 253{ 254 255 TAILQ_INIT(&nclruhead); 256 nchashtbl = phashinit(desiredvnodes, M_CACHE, &nchash); 257 cache_purge(&nchENOENT); /* Initialize v_id */ 258} 259 260/* 261 * Invalidate all entries to a particular vnode. 262 * 263 * We actually just increment the v_id, that will do it. The stale entries 264 * will be purged by lookup as they get found. 265 * If the v_id wraps around, we need to ditch the entire cache, to avoid 266 * confusion. 267 * No valid vnode will ever have (v_id == 0). 268 */ 269 270void 271cache_purge(vp) 272 struct vnode *vp; 273{ 274 struct nchashhead *ncpp; 275 static u_long nextvnodeid; 276 277 vp->v_id = ++nextvnodeid; 278 if (nextvnodeid != 0) 279 return; 280 for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) { 281 while(ncpp->lh_first) 282 PURGE(ncpp->lh_first); 283 } 284 nchENOENT.v_id = ++nextvnodeid; 285 vp->v_id = ++nextvnodeid; 286} 287 288/* 289 * Flush all entries referencing a particular filesystem. 290 * 291 * Since we need to check it anyway, we will flush all the invalid 292 * entries at the same time. 293 * 294 * If we purge anything, we scan the hash-bucket again. There is only 295 * a handful of entries, so it cheap and simple. 296 */ 297 298void 299cache_purgevfs(mp) 300 struct mount *mp; 301{ 302 struct nchashhead *ncpp; 303 struct namecache *ncp; 304 305 /* Scan hash tables for applicable entries */ 306 for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) { 307 ncp = ncpp->lh_first; 308 while(ncp) { 309 if (ncp->nc_dvpid != ncp->nc_dvp->v_id || 310 ncp->nc_vpid != ncp->nc_vp->v_id || 311 ncp->nc_dvp->v_mount == mp) { 312 PURGE(ncp); 313 ncp = ncpp->lh_first; 314 } else { 315 ncp = ncp->nc_hash.le_next; 316 } 317 } 318 } 319} 320