Re: problems with hierarchy: L4 pagers

[Jonathan S. Shapiro]

ALL: Espen's discussion reveals an important problem in the argument
about hierarchy that I am making. EROS *also* has hierarchies, but they
appear in different places in the design and the involve different
assumptions and dependencies. The burden is on me to try to explain why
the space bank hierarchy is a "good" hierarchy and the L4 mapping
hierarchy is not (in my opinion). I need to think about how to
articulate the difference between them clearly.


On Tue, 2005-10-18 at 15:25 +0200, Espen Skoglund wrote:
> One way to look at the in-kernel mapping database is as a cache for
> mapping information.  Inserts to and removals from the cache happen by
> MAP or UNMAP operations.

There was a long discussion of this at Dresden. The end of this
discussion was that the mapping database was *not* simply a cache,
because some of the state that it holds is not exported. I believe that
it was Kevin Elphinstone who gave the convincing example, but I do not
remember what his example was. It would be wonderful if the design has
evolved to solve this in a way that does not support storage denial of
resource. Is there a description that I can read?

> However, by virtue of being a cache the real
> mapping information must be stored somewhere else, i.e., in user-level
> pagers.  If the pagers do not record the mapping information, then
> yeah, tough luck, you'll have a hard time reconstructing the mappings.
> The analogy here would be an OS kernel that creates new VM mappings by
> inserting TLB entries, but without updating the corresponding page
> tables.

In the kernel example you give, the necessary knowledge is not
distributed among multiple parties, and all of the participating code
exists in a relationship of mutual and complete trust. Neither of these
statements is true in the A <-> B example that I gave.

> Your main gripe about the whole thing seems to be the question: "How
> can B' possibly reconstruct the mapping since it doesn't know where it
> originates from?"

This is not my complaint. I am clear that B' can know where the mapping
came from. All it takes is extra IPCs or a shared memory interface. The
real problem is that A' does not know that B/B' is a valid recipient
unless A does a similar exchange with A', and B cannot in general trust
A to make this exchange. One important objection is that a distant third
party -- the system pager -- can take actions where if any user-mode
application gets this wrong the entire arrangement collapses on the
floor.

>   Your suggestion to solve this is to use a protocol
> that involves IPCs to A' and B' for *every* mapping from A to B.
> While this could indeed solve the problem the protocol is overly
> pessimistic.  For starters, as Neal has already argued, you only
> really need to inform B' (or LB) about the mapping.

If A' is not informed, please explain how the mapping is reconstructable
in the absence of a universally trusted third party?

>   Second, B'/LB
> only needs to know about the mapping if the mapping is revoked.

If the system overall uses a swap area, then in the general case EVERY
mapping can be revoked!

>   And
> third, B recording something like "I'm accessing mapping X from A" in
> a location known to B' (or LB in Neal's case) is sufficient.

Yes. I agree that this is a significant optimization, and that I had
failed to see it. The cost of this optimization is that the pager must
trust the application that it pages. This assumption is common in L4
designs. We do not tend to make it in EROS/Coyotos designs. I do tend to
forget this difference in the design assumptions of the two systems.
Thank you for correcting this!

> Sure, if A is unwilling or not capable of re-providing the mapping
> then you have a problem.  But if this is the case and you are not
> willing to deal with it, then B had better make sure that it can
> retrieve the mapping from some other trusted entity if it needs to
> (e.g., from something like the physmem server in Hurd).

What you are appear to be arguing is: it is an architecturally
acceptable choice to require every program in a system to include code
that allows it to recover from the effects of system-wide paging and
makes recovery possible between peer processes only if one of the
following two conditions hold:

  1) The peers trust each other, or
  2) The peers have a commonly trusted third party

My first response to this is: Why should any application have *any*
responsibility for recovering from system-wide paging? Paging is a form
of virtualization, and well-designed virtualization should be
transparent.

But there is a bigger problem hiding inside my point (2).

The "peer" relationship is transitive, and a consequence of this is that
the "commonly trusted third party" therefore turns quickly into a
*globally* trusted third party in any practical design. Further, this
particular globally trusted party must perform storage allocation on
behalf of clients (in order to record relationships), and the mere
*existence* of such an allocation arrangement is a necessary and
sufficient condition to ensure that the system can be taken out by
denial of resource.

So yes, I insist on calling *any* hierarchy of this sort a problem. I
have no objection to L4 hierarchies in particular. The L4 hierarchies
are the most elegant example of this design pattern that I know about.
Unfortunately, the design pattern appears to me to be broken. I have
made this argument for years, and the L4 community has *never* responded
with a demonstration that the requirements I have identified can be met
on top of L4 without compromising something else.

So: if what you mean by "strongly disagree with the design patterns of
L4 systems" is that I disagree with design patterns that do not support
relatively modest standards of correctness, then I must confess that I
do disagree with these design patterns.

I would very much like to see a demonstration design sketch showing that
I am wrong. Perhaps you are correct, and I do *not* understand the L4
design patterns. I have been asking for a counterexample since 1996, and
I should hope that such a fundamental and obvious challenge to the
design might have received an answer by now. I look forward to seeing
it. Arguments of the form "you don't understand designs that we have
failed to disclose or explain" are not convincing.

> Further, the "from A" above doesn't necessarily mean that B' needs to
> request the memory from A.  If B' knows that A' is the one backing the
> memory then it can request it directly from there.  This of course
> requires that A informs A' that it has mapped something to B.  The
> information can be recorded in some location known to B' (it does not
> need to involve any IPC).

Good. You have clearly described the same protocol that has been
described to me by several other people in the L4 community.

This protocol makes assumptions about the trust relationships between
the parties that are not universally true.

There *do* exist many system designs in which this protocol will work
fine. I believe that there does *not* exist *any* system design using
this protocol that meet *either* of the following two requirements:

  global denial of resource is impossible
  sharing mappings across non-symmetric trust boundaries is feasible
    with any acceptable number of IPCs per transfer.

> Viewing the mapping database as a cache can also make perstistence and
> L4 kernel memory management easier to understand.  Since the mapping
> database is a cache, revoking memory that is holding mapping database
> nodes simply means that you're evicting a bunch of cached mappings.
> However, since the pagers need to store the real mapping information,
> they can later reconstruct the mappings.  Applying this all the way
> back to the root pager whose mapping information is explicitly written
> to disk at regular intervals gives you the ability to reconstruct all
> the mappings in the system.  This is essentially what [1] is saying.

This is precisely the argument that Kevin showed was incorrect.

> >From the previous paragraph it should also be clear that revoking
> memory that backs the mapping database is safe in the sense that the
> mappings can later be reconstructed by the user-level pagers.  Of
> course, in some cases one must be careful so as not to revoke memory
> that is backing mapping nodes for "pinned" mappings.  But I guess
> similar issues arise when, e.g., revoking memory that is backing
> certain node tables in EROS.

I do not think that the issues are entirely parallel, but I'm not
entirely sure what argument you are making. If we can get the parallel
more clearly stated, I be able to either agree or clarify. Could you try
to expand on this?

Part of my confusion is that there aren't any node tables in EROS.
Another part of my confusion is that node capabilities are not revoked
in order to support object paging.


shap