bug in ext3 htree rename: doesn't delete old name, leaves ino with bad nlink

I've isolated the problem to rename not removing the old name under some circumstances, leaving two names for a file with an nlink of 1. This will reliably reproduce the problem for me, under 2.4.19-ac4 and 2.4.19 (stock) w/ patch-ext3-dxdir-2.4.19-4.

Generate a new filesystem: this will create htree-bug.fs

$ sh genfs

# mkdir m
# mount -o loop htree-bug.fs m

$ gcc -o tickle tickle.c
$ ./tickle m/test
*** rename("drivers/scsi/psi240i.h", "drivers/scsi/psi240i.h.orig") failure:
stating drivers/scsi/psi240i.h
  ino=294
  nlink=1
stating drivers/scsi/psi240i.h.orig
  ino=294
  nlink=1
*** rename("drivers/scsi/sun3_scsi.h", "drivers/scsi/sun3_scsi.h.orig") failure:
stating drivers/scsi/sun3_scsi.h
  ino=350
  nlink=1
stating drivers/scsi/sun3_scsi.h.orig
  ino=350
  nlink=1

# umount m

$ e2fsck -f htree-bug.fs
e2fsck 1.30-WIP (30-Sep-2002)
Pass 1: Checking inodes, blocks, and sizes
Pass 2: Checking directory structure
Pass 3: Checking directory connectivity
Pass 4: Checking reference counts
Inode 294 ref count is 1, should be 2.  Fix<y>? yes

Inode 350 ref count is 1, should be 2. Fix<y>? yes

Pass 5: Checking group summary information

htree-bug.fs: ***** FILE SYSTEM WAS MODIFIED ***** htree-bug.fs: 541/10240 files (0.2% non-contiguous), 1369/10240 blocks exit status 1

$ debugfs htree-bug.fs 
debugfs 1.30-WIP (30-Sep-2002)
debugfs:  ncheck 294
Inode   Pathname
294     /test/drivers/scsi/psi240i.h
debugfs:  ncheck 350
Inode   Pathname
350     /test/drivers/scsi/sun3_scsi.h

I've put all the bits needed to reproduce the bug (genfs, tickle) at
http://www.goop.org/~jeremy/htree/

J

-------------------------------------------------------
This SF.net email is sponsored by: ApacheCon, November 18-21 in Las Vegas (supported by COMDEX), the only Apache event to be fully supported by the ASF. http://www.apachecon.com
_______________________________________________
Ext2-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/ext2-devel

Thanks again for the nice bug report.

I think I understand the problem now. What happen was, in ext3_rename, it will first add the new entry to directory and then remove the old entry. In this case, when add a new entry to the directory cause a leaf node split. And the old entry is in the very same leaf node. After split, the old entry have been move to another leaf node. But ext3_rename still holding the old pointer and bh to the old leaf node.

This also raise an interesting question, after split leave node, do we need to update the dentry cache for the change?

Thanks again for the nice bug report.

I think I understand the problem now. What happen was, in ext3_rename, it will first add the new entry to directory and then remove the old entry. In this case, when add a new entry to the directory cause a leaf node split. And the old entry is in the very same leaf node. After split, the old entry have been move to another leaf node. But ext3_rename still holding the old pointer and bh to the old leaf node.

It will try to delete the entry from old leaf node, and of course, it can't find it.

You know the rest of the story then.

The old ext3 code is OK because it only append new blocks, it will not change the previous block.

This also raise an interesting question, after split leave node, do we need to update the dentry cache for the change?

I will try to post a patch tonight (pacific time) to fix this problem.

Cheers.

Chris

Quoted 63 lines · Jeremy Fitzhardinge

I've isolated the problem to rename not removing the old name under some circumstances, leaving two names for a file with an nlink of 1. This will reliably reproduce the problem for me, under 2.4.19-ac4 and 2.4.19 (stock) w/ patch-ext3-dxdir-2.4.19-4.

Generate a new filesystem: this will create htree-bug.fs

$ sh genfs

# mkdir m
# mount -o loop htree-bug.fs m

$ gcc -o tickle tickle.c
$ ./tickle m/test
*** rename("drivers/scsi/psi240i.h", "drivers/scsi/psi240i.h.orig") failure:
stating drivers/scsi/psi240i.h
  ino=294
  nlink=1
stating drivers/scsi/psi240i.h.orig
  ino=294
  nlink=1
*** rename("drivers/scsi/sun3_scsi.h", "drivers/scsi/sun3_scsi.h.orig") failure:
stating drivers/scsi/sun3_scsi.h
  ino=350
  nlink=1
stating drivers/scsi/sun3_scsi.h.orig
  ino=350
  nlink=1

# umount m

$ e2fsck -f htree-bug.fs
e2fsck 1.30-WIP (30-Sep-2002)
Pass 1: Checking inodes, blocks, and sizes
Pass 2: Checking directory structure
Pass 3: Checking directory connectivity
Pass 4: Checking reference counts
Inode 294 ref count is 1, should be 2.  Fix<y>? yes

Inode 350 ref count is 1, should be 2. Fix<y>? yes

Pass 5: Checking group summary information

htree-bug.fs: ***** FILE SYSTEM WAS MODIFIED ***** htree-bug.fs: 541/10240 files (0.2% non-contiguous), 1369/10240 blocks exit status 1

$ debugfs htree-bug.fs 
debugfs 1.30-WIP (30-Sep-2002)
debugfs:  ncheck 294
Inode   Pathname
294     /test/drivers/scsi/psi240i.h
debugfs:  ncheck 350
Inode   Pathname
350     /test/drivers/scsi/sun3_scsi.h

I've put all the bits needed to reproduce the bug (genfs, tickle) at
http://www.goop.org/~jeremy/htree/

J

Quoted 8 lines

-------------------------------------------------------
This SF.net email is sponsored by: ApacheCon, November 18-21 in Las Vegas (supported by COMDEX), the only Apache event to be fully supported by the ASF. http://www.apachecon.com
_______________________________________________
Ext2-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/ext2-devel

-------------------------------------------------------
This sf.net email is sponsored by: See the NEW Palm Tungsten T handheld. Power & Color in a compact size!
http://ads.sourceforge.net/cgi-bin/redirect.pl?palm0001en
_______________________________________________
Ext2-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/ext2-devel

This should fix the ext3 htree rename problem. Please try it again.

This should fix the ext3 htree rename problem. Please try it again.

11/06 08:17:31 renamed from 11/06 07:19:11 1.2 +9 -1

-       ext3_delete_entry(handle, old_dir, old_de, old_bh);
+       retval = ext3_delete_entry(handle, old_dir, old_de, old_bh);
+       if (retval == -ENOENT) {
+               /*
+                * old_de can be moved during ext3_add_entry.
+                */
+               struct buffer_head * old_bh2;
+               struct ext3_dir_entry_2 * old_de2;
+               old_bh2 = ext3_find_entry (old_dentry, &old_de2);
+               if (old_bh2) {

Quoted 1 line · On Wed, Nov 06, 2002 at 12:25:00AM -0800, [email protected] wrote:

This should fix the ext3 htree rename problem. Please try it again.

I've looked over the patch, and I've got some comments....

11/06 08:17:31 line 2094

Quoted 3 lines

handle = ext3_journal_start(old_dir, 2 * EXT3_DATA_TRANS_BLOCKS +

11/06 08:17:31 renamed from 11/06 07:19:11 1.2 +1 -1

-                                       EXT3_INDEX_EXTRA_TRANS_BLOCKS + 2);
+                                       EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3);

There's no need to increase the number of blocks that might need to be dirtied; if ext3_delete_entry() can't find the missing entry, it won't dirty the block, so the number of blocks that might need to modified remains constant.

Quoted 20 lines

11/06 08:17:31 renamed from 11/06 07:19:11 1.2 +17 -1

-       ext3_delete_entry(handle, old_dir, old_de, old_bh);
+       retval = ext3_delete_entry(handle, old_dir, old_de, old_bh);
+       if (retval == -ENOENT) {
+               /*
+                * old_de can be moved during ext3_add_entry.
+                */
+               struct buffer_head * old_bh2;
+               struct ext3_dir_entry_2 * old_de2;
+               old_bh2 = ext3_find_entry (old_dentry, &old_de2);
+               if (old_bh2) {
+                       retval = ext3_delete_entry(handle, old_dir, old_de2,
+                                                  old_bh2);
+                       brelse(old_bh2);
+               } else {
+                       ext3_warning(old_dir->i_sb, "ext3_rename",
+                                    "Deleting old file not found (%lu), %d",
+                                    old_dir->i_ino, old_dir->i_nlink);
+               }

Quoted 1 line

+ }

Simply retrying the ext3_delete_entry() isn't sufficient, since another ext3_add_entry() could move the directory entry again while you're reading in the blocks as part of ext3_find_entry(). OK, that would be pretty rare, since enough other directory adds would have to fill up enough that another split could happen, but *is* possible. (Surely our scheduler isn't that unfair....)

Probably a better thing to do is use a while loop, and retry as long
(a) ext3_delete_entry fails, and (b) old_dir->i_version has changed. In practice this will probably never happen, but I'll feel better with that change.

Anyway, I plan to make these two changes to your patch, and then submit it to Linus.

Quoted 6 lines

Simply retrying the ext3_delete_entry() isn't sufficient, since another ext3_add_entry() could move the directory entry again while you're reading in the blocks as part of ext3_find_entry(). OK, that would be pretty rare, since enough other directory adds would have to fill up enough that another split could happen, but *is* possible. (Surely our scheduler isn't that unfair....)

I think we have the lock on ext3_rename. I might be wrong. If other process can change the dir between the add new entry and delete old entry. We should also need to check the entry have been delete from other process in case fall into dead loop?

Do you have time to look at the missing "." and ".." entry patch?

Can you please change my email address in source file to vmware if you submit it?

We take the BKL, yes; but if we need to sleep waiting for a block to be read in, that's when another process can run. Yes, that means another process could end up deleting the entry out from under us --- or make some other change to the directory. I was actually quite nervous about this, so I spent some time auditing the code paths of when do_split() might sleep, to make sure it would never leave the directory in an unstable condition.

HUH?

->rename() holds ->i_sem on both directories. So do all other directory methods. What the hell is going on there?

Quoted 5 lines · Christopher Li

I think we have the lock on ext3_rename. I might be wrong. If other process can change the dir between the add new entry and delete old entry. We should also need to check the entry have been delete from other process in case fall into dead loop?

We take the BKL, yes; but if we need to sleep waiting for a block to be read in, that's when another process can run. Yes, that means another process could end up deleting the entry out from under us --- or make some other change to the directory. I was actually quite

nervous about this, so I spent some time auditing the code paths of when do_split() might sleep, to make sure it would never leave the directory in an unstable condition.

Things will actually get easier once we fine-grain lock ext3 (and remove the BKL), since we'll very likely end up locking the directory during an insert, rename, or delete, and so we don't have to worry about things happening in an interleaved fashion.

I wasn't able to find your e-mail address in the source file.... grep -i chrisl fs/ext3/*.c didn't turn up anything?

Quoted 9 lines · Theodore Ts'o

Quoted 1 line · On Wed, Nov 06, 2002 at 12:25:00AM -0800, [email protected] wrote:

This should fix the ext3 htree rename problem. Please try it again.

I've looked over the patch, and I've got some comments....

Quoted 3 lines

handle = ext3_journal_start(old_dir, 2 * EXT3_DATA_TRANS_BLOCKS +

11/06 08:17:31 renamed from 11/06 07:19:11 1.2 +1 -1

-                                    EXT3_INDEX_EXTRA_TRANS_BLOCKS + 2);
+                                    EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3);

Quoted 4 lines

There's no need to increase the number of blocks that might need to be dirtied; if ext3_delete_entry() can't find the missing entry, it won't dirty the block, so the number of blocks that might need to modified remains constant.

Even for the same block dirty twice? I am not sure about that case so I put it there. I got a lots of thing to do tonight.

Quoted 6 lines

Simply retrying the ext3_delete_entry() isn't sufficient, since another ext3_add_entry() could move the directory entry again while you're reading in the blocks as part of ext3_find_entry(). OK, that would be pretty rare, since enough other directory adds would have to fill up enough that another split could happen, but *is* possible. (Surely our scheduler isn't that unfair....)

I think we have the lock on ext3_rename. I might be wrong. If other process can change the dir between the add new entry and delete old entry. We should also need to check the entry have been delete from other process in case fall into dead loop?