32k directory limit

[David Schultz]

On Wed, Jan 21, 2004, Robert Watson wrote:
> On Wed, 21 Jan 2004, Darcy Buskermolen wrote:
> 
> > Problem is some brain dead software (to which I don't have source) 
> > creating these dirs all under one dir and not nesting them in a way to
> > ensure that the 32k number isn't broken.
> 
> The largest number of files (not directories) I have in a single directory
> appears to be about 1.1 million.  Other than the link count, there's no
> real reason there couldn't be more, although you might well bump into
> other scalability limits (I have to remember not to let ls sort the
> directory listing for that directory, for example).

The fact that UFS lacks a hash-based on-disk directory format
limits scalability.  Even though lookups are optimized via hashing
once the directory has been read into memory, it is still
necessary to transfer the entire directory from disk (or about
half of it if all lookups are successful ones).  If I recall
correctly, some Linux folks addressed this problem in ext2 with a
hackish but reverse-compatible trick, documented in Proc. FREENIX
('98 or 2000, IIRC).  Several other filesystems use a hash-based
on-disk format natively.