diff options
author | marius eriksen <marius@cvs.openbsd.org> | 2005-05-26 22:40:54 +0000 |
---|---|---|
committer | marius eriksen <marius@cvs.openbsd.org> | 2005-05-26 22:40:54 +0000 |
commit | 8fe3257ed62e0ad8694a7d297ab533508db64c73 (patch) | |
tree | dd20f56566955eba654abe846d5081d66796dfcf /sys | |
parent | 21aa28c09910dc1ea64699bda2eb5f37bdcf9fd3 (diff) |
add a reverse name mapping into the namecache. (vnode->name)
this will help speedup getcwd (coming soon).
ok pedro@
Diffstat (limited to 'sys')
-rw-r--r-- | sys/kern/vfs_cache.c | 149 | ||||
-rw-r--r-- | sys/sys/namei.h | 32 |
2 files changed, 146 insertions, 35 deletions
diff --git a/sys/kern/vfs_cache.c b/sys/kern/vfs_cache.c index 64201bfe1f1..9e232b74240 100644 --- a/sys/kern/vfs_cache.c +++ b/sys/kern/vfs_cache.c @@ -1,4 +1,4 @@ -/* $OpenBSD: vfs_cache.c,v 1.14 2005/03/04 11:43:37 pedro Exp $ */ +/* $OpenBSD: vfs_cache.c,v 1.15 2005/05/26 22:40:53 marius Exp $ */ /* $NetBSD: vfs_cache.c,v 1.13 1996/02/04 02:18:09 christos Exp $ */ /* @@ -44,6 +44,10 @@ #include <sys/hash.h> /* + * TODO: namecache access should really be locked. + */ + +/* * Name caching works as follows: * * Names found by directory scans are retained in a cache @@ -70,6 +74,14 @@ long numcache; /* number of cache entries allocated */ TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */ struct nchstats nchstats; /* cache effectiveness statistics */ +LIST_HEAD(ncvhashhead, namecache) *ncvhashtbl; +u_long ncvhash; /* size of hash table - 1 */ + +#define NCHASH(dvp, cnp) \ + hash32_buf(&(dvp)->v_id, sizeof((dvp)->v_id), (cnp)->cn_hash) &nchash + +#define NCVHASH(vp) (vp)->v_id & ncvhash + int doingcache = 1; /* 1 => enable the cache */ struct pool nch_pool; @@ -93,10 +105,7 @@ u_long nextvnodeid; * is returned. */ int -cache_lookup(dvp, vpp, cnp) - struct vnode *dvp; - struct vnode **vpp; - struct componentname *cnp; +cache_lookup(struct vnode *dvp, struct vnode **vpp, struct componentname *cnp) { struct namecache *ncp; struct nchashhead *ncpp; @@ -117,8 +126,7 @@ cache_lookup(dvp, vpp, cnp) return (-1); } - ncpp = &nchashtbl[ - hash32_buf(&dvp->v_id, sizeof(dvp->v_id), cnp->cn_hash) & nchash]; + ncpp = &nchashtbl[NCHASH(dvp, cnp)]; LIST_FOREACH(ncp, ncpp, nc_hash) { if (ncp->nc_dvp == dvp && ncp->nc_dvpid == dvp->v_id && @@ -126,7 +134,7 @@ cache_lookup(dvp, vpp, cnp) !memcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) break; } - if (ncp == 0) { + if (ncp == NULL) { nchstats.ncs_miss++; return (-1); } @@ -235,27 +243,104 @@ remove: TAILQ_REMOVE(&nclruhead, ncp, nc_lru); LIST_REMOVE(ncp, nc_hash); ncp->nc_hash.le_prev = NULL; -#if 0 + if (ncp->nc_vhash.le_prev != NULL) { LIST_REMOVE(ncp, nc_vhash); ncp->nc_vhash.le_prev = NULL; } -#endif + TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); 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; + struct ncvhashhead *nvcpp; + char *bp; + + if (!doingcache) + goto out; + + nvcpp = &ncvhashtbl[NCVHASH(vp)]; + + LIST_FOREACH(ncp, nvcpp, nc_vhash) { + if (ncp->nc_vp == vp && + ncp->nc_vpid == vp->v_id && + (dvp = ncp->nc_dvp) != NULL && + /* avoid pesky '.' entries.. */ + dvp != vp) { + +#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()? + * + * For MP safety it might be necessary to do + * this here, while also protecting hash + * tables themselves to provide some sort of + * sane inter locking. + */ + return (0); + } + } + nchstats.ncs_revmiss++; + + out: + *dvpp = NULL; + return (-1); +} + +/* * Add an entry to the cache */ void -cache_enter(dvp, vp, cnp) - struct vnode *dvp; - struct vnode *vp; - struct componentname *cnp; +cache_enter(struct vnode *dvp, struct vnode *vp, struct componentname *cnp) { - register struct namecache *ncp; - register struct nchashhead *ncpp; + struct namecache *ncp; + struct nchashhead *ncpp; + struct ncvhashhead *nvcpp; if (!doingcache || cnp->cn_namelen > NCHNAMLEN) return; @@ -292,9 +377,24 @@ cache_enter(dvp, vp, cnp) ncp->nc_nlen = cnp->cn_namelen; bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); - ncpp = &nchashtbl[ - hash32_buf(&dvp->v_id, sizeof(dvp->v_id), cnp->cn_hash) & nchash]; + ncpp = &nchashtbl[NCHASH(dvp, cnp)]; LIST_INSERT_HEAD(ncpp, ncp, nc_hash); + + /* + * Create reverse-cache entries (used in getcwd) for + * directories. + */ + + ncp->nc_vhash.le_prev = 0; + ncp->nc_vhash.le_next = 0; + + if (vp && 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] != '.'))) { + nvcpp = &ncvhashtbl[NCVHASH(vp)]; + LIST_INSERT_HEAD(nvcpp, ncp, nc_vhash); + } } /* @@ -306,6 +406,7 @@ nchinit() TAILQ_INIT(&nclruhead); nchashtbl = hashinit(desiredvnodes, M_CACHE, M_WAITOK, &nchash); + ncvhashtbl = hashinit(desiredvnodes/8, M_CACHE, M_WAITOK, &ncvhash); pool_init(&nch_pool, sizeof(struct namecache), 0, 0, 0, "nchpl", &pool_allocator_nointr); } @@ -315,8 +416,7 @@ nchinit() * hide entries that would now be invalid */ void -cache_purge(vp) - struct vnode *vp; +cache_purge(struct vnode *vp) { struct namecache *ncp; struct nchashhead *ncpp; @@ -342,10 +442,9 @@ cache_purge(vp) * inode. This makes the algorithm O(n^2), but do you think I care? */ void -cache_purgevfs(mp) - struct mount *mp; +cache_purgevfs(struct mount *mp) { - register struct namecache *ncp, *nxtcp; + struct namecache *ncp, *nxtcp; for (ncp = TAILQ_FIRST(&nclruhead); ncp != TAILQ_END(&nclruhead); ncp = nxtcp) { @@ -361,6 +460,10 @@ cache_purgevfs(mp) LIST_REMOVE(ncp, nc_hash); ncp->nc_hash.le_prev = 0; } + if (ncp->nc_vhash.le_prev != 0) { + LIST_REMOVE(ncp, nc_vhash); + ncp->nc_vhash.le_prev = 0; + } /* cause rescan of list, it may have altered */ nxtcp = TAILQ_FIRST(&nclruhead); TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); diff --git a/sys/sys/namei.h b/sys/sys/namei.h index 681c2c66d5f..83027454fb2 100644 --- a/sys/sys/namei.h +++ b/sys/sys/namei.h @@ -1,4 +1,4 @@ -/* $OpenBSD: namei.h,v 1.13 2004/05/14 04:00:33 tedu Exp $ */ +/* $OpenBSD: namei.h,v 1.14 2005/05/26 22:40:52 marius Exp $ */ /* $NetBSD: namei.h,v 1.11 1996/02/09 18:25:20 christos Exp $ */ /* @@ -161,6 +161,7 @@ struct nameidata { struct namecache { LIST_ENTRY(namecache) nc_hash; /* hash chain */ + LIST_ENTRY(namecache) nc_vhash; /* (reverse) directory hash chain */ TAILQ_ENTRY(namecache) nc_lru; /* LRU chain */ struct vnode *nc_dvp; /* vnode of parent of name */ u_long nc_dvpid; /* capability number of nc_dvp */ @@ -179,6 +180,7 @@ int relookup(struct vnode *dvp, struct vnode **vpp, void cache_purge(struct vnode *); int cache_lookup(struct vnode *, struct vnode **, struct componentname *); void cache_enter(struct vnode *, struct vnode *, struct componentname *); +int cache_revlookup(struct vnode *, struct vnode **, char **, char *); void nchinit(void); struct mount; void cache_purgevfs(struct mount *); @@ -199,6 +201,8 @@ struct nchstats { long ncs_long; /* long names that ignore cache */ long ncs_pass2; /* names found with passes == 2 */ long ncs_2passes; /* number of times we attempt it */ + long ncs_revhits; /* reverse-cache hits */ + long ncs_revmiss; /* reverse-cache misses */ }; /* These sysctl names are only really used by sysctl(8) */ @@ -210,17 +214,21 @@ struct nchstats { #define KERN_NCHSTATS_LONG 6 #define KERN_NCHSTATS_PASS2 7 #define KERN_NCHSTATS_2PASSES 8 -#define KERN_NCHSTATS_MAXID 9 +#define KERN_NCHSTATS_REVHITS 9 +#define KERN_NCHSTATS_REVMISS 10 +#define KERN_NCHSTATS_MAXID 11 -#define CTL_KERN_NCHSTATS_NAMES { \ - { 0, 0 }, \ - { "good_hits", CTLTYPE_INT }, \ - { "negative_hits", CTLTYPE_INT }, \ - { "bad_hits", CTLTYPE_INT }, \ - { "false_hits", CTLTYPE_INT }, \ - { "misses", CTLTYPE_INT }, \ - { "long_names", CTLTYPE_INT }, \ - { "pass2", CTLTYPE_INT }, \ - { "2passes", CTLTYPE_INT }, \ +#define CTL_KERN_NCHSTATS_NAMES { \ + { 0, 0 }, \ + { "good_hits", CTLTYPE_INT }, \ + { "negative_hits", CTLTYPE_INT }, \ + { "bad_hits", CTLTYPE_INT }, \ + { "false_hits", CTLTYPE_INT }, \ + { "misses", CTLTYPE_INT }, \ + { "long_names", CTLTYPE_INT }, \ + { "pass2", CTLTYPE_INT }, \ + { "2passes", CTLTYPE_INT }, \ + { "ncs_revhits", CTLTYPE_INT }, \ + { "nfs_revmiss", CTLTYPE_INT }, \ } #endif /* !_SYS_NAMEI_H_ */ |