Annotation of sys/kern/vfs_cache.c, Revision 1.1
1.1 ! nbrk 1: /* $OpenBSD: vfs_cache.c,v 1.25 2007/06/21 12:05:14 pedro 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: pool_put(&nch_pool, ncp);
! 248: numcache--;
! 249: return (-1);
! 250: }
! 251:
! 252: /*
! 253: * Scan cache looking for name of directory entry pointing at vp.
! 254: *
! 255: * Fill in dvpp.
! 256: *
! 257: * If bufp is non-NULL, also place the name in the buffer which starts
! 258: * at bufp, immediately before *bpp, and move bpp backwards to point
! 259: * at the start of it. (Yes, this is a little baroque, but it's done
! 260: * this way to cater to the whims of getcwd).
! 261: *
! 262: * Returns 0 on success, -1 on cache miss, positive errno on failure.
! 263: *
! 264: * TODO: should we return *dvpp locked?
! 265: */
! 266:
! 267: int
! 268: cache_revlookup(struct vnode *vp, struct vnode **dvpp, char **bpp, char *bufp)
! 269: {
! 270: struct namecache *ncp;
! 271: struct vnode *dvp;
! 272: struct ncvhashhead *nvcpp;
! 273: char *bp;
! 274:
! 275: if (!doingcache)
! 276: goto out;
! 277:
! 278: nvcpp = &ncvhashtbl[NCVHASH(vp)];
! 279:
! 280: LIST_FOREACH(ncp, nvcpp, nc_vhash) {
! 281: if (ncp->nc_vp == vp &&
! 282: ncp->nc_vpid == vp->v_id &&
! 283: (dvp = ncp->nc_dvp) != NULL &&
! 284: /* avoid pesky '.' entries.. */
! 285: dvp != vp && ncp->nc_dvpid == dvp->v_id) {
! 286:
! 287: #ifdef DIAGNOSTIC
! 288: if (ncp->nc_nlen == 1 &&
! 289: ncp->nc_name[0] == '.')
! 290: panic("cache_revlookup: found entry for .");
! 291:
! 292: if (ncp->nc_nlen == 2 &&
! 293: ncp->nc_name[0] == '.' &&
! 294: ncp->nc_name[1] == '.')
! 295: panic("cache_revlookup: found entry for ..");
! 296: #endif
! 297: nchstats.ncs_revhits++;
! 298:
! 299: if (bufp != NULL) {
! 300: bp = *bpp;
! 301: bp -= ncp->nc_nlen;
! 302: if (bp <= bufp) {
! 303: *dvpp = NULL;
! 304: return (ERANGE);
! 305: }
! 306: memcpy(bp, ncp->nc_name, ncp->nc_nlen);
! 307: *bpp = bp;
! 308: }
! 309:
! 310: *dvpp = dvp;
! 311:
! 312: /*
! 313: * XXX: Should we vget() here to have more
! 314: * consistent semantics with cache_lookup()?
! 315: *
! 316: * For MP safety it might be necessary to do
! 317: * this here, while also protecting hash
! 318: * tables themselves to provide some sort of
! 319: * sane inter locking.
! 320: */
! 321: return (0);
! 322: }
! 323: }
! 324: nchstats.ncs_revmiss++;
! 325:
! 326: out:
! 327: *dvpp = NULL;
! 328: return (-1);
! 329: }
! 330:
! 331: /*
! 332: * Add an entry to the cache
! 333: */
! 334: void
! 335: cache_enter(struct vnode *dvp, struct vnode *vp, struct componentname *cnp)
! 336: {
! 337: struct namecache *ncp;
! 338: struct nchashhead *ncpp;
! 339: struct ncvhashhead *nvcpp;
! 340:
! 341: if (!doingcache || cnp->cn_namelen > NCHNAMLEN)
! 342: return;
! 343:
! 344: /*
! 345: * Free the cache slot at head of lru chain.
! 346: */
! 347: if (numcache < desiredvnodes) {
! 348: ncp = pool_get(&nch_pool, PR_WAITOK);
! 349: bzero((char *)ncp, sizeof *ncp);
! 350: numcache++;
! 351: } else if ((ncp = TAILQ_FIRST(&nclruhead)) != NULL) {
! 352: TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
! 353: if (ncp->nc_hash.le_prev != NULL) {
! 354: LIST_REMOVE(ncp, nc_hash);
! 355: ncp->nc_hash.le_prev = NULL;
! 356: }
! 357: if (ncp->nc_vhash.le_prev != NULL) {
! 358: LIST_REMOVE(ncp, nc_vhash);
! 359: ncp->nc_vhash.le_prev = NULL;
! 360: }
! 361: } else
! 362: return;
! 363: /* grab the vnode we just found */
! 364: ncp->nc_vp = vp;
! 365: if (vp)
! 366: ncp->nc_vpid = vp->v_id;
! 367: /* fill in cache info */
! 368: ncp->nc_dvp = dvp;
! 369: ncp->nc_dvpid = dvp->v_id;
! 370: ncp->nc_nlen = cnp->cn_namelen;
! 371: bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
! 372: TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
! 373: ncpp = &nchashtbl[NCHASH(dvp, cnp)];
! 374: LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
! 375:
! 376: /*
! 377: * Create reverse-cache entries (used in getcwd) for
! 378: * directories.
! 379: */
! 380:
! 381: ncp->nc_vhash.le_prev = NULL;
! 382: ncp->nc_vhash.le_next = NULL;
! 383:
! 384: if (vp && vp != dvp && vp->v_type == VDIR &&
! 385: (ncp->nc_nlen > 2 ||
! 386: (ncp->nc_nlen > 1 && ncp->nc_name[1] != '.') ||
! 387: (ncp->nc_nlen > 0 && ncp->nc_name[0] != '.'))) {
! 388: nvcpp = &ncvhashtbl[NCVHASH(vp)];
! 389: LIST_INSERT_HEAD(nvcpp, ncp, nc_vhash);
! 390: }
! 391: }
! 392:
! 393: /*
! 394: * Name cache initialization, from vfs_init() when we are booting
! 395: */
! 396: void
! 397: nchinit(void)
! 398: {
! 399:
! 400: TAILQ_INIT(&nclruhead);
! 401: nchashtbl = hashinit(desiredvnodes, M_CACHE, M_WAITOK, &nchash);
! 402: ncvhashtbl = hashinit(desiredvnodes/8, M_CACHE, M_WAITOK, &ncvhash);
! 403: pool_init(&nch_pool, sizeof(struct namecache), 0, 0, 0, "nchpl",
! 404: &pool_allocator_nointr);
! 405: }
! 406:
! 407: /*
! 408: * Cache flush, a particular vnode; called when a vnode is renamed to
! 409: * hide entries that would now be invalid
! 410: */
! 411: void
! 412: cache_purge(struct vnode *vp)
! 413: {
! 414: struct namecache *ncp;
! 415: struct nchashhead *ncpp;
! 416:
! 417: vp->v_id = ++nextvnodeid;
! 418: if (nextvnodeid != 0)
! 419: return;
! 420: for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
! 421: LIST_FOREACH(ncp, ncpp, nc_hash) {
! 422: ncp->nc_vpid = 0;
! 423: ncp->nc_dvpid = 0;
! 424: }
! 425: }
! 426: vp->v_id = ++nextvnodeid;
! 427: }
! 428:
! 429: /*
! 430: * Cache flush, a whole filesystem; called when filesys is umounted to
! 431: * remove entries that would now be invalid
! 432: */
! 433: void
! 434: cache_purgevfs(struct mount *mp)
! 435: {
! 436: struct namecache *ncp, *nxtcp;
! 437:
! 438: for (ncp = TAILQ_FIRST(&nclruhead); ncp != TAILQ_END(&nclruhead);
! 439: ncp = nxtcp) {
! 440: nxtcp = TAILQ_NEXT(ncp, nc_lru);
! 441: if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp)
! 442: continue;
! 443: /* free the resources we had */
! 444: ncp->nc_vp = NULL;
! 445: ncp->nc_dvp = NULL;
! 446: TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
! 447: if (ncp->nc_hash.le_prev != NULL) {
! 448: LIST_REMOVE(ncp, nc_hash);
! 449: ncp->nc_hash.le_prev = NULL;
! 450: }
! 451: if (ncp->nc_vhash.le_prev != NULL) {
! 452: LIST_REMOVE(ncp, nc_vhash);
! 453: ncp->nc_vhash.le_prev = NULL;
! 454: }
! 455: pool_put(&nch_pool, ncp);
! 456: numcache--;
! 457: }
! 458: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to vfs_cache.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / kern