sys/kern/vfs_cache.c

   1 /*
   2  * Copyright (c) 2003,2004 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@backplane.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  *
  34  * Copyright (c) 1989, 1993, 1995
  35  *      The Regents of the University of California.  All rights reserved.
  36  *
  37  * This code is derived from software contributed to Berkeley by
  38  * Poul-Henning Kamp of the FreeBSD Project.
  39  *
  40  * Redistribution and use in source and binary forms, with or without
  41  * modification, are permitted provided that the following conditions
  42  * are met:
  43  * 1. Redistributions of source code must retain the above copyright
  44  *    notice, this list of conditions and the following disclaimer.
  45  * 2. Redistributions in binary form must reproduce the above copyright
  46  *    notice, this list of conditions and the following disclaimer in the
  47  *    documentation and/or other materials provided with the distribution.
  48  * 3. All advertising materials mentioning features or use of this software
  49  *    must display the following acknowledgement:
  50  *      This product includes software developed by the University of
  51  *      California, Berkeley and its contributors.
  52  * 4. Neither the name of the University nor the names of its contributors
  53  *    may be used to endorse or promote products derived from this software
  54  *    without specific prior written permission.
  55  *
  56  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  57  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  58  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  59  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  60  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  61  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  62  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  63  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  64  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  65  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  66  * SUCH DAMAGE.
  67  *
  68  *      @(#)vfs_cache.c 8.5 (Berkeley) 3/22/95
  69  * $FreeBSD: src/sys/kern/vfs_cache.c,v 1.42.2.6 2001/10/05 20:07:03 dillon Exp $
  70  * $DragonFly: src/sys/kern/vfs_cache.c,v 1.34 2004/10/05 07:57:40 dillon Exp $
  71  */
  72
  73 #include <sys/param.h>
  74 #include <sys/systm.h>
  75 #include <sys/kernel.h>
  76 #include <sys/sysctl.h>
  77 #include <sys/mount.h>
  78 #include <sys/vnode.h>
  79 #include <sys/malloc.h>
  80 #include <sys/sysproto.h>
  81 #include <sys/proc.h>
  82 #include <sys/namei.h>
  83 #include <sys/nlookup.h>
  84 #include <sys/filedesc.h>
  85 #include <sys/fnv_hash.h>
  86 #include <sys/globaldata.h>
  87 #include <sys/kern_syscall.h>
  88 #include <ddb/ddb.h>
  89
  90 /*
  91  * Random lookups in the cache are accomplished with a hash table using
  92  * a hash key of (nc_src_vp, name).
  93  *
  94  * Negative entries may exist and correspond to structures where nc_vp
  95  * is NULL.  In a negative entry, NCF_WHITEOUT will be set if the entry
  96  * corresponds to a whited-out directory entry (verses simply not finding the
  97  * entry at all).
  98  *
  99  * Upon reaching the last segment of a path, if the reference is for DELETE,
 100  * or NOCACHE is set (rewrite), and the name is located in the cache, it
 101  * will be dropped.
 102  */
 103
 104 /*
 105  * Structures associated with name cacheing.
 106  */
 107 #define NCHHASH(hash)   (&nchashtbl[(hash) & nchash])
 108 #define MINNEG          1024
 109
 110 MALLOC_DEFINE(M_VFSCACHE, "vfscache", "VFS name cache entries");
 111
 112 static LIST_HEAD(nchashhead, namecache) *nchashtbl;     /* Hash Table */
 113 static struct namecache_list    ncneglist;              /* instead of vnode */
 114
 115 static u_long   nchash;                 /* size of hash table */
 116 SYSCTL_ULONG(_debug, OID_AUTO, nchash, CTLFLAG_RD, &nchash, 0, "");
 117
 118 static u_long   ncnegfactor = 16;       /* ratio of negative entries */
 119 SYSCTL_ULONG(_debug, OID_AUTO, ncnegfactor, CTLFLAG_RW, &ncnegfactor, 0, "");
 120
 121 static u_long   numneg;         /* number of cache entries allocated */
 122 SYSCTL_ULONG(_debug, OID_AUTO, numneg, CTLFLAG_RD, &numneg, 0, "");
 123
 124 static u_long   numcache;               /* number of cache entries allocated */
 125 SYSCTL_ULONG(_debug, OID_AUTO, numcache, CTLFLAG_RD, &numcache, 0, "");
 126
 127 static u_long   numunres;               /* number of unresolved entries */
 128 SYSCTL_ULONG(_debug, OID_AUTO, numunres, CTLFLAG_RD, &numunres, 0, "");
 129
 130 SYSCTL_INT(_debug, OID_AUTO, vnsize, CTLFLAG_RD, 0, sizeof(struct vnode), "");
 131 SYSCTL_INT(_debug, OID_AUTO, ncsize, CTLFLAG_RD, 0, sizeof(struct namecache), "");
 132
 133 static int cache_resolve_mp(struct namecache *ncp);
 134 static void cache_rehash(struct namecache *ncp);
 135
 136 /*
 137  * The new name cache statistics
 138  */
 139 SYSCTL_NODE(_vfs, OID_AUTO, cache, CTLFLAG_RW, 0, "Name cache statistics");
 140 #define STATNODE(mode, name, var) \
 141         SYSCTL_ULONG(_vfs_cache, OID_AUTO, name, mode, var, 0, "");
 142 STATNODE(CTLFLAG_RD, numneg, &numneg);
 143 STATNODE(CTLFLAG_RD, numcache, &numcache);
 144 static u_long numcalls; STATNODE(CTLFLAG_RD, numcalls, &numcalls);
 145 static u_long dothits; STATNODE(CTLFLAG_RD, dothits, &dothits);
 146 static u_long dotdothits; STATNODE(CTLFLAG_RD, dotdothits, &dotdothits);
 147 static u_long numchecks; STATNODE(CTLFLAG_RD, numchecks, &numchecks);
 148 static u_long nummiss; STATNODE(CTLFLAG_RD, nummiss, &nummiss);
 149 static u_long nummisszap; STATNODE(CTLFLAG_RD, nummisszap, &nummisszap);
 150 static u_long numposzaps; STATNODE(CTLFLAG_RD, numposzaps, &numposzaps);
 151 static u_long numposhits; STATNODE(CTLFLAG_RD, numposhits, &numposhits);
 152 static u_long numnegzaps; STATNODE(CTLFLAG_RD, numnegzaps, &numnegzaps);
 153 static u_long numneghits; STATNODE(CTLFLAG_RD, numneghits, &numneghits);
 154
 155 struct nchstats nchstats[SMP_MAXCPU];
 156 /*
 157  * Export VFS cache effectiveness statistics to user-land.
 158  *
 159  * The statistics are left for aggregation to user-land so
 160  * neat things can be achieved, like observing per-CPU cache
 161  * distribution.
 162  */
 163 static int
 164 sysctl_nchstats(SYSCTL_HANDLER_ARGS)
 165 {
 166         struct globaldata *gd;
 167         int i, error;
 168
 169         error = 0;
 170         for (i = 0; i < ncpus; ++i) {
 171                 gd = globaldata_find(i);
 172                 if ((error = SYSCTL_OUT(req, (void *)&(*gd->gd_nchstats),
 173                         sizeof(struct nchstats))))
 174                         break;
 175         }
 176
 177         return (error);
 178 }
 179 SYSCTL_PROC(_vfs_cache, OID_AUTO, nchstats, CTLTYPE_OPAQUE|CTLFLAG_RD,
 180   0, 0, sysctl_nchstats, "S,nchstats", "VFS cache effectiveness statistics");
 181
 182 static void cache_zap(struct namecache *ncp);
 183
 184 /*
 185  * cache_hold() and cache_drop() prevent the premature deletion of a
 186  * namecache entry but do not prevent operations (such as zapping) on
 187  * that namecache entry.
 188  */
 189 static __inline
 190 struct namecache *
 191 _cache_hold(struct namecache *ncp)
 192 {
 193         ++ncp->nc_refs;
 194         return(ncp);
 195 }
 196
 197 /*
 198  * When dropping an entry
 199  */
 200 static __inline
 201 void
 202 _cache_drop(struct namecache *ncp)
 203 {
 204         KKASSERT(ncp->nc_refs > 0);
 205         if (ncp->nc_refs == 1 &&
 206             (ncp->nc_flag & NCF_UNRESOLVED) &&
 207             TAILQ_EMPTY(&ncp->nc_list)
 208         ) {
 209                 cache_zap(ncp);
 210         } else {
 211                 --ncp->nc_refs;
 212         }
 213 }
 214
 215 /*
 216  * Link a new namecache entry to its parent.  Be careful to avoid races
 217  * if vhold() blocks in the future.
 218  *
 219  * If we are creating a child under an oldapi parent we must mark the
 220  * child as being an oldapi entry as well.
 221  */
 222 static void
 223 cache_link_parent(struct namecache *ncp, struct namecache *par)
 224 {
 225         KKASSERT(ncp->nc_parent == NULL);
 226         ncp->nc_parent = par;
 227         if (TAILQ_EMPTY(&par->nc_list)) {
 228                 TAILQ_INSERT_HEAD(&par->nc_list, ncp, nc_entry);
 229                 /*
 230                  * Any vp associated with an ncp which has children must
 231                  * be held to prevent it from being recycled.
 232                  */
 233                 if (par->nc_vp)
 234                         vhold(par->nc_vp);
 235         } else {
 236                 TAILQ_INSERT_HEAD(&par->nc_list, ncp, nc_entry);
 237         }
 238 }
 239
 240 /*
 241  * Remove the parent association from a namecache structure.
 242  */
 243 static void
 244 cache_unlink_parent(struct namecache *ncp)
 245 {
 246         struct namecache *par;
 247
 248         if ((par = ncp->nc_parent) != NULL) {
 249                 ncp->nc_parent = NULL;
 250                 par = cache_hold(par);
 251                 TAILQ_REMOVE(&par->nc_list, ncp, nc_entry);
 252                 if (par->nc_vp && TAILQ_EMPTY(&par->nc_list))
 253                         vdrop(par->nc_vp);
 254                 cache_drop(par);
 255         }
 256 }
 257
 258 /*
 259  * Allocate a new namecache structure.
 260  */
 261 static struct namecache *
 262 cache_alloc(int nlen)
 263 {
 264         struct namecache *ncp;
 265
 266         ncp = malloc(sizeof(*ncp), M_VFSCACHE, M_WAITOK|M_ZERO);
 267         if (nlen)
 268                 ncp->nc_name = malloc(nlen, M_VFSCACHE, M_WAITOK);
 269         ncp->nc_nlen = nlen;
 270         ncp->nc_flag = NCF_UNRESOLVED;
 271         ncp->nc_error = ENOTCONN;       /* needs to be resolved */
 272         ncp->nc_refs = 1;
 273         TAILQ_INIT(&ncp->nc_list);
 274         cache_lock(ncp);
 275         return(ncp);
 276 }
 277
 278 static void
 279 cache_free(struct namecache *ncp)
 280 {
 281         KKASSERT(ncp->nc_refs == 1 && ncp->nc_exlocks == 1);
 282         if (ncp->nc_name)
 283                 free(ncp->nc_name, M_VFSCACHE);
 284         free(ncp, M_VFSCACHE);
 285 }
 286
 287 /*
 288  * Ref and deref a namecache structure.
 289  */
 290 struct namecache *
 291 cache_hold(struct namecache *ncp)
 292 {
 293         return(_cache_hold(ncp));
 294 }
 295
 296 void
 297 cache_drop(struct namecache *ncp)
 298 {
 299         _cache_drop(ncp);
 300 }
 301
 302 /*
 303  * Namespace locking.  The caller must already hold a reference to the
 304  * namecache structure in order to lock/unlock it.  This function prevents
 305  * the namespace from being created or destroyed by accessors other then
 306  * the lock holder.
 307  *
 308  * Note that holding a locked namecache structure prevents other threads
 309  * from making namespace changes (e.g. deleting or creating), prevents
 310  * vnode association state changes by other threads, and prevents the
 311  * namecache entry from being resolved or unresolved by other threads.
 312  *
 313  * The lock owner has full authority to associate/disassociate vnodes
 314  * and resolve/unresolve the locked ncp.
 315  *
 316  * In particular, if a vnode is associated with a locked cache entry
 317  * that vnode will *NOT* be recycled.  We accomplish this by vhold()ing the
 318  * vnode.  XXX we should find a more efficient way to prevent the vnode
 319  * from being recycled, but remember that any given vnode may have multiple
 320  * namecache associations (think hardlinks).
 321  */
 322 void
 323 cache_lock(struct namecache *ncp)
 324 {
 325         thread_t td;
 326         int didwarn;
 327
 328         KKASSERT(ncp->nc_refs != 0);
 329         didwarn = 0;
 330         td = curthread;
 331
 332         for (;;) {
 333                 if (ncp->nc_exlocks == 0) {
 334                         ncp->nc_exlocks = 1;
 335                         ncp->nc_locktd = td;
 336                         /*
 337                          * The vp associated with a locked ncp must be held
 338                          * to prevent it from being recycled (which would
 339                          * cause the ncp to become unresolved).
 340                          *
 341                          * XXX loop on race for later MPSAFE work.
 342                          */
 343                         if (ncp->nc_vp)
 344                                 vhold(ncp->nc_vp);
 345                         break;
 346                 }
 347                 if (ncp->nc_locktd == td) {
 348                         ++ncp->nc_exlocks;
 349                         break;
 350                 }
 351                 ncp->nc_flag |= NCF_LOCKREQ;
 352                 if (tsleep(ncp, 0, "clock", hz) == EWOULDBLOCK) {
 353                         if (didwarn == 0) {
 354                                 didwarn = 1;
 355                                 printf("[diagnostic] cache_lock: blocked on %*.*s\n",
 356                                         ncp->nc_nlen, ncp->nc_nlen,
 357                                         ncp->nc_name);
 358                         }
 359                 }
 360         }
 361
 362         if (didwarn == 1) {
 363                 printf("[diagnostic] cache_lock: unblocked %*.*s\n",
 364                         ncp->nc_nlen, ncp->nc_nlen, ncp->nc_name);
 365         }
 366 }
 367
 368 void
 369 cache_unlock(struct namecache *ncp)
 370 {
 371         thread_t td = curthread;
 372
 373         KKASSERT(ncp->nc_refs > 0);
 374         KKASSERT(ncp->nc_exlocks > 0);
 375         KKASSERT(ncp->nc_locktd == td);
 376         if (--ncp->nc_exlocks == 0) {
 377                 if (ncp->nc_vp)
 378                         vdrop(ncp->nc_vp);
 379                 ncp->nc_locktd = NULL;
 380                 if (ncp->nc_flag & NCF_LOCKREQ) {
 381                         ncp->nc_flag &= ~NCF_LOCKREQ;
 382                         wakeup_one(ncp);
 383                 }
 384         }
 385 }
 386
 387 /*
 388  * ref-and-lock, unlock-and-deref functions.
 389  */
 390 struct namecache *
 391 cache_get(struct namecache *ncp)
 392 {
 393         _cache_hold(ncp);
 394         cache_lock(ncp);
 395         return(ncp);
 396 }
 397
 398 int
 399 cache_get_nonblock(struct namecache *ncp)
 400 {
 401         /* XXX MP */
 402         if (ncp->nc_exlocks == 0 || ncp->nc_locktd == curthread) {
 403                 _cache_hold(ncp);
 404                 cache_lock(ncp);
 405                 return(0);
 406         }
 407         return(EWOULDBLOCK);
 408 }
 409
 410 void
 411 cache_put(struct namecache *ncp)
 412 {
 413         cache_unlock(ncp);
 414         _cache_drop(ncp);
 415 }
 416
 417 /*
 418  * Resolve an unresolved ncp by associating a vnode with it.  If the
 419  * vnode is NULL, a negative cache entry is created.
 420  *
 421  * The ncp should be locked on entry and will remain locked on return.
 422  */
 423
 424 void
 425 cache_setvp(struct namecache *ncp, struct vnode *vp)
 426 {
 427         KKASSERT(ncp->nc_flag & NCF_UNRESOLVED);
 428         ncp->nc_vp = vp;
 429         if (vp != NULL) {
 430                 /*
 431                  * Any vp associated with an ncp which has children must
 432                  * be held.  Any vp associated with a locked ncp must be held.
 433                  */
 434                 if (!TAILQ_EMPTY(&ncp->nc_list))
 435                         vhold(vp);
 436                 TAILQ_INSERT_HEAD(&vp->v_namecache, ncp, nc_vnode);
 437                 if (ncp->nc_exlocks)
 438                         vhold(vp);
 439
 440                 /*
 441                  * Set auxillary flags
 442                  */
 443                 switch(vp->v_type) {
 444                 case VDIR:
 445                         ncp->nc_flag |= NCF_ISDIR;
 446                         break;
 447                 case VLNK:
 448                         ncp->nc_flag |= NCF_ISSYMLINK;
 449                         /* XXX cache the contents of the symlink */
 450                         break;
 451                 default:
 452                         break;
 453                 }
 454                 ++numcache;
 455                 ncp->nc_error = 0;
 456         } else {
 457                 TAILQ_INSERT_TAIL(&ncneglist, ncp, nc_vnode);
 458                 ++numneg;
 459                 ncp->nc_error = ENOENT;
 460         }
 461         ncp->nc_flag &= ~NCF_UNRESOLVED;
 462 }
 463
 464 /*
 465  * Disassociate the vnode or negative-cache association and mark a
 466  * namecache entry as unresolved again.  Note that the ncp is still
 467  * left in the hash table and still linked to its parent.
 468  *
 469  * The ncp should be locked on entry and will remain locked on return.
 470  *
 471  * This routine is normally never called on a directory containing children.
 472  * However, NFS often does just that in its rename() code as a cop-out to
 473  * avoid complex namespace operations.  This disconnects a directory vnode
 474  * from its namecache and can cause the OLDAPI and NEWAPI to get out of
 475  * sync.
 476  */
 477 void
 478 cache_setunresolved(struct namecache *ncp)
 479 {
 480         struct vnode *vp;
 481
 482         if ((ncp->nc_flag & NCF_UNRESOLVED) == 0) {
 483                 ncp->nc_flag |= NCF_UNRESOLVED;
 484                 ncp->nc_flag &= ~(NCF_WHITEOUT|NCF_ISDIR|NCF_ISSYMLINK);
 485                 ncp->nc_error = ENOTCONN;
 486                 ++numunres;
 487                 if ((vp = ncp->nc_vp) != NULL) {
 488                         --numcache;
 489                         ncp->nc_vp = NULL;      /* safety */
 490                         TAILQ_REMOVE(&vp->v_namecache, ncp, nc_vnode);
 491
 492                         /*
 493                          * Any vp associated with an ncp with children is
 494                          * held by that ncp.  Any vp associated with a locked
 495                          * ncp is held by that ncp.  These conditions must be
 496                          * undone when the vp is cleared out from the ncp.
 497                          */
 498                         if (!TAILQ_EMPTY(&ncp->nc_list))
 499                                 vdrop(vp);
 500                         if (ncp->nc_exlocks)
 501                                 vdrop(vp);
 502                 } else {
 503                         TAILQ_REMOVE(&ncneglist, ncp, nc_vnode);
 504                         --numneg;
 505                 }
 506
 507 #if 0
 508                 if (TAILQ_FIRST(&ncp->nc_list)) {
 509                         db_print_backtrace();
 510                         printf("[diagnostic] cache_setunresolved() called on directory with children: %p %*.*s\n", ncp, ncp->nc_nlen, ncp->nc_nlen, ncp->nc_name);
 511                 }
 512 #endif
 513         }
 514 }
 515
 516 /*
 517  * Invalidate portions of a namecache entry.  The passed ncp should be
 518  * referenced and locked but we might not adhere to that rule during the
 519  * old api -> new api transition period.
 520  *
 521  * CINV_PARENT          - disconnect the ncp from its parent
 522  * CINV_SELF            - same as cache_setunresolved(ncp)
 523  * CINV_CHILDREN        - disconnect children of the ncp from the ncp
 524  */
 525 void
 526 cache_inval(struct namecache *ncp, int flags)
 527 {
 528         struct namecache *kid;
 529
 530         if (flags & CINV_SELF)
 531                 cache_setunresolved(ncp);
 532         if (flags & CINV_PARENT) {
 533                 ncp->nc_flag |= NCF_REVALPARENT;
 534                 cache_unlink_parent(ncp);
 535         }
 536         if (flags & CINV_CHILDREN) {
 537                 while ((kid = TAILQ_FIRST(&ncp->nc_list)) != NULL) {
 538                         kid->nc_flag |= NCF_REVALPARENT;
 539                         cache_unlink_parent(kid);
 540                 }
 541         }
 542 }
 543
 544 void
 545 cache_inval_vp(struct vnode *vp, int flags)
 546 {
 547         struct namecache *ncp;
 548
 549         if (flags & CINV_SELF) {
 550                 while ((ncp = TAILQ_FIRST(&vp->v_namecache)) != NULL) {
 551                         cache_hold(ncp);
 552                         KKASSERT((ncp->nc_flag & NCF_UNRESOLVED) == 0);
 553                         cache_inval(ncp, flags);
 554                         cache_drop(ncp);
 555                 }
 556         } else {
 557                 TAILQ_FOREACH(ncp, &vp->v_namecache, nc_vnode) {
 558                         cache_hold(ncp);
 559                         cache_inval(ncp, flags);
 560                         cache_drop(ncp);
 561                 }
 562         }
 563 }
 564
 565 /*
 566  * vget the vnode associated with the namecache entry.  Resolve the namecache
 567  * entry if necessary and deal with namecache/vp races.  The passed ncp must
 568  * be referenced and may be locked.  The ncp's ref/locking state is not
 569  * effected by this call.
 570  *
 571  * lk_type may be LK_SHARED, LK_EXCLUSIVE.  A ref'd, possibly locked
 572  * (depending on the passed lk_type) will be returned in *vpp with an error
 573  * of 0, or NULL will be returned in *vpp with a non-0 error code.  The
 574  * most typical error is ENOENT, meaning that the ncp represents a negative
 575  * cache hit and there is no vnode to retrieve, but other errors can occur
 576  * too.
 577  *
 578  * The main race we have to deal with are namecache zaps.  The ncp itself
 579  * will not disappear since it is referenced, and it turns out that the
 580  * validity of the vp pointer can be checked simply by rechecking the
 581  * contents of ncp->nc_vp.
 582  */
 583 int
 584 cache_vget(struct namecache *ncp, struct ucred *cred,
 585            int lk_type, struct vnode **vpp)
 586 {
 587         struct vnode *vp;
 588         int error;
 589
 590 again:
 591         vp = NULL;
 592         if (ncp->nc_flag & NCF_UNRESOLVED) {
 593                 cache_lock(ncp);
 594                 error = cache_resolve(ncp, cred);
 595                 cache_unlock(ncp);
 596         } else {
 597                 error = 0;
 598         }
 599         if (error == 0 && (vp = ncp->nc_vp) != NULL) {
 600                 error = vget(vp, NULL, lk_type, curthread);
 601                 if (error) {
 602                         if (vp != ncp->nc_vp)   /* handle cache_zap race */
 603                                 goto again;
 604                         vp = NULL;
 605                 } else if (vp != ncp->nc_vp) {  /* handle cache_zap race */
 606                         vput(vp);
 607                         goto again;
 608                 }
 609         }
 610         if (error == 0 && vp == NULL)
 611                 error = ENOENT;
 612         *vpp = vp;
 613         return(error);
 614 }
 615
 616 int
 617 cache_vref(struct namecache *ncp, struct ucred *cred, struct vnode **vpp)
 618 {
 619         struct vnode *vp;
 620         int error;
 621
 622 again:
 623         vp = NULL;
 624         if (ncp->nc_flag & NCF_UNRESOLVED) {
 625                 cache_lock(ncp);
 626                 error = cache_resolve(ncp, cred);
 627                 cache_unlock(ncp);
 628         } else {
 629                 error = 0;
 630         }
 631         if (error == 0 && (vp = ncp->nc_vp) != NULL) {
 632                 vref(vp);
 633                 if (vp != ncp->nc_vp) {         /* handle cache_zap race */
 634                         vrele(vp);
 635                         goto again;
 636                 }
 637         }
 638         if (error == 0 && vp == NULL)
 639                 error = ENOENT;
 640         *vpp = vp;
 641         return(error);
 642 }
 643
 644 /*
 645  * Try to destroy a namecache entry.  The entry is disassociated from its
 646  * vnode or ncneglist and reverted to an UNRESOLVED state.
 647  *
 648  * Then, if there are no additional references to the ncp and we can
 649  * successfully delete the children, the entry is also removed from the
 650  * namecache hashlist / topology.
 651  *
 652  * References or undeletable children will prevent the entry from being
 653  * removed from the topology.  The entry may be revalidated (typically
 654  * by cache_enter()) at a later time.  Children remain because:
 655  *
 656  *      + we have tried to delete a node rather then a leaf in the topology.
 657  *      + the presence of negative entries (we try to scrap these).
 658  *      + an entry or child has a non-zero ref count and cannot be scrapped.
 659  *
 660  * This function must be called with the ncp held and will drop the ref
 661  * count during zapping.
 662  */
 663 static void
 664 cache_zap(struct namecache *ncp)
 665 {
 666         struct namecache *par;
 667
 668         /*
 669          * Disassociate the vnode or negative cache ref and set NCF_UNRESOLVED.
 670          */
 671         cache_setunresolved(ncp);
 672
 673         /*
 674          * Try to scrap the entry and possibly tail-recurse on its parent.
 675          * We only scrap unref'd (other then our ref) unresolved entries,
 676          * we do not scrap 'live' entries.
 677          */
 678         while (ncp->nc_flag & NCF_UNRESOLVED) {
 679                 /*
 680                  * Someone other then us has a ref, stop.
 681                  */
 682                 if (ncp->nc_refs > 1)
 683                         goto done;
 684
 685                 /*
 686                  * We have children, stop.
 687                  */
 688                 if (!TAILQ_EMPTY(&ncp->nc_list))
 689                         goto done;
 690
 691                 if (ncp->nc_flag & NCF_HASHED) {
 692                         ncp->nc_flag &= ~NCF_HASHED;
 693                         LIST_REMOVE(ncp, nc_hash);
 694                 }
 695
 696                 /*
 697                  * Unlink from its parent and free, then loop on the
 698                  * parent.  XXX temp hack, in stage-3 parent is never NULL
 699                  */
 700                 if ((par = ncp->nc_parent) != NULL) {
 701                         par = cache_hold(par);
 702                         TAILQ_REMOVE(&par->nc_list, ncp, nc_entry);
 703                         if (par->nc_vp && TAILQ_EMPTY(&par->nc_list))
 704                                 vdrop(par->nc_vp);
 705                         /* keep ref on par */
 706                 }
 707                 --numunres;
 708                 ncp->nc_refs = -1;      /* safety */
 709                 ncp->nc_parent = NULL;  /* safety */
 710                 if (ncp->nc_name)
 711                         free(ncp->nc_name, M_VFSCACHE);
 712                 free(ncp, M_VFSCACHE);
 713                 if ((ncp = par) == NULL)
 714                         return;
 715         }
 716 done:
 717         --ncp->nc_refs;
 718 }
 719
 720 /*
 721  * NEW NAMECACHE LOOKUP API
 722  *
 723  * Lookup an entry in the cache.  A locked, referenced, non-NULL
 724  * entry is *always* returned, even if the supplied component is illegal.
 725  * The returned namecache entry should be returned to the system with
 726  * cache_put() or cache_unlock() + cache_drop().
 727  *
 728  * namecache locks are recursive but care must be taken to avoid lock order
 729  * reversals.
 730  *
 731  * Nobody else will be able to manipulate the associated namespace (e.g.
 732  * create, delete, rename, rename-target) until the caller unlocks the
 733  * entry.
 734  *
 735  * The returned entry will be in one of three states:  positive hit (non-null
 736  * vnode), negative hit (null vnode), or unresolved (NCF_UNRESOLVED is set).
 737  * Unresolved entries must be resolved through the filesystem to associate the
 738  * vnode and/or determine whether a positive or negative hit has occured.
 739  *
 740  * It is not necessary to lock a directory in order to lock namespace under
 741  * that directory.  In fact, it is explicitly not allowed to do that.  A
 742  * directory is typically only locked when being created, renamed, or
 743  * destroyed.
 744  *
 745  * The directory (par) may be unresolved, in which case any returned child
 746  * will likely also be marked unresolved.  Likely but not guarenteed.  Since
 747  * the filesystem VOP_NEWLOOKUP() requires a resolved directory vnode the
 748  * caller is responsible for resolving the namecache chain top-down.  This API
 749  * specifically allows whole chains to be created in an unresolved state.
 750  */
 751 struct namecache *
 752 cache_nlookup(struct namecache *par, struct nlcomponent *nlc)
 753 {
 754         struct namecache *ncp;
 755         struct namecache *new_ncp;
 756         struct nchashhead *nchpp;
 757         u_int32_t hash;
 758         globaldata_t gd;
 759
 760         numcalls++;
 761         gd = mycpu;
 762
 763         /*
 764          * Try to locate an existing entry
 765          */
 766         hash = fnv_32_buf(nlc->nlc_nameptr, nlc->nlc_namelen, FNV1_32_INIT);
 767         hash = fnv_32_buf(&par, sizeof(par), hash);
 768         new_ncp = NULL;
 769 restart:
 770         LIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
 771                 numchecks++;
 772
 773                 /*
 774                  * Zap entries that have timed out.
 775                  */
 776                 if (ncp->nc_timeout &&
 777                     (int)(ncp->nc_timeout - ticks) < 0
 778                 ) {
 779                         cache_zap(cache_hold(ncp));
 780                         goto restart;
 781                 }
 782
 783                 /*
 784                  * Break out if we find a matching entry.  Note that
 785                  * UNRESOLVED entries may match.
 786                  */
 787                 if (ncp->nc_parent == par &&
 788                     ncp->nc_nlen == nlc->nlc_namelen &&
 789                     bcmp(ncp->nc_name, nlc->nlc_nameptr, ncp->nc_nlen) == 0
 790                 ) {
 791                         cache_get(ncp);
 792                         if (new_ncp)
 793                                 cache_free(new_ncp);
 794                         goto found;
 795                 }
 796         }
 797
 798         /*
 799          * We failed to locate an entry, create a new entry and add it to
 800          * the cache.  We have to relookup after possibly blocking in
 801          * malloc.
 802          */
 803         if (new_ncp == NULL) {
 804                 new_ncp = cache_alloc(nlc->nlc_namelen);
 805                 goto restart;
 806         }
 807
 808         ncp = new_ncp;
 809
 810         /*
 811          * Initialize as a new UNRESOLVED entry, lock (non-blocking),
 812          * and link to the parent.
 813          */
 814         bcopy(nlc->nlc_nameptr, ncp->nc_name, nlc->nlc_namelen);
 815         nchpp = NCHHASH(hash);
 816         LIST_INSERT_HEAD(nchpp, ncp, nc_hash);
 817         ncp->nc_flag |= NCF_HASHED;
 818         cache_link_parent(ncp, par);
 819 found:
 820         return(ncp);
 821 }
 822
 823 /*
 824  * Resolve an unresolved namecache entry, generally by looking it up.
 825  * The passed ncp must be locked.
 826  *
 827  * Theoretically since a vnode cannot be recycled while held, and since
 828  * the nc_parent chain holds its vnode as long as children exist, the
 829  * direct parent of the cache entry we are trying to resolve should
 830  * have a valid vnode.  If not then generate an error that we can
 831  * determine is related to a resolver bug.
 832  */
 833 int
 834 cache_resolve(struct namecache *ncp, struct ucred *cred)
 835 {
 836         struct namecache *par;
 837         struct namecache *scan;
 838
 839         /*
 840          * If the ncp is already resolved we have nothing to do.
 841          */
 842         if ((ncp->nc_flag & NCF_UNRESOLVED) == 0)
 843                 return (ncp->nc_error);
 844
 845         /*
 846          * Mount points need special handling because the parent does not
 847          * belong to the same filesystem as the ncp.
 848          */
 849         if (ncp->nc_flag & NCF_MOUNTPT)
 850                 return (cache_resolve_mp(ncp));
 851
 852         /*
 853          * We expect an unbroken chain of ncps to at least the mount point,
 854          * and even all the way to root (but this code doesn't have to go
 855          * past the mount point).
 856          */
 857         if (ncp->nc_parent == NULL) {
 858                 printf("EXDEV case 1 %p %*.*s\n", ncp,
 859                         ncp->nc_nlen, ncp->nc_nlen, ncp->nc_name);
 860                 ncp->nc_error = EXDEV;
 861                 return(ncp->nc_error);
 862         }
 863
 864         /*
 865          * The vp's of the parent directories in the chain are held via vhold()
 866          * due to the existance of the child, and should not disappear.
 867          * However, there are cases where they can disappear:
 868          *
 869          *      - due to filesystem I/O errors.
 870          *      - due to NFS being stupid about tracking the namespace and
 871          *        destroys the namespace for entire directories quite often.
 872          *      - due to forced unmounts.
 873          *
 874          * When this occurs we have to track the chain backwards and resolve
 875          * it, looping until the resolver catches up to the current node.  We
 876          * could recurse here but we might run ourselves out of kernel stack
 877          * so we do it in a more painful manner.  This situation really should
 878          * not occur all that often, or if it does not have to go back too
 879          * many nodes to resolve the ncp.
 880          */
 881         while (ncp->nc_parent->nc_vp == NULL) {
 882                 par = ncp->nc_parent;
 883                 while (par->nc_parent && par->nc_parent->nc_vp == NULL)
 884                         par = par->nc_parent;
 885                 if (par->nc_parent == NULL) {
 886                         printf("EXDEV case 2 %*.*s\n",
 887                                 par->nc_nlen, par->nc_nlen, par->nc_name);
 888                         return (EXDEV);
 889                 }
 890                 printf("[diagnostic] cache_resolve: had to recurse on %*.*s\n",
 891                         par->nc_nlen, par->nc_nlen, par->nc_name);
 892                 /*
 893                  * The leaf prevents the parent from going away, but a
 894                  * separate ref is still required to lock it.  Use cache_get()
 895                  * instead of cache_lock().
 896                  */
 897                 cache_get(par);
 898                 if (par->nc_flag & NCF_MOUNTPT) {
 899                         cache_resolve_mp(par);
 900                 } else if (par->nc_parent->nc_vp == NULL) {
 901                         printf("[diagnostic] cache_resolve: raced on %*.*s\n", par->nc_nlen, par->nc_nlen, par->nc_name);
 902                         cache_put(par);
 903                         continue;
 904                 } else {
 905                         par->nc_error =
 906                             vop_resolve(par->nc_parent->nc_vp->v_ops, par, cred);
 907                 }
 908                 cache_put(par);
 909                 if (par->nc_error) {
 910                         printf("EXDEV case 3 %*.*s error %d\n",
 911                                 par->nc_nlen, par->nc_nlen, par->nc_name,
 912                                 par->nc_error);
 913                         return(par->nc_error);
 914                 }
 915         }
 916
 917         /*
 918          * Call vop_resolve() to get the vp, then scan for any disconnected
 919          * ncp's and reattach them.  If this occurs the original ncp is marked
 920          * EAGAIN to force a relookup.
 921          */
 922         KKASSERT((ncp->nc_flag & NCF_MOUNTPT) == 0);
 923         ncp->nc_error = vop_resolve(ncp->nc_parent->nc_vp->v_ops, ncp, cred);
 924         if (ncp->nc_error == 0) {
 925                 TAILQ_FOREACH(scan, &ncp->nc_vp->v_namecache, nc_vnode) {
 926                         if (scan != ncp && (scan->nc_flag & NCF_REVALPARENT)) {
 927                                 cache_link_parent(scan, ncp->nc_parent);
 928                                 cache_unlink_parent(ncp);
 929                                 scan->nc_flag &= ~NCF_REVALPARENT;
 930                                 ncp->nc_error = EAGAIN;
 931                                 if (scan->nc_flag & NCF_HASHED)
 932                                         cache_rehash(scan);
 933                                 printf("[diagnostic] cache_resolve: relinked %*.*s\n", scan->nc_nlen, scan->nc_nlen, scan->nc_name);
 934                                 break;
 935                         }
 936                 }
 937         }
 938         return(ncp->nc_error);
 939 }
 940
 941 /*
 942  * Resolve the ncp associated with a mount point.  Such ncp's almost always
 943  * remain resolved and this routine is rarely called.  NFS MPs tends to force
 944  * re-resolution more often due to its mac-truck-smash-the-namecache
 945  * method of tracking namespace changes.
 946  *
 947  * The passed ncp must be locked.
 948  */
 949 static int
 950 cache_resolve_mp(struct namecache *ncp)
 951 {
 952         struct vnode *vp;
 953         struct mount *mp = ncp->nc_mount;
 954
 955         KKASSERT(mp != NULL);
 956         if (ncp->nc_flag & NCF_UNRESOLVED) {
 957                 while (vfs_busy(mp, 0, NULL, curthread))
 958                         ;
 959                 ncp->nc_error = VFS_ROOT(mp, &vp);
 960                 if (ncp->nc_error == 0) {
 961                         cache_setvp(ncp, vp);
 962                         vput(vp);
 963                 } else {
 964                         printf("[diagnostic] cache_resolve_mp: failed to resolve mount %p\n", mp);
 965                         cache_setvp(ncp, NULL);
 966                 }
 967                 vfs_unbusy(mp, curthread);
 968         }
 969         return(ncp->nc_error);
 970 }
 971
 972 /*
 973  * Lookup an entry in the cache.
 974  *
 975  * XXX OLD API ROUTINE!  WHEN ALL VFSs HAVE BEEN CLEANED UP THIS PROCEDURE
 976  * WILL BE REMOVED.
 977  *
 978  * Lookup is called with dvp pointing to the directory to search,
 979  * cnp pointing to the name of the entry being sought.
 980  *
 981  * If the lookup succeeds, the vnode is returned in *vpp, and a
 982  * status of -1 is returned.
 983  *
 984  * If the lookup determines that the name does not exist (negative cacheing),
 985  * a status of ENOENT is returned.
 986  *
 987  * If the lookup fails, a status of zero is returned.
 988  *
 989  * Matching UNRESOLVED entries are resolved.
 990  *
 991  * HACKS: we create dummy nodes for parents
 992  */
 993 int
 994 cache_lookup(struct vnode *dvp, struct vnode **vpp, struct componentname *cnp)
 995 {
 996         struct namecache *ncp;
 997         struct namecache *par;
 998         struct namecache *bpar;
 999         u_int32_t hash;
1000         globaldata_t gd = mycpu;
1001
1002         numcalls++;
1003
1004         /*
1005          * Obtain the namecache entry associated with dvp.  If there is no
1006          * entry then assume a miss.
1007          */
1008         if ((par = TAILQ_FIRST(&dvp->v_namecache)) == NULL) {
1009                 if ((cnp->cn_flags & CNP_MAKEENTRY) == 0) {
1010                         nummisszap++;
1011                 } else {
1012                         nummiss++;
1013                 }
1014                 gd->gd_nchstats->ncs_miss++;
1015                 return (0);
1016         }
1017
1018         /*
1019          * Deal with "." and "..".   Note that if the namecache is disjoint,
1020          * we won't find a vnode for ".." and we return a miss.
1021          */
1022         if (cnp->cn_nameptr[0] == '.') {
1023                 if (cnp->cn_namelen == 1) {
1024                         *vpp = dvp;
1025                         dothits++;
1026                         numposhits++;   /* include in total statistics */
1027                         return (-1);
1028                 }
1029                 if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.') {
1030                         if ((cnp->cn_flags & CNP_MAKEENTRY) == 0) {
1031                                 dotdothits++;
1032                                 numposhits++;
1033                                 return (0);
1034                         }
1035                         if (par->nc_parent == NULL ||
1036                             par->nc_parent->nc_vp == NULL) {
1037                                 nummiss++;
1038                                 gd->gd_nchstats->ncs_miss++;
1039                                 return (0);
1040                         }
1041                         *vpp = par->nc_parent->nc_vp;
1042                         dotdothits++;
1043                         numposhits++;   /* include in total statistics */
1044                         return (-1);
1045                 }
1046         }
1047
1048         /*
1049          * Try to locate an existing entry
1050          */
1051         cache_hold(par);
1052         hash = fnv_32_buf(cnp->cn_nameptr, cnp->cn_namelen, FNV1_32_INIT);
1053         bpar = par;
1054         hash = fnv_32_buf(&bpar, sizeof(bpar), hash);
1055 restart:
1056         LIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
1057                 numchecks++;
1058
1059                 /*
1060                  * Zap entries that have timed out.  Don't do anything if
1061                  * the entry is in an unresolved state or is held locked.
1062                  */
1063                 if (ncp->nc_timeout &&
1064                     (int)(ncp->nc_timeout - ticks) < 0 &&
1065                     !(ncp->nc_flag & NCF_UNRESOLVED) &&
1066                     ncp->nc_exlocks == 0
1067                 ) {
1068                         cache_zap(cache_hold(ncp));
1069                         goto restart;
1070                 }
1071
1072                 /*
1073                  * Break out if we find a matching entry.
1074                  */
1075                 if (ncp->nc_parent == par &&
1076                     ncp->nc_nlen == cnp->cn_namelen &&
1077                     bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen) == 0
1078                 ) {
1079                         cache_hold(ncp);
1080                         break;
1081                 }
1082         }
1083         cache_drop(par);
1084
1085         /*
1086          * We found an entry but it is unresolved, act the same as if we
1087          * failed to locate the entry.  cache_enter() will do the right
1088          * thing.
1089          */
1090         if (ncp && (ncp->nc_flag & NCF_UNRESOLVED)) {
1091                 cache_drop(ncp);
1092                 ncp = NULL;
1093         }
1094
1095         /*
1096          * If we failed to locate an entry, return 0 (indicates failure).
1097          */
1098         if (ncp == NULL) {
1099                 if ((cnp->cn_flags & CNP_MAKEENTRY) == 0) {
1100                         nummisszap++;
1101                 } else {
1102                         nummiss++;
1103                 }
1104                 gd->gd_nchstats->ncs_miss++;
1105                 return (0);
1106         }
1107
1108         /*
1109          * If we found an entry, but we don't want to have one, we zap it.
1110          * If we are deleting, we disconnect it as well.
1111          */
1112         if ((cnp->cn_flags & CNP_MAKEENTRY) == 0) {
1113                 if (cnp->cn_nameiop == NAMEI_DELETE)
1114                         cache_inval(ncp, CINV_PARENT|CINV_SELF|CINV_CHILDREN);
1115                 numposzaps++;
1116                 gd->gd_nchstats->ncs_badhits++;
1117                 cache_zap(ncp);
1118                 return (0);
1119         }
1120
1121         /*
1122          * If the vnode is not NULL then return the positive match.
1123          */
1124         if (ncp->nc_vp) {
1125                 numposhits++;
1126                 gd->gd_nchstats->ncs_goodhits++;
1127                 *vpp = ncp->nc_vp;
1128                 cache_drop(ncp);
1129                 return (-1);
1130         }
1131
1132         /*
1133          * If the vnode is NULL we found a negative match.  If we want to
1134          * create it, purge the negative match and return failure (as if
1135          * we hadn't found a match in the first place).
1136          */
1137         if (cnp->cn_nameiop == NAMEI_CREATE) {
1138                 numnegzaps++;
1139                 gd->gd_nchstats->ncs_badhits++;
1140                 cache_zap(ncp);
1141                 return (0);
1142         }
1143
1144         numneghits++;
1145
1146         /*
1147          * We found a "negative" match, ENOENT notifies client of this match.
1148          * The nc_flag field records whether this is a whiteout.  Since there
1149          * is no vnode we can use the vnode tailq link field with ncneglist.
1150          */
1151         TAILQ_REMOVE(&ncneglist, ncp, nc_vnode);
1152         TAILQ_INSERT_TAIL(&ncneglist, ncp, nc_vnode);
1153         gd->gd_nchstats->ncs_neghits++;
1154         if (ncp->nc_flag & NCF_WHITEOUT)
1155                 cnp->cn_flags |= CNP_ISWHITEOUT;
1156         cache_drop(ncp);
1157         return (ENOENT);
1158 }
1159
1160 /*
1161  * Add an entry to the cache.  (OLD API)
1162  *
1163  * XXX OLD API ROUTINE!  WHEN ALL VFSs HAVE BEEN CLEANED UP THIS PROCEDURE
1164  * WILL BE REMOVED.
1165  *
1166  * Generally speaking this is 'optional'.  It's ok to do nothing at all.
1167  * The only reason I don't just return is to try to set nc_timeout if
1168  * requested.
1169  */
1170 void
1171 cache_enter(struct vnode *dvp, struct vnode *vp, struct componentname *cnp)
1172 {
1173         struct namecache *par;
1174         struct namecache *ncp;
1175         struct namecache *new_ncp;
1176         struct namecache *bpar;
1177         struct nchashhead *nchpp;
1178         u_int32_t hash;
1179
1180         /*
1181          * If the directory has no namecache entry we bail.  This will result
1182          * in a lot of misses but frankly we don't have much of a choice if
1183          * we want to be compatible with the new api's storage scheme.
1184          */
1185         if ((ncp = TAILQ_FIRST(&dvp->v_namecache)) == NULL)
1186                 return;
1187         cache_hold(ncp);
1188
1189         /*
1190          * This may be a bit confusing.  "." and ".." are 'virtual' entries.
1191          * We do not actually create a namecache entry representing either.
1192          * However, the ".." case is used to linkup a potentially disjoint
1193          * directory with its parent, to disconnect a directory from its
1194          * parent, or to change an existing linkage that may no longer be
1195          * correct (as might occur when a subdirectory is renamed).
1196          */
1197
1198         if (cnp->cn_namelen == 1 && cnp->cn_nameptr[0] == '.') {
1199                 cache_drop(ncp);
1200                 return;
1201         }
1202         if (cnp->cn_namelen == 2 && cnp->cn_nameptr[0] == '.' &&
1203             cnp->cn_nameptr[1] == '.'
1204         ) {
1205                 cache_drop(ncp);
1206                 return;
1207         }
1208
1209         /*
1210          * Ok, no special cases, ncp is actually the parent directory so
1211          * assign it to par.  Note that it is held.
1212          */
1213         par = ncp;
1214
1215 #if 0
1216         /*
1217          * Locate other entries associated with this vnode and zap them,
1218          * because the purge code may not be able to find them due to
1219          * the topology not yet being consistent.  This is a hack (this
1220          * whole routine is a hack, actually, so that makes this a hack
1221          * inside a hack).
1222          */
1223         if (vp) {
1224 again:
1225                 TAILQ_FOREACH(ncp, &vp->v_namecache, nc_vnode) {
1226                         if ((ncp->nc_flag & NCF_UNRESOLVED) == 0 &&
1227                             ncp->nc_parent != par) {
1228                                 cache_zap(cache_hold(ncp));
1229                                 goto again;
1230                         }
1231                 }
1232         }
1233 #endif
1234
1235         /*
1236          * Try to find a match in the hash table, allocate a new entry if
1237          * we can't.  We have to retry the loop after any potential blocking
1238          * situation.
1239          */
1240         bpar = par;
1241         hash = fnv_32_buf(cnp->cn_nameptr, cnp->cn_namelen, FNV1_32_INIT);
1242         hash = fnv_32_buf(&bpar, sizeof(bpar), hash);
1243
1244         new_ncp = NULL;
1245 againagain:
1246         LIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
1247                 numchecks++;
1248
1249                 /*
1250                  * Break out if we find a matching entry.  Because cache_enter
1251                  * is called with one or more vnodes potentially locked, we
1252                  * cannot block trying to get the ncp lock (or we might
1253                  * deadlock).
1254                  */
1255                 if (ncp->nc_parent == par &&
1256                     ncp->nc_nlen == cnp->cn_namelen &&
1257                     bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen) == 0
1258                 ) {
1259                         if (cache_get_nonblock(ncp) != 0) {
1260                                 printf("[diagnostic] cache_enter: avoided race on %p %*.*s\n", ncp, ncp->nc_nlen, ncp->nc_nlen, ncp->nc_name);
1261                                 cache_drop(par);
1262                                 return;
1263                         }
1264                         break;
1265                 }
1266         }
1267         if (ncp == NULL) {
1268                 if (new_ncp == NULL) {
1269                         new_ncp = cache_alloc(cnp->cn_namelen);
1270                         goto againagain;
1271                 }
1272                 ncp = new_ncp;
1273                 bcopy(cnp->cn_nameptr, ncp->nc_name, cnp->cn_namelen);
1274                 nchpp = NCHHASH(hash);
1275                 LIST_INSERT_HEAD(nchpp, ncp, nc_hash);
1276                 ncp->nc_flag |= NCF_HASHED;
1277                 cache_link_parent(ncp, par);
1278         } else if (new_ncp) {
1279                 cache_free(new_ncp);
1280         }
1281         cache_drop(par);
1282
1283         /*
1284          * Avoid side effects if we are simply re-entering the same
1285          * information.
1286          */
1287         if ((ncp->nc_flag & NCF_UNRESOLVED) == 0 && ncp->nc_vp == vp) {
1288                 ncp->nc_error = vp ? 0 : ENOENT;
1289         } else {
1290                 cache_setunresolved(ncp);
1291                 cache_setvp(ncp, vp);
1292         }
1293
1294         /*
1295          * Set a timeout
1296          */
1297         if (cnp->cn_flags & CNP_CACHETIMEOUT) {
1298                 if ((ncp->nc_timeout = ticks + cnp->cn_timeout) == 0)
1299                         ncp->nc_timeout = 1;
1300         }
1301
1302         /*
1303          * If the target vnode is NULL if this is to be a negative cache
1304          * entry.
1305          */
1306         if (vp == NULL) {
1307                 ncp->nc_flag &= ~NCF_WHITEOUT;
1308                 if (cnp->cn_flags & CNP_ISWHITEOUT)
1309                         ncp->nc_flag |= NCF_WHITEOUT;
1310         }
1311         cache_put(ncp);
1312
1313         /*
1314          * Don't cache too many negative hits
1315          */
1316         if (numneg > MINNEG && numneg * ncnegfactor > numcache) {
1317                 ncp = TAILQ_FIRST(&ncneglist);
1318                 KKASSERT(ncp != NULL);
1319                 cache_zap(cache_hold(ncp));
1320         }
1321 }
1322
1323 static void
1324 cache_rehash(struct namecache *ncp)
1325 {
1326         struct nchashhead *nchpp;
1327         u_int32_t hash;
1328
1329         if (ncp->nc_flag & NCF_HASHED) {
1330                 ncp->nc_flag &= ~NCF_HASHED;
1331                 LIST_REMOVE(ncp, nc_hash);
1332         }
1333         hash = fnv_32_buf(ncp->nc_name, ncp->nc_nlen, FNV1_32_INIT);
1334         hash = fnv_32_buf(&ncp->nc_parent, sizeof(ncp->nc_parent), hash);
1335         nchpp = NCHHASH(hash);
1336         LIST_INSERT_HEAD(nchpp, ncp, nc_hash);
1337         ncp->nc_flag |= NCF_HASHED;
1338 }
1339
1340
1341 /*
1342  * Name cache initialization, from vfsinit() when we are booting
1343  */
1344 void
1345 nchinit(void)
1346 {
1347         int i;
1348         globaldata_t gd;
1349
1350         /* initialise per-cpu namecache effectiveness statistics. */
1351         for (i = 0; i < ncpus; ++i) {
1352                 gd = globaldata_find(i);
1353                 gd->gd_nchstats = &nchstats[i];
1354         }
1355
1356         TAILQ_INIT(&ncneglist);
1357         nchashtbl = hashinit(desiredvnodes*2, M_VFSCACHE, &nchash);
1358 }
1359
1360 /*
1361  * Called from start_init() to bootstrap the root filesystem.  Returns
1362  * a referenced, unlocked namecache record.
1363  */
1364 struct namecache *
1365 cache_allocroot(struct vnode *vp)
1366 {
1367         struct namecache *ncp = cache_alloc(0);
1368
1369         ncp->nc_flag |= NCF_MOUNTPT | NCF_ROOT;
1370         cache_setvp(ncp, vp);
1371         return(ncp);
1372 }
1373
1374 /*
1375  * vfs_cache_setroot()
1376  *
1377  *      Create an association between the root of our namecache and
1378  *      the root vnode.  This routine may be called several times during
1379  *      booting.
1380  *
1381  *      If the caller intends to save the returned namecache pointer somewhere
1382  *      it must cache_hold() it.
1383  */
1384 void
1385 vfs_cache_setroot(struct vnode *nvp, struct namecache *ncp)
1386 {
1387         struct vnode *ovp;
1388         struct namecache *oncp;
1389
1390         ovp = rootvnode;
1391         oncp = rootncp;
1392         rootvnode = nvp;
1393         rootncp = ncp;
1394
1395         if (ovp)
1396                 vrele(ovp);
1397         if (oncp)
1398                 cache_drop(oncp);
1399 }
1400
1401 /*
1402  * Invalidate all namecache entries to a particular vnode as well as
1403  * any direct children of that vnode in the namecache.  This is a
1404  * 'catch all' purge used by filesystems that do not know any better.
1405  *
1406  * A new vnode v_id is generated.  Note that no vnode will ever have a
1407  * v_id of 0.
1408  *
1409  * Note that the linkage between the vnode and its namecache entries will
1410  * be removed, but the namecache entries themselves might stay put due to
1411  * active references from elsewhere in the system or due to the existance of
1412  * the children.   The namecache topology is left intact even if we do not
1413  * know what the vnode association is.  Such entries will be marked
1414  * NCF_UNRESOLVED.
1415  *
1416  * XXX: Only time and the size of v_id prevents this from failing:
1417  * XXX: In theory we should hunt down all (struct vnode*, v_id)
1418  * XXX: soft references and nuke them, at least on the global
1419  * XXX: v_id wraparound.  The period of resistance can be extended
1420  * XXX: by incrementing each vnodes v_id individually instead of
1421  * XXX: using the global v_id.
1422  */
1423 void
1424 cache_purge(struct vnode *vp)
1425 {
1426         static u_long nextid;
1427
1428         cache_inval_vp(vp, CINV_PARENT | CINV_SELF | CINV_CHILDREN);
1429
1430         /*
1431          * Calculate a new unique id for ".." handling
1432          */
1433         do {
1434                 nextid++;
1435         } while (nextid == vp->v_id || nextid == 0);
1436         vp->v_id = nextid;
1437 }
1438
1439 /*
1440  * Flush all entries referencing a particular filesystem.
1441  *
1442  * Since we need to check it anyway, we will flush all the invalid
1443  * entries at the same time.
1444  */
1445 void
1446 cache_purgevfs(struct mount *mp)
1447 {
1448         struct nchashhead *nchpp;
1449         struct namecache *ncp, *nnp;
1450
1451         /*
1452          * Scan hash tables for applicable entries.
1453          */
1454         for (nchpp = &nchashtbl[nchash]; nchpp >= nchashtbl; nchpp--) {
1455                 ncp = LIST_FIRST(nchpp);
1456                 if (ncp)
1457                         cache_hold(ncp);
1458                 while (ncp) {
1459                         nnp = LIST_NEXT(ncp, nc_hash);
1460                         if (nnp)
1461                                 cache_hold(nnp);
1462                         if (ncp->nc_vp && ncp->nc_vp->v_mount == mp)
1463                                 cache_zap(ncp);
1464                         else
1465                                 cache_drop(ncp);
1466                         ncp = nnp;
1467                 }
1468         }
1469 }
1470
1471 /*
1472  * cache_leaf_test()
1473  *
1474  *      Test whether the vnode is at a leaf in the nameicache tree.
1475  *
1476  *      Returns 0 if it is a leaf, -1 if it isn't.
1477  */
1478 int
1479 cache_leaf_test(struct vnode *vp)
1480 {
1481         struct namecache *scan;
1482         struct namecache *ncp;
1483
1484         TAILQ_FOREACH(scan, &vp->v_namecache, nc_vnode) {
1485                 TAILQ_FOREACH(ncp, &scan->nc_list, nc_entry) {
1486                         /* YYY && ncp->nc_vp->v_type == VDIR ? */
1487                         if (ncp->nc_vp != NULL)
1488                                 return(-1);
1489                 }
1490         }
1491         return(0);
1492 }
1493
1494 /*
1495  * Perform canonical checks and cache lookup and pass on to filesystem
1496  * through the vop_cachedlookup only if needed.
1497  *
1498  * vop_lookup_args {
1499  *      struct vnode a_dvp;
1500  *      struct vnode **a_vpp;
1501  *      struct componentname *a_cnp;
1502  * }
1503  */
1504 int
1505 vfs_cache_lookup(struct vop_lookup_args *ap)
1506 {
1507         struct vnode *dvp, *vp;
1508         int lockparent;
1509         int error;
1510         struct vnode **vpp = ap->a_vpp;
1511         struct componentname *cnp = ap->a_cnp;
1512         struct ucred *cred = cnp->cn_cred;
1513         int flags = cnp->cn_flags;
1514         struct thread *td = cnp->cn_td;
1515         u_long vpid;    /* capability number of vnode */
1516
1517         *vpp = NULL;
1518         dvp = ap->a_dvp;
1519         lockparent = flags & CNP_LOCKPARENT;
1520
1521         if (dvp->v_type != VDIR)
1522                 return (ENOTDIR);
1523
1524         if ((flags & CNP_ISLASTCN) && (dvp->v_mount->mnt_flag & MNT_RDONLY) &&
1525             (cnp->cn_nameiop == NAMEI_DELETE || cnp->cn_nameiop == NAMEI_RENAME)) {
1526                 return (EROFS);
1527         }
1528
1529         error = VOP_ACCESS(dvp, VEXEC, cred, td);
1530
1531         if (error)
1532                 return (error);
1533
1534         error = cache_lookup(dvp, vpp, cnp);
1535
1536         if (!error)
1537                 return (VOP_CACHEDLOOKUP(dvp, vpp, cnp));
1538
1539         if (error == ENOENT)
1540                 return (error);
1541
1542         vp = *vpp;
1543         vpid = vp->v_id;
1544         cnp->cn_flags &= ~CNP_PDIRUNLOCK;
1545         if (dvp == vp) {   /* lookup on "." */
1546                 vref(vp);
1547                 error = 0;
1548         } else if (flags & CNP_ISDOTDOT) {
1549                 VOP_UNLOCK(dvp, NULL, 0, td);
1550                 cnp->cn_flags |= CNP_PDIRUNLOCK;
1551                 error = vget(vp, NULL, LK_EXCLUSIVE, td);
1552                 if (!error && lockparent && (flags & CNP_ISLASTCN)) {
1553                         if ((error = vn_lock(dvp, NULL, LK_EXCLUSIVE, td)) == 0)
1554                                 cnp->cn_flags &= ~CNP_PDIRUNLOCK;
1555                 }
1556         } else {
1557                 error = vget(vp, NULL, LK_EXCLUSIVE, td);
1558                 if (!lockparent || error || !(flags & CNP_ISLASTCN)) {
1559                         VOP_UNLOCK(dvp, NULL, 0, td);
1560                         cnp->cn_flags |= CNP_PDIRUNLOCK;
1561                 }
1562         }
1563         /*
1564          * Check that the capability number did not change
1565          * while we were waiting for the lock.
1566          */
1567         if (!error) {
1568                 if (vpid == vp->v_id)
1569                         return (0);
1570                 vput(vp);
1571                 if (lockparent && dvp != vp && (flags & CNP_ISLASTCN)) {
1572                         VOP_UNLOCK(dvp, NULL, 0, td);
1573                         cnp->cn_flags |= CNP_PDIRUNLOCK;
1574                 }
1575         }
1576         if (cnp->cn_flags & CNP_PDIRUNLOCK) {
1577                 error = vn_lock(dvp, NULL, LK_EXCLUSIVE, td);
1578                 if (error)
1579                         return (error);
1580                 cnp->cn_flags &= ~CNP_PDIRUNLOCK;
1581         }
1582         return (VOP_CACHEDLOOKUP(dvp, vpp, cnp));
1583 }
1584
1585 static int disablecwd;
1586 SYSCTL_INT(_debug, OID_AUTO, disablecwd, CTLFLAG_RW, &disablecwd, 0, "");
1587
1588 static u_long numcwdcalls; STATNODE(CTLFLAG_RD, numcwdcalls, &numcwdcalls);
1589 static u_long numcwdfail1; STATNODE(CTLFLAG_RD, numcwdfail1, &numcwdfail1);
1590 static u_long numcwdfail2; STATNODE(CTLFLAG_RD, numcwdfail2, &numcwdfail2);
1591 static u_long numcwdfail3; STATNODE(CTLFLAG_RD, numcwdfail3, &numcwdfail3);
1592 static u_long numcwdfail4; STATNODE(CTLFLAG_RD, numcwdfail4, &numcwdfail4);
1593 static u_long numcwdfound; STATNODE(CTLFLAG_RD, numcwdfound, &numcwdfound);
1594
1595 int
1596 __getcwd(struct __getcwd_args *uap)
1597 {
1598         int buflen;
1599         int error;
1600         char *buf;
1601         char *bp;
1602
1603         if (disablecwd)
1604                 return (ENODEV);
1605
1606         buflen = uap->buflen;
1607         if (buflen < 2)
1608                 return (EINVAL);
1609         if (buflen > MAXPATHLEN)
1610                 buflen = MAXPATHLEN;
1611
1612         buf = malloc(buflen, M_TEMP, M_WAITOK);
1613         bp = kern_getcwd(buf, buflen, &error);
1614         if (error == 0)
1615                 error = copyout(bp, uap->buf, strlen(bp) + 1);
1616         free(buf, M_TEMP);
1617         return (error);
1618 }
1619
1620 char *
1621 kern_getcwd(char *buf, size_t buflen, int *error)
1622 {
1623         struct proc *p = curproc;
1624         char *bp;
1625         int i, slash_prefixed;
1626         struct filedesc *fdp;
1627         struct namecache *ncp;
1628
1629         numcwdcalls++;
1630         bp = buf;
1631         bp += buflen - 1;
1632         *bp = '\0';
1633         fdp = p->p_fd;
1634         slash_prefixed = 0;
1635
1636         ncp = fdp->fd_ncdir;
1637         while (ncp && ncp != fdp->fd_nrdir && (ncp->nc_flag & NCF_ROOT) == 0) {
1638                 if (ncp->nc_flag & NCF_MOUNTPT) {
1639                         if (ncp->nc_mount == NULL) {
1640                                 *error = EBADF;         /* forced unmount? */
1641                                 return(NULL);
1642                         }
1643                         ncp = ncp->nc_parent;
1644                         continue;
1645                 }
1646                 for (i = ncp->nc_nlen - 1; i >= 0; i--) {
1647                         if (bp == buf) {
1648                                 numcwdfail4++;
1649                                 *error = ENOMEM;
1650                                 return(NULL);
1651                         }
1652                         *--bp = ncp->nc_name[i];
1653                 }
1654                 if (bp == buf) {
1655                         numcwdfail4++;
1656                         *error = ENOMEM;
1657                         return(NULL);
1658                 }
1659                 *--bp = '/';
1660                 slash_prefixed = 1;
1661                 ncp = ncp->nc_parent;
1662         }
1663         if (ncp == NULL) {
1664                 numcwdfail2++;
1665                 *error = ENOENT;
1666                 return(NULL);
1667         }
1668         if (!slash_prefixed) {
1669                 if (bp == buf) {
1670                         numcwdfail4++;
1671                         *error = ENOMEM;
1672                         return(NULL);
1673                 }
1674                 *--bp = '/';
1675         }
1676         numcwdfound++;
1677         *error = 0;
1678         return (bp);
1679 }
1680
1681 /*
1682  * Thus begins the fullpath magic.
1683  */
1684
1685 #undef STATNODE
1686 #define STATNODE(name)                                                  \
1687         static u_int name;                                              \
1688         SYSCTL_UINT(_vfs_cache, OID_AUTO, name, CTLFLAG_RD, &name, 0, "")
1689
1690 static int disablefullpath;
1691 SYSCTL_INT(_debug, OID_AUTO, disablefullpath, CTLFLAG_RW,
1692     &disablefullpath, 0, "");
1693
1694 STATNODE(numfullpathcalls);
1695 STATNODE(numfullpathfail1);
1696 STATNODE(numfullpathfail2);
1697 STATNODE(numfullpathfail3);
1698 STATNODE(numfullpathfail4);
1699 STATNODE(numfullpathfound);
1700
1701 int
1702 vn_fullpath(struct proc *p, struct vnode *vn, char **retbuf, char **freebuf)
1703 {
1704         char *bp, *buf;
1705         int i, slash_prefixed;
1706         struct filedesc *fdp;
1707         struct namecache *ncp;
1708
1709         numfullpathcalls++;
1710         if (disablefullpath)
1711                 return (ENODEV);
1712
1713         if (p == NULL)
1714                 return (EINVAL);
1715
1716         /* vn is NULL, client wants us to use p->p_textvp */
1717         if (vn == NULL) {
1718                 if ((vn = p->p_textvp) == NULL)
1719                         return (EINVAL);
1720         }
1721         ncp = TAILQ_FIRST(&vn->v_namecache);
1722         if (ncp == NULL)
1723                 return (EINVAL);
1724
1725         buf = malloc(MAXPATHLEN, M_TEMP, M_WAITOK);
1726         bp = buf + MAXPATHLEN - 1;
1727         *bp = '\0';
1728         fdp = p->p_fd;
1729         slash_prefixed = 0;
1730         while (ncp && ncp != fdp->fd_nrdir && (ncp->nc_flag & NCF_ROOT) == 0) {
1731                 if (ncp->nc_flag & NCF_MOUNTPT) {
1732                         if (ncp->nc_mount == NULL) {
1733                                 free(buf, M_TEMP);
1734                                 return(EBADF);
1735                         }
1736                         ncp = ncp->nc_parent;
1737                         continue;
1738                 }
1739                 for (i = ncp->nc_nlen - 1; i >= 0; i--) {
1740                         if (bp == buf) {
1741                                 numfullpathfail4++;
1742                                 free(buf, M_TEMP);
1743                                 return (ENOMEM);
1744                         }
1745                         *--bp = ncp->nc_name[i];
1746                 }
1747                 if (bp == buf) {
1748                         numfullpathfail4++;
1749                         free(buf, M_TEMP);
1750                         return (ENOMEM);
1751                 }
1752                 *--bp = '/';
1753                 slash_prefixed = 1;
1754                 ncp = ncp->nc_parent;
1755         }
1756         if (ncp == NULL) {
1757                 numfullpathfail2++;
1758                 free(buf, M_TEMP);
1759                 return (ENOENT);
1760         }
1761         if (!slash_prefixed) {
1762                 if (bp == buf) {
1763                         numfullpathfail4++;
1764                         free(buf, M_TEMP);
1765                         return (ENOMEM);
1766                 }
1767                 *--bp = '/';
1768         }
1769         numfullpathfound++;
1770         *retbuf = bp;
1771         *freebuf = buf;
1772         return (0);
1773 }
1774