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

[Jonathan S. Shapiro]

On Sun, 2006-12-31 at 20:15 -0800, Jed Donnelley wrote:
> >If we restrict ourselves to capabilities implemented by processes
> >(presumably stretching to include the kernel as a distinguished
> >process), we cannot account for address spaces, memory mapping, or
> >shared memory within the protection model of the system. That seems
> >disastrously bad.
> 
> I don't believe any of the above is true.  I believe one can
> use data (file, memory, you pick a name) objects and pass then
> to Process objects for mapping into memory...

You have a reductio problem buried in your response, because it is not
possible to pass memory. It is only possible to pass a mapping of
memory, and we must not make our solution rely on that because the
problem we are discussing is how to construct such a mapping within the
object-capability model.  Ditto files (fundamentally, a file is built on
an address space).

It is the "mapping into memory" part that we cannot account for. How,
using only object-capability mechanisms, does the process do that, using
only object-capability mechanisms, without making the primitive storage
objects (pages) and the mapping tables (page tables, but in KeyKOS/EROS:
Nodes) first class objects that are named by and manipulated through
capabilities. [I concede that there are other possible data structures
than Nodes, but there will be *some* data structure that records the
relationship between addresses, permissions, and pages]

Essential requirement: your solution may allocate bounded temporary
storage internally, and it may allocate a bounded number of entries in
software caches *provided* those entries can be flushed at the end of
the mapping operation without altering semantics. The implementation may
NOT otherwise allocate storage that survives the mapping operation,
because such storage would not be (and cannot be, due to sharing)
property accounted for.but

If the "kernel does not allocate" restriction is removed, then I agree
that address spaces can be abstracted to a greater degree. There are two
difficulties with this abstraction step:

  (1) Such a kernel is intrinsincally non-robust, because it is not
      doing (and cannot do) proper accountability for resource
      allocation.

  (2) We will discover that we have introduced a non-capability
      protection mechanism in the place were we describe the per-page
      mappings, and this will take us out of the statically analyzable
      model where mappings are concerned. This, please note, would
      render the confinement verification invalid.

>   This can allow
> you to do manipulation of address spaces, memory mapping,
> and shared memory within a pure (and virtualizable object-capability
> model) but still allow any sort of hardware page table or memory
> hardware, as it all has to map to blocks of data.

So far, we haven't found a hardware (or software) translation mechanism
that cannot be handled just fine under the constraints that I gave.

> >Perhaps worse, we cannot account robustly for resource allocation if we
> >don't architecturally reify the structure of address spaces. Mapping a
> >page carries with it a requirement to allocate some metadata that
> >records the space-relative offset of the page and its permissions. In
> >the presence of sharing, this storage cannot be correctly written off as
> >fixed per-page overhead. If address spaces are durable, this storage
> >occupies space on the disk as well.
> 
> This is part of the Process object, much like there is overhead for
> meta data structures for file objects, directory objects, etc., etc.

Jed: if this is part of the Process object, please explain how processes
can share memory, 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.

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

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

-- 
Jonathan S. Shapiro, Ph.D.
Managing Director
The EROS Group, LLC
+1 443 927 1719 x5100