linux-kernel - Quadratic behavior of shrink_dcache

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 20 Nov 2006 12:10:47 +0100
From:	Miklos Szeredi <miklos@...redi.hu>
To:	linux-fsdevel@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Quadratic behavior of shrink_dcache_parent()

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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/