1.\" $NetBSD: namecache.9,v 1.14 2010/07/21 09:01:35 hannken Exp $ 2.\" 3.\" Copyright (c) 2001 The NetBSD Foundation, Inc. 4.\" All rights reserved. 5.\" 6.\" This code is derived from software contributed to The NetBSD Foundation 7.\" by Gregory McGarry. 8.\" 9.\" Redistribution and use in source and binary forms, with or without 10.\" modification, are permitted provided that the following conditions 11.\" are met: 12.\" 1. Redistributions of source code must retain the above copyright 13.\" notice, this list of conditions and the following disclaimer. 14.\" 2. Redistributions in binary form must reproduce the above copyright 15.\" notice, this list of conditions and the following disclaimer in the 16.\" documentation and/or other materials provided with the distribution. 17.\" 18.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 19.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 20.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 21.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 22.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 28.\" POSSIBILITY OF SUCH DAMAGE. 29.\" 30.Dd July 21, 2010 31.Dt NAMECACHE 9 32.Os 33.Sh NAME 34.Nm namecache , 35.Nm cache_lookup , 36.Nm cache_revlookup , 37.Nm cache_enter , 38.Nm cache_purge , 39.Nm cache_purgevfs , 40.Nm namecache_print 41.Nd name lookup cache 42.Sh SYNOPSIS 43.In sys/namei.h 44.In sys/proc.h 45.In sys/uio.h 46.In sys/vnode.h 47.Ft int 48.Fn cache_lookup "struct vnode *dvp" "struct vnode **vpp" \ 49"struct componentname *cnp" 50.Ft int 51.Fn cache_revlookup "struct vnode *vp" "struct vnode *dvp" \ 52"char **bpp" "char *bufp" 53.Ft void 54.Fn cache_enter "struct vnode *dvp" "struct vnode *vp" \ 55"struct componentname *cnp" 56.Ft void 57.Fn cache_purge "struct vnode *vp" 58.Ft void 59.Fn cache_purgevfs "struct mount *mp" 60.Ft void 61.Fn namecache_print "struct vnode *vp" "void (*func)(const char *, ...)" 62.Sh DESCRIPTION 63The name lookup cache is the mechanism to allow the file system type 64dependent algorithms to quickly resolve a file's vnode from its 65pathname. 66The name lookup cache is generally accessed through the higher-level 67.Xr namei 9 68interface. 69.Pp 70The name of the file is used to lookup an entry associated with the 71file in the name lookup cache. 72If no entry is found, one is created for it. 73If an entry is found, the information obtained from the cache lookup 74contains information about the file which is useful to the file system 75type dependent functions. 76.Pp 77The name lookup cache is managed by a least recently used (LRU) 78algorithm so frequently used names will hang around. 79The cache itself is a hash table called 80.Va nchashtbl , 81containing 82.Em namecache 83entries that are allocated dynamically from a kernel memory pool. 84Each entry has the following structure: 85.Bd -literal 86#define NCHNAMLEN 31 /* maximum name segment length */ 87struct namecache { 88 LIST_ENTRY(namecache) nc_hash; /* hash chain */ 89 TAILQ_ENTRY(namecache) nc_lru; /* LRU chain */ 90 LIST_ENTRY(namecache) nc_vhash; /* directory hash chain */ 91 LIST_ENTRY(namecache) nc_dvlist; 92 struct vnode *nc_dvp; /* vnode of parent of name */ 93 LIST_ENTRY(namecache) nc_vlist; 94 struct vnode *nc_vp; /* vnode the name refers to */ 95 int nc_flags; /* copy of componentname's ISWHITEOUT */ 96 char nc_nlen; /* length of name */ 97 char nc_name[NCHNAMLEN]; /* segment name */ 98}; 99.Ed 100.Pp 101For simplicity (and economy of storage), names longer than a maximum 102length of NCHNAMLEN are not cached; they occur infrequently in any 103case, and are almost never of interest. 104.Pp 105Each 106.Em namecache 107entry can appear on two hash chains in addition to 108.Va nshashtbl : 109.Em ncvhashtbl 110(the name cache directory hash chain), and 111.Em nclruhead 112(the name cache LRU chain). 113The hash chains are indexed by a hash value obtained from the file's 114name and the address of its parent directory vnode. 115.Pp 116Functions which access to the name cache pass arguments in the 117partially initialised 118.Em componentname 119structure. 120See 121.Xr vnodeops 9 122for details on this structure. 123.Sh FUNCTIONS 124.Bl -tag -width compact 125.It Fn cache_lookup "dvp" "vpp" "cnp" 126Look for a name in the cache. 127.Fn cache_lookup 128is called with 129.Fa dvp 130pointing to the vnode of the directory to search and 131.Fa cnp 132pointing to the partially initialised component structure. 133.Fa cnp-\*[Gt]cn_nameptr 134points to the name of the entry being sought, 135.Fa cnp-\*[Gt]cn_namelen 136tells the length of the name, and 137.Fa cnp-\*[Gt]cn_hash 138contains a hash of the name. 139If the lookup succeeds, the vnode is locked, stored in 140.Fa vpp 141and a status of zero is returned. 142If the locking fails for whatever reason, the vnode is unlocked and the 143error is returned. 144If the lookup determines that the name does not exist any longer, a 145status of ENOENT is returned. 146If the lookup fails, a status of -1 is returned. 147.It Fn cache_revlookup "vp" "dvp" "bpp" "bufp" 148Scan cache looking for name of directory entry pointing at 149.Fa vp 150and fill in 151.Fa dvpp . 152If 153.Fa bufp 154is 155.Pf non- Dv NULL , 156also place the name in the buffer which starts at 157.Fa bufp , 158immediately before 159.Fa bpp , 160and move bpp backwards to point at the start of it. 161If the lookup succeeds, the vnode is referenced. 162Returns 0 on success, -1 on cache miss, positive errno on failure. 163.It Fn cache_enter "dvp" "vp" "cnp" 164Add an entry to the cache. 165.Fn cache_enter 166is called with 167.Fa dvp 168pointing to the vnode of the directory to enter and 169.Fa cnp 170pointing to the partially initialised component structure. 171If 172.Fa vp 173is 174.Dv NULL , 175a negative cache entry is created, specifying that the entry 176does not exist in the file system. 177.Fa cnp-\*[Gt]cn_nameptr 178points to the name of the entry being entered, 179.Fa cnp-\*[Gt]cn_namelen 180tells the length of the name, and 181.Fa cnp-\*[Gt]cn_hash 182contains a hash of the name. 183.It Fn cache_purge "vp" 184Flush the cache of a particular vnode 185.Fa vp . 186.Fn cache_purge 187is called when a vnode is renamed to hide entries that would now be 188invalid. 189.It Fn cache_purgevfs "mp" 190Flush cache of a whole file system 191.Fa mp . 192.Fn cache_purgevfs 193is called when file system is unmounted to remove entries that would 194now be invalid. 195.It Fn namecache_print "vp" "func" 196Print all entries of the name cache. 197.Fa func 198is the 199.Xr printf 9 200format. 201.Fn namecache_print 202is only defined if the kernel option DDB is compiled into the kernel. 203.El 204.Sh CODE REFERENCES 205This section describes places within the 206.Nx 207source tree where actual code implementing or using the name 208lookup cache can be found. 209All pathnames are relative to 210.Pa /usr/src . 211.Pp 212The name lookup cache is implemented within the file 213.Pa sys/kern/vfs_cache.c . 214.Sh SEE ALSO 215.Xr intro 9 , 216.Xr namei 9 , 217.Xr vfs 9 , 218.Xr vnode 9 219.Sh HISTORY 220The name lookup cache first appeared in 221.Bx 4.2 . 222.Sh AUTHORS 223The original name lookup cache was written by Robert Elz. 224