Documentation/filesystems/directory-locking.rst

7 kinds of locks - per-inode (->i_rwsem) and per-filesystem
8 (->s_vfs_rename_mutex).
10 When taking the i_rwsem on multiple non-directory objects, we
22 3) object removal.  Locking rules: caller locks parent, finds victim,
25 4) rename() that is _not_ cross-directory.  Locking rules: caller locks
26 the parent and finds source and target.  Then we decide which of the
27 source and target need to be locked.  Source needs to be locked if it's a
28 non-directory; target - if it's a non-directory or about to be removed.
31 non-directories - the source because it wouldn't be locked otherwise
32 and the target because mixing directory and non-directory is allowed
38 	* lock parent
45 6) cross-directory rename.  The trickiest in the whole bunch.  Locking
50 	  the other, lock the parent of source first.
52 	* if old parent is equal to or is a descendent of target
53 	  fail with -ENOTEMPTY
54 	* if new parent is equal to or is a descendent of source
55 	  fail with -ELOOP
57 	* Lock non-directories involved, in inode pointer order.
60 All ->i_rwsem are taken exclusive.
63 read, modified or removed by method will be locked by caller.
66 If no directory is its own ancestor, the scheme above is deadlock-free.
72 	objects - A < B iff (A is an ancestor of B) or (B is not an ancestor
77 (1) if object removal or non-cross-directory rename holds lock on A and
78     attempts to acquire lock on B, A will remain the parent of B until we
79     acquire the lock on B.  (Proof: only cross-directory rename can change
80     the parent of object and it would have to lock the parent).
82 (2) if cross-directory rename holds the lock on filesystem, order will not
83     change until rename acquires all locks.  (Proof: other cross-directory
87 (3) locks on non-directory objects are acquired only after locks on
90     non-directory object, except renames, which take locks on source and
97 Thus all processes are blocked on ->i_rwsem.
99 By (3), any process holding a non-directory lock can only be
100 waiting on another non-directory lock with a larger address.  Therefore
102 non-directory objects are not included in the set of contended locks.
104 Thus link creation can't be a part of deadlock - it can't be
107 Any contended object is either held by cross-directory rename or
109 operation other than cross-directory rename.  Then the lock this operation
112 It means that one of the operations is cross-directory rename.
113 Otherwise the set of contended objects would be infinite - each of them
115 own descendent.  Moreover, there is exactly one cross-directory rename
118 Consider the object blocking the cross-directory rename.  One
119 of its descendents is locked by cross-directory rename (otherwise we
121 means that cross-directory rename is taking locks out of order.  Due
123 But locking rules for cross-directory rename guarantee that we do not
129 the only operation that could introduce loops is cross-directory rename.
130 Since the only new (parent, child) pair added by rename() is (new parent,
133 rename() responsible for that would be holding filesystem lock and new parent
135 new parent had been equal to or a descendent of source since the moment when
136 we had acquired filesystem lock and rename() would fail with -ELOOP in that
142 also preserved by all operations (cross-directory rename on a tree that would