2 # ensure that "rm -rf DIR-with-many-entries" is not O(N^2)
4 # Copyright (C) 2008-2009 Free Software Foundation, Inc.
6 # This program is free software: you can redistribute it and/or modify
7 # it under the terms of the GNU General Public License as published by
8 # the Free Software Foundation, either version 3 of the License, or
9 # (at your option) any later version.
11 # This program is distributed in the hope that it will be useful,
12 # but WITHOUT ANY WARRANTY; without even the implied warranty of
13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 # GNU General Public License for more details.
16 # You should have received a copy of the GNU General Public License
17 # along with this program. If not, see <http://www.gnu.org/licenses/>.
19 if test "$VERBOSE" = yes; then
28 # Using rm -rf to remove a 400k-entry directory takes:
29 # - 9 seconds with the patch, on a 2-yr-old system
30 # - 350 seconds without the patch, on a high-end system (disk 20-30% faster)
33 # The number of entries in our test directory.
36 # Choose a value that is large enough to ensure an accidentally
37 # regressed rm would require much longer than $threshold_seconds to remove
38 # the directory. With n=400k, pre-patch GNU rm would require about 350
39 # seconds even on a fast disk. On a relatively modern system, the
40 # patched version of rm requires about 10 seconds, so even if you
41 # choose to enable very expensive tests with a disk that is much slower,
42 # the test should still succeed.
44 # Skip unless "." is on an ext[34] file system.
45 # FIXME-maybe: try to find a suitable file system or allow
46 # the user to specify it via an envvar.
47 df -T -t ext3 -t ext4dev -t ext4 . \
48 || skip_test_ 'this test runs only on an ext3 or ext4 file system'
50 # Skip if there are too few inodes free. Require some slack.
51 free_inodes=$(stat -f --format=%d .) || framework_failure
52 min_free_inodes=$(expr 12 \* $n / 10)
53 test $min_free_inodes -lt $free_inodes \
54 || skip_test_ "too few free inodes on '.': $free_inodes;" \
55 "this test requires at least $min_free_inodes"
61 seq $n | xargs touch &&
66 test $ok = 1 || framework_failure
67 setup_duration=$(expr $(date +%s) - $start)
68 echo creating a $n-entry directory took $setup_duration seconds
70 # If set-up took longer than the default $threshold_seconds,
71 # use the longer set-up duration as the limit.
72 test $threshold_seconds -lt $setup_duration \
73 && threshold_seconds=$setup_duration
76 timeout ${threshold_seconds}s rm -rf d; err=$?
77 duration=$(expr $(date +%s) - $start)
80 124) fail=1; echo rm took longer than $threshold_seconds seconds;;
85 echo removing a $n-entry directory took $duration seconds