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 */ 35 36 #include <sys/param.h> 37 #include <sys/systm.h> 38 #include <sys/time.h> 39 #include <sys/mount.h> 40 #include <sys/vnode.h> 41 #include <sys/namei.h> 42 #include <sys/errno.h> 43 #include <sys/malloc.h> 44 45 /* 46 * Name caching works as follows: 47 * 48 * Names found by directory scans are retained in a cache 49 * for future reference. It is managed LRU, so frequently 50 * used names will hang around. Cache is indexed by hash value 51 * obtained from (vp, name) where vp refers to the directory 52 * containing name. 53 * 54 * For simplicity (and economy of storage), names longer than 55 * a maximum length of NCHNAMLEN are not cached; they occur 56 * infrequently in any case, and are almost never of interest. 57 * 58 * Upon reaching the last segment of a path, if the reference 59 * is for DELETE, or NOCACHE is set (rewrite), and the 60 * name is located in the cache, it will be dropped. 61 */ 62 63 /* 64 * Structures associated with name cacheing. 65 */ 66 struct namecache **nchashtbl; 67 u_long nchash; /* size of hash table - 1 */ 68 long numcache; /* number of cache entries allocated */ 69 struct namecache *nchhead, **nchtail; /* LRU chain pointers */ 70 struct nchstats nchstats; /* cache effectiveness statistics */ 71 72 int doingcache = 1; /* 1 => enable the cache */ 73 74 /* 75 * Look for a the name in the cache. We don't do this 76 * if the segment name is long, simply so the cache can avoid 77 * holding long names (which would either waste space, or 78 * add greatly to the complexity). 79 * 80 * Lookup is called with ni_dvp pointing to the directory to search, 81 * ni_ptr pointing to the name of the entry being sought, ni_namelen 82 * tells the length of the name, and ni_hash contains a hash of 83 * the name. If the lookup succeeds, the vnode is returned in ni_vp 84 * and a status of -1 is returned. If the lookup determines that 85 * the name does not exist (negative cacheing), a status of ENOENT 86 * is returned. If the lookup fails, a status of zero is returned. 87 */ 88 int 89 cache_lookup(dvp, vpp, cnp) 90 struct vnode *dvp; 91 struct vnode **vpp; 92 struct componentname *cnp; 93 { 94 register struct namecache *ncp, *ncq, **ncpp; 95 96 if (!doingcache) 97 return (0); 98 if (cnp->cn_namelen > NCHNAMLEN) { 99 nchstats.ncs_long++; 100 cnp->cn_flags &= ~MAKEENTRY; 101 return (0); 102 } 103 ncpp = &nchashtbl[cnp->cn_hash & nchash]; 104 for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) { 105 if (ncp->nc_dvp == dvp && 106 ncp->nc_dvpid == dvp->v_id && 107 ncp->nc_nlen == cnp->cn_namelen && 108 !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 109 break; 110 } 111 if (ncp == NULL) { 112 nchstats.ncs_miss++; 113 return (0); 114 } 115 if (!(cnp->cn_flags & MAKEENTRY)) { 116 nchstats.ncs_badhits++; 117 } else if (ncp->nc_vp == NULL) { 118 if (cnp->cn_nameiop != CREATE) { 119 nchstats.ncs_neghits++; 120 /* 121 * Move this slot to end of LRU chain, 122 * if not already there. 123 */ 124 if (ncp->nc_nxt) { 125 /* remove from LRU chain */ 126 *ncp->nc_prev = ncp->nc_nxt; 127 ncp->nc_nxt->nc_prev = ncp->nc_prev; 128 /* and replace at end of it */ 129 ncp->nc_nxt = NULL; 130 ncp->nc_prev = nchtail; 131 *nchtail = ncp; 132 nchtail = &ncp->nc_nxt; 133 } 134 return (ENOENT); 135 } 136 } else if (ncp->nc_vpid != ncp->nc_vp->v_id) { 137 nchstats.ncs_falsehits++; 138 } else { 139 nchstats.ncs_goodhits++; 140 /* 141 * move this slot to end of LRU chain, if not already there 142 */ 143 if (ncp->nc_nxt) { 144 /* remove from LRU chain */ 145 *ncp->nc_prev = ncp->nc_nxt; 146 ncp->nc_nxt->nc_prev = ncp->nc_prev; 147 /* and replace at end of it */ 148 ncp->nc_nxt = NULL; 149 ncp->nc_prev = nchtail; 150 *nchtail = ncp; 151 nchtail = &ncp->nc_nxt; 152 } 153 *vpp = ncp->nc_vp; 154 return (-1); 155 } 156 157 /* 158 * Last component and we are renaming or deleting, 159 * the cache entry is invalid, or otherwise don't 160 * want cache entry to exist. 161 */ 162 /* remove from LRU chain */ 163 if (ncq = ncp->nc_nxt) 164 ncq->nc_prev = ncp->nc_prev; 165 else 166 nchtail = ncp->nc_prev; 167 *ncp->nc_prev = ncq; 168 /* remove from hash chain */ 169 if (ncq = ncp->nc_forw) 170 ncq->nc_back = ncp->nc_back; 171 *ncp->nc_back = ncq; 172 /* and make a dummy hash chain */ 173 ncp->nc_forw = NULL; 174 ncp->nc_back = NULL; 175 /* insert at head of LRU list (first to grab) */ 176 if (ncq = nchhead) 177 ncq->nc_prev = &ncp->nc_nxt; 178 else 179 nchtail = &ncp->nc_nxt; 180 nchhead = ncp; 181 ncp->nc_nxt = ncq; 182 ncp->nc_prev = &nchhead; 183 return (0); 184 } 185 186 /* 187 * Add an entry to the cache 188 */ 189 void 190 cache_enter(dvp, vp, cnp) 191 struct vnode *dvp; 192 struct vnode *vp; 193 struct componentname *cnp; 194 { 195 register struct namecache *ncp, *ncq, **ncpp; 196 197 #ifdef DIAGNOSTIC 198 if (cnp->cn_namelen > NCHNAMLEN) 199 panic("cache_enter: name too long"); 200 #endif 201 if (!doingcache) 202 return; 203 /* 204 * Free the cache slot at head of lru chain. 205 */ 206 if (numcache < desiredvnodes) { 207 ncp = (struct namecache *) 208 malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 209 bzero((char *)ncp, sizeof *ncp); 210 numcache++; 211 } else if (ncp = nchhead) { 212 /* remove from lru chain */ 213 if (ncq = ncp->nc_nxt) 214 ncq->nc_prev = ncp->nc_prev; 215 else 216 nchtail = ncp->nc_prev; 217 *ncp->nc_prev = ncq; 218 /* remove from old hash chain, if on one */ 219 if (ncp->nc_back) { 220 if (ncq = ncp->nc_forw) 221 ncq->nc_back = ncp->nc_back; 222 *ncp->nc_back = ncq; 223 ncp->nc_forw = NULL; 224 ncp->nc_back = NULL; 225 } 226 } else 227 return; 228 /* grab the vnode we just found */ 229 ncp->nc_vp = vp; 230 if (vp) 231 ncp->nc_vpid = vp->v_id; 232 else 233 ncp->nc_vpid = 0; 234 /* fill in cache info */ 235 ncp->nc_dvp = dvp; 236 ncp->nc_dvpid = dvp->v_id; 237 ncp->nc_nlen = cnp->cn_namelen; 238 bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 239 /* link at end of lru chain */ 240 ncp->nc_nxt = NULL; 241 ncp->nc_prev = nchtail; 242 *nchtail = ncp; 243 nchtail = &ncp->nc_nxt; 244 /* and insert on hash chain */ 245 ncpp = &nchashtbl[cnp->cn_hash & nchash]; 246 if (ncq = *ncpp) 247 ncq->nc_back = &ncp->nc_forw; 248 ncp->nc_forw = ncq; 249 ncp->nc_back = ncpp; 250 *ncpp = ncp; 251 } 252 253 /* 254 * Name cache initialization, from vfs_init() when we are booting 255 */ 256 void 257 nchinit() 258 { 259 260 nchtail = &nchhead; 261 nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash); 262 } 263 264 /* 265 * Cache flush, a particular vnode; called when a vnode is renamed to 266 * hide entries that would now be invalid 267 */ 268 void 269 cache_purge(vp) 270 struct vnode *vp; 271 { 272 struct namecache *ncp, **ncpp; 273 274 vp->v_id = ++nextvnodeid; 275 if (nextvnodeid != 0) 276 return; 277 for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 278 for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) { 279 ncp->nc_vpid = 0; 280 ncp->nc_dvpid = 0; 281 } 282 } 283 vp->v_id = ++nextvnodeid; 284 } 285 286 /* 287 * Cache flush, a whole filesystem; called when filesys is umounted to 288 * remove entries that would now be invalid 289 * 290 * The line "nxtcp = nchhead" near the end is to avoid potential problems 291 * if the cache lru chain is modified while we are dumping the 292 * inode. This makes the algorithm O(n^2), but do you think I care? 293 */ 294 void 295 cache_purgevfs(mp) 296 struct mount *mp; 297 { 298 register struct namecache *ncp, *nxtcp; 299 300 for (ncp = nchhead; ncp; ncp = nxtcp) { 301 if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) { 302 nxtcp = ncp->nc_nxt; 303 continue; 304 } 305 /* free the resources we had */ 306 ncp->nc_vp = NULL; 307 ncp->nc_dvp = NULL; 308 /* remove from old hash chain, if on one */ 309 if (ncp->nc_back) { 310 if (nxtcp = ncp->nc_forw) 311 nxtcp->nc_back = ncp->nc_back; 312 *ncp->nc_back = nxtcp; 313 ncp->nc_forw = NULL; 314 ncp->nc_back = NULL; 315 } 316 /* delete this entry from LRU chain */ 317 if (nxtcp = ncp->nc_nxt) 318 nxtcp->nc_prev = ncp->nc_prev; 319 else 320 nchtail = ncp->nc_prev; 321 *ncp->nc_prev = nxtcp; 322 /* cause rescan of list, it may have altered */ 323 /* also put the now-free entry at head of LRU */ 324 if (nxtcp = nchhead) 325 nxtcp->nc_prev = &ncp->nc_nxt; 326 else 327 nchtail = &ncp->nc_nxt; 328 nchhead = ncp; 329 ncp->nc_nxt = nxtcp; 330 ncp->nc_prev = &nchhead; 331 } 332 } 333