Edit
IABSD.fr/src/sys/kern/vfs_cache.c
kn
- sys/kern/vfs_cache.c
-
/* $OpenBSD: vfs_cache.c,v 1.57 2018/06/04 19:42:54 kn Exp $ */ /* $NetBSD: vfs_cache.c,v 1.13 1996/02/04 02:18:09 christos Exp $ */ /* * Copyright (c) 1989, 1993 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * @(#)vfs_cache.c 8.3 (Berkeley) 8/22/94 */ #include <sys/param.h> #include <sys/systm.h> #include <sys/time.h> #include <sys/mount.h> #include <sys/vnode.h> #include <sys/lock.h> #include <sys/namei.h> #include <sys/errno.h> #include <sys/pool.h> /* * TODO: namecache access should really be locked. */ /* * For simplicity (and economy of storage), names longer than * a maximum length of NAMECACHE_MAXLEN are not cached; they occur * infrequently in any case, and are almost never of interest. * * Upon reaching the last segment of a path, if the reference * is for DELETE, or NOCACHE is set (rewrite), and the * name is located in the cache, it will be dropped. */ /* * Structures associated with name caching. */ long numcache; /* total number of cache entries allocated */ long numneg; /* number of negative cache entries */ TAILQ_HEAD(, namecache) nclruhead; /* Regular Entry LRU chain */ TAILQ_HEAD(, namecache) nclruneghead; /* Negative Entry LRU chain */ struct nchstats nchstats; /* cache effectiveness statistics */ int doingcache = 1; /* 1 => enable the cache */ struct pool nch_pool; void cache_zap(struct namecache *); u_long nextvnodeid; static inline int namecache_compare(const struct namecache *n1, const struct namecache *n2) { if (n1->nc_nlen == n2->nc_nlen) return (memcmp(n1->nc_name, n2->nc_name, n1->nc_nlen)); else return (n1->nc_nlen - n2->nc_nlen); } RBT_PROTOTYPE(namecache_rb_cache, namecache, n_rbcache, namecache_compare); RBT_GENERATE(namecache_rb_cache, namecache, n_rbcache, namecache_compare); void cache_tree_init(struct namecache_rb_cache *tree) { RBT_INIT(namecache_rb_cache, tree); } /* * blow away a namecache entry */ void cache_zap(struct namecache *ncp) { struct vnode *dvp = NULL; if (ncp->nc_vp != NULL) { TAILQ_REMOVE(&nclruhead, ncp, nc_lru); numcache--; } else { TAILQ_REMOVE(&nclruneghead, ncp, nc_neg); numneg--; } if (ncp->nc_dvp) { RBT_REMOVE(namecache_rb_cache, &ncp->nc_dvp->v_nc_tree, ncp); if (RBT_EMPTY(namecache_rb_cache, &ncp->nc_dvp->v_nc_tree)) dvp = ncp->nc_dvp; } if (ncp->nc_vp && (ncp->nc_vpid == ncp->nc_vp->v_id)) { if (ncp->nc_vp != ncp->nc_dvp && ncp->nc_vp->v_type == VDIR && (ncp->nc_nlen > 2 || (ncp->nc_nlen > 1 && ncp->nc_name[1] != '.') || (ncp->nc_nlen > 0 && ncp->nc_name[0] != '.'))) { TAILQ_REMOVE(&ncp->nc_vp->v_cache_dst, ncp, nc_me); } } pool_put(&nch_pool, ncp); if (dvp) vdrop(dvp); } /* * Look for a name in the cache. * dvp points to the directory to search. The componentname cnp holds * the information on the entry being sought, such as its length * and its name. If the lookup succeeds, vpp is set to point to the vnode * and an error of 0 is returned. If the lookup determines the name does * not exist (negative caching) an error of ENOENT is returned. If the * lookup fails, an error of -1 is returned. */ int cache_lookup(struct vnode *dvp, struct vnode **vpp, struct componentname *cnp) { struct namecache *ncp; struct namecache n; struct vnode *vp; u_long vpid; int error; *vpp = NULL; if (!doingcache) { cnp->cn_flags &= ~MAKEENTRY; return (-1); } if (cnp->cn_namelen > NAMECACHE_MAXLEN) { nchstats.ncs_long++; cnp->cn_flags &= ~MAKEENTRY; return (-1); } /* lookup in directory vnode's redblack tree */ n.nc_nlen = cnp->cn_namelen; memcpy(n.nc_name, cnp->cn_nameptr, n.nc_nlen); ncp = RBT_FIND(namecache_rb_cache, &dvp->v_nc_tree, &n); if (ncp == NULL) { nchstats.ncs_miss++; return (-1); } if ((cnp->cn_flags & MAKEENTRY) == 0) { nchstats.ncs_badhits++; goto remove; } else if (ncp->nc_vp == NULL) { if (cnp->cn_nameiop != CREATE || (cnp->cn_flags & ISLASTCN) == 0) { nchstats.ncs_neghits++; /* * Move this slot to end of the negative LRU chain, */ if (TAILQ_NEXT(ncp, nc_neg) != NULL) { TAILQ_REMOVE(&nclruneghead, ncp, nc_neg); TAILQ_INSERT_TAIL(&nclruneghead, ncp, nc_neg); } return (ENOENT); } else { nchstats.ncs_badhits++; goto remove; } } else if (ncp->nc_vpid != ncp->nc_vp->v_id) { nchstats.ncs_falsehits++; goto remove; } /* * Move this slot to end of the regular LRU chain. */ if (TAILQ_NEXT(ncp, nc_lru) != NULL) { TAILQ_REMOVE(&nclruhead, ncp, nc_lru); TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); } vp = ncp->nc_vp; vpid = vp->v_id; if (vp == dvp) { /* lookup on "." */ vref(dvp); error = 0; } else if (cnp->cn_flags & ISDOTDOT) { VOP_UNLOCK(dvp); cnp->cn_flags |= PDIRUNLOCK; error = vget(vp, LK_EXCLUSIVE); /* * If the above vget() succeeded and both LOCKPARENT and * ISLASTCN is set, lock the directory vnode as well. */ if (!error && (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) == 0) { if ((error = vn_lock(dvp, LK_EXCLUSIVE)) != 0) { vput(vp); return (error); } cnp->cn_flags &= ~PDIRUNLOCK; } } else { error = vget(vp, LK_EXCLUSIVE); /* * If the above vget() failed or either of LOCKPARENT or * ISLASTCN is set, unlock the directory vnode. */ if (error || (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) { VOP_UNLOCK(dvp); cnp->cn_flags |= PDIRUNLOCK; } } /* * Check that the lock succeeded, and that the capability number did * not change while we were waiting for the lock. */ if (error || vpid != vp->v_id) { if (!error) { vput(vp); nchstats.ncs_falsehits++; } else nchstats.ncs_badhits++; /* * The parent needs to be locked when we return to VOP_LOOKUP(). * The `.' case here should be extremely rare (if it can happen * at all), so we don't bother optimizing out the unlock/relock. */ if (vp == dvp || error || (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) { if ((error = vn_lock(dvp, LK_EXCLUSIVE)) != 0) return (error); cnp->cn_flags &= ~PDIRUNLOCK; } return (-1); } nchstats.ncs_goodhits++; *vpp = vp; return (0); remove: /* * Last component and we are renaming or deleting, * the cache entry is invalid, or otherwise don't * want cache entry to exist. */ cache_zap(ncp); return (-1); } /* * Scan cache looking for name of directory entry pointing at vp. * * Fill in dvpp. * * If bufp is non-NULL, also place the name in the buffer which starts * at bufp, immediately before *bpp, and move bpp backwards to point * at the start of it. (Yes, this is a little baroque, but it's done * this way to cater to the whims of getcwd). * * Returns 0 on success, -1 on cache miss, positive errno on failure. * * TODO: should we return *dvpp locked? */ int cache_revlookup(struct vnode *vp, struct vnode **dvpp, char **bpp, char *bufp) { struct namecache *ncp; struct vnode *dvp = NULL; char *bp; if (!doingcache) goto out; TAILQ_FOREACH(ncp, &vp->v_cache_dst, nc_me) { dvp = ncp->nc_dvp; if (dvp && dvp != vp && ncp->nc_dvpid == dvp->v_id) goto found; } goto miss; found: #ifdef DIAGNOSTIC if (ncp->nc_nlen == 1 && ncp->nc_name[0] == '.') panic("cache_revlookup: found entry for ."); if (ncp->nc_nlen == 2 && ncp->nc_name[0] == '.' && ncp->nc_name[1] == '.') panic("cache_revlookup: found entry for .."); #endif nchstats.ncs_revhits++; if (bufp != NULL) { bp = *bpp; bp -= ncp->nc_nlen; if (bp <= bufp) { *dvpp = NULL; return (ERANGE); } memcpy(bp, ncp->nc_name, ncp->nc_nlen); *bpp = bp; } *dvpp = dvp; /* * XXX: Should we vget() here to have more * consistent semantics with cache_lookup()? */ return (0); miss: nchstats.ncs_revmiss++; out: *dvpp = NULL; return (-1); } /* * Add an entry to the cache */ void cache_enter(struct vnode *dvp, struct vnode *vp, struct componentname *cnp) { struct namecache *ncp, *lncp; if (!doingcache || cnp->cn_namelen > NAMECACHE_MAXLEN) return; /* * allocate, or recycle (free and allocate) an ncp. */ if (numcache >= initialvnodes) { if ((ncp = TAILQ_FIRST(&nclruhead)) != NULL) cache_zap(ncp); else if ((ncp = TAILQ_FIRST(&nclruneghead)) != NULL) cache_zap(ncp); else panic("wtf? leak?"); } ncp = pool_get(&nch_pool, PR_WAITOK|PR_ZERO); /* grab the vnode we just found */ ncp->nc_vp = vp; if (vp) ncp->nc_vpid = vp->v_id; /* fill in cache info */ ncp->nc_dvp = dvp; ncp->nc_dvpid = dvp->v_id; ncp->nc_nlen = cnp->cn_namelen; memcpy(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen); if (RBT_EMPTY(namecache_rb_cache, &dvp->v_nc_tree)) { vhold(dvp); } if ((lncp = RBT_INSERT(namecache_rb_cache, &dvp->v_nc_tree, ncp)) != NULL) { /* someone has raced us and added a different entry * for the same vnode (different ncp) - we don't need * this entry, so free it and we are done. */ pool_put(&nch_pool, ncp); /* we know now dvp->v_nc_tree is not empty, no need * to vdrop here */ goto done; } if (vp) { TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); numcache++; /* don't put . or .. in the reverse map */ if (vp != dvp && vp->v_type == VDIR && (ncp->nc_nlen > 2 || (ncp->nc_nlen > 1 && ncp->nc_name[1] != '.') || (ncp->nc_nlen > 0 && ncp->nc_name[0] != '.'))) TAILQ_INSERT_TAIL(&vp->v_cache_dst, ncp, nc_me); } else { TAILQ_INSERT_TAIL(&nclruneghead, ncp, nc_neg); numneg++; } if (numneg > initialvnodes) { if ((ncp = TAILQ_FIRST(&nclruneghead)) != NULL) cache_zap(ncp); } done: return; } /* * Name cache initialization, from vfs_init() when we are booting */ void nchinit(void) { TAILQ_INIT(&nclruhead); TAILQ_INIT(&nclruneghead); pool_init(&nch_pool, sizeof(struct namecache), 0, IPL_NONE, PR_WAITOK, "nchpl", NULL); } /* * Cache flush, a particular vnode; called when a vnode is renamed to * hide entries that would now be invalid */ void cache_purge(struct vnode *vp) { struct namecache *ncp; /* We should never have destinations cached for a non-VDIR vnode. */ KASSERT(vp->v_type == VDIR || TAILQ_EMPTY(&vp->v_cache_dst)); while ((ncp = TAILQ_FIRST(&vp->v_cache_dst))) cache_zap(ncp); while ((ncp = RBT_ROOT(namecache_rb_cache, &vp->v_nc_tree))) cache_zap(ncp); /* XXX this blows goats */ vp->v_id = ++nextvnodeid; if (vp->v_id == 0) vp->v_id = ++nextvnodeid; } /* * Cache flush, a whole filesystem; called when filesys is umounted to * remove entries that would now be invalid */ void cache_purgevfs(struct mount *mp) { struct namecache *ncp, *nxtcp; /* whack the regular entries */ TAILQ_FOREACH_SAFE(ncp, &nclruhead, nc_lru, nxtcp) { if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) continue; /* free the resources we had */ cache_zap(ncp); } /* whack the negative entries */ TAILQ_FOREACH_SAFE(ncp, &nclruneghead, nc_neg, nxtcp) { if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) continue; /* free the resources we had */ cache_zap(ncp); } }