Re: problems with hierarchy: L4 pagers

[Espen Skoglund]

[Jonathan S Shapiro]
> 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?

Given that I don't know what this "convincing example" is, I can't
tell if there is a design that "solves it".  BTW, what do you refer to
when you say "description" here?  Do you mean a description of mapping
and the mapping database in general, or do you mean a description of
user-level managed kernel memory?

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

It's unclear to me where you see this mutual trust.  Yes, a thread
must trust its pager.  However, a pager need not trust its client(s).

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

True.  B can not trust A to make this exchange.  And further, B can
not necessarily trust A' to re-provide the mapping.  More elaboration
below.

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

Er... by "system pager" here I can only assume that you mean something
like a root pager.  And of course, if the root pager decides to take
away all the mappings in the system it can do so.  (But I suspect this
was not the point you were trying to make.  Or was it?)

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

If you need A' to be informed, then just make A inform A' by writing
"I will map X to B" in some predefined location (just as on the
receiver side).  Anyhow, Neal was arguing about the case where B' asks
A to re-provide the mapping.  His assumption obviously was that A was
still alive.

As for trusted third party: see below.

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

Yes, every mapping CAN be revoked, but B' need only know about it
WHEN/IF the mapping is revoked.  Anyhow, this doesn't matter much
because of the third point.

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

I see absolutely no reason that the pager needs to trust the
application.  Is it because the application can write to some page
provided by the pager?  I'm lost.


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

What I'm saying is that it is an architecturally acceptable choice to
require every program in a system to include a pager that can recover
from the effects of system-wide paging.

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

There *is* a need for a commonly trusted party to provide some
"connection" between the peers.  However, this globally trusted party
need not be involved at all.  In particular it need not be involved in
any memory allocation.  Further, if a server does need to allocate
storage it can do so from a client specific container, much like you
have client provided space banks in EROS (if memory serves me right).

Now, back to the commonly trusted third party that is needed if B is
being really paranoid.  Here's a short description of how you could
imeplement this using tag spaces.  [Note: in the spec I'm writing I'm
using the term tags and tag spaces instead of IDs and ID spaces to
make sure that there are no confusion with, e.g., thread IDs.]

What you basically need to do if B is paranoid about the mapping from
A being revoked and not recoverable is for some sort of capability
COPY operation to take place from A to B.  Here's how it can work:

 o The root server creates a tag for every object (e.g., page frame)
   it manages.
 o The tag effectively implements a capability to the object.
 o In addition to (or instead of) handing out the object itself, a
   server can hand out the tag corresponding to that object.
 o Using the equivalent of an IDENTIFY operation any server who
   posesses a tag from the root server can verify the authenticity of
   a root server tag it receives.
 o A can map a tag to B.
 o B can ask B' to verify the autenticity of the tag.
 o If B' does not posess a tag that identifies the same object it can
   request it from someone it trusts.
 o When B' request such a tag it will of course have to provide the
   original tag as an argument.
 o The process can continue until someone in the hierarchy posesses a
   tag that can identify the appropriate resource.

The important point here is that the party that eventually manages a
successful IDENTIFY operation need not be the root pager.  In a real
system I would expect to have the load somehow distributed (perhaps
even dynamically and on demand).  In fact, since the different space
types in my proposed spec are completely orthogonal to each other one
can share a single tag space between the root pager and a huge number
of other pagers (each having their own memory and communication spaces
if you want).  In the extreme case one could even start one of these
pagers for every application.  Further, if these pagers are restricted
from actually modifying their tag space, they don't even have to be
trusted by the pagers higher up in the hierarchy.  (Remember that this
was a design where the tag space was shared.  If the tag space is not
shared you don't need this no-modify restriction.)

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

Would a system as sketched above satisfy you more?  Global denial of
resource is not possible if you use client provided memory, and
sharing accross non-symmetric trust boundaries requires a number of
IPCs that depends on how quickly you can identify the mapped tag
(i.e., how you construct your mapping hierarchies).

However, in my rush to write down my proposal above I might very well
have missed out on something important.  I would very much appreciate
if you could point this out.  (And I confident that you wouldn't
hesitate to do so. ;-)).

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

In what way is this argument incorrect?  I'm sure there is some detail
that escapes me and I would be happy if you can jog my memory here.

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

Sorry.  I'm apparently not terribly familiar with EROS teminology.
What I was referring to was nodes, not node tables, and what happens
when you (forcibly) reclaim the memory backing these nodes.

        eSk