bug-coreutils
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[PATCH] rm: improve efficiency of rm -r (without -f) from O(N^2) to O(N)


From: Jim Meyering
Subject: [PATCH] rm: improve efficiency of rm -r (without -f) from O(N^2) to O(N)
Date: Thu, 03 Sep 2009 15:42:49 +0200

I suppose this deserves mention in NEWS, too.

Not only does this fix a long-standing performance problem
with rm -r (but not with -f, which is already efficient),
but it makes rm -r behave correctly also for names longer than 8 KiB,
if your system has support for the faccessat system call.

While the O(N^2) -> O(N) improvement is real, it is not as great
as you might expect because we capped the length (in remove.c)
of the file for which we would try to toe the standards line.
For longer names, we punted and used possibly inaccurate
permission bits (see remove.c for details).

Now, however, on modern systems, rm is correct, efficient,
and its core in remove.c is almost completely thread-safe.

I've just pushed this to next.


>From d0c1381739cc1dbad8f9a9e8e2246d0a80f4acea Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Thu, 3 Sep 2009 15:15:09 +0200
Subject: [PATCH] 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.
---
 m4/jm-macros.m4 |    3 +++
 src/remove.c    |    7 +++++++
 2 files changed, 10 insertions(+), 0 deletions(-)

diff --git a/m4/jm-macros.m4 b/m4/jm-macros.m4
index 416a0af..934d4ed 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 32f67a1..2db3859 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);

--
1.6.4.2.395.ge3d52




reply via email to

[Prev in Thread] Current Thread [Next in Thread]