[cap-talk] KeyKOS, EROS, CapROS keyInfo/databyte (was: Re: EQ, MyCap? review)

[Eric Northup]

On February 12, 2008 5:13 PM, Jed Donnelley wrote:
[...]
> I think I get the idea.  One thing that's curious to me is
> the 16/8 bit size of the keyInfo/databyte.  I know that
> the equivalent in our NLTSS work was essentially a pointer
> of 64 bits.  I suppose that with a 16 bit keyInfo you
> were able to support 64k distinct objects?  Even that
> seems a bit limiting to me, but certainly only having
> the option for 256 seems almost impossibly constraining.

Given a fixed-length keyInfo/databyte, there is a design pattern which
enables extending it to an arbitrary length.  The object or service
which wants more Info for it's keys can Create proxy Domain whose sole
purpose is to relay all received invocations, prepending additional
keyInfo-like bits to the message.  These prepended are trustworthy
from the service's perspective.

As an optimization, one could multiplex multiple (up to 64k) keys onto
each proxy Domain.

In practice, a KeyKOS mechanism involving "Red Segments" ended up
being used for the proxies instead of actual Domains, but their
behavior was largely the same as what the proxy Domains would have
done.

[...]
> Since I believe I recall the KeyKOS, EROS, and CapROS capabilities
> are persistent, presumably you needed to use sufficient distinct
> "Key Info" values to distinguish from all possible past instances
> of capabilities (even if no longer valid) for a given deputy?
> I know this was an issue we had to deal with in NLTSS, so I'm
> just curious how you dealt with it in KeyKOS and heirs.

It was largely opaque to applications, but KeyKOS had an "allocation
count" field stored in each key that enabled distinguishing between
historical (but previously valid) and current keys to a particular
object identity.  There was a sever operation which would invalidate
all outstanding keys to an object.  A clever trick prevented the
persistent allocation counts from overflowing during the life of a
particular KeyKOS system even if an object was repeatedly and
frequently severed.

There was not an operation which would sever only those keys with a
Particular keyInfo/databyte value, and so the proxy Domain/RedSegment
objects ended up being used both to expand the per-facet data and
also to provide a mechanism to rescind keys to a particular subset of
facets.

I believe the Space Bank (either KeyKOS' or EROS') would be the code to
look at for how this was done.

-Eric