Re: [Bug 417] New: htree much slower than regular ext3

Daniel Phillips
2003-03-09T17:44:28Z

On Sun 09 Mar 03 08:08, Alex Tomas wrote:
> >>>>> Daniel Phillips (DP) writes:
>
> DP> On Fri 07 Mar 03 16:46, Alex Tomas wrote:
> DP> The problem I see with your approach is that the traversal is no
> DP> longer in hash order, so a leaf split in the middle of a
> DP> directory traversal could result in a lot of duplicate dirents.
> DP> I'm not sure there's a way around that.
>
> 1) As far as I understand, duplicates are possible even in classic ext2
> w/o sortdir/index. See the diagram:
>
> Process 1 Process 2
>
> getdents(2) returns
> dentry1 (file1 -> Inode1)
> dentry2 (file2 -> Inode2)
>
> context switch -->
> unlink(file1), empty dentry1
> creat(file3), Inode3, use
> dentry1 creat(file1), Inode1, use dentry3
>
> context switch -->
>
> getdents(2) returns
> dentry3(file1 -> Inode1)
>
>
> Am I right?
>
>
> 2) Why do not use hash order for traversal like ext3_dx_readdir() does?
> Upon reading several dentries within some hash set readdir() sorts them
> in inode order and returns to an user.
>
>
> with best regards, Alex

You're right, but you still don't win the stuffed poodle.

I put forth the same argument at last year's kernel workshop and was
overruled on the grounds that, let me see:

- Duplicates as a result of unlinks are one thing, duplicates as a
result of creates are another, worse thing.

- Creating one duplicate as a result of one unlink is one thing,
creating lots of duplicates with one operation is another, worse
thing.

- The rules are written to allow this particular duplicate behavior
in UFS (design inherited by Ext2/3) because at the time, UFS was
the only game in town.

The phrase "broken by design" comes to mind. Ted and Stephen would no doubt
be happy to elaborate. Anyway, there's another reason we need to return
results in hash order, and that is telldir/seekdir, which expects a stable
enumeration of a directory with no duplicates, even with concurrent
operations going on, and even if the server is rebooted in the middle of a
directory traversal. Not just broken by design, but smashed to pieces by
design. And we still have to make it work, for some definition of "work".

Anyway,