Home | History | Annotate | Line # | Download | only in kern
vfs_cache.c revision 1.5
      1  1.1      cgd /*
      2  1.5  mycroft  * Copyright (c) 1989, 1993
      3  1.5  mycroft  *	The Regents of the University of California.  All rights reserved.
      4  1.1      cgd  *
      5  1.1      cgd  * Redistribution and use in source and binary forms, with or without
      6  1.1      cgd  * modification, are permitted provided that the following conditions
      7  1.1      cgd  * are met:
      8  1.1      cgd  * 1. Redistributions of source code must retain the above copyright
      9  1.1      cgd  *    notice, this list of conditions and the following disclaimer.
     10  1.1      cgd  * 2. Redistributions in binary form must reproduce the above copyright
     11  1.1      cgd  *    notice, this list of conditions and the following disclaimer in the
     12  1.1      cgd  *    documentation and/or other materials provided with the distribution.
     13  1.1      cgd  * 3. All advertising materials mentioning features or use of this software
     14  1.1      cgd  *    must display the following acknowledgement:
     15  1.1      cgd  *	This product includes software developed by the University of
     16  1.1      cgd  *	California, Berkeley and its contributors.
     17  1.1      cgd  * 4. Neither the name of the University nor the names of its contributors
     18  1.1      cgd  *    may be used to endorse or promote products derived from this software
     19  1.1      cgd  *    without specific prior written permission.
     20  1.1      cgd  *
     21  1.1      cgd  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     22  1.1      cgd  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     23  1.1      cgd  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     24  1.1      cgd  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     25  1.1      cgd  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     26  1.1      cgd  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     27  1.1      cgd  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     28  1.1      cgd  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     29  1.1      cgd  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     30  1.1      cgd  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     31  1.1      cgd  * SUCH DAMAGE.
     32  1.1      cgd  *
     33  1.5  mycroft  *	from: @(#)vfs_cache.c	8.1 (Berkeley) 6/10/93
     34  1.5  mycroft  *	$Id: vfs_cache.c,v 1.5 1994/06/08 11:28:50 mycroft Exp $
     35  1.1      cgd  */
     36  1.1      cgd 
     37  1.4  mycroft #include <sys/param.h>
     38  1.4  mycroft #include <sys/systm.h>
     39  1.4  mycroft #include <sys/time.h>
     40  1.4  mycroft #include <sys/mount.h>
     41  1.4  mycroft #include <sys/vnode.h>
     42  1.4  mycroft #include <sys/namei.h>
     43  1.4  mycroft #include <sys/errno.h>
     44  1.4  mycroft #include <sys/malloc.h>
     45  1.1      cgd 
     46  1.1      cgd /*
     47  1.1      cgd  * Name caching works as follows:
     48  1.1      cgd  *
     49  1.1      cgd  * Names found by directory scans are retained in a cache
     50  1.1      cgd  * for future reference.  It is managed LRU, so frequently
     51  1.1      cgd  * used names will hang around.  Cache is indexed by hash value
     52  1.1      cgd  * obtained from (vp, name) where vp refers to the directory
     53  1.1      cgd  * containing name.
     54  1.1      cgd  *
     55  1.1      cgd  * For simplicity (and economy of storage), names longer than
     56  1.1      cgd  * a maximum length of NCHNAMLEN are not cached; they occur
     57  1.1      cgd  * infrequently in any case, and are almost never of interest.
     58  1.1      cgd  *
     59  1.1      cgd  * Upon reaching the last segment of a path, if the reference
     60  1.1      cgd  * is for DELETE, or NOCACHE is set (rewrite), and the
     61  1.1      cgd  * name is located in the cache, it will be dropped.
     62  1.1      cgd  */
     63  1.1      cgd 
     64  1.1      cgd /*
     65  1.1      cgd  * Structures associated with name cacheing.
     66  1.1      cgd  */
     67  1.5  mycroft struct namecache **nchashtbl;
     68  1.1      cgd u_long	nchash;				/* size of hash table - 1 */
     69  1.1      cgd long	numcache;			/* number of cache entries allocated */
     70  1.1      cgd struct	namecache *nchhead, **nchtail;	/* LRU chain pointers */
     71  1.1      cgd struct	nchstats nchstats;		/* cache effectiveness statistics */
     72  1.1      cgd 
     73  1.1      cgd int doingcache = 1;			/* 1 => enable the cache */
     74  1.1      cgd 
     75  1.1      cgd /*
     76  1.1      cgd  * Look for a the name in the cache. We don't do this
     77  1.1      cgd  * if the segment name is long, simply so the cache can avoid
     78  1.1      cgd  * holding long names (which would either waste space, or
     79  1.1      cgd  * add greatly to the complexity).
     80  1.1      cgd  *
     81  1.1      cgd  * Lookup is called with ni_dvp pointing to the directory to search,
     82  1.1      cgd  * ni_ptr pointing to the name of the entry being sought, ni_namelen
     83  1.1      cgd  * tells the length of the name, and ni_hash contains a hash of
     84  1.5  mycroft  * the name. If the lookup succeeds, the vnode is returned in ni_vp
     85  1.5  mycroft  * and a status of -1 is returned. If the lookup determines that
     86  1.5  mycroft  * the name does not exist (negative cacheing), a status of ENOENT
     87  1.5  mycroft  * is returned. If the lookup fails, a status of zero is returned.
     88  1.1      cgd  */
     89  1.5  mycroft int
     90  1.5  mycroft cache_lookup(dvp, vpp, cnp)
     91  1.5  mycroft 	struct vnode *dvp;
     92  1.5  mycroft 	struct vnode **vpp;
     93  1.5  mycroft 	struct componentname *cnp;
     94  1.1      cgd {
     95  1.5  mycroft 	register struct namecache *ncp, *ncq, **ncpp;
     96  1.1      cgd 
     97  1.1      cgd 	if (!doingcache)
     98  1.1      cgd 		return (0);
     99  1.5  mycroft 	if (cnp->cn_namelen > NCHNAMLEN) {
    100  1.1      cgd 		nchstats.ncs_long++;
    101  1.5  mycroft 		cnp->cn_flags &= ~MAKEENTRY;
    102  1.1      cgd 		return (0);
    103  1.1      cgd 	}
    104  1.5  mycroft 	ncpp = &nchashtbl[cnp->cn_hash & nchash];
    105  1.5  mycroft 	for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) {
    106  1.1      cgd 		if (ncp->nc_dvp == dvp &&
    107  1.1      cgd 		    ncp->nc_dvpid == dvp->v_id &&
    108  1.5  mycroft 		    ncp->nc_nlen == cnp->cn_namelen &&
    109  1.5  mycroft 		    !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
    110  1.1      cgd 			break;
    111  1.1      cgd 	}
    112  1.5  mycroft 	if (ncp == NULL) {
    113  1.1      cgd 		nchstats.ncs_miss++;
    114  1.1      cgd 		return (0);
    115  1.1      cgd 	}
    116  1.5  mycroft 	if (!(cnp->cn_flags & MAKEENTRY)) {
    117  1.1      cgd 		nchstats.ncs_badhits++;
    118  1.1      cgd 	} else if (ncp->nc_vp == NULL) {
    119  1.5  mycroft 		if (cnp->cn_nameiop != CREATE) {
    120  1.1      cgd 			nchstats.ncs_neghits++;
    121  1.1      cgd 			/*
    122  1.1      cgd 			 * Move this slot to end of LRU chain,
    123  1.1      cgd 			 * if not already there.
    124  1.1      cgd 			 */
    125  1.1      cgd 			if (ncp->nc_nxt) {
    126  1.1      cgd 				/* remove from LRU chain */
    127  1.1      cgd 				*ncp->nc_prev = ncp->nc_nxt;
    128  1.1      cgd 				ncp->nc_nxt->nc_prev = ncp->nc_prev;
    129  1.1      cgd 				/* and replace at end of it */
    130  1.1      cgd 				ncp->nc_nxt = NULL;
    131  1.1      cgd 				ncp->nc_prev = nchtail;
    132  1.1      cgd 				*nchtail = ncp;
    133  1.1      cgd 				nchtail = &ncp->nc_nxt;
    134  1.1      cgd 			}
    135  1.1      cgd 			return (ENOENT);
    136  1.1      cgd 		}
    137  1.1      cgd 	} else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
    138  1.1      cgd 		nchstats.ncs_falsehits++;
    139  1.1      cgd 	} else {
    140  1.1      cgd 		nchstats.ncs_goodhits++;
    141  1.1      cgd 		/*
    142  1.1      cgd 		 * move this slot to end of LRU chain, if not already there
    143  1.1      cgd 		 */
    144  1.1      cgd 		if (ncp->nc_nxt) {
    145  1.1      cgd 			/* remove from LRU chain */
    146  1.1      cgd 			*ncp->nc_prev = ncp->nc_nxt;
    147  1.1      cgd 			ncp->nc_nxt->nc_prev = ncp->nc_prev;
    148  1.1      cgd 			/* and replace at end of it */
    149  1.1      cgd 			ncp->nc_nxt = NULL;
    150  1.1      cgd 			ncp->nc_prev = nchtail;
    151  1.1      cgd 			*nchtail = ncp;
    152  1.1      cgd 			nchtail = &ncp->nc_nxt;
    153  1.1      cgd 		}
    154  1.5  mycroft 		*vpp = ncp->nc_vp;
    155  1.1      cgd 		return (-1);
    156  1.1      cgd 	}
    157  1.1      cgd 
    158  1.1      cgd 	/*
    159  1.1      cgd 	 * Last component and we are renaming or deleting,
    160  1.1      cgd 	 * the cache entry is invalid, or otherwise don't
    161  1.1      cgd 	 * want cache entry to exist.
    162  1.1      cgd 	 */
    163  1.1      cgd 	/* remove from LRU chain */
    164  1.5  mycroft 	if (ncq = ncp->nc_nxt)
    165  1.5  mycroft 		ncq->nc_prev = ncp->nc_prev;
    166  1.1      cgd 	else
    167  1.1      cgd 		nchtail = ncp->nc_prev;
    168  1.5  mycroft 	*ncp->nc_prev = ncq;
    169  1.1      cgd 	/* remove from hash chain */
    170  1.5  mycroft 	if (ncq = ncp->nc_forw)
    171  1.5  mycroft 		ncq->nc_back = ncp->nc_back;
    172  1.5  mycroft 	*ncp->nc_back = ncq;
    173  1.5  mycroft 	/* and make a dummy hash chain */
    174  1.5  mycroft 	ncp->nc_forw = NULL;
    175  1.5  mycroft 	ncp->nc_back = NULL;
    176  1.1      cgd 	/* insert at head of LRU list (first to grab) */
    177  1.5  mycroft 	if (ncq = nchhead)
    178  1.5  mycroft 		ncq->nc_prev = &ncp->nc_nxt;
    179  1.5  mycroft 	else
    180  1.5  mycroft 		nchtail = &ncp->nc_nxt;
    181  1.5  mycroft 	nchhead = ncp;
    182  1.5  mycroft 	ncp->nc_nxt = ncq;
    183  1.1      cgd 	ncp->nc_prev = &nchhead;
    184  1.1      cgd 	return (0);
    185  1.1      cgd }
    186  1.1      cgd 
    187  1.1      cgd /*
    188  1.1      cgd  * Add an entry to the cache
    189  1.1      cgd  */
    190  1.5  mycroft cache_enter(dvp, vp, cnp)
    191  1.5  mycroft 	struct vnode *dvp;
    192  1.5  mycroft 	struct vnode *vp;
    193  1.5  mycroft 	struct componentname *cnp;
    194  1.1      cgd {
    195  1.5  mycroft 	register struct namecache *ncp, *ncq, **ncpp;
    196  1.1      cgd 
    197  1.5  mycroft #ifdef DIAGNOSTIC
    198  1.5  mycroft 	if (cnp->cn_namelen > NCHNAMLEN)
    199  1.5  mycroft 		panic("cache_enter: name too long");
    200  1.5  mycroft #endif
    201  1.1      cgd 	if (!doingcache)
    202  1.1      cgd 		return;
    203  1.1      cgd 	/*
    204  1.1      cgd 	 * Free the cache slot at head of lru chain.
    205  1.1      cgd 	 */
    206  1.1      cgd 	if (numcache < desiredvnodes) {
    207  1.1      cgd 		ncp = (struct namecache *)
    208  1.1      cgd 			malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
    209  1.1      cgd 		bzero((char *)ncp, sizeof *ncp);
    210  1.1      cgd 		numcache++;
    211  1.1      cgd 	} else if (ncp = nchhead) {
    212  1.1      cgd 		/* remove from lru chain */
    213  1.5  mycroft 		if (ncq = ncp->nc_nxt)
    214  1.5  mycroft 			ncq->nc_prev = ncp->nc_prev;
    215  1.1      cgd 		else
    216  1.1      cgd 			nchtail = ncp->nc_prev;
    217  1.5  mycroft 		*ncp->nc_prev = ncq;
    218  1.5  mycroft 		/* remove from old hash chain, if on one */
    219  1.5  mycroft 		if (ncp->nc_back) {
    220  1.5  mycroft 			if (ncq = ncp->nc_forw)
    221  1.5  mycroft 				ncq->nc_back = ncp->nc_back;
    222  1.5  mycroft 			*ncp->nc_back = ncq;
    223  1.5  mycroft 			ncp->nc_forw = NULL;
    224  1.5  mycroft 			ncp->nc_back = NULL;
    225  1.5  mycroft 		}
    226  1.1      cgd 	} else
    227  1.1      cgd 		return;
    228  1.1      cgd 	/* grab the vnode we just found */
    229  1.5  mycroft 	ncp->nc_vp = vp;
    230  1.5  mycroft 	if (vp)
    231  1.5  mycroft 		ncp->nc_vpid = vp->v_id;
    232  1.1      cgd 	else
    233  1.1      cgd 		ncp->nc_vpid = 0;
    234  1.1      cgd 	/* fill in cache info */
    235  1.5  mycroft 	ncp->nc_dvp = dvp;
    236  1.5  mycroft 	ncp->nc_dvpid = dvp->v_id;
    237  1.5  mycroft 	ncp->nc_nlen = cnp->cn_namelen;
    238  1.5  mycroft 	bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
    239  1.1      cgd 	/* link at end of lru chain */
    240  1.1      cgd 	ncp->nc_nxt = NULL;
    241  1.1      cgd 	ncp->nc_prev = nchtail;
    242  1.1      cgd 	*nchtail = ncp;
    243  1.1      cgd 	nchtail = &ncp->nc_nxt;
    244  1.1      cgd 	/* and insert on hash chain */
    245  1.5  mycroft 	ncpp = &nchashtbl[cnp->cn_hash & nchash];
    246  1.5  mycroft 	if (ncq = *ncpp)
    247  1.5  mycroft 		ncq->nc_back = &ncp->nc_forw;
    248  1.5  mycroft 	ncp->nc_forw = ncq;
    249  1.5  mycroft 	ncp->nc_back = ncpp;
    250  1.5  mycroft 	*ncpp = ncp;
    251  1.1      cgd }
    252  1.1      cgd 
    253  1.1      cgd /*
    254  1.1      cgd  * Name cache initialization, from vfs_init() when we are booting
    255  1.1      cgd  */
    256  1.1      cgd nchinit()
    257  1.1      cgd {
    258  1.1      cgd 
    259  1.1      cgd 	nchtail = &nchhead;
    260  1.5  mycroft 	nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash);
    261  1.1      cgd }
    262  1.1      cgd 
    263  1.1      cgd /*
    264  1.1      cgd  * Cache flush, a particular vnode; called when a vnode is renamed to
    265  1.1      cgd  * hide entries that would now be invalid
    266  1.1      cgd  */
    267  1.1      cgd cache_purge(vp)
    268  1.1      cgd 	struct vnode *vp;
    269  1.1      cgd {
    270  1.5  mycroft 	struct namecache *ncp, **ncpp;
    271  1.1      cgd 
    272  1.1      cgd 	vp->v_id = ++nextvnodeid;
    273  1.1      cgd 	if (nextvnodeid != 0)
    274  1.1      cgd 		return;
    275  1.5  mycroft 	for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
    276  1.5  mycroft 		for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) {
    277  1.1      cgd 			ncp->nc_vpid = 0;
    278  1.1      cgd 			ncp->nc_dvpid = 0;
    279  1.1      cgd 		}
    280  1.1      cgd 	}
    281  1.1      cgd 	vp->v_id = ++nextvnodeid;
    282  1.1      cgd }
    283  1.1      cgd 
    284  1.1      cgd /*
    285  1.1      cgd  * Cache flush, a whole filesystem; called when filesys is umounted to
    286  1.1      cgd  * remove entries that would now be invalid
    287  1.1      cgd  *
    288  1.1      cgd  * The line "nxtcp = nchhead" near the end is to avoid potential problems
    289  1.1      cgd  * if the cache lru chain is modified while we are dumping the
    290  1.1      cgd  * inode.  This makes the algorithm O(n^2), but do you think I care?
    291  1.1      cgd  */
    292  1.1      cgd cache_purgevfs(mp)
    293  1.1      cgd 	struct mount *mp;
    294  1.1      cgd {
    295  1.1      cgd 	register struct namecache *ncp, *nxtcp;
    296  1.1      cgd 
    297  1.1      cgd 	for (ncp = nchhead; ncp; ncp = nxtcp) {
    298  1.5  mycroft 		if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) {
    299  1.5  mycroft 			nxtcp = ncp->nc_nxt;
    300  1.1      cgd 			continue;
    301  1.5  mycroft 		}
    302  1.1      cgd 		/* free the resources we had */
    303  1.1      cgd 		ncp->nc_vp = NULL;
    304  1.1      cgd 		ncp->nc_dvp = NULL;
    305  1.5  mycroft 		/* remove from old hash chain, if on one */
    306  1.5  mycroft 		if (ncp->nc_back) {
    307  1.5  mycroft 			if (nxtcp = ncp->nc_forw)
    308  1.5  mycroft 				nxtcp->nc_back = ncp->nc_back;
    309  1.5  mycroft 			*ncp->nc_back = nxtcp;
    310  1.5  mycroft 			ncp->nc_forw = NULL;
    311  1.5  mycroft 			ncp->nc_back = NULL;
    312  1.5  mycroft 		}
    313  1.1      cgd 		/* delete this entry from LRU chain */
    314  1.5  mycroft 		if (nxtcp = ncp->nc_nxt)
    315  1.1      cgd 			nxtcp->nc_prev = ncp->nc_prev;
    316  1.1      cgd 		else
    317  1.1      cgd 			nchtail = ncp->nc_prev;
    318  1.5  mycroft 		*ncp->nc_prev = nxtcp;
    319  1.1      cgd 		/* cause rescan of list, it may have altered */
    320  1.5  mycroft 		/* also put the now-free entry at head of LRU */
    321  1.5  mycroft 		if (nxtcp = nchhead)
    322  1.5  mycroft 			nxtcp->nc_prev = &ncp->nc_nxt;
    323  1.5  mycroft 		else
    324  1.5  mycroft 			nchtail = &ncp->nc_nxt;
    325  1.5  mycroft 		nchhead = ncp;
    326  1.1      cgd 		ncp->nc_nxt = nxtcp;
    327  1.1      cgd 		ncp->nc_prev = &nchhead;
    328  1.1      cgd 	}
    329  1.1      cgd }
    330