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.14 2004/04/02 05:46:02 hmp 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 /*
 193  * Try to destroy a namecache entry.  The entry is disassociated from its
 194  * vnode or ncneglist and reverted to an UNRESOLVED state.
 195  *
 196  * Then, if there are no additional references to the ncp and we can
 197  * successfully delete the children, the entry is also removed from the
 198  * namecache hashlist / topology.
 199  *
 200  * References or undeletable children will prevent the entry from being
 201  * removed from the topology.  The entry may be revalidated (typically
 202  * by cache_enter()) at a later time.  Children remain because:
 203  *
 204  *      + we have tried to delete a node rather then a leaf in the topology.
 205  *      + the presence of negative entries (we try to scrap these).
 206  *      + an entry or child has a non-zero ref count and cannot be scrapped.
 207  *
 208  * This function must be called with the ncp held and will drop the ref
 209  * count during zapping.
 210  */
 211 static void
 212 cache_zap(struct namecache *ncp)
 213 {
 214         struct namecache *par;
 215         struct vnode *vp;
 216
 217         /*
 218          * Disassociate the vnode or negative cache ref and set NCF_UNRESOLVED.
 219          */
 220         if ((ncp->nc_flag & NCF_UNRESOLVED) == 0) {
 221                 ncp->nc_flag |= NCF_UNRESOLVED;
 222                 ++numunres;
 223                 if ((vp = ncp->nc_vp) != NULL) {
 224                         --numcache;
 225                         ncp->nc_vp = NULL;      /* safety */
 226                         TAILQ_REMOVE(&vp->v_namecache, ncp, nc_vnode);
 227                         if (!TAILQ_EMPTY(&ncp->nc_list))
 228                                 vdrop(vp);
 229                 } else {
 230                         TAILQ_REMOVE(&ncneglist, ncp, nc_vnode);
 231                         --numneg;
 232                 }
 233         }
 234
 235         /*
 236          * Try to scrap the entry and possibly tail-recurse on its parent.
 237          * We only scrap unref'd (other then our ref) unresolved entries,
 238          * we do not scrap 'live' entries.
 239          */
 240         while (ncp->nc_flag & NCF_UNRESOLVED) {
 241                 /*
 242                  * Someone other then us has a ref, stop.
 243                  */
 244                 if (ncp->nc_refs > 1)
 245                         goto done;
 246
 247                 /*
 248                  * We have children, stop.
 249                  */
 250                 if (!TAILQ_EMPTY(&ncp->nc_list))
 251                         goto done;
 252
 253                 /*
 254                  * Ok, we can completely destroy and free this entry.  Sanity
 255                  * check it against our static rootnamecache structure,
 256                  * then remove it from the hash.
 257                  */
 258                 KKASSERT(ncp != &rootnamecache);
 259
 260                 if (ncp->nc_flag & NCF_HASHED) {
 261                         ncp->nc_flag &= ~NCF_HASHED;
 262                         LIST_REMOVE(ncp, nc_hash);
 263                 }
 264
 265                 /*
 266                  * Unlink from its parent and free, then loop on the
 267                  * parent.  XXX temp hack, in stage-3 parent is never NULL
 268                  */
 269                 if ((par = ncp->nc_parent) != NULL) {
 270                         par = cache_hold(par);
 271                         TAILQ_REMOVE(&par->nc_list, ncp, nc_entry);
 272                         if (par->nc_vp && TAILQ_EMPTY(&par->nc_list))
 273                                 vdrop(par->nc_vp);
 274                 }
 275                 --numunres;
 276                 ncp->nc_refs = -1;      /* safety */
 277                 ncp->nc_parent = NULL;  /* safety */
 278                 if (ncp->nc_name)
 279                         free(ncp->nc_name, M_VFSCACHE);
 280                 free(ncp, M_VFSCACHE);
 281                 ncp = par;
 282                 if (par == NULL)        /* temp hack */
 283                         return;         /* temp hack */
 284         }
 285 done:
 286         --ncp->nc_refs;
 287 }
 288
 289 /*
 290  * Lookup an entry in the cache
 291  *
 292  * Lookup is called with dvp pointing to the directory to search,
 293  * cnp pointing to the name of the entry being sought.
 294  *
 295  * If the lookup succeeds, the vnode is returned in *vpp, and a
 296  * status of -1 is returned.
 297  *
 298  * If the lookup determines that the name does not exist (negative cacheing),
 299  * a status of ENOENT is returned.
 300  *
 301  * If the lookup fails, a status of zero is returned.
 302  *
 303  * Note that UNRESOLVED entries are ignored.  They are not negative cache
 304  * entries.
 305  */
 306 int
 307 cache_lookup(struct vnode *dvp, struct namecache *par, struct vnode **vpp,
 308                 struct namecache **ncpp, struct componentname *cnp)
 309 {
 310         struct namecache *ncp;
 311         u_int32_t hash;
 312         globaldata_t gd = mycpu;
 313
 314         numcalls++;
 315
 316         if (cnp->cn_nameptr[0] == '.') {
 317                 if (cnp->cn_namelen == 1) {
 318                         *vpp = dvp;
 319                         dothits++;
 320                         numposhits++;   /* include in total statistics */
 321                         return (-1);
 322                 }
 323                 if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.') {
 324                         dotdothits++;
 325                         numposhits++;   /* include in total statistics */
 326                         if (dvp->v_dd->v_id != dvp->v_ddid ||
 327                             (cnp->cn_flags & CNP_MAKEENTRY) == 0) {
 328                                 dvp->v_ddid = 0;
 329                                 return (0);
 330                         }
 331                         *vpp = dvp->v_dd;
 332                         return (-1);
 333                 }
 334         }
 335
 336         hash = fnv_32_buf(cnp->cn_nameptr, cnp->cn_namelen, FNV1_32_INIT);
 337         hash = fnv_32_buf(&dvp->v_id, sizeof(dvp->v_id), hash);
 338         LIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
 339                 numchecks++;
 340                 if ((ncp->nc_flag & NCF_UNRESOLVED) == 0 &&
 341                     /* ncp->nc_parent == par instead of dvp STAGE-3 */
 342                     ncp->nc_dvp_data == (uintptr_t)dvp && /* STAGE-2 only */
 343                     ncp->nc_dvp_id == dvp->v_id && /* STAGE-2 only */
 344                     ncp->nc_nlen == cnp->cn_namelen &&
 345                     bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen) == 0
 346                 ) {
 347                         cache_hold(ncp);
 348                         break;
 349                 }
 350         }
 351
 352         /* We failed to find an entry */
 353         if (ncp == NULL) {
 354                 if ((cnp->cn_flags & CNP_MAKEENTRY) == 0) {
 355                         nummisszap++;
 356                 } else {
 357                         nummiss++;
 358                 }
 359                 gd->gd_nchstats->ncs_miss++;
 360                 return (0);
 361         }
 362
 363         /* We don't want to have an entry, so dump it */
 364         if ((cnp->cn_flags & CNP_MAKEENTRY) == 0) {
 365                 numposzaps++;
 366                 gd->gd_nchstats->ncs_badhits++;
 367                 cache_zap(ncp);
 368                 return (0);
 369         }
 370
 371         /* We found a "positive" match, return the vnode */
 372         if (ncp->nc_vp) {
 373                 numposhits++;
 374                 gd->gd_nchstats->ncs_goodhits++;
 375                 *vpp = ncp->nc_vp;
 376                 cache_drop(ncp);
 377                 return (-1);
 378         }
 379
 380         /* We found a negative match, and want to create it, so purge */
 381         if (cnp->cn_nameiop == NAMEI_CREATE) {
 382                 numnegzaps++;
 383                 gd->gd_nchstats->ncs_badhits++;
 384                 cache_zap(ncp);
 385                 return (0);
 386         }
 387
 388         numneghits++;
 389
 390         /*
 391          * We found a "negative" match, ENOENT notifies client of this match.
 392          * The nc_flag field records whether this is a whiteout.  Since there
 393          * is no vnode we can use the vnode tailq link field with ncneglist.
 394          */
 395         TAILQ_REMOVE(&ncneglist, ncp, nc_vnode);
 396         TAILQ_INSERT_TAIL(&ncneglist, ncp, nc_vnode);
 397         gd->gd_nchstats->ncs_neghits++;
 398         if (ncp->nc_flag & NCF_WHITEOUT)
 399                 cnp->cn_flags |= CNP_ISWHITEOUT;
 400         cache_drop(ncp);
 401         return (ENOENT);
 402 }
 403
 404 /*
 405  * Generate a special linkage between the mount point and the root of the
 406  * mounted filesystem in order to maintain the namecache topology across
 407  * a mount point.  The special linkage has a 0-length name component
 408  * and sets NCF_MOUNTPT.
 409  */
 410 void
 411 cache_mount(struct vnode *dvp, struct vnode *tvp)
 412 {
 413         struct namecache *ncp;
 414         struct namecache *par;
 415         struct nchashhead *nchpp;
 416         u_int32_t hash;
 417
 418         /*
 419          * If a linkage already exists we do not have to do anything.
 420          */
 421         hash = fnv_32_buf("", 0, FNV1_32_INIT);
 422         hash = fnv_32_buf(&dvp->v_id, sizeof(dvp->v_id), hash);
 423         LIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) {
 424                 numchecks++;
 425                 if (ncp->nc_vp == tvp &&
 426                     ncp->nc_nlen == 0 &&
 427                     /* ncp->nc_parent == par STAGE-3 par instad of dvp */
 428                     ncp->nc_dvp_data == (uintptr_t)dvp && /* STAGE-2 only */
 429                     ncp->nc_dvp_id == dvp->v_id /* STAGE-2 only */
 430                 ) {
 431                         return;
 432                 }
 433         }
 434
 435         /*
 436          * STAGE-2 par can be NULL
 437          * STAGE-3 par is passed as argument and cannot be NULL
 438          */
 439         par = TAILQ_FIRST(&dvp->v_namecache);
 440
 441         /*
 442          * Otherwise create a new linkage.
 443          */
 444         ncp = malloc(sizeof(*ncp), M_VFSCACHE, M_WAITOK | M_ZERO);
 445
 446         TAILQ_INIT(&ncp->nc_list);
 447         ncp->nc_flag = NCF_MOUNTPT;
 448         if (par != NULL) {
 449                 /* STAGE-3 par never NULL */
 450                 ncp->nc_parent = par;
 451                 if (TAILQ_EMPTY(&par->nc_list)) {
 452                         if (par->nc_vp)
 453                                 vhold(par->nc_vp);
 454                 }
 455                 TAILQ_INSERT_HEAD(&par->nc_list, ncp, nc_entry);
 456         }
 457         ncp->nc_dvp_data = (uintptr_t)dvp; /* STAGE-2 ONLY */
 458         ncp->nc_dvp_id = dvp->v_id;     /* STAGE-2 ONLY */
 459
 460         /*
 461          * Linkup the target vnode.  The target vnode is NULL if this is
 462          * to be a negative cache entry.
 463          */
 464         ++numcache;
 465         ncp->nc_vp = tvp;
 466         TAILQ_INSERT_HEAD(&tvp->v_namecache, ncp, nc_vnode);
 467 #if 0
 468         if (tvp->v_type == VDIR) {
 469                 vp->v_dd = dvp;
 470                 vp->v_ddid = dvp->v_id;
 471         }
 472 #endif
 473
 474         /*
 475          * Hash table
 476          */
 477         hash = fnv_32_buf("", 0, FNV1_32_INIT);
 478         hash = fnv_32_buf(&ncp->nc_dvp_id, sizeof(ncp->nc_dvp_id), hash);
 479         nchpp = NCHHASH(hash);
 480         LIST_INSERT_HEAD(nchpp, ncp, nc_hash);
 481
 482         ncp->nc_flag |= NCF_HASHED;
 483 }
 484
 485 /*
 486  * Add an entry to the cache.
 487  */
 488 void
 489 cache_enter(struct vnode *dvp, struct namecache *par, struct vnode *vp, struct componentname *cnp)
 490 {
 491         struct namecache *ncp;
 492         struct nchashhead *nchpp;
 493         u_int32_t hash;
 494
 495         /* YYY use par */
 496
 497         /*
 498          * "." and ".." are degenerate cases, they are not added to the
 499          * cache.
 500          */
 501         if (cnp->cn_nameptr[0] == '.') {
 502                 if (cnp->cn_namelen == 1) {
 503                         return;
 504                 }
 505                 if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.') {
 506                         if (vp) {
 507                                 dvp->v_dd = vp;
 508                                 dvp->v_ddid = vp->v_id;
 509                         } else {
 510                                 dvp->v_dd = dvp;
 511                                 dvp->v_ddid = 0;
 512                         }
 513                         return;
 514                 }
 515         }
 516
 517         if (nczapcheck)
 518             printf("ENTER '%*.*s' %p ", (int)cnp->cn_namelen, (int)cnp->cn_namelen, cnp->cn_nameptr, vp);
 519
 520         /*
 521          * Locate other entries associated with this vnode and zap them,
 522          * because the purge code may not be able to find them due to
 523          * the topology not yet being consistent.  This is a temporary
 524          * hack.
 525          */
 526         if (vp) {
 527 again:
 528                 TAILQ_FOREACH(ncp, &vp->v_namecache, nc_vnode) {
 529                         if ((ncp->nc_flag & NCF_UNRESOLVED) == 0) {
 530                                 cache_zap(cache_hold(ncp));
 531                                 goto again;
 532                         }
 533                 }
 534         }
 535
 536         hash = fnv_32_buf(cnp->cn_nameptr, cnp->cn_namelen, FNV1_32_INIT);
 537         hash = fnv_32_buf(&dvp->v_id, sizeof(dvp->v_id), hash);
 538
 539         ncp = malloc(sizeof(*ncp), M_VFSCACHE, M_WAITOK | M_ZERO);
 540         ncp->nc_name = malloc(cnp->cn_namelen, M_VFSCACHE, M_WAITOK);
 541         TAILQ_INIT(&ncp->nc_list);
 542         if (nczapcheck)
 543             printf("alloc\n");
 544
 545         /*
 546          * Linkup the parent pointer, bump the parent vnode's hold
 547          * count when we go from 0->1 children.
 548          *
 549          * STAGE-2 par may be NULL
 550          * STAGE-3 par may not be NULL, nc_dvp_* removed
 551          */
 552         par = TAILQ_FIRST(&dvp->v_namecache);
 553         if (par != NULL) {
 554                 ncp->nc_parent = par;
 555                 if (TAILQ_EMPTY(&par->nc_list)) {
 556                         if (par->nc_vp)
 557                                 vhold(par->nc_vp);
 558                 }
 559                 TAILQ_INSERT_HEAD(&par->nc_list, ncp, nc_entry);
 560         }
 561         ncp->nc_dvp_data = (uintptr_t)dvp;
 562         ncp->nc_dvp_id = dvp->v_id;
 563
 564         /*
 565          * Add to the hash table
 566          */
 567         ncp->nc_nlen = cnp->cn_namelen;
 568         bcopy(cnp->cn_nameptr, ncp->nc_name, cnp->cn_namelen);
 569         nchpp = NCHHASH(hash);
 570         LIST_INSERT_HEAD(nchpp, ncp, nc_hash);
 571
 572         ncp->nc_flag |= NCF_HASHED;
 573
 574         /*
 575          * Linkup the target vnode.  The target vnode is NULL if this is
 576          * to be a negative cache entry.
 577          */
 578         ncp->nc_vp = vp;
 579         if (vp == NULL) {
 580                 ++numneg;
 581                 TAILQ_INSERT_HEAD(&ncneglist, ncp, nc_vnode);
 582                 ncp->nc_flag &= ~NCF_WHITEOUT;
 583                 if (cnp->cn_flags & CNP_ISWHITEOUT)
 584                         ncp->nc_flag |= NCF_WHITEOUT;
 585         } else {
 586                 ++numcache;
 587                 if (!TAILQ_EMPTY(&ncp->nc_list))
 588                         vhold(vp);
 589                 TAILQ_INSERT_HEAD(&vp->v_namecache, ncp, nc_vnode);
 590                 if (vp->v_type == VDIR) {
 591                         vp->v_dd = dvp;
 592                         vp->v_ddid = dvp->v_id;
 593                 }
 594         }
 595
 596         /*
 597          * Don't cache too many negative hits
 598          */
 599         if (numneg > MINNEG && numneg * ncnegfactor > numcache) {
 600                 ncp = TAILQ_FIRST(&ncneglist);
 601                 KKASSERT(ncp != NULL);
 602                 cache_zap(cache_hold(ncp));
 603         }
 604 }
 605
 606 /*
 607  * Name cache initialization, from vfsinit() when we are booting
 608  *
 609  * rootnamecache is initialized such that it cannot be recursively deleted.
 610  */
 611 void
 612 nchinit(void)
 613 {
 614         int i;
 615         globaldata_t gd;
 616
 617         /* initialise per-cpu namecache effectiveness statistics. */
 618         for (i = 0; i < ncpus; ++i) {
 619                 gd = globaldata_find(i);
 620                 gd->gd_nchstats = &nchstats[i];
 621         }
 622
 623         TAILQ_INIT(&ncneglist);
 624         nchashtbl = hashinit(desiredvnodes*2, M_VFSCACHE, &nchash);
 625         TAILQ_INIT(&rootnamecache.nc_list);
 626         rootnamecache.nc_flag |= NCF_HASHED | NCF_ROOT | NCF_UNRESOLVED;
 627         rootnamecache.nc_refs = 1;
 628 }
 629
 630 /*
 631  * vfs_cache_setroot()
 632  *
 633  *      Create an association between the root of our namecache and
 634  *      the root vnode.  This routine may be called several times during
 635  *      booting.
 636  */
 637 void
 638 vfs_cache_setroot(struct vnode *nvp)
 639 {
 640         KKASSERT(rootnamecache.nc_refs > 0);    /* don't accidently free */
 641         cache_zap(cache_hold(&rootnamecache));
 642
 643         rootnamecache.nc_vp = nvp;
 644         rootnamecache.nc_flag &= ~NCF_UNRESOLVED;
 645         if (nvp) {
 646                 ++numcache;
 647                 if (!TAILQ_EMPTY(&rootnamecache.nc_list))
 648                         vhold(nvp);
 649                 TAILQ_INSERT_HEAD(&nvp->v_namecache, &rootnamecache, nc_vnode);
 650         } else {
 651                 ++numneg;
 652                 TAILQ_INSERT_HEAD(&ncneglist, &rootnamecache, nc_vnode);
 653                 rootnamecache.nc_flag &= ~NCF_WHITEOUT;
 654         }
 655 }
 656
 657 /*
 658  * Invalidate all namecache entries to a particular vnode as well as
 659  * any direct children of that vnode in the namecache.  This is a
 660  * 'catch all' purge used by filesystems that do not know any better.
 661  *
 662  * A new vnode v_id is generated.  Note that no vnode will ever have a
 663  * v_id of 0.
 664  *
 665  * Note that the linkage between the vnode and its namecache entries will
 666  * be removed, but the namecache entries themselves might stay put due to
 667  * active references from elsewhere in the system or due to the existance of
 668  * the children.   The namecache topology is left intact even if we do not
 669  * know what the vnode association is.  Such entries will be marked
 670  * NCF_UNRESOLVED.
 671  *
 672  * XXX: Only time and the size of v_id prevents this from failing:
 673  * XXX: In theory we should hunt down all (struct vnode*, v_id)
 674  * XXX: soft references and nuke them, at least on the global
 675  * XXX: v_id wraparound.  The period of resistance can be extended
 676  * XXX: by incrementing each vnodes v_id individually instead of
 677  * XXX: using the global v_id.
 678  */
 679 void
 680 cache_purge(struct vnode *vp)
 681 {
 682         static u_long nextid;
 683         struct namecache *ncp;
 684         struct namecache *scan;
 685
 686         /*
 687          * Disassociate the vnode from its namecache entries along with
 688          * (for historical reasons) any direct children.
 689          */
 690         while ((ncp = TAILQ_FIRST(&vp->v_namecache)) != NULL) {
 691                 cache_hold(ncp);
 692
 693 restart: /* YYY hack, fix me */
 694                 TAILQ_FOREACH(scan, &ncp->nc_list, nc_entry) {
 695                         if ((scan->nc_flag & NCF_UNRESOLVED) == 0) {
 696                                 cache_zap(cache_hold(scan));
 697                                 goto restart;
 698                         }
 699                 }
 700                 cache_zap(ncp);
 701         }
 702
 703         /*
 704          * Calculate a new unique id for ".." handling
 705          */
 706         do {
 707                 nextid++;
 708         } while (nextid == vp->v_id || nextid == 0);
 709         vp->v_id = nextid;
 710         vp->v_dd = vp;
 711         vp->v_ddid = 0;
 712 }
 713
 714 /*
 715  * Flush all entries referencing a particular filesystem.
 716  *
 717  * Since we need to check it anyway, we will flush all the invalid
 718  * entries at the same time.
 719  */
 720 void
 721 cache_purgevfs(struct mount *mp)
 722 {
 723         struct nchashhead *nchpp;
 724         struct namecache *ncp, *nnp;
 725
 726         /*
 727          * Scan hash tables for applicable entries.
 728          */
 729         for (nchpp = &nchashtbl[nchash]; nchpp >= nchashtbl; nchpp--) {
 730                 ncp = LIST_FIRST(nchpp);
 731                 if (ncp)
 732                         cache_hold(ncp);
 733                 while (ncp) {
 734                         nnp = LIST_NEXT(ncp, nc_hash);
 735                         if (nnp)
 736                                 cache_hold(nnp);
 737                         if (ncp->nc_vp && ncp->nc_vp->v_mount == mp)
 738                                 cache_zap(ncp);
 739                         else
 740                                 cache_drop(ncp);
 741                         ncp = nnp;
 742                 }
 743         }
 744 }
 745
 746 /*
 747  * cache_leaf_test()
 748  *
 749  *      Test whether the vnode is at a leaf in the nameicache tree.
 750  *
 751  *      Returns 0 if it is a leaf, -1 if it isn't.
 752  */
 753 int
 754 cache_leaf_test(struct vnode *vp)
 755 {
 756         struct namecache *scan;
 757         struct namecache *ncp;
 758
 759         TAILQ_FOREACH(scan, &vp->v_namecache, nc_vnode) {
 760                 TAILQ_FOREACH(ncp, &scan->nc_list, nc_entry) {
 761                         /* YYY && ncp->nc_vp->v_type == VDIR ? */
 762                         if (ncp->nc_vp != NULL)
 763                                 return(-1);
 764                 }
 765         }
 766         return(0);
 767 }
 768
 769 /*
 770  * Perform canonical checks and cache lookup and pass on to filesystem
 771  * through the vop_cachedlookup only if needed.
 772  *
 773  * vop_lookup_args {
 774  *      struct vnode a_dvp;
 775  *      struct namecache *a_ncp;
 776  *      struct vnode **a_vpp;
 777  *      struct namecache **a_ncpp;
 778  *      struct componentname *a_cnp;
 779  * }
 780  */
 781 int
 782 vfs_cache_lookup(struct vop_lookup_args *ap)
 783 {
 784         struct vnode *dvp, *vp;
 785         int lockparent;
 786         int error;
 787         struct namecache *par = ap->a_par;
 788         struct vnode **vpp = ap->a_vpp;
 789         struct namecache **ncpp = ap->a_ncpp;
 790         struct componentname *cnp = ap->a_cnp;
 791         struct ucred *cred = cnp->cn_cred;
 792         int flags = cnp->cn_flags;
 793         struct thread *td = cnp->cn_td;
 794         u_long vpid;    /* capability number of vnode */
 795
 796         *vpp = NULL;
 797         if (ncpp)
 798                 *ncpp = NULL;
 799         dvp = ap->a_dvp;
 800         lockparent = flags & CNP_LOCKPARENT;
 801
 802         if (dvp->v_type != VDIR)
 803                 return (ENOTDIR);
 804
 805         if ((flags & CNP_ISLASTCN) && (dvp->v_mount->mnt_flag & MNT_RDONLY) &&
 806             (cnp->cn_nameiop == NAMEI_DELETE || cnp->cn_nameiop == NAMEI_RENAME)) {
 807                 return (EROFS);
 808         }
 809
 810         error = VOP_ACCESS(dvp, VEXEC, cred, td);
 811
 812         if (error)
 813                 return (error);
 814
 815         error = cache_lookup(dvp, par, vpp, ncpp, cnp);
 816
 817         if (!error)
 818                 return (VOP_CACHEDLOOKUP(dvp, par, vpp, ncpp, cnp));
 819
 820         if (error == ENOENT)
 821                 return (error);
 822
 823         vp = *vpp;
 824         vpid = vp->v_id;
 825         cnp->cn_flags &= ~CNP_PDIRUNLOCK;
 826         if (dvp == vp) {   /* lookup on "." */
 827                 VREF(vp);
 828                 error = 0;
 829         } else if (flags & CNP_ISDOTDOT) {
 830                 VOP_UNLOCK(dvp, NULL, 0, td);
 831                 cnp->cn_flags |= CNP_PDIRUNLOCK;
 832                 error = vget(vp, NULL, LK_EXCLUSIVE, td);
 833                 if (!error && lockparent && (flags & CNP_ISLASTCN)) {
 834                         if ((error = vn_lock(dvp, NULL, LK_EXCLUSIVE, td)) == 0)
 835                                 cnp->cn_flags &= ~CNP_PDIRUNLOCK;
 836                 }
 837         } else {
 838                 error = vget(vp, NULL, LK_EXCLUSIVE, td);
 839                 if (!lockparent || error || !(flags & CNP_ISLASTCN)) {
 840                         VOP_UNLOCK(dvp, NULL, 0, td);
 841                         cnp->cn_flags |= CNP_PDIRUNLOCK;
 842                 }
 843         }
 844         /*
 845          * Check that the capability number did not change
 846          * while we were waiting for the lock.
 847          */
 848         if (!error) {
 849                 if (vpid == vp->v_id)
 850                         return (0);
 851                 vput(vp);
 852                 if (lockparent && dvp != vp && (flags & CNP_ISLASTCN)) {
 853                         VOP_UNLOCK(dvp, NULL, 0, td);
 854                         cnp->cn_flags |= CNP_PDIRUNLOCK;
 855                 }
 856         }
 857         if (cnp->cn_flags & CNP_PDIRUNLOCK) {
 858                 error = vn_lock(dvp, NULL, LK_EXCLUSIVE, td);
 859                 if (error)
 860                         return (error);
 861                 cnp->cn_flags &= ~CNP_PDIRUNLOCK;
 862         }
 863         return (VOP_CACHEDLOOKUP(dvp, par, vpp, ncpp, cnp));
 864 }
 865
 866 static int disablecwd;
 867 SYSCTL_INT(_debug, OID_AUTO, disablecwd, CTLFLAG_RW, &disablecwd, 0, "");
 868
 869 static u_long numcwdcalls; STATNODE(CTLFLAG_RD, numcwdcalls, &numcwdcalls);
 870 static u_long numcwdfail1; STATNODE(CTLFLAG_RD, numcwdfail1, &numcwdfail1);
 871 static u_long numcwdfail2; STATNODE(CTLFLAG_RD, numcwdfail2, &numcwdfail2);
 872 static u_long numcwdfail3; STATNODE(CTLFLAG_RD, numcwdfail3, &numcwdfail3);
 873 static u_long numcwdfail4; STATNODE(CTLFLAG_RD, numcwdfail4, &numcwdfail4);
 874 static u_long numcwdfound; STATNODE(CTLFLAG_RD, numcwdfound, &numcwdfound);
 875
 876 int
 877 __getcwd(struct __getcwd_args *uap)
 878 {
 879         struct proc *p = curproc;
 880         char *bp, *buf;
 881         int error, i, slash_prefixed;
 882         struct filedesc *fdp;
 883         struct namecache *ncp;
 884         struct vnode *vp;
 885
 886         numcwdcalls++;
 887         if (disablecwd)
 888                 return (ENODEV);
 889         if (uap->buflen < 2)
 890                 return (EINVAL);
 891         if (uap->buflen > MAXPATHLEN)
 892                 uap->buflen = MAXPATHLEN;
 893         buf = bp = malloc(uap->buflen, M_TEMP, M_WAITOK);
 894         bp += uap->buflen - 1;
 895         *bp = '\0';
 896         fdp = p->p_fd;
 897         slash_prefixed = 0;
 898         for (vp = fdp->fd_cdir; vp != fdp->fd_rdir && vp != rootvnode;) {
 899                 if (vp->v_flag & VROOT) {
 900                         if (vp->v_mount == NULL) {      /* forced unmount */
 901                                 free(buf, M_TEMP);
 902                                 return (EBADF);
 903                         }
 904                         vp = vp->v_mount->mnt_vnodecovered;
 905                         continue;
 906                 }
 907                 if (vp->v_dd->v_id != vp->v_ddid) {
 908                         numcwdfail1++;
 909                         free(buf, M_TEMP);
 910                         return (ENOTDIR);
 911                 }
 912                 TAILQ_FOREACH(ncp, &vp->v_namecache, nc_vnode) {
 913                         /* ncp->nc_parent == par STAGE-3 */
 914                         if (ncp->nc_dvp_data == (uintptr_t)vp->v_dd &&
 915                             ncp->nc_dvp_id == vp->v_ddid) {
 916                                 break;
 917                         }
 918                 }
 919                 if (ncp == NULL) {
 920                         numcwdfail2++;
 921                         free(buf, M_TEMP);
 922                         return (ENOENT);
 923                 }
 924                 for (i = ncp->nc_nlen - 1; i >= 0; i--) {
 925                         if (bp == buf) {
 926                                 numcwdfail4++;
 927                                 free(buf, M_TEMP);
 928                                 return (ENOMEM);
 929                         }
 930                         *--bp = ncp->nc_name[i];
 931                 }
 932                 if (bp == buf) {
 933                         numcwdfail4++;
 934                         free(buf, M_TEMP);
 935                         return (ENOMEM);
 936                 }
 937                 *--bp = '/';
 938                 slash_prefixed = 1;
 939                 vp = vp->v_dd;
 940         }
 941         if (!slash_prefixed) {
 942                 if (bp == buf) {
 943                         numcwdfail4++;
 944                         free(buf, M_TEMP);
 945                         return (ENOMEM);
 946                 }
 947                 *--bp = '/';
 948         }
 949         numcwdfound++;
 950         error = copyout(bp, uap->buf, strlen(bp) + 1);
 951         free(buf, M_TEMP);
 952         return (error);
 953 }
 954
 955 /*
 956  * Thus begins the fullpath magic.
 957  */
 958
 959 #undef STATNODE
 960 #define STATNODE(name)                                                  \
 961         static u_int name;                                              \
 962         SYSCTL_UINT(_vfs_cache, OID_AUTO, name, CTLFLAG_RD, &name, 0, "")
 963
 964 static int disablefullpath;
 965 SYSCTL_INT(_debug, OID_AUTO, disablefullpath, CTLFLAG_RW,
 966     &disablefullpath, 0, "");
 967
 968 STATNODE(numfullpathcalls);
 969 STATNODE(numfullpathfail1);
 970 STATNODE(numfullpathfail2);
 971 STATNODE(numfullpathfail3);
 972 STATNODE(numfullpathfail4);
 973 STATNODE(numfullpathfound);
 974
 975 int
 976 textvp_fullpath(struct proc *p, char **retbuf, char **retfreebuf)
 977 {
 978         char *bp, *buf;
 979         int i, slash_prefixed;
 980         struct filedesc *fdp;
 981         struct namecache *ncp;
 982         struct vnode *vp, *textvp;
 983
 984         numfullpathcalls++;
 985         if (disablefullpath)
 986                 return (ENODEV);
 987         textvp = p->p_textvp;
 988         if (textvp == NULL)
 989                 return (EINVAL);
 990         buf = malloc(MAXPATHLEN, M_TEMP, M_WAITOK);
 991         bp = buf + MAXPATHLEN - 1;
 992         *bp = '\0';
 993         fdp = p->p_fd;
 994         slash_prefixed = 0;
 995         for (vp = textvp; vp != fdp->fd_rdir && vp != rootvnode;) {
 996                 if (vp->v_flag & VROOT) {
 997                         if (vp->v_mount == NULL) {      /* forced unmount */
 998                                 free(buf, M_TEMP);
 999                                 return (EBADF);
1000                         }
1001                         vp = vp->v_mount->mnt_vnodecovered;
1002                         continue;
1003                 }
1004                 if (vp != textvp && vp->v_dd->v_id != vp->v_ddid) {
1005                         numfullpathfail1++;
1006                         free(buf, M_TEMP);
1007                         return (ENOTDIR);
1008                 }
1009                 TAILQ_FOREACH(ncp, &vp->v_namecache, nc_vnode) {
1010                         if (vp == textvp)
1011                                 break;
1012                         /* ncp->nc_parent == par STAGE-3 */
1013                         if (ncp->nc_dvp_data == (uintptr_t)vp->v_dd &&
1014                             ncp->nc_dvp_id == vp->v_ddid) {
1015                                 break;
1016                         }
1017                 }
1018                 if (ncp == NULL) {
1019                         numfullpathfail2++;
1020                         free(buf, M_TEMP);
1021                         return (ENOENT);
1022                 }
1023                 for (i = ncp->nc_nlen - 1; i >= 0; i--) {
1024                         if (bp == buf) {
1025                                 numfullpathfail4++;
1026                                 free(buf, M_TEMP);
1027                                 return (ENOMEM);
1028                         }
1029                         *--bp = ncp->nc_name[i];
1030                 }
1031                 if (bp == buf) {
1032                         numfullpathfail4++;
1033                         free(buf, M_TEMP);
1034                         return (ENOMEM);
1035                 }
1036                 *--bp = '/';
1037                 slash_prefixed = 1;
1038                 vp = vp->v_dd;
1039         }
1040         if (!slash_prefixed) {
1041                 if (bp == buf) {
1042                         numfullpathfail4++;
1043                         free(buf, M_TEMP);
1044                         return (ENOMEM);
1045                 }
1046                 *--bp = '/';
1047         }
1048         numfullpathfound++;
1049         *retbuf = bp;
1050         *retfreebuf = buf;
1051         return (0);
1052 }
1053