![[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 [Apple Darwin 0.x] / kernel / bsd / vfs|
Return to vfs_cache.c CVS log | Up to [Apple Darwin 0.x] / kernel / bsd / vfs |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /* Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved */
26: /*
27: * Copyright (c) 1989, 1993, 1995
28: * The Regents of the University of California. All rights reserved.
29: *
30: * This code is derived from software contributed to Berkeley by
31: * Poul-Henning Kamp of the FreeBSD Project.
32: *
33: * Redistribution and use in source and binary forms, with or without
34: * modification, are permitted provided that the following conditions
35: * are met:
36: * 1. Redistributions of source code must retain the above copyright
37: * notice, this list of conditions and the following disclaimer.
38: * 2. Redistributions in binary form must reproduce the above copyright
39: * notice, this list of conditions and the following disclaimer in the
40: * documentation and/or other materials provided with the distribution.
41: * 3. All advertising materials mentioning features or use of this software
42: * must display the following acknowledgement:
43: * This product includes software developed by the University of
44: * California, Berkeley and its contributors.
45: * 4. Neither the name of the University nor the names of its contributors
46: * may be used to endorse or promote products derived from this software
47: * without specific prior written permission.
48: *
49: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
50: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
51: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
52: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
53: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
54: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
55: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
56: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
57: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
58: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
59: * SUCH DAMAGE.
60: *
61: * from: vfs_cache.c,v 1.11 1995/03/12 02:01:20 phk Exp $
62: *
63: * @(#)vfs_cache.c 8.5 (Berkeley) 3/22/95
64: */
65: #include <mach_nbc.h>
66: #include <sys/param.h>
67: #include <sys/systm.h>
68: #include <sys/time.h>
69: #include <sys/mount.h>
70: #include <sys/vnode.h>
71: #include <sys/namei.h>
72: #include <sys/errno.h>
73: #include <sys/malloc.h>
74: #include <kern/mapfs.h>
75: /*
76: * Name caching works as follows:
77: *
78: * Names found by directory scans are retained in a cache
79: * for future reference. It is managed LRU, so frequently
80: * used names will hang around. Cache is indexed by hash value
81: * obtained from (vp, name) where vp refers to the directory
82: * containing name.
83: *
84: * If it is a "negative" entry, (i.e. for a name that is known NOT to
85: * exist) the vnode pointer will be NULL.
86: *
87: * For simplicity (and economy of storage), names longer than
88: * a maximum length of NCHNAMLEN are not cached; they occur
89: * infrequently in any case, and are almost never of interest.
90: *
91: * Upon reaching the last segment of a path, if the reference
92: * is for DELETE, or NOCACHE is set (rewrite), and the
93: * name is located in the cache, it will be dropped.
94: */
95:
96: /*
97: * Structures associated with name cacheing.
98: */
99: #define NCHHASH(dvp, cnp) \
100: (&nchashtbl[((dvp)->v_id + (cnp)->cn_hash) & nchash])
101: LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */
102: u_long nchash; /* size of hash table - 1 */
103: long numcache; /* number of cache entries allocated */
104: TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */
105: struct nchstats nchstats; /* cache effectiveness statistics */
106: u_long nextvnodeid = 0;
107: int doingcache = 1; /* 1 => enable the cache */
108:
109: /*
110: * Delete an entry from its hash list and move it to the front
111: * of the LRU list for immediate reuse.
112: */
113: #if DIAGNOSTIC
114: #define PURGE(ncp) { \
115: if (ncp->nc_hash.le_prev == 0) \
116: panic("namecache purge le_prev"); \
117: if (ncp->nc_hash.le_next == ncp) \
118: panic("namecache purge le_next"); \
119: LIST_REMOVE(ncp, nc_hash); \
120: ncp->nc_hash.le_prev = 0; \
121: TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
122: TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); \
123: }
124: #else
125: #define PURGE(ncp) { \
126: LIST_REMOVE(ncp, nc_hash); \
127: ncp->nc_hash.le_prev = 0; \
128: TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
129: TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); \
130: }
131: #endif /* DIAGNOSTIC */
132:
133: /*
134: * Move an entry that has been used to the tail of the LRU list
135: * so that it will be preserved for future use.
136: */
137: #define TOUCH(ncp) { \
138: if (ncp->nc_lru.tqe_next != 0) { \
139: TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
140: TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); \
141: } \
142: }
143:
144: /*
145: * Lookup an entry in the cache
146: *
147: * We don't do this if the segment name is long, simply so the cache
148: * can avoid holding long names (which would either waste space, or
149: * add greatly to the complexity).
150: *
151: * Lookup is called with dvp pointing to the directory to search,
152: * cnp pointing to the name of the entry being sought. If the lookup
153: * succeeds, the vnode is returned in *vpp, and a status of -1 is
154: * returned. If the lookup determines that the name does not exist
155: * (negative cacheing), a status of ENOENT is returned. If the lookup
156: * fails, a status of zero is returned.
157: */
158:
159: int
160: cache_lookup(dvp, vpp, cnp)
161: struct vnode *dvp;
162: struct vnode **vpp;
163: struct componentname *cnp;
164: {
165: register struct namecache *ncp, *nnp;
166: register struct nchashhead *ncpp;
167:
168: if (!doingcache) {
169: cnp->cn_flags &= ~MAKEENTRY;
170: return (0);
171: }
172: if (cnp->cn_namelen > NCHNAMLEN) {
173: nchstats.ncs_long++;
174: cnp->cn_flags &= ~MAKEENTRY;
175: return (0);
176: }
177:
178: ncpp = NCHHASH(dvp, cnp);
179: for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
180: nnp = ncp->nc_hash.le_next;
181: /* If one of the vp's went stale, don't bother anymore. */
182: if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) ||
183: (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id)) {
184: nchstats.ncs_falsehits++;
185: PURGE(ncp);
186: continue;
187: }
188: /* Now that we know the vp's to be valid, is it ours ? */
189: if (ncp->nc_dvp == dvp &&
190: ncp->nc_nlen == cnp->cn_namelen &&
191: !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
192: break;
193: }
194:
195: /* We failed to find an entry */
196: if (ncp == 0) {
197: nchstats.ncs_miss++;
198: return (0);
199: }
200:
201: /* We don't want to have an entry, so dump it */
202: if ((cnp->cn_flags & MAKEENTRY) == 0) {
203: nchstats.ncs_badhits++;
204: PURGE(ncp);
205: return (0);
206: }
207:
208: /* We found a "positive" match, return the vnode */
209: if (ncp->nc_vp) {
210: nchstats.ncs_goodhits++;
211: TOUCH(ncp);
212: *vpp = ncp->nc_vp;
213: return (-1);
214: }
215:
216: /* We found a negative match, and want to create it, so purge */
217: if (cnp->cn_nameiop == CREATE) {
218: nchstats.ncs_badhits++;
219: PURGE(ncp);
220: return (0);
221: }
222:
223: /*
224: * We found a "negative" match, ENOENT notifies client of this match.
225: * The nc_vpid field records whether this is a whiteout.
226: */
227: nchstats.ncs_neghits++;
228: TOUCH(ncp);
229: cnp->cn_flags |= ncp->nc_vpid;
230: return (ENOENT);
231: }
232:
233: /*
234: * Add an entry to the cache.
235: */
236: void
237: cache_enter(dvp, vp, cnp)
238: struct vnode *dvp;
239: struct vnode *vp;
240: struct componentname *cnp;
241: {
242: register struct namecache *ncp;
243: register struct nchashhead *ncpp;
244:
245: if (!doingcache)
246: return;
247:
248: #if DIAGNOSTIC
249: if (cnp->cn_namelen > NCHNAMLEN)
250: panic("cache_enter: name too long");
251: #endif
252:
253: /*
254: * We allocate a new entry if we are less than the maximum
255: * allowed and the one at the front of the LRU list is in use.
256: * Otherwise we use the one at the front of the LRU list.
257: */
258: if (numcache < desiredvnodes &&
259: ((ncp = nclruhead.tqh_first) == NULL ||
260: ncp->nc_hash.le_prev != 0)) {
261: /* Add one more entry */
262: ncp = (struct namecache *)
263: _MALLOC_ZONE((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
264: numcache++;
265: } else if (ncp = nclruhead.tqh_first) {
266: /* reuse an old entry */
267: TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
268: if (ncp->nc_hash.le_prev != 0) {
269: #if DIAGNOSTIC
270: if (ncp->nc_hash.le_next == ncp)
271: panic("cache_enter: le_next");
272: #endif
273: LIST_REMOVE(ncp, nc_hash);
274: ncp->nc_hash.le_prev = 0;
275: }
276: } else {
277: /* give up */
278: return;
279: }
280:
281: /*
282: * Fill in cache info, if vp is NULL this is a "negative" cache entry.
283: * For negative entries, we have to record whether it is a whiteout.
284: * the whiteout flag is stored in the nc_vpid field which is
285: * otherwise unused.
286: */
287: ncp->nc_vp = vp;
288: if (vp)
289: ncp->nc_vpid = vp->v_id;
290: else
291: ncp->nc_vpid = cnp->cn_flags & ISWHITEOUT;
292: ncp->nc_dvp = dvp;
293: ncp->nc_dvpid = dvp->v_id;
294: ncp->nc_nlen = cnp->cn_namelen;
295: bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
296: TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
297: ncpp = NCHHASH(dvp, cnp);
298: #if DIAGNOSTIC
299: {
300: register struct namecache *p;
301:
302: for (p = ncpp->lh_first; p != 0; p = p->nc_hash.le_next)
303: if (p == ncp)
304: panic("cache_enter: duplicate");
305: }
306: #endif
307: LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
308: }
309:
310: /*
311: * Name cache initialization, from vfs_init() when we are booting
312: */
313: void
314: nchinit()
315: {
316:
317: TAILQ_INIT(&nclruhead);
318: nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash);
319: }
320:
321: /*
322: * Invalidate a all entries to particular vnode.
323: *
324: * We actually just increment the v_id, that will do it. The entries will
325: * be purged by lookup as they get found. If the v_id wraps around, we
326: * need to ditch the entire cache, to avoid confusion. No valid vnode will
327: * ever have (v_id == 0).
328: */
329: void
330: cache_purge(vp)
331: struct vnode *vp;
332: {
333: struct namecache *ncp;
334: struct nchashhead *ncpp;
335:
336: vp->v_id = ++nextvnodeid;
337: if (nextvnodeid != 0)
338: return;
339: for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
340: while (ncp = ncpp->lh_first)
341: PURGE(ncp);
342: }
343: vp->v_id = ++nextvnodeid;
344: #if MACH_NBC
345: /* ?? */
346: /* mapfs_uncache(vp); */
347: #endif /* MACH_NBC */
348: }
349:
350: /*
351: * Flush all entries referencing a particular filesystem.
352: *
353: * Since we need to check it anyway, we will flush all the invalid
354: * entriess at the same time.
355: */
356: void
357: cache_purgevfs(mp)
358: struct mount *mp;
359: {
360: struct nchashhead *ncpp;
361: struct namecache *ncp, *nnp;
362:
363: /* Scan hash tables for applicable entries */
364: for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
365: for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
366: nnp = ncp->nc_hash.le_next;
367: if (ncp->nc_dvpid != ncp->nc_dvp->v_id ||
368: (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id) ||
369: ncp->nc_dvp->v_mount == mp) {
370: PURGE(ncp);
371: }
372: }
373: }
374: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.