Documentation/filesystems/propagate_umount.txt

3 Umount propagation starts with a set of mounts we are already going to
5 that set - anything with the same mountpoint as one of the removed
6 mounts and with parent that would receive events from the parent of that
10 It is convenient to define several properties of sets of mounts:
12 1) A set S of mounts is non-shifting if for any mount X belonging
13 to S all subtrees mounted strictly inside of X (i.e. not overmounting
14 the root of X) contain only elements of S.
19 3) A set S is closed if it contains all children of its elements.
21 The set of mounts taken out by umount(2) must be non-shifting and
24 of any concealed mountpoints.
30 of that set, but only on top of stacks of root-overmounting elements
31 of set.  They can be reparented to the place where the bottom of
38 set and one side of the conflict (bottom of the stack of overmounts)
40 doing that pretty much immediately after the call of propagate_umount().
43 	1) for any set S, there is a maximal non-shifting subset of S
46 subset of S.  That subset is also non-shifting and it can be calculated
53 propagation from the parent of the same mount m.  Naive implementation
64 subtrees of U, in which case we'd end up examining the same candidates
66 everything downstream of that candidate and it's not hard to construct
68 number of candidates.
71 added on an earlier iteration of the outer loop - all additions made
72 during one iteration of the outer loop have different parents.  So
96 would get rid of that problem, but we need a sane implementation of
100 or something that isn't a peer of the one we are skipping".
113 The set is non-shifting when none of its elements are forbidden in it.
116 belongs to.  In other words, it can't belong to any of the non-shifting
117 subsets of S.  If we had a way to find a forbidden mount or show that
126 So in principle we could go through elements of S, checking if they
131 is linear by size of S.
135 	* there is a chain of mounts starting at x and leaving S
141 Note 3: if y has no children outside of S, it can't forbid anything in S.
150 Note that if m does not belong to S or has no children outside of S we
157 chain of mounts (x_0 = x, ..., x_k = y, x_{k+1} = r), such that x_{k+1}
159 mountpoint of x_1 is strictly inside x.  If mount r belongs to S, it must
161 Then there was a mount chain from r to some child of m that stayed in
170 in the part of S removed in Trim(S, m).
181 no mount remaining in S will be forbidden by either of x_1,...,x_k.
186 		let m be an arbitrary such element of S
190 S never grows, so the number of elements of S not belonging to visited
193 the beginning of each iteration no mount remaining in S will be forbidden
194 by any element of visited.  In other words, no mount remaining in S will
195 be forbidden, i.e. final value of S will be non-shifting.  It will be
201 element.  Naive implementation of Trim() is vulnerable to running into a
202 long chain of mounts, each mounted on top of parent's root.  Nothing in
204 recognize such chains and avoid walking them again on subsequent calls of
206 the number of elements in S.  Another difficulty is in implementing the
207 outer loop - we need to iterate through all elements of a shrinking set.
235 two elements in such chain are m and some child of m that does not belong
238 elements, i.e. when the last element does not overmount the root of m.
240 overmount the root of m.
241 	All other elements to remove will be ancestors of m, such that
251 only elements that had already been visited and remove none of them.
252 That's the weakness that makes it vulnerable to long chains of full
256 elements of S; we would mark all elements already visited by
266 In other words, the elements of that subset will remain in S until
269 	That suggests keeping S as a disjoint union of a closed set U
270 ('will be unmounted, no matter what') and the set of all elements of
273 consisting of all list elements that are marked as candidates (initially -
274 all of them).  Then we could have Trim_ancestors() only remove the mark,
316 an ancestor of argument of Trim_one() and since U is closed, the argument
317 of Trim_one() would also have to belong to U.  But Trim_one() is never
318 called for elements of U.  In other words, p belongs to S if and only
322 * we get no more than O(#S) calls of Trim_one()
325 * iterations of that loop for children in S are no more than O(#S)
327 * at most two children that are not elements of S are considered per
328 call of Trim_one().
330 no element of S has is set more than once.
338 	The caller has already removed all elements of U from their parents'
339 lists of children, which means that checking if child belongs to S is
341 the elements of U in the loop over children in Trim_one().
345 from the parent's list of children, etc.).  That's one fewer mount we'll
346 have to look into when we check the list of children of its parent *and*
352 such that parent of x is not in S.
354 Obviously, no non-revealing subset of S may contain x.  Removing such
356 subset (possibly empty one).  Note that removal of an element will
357 require removal of all its locked children, etc.
361 Proof: suppose S was non-shifting, x is a locked element of S, parent of x
366 contain x somewhere *and* that parent of x either belongs that subtree
370 // S is a disjoint union of a non-revealing set U (the ones we are committed
371 // to unmount) and a set of candidates, represented as a subset of list
373 // Elements of U are removed from their parents' lists of children.
375 // subset of S is now in U
399 Let (x_0, ..., x_n = m) be the maximal chain of descent of m within S.
400 * If it contains some elements of U, let x_k be the last one of those.
401 Then union of U with {x_{k+1}, ..., x_n} is obviously non-revealing.
402 * otherwise if all its elements are locked, then none of {x_0, ..., x_n}
403 may be elements of a non-revealing subset of S.
404 * otherwise let x_k be the first unlocked element of the chain.  Then none
405 of {x_0, ..., x_{k-1}} may be an element of a non-revealing subset of
406 S and union of U and {x_k, ..., x_n} is non-revealing.
408 handle_locked(m) finds which of these cases applies and adjusts Candidates
409 and U accordingly.  U remains non-revealing, union of Candidates and
410 U still contains any non-revealing subset of S and after the call of
412 it called for each element of S would suffice to empty Candidates,
413 leaving U the maximal non-revealing subset of S.
416 to have it called for elements of Candidates list until none remain.
418 Time complexity: number of calls of handle_locked() is limited by
419 #Candidates, each iteration of the first loop in handle_locked() removes
420 an element from the list, so their total number of executions is also
421 limited by #Candidates; number of iterations in the second loop is no
422 greater than the number of iterations of the first loop.
428 reparenting - if an element of the final set has a child not in it,
436 		Putting all of that together
447 terms of the pseudocode above) and everything we are still not sure about
448 ("candidates").  It means that for the output of the 1st step we'd like
455 	* undecided candidates ("candidates").  Subset of a list,
456 consisting of all its elements marked with a new flag (T_UMOUNT_CANDIDATE).
457 Initially all elements of the list will be marked that way; in the
461 	* anything in U that hadn't been in the original set - elements of
468 set) and intersection of S with set.  Use T_UMOUNT_CANDIDATE for
470 set into the list of candidates.  When we are done, strip that flag from
471 all elements of the original set.  That gives a cheap way to check
476 All elements of the original set are marked with MNT_UMOUNT and we'll
477 need the same for elements added when joining the contents of to_umount
481 "belongs to union of set and to_umount"; will_be_unmounted() for now.