lkml.org 
[lkml]   [2006]   [Nov]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectQuadratic behavior of shrink_dcache_parent()
From
Date
The shrink_dcache_parent() can take a very long time for deep
directory trees: minutes for depth of 100,000, probably hours for
depth of 1,000,000.

The reason is that after dropping a leaf, it starts again from the
root.

Filesystems affected include FUSE, NFS, CIFS. Others I haven't
checked. NFS and to a lesser extent CIFS don't seem to efficiently
handle lookups within such a deep hierarchy, so they're sort of
immune.

But with FUSE it's pretty easy to DoS the system.

Limiting the depth to some sane value could work around this problem,
but that would mean having to traverse subtrees in rename().

Any better ideas?

Thanks,
Miklos
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2006-11-20 12:13    [W:0.026 / U:2.952 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site