vfs_cache.c revision 6952
11541Srgrimes/* 21541Srgrimes * Copyright (c) 1989, 1993 31541Srgrimes * The Regents of the University of California. All rights reserved. 41541Srgrimes * 51541Srgrimes * Redistribution and use in source and binary forms, with or without 61541Srgrimes * modification, are permitted provided that the following conditions 71541Srgrimes * are met: 81541Srgrimes * 1. Redistributions of source code must retain the above copyright 91541Srgrimes * notice, this list of conditions and the following disclaimer. 101541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111541Srgrimes * notice, this list of conditions and the following disclaimer in the 121541Srgrimes * documentation and/or other materials provided with the distribution. 131541Srgrimes * 3. All advertising materials mentioning features or use of this software 141541Srgrimes * must display the following acknowledgement: 151541Srgrimes * This product includes software developed by the University of 161541Srgrimes * California, Berkeley and its contributors. 171541Srgrimes * 4. Neither the name of the University nor the names of its contributors 181541Srgrimes * may be used to endorse or promote products derived from this software 191541Srgrimes * without specific prior written permission. 201541Srgrimes * 211541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 221541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 231541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 241541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 251541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 261541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 271541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 281541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 291541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 301541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 311541Srgrimes * SUCH DAMAGE. 321541Srgrimes * 336928Sphk * @(#)vfs_cache.c 8.3 (Berkeley) 8/22/94 346952Sphk * $Id: vfs_cache.c,v 1.6 1995/03/08 01:08:03 phk Exp $ 351541Srgrimes */ 361541Srgrimes 371541Srgrimes#include <sys/param.h> 381541Srgrimes#include <sys/systm.h> 391541Srgrimes#include <sys/time.h> 401541Srgrimes#include <sys/mount.h> 411541Srgrimes#include <sys/vnode.h> 421541Srgrimes#include <sys/namei.h> 431541Srgrimes#include <sys/errno.h> 441541Srgrimes#include <sys/malloc.h> 451541Srgrimes 461541Srgrimes/* 471541Srgrimes * Name caching works as follows: 481541Srgrimes * 491541Srgrimes * Names found by directory scans are retained in a cache 501541Srgrimes * for future reference. It is managed LRU, so frequently 511541Srgrimes * used names will hang around. Cache is indexed by hash value 521541Srgrimes * obtained from (vp, name) where vp refers to the directory 531541Srgrimes * containing name. 541541Srgrimes * 551541Srgrimes * For simplicity (and economy of storage), names longer than 561541Srgrimes * a maximum length of NCHNAMLEN are not cached; they occur 571541Srgrimes * infrequently in any case, and are almost never of interest. 581541Srgrimes * 591541Srgrimes * Upon reaching the last segment of a path, if the reference 601541Srgrimes * is for DELETE, or NOCACHE is set (rewrite), and the 611541Srgrimes * name is located in the cache, it will be dropped. 621541Srgrimes */ 631541Srgrimes 641541Srgrimes/* 651541Srgrimes * Structures associated with name cacheing. 661541Srgrimes */ 676928SphkLIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */ 681541Srgrimesu_long nchash; /* size of hash table - 1 */ 691541Srgrimeslong numcache; /* number of cache entries allocated */ 706928SphkTAILQ_HEAD(, namecache) nclruhead; /* LRU chain */ 711541Srgrimesstruct nchstats nchstats; /* cache effectiveness statistics */ 721541Srgrimes 731541Srgrimesint doingcache = 1; /* 1 => enable the cache */ 741541Srgrimes 751541Srgrimes/* 761541Srgrimes * Look for a the name in the cache. We don't do this 771541Srgrimes * if the segment name is long, simply so the cache can avoid 781541Srgrimes * holding long names (which would either waste space, or 791541Srgrimes * add greatly to the complexity). 801541Srgrimes * 811541Srgrimes * Lookup is called with ni_dvp pointing to the directory to search, 821541Srgrimes * ni_ptr pointing to the name of the entry being sought, ni_namelen 831541Srgrimes * tells the length of the name, and ni_hash contains a hash of 841541Srgrimes * the name. If the lookup succeeds, the vnode is returned in ni_vp 851541Srgrimes * and a status of -1 is returned. If the lookup determines that 861541Srgrimes * the name does not exist (negative cacheing), a status of ENOENT 871541Srgrimes * is returned. If the lookup fails, a status of zero is returned. 881541Srgrimes */ 891541Srgrimesint 901541Srgrimescache_lookup(dvp, vpp, cnp) 911541Srgrimes struct vnode *dvp; 921541Srgrimes struct vnode **vpp; 931541Srgrimes struct componentname *cnp; 941541Srgrimes{ 956928Sphk register struct namecache *ncp,*nnp; 966928Sphk register struct nchashhead *ncpp; 971541Srgrimes 986928Sphk if (!doingcache) { 996928Sphk cnp->cn_flags &= ~MAKEENTRY; 1001541Srgrimes return (0); 1016928Sphk } 1021541Srgrimes if (cnp->cn_namelen > NCHNAMLEN) { 1031541Srgrimes nchstats.ncs_long++; 1041541Srgrimes cnp->cn_flags &= ~MAKEENTRY; 1051541Srgrimes return (0); 1061541Srgrimes } 1076951Sphk ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) & nchash]; 1086928Sphk for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) { 1091541Srgrimes if (ncp->nc_dvp == dvp && 1101541Srgrimes ncp->nc_dvpid == dvp->v_id && 1111541Srgrimes ncp->nc_nlen == cnp->cn_namelen && 1121541Srgrimes !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 1131541Srgrimes break; 1146928Sphk nnp = ncp->nc_hash.le_next; 1156952Sphk /* If one of the vp's went stale, don't bother anymore. */ 1166952Sphk if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) || 1176952Sphk (ncp->nc_vp && (ncp->nc_vpid != ncp->nc_vp->v_id))) { 1186928Sphk LIST_REMOVE(ncp, nc_hash); 1196928Sphk ncp->nc_hash.le_prev = 0; 1206928Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 1216928Sphk TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); 1226928Sphk } 1231541Srgrimes } 1246928Sphk if (ncp == 0) { 1251541Srgrimes nchstats.ncs_miss++; 1261541Srgrimes return (0); 1271541Srgrimes } 1286928Sphk if ((cnp->cn_flags & MAKEENTRY) == 0) { 1291541Srgrimes nchstats.ncs_badhits++; 1301541Srgrimes } else if (ncp->nc_vp == NULL) { 1311541Srgrimes if (cnp->cn_nameiop != CREATE) { 1321541Srgrimes nchstats.ncs_neghits++; 1331541Srgrimes /* 1341541Srgrimes * Move this slot to end of LRU chain, 1351541Srgrimes * if not already there. 1361541Srgrimes */ 1376928Sphk if (ncp->nc_lru.tqe_next != 0) { 1386928Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 1396928Sphk TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 1401541Srgrimes } 1411541Srgrimes return (ENOENT); 1421541Srgrimes } 1431541Srgrimes } else if (ncp->nc_vpid != ncp->nc_vp->v_id) { 1441541Srgrimes nchstats.ncs_falsehits++; 1451541Srgrimes } else { 1461541Srgrimes nchstats.ncs_goodhits++; 1471541Srgrimes /* 1481541Srgrimes * move this slot to end of LRU chain, if not already there 1491541Srgrimes */ 1506928Sphk if (ncp->nc_lru.tqe_next != 0) { 1516928Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 1526928Sphk TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 1531541Srgrimes } 1541541Srgrimes *vpp = ncp->nc_vp; 1551541Srgrimes return (-1); 1561541Srgrimes } 1571541Srgrimes 1581541Srgrimes /* 1591541Srgrimes * Last component and we are renaming or deleting, 1601541Srgrimes * the cache entry is invalid, or otherwise don't 1611541Srgrimes * want cache entry to exist. 1621541Srgrimes */ 1636928Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 1646928Sphk LIST_REMOVE(ncp, nc_hash); 1656928Sphk ncp->nc_hash.le_prev = 0; 1666928Sphk TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); 1671541Srgrimes return (0); 1681541Srgrimes} 1691541Srgrimes 1701541Srgrimes/* 1711541Srgrimes * Add an entry to the cache 1721541Srgrimes */ 1731549Srgrimesvoid 1741541Srgrimescache_enter(dvp, vp, cnp) 1751541Srgrimes struct vnode *dvp; 1761541Srgrimes struct vnode *vp; 1771541Srgrimes struct componentname *cnp; 1781541Srgrimes{ 1796928Sphk register struct namecache *ncp; 1806928Sphk register struct nchashhead *ncpp; 1811541Srgrimes 1821541Srgrimes#ifdef DIAGNOSTIC 1831541Srgrimes if (cnp->cn_namelen > NCHNAMLEN) 1841541Srgrimes panic("cache_enter: name too long"); 1851541Srgrimes#endif 1861541Srgrimes if (!doingcache) 1871541Srgrimes return; 1881541Srgrimes /* 1891541Srgrimes * Free the cache slot at head of lru chain. 1901541Srgrimes */ 1911541Srgrimes if (numcache < desiredvnodes) { 1921541Srgrimes ncp = (struct namecache *) 1931541Srgrimes malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 1941541Srgrimes bzero((char *)ncp, sizeof *ncp); 1951541Srgrimes numcache++; 1966928Sphk } else if (ncp = nclruhead.tqh_first) { 1976928Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 1986928Sphk if (ncp->nc_hash.le_prev != 0) { 1996928Sphk LIST_REMOVE(ncp, nc_hash); 2006928Sphk ncp->nc_hash.le_prev = 0; 2016928Sphk } 2026928Sphk } else 2033308Sphk return; 2041541Srgrimes /* grab the vnode we just found */ 2051541Srgrimes ncp->nc_vp = vp; 2061541Srgrimes if (vp) 2071541Srgrimes ncp->nc_vpid = vp->v_id; 2081541Srgrimes else 2091541Srgrimes ncp->nc_vpid = 0; 2101541Srgrimes /* fill in cache info */ 2111541Srgrimes ncp->nc_dvp = dvp; 2121541Srgrimes ncp->nc_dvpid = dvp->v_id; 2131541Srgrimes ncp->nc_nlen = cnp->cn_namelen; 2141541Srgrimes bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 2156928Sphk TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 2166951Sphk ncpp = &nchashtbl[(dvp->v_id + cnp->cn_hash) & nchash]; 2176928Sphk LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 2181541Srgrimes} 2191541Srgrimes 2201541Srgrimes/* 2211541Srgrimes * Name cache initialization, from vfs_init() when we are booting 2221541Srgrimes */ 2231549Srgrimesvoid 2241541Srgrimesnchinit() 2251541Srgrimes{ 2261541Srgrimes 2276928Sphk TAILQ_INIT(&nclruhead); 2281541Srgrimes nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash); 2291541Srgrimes} 2301541Srgrimes 2311541Srgrimes/* 2321541Srgrimes * Cache flush, a particular vnode; called when a vnode is renamed to 2331541Srgrimes * hide entries that would now be invalid 2341541Srgrimes */ 2351549Srgrimesvoid 2361541Srgrimescache_purge(vp) 2371541Srgrimes struct vnode *vp; 2381541Srgrimes{ 2396928Sphk struct namecache *ncp; 2406928Sphk struct nchashhead *ncpp; 2411541Srgrimes 2421541Srgrimes vp->v_id = ++nextvnodeid; 2431541Srgrimes if (nextvnodeid != 0) 2441541Srgrimes return; 2451541Srgrimes for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 2466928Sphk for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) { 2471541Srgrimes ncp->nc_vpid = 0; 2481541Srgrimes ncp->nc_dvpid = 0; 2491541Srgrimes } 2501541Srgrimes } 2511541Srgrimes vp->v_id = ++nextvnodeid; 2521541Srgrimes} 2531541Srgrimes 2541541Srgrimes/* 2551541Srgrimes * Cache flush, a whole filesystem; called when filesys is umounted to 2561541Srgrimes * remove entries that would now be invalid 2571541Srgrimes * 2581541Srgrimes * The line "nxtcp = nchhead" near the end is to avoid potential problems 2591541Srgrimes * if the cache lru chain is modified while we are dumping the 2601541Srgrimes * inode. This makes the algorithm O(n^2), but do you think I care? 2611541Srgrimes */ 2621549Srgrimesvoid 2631541Srgrimescache_purgevfs(mp) 2641541Srgrimes struct mount *mp; 2651541Srgrimes{ 2661541Srgrimes register struct namecache *ncp, *nxtcp; 2671541Srgrimes 2686928Sphk for (ncp = nclruhead.tqh_first; ncp != 0; ncp = nxtcp) { 2691541Srgrimes if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) { 2706928Sphk nxtcp = ncp->nc_lru.tqe_next; 2711541Srgrimes continue; 2721541Srgrimes } 2731541Srgrimes /* free the resources we had */ 2741541Srgrimes ncp->nc_vp = NULL; 2751541Srgrimes ncp->nc_dvp = NULL; 2766928Sphk TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 2776928Sphk if (ncp->nc_hash.le_prev != 0) { 2786928Sphk LIST_REMOVE(ncp, nc_hash); 2796928Sphk ncp->nc_hash.le_prev = 0; 2801541Srgrimes } 2811541Srgrimes /* cause rescan of list, it may have altered */ 2826928Sphk nxtcp = nclruhead.tqh_first; 2836928Sphk TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); 2841541Srgrimes } 2851541Srgrimes} 286