Notes on propagate_umount()

`propagate_umount()`의 목표와 집합 제약

언마운트 전파는 이미 제거하기로 한 마운트 집합에서 시작한다. 이상적으로는 제거 대상과 같은 마운트 지점을 사용하고, 그 제거 대상의 부모로부터 이벤트를 받을 부모를 가진 모든 하류 동족 마운트를 집합에 추가해야 한다. 다만 최종 집합은 이후의 재부모화와 은폐 보장을 위해 몇 가지 제약을 만족해야 한다.

`umount(2)`가 제거하는 집합은 non-shifting이면서 non-revealing이어야 한다. 첫 조건은 남아 있는 마운트의 재부모화를 가능하게 하고, 둘째 조건은 은폐된 마운트 지점이 드러나는 것을 막는다.

`propagate_umount()`는 원래 집합을 받아 확장한다. 원래 집합은 루트가 잠기지 않은 완전한 하위 트리이므로 closed이자 non-revealing이다. 결과 집합은 closed가 아닐 수 있다. 집합 밖의 마운트가 루트 위를 덮는 원소 스택의 꼭대기에만 남을 수 있으며, 이들은 스택 바닥이 살아남을 마운트에 붙는 위치로 재부모화할 수 있다.

재부모화 직후에는 같은 부모와 마운트 지점 쌍을 가진 마운트가 둘 이상 존재하지 않아야 한다는 제약을 일시적으로 위반할 수 있다. 호출자 `umount_tree()`가 곧바로 충돌을 해소한다. 충돌 양쪽은 집합에 없는 공통 부모를 가지며, 한쪽인 overmount 스택의 바닥은 제거 집합에 있으므로 정리할 수 있다. 따라서 `propagate_umount()` 호출 직후 `umount_tree()`가 실행된다는 순서에 의존한다.

알고리즘은 두 명제에 기반한다. 임의의 집합 `S`에는 최대 non-shifting 부분집합이 있고 `O(#S)`에 계산할 수 있다. 또한 non-shifting 집합 `S`에는 최대 non-revealing 부분집합이 있으며, 이 부분집합도 non-shifting이고 `O(#S)`에 계산할 수 있다.

        Notes on propagate_umount()

Umount propagation starts with a set of mounts we are already going to
take out.  Ideally, we would like to add all downstream cognates to
that set - anything with the same mountpoint as one of the removed
mounts and with parent that would receive events from the parent of that
mount.  However, there are some constraints the resulting set must
satisfy.

It is convenient to define several properties of sets of mounts:

1) A set S of mounts is non-shifting if for any mount X belonging
to S all subtrees mounted strictly inside of X (i.e. not overmounting
the root of X) contain only elements of S.

2) A set S is non-revealing if all locked mounts that belong to S have
parents that also belong to S.

3) A set S is closed if it contains all children of its elements.

The set of mounts taken out by umount(2) must be non-shifting and
non-revealing; the first constraint is what allows to reparent
any remaining mounts and the second is what prevents the exposure
of any concealed mountpoints.

propagate_umount() takes the original set as an argument and tries to
extend that set.  The original set is a full subtree and its root is
unlocked; what matters is that it's closed and non-revealing.
Resulting set may not be closed; there might still be mounts outside
of that set, but only on top of stacks of root-overmounting elements
of set.  They can be reparented to the place where the bottom of
stack is attached to a mount that will survive.  NOTE: doing that
will violate a constraint on having no more than one mount with
the same parent/mountpoint pair; however, the caller (umount_tree())
will immediately remedy that - it may keep unmounted element attached
to parent, but only if the parent itself is unmounted.  Since all
conflicts created by reparenting have common parent *not* in the
set and one side of the conflict (bottom of the stack of overmounts)
is in the set, it will be resolved.  However, we rely upon umount_tree()
doing that pretty much immediately after the call of propagate_umount().

Algorithm is based on two statements:
        1) for any set S, there is a maximal non-shifting subset of S
and it can be calculated in O(#S) time.
        2) for any non-shifting set S, there is a maximal non-revealing
subset of S.  That subset is also non-shifting and it can be calculated
in O(#S) time.

전파 관계에서 후보 찾기

주어진 closed 집합 `U`에 대해, `U`의 어떤 마운트 `m`과 같은 마운트 지점을 가지면서 자신의 부모가 `parent(m)`으로부터 전파를 받는 모든 마운트를 찾아야 한다. 단순 구현은 각 `m`을 `S`에 넣고 `Propagation(parent(m)) - {parent(m)}`를 모두 훑어 같은 지점의 자식을 추가한다.

S = {}
for each m in U
        add m to S
        p = parent(m)
        for each q in Propagation(p) - {p}
                child = look_up(q, mountpoint(m))
                if child
                        add child to S

그러나 `U`의 하위 트리 사이에 전파가 있으면 같은 후보를 반복 조사한다. 전파는 추이적이므로 이미 본 후보의 모든 하류에서도 중복이 이어지고, 실제 후보 수에 대해 시간이 이차식으로 커지는 사례를 만들 수 있다.

이미 본 후보를 다시 만났다면 그 후보는 바깥 반복문의 이전 회차에서 추가된 것이다. 한 회차에서 추가되는 항목들은 부모가 서로 다르기 때문이다. 따라서 `child`가 이미 `S`에 있으면 `Propagation(parent(child))`에서 같은 마운트 지점을 가진 항목은 이미 모두 추가됐음을 알 수 있다.

S = {}
for each m in U
        if m in S
                continue
        add m to S
        p = parent(m)
        q = propagation_next(p, p)
        while q
                child = look_up(q, mountpoint(m))
                if child
                        if child in S
                                q = skip_them(q, p)
                                continue
                        add child to S
                q = propagation_next(q, p)

`skip_them(q, p)`는 `q`부터 `Propagation(p)`를 계속 걸어 `Propagation(q)` 밖의 첫 항목을 찾는다. 구현은 `propagation_next()`를 `mnt_slave_list`로 내려가는 부분과 forward-and-up 부분으로 나누고, 건너뛸 peer가 아닌 항목이나 `NULL`을 만날 때까지 후자만 반복하면 된다.

추가 후보는 모두 마운트 조회로 얻으므로 절대 루트가 될 수 없다. 원래 집합에 절대 루트가 들어오는 일도 현재는 불가능하지만, 향후 조건 변화에 대비해 방어하는 편이 좋다.

                Finding candidates.

We are given a closed set U and we want to find all mounts that have
the same mountpoint as some mount m in U *and* whose parent receives
propagation from the parent of the same mount m.  Naive implementation
would be
        S = {}
        for each m in U
                add m to S
                p = parent(m)
                for each q in Propagation(p) - {p}
                        child = look_up(q, mountpoint(m))
                        if child
                                add child to S
but that can lead to excessive work - there might be propagation among the
subtrees of U, in which case we'd end up examining the same candidates
many times.  Since propagation is transitive, the same will happen to
everything downstream of that candidate and it's not hard to construct
cases where the approach above leads to the time quadratic by the actual
number of candidates.

Note that if we run into a candidate we'd already seen, it must've been
added on an earlier iteration of the outer loop - all additions made
during one iteration of the outer loop have different parents.  So
if we find a child already added to the set, we know that everything
in Propagation(parent(child)) with the same mountpoint has been already
added.
        S = {}
        for each m in U
                if m in S
                        continue
                add m to S
                p = parent(m)
                q = propagation_next(p, p)
                while q
                        child = look_up(q, mountpoint(m))
                        if child
                                if child in S
                                        q = skip_them(q, p)
                                        continue;
                                add child to S
                        q = propagation_next(q, p)
where
skip_them(q, p)
        keep walking Propagation(p) from q until we find something
        not in Propagation(q)

would get rid of that problem, but we need a sane implementation of
skip_them().  That's not hard to do - split propagation_next() into
"down into mnt_slave_list" and "forward-and-up" parts, with the
skip_them() being "repeat the forward-and-up part until we get NULL
or something that isn't a peer of the one we are skipping".

Note that there can be no absolute roots among the extra candidates -
they all come from mount lookups.  Absolute root among the original
set is _currently_ impossible, but it might be worth protecting
against.

최대 non-shifting 부분집합의 성질

집합 `S`의 마운트 `m` 내부에 엄격히 마운트된 하위 트리가 `S`에 속하지 않는 마운트를 포함하면 `m`을 `S`에서 forbidden이라고 부른다. forbidden 원소가 하나도 없는 집합이 바로 non-shifting 집합이다.

`m`이 `S`에서 forbidden이면 `m`을 포함하는 모든 부분집합 `S'`에서도 forbidden이다. 따라서 `m`은 `S`의 어떤 non-shifting 부분집합에도 들어갈 수 없다. forbidden 마운트를 하나 찾거나 없음을 판정할 수 있다면, 더 이상 없을 때까지 제거하여 최대 non-shifting 부분집합을 얻을 수 있다.

`m`을 제거해도 이전에 forbidden이었던 다른 마운트만 forbidden으로 남는다. `m`은 이미 `S` 밖의 후손을 갖기 때문에 `S` 안에 완전히 들어가던 하위 트리는 `S - {m}`에도 들어간다. 반대로 먼저 검사했을 때 forbidden이 아니었던 마운트가 이후 제거 때문에 새로 forbidden이 되지는 않는다.

원칙적으로는 `S`의 원소를 차례로 검사해 forbidden인 항목을 지울 수 있다. 하지만 각 검사에서 하위 트리를 다시 찾으면 비싸므로, 같은 제거 논리를 `S` 크기에 선형인 형태로 구현해야 한다.

                Maximal non-shifting subsets.

Let's call a mount m in a set S forbidden in that set if there is a
subtree mounted strictly inside m and containing mounts that do not
belong to S.

The set is non-shifting when none of its elements are forbidden in it.

If mount m is forbidden in a set S, it is forbidden in any subset S' it
belongs to.  In other words, it can't belong to any of the non-shifting
subsets of S.  If we had a way to find a forbidden mount or show that
there's none, we could use it to find the maximal non-shifting subset
simply by finding and removing them until none remain.

Suppose mount m is forbidden in S; then any mounts forbidden in S - {m}
must have been forbidden in S itself.  Indeed, since m has descendents
that do not belong to S, any subtree that fits into S will fit into
S - {m} as well.

So in principle we could go through elements of S, checking if they
are forbidden in S and removing the ones that are.  Removals will
not invalidate the checks done for earlier mounts - if they were not
forbidden at the time we checked, they won't become forbidden later.
It's too costly to be practical, but there is a similar approach that
is linear by size of S.

Let's say that mount x in a set S is forbidden by mount y, if
        * both x and y belong to S.
        * there is a chain of mounts starting at x and leaving S
          immediately after passing through y, with the first
          mountpoint strictly inside x.
Note 1: x may be equal to y - that's the case when something not
belonging to S is mounted strictly inside x.
Note 2: if y does not belong to S, it can't forbid anything in S.
Note 3: if y has no children outside of S, it can't forbid anything in S.

It's easy to show that mount x is forbidden in S if and only if x is
forbidden in S by some mount y.  And it's easy to find all mounts in S
forbidden by a given mount.

Consider the following operation:
        Trim(S, m) = S - {x : x is forbidden by m in S}

Note that if m does not belong to S or has no children outside of S we
are guaranteed that Trim(S, m) is equal to S.

The following is true: if x is forbidden by y in Trim(S, m), it was
already forbidden by y in S.

Proof: Suppose x is forbidden by y in Trim(S, m).  Then there is a
chain of mounts (x_0 = x, ..., x_k = y, x_{k+1} = r), such that x_{k+1}
is the first element that doesn't belong to Trim(S, m) and the
mountpoint of x_1 is strictly inside x.  If mount r belongs to S, it must
have been removed by Trim(S, m), i.e. it was forbidden in S by m.
Then there was a mount chain from r to some child of m that stayed in

`Trim(S, m)`과 최대성 증명

집합 `S`의 마운트 `x`가 `y`에 의해 forbidden이라는 말은 `x`와 `y`가 모두 `S`에 있고, `x`에서 시작해 `y`를 지난 직후 `S`를 벗어나는 마운트 체인이 있으며 첫 마운트 지점이 `x`의 엄격한 내부라는 뜻이다. `x == y`일 수 있는데, 이는 `S` 밖의 항목이 `x` 내부에 직접 마운트된 경우다.

`y`가 `S`에 없거나 `S` 밖의 자식이 없으면 `S` 안의 어떤 항목도 forbid할 수 없다. `x`가 `S`에서 forbidden인 것과 어떤 `y`에 의해 forbidden인 것은 동치이며, 주어진 `y`가 forbid하는 모든 마운트는 쉽게 찾을 수 있다.

`Trim(S, m) = S - {x : x is forbidden by m in S}`로 정의한다. `m`이 `S`에 없거나 `S` 밖의 자식이 없으면 `Trim(S, m) == S`가 보장된다.

핵심 성질은 `x`가 `Trim(S, m)`에서 `y`에 의해 forbidden이면 이미 `S`에서도 `y`에 의해 forbidden이었다는 것이다. `x = x_0`에서 `y = x_k`를 지나 처음 `Trim(S, m)` 밖인 `r = x_{k+1}`로 가는 체인을 생각한다. `r`이 `S` 안이었다면 `Trim`이 `m` 때문에 제거한 항목이어야 한다. 그러면 `r`에서 `m`의 어떤 자식까지 `S` 안에 머무는 체인을 앞 체인에 붙여 `x` 역시 `m`에 의해 forbidden임을 보일 수 있는데, 이는 `x`가 `Trim(S, m)`에 남았다는 가정과 모순이다. 따라서 `r`은 `S` 밖이고 원래 체인이 `S`에서의 forbidden 관계를 증명한다.

따름정리로 `Trim(S, m)`에는 `m`에 의해 forbidden인 마운트가 남지 않는다. 이어서 다른 `n`으로 `Trim`해도 `m`에 의해 forbidden인 항목이 새로 생기지 않는다. 따라서 `x_1`부터 `x_k`까지 차례로 `Trim`한 뒤에는 남은 어느 마운트도 이 원소들에 의해 forbidden이지 않다.

visited = {}
while S contains elements not belonging to visited
        let m be an arbitrary such element of S
        S = Trim(S, m)
        add m to visited

`S`는 커지지 않으므로 매 회차마다 `visited`에 속하지 않은 원소 수가 적어도 하나 줄어든다. 종료 시 남은 원소는 모두 visited이며, 각 회차 시작 때 visited 원소가 남은 마운트를 forbid하지 않는다는 불변식이 성립한다. 그러므로 최종 `S`는 non-shifting이고, 제거한 것은 어떤 non-shifting 부분집합에도 들어갈 수 없는 forbidden 원소뿐이므로 최대 부분집합이다.

S all the way until m, but that's impossible since x belongs to Trim(S, m)
and prepending (x_0, ..., x_k) to that chain demonstrates that x is also
forbidden in S by m, and thus can't belong to Trim(S, m).
Therefore r can not belong to S and our chain demonstrates that
x is forbidden by y in S.  QED.

Corollary: no mount is forbidden by m in Trim(S, m).  Indeed, any
such mount would have been forbidden by m in S and thus would have been
in the part of S removed in Trim(S, m).

Corollary: no mount is forbidden by m in Trim(Trim(S, m), n).  Indeed,
any such would have to have been forbidden by m in Trim(S, m), which
is impossible.

Corollary: after
        S = Trim(S, x_1)
        S = Trim(S, x_2)
        ...
        S = Trim(S, x_k)
no mount remaining in S will be forbidden by either of x_1,...,x_k.

The following will reduce S to its maximal non-shifting subset:
        visited = {}
        while S contains elements not belonging to visited
                let m be an arbitrary such element of S
                S = Trim(S, m)
                add m to visited

S never grows, so the number of elements of S not belonging to visited
decreases at least by one on each iteration.  When the loop terminates,
all mounts remaining in S belong to visited.  It's easy to see that at
the beginning of each iteration no mount remaining in S will be forbidden
by any element of visited.  In other words, no mount remaining in S will
be forbidden, i.e. final value of S will be non-shifting.  It will be
the maximal non-shifting subset, since we were removing only forbidden
elements.

        There are two difficulties in implementing the above in linear
time, both due to the fact that Trim() might need to remove more than one
element.  Naive implementation of Trim() is vulnerable to running into a
long chain of mounts, each mounted on top of parent's root.  Nothing in
that chain is forbidden, so nothing gets removed from it.  We need to
recognize such chains and avoid walking them again on subsequent calls of
Trim(), otherwise we will end up with worst-case time being quadratic by
the number of elements in S.  Another difficulty is in implementing the
outer loop - we need to iterate through all elements of a shrinking set.
That would be trivial if we never removed more than one element at a time
(linked list, with list_for_each_entry_safe for iterator), but we may
need to remove more than one entry, possibly including the ones we have
already visited.

        Let's start with naive algorithm for Trim():

`Trim_one()`의 단순 구현과 선형화 과제

선형 시간 구현에는 두 난점이 있다. 첫째, `Trim()`이 여러 항목을 지울 수 있어 부모 루트 위에 연속해서 마운트된 긴 체인을 매번 다시 걸으면 최악의 경우 이차 시간이 된다. 이 체인의 항목들은 forbidden이 아니어서 제거되지 않는다. 둘째, 이미 방문한 항목까지 한꺼번에 제거될 수 있는 축소 집합을 안정적으로 순회해야 한다.

Trim_one(m)
        found = false
        for each n in children(m)
                if n not in S
                        found = true
                        if (mountpoint(n) != root(m))
                                remove m from S
                                break
        if found
                Trim_ancestors(m)

Trim_ancestors(m)
        for (; parent(m) in S; m = parent(m)) {
                if (mountpoint(m) != root(parent(m)))
                        remove parent(m) from S
        }

`m`이 `S`에 있으면 이 `Trim_one(m)`은 `S`를 `Trim(S, m)`으로 바꾼다. 제외 체인의 마지막 두 원소는 `m`과 `S` 밖인 `m`의 자식이다. 그런 자식이 없으면 아무 변화가 없다. 체인 길이가 둘이고 마지막 자식이 `m`의 루트를 overmount하지 않을 때만 `m` 자체를 제거한다.

나머지 제거 대상은 `m`의 조상이다. `S` 안에서 `m`까지 내려오는 가장 긴 체인 `(x_0, x_1, ..., x_k = m)`에서 `x_{i+1}`이 `x_i`의 루트를 overmount하지 않을 때 정확히 `x_i`를 제거해야 한다. `Trim_ancestors(m)`은 이 체인을 `x_k`에서 `x_1` 방향으로 걸으며 필요한 원소만 제거한다.

하지만 `Trim_ancestors()`가 이미 방문한 원소에 닿으면 이후에는 이미 방문한 원소만 만나고 아무것도 제거하지 않는다. 긴 full-overmount 체인에서 같은 구간을 반복하게 되는 약점이다. 집합 원소에 표시할 수 있다면 이미 `Trim_ancestors()`가 본 원소를 mark하고, 표시된 원소를 만나자마자 종료해 해결할 수 있다.

집합 순회 문제는 표현 방식으로 해결한다. 원래 `propagate_umount()`에 전달된 closed 부분집합 `U`는 모든 후손이 `S`에 있으므로 어떤 항목도 forbid하지 않고 어떤 항목에 의해 forbidden이지도 않다. `U`는 끝까지 남으며, `m ∈ U`에 대한 `Trim_one(S, m)`은 항상 no-op이다.

Trim_one(m)
        found = false
        for each n in children(m)
                if n not in S
                        found = true
                        if (mountpoint(n) != root(m))
                                remove m from S
                                break
        if found
                Trim_ancestors(m)

Trim_ancestors(m)
        for (; parent(m) in S; m = parent(m)) {
                if (mountpoint(m) != root(parent(m)))
                        remove parent(m) from S
        }

If m belongs to S, Trim_one(m) will replace S with Trim(S, m).
Proof:
        Consider the chains excluding elements from Trim(S, m).  The last
two elements in such chain are m and some child of m that does not belong
to S.  If m has no such children, Trim(S, m) is equal to S.
        m itself is removed if and only if the chain has exactly two
elements, i.e. when the last element does not overmount the root of m.
In other words, that happens when m has a child not in S that does not
overmount the root of m.
        All other elements to remove will be ancestors of m, such that
the entire descent chain from them to m is contained in S.  Let
(x_0, x_1, ..., x_k = m) be the longest such chain.  x_i needs to be
removed if and only if x_{i+1} does not overmount its root.  It's easy
to see that Trim_ancestors(m) will iterate through that chain from
x_k to x_1 and that it will remove exactly the elements that need to be
removed.

        Note that if the loop in Trim_ancestors() walks into an already
visited element, we are guaranteed that remaining iterations will see
only elements that had already been visited and remove none of them.
That's the weakness that makes it vulnerable to long chains of full
overmounts.

        It's easy to deal with, if we can afford setting marks on
elements of S; we would mark all elements already visited by
Trim_ancestors() and have it bail out as soon as it sees an already
marked element.

        The problems with iterating through the set can be dealt with in
several ways, depending upon the representation we choose for our set.
One useful observation is that we are given a closed subset in S - the
original set passed to propagate_umount().  Its elements can neither
forbid anything nor be forbidden by anything - all their descendents
belong to S, so they can not occur anywhere in any excluding chain.
In other words, the elements of that subset will remain in S until
the end and Trim_one(S, m) is a no-op for all m from that subset.

        That suggests keeping S as a disjoint union of a closed set U
('will be unmounted, no matter what') and the set of all elements of
S that do not belong to U.  That set ('candidates') is all we need
to iterate through.  Let's represent it as a subset in a cyclic list,
consisting of all list elements that are marked as candidates (initially -
all of them).  Then we could have Trim_ancestors() only remove the mark,
leaving the elements on the list.  Then Trim_one() would never remove
anything other than its argument from the containing list, allowing to
use list_for_each_entry_safe() as iterator.

후보 목록을 이용한 선형 `Trim` 구현

`S`를 서로 겹치지 않는 closed 집합 `U`와 `S - U`인 candidates의 합으로 표현한다. candidates는 순환 목록 원소 가운데 candidate 표시가 켜진 부분집합이다. 처음에는 모두 표시되어 있다. `Trim_ancestors()`는 목록에서 원소를 바로 빼지 않고 표시만 지운다. 그러면 `Trim_one()`은 자신 외의 목록 원소를 제거하지 않으므로 `list_for_each_entry_safe()`로 순회할 수 있다.

list_for_each_entry_safe(m, ..., Candidates, ...)
        Trim_one(m)

Trim_one(m)
        if (m is not marked as a candidate)
                strip the "seen by Trim_ancestors" mark from m
                remove m from the Candidates list
                return

        remove_this = false
        found = false
        for each n in children(m)
                if n not in S
                        found = true
                        if (mountpoint(n) != root(m))
                                remove_this = true
                                break
        if found
                Trim_ancestors(m)
        if remove_this
                strip the "seen by Trim_ancestors" mark from m
                strip the "candidate" mark from m
                remove m from the Candidate list

Trim_ancestors(m)
        for (p = parent(m); p is marked as candidate ; m = p, p = parent(p)) {
                if m is marked as seen by Trim_ancestors
                        return
                mark m as seen by Trim_ancestors
                if (mountpoint(m) != root(p))
                        strip the "candidate" mark from p
        }

`Trim_ancestors()`의 종료 조건은 정확하다. 반복문의 `p`가 `U`에 들어갈 수는 없다. `p`는 `Trim_one()` 인자의 조상이고 `U`가 closed이므로 `p ∈ U`라면 인자도 `U`에 속해야 하지만, `Trim_one()`은 `U` 원소에 호출되지 않는다. 따라서 이 문맥에서는 `p ∈ S`와 `p ∈ candidates`가 동치다.

시간 복잡도는 `Trim_one()` 호출이 `O(#S)` 이하이고, 모든 호출을 합쳐 자식 하나를 두 번 보지 않는다. `S` 안 자식을 보는 반복도 최악 `O(#S)`이며, `S` 밖 자식은 호출당 최대 둘만 본다. `Trim_ancestors()`는 반복마다 mark를 세우고 각 원소의 mark는 최대 한 번만 세워지므로 전체가 선형이다.

종료 시 `Trim_ancestors()`가 `S`에서 제외했지만 목록에는 남긴 원소가 있을 수 있다. 별도 선형 정리 반복을 돌릴 수도 있지만 다음 non-revealing 단계가 candidates를 어차피 순회하므로 그때 제거한다.

호출자는 이미 `U`의 모든 원소를 부모의 자식 목록에서 떼어 놓았다. 따라서 `Trim_one()`의 자식 순회에서 `child ∈ S` 검사는 candidate mark 검사와 같다. `U` 원소는 자식 목록에서 보이지 않는다.

또한 `children(m)`이 비어 있고 `m`이 locked가 아니면 즉시 committed 부분집합으로 옮길 수 있다. 부모의 자식 목록에서 제거하면 부모 자식을 검사할 때 한 번, non-revealing 집합을 만들 때 한 번 더 조사할 마운트를 줄인다.

        Assuming that representation we get the following:

        list_for_each_entry_safe(m, ..., Candidates, ...)
                Trim_one(m)
where
Trim_one(m)
        if (m is not marked as a candidate)
                strip the "seen by Trim_ancestors" mark from m
                remove m from the Candidates list
                return

        remove_this = false
        found = false
        for each n in children(m)
                if n not in S
                        found = true
                        if (mountpoint(n) != root(m))
                                remove_this = true
                                break
        if found
                Trim_ancestors(m)
        if remove_this
                strip the "seen by Trim_ancestors" mark from m
                strip the "candidate" mark from m
                remove m from the Candidate list

Trim_ancestors(m)
        for (p = parent(m); p is marked as candidate ; m = p, p = parent(p)) {
                if m is marked as seen by Trim_ancestors
                        return
                mark m as seen by Trim_ancestors
                if (mountpoint(m) != root(p))
                        strip the "candidate" mark from p
        }

        Terminating condition in the loop in Trim_ancestors() is correct,
since that loop will never run into p belonging to U - p is always
an ancestor of argument of Trim_one() and since U is closed, the argument
of Trim_one() would also have to belong to U.  But Trim_one() is never
called for elements of U.  In other words, p belongs to S if and only
if it belongs to candidates.

        Time complexity:
* we get no more than O(#S) calls of Trim_one()
* the loop over children in Trim_one() never looks at the same child
twice through all the calls.
* iterations of that loop for children in S are no more than O(#S)
in the worst case
* at most two children that are not elements of S are considered per
call of Trim_one().
* the loop in Trim_ancestors() sets its mark once per iteration and
no element of S has is set more than once.

        In the end we may have some elements excluded from S by
Trim_ancestors() still stuck on the list.  We could do a separate
loop removing them from the list (also no worse than O(#S) time),
but it's easier to leave that until the next phase - there we will
iterate through the candidates anyway.

        The caller has already removed all elements of U from their parents'
lists of children, which means that checking if child belongs to S is
equivalent to checking if it's marked as a candidate; we'll never see
the elements of U in the loop over children in Trim_one().

        What's more, if we see that children(m) is empty and m is not
locked, we can immediately move m into the committed subset (remove
from the parent's list of children, etc.).  That's one fewer mount we'll
have to look into when we check the list of children of its parent *and*
when we get to building the non-revealing subset.

최대 non-revealing 부분집합

`S`가 non-revealing이 아니면 부모가 `S`에 없는 locked 원소 `x ∈ S`가 존재한다. 어떤 non-revealing 부분집합도 `x`를 포함할 수 없다. 이런 원소를 하나씩 지우되 locked 자식들도 연쇄 제거하면 최대 non-revealing 부분집합에 도달한다. 결과가 빈 집합일 수도 있다.

원래 집합이 non-shifting이었다면 이 제거 뒤에도 non-shifting이다. 반대로 `S - {x}`가 non-shifting이 아니라고 가정하면, 남은 `m` 내부의 하위 트리가 `S - {x}` 밖 원소를 포함한다. 원래 `S`는 non-shifting이므로 그 트리의 원소는 모두 `S`에 속하며, 빠진 원소는 `x`여야 한다. 그러면 `parent(x)`도 같은 트리에 있거나 `m`과 같아 `S`에 속해야 하므로 `parent(x) ∉ S`와 모순이다.

표현은 앞 단계와 같다. `S`는 반드시 언마운트할 non-revealing 집합 `U`와 candidate mark가 있는 목록 부분집합의 서로소 합이다. `U` 원소는 부모의 자식 목록에서 제거돼 있다. 마지막에는 candidates가 비고 `U`가 `S`의 최대 non-revealing·non-shifting 부분집합이 된다.

while (Candidates list is non-empty)
        handle_locked(first(Candidates))

handle_locked(m)
        if m is not marked as a candidate
                strip the "seen by Trim_ancestors" mark from m
                remove m from the list
                return
        cutoff = m
        for (p = m; p in candidates; p = parent(p)) {
                strip the "seen by Trim_ancestors" mark from p
                strip the "candidate" mark from p
                remove p from the Candidates list
                if (!locked(p))
                        cutoff = parent(p)
        }
        if p in U
                cutoff = p
        while m != cutoff
                remove m from children(parent(m))
                add m to U
                m = parent(m)

`m`으로 끝나는 `S` 안의 최대 하강 체인 `(x_0, ..., x_n = m)`에는 세 경우가 있다. 체인에 `U` 원소가 있으면 마지막 `U` 원소 `x_k` 뒤의 `{x_{k+1}, ..., x_n}`를 `U`와 합쳐도 non-revealing이다. 모든 원소가 locked면 어느 원소도 non-revealing 부분집합에 들어갈 수 없다. 그 밖에는 첫 unlocked 원소 `x_k` 이전의 locked 원소를 버리고 `{x_k, ..., x_n}`을 `U`에 합칠 수 있다.

`handle_locked(m)`은 이 세 경우를 판별하여 Candidates와 `U`를 조정한다. `U`는 계속 non-revealing이고, `Candidates ∪ U`는 `S`의 모든 non-revealing 부분집합을 계속 포함하며, 호출 후 `m`은 Candidate 목록에 남지 않는다. `U` 원소에 대한 호출은 no-op이므로 Candidates가 빌 때까지 목록 원소만 처리하면 충분하다.

호출 횟수는 `#Candidates` 이하이다. 첫 반복문의 각 회차는 목록 원소 하나를 제거하므로 모든 호출을 합친 회차 수도 `#Candidates` 이하이고, 둘째 반복문의 회차 수는 첫 반복문보다 많지 않다. 따라서 이 단계 역시 선형이다.

                Maximal non-revealing subsets

If S is not a non-revealing subset, there is a locked element x in S
such that parent of x is not in S.

Obviously, no non-revealing subset of S may contain x.  Removing such
elements one by one will obviously end with the maximal non-revealing
subset (possibly empty one).  Note that removal of an element will
require removal of all its locked children, etc.

If the set had been non-shifting, it will remain non-shifting after
such removals.
Proof: suppose S was non-shifting, x is a locked element of S, parent of x
is not in S and S - {x} is not non-shifting.  Then there is an element m
in S - {x} and a subtree mounted strictly inside m, such that m contains
an element not in S - {x}.  Since S is non-shifting, everything in
that subtree must belong to S.  But that means that this subtree must
contain x somewhere *and* that parent of x either belongs that subtree
or is equal to m.  Either way it must belong to S.  Contradiction.

// same representation as for finding maximal non-shifting subsets:
// S is a disjoint union of a non-revealing set U (the ones we are committed
// to unmount) and a set of candidates, represented as a subset of list
// elements that have "is a candidate" mark on them.
// Elements of U are removed from their parents' lists of children.
// In the end candidates becomes empty and maximal non-revealing non-shifting
// subset of S is now in U
        while (Candidates list is non-empty)
                handle_locked(first(Candidates))

handle_locked(m)
        if m is not marked as a candidate
                strip the "seen by Trim_ancestors" mark from m
                remove m from the list
                return
        cutoff = m
        for (p = m; p in candidates; p = parent(p)) {
                strip the "seen by Trim_ancestors" mark from p
                strip the "candidate" mark from p
                remove p from the Candidates list
                if (!locked(p))
                        cutoff = parent(p)
        }
        if p in U
                cutoff = p
        while m != cutoff
                remove m from children(parent(m))
                add m to U
                m = parent(m)

Let (x_0, ..., x_n = m) be the maximal chain of descent of m within S.
* If it contains some elements of U, let x_k be the last one of those.
Then union of U with {x_{k+1}, ..., x_n} is obviously non-revealing.
* otherwise if all its elements are locked, then none of {x_0, ..., x_n}
may be elements of a non-revealing subset of S.
* otherwise let x_k be the first unlocked element of the chain.  Then none
of {x_0, ..., x_{k-1}} may be an element of a non-revealing subset of
S and union of U and {x_k, ..., x_n} is non-revealing.

handle_locked(m) finds which of these cases applies and adjusts Candidates
and U accordingly.  U remains non-revealing, union of Candidates and
U still contains any non-revealing subset of S and after the call of
handle_locked(m) m is guaranteed to be not in Candidates list.  So having
it called for each element of S would suffice to empty Candidates,
leaving U the maximal non-revealing subset of S.

However, handle_locked(m) is a no-op when m belongs to U, so it's enough
to have it called for elements of Candidates list until none remain.

Time complexity: number of calls of handle_locked() is limited by
#Candidates, each iteration of the first loop in handle_locked() removes
an element from the list, so their total number of executions is also
limited by #Candidates; number of iterations in the second loop is no
greater than the number of iterations of the first loop.

최종 집합 밖 자식의 재부모화

최종 집합을 계산한 뒤에도 그 집합 원소가 집합 밖의 자식을 가지면 해당 자식을 재부모화해야 한다. 최종 집합이 non-shifting이므로 이런 자식은 부모 루트를 덮는 root-overmount일 수밖에 없다.

원래 집합은 closed가 보장되므로 집합 밖 자식의 부모가 원래 집합에 속할 수도 없다. 따라서 추가 후보에서 최종 제거 대상으로 선택된 overmount 스택만 재부모화 대상으로 남는다.

                Reparenting

After we'd calculated the final set, we still need to deal with
reparenting - if an element of the final set has a child not in it,
we need to reparent such child.

Such children can only be root-overmounting (otherwise the set wouldn't
be non-shifting) and their parents can not belong to the original set,
since the original is guaranteed to be closed.

전체 단계와 커널 자료구조 표시

전체 계획은 후보를 모두 찾고, 최대 non-shifting 부분집합으로 줄이고, 다시 최대 non-revealing 부분집합으로 줄인 뒤, 필요한 자식을 재부모화하고 결과 집합을 호출자에게 반환하는 순서다.

둘째와 셋째 단계에서는 집합을 원래 집합을 포함하는 성장 중인 non-revealing 부분집합 `U`와 아직 결정하지 않은 candidates로 나눈다. 첫 단계 출력에서는 추가 후보와 원래 집합을 구별해야 하며, 넷째 단계에서는 `U`에 추가된 항목과 원래 집합을 구별해야 한다.

초기 candidates 목록의 모든 원소에는 `T_UMOUNT_CANDIDATE`를 세우며, 처리가 끝나면 목록은 비고 어느 마운트에도 이 플래그가 남지 않는다. `T_MARKED`는 `trim_ancestors()`가 이미 본 항목이라는 표시에 재사용한다. candidates에서 버리거나 `to_umount`로 옮긴 항목은 목록과 표시를 함께 정리한다.

`gather_candidates()`는 `S - set`인 candidates와 `S ∩ set`을 동시에 유지해야 한다. 만나는 모든 원소에 `T_UMOUNT_CANDIDATE`를 세우되 원래 집합에 없던 항목만 candidates 목록에 넣는다. 수집이 끝나면 원래 집합 원소에서 이 플래그를 지운다.

이렇게 하면 후보 수집 중에는 원소가 `S`에 속하는지 저렴하게 검사하고, 후속 단계에서는 원소가 candidates 자체에 속하는지 같은 플래그로 검사할 수 있다. `is_candidate()`는 `m->mnt_t_flags & T_UMOUNT_CANDIDATE`로 구현한다.

원래 집합의 모든 원소에는 `MNT_UMOUNT`가 이미 설정돼 있다. `to_umount`에 추가되는 원소에도 들어갈 때 `MNT_UMOUNT`를 설정한다. 이 작업은 기존 `umount_one`의 역할과 가깝기 때문에 그 이름을 유지하며, `set ∪ to_umount`에 속하는지는 `will_be_unmounted()`로 판정한다.

candidates 목록에서 제거할 때는 `T_MARKED`와 `T_UMOUNT_CANDIDATE`를 모두 지워야 한다. 이 공통 처리를 `remove_from_candidates_list()`로 묶는다.

                Putting all of that together

The plan is to
        * find all candidates
        * trim down to maximal non-shifting subset
        * trim down to maximal non-revealing subset
        * reparent anything that needs to be reparented
        * return the resulting set to the caller

For the 2nd and 3rd steps we want to separate the set into growing
non-revealing subset, initially containing the original set ("U" in
terms of the pseudocode above) and everything we are still not sure about
("candidates").  It means that for the output of the 1st step we'd like
the extra candidates separated from the stuff already in the original set.
For the 4th step we would like the additions to U separate from the
original set.

So let's go for
        * original set ("set").  Linkage via mnt_list
        * undecided candidates ("candidates").  Subset of a list,
consisting of all its elements marked with a new flag (T_UMOUNT_CANDIDATE).
Initially all elements of the list will be marked that way; in the
end the list will become empty and no mounts will remain marked with
that flag.
        * Reuse T_MARKED for "has been already seen by trim_ancestors()".
        * anything in U that hadn't been in the original set - elements of
candidates will gradually be either discarded or moved there.  In other
words, it's the candidates we have already decided to unmount.        Its role
is reasonably close to the old "to_umount", so let's use that name.
Linkage via mnt_list.

For gather_candidates() we'll need to maintain both candidates (S -
set) and intersection of S with set.  Use T_UMOUNT_CANDIDATE for
all elements we encounter, putting the ones not already in the original
set into the list of candidates.  When we are done, strip that flag from
all elements of the original set.  That gives a cheap way to check
if element belongs to S (in gather_candidates) and to candidates
itself (at later stages).  Call that predicate is_candidate(); it would
be m->mnt_t_flags & T_UMOUNT_CANDIDATE.

All elements of the original set are marked with MNT_UMOUNT and we'll
need the same for elements added when joining the contents of to_umount
to set in the end.  Let's set MNT_UMOUNT at the time we add an element
to to_umount; that's close to what the old 'umount_one' is doing, so
let's keep that name.  It also gives us another predicate we need -
"belongs to union of set and to_umount"; will_be_unmounted() for now.

Removals from the candidates list should strip both T_MARKED and
T_UMOUNT_CANDIDATE; call it remove_from_candidates_list().