The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/vfs_cache.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*
    2  * Copyright (c) 1989, 1993
    3  *      The Regents of the University of California.  All rights reserved.
    4  * Copyright (c) 1995
    5  *      Poul-Henning Kamp.  All rights reserved.
    6  *
    7  * Redistribution and use in source and binary forms, with or without
    8  * modification, are permitted provided that the following conditions
    9  * are met:
   10  * 1. Redistributions of source code must retain the above copyright
   11  *    notice, this list of conditions and the following disclaimer.
   12  * 2. Redistributions in binary form must reproduce the above copyright
   13  *    notice, this list of conditions and the following disclaimer in the
   14  *    documentation and/or other materials provided with the distribution.
   15  * 3. All advertising materials mentioning features or use of this software
   16  *    must display the following acknowledgement:
   17  *      This product includes software developed by the University of
   18  *      California, Berkeley and its contributors.
   19  * 4. Neither the name of the University nor the names of its contributors
   20  *    may be used to endorse or promote products derived from this software
   21  *    without specific prior written permission.
   22  *
   23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   33  * SUCH DAMAGE.
   34  *
   35  *      @(#)vfs_cache.c 8.3 (Berkeley) 8/22/94
   36  * $FreeBSD: src/sys/kern/vfs_cache.c,v 1.20.4.1 1999/09/05 08:15:39 peter Exp $
   37  */
   38 
   39 #include <sys/param.h>
   40 #include <sys/systm.h>
   41 #include <sys/kernel.h>
   42 #include <sys/sysctl.h>
   43 #include <sys/time.h>
   44 #include <sys/mount.h>
   45 #include <sys/vnode.h>
   46 #include <sys/namei.h>
   47 #include <sys/errno.h>
   48 #include <sys/malloc.h>
   49 
   50 #define MAXVNODEUSE 32
   51 
   52 /*
   53  * Name caching works as follows:
   54  *
   55  * Names found by directory scans are retained in a cache
   56  * for future reference.  It is managed LRU, so frequently
   57  * used names will hang around.  Cache is indexed by hash value
   58  * obtained from (vp, name) where vp refers to the directory
   59  * containing name.
   60  *
   61  * If it is a "negative" entry, (that we know a name to >not< exist)
   62  * we point out entry at our own "nchENOENT", to avoid too much special
   63  * casing in the inner loops of lookup.
   64  *
   65  * For simplicity (and economy of storage), names longer than
   66  * a maximum length of NCHNAMLEN are not cached; they occur
   67  * infrequently in any case, and are almost never of interest.
   68  *
   69  * Upon reaching the last segment of a path, if the reference
   70  * is for DELETE, or NOCACHE is set (rewrite), and the
   71  * name is located in the cache, it will be dropped.
   72  */
   73 
   74 /*
   75  * Structures associated with name cacheing.
   76  */
   77 static LIST_HEAD(nchashhead, namecache) *nchashtbl;     /* Hash Table */
   78 static TAILQ_HEAD(, namecache) nclruhead;       /* LRU chain */
   79 static u_long   nchash;                 /* size of hash table */
   80 struct nchstats nchstats;               /* cache effectiveness statistics */
   81 static struct vnode nchENOENT;          /* our own "novnode" */
   82 static int doingcache = 1;              /* 1 => enable the cache */
   83 SYSCTL_INT(_debug, OID_AUTO, vfscache, CTLFLAG_RW, &doingcache, 0, "");
   84 static u_long   numcache;
   85 u_long  numvnodes;
   86 
   87 #ifdef NCH_STATISTICS
   88 u_long  nchnbr;
   89 #define NCHNBR(ncp) (ncp)->nc_nbr = ++nchnbr;
   90 #define NCHHIT(ncp) (ncp)->nc_hits++
   91 #else
   92 #define NCHNBR(ncp)
   93 #define NCHHIT(ncp)
   94 #endif
   95 
   96 #define PURGE(ncp)  {                                           \
   97         LIST_REMOVE(ncp, nc_hash);                              \
   98         ncp->nc_hash.le_prev = 0;                               \
   99         TAILQ_REMOVE(&nclruhead, ncp, nc_lru);                  \
  100         TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); }
  101 
  102 #define TOUCH(ncp)  {                                           \
  103         if (ncp->nc_lru.tqe_next == 0) { } else {               \
  104                 TAILQ_REMOVE(&nclruhead, ncp, nc_lru);          \
  105                 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);     \
  106                 NCHNBR(ncp); } }
  107 
  108 /*
  109  * Lookup an entry in the cache
  110  *
  111  * We don't do this if the segment name is long, simply so the cache
  112  * can avoid holding long names (which would either waste space, or
  113  * add greatly to the complexity).
  114  *
  115  * Lookup is called with dvp pointing to the directory to search,
  116  * cnp pointing to the name of the entry being sought.
  117  * If the lookup succeeds, the vnode is returned in *vpp, and a status
  118  * of -1 is returned.
  119  * If the lookup determines that the name does not exist (negative cacheing),
  120  * a status of ENOENT is returned.
  121  * If the lookup fails, a status of zero is returned.
  122  */
  123 
  124 int
  125 cache_lookup(dvp, vpp, cnp)
  126         struct vnode *dvp;
  127         struct vnode **vpp;
  128         struct componentname *cnp;
  129 {
  130         register struct namecache *ncp,*nnp;
  131         register struct nchashhead *ncpp;
  132 
  133         if (!doingcache) {
  134                 cnp->cn_flags &= ~MAKEENTRY;
  135                 return (0);
  136         }
  137 
  138         if (cnp->cn_namelen > NCHNAMLEN) {
  139                 nchstats.ncs_long++;
  140                 cnp->cn_flags &= ~MAKEENTRY;
  141                 return (0);
  142         }
  143 
  144         ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) % nchash];
  145         for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
  146                 nnp = ncp->nc_hash.le_next;
  147                 /* If one of the vp's went stale, don't bother anymore. */
  148                 if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) ||
  149                     (ncp->nc_vpid  != ncp->nc_vp->v_id)) {
  150                         nchstats.ncs_falsehits++;
  151                         PURGE(ncp);
  152                         continue;
  153                 }
  154                 /* Now that we know the vp's to be valid, is it ours ? */
  155                 if (ncp->nc_dvp == dvp &&
  156                     ncp->nc_nlen == cnp->cn_namelen &&
  157                     !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
  158                         goto found;     /* Fanatism considered bad. */
  159         }
  160         nchstats.ncs_miss++;
  161         return (0);
  162 
  163     found:
  164         NCHHIT(ncp);
  165 
  166         /* We don't want to have an entry, so dump it */
  167         if ((cnp->cn_flags & MAKEENTRY) == 0) {
  168                 nchstats.ncs_badhits++;
  169                 PURGE(ncp);
  170                 return (0);
  171         }
  172 
  173         /* We found a "positive" match, return the vnode */
  174         if (ncp->nc_vp != &nchENOENT) {
  175                 nchstats.ncs_goodhits++;
  176                 TOUCH(ncp);
  177                 *vpp = ncp->nc_vp;
  178                 if ((*vpp)->v_usage < MAXVNODEUSE)
  179                         (*vpp)->v_usage++;
  180                 return (-1);
  181         }
  182 
  183         /* We found a negative match, and want to create it, so purge */
  184         if (cnp->cn_nameiop == CREATE) {
  185                 nchstats.ncs_badhits++;
  186                 PURGE(ncp);
  187                 return (0);
  188         }
  189 
  190         /* The name does not exists */
  191         nchstats.ncs_neghits++;
  192         TOUCH(ncp);
  193         return (ENOENT);
  194 }
  195 
  196 /*
  197  * Add an entry to the cache.
  198  */
  199 
  200 void
  201 cache_enter(dvp, vp, cnp)
  202         struct vnode *dvp;
  203         struct vnode *vp;
  204         struct componentname *cnp;
  205 {
  206         register struct namecache *ncp;
  207         register struct nchashhead *ncpp;
  208 
  209         if (!doingcache)
  210                 return;
  211 
  212         if (cnp->cn_namelen > NCHNAMLEN) {
  213                 printf("cache_enter: name too long");
  214                 return;
  215         }
  216 
  217         if (numcache < numvnodes) {
  218                 /* Add one more entry */
  219                 ncp = (struct namecache *)
  220                         malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
  221                 bzero((char *)ncp, sizeof *ncp);
  222                 numcache++;
  223         } else if (ncp = nclruhead.tqh_first) {
  224                 /* reuse an old entry */
  225                 TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
  226                 if (ncp->nc_hash.le_prev != 0) {
  227                         LIST_REMOVE(ncp, nc_hash);
  228                         ncp->nc_hash.le_prev = 0;
  229                 }
  230         } else {
  231                 /* give up */
  232                 return;
  233         }
  234 
  235         /* If vp is NULL this is a "negative" cache entry */
  236         if (!vp)
  237                 vp = &nchENOENT;
  238 
  239         /* fill in cache info */
  240         ncp->nc_vp = vp;
  241         if (vp->v_usage < MAXVNODEUSE)
  242                 ++vp->v_usage;
  243         ncp->nc_vpid = vp->v_id;
  244         ncp->nc_dvp = dvp;
  245         ncp->nc_dvpid = dvp->v_id;
  246         ncp->nc_nlen = cnp->cn_namelen;
  247         bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
  248         TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
  249         ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) % nchash];
  250         LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
  251 }
  252 
  253 /*
  254  * Name cache initialization, from vfs_init() when we are booting
  255  */
  256 
  257 void
  258 nchinit()
  259 {
  260 
  261         TAILQ_INIT(&nclruhead);
  262         nchashtbl = phashinit(desiredvnodes, M_CACHE, &nchash);
  263         cache_purge(&nchENOENT);        /* Initialize v_id */
  264 }
  265 
  266 /*
  267  * Invalidate all entries to a particular vnode.
  268  *
  269  * We actually just increment the v_id, that will do it.  The stale entries 
  270  * will be purged by lookup as they get found.
  271  * If the v_id wraps around, we need to ditch the entire cache, to avoid
  272  * confusion.
  273  * No valid vnode will ever have (v_id == 0).
  274  */
  275 
  276 void
  277 cache_purge(vp)
  278         struct vnode *vp;
  279 {
  280         struct nchashhead *ncpp;
  281         static u_long nextvnodeid;
  282 
  283         vp->v_id = ++nextvnodeid;
  284         if (nextvnodeid != 0)
  285                 return;
  286         for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) {
  287                 while(ncpp->lh_first)
  288                         PURGE(ncpp->lh_first);
  289         }
  290         nchENOENT.v_id = ++nextvnodeid;
  291         vp->v_id = ++nextvnodeid;
  292 }
  293 
  294 /*
  295  * Flush all entries referencing a particular filesystem.
  296  *
  297  * Since we need to check it anyway, we will flush all the invalid
  298  * entries at the same time.
  299  *
  300  * If we purge anything, we scan the hash-bucket again.  There is only
  301  * a handful of entries, so it cheap and simple.
  302  */
  303 
  304 void
  305 cache_purgevfs(mp)
  306         struct mount *mp;
  307 {
  308         struct nchashhead *ncpp;
  309         struct namecache *ncp;
  310 
  311         /* Scan hash tables for applicable entries */
  312         for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) {
  313                 ncp = ncpp->lh_first;
  314                 while(ncp) {
  315                         if (ncp->nc_dvpid != ncp->nc_dvp->v_id ||
  316                             ncp->nc_vpid != ncp->nc_vp->v_id ||
  317                             ncp->nc_dvp->v_mount == mp) {
  318                                 PURGE(ncp);
  319                                 ncp = ncpp->lh_first;
  320                         } else {
  321                                 ncp = ncp->nc_hash.le_next;
  322                         }
  323                 }
  324         }
  325 }

Cache object: 901534ebae2b84fbf0d8c47b9ade2ec6


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.