Annotation of src/sys/kern/vfs_cache.c, Revision 1.18
1.18 ! thorpej 1: /* $NetBSD: vfs_cache.c,v 1.17 1998/08/04 04:03:18 perry Exp $ */
1.6 cgd 2:
1.1 cgd 3: /*
1.5 mycroft 4: * Copyright (c) 1989, 1993
5: * The Regents of the University of California. All rights reserved.
1.1 cgd 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: *
1.10 mycroft 35: * @(#)vfs_cache.c 8.3 (Berkeley) 8/22/94
1.1 cgd 36: */
37:
1.4 mycroft 38: #include <sys/param.h>
39: #include <sys/systm.h>
40: #include <sys/time.h>
41: #include <sys/mount.h>
42: #include <sys/vnode.h>
43: #include <sys/namei.h>
44: #include <sys/errno.h>
45: #include <sys/malloc.h>
1.18 ! thorpej 46: #include <sys/pool.h>
1.1 cgd 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: * For simplicity (and economy of storage), names longer than
58: * a maximum length of NCHNAMLEN are not cached; they occur
59: * infrequently in any case, and are almost never of interest.
60: *
61: * Upon reaching the last segment of a path, if the reference
62: * is for DELETE, or NOCACHE is set (rewrite), and the
63: * name is located in the cache, it will be dropped.
64: */
65:
66: /*
67: * Structures associated with name cacheing.
68: */
1.9 mycroft 69: LIST_HEAD(nchashhead, namecache) *nchashtbl;
1.1 cgd 70: u_long nchash; /* size of hash table - 1 */
71: long numcache; /* number of cache entries allocated */
1.9 mycroft 72: TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */
1.1 cgd 73: struct nchstats nchstats; /* cache effectiveness statistics */
74:
1.18 ! thorpej 75: struct pool namecache_pool;
! 76:
1.7 chopps 77: int doingcache = 1; /* 1 => enable the cache */
1.1 cgd 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
1.5 mycroft 88: * the name. If the lookup succeeds, the vnode is returned in ni_vp
89: * and a status of -1 is returned. If the lookup determines that
90: * the name does not exist (negative cacheing), a status of ENOENT
91: * is returned. If the lookup fails, a status of zero is returned.
1.1 cgd 92: */
1.5 mycroft 93: int
94: cache_lookup(dvp, vpp, cnp)
95: struct vnode *dvp;
96: struct vnode **vpp;
97: struct componentname *cnp;
1.1 cgd 98: {
1.9 mycroft 99: register struct namecache *ncp;
100: register struct nchashhead *ncpp;
1.1 cgd 101:
1.8 cgd 102: if (!doingcache) {
103: cnp->cn_flags &= ~MAKEENTRY;
1.1 cgd 104: return (0);
1.8 cgd 105: }
1.5 mycroft 106: if (cnp->cn_namelen > NCHNAMLEN) {
1.1 cgd 107: nchstats.ncs_long++;
1.5 mycroft 108: cnp->cn_flags &= ~MAKEENTRY;
1.1 cgd 109: return (0);
110: }
1.12 ws 111: ncpp = &nchashtbl[(cnp->cn_hash ^ dvp->v_id) & nchash];
1.9 mycroft 112: for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) {
1.1 cgd 113: if (ncp->nc_dvp == dvp &&
114: ncp->nc_dvpid == dvp->v_id &&
1.5 mycroft 115: ncp->nc_nlen == cnp->cn_namelen &&
1.17 perry 116: !memcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
1.1 cgd 117: break;
118: }
1.9 mycroft 119: if (ncp == 0) {
1.1 cgd 120: nchstats.ncs_miss++;
121: return (0);
122: }
1.9 mycroft 123: if ((cnp->cn_flags & MAKEENTRY) == 0) {
1.1 cgd 124: nchstats.ncs_badhits++;
125: } else if (ncp->nc_vp == NULL) {
1.11 mycroft 126: /*
127: * Restore the ISWHITEOUT flag saved earlier.
128: */
129: cnp->cn_flags |= ncp->nc_vpid;
1.5 mycroft 130: if (cnp->cn_nameiop != CREATE) {
1.1 cgd 131: nchstats.ncs_neghits++;
132: /*
133: * Move this slot to end of LRU chain,
134: * if not already there.
135: */
1.9 mycroft 136: if (ncp->nc_lru.tqe_next != 0) {
137: TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
138: TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
1.1 cgd 139: }
140: return (ENOENT);
1.15 fvdl 141: } else
142: nchstats.ncs_badhits++;
1.1 cgd 143: } else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
144: nchstats.ncs_falsehits++;
145: } else {
146: nchstats.ncs_goodhits++;
147: /*
148: * move this slot to end of LRU chain, if not already there
149: */
1.9 mycroft 150: if (ncp->nc_lru.tqe_next != 0) {
151: TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
152: TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
1.1 cgd 153: }
1.5 mycroft 154: *vpp = ncp->nc_vp;
1.1 cgd 155: return (-1);
156: }
157:
158: /*
159: * Last component and we are renaming or deleting,
160: * the cache entry is invalid, or otherwise don't
161: * want cache entry to exist.
162: */
1.9 mycroft 163: TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
164: LIST_REMOVE(ncp, nc_hash);
165: ncp->nc_hash.le_prev = 0;
166: TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);
1.1 cgd 167: return (0);
168: }
169:
170: /*
171: * Add an entry to the cache
172: */
1.13 christos 173: void
1.5 mycroft 174: cache_enter(dvp, vp, cnp)
175: struct vnode *dvp;
176: struct vnode *vp;
177: struct componentname *cnp;
1.1 cgd 178: {
1.9 mycroft 179: register struct namecache *ncp;
180: register struct nchashhead *ncpp;
1.1 cgd 181:
1.5 mycroft 182: #ifdef DIAGNOSTIC
183: if (cnp->cn_namelen > NCHNAMLEN)
184: panic("cache_enter: name too long");
185: #endif
1.1 cgd 186: if (!doingcache)
187: return;
188: /*
189: * Free the cache slot at head of lru chain.
190: */
191: if (numcache < desiredvnodes) {
1.18 ! thorpej 192: ncp = pool_get(&namecache_pool, PR_WAITOK);
1.17 perry 193: memset((char *)ncp, 0, sizeof(*ncp));
1.1 cgd 194: numcache++;
1.13 christos 195: } else if ((ncp = nclruhead.tqh_first) != NULL) {
1.9 mycroft 196: TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
197: if (ncp->nc_hash.le_prev != 0) {
198: LIST_REMOVE(ncp, nc_hash);
199: ncp->nc_hash.le_prev = 0;
1.5 mycroft 200: }
1.1 cgd 201: } else
202: return;
203: /* grab the vnode we just found */
1.5 mycroft 204: ncp->nc_vp = vp;
205: if (vp)
206: ncp->nc_vpid = vp->v_id;
1.11 mycroft 207: else {
208: /*
209: * For negative hits, save the ISWHITEOUT flag so we can
210: * restore it later when the cache entry is used again.
211: */
212: ncp->nc_vpid = cnp->cn_flags & ISWHITEOUT;
213: }
1.1 cgd 214: /* fill in cache info */
1.5 mycroft 215: ncp->nc_dvp = dvp;
216: ncp->nc_dvpid = dvp->v_id;
217: ncp->nc_nlen = cnp->cn_namelen;
1.17 perry 218: memcpy(ncp->nc_name, cnp->cn_nameptr, (unsigned)ncp->nc_nlen);
1.9 mycroft 219: TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
1.12 ws 220: ncpp = &nchashtbl[(cnp->cn_hash ^ dvp->v_id) & nchash];
1.9 mycroft 221: LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
1.1 cgd 222: }
223:
224: /*
225: * Name cache initialization, from vfs_init() when we are booting
226: */
1.13 christos 227: void
1.1 cgd 228: nchinit()
229: {
230:
1.9 mycroft 231: TAILQ_INIT(&nclruhead);
1.14 chs 232: nchashtbl = hashinit(desiredvnodes, M_CACHE, M_WAITOK, &nchash);
1.18 ! thorpej 233: pool_init(&namecache_pool, sizeof(struct namecache), 0, 0, 0,
! 234: "ncachepl", 0, pool_page_alloc_nointr, pool_page_free_nointr,
! 235: M_CACHE);
1.1 cgd 236: }
237:
238: /*
239: * Cache flush, a particular vnode; called when a vnode is renamed to
240: * hide entries that would now be invalid
241: */
1.13 christos 242: void
1.1 cgd 243: cache_purge(vp)
244: struct vnode *vp;
245: {
1.9 mycroft 246: struct namecache *ncp;
247: struct nchashhead *ncpp;
1.1 cgd 248:
249: vp->v_id = ++nextvnodeid;
250: if (nextvnodeid != 0)
251: return;
1.5 mycroft 252: for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
1.9 mycroft 253: for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) {
1.1 cgd 254: ncp->nc_vpid = 0;
255: ncp->nc_dvpid = 0;
256: }
257: }
258: vp->v_id = ++nextvnodeid;
259: }
260:
261: /*
262: * Cache flush, a whole filesystem; called when filesys is umounted to
263: * remove entries that would now be invalid
264: *
265: * The line "nxtcp = nchhead" near the end is to avoid potential problems
266: * if the cache lru chain is modified while we are dumping the
267: * inode. This makes the algorithm O(n^2), but do you think I care?
268: */
1.13 christos 269: void
1.1 cgd 270: cache_purgevfs(mp)
271: struct mount *mp;
272: {
273: register struct namecache *ncp, *nxtcp;
274:
1.9 mycroft 275: for (ncp = nclruhead.tqh_first; ncp != 0; ncp = nxtcp) {
1.5 mycroft 276: if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) {
1.9 mycroft 277: nxtcp = ncp->nc_lru.tqe_next;
1.1 cgd 278: continue;
1.5 mycroft 279: }
1.1 cgd 280: /* free the resources we had */
281: ncp->nc_vp = NULL;
282: ncp->nc_dvp = NULL;
1.9 mycroft 283: TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
284: if (ncp->nc_hash.le_prev != 0) {
285: LIST_REMOVE(ncp, nc_hash);
286: ncp->nc_hash.le_prev = 0;
1.5 mycroft 287: }
1.1 cgd 288: /* cause rescan of list, it may have altered */
1.9 mycroft 289: nxtcp = nclruhead.tqh_first;
290: TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);
1.1 cgd 291: }
292: }
CVSweb <webmaster@jp.NetBSD.org>