Subject: Re: namei caching of newly created files?
To: Havard Eidnes <>
From: Bill Studenmund <>
List: tech-kern
Date: 01/19/2005 17:47:31
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Thu, Jan 20, 2005 at 02:09:13AM +0100, Havard Eidnes wrote:
> ...and here follows some revised profiling data.  Unsurprisingly,
> ufs_lookup still dominates completely:

As it will. ufs_lookup is doing two things in the initial case. It is=20
checking to see if the name exists, and it is looking for a slot to add=20
the new file in if it doesn't exist.

Becasue we don't build in-kernel lists of files in the directory, we have=
to do a full search (O(n)) of the directory to see if the name is or isn't=
there already.

To further complicate things, we also use that initial search to look for=
empty entries. If we don't find the name, we will use one empty entry to=20
store the to-be-created inode. So even if we used an in-core tree (or hash=
table) to tell if the file doesn't exist, we still need to know where to=20
create it in the dir.

The answer is if we do create an in-core index (via a balanced tree or a
hash or whatever), we also create a linked list indicating which entries
in the directory are empty. Then creating becomes O(log n) or O(c) for the
lookup and O(c) for the entry-finding.

The question of course is writing code to handle this and then deciding=20
when we use it - if the directory only has a few entries or is only so=20
big, it may be easier to just do the current linear searches.

Take care,


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

Version: GnuPG v1.2.3 (NetBSD)