vfs_cache.c revision 9759
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 369759Sbde * $Id: vfs_cache.c,v 1.15 1995/05/30 08:06:28 rgrimes Exp $ 371541Srgrimes */ 381541Srgrimes 391541Srgrimes#include <sys/param.h> 401541Srgrimes#include <sys/systm.h> 411541Srgrimes#include <sys/time.h> 421541Srgrimes#include <sys/mount.h> 431541Srgrimes#include <sys/vnode.h> 441541Srgrimes#include <sys/namei.h> 451541Srgrimes#include <sys/errno.h> 461541Srgrimes#include <sys/malloc.h> 471541Srgrimes 481541Srgrimes/* 491541Srgrimes * Name caching works as follows: 501541Srgrimes * 511541Srgrimes * Names found by directory scans are retained in a cache 521541Srgrimes * for future reference. It is managed LRU, so frequently 531541Srgrimes * used names will hang around. Cache is indexed by hash value 541541Srgrimes * obtained from (vp, name) where vp refers to the directory 551541Srgrimes * containing name. 561541Srgrimes * 576968Sphk * If it is a "negative" entry, (that we know a name to >not< exist) 586968Sphk * we point out entry at our own "nchENOENT", to avoid too much special 596968Sphk * casing in the inner loops of lookup. 606968Sphk * 611541Srgrimes * For simplicity (and economy of storage), names longer than 621541Srgrimes * a maximum length of NCHNAMLEN are not cached; they occur 631541Srgrimes * infrequently in any case, and are almost never of interest. 641541Srgrimes * 651541Srgrimes * Upon reaching the last segment of a path, if the reference 661541Srgrimes * is for DELETE, or NOCACHE is set (rewrite), and the 671541Srgrimes * name is located in the cache, it will be dropped. 681541Srgrimes */ 691541Srgrimes 701541Srgrimes/* 711541Srgrimes * Structures associated with name cacheing. 721541Srgrimes */ 736928SphkLIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */ 746968SphkTAILQ_HEAD(, namecache) nclruhead; /* LRU chain */ 757611Sdgu_long nchash; /* size of hash table */ 769759Sbdestruct nchstats nchstats; /* cache effectiveness statistics */ 779759Sbdestruct vnode nchENOENT; /* our own "novnode" */ 781541Srgrimesint doingcache = 1; /* 1 => enable the cache */ 799759Sbdeu_long nextvnodeid; 809759Sbdeu_long numcache; 819759Sbdeu_long numvnodes; 821541Srgrimes 836968Sphk#ifdef NCH_STATISTICS 846968Sphku_long nchnbr; 856968Sphk#define NCHNBR(ncp) (ncp)->nc_nbr = ++nchnbr; 866968Sphk#define NCHHIT(ncp) (ncp)->nc_hits++ 876968Sphk#else 886968Sphk#define NCHNBR(ncp) 896968Sphk#define NCHHIT(ncp) 906968Sphk#endif 916968Sphk 926968Sphk#define PURGE(ncp) { \ 936968Sphk LIST_REMOVE(ncp, nc_hash); \ 946968Sphk ncp->nc_hash.le_prev = 0; \ 956968Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 966968Sphk TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); } 976968Sphk 986968Sphk#define TOUCH(ncp) { \ 996968Sphk if (ncp->nc_lru.tqe_next == 0) { } else { \ 1006968Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 1016968Sphk TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); \ 1026968Sphk NCHNBR(ncp); } } 1036968Sphk 1041541Srgrimes/* 1058876Srgrimes * Lookup an entry in the cache 1066968Sphk * 1078876Srgrimes * We don't do this if the segment name is long, simply so the cache 1086968Sphk * can avoid holding long names (which would either waste space, or 1091541Srgrimes * add greatly to the complexity). 1101541Srgrimes * 1116968Sphk * Lookup is called with dvp pointing to the directory to search, 1126968Sphk * cnp pointing to the name of the entry being sought. 1138876Srgrimes * If the lookup succeeds, the vnode is returned in *vpp, and a status 1146968Sphk * of -1 is returned. 1156968Sphk * If the lookup determines that the name does not exist (negative cacheing), 1166968Sphk * a status of ENOENT is returned. 1176968Sphk * If the lookup fails, a status of zero is returned. 1181541Srgrimes */ 1196968Sphk 1201541Srgrimesint 1211541Srgrimescache_lookup(dvp, vpp, cnp) 1221541Srgrimes struct vnode *dvp; 1231541Srgrimes struct vnode **vpp; 1241541Srgrimes struct componentname *cnp; 1251541Srgrimes{ 1266928Sphk register struct namecache *ncp,*nnp; 1276928Sphk register struct nchashhead *ncpp; 1281541Srgrimes 1296928Sphk if (!doingcache) { 1306928Sphk cnp->cn_flags &= ~MAKEENTRY; 1311541Srgrimes return (0); 1326928Sphk } 1336968Sphk 1341541Srgrimes if (cnp->cn_namelen > NCHNAMLEN) { 1351541Srgrimes nchstats.ncs_long++; 1361541Srgrimes cnp->cn_flags &= ~MAKEENTRY; 1371541Srgrimes return (0); 1381541Srgrimes } 1396968Sphk 1407611Sdg ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) % nchash]; 1416928Sphk for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) { 1426928Sphk nnp = ncp->nc_hash.le_next; 1436952Sphk /* If one of the vp's went stale, don't bother anymore. */ 1446952Sphk if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) || 1456968Sphk (ncp->nc_vpid != ncp->nc_vp->v_id)) { 1467013Sphk nchstats.ncs_falsehits++; 1476968Sphk PURGE(ncp); 1486968Sphk continue; 1496928Sphk } 1506968Sphk /* Now that we know the vp's to be valid, is it ours ? */ 1516968Sphk if (ncp->nc_dvp == dvp && 1526968Sphk ncp->nc_nlen == cnp->cn_namelen && 1536968Sphk !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 1546968Sphk goto found; /* Fanatism considered bad. */ 1551541Srgrimes } 1566968Sphk nchstats.ncs_miss++; 1576968Sphk return (0); 1586968Sphk 1596968Sphk found: 1606968Sphk NCHHIT(ncp); 1616968Sphk 1626968Sphk /* We don't want to have an entry, so dump it */ 1636928Sphk if ((cnp->cn_flags & MAKEENTRY) == 0) { 1641541Srgrimes nchstats.ncs_badhits++; 1656968Sphk PURGE(ncp); 1666968Sphk return (0); 1678876Srgrimes } 1686968Sphk 1696968Sphk /* We found a "positive" match, return the vnode */ 1706968Sphk if (ncp->nc_vp != &nchENOENT) { 1711541Srgrimes nchstats.ncs_goodhits++; 1726968Sphk TOUCH(ncp); 1731541Srgrimes *vpp = ncp->nc_vp; 1741541Srgrimes return (-1); 1751541Srgrimes } 1761541Srgrimes 1776968Sphk /* We found a negative match, and want to create it, so purge */ 1786968Sphk if (cnp->cn_nameiop == CREATE) { 1797013Sphk nchstats.ncs_badhits++; 1806968Sphk PURGE(ncp); 1816968Sphk return (0); 1826968Sphk } 1836968Sphk 1846968Sphk /* The name does not exists */ 1856968Sphk nchstats.ncs_neghits++; 1866968Sphk TOUCH(ncp); 1876968Sphk return (ENOENT); 1881541Srgrimes} 1891541Srgrimes 1901541Srgrimes/* 1916968Sphk * Add an entry to the cache. 1921541Srgrimes */ 1936968Sphk 1941549Srgrimesvoid 1951541Srgrimescache_enter(dvp, vp, cnp) 1961541Srgrimes struct vnode *dvp; 1971541Srgrimes struct vnode *vp; 1981541Srgrimes struct componentname *cnp; 1991541Srgrimes{ 2006928Sphk register struct namecache *ncp; 2016928Sphk register struct nchashhead *ncpp; 2021541Srgrimes 2031541Srgrimes if (!doingcache) 2041541Srgrimes return; 2056968Sphk 2066968Sphk if (cnp->cn_namelen > NCHNAMLEN) { 2076968Sphk printf("cache_enter: name too long"); 2086968Sphk return; 2096968Sphk } 2106968Sphk 2116990Sdg if (numcache < numvnodes) { 2126968Sphk /* Add one more entry */ 2131541Srgrimes ncp = (struct namecache *) 2141541Srgrimes malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 2151541Srgrimes bzero((char *)ncp, sizeof *ncp); 2161541Srgrimes numcache++; 2176928Sphk } else if (ncp = nclruhead.tqh_first) { 2186968Sphk /* reuse an old entry */ 2196928Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 2206928Sphk if (ncp->nc_hash.le_prev != 0) { 2216928Sphk LIST_REMOVE(ncp, nc_hash); 2226928Sphk ncp->nc_hash.le_prev = 0; 2236928Sphk } 2246968Sphk } else { 2256968Sphk /* give up */ 2263308Sphk return; 2276968Sphk } 2286968Sphk 2296968Sphk /* If vp is NULL this is a "negative" cache entry */ 2306968Sphk if (!vp) 2316968Sphk vp = &nchENOENT; 2326968Sphk 2336968Sphk /* fill in cache info */ 2341541Srgrimes ncp->nc_vp = vp; 2356968Sphk ncp->nc_vpid = vp->v_id; 2361541Srgrimes ncp->nc_dvp = dvp; 2371541Srgrimes ncp->nc_dvpid = dvp->v_id; 2381541Srgrimes ncp->nc_nlen = cnp->cn_namelen; 2391541Srgrimes bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 2406928Sphk TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 2417611Sdg ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) % nchash]; 2426928Sphk LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 2431541Srgrimes} 2441541Srgrimes 2451541Srgrimes/* 2461541Srgrimes * Name cache initialization, from vfs_init() when we are booting 2471541Srgrimes */ 2486968Sphk 2491549Srgrimesvoid 2501541Srgrimesnchinit() 2511541Srgrimes{ 2521541Srgrimes 2536928Sphk TAILQ_INIT(&nclruhead); 2547611Sdg nchashtbl = phashinit(desiredvnodes, M_CACHE, &nchash); 2556968Sphk nchENOENT.v_id = 1; 2561541Srgrimes} 2571541Srgrimes 2581541Srgrimes/* 2596968Sphk * Invalidate a all entries to particular vnode. 2608876Srgrimes * 2616968Sphk * We actually just increment the v_id, that will do it. The entries will 2626968Sphk * be purged by lookup as they get found. 2636968Sphk * If the v_id wraps around, we need to ditch the entire cache, to avoid 2646968Sphk * confusion. 2656968Sphk * No valid vnode will ever have (v_id == 0). 2661541Srgrimes */ 2676968Sphk 2681549Srgrimesvoid 2691541Srgrimescache_purge(vp) 2701541Srgrimes struct vnode *vp; 2711541Srgrimes{ 2726928Sphk struct nchashhead *ncpp; 2731541Srgrimes 2741541Srgrimes vp->v_id = ++nextvnodeid; 2751541Srgrimes if (nextvnodeid != 0) 2761541Srgrimes return; 2777831Sdg for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) { 2786968Sphk while(ncpp->lh_first) 2796968Sphk PURGE(ncpp->lh_first); 2801541Srgrimes } 2811541Srgrimes vp->v_id = ++nextvnodeid; 2821541Srgrimes} 2831541Srgrimes 2841541Srgrimes/* 2856968Sphk * Flush all entries referencing a particular filesystem. 2861541Srgrimes * 2876968Sphk * Since we need to check it anyway, we will flush all the invalid 2886968Sphk * entriess at the same time. 2896968Sphk * 2906968Sphk * If we purge anything, we scan the hash-bucket again. There is only 2916968Sphk * a handful of entries, so it cheap and simple. 2921541Srgrimes */ 2936968Sphk 2941549Srgrimesvoid 2951541Srgrimescache_purgevfs(mp) 2961541Srgrimes struct mount *mp; 2971541Srgrimes{ 2986968Sphk struct nchashhead *ncpp; 2996968Sphk struct namecache *ncp, *nxtcp; 3001541Srgrimes 3016968Sphk /* Scan hash tables for applicable entries */ 3027831Sdg for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) { 3036968Sphk ncp = ncpp->lh_first; 3046968Sphk while(ncp) { 3056968Sphk if (ncp->nc_dvpid != ncp->nc_dvp->v_id || 3066968Sphk ncp->nc_vpid != ncp->nc_vp->v_id || 3076968Sphk ncp->nc_dvp->v_mount == mp) { 3086968Sphk PURGE(ncp); 3096968Sphk ncp = ncpp->lh_first; 3106968Sphk } else { 3117155Sdg ncp = ncp->nc_hash.le_next; 3126968Sphk } 3131541Srgrimes } 3141541Srgrimes } 3151541Srgrimes} 316