[cap-talk] Capabilities - the rub, an account - Brinkmann

Marcus Brinkmann marcus.brinkmann at ruhr-uni-bochum.de
Tue Nov 28 09:22:40 CST 2006

At Mon, 27 Nov 2006 14:46:32 -0800,
Jed at Webstart <donnelley1 at webstart.com> wrote:
> As I've oft repeated on this list I'm an advocate of the "network down"
> approach to creating greater market share for object/capabilities.

I see.  I am at this point mainly interested in single nodes.

> policy.  It's been noted again and again on this list how it's
> possible to set up revocable capabilities, membranes, etc. on top
> of a simple base capability communication mechanism.  If such
> tracked delegation is used relatively rarely (relative to all process
> to process delegations) then I don't believe it need substantially
> effect system overhead.

I am currently looking into designs where it is not rare, but the

One can make a distinction here: If it is rare to create and invoke
such capabilities, then of course no special mechanism is required,
and the monitor can just interpose all IPCs.  If it is rare to create
such capabilities, but invocation is not, then you may want to
optimise for invocation.
> >Of course, there may be alternatives.  One may try to design a
> >microkernel system that efficiently supports an alternative set of
> >operations that is more adequate to build such systems.  Or one may try
> >to design the operating system in a way to make such operations rare.
> >The latter is what we (Hurd) are currently pursuing.  But that is
> >arguably more challenging than mere bookkeeping ;)
> The later is what I was suggesting above.  Since I have implemented
> a comparable scheme, I know that it can be as simple as 'mere' book keeping,
> though of course it need not be.  In our system an application wishing to
> create a revocable capability (similar to delegation) would make such a
> request of the server.  The server would add a book keeping entry and
> return a new capability with the same permission (but that can be revoked
> through the book keeping entry, can have it's access audited, etc.).
> In our system the revocable capability went back to the requesting
> process that had the base capability.  To effectively place responsibility
> a delegated capability must be communicated directly to the
> subject (person, process acting on their behalf) - the delegate.
> That's the part of this procedure/protocol I would like to see discussed
> more if there is sufficient merit.

How did the server account for the resources required for the
book keeping?  I would expect the resources to be accounted
(eventually) to the actual receiver of the delegated capability.

> >However, my argument above goes beyond mere performance considerations.
> >There is a deeper problem involving timing guarantees.  Take for example
> >the L4 kernel, which has a rather straightforward capability mapping
> >model (for memory in L4 X.2, for other stuff as well in the upcoming
> >L4.sec designs).  The map operation can be performed in constant time,
> >no matter at which point in the hierarchy (and this requires tricky data
> >structures).  The unmap operation however is bounded by the height of
> >the unmapped subtree only.  This means in practice that a server can
> >only revoke a resource given to a client in a time that is only bounded
> >by the accumulated resources of programs cooperating with the client.
> In that case I argue that the design is flawed - though perhaps we aren't
> using common terminology.  Clearly the server can "revoke" any capability
> that it serves simply by noting in whatever table structure it uses to
> define the meaning of the capability that the capability is no longer
> valid.

You may consider it to be flawed, but the alternative you describe may
be worse, depending on your goals.  If you simply mark the capability
as dead, then you will have to check each interposed capability in the
hierarchy at each invokation.  This means that now the invocation
operation becomes unbounded in time, not a pretty sight.  Every
capability will only be revoked once, but it may be invoked many

I think this is what EROS does though, leading to the requirement of a
fixed upper level of nesting of wrapper capabilities to ensure a
bounded invocation time in the kernel.

> >I can think of ways to do away with this problem.  For example, the
> >server may not care if the user's own resources down the hierarchy are
> >not released properly.  However, the challenge is to come up with
> >something that is both reliable and efficient.  If you only care about
> >one, it's not particularly challenging.
> I'm getting the sense that you are dealing with the 'lost object'
> problem.  Namely an effort to notice if all the references to
> an object have been removed - so that the object itself can
> be destroyed.

That is tangential, yes.  However, in this case I was merely
describing the same solution to the unmap-unbounded issue as you
mentioned above.

I think I can follow what you are saying here, with the one thing I am
missing: How you did the accounting of the server-side resources for
delegated capabilities.


More information about the cap-talk mailing list