[cap-talk] EQ and the object-cap model

[Marcus Brinkmann]

At Mon, 11 Dec 2006 09:31:52 -0800,
Jed Donnelley <capability at webstart.com> wrote:
> 
> At 03:03 AM 12/11/2006, Marcus Brinkmann wrote:
> >At Sun, 10 Dec 2006 20:34:23 -0800,
> >Charles Landau <clandau at macslab.com> wrote:
> > > At 12:26 PM -0500 12/10/06, Jonathan S. Shapiro wrote:
> > > >>From a purist perspective, the one that we want is EQUAL?
> > >
> > > I can't think of much use for an equality operation that isn't
> > > durable. For example, it wouldn't satisfy the requirement of the
> > > Grant Matcher, which is the only example we have that everyone seems
> > > to agree needs EQ. The fact that implementing EQUAL? is undecidable
> > > doesn't make it very attractive, either.
> >
> >There may or may not be a use for such an operation in the client
> >space.  However there is one particular use of EQ*? that appears to me
> >important (well, relatively important depending on other aspects of
> >the infrastructure), and that is supported by a non-durable EQUAL?.
> >
> >This is if the server which implements an object gets a capability to
> >another object it implements in an invocation, and wants to perform
> >the operation on both objects at the same time (say a virtual copy
> >operation from one object to another).
> 
> I'll note in passing that this sounds exactly like the "MyCap?"
> need that I had in the DCCS mechanism:
> 
> http://www.eros-os.org/pipermail/cap-talk/2006-December/006255.html
> http://www.webstart.com/jed/papers/DCCS/
> (look for "extension capabilities").

Yes, I noticed that after reading your description.  Note that this
was also the result of a eq? discussion on l4-hackers mailing list
from the Dresden group.  It can be efficiently implemented in L4 with
any depth of delegation, because it's the same problem as invocation.

However, I should note in passing, given this opportunity, that it is
the death nail for my proposed third alternative OS design, which was
supposed to support unlimited depth of delegation well, because in
that case MyCap? would be potentially unbounded in time and punishes
the wrong party.  Too bad!

> >In EROS this is done
with the branding mechanism.
> 
> Can you point to or otherwise supply documentation on the "branding mechanism"?

My mind is sketchy on the details (Jonathan will be able to provide
more details and/or correct me), but in EROS it allows the constructor
to verify if a process was created by it or not.  The constructor
would use a kernel mechanism to associate a brand capability
(arbitrary capability) with a process it creates (how this is done is
what I don't remember, but any mechanism that allows you to associate
a capability with an object you implement would work).  Then there is
a function that allows you to test if the object named by a capability
has a specific brand---returning true if you can provide a copy of the
brand capability at sense time for comparison and false in any other
case.

Note that the only purpose of the brand capability is to provide an
unforgeable unique identifier that can be used for comparison.

> >If such an operation is not available, it can be
> >implemented using EQUAL? under some definition of EQUAL?.
> 
> Am I right in thinking that we would like the weakest capability
> identifying mechanism that will do what's needed?

I agree, provisionally (I hesitate to claim I know what's needed---I'm
a burned child in this regard).

> >In this case, it is sufficient for the client to prove that it held a
> >valid capability for the object at invocation time.  If it is revoked
> >afterwards doesn't affect the outcome of the operation in the server.
> >(Of course, if the server does not implement such operations
> >atomically it may have to recheck the EQUAL?-ness after reentering a
> >critical section, etc.  I think this was discussed before here on the
> >list, but it could have been hurd-l4---if somebody is interesting I
> >can search for it).
> 
> As I mentioned, I would like to hear more about what you refer to
> as the "branding mechanism" to see how it compares with other
> alternatives (if that's what they really are) to EQ.

Here is what we came up with for L4 as the minimal mechanism: If a
capability was a "my capability", the server could do an operation
that tested if that capability was pointing to the same communication
endpoint (think object), as a specified msg receive capability.
Usually receive capabilities are closely held by the server.  Note
that this means that you have to know before the test which object you
want to compare against, ie you need to supply a guess and can only
verify it.  In practice this requires a client to submit an
(server-local object id, capability) pair to provide a guess, and the
server needs to translate server-local object ids to receive
capabilities.  This is in fact similar to the branding mechanism,
except that the brand is hardwired to be the receive capability.

I can't see how one could be more minimal than that in supporting a
MyCap? operation.

Thanks,
Marcus