[cap-talk] Another "core" principle - virtualize capabilities

[Marcus Brinkmann]

Hi,

some technical notes.

At Wed, 03 Jan 2007 17:07:23 -0800,
Jed Donnelley <capability at webstart.com> wrote:
> >I claim that this is merely the beginning of a model for computation,
> >and that it lacks, among other things, in the words of Jonathan,
> >considerations of:
> >
> >    "durability, resource exhaustion, and synchronicity"
> >
> >In other words, it lacks *anything* related to the question of
> >executing instructions on a real machine architecture.
> 
> Hmmm.  I'm afraid I don't understand what you're getting at.
> In the object-capability model processes are assumed to
> execute the instructions of their underlying processor
> architecture in their own memory except for the "invoke"
> instruction (virtual instruction if you will) that behaves as
> above, namely that it allows:
> 
> 1.  Some amount of data and some number of capabilities
> to be sent to whatever services the invocation, and
> 
> 2.  The process to block until some amount of data and
> some number of capabilities are received in "reply" to
> the invocation.

Note that you introduce a new concept, that of a process, here.  You
then have to answer several questions:

  Are objects passive or active?

  How are concurrent processes scheduled?

  How do you avoid priority inversion?

  How can a process unblock a blocked process safely (important for
  signal delivery)?

The answers to these questions heavily influence the feasible system
structures that can be implemented.

> I'm not quite sure what you mean by "durability", but I expect
> that should also be included at a higher level.

Resources have different durability.  A page of memory allocated from
the system has different durability than a page of memory mapped by
the client, if the principle holds that the resource owner can destroy
the resource at any time.
 
> Fine.  Provide such an interface.  There's nothing about the base
> object-capability model that prohibits doing so.
> 
> >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.
> 
> Sorry, I do (as I did above).

Are you saying that it is adequate to start 5000 processes to poll
5000 file descriptors?  I would like to hear about your experiences in
that area.

> 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.

Note that there is no system to my knowledge which implements a
membrane primitive, and that all capabiities fetched through wrappers
are transfered, not delegated through the membrane.  That means that
all existing (to my knowledge) performance measurements are biased
towards the wrong (in my opinion) model.

> >It's not that "an" interface imposes necessarily performance problems.
> >However, the "wrong" interface certainly will.  What is the "correct"
> >and what is the "wrong" interface depends greatly on system details
> >that lie well outside of what is covered by your proposal.
> 
> At this point I don't see anything we can do but respectfully disagree.
> I have my experience in this area, described above.  I can only
> guess that you have some experience where an interface faithful
> to the object-capability paradigm imposed unacceptable overhead
> and you believe no object-capability interface could provide acceptable
> overhead.  Perhaps you can describe your experience in this
> regard and we can discuss it.

Just for the record: I don't claim that no object-capability interface
could provide acceptable overhead.  I am saying that we do not have
sufficient evidence to claim that a single universal mechanism is good
enough for all applications.

[Points about Mach deleted]

> That is, the trade-off isn't in the interface, it's in the
> service implementation.

I don't think it's one or the other.  Services can only make use of
the available interfaces, so the interfaces determine the feasible
design space for services.  Also, there may be outside constraints on
the feasibble server designs.  It simply isn't an option to put
everything into the kernel.

> >An analysis of how these failures can be avoided by careful
> >construction of the microkernel primitives is contained in the
> >following paper.  Also contains references to other projects.
> >http://www.l4ka.org/publications/paper.php?docid=642
> >
> >This last paper illustrates that the requirements for the
> >communication primitives go beyond what you specified.  This does not
> >mean that the decisions made by Liedtke are the only feasible ones,
> >but they show that the design constraints are tight.  You have to do
> >an effort to get a fast IPC mechanism, and you can not design the IPC
> >mechanism arbitrarily.
> 
> I didn't argue that care isn't required.  Certainly any interface must
> be carefully designed with performance in mind.  This is particularly
> true for an interface (e.g. an underlying invocation or RPC interface)
> on which much of a system will depend.  Even then, however,
> I argue that techniques are available for improving performance
> that can be done behind the scenes and needn't impact the
> base object-capability interface.

What is "behind the scenes" for you?  For me, it is everything that is
not in the kernel, which means just about everything except for the
basic mechanisms.  Maybe that's a difference between us that can
explain some of the confusion.

> ><snip>
> >It took years for the microkernel community to develop a fast IPC
> >mechanism (due to Liedtke).  Now it is taking years for the L4 group
> >to solve the resource allocation problems involved in managing the
> >mapping database.  And even if they succeed it is unclear if their
> >mechanisms are universal.  Comparing KeyKOS/EROS/Coyotos with L4 shows
> >many similarities, but also some fundamental differences.  Given that
> >even a single level of indirection makes these systems non-competitive
> >with traditional monolithic kernels without object/capability system
> >should make one careful about any exaggerated claims.
> 
> I described my approach to dealing with a "single level of indirection"
> above.  Namely, eliminate it where needed, smash the mechanism
> into a monolithic kernel (which may be needed to provide the required
> performance), but leave the interface the same.  In my experience
> this works - though it may not be as pretty or analyzable, etc. as
> some may wish.  It can meet the performance goals, and it may
> be the only approach that will.  It can also meet the functional
> goals of fully wrappable object-capabilities.

Frankly, I don't believe that it is the only approach that will.

I see now that you do not seem to be all that interested in using IPC
as a feasible basis for user-level system construction, and are
satisfied with a nicer set of kernel interfaces, that achieve, as you
say below, POLA and virtualization.  Ok, I see the value in that.  I
am not sure if people will go that way beyond what is already
happening with privilege separation and the likes, but I can see where
you are going.

> Clearly you can't demand a modular design with many domain
> changes per request, where domain changes have a significant
> cost, and meet a stringent performance goal.  Something
> has to give.  If the performance requirement is ascendent
> then I argue that the modularity must be sacrificed.

I think that's overly pessimistic.  Instead, I think the solution is
to avoid many domain changes per request.  I optimistically believe
that functional membrances can be implement in the kernel efficiently
as a fundamental mechanism.  Furthermore, Neal has a proposal for
fine-grained resource delegation without interposition, so that
resource management can be done without many domain changes per
request as well.

> I don't believe that an appropriately design object-capability interface
> is (in my experience) or will be a significant issue.  That interface
> has a value of it's own (POLA, virtualization, etc.) that can be
> maintained along with meeting performance goals.

[...]

> >You make it sound like Mach never happened,
> 
> Heh.  For me Mach didn't happen.

Some guys are born lucky :)

[...]

> All I can say is that in our system we had no limitations on message
> size (the buffers could be as large as the process memory).  Any of
> our operations could be what you regard as "statefull".  What's the
> problem?  Our servers handled the worse case behavior by clients
> (as I described elsewhere with "good guy" timeouts - an issue I
> hope to get back to) and we considered it quite a "pretty sight."

The first problem is that the bound on the IPC send operation is
potentially too large, unless you have a preemptible IPC mechanism.
This can be fixed by limiting the message size appropriately by the
kernel.

The second problem is that the server naturally absolutely must
restrict the size of an incoming message to the resources it is
willing to allocate to this request.  This can be fixed by limiting
the message size in the receive operation.

The third problem is that stateful communication has a significant
build-up overhead if sessions are instantiated frequently and are of
short duration, as often is the case in a fine-grained capability
system.  This can not be fixed except by using a stateless server
design, or by avoiding delegation of capabilities.

The fourth problem is that sessions expose the identity of the invoker
of a capability, which may be a security violation (depending on your
level of paranoia).

The fifth problem is that N cooperating clients can perform a DoS
attack at the server.

The sixth problem is that in many cases it is not clear what an
appropriate time out is (although some people say that it would be a
mistake to build systems without timing considerations in 2007, so
this may be a virtue as well).

Given your example, I consider problem 1, 2, and 6 as non-critical.
But 3 and 5 are serious, and I am of mixed opinion on 4.

> One other thing I'll mention in passing regarding your designs
> with fixed RPC buffers.  I can only assume you are suggesting
> such designs because the user buffers are copied at some point
> into system buffers apart from their ultimate destination.

No, the motivation is to get a bound on the length of the IPC
invocation in the kernel.  Also, it seems clear to me that the server
must limit the length of messages it accepts.

> I sense we may be at something of an impasse.

It probably was just a misunderstanding of what you said earlier.

Thanks,
Marcus