Al Viro <viro@xxxxxxxxxxxxxxxxxx> 于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)
