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

#include "param.h"
#include "systm.h"
#include "time.h"
#include "vnode.h"
#include "namei.h"
#include "errno.h"
#include "malloc.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.
 */
union nchash {
	union	nchash *nch_head[2];
	struct	namecache *nch_chain[2];
} *nchashtbl;
#define	nch_forw	nch_chain[0]
#define	nch_back	nch_chain[1]

u_long	nchash;				/* size of hash table - 1 */
long	numcache;			/* number of cache entries allocated */
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 = &nchashtbl[ndp->ni_hash & nchash];
	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 (numcache < desiredvnodes) {
		ncp = (struct namecache *)
			malloc(sizeof *ncp, M_CACHE, M_WAITOK);
		bzero((char *)ncp, sizeof *ncp);
		numcache++;
	} else 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);
	} else
		return;
	/* grab the vnode 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 = &nchashtbl[ndp->ni_hash & nchash];
	insque(ncp, nhp);
}

/*
 * Name cache initialization, from vfs_init() when we are booting
 */
nchinit()
{
	register union nchash *nchp;
	long nchashsize;

	nchhead = 0;
	nchtail = &nchhead;
	nchashsize = roundup((desiredvnodes + 1) * sizeof *nchp / 2,
		NBPG * CLSIZE);
	nchashtbl = (union nchash *)malloc(nchashsize, M_CACHE, M_WAITOK);
	for (nchash = 1; nchash <= nchashsize / sizeof *nchp; nchash <<= 1)
		/* void */;
	nchash = (nchash >> 1) - 1;
	for (nchp = &nchashtbl[nchash]; nchp >= nchashtbl; 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;
{
	union nchash *nhp;
	struct namecache *ncp;

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