Locking issue with directory renames

Hello!

I've some across an interesting issue that was spotted by syzbot [1]. The report is against UDF but AFAICS the problem exists for ext4 as well and possibly other filesystems. The problem is the following: When we are renaming directory 'dir' say rename("foo/dir", "bar/") we lock 'foo' and 'bar' but 'dir' is unlocked because the locking done by vfs_rename() is

        if (!is_dir || (flags & RENAME_EXCHANGE))
                lock_two_nondirectories(source, target);
        else if (target)
                inode_lock(target);

However some filesystems (e.g. UDF but ext4 as well, I suspect XFS may be hurt by this as well because it converts among multiple dir formats) need to update parent pointer in 'dir' and nothing protects this update against a race with someone else modifying 'dir'. Now this is mostly harmless because the parent pointer (".." directory entry) is at the beginning of the directory and stable however if for example the directory is converted from packed "in-inode" format to "expanded" format as a result of concurrent operation on 'dir', the filesystem gets corrupted (or crashes as in case of UDF).

So we'd need to lock 'source' if it is a directory. Ideally this would happen in VFS as otherwise I bet a lot of filesystems will get this wrong so could vfs_rename() lock 'source' if it is a dir as well? Essentially this would amount to calling lock_two_nondirectories(source, target) unconditionally but that would become a serious misnomer ;). Al, any thought?

Quoted 23 lines · Jan Kara

Hello!

I've some across an interesting issue that was spotted by syzbot [1]. The report is against UDF but AFAICS the problem exists for ext4 as well and possibly other filesystems. The problem is the following: When we are renaming directory 'dir' say rename("foo/dir", "bar/") we lock 'foo' and 'bar' but 'dir' is unlocked because the locking done by vfs_rename() is

        if (!is_dir || (flags & RENAME_EXCHANGE))
                lock_two_nondirectories(source, target);
        else if (target)
                inode_lock(target);

However some filesystems (e.g. UDF but ext4 as well, I suspect XFS may be hurt by this as well because it converts among multiple dir formats) need to update parent pointer in 'dir' and nothing protects this update against a race with someone else modifying 'dir'. Now this is mostly harmless because the parent pointer (".." directory entry) is at the beginning of the directory and stable however if for example the directory is converted from packed "in-inode" format to "expanded" format as a result of concurrent operation on 'dir', the filesystem gets corrupted (or crashes as in case of UDF).

Quoted 6 lines

So we'd need to lock 'source' if it is a directory. Ideally this would happen in VFS as otherwise I bet a lot of filesystems will get this wrong so could vfs_rename() lock 'source' if it is a dir as well? Essentially this would amount to calling lock_two_nondirectories(source, target) unconditionally but that would become a serious misnomer ;). Al, any thought?

FWIW, I suspect that majority of filesystems that do implement rename do not have that problem. Moreover, on cross-directory rename we already have
* tree topology stabilized
* source guaranteed not to be an ancestor of target or either of
the parents
so the method instance should be free to lock the source if it needs to do so.

Yes, we can lock the source inode in ->rename() if we need it. The snag is that if 'target' exists, it is already locked so when locking 'source' we are possibly not following the VFS lock ordering of i_rwsem by inode address (I don't think it can cause any real dealock but still it looks suspicious). Also we'll have to lock with I_MUTEX_NONDIR2 lockdep class to make lockdep happy but that's just a minor annoyance. Finally, we'll have to check for RENAME_EXCHANGE because in that case, both source and target will be already locked. Thus if we do the additional locking in the filesystem, we will leak quite some details about rename locking into the filesystem which seems undesirable to me.

Quoted 11 lines · Jan Kara

Yes, we can lock the source inode in ->rename() if we need it. The snag is that if 'target' exists, it is already locked so when locking 'source' we are possibly not following the VFS lock ordering of i_rwsem by inode address (I don't think it can cause any real dealock but still it looks suspicious). Also we'll have to lock with I_MUTEX_NONDIR2 lockdep class to make lockdep happy but that's just a minor annoyance. Finally, we'll have to check for RENAME_EXCHANGE because in that case, both source and target will be already locked. Thus if we do the additional locking in the filesystem, we will leak quite some details about rename locking into the filesystem which seems undesirable to me.

Rules for inode locks are simple:
* directories before non-directories
* ancestors before descendents
* for non-directories the ordering is by in-core inode address

So the instances that need that extra lock would do that when source is a directory and non RENAME_EXCHANGE is given. Having the target already locked is irrelevant - if it exists, it's already checked to be a directory as well, and had it been a descendent of source, we would have already found that and failed with -ELOOP.

If A and B are both directories, there's no ordering between them unless one is an ancestor of another - such can be locked in any order. However, one of the following must be true:
* C is locked and both A and B had been observed to be children of C
after the lock on C had been acquired, or
* ->s_vfs_rename_mutex is held for the filesystem containing both
A and B.

Note that ->s_vfs_rename_mutex is there to stabilize the tree topology and make "is A an ancestor of B?" possible to check for more than "A is locked, B is a child of A, so A will remain its ancestor until unlocked"...

Hello!

I've some across an interesting issue that was spotted by syzbot [1]. The report is against UDF but AFAICS the problem exists for ext4 as well and possibly other filesystems. The problem is the following: When we are renaming directory 'dir' say rename("foo/dir", "bar/") we lock 'foo' and 'bar' but 'dir' is unlocked because the locking done by vfs_rename() is

        if (!is_dir || (flags & RENAME_EXCHANGE))
                lock_two_nondirectories(source, target);
        else if (target)
                inode_lock(target);

However some filesystems (e.g. UDF but ext4 as well, I suspect XFS may be hurt by this as well because it converts among multiple dir formats) need to update parent pointer in 'dir' and nothing protects this update against a race with someone else modifying 'dir'. Now this is mostly harmless because the parent pointer (".." directory entry) is at the beginning of the directory and stable however if for example the directory is converted from packed "in-inode" format to "expanded" format as a result of concurrent operation on 'dir', the filesystem gets corrupted (or crashes as in case of UDF).

So we'd need to lock 'source' if it is a directory.

Ideally this would
happen in VFS as otherwise I bet a lot of filesystems will get this wrong so could vfs_rename() lock 'source' if it is a dir as well? Essentially this would amount to calling lock_two_nondirectories(source, target) unconditionally but that would become a serious misnomer ;). Al, any thought?

Quoted 11 lines · Jan Kara

I've some across an interesting issue that was spotted by syzbot [1]. The report is against UDF but AFAICS the problem exists for ext4 as well and possibly other filesystems. The problem is the following: When we are renaming directory 'dir' say rename("foo/dir", "bar/") we lock 'foo' and 'bar' but 'dir' is unlocked because the locking done by vfs_rename() is

        if (!is_dir || (flags & RENAME_EXCHANGE))
                lock_two_nondirectories(source, target);
        else if (target)
                inode_lock(target);

Quoted 9 lines

However some filesystems (e.g. UDF but ext4 as well, I suspect XFS may be hurt by this as well because it converts among multiple dir formats) need to update parent pointer in 'dir' and nothing protects this update against a race with someone else modifying 'dir'. Now this is mostly harmless because the parent pointer (".." directory entry) is at the beginning of the directory and stable however if for example the directory is converted from packed "in-inode" format to "expanded" format as a result of concurrent operation on 'dir', the filesystem gets corrupted (or crashes as in case of UDF).

No, xfs_rename() does not have this problem - we pass four inodes to the function - the source directory, source inode, destination directory and destination inode.

In the above case, "dir/" is passed to XFs as the source inode - the src_dir is "foo/", the target dir is "bar/" and the target inode is null. src_dir != target_dir, so we set the "new_parent" flag. the srouce inode is a directory, so we set the src_is_directory flag, too.

We lock all three inodes that are passed. We do various things, then run:

        if (new_parent && src_is_directory) {
                /*
                 * Rewrite the ".." entry to point to the new
                 * directory.
                 */
                error = xfs_dir_replace(tp, src_ip, &xfs_name_dotdot,
                                        target_dp->i_ino, spaceres);
                ASSERT(error != -EEXIST);
                if (error)
                        goto out_trans_cancel;
        }

which replaces the ".." entry in source inode atomically whilst it is locked. Any directory format changes that occur during the rename are done while the ILOCK is held, so they appear atomic to outside observers that are trying to parse the directory structure (e.g. readdir).

XFS just has a function that allows for an arbitrary number of inodes to be locked in the given order: xfs_lock_inodes(). For rename, the lock order is determined by xfs_sort_for_rename().

Quoted 13 lines · Jan Kara

Hello!

I've some across an interesting issue that was spotted by syzbot [1]. The report is against UDF but AFAICS the problem exists for ext4 as well and possibly other filesystems. The problem is the following: When we are renaming directory 'dir' say rename("foo/dir", "bar/") we lock 'foo' and 'bar' but 'dir' is unlocked because the locking done by vfs_rename() is

        if (!is_dir || (flags & RENAME_EXCHANGE))
                lock_two_nondirectories(source, target);
        else if (target)
                inode_lock(target);

Quoted 9 lines

However some filesystems (e.g. UDF but ext4 as well, I suspect XFS may be hurt by this as well because it converts among multiple dir formats) need to update parent pointer in 'dir' and nothing protects this update against a race with someone else modifying 'dir'. Now this is mostly harmless because the parent pointer (".." directory entry) is at the beginning of the directory and stable however if for example the directory is converted from packed "in-inode" format to "expanded" format as a result of concurrent operation on 'dir', the filesystem gets corrupted (or crashes as in case of UDF).

No, xfs_rename() does not have this problem - we pass four inodes to the function - the source directory, source inode, destination directory and destination inode.

In the above case, "dir/" is passed to XFs as the source inode - the src_dir is "foo/", the target dir is "bar/" and the target inode is null. src_dir != target_dir, so we set the "new_parent" flag. the srouce inode is a directory, so we set the src_is_directory flag, too.

We lock all three inodes that are passed. We do various things, then run:

        if (new_parent && src_is_directory) {
                /*
                 * Rewrite the ".." entry to point to the new
                 * directory.
                 */
                error = xfs_dir_replace(tp, src_ip, &xfs_name_dotdot,
                                        target_dp->i_ino, spaceres);
                ASSERT(error != -EEXIST);
                if (error)
                        goto out_trans_cancel;
        }

which replaces the ".." entry in source inode atomically whilst it is locked. Any directory format changes that occur during the rename are done while the ILOCK is held, so they appear atomic to outside observers that are trying to parse the directory structure (e.g. readdir).

Quoted 1 line

So we'd need to lock 'source' if it is a directory.

Yup, and XFS goes further by always locking the source inode in a rename, even if it is not a directory. This ensures the inode being moved cannot have it's metadata otherwise modified whilst the rename is in progress, even if that modification would have no impact on the rename. It's a pretty strict interpretation of "rename is an atomic operation", but it avoids accidentally missing nasty corner cases like the one described above...

Quoted 6 lines

Ideally this would
happen in VFS as otherwise I bet a lot of filesystems will get this wrong so could vfs_rename() lock 'source' if it is a dir as well? Essentially this would amount to calling lock_two_nondirectories(source, target) unconditionally but that would become a serious misnomer ;). Al, any thought?

XFS just has a function that allows for an arbitrary number of inodes to be locked in the given order: xfs_lock_inodes(). For rename, the lock order is determined by xfs_sort_for_rename().

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]

Quoted 24 lines · Dave Chinner

Quoted 13 lines · Jan Kara

Hello!

I've some across an interesting issue that was spotted by syzbot [1]. The report is against UDF but AFAICS the problem exists for ext4 as well and possibly other filesystems. The problem is the following: When we are renaming directory 'dir' say rename("foo/dir", "bar/") we lock 'foo' and 'bar' but 'dir' is unlocked because the locking done by vfs_rename() is

        if (!is_dir || (flags & RENAME_EXCHANGE))
                lock_two_nondirectories(source, target);
        else if (target)
                inode_lock(target);

Quoted 9 lines

However some filesystems (e.g. UDF but ext4 as well, I suspect XFS may be hurt by this as well because it converts among multiple dir formats) need to update parent pointer in 'dir' and nothing protects this update against a race with someone else modifying 'dir'. Now this is mostly harmless because the parent pointer (".." directory entry) is at the beginning of the directory and stable however if for example the directory is converted from packed "in-inode" format to "expanded" format as a result of concurrent operation on 'dir', the filesystem gets corrupted (or crashes as in case of UDF).

Quoted 3 lines

No, xfs_rename() does not have this problem - we pass four inodes to the function - the source directory, source inode, destination directory and destination inode.

Um, I think it does have this problem. xfs_readdir thinks it can parse a shortform inode without taking the ILOCK:

	if (dp->i_df.if_format == XFS_DINODE_FMT_LOCAL)
		return xfs_dir2_sf_getdents(&args, ctx);

	lock_mode = xfs_ilock_data_map_shared(dp);
	error = xfs_dir2_isblock(&args, &isblock);

So xfs_dir2_sf_replace can rewrite the shortform structure (or even convert it to block format!) while readdir is accessing it. Or am I mising something?

--D

Quoted 54 lines

In the above case, "dir/" is passed to XFs as the source inode - the src_dir is "foo/", the target dir is "bar/" and the target inode is null. src_dir != target_dir, so we set the "new_parent" flag. the srouce inode is a directory, so we set the src_is_directory flag, too.

We lock all three inodes that are passed. We do various things, then run:

        if (new_parent && src_is_directory) {
                /*
                 * Rewrite the ".." entry to point to the new
                 * directory.
                 */
                error = xfs_dir_replace(tp, src_ip, &xfs_name_dotdot,
                                        target_dp->i_ino, spaceres);
                ASSERT(error != -EEXIST);
                if (error)
                        goto out_trans_cancel;
        }

which replaces the ".." entry in source inode atomically whilst it is locked. Any directory format changes that occur during the rename are done while the ILOCK is held, so they appear atomic to outside observers that are trying to parse the directory structure (e.g. readdir).

Quoted 1 line

So we'd need to lock 'source' if it is a directory.

Yup, and XFS goes further by always locking the source inode in a rename, even if it is not a directory. This ensures the inode being moved cannot have it's metadata otherwise modified whilst the rename is in progress, even if that modification would have no impact on the rename. It's a pretty strict interpretation of "rename is an atomic operation", but it avoids accidentally missing nasty corner cases like the one described above...

Quoted 6 lines

Ideally this would
happen in VFS as otherwise I bet a lot of filesystems will get this wrong so could vfs_rename() lock 'source' if it is a dir as well? Essentially this would amount to calling lock_two_nondirectories(source, target) unconditionally but that would become a serious misnomer ;). Al, any thought?

XFS just has a function that allows for an arbitrary number of inodes to be locked in the given order: xfs_lock_inodes(). For rename, the lock order is determined by xfs_sort_for_rename().

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]

Quoted 3 lines · Darrick J. Wong

So xfs_dir2_sf_replace can rewrite the shortform structure (or even convert it to block format!) while readdir is accessing it. Or am I mising something?

True, I missed that.

Hmmmm. ISTR that holding ILOCK over filldir callbacks causes problems with lock ordering{1], and that's why we removed the ILOCK from the getdents path in the first place and instead relied on the IOLOCK being held by the VFS across readdir for exclusion against concurrent modification from the VFS.

Yup, the current code only holds the ILOCK for the extent lookup and buffer read process, it drops it while it is walking the locked buffer and calling the filldir callback. Which is why we don't hold it for xfs_dir2_sf_getdents() - the VFS is supposed to be holding i_rwsem in exclusive mode for any operation that modifies a directory entry. We should only need the ILOCK for serialising the extent tree loading, not for serialising access vs modification to the directory.

So, yeah, I think you're right, Darrick. And the fix is that the VFS needs to hold the i_rwsem correctly for allo inodes that may be modified during rename...

Quoted 22 lines · Dave Chinner

Quoted 3 lines · Darrick J. Wong

So xfs_dir2_sf_replace can rewrite the shortform structure (or even convert it to block format!) while readdir is accessing it. Or am I mising something?

True, I missed that.

Hmmmm. ISTR that holding ILOCK over filldir callbacks causes problems with lock ordering{1], and that's why we removed the ILOCK from the getdents path in the first place and instead relied on the IOLOCK being held by the VFS across readdir for exclusion against concurrent modification from the VFS.

Yup, the current code only holds the ILOCK for the extent lookup and buffer read process, it drops it while it is walking the locked buffer and calling the filldir callback. Which is why we don't hold it for xfs_dir2_sf_getdents() - the VFS is supposed to be holding i_rwsem in exclusive mode for any operation that modifies a directory entry. We should only need the ILOCK for serialising the extent tree loading, not for serialising access vs modification to the directory.

Quoted 3 lines

So, yeah, I think you're right, Darrick. And the fix is that the VFS needs to hold the i_rwsem correctly for allo inodes that may be modified during rename...

But Al Viro didn't want to lock the inode in the VFS (as some filesystems don't need the lock)

Quoted 23 lines · Jan Kara

Quoted 22 lines · Dave Chinner

Quoted 3 lines · Darrick J. Wong

So xfs_dir2_sf_replace can rewrite the shortform structure (or even convert it to block format!) while readdir is accessing it. Or am I mising something?

True, I missed that.

Hmmmm. ISTR that holding ILOCK over filldir callbacks causes problems with lock ordering{1], and that's why we removed the ILOCK from the getdents path in the first place and instead relied on the IOLOCK being held by the VFS across readdir for exclusion against concurrent modification from the VFS.

Yup, the current code only holds the ILOCK for the extent lookup and buffer read process, it drops it while it is walking the locked buffer and calling the filldir callback. Which is why we don't hold it for xfs_dir2_sf_getdents() - the VFS is supposed to be holding i_rwsem in exclusive mode for any operation that modifies a directory entry. We should only need the ILOCK for serialising the extent tree loading, not for serialising access vs modification to the directory.

Quoted 6 lines

Quoted 3 lines

So, yeah, I think you're right, Darrick. And the fix is that the VFS needs to hold the i_rwsem correctly for allo inodes that may be modified during rename...

But Al Viro didn't want to lock the inode in the VFS (as some filesystems don't need the lock)

Was any reason given?

We know we have to modify the ".." entry of the child directory being moved, so I'd really like to understand why the locking rule of "directory i_rwsem must be held exclusively over modifications" so that we can use shared access for read operations has been waived for this specific case.

Apart from exposing multiple filesystems to modifications racing with operations that hold the i_rwsem shared to *prevent concurrent directory modifications*, what performance or scalability benefit is seen as a result of eliding this inode lock from the VFS rename setup?

This looks like a straight forward VFS level directory locking violation, and now we are playing whack-a-mole to fix it in each filesystem we discover that requires the child directory inode to be locked...

Quoted 3 lines

so in ext4 we ended up grabbing the lock in
ext4_rename() like:

Review

Quoted 5 lines

(quoted diff) +5 -0

+               /*
+                * We need to protect against old.inode directory getting
+                * converted from inline directory format into a normal one.
+                */
+               inode_lock_nested(old.inode, I_MUTEX_NONDIR2);

Why are you using the I_MUTEX_NONDIR2 annotation when locking a directory inode? That doesn't seem right.

Further, how do we guarantee correct i_rwsem lock ordering against the all the other inodes that the VFS has already locked and/or other multi-inode i_rwsem locking primitives in the VFS?