[cap-talk] Capability levels (simple summary fore and aft, DEMOS example between)

[Jed at Webstart]

At 10:02 PM 8/15/2006, David Hopwood wrote:

>... we need to identify and fix any
>limitations of E's capability model that prevent it from being extended
>to the OS level as well.

To me the above "extend" is the key to what I regard as the relevant levels.

You "extend" the language level capabilities (e.g. E's) to the "OS" 
level (what I consider the IPC level).

You "extend" the OS/IPC level capabilities to the network level.

At each extension you get broader scope.  I consider that broader 
scope a higher "level" - a higher capability level.  The broader 
scope (higher "level") of the IPC level allows its capabilities be 
used (delegated, invoked) between independent processes (e.g. run by 
different users in different domains) within a system.  The broader 
scope of the network level allows its capabilities to be used between 
separate systems in distinct administrative domains across a network.

To me an important value in the object capability model is it's 
simplicity.  I believe this simplicity is in some ways forced at the 
network level - where it is much easier to see/appreciate.  In some 
ways I regard the additional flexibility at the IPC level and even 
more flexibility at the language level as liabilities.  They allow 
mechanisms to be added that can (in my view) corrupt the base object 
capability model and introduce features that are difficult or 
impossible to extend to the next higher level.

As a case in point I've posted the "Task Communication in DEMOS" paper (1977):

http://www.webstart.com/jed/papers/DEMOS/demos.pdf

I think those of you who are familiar with DVH and that style 
operating system will find much familiar in the DEMOS 
design.  However, I think you will also see what I regard as 
aberrations that make such an architecture awkward/impossible to extend.

DEMOS had a fixed size data block mechanism associated with its 
"links" (capabilities - why they used a distinct term is unclear to 
me).  Here is an excerpted section of the paper to illustrate:
____________
The set of links held by a task defines its environment. A task may 
send messages
using any link it holds, and in some cases can move data to or from 
the memory area of
other tasks. Passing links between tasks allows programs to be 
divided into multiple
tasks in a convenient manner which is transparent to the tasks which 
might receive messages
from such programs. A link may be duplicated (with certain 
restrictions) so that
a link may be passed to another task without loss of the original 
communication path. A
message is sent to the task which created a link each time the link 
is duplicated or
destroyed, so that an accurate count of outstanding links can be kept 
by the link creator.
A variant of link passing allows duplicating the data area pointer of 
an existing
link in a newly created link. This allows one task to monitor the 
messages of a subtask
without having to move large amounts of data through intermediate 
buffers; the data connection
but not the message connection bypasses the monitoring task.
_____________

That business of sending a message to the task that created the link 
every time the link
is delegated (Baskett says "duplicated") is a peculiar variation on 
the reference count
business and dealing with lost objects.

One can see that in DEMOS ambient authority rears it's ugly head, e.g.:
_________________________________________________________
The following example interaction with the file system is intended to 
provide an
intuitive understanding of these basic operations. Suppose our 
example task, taskA,
wishes to read file FILEX. It must open the file, do some read 
operations, then close
the file. Each of these involves a message to the file system 
requesting an action and
a reply saying that the action is done.

To open the file, taskA performs a CALL operation on its standard 
link to the file
system, sending a message containing the file name and other required 
parameters. The
kernel creates a reply link, specifying the standard reply channel, 
and sends the message
and the reply link to the file system. When the file system receives 
the message,
it interprets it, opens FILEX, and in turn CREATEs a resource link to 
itself. The code
field of the resource link contains the internal index into the file 
system's open file
table entry for FILEX. The file system then does a REPLY operation on 
the reply link
sent by taskA, passing the resource link representing FILEX back 
along the reply link to
taskA. The completion message and the link ID for the resource link 
representing FILEX
are returned to taskA (which becomes ready because the implicit 
RECEIVE operation is satisfied).
The reply link is destroyed by the kernel after it is used. TaskA now has
two links to the file system, its standard request link and a 
resource link representing
FILEX. The file system has no links to taskA.
_________________________________________________________________

Finally (regarding DEMOS) here's a summary section relating DEMOS 
links to capabilities:
_________________________________________________________________
Links resemble capabilities, so their management must take into 
account many of the
well known difficulties of managing capabilities. This section 
discusses a management
scheme which addresses some of these difficulties.

One problem with capabilities is the possibility that they may 
continue to exist
after the object they point to is destroyed. In the case of links, 
the objects are
tasks. We use the standard technique of not reusing task identifiers 
to solve this problem.

Sometimes it is desirable to account for outstanding links to a task. 
For example,
the file system will need to keep track of open file links in order 
to close files when
their last link is destroyed. We allow this by notifying the creating 
task whenever a
resource or general link is duplicated or destroyed. A task may 
restrict its links so
that they may not be duplicated, in which case an explicit request 
for another link must
be made to obtain a second copy.

Yet another problem with capabilities is the lack of control over 
their being given
away to an unauthorized third party. Classifying links into types and 
restricting
specific operations to specific types provides a partial solution to 
this problem. For
example, resource links may only be passed to tasks with the same 
user ID. Reply links,
which can be used only once, reduce the problem of uncontrolled 
passing of links.
__________________________________________________________________

... "resource links may only be passed to tasks with the same user 
ID" ??!!??  ARG!

I think that by the time you get to the network level such nonsense 
must necessarily
fall away.


Of course I don't want to come down too hard on a paper written in 
relative isolation
in 1977, but I do want to illustrate the value that I see in 
considering capabilities in
their highest calling (which I regard as the network level ;-) to 
insure that any lower level
implementations can be extended and effectively used at the network level.

I believe that adapting a shared network level capability 
implementation (e.g. YURLs)
to optimized lower level mechanisms (IPC, language) is likely to be 
the most effective
approach to obtaining an object capability facility that can be used 
universally.

I think it's important to ask and answer questions such as:

"What's wrong with a network level implementation?"  (e.g. password 
capabilities
like YURLs).  Whatever is wrong, can it be remedied at the network level?  If
not, why not?  If not, then doesn't that mean that any capability mechanism
implemented at a lower level that remedies a perceived deficiency at the
network level CAN'T be extended to the network level?  Clearly if it could be
so extended, then its extension could be used as the correction to the network
level mechanism.

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