1 /* $OpenBSD: vfs_cache.c,v 1.11 2003/06/02 23:28:07 millert Exp $ */ 2 /* $NetBSD: vfs_cache.c,v 1.13 1996/02/04 02:18:09 christos Exp $ */ 3 4 /* 5 * Copyright (c) 1989, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 * 32 * @(#)vfs_cache.c 8.3 (Berkeley) 8/22/94 33 */ 34 35 #include <sys/param.h> 36 #include <sys/systm.h> 37 #include <sys/time.h> 38 #include <sys/mount.h> 39 #include <sys/vnode.h> 40 #include <sys/namei.h> 41 #include <sys/errno.h> 42 #include <sys/malloc.h> 43 #include <sys/pool.h> 44 #include <sys/hash.h> 45 46 /* 47 * Name caching works as follows: 48 * 49 * Names found by directory scans are retained in a cache 50 * for future reference. It is managed LRU, so frequently 51 * used names will hang around. Cache is indexed by hash value 52 * obtained from (vp, name) where vp refers to the directory 53 * containing name. 54 * 55 * For simplicity (and economy of storage), names longer than 56 * a maximum length of NCHNAMLEN are not cached; they occur 57 * infrequently in any case, and are almost never of interest. 58 * 59 * Upon reaching the last segment of a path, if the reference 60 * is for DELETE, or NOCACHE is set (rewrite), and the 61 * name is located in the cache, it will be dropped. 62 */ 63 64 /* 65 * Structures associated with name cacheing. 66 */ 67 LIST_HEAD(nchashhead, namecache) *nchashtbl; 68 u_long nchash; /* size of hash table - 1 */ 69 long numcache; /* number of cache entries allocated */ 70 TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */ 71 struct nchstats nchstats; /* cache effectiveness statistics */ 72 73 int doingcache = 1; /* 1 => enable the cache */ 74 75 struct pool nch_pool; 76 77 u_long nextvnodeid; 78 79 /* 80 * Look for a the name in the cache. We don't do this 81 * if the segment name is long, simply so the cache can avoid 82 * holding long names (which would either waste space, or 83 * add greatly to the complexity). 84 * 85 * Lookup is called with ni_dvp pointing to the directory to search, 86 * ni_ptr pointing to the name of the entry being sought, ni_namelen 87 * tells the length of the name, and ni_hash contains a hash of 88 * the name. If the lookup succeeds, the vnode is returned in ni_vp 89 * and a status of 0 is returned. If the locking fails for whatever 90 * reason, the vnode is unlocked and the error is returned to caller. 91 * If the lookup determines that the name does not exist (negative cacheing), 92 * a status of ENOENT is returned. If the lookup fails, a status of -1 93 * is returned. 94 */ 95 int 96 cache_lookup(dvp, vpp, cnp) 97 struct vnode *dvp; 98 struct vnode **vpp; 99 struct componentname *cnp; 100 { 101 struct namecache *ncp; 102 struct nchashhead *ncpp; 103 struct vnode *vp; 104 struct proc *p = curproc; 105 u_long vpid; 106 int error; 107 108 *vpp = NULL; 109 110 if (!doingcache) { 111 cnp->cn_flags &= ~MAKEENTRY; 112 return (-1); 113 } 114 if (cnp->cn_namelen > NCHNAMLEN) { 115 nchstats.ncs_long++; 116 cnp->cn_flags &= ~MAKEENTRY; 117 return (-1); 118 } 119 120 ncpp = &nchashtbl[ 121 hash32_buf(&dvp->v_id, sizeof(dvp->v_id), cnp->cn_hash) & nchash]; 122 LIST_FOREACH(ncp, ncpp, nc_hash) { 123 if (ncp->nc_dvp == dvp && 124 ncp->nc_dvpid == dvp->v_id && 125 ncp->nc_nlen == cnp->cn_namelen && 126 !memcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 127 break; 128 } 129 if (ncp == 0) { 130 nchstats.ncs_miss++; 131 return (-1); 132 } 133 if ((cnp->cn_flags & MAKEENTRY) == 0) { 134 nchstats.ncs_badhits++; 135 goto remove; 136 } else if (ncp->nc_vp == NULL) { 137 /* 138 * Restore the ISWHITEOUT flag saved earlier. 139 */ 140 cnp->cn_flags |= ncp->nc_vpid; 141 if (cnp->cn_nameiop != CREATE || 142 (cnp->cn_flags & ISLASTCN) == 0) { 143 nchstats.ncs_neghits++; 144 /* 145 * Move this slot to end of LRU chain, 146 * if not already there. 147 */ 148 if (TAILQ_NEXT(ncp, nc_lru) != NULL) { 149 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 150 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 151 } 152 return (ENOENT); 153 } else { 154 nchstats.ncs_badhits++; 155 goto remove; 156 } 157 } else if (ncp->nc_vpid != ncp->nc_vp->v_id) { 158 nchstats.ncs_falsehits++; 159 goto remove; 160 } 161 162 vp = ncp->nc_vp; 163 vpid = vp->v_id; 164 if (vp == dvp) { /* lookup on "." */ 165 VREF(dvp); 166 error = 0; 167 } else if (cnp->cn_flags & ISDOTDOT) { 168 VOP_UNLOCK(dvp, 0, p); 169 cnp->cn_flags |= PDIRUNLOCK; 170 error = vget(vp, LK_EXCLUSIVE, p); 171 /* 172 * If the above vget() succeeded and both LOCKPARENT and 173 * ISLASTCN is set, lock the directory vnode as well. 174 */ 175 if (!error && (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) == 0) { 176 if ((error = vn_lock(dvp, LK_EXCLUSIVE, p)) != 0) { 177 vput(vp); 178 return (error); 179 } 180 cnp->cn_flags &= ~PDIRUNLOCK; 181 } 182 } else { 183 error = vget(vp, LK_EXCLUSIVE, p); 184 /* 185 * If the above vget() failed or either of LOCKPARENT or 186 * ISLASTCN is set, unlock the directory vnode. 187 */ 188 if (error || (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) { 189 VOP_UNLOCK(dvp, 0, p); 190 cnp->cn_flags |= PDIRUNLOCK; 191 } 192 } 193 194 /* 195 * Check that the lock succeeded, and that the capability number did 196 * not change while we were waiting for the lock. 197 */ 198 if (error || vpid != vp->v_id) { 199 if (!error) { 200 vput(vp); 201 nchstats.ncs_falsehits++; 202 } else 203 nchstats.ncs_badhits++; 204 /* 205 * The parent needs to be locked when we return to VOP_LOOKUP(). 206 * The `.' case here should be extremely rare (if it can happen 207 * at all), so we don't bother optimizing out the unlock/relock. 208 */ 209 if (vp == dvp || error || 210 (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) { 211 if ((error = vn_lock(dvp, LK_EXCLUSIVE, p)) != 0) 212 return (error); 213 cnp->cn_flags &= ~PDIRUNLOCK; 214 } 215 return (-1); 216 } 217 218 nchstats.ncs_goodhits++; 219 /* 220 * Move this slot to end of LRU chain, if not already there. 221 */ 222 if (TAILQ_NEXT(ncp, nc_lru) != NULL) { 223 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 224 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 225 } 226 *vpp = vp; 227 return (0); 228 229 remove: 230 /* 231 * Last component and we are renaming or deleting, 232 * the cache entry is invalid, or otherwise don't 233 * want cache entry to exist. 234 */ 235 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 236 LIST_REMOVE(ncp, nc_hash); 237 ncp->nc_hash.le_prev = NULL; 238 #if 0 239 if (ncp->nc_vhash.le_prev != NULL) { 240 LIST_REMOVE(ncp, nc_vhash); 241 ncp->nc_vhash.le_prev = NULL; 242 } 243 #endif 244 TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); 245 return (-1); 246 } 247 248 /* 249 * Add an entry to the cache 250 */ 251 void 252 cache_enter(dvp, vp, cnp) 253 struct vnode *dvp; 254 struct vnode *vp; 255 struct componentname *cnp; 256 { 257 register struct namecache *ncp; 258 register struct nchashhead *ncpp; 259 260 #ifdef DIAGNOSTIC 261 if (cnp->cn_namelen > NCHNAMLEN) 262 panic("cache_enter: name too long"); 263 #endif 264 if (!doingcache) 265 return; 266 /* 267 * Free the cache slot at head of lru chain. 268 */ 269 if (numcache < desiredvnodes) { 270 ncp = pool_get(&nch_pool, PR_WAITOK); 271 bzero((char *)ncp, sizeof *ncp); 272 numcache++; 273 } else if ((ncp = nclruhead.tqh_first) != NULL) { 274 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 275 if (ncp->nc_hash.le_prev != 0) { 276 LIST_REMOVE(ncp, nc_hash); 277 ncp->nc_hash.le_prev = 0; 278 } 279 } else 280 return; 281 /* grab the vnode we just found */ 282 ncp->nc_vp = vp; 283 if (vp) 284 ncp->nc_vpid = vp->v_id; 285 else { 286 /* 287 * For negative hits, save the ISWHITEOUT flag so we can 288 * restore it later when the cache entry is used again. 289 */ 290 ncp->nc_vpid = cnp->cn_flags & ISWHITEOUT; 291 } 292 /* fill in cache info */ 293 ncp->nc_dvp = dvp; 294 ncp->nc_dvpid = dvp->v_id; 295 ncp->nc_nlen = cnp->cn_namelen; 296 bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 297 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 298 ncpp = &nchashtbl[ 299 hash32_buf(&dvp->v_id, sizeof(dvp->v_id), cnp->cn_hash) & nchash]; 300 LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 301 } 302 303 /* 304 * Name cache initialization, from vfs_init() when we are booting 305 */ 306 void 307 nchinit() 308 { 309 310 TAILQ_INIT(&nclruhead); 311 nchashtbl = hashinit(desiredvnodes, M_CACHE, M_WAITOK, &nchash); 312 pool_init(&nch_pool, sizeof(struct namecache), 0, 0, 0, "nchpl", 313 &pool_allocator_nointr); 314 } 315 316 /* 317 * Cache flush, a particular vnode; called when a vnode is renamed to 318 * hide entries that would now be invalid 319 */ 320 void 321 cache_purge(vp) 322 struct vnode *vp; 323 { 324 struct namecache *ncp; 325 struct nchashhead *ncpp; 326 327 vp->v_id = ++nextvnodeid; 328 if (nextvnodeid != 0) 329 return; 330 for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 331 for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) { 332 ncp->nc_vpid = 0; 333 ncp->nc_dvpid = 0; 334 } 335 } 336 vp->v_id = ++nextvnodeid; 337 } 338 339 /* 340 * Cache flush, a whole filesystem; called when filesys is umounted to 341 * remove entries that would now be invalid 342 * 343 * The line "nxtcp = nchhead" near the end is to avoid potential problems 344 * if the cache lru chain is modified while we are dumping the 345 * inode. This makes the algorithm O(n^2), but do you think I care? 346 */ 347 void 348 cache_purgevfs(mp) 349 struct mount *mp; 350 { 351 register struct namecache *ncp, *nxtcp; 352 353 for (ncp = nclruhead.tqh_first; ncp != 0; ncp = nxtcp) { 354 if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) { 355 nxtcp = ncp->nc_lru.tqe_next; 356 continue; 357 } 358 /* free the resources we had */ 359 ncp->nc_vp = NULL; 360 ncp->nc_dvp = NULL; 361 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 362 if (ncp->nc_hash.le_prev != 0) { 363 LIST_REMOVE(ncp, nc_hash); 364 ncp->nc_hash.le_prev = 0; 365 } 366 /* cause rescan of list, it may have altered */ 367 nxtcp = nclruhead.tqh_first; 368 TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); 369 } 370 } 371