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

[Matthieu Lemerre]

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

Right, I was really too tired when I wrote that.  Sorry.

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

OK.

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

OK.  Maybe they have plan for it, though.

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

It seems to me that you avoid REVOCABLE COPY because it is less
efficient than COPY (need to create a new object, etc...).  My point
is that there are cases where REVOCABLE COPY can be a replacement for
COPY.

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

* What are they?  Are they something that make sure that the buffer
can not be revoked for a certain amount of time?  Or do you have a
more clever way to deal with this?

* I don't see the difference between COPY and REVOCABLE COPY with
  regarde to dealing with revoke during mid-operation.  The memory can
  be revoked in either cases (either selectivly REVOKED or the memory
  object could be destroyed, and this makes no difference to me).

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

It seems to me that:

-Either the objects to a server are "alones", or have only relations
 between objects allocated by the same (homogeneous) source. In this
 case, if the memory is revoked during mid-operation, then we don't
 care if the data is inconsistent (because the client just lost the
 thread providing the ressource allocated by itself.). I don't see
 additional harm in this case of homogeneous storage.

-"Global states" (like, for a global thread server, which thread has
 the server mapped (which is something needed on L4)) would be run on
 the server's memory (and cannot be unmapped except by owner of the
 memory on which the server is runned, which we must assume to be
 trusted), and would be manipulated by the "global thread".

There may be a need for exchanging datas between "global state" and
"client state", which you described in another email by a
"paranoidmemcpy".  This could be IMO written using L4's string items.
(well, to be secure, we can't just directly copy the data from the
client state to the server state, because a "transfer pagefault" could
occur, if the client unmaps the memory during the transfer.  So there
need to be a local buffer in the trusted memory for memory transfers,
unless the kernel can prevent UNMAP operation during string items
transfers.).  But maybe there are security problems that you solve
with paranoidmemcpy and which I don't even see.

I agree that this type of servers should then be written with care,
but the approach I describe above seems to me quite similar than your
"paranoidmemcpy" method.  Still performance may be quite bad.

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

I should rewrite this sentence: A hostile client could then do nothing
to the server, asides from making its own thread fault, provided that
the server is written with care (which may not be easy, but maybe
easier with having two threads communicating than using a
specialmemcpy operation)

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

Threads are a basis for scheduling in the L4 world, so they are not
completly orthogonal.  Still, I agree that the L4 scheduling API does
not seem to permit fancy scheduling (I didn't checked the new
real-time extensions from Fiasco yet).  This is evolving, see for
instance
(http://i30www.ira.uka.de/teaching/theses/topics/index.php?thid=49)

Still, a simple approach would be to associate each thread with a "CPU
time ressource", which could be recursively mapped.  So a client would
only consume its CPU time.  Of course I already see problems with the
communication between the "server master thread" and the "client
thread allocated by the server" when one runs out of CPU time...

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

Why that?  If the protected objects are stored on kernel immutable
memory, how could a thread modify it?  Or is the problem something
completly different?

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

What I wanted to say is that this design pattern fits well with the
MAP/UNMAP operations, and seemed to have better performance.  Of
course, this is to counterbalance with the "global thread/local
thread" communications (when needed).

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

Right.  As for 2., I imagine this is a problem because the chain of
processes can be potentially untrusted, but the implementation of a
capability can be checked?  I didn't thing of it because (as stated in
another discussion) we don't have (yet?) such things in the Hurd.

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

Well, I think you always have to be prepared for an error, just
because the server you want to talk to might have die.

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

I didn't know there was an "endpoint pager" (the L4sec spec isn't out
yet).  I have even never thought on how it could be useful.

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

But when sigma1 needs some memory, it could be arranged that it does
not revoke a fpage containing endpoints informations.

What we planned to have was that each task would run on its own memory
and the pager would then maps it to the application.  It would
renegociate contracts with the physical memory server from times to times.

Thus we could change sigma1 in "sigma1 asks physmem for some memory,
that physmem kept just in case of.  At next renegociation physmem keep
some more memory to eventually give to sigma1" and thus get rid of the
problem (or we could find something more secure with regard to denial
of storage attacks)

Thanks,
Matthieu