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 are permitted 6 * provided that the above copyright notice and this paragraph are 7 * duplicated in all such forms and that any documentation, 8 * advertising materials, and other materials related to such 9 * distribution and use acknowledge that the software was developed 10 * by the University of California, Berkeley. The name of the 11 * University may not be used to endorse or promote products derived 12 * from this software without specific prior written permission. 13 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 14 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 15 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 16 * 17 * @(#)vfs_cache.c 7.2 (Berkeley) 05/05/89 18 */ 19 20 #include "param.h" 21 #include "systm.h" 22 #include "time.h" 23 #include "vnode.h" 24 #include "namei.h" 25 26 /* 27 * Name caching works as follows: 28 * 29 * Names found by directory scans are retained in a cache 30 * for future reference. It is managed LRU, so frequently 31 * used names will hang around. Cache is indexed by hash value 32 * obtained from (ino,dev,name) where ino & dev refer to the 33 * directory containing name. 34 * 35 * For simplicity (and economy of storage), names longer than 36 * a maximum length of NCHNAMLEN are not cached; they occur 37 * infrequently in any case, and are almost never of interest. 38 * 39 * Upon reaching the last segment of a path, if the reference 40 * is for DELETE, or NOCACHE is set (rewrite), and the 41 * name is located in the cache, it will be dropped. 42 */ 43 44 /* 45 * Structures associated with name cacheing. 46 */ 47 #define NCHHASH 128 /* size of hash table */ 48 49 #if ((NCHHASH)&((NCHHASH)-1)) != 0 50 #define NHASH(h) (((unsigned)(h) >> 6) % (NCHHASH)) 51 #else 52 #define NHASH(h) (((unsigned)(h) >> 6) & ((NCHHASH)-1)) 53 #endif 54 55 union nchash { 56 union nchash *nch_head[2]; 57 struct namecache *nch_chain[2]; 58 } nchash[NCHHASH]; 59 #define nch_forw nch_chain[0] 60 #define nch_back nch_chain[1] 61 62 struct namecache *nchhead, **nchtail; /* LRU chain pointers */ 63 struct nchstats nchstats; /* cache effectiveness statistics */ 64 65 /* 66 * Look for a the name in the cache. We don't do this 67 * if the segment name is long, simply so the cache can avoid 68 * holding long names (which would either waste space, or 69 * add greatly to the complexity). 70 */ 71 struct vnode * 72 cache_lookup(ndp) 73 register struct nameidata *ndp; 74 { 75 register struct vnode *dp; 76 register struct namecache *ncp; 77 union nchash *nhp; 78 79 if (ndp->ni_dent.d_namlen > NCHNAMLEN) { 80 nchstats.ncs_long++; 81 ndp->ni_makeentry = 0; 82 return (0); 83 } 84 dp = ndp->ni_vp; 85 nhp = &nchash[NHASH(dp)]; 86 for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp; 87 ncp = ncp->nc_forw) { 88 if (ncp->nc_vp == dp && 89 ncp->nc_nlen == ndp->ni_dent.d_namlen && 90 !bcmp(ncp->nc_name, ndp->ni_dent.d_name, 91 (unsigned)ncp->nc_nlen)) 92 break; 93 } 94 if (ncp == (struct namecache *)nhp) { 95 nchstats.ncs_miss++; 96 ncp = NULL; 97 return (0); 98 } 99 if (ndp->ni_makeentry) { 100 /* 101 * move this slot to end of LRU 102 * chain, if not already there 103 */ 104 if (ncp->nc_nxt) { 105 /* remove from LRU chain */ 106 *ncp->nc_prev = ncp->nc_nxt; 107 ncp->nc_nxt->nc_prev = ncp->nc_prev; 108 109 /* and replace at end of it */ 110 ncp->nc_nxt = NULL; 111 ncp->nc_prev = nchtail; 112 *nchtail = ncp; 113 nchtail = &ncp->nc_nxt; 114 } 115 /* ndp->ni_dent.d_ino = dp->i_number; */ 116 /* ni_dent.d_reclen is garbage ... */ 117 nchstats.ncs_goodhits++; 118 return (ncp->nc_vp); 119 } 120 121 /* 122 * Last component and we are renaming or deleting, 123 * the cache entry is invalid, or otherwise don't 124 * want cache entry to exist. 125 */ 126 nchstats.ncs_badhits++; 127 /* remove from LRU chain */ 128 *ncp->nc_prev = ncp->nc_nxt; 129 if (ncp->nc_nxt) 130 ncp->nc_nxt->nc_prev = ncp->nc_prev; 131 else 132 nchtail = ncp->nc_prev; 133 remque(ncp); /* remove from hash chain */ 134 /* insert at head of LRU list (first to grab) */ 135 ncp->nc_nxt = nchhead; 136 ncp->nc_prev = &nchhead; 137 nchhead->nc_prev = &ncp->nc_nxt; 138 nchhead = ncp; 139 /* and make a dummy hash chain */ 140 ncp->nc_forw = ncp; 141 ncp->nc_back = ncp; 142 ncp = NULL; 143 return (0); 144 } 145 146 /* 147 * Add an entry to the cache 148 */ 149 cache_enter(ndp) 150 register struct nameidata *ndp; 151 { 152 register struct namecache *ncp; 153 union nchash *nhp; 154 155 /* 156 * Free the cache slot at head of lru chain. 157 */ 158 if (ncp = nchhead) { 159 /* remove from lru chain */ 160 *ncp->nc_prev = ncp->nc_nxt; 161 if (ncp->nc_nxt) 162 ncp->nc_nxt->nc_prev = ncp->nc_prev; 163 else 164 nchtail = ncp->nc_prev; 165 remque(ncp); /* remove from old hash chain */ 166 /* grab the inode we just found */ 167 ncp->nc_vp = ndp->ni_vp; 168 /* fill in cache info */ 169 ncp->nc_dp = ndp->ni_dvp; /* parents vnode */ 170 ncp->nc_nlen = ndp->ni_dent.d_namlen; 171 bcopy(ndp->ni_dent.d_name, ncp->nc_name, 172 (unsigned)ncp->nc_nlen); 173 /* link at end of lru chain */ 174 ncp->nc_nxt = NULL; 175 ncp->nc_prev = nchtail; 176 *nchtail = ncp; 177 nchtail = &ncp->nc_nxt; 178 /* and insert on hash chain */ 179 nhp = &nchash[NHASH(ndp->ni_vp)]; 180 insque(ncp, nhp); 181 } 182 } 183 184 /* 185 * Name cache initialization, from main() when we are booting 186 */ 187 nchinit() 188 { 189 register union nchash *nchp; 190 register struct namecache *ncp; 191 192 nchhead = 0; 193 nchtail = &nchhead; 194 for (ncp = namecache; ncp < &namecache[nchsize]; ncp++) { 195 ncp->nc_forw = ncp; /* hash chain */ 196 ncp->nc_back = ncp; 197 ncp->nc_nxt = NULL; /* lru chain */ 198 *nchtail = ncp; 199 ncp->nc_prev = nchtail; 200 nchtail = &ncp->nc_nxt; 201 /* all else is zero already */ 202 } 203 for (nchp = nchash; nchp < &nchash[NCHHASH]; nchp++) { 204 nchp->nch_head[0] = nchp; 205 nchp->nch_head[1] = nchp; 206 } 207 } 208 209 /* 210 * Cache flush, a particular vnode; called when a vnode is renamed to 211 * remove entries that would now be invalid 212 * 213 * The line "nxtcp = nchhead" near the end is to avoid potential problems 214 * if the cache lru chain is modified while we are dumping the 215 * inode. This makes the algorithm O(n^2), but do you think I care? 216 */ 217 cache_purge(vp) 218 register struct vnode *vp; 219 { 220 register struct namecache *ncp, *nxtcp; 221 222 for (ncp = nchhead; ncp; ncp = nxtcp) { 223 nxtcp = ncp->nc_nxt; 224 if (ncp->nc_vp == NULL || ncp->nc_vp != vp) 225 continue; 226 /* free the resources we had */ 227 ncp->nc_vp = NULL; 228 ncp->nc_dp = NULL; 229 remque(ncp); /* remove entry from its hash chain */ 230 ncp->nc_forw = ncp; /* and make a dummy one */ 231 ncp->nc_back = ncp; 232 /* delete this entry from LRU chain */ 233 *ncp->nc_prev = nxtcp; 234 if (nxtcp) 235 nxtcp->nc_prev = ncp->nc_prev; 236 else 237 nchtail = ncp->nc_prev; 238 /* cause rescan of list, it may have altered */ 239 nxtcp = nchhead; 240 /* put the now-free entry at head of LRU */ 241 ncp->nc_nxt = nxtcp; 242 ncp->nc_prev = &nchhead; 243 nxtcp->nc_prev = &ncp->nc_nxt; 244 nchhead = ncp; 245 } 246 } 247 248 /* 249 * Cache flush, a whole filesystem; called when filesys is umounted to 250 * remove entries that would now be invalid 251 * 252 * The line "nxtcp = nchhead" near the end is to avoid potential problems 253 * if the cache lru chain is modified while we are dumping the 254 * inode. This makes the algorithm O(n^2), but do you think I care? 255 */ 256 cache_purgevfs(mp) 257 register struct mount *mp; 258 { 259 register struct namecache *ncp, *nxtcp; 260 261 for (ncp = nchhead; ncp; ncp = nxtcp) { 262 nxtcp = ncp->nc_nxt; 263 if (ncp->nc_vp == NULL || ncp->nc_vp->v_mount != mp) 264 continue; 265 /* free the resources we had */ 266 ncp->nc_vp = NULL; 267 ncp->nc_dp = NULL; 268 remque(ncp); /* remove entry from its hash chain */ 269 ncp->nc_forw = ncp; /* and make a dummy one */ 270 ncp->nc_back = ncp; 271 /* delete this entry from LRU chain */ 272 *ncp->nc_prev = nxtcp; 273 if (nxtcp) 274 nxtcp->nc_prev = ncp->nc_prev; 275 else 276 nchtail = ncp->nc_prev; 277 /* cause rescan of list, it may have altered */ 278 nxtcp = nchhead; 279 /* put the now-free entry at head of LRU */ 280 ncp->nc_nxt = nxtcp; 281 ncp->nc_prev = &nchhead; 282 nxtcp->nc_prev = &ncp->nc_nxt; 283 nchhead = ncp; 284 } 285 } 286