Re: problems with hierarchy: L4 pagers

[Jonathan S. Shapiro]

On Mon, 2005-10-17 at 21:44 +0100, Neal H. Walfield wrote:
> At Sat, 08 Oct 2005 16:27:57 -0400,
> Jonathan S. Shapiro wrote:
> > In fact, there is a hierarchy problem in L4.x2 today in the memory
> > manager. Consider two process A, B with respective pagers A', B'. Now:
> > 
> >     A' maps to A
> >     A maps to B
> >     A' revokes
> >     B' knows nothing and cannot reconstruct the mapping.
> > 
> > This problem is now well-known by the L4 designers, and it is a direct
> > consequence of using REVOCABLE COPY as the primitive operation. In every
> > real system that has been constructed on top of L4.x2, the solution has
> > been to require that either
> > 
> >     A' and B' are identical, or
> >     A' and B' have a commonly trusted parent who knows how to
> >       recover, or
> >     The design is broken, so unmaps are not performed.
> > 
> > The current L4sec design will require that every capability interaction
> > must use the same kinds of solutions.
> 
> A can only map to be B if B accepts an IPC containing a map item.
> That is, B always knows when someone maps to it and can inform B'
> about such a mapping.  If B' doesn't trust B or if B' is unwilling to
> accept this information this is not a problem: B can still create a
> new thread (LB) and set it as its pager (B' cannot prevent this).
> When a page fault occurs, LB looks up how to reconstruct the mapping.
> If it doesn't have the required information, it simply propagates the
> fault to B':
> 
>    B -page fault-> LB -fault propagation -> B'
> 
> Do you find this a reasonable solution?

No.

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.

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.

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.

shap