![[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: *
1.1.1.2 ! root 33: * from: @(#)vfs_cache.c 7.8 (Berkeley) 2/28/91
! 34: * vfs_cache.c,v 1.2 1993/05/20 02:55:33 cgd Exp
1.1 root 35: */
36:
37: #include "param.h"
38: #include "systm.h"
39: #include "time.h"
40: #include "mount.h"
41: #include "vnode.h"
42: #include "namei.h"
43: #include "errno.h"
44: #include "malloc.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: union nchash {
68: union nchash *nch_head[2];
69: struct namecache *nch_chain[2];
70: } *nchashtbl;
71: #define nch_forw nch_chain[0]
72: #define nch_back nch_chain[1]
73:
74: u_long nchash; /* size of hash table - 1 */
75: long numcache; /* number of cache entries allocated */
76: struct namecache *nchhead, **nchtail; /* LRU chain pointers */
77: struct nchstats nchstats; /* cache effectiveness statistics */
78:
79: int doingcache = 1; /* 1 => enable the cache */
80:
81: /*
82: * Look for a the name in the cache. We don't do this
83: * if the segment name is long, simply so the cache can avoid
84: * holding long names (which would either waste space, or
85: * add greatly to the complexity).
86: *
87: * Lookup is called with ni_dvp pointing to the directory to search,
88: * ni_ptr pointing to the name of the entry being sought, ni_namelen
89: * tells the length of the name, and ni_hash contains a hash of
90: * the name. If the lookup succeeds, the vnode is returned in ni_vp
91: * and a status of -1 is returned. If the lookup determines that
92: * the name does not exist (negative cacheing), a status of ENOENT
93: * is returned. If the lookup fails, a status of zero is returned.
94: */
95: cache_lookup(ndp)
96: register struct nameidata *ndp;
97: {
98: register struct vnode *dvp;
99: register struct namecache *ncp;
100: union nchash *nhp;
101:
102: if (!doingcache)
103: return (0);
104: if (ndp->ni_namelen > NCHNAMLEN) {
105: nchstats.ncs_long++;
106: ndp->ni_makeentry = 0;
107: return (0);
108: }
109: dvp = ndp->ni_dvp;
110: nhp = &nchashtbl[ndp->ni_hash & nchash];
111: for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp;
112: ncp = ncp->nc_forw) {
113: if (ncp->nc_dvp == dvp &&
114: ncp->nc_dvpid == dvp->v_id &&
115: ncp->nc_nlen == ndp->ni_namelen &&
116: !bcmp(ncp->nc_name, ndp->ni_ptr, (unsigned)ncp->nc_nlen))
117: break;
118: }
119: if (ncp == (struct namecache *)nhp) {
120: nchstats.ncs_miss++;
121: return (0);
122: }
123: if (!ndp->ni_makeentry) {
124: nchstats.ncs_badhits++;
125: } else if (ncp->nc_vp == NULL) {
126: if ((ndp->ni_nameiop & OPMASK) != CREATE) {
127: nchstats.ncs_neghits++;
128: /*
129: * Move this slot to end of LRU chain,
130: * if not already there.
131: */
132: if (ncp->nc_nxt) {
133: /* remove from LRU chain */
134: *ncp->nc_prev = ncp->nc_nxt;
135: ncp->nc_nxt->nc_prev = ncp->nc_prev;
136: /* and replace at end of it */
137: ncp->nc_nxt = NULL;
138: ncp->nc_prev = nchtail;
139: *nchtail = ncp;
140: nchtail = &ncp->nc_nxt;
141: }
142: return (ENOENT);
143: }
144: } else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
145: nchstats.ncs_falsehits++;
146: } else {
147: nchstats.ncs_goodhits++;
148: /*
149: * move this slot to end of LRU chain, if not already there
150: */
151: if (ncp->nc_nxt) {
152: /* remove from LRU chain */
153: *ncp->nc_prev = ncp->nc_nxt;
154: ncp->nc_nxt->nc_prev = ncp->nc_prev;
155: /* and replace at end of it */
156: ncp->nc_nxt = NULL;
157: ncp->nc_prev = nchtail;
158: *nchtail = ncp;
159: nchtail = &ncp->nc_nxt;
160: }
161: ndp->ni_vp = ncp->nc_vp;
162: return (-1);
163: }
164:
165: /*
166: * Last component and we are renaming or deleting,
167: * the cache entry is invalid, or otherwise don't
168: * want cache entry to exist.
169: */
170: /* remove from LRU chain */
171: *ncp->nc_prev = ncp->nc_nxt;
172: if (ncp->nc_nxt)
173: ncp->nc_nxt->nc_prev = ncp->nc_prev;
174: else
175: nchtail = ncp->nc_prev;
176: /* remove from hash chain */
177: remque(ncp);
178: /* insert at head of LRU list (first to grab) */
179: ncp->nc_nxt = nchhead;
180: ncp->nc_prev = &nchhead;
181: nchhead->nc_prev = &ncp->nc_nxt;
182: nchhead = ncp;
183: /* and make a dummy hash chain */
184: ncp->nc_forw = ncp;
185: ncp->nc_back = ncp;
186: return (0);
187: }
188:
189: /*
190: * Add an entry to the cache
191: */
192: cache_enter(ndp)
193: register struct nameidata *ndp;
194: {
195: register struct namecache *ncp;
196: union nchash *nhp;
197:
198: if (!doingcache)
199: return;
200: /*
201: * Free the cache slot at head of lru chain.
202: */
203: if (numcache < desiredvnodes) {
204: ncp = (struct namecache *)
205: malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
206: bzero((char *)ncp, sizeof *ncp);
207: numcache++;
208: } else if (ncp = nchhead) {
209: /* remove from lru chain */
210: *ncp->nc_prev = ncp->nc_nxt;
211: if (ncp->nc_nxt)
212: ncp->nc_nxt->nc_prev = ncp->nc_prev;
213: else
214: nchtail = ncp->nc_prev;
215: /* remove from old hash chain */
216: remque(ncp);
217: } else
218: return;
219: /* grab the vnode we just found */
220: ncp->nc_vp = ndp->ni_vp;
221: if (ndp->ni_vp)
222: ncp->nc_vpid = ndp->ni_vp->v_id;
223: else
224: ncp->nc_vpid = 0;
225: /* fill in cache info */
226: ncp->nc_dvp = ndp->ni_dvp;
227: ncp->nc_dvpid = ndp->ni_dvp->v_id;
228: ncp->nc_nlen = ndp->ni_namelen;
229: bcopy(ndp->ni_ptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
230: /* link at end of lru chain */
231: ncp->nc_nxt = NULL;
232: ncp->nc_prev = nchtail;
233: *nchtail = ncp;
234: nchtail = &ncp->nc_nxt;
235: /* and insert on hash chain */
236: nhp = &nchashtbl[ndp->ni_hash & nchash];
237: insque(ncp, nhp);
238: }
239:
240: /*
241: * Name cache initialization, from vfs_init() when we are booting
242: */
243: nchinit()
244: {
245: register union nchash *nchp;
246: long nchashsize;
247:
248: nchhead = 0;
249: nchtail = &nchhead;
250: nchashsize = roundup((desiredvnodes + 1) * sizeof *nchp / 2,
251: NBPG * CLSIZE);
252: nchashtbl = (union nchash *)malloc((u_long)nchashsize,
253: M_CACHE, M_WAITOK);
254: for (nchash = 1; nchash <= nchashsize / sizeof *nchp; nchash <<= 1)
255: /* void */;
256: nchash = (nchash >> 1) - 1;
257: for (nchp = &nchashtbl[nchash]; nchp >= nchashtbl; nchp--) {
258: nchp->nch_head[0] = nchp;
259: nchp->nch_head[1] = nchp;
260: }
261: }
262:
263: /*
264: * Cache flush, a particular vnode; called when a vnode is renamed to
265: * hide entries that would now be invalid
266: */
267: cache_purge(vp)
268: struct vnode *vp;
269: {
270: union nchash *nhp;
271: struct namecache *ncp;
272:
273: vp->v_id = ++nextvnodeid;
274: if (nextvnodeid != 0)
275: return;
276: for (nhp = &nchashtbl[nchash]; nhp >= nchashtbl; nhp--) {
277: for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp;
278: ncp = ncp->nc_forw) {
279: ncp->nc_vpid = 0;
280: ncp->nc_dvpid = 0;
281: }
282: }
283: vp->v_id = ++nextvnodeid;
284: }
285:
286: /*
287: * Cache flush, a whole filesystem; called when filesys is umounted to
288: * remove entries that would now be invalid
289: *
290: * The line "nxtcp = nchhead" near the end is to avoid potential problems
291: * if the cache lru chain is modified while we are dumping the
292: * inode. This makes the algorithm O(n^2), but do you think I care?
293: */
294: cache_purgevfs(mp)
295: struct mount *mp;
296: {
297: register struct namecache *ncp, *nxtcp;
298:
299: for (ncp = nchhead; ncp; ncp = nxtcp) {
300: nxtcp = ncp->nc_nxt;
301: if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp)
302: continue;
303: /* free the resources we had */
304: ncp->nc_vp = NULL;
305: ncp->nc_dvp = NULL;
306: remque(ncp); /* remove entry from its hash chain */
307: ncp->nc_forw = ncp; /* and make a dummy one */
308: ncp->nc_back = ncp;
309: /* delete this entry from LRU chain */
310: *ncp->nc_prev = nxtcp;
311: if (nxtcp)
312: nxtcp->nc_prev = ncp->nc_prev;
313: else
314: nchtail = ncp->nc_prev;
315: /* cause rescan of list, it may have altered */
316: nxtcp = nchhead;
317: /* put the now-free entry at head of LRU */
318: ncp->nc_nxt = nxtcp;
319: ncp->nc_prev = &nchhead;
320: nxtcp->nc_prev = &ncp->nc_nxt;
321: nchhead = ncp;
322: }
323: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.