Import 4.4BSD-Lite2 onto the vendor branch, note that in the kernel, all

files are off the vendor branch, so this should not change anything.

A "U" marker generally means that the file was not changed in between
the 4.4Lite and Lite-2 releases, and does not need a merge.  "C" generally
means that there was a change.
[note new unused (in this form) syscalls.conf, to be 'cvs rm'ed]

1 files changed, 153 insertions, 161 deletions

diff --git a/sys/kern/vfs_cache.c b/sys/kern/vfs_cache.c
index 4ccfd72..c20966b 100644
--- a/sys/kern/vfs_cache.c
+++ b/sys/kern/vfs_cache.c
@@ -1,7 +1,10 @@
 /*
- * Copyright (c) 1989, 1993
+ * Copyright (c) 1989, 1993, 1995
  *	The Regents of the University of California.  All rights reserved.
  *
+ * This code is derived from software contributed to Berkeley by
+ * Poul-Henning Kamp of the FreeBSD Project.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
@@ -30,7 +33,9 @@
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
- *	@(#)vfs_cache.c	8.1 (Berkeley) 6/10/93
+ * from: vfs_cache.c,v 1.11 1995/03/12 02:01:20 phk Exp $
+ *
+ *	@(#)vfs_cache.c	8.5 (Berkeley) 3/22/95
  */
 
 #include <sys/param.h>
@@ -51,6 +56,9 @@
  * obtained from (vp, name) where vp refers to the directory
  * containing name.
  *
+ * If it is a "negative" entry, (i.e. for a name that is known NOT to
+ * exist) the vnode pointer will be NULL.
+ *
  * 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.
@@ -63,266 +71,250 @@
 /*
  * Structures associated with name cacheing.
  */
-struct namecache **nchashtbl;
+#define NCHHASH(dvp, cnp) \
+	(&nchashtbl[((dvp)->v_id + (cnp)->cn_hash) & nchash])
+LIST_HEAD(nchashhead, namecache) *nchashtbl;	/* Hash Table */
 u_long	nchash;				/* size of hash table - 1 */
 long	numcache;			/* number of cache entries allocated */
-struct	namecache *nchhead, **nchtail;	/* LRU chain pointers */
+TAILQ_HEAD(, namecache) nclruhead;	/* LRU chain */
 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
+ * Delete an entry from its hash list and move it to the front
+ * of the LRU list for immediate reuse.
+ */
+#define PURGE(ncp)  {						\
+	LIST_REMOVE(ncp, nc_hash);				\
+	ncp->nc_hash.le_prev = 0;				\
+	TAILQ_REMOVE(&nclruhead, ncp, nc_lru);			\
+	TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);		\
+}
+
+/*
+ * Move an entry that has been used to the tail of the LRU list
+ * so that it will be preserved for future use.
+ */
+#define TOUCH(ncp)  {						\
+	if (ncp->nc_lru.tqe_next != 0) {			\
+		TAILQ_REMOVE(&nclruhead, ncp, nc_lru);		\
+		TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);	\
+	}							\
+}
+
+/*
+ * Lookup an entry 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.
+ * Lookup is called with dvp pointing to the directory to search,
+ * cnp pointing to the name of the entry being sought. If the lookup
+ * succeeds, the vnode is returned in *vpp, 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.
  */
+
 int
 cache_lookup(dvp, vpp, cnp)
 	struct vnode *dvp;
 	struct vnode **vpp;
 	struct componentname *cnp;
 {
-	register struct namecache *ncp, *ncq, **ncpp;
+	register struct namecache *ncp, *nnp;
+	register struct nchashhead *ncpp;
 
-	if (!doingcache)
+	if (!doingcache) {
+		cnp->cn_flags &= ~MAKEENTRY;
 		return (0);
+	}
 	if (cnp->cn_namelen > NCHNAMLEN) {
 		nchstats.ncs_long++;
 		cnp->cn_flags &= ~MAKEENTRY;
 		return (0);
 	}
-	ncpp = &nchashtbl[cnp->cn_hash & nchash];
-	for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) {
+
+	ncpp = NCHHASH(dvp, cnp);
+	for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
+		nnp = ncp->nc_hash.le_next;
+		/* If one of the vp's went stale, don't bother anymore. */
+		if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) ||
+		    (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id)) {
+			nchstats.ncs_falsehits++;
+			PURGE(ncp);
+			continue;
+		}
+		/* Now that we know the vp's to be valid, is it ours ? */
 		if (ncp->nc_dvp == dvp &&
-		    ncp->nc_dvpid == dvp->v_id &&
 		    ncp->nc_nlen == cnp->cn_namelen &&
 		    !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
 			break;
 	}
-	if (ncp == NULL) {
+
+	/* We failed to find an entry */
+	if (ncp == 0) {
 		nchstats.ncs_miss++;
 		return (0);
 	}
-	if (!(cnp->cn_flags & MAKEENTRY)) {
+
+	/* We don't want to have an entry, so dump it */
+	if ((cnp->cn_flags & MAKEENTRY) == 0) {
 		nchstats.ncs_badhits++;
-	} else if (ncp->nc_vp == NULL) {
-		if (cnp->cn_nameiop != CREATE) {
-			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 {
+		PURGE(ncp);
+		return (0);
+	} 
+
+	/* We found a "positive" match, return the vnode */
+        if (ncp->nc_vp) {
 		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;
-		}
+		TOUCH(ncp);
 		*vpp = ncp->nc_vp;
 		return (-1);
 	}
 
+	/* We found a negative match, and want to create it, so purge */
+	if (cnp->cn_nameiop == CREATE) {
+		nchstats.ncs_badhits++;
+		PURGE(ncp);
+		return (0);
+	}
+
 	/*
-	 * Last component and we are renaming or deleting,
-	 * the cache entry is invalid, or otherwise don't
-	 * want cache entry to exist.
+	 * We found a "negative" match, ENOENT notifies client of this match.
+	 * The nc_vpid field records whether this is a whiteout.
 	 */
-	/* remove from LRU chain */
-	if (ncq = ncp->nc_nxt)
-		ncq->nc_prev = ncp->nc_prev;
-	else
-		nchtail = ncp->nc_prev;
-	*ncp->nc_prev = ncq;
-	/* remove from hash chain */
-	if (ncq = ncp->nc_forw)
-		ncq->nc_back = ncp->nc_back;
-	*ncp->nc_back = ncq;
-	/* and make a dummy hash chain */
-	ncp->nc_forw = NULL;
-	ncp->nc_back = NULL;
-	/* insert at head of LRU list (first to grab) */
-	if (ncq = nchhead)
-		ncq->nc_prev = &ncp->nc_nxt;
-	else
-		nchtail = &ncp->nc_nxt;
-	nchhead = ncp;
-	ncp->nc_nxt = ncq;
-	ncp->nc_prev = &nchhead;
-	return (0);
+	nchstats.ncs_neghits++;
+	TOUCH(ncp);
+	cnp->cn_flags |= ncp->nc_vpid;
+	return (ENOENT);
 }
 
 /*
- * Add an entry to the cache
+ * Add an entry to the cache.
  */
+void
 cache_enter(dvp, vp, cnp)
 	struct vnode *dvp;
 	struct vnode *vp;
 	struct componentname *cnp;
 {
-	register struct namecache *ncp, *ncq, **ncpp;
+	register struct namecache *ncp;
+	register struct nchashhead *ncpp;
+
+	if (!doingcache)
+		return;
 
 #ifdef DIAGNOSTIC
 	if (cnp->cn_namelen > NCHNAMLEN)
 		panic("cache_enter: name too long");
 #endif
-	if (!doingcache)
-		return;
+
 	/*
-	 * Free the cache slot at head of lru chain.
+	 * We allocate a new entry if we are less than the maximum
+	 * allowed and the one at the front of the LRU list is in use.
+	 * Otherwise we use the one at the front of the LRU list.
 	 */
-	if (numcache < desiredvnodes) {
+	if (numcache < desiredvnodes &&
+	    ((ncp = nclruhead.tqh_first) == NULL ||
+	    ncp->nc_hash.le_prev != 0)) {
+		/* Add one more entry */
 		ncp = (struct namecache *)
 			malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
 		bzero((char *)ncp, sizeof *ncp);
 		numcache++;
-	} else if (ncp = nchhead) {
-		/* remove from lru chain */
-		if (ncq = ncp->nc_nxt)
-			ncq->nc_prev = ncp->nc_prev;
-		else
-			nchtail = ncp->nc_prev;
-		*ncp->nc_prev = ncq;
-		/* remove from old hash chain, if on one */
-		if (ncp->nc_back) {
-			if (ncq = ncp->nc_forw)
-				ncq->nc_back = ncp->nc_back;
-			*ncp->nc_back = ncq;
-			ncp->nc_forw = NULL;
-			ncp->nc_back = NULL;
+	} else if (ncp = nclruhead.tqh_first) {
+		/* reuse an old entry */
+		TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
+		if (ncp->nc_hash.le_prev != 0) {
+			LIST_REMOVE(ncp, nc_hash);
+			ncp->nc_hash.le_prev = 0;
 		}
-	} else
+	} else {
+		/* give up */
 		return;
-	/* grab the vnode we just found */
+	}
+
+	/*
+	 * Fill in cache info, if vp is NULL this is a "negative" cache entry.
+	 * For negative entries, we have to record whether it is a whiteout.
+	 * the whiteout flag is stored in the nc_vpid field which is
+	 * otherwise unused.
+	 */
 	ncp->nc_vp = vp;
 	if (vp)
 		ncp->nc_vpid = vp->v_id;
 	else
-		ncp->nc_vpid = 0;
-	/* fill in cache info */
+		ncp->nc_vpid = cnp->cn_flags & ISWHITEOUT;
 	ncp->nc_dvp = dvp;
 	ncp->nc_dvpid = dvp->v_id;
 	ncp->nc_nlen = cnp->cn_namelen;
 	bcopy(cnp->cn_nameptr, 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 */
-	ncpp = &nchashtbl[cnp->cn_hash & nchash];
-	if (ncq = *ncpp)
-		ncq->nc_back = &ncp->nc_forw;
-	ncp->nc_forw = ncq;
-	ncp->nc_back = ncpp;
-	*ncpp = ncp;
+	TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
+	ncpp = NCHHASH(dvp, cnp);
+	LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
 }
 
 /*
  * Name cache initialization, from vfs_init() when we are booting
  */
+void
 nchinit()
 {
 
-	nchtail = &nchhead;
+	TAILQ_INIT(&nclruhead);
 	nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash);
 }
 
 /*
- * Cache flush, a particular vnode; called when a vnode is renamed to
- * hide entries that would now be invalid
+ * Invalidate a all entries to particular vnode.
+ * 
+ * We actually just increment the v_id, that will do it. The entries will
+ * be purged by lookup as they get found. If the v_id wraps around, we
+ * need to ditch the entire cache, to avoid confusion. No valid vnode will
+ * ever have (v_id == 0).
  */
+void
 cache_purge(vp)
 	struct vnode *vp;
 {
-	struct namecache *ncp, **ncpp;
+	struct namecache *ncp;
+	struct nchashhead *ncpp;
 
 	vp->v_id = ++nextvnodeid;
 	if (nextvnodeid != 0)
 		return;
 	for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
-		for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) {
-			ncp->nc_vpid = 0;
-			ncp->nc_dvpid = 0;
-		}
+		while (ncp = ncpp->lh_first)
+			PURGE(ncp);
 	}
 	vp->v_id = ++nextvnodeid;
 }
 
 /*
- * Cache flush, a whole filesystem; called when filesys is umounted to
- * remove entries that would now be invalid
+ * Flush all entries referencing a particular filesystem.
  *
- * 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?
+ * Since we need to check it anyway, we will flush all the invalid
+ * entriess at the same time.
  */
+void
 cache_purgevfs(mp)
 	struct mount *mp;
 {
-	register struct namecache *ncp, *nxtcp;
+	struct nchashhead *ncpp;
+	struct namecache *ncp, *nnp;
 
-	for (ncp = nchhead; ncp; ncp = nxtcp) {
-		if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) {
-			nxtcp = ncp->nc_nxt;
-			continue;
-		}
-		/* free the resources we had */
-		ncp->nc_vp = NULL;
-		ncp->nc_dvp = NULL;
-		/* remove from old hash chain, if on one */
-		if (ncp->nc_back) {
-			if (nxtcp = ncp->nc_forw)
-				nxtcp->nc_back = ncp->nc_back;
-			*ncp->nc_back = nxtcp;
-			ncp->nc_forw = NULL;
-			ncp->nc_back = NULL;
+	/* Scan hash tables for applicable entries */
+	for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
+		for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
+			nnp = ncp->nc_hash.le_next;
+			if (ncp->nc_dvpid != ncp->nc_dvp->v_id ||
+			    (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id) ||
+			    ncp->nc_dvp->v_mount == mp) {
+				PURGE(ncp);
+			}
 		}
-		/* delete this entry from LRU chain */
-		if (nxtcp = ncp->nc_nxt)
-			nxtcp->nc_prev = ncp->nc_prev;
-		else
-			nchtail = ncp->nc_prev;
-		*ncp->nc_prev = nxtcp;
-		/* cause rescan of list, it may have altered */
-		/* also put the now-free entry at head of LRU */
-		if (nxtcp = nchhead)
-			nxtcp->nc_prev = &ncp->nc_nxt;
-		else
-			nchtail = &ncp->nc_nxt;
-		nchhead = ncp;
-		ncp->nc_nxt = nxtcp;
-		ncp->nc_prev = &nchhead;
 	}
 }