Re: Large directories and poor order correlation

[Ted Ts'o <tytso@mit.edu>]

On Mon, Mar 14, 2011 at 04:52:21PM -0400, Phillip Susi wrote:
> It seems unreasonable to ask applications to read all directory entries,
> then sort them by inode number to achieve reasonable performance.  This
> seems like something the fs should be doing.

Unfortunately the kernel can't do it, because a directory could be
arbitrarily big, and kernel memory is non-swappable.  In addition,
what if a process opens a directory, starts calling readdir, pauses in
the middle, and then holds onto it for days, weeks, or months?

Combine that with POSIX requirements about how readdir() has to behave
if files are added or deleted during a readdir() session (even a
readdir session which takes days, weeks, or months), and it's a
complete mess.

It's not hard to provide library routines that do the right thing, and
I have written an LD_PRELOAD which intercepts opendir() and readdir()
calls and does the sorting in userspace.  Perhaps the right answer is
getting this into libc, but I have exactly two words for you: "Uhlrich
Drepper".

					- Ted