[cap-talk] Messaging, [a]synchrony, and select

[Jonathan S. Shapiro]

On Wed, 2007-01-03 at 17:07 -0800, Jed Donnelley wrote: 
>At 09:42 AM 1/3/2007, Marcus Brinkmann wrote:

> >Consider a system that emulates the
> >select() POSIX system call using a synchronous call primitive, say on
> >5000 file descriptors.  There are not many applications that need this
> >functionality, but those that do are decidedly performance critical.
> >Sometimes additional threads are not cheap enough.
> >
> >A system which is designed to support this efficiently depends on
> >asynchronously delivered notification that can unblock a blocking
> >thread.  It is not feasible to implement such a mechanism in a
> >synchronous message system.
> 
> Fine.  Provide such an interface.  There's nothing about the base
> object-capability model that prohibits doing so.


Ironically, this was the original impetus for changing the IPC model in
Coyotos. There is no known kernel mechanism for implementing select
without dynamic in-kernel allocation. More generally, there is no know
mechanism for efficiently implementing an MxN rendezvous in O(M+N)
memory.

In abstract, you can build select on more primitive mechanism. In
practice, the performance impact is so great that the two systems are
not computationally equivalent in any meaningful sense.

I agree with Jed that implementing this does not violate the
object-capability model, but it is very easy to do it in a way that
violates robustness.

> >Note that people who advocate a synchronous call primitive do not say
> >that select() can be implemented on top of it if pressed on this
> >point.

Sure we do. We just don't claim any efficiency for it. :-)

> Sorry, I do (as I did above).

I think that's a little silly. Such a system would fail any modern
application level benchmark suite -- and many *microbenchmark* suites --
no matter HOW much engineering effort you put into tuning the blocking
IPC mechanism. At an abstract level the computing models are equivalent,
but in any practical sense the differences are quite large.

>   I also say that I don't particularly
> care whether there is some sort of asynchronous communication
> primitive in the system...

In one sense this is orthogonal to the select() discussion, but in
another it isn't.

If messages are delivered asynchronously, and there are multiple
concurrent senders, then one of the following three statements holds:

  (1) The messages are serialized, in the sense that all fragments
      from one sender will be received before any fragment from a
      second sender. In this case you might as well use a synchronous
      primitive.
  OR
  (2) Wherever messages are transferred in interleaved fashion,
      they go to distinct receive buffers [equivalently: fragments are
      tagged such that the recipient can unscramble them].
  OR
  (3) The messaging system yields scrambled eggs, and we need not
      consider it further. This design is most commonly known by
      the name "UNIX pipe".

Asynchronous messaging primitives are mainly helpful when you really
have simultaneous senders (concurrently, not just potentially). The cost
of this type of messaging is that the recipient needs multiple receive
areas and usually multiple threads. Even if we ignore the complexities
of concurrency that this entails, the amount of memory required simply
to have 5,000 threads blocked with available receive areas is
staggeringly large. Note that this memory rapidly becomes backed by real
pages -- the swap space implications are staggering.

  [The 5,000 thread number, by the way, is not hypothetical. The
   application in question is called "Oracle". It's not unheard-of
   in web servers, either.]

What the select() primitive does is provide a single-bit notification
scheme per sender, allowing the receiver to demultiplex the senders
using an event driven strategy, accepting the incoming messages in
whatever fashion seems appropriate to the receiver. Used well, this
significantly reduces the memory required by the server.

The only point I am trying to make here is that an asynchronous
messaging transport doesn't make the implementation of select() any
easier. I do not intend this as an argument against asynchronous
transfer.

Select is a subtle and important primitive. It has a bunch of properties
that are difficult to emulate well simultaneously. It's actually a good
torture test for an IPC proposal to ask how it can be used to simulate
select() well.

> I guess I should also mention that I'm not concerned about
> what I would call "out of band" perfection in the wrapping
> mechanism, specifically anything like "EQ?" or "MyCap?".
> It is enough for me that functionally a wrapped object
> (capability) behaves in the same way as the original
> in terms of what happens when data and capabilities
> are sent in and come back.

I think I agree. I suggest that there are two "lines in the sand" for
virtualization:

  friendly virtualization: client must go out of their way to
    discover that the object has been virtualized. Specifically:
    they must execute some protocol that would not normally be
    done.

  precise virtualization: mechanism must succeed in the face of
    client attempts to detect it (excluding detection through latency).

Unfortunately, the MyCap? operation is often part of the normal
protocol, so friendly virtualization is harder than it sounds.

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