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