vfs_dnlc.c

<B>Digital的Unix操作系统VAX 4.2源码</B>

#ifndef lint
static	char	*sccsid = "@(#)vfs_dnlc.c	4.2	(ULTRIX)	11/9/90";
#endif lint

/************************************************************************
 *									*
 *			Copyright (c) 1986 by				*
 *		Digital Equipment Corporation, Maynard, MA		*
 *			All rights reserved.				*
 *									*
 *   This software is furnished under a license and may be used and	*
 *   copied  only  in accordance with the terms of such license and	*
 *   with the  inclusion  of  the  above  copyright  notice.   This	*
 *   software  or  any  other copies thereof may not be provided or	*
 *   otherwise made available to any other person.  No title to and	*
 *   ownership of the software is hereby transferred.			*
 *									*
 *   This software is  derived  from  software  received  from  the	*
 *   University    of   California,   Berkeley,   and   from   Bell	*
 *   Laboratories.  Use, duplication, or disclosure is  subject  to	*
 *   restrictions  under  license  agreements  with  University  of	*
 *   California and with AT&T.						*
 *									*
 *   The information in this software is subject to change  without	*
 *   notice  and should not be construed as a commitment by Digital	*
 *   Equipment Corporation.						*
 *									*
 *   Digital assumes no responsibility for the use  or  reliability	*
 *   of its software on equipment which is not supplied by Digital.	*
 *									*
 ************************************************************************/

/*
 *	Portions of this software have been licensed to 
 *	Digital Equipment Company, Maynard, MA.
 *	Copyright (c) 1986 Sun Microsystems, Inc.  ALL RIGHTS RESERVED.
 */

#include "../h/types.h"
#include "../h/param.h"
#include "../h/time.h"
#include "../h/systm.h"
#include "../h/errno.h"
#include "../h/user.h"
#include "../net/rpc/types.h"
#include "../nfs/nfs.h"
#include "../nfs/vnode.h"
#include "../nfs/dnlc.h"
#include "../h/fs_types.h"

/*
 * 20 Jul 89 -- condylis
 *	Added hash2 and hash3 to speed up purges of cache entries
 *	referring to a vnode.
 *
 * 18 Jul 88 -- condylis
 *	Made directory name lookup cache operations SMP safe.  dnlc_lookup
 *	now increments ref count of gnode before returning.  This permitted
 *	me to keep all dnlc locking in this file.  
*/
/*
 * Directory name lookup cache.
 * Based on code originally done by Robert Els at Melbourne.
 *
 * Names found by directory scans are retained in a cache
 * for future referene.  It is managed LRU, so frequently
 * used names will hang around.  Cache is indexed by hash value
 * obtained from (vp, name) where the vp refers to the
 * directory containing the name.
 *
 * Hash2 and hash3 are optimized for purging the cache based on 
 * a vnode.  Hash2 is indexed by hash value obtained from the
 * address of the vnode of the directory containing the name.
 * Hash3 is indexed by a hash value obtained from the address of
 * the vnode returned from the lookup.
 *
 * For simplicity (and economy of storage), names longer than
 * some (small) maximum length are not cached, they occur
 * infrequently in any case, and are almost never of interest.
 */

#define NC_CHAIN_SIZE		12	/* the average size of a hash chain */

#define	NC_HASH1(namep, namlen, vp)	\
	((namep[0] + namep[namlen-1] + namlen + (u_int) vp) % nchashsize)
#define	NC_HASH2(vp)	\
	(((u_int)vp / (sizeof (struct gnode)))  % nchashsize)
#define	NC_HASH3(vp)	\
	(((u_int)vp / (sizeof (struct gnode)))  % nchashsize)

/*
 * Macros to insert, remove cache entries from hash, LRU lists.
 */
#define	INS_HASH1(ncp,nch)	insque(ncp, nch)
#define	RM_HASH1(ncp)		remque(ncp)
#define	INS_HASH2(ncp,nch)	insque2(ncp, nch)
#define	RM_HASH2(ncp)		remque2(ncp)
#define	INS_HASH3(ncp,nch)	insque3(ncp, nch)
#define	RM_HASH3(ncp)		remque3(ncp)

#define	INS_LRU(ncp1,ncp2)	insque4((struct ncache *) ncp1, (struct ncache *) ncp2)
#define	RM_LRU(ncp)		remque4((struct ncache *) ncp)

#define	NULL_HASH1(ncp)		(ncp)->hash1_next = (ncp)->hash1_prev = (ncp)
#define	NULL_HASH2(ncp)		(ncp)->hash2_next = (ncp)->hash2_prev = (ncp)
#define	NULL_HASH3(ncp)		(ncp)->hash3_next = (ncp)->hash3_prev = (ncp)

#define NOT_NULL1(ncp)		(ncp)->hash1_next != (ncp)

/*
 * Stats on usefulness of name cache.
 */
struct	ncstats {
	int	hits;		/* hits that we can really use */
	int	misses;		/* cache misses */
	int	enters;		/* number of enters done */
	int	dbl_enters;	/* number of enters tried when already cached */
	int	long_enter;	/* long names tried to enter */
	int	long_look;	/* long names tried to look up */
	int	lru_empty;	/* LRU list empty */
	int	hashedentries;	/* current number of hashed entries */
	int	purges;		/* number of purges of cache */
	int	purgevp;	/* number of calls to dnlc_purge_vp */
	int 	purgevpworked;	/* number of calls to dnlc_purge_vp that */
				/* purged something 			*/
	int	purge1yes;	/* number of dnlc_purge1 successes */
	int	purge1no;	/* number of dnlc_purge1 failures */
};

/*
 * Hash list of name cache entries for fast lookup.
 */
struct	nc_hash {
	struct  ncache  *hash1_next, *hash1_prev;/* lookup hash chain */
	struct  ncache  *hash2_next, *hash2_prev;/* parent vnode hash chain */
	struct  ncache  *hash3_next, *hash3_prev;/* looked up vnode hash chain*/
} *nc_hash1;

/*
 * Hash list of name cache entries for fast purge based on parent gp.
 */
struct nc_hash *nc_hash2;

/*
 * Hash list of name cache entries for fast purge based on looked up gp.
 */
struct nc_hash *nc_hash3;

/*
 * LRU list of cache entries for aging.
 */
struct	nc_lru	{
        struct  ncache  *hash1_next, *hash1_prev;/* lookup hash chain */
        struct  ncache  *hash2_next, *hash2_prev;/* parent vnode hash chain */
        struct  ncache  *hash3_next, *hash3_prev;/* looked up vnode hash chain*/
        struct  ncache  *lru_next, *lru_prev;   /* LRU chain */
} nc_lru;

struct ncache *ncache;		/* the cache itself */
int ncsize = 0;			/* size of cache, computed by dnlc_init() */
int nchashsize = 0;		/* number of hash chains, function of ncsize*/

struct	ncstats ncstats;		/* cache effectiveness statistics */

struct ncache *dnlc_search();
int	dnlc_cache = 1;
struct	lock_t	lk_nfsdnlc;		/* SMP lock for directory name
					/* lookup cache and related 
					/* statistics		  */

/*
 * Initialize the directory cache.
 * Put all the entries on the LRU chain and clear out the hash links.
 */
dnlc_init()
{
	register struct ncache *ncp;
	register int i;
	extern int ngnode;

	/*
	 * Allocate cache based on system "size"
	 */
	if (!ncsize) {
		ncsize = ngnode;
#ifdef UFS
		ncsize -= ncsize/4;	/* downsize cache when UFS present */
#endif UFS
	}

	KM_ALLOC(ncache, struct ncache *,
		 (u_int)(ncsize * sizeof(struct ncache)), KM_NFS,
		 KM_CONTIG | KM_CLEAR | KM_NOWAIT);
	if (ncache == NULL) {
		printf("dnlc_init: can't km_alloc %d\n",
		       ncsize * sizeof(struct ncache));
		panic("dnlc_init");
	}

	/*
	 * number of hash chains
	 */
	nchashsize = ncsize / NC_CHAIN_SIZE;

	KM_ALLOC(nc_hash1, struct nc_hash *,
		 (u_int)(3 * nchashsize * sizeof(struct nc_hash)), KM_NFS,
		 KM_CONTIG | KM_CLEAR | KM_NOWAIT);
	if (nc_hash1 == NULL) {
		printf("dnlc_init: can't km_alloc %d\n",
		       nchashsize * sizeof(struct nc_hash));
		panic("dnlc_init");
	}
	nc_hash2 = &nc_hash1[nchashsize];
	nc_hash3 = &nc_hash2[nchashsize];

	nc_lru.lru_next = (struct ncache *) &nc_lru;
	nc_lru.lru_prev = (struct ncache *) &nc_lru;
	for (i = 0; i < ncsize; i++) {
		ncp = &ncache[i];
		INS_LRU(ncp, &nc_lru);
		NULL_HASH1(ncp);
		NULL_HASH2(ncp);
		NULL_HASH3(ncp);
		ncp->dp = ncp->vp = (struct vnode *) 0;
	}
	for (i = 0; i < nchashsize; i++) {
		ncp = (struct ncache *) &nc_hash1[i];
		NULL_HASH1(ncp);
		ncp = (struct ncache *) &nc_hash2[i];
		NULL_HASH2(ncp);
		ncp = (struct ncache *) &nc_hash3[i];
		NULL_HASH3(ncp);
	}
}

/*
 * Add a name to the directory cahce.
 */
dnlc_enter(dp, name, vp, cred)
	register struct vnode *dp;
	register char *name;
	struct vnode *vp;
	struct ucred *cred;
{
	register int namlen;
	register struct ncache *ncp;
	register int hash1, hash2, hash3;
	struct vnode *tdp;
	struct vnode *tvp;

	if (!dnlc_cache) {
		return;
	}
	namlen = strlen(name);
	if (namlen > NC_NAMLEN) {
		/* SMP lock name cache statistics during access */
		smp_lock(&lk_nfsdnlc, LK_RETRY);
		ncstats.long_enter++;
		smp_unlock(&lk_nfsdnlc);
		return;
	}
	hash1 = NC_HASH1(name, namlen, dp);
	/* SMP lock access to directory name lookup cache */
	smp_lock(&lk_nfsdnlc, LK_RETRY);
	ncp = dnlc_search(dp, name, namlen, hash1, cred);
	if (ncp != (struct ncache *) 0) {
		ncstats.dbl_enters++;
		smp_unlock(&lk_nfsdnlc);
		return;
	}
	/*
	 * Take least recently used cache struct.
	 */
	ncp = nc_lru.lru_next;
	if (ncp == (struct ncache *) &nc_lru) {	/* LRU queue empty */
		ncstats.lru_empty++;
		smp_unlock(&lk_nfsdnlc);
		return;
	}
	/*
	 * Remove from LRU, hash chains.
	 */
	RM_LRU(ncp);
	if (NOT_NULL1(ncp)) {
		ncstats.hashedentries--;
		RM_HASH1(ncp);
		RM_HASH2(ncp);
		RM_HASH3(ncp);
	}

	/*
	 * Save references to vnodes.  We'll release them after unlocking
	 * dnlc.  Must follow lock ordering rules.
	 */
	tdp = ncp->dp;
	tvp = ncp->vp;


	/* make sure the cred associated with the vnode gets freed */
	if (ncp->cred != NOCRED) {   
		crfree(ncp->cred);
	}

	/*
	 * Hold the vnodes we are entering and
	 * fill in cache info.
	 */
	ncp->dp = dp;
	VN_HOLD(dp);
	ncp->vp = vp;
	VN_HOLD(vp);
	ncp->namlen = namlen;
	bcopy(name, ncp->name, (unsigned)namlen);
	ncp->cred = cred;
	if (cred != NOCRED) {
		crhold(cred);
	}
	/*
	 * Insert in LRU, hash chains.
	 */
	hash2 = NC_HASH2(dp);
	hash3 = NC_HASH3(vp);
	INS_LRU(ncp, nc_lru.lru_prev);
	ncstats.hashedentries++;
	INS_HASH1(ncp, &nc_hash1[hash1]);
	INS_HASH2(ncp, &nc_hash2[hash2]);
	INS_HASH3(ncp, &nc_hash3[hash3]);
	ncstats.enters++;
	smp_unlock(&lk_nfsdnlc);
	/*
	 * Drop hold on vnodes (if we had any).
	 */
	if (tdp != (struct vnode *) 0) {
		VN_RELE(tdp);
	}