[cap-talk] kernel object knowledge

[David Hopwood]

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 seem to recall that MarkM had an implementation in E at one point that
> was able to evade this issue by re-using the proxy object in some clever
> way that I no longer recall. I may be mistaken.
> 
> 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). 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.

No. The total storage requirement introduced by a Horton-style membrane
(i.e. one that keeps track of delegation chains and supports revocation)
can be bounded by a small constant times the number of capabilities in the
system at any given time.

To see this, consider extending the representation of a capability by
adding a pointer to an object corresponding to the outermost wrapper.
I.e. if a wrapper would normally have fields 'interceptor' and 'inner',
we move those fields (which are immutable, even though 'interceptor'
may itself have mutable state) to the capability representation, which
is still passed by value.

To implement a Horton-style membrane, the 'interceptor' object would
contain a description of the principal (a Horton 'Who'), and a 'revoked'
slot. An invocation checks that 'interceptor->revoked' is false, and then
calls 'inner' with the original message. A reference to an object that
has not been wrapped is represented with a null 'interceptor' field.

A side benefit is that, for membrane implementations known to and trusted
by the kernel, no kernel <-> user mode transitions are necessary for
revocation checking (up to a fixed number of delegations per invocation).

There can be multiple independent revokers per principal, each implemented
by a different interceptor object.


We can make describe this a bit more generally, so that it applies to any
interception behaviour (essentially implementing a very simple metaobject
protocol). I'll call this the Interceptor Pattern:

  Start with a base object system in which references are of type
  BaseRef, and invocation is denoted by 'base_invoke(target, msg)'.
  A reference can be base_null.

  Construct a derived object system in which references are pairs of type
  BaseRef x BaseRef, and invocation is denoted by 'invoke(target, msg)',
  defined as follows:

    to invoke((interceptor, inner), msg) {
        if (interceptor == base_null) {
            base_invoke(inner, msg)
        } else {
            base_invoke(interceptor, `intercept(inner, msg)`)
        }
    }

  (OK, I fudged the difference between base messages and derived messages.
  But you get the idea, I hope.)

  For interceptor types trusted by the kernel, inline the implementation
  of 'intercept(inner, msg)'. This will probably involve a recursive call
  to 'invoke((base_null, inner), msg)', and this recursion can be unrolled
  to a fixed number of levels.

-- 
David Hopwood <david.hopwood at industrial-designers.co.uk>