vfs_cache.c revision 12968
11541Srgrimes/* 21541Srgrimes * Copyright (c) 1989, 1993 31541Srgrimes * The Regents of the University of California. All rights reserved. 46968Sphk * Copyright (c) 1995 56968Sphk * Poul-Henning Kamp. All rights reserved. 61541Srgrimes * 71541Srgrimes * Redistribution and use in source and binary forms, with or without 81541Srgrimes * modification, are permitted provided that the following conditions 91541Srgrimes * are met: 101541Srgrimes * 1. Redistributions of source code must retain the above copyright 111541Srgrimes * notice, this list of conditions and the following disclaimer. 121541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 131541Srgrimes * notice, this list of conditions and the following disclaimer in the 141541Srgrimes * documentation and/or other materials provided with the distribution. 151541Srgrimes * 3. All advertising materials mentioning features or use of this software 161541Srgrimes * must display the following acknowledgement: 171541Srgrimes * This product includes software developed by the University of 181541Srgrimes * California, Berkeley and its contributors. 191541Srgrimes * 4. Neither the name of the University nor the names of its contributors 201541Srgrimes * may be used to endorse or promote products derived from this software 211541Srgrimes * without specific prior written permission. 221541Srgrimes * 231541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 241541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 251541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 261541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 271541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 281541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 291541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 301541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 311541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 321541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 331541Srgrimes * SUCH DAMAGE. 341541Srgrimes * 356928Sphk * @(#)vfs_cache.c 8.3 (Berkeley) 8/22/94 3612968Sphk * $Id: vfs_cache.c,v 1.18 1995/12/14 09:52:47 phk Exp $ 371541Srgrimes */ 381541Srgrimes 391541Srgrimes#include <sys/param.h> 401541Srgrimes#include <sys/systm.h> 4112820Sphk#include <sys/kernel.h> 4212820Sphk#include <sys/sysctl.h> 431541Srgrimes#include <sys/time.h> 441541Srgrimes#include <sys/mount.h> 451541Srgrimes#include <sys/vnode.h> 461541Srgrimes#include <sys/namei.h> 471541Srgrimes#include <sys/errno.h> 481541Srgrimes#include <sys/malloc.h> 491541Srgrimes 501541Srgrimes/* 511541Srgrimes * Name caching works as follows: 521541Srgrimes * 531541Srgrimes * Names found by directory scans are retained in a cache 541541Srgrimes * for future reference. It is managed LRU, so frequently 551541Srgrimes * used names will hang around. Cache is indexed by hash value 561541Srgrimes * obtained from (vp, name) where vp refers to the directory 571541Srgrimes * containing name. 581541Srgrimes * 596968Sphk * If it is a "negative" entry, (that we know a name to >not< exist) 606968Sphk * we point out entry at our own "nchENOENT", to avoid too much special 616968Sphk * casing in the inner loops of lookup. 626968Sphk * 631541Srgrimes * For simplicity (and economy of storage), names longer than 641541Srgrimes * a maximum length of NCHNAMLEN are not cached; they occur 651541Srgrimes * infrequently in any case, and are almost never of interest. 661541Srgrimes * 671541Srgrimes * Upon reaching the last segment of a path, if the reference 681541Srgrimes * is for DELETE, or NOCACHE is set (rewrite), and the 691541Srgrimes * name is located in the cache, it will be dropped. 701541Srgrimes */ 711541Srgrimes 721541Srgrimes/* 731541Srgrimes * Structures associated with name cacheing. 741541Srgrimes */ 7512820Sphkstatic LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */ 7612820Sphkstatic TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */ 7712820Sphkstatic u_long nchash; /* size of hash table */ 789759Sbdestruct nchstats nchstats; /* cache effectiveness statistics */ 7912820Sphkstatic struct vnode nchENOENT; /* our own "novnode" */ 8012820Sphkstatic int doingcache = 1; /* 1 => enable the cache */ 8112820SphkSYSCTL_INT(_debug, OID_AUTO, vfscache, CTLFLAG_RW, &doingcache, 0, ""); 8212820Sphkstatic u_long numcache; 839759Sbdeu_long numvnodes; 841541Srgrimes 856968Sphk#ifdef NCH_STATISTICS 866968Sphku_long nchnbr; 876968Sphk#define NCHNBR(ncp) (ncp)->nc_nbr = ++nchnbr; 886968Sphk#define NCHHIT(ncp) (ncp)->nc_hits++ 896968Sphk#else 906968Sphk#define NCHNBR(ncp) 916968Sphk#define NCHHIT(ncp) 926968Sphk#endif 936968Sphk 946968Sphk#define PURGE(ncp) { \ 956968Sphk LIST_REMOVE(ncp, nc_hash); \ 966968Sphk ncp->nc_hash.le_prev = 0; \ 976968Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 986968Sphk TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); } 996968Sphk 1006968Sphk#define TOUCH(ncp) { \ 1016968Sphk if (ncp->nc_lru.tqe_next == 0) { } else { \ 1026968Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 1036968Sphk TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); \ 1046968Sphk NCHNBR(ncp); } } 1056968Sphk 1061541Srgrimes/* 1078876Srgrimes * Lookup an entry in the cache 1086968Sphk * 1098876Srgrimes * We don't do this if the segment name is long, simply so the cache 1106968Sphk * can avoid holding long names (which would either waste space, or 1111541Srgrimes * add greatly to the complexity). 1121541Srgrimes * 1136968Sphk * Lookup is called with dvp pointing to the directory to search, 1146968Sphk * cnp pointing to the name of the entry being sought. 1158876Srgrimes * If the lookup succeeds, the vnode is returned in *vpp, and a status 1166968Sphk * of -1 is returned. 1176968Sphk * If the lookup determines that the name does not exist (negative cacheing), 1186968Sphk * a status of ENOENT is returned. 1196968Sphk * If the lookup fails, a status of zero is returned. 1201541Srgrimes */ 1216968Sphk 1221541Srgrimesint 1231541Srgrimescache_lookup(dvp, vpp, cnp) 1241541Srgrimes struct vnode *dvp; 1251541Srgrimes struct vnode **vpp; 1261541Srgrimes struct componentname *cnp; 1271541Srgrimes{ 1286928Sphk register struct namecache *ncp,*nnp; 1296928Sphk register struct nchashhead *ncpp; 1301541Srgrimes 1316928Sphk if (!doingcache) { 1326928Sphk cnp->cn_flags &= ~MAKEENTRY; 1331541Srgrimes return (0); 1346928Sphk } 1356968Sphk 1361541Srgrimes if (cnp->cn_namelen > NCHNAMLEN) { 1371541Srgrimes nchstats.ncs_long++; 1381541Srgrimes cnp->cn_flags &= ~MAKEENTRY; 1391541Srgrimes return (0); 1401541Srgrimes } 1416968Sphk 1427611Sdg ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) % nchash]; 1436928Sphk for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) { 1446928Sphk nnp = ncp->nc_hash.le_next; 1456952Sphk /* If one of the vp's went stale, don't bother anymore. */ 1466952Sphk if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) || 1476968Sphk (ncp->nc_vpid != ncp->nc_vp->v_id)) { 1487013Sphk nchstats.ncs_falsehits++; 1496968Sphk PURGE(ncp); 1506968Sphk continue; 1516928Sphk } 1526968Sphk /* Now that we know the vp's to be valid, is it ours ? */ 1536968Sphk if (ncp->nc_dvp == dvp && 1546968Sphk ncp->nc_nlen == cnp->cn_namelen && 1556968Sphk !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 1566968Sphk goto found; /* Fanatism considered bad. */ 1571541Srgrimes } 1586968Sphk nchstats.ncs_miss++; 1596968Sphk return (0); 1606968Sphk 1616968Sphk found: 1626968Sphk NCHHIT(ncp); 1636968Sphk 1646968Sphk /* We don't want to have an entry, so dump it */ 1656928Sphk if ((cnp->cn_flags & MAKEENTRY) == 0) { 1661541Srgrimes nchstats.ncs_badhits++; 1676968Sphk PURGE(ncp); 1686968Sphk return (0); 1698876Srgrimes } 1706968Sphk 1716968Sphk /* We found a "positive" match, return the vnode */ 1726968Sphk if (ncp->nc_vp != &nchENOENT) { 1731541Srgrimes nchstats.ncs_goodhits++; 1746968Sphk TOUCH(ncp); 1751541Srgrimes *vpp = ncp->nc_vp; 1761541Srgrimes return (-1); 1771541Srgrimes } 1781541Srgrimes 1796968Sphk /* We found a negative match, and want to create it, so purge */ 1806968Sphk if (cnp->cn_nameiop == CREATE) { 1817013Sphk nchstats.ncs_badhits++; 1826968Sphk PURGE(ncp); 1836968Sphk return (0); 1846968Sphk } 1856968Sphk 1866968Sphk /* The name does not exists */ 1876968Sphk nchstats.ncs_neghits++; 1886968Sphk TOUCH(ncp); 1896968Sphk return (ENOENT); 1901541Srgrimes} 1911541Srgrimes 1921541Srgrimes/* 1936968Sphk * Add an entry to the cache. 1941541Srgrimes */ 1956968Sphk 1961549Srgrimesvoid 1971541Srgrimescache_enter(dvp, vp, cnp) 1981541Srgrimes struct vnode *dvp; 1991541Srgrimes struct vnode *vp; 2001541Srgrimes struct componentname *cnp; 2011541Srgrimes{ 2026928Sphk register struct namecache *ncp; 2036928Sphk register struct nchashhead *ncpp; 2041541Srgrimes 2051541Srgrimes if (!doingcache) 2061541Srgrimes return; 2076968Sphk 2086968Sphk if (cnp->cn_namelen > NCHNAMLEN) { 2096968Sphk printf("cache_enter: name too long"); 2106968Sphk return; 2116968Sphk } 2126968Sphk 2136990Sdg if (numcache < numvnodes) { 2146968Sphk /* Add one more entry */ 2151541Srgrimes ncp = (struct namecache *) 2161541Srgrimes malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 2171541Srgrimes bzero((char *)ncp, sizeof *ncp); 2181541Srgrimes numcache++; 2196928Sphk } else if (ncp = nclruhead.tqh_first) { 2206968Sphk /* reuse an old entry */ 2216928Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 2226928Sphk if (ncp->nc_hash.le_prev != 0) { 2236928Sphk LIST_REMOVE(ncp, nc_hash); 2246928Sphk ncp->nc_hash.le_prev = 0; 2256928Sphk } 2266968Sphk } else { 2276968Sphk /* give up */ 2283308Sphk return; 2296968Sphk } 2306968Sphk 2316968Sphk /* If vp is NULL this is a "negative" cache entry */ 2326968Sphk if (!vp) 2336968Sphk vp = &nchENOENT; 2346968Sphk 2356968Sphk /* fill in cache info */ 2361541Srgrimes ncp->nc_vp = vp; 2376968Sphk ncp->nc_vpid = vp->v_id; 2381541Srgrimes ncp->nc_dvp = dvp; 2391541Srgrimes ncp->nc_dvpid = dvp->v_id; 2401541Srgrimes ncp->nc_nlen = cnp->cn_namelen; 2411541Srgrimes bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 2426928Sphk TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 2437611Sdg ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) % nchash]; 2446928Sphk LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 2451541Srgrimes} 2461541Srgrimes 2471541Srgrimes/* 2481541Srgrimes * Name cache initialization, from vfs_init() when we are booting 2491541Srgrimes */ 2506968Sphk 2511549Srgrimesvoid 2521541Srgrimesnchinit() 2531541Srgrimes{ 2541541Srgrimes 2556928Sphk TAILQ_INIT(&nclruhead); 2567611Sdg nchashtbl = phashinit(desiredvnodes, M_CACHE, &nchash); 25712968Sphk cache_purge(&nchENOENT); /* Initialize v_id */ 2581541Srgrimes} 2591541Srgrimes 2601541Srgrimes/* 26112968Sphk * Invalidate all entries to a particular vnode. 2628876Srgrimes * 26312968Sphk * We actually just increment the v_id, that will do it. The stale entries 26412968Sphk * will be purged by lookup as they get found. 2656968Sphk * If the v_id wraps around, we need to ditch the entire cache, to avoid 2666968Sphk * confusion. 2676968Sphk * No valid vnode will ever have (v_id == 0). 2681541Srgrimes */ 2696968Sphk 2701549Srgrimesvoid 2711541Srgrimescache_purge(vp) 2721541Srgrimes struct vnode *vp; 2731541Srgrimes{ 2746928Sphk struct nchashhead *ncpp; 27512968Sphk static u_long nextvnodeid; 2761541Srgrimes 2771541Srgrimes vp->v_id = ++nextvnodeid; 2781541Srgrimes if (nextvnodeid != 0) 2791541Srgrimes return; 2807831Sdg for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) { 2816968Sphk while(ncpp->lh_first) 2826968Sphk PURGE(ncpp->lh_first); 2831541Srgrimes } 28412968Sphk nchENOENT.v_id = ++nextvnodeid; 2851541Srgrimes vp->v_id = ++nextvnodeid; 2861541Srgrimes} 2871541Srgrimes 2881541Srgrimes/* 2896968Sphk * Flush all entries referencing a particular filesystem. 2901541Srgrimes * 2916968Sphk * Since we need to check it anyway, we will flush all the invalid 29212968Sphk * entries at the same time. 2936968Sphk * 2946968Sphk * If we purge anything, we scan the hash-bucket again. There is only 2956968Sphk * a handful of entries, so it cheap and simple. 2961541Srgrimes */ 2976968Sphk 2981549Srgrimesvoid 2991541Srgrimescache_purgevfs(mp) 3001541Srgrimes struct mount *mp; 3011541Srgrimes{ 3026968Sphk struct nchashhead *ncpp; 30311921Sphk struct namecache *ncp; 3041541Srgrimes 3056968Sphk /* Scan hash tables for applicable entries */ 3067831Sdg for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) { 3076968Sphk ncp = ncpp->lh_first; 3086968Sphk while(ncp) { 3096968Sphk if (ncp->nc_dvpid != ncp->nc_dvp->v_id || 3106968Sphk ncp->nc_vpid != ncp->nc_vp->v_id || 3116968Sphk ncp->nc_dvp->v_mount == mp) { 3126968Sphk PURGE(ncp); 3136968Sphk ncp = ncpp->lh_first; 3146968Sphk } else { 3157155Sdg ncp = ncp->nc_hash.le_next; 3166968Sphk } 3171541Srgrimes } 3181541Srgrimes } 3191541Srgrimes} 320