1 /* 2 * Copyright (c) 1989, 1993, 1995 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Poul-Henning Kamp of the FreeBSD Project. 7 * 8 * %sccs.include.redist.c% 9 * 10 * from: vfs_cache.c,v 1.11 1995/03/12 02:01:20 phk Exp $ 11 * 12 * @(#)vfs_cache.c 8.4 (Berkeley) 03/18/95 13 */ 14 15 #include <sys/param.h> 16 #include <sys/systm.h> 17 #include <sys/time.h> 18 #include <sys/mount.h> 19 #include <sys/vnode.h> 20 #include <sys/namei.h> 21 #include <sys/errno.h> 22 #include <sys/malloc.h> 23 24 /* 25 * Name caching works as follows: 26 * 27 * Names found by directory scans are retained in a cache 28 * for future reference. It is managed LRU, so frequently 29 * used names will hang around. Cache is indexed by hash value 30 * obtained from (vp, name) where vp refers to the directory 31 * containing name. 32 * 33 * If it is a "negative" entry, (i.e. for a name that is known NOT to 34 * exist) the vnode pointer will be NULL. 35 * 36 * For simplicity (and economy of storage), names longer than 37 * a maximum length of NCHNAMLEN are not cached; they occur 38 * infrequently in any case, and are almost never of interest. 39 * 40 * Upon reaching the last segment of a path, if the reference 41 * is for DELETE, or NOCACHE is set (rewrite), and the 42 * name is located in the cache, it will be dropped. 43 */ 44 45 /* 46 * Structures associated with name cacheing. 47 */ 48 #define NCHHASH(dvp, cnp) \ 49 (&nchashtbl[((dvp)->v_id + (cnp)->cn_hash) & nchash]) 50 LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */ 51 u_long nchash; /* size of hash table - 1 */ 52 long numcache; /* number of cache entries allocated */ 53 TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */ 54 struct nchstats nchstats; /* cache effectiveness statistics */ 55 56 int doingcache = 1; /* 1 => enable the cache */ 57 58 /* 59 * Delete an entry from its hash list and move it to the front 60 * of the LRU list for immediate reuse. 61 */ 62 #define PURGE(ncp) { \ 63 LIST_REMOVE(ncp, nc_hash); \ 64 ncp->nc_hash.le_prev = 0; \ 65 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 66 TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); \ 67 } 68 69 /* 70 * Move an entry that has been used to the tail of the LRU list 71 * so that it will be preserved for future use. 72 */ 73 #define TOUCH(ncp) { \ 74 if (ncp->nc_lru.tqe_next != 0) { \ 75 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \ 76 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); \ 77 } \ 78 } 79 80 /* 81 * Lookup an entry in the cache 82 * 83 * We don't do this if the segment name is long, simply so the cache 84 * can avoid holding long names (which would either waste space, or 85 * add greatly to the complexity). 86 * 87 * Lookup is called with dvp pointing to the directory to search, 88 * cnp pointing to the name of the entry being sought. If the lookup 89 * succeeds, the vnode is returned in *vpp, and a status of -1 is 90 * returned. If the lookup determines that the name does not exist 91 * (negative cacheing), a status of ENOENT is returned. If the lookup 92 * fails, a status of zero is returned. 93 */ 94 95 int 96 cache_lookup(dvp, vpp, cnp) 97 struct vnode *dvp; 98 struct vnode **vpp; 99 struct componentname *cnp; 100 { 101 register struct namecache *ncp, *nnp; 102 register struct nchashhead *ncpp; 103 104 if (!doingcache) { 105 cnp->cn_flags &= ~MAKEENTRY; 106 return (0); 107 } 108 if (cnp->cn_namelen > NCHNAMLEN) { 109 nchstats.ncs_long++; 110 cnp->cn_flags &= ~MAKEENTRY; 111 return (0); 112 } 113 114 ncpp = NCHHASH(dvp, cnp); 115 for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) { 116 nnp = ncp->nc_hash.le_next; 117 /* If one of the vp's went stale, don't bother anymore. */ 118 if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) || 119 (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id)) { 120 nchstats.ncs_falsehits++; 121 PURGE(ncp); 122 continue; 123 } 124 /* Now that we know the vp's to be valid, is it ours ? */ 125 if (ncp->nc_dvp == dvp && 126 ncp->nc_nlen == cnp->cn_namelen && 127 !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 128 break; 129 } 130 131 /* We failed to find an entry */ 132 if (ncp == 0) { 133 nchstats.ncs_miss++; 134 return (0); 135 } 136 137 /* We don't want to have an entry, so dump it */ 138 if ((cnp->cn_flags & MAKEENTRY) == 0) { 139 nchstats.ncs_badhits++; 140 PURGE(ncp); 141 return (0); 142 } 143 144 /* We found a "positive" match, return the vnode */ 145 if (ncp->nc_vp) { 146 nchstats.ncs_goodhits++; 147 TOUCH(ncp); 148 *vpp = ncp->nc_vp; 149 return (-1); 150 } 151 152 /* We found a negative match, and want to create it, so purge */ 153 if (cnp->cn_nameiop == CREATE) { 154 nchstats.ncs_badhits++; 155 PURGE(ncp); 156 return (0); 157 } 158 159 /* We found a "negative" match, ENOENT notifies client of this match */ 160 nchstats.ncs_neghits++; 161 TOUCH(ncp); 162 return (ENOENT); 163 } 164 165 /* 166 * Add an entry to the cache. 167 */ 168 void 169 cache_enter(dvp, vp, cnp) 170 struct vnode *dvp; 171 struct vnode *vp; 172 struct componentname *cnp; 173 { 174 register struct namecache *ncp; 175 register struct nchashhead *ncpp; 176 177 if (!doingcache) 178 return; 179 180 #ifdef DIAGNOSTIC 181 if (cnp->cn_namelen > NCHNAMLEN) 182 panic("cache_enter: name too long"); 183 #endif 184 185 /* 186 * We allocate a new entry if we are less than the maximum 187 * allowed and the one at the front of the LRU list is in use. 188 * Otherwise we use the one at the front of the LRU list. 189 */ 190 if (numcache < desiredvnodes && 191 ((ncp = nclruhead.tqh_first) == NULL || 192 ncp->nc_hash.le_prev != 0)) { 193 /* Add one more entry */ 194 ncp = (struct namecache *) 195 malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 196 bzero((char *)ncp, sizeof *ncp); 197 numcache++; 198 } else if (ncp = nclruhead.tqh_first) { 199 /* reuse an old entry */ 200 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 201 if (ncp->nc_hash.le_prev != 0) { 202 LIST_REMOVE(ncp, nc_hash); 203 ncp->nc_hash.le_prev = 0; 204 } 205 } else { 206 /* give up */ 207 return; 208 } 209 210 /* fill in cache info, if vp is NULL this is a "negative" cache entry */ 211 ncp->nc_vp = vp; 212 if (vp) 213 ncp->nc_vpid = vp->v_id; 214 else 215 ncp->nc_vpid = 0; 216 ncp->nc_dvp = dvp; 217 ncp->nc_dvpid = dvp->v_id; 218 ncp->nc_nlen = cnp->cn_namelen; 219 bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 220 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 221 ncpp = NCHHASH(dvp, cnp); 222 LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 223 } 224 225 /* 226 * Name cache initialization, from vfs_init() when we are booting 227 */ 228 void 229 nchinit() 230 { 231 232 TAILQ_INIT(&nclruhead); 233 nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash); 234 } 235 236 /* 237 * Invalidate a all entries to particular vnode. 238 * 239 * We actually just increment the v_id, that will do it. The entries will 240 * be purged by lookup as they get found. If the v_id wraps around, we 241 * need to ditch the entire cache, to avoid confusion. No valid vnode will 242 * ever have (v_id == 0). 243 */ 244 void 245 cache_purge(vp) 246 struct vnode *vp; 247 { 248 struct namecache *ncp; 249 struct nchashhead *ncpp; 250 251 vp->v_id = ++nextvnodeid; 252 if (nextvnodeid != 0) 253 return; 254 for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 255 while (ncp = ncpp->lh_first) 256 PURGE(ncp); 257 } 258 vp->v_id = ++nextvnodeid; 259 } 260 261 /* 262 * Flush all entries referencing a particular filesystem. 263 * 264 * Since we need to check it anyway, we will flush all the invalid 265 * entriess at the same time. 266 */ 267 void 268 cache_purgevfs(mp) 269 struct mount *mp; 270 { 271 struct nchashhead *ncpp; 272 struct namecache *ncp, *nnp; 273 274 /* Scan hash tables for applicable entries */ 275 for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 276 for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) { 277 nnp = ncp->nc_hash.le_next; 278 if (ncp->nc_dvpid != ncp->nc_dvp->v_id || 279 (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id) || 280 ncp->nc_dvp->v_mount == mp) { 281 PURGE(ncp); 282 } 283 } 284 } 285 } 286