sys/kern/vfs_cache.c

   1 /*
   2  * Copyright (c) 1989, 1993, 1995
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Poul-Henning Kamp of the FreeBSD Project.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  *
  36  *      @(#)vfs_cache.c 8.5 (Berkeley) 3/22/95
  37  * $FreeBSD$
  38  */
  39
  40 #include <sys/param.h>
  41 #include <sys/systm.h>
  42 #include <sys/kernel.h>
  43 #include <sys/sysctl.h>
  44 #include <sys/mount.h>
  45 #include <sys/vnode.h>
  46 #include <sys/namei.h>
  47 #include <sys/malloc.h>
  48 #include <sys/sysproto.h>
  49 #include <sys/proc.h>
  50 #include <sys/filedesc.h>
  51
  52 /*
  53  * Name caching works as follows:
  54  *
  55  * Names found by directory scans are retained in a cache
  56  * for future reference.  It is managed LRU, so frequently
  57  * used names will hang around.  Cache is indexed by hash value
  58  * obtained from (vp, name) where vp refers to the directory
  59  * containing name.
  60  *
  61  * If it is a "negative" entry, (i.e. for a name that is known NOT to
  62  * exist) the vnode pointer will be NULL.
  63  *
  64  * Upon reaching the last segment of a path, if the reference
  65  * is for DELETE, or NOCACHE is set (rewrite), and the
  66  * name is located in the cache, it will be dropped.
  67  */
  68
  69 /*
  70  * Structures associated with name cacheing.
  71  */
  72 #define NCHHASH(dvp, hash) \
  73         (&nchashtbl[((dvp)->v_id + (hash)) & nchash])
  74 static LIST_HEAD(nchashhead, namecache) *nchashtbl;     /* Hash Table */
  75 static TAILQ_HEAD(, namecache) ncneg;   /* Hash Table */
  76 static u_long   nchash;                 /* size of hash table */
  77 SYSCTL_INT(_debug, OID_AUTO, nchash, CTLFLAG_RD, &nchash, 0, "");
  78 static u_long   ncnegfactor = 16;       /* ratio of negative entries */
  79 SYSCTL_INT(_debug, OID_AUTO, ncnegfactor, CTLFLAG_RW, &ncnegfactor, 0, "");
  80 static u_long   numneg;         /* number of cache entries allocated */
  81 SYSCTL_INT(_debug, OID_AUTO, numneg, CTLFLAG_RD, &numneg, 0, "");
  82 static u_long   numcache;               /* number of cache entries allocated */
  83 SYSCTL_INT(_debug, OID_AUTO, numcache, CTLFLAG_RD, &numcache, 0, "");
  84 struct  nchstats nchstats;              /* cache effectiveness statistics */
  85
  86 static int      doingcache = 1;         /* 1 => enable the cache */
  87 SYSCTL_INT(_debug, OID_AUTO, vfscache, CTLFLAG_RW, &doingcache, 0, "");
  88 SYSCTL_INT(_debug, OID_AUTO, vnsize, CTLFLAG_RD, 0, sizeof(struct vnode), "");
  89 SYSCTL_INT(_debug, OID_AUTO, ncsize, CTLFLAG_RD, 0, sizeof(struct namecache), "");
  90
  91 /*
  92  * The new name cache statistics
  93  */
  94 SYSCTL_NODE(_vfs, OID_AUTO, cache, CTLFLAG_RW, 0, "Name cache statistics");
  95 #define STATNODE(mode, name, var) \
  96         SYSCTL_INT(_vfs_cache, OID_AUTO, name, mode, var, 0, "");
  97 STATNODE(CTLFLAG_RD, numneg, &numneg);
  98 STATNODE(CTLFLAG_RD, numcache, &numcache);
  99 static u_long numcalls; STATNODE(CTLFLAG_RD, numcalls, &numcalls);
 100 static u_long dothits; STATNODE(CTLFLAG_RD, dothits, &dothits);
 101 static u_long dotdothits; STATNODE(CTLFLAG_RD, dotdothits, &dotdothits);
 102 static u_long numchecks; STATNODE(CTLFLAG_RD, numchecks, &numchecks);
 103 static u_long nummiss; STATNODE(CTLFLAG_RD, nummiss, &nummiss);
 104 static u_long nummisszap; STATNODE(CTLFLAG_RD, nummisszap, &nummisszap);
 105 static u_long numposzaps; STATNODE(CTLFLAG_RD, numposzaps, &numposzaps);
 106 static u_long numposhits; STATNODE(CTLFLAG_RD, numposhits, &numposhits);
 107 static u_long numnegzaps; STATNODE(CTLFLAG_RD, numnegzaps, &numnegzaps);
 108 static u_long numneghits; STATNODE(CTLFLAG_RD, numneghits, &numneghits);
 109
 110
 111 static void cache_zap __P((struct namecache *ncp));
 112
 113 MALLOC_DEFINE(M_VFSCACHE, "vfscache", "VFS name cache entries");
 114
 115 /*
 116  * Flags in namecache.nc_flag
 117  */
 118 #define NCF_WHITE       1
 119 /*
 120  * Delete an entry from its hash list and move it to the front
 121  * of the LRU list for immediate reuse.
 122  */
 123 static void
 124 cache_zap(ncp)
 125         struct namecache *ncp;
 126 {
 127         LIST_REMOVE(ncp, nc_hash);
 128         LIST_REMOVE(ncp, nc_src);
 129         if (LIST_EMPTY(&ncp->nc_dvp->v_cache_src))
 130                 vdrop(ncp->nc_dvp);
 131         if (ncp->nc_vp) {
 132                 TAILQ_REMOVE(&ncp->nc_vp->v_cache_dst, ncp, nc_dst);
 133         } else {
 134                 TAILQ_REMOVE(&ncneg, ncp, nc_dst);
 135                 numneg--;
 136         }
 137         numcache--;
 138         free(ncp, M_VFSCACHE);
 139 }
 140
 141 /*
 142  * Lookup an entry in the cache
 143  *
 144  * We don't do this if the segment name is long, simply so the cache
 145  * can avoid holding long names (which would either waste space, or
 146  * add greatly to the complexity).
 147  *
 148  * Lookup is called with dvp pointing to the directory to search,
 149  * cnp pointing to the name of the entry being sought. If the lookup
 150  * succeeds, the vnode is returned in *vpp, and a status of -1 is
 151  * returned. If the lookup determines that the name does not exist
 152  * (negative cacheing), a status of ENOENT is returned. If the lookup
 153  * fails, a status of zero is returned.
 154  */
 155
 156 int
 157 cache_lookup(dvp, vpp, cnp)
 158         struct vnode *dvp;
 159         struct vnode **vpp;
 160         struct componentname *cnp;
 161 {
 162         struct namecache *ncp;
 163         u_long hash;
 164         u_char *cp;
 165         int len;
 166
 167         if (!doingcache) {
 168                 cnp->cn_flags &= ~MAKEENTRY;
 169                 return (0);
 170         }
 171
 172         numcalls++;
 173
 174         if (cnp->cn_nameptr[0] == '.') {
 175                 if (cnp->cn_namelen == 1) {
 176                         *vpp = dvp;
 177                         dothits++;
 178                         return (-1);
 179                 }
 180                 if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.') {
 181                         dotdothits++;
 182                         if (dvp->v_dd->v_id != dvp->v_ddid ||
 183                             (cnp->cn_flags & MAKEENTRY) == 0) {
 184                                 dvp->v_ddid = 0;
 185                                 return (0);
 186                         }
 187                         *vpp = dvp->v_dd;
 188                         return (-1);
 189                 }
 190         }
 191
 192         hash = 0;
 193         len = cnp->cn_namelen;
 194         for (cp = cnp->cn_nameptr; len; len--, cp++)
 195                 hash += *cp;
 196         LIST_FOREACH(ncp, (NCHHASH(dvp, hash)), nc_hash) {
 197                 numchecks++;
 198                 if (ncp->nc_dvp == dvp && ncp->nc_nlen == cnp->cn_namelen &&
 199                     !bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen))
 200                         break;
 201         }
 202
 203         /* We failed to find an entry */
 204         if (ncp == 0) {
 205                 if ((cnp->cn_flags & MAKEENTRY) == 0) {
 206                         nummisszap++;
 207                 } else {
 208                         nummiss++;
 209                 }
 210                 nchstats.ncs_miss++;
 211                 return (0);
 212         }
 213
 214         /* We don't want to have an entry, so dump it */
 215         if ((cnp->cn_flags & MAKEENTRY) == 0) {
 216                 numposzaps++;
 217                 nchstats.ncs_badhits++;
 218                 cache_zap(ncp);
 219                 return (0);
 220         }
 221
 222         /* We found a "positive" match, return the vnode */
 223         if (ncp->nc_vp) {
 224                 numposhits++;
 225                 nchstats.ncs_goodhits++;
 226                 *vpp = ncp->nc_vp;
 227                 return (-1);
 228         }
 229
 230         /* We found a negative match, and want to create it, so purge */
 231         if (cnp->cn_nameiop == CREATE) {
 232                 numnegzaps++;
 233                 nchstats.ncs_badhits++;
 234                 cache_zap(ncp);
 235                 return (0);
 236         }
 237
 238         numneghits++;
 239         /*
 240          * We found a "negative" match, ENOENT notifies client of this match.
 241          * The nc_vpid field records whether this is a whiteout.
 242          */
 243         TAILQ_REMOVE(&ncneg, ncp, nc_dst);
 244         TAILQ_INSERT_TAIL(&ncneg, ncp, nc_dst);
 245         nchstats.ncs_neghits++;
 246         if (ncp->nc_flag & NCF_WHITE)
 247                 cnp->cn_flags |= ISWHITEOUT;
 248         return (ENOENT);
 249 }
 250
 251 /*
 252  * Add an entry to the cache.
 253  */
 254 void
 255 cache_enter(dvp, vp, cnp)
 256         struct vnode *dvp;
 257         struct vnode *vp;
 258         struct componentname *cnp;
 259 {
 260         struct namecache *ncp;
 261         struct nchashhead *ncpp;
 262         u_long hash;
 263         u_char *cp, *dp;
 264         int len;
 265
 266         if (!doingcache)
 267                 return;
 268
 269         if (cnp->cn_nameptr[0] == '.') {
 270                 if (cnp->cn_namelen == 1) {
 271                         return;
 272                 }
 273                 if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.') {
 274                         if (vp) {
 275                                 dvp->v_dd = vp;
 276                                 dvp->v_ddid = vp->v_id;
 277                         } else {
 278                                 dvp->v_dd = dvp;
 279                                 dvp->v_ddid = 0;
 280                         }
 281                         return;
 282                 }
 283         }
 284
 285         ncp = (struct namecache *)
 286                 malloc(sizeof *ncp + cnp->cn_namelen, M_VFSCACHE, M_WAITOK);
 287         bzero((char *)ncp, sizeof *ncp);
 288         numcache++;
 289         if (!vp) {
 290                 numneg++;
 291                 ncp->nc_flag = cnp->cn_flags & ISWHITEOUT ? NCF_WHITE : 0;
 292         } else if (vp->v_type == VDIR) {
 293                 vp->v_dd = dvp;
 294                 vp->v_ddid = dvp->v_id;
 295         }
 296
 297         /*
 298          * Fill in cache info, if vp is NULL this is a "negative" cache entry.
 299          * For negative entries, we have to record whether it is a whiteout.
 300          * the whiteout flag is stored in the nc_vpid field which is
 301          * otherwise unused.
 302          */
 303         ncp->nc_vp = vp;
 304         ncp->nc_dvp = dvp;
 305         len = ncp->nc_nlen = cnp->cn_namelen;
 306         hash = 0;
 307         dp = ncp->nc_name;
 308         for (cp = cnp->cn_nameptr; len; len--, cp++, dp++)
 309                 hash += (*dp = *cp);
 310         ncpp = NCHHASH(dvp, hash);
 311         LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
 312         if (LIST_EMPTY(&dvp->v_cache_src))
 313                 vhold(dvp);
 314         LIST_INSERT_HEAD(&dvp->v_cache_src, ncp, nc_src);
 315         if (vp) {
 316                 TAILQ_INSERT_HEAD(&vp->v_cache_dst, ncp, nc_dst);
 317         } else {
 318                 TAILQ_INSERT_TAIL(&ncneg, ncp, nc_dst);
 319         }
 320         if (numneg * ncnegfactor > numcache) {
 321                 ncp = TAILQ_FIRST(&ncneg);
 322                 cache_zap(ncp);
 323         }
 324 }
 325
 326 /*
 327  * Name cache initialization, from vfs_init() when we are booting
 328  */
 329 void
 330 nchinit()
 331 {
 332
 333         TAILQ_INIT(&ncneg);
 334         nchashtbl = hashinit(desiredvnodes*2, M_VFSCACHE, &nchash);
 335 }
 336
 337 /*
 338  * Invalidate all entries to a particular vnode.
 339  *
 340  * Remove all entries in the namecache relating to this vnode and
 341  * change the v_id.  We take the v_id from a global counter, since
 342  * it becomes a handy sequence number in crash-dumps that way.
 343  * No valid vnode will ever have (v_id == 0).
 344  *
 345  * XXX: Only time and the size of v_id prevents this from failing:
 346  * XXX: In theory we should hunt down all (struct vnode*, v_id)
 347  * XXX: soft references and nuke them, at least on the global
 348  * XXX: v_id wraparound.  The period of resistance can be extended
 349  * XXX: by incrementing each vnodes v_id individually instead of
 350  * XXX: using the global v_id.
 351  */
 352
 353 void
 354 cache_purge(vp)
 355         struct vnode *vp;
 356 {
 357         static u_long nextid;
 358
 359         while (!LIST_EMPTY(&vp->v_cache_src))
 360                 cache_zap(LIST_FIRST(&vp->v_cache_src));
 361         while (!TAILQ_EMPTY(&vp->v_cache_dst))
 362                 cache_zap(TAILQ_FIRST(&vp->v_cache_dst));
 363
 364         do
 365                 nextid++;
 366         while (nextid == vp->v_id || !nextid);
 367         vp->v_id = nextid;
 368         vp->v_dd = vp;
 369         vp->v_ddid = 0;
 370 }
 371
 372 /*
 373  * Flush all entries referencing a particular filesystem.
 374  *
 375  * Since we need to check it anyway, we will flush all the invalid
 376  * entries at the same time.
 377  */
 378 void
 379 cache_purgevfs(mp)
 380         struct mount *mp;
 381 {
 382         struct nchashhead *ncpp;
 383         struct namecache *ncp, *nnp;
 384
 385         /* Scan hash tables for applicable entries */
 386         for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
 387                 for (ncp = LIST_FIRST(ncpp); ncp != 0; ncp = nnp) {
 388                         nnp = LIST_NEXT(ncp, nc_hash);
 389                         if (ncp->nc_dvp->v_mount == mp) {
 390                                 cache_zap(ncp);
 391                         }
 392                 }
 393         }
 394 }
 395
 396 /*
 397  * Perform canonical checks and cache lookup and pass on to filesystem
 398  * through the vop_cachedlookup only if needed.
 399  */
 400
 401 int
 402 vfs_cache_lookup(ap)
 403         struct vop_lookup_args /* {
 404                 struct vnode *a_dvp;
 405                 struct vnode **a_vpp;
 406                 struct componentname *a_cnp;
 407         } */ *ap;
 408 {
 409         struct vnode *vdp;
 410         struct vnode *pdp;
 411         int lockparent;
 412         int error;
 413         struct vnode **vpp = ap->a_vpp;
 414         struct componentname *cnp = ap->a_cnp;
 415         struct ucred *cred = cnp->cn_cred;
 416         int flags = cnp->cn_flags;
 417         struct proc *p = cnp->cn_proc;
 418         u_long vpid;    /* capability number of vnode */
 419
 420         *vpp = NULL;
 421         vdp = ap->a_dvp;
 422         lockparent = flags & LOCKPARENT;
 423
 424         if (vdp->v_type != VDIR)
 425                 return (ENOTDIR);
 426
 427         if ((flags & ISLASTCN) && (vdp->v_mount->mnt_flag & MNT_RDONLY) &&
 428             (cnp->cn_nameiop == DELETE || cnp->cn_nameiop == RENAME))
 429                 return (EROFS);
 430
 431         error = VOP_ACCESS(vdp, VEXEC, cred, cnp->cn_proc);
 432
 433         if (error)
 434                 return (error);
 435
 436         error = cache_lookup(vdp, vpp, cnp);
 437
 438         if (!error)
 439                 return (VOP_CACHEDLOOKUP(ap->a_dvp, ap->a_vpp, ap->a_cnp));
 440
 441         if (error == ENOENT)
 442                 return (error);
 443
 444         pdp = vdp;
 445         vdp = *vpp;
 446         vpid = vdp->v_id;
 447         if (pdp == vdp) {   /* lookup on "." */
 448                 VREF(vdp);
 449                 error = 0;
 450         } else if (flags & ISDOTDOT) {
 451                 VOP_UNLOCK(pdp, 0, p);
 452                 error = vget(vdp, LK_EXCLUSIVE, p);
 453                 if (!error && lockparent && (flags & ISLASTCN))
 454                         error = vn_lock(pdp, LK_EXCLUSIVE, p);
 455         } else {
 456                 error = vget(vdp, LK_EXCLUSIVE, p);
 457                 if (!lockparent || error || !(flags & ISLASTCN))
 458                         VOP_UNLOCK(pdp, 0, p);
 459         }
 460         /*
 461          * Check that the capability number did not change
 462          * while we were waiting for the lock.
 463          */
 464         if (!error) {
 465                 if (vpid == vdp->v_id)
 466                         return (0);
 467                 vput(vdp);
 468                 if (lockparent && pdp != vdp && (flags & ISLASTCN))
 469                         VOP_UNLOCK(pdp, 0, p);
 470         }
 471         error = vn_lock(pdp, LK_EXCLUSIVE, p);
 472         if (error)
 473                 return (error);
 474         return (VOP_CACHEDLOOKUP(ap->a_dvp, ap->a_vpp, ap->a_cnp));
 475 }
 476
 477
 478 #ifndef _SYS_SYSPROTO_H_
 479 struct  __getcwd_args {
 480         u_char  *buf;
 481         u_int   buflen;
 482 };
 483 #endif
 484
 485 #define STATNODE(mode, name, var) \
 486         SYSCTL_INT(_vfs_cache, OID_AUTO, name, mode, var, 0, "");
 487
 488 static int disablecwd;
 489 SYSCTL_INT(_debug, OID_AUTO, disablecwd, CTLFLAG_RW, &disablecwd, 0, "");
 490
 491 static u_long numcwdcalls; STATNODE(CTLFLAG_RD, numcwdcalls, &numcwdcalls);
 492 static u_long numcwdfail1; STATNODE(CTLFLAG_RD, numcwdfail1, &numcwdfail1);
 493 static u_long numcwdfail2; STATNODE(CTLFLAG_RD, numcwdfail2, &numcwdfail2);
 494 static u_long numcwdfail3; STATNODE(CTLFLAG_RD, numcwdfail3, &numcwdfail3);
 495 static u_long numcwdfail4; STATNODE(CTLFLAG_RD, numcwdfail4, &numcwdfail4);
 496 static u_long numcwdfound; STATNODE(CTLFLAG_RD, numcwdfound, &numcwdfound);
 497 int
 498 __getcwd(p, uap)
 499         struct proc *p;
 500         struct __getcwd_args *uap;
 501 {
 502         char *bp, *buf;
 503         int error, i, slash_prefixed;
 504         struct filedesc *fdp;
 505         struct namecache *ncp;
 506         struct vnode *vp;
 507
 508         numcwdcalls++;
 509         if (disablecwd)
 510                 return (ENODEV);
 511         if (uap->buflen < 2)
 512                 return (EINVAL);
 513         if (uap->buflen > MAXPATHLEN)
 514                 uap->buflen = MAXPATHLEN;
 515         buf = bp = malloc(uap->buflen, M_TEMP, M_WAITOK);
 516         bp += uap->buflen - 1;
 517         *bp = '\0';
 518         fdp = p->p_fd;
 519         slash_prefixed = 0;
 520         for (vp = fdp->fd_cdir; vp != fdp->fd_rdir && vp != rootvnode;) {
 521                 if (vp->v_flag & VROOT) {
 522                         if (vp->v_mount == NULL)        /* forced unmount */
 523                                 return (EBADF);
 524                         vp = vp->v_mount->mnt_vnodecovered;
 525                         continue;
 526                 }
 527                 if (vp->v_dd->v_id != vp->v_ddid) {
 528                         numcwdfail1++;
 529                         free(buf, M_TEMP);
 530                         return (ENOTDIR);
 531                 }
 532                 ncp = TAILQ_FIRST(&vp->v_cache_dst);
 533                 if (!ncp) {
 534                         numcwdfail2++;
 535                         free(buf, M_TEMP);
 536                         return (ENOENT);
 537                 }
 538                 if (ncp->nc_dvp != vp->v_dd) {
 539                         numcwdfail3++;
 540                         free(buf, M_TEMP);
 541                         return (EBADF);
 542                 }
 543                 for (i = ncp->nc_nlen - 1; i >= 0; i--) {
 544                         if (bp == buf) {
 545                                 numcwdfail4++;
 546                                 free(buf, M_TEMP);
 547                                 return (ENOMEM);
 548                         }
 549                         *--bp = ncp->nc_name[i];
 550                 }
 551                 if (bp == buf) {
 552                         numcwdfail4++;
 553                         free(buf, M_TEMP);
 554                         return (ENOMEM);
 555                 }
 556                 *--bp = '/';
 557                 slash_prefixed = 1;
 558                 vp = vp->v_dd;
 559         }
 560         if (!slash_prefixed) {
 561                 if (bp == buf) {
 562                         numcwdfail4++;
 563                         free(buf, M_TEMP);
 564                         return (ENOMEM);
 565                 }
 566                 *--bp = '/';
 567         }
 568         numcwdfound++;
 569         error = copyout(bp, uap->buf, strlen(bp) + 1);
 570         free(buf, M_TEMP);
 571         return (error);
 572 }
 573