1 /* $OpenBSD: vfs_cache.c,v 1.29 2008/10/24 00:22:57 tedu 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 * TODO: namecache access should really be locked. 48 */ 49 50 /* 51 * Name caching works as follows: 52 * 53 * Names found by directory scans are retained in a cache 54 * for future reference. It is managed LRU, so frequently 55 * used names will hang around. Cache is indexed by hash value 56 * obtained from (vp, name) where vp refers to the directory 57 * containing name. 58 * 59 * For simplicity (and economy of storage), names longer than 60 * a maximum length of NCHNAMLEN are not cached; they occur 61 * infrequently in any case, and are almost never of interest. 62 * 63 * Upon reaching the last segment of a path, if the reference 64 * is for DELETE, or NOCACHE is set (rewrite), and the 65 * name is located in the cache, it will be dropped. 66 */ 67 68 /* 69 * Structures associated with name caching. 70 */ 71 LIST_HEAD(nchashhead, namecache) *nchashtbl; 72 u_long nchash; /* size of hash table - 1 */ 73 long numcache; /* number of cache entries allocated */ 74 TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */ 75 struct nchstats nchstats; /* cache effectiveness statistics */ 76 77 LIST_HEAD(ncvhashhead, namecache) *ncvhashtbl; 78 u_long ncvhash; /* size of hash table - 1 */ 79 80 #define NCHASH(dvp, cnp) \ 81 hash32_buf(&(dvp)->v_id, sizeof((dvp)->v_id), (cnp)->cn_hash) & nchash 82 83 #define NCVHASH(vp) (vp)->v_id & ncvhash 84 85 int doingcache = 1; /* 1 => enable the cache */ 86 87 struct pool nch_pool; 88 89 u_long nextvnodeid; 90 91 /* 92 * Look for a name in the cache. We don't do this if the segment name is 93 * long, simply so the cache can avoid holding long names (which would 94 * either waste space, or add greatly to the complexity). 95 * 96 * Lookup is called with ni_dvp pointing to the directory to search, 97 * ni_ptr pointing to the name of the entry being sought, ni_namelen 98 * tells the length of the name, and ni_hash contains a hash of 99 * the name. If the lookup succeeds, the vnode is returned in ni_vp 100 * and a status of 0 is returned. If the locking fails for whatever 101 * reason, the vnode is unlocked and the error is returned to caller. 102 * If the lookup determines that the name does not exist (negative caching), 103 * a status of ENOENT is returned. If the lookup fails, a status of -1 104 * is returned. 105 */ 106 int 107 cache_lookup(struct vnode *dvp, struct vnode **vpp, struct componentname *cnp) 108 { 109 struct namecache *ncp; 110 struct nchashhead *ncpp; 111 struct vnode *vp; 112 struct proc *p = curproc; 113 u_long vpid; 114 int error; 115 116 *vpp = NULL; 117 118 if (!doingcache) { 119 cnp->cn_flags &= ~MAKEENTRY; 120 return (-1); 121 } 122 if (cnp->cn_namelen > NCHNAMLEN) { 123 nchstats.ncs_long++; 124 cnp->cn_flags &= ~MAKEENTRY; 125 return (-1); 126 } 127 128 ncpp = &nchashtbl[NCHASH(dvp, cnp)]; 129 LIST_FOREACH(ncp, ncpp, nc_hash) { 130 if (ncp->nc_dvp == dvp && 131 ncp->nc_dvpid == dvp->v_id && 132 ncp->nc_nlen == cnp->cn_namelen && 133 !memcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 134 break; 135 } 136 if (ncp == NULL) { 137 nchstats.ncs_miss++; 138 return (-1); 139 } 140 if ((cnp->cn_flags & MAKEENTRY) == 0) { 141 nchstats.ncs_badhits++; 142 goto remove; 143 } else if (ncp->nc_vp == NULL) { 144 if (cnp->cn_nameiop != CREATE || 145 (cnp->cn_flags & ISLASTCN) == 0) { 146 nchstats.ncs_neghits++; 147 /* 148 * Move this slot to end of LRU chain, 149 * if not already there. 150 */ 151 if (TAILQ_NEXT(ncp, nc_lru) != NULL) { 152 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 153 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 154 } 155 return (ENOENT); 156 } else { 157 nchstats.ncs_badhits++; 158 goto remove; 159 } 160 } else if (ncp->nc_vpid != ncp->nc_vp->v_id) { 161 nchstats.ncs_falsehits++; 162 goto remove; 163 } 164 165 vp = ncp->nc_vp; 166 vpid = vp->v_id; 167 if (vp == dvp) { /* lookup on "." */ 168 VREF(dvp); 169 error = 0; 170 } else if (cnp->cn_flags & ISDOTDOT) { 171 VOP_UNLOCK(dvp, 0, p); 172 cnp->cn_flags |= PDIRUNLOCK; 173 error = vget(vp, LK_EXCLUSIVE, p); 174 /* 175 * If the above vget() succeeded and both LOCKPARENT and 176 * ISLASTCN is set, lock the directory vnode as well. 177 */ 178 if (!error && (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) == 0) { 179 if ((error = vn_lock(dvp, LK_EXCLUSIVE, p)) != 0) { 180 vput(vp); 181 return (error); 182 } 183 cnp->cn_flags &= ~PDIRUNLOCK; 184 } 185 } else { 186 error = vget(vp, LK_EXCLUSIVE, p); 187 /* 188 * If the above vget() failed or either of LOCKPARENT or 189 * ISLASTCN is set, unlock the directory vnode. 190 */ 191 if (error || (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) { 192 VOP_UNLOCK(dvp, 0, p); 193 cnp->cn_flags |= PDIRUNLOCK; 194 } 195 } 196 197 /* 198 * Check that the lock succeeded, and that the capability number did 199 * not change while we were waiting for the lock. 200 */ 201 if (error || vpid != vp->v_id) { 202 if (!error) { 203 vput(vp); 204 nchstats.ncs_falsehits++; 205 } else 206 nchstats.ncs_badhits++; 207 /* 208 * The parent needs to be locked when we return to VOP_LOOKUP(). 209 * The `.' case here should be extremely rare (if it can happen 210 * at all), so we don't bother optimizing out the unlock/relock. 211 */ 212 if (vp == dvp || error || 213 (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) { 214 if ((error = vn_lock(dvp, LK_EXCLUSIVE, p)) != 0) 215 return (error); 216 cnp->cn_flags &= ~PDIRUNLOCK; 217 } 218 return (-1); 219 } 220 221 nchstats.ncs_goodhits++; 222 /* 223 * Move this slot to end of LRU chain, if not already there. 224 */ 225 if (TAILQ_NEXT(ncp, nc_lru) != NULL) { 226 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 227 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 228 } 229 *vpp = vp; 230 return (0); 231 232 remove: 233 /* 234 * Last component and we are renaming or deleting, 235 * the cache entry is invalid, or otherwise don't 236 * want cache entry to exist. 237 */ 238 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 239 LIST_REMOVE(ncp, nc_hash); 240 ncp->nc_hash.le_prev = NULL; 241 242 if (ncp->nc_vhash.le_prev != NULL) { 243 LIST_REMOVE(ncp, nc_vhash); 244 ncp->nc_vhash.le_prev = NULL; 245 } 246 247 TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); 248 return (-1); 249 } 250 251 /* 252 * Scan cache looking for name of directory entry pointing at vp. 253 * 254 * Fill in dvpp. 255 * 256 * If bufp is non-NULL, also place the name in the buffer which starts 257 * at bufp, immediately before *bpp, and move bpp backwards to point 258 * at the start of it. (Yes, this is a little baroque, but it's done 259 * this way to cater to the whims of getcwd). 260 * 261 * Returns 0 on success, -1 on cache miss, positive errno on failure. 262 * 263 * TODO: should we return *dvpp locked? 264 */ 265 266 int 267 cache_revlookup(struct vnode *vp, struct vnode **dvpp, char **bpp, char *bufp) 268 { 269 struct namecache *ncp; 270 struct vnode *dvp; 271 struct ncvhashhead *nvcpp; 272 char *bp; 273 274 if (!doingcache) 275 goto out; 276 277 nvcpp = &ncvhashtbl[NCVHASH(vp)]; 278 279 LIST_FOREACH(ncp, nvcpp, nc_vhash) { 280 if (ncp->nc_vp == vp && 281 ncp->nc_vpid == vp->v_id && 282 (dvp = ncp->nc_dvp) != NULL && 283 /* avoid pesky '.' entries.. */ 284 dvp != vp && ncp->nc_dvpid == dvp->v_id) { 285 286 #ifdef DIAGNOSTIC 287 if (ncp->nc_nlen == 1 && 288 ncp->nc_name[0] == '.') 289 panic("cache_revlookup: found entry for ."); 290 291 if (ncp->nc_nlen == 2 && 292 ncp->nc_name[0] == '.' && 293 ncp->nc_name[1] == '.') 294 panic("cache_revlookup: found entry for .."); 295 #endif 296 nchstats.ncs_revhits++; 297 298 if (bufp != NULL) { 299 bp = *bpp; 300 bp -= ncp->nc_nlen; 301 if (bp <= bufp) { 302 *dvpp = NULL; 303 return (ERANGE); 304 } 305 memcpy(bp, ncp->nc_name, ncp->nc_nlen); 306 *bpp = bp; 307 } 308 309 *dvpp = dvp; 310 311 /* 312 * XXX: Should we vget() here to have more 313 * consistent semantics with cache_lookup()? 314 * 315 * For MP safety it might be necessary to do 316 * this here, while also protecting hash 317 * tables themselves to provide some sort of 318 * sane inter locking. 319 */ 320 return (0); 321 } 322 } 323 nchstats.ncs_revmiss++; 324 325 out: 326 *dvpp = NULL; 327 return (-1); 328 } 329 330 /* 331 * Add an entry to the cache 332 */ 333 void 334 cache_enter(struct vnode *dvp, struct vnode *vp, struct componentname *cnp) 335 { 336 struct namecache *ncp; 337 struct nchashhead *ncpp; 338 struct ncvhashhead *nvcpp; 339 340 if (!doingcache || cnp->cn_namelen > NCHNAMLEN) 341 return; 342 343 /* 344 * Free the cache slot at head of lru chain. 345 */ 346 if (numcache < desiredvnodes) { 347 ncp = pool_get(&nch_pool, PR_WAITOK|PR_ZERO); 348 numcache++; 349 } else if ((ncp = TAILQ_FIRST(&nclruhead)) != NULL) { 350 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 351 if (ncp->nc_hash.le_prev != NULL) { 352 LIST_REMOVE(ncp, nc_hash); 353 ncp->nc_hash.le_prev = NULL; 354 } 355 if (ncp->nc_vhash.le_prev != NULL) { 356 LIST_REMOVE(ncp, nc_vhash); 357 ncp->nc_vhash.le_prev = NULL; 358 } 359 } else 360 return; 361 /* grab the vnode we just found */ 362 ncp->nc_vp = vp; 363 if (vp) 364 ncp->nc_vpid = vp->v_id; 365 /* fill in cache info */ 366 ncp->nc_dvp = dvp; 367 ncp->nc_dvpid = dvp->v_id; 368 ncp->nc_nlen = cnp->cn_namelen; 369 bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 370 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 371 ncpp = &nchashtbl[NCHASH(dvp, cnp)]; 372 LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 373 374 /* 375 * Create reverse-cache entries (used in getcwd) for 376 * directories. 377 */ 378 379 ncp->nc_vhash.le_prev = NULL; 380 ncp->nc_vhash.le_next = NULL; 381 382 if (vp && vp != dvp && vp->v_type == VDIR && 383 (ncp->nc_nlen > 2 || 384 (ncp->nc_nlen > 1 && ncp->nc_name[1] != '.') || 385 (ncp->nc_nlen > 0 && ncp->nc_name[0] != '.'))) { 386 nvcpp = &ncvhashtbl[NCVHASH(vp)]; 387 LIST_INSERT_HEAD(nvcpp, ncp, nc_vhash); 388 } 389 } 390 391 /* 392 * Name cache initialization, from vfs_init() when we are booting 393 */ 394 void 395 nchinit() 396 { 397 398 TAILQ_INIT(&nclruhead); 399 nchashtbl = hashinit(desiredvnodes, M_CACHE, M_WAITOK, &nchash); 400 ncvhashtbl = hashinit(desiredvnodes/8, M_CACHE, M_WAITOK, &ncvhash); 401 pool_init(&nch_pool, sizeof(struct namecache), 0, 0, 0, "nchpl", 402 &pool_allocator_nointr); 403 } 404 405 /* 406 * Cache flush, a particular vnode; called when a vnode is renamed to 407 * hide entries that would now be invalid 408 */ 409 void 410 cache_purge(struct vnode *vp) 411 { 412 struct namecache *ncp; 413 struct nchashhead *ncpp; 414 415 vp->v_id = ++nextvnodeid; 416 if (nextvnodeid != 0) 417 return; 418 for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 419 LIST_FOREACH(ncp, ncpp, nc_hash) { 420 ncp->nc_vpid = 0; 421 ncp->nc_dvpid = 0; 422 } 423 } 424 vp->v_id = ++nextvnodeid; 425 } 426 427 /* 428 * Cache flush, a whole filesystem; called when filesys is umounted to 429 * remove entries that would now be invalid 430 * 431 * The line "nxtcp = nchhead" near the end is to avoid potential problems 432 * if the cache lru chain is modified while we are dumping the 433 * inode. This makes the algorithm O(n^2), but do you think I care? 434 */ 435 void 436 cache_purgevfs(struct mount *mp) 437 { 438 struct namecache *ncp, *nxtcp; 439 440 for (ncp = TAILQ_FIRST(&nclruhead); ncp != TAILQ_END(&nclruhead); 441 ncp = nxtcp) { 442 if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) { 443 nxtcp = TAILQ_NEXT(ncp, nc_lru); 444 continue; 445 } 446 /* free the resources we had */ 447 ncp->nc_vp = NULL; 448 ncp->nc_dvp = NULL; 449 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 450 if (ncp->nc_hash.le_prev != NULL) { 451 LIST_REMOVE(ncp, nc_hash); 452 ncp->nc_hash.le_prev = NULL; 453 } 454 if (ncp->nc_vhash.le_prev != NULL) { 455 LIST_REMOVE(ncp, nc_vhash); 456 ncp->nc_vhash.le_prev = NULL; 457 } 458 /* cause rescan of list, it may have altered */ 459 nxtcp = TAILQ_FIRST(&nclruhead); 460 TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); 461 } 462 } 463