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.1 (Berkeley) 6/10/93 34 * $Id: vfs_cache.c,v 1.3 1994/08/02 07:43:15 davidg Exp $ 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 */ 67 struct namecache **nchashtbl; 68 u_long nchash; /* size of hash table - 1 */ 69 long numcache; /* number of cache entries allocated */ 70 struct namecache *nchhead, **nchtail; /* LRU chain pointers */ 71 struct nchstats nchstats; /* cache effectiveness statistics */ 72 73 int 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 */ 89 int 90 cache_lookup(dvp, vpp, cnp) 91 struct vnode *dvp; 92 struct vnode **vpp; 93 struct componentname *cnp; 94 { 95 register struct namecache *ncp, *ncq, **ncpp; 96 97 if (!doingcache) 98 return (0); 99 if (cnp->cn_namelen > NCHNAMLEN) { 100 nchstats.ncs_long++; 101 cnp->cn_flags &= ~MAKEENTRY; 102 return (0); 103 } 104 ncpp = &nchashtbl[cnp->cn_hash & nchash]; 105 for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) { 106 if (ncp->nc_dvp == dvp && 107 ncp->nc_dvpid == dvp->v_id && 108 ncp->nc_nlen == cnp->cn_namelen && 109 !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 110 break; 111 } 112 if (ncp == NULL) { 113 nchstats.ncs_miss++; 114 return (0); 115 } 116 if (!(cnp->cn_flags & MAKEENTRY)) { 117 nchstats.ncs_badhits++; 118 } else if (ncp->nc_vp == NULL) { 119 if (cnp->cn_nameiop != CREATE) { 120 nchstats.ncs_neghits++; 121 /* 122 * Move this slot to end of LRU chain, 123 * if not already there. 124 */ 125 if (ncp->nc_nxt) { 126 /* remove from LRU chain */ 127 *ncp->nc_prev = ncp->nc_nxt; 128 ncp->nc_nxt->nc_prev = ncp->nc_prev; 129 /* and replace at end of it */ 130 ncp->nc_nxt = NULL; 131 ncp->nc_prev = nchtail; 132 *nchtail = ncp; 133 nchtail = &ncp->nc_nxt; 134 } 135 return (ENOENT); 136 } 137 } else if (ncp->nc_vpid != ncp->nc_vp->v_id) { 138 nchstats.ncs_falsehits++; 139 } else { 140 nchstats.ncs_goodhits++; 141 /* 142 * move this slot to end of LRU chain, if not already there 143 */ 144 if (ncp->nc_nxt) { 145 /* remove from LRU chain */ 146 *ncp->nc_prev = ncp->nc_nxt; 147 ncp->nc_nxt->nc_prev = ncp->nc_prev; 148 /* and replace at end of it */ 149 ncp->nc_nxt = NULL; 150 ncp->nc_prev = nchtail; 151 *nchtail = ncp; 152 nchtail = &ncp->nc_nxt; 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 /* remove from LRU chain */ 164 ncq = ncp->nc_nxt; 165 if (ncq) 166 ncq->nc_prev = ncp->nc_prev; 167 else 168 nchtail = ncp->nc_prev; 169 *ncp->nc_prev = ncq; 170 /* remove from hash chain */ 171 ncq = ncp->nc_forw; 172 if (ncq) 173 ncq->nc_back = ncp->nc_back; 174 *ncp->nc_back = ncq; 175 /* and make a dummy hash chain */ 176 ncp->nc_forw = NULL; 177 ncp->nc_back = NULL; 178 /* insert at head of LRU list (first to grab) */ 179 ncq = nchhead; 180 if (ncq) 181 ncq->nc_prev = &ncp->nc_nxt; 182 else 183 nchtail = &ncp->nc_nxt; 184 nchhead = ncp; 185 ncp->nc_nxt = ncq; 186 ncp->nc_prev = &nchhead; 187 return (0); 188 } 189 190 /* 191 * Add an entry to the cache 192 */ 193 void 194 cache_enter(dvp, vp, cnp) 195 struct vnode *dvp; 196 struct vnode *vp; 197 struct componentname *cnp; 198 { 199 register struct namecache *ncp, *ncq, **ncpp; 200 201 #ifdef DIAGNOSTIC 202 if (cnp->cn_namelen > NCHNAMLEN) 203 panic("cache_enter: name too long"); 204 #endif 205 if (!doingcache) 206 return; 207 /* 208 * Free the cache slot at head of lru chain. 209 */ 210 if (numcache < desiredvnodes) { 211 ncp = (struct namecache *) 212 malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 213 bzero((char *)ncp, sizeof *ncp); 214 numcache++; 215 } else if (!nchhead) { 216 return; 217 } else { 218 ncp = nchhead; 219 /* remove from lru chain */ 220 ncq = ncp->nc_nxt; 221 if (ncq) 222 ncq->nc_prev = ncp->nc_prev; 223 else 224 nchtail = ncp->nc_prev; 225 *ncp->nc_prev = ncq; 226 /* remove from old hash chain, if on one */ 227 if (ncp->nc_back) { 228 ncq = ncp->nc_forw; 229 if (ncq) 230 ncq->nc_back = ncp->nc_back; 231 *ncp->nc_back = ncq; 232 ncp->nc_forw = NULL; 233 ncp->nc_back = NULL; 234 } 235 } 236 /* grab the vnode we just found */ 237 ncp->nc_vp = vp; 238 if (vp) 239 ncp->nc_vpid = vp->v_id; 240 else 241 ncp->nc_vpid = 0; 242 /* fill in cache info */ 243 ncp->nc_dvp = dvp; 244 ncp->nc_dvpid = dvp->v_id; 245 ncp->nc_nlen = cnp->cn_namelen; 246 bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 247 /* link at end of lru chain */ 248 ncp->nc_nxt = NULL; 249 ncp->nc_prev = nchtail; 250 *nchtail = ncp; 251 nchtail = &ncp->nc_nxt; 252 /* and insert on hash chain */ 253 ncpp = &nchashtbl[cnp->cn_hash & nchash]; 254 ncq = *ncpp; 255 if (ncq) 256 ncq->nc_back = &ncp->nc_forw; 257 ncp->nc_forw = ncq; 258 ncp->nc_back = ncpp; 259 *ncpp = ncp; 260 } 261 262 /* 263 * Name cache initialization, from vfs_init() when we are booting 264 */ 265 void 266 nchinit() 267 { 268 269 nchtail = &nchhead; 270 nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash); 271 } 272 273 /* 274 * Cache flush, a particular vnode; called when a vnode is renamed to 275 * hide entries that would now be invalid 276 */ 277 void 278 cache_purge(vp) 279 struct vnode *vp; 280 { 281 struct namecache *ncp, **ncpp; 282 283 vp->v_id = ++nextvnodeid; 284 if (nextvnodeid != 0) 285 return; 286 for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 287 for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) { 288 ncp->nc_vpid = 0; 289 ncp->nc_dvpid = 0; 290 } 291 } 292 vp->v_id = ++nextvnodeid; 293 } 294 295 /* 296 * Cache flush, a whole filesystem; called when filesys is umounted to 297 * remove entries that would now be invalid 298 * 299 * The line "nxtcp = nchhead" near the end is to avoid potential problems 300 * if the cache lru chain is modified while we are dumping the 301 * inode. This makes the algorithm O(n^2), but do you think I care? 302 */ 303 void 304 cache_purgevfs(mp) 305 struct mount *mp; 306 { 307 register struct namecache *ncp, *nxtcp; 308 309 for (ncp = nchhead; ncp; ncp = nxtcp) { 310 if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) { 311 nxtcp = ncp->nc_nxt; 312 continue; 313 } 314 /* free the resources we had */ 315 ncp->nc_vp = NULL; 316 ncp->nc_dvp = NULL; 317 /* remove from old hash chain, if on one */ 318 if (ncp->nc_back) { 319 nxtcp = ncp->nc_forw; 320 if (nxtcp) 321 nxtcp->nc_back = ncp->nc_back; 322 *ncp->nc_back = nxtcp; 323 ncp->nc_forw = NULL; 324 ncp->nc_back = NULL; 325 } 326 /* delete this entry from LRU chain */ 327 nxtcp = ncp->nc_nxt; 328 if (nxtcp) 329 nxtcp->nc_prev = ncp->nc_prev; 330 else 331 nchtail = ncp->nc_prev; 332 *ncp->nc_prev = nxtcp; 333 /* cause rescan of list, it may have altered */ 334 /* also put the now-free entry at head of LRU */ 335 nxtcp = nchhead; 336 if (nxtcp) 337 nxtcp->nc_prev = &ncp->nc_nxt; 338 else 339 nchtail = &ncp->nc_nxt; 340 nchhead = ncp; 341 ncp->nc_nxt = nxtcp; 342 ncp->nc_prev = &nchhead; 343 } 344 } 345