Quadratic behavior of shrink_dcache_parent()

Quadratic behavior of shrink_dcache_parent()

[Miklos Szeredi]

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

Re: Quadratic behavior of shrink_dcache_parent()

[Rafael J. Wysocki]

On Monday, 20 November 2006 12:10, Miklos Szeredi wrote:
> 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.

Oh, well.  So that's the reason why the shrinking of memory in swsusp can
take so much time.

> 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?

None, for now.  It looks like I need to learn that code ...

Greetings,
Rafael


-- 
You never change things by fighting the existing reality.
		R. Buckminster Fuller