[cap-talk] Claim: correct generic wrapping is not possible in principle

[Jonathan S. Shapiro]

On Mon, 2007-01-01 at 23:30 -0800, Jed Donnelley wrote:
> As described briefly in figures 11 and 12
> and surrounding text in:
> 
> http://www.webstart.com/jed/papers/Components/

Jed:

Thanks for the reference. If nothing else, I hope you realize that I
would have liked to credit prior work, including yours. As with so many
early systems, lots of key ideas were never formally published, and it
makes it very difficult to do so. I'll read through the paper.

> (ii)  At the point where the kernel gets involved we're talking
> about one send buffer and one receive buffer.  That data or any
> "protocol" notions are at a higher level and properly ignored
> at this level.  I don't even understand how they might come into
> play.

I think this bit is a consequence of our divergent use of the term
"buffer".

> (iii) I'm not sure I understand what you mean by this case.
> In our system delivery of data was visible in an incremented
> pointer in the buffers (send and receive).  When a receive
> buffer was terminated, it could happen either because it
> was full (partial transfer) or because the transfer was
> complete.  Do you see a problem with that approach?

Aside from complexity, none at the kernel level. There are a number of
issues at the application level, which we have been addressing back and
forth over the last few notes.

> At the beginning of the above paper you say:
> 
> [quote ommitted]
>
> I'm not quite sure how to describe what we implemented
> in terms of synchronous vs. asynchronous.

My use of "synchronous" in that paper was just a bad choice of terms.
What I should have said was "blocking and unbuffered". The key points
are:

  (1) Transmission does not proceed until receiver becomes
      available
  (2) No internal buffers are used in the OS
  (3) Receiver does not proceed until message transfer is complete
      (or has failed, which is a form of completion).

Perhaps it was obvious to the NTLSS team that these were the right way
to design a primitive transfer mechanism. If so, it is terribly
unfortunate that the argument and its evaluation were not published (or
did not survived in the archival literature that I know about). It would
have saved person-decades of duplicated research effort.

>   Our design
> supported both styles of communication (so I guess in
> that sense it was asynchronous), but the overwhelmingly
> most common use was for synchronous communication as
> with a remote procedure call - which meant that
> performance was quite good for that case.

I think you mean that you permitted transfers to proceed while a
receiver was not yet waiting to receive?

The argument against in-kernel buffering is about cache behavior and
memory bandwidth. It's pretty clear, and we seem to be agreeing about
it. The argument against a transfer where recipient activation is
deferred is an argument about context switch penalties. This argument
was much less compelling before the introduction of the Pentium (crappy
u/s transition speed, untagged TLB), but of course it is now a critical
issue because we all have to live with that piece of crap (the Pentium).

Experience in EROS showed that you don't want deferred activation very
often (it certainly shouldn't be the common case), but when you do, you
really need it. This is part of why Coyotos uses a different mechanism.

I think I am agreeing with you.

> You seem to suggest that the only alternatives are what you refer
> to as synchronous (non buffering) or asynchronous (buffering) - though
> that terminology is a bit odd to me (I usually think of synchronous
> as blocking send/receive and asynchronous as separated sending and
> receiving, but I will try to adapt to your terminology)

The paper also identified timeouts and explicitly rejected them for
reasons of non-reproducibility.

> Regarding "reproducibility" - any timeouts at the application
> level necessarily leads to the possibility of non reproducibility.
> I don't see how this can be avoided.
> ...I argue that there is no way to guarantee reproducibility
> in the face of application level timeouts.  I suppose you can
> try to get around this by not making a clock or a timeout
> mechanism available.  This seems unwise to me.

I have gone back and forth on this many times. I definitely don't like
your "good guy timeouts" (timeout that triggers only under pressure)
because they seem completely impossible to test. Concerning ordinary
timeouts, I go back and forth.

L4 (and predecessors) is probably the system having the most continuous
experience with IPC timeouts. In 20 some-odd years of operation, they
observe four "types" of timeouts that are actually used.

1. Wait forever       the common one

2. Don't wait         when trust is asymmetric

3. Absolute duration  When recovering from a physical device
                      failure, e.g. seek timeout recovery

4. All other cases    Arbitrarily selected "sanity" values
                      that *invariably* become tomorrow's
                      debugging problems.

I went back and forth on this in EROS. Because (3) is very rare, and (4)
is very common, I decided not to add timeouts to the KeyKOS mechanism.
When needed, watchdogs can be implemented external to the IPC system,
though it is bloody awkward. Of course, the *fact* that it can be
implemented externally means that people will do so, and they will then
use the mechanism stupidly, so perhaps I didn't gain anything.

In Coyotos the issue is addressed more coherently by the existence of
FCRBs and the possibility that two messages can be transferred
concurrently. The timeout is simply issued on a second FCRB. This seems
to be both simple and clean.

> I'm afraid your discussion of issues related to revelation of
> a sender's "task id" are lost on me.  Any such "task id" was
> hidden within the process servers designation and visible only
> to another process in possession of a process capability in
> our system.

I was referring to the fact that many IPC mechanisms disclose the
sender's process ID (in the UNIX sense) to the receiver. The term
"task-id" was a specific reference to L3/L4 (where processes are called
"tasks").

> Regarding "Invokee in Wrong State" and the issues of "open" or
> "closed" waits - if I'm understanding correctly we used open
> waits.  As you note with a sufficient number of requests before
> a server ran, these open waits could be exhausted, resulting in
> a client having a send blocked.

In NTLSS, after the client has sent it's message during an RPC
operation, surely it waits in a closed wait for the reply? If not, how
does it distinguish the reply from an unrelated incoming request?

If this is covered in the Components paper, please just say so. I
haven't read that yet, and I don't want to waste your time.

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