Re: problems with hierarchy: L4 pagers

[Espen Skoglund]

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

Jonathan,

You insist on calling the hierarchies in L4 a problem.  To me it seems
that you either (a) just strongly disagree with the design patterns of
L4 systems, or (b) you don't understand them.  Yes, it is true that
the kernel gives no guarantee to the receiver of a mapping that the
mapping will not be revoked.  But this is by design.  It is not a
"bug".

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

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?"  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.  Second, B'/LB
only needs to know about the mapping if the mapping is 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.

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

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


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.

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

Note that the approach to kernel memory management I describe here is
not identical to what is described in [2].  In [2] the pages
containing mapping nodes are transformed into some safe canonical form
before being exported back to the kpager.

        eSk


[1] http://l4ka.org/publications/paper.php?docid=663
[2] http://l4ka.org/publications/paper.php?docid=919