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