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