xref: /csrg-svn/sys/kern/vfs_cache.c (revision 45117)
137487Smckusick /*
237487Smckusick  * Copyright (c) 1989 The Regents of the University of California.
337487Smckusick  * All rights reserved.
437487Smckusick  *
544455Sbostic  * %sccs.include.redist.c%
637487Smckusick  *
7*45117Smckusick  *	@(#)vfs_cache.c	7.7 (Berkeley) 08/24/90
837487Smckusick  */
937487Smckusick 
1037487Smckusick #include "param.h"
1137487Smckusick #include "systm.h"
1237487Smckusick #include "time.h"
13*45117Smckusick #include "mount.h"
1437487Smckusick #include "vnode.h"
1537487Smckusick #include "namei.h"
1638768Smckusick #include "errno.h"
1740881Smckusick #include "malloc.h"
1837487Smckusick 
1937487Smckusick /*
2037487Smckusick  * Name caching works as follows:
2137487Smckusick  *
2237487Smckusick  * Names found by directory scans are retained in a cache
2337487Smckusick  * for future reference.  It is managed LRU, so frequently
2437487Smckusick  * used names will hang around.  Cache is indexed by hash value
2538768Smckusick  * obtained from (vp, name) where vp refers to the directory
2638768Smckusick  * containing name.
2737487Smckusick  *
2837487Smckusick  * For simplicity (and economy of storage), names longer than
2937487Smckusick  * a maximum length of NCHNAMLEN are not cached; they occur
3037487Smckusick  * infrequently in any case, and are almost never of interest.
3137487Smckusick  *
3237487Smckusick  * Upon reaching the last segment of a path, if the reference
3337487Smckusick  * is for DELETE, or NOCACHE is set (rewrite), and the
3437487Smckusick  * name is located in the cache, it will be dropped.
3537487Smckusick  */
3637487Smckusick 
3737487Smckusick /*
3837487Smckusick  * Structures associated with name cacheing.
3937487Smckusick  */
4037487Smckusick union nchash {
4137487Smckusick 	union	nchash *nch_head[2];
4237487Smckusick 	struct	namecache *nch_chain[2];
4340881Smckusick } *nchashtbl;
4437487Smckusick #define	nch_forw	nch_chain[0]
4537487Smckusick #define	nch_back	nch_chain[1]
4637487Smckusick 
4740881Smckusick u_long	nchash;				/* size of hash table - 1 */
4840881Smckusick long	numcache;			/* number of cache entries allocated */
4937487Smckusick struct	namecache *nchhead, **nchtail;	/* LRU chain pointers */
5037487Smckusick struct	nchstats nchstats;		/* cache effectiveness statistics */
5137487Smckusick 
5238768Smckusick int doingcache = 1;			/* 1 => enable the cache */
5338768Smckusick 
5437487Smckusick /*
5537487Smckusick  * Look for a the name in the cache. We don't do this
5637487Smckusick  * if the segment name is long, simply so the cache can avoid
5737487Smckusick  * holding long names (which would either waste space, or
5837487Smckusick  * add greatly to the complexity).
5938768Smckusick  *
6038768Smckusick  * Lookup is called with ni_dvp pointing to the directory to search,
6138768Smckusick  * ni_ptr pointing to the name of the entry being sought, ni_namelen
6238768Smckusick  * tells the length of the name, and ni_hash contains a hash of
6338768Smckusick  * the name. If the lookup succeeds, the vnode is returned in ni_vp
6438768Smckusick  * and a status of -1 is returned. If the lookup determines that
6538768Smckusick  * the name does not exist (negative cacheing), a status of ENOENT
6638768Smckusick  * is returned. If the lookup fails, a status of zero is returned.
6737487Smckusick  */
6837487Smckusick cache_lookup(ndp)
6937487Smckusick 	register struct nameidata *ndp;
7037487Smckusick {
7138768Smckusick 	register struct vnode *dvp;
7237487Smckusick 	register struct namecache *ncp;
7337487Smckusick 	union nchash *nhp;
7437487Smckusick 
7538768Smckusick 	if (!doingcache)
7638768Smckusick 		return (0);
7738768Smckusick 	if (ndp->ni_namelen > NCHNAMLEN) {
7837487Smckusick 		nchstats.ncs_long++;
7937487Smckusick 		ndp->ni_makeentry = 0;
8037487Smckusick 		return (0);
8137487Smckusick 	}
8238768Smckusick 	dvp = ndp->ni_dvp;
8340881Smckusick 	nhp = &nchashtbl[ndp->ni_hash & nchash];
8437487Smckusick 	for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp;
8537487Smckusick 	    ncp = ncp->nc_forw) {
8638768Smckusick 		if (ncp->nc_dvp == dvp &&
8738768Smckusick 		    ncp->nc_dvpid == dvp->v_id &&
8838768Smckusick 		    ncp->nc_nlen == ndp->ni_namelen &&
8938768Smckusick 		    !bcmp(ncp->nc_name, ndp->ni_ptr, (unsigned)ncp->nc_nlen))
9037487Smckusick 			break;
9137487Smckusick 	}
9237487Smckusick 	if (ncp == (struct namecache *)nhp) {
9337487Smckusick 		nchstats.ncs_miss++;
9437487Smckusick 		return (0);
9537487Smckusick 	}
9638768Smckusick 	if (!ndp->ni_makeentry) {
9738768Smckusick 		nchstats.ncs_badhits++;
9838768Smckusick 	} else if (ncp->nc_vp == NULL) {
9938768Smckusick 		nchstats.ncs_neghits++;
10037487Smckusick 		/*
10138768Smckusick 		 * move this slot to end of LRU chain, if not already there
10237487Smckusick 		 */
10337487Smckusick 		if (ncp->nc_nxt) {
10437487Smckusick 			/* remove from LRU chain */
10537487Smckusick 			*ncp->nc_prev = ncp->nc_nxt;
10637487Smckusick 			ncp->nc_nxt->nc_prev = ncp->nc_prev;
10737487Smckusick 			/* and replace at end of it */
10837487Smckusick 			ncp->nc_nxt = NULL;
10937487Smckusick 			ncp->nc_prev = nchtail;
11037487Smckusick 			*nchtail = ncp;
11137487Smckusick 			nchtail = &ncp->nc_nxt;
11237487Smckusick 		}
11338768Smckusick 		return (ENOENT);
11438768Smckusick 	} else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
11538768Smckusick 		nchstats.ncs_falsehits++;
11638768Smckusick 	} else {
11737487Smckusick 		nchstats.ncs_goodhits++;
11838768Smckusick 		/*
11938768Smckusick 		 * move this slot to end of LRU chain, if not already there
12038768Smckusick 		 */
12138768Smckusick 		if (ncp->nc_nxt) {
12238768Smckusick 			/* remove from LRU chain */
12338768Smckusick 			*ncp->nc_prev = ncp->nc_nxt;
12438768Smckusick 			ncp->nc_nxt->nc_prev = ncp->nc_prev;
12538768Smckusick 			/* and replace at end of it */
12638768Smckusick 			ncp->nc_nxt = NULL;
12738768Smckusick 			ncp->nc_prev = nchtail;
12838768Smckusick 			*nchtail = ncp;
12938768Smckusick 			nchtail = &ncp->nc_nxt;
13038768Smckusick 		}
13138768Smckusick 		ndp->ni_vp = ncp->nc_vp;
13238768Smckusick 		return (-1);
13337487Smckusick 	}
13437487Smckusick 
13537487Smckusick 	/*
13637487Smckusick 	 * Last component and we are renaming or deleting,
13737487Smckusick 	 * the cache entry is invalid, or otherwise don't
13837487Smckusick 	 * want cache entry to exist.
13937487Smckusick 	 */
14037487Smckusick 	/* remove from LRU chain */
14137487Smckusick 	*ncp->nc_prev = ncp->nc_nxt;
14237487Smckusick 	if (ncp->nc_nxt)
14337487Smckusick 		ncp->nc_nxt->nc_prev = ncp->nc_prev;
14437487Smckusick 	else
14537487Smckusick 		nchtail = ncp->nc_prev;
14638768Smckusick 	/* remove from hash chain */
14738768Smckusick 	remque(ncp);
14837487Smckusick 	/* insert at head of LRU list (first to grab) */
14937487Smckusick 	ncp->nc_nxt = nchhead;
15037487Smckusick 	ncp->nc_prev = &nchhead;
15137487Smckusick 	nchhead->nc_prev = &ncp->nc_nxt;
15237487Smckusick 	nchhead = ncp;
15337487Smckusick 	/* and make a dummy hash chain */
15437487Smckusick 	ncp->nc_forw = ncp;
15537487Smckusick 	ncp->nc_back = ncp;
15637487Smckusick 	return (0);
15737487Smckusick }
15837487Smckusick 
15937487Smckusick /*
16037487Smckusick  * Add an entry to the cache
16137487Smckusick  */
16237487Smckusick cache_enter(ndp)
16337487Smckusick 	register struct nameidata *ndp;
16437487Smckusick {
16537487Smckusick 	register struct namecache *ncp;
16637487Smckusick 	union nchash *nhp;
16737487Smckusick 
16838768Smckusick 	if (!doingcache)
16938768Smckusick 		return;
17037487Smckusick 	/*
17137487Smckusick 	 * Free the cache slot at head of lru chain.
17237487Smckusick 	 */
17340881Smckusick 	if (numcache < desiredvnodes) {
17440881Smckusick 		ncp = (struct namecache *)
175*45117Smckusick 			malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
17640881Smckusick 		bzero((char *)ncp, sizeof *ncp);
17740881Smckusick 		numcache++;
17840881Smckusick 	} else if (ncp = nchhead) {
17937487Smckusick 		/* remove from lru chain */
18037487Smckusick 		*ncp->nc_prev = ncp->nc_nxt;
18137487Smckusick 		if (ncp->nc_nxt)
18237487Smckusick 			ncp->nc_nxt->nc_prev = ncp->nc_prev;
18337487Smckusick 		else
18437487Smckusick 			nchtail = ncp->nc_prev;
18538768Smckusick 		/* remove from old hash chain */
18638768Smckusick 		remque(ncp);
18740881Smckusick 	} else
18840881Smckusick 		return;
18940881Smckusick 	/* grab the vnode we just found */
19040881Smckusick 	ncp->nc_vp = ndp->ni_vp;
19140881Smckusick 	if (ndp->ni_vp)
19240881Smckusick 		ncp->nc_vpid = ndp->ni_vp->v_id;
19340881Smckusick 	else
19440881Smckusick 		ncp->nc_vpid = 0;
19540881Smckusick 	/* fill in cache info */
19640881Smckusick 	ncp->nc_dvp = ndp->ni_dvp;
19740881Smckusick 	ncp->nc_dvpid = ndp->ni_dvp->v_id;
19840881Smckusick 	ncp->nc_nlen = ndp->ni_namelen;
19940881Smckusick 	bcopy(ndp->ni_ptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
20040881Smckusick 	/* link at end of lru chain */
20140881Smckusick 	ncp->nc_nxt = NULL;
20240881Smckusick 	ncp->nc_prev = nchtail;
20340881Smckusick 	*nchtail = ncp;
20440881Smckusick 	nchtail = &ncp->nc_nxt;
20540881Smckusick 	/* and insert on hash chain */
20640881Smckusick 	nhp = &nchashtbl[ndp->ni_hash & nchash];
20740881Smckusick 	insque(ncp, nhp);
20837487Smckusick }
20937487Smckusick 
21037487Smckusick /*
21140881Smckusick  * Name cache initialization, from vfs_init() when we are booting
21237487Smckusick  */
21337487Smckusick nchinit()
21437487Smckusick {
21537487Smckusick 	register union nchash *nchp;
21640881Smckusick 	long nchashsize;
21737487Smckusick 
21837487Smckusick 	nchhead = 0;
21937487Smckusick 	nchtail = &nchhead;
22040881Smckusick 	nchashsize = roundup((desiredvnodes + 1) * sizeof *nchp / 2,
22140881Smckusick 		NBPG * CLSIZE);
222*45117Smckusick 	nchashtbl = (union nchash *)malloc((u_long)nchashsize,
223*45117Smckusick 	    M_CACHE, M_WAITOK);
22440881Smckusick 	for (nchash = 1; nchash <= nchashsize / sizeof *nchp; nchash <<= 1)
22540881Smckusick 		/* void */;
22640881Smckusick 	nchash = (nchash >> 1) - 1;
22740881Smckusick 	for (nchp = &nchashtbl[nchash]; nchp >= nchashtbl; nchp--) {
22837487Smckusick 		nchp->nch_head[0] = nchp;
22937487Smckusick 		nchp->nch_head[1] = nchp;
23037487Smckusick 	}
23137487Smckusick }
23237487Smckusick 
23337487Smckusick /*
23437487Smckusick  * Cache flush, a particular vnode; called when a vnode is renamed to
23538768Smckusick  * hide entries that would now be invalid
23637487Smckusick  */
23737487Smckusick cache_purge(vp)
23838768Smckusick 	struct vnode *vp;
23937487Smckusick {
24040881Smckusick 	union nchash *nhp;
24138768Smckusick 	struct namecache *ncp;
24237487Smckusick 
24338768Smckusick 	vp->v_id = ++nextvnodeid;
24438768Smckusick 	if (nextvnodeid != 0)
24538768Smckusick 		return;
24640881Smckusick 	for (nhp = &nchashtbl[nchash]; nhp >= nchashtbl; nhp--) {
24740881Smckusick 		for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp;
24840881Smckusick 		    ncp = ncp->nc_forw) {
24940881Smckusick 			ncp->nc_vpid = 0;
25040881Smckusick 			ncp->nc_dvpid = 0;
25140881Smckusick 		}
25237487Smckusick 	}
25338768Smckusick 	vp->v_id = ++nextvnodeid;
25437487Smckusick }
25537487Smckusick 
25637487Smckusick /*
25737487Smckusick  * Cache flush, a whole filesystem; called when filesys is umounted to
25837487Smckusick  * remove entries that would now be invalid
25937487Smckusick  *
26037487Smckusick  * The line "nxtcp = nchhead" near the end is to avoid potential problems
26137487Smckusick  * if the cache lru chain is modified while we are dumping the
26237487Smckusick  * inode.  This makes the algorithm O(n^2), but do you think I care?
26337487Smckusick  */
26437487Smckusick cache_purgevfs(mp)
265*45117Smckusick 	struct mount *mp;
26637487Smckusick {
26737487Smckusick 	register struct namecache *ncp, *nxtcp;
26837487Smckusick 
26937487Smckusick 	for (ncp = nchhead; ncp; ncp = nxtcp) {
27037487Smckusick 		nxtcp = ncp->nc_nxt;
27138768Smckusick 		if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp)
27237487Smckusick 			continue;
27337487Smckusick 		/* free the resources we had */
27437487Smckusick 		ncp->nc_vp = NULL;
27538768Smckusick 		ncp->nc_dvp = NULL;
27637487Smckusick 		remque(ncp);		/* remove entry from its hash chain */
27737487Smckusick 		ncp->nc_forw = ncp;	/* and make a dummy one */
27837487Smckusick 		ncp->nc_back = ncp;
27937487Smckusick 		/* delete this entry from LRU chain */
28037487Smckusick 		*ncp->nc_prev = nxtcp;
28137487Smckusick 		if (nxtcp)
28237487Smckusick 			nxtcp->nc_prev = ncp->nc_prev;
28337487Smckusick 		else
28437487Smckusick 			nchtail = ncp->nc_prev;
28537487Smckusick 		/* cause rescan of list, it may have altered */
28637487Smckusick 		nxtcp = nchhead;
28737487Smckusick 		/* put the now-free entry at head of LRU */
28837487Smckusick 		ncp->nc_nxt = nxtcp;
28937487Smckusick 		ncp->nc_prev = &nchhead;
29037487Smckusick 		nxtcp->nc_prev = &ncp->nc_nxt;
29137487Smckusick 		nchhead = ncp;
29237487Smckusick 	}
29337487Smckusick }
294