Lines Matching +full:parent +full:- +full:locked
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
30 * lock the parent (exclusive)
36 * lock the parent (exclusive)
40 5. rename that is _not_ cross-directory. Locking rules:
42 * lock the parent (exclusive)
44 * decide which of the source and target need to be locked.
45 The source needs to be locked if it's a non-directory, target - if it's
46 a non-directory or about to be removed.
49 are non-directories - the source because it wouldn't need to be locked
50 otherwise and the target because mixing directory and non-directory is
53 6. cross-directory rename. The trickiest in the whole bunch. Locking rules:
58 ancestor of the other, lock the parent of source first.
63 * lock the non-directories involved (exclusive), in inode pointer order.
66 to be read, modified or removed by method will be locked by the caller.
72 There is one more thing to consider - splicing. It's not an operation
75 picture of those - especially for network filesystems. What we have
78 that's not a problem, but there is a nasty twist - what should we do
82 the root of another"; there's also open-by-fhandle stuff, and there's a
89 dcache trees. Lookup is already holding the parent locked. If alias is
97 current parent of the alias. If either trylock fails, we fail the lookup.
98 If trylocks succeed, we detach the alias from its current parent and
102 all we change is the view in dcache. Moreover, holding a directory locked
109 splicing is almost irrelevant - the only place where it matters is one
110 step in cross-directory renames; we need to be careful when checking if
114 Multiple-filesystem stuff
125 on a filesystem could trigger directory operations only on higher-ranked
126 ones - in these terms overlayfs ranks lower than its layers, network
133 If no directory is its own ancestor, the scheme above is deadlock-free.
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
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
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
169 i.e. they all will be ->i_rwsem of directories on the same filesystem.
185 Each operation in the minimal cycle must have locked at least
187 only 3 possible operations: directory removal (locks parent, then
188 child), same-directory rename killing a subdirectory (ditto) and
189 cross-directory rename of some sort.
191 There must be a cross-directory rename in the set; indeed,
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
201 generality we can assume that T1 is the one doing a cross-directory
202 rename and everything else is of the "lock parent, then child" sort.
204 In other words, we have a cross-directory rename that locked
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
208 cross-directory rename does not get to locking any directories until it
213 Consider the order in which directories are locked by the
214 cross-directory rename; parents first, then possibly their children.
215 Dn and D1 would have to be among those, with Dn locked before D1.
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
221 of another - otherwise the operation would not have progressed past
224 It can't be a parent and its child; otherwise we would've had
225 a loop, since the parents are locked before the children, so the parent
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
232 That leaves only one possibility - namely, both Dn and D1 are
239 Note that the check for having a common ancestor in cross-directory
240 rename is crucial - without it a deadlock would be possible. Indeed,
242 parent of source, then try to lock the parent of target, only to have
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
247 in between (all of those would fail with -ENOTEMPTY, had they ever gotten
248 the locks) and voila - we have a deadlock.
254 the only operation that could introduce loops is cross-directory rename.
257 had its parent changed. In other words, the loop must be passing through
262 in the parent of source could not have passed through the target and
266 the parent after the operation, so the operation does not change the
267 chains of ancestors of (ex-)parents of source and target. In particular,
271 source or target; the next node in the loop would be the ex-parent of
273 ancestors of that parent. But as we have just shown, that chain must
280 also preserved by all operations (cross-directory rename on a tree that would