[cap-talk] Another "core" principle - virtualizing memory

[Jonathan S. Shapiro]

On Mon, 2007-01-01 at 21:07 -0800, Jed Donnelley wrote:
> At 08:59 AM 1/1/2007, Jonathan S. Shapiro wrote:
> >Jed: if this is part of the Process object, please explain how processes
> >can share memory,
> 
> This is what I described before that you criticized as merely a mechanism
> for distributed shared memory.  It can be distributed or not, it works
> locally or remotely.  It works because this is how processors must work.
> Just to repeat the overview (for anybody that didn't read the other
> message in detail), the basic idea is that data storage objects
> (call them files, or segments, or whatever) are passed to the Process
> object for mapping into memory.  They need appropriate locking with
> notification (write locks and read/write locks) for the shared
> memory application.  This is all rather simple.

You have reduced the problem to a previously unsolved problem, which is
the construction of "files, segments, or whatever". As I stated in my
earlier mail, each of these is an example of an address space. So your
answer amounts to "you build an address space by mapping address
spaces". You have a reductio problem here: the map operation is a
higher-level operation that is implemented in terms of some lower level
data structure (namely: mapping tables). You cannot define the mapping
operation without accounting for how these lower-level structures are
allocated and accounted for. The issue at hand is to describe within the
object-capability paradigm how this occurs. Read on, because I saw your
answer and I don't think it satisfies my requirements.

> >and please give a sane story for storage accounting if
> >(1) the space used for the mapping is accounted to the allocating
> >process, the space is (partially or wholely) shared, and the allocating
> >process exits, OR (2) two processes interleave mapping operations within
> >a shared region.
> 
> The metadata for the process is "charged" to the process.  The
> memory when it is used (mapped and active) by a process is charged
> to the process.  The data storage is charged to the "file" object,
> which also is charged for it's own metadata of course.

So you seem to propose that there is a relatively high-level kernel
operation "map", which accepts as arguments:

   a process (implicitly: the invoking process),
   an address relative to the process's address space, and
   an address space to be mapped at that address (a "file, segment,
     or whatever") whose construction happens by unspecified means.

This operation is somehow entitled to charge a process for the storage
that is used by the low-level data structures that record the desired
mapping. How does the kernel know what storage pool should be used as
the source of this storage (which is the essence of storage
accountability)? Since the lower-level mapping data structures are
pageable, this is an allocation of *real* resource, and it really needs
to come from an explicitly designated storage pool.

There are three ways that I can reconcile your assumptions, but none of
them is consistent with your outcome:

  1. Assume that every process names (via capability, in the process
     state) the storage pool that should be used for allocating mapping
     data, and the kernel performs some sort of an upcall to this
     storage pool object when it is necessary to allocate low-level
     mapping structures. But in order to return those objects, it must
     be possible for the storage pool server to name them via
     capabilities, and voilla they are now first class.

     The (experimental) "split" operation in Coyotos works this way.

     This cannot be your model, because you clearly do not intend
     that the low-level data structures ever need to be reified.

  OR

  2. Assume that the low-level mapping implementation structures are
     never shared (because they must be reclaimed when the "owning"
     process exits). In this case we could allocate them by requesting
     untyped "bare" storage from the storage allocator and somehow make
     this storage private to the kernel.

     This is approximately the notional L4.sec "user backed kernel heap"
     notion, and its implementation is very problematic because of
     aliasing concerns.

     Further, the decision not to share low-level mapping structures has
     a measured performance cost of 1000x on Pentium 120Mhz on some
     operations that are performance-critical in real applications. The
     multiplier would be much higher on a current-generation Pentium.

  3. Assume that there is sufficient kernel memory, and that the
     low-level mapping structures do not need to be allocated from
     accountable storage.

Clearly you have a fourth picture. Can you state it in detail?

> >The decision to make address spaces first class independent of
> >objects, and the decision to make them recursively defined with pages as
> >a (degenerate) atomic address space, were two of the most elegant and
> >beautiful decisions of GNOSIS. They constitute the first successful
> >conceptual disentangling of address space design confusions that go back
> >into the earliest multiprocess operating systems (or at least, the first
> >that I know about).
> 
> Sorry, you lost me in the above.  I presented a solution to a problem
> that you defined.  Do you believe it isn't a solution?  If so, why not?

Your solution does not satisfy the accountability requirement.

> > > Hmmm.  I'm not quite sure where this discussion stands.  All I care
> > > about is that the objects needed for a practical (well performing,
> > > subject to any needed sort of analysis, etc., not necessarily up to
> > > some arbitrary standard of "elegance", which may be a matter of taste)
> > > systems can be wrapped as needed for modularizing higher level
> > > services (e.g. remote access, revocation, responsible delegation,
> > > etc.).
> >
> >We haven't lost that. We've merely explained why your belief that it was
> >trivial to wrap objects denoting real memory was wrong. In a nutshell,
> >you were busy considering the network distribution problem, and failed
> >to fully consider the requirements of front-ending page capabilities in
> >the local case.
> 
> I agree that it's possible to design primitive (kernel) objects in
> systems so that virtualization isn't possible.  RATS did that, so
> that much is obvious to me.  However, I also argue that it's possible
> (in fact very simply so) to design a system that includes mapped
> virtual memory in which all kernel objects are virtualizable.
> Not only that, but I argue that it can be done efficiently.  I
> believe this because I've seen all the details laid out.  I believe
> doing so is pretty much independent of processor architecture,
> as long as the mechanism is contained within the appropriate objects.

Can you explain how your DSM-style solution accounts for the behavior of
load and store instructions, which *must* be reifiable as capability
invocations if the system is to remain a pure object-capability system?

shap