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

[Matthieu Lemerre]

"Jonathan S. Shapiro" <address@hidden> writes:

>> > 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?
>
> See "Vulnerabilities in Synchronous IPC Designs":
>
>       http://www.eros-os.org/papers/IPC-Assurance.ps
>
>> * 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).
>
> Not necessarily.
>
> I think you are struggling here with something difficult. Taken alone,
> you are correct that COPY and REVOCABLE COPY are not enough to resolve
> this problem. The interesting part about EROS is the ways in which the
> pieces interact to let problems like this be solved. The difficulty is
> that you need to step back and figure out how to put those pieces
> together. One of my tasks over the next month or so is to write a
> journal paper that captures some of this.
>
> Have a look at the IPC Vulnerabilities paper. It is an attempt to
> capture *some* of the issues.

I read it, and I admit that it is very clever.  It seems that timeouts
were impossible in EROS, because applications don't control their
swapping, and thus they cannot know how long a string copy will take.

In the Hurd, applications are in control of their pagers; so I think
IPC timeout is sufficient.  We actually use a zero-timeout for
transfer timeouts, which mean that pagefault during string copy is
impossible.  (We changed L4ka's Xfer timeout behaviour for this, see
http://lists.gnu.org/archive/html/l4-hurd/2005-01/msg00108.html for
more details).

By mid-operation, I actually didn't meant during IPC.  (My terminology
isn't as clear as yours, so (as you may have noticed) I often have
problems making me understood).

By mid-operation, I meant during the RPC, not during the IPC.  That is
to say, during the non-IPC phase of the RPC (i.e. when the server is
computing something).  My question was: what difference does it make
if memory is copied from a client to the server, instead of revocably
copied?  Destroy and revoke while the server is using the memory
object seemed equivalently harmful to me.

But I assumed that transmitted memory was mapped (in the sense of
mmap, nothing to do with MAP vs COPY) into the server address space.
Where you are instead using string copies.

I was first thinking "isn't it a waste of cycles?  Passing fpages is
much faster than copying data".

It then occured to me that when you perfor a read() operation (on
UNIX), what you want in the end is data to be copied from your file
capability to your buffer.  Thus, string copy is well adapted for many
IO-operations e.g on files. (Because you can perform only one copy,
when the TBO is mapped in the client address space).

Still, some questions occur to me:

-If clients want to perform a read on a buffer smaller than a page
 size : how to do this without doing two string copies and preventing
 the server to overrun the buffer?  Wouldn't it be better to map the
 TBO in the sender's AS in this case?

-How do you perform mmap-like operations in EROS (maybe you already
 answered to that question, I didn't have time to read all of your
 answers yet.  Sorry about that.)

-If the kernel performs the copy, can you preempt the copy (this is
 necessary for low latency operations, or this could maybe be a denial
 of CPU ressource attack if time passed in the kernel for the copy
 isn't accounted to one of the participants)

-If data isn't ready yet (for instance it's dynamically created) , you
 have to prepare it in some buffer before sending it.  You would then
 perform two copy operations, when you could have done one if you
 wrote directly in the client buffer.


I'd like now to explain a bit more my motivations behind what I
proposed.  What Neal and Marcus wanted to do in the Hurd on L4 was to
use fpages for passing of data.  As mapping of fpage is unsecure,
physmem was used to act as a trusted third party to pass what we call
"memory containers".  This scheme requires quite a number of RPCs: in
order to do an IO-operation, you have:

-To create a new lesser container (that the server can't revoke)
-To fill it with physical memory  (maybe these two first can be combined)
-To copy the container capability to the server
-The server then calls physmem to map the memory into its address space
-It fills the appropriate region with data, and then returns to the client.

What I wanted was to reduce this number of RPCs: it would be cool if
we could just:

-call the server, mapping the fpages so that he can fill it 
-return.

But the security problem still have to be solved, that's why I
proposed the mapping thread solution, but you pointed some problems in
it (and I trust you on finding them more easily than anyone else :))

>> 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.
>
> I agree. In practice, all situations of homogeneous storage appear (so
> far) to involve symmetric trust (i.e. all parties trust each other), so
> there is rarely any problem in this case.

OK.  I think most of the cases are when a client set up a server for
its single purpose (and the server runs so on the client's memory).
>
>> -"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".
>
> How can this possibly lead to a robust system? You have just architected
> a denial of resource opportunity!

Hum, of course.  Let's refine this.

* My "global thread server" example was the example of any necessary
system server.  Another example would be the root space bank in EROS.

These servers have to do ressource accounting, and how to account
ressource on memory provided by the client?  How a physical memory
server can account where there is free memory on client-provided
memory (well, maybe there is no problem for that in EROS because of
persistence).  Or how can a hard drive server account free sectors on
client-supplied memory?

Maybe I'm wrong, but it seemed to me that that these kind of servers
needed a bit of their own memory for ressource accounting. However,
(luckily?) ressources are limited, so you can't exhaust memory used
for ressource accounting (if the ressource can only be allocated
once.)

* There is also the examples of servers which have to share state
  between clients.  But I do think that in these servers, we always
  have a client which creates the objets, and can always provide the
  memory.

>> >> 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)
>
> No. Consider the following counter-example:
>
> We assume from your initial conditions that the server has multiple
> threads. Therefore, I will assume that the server is implemented with at
> least one critical section.
>
> The client thread enters the critical section. Before exiting the
> critical section it is killed. Note that this does NOT release the
> critical section lock!
>
> Please give a general strategy for recovery, or at least a set of
> architectural principles for how to design a multithreaded server that
> can recover from this situation.
>
> Hint: it does not exist in the general case, and the field of computer
> science has been looking for useful design patterns that would support
> practically useful cases for 40 years without success. The best
> solutions so far involve designing the entire subsystem transactionally,
> with a single atomic update operation that commits the operation.

That was one of my points.  The threads provided by the clients
*never* enter critical sections:

-Only the thread provided by the client can manage the client's data,
 so there is no need to set any lock to protect these.

-Whenever they want to enter a critical section for something "global"
 to the server (for instance allocate some ressource), they just do an
 IPC to the server's thread, which cannet be revoked by anyone, and
 does not count on untrusted (unmappable at anytime) memory.

So critical sections are computed by threads that cannot be stopped,
so hopefully it always exit the critical section.

>> >> 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.
>
> It is true that threads are the unit of dispatch. They are therefore the
> unit that is controlled by the scheduler. This is true in EROS/Coyotos
> as well.
>
> However, threads to not migrate from one process to another in L4 in the
> way that you imagine. What you are really proposing is that the
> *binding* between the thread and it's scheduling slot should migrate.
>
> Actually, there are two separate decisions here:
>
>   1. Should the binding migrate?
>   2. Should a preemption point exist in the IPC path?
>
>      A preemption point is any point where the kernel asks: "Should
>      I consider scheduling something else now?
>
> The concept of "thread migrating IPC" is really just question (2) where
> the answer is decided to be "there are no preemption points in the IPC
> path". The name "thread migrating IPC" was a horrible name, because it
> simply does not describe what is actually happening.
>
> You are considering a design in which the answer to (1) is "yes", or at
> least "possibly". This is known under various names, but is most
> commonly called "schedule donation", "priority donation", or "priority
> inheritance scheduling". It's really quite a horrible idea.

OK I understand that.  The receiver of a schedule donation could
possibly misuse the scheduling ressource, so it's better if we just
have the time slice passed from the caller to the callee during IPC.

I often wondered, in the general case, what happens if you do this
when your time slice is nearly finished.  The callee thread in the
server would then stop while computing the operation?  Could that be a
denial of service attack on the server?

I note that on the "thread given by the client" model, the above
problem does not occur since all you can do is prevent yourself from
being served.

>> >> 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?
>
> The problem is that the semantics of local IPC was wrong, and it wasn't
> wrong in a fixable way.

OK.  I note that in this case, enter critical section is very costly.
But I also note than Espen disagrees.
>
>> >> * 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).
>
> It is true that you need support for establishing a shared mapping. It
> does not follow that MAP/UNMAP is the best design, or that creating this
> kind of mapping should be convoluted with revocability.
>
> However: I agree that it is desirable to have an in-kernel mechanism
> that allows to processes A and B to quickly establish a shared region.
> Further, I agree that the flexpage notion (a poor name, since it has
> nothing to do with pages) is useful here. What we wish to do is quickly
> establish a shared mapping of 2^k units that are naturally aligned.
>
> This is one of the reasons that Coyotos is shifting from the Node data
> structure to the PATT data structure. It will allow us to establish this
> sharing by a single capability copy.

This is great.

Thank you for pointing all the weaknesses of what I proposed.  I feel
like I'm quickly learning key notions thanks to you (and I'm beginning
to see security problems everywhere ;))