[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.4 (Berkeley) %G%
 */

#include "param.h"
#include "systm.h"
#include "time.h"
#include "vnode.h"
#include "namei.h"
#include "errno.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 (vp, name) where vp refers 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(vp, h)	((((unsigned)(h) >> 6) + (h)) % (NCHHASH))
#else
#define	NHASH(vp, h)	((((unsigned)(h) >> 6) + (h)) & ((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 */

int doingcache = 1;			/* 1 => enable the cache */

/*
 * 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).
 *
 * Lookup is called with ni_dvp pointing to the directory to search,
 * ni_ptr pointing to the name of the entry being sought, ni_namelen
 * tells the length of the name, and ni_hash contains a hash of
 * the name. If the lookup succeeds, the vnode is returned in ni_vp
 * and a status of -1 is returned. If the lookup determines that
 * the name does not exist (negative cacheing), a status of ENOENT
 * is returned. If the lookup fails, a status of zero is returned.
 */
cache_lookup(ndp)
	register struct nameidata *ndp;
{
	register struct vnode *dvp;
	register struct namecache *ncp;
	union nchash *nhp;

	if (!doingcache)
		return (0);
	if (ndp->ni_namelen > NCHNAMLEN) {
		nchstats.ncs_long++;
		ndp->ni_makeentry = 0;
		return (0);
	}
	dvp = ndp->ni_dvp;
	nhp = &nchash[NHASH(dvp, ndp->ni_hash)];
	for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp;
	    ncp = ncp->nc_forw) {
		if (ncp->nc_dvp == dvp &&
		    ncp->nc_dvpid == dvp->v_id &&
		    ncp->nc_nlen == ndp->ni_namelen &&
		    !bcmp(ncp->nc_name, ndp->ni_ptr, (unsigned)ncp->nc_nlen))
			break;
	}
	if (ncp == (struct namecache *)nhp) {
		nchstats.ncs_miss++;
		return (0);
	}
	if (!ndp->ni_makeentry) {
		nchstats.ncs_badhits++;
	} else if (ncp->nc_vp == NULL) {
		nchstats.ncs_neghits++;
		/*
		 * 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;
		}
		return (ENOENT);
	} else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
		nchstats.ncs_falsehits++;
	} else {
		nchstats.ncs_goodhits++;
		/*
		 * 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_vp = ncp->nc_vp;
		return (-1);
	}

	/*
	 * Last component and we are renaming or deleting,
	 * the cache entry is invalid, or otherwise don't
	 * want cache entry to exist.
	 */
	/* 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;
	/* remove from hash chain */
	remque(ncp);
	/* 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;
	return (0);
}

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

	if (!doingcache)
		return;
	/*
	 * 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;
		/* remove from old hash chain */
		remque(ncp);
		/* grab the inode we just found */
		ncp->nc_vp = ndp->ni_vp;
		if (ndp->ni_vp)
			ncp->nc_vpid = ndp->ni_vp->v_id;
		else
			ncp->nc_vpid = 0;
		/* fill in cache info */
		ncp->nc_dvp = ndp->ni_dvp;
		ncp->nc_dvpid = ndp->ni_dvp->v_id;
		ncp->nc_nlen = ndp->ni_namelen;
		bcopy(ndp->ni_ptr, 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, ndp->ni_hash)];
		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
 * hide entries that would now be invalid
 */
cache_purge(vp)
	struct vnode *vp;
{
	struct namecache *ncp;

	vp->v_id = ++nextvnodeid;
	if (nextvnodeid != 0)
		return;
	for (ncp = namecache; ncp < &namecache[nchsize]; ncp++) {
		ncp->nc_vpid = 0;
		ncp->nc_dvpid = 0;
	}
	vp->v_id = ++nextvnodeid;
}

/*
 * 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_dvp == NULL || ncp->nc_dvp->v_mount != mp)
			continue;
		/* free the resources we had */
		ncp->nc_vp = NULL;
		ncp->nc_dvp = 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	*
ea5eb849	17	* @(#)vfs_cache.c 7.4 (Berkeley) %G%
6f7b6c68 KM	18	*/
	19
	20	#include "param.h"
	21	#include "systm.h"
	22	#include "time.h"
	23	#include "vnode.h"
6f7b6c68	24	#include "namei.h"
ea5eb849	25	#include "errno.h"
6f7b6c68 KM	26
	27	/*
	28	* Name caching works as follows:
	29	*
	30	* Names found by directory scans are retained in a cache
	31	* for future reference. It is managed LRU, so frequently
	32	* used names will hang around. Cache is indexed by hash value
ea5eb849 KM	33	* obtained from (vp, name) where vp refers to the directory
ea5eb849 KM	34	* containing name.
6f7b6c68 KM	35	*
	36	* For simplicity (and economy of storage), names longer than
	37	* a maximum length of NCHNAMLEN are not cached; they occur
	38	* infrequently in any case, and are almost never of interest.
	39	*
	40	* Upon reaching the last segment of a path, if the reference
	41	* is for DELETE, or NOCACHE is set (rewrite), and the
	42	* name is located in the cache, it will be dropped.
	43	*/
	44
	45	/*
	46	* Structures associated with name cacheing.
	47	*/
	48	#define NCHHASH 128 /* size of hash table */
	49
	50	#if ((NCHHASH)&((NCHHASH)-1)) != 0
ea5eb849	51	#define NHASH(vp, h) ((((unsigned)(h) >> 6) + (h)) % (NCHHASH))
6f7b6c68	52	#else
ea5eb849	53	#define NHASH(vp, h) ((((unsigned)(h) >> 6) + (h)) & ((NCHHASH)-1))
6f7b6c68 KM	54	#endif
	55
	56	union nchash {
	57	union nchash *nch_head[2];
	58	struct namecache *nch_chain[2];
	59	} nchash[NCHHASH];
	60	#define nch_forw nch_chain[0]
	61	#define nch_back nch_chain[1]
	62
	63	struct namecache nchhead, nchtail; / LRU chain pointers */
	64	struct nchstats nchstats; /* cache effectiveness statistics */
	65
ea5eb849 KM	66	int doingcache = 1; /* 1 => enable the cache */
ea5eb849 KM	67
6f7b6c68 KM	68	/*
	69	* Look for a the name in the cache. We don't do this
	70	* if the segment name is long, simply so the cache can avoid
	71	* holding long names (which would either waste space, or
	72	* add greatly to the complexity).
ea5eb849 KM	73	*
	74	* Lookup is called with ni_dvp pointing to the directory to search,
	75	* ni_ptr pointing to the name of the entry being sought, ni_namelen
	76	* tells the length of the name, and ni_hash contains a hash of
	77	* the name. If the lookup succeeds, the vnode is returned in ni_vp
	78	* and a status of -1 is returned. If the lookup determines that
	79	* the name does not exist (negative cacheing), a status of ENOENT
	80	* is returned. If the lookup fails, a status of zero is returned.
6f7b6c68	81	*/
6f7b6c68 KM	82	cache_lookup(ndp)
	83	register struct nameidata *ndp;
	84	{
ea5eb849	85	register struct vnode *dvp;
6f7b6c68 KM	86	register struct namecache *ncp;
	87	union nchash *nhp;
	88
ea5eb849 KM	89	if (!doingcache)
	90	return (0);
	91	if (ndp->ni_namelen > NCHNAMLEN) {
6f7b6c68 KM	92	nchstats.ncs_long++;
	93	ndp->ni_makeentry = 0;
	94	return (0);
	95	}
ea5eb849 KM	96	dvp = ndp->ni_dvp;
ea5eb849 KM	97	nhp = &nchash[NHASH(dvp, ndp->ni_hash)];
6f7b6c68 KM	98	for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp;
6f7b6c68 KM	99	ncp = ncp->nc_forw) {
ea5eb849 KM	100	if (ncp->nc_dvp == dvp &&
	101	ncp->nc_dvpid == dvp->v_id &&
	102	ncp->nc_nlen == ndp->ni_namelen &&
	103	!bcmp(ncp->nc_name, ndp->ni_ptr, (unsigned)ncp->nc_nlen))
6f7b6c68 KM	104	break;
	105	}
	106	if (ncp == (struct namecache *)nhp) {
	107	nchstats.ncs_miss++;
6f7b6c68 KM	108	return (0);
6f7b6c68 KM	109	}
ea5eb849 KM	110	if (!ndp->ni_makeentry) {
	111	nchstats.ncs_badhits++;
	112	} else if (ncp->nc_vp == NULL) {
	113	nchstats.ncs_neghits++;
6f7b6c68	114	/*
ea5eb849	115	* move this slot to end of LRU chain, if not already there
6f7b6c68 KM	116	*/
	117	if (ncp->nc_nxt) {
	118	/* remove from LRU chain */
	119	*ncp->nc_prev = ncp->nc_nxt;
	120	ncp->nc_nxt->nc_prev = ncp->nc_prev;
6f7b6c68 KM	121	/* and replace at end of it */
	122	ncp->nc_nxt = NULL;
	123	ncp->nc_prev = nchtail;
	124	*nchtail = ncp;
	125	nchtail = &ncp->nc_nxt;
	126	}
ea5eb849 KM	127	return (ENOENT);
	128	} else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
	129	nchstats.ncs_falsehits++;
	130	} else {
6f7b6c68	131	nchstats.ncs_goodhits++;
ea5eb849 KM	132	/*
	133	* move this slot to end of LRU chain, if not already there
	134	*/
	135	if (ncp->nc_nxt) {
	136	/* remove from LRU chain */
	137	*ncp->nc_prev = ncp->nc_nxt;
	138	ncp->nc_nxt->nc_prev = ncp->nc_prev;
	139	/* and replace at end of it */
	140	ncp->nc_nxt = NULL;
	141	ncp->nc_prev = nchtail;
	142	*nchtail = ncp;
	143	nchtail = &ncp->nc_nxt;
	144	}
	145	ndp->ni_vp = ncp->nc_vp;
	146	return (-1);
6f7b6c68 KM	147	}
	148
	149	/*
	150	* Last component and we are renaming or deleting,
	151	* the cache entry is invalid, or otherwise don't
	152	* want cache entry to exist.
	153	*/
6f7b6c68 KM	154	/* remove from LRU chain */
	155	*ncp->nc_prev = ncp->nc_nxt;
	156	if (ncp->nc_nxt)
	157	ncp->nc_nxt->nc_prev = ncp->nc_prev;
	158	else
	159	nchtail = ncp->nc_prev;
ea5eb849 KM	160	/* remove from hash chain */
ea5eb849 KM	161	remque(ncp);
6f7b6c68 KM	162	/* insert at head of LRU list (first to grab) */
	163	ncp->nc_nxt = nchhead;
	164	ncp->nc_prev = &nchhead;
	165	nchhead->nc_prev = &ncp->nc_nxt;
	166	nchhead = ncp;
	167	/* and make a dummy hash chain */
	168	ncp->nc_forw = ncp;
	169	ncp->nc_back = ncp;
6f7b6c68 KM	170	return (0);
	171	}
	172
	173	/*
	174	* Add an entry to the cache
	175	*/
	176	cache_enter(ndp)
	177	register struct nameidata *ndp;
	178	{
	179	register struct namecache *ncp;
	180	union nchash *nhp;
	181
ea5eb849 KM	182	if (!doingcache)
ea5eb849 KM	183	return;
6f7b6c68 KM	184	/*
	185	* Free the cache slot at head of lru chain.
	186	*/
	187	if (ncp = nchhead) {
	188	/* remove from lru chain */
	189	*ncp->nc_prev = ncp->nc_nxt;
	190	if (ncp->nc_nxt)
	191	ncp->nc_nxt->nc_prev = ncp->nc_prev;
	192	else
	193	nchtail = ncp->nc_prev;
ea5eb849 KM	194	/* remove from old hash chain */
ea5eb849 KM	195	remque(ncp);
6f7b6c68 KM	196	/* grab the inode we just found */
6f7b6c68 KM	197	ncp->nc_vp = ndp->ni_vp;
ea5eb849 KM	198	if (ndp->ni_vp)
	199	ncp->nc_vpid = ndp->ni_vp->v_id;
	200	else
	201	ncp->nc_vpid = 0;
6f7b6c68	202	/* fill in cache info */
ea5eb849 KM	203	ncp->nc_dvp = ndp->ni_dvp;
	204	ncp->nc_dvpid = ndp->ni_dvp->v_id;
	205	ncp->nc_nlen = ndp->ni_namelen;
	206	bcopy(ndp->ni_ptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
6f7b6c68 KM	207	/* link at end of lru chain */
	208	ncp->nc_nxt = NULL;
	209	ncp->nc_prev = nchtail;
	210	*nchtail = ncp;
	211	nchtail = &ncp->nc_nxt;
	212	/* and insert on hash chain */
ea5eb849	213	nhp = &nchash[NHASH(ndp->ni_vp, ndp->ni_hash)];
6f7b6c68 KM	214	insque(ncp, nhp);
	215	}
	216	}
	217
	218	/*
	219	* Name cache initialization, from main() when we are booting
	220	*/
	221	nchinit()
	222	{
	223	register union nchash *nchp;
	224	register struct namecache *ncp;
	225
	226	nchhead = 0;
	227	nchtail = &nchhead;
	228	for (ncp = namecache; ncp < &namecache[nchsize]; ncp++) {
	229	ncp->nc_forw = ncp; /* hash chain */
	230	ncp->nc_back = ncp;
	231	ncp->nc_nxt = NULL; /* lru chain */
	232	*nchtail = ncp;
	233	ncp->nc_prev = nchtail;
	234	nchtail = &ncp->nc_nxt;
	235	/* all else is zero already */
	236	}
	237	for (nchp = nchash; nchp < &nchash[NCHHASH]; nchp++) {
	238	nchp->nch_head[0] = nchp;
	239	nchp->nch_head[1] = nchp;
	240	}
	241	}
	242
	243	/*
	244	* Cache flush, a particular vnode; called when a vnode is renamed to
ea5eb849	245	* hide entries that would now be invalid
6f7b6c68 KM	246	*/
6f7b6c68 KM	247	cache_purge(vp)
ea5eb849	248	struct vnode *vp;
6f7b6c68	249	{
ea5eb849	250	struct namecache *ncp;
6f7b6c68	251
ea5eb849 KM	252	vp->v_id = ++nextvnodeid;
	253	if (nextvnodeid != 0)
	254	return;
	255	for (ncp = namecache; ncp < &namecache[nchsize]; ncp++) {
	256	ncp->nc_vpid = 0;
	257	ncp->nc_dvpid = 0;
6f7b6c68	258	}
ea5eb849	259	vp->v_id = ++nextvnodeid;
6f7b6c68 KM	260	}
	261
	262	/*
	263	* Cache flush, a whole filesystem; called when filesys is umounted to
	264	* remove entries that would now be invalid
	265	*
	266	* The line "nxtcp = nchhead" near the end is to avoid potential problems
	267	* if the cache lru chain is modified while we are dumping the
	268	* inode. This makes the algorithm O(n^2), but do you think I care?
	269	*/
	270	cache_purgevfs(mp)
	271	register struct mount *mp;
	272	{
	273	register struct namecache ncp, nxtcp;
	274
	275	for (ncp = nchhead; ncp; ncp = nxtcp) {
	276	nxtcp = ncp->nc_nxt;
ea5eb849	277	if (ncp->nc_dvp == NULL \|\| ncp->nc_dvp->v_mount != mp)
6f7b6c68 KM	278	continue;
	279	/* free the resources we had */
	280	ncp->nc_vp = NULL;
ea5eb849	281	ncp->nc_dvp = NULL;
6f7b6c68 KM	282	remque(ncp); /* remove entry from its hash chain */
	283	ncp->nc_forw = ncp; /* and make a dummy one */
	284	ncp->nc_back = ncp;
	285	/* delete this entry from LRU chain */
	286	*ncp->nc_prev = nxtcp;
	287	if (nxtcp)
	288	nxtcp->nc_prev = ncp->nc_prev;
	289	else
	290	nchtail = ncp->nc_prev;
	291	/* cause rescan of list, it may have altered */
	292	nxtcp = nchhead;
	293	/* put the now-free entry at head of LRU */
	294	ncp->nc_nxt = nxtcp;
	295	ncp->nc_prev = &nchhead;
	296	nxtcp->nc_prev = &ncp->nc_nxt;
	297	nchhead = ncp;
	298	}
	299	}