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.3 (Berkeley) 05/09/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 return (0); /* XXX for now */ 80 if (ndp->ni_dent.d_namlen > NCHNAMLEN) { 81 nchstats.ncs_long++; 82 ndp->ni_makeentry = 0; 83 return (0); 84 } 85 dp = ndp->ni_vp; 86 nhp = &nchash[NHASH(dp)]; 87 for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp; 88 ncp = ncp->nc_forw) { 89 if (ncp->nc_vp == dp && 90 ncp->nc_nlen == ndp->ni_dent.d_namlen && 91 !bcmp(ncp->nc_name, ndp->ni_dent.d_name, 92 (unsigned)ncp->nc_nlen)) 93 break; 94 } 95 if (ncp == (struct namecache *)nhp) { 96 nchstats.ncs_miss++; 97 ncp = NULL; 98 return (0); 99 } 100 if (ndp->ni_makeentry) { 101 /* 102 * move this slot to end of LRU 103 * chain, if not already there 104 */ 105 if (ncp->nc_nxt) { 106 /* remove from LRU chain */ 107 *ncp->nc_prev = ncp->nc_nxt; 108 ncp->nc_nxt->nc_prev = ncp->nc_prev; 109 110 /* and replace at end of it */ 111 ncp->nc_nxt = NULL; 112 ncp->nc_prev = nchtail; 113 *nchtail = ncp; 114 nchtail = &ncp->nc_nxt; 115 } 116 /* ndp->ni_dent.d_ino = dp->i_number; */ 117 /* ni_dent.d_reclen is garbage ... */ 118 nchstats.ncs_goodhits++; 119 return (ncp->nc_vp); 120 } 121 122 /* 123 * Last component and we are renaming or deleting, 124 * the cache entry is invalid, or otherwise don't 125 * want cache entry to exist. 126 */ 127 nchstats.ncs_badhits++; 128 /* remove from LRU chain */ 129 *ncp->nc_prev = ncp->nc_nxt; 130 if (ncp->nc_nxt) 131 ncp->nc_nxt->nc_prev = ncp->nc_prev; 132 else 133 nchtail = ncp->nc_prev; 134 remque(ncp); /* remove from hash chain */ 135 /* insert at head of LRU list (first to grab) */ 136 ncp->nc_nxt = nchhead; 137 ncp->nc_prev = &nchhead; 138 nchhead->nc_prev = &ncp->nc_nxt; 139 nchhead = ncp; 140 /* and make a dummy hash chain */ 141 ncp->nc_forw = ncp; 142 ncp->nc_back = ncp; 143 ncp = NULL; 144 return (0); 145 } 146 147 /* 148 * Add an entry to the cache 149 */ 150 cache_enter(ndp) 151 register struct nameidata *ndp; 152 { 153 register struct namecache *ncp; 154 union nchash *nhp; 155 156 return; /* XXX for now */ 157 /* 158 * Free the cache slot at head of lru chain. 159 */ 160 if (ncp = nchhead) { 161 /* remove from lru chain */ 162 *ncp->nc_prev = ncp->nc_nxt; 163 if (ncp->nc_nxt) 164 ncp->nc_nxt->nc_prev = ncp->nc_prev; 165 else 166 nchtail = ncp->nc_prev; 167 remque(ncp); /* remove from old hash chain */ 168 /* grab the inode we just found */ 169 ncp->nc_vp = ndp->ni_vp; 170 /* fill in cache info */ 171 ncp->nc_dp = ndp->ni_dvp; /* parents vnode */ 172 ncp->nc_nlen = ndp->ni_dent.d_namlen; 173 bcopy(ndp->ni_dent.d_name, ncp->nc_name, 174 (unsigned)ncp->nc_nlen); 175 /* link at end of lru chain */ 176 ncp->nc_nxt = NULL; 177 ncp->nc_prev = nchtail; 178 *nchtail = ncp; 179 nchtail = &ncp->nc_nxt; 180 /* and insert on hash chain */ 181 nhp = &nchash[NHASH(ndp->ni_vp)]; 182 insque(ncp, nhp); 183 } 184 } 185 186 /* 187 * Name cache initialization, from main() when we are booting 188 */ 189 nchinit() 190 { 191 register union nchash *nchp; 192 register struct namecache *ncp; 193 194 nchhead = 0; 195 nchtail = &nchhead; 196 for (ncp = namecache; ncp < &namecache[nchsize]; ncp++) { 197 ncp->nc_forw = ncp; /* hash chain */ 198 ncp->nc_back = ncp; 199 ncp->nc_nxt = NULL; /* lru chain */ 200 *nchtail = ncp; 201 ncp->nc_prev = nchtail; 202 nchtail = &ncp->nc_nxt; 203 /* all else is zero already */ 204 } 205 for (nchp = nchash; nchp < &nchash[NCHHASH]; nchp++) { 206 nchp->nch_head[0] = nchp; 207 nchp->nch_head[1] = nchp; 208 } 209 } 210 211 /* 212 * Cache flush, a particular vnode; called when a vnode is renamed to 213 * remove entries that would now be invalid 214 * 215 * The line "nxtcp = nchhead" near the end is to avoid potential problems 216 * if the cache lru chain is modified while we are dumping the 217 * inode. This makes the algorithm O(n^2), but do you think I care? 218 */ 219 cache_purge(vp) 220 register struct vnode *vp; 221 { 222 register struct namecache *ncp, *nxtcp; 223 224 for (ncp = nchhead; ncp; ncp = nxtcp) { 225 nxtcp = ncp->nc_nxt; 226 if (ncp->nc_vp == NULL || ncp->nc_vp != vp) 227 continue; 228 /* free the resources we had */ 229 ncp->nc_vp = NULL; 230 ncp->nc_dp = NULL; 231 remque(ncp); /* remove entry from its hash chain */ 232 ncp->nc_forw = ncp; /* and make a dummy one */ 233 ncp->nc_back = ncp; 234 /* delete this entry from LRU chain */ 235 *ncp->nc_prev = nxtcp; 236 if (nxtcp) 237 nxtcp->nc_prev = ncp->nc_prev; 238 else 239 nchtail = ncp->nc_prev; 240 /* cause rescan of list, it may have altered */ 241 nxtcp = nchhead; 242 /* put the now-free entry at head of LRU */ 243 ncp->nc_nxt = nxtcp; 244 ncp->nc_prev = &nchhead; 245 nxtcp->nc_prev = &ncp->nc_nxt; 246 nchhead = ncp; 247 } 248 } 249 250 /* 251 * Cache flush, a whole filesystem; called when filesys is umounted to 252 * remove entries that would now be invalid 253 * 254 * The line "nxtcp = nchhead" near the end is to avoid potential problems 255 * if the cache lru chain is modified while we are dumping the 256 * inode. This makes the algorithm O(n^2), but do you think I care? 257 */ 258 cache_purgevfs(mp) 259 register struct mount *mp; 260 { 261 register struct namecache *ncp, *nxtcp; 262 263 for (ncp = nchhead; ncp; ncp = nxtcp) { 264 nxtcp = ncp->nc_nxt; 265 if (ncp->nc_vp == NULL || ncp->nc_vp->v_mount != mp) 266 continue; 267 /* free the resources we had */ 268 ncp->nc_vp = NULL; 269 ncp->nc_dp = NULL; 270 remque(ncp); /* remove entry from its hash chain */ 271 ncp->nc_forw = ncp; /* and make a dummy one */ 272 ncp->nc_back = ncp; 273 /* delete this entry from LRU chain */ 274 *ncp->nc_prev = nxtcp; 275 if (nxtcp) 276 nxtcp->nc_prev = ncp->nc_prev; 277 else 278 nchtail = ncp->nc_prev; 279 /* cause rescan of list, it may have altered */ 280 nxtcp = nchhead; 281 /* put the now-free entry at head of LRU */ 282 ncp->nc_nxt = nxtcp; 283 ncp->nc_prev = &nchhead; 284 nxtcp->nc_prev = &ncp->nc_nxt; 285 nchhead = ncp; 286 } 287 } 288