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