xref: /netbsd/sys/kern/vfs_cache.c (revision c4a72b64) 
1 /*	$NetBSD: vfs_cache.c,v 1.37 2002/09/04 01:32:47 matt Exp $	*/
2 
3 /*
4  * Copyright (c) 1989, 1993
5  *	The Regents of the University of California.  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  */
37 
38 #include <sys/cdefs.h>
39 __KERNEL_RCSID(0, "$NetBSD: vfs_cache.c,v 1.37 2002/09/04 01:32:47 matt Exp $");
40 
41 #include "opt_ddb.h"
42 #include "opt_revcache.h"
43 
44 #include <sys/param.h>
45 #include <sys/systm.h>
46 #include <sys/time.h>
47 #include <sys/mount.h>
48 #include <sys/vnode.h>
49 #include <sys/namei.h>
50 #include <sys/errno.h>
51 #include <sys/malloc.h>
52 #include <sys/pool.h>
53 
54 /*
55  * Name caching works as follows:
56  *
57  * Names found by directory scans are retained in a cache
58  * for future reference.  It is managed LRU, so frequently
59  * used names will hang around.  Cache is indexed by hash value
60  * obtained from (dvp, name) where dvp refers to the directory
61  * containing name.
62  *
63  * For simplicity (and economy of storage), names longer than
64  * a maximum length of NCHNAMLEN are not cached; they occur
65  * infrequently in any case, and are almost never of interest.
66  *
67  * Upon reaching the last segment of a path, if the reference
68  * is for DELETE, or NOCACHE is set (rewrite), and the
69  * name is located in the cache, it will be dropped.
70  * The entry is dropped also when it was not possible to lock
71  * the cached vnode, either because vget() failed or the generation
72  * number has changed while waiting for the lock.
73  */
74 
75 /*
76  * Structures associated with name cacheing.
77  */
78 LIST_HEAD(nchashhead, namecache) *nchashtbl;
79 u_long	nchash;				/* size of hash table - 1 */
80 long	numcache;			/* number of cache entries allocated */
81 #define	NCHASH(cnp, dvp)	(((cnp)->cn_hash ^ (dvp)->v_id) & nchash)
82 
83 LIST_HEAD(ncvhashhead, namecache) *ncvhashtbl;
84 u_long	ncvhash;			/* size of hash table - 1 */
85 #define	NCVHASH(vp)		((vp)->v_id & ncvhash)
86 
87 TAILQ_HEAD(, namecache) nclruhead;		/* LRU chain */
88 struct	nchstats nchstats;		/* cache effectiveness statistics */
89 
90 struct pool namecache_pool;
91 
92 int doingcache = 1;			/* 1 => enable the cache */
93 
94 /*
95  * Look for a the name in the cache. We don't do this
96  * if the segment name is long, simply so the cache can avoid
97  * holding long names (which would either waste space, or
98  * add greatly to the complexity).
99  *
100  * Lookup is called with ni_dvp pointing to the directory to search,
101  * ni_ptr pointing to the name of the entry being sought, ni_namelen
102  * tells the length of the name, and ni_hash contains a hash of
103  * the name. If the lookup succeeds, the vnode is locked, stored in ni_vp
104  * and a status of zero is returned. If the locking fails for whatever
105  * reason, the vnode is unlocked and the error is returned to caller.
106  * If the lookup determines that the name does not exist (negative cacheing),
107  * a status of ENOENT is returned. If the lookup fails, a status of -1
108  * is returned.
109  */
110 int
111 cache_lookup(struct vnode *dvp, struct vnode **vpp, struct componentname *cnp)
112 {
113 	struct namecache *ncp;
114 	struct nchashhead *ncpp;
115 	struct vnode *vp;
116 	u_long vpid;
117 	int error;
118 
119 	if (!doingcache) {
120 		cnp->cn_flags &= ~MAKEENTRY;
121 		*vpp = NULL;
122 		return (-1);
123 	}
124 	if (cnp->cn_namelen > NCHNAMLEN) {
125 		nchstats.ncs_long++;
126 		cnp->cn_flags &= ~MAKEENTRY;
127 		*vpp = NULL;
128 		return (-1);
129 	}
130 	ncpp = &nchashtbl[NCHASH(cnp, dvp)];
131 	LIST_FOREACH(ncp, ncpp, nc_hash) {
132 		if (ncp->nc_dvp == dvp &&
133 		    ncp->nc_dvpid == dvp->v_id &&
134 		    ncp->nc_nlen == cnp->cn_namelen &&
135 		    !memcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
136 			break;
137 	}
138 	if (ncp == 0) {
139 		nchstats.ncs_miss++;
140 		*vpp = NULL;
141 		return (-1);
142 	}
143 	if ((cnp->cn_flags & MAKEENTRY) == 0) {
144 		nchstats.ncs_badhits++;
145 		goto remove;
146 	} else if (ncp->nc_vp == NULL) {
147 		/*
148 		 * Restore the ISWHITEOUT flag saved earlier.
149 		 */
150 		cnp->cn_flags |= ncp->nc_vpid;
151 		if (cnp->cn_nameiop != CREATE ||
152 		    (cnp->cn_flags & ISLASTCN) == 0) {
153 			nchstats.ncs_neghits++;
154 			/*
155 			 * Move this slot to end of LRU chain,
156 			 * if not already there.
157 			 */
158 			if (TAILQ_NEXT(ncp, nc_lru) != 0) {
159 				TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
160 				TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
161 			}
162 			return (ENOENT);
163 		} else {
164 			nchstats.ncs_badhits++;
165 			goto remove;
166 		}
167 	} else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
168 		nchstats.ncs_falsehits++;
169 		goto remove;
170 	}
171 
172 	vp = ncp->nc_vp;
173 	vpid = vp->v_id;
174 	if (vp == dvp) {	/* lookup on "." */
175 		VREF(dvp);
176 		error = 0;
177 	} else if (cnp->cn_flags & ISDOTDOT) {
178 		VOP_UNLOCK(dvp, 0);
179 		cnp->cn_flags |= PDIRUNLOCK;
180 		error = vget(vp, LK_EXCLUSIVE);
181 		/*
182 		 * If the above vget() succeeded and both LOCKPARENT and
183 		 * ISLASTCN is set, lock the directory vnode as well.
184 		 */
185 		if (!error && (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) == 0) {
186 			if ((error = vn_lock(dvp, LK_EXCLUSIVE)) != 0) {
187 				vput(vp);
188 				return (error);
189 			}
190 			cnp->cn_flags &= ~PDIRUNLOCK;
191 		}
192 	} else {
193 		error = vget(vp, LK_EXCLUSIVE);
194 		/*
195 		 * If the above vget() failed or either of LOCKPARENT or
196 		 * ISLASTCN is set, unlock the directory vnode.
197 		 */
198 		if (error || (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) {
199 			VOP_UNLOCK(dvp, 0);
200 			cnp->cn_flags |= PDIRUNLOCK;
201 		}
202 	}
203 
204 	/*
205 	 * Check that the lock succeeded, and that the capability number did
206 	 * not change while we were waiting for the lock.
207 	 */
208 	if (error || vpid != vp->v_id) {
209 		if (!error) {
210 			vput(vp);
211 			nchstats.ncs_falsehits++;
212 		} else
213 			nchstats.ncs_badhits++;
214 		/*
215 		 * The parent needs to be locked when we return to VOP_LOOKUP().
216 		 * The `.' case here should be extremely rare (if it can happen
217 		 * at all), so we don't bother optimizing out the unlock/relock.
218 		 */
219 		if (vp == dvp ||
220 		    error || (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) {
221 			if ((error = vn_lock(dvp, LK_EXCLUSIVE)) != 0)
222 				return (error);
223 			cnp->cn_flags &= ~PDIRUNLOCK;
224 		}
225 		*vpp = NULL;
226 		return (-1);
227 	}
228 
229 	nchstats.ncs_goodhits++;
230 	/*
231 	 * Move this slot to end of LRU chain, if not already there.
232 	 */
233 	if (TAILQ_NEXT(ncp, nc_lru) != 0) {
234 		TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
235 		TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
236 	}
237 	*vpp = vp;
238 	return (0);
239 
240 remove:
241 	/*
242 	 * Last component and we are renaming or deleting,
243 	 * the cache entry is invalid, or otherwise don't
244 	 * want cache entry to exist.
245 	 */
246 	TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
247 	LIST_REMOVE(ncp, nc_hash);
248 	ncp->nc_hash.le_prev = NULL;
249 	if (ncp->nc_vhash.le_prev != NULL) {
250 		LIST_REMOVE(ncp, nc_vhash);
251 		ncp->nc_vhash.le_prev = NULL;
252 	}
253 	TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);
254 	*vpp = NULL;
255 	return (-1);
256 }
257 
258 /*
259  * Scan cache looking for name of directory entry pointing at vp.
260  *
261  * Fill in dvpp.
262  *
263  * If bufp is non-NULL, also place the name in the buffer which starts
264  * at bufp, immediately before *bpp, and move bpp backwards to point
265  * at the start of it.  (Yes, this is a little baroque, but it's done
266  * this way to cater to the whims of getcwd).
267  *
268  * Returns 0 on success, -1 on cache miss, positive errno on failure.
269  */
270 int
271 cache_revlookup(struct vnode *vp, struct vnode **dvpp, char **bpp, char *bufp)
272 {
273 	struct namecache *ncp;
274 	struct vnode *dvp;
275 	struct ncvhashhead *nvcpp;
276 	char *bp;
277 
278 	if (!doingcache)
279 		goto out;
280 
281 	nvcpp = &ncvhashtbl[NCVHASH(vp)];
282 
283 	LIST_FOREACH(ncp, nvcpp, nc_vhash) {
284 		if (ncp->nc_vp == vp &&
285 		    ncp->nc_vpid == vp->v_id &&
286 		    (dvp = ncp->nc_dvp) != NULL &&
287 		    dvp != vp && 		/* avoid pesky . entries.. */
288 		    dvp->v_id == ncp->nc_dvpid) {
289 
290 #ifdef DIAGNOSTIC
291 			if (ncp->nc_nlen == 1 &&
292 			    ncp->nc_name[0] == '.')
293 				panic("cache_revlookup: found entry for .");
294 
295 			if (ncp->nc_nlen == 2 &&
296 			    ncp->nc_name[0] == '.' &&
297 			    ncp->nc_name[1] == '.')
298 				panic("cache_revlookup: found entry for ..");
299 #endif
300 			nchstats.ncs_revhits++;
301 
302 			if (bufp) {
303 				bp = *bpp;
304 				bp -= ncp->nc_nlen;
305 				if (bp <= bufp) {
306 					*dvpp = NULL;
307 					return (ERANGE);
308 				}
309 				memcpy(bp, ncp->nc_name, ncp->nc_nlen);
310 				*bpp = bp;
311 			}
312 
313 			/* XXX MP: how do we know dvp won't evaporate? */
314 			*dvpp = dvp;
315 			return (0);
316 		}
317 	}
318 	nchstats.ncs_revmiss++;
319  out:
320 	*dvpp = NULL;
321 	return (-1);
322 }
323 
324 /*
325  * Add an entry to the cache
326  */
327 void
328 cache_enter(struct vnode *dvp, struct vnode *vp, struct componentname *cnp)
329 {
330 	struct namecache *ncp;
331 	struct nchashhead *ncpp;
332 	struct ncvhashhead *nvcpp;
333 
334 #ifdef DIAGNOSTIC
335 	if (cnp->cn_namelen > NCHNAMLEN)
336 		panic("cache_enter: name too long");
337 #endif
338 	if (!doingcache)
339 		return;
340 	/*
341 	 * Free the cache slot at head of lru chain.
342 	 */
343 	if (numcache < numvnodes) {
344 		ncp = pool_get(&namecache_pool, PR_WAITOK);
345 		memset(ncp, 0, sizeof(*ncp));
346 		numcache++;
347 	} else if ((ncp = TAILQ_FIRST(&nclruhead)) != NULL) {
348 		TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
349 		if (ncp->nc_hash.le_prev != NULL) {
350 			LIST_REMOVE(ncp, nc_hash);
351 			ncp->nc_hash.le_prev = NULL;
352 		}
353 		if (ncp->nc_vhash.le_prev != NULL) {
354 			LIST_REMOVE(ncp, nc_vhash);
355 			ncp->nc_vhash.le_prev = NULL;
356 		}
357 	} else
358 		return;
359 	/* Grab the vnode we just found. */
360 	ncp->nc_vp = vp;
361 	if (vp)
362 		ncp->nc_vpid = vp->v_id;
363 	else {
364 		/*
365 		 * For negative hits, save the ISWHITEOUT flag so we can
366 		 * restore it later when the cache entry is used again.
367 		 */
368 		ncp->nc_vpid = cnp->cn_flags & ISWHITEOUT;
369 	}
370 	/* Fill in cache info. */
371 	ncp->nc_dvp = dvp;
372 	ncp->nc_dvpid = dvp->v_id;
373 	ncp->nc_nlen = cnp->cn_namelen;
374 	memcpy(ncp->nc_name, cnp->cn_nameptr, (unsigned)ncp->nc_nlen);
375 	TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
376 	ncpp = &nchashtbl[NCHASH(cnp, dvp)];
377 	LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
378 
379 	ncp->nc_vhash.le_prev = NULL;
380 	ncp->nc_vhash.le_next = NULL;
381 
382 	/*
383 	 * Create reverse-cache entries (used in getcwd) for directories.
384 	 */
385 	if (vp != NULL &&
386 	    vp != dvp &&
387 #ifndef NAMECACHE_ENTER_REVERSE
388 	    vp->v_type == VDIR &&
389 #endif
390 	    (ncp->nc_nlen > 2 ||
391 	    (ncp->nc_nlen > 1 && ncp->nc_name[1] != '.') ||
392 	    (/* ncp->nc_nlen > 0 && */ ncp->nc_name[0] != '.'))) {
393 		nvcpp = &ncvhashtbl[NCVHASH(vp)];
394 		LIST_INSERT_HEAD(nvcpp, ncp, nc_vhash);
395 	}
396 }
397 
398 /*
399  * Name cache initialization, from vfs_init() when we are booting
400  */
401 void
402 nchinit(void)
403 {
404 
405 	TAILQ_INIT(&nclruhead);
406 	nchashtbl =
407 	    hashinit(desiredvnodes, HASH_LIST, M_CACHE, M_WAITOK, &nchash);
408 	ncvhashtbl =
409 #ifdef NAMECACHE_ENTER_REVERSE
410 	    hashinit(desiredvnodes, HASH_LIST, M_CACHE, M_WAITOK, &ncvhash);
411 #else
412 	    hashinit(desiredvnodes/8, HASH_LIST, M_CACHE, M_WAITOK, &ncvhash);
413 #endif
414 	pool_init(&namecache_pool, sizeof(struct namecache), 0, 0, 0,
415 	    "ncachepl", &pool_allocator_nointr);
416 }
417 
418 /*
419  * Name cache reinitialization, for when the maximum number of vnodes increases.
420  */
421 void
422 nchreinit(void)
423 {
424 	struct namecache *ncp;
425 	struct nchashhead *oldhash1, *hash1;
426 	struct ncvhashhead *oldhash2, *hash2;
427 	u_long i, oldmask1, oldmask2, mask1, mask2;
428 
429 	hash1 = hashinit(desiredvnodes, HASH_LIST, M_CACHE, M_WAITOK, &mask1);
430 	hash2 =
431 #ifdef NAMECACHE_ENTER_REVERSE
432 	    hashinit(desiredvnodes, HASH_LIST, M_CACHE, M_WAITOK, &mask2);
433 #else
434 	    hashinit(desiredvnodes/8, HASH_LIST, M_CACHE, M_WAITOK, &mask2);
435 #endif
436 	oldhash1 = nchashtbl;
437 	oldmask1 = nchash;
438 	nchashtbl = hash1;
439 	nchash = mask1;
440 	oldhash2 = ncvhashtbl;
441 	oldmask2 = ncvhash;
442 	ncvhashtbl = hash2;
443 	ncvhash = mask2;
444 	for (i = 0; i <= oldmask1; i++) {
445 		while ((ncp = LIST_FIRST(&oldhash1[i])) != NULL) {
446 			LIST_REMOVE(ncp, nc_hash);
447 			ncp->nc_hash.le_prev = NULL;
448 		}
449 	}
450 	for (i = 0; i <= oldmask2; i++) {
451 		while ((ncp = LIST_FIRST(&oldhash2[i])) != NULL) {
452 			LIST_REMOVE(ncp, nc_vhash);
453 			ncp->nc_vhash.le_prev = NULL;
454 		}
455 	}
456 	hashdone(oldhash1, M_CACHE);
457 	hashdone(oldhash2, M_CACHE);
458 }
459 
460 /*
461  * Cache flush, a particular vnode; called when a vnode is renamed to
462  * hide entries that would now be invalid
463  */
464 void
465 cache_purge(struct vnode *vp)
466 {
467 	struct namecache *ncp;
468 	struct nchashhead *ncpp;
469 	static u_long nextvnodeid;
470 
471 	vp->v_id = ++nextvnodeid;
472 	if (nextvnodeid != 0)
473 		return;
474 	for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
475 		LIST_FOREACH(ncp, ncpp, nc_hash) {
476 			ncp->nc_vpid = 0;
477 			ncp->nc_dvpid = 0;
478 		}
479 	}
480 	vp->v_id = ++nextvnodeid;
481 }
482 
483 /*
484  * Cache flush, a whole filesystem; called when filesys is umounted to
485  * remove entries that would now be invalid.
486  */
487 void
488 cache_purgevfs(struct mount *mp)
489 {
490 	struct namecache *ncp, *nxtcp;
491 
492 	for (ncp = TAILQ_FIRST(&nclruhead); ncp != NULL; ncp = nxtcp) {
493 		nxtcp = TAILQ_NEXT(ncp, nc_lru);
494 		if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) {
495 			continue;
496 		}
497 		/* Free the resources we had. */
498 		ncp->nc_vp = NULL;
499 		ncp->nc_dvp = NULL;
500 		TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
501 		if (ncp->nc_hash.le_prev != NULL) {
502 			LIST_REMOVE(ncp, nc_hash);
503 			ncp->nc_hash.le_prev = NULL;
504 		}
505 		if (ncp->nc_vhash.le_prev != NULL) {
506 			LIST_REMOVE(ncp, nc_vhash);
507 			ncp->nc_vhash.le_prev = NULL;
508 		}
509 		TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);
510 	}
511 }
512 
513 #ifdef DDB
514 void
515 namecache_print(struct vnode *vp, void (*pr)(const char *, ...))
516 {
517 	struct vnode *dvp = NULL;
518 	struct namecache *ncp;
519 
520 	TAILQ_FOREACH(ncp, &nclruhead, nc_lru) {
521 		if (ncp->nc_vp == vp && ncp->nc_vpid == vp->v_id) {
522 			(*pr)("name %.*s\n", ncp->nc_nlen, ncp->nc_name);
523 			dvp = ncp->nc_dvp;
524 		}
525 	}
526 	if (dvp == NULL) {
527 		(*pr)("name not found\n");
528 		return;
529 	}
530 	vp = dvp;
531 	TAILQ_FOREACH(ncp, &nclruhead, nc_lru) {
532 		if (ncp->nc_vp == vp && ncp->nc_vpid == vp->v_id) {
533 			(*pr)("parent %.*s\n", ncp->nc_nlen, ncp->nc_name);
534 		}
535 	}
536 }
537 #endif
538