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