Re: problems with hierarchy: L4 pagers

[Neal H. Walfield]

At Mon, 17 Oct 2005 17:15:06 -0400,
Jonathan S. Shapiro wrote:
> 
> 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.

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.

In my proposed example, there is one additional IPC.  When B faults,
the kernel invokes LB.  (I think this should actually be relatively
cheap as there is no address space switch.)  If LB is unable to
satisfy the fault, it then *propagates* the IPC to B'.  Finally B'
responds with a third IPC to B.

> 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.

> 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.

Thanks,
Neal