Re: namei caching of newly created files?

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 
checking to see if the name exists, and it is looking for a slot to add 
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 
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 
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 
when we use it - if the directory only has a few entries or is only so 
big, it may be easier to just do the current linear searches.

Take care,

Bill

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (NetBSD)

iD8DBQFB7w2zWz+3JHUci9cRAkxwAJ0Um0kgKh95ExA9Uy1dmAHgw2MKwwCglKh6
GzhsbUecSD/oDSkC+NdITSY=
=tzFo
-----END PGP SIGNATURE-----