xref: /freebsd/sys/kern/vfs_cache.c (revision 944223076fbcb681a8eb3e118ddafab79b21ac3d)
1 /*-
2  * SPDX-License-Identifier: BSD-3-Clause
3  *
4  * Copyright (c) 1989, 1993, 1995
5  *	The Regents of the University of California.  All rights reserved.
6  *
7  * This code is derived from software contributed to Berkeley by
8  * Poul-Henning Kamp of the FreeBSD Project.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  * 3. Neither the name of the University nor the names of its contributors
19  *    may be used to endorse or promote products derived from this software
20  *    without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  *
34  *	@(#)vfs_cache.c	8.5 (Berkeley) 3/22/95
35  */
36 
37 #include <sys/cdefs.h>
38 #include "opt_ddb.h"
39 #include "opt_ktrace.h"
40 
41 #include <sys/param.h>
42 #include <sys/systm.h>
43 #include <sys/capsicum.h>
44 #include <sys/counter.h>
45 #include <sys/filedesc.h>
46 #include <sys/fnv_hash.h>
47 #include <sys/kernel.h>
48 #include <sys/ktr.h>
49 #include <sys/lock.h>
50 #include <sys/malloc.h>
51 #include <sys/fcntl.h>
52 #include <sys/jail.h>
53 #include <sys/mount.h>
54 #include <sys/namei.h>
55 #include <sys/proc.h>
56 #include <sys/seqc.h>
57 #include <sys/sdt.h>
58 #include <sys/smr.h>
59 #include <sys/smp.h>
60 #include <sys/syscallsubr.h>
61 #include <sys/sysctl.h>
62 #include <sys/sysproto.h>
63 #include <sys/vnode.h>
64 #include <ck_queue.h>
65 #ifdef KTRACE
66 #include <sys/ktrace.h>
67 #endif
68 #ifdef INVARIANTS
69 #include <machine/_inttypes.h>
70 #endif
71 
72 #include <security/audit/audit.h>
73 #include <security/mac/mac_framework.h>
74 
75 #ifdef DDB
76 #include <ddb/ddb.h>
77 #endif
78 
79 #include <vm/uma.h>
80 
81 /*
82  * High level overview of name caching in the VFS layer.
83  *
84  * Originally caching was implemented as part of UFS, later extracted to allow
85  * use by other filesystems. A decision was made to make it optional and
86  * completely detached from the rest of the kernel, which comes with limitations
87  * outlined near the end of this comment block.
88  *
89  * This fundamental choice needs to be revisited. In the meantime, the current
90  * state is described below. Significance of all notable routines is explained
91  * in comments placed above their implementation. Scattered thoroughout the
92  * file are TODO comments indicating shortcomings which can be fixed without
93  * reworking everything (most of the fixes will likely be reusable). Various
94  * details are omitted from this explanation to not clutter the overview, they
95  * have to be checked by reading the code and associated commentary.
96  *
97  * Keep in mind that it's individual path components which are cached, not full
98  * paths. That is, for a fully cached path "foo/bar/baz" there are 3 entries,
99  * one for each name.
100  *
101  * I. Data organization
102  *
103  * Entries are described by "struct namecache" objects and stored in a hash
104  * table. See cache_get_hash for more information.
105  *
106  * "struct vnode" contains pointers to source entries (names which can be found
107  * when traversing through said vnode), destination entries (names of that
108  * vnode (see "Limitations" for a breakdown on the subject) and a pointer to
109  * the parent vnode.
110  *
111  * The (directory vnode; name) tuple reliably determines the target entry if
112  * it exists.
113  *
114  * Since there are no small locks at this time (all are 32 bytes in size on
115  * LP64), the code works around the problem by introducing lock arrays to
116  * protect hash buckets and vnode lists.
117  *
118  * II. Filesystem integration
119  *
120  * Filesystems participating in name caching do the following:
121  * - set vop_lookup routine to vfs_cache_lookup
122  * - set vop_cachedlookup to whatever can perform the lookup if the above fails
123  * - if they support lockless lookup (see below), vop_fplookup_vexec and
124  *   vop_fplookup_symlink are set along with the MNTK_FPLOOKUP flag on the
125  *   mount point
126  * - call cache_purge or cache_vop_* routines to eliminate stale entries as
127  *   applicable
128  * - call cache_enter to add entries depending on the MAKEENTRY flag
129  *
130  * With the above in mind, there are 2 entry points when doing lookups:
131  * - ... -> namei -> cache_fplookup -- this is the default
132  * - ... -> VOP_LOOKUP -> vfs_cache_lookup -- normally only called by namei
133  *   should the above fail
134  *
135  * Example code flow how an entry is added:
136  * ... -> namei -> cache_fplookup -> cache_fplookup_noentry -> VOP_LOOKUP ->
137  * vfs_cache_lookup -> VOP_CACHEDLOOKUP -> ufs_lookup_ino -> cache_enter
138  *
139  * III. Performance considerations
140  *
141  * For lockless case forward lookup avoids any writes to shared areas apart
142  * from the terminal path component. In other words non-modifying lookups of
143  * different files don't suffer any scalability problems in the namecache.
144  * Looking up the same file is limited by VFS and goes beyond the scope of this
145  * file.
146  *
147  * At least on amd64 the single-threaded bottleneck for long paths is hashing
148  * (see cache_get_hash). There are cases where the code issues acquire fence
149  * multiple times, they can be combined on architectures which suffer from it.
150  *
151  * For locked case each encountered vnode has to be referenced and locked in
152  * order to be handed out to the caller (normally that's namei). This
153  * introduces significant hit single-threaded and serialization multi-threaded.
154  *
155  * Reverse lookup (e.g., "getcwd") fully scales provided it is fully cached --
156  * avoids any writes to shared areas to any components.
157  *
158  * Unrelated insertions are partially serialized on updating the global entry
159  * counter and possibly serialized on colliding bucket or vnode locks.
160  *
161  * IV. Observability
162  *
163  * Note not everything has an explicit dtrace probe nor it should have, thus
164  * some of the one-liners below depend on implementation details.
165  *
166  * Examples:
167  *
168  * # Check what lookups failed to be handled in a lockless manner. Column 1 is
169  * # line number, column 2 is status code (see cache_fpl_status)
170  * dtrace -n 'vfs:fplookup:lookup:done { @[arg1, arg2] = count(); }'
171  *
172  * # Lengths of names added by binary name
173  * dtrace -n 'fbt::cache_enter_time:entry { @[execname] = quantize(args[2]->cn_namelen); }'
174  *
175  * # Same as above but only those which exceed 64 characters
176  * dtrace -n 'fbt::cache_enter_time:entry /args[2]->cn_namelen > 64/ { @[execname] = quantize(args[2]->cn_namelen); }'
177  *
178  * # Who is performing lookups with spurious slashes (e.g., "foo//bar") and what
179  * # path is it
180  * dtrace -n 'fbt::cache_fplookup_skip_slashes:entry { @[execname, stringof(args[0]->cnp->cn_pnbuf)] = count(); }'
181  *
182  * V. Limitations and implementation defects
183  *
184  * - since it is possible there is no entry for an open file, tools like
185  *   "procstat" may fail to resolve fd -> vnode -> path to anything
186  * - even if a filesystem adds an entry, it may get purged (e.g., due to memory
187  *   shortage) in which case the above problem applies
188  * - hardlinks are not tracked, thus if a vnode is reachable in more than one
189  *   way, resolving a name may return a different path than the one used to
190  *   open it (even if said path is still valid)
191  * - by default entries are not added for newly created files
192  * - adding an entry may need to evict negative entry first, which happens in 2
193  *   distinct places (evicting on lookup, adding in a later VOP) making it
194  *   impossible to simply reuse it
195  * - there is a simple scheme to evict negative entries as the cache is approaching
196  *   its capacity, but it is very unclear if doing so is a good idea to begin with
197  * - vnodes are subject to being recycled even if target inode is left in memory,
198  *   which loses the name cache entries when it perhaps should not. in case of tmpfs
199  *   names get duplicated -- kept by filesystem itself and namecache separately
200  * - struct namecache has a fixed size and comes in 2 variants, often wasting
201  *   space.  now hard to replace with malloc due to dependence on SMR, which
202  *   requires UMA zones to opt in
203  * - lack of better integration with the kernel also turns nullfs into a layered
204  *   filesystem instead of something which can take advantage of caching
205  *
206  * Appendix A: where is the time lost, expanding on paragraph III
207  *
208  * While some care went into optimizing lookups, there is still plenty of
209  * performance left on the table, most notably from single-threaded standpoint.
210  * Below is a woefully incomplete list of changes which can help.  Ideas are
211  * mostly sketched out, no claim is made all kinks or prerequisites are laid
212  * out.
213  *
214  * Note there is performance lost all over VFS.
215  *
216  * === SMR-only lookup
217  *
218  * For commonly used ops like stat(2), when the terminal vnode *is* cached,
219  * lockless lookup could refrain from refing/locking the found vnode and
220  * instead return while within the SMR section. Then a call to, say,
221  * vop_stat_smr could do the work (or fail with EAGAIN), finally the result
222  * would be validated with seqc not changing. This would be faster
223  * single-threaded as it dodges atomics and would provide full scalability for
224  * multicore uses. This would *not* work for open(2) or other calls which need
225  * the vnode to hang around for the long haul, but would work for aforementioned
226  * stat(2) but also access(2), readlink(2), realpathat(2) and probably more.
227  *
228  * === hotpatching for sdt probes
229  *
230  * They result in *tons* of branches all over with rather regrettable codegen
231  * at times. Removing sdt probes altogether gives over 2% boost in lookup rate.
232  * Reworking the code to patch itself at runtime with asm goto would solve it.
233  * asm goto is fully supported by gcc and clang.
234  *
235  * === copyinstr
236  *
237  * On all architectures it operates one byte at a time, while it could be
238  * word-sized instead thanks to the Mycroft trick.
239  *
240  * API itself is rather pessimal for path lookup, accepting arbitrary sizes and
241  * *optionally* filling in the length parameter.
242  *
243  * Instead a new routine (copyinpath?) could be introduced, demanding a buffer
244  * size which is a multiply of the word (and never zero), with the length
245  * always returned. On top of it the routine could be allowed to transform the
246  * buffer in arbitrary ways, most notably writing past the found length (not to
247  * be confused with writing past buffer size) -- this would allow word-sized
248  * movs while checking for '\0' later.
249  *
250  * === detour through namei
251  *
252  * Currently one suffers being called from namei, which then has to check if
253  * things worked out locklessly. Instead the lockless lookup could be the
254  * actual entry point which calls what is currently namei as a fallback.
255  *
256  * === avoidable branches in cache_can_fplookup
257  *
258  * The cache_fast_lookup_enabled flag check could be hotpatchable (in fact if
259  * this is off, none of fplookup code should execute).
260  *
261  * Both audit and capsicum branches can be combined into one, but it requires
262  * paying off a lot of tech debt first.
263  *
264  * ni_startdir could be indicated with a flag in cn_flags, eliminating the
265  * branch.
266  *
267  * === mount stacks
268  *
269  * Crossing a mount requires checking if perhaps something is mounted on top.
270  * Instead, an additional entry could be added to struct mount with a pointer
271  * to the final mount on the stack. This would be recalculated on each
272  * mount/unmount.
273  *
274  * === root vnodes
275  *
276  * It could become part of the API contract to *always* have a rootvnode set in
277  * mnt_rootvnode. Such vnodes are annotated with VV_ROOT and vnlru would have
278  * to be modified to always skip them.
279  *
280  * === inactive on v_usecount reaching 0
281  *
282  * VOP_NEED_INACTIVE should not exist. Filesystems would indicate need for such
283  * processing with a bit in usecount.
284  *
285  * === v_holdcnt
286  *
287  * Hold count should probably get eliminated, but one can argue it is a useful
288  * feature. Even if so, handling of v_usecount could be decoupled from it --
289  * vnlru et al would consider the vnode not-freeable if has either hold or
290  * usecount on it.
291  *
292  * This would eliminate 2 atomics.
293  */
294 
295 static SYSCTL_NODE(_vfs, OID_AUTO, cache, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
296     "Name cache");
297 
298 SDT_PROVIDER_DECLARE(vfs);
299 SDT_PROBE_DEFINE3(vfs, namecache, enter, done, "struct vnode *", "char *",
300     "struct vnode *");
301 SDT_PROBE_DEFINE3(vfs, namecache, enter, duplicate, "struct vnode *", "char *",
302     "struct vnode *");
303 SDT_PROBE_DEFINE2(vfs, namecache, enter_negative, done, "struct vnode *",
304     "char *");
305 SDT_PROBE_DEFINE2(vfs, namecache, fullpath_smr, hit, "struct vnode *",
306     "const char *");
307 SDT_PROBE_DEFINE4(vfs, namecache, fullpath_smr, miss, "struct vnode *",
308     "struct namecache *", "int", "int");
309 SDT_PROBE_DEFINE1(vfs, namecache, fullpath, entry, "struct vnode *");
310 SDT_PROBE_DEFINE3(vfs, namecache, fullpath, hit, "struct vnode *",
311     "char *", "struct vnode *");
312 SDT_PROBE_DEFINE1(vfs, namecache, fullpath, miss, "struct vnode *");
313 SDT_PROBE_DEFINE3(vfs, namecache, fullpath, return, "int",
314     "struct vnode *", "char *");
315 SDT_PROBE_DEFINE3(vfs, namecache, lookup, hit, "struct vnode *", "char *",
316     "struct vnode *");
317 SDT_PROBE_DEFINE2(vfs, namecache, lookup, hit__negative,
318     "struct vnode *", "char *");
319 SDT_PROBE_DEFINE2(vfs, namecache, lookup, miss, "struct vnode *",
320     "char *");
321 SDT_PROBE_DEFINE2(vfs, namecache, removecnp, hit, "struct vnode *",
322     "struct componentname *");
323 SDT_PROBE_DEFINE2(vfs, namecache, removecnp, miss, "struct vnode *",
324     "struct componentname *");
325 SDT_PROBE_DEFINE3(vfs, namecache, purge, done, "struct vnode *", "size_t", "size_t");
326 SDT_PROBE_DEFINE1(vfs, namecache, purge, batch, "int");
327 SDT_PROBE_DEFINE1(vfs, namecache, purge_negative, done, "struct vnode *");
328 SDT_PROBE_DEFINE1(vfs, namecache, purgevfs, done, "struct mount *");
329 SDT_PROBE_DEFINE3(vfs, namecache, zap, done, "struct vnode *", "char *",
330     "struct vnode *");
331 SDT_PROBE_DEFINE2(vfs, namecache, zap_negative, done, "struct vnode *",
332     "char *");
333 SDT_PROBE_DEFINE2(vfs, namecache, evict_negative, done, "struct vnode *",
334     "char *");
335 SDT_PROBE_DEFINE1(vfs, namecache, symlink, alloc__fail, "size_t");
336 
337 SDT_PROBE_DEFINE3(vfs, fplookup, lookup, done, "struct nameidata", "int", "bool");
338 SDT_PROBE_DECLARE(vfs, namei, lookup, entry);
339 SDT_PROBE_DECLARE(vfs, namei, lookup, return);
340 
341 static char __read_frequently cache_fast_lookup_enabled = true;
342 
343 /*
344  * This structure describes the elements in the cache of recent
345  * names looked up by namei.
346  */
347 struct negstate {
348 	u_char neg_flag;
349 	u_char neg_hit;
350 };
351 _Static_assert(sizeof(struct negstate) <= sizeof(struct vnode *),
352     "the state must fit in a union with a pointer without growing it");
353 
354 struct	namecache {
355 	LIST_ENTRY(namecache) nc_src;	/* source vnode list */
356 	TAILQ_ENTRY(namecache) nc_dst;	/* destination vnode list */
357 	CK_SLIST_ENTRY(namecache) nc_hash;/* hash chain */
358 	struct	vnode *nc_dvp;		/* vnode of parent of name */
359 	union {
360 		struct	vnode *nu_vp;	/* vnode the name refers to */
361 		struct	negstate nu_neg;/* negative entry state */
362 	} n_un;
363 	u_char	nc_flag;		/* flag bits */
364 	u_char	nc_nlen;		/* length of name */
365 	char	nc_name[];		/* segment name + nul */
366 };
367 
368 /*
369  * struct namecache_ts repeats struct namecache layout up to the
370  * nc_nlen member.
371  * struct namecache_ts is used in place of struct namecache when time(s) need
372  * to be stored.  The nc_dotdottime field is used when a cache entry is mapping
373  * both a non-dotdot directory name plus dotdot for the directory's
374  * parent.
375  *
376  * See below for alignment requirement.
377  */
378 struct	namecache_ts {
379 	struct	timespec nc_time;	/* timespec provided by fs */
380 	struct	timespec nc_dotdottime;	/* dotdot timespec provided by fs */
381 	int	nc_ticks;		/* ticks value when entry was added */
382 	int	nc_pad;
383 	struct namecache nc_nc;
384 };
385 
386 TAILQ_HEAD(cache_freebatch, namecache);
387 
388 /*
389  * At least mips n32 performs 64-bit accesses to timespec as found
390  * in namecache_ts and requires them to be aligned. Since others
391  * may be in the same spot suffer a little bit and enforce the
392  * alignment for everyone. Note this is a nop for 64-bit platforms.
393  */
394 #define CACHE_ZONE_ALIGNMENT	UMA_ALIGNOF(time_t)
395 
396 /*
397  * TODO: the initial value of CACHE_PATH_CUTOFF was inherited from the
398  * 4.4 BSD codebase. Later on struct namecache was tweaked to become
399  * smaller and the value was bumped to retain the total size, but it
400  * was never re-evaluated for suitability. A simple test counting
401  * lengths during package building shows that the value of 45 covers
402  * about 86% of all added entries, reaching 99% at 65.
403  *
404  * Regardless of the above, use of dedicated zones instead of malloc may be
405  * inducing additional waste. This may be hard to address as said zones are
406  * tied to VFS SMR. Even if retaining them, the current split should be
407  * re-evaluated.
408  */
409 #ifdef __LP64__
410 #define	CACHE_PATH_CUTOFF	45
411 #define	CACHE_LARGE_PAD		6
412 #else
413 #define	CACHE_PATH_CUTOFF	41
414 #define	CACHE_LARGE_PAD		2
415 #endif
416 
417 #define CACHE_ZONE_SMALL_SIZE		(offsetof(struct namecache, nc_name) + CACHE_PATH_CUTOFF + 1)
418 #define CACHE_ZONE_SMALL_TS_SIZE	(offsetof(struct namecache_ts, nc_nc) + CACHE_ZONE_SMALL_SIZE)
419 #define CACHE_ZONE_LARGE_SIZE		(offsetof(struct namecache, nc_name) + NAME_MAX + 1 + CACHE_LARGE_PAD)
420 #define CACHE_ZONE_LARGE_TS_SIZE	(offsetof(struct namecache_ts, nc_nc) + CACHE_ZONE_LARGE_SIZE)
421 
422 _Static_assert((CACHE_ZONE_SMALL_SIZE % (CACHE_ZONE_ALIGNMENT + 1)) == 0, "bad zone size");
423 _Static_assert((CACHE_ZONE_SMALL_TS_SIZE % (CACHE_ZONE_ALIGNMENT + 1)) == 0, "bad zone size");
424 _Static_assert((CACHE_ZONE_LARGE_SIZE % (CACHE_ZONE_ALIGNMENT + 1)) == 0, "bad zone size");
425 _Static_assert((CACHE_ZONE_LARGE_TS_SIZE % (CACHE_ZONE_ALIGNMENT + 1)) == 0, "bad zone size");
426 
427 #define	nc_vp		n_un.nu_vp
428 #define	nc_neg		n_un.nu_neg
429 
430 /*
431  * Flags in namecache.nc_flag
432  */
433 #define NCF_WHITE	0x01
434 #define NCF_ISDOTDOT	0x02
435 #define	NCF_TS		0x04
436 #define	NCF_DTS		0x08
437 #define	NCF_DVDROP	0x10
438 #define	NCF_NEGATIVE	0x20
439 #define	NCF_INVALID	0x40
440 #define	NCF_WIP		0x80
441 
442 /*
443  * Flags in negstate.neg_flag
444  */
445 #define NEG_HOT		0x01
446 
447 static bool	cache_neg_evict_cond(u_long lnumcache);
448 
449 /*
450  * Mark an entry as invalid.
451  *
452  * This is called before it starts getting deconstructed.
453  */
454 static void
455 cache_ncp_invalidate(struct namecache *ncp)
456 {
457 
458 	KASSERT((ncp->nc_flag & NCF_INVALID) == 0,
459 	    ("%s: entry %p already invalid", __func__, ncp));
460 	atomic_store_char(&ncp->nc_flag, ncp->nc_flag | NCF_INVALID);
461 	atomic_thread_fence_rel();
462 }
463 
464 /*
465  * Check whether the entry can be safely used.
466  *
467  * All places which elide locks are supposed to call this after they are
468  * done with reading from an entry.
469  */
470 #define cache_ncp_canuse(ncp)	({					\
471 	struct namecache *_ncp = (ncp);					\
472 	u_char _nc_flag;						\
473 									\
474 	atomic_thread_fence_acq();					\
475 	_nc_flag = atomic_load_char(&_ncp->nc_flag);			\
476 	__predict_true((_nc_flag & (NCF_INVALID | NCF_WIP)) == 0);	\
477 })
478 
479 /*
480  * Like the above but also checks NCF_WHITE.
481  */
482 #define cache_fpl_neg_ncp_canuse(ncp)	({				\
483 	struct namecache *_ncp = (ncp);					\
484 	u_char _nc_flag;						\
485 									\
486 	atomic_thread_fence_acq();					\
487 	_nc_flag = atomic_load_char(&_ncp->nc_flag);			\
488 	__predict_true((_nc_flag & (NCF_INVALID | NCF_WIP | NCF_WHITE)) == 0);	\
489 })
490 
491 VFS_SMR_DECLARE;
492 
493 static SYSCTL_NODE(_vfs_cache, OID_AUTO, param, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
494     "Name cache parameters");
495 
496 static u_int __read_mostly	ncsize; /* the size as computed on creation or resizing */
497 SYSCTL_UINT(_vfs_cache_param, OID_AUTO, size, CTLFLAG_RD, &ncsize, 0,
498     "Total namecache capacity");
499 
500 u_int ncsizefactor = 2;
501 SYSCTL_UINT(_vfs_cache_param, OID_AUTO, sizefactor, CTLFLAG_RW, &ncsizefactor, 0,
502     "Size factor for namecache");
503 
504 static u_long __read_mostly	ncnegfactor = 5; /* ratio of negative entries */
505 SYSCTL_ULONG(_vfs_cache_param, OID_AUTO, negfactor, CTLFLAG_RW, &ncnegfactor, 0,
506     "Ratio of negative namecache entries");
507 
508 /*
509  * Negative entry % of namecache capacity above which automatic eviction is allowed.
510  *
511  * Check cache_neg_evict_cond for details.
512  */
513 static u_int ncnegminpct = 3;
514 
515 static u_int __read_mostly     neg_min; /* the above recomputed against ncsize */
516 SYSCTL_UINT(_vfs_cache_param, OID_AUTO, negmin, CTLFLAG_RD, &neg_min, 0,
517     "Negative entry count above which automatic eviction is allowed");
518 
519 /*
520  * Structures associated with name caching.
521  */
522 #define NCHHASH(hash) \
523 	(&nchashtbl[(hash) & nchash])
524 static __read_mostly CK_SLIST_HEAD(nchashhead, namecache) *nchashtbl;/* Hash Table */
525 static u_long __read_mostly	nchash;			/* size of hash table */
526 SYSCTL_ULONG(_debug, OID_AUTO, nchash, CTLFLAG_RD, &nchash, 0,
527     "Size of namecache hash table");
528 static u_long __exclusive_cache_line	numneg;	/* number of negative entries allocated */
529 static u_long __exclusive_cache_line	numcache;/* number of cache entries allocated */
530 
531 struct nchstats	nchstats;		/* cache effectiveness statistics */
532 
533 static u_int __exclusive_cache_line neg_cycle;
534 
535 #define ncneghash	3
536 #define	numneglists	(ncneghash + 1)
537 
538 struct neglist {
539 	struct mtx		nl_evict_lock;
540 	struct mtx		nl_lock __aligned(CACHE_LINE_SIZE);
541 	TAILQ_HEAD(, namecache) nl_list;
542 	TAILQ_HEAD(, namecache) nl_hotlist;
543 	u_long			nl_hotnum;
544 } __aligned(CACHE_LINE_SIZE);
545 
546 static struct neglist neglists[numneglists];
547 
548 static inline struct neglist *
549 NCP2NEGLIST(struct namecache *ncp)
550 {
551 
552 	return (&neglists[(((uintptr_t)(ncp) >> 8) & ncneghash)]);
553 }
554 
555 static inline struct negstate *
556 NCP2NEGSTATE(struct namecache *ncp)
557 {
558 
559 	MPASS(atomic_load_char(&ncp->nc_flag) & NCF_NEGATIVE);
560 	return (&ncp->nc_neg);
561 }
562 
563 #define	numbucketlocks (ncbuckethash + 1)
564 static u_int __read_mostly  ncbuckethash;
565 static struct mtx_padalign __read_mostly  *bucketlocks;
566 #define	HASH2BUCKETLOCK(hash) \
567 	((struct mtx *)(&bucketlocks[((hash) & ncbuckethash)]))
568 
569 #define	numvnodelocks (ncvnodehash + 1)
570 static u_int __read_mostly  ncvnodehash;
571 static struct mtx __read_mostly *vnodelocks;
572 static inline struct mtx *
573 VP2VNODELOCK(struct vnode *vp)
574 {
575 
576 	return (&vnodelocks[(((uintptr_t)(vp) >> 8) & ncvnodehash)]);
577 }
578 
579 static void
580 cache_out_ts(struct namecache *ncp, struct timespec *tsp, int *ticksp)
581 {
582 	struct namecache_ts *ncp_ts;
583 
584 	KASSERT((ncp->nc_flag & NCF_TS) != 0 ||
585 	    (tsp == NULL && ticksp == NULL),
586 	    ("No NCF_TS"));
587 
588 	if (tsp == NULL)
589 		return;
590 
591 	ncp_ts = __containerof(ncp, struct namecache_ts, nc_nc);
592 	*tsp = ncp_ts->nc_time;
593 	*ticksp = ncp_ts->nc_ticks;
594 }
595 
596 #ifdef DEBUG_CACHE
597 static int __read_mostly	doingcache = 1;	/* 1 => enable the cache */
598 SYSCTL_INT(_debug, OID_AUTO, vfscache, CTLFLAG_RW, &doingcache, 0,
599     "VFS namecache enabled");
600 #endif
601 
602 /* Export size information to userland */
603 SYSCTL_INT(_debug_sizeof, OID_AUTO, namecache, CTLFLAG_RD, SYSCTL_NULL_INT_PTR,
604     sizeof(struct namecache), "sizeof(struct namecache)");
605 
606 /*
607  * The new name cache statistics
608  */
609 static SYSCTL_NODE(_vfs_cache, OID_AUTO, stats, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
610     "Name cache statistics");
611 
612 #define STATNODE_ULONG(name, varname, descr)					\
613 	SYSCTL_ULONG(_vfs_cache_stats, OID_AUTO, name, CTLFLAG_RD, &varname, 0, descr);
614 #define STATNODE_COUNTER(name, varname, descr)					\
615 	static COUNTER_U64_DEFINE_EARLY(varname);				\
616 	SYSCTL_COUNTER_U64(_vfs_cache_stats, OID_AUTO, name, CTLFLAG_RD, &varname, \
617 	    descr);
618 STATNODE_ULONG(neg, numneg, "Number of negative cache entries");
619 STATNODE_ULONG(count, numcache, "Number of cache entries");
620 STATNODE_COUNTER(heldvnodes, numcachehv, "Number of namecache entries with vnodes held");
621 STATNODE_COUNTER(drops, numdrops, "Number of dropped entries due to reaching the limit");
622 STATNODE_COUNTER(miss, nummiss, "Number of cache misses");
623 STATNODE_COUNTER(misszap, nummisszap, "Number of cache misses we do not want to cache");
624 STATNODE_COUNTER(poszaps, numposzaps,
625     "Number of cache hits (positive) we do not want to cache");
626 STATNODE_COUNTER(poshits, numposhits, "Number of cache hits (positive)");
627 STATNODE_COUNTER(negzaps, numnegzaps,
628     "Number of cache hits (negative) we do not want to cache");
629 STATNODE_COUNTER(neghits, numneghits, "Number of cache hits (negative)");
630 /* These count for vn_getcwd(), too. */
631 STATNODE_COUNTER(fullpathcalls, numfullpathcalls, "Number of fullpath search calls");
632 STATNODE_COUNTER(fullpathfail2, numfullpathfail2,
633     "Number of fullpath search errors (VOP_VPTOCNP failures)");
634 STATNODE_COUNTER(fullpathfail4, numfullpathfail4, "Number of fullpath search errors (ENOMEM)");
635 STATNODE_COUNTER(fullpathfound, numfullpathfound, "Number of successful fullpath calls");
636 STATNODE_COUNTER(symlinktoobig, symlinktoobig, "Number of times symlink did not fit the cache");
637 
638 /*
639  * Debug or developer statistics.
640  */
641 static SYSCTL_NODE(_vfs_cache, OID_AUTO, debug, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
642     "Name cache debugging");
643 #define DEBUGNODE_ULONG(name, varname, descr)					\
644 	SYSCTL_ULONG(_vfs_cache_debug, OID_AUTO, name, CTLFLAG_RD, &varname, 0, descr);
645 static u_long zap_bucket_relock_success;
646 DEBUGNODE_ULONG(zap_bucket_relock_success, zap_bucket_relock_success,
647     "Number of successful removals after relocking");
648 static u_long zap_bucket_fail;
649 DEBUGNODE_ULONG(zap_bucket_fail, zap_bucket_fail, "");
650 static u_long zap_bucket_fail2;
651 DEBUGNODE_ULONG(zap_bucket_fail2, zap_bucket_fail2, "");
652 static u_long cache_lock_vnodes_cel_3_failures;
653 DEBUGNODE_ULONG(vnodes_cel_3_failures, cache_lock_vnodes_cel_3_failures,
654     "Number of times 3-way vnode locking failed");
655 
656 static void cache_zap_locked(struct namecache *ncp);
657 static int vn_fullpath_any_smr(struct vnode *vp, struct vnode *rdir, char *buf,
658     char **retbuf, size_t *buflen, size_t addend);
659 static int vn_fullpath_any(struct vnode *vp, struct vnode *rdir, char *buf,
660     char **retbuf, size_t *buflen);
661 static int vn_fullpath_dir(struct vnode *vp, struct vnode *rdir, char *buf,
662     char **retbuf, size_t *len, size_t addend);
663 
664 static MALLOC_DEFINE(M_VFSCACHE, "vfscache", "VFS name cache entries");
665 
666 static inline void
667 cache_assert_vlp_locked(struct mtx *vlp)
668 {
669 
670 	if (vlp != NULL)
671 		mtx_assert(vlp, MA_OWNED);
672 }
673 
674 static inline void
675 cache_assert_vnode_locked(struct vnode *vp)
676 {
677 	struct mtx *vlp;
678 
679 	vlp = VP2VNODELOCK(vp);
680 	cache_assert_vlp_locked(vlp);
681 }
682 
683 /*
684  * Directory vnodes with entries are held for two reasons:
685  * 1. make them less of a target for reclamation in vnlru
686  * 2. suffer smaller performance penalty in locked lookup as requeieing is avoided
687  *
688  * It will be feasible to stop doing it altogether if all filesystems start
689  * supporting lockless lookup.
690  */
691 static void
692 cache_hold_vnode(struct vnode *vp)
693 {
694 
695 	cache_assert_vnode_locked(vp);
696 	VNPASS(LIST_EMPTY(&vp->v_cache_src), vp);
697 	vhold(vp);
698 	counter_u64_add(numcachehv, 1);
699 }
700 
701 static void
702 cache_drop_vnode(struct vnode *vp)
703 {
704 
705 	/*
706 	 * Called after all locks are dropped, meaning we can't assert
707 	 * on the state of v_cache_src.
708 	 */
709 	vdrop(vp);
710 	counter_u64_add(numcachehv, -1);
711 }
712 
713 /*
714  * UMA zones.
715  */
716 static uma_zone_t __read_mostly cache_zone_small;
717 static uma_zone_t __read_mostly cache_zone_small_ts;
718 static uma_zone_t __read_mostly cache_zone_large;
719 static uma_zone_t __read_mostly cache_zone_large_ts;
720 
721 char *
722 cache_symlink_alloc(size_t size, int flags)
723 {
724 
725 	if (size < CACHE_ZONE_SMALL_SIZE) {
726 		return (uma_zalloc_smr(cache_zone_small, flags));
727 	}
728 	if (size < CACHE_ZONE_LARGE_SIZE) {
729 		return (uma_zalloc_smr(cache_zone_large, flags));
730 	}
731 	counter_u64_add(symlinktoobig, 1);
732 	SDT_PROBE1(vfs, namecache, symlink, alloc__fail, size);
733 	return (NULL);
734 }
735 
736 void
737 cache_symlink_free(char *string, size_t size)
738 {
739 
740 	MPASS(string != NULL);
741 	KASSERT(size < CACHE_ZONE_LARGE_SIZE,
742 	    ("%s: size %zu too big", __func__, size));
743 
744 	if (size < CACHE_ZONE_SMALL_SIZE) {
745 		uma_zfree_smr(cache_zone_small, string);
746 		return;
747 	}
748 	if (size < CACHE_ZONE_LARGE_SIZE) {
749 		uma_zfree_smr(cache_zone_large, string);
750 		return;
751 	}
752 	__assert_unreachable();
753 }
754 
755 static struct namecache *
756 cache_alloc_uma(int len, bool ts)
757 {
758 	struct namecache_ts *ncp_ts;
759 	struct namecache *ncp;
760 
761 	if (__predict_false(ts)) {
762 		if (len <= CACHE_PATH_CUTOFF)
763 			ncp_ts = uma_zalloc_smr(cache_zone_small_ts, M_WAITOK);
764 		else
765 			ncp_ts = uma_zalloc_smr(cache_zone_large_ts, M_WAITOK);
766 		ncp = &ncp_ts->nc_nc;
767 	} else {
768 		if (len <= CACHE_PATH_CUTOFF)
769 			ncp = uma_zalloc_smr(cache_zone_small, M_WAITOK);
770 		else
771 			ncp = uma_zalloc_smr(cache_zone_large, M_WAITOK);
772 	}
773 	return (ncp);
774 }
775 
776 static void
777 cache_free_uma(struct namecache *ncp)
778 {
779 	struct namecache_ts *ncp_ts;
780 
781 	if (__predict_false(ncp->nc_flag & NCF_TS)) {
782 		ncp_ts = __containerof(ncp, struct namecache_ts, nc_nc);
783 		if (ncp->nc_nlen <= CACHE_PATH_CUTOFF)
784 			uma_zfree_smr(cache_zone_small_ts, ncp_ts);
785 		else
786 			uma_zfree_smr(cache_zone_large_ts, ncp_ts);
787 	} else {
788 		if (ncp->nc_nlen <= CACHE_PATH_CUTOFF)
789 			uma_zfree_smr(cache_zone_small, ncp);
790 		else
791 			uma_zfree_smr(cache_zone_large, ncp);
792 	}
793 }
794 
795 static struct namecache *
796 cache_alloc(int len, bool ts)
797 {
798 	u_long lnumcache;
799 
800 	/*
801 	 * Avoid blowout in namecache entries.
802 	 *
803 	 * Bugs:
804 	 * 1. filesystems may end up trying to add an already existing entry
805 	 * (for example this can happen after a cache miss during concurrent
806 	 * lookup), in which case we will call cache_neg_evict despite not
807 	 * adding anything.
808 	 * 2. the routine may fail to free anything and no provisions are made
809 	 * to make it try harder (see the inside for failure modes)
810 	 * 3. it only ever looks at negative entries.
811 	 */
812 	lnumcache = atomic_fetchadd_long(&numcache, 1) + 1;
813 	if (cache_neg_evict_cond(lnumcache)) {
814 		lnumcache = atomic_load_long(&numcache);
815 	}
816 	if (__predict_false(lnumcache >= ncsize)) {
817 		atomic_subtract_long(&numcache, 1);
818 		counter_u64_add(numdrops, 1);
819 		return (NULL);
820 	}
821 	return (cache_alloc_uma(len, ts));
822 }
823 
824 static void
825 cache_free(struct namecache *ncp)
826 {
827 
828 	MPASS(ncp != NULL);
829 	if ((ncp->nc_flag & NCF_DVDROP) != 0) {
830 		cache_drop_vnode(ncp->nc_dvp);
831 	}
832 	cache_free_uma(ncp);
833 	atomic_subtract_long(&numcache, 1);
834 }
835 
836 static void
837 cache_free_batch(struct cache_freebatch *batch)
838 {
839 	struct namecache *ncp, *nnp;
840 	int i;
841 
842 	i = 0;
843 	if (TAILQ_EMPTY(batch))
844 		goto out;
845 	TAILQ_FOREACH_SAFE(ncp, batch, nc_dst, nnp) {
846 		if ((ncp->nc_flag & NCF_DVDROP) != 0) {
847 			cache_drop_vnode(ncp->nc_dvp);
848 		}
849 		cache_free_uma(ncp);
850 		i++;
851 	}
852 	atomic_subtract_long(&numcache, i);
853 out:
854 	SDT_PROBE1(vfs, namecache, purge, batch, i);
855 }
856 
857 /*
858  * Hashing.
859  *
860  * The code was made to use FNV in 2001 and this choice needs to be revisited.
861  *
862  * Short summary of the difficulty:
863  * The longest name which can be inserted is NAME_MAX characters in length (or
864  * 255 at the time of writing this comment), while majority of names used in
865  * practice are significantly shorter (mostly below 10). More importantly
866  * majority of lookups performed find names are even shorter than that.
867  *
868  * This poses a problem where hashes which do better than FNV past word size
869  * (or so) tend to come with additional overhead when finalizing the result,
870  * making them noticeably slower for the most commonly used range.
871  *
872  * Consider a path like: /usr/obj/usr/src/sys/amd64/GENERIC/vnode_if.c
873  *
874  * When looking it up the most time consuming part by a large margin (at least
875  * on amd64) is hashing.  Replacing FNV with something which pessimizes short
876  * input would make the slowest part stand out even more.
877  */
878 
879 /*
880  * TODO: With the value stored we can do better than computing the hash based
881  * on the address.
882  */
883 static void
884 cache_prehash(struct vnode *vp)
885 {
886 
887 	vp->v_nchash = fnv_32_buf(&vp, sizeof(vp), FNV1_32_INIT);
888 }
889 
890 static uint32_t
891 cache_get_hash(char *name, u_char len, struct vnode *dvp)
892 {
893 
894 	return (fnv_32_buf(name, len, dvp->v_nchash));
895 }
896 
897 static uint32_t
898 cache_get_hash_iter_start(struct vnode *dvp)
899 {
900 
901 	return (dvp->v_nchash);
902 }
903 
904 static uint32_t
905 cache_get_hash_iter(char c, uint32_t hash)
906 {
907 
908 	return (fnv_32_buf(&c, 1, hash));
909 }
910 
911 static uint32_t
912 cache_get_hash_iter_finish(uint32_t hash)
913 {
914 
915 	return (hash);
916 }
917 
918 static inline struct nchashhead *
919 NCP2BUCKET(struct namecache *ncp)
920 {
921 	uint32_t hash;
922 
923 	hash = cache_get_hash(ncp->nc_name, ncp->nc_nlen, ncp->nc_dvp);
924 	return (NCHHASH(hash));
925 }
926 
927 static inline struct mtx *
928 NCP2BUCKETLOCK(struct namecache *ncp)
929 {
930 	uint32_t hash;
931 
932 	hash = cache_get_hash(ncp->nc_name, ncp->nc_nlen, ncp->nc_dvp);
933 	return (HASH2BUCKETLOCK(hash));
934 }
935 
936 #ifdef INVARIANTS
937 static void
938 cache_assert_bucket_locked(struct namecache *ncp)
939 {
940 	struct mtx *blp;
941 
942 	blp = NCP2BUCKETLOCK(ncp);
943 	mtx_assert(blp, MA_OWNED);
944 }
945 
946 static void
947 cache_assert_bucket_unlocked(struct namecache *ncp)
948 {
949 	struct mtx *blp;
950 
951 	blp = NCP2BUCKETLOCK(ncp);
952 	mtx_assert(blp, MA_NOTOWNED);
953 }
954 #else
955 #define cache_assert_bucket_locked(x) do { } while (0)
956 #define cache_assert_bucket_unlocked(x) do { } while (0)
957 #endif
958 
959 #define cache_sort_vnodes(x, y)	_cache_sort_vnodes((void **)(x), (void **)(y))
960 static void
961 _cache_sort_vnodes(void **p1, void **p2)
962 {
963 	void *tmp;
964 
965 	MPASS(*p1 != NULL || *p2 != NULL);
966 
967 	if (*p1 > *p2) {
968 		tmp = *p2;
969 		*p2 = *p1;
970 		*p1 = tmp;
971 	}
972 }
973 
974 static void
975 cache_lock_all_buckets(void)
976 {
977 	u_int i;
978 
979 	for (i = 0; i < numbucketlocks; i++)
980 		mtx_lock(&bucketlocks[i]);
981 }
982 
983 static void
984 cache_unlock_all_buckets(void)
985 {
986 	u_int i;
987 
988 	for (i = 0; i < numbucketlocks; i++)
989 		mtx_unlock(&bucketlocks[i]);
990 }
991 
992 static void
993 cache_lock_all_vnodes(void)
994 {
995 	u_int i;
996 
997 	for (i = 0; i < numvnodelocks; i++)
998 		mtx_lock(&vnodelocks[i]);
999 }
1000 
1001 static void
1002 cache_unlock_all_vnodes(void)
1003 {
1004 	u_int i;
1005 
1006 	for (i = 0; i < numvnodelocks; i++)
1007 		mtx_unlock(&vnodelocks[i]);
1008 }
1009 
1010 static int
1011 cache_trylock_vnodes(struct mtx *vlp1, struct mtx *vlp2)
1012 {
1013 
1014 	cache_sort_vnodes(&vlp1, &vlp2);
1015 
1016 	if (vlp1 != NULL) {
1017 		if (!mtx_trylock(vlp1))
1018 			return (EAGAIN);
1019 	}
1020 	if (!mtx_trylock(vlp2)) {
1021 		if (vlp1 != NULL)
1022 			mtx_unlock(vlp1);
1023 		return (EAGAIN);
1024 	}
1025 
1026 	return (0);
1027 }
1028 
1029 static void
1030 cache_lock_vnodes(struct mtx *vlp1, struct mtx *vlp2)
1031 {
1032 
1033 	MPASS(vlp1 != NULL || vlp2 != NULL);
1034 	MPASS(vlp1 <= vlp2);
1035 
1036 	if (vlp1 != NULL)
1037 		mtx_lock(vlp1);
1038 	if (vlp2 != NULL)
1039 		mtx_lock(vlp2);
1040 }
1041 
1042 static void
1043 cache_unlock_vnodes(struct mtx *vlp1, struct mtx *vlp2)
1044 {
1045 
1046 	MPASS(vlp1 != NULL || vlp2 != NULL);
1047 
1048 	if (vlp1 != NULL)
1049 		mtx_unlock(vlp1);
1050 	if (vlp2 != NULL)
1051 		mtx_unlock(vlp2);
1052 }
1053 
1054 static int
1055 sysctl_nchstats(SYSCTL_HANDLER_ARGS)
1056 {
1057 	struct nchstats snap;
1058 
1059 	if (req->oldptr == NULL)
1060 		return (SYSCTL_OUT(req, 0, sizeof(snap)));
1061 
1062 	snap = nchstats;
1063 	snap.ncs_goodhits = counter_u64_fetch(numposhits);
1064 	snap.ncs_neghits = counter_u64_fetch(numneghits);
1065 	snap.ncs_badhits = counter_u64_fetch(numposzaps) +
1066 	    counter_u64_fetch(numnegzaps);
1067 	snap.ncs_miss = counter_u64_fetch(nummisszap) +
1068 	    counter_u64_fetch(nummiss);
1069 
1070 	return (SYSCTL_OUT(req, &snap, sizeof(snap)));
1071 }
1072 SYSCTL_PROC(_vfs_cache, OID_AUTO, nchstats, CTLTYPE_OPAQUE | CTLFLAG_RD |
1073     CTLFLAG_MPSAFE, 0, 0, sysctl_nchstats, "LU",
1074     "VFS cache effectiveness statistics");
1075 
1076 static void
1077 cache_recalc_neg_min(void)
1078 {
1079 
1080 	neg_min = (ncsize * ncnegminpct) / 100;
1081 }
1082 
1083 static int
1084 sysctl_negminpct(SYSCTL_HANDLER_ARGS)
1085 {
1086 	u_int val;
1087 	int error;
1088 
1089 	val = ncnegminpct;
1090 	error = sysctl_handle_int(oidp, &val, 0, req);
1091 	if (error != 0 || req->newptr == NULL)
1092 		return (error);
1093 
1094 	if (val == ncnegminpct)
1095 		return (0);
1096 	if (val < 0 || val > 99)
1097 		return (EINVAL);
1098 	ncnegminpct = val;
1099 	cache_recalc_neg_min();
1100 	return (0);
1101 }
1102 
1103 SYSCTL_PROC(_vfs_cache_param, OID_AUTO, negminpct,
1104     CTLTYPE_INT | CTLFLAG_MPSAFE | CTLFLAG_RW, NULL, 0, sysctl_negminpct,
1105     "I", "Negative entry \% of namecache capacity above which automatic eviction is allowed");
1106 
1107 #ifdef DEBUG_CACHE
1108 /*
1109  * Grab an atomic snapshot of the name cache hash chain lengths
1110  */
1111 static SYSCTL_NODE(_debug, OID_AUTO, hashstat,
1112     CTLFLAG_RW | CTLFLAG_MPSAFE, NULL,
1113     "hash table stats");
1114 
1115 static int
1116 sysctl_debug_hashstat_rawnchash(SYSCTL_HANDLER_ARGS)
1117 {
1118 	struct nchashhead *ncpp;
1119 	struct namecache *ncp;
1120 	int i, error, n_nchash, *cntbuf;
1121 
1122 retry:
1123 	n_nchash = nchash + 1;	/* nchash is max index, not count */
1124 	if (req->oldptr == NULL)
1125 		return SYSCTL_OUT(req, 0, n_nchash * sizeof(int));
1126 	cntbuf = malloc(n_nchash * sizeof(int), M_TEMP, M_ZERO | M_WAITOK);
1127 	cache_lock_all_buckets();
1128 	if (n_nchash != nchash + 1) {
1129 		cache_unlock_all_buckets();
1130 		free(cntbuf, M_TEMP);
1131 		goto retry;
1132 	}
1133 	/* Scan hash tables counting entries */
1134 	for (ncpp = nchashtbl, i = 0; i < n_nchash; ncpp++, i++)
1135 		CK_SLIST_FOREACH(ncp, ncpp, nc_hash)
1136 			cntbuf[i]++;
1137 	cache_unlock_all_buckets();
1138 	for (error = 0, i = 0; i < n_nchash; i++)
1139 		if ((error = SYSCTL_OUT(req, &cntbuf[i], sizeof(int))) != 0)
1140 			break;
1141 	free(cntbuf, M_TEMP);
1142 	return (error);
1143 }
1144 SYSCTL_PROC(_debug_hashstat, OID_AUTO, rawnchash, CTLTYPE_INT|CTLFLAG_RD|
1145     CTLFLAG_MPSAFE, 0, 0, sysctl_debug_hashstat_rawnchash, "S,int",
1146     "nchash chain lengths");
1147 
1148 static int
1149 sysctl_debug_hashstat_nchash(SYSCTL_HANDLER_ARGS)
1150 {
1151 	int error;
1152 	struct nchashhead *ncpp;
1153 	struct namecache *ncp;
1154 	int n_nchash;
1155 	int count, maxlength, used, pct;
1156 
1157 	if (!req->oldptr)
1158 		return SYSCTL_OUT(req, 0, 4 * sizeof(int));
1159 
1160 	cache_lock_all_buckets();
1161 	n_nchash = nchash + 1;	/* nchash is max index, not count */
1162 	used = 0;
1163 	maxlength = 0;
1164 
1165 	/* Scan hash tables for applicable entries */
1166 	for (ncpp = nchashtbl; n_nchash > 0; n_nchash--, ncpp++) {
1167 		count = 0;
1168 		CK_SLIST_FOREACH(ncp, ncpp, nc_hash) {
1169 			count++;
1170 		}
1171 		if (count)
1172 			used++;
1173 		if (maxlength < count)
1174 			maxlength = count;
1175 	}
1176 	n_nchash = nchash + 1;
1177 	cache_unlock_all_buckets();
1178 	pct = (used * 100) / (n_nchash / 100);
1179 	error = SYSCTL_OUT(req, &n_nchash, sizeof(n_nchash));
1180 	if (error)
1181 		return (error);
1182 	error = SYSCTL_OUT(req, &used, sizeof(used));
1183 	if (error)
1184 		return (error);
1185 	error = SYSCTL_OUT(req, &maxlength, sizeof(maxlength));
1186 	if (error)
1187 		return (error);
1188 	error = SYSCTL_OUT(req, &pct, sizeof(pct));
1189 	if (error)
1190 		return (error);
1191 	return (0);
1192 }
1193 SYSCTL_PROC(_debug_hashstat, OID_AUTO, nchash, CTLTYPE_INT|CTLFLAG_RD|
1194     CTLFLAG_MPSAFE, 0, 0, sysctl_debug_hashstat_nchash, "I",
1195     "nchash statistics (number of total/used buckets, maximum chain length, usage percentage)");
1196 #endif
1197 
1198 /*
1199  * Negative entries management
1200  *
1201  * Various workloads create plenty of negative entries and barely use them
1202  * afterwards. Moreover malicious users can keep performing bogus lookups
1203  * adding even more entries. For example "make tinderbox" as of writing this
1204  * comment ends up with 2.6M namecache entries in total, 1.2M of which are
1205  * negative.
1206  *
1207  * As such, a rather aggressive eviction method is needed. The currently
1208  * employed method is a placeholder.
1209  *
1210  * Entries are split over numneglists separate lists, each of which is further
1211  * split into hot and cold entries. Entries get promoted after getting a hit.
1212  * Eviction happens on addition of new entry.
1213  */
1214 static SYSCTL_NODE(_vfs_cache, OID_AUTO, neg, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
1215     "Name cache negative entry statistics");
1216 
1217 SYSCTL_ULONG(_vfs_cache_neg, OID_AUTO, count, CTLFLAG_RD, &numneg, 0,
1218     "Number of negative cache entries");
1219 
1220 static COUNTER_U64_DEFINE_EARLY(neg_created);
1221 SYSCTL_COUNTER_U64(_vfs_cache_neg, OID_AUTO, created, CTLFLAG_RD, &neg_created,
1222     "Number of created negative entries");
1223 
1224 static COUNTER_U64_DEFINE_EARLY(neg_evicted);
1225 SYSCTL_COUNTER_U64(_vfs_cache_neg, OID_AUTO, evicted, CTLFLAG_RD, &neg_evicted,
1226     "Number of evicted negative entries");
1227 
1228 static COUNTER_U64_DEFINE_EARLY(neg_evict_skipped_empty);
1229 SYSCTL_COUNTER_U64(_vfs_cache_neg, OID_AUTO, evict_skipped_empty, CTLFLAG_RD,
1230     &neg_evict_skipped_empty,
1231     "Number of times evicting failed due to lack of entries");
1232 
1233 static COUNTER_U64_DEFINE_EARLY(neg_evict_skipped_missed);
1234 SYSCTL_COUNTER_U64(_vfs_cache_neg, OID_AUTO, evict_skipped_missed, CTLFLAG_RD,
1235     &neg_evict_skipped_missed,
1236     "Number of times evicting failed due to target entry disappearing");
1237 
1238 static COUNTER_U64_DEFINE_EARLY(neg_evict_skipped_contended);
1239 SYSCTL_COUNTER_U64(_vfs_cache_neg, OID_AUTO, evict_skipped_contended, CTLFLAG_RD,
1240     &neg_evict_skipped_contended,
1241     "Number of times evicting failed due to contention");
1242 
1243 SYSCTL_COUNTER_U64(_vfs_cache_neg, OID_AUTO, hits, CTLFLAG_RD, &numneghits,
1244     "Number of cache hits (negative)");
1245 
1246 static int
1247 sysctl_neg_hot(SYSCTL_HANDLER_ARGS)
1248 {
1249 	int i, out;
1250 
1251 	out = 0;
1252 	for (i = 0; i < numneglists; i++)
1253 		out += neglists[i].nl_hotnum;
1254 
1255 	return (SYSCTL_OUT(req, &out, sizeof(out)));
1256 }
1257 SYSCTL_PROC(_vfs_cache_neg, OID_AUTO, hot, CTLTYPE_INT | CTLFLAG_RD |
1258     CTLFLAG_MPSAFE, 0, 0, sysctl_neg_hot, "I",
1259     "Number of hot negative entries");
1260 
1261 static void
1262 cache_neg_init(struct namecache *ncp)
1263 {
1264 	struct negstate *ns;
1265 
1266 	ncp->nc_flag |= NCF_NEGATIVE;
1267 	ns = NCP2NEGSTATE(ncp);
1268 	ns->neg_flag = 0;
1269 	ns->neg_hit = 0;
1270 	counter_u64_add(neg_created, 1);
1271 }
1272 
1273 #define CACHE_NEG_PROMOTION_THRESH 2
1274 
1275 static bool
1276 cache_neg_hit_prep(struct namecache *ncp)
1277 {
1278 	struct negstate *ns;
1279 	u_char n;
1280 
1281 	ns = NCP2NEGSTATE(ncp);
1282 	n = atomic_load_char(&ns->neg_hit);
1283 	for (;;) {
1284 		if (n >= CACHE_NEG_PROMOTION_THRESH)
1285 			return (false);
1286 		if (atomic_fcmpset_8(&ns->neg_hit, &n, n + 1))
1287 			break;
1288 	}
1289 	return (n + 1 == CACHE_NEG_PROMOTION_THRESH);
1290 }
1291 
1292 /*
1293  * Nothing to do here but it is provided for completeness as some
1294  * cache_neg_hit_prep callers may end up returning without even
1295  * trying to promote.
1296  */
1297 #define cache_neg_hit_abort(ncp)	do { } while (0)
1298 
1299 static void
1300 cache_neg_hit_finish(struct namecache *ncp)
1301 {
1302 
1303 	SDT_PROBE2(vfs, namecache, lookup, hit__negative, ncp->nc_dvp, ncp->nc_name);
1304 	counter_u64_add(numneghits, 1);
1305 }
1306 
1307 /*
1308  * Move a negative entry to the hot list.
1309  */
1310 static void
1311 cache_neg_promote_locked(struct namecache *ncp)
1312 {
1313 	struct neglist *nl;
1314 	struct negstate *ns;
1315 
1316 	ns = NCP2NEGSTATE(ncp);
1317 	nl = NCP2NEGLIST(ncp);
1318 	mtx_assert(&nl->nl_lock, MA_OWNED);
1319 	if ((ns->neg_flag & NEG_HOT) == 0) {
1320 		TAILQ_REMOVE(&nl->nl_list, ncp, nc_dst);
1321 		TAILQ_INSERT_TAIL(&nl->nl_hotlist, ncp, nc_dst);
1322 		nl->nl_hotnum++;
1323 		ns->neg_flag |= NEG_HOT;
1324 	}
1325 }
1326 
1327 /*
1328  * Move a hot negative entry to the cold list.
1329  */
1330 static void
1331 cache_neg_demote_locked(struct namecache *ncp)
1332 {
1333 	struct neglist *nl;
1334 	struct negstate *ns;
1335 
1336 	ns = NCP2NEGSTATE(ncp);
1337 	nl = NCP2NEGLIST(ncp);
1338 	mtx_assert(&nl->nl_lock, MA_OWNED);
1339 	MPASS(ns->neg_flag & NEG_HOT);
1340 	TAILQ_REMOVE(&nl->nl_hotlist, ncp, nc_dst);
1341 	TAILQ_INSERT_TAIL(&nl->nl_list, ncp, nc_dst);
1342 	nl->nl_hotnum--;
1343 	ns->neg_flag &= ~NEG_HOT;
1344 	atomic_store_char(&ns->neg_hit, 0);
1345 }
1346 
1347 /*
1348  * Move a negative entry to the hot list if it matches the lookup.
1349  *
1350  * We have to take locks, but they may be contended and in the worst
1351  * case we may need to go off CPU. We don't want to spin within the
1352  * smr section and we can't block with it. Exiting the section means
1353  * the found entry could have been evicted. We are going to look it
1354  * up again.
1355  */
1356 static bool
1357 cache_neg_promote_cond(struct vnode *dvp, struct componentname *cnp,
1358     struct namecache *oncp, uint32_t hash)
1359 {
1360 	struct namecache *ncp;
1361 	struct neglist *nl;
1362 	u_char nc_flag;
1363 
1364 	nl = NCP2NEGLIST(oncp);
1365 
1366 	mtx_lock(&nl->nl_lock);
1367 	/*
1368 	 * For hash iteration.
1369 	 */
1370 	vfs_smr_enter();
1371 
1372 	/*
1373 	 * Avoid all surprises by only succeeding if we got the same entry and
1374 	 * bailing completely otherwise.
1375 	 * XXX There are no provisions to keep the vnode around, meaning we may
1376 	 * end up promoting a negative entry for a *new* vnode and returning
1377 	 * ENOENT on its account. This is the error we want to return anyway
1378 	 * and promotion is harmless.
1379 	 *
1380 	 * In particular at this point there can be a new ncp which matches the
1381 	 * search but hashes to a different neglist.
1382 	 */
1383 	CK_SLIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
1384 		if (ncp == oncp)
1385 			break;
1386 	}
1387 
1388 	/*
1389 	 * No match to begin with.
1390 	 */
1391 	if (__predict_false(ncp == NULL)) {
1392 		goto out_abort;
1393 	}
1394 
1395 	/*
1396 	 * The newly found entry may be something different...
1397 	 */
1398 	if (!(ncp->nc_dvp == dvp && ncp->nc_nlen == cnp->cn_namelen &&
1399 	    !bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen))) {
1400 		goto out_abort;
1401 	}
1402 
1403 	/*
1404 	 * ... and not even negative.
1405 	 */
1406 	nc_flag = atomic_load_char(&ncp->nc_flag);
1407 	if ((nc_flag & NCF_NEGATIVE) == 0) {
1408 		goto out_abort;
1409 	}
1410 
1411 	if (!cache_ncp_canuse(ncp)) {
1412 		goto out_abort;
1413 	}
1414 
1415 	cache_neg_promote_locked(ncp);
1416 	cache_neg_hit_finish(ncp);
1417 	vfs_smr_exit();
1418 	mtx_unlock(&nl->nl_lock);
1419 	return (true);
1420 out_abort:
1421 	vfs_smr_exit();
1422 	mtx_unlock(&nl->nl_lock);
1423 	return (false);
1424 }
1425 
1426 static void
1427 cache_neg_promote(struct namecache *ncp)
1428 {
1429 	struct neglist *nl;
1430 
1431 	nl = NCP2NEGLIST(ncp);
1432 	mtx_lock(&nl->nl_lock);
1433 	cache_neg_promote_locked(ncp);
1434 	mtx_unlock(&nl->nl_lock);
1435 }
1436 
1437 static void
1438 cache_neg_insert(struct namecache *ncp)
1439 {
1440 	struct neglist *nl;
1441 
1442 	MPASS(ncp->nc_flag & NCF_NEGATIVE);
1443 	cache_assert_bucket_locked(ncp);
1444 	nl = NCP2NEGLIST(ncp);
1445 	mtx_lock(&nl->nl_lock);
1446 	TAILQ_INSERT_TAIL(&nl->nl_list, ncp, nc_dst);
1447 	mtx_unlock(&nl->nl_lock);
1448 	atomic_add_long(&numneg, 1);
1449 }
1450 
1451 static void
1452 cache_neg_remove(struct namecache *ncp)
1453 {
1454 	struct neglist *nl;
1455 	struct negstate *ns;
1456 
1457 	cache_assert_bucket_locked(ncp);
1458 	nl = NCP2NEGLIST(ncp);
1459 	ns = NCP2NEGSTATE(ncp);
1460 	mtx_lock(&nl->nl_lock);
1461 	if ((ns->neg_flag & NEG_HOT) != 0) {
1462 		TAILQ_REMOVE(&nl->nl_hotlist, ncp, nc_dst);
1463 		nl->nl_hotnum--;
1464 	} else {
1465 		TAILQ_REMOVE(&nl->nl_list, ncp, nc_dst);
1466 	}
1467 	mtx_unlock(&nl->nl_lock);
1468 	atomic_subtract_long(&numneg, 1);
1469 }
1470 
1471 static struct neglist *
1472 cache_neg_evict_select_list(void)
1473 {
1474 	struct neglist *nl;
1475 	u_int c;
1476 
1477 	c = atomic_fetchadd_int(&neg_cycle, 1) + 1;
1478 	nl = &neglists[c % numneglists];
1479 	if (!mtx_trylock(&nl->nl_evict_lock)) {
1480 		counter_u64_add(neg_evict_skipped_contended, 1);
1481 		return (NULL);
1482 	}
1483 	return (nl);
1484 }
1485 
1486 static struct namecache *
1487 cache_neg_evict_select_entry(struct neglist *nl)
1488 {
1489 	struct namecache *ncp, *lncp;
1490 	struct negstate *ns, *lns;
1491 	int i;
1492 
1493 	mtx_assert(&nl->nl_evict_lock, MA_OWNED);
1494 	mtx_assert(&nl->nl_lock, MA_OWNED);
1495 	ncp = TAILQ_FIRST(&nl->nl_list);
1496 	if (ncp == NULL)
1497 		return (NULL);
1498 	lncp = ncp;
1499 	lns = NCP2NEGSTATE(lncp);
1500 	for (i = 1; i < 4; i++) {
1501 		ncp = TAILQ_NEXT(ncp, nc_dst);
1502 		if (ncp == NULL)
1503 			break;
1504 		ns = NCP2NEGSTATE(ncp);
1505 		if (ns->neg_hit < lns->neg_hit) {
1506 			lncp = ncp;
1507 			lns = ns;
1508 		}
1509 	}
1510 	return (lncp);
1511 }
1512 
1513 static bool
1514 cache_neg_evict(void)
1515 {
1516 	struct namecache *ncp, *ncp2;
1517 	struct neglist *nl;
1518 	struct vnode *dvp;
1519 	struct mtx *dvlp;
1520 	struct mtx *blp;
1521 	uint32_t hash;
1522 	u_char nlen;
1523 	bool evicted;
1524 
1525 	nl = cache_neg_evict_select_list();
1526 	if (nl == NULL) {
1527 		return (false);
1528 	}
1529 
1530 	mtx_lock(&nl->nl_lock);
1531 	ncp = TAILQ_FIRST(&nl->nl_hotlist);
1532 	if (ncp != NULL) {
1533 		cache_neg_demote_locked(ncp);
1534 	}
1535 	ncp = cache_neg_evict_select_entry(nl);
1536 	if (ncp == NULL) {
1537 		counter_u64_add(neg_evict_skipped_empty, 1);
1538 		mtx_unlock(&nl->nl_lock);
1539 		mtx_unlock(&nl->nl_evict_lock);
1540 		return (false);
1541 	}
1542 	nlen = ncp->nc_nlen;
1543 	dvp = ncp->nc_dvp;
1544 	hash = cache_get_hash(ncp->nc_name, nlen, dvp);
1545 	dvlp = VP2VNODELOCK(dvp);
1546 	blp = HASH2BUCKETLOCK(hash);
1547 	mtx_unlock(&nl->nl_lock);
1548 	mtx_unlock(&nl->nl_evict_lock);
1549 	mtx_lock(dvlp);
1550 	mtx_lock(blp);
1551 	/*
1552 	 * Note that since all locks were dropped above, the entry may be
1553 	 * gone or reallocated to be something else.
1554 	 */
1555 	CK_SLIST_FOREACH(ncp2, (NCHHASH(hash)), nc_hash) {
1556 		if (ncp2 == ncp && ncp2->nc_dvp == dvp &&
1557 		    ncp2->nc_nlen == nlen && (ncp2->nc_flag & NCF_NEGATIVE) != 0)
1558 			break;
1559 	}
1560 	if (ncp2 == NULL) {
1561 		counter_u64_add(neg_evict_skipped_missed, 1);
1562 		ncp = NULL;
1563 		evicted = false;
1564 	} else {
1565 		MPASS(dvlp == VP2VNODELOCK(ncp->nc_dvp));
1566 		MPASS(blp == NCP2BUCKETLOCK(ncp));
1567 		SDT_PROBE2(vfs, namecache, evict_negative, done, ncp->nc_dvp,
1568 		    ncp->nc_name);
1569 		cache_zap_locked(ncp);
1570 		counter_u64_add(neg_evicted, 1);
1571 		evicted = true;
1572 	}
1573 	mtx_unlock(blp);
1574 	mtx_unlock(dvlp);
1575 	if (ncp != NULL)
1576 		cache_free(ncp);
1577 	return (evicted);
1578 }
1579 
1580 /*
1581  * Maybe evict a negative entry to create more room.
1582  *
1583  * The ncnegfactor parameter limits what fraction of the total count
1584  * can comprise of negative entries. However, if the cache is just
1585  * warming up this leads to excessive evictions.  As such, ncnegminpct
1586  * (recomputed to neg_min) dictates whether the above should be
1587  * applied.
1588  *
1589  * Try evicting if the cache is close to full capacity regardless of
1590  * other considerations.
1591  */
1592 static bool
1593 cache_neg_evict_cond(u_long lnumcache)
1594 {
1595 	u_long lnumneg;
1596 
1597 	if (ncsize - 1000 < lnumcache)
1598 		goto out_evict;
1599 	lnumneg = atomic_load_long(&numneg);
1600 	if (lnumneg < neg_min)
1601 		return (false);
1602 	if (lnumneg * ncnegfactor < lnumcache)
1603 		return (false);
1604 out_evict:
1605 	return (cache_neg_evict());
1606 }
1607 
1608 /*
1609  * cache_zap_locked():
1610  *
1611  *   Removes a namecache entry from cache, whether it contains an actual
1612  *   pointer to a vnode or if it is just a negative cache entry.
1613  */
1614 static void
1615 cache_zap_locked(struct namecache *ncp)
1616 {
1617 	struct nchashhead *ncpp;
1618 	struct vnode *dvp, *vp;
1619 
1620 	dvp = ncp->nc_dvp;
1621 	vp = ncp->nc_vp;
1622 
1623 	if (!(ncp->nc_flag & NCF_NEGATIVE))
1624 		cache_assert_vnode_locked(vp);
1625 	cache_assert_vnode_locked(dvp);
1626 	cache_assert_bucket_locked(ncp);
1627 
1628 	cache_ncp_invalidate(ncp);
1629 
1630 	ncpp = NCP2BUCKET(ncp);
1631 	CK_SLIST_REMOVE(ncpp, ncp, namecache, nc_hash);
1632 	if (!(ncp->nc_flag & NCF_NEGATIVE)) {
1633 		SDT_PROBE3(vfs, namecache, zap, done, dvp, ncp->nc_name, vp);
1634 		TAILQ_REMOVE(&vp->v_cache_dst, ncp, nc_dst);
1635 		if (ncp == vp->v_cache_dd) {
1636 			atomic_store_ptr(&vp->v_cache_dd, NULL);
1637 		}
1638 	} else {
1639 		SDT_PROBE2(vfs, namecache, zap_negative, done, dvp, ncp->nc_name);
1640 		cache_neg_remove(ncp);
1641 	}
1642 	if (ncp->nc_flag & NCF_ISDOTDOT) {
1643 		if (ncp == dvp->v_cache_dd) {
1644 			atomic_store_ptr(&dvp->v_cache_dd, NULL);
1645 		}
1646 	} else {
1647 		LIST_REMOVE(ncp, nc_src);
1648 		if (LIST_EMPTY(&dvp->v_cache_src)) {
1649 			ncp->nc_flag |= NCF_DVDROP;
1650 		}
1651 	}
1652 }
1653 
1654 static void
1655 cache_zap_negative_locked_vnode_kl(struct namecache *ncp, struct vnode *vp)
1656 {
1657 	struct mtx *blp;
1658 
1659 	MPASS(ncp->nc_dvp == vp);
1660 	MPASS(ncp->nc_flag & NCF_NEGATIVE);
1661 	cache_assert_vnode_locked(vp);
1662 
1663 	blp = NCP2BUCKETLOCK(ncp);
1664 	mtx_lock(blp);
1665 	cache_zap_locked(ncp);
1666 	mtx_unlock(blp);
1667 }
1668 
1669 static bool
1670 cache_zap_locked_vnode_kl2(struct namecache *ncp, struct vnode *vp,
1671     struct mtx **vlpp)
1672 {
1673 	struct mtx *pvlp, *vlp1, *vlp2, *to_unlock;
1674 	struct mtx *blp;
1675 
1676 	MPASS(vp == ncp->nc_dvp || vp == ncp->nc_vp);
1677 	cache_assert_vnode_locked(vp);
1678 
1679 	if (ncp->nc_flag & NCF_NEGATIVE) {
1680 		if (*vlpp != NULL) {
1681 			mtx_unlock(*vlpp);
1682 			*vlpp = NULL;
1683 		}
1684 		cache_zap_negative_locked_vnode_kl(ncp, vp);
1685 		return (true);
1686 	}
1687 
1688 	pvlp = VP2VNODELOCK(vp);
1689 	blp = NCP2BUCKETLOCK(ncp);
1690 	vlp1 = VP2VNODELOCK(ncp->nc_dvp);
1691 	vlp2 = VP2VNODELOCK(ncp->nc_vp);
1692 
1693 	if (*vlpp == vlp1 || *vlpp == vlp2) {
1694 		to_unlock = *vlpp;
1695 		*vlpp = NULL;
1696 	} else {
1697 		if (*vlpp != NULL) {
1698 			mtx_unlock(*vlpp);
1699 			*vlpp = NULL;
1700 		}
1701 		cache_sort_vnodes(&vlp1, &vlp2);
1702 		if (vlp1 == pvlp) {
1703 			mtx_lock(vlp2);
1704 			to_unlock = vlp2;
1705 		} else {
1706 			if (!mtx_trylock(vlp1))
1707 				goto out_relock;
1708 			to_unlock = vlp1;
1709 		}
1710 	}
1711 	mtx_lock(blp);
1712 	cache_zap_locked(ncp);
1713 	mtx_unlock(blp);
1714 	if (to_unlock != NULL)
1715 		mtx_unlock(to_unlock);
1716 	return (true);
1717 
1718 out_relock:
1719 	mtx_unlock(vlp2);
1720 	mtx_lock(vlp1);
1721 	mtx_lock(vlp2);
1722 	MPASS(*vlpp == NULL);
1723 	*vlpp = vlp1;
1724 	return (false);
1725 }
1726 
1727 /*
1728  * If trylocking failed we can get here. We know enough to take all needed locks
1729  * in the right order and re-lookup the entry.
1730  */
1731 static int
1732 cache_zap_unlocked_bucket(struct namecache *ncp, struct componentname *cnp,
1733     struct vnode *dvp, struct mtx *dvlp, struct mtx *vlp, uint32_t hash,
1734     struct mtx *blp)
1735 {
1736 	struct namecache *rncp;
1737 	struct mtx *rvlp;
1738 
1739 	cache_assert_bucket_unlocked(ncp);
1740 
1741 	cache_sort_vnodes(&dvlp, &vlp);
1742 	cache_lock_vnodes(dvlp, vlp);
1743 	mtx_lock(blp);
1744 	CK_SLIST_FOREACH(rncp, (NCHHASH(hash)), nc_hash) {
1745 		if (rncp == ncp && rncp->nc_dvp == dvp &&
1746 		    rncp->nc_nlen == cnp->cn_namelen &&
1747 		    !bcmp(rncp->nc_name, cnp->cn_nameptr, rncp->nc_nlen))
1748 			break;
1749 	}
1750 
1751 	if (rncp == NULL)
1752 		goto out_mismatch;
1753 
1754 	if (!(ncp->nc_flag & NCF_NEGATIVE))
1755 		rvlp = VP2VNODELOCK(rncp->nc_vp);
1756 	else
1757 		rvlp = NULL;
1758 	if (rvlp != vlp)
1759 		goto out_mismatch;
1760 
1761 	cache_zap_locked(rncp);
1762 	mtx_unlock(blp);
1763 	cache_unlock_vnodes(dvlp, vlp);
1764 	atomic_add_long(&zap_bucket_relock_success, 1);
1765 	return (0);
1766 
1767 out_mismatch:
1768 	mtx_unlock(blp);
1769 	cache_unlock_vnodes(dvlp, vlp);
1770 	return (EAGAIN);
1771 }
1772 
1773 static int __noinline
1774 cache_zap_locked_bucket(struct namecache *ncp, struct componentname *cnp,
1775     uint32_t hash, struct mtx *blp)
1776 {
1777 	struct mtx *dvlp, *vlp;
1778 	struct vnode *dvp;
1779 
1780 	cache_assert_bucket_locked(ncp);
1781 
1782 	dvlp = VP2VNODELOCK(ncp->nc_dvp);
1783 	vlp = NULL;
1784 	if (!(ncp->nc_flag & NCF_NEGATIVE))
1785 		vlp = VP2VNODELOCK(ncp->nc_vp);
1786 	if (cache_trylock_vnodes(dvlp, vlp) == 0) {
1787 		cache_zap_locked(ncp);
1788 		mtx_unlock(blp);
1789 		cache_unlock_vnodes(dvlp, vlp);
1790 		return (0);
1791 	}
1792 
1793 	dvp = ncp->nc_dvp;
1794 	mtx_unlock(blp);
1795 	return (cache_zap_unlocked_bucket(ncp, cnp, dvp, dvlp, vlp, hash, blp));
1796 }
1797 
1798 static __noinline int
1799 cache_remove_cnp(struct vnode *dvp, struct componentname *cnp)
1800 {
1801 	struct namecache *ncp;
1802 	struct mtx *blp;
1803 	struct mtx *dvlp, *dvlp2;
1804 	uint32_t hash;
1805 	int error;
1806 
1807 	if (cnp->cn_namelen == 2 &&
1808 	    cnp->cn_nameptr[0] == '.' && cnp->cn_nameptr[1] == '.') {
1809 		dvlp = VP2VNODELOCK(dvp);
1810 		dvlp2 = NULL;
1811 		mtx_lock(dvlp);
1812 retry_dotdot:
1813 		ncp = dvp->v_cache_dd;
1814 		if (ncp == NULL) {
1815 			mtx_unlock(dvlp);
1816 			if (dvlp2 != NULL)
1817 				mtx_unlock(dvlp2);
1818 			SDT_PROBE2(vfs, namecache, removecnp, miss, dvp, cnp);
1819 			return (0);
1820 		}
1821 		if ((ncp->nc_flag & NCF_ISDOTDOT) != 0) {
1822 			if (!cache_zap_locked_vnode_kl2(ncp, dvp, &dvlp2))
1823 				goto retry_dotdot;
1824 			MPASS(dvp->v_cache_dd == NULL);
1825 			mtx_unlock(dvlp);
1826 			if (dvlp2 != NULL)
1827 				mtx_unlock(dvlp2);
1828 			cache_free(ncp);
1829 		} else {
1830 			atomic_store_ptr(&dvp->v_cache_dd, NULL);
1831 			mtx_unlock(dvlp);
1832 			if (dvlp2 != NULL)
1833 				mtx_unlock(dvlp2);
1834 		}
1835 		SDT_PROBE2(vfs, namecache, removecnp, hit, dvp, cnp);
1836 		return (1);
1837 	}
1838 
1839 	/*
1840 	 * XXX note that access here is completely unlocked with no provisions
1841 	 * to keep the hash allocated. If one is sufficiently unlucky a
1842 	 * parallel cache resize can reallocate the hash, unmap backing pages
1843 	 * and cause the empty check below to fault.
1844 	 *
1845 	 * Fixing this has epsilon priority, but can be done with no overhead
1846 	 * for this codepath with sufficient effort.
1847 	 */
1848 	hash = cache_get_hash(cnp->cn_nameptr, cnp->cn_namelen, dvp);
1849 	blp = HASH2BUCKETLOCK(hash);
1850 retry:
1851 	if (CK_SLIST_EMPTY(NCHHASH(hash)))
1852 		goto out_no_entry;
1853 
1854 	mtx_lock(blp);
1855 
1856 	CK_SLIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
1857 		if (ncp->nc_dvp == dvp && ncp->nc_nlen == cnp->cn_namelen &&
1858 		    !bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen))
1859 			break;
1860 	}
1861 
1862 	if (ncp == NULL) {
1863 		mtx_unlock(blp);
1864 		goto out_no_entry;
1865 	}
1866 
1867 	error = cache_zap_locked_bucket(ncp, cnp, hash, blp);
1868 	if (__predict_false(error != 0)) {
1869 		atomic_add_long(&zap_bucket_fail, 1);
1870 		goto retry;
1871 	}
1872 	counter_u64_add(numposzaps, 1);
1873 	SDT_PROBE2(vfs, namecache, removecnp, hit, dvp, cnp);
1874 	cache_free(ncp);
1875 	return (1);
1876 out_no_entry:
1877 	counter_u64_add(nummisszap, 1);
1878 	SDT_PROBE2(vfs, namecache, removecnp, miss, dvp, cnp);
1879 	return (0);
1880 }
1881 
1882 static int __noinline
1883 cache_lookup_dot(struct vnode *dvp, struct vnode **vpp, struct componentname *cnp,
1884     struct timespec *tsp, int *ticksp)
1885 {
1886 	int ltype;
1887 
1888 	*vpp = dvp;
1889 	SDT_PROBE3(vfs, namecache, lookup, hit, dvp, ".", *vpp);
1890 	if (tsp != NULL)
1891 		timespecclear(tsp);
1892 	if (ticksp != NULL)
1893 		*ticksp = ticks;
1894 	vrefact(*vpp);
1895 	/*
1896 	 * When we lookup "." we still can be asked to lock it
1897 	 * differently...
1898 	 */
1899 	ltype = cnp->cn_lkflags & LK_TYPE_MASK;
1900 	if (ltype != VOP_ISLOCKED(*vpp)) {
1901 		if (ltype == LK_EXCLUSIVE) {
1902 			vn_lock(*vpp, LK_UPGRADE | LK_RETRY);
1903 			if (VN_IS_DOOMED((*vpp))) {
1904 				/* forced unmount */
1905 				vrele(*vpp);
1906 				*vpp = NULL;
1907 				return (ENOENT);
1908 			}
1909 		} else
1910 			vn_lock(*vpp, LK_DOWNGRADE | LK_RETRY);
1911 	}
1912 	return (-1);
1913 }
1914 
1915 static int __noinline
1916 cache_lookup_dotdot(struct vnode *dvp, struct vnode **vpp, struct componentname *cnp,
1917     struct timespec *tsp, int *ticksp)
1918 {
1919 	struct namecache_ts *ncp_ts;
1920 	struct namecache *ncp;
1921 	struct mtx *dvlp;
1922 	enum vgetstate vs;
1923 	int error, ltype;
1924 	bool whiteout;
1925 
1926 	MPASS((cnp->cn_flags & ISDOTDOT) != 0);
1927 
1928 	if ((cnp->cn_flags & MAKEENTRY) == 0) {
1929 		cache_remove_cnp(dvp, cnp);
1930 		return (0);
1931 	}
1932 
1933 retry:
1934 	dvlp = VP2VNODELOCK(dvp);
1935 	mtx_lock(dvlp);
1936 	ncp = dvp->v_cache_dd;
1937 	if (ncp == NULL) {
1938 		SDT_PROBE2(vfs, namecache, lookup, miss, dvp, "..");
1939 		mtx_unlock(dvlp);
1940 		return (0);
1941 	}
1942 	if ((ncp->nc_flag & NCF_ISDOTDOT) != 0) {
1943 		if (ncp->nc_flag & NCF_NEGATIVE)
1944 			*vpp = NULL;
1945 		else
1946 			*vpp = ncp->nc_vp;
1947 	} else
1948 		*vpp = ncp->nc_dvp;
1949 	if (*vpp == NULL)
1950 		goto negative_success;
1951 	SDT_PROBE3(vfs, namecache, lookup, hit, dvp, "..", *vpp);
1952 	cache_out_ts(ncp, tsp, ticksp);
1953 	if ((ncp->nc_flag & (NCF_ISDOTDOT | NCF_DTS)) ==
1954 	    NCF_DTS && tsp != NULL) {
1955 		ncp_ts = __containerof(ncp, struct namecache_ts, nc_nc);
1956 		*tsp = ncp_ts->nc_dotdottime;
1957 	}
1958 
1959 	MPASS(dvp != *vpp);
1960 	ltype = VOP_ISLOCKED(dvp);
1961 	VOP_UNLOCK(dvp);
1962 	vs = vget_prep(*vpp);
1963 	mtx_unlock(dvlp);
1964 	error = vget_finish(*vpp, cnp->cn_lkflags, vs);
1965 	vn_lock(dvp, ltype | LK_RETRY);
1966 	if (VN_IS_DOOMED(dvp)) {
1967 		if (error == 0)
1968 			vput(*vpp);
1969 		*vpp = NULL;
1970 		return (ENOENT);
1971 	}
1972 	if (error) {
1973 		*vpp = NULL;
1974 		goto retry;
1975 	}
1976 	return (-1);
1977 negative_success:
1978 	if (__predict_false(cnp->cn_nameiop == CREATE)) {
1979 		if (cnp->cn_flags & ISLASTCN) {
1980 			counter_u64_add(numnegzaps, 1);
1981 			cache_zap_negative_locked_vnode_kl(ncp, dvp);
1982 			mtx_unlock(dvlp);
1983 			cache_free(ncp);
1984 			return (0);
1985 		}
1986 	}
1987 
1988 	whiteout = (ncp->nc_flag & NCF_WHITE);
1989 	cache_out_ts(ncp, tsp, ticksp);
1990 	if (cache_neg_hit_prep(ncp))
1991 		cache_neg_promote(ncp);
1992 	else
1993 		cache_neg_hit_finish(ncp);
1994 	mtx_unlock(dvlp);
1995 	if (whiteout)
1996 		cnp->cn_flags |= ISWHITEOUT;
1997 	return (ENOENT);
1998 }
1999 
2000 /**
2001  * Lookup a name in the name cache
2002  *
2003  * # Arguments
2004  *
2005  * - dvp:	Parent directory in which to search.
2006  * - vpp:	Return argument.  Will contain desired vnode on cache hit.
2007  * - cnp:	Parameters of the name search.  The most interesting bits of
2008  *   		the cn_flags field have the following meanings:
2009  *   	- MAKEENTRY:	If clear, free an entry from the cache rather than look
2010  *   			it up.
2011  *   	- ISDOTDOT:	Must be set if and only if cn_nameptr == ".."
2012  * - tsp:	Return storage for cache timestamp.  On a successful (positive
2013  *   		or negative) lookup, tsp will be filled with any timespec that
2014  *   		was stored when this cache entry was created.  However, it will
2015  *   		be clear for "." entries.
2016  * - ticks:	Return storage for alternate cache timestamp.  On a successful
2017  *   		(positive or negative) lookup, it will contain the ticks value
2018  *   		that was current when the cache entry was created, unless cnp
2019  *   		was ".".
2020  *
2021  * Either both tsp and ticks have to be provided or neither of them.
2022  *
2023  * # Returns
2024  *
2025  * - -1:	A positive cache hit.  vpp will contain the desired vnode.
2026  * - ENOENT:	A negative cache hit, or dvp was recycled out from under us due
2027  *		to a forced unmount.  vpp will not be modified.  If the entry
2028  *		is a whiteout, then the ISWHITEOUT flag will be set in
2029  *		cnp->cn_flags.
2030  * - 0:		A cache miss.  vpp will not be modified.
2031  *
2032  * # Locking
2033  *
2034  * On a cache hit, vpp will be returned locked and ref'd.  If we're looking up
2035  * .., dvp is unlocked.  If we're looking up . an extra ref is taken, but the
2036  * lock is not recursively acquired.
2037  */
2038 static int __noinline
2039 cache_lookup_fallback(struct vnode *dvp, struct vnode **vpp, struct componentname *cnp,
2040     struct timespec *tsp, int *ticksp)
2041 {
2042 	struct namecache *ncp;
2043 	struct mtx *blp;
2044 	uint32_t hash;
2045 	enum vgetstate vs;
2046 	int error;
2047 	bool whiteout;
2048 
2049 	MPASS((cnp->cn_flags & ISDOTDOT) == 0);
2050 	MPASS((cnp->cn_flags & (MAKEENTRY | NC_KEEPPOSENTRY)) != 0);
2051 
2052 retry:
2053 	hash = cache_get_hash(cnp->cn_nameptr, cnp->cn_namelen, dvp);
2054 	blp = HASH2BUCKETLOCK(hash);
2055 	mtx_lock(blp);
2056 
2057 	CK_SLIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
2058 		if (ncp->nc_dvp == dvp && ncp->nc_nlen == cnp->cn_namelen &&
2059 		    !bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen))
2060 			break;
2061 	}
2062 
2063 	if (__predict_false(ncp == NULL)) {
2064 		mtx_unlock(blp);
2065 		SDT_PROBE2(vfs, namecache, lookup, miss, dvp, cnp->cn_nameptr);
2066 		counter_u64_add(nummiss, 1);
2067 		return (0);
2068 	}
2069 
2070 	if (ncp->nc_flag & NCF_NEGATIVE)
2071 		goto negative_success;
2072 
2073 	counter_u64_add(numposhits, 1);
2074 	*vpp = ncp->nc_vp;
2075 	SDT_PROBE3(vfs, namecache, lookup, hit, dvp, ncp->nc_name, *vpp);
2076 	cache_out_ts(ncp, tsp, ticksp);
2077 	MPASS(dvp != *vpp);
2078 	vs = vget_prep(*vpp);
2079 	mtx_unlock(blp);
2080 	error = vget_finish(*vpp, cnp->cn_lkflags, vs);
2081 	if (error) {
2082 		*vpp = NULL;
2083 		goto retry;
2084 	}
2085 	return (-1);
2086 negative_success:
2087 	/*
2088 	 * We don't get here with regular lookup apart from corner cases.
2089 	 */
2090 	if (__predict_true(cnp->cn_nameiop == CREATE)) {
2091 		if (cnp->cn_flags & ISLASTCN) {
2092 			counter_u64_add(numnegzaps, 1);
2093 			error = cache_zap_locked_bucket(ncp, cnp, hash, blp);
2094 			if (__predict_false(error != 0)) {
2095 				atomic_add_long(&zap_bucket_fail2, 1);
2096 				goto retry;
2097 			}
2098 			cache_free(ncp);
2099 			return (0);
2100 		}
2101 	}
2102 
2103 	whiteout = (ncp->nc_flag & NCF_WHITE);
2104 	cache_out_ts(ncp, tsp, ticksp);
2105 	if (cache_neg_hit_prep(ncp))
2106 		cache_neg_promote(ncp);
2107 	else
2108 		cache_neg_hit_finish(ncp);
2109 	mtx_unlock(blp);
2110 	if (whiteout)
2111 		cnp->cn_flags |= ISWHITEOUT;
2112 	return (ENOENT);
2113 }
2114 
2115 int
2116 cache_lookup(struct vnode *dvp, struct vnode **vpp, struct componentname *cnp,
2117     struct timespec *tsp, int *ticksp)
2118 {
2119 	struct namecache *ncp;
2120 	uint32_t hash;
2121 	enum vgetstate vs;
2122 	int error;
2123 	bool whiteout, neg_promote;
2124 	u_short nc_flag;
2125 
2126 	MPASS((tsp == NULL && ticksp == NULL) || (tsp != NULL && ticksp != NULL));
2127 
2128 #ifdef DEBUG_CACHE
2129 	if (__predict_false(!doingcache)) {
2130 		cnp->cn_flags &= ~MAKEENTRY;
2131 		return (0);
2132 	}
2133 #endif
2134 
2135 	if (__predict_false(cnp->cn_nameptr[0] == '.')) {
2136 		if (cnp->cn_namelen == 1)
2137 			return (cache_lookup_dot(dvp, vpp, cnp, tsp, ticksp));
2138 		if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.')
2139 			return (cache_lookup_dotdot(dvp, vpp, cnp, tsp, ticksp));
2140 	}
2141 
2142 	MPASS((cnp->cn_flags & ISDOTDOT) == 0);
2143 
2144 	if ((cnp->cn_flags & (MAKEENTRY | NC_KEEPPOSENTRY)) == 0) {
2145 		cache_remove_cnp(dvp, cnp);
2146 		return (0);
2147 	}
2148 
2149 	hash = cache_get_hash(cnp->cn_nameptr, cnp->cn_namelen, dvp);
2150 	vfs_smr_enter();
2151 
2152 	CK_SLIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
2153 		if (ncp->nc_dvp == dvp && ncp->nc_nlen == cnp->cn_namelen &&
2154 		    !bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen))
2155 			break;
2156 	}
2157 
2158 	if (__predict_false(ncp == NULL)) {
2159 		vfs_smr_exit();
2160 		SDT_PROBE2(vfs, namecache, lookup, miss, dvp, cnp->cn_nameptr);
2161 		counter_u64_add(nummiss, 1);
2162 		return (0);
2163 	}
2164 
2165 	nc_flag = atomic_load_char(&ncp->nc_flag);
2166 	if (nc_flag & NCF_NEGATIVE)
2167 		goto negative_success;
2168 
2169 	counter_u64_add(numposhits, 1);
2170 	*vpp = ncp->nc_vp;
2171 	SDT_PROBE3(vfs, namecache, lookup, hit, dvp, ncp->nc_name, *vpp);
2172 	cache_out_ts(ncp, tsp, ticksp);
2173 	MPASS(dvp != *vpp);
2174 	if (!cache_ncp_canuse(ncp)) {
2175 		vfs_smr_exit();
2176 		*vpp = NULL;
2177 		goto out_fallback;
2178 	}
2179 	vs = vget_prep_smr(*vpp);
2180 	vfs_smr_exit();
2181 	if (__predict_false(vs == VGET_NONE)) {
2182 		*vpp = NULL;
2183 		goto out_fallback;
2184 	}
2185 	error = vget_finish(*vpp, cnp->cn_lkflags, vs);
2186 	if (error) {
2187 		*vpp = NULL;
2188 		goto out_fallback;
2189 	}
2190 	return (-1);
2191 negative_success:
2192 	if (cnp->cn_nameiop == CREATE) {
2193 		if (cnp->cn_flags & ISLASTCN) {
2194 			vfs_smr_exit();
2195 			goto out_fallback;
2196 		}
2197 	}
2198 
2199 	cache_out_ts(ncp, tsp, ticksp);
2200 	whiteout = (atomic_load_char(&ncp->nc_flag) & NCF_WHITE);
2201 	neg_promote = cache_neg_hit_prep(ncp);
2202 	if (!cache_ncp_canuse(ncp)) {
2203 		cache_neg_hit_abort(ncp);
2204 		vfs_smr_exit();
2205 		goto out_fallback;
2206 	}
2207 	if (neg_promote) {
2208 		vfs_smr_exit();
2209 		if (!cache_neg_promote_cond(dvp, cnp, ncp, hash))
2210 			goto out_fallback;
2211 	} else {
2212 		cache_neg_hit_finish(ncp);
2213 		vfs_smr_exit();
2214 	}
2215 	if (whiteout)
2216 		cnp->cn_flags |= ISWHITEOUT;
2217 	return (ENOENT);
2218 out_fallback:
2219 	return (cache_lookup_fallback(dvp, vpp, cnp, tsp, ticksp));
2220 }
2221 
2222 struct celockstate {
2223 	struct mtx *vlp[3];
2224 	struct mtx *blp[2];
2225 };
2226 CTASSERT((nitems(((struct celockstate *)0)->vlp) == 3));
2227 CTASSERT((nitems(((struct celockstate *)0)->blp) == 2));
2228 
2229 static inline void
2230 cache_celockstate_init(struct celockstate *cel)
2231 {
2232 
2233 	bzero(cel, sizeof(*cel));
2234 }
2235 
2236 static void
2237 cache_lock_vnodes_cel(struct celockstate *cel, struct vnode *vp,
2238     struct vnode *dvp)
2239 {
2240 	struct mtx *vlp1, *vlp2;
2241 
2242 	MPASS(cel->vlp[0] == NULL);
2243 	MPASS(cel->vlp[1] == NULL);
2244 	MPASS(cel->vlp[2] == NULL);
2245 
2246 	MPASS(vp != NULL || dvp != NULL);
2247 
2248 	vlp1 = VP2VNODELOCK(vp);
2249 	vlp2 = VP2VNODELOCK(dvp);
2250 	cache_sort_vnodes(&vlp1, &vlp2);
2251 
2252 	if (vlp1 != NULL) {
2253 		mtx_lock(vlp1);
2254 		cel->vlp[0] = vlp1;
2255 	}
2256 	mtx_lock(vlp2);
2257 	cel->vlp[1] = vlp2;
2258 }
2259 
2260 static void
2261 cache_unlock_vnodes_cel(struct celockstate *cel)
2262 {
2263 
2264 	MPASS(cel->vlp[0] != NULL || cel->vlp[1] != NULL);
2265 
2266 	if (cel->vlp[0] != NULL)
2267 		mtx_unlock(cel->vlp[0]);
2268 	if (cel->vlp[1] != NULL)
2269 		mtx_unlock(cel->vlp[1]);
2270 	if (cel->vlp[2] != NULL)
2271 		mtx_unlock(cel->vlp[2]);
2272 }
2273 
2274 static bool
2275 cache_lock_vnodes_cel_3(struct celockstate *cel, struct vnode *vp)
2276 {
2277 	struct mtx *vlp;
2278 	bool ret;
2279 
2280 	cache_assert_vlp_locked(cel->vlp[0]);
2281 	cache_assert_vlp_locked(cel->vlp[1]);
2282 	MPASS(cel->vlp[2] == NULL);
2283 
2284 	MPASS(vp != NULL);
2285 	vlp = VP2VNODELOCK(vp);
2286 
2287 	ret = true;
2288 	if (vlp >= cel->vlp[1]) {
2289 		mtx_lock(vlp);
2290 	} else {
2291 		if (mtx_trylock(vlp))
2292 			goto out;
2293 		cache_unlock_vnodes_cel(cel);
2294 		atomic_add_long(&cache_lock_vnodes_cel_3_failures, 1);
2295 		if (vlp < cel->vlp[0]) {
2296 			mtx_lock(vlp);
2297 			mtx_lock(cel->vlp[0]);
2298 			mtx_lock(cel->vlp[1]);
2299 		} else {
2300 			if (cel->vlp[0] != NULL)
2301 				mtx_lock(cel->vlp[0]);
2302 			mtx_lock(vlp);
2303 			mtx_lock(cel->vlp[1]);
2304 		}
2305 		ret = false;
2306 	}
2307 out:
2308 	cel->vlp[2] = vlp;
2309 	return (ret);
2310 }
2311 
2312 static void
2313 cache_lock_buckets_cel(struct celockstate *cel, struct mtx *blp1,
2314     struct mtx *blp2)
2315 {
2316 
2317 	MPASS(cel->blp[0] == NULL);
2318 	MPASS(cel->blp[1] == NULL);
2319 
2320 	cache_sort_vnodes(&blp1, &blp2);
2321 
2322 	if (blp1 != NULL) {
2323 		mtx_lock(blp1);
2324 		cel->blp[0] = blp1;
2325 	}
2326 	mtx_lock(blp2);
2327 	cel->blp[1] = blp2;
2328 }
2329 
2330 static void
2331 cache_unlock_buckets_cel(struct celockstate *cel)
2332 {
2333 
2334 	if (cel->blp[0] != NULL)
2335 		mtx_unlock(cel->blp[0]);
2336 	mtx_unlock(cel->blp[1]);
2337 }
2338 
2339 /*
2340  * Lock part of the cache affected by the insertion.
2341  *
2342  * This means vnodelocks for dvp, vp and the relevant bucketlock.
2343  * However, insertion can result in removal of an old entry. In this
2344  * case we have an additional vnode and bucketlock pair to lock.
2345  *
2346  * That is, in the worst case we have to lock 3 vnodes and 2 bucketlocks, while
2347  * preserving the locking order (smaller address first).
2348  */
2349 static void
2350 cache_enter_lock(struct celockstate *cel, struct vnode *dvp, struct vnode *vp,
2351     uint32_t hash)
2352 {
2353 	struct namecache *ncp;
2354 	struct mtx *blps[2];
2355 	u_char nc_flag;
2356 
2357 	blps[0] = HASH2BUCKETLOCK(hash);
2358 	for (;;) {
2359 		blps[1] = NULL;
2360 		cache_lock_vnodes_cel(cel, dvp, vp);
2361 		if (vp == NULL || vp->v_type != VDIR)
2362 			break;
2363 		ncp = atomic_load_consume_ptr(&vp->v_cache_dd);
2364 		if (ncp == NULL)
2365 			break;
2366 		nc_flag = atomic_load_char(&ncp->nc_flag);
2367 		if ((nc_flag & NCF_ISDOTDOT) == 0)
2368 			break;
2369 		MPASS(ncp->nc_dvp == vp);
2370 		blps[1] = NCP2BUCKETLOCK(ncp);
2371 		if ((nc_flag & NCF_NEGATIVE) != 0)
2372 			break;
2373 		if (cache_lock_vnodes_cel_3(cel, ncp->nc_vp))
2374 			break;
2375 		/*
2376 		 * All vnodes got re-locked. Re-validate the state and if
2377 		 * nothing changed we are done. Otherwise restart.
2378 		 */
2379 		if (ncp == vp->v_cache_dd &&
2380 		    (ncp->nc_flag & NCF_ISDOTDOT) != 0 &&
2381 		    blps[1] == NCP2BUCKETLOCK(ncp) &&
2382 		    VP2VNODELOCK(ncp->nc_vp) == cel->vlp[2])
2383 			break;
2384 		cache_unlock_vnodes_cel(cel);
2385 		cel->vlp[0] = NULL;
2386 		cel->vlp[1] = NULL;
2387 		cel->vlp[2] = NULL;
2388 	}
2389 	cache_lock_buckets_cel(cel, blps[0], blps[1]);
2390 }
2391 
2392 static void
2393 cache_enter_lock_dd(struct celockstate *cel, struct vnode *dvp, struct vnode *vp,
2394     uint32_t hash)
2395 {
2396 	struct namecache *ncp;
2397 	struct mtx *blps[2];
2398 	u_char nc_flag;
2399 
2400 	blps[0] = HASH2BUCKETLOCK(hash);
2401 	for (;;) {
2402 		blps[1] = NULL;
2403 		cache_lock_vnodes_cel(cel, dvp, vp);
2404 		ncp = atomic_load_consume_ptr(&dvp->v_cache_dd);
2405 		if (ncp == NULL)
2406 			break;
2407 		nc_flag = atomic_load_char(&ncp->nc_flag);
2408 		if ((nc_flag & NCF_ISDOTDOT) == 0)
2409 			break;
2410 		MPASS(ncp->nc_dvp == dvp);
2411 		blps[1] = NCP2BUCKETLOCK(ncp);
2412 		if ((nc_flag & NCF_NEGATIVE) != 0)
2413 			break;
2414 		if (cache_lock_vnodes_cel_3(cel, ncp->nc_vp))
2415 			break;
2416 		if (ncp == dvp->v_cache_dd &&
2417 		    (ncp->nc_flag & NCF_ISDOTDOT) != 0 &&
2418 		    blps[1] == NCP2BUCKETLOCK(ncp) &&
2419 		    VP2VNODELOCK(ncp->nc_vp) == cel->vlp[2])
2420 			break;
2421 		cache_unlock_vnodes_cel(cel);
2422 		cel->vlp[0] = NULL;
2423 		cel->vlp[1] = NULL;
2424 		cel->vlp[2] = NULL;
2425 	}
2426 	cache_lock_buckets_cel(cel, blps[0], blps[1]);
2427 }
2428 
2429 static void
2430 cache_enter_unlock(struct celockstate *cel)
2431 {
2432 
2433 	cache_unlock_buckets_cel(cel);
2434 	cache_unlock_vnodes_cel(cel);
2435 }
2436 
2437 static void __noinline
2438 cache_enter_dotdot_prep(struct vnode *dvp, struct vnode *vp,
2439     struct componentname *cnp)
2440 {
2441 	struct celockstate cel;
2442 	struct namecache *ncp;
2443 	uint32_t hash;
2444 	int len;
2445 
2446 	if (atomic_load_ptr(&dvp->v_cache_dd) == NULL)
2447 		return;
2448 	len = cnp->cn_namelen;
2449 	cache_celockstate_init(&cel);
2450 	hash = cache_get_hash(cnp->cn_nameptr, len, dvp);
2451 	cache_enter_lock_dd(&cel, dvp, vp, hash);
2452 	ncp = dvp->v_cache_dd;
2453 	if (ncp != NULL && (ncp->nc_flag & NCF_ISDOTDOT)) {
2454 		KASSERT(ncp->nc_dvp == dvp, ("wrong isdotdot parent"));
2455 		cache_zap_locked(ncp);
2456 	} else {
2457 		ncp = NULL;
2458 	}
2459 	atomic_store_ptr(&dvp->v_cache_dd, NULL);
2460 	cache_enter_unlock(&cel);
2461 	if (ncp != NULL)
2462 		cache_free(ncp);
2463 }
2464 
2465 /*
2466  * Add an entry to the cache.
2467  */
2468 void
2469 cache_enter_time(struct vnode *dvp, struct vnode *vp, struct componentname *cnp,
2470     struct timespec *tsp, struct timespec *dtsp)
2471 {
2472 	struct celockstate cel;
2473 	struct namecache *ncp, *n2, *ndd;
2474 	struct namecache_ts *ncp_ts;
2475 	struct nchashhead *ncpp;
2476 	uint32_t hash;
2477 	int flag;
2478 	int len;
2479 
2480 	KASSERT(cnp->cn_namelen <= NAME_MAX,
2481 	    ("%s: passed len %ld exceeds NAME_MAX (%d)", __func__, cnp->cn_namelen,
2482 	    NAME_MAX));
2483 	VNPASS(!VN_IS_DOOMED(dvp), dvp);
2484 	VNPASS(dvp->v_type != VNON, dvp);
2485 	if (vp != NULL) {
2486 		VNPASS(!VN_IS_DOOMED(vp), vp);
2487 		VNPASS(vp->v_type != VNON, vp);
2488 	}
2489 	if (cnp->cn_namelen == 1 && cnp->cn_nameptr[0] == '.') {
2490 		KASSERT(dvp == vp,
2491 		    ("%s: different vnodes for dot entry (%p; %p)\n", __func__,
2492 		    dvp, vp));
2493 	} else {
2494 		KASSERT(dvp != vp,
2495 		    ("%s: same vnode for non-dot entry [%s] (%p)\n", __func__,
2496 		    cnp->cn_nameptr, dvp));
2497 	}
2498 
2499 #ifdef DEBUG_CACHE
2500 	if (__predict_false(!doingcache))
2501 		return;
2502 #endif
2503 
2504 	flag = 0;
2505 	if (__predict_false(cnp->cn_nameptr[0] == '.')) {
2506 		if (cnp->cn_namelen == 1)
2507 			return;
2508 		if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.') {
2509 			cache_enter_dotdot_prep(dvp, vp, cnp);
2510 			flag = NCF_ISDOTDOT;
2511 		}
2512 	}
2513 
2514 	ncp = cache_alloc(cnp->cn_namelen, tsp != NULL);
2515 	if (ncp == NULL)
2516 		return;
2517 
2518 	cache_celockstate_init(&cel);
2519 	ndd = NULL;
2520 	ncp_ts = NULL;
2521 
2522 	/*
2523 	 * Calculate the hash key and setup as much of the new
2524 	 * namecache entry as possible before acquiring the lock.
2525 	 */
2526 	ncp->nc_flag = flag | NCF_WIP;
2527 	ncp->nc_vp = vp;
2528 	if (vp == NULL)
2529 		cache_neg_init(ncp);
2530 	ncp->nc_dvp = dvp;
2531 	if (tsp != NULL) {
2532 		ncp_ts = __containerof(ncp, struct namecache_ts, nc_nc);
2533 		ncp_ts->nc_time = *tsp;
2534 		ncp_ts->nc_ticks = ticks;
2535 		ncp_ts->nc_nc.nc_flag |= NCF_TS;
2536 		if (dtsp != NULL) {
2537 			ncp_ts->nc_dotdottime = *dtsp;
2538 			ncp_ts->nc_nc.nc_flag |= NCF_DTS;
2539 		}
2540 	}
2541 	len = ncp->nc_nlen = cnp->cn_namelen;
2542 	hash = cache_get_hash(cnp->cn_nameptr, len, dvp);
2543 	memcpy(ncp->nc_name, cnp->cn_nameptr, len);
2544 	ncp->nc_name[len] = '\0';
2545 	cache_enter_lock(&cel, dvp, vp, hash);
2546 
2547 	/*
2548 	 * See if this vnode or negative entry is already in the cache
2549 	 * with this name.  This can happen with concurrent lookups of
2550 	 * the same path name.
2551 	 */
2552 	ncpp = NCHHASH(hash);
2553 	CK_SLIST_FOREACH(n2, ncpp, nc_hash) {
2554 		if (n2->nc_dvp == dvp &&
2555 		    n2->nc_nlen == cnp->cn_namelen &&
2556 		    !bcmp(n2->nc_name, cnp->cn_nameptr, n2->nc_nlen)) {
2557 			MPASS(cache_ncp_canuse(n2));
2558 			if ((n2->nc_flag & NCF_NEGATIVE) != 0)
2559 				KASSERT(vp == NULL,
2560 				    ("%s: found entry pointing to a different vnode (%p != %p) ; name [%s]",
2561 				    __func__, NULL, vp, cnp->cn_nameptr));
2562 			else
2563 				KASSERT(n2->nc_vp == vp,
2564 				    ("%s: found entry pointing to a different vnode (%p != %p) ; name [%s]",
2565 				    __func__, n2->nc_vp, vp, cnp->cn_nameptr));
2566 			/*
2567 			 * Entries are supposed to be immutable unless in the
2568 			 * process of getting destroyed. Accommodating for
2569 			 * changing timestamps is possible but not worth it.
2570 			 * This should be harmless in terms of correctness, in
2571 			 * the worst case resulting in an earlier expiration.
2572 			 * Alternatively, the found entry can be replaced
2573 			 * altogether.
2574 			 */
2575 			MPASS((n2->nc_flag & (NCF_TS | NCF_DTS)) == (ncp->nc_flag & (NCF_TS | NCF_DTS)));
2576 #if 0
2577 			if (tsp != NULL) {
2578 				KASSERT((n2->nc_flag & NCF_TS) != 0,
2579 				    ("no NCF_TS"));
2580 				n2_ts = __containerof(n2, struct namecache_ts, nc_nc);
2581 				n2_ts->nc_time = ncp_ts->nc_time;
2582 				n2_ts->nc_ticks = ncp_ts->nc_ticks;
2583 				if (dtsp != NULL) {
2584 					n2_ts->nc_dotdottime = ncp_ts->nc_dotdottime;
2585 					n2_ts->nc_nc.nc_flag |= NCF_DTS;
2586 				}
2587 			}
2588 #endif
2589 			SDT_PROBE3(vfs, namecache, enter, duplicate, dvp, ncp->nc_name,
2590 			    vp);
2591 			goto out_unlock_free;
2592 		}
2593 	}
2594 
2595 	if (flag == NCF_ISDOTDOT) {
2596 		/*
2597 		 * See if we are trying to add .. entry, but some other lookup
2598 		 * has populated v_cache_dd pointer already.
2599 		 */
2600 		if (dvp->v_cache_dd != NULL)
2601 			goto out_unlock_free;
2602 		KASSERT(vp == NULL || vp->v_type == VDIR,
2603 		    ("wrong vnode type %p", vp));
2604 		atomic_thread_fence_rel();
2605 		atomic_store_ptr(&dvp->v_cache_dd, ncp);
2606 	}
2607 
2608 	if (vp != NULL) {
2609 		if (flag != NCF_ISDOTDOT) {
2610 			/*
2611 			 * For this case, the cache entry maps both the
2612 			 * directory name in it and the name ".." for the
2613 			 * directory's parent.
2614 			 */
2615 			if ((ndd = vp->v_cache_dd) != NULL) {
2616 				if ((ndd->nc_flag & NCF_ISDOTDOT) != 0)
2617 					cache_zap_locked(ndd);
2618 				else
2619 					ndd = NULL;
2620 			}
2621 			atomic_thread_fence_rel();
2622 			atomic_store_ptr(&vp->v_cache_dd, ncp);
2623 		} else if (vp->v_type != VDIR) {
2624 			if (vp->v_cache_dd != NULL) {
2625 				atomic_store_ptr(&vp->v_cache_dd, NULL);
2626 			}
2627 		}
2628 	}
2629 
2630 	if (flag != NCF_ISDOTDOT) {
2631 		if (LIST_EMPTY(&dvp->v_cache_src)) {
2632 			cache_hold_vnode(dvp);
2633 		}
2634 		LIST_INSERT_HEAD(&dvp->v_cache_src, ncp, nc_src);
2635 	}
2636 
2637 	/*
2638 	 * If the entry is "negative", we place it into the
2639 	 * "negative" cache queue, otherwise, we place it into the
2640 	 * destination vnode's cache entries queue.
2641 	 */
2642 	if (vp != NULL) {
2643 		TAILQ_INSERT_HEAD(&vp->v_cache_dst, ncp, nc_dst);
2644 		SDT_PROBE3(vfs, namecache, enter, done, dvp, ncp->nc_name,
2645 		    vp);
2646 	} else {
2647 		if (cnp->cn_flags & ISWHITEOUT)
2648 			atomic_store_char(&ncp->nc_flag, ncp->nc_flag | NCF_WHITE);
2649 		cache_neg_insert(ncp);
2650 		SDT_PROBE2(vfs, namecache, enter_negative, done, dvp,
2651 		    ncp->nc_name);
2652 	}
2653 
2654 	/*
2655 	 * Insert the new namecache entry into the appropriate chain
2656 	 * within the cache entries table.
2657 	 */
2658 	CK_SLIST_INSERT_HEAD(ncpp, ncp, nc_hash);
2659 
2660 	atomic_thread_fence_rel();
2661 	/*
2662 	 * Mark the entry as fully constructed.
2663 	 * It is immutable past this point until its removal.
2664 	 */
2665 	atomic_store_char(&ncp->nc_flag, ncp->nc_flag & ~NCF_WIP);
2666 
2667 	cache_enter_unlock(&cel);
2668 	if (ndd != NULL)
2669 		cache_free(ndd);
2670 	return;
2671 out_unlock_free:
2672 	cache_enter_unlock(&cel);
2673 	cache_free(ncp);
2674 	return;
2675 }
2676 
2677 /*
2678  * A variant of the above accepting flags.
2679  *
2680  * - VFS_CACHE_DROPOLD -- if a conflicting entry is found, drop it.
2681  *
2682  * TODO: this routine is a hack. It blindly removes the old entry, even if it
2683  * happens to match and it is doing it in an inefficient manner. It was added
2684  * to accommodate NFS which runs into a case where the target for a given name
2685  * may change from under it. Note this does nothing to solve the following
2686  * race: 2 callers of cache_enter_time_flags pass a different target vnode for
2687  * the same [dvp, cnp]. It may be argued that code doing this is broken.
2688  */
2689 void
2690 cache_enter_time_flags(struct vnode *dvp, struct vnode *vp, struct componentname *cnp,
2691     struct timespec *tsp, struct timespec *dtsp, int flags)
2692 {
2693 
2694 	MPASS((flags & ~(VFS_CACHE_DROPOLD)) == 0);
2695 
2696 	if (flags & VFS_CACHE_DROPOLD)
2697 		cache_remove_cnp(dvp, cnp);
2698 	cache_enter_time(dvp, vp, cnp, tsp, dtsp);
2699 }
2700 
2701 static u_long
2702 cache_roundup_2(u_long val)
2703 {
2704 	u_long res;
2705 
2706 	for (res = 1; res <= val; res <<= 1)
2707 		continue;
2708 
2709 	return (res);
2710 }
2711 
2712 static struct nchashhead *
2713 nchinittbl(u_long elements, u_long *hashmask)
2714 {
2715 	struct nchashhead *hashtbl;
2716 	u_long hashsize, i;
2717 
2718 	hashsize = cache_roundup_2(elements) / 2;
2719 
2720 	hashtbl = malloc(hashsize * sizeof(*hashtbl), M_VFSCACHE, M_WAITOK);
2721 	for (i = 0; i < hashsize; i++)
2722 		CK_SLIST_INIT(&hashtbl[i]);
2723 	*hashmask = hashsize - 1;
2724 	return (hashtbl);
2725 }
2726 
2727 static void
2728 ncfreetbl(struct nchashhead *hashtbl)
2729 {
2730 
2731 	free(hashtbl, M_VFSCACHE);
2732 }
2733 
2734 /*
2735  * Name cache initialization, from vfs_init() when we are booting
2736  */
2737 static void
2738 nchinit(void *dummy __unused)
2739 {
2740 	u_int i;
2741 
2742 	cache_zone_small = uma_zcreate("S VFS Cache", CACHE_ZONE_SMALL_SIZE,
2743 	    NULL, NULL, NULL, NULL, CACHE_ZONE_ALIGNMENT, UMA_ZONE_ZINIT);
2744 	cache_zone_small_ts = uma_zcreate("STS VFS Cache", CACHE_ZONE_SMALL_TS_SIZE,
2745 	    NULL, NULL, NULL, NULL, CACHE_ZONE_ALIGNMENT, UMA_ZONE_ZINIT);
2746 	cache_zone_large = uma_zcreate("L VFS Cache", CACHE_ZONE_LARGE_SIZE,
2747 	    NULL, NULL, NULL, NULL, CACHE_ZONE_ALIGNMENT, UMA_ZONE_ZINIT);
2748 	cache_zone_large_ts = uma_zcreate("LTS VFS Cache", CACHE_ZONE_LARGE_TS_SIZE,
2749 	    NULL, NULL, NULL, NULL, CACHE_ZONE_ALIGNMENT, UMA_ZONE_ZINIT);
2750 
2751 	VFS_SMR_ZONE_SET(cache_zone_small);
2752 	VFS_SMR_ZONE_SET(cache_zone_small_ts);
2753 	VFS_SMR_ZONE_SET(cache_zone_large);
2754 	VFS_SMR_ZONE_SET(cache_zone_large_ts);
2755 
2756 	ncsize = desiredvnodes * ncsizefactor;
2757 	cache_recalc_neg_min();
2758 	nchashtbl = nchinittbl(desiredvnodes * 2, &nchash);
2759 	ncbuckethash = cache_roundup_2(mp_ncpus * mp_ncpus) - 1;
2760 	if (ncbuckethash < 7) /* arbitrarily chosen to avoid having one lock */
2761 		ncbuckethash = 7;
2762 	if (ncbuckethash > nchash)
2763 		ncbuckethash = nchash;
2764 	bucketlocks = malloc(sizeof(*bucketlocks) * numbucketlocks, M_VFSCACHE,
2765 	    M_WAITOK | M_ZERO);
2766 	for (i = 0; i < numbucketlocks; i++)
2767 		mtx_init(&bucketlocks[i], "ncbuc", NULL, MTX_DUPOK | MTX_RECURSE);
2768 	ncvnodehash = ncbuckethash;
2769 	vnodelocks = malloc(sizeof(*vnodelocks) * numvnodelocks, M_VFSCACHE,
2770 	    M_WAITOK | M_ZERO);
2771 	for (i = 0; i < numvnodelocks; i++)
2772 		mtx_init(&vnodelocks[i], "ncvn", NULL, MTX_DUPOK | MTX_RECURSE);
2773 
2774 	for (i = 0; i < numneglists; i++) {
2775 		mtx_init(&neglists[i].nl_evict_lock, "ncnege", NULL, MTX_DEF);
2776 		mtx_init(&neglists[i].nl_lock, "ncnegl", NULL, MTX_DEF);
2777 		TAILQ_INIT(&neglists[i].nl_list);
2778 		TAILQ_INIT(&neglists[i].nl_hotlist);
2779 	}
2780 }
2781 SYSINIT(vfs, SI_SUB_VFS, SI_ORDER_SECOND, nchinit, NULL);
2782 
2783 void
2784 cache_vnode_init(struct vnode *vp)
2785 {
2786 
2787 	LIST_INIT(&vp->v_cache_src);
2788 	TAILQ_INIT(&vp->v_cache_dst);
2789 	vp->v_cache_dd = NULL;
2790 	cache_prehash(vp);
2791 }
2792 
2793 /*
2794  * Induce transient cache misses for lockless operation in cache_lookup() by
2795  * using a temporary hash table.
2796  *
2797  * This will force a fs lookup.
2798  *
2799  * Synchronisation is done in 2 steps, calling vfs_smr_synchronize each time
2800  * to observe all CPUs not performing the lookup.
2801  */
2802 static void
2803 cache_changesize_set_temp(struct nchashhead *temptbl, u_long temphash)
2804 {
2805 
2806 	MPASS(temphash < nchash);
2807 	/*
2808 	 * Change the size. The new size is smaller and can safely be used
2809 	 * against the existing table. All lookups which now hash wrong will
2810 	 * result in a cache miss, which all callers are supposed to know how
2811 	 * to handle.
2812 	 */
2813 	atomic_store_long(&nchash, temphash);
2814 	atomic_thread_fence_rel();
2815 	vfs_smr_synchronize();
2816 	/*
2817 	 * At this point everyone sees the updated hash value, but they still
2818 	 * see the old table.
2819 	 */
2820 	atomic_store_ptr(&nchashtbl, temptbl);
2821 	atomic_thread_fence_rel();
2822 	vfs_smr_synchronize();
2823 	/*
2824 	 * At this point everyone sees the updated table pointer and size pair.
2825 	 */
2826 }
2827 
2828 /*
2829  * Set the new hash table.
2830  *
2831  * Similarly to cache_changesize_set_temp(), this has to synchronize against
2832  * lockless operation in cache_lookup().
2833  */
2834 static void
2835 cache_changesize_set_new(struct nchashhead *new_tbl, u_long new_hash)
2836 {
2837 
2838 	MPASS(nchash < new_hash);
2839 	/*
2840 	 * Change the pointer first. This wont result in out of bounds access
2841 	 * since the temporary table is guaranteed to be smaller.
2842 	 */
2843 	atomic_store_ptr(&nchashtbl, new_tbl);
2844 	atomic_thread_fence_rel();
2845 	vfs_smr_synchronize();
2846 	/*
2847 	 * At this point everyone sees the updated pointer value, but they
2848 	 * still see the old size.
2849 	 */
2850 	atomic_store_long(&nchash, new_hash);
2851 	atomic_thread_fence_rel();
2852 	vfs_smr_synchronize();
2853 	/*
2854 	 * At this point everyone sees the updated table pointer and size pair.
2855 	 */
2856 }
2857 
2858 void
2859 cache_changesize(u_long newmaxvnodes)
2860 {
2861 	struct nchashhead *new_nchashtbl, *old_nchashtbl, *temptbl;
2862 	u_long new_nchash, old_nchash, temphash;
2863 	struct namecache *ncp;
2864 	uint32_t hash;
2865 	u_long newncsize;
2866 	u_long i;
2867 
2868 	newncsize = newmaxvnodes * ncsizefactor;
2869 	newmaxvnodes = cache_roundup_2(newmaxvnodes * 2);
2870 	if (newmaxvnodes < numbucketlocks)
2871 		newmaxvnodes = numbucketlocks;
2872 
2873 	new_nchashtbl = nchinittbl(newmaxvnodes, &new_nchash);
2874 	/* If same hash table size, nothing to do */
2875 	if (nchash == new_nchash) {
2876 		ncfreetbl(new_nchashtbl);
2877 		return;
2878 	}
2879 
2880 	temptbl = nchinittbl(1, &temphash);
2881 
2882 	/*
2883 	 * Move everything from the old hash table to the new table.
2884 	 * None of the namecache entries in the table can be removed
2885 	 * because to do so, they have to be removed from the hash table.
2886 	 */
2887 	cache_lock_all_vnodes();
2888 	cache_lock_all_buckets();
2889 	old_nchashtbl = nchashtbl;
2890 	old_nchash = nchash;
2891 	cache_changesize_set_temp(temptbl, temphash);
2892 	for (i = 0; i <= old_nchash; i++) {
2893 		while ((ncp = CK_SLIST_FIRST(&old_nchashtbl[i])) != NULL) {
2894 			hash = cache_get_hash(ncp->nc_name, ncp->nc_nlen,
2895 			    ncp->nc_dvp);
2896 			CK_SLIST_REMOVE(&old_nchashtbl[i], ncp, namecache, nc_hash);
2897 			CK_SLIST_INSERT_HEAD(&new_nchashtbl[hash & new_nchash], ncp, nc_hash);
2898 		}
2899 	}
2900 	ncsize = newncsize;
2901 	cache_recalc_neg_min();
2902 	cache_changesize_set_new(new_nchashtbl, new_nchash);
2903 	cache_unlock_all_buckets();
2904 	cache_unlock_all_vnodes();
2905 	ncfreetbl(old_nchashtbl);
2906 	ncfreetbl(temptbl);
2907 }
2908 
2909 /*
2910  * Remove all entries from and to a particular vnode.
2911  */
2912 static void
2913 cache_purge_impl(struct vnode *vp)
2914 {
2915 	struct cache_freebatch batch;
2916 	struct namecache *ncp;
2917 	struct mtx *vlp, *vlp2;
2918 
2919 	TAILQ_INIT(&batch);
2920 	vlp = VP2VNODELOCK(vp);
2921 	vlp2 = NULL;
2922 	mtx_lock(vlp);
2923 retry:
2924 	while (!LIST_EMPTY(&vp->v_cache_src)) {
2925 		ncp = LIST_FIRST(&vp->v_cache_src);
2926 		if (!cache_zap_locked_vnode_kl2(ncp, vp, &vlp2))
2927 			goto retry;
2928 		TAILQ_INSERT_TAIL(&batch, ncp, nc_dst);
2929 	}
2930 	while (!TAILQ_EMPTY(&vp->v_cache_dst)) {
2931 		ncp = TAILQ_FIRST(&vp->v_cache_dst);
2932 		if (!cache_zap_locked_vnode_kl2(ncp, vp, &vlp2))
2933 			goto retry;
2934 		TAILQ_INSERT_TAIL(&batch, ncp, nc_dst);
2935 	}
2936 	ncp = vp->v_cache_dd;
2937 	if (ncp != NULL) {
2938 		KASSERT(ncp->nc_flag & NCF_ISDOTDOT,
2939 		   ("lost dotdot link"));
2940 		if (!cache_zap_locked_vnode_kl2(ncp, vp, &vlp2))
2941 			goto retry;
2942 		TAILQ_INSERT_TAIL(&batch, ncp, nc_dst);
2943 	}
2944 	KASSERT(vp->v_cache_dd == NULL, ("incomplete purge"));
2945 	mtx_unlock(vlp);
2946 	if (vlp2 != NULL)
2947 		mtx_unlock(vlp2);
2948 	cache_free_batch(&batch);
2949 }
2950 
2951 /*
2952  * Opportunistic check to see if there is anything to do.
2953  */
2954 static bool
2955 cache_has_entries(struct vnode *vp)
2956 {
2957 
2958 	if (LIST_EMPTY(&vp->v_cache_src) && TAILQ_EMPTY(&vp->v_cache_dst) &&
2959 	    atomic_load_ptr(&vp->v_cache_dd) == NULL)
2960 		return (false);
2961 	return (true);
2962 }
2963 
2964 void
2965 cache_purge(struct vnode *vp)
2966 {
2967 
2968 	SDT_PROBE1(vfs, namecache, purge, done, vp);
2969 	if (!cache_has_entries(vp))
2970 		return;
2971 	cache_purge_impl(vp);
2972 }
2973 
2974 /*
2975  * Only to be used by vgone.
2976  */
2977 void
2978 cache_purge_vgone(struct vnode *vp)
2979 {
2980 	struct mtx *vlp;
2981 
2982 	VNPASS(VN_IS_DOOMED(vp), vp);
2983 	if (cache_has_entries(vp)) {
2984 		cache_purge_impl(vp);
2985 		return;
2986 	}
2987 
2988 	/*
2989 	 * Serialize against a potential thread doing cache_purge.
2990 	 */
2991 	vlp = VP2VNODELOCK(vp);
2992 	mtx_wait_unlocked(vlp);
2993 	if (cache_has_entries(vp)) {
2994 		cache_purge_impl(vp);
2995 		return;
2996 	}
2997 	return;
2998 }
2999 
3000 /*
3001  * Remove all negative entries for a particular directory vnode.
3002  */
3003 void
3004 cache_purge_negative(struct vnode *vp)
3005 {
3006 	struct cache_freebatch batch;
3007 	struct namecache *ncp, *nnp;
3008 	struct mtx *vlp;
3009 
3010 	SDT_PROBE1(vfs, namecache, purge_negative, done, vp);
3011 	if (LIST_EMPTY(&vp->v_cache_src))
3012 		return;
3013 	TAILQ_INIT(&batch);
3014 	vlp = VP2VNODELOCK(vp);
3015 	mtx_lock(vlp);
3016 	LIST_FOREACH_SAFE(ncp, &vp->v_cache_src, nc_src, nnp) {
3017 		if (!(ncp->nc_flag & NCF_NEGATIVE))
3018 			continue;
3019 		cache_zap_negative_locked_vnode_kl(ncp, vp);
3020 		TAILQ_INSERT_TAIL(&batch, ncp, nc_dst);
3021 	}
3022 	mtx_unlock(vlp);
3023 	cache_free_batch(&batch);
3024 }
3025 
3026 /*
3027  * Entry points for modifying VOP operations.
3028  */
3029 void
3030 cache_vop_rename(struct vnode *fdvp, struct vnode *fvp, struct vnode *tdvp,
3031     struct vnode *tvp, struct componentname *fcnp, struct componentname *tcnp)
3032 {
3033 
3034 	ASSERT_VOP_IN_SEQC(fdvp);
3035 	ASSERT_VOP_IN_SEQC(fvp);
3036 	ASSERT_VOP_IN_SEQC(tdvp);
3037 	if (tvp != NULL)
3038 		ASSERT_VOP_IN_SEQC(tvp);
3039 
3040 	cache_purge(fvp);
3041 	if (tvp != NULL) {
3042 		cache_purge(tvp);
3043 		KASSERT(!cache_remove_cnp(tdvp, tcnp),
3044 		    ("%s: lingering negative entry", __func__));
3045 	} else {
3046 		cache_remove_cnp(tdvp, tcnp);
3047 	}
3048 
3049 	/*
3050 	 * TODO
3051 	 *
3052 	 * Historically renaming was always purging all revelang entries,
3053 	 * but that's quite wasteful. In particular turns out that in many cases
3054 	 * the target file is immediately accessed after rename, inducing a cache
3055 	 * miss.
3056 	 *
3057 	 * Recode this to reduce relocking and reuse the existing entry (if any)
3058 	 * instead of just removing it above and allocating a new one here.
3059 	 */
3060 	cache_enter(tdvp, fvp, tcnp);
3061 }
3062 
3063 void
3064 cache_vop_rmdir(struct vnode *dvp, struct vnode *vp)
3065 {
3066 
3067 	ASSERT_VOP_IN_SEQC(dvp);
3068 	ASSERT_VOP_IN_SEQC(vp);
3069 	cache_purge(vp);
3070 }
3071 
3072 #ifdef INVARIANTS
3073 /*
3074  * Validate that if an entry exists it matches.
3075  */
3076 void
3077 cache_validate(struct vnode *dvp, struct vnode *vp, struct componentname *cnp)
3078 {
3079 	struct namecache *ncp;
3080 	struct mtx *blp;
3081 	uint32_t hash;
3082 
3083 	hash = cache_get_hash(cnp->cn_nameptr, cnp->cn_namelen, dvp);
3084 	if (CK_SLIST_EMPTY(NCHHASH(hash)))
3085 		return;
3086 	blp = HASH2BUCKETLOCK(hash);
3087 	mtx_lock(blp);
3088 	CK_SLIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
3089 		if (ncp->nc_dvp == dvp && ncp->nc_nlen == cnp->cn_namelen &&
3090 		    !bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen)) {
3091 			if (ncp->nc_vp != vp)
3092 				panic("%s: mismatch (%p != %p); ncp %p [%s] dvp %p\n",
3093 				    __func__, vp, ncp->nc_vp, ncp, ncp->nc_name, ncp->nc_dvp);
3094 		}
3095 	}
3096 	mtx_unlock(blp);
3097 }
3098 
3099 void
3100 cache_assert_no_entries(struct vnode *vp)
3101 {
3102 
3103 	VNPASS(TAILQ_EMPTY(&vp->v_cache_dst), vp);
3104 	VNPASS(LIST_EMPTY(&vp->v_cache_src), vp);
3105 	VNPASS(vp->v_cache_dd == NULL, vp);
3106 }
3107 #endif
3108 
3109 /*
3110  * Flush all entries referencing a particular filesystem.
3111  */
3112 void
3113 cache_purgevfs(struct mount *mp)
3114 {
3115 	struct vnode *vp, *mvp;
3116 	size_t visited __sdt_used, purged __sdt_used;
3117 
3118 	visited = purged = 0;
3119 	/*
3120 	 * Somewhat wasteful iteration over all vnodes. Would be better to
3121 	 * support filtering and avoid the interlock to begin with.
3122 	 */
3123 	MNT_VNODE_FOREACH_ALL(vp, mp, mvp) {
3124 		visited++;
3125 		if (!cache_has_entries(vp)) {
3126 			VI_UNLOCK(vp);
3127 			continue;
3128 		}
3129 		vholdl(vp);
3130 		VI_UNLOCK(vp);
3131 		cache_purge(vp);
3132 		purged++;
3133 		vdrop(vp);
3134 	}
3135 
3136 	SDT_PROBE3(vfs, namecache, purgevfs, done, mp, visited, purged);
3137 }
3138 
3139 /*
3140  * Perform canonical checks and cache lookup and pass on to filesystem
3141  * through the vop_cachedlookup only if needed.
3142  */
3143 
3144 int
3145 vfs_cache_lookup(struct vop_lookup_args *ap)
3146 {
3147 	struct vnode *dvp;
3148 	int error;
3149 	struct vnode **vpp = ap->a_vpp;
3150 	struct componentname *cnp = ap->a_cnp;
3151 	int flags = cnp->cn_flags;
3152 
3153 	*vpp = NULL;
3154 	dvp = ap->a_dvp;
3155 
3156 	if (dvp->v_type != VDIR)
3157 		return (ENOTDIR);
3158 
3159 	if ((flags & ISLASTCN) && (dvp->v_mount->mnt_flag & MNT_RDONLY) &&
3160 	    (cnp->cn_nameiop == DELETE || cnp->cn_nameiop == RENAME))
3161 		return (EROFS);
3162 
3163 	error = vn_dir_check_exec(dvp, cnp);
3164 	if (error != 0)
3165 		return (error);
3166 
3167 	error = cache_lookup(dvp, vpp, cnp, NULL, NULL);
3168 	if (error == 0)
3169 		return (VOP_CACHEDLOOKUP(dvp, vpp, cnp));
3170 	if (error == -1)
3171 		return (0);
3172 	return (error);
3173 }
3174 
3175 /* Implementation of the getcwd syscall. */
3176 int
3177 sys___getcwd(struct thread *td, struct __getcwd_args *uap)
3178 {
3179 	char *buf, *retbuf;
3180 	size_t buflen;
3181 	int error;
3182 
3183 	buflen = uap->buflen;
3184 	if (__predict_false(buflen < 2))
3185 		return (EINVAL);
3186 	if (buflen > MAXPATHLEN)
3187 		buflen = MAXPATHLEN;
3188 
3189 	buf = uma_zalloc(namei_zone, M_WAITOK);
3190 	error = vn_getcwd(buf, &retbuf, &buflen);
3191 	if (error == 0)
3192 		error = copyout(retbuf, uap->buf, buflen);
3193 	uma_zfree(namei_zone, buf);
3194 	return (error);
3195 }
3196 
3197 int
3198 vn_getcwd(char *buf, char **retbuf, size_t *buflen)
3199 {
3200 	struct pwd *pwd;
3201 	int error;
3202 
3203 	vfs_smr_enter();
3204 	pwd = pwd_get_smr();
3205 	error = vn_fullpath_any_smr(pwd->pwd_cdir, pwd->pwd_rdir, buf, retbuf,
3206 	    buflen, 0);
3207 	VFS_SMR_ASSERT_NOT_ENTERED();
3208 	if (error < 0) {
3209 		pwd = pwd_hold(curthread);
3210 		error = vn_fullpath_any(pwd->pwd_cdir, pwd->pwd_rdir, buf,
3211 		    retbuf, buflen);
3212 		pwd_drop(pwd);
3213 	}
3214 
3215 #ifdef KTRACE
3216 	if (KTRPOINT(curthread, KTR_NAMEI) && error == 0)
3217 		ktrnamei(*retbuf);
3218 #endif
3219 	return (error);
3220 }
3221 
3222 /*
3223  * Canonicalize a path by walking it forward and back.
3224  *
3225  * BUGS:
3226  * - Nothing guarantees the integrity of the entire chain. Consider the case
3227  *   where the path "foo/bar/baz/qux" is passed, but "bar" is moved out of
3228  *   "foo" into "quux" during the backwards walk. The result will be
3229  *   "quux/bar/baz/qux", which could not have been obtained by an incremental
3230  *   walk in userspace. Moreover, the path we return is inaccessible if the
3231  *   calling thread lacks permission to traverse "quux".
3232  */
3233 static int
3234 kern___realpathat(struct thread *td, int fd, const char *path, char *buf,
3235     size_t size, int flags, enum uio_seg pathseg)
3236 {
3237 	struct nameidata nd;
3238 	char *retbuf, *freebuf;
3239 	int error;
3240 
3241 	if (flags != 0)
3242 		return (EINVAL);
3243 	NDINIT_ATRIGHTS(&nd, LOOKUP, FOLLOW | WANTPARENT | AUDITVNODE1,
3244 	    pathseg, path, fd, &cap_fstat_rights);
3245 	if ((error = namei(&nd)) != 0)
3246 		return (error);
3247 
3248 	if (nd.ni_vp->v_type == VREG && nd.ni_dvp->v_type != VDIR &&
3249 	    (nd.ni_vp->v_vflag & VV_ROOT) != 0) {
3250 		/*
3251 		 * This happens if vp is a file mount. The call to
3252 		 * vn_fullpath_hardlink can panic if path resolution can't be
3253 		 * handled without the directory.
3254 		 *
3255 		 * To resolve this, we find the vnode which was mounted on -
3256 		 * this should have a unique global path since we disallow
3257 		 * mounting on linked files.
3258 		 */
3259 		struct vnode *covered_vp;
3260 		error = vn_lock(nd.ni_vp, LK_SHARED);
3261 		if (error != 0)
3262 			goto out;
3263 		covered_vp = nd.ni_vp->v_mount->mnt_vnodecovered;
3264 		vref(covered_vp);
3265 		VOP_UNLOCK(nd.ni_vp);
3266 		error = vn_fullpath(covered_vp, &retbuf, &freebuf);
3267 		vrele(covered_vp);
3268 	} else {
3269 		error = vn_fullpath_hardlink(nd.ni_vp, nd.ni_dvp, nd.ni_cnd.cn_nameptr,
3270 		    nd.ni_cnd.cn_namelen, &retbuf, &freebuf, &size);
3271 	}
3272 	if (error == 0) {
3273 		error = copyout(retbuf, buf, size);
3274 		free(freebuf, M_TEMP);
3275 	}
3276 out:
3277 	vrele(nd.ni_vp);
3278 	vrele(nd.ni_dvp);
3279 	NDFREE_PNBUF(&nd);
3280 	return (error);
3281 }
3282 
3283 int
3284 sys___realpathat(struct thread *td, struct __realpathat_args *uap)
3285 {
3286 
3287 	return (kern___realpathat(td, uap->fd, uap->path, uap->buf, uap->size,
3288 	    uap->flags, UIO_USERSPACE));
3289 }
3290 
3291 /*
3292  * Retrieve the full filesystem path that correspond to a vnode from the name
3293  * cache (if available)
3294  */
3295 int
3296 vn_fullpath(struct vnode *vp, char **retbuf, char **freebuf)
3297 {
3298 	struct pwd *pwd;
3299 	char *buf;
3300 	size_t buflen;
3301 	int error;
3302 
3303 	if (__predict_false(vp == NULL))
3304 		return (EINVAL);
3305 
3306 	buflen = MAXPATHLEN;
3307 	buf = malloc(buflen, M_TEMP, M_WAITOK);
3308 	vfs_smr_enter();
3309 	pwd = pwd_get_smr();
3310 	error = vn_fullpath_any_smr(vp, pwd->pwd_rdir, buf, retbuf, &buflen, 0);
3311 	VFS_SMR_ASSERT_NOT_ENTERED();
3312 	if (error < 0) {
3313 		pwd = pwd_hold(curthread);
3314 		error = vn_fullpath_any(vp, pwd->pwd_rdir, buf, retbuf, &buflen);
3315 		pwd_drop(pwd);
3316 	}
3317 	if (error == 0)
3318 		*freebuf = buf;
3319 	else
3320 		free(buf, M_TEMP);
3321 	return (error);
3322 }
3323 
3324 /*
3325  * This function is similar to vn_fullpath, but it attempts to lookup the
3326  * pathname relative to the global root mount point.  This is required for the
3327  * auditing sub-system, as audited pathnames must be absolute, relative to the
3328  * global root mount point.
3329  */
3330 int
3331 vn_fullpath_global(struct vnode *vp, char **retbuf, char **freebuf)
3332 {
3333 	char *buf;
3334 	size_t buflen;
3335 	int error;
3336 
3337 	if (__predict_false(vp == NULL))
3338 		return (EINVAL);
3339 	buflen = MAXPATHLEN;
3340 	buf = malloc(buflen, M_TEMP, M_WAITOK);
3341 	vfs_smr_enter();
3342 	error = vn_fullpath_any_smr(vp, rootvnode, buf, retbuf, &buflen, 0);
3343 	VFS_SMR_ASSERT_NOT_ENTERED();
3344 	if (error < 0) {
3345 		error = vn_fullpath_any(vp, rootvnode, buf, retbuf, &buflen);
3346 	}
3347 	if (error == 0)
3348 		*freebuf = buf;
3349 	else
3350 		free(buf, M_TEMP);
3351 	return (error);
3352 }
3353 
3354 static struct namecache *
3355 vn_dd_from_dst(struct vnode *vp)
3356 {
3357 	struct namecache *ncp;
3358 
3359 	cache_assert_vnode_locked(vp);
3360 	TAILQ_FOREACH(ncp, &vp->v_cache_dst, nc_dst) {
3361 		if ((ncp->nc_flag & NCF_ISDOTDOT) == 0)
3362 			return (ncp);
3363 	}
3364 	return (NULL);
3365 }
3366 
3367 int
3368 vn_vptocnp(struct vnode **vp, char *buf, size_t *buflen)
3369 {
3370 	struct vnode *dvp;
3371 	struct namecache *ncp;
3372 	struct mtx *vlp;
3373 	int error;
3374 
3375 	vlp = VP2VNODELOCK(*vp);
3376 	mtx_lock(vlp);
3377 	ncp = (*vp)->v_cache_dd;
3378 	if (ncp != NULL && (ncp->nc_flag & NCF_ISDOTDOT) == 0) {
3379 		KASSERT(ncp == vn_dd_from_dst(*vp),
3380 		    ("%s: mismatch for dd entry (%p != %p)", __func__,
3381 		    ncp, vn_dd_from_dst(*vp)));
3382 	} else {
3383 		ncp = vn_dd_from_dst(*vp);
3384 	}
3385 	if (ncp != NULL) {
3386 		if (*buflen < ncp->nc_nlen) {
3387 			mtx_unlock(vlp);
3388 			vrele(*vp);
3389 			counter_u64_add(numfullpathfail4, 1);
3390 			error = ENOMEM;
3391 			SDT_PROBE3(vfs, namecache, fullpath, return, error,
3392 			    vp, NULL);
3393 			return (error);
3394 		}
3395 		*buflen -= ncp->nc_nlen;
3396 		memcpy(buf + *buflen, ncp->nc_name, ncp->nc_nlen);
3397 		SDT_PROBE3(vfs, namecache, fullpath, hit, ncp->nc_dvp,
3398 		    ncp->nc_name, vp);
3399 		dvp = *vp;
3400 		*vp = ncp->nc_dvp;
3401 		vref(*vp);
3402 		mtx_unlock(vlp);
3403 		vrele(dvp);
3404 		return (0);
3405 	}
3406 	SDT_PROBE1(vfs, namecache, fullpath, miss, vp);
3407 
3408 	mtx_unlock(vlp);
3409 	vn_lock(*vp, LK_SHARED | LK_RETRY);
3410 	error = VOP_VPTOCNP(*vp, &dvp, buf, buflen);
3411 	vput(*vp);
3412 	if (error) {
3413 		counter_u64_add(numfullpathfail2, 1);
3414 		SDT_PROBE3(vfs, namecache, fullpath, return,  error, vp, NULL);
3415 		return (error);
3416 	}
3417 
3418 	*vp = dvp;
3419 	if (VN_IS_DOOMED(dvp)) {
3420 		/* forced unmount */
3421 		vrele(dvp);
3422 		error = ENOENT;
3423 		SDT_PROBE3(vfs, namecache, fullpath, return, error, vp, NULL);
3424 		return (error);
3425 	}
3426 	/*
3427 	 * *vp has its use count incremented still.
3428 	 */
3429 
3430 	return (0);
3431 }
3432 
3433 /*
3434  * Resolve a directory to a pathname.
3435  *
3436  * The name of the directory can always be found in the namecache or fetched
3437  * from the filesystem. There is also guaranteed to be only one parent, meaning
3438  * we can just follow vnodes up until we find the root.
3439  *
3440  * The vnode must be referenced.
3441  */
3442 static int
3443 vn_fullpath_dir(struct vnode *vp, struct vnode *rdir, char *buf, char **retbuf,
3444     size_t *len, size_t addend)
3445 {
3446 #ifdef KDTRACE_HOOKS
3447 	struct vnode *startvp = vp;
3448 #endif
3449 	struct vnode *vp1;
3450 	size_t buflen;
3451 	int error;
3452 	bool slash_prefixed;
3453 
3454 	VNPASS(vp->v_type == VDIR || VN_IS_DOOMED(vp), vp);
3455 	VNPASS(vp->v_usecount > 0, vp);
3456 
3457 	buflen = *len;
3458 
3459 	slash_prefixed = true;
3460 	if (addend == 0) {
3461 		MPASS(*len >= 2);
3462 		buflen--;
3463 		buf[buflen] = '\0';
3464 		slash_prefixed = false;
3465 	}
3466 
3467 	error = 0;
3468 
3469 	SDT_PROBE1(vfs, namecache, fullpath, entry, vp);
3470 	counter_u64_add(numfullpathcalls, 1);
3471 	while (vp != rdir && vp != rootvnode) {
3472 		/*
3473 		 * The vp vnode must be already fully constructed,
3474 		 * since it is either found in namecache or obtained
3475 		 * from VOP_VPTOCNP().  We may test for VV_ROOT safely
3476 		 * without obtaining the vnode lock.
3477 		 */
3478 		if ((vp->v_vflag & VV_ROOT) != 0) {
3479 			vn_lock(vp, LK_RETRY | LK_SHARED);
3480 
3481 			/*
3482 			 * With the vnode locked, check for races with
3483 			 * unmount, forced or not.  Note that we
3484 			 * already verified that vp is not equal to
3485 			 * the root vnode, which means that
3486 			 * mnt_vnodecovered can be NULL only for the
3487 			 * case of unmount.
3488 			 */
3489 			if (VN_IS_DOOMED(vp) ||
3490 			    (vp1 = vp->v_mount->mnt_vnodecovered) == NULL ||
3491 			    vp1->v_mountedhere != vp->v_mount) {
3492 				vput(vp);
3493 				error = ENOENT;
3494 				SDT_PROBE3(vfs, namecache, fullpath, return,
3495 				    error, vp, NULL);
3496 				break;
3497 			}
3498 
3499 			vref(vp1);
3500 			vput(vp);
3501 			vp = vp1;
3502 			continue;
3503 		}
3504 		VNPASS(vp->v_type == VDIR || VN_IS_DOOMED(vp), vp);
3505 		error = vn_vptocnp(&vp, buf, &buflen);
3506 		if (error)
3507 			break;
3508 		if (buflen == 0) {
3509 			vrele(vp);
3510 			error = ENOMEM;
3511 			SDT_PROBE3(vfs, namecache, fullpath, return, error,
3512 			    startvp, NULL);
3513 			break;
3514 		}
3515 		buf[--buflen] = '/';
3516 		slash_prefixed = true;
3517 	}
3518 	if (error)
3519 		return (error);
3520 	if (!slash_prefixed) {
3521 		if (buflen == 0) {
3522 			vrele(vp);
3523 			counter_u64_add(numfullpathfail4, 1);
3524 			SDT_PROBE3(vfs, namecache, fullpath, return, ENOMEM,
3525 			    startvp, NULL);
3526 			return (ENOMEM);
3527 		}
3528 		buf[--buflen] = '/';
3529 	}
3530 	counter_u64_add(numfullpathfound, 1);
3531 	vrele(vp);
3532 
3533 	*retbuf = buf + buflen;
3534 	SDT_PROBE3(vfs, namecache, fullpath, return, 0, startvp, *retbuf);
3535 	*len -= buflen;
3536 	*len += addend;
3537 	return (0);
3538 }
3539 
3540 /*
3541  * Resolve an arbitrary vnode to a pathname.
3542  *
3543  * Note 2 caveats:
3544  * - hardlinks are not tracked, thus if the vnode is not a directory this can
3545  *   resolve to a different path than the one used to find it
3546  * - namecache is not mandatory, meaning names are not guaranteed to be added
3547  *   (in which case resolving fails)
3548  */
3549 static void __inline
3550 cache_rev_failed_impl(int *reason, int line)
3551 {
3552 
3553 	*reason = line;
3554 }
3555 #define cache_rev_failed(var)	cache_rev_failed_impl((var), __LINE__)
3556 
3557 static int
3558 vn_fullpath_any_smr(struct vnode *vp, struct vnode *rdir, char *buf,
3559     char **retbuf, size_t *buflen, size_t addend)
3560 {
3561 #ifdef KDTRACE_HOOKS
3562 	struct vnode *startvp = vp;
3563 #endif
3564 	struct vnode *tvp;
3565 	struct mount *mp;
3566 	struct namecache *ncp;
3567 	size_t orig_buflen;
3568 	int reason;
3569 	int error;
3570 #ifdef KDTRACE_HOOKS
3571 	int i;
3572 #endif
3573 	seqc_t vp_seqc, tvp_seqc;
3574 	u_char nc_flag;
3575 
3576 	VFS_SMR_ASSERT_ENTERED();
3577 
3578 	if (!atomic_load_char(&cache_fast_lookup_enabled)) {
3579 		vfs_smr_exit();
3580 		return (-1);
3581 	}
3582 
3583 	orig_buflen = *buflen;
3584 
3585 	if (addend == 0) {
3586 		MPASS(*buflen >= 2);
3587 		*buflen -= 1;
3588 		buf[*buflen] = '\0';
3589 	}
3590 
3591 	if (vp == rdir || vp == rootvnode) {
3592 		if (addend == 0) {
3593 			*buflen -= 1;
3594 			buf[*buflen] = '/';
3595 		}
3596 		goto out_ok;
3597 	}
3598 
3599 #ifdef KDTRACE_HOOKS
3600 	i = 0;
3601 #endif
3602 	error = -1;
3603 	ncp = NULL; /* for sdt probe down below */
3604 	vp_seqc = vn_seqc_read_any(vp);
3605 	if (seqc_in_modify(vp_seqc)) {
3606 		cache_rev_failed(&reason);
3607 		goto out_abort;
3608 	}
3609 
3610 	for (;;) {
3611 #ifdef KDTRACE_HOOKS
3612 		i++;
3613 #endif
3614 		if ((vp->v_vflag & VV_ROOT) != 0) {
3615 			mp = atomic_load_ptr(&vp->v_mount);
3616 			if (mp == NULL) {
3617 				cache_rev_failed(&reason);
3618 				goto out_abort;
3619 			}
3620 			tvp = atomic_load_ptr(&mp->mnt_vnodecovered);
3621 			tvp_seqc = vn_seqc_read_any(tvp);
3622 			if (seqc_in_modify(tvp_seqc)) {
3623 				cache_rev_failed(&reason);
3624 				goto out_abort;
3625 			}
3626 			if (!vn_seqc_consistent(vp, vp_seqc)) {
3627 				cache_rev_failed(&reason);
3628 				goto out_abort;
3629 			}
3630 			vp = tvp;
3631 			vp_seqc = tvp_seqc;
3632 			continue;
3633 		}
3634 		ncp = atomic_load_consume_ptr(&vp->v_cache_dd);
3635 		if (ncp == NULL) {
3636 			cache_rev_failed(&reason);
3637 			goto out_abort;
3638 		}
3639 		nc_flag = atomic_load_char(&ncp->nc_flag);
3640 		if ((nc_flag & NCF_ISDOTDOT) != 0) {
3641 			cache_rev_failed(&reason);
3642 			goto out_abort;
3643 		}
3644 		if (ncp->nc_nlen >= *buflen) {
3645 			cache_rev_failed(&reason);
3646 			error = ENOMEM;
3647 			goto out_abort;
3648 		}
3649 		*buflen -= ncp->nc_nlen;
3650 		memcpy(buf + *buflen, ncp->nc_name, ncp->nc_nlen);
3651 		*buflen -= 1;
3652 		buf[*buflen] = '/';
3653 		tvp = ncp->nc_dvp;
3654 		tvp_seqc = vn_seqc_read_any(tvp);
3655 		if (seqc_in_modify(tvp_seqc)) {
3656 			cache_rev_failed(&reason);
3657 			goto out_abort;
3658 		}
3659 		if (!vn_seqc_consistent(vp, vp_seqc)) {
3660 			cache_rev_failed(&reason);
3661 			goto out_abort;
3662 		}
3663 		/*
3664 		 * Acquire fence provided by vn_seqc_read_any above.
3665 		 */
3666 		if (__predict_false(atomic_load_ptr(&vp->v_cache_dd) != ncp)) {
3667 			cache_rev_failed(&reason);
3668 			goto out_abort;
3669 		}
3670 		if (!cache_ncp_canuse(ncp)) {
3671 			cache_rev_failed(&reason);
3672 			goto out_abort;
3673 		}
3674 		vp = tvp;
3675 		vp_seqc = tvp_seqc;
3676 		if (vp == rdir || vp == rootvnode)
3677 			break;
3678 	}
3679 out_ok:
3680 	vfs_smr_exit();
3681 	*retbuf = buf + *buflen;
3682 	*buflen = orig_buflen - *buflen + addend;
3683 	SDT_PROBE2(vfs, namecache, fullpath_smr, hit, startvp, *retbuf);
3684 	return (0);
3685 
3686 out_abort:
3687 	*buflen = orig_buflen;
3688 	SDT_PROBE4(vfs, namecache, fullpath_smr, miss, startvp, ncp, reason, i);
3689 	vfs_smr_exit();
3690 	return (error);
3691 }
3692 
3693 static int
3694 vn_fullpath_any(struct vnode *vp, struct vnode *rdir, char *buf, char **retbuf,
3695     size_t *buflen)
3696 {
3697 	size_t orig_buflen, addend;
3698 	int error;
3699 
3700 	if (*buflen < 2)
3701 		return (EINVAL);
3702 
3703 	orig_buflen = *buflen;
3704 
3705 	vref(vp);
3706 	addend = 0;
3707 	if (vp->v_type != VDIR) {
3708 		*buflen -= 1;
3709 		buf[*buflen] = '\0';
3710 		error = vn_vptocnp(&vp, buf, buflen);
3711 		if (error)
3712 			return (error);
3713 		if (*buflen == 0) {
3714 			vrele(vp);
3715 			return (ENOMEM);
3716 		}
3717 		*buflen -= 1;
3718 		buf[*buflen] = '/';
3719 		addend = orig_buflen - *buflen;
3720 	}
3721 
3722 	return (vn_fullpath_dir(vp, rdir, buf, retbuf, buflen, addend));
3723 }
3724 
3725 /*
3726  * Resolve an arbitrary vnode to a pathname (taking care of hardlinks).
3727  *
3728  * Since the namecache does not track hardlinks, the caller is expected to
3729  * first look up the target vnode with WANTPARENT flag passed to namei to get
3730  * dvp and vp.
3731  *
3732  * Then we have 2 cases:
3733  * - if the found vnode is a directory, the path can be constructed just by
3734  *   following names up the chain
3735  * - otherwise we populate the buffer with the saved name and start resolving
3736  *   from the parent
3737  */
3738 int
3739 vn_fullpath_hardlink(struct vnode *vp, struct vnode *dvp,
3740     const char *hrdl_name, size_t hrdl_name_length,
3741     char **retbuf, char **freebuf, size_t *buflen)
3742 {
3743 	char *buf, *tmpbuf;
3744 	struct pwd *pwd;
3745 	size_t addend;
3746 	int error;
3747 	__enum_uint8(vtype) type;
3748 
3749 	if (*buflen < 2)
3750 		return (EINVAL);
3751 	if (*buflen > MAXPATHLEN)
3752 		*buflen = MAXPATHLEN;
3753 
3754 	buf = malloc(*buflen, M_TEMP, M_WAITOK);
3755 
3756 	addend = 0;
3757 
3758 	/*
3759 	 * Check for VBAD to work around the vp_crossmp bug in lookup().
3760 	 *
3761 	 * For example consider tmpfs on /tmp and realpath /tmp. ni_vp will be
3762 	 * set to mount point's root vnode while ni_dvp will be vp_crossmp.
3763 	 * If the type is VDIR (like in this very case) we can skip looking
3764 	 * at ni_dvp in the first place. However, since vnodes get passed here
3765 	 * unlocked the target may transition to doomed state (type == VBAD)
3766 	 * before we get to evaluate the condition. If this happens, we will
3767 	 * populate part of the buffer and descend to vn_fullpath_dir with
3768 	 * vp == vp_crossmp. Prevent the problem by checking for VBAD.
3769 	 */
3770 	type = atomic_load_8(&vp->v_type);
3771 	if (type == VBAD) {
3772 		error = ENOENT;
3773 		goto out_bad;
3774 	}
3775 	if (type != VDIR) {
3776 		addend = hrdl_name_length + 2;
3777 		if (*buflen < addend) {
3778 			error = ENOMEM;
3779 			goto out_bad;
3780 		}
3781 		*buflen -= addend;
3782 		tmpbuf = buf + *buflen;
3783 		tmpbuf[0] = '/';
3784 		memcpy(&tmpbuf[1], hrdl_name, hrdl_name_length);
3785 		tmpbuf[addend - 1] = '\0';
3786 		vp = dvp;
3787 	}
3788 
3789 	vfs_smr_enter();
3790 	pwd = pwd_get_smr();
3791 	error = vn_fullpath_any_smr(vp, pwd->pwd_rdir, buf, retbuf, buflen,
3792 	    addend);
3793 	VFS_SMR_ASSERT_NOT_ENTERED();
3794 	if (error < 0) {
3795 		pwd = pwd_hold(curthread);
3796 		vref(vp);
3797 		error = vn_fullpath_dir(vp, pwd->pwd_rdir, buf, retbuf, buflen,
3798 		    addend);
3799 		pwd_drop(pwd);
3800 	}
3801 	if (error != 0)
3802 		goto out_bad;
3803 
3804 	*freebuf = buf;
3805 
3806 	return (0);
3807 out_bad:
3808 	free(buf, M_TEMP);
3809 	return (error);
3810 }
3811 
3812 struct vnode *
3813 vn_dir_dd_ino(struct vnode *vp)
3814 {
3815 	struct namecache *ncp;
3816 	struct vnode *ddvp;
3817 	struct mtx *vlp;
3818 	enum vgetstate vs;
3819 
3820 	ASSERT_VOP_LOCKED(vp, "vn_dir_dd_ino");
3821 	vlp = VP2VNODELOCK(vp);
3822 	mtx_lock(vlp);
3823 	TAILQ_FOREACH(ncp, &(vp->v_cache_dst), nc_dst) {
3824 		if ((ncp->nc_flag & NCF_ISDOTDOT) != 0)
3825 			continue;
3826 		ddvp = ncp->nc_dvp;
3827 		vs = vget_prep(ddvp);
3828 		mtx_unlock(vlp);
3829 		if (vget_finish(ddvp, LK_SHARED | LK_NOWAIT, vs))
3830 			return (NULL);
3831 		return (ddvp);
3832 	}
3833 	mtx_unlock(vlp);
3834 	return (NULL);
3835 }
3836 
3837 int
3838 vn_commname(struct vnode *vp, char *buf, u_int buflen)
3839 {
3840 	struct namecache *ncp;
3841 	struct mtx *vlp;
3842 	int l;
3843 
3844 	vlp = VP2VNODELOCK(vp);
3845 	mtx_lock(vlp);
3846 	TAILQ_FOREACH(ncp, &vp->v_cache_dst, nc_dst)
3847 		if ((ncp->nc_flag & NCF_ISDOTDOT) == 0)
3848 			break;
3849 	if (ncp == NULL) {
3850 		mtx_unlock(vlp);
3851 		return (ENOENT);
3852 	}
3853 	l = min(ncp->nc_nlen, buflen - 1);
3854 	memcpy(buf, ncp->nc_name, l);
3855 	mtx_unlock(vlp);
3856 	buf[l] = '\0';
3857 	return (0);
3858 }
3859 
3860 /*
3861  * This function updates path string to vnode's full global path
3862  * and checks the size of the new path string against the pathlen argument.
3863  *
3864  * Requires a locked, referenced vnode.
3865  * Vnode is re-locked on success or ENODEV, otherwise unlocked.
3866  *
3867  * If vp is a directory, the call to vn_fullpath_global() always succeeds
3868  * because it falls back to the ".." lookup if the namecache lookup fails.
3869  */
3870 int
3871 vn_path_to_global_path(struct thread *td, struct vnode *vp, char *path,
3872     u_int pathlen)
3873 {
3874 	struct nameidata nd;
3875 	struct vnode *vp1;
3876 	char *rpath, *fbuf;
3877 	int error;
3878 
3879 	ASSERT_VOP_ELOCKED(vp, __func__);
3880 
3881 	/* Construct global filesystem path from vp. */
3882 	VOP_UNLOCK(vp);
3883 	error = vn_fullpath_global(vp, &rpath, &fbuf);
3884 
3885 	if (error != 0) {
3886 		vrele(vp);
3887 		return (error);
3888 	}
3889 
3890 	if (strlen(rpath) >= pathlen) {
3891 		vrele(vp);
3892 		error = ENAMETOOLONG;
3893 		goto out;
3894 	}
3895 
3896 	/*
3897 	 * Re-lookup the vnode by path to detect a possible rename.
3898 	 * As a side effect, the vnode is relocked.
3899 	 * If vnode was renamed, return ENOENT.
3900 	 */
3901 	NDINIT(&nd, LOOKUP, FOLLOW | LOCKLEAF | AUDITVNODE1, UIO_SYSSPACE, path);
3902 	error = namei(&nd);
3903 	if (error != 0) {
3904 		vrele(vp);
3905 		goto out;
3906 	}
3907 	NDFREE_PNBUF(&nd);
3908 	vp1 = nd.ni_vp;
3909 	vrele(vp);
3910 	if (vp1 == vp)
3911 		strcpy(path, rpath);
3912 	else {
3913 		vput(vp1);
3914 		error = ENOENT;
3915 	}
3916 
3917 out:
3918 	free(fbuf, M_TEMP);
3919 	return (error);
3920 }
3921 
3922 /*
3923  * This is similar to vn_path_to_global_path but allows for regular
3924  * files which may not be present in the cache.
3925  *
3926  * Requires a locked, referenced vnode.
3927  * Vnode is re-locked on success or ENODEV, otherwise unlocked.
3928  */
3929 int
3930 vn_path_to_global_path_hardlink(struct thread *td, struct vnode *vp,
3931     struct vnode *dvp, char *path, u_int pathlen, const char *leaf_name,
3932     size_t leaf_length)
3933 {
3934 	struct nameidata nd;
3935 	struct vnode *vp1;
3936 	char *rpath, *fbuf;
3937 	size_t len;
3938 	int error;
3939 
3940 	ASSERT_VOP_ELOCKED(vp, __func__);
3941 
3942 	/*
3943 	 * Construct global filesystem path from dvp, vp and leaf
3944 	 * name.
3945 	 */
3946 	VOP_UNLOCK(vp);
3947 	len = pathlen;
3948 	error = vn_fullpath_hardlink(vp, dvp, leaf_name, leaf_length,
3949 	    &rpath, &fbuf, &len);
3950 
3951 	if (error != 0) {
3952 		vrele(vp);
3953 		return (error);
3954 	}
3955 
3956 	if (strlen(rpath) >= pathlen) {
3957 		vrele(vp);
3958 		error = ENAMETOOLONG;
3959 		goto out;
3960 	}
3961 
3962 	/*
3963 	 * Re-lookup the vnode by path to detect a possible rename.
3964 	 * As a side effect, the vnode is relocked.
3965 	 * If vnode was renamed, return ENOENT.
3966 	 */
3967 	NDINIT(&nd, LOOKUP, FOLLOW | LOCKLEAF | AUDITVNODE1, UIO_SYSSPACE, path);
3968 	error = namei(&nd);
3969 	if (error != 0) {
3970 		vrele(vp);
3971 		goto out;
3972 	}
3973 	NDFREE_PNBUF(&nd);
3974 	vp1 = nd.ni_vp;
3975 	vrele(vp);
3976 	if (vp1 == vp)
3977 		strcpy(path, rpath);
3978 	else {
3979 		vput(vp1);
3980 		error = ENOENT;
3981 	}
3982 
3983 out:
3984 	free(fbuf, M_TEMP);
3985 	return (error);
3986 }
3987 
3988 #ifdef DDB
3989 static void
3990 db_print_vpath(struct vnode *vp)
3991 {
3992 
3993 	while (vp != NULL) {
3994 		db_printf("%p: ", vp);
3995 		if (vp == rootvnode) {
3996 			db_printf("/");
3997 			vp = NULL;
3998 		} else {
3999 			if (vp->v_vflag & VV_ROOT) {
4000 				db_printf("<mount point>");
4001 				vp = vp->v_mount->mnt_vnodecovered;
4002 			} else {
4003 				struct namecache *ncp;
4004 				char *ncn;
4005 				int i;
4006 
4007 				ncp = TAILQ_FIRST(&vp->v_cache_dst);
4008 				if (ncp != NULL) {
4009 					ncn = ncp->nc_name;
4010 					for (i = 0; i < ncp->nc_nlen; i++)
4011 						db_printf("%c", *ncn++);
4012 					vp = ncp->nc_dvp;
4013 				} else {
4014 					vp = NULL;
4015 				}
4016 			}
4017 		}
4018 		db_printf("\n");
4019 	}
4020 
4021 	return;
4022 }
4023 
4024 DB_SHOW_COMMAND(vpath, db_show_vpath)
4025 {
4026 	struct vnode *vp;
4027 
4028 	if (!have_addr) {
4029 		db_printf("usage: show vpath <struct vnode *>\n");
4030 		return;
4031 	}
4032 
4033 	vp = (struct vnode *)addr;
4034 	db_print_vpath(vp);
4035 }
4036 
4037 #endif
4038 
4039 static int cache_fast_lookup = 1;
4040 
4041 #define CACHE_FPL_FAILED	-2020
4042 
4043 static int
4044 cache_vop_bad_vexec(struct vop_fplookup_vexec_args *v)
4045 {
4046 	vn_printf(v->a_vp, "no proper vop_fplookup_vexec\n");
4047 	panic("no proper vop_fplookup_vexec");
4048 }
4049 
4050 static int
4051 cache_vop_bad_symlink(struct vop_fplookup_symlink_args *v)
4052 {
4053 	vn_printf(v->a_vp, "no proper vop_fplookup_symlink\n");
4054 	panic("no proper vop_fplookup_symlink");
4055 }
4056 
4057 void
4058 cache_vop_vector_register(struct vop_vector *v)
4059 {
4060 	size_t ops;
4061 
4062 	ops = 0;
4063 	if (v->vop_fplookup_vexec != NULL) {
4064 		ops++;
4065 	}
4066 	if (v->vop_fplookup_symlink != NULL) {
4067 		ops++;
4068 	}
4069 
4070 	if (ops == 2) {
4071 		return;
4072 	}
4073 
4074 	if (ops == 0) {
4075 		v->vop_fplookup_vexec = cache_vop_bad_vexec;
4076 		v->vop_fplookup_symlink = cache_vop_bad_symlink;
4077 		return;
4078 	}
4079 
4080 	printf("%s: invalid vop vector %p -- either all or none fplookup vops "
4081 	    "need to be provided",  __func__, v);
4082 	if (v->vop_fplookup_vexec == NULL) {
4083 		printf("%s: missing vop_fplookup_vexec\n", __func__);
4084 	}
4085 	if (v->vop_fplookup_symlink == NULL) {
4086 		printf("%s: missing vop_fplookup_symlink\n", __func__);
4087 	}
4088 	panic("bad vop vector %p", v);
4089 }
4090 
4091 #ifdef INVARIANTS
4092 void
4093 cache_validate_vop_vector(struct mount *mp, struct vop_vector *vops)
4094 {
4095 	if (mp == NULL)
4096 		return;
4097 
4098 	if ((mp->mnt_kern_flag & MNTK_FPLOOKUP) == 0)
4099 		return;
4100 
4101 	if (vops->vop_fplookup_vexec == NULL ||
4102 	    vops->vop_fplookup_vexec == cache_vop_bad_vexec)
4103 		panic("bad vop_fplookup_vexec on vector %p for filesystem %s",
4104 		    vops, mp->mnt_vfc->vfc_name);
4105 
4106 	if (vops->vop_fplookup_symlink == NULL ||
4107 	    vops->vop_fplookup_symlink == cache_vop_bad_symlink)
4108 		panic("bad vop_fplookup_symlink on vector %p for filesystem %s",
4109 		    vops, mp->mnt_vfc->vfc_name);
4110 }
4111 #endif
4112 
4113 void
4114 cache_fast_lookup_enabled_recalc(void)
4115 {
4116 	int lookup_flag;
4117 	int mac_on;
4118 
4119 #ifdef MAC
4120 	mac_on = mac_vnode_check_lookup_enabled();
4121 	mac_on |= mac_vnode_check_readlink_enabled();
4122 #else
4123 	mac_on = 0;
4124 #endif
4125 
4126 	lookup_flag = atomic_load_int(&cache_fast_lookup);
4127 	if (lookup_flag && !mac_on) {
4128 		atomic_store_char(&cache_fast_lookup_enabled, true);
4129 	} else {
4130 		atomic_store_char(&cache_fast_lookup_enabled, false);
4131 	}
4132 }
4133 
4134 static int
4135 syscal_vfs_cache_fast_lookup(SYSCTL_HANDLER_ARGS)
4136 {
4137 	int error, old;
4138 
4139 	old = atomic_load_int(&cache_fast_lookup);
4140 	error = sysctl_handle_int(oidp, arg1, arg2, req);
4141 	if (error == 0 && req->newptr && old != atomic_load_int(&cache_fast_lookup))
4142 		cache_fast_lookup_enabled_recalc();
4143 	return (error);
4144 }
4145 SYSCTL_PROC(_vfs_cache_param, OID_AUTO, fast_lookup, CTLTYPE_INT|CTLFLAG_RW|CTLFLAG_MPSAFE,
4146     &cache_fast_lookup, 0, syscal_vfs_cache_fast_lookup, "IU", "");
4147 
4148 /*
4149  * Components of nameidata (or objects it can point to) which may
4150  * need restoring in case fast path lookup fails.
4151  */
4152 struct nameidata_outer {
4153 	size_t ni_pathlen;
4154 	int cn_flags;
4155 };
4156 
4157 struct nameidata_saved {
4158 #ifdef INVARIANTS
4159 	char *cn_nameptr;
4160 	size_t ni_pathlen;
4161 #endif
4162 };
4163 
4164 #ifdef INVARIANTS
4165 struct cache_fpl_debug {
4166 	size_t ni_pathlen;
4167 };
4168 #endif
4169 
4170 struct cache_fpl {
4171 	struct nameidata *ndp;
4172 	struct componentname *cnp;
4173 	char *nulchar;
4174 	struct vnode *dvp;
4175 	struct vnode *tvp;
4176 	seqc_t dvp_seqc;
4177 	seqc_t tvp_seqc;
4178 	uint32_t hash;
4179 	struct nameidata_saved snd;
4180 	struct nameidata_outer snd_outer;
4181 	int line;
4182 	enum cache_fpl_status status:8;
4183 	bool in_smr;
4184 	bool fsearch;
4185 	struct pwd **pwd;
4186 #ifdef INVARIANTS
4187 	struct cache_fpl_debug debug;
4188 #endif
4189 };
4190 
4191 static bool cache_fplookup_mp_supported(struct mount *mp);
4192 static bool cache_fplookup_is_mp(struct cache_fpl *fpl);
4193 static int cache_fplookup_cross_mount(struct cache_fpl *fpl);
4194 static int cache_fplookup_partial_setup(struct cache_fpl *fpl);
4195 static int cache_fplookup_skip_slashes(struct cache_fpl *fpl);
4196 static int cache_fplookup_trailingslash(struct cache_fpl *fpl);
4197 static void cache_fpl_pathlen_dec(struct cache_fpl *fpl);
4198 static void cache_fpl_pathlen_inc(struct cache_fpl *fpl);
4199 static void cache_fpl_pathlen_add(struct cache_fpl *fpl, size_t n);
4200 static void cache_fpl_pathlen_sub(struct cache_fpl *fpl, size_t n);
4201 
4202 static void
4203 cache_fpl_cleanup_cnp(struct componentname *cnp)
4204 {
4205 
4206 	uma_zfree(namei_zone, cnp->cn_pnbuf);
4207 	cnp->cn_pnbuf = NULL;
4208 	cnp->cn_nameptr = NULL;
4209 }
4210 
4211 static struct vnode *
4212 cache_fpl_handle_root(struct cache_fpl *fpl)
4213 {
4214 	struct nameidata *ndp;
4215 	struct componentname *cnp;
4216 
4217 	ndp = fpl->ndp;
4218 	cnp = fpl->cnp;
4219 
4220 	MPASS(*(cnp->cn_nameptr) == '/');
4221 	cnp->cn_nameptr++;
4222 	cache_fpl_pathlen_dec(fpl);
4223 
4224 	if (__predict_false(*(cnp->cn_nameptr) == '/')) {
4225 		do {
4226 			cnp->cn_nameptr++;
4227 			cache_fpl_pathlen_dec(fpl);
4228 		} while (*(cnp->cn_nameptr) == '/');
4229 	}
4230 
4231 	return (ndp->ni_rootdir);
4232 }
4233 
4234 static void
4235 cache_fpl_checkpoint_outer(struct cache_fpl *fpl)
4236 {
4237 
4238 	fpl->snd_outer.ni_pathlen = fpl->ndp->ni_pathlen;
4239 	fpl->snd_outer.cn_flags = fpl->ndp->ni_cnd.cn_flags;
4240 }
4241 
4242 static void
4243 cache_fpl_checkpoint(struct cache_fpl *fpl)
4244 {
4245 
4246 #ifdef INVARIANTS
4247 	fpl->snd.cn_nameptr = fpl->ndp->ni_cnd.cn_nameptr;
4248 	fpl->snd.ni_pathlen = fpl->debug.ni_pathlen;
4249 #endif
4250 }
4251 
4252 static void
4253 cache_fpl_restore_partial(struct cache_fpl *fpl)
4254 {
4255 
4256 	fpl->ndp->ni_cnd.cn_flags = fpl->snd_outer.cn_flags;
4257 #ifdef INVARIANTS
4258 	fpl->debug.ni_pathlen = fpl->snd.ni_pathlen;
4259 #endif
4260 }
4261 
4262 static void
4263 cache_fpl_restore_abort(struct cache_fpl *fpl)
4264 {
4265 
4266 	cache_fpl_restore_partial(fpl);
4267 	/*
4268 	 * It is 0 on entry by API contract.
4269 	 */
4270 	fpl->ndp->ni_resflags = 0;
4271 	fpl->ndp->ni_cnd.cn_nameptr = fpl->ndp->ni_cnd.cn_pnbuf;
4272 	fpl->ndp->ni_pathlen = fpl->snd_outer.ni_pathlen;
4273 }
4274 
4275 #ifdef INVARIANTS
4276 #define cache_fpl_smr_assert_entered(fpl) ({			\
4277 	struct cache_fpl *_fpl = (fpl);				\
4278 	MPASS(_fpl->in_smr == true);				\
4279 	VFS_SMR_ASSERT_ENTERED();				\
4280 })
4281 #define cache_fpl_smr_assert_not_entered(fpl) ({		\
4282 	struct cache_fpl *_fpl = (fpl);				\
4283 	MPASS(_fpl->in_smr == false);				\
4284 	VFS_SMR_ASSERT_NOT_ENTERED();				\
4285 })
4286 static void
4287 cache_fpl_assert_status(struct cache_fpl *fpl)
4288 {
4289 
4290 	switch (fpl->status) {
4291 	case CACHE_FPL_STATUS_UNSET:
4292 		__assert_unreachable();
4293 		break;
4294 	case CACHE_FPL_STATUS_DESTROYED:
4295 	case CACHE_FPL_STATUS_ABORTED:
4296 	case CACHE_FPL_STATUS_PARTIAL:
4297 	case CACHE_FPL_STATUS_HANDLED:
4298 		break;
4299 	}
4300 }
4301 #else
4302 #define cache_fpl_smr_assert_entered(fpl) do { } while (0)
4303 #define cache_fpl_smr_assert_not_entered(fpl) do { } while (0)
4304 #define cache_fpl_assert_status(fpl) do { } while (0)
4305 #endif
4306 
4307 #define cache_fpl_smr_enter_initial(fpl) ({			\
4308 	struct cache_fpl *_fpl = (fpl);				\
4309 	vfs_smr_enter();					\
4310 	_fpl->in_smr = true;					\
4311 })
4312 
4313 #define cache_fpl_smr_enter(fpl) ({				\
4314 	struct cache_fpl *_fpl = (fpl);				\
4315 	MPASS(_fpl->in_smr == false);				\
4316 	vfs_smr_enter();					\
4317 	_fpl->in_smr = true;					\
4318 })
4319 
4320 #define cache_fpl_smr_exit(fpl) ({				\
4321 	struct cache_fpl *_fpl = (fpl);				\
4322 	MPASS(_fpl->in_smr == true);				\
4323 	vfs_smr_exit();						\
4324 	_fpl->in_smr = false;					\
4325 })
4326 
4327 static int
4328 cache_fpl_aborted_early_impl(struct cache_fpl *fpl, int line)
4329 {
4330 
4331 	if (fpl->status != CACHE_FPL_STATUS_UNSET) {
4332 		KASSERT(fpl->status == CACHE_FPL_STATUS_PARTIAL,
4333 		    ("%s: converting to abort from %d at %d, set at %d\n",
4334 		    __func__, fpl->status, line, fpl->line));
4335 	}
4336 	cache_fpl_smr_assert_not_entered(fpl);
4337 	fpl->status = CACHE_FPL_STATUS_ABORTED;
4338 	fpl->line = line;
4339 	return (CACHE_FPL_FAILED);
4340 }
4341 
4342 #define cache_fpl_aborted_early(x)	cache_fpl_aborted_early_impl((x), __LINE__)
4343 
4344 static int __noinline
4345 cache_fpl_aborted_impl(struct cache_fpl *fpl, int line)
4346 {
4347 	struct nameidata *ndp;
4348 	struct componentname *cnp;
4349 
4350 	ndp = fpl->ndp;
4351 	cnp = fpl->cnp;
4352 
4353 	if (fpl->status != CACHE_FPL_STATUS_UNSET) {
4354 		KASSERT(fpl->status == CACHE_FPL_STATUS_PARTIAL,
4355 		    ("%s: converting to abort from %d at %d, set at %d\n",
4356 		    __func__, fpl->status, line, fpl->line));
4357 	}
4358 	fpl->status = CACHE_FPL_STATUS_ABORTED;
4359 	fpl->line = line;
4360 	if (fpl->in_smr)
4361 		cache_fpl_smr_exit(fpl);
4362 	cache_fpl_restore_abort(fpl);
4363 	/*
4364 	 * Resolving symlinks overwrites data passed by the caller.
4365 	 * Let namei know.
4366 	 */
4367 	if (ndp->ni_loopcnt > 0) {
4368 		fpl->status = CACHE_FPL_STATUS_DESTROYED;
4369 		cache_fpl_cleanup_cnp(cnp);
4370 	}
4371 	return (CACHE_FPL_FAILED);
4372 }
4373 
4374 #define cache_fpl_aborted(x)	cache_fpl_aborted_impl((x), __LINE__)
4375 
4376 static int __noinline
4377 cache_fpl_partial_impl(struct cache_fpl *fpl, int line)
4378 {
4379 
4380 	KASSERT(fpl->status == CACHE_FPL_STATUS_UNSET,
4381 	    ("%s: setting to partial at %d, but already set to %d at %d\n",
4382 	    __func__, line, fpl->status, fpl->line));
4383 	cache_fpl_smr_assert_entered(fpl);
4384 	fpl->status = CACHE_FPL_STATUS_PARTIAL;
4385 	fpl->line = line;
4386 	return (cache_fplookup_partial_setup(fpl));
4387 }
4388 
4389 #define cache_fpl_partial(x)	cache_fpl_partial_impl((x), __LINE__)
4390 
4391 static int
4392 cache_fpl_handled_impl(struct cache_fpl *fpl, int line)
4393 {
4394 
4395 	KASSERT(fpl->status == CACHE_FPL_STATUS_UNSET,
4396 	    ("%s: setting to handled at %d, but already set to %d at %d\n",
4397 	    __func__, line, fpl->status, fpl->line));
4398 	cache_fpl_smr_assert_not_entered(fpl);
4399 	fpl->status = CACHE_FPL_STATUS_HANDLED;
4400 	fpl->line = line;
4401 	return (0);
4402 }
4403 
4404 #define cache_fpl_handled(x)	cache_fpl_handled_impl((x), __LINE__)
4405 
4406 static int
4407 cache_fpl_handled_error_impl(struct cache_fpl *fpl, int error, int line)
4408 {
4409 
4410 	KASSERT(fpl->status == CACHE_FPL_STATUS_UNSET,
4411 	    ("%s: setting to handled at %d, but already set to %d at %d\n",
4412 	    __func__, line, fpl->status, fpl->line));
4413 	MPASS(error != 0);
4414 	MPASS(error != CACHE_FPL_FAILED);
4415 	cache_fpl_smr_assert_not_entered(fpl);
4416 	fpl->status = CACHE_FPL_STATUS_HANDLED;
4417 	fpl->line = line;
4418 	fpl->dvp = NULL;
4419 	fpl->tvp = NULL;
4420 	return (error);
4421 }
4422 
4423 #define cache_fpl_handled_error(x, e)	cache_fpl_handled_error_impl((x), (e), __LINE__)
4424 
4425 static bool
4426 cache_fpl_terminated(struct cache_fpl *fpl)
4427 {
4428 
4429 	return (fpl->status != CACHE_FPL_STATUS_UNSET);
4430 }
4431 
4432 #define CACHE_FPL_SUPPORTED_CN_FLAGS \
4433 	(NC_NOMAKEENTRY | NC_KEEPPOSENTRY | LOCKLEAF | LOCKPARENT | WANTPARENT | \
4434 	 FAILIFEXISTS | FOLLOW | EMPTYPATH | LOCKSHARED | ISRESTARTED | WILLBEDIR | \
4435 	 ISOPEN | NOMACCHECK | AUDITVNODE1 | AUDITVNODE2 | NOCAPCHECK | OPENREAD | \
4436 	 OPENWRITE | WANTIOCTLCAPS)
4437 
4438 #define CACHE_FPL_INTERNAL_CN_FLAGS \
4439 	(ISDOTDOT | MAKEENTRY | ISLASTCN)
4440 
4441 _Static_assert((CACHE_FPL_SUPPORTED_CN_FLAGS & CACHE_FPL_INTERNAL_CN_FLAGS) == 0,
4442     "supported and internal flags overlap");
4443 
4444 static bool
4445 cache_fpl_islastcn(struct nameidata *ndp)
4446 {
4447 
4448 	return (*ndp->ni_next == 0);
4449 }
4450 
4451 static bool
4452 cache_fpl_istrailingslash(struct cache_fpl *fpl)
4453 {
4454 
4455 	MPASS(fpl->nulchar > fpl->cnp->cn_pnbuf);
4456 	return (*(fpl->nulchar - 1) == '/');
4457 }
4458 
4459 static bool
4460 cache_fpl_isdotdot(struct componentname *cnp)
4461 {
4462 
4463 	if (cnp->cn_namelen == 2 &&
4464 	    cnp->cn_nameptr[1] == '.' && cnp->cn_nameptr[0] == '.')
4465 		return (true);
4466 	return (false);
4467 }
4468 
4469 static bool
4470 cache_can_fplookup(struct cache_fpl *fpl)
4471 {
4472 	struct nameidata *ndp;
4473 	struct componentname *cnp;
4474 	struct thread *td;
4475 
4476 	ndp = fpl->ndp;
4477 	cnp = fpl->cnp;
4478 	td = curthread;
4479 
4480 	if (!atomic_load_char(&cache_fast_lookup_enabled)) {
4481 		cache_fpl_aborted_early(fpl);
4482 		return (false);
4483 	}
4484 	if ((cnp->cn_flags & ~CACHE_FPL_SUPPORTED_CN_FLAGS) != 0) {
4485 		cache_fpl_aborted_early(fpl);
4486 		return (false);
4487 	}
4488 	if (IN_CAPABILITY_MODE(td)) {
4489 		cache_fpl_aborted_early(fpl);
4490 		return (false);
4491 	}
4492 	if (AUDITING_TD(td)) {
4493 		cache_fpl_aborted_early(fpl);
4494 		return (false);
4495 	}
4496 	if (ndp->ni_startdir != NULL) {
4497 		cache_fpl_aborted_early(fpl);
4498 		return (false);
4499 	}
4500 	return (true);
4501 }
4502 
4503 static int __noinline
4504 cache_fplookup_dirfd(struct cache_fpl *fpl, struct vnode **vpp)
4505 {
4506 	struct nameidata *ndp;
4507 	struct componentname *cnp;
4508 	int error;
4509 	bool fsearch;
4510 
4511 	ndp = fpl->ndp;
4512 	cnp = fpl->cnp;
4513 
4514 	error = fgetvp_lookup_smr(ndp->ni_dirfd, ndp, vpp, &fsearch);
4515 	if (__predict_false(error != 0)) {
4516 		return (cache_fpl_aborted(fpl));
4517 	}
4518 	fpl->fsearch = fsearch;
4519 	if ((*vpp)->v_type != VDIR) {
4520 		if (!((cnp->cn_flags & EMPTYPATH) != 0 && cnp->cn_pnbuf[0] == '\0')) {
4521 			cache_fpl_smr_exit(fpl);
4522 			return (cache_fpl_handled_error(fpl, ENOTDIR));
4523 		}
4524 	}
4525 	return (0);
4526 }
4527 
4528 static int __noinline
4529 cache_fplookup_negative_promote(struct cache_fpl *fpl, struct namecache *oncp,
4530     uint32_t hash)
4531 {
4532 	struct componentname *cnp;
4533 	struct vnode *dvp;
4534 
4535 	cnp = fpl->cnp;
4536 	dvp = fpl->dvp;
4537 
4538 	cache_fpl_smr_exit(fpl);
4539 	if (cache_neg_promote_cond(dvp, cnp, oncp, hash))
4540 		return (cache_fpl_handled_error(fpl, ENOENT));
4541 	else
4542 		return (cache_fpl_aborted(fpl));
4543 }
4544 
4545 /*
4546  * The target vnode is not supported, prepare for the slow path to take over.
4547  */
4548 static int __noinline
4549 cache_fplookup_partial_setup(struct cache_fpl *fpl)
4550 {
4551 	struct nameidata *ndp;
4552 	struct componentname *cnp;
4553 	enum vgetstate dvs;
4554 	struct vnode *dvp;
4555 	struct pwd *pwd;
4556 	seqc_t dvp_seqc;
4557 
4558 	ndp = fpl->ndp;
4559 	cnp = fpl->cnp;
4560 	pwd = *(fpl->pwd);
4561 	dvp = fpl->dvp;
4562 	dvp_seqc = fpl->dvp_seqc;
4563 
4564 	if (!pwd_hold_smr(pwd)) {
4565 		return (cache_fpl_aborted(fpl));
4566 	}
4567 
4568 	/*
4569 	 * Note that seqc is checked before the vnode is locked, so by
4570 	 * the time regular lookup gets to it it may have moved.
4571 	 *
4572 	 * Ultimately this does not affect correctness, any lookup errors
4573 	 * are userspace racing with itself. It is guaranteed that any
4574 	 * path which ultimately gets found could also have been found
4575 	 * by regular lookup going all the way in absence of concurrent
4576 	 * modifications.
4577 	 */
4578 	dvs = vget_prep_smr(dvp);
4579 	cache_fpl_smr_exit(fpl);
4580 	if (__predict_false(dvs == VGET_NONE)) {
4581 		pwd_drop(pwd);
4582 		return (cache_fpl_aborted(fpl));
4583 	}
4584 
4585 	vget_finish_ref(dvp, dvs);
4586 	if (!vn_seqc_consistent(dvp, dvp_seqc)) {
4587 		vrele(dvp);
4588 		pwd_drop(pwd);
4589 		return (cache_fpl_aborted(fpl));
4590 	}
4591 
4592 	cache_fpl_restore_partial(fpl);
4593 #ifdef INVARIANTS
4594 	if (cnp->cn_nameptr != fpl->snd.cn_nameptr) {
4595 		panic("%s: cn_nameptr mismatch (%p != %p) full [%s]\n", __func__,
4596 		    cnp->cn_nameptr, fpl->snd.cn_nameptr, cnp->cn_pnbuf);
4597 	}
4598 #endif
4599 
4600 	ndp->ni_startdir = dvp;
4601 	cnp->cn_flags |= MAKEENTRY;
4602 	if (cache_fpl_islastcn(ndp))
4603 		cnp->cn_flags |= ISLASTCN;
4604 	if (cache_fpl_isdotdot(cnp))
4605 		cnp->cn_flags |= ISDOTDOT;
4606 
4607 	/*
4608 	 * Skip potential extra slashes parsing did not take care of.
4609 	 * cache_fplookup_skip_slashes explains the mechanism.
4610 	 */
4611 	if (__predict_false(*(cnp->cn_nameptr) == '/')) {
4612 		do {
4613 			cnp->cn_nameptr++;
4614 			cache_fpl_pathlen_dec(fpl);
4615 		} while (*(cnp->cn_nameptr) == '/');
4616 	}
4617 
4618 	ndp->ni_pathlen = fpl->nulchar - cnp->cn_nameptr + 1;
4619 #ifdef INVARIANTS
4620 	if (ndp->ni_pathlen != fpl->debug.ni_pathlen) {
4621 		panic("%s: mismatch (%zu != %zu) nulchar %p nameptr %p [%s] ; full string [%s]\n",
4622 		    __func__, ndp->ni_pathlen, fpl->debug.ni_pathlen, fpl->nulchar,
4623 		    cnp->cn_nameptr, cnp->cn_nameptr, cnp->cn_pnbuf);
4624 	}
4625 #endif
4626 	return (0);
4627 }
4628 
4629 static int
4630 cache_fplookup_final_child(struct cache_fpl *fpl, enum vgetstate tvs)
4631 {
4632 	struct componentname *cnp;
4633 	struct vnode *tvp;
4634 	seqc_t tvp_seqc;
4635 	int error, lkflags;
4636 
4637 	cnp = fpl->cnp;
4638 	tvp = fpl->tvp;
4639 	tvp_seqc = fpl->tvp_seqc;
4640 
4641 	if ((cnp->cn_flags & LOCKLEAF) != 0) {
4642 		lkflags = LK_SHARED;
4643 		if ((cnp->cn_flags & LOCKSHARED) == 0)
4644 			lkflags = LK_EXCLUSIVE;
4645 		error = vget_finish(tvp, lkflags, tvs);
4646 		if (__predict_false(error != 0)) {
4647 			return (cache_fpl_aborted(fpl));
4648 		}
4649 	} else {
4650 		vget_finish_ref(tvp, tvs);
4651 	}
4652 
4653 	if (!vn_seqc_consistent(tvp, tvp_seqc)) {
4654 		if ((cnp->cn_flags & LOCKLEAF) != 0)
4655 			vput(tvp);
4656 		else
4657 			vrele(tvp);
4658 		return (cache_fpl_aborted(fpl));
4659 	}
4660 
4661 	return (cache_fpl_handled(fpl));
4662 }
4663 
4664 /*
4665  * They want to possibly modify the state of the namecache.
4666  */
4667 static int __noinline
4668 cache_fplookup_final_modifying(struct cache_fpl *fpl)
4669 {
4670 	struct nameidata *ndp __diagused;
4671 	struct componentname *cnp;
4672 	enum vgetstate dvs;
4673 	struct vnode *dvp, *tvp;
4674 	struct mount *mp;
4675 	seqc_t dvp_seqc;
4676 	int error;
4677 	bool docache;
4678 
4679 	ndp = fpl->ndp;
4680 	cnp = fpl->cnp;
4681 	dvp = fpl->dvp;
4682 	dvp_seqc = fpl->dvp_seqc;
4683 
4684 	MPASS(*(cnp->cn_nameptr) != '/');
4685 	MPASS(cache_fpl_islastcn(ndp));
4686 	if ((cnp->cn_flags & LOCKPARENT) == 0)
4687 		MPASS((cnp->cn_flags & WANTPARENT) != 0);
4688 	MPASS((cnp->cn_flags & TRAILINGSLASH) == 0);
4689 	MPASS(cnp->cn_nameiop == CREATE || cnp->cn_nameiop == DELETE ||
4690 	    cnp->cn_nameiop == RENAME);
4691 	MPASS((cnp->cn_flags & MAKEENTRY) == 0);
4692 	MPASS((cnp->cn_flags & ISDOTDOT) == 0);
4693 
4694 	docache = (cnp->cn_flags & NOCACHE) ^ NOCACHE;
4695 	if (cnp->cn_nameiop == DELETE || cnp->cn_nameiop == RENAME)
4696 		docache = false;
4697 
4698 	/*
4699 	 * Regular lookup nulifies the slash, which we don't do here.
4700 	 * Don't take chances with filesystem routines seeing it for
4701 	 * the last entry.
4702 	 */
4703 	if (cache_fpl_istrailingslash(fpl)) {
4704 		return (cache_fpl_partial(fpl));
4705 	}
4706 
4707 	mp = atomic_load_ptr(&dvp->v_mount);
4708 	if (__predict_false(mp == NULL)) {
4709 		return (cache_fpl_aborted(fpl));
4710 	}
4711 
4712 	if (__predict_false(mp->mnt_flag & MNT_RDONLY)) {
4713 		cache_fpl_smr_exit(fpl);
4714 		/*
4715 		 * Original code keeps not checking for CREATE which
4716 		 * might be a bug. For now let the old lookup decide.
4717 		 */
4718 		if (cnp->cn_nameiop == CREATE) {
4719 			return (cache_fpl_aborted(fpl));
4720 		}
4721 		return (cache_fpl_handled_error(fpl, EROFS));
4722 	}
4723 
4724 	if (fpl->tvp != NULL && (cnp->cn_flags & FAILIFEXISTS) != 0) {
4725 		cache_fpl_smr_exit(fpl);
4726 		return (cache_fpl_handled_error(fpl, EEXIST));
4727 	}
4728 
4729 	/*
4730 	 * Secure access to dvp; check cache_fplookup_partial_setup for
4731 	 * reasoning.
4732 	 *
4733 	 * XXX At least UFS requires its lookup routine to be called for
4734 	 * the last path component, which leads to some level of complication
4735 	 * and inefficiency:
4736 	 * - the target routine always locks the target vnode, but our caller
4737 	 *   may not need it locked
4738 	 * - some of the VOP machinery asserts that the parent is locked, which
4739 	 *   once more may be not required
4740 	 *
4741 	 * TODO: add a flag for filesystems which don't need this.
4742 	 */
4743 	dvs = vget_prep_smr(dvp);
4744 	cache_fpl_smr_exit(fpl);
4745 	if (__predict_false(dvs == VGET_NONE)) {
4746 		return (cache_fpl_aborted(fpl));
4747 	}
4748 
4749 	vget_finish_ref(dvp, dvs);
4750 	if (!vn_seqc_consistent(dvp, dvp_seqc)) {
4751 		vrele(dvp);
4752 		return (cache_fpl_aborted(fpl));
4753 	}
4754 
4755 	error = vn_lock(dvp, LK_EXCLUSIVE);
4756 	if (__predict_false(error != 0)) {
4757 		vrele(dvp);
4758 		return (cache_fpl_aborted(fpl));
4759 	}
4760 
4761 	tvp = NULL;
4762 	cnp->cn_flags |= ISLASTCN;
4763 	if (docache)
4764 		cnp->cn_flags |= MAKEENTRY;
4765 	if (cache_fpl_isdotdot(cnp))
4766 		cnp->cn_flags |= ISDOTDOT;
4767 	cnp->cn_lkflags = LK_EXCLUSIVE;
4768 	error = VOP_LOOKUP(dvp, &tvp, cnp);
4769 	switch (error) {
4770 	case EJUSTRETURN:
4771 	case 0:
4772 		break;
4773 	case ENOTDIR:
4774 	case ENOENT:
4775 		vput(dvp);
4776 		return (cache_fpl_handled_error(fpl, error));
4777 	default:
4778 		vput(dvp);
4779 		return (cache_fpl_aborted(fpl));
4780 	}
4781 
4782 	fpl->tvp = tvp;
4783 
4784 	if (tvp == NULL) {
4785 		MPASS(error == EJUSTRETURN);
4786 		if ((cnp->cn_flags & LOCKPARENT) == 0) {
4787 			VOP_UNLOCK(dvp);
4788 		}
4789 		return (cache_fpl_handled(fpl));
4790 	}
4791 
4792 	/*
4793 	 * There are very hairy corner cases concerning various flag combinations
4794 	 * and locking state. In particular here we only hold one lock instead of
4795 	 * two.
4796 	 *
4797 	 * Skip the complexity as it is of no significance for normal workloads.
4798 	 */
4799 	if (__predict_false(tvp == dvp)) {
4800 		vput(dvp);
4801 		vrele(tvp);
4802 		return (cache_fpl_aborted(fpl));
4803 	}
4804 
4805 	/*
4806 	 * If they want the symlink itself we are fine, but if they want to
4807 	 * follow it regular lookup has to be engaged.
4808 	 */
4809 	if (tvp->v_type == VLNK) {
4810 		if ((cnp->cn_flags & FOLLOW) != 0) {
4811 			vput(dvp);
4812 			vput(tvp);
4813 			return (cache_fpl_aborted(fpl));
4814 		}
4815 	}
4816 
4817 	/*
4818 	 * Since we expect this to be the terminal vnode it should almost never
4819 	 * be a mount point.
4820 	 */
4821 	if (__predict_false(cache_fplookup_is_mp(fpl))) {
4822 		vput(dvp);
4823 		vput(tvp);
4824 		return (cache_fpl_aborted(fpl));
4825 	}
4826 
4827 	if ((cnp->cn_flags & FAILIFEXISTS) != 0) {
4828 		vput(dvp);
4829 		vput(tvp);
4830 		return (cache_fpl_handled_error(fpl, EEXIST));
4831 	}
4832 
4833 	if ((cnp->cn_flags & LOCKLEAF) == 0) {
4834 		VOP_UNLOCK(tvp);
4835 	}
4836 
4837 	if ((cnp->cn_flags & LOCKPARENT) == 0) {
4838 		VOP_UNLOCK(dvp);
4839 	}
4840 
4841 	return (cache_fpl_handled(fpl));
4842 }
4843 
4844 static int __noinline
4845 cache_fplookup_modifying(struct cache_fpl *fpl)
4846 {
4847 	struct nameidata *ndp;
4848 
4849 	ndp = fpl->ndp;
4850 
4851 	if (!cache_fpl_islastcn(ndp)) {
4852 		return (cache_fpl_partial(fpl));
4853 	}
4854 	return (cache_fplookup_final_modifying(fpl));
4855 }
4856 
4857 static int __noinline
4858 cache_fplookup_final_withparent(struct cache_fpl *fpl)
4859 {
4860 	struct componentname *cnp;
4861 	enum vgetstate dvs, tvs;
4862 	struct vnode *dvp, *tvp;
4863 	seqc_t dvp_seqc;
4864 	int error;
4865 
4866 	cnp = fpl->cnp;
4867 	dvp = fpl->dvp;
4868 	dvp_seqc = fpl->dvp_seqc;
4869 	tvp = fpl->tvp;
4870 
4871 	MPASS((cnp->cn_flags & (LOCKPARENT|WANTPARENT)) != 0);
4872 
4873 	/*
4874 	 * This is less efficient than it can be for simplicity.
4875 	 */
4876 	dvs = vget_prep_smr(dvp);
4877 	if (__predict_false(dvs == VGET_NONE)) {
4878 		return (cache_fpl_aborted(fpl));
4879 	}
4880 	tvs = vget_prep_smr(tvp);
4881 	if (__predict_false(tvs == VGET_NONE)) {
4882 		cache_fpl_smr_exit(fpl);
4883 		vget_abort(dvp, dvs);
4884 		return (cache_fpl_aborted(fpl));
4885 	}
4886 
4887 	cache_fpl_smr_exit(fpl);
4888 
4889 	if ((cnp->cn_flags & LOCKPARENT) != 0) {
4890 		error = vget_finish(dvp, LK_EXCLUSIVE, dvs);
4891 		if (__predict_false(error != 0)) {
4892 			vget_abort(tvp, tvs);
4893 			return (cache_fpl_aborted(fpl));
4894 		}
4895 	} else {
4896 		vget_finish_ref(dvp, dvs);
4897 	}
4898 
4899 	if (!vn_seqc_consistent(dvp, dvp_seqc)) {
4900 		vget_abort(tvp, tvs);
4901 		if ((cnp->cn_flags & LOCKPARENT) != 0)
4902 			vput(dvp);
4903 		else
4904 			vrele(dvp);
4905 		return (cache_fpl_aborted(fpl));
4906 	}
4907 
4908 	error = cache_fplookup_final_child(fpl, tvs);
4909 	if (__predict_false(error != 0)) {
4910 		MPASS(fpl->status == CACHE_FPL_STATUS_ABORTED ||
4911 		    fpl->status == CACHE_FPL_STATUS_DESTROYED);
4912 		if ((cnp->cn_flags & LOCKPARENT) != 0)
4913 			vput(dvp);
4914 		else
4915 			vrele(dvp);
4916 		return (error);
4917 	}
4918 
4919 	MPASS(fpl->status == CACHE_FPL_STATUS_HANDLED);
4920 	return (0);
4921 }
4922 
4923 static int
4924 cache_fplookup_final(struct cache_fpl *fpl)
4925 {
4926 	struct componentname *cnp;
4927 	enum vgetstate tvs;
4928 	struct vnode *dvp, *tvp;
4929 	seqc_t dvp_seqc;
4930 
4931 	cnp = fpl->cnp;
4932 	dvp = fpl->dvp;
4933 	dvp_seqc = fpl->dvp_seqc;
4934 	tvp = fpl->tvp;
4935 
4936 	MPASS(*(cnp->cn_nameptr) != '/');
4937 
4938 	if (cnp->cn_nameiop != LOOKUP) {
4939 		return (cache_fplookup_final_modifying(fpl));
4940 	}
4941 
4942 	if ((cnp->cn_flags & (LOCKPARENT|WANTPARENT)) != 0)
4943 		return (cache_fplookup_final_withparent(fpl));
4944 
4945 	tvs = vget_prep_smr(tvp);
4946 	if (__predict_false(tvs == VGET_NONE)) {
4947 		return (cache_fpl_partial(fpl));
4948 	}
4949 
4950 	if (!vn_seqc_consistent(dvp, dvp_seqc)) {
4951 		cache_fpl_smr_exit(fpl);
4952 		vget_abort(tvp, tvs);
4953 		return (cache_fpl_aborted(fpl));
4954 	}
4955 
4956 	cache_fpl_smr_exit(fpl);
4957 	return (cache_fplookup_final_child(fpl, tvs));
4958 }
4959 
4960 /*
4961  * Comment from locked lookup:
4962  * Check for degenerate name (e.g. / or "") which is a way of talking about a
4963  * directory, e.g. like "/." or ".".
4964  */
4965 static int __noinline
4966 cache_fplookup_degenerate(struct cache_fpl *fpl)
4967 {
4968 	struct componentname *cnp;
4969 	struct vnode *dvp;
4970 	enum vgetstate dvs;
4971 	int error, lkflags;
4972 #ifdef INVARIANTS
4973 	char *cp;
4974 #endif
4975 
4976 	fpl->tvp = fpl->dvp;
4977 	fpl->tvp_seqc = fpl->dvp_seqc;
4978 
4979 	cnp = fpl->cnp;
4980 	dvp = fpl->dvp;
4981 
4982 #ifdef INVARIANTS
4983 	for (cp = cnp->cn_pnbuf; *cp != '\0'; cp++) {
4984 		KASSERT(*cp == '/',
4985 		    ("%s: encountered non-slash; string [%s]\n", __func__,
4986 		    cnp->cn_pnbuf));
4987 	}
4988 #endif
4989 
4990 	if (__predict_false(cnp->cn_nameiop != LOOKUP)) {
4991 		cache_fpl_smr_exit(fpl);
4992 		return (cache_fpl_handled_error(fpl, EISDIR));
4993 	}
4994 
4995 	if ((cnp->cn_flags & (LOCKPARENT|WANTPARENT)) != 0) {
4996 		return (cache_fplookup_final_withparent(fpl));
4997 	}
4998 
4999 	dvs = vget_prep_smr(dvp);
5000 	cache_fpl_smr_exit(fpl);
5001 	if (__predict_false(dvs == VGET_NONE)) {
5002 		return (cache_fpl_aborted(fpl));
5003 	}
5004 
5005 	if ((cnp->cn_flags & LOCKLEAF) != 0) {
5006 		lkflags = LK_SHARED;
5007 		if ((cnp->cn_flags & LOCKSHARED) == 0)
5008 			lkflags = LK_EXCLUSIVE;
5009 		error = vget_finish(dvp, lkflags, dvs);
5010 		if (__predict_false(error != 0)) {
5011 			return (cache_fpl_aborted(fpl));
5012 		}
5013 	} else {
5014 		vget_finish_ref(dvp, dvs);
5015 	}
5016 	return (cache_fpl_handled(fpl));
5017 }
5018 
5019 static int __noinline
5020 cache_fplookup_emptypath(struct cache_fpl *fpl)
5021 {
5022 	struct nameidata *ndp;
5023 	struct componentname *cnp;
5024 	enum vgetstate tvs;
5025 	struct vnode *tvp;
5026 	int error, lkflags;
5027 
5028 	fpl->tvp = fpl->dvp;
5029 	fpl->tvp_seqc = fpl->dvp_seqc;
5030 
5031 	ndp = fpl->ndp;
5032 	cnp = fpl->cnp;
5033 	tvp = fpl->tvp;
5034 
5035 	MPASS(*cnp->cn_pnbuf == '\0');
5036 
5037 	if (__predict_false((cnp->cn_flags & EMPTYPATH) == 0)) {
5038 		cache_fpl_smr_exit(fpl);
5039 		return (cache_fpl_handled_error(fpl, ENOENT));
5040 	}
5041 
5042 	MPASS((cnp->cn_flags & (LOCKPARENT | WANTPARENT)) == 0);
5043 
5044 	tvs = vget_prep_smr(tvp);
5045 	cache_fpl_smr_exit(fpl);
5046 	if (__predict_false(tvs == VGET_NONE)) {
5047 		return (cache_fpl_aborted(fpl));
5048 	}
5049 
5050 	if ((cnp->cn_flags & LOCKLEAF) != 0) {
5051 		lkflags = LK_SHARED;
5052 		if ((cnp->cn_flags & LOCKSHARED) == 0)
5053 			lkflags = LK_EXCLUSIVE;
5054 		error = vget_finish(tvp, lkflags, tvs);
5055 		if (__predict_false(error != 0)) {
5056 			return (cache_fpl_aborted(fpl));
5057 		}
5058 	} else {
5059 		vget_finish_ref(tvp, tvs);
5060 	}
5061 
5062 	ndp->ni_resflags |= NIRES_EMPTYPATH;
5063 	return (cache_fpl_handled(fpl));
5064 }
5065 
5066 static int __noinline
5067 cache_fplookup_noentry(struct cache_fpl *fpl)
5068 {
5069 	struct nameidata *ndp;
5070 	struct componentname *cnp;
5071 	enum vgetstate dvs;
5072 	struct vnode *dvp, *tvp;
5073 	seqc_t dvp_seqc;
5074 	int error;
5075 
5076 	ndp = fpl->ndp;
5077 	cnp = fpl->cnp;
5078 	dvp = fpl->dvp;
5079 	dvp_seqc = fpl->dvp_seqc;
5080 
5081 	MPASS((cnp->cn_flags & MAKEENTRY) == 0);
5082 	MPASS((cnp->cn_flags & ISDOTDOT) == 0);
5083 	if (cnp->cn_nameiop == LOOKUP)
5084 		MPASS((cnp->cn_flags & NOCACHE) == 0);
5085 	MPASS(!cache_fpl_isdotdot(cnp));
5086 
5087 	/*
5088 	 * Hack: delayed name len checking.
5089 	 */
5090 	if (__predict_false(cnp->cn_namelen > NAME_MAX)) {
5091 		cache_fpl_smr_exit(fpl);
5092 		return (cache_fpl_handled_error(fpl, ENAMETOOLONG));
5093 	}
5094 
5095 	if (cnp->cn_nameptr[0] == '/') {
5096 		return (cache_fplookup_skip_slashes(fpl));
5097 	}
5098 
5099 	if (cnp->cn_pnbuf[0] == '\0') {
5100 		return (cache_fplookup_emptypath(fpl));
5101 	}
5102 
5103 	if (cnp->cn_nameptr[0] == '\0') {
5104 		if (fpl->tvp == NULL) {
5105 			return (cache_fplookup_degenerate(fpl));
5106 		}
5107 		return (cache_fplookup_trailingslash(fpl));
5108 	}
5109 
5110 	if (cnp->cn_nameiop != LOOKUP) {
5111 		fpl->tvp = NULL;
5112 		return (cache_fplookup_modifying(fpl));
5113 	}
5114 
5115 	/*
5116 	 * Only try to fill in the component if it is the last one,
5117 	 * otherwise not only there may be several to handle but the
5118 	 * walk may be complicated.
5119 	 */
5120 	if (!cache_fpl_islastcn(ndp)) {
5121 		return (cache_fpl_partial(fpl));
5122 	}
5123 
5124 	/*
5125 	 * Regular lookup nulifies the slash, which we don't do here.
5126 	 * Don't take chances with filesystem routines seeing it for
5127 	 * the last entry.
5128 	 */
5129 	if (cache_fpl_istrailingslash(fpl)) {
5130 		return (cache_fpl_partial(fpl));
5131 	}
5132 
5133 	/*
5134 	 * Secure access to dvp; check cache_fplookup_partial_setup for
5135 	 * reasoning.
5136 	 */
5137 	dvs = vget_prep_smr(dvp);
5138 	cache_fpl_smr_exit(fpl);
5139 	if (__predict_false(dvs == VGET_NONE)) {
5140 		return (cache_fpl_aborted(fpl));
5141 	}
5142 
5143 	vget_finish_ref(dvp, dvs);
5144 	if (!vn_seqc_consistent(dvp, dvp_seqc)) {
5145 		vrele(dvp);
5146 		return (cache_fpl_aborted(fpl));
5147 	}
5148 
5149 	error = vn_lock(dvp, LK_SHARED);
5150 	if (__predict_false(error != 0)) {
5151 		vrele(dvp);
5152 		return (cache_fpl_aborted(fpl));
5153 	}
5154 
5155 	tvp = NULL;
5156 	/*
5157 	 * TODO: provide variants which don't require locking either vnode.
5158 	 */
5159 	cnp->cn_flags |= ISLASTCN | MAKEENTRY;
5160 	cnp->cn_lkflags = LK_SHARED;
5161 	if ((cnp->cn_flags & LOCKSHARED) == 0) {
5162 		cnp->cn_lkflags = LK_EXCLUSIVE;
5163 	}
5164 	error = VOP_LOOKUP(dvp, &tvp, cnp);
5165 	switch (error) {
5166 	case EJUSTRETURN:
5167 	case 0:
5168 		break;
5169 	case ENOTDIR:
5170 	case ENOENT:
5171 		vput(dvp);
5172 		return (cache_fpl_handled_error(fpl, error));
5173 	default:
5174 		vput(dvp);
5175 		return (cache_fpl_aborted(fpl));
5176 	}
5177 
5178 	fpl->tvp = tvp;
5179 
5180 	if (tvp == NULL) {
5181 		MPASS(error == EJUSTRETURN);
5182 		if ((cnp->cn_flags & (WANTPARENT | LOCKPARENT)) == 0) {
5183 			vput(dvp);
5184 		} else if ((cnp->cn_flags & LOCKPARENT) == 0) {
5185 			VOP_UNLOCK(dvp);
5186 		}
5187 		return (cache_fpl_handled(fpl));
5188 	}
5189 
5190 	if (tvp->v_type == VLNK) {
5191 		if ((cnp->cn_flags & FOLLOW) != 0) {
5192 			vput(dvp);
5193 			vput(tvp);
5194 			return (cache_fpl_aborted(fpl));
5195 		}
5196 	}
5197 
5198 	if (__predict_false(cache_fplookup_is_mp(fpl))) {
5199 		vput(dvp);
5200 		vput(tvp);
5201 		return (cache_fpl_aborted(fpl));
5202 	}
5203 
5204 	if ((cnp->cn_flags & LOCKLEAF) == 0) {
5205 		VOP_UNLOCK(tvp);
5206 	}
5207 
5208 	if ((cnp->cn_flags & (WANTPARENT | LOCKPARENT)) == 0) {
5209 		vput(dvp);
5210 	} else if ((cnp->cn_flags & LOCKPARENT) == 0) {
5211 		VOP_UNLOCK(dvp);
5212 	}
5213 	return (cache_fpl_handled(fpl));
5214 }
5215 
5216 static int __noinline
5217 cache_fplookup_dot(struct cache_fpl *fpl)
5218 {
5219 	int error;
5220 
5221 	MPASS(!seqc_in_modify(fpl->dvp_seqc));
5222 
5223 	if (__predict_false(fpl->dvp->v_type != VDIR)) {
5224 		cache_fpl_smr_exit(fpl);
5225 		return (cache_fpl_handled_error(fpl, ENOTDIR));
5226 	}
5227 
5228 	/*
5229 	 * Just re-assign the value. seqc will be checked later for the first
5230 	 * non-dot path component in line and/or before deciding to return the
5231 	 * vnode.
5232 	 */
5233 	fpl->tvp = fpl->dvp;
5234 	fpl->tvp_seqc = fpl->dvp_seqc;
5235 
5236 	SDT_PROBE3(vfs, namecache, lookup, hit, fpl->dvp, ".", fpl->dvp);
5237 
5238 	error = 0;
5239 	if (cache_fplookup_is_mp(fpl)) {
5240 		error = cache_fplookup_cross_mount(fpl);
5241 	}
5242 	return (error);
5243 }
5244 
5245 static int __noinline
5246 cache_fplookup_dotdot(struct cache_fpl *fpl)
5247 {
5248 	struct nameidata *ndp;
5249 	struct componentname *cnp;
5250 	struct namecache *ncp;
5251 	struct vnode *dvp;
5252 	struct prison *pr;
5253 	u_char nc_flag;
5254 
5255 	ndp = fpl->ndp;
5256 	cnp = fpl->cnp;
5257 	dvp = fpl->dvp;
5258 
5259 	MPASS(cache_fpl_isdotdot(cnp));
5260 
5261 	/*
5262 	 * XXX this is racy the same way regular lookup is
5263 	 */
5264 	for (pr = cnp->cn_cred->cr_prison; pr != NULL;
5265 	    pr = pr->pr_parent)
5266 		if (dvp == pr->pr_root)
5267 			break;
5268 
5269 	if (dvp == ndp->ni_rootdir ||
5270 	    dvp == ndp->ni_topdir ||
5271 	    dvp == rootvnode ||
5272 	    pr != NULL) {
5273 		fpl->tvp = dvp;
5274 		fpl->tvp_seqc = vn_seqc_read_any(dvp);
5275 		if (seqc_in_modify(fpl->tvp_seqc)) {
5276 			return (cache_fpl_aborted(fpl));
5277 		}
5278 		return (0);
5279 	}
5280 
5281 	if ((dvp->v_vflag & VV_ROOT) != 0) {
5282 		/*
5283 		 * TODO
5284 		 * The opposite of climb mount is needed here.
5285 		 */
5286 		return (cache_fpl_partial(fpl));
5287 	}
5288 
5289 	if (__predict_false(dvp->v_type != VDIR)) {
5290 		cache_fpl_smr_exit(fpl);
5291 		return (cache_fpl_handled_error(fpl, ENOTDIR));
5292 	}
5293 
5294 	ncp = atomic_load_consume_ptr(&dvp->v_cache_dd);
5295 	if (ncp == NULL) {
5296 		return (cache_fpl_aborted(fpl));
5297 	}
5298 
5299 	nc_flag = atomic_load_char(&ncp->nc_flag);
5300 	if ((nc_flag & NCF_ISDOTDOT) != 0) {
5301 		if ((nc_flag & NCF_NEGATIVE) != 0)
5302 			return (cache_fpl_aborted(fpl));
5303 		fpl->tvp = ncp->nc_vp;
5304 	} else {
5305 		fpl->tvp = ncp->nc_dvp;
5306 	}
5307 
5308 	fpl->tvp_seqc = vn_seqc_read_any(fpl->tvp);
5309 	if (seqc_in_modify(fpl->tvp_seqc)) {
5310 		return (cache_fpl_partial(fpl));
5311 	}
5312 
5313 	/*
5314 	 * Acquire fence provided by vn_seqc_read_any above.
5315 	 */
5316 	if (__predict_false(atomic_load_ptr(&dvp->v_cache_dd) != ncp)) {
5317 		return (cache_fpl_aborted(fpl));
5318 	}
5319 
5320 	if (!cache_ncp_canuse(ncp)) {
5321 		return (cache_fpl_aborted(fpl));
5322 	}
5323 
5324 	return (0);
5325 }
5326 
5327 static int __noinline
5328 cache_fplookup_neg(struct cache_fpl *fpl, struct namecache *ncp, uint32_t hash)
5329 {
5330 	u_char nc_flag __diagused;
5331 	bool neg_promote;
5332 
5333 #ifdef INVARIANTS
5334 	nc_flag = atomic_load_char(&ncp->nc_flag);
5335 	MPASS((nc_flag & NCF_NEGATIVE) != 0);
5336 #endif
5337 	/*
5338 	 * If they want to create an entry we need to replace this one.
5339 	 */
5340 	if (__predict_false(fpl->cnp->cn_nameiop != LOOKUP)) {
5341 		fpl->tvp = NULL;
5342 		return (cache_fplookup_modifying(fpl));
5343 	}
5344 	neg_promote = cache_neg_hit_prep(ncp);
5345 	if (!cache_fpl_neg_ncp_canuse(ncp)) {
5346 		cache_neg_hit_abort(ncp);
5347 		return (cache_fpl_partial(fpl));
5348 	}
5349 	if (neg_promote) {
5350 		return (cache_fplookup_negative_promote(fpl, ncp, hash));
5351 	}
5352 	cache_neg_hit_finish(ncp);
5353 	cache_fpl_smr_exit(fpl);
5354 	return (cache_fpl_handled_error(fpl, ENOENT));
5355 }
5356 
5357 /*
5358  * Resolve a symlink. Called by filesystem-specific routines.
5359  *
5360  * Code flow is:
5361  * ... -> cache_fplookup_symlink -> VOP_FPLOOKUP_SYMLINK -> cache_symlink_resolve
5362  */
5363 int
5364 cache_symlink_resolve(struct cache_fpl *fpl, const char *string, size_t len)
5365 {
5366 	struct nameidata *ndp;
5367 	struct componentname *cnp;
5368 	size_t adjust;
5369 
5370 	ndp = fpl->ndp;
5371 	cnp = fpl->cnp;
5372 
5373 	if (__predict_false(len == 0)) {
5374 		return (ENOENT);
5375 	}
5376 
5377 	if (__predict_false(len > MAXPATHLEN - 2)) {
5378 		if (cache_fpl_istrailingslash(fpl)) {
5379 			return (EAGAIN);
5380 		}
5381 	}
5382 
5383 	ndp->ni_pathlen = fpl->nulchar - cnp->cn_nameptr - cnp->cn_namelen + 1;
5384 #ifdef INVARIANTS
5385 	if (ndp->ni_pathlen != fpl->debug.ni_pathlen) {
5386 		panic("%s: mismatch (%zu != %zu) nulchar %p nameptr %p [%s] ; full string [%s]\n",
5387 		    __func__, ndp->ni_pathlen, fpl->debug.ni_pathlen, fpl->nulchar,
5388 		    cnp->cn_nameptr, cnp->cn_nameptr, cnp->cn_pnbuf);
5389 	}
5390 #endif
5391 
5392 	if (__predict_false(len + ndp->ni_pathlen > MAXPATHLEN)) {
5393 		return (ENAMETOOLONG);
5394 	}
5395 
5396 	if (__predict_false(ndp->ni_loopcnt++ >= MAXSYMLINKS)) {
5397 		return (ELOOP);
5398 	}
5399 
5400 	adjust = len;
5401 	if (ndp->ni_pathlen > 1) {
5402 		bcopy(ndp->ni_next, cnp->cn_pnbuf + len, ndp->ni_pathlen);
5403 	} else {
5404 		if (cache_fpl_istrailingslash(fpl)) {
5405 			adjust = len + 1;
5406 			cnp->cn_pnbuf[len] = '/';
5407 			cnp->cn_pnbuf[len + 1] = '\0';
5408 		} else {
5409 			cnp->cn_pnbuf[len] = '\0';
5410 		}
5411 	}
5412 	bcopy(string, cnp->cn_pnbuf, len);
5413 
5414 	ndp->ni_pathlen += adjust;
5415 	cache_fpl_pathlen_add(fpl, adjust);
5416 	cnp->cn_nameptr = cnp->cn_pnbuf;
5417 	fpl->nulchar = &cnp->cn_nameptr[ndp->ni_pathlen - 1];
5418 	fpl->tvp = NULL;
5419 	return (0);
5420 }
5421 
5422 static int __noinline
5423 cache_fplookup_symlink(struct cache_fpl *fpl)
5424 {
5425 	struct mount *mp;
5426 	struct nameidata *ndp;
5427 	struct componentname *cnp;
5428 	struct vnode *dvp, *tvp;
5429 	int error;
5430 
5431 	ndp = fpl->ndp;
5432 	cnp = fpl->cnp;
5433 	dvp = fpl->dvp;
5434 	tvp = fpl->tvp;
5435 
5436 	if (cache_fpl_islastcn(ndp)) {
5437 		if ((cnp->cn_flags & FOLLOW) == 0) {
5438 			return (cache_fplookup_final(fpl));
5439 		}
5440 	}
5441 
5442 	mp = atomic_load_ptr(&dvp->v_mount);
5443 	if (__predict_false(mp == NULL)) {
5444 		return (cache_fpl_aborted(fpl));
5445 	}
5446 
5447 	/*
5448 	 * Note this check races against setting the flag just like regular
5449 	 * lookup.
5450 	 */
5451 	if (__predict_false((mp->mnt_flag & MNT_NOSYMFOLLOW) != 0)) {
5452 		cache_fpl_smr_exit(fpl);
5453 		return (cache_fpl_handled_error(fpl, EACCES));
5454 	}
5455 
5456 	error = VOP_FPLOOKUP_SYMLINK(tvp, fpl);
5457 	if (__predict_false(error != 0)) {
5458 		switch (error) {
5459 		case EAGAIN:
5460 			return (cache_fpl_partial(fpl));
5461 		case ENOENT:
5462 		case ENAMETOOLONG:
5463 		case ELOOP:
5464 			cache_fpl_smr_exit(fpl);
5465 			return (cache_fpl_handled_error(fpl, error));
5466 		default:
5467 			return (cache_fpl_aborted(fpl));
5468 		}
5469 	}
5470 
5471 	if (*(cnp->cn_nameptr) == '/') {
5472 		fpl->dvp = cache_fpl_handle_root(fpl);
5473 		fpl->dvp_seqc = vn_seqc_read_any(fpl->dvp);
5474 		if (seqc_in_modify(fpl->dvp_seqc)) {
5475 			return (cache_fpl_aborted(fpl));
5476 		}
5477 		/*
5478 		 * The main loop assumes that ->dvp points to a vnode belonging
5479 		 * to a filesystem which can do lockless lookup, but the absolute
5480 		 * symlink can be wandering off to one which does not.
5481 		 */
5482 		mp = atomic_load_ptr(&fpl->dvp->v_mount);
5483 		if (__predict_false(mp == NULL)) {
5484 			return (cache_fpl_aborted(fpl));
5485 		}
5486 		if (!cache_fplookup_mp_supported(mp)) {
5487 			cache_fpl_checkpoint(fpl);
5488 			return (cache_fpl_partial(fpl));
5489 		}
5490 	}
5491 	return (0);
5492 }
5493 
5494 static int
5495 cache_fplookup_next(struct cache_fpl *fpl)
5496 {
5497 	struct componentname *cnp;
5498 	struct namecache *ncp;
5499 	struct vnode *dvp, *tvp;
5500 	u_char nc_flag;
5501 	uint32_t hash;
5502 	int error;
5503 
5504 	cnp = fpl->cnp;
5505 	dvp = fpl->dvp;
5506 	hash = fpl->hash;
5507 
5508 	if (__predict_false(cnp->cn_nameptr[0] == '.')) {
5509 		if (cnp->cn_namelen == 1) {
5510 			return (cache_fplookup_dot(fpl));
5511 		}
5512 		if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.') {
5513 			return (cache_fplookup_dotdot(fpl));
5514 		}
5515 	}
5516 
5517 	MPASS(!cache_fpl_isdotdot(cnp));
5518 
5519 	CK_SLIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
5520 		if (ncp->nc_dvp == dvp && ncp->nc_nlen == cnp->cn_namelen &&
5521 		    !bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen))
5522 			break;
5523 	}
5524 
5525 	if (__predict_false(ncp == NULL)) {
5526 		return (cache_fplookup_noentry(fpl));
5527 	}
5528 
5529 	tvp = atomic_load_ptr(&ncp->nc_vp);
5530 	nc_flag = atomic_load_char(&ncp->nc_flag);
5531 	if ((nc_flag & NCF_NEGATIVE) != 0) {
5532 		return (cache_fplookup_neg(fpl, ncp, hash));
5533 	}
5534 
5535 	if (!cache_ncp_canuse(ncp)) {
5536 		return (cache_fpl_partial(fpl));
5537 	}
5538 
5539 	fpl->tvp = tvp;
5540 	fpl->tvp_seqc = vn_seqc_read_any(tvp);
5541 	if (seqc_in_modify(fpl->tvp_seqc)) {
5542 		return (cache_fpl_partial(fpl));
5543 	}
5544 
5545 	counter_u64_add(numposhits, 1);
5546 	SDT_PROBE3(vfs, namecache, lookup, hit, dvp, ncp->nc_name, tvp);
5547 
5548 	error = 0;
5549 	if (cache_fplookup_is_mp(fpl)) {
5550 		error = cache_fplookup_cross_mount(fpl);
5551 	}
5552 	return (error);
5553 }
5554 
5555 static bool
5556 cache_fplookup_mp_supported(struct mount *mp)
5557 {
5558 
5559 	MPASS(mp != NULL);
5560 	if ((mp->mnt_kern_flag & MNTK_FPLOOKUP) == 0)
5561 		return (false);
5562 	return (true);
5563 }
5564 
5565 /*
5566  * Walk up the mount stack (if any).
5567  *
5568  * Correctness is provided in the following ways:
5569  * - all vnodes are protected from freeing with SMR
5570  * - struct mount objects are type stable making them always safe to access
5571  * - stability of the particular mount is provided by busying it
5572  * - relationship between the vnode which is mounted on and the mount is
5573  *   verified with the vnode sequence counter after busying
5574  * - association between root vnode of the mount and the mount is protected
5575  *   by busy
5576  *
5577  * From that point on we can read the sequence counter of the root vnode
5578  * and get the next mount on the stack (if any) using the same protection.
5579  *
5580  * By the end of successful walk we are guaranteed the reached state was
5581  * indeed present at least at some point which matches the regular lookup.
5582  */
5583 static int __noinline
5584 cache_fplookup_climb_mount(struct cache_fpl *fpl)
5585 {
5586 	struct mount *mp, *prev_mp;
5587 	struct mount_pcpu *mpcpu, *prev_mpcpu;
5588 	struct vnode *vp;
5589 	seqc_t vp_seqc;
5590 
5591 	vp = fpl->tvp;
5592 	vp_seqc = fpl->tvp_seqc;
5593 
5594 	VNPASS(vp->v_type == VDIR || vp->v_type == VREG || vp->v_type == VBAD, vp);
5595 	mp = atomic_load_ptr(&vp->v_mountedhere);
5596 	if (__predict_false(mp == NULL)) {
5597 		return (0);
5598 	}
5599 
5600 	prev_mp = NULL;
5601 	for (;;) {
5602 		if (!vfs_op_thread_enter_crit(mp, mpcpu)) {
5603 			if (prev_mp != NULL)
5604 				vfs_op_thread_exit_crit(prev_mp, prev_mpcpu);
5605 			return (cache_fpl_partial(fpl));
5606 		}
5607 		if (prev_mp != NULL)
5608 			vfs_op_thread_exit_crit(prev_mp, prev_mpcpu);
5609 		if (!vn_seqc_consistent(vp, vp_seqc)) {
5610 			vfs_op_thread_exit_crit(mp, mpcpu);
5611 			return (cache_fpl_partial(fpl));
5612 		}
5613 		if (!cache_fplookup_mp_supported(mp)) {
5614 			vfs_op_thread_exit_crit(mp, mpcpu);
5615 			return (cache_fpl_partial(fpl));
5616 		}
5617 		vp = atomic_load_ptr(&mp->mnt_rootvnode);
5618 		if (vp == NULL) {
5619 			vfs_op_thread_exit_crit(mp, mpcpu);
5620 			return (cache_fpl_partial(fpl));
5621 		}
5622 		vp_seqc = vn_seqc_read_any(vp);
5623 		if (seqc_in_modify(vp_seqc)) {
5624 			vfs_op_thread_exit_crit(mp, mpcpu);
5625 			return (cache_fpl_partial(fpl));
5626 		}
5627 		prev_mp = mp;
5628 		prev_mpcpu = mpcpu;
5629 		mp = atomic_load_ptr(&vp->v_mountedhere);
5630 		if (mp == NULL)
5631 			break;
5632 	}
5633 
5634 	vfs_op_thread_exit_crit(prev_mp, prev_mpcpu);
5635 	fpl->tvp = vp;
5636 	fpl->tvp_seqc = vp_seqc;
5637 	return (0);
5638 }
5639 
5640 static int __noinline
5641 cache_fplookup_cross_mount(struct cache_fpl *fpl)
5642 {
5643 	struct mount *mp;
5644 	struct mount_pcpu *mpcpu;
5645 	struct vnode *vp;
5646 	seqc_t vp_seqc;
5647 
5648 	vp = fpl->tvp;
5649 	vp_seqc = fpl->tvp_seqc;
5650 
5651 	VNPASS(vp->v_type == VDIR || vp->v_type == VREG || vp->v_type == VBAD, vp);
5652 	mp = atomic_load_ptr(&vp->v_mountedhere);
5653 	if (__predict_false(mp == NULL)) {
5654 		return (0);
5655 	}
5656 
5657 	if (!vfs_op_thread_enter_crit(mp, mpcpu)) {
5658 		return (cache_fpl_partial(fpl));
5659 	}
5660 	if (!vn_seqc_consistent(vp, vp_seqc)) {
5661 		vfs_op_thread_exit_crit(mp, mpcpu);
5662 		return (cache_fpl_partial(fpl));
5663 	}
5664 	if (!cache_fplookup_mp_supported(mp)) {
5665 		vfs_op_thread_exit_crit(mp, mpcpu);
5666 		return (cache_fpl_partial(fpl));
5667 	}
5668 	vp = atomic_load_ptr(&mp->mnt_rootvnode);
5669 	if (__predict_false(vp == NULL)) {
5670 		vfs_op_thread_exit_crit(mp, mpcpu);
5671 		return (cache_fpl_partial(fpl));
5672 	}
5673 	vp_seqc = vn_seqc_read_any(vp);
5674 	vfs_op_thread_exit_crit(mp, mpcpu);
5675 	if (seqc_in_modify(vp_seqc)) {
5676 		return (cache_fpl_partial(fpl));
5677 	}
5678 	mp = atomic_load_ptr(&vp->v_mountedhere);
5679 	if (__predict_false(mp != NULL)) {
5680 		/*
5681 		 * There are possibly more mount points on top.
5682 		 * Normally this does not happen so for simplicity just start
5683 		 * over.
5684 		 */
5685 		return (cache_fplookup_climb_mount(fpl));
5686 	}
5687 
5688 	fpl->tvp = vp;
5689 	fpl->tvp_seqc = vp_seqc;
5690 	return (0);
5691 }
5692 
5693 /*
5694  * Check if a vnode is mounted on.
5695  */
5696 static bool
5697 cache_fplookup_is_mp(struct cache_fpl *fpl)
5698 {
5699 	struct vnode *vp;
5700 
5701 	vp = fpl->tvp;
5702 	return ((vn_irflag_read(vp) & VIRF_MOUNTPOINT) != 0);
5703 }
5704 
5705 /*
5706  * Parse the path.
5707  *
5708  * The code was originally copy-pasted from regular lookup and despite
5709  * clean ups leaves performance on the table. Any modifications here
5710  * must take into account that in case off fallback the resulting
5711  * nameidata state has to be compatible with the original.
5712  */
5713 
5714 /*
5715  * Debug ni_pathlen tracking.
5716  */
5717 #ifdef INVARIANTS
5718 static void
5719 cache_fpl_pathlen_add(struct cache_fpl *fpl, size_t n)
5720 {
5721 
5722 	fpl->debug.ni_pathlen += n;
5723 	KASSERT(fpl->debug.ni_pathlen <= PATH_MAX,
5724 	    ("%s: pathlen overflow to %zd\n", __func__, fpl->debug.ni_pathlen));
5725 }
5726 
5727 static void
5728 cache_fpl_pathlen_sub(struct cache_fpl *fpl, size_t n)
5729 {
5730 
5731 	fpl->debug.ni_pathlen -= n;
5732 	KASSERT(fpl->debug.ni_pathlen <= PATH_MAX,
5733 	    ("%s: pathlen underflow to %zd\n", __func__, fpl->debug.ni_pathlen));
5734 }
5735 
5736 static void
5737 cache_fpl_pathlen_inc(struct cache_fpl *fpl)
5738 {
5739 
5740 	cache_fpl_pathlen_add(fpl, 1);
5741 }
5742 
5743 static void
5744 cache_fpl_pathlen_dec(struct cache_fpl *fpl)
5745 {
5746 
5747 	cache_fpl_pathlen_sub(fpl, 1);
5748 }
5749 #else
5750 static void
5751 cache_fpl_pathlen_add(struct cache_fpl *fpl, size_t n)
5752 {
5753 }
5754 
5755 static void
5756 cache_fpl_pathlen_sub(struct cache_fpl *fpl, size_t n)
5757 {
5758 }
5759 
5760 static void
5761 cache_fpl_pathlen_inc(struct cache_fpl *fpl)
5762 {
5763 }
5764 
5765 static void
5766 cache_fpl_pathlen_dec(struct cache_fpl *fpl)
5767 {
5768 }
5769 #endif
5770 
5771 static void
5772 cache_fplookup_parse(struct cache_fpl *fpl)
5773 {
5774 	struct nameidata *ndp;
5775 	struct componentname *cnp;
5776 	struct vnode *dvp;
5777 	char *cp;
5778 	uint32_t hash;
5779 
5780 	ndp = fpl->ndp;
5781 	cnp = fpl->cnp;
5782 	dvp = fpl->dvp;
5783 
5784 	/*
5785 	 * Find the end of this path component, it is either / or nul.
5786 	 *
5787 	 * Store / as a temporary sentinel so that we only have one character
5788 	 * to test for. Pathnames tend to be short so this should not be
5789 	 * resulting in cache misses.
5790 	 *
5791 	 * TODO: fix this to be word-sized.
5792 	 */
5793 	MPASS(&cnp->cn_nameptr[fpl->debug.ni_pathlen - 1] >= cnp->cn_pnbuf);
5794 	KASSERT(&cnp->cn_nameptr[fpl->debug.ni_pathlen - 1] == fpl->nulchar,
5795 	    ("%s: mismatch between pathlen (%zu) and nulchar (%p != %p), string [%s]\n",
5796 	    __func__, fpl->debug.ni_pathlen, &cnp->cn_nameptr[fpl->debug.ni_pathlen - 1],
5797 	    fpl->nulchar, cnp->cn_pnbuf));
5798 	KASSERT(*fpl->nulchar == '\0',
5799 	    ("%s: expected nul at %p; string [%s]\n", __func__, fpl->nulchar,
5800 	    cnp->cn_pnbuf));
5801 	hash = cache_get_hash_iter_start(dvp);
5802 	*fpl->nulchar = '/';
5803 	for (cp = cnp->cn_nameptr; *cp != '/'; cp++) {
5804 		KASSERT(*cp != '\0',
5805 		    ("%s: encountered unexpected nul; string [%s]\n", __func__,
5806 		    cnp->cn_nameptr));
5807 		hash = cache_get_hash_iter(*cp, hash);
5808 		continue;
5809 	}
5810 	*fpl->nulchar = '\0';
5811 	fpl->hash = cache_get_hash_iter_finish(hash);
5812 
5813 	cnp->cn_namelen = cp - cnp->cn_nameptr;
5814 	cache_fpl_pathlen_sub(fpl, cnp->cn_namelen);
5815 
5816 #ifdef INVARIANTS
5817 	/*
5818 	 * cache_get_hash only accepts lengths up to NAME_MAX. This is fine since
5819 	 * we are going to fail this lookup with ENAMETOOLONG (see below).
5820 	 */
5821 	if (cnp->cn_namelen <= NAME_MAX) {
5822 		if (fpl->hash != cache_get_hash(cnp->cn_nameptr, cnp->cn_namelen, dvp)) {
5823 			panic("%s: mismatched hash for [%s] len %ld", __func__,
5824 			    cnp->cn_nameptr, cnp->cn_namelen);
5825 		}
5826 	}
5827 #endif
5828 
5829 	/*
5830 	 * Hack: we have to check if the found path component's length exceeds
5831 	 * NAME_MAX. However, the condition is very rarely true and check can
5832 	 * be elided in the common case -- if an entry was found in the cache,
5833 	 * then it could not have been too long to begin with.
5834 	 */
5835 	ndp->ni_next = cp;
5836 }
5837 
5838 static void
5839 cache_fplookup_parse_advance(struct cache_fpl *fpl)
5840 {
5841 	struct nameidata *ndp;
5842 	struct componentname *cnp;
5843 
5844 	ndp = fpl->ndp;
5845 	cnp = fpl->cnp;
5846 
5847 	cnp->cn_nameptr = ndp->ni_next;
5848 	KASSERT(*(cnp->cn_nameptr) == '/',
5849 	    ("%s: should have seen slash at %p ; buf %p [%s]\n", __func__,
5850 	    cnp->cn_nameptr, cnp->cn_pnbuf, cnp->cn_pnbuf));
5851 	cnp->cn_nameptr++;
5852 	cache_fpl_pathlen_dec(fpl);
5853 }
5854 
5855 /*
5856  * Skip spurious slashes in a pathname (e.g., "foo///bar") and retry.
5857  *
5858  * Lockless lookup tries to elide checking for spurious slashes and should they
5859  * be present is guaranteed to fail to find an entry. In this case the caller
5860  * must check if the name starts with a slash and call this routine.  It is
5861  * going to fast forward across the spurious slashes and set the state up for
5862  * retry.
5863  */
5864 static int __noinline
5865 cache_fplookup_skip_slashes(struct cache_fpl *fpl)
5866 {
5867 	struct nameidata *ndp;
5868 	struct componentname *cnp;
5869 
5870 	ndp = fpl->ndp;
5871 	cnp = fpl->cnp;
5872 
5873 	MPASS(*(cnp->cn_nameptr) == '/');
5874 	do {
5875 		cnp->cn_nameptr++;
5876 		cache_fpl_pathlen_dec(fpl);
5877 	} while (*(cnp->cn_nameptr) == '/');
5878 
5879 	/*
5880 	 * Go back to one slash so that cache_fplookup_parse_advance has
5881 	 * something to skip.
5882 	 */
5883 	cnp->cn_nameptr--;
5884 	cache_fpl_pathlen_inc(fpl);
5885 
5886 	/*
5887 	 * cache_fplookup_parse_advance starts from ndp->ni_next
5888 	 */
5889 	ndp->ni_next = cnp->cn_nameptr;
5890 
5891 	/*
5892 	 * See cache_fplookup_dot.
5893 	 */
5894 	fpl->tvp = fpl->dvp;
5895 	fpl->tvp_seqc = fpl->dvp_seqc;
5896 
5897 	return (0);
5898 }
5899 
5900 /*
5901  * Handle trailing slashes (e.g., "foo/").
5902  *
5903  * If a trailing slash is found the terminal vnode must be a directory.
5904  * Regular lookup shortens the path by nulifying the first trailing slash and
5905  * sets the TRAILINGSLASH flag to denote this took place. There are several
5906  * checks on it performed later.
5907  *
5908  * Similarly to spurious slashes, lockless lookup handles this in a speculative
5909  * manner relying on an invariant that a non-directory vnode will get a miss.
5910  * In this case cn_nameptr[0] == '\0' and cn_namelen == 0.
5911  *
5912  * Thus for a path like "foo/bar/" the code unwinds the state back to "bar/"
5913  * and denotes this is the last path component, which avoids looping back.
5914  *
5915  * Only plain lookups are supported for now to restrict corner cases to handle.
5916  */
5917 static int __noinline
5918 cache_fplookup_trailingslash(struct cache_fpl *fpl)
5919 {
5920 #ifdef INVARIANTS
5921 	size_t ni_pathlen;
5922 #endif
5923 	struct nameidata *ndp;
5924 	struct componentname *cnp;
5925 	struct namecache *ncp;
5926 	struct vnode *tvp;
5927 	char *cn_nameptr_orig, *cn_nameptr_slash;
5928 	seqc_t tvp_seqc;
5929 	u_char nc_flag;
5930 
5931 	ndp = fpl->ndp;
5932 	cnp = fpl->cnp;
5933 	tvp = fpl->tvp;
5934 	tvp_seqc = fpl->tvp_seqc;
5935 
5936 	MPASS(fpl->dvp == fpl->tvp);
5937 	KASSERT(cache_fpl_istrailingslash(fpl),
5938 	    ("%s: expected trailing slash at %p; string [%s]\n", __func__, fpl->nulchar - 1,
5939 	    cnp->cn_pnbuf));
5940 	KASSERT(cnp->cn_nameptr[0] == '\0',
5941 	    ("%s: expected nul char at %p; string [%s]\n", __func__, &cnp->cn_nameptr[0],
5942 	    cnp->cn_pnbuf));
5943 	KASSERT(cnp->cn_namelen == 0,
5944 	    ("%s: namelen 0 but got %ld; string [%s]\n", __func__, cnp->cn_namelen,
5945 	    cnp->cn_pnbuf));
5946 	MPASS(cnp->cn_nameptr > cnp->cn_pnbuf);
5947 
5948 	if (cnp->cn_nameiop != LOOKUP) {
5949 		return (cache_fpl_aborted(fpl));
5950 	}
5951 
5952 	if (__predict_false(tvp->v_type != VDIR)) {
5953 		if (!vn_seqc_consistent(tvp, tvp_seqc)) {
5954 			return (cache_fpl_aborted(fpl));
5955 		}
5956 		cache_fpl_smr_exit(fpl);
5957 		return (cache_fpl_handled_error(fpl, ENOTDIR));
5958 	}
5959 
5960 	/*
5961 	 * Denote the last component.
5962 	 */
5963 	ndp->ni_next = &cnp->cn_nameptr[0];
5964 	MPASS(cache_fpl_islastcn(ndp));
5965 
5966 	/*
5967 	 * Unwind trailing slashes.
5968 	 */
5969 	cn_nameptr_orig = cnp->cn_nameptr;
5970 	while (cnp->cn_nameptr >= cnp->cn_pnbuf) {
5971 		cnp->cn_nameptr--;
5972 		if (cnp->cn_nameptr[0] != '/') {
5973 			break;
5974 		}
5975 	}
5976 
5977 	/*
5978 	 * Unwind to the beginning of the path component.
5979 	 *
5980 	 * Note the path may or may not have started with a slash.
5981 	 */
5982 	cn_nameptr_slash = cnp->cn_nameptr;
5983 	while (cnp->cn_nameptr > cnp->cn_pnbuf) {
5984 		cnp->cn_nameptr--;
5985 		if (cnp->cn_nameptr[0] == '/') {
5986 			break;
5987 		}
5988 	}
5989 	if (cnp->cn_nameptr[0] == '/') {
5990 		cnp->cn_nameptr++;
5991 	}
5992 
5993 	cnp->cn_namelen = cn_nameptr_slash - cnp->cn_nameptr + 1;
5994 	cache_fpl_pathlen_add(fpl, cn_nameptr_orig - cnp->cn_nameptr);
5995 	cache_fpl_checkpoint(fpl);
5996 
5997 #ifdef INVARIANTS
5998 	ni_pathlen = fpl->nulchar - cnp->cn_nameptr + 1;
5999 	if (ni_pathlen != fpl->debug.ni_pathlen) {
6000 		panic("%s: mismatch (%zu != %zu) nulchar %p nameptr %p [%s] ; full string [%s]\n",
6001 		    __func__, ni_pathlen, fpl->debug.ni_pathlen, fpl->nulchar,
6002 		    cnp->cn_nameptr, cnp->cn_nameptr, cnp->cn_pnbuf);
6003 	}
6004 #endif
6005 
6006 	/*
6007 	 * If this was a "./" lookup the parent directory is already correct.
6008 	 */
6009 	if (cnp->cn_nameptr[0] == '.' && cnp->cn_namelen == 1) {
6010 		return (0);
6011 	}
6012 
6013 	/*
6014 	 * Otherwise we need to look it up.
6015 	 */
6016 	tvp = fpl->tvp;
6017 	ncp = atomic_load_consume_ptr(&tvp->v_cache_dd);
6018 	if (__predict_false(ncp == NULL)) {
6019 		return (cache_fpl_aborted(fpl));
6020 	}
6021 	nc_flag = atomic_load_char(&ncp->nc_flag);
6022 	if ((nc_flag & NCF_ISDOTDOT) != 0) {
6023 		return (cache_fpl_aborted(fpl));
6024 	}
6025 	fpl->dvp = ncp->nc_dvp;
6026 	fpl->dvp_seqc = vn_seqc_read_any(fpl->dvp);
6027 	if (seqc_in_modify(fpl->dvp_seqc)) {
6028 		return (cache_fpl_aborted(fpl));
6029 	}
6030 	return (0);
6031 }
6032 
6033 /*
6034  * See the API contract for VOP_FPLOOKUP_VEXEC.
6035  */
6036 static int __noinline
6037 cache_fplookup_failed_vexec(struct cache_fpl *fpl, int error)
6038 {
6039 	struct componentname *cnp;
6040 	struct vnode *dvp;
6041 	seqc_t dvp_seqc;
6042 
6043 	cnp = fpl->cnp;
6044 	dvp = fpl->dvp;
6045 	dvp_seqc = fpl->dvp_seqc;
6046 
6047 	/*
6048 	 * Hack: delayed empty path checking.
6049 	 */
6050 	if (cnp->cn_pnbuf[0] == '\0') {
6051 		return (cache_fplookup_emptypath(fpl));
6052 	}
6053 
6054 	/*
6055 	 * TODO: Due to ignoring trailing slashes lookup will perform a
6056 	 * permission check on the last dir when it should not be doing it.  It
6057 	 * may fail, but said failure should be ignored. It is possible to fix
6058 	 * it up fully without resorting to regular lookup, but for now just
6059 	 * abort.
6060 	 */
6061 	if (cache_fpl_istrailingslash(fpl)) {
6062 		return (cache_fpl_aborted(fpl));
6063 	}
6064 
6065 	/*
6066 	 * Hack: delayed degenerate path checking.
6067 	 */
6068 	if (cnp->cn_nameptr[0] == '\0' && fpl->tvp == NULL) {
6069 		return (cache_fplookup_degenerate(fpl));
6070 	}
6071 
6072 	/*
6073 	 * Hack: delayed name len checking.
6074 	 */
6075 	if (__predict_false(cnp->cn_namelen > NAME_MAX)) {
6076 		cache_fpl_smr_exit(fpl);
6077 		return (cache_fpl_handled_error(fpl, ENAMETOOLONG));
6078 	}
6079 
6080 	/*
6081 	 * Hack: they may be looking up foo/bar, where foo is not a directory.
6082 	 * In such a case we need to return ENOTDIR, but we may happen to get
6083 	 * here with a different error.
6084 	 */
6085 	if (dvp->v_type != VDIR) {
6086 		error = ENOTDIR;
6087 	}
6088 
6089 	/*
6090 	 * Hack: handle O_SEARCH.
6091 	 *
6092 	 * Open Group Base Specifications Issue 7, 2018 edition states:
6093 	 * <quote>
6094 	 * If the access mode of the open file description associated with the
6095 	 * file descriptor is not O_SEARCH, the function shall check whether
6096 	 * directory searches are permitted using the current permissions of
6097 	 * the directory underlying the file descriptor. If the access mode is
6098 	 * O_SEARCH, the function shall not perform the check.
6099 	 * </quote>
6100 	 *
6101 	 * Regular lookup tests for the NOEXECCHECK flag for every path
6102 	 * component to decide whether to do the permission check. However,
6103 	 * since most lookups never have the flag (and when they do it is only
6104 	 * present for the first path component), lockless lookup only acts on
6105 	 * it if there is a permission problem. Here the flag is represented
6106 	 * with a boolean so that we don't have to clear it on the way out.
6107 	 *
6108 	 * For simplicity this always aborts.
6109 	 * TODO: check if this is the first lookup and ignore the permission
6110 	 * problem. Note the flag has to survive fallback (if it happens to be
6111 	 * performed).
6112 	 */
6113 	if (fpl->fsearch) {
6114 		return (cache_fpl_aborted(fpl));
6115 	}
6116 
6117 	switch (error) {
6118 	case EAGAIN:
6119 		if (!vn_seqc_consistent(dvp, dvp_seqc)) {
6120 			error = cache_fpl_aborted(fpl);
6121 		} else {
6122 			cache_fpl_partial(fpl);
6123 		}
6124 		break;
6125 	default:
6126 		if (!vn_seqc_consistent(dvp, dvp_seqc)) {
6127 			error = cache_fpl_aborted(fpl);
6128 		} else {
6129 			cache_fpl_smr_exit(fpl);
6130 			cache_fpl_handled_error(fpl, error);
6131 		}
6132 		break;
6133 	}
6134 	return (error);
6135 }
6136 
6137 static int
6138 cache_fplookup_impl(struct vnode *dvp, struct cache_fpl *fpl)
6139 {
6140 	struct nameidata *ndp;
6141 	struct componentname *cnp;
6142 	struct mount *mp;
6143 	int error;
6144 
6145 	ndp = fpl->ndp;
6146 	cnp = fpl->cnp;
6147 
6148 	cache_fpl_checkpoint(fpl);
6149 
6150 	/*
6151 	 * The vnode at hand is almost always stable, skip checking for it.
6152 	 * Worst case this postpones the check towards the end of the iteration
6153 	 * of the main loop.
6154 	 */
6155 	fpl->dvp = dvp;
6156 	fpl->dvp_seqc = vn_seqc_read_notmodify(fpl->dvp);
6157 
6158 	mp = atomic_load_ptr(&dvp->v_mount);
6159 	if (__predict_false(mp == NULL || !cache_fplookup_mp_supported(mp))) {
6160 		return (cache_fpl_aborted(fpl));
6161 	}
6162 
6163 	MPASS(fpl->tvp == NULL);
6164 
6165 	for (;;) {
6166 		cache_fplookup_parse(fpl);
6167 
6168 		error = VOP_FPLOOKUP_VEXEC(fpl->dvp, cnp->cn_cred);
6169 		if (__predict_false(error != 0)) {
6170 			error = cache_fplookup_failed_vexec(fpl, error);
6171 			break;
6172 		}
6173 
6174 		error = cache_fplookup_next(fpl);
6175 		if (__predict_false(cache_fpl_terminated(fpl))) {
6176 			break;
6177 		}
6178 
6179 		VNPASS(!seqc_in_modify(fpl->tvp_seqc), fpl->tvp);
6180 
6181 		if (fpl->tvp->v_type == VLNK) {
6182 			error = cache_fplookup_symlink(fpl);
6183 			if (cache_fpl_terminated(fpl)) {
6184 				break;
6185 			}
6186 		} else {
6187 			if (cache_fpl_islastcn(ndp)) {
6188 				error = cache_fplookup_final(fpl);
6189 				break;
6190 			}
6191 
6192 			if (!vn_seqc_consistent(fpl->dvp, fpl->dvp_seqc)) {
6193 				error = cache_fpl_aborted(fpl);
6194 				break;
6195 			}
6196 
6197 			fpl->dvp = fpl->tvp;
6198 			fpl->dvp_seqc = fpl->tvp_seqc;
6199 			cache_fplookup_parse_advance(fpl);
6200 		}
6201 
6202 		cache_fpl_checkpoint(fpl);
6203 	}
6204 
6205 	return (error);
6206 }
6207 
6208 /*
6209  * Fast path lookup protected with SMR and sequence counters.
6210  *
6211  * Note: all VOP_FPLOOKUP_VEXEC routines have a comment referencing this one.
6212  *
6213  * Filesystems can opt in by setting the MNTK_FPLOOKUP flag and meeting criteria
6214  * outlined below.
6215  *
6216  * Traditional vnode lookup conceptually looks like this:
6217  *
6218  * vn_lock(current);
6219  * for (;;) {
6220  *	next = find();
6221  *	vn_lock(next);
6222  *	vn_unlock(current);
6223  *	current = next;
6224  *	if (last)
6225  *	    break;
6226  * }
6227  * return (current);
6228  *
6229  * Each jump to the next vnode is safe memory-wise and atomic with respect to
6230  * any modifications thanks to holding respective locks.
6231  *
6232  * The same guarantee can be provided with a combination of safe memory
6233  * reclamation and sequence counters instead. If all operations which affect
6234  * the relationship between the current vnode and the one we are looking for
6235  * also modify the counter, we can verify whether all the conditions held as
6236  * we made the jump. This includes things like permissions, mount points etc.
6237  * Counter modification is provided by enclosing relevant places in
6238  * vn_seqc_write_begin()/end() calls.
6239  *
6240  * Thus this translates to:
6241  *
6242  * vfs_smr_enter();
6243  * dvp_seqc = seqc_read_any(dvp);
6244  * if (seqc_in_modify(dvp_seqc)) // someone is altering the vnode
6245  *     abort();
6246  * for (;;) {
6247  * 	tvp = find();
6248  * 	tvp_seqc = seqc_read_any(tvp);
6249  * 	if (seqc_in_modify(tvp_seqc)) // someone is altering the target vnode
6250  * 	    abort();
6251  * 	if (!seqc_consistent(dvp, dvp_seqc) // someone is altering the vnode
6252  * 	    abort();
6253  * 	dvp = tvp; // we know nothing of importance has changed
6254  * 	dvp_seqc = tvp_seqc; // store the counter for the tvp iteration
6255  * 	if (last)
6256  * 	    break;
6257  * }
6258  * vget(); // secure the vnode
6259  * if (!seqc_consistent(tvp, tvp_seqc) // final check
6260  * 	    abort();
6261  * // at this point we know nothing has changed for any parent<->child pair
6262  * // as they were crossed during the lookup, meaning we matched the guarantee
6263  * // of the locked variant
6264  * return (tvp);
6265  *
6266  * The API contract for VOP_FPLOOKUP_VEXEC routines is as follows:
6267  * - they are called while within vfs_smr protection which they must never exit
6268  * - EAGAIN can be returned to denote checking could not be performed, it is
6269  *   always valid to return it
6270  * - if the sequence counter has not changed the result must be valid
6271  * - if the sequence counter has changed both false positives and false negatives
6272  *   are permitted (since the result will be rejected later)
6273  * - for simple cases of unix permission checks vaccess_vexec_smr can be used
6274  *
6275  * Caveats to watch out for:
6276  * - vnodes are passed unlocked and unreferenced with nothing stopping
6277  *   VOP_RECLAIM, in turn meaning that ->v_data can become NULL. It is advised
6278  *   to use atomic_load_ptr to fetch it.
6279  * - the aforementioned object can also get freed, meaning absent other means it
6280  *   should be protected with vfs_smr
6281  * - either safely checking permissions as they are modified or guaranteeing
6282  *   their stability is left to the routine
6283  */
6284 int
6285 cache_fplookup(struct nameidata *ndp, enum cache_fpl_status *status,
6286     struct pwd **pwdp)
6287 {
6288 	struct cache_fpl fpl;
6289 	struct pwd *pwd;
6290 	struct vnode *dvp;
6291 	struct componentname *cnp;
6292 	int error;
6293 
6294 	fpl.status = CACHE_FPL_STATUS_UNSET;
6295 	fpl.in_smr = false;
6296 	fpl.ndp = ndp;
6297 	fpl.cnp = cnp = &ndp->ni_cnd;
6298 	MPASS(ndp->ni_lcf == 0);
6299 	KASSERT ((cnp->cn_flags & CACHE_FPL_INTERNAL_CN_FLAGS) == 0,
6300 	    ("%s: internal flags found in cn_flags %" PRIx64, __func__,
6301 	    cnp->cn_flags));
6302 	MPASS(cnp->cn_nameptr == cnp->cn_pnbuf);
6303 	MPASS(ndp->ni_resflags == 0);
6304 
6305 	if (__predict_false(!cache_can_fplookup(&fpl))) {
6306 		*status = fpl.status;
6307 		SDT_PROBE3(vfs, fplookup, lookup, done, ndp, fpl.line, fpl.status);
6308 		return (EOPNOTSUPP);
6309 	}
6310 
6311 	cache_fpl_checkpoint_outer(&fpl);
6312 
6313 	cache_fpl_smr_enter_initial(&fpl);
6314 #ifdef INVARIANTS
6315 	fpl.debug.ni_pathlen = ndp->ni_pathlen;
6316 #endif
6317 	fpl.nulchar = &cnp->cn_nameptr[ndp->ni_pathlen - 1];
6318 	fpl.fsearch = false;
6319 	fpl.tvp = NULL; /* for degenerate path handling */
6320 	fpl.pwd = pwdp;
6321 	pwd = pwd_get_smr();
6322 	*(fpl.pwd) = pwd;
6323 	namei_setup_rootdir(ndp, cnp, pwd);
6324 	ndp->ni_topdir = pwd->pwd_jdir;
6325 
6326 	if (cnp->cn_pnbuf[0] == '/') {
6327 		dvp = cache_fpl_handle_root(&fpl);
6328 		ndp->ni_resflags = NIRES_ABS;
6329 	} else {
6330 		if (ndp->ni_dirfd == AT_FDCWD) {
6331 			dvp = pwd->pwd_cdir;
6332 		} else {
6333 			error = cache_fplookup_dirfd(&fpl, &dvp);
6334 			if (__predict_false(error != 0)) {
6335 				goto out;
6336 			}
6337 		}
6338 	}
6339 
6340 	SDT_PROBE4(vfs, namei, lookup, entry, dvp, cnp->cn_pnbuf, cnp->cn_flags, true);
6341 	error = cache_fplookup_impl(dvp, &fpl);
6342 out:
6343 	cache_fpl_smr_assert_not_entered(&fpl);
6344 	cache_fpl_assert_status(&fpl);
6345 	*status = fpl.status;
6346 	if (SDT_PROBES_ENABLED()) {
6347 		SDT_PROBE3(vfs, fplookup, lookup, done, ndp, fpl.line, fpl.status);
6348 		if (fpl.status == CACHE_FPL_STATUS_HANDLED)
6349 			SDT_PROBE4(vfs, namei, lookup, return, error, ndp->ni_vp, true,
6350 			    ndp);
6351 	}
6352 
6353 	if (__predict_true(fpl.status == CACHE_FPL_STATUS_HANDLED)) {
6354 		MPASS(error != CACHE_FPL_FAILED);
6355 		if (error != 0) {
6356 			cache_fpl_cleanup_cnp(fpl.cnp);
6357 			MPASS(fpl.dvp == NULL);
6358 			MPASS(fpl.tvp == NULL);
6359 		}
6360 		ndp->ni_dvp = fpl.dvp;
6361 		ndp->ni_vp = fpl.tvp;
6362 	}
6363 	return (error);
6364 }
6365