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.3 1993/09/07 15:41:10 ws 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 and directory vnode. If the lookup succeeds, the vnode is 91 * returned in ni_vp and a status of -1 is returned. If the lookup 92 * determines that the name does not exist (negative cacheing), 93 * a status of ENOENT is returned. 94 * If the lookup fails, a status of zero is returned. 95 */ 96 cache_lookup(ndp) 97 register struct nameidata *ndp; 98 { 99 register struct vnode *dvp; 100 register struct namecache *ncp; 101 union nchash *nhp; 102 103 if (!doingcache) 104 return (0); 105 if (ndp->ni_namelen > NCHNAMLEN) { 106 nchstats.ncs_long++; 107 ndp->ni_makeentry = 0; 108 return (0); 109 } 110 dvp = ndp->ni_dvp; 111 nhp = &nchashtbl[ndp->ni_hash & nchash]; 112 for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp; 113 ncp = ncp->nc_forw) { 114 if (ncp->nc_dvp == dvp && 115 ncp->nc_dvpid == dvp->v_id && 116 ncp->nc_nlen == ndp->ni_namelen && 117 !bcmp(ncp->nc_name, ndp->ni_ptr, (unsigned)ncp->nc_nlen)) 118 break; 119 } 120 if (ncp == (struct namecache *)nhp) { 121 nchstats.ncs_miss++; 122 return (0); 123 } 124 if (!ndp->ni_makeentry) { 125 nchstats.ncs_badhits++; 126 } else if (ncp->nc_vp == NULL) { 127 if ((ndp->ni_nameiop & OPMASK) != 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_nxt) { 134 /* remove from LRU chain */ 135 *ncp->nc_prev = ncp->nc_nxt; 136 ncp->nc_nxt->nc_prev = ncp->nc_prev; 137 /* and replace at end of it */ 138 ncp->nc_nxt = NULL; 139 ncp->nc_prev = nchtail; 140 *nchtail = ncp; 141 nchtail = &ncp->nc_nxt; 142 } 143 return (ENOENT); 144 } 145 } else if (ncp->nc_vpid != ncp->nc_vp->v_id) { 146 nchstats.ncs_falsehits++; 147 } else { 148 nchstats.ncs_goodhits++; 149 /* 150 * move this slot to end of LRU chain, if not already there 151 */ 152 if (ncp->nc_nxt) { 153 /* remove from LRU chain */ 154 *ncp->nc_prev = ncp->nc_nxt; 155 ncp->nc_nxt->nc_prev = ncp->nc_prev; 156 /* and replace at end of it */ 157 ncp->nc_nxt = NULL; 158 ncp->nc_prev = nchtail; 159 *nchtail = ncp; 160 nchtail = &ncp->nc_nxt; 161 } 162 ndp->ni_vp = ncp->nc_vp; 163 return (-1); 164 } 165 166 /* 167 * Last component and we are renaming or deleting, 168 * the cache entry is invalid, or otherwise don't 169 * want cache entry to exist. 170 */ 171 /* remove from LRU chain */ 172 *ncp->nc_prev = ncp->nc_nxt; 173 if (ncp->nc_nxt) 174 ncp->nc_nxt->nc_prev = ncp->nc_prev; 175 else 176 nchtail = ncp->nc_prev; 177 /* remove from hash chain */ 178 remque(ncp); 179 /* insert at head of LRU list (first to grab) */ 180 ncp->nc_nxt = nchhead; 181 ncp->nc_prev = &nchhead; 182 nchhead->nc_prev = &ncp->nc_nxt; 183 nchhead = ncp; 184 /* and make a dummy hash chain */ 185 ncp->nc_forw = ncp; 186 ncp->nc_back = ncp; 187 return (0); 188 } 189 190 /* 191 * Add an entry to the cache 192 */ 193 cache_enter(ndp) 194 register struct nameidata *ndp; 195 { 196 register struct namecache *ncp; 197 union nchash *nhp; 198 199 if (!doingcache) 200 return; 201 /* 202 * Free the cache slot at head of lru chain. 203 */ 204 if (numcache < desiredvnodes) { 205 ncp = (struct namecache *) 206 malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 207 bzero((char *)ncp, sizeof *ncp); 208 numcache++; 209 } else if (ncp = nchhead) { 210 /* remove from lru chain */ 211 *ncp->nc_prev = ncp->nc_nxt; 212 if (ncp->nc_nxt) 213 ncp->nc_nxt->nc_prev = ncp->nc_prev; 214 else 215 nchtail = ncp->nc_prev; 216 /* remove from old hash chain */ 217 remque(ncp); 218 } else 219 return; 220 /* grab the vnode we just found */ 221 ncp->nc_vp = ndp->ni_vp; 222 if (ndp->ni_vp) 223 ncp->nc_vpid = ndp->ni_vp->v_id; 224 else 225 ncp->nc_vpid = 0; 226 /* fill in cache info */ 227 ncp->nc_dvp = ndp->ni_dvp; 228 ncp->nc_dvpid = ndp->ni_dvp->v_id; 229 ncp->nc_nlen = ndp->ni_namelen; 230 bcopy(ndp->ni_ptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 231 /* link at end of lru chain */ 232 ncp->nc_nxt = NULL; 233 ncp->nc_prev = nchtail; 234 *nchtail = ncp; 235 nchtail = &ncp->nc_nxt; 236 /* and insert on hash chain */ 237 nhp = &nchashtbl[ndp->ni_hash & nchash]; 238 insque(ncp, nhp); 239 } 240 241 /* 242 * Name cache initialization, from vfs_init() when we are booting 243 */ 244 nchinit() 245 { 246 register union nchash *nchp; 247 long nchashsize; 248 249 nchhead = 0; 250 nchtail = &nchhead; 251 nchashsize = roundup((desiredvnodes + 1) * sizeof *nchp / 2, 252 NBPG * CLSIZE); 253 nchashtbl = (union nchash *)malloc((u_long)nchashsize, 254 M_CACHE, M_WAITOK); 255 for (nchash = 1; nchash <= nchashsize / sizeof *nchp; nchash <<= 1) 256 /* void */; 257 nchash = (nchash >> 1) - 1; 258 for (nchp = &nchashtbl[nchash]; nchp >= nchashtbl; nchp--) { 259 nchp->nch_head[0] = nchp; 260 nchp->nch_head[1] = nchp; 261 } 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 cache_purge(vp) 269 struct vnode *vp; 270 { 271 union nchash *nhp; 272 struct namecache *ncp; 273 274 vp->v_id = ++nextvnodeid; 275 if (nextvnodeid != 0) 276 return; 277 for (nhp = &nchashtbl[nchash]; nhp >= nchashtbl; nhp--) { 278 for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp; 279 ncp = ncp->nc_forw) { 280 ncp->nc_vpid = 0; 281 ncp->nc_dvpid = 0; 282 } 283 } 284 vp->v_id = ++nextvnodeid; 285 } 286 287 /* 288 * Cache flush, a whole filesystem; called when filesys is umounted to 289 * remove entries that would now be invalid 290 * 291 * The line "nxtcp = nchhead" near the end is to avoid potential problems 292 * if the cache lru chain is modified while we are dumping the 293 * inode. This makes the algorithm O(n^2), but do you think I care? 294 */ 295 cache_purgevfs(mp) 296 struct mount *mp; 297 { 298 register struct namecache *ncp, *nxtcp; 299 300 for (ncp = nchhead; ncp; ncp = nxtcp) { 301 nxtcp = ncp->nc_nxt; 302 if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) 303 continue; 304 /* free the resources we had */ 305 ncp->nc_vp = NULL; 306 ncp->nc_dvp = NULL; 307 remque(ncp); /* remove entry from its hash chain */ 308 ncp->nc_forw = ncp; /* and make a dummy one */ 309 ncp->nc_back = ncp; 310 /* delete this entry from LRU chain */ 311 *ncp->nc_prev = nxtcp; 312 if (nxtcp) 313 nxtcp->nc_prev = ncp->nc_prev; 314 else 315 nchtail = ncp->nc_prev; 316 /* cause rescan of list, it may have altered */ 317 nxtcp = nchhead; 318 /* put the now-free entry at head of LRU */ 319 ncp->nc_nxt = nxtcp; 320 ncp->nc_prev = &nchhead; 321 nxtcp->nc_prev = &ncp->nc_nxt; 322 nchhead = ncp; 323 } 324 } 325