[cap-talk] Hybrid Cap Systems redux

[Sandro Magi]

I think these are the important questions, and my take on them may be 
controversial. ;-)

Jonathan S. Shapiro wrote:
> I agree. I further agree with Alan that the Singularity folks "missed it
> by *that* much" (which seems to be a sad tradition in OS work). At the
> end of the day, I am leading up to some very disturbing questions:
> 
>   1. Are OS-based cap systems, where I mean "OS" in the traditional
>      sense, as distinct from some sort of exokernel-style thing,
>      actually viable?

Yes, but only if you're willing to live with certain limitations. For 
many years I've watched you struggle to implement fundamental capability 
abstractions on increasingly uncooperative hardware. I think a 
capability OS is possible, but certain abstractions will never be 
efficient. This is why I switched my focus from OSes to languages a few 
years ago. That said, I'm not yet convinced that all of these 
unrealizable abstractions are actually useful.

For instance, it's my impression that membranes are only really to be 
used for communication between high-level entities, in which case 
introducing an additional context switch isn't that huge a performance 
hit. Even in a cap-language, I can't imagine wrapping an application's 
performance intensive core functions and data structures in membranes. 
Membranes will always be a coarser-grain access control pattern.

Still, certain efficiently expressible cap-language patterns will never 
be efficient in a hardware OS, so either you live with those limitations 
and see how far you can go, or you move away from purity slightly.

>   2. If language-based cap systems are the way to go, how do we deal
>      with things like system-wide persistence?
> 
>      Systems like E rely implicitly on the assumption that the size of a
>      VAT is less than the size of a single hardware address space.

Garbage collection is a natural persistence mechanism. GC already 
traverses live data and read and write barriers are executed when 
updating references. GC can thus implement checkpointing as found in EROS.

>   3. If the answer is: "persistence is necessarily scoped by some
>      domain" Then it follows that we have a layered cap design (c.f.
>      E refs vs. E sturdyrefs), and the next question should be "how
>      shall we choose a proper granularity for such domains?" and in
>      particular, "is it feasible to build a system in which the largest
>      persistence domain is bounded by the hardware address space size?"

Do you mean, can a domain span the entire addressable memory space? ie. 
4GB on 32 bit systems. If you're using a cap language with safe manual 
memory management (MM), I believe the answer is yes. If you're using 
automatic MM, there will always be some overhead (remembered sets, 
object headers, tags, etc.), so the answer is no, but live data can 
probably get within 30% of it given a sufficiently advanced GC. I'm 
ignoring automatic MM with region inference, as their properties aren't 
sufficiently well known yet.

>   4. Given that a pure language approach abandons any hope for backwards
>      compatibility with existing programs, can we come up with a hybrid
>      approach in which address-space based protection remains a viable
>      design option?

I too once believed language systems abandon backwards compatibility. 
There are now two possible solutions to keeping old code that I know of:

1. Proof-carrying code can support arbitrary assembly code execution, 
while retaining various safety properties. It can fulfill the dream, 
once it matures in 10 years. ;-)

2. Compiling unsafe code like C via a virtual architecture which injects 
safety checks into code, like LLVM's LLVA architecture, points to an 
alternate approach which might become viable sooner. There's no paper 
that I know of, but I linked to a presentation of theirs earlier where 
they describe overheads in the 5-10% range IIRC. That's totally 
acceptable overhead for memory safety in C.

Sandro