Re: Expected getdents behaviour

[Nikita Danilov <nikita@clusterfs.com>]

Anton Altaparmakov writes:

[...]

 > 
 > I don't know how your hash works but on ntfs this does not work like that.  
 > There is no parameter which would be able to tell you where you are in the 
 > b tree, unless you take a reference on an entry so it cannot be removed 
 > (rename==remove btw) but how does the reference get released later?

Reiser4 has exactly the same problem, and this is how it was solved (not
for the weak of heart):

 - offset of a directory entry is its ordinal number within a
 directory. I.e., first name in the directory has offset 0, second---1,
 etc.;

 - struct file for directory remembers "current readdir position" which
 is a pair (ordinal-number-of-entry, key-of-entry-in-the--tree);

 - on seekdir(dir, pos) (== lseek(dir, pos)), pos is the ordinal number
 of the target entry, and comparing it with the current readdir position
 we know how many entries to rewind to the left or to the right to reach
 the target. This can be done in any reasonable *-tree (for suitable
 values of *);

 - now the fun (or horror) part: above rewinding does not work correctly
 when entries were added or removed between current position and the
 target entry. To work about this, all directory modifications are
 monitored and current position is adjusted accordingly: when new
 directory entry is created, its key is compared against key in the
 current readdir position. If entry's key is smaller, then entry is
 added "before" current position and current position's
 ordinal-number-of-entry is incremented. Similarly for entry removal;

 - this of course is still fragile and can be broken, but that's enough
 for most cases (rm -r and friends work, for example);

 - additional complexities due to non-unique keys in the tree and NFS
 (where we don't have persistent struct file for a directory) are left
 as an exercise for a reader.

Nikita.