Documentation/filesystems/directory-locking.rst

12 that "inode pointer" order in the following.
37 	* check that the source is not a directory
40 5. rename that is _not_ cross-directory.  Locking rules:
47 	* take the locks that need to be taken (exclusive), in inode pointer order
48 	  if need to take both (that can happen only when both source and target
51 	  allowed only with RENAME_EXCHANGE, and that won't be removing the target).
60 	* verify that the source is not a descendent of the target and
65 The rules above obviously guarantee that all directories that are going
78 that's not a problem, but there is a nasty twist - what should we do
79 when one growing tree reaches the root of another?  That can happen in
83 possibility that directory we see in one place gets moved by the server
88 a subdirectory that already has an alias, something needs to be done with
95 First of all, we verify that it is *not* an ancestor of our directory
101 Note that splicing does *not* involve any modification of the filesystem;
123 on that filesystem" should be an asymmetric relation (or, if you will,
124 it should be possible to rank the filesystems so that directory operation
137 There is a ranking on the locks, such that all primitives take
144   * put ->s_vfs_rename_mutex at rank lower than that of any ->i_rwsem
152   2. ->i_rwsem of directories on that NFS filesystem, same rank for all
153   3. ->i_rwsem of non-directories on that filesystem, in order of
160 It's easy to verify that operations never take a lock with rank
161 lower than that of an already held lock.
170 Moreover, without loss of generality we can assume that all operations
171 are done directly to that filesystem and none of them has actually
175 and the same number of directories (D1,...,Dn) such that
186 one directory and blocked on attempt to lock another.  That leaves
201 generality we can assume that T1 is the one doing a cross-directory
204 In other words, we have a cross-directory rename that locked
209 has acquired filesystem lock and verified that directories involved have
210 a common ancestor, which guarantees that ancestry relationships between
232 That leaves only one possibility - namely, both Dn and D1 are
233 among the children, in some order.  But that is also impossible, since
236 That concludes the proof, since the set of operations with the
239 Note that the check for having a common ancestor in cross-directory
244 descendent of the parent of target.   At that point we have cross-directory
254 the only operation that could introduce loops is cross-directory rename.
256 loops before the operation, at least on of the nodes in that loop must've
272 target or source resp.  After that the loop would follow the chain of
273 ancestors of that parent.  But as we have just shown, that chain must
274 end after a finite number of steps, which means that it can't be a part
278 ability to check that directory is a descendent of another object.  Current
279 implementation assumes that directory graph is a tree.  This assumption is
280 also preserved by all operations (cross-directory rename on a tree that would
283 Notice that "directory" in the above == "anything that might have
285 either to make sure that link(2) doesn't work for them or to make changes
286 in is_subdir() that would make it work even in presence of such beasts.