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