xref: /csrg-svn/sys/kern/vfs_cache.c (revision 63180)
137487Smckusick /*
2*63180Sbostic  * Copyright (c) 1989, 1993
3*63180Sbostic  *	The Regents of the University of California.  All rights reserved.
437487Smckusick  *
544455Sbostic  * %sccs.include.redist.c%
637487Smckusick  *
7*63180Sbostic  *	@(#)vfs_cache.c	8.1 (Berkeley) 06/10/93
837487Smckusick  */
937487Smckusick 
1056517Sbostic #include <sys/param.h>
1156517Sbostic #include <sys/systm.h>
1256517Sbostic #include <sys/time.h>
1356517Sbostic #include <sys/mount.h>
1456517Sbostic #include <sys/vnode.h>
1556517Sbostic #include <sys/namei.h>
1656517Sbostic #include <sys/errno.h>
1756517Sbostic #include <sys/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  */
4055544Smckusick struct namecache **nchashtbl;
4140881Smckusick u_long	nchash;				/* size of hash table - 1 */
4240881Smckusick long	numcache;			/* number of cache entries allocated */
4337487Smckusick struct	namecache *nchhead, **nchtail;	/* LRU chain pointers */
4437487Smckusick struct	nchstats nchstats;		/* cache effectiveness statistics */
4537487Smckusick 
4638768Smckusick int doingcache = 1;			/* 1 => enable the cache */
4738768Smckusick 
4837487Smckusick /*
4937487Smckusick  * Look for a the name in the cache. We don't do this
5037487Smckusick  * if the segment name is long, simply so the cache can avoid
5137487Smckusick  * holding long names (which would either waste space, or
5237487Smckusick  * add greatly to the complexity).
5338768Smckusick  *
5438768Smckusick  * Lookup is called with ni_dvp pointing to the directory to search,
5538768Smckusick  * ni_ptr pointing to the name of the entry being sought, ni_namelen
5638768Smckusick  * tells the length of the name, and ni_hash contains a hash of
5738768Smckusick  * the name. If the lookup succeeds, the vnode is returned in ni_vp
5838768Smckusick  * and a status of -1 is returned. If the lookup determines that
5938768Smckusick  * the name does not exist (negative cacheing), a status of ENOENT
6038768Smckusick  * is returned. If the lookup fails, a status of zero is returned.
6137487Smckusick  */
6252231Sheideman int
6352306Sheideman cache_lookup(dvp, vpp, cnp)
6452231Sheideman 	struct vnode *dvp;
6552231Sheideman 	struct vnode **vpp;
6652231Sheideman 	struct componentname *cnp;
6737487Smckusick {
6855544Smckusick 	register struct namecache *ncp, *ncq, **ncpp;
6937487Smckusick 
7038768Smckusick 	if (!doingcache)
7138768Smckusick 		return (0);
7252231Sheideman 	if (cnp->cn_namelen > NCHNAMLEN) {
7337487Smckusick 		nchstats.ncs_long++;
7452231Sheideman 		cnp->cn_flags &= ~MAKEENTRY;
7537487Smckusick 		return (0);
7637487Smckusick 	}
7755544Smckusick 	ncpp = &nchashtbl[cnp->cn_hash & nchash];
7855544Smckusick 	for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) {
7938768Smckusick 		if (ncp->nc_dvp == dvp &&
8038768Smckusick 		    ncp->nc_dvpid == dvp->v_id &&
8152231Sheideman 		    ncp->nc_nlen == cnp->cn_namelen &&
8255544Smckusick 		    !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
8337487Smckusick 			break;
8437487Smckusick 	}
8555544Smckusick 	if (ncp == NULL) {
8637487Smckusick 		nchstats.ncs_miss++;
8737487Smckusick 		return (0);
8837487Smckusick 	}
8952231Sheideman 	if (!(cnp->cn_flags & MAKEENTRY)) {
9038768Smckusick 		nchstats.ncs_badhits++;
9138768Smckusick 	} else if (ncp->nc_vp == NULL) {
9252306Sheideman 		if (cnp->cn_nameiop != CREATE) {
9346747Smckusick 			nchstats.ncs_neghits++;
9446747Smckusick 			/*
9546747Smckusick 			 * Move this slot to end of LRU chain,
9646747Smckusick 			 * if not already there.
9746747Smckusick 			 */
9846747Smckusick 			if (ncp->nc_nxt) {
9946747Smckusick 				/* remove from LRU chain */
10046747Smckusick 				*ncp->nc_prev = ncp->nc_nxt;
10146747Smckusick 				ncp->nc_nxt->nc_prev = ncp->nc_prev;
10246747Smckusick 				/* and replace at end of it */
10346747Smckusick 				ncp->nc_nxt = NULL;
10446747Smckusick 				ncp->nc_prev = nchtail;
10546747Smckusick 				*nchtail = ncp;
10646747Smckusick 				nchtail = &ncp->nc_nxt;
10746747Smckusick 			}
10846747Smckusick 			return (ENOENT);
10937487Smckusick 		}
11038768Smckusick 	} else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
11138768Smckusick 		nchstats.ncs_falsehits++;
11238768Smckusick 	} else {
11337487Smckusick 		nchstats.ncs_goodhits++;
11438768Smckusick 		/*
11538768Smckusick 		 * move this slot to end of LRU chain, if not already there
11638768Smckusick 		 */
11738768Smckusick 		if (ncp->nc_nxt) {
11838768Smckusick 			/* remove from LRU chain */
11938768Smckusick 			*ncp->nc_prev = ncp->nc_nxt;
12038768Smckusick 			ncp->nc_nxt->nc_prev = ncp->nc_prev;
12138768Smckusick 			/* and replace at end of it */
12238768Smckusick 			ncp->nc_nxt = NULL;
12338768Smckusick 			ncp->nc_prev = nchtail;
12438768Smckusick 			*nchtail = ncp;
12538768Smckusick 			nchtail = &ncp->nc_nxt;
12638768Smckusick 		}
12752231Sheideman 		*vpp = ncp->nc_vp;
12838768Smckusick 		return (-1);
12937487Smckusick 	}
13037487Smckusick 
13137487Smckusick 	/*
13237487Smckusick 	 * Last component and we are renaming or deleting,
13337487Smckusick 	 * the cache entry is invalid, or otherwise don't
13437487Smckusick 	 * want cache entry to exist.
13537487Smckusick 	 */
13637487Smckusick 	/* remove from LRU chain */
13755544Smckusick 	if (ncq = ncp->nc_nxt)
13855544Smckusick 		ncq->nc_prev = ncp->nc_prev;
13937487Smckusick 	else
14037487Smckusick 		nchtail = ncp->nc_prev;
14155544Smckusick 	*ncp->nc_prev = ncq;
14238768Smckusick 	/* remove from hash chain */
14355544Smckusick 	if (ncq = ncp->nc_forw)
14455544Smckusick 		ncq->nc_back = ncp->nc_back;
14555544Smckusick 	*ncp->nc_back = ncq;
14655544Smckusick 	/* and make a dummy hash chain */
14755544Smckusick 	ncp->nc_forw = NULL;
14855544Smckusick 	ncp->nc_back = NULL;
14937487Smckusick 	/* insert at head of LRU list (first to grab) */
15056341Smckusick 	if (ncq = nchhead)
15156341Smckusick 		ncq->nc_prev = &ncp->nc_nxt;
15256341Smckusick 	else
15356341Smckusick 		nchtail = &ncp->nc_nxt;
15456341Smckusick 	nchhead = ncp;
15556341Smckusick 	ncp->nc_nxt = ncq;
15637487Smckusick 	ncp->nc_prev = &nchhead;
15737487Smckusick 	return (0);
15837487Smckusick }
15937487Smckusick 
16037487Smckusick /*
16137487Smckusick  * Add an entry to the cache
16237487Smckusick  */
16352306Sheideman cache_enter(dvp, vp, cnp)
16452231Sheideman 	struct vnode *dvp;
16552231Sheideman 	struct vnode *vp;
16652231Sheideman 	struct componentname *cnp;
16737487Smckusick {
16855544Smckusick 	register struct namecache *ncp, *ncq, **ncpp;
16937487Smckusick 
17055185Smckusick #ifdef DIAGNOSTIC
17155185Smckusick 	if (cnp->cn_namelen > NCHNAMLEN)
17255185Smckusick 		panic("cache_enter: name too long");
17355185Smckusick #endif
17438768Smckusick 	if (!doingcache)
17538768Smckusick 		return;
17637487Smckusick 	/*
17737487Smckusick 	 * Free the cache slot at head of lru chain.
17837487Smckusick 	 */
17940881Smckusick 	if (numcache < desiredvnodes) {
18040881Smckusick 		ncp = (struct namecache *)
18145117Smckusick 			malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
18240881Smckusick 		bzero((char *)ncp, sizeof *ncp);
18340881Smckusick 		numcache++;
18440881Smckusick 	} else if (ncp = nchhead) {
18537487Smckusick 		/* remove from lru chain */
18655544Smckusick 		if (ncq = ncp->nc_nxt)
18755544Smckusick 			ncq->nc_prev = ncp->nc_prev;
18837487Smckusick 		else
18937487Smckusick 			nchtail = ncp->nc_prev;
19055544Smckusick 		*ncp->nc_prev = ncq;
19155699Smckusick 		/* remove from old hash chain, if on one */
19255699Smckusick 		if (ncp->nc_back) {
19355699Smckusick 			if (ncq = ncp->nc_forw)
19455699Smckusick 				ncq->nc_back = ncp->nc_back;
19555699Smckusick 			*ncp->nc_back = ncq;
19655699Smckusick 			ncp->nc_forw = NULL;
19755699Smckusick 			ncp->nc_back = NULL;
19855699Smckusick 		}
19940881Smckusick 	} else
20040881Smckusick 		return;
20140881Smckusick 	/* grab the vnode we just found */
20252231Sheideman 	ncp->nc_vp = vp;
20352231Sheideman 	if (vp)
20452231Sheideman 		ncp->nc_vpid = vp->v_id;
20540881Smckusick 	else
20640881Smckusick 		ncp->nc_vpid = 0;
20740881Smckusick 	/* fill in cache info */
20852231Sheideman 	ncp->nc_dvp = dvp;
20952231Sheideman 	ncp->nc_dvpid = dvp->v_id;
21052231Sheideman 	ncp->nc_nlen = cnp->cn_namelen;
21152231Sheideman 	bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
21240881Smckusick 	/* link at end of lru chain */
21340881Smckusick 	ncp->nc_nxt = NULL;
21440881Smckusick 	ncp->nc_prev = nchtail;
21540881Smckusick 	*nchtail = ncp;
21640881Smckusick 	nchtail = &ncp->nc_nxt;
21740881Smckusick 	/* and insert on hash chain */
21855544Smckusick 	ncpp = &nchashtbl[cnp->cn_hash & nchash];
21955544Smckusick 	if (ncq = *ncpp)
22055544Smckusick 		ncq->nc_back = &ncp->nc_forw;
22155544Smckusick 	ncp->nc_forw = ncq;
22255544Smckusick 	ncp->nc_back = ncpp;
22355544Smckusick 	*ncpp = ncp;
22437487Smckusick }
22537487Smckusick 
22637487Smckusick /*
22740881Smckusick  * Name cache initialization, from vfs_init() when we are booting
22837487Smckusick  */
22937487Smckusick nchinit()
23037487Smckusick {
23137487Smckusick 
23237487Smckusick 	nchtail = &nchhead;
23355544Smckusick 	nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash);
23437487Smckusick }
23537487Smckusick 
23637487Smckusick /*
23737487Smckusick  * Cache flush, a particular vnode; called when a vnode is renamed to
23838768Smckusick  * hide entries that would now be invalid
23937487Smckusick  */
24037487Smckusick cache_purge(vp)
24138768Smckusick 	struct vnode *vp;
24237487Smckusick {
24355544Smckusick 	struct namecache *ncp, **ncpp;
24437487Smckusick 
24538768Smckusick 	vp->v_id = ++nextvnodeid;
24638768Smckusick 	if (nextvnodeid != 0)
24738768Smckusick 		return;
24855544Smckusick 	for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
24955544Smckusick 		for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) {
25040881Smckusick 			ncp->nc_vpid = 0;
25140881Smckusick 			ncp->nc_dvpid = 0;
25240881Smckusick 		}
25337487Smckusick 	}
25438768Smckusick 	vp->v_id = ++nextvnodeid;
25537487Smckusick }
25637487Smckusick 
25737487Smckusick /*
25837487Smckusick  * Cache flush, a whole filesystem; called when filesys is umounted to
25937487Smckusick  * remove entries that would now be invalid
26037487Smckusick  *
26137487Smckusick  * The line "nxtcp = nchhead" near the end is to avoid potential problems
26237487Smckusick  * if the cache lru chain is modified while we are dumping the
26337487Smckusick  * inode.  This makes the algorithm O(n^2), but do you think I care?
26437487Smckusick  */
26537487Smckusick cache_purgevfs(mp)
26645117Smckusick 	struct mount *mp;
26737487Smckusick {
26837487Smckusick 	register struct namecache *ncp, *nxtcp;
26937487Smckusick 
27037487Smckusick 	for (ncp = nchhead; ncp; ncp = nxtcp) {
27155544Smckusick 		if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) {
27255544Smckusick 			nxtcp = ncp->nc_nxt;
27337487Smckusick 			continue;
27455544Smckusick 		}
27537487Smckusick 		/* free the resources we had */
27637487Smckusick 		ncp->nc_vp = NULL;
27738768Smckusick 		ncp->nc_dvp = NULL;
27855699Smckusick 		/* remove from old hash chain, if on one */
27955699Smckusick 		if (ncp->nc_back) {
28055699Smckusick 			if (nxtcp = ncp->nc_forw)
28155699Smckusick 				nxtcp->nc_back = ncp->nc_back;
28255699Smckusick 			*ncp->nc_back = nxtcp;
28355699Smckusick 			ncp->nc_forw = NULL;
28455699Smckusick 			ncp->nc_back = NULL;
28555699Smckusick 		}
28637487Smckusick 		/* delete this entry from LRU chain */
28755544Smckusick 		if (nxtcp = ncp->nc_nxt)
28837487Smckusick 			nxtcp->nc_prev = ncp->nc_prev;
28937487Smckusick 		else
29037487Smckusick 			nchtail = ncp->nc_prev;
29155544Smckusick 		*ncp->nc_prev = nxtcp;
29237487Smckusick 		/* cause rescan of list, it may have altered */
29356341Smckusick 		/* also put the now-free entry at head of LRU */
29456341Smckusick 		if (nxtcp = nchhead)
29556341Smckusick 			nxtcp->nc_prev = &ncp->nc_nxt;
29656341Smckusick 		else
29756341Smckusick 			nchtail = &ncp->nc_nxt;
29856341Smckusick 		nchhead = ncp;
29937487Smckusick 		ncp->nc_nxt = nxtcp;
30037487Smckusick 		ncp->nc_prev = &nchhead;
30137487Smckusick 	}
30237487Smckusick }
303