Return to vfs_cache.c CVS log

Up to [CSRG BSD Unix] / 43BSDReno / sys / kern

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

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