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