RE: Split Capabilities: Making Capabilities Scale Karp, Alan (alan_karp@hp.com)
Fri, 30 Jun 2000 08:45:43 -0700

> -----Original Message-----
> From: Norman Hardy
[mailto:norm@netcom.com]
> Sent: Thursday, June 29, 2000 6:41 PM
> To: Karp, Alan; 'e-lang@eros-os.org'
> Subject: RE: Split Capabilities: Making Capabilities Scale
>
> (snip)
>
> Capabilities are a bit like floating point values. You do not
> need enough
> storage to keep every possible floating point value even
> though in general
> a particular computation may in principle use any possible
> floating point
> number. As with fp numbers you may discard them and reproduce
> them upon
> demand. Most Keykos objects were created and destroyed with
> few of the
> possible capabilities for them ever having existed. Many (most?)
> capabilities were created, passed, used and then discarded in
> less than a
> second.
>
> Your pattern may have other strengths, however.
>

Many cryptographically secure capabilities are not lightweight enough to be treated so cavalierly. For example, the SPKI certificates used in e-speak Beta 3.0 carry quite a bit of information, and delegating a subset of the rights is a non-trivial operation. We were quite latency sensitive in the early days of e-speak, sub millisecond latency being our goal. I don't think that's possible if capability construction is in the critical path.

There is another difference here. Most Keykos objects were transient instantiations. Many if not most of the services and resources in e-speak are persistent or at least long-lived. Examples include files, SAP, and the like. Hence, it is not unlikely that most combinations of access rights will be needed over the lifetime of an e-speak resource.

>

>		(snip)

>
> If we are to model the access that the Unix directory logic
> provides to
> files we may proceed as follows: The directory object holds a strong
> capability to each of its files or subdirectories. A
> requestor invokes the
> directory object via a capability that identifies his uid & gid. The
> directory code now has the information to produce and return
> a capability
> of just the right strength. The directory object need not store this
> returned capability as it can be easily regenerated on demand. I may
> misunderstand your example.

The problem is not the number of capabilities held by the directory service; it's the number of capabilities held by the client. I'm always free to treat my collection of capabilities as a cache and get a new version from the directory service if I've flushed one that I need. Still, I'll want to hold as many as I can for as long as I think I'll need them for performance reasons.

Besides, we can't really use that approach in e-speak because of the additional latency. The two step process you describe doubles the latency. That's because in e-speak the holder of the strong capability is a service, not an object. An e-speak client would have to invoke the directory service to get its access rights capabilities and only then invoke the service. In the worst case, the client, directory service, and resource all reside on different machines.

There's also the problem of mapping a uid to sets of access rights. What you describe is an identity certificate (not a capability) that is used to map into an access control list. That's not a pure capability system. (If the uids are dummies, the requester can just as well use the identity certificate as a capability.)

>
> >There's still a problem with the approach you describe.
> Namely, over time
> >I'll accumulate a large number of capabilities. Either I'll
> have to present
> >them all on each request,
>
> If the code making that request is capability savvy it whill
> know exactly
> which capability to invoke. It probably depends uniquely on
> the call site.
> I think there is a conceptual mismatch here. Perhaps I am
> just confused.

No confusion. If you're capability savvy, you need this code. My point is that you don't need this code (one less thing to debug) with split capabilities.

>
> Irrelevant anecdote:
> Some Prolog systems intern floating point numbers. This has prevented
> serious physics from using Prolog at least once. (There might
> have also
> been other problems. This was the first show stopper.)
> Norman Hardy <http://www.mediacity.com/~norm>
>



Alan Karp
Decision Technology Department
Hewlett-Packard Laboratories MS 1U-2
1501 Page Mill Road
Palo Alto, CA 94304
(650) 857-3967, fax (650) 857-6278