Re: Reliability of RPC services

[Jonathan S. Shapiro]

On Mon, 2006-04-24 at 11:09 +0200, Bas Wijnen wrote:
> On Mon, Apr 24, 2006 at 12:24:34AM -0400, Jonathan S. Shapiro wrote:
> > On Sun, 2006-04-23 at 00:31 +0200, Bas Wijnen wrote:
> > > This can be done in the capability structure itself, which is paid for by
> > > the owner, not by the object or the kernel.
> > 
> > I do not believe so. Anything that is stored in the capability itself is
> > smashed when the capability is overwritten. I thought that Marcus wanted
> > notification even in that case.
> 
> I must have misunderstood how capabilities are stored.  I thought they were in
> kernel-controlled (but user owned) memory, and could only be modified via
> kernel calls.  How else can you protect against forging them?
> 
> So I was assuming that the kernel needed to do the overwrite on behalf of the
> program.  In that case it can include the notification check as part of that
> operation.
> 
> But appearantly I misunderstood how things work.  Could you please explain
> this a bit?

Let us start closer to the beginning.

1. Capabilities are only overwritten as a consequence of invoking some
capability. Every capability invocation has input and output arguments.
All capability writes happen as a side effect of delivering output
arguments. That is: in a capability system, IPC is a special case of
capability invocation.

2. All notifications are delivered by IPC. This includes death
notifications.

These two statements together lead to a reductio problem: every IPC may
be required to send other IPCs before it can proceed. The reductio can
be solved provided that the death notification does NOT transfer any
capabilities (which, fortunately, it does not).

However, we now have the situation that if the initial invocation sends
K capabilities, there may need to be as many as K death notices -- one
for each overwrite. In Coyotos, K may be as high as 256. Sending K
notices is certainly not the usual case, but it must be a case that
works well if the system architecture is to be clean.

It is difficult to imagine how to make things slower than Mach, but this
approach would definitely do the job.



In any case, it does not achieve the desired objective. What this design
provides is "notify on capability overwrite", which is MUCH too strong.
It provides the recipient with very fine grain information about
capability drops (which should not be disclosed).

Also, remember that these capabilities must be "invoke only once", so
any overwrite of any of these capabilities will send a death notice, and
that death notice will guarantee that the client will never get a reply
from any other copy.

So in Marcus's scenario where C calls S which delegates to T, note that
S must not overwrite its capability until T replies. This essentially
defeats the purpose of delegation.

> 
> > > > It can shrink the list when it notices that some of these capabilities
> > > > have become invalid, but in abstract this could require an arbitrarily
> > > > large amount of storage.
> > > 
> > > No, at most one notification slot per capability.
> > 
> > Yes, but an arbitrary pool of clients can send an infinite number of
> > capabilities!
> 
> Yes, my remark didn't make much sense.  Sorry about that. :-)  What I wanted
> to say was that not only is this arbitrarily large amount of storage no
> problem for the kernel (because I assumed it would be part of the capability
> structure), but it would also not be a problem for the applications, because
> they reserve space for a number of capabilities, and the storage doesn't get
> bigger than that.  So even though it is an abitrarily large amount, no party
> will be unpleasantly surprised by the bill. ;-)

Reminder: the fragment above is discussing a different scenario: notify
on *last* drop.

The only way I can think of to do this is to put the capabilities on a
circular list whose head is the target object, and then notify when
there are no more capabilities.

The circular linked list is not difficult when all capabilities are in
memory -- this is how KeyKOS did things (for unrelated reasons).

The problem comes when the capabilities go out to the disk. The doubly
linked list (or equivalent) must be preserved. One can optimize this by
a hybrid data structure:

  - use the doubly linked list for in-memory capabilities
  - use a reference count for on-disk capabilities
  - switch mechanisms as capabilities are converted to/from
    their in-memory form.

but there is an unfortunate consequence of this: in order to overwrite
any capability, you must first bring its target object into memory. This
is necessary in order to decrement the reference count.

The paging behavior of this is quite horrible, and the memory pressure
that it would create is fairly impressive.

I can think of some ways to optimize it further, but it definitely is
not pretty.


shap