1 /* 2 * Copyright (c) 1989 The Regents of the University of California. 3 * 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 * from: @(#)vfs_cache.c 7.8 (Berkeley) 2/28/91 34 * $Id: vfs_cache.c,v 1.2 1993/05/20 02:55:33 cgd Exp $ 35 */ 36 37 #include "param.h" 38 #include "systm.h" 39 #include "time.h" 40 #include "mount.h" 41 #include "vnode.h" 42 #include "namei.h" 43 #include "errno.h" 44 #include "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 union nchash { 68 union nchash *nch_head[2]; 69 struct namecache *nch_chain[2]; 70 } *nchashtbl; 71 #define nch_forw nch_chain[0] 72 #define nch_back nch_chain[1] 73 74 u_long nchash; /* size of hash table - 1 */ 75 long numcache; /* number of cache entries allocated */ 76 struct namecache *nchhead, **nchtail; /* LRU chain pointers */ 77 struct nchstats nchstats; /* cache effectiveness statistics */ 78 79 int doingcache = 1; /* 1 => enable the cache */ 80 81 /* 82 * Look for a the name in the cache. We don't do this 83 * if the segment name is long, simply so the cache can avoid 84 * holding long names (which would either waste space, or 85 * add greatly to the complexity). 86 * 87 * Lookup is called with ni_dvp pointing to the directory to search, 88 * ni_ptr pointing to the name of the entry being sought, ni_namelen 89 * tells the length of the name, and ni_hash contains a hash of 90 * the name. If the lookup succeeds, the vnode is returned in ni_vp 91 * and a status of -1 is returned. If the lookup determines that 92 * the name does not exist (negative cacheing), a status of ENOENT 93 * is returned. If the lookup fails, a status of zero is returned. 94 */ 95 cache_lookup(ndp) 96 register struct nameidata *ndp; 97 { 98 register struct vnode *dvp; 99 register struct namecache *ncp; 100 union nchash *nhp; 101 102 if (!doingcache) 103 return (0); 104 if (ndp->ni_namelen > NCHNAMLEN) { 105 nchstats.ncs_long++; 106 ndp->ni_makeentry = 0; 107 return (0); 108 } 109 dvp = ndp->ni_dvp; 110 nhp = &nchashtbl[ndp->ni_hash & nchash]; 111 for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp; 112 ncp = ncp->nc_forw) { 113 if (ncp->nc_dvp == dvp && 114 ncp->nc_dvpid == dvp->v_id && 115 ncp->nc_nlen == ndp->ni_namelen && 116 !bcmp(ncp->nc_name, ndp->ni_ptr, (unsigned)ncp->nc_nlen)) 117 break; 118 } 119 if (ncp == (struct namecache *)nhp) { 120 nchstats.ncs_miss++; 121 return (0); 122 } 123 if (!ndp->ni_makeentry) { 124 nchstats.ncs_badhits++; 125 } else if (ncp->nc_vp == NULL) { 126 if ((ndp->ni_nameiop & OPMASK) != CREATE) { 127 nchstats.ncs_neghits++; 128 /* 129 * Move this slot to end of LRU chain, 130 * if not already there. 131 */ 132 if (ncp->nc_nxt) { 133 /* remove from LRU chain */ 134 *ncp->nc_prev = ncp->nc_nxt; 135 ncp->nc_nxt->nc_prev = ncp->nc_prev; 136 /* and replace at end of it */ 137 ncp->nc_nxt = NULL; 138 ncp->nc_prev = nchtail; 139 *nchtail = ncp; 140 nchtail = &ncp->nc_nxt; 141 } 142 return (ENOENT); 143 } 144 } else if (ncp->nc_vpid != ncp->nc_vp->v_id) { 145 nchstats.ncs_falsehits++; 146 } else { 147 nchstats.ncs_goodhits++; 148 /* 149 * move this slot to end of LRU chain, if not already there 150 */ 151 if (ncp->nc_nxt) { 152 /* remove from LRU chain */ 153 *ncp->nc_prev = ncp->nc_nxt; 154 ncp->nc_nxt->nc_prev = ncp->nc_prev; 155 /* and replace at end of it */ 156 ncp->nc_nxt = NULL; 157 ncp->nc_prev = nchtail; 158 *nchtail = ncp; 159 nchtail = &ncp->nc_nxt; 160 } 161 ndp->ni_vp = ncp->nc_vp; 162 return (-1); 163 } 164 165 /* 166 * Last component and we are renaming or deleting, 167 * the cache entry is invalid, or otherwise don't 168 * want cache entry to exist. 169 */ 170 /* remove from LRU chain */ 171 *ncp->nc_prev = ncp->nc_nxt; 172 if (ncp->nc_nxt) 173 ncp->nc_nxt->nc_prev = ncp->nc_prev; 174 else 175 nchtail = ncp->nc_prev; 176 /* remove from hash chain */ 177 remque(ncp); 178 /* insert at head of LRU list (first to grab) */ 179 ncp->nc_nxt = nchhead; 180 ncp->nc_prev = &nchhead; 181 nchhead->nc_prev = &ncp->nc_nxt; 182 nchhead = ncp; 183 /* and make a dummy hash chain */ 184 ncp->nc_forw = ncp; 185 ncp->nc_back = ncp; 186 return (0); 187 } 188 189 /* 190 * Add an entry to the cache 191 */ 192 cache_enter(ndp) 193 register struct nameidata *ndp; 194 { 195 register struct namecache *ncp; 196 union nchash *nhp; 197 198 if (!doingcache) 199 return; 200 /* 201 * Free the cache slot at head of lru chain. 202 */ 203 if (numcache < desiredvnodes) { 204 ncp = (struct namecache *) 205 malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 206 bzero((char *)ncp, sizeof *ncp); 207 numcache++; 208 } else if (ncp = nchhead) { 209 /* remove from lru chain */ 210 *ncp->nc_prev = ncp->nc_nxt; 211 if (ncp->nc_nxt) 212 ncp->nc_nxt->nc_prev = ncp->nc_prev; 213 else 214 nchtail = ncp->nc_prev; 215 /* remove from old hash chain */ 216 remque(ncp); 217 } else 218 return; 219 /* grab the vnode we just found */ 220 ncp->nc_vp = ndp->ni_vp; 221 if (ndp->ni_vp) 222 ncp->nc_vpid = ndp->ni_vp->v_id; 223 else 224 ncp->nc_vpid = 0; 225 /* fill in cache info */ 226 ncp->nc_dvp = ndp->ni_dvp; 227 ncp->nc_dvpid = ndp->ni_dvp->v_id; 228 ncp->nc_nlen = ndp->ni_namelen; 229 bcopy(ndp->ni_ptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 230 /* link at end of lru chain */ 231 ncp->nc_nxt = NULL; 232 ncp->nc_prev = nchtail; 233 *nchtail = ncp; 234 nchtail = &ncp->nc_nxt; 235 /* and insert on hash chain */ 236 nhp = &nchashtbl[ndp->ni_hash & nchash]; 237 insque(ncp, nhp); 238 } 239 240 /* 241 * Name cache initialization, from vfs_init() when we are booting 242 */ 243 nchinit() 244 { 245 register union nchash *nchp; 246 long nchashsize; 247 248 nchhead = 0; 249 nchtail = &nchhead; 250 nchashsize = roundup((desiredvnodes + 1) * sizeof *nchp / 2, 251 NBPG * CLSIZE); 252 nchashtbl = (union nchash *)malloc((u_long)nchashsize, 253 M_CACHE, M_WAITOK); 254 for (nchash = 1; nchash <= nchashsize / sizeof *nchp; nchash <<= 1) 255 /* void */; 256 nchash = (nchash >> 1) - 1; 257 for (nchp = &nchashtbl[nchash]; nchp >= nchashtbl; nchp--) { 258 nchp->nch_head[0] = nchp; 259 nchp->nch_head[1] = nchp; 260 } 261 } 262 263 /* 264 * Cache flush, a particular vnode; called when a vnode is renamed to 265 * hide entries that would now be invalid 266 */ 267 cache_purge(vp) 268 struct vnode *vp; 269 { 270 union nchash *nhp; 271 struct namecache *ncp; 272 273 vp->v_id = ++nextvnodeid; 274 if (nextvnodeid != 0) 275 return; 276 for (nhp = &nchashtbl[nchash]; nhp >= nchashtbl; nhp--) { 277 for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp; 278 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 cache_purgevfs(mp) 295 struct mount *mp; 296 { 297 register struct namecache *ncp, *nxtcp; 298 299 for (ncp = nchhead; ncp; ncp = nxtcp) { 300 nxtcp = ncp->nc_nxt; 301 if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) 302 continue; 303 /* free the resources we had */ 304 ncp->nc_vp = NULL; 305 ncp->nc_dvp = NULL; 306 remque(ncp); /* remove entry from its hash chain */ 307 ncp->nc_forw = ncp; /* and make a dummy one */ 308 ncp->nc_back = ncp; 309 /* delete this entry from LRU chain */ 310 *ncp->nc_prev = nxtcp; 311 if (nxtcp) 312 nxtcp->nc_prev = ncp->nc_prev; 313 else 314 nchtail = ncp->nc_prev; 315 /* cause rescan of list, it may have altered */ 316 nxtcp = nchhead; 317 /* put the now-free entry at head of LRU */ 318 ncp->nc_nxt = nxtcp; 319 ncp->nc_prev = &nchhead; 320 nxtcp->nc_prev = &ncp->nc_nxt; 321 nchhead = ncp; 322 } 323 } 324