Re: readdir on hash filesystems

[Nikita Danilov <nikita@clusterfs.com>]

Bob Copeland writes:
 > Hi all,
 > 
 > I am writing a new filesystem driver for the filesystem used by the
 > Rio Karma (and, as it happens, ReplayTV).  See the attached patch and
 > my webpage here for more info: http://bobcopeland.com/karma/.  I have
 > a
 > couple of newbie questions:
 > 
 > 1) The directory structure implements a hash table where each
 > directory has a fixed number of entries.  Each entry is a file that
 > has a pointer to another file in the hash chain and so there can be an
 > unlimited number of files in any hash chain.  What is the usual way to
 > implement readdir efficiently in this case?  With f_pos alone, I don't

All file systems with hash-based directories I know of, treat hash
collisions (a hash chain with more than one item) as some sort of
exception, because they have large number of hash buckets. For your case
where long hash chains are ordinary --because omfs has 201 hash buckets
per directory (hard-coded value is bad, by the way)-- there is no "usual
way", you have to invent one yourself.

 > have any idea which node I want along the hash chain without counting
 > up f_pos nodes in the tree.

One possible solution is to use lower 24 bits of f_pos to store an index
within given hash chain, and next 8 bits to store index of hash chain:

int hchain = file->f_pos >> 24 & 0xff;
int hindex = file->f_pos & 0xffffff;

Nikita.