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