bsd/vfs/vfs_cache.c

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25 /* Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved */
  26 /*
  27  * Copyright (c) 1989, 1993, 1995
  28  *      The Regents of the University of California.  All rights reserved.
  29  *
  30  * This code is derived from software contributed to Berkeley by
  31  * Poul-Henning Kamp of the FreeBSD Project.
  32  *
  33  * Redistribution and use in source and binary forms, with or without
  34  * modification, are permitted provided that the following conditions
  35  * are met:
  36  * 1. Redistributions of source code must retain the above copyright
  37  *    notice, this list of conditions and the following disclaimer.
  38  * 2. Redistributions in binary form must reproduce the above copyright
  39  *    notice, this list of conditions and the following disclaimer in the
  40  *    documentation and/or other materials provided with the distribution.
  41  * 3. All advertising materials mentioning features or use of this software
  42  *    must display the following acknowledgement:
  43  *      This product includes software developed by the University of
  44  *      California, Berkeley and its contributors.
  45  * 4. Neither the name of the University nor the names of its contributors
  46  *    may be used to endorse or promote products derived from this software
  47  *    without specific prior written permission.
  48  *
  49  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  50  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  51  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  52  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  53  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  54  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  55  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  56  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  57  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  58  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  59  * SUCH DAMAGE.
  60  *
  61  *
  62  *      @(#)vfs_cache.c 8.5 (Berkeley) 3/22/95
  63  */
  64 #include <sys/param.h>
  65 #include <sys/systm.h>
  66 #include <sys/time.h>
  67 #include <sys/mount.h>
  68 #include <sys/vnode.h>
  69 #include <sys/namei.h>
  70 #include <sys/errno.h>
  71 #include <sys/malloc.h>
  72
  73 /*
  74  * Name caching works as follows:
  75  *
  76  * Names found by directory scans are retained in a cache
  77  * for future reference.  It is managed LRU, so frequently
  78  * used names will hang around.  Cache is indexed by hash value
  79  * obtained from (vp, name) where vp refers to the directory
  80  * containing name.
  81  *
  82  * If it is a "negative" entry, (i.e. for a name that is known NOT to
  83  * exist) the vnode pointer will be NULL.
  84  *
  85  * For simplicity (and economy of storage), names longer than
  86  * a maximum length of NCHNAMLEN are not cached; they occur
  87  * infrequently in any case, and are almost never of interest.
  88  *
  89  * Upon reaching the last segment of a path, if the reference
  90  * is for DELETE, or NOCACHE is set (rewrite), and the
  91  * name is located in the cache, it will be dropped.
  92  */
  93
  94 /*
  95  * Structures associated with name cacheing.
  96  */
  97 #define NCHHASH(dvp, cnp) \
  98         (&nchashtbl[((dvp)->v_id + (cnp)->cn_hash) & nchash])
  99 LIST_HEAD(nchashhead, namecache) *nchashtbl;    /* Hash Table */
 100 u_long  nchash;                         /* size of hash table - 1 */
 101 long    numcache;                       /* number of cache entries allocated */
 102 TAILQ_HEAD(, namecache) nclruhead;      /* LRU chain */
 103 struct  nchstats nchstats;              /* cache effectiveness statistics */
 104 u_long nextvnodeid = 0;
 105 int doingcache = 1;                     /* 1 => enable the cache */
 106
 107 /*
 108  * Delete an entry from its hash list and move it to the front
 109  * of the LRU list for immediate reuse.
 110  */
 111 #if DIAGNOSTIC
 112 #define PURGE(ncp)  {                                           \
 113         if (ncp->nc_hash.le_prev == 0)                          \
 114                 panic("namecache purge le_prev");               \
 115         if (ncp->nc_hash.le_next == ncp)                        \
 116                 panic("namecache purge le_next");               \
 117         LIST_REMOVE(ncp, nc_hash);                              \
 118         ncp->nc_hash.le_prev = 0;                               \
 119         TAILQ_REMOVE(&nclruhead, ncp, nc_lru);                  \
 120         TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);             \
 121 }
 122 #else
 123 #define PURGE(ncp)  {                                           \
 124         LIST_REMOVE(ncp, nc_hash);                              \
 125         ncp->nc_hash.le_prev = 0;                               \
 126         TAILQ_REMOVE(&nclruhead, ncp, nc_lru);                  \
 127         TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);             \
 128 }
 129 #endif /* DIAGNOSTIC */
 130
 131 /*
 132  * Move an entry that has been used to the tail of the LRU list
 133  * so that it will be preserved for future use.
 134  */
 135 #define TOUCH(ncp)  {                                           \
 136         if (ncp->nc_lru.tqe_next != 0) {                        \
 137                 TAILQ_REMOVE(&nclruhead, ncp, nc_lru);          \
 138                 TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);     \
 139         }                                                       \
 140 }
 141
 142 /*
 143  * Lookup an entry in the cache
 144  *
 145  * We don't do this if the segment name is long, simply so the cache
 146  * can avoid holding long names (which would either waste space, or
 147  * add greatly to the complexity).
 148  *
 149  * Lookup is called with dvp pointing to the directory to search,
 150  * cnp pointing to the name of the entry being sought. If the lookup
 151  * succeeds, the vnode is returned in *vpp, and a status of -1 is
 152  * returned. If the lookup determines that the name does not exist
 153  * (negative cacheing), a status of ENOENT is returned. If the lookup
 154  * fails, a status of zero is returned.
 155  */
 156
 157 int
 158 cache_lookup(dvp, vpp, cnp)
 159         struct vnode *dvp;
 160         struct vnode **vpp;
 161         struct componentname *cnp;
 162 {
 163         register struct namecache *ncp, *nnp;
 164         register struct nchashhead *ncpp;
 165
 166         if (!doingcache) {
 167                 cnp->cn_flags &= ~MAKEENTRY;
 168                 return (0);
 169         }
 170         if (cnp->cn_namelen > NCHNAMLEN) {
 171                 nchstats.ncs_long++;
 172                 cnp->cn_flags &= ~MAKEENTRY;
 173                 return (0);
 174         }
 175
 176         ncpp = NCHHASH(dvp, cnp);
 177         for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
 178                 nnp = ncp->nc_hash.le_next;
 179                 /* If one of the vp's went stale, don't bother anymore. */
 180                 if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) ||
 181                     (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id)) {
 182                         nchstats.ncs_falsehits++;
 183                         PURGE(ncp);
 184                         continue;
 185                 }
 186                 /* Now that we know the vp's to be valid, is it ours ? */
 187                 if (ncp->nc_dvp == dvp &&
 188                     ncp->nc_nlen == cnp->cn_namelen &&
 189                     !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
 190                         break;
 191         }
 192
 193         /* We failed to find an entry */
 194         if (ncp == 0) {
 195                 nchstats.ncs_miss++;
 196                 return (0);
 197         }
 198
 199         /* We don't want to have an entry, so dump it */
 200         if ((cnp->cn_flags & MAKEENTRY) == 0) {
 201                 nchstats.ncs_badhits++;
 202                 PURGE(ncp);
 203                 return (0);
 204         }
 205
 206         /* We found a "positive" match, return the vnode */
 207         if (ncp->nc_vp) {
 208                 nchstats.ncs_goodhits++;
 209                 TOUCH(ncp);
 210                 *vpp = ncp->nc_vp;
 211                 return (-1);
 212         }
 213
 214         /* We found a negative match, and want to create it, so purge */
 215         if (cnp->cn_nameiop == CREATE) {
 216                 nchstats.ncs_badhits++;
 217                 PURGE(ncp);
 218                 return (0);
 219         }
 220
 221         /*
 222          * We found a "negative" match, ENOENT notifies client of this match.
 223          * The nc_vpid field records whether this is a whiteout.
 224          */
 225         nchstats.ncs_neghits++;
 226         TOUCH(ncp);
 227         cnp->cn_flags |= ncp->nc_vpid;
 228         return (ENOENT);
 229 }
 230
 231 /*
 232  * Add an entry to the cache.
 233  */
 234 void
 235 cache_enter(dvp, vp, cnp)
 236         struct vnode *dvp;
 237         struct vnode *vp;
 238         struct componentname *cnp;
 239 {
 240         register struct namecache *ncp;
 241         register struct nchashhead *ncpp;
 242
 243         if (!doingcache)
 244                 return;
 245
 246         /*
 247          * If an entry that is too long, is entered, bad things happen.
 248          * cache_lookup acts as the sentinel to make sure longer names
 249          * are not stored. This here will prevent outsiders from doing
 250          * something that is unexpected.
 251          */
 252         if (cnp->cn_namelen > NCHNAMLEN)
 253                 panic("cache_enter: name too long");
 254
 255         /*
 256          * We allocate a new entry if we are less than the maximum
 257          * allowed and the one at the front of the LRU list is in use.
 258          * Otherwise we use the one at the front of the LRU list.
 259          */
 260         if (numcache < desiredvnodes &&
 261             ((ncp = nclruhead.tqh_first) == NULL ||
 262             ncp->nc_hash.le_prev != 0)) {
 263                 /* Add one more entry */
 264                 ncp = (struct namecache *)
 265                         _MALLOC_ZONE((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
 266                 numcache++;
 267         } else if (ncp = nclruhead.tqh_first) {
 268                 /* reuse an old entry */
 269                 TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
 270                 if (ncp->nc_hash.le_prev != 0) {
 271 #if DIAGNOSTIC
 272                         if (ncp->nc_hash.le_next == ncp)
 273                                 panic("cache_enter: le_next");
 274 #endif
 275                         LIST_REMOVE(ncp, nc_hash);
 276                         ncp->nc_hash.le_prev = 0;
 277                 }
 278         } else {
 279                 /* give up */
 280                 return;
 281         }
 282
 283         /*
 284          * Fill in cache info, if vp is NULL this is a "negative" cache entry.
 285          * For negative entries, we have to record whether it is a whiteout.
 286          * the whiteout flag is stored in the nc_vpid field which is
 287          * otherwise unused.
 288          */
 289         ncp->nc_vp = vp;
 290         if (vp)
 291                 ncp->nc_vpid = vp->v_id;
 292         else
 293                 ncp->nc_vpid = cnp->cn_flags & ISWHITEOUT;
 294         ncp->nc_dvp = dvp;
 295         ncp->nc_dvpid = dvp->v_id;
 296         ncp->nc_nlen = cnp->cn_namelen;
 297         bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
 298         TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
 299         ncpp = NCHHASH(dvp, cnp);
 300 #if DIAGNOSTIC
 301         {
 302                 register struct namecache *p;
 303
 304                 for (p = ncpp->lh_first; p != 0; p = p->nc_hash.le_next)
 305                         if (p == ncp)
 306                                 panic("cache_enter: duplicate");
 307         }
 308 #endif
 309         LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
 310 }
 311
 312 /*
 313  * Name cache initialization, from vfs_init() when we are booting
 314  */
 315 void
 316 nchinit()
 317 {
 318
 319         TAILQ_INIT(&nclruhead);
 320         nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash);
 321 }
 322
 323 /*
 324  * Invalidate a all entries to particular vnode.
 325  *
 326  * We actually just increment the v_id, that will do it. The entries will
 327  * be purged by lookup as they get found. If the v_id wraps around, we
 328  * need to ditch the entire cache, to avoid confusion. No valid vnode will
 329  * ever have (v_id == 0).
 330  */
 331 void
 332 cache_purge(vp)
 333         struct vnode *vp;
 334 {
 335         struct namecache *ncp;
 336         struct nchashhead *ncpp;
 337
 338         vp->v_id = ++nextvnodeid;
 339         if (nextvnodeid != 0)
 340                 return;
 341         for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
 342                 while (ncp = ncpp->lh_first)
 343                         PURGE(ncp);
 344         }
 345         vp->v_id = ++nextvnodeid;
 346 }
 347
 348 /*
 349  * Flush all entries referencing a particular filesystem.
 350  *
 351  * Since we need to check it anyway, we will flush all the invalid
 352  * entriess at the same time.
 353  */
 354 void
 355 cache_purgevfs(mp)
 356         struct mount *mp;
 357 {
 358         struct nchashhead *ncpp;
 359         struct namecache *ncp, *nnp;
 360
 361         /* Scan hash tables for applicable entries */
 362         for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
 363                 for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
 364                         nnp = ncp->nc_hash.le_next;
 365                         if (ncp->nc_dvpid != ncp->nc_dvp->v_id ||
 366                             (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id) ||
 367                             ncp->nc_dvp->v_mount == mp) {
 368                                 PURGE(ncp);
 369                         }
 370                 }
 371         }
 372 }