FreeBSD/Linux Kernel Cross Reference
sys/kern/vfs_cache.c
1 /*
2 * Copyright (c) 1989, 1993
3 * The Regents of the University of California. All rights reserved.
4 * Copyright (c) 1995
5 * Poul-Henning Kamp. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. All advertising materials mentioning features or use of this software
16 * must display the following acknowledgement:
17 * This product includes software developed by the University of
18 * California, Berkeley and its contributors.
19 * 4. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 *
35 * @(#)vfs_cache.c 8.3 (Berkeley) 8/22/94
36 * $FreeBSD: src/sys/kern/vfs_cache.c,v 1.20.4.1 1999/09/05 08:15:39 peter Exp $
37 */
38
39 #include <sys/param.h>
40 #include <sys/systm.h>
41 #include <sys/kernel.h>
42 #include <sys/sysctl.h>
43 #include <sys/time.h>
44 #include <sys/mount.h>
45 #include <sys/vnode.h>
46 #include <sys/namei.h>
47 #include <sys/errno.h>
48 #include <sys/malloc.h>
49
50 #define MAXVNODEUSE 32
51
52 /*
53 * Name caching works as follows:
54 *
55 * Names found by directory scans are retained in a cache
56 * for future reference. It is managed LRU, so frequently
57 * used names will hang around. Cache is indexed by hash value
58 * obtained from (vp, name) where vp refers to the directory
59 * containing name.
60 *
61 * If it is a "negative" entry, (that we know a name to >not< exist)
62 * we point out entry at our own "nchENOENT", to avoid too much special
63 * casing in the inner loops of lookup.
64 *
65 * For simplicity (and economy of storage), names longer than
66 * a maximum length of NCHNAMLEN are not cached; they occur
67 * infrequently in any case, and are almost never of interest.
68 *
69 * Upon reaching the last segment of a path, if the reference
70 * is for DELETE, or NOCACHE is set (rewrite), and the
71 * name is located in the cache, it will be dropped.
72 */
73
74 /*
75 * Structures associated with name cacheing.
76 */
77 static LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */
78 static TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */
79 static u_long nchash; /* size of hash table */
80 struct nchstats nchstats; /* cache effectiveness statistics */
81 static struct vnode nchENOENT; /* our own "novnode" */
82 static int doingcache = 1; /* 1 => enable the cache */
83 SYSCTL_INT(_debug, OID_AUTO, vfscache, CTLFLAG_RW, &doingcache, 0, "");
84 static u_long numcache;
85 u_long numvnodes;
86
87 #ifdef NCH_STATISTICS
88 u_long nchnbr;
89 #define NCHNBR(ncp) (ncp)->nc_nbr = ++nchnbr;
90 #define NCHHIT(ncp) (ncp)->nc_hits++
91 #else
92 #define NCHNBR(ncp)
93 #define NCHHIT(ncp)
94 #endif
95
96 #define PURGE(ncp) { \
97 LIST_REMOVE(ncp, nc_hash); \
98 ncp->nc_hash.le_prev = 0; \
99 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
100 TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); }
101
102 #define TOUCH(ncp) { \
103 if (ncp->nc_lru.tqe_next == 0) { } else { \
104 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
105 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); \
106 NCHNBR(ncp); } }
107
108 /*
109 * Lookup an entry in the cache
110 *
111 * We don't do this if the segment name is long, simply so the cache
112 * can avoid holding long names (which would either waste space, or
113 * add greatly to the complexity).
114 *
115 * Lookup is called with dvp pointing to the directory to search,
116 * cnp pointing to the name of the entry being sought.
117 * If the lookup succeeds, the vnode is returned in *vpp, and a status
118 * of -1 is returned.
119 * If the lookup determines that the name does not exist (negative cacheing),
120 * a status of ENOENT is returned.
121 * If the lookup fails, a status of zero is returned.
122 */
123
124 int
125 cache_lookup(dvp, vpp, cnp)
126 struct vnode *dvp;
127 struct vnode **vpp;
128 struct componentname *cnp;
129 {
130 register struct namecache *ncp,*nnp;
131 register struct nchashhead *ncpp;
132
133 if (!doingcache) {
134 cnp->cn_flags &= ~MAKEENTRY;
135 return (0);
136 }
137
138 if (cnp->cn_namelen > NCHNAMLEN) {
139 nchstats.ncs_long++;
140 cnp->cn_flags &= ~MAKEENTRY;
141 return (0);
142 }
143
144 ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) % nchash];
145 for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
146 nnp = ncp->nc_hash.le_next;
147 /* If one of the vp's went stale, don't bother anymore. */
148 if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) ||
149 (ncp->nc_vpid != ncp->nc_vp->v_id)) {
150 nchstats.ncs_falsehits++;
151 PURGE(ncp);
152 continue;
153 }
154 /* Now that we know the vp's to be valid, is it ours ? */
155 if (ncp->nc_dvp == dvp &&
156 ncp->nc_nlen == cnp->cn_namelen &&
157 !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
158 goto found; /* Fanatism considered bad. */
159 }
160 nchstats.ncs_miss++;
161 return (0);
162
163 found:
164 NCHHIT(ncp);
165
166 /* We don't want to have an entry, so dump it */
167 if ((cnp->cn_flags & MAKEENTRY) == 0) {
168 nchstats.ncs_badhits++;
169 PURGE(ncp);
170 return (0);
171 }
172
173 /* We found a "positive" match, return the vnode */
174 if (ncp->nc_vp != &nchENOENT) {
175 nchstats.ncs_goodhits++;
176 TOUCH(ncp);
177 *vpp = ncp->nc_vp;
178 if ((*vpp)->v_usage < MAXVNODEUSE)
179 (*vpp)->v_usage++;
180 return (-1);
181 }
182
183 /* We found a negative match, and want to create it, so purge */
184 if (cnp->cn_nameiop == CREATE) {
185 nchstats.ncs_badhits++;
186 PURGE(ncp);
187 return (0);
188 }
189
190 /* The name does not exists */
191 nchstats.ncs_neghits++;
192 TOUCH(ncp);
193 return (ENOENT);
194 }
195
196 /*
197 * Add an entry to the cache.
198 */
199
200 void
201 cache_enter(dvp, vp, cnp)
202 struct vnode *dvp;
203 struct vnode *vp;
204 struct componentname *cnp;
205 {
206 register struct namecache *ncp;
207 register struct nchashhead *ncpp;
208
209 if (!doingcache)
210 return;
211
212 if (cnp->cn_namelen > NCHNAMLEN) {
213 printf("cache_enter: name too long");
214 return;
215 }
216
217 if (numcache < numvnodes) {
218 /* Add one more entry */
219 ncp = (struct namecache *)
220 malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
221 bzero((char *)ncp, sizeof *ncp);
222 numcache++;
223 } else if (ncp = nclruhead.tqh_first) {
224 /* reuse an old entry */
225 TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
226 if (ncp->nc_hash.le_prev != 0) {
227 LIST_REMOVE(ncp, nc_hash);
228 ncp->nc_hash.le_prev = 0;
229 }
230 } else {
231 /* give up */
232 return;
233 }
234
235 /* If vp is NULL this is a "negative" cache entry */
236 if (!vp)
237 vp = &nchENOENT;
238
239 /* fill in cache info */
240 ncp->nc_vp = vp;
241 if (vp->v_usage < MAXVNODEUSE)
242 ++vp->v_usage;
243 ncp->nc_vpid = vp->v_id;
244 ncp->nc_dvp = dvp;
245 ncp->nc_dvpid = dvp->v_id;
246 ncp->nc_nlen = cnp->cn_namelen;
247 bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
248 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
249 ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) % nchash];
250 LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
251 }
252
253 /*
254 * Name cache initialization, from vfs_init() when we are booting
255 */
256
257 void
258 nchinit()
259 {
260
261 TAILQ_INIT(&nclruhead);
262 nchashtbl = phashinit(desiredvnodes, M_CACHE, &nchash);
263 cache_purge(&nchENOENT); /* Initialize v_id */
264 }
265
266 /*
267 * Invalidate all entries to a particular vnode.
268 *
269 * We actually just increment the v_id, that will do it. The stale entries
270 * will be purged by lookup as they get found.
271 * If the v_id wraps around, we need to ditch the entire cache, to avoid
272 * confusion.
273 * No valid vnode will ever have (v_id == 0).
274 */
275
276 void
277 cache_purge(vp)
278 struct vnode *vp;
279 {
280 struct nchashhead *ncpp;
281 static u_long nextvnodeid;
282
283 vp->v_id = ++nextvnodeid;
284 if (nextvnodeid != 0)
285 return;
286 for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) {
287 while(ncpp->lh_first)
288 PURGE(ncpp->lh_first);
289 }
290 nchENOENT.v_id = ++nextvnodeid;
291 vp->v_id = ++nextvnodeid;
292 }
293
294 /*
295 * Flush all entries referencing a particular filesystem.
296 *
297 * Since we need to check it anyway, we will flush all the invalid
298 * entries at the same time.
299 *
300 * If we purge anything, we scan the hash-bucket again. There is only
301 * a handful of entries, so it cheap and simple.
302 */
303
304 void
305 cache_purgevfs(mp)
306 struct mount *mp;
307 {
308 struct nchashhead *ncpp;
309 struct namecache *ncp;
310
311 /* Scan hash tables for applicable entries */
312 for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) {
313 ncp = ncpp->lh_first;
314 while(ncp) {
315 if (ncp->nc_dvpid != ncp->nc_dvp->v_id ||
316 ncp->nc_vpid != ncp->nc_vp->v_id ||
317 ncp->nc_dvp->v_mount == mp) {
318 PURGE(ncp);
319 ncp = ncpp->lh_first;
320 } else {
321 ncp = ncp->nc_hash.le_next;
322 }
323 }
324 }
325 }
Cache object: 901534ebae2b84fbf0d8c47b9ade2ec6
|