lkml.org 
[lkml]   [1999]   [Nov]   [2]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: structure dentry help...


On Tue, 2 Nov 1999, Jamie Lokier wrote:

> Alexander Viro wrote:
> > > My program reads only about 5% (my guesstimate) of the inodes. The rest
> > > are elided by the "leaf optimisation" (also in GNU find) or, in my
> > > program, a heuristic-guided variant which finds equivalent solutions
> > > with fewer inode reads.
> >
> > Details, please. In almost all cases when find(1) is applied to
> > really large trees it involves mode conditions (either -perm or -t), i.e.
> > lstat(2).
>
> The biggest case of all is `updatedb', run on many Linux systems every
> night.

Aaaargh. Updatedb is only one of the tree scanners and usual sequence of
cron jobs involves, for example, scan for suid binaries + several more
things. Sorry, it's a long-standing pet peeve - never got to sit and
change updatedb so that it would store mode. That would allow to cut down
on the other scans. Big way.

> Optimisation #2: the "leaf" optimisation (GNU & BSD)
>
> Unix filesystems follow this convention: the link count of a
> directory (that is not itself hard linked) is two plus the number
> of subdirectories. The count works like this: one for the link
> from its parent -- i.e. the name of the directory; one for the
> entry "." in the directory itself, and one each for every ".."
> entry in subdirectories of the directory because they refer back to
> this directory.

AFFS fscks that up. The thing has no i_nlink. By design ;-<

> This saves about 2/3 of all stat() calls. stat() calls are
> expensive because they typically involve reading "inodes" from
> disk for every file statted. Avoiding stat() calls means those
> disk accesses are avoided as well.

I would beg to differ. Number of stat(2) calls is not a sensible metrics
here: you have several inodes in a block and stat() on any of them brings
the whole bunch into core. IOW, if inumbers are scattered you are not
winning much.

> You can do even better in more cases if you know the type of an entry
> before reading its inode. This affects not just eliding stat() calls,
> but also O_DIRECTORY, and intermediate path name lookups. BSD has had

Big win for 4.4BSD, but we have dcache... Again, it's a nice idea, but
I'ld like to see some data.

> > expect large and nasty directory fiddling (quadratic by size) to take quite
> > some time...
>
> Most filesystems do not have any large directories, so directory search
> time is negligable. Unless everything is in memory already, the
> dominant time is I/O. Some CPU time is required for the sorting and
> general strategic things, but that will improve.
>
> For a full disk scan of a 2/3 full 6.4G disk, which includes about 100
> megabytes of local newsspool cache, reading inodes takes about half of
> the time and reading directories takes the other half. (This is a very
> rough subjective measurement based on watching messages appear between
> alternating phases).

When you are "reading inodes" you are doing lookups too. And that
_can_ be eliminated (from O(n^2) to O(n)).

> I found nearly half the total execution time is removed if I scan
> everything except the newsspool directory, so the unusual directory
> structure is significant. The subjective 50/50 split still applies.

Sure it is. It's a helluva fat directory, so effects of search will play
here. Big way. Notice that readdir() is O(n), but calling stat() on
everything (especially when reordered) will give O(n^2) lookups and O(n)
inode reads, and I don't see how to distinguish between reading inode and
doing lookup - both happen in one syscall.

> The 2/3 stat() measurement was taken on another disk, with most of its
> 3G or so used, that does not have a local newsspool cache, and in
> neither case have I used the name heuristic yet.
>
> > BTW, lookup() is protected by lock on the parent, so that might be the
> > reason for contention.
>
> Another reason for "dentry without inode"? Can you avoid locking the
> parent if you only have to do an iget()?

Not. You will get races over the whole VFS. You don't want to go there.
Really. Semaphore on directory inodes is used for dcache integrity
protection. The last thing you want here is somebody being able to bypass
locked nodes in the tree.

> Alternatively the kernel could provide the same. If readdir() can prime
> the dentry cache, then if a name is not in the dentry cache and the
> directory has not changed, there is no need for a lookup()...

You forgot about the memory pressure _and_ about the fact that negative
dentries are used as templates for create() and friends.


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:54    [W:1.393 / U:0.212 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site