* Copyright (c) 1989, 1993
* The Regents of the University of California. All rights reserved.
* %sccs.include.redist.c%
* @(#)vfs_cache.c 8.1 (Berkeley) %G%
* Name caching works as follows:
* Names found by directory scans are retained in a cache
* for future reference. It is managed LRU, so frequently
* used names will hang around. Cache is indexed by hash value
* obtained from (vp, name) where vp refers to the directory
* For simplicity (and economy of storage), names longer than
* a maximum length of NCHNAMLEN 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 cacheing.
struct namecache
**nchashtbl
;
u_long nchash
; /* size of hash table - 1 */
long numcache
; /* number of cache entries allocated */
struct namecache
*nchhead
, **nchtail
; /* LRU chain pointers */
struct nchstats nchstats
; /* cache effectiveness statistics */
int doingcache
= 1; /* 1 => enable the cache */
* Look for a the name in the cache. We don't do this
* if the segment name is long, simply so the cache can avoid
* holding long names (which would either waste space, or
* add greatly to the complexity).
* Lookup is called with ni_dvp pointing to the directory to search,
* ni_ptr pointing to the name of the entry being sought, ni_namelen
* tells the length of the name, and ni_hash contains a hash of
* the name. If the lookup succeeds, the vnode is returned in ni_vp
* and a status of -1 is returned. If the lookup determines that
* the name does not exist (negative cacheing), a status of ENOENT
* is returned. If the lookup fails, a status of zero is returned.
cache_lookup(dvp
, vpp
, cnp
)
struct componentname
*cnp
;
register struct namecache
*ncp
, *ncq
, **ncpp
;
if (cnp
->cn_namelen
> NCHNAMLEN
) {
cnp
->cn_flags
&= ~MAKEENTRY
;
ncpp
= &nchashtbl
[cnp
->cn_hash
& nchash
];
for (ncp
= *ncpp
; ncp
; ncp
= ncp
->nc_forw
) {
if (ncp
->nc_dvp
== dvp
&&
ncp
->nc_dvpid
== dvp
->v_id
&&
ncp
->nc_nlen
== cnp
->cn_namelen
&&
!bcmp(ncp
->nc_name
, cnp
->cn_nameptr
, (u_int
)ncp
->nc_nlen
))
if (!(cnp
->cn_flags
& MAKEENTRY
)) {
} else if (ncp
->nc_vp
== NULL
) {
if (cnp
->cn_nameiop
!= CREATE
) {
* Move this slot to end of LRU chain,
/* remove from LRU chain */
*ncp
->nc_prev
= ncp
->nc_nxt
;
ncp
->nc_nxt
->nc_prev
= ncp
->nc_prev
;
/* and replace at end of it */
} else if (ncp
->nc_vpid
!= ncp
->nc_vp
->v_id
) {
nchstats
.ncs_falsehits
++;
* move this slot to end of LRU chain, if not already there
/* remove from LRU chain */
*ncp
->nc_prev
= ncp
->nc_nxt
;
ncp
->nc_nxt
->nc_prev
= ncp
->nc_prev
;
/* and replace at end of it */
* Last component and we are renaming or deleting,
* the cache entry is invalid, or otherwise don't
* want cache entry to exist.
/* remove from LRU chain */
ncq
->nc_prev
= ncp
->nc_prev
;
/* remove from hash chain */
ncq
->nc_back
= ncp
->nc_back
;
/* and make a dummy hash chain */
/* insert at head of LRU list (first to grab) */
ncq
->nc_prev
= &ncp
->nc_nxt
;
* Add an entry to the cache
cache_enter(dvp
, vp
, cnp
)
struct componentname
*cnp
;
register struct namecache
*ncp
, *ncq
, **ncpp
;
if (cnp
->cn_namelen
> NCHNAMLEN
)
panic("cache_enter: name too long");
* Free the cache slot at head of lru chain.
if (numcache
< desiredvnodes
) {
ncp
= (struct namecache
*)
malloc((u_long
)sizeof *ncp
, M_CACHE
, M_WAITOK
);
bzero((char *)ncp
, sizeof *ncp
);
} else if (ncp
= nchhead
) {
/* remove from lru chain */
ncq
->nc_prev
= ncp
->nc_prev
;
/* remove from old hash chain, if on one */
ncq
->nc_back
= ncp
->nc_back
;
/* grab the vnode we just found */
ncp
->nc_dvpid
= dvp
->v_id
;
ncp
->nc_nlen
= cnp
->cn_namelen
;
bcopy(cnp
->cn_nameptr
, ncp
->nc_name
, (unsigned)ncp
->nc_nlen
);
/* link at end of lru chain */
/* and insert on hash chain */
ncpp
= &nchashtbl
[cnp
->cn_hash
& nchash
];
ncq
->nc_back
= &ncp
->nc_forw
;
* Name cache initialization, from vfs_init() when we are booting
nchashtbl
= hashinit(desiredvnodes
, M_CACHE
, &nchash
);
* Cache flush, a particular vnode; called when a vnode is renamed to
* hide entries that would now be invalid
struct namecache
*ncp
, **ncpp
;
vp
->v_id
= ++nextvnodeid
;
for (ncpp
= &nchashtbl
[nchash
]; ncpp
>= nchashtbl
; ncpp
--) {
for (ncp
= *ncpp
; ncp
; ncp
= ncp
->nc_forw
) {
vp
->v_id
= ++nextvnodeid
;
* Cache flush, a whole filesystem; called when filesys is umounted to
* remove entries that would now be invalid
* The line "nxtcp = nchhead" near the end is to avoid potential problems
* if the cache lru chain is modified while we are dumping the
* inode. This makes the algorithm O(n^2), but do you think I care?
register struct namecache
*ncp
, *nxtcp
;
for (ncp
= nchhead
; ncp
; ncp
= nxtcp
) {
if (ncp
->nc_dvp
== NULL
|| ncp
->nc_dvp
->v_mount
!= mp
) {
/* free the resources we had */
/* remove from old hash chain, if on one */
if (nxtcp
= ncp
->nc_forw
)
nxtcp
->nc_back
= ncp
->nc_back
;
/* delete this entry from LRU chain */
nxtcp
->nc_prev
= ncp
->nc_prev
;
/* cause rescan of list, it may have altered */
/* also put the now-free entry at head of LRU */
nxtcp
->nc_prev
= &ncp
->nc_nxt
;