[cap-talk] Use-case: hybrid capability systems

[Jed Donnelley]

On 2/7/2008 6:53 AM, Jonathan S. Shapiro wrote:
> On Wed, 2008-02-06 at 14:07 +0900, John McCabe-Dansted wrote:
>> On Feb 6, 2008 1:20 AM, Jonathan S. Shapiro <shap at eros-os.com> wrote:
>>         On Tue, 2008-02-05 at 12:26 +0900, John McCabe-Dansted wrote:
>>         > Also for many purposes it is sufficient to know that the
>>         capability is
>>         > tainted by {A,B}
>>         
>>         
>>         This storage compression is certainly possible. How is it
>>         implemented
>>         given the requirement for prompt and explicit storage
>>         reclamation?
>>
>> I imagine that an identity A would be billed for the storage for each
>> data structure needed to describe the capabilities that processes
>> within A holds.
> 
> This does not seem to be possible -- or at least, none of us has found a
> way to make this work out in a pure capability design.
> 
> Capabilities contain no information about who holds them. In
> consequence, a pure capability system must keep track of the chain of
> capability transfers in order to implement this type of revocation. It
> is possible (indeed, necessary) for each party to pay for the storage
> associated with their step in the chain. But there is a problem with
> this.
> 
> In any system where storage is charged, prompt destruction is required
> in order to avoid denial of resource vulnerabilities. When a chain-like
> data structure is used, prompt revocation can break an intermediate
> link, causing all downstream caps to become invalid without any
> opportunity for repair.
> 
> So there are really two problems with a chain structure: the amount of
> storage involved and the problem of revocation.

Regarding the first, the amount of storage involved, let me say
two things:

1.  If allocating storage for intermediate capability communication
is an insolvable problem, then this is serious indeed.  Every
membrane mechanism from vats back to DCCS have the problem of
allocating storage for every capability that passes through
them.

2.  My own programming experience in this area is dated, but in
the NLTSS system we used a mechanism that we called "cachelib"
for this purpose.  The basic idea was that it would allocate
memory blocks of a requested size and manage an most recently
used cache of such object with aggressive writing to disk.
Blocks could be requested (locked) for reading or writing
and later released.  In the worse case a disk I/O operation
would be required to access (lock into memory) a storage
block.  This would happen of course if a very seldom used
block of memory was locked, but as with most caching mechanisms
could be tuned for quite good performance.

I'm sure there are modern equivalents that are at least
as effective.  Couldn't an approach like the above be used
to deal practically with the dynamic allocation and deallocation
of storage blocks for delegation or membraned information?

> It is possible to imagine a design in which some sort of capability
> exchange protocol is used at compartment boundaries so as to ensure that
> each compartment holds a copied capability C' that is independent of the
> origin capability C for purposes of revocation. It is not immediately
> clear how to do this without supporting protocol in every object
> implementation. Unfortunately, the objects themselves are not trusted
> and so it is difficult for the per-compartment reference monitor to call
> them safely in order to exercise the exchange protocol.

Sorry, but I don't understand what problem is being described above.
However, with regard to:

>> When all instances of capabilities that reference that data structure
>> are destroyed, that data structure is also destroyed.
> 
> This appears to suggest a reference counting design. There are two
> problems with such designs:
> 
>   1. Capability structures, in general may be cyclical. Any design
>      based on reference counts must be backed by a periodic GC. In
>      Coyotos, at least, this is a *disk* GC, which is quite expensive.
> 
>   2. Reference counts do not eliminate the requirement for prompt
>      object destruction.

I agree with both the above.  In a distributed design (e.g. network
capabilities) these problems become even more serious.

In our network capability work we found it necessary and
quite workable to distinguish between destroying references
to an object and destroying the object itself.  That is, we
explicitly permitted "lost objects" - objects with no
reference capabilities.  In some sense in our network
capability designs such "lost objects" were impossible,
because for any object that was being "paid" for (accounted),
a new capability to the object could always be re created by
whoever was paying for the object.  Also of course the
destroy operation could be done on an object at any time
though any capability with the appropriate permission,
rendering all other outstanding capabilities dangling.  Such
destruction was also possible by whoever was paying
for the object by the simple act of stopping payment.

This approach worked quite well for us and seems to me
analogous to the situation in the real world with such
"objects" (e.g. consider a bank account) and references
to same (e.g. consider a bank card).  I don't really see
an alternative for a large distributed system - as I
hope we achieve on the Internet.

--Jed  http://www.webstart.com/jed/