bsd/vfs/vfs_cache.c

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