BSD 4_4_Lite2 release

[unix-history] / usr / src / sys / kern / vfs_cache.c

diff --git a/usr/src/sys/kern/vfs_cache.c b/usr/src/sys/kern/vfs_cache.c
index 4ccfd72..c20966b 100644 (file)
--- a/usr/src/sys/kern/vfs_cache.c
+++ b/usr/src/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.
  *
  *     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:
  * 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.
  *
  * 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>
  */
 
 #include <sys/param.h>


@@ -51,6 +56,9 @@
  * obtained from (vp, name) where vp refers to the directory
  * containing name.
  *
  * 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.
  * 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.
  */
 /*
  * 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 */
 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 */
 
 /*
 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).
  *
  * 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;
 {
 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);
                return (0);

+       }

        if (cnp->cn_namelen > NCHNAMLEN) {
                nchstats.ncs_long++;
                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 &&
                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;
        }
                    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);
        }
                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++;
                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++;
                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);
        }
 
                *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;
 {
 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
 
 #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++;
                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;
                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_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);
        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
  */
 }
 
 /*
  * Name cache initialization, from vfs_init() when we are booting
  */

+void

 nchinit()
 {
 
 nchinit()
 {
 

-       nchtail = &nchhead;
+       TAILQ_INIT(&nclruhead);

        nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash);
 }
 
 /*
        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;
 {
 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--) {
 
        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;
 }
 
 /*
        }
        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;
 {
 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;

        }
 }
        }
 }