[cap-talk] kernel object knowledge

[Charles Landau]

At 1:23 PM -0400 5/30/07, Jonathan S. Shapiro wrote:
>On Wed, 2007-05-30 at 10:09 -0700, Charles Landau wrote:
>>  At 1:53 PM -0400 5/29/07, Jonathan S. Shapiro wrote:
>>  >   2. Naive (and even sophisticated) membranes must perform
>>  >      storage allocation on every invocation
>>
>>  to wrap every capability passed
>>
>>  >, except where
>>  >      they are able to recognize a capability as EQ to some
>>  >      capability that they have already wrapped.
>>
>>  Don't these difficulties apply also to non-oblivious membranes,
>>  though to a lesser degree? A non-oblivious membrane may know that
>>  some capabilities do not need to be wrapped, but there may still be
>>  some that do need to be wrapped. At best, a non-oblivious membrane
>>  simply lowers the bound of storage required (possibly lowering it
>  > from infinite to finite).
>
>I suspect (without any evidence) that the requirement to wrap (or avoid
>wrapping) is a pure function of the capability type, and that oblivious
>membranes can mostly implement that.
>
>Assuming that a bounded number of capabilities are transferrable per
>message, the oblivious membrane has a storage requirement that is
>O(n-message). The non-oblivious membrane reduces this to
>O(n-distinct-caps-xferred).

Assuming the system has an EQ operator, both kinds of membranes can 
determine whether passed capabilities are distinct and thus need to 
be separately wrapped. Thus it's O(n-distinct-caps-xferred) for both.

>Neither number is usefully small, since both
>numbers considerably exceed available storage. Indeed, both requirements
>likely exceed total historical world production of real storage media.

I don't see how this statement can be justified. Let's take an 
example. Consider a membrane that wraps a key to some output device 
such as a terminal or system log (see for example 
http://www.eros-os.org/devel/ObRef/kernel/LogAppend.html). The only 
key that needs to be wrapped, other than the original log key, is the 
resume key from the call. (All other passed keys are EQ to the void 
key.) On each call, a new resume key is passed. But, the membrane can 
observe that previous resume keys have become void and thus no longer 
need to be wrapped. So in this case the storage is actually bounded 
to that needed to wrap two keys.

In this example we used knowledge of the protocol to analyze the 
storage requirement, but the membrane does not need to know the 
protocol.