Re: Comparing "copy" and "map/unmap"

[Jonathan S. Shapiro]

Here is my original reply to Matthieu. Since I have already sent the
comparison table to the list separately, let me point out that this is
an earlier, and less complete version of that table.

shap

Matthieu:

Did you intend for this to go to the list? It looks like it only went to
me.

In any case, here are my responses, so you may wish to edit before
re-sending.

On Fri, 2005-10-14 at 02:23 +0200, Matthieu Lemerre wrote:
> [Sorry for the long delay, I'm following two university programs and
> had very little time this week]
> 
> So far, Shapiro showed how reference counting wasn't needed anymore,
> and thus eliminates the need for a cap server, which had many issues.
> Capability copy is an operation that is highly wantable.

A cap server is not needed for referencing counting. Depending on the
choice of microkernel and the operations that are provided as
primitives, it may be necessary to implement the COPY operation.

> I also note than Espen Skoglund noted that he could change L4 to add a
> copy operation in a couple of lines.

Yes.

> 
> So I'd like to concentrate on REVOCABLE COPY vs MAP/UNMAP, and
> advocate a bit on why MAP/UNMAP could still be useful.

I think this comparison is a little bit confused. Revocable copy is a
category of operation. Both L4 MAP and EROS/Coyotos Wrappers provide a
mechanism for revocable copy. The main differences are these:

  COPY

                           L4     EROS/Coyotos  Notes
  Primitive?               No     Yes           [1,4]
  Requires Kernel Alloc?   Yes    No            [2,5]

  REVOCABLE COPY

                           L4     EROS/Coyotos  Notes
  Primitive?               Yes    No            [1,6]
  Delegatable revocation?  No     Yes           [3]
  Requires Kernel Alloc?   Yes    No            [2]

  FREQUENCY OF OPERATION in HURD:
    Copy:           common case, probably high frequency
    Revocable Copy: exceptional case, probably very low frequency

  [1] A non-primitive implementation requires more IPCs to implement.
  [2] Allocation accounted to the kernel is a denial of resource
      opportunity.
  [3] Test; If I perform a revocable copy, can I delegate to some
      other process the authority to revoke?
  [4] Espen Skoglund says this could be changed for L4, but the Dresden
      group committed to this at one point and subsequently backed out.
  [5] L4sec is exploring a kernel heap design. If this design is viable,
      then the "requires kernel alloc" answer would change to "no" for
      L4sec
  [6] L4sec is exploring a kernel heap design. If this design is viable,
      then the "primitive" answer would change to "yes" for 
      EROS/Coyotos.

> 1/
> > The main problem with the EROS wrapper design is performance: it
> > requires a number of IPCs. Fortunately, it appears to be a very rare
> > design pattern in our system.

If you use the table (or something similar), this is already said

> 
> 2/
> >The *bad* part is that selective revocation [in EROS] requires some
> >application-level planning.
> This is not too much of a concern, IMO.  I'd like to (humbly) propose
> a solution for this in the next few days (but it's getting late now).

This statement is consistent with what I have said in the email, but I
no longer believe that this is accurate. Here is the real issue:

In any system having both COPY and REVOCABLE COPY, the transmitting
application must make an intentional choice which one to use, and
failure to use the correct choice can have unfortunate consequences.
This issue exists in all of the kernels we are discussing.

> 3/
> > One difference between this approach and UNMAP is that the EROS
approach
> > interacts well with persistence, while the UNMAP approach does not
> > appear to (to me). My question about unmap is that I do not
understand
> > how it scales successfully when the mapping database grows large
enough
> > to become an out-of-memory data structure, and I have already
described
> > in a previous note why flushing and reconstructing the mappings
doesn't
> > work without severe restrictions on system architecture.
> 
> Maybe the L4 people have thought about this.  There is already a paper
> about persistence on the L4ka web site.

That paper assumes that kernel virtual memory is not exceeded, so it is
not scalable. It is a "dump to memory" design rather than a first-class
persistence design. In my opinion, the current L4 system would need a
complete redesign to enable scalable persistence. It simply wasn't a
design goal.

> 4/
> You have to allocate kernel memory for the mapping database.  But
> there may be solutions to that problem ("in-kernel heaps that were
> backed by an out-of-kernel storage allocator.". Is it sigma1?)

Yes. No, this is probably not sigma1. The complication is how to make
this design correctly transactional in a persistent system, and how to
design a kernel that can survive revocation of kernel heap storage by
application code.

This is deeply challenging. It may be solved, but I do not expect that
it will be solved robustly any time soon.

> So, if points 3/ and 4/ could be solved, MAP/UNMAP has better
> performances.  This is really important if it becomes a common usage
> pattern, and I have some ideas that would require MAP/UNMAP
> operations.

I would be very interested to see a list! Perhaps there are simpler
answers.

> But first, here's something I wanted to ask you (I'm too lazy to find
> where) and my question was not clear enough.  So let me reask:
> 
> -What happens in EROS if the client desallocate the storage for an
>  object while the server is using this object (i.e. reading or writing
>  to it)?  How does the server deals with the pagefault?

I just answered this for Neal. See the "instance and instantiator"
thread at

  http://lists.gnu.org/archive/html/l4-hurd/2005-10/msg00268.html

> * I then wondered if memory provided by a client to a server for its
> object allocations could just be mapped to the server.  Indeed, this
> would save some RPCs between the server and the space bank (or, in our
> current implementation, between the server and physmem), and thus have
> better performance.

Yes, in both systems this can be done, but with the cost that the server
must now deal with revoke during mid-operation. The EROS "trusted buffer
object" provides a pre-packaged solution for this that is not doable in
L4sec (at least, not at the moment).

> In L4ng threads are mappable.  So a client could in fact map a thread
> to a server so that it could serves its own requests (to avoir thread
> explosion, maybe we should have one thread per principal.  But maybe
> having a bunch of inactive threads isn't really harmful.).

The real problem is not page faults per se. You aren't going to recover
the thread anyway. The real problem is re-establishing consistency for
all of your data structures after a client defaults. Sending a thread
just introduces another way that the client can default.

> A hostile client could then do nothing to the server, asides from
> making its own thread fault.

Is it clear from my comment above that this is FAR from true?

> This has another advantages not only the clients pays for its memory
> usage on the server, but it also pays for its CPU time usage and can
> adjust it (provided that it has some control on the time slices
> allocated to the thread, that it can take from its "CPU time
> container")

CPU time has nothing to do with passing/mapping of thread resources. It
has to do with passing/mapping of scheduling resources, which is an
orthogonal issue.

> So the user provided thread just has to make a call to
> the server thread.  This is local IPC, so potentially very fast.

Local IPC was a bad idea, and is going away. It cannot be implemented
cleanly in a protected system in any case.

> * I also noted, in a previous answer, that when you use a private
>   server, you can just map memory to it : you don't have to copy it.
> 
> Thus, I am wondering if MAP/UNMAP isn't the best operation for some
> kinds of pattern (with the above exemple memory usage).

Sharing memory (or storage) is a fine design for many patterns. This is
orthogonal to whether the primitive is MAP or not.

> * I'd like to come back on the argument of the transport chain of
>  processes: you forgot that there is also a GRANT operation.  If the
>  intermediary threads are meant to act only has a transport or proxy,
>  either it wants to retain control and then MAPs the capability, or it
>  doesn't want to and can just GRANT.  At that moment the intermediary
>  processes can just die.
> 
> I'm not arguing that MAP/GRANT is a better solution than COPY for
> transmitting a capability from a server to a client, I am just
> wondering if there is any problem with the GRANT operations.

The last I heard, the L4sec group was considering dropping GRANT. In any
case, GRANT does not help. In order for grant to help, *all* transfers
would need to be done with GRANT, and there are now two problems:

  1. It precludes two processes or threads ever holding the same
     capability at the same time.
  2. There is no way for the recipient to check whether this
     condition has actually been satisfied for the capabilities
     that it receives.

> >> Unmapping [endpoint] objects is not that harmful: upon RPC attempt,
the
> >> client only has to be prepared to an error.

This really depends a lot on how hard exception recovery is in your
code. It is exactly as hard (or as easy) as getting any other bad
ERRNO-type value back.

> > Further, you have not addressed the problem of reconstructing these
> > endpoint mappings. Remember that L4 revokes in two situations:
> >
> >   1. When the endpoint is intended to be revoked.
> >   2. When memory must be reclaimed for other use.
> >
> > In the second case, mapping reconstruction is required. The protocol
> > needed to do this is complex, and the security and robustness
> > consequences are somewhere between unpleasant and a complete
disaster.
> 
> I don't understand you here.  When does L4 revokes memory (i.e. fpage
> mappings?)?  And I am not talking about revocation of memory, but
> about communication endpoints revocation.

The two types of revocation are the same for the purposes of this issue.
The point is that B' cannot reconstruct the mapping.

In practice, it would not be A' revoking the mapping either. The problem
is that A' ultimately got its storage from sigma1, and if sigma1 needs
to page something out it is going to need to revoke the mappings. This
revokes A', and consequently revokes A and B. The problem is that when B
now touches that object, it doesn't have enough information to get it
paged back in successfully.

> > So the real question is: "Do the bindings to the storage resource
> > disappear when the allocating thread disappears?" In L4sec, the
answer
> > appears (to me) to be "yes", but it is possible that they have some
> > clever way to avoid this problem. In EROS/Coyotos, the answer is
that
> > the lifespan of a storage allocator is different from the lifespan
of a
> > thread. As long as the storage allocator survives, the object that
lives
> > in the storage survives.
> 
> Couldn't the allocating thread which holds memory ressource just grant
> the memory to another one?

Not necessarily. The GRANT operation prevents sharing after the GRANT.
Architecturally, you really want the following two questions to be
separate decisions:

  1. Is it sharable by multiple parties?
  2. Who can revoke it?

There is really no reason to think that the answers should be in any way
correlated in a general purpose architecture.

shap