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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/