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