Lines Matching full:of
7 kinds of locks - per-inode (->i_rwsem) and per-filesystem
44 * decide which of the source and target need to be locked.
58 ancestor of the other, lock the parent of source first.
60 * verify that the source is not a descendent of the target and
61 target is not a descendent of source; fail the operation otherwise.
73 in its own right; it may happen as part of lookup. We speak of the
75 picture of those - especially for network filesystems. What we have
76 is a bunch of subtrees visible in dcache and locking happens on those.
79 when one growing tree reaches the root of another? That can happen in
81 from the same NFS4 server and doing lookups in one of them has reached
82 the root of another"; there's also open-by-fhandle stuff, and there's a
86 For a lot of reasons we want to have the same directory present in dcache
90 a root of separate tree, it gets attached to the directory we are doing a
92 a child of the directory we are looking in, it changes name to the one
94 However, if it's a child of some other directory, the things get trickier.
95 First of all, we verify that it is *not* an ancestor of our directory
97 current parent of the alias. If either trylock fails, we fail the lookup.
101 Note that splicing does *not* involve any modification of the filesystem;
104 filesystem lock prevents any changes of tree topology, other than having a
105 root of one tree becoming a child of directory in another. In particular,
108 the lock is dropped. So from the directory operations' point of view
138 them in order of non-decreasing rank. Namely,
140 * rank ->i_rwsem of non-directories on given filesystem in inode pointer
142 * put ->i_rwsem of all directories on a filesystem at the same rank,
143 lower than ->i_rwsem of any non-directory on the same filesystem.
144 * put ->s_vfs_rename_mutex at rank lower than that of any ->i_rwsem
147 rank of those filesystems.
151 1. ->s_vfs_rename_mutex of NFS filesystem
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
154 increasing address of inode
155 4. ->s_vfs_rename_mutex of local filesystem
156 5. ->i_rwsem of directories on the local filesystem, same rank for all
157 6. ->i_rwsem of non-directories on local filesystem, in order of
158 increasing address of inode.
161 lower than that of an already held lock.
164 set of threads. It is a cycle of several threads, each blocked on a lock
168 contended locks in the minimal deadlock will be of the same rank,
169 i.e. they all will be ->i_rwsem of directories on the same filesystem.
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
174 In other words, we have a cycle of threads, T1,..., Tn,
175 and the same number of directories (D1,...,Dn) such that
189 cross-directory rename of some sort.
192 if all operations had been of the "lock parent, then child" sort
193 we would have Dn a parent of D1, which is a parent of D2, which is
194 a parent of D3, ..., which is a parent of Dn. Relationships couldn't
200 more than one cross-directory rename among them. Without loss of
202 rename and everything else is of the "lock parent, then child" sort.
205 Dn and blocked on attempt to lock D1, which is a parent of D2, which is
206 a parent of D3, ..., which is a parent of Dn. Relationships between
211 all of them had been stable.
218 It can't be the parents - indeed, since D1 is an ancestor of Dn,
219 it would be the first parent to be locked. Therefore at least one of the
220 children must be involved and thus neither of them could be a descendent
221 of another - otherwise the operation would not have progressed past
226 would have to be a descendent of its child.
228 It can't be a parent and a child of another parent either.
229 Otherwise the child of the parent in question would've been a descendent
230 of another child.
234 neither of the children is a descendent of another.
236 That concludes the proof, since the set of operations with the
242 parent of source, then try to lock the parent of target, only to have
243 an unrelated lookup splice a distant ancestor of source to some distant
244 descendent of the parent of target. At that point we have cross-directory
245 rename holding the lock on parent of source and trying to lock its
246 distant ancestor. Add a bunch of rmdir() attempts on all directories
247 in between (all of those would fail with -ENOTEMPTY, had they ever gotten
256 loops before the operation, at least on of the nodes in that loop must've
258 the source or, in case of exchange, possibly the target.
261 been ancestors of each other. Therefore the chain of ancestors starting
262 in the parent of source could not have passed through the target and
263 vice versa. On the other hand, the chain of ancestors of any node could
267 chains of ancestors of (ex-)parents of source and target. In particular,
268 those chains must end after a finite number of steps.
271 source or target; the next node in the loop would be the ex-parent of
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
275 of any loop. Q.E.D.
278 ability to check that directory is a descendent of another object. Current
286 in is_subdir() that would make it work even in presence of such beasts.