vfs_cache.c revision 6968
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 366968Sphk * $Id: vfs_cache.c,v 1.7 1995/03/08 01:40:44 phk 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 */ 751541Srgrimesu_long nchash; /* size of hash table - 1 */ 761541Srgrimesstruct nchstats nchstats; /* cache effectiveness statistics */ 776968Sphkstruct vnode nchENOENT; /* our own "novnode" */ 781541Srgrimesint doingcache = 1; /* 1 => enable the cache */ 791541Srgrimes 806968Sphk#ifdef NCH_STATISTICS 816968Sphku_long nchnbr; 826968Sphk#define NCHNBR(ncp) (ncp)->nc_nbr = ++nchnbr; 836968Sphk#define NCHHIT(ncp) (ncp)->nc_hits++ 846968Sphk#else 856968Sphk#define NCHNBR(ncp) 866968Sphk#define NCHHIT(ncp) 876968Sphk#endif 886968Sphk 896968Sphk#define PURGE(ncp) { \ 906968Sphk LIST_REMOVE(ncp, nc_hash); \ 916968Sphk ncp->nc_hash.le_prev = 0; \ 926968Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 936968Sphk TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); } 946968Sphk 956968Sphk#define TOUCH(ncp) { \ 966968Sphk if (ncp->nc_lru.tqe_next == 0) { } else { \ 976968Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 986968Sphk TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); \ 996968Sphk NCHNBR(ncp); } } 1006968Sphk 1011541Srgrimes/* 1026968Sphk * Lookup an entry in the cache 1036968Sphk * 1046968Sphk * We don't do this if the segment name is long, simply so the cache 1056968Sphk * can avoid holding long names (which would either waste space, or 1061541Srgrimes * add greatly to the complexity). 1071541Srgrimes * 1086968Sphk * Lookup is called with dvp pointing to the directory to search, 1096968Sphk * cnp pointing to the name of the entry being sought. 1106968Sphk * If the lookup succeeds, the vnode is returned in *vpp, and a status 1116968Sphk * of -1 is returned. 1126968Sphk * If the lookup determines that the name does not exist (negative cacheing), 1136968Sphk * a status of ENOENT is returned. 1146968Sphk * If the lookup fails, a status of zero is returned. 1151541Srgrimes */ 1166968Sphk 1171541Srgrimesint 1181541Srgrimescache_lookup(dvp, vpp, cnp) 1191541Srgrimes struct vnode *dvp; 1201541Srgrimes struct vnode **vpp; 1211541Srgrimes struct componentname *cnp; 1221541Srgrimes{ 1236928Sphk register struct namecache *ncp,*nnp; 1246928Sphk register struct nchashhead *ncpp; 1251541Srgrimes 1266928Sphk if (!doingcache) { 1276928Sphk cnp->cn_flags &= ~MAKEENTRY; 1281541Srgrimes return (0); 1296928Sphk } 1306968Sphk 1311541Srgrimes if (cnp->cn_namelen > NCHNAMLEN) { 1321541Srgrimes nchstats.ncs_long++; 1331541Srgrimes cnp->cn_flags &= ~MAKEENTRY; 1341541Srgrimes return (0); 1351541Srgrimes } 1366968Sphk 1376951Sphk ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) & nchash]; 1386928Sphk for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) { 1396928Sphk nnp = ncp->nc_hash.le_next; 1406952Sphk /* If one of the vp's went stale, don't bother anymore. */ 1416952Sphk if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) || 1426968Sphk (ncp->nc_vpid != ncp->nc_vp->v_id)) { 1436968Sphk PURGE(ncp); 1446968Sphk continue; 1456928Sphk } 1466968Sphk /* Now that we know the vp's to be valid, is it ours ? */ 1476968Sphk if (ncp->nc_dvp == dvp && 1486968Sphk ncp->nc_nlen == cnp->cn_namelen && 1496968Sphk !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 1506968Sphk goto found; /* Fanatism considered bad. */ 1511541Srgrimes } 1526968Sphk nchstats.ncs_miss++; 1536968Sphk return (0); 1546968Sphk 1556968Sphk found: 1566968Sphk NCHHIT(ncp); 1576968Sphk 1586968Sphk /* We don't want to have an entry, so dump it */ 1596928Sphk if ((cnp->cn_flags & MAKEENTRY) == 0) { 1601541Srgrimes nchstats.ncs_badhits++; 1616968Sphk PURGE(ncp); 1626968Sphk return (0); 1636968Sphk } 1646968Sphk 1656968Sphk /* We found a "positive" match, return the vnode */ 1666968Sphk if (ncp->nc_vp != &nchENOENT) { 1671541Srgrimes nchstats.ncs_goodhits++; 1686968Sphk TOUCH(ncp); 1691541Srgrimes *vpp = ncp->nc_vp; 1701541Srgrimes return (-1); 1711541Srgrimes } 1721541Srgrimes 1736968Sphk /* We found a negative match, and want to create it, so purge */ 1746968Sphk if (cnp->cn_nameiop == CREATE) { 1756968Sphk PURGE(ncp); 1766968Sphk return (0); 1776968Sphk } 1786968Sphk 1796968Sphk /* The name does not exists */ 1806968Sphk nchstats.ncs_neghits++; 1816968Sphk TOUCH(ncp); 1826968Sphk return (ENOENT); 1831541Srgrimes} 1841541Srgrimes 1851541Srgrimes/* 1866968Sphk * Add an entry to the cache. 1871541Srgrimes */ 1886968Sphk 1891549Srgrimesvoid 1901541Srgrimescache_enter(dvp, vp, cnp) 1911541Srgrimes struct vnode *dvp; 1921541Srgrimes struct vnode *vp; 1931541Srgrimes struct componentname *cnp; 1941541Srgrimes{ 1956928Sphk register struct namecache *ncp; 1966928Sphk register struct nchashhead *ncpp; 1971541Srgrimes 1981541Srgrimes if (!doingcache) 1991541Srgrimes return; 2006968Sphk 2016968Sphk if (cnp->cn_namelen > NCHNAMLEN) { 2026968Sphk printf("cache_enter: name too long"); 2036968Sphk return; 2046968Sphk } 2056968Sphk 2066968Sphk if (numcache < numvnodes) { 2076968Sphk /* Add one more entry */ 2081541Srgrimes ncp = (struct namecache *) 2091541Srgrimes malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 2101541Srgrimes bzero((char *)ncp, sizeof *ncp); 2111541Srgrimes numcache++; 2126928Sphk } else if (ncp = nclruhead.tqh_first) { 2136968Sphk /* reuse an old entry */ 2146928Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 2156928Sphk if (ncp->nc_hash.le_prev != 0) { 2166928Sphk LIST_REMOVE(ncp, nc_hash); 2176928Sphk ncp->nc_hash.le_prev = 0; 2186928Sphk } 2196968Sphk } else { 2206968Sphk /* give up */ 2213308Sphk return; 2226968Sphk } 2236968Sphk 2246968Sphk /* If vp is NULL this is a "negative" cache entry */ 2256968Sphk if (!vp) 2266968Sphk vp = &nchENOENT; 2276968Sphk 2286968Sphk /* fill in cache info */ 2291541Srgrimes ncp->nc_vp = vp; 2306968Sphk ncp->nc_vpid = vp->v_id; 2311541Srgrimes ncp->nc_dvp = dvp; 2321541Srgrimes ncp->nc_dvpid = dvp->v_id; 2331541Srgrimes ncp->nc_nlen = cnp->cn_namelen; 2341541Srgrimes bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 2356928Sphk TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 2366951Sphk ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) & nchash]; 2376928Sphk LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 2381541Srgrimes} 2391541Srgrimes 2401541Srgrimes/* 2411541Srgrimes * Name cache initialization, from vfs_init() when we are booting 2421541Srgrimes */ 2436968Sphk 2441549Srgrimesvoid 2451541Srgrimesnchinit() 2461541Srgrimes{ 2471541Srgrimes 2486928Sphk TAILQ_INIT(&nclruhead); 2491541Srgrimes nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash); 2506968Sphk nchENOENT.v_id = 1; 2511541Srgrimes} 2521541Srgrimes 2531541Srgrimes/* 2546968Sphk * Invalidate a all entries to particular vnode. 2556968Sphk * 2566968Sphk * We actually just increment the v_id, that will do it. The entries will 2576968Sphk * be purged by lookup as they get found. 2586968Sphk * If the v_id wraps around, we need to ditch the entire cache, to avoid 2596968Sphk * confusion. 2606968Sphk * No valid vnode will ever have (v_id == 0). 2611541Srgrimes */ 2626968Sphk 2631549Srgrimesvoid 2641541Srgrimescache_purge(vp) 2651541Srgrimes struct vnode *vp; 2661541Srgrimes{ 2676928Sphk struct nchashhead *ncpp; 2681541Srgrimes 2691541Srgrimes vp->v_id = ++nextvnodeid; 2701541Srgrimes if (nextvnodeid != 0) 2711541Srgrimes return; 2721541Srgrimes for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 2736968Sphk while(ncpp->lh_first) 2746968Sphk PURGE(ncpp->lh_first); 2751541Srgrimes } 2761541Srgrimes vp->v_id = ++nextvnodeid; 2771541Srgrimes} 2781541Srgrimes 2791541Srgrimes/* 2806968Sphk * Flush all entries referencing a particular filesystem. 2811541Srgrimes * 2826968Sphk * Since we need to check it anyway, we will flush all the invalid 2836968Sphk * entriess at the same time. 2846968Sphk * 2856968Sphk * If we purge anything, we scan the hash-bucket again. There is only 2866968Sphk * a handful of entries, so it cheap and simple. 2871541Srgrimes */ 2886968Sphk 2891549Srgrimesvoid 2901541Srgrimescache_purgevfs(mp) 2911541Srgrimes struct mount *mp; 2921541Srgrimes{ 2936968Sphk struct nchashhead *ncpp; 2946968Sphk struct namecache *ncp, *nxtcp; 2951541Srgrimes 2966968Sphk /* Scan hash tables for applicable entries */ 2976968Sphk for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 2986968Sphk ncp = ncpp->lh_first; 2996968Sphk while(ncp) { 3006968Sphk if (ncp->nc_dvpid != ncp->nc_dvp->v_id || 3016968Sphk ncp->nc_vpid != ncp->nc_vp->v_id || 3026968Sphk ncp->nc_dvp->v_mount == mp) { 3036968Sphk PURGE(ncp); 3046968Sphk ncp = ncpp->lh_first; 3056968Sphk } else { 3066968Sphk ncp = ncp->nc_lru.tqe_next; 3076968Sphk } 3081541Srgrimes } 3091541Srgrimes } 3101541Srgrimes} 311