[PATCH] Documentation: fs: fix directory locking proofs

[PATCH] Documentation: fs: fix directory locking proofs

[Mo Zou]

Commit 28eceeda130f ("fs: Lock moved directories") acquires locks also for
directories when they are moved and updates the deadlock-freedom proof
to claim "a linear ordering of the objects - A < B iff (A is an ancestor
of B) or (B is an ancestor of A and ptr(A) < ptr(B))". This claim,
however, is not correct. Because cross-directory rename may acquire two
parents (old parent and new parent) and two child directories (source
and target) and the ordering between old parent and target (or new parent
and source) may not fall into the above cases, i.e. ptr(old parent) <
ptr(target) may not hold. We should revert to previous description that
"at any moment we have a partial ordering of the objects - A < B iff A is
an ancestor of B".

Signed-off-by: Mo Zou <lostzoumo@gmail.com>
---
 Documentation/filesystems/directory-locking.rst | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/Documentation/filesystems/directory-locking.rst b/Documentation/filesystems/directory-locking.rst
index dccd61c7c5c3..5b26ecd9f0db 100644
--- a/Documentation/filesystems/directory-locking.rst
+++ b/Documentation/filesystems/directory-locking.rst
@@ -67,9 +67,8 @@ If no directory is its own ancestor, the scheme above is deadlock-free.
 
 Proof:
 
-	First of all, at any moment we have a linear ordering of the
-	objects - A < B iff (A is an ancestor of B) or (B is not an ancestor
-        of A and ptr(A) < ptr(B)).
+	First of all, at any moment we have a partial ordering of the
+	objects - A < B iff A is an ancestor of B.
 
 	That ordering can change.  However, the following is true:
 
-- 
2.30.1 (Apple Git-130)

Re: [PATCH] Documentation: fs: fix directory locking proofs

[Al Viro]

On Wed, Oct 11, 2023 at 01:28:15PM +0800, Mo Zou wrote:
> Commit 28eceeda130f ("fs: Lock moved directories") acquires locks also for
> directories when they are moved and updates the deadlock-freedom proof
> to claim "a linear ordering of the objects - A < B iff (A is an ancestor
> of B) or (B is an ancestor of A and ptr(A) < ptr(B))". This claim,
> however, is not correct. Because cross-directory rename may acquire two
> parents (old parent and new parent) and two child directories (source
> and target) and the ordering between old parent and target (or new parent
> and source) may not fall into the above cases, i.e. ptr(old parent) <
> ptr(target) may not hold. We should revert to previous description that
> "at any moment we have a partial ordering of the objects - A < B iff A is
> an ancestor of B".

Not quite.  I agree that the proof needs fixing, but your change doesn't
do it.

The thing is, the ordering in "neither is an ancestor of another" case
of lock_two_directories() does, unfortunately, matter.  That's new,
subtle and not adequately discussed.

Another thing is that callers of lock_two_nondirectories() are not
covered at all.

I'll put something together and post it; it's 2:45am here at the moment,
and I'd rather get some sleep first.

Re: [PATCH] Documentation: fs: fix directory locking proofs

[Mo Zou]

Al Viro <viro@zeniv.linux.org.uk> 于2023年10月11日周三 14:46写道：
>
> On Wed, Oct 11, 2023 at 01:28:15PM +0800, Mo Zou wrote:
> > Commit 28eceeda130f ("fs: Lock moved directories") acquires locks also for
> > directories when they are moved and updates the deadlock-freedom proof
> > to claim "a linear ordering of the objects - A < B iff (A is an ancestor
> > of B) or (B is an ancestor of A and ptr(A) < ptr(B))". This claim,
> > however, is not correct. Because cross-directory rename may acquire two
> > parents (old parent and new parent) and two child directories (source
> > and target) and the ordering between old parent and target (or new parent
> > and source) may not fall into the above cases, i.e. ptr(old parent) <
> > ptr(target) may not hold. We should revert to previous description that
> > "at any moment we have a partial ordering of the objects - A < B iff A is
> > an ancestor of B".
>
> Not quite.  I agree that the proof needs fixing, but your change doesn't
> do it.
>
> The thing is, the ordering in "neither is an ancestor of another" case
> of lock_two_directories() does, unfortunately, matter.  That's new,
> subtle and not adequately discussed.
>
> Another thing is that callers of lock_two_nondirectories() are not
> covered at all.
>
> I'll put something together and post it; it's 2:45am here at the moment,
> and I'd rather get some sleep first.

When trying to write a fix for the proof, I seem to encounter a corner
case that could lead to deadlocks. The key problem is that the code
introduces more inode-pointer orders between directories (originally,
there is at most one such order for cross-directory rename) and
inode-pointer orders are not compatible with ancestor orders, i.e.
they do not give a linear order!

Consider directories objects A, B, C. The pointer orders are that A < B
and C < A. And B is ancestor to C, so B < C. Thus we have A < B < C
< A!

A concrete deadlock  example can be constructed as follows. Suppose
the tree has following edges /A and /B/C and A < B and C < A. There are
three operations forming a deadlock.

rename(/A, /B) executes: lock /; lock A; (about to lock B)
unlink(/B/C) executes: lock B; (about to lock C)
rename(/A/x, /C/y) executes: lock C; (about to lock A)

Re: [PATCH] Documentation: fs: fix directory locking proofs

[Al Viro]

On Wed, Oct 11, 2023 at 10:11:42PM +0800, Mo Zou wrote:
> 
> Consider directories objects A, B, C. The pointer orders are that A < B
> and C < A. And B is ancestor to C, so B < C. Thus we have A < B < C
> < A!
> 
> A concrete deadlock  example can be constructed as follows. Suppose
> the tree has following edges /A and /B/C and A < B and C < A. There are
> three operations forming a deadlock.
> 
> rename(/A, /B) executes: lock /; lock A; (about to lock B)
> unlink(/B/C) executes: lock B; (about to lock C)
> rename(/A/x, /C/y) executes: lock C; (about to lock A)

Nope - your C in line 2 is not C in line 3.

There *IS* a deadlock, but it's more subtle than that.
Look:
# address(/X/A) < address(C) < address(X)
T_1: rename /C/D /X/A/B
T_2: exchange /X /C
T_3: rmdir /X/A
T_1:	looked up /X/A and /C (all in dcache)
T_2:	looked up /
T_3:	looked up /X
T_1:	grabbed ->s_vfs_rename_mutex
T_1:	grabbed /X/A
T_2:	grabbed /
T_2:	grabbed /C
T_3:	grabbed /X
T_2:	tries to grab /X
T_3:	tries to grab /X/A
T_1:	tries to grab /C