FreeBSD/Linux Kernel Cross Reference
sys/kern/vfs_cache.c
1 /*
2 * Copyright (c) 1989, 1993, 1995
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Poul-Henning Kamp of the FreeBSD Project.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 *
36 * @(#)vfs_cache.c 8.5 (Berkeley) 3/22/95
37 * $FreeBSD$
38 */
39
40 #include <sys/param.h>
41 #include <sys/systm.h>
42 #include <sys/kernel.h>
43 #include <sys/sysctl.h>
44 #include <sys/mount.h>
45 #include <sys/vnode.h>
46 #include <sys/namei.h>
47 #include <sys/malloc.h>
48
49
50 /*
51 * Name caching works as follows:
52 *
53 * Names found by directory scans are retained in a cache
54 * for future reference. It is managed LRU, so frequently
55 * used names will hang around. Cache is indexed by hash value
56 * obtained from (vp, name) where vp refers to the directory
57 * containing name.
58 *
59 * If it is a "negative" entry, (i.e. for a name that is known NOT to
60 * exist) the vnode pointer will be NULL.
61 *
62 * Upon reaching the last segment of a path, if the reference
63 * is for DELETE, or NOCACHE is set (rewrite), and the
64 * name is located in the cache, it will be dropped.
65 */
66
67 /*
68 * Structures associated with name cacheing.
69 */
70 #define NCHHASH(dvp, cnp) \
71 (&nchashtbl[((dvp)->v_id + (cnp)->cn_hash) & nchash])
72 static LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */
73 static TAILQ_HEAD(, namecache) ncneg; /* Hash Table */
74 static u_long nchash; /* size of hash table */
75 SYSCTL_INT(_debug, OID_AUTO, nchash, CTLFLAG_RD, &nchash, 0, "");
76 static u_long ncnegfactor = 16; /* ratio of negative entries */
77 SYSCTL_INT(_debug, OID_AUTO, ncnegfactor, CTLFLAG_RW, &ncnegfactor, 0, "");
78 static u_long numneg; /* number of cache entries allocated */
79 SYSCTL_INT(_debug, OID_AUTO, numneg, CTLFLAG_RD, &numneg, 0, "");
80 static u_long numcache; /* number of cache entries allocated */
81 SYSCTL_INT(_debug, OID_AUTO, numcache, CTLFLAG_RD, &numcache, 0, "");
82 struct nchstats nchstats; /* cache effectiveness statistics */
83
84 static int doingcache = 1; /* 1 => enable the cache */
85 SYSCTL_INT(_debug, OID_AUTO, vfscache, CTLFLAG_RW, &doingcache, 0, "");
86 SYSCTL_INT(_debug, OID_AUTO, vnsize, CTLFLAG_RD, 0, sizeof(struct vnode), "");
87 SYSCTL_INT(_debug, OID_AUTO, ncsize, CTLFLAG_RD, 0, sizeof(struct namecache), "");
88
89 /*
90 * The new name cache statistics
91 */
92 SYSCTL_NODE(_vfs, OID_AUTO, cache, CTLFLAG_RW, 0, "Name cache statistics");
93 #define STATNODE(mode, name, var) \
94 SYSCTL_INT(_vfs_cache, OID_AUTO, name, mode, var, 0, "");
95 STATNODE(CTLFLAG_RD, numneg, &numneg);
96 STATNODE(CTLFLAG_RD, numcache, &numcache);
97 static u_long numcalls; STATNODE(CTLFLAG_RD, numcalls, &numcalls);
98 static u_long dothits; STATNODE(CTLFLAG_RD, dothits, &dothits);
99 static u_long dotdothits; STATNODE(CTLFLAG_RD, dotdothits, &dotdothits);
100 static u_long numchecks; STATNODE(CTLFLAG_RD, numchecks, &numchecks);
101 static u_long nummiss; STATNODE(CTLFLAG_RD, nummiss, &nummiss);
102 static u_long nummisszap; STATNODE(CTLFLAG_RD, nummisszap, &nummisszap);
103 static u_long numposzaps; STATNODE(CTLFLAG_RD, numposzaps, &numposzaps);
104 static u_long numposhits; STATNODE(CTLFLAG_RD, numposhits, &numposhits);
105 static u_long numnegzaps; STATNODE(CTLFLAG_RD, numnegzaps, &numnegzaps);
106 static u_long numneghits; STATNODE(CTLFLAG_RD, numneghits, &numneghits);
107
108 /*
109 * Max aliases to a name, avoids DoS of the system via hardlinks
110 */
111 static int ncmaxaliases = 4;
112 SYSCTL_INT(_vfs_cache, OID_AUTO, maxaliases, CTLFLAG_RW, &ncmaxaliases, 4,
113 "Maximum amount of cache entries that can point to a particular file");
114
115 static void cache_zap __P((struct namecache *ncp));
116
117 /*
118 * Flags in namecache.nc_flag
119 */
120 #define NCF_WHITE 1
121 /*
122 * Delete an entry from its hash list and move it to the front
123 * of the LRU list for immediate reuse.
124 */
125 static void
126 cache_zap(ncp)
127 struct namecache *ncp;
128 {
129 LIST_REMOVE(ncp, nc_hash);
130 LIST_REMOVE(ncp, nc_src);
131 if (LIST_EMPTY(&ncp->nc_dvp->v_cache_src))
132 vdrop(ncp->nc_dvp);
133 if (ncp->nc_vp) {
134 TAILQ_REMOVE(&ncp->nc_vp->v_cache_dst, ncp, nc_dst);
135 ncp->nc_vp->v_cache_dst_count--;
136 } else {
137 TAILQ_REMOVE(&ncneg, ncp, nc_dst);
138 numneg--;
139 }
140 numcache--;
141 free(ncp, M_CACHE);
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;
166
167 if (!doingcache) {
168 cnp->cn_flags &= ~MAKEENTRY;
169 return (0);
170 }
171
172 numcalls++;
173
174 if (cnp->cn_nameptr[0] == '.') {
175 if (cnp->cn_namelen == 1) {
176 *vpp = dvp;
177 dothits++;
178 return (-1);
179 }
180 if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.') {
181 dotdothits++;
182 if (dvp->v_dd->v_id != dvp->v_ddid ||
183 (cnp->cn_flags & MAKEENTRY) == 0) {
184 dvp->v_ddid = 0;
185 return (0);
186 }
187 *vpp = dvp->v_dd;
188 return (-1);
189 }
190 }
191
192 LIST_FOREACH(ncp, (NCHHASH(dvp, cnp)), nc_hash) {
193 numchecks++;
194 if (ncp->nc_dvp == dvp && ncp->nc_nlen == cnp->cn_namelen &&
195 !bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen))
196 break;
197 }
198
199 /* We failed to find an entry */
200 if (ncp == 0) {
201 if ((cnp->cn_flags & MAKEENTRY) == 0) {
202 nummisszap++;
203 } else {
204 nummiss++;
205 }
206 nchstats.ncs_miss++;
207 return (0);
208 }
209
210 /* We don't want to have an entry, so dump it */
211 if ((cnp->cn_flags & MAKEENTRY) == 0) {
212 numposzaps++;
213 nchstats.ncs_badhits++;
214 cache_zap(ncp);
215 return (0);
216 }
217
218 /* We found a "positive" match, return the vnode */
219 if (ncp->nc_vp) {
220 numposhits++;
221 nchstats.ncs_goodhits++;
222 *vpp = ncp->nc_vp;
223 return (-1);
224 }
225
226 /* We found a negative match, and want to create it, so purge */
227 if (cnp->cn_nameiop == CREATE) {
228 numnegzaps++;
229 nchstats.ncs_badhits++;
230 cache_zap(ncp);
231 return (0);
232 }
233
234 numneghits++;
235 /*
236 * We found a "negative" match, ENOENT notifies client of this match.
237 * The nc_vpid field records whether this is a whiteout.
238 */
239 TAILQ_REMOVE(&ncneg, ncp, nc_dst);
240 TAILQ_INSERT_TAIL(&ncneg, ncp, nc_dst);
241 nchstats.ncs_neghits++;
242 if (ncp->nc_flag & NCF_WHITE)
243 cnp->cn_flags |= ISWHITEOUT;
244 return (ENOENT);
245 }
246
247 /*
248 * Add an entry to the cache.
249 */
250 void
251 cache_enter(dvp, vp, cnp)
252 struct vnode *dvp;
253 struct vnode *vp;
254 struct componentname *cnp;
255 {
256 register struct namecache *ncp;
257 register struct nchashhead *ncpp;
258
259 if (!doingcache)
260 return;
261
262 if (cnp->cn_nameptr[0] == '.') {
263 if (cnp->cn_namelen == 1) {
264 return;
265 }
266 if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.') {
267 if (vp) {
268 dvp->v_dd = vp;
269 dvp->v_ddid = vp->v_id;
270 } else {
271 dvp->v_dd = dvp;
272 dvp->v_ddid = 0;
273 }
274 return;
275 }
276 }
277
278 ncp = (struct namecache *)
279 malloc(sizeof *ncp + cnp->cn_namelen, M_CACHE, M_WAITOK);
280 bzero((char *)ncp, sizeof *ncp);
281 numcache++;
282 if (!vp) {
283 numneg++;
284 ncp->nc_flag = cnp->cn_flags & ISWHITEOUT ? NCF_WHITE : 0;
285 } else if (vp->v_type == VDIR) {
286 vp->v_dd = dvp;
287 vp->v_ddid = dvp->v_id;
288 }
289
290 /*
291 * Fill in cache info, if vp is NULL this is a "negative" cache entry.
292 * For negative entries, we have to record whether it is a whiteout.
293 * the whiteout flag is stored in the nc_vpid field which is
294 * otherwise unused.
295 */
296 ncp->nc_vp = vp;
297 ncp->nc_dvp = dvp;
298 ncp->nc_nlen = cnp->cn_namelen;
299 bcopy(cnp->cn_nameptr, ncp->nc_name, ncp->nc_nlen);
300 ncpp = NCHHASH(dvp, cnp);
301 LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
302 if (LIST_EMPTY(&dvp->v_cache_src))
303 vhold(dvp);
304 LIST_INSERT_HEAD(&dvp->v_cache_src, ncp, nc_src);
305 if (vp) {
306 while (vp->v_cache_dst_count > ncmaxaliases)
307 cache_zap(TAILQ_LAST(&vp->v_cache_dst, cdst));
308 vp->v_cache_dst_count++;
309 TAILQ_INSERT_HEAD(&vp->v_cache_dst, ncp, nc_dst);
310 } else {
311 TAILQ_INSERT_TAIL(&ncneg, ncp, nc_dst);
312 }
313 if (numneg*ncnegfactor > numcache) {
314 ncp = TAILQ_FIRST(&ncneg);
315 cache_zap(ncp);
316 }
317 }
318
319 /*
320 * Name cache initialization, from vfs_init() when we are booting
321 */
322 void
323 nchinit()
324 {
325
326 TAILQ_INIT(&ncneg);
327 nchashtbl = hashinit(desiredvnodes*2, M_CACHE, &nchash);
328 }
329
330 /*
331 * Invalidate all entries to a particular vnode.
332 *
333 * Remove all entries in the namecache relating to this vnode and
334 * change the v_id. We take the v_id from a global counter, since
335 * it becomes a handy sequence number in crash-dumps that way.
336 * No valid vnode will ever have (v_id == 0).
337 *
338 * XXX: Only time and the size of v_id prevents this from failing:
339 * XXX: In theory we should hunt down all (struct vnode*, v_id)
340 * XXX: soft references and nuke them, at least on the global
341 * XXX: v_id wraparound. The period of resistance can be extended
342 * XXX: by incrementing each vnodes v_id individually instead of
343 * XXX: using the global v_id.
344 */
345
346 void
347 cache_purge(vp)
348 struct vnode *vp;
349 {
350 static u_long nextid;
351
352 while (!LIST_EMPTY(&vp->v_cache_src))
353 cache_zap(LIST_FIRST(&vp->v_cache_src));
354 while (!TAILQ_EMPTY(&vp->v_cache_dst))
355 cache_zap(TAILQ_FIRST(&vp->v_cache_dst));
356
357 do
358 nextid++;
359 while (nextid == vp->v_id || !nextid);
360 vp->v_id = nextid;
361 vp->v_dd = vp;
362 vp->v_ddid = 0;
363 }
364
365 /*
366 * Flush all entries referencing a particular filesystem.
367 *
368 * Since we need to check it anyway, we will flush all the invalid
369 * entries at the same time.
370 */
371 void
372 cache_purgevfs(mp)
373 struct mount *mp;
374 {
375 struct nchashhead *ncpp;
376 struct namecache *ncp, *nnp;
377
378 /* Scan hash tables for applicable entries */
379 for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
380 for (ncp = LIST_FIRST(ncpp); ncp != 0; ncp = nnp) {
381 nnp = LIST_NEXT(ncp, nc_hash);
382 if (ncp->nc_dvp->v_mount == mp) {
383 cache_zap(ncp);
384 }
385 }
386 }
387 }
388
389 /*
390 * Perform canonical checks and cache lookup and pass on to filesystem
391 * through the vop_cachedlookup only if needed.
392 */
393
394 int
395 vfs_cache_lookup(ap)
396 struct vop_lookup_args /* {
397 struct vnode *a_dvp;
398 struct vnode **a_vpp;
399 struct componentname *a_cnp;
400 } */ *ap;
401 {
402 struct vnode *vdp;
403 struct vnode *pdp;
404 int lockparent;
405 int error;
406 struct vnode **vpp = ap->a_vpp;
407 struct componentname *cnp = ap->a_cnp;
408 struct ucred *cred = cnp->cn_cred;
409 int flags = cnp->cn_flags;
410 struct proc *p = cnp->cn_proc;
411 u_long vpid; /* capability number of vnode */
412
413 *vpp = NULL;
414 vdp = ap->a_dvp;
415 lockparent = flags & LOCKPARENT;
416
417 if (vdp->v_type != VDIR)
418 return (ENOTDIR);
419
420 if ((flags & ISLASTCN) && (vdp->v_mount->mnt_flag & MNT_RDONLY) &&
421 (cnp->cn_nameiop == DELETE || cnp->cn_nameiop == RENAME))
422 return (EROFS);
423
424 error = VOP_ACCESS(vdp, VEXEC, cred, cnp->cn_proc);
425
426 if (error)
427 return (error);
428
429 error = cache_lookup(vdp, vpp, cnp);
430
431 if (!error)
432 return (VOP_CACHEDLOOKUP(ap->a_dvp, ap->a_vpp, ap->a_cnp));
433
434 if (error == ENOENT)
435 return (error);
436
437 pdp = vdp;
438 vdp = *vpp;
439 vpid = vdp->v_id;
440 if (pdp == vdp) { /* lookup on "." */
441 VREF(vdp);
442 error = 0;
443 } else if (flags & ISDOTDOT) {
444 VOP_UNLOCK(pdp, 0, p);
445 error = vget(vdp, LK_EXCLUSIVE, p);
446 if (!error && lockparent && (flags & ISLASTCN))
447 error = vn_lock(pdp, LK_EXCLUSIVE, p);
448 } else {
449 error = vget(vdp, LK_EXCLUSIVE, p);
450 if (!lockparent || error || !(flags & ISLASTCN))
451 VOP_UNLOCK(pdp, 0, p);
452 }
453 /*
454 * Check that the capability number did not change
455 * while we were waiting for the lock.
456 */
457 if (!error) {
458 if (vpid == vdp->v_id)
459 return (0);
460 vput(vdp);
461 if (lockparent && pdp != vdp && (flags & ISLASTCN))
462 VOP_UNLOCK(pdp, 0, p);
463 }
464 error = vn_lock(pdp, LK_EXCLUSIVE, p);
465 if (error)
466 return (error);
467 return (VOP_CACHEDLOOKUP(ap->a_dvp, ap->a_vpp, ap->a_cnp));
468 }
Cache object: ca81b45dee981fe4e1fa5e59cb6dbd5b
|