vfs_cache.c revision 6928
1/* 2 * Copyright (c) 1989, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the University of 16 * California, Berkeley and its contributors. 17 * 4. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 * 33 * @(#)vfs_cache.c 8.3 (Berkeley) 8/22/94 34 * $Id$ 35 */ 36 37#include <sys/param.h> 38#include <sys/systm.h> 39#include <sys/time.h> 40#include <sys/mount.h> 41#include <sys/vnode.h> 42#include <sys/namei.h> 43#include <sys/errno.h> 44#include <sys/malloc.h> 45 46/* 47 * Name caching works as follows: 48 * 49 * Names found by directory scans are retained in a cache 50 * for future reference. It is managed LRU, so frequently 51 * used names will hang around. Cache is indexed by hash value 52 * obtained from (vp, name) where vp refers to the directory 53 * containing name. 54 * 55 * For simplicity (and economy of storage), names longer than 56 * a maximum length of NCHNAMLEN are not cached; they occur 57 * infrequently in any case, and are almost never of interest. 58 * 59 * Upon reaching the last segment of a path, if the reference 60 * is for DELETE, or NOCACHE is set (rewrite), and the 61 * name is located in the cache, it will be dropped. 62 */ 63 64/* 65 * Structures associated with name cacheing. 66 */ 67LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */ 68u_long nchash; /* size of hash table - 1 */ 69long numcache; /* number of cache entries allocated */ 70TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */ 71struct nchstats nchstats; /* cache effectiveness statistics */ 72 73int doingcache = 1; /* 1 => enable the cache */ 74 75/* 76 * Look for a the name in the cache. We don't do this 77 * if the segment name is long, simply so the cache can avoid 78 * holding long names (which would either waste space, or 79 * add greatly to the complexity). 80 * 81 * Lookup is called with ni_dvp pointing to the directory to search, 82 * ni_ptr pointing to the name of the entry being sought, ni_namelen 83 * tells the length of the name, and ni_hash contains a hash of 84 * the name. If the lookup succeeds, the vnode is returned in ni_vp 85 * and a status of -1 is returned. If the lookup determines that 86 * the name does not exist (negative cacheing), a status of ENOENT 87 * is returned. If the lookup fails, a status of zero is returned. 88 */ 89int 90cache_lookup(dvp, vpp, cnp) 91 struct vnode *dvp; 92 struct vnode **vpp; 93 struct componentname *cnp; 94{ 95 register struct namecache *ncp,*nnp; 96 register struct nchashhead *ncpp; 97 98 if (!doingcache) { 99 cnp->cn_flags &= ~MAKEENTRY; 100 return (0); 101 } 102 if (cnp->cn_namelen > NCHNAMLEN) { 103 nchstats.ncs_long++; 104 cnp->cn_flags &= ~MAKEENTRY; 105 return (0); 106 } 107 ncpp = &nchashtbl[cnp->cn_hash & nchash]; 108 for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) { 109 if (ncp->nc_dvp == dvp && 110 ncp->nc_dvpid == dvp->v_id && 111 ncp->nc_nlen == cnp->cn_namelen && 112 !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 113 break; 114 nnp = ncp->nc_hash.le_next; 115#ifdef not_yet_phk 116 /* 117 * if not already last and one of the vp's are invalid, 118 * move to head of LRU 119 */ 120 if ((ncp->nc_lru.tqe_next != 0) && 121 ( (ncp->nc_dvpid != ncp->nc_dvp->v_id) || 122 (ncp->nc_vp && (ncp->nc_vpid != ncp->nc_vp->v_id)))) { 123 LIST_REMOVE(ncp, nc_hash); 124 ncp->nc_hash.le_prev = 0; 125 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 126 TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); 127 } 128#endif /* not_yet_phk */ 129 } 130 if (ncp == 0) { 131 nchstats.ncs_miss++; 132 return (0); 133 } 134 if ((cnp->cn_flags & MAKEENTRY) == 0) { 135 nchstats.ncs_badhits++; 136 } else if (ncp->nc_vp == NULL) { 137 if (cnp->cn_nameiop != CREATE) { 138 nchstats.ncs_neghits++; 139 /* 140 * Move this slot to end of LRU chain, 141 * if not already there. 142 */ 143 if (ncp->nc_lru.tqe_next != 0) { 144 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 145 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 146 } 147 return (ENOENT); 148 } 149 } else if (ncp->nc_vpid != ncp->nc_vp->v_id) { 150 nchstats.ncs_falsehits++; 151 } else { 152 nchstats.ncs_goodhits++; 153 /* 154 * move this slot to end of LRU chain, if not already there 155 */ 156 if (ncp->nc_lru.tqe_next != 0) { 157 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 158 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 159 } 160#ifdef not_yet_phk 161 /* Touch the parent vnode */ 162 vtouch(ncp->nc_dvp); 163#endif /* not_yet_phk */ 164 *vpp = ncp->nc_vp; 165 return (-1); 166 } 167 168 /* 169 * Last component and we are renaming or deleting, 170 * the cache entry is invalid, or otherwise don't 171 * want cache entry to exist. 172 */ 173 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 174 LIST_REMOVE(ncp, nc_hash); 175 ncp->nc_hash.le_prev = 0; 176 TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); 177 return (0); 178} 179 180/* 181 * Add an entry to the cache 182 */ 183void 184cache_enter(dvp, vp, cnp) 185 struct vnode *dvp; 186 struct vnode *vp; 187 struct componentname *cnp; 188{ 189 register struct namecache *ncp; 190 register struct nchashhead *ncpp; 191 192#ifdef DIAGNOSTIC 193 if (cnp->cn_namelen > NCHNAMLEN) 194 panic("cache_enter: name too long"); 195#endif 196 if (!doingcache) 197 return; 198 /* 199 * Free the cache slot at head of lru chain. 200 */ 201 if (numcache < desiredvnodes) { 202 ncp = (struct namecache *) 203 malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 204 bzero((char *)ncp, sizeof *ncp); 205 numcache++; 206 } else if (ncp = nclruhead.tqh_first) { 207 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 208 if (ncp->nc_hash.le_prev != 0) { 209 LIST_REMOVE(ncp, nc_hash); 210 ncp->nc_hash.le_prev = 0; 211 } 212 } else 213 return; 214 /* grab the vnode we just found */ 215 ncp->nc_vp = vp; 216 if (vp) 217 ncp->nc_vpid = vp->v_id; 218 else 219 ncp->nc_vpid = 0; 220 /* fill in cache info */ 221 ncp->nc_dvp = dvp; 222 ncp->nc_dvpid = dvp->v_id; 223 ncp->nc_nlen = cnp->cn_namelen; 224 bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 225 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 226 ncpp = &nchashtbl[cnp->cn_hash & nchash]; 227 LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 228} 229 230/* 231 * Name cache initialization, from vfs_init() when we are booting 232 */ 233void 234nchinit() 235{ 236 237 TAILQ_INIT(&nclruhead); 238 nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash); 239} 240 241/* 242 * Cache flush, a particular vnode; called when a vnode is renamed to 243 * hide entries that would now be invalid 244 */ 245void 246cache_purge(vp) 247 struct vnode *vp; 248{ 249 struct namecache *ncp; 250 struct nchashhead *ncpp; 251 252 vp->v_id = ++nextvnodeid; 253 if (nextvnodeid != 0) 254 return; 255 for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 256 for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) { 257 ncp->nc_vpid = 0; 258 ncp->nc_dvpid = 0; 259 } 260 } 261 vp->v_id = ++nextvnodeid; 262} 263 264/* 265 * Cache flush, a whole filesystem; called when filesys is umounted to 266 * remove entries that would now be invalid 267 * 268 * The line "nxtcp = nchhead" near the end is to avoid potential problems 269 * if the cache lru chain is modified while we are dumping the 270 * inode. This makes the algorithm O(n^2), but do you think I care? 271 */ 272void 273cache_purgevfs(mp) 274 struct mount *mp; 275{ 276 register struct namecache *ncp, *nxtcp; 277 278 for (ncp = nclruhead.tqh_first; ncp != 0; ncp = nxtcp) { 279 if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) { 280 nxtcp = ncp->nc_lru.tqe_next; 281 continue; 282 } 283 /* free the resources we had */ 284 ncp->nc_vp = NULL; 285 ncp->nc_dvp = NULL; 286 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 287 if (ncp->nc_hash.le_prev != 0) { 288 LIST_REMOVE(ncp, nc_hash); 289 ncp->nc_hash.le_prev = 0; 290 } 291 /* cause rescan of list, it may have altered */ 292 nxtcp = nclruhead.tqh_first; 293 TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); 294 } 295} 296