Home | History | Annotate | Line # | Download | only in kern
vfs_cache.c revision 1.20
      1  1.20  jdolecek /*	$NetBSD: vfs_cache.c,v 1.20 1999/09/05 14:22:34 jdolecek 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.4   mycroft #include <sys/param.h>
     39   1.4   mycroft #include <sys/systm.h>
     40   1.4   mycroft #include <sys/time.h>
     41   1.4   mycroft #include <sys/mount.h>
     42   1.4   mycroft #include <sys/vnode.h>
     43   1.4   mycroft #include <sys/namei.h>
     44   1.4   mycroft #include <sys/errno.h>
     45   1.4   mycroft #include <sys/malloc.h>
     46  1.18   thorpej #include <sys/pool.h>
     47   1.1       cgd 
     48   1.1       cgd /*
     49   1.1       cgd  * Name caching works as follows:
     50   1.1       cgd  *
     51   1.1       cgd  * Names found by directory scans are retained in a cache
     52   1.1       cgd  * for future reference.  It is managed LRU, so frequently
     53   1.1       cgd  * used names will hang around.  Cache is indexed by hash value
     54  1.20  jdolecek  * obtained from (dvp, name) where dvp refers to the directory
     55   1.1       cgd  * containing name.
     56   1.1       cgd  *
     57   1.1       cgd  * For simplicity (and economy of storage), names longer than
     58   1.1       cgd  * a maximum length of NCHNAMLEN are not cached; they occur
     59   1.1       cgd  * infrequently in any case, and are almost never of interest.
     60   1.1       cgd  *
     61   1.1       cgd  * Upon reaching the last segment of a path, if the reference
     62   1.1       cgd  * is for DELETE, or NOCACHE is set (rewrite), and the
     63   1.1       cgd  * name is located in the cache, it will be dropped.
     64  1.20  jdolecek  * The entry is dropped also when it was not possible to lock
     65  1.20  jdolecek  * the cached vnode, either because vget() failed or the generation
     66  1.20  jdolecek  * number has changed while waiting for the lock.
     67   1.1       cgd  */
     68   1.1       cgd 
     69   1.1       cgd /*
     70   1.1       cgd  * Structures associated with name cacheing.
     71   1.1       cgd  */
     72   1.9   mycroft LIST_HEAD(nchashhead, namecache) *nchashtbl;
     73   1.1       cgd u_long	nchash;				/* size of hash table - 1 */
     74   1.1       cgd long	numcache;			/* number of cache entries allocated */
     75  1.19  sommerfe 
     76  1.19  sommerfe LIST_HEAD(ncvhashhead, namecache) *ncvhashtbl;
     77  1.19  sommerfe u_long	ncvhash;			/* size of hash table - 1 */
     78  1.19  sommerfe 
     79   1.9   mycroft TAILQ_HEAD(, namecache) nclruhead;		/* LRU chain */
     80   1.1       cgd struct	nchstats nchstats;		/* cache effectiveness statistics */
     81   1.1       cgd 
     82  1.18   thorpej struct pool namecache_pool;
     83  1.18   thorpej 
     84   1.7    chopps int doingcache = 1;			/* 1 => enable the cache */
     85   1.1       cgd 
     86   1.1       cgd /*
     87   1.1       cgd  * Look for a the name in the cache. We don't do this
     88   1.1       cgd  * if the segment name is long, simply so the cache can avoid
     89   1.1       cgd  * holding long names (which would either waste space, or
     90   1.1       cgd  * add greatly to the complexity).
     91   1.1       cgd  *
     92   1.1       cgd  * Lookup is called with ni_dvp pointing to the directory to search,
     93   1.1       cgd  * ni_ptr pointing to the name of the entry being sought, ni_namelen
     94   1.1       cgd  * tells the length of the name, and ni_hash contains a hash of
     95  1.20  jdolecek  * the name. If the lookup succeeds, the vnode is locked, stored in ni_vp
     96  1.20  jdolecek  * and a status of zero is returned. If the locking fails for whatever
     97  1.20  jdolecek  * reason, the vnode is unlocked and the error is returned to caller.
     98  1.20  jdolecek  * If the lookup determines that the name does not exist (negative cacheing),
     99  1.20  jdolecek  * a status of ENOENT is returned. If the lookup fails, a status of -1
    100  1.20  jdolecek  * is returned.
    101   1.1       cgd  */
    102   1.5   mycroft int
    103   1.5   mycroft cache_lookup(dvp, vpp, cnp)
    104   1.5   mycroft 	struct vnode *dvp;
    105   1.5   mycroft 	struct vnode **vpp;
    106   1.5   mycroft 	struct componentname *cnp;
    107   1.1       cgd {
    108   1.9   mycroft 	register struct namecache *ncp;
    109   1.9   mycroft 	register struct nchashhead *ncpp;
    110  1.20  jdolecek 	struct vnode *vp;
    111  1.20  jdolecek 	int vpid, error;
    112   1.1       cgd 
    113   1.8       cgd 	if (!doingcache) {
    114   1.8       cgd 		cnp->cn_flags &= ~MAKEENTRY;
    115  1.20  jdolecek 		*vpp = 0;
    116  1.20  jdolecek 		return (-1);
    117   1.8       cgd 	}
    118   1.5   mycroft 	if (cnp->cn_namelen > NCHNAMLEN) {
    119   1.1       cgd 		nchstats.ncs_long++;
    120   1.5   mycroft 		cnp->cn_flags &= ~MAKEENTRY;
    121  1.20  jdolecek 		*vpp = 0;
    122  1.20  jdolecek 		return (-1);
    123   1.1       cgd 	}
    124  1.12        ws 	ncpp = &nchashtbl[(cnp->cn_hash ^ dvp->v_id) & nchash];
    125   1.9   mycroft 	for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) {
    126   1.1       cgd 		if (ncp->nc_dvp == dvp &&
    127   1.1       cgd 		    ncp->nc_dvpid == dvp->v_id &&
    128   1.5   mycroft 		    ncp->nc_nlen == cnp->cn_namelen &&
    129  1.17     perry 		    !memcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
    130   1.1       cgd 			break;
    131   1.1       cgd 	}
    132   1.9   mycroft 	if (ncp == 0) {
    133   1.1       cgd 		nchstats.ncs_miss++;
    134  1.20  jdolecek 		*vpp = 0;
    135  1.20  jdolecek 		return (-1);
    136   1.1       cgd 	}
    137   1.9   mycroft 	if ((cnp->cn_flags & MAKEENTRY) == 0) {
    138   1.1       cgd 		nchstats.ncs_badhits++;
    139  1.20  jdolecek 		goto remove;
    140   1.1       cgd 	} else if (ncp->nc_vp == NULL) {
    141  1.11   mycroft 		/*
    142  1.11   mycroft 		 * Restore the ISWHITEOUT flag saved earlier.
    143  1.11   mycroft 		 */
    144  1.11   mycroft 		cnp->cn_flags |= ncp->nc_vpid;
    145   1.5   mycroft 		if (cnp->cn_nameiop != CREATE) {
    146   1.1       cgd 			nchstats.ncs_neghits++;
    147   1.1       cgd 			/*
    148   1.1       cgd 			 * Move this slot to end of LRU chain,
    149   1.1       cgd 			 * if not already there.
    150   1.1       cgd 			 */
    151   1.9   mycroft 			if (ncp->nc_lru.tqe_next != 0) {
    152   1.9   mycroft 				TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
    153   1.9   mycroft 				TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
    154   1.1       cgd 			}
    155   1.1       cgd 			return (ENOENT);
    156  1.20  jdolecek 		} else {
    157  1.15      fvdl 			nchstats.ncs_badhits++;
    158  1.20  jdolecek 			goto remove;
    159  1.20  jdolecek 		}
    160   1.1       cgd 	} else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
    161   1.1       cgd 		nchstats.ncs_falsehits++;
    162  1.20  jdolecek 		goto remove;
    163  1.20  jdolecek 	}
    164  1.20  jdolecek 
    165  1.20  jdolecek 	vp = ncp->nc_vp;
    166  1.20  jdolecek 	vpid = vp->v_id;
    167  1.20  jdolecek 	if (vp == dvp) {	/* lookup on "." */
    168  1.20  jdolecek 		VREF(dvp);
    169  1.20  jdolecek 		error = 0;
    170  1.20  jdolecek 	} else if (cnp->cn_flags & ISDOTDOT) {
    171  1.20  jdolecek 		VOP_UNLOCK(dvp, 0);
    172  1.20  jdolecek 		cnp->cn_flags |= PDIRUNLOCK;
    173  1.20  jdolecek 		error = vget(vp, LK_EXCLUSIVE);
    174  1.20  jdolecek 		/* if the above vget() succeeded and both LOCKPARENT and
    175  1.20  jdolecek 		 * ISLASTCN is set, lock the directory vnode as well */
    176  1.20  jdolecek 		if (!error && (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) == 0) {
    177  1.20  jdolecek 			if ((error = vn_lock(dvp, LK_EXCLUSIVE)) != 0) {
    178  1.20  jdolecek 				vput(vp);
    179  1.20  jdolecek 				return (error);
    180  1.20  jdolecek 			}
    181  1.20  jdolecek 			cnp->cn_flags &= ~PDIRUNLOCK;
    182  1.20  jdolecek 		}
    183   1.1       cgd 	} else {
    184  1.20  jdolecek 		error = vget(vp, LK_EXCLUSIVE);
    185  1.20  jdolecek 		/* if the above vget() failed or either of LOCKPARENT or
    186  1.20  jdolecek 		 * ISLASTCN is set, unlock the directory vnode */
    187  1.20  jdolecek 		if (error || (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) {
    188  1.20  jdolecek 			VOP_UNLOCK(dvp, 0);
    189  1.20  jdolecek 			cnp->cn_flags |= PDIRUNLOCK;
    190  1.20  jdolecek 		}
    191  1.20  jdolecek 	}
    192  1.20  jdolecek 
    193  1.20  jdolecek 	/*
    194  1.20  jdolecek 	 * Check that the lock succeeded, and that the capability number did
    195  1.20  jdolecek 	 * not change while we were waiting for the lock.
    196  1.20  jdolecek 	 */
    197  1.20  jdolecek 	if (error || vpid != vp->v_id) {
    198  1.20  jdolecek 		if (!error) {
    199  1.20  jdolecek 			vput(vp);
    200  1.20  jdolecek 			nchstats.ncs_falsehits++;
    201  1.20  jdolecek 		} else
    202  1.20  jdolecek 			nchstats.ncs_badhits++;
    203   1.1       cgd 		/*
    204  1.20  jdolecek 		 * The parent needs to be locked when we return to VOP_LOOKUP().
    205  1.20  jdolecek 		 * The `.' case here should be extremely rare (if it can happen
    206  1.20  jdolecek 		 * at all), so we don't bother optimizing out the unlock/relock.
    207   1.1       cgd 		 */
    208  1.20  jdolecek 		if (vp == dvp ||
    209  1.20  jdolecek 		    error || (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) {
    210  1.20  jdolecek 			if ((error = vn_lock(dvp, LK_EXCLUSIVE)) != 0)
    211  1.20  jdolecek 				return (error);
    212  1.20  jdolecek 			cnp->cn_flags &= ~PDIRUNLOCK;
    213   1.1       cgd 		}
    214  1.20  jdolecek 		goto remove;
    215  1.20  jdolecek 	}
    216  1.20  jdolecek 
    217  1.20  jdolecek 	nchstats.ncs_goodhits++;
    218  1.20  jdolecek 	/*
    219  1.20  jdolecek 	 * move this slot to end of LRU chain, if not already there
    220  1.20  jdolecek 	 */
    221  1.20  jdolecek 	if (ncp->nc_lru.tqe_next != 0) {
    222  1.20  jdolecek 		TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
    223  1.20  jdolecek 		TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
    224   1.1       cgd 	}
    225  1.20  jdolecek 	*vpp = vp;
    226  1.20  jdolecek 	return (0);
    227   1.1       cgd 
    228  1.20  jdolecek remove:
    229   1.1       cgd 	/*
    230   1.1       cgd 	 * Last component and we are renaming or deleting,
    231   1.1       cgd 	 * the cache entry is invalid, or otherwise don't
    232   1.1       cgd 	 * want cache entry to exist.
    233   1.1       cgd 	 */
    234   1.9   mycroft 	TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
    235   1.9   mycroft 	LIST_REMOVE(ncp, nc_hash);
    236   1.9   mycroft 	ncp->nc_hash.le_prev = 0;
    237  1.19  sommerfe 	if (ncp->nc_vhash.le_prev != NULL) {
    238  1.19  sommerfe 		LIST_REMOVE(ncp, nc_vhash);
    239  1.19  sommerfe 		ncp->nc_vhash.le_prev = 0;
    240  1.19  sommerfe 	}
    241   1.9   mycroft 	TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);
    242  1.20  jdolecek 	*vpp = 0;
    243  1.20  jdolecek 	return (-1);
    244   1.1       cgd }
    245   1.1       cgd 
    246   1.1       cgd /*
    247  1.19  sommerfe  * Scan cache looking for name of directory entry pointing at vp.
    248  1.19  sommerfe  *
    249  1.19  sommerfe  * Fill in dvpp.
    250  1.19  sommerfe  *
    251  1.19  sommerfe  * If bufp is non-NULL, also place the name in the buffer which starts
    252  1.19  sommerfe  * at bufp, immediately before *bpp, and move bpp backwards to point
    253  1.19  sommerfe  * at the start of it.  (Yes, this is a little baroque, but it's done
    254  1.19  sommerfe  * this way to cater to the whims of getcwd).
    255  1.19  sommerfe  *
    256  1.19  sommerfe  * Returns 0 on success, -1 on cache miss, positive errno on failure.
    257  1.19  sommerfe  */
    258  1.19  sommerfe int
    259  1.19  sommerfe cache_revlookup (vp, dvpp, bpp, bufp)
    260  1.19  sommerfe 	struct vnode *vp, **dvpp;
    261  1.19  sommerfe 	char **bpp;
    262  1.19  sommerfe 	char *bufp;
    263  1.19  sommerfe {
    264  1.19  sommerfe 	struct namecache *ncp;
    265  1.19  sommerfe 	struct vnode *dvp;
    266  1.19  sommerfe 	struct ncvhashhead *nvcpp;
    267  1.19  sommerfe 
    268  1.19  sommerfe 	if (!doingcache)
    269  1.19  sommerfe 		goto out;
    270  1.19  sommerfe 
    271  1.19  sommerfe 	nvcpp = &ncvhashtbl[(vp->v_id & ncvhash)];
    272  1.19  sommerfe 
    273  1.19  sommerfe 	for (ncp = nvcpp->lh_first; ncp != 0; ncp = ncp->nc_vhash.le_next) {
    274  1.19  sommerfe 		if ((ncp->nc_vp == vp) &&
    275  1.19  sommerfe 		    (ncp->nc_vpid == vp->v_id) &&
    276  1.19  sommerfe 		    ((dvp = ncp->nc_dvp) != 0) &&
    277  1.19  sommerfe 		    (dvp != vp) && 		/* avoid pesky . entries.. */
    278  1.19  sommerfe 		    (dvp->v_id == ncp->nc_dvpid))
    279  1.19  sommerfe 		{
    280  1.19  sommerfe 			char *bp;
    281  1.19  sommerfe 
    282  1.19  sommerfe #ifdef DIAGNOSTIC
    283  1.19  sommerfe 			if ((ncp->nc_nlen == 1) &&
    284  1.19  sommerfe 			    (ncp->nc_name[0] == '.'))
    285  1.19  sommerfe 				panic("cache_revlookup: found entry for .");
    286  1.19  sommerfe 
    287  1.19  sommerfe 			if ((ncp->nc_nlen == 2) &&
    288  1.19  sommerfe 			    (ncp->nc_name[0] == '.') &&
    289  1.19  sommerfe 			    (ncp->nc_name[1] == '.'))
    290  1.19  sommerfe 				panic("cache_revlookup: found entry for ..");
    291  1.19  sommerfe #endif
    292  1.19  sommerfe 			nchstats.ncs_revhits++;
    293  1.19  sommerfe 
    294  1.19  sommerfe 			if (bufp) {
    295  1.19  sommerfe 				bp = *bpp;
    296  1.19  sommerfe 				bp -= ncp->nc_nlen;
    297  1.19  sommerfe 				if (bp <= bufp) {
    298  1.19  sommerfe 					*dvpp = 0;
    299  1.19  sommerfe 					return ERANGE;
    300  1.19  sommerfe 				}
    301  1.19  sommerfe 				memcpy(bp, ncp->nc_name, ncp->nc_nlen);
    302  1.19  sommerfe 				*bpp = bp;
    303  1.19  sommerfe 			}
    304  1.19  sommerfe 
    305  1.19  sommerfe 			/* XXX MP: how do we know dvp won't evaporate? */
    306  1.19  sommerfe 			*dvpp = dvp;
    307  1.19  sommerfe 			return 0;
    308  1.19  sommerfe 		}
    309  1.19  sommerfe 	}
    310  1.19  sommerfe 	nchstats.ncs_revmiss++;
    311  1.19  sommerfe  out:
    312  1.19  sommerfe 	*dvpp = 0;
    313  1.19  sommerfe 	return -1;
    314  1.19  sommerfe }
    315  1.19  sommerfe 
    316  1.19  sommerfe /*
    317   1.1       cgd  * Add an entry to the cache
    318   1.1       cgd  */
    319  1.13  christos void
    320   1.5   mycroft cache_enter(dvp, vp, cnp)
    321   1.5   mycroft 	struct vnode *dvp;
    322   1.5   mycroft 	struct vnode *vp;
    323   1.5   mycroft 	struct componentname *cnp;
    324   1.1       cgd {
    325   1.9   mycroft 	register struct namecache *ncp;
    326   1.9   mycroft 	register struct nchashhead *ncpp;
    327  1.19  sommerfe 	register struct ncvhashhead *nvcpp;
    328   1.1       cgd 
    329   1.5   mycroft #ifdef DIAGNOSTIC
    330   1.5   mycroft 	if (cnp->cn_namelen > NCHNAMLEN)
    331   1.5   mycroft 		panic("cache_enter: name too long");
    332   1.5   mycroft #endif
    333   1.1       cgd 	if (!doingcache)
    334   1.1       cgd 		return;
    335   1.1       cgd 	/*
    336   1.1       cgd 	 * Free the cache slot at head of lru chain.
    337   1.1       cgd 	 */
    338   1.1       cgd 	if (numcache < desiredvnodes) {
    339  1.18   thorpej 		ncp = pool_get(&namecache_pool, PR_WAITOK);
    340  1.17     perry 		memset((char *)ncp, 0, sizeof(*ncp));
    341   1.1       cgd 		numcache++;
    342  1.13  christos 	} else if ((ncp = nclruhead.tqh_first) != NULL) {
    343   1.9   mycroft 		TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
    344   1.9   mycroft 		if (ncp->nc_hash.le_prev != 0) {
    345   1.9   mycroft 			LIST_REMOVE(ncp, nc_hash);
    346   1.9   mycroft 			ncp->nc_hash.le_prev = 0;
    347   1.5   mycroft 		}
    348  1.19  sommerfe 		if (ncp->nc_vhash.le_prev != 0) {
    349  1.19  sommerfe 			LIST_REMOVE(ncp, nc_vhash);
    350  1.19  sommerfe 			ncp->nc_vhash.le_prev = 0;
    351  1.19  sommerfe 		}
    352   1.1       cgd 	} else
    353   1.1       cgd 		return;
    354   1.1       cgd 	/* grab the vnode we just found */
    355   1.5   mycroft 	ncp->nc_vp = vp;
    356   1.5   mycroft 	if (vp)
    357   1.5   mycroft 		ncp->nc_vpid = vp->v_id;
    358  1.11   mycroft 	else {
    359  1.11   mycroft 		/*
    360  1.11   mycroft 		 * For negative hits, save the ISWHITEOUT flag so we can
    361  1.11   mycroft 		 * restore it later when the cache entry is used again.
    362  1.11   mycroft 		 */
    363  1.11   mycroft 		ncp->nc_vpid = cnp->cn_flags & ISWHITEOUT;
    364  1.11   mycroft 	}
    365   1.1       cgd 	/* fill in cache info */
    366   1.5   mycroft 	ncp->nc_dvp = dvp;
    367   1.5   mycroft 	ncp->nc_dvpid = dvp->v_id;
    368   1.5   mycroft 	ncp->nc_nlen = cnp->cn_namelen;
    369  1.17     perry 	memcpy(ncp->nc_name, cnp->cn_nameptr, (unsigned)ncp->nc_nlen);
    370   1.9   mycroft 	TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
    371  1.12        ws 	ncpp = &nchashtbl[(cnp->cn_hash ^ dvp->v_id) & nchash];
    372   1.9   mycroft 	LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
    373  1.19  sommerfe 
    374  1.19  sommerfe 	ncp->nc_vhash.le_prev = 0;
    375  1.19  sommerfe 	ncp->nc_vhash.le_next = 0;
    376  1.19  sommerfe 
    377  1.19  sommerfe 	/*
    378  1.19  sommerfe 	 * Create reverse-cache entries (used in getcwd) for directories.
    379  1.19  sommerfe 	 */
    380  1.19  sommerfe 	if (vp &&
    381  1.19  sommerfe 	    (vp != dvp) &&
    382  1.19  sommerfe 	    (vp->v_type == VDIR) &&
    383  1.19  sommerfe 	    ((ncp->nc_nlen > 2) ||
    384  1.19  sommerfe 	     ((ncp->nc_nlen == 2) && (ncp->nc_name[0] != '.') && (ncp->nc_name[1] != '.')) ||
    385  1.19  sommerfe 	     ((ncp->nc_nlen == 1) && (ncp->nc_name[0] != '.'))))
    386  1.19  sommerfe 	{
    387  1.19  sommerfe 		nvcpp = &ncvhashtbl[(vp->v_id & ncvhash)];
    388  1.19  sommerfe 		LIST_INSERT_HEAD(nvcpp, ncp, nc_vhash);
    389  1.19  sommerfe 	}
    390  1.19  sommerfe 
    391   1.1       cgd }
    392   1.1       cgd 
    393   1.1       cgd /*
    394   1.1       cgd  * Name cache initialization, from vfs_init() when we are booting
    395   1.1       cgd  */
    396  1.13  christos void
    397   1.1       cgd nchinit()
    398   1.1       cgd {
    399   1.1       cgd 
    400   1.9   mycroft 	TAILQ_INIT(&nclruhead);
    401  1.14       chs 	nchashtbl = hashinit(desiredvnodes, M_CACHE, M_WAITOK, &nchash);
    402  1.19  sommerfe 	ncvhashtbl = hashinit(desiredvnodes/8, M_CACHE, M_WAITOK, &ncvhash);
    403  1.18   thorpej 	pool_init(&namecache_pool, sizeof(struct namecache), 0, 0, 0,
    404  1.18   thorpej 	    "ncachepl", 0, pool_page_alloc_nointr, pool_page_free_nointr,
    405  1.18   thorpej 	    M_CACHE);
    406   1.1       cgd }
    407   1.1       cgd 
    408   1.1       cgd /*
    409   1.1       cgd  * Cache flush, a particular vnode; called when a vnode is renamed to
    410   1.1       cgd  * hide entries that would now be invalid
    411   1.1       cgd  */
    412  1.13  christos void
    413   1.1       cgd cache_purge(vp)
    414   1.1       cgd 	struct vnode *vp;
    415   1.1       cgd {
    416   1.9   mycroft 	struct namecache *ncp;
    417   1.9   mycroft 	struct nchashhead *ncpp;
    418   1.1       cgd 
    419   1.1       cgd 	vp->v_id = ++nextvnodeid;
    420   1.1       cgd 	if (nextvnodeid != 0)
    421   1.1       cgd 		return;
    422   1.5   mycroft 	for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
    423   1.9   mycroft 		for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) {
    424   1.1       cgd 			ncp->nc_vpid = 0;
    425   1.1       cgd 			ncp->nc_dvpid = 0;
    426   1.1       cgd 		}
    427   1.1       cgd 	}
    428   1.1       cgd 	vp->v_id = ++nextvnodeid;
    429   1.1       cgd }
    430   1.1       cgd 
    431   1.1       cgd /*
    432   1.1       cgd  * Cache flush, a whole filesystem; called when filesys is umounted to
    433   1.1       cgd  * remove entries that would now be invalid
    434   1.1       cgd  *
    435   1.1       cgd  * The line "nxtcp = nchhead" near the end is to avoid potential problems
    436   1.1       cgd  * if the cache lru chain is modified while we are dumping the
    437   1.1       cgd  * inode.  This makes the algorithm O(n^2), but do you think I care?
    438   1.1       cgd  */
    439  1.13  christos void
    440   1.1       cgd cache_purgevfs(mp)
    441   1.1       cgd 	struct mount *mp;
    442   1.1       cgd {
    443   1.1       cgd 	register struct namecache *ncp, *nxtcp;
    444   1.1       cgd 
    445   1.9   mycroft 	for (ncp = nclruhead.tqh_first; ncp != 0; ncp = nxtcp) {
    446   1.5   mycroft 		if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) {
    447   1.9   mycroft 			nxtcp = ncp->nc_lru.tqe_next;
    448   1.1       cgd 			continue;
    449   1.5   mycroft 		}
    450   1.1       cgd 		/* free the resources we had */
    451   1.1       cgd 		ncp->nc_vp = NULL;
    452   1.1       cgd 		ncp->nc_dvp = NULL;
    453   1.9   mycroft 		TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
    454   1.9   mycroft 		if (ncp->nc_hash.le_prev != 0) {
    455   1.9   mycroft 			LIST_REMOVE(ncp, nc_hash);
    456   1.9   mycroft 			ncp->nc_hash.le_prev = 0;
    457   1.5   mycroft 		}
    458  1.19  sommerfe 		if (ncp->nc_vhash.le_prev != 0) {
    459  1.19  sommerfe 			LIST_REMOVE(ncp, nc_vhash);
    460  1.19  sommerfe 			ncp->nc_vhash.le_prev = 0;
    461  1.19  sommerfe 		}
    462   1.1       cgd 		/* cause rescan of list, it may have altered */
    463   1.9   mycroft 		nxtcp = nclruhead.tqh_first;
    464   1.9   mycroft 		TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);
    465   1.1       cgd 	}
    466   1.1       cgd }
    467  1.19  sommerfe 
    468