Subject: Re: namei caching of newly created files?
To: Havard Eidnes <firstname.lastname@example.org>
From: Bill Studenmund <email@example.com>
Date: 01/19/2005 17:47:31
Content-Type: text/plain; charset=us-ascii
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=
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.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (NetBSD)
-----END PGP SIGNATURE-----