Subject: Re: RFC: VOP_LOOKUP() speedup
To: None <>
From: Bill Studenmund <>
List: tech-kern
Date: 05/05/2004 09:12:28
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Wed, May 05, 2004 at 12:47:47AM +0200, Reinoud Zandijk wrote:
> Dera Bill,
> On Tue, May 04, 2004 at 12:13:28PM -0700, Bill Studenmund wrote:
> > On Tue, May 04, 2004 at 01:07:10AM +0200, Reinoud Zandijk wrote:
> > > 1) before a VOP_CREATE() / VOP_MKDIR() / ... is called, VOP_LOOKUP() =
> > >    called first to check if the file opr directory name is allready p=
> > >    or not.
> > > 2) VOP_LOOKLUP() uses the namecache to check if its there...
> > > 3) if the namecache fails, VOP_LOOKUP() needs to search the directory=
> > >    disc for the name. _hopefully_ its still in the cache....
> So this is correct? i dont miss out a thing?

With the second cache =3D=3D block cache, yes, I think that's right.

> > > 1) every vnode/inode describing a directory gets a `number of directo=
> > > entries in cache' counter.
> > >=20
> > > 2) on addition or removal of an entry from the cache, this number is=
> > > maintained. Also when an entry is purged from the LRU.
> i've implemented this part in my test-kernel on my Alpha, and it works=20
> fine.

I still don't understand why you want a number. Isn't a boolean (all here=
or not all here) enough?

> > > 3) with this provision, ,VOP_LOOKUP() now can check the number of dir=
> > > entries in the directory with the `number of directory entries in cac=
> > > and see that the answer of the namecache is authorative if the two ar=
e the
> > > same.
> Only filing systems that want to use this feature need explicit coding;=
> othres just ignore and go for the normal way.
> > However, I think you can do everything you want in your own file system.
> :)

Perhaps I'm misunderstanding you, but my objection is to changing struct=20
vnode or the name cache structures. I think all you need to do is either=20
keep a flag or count in your fs's structure off the vnode.

> > All you need is one extra bit per node. When you do a linear search of =
> > dir, create vnodes and name cache entries for all files. Then flag the =
> > as all-present. Then in vop_revoke, in addition to blowing away cache=
> > entries, clear the "All present" bit in the parent vnode.
> but wouldn't this give a `false hit' when say a file is deleted? since th=
> VOP_REVOKE() will be called after the VOP_REMOVE()?

No. You won't have a parent after the VOP_REMOVE(), so the VOP_REVOKE()=20
won't clear anything.

Also, if we find issues in the proposal that need tweaking, we can tweak=20
things. ;-)

> > One thing you might need is a way to search the name cache for all pare=
> > vnodes of a given vnode. Not sure if we have this interface. If we don'=
> > it'd be a fine thing to add to the general code. Then on revoke, you cl=
> > the bit in all present parents.
> I dont get this honestly; if one focuses on the namecache itself and let =
> handle the counters itself, then the filingsystem doesn't need to search=
> around etc. and is the definition of the reference count allways correct.

The problem is that using the namecache means having vnodes for all of=20
these entities. So just doing an ls on a directory creates vnodes for all=
the contents.

Given the costs of reading a directory for UDF, especially while writing,=
I think the cost of the extra vnodes is less than the cost of not having=20
them. But for all other file systems, I do not expect the cost of the=20
directory reads is worth the extra vnodes.

As an example, consider my build machines. I keep a few kernel builds=20
around. If we used the name cache like you describe, each time I do an ls,=
we gain a lot of vnodes. Those vnodes push out the vnodes of files that we=
were using. If I'm not actually compiling a kernel, I just gained a lot of=
useless vnodes.

The fact that we don't always create vnodes when we read a directory is a
feature for a lot of workloads. I think we need to keep it (for everything
other than UDF).

Take care,


Content-Type: application/pgp-signature
Content-Disposition: inline

Version: GnuPG v1.2.3 (NetBSD)