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