[cap-talk] Capability levels

[David Hopwood]

Jed at Webstart wrote:
> At 06:18 PM 8/14/2006, David Hopwood wrote:
> 
>>...the layering is "hardware \ language1 \ OS \ language2 \ application",
>>where "\" means "is below". From an application programmer's point of
>>view, and from the point of view of OS design rather than implementation,
>>however, "language1 \ OS" can be viewed as a single layer.
>>
>>(The OS may be implemented in more than one language. Also, some of what
>>appears as "the OS" to application programmers may in fact be implemented
>>in per-process libraries, rather than in the kernel. But these are just
>>implementation details.)
> 
> I believe this difference in views arises from a difference in 
> 'operating system' architectures.  To me the above suggests the typical
> monolithic operating system architecture - e.g. Windows or Unix.

I didn't mean it to do so. In a microkernel or exokernel operating system,
the layering of language(s) and OS is still as I described above for each
process/domain. The difference is that there are *also* a large number of
"horizontal" dependencies between domains. (Such dependencies can exist in
monolithic OSes, but are less common.)

> My thinking about operating
> systems reflects what's typically referred to as a micro kernel architecture
> where all processes (active objects) are in a sense equal except in so far
> as some may have more permissions than others (POLA).  E.g. consider
> the NLTSS architecture as depicted in:
> 
> http://www.webstart.com/jed/papers/Components/Figure-4-50.gif
> (from http://www.webstart.com/jed/papers/Components/ )
> 
> In such an architecture, what's referred to as the "message system"
> (and at least the network driver, perhaps the other drivers in terms
> of the implementation) seems to fit into the sort of 'operating system'
> category that you've depicted in your diagram above.  This part of the
> "system" supports only the "invoke" or "communicate" functionality
> of the system.  All services that are typically considered operating
> system services (e.g. file access, process creation and manipulation,
> directory support, user/account management, etc., etc.) are made
> available through processes with more or less privileges.
> 
> I believe that many/most micro kernel architectures are comparable.
> For example, one could consider Mach and it's "port"s.  The
> micro kernel implements the communication primitives on ports,
> and user mode processes (with various permissions needed to
> get their jobs done) implement the majority of the services that
> are typically considered to compose the "operating system".
> All such processes are given whatever privileges (permissions)
> they need in terms of ports to perform their needed services.
> <unfortunately the view of the Mach kernel is often hidden
> under a set of apparently monolithic "OS" services as in MacOS>.
> 
> Considered in the light of such micro kernel architectures, what do
> the "Capability Levels" look like?  I believe that in such architectures
> any software that goes into the micro kernel can more appropriately
> be considered as part of the hardware level - e.g. like in a machine
> with capability hardware such as the Plessey-250.  All it provides
> is an invoke or communicate "instruction".

Actual capability hardware is very uncommon. I agree that an invocation
primitive can be viewed as an instruction -- but it is an instruction in
the virtual machine provided by the OS, which is clearly at a different
level than ("above") the hardware.

[snip]
> As I hope you can see, for me the "level" of the capability
> connotes how widely it can be used:
> 
> I.    Language level capabilities can nominally only be used within
> a single language, or perhaps by conventions between languages
> inside a single process (shared memory, OS level protected domain)
> though shared library conventions.
> 
> II.   IPC (operating system) level capabilities can be used
> through inner process communication between processes
> (e.g. run by different "users", in different protection domains,
> etc.) within a single "operating system" (think DVH, KeyKOS,
> or EROS) which defines the capability invocation and delegation
> mechanisms between processes.
> 
> III.  Network level capabilities can be used by any process anywhere
> on the network.  They are generally a higher level abstraction that
> can be used by processes of many different types (e.g. with
> or without confinement, nominally capability systems or
> ambient authority systems, etc.).

I don't understand why you are referring to this as the "level" of
the capability [system].

As I understand it, one of the earliest uses of layered abstraction
levels to describe and inform the design of operating systems was
Dijkstra's description of the THE operating system. See
<http://www.cs.utexas.edu/~EWD/ewd01xx/EWD196.PDF>, especially the
subsection "System hierarchy".

I am using "level" in the sense that Dijkstra used it. I think this
is also what is usually meant when referring to levels in protocol
design, or layered software architectures in general.

The concept you're referring to above seems to be something entirely
different, which could perhaps be called "scope". More precisely, it is
the scope of validity of a capability, or of a capability representation.

[...]
>>>...I guess you're basing your argument on the issue of who's in
>>>control?
>>
>>Yes. Isn't that the most important point?
> 
> As I hope you can see in the above - no, I don't think the issue
> of control is the most relevant.  In a POLA architecture there is
> no control hierarchy, but rather each independent entity is
> trusted with just its needed POLA.  What's important to me
> is the levels of communication that reflect the level of composition.
> 
> I see IPC level capabilities generally as being composed of language
> level capabilities and network capabilities being composed of IPC
> level capabilities - [...]

That is really very imprecise. These are not "composed of" relations,
AFAICS.

In fact there is no necessary relation between these capability types
at all; a system may allow capabilities of one type to act as forwarders
to capabilities of another type, but it need not do so (and it is rarely
possible to hide all of the semantic differences between the different
levels of capability system, i.e. this forwarding/proxying is not fully
transparent).

> - though I admit that independent capability
> models (standards/implementations) can be created at all three
> levels.  I generally see language level capabilities as needing
> an extension mechanism to be used at the IPC level.  I generally
> see IPC level capabilities needing an extension mechanism
> to be used at the network level (DCCS was such an extension
> mechanism).
> 
> My dream (I have a dream!!) [goal] is to blend, merge, combine
> these levels, at least the terminology and I hope the implementations
> (though perhaps with caching optimizations at each level) so that
> we have a single capability (communicable permission token)
> notion that works across all levels:
> 
> (hardware - if any), language, IPC, and network.

I am much less optimistic about the feasability of doing this in general;
I think that for it to work without imposing unreasonable complexity,
the systems at different levels will have to be codesigned.

Note that we already have a capability system with codesigned language
and network levels: E is such a system. IMHO 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.

(One such limitation is poor support for resource accounting and protection
against denial of service. <http://www.cs.utah.edu/flux/papers/redline-hotos7.pdf>
has an interesting point of view here.)

-- 
David Hopwood <david.nospam.hopwood at blueyonder.co.uk>