Re: Comparing "copy" and "map/unmap"

[Jonathan S. Shapiro]

On Sun, 2005-10-09 at 21:48 +0200, Matthieu Lemerre wrote:
> >> OK.  So you have to create a new forwarding object for each new
> >> client, but I assume this is a relatively cheap operation.
> >
> > I think there are good reasons to believe that a forwarding object can
> > be implented efficiently in the COPY model, while we know for sure
> > that the reverse is not true (ie, implementing COPY in the REVOCABLE
> > COPY model is inefficient).
> 
> It seems that a pointer to the real object would be sufficient.  The
> cost would be one indirection....

Yes. Or in the case of EROS, a capability. Also, you need to allocate
the storage to *hold* this indirection pointer.

>   But (as I wrote in the other mail),
> does the number of indirections increase with the mapping hierarchy,
> or is it constant?  I think that if you have 2 pointers...

It is possible in EROS to implement a design where the pointer chain is
kept limited and the recording of the revocation dependencies is pushed
to application code. The problem is that you really want a single
application to do this, and there is no one party who can correctly pay
for all of the storage required.

The concrete depth limit in EROS was 20. In 30 years of operation of
Gnosis, KeyKOS, and EROS, we never exceeded a depth of 3 in real
practice. We never bothered to consider any more clever strategy,
because it wasn't needed.

Note that the kernel is in a position to cache the traversal after you
execute it once.

> > This suggests to me that we should try to use less reference counting,
> > and not make it a fundamental paradigm of our operating system.
> 
> OK.  Several comment/issues come to my mind:

Some of this may be easier to see after you read my note on storage
allocation. My comments below assume that you have done so.

> 
> -If a server serves a ressource to a client, and the client is
>  destroyed.  How is freed the ressource?...

If the server paid for the storage in the first place, you already have
a bigger problem. If it did not, then why do you care? Let the client
clean up its own messes!

> To conclude, I don't know how a system without reference counting
> would look like.  Especially if we want to emulate POSIX.  But maybe
> we should look again at how it's done in EROS?

For POSIX, you definitely need reference counts, but these are not
capability-layer reference counts. These are reference counts that are
implemented by the POSIX server, which is an entirely different thing.
There is absolutely no need for these to be implemented in the kernel.

> > This is wrong.  The server implements the object, and never
> > distinguishes different users of the same object.  So, if the server
> > wants to reclaim the object, it will just destroy it completely,
> > revoking _all_ copies of the capability.  This is not selective
> > revocation.
> 
> I'm not sure we are speaking about the same thing here.  When the
> client has to map a capability to a server it does not trust, I think
> it would want to REVOCABLY COPY the capability to that server, so that
> it can itself revoke the right that this server has to use the object.

When a client transfers a capability to *anyone* it may want to revoke
that capability. It has nothing to do with whether the receiver is a
server.

But we need to challenge your assumption here: once I give a capability
to a hostile party, I have to assume that the hostile party misuses it.
If they *do* misuse it, then either:

  1) The object is robust against misuse, or
  2) The object itself is now corrupted.

In the first case, there is no need to revoke the capability. In the
second case, revoking the capability will not help. What I need to do at
that point is revoke the *object*, because it is now garbage.

The case for revoking the capability here is the possibility that the
receiver is *now* trustworthy, but may in the future become compromised.
It is simpler in this case to design the receiver not to hold on to
capabilities that it should not retain. Also, this does not address the
question of how you will know in the future that the receiver is no
longer trustworthy.

In EROS, the common pattern of exclusively used and confined servers
tends to make this a non-issue in our system designs.

> For instance, a client may want to give some server acces to a file,
> and that server would write something into the file.  Then, it would
> have to revoke the mapping, because else the server could use the file
> as memory provided by the client.

Yes. But how does it know when to perform this revocation? If the other
party (what you call the server) performs a close()-like operation, or
otherwise signals that it is "done", then you have a natural place to
revoke that capability. If they do not, and some watchdog goes off, then
what you know is that the file is probably corrupt and the right thing
to do is to destroy the file.

This is an integrity issue, not a security issue. Security issues are
relatively easy. Integrity issues are really really hard. Coyotos has
all of the mechanism needed, but *nobody* knows a consistent set of
design patterns for when to use them.

But yes, this is a good example of a place where you would impose a
wrapper for the purpose of imposing a temporal scope on the
relationship.

> BTW, I haven't told why I named capabilities which shouldn't be copied
> authentification tokens.  They would have been better named "exclusive
> capability" or something like that.  This is because we don't want
> these capabilities to be copied without the mapper being able to
> revoke the mapping (like for the notification server example).

I am still not sure why you want this. You appear to be concerned about
capability leakage. If you do not trust the downstream party, then
either

  1) You shouldn't send the capability. Even if it cannot leak
     directly, the hostile receiver can act as a proxy.

  2) You should confine the receiver so that it *cannot* leak.

Regardless, if you pass a wrapped capability and later destroy the
wrapper, you are guaranteed that no further use of the wrapped
capability through that wrapper is possible.

shap