RFC replace some locking of i_sem wiht atomic_t

RFC replace some locking of i_sem wiht atomic_t

[Joshua Hudson]

This might be a way to decrease complexity of locking in vfs.

Basic idea: for local filesystems, i_sem gets taken on several objects
only to protect i_nlink.
These can be removed if i_nlink is atomic.

For network filesystems, no amount of locking would ensure atomic
operations anyway, so
probably no loss there.

inode operations would then lock:
 lookup:   parent
 create:   parent
 link:       both parents
 mknod:   parent
 symlink:  parent
 mkdir:     parent
 unlink:    parent
 rmdir:     parent
 truncate: item
 rename:  both parents

A new per-superblock semaphore vfs_link_sem would be created, to be taken
first on both link and rename, dropped as soon as all other locks are taken.
This prevents deadlocks in pathelogical cases. vfs_rename_sem is still needed
(taken after vfs_link_sem) to prevent cycles from being created.

Grabbing the target on link doesn't do much for most filesystems
because the operation
is (or should be) syncronized by the page lock for each directory
pages. If this change
is made, it is possible to remove this locking from all the filesystems.

Note that locking of source or target is no longer necessary. Except
for i_nlink, nothing
can change the source or target anyway.

Comment as you will. I am competent to write this if it is wanted. I
expect however
that I will be flamed to ashes for this suggestion.

Re: RFC replace some locking of i_sem wiht atomic_t

[Joshua Hudson]

On 3/31/06, Joshua Hudson <joshudson@gmail.com> wrote:
> This might be a way to decrease complexity of locking in vfs.
>
> Basic idea: for local filesystems, i_sem gets taken on several objects
> only to protect i_nlink.
> These can be removed if i_nlink is atomic.
>
That doesn't work. Some code in affs I don't understand and the code in ext2
that checks for maximum hard links basically makes this not work. The
ext2 problem is solvable in assembly (adding a new atomic_* operation),
but the affs problem is not.

Scratch that idea.

Herein lies the problem with the current locking scheme:
1. rename locks target if it exists, but target may be created by
link() immediately
after the check&lock procedure.
2. The target of link() is completely unprotected.

Against ext2, this can result in a corrupted filesystem (two directory
entries with
the same name) by a three-way race between two instances of link() and one
unlink().

1. Both instances of link are started with target being the same name
in the same directory.
2. unlink() is started on a different name in the same directory.
3. link() 1 doesn't find a free slot in the first page, moves to the second.
    *rescheduled before locking second page*
4. unlink() finds target in first page, removes it.
5. link() 2 finds free slot in first page, creates entry, finishes
6. link() 1 continues, finds space in second page, creates entry

Re: RFC replace some locking of i_sem wiht atomic_t

[Al Viro]

On Sun, Apr 02, 2006 at 11:01:30AM -0700, Joshua Hudson wrote:
> Herein lies the problem with the current locking scheme:
> 1. rename locks target if it exists, but target may be created by
> link() immediately
> after the check&lock procedure.
> 2. The target of link() is completely unprotected.
 
3. You have failed to RTFS or RTFM.

> Against ext2, this can result in a corrupted filesystem (two directory
> entries with
> the same name) by a three-way race between two instances of link() and one
> unlink().

Not really.
 
> 1. Both instances of link are started with target being the same name
> in the same directory.
> 2. unlink() is started on a different name in the same directory.
> 3. link() 1 doesn't find a free slot in the first page, moves to the second.
>     *rescheduled before locking second page*
> 4. unlink() finds target in first page, removes it.
> 5. link() 2 finds free slot in first page, creates entry, finishes
> 6. link() 1 continues, finds space in second page, creates entry

And this is BS, since link() _does_ grab ->i_sem on directory it modifies.
So does unlink().

Re: RFC replace some locking of i_sem wiht atomic_t

[Joshua Hudson]

On 4/2/06, Al Viro <viro@ftp.linux.org.uk> wrote:
> On Sun, Apr 02, 2006 at 11:01:30AM -0700, Joshua Hudson wrote:
> > Herein lies the problem with the current locking scheme:
> > 1. rename locks target if it exists, but target may be created by
> > link() immediately
> > after the check&lock procedure.
> > 2. The target of link() is completely unprotected.
>
> 3. You have failed to RTFS or RTFM.
>
Ah here we are

directory-locking.txt shows link() does:
lock parent
insure that source is not a directory
lock source

Let me guess, parent means parent of target, not parent of source.
This has been confusing me for months. Thanks for streightning me out.