diff options
| author | Jim Meyering <meyering@redhat.com> | 2009-09-03 15:15:09 +0200 |
|---|---|---|
| committer | Jim Meyering <meyering@redhat.com> | 2009-09-11 14:08:58 +0200 |
| commit | 722287e443c93e04e724e2812857a395cfab0b60 (patch) | |
| tree | 6513b8c652ab59cd12c79fe722930a3ce5f73978 | |
| parent | 9966c92dd4851db611ad88fc1eb68b01fffcaea3 (diff) | |
| download | coreutils-722287e443c93e04e724e2812857a395cfab0b60.tar.xz | |
rm: improve efficiency of rm -r (without -f) from O(N^2) to O(N)
where N is the depth of the deepest hierarchy rm is processing.
* src/remove.c (write_protected_non_symlink): Use faccessat to
avoid O(N)-per-entry cost of calling euidaccess.
* m4/jm-macros.m4 (coreutils_MACROS): Check for faccessat.
* NEWS (Improvements): Mention it.
| -rw-r--r-- | NEWS | 10 | ||||
| -rw-r--r-- | m4/jm-macros.m4 | 3 | ||||
| -rw-r--r-- | src/remove.c | 7 |
3 files changed, 20 insertions, 0 deletions
@@ -8,6 +8,16 @@ GNU coreutils NEWS -*- outline -*- This makes rm -rf significantly faster (400-500%) in some pathological cases, and slightly slower (20%) in at least one pathological case. + rm -r deletes deep hierarchies more efficiently. Before, it took O(N^2) + time, now it takes O(N). However, this improvement is not as pronounced + as might be expected for very deep trees, because prior to this change, for + any relative name length longer than 8KiB, rm -r would sacrifice official + conformance to avoid the disproportionate O(N^2) performance penalty. + Leading to another improvement: + + rm -r is now slightly more standards-conformant when operating on + write-protected relative file names longer than 8KiB. + * Noteworthy changes in release 7.6 (2009-09-11) [stable] diff --git a/m4/jm-macros.m4 b/m4/jm-macros.m4 index f4d43f1dd..75ee75e2d 100644 --- a/m4/jm-macros.m4 +++ b/m4/jm-macros.m4 @@ -92,6 +92,9 @@ AC_DEFUN([coreutils_MACROS], # for cp.c AC_CHECK_FUNCS_ONCE([utimensat]) + # for remove.c + AC_CHECK_FUNCS_ONCE([faccessat]) + dnl This can't use AC_REQUIRE; I'm not quite sure why. cu_PREREQ_STAT_PROG diff --git a/src/remove.c b/src/remove.c index 32f67a181..2db385909 100644 --- a/src/remove.c +++ b/src/remove.c @@ -172,6 +172,13 @@ write_protected_non_symlink (int fd_cwd, mess up with long file names). */ { + /* Use faccessat if possible, so as to avoid the expense + of processing an N-component name. */ +#if HAVE_FACCESSAT && AT_EACCESS + if (faccessat (fd_cwd, file, W_OK, AT_EACCESS) == 0) + return 0; +#endif + /* This implements #5: */ size_t file_name_len = strlen (full_name); |