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