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