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.5 (Berkeley) 03/22/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 /* 160 * We found a "negative" match, ENOENT notifies client of this match. 161 * The nc_vpid field records whether this is a whiteout. 162 */ 163 nchstats.ncs_neghits++; 164 TOUCH(ncp); 165 cnp->cn_flags |= ncp->nc_vpid; 166 return (ENOENT); 167 } 168 169 /* 170 * Add an entry to the cache. 171 */ 172 void 173 cache_enter(dvp, vp, cnp) 174 struct vnode *dvp; 175 struct vnode *vp; 176 struct componentname *cnp; 177 { 178 register struct namecache *ncp; 179 register struct nchashhead *ncpp; 180 181 if (!doingcache) 182 return; 183 184 #ifdef DIAGNOSTIC 185 if (cnp->cn_namelen > NCHNAMLEN) 186 panic("cache_enter: name too long"); 187 #endif 188 189 /* 190 * We allocate a new entry if we are less than the maximum 191 * allowed and the one at the front of the LRU list is in use. 192 * Otherwise we use the one at the front of the LRU list. 193 */ 194 if (numcache < desiredvnodes && 195 ((ncp = nclruhead.tqh_first) == NULL || 196 ncp->nc_hash.le_prev != 0)) { 197 /* Add one more entry */ 198 ncp = (struct namecache *) 199 malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 200 bzero((char *)ncp, sizeof *ncp); 201 numcache++; 202 } else if (ncp = nclruhead.tqh_first) { 203 /* reuse an old entry */ 204 TAILQ_REMOVE(&nclruhead, ncp, nc_lru); 205 if (ncp->nc_hash.le_prev != 0) { 206 LIST_REMOVE(ncp, nc_hash); 207 ncp->nc_hash.le_prev = 0; 208 } 209 } else { 210 /* give up */ 211 return; 212 } 213 214 /* 215 * Fill in cache info, if vp is NULL this is a "negative" cache entry. 216 * For negative entries, we have to record whether it is a whiteout. 217 * the whiteout flag is stored in the nc_vpid field which is 218 * otherwise unused. 219 */ 220 ncp->nc_vp = vp; 221 if (vp) 222 ncp->nc_vpid = vp->v_id; 223 else 224 ncp->nc_vpid = cnp->cn_flags & ISWHITEOUT; 225 ncp->nc_dvp = dvp; 226 ncp->nc_dvpid = dvp->v_id; 227 ncp->nc_nlen = cnp->cn_namelen; 228 bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 229 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); 230 ncpp = NCHHASH(dvp, cnp); 231 LIST_INSERT_HEAD(ncpp, ncp, nc_hash); 232 } 233 234 /* 235 * Name cache initialization, from vfs_init() when we are booting 236 */ 237 void 238 nchinit() 239 { 240 241 TAILQ_INIT(&nclruhead); 242 nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash); 243 } 244 245 /* 246 * Invalidate a all entries to particular vnode. 247 * 248 * We actually just increment the v_id, that will do it. The entries will 249 * be purged by lookup as they get found. If the v_id wraps around, we 250 * need to ditch the entire cache, to avoid confusion. No valid vnode will 251 * ever have (v_id == 0). 252 */ 253 void 254 cache_purge(vp) 255 struct vnode *vp; 256 { 257 struct namecache *ncp; 258 struct nchashhead *ncpp; 259 260 vp->v_id = ++nextvnodeid; 261 if (nextvnodeid != 0) 262 return; 263 for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 264 while (ncp = ncpp->lh_first) 265 PURGE(ncp); 266 } 267 vp->v_id = ++nextvnodeid; 268 } 269 270 /* 271 * Flush all entries referencing a particular filesystem. 272 * 273 * Since we need to check it anyway, we will flush all the invalid 274 * entriess at the same time. 275 */ 276 void 277 cache_purgevfs(mp) 278 struct mount *mp; 279 { 280 struct nchashhead *ncpp; 281 struct namecache *ncp, *nnp; 282 283 /* Scan hash tables for applicable entries */ 284 for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 285 for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) { 286 nnp = ncp->nc_hash.le_next; 287 if (ncp->nc_dvpid != ncp->nc_dvp->v_id || 288 (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id) || 289 ncp->nc_dvp->v_mount == mp) { 290 PURGE(ncp); 291 } 292 } 293 } 294 } 295