Line data Source code
1 : /* $OpenBSD: vfs_cache.c,v 1.57 2018/06/04 19:42:54 kn Exp $ */
2 : /* $NetBSD: vfs_cache.c,v 1.13 1996/02/04 02:18:09 christos Exp $ */
3 :
4 : /*
5 : * Copyright (c) 1989, 1993
6 : * The Regents of the University of California. All rights reserved.
7 : *
8 : * Redistribution and use in source and binary forms, with or without
9 : * modification, are permitted provided that the following conditions
10 : * are met:
11 : * 1. Redistributions of source code must retain the above copyright
12 : * notice, this list of conditions and the following disclaimer.
13 : * 2. Redistributions in binary form must reproduce the above copyright
14 : * notice, this list of conditions and the following disclaimer in the
15 : * documentation and/or other materials provided with the distribution.
16 : * 3. Neither the name of the University nor the names of its contributors
17 : * may be used to endorse or promote products derived from this software
18 : * without specific prior written permission.
19 : *
20 : * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 : * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 : * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 : * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 : * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 : * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 : * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 : * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 : * SUCH DAMAGE.
31 : *
32 : * @(#)vfs_cache.c 8.3 (Berkeley) 8/22/94
33 : */
34 :
35 : #include <sys/param.h>
36 : #include <sys/systm.h>
37 : #include <sys/time.h>
38 : #include <sys/mount.h>
39 : #include <sys/vnode.h>
40 : #include <sys/lock.h>
41 : #include <sys/namei.h>
42 : #include <sys/errno.h>
43 : #include <sys/pool.h>
44 :
45 : /*
46 : * TODO: namecache access should really be locked.
47 : */
48 :
49 : /*
50 : * For simplicity (and economy of storage), names longer than
51 : * a maximum length of NAMECACHE_MAXLEN are not cached; they occur
52 : * infrequently in any case, and are almost never of interest.
53 : *
54 : * Upon reaching the last segment of a path, if the reference
55 : * is for DELETE, or NOCACHE is set (rewrite), and the
56 : * name is located in the cache, it will be dropped.
57 : */
58 :
59 : /*
60 : * Structures associated with name caching.
61 : */
62 : long numcache; /* total number of cache entries allocated */
63 : long numneg; /* number of negative cache entries */
64 :
65 : TAILQ_HEAD(, namecache) nclruhead; /* Regular Entry LRU chain */
66 : TAILQ_HEAD(, namecache) nclruneghead; /* Negative Entry LRU chain */
67 : struct nchstats nchstats; /* cache effectiveness statistics */
68 :
69 : int doingcache = 1; /* 1 => enable the cache */
70 :
71 : struct pool nch_pool;
72 :
73 : void cache_zap(struct namecache *);
74 : u_long nextvnodeid;
75 :
76 : static inline int
77 0 : namecache_compare(const struct namecache *n1, const struct namecache *n2)
78 : {
79 0 : if (n1->nc_nlen == n2->nc_nlen)
80 0 : return (memcmp(n1->nc_name, n2->nc_name, n1->nc_nlen));
81 : else
82 0 : return (n1->nc_nlen - n2->nc_nlen);
83 0 : }
84 :
85 0 : RBT_PROTOTYPE(namecache_rb_cache, namecache, n_rbcache, namecache_compare);
86 0 : RBT_GENERATE(namecache_rb_cache, namecache, n_rbcache, namecache_compare);
87 :
88 : void
89 0 : cache_tree_init(struct namecache_rb_cache *tree)
90 : {
91 0 : RBT_INIT(namecache_rb_cache, tree);
92 0 : }
93 :
94 : /*
95 : * blow away a namecache entry
96 : */
97 : void
98 0 : cache_zap(struct namecache *ncp)
99 : {
100 : struct vnode *dvp = NULL;
101 :
102 0 : if (ncp->nc_vp != NULL) {
103 0 : TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
104 0 : numcache--;
105 0 : } else {
106 0 : TAILQ_REMOVE(&nclruneghead, ncp, nc_neg);
107 0 : numneg--;
108 : }
109 0 : if (ncp->nc_dvp) {
110 0 : RBT_REMOVE(namecache_rb_cache, &ncp->nc_dvp->v_nc_tree, ncp);
111 0 : if (RBT_EMPTY(namecache_rb_cache, &ncp->nc_dvp->v_nc_tree))
112 0 : dvp = ncp->nc_dvp;
113 : }
114 0 : if (ncp->nc_vp && (ncp->nc_vpid == ncp->nc_vp->v_id)) {
115 0 : if (ncp->nc_vp != ncp->nc_dvp &&
116 0 : ncp->nc_vp->v_type == VDIR &&
117 0 : (ncp->nc_nlen > 2 ||
118 0 : (ncp->nc_nlen > 1 &&
119 0 : ncp->nc_name[1] != '.') ||
120 0 : (ncp->nc_nlen > 0 &&
121 0 : ncp->nc_name[0] != '.'))) {
122 0 : TAILQ_REMOVE(&ncp->nc_vp->v_cache_dst, ncp, nc_me);
123 0 : }
124 : }
125 0 : pool_put(&nch_pool, ncp);
126 0 : if (dvp)
127 0 : vdrop(dvp);
128 0 : }
129 :
130 : /*
131 : * Look for a name in the cache.
132 : * dvp points to the directory to search. The componentname cnp holds
133 : * the information on the entry being sought, such as its length
134 : * and its name. If the lookup succeeds, vpp is set to point to the vnode
135 : * and an error of 0 is returned. If the lookup determines the name does
136 : * not exist (negative caching) an error of ENOENT is returned. If the
137 : * lookup fails, an error of -1 is returned.
138 : */
139 : int
140 0 : cache_lookup(struct vnode *dvp, struct vnode **vpp,
141 : struct componentname *cnp)
142 : {
143 : struct namecache *ncp;
144 0 : struct namecache n;
145 : struct vnode *vp;
146 : u_long vpid;
147 : int error;
148 :
149 0 : *vpp = NULL;
150 :
151 0 : if (!doingcache) {
152 0 : cnp->cn_flags &= ~MAKEENTRY;
153 0 : return (-1);
154 : }
155 0 : if (cnp->cn_namelen > NAMECACHE_MAXLEN) {
156 0 : nchstats.ncs_long++;
157 0 : cnp->cn_flags &= ~MAKEENTRY;
158 0 : return (-1);
159 : }
160 :
161 : /* lookup in directory vnode's redblack tree */
162 0 : n.nc_nlen = cnp->cn_namelen;
163 0 : memcpy(n.nc_name, cnp->cn_nameptr, n.nc_nlen);
164 0 : ncp = RBT_FIND(namecache_rb_cache, &dvp->v_nc_tree, &n);
165 :
166 0 : if (ncp == NULL) {
167 0 : nchstats.ncs_miss++;
168 0 : return (-1);
169 : }
170 0 : if ((cnp->cn_flags & MAKEENTRY) == 0) {
171 0 : nchstats.ncs_badhits++;
172 0 : goto remove;
173 0 : } else if (ncp->nc_vp == NULL) {
174 0 : if (cnp->cn_nameiop != CREATE ||
175 0 : (cnp->cn_flags & ISLASTCN) == 0) {
176 0 : nchstats.ncs_neghits++;
177 : /*
178 : * Move this slot to end of the negative LRU chain,
179 : */
180 0 : if (TAILQ_NEXT(ncp, nc_neg) != NULL) {
181 0 : TAILQ_REMOVE(&nclruneghead, ncp, nc_neg);
182 0 : TAILQ_INSERT_TAIL(&nclruneghead, ncp,
183 : nc_neg);
184 0 : }
185 0 : return (ENOENT);
186 : } else {
187 0 : nchstats.ncs_badhits++;
188 0 : goto remove;
189 : }
190 0 : } else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
191 0 : nchstats.ncs_falsehits++;
192 0 : goto remove;
193 : }
194 :
195 : /*
196 : * Move this slot to end of the regular LRU chain.
197 : */
198 0 : if (TAILQ_NEXT(ncp, nc_lru) != NULL) {
199 0 : TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
200 0 : TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
201 0 : }
202 :
203 0 : vp = ncp->nc_vp;
204 0 : vpid = vp->v_id;
205 0 : if (vp == dvp) { /* lookup on "." */
206 0 : vref(dvp);
207 : error = 0;
208 0 : } else if (cnp->cn_flags & ISDOTDOT) {
209 0 : VOP_UNLOCK(dvp);
210 0 : cnp->cn_flags |= PDIRUNLOCK;
211 0 : error = vget(vp, LK_EXCLUSIVE);
212 : /*
213 : * If the above vget() succeeded and both LOCKPARENT and
214 : * ISLASTCN is set, lock the directory vnode as well.
215 : */
216 0 : if (!error && (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) == 0) {
217 0 : if ((error = vn_lock(dvp, LK_EXCLUSIVE)) != 0) {
218 0 : vput(vp);
219 0 : return (error);
220 : }
221 0 : cnp->cn_flags &= ~PDIRUNLOCK;
222 0 : }
223 : } else {
224 0 : error = vget(vp, LK_EXCLUSIVE);
225 : /*
226 : * If the above vget() failed or either of LOCKPARENT or
227 : * ISLASTCN is set, unlock the directory vnode.
228 : */
229 0 : if (error || (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) {
230 0 : VOP_UNLOCK(dvp);
231 0 : cnp->cn_flags |= PDIRUNLOCK;
232 0 : }
233 : }
234 :
235 : /*
236 : * Check that the lock succeeded, and that the capability number did
237 : * not change while we were waiting for the lock.
238 : */
239 0 : if (error || vpid != vp->v_id) {
240 0 : if (!error) {
241 0 : vput(vp);
242 0 : nchstats.ncs_falsehits++;
243 0 : } else
244 0 : nchstats.ncs_badhits++;
245 : /*
246 : * The parent needs to be locked when we return to VOP_LOOKUP().
247 : * The `.' case here should be extremely rare (if it can happen
248 : * at all), so we don't bother optimizing out the unlock/relock.
249 : */
250 0 : if (vp == dvp || error ||
251 0 : (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) {
252 0 : if ((error = vn_lock(dvp, LK_EXCLUSIVE)) != 0)
253 0 : return (error);
254 0 : cnp->cn_flags &= ~PDIRUNLOCK;
255 0 : }
256 0 : return (-1);
257 : }
258 :
259 0 : nchstats.ncs_goodhits++;
260 0 : *vpp = vp;
261 0 : return (0);
262 :
263 : remove:
264 : /*
265 : * Last component and we are renaming or deleting,
266 : * the cache entry is invalid, or otherwise don't
267 : * want cache entry to exist.
268 : */
269 0 : cache_zap(ncp);
270 0 : return (-1);
271 0 : }
272 :
273 : /*
274 : * Scan cache looking for name of directory entry pointing at vp.
275 : *
276 : * Fill in dvpp.
277 : *
278 : * If bufp is non-NULL, also place the name in the buffer which starts
279 : * at bufp, immediately before *bpp, and move bpp backwards to point
280 : * at the start of it. (Yes, this is a little baroque, but it's done
281 : * this way to cater to the whims of getcwd).
282 : *
283 : * Returns 0 on success, -1 on cache miss, positive errno on failure.
284 : *
285 : * TODO: should we return *dvpp locked?
286 : */
287 :
288 : int
289 0 : cache_revlookup(struct vnode *vp, struct vnode **dvpp, char **bpp, char *bufp)
290 : {
291 : struct namecache *ncp;
292 : struct vnode *dvp = NULL;
293 : char *bp;
294 :
295 0 : if (!doingcache)
296 : goto out;
297 0 : TAILQ_FOREACH(ncp, &vp->v_cache_dst, nc_me) {
298 0 : dvp = ncp->nc_dvp;
299 0 : if (dvp && dvp != vp && ncp->nc_dvpid == dvp->v_id)
300 : goto found;
301 : }
302 : goto miss;
303 : found:
304 : #ifdef DIAGNOSTIC
305 0 : if (ncp->nc_nlen == 1 &&
306 0 : ncp->nc_name[0] == '.')
307 0 : panic("cache_revlookup: found entry for .");
308 0 : if (ncp->nc_nlen == 2 &&
309 0 : ncp->nc_name[0] == '.' &&
310 0 : ncp->nc_name[1] == '.')
311 0 : panic("cache_revlookup: found entry for ..");
312 : #endif
313 0 : nchstats.ncs_revhits++;
314 :
315 0 : if (bufp != NULL) {
316 0 : bp = *bpp;
317 0 : bp -= ncp->nc_nlen;
318 0 : if (bp <= bufp) {
319 0 : *dvpp = NULL;
320 0 : return (ERANGE);
321 : }
322 0 : memcpy(bp, ncp->nc_name, ncp->nc_nlen);
323 0 : *bpp = bp;
324 0 : }
325 :
326 0 : *dvpp = dvp;
327 :
328 : /*
329 : * XXX: Should we vget() here to have more
330 : * consistent semantics with cache_lookup()?
331 : */
332 0 : return (0);
333 :
334 : miss:
335 0 : nchstats.ncs_revmiss++;
336 : out:
337 0 : *dvpp = NULL;
338 0 : return (-1);
339 0 : }
340 :
341 : /*
342 : * Add an entry to the cache
343 : */
344 : void
345 0 : cache_enter(struct vnode *dvp, struct vnode *vp, struct componentname *cnp)
346 : {
347 : struct namecache *ncp, *lncp;
348 :
349 0 : if (!doingcache || cnp->cn_namelen > NAMECACHE_MAXLEN)
350 0 : return;
351 :
352 : /*
353 : * allocate, or recycle (free and allocate) an ncp.
354 : */
355 0 : if (numcache >= initialvnodes) {
356 0 : if ((ncp = TAILQ_FIRST(&nclruhead)) != NULL)
357 0 : cache_zap(ncp);
358 0 : else if ((ncp = TAILQ_FIRST(&nclruneghead)) != NULL)
359 0 : cache_zap(ncp);
360 : else
361 0 : panic("wtf? leak?");
362 : }
363 0 : ncp = pool_get(&nch_pool, PR_WAITOK|PR_ZERO);
364 :
365 : /* grab the vnode we just found */
366 0 : ncp->nc_vp = vp;
367 0 : if (vp)
368 0 : ncp->nc_vpid = vp->v_id;
369 :
370 : /* fill in cache info */
371 0 : ncp->nc_dvp = dvp;
372 0 : ncp->nc_dvpid = dvp->v_id;
373 0 : ncp->nc_nlen = cnp->cn_namelen;
374 0 : memcpy(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen);
375 0 : if (RBT_EMPTY(namecache_rb_cache, &dvp->v_nc_tree)) {
376 0 : vhold(dvp);
377 0 : }
378 0 : if ((lncp = RBT_INSERT(namecache_rb_cache, &dvp->v_nc_tree, ncp))
379 0 : != NULL) {
380 : /* someone has raced us and added a different entry
381 : * for the same vnode (different ncp) - we don't need
382 : * this entry, so free it and we are done.
383 : */
384 0 : pool_put(&nch_pool, ncp);
385 : /* we know now dvp->v_nc_tree is not empty, no need
386 : * to vdrop here
387 : */
388 0 : goto done;
389 : }
390 0 : if (vp) {
391 0 : TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
392 0 : numcache++;
393 : /* don't put . or .. in the reverse map */
394 0 : if (vp != dvp && vp->v_type == VDIR &&
395 0 : (ncp->nc_nlen > 2 ||
396 0 : (ncp->nc_nlen > 1 &&
397 0 : ncp->nc_name[1] != '.') ||
398 0 : (ncp->nc_nlen > 0 &&
399 0 : ncp->nc_name[0] != '.')))
400 0 : TAILQ_INSERT_TAIL(&vp->v_cache_dst, ncp,
401 : nc_me);
402 : } else {
403 0 : TAILQ_INSERT_TAIL(&nclruneghead, ncp, nc_neg);
404 0 : numneg++;
405 : }
406 0 : if (numneg > initialvnodes) {
407 0 : if ((ncp = TAILQ_FIRST(&nclruneghead))
408 0 : != NULL)
409 0 : cache_zap(ncp);
410 : }
411 : done:
412 0 : return;
413 0 : }
414 :
415 :
416 : /*
417 : * Name cache initialization, from vfs_init() when we are booting
418 : */
419 : void
420 0 : nchinit(void)
421 : {
422 0 : TAILQ_INIT(&nclruhead);
423 0 : TAILQ_INIT(&nclruneghead);
424 0 : pool_init(&nch_pool, sizeof(struct namecache), 0, IPL_NONE, PR_WAITOK,
425 : "nchpl", NULL);
426 0 : }
427 :
428 : /*
429 : * Cache flush, a particular vnode; called when a vnode is renamed to
430 : * hide entries that would now be invalid
431 : */
432 : void
433 0 : cache_purge(struct vnode *vp)
434 : {
435 : struct namecache *ncp;
436 :
437 : /* We should never have destinations cached for a non-VDIR vnode. */
438 0 : KASSERT(vp->v_type == VDIR || TAILQ_EMPTY(&vp->v_cache_dst));
439 :
440 0 : while ((ncp = TAILQ_FIRST(&vp->v_cache_dst)))
441 0 : cache_zap(ncp);
442 0 : while ((ncp = RBT_ROOT(namecache_rb_cache, &vp->v_nc_tree)))
443 0 : cache_zap(ncp);
444 :
445 : /* XXX this blows goats */
446 0 : vp->v_id = ++nextvnodeid;
447 0 : if (vp->v_id == 0)
448 0 : vp->v_id = ++nextvnodeid;
449 0 : }
450 :
451 : /*
452 : * Cache flush, a whole filesystem; called when filesys is umounted to
453 : * remove entries that would now be invalid
454 : */
455 : void
456 0 : cache_purgevfs(struct mount *mp)
457 : {
458 : struct namecache *ncp, *nxtcp;
459 :
460 : /* whack the regular entries */
461 0 : TAILQ_FOREACH_SAFE(ncp, &nclruhead, nc_lru, nxtcp) {
462 0 : if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp)
463 : continue;
464 : /* free the resources we had */
465 0 : cache_zap(ncp);
466 0 : }
467 : /* whack the negative entries */
468 0 : TAILQ_FOREACH_SAFE(ncp, &nclruneghead, nc_neg, nxtcp) {
469 0 : if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp)
470 : continue;
471 : /* free the resources we had */
472 0 : cache_zap(ncp);
473 0 : }
474 0 : }
|
