[cap-talk] On revocation and the use of wrappers and In Defenseof Identities
Jonathan S. Shapiro
shap at eros-os.com
Mon Jan 15 10:59:31 CST 2007
On Mon, 2007-01-15 at 06:09 +0100, Pierre THIERRY wrote:
> Scribit Marcus Brinkmann dies 07/12/2006 hora 17:35:
> > Two existing implementations:
> > 1) Make invocation constant in time and revocation linear in time with
> > the depth of delegation. This is what current L4 implementations
> > do. In this case, the revoker will be punished. L4 does allow
> > arbitrary nesting (even in the L4.sec designs) at the cost of
> > making unmap() preemptible.
> > 2) Make invocation linear in time with the depth of delegation and
> > revocation constant in time. This is what EROS does. In this
> > case, the invoker will be punished. EROS does not allow arbitrary
> > nesting.
> Maybe I'm missing something about that previous discussion on revokation
> and delegation: you discuss time linear with the depth of delegation,
> but isn't delegation a tree? Then shouldn't time be exponential with
> depth of delegation?
No, but I DID make some errors in my previous statement. Here is an
attempt to correct that:
FACTS (as I understand them):
L4.1: Receiver of invocation can be determined in constant time.
L4.2: Revocation of delegations is linear in the total number of
delegations that have been performed below the point of
revocation (because each delegation only needs to be revoked
L4.3: All capability transfers are performed by map. Therefore all
capability transfers are revocable delegations.
L4.4: Capability transfer often has the same cost as revocation,
because an occupied slot must be revoked before it can be
EROS.1: Receiver of invocation can be determined in time that is
linear in the number of revocable delegations of the
capability being invoked.
EROS.2: Revocation of revocable delegations is constant time.
EROS.3: All capability transfers are performed by copy. Capability
transfers are not revocable unless special actions are taken.
EROS.4: Capability transfer takes constant time.
1. Relative performance is NOT simple to compare. Every IPC transfers at
least one capability (the reply capability), and this will invariably go
into an occupied slot. Therefore, the cost of IPC is determined by
L4.1 + L4.4 => linear in total number of delegations of
capability being overwritten
[times number of caps received, but this
is usually 1]
EROS.1 + EROS.4 => linear in depth of delegations of invoked
2. If we believe that most IPCs involve processes at the "leaves" of the
delegation tree (which does seem likely), the L4 design may be better.
3. The EROS design is not intended to be heavily used without trusted
mediators. A correctly implemented family of mediators can keep the
chain depth at one.
Eric Northup has proposed an internal optimization in EROS that would
cache the traversal, yielding a typical case invocation in unit time but
a revocation delay that is linear in the depth of the delegation.
Jonathan S. Shapiro, Ph.D.
The EROS Group, LLC
+1 443 927 1719 x5100
More information about the cap-talk