* Copyright (c) 1989 The Regents of the University of California.
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* 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. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the University of
* California, Berkeley and its contributors.
* 4. 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
* @(#)vfs_cache.c 7.8 (Berkeley) 2/28/91
* 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.
union nchash
*nch_head
[2];
struct namecache
*nch_chain
[2];
#define nch_forw nch_chain[0]
#define nch_back nch_chain[1]
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.
register struct nameidata
*ndp
;
register struct vnode
*dvp
;
register struct namecache
*ncp
;
if (ndp
->ni_namelen
> NCHNAMLEN
) {
nhp
= &nchashtbl
[ndp
->ni_hash
& nchash
];
for (ncp
= nhp
->nch_forw
; ncp
!= (struct namecache
*)nhp
;
if (ncp
->nc_dvp
== dvp
&&
ncp
->nc_dvpid
== dvp
->v_id
&&
ncp
->nc_nlen
== ndp
->ni_namelen
&&
!bcmp(ncp
->nc_name
, ndp
->ni_ptr
, (unsigned)ncp
->nc_nlen
))
if (ncp
== (struct namecache
*)nhp
) {
if (!ndp
->ni_makeentry
) {
} else if (ncp
->nc_vp
== NULL
) {
if ((ndp
->ni_nameiop
& OPMASK
) != 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 */
*ncp
->nc_prev
= ncp
->nc_nxt
;
ncp
->nc_nxt
->nc_prev
= ncp
->nc_prev
;
/* remove from hash chain */
/* insert at head of LRU list (first to grab) */
nchhead
->nc_prev
= &ncp
->nc_nxt
;
/* and make a dummy hash chain */
* Add an entry to the cache
register struct nameidata
*ndp
;
register struct namecache
*ncp
;
* 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 */
*ncp
->nc_prev
= ncp
->nc_nxt
;
ncp
->nc_nxt
->nc_prev
= ncp
->nc_prev
;
/* remove from old hash chain */
/* grab the vnode we just found */
ncp
->nc_vpid
= ndp
->ni_vp
->v_id
;
ncp
->nc_dvp
= ndp
->ni_dvp
;
ncp
->nc_dvpid
= ndp
->ni_dvp
->v_id
;
ncp
->nc_nlen
= ndp
->ni_namelen
;
bcopy(ndp
->ni_ptr
, ncp
->nc_name
, (unsigned)ncp
->nc_nlen
);
/* link at end of lru chain */
/* and insert on hash chain */
nhp
= &nchashtbl
[ndp
->ni_hash
& nchash
];
* Name cache initialization, from vfs_init() when we are booting
register union nchash
*nchp
;
nchashsize
= roundup((desiredvnodes
+ 1) * sizeof *nchp
/ 2,
nchashtbl
= (union nchash
*)malloc((u_long
)nchashsize
,
for (nchash
= 1; nchash
<= nchashsize
/ sizeof *nchp
; nchash
<<= 1)
nchash
= (nchash
>> 1) - 1;
for (nchp
= &nchashtbl
[nchash
]; nchp
>= nchashtbl
; nchp
--) {
nchp
->nch_head
[0] = nchp
;
nchp
->nch_head
[1] = nchp
;
* Cache flush, a particular vnode; called when a vnode is renamed to
* hide entries that would now be invalid
vp
->v_id
= ++nextvnodeid
;
for (nhp
= &nchashtbl
[nchash
]; nhp
>= nchashtbl
; nhp
--) {
for (ncp
= nhp
->nch_forw
; ncp
!= (struct namecache
*)nhp
;
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 */
remque(ncp
); /* remove entry from its hash chain */
ncp
->nc_forw
= ncp
; /* and make a dummy one */
/* delete this entry from LRU chain */
nxtcp
->nc_prev
= ncp
->nc_prev
;
/* cause rescan of list, it may have altered */
/* put the now-free entry at head of LRU */
nxtcp
->nc_prev
= &ncp
->nc_nxt
;