1#!/bin/sh
2# ensure that "rm -rf DIR-with-many-entries" is not O(N^2)
3
4# Copyright (C) 2008-2023 Free Software Foundation, Inc.
5
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.
10
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.
15
16# You should have received a copy of the GNU General Public License
17# along with this program.  If not, see <https://www.gnu.org/licenses/>.
18
19. "${srcdir=.}/tests/init.sh"; path_prepend_ ./src
20print_ver_ rm
21
22very_expensive_
23
24# In a circa 2008 benchmark, using rm -rf to remove a 400k-entry directory took:
25# - 9 seconds with the patch, on a 2-yr-old system
26# - 350 seconds without the patch, on a high-end system (disk 20-30% faster)
27threshold_seconds=60
28
29# The number of entries in our test directory.
30n=400000
31
32# Choose a value that is large enough to ensure an accidentally
33# regressed rm would require much longer than $threshold_seconds to remove
34# the directory.  With n=400k, pre-patch GNU rm would require about 350
35# seconds even on a fast disk.  On a circa 2006 system, the
36# patched version of rm requires about 10 seconds, so even if you
37# choose to enable very expensive tests with a device that is much slower,
38# the test should still succeed.
39
40# Skip unless "." is on an ext[34] file system.
41# FIXME-maybe: try to find a suitable file system or allow
42# the user to specify it via an envvar.
43df -T -t ext3 -t ext4dev -t ext4 . \
44  || skip_ 'this test runs only on an ext3 or ext4 file system'
45
46# Skip if there are too few inodes free.  Require some slack.
47free_inodes=$(stat -f --format=%d .) || framework_failure_
48min_free_inodes=$(expr 12 \* $n / 10)
49test $min_free_inodes -lt $free_inodes \
50  || skip_ "too few free inodes on '.': $free_inodes;" \
51      "this test requires at least $min_free_inodes"
52
53ok=0
54start=$(date +%s)
55mkdir d &&
56  cd d &&
57    seq $n | xargs touch &&
58    test -f 1 &&
59    test -f $n &&
60  cd .. &&
61  ok=1
62test $ok = 1 || framework_failure_
63setup_duration=$(expr $(date +%s) - $start)
64echo creating a $n-entry directory took $setup_duration seconds
65
66# If set-up took longer than the default $threshold_seconds,
67# use the longer set-up duration as the limit.
68test $threshold_seconds -lt $setup_duration \
69  && threshold_seconds=$setup_duration
70
71start=$(date +%s)
72timeout ${threshold_seconds}s rm -rf d; err=$?
73duration=$(expr $(date +%s) - $start)
74
75case $err in
76  124) fail=1; echo rm took longer than $threshold_seconds seconds;;
77  0) ;;
78  *) fail=1;;
79esac
80
81echo removing a $n-entry directory took $duration seconds
82
83Exit $fail
84