137487Smckusick /* 2*63180Sbostic * Copyright (c) 1989, 1993 3*63180Sbostic * The Regents of the University of California. All rights reserved. 437487Smckusick * 544455Sbostic * %sccs.include.redist.c% 637487Smckusick * 7*63180Sbostic * @(#)vfs_cache.c 8.1 (Berkeley) 06/10/93 837487Smckusick */ 937487Smckusick 1056517Sbostic #include <sys/param.h> 1156517Sbostic #include <sys/systm.h> 1256517Sbostic #include <sys/time.h> 1356517Sbostic #include <sys/mount.h> 1456517Sbostic #include <sys/vnode.h> 1556517Sbostic #include <sys/namei.h> 1656517Sbostic #include <sys/errno.h> 1756517Sbostic #include <sys/malloc.h> 1837487Smckusick 1937487Smckusick /* 2037487Smckusick * Name caching works as follows: 2137487Smckusick * 2237487Smckusick * Names found by directory scans are retained in a cache 2337487Smckusick * for future reference. It is managed LRU, so frequently 2437487Smckusick * used names will hang around. Cache is indexed by hash value 2538768Smckusick * obtained from (vp, name) where vp refers to the directory 2638768Smckusick * containing name. 2737487Smckusick * 2837487Smckusick * For simplicity (and economy of storage), names longer than 2937487Smckusick * a maximum length of NCHNAMLEN are not cached; they occur 3037487Smckusick * infrequently in any case, and are almost never of interest. 3137487Smckusick * 3237487Smckusick * Upon reaching the last segment of a path, if the reference 3337487Smckusick * is for DELETE, or NOCACHE is set (rewrite), and the 3437487Smckusick * name is located in the cache, it will be dropped. 3537487Smckusick */ 3637487Smckusick 3737487Smckusick /* 3837487Smckusick * Structures associated with name cacheing. 3937487Smckusick */ 4055544Smckusick struct namecache **nchashtbl; 4140881Smckusick u_long nchash; /* size of hash table - 1 */ 4240881Smckusick long numcache; /* number of cache entries allocated */ 4337487Smckusick struct namecache *nchhead, **nchtail; /* LRU chain pointers */ 4437487Smckusick struct nchstats nchstats; /* cache effectiveness statistics */ 4537487Smckusick 4638768Smckusick int doingcache = 1; /* 1 => enable the cache */ 4738768Smckusick 4837487Smckusick /* 4937487Smckusick * Look for a the name in the cache. We don't do this 5037487Smckusick * if the segment name is long, simply so the cache can avoid 5137487Smckusick * holding long names (which would either waste space, or 5237487Smckusick * add greatly to the complexity). 5338768Smckusick * 5438768Smckusick * Lookup is called with ni_dvp pointing to the directory to search, 5538768Smckusick * ni_ptr pointing to the name of the entry being sought, ni_namelen 5638768Smckusick * tells the length of the name, and ni_hash contains a hash of 5738768Smckusick * the name. If the lookup succeeds, the vnode is returned in ni_vp 5838768Smckusick * and a status of -1 is returned. If the lookup determines that 5938768Smckusick * the name does not exist (negative cacheing), a status of ENOENT 6038768Smckusick * is returned. If the lookup fails, a status of zero is returned. 6137487Smckusick */ 6252231Sheideman int 6352306Sheideman cache_lookup(dvp, vpp, cnp) 6452231Sheideman struct vnode *dvp; 6552231Sheideman struct vnode **vpp; 6652231Sheideman struct componentname *cnp; 6737487Smckusick { 6855544Smckusick register struct namecache *ncp, *ncq, **ncpp; 6937487Smckusick 7038768Smckusick if (!doingcache) 7138768Smckusick return (0); 7252231Sheideman if (cnp->cn_namelen > NCHNAMLEN) { 7337487Smckusick nchstats.ncs_long++; 7452231Sheideman cnp->cn_flags &= ~MAKEENTRY; 7537487Smckusick return (0); 7637487Smckusick } 7755544Smckusick ncpp = &nchashtbl[cnp->cn_hash & nchash]; 7855544Smckusick for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) { 7938768Smckusick if (ncp->nc_dvp == dvp && 8038768Smckusick ncp->nc_dvpid == dvp->v_id && 8152231Sheideman ncp->nc_nlen == cnp->cn_namelen && 8255544Smckusick !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) 8337487Smckusick break; 8437487Smckusick } 8555544Smckusick if (ncp == NULL) { 8637487Smckusick nchstats.ncs_miss++; 8737487Smckusick return (0); 8837487Smckusick } 8952231Sheideman if (!(cnp->cn_flags & MAKEENTRY)) { 9038768Smckusick nchstats.ncs_badhits++; 9138768Smckusick } else if (ncp->nc_vp == NULL) { 9252306Sheideman if (cnp->cn_nameiop != CREATE) { 9346747Smckusick nchstats.ncs_neghits++; 9446747Smckusick /* 9546747Smckusick * Move this slot to end of LRU chain, 9646747Smckusick * if not already there. 9746747Smckusick */ 9846747Smckusick if (ncp->nc_nxt) { 9946747Smckusick /* remove from LRU chain */ 10046747Smckusick *ncp->nc_prev = ncp->nc_nxt; 10146747Smckusick ncp->nc_nxt->nc_prev = ncp->nc_prev; 10246747Smckusick /* and replace at end of it */ 10346747Smckusick ncp->nc_nxt = NULL; 10446747Smckusick ncp->nc_prev = nchtail; 10546747Smckusick *nchtail = ncp; 10646747Smckusick nchtail = &ncp->nc_nxt; 10746747Smckusick } 10846747Smckusick return (ENOENT); 10937487Smckusick } 11038768Smckusick } else if (ncp->nc_vpid != ncp->nc_vp->v_id) { 11138768Smckusick nchstats.ncs_falsehits++; 11238768Smckusick } else { 11337487Smckusick nchstats.ncs_goodhits++; 11438768Smckusick /* 11538768Smckusick * move this slot to end of LRU chain, if not already there 11638768Smckusick */ 11738768Smckusick if (ncp->nc_nxt) { 11838768Smckusick /* remove from LRU chain */ 11938768Smckusick *ncp->nc_prev = ncp->nc_nxt; 12038768Smckusick ncp->nc_nxt->nc_prev = ncp->nc_prev; 12138768Smckusick /* and replace at end of it */ 12238768Smckusick ncp->nc_nxt = NULL; 12338768Smckusick ncp->nc_prev = nchtail; 12438768Smckusick *nchtail = ncp; 12538768Smckusick nchtail = &ncp->nc_nxt; 12638768Smckusick } 12752231Sheideman *vpp = ncp->nc_vp; 12838768Smckusick return (-1); 12937487Smckusick } 13037487Smckusick 13137487Smckusick /* 13237487Smckusick * Last component and we are renaming or deleting, 13337487Smckusick * the cache entry is invalid, or otherwise don't 13437487Smckusick * want cache entry to exist. 13537487Smckusick */ 13637487Smckusick /* remove from LRU chain */ 13755544Smckusick if (ncq = ncp->nc_nxt) 13855544Smckusick ncq->nc_prev = ncp->nc_prev; 13937487Smckusick else 14037487Smckusick nchtail = ncp->nc_prev; 14155544Smckusick *ncp->nc_prev = ncq; 14238768Smckusick /* remove from hash chain */ 14355544Smckusick if (ncq = ncp->nc_forw) 14455544Smckusick ncq->nc_back = ncp->nc_back; 14555544Smckusick *ncp->nc_back = ncq; 14655544Smckusick /* and make a dummy hash chain */ 14755544Smckusick ncp->nc_forw = NULL; 14855544Smckusick ncp->nc_back = NULL; 14937487Smckusick /* insert at head of LRU list (first to grab) */ 15056341Smckusick if (ncq = nchhead) 15156341Smckusick ncq->nc_prev = &ncp->nc_nxt; 15256341Smckusick else 15356341Smckusick nchtail = &ncp->nc_nxt; 15456341Smckusick nchhead = ncp; 15556341Smckusick ncp->nc_nxt = ncq; 15637487Smckusick ncp->nc_prev = &nchhead; 15737487Smckusick return (0); 15837487Smckusick } 15937487Smckusick 16037487Smckusick /* 16137487Smckusick * Add an entry to the cache 16237487Smckusick */ 16352306Sheideman cache_enter(dvp, vp, cnp) 16452231Sheideman struct vnode *dvp; 16552231Sheideman struct vnode *vp; 16652231Sheideman struct componentname *cnp; 16737487Smckusick { 16855544Smckusick register struct namecache *ncp, *ncq, **ncpp; 16937487Smckusick 17055185Smckusick #ifdef DIAGNOSTIC 17155185Smckusick if (cnp->cn_namelen > NCHNAMLEN) 17255185Smckusick panic("cache_enter: name too long"); 17355185Smckusick #endif 17438768Smckusick if (!doingcache) 17538768Smckusick return; 17637487Smckusick /* 17737487Smckusick * Free the cache slot at head of lru chain. 17837487Smckusick */ 17940881Smckusick if (numcache < desiredvnodes) { 18040881Smckusick ncp = (struct namecache *) 18145117Smckusick malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 18240881Smckusick bzero((char *)ncp, sizeof *ncp); 18340881Smckusick numcache++; 18440881Smckusick } else if (ncp = nchhead) { 18537487Smckusick /* remove from lru chain */ 18655544Smckusick if (ncq = ncp->nc_nxt) 18755544Smckusick ncq->nc_prev = ncp->nc_prev; 18837487Smckusick else 18937487Smckusick nchtail = ncp->nc_prev; 19055544Smckusick *ncp->nc_prev = ncq; 19155699Smckusick /* remove from old hash chain, if on one */ 19255699Smckusick if (ncp->nc_back) { 19355699Smckusick if (ncq = ncp->nc_forw) 19455699Smckusick ncq->nc_back = ncp->nc_back; 19555699Smckusick *ncp->nc_back = ncq; 19655699Smckusick ncp->nc_forw = NULL; 19755699Smckusick ncp->nc_back = NULL; 19855699Smckusick } 19940881Smckusick } else 20040881Smckusick return; 20140881Smckusick /* grab the vnode we just found */ 20252231Sheideman ncp->nc_vp = vp; 20352231Sheideman if (vp) 20452231Sheideman ncp->nc_vpid = vp->v_id; 20540881Smckusick else 20640881Smckusick ncp->nc_vpid = 0; 20740881Smckusick /* fill in cache info */ 20852231Sheideman ncp->nc_dvp = dvp; 20952231Sheideman ncp->nc_dvpid = dvp->v_id; 21052231Sheideman ncp->nc_nlen = cnp->cn_namelen; 21152231Sheideman bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 21240881Smckusick /* link at end of lru chain */ 21340881Smckusick ncp->nc_nxt = NULL; 21440881Smckusick ncp->nc_prev = nchtail; 21540881Smckusick *nchtail = ncp; 21640881Smckusick nchtail = &ncp->nc_nxt; 21740881Smckusick /* and insert on hash chain */ 21855544Smckusick ncpp = &nchashtbl[cnp->cn_hash & nchash]; 21955544Smckusick if (ncq = *ncpp) 22055544Smckusick ncq->nc_back = &ncp->nc_forw; 22155544Smckusick ncp->nc_forw = ncq; 22255544Smckusick ncp->nc_back = ncpp; 22355544Smckusick *ncpp = ncp; 22437487Smckusick } 22537487Smckusick 22637487Smckusick /* 22740881Smckusick * Name cache initialization, from vfs_init() when we are booting 22837487Smckusick */ 22937487Smckusick nchinit() 23037487Smckusick { 23137487Smckusick 23237487Smckusick nchtail = &nchhead; 23355544Smckusick nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash); 23437487Smckusick } 23537487Smckusick 23637487Smckusick /* 23737487Smckusick * Cache flush, a particular vnode; called when a vnode is renamed to 23838768Smckusick * hide entries that would now be invalid 23937487Smckusick */ 24037487Smckusick cache_purge(vp) 24138768Smckusick struct vnode *vp; 24237487Smckusick { 24355544Smckusick struct namecache *ncp, **ncpp; 24437487Smckusick 24538768Smckusick vp->v_id = ++nextvnodeid; 24638768Smckusick if (nextvnodeid != 0) 24738768Smckusick return; 24855544Smckusick for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { 24955544Smckusick for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) { 25040881Smckusick ncp->nc_vpid = 0; 25140881Smckusick ncp->nc_dvpid = 0; 25240881Smckusick } 25337487Smckusick } 25438768Smckusick vp->v_id = ++nextvnodeid; 25537487Smckusick } 25637487Smckusick 25737487Smckusick /* 25837487Smckusick * Cache flush, a whole filesystem; called when filesys is umounted to 25937487Smckusick * remove entries that would now be invalid 26037487Smckusick * 26137487Smckusick * The line "nxtcp = nchhead" near the end is to avoid potential problems 26237487Smckusick * if the cache lru chain is modified while we are dumping the 26337487Smckusick * inode. This makes the algorithm O(n^2), but do you think I care? 26437487Smckusick */ 26537487Smckusick cache_purgevfs(mp) 26645117Smckusick struct mount *mp; 26737487Smckusick { 26837487Smckusick register struct namecache *ncp, *nxtcp; 26937487Smckusick 27037487Smckusick for (ncp = nchhead; ncp; ncp = nxtcp) { 27155544Smckusick if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) { 27255544Smckusick nxtcp = ncp->nc_nxt; 27337487Smckusick continue; 27455544Smckusick } 27537487Smckusick /* free the resources we had */ 27637487Smckusick ncp->nc_vp = NULL; 27738768Smckusick ncp->nc_dvp = NULL; 27855699Smckusick /* remove from old hash chain, if on one */ 27955699Smckusick if (ncp->nc_back) { 28055699Smckusick if (nxtcp = ncp->nc_forw) 28155699Smckusick nxtcp->nc_back = ncp->nc_back; 28255699Smckusick *ncp->nc_back = nxtcp; 28355699Smckusick ncp->nc_forw = NULL; 28455699Smckusick ncp->nc_back = NULL; 28555699Smckusick } 28637487Smckusick /* delete this entry from LRU chain */ 28755544Smckusick if (nxtcp = ncp->nc_nxt) 28837487Smckusick nxtcp->nc_prev = ncp->nc_prev; 28937487Smckusick else 29037487Smckusick nchtail = ncp->nc_prev; 29155544Smckusick *ncp->nc_prev = nxtcp; 29237487Smckusick /* cause rescan of list, it may have altered */ 29356341Smckusick /* also put the now-free entry at head of LRU */ 29456341Smckusick if (nxtcp = nchhead) 29556341Smckusick nxtcp->nc_prev = &ncp->nc_nxt; 29656341Smckusick else 29756341Smckusick nchtail = &ncp->nc_nxt; 29856341Smckusick nchhead = ncp; 29937487Smckusick ncp->nc_nxt = nxtcp; 30037487Smckusick ncp->nc_prev = &nchhead; 30137487Smckusick } 30237487Smckusick } 303