sys/kern/vfs_cache.c

   1 /*
   2  * Copyright (c) 1989, 1993, 1995
   3  *      The Regents of the University of California.  All rights reserved.
   4  * Copyright (c) 2003 Matthew Dillon <dillon@backplane.com>,
   5  *      All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Poul-Henning Kamp of the FreeBSD Project.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. All advertising materials mentioning features or use of this software
  19  *    must display the following acknowledgement:
  20  *      This product includes software developed by the University of
  21  *      California, Berkeley and its contributors.
  22  * 4. Neither the name of the University nor the names of its contributors
  23  *    may be used to endorse or promote products derived from this software
  24  *    without specific prior written permission.
  25  *
  26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36  * SUCH DAMAGE.
  37  *
  38  *      @(#)vfs_cache.c 8.5 (Berkeley) 3/22/95
  39  * $FreeBSD: src/sys/kern/vfs_cache.c,v 1.42.2.6 2001/10/05 20:07:03 dillon Exp $
  40  * $DragonFly: src/sys/kern/vfs_cache.c,v 1.15 2004/04/08 17:56:48 dillon Exp $
  41  */
  42
  43 #include <sys/param.h>
  44 #include <sys/systm.h>
  45 #include <sys/kernel.h>
  46 #include <sys/sysctl.h>
  47 #include <sys/mount.h>
  48 #include <sys/vnode.h>
  49 #include <sys/malloc.h>
  50 #include <sys/sysproto.h>
  51 #include <sys/proc.h>
  52 #include <sys/namei.h>
  53 #include <sys/filedesc.h>
  54 #include <sys/fnv_hash.h>
  55 #include <sys/globaldata.h>
  56
  57 /*
  58  * Random lookups in the cache are accomplished with a hash table using
  59  * a hash key of (nc_src_vp, name).
  60  *
  61  * Negative entries may exist and correspond to structures where nc_vp
  62  * is NULL.  In a negative entry, NCF_WHITEOUT will be set if the entry
  63  * corresponds to a whited-out directory entry (verses simply not finding the
  64  * entry at all).
  65  *
  66  * Upon reaching the last segment of a path, if the reference is for DELETE,
  67  * or NOCACHE is set (rewrite), and the name is located in the cache, it
  68  * will be dropped.
  69  */
  70
  71 /*
  72  * Structures associated with name cacheing.
  73  */
  74 #define NCHHASH(hash)   (&nchashtbl[(hash) & nchash])
  75 #define MINNEG          1024
  76
  77 MALLOC_DEFINE(M_VFSCACHE, "vfscache", "VFS name cache entries");
  78
  79 static LIST_HEAD(nchashhead, namecache) *nchashtbl;     /* Hash Table */
  80 static struct namecache_list    ncneglist;              /* instead of vnode */
  81 static struct namecache         rootnamecache;          /* Dummy node */
  82
  83 static int      nczapcheck;             /* panic on bad release */
  84 SYSCTL_INT(_debug, OID_AUTO, nczapcheck, CTLFLAG_RW, &nczapcheck, 0, "");
  85
  86 static u_long   nchash;                 /* size of hash table */
  87 SYSCTL_ULONG(_debug, OID_AUTO, nchash, CTLFLAG_RD, &nchash, 0, "");
  88
  89 static u_long   ncnegfactor = 16;       /* ratio of negative entries */
  90 SYSCTL_ULONG(_debug, OID_AUTO, ncnegfactor, CTLFLAG_RW, &ncnegfactor, 0, "");
  91
  92 static u_long   numneg;         /* number of cache entries allocated */
  93 SYSCTL_ULONG(_debug, OID_AUTO, numneg, CTLFLAG_RD, &numneg, 0, "");
  94
  95 static u_long   numcache;               /* number of cache entries allocated */
  96 SYSCTL_ULONG(_debug, OID_AUTO, numcache, CTLFLAG_RD, &numcache, 0, "");
  97
  98 static u_long   numunres;               /* number of unresolved entries */
  99 SYSCTL_ULONG(_debug, OID_AUTO, numunres, CTLFLAG_RD, &numunres, 0, "");
 100
 101 SYSCTL_INT(_debug, OID_AUTO, vnsize, CTLFLAG_RD, 0, sizeof(struct vnode), "");
 102 SYSCTL_INT(_debug, OID_AUTO, ncsize, CTLFLAG_RD, 0, sizeof(struct namecache), "");
 103
 104 /*
 105  * The new name cache statistics
 106  */
 107 SYSCTL_NODE(_vfs, OID_AUTO, cache, CTLFLAG_RW, 0, "Name cache statistics");
 108 #define STATNODE(mode, name, var) \
 109         SYSCTL_ULONG(_vfs_cache, OID_AUTO, name, mode, var, 0, "");
 110 STATNODE(CTLFLAG_RD, numneg, &numneg);
 111 STATNODE(CTLFLAG_RD, numcache, &numcache);
 112 static u_long numcalls; STATNODE(CTLFLAG_RD, numcalls, &numcalls);
 113 static u_long dothits; STATNODE(CTLFLAG_RD, dothits, &dothits);
 114 static u_long dotdothits; STATNODE(CTLFLAG_RD, dotdothits, &dotdothits);
 115 static u_long numchecks; STATNODE(CTLFLAG_RD, numchecks, &numchecks);
 116 static u_long nummiss; STATNODE(CTLFLAG_RD, nummiss, &nummiss);
 117 static u_long nummisszap; STATNODE(CTLFLAG_RD, nummisszap, &nummisszap);
 118 static u_long numposzaps; STATNODE(CTLFLAG_RD, numposzaps, &numposzaps);
 119 static u_long numposhits; STATNODE(CTLFLAG_RD, numposhits, &numposhits);
 120 static u_long numnegzaps; STATNODE(CTLFLAG_RD, numnegzaps, &numnegzaps);
 121 static u_long numneghits; STATNODE(CTLFLAG_RD, numneghits, &numneghits);
 122
 123 struct nchstats nchstats[SMP_MAXCPU];
 124 /*
 125  * Export VFS cache effectiveness statistics to user-land.
 126  *
 127  * The statistics are left for aggregation to user-land so
 128  * neat things can be achieved, like observing per-CPU cache
 129  * distribution.
 130  */
 131 static int
 132 nchstats_agg(SYSCTL_HANDLER_ARGS)
 133 {
 134         struct globaldata *gd;
 135         int i, error;
 136
 137         error = 0;
 138         for (i = 0; i < ncpus; ++i) {
 139                 gd = globaldata_find(i);
 140                 if ((error = SYSCTL_OUT(req, (void *)&(*gd->gd_nchstats),
 141                         sizeof(struct nchstats))))
 142                         break;
 143         }
 144
 145         return (error);
 146 }
 147 SYSCTL_PROC(_vfs_cache, OID_AUTO, nchstats, CTLTYPE_OPAQUE|CTLFLAG_RD,
 148   0, 0, nchstats_agg, "S,nchstats", "VFS cache effectiveness statistics");
 149
 150 static void cache_zap(struct namecache *ncp);
 151
 152 /*
 153  * cache_hold() and cache_drop() prevent the premature deletion of a
 154  * namecache entry but do not prevent operations (such as zapping) on
 155  * that namecache entry.
 156  */
 157 static __inline
 158 struct namecache *
 159 _cache_hold(struct namecache *ncp)
 160 {
 161         ++ncp->nc_refs;
 162         return(ncp);
 163 }
 164
 165 static __inline
 166 void
 167 _cache_drop(struct namecache *ncp)
 168 {
 169         KKASSERT(ncp->nc_refs > 0);
 170         if (ncp->nc_refs == 1 &&
 171             (ncp->nc_flag & NCF_UNRESOLVED) &&
 172             TAILQ_EMPTY(&ncp->nc_list)
 173         ) {
 174                 cache_zap(ncp);
 175         } else {
 176                 --ncp->nc_refs;
 177         }
 178 }
 179
 180 struct namecache *
 181 cache_hold(struct namecache *ncp)
 182 {
 183         return(_cache_hold(ncp));
 184 }
 185
 186 void
 187 cache_drop(struct namecache *ncp)
 188 {
 189         _cache_drop(ncp);
 190 }
 191
 192 static void
 193 cache_link_parent(struct namecache *ncp, struct namecache *par)
 194 {
 195         KKASSERT(ncp->nc_parent == NULL);
 196         ncp->nc_parent = par;
 197         if (TAILQ_EMPTY(&par->nc_list)) {
 198                 if (par->nc_vp)
 199                         vhold(par->nc_vp);
 200         }
 201         TAILQ_INSERT_HEAD(&par->nc_list, ncp, nc_entry);
 202 }
 203
 204 static void
 205 cache_unlink_parent(struct namecache *ncp)
 206 {
 207         struct namecache *par;
 208
 209         if ((par = ncp->nc_parent) != NULL) {
 210                 ncp->nc_parent = NULL;
 211                 par = cache_hold(par);
 212                 TAILQ_REMOVE(&par->nc_list, ncp, nc_entry);
 213                 if (par->nc_vp && TAILQ_EMPTY(&par->nc_list))
 214                         vdrop(par->nc_vp);
 215                 cache_drop(par);
 216         }
 217 }
 218
 219 static struct namecache *
 220 cache_alloc(struct vnode *vp)
 221 {
 222         struct namecache *ncp;
 223
 224         ncp = malloc(sizeof(*ncp), M_VFSCACHE, M_WAITOK|M_ZERO);
 225         TAILQ_INIT(&ncp->nc_list);
 226         ncp->nc_vp = vp;
 227         if (vp != NULL) {
 228                 TAILQ_INSERT_HEAD(&vp->v_namecache, ncp, nc_vnode);
 229                 ++numcache;
 230         } else {
 231                 TAILQ_INSERT_HEAD(&ncneglist, ncp, nc_vnode);
 232                 ++numneg;
 233         }
 234         return(ncp);
 235 }
 236
 237 /*
 238  * Try to destroy a namecache entry.  The entry is disassociated from its
 239  * vnode or ncneglist and reverted to an UNRESOLVED state.
 240  *
 241  * Then, if there are no additional references to the ncp and we can
 242  * successfully delete the children, the entry is also removed from the
 243  * namecache hashlist / topology.
 244  *
 245  * References or undeletable children will prevent the entry from being
 246  * removed from the topology.  The entry may be revalidated (typically
 247  * by cache_enter()) at a later time.  Children remain because:
 248  *
 249  *      + we have tried to delete a node rather then a leaf in the topology.
 250  *      + the presence of negative entries (we try to scrap these).
 251  *      + an entry or child has a non-zero ref count and cannot be scrapped.
 252  *
 253  * This function must be called with the ncp held and will drop the ref
 254  * count during zapping.
 255  */
 256 static void
 257 cache_zap(struct namecache *ncp)
 258 {
 259         struct namecache *par;
 260         struct vnode *vp;
 261
 262         /*
 263          * Disassociate the vnode or negative cache ref and set NCF_UNRESOLVED.
 264          */
 265         if ((ncp->nc_flag & NCF_UNRESOLVED) == 0) {
 266                 ncp->nc_flag |= NCF_UNRESOLVED;
 267                 ++numunres;
 268                 if ((vp = ncp->nc_vp) != NULL) {
 269                         --numcache;
 270                         ncp->nc_vp = NULL;      /* safety */
 271                         TAILQ_REMOVE(&vp->v_namecache, ncp, nc_vnode);
 272                         if (!TAILQ_EMPTY(&ncp->nc_list))
 273                                 vdrop(vp);
 274                 } else {
 275                         TAILQ_REMOVE(&ncneglist, ncp, nc_vnode);
 276                         --numneg;
 277                 }
 278         }
 279
 280         /*
 281          * Try to scrap the entry and possibly tail-recurse on its parent.
 282          * We only scrap unref'd (other then our ref) unresolved entries,
 283          * we do not scrap 'live' entries.
 284          */
 285         while (ncp->nc_flag & NCF_UNRESOLVED) {
 286                 /*
 287                  * Someone other then us has a ref, stop.
 288                  */
 289                 if (ncp->nc_refs > 1)
 290                         goto done;
 291
 292                 /*
 293                  * We have children, stop.
 294                  */
 295                 if (!TAILQ_EMPTY(&ncp->nc_list))
 296                         goto done;
 297
 298                 /*
 299                  * Ok, we can completely destroy and free this entry.  Sanity
 300                  * check it against our static rootnamecache structure,
 301                  * then remove it from the hash.
 302                  */
 303                 KKASSERT(ncp != &rootnamecache);
 304
 305                 if (ncp->nc_flag & NCF_HASHED) {
 306                         ncp->nc_flag &= ~NCF_HASHED;
 307                         LIST_REMOVE(ncp, nc_hash);
 308                 }
 309
 310                 /*
 311                  * Unlink from its parent and free, then loop on the
 312                  * parent.  XXX temp hack, in stage-3 parent is never NULL
 313                  */
 314                 if ((par = ncp->nc_parent) != NULL) {
 315                         par = cache_hold(par);
 316                         TAILQ_REMOVE(&par->nc_list, ncp, nc_entry);
 317                         if (par->nc_vp && TAILQ_EMPTY(&par->nc_list))
 318                                 vdrop(par->nc_vp);
 319                 }
 320                 --numunres;
 321                 ncp->nc_refs = -1;      /* safety */
 322                 ncp->nc_parent = NULL;  /* safety */
 323                 if (ncp->nc_name)
 324                         free(ncp->nc_name, M_VFSCACHE);
 325                 free(ncp, M_VFSCACHE);
 326                 ncp = par;
 327                 if (par == NULL)        /* temp hack */
 328                         return;         /* temp hack */
 329         }
 330 done:
 331         --ncp->nc_refs;
 332 }
 333
 334 /*
 335  * Lookup an entry in the cache
 336  *
 337  * Lookup is called with dvp pointing to the directory to search,
 338  * cnp pointing to the name of the entry being sought.
 339  *
 340  * If the lookup succeeds, the vnode is returned in *vpp, and a
 341  * status of -1 is returned.
 342  *
 343  * If the lookup determines that the name does not exist (negative cacheing),
 344  * a status of ENOENT is returned.
 345  *
 346  * If the lookup fails, a status of zero is returned.
 347  *
 348  * Note that UNRESOLVED entries are ignored.  They are not negative cache
 349  * entries.
 350  */
 351 int
 352 cache_lookup(struct vnode *dvp, struct namecache *par, struct vnode **vpp,
 353                 struct namecache **ncpp, struct componentname *cnp)
 354 {
 355         struct namecache *ncp;
 356         u_int32_t hash;
 357         globaldata_t gd = mycpu;
 358
 359         numcalls++;
 360
 361         /*
 362          * Obtain the namecache entry associated with dvp, creating one if
 363          * necessary.  If we have to create one we have insufficient
 364          * information to hash it or even supply the name, but we still
 365          * need one so we can link it in.
 366          *
 367          * NOTE: in this stage of development, the passed 'par' is
 368          * almost always NULL.
 369          */
 370         if (par == NULL) {
 371                 if ((par = TAILQ_FIRST(&dvp->v_namecache)) == NULL)
 372                         par = cache_alloc(dvp);
 373         }
 374
 375         /*
 376          * Deal with "." and "..".  In this stage of code development we leave
 377          * the returned ncpp NULL.  Note that if the namecache is disjoint,
 378          * we won't find a vnode for "..".
 379          */
 380         if (cnp->cn_nameptr[0] == '.') {
 381                 if (cnp->cn_namelen == 1) {
 382                         *vpp = dvp;
 383                         dothits++;
 384                         numposhits++;   /* include in total statistics */
 385                         return (-1);
 386                 }
 387                 if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.') {
 388                         dotdothits++;
 389                         numposhits++;   /* include in total statistics */
 390                         if ((cnp->cn_flags & CNP_MAKEENTRY) == 0)
 391                                 return (0);
 392                         if (par->nc_parent == NULL ||
 393                             par->nc_parent->nc_vp == NULL) {
 394                                 return (0);
 395                         }
 396                         *vpp = par->nc_parent->nc_vp;
 397                         return (-1);
 398                 }
 399         }
 400
 401         /*
 402          * Try to locate an existing entry
 403          */
 404         hash = fnv_32_buf(cnp->cn_nameptr, cnp->cn_namelen, FNV1_32_INIT);
 405         hash = fnv_32_buf(&par, sizeof(par), hash);
 406         if (nczapcheck)
 407             printf("DVP %p/%p %08x %*.*s\n", dvp, par, hash, cnp->cn_namelen, cnp->cn_namelen, cnp->cn_nameptr);
 408         LIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
 409                 numchecks++;
 410                 if (nczapcheck) {
 411                     printf("TEST ncp par=%p %*.*s\n",
 412                         ncp->nc_parent, ncp->nc_nlen, ncp->nc_nlen,
 413                         ncp->nc_name);
 414                 }
 415                 if ((ncp->nc_flag & NCF_UNRESOLVED) == 0 &&
 416                     ncp->nc_parent == par &&
 417                     ncp->nc_nlen == cnp->cn_namelen &&
 418                     bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen) == 0
 419                 ) {
 420                         if (nczapcheck)
 421                             printf("GOOD\n");
 422                         cache_hold(ncp);
 423                         break;
 424                 }
 425         }
 426
 427         /*
 428          * If we failed to locate an entry, return 0 (indicates failure).
 429          */
 430         if (ncp == NULL) {
 431                 if ((cnp->cn_flags & CNP_MAKEENTRY) == 0) {
 432                         nummisszap++;
 433                 } else {
 434                         nummiss++;
 435                 }
 436                 gd->gd_nchstats->ncs_miss++;
 437                 return (0);
 438         }
 439
 440         /*
 441          * If we found an entry, but we don't want to have one, we zap it.
 442          */
 443         if ((cnp->cn_flags & CNP_MAKEENTRY) == 0) {
 444                 numposzaps++;
 445                 gd->gd_nchstats->ncs_badhits++;
 446                 cache_zap(ncp);
 447                 return (0);
 448         }
 449
 450         /*
 451          * If the vnode is not NULL then return the positive match.
 452          */
 453         if (ncp->nc_vp) {
 454                 numposhits++;
 455                 gd->gd_nchstats->ncs_goodhits++;
 456                 *vpp = ncp->nc_vp;
 457                 cache_drop(ncp);
 458                 return (-1);
 459         }
 460
 461         /*
 462          * If the vnode is NULL we found a negative match.  If we want to
 463          * create it, purge the negative match and return failure (as if
 464          * we hadn't found a match in the first place).
 465          */
 466         if (cnp->cn_nameiop == NAMEI_CREATE) {
 467                 numnegzaps++;
 468                 gd->gd_nchstats->ncs_badhits++;
 469                 cache_zap(ncp);
 470                 return (0);
 471         }
 472
 473         numneghits++;
 474
 475         /*
 476          * We found a "negative" match, ENOENT notifies client of this match.
 477          * The nc_flag field records whether this is a whiteout.  Since there
 478          * is no vnode we can use the vnode tailq link field with ncneglist.
 479          */
 480         TAILQ_REMOVE(&ncneglist, ncp, nc_vnode);
 481         TAILQ_INSERT_TAIL(&ncneglist, ncp, nc_vnode);
 482         gd->gd_nchstats->ncs_neghits++;
 483         if (ncp->nc_flag & NCF_WHITEOUT)
 484                 cnp->cn_flags |= CNP_ISWHITEOUT;
 485         cache_drop(ncp);
 486         return (ENOENT);
 487 }
 488
 489 /*
 490  * Generate a special linkage between the mount point and the root of the
 491  * mounted filesystem in order to maintain the namecache topology across
 492  * a mount point.  The special linkage has a 0-length name component
 493  * and sets NCF_MOUNTPT.
 494  */
 495 void
 496 cache_mount(struct vnode *dvp, struct vnode *tvp)
 497 {
 498         struct namecache *ncp;
 499         struct namecache *par;
 500         struct nchashhead *nchpp;
 501         u_int32_t hash;
 502
 503         /*
 504          * If a linkage already exists we do not have to do anything.
 505          */
 506         hash = fnv_32_buf("", 0, FNV1_32_INIT);
 507         hash = fnv_32_buf(&dvp->v_id, sizeof(dvp->v_id), hash);
 508         LIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
 509                 numchecks++;
 510                 if (ncp->nc_vp == tvp &&
 511                     ncp->nc_nlen == 0 &&
 512                     ncp->nc_parent &&
 513                     ncp->nc_parent->nc_vp == dvp
 514                 ) {
 515                         return;
 516                 }
 517         }
 518
 519         if ((par = TAILQ_FIRST(&dvp->v_namecache)) == NULL)
 520                 par = cache_alloc(dvp);
 521
 522         /*
 523          * Otherwise create a new linkage.
 524          */
 525         ncp = cache_alloc(tvp);
 526         ncp->nc_flag = NCF_MOUNTPT;
 527         cache_link_parent(ncp, par);
 528
 529         /*
 530          * Hash table
 531          */
 532         hash = fnv_32_buf("", 0, FNV1_32_INIT);
 533         hash = fnv_32_buf(&dvp->v_id, sizeof(dvp->v_id), hash);
 534         nchpp = NCHHASH(hash);
 535         LIST_INSERT_HEAD(nchpp, ncp, nc_hash);
 536
 537         ncp->nc_flag |= NCF_HASHED;
 538 }
 539
 540 /*
 541  * Add an entry to the cache.
 542  */
 543 void
 544 cache_enter(struct vnode *dvp, struct namecache *par, struct vnode *vp, struct componentname *cnp)
 545 {
 546         struct namecache *ncp;
 547         struct namecache *bpar;
 548         struct nchashhead *nchpp;
 549         u_int32_t hash;
 550         char *name;
 551
 552         /*
 553          * If the directory has no namecache entry we must associate one with
 554          * it.  The name of the entry is not known so it isn't hashed.
 555          */
 556         if (par == NULL) {
 557                 if ((par = TAILQ_FIRST(&dvp->v_namecache)) == NULL)
 558                         par = cache_alloc(dvp);
 559         }
 560
 561         /*
 562          * This may be a bit confusing.  "." and ".." are 'virtual' entries.
 563          * We do not actually create a namecache entry representing either.
 564          * However, the ".." case is used to linkup a potentially disjoint
 565          * directory with its parent, to disconnect a directory from its
 566          * parent, or to change an existing linkage that may no longer be
 567          * correct (as might occur when a subdirectory is renamed).
 568          */
 569
 570         if (cnp->cn_namelen == 1 && cnp->cn_nameptr[0] == '.')
 571                 return;
 572         if (cnp->cn_namelen == 2 && cnp->cn_nameptr[0] == '.' &&
 573             cnp->cn_nameptr[1] == '.'
 574         ) {
 575                 if (vp == NULL) {
 576                         if (par->nc_parent)
 577                                 cache_unlink_parent(par);
 578                 } else {
 579                         if ((ncp = TAILQ_FIRST(&vp->v_namecache)) == NULL)
 580                                 ncp = cache_alloc(vp);
 581                         cache_hold(par);
 582                         if (par->nc_parent)
 583                                 cache_unlink_parent(par);
 584                         cache_link_parent(par, ncp); /* ncp is parent of par */
 585                         cache_drop(par);
 586                 }
 587                 return;
 588         }
 589
 590         /*
 591          * Locate other entries associated with this vnode and zap them,
 592          * because the purge code may not be able to find them due to
 593          * the topology not yet being consistent.  This is a temporary
 594          * hack.
 595          */
 596         if (vp) {
 597 again:
 598                 TAILQ_FOREACH(ncp, &vp->v_namecache, nc_vnode) {
 599                         if ((ncp->nc_flag & NCF_UNRESOLVED) == 0) {
 600                                 cache_zap(cache_hold(ncp));
 601                                 goto again;
 602                         }
 603                 }
 604         }
 605
 606         hash = fnv_32_buf(cnp->cn_nameptr, cnp->cn_namelen, FNV1_32_INIT);
 607         bpar = par;
 608         hash = fnv_32_buf(&bpar, sizeof(bpar), hash);
 609
 610         if (nczapcheck)
 611             printf("ENTER %p/%p %08x '%*.*s' %p ", dvp, par, hash, (int)cnp->cn_namelen, (int)cnp->cn_namelen, cnp->cn_nameptr, vp);
 612
 613
 614         name = malloc(cnp->cn_namelen, M_VFSCACHE, M_WAITOK);
 615         ncp = cache_alloc(vp);
 616         if (nczapcheck)
 617             printf("alloc\n");
 618
 619         /*
 620          * Linkup the parent pointer, bump the parent vnode's hold
 621          * count when we go from 0->1 children.
 622          */
 623         cache_link_parent(ncp, par);
 624
 625         /*
 626          * Add to the hash table
 627          */
 628         ncp->nc_name = name;
 629         ncp->nc_nlen = cnp->cn_namelen;
 630         bcopy(cnp->cn_nameptr, ncp->nc_name, cnp->cn_namelen);
 631         nchpp = NCHHASH(hash);
 632         LIST_INSERT_HEAD(nchpp, ncp, nc_hash);
 633         ncp->nc_flag |= NCF_HASHED;
 634
 635         /*
 636          * If the target vnode is NULL if this is to be a negative cache
 637          * entry.
 638          */
 639         if (vp == NULL) {
 640                 ncp->nc_flag &= ~NCF_WHITEOUT;
 641                 if (cnp->cn_flags & CNP_ISWHITEOUT)
 642                         ncp->nc_flag |= NCF_WHITEOUT;
 643         }
 644
 645         /*
 646          * Don't cache too many negative hits
 647          */
 648         if (numneg > MINNEG && numneg * ncnegfactor > numcache) {
 649                 ncp = TAILQ_FIRST(&ncneglist);
 650                 KKASSERT(ncp != NULL);
 651                 cache_zap(cache_hold(ncp));
 652         }
 653 }
 654
 655 /*
 656  * Name cache initialization, from vfsinit() when we are booting
 657  *
 658  * rootnamecache is initialized such that it cannot be recursively deleted.
 659  */
 660 void
 661 nchinit(void)
 662 {
 663         int i;
 664         globaldata_t gd;
 665
 666         /* initialise per-cpu namecache effectiveness statistics. */
 667         for (i = 0; i < ncpus; ++i) {
 668                 gd = globaldata_find(i);
 669                 gd->gd_nchstats = &nchstats[i];
 670         }
 671
 672         TAILQ_INIT(&ncneglist);
 673         nchashtbl = hashinit(desiredvnodes*2, M_VFSCACHE, &nchash);
 674         TAILQ_INIT(&rootnamecache.nc_list);
 675         rootnamecache.nc_flag |= NCF_HASHED | NCF_ROOT | NCF_UNRESOLVED;
 676         rootnamecache.nc_refs = 1;
 677 }
 678
 679 /*
 680  * vfs_cache_setroot()
 681  *
 682  *      Create an association between the root of our namecache and
 683  *      the root vnode.  This routine may be called several times during
 684  *      booting.
 685  */
 686 void
 687 vfs_cache_setroot(struct vnode *nvp)
 688 {
 689         KKASSERT(rootnamecache.nc_refs > 0);    /* don't accidently free */
 690         cache_zap(cache_hold(&rootnamecache));
 691
 692         rootnamecache.nc_vp = nvp;
 693         rootnamecache.nc_flag &= ~NCF_UNRESOLVED;
 694         if (nvp) {
 695                 ++numcache;
 696                 if (!TAILQ_EMPTY(&rootnamecache.nc_list))
 697                         vhold(nvp);
 698                 TAILQ_INSERT_HEAD(&nvp->v_namecache, &rootnamecache, nc_vnode);
 699         } else {
 700                 ++numneg;
 701                 TAILQ_INSERT_HEAD(&ncneglist, &rootnamecache, nc_vnode);
 702                 rootnamecache.nc_flag &= ~NCF_WHITEOUT;
 703         }
 704 }
 705
 706 /*
 707  * Invalidate all namecache entries to a particular vnode as well as
 708  * any direct children of that vnode in the namecache.  This is a
 709  * 'catch all' purge used by filesystems that do not know any better.
 710  *
 711  * A new vnode v_id is generated.  Note that no vnode will ever have a
 712  * v_id of 0.
 713  *
 714  * Note that the linkage between the vnode and its namecache entries will
 715  * be removed, but the namecache entries themselves might stay put due to
 716  * active references from elsewhere in the system or due to the existance of
 717  * the children.   The namecache topology is left intact even if we do not
 718  * know what the vnode association is.  Such entries will be marked
 719  * NCF_UNRESOLVED.
 720  *
 721  * XXX: Only time and the size of v_id prevents this from failing:
 722  * XXX: In theory we should hunt down all (struct vnode*, v_id)
 723  * XXX: soft references and nuke them, at least on the global
 724  * XXX: v_id wraparound.  The period of resistance can be extended
 725  * XXX: by incrementing each vnodes v_id individually instead of
 726  * XXX: using the global v_id.
 727  */
 728 void
 729 cache_purge(struct vnode *vp)
 730 {
 731         static u_long nextid;
 732         struct namecache *ncp;
 733         struct namecache *scan;
 734
 735         /*
 736          * Disassociate the vnode from its namecache entries along with
 737          * (for historical reasons) any direct children.
 738          */
 739         while ((ncp = TAILQ_FIRST(&vp->v_namecache)) != NULL) {
 740                 cache_hold(ncp);
 741
 742 restart: /* YYY hack, fix me */
 743                 TAILQ_FOREACH(scan, &ncp->nc_list, nc_entry) {
 744                         if ((scan->nc_flag & NCF_UNRESOLVED) == 0) {
 745                                 cache_zap(cache_hold(scan));
 746                                 goto restart;
 747                         }
 748                 }
 749                 cache_zap(ncp);
 750         }
 751
 752         /*
 753          * Calculate a new unique id for ".." handling
 754          */
 755         do {
 756                 nextid++;
 757         } while (nextid == vp->v_id || nextid == 0);
 758         vp->v_id = nextid;
 759 }
 760
 761 /*
 762  * Flush all entries referencing a particular filesystem.
 763  *
 764  * Since we need to check it anyway, we will flush all the invalid
 765  * entries at the same time.
 766  */
 767 void
 768 cache_purgevfs(struct mount *mp)
 769 {
 770         struct nchashhead *nchpp;
 771         struct namecache *ncp, *nnp;
 772
 773         /*
 774          * Scan hash tables for applicable entries.
 775          */
 776         for (nchpp = &nchashtbl[nchash]; nchpp >= nchashtbl; nchpp--) {
 777                 ncp = LIST_FIRST(nchpp);
 778                 if (ncp)
 779                         cache_hold(ncp);
 780                 while (ncp) {
 781                         nnp = LIST_NEXT(ncp, nc_hash);
 782                         if (nnp)
 783                                 cache_hold(nnp);
 784                         if (ncp->nc_vp && ncp->nc_vp->v_mount == mp)
 785                                 cache_zap(ncp);
 786                         else
 787                                 cache_drop(ncp);
 788                         ncp = nnp;
 789                 }
 790         }
 791 }
 792
 793 /*
 794  * cache_leaf_test()
 795  *
 796  *      Test whether the vnode is at a leaf in the nameicache tree.
 797  *
 798  *      Returns 0 if it is a leaf, -1 if it isn't.
 799  */
 800 int
 801 cache_leaf_test(struct vnode *vp)
 802 {
 803         struct namecache *scan;
 804         struct namecache *ncp;
 805
 806         TAILQ_FOREACH(scan, &vp->v_namecache, nc_vnode) {
 807                 TAILQ_FOREACH(ncp, &scan->nc_list, nc_entry) {
 808                         /* YYY && ncp->nc_vp->v_type == VDIR ? */
 809                         if (ncp->nc_vp != NULL)
 810                                 return(-1);
 811                 }
 812         }
 813         return(0);
 814 }
 815
 816 /*
 817  * Perform canonical checks and cache lookup and pass on to filesystem
 818  * through the vop_cachedlookup only if needed.
 819  *
 820  * vop_lookup_args {
 821  *      struct vnode a_dvp;
 822  *      struct namecache *a_ncp;
 823  *      struct vnode **a_vpp;
 824  *      struct namecache **a_ncpp;
 825  *      struct componentname *a_cnp;
 826  * }
 827  */
 828 int
 829 vfs_cache_lookup(struct vop_lookup_args *ap)
 830 {
 831         struct vnode *dvp, *vp;
 832         int lockparent;
 833         int error;
 834         struct namecache *par = ap->a_par;
 835         struct vnode **vpp = ap->a_vpp;
 836         struct namecache **ncpp = ap->a_ncpp;
 837         struct componentname *cnp = ap->a_cnp;
 838         struct ucred *cred = cnp->cn_cred;
 839         int flags = cnp->cn_flags;
 840         struct thread *td = cnp->cn_td;
 841         u_long vpid;    /* capability number of vnode */
 842
 843         *vpp = NULL;
 844         if (ncpp)
 845                 *ncpp = NULL;
 846         dvp = ap->a_dvp;
 847         lockparent = flags & CNP_LOCKPARENT;
 848
 849         if (dvp->v_type != VDIR)
 850                 return (ENOTDIR);
 851
 852         if ((flags & CNP_ISLASTCN) && (dvp->v_mount->mnt_flag & MNT_RDONLY) &&
 853             (cnp->cn_nameiop == NAMEI_DELETE || cnp->cn_nameiop == NAMEI_RENAME)) {
 854                 return (EROFS);
 855         }
 856
 857         error = VOP_ACCESS(dvp, VEXEC, cred, td);
 858
 859         if (error)
 860                 return (error);
 861
 862         error = cache_lookup(dvp, par, vpp, ncpp, cnp);
 863
 864         if (!error)
 865                 return (VOP_CACHEDLOOKUP(dvp, par, vpp, ncpp, cnp));
 866
 867         if (error == ENOENT)
 868                 return (error);
 869
 870         vp = *vpp;
 871         vpid = vp->v_id;
 872         cnp->cn_flags &= ~CNP_PDIRUNLOCK;
 873         if (dvp == vp) {   /* lookup on "." */
 874                 VREF(vp);
 875                 error = 0;
 876         } else if (flags & CNP_ISDOTDOT) {
 877                 VOP_UNLOCK(dvp, NULL, 0, td);
 878                 cnp->cn_flags |= CNP_PDIRUNLOCK;
 879                 error = vget(vp, NULL, LK_EXCLUSIVE, td);
 880                 if (!error && lockparent && (flags & CNP_ISLASTCN)) {
 881                         if ((error = vn_lock(dvp, NULL, LK_EXCLUSIVE, td)) == 0)
 882                                 cnp->cn_flags &= ~CNP_PDIRUNLOCK;
 883                 }
 884         } else {
 885                 error = vget(vp, NULL, LK_EXCLUSIVE, td);
 886                 if (!lockparent || error || !(flags & CNP_ISLASTCN)) {
 887                         VOP_UNLOCK(dvp, NULL, 0, td);
 888                         cnp->cn_flags |= CNP_PDIRUNLOCK;
 889                 }
 890         }
 891         /*
 892          * Check that the capability number did not change
 893          * while we were waiting for the lock.
 894          */
 895         if (!error) {
 896                 if (vpid == vp->v_id)
 897                         return (0);
 898                 vput(vp);
 899                 if (lockparent && dvp != vp && (flags & CNP_ISLASTCN)) {
 900                         VOP_UNLOCK(dvp, NULL, 0, td);
 901                         cnp->cn_flags |= CNP_PDIRUNLOCK;
 902                 }
 903         }
 904         if (cnp->cn_flags & CNP_PDIRUNLOCK) {
 905                 error = vn_lock(dvp, NULL, LK_EXCLUSIVE, td);
 906                 if (error)
 907                         return (error);
 908                 cnp->cn_flags &= ~CNP_PDIRUNLOCK;
 909         }
 910         return (VOP_CACHEDLOOKUP(dvp, par, vpp, ncpp, cnp));
 911 }
 912
 913 static int disablecwd;
 914 SYSCTL_INT(_debug, OID_AUTO, disablecwd, CTLFLAG_RW, &disablecwd, 0, "");
 915
 916 static u_long numcwdcalls; STATNODE(CTLFLAG_RD, numcwdcalls, &numcwdcalls);
 917 static u_long numcwdfail1; STATNODE(CTLFLAG_RD, numcwdfail1, &numcwdfail1);
 918 static u_long numcwdfail2; STATNODE(CTLFLAG_RD, numcwdfail2, &numcwdfail2);
 919 static u_long numcwdfail3; STATNODE(CTLFLAG_RD, numcwdfail3, &numcwdfail3);
 920 static u_long numcwdfail4; STATNODE(CTLFLAG_RD, numcwdfail4, &numcwdfail4);
 921 static u_long numcwdfound; STATNODE(CTLFLAG_RD, numcwdfound, &numcwdfound);
 922
 923 int
 924 __getcwd(struct __getcwd_args *uap)
 925 {
 926         struct proc *p = curproc;
 927         char *bp, *buf;
 928         int error, i, slash_prefixed;
 929         struct filedesc *fdp;
 930         struct namecache *ncp;
 931         struct vnode *vp;
 932
 933         numcwdcalls++;
 934         if (disablecwd)
 935                 return (ENODEV);
 936         if (uap->buflen < 2)
 937                 return (EINVAL);
 938         if (uap->buflen > MAXPATHLEN)
 939                 uap->buflen = MAXPATHLEN;
 940         buf = bp = malloc(uap->buflen, M_TEMP, M_WAITOK);
 941         bp += uap->buflen - 1;
 942         *bp = '\0';
 943         fdp = p->p_fd;
 944         slash_prefixed = 0;
 945         for (vp = fdp->fd_cdir; vp != fdp->fd_rdir && vp != rootvnode;) {
 946                 if (vp->v_flag & VROOT) {
 947                         if (vp->v_mount == NULL) {      /* forced unmount */
 948                                 free(buf, M_TEMP);
 949                                 return (EBADF);
 950                         }
 951                         vp = vp->v_mount->mnt_vnodecovered;
 952                         continue;
 953                 }
 954                 TAILQ_FOREACH(ncp, &vp->v_namecache, nc_vnode) {
 955                         if (ncp->nc_parent && ncp->nc_parent->nc_vp &&
 956                             ncp->nc_nlen > 0) {
 957                                 break;
 958                         }
 959                 }
 960                 if (ncp == NULL) {
 961                         numcwdfail2++;
 962                         free(buf, M_TEMP);
 963                         return (ENOENT);
 964                 }
 965                 for (i = ncp->nc_nlen - 1; i >= 0; i--) {
 966                         if (bp == buf) {
 967                                 numcwdfail4++;
 968                                 free(buf, M_TEMP);
 969                                 return (ENOMEM);
 970                         }
 971                         *--bp = ncp->nc_name[i];
 972                 }
 973                 if (bp == buf) {
 974                         numcwdfail4++;
 975                         free(buf, M_TEMP);
 976                         return (ENOMEM);
 977                 }
 978                 *--bp = '/';
 979                 slash_prefixed = 1;
 980                 vp = ncp->nc_parent->nc_vp;
 981         }
 982         if (!slash_prefixed) {
 983                 if (bp == buf) {
 984                         numcwdfail4++;
 985                         free(buf, M_TEMP);
 986                         return (ENOMEM);
 987                 }
 988                 *--bp = '/';
 989         }
 990         numcwdfound++;
 991         error = copyout(bp, uap->buf, strlen(bp) + 1);
 992         free(buf, M_TEMP);
 993         return (error);
 994 }
 995
 996 /*
 997  * Thus begins the fullpath magic.
 998  */
 999
1000 #undef STATNODE
1001 #define STATNODE(name)                                                  \
1002         static u_int name;                                              \
1003         SYSCTL_UINT(_vfs_cache, OID_AUTO, name, CTLFLAG_RD, &name, 0, "")
1004
1005 static int disablefullpath;
1006 SYSCTL_INT(_debug, OID_AUTO, disablefullpath, CTLFLAG_RW,
1007     &disablefullpath, 0, "");
1008
1009 STATNODE(numfullpathcalls);
1010 STATNODE(numfullpathfail1);
1011 STATNODE(numfullpathfail2);
1012 STATNODE(numfullpathfail3);
1013 STATNODE(numfullpathfail4);
1014 STATNODE(numfullpathfound);
1015
1016 int
1017 textvp_fullpath(struct proc *p, char **retbuf, char **retfreebuf)
1018 {
1019         char *bp, *buf;
1020         int i, slash_prefixed;
1021         struct filedesc *fdp;
1022         struct namecache *ncp;
1023         struct vnode *vp, *textvp;
1024
1025         numfullpathcalls++;
1026         if (disablefullpath)
1027                 return (ENODEV);
1028         textvp = p->p_textvp;
1029         if (textvp == NULL)
1030                 return (EINVAL);
1031         buf = malloc(MAXPATHLEN, M_TEMP, M_WAITOK);
1032         bp = buf + MAXPATHLEN - 1;
1033         *bp = '\0';
1034         fdp = p->p_fd;
1035         slash_prefixed = 0;
1036         for (vp = textvp; vp != fdp->fd_rdir && vp != rootvnode;) {
1037                 if (vp->v_flag & VROOT) {
1038                         if (vp->v_mount == NULL) {      /* forced unmount */
1039                                 free(buf, M_TEMP);
1040                                 return (EBADF);
1041                         }
1042                         vp = vp->v_mount->mnt_vnodecovered;
1043                         continue;
1044                 }
1045                 TAILQ_FOREACH(ncp, &vp->v_namecache, nc_vnode) {
1046                         if (vp == textvp)
1047                                 break;
1048                         if (ncp->nc_parent && ncp->nc_parent->nc_vp &&
1049                             ncp->nc_nlen > 0) {
1050                                 break;
1051                         }
1052                 }
1053                 if (ncp == NULL) {
1054                         numfullpathfail2++;
1055                         free(buf, M_TEMP);
1056                         return (ENOENT);
1057                 }
1058                 for (i = ncp->nc_nlen - 1; i >= 0; i--) {
1059                         if (bp == buf) {
1060                                 numfullpathfail4++;
1061                                 free(buf, M_TEMP);
1062                                 return (ENOMEM);
1063                         }
1064                         *--bp = ncp->nc_name[i];
1065                 }
1066                 if (bp == buf) {
1067                         numfullpathfail4++;
1068                         free(buf, M_TEMP);
1069                         return (ENOMEM);
1070                 }
1071                 *--bp = '/';
1072                 slash_prefixed = 1;
1073                 vp = ncp->nc_parent->nc_vp;
1074         }
1075         if (!slash_prefixed) {
1076                 if (bp == buf) {
1077                         numfullpathfail4++;
1078                         free(buf, M_TEMP);
1079                         return (ENOMEM);
1080                 }
1081                 *--bp = '/';
1082         }
1083         numfullpathfound++;
1084         *retbuf = bp;
1085         *retfreebuf = buf;
1086         return (0);
1087 }
1088