vfs_cache.c revision 1.115 1 1.115 riastrad /* $NetBSD: vfs_cache.c,v 1.115 2017/03/18 20:00:10 riastradh Exp $ */
2 1.73 ad
3 1.73 ad /*-
4 1.73 ad * Copyright (c) 2008 The NetBSD Foundation, Inc.
5 1.73 ad * All rights reserved.
6 1.73 ad *
7 1.73 ad * Redistribution and use in source and binary forms, with or without
8 1.73 ad * modification, are permitted provided that the following conditions
9 1.73 ad * are met:
10 1.73 ad * 1. Redistributions of source code must retain the above copyright
11 1.73 ad * notice, this list of conditions and the following disclaimer.
12 1.73 ad * 2. Redistributions in binary form must reproduce the above copyright
13 1.73 ad * notice, this list of conditions and the following disclaimer in the
14 1.73 ad * documentation and/or other materials provided with the distribution.
15 1.73 ad *
16 1.73 ad * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
17 1.73 ad * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
18 1.73 ad * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19 1.73 ad * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
20 1.73 ad * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 1.73 ad * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 1.73 ad * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 1.73 ad * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 1.73 ad * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 1.73 ad * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 1.73 ad * POSSIBILITY OF SUCH DAMAGE.
27 1.73 ad */
28 1.6 cgd
29 1.1 cgd /*
30 1.5 mycroft * Copyright (c) 1989, 1993
31 1.5 mycroft * The Regents of the University of California. All rights reserved.
32 1.1 cgd *
33 1.1 cgd * Redistribution and use in source and binary forms, with or without
34 1.1 cgd * modification, are permitted provided that the following conditions
35 1.1 cgd * are met:
36 1.1 cgd * 1. Redistributions of source code must retain the above copyright
37 1.1 cgd * notice, this list of conditions and the following disclaimer.
38 1.1 cgd * 2. Redistributions in binary form must reproduce the above copyright
39 1.1 cgd * notice, this list of conditions and the following disclaimer in the
40 1.1 cgd * documentation and/or other materials provided with the distribution.
41 1.51 agc * 3. Neither the name of the University nor the names of its contributors
42 1.1 cgd * may be used to endorse or promote products derived from this software
43 1.1 cgd * without specific prior written permission.
44 1.1 cgd *
45 1.1 cgd * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
46 1.1 cgd * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
47 1.1 cgd * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
48 1.1 cgd * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
49 1.1 cgd * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
50 1.1 cgd * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
51 1.1 cgd * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
52 1.1 cgd * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
53 1.1 cgd * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
54 1.1 cgd * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
55 1.1 cgd * SUCH DAMAGE.
56 1.1 cgd *
57 1.10 mycroft * @(#)vfs_cache.c 8.3 (Berkeley) 8/22/94
58 1.1 cgd */
59 1.32 lukem
60 1.32 lukem #include <sys/cdefs.h>
61 1.115 riastrad __KERNEL_RCSID(0, "$NetBSD: vfs_cache.c,v 1.115 2017/03/18 20:00:10 riastradh Exp $");
62 1.1 cgd
63 1.107 pooka #ifdef _KERNEL_OPT
64 1.28 chs #include "opt_ddb.h"
65 1.115 riastrad #include "opt_dtrace.h"
66 1.29 fvdl #include "opt_revcache.h"
67 1.107 pooka #endif
68 1.28 chs
69 1.4 mycroft #include <sys/param.h>
70 1.115 riastrad #include <sys/atomic.h>
71 1.115 riastrad #include <sys/cpu.h>
72 1.115 riastrad #include <sys/errno.h>
73 1.115 riastrad #include <sys/evcnt.h>
74 1.115 riastrad #include <sys/kernel.h>
75 1.115 riastrad #include <sys/kthread.h>
76 1.4 mycroft #include <sys/mount.h>
77 1.115 riastrad #include <sys/mutex.h>
78 1.4 mycroft #include <sys/namei.h>
79 1.18 thorpej #include <sys/pool.h>
80 1.108 christos #include <sys/sdt.h>
81 1.115 riastrad #include <sys/sysctl.h>
82 1.115 riastrad #include <sys/systm.h>
83 1.115 riastrad #include <sys/time.h>
84 1.115 riastrad #include <sys/vnode_impl.h>
85 1.1 cgd
86 1.66 christos #define NAMECACHE_ENTER_REVERSE
87 1.1 cgd /*
88 1.1 cgd * Name caching works as follows:
89 1.1 cgd *
90 1.1 cgd * Names found by directory scans are retained in a cache
91 1.1 cgd * for future reference. It is managed LRU, so frequently
92 1.1 cgd * used names will hang around. Cache is indexed by hash value
93 1.20 jdolecek * obtained from (dvp, name) where dvp refers to the directory
94 1.1 cgd * containing name.
95 1.1 cgd *
96 1.1 cgd * For simplicity (and economy of storage), names longer than
97 1.1 cgd * a maximum length of NCHNAMLEN are not cached; they occur
98 1.1 cgd * infrequently in any case, and are almost never of interest.
99 1.1 cgd *
100 1.1 cgd * Upon reaching the last segment of a path, if the reference
101 1.1 cgd * is for DELETE, or NOCACHE is set (rewrite), and the
102 1.1 cgd * name is located in the cache, it will be dropped.
103 1.1 cgd */
104 1.1 cgd
105 1.1 cgd /*
106 1.102 dennis * The locking in this subsystem works as follows:
107 1.102 dennis *
108 1.102 dennis * When an entry is added to the cache, via cache_enter(),
109 1.102 dennis * namecache_lock is taken to exclude other writers. The new
110 1.102 dennis * entry is added to the hash list in a way which permits
111 1.102 dennis * concurrent lookups and invalidations in the cache done on
112 1.102 dennis * other CPUs to continue in parallel.
113 1.102 dennis *
114 1.102 dennis * When a lookup is done in the cache, via cache_lookup() or
115 1.102 dennis * cache_lookup_raw(), the per-cpu lock below is taken. This
116 1.102 dennis * protects calls to cache_lookup_entry() and cache_invalidate()
117 1.102 dennis * against cache_reclaim() but allows lookups to continue in
118 1.102 dennis * parallel with cache_enter().
119 1.102 dennis *
120 1.102 dennis * cache_revlookup() takes namecache_lock to exclude cache_enter()
121 1.102 dennis * and cache_reclaim() since the list it operates on is not
122 1.102 dennis * maintained to allow concurrent reads.
123 1.102 dennis *
124 1.102 dennis * When cache_reclaim() is called namecache_lock is held to hold
125 1.102 dennis * off calls to cache_enter()/cache_revlookup() and each of the
126 1.102 dennis * per-cpu locks is taken to hold off lookups. Holding all these
127 1.102 dennis * locks essentially idles the subsystem, ensuring there are no
128 1.102 dennis * concurrent references to the cache entries being freed.
129 1.102 dennis *
130 1.103 dennis * 32 bit per-cpu statistic counters (struct nchstats_percpu) are
131 1.103 dennis * incremented when the operations they count are performed while
132 1.103 dennis * running on the corresponding CPU. Frequently individual counters
133 1.103 dennis * are incremented while holding a lock (either a per-cpu lock or
134 1.103 dennis * namecache_lock) sufficient to preclude concurrent increments
135 1.103 dennis * being done to the same counter, so non-atomic increments are
136 1.103 dennis * done using the COUNT() macro. Counters which are incremented
137 1.103 dennis * when one of these locks is not held use the COUNT_UNL() macro
138 1.103 dennis * instead. COUNT_UNL() could be defined to do atomic increments
139 1.103 dennis * but currently just does what COUNT() does, on the theory that
140 1.103 dennis * it is unlikely the non-atomic increment will be interrupted
141 1.103 dennis * by something on the same CPU that increments the same counter,
142 1.103 dennis * but even if it does happen the consequences aren't serious.
143 1.103 dennis *
144 1.103 dennis * N.B.: Attempting to protect COUNT_UNL() increments by taking
145 1.103 dennis * a per-cpu lock in the namecache_count_*() functions causes
146 1.103 dennis * a deadlock. Don't do that, use atomic increments instead if
147 1.103 dennis * the imperfections here bug you.
148 1.103 dennis *
149 1.103 dennis * The 64 bit system-wide statistic counts (struct nchstats) are
150 1.103 dennis * maintained by sampling the per-cpu counters periodically, adding
151 1.103 dennis * in the deltas since the last samples and recording the current
152 1.103 dennis * samples to use to compute the next delta. The sampling is done
153 1.103 dennis * as a side effect of cache_reclaim() which is run periodically,
154 1.103 dennis * for its own purposes, often enough to avoid overflow of the 32
155 1.103 dennis * bit counters. While sampling in this fashion requires no locking
156 1.103 dennis * it is never-the-less done only after all locks have been taken by
157 1.103 dennis * cache_reclaim() to allow cache_stat_sysctl() to hold off
158 1.103 dennis * cache_reclaim() with minimal locking.
159 1.103 dennis *
160 1.103 dennis * cache_stat_sysctl() takes its CPU's per-cpu lock to hold off
161 1.103 dennis * cache_reclaim() so that it can copy the subsystem total stats
162 1.103 dennis * without them being concurrently modified. If CACHE_STATS_CURRENT
163 1.103 dennis * is defined it also harvests the per-cpu increments into the total,
164 1.103 dennis * which again requires cache_reclaim() to be held off.
165 1.102 dennis *
166 1.103 dennis * The per-cpu data (a lock and the per-cpu stats structures)
167 1.103 dennis * are defined next.
168 1.77 ad */
169 1.103 dennis struct nchstats_percpu _NAMEI_CACHE_STATS(uint32_t);
170 1.103 dennis
171 1.77 ad struct nchcpu {
172 1.103 dennis kmutex_t cpu_lock;
173 1.103 dennis struct nchstats_percpu cpu_stats;
174 1.103 dennis /* XXX maybe __cacheline_aligned would improve this? */
175 1.103 dennis struct nchstats_percpu cpu_stats_last; /* from last sample */
176 1.77 ad };
177 1.77 ad
178 1.77 ad /*
179 1.90 dholland * The type for the hash code. While the hash function generates a
180 1.90 dholland * u32, the hash code has historically been passed around as a u_long,
181 1.90 dholland * and the value is modified by xor'ing a uintptr_t, so it's not
182 1.90 dholland * entirely clear what the best type is. For now I'll leave it
183 1.90 dholland * unchanged as u_long.
184 1.90 dholland */
185 1.90 dholland
186 1.90 dholland typedef u_long nchash_t;
187 1.90 dholland
188 1.90 dholland /*
189 1.1 cgd * Structures associated with name cacheing.
190 1.1 cgd */
191 1.89 rmind
192 1.89 rmind static kmutex_t *namecache_lock __read_mostly;
193 1.89 rmind static pool_cache_t namecache_cache __read_mostly;
194 1.89 rmind static TAILQ_HEAD(, namecache) nclruhead __cacheline_aligned;
195 1.89 rmind
196 1.89 rmind static LIST_HEAD(nchashhead, namecache) *nchashtbl __read_mostly;
197 1.89 rmind static u_long nchash __read_mostly;
198 1.89 rmind
199 1.90 dholland #define NCHASH2(hash, dvp) \
200 1.90 dholland (((hash) ^ ((uintptr_t)(dvp) >> 3)) & nchash)
201 1.19 sommerfe
202 1.89 rmind static LIST_HEAD(ncvhashhead, namecache) *ncvhashtbl __read_mostly;
203 1.89 rmind static u_long ncvhash __read_mostly;
204 1.89 rmind
205 1.48 yamt #define NCVHASH(vp) (((uintptr_t)(vp) >> 3) & ncvhash)
206 1.19 sommerfe
207 1.89 rmind /* Number of cache entries allocated. */
208 1.89 rmind static long numcache __cacheline_aligned;
209 1.73 ad
210 1.89 rmind /* Garbage collection queue and number of entries pending in it. */
211 1.89 rmind static void *cache_gcqueue;
212 1.89 rmind static u_int cache_gcpend;
213 1.89 rmind
214 1.103 dennis /* Cache effectiveness statistics. This holds total from per-cpu stats */
215 1.89 rmind struct nchstats nchstats __cacheline_aligned;
216 1.103 dennis
217 1.103 dennis /*
218 1.103 dennis * Macros to count an event, update the central stats with per-cpu
219 1.103 dennis * values and add current per-cpu increments to the subsystem total
220 1.103 dennis * last collected by cache_reclaim().
221 1.103 dennis */
222 1.103 dennis #define CACHE_STATS_CURRENT /* nothing */
223 1.103 dennis
224 1.103 dennis #define COUNT(cpup, f) ((cpup)->cpu_stats.f++)
225 1.103 dennis
226 1.103 dennis #define UPDATE(cpup, f) do { \
227 1.103 dennis struct nchcpu *Xcpup = (cpup); \
228 1.103 dennis uint32_t Xcnt = (volatile uint32_t) Xcpup->cpu_stats.f; \
229 1.103 dennis nchstats.f += Xcnt - Xcpup->cpu_stats_last.f; \
230 1.103 dennis Xcpup->cpu_stats_last.f = Xcnt; \
231 1.103 dennis } while (/* CONSTCOND */ 0)
232 1.103 dennis
233 1.103 dennis #define ADD(stats, cpup, f) do { \
234 1.103 dennis struct nchcpu *Xcpup = (cpup); \
235 1.103 dennis stats.f += Xcpup->cpu_stats.f - Xcpup->cpu_stats_last.f; \
236 1.103 dennis } while (/* CONSTCOND */ 0)
237 1.103 dennis
238 1.103 dennis /* Do unlocked stats the same way. Use a different name to allow mind changes */
239 1.103 dennis #define COUNT_UNL(cpup, f) COUNT((cpup), f)
240 1.38 thorpej
241 1.89 rmind static const int cache_lowat = 95;
242 1.89 rmind static const int cache_hiwat = 98;
243 1.89 rmind static const int cache_hottime = 5; /* number of seconds */
244 1.89 rmind static int doingcache = 1; /* 1 => enable the cache */
245 1.1 cgd
246 1.73 ad static struct evcnt cache_ev_scan;
247 1.73 ad static struct evcnt cache_ev_gc;
248 1.73 ad static struct evcnt cache_ev_over;
249 1.73 ad static struct evcnt cache_ev_under;
250 1.73 ad static struct evcnt cache_ev_forced;
251 1.73 ad
252 1.73 ad static void cache_invalidate(struct namecache *);
253 1.89 rmind static struct namecache *cache_lookup_entry(
254 1.91 dholland const struct vnode *, const char *, size_t);
255 1.73 ad static void cache_thread(void *);
256 1.73 ad static void cache_invalidate(struct namecache *);
257 1.73 ad static void cache_disassociate(struct namecache *);
258 1.73 ad static void cache_reclaim(void);
259 1.73 ad static int cache_ctor(void *, void *, int);
260 1.73 ad static void cache_dtor(void *, void *);
261 1.46 yamt
262 1.104 pooka static struct sysctllog *sysctllog;
263 1.104 pooka static void sysctl_cache_stat_setup(void);
264 1.104 pooka
265 1.108 christos SDT_PROVIDER_DEFINE(vfs);
266 1.108 christos
267 1.108 christos SDT_PROBE_DEFINE1(vfs, namecache, invalidate, done, "struct vnode *");
268 1.108 christos SDT_PROBE_DEFINE1(vfs, namecache, purge, parents, "struct vnode *");
269 1.108 christos SDT_PROBE_DEFINE1(vfs, namecache, purge, children, "struct vnode *");
270 1.108 christos SDT_PROBE_DEFINE2(vfs, namecache, purge, name, "char *", "size_t");
271 1.108 christos SDT_PROBE_DEFINE1(vfs, namecache, purge, vfs, "struct mount *");
272 1.108 christos SDT_PROBE_DEFINE3(vfs, namecache, lookup, hit, "struct vnode *",
273 1.108 christos "char *", "size_t");
274 1.108 christos SDT_PROBE_DEFINE3(vfs, namecache, lookup, miss, "struct vnode *",
275 1.108 christos "char *", "size_t");
276 1.108 christos SDT_PROBE_DEFINE3(vfs, namecache, lookup, toolong, "struct vnode *",
277 1.108 christos "char *", "size_t");
278 1.108 christos SDT_PROBE_DEFINE2(vfs, namecache, revlookup, success, "struct vnode *",
279 1.108 christos "struct vnode *");
280 1.108 christos SDT_PROBE_DEFINE2(vfs, namecache, revlookup, fail, "struct vnode *",
281 1.108 christos "int");
282 1.108 christos SDT_PROBE_DEFINE2(vfs, namecache, prune, done, "int", "int");
283 1.108 christos SDT_PROBE_DEFINE3(vfs, namecache, enter, toolong, "struct vnode *",
284 1.108 christos "char *", "size_t");
285 1.108 christos SDT_PROBE_DEFINE3(vfs, namecache, enter, done, "struct vnode *",
286 1.108 christos "char *", "size_t");
287 1.108 christos
288 1.73 ad /*
289 1.90 dholland * Compute the hash for an entry.
290 1.90 dholland *
291 1.90 dholland * (This is for now a wrapper around namei_hash, whose interface is
292 1.90 dholland * for the time being slightly inconvenient.)
293 1.90 dholland */
294 1.90 dholland static nchash_t
295 1.91 dholland cache_hash(const char *name, size_t namelen)
296 1.90 dholland {
297 1.90 dholland const char *endptr;
298 1.90 dholland
299 1.91 dholland endptr = name + namelen;
300 1.91 dholland return namei_hash(name, &endptr);
301 1.90 dholland }
302 1.90 dholland
303 1.90 dholland /*
304 1.73 ad * Invalidate a cache entry and enqueue it for garbage collection.
305 1.103 dennis * The caller needs to hold namecache_lock or a per-cpu lock to hold
306 1.103 dennis * off cache_reclaim().
307 1.73 ad */
308 1.46 yamt static void
309 1.73 ad cache_invalidate(struct namecache *ncp)
310 1.46 yamt {
311 1.73 ad void *head;
312 1.46 yamt
313 1.73 ad KASSERT(mutex_owned(&ncp->nc_lock));
314 1.46 yamt
315 1.73 ad if (ncp->nc_dvp != NULL) {
316 1.108 christos SDT_PROBE(vfs, namecache, invalidate, done, ncp->nc_dvp,
317 1.108 christos 0, 0, 0, 0);
318 1.108 christos
319 1.73 ad ncp->nc_vp = NULL;
320 1.73 ad ncp->nc_dvp = NULL;
321 1.73 ad do {
322 1.73 ad head = cache_gcqueue;
323 1.73 ad ncp->nc_gcqueue = head;
324 1.73 ad } while (atomic_cas_ptr(&cache_gcqueue, head, ncp) != head);
325 1.73 ad atomic_inc_uint(&cache_gcpend);
326 1.73 ad }
327 1.73 ad }
328 1.46 yamt
329 1.73 ad /*
330 1.73 ad * Disassociate a namecache entry from any vnodes it is attached to,
331 1.73 ad * and remove from the global LRU list.
332 1.73 ad */
333 1.73 ad static void
334 1.73 ad cache_disassociate(struct namecache *ncp)
335 1.73 ad {
336 1.73 ad
337 1.73 ad KASSERT(mutex_owned(namecache_lock));
338 1.73 ad KASSERT(ncp->nc_dvp == NULL);
339 1.73 ad
340 1.73 ad if (ncp->nc_lru.tqe_prev != NULL) {
341 1.73 ad TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
342 1.73 ad ncp->nc_lru.tqe_prev = NULL;
343 1.46 yamt }
344 1.46 yamt if (ncp->nc_vhash.le_prev != NULL) {
345 1.46 yamt LIST_REMOVE(ncp, nc_vhash);
346 1.46 yamt ncp->nc_vhash.le_prev = NULL;
347 1.46 yamt }
348 1.46 yamt if (ncp->nc_vlist.le_prev != NULL) {
349 1.46 yamt LIST_REMOVE(ncp, nc_vlist);
350 1.46 yamt ncp->nc_vlist.le_prev = NULL;
351 1.46 yamt }
352 1.46 yamt if (ncp->nc_dvlist.le_prev != NULL) {
353 1.46 yamt LIST_REMOVE(ncp, nc_dvlist);
354 1.46 yamt ncp->nc_dvlist.le_prev = NULL;
355 1.46 yamt }
356 1.46 yamt }
357 1.46 yamt
358 1.73 ad /*
359 1.73 ad * Lock all CPUs to prevent any cache lookup activity. Conceptually,
360 1.73 ad * this locks out all "readers".
361 1.73 ad */
362 1.46 yamt static void
363 1.73 ad cache_lock_cpus(void)
364 1.46 yamt {
365 1.73 ad CPU_INFO_ITERATOR cii;
366 1.73 ad struct cpu_info *ci;
367 1.77 ad struct nchcpu *cpup;
368 1.46 yamt
369 1.103 dennis /*
370 1.103 dennis * Lock out all CPUs first, then harvest per-cpu stats. This
371 1.103 dennis * is probably not quite as cache-efficient as doing the lock
372 1.103 dennis * and harvest at the same time, but allows cache_stat_sysctl()
373 1.103 dennis * to make do with a per-cpu lock.
374 1.103 dennis */
375 1.73 ad for (CPU_INFO_FOREACH(cii, ci)) {
376 1.77 ad cpup = ci->ci_data.cpu_nch;
377 1.77 ad mutex_enter(&cpup->cpu_lock);
378 1.103 dennis }
379 1.103 dennis for (CPU_INFO_FOREACH(cii, ci)) {
380 1.103 dennis cpup = ci->ci_data.cpu_nch;
381 1.103 dennis UPDATE(cpup, ncs_goodhits);
382 1.103 dennis UPDATE(cpup, ncs_neghits);
383 1.103 dennis UPDATE(cpup, ncs_badhits);
384 1.103 dennis UPDATE(cpup, ncs_falsehits);
385 1.103 dennis UPDATE(cpup, ncs_miss);
386 1.103 dennis UPDATE(cpup, ncs_long);
387 1.103 dennis UPDATE(cpup, ncs_pass2);
388 1.103 dennis UPDATE(cpup, ncs_2passes);
389 1.103 dennis UPDATE(cpup, ncs_revhits);
390 1.103 dennis UPDATE(cpup, ncs_revmiss);
391 1.73 ad }
392 1.46 yamt }
393 1.46 yamt
394 1.73 ad /*
395 1.73 ad * Release all CPU locks.
396 1.73 ad */
397 1.73 ad static void
398 1.73 ad cache_unlock_cpus(void)
399 1.73 ad {
400 1.73 ad CPU_INFO_ITERATOR cii;
401 1.73 ad struct cpu_info *ci;
402 1.77 ad struct nchcpu *cpup;
403 1.73 ad
404 1.73 ad for (CPU_INFO_FOREACH(cii, ci)) {
405 1.77 ad cpup = ci->ci_data.cpu_nch;
406 1.77 ad mutex_exit(&cpup->cpu_lock);
407 1.73 ad }
408 1.73 ad }
409 1.73 ad
410 1.73 ad /*
411 1.103 dennis * Find a single cache entry and return it locked.
412 1.103 dennis * The caller needs to hold namecache_lock or a per-cpu lock to hold
413 1.103 dennis * off cache_reclaim().
414 1.73 ad */
415 1.73 ad static struct namecache *
416 1.91 dholland cache_lookup_entry(const struct vnode *dvp, const char *name, size_t namelen)
417 1.55 yamt {
418 1.55 yamt struct nchashhead *ncpp;
419 1.55 yamt struct namecache *ncp;
420 1.90 dholland nchash_t hash;
421 1.55 yamt
422 1.84 yamt KASSERT(dvp != NULL);
423 1.91 dholland hash = cache_hash(name, namelen);
424 1.90 dholland ncpp = &nchashtbl[NCHASH2(hash, dvp)];
425 1.55 yamt
426 1.55 yamt LIST_FOREACH(ncp, ncpp, nc_hash) {
427 1.105 dennis membar_datadep_consumer(); /* for Alpha... */
428 1.73 ad if (ncp->nc_dvp != dvp ||
429 1.91 dholland ncp->nc_nlen != namelen ||
430 1.91 dholland memcmp(ncp->nc_name, name, (u_int)ncp->nc_nlen))
431 1.73 ad continue;
432 1.73 ad mutex_enter(&ncp->nc_lock);
433 1.77 ad if (__predict_true(ncp->nc_dvp == dvp)) {
434 1.73 ad ncp->nc_hittime = hardclock_ticks;
435 1.108 christos SDT_PROBE(vfs, namecache, lookup, hit, dvp,
436 1.108 christos name, namelen, 0, 0);
437 1.73 ad return ncp;
438 1.73 ad }
439 1.73 ad /* Raced: entry has been nullified. */
440 1.73 ad mutex_exit(&ncp->nc_lock);
441 1.55 yamt }
442 1.55 yamt
443 1.108 christos SDT_PROBE(vfs, namecache, lookup, miss, dvp,
444 1.108 christos name, namelen, 0, 0);
445 1.73 ad return NULL;
446 1.55 yamt }
447 1.55 yamt
448 1.1 cgd /*
449 1.1 cgd * Look for a the name in the cache. We don't do this
450 1.1 cgd * if the segment name is long, simply so the cache can avoid
451 1.1 cgd * holding long names (which would either waste space, or
452 1.1 cgd * add greatly to the complexity).
453 1.1 cgd *
454 1.90 dholland * Lookup is called with DVP pointing to the directory to search,
455 1.90 dholland * and CNP providing the name of the entry being sought: cn_nameptr
456 1.90 dholland * is the name, cn_namelen is its length, and cn_flags is the flags
457 1.90 dholland * word from the namei operation.
458 1.90 dholland *
459 1.90 dholland * DVP must be locked.
460 1.90 dholland *
461 1.90 dholland * There are three possible non-error return states:
462 1.90 dholland * 1. Nothing was found in the cache. Nothing is known about
463 1.90 dholland * the requested name.
464 1.90 dholland * 2. A negative entry was found in the cache, meaning that the
465 1.90 dholland * requested name definitely does not exist.
466 1.90 dholland * 3. A positive entry was found in the cache, meaning that the
467 1.90 dholland * requested name does exist and that we are providing the
468 1.90 dholland * vnode.
469 1.90 dholland * In these cases the results are:
470 1.90 dholland * 1. 0 returned; VN is set to NULL.
471 1.90 dholland * 2. 1 returned; VN is set to NULL.
472 1.90 dholland * 3. 1 returned; VN is set to the vnode found.
473 1.90 dholland *
474 1.90 dholland * The additional result argument ISWHT is set to zero, unless a
475 1.90 dholland * negative entry is found that was entered as a whiteout, in which
476 1.90 dholland * case ISWHT is set to one.
477 1.90 dholland *
478 1.90 dholland * The ISWHT_RET argument pointer may be null. In this case an
479 1.90 dholland * assertion is made that the whiteout flag is not set. File systems
480 1.90 dholland * that do not support whiteouts can/should do this.
481 1.90 dholland *
482 1.90 dholland * Filesystems that do support whiteouts should add ISWHITEOUT to
483 1.90 dholland * cnp->cn_flags if ISWHT comes back nonzero.
484 1.90 dholland *
485 1.90 dholland * When a vnode is returned, it is locked, as per the vnode lookup
486 1.90 dholland * locking protocol.
487 1.90 dholland *
488 1.90 dholland * There is no way for this function to fail, in the sense of
489 1.90 dholland * generating an error that requires aborting the namei operation.
490 1.90 dholland *
491 1.90 dholland * (Prior to October 2012, this function returned an integer status,
492 1.90 dholland * and a vnode, and mucked with the flags word in CNP for whiteouts.
493 1.90 dholland * The integer status was -1 for "nothing found", ENOENT for "a
494 1.90 dholland * negative entry found", 0 for "a positive entry found", and possibly
495 1.90 dholland * other errors, and the value of VN might or might not have been set
496 1.90 dholland * depending on what error occurred.)
497 1.1 cgd */
498 1.113 riastrad bool
499 1.91 dholland cache_lookup(struct vnode *dvp, const char *name, size_t namelen,
500 1.91 dholland uint32_t nameiop, uint32_t cnflags,
501 1.90 dholland int *iswht_ret, struct vnode **vn_ret)
502 1.1 cgd {
503 1.23 augustss struct namecache *ncp;
504 1.20 jdolecek struct vnode *vp;
505 1.77 ad struct nchcpu *cpup;
506 1.113 riastrad int error;
507 1.113 riastrad bool hit;
508 1.103 dennis
509 1.1 cgd
510 1.90 dholland /* Establish default result values */
511 1.90 dholland if (iswht_ret != NULL) {
512 1.90 dholland *iswht_ret = 0;
513 1.90 dholland }
514 1.90 dholland *vn_ret = NULL;
515 1.90 dholland
516 1.77 ad if (__predict_false(!doingcache)) {
517 1.113 riastrad return false;
518 1.8 cgd }
519 1.39 pk
520 1.77 ad cpup = curcpu()->ci_data.cpu_nch;
521 1.102 dennis mutex_enter(&cpup->cpu_lock);
522 1.91 dholland if (__predict_false(namelen > NCHNAMLEN)) {
523 1.108 christos SDT_PROBE(vfs, namecache, lookup, toolong, dvp,
524 1.108 christos name, namelen, 0, 0);
525 1.103 dennis COUNT(cpup, ncs_long);
526 1.77 ad mutex_exit(&cpup->cpu_lock);
527 1.90 dholland /* found nothing */
528 1.113 riastrad return false;
529 1.1 cgd }
530 1.103 dennis
531 1.91 dholland ncp = cache_lookup_entry(dvp, name, namelen);
532 1.77 ad if (__predict_false(ncp == NULL)) {
533 1.103 dennis COUNT(cpup, ncs_miss);
534 1.77 ad mutex_exit(&cpup->cpu_lock);
535 1.90 dholland /* found nothing */
536 1.113 riastrad return false;
537 1.1 cgd }
538 1.91 dholland if ((cnflags & MAKEENTRY) == 0) {
539 1.103 dennis COUNT(cpup, ncs_badhits);
540 1.77 ad /*
541 1.77 ad * Last component and we are renaming or deleting,
542 1.77 ad * the cache entry is invalid, or otherwise don't
543 1.77 ad * want cache entry to exist.
544 1.77 ad */
545 1.77 ad cache_invalidate(ncp);
546 1.77 ad mutex_exit(&ncp->nc_lock);
547 1.102 dennis mutex_exit(&cpup->cpu_lock);
548 1.90 dholland /* found nothing */
549 1.113 riastrad return false;
550 1.90 dholland }
551 1.90 dholland if (ncp->nc_vp == NULL) {
552 1.90 dholland if (iswht_ret != NULL) {
553 1.90 dholland /*
554 1.90 dholland * Restore the ISWHITEOUT flag saved earlier.
555 1.90 dholland */
556 1.90 dholland KASSERT((ncp->nc_flags & ~ISWHITEOUT) == 0);
557 1.90 dholland *iswht_ret = (ncp->nc_flags & ISWHITEOUT) != 0;
558 1.90 dholland } else {
559 1.90 dholland KASSERT(ncp->nc_flags == 0);
560 1.90 dholland }
561 1.90 dholland
562 1.91 dholland if (__predict_true(nameiop != CREATE ||
563 1.91 dholland (cnflags & ISLASTCN) == 0)) {
564 1.103 dennis COUNT(cpup, ncs_neghits);
565 1.90 dholland /* found neg entry; vn is already null from above */
566 1.113 riastrad hit = true;
567 1.20 jdolecek } else {
568 1.103 dennis COUNT(cpup, ncs_badhits);
569 1.77 ad /*
570 1.109 dholland * Last component and we are preparing to create
571 1.109 dholland * the named object, so flush the negative cache
572 1.109 dholland * entry.
573 1.77 ad */
574 1.77 ad cache_invalidate(ncp);
575 1.90 dholland /* found nothing */
576 1.113 riastrad hit = false;
577 1.20 jdolecek }
578 1.103 dennis mutex_exit(&ncp->nc_lock);
579 1.103 dennis mutex_exit(&cpup->cpu_lock);
580 1.113 riastrad return hit;
581 1.20 jdolecek }
582 1.20 jdolecek
583 1.20 jdolecek vp = ncp->nc_vp;
584 1.92 hannken mutex_enter(vp->v_interlock);
585 1.92 hannken mutex_exit(&ncp->nc_lock);
586 1.102 dennis mutex_exit(&cpup->cpu_lock);
587 1.103 dennis
588 1.103 dennis /*
589 1.111 hannken * Unlocked except for the vnode interlock. Call vcache_tryvget().
590 1.103 dennis */
591 1.111 hannken error = vcache_tryvget(vp);
592 1.92 hannken if (error) {
593 1.92 hannken KASSERT(error == EBUSY);
594 1.92 hannken /*
595 1.92 hannken * This vnode is being cleaned out.
596 1.92 hannken * XXX badhits?
597 1.92 hannken */
598 1.103 dennis COUNT_UNL(cpup, ncs_falsehits);
599 1.92 hannken /* found nothing */
600 1.113 riastrad return false;
601 1.77 ad }
602 1.101 christos
603 1.103 dennis COUNT_UNL(cpup, ncs_goodhits);
604 1.101 christos /* found it */
605 1.101 christos *vn_ret = vp;
606 1.113 riastrad return true;
607 1.1 cgd }
608 1.1 cgd
609 1.103 dennis
610 1.103 dennis /*
611 1.103 dennis * Cut-'n-pasted version of the above without the nameiop argument.
612 1.103 dennis */
613 1.113 riastrad bool
614 1.91 dholland cache_lookup_raw(struct vnode *dvp, const char *name, size_t namelen,
615 1.91 dholland uint32_t cnflags,
616 1.90 dholland int *iswht_ret, struct vnode **vn_ret)
617 1.61 yamt {
618 1.61 yamt struct namecache *ncp;
619 1.61 yamt struct vnode *vp;
620 1.77 ad struct nchcpu *cpup;
621 1.101 christos int error;
622 1.61 yamt
623 1.90 dholland /* Establish default results. */
624 1.90 dholland if (iswht_ret != NULL) {
625 1.90 dholland *iswht_ret = 0;
626 1.90 dholland }
627 1.90 dholland *vn_ret = NULL;
628 1.90 dholland
629 1.77 ad if (__predict_false(!doingcache)) {
630 1.90 dholland /* found nothing */
631 1.113 riastrad return false;
632 1.61 yamt }
633 1.61 yamt
634 1.77 ad cpup = curcpu()->ci_data.cpu_nch;
635 1.102 dennis mutex_enter(&cpup->cpu_lock);
636 1.91 dholland if (__predict_false(namelen > NCHNAMLEN)) {
637 1.103 dennis COUNT(cpup, ncs_long);
638 1.77 ad mutex_exit(&cpup->cpu_lock);
639 1.90 dholland /* found nothing */
640 1.113 riastrad return false;
641 1.61 yamt }
642 1.91 dholland ncp = cache_lookup_entry(dvp, name, namelen);
643 1.77 ad if (__predict_false(ncp == NULL)) {
644 1.103 dennis COUNT(cpup, ncs_miss);
645 1.77 ad mutex_exit(&cpup->cpu_lock);
646 1.90 dholland /* found nothing */
647 1.113 riastrad return false;
648 1.61 yamt }
649 1.61 yamt vp = ncp->nc_vp;
650 1.61 yamt if (vp == NULL) {
651 1.61 yamt /*
652 1.61 yamt * Restore the ISWHITEOUT flag saved earlier.
653 1.61 yamt */
654 1.90 dholland if (iswht_ret != NULL) {
655 1.90 dholland KASSERT((ncp->nc_flags & ~ISWHITEOUT) == 0);
656 1.90 dholland /*cnp->cn_flags |= ncp->nc_flags;*/
657 1.90 dholland *iswht_ret = (ncp->nc_flags & ISWHITEOUT) != 0;
658 1.90 dholland }
659 1.103 dennis COUNT(cpup, ncs_neghits);
660 1.102 dennis mutex_exit(&ncp->nc_lock);
661 1.101 christos mutex_exit(&cpup->cpu_lock);
662 1.90 dholland /* found negative entry; vn is already null from above */
663 1.113 riastrad return true;
664 1.61 yamt }
665 1.92 hannken mutex_enter(vp->v_interlock);
666 1.92 hannken mutex_exit(&ncp->nc_lock);
667 1.102 dennis mutex_exit(&cpup->cpu_lock);
668 1.103 dennis
669 1.103 dennis /*
670 1.111 hannken * Unlocked except for the vnode interlock. Call vcache_tryvget().
671 1.103 dennis */
672 1.111 hannken error = vcache_tryvget(vp);
673 1.92 hannken if (error) {
674 1.92 hannken KASSERT(error == EBUSY);
675 1.92 hannken /*
676 1.92 hannken * This vnode is being cleaned out.
677 1.92 hannken * XXX badhits?
678 1.92 hannken */
679 1.103 dennis COUNT_UNL(cpup, ncs_falsehits);
680 1.92 hannken /* found nothing */
681 1.113 riastrad return false;
682 1.61 yamt }
683 1.101 christos
684 1.103 dennis COUNT_UNL(cpup, ncs_goodhits); /* XXX can be "badhits" */
685 1.101 christos /* found it */
686 1.101 christos *vn_ret = vp;
687 1.113 riastrad return true;
688 1.61 yamt }
689 1.61 yamt
690 1.1 cgd /*
691 1.19 sommerfe * Scan cache looking for name of directory entry pointing at vp.
692 1.19 sommerfe *
693 1.86 hannken * If the lookup succeeds the vnode is referenced and stored in dvpp.
694 1.19 sommerfe *
695 1.19 sommerfe * If bufp is non-NULL, also place the name in the buffer which starts
696 1.19 sommerfe * at bufp, immediately before *bpp, and move bpp backwards to point
697 1.19 sommerfe * at the start of it. (Yes, this is a little baroque, but it's done
698 1.19 sommerfe * this way to cater to the whims of getcwd).
699 1.19 sommerfe *
700 1.19 sommerfe * Returns 0 on success, -1 on cache miss, positive errno on failure.
701 1.19 sommerfe */
702 1.19 sommerfe int
703 1.34 enami cache_revlookup(struct vnode *vp, struct vnode **dvpp, char **bpp, char *bufp)
704 1.19 sommerfe {
705 1.19 sommerfe struct namecache *ncp;
706 1.19 sommerfe struct vnode *dvp;
707 1.103 dennis struct ncvhashhead *nvcpp;
708 1.95 joerg struct nchcpu *cpup;
709 1.34 enami char *bp;
710 1.86 hannken int error, nlen;
711 1.34 enami
712 1.19 sommerfe if (!doingcache)
713 1.19 sommerfe goto out;
714 1.19 sommerfe
715 1.30 chs nvcpp = &ncvhashtbl[NCVHASH(vp)];
716 1.103 dennis
717 1.103 dennis /*
718 1.103 dennis * We increment counters in the local CPU's per-cpu stats.
719 1.103 dennis * We don't take the per-cpu lock, however, since this function
720 1.103 dennis * is the only place these counters are incremented so no one
721 1.103 dennis * will be racing with us to increment them.
722 1.103 dennis */
723 1.95 joerg cpup = curcpu()->ci_data.cpu_nch;
724 1.73 ad mutex_enter(namecache_lock);
725 1.27 chs LIST_FOREACH(ncp, nvcpp, nc_vhash) {
726 1.73 ad mutex_enter(&ncp->nc_lock);
727 1.34 enami if (ncp->nc_vp == vp &&
728 1.34 enami (dvp = ncp->nc_dvp) != NULL &&
729 1.47 yamt dvp != vp) { /* avoid pesky . entries.. */
730 1.34 enami
731 1.19 sommerfe #ifdef DIAGNOSTIC
732 1.34 enami if (ncp->nc_nlen == 1 &&
733 1.34 enami ncp->nc_name[0] == '.')
734 1.19 sommerfe panic("cache_revlookup: found entry for .");
735 1.19 sommerfe
736 1.34 enami if (ncp->nc_nlen == 2 &&
737 1.34 enami ncp->nc_name[0] == '.' &&
738 1.34 enami ncp->nc_name[1] == '.')
739 1.19 sommerfe panic("cache_revlookup: found entry for ..");
740 1.19 sommerfe #endif
741 1.103 dennis COUNT(cpup, ncs_revhits);
742 1.86 hannken nlen = ncp->nc_nlen;
743 1.19 sommerfe
744 1.19 sommerfe if (bufp) {
745 1.19 sommerfe bp = *bpp;
746 1.86 hannken bp -= nlen;
747 1.19 sommerfe if (bp <= bufp) {
748 1.34 enami *dvpp = NULL;
749 1.73 ad mutex_exit(&ncp->nc_lock);
750 1.73 ad mutex_exit(namecache_lock);
751 1.108 christos SDT_PROBE(vfs, namecache, revlookup,
752 1.108 christos fail, vp, ERANGE, 0, 0, 0);
753 1.34 enami return (ERANGE);
754 1.19 sommerfe }
755 1.86 hannken memcpy(bp, ncp->nc_name, nlen);
756 1.19 sommerfe *bpp = bp;
757 1.19 sommerfe }
758 1.34 enami
759 1.92 hannken mutex_enter(dvp->v_interlock);
760 1.110 msaitoh mutex_exit(&ncp->nc_lock);
761 1.92 hannken mutex_exit(namecache_lock);
762 1.111 hannken error = vcache_tryvget(dvp);
763 1.92 hannken if (error) {
764 1.92 hannken KASSERT(error == EBUSY);
765 1.92 hannken if (bufp)
766 1.92 hannken (*bpp) += nlen;
767 1.92 hannken *dvpp = NULL;
768 1.108 christos SDT_PROBE(vfs, namecache, revlookup, fail, vp,
769 1.108 christos error, 0, 0, 0);
770 1.92 hannken return -1;
771 1.86 hannken }
772 1.19 sommerfe *dvpp = dvp;
773 1.108 christos SDT_PROBE(vfs, namecache, revlookup, success, vp, dvp,
774 1.108 christos 0, 0, 0);
775 1.34 enami return (0);
776 1.19 sommerfe }
777 1.73 ad mutex_exit(&ncp->nc_lock);
778 1.19 sommerfe }
779 1.103 dennis COUNT(cpup, ncs_revmiss);
780 1.73 ad mutex_exit(namecache_lock);
781 1.19 sommerfe out:
782 1.34 enami *dvpp = NULL;
783 1.34 enami return (-1);
784 1.19 sommerfe }
785 1.19 sommerfe
786 1.19 sommerfe /*
787 1.1 cgd * Add an entry to the cache
788 1.1 cgd */
789 1.13 christos void
790 1.91 dholland cache_enter(struct vnode *dvp, struct vnode *vp,
791 1.91 dholland const char *name, size_t namelen, uint32_t cnflags)
792 1.1 cgd {
793 1.23 augustss struct namecache *ncp;
794 1.59 yamt struct namecache *oncp;
795 1.23 augustss struct nchashhead *ncpp;
796 1.23 augustss struct ncvhashhead *nvcpp;
797 1.90 dholland nchash_t hash;
798 1.1 cgd
799 1.89 rmind /* First, check whether we can/should add a cache entry. */
800 1.91 dholland if ((cnflags & MAKEENTRY) == 0 ||
801 1.91 dholland __predict_false(namelen > NCHNAMLEN || !doingcache)) {
802 1.108 christos SDT_PROBE(vfs, namecache, enter, toolong, vp, name, namelen,
803 1.108 christos 0, 0);
804 1.1 cgd return;
805 1.89 rmind }
806 1.58 yamt
807 1.108 christos SDT_PROBE(vfs, namecache, enter, done, vp, name, namelen, 0, 0);
808 1.73 ad if (numcache > desiredvnodes) {
809 1.73 ad mutex_enter(namecache_lock);
810 1.73 ad cache_ev_forced.ev_count++;
811 1.73 ad cache_reclaim();
812 1.73 ad mutex_exit(namecache_lock);
813 1.39 pk }
814 1.57 pk
815 1.73 ad ncp = pool_cache_get(namecache_cache, PR_WAITOK);
816 1.73 ad mutex_enter(namecache_lock);
817 1.73 ad numcache++;
818 1.73 ad
819 1.59 yamt /*
820 1.59 yamt * Concurrent lookups in the same directory may race for a
821 1.59 yamt * cache entry. if there's a duplicated entry, free it.
822 1.59 yamt */
823 1.91 dholland oncp = cache_lookup_entry(dvp, name, namelen);
824 1.59 yamt if (oncp) {
825 1.73 ad cache_invalidate(oncp);
826 1.73 ad mutex_exit(&oncp->nc_lock);
827 1.59 yamt }
828 1.59 yamt
829 1.34 enami /* Grab the vnode we just found. */
830 1.73 ad mutex_enter(&ncp->nc_lock);
831 1.5 mycroft ncp->nc_vp = vp;
832 1.73 ad ncp->nc_flags = 0;
833 1.73 ad ncp->nc_hittime = 0;
834 1.73 ad ncp->nc_gcqueue = NULL;
835 1.47 yamt if (vp == NULL) {
836 1.11 mycroft /*
837 1.11 mycroft * For negative hits, save the ISWHITEOUT flag so we can
838 1.11 mycroft * restore it later when the cache entry is used again.
839 1.11 mycroft */
840 1.91 dholland ncp->nc_flags = cnflags & ISWHITEOUT;
841 1.11 mycroft }
842 1.89 rmind
843 1.34 enami /* Fill in cache info. */
844 1.5 mycroft ncp->nc_dvp = dvp;
845 1.112 hannken LIST_INSERT_HEAD(&VNODE_TO_VIMPL(dvp)->vi_dnclist, ncp, nc_dvlist);
846 1.46 yamt if (vp)
847 1.112 hannken LIST_INSERT_HEAD(&VNODE_TO_VIMPL(vp)->vi_nclist, ncp, nc_vlist);
848 1.73 ad else {
849 1.73 ad ncp->nc_vlist.le_prev = NULL;
850 1.73 ad ncp->nc_vlist.le_next = NULL;
851 1.73 ad }
852 1.91 dholland KASSERT(namelen <= NCHNAMLEN);
853 1.91 dholland ncp->nc_nlen = namelen;
854 1.91 dholland memcpy(ncp->nc_name, name, (unsigned)ncp->nc_nlen);
855 1.73 ad TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
856 1.91 dholland hash = cache_hash(name, namelen);
857 1.90 dholland ncpp = &nchashtbl[NCHASH2(hash, dvp)];
858 1.73 ad
859 1.73 ad /*
860 1.73 ad * Flush updates before making visible in table. No need for a
861 1.73 ad * memory barrier on the other side: to see modifications the
862 1.73 ad * list must be followed, meaning a dependent pointer load.
863 1.74 ad * The below is LIST_INSERT_HEAD() inlined, with the memory
864 1.74 ad * barrier included in the correct place.
865 1.73 ad */
866 1.74 ad if ((ncp->nc_hash.le_next = ncpp->lh_first) != NULL)
867 1.74 ad ncpp->lh_first->nc_hash.le_prev = &ncp->nc_hash.le_next;
868 1.74 ad ncp->nc_hash.le_prev = &ncpp->lh_first;
869 1.73 ad membar_producer();
870 1.74 ad ncpp->lh_first = ncp;
871 1.19 sommerfe
872 1.34 enami ncp->nc_vhash.le_prev = NULL;
873 1.34 enami ncp->nc_vhash.le_next = NULL;
874 1.34 enami
875 1.19 sommerfe /*
876 1.19 sommerfe * Create reverse-cache entries (used in getcwd) for directories.
877 1.66 christos * (and in linux procfs exe node)
878 1.19 sommerfe */
879 1.33 enami if (vp != NULL &&
880 1.33 enami vp != dvp &&
881 1.29 fvdl #ifndef NAMECACHE_ENTER_REVERSE
882 1.33 enami vp->v_type == VDIR &&
883 1.29 fvdl #endif
884 1.33 enami (ncp->nc_nlen > 2 ||
885 1.33 enami (ncp->nc_nlen > 1 && ncp->nc_name[1] != '.') ||
886 1.33 enami (/* ncp->nc_nlen > 0 && */ ncp->nc_name[0] != '.'))) {
887 1.30 chs nvcpp = &ncvhashtbl[NCVHASH(vp)];
888 1.19 sommerfe LIST_INSERT_HEAD(nvcpp, ncp, nc_vhash);
889 1.19 sommerfe }
890 1.73 ad mutex_exit(&ncp->nc_lock);
891 1.73 ad mutex_exit(namecache_lock);
892 1.1 cgd }
893 1.1 cgd
894 1.1 cgd /*
895 1.1 cgd * Name cache initialization, from vfs_init() when we are booting
896 1.1 cgd */
897 1.13 christos void
898 1.34 enami nchinit(void)
899 1.1 cgd {
900 1.73 ad int error;
901 1.1 cgd
902 1.89 rmind TAILQ_INIT(&nclruhead);
903 1.73 ad namecache_cache = pool_cache_init(sizeof(struct namecache),
904 1.73 ad coherency_unit, 0, 0, "ncache", NULL, IPL_NONE, cache_ctor,
905 1.73 ad cache_dtor, NULL);
906 1.71 ad KASSERT(namecache_cache != NULL);
907 1.71 ad
908 1.73 ad namecache_lock = mutex_obj_alloc(MUTEX_DEFAULT, IPL_NONE);
909 1.73 ad
910 1.76 ad nchashtbl = hashinit(desiredvnodes, HASH_LIST, true, &nchash);
911 1.26 ad ncvhashtbl =
912 1.29 fvdl #ifdef NAMECACHE_ENTER_REVERSE
913 1.76 ad hashinit(desiredvnodes, HASH_LIST, true, &ncvhash);
914 1.29 fvdl #else
915 1.76 ad hashinit(desiredvnodes/8, HASH_LIST, true, &ncvhash);
916 1.29 fvdl #endif
917 1.73 ad
918 1.73 ad error = kthread_create(PRI_VM, KTHREAD_MPSAFE, NULL, cache_thread,
919 1.73 ad NULL, NULL, "cachegc");
920 1.73 ad if (error != 0)
921 1.73 ad panic("nchinit %d", error);
922 1.73 ad
923 1.73 ad evcnt_attach_dynamic(&cache_ev_scan, EVCNT_TYPE_MISC, NULL,
924 1.73 ad "namecache", "entries scanned");
925 1.73 ad evcnt_attach_dynamic(&cache_ev_gc, EVCNT_TYPE_MISC, NULL,
926 1.73 ad "namecache", "entries collected");
927 1.73 ad evcnt_attach_dynamic(&cache_ev_over, EVCNT_TYPE_MISC, NULL,
928 1.73 ad "namecache", "over scan target");
929 1.73 ad evcnt_attach_dynamic(&cache_ev_under, EVCNT_TYPE_MISC, NULL,
930 1.73 ad "namecache", "under scan target");
931 1.73 ad evcnt_attach_dynamic(&cache_ev_forced, EVCNT_TYPE_MISC, NULL,
932 1.73 ad "namecache", "forced reclaims");
933 1.104 pooka
934 1.104 pooka sysctl_cache_stat_setup();
935 1.73 ad }
936 1.73 ad
937 1.73 ad static int
938 1.73 ad cache_ctor(void *arg, void *obj, int flag)
939 1.73 ad {
940 1.73 ad struct namecache *ncp;
941 1.73 ad
942 1.73 ad ncp = obj;
943 1.73 ad mutex_init(&ncp->nc_lock, MUTEX_DEFAULT, IPL_NONE);
944 1.73 ad
945 1.73 ad return 0;
946 1.73 ad }
947 1.73 ad
948 1.73 ad static void
949 1.73 ad cache_dtor(void *arg, void *obj)
950 1.73 ad {
951 1.73 ad struct namecache *ncp;
952 1.73 ad
953 1.73 ad ncp = obj;
954 1.73 ad mutex_destroy(&ncp->nc_lock);
955 1.73 ad }
956 1.73 ad
957 1.73 ad /*
958 1.73 ad * Called once for each CPU in the system as attached.
959 1.73 ad */
960 1.73 ad void
961 1.73 ad cache_cpu_init(struct cpu_info *ci)
962 1.73 ad {
963 1.77 ad struct nchcpu *cpup;
964 1.77 ad size_t sz;
965 1.73 ad
966 1.77 ad sz = roundup2(sizeof(*cpup), coherency_unit) + coherency_unit;
967 1.77 ad cpup = kmem_zalloc(sz, KM_SLEEP);
968 1.77 ad cpup = (void *)roundup2((uintptr_t)cpup, coherency_unit);
969 1.77 ad mutex_init(&cpup->cpu_lock, MUTEX_DEFAULT, IPL_NONE);
970 1.77 ad ci->ci_data.cpu_nch = cpup;
971 1.30 chs }
972 1.30 chs
973 1.30 chs /*
974 1.30 chs * Name cache reinitialization, for when the maximum number of vnodes increases.
975 1.30 chs */
976 1.30 chs void
977 1.34 enami nchreinit(void)
978 1.30 chs {
979 1.30 chs struct namecache *ncp;
980 1.30 chs struct nchashhead *oldhash1, *hash1;
981 1.30 chs struct ncvhashhead *oldhash2, *hash2;
982 1.36 thorpej u_long i, oldmask1, oldmask2, mask1, mask2;
983 1.30 chs
984 1.76 ad hash1 = hashinit(desiredvnodes, HASH_LIST, true, &mask1);
985 1.30 chs hash2 =
986 1.30 chs #ifdef NAMECACHE_ENTER_REVERSE
987 1.76 ad hashinit(desiredvnodes, HASH_LIST, true, &mask2);
988 1.30 chs #else
989 1.76 ad hashinit(desiredvnodes/8, HASH_LIST, true, &mask2);
990 1.30 chs #endif
991 1.73 ad mutex_enter(namecache_lock);
992 1.73 ad cache_lock_cpus();
993 1.30 chs oldhash1 = nchashtbl;
994 1.30 chs oldmask1 = nchash;
995 1.30 chs nchashtbl = hash1;
996 1.30 chs nchash = mask1;
997 1.30 chs oldhash2 = ncvhashtbl;
998 1.30 chs oldmask2 = ncvhash;
999 1.30 chs ncvhashtbl = hash2;
1000 1.30 chs ncvhash = mask2;
1001 1.30 chs for (i = 0; i <= oldmask1; i++) {
1002 1.30 chs while ((ncp = LIST_FIRST(&oldhash1[i])) != NULL) {
1003 1.30 chs LIST_REMOVE(ncp, nc_hash);
1004 1.30 chs ncp->nc_hash.le_prev = NULL;
1005 1.30 chs }
1006 1.30 chs }
1007 1.30 chs for (i = 0; i <= oldmask2; i++) {
1008 1.30 chs while ((ncp = LIST_FIRST(&oldhash2[i])) != NULL) {
1009 1.30 chs LIST_REMOVE(ncp, nc_vhash);
1010 1.30 chs ncp->nc_vhash.le_prev = NULL;
1011 1.30 chs }
1012 1.30 chs }
1013 1.73 ad cache_unlock_cpus();
1014 1.73 ad mutex_exit(namecache_lock);
1015 1.76 ad hashdone(oldhash1, HASH_LIST, oldmask1);
1016 1.76 ad hashdone(oldhash2, HASH_LIST, oldmask2);
1017 1.1 cgd }
1018 1.1 cgd
1019 1.1 cgd /*
1020 1.1 cgd * Cache flush, a particular vnode; called when a vnode is renamed to
1021 1.1 cgd * hide entries that would now be invalid
1022 1.1 cgd */
1023 1.13 christos void
1024 1.91 dholland cache_purge1(struct vnode *vp, const char *name, size_t namelen, int flags)
1025 1.1 cgd {
1026 1.46 yamt struct namecache *ncp, *ncnext;
1027 1.1 cgd
1028 1.73 ad mutex_enter(namecache_lock);
1029 1.55 yamt if (flags & PURGE_PARENTS) {
1030 1.108 christos SDT_PROBE(vfs, namecache, purge, parents, vp, 0, 0, 0, 0);
1031 1.108 christos
1032 1.112 hannken for (ncp = LIST_FIRST(&VNODE_TO_VIMPL(vp)->vi_nclist);
1033 1.112 hannken ncp != NULL; ncp = ncnext) {
1034 1.55 yamt ncnext = LIST_NEXT(ncp, nc_vlist);
1035 1.73 ad mutex_enter(&ncp->nc_lock);
1036 1.73 ad cache_invalidate(ncp);
1037 1.73 ad mutex_exit(&ncp->nc_lock);
1038 1.73 ad cache_disassociate(ncp);
1039 1.55 yamt }
1040 1.55 yamt }
1041 1.55 yamt if (flags & PURGE_CHILDREN) {
1042 1.108 christos SDT_PROBE(vfs, namecache, purge, children, vp, 0, 0, 0, 0);
1043 1.112 hannken for (ncp = LIST_FIRST(&VNODE_TO_VIMPL(vp)->vi_dnclist);
1044 1.112 hannken ncp != NULL; ncp = ncnext) {
1045 1.55 yamt ncnext = LIST_NEXT(ncp, nc_dvlist);
1046 1.73 ad mutex_enter(&ncp->nc_lock);
1047 1.73 ad cache_invalidate(ncp);
1048 1.73 ad mutex_exit(&ncp->nc_lock);
1049 1.73 ad cache_disassociate(ncp);
1050 1.55 yamt }
1051 1.46 yamt }
1052 1.91 dholland if (name != NULL) {
1053 1.108 christos SDT_PROBE(vfs, namecache, purge, name, name, namelen, 0, 0, 0);
1054 1.91 dholland ncp = cache_lookup_entry(vp, name, namelen);
1055 1.55 yamt if (ncp) {
1056 1.73 ad cache_invalidate(ncp);
1057 1.83 yamt mutex_exit(&ncp->nc_lock);
1058 1.73 ad cache_disassociate(ncp);
1059 1.55 yamt }
1060 1.46 yamt }
1061 1.73 ad mutex_exit(namecache_lock);
1062 1.1 cgd }
1063 1.1 cgd
1064 1.1 cgd /*
1065 1.1 cgd * Cache flush, a whole filesystem; called when filesys is umounted to
1066 1.27 chs * remove entries that would now be invalid.
1067 1.1 cgd */
1068 1.13 christos void
1069 1.34 enami cache_purgevfs(struct mount *mp)
1070 1.1 cgd {
1071 1.23 augustss struct namecache *ncp, *nxtcp;
1072 1.1 cgd
1073 1.108 christos SDT_PROBE(vfs, namecache, purge, vfs, mp, 0, 0, 0, 0);
1074 1.73 ad mutex_enter(namecache_lock);
1075 1.73 ad for (ncp = TAILQ_FIRST(&nclruhead); ncp != NULL; ncp = nxtcp) {
1076 1.73 ad nxtcp = TAILQ_NEXT(ncp, nc_lru);
1077 1.73 ad mutex_enter(&ncp->nc_lock);
1078 1.73 ad if (ncp->nc_dvp != NULL && ncp->nc_dvp->v_mount == mp) {
1079 1.73 ad /* Free the resources we had. */
1080 1.73 ad cache_invalidate(ncp);
1081 1.73 ad cache_disassociate(ncp);
1082 1.73 ad }
1083 1.73 ad mutex_exit(&ncp->nc_lock);
1084 1.73 ad }
1085 1.73 ad cache_reclaim();
1086 1.73 ad mutex_exit(namecache_lock);
1087 1.73 ad }
1088 1.73 ad
1089 1.73 ad /*
1090 1.73 ad * Scan global list invalidating entries until we meet a preset target.
1091 1.73 ad * Prefer to invalidate entries that have not scored a hit within
1092 1.73 ad * cache_hottime seconds. We sort the LRU list only for this routine's
1093 1.73 ad * benefit.
1094 1.73 ad */
1095 1.73 ad static void
1096 1.73 ad cache_prune(int incache, int target)
1097 1.73 ad {
1098 1.73 ad struct namecache *ncp, *nxtcp, *sentinel;
1099 1.73 ad int items, recent, tryharder;
1100 1.73 ad
1101 1.73 ad KASSERT(mutex_owned(namecache_lock));
1102 1.73 ad
1103 1.108 christos SDT_PROBE(vfs, namecache, prune, done, incache, target, 0, 0, 0);
1104 1.73 ad items = 0;
1105 1.73 ad tryharder = 0;
1106 1.73 ad recent = hardclock_ticks - hz * cache_hottime;
1107 1.73 ad sentinel = NULL;
1108 1.27 chs for (ncp = TAILQ_FIRST(&nclruhead); ncp != NULL; ncp = nxtcp) {
1109 1.73 ad if (incache <= target)
1110 1.73 ad break;
1111 1.73 ad items++;
1112 1.27 chs nxtcp = TAILQ_NEXT(ncp, nc_lru);
1113 1.73 ad if (ncp == sentinel) {
1114 1.73 ad /*
1115 1.73 ad * If we looped back on ourself, then ignore
1116 1.73 ad * recent entries and purge whatever we find.
1117 1.73 ad */
1118 1.73 ad tryharder = 1;
1119 1.5 mycroft }
1120 1.93 hannken if (ncp->nc_dvp == NULL)
1121 1.93 hannken continue;
1122 1.81 yamt if (!tryharder && (ncp->nc_hittime - recent) > 0) {
1123 1.73 ad if (sentinel == NULL)
1124 1.73 ad sentinel = ncp;
1125 1.73 ad TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
1126 1.73 ad TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
1127 1.73 ad continue;
1128 1.73 ad }
1129 1.73 ad mutex_enter(&ncp->nc_lock);
1130 1.73 ad if (ncp->nc_dvp != NULL) {
1131 1.73 ad cache_invalidate(ncp);
1132 1.73 ad cache_disassociate(ncp);
1133 1.73 ad incache--;
1134 1.73 ad }
1135 1.73 ad mutex_exit(&ncp->nc_lock);
1136 1.73 ad }
1137 1.73 ad cache_ev_scan.ev_count += items;
1138 1.73 ad }
1139 1.73 ad
1140 1.73 ad /*
1141 1.73 ad * Collect dead cache entries from all CPUs and garbage collect.
1142 1.73 ad */
1143 1.73 ad static void
1144 1.73 ad cache_reclaim(void)
1145 1.73 ad {
1146 1.73 ad struct namecache *ncp, *next;
1147 1.73 ad int items;
1148 1.73 ad
1149 1.73 ad KASSERT(mutex_owned(namecache_lock));
1150 1.73 ad
1151 1.73 ad /*
1152 1.73 ad * If the number of extant entries not awaiting garbage collection
1153 1.73 ad * exceeds the high water mark, then reclaim stale entries until we
1154 1.73 ad * reach our low water mark.
1155 1.73 ad */
1156 1.73 ad items = numcache - cache_gcpend;
1157 1.73 ad if (items > (uint64_t)desiredvnodes * cache_hiwat / 100) {
1158 1.73 ad cache_prune(items, (int)((uint64_t)desiredvnodes *
1159 1.73 ad cache_lowat / 100));
1160 1.73 ad cache_ev_over.ev_count++;
1161 1.73 ad } else
1162 1.73 ad cache_ev_under.ev_count++;
1163 1.73 ad
1164 1.73 ad /*
1165 1.73 ad * Stop forward lookup activity on all CPUs and garbage collect dead
1166 1.73 ad * entries.
1167 1.73 ad */
1168 1.73 ad cache_lock_cpus();
1169 1.73 ad ncp = cache_gcqueue;
1170 1.73 ad cache_gcqueue = NULL;
1171 1.73 ad items = cache_gcpend;
1172 1.73 ad cache_gcpend = 0;
1173 1.73 ad while (ncp != NULL) {
1174 1.73 ad next = ncp->nc_gcqueue;
1175 1.73 ad cache_disassociate(ncp);
1176 1.73 ad KASSERT(ncp->nc_dvp == NULL);
1177 1.73 ad if (ncp->nc_hash.le_prev != NULL) {
1178 1.73 ad LIST_REMOVE(ncp, nc_hash);
1179 1.73 ad ncp->nc_hash.le_prev = NULL;
1180 1.73 ad }
1181 1.73 ad pool_cache_put(namecache_cache, ncp);
1182 1.73 ad ncp = next;
1183 1.73 ad }
1184 1.73 ad cache_unlock_cpus();
1185 1.73 ad numcache -= items;
1186 1.73 ad cache_ev_gc.ev_count += items;
1187 1.73 ad }
1188 1.73 ad
1189 1.73 ad /*
1190 1.73 ad * Cache maintainence thread, awakening once per second to:
1191 1.73 ad *
1192 1.73 ad * => keep number of entries below the high water mark
1193 1.73 ad * => sort pseudo-LRU list
1194 1.73 ad * => garbage collect dead entries
1195 1.73 ad */
1196 1.73 ad static void
1197 1.73 ad cache_thread(void *arg)
1198 1.73 ad {
1199 1.73 ad
1200 1.73 ad mutex_enter(namecache_lock);
1201 1.73 ad for (;;) {
1202 1.73 ad cache_reclaim();
1203 1.73 ad kpause("cachegc", false, hz, namecache_lock);
1204 1.1 cgd }
1205 1.1 cgd }
1206 1.19 sommerfe
1207 1.28 chs #ifdef DDB
1208 1.28 chs void
1209 1.28 chs namecache_print(struct vnode *vp, void (*pr)(const char *, ...))
1210 1.28 chs {
1211 1.28 chs struct vnode *dvp = NULL;
1212 1.28 chs struct namecache *ncp;
1213 1.28 chs
1214 1.28 chs TAILQ_FOREACH(ncp, &nclruhead, nc_lru) {
1215 1.73 ad if (ncp->nc_vp == vp && ncp->nc_dvp != NULL) {
1216 1.28 chs (*pr)("name %.*s\n", ncp->nc_nlen, ncp->nc_name);
1217 1.28 chs dvp = ncp->nc_dvp;
1218 1.28 chs }
1219 1.28 chs }
1220 1.28 chs if (dvp == NULL) {
1221 1.28 chs (*pr)("name not found\n");
1222 1.28 chs return;
1223 1.28 chs }
1224 1.28 chs vp = dvp;
1225 1.28 chs TAILQ_FOREACH(ncp, &nclruhead, nc_lru) {
1226 1.47 yamt if (ncp->nc_vp == vp) {
1227 1.28 chs (*pr)("parent %.*s\n", ncp->nc_nlen, ncp->nc_name);
1228 1.28 chs }
1229 1.28 chs }
1230 1.28 chs }
1231 1.28 chs #endif
1232 1.95 joerg
1233 1.95 joerg void
1234 1.95 joerg namecache_count_pass2(void)
1235 1.95 joerg {
1236 1.95 joerg struct nchcpu *cpup = curcpu()->ci_data.cpu_nch;
1237 1.95 joerg
1238 1.103 dennis COUNT_UNL(cpup, ncs_pass2);
1239 1.95 joerg }
1240 1.95 joerg
1241 1.95 joerg void
1242 1.95 joerg namecache_count_2passes(void)
1243 1.95 joerg {
1244 1.95 joerg struct nchcpu *cpup = curcpu()->ci_data.cpu_nch;
1245 1.95 joerg
1246 1.103 dennis COUNT_UNL(cpup, ncs_2passes);
1247 1.95 joerg }
1248 1.97 joerg
1249 1.103 dennis /*
1250 1.103 dennis * Fetch the current values of the stats. We return the most
1251 1.103 dennis * recent values harvested into nchstats by cache_reclaim(), which
1252 1.103 dennis * will be less than a second old.
1253 1.103 dennis */
1254 1.97 joerg static int
1255 1.97 joerg cache_stat_sysctl(SYSCTLFN_ARGS)
1256 1.97 joerg {
1257 1.103 dennis struct nchstats stats;
1258 1.103 dennis struct nchcpu *my_cpup;
1259 1.103 dennis #ifdef CACHE_STATS_CURRENT
1260 1.103 dennis CPU_INFO_ITERATOR cii;
1261 1.103 dennis struct cpu_info *ci;
1262 1.103 dennis #endif /* CACHE_STATS_CURRENT */
1263 1.97 joerg
1264 1.97 joerg if (oldp == NULL) {
1265 1.97 joerg *oldlenp = sizeof(stats);
1266 1.97 joerg return 0;
1267 1.97 joerg }
1268 1.97 joerg
1269 1.97 joerg if (*oldlenp < sizeof(stats)) {
1270 1.97 joerg *oldlenp = 0;
1271 1.97 joerg return 0;
1272 1.97 joerg }
1273 1.97 joerg
1274 1.103 dennis /*
1275 1.103 dennis * Take this CPU's per-cpu lock to hold off cache_reclaim()
1276 1.103 dennis * from doing a stats update while doing minimal damage to
1277 1.103 dennis * concurrent operations.
1278 1.103 dennis */
1279 1.103 dennis sysctl_unlock();
1280 1.103 dennis my_cpup = curcpu()->ci_data.cpu_nch;
1281 1.103 dennis mutex_enter(&my_cpup->cpu_lock);
1282 1.103 dennis stats = nchstats;
1283 1.103 dennis #ifdef CACHE_STATS_CURRENT
1284 1.103 dennis for (CPU_INFO_FOREACH(cii, ci)) {
1285 1.103 dennis struct nchcpu *cpup = ci->ci_data.cpu_nch;
1286 1.97 joerg
1287 1.103 dennis ADD(stats, cpup, ncs_goodhits);
1288 1.103 dennis ADD(stats, cpup, ncs_neghits);
1289 1.103 dennis ADD(stats, cpup, ncs_badhits);
1290 1.103 dennis ADD(stats, cpup, ncs_falsehits);
1291 1.103 dennis ADD(stats, cpup, ncs_miss);
1292 1.103 dennis ADD(stats, cpup, ncs_long);
1293 1.103 dennis ADD(stats, cpup, ncs_pass2);
1294 1.103 dennis ADD(stats, cpup, ncs_2passes);
1295 1.103 dennis ADD(stats, cpup, ncs_revhits);
1296 1.103 dennis ADD(stats, cpup, ncs_revmiss);
1297 1.103 dennis }
1298 1.103 dennis #endif /* CACHE_STATS_CURRENT */
1299 1.103 dennis mutex_exit(&my_cpup->cpu_lock);
1300 1.97 joerg sysctl_relock();
1301 1.97 joerg
1302 1.97 joerg *oldlenp = sizeof(stats);
1303 1.97 joerg return sysctl_copyout(l, &stats, oldp, sizeof(stats));
1304 1.97 joerg }
1305 1.97 joerg
1306 1.104 pooka static void
1307 1.104 pooka sysctl_cache_stat_setup(void)
1308 1.97 joerg {
1309 1.104 pooka
1310 1.104 pooka KASSERT(sysctllog == NULL);
1311 1.104 pooka sysctl_createv(&sysctllog, 0, NULL, NULL,
1312 1.97 joerg CTLFLAG_PERMANENT,
1313 1.97 joerg CTLTYPE_STRUCT, "namecache_stats",
1314 1.97 joerg SYSCTL_DESCR("namecache statistics"),
1315 1.97 joerg cache_stat_sysctl, 0, NULL, 0,
1316 1.97 joerg CTL_VFS, CTL_CREATE, CTL_EOL);
1317 1.97 joerg }
1318