sys/kern/vfs_cache.c

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