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
cache_lookup(dvp,vpp,cnp)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
cache_enter(dvp,vp,cnp)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
nchinit()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
cache_purge(vp)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
cache_purgevfs(mp)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