[cap-talk] On revocation and the use of wrappers and In Defenseof Identities

Sat Dec 9 06:09:26 CST 2006

On 07/12/2006, at 17.35, Marcus Brinkmann wrote:

>At Thu, 07 Dec 2006 09:41:08 -0500,
>"Jonathan S. Shapiro" <shap at eros-os.com> wrote:
>> 
>> On Thu, 2006-12-07 at 14:57 +0100, Marcus Brinkmann wrote:
>> > > The server can always refuse if a given capability has been
delegated
>> > > too many times.
>> > 
>> > As Neal said.  Or: "What's too many?" [1]
>> 
>> I appreciate the humor, but there is a serious problem here in the OS
>> context. If wrapping or delegation involves building a data structure,
>> my bet is that data structure will grow linearly in the number of
>> delegations.
>
>I can accept that assumption.
>
>> In order for the OS to have bounded-time operations, it MUST set a
bound
>> on the number of steps it will take in any given operation.
>
>Sure, that's an obvious truism.  But an operation can also be
>preemptible, in which case it does not need to be bounded in time (at
>least from the kernel's perspective).  Yes, this causes other
>problems.  But it can be a viable design alternative.

The other problems you are referring to are really nasty for a real-time
system like Coyotos. The nastiest problem is that if atomic operations
aren't bounded in time you lose the guarantee of measurability of
real-time accuracy.

>
>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.
>
>EROS does not need preemptible operations, but it puts a hard limit at
>the depth of delegation possible.  L4 is highly optimized for the
>common case, but punishes the wrong party: The revoker does not
>control subsequent delegations, thus it should not be punished by
>them.
>
>There is a third alternative: If one favors flexibility and security,
>one would want to make revocation constant in time like EROS, but
>allow arbitrary nesting like L4.  The consequence would be a hefty
>performance and code complexity penalty because invocation would need
>to be preemptible.  However, it seems to me that this third
>alternative may be a safer approach than what L4 is doing.
>
>I do not know about a system that follows this approach, thus I can
>not say if it is "viable" or not.  It sounds interesting to me in any
>case.
>
>> Brinkmann and Walfield's "Critique of the Hurd" complains that EROS
>> imposes such a limit (He states it incorrectly at 4.  The actual number
>> is 20)

I'm not sure that unlimited delegation makes sense in any case. When you
have delegated 10 or 20 times it is largely sufficient for any real job.
Already at 15 delegations you have somewhere 15 modules in your delegation
chain, your application is very complex. What application would do that
much delegation?

>
>As for the critique, see Neal's reply.  Thanks for giving the actual
>number, I keep forgetting it, although I think I remember that it was
>supposed to be much smaller in Coyotos.  If I mentioned a 4 somewhere,
>it may have been some left-over bits of information from our Coyotos
>discussions.
>
>> but fails to contemplate the consequences of his preferred
>> alternative (unstated, but presumed to be "no traversal limit").
>>
>> The absence of a limit entails loss of bounded-time atomicity and
>> potential infinite loops in the forwarding structures that the
>> kernel cannot effectively guard against.
>
>That may be true for EROS/Coyotos.  Unless I am missing something
>fundamental, it does not necessarily needs to be true for other
>systems as well.
>
>> RANT
>> 
>> Nobody likes having the bound, but I confess I get annoyed by that
>> particular critique. It comes up surprisingly often, but I have *never*
>> observed the critic to either consider the alternative or propose a
>> viable replacement mechanism.
>>
>> I'm not annoyed at Neal or Marcus. I just get tired of hearing
one-sided
>> reasoning on this issue.
>> 
>> END RANT
>
>I don't criticize the bound in the context of the EROS/Coyotos
>operating system.  It does what it does in an appropriate manner.
>There is not much to be gained from simply removing (or increasing)
>the bound in EROS and keeping the rest of the system as it is.  My
>criticism of the bound stems from a desire to explore other system
>designs which use revocable delegation without interposition as the
>only delegation mechanism.  For these, other system mechanisms are
>required.  Can such a system be viable?  Nobody has built (or
>published) such a system yet, so we can't know for sure.
>
>However, I am aware of at least one potentially viable replacement
>mechanism, and that is the L4 mapping model.  It is an open question
>if the L4 group can feasibly address the resource accounting problem,
>but the L4.sec designs are interesting.  I have some doubts if the L4
>unmap operation is really guaranteed to succeed at all in finite time
>(I don't know any of the many implementations in sufficient detail),
>but that may be because of aggressive optimization that can be
>sacrificed (by corresponding checks in the map operation), or it may
>be one of those warts that every system seems unavoidably to end up
>with.
>
>Design and Implementation of the Recursive Virtual Address Space Model
for
>Small Scale Multiprocessor Systems
>http://i30www.ira.uka.de/teaching/theses/l4ka/index.php?lid=en&year=2002&d
ocid=814
>L4.sec implementation:
>http://www.tud-os.org/papers_ps/kauer-diplom.pdf
>
>In fact, this was discussed before in some detail:
>http://lists.gnu.org/archive/html/l4-hurd/2005-10/msg00419.html
>
>Thanks,
>Marcus
>
>_______________________________________________
>cap-talk mailing list
>cap-talk at mail.eros-os.org
>http://www.eros-os.org/mailman/listinfo/cap-talk