Re: problems with hierarchy: L4 pagers

[Jonathan S. Shapiro]

On Tue, 2005-10-18 at 10:02 +0100, Neal H. Walfield wrote:
> At Mon, 17 Oct 2005 17:15:06 -0400,
> Jonathan S. Shapiro wrote:
> First, you have just multiplied the cost of any IPC involving a map
> > operation by four additional IPCs. In essence, you have reconstructed
> > the logic that had to be used to implement COPY on top of REVOCABLE
> > COPY, but you haven't yet covered all of the necessary advisory
> > messages.
> 
> What RPCs?  In your example, I see two base IPCs per B page fault:
> when B faults, the kernel sends an IPC to B' and B' installs the
> mapping by sending an IPC to B.

I see five:

  A must advice A' that it plans to send a mapping to B so
  that A' knows to support later recovery. This is an RPC
  operation. It requires to IPCs.

  A now transmits to B: one IPC

  B must now advice B' of the existence of the mapping.
  This is another RPC. It requires two IPCs

Perhaps I created confusion by the term "RPC". I simply meant a
cross-process procedure call. I have always thought that the term "local
remote procedure call" was a really stupid coinage.

> > In particular, you have unintentionally assumed that A' will agree to
> > service faults from B, when it knows nothing about B. This can only be
> > done by ignoring a bunch of access check requirements, since B might be
> > anyone at all. The only way to fix this is to require *both* A and B to
> > inform their respective fault handlers, so actually this is worse than
> > it looks. In addition to the transfer, you need a call and return on
> > both sides of the protocol.
> 
> How does B even know about A'?  What I imagine is that since B got the
> original mapping from A it (or rather, LB) would again go to A to get
> a new mapping.  A might in turn go to A' but that is a different
> issue.  This is the assumption that I am making.

It cannot do this. The scenario here is that A has been paged out and/or
destroyed. It must go to A'.

B knows about A' because there is an architectural requirement in
practice that A must have a pager. A' is the pager.

> 
> > Finally, it is not likely that the pager for B (which can still be B')
> > can safely call A'. Consider the case where B is a server and A is an
> > untrusted client. B (therefore B') must assume that A' acts under the
> > control of A (because A can insert pagers too) and therefore may not
> > call A'.
> >
> > So: no, I do not consider this a reasonable solution. With regard to the
> > last issue (server cannot trust client) I'm not aware of a solution **in
> > principle** that would permit the server to rely on a client-controlled
> > entity in order to rebuild a mapping.
> 
> In scenario I tried to present, if B does not trust A then either it
> shouldn't accept the mapping in the first place or it should be
> prepared for it to disappear.
> 
> I don't understand how this is fundamentally different (with respect
> to mapping persistence) from a client provided space bank in EROS.

It is different because the L4 design conflates paging with revocation.
B must certainly be prepared to recover if A revokes the mapping. The
problem here is that A *didn't* revoke the mapping. What actually
happened is that the system pager decided to page A to disk, and
therefore revoked the mappings out from under A. This had the
consequence of revoking them from B, since B is downstream in the tree.

The problem now is that B cannot tell the difference between a hostile
act (A revoking the mapping) and a perfectly ordinary system activity
that A had nothing to do with. All B can see is that the mapping was
revoked.

Are we seriously going to propose trying to build a robust system in
which paging activity is sufficient to unrecoverably break communication
channels?

I am arguing, and I have argued to the L4 team, that implementing paging
in a way that breaks resource bindings is simply broken. Various
individuals have proposed various "solutions" to this problem within the
L4 primitive set. All of the solutions that I have heard so far involve
a central region manager (or something conceptually playing the same
role) and make it impossible to eliminate system-wide denial of
resource. I consider any design that imposes this requirement to be
entirely unacceptable. If I want broken architecture, I can run Linux.

shap