Home | History | Annotate | Line # | Download | only in kern
vfs_cache.c revision 1.30
      1  1.30       chs /*	$NetBSD: vfs_cache.c,v 1.30 2001/09/24 06:01:13 chs Exp $	*/
      2   1.6       cgd 
      3   1.1       cgd /*
      4   1.5   mycroft  * Copyright (c) 1989, 1993
      5   1.5   mycroft  *	The Regents of the University of California.  All rights reserved.
      6   1.1       cgd  *
      7   1.1       cgd  * Redistribution and use in source and binary forms, with or without
      8   1.1       cgd  * modification, are permitted provided that the following conditions
      9   1.1       cgd  * are met:
     10   1.1       cgd  * 1. Redistributions of source code must retain the above copyright
     11   1.1       cgd  *    notice, this list of conditions and the following disclaimer.
     12   1.1       cgd  * 2. Redistributions in binary form must reproduce the above copyright
     13   1.1       cgd  *    notice, this list of conditions and the following disclaimer in the
     14   1.1       cgd  *    documentation and/or other materials provided with the distribution.
     15   1.1       cgd  * 3. All advertising materials mentioning features or use of this software
     16   1.1       cgd  *    must display the following acknowledgement:
     17   1.1       cgd  *	This product includes software developed by the University of
     18   1.1       cgd  *	California, Berkeley and its contributors.
     19   1.1       cgd  * 4. Neither the name of the University nor the names of its contributors
     20   1.1       cgd  *    may be used to endorse or promote products derived from this software
     21   1.1       cgd  *    without specific prior written permission.
     22   1.1       cgd  *
     23   1.1       cgd  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     24   1.1       cgd  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     25   1.1       cgd  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     26   1.1       cgd  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     27   1.1       cgd  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     28   1.1       cgd  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     29   1.1       cgd  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     30   1.1       cgd  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     31   1.1       cgd  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     32   1.1       cgd  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     33   1.1       cgd  * SUCH DAMAGE.
     34   1.1       cgd  *
     35  1.10   mycroft  *	@(#)vfs_cache.c	8.3 (Berkeley) 8/22/94
     36   1.1       cgd  */
     37   1.1       cgd 
     38  1.28       chs #include "opt_ddb.h"
     39  1.29      fvdl #include "opt_revcache.h"
     40  1.28       chs 
     41   1.4   mycroft #include <sys/param.h>
     42   1.4   mycroft #include <sys/systm.h>
     43   1.4   mycroft #include <sys/time.h>
     44   1.4   mycroft #include <sys/mount.h>
     45   1.4   mycroft #include <sys/vnode.h>
     46   1.4   mycroft #include <sys/namei.h>
     47   1.4   mycroft #include <sys/errno.h>
     48   1.4   mycroft #include <sys/malloc.h>
     49  1.18   thorpej #include <sys/pool.h>
     50   1.1       cgd 
     51   1.1       cgd /*
     52   1.1       cgd  * Name caching works as follows:
     53   1.1       cgd  *
     54   1.1       cgd  * Names found by directory scans are retained in a cache
     55   1.1       cgd  * for future reference.  It is managed LRU, so frequently
     56   1.1       cgd  * used names will hang around.  Cache is indexed by hash value
     57  1.20  jdolecek  * obtained from (dvp, name) where dvp refers to the directory
     58   1.1       cgd  * containing name.
     59   1.1       cgd  *
     60   1.1       cgd  * For simplicity (and economy of storage), names longer than
     61   1.1       cgd  * a maximum length of NCHNAMLEN are not cached; they occur
     62   1.1       cgd  * infrequently in any case, and are almost never of interest.
     63   1.1       cgd  *
     64   1.1       cgd  * Upon reaching the last segment of a path, if the reference
     65   1.1       cgd  * is for DELETE, or NOCACHE is set (rewrite), and the
     66   1.1       cgd  * name is located in the cache, it will be dropped.
     67  1.20  jdolecek  * The entry is dropped also when it was not possible to lock
     68  1.20  jdolecek  * the cached vnode, either because vget() failed or the generation
     69  1.20  jdolecek  * number has changed while waiting for the lock.
     70   1.1       cgd  */
     71   1.1       cgd 
     72   1.1       cgd /*
     73   1.1       cgd  * Structures associated with name cacheing.
     74   1.1       cgd  */
     75   1.9   mycroft LIST_HEAD(nchashhead, namecache) *nchashtbl;
     76   1.1       cgd u_long	nchash;				/* size of hash table - 1 */
     77   1.1       cgd long	numcache;			/* number of cache entries allocated */
     78  1.30       chs #define NCHASH(cnp, dvp)	(((cnp)->cn_hash ^ (dvp)->v_id) & nchash)
     79  1.19  sommerfe 
     80  1.19  sommerfe LIST_HEAD(ncvhashhead, namecache) *ncvhashtbl;
     81  1.19  sommerfe u_long	ncvhash;			/* size of hash table - 1 */
     82  1.30       chs #define NCVHASH(vp)		((vp)->v_id & ncvhash)
     83  1.19  sommerfe 
     84   1.9   mycroft TAILQ_HEAD(, namecache) nclruhead;		/* LRU chain */
     85   1.1       cgd struct	nchstats nchstats;		/* cache effectiveness statistics */
     86   1.1       cgd 
     87  1.18   thorpej struct pool namecache_pool;
     88  1.18   thorpej 
     89   1.7    chopps int doingcache = 1;			/* 1 => enable the cache */
     90   1.1       cgd 
     91   1.1       cgd /*
     92   1.1       cgd  * Look for a the name in the cache. We don't do this
     93   1.1       cgd  * if the segment name is long, simply so the cache can avoid
     94   1.1       cgd  * holding long names (which would either waste space, or
     95   1.1       cgd  * add greatly to the complexity).
     96   1.1       cgd  *
     97   1.1       cgd  * Lookup is called with ni_dvp pointing to the directory to search,
     98   1.1       cgd  * ni_ptr pointing to the name of the entry being sought, ni_namelen
     99   1.1       cgd  * tells the length of the name, and ni_hash contains a hash of
    100  1.20  jdolecek  * the name. If the lookup succeeds, the vnode is locked, stored in ni_vp
    101  1.20  jdolecek  * and a status of zero is returned. If the locking fails for whatever
    102  1.20  jdolecek  * reason, the vnode is unlocked and the error is returned to caller.
    103  1.20  jdolecek  * If the lookup determines that the name does not exist (negative cacheing),
    104  1.20  jdolecek  * a status of ENOENT is returned. If the lookup fails, a status of -1
    105  1.20  jdolecek  * is returned.
    106   1.1       cgd  */
    107   1.5   mycroft int
    108   1.5   mycroft cache_lookup(dvp, vpp, cnp)
    109   1.5   mycroft 	struct vnode *dvp;
    110   1.5   mycroft 	struct vnode **vpp;
    111   1.5   mycroft 	struct componentname *cnp;
    112   1.1       cgd {
    113  1.23  augustss 	struct namecache *ncp;
    114  1.23  augustss 	struct nchashhead *ncpp;
    115  1.20  jdolecek 	struct vnode *vp;
    116  1.20  jdolecek 	int vpid, error;
    117   1.1       cgd 
    118   1.8       cgd 	if (!doingcache) {
    119   1.8       cgd 		cnp->cn_flags &= ~MAKEENTRY;
    120  1.20  jdolecek 		*vpp = 0;
    121  1.20  jdolecek 		return (-1);
    122   1.8       cgd 	}
    123   1.5   mycroft 	if (cnp->cn_namelen > NCHNAMLEN) {
    124   1.1       cgd 		nchstats.ncs_long++;
    125   1.5   mycroft 		cnp->cn_flags &= ~MAKEENTRY;
    126  1.20  jdolecek 		*vpp = 0;
    127  1.20  jdolecek 		return (-1);
    128   1.1       cgd 	}
    129  1.30       chs 	ncpp = &nchashtbl[NCHASH(cnp, dvp)];
    130  1.27       chs 	LIST_FOREACH(ncp, ncpp, nc_hash) {
    131   1.1       cgd 		if (ncp->nc_dvp == dvp &&
    132   1.1       cgd 		    ncp->nc_dvpid == dvp->v_id &&
    133   1.5   mycroft 		    ncp->nc_nlen == cnp->cn_namelen &&
    134  1.17     perry 		    !memcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
    135   1.1       cgd 			break;
    136   1.1       cgd 	}
    137   1.9   mycroft 	if (ncp == 0) {
    138   1.1       cgd 		nchstats.ncs_miss++;
    139  1.20  jdolecek 		*vpp = 0;
    140  1.20  jdolecek 		return (-1);
    141   1.1       cgd 	}
    142   1.9   mycroft 	if ((cnp->cn_flags & MAKEENTRY) == 0) {
    143   1.1       cgd 		nchstats.ncs_badhits++;
    144  1.20  jdolecek 		goto remove;
    145   1.1       cgd 	} else if (ncp->nc_vp == NULL) {
    146  1.11   mycroft 		/*
    147  1.11   mycroft 		 * Restore the ISWHITEOUT flag saved earlier.
    148  1.11   mycroft 		 */
    149  1.11   mycroft 		cnp->cn_flags |= ncp->nc_vpid;
    150  1.21   mycroft 		if (cnp->cn_nameiop != CREATE ||
    151  1.21   mycroft 		    (cnp->cn_flags & ISLASTCN) == 0) {
    152   1.1       cgd 			nchstats.ncs_neghits++;
    153   1.1       cgd 			/*
    154   1.1       cgd 			 * Move this slot to end of LRU chain,
    155   1.1       cgd 			 * if not already there.
    156   1.1       cgd 			 */
    157   1.9   mycroft 			if (ncp->nc_lru.tqe_next != 0) {
    158   1.9   mycroft 				TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
    159   1.9   mycroft 				TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
    160   1.1       cgd 			}
    161   1.1       cgd 			return (ENOENT);
    162  1.20  jdolecek 		} else {
    163  1.15      fvdl 			nchstats.ncs_badhits++;
    164  1.20  jdolecek 			goto remove;
    165  1.20  jdolecek 		}
    166   1.1       cgd 	} else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
    167   1.1       cgd 		nchstats.ncs_falsehits++;
    168  1.20  jdolecek 		goto remove;
    169  1.20  jdolecek 	}
    170  1.20  jdolecek 
    171  1.20  jdolecek 	vp = ncp->nc_vp;
    172  1.20  jdolecek 	vpid = vp->v_id;
    173  1.20  jdolecek 	if (vp == dvp) {	/* lookup on "." */
    174  1.20  jdolecek 		VREF(dvp);
    175  1.20  jdolecek 		error = 0;
    176  1.20  jdolecek 	} else if (cnp->cn_flags & ISDOTDOT) {
    177  1.20  jdolecek 		VOP_UNLOCK(dvp, 0);
    178  1.20  jdolecek 		cnp->cn_flags |= PDIRUNLOCK;
    179  1.20  jdolecek 		error = vget(vp, LK_EXCLUSIVE);
    180  1.20  jdolecek 		/* if the above vget() succeeded and both LOCKPARENT and
    181  1.20  jdolecek 		 * ISLASTCN is set, lock the directory vnode as well */
    182  1.20  jdolecek 		if (!error && (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) == 0) {
    183  1.20  jdolecek 			if ((error = vn_lock(dvp, LK_EXCLUSIVE)) != 0) {
    184  1.20  jdolecek 				vput(vp);
    185  1.20  jdolecek 				return (error);
    186  1.20  jdolecek 			}
    187  1.20  jdolecek 			cnp->cn_flags &= ~PDIRUNLOCK;
    188  1.20  jdolecek 		}
    189   1.1       cgd 	} else {
    190  1.20  jdolecek 		error = vget(vp, LK_EXCLUSIVE);
    191  1.20  jdolecek 		/* if the above vget() failed or either of LOCKPARENT or
    192  1.20  jdolecek 		 * ISLASTCN is set, unlock the directory vnode */
    193  1.20  jdolecek 		if (error || (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) {
    194  1.20  jdolecek 			VOP_UNLOCK(dvp, 0);
    195  1.20  jdolecek 			cnp->cn_flags |= PDIRUNLOCK;
    196  1.20  jdolecek 		}
    197  1.20  jdolecek 	}
    198  1.20  jdolecek 
    199  1.20  jdolecek 	/*
    200  1.20  jdolecek 	 * Check that the lock succeeded, and that the capability number did
    201  1.20  jdolecek 	 * not change while we were waiting for the lock.
    202  1.20  jdolecek 	 */
    203  1.20  jdolecek 	if (error || vpid != vp->v_id) {
    204  1.20  jdolecek 		if (!error) {
    205  1.20  jdolecek 			vput(vp);
    206  1.20  jdolecek 			nchstats.ncs_falsehits++;
    207  1.20  jdolecek 		} else
    208  1.20  jdolecek 			nchstats.ncs_badhits++;
    209   1.1       cgd 		/*
    210  1.20  jdolecek 		 * The parent needs to be locked when we return to VOP_LOOKUP().
    211  1.20  jdolecek 		 * The `.' case here should be extremely rare (if it can happen
    212  1.20  jdolecek 		 * at all), so we don't bother optimizing out the unlock/relock.
    213   1.1       cgd 		 */
    214  1.20  jdolecek 		if (vp == dvp ||
    215  1.20  jdolecek 		    error || (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) {
    216  1.20  jdolecek 			if ((error = vn_lock(dvp, LK_EXCLUSIVE)) != 0)
    217  1.20  jdolecek 				return (error);
    218  1.20  jdolecek 			cnp->cn_flags &= ~PDIRUNLOCK;
    219   1.1       cgd 		}
    220  1.20  jdolecek 		goto remove;
    221  1.20  jdolecek 	}
    222  1.20  jdolecek 
    223  1.20  jdolecek 	nchstats.ncs_goodhits++;
    224  1.20  jdolecek 	/*
    225  1.20  jdolecek 	 * move this slot to end of LRU chain, if not already there
    226  1.20  jdolecek 	 */
    227  1.20  jdolecek 	if (ncp->nc_lru.tqe_next != 0) {
    228  1.20  jdolecek 		TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
    229  1.20  jdolecek 		TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
    230   1.1       cgd 	}
    231  1.20  jdolecek 	*vpp = vp;
    232  1.20  jdolecek 	return (0);
    233   1.1       cgd 
    234  1.20  jdolecek remove:
    235   1.1       cgd 	/*
    236   1.1       cgd 	 * Last component and we are renaming or deleting,
    237   1.1       cgd 	 * the cache entry is invalid, or otherwise don't
    238   1.1       cgd 	 * want cache entry to exist.
    239   1.1       cgd 	 */
    240   1.9   mycroft 	TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
    241   1.9   mycroft 	LIST_REMOVE(ncp, nc_hash);
    242   1.9   mycroft 	ncp->nc_hash.le_prev = 0;
    243  1.19  sommerfe 	if (ncp->nc_vhash.le_prev != NULL) {
    244  1.19  sommerfe 		LIST_REMOVE(ncp, nc_vhash);
    245  1.19  sommerfe 		ncp->nc_vhash.le_prev = 0;
    246  1.19  sommerfe 	}
    247   1.9   mycroft 	TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);
    248  1.20  jdolecek 	*vpp = 0;
    249  1.20  jdolecek 	return (-1);
    250   1.1       cgd }
    251   1.1       cgd 
    252   1.1       cgd /*
    253  1.19  sommerfe  * Scan cache looking for name of directory entry pointing at vp.
    254  1.19  sommerfe  *
    255  1.19  sommerfe  * Fill in dvpp.
    256  1.19  sommerfe  *
    257  1.19  sommerfe  * If bufp is non-NULL, also place the name in the buffer which starts
    258  1.19  sommerfe  * at bufp, immediately before *bpp, and move bpp backwards to point
    259  1.19  sommerfe  * at the start of it.  (Yes, this is a little baroque, but it's done
    260  1.19  sommerfe  * this way to cater to the whims of getcwd).
    261  1.19  sommerfe  *
    262  1.19  sommerfe  * Returns 0 on success, -1 on cache miss, positive errno on failure.
    263  1.19  sommerfe  */
    264  1.19  sommerfe int
    265  1.19  sommerfe cache_revlookup (vp, dvpp, bpp, bufp)
    266  1.19  sommerfe 	struct vnode *vp, **dvpp;
    267  1.19  sommerfe 	char **bpp;
    268  1.19  sommerfe 	char *bufp;
    269  1.19  sommerfe {
    270  1.19  sommerfe 	struct namecache *ncp;
    271  1.19  sommerfe 	struct vnode *dvp;
    272  1.19  sommerfe 	struct ncvhashhead *nvcpp;
    273  1.19  sommerfe 
    274  1.19  sommerfe 	if (!doingcache)
    275  1.19  sommerfe 		goto out;
    276  1.19  sommerfe 
    277  1.30       chs 	nvcpp = &ncvhashtbl[NCVHASH(vp)];
    278  1.19  sommerfe 
    279  1.27       chs 	LIST_FOREACH(ncp, nvcpp, nc_vhash) {
    280  1.19  sommerfe 		if ((ncp->nc_vp == vp) &&
    281  1.19  sommerfe 		    (ncp->nc_vpid == vp->v_id) &&
    282  1.19  sommerfe 		    ((dvp = ncp->nc_dvp) != 0) &&
    283  1.19  sommerfe 		    (dvp != vp) && 		/* avoid pesky . entries.. */
    284  1.19  sommerfe 		    (dvp->v_id == ncp->nc_dvpid))
    285  1.19  sommerfe 		{
    286  1.19  sommerfe 			char *bp;
    287  1.19  sommerfe 
    288  1.19  sommerfe #ifdef DIAGNOSTIC
    289  1.19  sommerfe 			if ((ncp->nc_nlen == 1) &&
    290  1.19  sommerfe 			    (ncp->nc_name[0] == '.'))
    291  1.19  sommerfe 				panic("cache_revlookup: found entry for .");
    292  1.19  sommerfe 
    293  1.19  sommerfe 			if ((ncp->nc_nlen == 2) &&
    294  1.19  sommerfe 			    (ncp->nc_name[0] == '.') &&
    295  1.19  sommerfe 			    (ncp->nc_name[1] == '.'))
    296  1.19  sommerfe 				panic("cache_revlookup: found entry for ..");
    297  1.19  sommerfe #endif
    298  1.19  sommerfe 			nchstats.ncs_revhits++;
    299  1.19  sommerfe 
    300  1.19  sommerfe 			if (bufp) {
    301  1.19  sommerfe 				bp = *bpp;
    302  1.19  sommerfe 				bp -= ncp->nc_nlen;
    303  1.19  sommerfe 				if (bp <= bufp) {
    304  1.19  sommerfe 					*dvpp = 0;
    305  1.19  sommerfe 					return ERANGE;
    306  1.19  sommerfe 				}
    307  1.19  sommerfe 				memcpy(bp, ncp->nc_name, ncp->nc_nlen);
    308  1.19  sommerfe 				*bpp = bp;
    309  1.19  sommerfe 			}
    310  1.19  sommerfe 
    311  1.19  sommerfe 			/* XXX MP: how do we know dvp won't evaporate? */
    312  1.19  sommerfe 			*dvpp = dvp;
    313  1.19  sommerfe 			return 0;
    314  1.19  sommerfe 		}
    315  1.19  sommerfe 	}
    316  1.19  sommerfe 	nchstats.ncs_revmiss++;
    317  1.19  sommerfe  out:
    318  1.19  sommerfe 	*dvpp = 0;
    319  1.19  sommerfe 	return -1;
    320  1.19  sommerfe }
    321  1.19  sommerfe 
    322  1.19  sommerfe /*
    323   1.1       cgd  * Add an entry to the cache
    324   1.1       cgd  */
    325  1.13  christos void
    326   1.5   mycroft cache_enter(dvp, vp, cnp)
    327   1.5   mycroft 	struct vnode *dvp;
    328   1.5   mycroft 	struct vnode *vp;
    329   1.5   mycroft 	struct componentname *cnp;
    330   1.1       cgd {
    331  1.23  augustss 	struct namecache *ncp;
    332  1.23  augustss 	struct nchashhead *ncpp;
    333  1.23  augustss 	struct ncvhashhead *nvcpp;
    334   1.1       cgd 
    335   1.5   mycroft #ifdef DIAGNOSTIC
    336   1.5   mycroft 	if (cnp->cn_namelen > NCHNAMLEN)
    337   1.5   mycroft 		panic("cache_enter: name too long");
    338   1.5   mycroft #endif
    339   1.1       cgd 	if (!doingcache)
    340   1.1       cgd 		return;
    341   1.1       cgd 	/*
    342   1.1       cgd 	 * Free the cache slot at head of lru chain.
    343   1.1       cgd 	 */
    344  1.24       chs 	if (numcache < numvnodes) {
    345  1.18   thorpej 		ncp = pool_get(&namecache_pool, PR_WAITOK);
    346  1.27       chs 		memset(ncp, 0, sizeof(*ncp));
    347   1.1       cgd 		numcache++;
    348  1.27       chs 	} else if ((ncp = TAILQ_FIRST(&nclruhead)) != NULL) {
    349   1.9   mycroft 		TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
    350   1.9   mycroft 		if (ncp->nc_hash.le_prev != 0) {
    351   1.9   mycroft 			LIST_REMOVE(ncp, nc_hash);
    352   1.9   mycroft 			ncp->nc_hash.le_prev = 0;
    353   1.5   mycroft 		}
    354  1.19  sommerfe 		if (ncp->nc_vhash.le_prev != 0) {
    355  1.19  sommerfe 			LIST_REMOVE(ncp, nc_vhash);
    356  1.19  sommerfe 			ncp->nc_vhash.le_prev = 0;
    357  1.19  sommerfe 		}
    358   1.1       cgd 	} else
    359   1.1       cgd 		return;
    360   1.1       cgd 	/* grab the vnode we just found */
    361   1.5   mycroft 	ncp->nc_vp = vp;
    362   1.5   mycroft 	if (vp)
    363   1.5   mycroft 		ncp->nc_vpid = vp->v_id;
    364  1.11   mycroft 	else {
    365  1.11   mycroft 		/*
    366  1.11   mycroft 		 * For negative hits, save the ISWHITEOUT flag so we can
    367  1.11   mycroft 		 * restore it later when the cache entry is used again.
    368  1.11   mycroft 		 */
    369  1.11   mycroft 		ncp->nc_vpid = cnp->cn_flags & ISWHITEOUT;
    370  1.11   mycroft 	}
    371   1.1       cgd 	/* fill in cache info */
    372   1.5   mycroft 	ncp->nc_dvp = dvp;
    373   1.5   mycroft 	ncp->nc_dvpid = dvp->v_id;
    374   1.5   mycroft 	ncp->nc_nlen = cnp->cn_namelen;
    375  1.17     perry 	memcpy(ncp->nc_name, cnp->cn_nameptr, (unsigned)ncp->nc_nlen);
    376   1.9   mycroft 	TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
    377  1.30       chs 	ncpp = &nchashtbl[NCHASH(cnp, dvp)];
    378   1.9   mycroft 	LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
    379  1.19  sommerfe 
    380  1.19  sommerfe 	ncp->nc_vhash.le_prev = 0;
    381  1.19  sommerfe 	ncp->nc_vhash.le_next = 0;
    382  1.19  sommerfe 
    383  1.19  sommerfe 	/*
    384  1.19  sommerfe 	 * Create reverse-cache entries (used in getcwd) for directories.
    385  1.19  sommerfe 	 */
    386  1.19  sommerfe 	if (vp &&
    387  1.19  sommerfe 	    (vp != dvp) &&
    388  1.29      fvdl #ifndef NAMECACHE_ENTER_REVERSE
    389  1.19  sommerfe 	    (vp->v_type == VDIR) &&
    390  1.29      fvdl #endif
    391  1.19  sommerfe 	    ((ncp->nc_nlen > 2) ||
    392  1.19  sommerfe 	     ((ncp->nc_nlen == 2) && (ncp->nc_name[0] != '.') && (ncp->nc_name[1] != '.')) ||
    393  1.19  sommerfe 	     ((ncp->nc_nlen == 1) && (ncp->nc_name[0] != '.'))))
    394  1.19  sommerfe 	{
    395  1.30       chs 		nvcpp = &ncvhashtbl[NCVHASH(vp)];
    396  1.19  sommerfe 		LIST_INSERT_HEAD(nvcpp, ncp, nc_vhash);
    397  1.19  sommerfe 	}
    398  1.19  sommerfe 
    399   1.1       cgd }
    400   1.1       cgd 
    401   1.1       cgd /*
    402   1.1       cgd  * Name cache initialization, from vfs_init() when we are booting
    403   1.1       cgd  */
    404  1.13  christos void
    405   1.1       cgd nchinit()
    406   1.1       cgd {
    407   1.1       cgd 
    408   1.9   mycroft 	TAILQ_INIT(&nclruhead);
    409  1.26        ad 	nchashtbl =
    410  1.26        ad 	    hashinit(desiredvnodes, HASH_LIST, M_CACHE, M_WAITOK, &nchash);
    411  1.26        ad 	ncvhashtbl =
    412  1.29      fvdl #ifdef NAMECACHE_ENTER_REVERSE
    413  1.29      fvdl 	    hashinit(desiredvnodes, HASH_LIST, M_CACHE, M_WAITOK, &ncvhash);
    414  1.29      fvdl #else
    415  1.26        ad 	    hashinit(desiredvnodes/8, HASH_LIST, M_CACHE, M_WAITOK, &ncvhash);
    416  1.29      fvdl #endif
    417  1.18   thorpej 	pool_init(&namecache_pool, sizeof(struct namecache), 0, 0, 0,
    418  1.18   thorpej 	    "ncachepl", 0, pool_page_alloc_nointr, pool_page_free_nointr,
    419  1.18   thorpej 	    M_CACHE);
    420  1.30       chs }
    421  1.30       chs 
    422  1.30       chs /*
    423  1.30       chs  * Name cache reinitialization, for when the maximum number of vnodes increases.
    424  1.30       chs  */
    425  1.30       chs void
    426  1.30       chs nchreinit()
    427  1.30       chs {
    428  1.30       chs 	struct namecache *ncp;
    429  1.30       chs 	struct nchashhead *oldhash1, *hash1;
    430  1.30       chs 	struct ncvhashhead *oldhash2, *hash2;
    431  1.30       chs 	u_long oldmask1, oldmask2, mask1, mask2;
    432  1.30       chs 	int i;
    433  1.30       chs 
    434  1.30       chs 	hash1 = hashinit(desiredvnodes, HASH_LIST, M_CACHE, M_WAITOK, &mask1);
    435  1.30       chs 	hash2 =
    436  1.30       chs #ifdef NAMECACHE_ENTER_REVERSE
    437  1.30       chs 	    hashinit(desiredvnodes, HASH_LIST, M_CACHE, M_WAITOK, &mask2);
    438  1.30       chs #else
    439  1.30       chs 	    hashinit(desiredvnodes/8, HASH_LIST, M_CACHE, M_WAITOK, &mask2);
    440  1.30       chs #endif
    441  1.30       chs 	oldhash1 = nchashtbl;
    442  1.30       chs 	oldmask1 = nchash;
    443  1.30       chs 	nchashtbl = hash1;
    444  1.30       chs 	nchash = mask1;
    445  1.30       chs 	oldhash2 = ncvhashtbl;
    446  1.30       chs 	oldmask2 = ncvhash;
    447  1.30       chs 	ncvhashtbl = hash2;
    448  1.30       chs 	ncvhash = mask2;
    449  1.30       chs 	for (i = 0; i <= oldmask1; i++) {
    450  1.30       chs 		while ((ncp = LIST_FIRST(&oldhash1[i])) != NULL) {
    451  1.30       chs 			LIST_REMOVE(ncp, nc_hash);
    452  1.30       chs 			ncp->nc_hash.le_prev = NULL;
    453  1.30       chs 		}
    454  1.30       chs 	}
    455  1.30       chs 	for (i = 0; i <= oldmask2; i++) {
    456  1.30       chs 		while ((ncp = LIST_FIRST(&oldhash2[i])) != NULL) {
    457  1.30       chs 			LIST_REMOVE(ncp, nc_vhash);
    458  1.30       chs 			ncp->nc_vhash.le_prev = NULL;
    459  1.30       chs 		}
    460  1.30       chs 	}
    461  1.30       chs 	hashdone(oldhash1, M_CACHE);
    462  1.30       chs 	hashdone(oldhash2, M_CACHE);
    463   1.1       cgd }
    464   1.1       cgd 
    465   1.1       cgd /*
    466   1.1       cgd  * Cache flush, a particular vnode; called when a vnode is renamed to
    467   1.1       cgd  * hide entries that would now be invalid
    468   1.1       cgd  */
    469  1.13  christos void
    470   1.1       cgd cache_purge(vp)
    471   1.1       cgd 	struct vnode *vp;
    472   1.1       cgd {
    473   1.9   mycroft 	struct namecache *ncp;
    474   1.9   mycroft 	struct nchashhead *ncpp;
    475  1.25       chs 	static u_long nextvnodeid;
    476   1.1       cgd 
    477   1.1       cgd 	vp->v_id = ++nextvnodeid;
    478   1.1       cgd 	if (nextvnodeid != 0)
    479   1.1       cgd 		return;
    480   1.5   mycroft 	for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
    481  1.27       chs 		LIST_FOREACH(ncp, ncpp, nc_hash) {
    482   1.1       cgd 			ncp->nc_vpid = 0;
    483   1.1       cgd 			ncp->nc_dvpid = 0;
    484   1.1       cgd 		}
    485   1.1       cgd 	}
    486   1.1       cgd 	vp->v_id = ++nextvnodeid;
    487   1.1       cgd }
    488   1.1       cgd 
    489   1.1       cgd /*
    490   1.1       cgd  * Cache flush, a whole filesystem; called when filesys is umounted to
    491  1.27       chs  * remove entries that would now be invalid.
    492   1.1       cgd  */
    493  1.13  christos void
    494   1.1       cgd cache_purgevfs(mp)
    495   1.1       cgd 	struct mount *mp;
    496   1.1       cgd {
    497  1.23  augustss 	struct namecache *ncp, *nxtcp;
    498   1.1       cgd 
    499  1.27       chs 	for (ncp = TAILQ_FIRST(&nclruhead); ncp != NULL; ncp = nxtcp) {
    500  1.27       chs 		nxtcp = TAILQ_NEXT(ncp, nc_lru);
    501   1.5   mycroft 		if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) {
    502   1.1       cgd 			continue;
    503   1.5   mycroft 		}
    504   1.1       cgd 		/* free the resources we had */
    505   1.1       cgd 		ncp->nc_vp = NULL;
    506   1.1       cgd 		ncp->nc_dvp = NULL;
    507   1.9   mycroft 		TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
    508   1.9   mycroft 		if (ncp->nc_hash.le_prev != 0) {
    509   1.9   mycroft 			LIST_REMOVE(ncp, nc_hash);
    510   1.9   mycroft 			ncp->nc_hash.le_prev = 0;
    511   1.5   mycroft 		}
    512  1.19  sommerfe 		if (ncp->nc_vhash.le_prev != 0) {
    513  1.19  sommerfe 			LIST_REMOVE(ncp, nc_vhash);
    514  1.19  sommerfe 			ncp->nc_vhash.le_prev = 0;
    515  1.19  sommerfe 		}
    516   1.9   mycroft 		TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);
    517   1.1       cgd 	}
    518   1.1       cgd }
    519  1.19  sommerfe 
    520  1.28       chs #ifdef DDB
    521  1.28       chs void
    522  1.28       chs namecache_print(struct vnode *vp, void (*pr)(const char *, ...))
    523  1.28       chs {
    524  1.28       chs 	struct vnode *dvp = NULL;
    525  1.28       chs 	struct namecache *ncp;
    526  1.28       chs 
    527  1.28       chs 	TAILQ_FOREACH(ncp, &nclruhead, nc_lru) {
    528  1.28       chs 		if (ncp->nc_vp == vp && ncp->nc_vpid == vp->v_id) {
    529  1.28       chs 			(*pr)("name %.*s\n", ncp->nc_nlen, ncp->nc_name);
    530  1.28       chs 			dvp = ncp->nc_dvp;
    531  1.28       chs 		}
    532  1.28       chs 	}
    533  1.28       chs 	if (dvp == NULL) {
    534  1.28       chs 		(*pr)("name not found\n");
    535  1.28       chs 		return;
    536  1.28       chs 	}
    537  1.28       chs 	vp = dvp;
    538  1.28       chs 	TAILQ_FOREACH(ncp, &nclruhead, nc_lru) {
    539  1.28       chs 		if (ncp->nc_vp == vp && ncp->nc_vpid == vp->v_id) {
    540  1.28       chs 			(*pr)("parent %.*s\n", ncp->nc_nlen, ncp->nc_name);
    541  1.28       chs 		}
    542  1.28       chs 	}
    543  1.28       chs }
    544  1.28       chs #endif
    545