![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to vfs_cache.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Net/2] / Net2 / kern|
Return to vfs_cache.c CVS log | Up to [Net/2] / Net2 / kern |
1.1 root 1: /*
2: * Copyright (c) 1989 The Regents of the University of California.
3: * All rights reserved.
4: *
5: * Redistribution and use in source and binary forms, with or without
6: * modification, are permitted provided that the following conditions
7: * are met:
8: * 1. Redistributions of source code must retain the above copyright
9: * notice, this list of conditions and the following disclaimer.
10: * 2. Redistributions in binary form must reproduce the above copyright
11: * notice, this list of conditions and the following disclaimer in the
12: * documentation and/or other materials provided with the distribution.
13: * 3. All advertising materials mentioning features or use of this software
14: * must display the following acknowledgement:
15: * This product includes software developed by the University of
16: * California, Berkeley and its contributors.
17: * 4. Neither the name of the University nor the names of its contributors
18: * may be used to endorse or promote products derived from this software
19: * without specific prior written permission.
20: *
21: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31: * SUCH DAMAGE.
32: *
33: * @(#)vfs_cache.c 7.8 (Berkeley) 2/28/91
34: */
35:
36: #include "param.h"
37: #include "systm.h"
38: #include "time.h"
39: #include "mount.h"
40: #include "vnode.h"
41: #include "namei.h"
42: #include "errno.h"
43: #include "malloc.h"
44:
45: /*
46: * Name caching works as follows:
47: *
48: * Names found by directory scans are retained in a cache
49: * for future reference. It is managed LRU, so frequently
50: * used names will hang around. Cache is indexed by hash value
51: * obtained from (vp, name) where vp refers to the directory
52: * containing name.
53: *
54: * For simplicity (and economy of storage), names longer than
55: * a maximum length of NCHNAMLEN are not cached; they occur
56: * infrequently in any case, and are almost never of interest.
57: *
58: * Upon reaching the last segment of a path, if the reference
59: * is for DELETE, or NOCACHE is set (rewrite), and the
60: * name is located in the cache, it will be dropped.
61: */
62:
63: /*
64: * Structures associated with name cacheing.
65: */
66: union nchash {
67: union nchash *nch_head[2];
68: struct namecache *nch_chain[2];
69: } *nchashtbl;
70: #define nch_forw nch_chain[0]
71: #define nch_back nch_chain[1]
72:
73: u_long nchash; /* size of hash table - 1 */
74: long numcache; /* number of cache entries allocated */
75: struct namecache *nchhead, **nchtail; /* LRU chain pointers */
76: struct nchstats nchstats; /* cache effectiveness statistics */
77:
78: int doingcache = 1; /* 1 => enable the cache */
79:
80: /*
81: * Look for a the name in the cache. We don't do this
82: * if the segment name is long, simply so the cache can avoid
83: * holding long names (which would either waste space, or
84: * add greatly to the complexity).
85: *
86: * Lookup is called with ni_dvp pointing to the directory to search,
87: * ni_ptr pointing to the name of the entry being sought, ni_namelen
88: * tells the length of the name, and ni_hash contains a hash of
89: * the name. If the lookup succeeds, the vnode is returned in ni_vp
90: * and a status of -1 is returned. If the lookup determines that
91: * the name does not exist (negative cacheing), a status of ENOENT
92: * is returned. If the lookup fails, a status of zero is returned.
93: */
94: cache_lookup(ndp)
95: register struct nameidata *ndp;
96: {
97: register struct vnode *dvp;
98: register struct namecache *ncp;
99: union nchash *nhp;
100:
101: if (!doingcache)
102: return (0);
103: if (ndp->ni_namelen > NCHNAMLEN) {
104: nchstats.ncs_long++;
105: ndp->ni_makeentry = 0;
106: return (0);
107: }
108: dvp = ndp->ni_dvp;
109: nhp = &nchashtbl[ndp->ni_hash & nchash];
110: for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp;
111: ncp = ncp->nc_forw) {
112: if (ncp->nc_dvp == dvp &&
113: ncp->nc_dvpid == dvp->v_id &&
114: ncp->nc_nlen == ndp->ni_namelen &&
115: !bcmp(ncp->nc_name, ndp->ni_ptr, (unsigned)ncp->nc_nlen))
116: break;
117: }
118: if (ncp == (struct namecache *)nhp) {
119: nchstats.ncs_miss++;
120: return (0);
121: }
122: if (!ndp->ni_makeentry) {
123: nchstats.ncs_badhits++;
124: } else if (ncp->nc_vp == NULL) {
125: if ((ndp->ni_nameiop & OPMASK) != CREATE) {
126: nchstats.ncs_neghits++;
127: /*
128: * Move this slot to end of LRU chain,
129: * if not already there.
130: */
131: if (ncp->nc_nxt) {
132: /* remove from LRU chain */
133: *ncp->nc_prev = ncp->nc_nxt;
134: ncp->nc_nxt->nc_prev = ncp->nc_prev;
135: /* and replace at end of it */
136: ncp->nc_nxt = NULL;
137: ncp->nc_prev = nchtail;
138: *nchtail = ncp;
139: nchtail = &ncp->nc_nxt;
140: }
141: return (ENOENT);
142: }
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: */
150: if (ncp->nc_nxt) {
151: /* remove from LRU chain */
152: *ncp->nc_prev = ncp->nc_nxt;
153: ncp->nc_nxt->nc_prev = ncp->nc_prev;
154: /* and replace at end of it */
155: ncp->nc_nxt = NULL;
156: ncp->nc_prev = nchtail;
157: *nchtail = ncp;
158: nchtail = &ncp->nc_nxt;
159: }
160: ndp->ni_vp = ncp->nc_vp;
161: return (-1);
162: }
163:
164: /*
165: * Last component and we are renaming or deleting,
166: * the cache entry is invalid, or otherwise don't
167: * want cache entry to exist.
168: */
169: /* remove from LRU chain */
170: *ncp->nc_prev = ncp->nc_nxt;
171: if (ncp->nc_nxt)
172: ncp->nc_nxt->nc_prev = ncp->nc_prev;
173: else
174: nchtail = ncp->nc_prev;
175: /* remove from hash chain */
176: remque(ncp);
177: /* insert at head of LRU list (first to grab) */
178: ncp->nc_nxt = nchhead;
179: ncp->nc_prev = &nchhead;
180: nchhead->nc_prev = &ncp->nc_nxt;
181: nchhead = ncp;
182: /* and make a dummy hash chain */
183: ncp->nc_forw = ncp;
184: ncp->nc_back = ncp;
185: return (0);
186: }
187:
188: /*
189: * Add an entry to the cache
190: */
191: cache_enter(ndp)
192: register struct nameidata *ndp;
193: {
194: register struct namecache *ncp;
195: union nchash *nhp;
196:
197: if (!doingcache)
198: return;
199: /*
200: * Free the cache slot at head of lru chain.
201: */
202: if (numcache < desiredvnodes) {
203: ncp = (struct namecache *)
204: malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
205: bzero((char *)ncp, sizeof *ncp);
206: numcache++;
207: } else if (ncp = nchhead) {
208: /* remove from lru chain */
209: *ncp->nc_prev = ncp->nc_nxt;
210: if (ncp->nc_nxt)
211: ncp->nc_nxt->nc_prev = ncp->nc_prev;
212: else
213: nchtail = ncp->nc_prev;
214: /* remove from old hash chain */
215: remque(ncp);
216: } else
217: return;
218: /* grab the vnode we just found */
219: ncp->nc_vp = ndp->ni_vp;
220: if (ndp->ni_vp)
221: ncp->nc_vpid = ndp->ni_vp->v_id;
222: else
223: ncp->nc_vpid = 0;
224: /* fill in cache info */
225: ncp->nc_dvp = ndp->ni_dvp;
226: ncp->nc_dvpid = ndp->ni_dvp->v_id;
227: ncp->nc_nlen = ndp->ni_namelen;
228: bcopy(ndp->ni_ptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
229: /* link at end of lru chain */
230: ncp->nc_nxt = NULL;
231: ncp->nc_prev = nchtail;
232: *nchtail = ncp;
233: nchtail = &ncp->nc_nxt;
234: /* and insert on hash chain */
235: nhp = &nchashtbl[ndp->ni_hash & nchash];
236: insque(ncp, nhp);
237: }
238:
239: /*
240: * Name cache initialization, from vfs_init() when we are booting
241: */
242: nchinit()
243: {
244: register union nchash *nchp;
245: long nchashsize;
246:
247: nchhead = 0;
248: nchtail = &nchhead;
249: nchashsize = roundup((desiredvnodes + 1) * sizeof *nchp / 2,
250: NBPG * CLSIZE);
251: nchashtbl = (union nchash *)malloc((u_long)nchashsize,
252: M_CACHE, M_WAITOK);
253: for (nchash = 1; nchash <= nchashsize / sizeof *nchp; nchash <<= 1)
254: /* void */;
255: nchash = (nchash >> 1) - 1;
256: for (nchp = &nchashtbl[nchash]; nchp >= nchashtbl; nchp--) {
257: nchp->nch_head[0] = nchp;
258: nchp->nch_head[1] = nchp;
259: }
260: }
261:
262: /*
263: * Cache flush, a particular vnode; called when a vnode is renamed to
264: * hide entries that would now be invalid
265: */
266: cache_purge(vp)
267: struct vnode *vp;
268: {
269: union nchash *nhp;
270: struct namecache *ncp;
271:
272: vp->v_id = ++nextvnodeid;
273: if (nextvnodeid != 0)
274: return;
275: for (nhp = &nchashtbl[nchash]; nhp >= nchashtbl; nhp--) {
276: for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp;
277: ncp = ncp->nc_forw) {
278: ncp->nc_vpid = 0;
279: ncp->nc_dvpid = 0;
280: }
281: }
282: vp->v_id = ++nextvnodeid;
283: }
284:
285: /*
286: * Cache flush, a whole filesystem; called when filesys is umounted to
287: * remove entries that would now be invalid
288: *
289: * The line "nxtcp = nchhead" near the end is to avoid potential problems
290: * if the cache lru chain is modified while we are dumping the
291: * inode. This makes the algorithm O(n^2), but do you think I care?
292: */
293: cache_purgevfs(mp)
294: struct mount *mp;
295: {
296: register struct namecache *ncp, *nxtcp;
297:
298: for (ncp = nchhead; ncp; ncp = nxtcp) {
299: nxtcp = ncp->nc_nxt;
300: if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp)
301: continue;
302: /* free the resources we had */
303: ncp->nc_vp = NULL;
304: ncp->nc_dvp = NULL;
305: remque(ncp); /* remove entry from its hash chain */
306: ncp->nc_forw = ncp; /* and make a dummy one */
307: ncp->nc_back = ncp;
308: /* delete this entry from LRU chain */
309: *ncp->nc_prev = nxtcp;
310: if (nxtcp)
311: nxtcp->nc_prev = ncp->nc_prev;
312: else
313: nchtail = ncp->nc_prev;
314: /* cause rescan of list, it may have altered */
315: nxtcp = nchhead;
316: /* put the now-free entry at head of LRU */
317: ncp->nc_nxt = nxtcp;
318: ncp->nc_prev = &nchhead;
319: nxtcp->nc_prev = &ncp->nc_nxt;
320: nchhead = ncp;
321: }
322: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.