vfs_cache.c revision 6990
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.9 1995/03/10 20:26:29 davidg Exp $ 37 */ 38 39#include <sys/param.h> 40#include <sys/systm.h> 41#include <sys/time.h> 42#include <sys/mount.h> 43#include <sys/vnode.h> 44#include <sys/namei.h> 45#include <sys/errno.h> 46#include <sys/malloc.h> 47 48/* 49 * Name caching works as follows: 50 * 51 * Names found by directory scans are retained in a cache 52 * for future reference. It is managed LRU, so frequently 53 * used names will hang around. Cache is indexed by hash value 54 * obtained from (vp, name) where vp refers to the directory 55 * containing name. 56 * 57 * If it is a "negative" entry, (that we know a name to >not< exist) 58 * we point out entry at our own "nchENOENT", to avoid too much special 59 * casing in the inner loops of lookup. 60 * 61 * For simplicity (and economy of storage), names longer than 62 * a maximum length of NCHNAMLEN are not cached; they occur 63 * infrequently in any case, and are almost never of interest. 64 * 65 * Upon reaching the last segment of a path, if the reference 66 * is for DELETE, or NOCACHE is set (rewrite), and the 67 * name is located in the cache, it will be dropped. 68 */ 69 70/* 71 * Structures associated with name cacheing. 72 */ 73LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */ 74TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */ 75u_long nchash; /* size of hash table - 1 */ 76struct nchstats nchstats; /* cache effectiveness statistics */ 77struct vnode nchENOENT; /* our own "novnode" */ 78int doingcache = 1; /* 1 => enable the cache */ 79 80#ifdef NCH_STATISTICS 81u_long nchnbr; 82#define NCHNBR(ncp) (ncp)->nc_nbr = ++nchnbr; 83#define NCHHIT(ncp) (ncp)->nc_hits++ 84#else 85#define NCHNBR(ncp) 86#define NCHHIT(ncp) 87#endif 88 89#define PURGE(ncp) { \ 90 LIST_REMOVE(ncp, nc_hash); \ 91 ncp->nc_hash.le_prev = 0; \ 92 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 93 TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); } 94 95#define TOUCH(ncp) { \ 96 if (ncp->nc_lru.tqe_next == 0) { } else { \ 97 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 98 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); \ 99 NCHNBR(ncp); } } 100 101/* 102 * Lookup an entry in the cache 103 * 104 * We don't do this if the segment name is long, simply so the cache 105 * can avoid holding long names (which would either waste space, or 106 * add greatly to the complexity). 107 * 108 * Lookup is called with dvp pointing to the directory to search, 109 * cnp pointing to the name of the entry being sought. 110 * If the lookup succeeds, the vnode is returned in *vpp, and a status 111 * of -1 is returned. 112 * If the lookup determines that the name does not exist (negative cacheing), 113 * a status of ENOENT is returned. 114 * If the lookup fails, a status of zero is returned. 115 */ 116 117int 118cache_lookup(dvp, vpp, cnp) 119 struct vnode *dvp; 120 struct vnode **vpp; 121 struct componentname *cnp; 122{ 123 register struct namecache *ncp,*nnp; 124 register struct nchashhead *ncpp; 125 126 if (!doingcache) { 127 cnp->cn_flags &= ~MAKEENTRY; 128 return (0); 129 } 130 131 if (cnp->cn_namelen > NCHNAMLEN) { 132 nchstats.ncs_long++; 133 cnp->cn_flags &= ~MAKEENTRY; 134 return (0); 135 } 136 137 ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) & nchash]; 138 for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) { 139 nnp = ncp->nc_hash.le_next; 140 /* If one of the vp's went stale, don't bother anymore. */ 141 if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) || 142 (ncp->nc_vpid != ncp->nc_vp->v_id)) { 143 PURGE(ncp); 144 continue; 145 } 146 /* Now that we know the vp's to be valid, is it ours ? */ 147 if (ncp->nc_dvp == dvp && 148 ncp->nc_nlen == cnp->cn_namelen && 149 !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 150 goto found; /* Fanatism considered bad. */ 151 } 152 nchstats.ncs_miss++; 153 return (0); 154 155 found: 156 NCHHIT(ncp); 157 158 /* We don't want to have an entry, so dump it */ 159 if ((cnp->cn_flags & MAKEENTRY) == 0) { 160 nchstats.ncs_badhits++; 161 PURGE(ncp); 162 return (0); 163 } 164 165 /* We found a "positive" match, return the vnode */ 166 if (ncp->nc_vp != &nchENOENT) { 167 nchstats.ncs_goodhits++; 168 TOUCH(ncp); 169 *vpp = ncp->nc_vp; 170 return (-1); 171 } 172 173 /* We found a negative match, and want to create it, so purge */ 174 if (cnp->cn_nameiop == CREATE) { 175 PURGE(ncp); 176 return (0); 177 } 178 179 /* The name does not exists */ 180 nchstats.ncs_neghits++; 181 TOUCH(ncp); 182 return (ENOENT); 183} 184 185/* 186 * Add an entry to the cache. 187 */ 188 189void 190cache_enter(dvp, vp, cnp) 191 struct vnode *dvp; 192 struct vnode *vp; 193 struct componentname *cnp; 194{ 195 register struct namecache *ncp; 196 register struct nchashhead *ncpp; 197 198 if (!doingcache) 199 return; 200 201 if (cnp->cn_namelen > NCHNAMLEN) { 202 printf("cache_enter: name too long"); 203 return; 204 } 205 206 if (numcache < numvnodes) { 207 /* Add one more entry */ 208 ncp = (struct namecache *) 209 malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 210 bzero((char *)ncp, sizeof *ncp); 211 numcache++; 212 } else if (ncp = nclruhead.tqh_first) { 213 /* reuse an old entry */ 214 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 215 if (ncp->nc_hash.le_prev != 0) { 216 LIST_REMOVE(ncp, nc_hash); 217 ncp->nc_hash.le_prev = 0; 218 } 219 } else { 220 /* give up */ 221 return; 222 } 223 224 /* If vp is NULL this is a "negative" cache entry */ 225 if (!vp) 226 vp = &nchENOENT; 227 228 /* fill in cache info */ 229 ncp->nc_vp = vp; 230 ncp->nc_vpid = vp->v_id; 231 ncp->nc_dvp = dvp; 232 ncp->nc_dvpid = dvp->v_id; 233 ncp->nc_nlen = cnp->cn_namelen; 234 bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 235 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 236 ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) & nchash]; 237 LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 238} 239 240/* 241 * Name cache initialization, from vfs_init() when we are booting 242 */ 243 244void 245nchinit() 246{ 247 248 TAILQ_INIT(&nclruhead); 249 nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash); 250 nchENOENT.v_id = 1; 251} 252 253/* 254 * Invalidate a all entries to particular vnode. 255 * 256 * We actually just increment the v_id, that will do it. The entries will 257 * be purged by lookup as they get found. 258 * If the v_id wraps around, we need to ditch the entire cache, to avoid 259 * confusion. 260 * No valid vnode will ever have (v_id == 0). 261 */ 262 263void 264cache_purge(vp) 265 struct vnode *vp; 266{ 267 struct nchashhead *ncpp; 268 269 vp->v_id = ++nextvnodeid; 270 if (nextvnodeid != 0) 271 return; 272 for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 273 while(ncpp->lh_first) 274 PURGE(ncpp->lh_first); 275 } 276 vp->v_id = ++nextvnodeid; 277} 278 279/* 280 * Flush all entries referencing a particular filesystem. 281 * 282 * Since we need to check it anyway, we will flush all the invalid 283 * entriess at the same time. 284 * 285 * If we purge anything, we scan the hash-bucket again. There is only 286 * a handful of entries, so it cheap and simple. 287 */ 288 289void 290cache_purgevfs(mp) 291 struct mount *mp; 292{ 293 struct nchashhead *ncpp; 294 struct namecache *ncp, *nxtcp; 295 296 /* Scan hash tables for applicable entries */ 297 for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 298 ncp = ncpp->lh_first; 299 while(ncp) { 300 if (ncp->nc_dvpid != ncp->nc_dvp->v_id || 301 ncp->nc_vpid != ncp->nc_vp->v_id || 302 ncp->nc_dvp->v_mount == mp) { 303 PURGE(ncp); 304 ncp = ncpp->lh_first; 305 } else { 306 ncp = ncp->nc_lru.tqe_next; 307 } 308 } 309 } 310} 311