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