1
0
mirror of https://github.com/openbsd/src.git synced 2024-12-22 16:42:56 -08:00
openbsd-src/sys/kern/vfs_cache.c

473 lines
12 KiB
C
Raw Permalink Normal View History

/* $OpenBSD: vfs_cache.c,v 1.58 2022/08/14 01:58:28 jsg Exp $ */
1996-03-03 09:19:36 -08:00
/* $NetBSD: vfs_cache.c,v 1.13 1996/02/04 02:18:09 christos Exp $ */
1995-10-18 01:37:01 -07:00
/*
* 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
1995-10-18 01:37:01 -07:00
* 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/vnode.h>
#include <sys/lock.h>
1995-10-18 01:37:01 -07:00
#include <sys/namei.h>
#include <sys/errno.h>
#include <sys/pool.h>
1995-10-18 01:37:01 -07:00
/*
* TODO: namecache access should really be locked.
*/
1995-10-18 01:37:01 -07:00
/*
* For simplicity (and economy of storage), names longer than
* a maximum length of NAMECACHE_MAXLEN are not cached; they occur
1995-10-18 01:37:01 -07:00
* 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.
*/
/*
2004-10-04 05:03:45 -07:00
* Structures associated with name caching.
1995-10-18 01:37:01 -07:00
*/
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 */
1995-10-18 01:37:01 -07:00
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);
}
1995-10-18 01:37:01 -07:00
/*
* 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.
1995-10-18 01:37:01 -07:00
*/
int
cache_lookup(struct vnode *dvp, struct vnode **vpp,
struct componentname *cnp)
1995-10-18 01:37:01 -07:00
{
struct namecache *ncp;
struct namecache n;
struct vnode *vp;
u_long vpid;
int error;
1995-10-18 01:37:01 -07:00
*vpp = NULL;
1995-10-18 01:37:01 -07:00
if (!doingcache) {
cnp->cn_flags &= ~MAKEENTRY;
return (-1);
1995-10-18 01:37:01 -07:00
}
if (cnp->cn_namelen > NAMECACHE_MAXLEN) {
1995-10-18 01:37:01 -07:00
nchstats.ncs_long++;
cnp->cn_flags &= ~MAKEENTRY;
return (-1);
1995-10-18 01:37:01 -07:00
}
/* 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) {
1995-10-18 01:37:01 -07:00
nchstats.ncs_miss++;
return (-1);
1995-10-18 01:37:01 -07:00
}
if ((cnp->cn_flags & MAKEENTRY) == 0) {
nchstats.ncs_badhits++;
goto remove;
1995-10-18 01:37:01 -07:00
} else if (ncp->nc_vp == NULL) {
if (cnp->cn_nameiop != CREATE ||
(cnp->cn_flags & ISLASTCN) == 0) {
1995-10-18 01:37:01 -07:00
nchstats.ncs_neghits++;
/*
* Move this slot to end of the negative LRU chain,
1995-10-18 01:37:01 -07:00
*/
if (TAILQ_NEXT(ncp, nc_neg) != NULL) {
TAILQ_REMOVE(&nclruneghead, ncp, nc_neg);
TAILQ_INSERT_TAIL(&nclruneghead, ncp,
nc_neg);
1995-10-18 01:37:01 -07:00
}
return (ENOENT);
} else {
nchstats.ncs_badhits++;
goto remove;
1995-10-18 01:37:01 -07:00
}
} 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;
}
1995-10-18 01:37:01 -07:00
} else {
error = vget(vp, LK_EXCLUSIVE);
1995-10-18 01:37:01 -07:00
/*
* If the above vget() failed or either of LOCKPARENT or
* ISLASTCN is set, unlock the directory vnode.
1995-10-18 01:37:01 -07:00
*/
if (error || (~cnp->cn_flags & (LOCKPARENT|ISLASTCN)) != 0) {
VOP_UNLOCK(dvp);
cnp->cn_flags |= PDIRUNLOCK;
1995-10-18 01:37:01 -07:00
}
}
/*
* 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;
}
1995-10-18 01:37:01 -07:00
return (-1);
}
nchstats.ncs_goodhits++;
*vpp = vp;
return (0);
remove:
1995-10-18 01:37:01 -07:00
/*
* 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);
1995-10-18 01:37:01 -07:00
}
/*
* 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);
}
1995-10-18 01:37:01 -07:00
/*
* Add an entry to the cache
*/
1996-03-03 09:19:36 -08:00
void
cache_enter(struct vnode *dvp, struct vnode *vp, struct componentname *cnp)
1995-10-18 01:37:01 -07:00
{
struct namecache *ncp, *lncp;
1995-10-18 01:37:01 -07:00
if (!doingcache || cnp->cn_namelen > NAMECACHE_MAXLEN)
1995-10-18 01:37:01 -07:00
return;
1995-10-18 01:37:01 -07:00
/*
* allocate, or recycle (free and allocate) an ncp.
1995-10-18 01:37:01 -07:00
*/
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);
1995-10-18 01:37:01 -07:00
/* grab the vnode we just found */
ncp->nc_vp = vp;
if (vp)
ncp->nc_vpid = vp->v_id;
1995-10-18 01:37:01 -07:00
/* fill in cache info */
ncp->nc_dvp = dvp;
ncp->nc_dvpid = dvp->v_id;
ncp->nc_nlen = cnp->cn_namelen;
2014-12-09 18:44:46 -08:00
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;
1995-10-18 01:37:01 -07:00
}
1995-10-18 01:37:01 -07:00
/*
* Name cache initialization, from vfs_init() when we are booting
*/
1996-03-03 09:19:36 -08:00
void
nchinit(void)
1995-10-18 01:37:01 -07:00
{
TAILQ_INIT(&nclruhead);
TAILQ_INIT(&nclruneghead);
pool_init(&nch_pool, sizeof(struct namecache), 0, IPL_NONE, PR_WAITOK,
"nchpl", NULL);
1995-10-18 01:37:01 -07:00
}
/*
* Cache flush, a particular vnode; called when a vnode is renamed to
* hide entries that would now be invalid
*/
1996-03-03 09:19:36 -08:00
void
cache_purge(struct vnode *vp)
1995-10-18 01:37:01 -07:00
{
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 */
1995-10-18 01:37:01 -07:00
vp->v_id = ++nextvnodeid;
if (vp->v_id == 0)
vp->v_id = ++nextvnodeid;
1995-10-18 01:37:01 -07:00
}
/*
* Cache flush, a whole filesystem; called when filesys is umounted to
* remove entries that would now be invalid
*/
1996-03-03 09:19:36 -08:00
void
cache_purgevfs(struct mount *mp)
1995-10-18 01:37:01 -07:00
{
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)
1995-10-18 01:37:01 -07:00
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);
1995-10-18 01:37:01 -07:00
}
}