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

2 files changed, 77 insertions, 0 deletions

diff --git a/tests/Makefile.am b/tests/Makefile.am
index bc656c427..e0377cc32 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -72,6 +72,7 @@ EXTRA_DIST += $(TESTS)
 TESTS =						\
   misc/help-version				\
   misc/invalid-opt				\
+  rm/ext3-perf					\
   rm/cycle					\
   chmod/no-x					\
   chgrp/basic					\
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