Return to vfs_cache.c CVS log

Up to [Net/2] / Net2 / kern

Annotation of Net2/kern/vfs_cache.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1989 The Regents of the University of California.
        !             3:  * All rights reserved.
        !             4:  *
        !             5:  * Redistribution and use in source and binary forms, with or without
        !             6:  * modification, are permitted provided that the following conditions
        !             7:  * are met:
        !             8:  * 1. Redistributions of source code must retain the above copyright
        !             9:  *    notice, this list of conditions and the following disclaimer.
        !            10:  * 2. Redistributions in binary form must reproduce the above copyright
        !            11:  *    notice, this list of conditions and the following disclaimer in the
        !            12:  *    documentation and/or other materials provided with the distribution.
        !            13:  * 3. All advertising materials mentioning features or use of this software
        !            14:  *    must display the following acknowledgement:
        !            15:  *     This product includes software developed by the University of
        !            16:  *     California, Berkeley and its contributors.
        !            17:  * 4. Neither the name of the University nor the names of its contributors
        !            18:  *    may be used to endorse or promote products derived from this software
        !            19:  *    without specific prior written permission.
        !            20:  *
        !            21:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
        !            22:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
        !            23:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
        !            24:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
        !            25:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
        !            26:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
        !            27:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
        !            28:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
        !            29:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
        !            30:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
        !            31:  * SUCH DAMAGE.
        !            32:  *
        !            33:  *     @(#)vfs_cache.c 7.8 (Berkeley) 2/28/91
        !            34:  */
        !            35: 
        !            36: #include "param.h"
        !            37: #include "systm.h"
        !            38: #include "time.h"
        !            39: #include "mount.h"
        !            40: #include "vnode.h"
        !            41: #include "namei.h"
        !            42: #include "errno.h"
        !            43: #include "malloc.h"
        !            44: 
        !            45: /*
        !            46:  * Name caching works as follows:
        !            47:  *
        !            48:  * Names found by directory scans are retained in a cache
        !            49:  * for future reference.  It is managed LRU, so frequently
        !            50:  * used names will hang around.  Cache is indexed by hash value
        !            51:  * obtained from (vp, name) where vp refers to the directory
        !            52:  * containing name.
        !            53:  *
        !            54:  * For simplicity (and economy of storage), names longer than
        !            55:  * a maximum length of NCHNAMLEN are not cached; they occur
        !            56:  * infrequently in any case, and are almost never of interest.
        !            57:  *
        !            58:  * Upon reaching the last segment of a path, if the reference
        !            59:  * is for DELETE, or NOCACHE is set (rewrite), and the
        !            60:  * name is located in the cache, it will be dropped.
        !            61:  */
        !            62: 
        !            63: /*
        !            64:  * Structures associated with name cacheing.
        !            65:  */
        !            66: union nchash {
        !            67:        union   nchash *nch_head[2];
        !            68:        struct  namecache *nch_chain[2];
        !            69: } *nchashtbl;
        !            70: #define        nch_forw        nch_chain[0]
        !            71: #define        nch_back        nch_chain[1]
        !            72: 
        !            73: u_long nchash;                         /* size of hash table - 1 */
        !            74: long   numcache;                       /* number of cache entries allocated */
        !            75: struct namecache *nchhead, **nchtail;  /* LRU chain pointers */
        !            76: struct nchstats nchstats;              /* cache effectiveness statistics */
        !            77: 
        !            78: int doingcache = 1;                    /* 1 => enable the cache */
        !            79: 
        !            80: /*
        !            81:  * Look for a the name in the cache. We don't do this
        !            82:  * if the segment name is long, simply so the cache can avoid
        !            83:  * holding long names (which would either waste space, or
        !            84:  * add greatly to the complexity).
        !            85:  *
        !            86:  * Lookup is called with ni_dvp pointing to the directory to search,
        !            87:  * ni_ptr pointing to the name of the entry being sought, ni_namelen
        !            88:  * tells the length of the name, and ni_hash contains a hash of
        !            89:  * the name. If the lookup succeeds, the vnode is returned in ni_vp
        !            90:  * and a status of -1 is returned. If the lookup determines that
        !            91:  * the name does not exist (negative cacheing), a status of ENOENT
        !            92:  * is returned. If the lookup fails, a status of zero is returned.
        !            93:  */
        !            94: cache_lookup(ndp)
        !            95:        register struct nameidata *ndp;
        !            96: {
        !            97:        register struct vnode *dvp;
        !            98:        register struct namecache *ncp;
        !            99:        union nchash *nhp;
        !           100: 
        !           101:        if (!doingcache)
        !           102:                return (0);
        !           103:        if (ndp->ni_namelen > NCHNAMLEN) {
        !           104:                nchstats.ncs_long++;
        !           105:                ndp->ni_makeentry = 0;
        !           106:                return (0);
        !           107:        }
        !           108:        dvp = ndp->ni_dvp;
        !           109:        nhp = &nchashtbl[ndp->ni_hash & nchash];
        !           110:        for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp;
        !           111:            ncp = ncp->nc_forw) {
        !           112:                if (ncp->nc_dvp == dvp &&
        !           113:                    ncp->nc_dvpid == dvp->v_id &&
        !           114:                    ncp->nc_nlen == ndp->ni_namelen &&
        !           115:                    !bcmp(ncp->nc_name, ndp->ni_ptr, (unsigned)ncp->nc_nlen))
        !           116:                        break;
        !           117:        }
        !           118:        if (ncp == (struct namecache *)nhp) {
        !           119:                nchstats.ncs_miss++;
        !           120:                return (0);
        !           121:        }
        !           122:        if (!ndp->ni_makeentry) {
        !           123:                nchstats.ncs_badhits++;
        !           124:        } else if (ncp->nc_vp == NULL) {
        !           125:                if ((ndp->ni_nameiop & OPMASK) != CREATE) {
        !           126:                        nchstats.ncs_neghits++;
        !           127:                        /*
        !           128:                         * Move this slot to end of LRU chain,
        !           129:                         * if not already there.
        !           130:                         */
        !           131:                        if (ncp->nc_nxt) {
        !           132:                                /* remove from LRU chain */
        !           133:                                *ncp->nc_prev = ncp->nc_nxt;
        !           134:                                ncp->nc_nxt->nc_prev = ncp->nc_prev;
        !           135:                                /* and replace at end of it */
        !           136:                                ncp->nc_nxt = NULL;
        !           137:                                ncp->nc_prev = nchtail;
        !           138:                                *nchtail = ncp;
        !           139:                                nchtail = &ncp->nc_nxt;
        !           140:                        }
        !           141:                        return (ENOENT);
        !           142:                }
        !           143:        } else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
        !           144:                nchstats.ncs_falsehits++;
        !           145:        } else {
        !           146:                nchstats.ncs_goodhits++;
        !           147:                /*
        !           148:                 * move this slot to end of LRU chain, if not already there
        !           149:                 */
        !           150:                if (ncp->nc_nxt) {
        !           151:                        /* remove from LRU chain */
        !           152:                        *ncp->nc_prev = ncp->nc_nxt;
        !           153:                        ncp->nc_nxt->nc_prev = ncp->nc_prev;
        !           154:                        /* and replace at end of it */
        !           155:                        ncp->nc_nxt = NULL;
        !           156:                        ncp->nc_prev = nchtail;
        !           157:                        *nchtail = ncp;
        !           158:                        nchtail = &ncp->nc_nxt;
        !           159:                }
        !           160:                ndp->ni_vp = ncp->nc_vp;
        !           161:                return (-1);
        !           162:        }
        !           163: 
        !           164:        /*
        !           165:         * Last component and we are renaming or deleting,
        !           166:         * the cache entry is invalid, or otherwise don't
        !           167:         * want cache entry to exist.
        !           168:         */
        !           169:        /* remove from LRU chain */
        !           170:        *ncp->nc_prev = ncp->nc_nxt;
        !           171:        if (ncp->nc_nxt)
        !           172:                ncp->nc_nxt->nc_prev = ncp->nc_prev;
        !           173:        else
        !           174:                nchtail = ncp->nc_prev;
        !           175:        /* remove from hash chain */
        !           176:        remque(ncp);
        !           177:        /* insert at head of LRU list (first to grab) */
        !           178:        ncp->nc_nxt = nchhead;
        !           179:        ncp->nc_prev = &nchhead;
        !           180:        nchhead->nc_prev = &ncp->nc_nxt;
        !           181:        nchhead = ncp;
        !           182:        /* and make a dummy hash chain */
        !           183:        ncp->nc_forw = ncp;
        !           184:        ncp->nc_back = ncp;
        !           185:        return (0);
        !           186: }
        !           187: 
        !           188: /*
        !           189:  * Add an entry to the cache
        !           190:  */
        !           191: cache_enter(ndp)
        !           192:        register struct nameidata *ndp;
        !           193: {
        !           194:        register struct namecache *ncp;
        !           195:        union nchash *nhp;
        !           196: 
        !           197:        if (!doingcache)
        !           198:                return;
        !           199:        /*
        !           200:         * Free the cache slot at head of lru chain.
        !           201:         */
        !           202:        if (numcache < desiredvnodes) {
        !           203:                ncp = (struct namecache *)
        !           204:                        malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
        !           205:                bzero((char *)ncp, sizeof *ncp);
        !           206:                numcache++;
        !           207:        } else if (ncp = nchhead) {
        !           208:                /* remove from lru chain */
        !           209:                *ncp->nc_prev = ncp->nc_nxt;
        !           210:                if (ncp->nc_nxt)
        !           211:                        ncp->nc_nxt->nc_prev = ncp->nc_prev;
        !           212:                else
        !           213:                        nchtail = ncp->nc_prev;
        !           214:                /* remove from old hash chain */
        !           215:                remque(ncp);
        !           216:        } else
        !           217:                return;
        !           218:        /* grab the vnode we just found */
        !           219:        ncp->nc_vp = ndp->ni_vp;
        !           220:        if (ndp->ni_vp)
        !           221:                ncp->nc_vpid = ndp->ni_vp->v_id;
        !           222:        else
        !           223:                ncp->nc_vpid = 0;
        !           224:        /* fill in cache info */
        !           225:        ncp->nc_dvp = ndp->ni_dvp;
        !           226:        ncp->nc_dvpid = ndp->ni_dvp->v_id;
        !           227:        ncp->nc_nlen = ndp->ni_namelen;
        !           228:        bcopy(ndp->ni_ptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
        !           229:        /* link at end of lru chain */
        !           230:        ncp->nc_nxt = NULL;
        !           231:        ncp->nc_prev = nchtail;
        !           232:        *nchtail = ncp;
        !           233:        nchtail = &ncp->nc_nxt;
        !           234:        /* and insert on hash chain */
        !           235:        nhp = &nchashtbl[ndp->ni_hash & nchash];
        !           236:        insque(ncp, nhp);
        !           237: }
        !           238: 
        !           239: /*
        !           240:  * Name cache initialization, from vfs_init() when we are booting
        !           241:  */
        !           242: nchinit()
        !           243: {
        !           244:        register union nchash *nchp;
        !           245:        long nchashsize;
        !           246: 
        !           247:        nchhead = 0;
        !           248:        nchtail = &nchhead;
        !           249:        nchashsize = roundup((desiredvnodes + 1) * sizeof *nchp / 2,
        !           250:                NBPG * CLSIZE);
        !           251:        nchashtbl = (union nchash *)malloc((u_long)nchashsize,
        !           252:            M_CACHE, M_WAITOK);
        !           253:        for (nchash = 1; nchash <= nchashsize / sizeof *nchp; nchash <<= 1)
        !           254:                /* void */;
        !           255:        nchash = (nchash >> 1) - 1;
        !           256:        for (nchp = &nchashtbl[nchash]; nchp >= nchashtbl; nchp--) {
        !           257:                nchp->nch_head[0] = nchp;
        !           258:                nchp->nch_head[1] = nchp;
        !           259:        }
        !           260: }
        !           261: 
        !           262: /*
        !           263:  * Cache flush, a particular vnode; called when a vnode is renamed to
        !           264:  * hide entries that would now be invalid
        !           265:  */
        !           266: cache_purge(vp)
        !           267:        struct vnode *vp;
        !           268: {
        !           269:        union nchash *nhp;
        !           270:        struct namecache *ncp;
        !           271: 
        !           272:        vp->v_id = ++nextvnodeid;
        !           273:        if (nextvnodeid != 0)
        !           274:                return;
        !           275:        for (nhp = &nchashtbl[nchash]; nhp >= nchashtbl; nhp--) {
        !           276:                for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp;
        !           277:                    ncp = ncp->nc_forw) {
        !           278:                        ncp->nc_vpid = 0;
        !           279:                        ncp->nc_dvpid = 0;
        !           280:                }
        !           281:        }
        !           282:        vp->v_id = ++nextvnodeid;
        !           283: }
        !           284: 
        !           285: /*
        !           286:  * Cache flush, a whole filesystem; called when filesys is umounted to
        !           287:  * remove entries that would now be invalid
        !           288:  *
        !           289:  * The line "nxtcp = nchhead" near the end is to avoid potential problems
        !           290:  * if the cache lru chain is modified while we are dumping the
        !           291:  * inode.  This makes the algorithm O(n^2), but do you think I care?
        !           292:  */
        !           293: cache_purgevfs(mp)
        !           294:        struct mount *mp;
        !           295: {
        !           296:        register struct namecache *ncp, *nxtcp;
        !           297: 
        !           298:        for (ncp = nchhead; ncp; ncp = nxtcp) {
        !           299:                nxtcp = ncp->nc_nxt;
        !           300:                if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp)
        !           301:                        continue;
        !           302:                /* free the resources we had */
        !           303:                ncp->nc_vp = NULL;
        !           304:                ncp->nc_dvp = NULL;
        !           305:                remque(ncp);            /* remove entry from its hash chain */
        !           306:                ncp->nc_forw = ncp;     /* and make a dummy one */
        !           307:                ncp->nc_back = ncp;
        !           308:                /* delete this entry from LRU chain */
        !           309:                *ncp->nc_prev = nxtcp;
        !           310:                if (nxtcp)
        !           311:                        nxtcp->nc_prev = ncp->nc_prev;
        !           312:                else
        !           313:                        nchtail = ncp->nc_prev;
        !           314:                /* cause rescan of list, it may have altered */
        !           315:                nxtcp = nchhead;
        !           316:                /* put the now-free entry at head of LRU */
        !           317:                ncp->nc_nxt = nxtcp;
        !           318:                ncp->nc_prev = &nchhead;
        !           319:                nxtcp->nc_prev = &ncp->nc_nxt;
        !           320:                nchhead = ncp;
        !           321:        }
        !           322: }

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