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