diff options
author | Jim Meyering <meyering@redhat.com> | 2008-09-22 22:42:12 +0200 |
---|---|---|
committer | Jim Meyering <meyering@redhat.com> | 2008-09-27 00:10:08 +0200 |
commit | 24412edeaf556a96a5ee122851de7c3e37726bdb (patch) | |
tree | 54240c2ae7944434cb6ef9ed2ff69ba6c964c78b /tests/rm/ext3-perf | |
parent | a5111af33ea6a5d27c3f7ab67afdb2a5884c38b6 (diff) | |
download | coreutils-24412edeaf556a96a5ee122851de7c3e37726bdb.tar.xz |
rm -r: avoid O(n^2) performance for a directory with very many entries
This enhancement works around a problem that is specific to at least
ext3 and ext4 file systems. With them, it would take hours to remove
a two-million-entry directory. RAM-backed file systems (tmpfs) are
not affected, since there is no seek penalty.
* remove.c (rm_malloc, rm_free, compare_ino): New functions.
(dirent_count, preprocess_dir): New function.
[struct readdir_data]: New struct.
(remove_cwd_entries): Call preprocess_dir.
* tests/rm/ext3-perf: New file. Test for the performance fix.
* NEWS: mention the new feature
Diffstat (limited to 'tests/rm/ext3-perf')
-rwxr-xr-x | tests/rm/ext3-perf | 76 |
1 files changed, 76 insertions, 0 deletions
diff --git a/tests/rm/ext3-perf b/tests/rm/ext3-perf new file mode 100755 index 000000000..e0439dffb --- /dev/null +++ b/tests/rm/ext3-perf @@ -0,0 +1,76 @@ +#!/bin/sh +# ensure that "rm -rf DIR-with-many-entries" is not O(N^2) + +# Copyright (C) 2008 Free Software Foundation, Inc. + +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program. If not, see <http://www.gnu.org/licenses/>. + +if test "$VERBOSE" = yes; then + set -x + rm --version +fi + +. $srcdir/test-lib.sh + +expensive_ + +# Using rm -rf to remove a 400k-entry directory takes: +# - 9 seconds with the patch, on a 2-yr-old system +# - 350 seconds without the patch, on a high-end system (disk 20-30% faster) +threshold_seconds=60 + +# The number of entries in our test directory. +n=400000 + +# Choose a value that is large enough to ensure an accidentally +# regressed rm would require much longer than $threshold_seconds to remove +# the directory. With n=400k, pre-patch GNU rm would require about 350 +# seconds even on a fast disk. On a relatively modern system, the +# patched version of rm requires about 10 seconds, so even if you +# choose to enable very expensive tests with a disk that is much slower, +# the test should still succeed. + +# Skip unless "." is on an ext[34] file system. +# FIXME-maybe: try to find a suitable file system or allow +# the user to specify it via an envvar. +df -t ext3 -t ext4dev -t ext4 . \ + || skip_test_ 'this test runs only on an ext3 or ext4 file system' + +# Skip if there are too few inodes free. Require some slack. +free_inodes=$(stat -f --format=%d .) || framework_failure +min_free_inodes=$(expr 12 \* $n / 10) +test $min_free_inodes -lt $free_inodes \ + || skip_test_ "too few free inodes on '.': $free_inodes;" \ + "this test requires at least $min_free_inodes" + +ok=0 +mkdir d && + cd d && + seq $n | xargs touch && + test -f 1 && + test -f $n && + cd .. && + ok=1 +test $ok = 1 || framework_failure + +fail=0 +start=$(date +%s) +rm -rf d || fail=1 +duration=$(expr $(date +%s) - $start) +test $duration -lt $threshold_seconds || + { fail=1; echo rm took longer than $threshold_seconds seconds; } + +echo removing a $n-entry directory took $duration seconds + +Exit $fail |