![[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 XNU] / XNU / bsd / vfs|
Return to vfs_cache.c CVS log | Up to [Apple XNU] / XNU / bsd / vfs |
1.1 root 1: /*
2: * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * The contents of this file constitute Original Code as defined in and
7: * are subject to the Apple Public Source License Version 1.1 (the
8: * "License"). You may not use this file except in compliance with the
9: * License. Please obtain a copy of the License at
10: * http://www.apple.com/publicsource and read it before using this file.
11: *
12: * This Original Code and all software distributed under the License are
13: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17: * License for the specific language governing rights and limitations
18: * under the License.
19: *
20: * @APPLE_LICENSE_HEADER_END@
21: */
22: /* Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved */
23: /*
24: * Copyright (c) 1989, 1993, 1995
25: * The Regents of the University of California. All rights reserved.
26: *
27: * This code is derived from software contributed to Berkeley by
28: * Poul-Henning Kamp of the FreeBSD Project.
29: *
30: * Redistribution and use in source and binary forms, with or without
31: * modification, are permitted provided that the following conditions
32: * are met:
33: * 1. Redistributions of source code must retain the above copyright
34: * notice, this list of conditions and the following disclaimer.
35: * 2. Redistributions in binary form must reproduce the above copyright
36: * notice, this list of conditions and the following disclaimer in the
37: * documentation and/or other materials provided with the distribution.
38: * 3. All advertising materials mentioning features or use of this software
39: * must display the following acknowledgement:
40: * This product includes software developed by the University of
41: * California, Berkeley and its contributors.
42: * 4. Neither the name of the University nor the names of its contributors
43: * may be used to endorse or promote products derived from this software
44: * without specific prior written permission.
45: *
46: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
47: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
48: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
49: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
50: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
51: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
52: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
53: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
54: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
55: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
56: * SUCH DAMAGE.
57: *
58: *
59: * @(#)vfs_cache.c 8.5 (Berkeley) 3/22/95
60: */
61: #include <mach_nbc.h>
62: #include <sys/param.h>
63: #include <sys/systm.h>
64: #include <sys/time.h>
65: #include <sys/mount.h>
66: #include <sys/vnode.h>
67: #include <sys/namei.h>
68: #include <sys/errno.h>
69: #include <sys/malloc.h>
70: #include <kern/mapfs.h>
71: /*
72: * Name caching works as follows:
73: *
74: * Names found by directory scans are retained in a cache
75: * for future reference. It is managed LRU, so frequently
76: * used names will hang around. Cache is indexed by hash value
77: * obtained from (vp, name) where vp refers to the directory
78: * containing name.
79: *
80: * If it is a "negative" entry, (i.e. for a name that is known NOT to
81: * exist) the vnode pointer will be NULL.
82: *
83: * For simplicity (and economy of storage), names longer than
84: * a maximum length of NCHNAMLEN are not cached; they occur
85: * infrequently in any case, and are almost never of interest.
86: *
87: * Upon reaching the last segment of a path, if the reference
88: * is for DELETE, or NOCACHE is set (rewrite), and the
89: * name is located in the cache, it will be dropped.
90: */
91:
92: /*
93: * Structures associated with name cacheing.
94: */
95: #define NCHHASH(dvp, cnp) \
96: (&nchashtbl[((dvp)->v_id + (cnp)->cn_hash) & nchash])
97: LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */
98: u_long nchash; /* size of hash table - 1 */
99: long numcache; /* number of cache entries allocated */
100: TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */
101: struct nchstats nchstats; /* cache effectiveness statistics */
102: u_long nextvnodeid = 0;
103: int doingcache = 1; /* 1 => enable the cache */
104:
105: /*
106: * Delete an entry from its hash list and move it to the front
107: * of the LRU list for immediate reuse.
108: */
109: #if DIAGNOSTIC
110: #define PURGE(ncp) { \
111: if (ncp->nc_hash.le_prev == 0) \
112: panic("namecache purge le_prev"); \
113: if (ncp->nc_hash.le_next == ncp) \
114: panic("namecache purge le_next"); \
115: LIST_REMOVE(ncp, nc_hash); \
116: ncp->nc_hash.le_prev = 0; \
117: TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
118: TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); \
119: }
120: #else
121: #define PURGE(ncp) { \
122: LIST_REMOVE(ncp, nc_hash); \
123: ncp->nc_hash.le_prev = 0; \
124: TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
125: TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); \
126: }
127: #endif /* DIAGNOSTIC */
128:
129: /*
130: * Move an entry that has been used to the tail of the LRU list
131: * so that it will be preserved for future use.
132: */
133: #define TOUCH(ncp) { \
134: if (ncp->nc_lru.tqe_next != 0) { \
135: TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
136: TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); \
137: } \
138: }
139:
140: /*
141: * Lookup an entry in the cache
142: *
143: * We don't do this if the segment name is long, simply so the cache
144: * can avoid holding long names (which would either waste space, or
145: * add greatly to the complexity).
146: *
147: * Lookup is called with dvp pointing to the directory to search,
148: * cnp pointing to the name of the entry being sought. If the lookup
149: * succeeds, the vnode is returned in *vpp, and a status of -1 is
150: * returned. If the lookup determines that the name does not exist
151: * (negative cacheing), a status of ENOENT is returned. If the lookup
152: * fails, a status of zero is returned.
153: */
154:
155: int
156: cache_lookup(dvp, vpp, cnp)
157: struct vnode *dvp;
158: struct vnode **vpp;
159: struct componentname *cnp;
160: {
161: register struct namecache *ncp, *nnp;
162: register struct nchashhead *ncpp;
163:
164: if (!doingcache) {
165: cnp->cn_flags &= ~MAKEENTRY;
166: return (0);
167: }
168: if (cnp->cn_namelen > NCHNAMLEN) {
169: nchstats.ncs_long++;
170: cnp->cn_flags &= ~MAKEENTRY;
171: return (0);
172: }
173:
174: ncpp = NCHHASH(dvp, cnp);
175: for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
176: nnp = ncp->nc_hash.le_next;
177: /* If one of the vp's went stale, don't bother anymore. */
178: if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) ||
179: (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id)) {
180: nchstats.ncs_falsehits++;
181: PURGE(ncp);
182: continue;
183: }
184: /* Now that we know the vp's to be valid, is it ours ? */
185: if (ncp->nc_dvp == dvp &&
186: ncp->nc_nlen == cnp->cn_namelen &&
187: !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
188: break;
189: }
190:
191: /* We failed to find an entry */
192: if (ncp == 0) {
193: nchstats.ncs_miss++;
194: return (0);
195: }
196:
197: /* We don't want to have an entry, so dump it */
198: if ((cnp->cn_flags & MAKEENTRY) == 0) {
199: nchstats.ncs_badhits++;
200: PURGE(ncp);
201: return (0);
202: }
203:
204: /* We found a "positive" match, return the vnode */
205: if (ncp->nc_vp) {
206: nchstats.ncs_goodhits++;
207: TOUCH(ncp);
208: *vpp = ncp->nc_vp;
209: return (-1);
210: }
211:
212: /* We found a negative match, and want to create it, so purge */
213: if (cnp->cn_nameiop == CREATE) {
214: nchstats.ncs_badhits++;
215: PURGE(ncp);
216: return (0);
217: }
218:
219: /*
220: * We found a "negative" match, ENOENT notifies client of this match.
221: * The nc_vpid field records whether this is a whiteout.
222: */
223: nchstats.ncs_neghits++;
224: TOUCH(ncp);
225: cnp->cn_flags |= ncp->nc_vpid;
226: return (ENOENT);
227: }
228:
229: /*
230: * Add an entry to the cache.
231: */
232: void
233: cache_enter(dvp, vp, cnp)
234: struct vnode *dvp;
235: struct vnode *vp;
236: struct componentname *cnp;
237: {
238: register struct namecache *ncp;
239: register struct nchashhead *ncpp;
240:
241: if (!doingcache)
242: return;
243:
244: /*
245: * If an entry that is too long, is entered, bad things happen.
246: * cache_lookup acts as the sentinel to make sure longer names
247: * are not stored. This here will prevent outsiders from doing
248: * something that is unexpected.
249: */
250: if (cnp->cn_namelen > NCHNAMLEN)
251: panic("cache_enter: name too long");
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.