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