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.

1 files changed, 10 insertions, 0 deletions

diff --git a/NEWS b/NEWS
index 1825beccb..6cfe8bb1c 100644
--- a/NEWS
+++ b/NEWS
@@ -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]