From: Jim Meyering <jim@meyering.net>
To: vineet chadha <...>
Cc: bug-coreutils@gnu.org
Subject: Re: Remove Utility- need guidance
Date: Fri, 10 Mar 2006 22:51:25 +0100
Message-ID: <87y7ziufxe.fsf@rho.meyering.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Lines: 96

vineet chadha <...> wrote:
> I a grad at Univ of Florida and working to develop an application
> (copy-on-write) for my research. When working on it, I found remove
> utility "circular directory test" little intriguing. Here is the reason:
>
> Modern operating system put the in-core inode into free list and
> sometimes re-allocates inode immediately to NEXT creation of file system
> object. remove UTILITY heavily works on assumption that
> directory-to-be-deleted is of single thread and not being modified by
> other user or prcoess. Sepcifically, I will give you as example of my
> copy-on-write implementation. i have been trying to replicate  a directory
> hierarchy from main server to a dummy server called as shadow server
> dynamically. Now if I issue "rm -rf", due to certain restrictions my
> implementation starts replicating file ( untill it is already done so) in
> shadow server and subsequetnly delete it and update state of corresponding
> dir in a hash table. Point is that during is process of remove, directory
> is also being changed (as being replicated). Since, OS is allocating
> inodes, almost most of time, remove fails on circular directory structure
> as OS has reallocated the inode to newly replicated file object in same
> diretory hierachy. So, probabiity of matching inode in state buffer
> (stored as power of two) is almost certain.
>
> I confirmed this phenomenon ( though not conistently ) through running two
> scripts (one creating 10000 dir hierachy and other deleting it. I tried
> nearly 10 times and it failed 2 times (even though it is completely
> different dir) .
> I am thinking to work on a patch for the same. Please comment on issue.

Thank you very much for tracking that down and reporting it!
I reproduced the problem like this:

(mkdir x && cd x && perl -e 'while (1) { mkdir int rand 9999 }') &
pid=$!
sleep 3; rm -rf x
kill $pid

Here's the output I got, using ReiserFS3[*] on linux-2.6.15 with
the latest version of GNU rm:

    rm: WARNING: Circular directory structure.
    This almost certainly means that you have a corrupted file system.
    NOTIFY YOUR SYSTEM MANAGER.
    The following directory is part of the cycle:
      `x'

    [Exit 1]

[*] I tried a few times using ext3, xfs, and tmpfs, but the above
did not trigger the failure.  Different inode-reuse policy, I suppose.

--------------------
Here's a fix for the CVS trunk (it'll also go onto the b5 branch,
from which coreutils-5.95 will come).

2006-03-10  Jim Meyering  <jim@meyering.net>

	* src/remove.c (AD_pop_and_chdir): Fix a bug whereby a user with
	write access to a directory being removed could cause the removal
	of that directory to fail with an erroneous diagnostic about a
	directory cycle.  Reported by Vineet Chadha.

Index: remove.c
===================================================================
RCS file: /fetish/cu/src/remove.c,v
retrieving revision 1.146
diff -u -p -r1.146 remove.c
--- remove.c	12 Feb 2006 07:55:38 -0000	1.146
+++ remove.c	10 Mar 2006 21:21:22 -0000
@@ -391,7 +391,9 @@ ds_free (Dirstack_state *ds)
 static void
 AD_pop_and_chdir (DIR **dirp, Dirstack_state *ds, char **prev_dir)
 {
-  enum RM_status old_status = AD_stack_top(ds)->status;
+  struct AD_ent *leaf_dir_ent = AD_stack_top(ds);
+  struct dev_ino leaf_dev_ino = leaf_dir_ent->dev_ino;
+  enum RM_status old_status = leaf_dir_ent->status;
   struct AD_ent *top;
 
   /* Get the name of the current (but soon to be `previous') directory
@@ -402,6 +404,16 @@ AD_pop_and_chdir (DIR **dirp, Dirstack_s
   pop_dir (ds);
   top = AD_stack_top (ds);
 
+  /* If the directory we're about to leave (and try to rmdir)
+     is the one whose dev_ino is being used to detect a cycle,
+     reset cycle_check_state.dev_ino to that of the parent.
+     Otherwise, once that directory is removed, its dev_ino
+     could be reused in the creation (by some other process)
+     of a directory that this rm process would encounter,
+     which would result in a false-positive cycle indication.  */
+  if (SAME_INODE (ds->cycle_check_state.dev_ino, leaf_dev_ino))
+    ds->cycle_check_state.dev_ino = top->dev_ino;
+
   /* Propagate any failure to parent.  */
   UPDATE_STATUS (top->status, old_status);