[unix-history] / usr / src / sys / kern / vfs_cache.c

/*
 * Copyright (c) 1989 The Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that the above copyright notice and this paragraph are
 * duplicated in all such forms and that any documentation,
 * advertising materials, and other materials related to such
 * distribution and use acknowledge that the software was developed
 * by the University of California, Berkeley.  The name of the
 * University may not be used to endorse or promote products derived
 * from this software without specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 *
 *	@(#)vfs_cache.c	7.3 (Berkeley) %G%
 */

#include "param.h"
#include "systm.h"
#include "time.h"
#include "vnode.h"
#include "namei.h"

/*
 * Name caching works as follows:
 *
 * Names found by directory scans are retained in a cache
 * for future reference.  It is managed LRU, so frequently
 * used names will hang around.  Cache is indexed by hash value
 * obtained from (ino,dev,name) where ino & dev refer to the
 * directory containing name.
 *
 * For simplicity (and economy of storage), names longer than
 * a maximum length of NCHNAMLEN are not cached; they occur
 * infrequently in any case, and are almost never of interest.
 *
 * Upon reaching the last segment of a path, if the reference
 * is for DELETE, or NOCACHE is set (rewrite), and the
 * name is located in the cache, it will be dropped.
 */

/*
 * Structures associated with name cacheing.
 */
#define	NCHHASH		128	/* size of hash table */

#if	((NCHHASH)&((NCHHASH)-1)) != 0
#define	NHASH(h)	(((unsigned)(h) >> 6) % (NCHHASH))
#else
#define	NHASH(h)	(((unsigned)(h) >> 6) & ((NCHHASH)-1))
#endif

union nchash {
	union	nchash *nch_head[2];
	struct	namecache *nch_chain[2];
} nchash[NCHHASH];
#define	nch_forw	nch_chain[0]
#define	nch_back	nch_chain[1]

struct	namecache *nchhead, **nchtail;	/* LRU chain pointers */
struct	nchstats nchstats;		/* cache effectiveness statistics */

/*
 * Look for a the name in the cache. We don't do this
 * if the segment name is long, simply so the cache can avoid
 * holding long names (which would either waste space, or
 * add greatly to the complexity).
 */
struct vnode *
cache_lookup(ndp)
	register struct nameidata *ndp;
{
	register struct vnode *dp;
	register struct namecache *ncp;
	union nchash *nhp;

	return (0);		/* XXX for now */
	if (ndp->ni_dent.d_namlen > NCHNAMLEN) {
		nchstats.ncs_long++;
		ndp->ni_makeentry = 0;
		return (0);
	}
	dp = ndp->ni_vp;
	nhp = &nchash[NHASH(dp)];
	for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp;
	    ncp = ncp->nc_forw) {
		if (ncp->nc_vp == dp &&
		    ncp->nc_nlen == ndp->ni_dent.d_namlen &&
		    !bcmp(ncp->nc_name, ndp->ni_dent.d_name,
			(unsigned)ncp->nc_nlen))
			break;
	}
	if (ncp == (struct namecache *)nhp) {
		nchstats.ncs_miss++;
		ncp = NULL;
		return (0);
	}
	if (ndp->ni_makeentry) {
		/*
		 * move this slot to end of LRU
		 * chain, if not already there
		 */
		if (ncp->nc_nxt) {
			/* remove from LRU chain */
			*ncp->nc_prev = ncp->nc_nxt;
			ncp->nc_nxt->nc_prev = ncp->nc_prev;

			/* and replace at end of it */
			ncp->nc_nxt = NULL;
			ncp->nc_prev = nchtail;
			*nchtail = ncp;
			nchtail = &ncp->nc_nxt;
		}
		/* ndp->ni_dent.d_ino = dp->i_number; */
		/* ni_dent.d_reclen is garbage ... */
		nchstats.ncs_goodhits++;
		return (ncp->nc_vp);
	}

	/*
	 * Last component and we are renaming or deleting,
	 * the cache entry is invalid, or otherwise don't
	 * want cache entry to exist.
	 */
	nchstats.ncs_badhits++;
	/* remove from LRU chain */
	*ncp->nc_prev = ncp->nc_nxt;
	if (ncp->nc_nxt)
		ncp->nc_nxt->nc_prev = ncp->nc_prev;
	else
		nchtail = ncp->nc_prev;
	remque(ncp);		/* remove from hash chain */
	/* insert at head of LRU list (first to grab) */
	ncp->nc_nxt = nchhead;
	ncp->nc_prev = &nchhead;
	nchhead->nc_prev = &ncp->nc_nxt;
	nchhead = ncp;
	/* and make a dummy hash chain */
	ncp->nc_forw = ncp;
	ncp->nc_back = ncp;
	ncp = NULL;
	return (0);
}

/*
 * Add an entry to the cache
 */
cache_enter(ndp)
	register struct nameidata *ndp;
{
	register struct namecache *ncp;
	union nchash *nhp;

	return;		/* XXX for now */
	/*
	 * Free the cache slot at head of lru chain.
	 */
	if (ncp = nchhead) {
		/* remove from lru chain */
		*ncp->nc_prev = ncp->nc_nxt;
		if (ncp->nc_nxt)
			ncp->nc_nxt->nc_prev = ncp->nc_prev;
		else
			nchtail = ncp->nc_prev;
		remque(ncp);		/* remove from old hash chain */
		/* grab the inode we just found */
		ncp->nc_vp = ndp->ni_vp;
		/* fill in cache info */
		ncp->nc_dp = ndp->ni_dvp;	/* parents vnode */
		ncp->nc_nlen = ndp->ni_dent.d_namlen;
		bcopy(ndp->ni_dent.d_name, ncp->nc_name,
		    (unsigned)ncp->nc_nlen);
		/* link at end of lru chain */
		ncp->nc_nxt = NULL;
		ncp->nc_prev = nchtail;
		*nchtail = ncp;
		nchtail = &ncp->nc_nxt;
		/* and insert on hash chain */
		nhp = &nchash[NHASH(ndp->ni_vp)];
		insque(ncp, nhp);
	}
}

/*
 * Name cache initialization, from main() when we are booting
 */
nchinit()
{
	register union nchash *nchp;
	register struct namecache *ncp;

	nchhead = 0;
	nchtail = &nchhead;
	for (ncp = namecache; ncp < &namecache[nchsize]; ncp++) {
		ncp->nc_forw = ncp;			/* hash chain */
		ncp->nc_back = ncp;
		ncp->nc_nxt = NULL;			/* lru chain */
		*nchtail = ncp;
		ncp->nc_prev = nchtail;
		nchtail = &ncp->nc_nxt;
		/* all else is zero already */
	}
	for (nchp = nchash; nchp < &nchash[NCHHASH]; nchp++) {
		nchp->nch_head[0] = nchp;
		nchp->nch_head[1] = nchp;
	}
}

/*
 * Cache flush, a particular vnode; called when a vnode is renamed to
 * remove entries that would now be invalid
 *
 * The line "nxtcp = nchhead" near the end is to avoid potential problems
 * if the cache lru chain is modified while we are dumping the
 * inode.  This makes the algorithm O(n^2), but do you think I care?
 */
cache_purge(vp)
	register struct vnode *vp;
{
	register struct namecache *ncp, *nxtcp;

	for (ncp = nchhead; ncp; ncp = nxtcp) {
		nxtcp = ncp->nc_nxt;
		if (ncp->nc_vp == NULL || ncp->nc_vp != vp)
			continue;
		/* free the resources we had */
		ncp->nc_vp = NULL;
		ncp->nc_dp = NULL;
		remque(ncp);		/* remove entry from its hash chain */
		ncp->nc_forw = ncp;	/* and make a dummy one */
		ncp->nc_back = ncp;
		/* delete this entry from LRU chain */
		*ncp->nc_prev = nxtcp;
		if (nxtcp)
			nxtcp->nc_prev = ncp->nc_prev;
		else
			nchtail = ncp->nc_prev;
		/* cause rescan of list, it may have altered */
		nxtcp = nchhead;
		/* put the now-free entry at head of LRU */
		ncp->nc_nxt = nxtcp;
		ncp->nc_prev = &nchhead;
		nxtcp->nc_prev = &ncp->nc_nxt;
		nchhead = ncp;
	}
}

/*
 * Cache flush, a whole filesystem; called when filesys is umounted to
 * remove entries that would now be invalid
 *
 * The line "nxtcp = nchhead" near the end is to avoid potential problems
 * if the cache lru chain is modified while we are dumping the
 * inode.  This makes the algorithm O(n^2), but do you think I care?
 */
cache_purgevfs(mp)
	register struct mount *mp;
{
	register struct namecache *ncp, *nxtcp;

	for (ncp = nchhead; ncp; ncp = nxtcp) {
		nxtcp = ncp->nc_nxt;
		if (ncp->nc_vp == NULL || ncp->nc_vp->v_mount != mp)
			continue;
		/* free the resources we had */
		ncp->nc_vp = NULL;
		ncp->nc_dp = NULL;
		remque(ncp);		/* remove entry from its hash chain */
		ncp->nc_forw = ncp;	/* and make a dummy one */
		ncp->nc_back = ncp;
		/* delete this entry from LRU chain */
		*ncp->nc_prev = nxtcp;
		if (nxtcp)
			nxtcp->nc_prev = ncp->nc_prev;
		else
			nchtail = ncp->nc_prev;
		/* cause rescan of list, it may have altered */
		nxtcp = nchhead;
		/* put the now-free entry at head of LRU */
		ncp->nc_nxt = nxtcp;
		ncp->nc_prev = &nchhead;
		nxtcp->nc_prev = &ncp->nc_nxt;
		nchhead = ncp;
	}
}
Commit	Line	Data
6f7b6c68 KM	1	/*
	2	* Copyright (c) 1989 The Regents of the University of California.
	3	* All rights reserved.
	4	*
	5	* Redistribution and use in source and binary forms are permitted
	6	* provided that the above copyright notice and this paragraph are
	7	* duplicated in all such forms and that any documentation,
	8	* advertising materials, and other materials related to such
	9	* distribution and use acknowledge that the software was developed
	10	* by the University of California, Berkeley. The name of the
	11	* University may not be used to endorse or promote products derived
	12	* from this software without specific prior written permission.
	13	* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
	14	* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
	15	* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
	16	*
527dc51f	17	* @(#)vfs_cache.c 7.3 (Berkeley) %G%
6f7b6c68 KM	18	*/
	19
	20	#include "param.h"
	21	#include "systm.h"
	22	#include "time.h"
	23	#include "vnode.h"
6f7b6c68 KM	24	#include "namei.h"
	25
	26	/*
	27	* Name caching works as follows:
	28	*
	29	* Names found by directory scans are retained in a cache
	30	* for future reference. It is managed LRU, so frequently
	31	* used names will hang around. Cache is indexed by hash value
	32	* obtained from (ino,dev,name) where ino & dev refer to the
	33	* directory containing name.
	34	*
	35	* For simplicity (and economy of storage), names longer than
	36	* a maximum length of NCHNAMLEN are not cached; they occur
	37	* infrequently in any case, and are almost never of interest.
	38	*
	39	* Upon reaching the last segment of a path, if the reference
	40	* is for DELETE, or NOCACHE is set (rewrite), and the
	41	* name is located in the cache, it will be dropped.
	42	*/
	43
	44	/*
	45	* Structures associated with name cacheing.
	46	*/
	47	#define NCHHASH 128 /* size of hash table */
	48
	49	#if ((NCHHASH)&((NCHHASH)-1)) != 0
	50	#define NHASH(h) (((unsigned)(h) >> 6) % (NCHHASH))
	51	#else
	52	#define NHASH(h) (((unsigned)(h) >> 6) & ((NCHHASH)-1))
	53	#endif
	54
	55	union nchash {
	56	union nchash *nch_head[2];
	57	struct namecache *nch_chain[2];
	58	} nchash[NCHHASH];
	59	#define nch_forw nch_chain[0]
	60	#define nch_back nch_chain[1]
	61
	62	struct namecache nchhead, nchtail; / LRU chain pointers */
	63	struct nchstats nchstats; /* cache effectiveness statistics */
	64
	65	/*
	66	* Look for a the name in the cache. We don't do this
	67	* if the segment name is long, simply so the cache can avoid
	68	* holding long names (which would either waste space, or
	69	* add greatly to the complexity).
	70	*/
	71	struct vnode *
	72	cache_lookup(ndp)
	73	register struct nameidata *ndp;
	74	{
	75	register struct vnode *dp;
	76	register struct namecache *ncp;
	77	union nchash *nhp;
	78
527dc51f	79	return (0); /* XXX for now */
6f7b6c68 KM	80	if (ndp->ni_dent.d_namlen > NCHNAMLEN) {
	81	nchstats.ncs_long++;
	82	ndp->ni_makeentry = 0;
	83	return (0);
	84	}
	85	dp = ndp->ni_vp;
	86	nhp = &nchash[NHASH(dp)];
	87	for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp;
	88	ncp = ncp->nc_forw) {
	89	if (ncp->nc_vp == dp &&
	90	ncp->nc_nlen == ndp->ni_dent.d_namlen &&
	91	!bcmp(ncp->nc_name, ndp->ni_dent.d_name,
	92	(unsigned)ncp->nc_nlen))
	93	break;
	94	}
	95	if (ncp == (struct namecache *)nhp) {
	96	nchstats.ncs_miss++;
	97	ncp = NULL;
	98	return (0);
	99	}
	100	if (ndp->ni_makeentry) {
	101	/*
	102	* move this slot to end of LRU
	103	* chain, if not already there
	104	*/
	105	if (ncp->nc_nxt) {
	106	/* remove from LRU chain */
	107	*ncp->nc_prev = ncp->nc_nxt;
	108	ncp->nc_nxt->nc_prev = ncp->nc_prev;
	109
	110	/* and replace at end of it */
	111	ncp->nc_nxt = NULL;
	112	ncp->nc_prev = nchtail;
	113	*nchtail = ncp;
	114	nchtail = &ncp->nc_nxt;
	115	}
	116	/* ndp->ni_dent.d_ino = dp->i_number; */
	117	/* ni_dent.d_reclen is garbage ... */
	118	nchstats.ncs_goodhits++;
	119	return (ncp->nc_vp);
	120	}
	121
	122	/*
	123	* Last component and we are renaming or deleting,
	124	* the cache entry is invalid, or otherwise don't
	125	* want cache entry to exist.
	126	*/
	127	nchstats.ncs_badhits++;
	128	/* remove from LRU chain */
	129	*ncp->nc_prev = ncp->nc_nxt;
	130	if (ncp->nc_nxt)
	131	ncp->nc_nxt->nc_prev = ncp->nc_prev;
	132	else
	133	nchtail = ncp->nc_prev;
	134	remque(ncp); /* remove from hash chain */
	135	/* insert at head of LRU list (first to grab) */
	136	ncp->nc_nxt = nchhead;
	137	ncp->nc_prev = &nchhead;
	138	nchhead->nc_prev = &ncp->nc_nxt;
	139	nchhead = ncp;
	140	/* and make a dummy hash chain */
	141	ncp->nc_forw = ncp;
	142	ncp->nc_back = ncp;
	143	ncp = NULL;
144	return (0);
145	}
146
147	/*
148	* Add an entry to the cache
149	*/
150	cache_enter(ndp)
151	register struct nameidata *ndp;
152	{
153	register struct namecache *ncp;
154	union nchash *nhp;
155
527dc51f	156	return; /* XXX for now */
6f7b6c68 KM	157	/*
	158	* Free the cache slot at head of lru chain.
	159	*/
	160	if (ncp = nchhead) {
	161	/* remove from lru chain */
	162	*ncp->nc_prev = ncp->nc_nxt;
	163	if (ncp->nc_nxt)
	164	ncp->nc_nxt->nc_prev = ncp->nc_prev;
	165	else
	166	nchtail = ncp->nc_prev;
	167	remque(ncp); /* remove from old hash chain */
	168	/* grab the inode we just found */
	169	ncp->nc_vp = ndp->ni_vp;
	170	/* fill in cache info */
	171	ncp->nc_dp = ndp->ni_dvp; /* parents vnode */
	172	ncp->nc_nlen = ndp->ni_dent.d_namlen;
	173	bcopy(ndp->ni_dent.d_name, ncp->nc_name,
	174	(unsigned)ncp->nc_nlen);
	175	/* link at end of lru chain */
	176	ncp->nc_nxt = NULL;
	177	ncp->nc_prev = nchtail;
	178	*nchtail = ncp;
	179	nchtail = &ncp->nc_nxt;
	180	/* and insert on hash chain */
	181	nhp = &nchash[NHASH(ndp->ni_vp)];
	182	insque(ncp, nhp);
	183	}
	184	}
	185
	186	/*
	187	* Name cache initialization, from main() when we are booting
	188	*/
	189	nchinit()
	190	{
	191	register union nchash *nchp;
	192	register struct namecache *ncp;
	193
	194	nchhead = 0;
	195	nchtail = &nchhead;
	196	for (ncp = namecache; ncp < &namecache[nchsize]; ncp++) {
	197	ncp->nc_forw = ncp; /* hash chain */
	198	ncp->nc_back = ncp;
	199	ncp->nc_nxt = NULL; /* lru chain */
	200	*nchtail = ncp;
	201	ncp->nc_prev = nchtail;
	202	nchtail = &ncp->nc_nxt;
	203	/* all else is zero already */
	204	}
	205	for (nchp = nchash; nchp < &nchash[NCHHASH]; nchp++) {
	206	nchp->nch_head[0] = nchp;
	207	nchp->nch_head[1] = nchp;
	208	}
	209	}
	210
	211	/*
	212	* Cache flush, a particular vnode; called when a vnode is renamed to
	213	* remove entries that would now be invalid
	214	*
	215	* The line "nxtcp = nchhead" near the end is to avoid potential problems
	216	* if the cache lru chain is modified while we are dumping the
	217	* inode. This makes the algorithm O(n^2), but do you think I care?
	218	*/
	219	cache_purge(vp)
	220	register struct vnode *vp;
221	{
222	register struct namecache ncp, nxtcp;
223
224	for (ncp = nchhead; ncp; ncp = nxtcp) {
225	nxtcp = ncp->nc_nxt;
226	if (ncp->nc_vp == NULL \|\| ncp->nc_vp != vp)
227	continue;
228	/* free the resources we had */
229	ncp->nc_vp = NULL;
230	ncp->nc_dp = NULL;
231	remque(ncp); /* remove entry from its hash chain */
232	ncp->nc_forw = ncp; /* and make a dummy one */
233	ncp->nc_back = ncp;
234	/* delete this entry from LRU chain */
235	*ncp->nc_prev = nxtcp;
236	if (nxtcp)
237	nxtcp->nc_prev = ncp->nc_prev;
238	else
239	nchtail = ncp->nc_prev;
240	/* cause rescan of list, it may have altered */
241	nxtcp = nchhead;
242	/* put the now-free entry at head of LRU */
243	ncp->nc_nxt = nxtcp;
244	ncp->nc_prev = &nchhead;
245	nxtcp->nc_prev = &ncp->nc_nxt;
246	nchhead = ncp;
247	}
248	}
249
250	/*
251	* Cache flush, a whole filesystem; called when filesys is umounted to
252	* remove entries that would now be invalid
253	*
254	* The line "nxtcp = nchhead" near the end is to avoid potential problems
255	* if the cache lru chain is modified while we are dumping the
256	* inode. This makes the algorithm O(n^2), but do you think I care?
257	*/
258	cache_purgevfs(mp)
259	register struct mount *mp;
260	{
261	register struct namecache ncp, nxtcp;
262
263	for (ncp = nchhead; ncp; ncp = nxtcp) {
264	nxtcp = ncp->nc_nxt;
265	if (ncp->nc_vp == NULL \|\| ncp->nc_vp->v_mount != mp)
266	continue;
267	/* free the resources we had */
268	ncp->nc_vp = NULL;
269	ncp->nc_dp = NULL;
270	remque(ncp); /* remove entry from its hash chain */
271	ncp->nc_forw = ncp; /* and make a dummy one */
272	ncp->nc_back = ncp;
273	/* delete this entry from LRU chain */
274	*ncp->nc_prev = nxtcp;
275	if (nxtcp)
276	nxtcp->nc_prev = ncp->nc_prev;
277	else
278	nchtail = ncp->nc_prev;
279	/* cause rescan of list, it may have altered */
280	nxtcp = nchhead;
281	/* put the now-free entry at head of LRU */
282	ncp->nc_nxt = nxtcp;
283	ncp->nc_prev = &nchhead;
284	nxtcp->nc_prev = &ncp->nc_nxt;
285	nchhead = ncp;
286	}
287	}