Date: Thu, 14 Dec 1995 17:04:51 -0700 (MST) From: Terry Lambert <terry@lambert.org> To: current@freebsd.org Subject: HOW THE BSD DIRECTORY NAME CACHE CURRENTLY WORKS Message-ID: <199512150004.RAA03084@phaeton.artisoft.com>
next in thread | raw e-mail | index | archive | help
Here is a documentation of the current directory entry name cache mechanism employed by FreeBSD. Be warned that because of the level at which it is wired in, it has certain obvious bogosities. It should be rewired directly into the lookup() in vfs_lookup.c some day. Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers. ============================================================================= HOW THE BSD DIRECTORY NAME CACHE CURRENTLY WORKS Note1: This diagram refers to the ufs/cache interaction only. Other File Systems which are cache users are not described (two are known to be erroneous in certain cases). Note2: The cache_purge() and cache_purgevfs() calls on mount/unmount operations are not described in detail. In general, mount point vnodes that are covered are purged with cache_purge(), and file systems that are unmounted are purged with cache_purgevfs(). Note3: All vnodes allocated or recovered from the freelist by the getnewvnode() are purged as part of initialization. ,----------,----------,----------,-----------------------------------. VOP_ | RECLAIM | RENAME | RMDIR | LOOKUP | nameiop | | | |LOOKUP |CREATE |RENAME |DELETE | `----------`----------`----------`--------`--------`--------`--------' cache_lookup() ---------,----------,----------,----------,--------,--------,--------,--------. NO ENTRY | | | | cache | cache | cache | cache | NO EXIST | | | | miss | miss | miss | miss | ---------+----------+----------+----------+--------+--------+--------+--------. NO ENTRY | | | | cache | cache | cache | cache | EXIST | | | | miss | miss | miss | miss | ---------+----------+----------+----------+--------+--------+--------+--------. NEG ENTRY| | | | cache | PURGE3 | PURGE2 |PURGE2 | VALID | | | | hit(-) | | | | ---------+----------+----------+----------+--------+--------+--------+--------. ENTRY | | | | cache | cache | PURGE2 |PURGE2 | VALID | | | | hit | hit | | | ---------+----------+----------+----------+--------+--------+--------+--------. NEG ENTRY| | | | PURGE1 | PURGE1 | PURGE1 | PURGE1 | INVALID | | | | | | | | ---------+----------+----------+----------+--------+--------+--------+--------. ENTRY | | | | PURGE1 | PURGE1 | PURGE1 | PURGE1 | INVALID | | | | | | | | ---------`----------`----------`----------`--------`--------`--------`--------. cache_enter() ---------,----------,----------,----------,--------,--------,--------,--------. NO ENTRY | | | | make | skip | skip | skip | NO EXIST | | | | entry | entry | entry | entry | ---------+----------+----------+----------+--------+--------+--------+--------. NO ENTRY | | | | make | make | skip | skip | EXIST | | | | entry | entry | entry | entry | ---------+----------+----------+----------+--------+--------+--------+--------. NEG ENTRY| | | | | | | | VALID | | | | | | | | ---------+----------+----------+----------+--------+--------+--------+--------. ENTRY | | | | | | | | VALID | | | | | | | | ---------+----------+----------+----------+--------+--------+--------+--------. NEG ENTRY| | | | | | | | INVALID | | | | | | | | ---------+----------+----------+----------+--------+--------+--------+--------. ENTRY | | | | | | | | INVALID | | | | | | | | ---------`----------`----------`----------`--------`--------`--------`--------. cache_purge() ---------,----------,----------,----------,--------,--------,--------,--------. NO ENTRY | cache | cache | cache | | | | | NO EXIST | purge1 | purge2 | purge3 | | | | | ---------+----------+----------+----------+--------+--------+--------+--------. NO ENTRY | cache | cache | cache | | | | | EXIST | purge1 | purge2 | purge3 | | | | | ---------+----------+----------+----------+--------+--------+--------+--------. NEG ENTRY| cache | cache | cache | | | | | VALID | purge1 | purge2 | purge3 | | | | | ---------+----------+----------+----------+--------+--------+--------+--------. ENTRY | cache | cache | cache | | | | | VALID | purge1 | purge2 | purge3 | | | | | ---------+----------+----------+----------+--------+--------+--------+--------. NEG ENTRY| cache | cache | cache | | | | | INVALID | purge1 | purge2 | purge3 | | | | | ---------+----------+----------+----------+--------+--------+--------+--------. ENTRY | cache | cache | cache | | | | | INVALID | purge1 | purge2 | purge3 | | | | | ---------`----------`----------`----------`--------`--------`--------`--------. ============================================================================= KEY ============================================================================= cache Entry not present in cache; cache Entry present in cache; miss lookup returns 0 hit entry returned (may be neg) PURGE1 cache_purge has been called PURGE2 The MAKEENTRY flag(1) is to invalidate the entry not set; delete the entry PURGE3 Negative entries are purged skip The negative cache_enter() if nameiop is CREATE(2) entry won't happen for CREATE(3) make An entry, positive or cache Unconditionally invalidate entry negative, is made purge1 the vnode cache Conditionally invalidate cache The dir being rmdir'ed and purge2 the vnode(4) purge3 its parent are invalidated (1) The MAKEENTRY flag is set by default. It is unset by lookup() before VOP_LOOKUP is called IFF the component being looked up is the last component AND 'docache' is zero. 'docache' will be zero IFF: the NOCACHE flag is set on NDINIT(), OR the nameiop is DELETE, OR: IFF the nameiop *isn't* CREATE and either the WANTPARENT or LOCKPARENT flag is set on NDINIT(). The RENAME nameiop is only ever used with the LOCKPARENT flag set. The DELETE nameiop is called with WANTPARENT in the general case and LOCKPARENT in the VOP_RENAME case. (2) The CREATE nameiop will not unset the MAKEENTRY flag. This is somewhat bogus in implementation, but the purpose is to use the CREATE nameiop as an intention mode to get a directory slot to be used in the actual VOP_CREATE() later. (3) Or if the MAKEENTRY flag is not set. Which it never is in the RENAME/DELETE nameiop case in the current code. (4) The "to" vnode is invalidated if it is a directory. This is not the right thing to do in several cases, but it happens anyway: if the ufs_dirrewrite() fails or if the target directory and the source directory are the same vnode. The "from" directory is invalidated in the case of a successful rename of the directory (again, even in the case that the subsequent entry removal fails (and therefore the source directory is not changed). =============================================================================
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199512150004.RAA03084>