[coyotos-dev] Re-thinking FCRBs

[Jonathan S. Shapiro]

I have spent most of the last three days trying to figure out what to do
about FCRBs. Valerio is right: their motivation does not justify their
complexity -- at least not in their current form.

In essence, an FCRB is a "proxy" for a process that is blocked in a
receive state. A blocked process involves a lot of state, where an FCRB
is comparatively small. The idea is that if the process is willing to
allocate an object that stores all of the information needed for a
receive to happen, it should be able to do this and continue executing.
So one way to look at FCRBs is that they are the mechanism for
asynchronous receive.

As far as I can tell, the FCRB complexity came from several factors:

  1. I had message payload receipt tied together with scheduler
     activation.

  2. Separating the FCRB from the receive block makes them really
     hard to understand and fairly expensive to implement.

     This was motivated partly by the receive block size, which was too
     big in any case.

  3. I was trying to tie all of this in with some SMP message dispatch
     ideas that haven't been articulated clearly enough yet.

  4. The motivation wasn't articulated anywhere, so it wasn't clear
     what problem was being solved.

Today I decided to start over. I went back to the EROS-style IPC design
(i.e. using explicit running/open-wait/closed-wait), and I re-examined
the whole send block/receive block logic on the assumption that we would
*not* do asynchronous receives. There are several conclusions from this:

  1. The capability string idea was a bad idea, and needs to be removed.

  2. Having 64 IPC words (VDRs) is excessive. EROS only had problems
     with the 4 register limit in a few cases, and these happened purely
     because of register width issues. Having only 4 IPC words would
     probably be enough, and 8 is certainly enough **provided** the IPC
     words are 64-bit quantities.

Once these issues are addressed, the receive block is reduced to a
fairly manageable size. Obviously we can do blocking receive, but if we
needed to have asynchronous receives for some reason we could now put a
complete receive block into the FCRB.


** Why use an FCRB at all?

You don't need FCRBs at all (ignoring contrived cases) in any situation
where the process would perform an "open" wait. In these scenarios:

   1. The sender is almost always willing to block.

   2. The receiver can receive any incoming message.

   3. Selective revocation can be accomplished using less space by
      applying a Wrapper object (these didn't exist when FCRBs were
      introduced).

   4. If you want to handle requests using multiple lightweight threads,
      this can be accomplished by having two heavyweight threads: one
      to perform an open wait and place the request on an internal
      queue at application level, and the other to execute the requests
      from that queue. At most you need "K+1", where K is the number of
      hardware CPUs.

So FCRBs are not motivated by the open wait case.

Let's look at the closed wait case in the *absence* of FCRBs. In a
closed wait, the situation is approximately the dual of the open wait
case:

   1. The sender is usually a server performing a reply to you,
      and is generally NOT willing to block.

   2. You are generally waiting for a reply to some specific call, so
      you need to be looking for that specific incoming message.
      Other messages cannot reach you until the current receive
      completes.

      The exceptional case is things like asynchronous I/O.

   3. Selective revocation isn't an issue, because the protected
      payload mechanism is going to take care of that.

   4. If you need to block for multiple replies at once you
      are going to need to have an active receive on each one.
      In the absence of FCRBs this requires that you have
      a heavyweight thread waiting in a receive state, because
      the sender will not block.

Points [2,4] combine to provide the motivation for FCRBs.

** When are FCRBs appropriate?

Basically, FCRBs are appropriate in the same circumstances that the UNIX
"aio" interface is appropriate. You need to start a bunch of operations,
you want to know when they complete, but you can continue processing
without knowing this. What the FCRB accomplishes is to leave you a way
to get the response (which would be dropped if nothing waits for it).

** Why not just use a heavyweight thread in this case instead of an
FCRB?

Each blocked heavyweight thread costs about 6 kbytes (KPCB, UPCB, and
stack). An FCRB (in the notionally revised design) is somewhere around
168 bytes. If the thread is going to be used for kernel-scheduled
execution after the reply is received, allocating a thread makes a lot
of sense, but this is not generally the case when you are doing
asynchronous I/O operations.

** What about I/O completion?

This is where the FCRB design got lost. If you are doing asynchronous
I/O, you need a way to know that the I/O has completed. The idea of the
bad design was to accomplish this with a scheduler activation. If the
completion notice happens this way, it can be used to handle the blocked
(synchronous) case too, which is what I attempted to do. This was too
much to load onto one straining activation interface.

When an asynchronous I/O completes, three things need to happen:

  1. The recipient needs to be told that *something* completed.

     [This is what the older UNIX SIGIO does]

  2. The recipient needs to discover *what* operation completed.

     [This is the mechanism added by UNIX AIO]

  3. The actual reply message needs to be collected.

     [This is defined by the messaging layer]

Given the scheduler activation mechanism, it is possible to use an
AIO-like delivery mechanism in Coyotos. Basically, you define an
"IoCompleted" exception and provide the operation identifier in an
auxiliary word. This is a process-internal exception; it isn't delivered
to an external fault handler.

Up to this point, the scheduler activation thing would have worked quite
well. The problem was that I went further and tried to bash part [3]
onto the same mechanism.

There is a simpler solution:

  (1) accept notice of completion as in AIO-style exception
  (2) use an explicit receive to pick up the message payload.

More specifically, do completion notification via exception only if
there is no currently pending receive on that FCRB already. The
notification exists only for the purpose of inducing the receive to
happen.

** Should all closed waits be handled using FCRBs?

It is not necessary to do this, but I am inclined to think that the
answer is usually "yes". The basic reason is to allow a process waiting
for a reply (i.e. in a closed wait) to be halted by a debugger without
losing any data. In the normal case, the process will be performing a
closed receive anyway, and no activation will be initiated. In the
debugging case we can avoid losing the message.

** So what about asynchronous *sends* ??

If we need a mechanism for asynchronous completion, what about a
mechanism for asynchronous sends?

My answer is "no". If the use of asynchronous receive is properly
engineered, sends will not block. If they do you have a systemic issue
and my sense is that you want to see it rather than obscure it. I could
be completely wrong on this, and I'ld appreciate input on this point.


shap

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