137487Smckusick /* 237487Smckusick * Copyright (c) 1989 The Regents of the University of California. 337487Smckusick * All rights reserved. 437487Smckusick * 544455Sbostic * %sccs.include.redist.c% 637487Smckusick * 7*45117Smckusick * @(#)vfs_cache.c 7.7 (Berkeley) 08/24/90 837487Smckusick */ 937487Smckusick 1037487Smckusick #include "param.h" 1137487Smckusick #include "systm.h" 1237487Smckusick #include "time.h" 13*45117Smckusick #include "mount.h" 1437487Smckusick #include "vnode.h" 1537487Smckusick #include "namei.h" 1638768Smckusick #include "errno.h" 1740881Smckusick #include "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 */ 4037487Smckusick union nchash { 4137487Smckusick union nchash *nch_head[2]; 4237487Smckusick struct namecache *nch_chain[2]; 4340881Smckusick } *nchashtbl; 4437487Smckusick #define nch_forw nch_chain[0] 4537487Smckusick #define nch_back nch_chain[1] 4637487Smckusick 4740881Smckusick u_long nchash; /* size of hash table - 1 */ 4840881Smckusick long numcache; /* number of cache entries allocated */ 4937487Smckusick struct namecache *nchhead, **nchtail; /* LRU chain pointers */ 5037487Smckusick struct nchstats nchstats; /* cache effectiveness statistics */ 5137487Smckusick 5238768Smckusick int doingcache = 1; /* 1 => enable the cache */ 5338768Smckusick 5437487Smckusick /* 5537487Smckusick * Look for a the name in the cache. We don't do this 5637487Smckusick * if the segment name is long, simply so the cache can avoid 5737487Smckusick * holding long names (which would either waste space, or 5837487Smckusick * add greatly to the complexity). 5938768Smckusick * 6038768Smckusick * Lookup is called with ni_dvp pointing to the directory to search, 6138768Smckusick * ni_ptr pointing to the name of the entry being sought, ni_namelen 6238768Smckusick * tells the length of the name, and ni_hash contains a hash of 6338768Smckusick * the name. If the lookup succeeds, the vnode is returned in ni_vp 6438768Smckusick * and a status of -1 is returned. If the lookup determines that 6538768Smckusick * the name does not exist (negative cacheing), a status of ENOENT 6638768Smckusick * is returned. If the lookup fails, a status of zero is returned. 6737487Smckusick */ 6837487Smckusick cache_lookup(ndp) 6937487Smckusick register struct nameidata *ndp; 7037487Smckusick { 7138768Smckusick register struct vnode *dvp; 7237487Smckusick register struct namecache *ncp; 7337487Smckusick union nchash *nhp; 7437487Smckusick 7538768Smckusick if (!doingcache) 7638768Smckusick return (0); 7738768Smckusick if (ndp->ni_namelen > NCHNAMLEN) { 7837487Smckusick nchstats.ncs_long++; 7937487Smckusick ndp->ni_makeentry = 0; 8037487Smckusick return (0); 8137487Smckusick } 8238768Smckusick dvp = ndp->ni_dvp; 8340881Smckusick nhp = &nchashtbl[ndp->ni_hash & nchash]; 8437487Smckusick for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp; 8537487Smckusick ncp = ncp->nc_forw) { 8638768Smckusick if (ncp->nc_dvp == dvp && 8738768Smckusick ncp->nc_dvpid == dvp->v_id && 8838768Smckusick ncp->nc_nlen == ndp->ni_namelen && 8938768Smckusick !bcmp(ncp->nc_name, ndp->ni_ptr, (unsigned)ncp->nc_nlen)) 9037487Smckusick break; 9137487Smckusick } 9237487Smckusick if (ncp == (struct namecache *)nhp) { 9337487Smckusick nchstats.ncs_miss++; 9437487Smckusick return (0); 9537487Smckusick } 9638768Smckusick if (!ndp->ni_makeentry) { 9738768Smckusick nchstats.ncs_badhits++; 9838768Smckusick } else if (ncp->nc_vp == NULL) { 9938768Smckusick nchstats.ncs_neghits++; 10037487Smckusick /* 10138768Smckusick * move this slot to end of LRU chain, if not already there 10237487Smckusick */ 10337487Smckusick if (ncp->nc_nxt) { 10437487Smckusick /* remove from LRU chain */ 10537487Smckusick *ncp->nc_prev = ncp->nc_nxt; 10637487Smckusick ncp->nc_nxt->nc_prev = ncp->nc_prev; 10737487Smckusick /* and replace at end of it */ 10837487Smckusick ncp->nc_nxt = NULL; 10937487Smckusick ncp->nc_prev = nchtail; 11037487Smckusick *nchtail = ncp; 11137487Smckusick nchtail = &ncp->nc_nxt; 11237487Smckusick } 11338768Smckusick return (ENOENT); 11438768Smckusick } else if (ncp->nc_vpid != ncp->nc_vp->v_id) { 11538768Smckusick nchstats.ncs_falsehits++; 11638768Smckusick } else { 11737487Smckusick nchstats.ncs_goodhits++; 11838768Smckusick /* 11938768Smckusick * move this slot to end of LRU chain, if not already there 12038768Smckusick */ 12138768Smckusick if (ncp->nc_nxt) { 12238768Smckusick /* remove from LRU chain */ 12338768Smckusick *ncp->nc_prev = ncp->nc_nxt; 12438768Smckusick ncp->nc_nxt->nc_prev = ncp->nc_prev; 12538768Smckusick /* and replace at end of it */ 12638768Smckusick ncp->nc_nxt = NULL; 12738768Smckusick ncp->nc_prev = nchtail; 12838768Smckusick *nchtail = ncp; 12938768Smckusick nchtail = &ncp->nc_nxt; 13038768Smckusick } 13138768Smckusick ndp->ni_vp = ncp->nc_vp; 13238768Smckusick return (-1); 13337487Smckusick } 13437487Smckusick 13537487Smckusick /* 13637487Smckusick * Last component and we are renaming or deleting, 13737487Smckusick * the cache entry is invalid, or otherwise don't 13837487Smckusick * want cache entry to exist. 13937487Smckusick */ 14037487Smckusick /* remove from LRU chain */ 14137487Smckusick *ncp->nc_prev = ncp->nc_nxt; 14237487Smckusick if (ncp->nc_nxt) 14337487Smckusick ncp->nc_nxt->nc_prev = ncp->nc_prev; 14437487Smckusick else 14537487Smckusick nchtail = ncp->nc_prev; 14638768Smckusick /* remove from hash chain */ 14738768Smckusick remque(ncp); 14837487Smckusick /* insert at head of LRU list (first to grab) */ 14937487Smckusick ncp->nc_nxt = nchhead; 15037487Smckusick ncp->nc_prev = &nchhead; 15137487Smckusick nchhead->nc_prev = &ncp->nc_nxt; 15237487Smckusick nchhead = ncp; 15337487Smckusick /* and make a dummy hash chain */ 15437487Smckusick ncp->nc_forw = ncp; 15537487Smckusick ncp->nc_back = ncp; 15637487Smckusick return (0); 15737487Smckusick } 15837487Smckusick 15937487Smckusick /* 16037487Smckusick * Add an entry to the cache 16137487Smckusick */ 16237487Smckusick cache_enter(ndp) 16337487Smckusick register struct nameidata *ndp; 16437487Smckusick { 16537487Smckusick register struct namecache *ncp; 16637487Smckusick union nchash *nhp; 16737487Smckusick 16838768Smckusick if (!doingcache) 16938768Smckusick return; 17037487Smckusick /* 17137487Smckusick * Free the cache slot at head of lru chain. 17237487Smckusick */ 17340881Smckusick if (numcache < desiredvnodes) { 17440881Smckusick ncp = (struct namecache *) 175*45117Smckusick malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); 17640881Smckusick bzero((char *)ncp, sizeof *ncp); 17740881Smckusick numcache++; 17840881Smckusick } else if (ncp = nchhead) { 17937487Smckusick /* remove from lru chain */ 18037487Smckusick *ncp->nc_prev = ncp->nc_nxt; 18137487Smckusick if (ncp->nc_nxt) 18237487Smckusick ncp->nc_nxt->nc_prev = ncp->nc_prev; 18337487Smckusick else 18437487Smckusick nchtail = ncp->nc_prev; 18538768Smckusick /* remove from old hash chain */ 18638768Smckusick remque(ncp); 18740881Smckusick } else 18840881Smckusick return; 18940881Smckusick /* grab the vnode we just found */ 19040881Smckusick ncp->nc_vp = ndp->ni_vp; 19140881Smckusick if (ndp->ni_vp) 19240881Smckusick ncp->nc_vpid = ndp->ni_vp->v_id; 19340881Smckusick else 19440881Smckusick ncp->nc_vpid = 0; 19540881Smckusick /* fill in cache info */ 19640881Smckusick ncp->nc_dvp = ndp->ni_dvp; 19740881Smckusick ncp->nc_dvpid = ndp->ni_dvp->v_id; 19840881Smckusick ncp->nc_nlen = ndp->ni_namelen; 19940881Smckusick bcopy(ndp->ni_ptr, ncp->nc_name, (unsigned)ncp->nc_nlen); 20040881Smckusick /* link at end of lru chain */ 20140881Smckusick ncp->nc_nxt = NULL; 20240881Smckusick ncp->nc_prev = nchtail; 20340881Smckusick *nchtail = ncp; 20440881Smckusick nchtail = &ncp->nc_nxt; 20540881Smckusick /* and insert on hash chain */ 20640881Smckusick nhp = &nchashtbl[ndp->ni_hash & nchash]; 20740881Smckusick insque(ncp, nhp); 20837487Smckusick } 20937487Smckusick 21037487Smckusick /* 21140881Smckusick * Name cache initialization, from vfs_init() when we are booting 21237487Smckusick */ 21337487Smckusick nchinit() 21437487Smckusick { 21537487Smckusick register union nchash *nchp; 21640881Smckusick long nchashsize; 21737487Smckusick 21837487Smckusick nchhead = 0; 21937487Smckusick nchtail = &nchhead; 22040881Smckusick nchashsize = roundup((desiredvnodes + 1) * sizeof *nchp / 2, 22140881Smckusick NBPG * CLSIZE); 222*45117Smckusick nchashtbl = (union nchash *)malloc((u_long)nchashsize, 223*45117Smckusick M_CACHE, M_WAITOK); 22440881Smckusick for (nchash = 1; nchash <= nchashsize / sizeof *nchp; nchash <<= 1) 22540881Smckusick /* void */; 22640881Smckusick nchash = (nchash >> 1) - 1; 22740881Smckusick for (nchp = &nchashtbl[nchash]; nchp >= nchashtbl; nchp--) { 22837487Smckusick nchp->nch_head[0] = nchp; 22937487Smckusick nchp->nch_head[1] = nchp; 23037487Smckusick } 23137487Smckusick } 23237487Smckusick 23337487Smckusick /* 23437487Smckusick * Cache flush, a particular vnode; called when a vnode is renamed to 23538768Smckusick * hide entries that would now be invalid 23637487Smckusick */ 23737487Smckusick cache_purge(vp) 23838768Smckusick struct vnode *vp; 23937487Smckusick { 24040881Smckusick union nchash *nhp; 24138768Smckusick struct namecache *ncp; 24237487Smckusick 24338768Smckusick vp->v_id = ++nextvnodeid; 24438768Smckusick if (nextvnodeid != 0) 24538768Smckusick return; 24640881Smckusick for (nhp = &nchashtbl[nchash]; nhp >= nchashtbl; nhp--) { 24740881Smckusick for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp; 24840881Smckusick ncp = ncp->nc_forw) { 24940881Smckusick ncp->nc_vpid = 0; 25040881Smckusick ncp->nc_dvpid = 0; 25140881Smckusick } 25237487Smckusick } 25338768Smckusick vp->v_id = ++nextvnodeid; 25437487Smckusick } 25537487Smckusick 25637487Smckusick /* 25737487Smckusick * Cache flush, a whole filesystem; called when filesys is umounted to 25837487Smckusick * remove entries that would now be invalid 25937487Smckusick * 26037487Smckusick * The line "nxtcp = nchhead" near the end is to avoid potential problems 26137487Smckusick * if the cache lru chain is modified while we are dumping the 26237487Smckusick * inode. This makes the algorithm O(n^2), but do you think I care? 26337487Smckusick */ 26437487Smckusick cache_purgevfs(mp) 265*45117Smckusick struct mount *mp; 26637487Smckusick { 26737487Smckusick register struct namecache *ncp, *nxtcp; 26837487Smckusick 26937487Smckusick for (ncp = nchhead; ncp; ncp = nxtcp) { 27037487Smckusick nxtcp = ncp->nc_nxt; 27138768Smckusick if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) 27237487Smckusick continue; 27337487Smckusick /* free the resources we had */ 27437487Smckusick ncp->nc_vp = NULL; 27538768Smckusick ncp->nc_dvp = NULL; 27637487Smckusick remque(ncp); /* remove entry from its hash chain */ 27737487Smckusick ncp->nc_forw = ncp; /* and make a dummy one */ 27837487Smckusick ncp->nc_back = ncp; 27937487Smckusick /* delete this entry from LRU chain */ 28037487Smckusick *ncp->nc_prev = nxtcp; 28137487Smckusick if (nxtcp) 28237487Smckusick nxtcp->nc_prev = ncp->nc_prev; 28337487Smckusick else 28437487Smckusick nchtail = ncp->nc_prev; 28537487Smckusick /* cause rescan of list, it may have altered */ 28637487Smckusick nxtcp = nchhead; 28737487Smckusick /* put the now-free entry at head of LRU */ 28837487Smckusick ncp->nc_nxt = nxtcp; 28937487Smckusick ncp->nc_prev = &nchhead; 29037487Smckusick nxtcp->nc_prev = &ncp->nc_nxt; 29137487Smckusick nchhead = ncp; 29237487Smckusick } 29337487Smckusick } 294