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>