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.13 1995/04/04 02:01:13 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 */ 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 80 #ifdef NCH_STATISTICS 81 u_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 117 int 118 cache_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 nchstats.ncs_falsehits++; 144 PURGE(ncp); 145 continue; 146 } 147 /* Now that we know the vp's to be valid, is it ours ? */ 148 if (ncp->nc_dvp == dvp && 149 ncp->nc_nlen == cnp->cn_namelen && 150 !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 151 goto found; /* Fanatism considered bad. */ 152 } 153 nchstats.ncs_miss++; 154 return (0); 155 156 found: 157 NCHHIT(ncp); 158 159 /* We don't want to have an entry, so dump it */ 160 if ((cnp->cn_flags & MAKEENTRY) == 0) { 161 nchstats.ncs_badhits++; 162 PURGE(ncp); 163 return (0); 164 } 165 166 /* We found a "positive" match, return the vnode */ 167 if (ncp->nc_vp != &nchENOENT) { 168 nchstats.ncs_goodhits++; 169 TOUCH(ncp); 170 *vpp = ncp->nc_vp; 171 return (-1); 172 } 173 174 /* We found a negative match, and want to create it, so purge */ 175 if (cnp->cn_nameiop == CREATE) { 176 nchstats.ncs_badhits++; 177 PURGE(ncp); 178 return (0); 179 } 180 181 /* The name does not exists */ 182 nchstats.ncs_neghits++; 183 TOUCH(ncp); 184 return (ENOENT); 185 } 186 187 /* 188 * Add an entry to the cache. 189 */ 190 191 void 192 cache_enter(dvp, vp, cnp) 193 struct vnode *dvp; 194 struct vnode *vp; 195 struct componentname *cnp; 196 { 197 register struct namecache *ncp; 198 register struct nchashhead *ncpp; 199 200 if (!doingcache) 201 return; 202 203 if (cnp->cn_namelen > NCHNAMLEN) { 204 printf("cache_enter: name too long"); 205 return; 206 } 207 208 if (numcache < numvnodes) { 209 /* Add one more entry */ 210 ncp = (struct namecache *) 211 malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 212 bzero((char *)ncp, sizeof *ncp); 213 numcache++; 214 } else if (ncp = nclruhead.tqh_first) { 215 /* reuse an old entry */ 216 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 217 if (ncp->nc_hash.le_prev != 0) { 218 LIST_REMOVE(ncp, nc_hash); 219 ncp->nc_hash.le_prev = 0; 220 } 221 } else { 222 /* give up */ 223 return; 224 } 225 226 /* If vp is NULL this is a "negative" cache entry */ 227 if (!vp) 228 vp = &nchENOENT; 229 230 /* fill in cache info */ 231 ncp->nc_vp = vp; 232 ncp->nc_vpid = vp->v_id; 233 ncp->nc_dvp = dvp; 234 ncp->nc_dvpid = dvp->v_id; 235 ncp->nc_nlen = cnp->cn_namelen; 236 bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 237 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 238 ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) % nchash]; 239 LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 240 } 241 242 /* 243 * Name cache initialization, from vfs_init() when we are booting 244 */ 245 246 void 247 nchinit() 248 { 249 250 TAILQ_INIT(&nclruhead); 251 nchashtbl = phashinit(desiredvnodes, M_CACHE, &nchash); 252 nchENOENT.v_id = 1; 253 } 254 255 /* 256 * Invalidate a all entries to particular vnode. 257 * 258 * We actually just increment the v_id, that will do it. The entries will 259 * be purged by lookup as they get found. 260 * If the v_id wraps around, we need to ditch the entire cache, to avoid 261 * confusion. 262 * No valid vnode will ever have (v_id == 0). 263 */ 264 265 void 266 cache_purge(vp) 267 struct vnode *vp; 268 { 269 struct nchashhead *ncpp; 270 271 vp->v_id = ++nextvnodeid; 272 if (nextvnodeid != 0) 273 return; 274 for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) { 275 while(ncpp->lh_first) 276 PURGE(ncpp->lh_first); 277 } 278 vp->v_id = ++nextvnodeid; 279 } 280 281 /* 282 * Flush all entries referencing a particular filesystem. 283 * 284 * Since we need to check it anyway, we will flush all the invalid 285 * entriess at the same time. 286 * 287 * If we purge anything, we scan the hash-bucket again. There is only 288 * a handful of entries, so it cheap and simple. 289 */ 290 291 void 292 cache_purgevfs(mp) 293 struct mount *mp; 294 { 295 struct nchashhead *ncpp; 296 struct namecache *ncp, *nxtcp; 297 298 /* Scan hash tables for applicable entries */ 299 for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) { 300 ncp = ncpp->lh_first; 301 while(ncp) { 302 if (ncp->nc_dvpid != ncp->nc_dvp->v_id || 303 ncp->nc_vpid != ncp->nc_vp->v_id || 304 ncp->nc_dvp->v_mount == mp) { 305 PURGE(ncp); 306 ncp = ncpp->lh_first; 307 } else { 308 ncp = ncp->nc_hash.le_next; 309 } 310 } 311 } 312 } 313