Return to vfs_cache.c CVS log

Up to [Apple XNU] / XNU / bsd / vfs

Annotation of XNU/bsd/vfs/vfs_cache.c, revision 1.1

1.1     ! root        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 <mach_nbc.h>
        !            62: #include <sys/param.h>
        !            63: #include <sys/systm.h>
        !            64: #include <sys/time.h>
        !            65: #include <sys/mount.h>
        !            66: #include <sys/vnode.h>
        !            67: #include <sys/namei.h>
        !            68: #include <sys/errno.h>
        !            69: #include <sys/malloc.h>
        !            70: #include <kern/mapfs.h>
        !            71: /*
        !            72:  * Name caching works as follows:
        !            73:  *
        !            74:  * Names found by directory scans are retained in a cache
        !            75:  * for future reference.  It is managed LRU, so frequently
        !            76:  * used names will hang around.  Cache is indexed by hash value
        !            77:  * obtained from (vp, name) where vp refers to the directory
        !            78:  * containing name.
        !            79:  *
        !            80:  * If it is a "negative" entry, (i.e. for a name that is known NOT to
        !            81:  * exist) the vnode pointer will be NULL.
        !            82:  *
        !            83:  * For simplicity (and economy of storage), names longer than
        !            84:  * a maximum length of NCHNAMLEN are not cached; they occur
        !            85:  * infrequently in any case, and are almost never of interest.
        !            86:  *
        !            87:  * Upon reaching the last segment of a path, if the reference
        !            88:  * is for DELETE, or NOCACHE is set (rewrite), and the
        !            89:  * name is located in the cache, it will be dropped.
        !            90:  */
        !            91: 
        !            92: /*
        !            93:  * Structures associated with name cacheing.
        !            94:  */
        !            95: #define NCHHASH(dvp, cnp) \
        !            96:        (&nchashtbl[((dvp)->v_id + (cnp)->cn_hash) & nchash])
        !            97: LIST_HEAD(nchashhead, namecache) *nchashtbl;   /* Hash Table */
        !            98: u_long nchash;                         /* size of hash table - 1 */
        !            99: long   numcache;                       /* number of cache entries allocated */
        !           100: TAILQ_HEAD(, namecache) nclruhead;     /* LRU chain */
        !           101: struct nchstats nchstats;              /* cache effectiveness statistics */
        !           102: u_long nextvnodeid = 0;
        !           103: int doingcache = 1;                    /* 1 => enable the cache */
        !           104: 
        !           105: /*
        !           106:  * Delete an entry from its hash list and move it to the front
        !           107:  * of the LRU list for immediate reuse.
        !           108:  */
        !           109: #if DIAGNOSTIC
        !           110: #define PURGE(ncp)  {                                          \
        !           111:        if (ncp->nc_hash.le_prev == 0)                          \
        !           112:                panic("namecache purge le_prev");               \
        !           113:        if (ncp->nc_hash.le_next == ncp)                        \
        !           114:                panic("namecache purge le_next");               \
        !           115:        LIST_REMOVE(ncp, nc_hash);                              \
        !           116:        ncp->nc_hash.le_prev = 0;                               \
        !           117:        TAILQ_REMOVE(&nclruhead, ncp, nc_lru);                  \
        !           118:        TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);             \
        !           119: }
        !           120: #else
        !           121: #define PURGE(ncp)  {                                          \
        !           122:        LIST_REMOVE(ncp, nc_hash);                              \
        !           123:        ncp->nc_hash.le_prev = 0;                               \
        !           124:        TAILQ_REMOVE(&nclruhead, ncp, nc_lru);                  \
        !           125:        TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);             \
        !           126: }
        !           127: #endif /* DIAGNOSTIC */
        !           128: 
        !           129: /*
        !           130:  * Move an entry that has been used to the tail of the LRU list
        !           131:  * so that it will be preserved for future use.
        !           132:  */
        !           133: #define TOUCH(ncp)  {                                          \
        !           134:        if (ncp->nc_lru.tqe_next != 0) {                        \
        !           135:                TAILQ_REMOVE(&nclruhead, ncp, nc_lru);          \
        !           136:                TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);     \
        !           137:        }                                                       \
        !           138: }
        !           139: 
        !           140: /*
        !           141:  * Lookup an entry in the cache 
        !           142:  *
        !           143:  * We don't do this if the segment name is long, simply so the cache 
        !           144:  * can avoid holding long names (which would either waste space, or
        !           145:  * add greatly to the complexity).
        !           146:  *
        !           147:  * Lookup is called with dvp pointing to the directory to search,
        !           148:  * cnp pointing to the name of the entry being sought. If the lookup
        !           149:  * succeeds, the vnode is returned in *vpp, and a status of -1 is
        !           150:  * returned. If the lookup determines that the name does not exist
        !           151:  * (negative cacheing), a status of ENOENT is returned. If the lookup
        !           152:  * fails, a status of zero is returned.
        !           153:  */
        !           154: 
        !           155: int
        !           156: cache_lookup(dvp, vpp, cnp)
        !           157:        struct vnode *dvp;
        !           158:        struct vnode **vpp;
        !           159:        struct componentname *cnp;
        !           160: {
        !           161:        register struct namecache *ncp, *nnp;
        !           162:        register struct nchashhead *ncpp;
        !           163: 
        !           164:        if (!doingcache) {
        !           165:                cnp->cn_flags &= ~MAKEENTRY;
        !           166:                return (0);
        !           167:        }
        !           168:        if (cnp->cn_namelen > NCHNAMLEN) {
        !           169:                nchstats.ncs_long++;
        !           170:                cnp->cn_flags &= ~MAKEENTRY;
        !           171:                return (0);
        !           172:        }
        !           173: 
        !           174:        ncpp = NCHHASH(dvp, cnp);
        !           175:        for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
        !           176:                nnp = ncp->nc_hash.le_next;
        !           177:                /* If one of the vp's went stale, don't bother anymore. */
        !           178:                if ((ncp->nc_dvpid != ncp->nc_dvp->v_id) ||
        !           179:                    (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id)) {
        !           180:                        nchstats.ncs_falsehits++;
        !           181:                        PURGE(ncp);
        !           182:                        continue;
        !           183:                }
        !           184:                /* Now that we know the vp's to be valid, is it ours ? */
        !           185:                if (ncp->nc_dvp == dvp &&
        !           186:                    ncp->nc_nlen == cnp->cn_namelen &&
        !           187:                    !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
        !           188:                        break;
        !           189:        }
        !           190: 
        !           191:        /* We failed to find an entry */
        !           192:        if (ncp == 0) {
        !           193:                nchstats.ncs_miss++;
        !           194:                return (0);
        !           195:        }
        !           196: 
        !           197:        /* We don't want to have an entry, so dump it */
        !           198:        if ((cnp->cn_flags & MAKEENTRY) == 0) {
        !           199:                nchstats.ncs_badhits++;
        !           200:                PURGE(ncp);
        !           201:                return (0);
        !           202:        } 
        !           203: 
        !           204:        /* We found a "positive" match, return the vnode */
        !           205:         if (ncp->nc_vp) {
        !           206:                nchstats.ncs_goodhits++;
        !           207:                TOUCH(ncp);
        !           208:                *vpp = ncp->nc_vp;
        !           209:                return (-1);
        !           210:        }
        !           211: 
        !           212:        /* We found a negative match, and want to create it, so purge */
        !           213:        if (cnp->cn_nameiop == CREATE) {
        !           214:                nchstats.ncs_badhits++;
        !           215:                PURGE(ncp);
        !           216:                return (0);
        !           217:        }
        !           218: 
        !           219:        /*
        !           220:         * We found a "negative" match, ENOENT notifies client of this match.
        !           221:         * The nc_vpid field records whether this is a whiteout.
        !           222:         */
        !           223:        nchstats.ncs_neghits++;
        !           224:        TOUCH(ncp);
        !           225:        cnp->cn_flags |= ncp->nc_vpid;
        !           226:        return (ENOENT);
        !           227: }
        !           228: 
        !           229: /*
        !           230:  * Add an entry to the cache.
        !           231:  */
        !           232: void
        !           233: cache_enter(dvp, vp, cnp)
        !           234:        struct vnode *dvp;
        !           235:        struct vnode *vp;
        !           236:        struct componentname *cnp;
        !           237: {
        !           238:        register struct namecache *ncp;
        !           239:        register struct nchashhead *ncpp;
        !           240: 
        !           241:        if (!doingcache)
        !           242:                return;
        !           243: 
        !           244:        /*
        !           245:         * If an entry that is too long, is entered, bad things happen.
        !           246:         * cache_lookup acts as the sentinel to make sure longer names
        !           247:         * are not stored. This here will prevent outsiders from doing
        !           248:         * something that is unexpected.
        !           249:         */
        !           250:        if (cnp->cn_namelen > NCHNAMLEN)
        !           251:                panic("cache_enter: name too long");
        !           252: 
        !           253:        /*
        !           254:         * We allocate a new entry if we are less than the maximum
        !           255:         * allowed and the one at the front of the LRU list is in use.
        !           256:         * Otherwise we use the one at the front of the LRU list.
        !           257:         */
        !           258:        if (numcache < desiredvnodes &&
        !           259:            ((ncp = nclruhead.tqh_first) == NULL ||
        !           260:            ncp->nc_hash.le_prev != 0)) {
        !           261:                /* Add one more entry */
        !           262:                ncp = (struct namecache *)
        !           263:                        _MALLOC_ZONE((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
        !           264:                numcache++;
        !           265:        } else if (ncp = nclruhead.tqh_first) {
        !           266:                /* reuse an old entry */
        !           267:                TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
        !           268:                if (ncp->nc_hash.le_prev != 0) {
        !           269: #if DIAGNOSTIC
        !           270:                        if (ncp->nc_hash.le_next == ncp)
        !           271:                                panic("cache_enter: le_next");
        !           272: #endif
        !           273:                        LIST_REMOVE(ncp, nc_hash);
        !           274:                        ncp->nc_hash.le_prev = 0;
        !           275:                }
        !           276:        } else {
        !           277:                /* give up */
        !           278:                return;
        !           279:        }
        !           280: 
        !           281:        /*
        !           282:         * Fill in cache info, if vp is NULL this is a "negative" cache entry.
        !           283:         * For negative entries, we have to record whether it is a whiteout.
        !           284:         * the whiteout flag is stored in the nc_vpid field which is
        !           285:         * otherwise unused.
        !           286:         */
        !           287:        ncp->nc_vp = vp;
        !           288:        if (vp)
        !           289:                ncp->nc_vpid = vp->v_id;
        !           290:        else
        !           291:                ncp->nc_vpid = cnp->cn_flags & ISWHITEOUT;
        !           292:        ncp->nc_dvp = dvp;
        !           293:        ncp->nc_dvpid = dvp->v_id;
        !           294:        ncp->nc_nlen = cnp->cn_namelen;
        !           295:        bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
        !           296:        TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
        !           297:        ncpp = NCHHASH(dvp, cnp);
        !           298: #if DIAGNOSTIC
        !           299:        {
        !           300:                register struct namecache *p;
        !           301: 
        !           302:                for (p = ncpp->lh_first; p != 0; p = p->nc_hash.le_next)
        !           303:                        if (p == ncp)
        !           304:                                panic("cache_enter: duplicate");
        !           305:        }
        !           306: #endif
        !           307:        LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
        !           308: }
        !           309: 
        !           310: /*
        !           311:  * Name cache initialization, from vfs_init() when we are booting
        !           312:  */
        !           313: void
        !           314: nchinit()
        !           315: {
        !           316: 
        !           317:        TAILQ_INIT(&nclruhead);
        !           318:        nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash);
        !           319: }
        !           320: 
        !           321: /*
        !           322:  * Invalidate a all entries to particular vnode.
        !           323:  * 
        !           324:  * We actually just increment the v_id, that will do it. The entries will
        !           325:  * be purged by lookup as they get found. If the v_id wraps around, we
        !           326:  * need to ditch the entire cache, to avoid confusion. No valid vnode will
        !           327:  * ever have (v_id == 0).
        !           328:  */
        !           329: void
        !           330: cache_purge(vp)
        !           331:        struct vnode *vp;
        !           332: {
        !           333:        struct namecache *ncp;
        !           334:        struct nchashhead *ncpp;
        !           335: 
        !           336:        vp->v_id = ++nextvnodeid;
        !           337:        if (nextvnodeid != 0)
        !           338:                return;
        !           339:        for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
        !           340:                while (ncp = ncpp->lh_first)
        !           341:                        PURGE(ncp);
        !           342:        }
        !           343:        vp->v_id = ++nextvnodeid;
        !           344: #if MACH_NBC
        !           345:        /* ?? */
        !           346: /*     mapfs_uncache(vp); */
        !           347: #endif /* MACH_NBC */
        !           348: }
        !           349: 
        !           350: /*
        !           351:  * Flush all entries referencing a particular filesystem.
        !           352:  *
        !           353:  * Since we need to check it anyway, we will flush all the invalid
        !           354:  * entriess at the same time.
        !           355:  */
        !           356: void
        !           357: cache_purgevfs(mp)
        !           358:        struct mount *mp;
        !           359: {
        !           360:        struct nchashhead *ncpp;
        !           361:        struct namecache *ncp, *nnp;
        !           362: 
        !           363:        /* Scan hash tables for applicable entries */
        !           364:        for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
        !           365:                for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
        !           366:                        nnp = ncp->nc_hash.le_next;
        !           367:                        if (ncp->nc_dvpid != ncp->nc_dvp->v_id ||
        !           368:                            (ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id) ||
        !           369:                            ncp->nc_dvp->v_mount == mp) {
        !           370:                                PURGE(ncp);
        !           371:                        }
        !           372:                }
        !           373:        }
        !           374: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.